1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (C) 2011 Red Hat, Inc. 4 * 5 * This file is released under the GPL. 6 */ 7 8 #include "dm-btree-internal.h" 9 #include "dm-transaction-manager.h" 10 11 #include <linux/device-mapper.h> 12 13 #define DM_MSG_PREFIX "btree spine" 14 15 /*----------------------------------------------------------------*/ 16 17 #define BTREE_CSUM_XOR 121107 18 19 static void node_prepare_for_write(struct dm_block_validator *v, 20 struct dm_block *b, 21 size_t block_size) 22 { 23 struct btree_node *n = dm_block_data(b); 24 struct node_header *h = &n->header; 25 26 h->blocknr = cpu_to_le64(dm_block_location(b)); 27 h->csum = cpu_to_le32(dm_bm_checksum(&h->flags, 28 block_size - sizeof(__le32), 29 BTREE_CSUM_XOR)); 30 } 31 32 static int node_check(struct dm_block_validator *v, 33 struct dm_block *b, 34 size_t block_size) 35 { 36 struct btree_node *n = dm_block_data(b); 37 struct node_header *h = &n->header; 38 size_t value_size; 39 __le32 csum_disk; 40 uint32_t flags, nr_entries, max_entries; 41 42 if (dm_block_location(b) != le64_to_cpu(h->blocknr)) { 43 DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu", __func__, 44 le64_to_cpu(h->blocknr), dm_block_location(b)); 45 return -ENOTBLK; 46 } 47 48 csum_disk = cpu_to_le32(dm_bm_checksum(&h->flags, 49 block_size - sizeof(__le32), 50 BTREE_CSUM_XOR)); 51 if (csum_disk != h->csum) { 52 DMERR_LIMIT("%s failed: csum %u != wanted %u", __func__, 53 le32_to_cpu(csum_disk), le32_to_cpu(h->csum)); 54 return -EILSEQ; 55 } 56 57 nr_entries = le32_to_cpu(h->nr_entries); 58 max_entries = le32_to_cpu(h->max_entries); 59 value_size = le32_to_cpu(h->value_size); 60 61 if (sizeof(struct node_header) + 62 (sizeof(__le64) + value_size) * max_entries > block_size) { 63 DMERR_LIMIT("%s failed: max_entries too large", __func__); 64 return -EILSEQ; 65 } 66 67 if (nr_entries > max_entries) { 68 DMERR_LIMIT("%s failed: too many entries", __func__); 69 return -EILSEQ; 70 } 71 72 /* 73 * The node must be either INTERNAL or LEAF. 74 */ 75 flags = le32_to_cpu(h->flags); 76 if (!(flags & INTERNAL_NODE) && !(flags & LEAF_NODE)) { 77 DMERR_LIMIT("%s failed: node is neither INTERNAL or LEAF", __func__); 78 return -EILSEQ; 79 } 80 81 return 0; 82 } 83 84 struct dm_block_validator btree_node_validator = { 85 .name = "btree_node", 86 .prepare_for_write = node_prepare_for_write, 87 .check = node_check 88 }; 89 90 /*----------------------------------------------------------------*/ 91 92 int bn_read_lock(struct dm_btree_info *info, dm_block_t b, 93 struct dm_block **result) 94 { 95 return dm_tm_read_lock(info->tm, b, &btree_node_validator, result); 96 } 97 98 static int bn_shadow(struct dm_btree_info *info, dm_block_t orig, 99 struct dm_btree_value_type *vt, 100 struct dm_block **result) 101 { 102 int r, inc; 103 104 r = dm_tm_shadow_block(info->tm, orig, &btree_node_validator, 105 result, &inc); 106 if (!r && inc) 107 inc_children(info->tm, dm_block_data(*result), vt); 108 109 return r; 110 } 111 112 int new_block(struct dm_btree_info *info, struct dm_block **result) 113 { 114 return dm_tm_new_block(info->tm, &btree_node_validator, result); 115 } 116 117 void unlock_block(struct dm_btree_info *info, struct dm_block *b) 118 { 119 dm_tm_unlock(info->tm, b); 120 } 121 122 /*----------------------------------------------------------------*/ 123 124 void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info) 125 { 126 s->info = info; 127 s->count = 0; 128 s->nodes[0] = NULL; 129 s->nodes[1] = NULL; 130 } 131 132 void exit_ro_spine(struct ro_spine *s) 133 { 134 int i; 135 136 for (i = 0; i < s->count; i++) 137 unlock_block(s->info, s->nodes[i]); 138 } 139 140 int ro_step(struct ro_spine *s, dm_block_t new_child) 141 { 142 int r; 143 144 if (s->count == 2) { 145 unlock_block(s->info, s->nodes[0]); 146 s->nodes[0] = s->nodes[1]; 147 s->count--; 148 } 149 150 r = bn_read_lock(s->info, new_child, s->nodes + s->count); 151 if (!r) 152 s->count++; 153 154 return r; 155 } 156 157 void ro_pop(struct ro_spine *s) 158 { 159 BUG_ON(!s->count); 160 --s->count; 161 unlock_block(s->info, s->nodes[s->count]); 162 } 163 164 struct btree_node *ro_node(struct ro_spine *s) 165 { 166 struct dm_block *block; 167 168 BUG_ON(!s->count); 169 block = s->nodes[s->count - 1]; 170 171 return dm_block_data(block); 172 } 173 174 /*----------------------------------------------------------------*/ 175 176 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info) 177 { 178 s->info = info; 179 s->count = 0; 180 } 181 182 void exit_shadow_spine(struct shadow_spine *s) 183 { 184 int i; 185 186 for (i = 0; i < s->count; i++) 187 unlock_block(s->info, s->nodes[i]); 188 } 189 190 int shadow_step(struct shadow_spine *s, dm_block_t b, 191 struct dm_btree_value_type *vt) 192 { 193 int r; 194 195 if (s->count == 2) { 196 unlock_block(s->info, s->nodes[0]); 197 s->nodes[0] = s->nodes[1]; 198 s->count--; 199 } 200 201 r = bn_shadow(s->info, b, vt, s->nodes + s->count); 202 if (!r) { 203 if (!s->count) 204 s->root = dm_block_location(s->nodes[0]); 205 206 s->count++; 207 } 208 209 return r; 210 } 211 212 struct dm_block *shadow_current(struct shadow_spine *s) 213 { 214 BUG_ON(!s->count); 215 216 return s->nodes[s->count - 1]; 217 } 218 219 struct dm_block *shadow_parent(struct shadow_spine *s) 220 { 221 BUG_ON(s->count != 2); 222 223 return s->count == 2 ? s->nodes[0] : NULL; 224 } 225 226 int shadow_has_parent(struct shadow_spine *s) 227 { 228 return s->count >= 2; 229 } 230 231 dm_block_t shadow_root(struct shadow_spine *s) 232 { 233 return s->root; 234 } 235 236 static void le64_inc(void *context, const void *value_le, unsigned int count) 237 { 238 dm_tm_with_runs(context, value_le, count, dm_tm_inc_range); 239 } 240 241 static void le64_dec(void *context, const void *value_le, unsigned int count) 242 { 243 dm_tm_with_runs(context, value_le, count, dm_tm_dec_range); 244 } 245 246 static int le64_equal(void *context, const void *value1_le, const void *value2_le) 247 { 248 __le64 v1_le, v2_le; 249 250 memcpy(&v1_le, value1_le, sizeof(v1_le)); 251 memcpy(&v2_le, value2_le, sizeof(v2_le)); 252 return v1_le == v2_le; 253 } 254 255 void init_le64_type(struct dm_transaction_manager *tm, 256 struct dm_btree_value_type *vt) 257 { 258 vt->context = tm; 259 vt->size = sizeof(__le64); 260 vt->inc = le64_inc; 261 vt->dec = le64_dec; 262 vt->equal = le64_equal; 263 } 264