md/persistent-data/dm-btree-spine.c

0001 /*
0002  * Copyright (C) 2011 Red Hat, Inc.
0003  *
0004  * This file is released under the GPL.
0005  */
0006
0007 #include "dm-btree-internal.h"
0008 #include "dm-transaction-manager.h"
0009
0010 #include <linux/device-mapper.h>
0011
0012 #define DM_MSG_PREFIX "btree spine"
0013
0014 /*----------------------------------------------------------------*/
0015
0016 #define BTREE_CSUM_XOR 121107
0017
0018 static void node_prepare_for_write(struct dm_block_validator *v,
0019                    struct dm_block *b,
0020                    size_t block_size)
0021 {
0022     struct btree_node *n = dm_block_data(b);
0023     struct node_header *h = &n->header;
0024
0025     h->blocknr = cpu_to_le64(dm_block_location(b));
0026     h->csum = cpu_to_le32(dm_bm_checksum(&h->flags,
0027                          block_size - sizeof(__le32),
0028                          BTREE_CSUM_XOR));
0029 }
0030
0031 static int node_check(struct dm_block_validator *v,
0032               struct dm_block *b,
0033               size_t block_size)
0034 {
0035     struct btree_node *n = dm_block_data(b);
0036     struct node_header *h = &n->header;
0037     size_t value_size;
0038     __le32 csum_disk;
0039     uint32_t flags, nr_entries, max_entries;
0040
0041     if (dm_block_location(b) != le64_to_cpu(h->blocknr)) {
0042         DMERR_LIMIT("node_check failed: blocknr %llu != wanted %llu",
0043                 le64_to_cpu(h->blocknr), dm_block_location(b));
0044         return -ENOTBLK;
0045     }
0046
0047     csum_disk = cpu_to_le32(dm_bm_checksum(&h->flags,
0048                            block_size - sizeof(__le32),
0049                            BTREE_CSUM_XOR));
0050     if (csum_disk != h->csum) {
0051         DMERR_LIMIT("node_check failed: csum %u != wanted %u",
0052                 le32_to_cpu(csum_disk), le32_to_cpu(h->csum));
0053         return -EILSEQ;
0054     }
0055
0056     nr_entries = le32_to_cpu(h->nr_entries);
0057     max_entries = le32_to_cpu(h->max_entries);
0058     value_size = le32_to_cpu(h->value_size);
0059
0060     if (sizeof(struct node_header) +
0061         (sizeof(__le64) + value_size) * max_entries > block_size) {
0062         DMERR_LIMIT("node_check failed: max_entries too large");
0063         return -EILSEQ;
0064     }
0065
0066     if (nr_entries > max_entries) {
0067         DMERR_LIMIT("node_check failed: too many entries");
0068         return -EILSEQ;
0069     }
0070
0071     /*
0072      * The node must be either INTERNAL or LEAF.
0073      */
0074     flags = le32_to_cpu(h->flags);
0075     if (!(flags & INTERNAL_NODE) && !(flags & LEAF_NODE)) {
0076         DMERR_LIMIT("node_check failed: node is neither INTERNAL or LEAF");
0077         return -EILSEQ;
0078     }
0079
0080     return 0;
0081 }
0082
0083 struct dm_block_validator btree_node_validator = {
0084     .name = "btree_node",
0085     .prepare_for_write = node_prepare_for_write,
0086     .check = node_check
0087 };
0088
0089 /*----------------------------------------------------------------*/
0090
0091 int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
0092          struct dm_block **result)
0093 {
0094     return dm_tm_read_lock(info->tm, b, &btree_node_validator, result);
0095 }
0096
0097 static int bn_shadow(struct dm_btree_info *info, dm_block_t orig,
0098           struct dm_btree_value_type *vt,
0099           struct dm_block **result)
0100 {
0101     int r, inc;
0102
0103     r = dm_tm_shadow_block(info->tm, orig, &btree_node_validator,
0104                    result, &inc);
0105     if (!r && inc)
0106         inc_children(info->tm, dm_block_data(*result), vt);
0107
0108     return r;
0109 }
0110
0111 int new_block(struct dm_btree_info *info, struct dm_block **result)
0112 {
0113     return dm_tm_new_block(info->tm, &btree_node_validator, result);
0114 }
0115
0116 void unlock_block(struct dm_btree_info *info, struct dm_block *b)
0117 {
0118     dm_tm_unlock(info->tm, b);
0119 }
0120
0121 /*----------------------------------------------------------------*/
0122
0123 void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info)
0124 {
0125     s->info = info;
0126     s->count = 0;
0127     s->nodes[0] = NULL;
0128     s->nodes[1] = NULL;
0129 }
0130
0131 void exit_ro_spine(struct ro_spine *s)
0132 {
0133     int i;
0134
0135     for (i = 0; i < s->count; i++) {
0136         unlock_block(s->info, s->nodes[i]);
0137     }
0138 }
0139
0140 int ro_step(struct ro_spine *s, dm_block_t new_child)
0141 {
0142     int r;
0143
0144     if (s->count == 2) {
0145         unlock_block(s->info, s->nodes[0]);
0146         s->nodes[0] = s->nodes[1];
0147         s->count--;
0148     }
0149
0150     r = bn_read_lock(s->info, new_child, s->nodes + s->count);
0151     if (!r)
0152         s->count++;
0153
0154     return r;
0155 }
0156
0157 void ro_pop(struct ro_spine *s)
0158 {
0159     BUG_ON(!s->count);
0160     --s->count;
0161     unlock_block(s->info, s->nodes[s->count]);
0162 }
0163
0164 struct btree_node *ro_node(struct ro_spine *s)
0165 {
0166     struct dm_block *block;
0167
0168     BUG_ON(!s->count);
0169     block = s->nodes[s->count - 1];
0170
0171     return dm_block_data(block);
0172 }
0173
0174 /*----------------------------------------------------------------*/
0175
0176 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info)
0177 {
0178     s->info = info;
0179     s->count = 0;
0180 }
0181
0182 void exit_shadow_spine(struct shadow_spine *s)
0183 {
0184     int i;
0185
0186     for (i = 0; i < s->count; i++) {
0187         unlock_block(s->info, s->nodes[i]);
0188     }
0189 }
0190
0191 int shadow_step(struct shadow_spine *s, dm_block_t b,
0192         struct dm_btree_value_type *vt)
0193 {
0194     int r;
0195
0196     if (s->count == 2) {
0197         unlock_block(s->info, s->nodes[0]);
0198         s->nodes[0] = s->nodes[1];
0199         s->count--;
0200     }
0201
0202     r = bn_shadow(s->info, b, vt, s->nodes + s->count);
0203     if (!r) {
0204         if (!s->count)
0205             s->root = dm_block_location(s->nodes[0]);
0206
0207         s->count++;
0208     }
0209
0210     return r;
0211 }
0212
0213 struct dm_block *shadow_current(struct shadow_spine *s)
0214 {
0215     BUG_ON(!s->count);
0216
0217     return s->nodes[s->count - 1];
0218 }
0219
0220 struct dm_block *shadow_parent(struct shadow_spine *s)
0221 {
0222     BUG_ON(s->count != 2);
0223
0224     return s->count == 2 ? s->nodes[0] : NULL;
0225 }
0226
0227 int shadow_has_parent(struct shadow_spine *s)
0228 {
0229     return s->count >= 2;
0230 }
0231
0232 dm_block_t shadow_root(struct shadow_spine *s)
0233 {
0234     return s->root;
0235 }
0236
0237 static void le64_inc(void *context, const void *value_le, unsigned count)
0238 {
0239     dm_tm_with_runs(context, value_le, count, dm_tm_inc_range);
0240 }
0241
0242 static void le64_dec(void *context, const void *value_le, unsigned count)
0243 {
0244     dm_tm_with_runs(context, value_le, count, dm_tm_dec_range);
0245 }
0246
0247 static int le64_equal(void *context, const void *value1_le, const void *value2_le)
0248 {
0249     __le64 v1_le, v2_le;
0250
0251     memcpy(&v1_le, value1_le, sizeof(v1_le));
0252     memcpy(&v2_le, value2_le, sizeof(v2_le));
0253     return v1_le == v2_le;
0254 }
0255
0256 void init_le64_type(struct dm_transaction_manager *tm,
0257             struct dm_btree_value_type *vt)
0258 {
0259     vt->context = tm;
0260     vt->size = sizeof(__le64);
0261     vt->inc = le64_inc;
0262     vt->dec = le64_dec;
0263     vt->equal = le64_equal;
0264 }