Joe Thornber | 6513c29 | 2013-03-01 22:45:51 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2012 Red Hat, Inc. |
| 3 | * |
| 4 | * This file is released under the GPL. |
| 5 | */ |
| 6 | |
| 7 | #include "dm-array.h" |
| 8 | #include "dm-space-map.h" |
| 9 | #include "dm-transaction-manager.h" |
| 10 | |
| 11 | #include <linux/export.h> |
| 12 | #include <linux/device-mapper.h> |
| 13 | |
| 14 | #define DM_MSG_PREFIX "array" |
| 15 | |
| 16 | /*----------------------------------------------------------------*/ |
| 17 | |
| 18 | /* |
| 19 | * The array is implemented as a fully populated btree, which points to |
| 20 | * blocks that contain the packed values. This is more space efficient |
| 21 | * than just using a btree since we don't store 1 key per value. |
| 22 | */ |
| 23 | struct array_block { |
| 24 | __le32 csum; |
| 25 | __le32 max_entries; |
| 26 | __le32 nr_entries; |
| 27 | __le32 value_size; |
| 28 | __le64 blocknr; /* Block this node is supposed to live in. */ |
| 29 | } __packed; |
| 30 | |
| 31 | /*----------------------------------------------------------------*/ |
| 32 | |
| 33 | /* |
| 34 | * Validator methods. As usual we calculate a checksum, and also write the |
| 35 | * block location into the header (paranoia about ssds remapping areas by |
| 36 | * mistake). |
| 37 | */ |
| 38 | #define CSUM_XOR 595846735 |
| 39 | |
| 40 | static void array_block_prepare_for_write(struct dm_block_validator *v, |
| 41 | struct dm_block *b, |
| 42 | size_t size_of_block) |
| 43 | { |
| 44 | struct array_block *bh_le = dm_block_data(b); |
| 45 | |
| 46 | bh_le->blocknr = cpu_to_le64(dm_block_location(b)); |
| 47 | bh_le->csum = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries, |
| 48 | size_of_block - sizeof(__le32), |
| 49 | CSUM_XOR)); |
| 50 | } |
| 51 | |
| 52 | static int array_block_check(struct dm_block_validator *v, |
| 53 | struct dm_block *b, |
| 54 | size_t size_of_block) |
| 55 | { |
| 56 | struct array_block *bh_le = dm_block_data(b); |
| 57 | __le32 csum_disk; |
| 58 | |
| 59 | if (dm_block_location(b) != le64_to_cpu(bh_le->blocknr)) { |
| 60 | DMERR_LIMIT("array_block_check failed: blocknr %llu != wanted %llu", |
| 61 | (unsigned long long) le64_to_cpu(bh_le->blocknr), |
| 62 | (unsigned long long) dm_block_location(b)); |
| 63 | return -ENOTBLK; |
| 64 | } |
| 65 | |
| 66 | csum_disk = cpu_to_le32(dm_bm_checksum(&bh_le->max_entries, |
| 67 | size_of_block - sizeof(__le32), |
| 68 | CSUM_XOR)); |
| 69 | if (csum_disk != bh_le->csum) { |
| 70 | DMERR_LIMIT("array_block_check failed: csum %u != wanted %u", |
| 71 | (unsigned) le32_to_cpu(csum_disk), |
| 72 | (unsigned) le32_to_cpu(bh_le->csum)); |
| 73 | return -EILSEQ; |
| 74 | } |
| 75 | |
| 76 | return 0; |
| 77 | } |
| 78 | |
| 79 | static struct dm_block_validator array_validator = { |
| 80 | .name = "array", |
| 81 | .prepare_for_write = array_block_prepare_for_write, |
| 82 | .check = array_block_check |
| 83 | }; |
| 84 | |
| 85 | /*----------------------------------------------------------------*/ |
| 86 | |
| 87 | /* |
| 88 | * Functions for manipulating the array blocks. |
| 89 | */ |
| 90 | |
| 91 | /* |
| 92 | * Returns a pointer to a value within an array block. |
| 93 | * |
| 94 | * index - The index into _this_ specific block. |
| 95 | */ |
| 96 | static void *element_at(struct dm_array_info *info, struct array_block *ab, |
| 97 | unsigned index) |
| 98 | { |
| 99 | unsigned char *entry = (unsigned char *) (ab + 1); |
| 100 | |
| 101 | entry += index * info->value_type.size; |
| 102 | |
| 103 | return entry; |
| 104 | } |
| 105 | |
| 106 | /* |
| 107 | * Utility function that calls one of the value_type methods on every value |
| 108 | * in an array block. |
| 109 | */ |
| 110 | static void on_entries(struct dm_array_info *info, struct array_block *ab, |
| 111 | void (*fn)(void *, const void *)) |
| 112 | { |
| 113 | unsigned i, nr_entries = le32_to_cpu(ab->nr_entries); |
| 114 | |
| 115 | for (i = 0; i < nr_entries; i++) |
| 116 | fn(info->value_type.context, element_at(info, ab, i)); |
| 117 | } |
| 118 | |
| 119 | /* |
| 120 | * Increment every value in an array block. |
| 121 | */ |
| 122 | static void inc_ablock_entries(struct dm_array_info *info, struct array_block *ab) |
| 123 | { |
| 124 | struct dm_btree_value_type *vt = &info->value_type; |
| 125 | |
| 126 | if (vt->inc) |
| 127 | on_entries(info, ab, vt->inc); |
| 128 | } |
| 129 | |
| 130 | /* |
| 131 | * Decrement every value in an array block. |
| 132 | */ |
| 133 | static void dec_ablock_entries(struct dm_array_info *info, struct array_block *ab) |
| 134 | { |
| 135 | struct dm_btree_value_type *vt = &info->value_type; |
| 136 | |
| 137 | if (vt->dec) |
| 138 | on_entries(info, ab, vt->dec); |
| 139 | } |
| 140 | |
| 141 | /* |
| 142 | * Each array block can hold this many values. |
| 143 | */ |
| 144 | static uint32_t calc_max_entries(size_t value_size, size_t size_of_block) |
| 145 | { |
| 146 | return (size_of_block - sizeof(struct array_block)) / value_size; |
| 147 | } |
| 148 | |
| 149 | /* |
| 150 | * Allocate a new array block. The caller will need to unlock block. |
| 151 | */ |
| 152 | static int alloc_ablock(struct dm_array_info *info, size_t size_of_block, |
| 153 | uint32_t max_entries, |
| 154 | struct dm_block **block, struct array_block **ab) |
| 155 | { |
| 156 | int r; |
| 157 | |
| 158 | r = dm_tm_new_block(info->btree_info.tm, &array_validator, block); |
| 159 | if (r) |
| 160 | return r; |
| 161 | |
| 162 | (*ab) = dm_block_data(*block); |
| 163 | (*ab)->max_entries = cpu_to_le32(max_entries); |
| 164 | (*ab)->nr_entries = cpu_to_le32(0); |
| 165 | (*ab)->value_size = cpu_to_le32(info->value_type.size); |
| 166 | |
| 167 | return 0; |
| 168 | } |
| 169 | |
| 170 | /* |
| 171 | * Pad an array block out with a particular value. Every instance will |
| 172 | * cause an increment of the value_type. new_nr must always be more than |
| 173 | * the current number of entries. |
| 174 | */ |
| 175 | static void fill_ablock(struct dm_array_info *info, struct array_block *ab, |
| 176 | const void *value, unsigned new_nr) |
| 177 | { |
| 178 | unsigned i; |
| 179 | uint32_t nr_entries; |
| 180 | struct dm_btree_value_type *vt = &info->value_type; |
| 181 | |
| 182 | BUG_ON(new_nr > le32_to_cpu(ab->max_entries)); |
| 183 | BUG_ON(new_nr < le32_to_cpu(ab->nr_entries)); |
| 184 | |
| 185 | nr_entries = le32_to_cpu(ab->nr_entries); |
| 186 | for (i = nr_entries; i < new_nr; i++) { |
| 187 | if (vt->inc) |
| 188 | vt->inc(vt->context, value); |
| 189 | memcpy(element_at(info, ab, i), value, vt->size); |
| 190 | } |
| 191 | ab->nr_entries = cpu_to_le32(new_nr); |
| 192 | } |
| 193 | |
| 194 | /* |
| 195 | * Remove some entries from the back of an array block. Every value |
| 196 | * removed will be decremented. new_nr must be <= the current number of |
| 197 | * entries. |
| 198 | */ |
| 199 | static void trim_ablock(struct dm_array_info *info, struct array_block *ab, |
| 200 | unsigned new_nr) |
| 201 | { |
| 202 | unsigned i; |
| 203 | uint32_t nr_entries; |
| 204 | struct dm_btree_value_type *vt = &info->value_type; |
| 205 | |
| 206 | BUG_ON(new_nr > le32_to_cpu(ab->max_entries)); |
| 207 | BUG_ON(new_nr > le32_to_cpu(ab->nr_entries)); |
| 208 | |
| 209 | nr_entries = le32_to_cpu(ab->nr_entries); |
| 210 | for (i = nr_entries; i > new_nr; i--) |
| 211 | if (vt->dec) |
| 212 | vt->dec(vt->context, element_at(info, ab, i - 1)); |
| 213 | ab->nr_entries = cpu_to_le32(new_nr); |
| 214 | } |
| 215 | |
| 216 | /* |
| 217 | * Read locks a block, and coerces it to an array block. The caller must |
| 218 | * unlock 'block' when finished. |
| 219 | */ |
| 220 | static int get_ablock(struct dm_array_info *info, dm_block_t b, |
| 221 | struct dm_block **block, struct array_block **ab) |
| 222 | { |
| 223 | int r; |
| 224 | |
| 225 | r = dm_tm_read_lock(info->btree_info.tm, b, &array_validator, block); |
| 226 | if (r) |
| 227 | return r; |
| 228 | |
| 229 | *ab = dm_block_data(*block); |
| 230 | return 0; |
| 231 | } |
| 232 | |
| 233 | /* |
| 234 | * Unlocks an array block. |
| 235 | */ |
| 236 | static int unlock_ablock(struct dm_array_info *info, struct dm_block *block) |
| 237 | { |
| 238 | return dm_tm_unlock(info->btree_info.tm, block); |
| 239 | } |
| 240 | |
| 241 | /*----------------------------------------------------------------*/ |
| 242 | |
| 243 | /* |
| 244 | * Btree manipulation. |
| 245 | */ |
| 246 | |
| 247 | /* |
| 248 | * Looks up an array block in the btree, and then read locks it. |
| 249 | * |
| 250 | * index is the index of the index of the array_block, (ie. the array index |
| 251 | * / max_entries). |
| 252 | */ |
| 253 | static int lookup_ablock(struct dm_array_info *info, dm_block_t root, |
| 254 | unsigned index, struct dm_block **block, |
| 255 | struct array_block **ab) |
| 256 | { |
| 257 | int r; |
| 258 | uint64_t key = index; |
| 259 | __le64 block_le; |
| 260 | |
| 261 | r = dm_btree_lookup(&info->btree_info, root, &key, &block_le); |
| 262 | if (r) |
| 263 | return r; |
| 264 | |
| 265 | return get_ablock(info, le64_to_cpu(block_le), block, ab); |
| 266 | } |
| 267 | |
| 268 | /* |
| 269 | * Insert an array block into the btree. The block is _not_ unlocked. |
| 270 | */ |
| 271 | static int insert_ablock(struct dm_array_info *info, uint64_t index, |
| 272 | struct dm_block *block, dm_block_t *root) |
| 273 | { |
| 274 | __le64 block_le = cpu_to_le64(dm_block_location(block)); |
| 275 | |
| 276 | __dm_bless_for_disk(block_le); |
| 277 | return dm_btree_insert(&info->btree_info, *root, &index, &block_le, root); |
| 278 | } |
| 279 | |
| 280 | /* |
| 281 | * Looks up an array block in the btree. Then shadows it, and updates the |
| 282 | * btree to point to this new shadow. 'root' is an input/output parameter |
| 283 | * for both the current root block, and the new one. |
| 284 | */ |
| 285 | static int shadow_ablock(struct dm_array_info *info, dm_block_t *root, |
| 286 | unsigned index, struct dm_block **block, |
| 287 | struct array_block **ab) |
| 288 | { |
| 289 | int r, inc; |
| 290 | uint64_t key = index; |
| 291 | dm_block_t b; |
| 292 | __le64 block_le; |
| 293 | |
| 294 | /* |
| 295 | * lookup |
| 296 | */ |
| 297 | r = dm_btree_lookup(&info->btree_info, *root, &key, &block_le); |
| 298 | if (r) |
| 299 | return r; |
| 300 | b = le64_to_cpu(block_le); |
| 301 | |
| 302 | /* |
| 303 | * shadow |
| 304 | */ |
| 305 | r = dm_tm_shadow_block(info->btree_info.tm, b, |
| 306 | &array_validator, block, &inc); |
| 307 | if (r) |
| 308 | return r; |
| 309 | |
| 310 | *ab = dm_block_data(*block); |
| 311 | if (inc) |
| 312 | inc_ablock_entries(info, *ab); |
| 313 | |
| 314 | /* |
| 315 | * Reinsert. |
| 316 | * |
| 317 | * The shadow op will often be a noop. Only insert if it really |
| 318 | * copied data. |
| 319 | */ |
| 320 | if (dm_block_location(*block) != b) |
| 321 | r = insert_ablock(info, index, *block, root); |
| 322 | |
| 323 | return r; |
| 324 | } |
| 325 | |
| 326 | /* |
| 327 | * Allocate an new array block, and fill it with some values. |
| 328 | */ |
| 329 | static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block, |
| 330 | uint32_t max_entries, |
| 331 | unsigned block_index, uint32_t nr, |
| 332 | const void *value, dm_block_t *root) |
| 333 | { |
| 334 | int r; |
| 335 | struct dm_block *block; |
| 336 | struct array_block *ab; |
| 337 | |
| 338 | r = alloc_ablock(info, size_of_block, max_entries, &block, &ab); |
| 339 | if (r) |
| 340 | return r; |
| 341 | |
| 342 | fill_ablock(info, ab, value, nr); |
| 343 | r = insert_ablock(info, block_index, block, root); |
| 344 | unlock_ablock(info, block); |
| 345 | |
| 346 | return r; |
| 347 | } |
| 348 | |
| 349 | static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block, |
| 350 | unsigned begin_block, unsigned end_block, |
| 351 | unsigned max_entries, const void *value, |
| 352 | dm_block_t *root) |
| 353 | { |
| 354 | int r = 0; |
| 355 | |
| 356 | for (; !r && begin_block != end_block; begin_block++) |
| 357 | r = insert_new_ablock(info, size_of_block, max_entries, begin_block, max_entries, value, root); |
| 358 | |
| 359 | return r; |
| 360 | } |
| 361 | |
| 362 | /* |
| 363 | * There are a bunch of functions involved with resizing an array. This |
| 364 | * structure holds information that commonly needed by them. Purely here |
| 365 | * to reduce parameter count. |
| 366 | */ |
| 367 | struct resize { |
| 368 | /* |
| 369 | * Describes the array. |
| 370 | */ |
| 371 | struct dm_array_info *info; |
| 372 | |
| 373 | /* |
| 374 | * The current root of the array. This gets updated. |
| 375 | */ |
| 376 | dm_block_t root; |
| 377 | |
| 378 | /* |
| 379 | * Metadata block size. Used to calculate the nr entries in an |
| 380 | * array block. |
| 381 | */ |
| 382 | size_t size_of_block; |
| 383 | |
| 384 | /* |
| 385 | * Maximum nr entries in an array block. |
| 386 | */ |
| 387 | unsigned max_entries; |
| 388 | |
| 389 | /* |
| 390 | * nr of completely full blocks in the array. |
| 391 | * |
| 392 | * 'old' refers to before the resize, 'new' after. |
| 393 | */ |
| 394 | unsigned old_nr_full_blocks, new_nr_full_blocks; |
| 395 | |
| 396 | /* |
| 397 | * Number of entries in the final block. 0 iff only full blocks in |
| 398 | * the array. |
| 399 | */ |
| 400 | unsigned old_nr_entries_in_last_block, new_nr_entries_in_last_block; |
| 401 | |
| 402 | /* |
| 403 | * The default value used when growing the array. |
| 404 | */ |
| 405 | const void *value; |
| 406 | }; |
| 407 | |
| 408 | /* |
| 409 | * Removes a consecutive set of array blocks from the btree. The values |
| 410 | * in block are decremented as a side effect of the btree remove. |
| 411 | * |
| 412 | * begin_index - the index of the first array block to remove. |
| 413 | * end_index - the one-past-the-end value. ie. this block is not removed. |
| 414 | */ |
| 415 | static int drop_blocks(struct resize *resize, unsigned begin_index, |
| 416 | unsigned end_index) |
| 417 | { |
| 418 | int r; |
| 419 | |
| 420 | while (begin_index != end_index) { |
| 421 | uint64_t key = begin_index++; |
| 422 | r = dm_btree_remove(&resize->info->btree_info, resize->root, |
| 423 | &key, &resize->root); |
| 424 | if (r) |
| 425 | return r; |
| 426 | } |
| 427 | |
| 428 | return 0; |
| 429 | } |
| 430 | |
| 431 | /* |
| 432 | * Calculates how many blocks are needed for the array. |
| 433 | */ |
| 434 | static unsigned total_nr_blocks_needed(unsigned nr_full_blocks, |
| 435 | unsigned nr_entries_in_last_block) |
| 436 | { |
| 437 | return nr_full_blocks + (nr_entries_in_last_block ? 1 : 0); |
| 438 | } |
| 439 | |
| 440 | /* |
| 441 | * Shrink an array. |
| 442 | */ |
| 443 | static int shrink(struct resize *resize) |
| 444 | { |
| 445 | int r; |
| 446 | unsigned begin, end; |
| 447 | struct dm_block *block; |
| 448 | struct array_block *ab; |
| 449 | |
| 450 | /* |
| 451 | * Lose some blocks from the back? |
| 452 | */ |
| 453 | if (resize->new_nr_full_blocks < resize->old_nr_full_blocks) { |
| 454 | begin = total_nr_blocks_needed(resize->new_nr_full_blocks, |
| 455 | resize->new_nr_entries_in_last_block); |
| 456 | end = total_nr_blocks_needed(resize->old_nr_full_blocks, |
| 457 | resize->old_nr_entries_in_last_block); |
| 458 | |
| 459 | r = drop_blocks(resize, begin, end); |
| 460 | if (r) |
| 461 | return r; |
| 462 | } |
| 463 | |
| 464 | /* |
| 465 | * Trim the new tail block |
| 466 | */ |
| 467 | if (resize->new_nr_entries_in_last_block) { |
| 468 | r = shadow_ablock(resize->info, &resize->root, |
| 469 | resize->new_nr_full_blocks, &block, &ab); |
| 470 | if (r) |
| 471 | return r; |
| 472 | |
| 473 | trim_ablock(resize->info, ab, resize->new_nr_entries_in_last_block); |
| 474 | unlock_ablock(resize->info, block); |
| 475 | } |
| 476 | |
| 477 | return 0; |
| 478 | } |
| 479 | |
| 480 | /* |
| 481 | * Grow an array. |
| 482 | */ |
| 483 | static int grow_extend_tail_block(struct resize *resize, uint32_t new_nr_entries) |
| 484 | { |
| 485 | int r; |
| 486 | struct dm_block *block; |
| 487 | struct array_block *ab; |
| 488 | |
| 489 | r = shadow_ablock(resize->info, &resize->root, |
| 490 | resize->old_nr_full_blocks, &block, &ab); |
| 491 | if (r) |
| 492 | return r; |
| 493 | |
| 494 | fill_ablock(resize->info, ab, resize->value, new_nr_entries); |
| 495 | unlock_ablock(resize->info, block); |
| 496 | |
| 497 | return r; |
| 498 | } |
| 499 | |
| 500 | static int grow_add_tail_block(struct resize *resize) |
| 501 | { |
| 502 | return insert_new_ablock(resize->info, resize->size_of_block, |
| 503 | resize->max_entries, |
| 504 | resize->new_nr_full_blocks, |
| 505 | resize->new_nr_entries_in_last_block, |
| 506 | resize->value, &resize->root); |
| 507 | } |
| 508 | |
| 509 | static int grow_needs_more_blocks(struct resize *resize) |
| 510 | { |
| 511 | int r; |
Joe Thornber | 9c1d4de | 2013-10-30 11:19:59 +0000 | [diff] [blame] | 512 | unsigned old_nr_blocks = resize->old_nr_full_blocks; |
Joe Thornber | 6513c29 | 2013-03-01 22:45:51 +0000 | [diff] [blame] | 513 | |
| 514 | if (resize->old_nr_entries_in_last_block > 0) { |
Joe Thornber | 9c1d4de | 2013-10-30 11:19:59 +0000 | [diff] [blame] | 515 | old_nr_blocks++; |
| 516 | |
Joe Thornber | 6513c29 | 2013-03-01 22:45:51 +0000 | [diff] [blame] | 517 | r = grow_extend_tail_block(resize, resize->max_entries); |
| 518 | if (r) |
| 519 | return r; |
| 520 | } |
| 521 | |
| 522 | r = insert_full_ablocks(resize->info, resize->size_of_block, |
Joe Thornber | 9c1d4de | 2013-10-30 11:19:59 +0000 | [diff] [blame] | 523 | old_nr_blocks, |
Joe Thornber | 6513c29 | 2013-03-01 22:45:51 +0000 | [diff] [blame] | 524 | resize->new_nr_full_blocks, |
| 525 | resize->max_entries, resize->value, |
| 526 | &resize->root); |
| 527 | if (r) |
| 528 | return r; |
| 529 | |
| 530 | if (resize->new_nr_entries_in_last_block) |
| 531 | r = grow_add_tail_block(resize); |
| 532 | |
| 533 | return r; |
| 534 | } |
| 535 | |
| 536 | static int grow(struct resize *resize) |
| 537 | { |
| 538 | if (resize->new_nr_full_blocks > resize->old_nr_full_blocks) |
| 539 | return grow_needs_more_blocks(resize); |
| 540 | |
| 541 | else if (resize->old_nr_entries_in_last_block) |
| 542 | return grow_extend_tail_block(resize, resize->new_nr_entries_in_last_block); |
| 543 | |
| 544 | else |
| 545 | return grow_add_tail_block(resize); |
| 546 | } |
| 547 | |
| 548 | /*----------------------------------------------------------------*/ |
| 549 | |
| 550 | /* |
| 551 | * These are the value_type functions for the btree elements, which point |
| 552 | * to array blocks. |
| 553 | */ |
| 554 | static void block_inc(void *context, const void *value) |
| 555 | { |
| 556 | __le64 block_le; |
| 557 | struct dm_array_info *info = context; |
| 558 | |
| 559 | memcpy(&block_le, value, sizeof(block_le)); |
| 560 | dm_tm_inc(info->btree_info.tm, le64_to_cpu(block_le)); |
| 561 | } |
| 562 | |
| 563 | static void block_dec(void *context, const void *value) |
| 564 | { |
| 565 | int r; |
| 566 | uint64_t b; |
| 567 | __le64 block_le; |
| 568 | uint32_t ref_count; |
| 569 | struct dm_block *block; |
| 570 | struct array_block *ab; |
| 571 | struct dm_array_info *info = context; |
| 572 | |
| 573 | memcpy(&block_le, value, sizeof(block_le)); |
| 574 | b = le64_to_cpu(block_le); |
| 575 | |
| 576 | r = dm_tm_ref(info->btree_info.tm, b, &ref_count); |
| 577 | if (r) { |
| 578 | DMERR_LIMIT("couldn't get reference count for block %llu", |
| 579 | (unsigned long long) b); |
| 580 | return; |
| 581 | } |
| 582 | |
| 583 | if (ref_count == 1) { |
| 584 | /* |
| 585 | * We're about to drop the last reference to this ablock. |
| 586 | * So we need to decrement the ref count of the contents. |
| 587 | */ |
| 588 | r = get_ablock(info, b, &block, &ab); |
| 589 | if (r) { |
| 590 | DMERR_LIMIT("couldn't get array block %llu", |
| 591 | (unsigned long long) b); |
| 592 | return; |
| 593 | } |
| 594 | |
| 595 | dec_ablock_entries(info, ab); |
| 596 | unlock_ablock(info, block); |
| 597 | } |
| 598 | |
| 599 | dm_tm_dec(info->btree_info.tm, b); |
| 600 | } |
| 601 | |
| 602 | static int block_equal(void *context, const void *value1, const void *value2) |
| 603 | { |
| 604 | return !memcmp(value1, value2, sizeof(__le64)); |
| 605 | } |
| 606 | |
| 607 | /*----------------------------------------------------------------*/ |
| 608 | |
| 609 | void dm_array_info_init(struct dm_array_info *info, |
| 610 | struct dm_transaction_manager *tm, |
| 611 | struct dm_btree_value_type *vt) |
| 612 | { |
| 613 | struct dm_btree_value_type *bvt = &info->btree_info.value_type; |
| 614 | |
| 615 | memcpy(&info->value_type, vt, sizeof(info->value_type)); |
| 616 | info->btree_info.tm = tm; |
| 617 | info->btree_info.levels = 1; |
| 618 | |
| 619 | bvt->context = info; |
| 620 | bvt->size = sizeof(__le64); |
| 621 | bvt->inc = block_inc; |
| 622 | bvt->dec = block_dec; |
| 623 | bvt->equal = block_equal; |
| 624 | } |
| 625 | EXPORT_SYMBOL_GPL(dm_array_info_init); |
| 626 | |
| 627 | int dm_array_empty(struct dm_array_info *info, dm_block_t *root) |
| 628 | { |
| 629 | return dm_btree_empty(&info->btree_info, root); |
| 630 | } |
| 631 | EXPORT_SYMBOL_GPL(dm_array_empty); |
| 632 | |
| 633 | static int array_resize(struct dm_array_info *info, dm_block_t root, |
| 634 | uint32_t old_size, uint32_t new_size, |
| 635 | const void *value, dm_block_t *new_root) |
| 636 | { |
| 637 | int r; |
| 638 | struct resize resize; |
| 639 | |
| 640 | if (old_size == new_size) |
| 641 | return 0; |
| 642 | |
| 643 | resize.info = info; |
| 644 | resize.root = root; |
| 645 | resize.size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm)); |
| 646 | resize.max_entries = calc_max_entries(info->value_type.size, |
| 647 | resize.size_of_block); |
| 648 | |
| 649 | resize.old_nr_full_blocks = old_size / resize.max_entries; |
| 650 | resize.old_nr_entries_in_last_block = old_size % resize.max_entries; |
| 651 | resize.new_nr_full_blocks = new_size / resize.max_entries; |
| 652 | resize.new_nr_entries_in_last_block = new_size % resize.max_entries; |
| 653 | resize.value = value; |
| 654 | |
| 655 | r = ((new_size > old_size) ? grow : shrink)(&resize); |
| 656 | if (r) |
| 657 | return r; |
| 658 | |
| 659 | *new_root = resize.root; |
| 660 | return 0; |
| 661 | } |
| 662 | |
| 663 | int dm_array_resize(struct dm_array_info *info, dm_block_t root, |
| 664 | uint32_t old_size, uint32_t new_size, |
| 665 | const void *value, dm_block_t *new_root) |
| 666 | __dm_written_to_disk(value) |
| 667 | { |
| 668 | int r = array_resize(info, root, old_size, new_size, value, new_root); |
| 669 | __dm_unbless_for_disk(value); |
| 670 | return r; |
| 671 | } |
| 672 | EXPORT_SYMBOL_GPL(dm_array_resize); |
| 673 | |
| 674 | int dm_array_del(struct dm_array_info *info, dm_block_t root) |
| 675 | { |
| 676 | return dm_btree_del(&info->btree_info, root); |
| 677 | } |
| 678 | EXPORT_SYMBOL_GPL(dm_array_del); |
| 679 | |
| 680 | int dm_array_get_value(struct dm_array_info *info, dm_block_t root, |
| 681 | uint32_t index, void *value_le) |
| 682 | { |
| 683 | int r; |
| 684 | struct dm_block *block; |
| 685 | struct array_block *ab; |
| 686 | size_t size_of_block; |
| 687 | unsigned entry, max_entries; |
| 688 | |
| 689 | size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm)); |
| 690 | max_entries = calc_max_entries(info->value_type.size, size_of_block); |
| 691 | |
| 692 | r = lookup_ablock(info, root, index / max_entries, &block, &ab); |
| 693 | if (r) |
| 694 | return r; |
| 695 | |
| 696 | entry = index % max_entries; |
| 697 | if (entry >= le32_to_cpu(ab->nr_entries)) |
| 698 | r = -ENODATA; |
| 699 | else |
| 700 | memcpy(value_le, element_at(info, ab, entry), |
| 701 | info->value_type.size); |
| 702 | |
| 703 | unlock_ablock(info, block); |
| 704 | return r; |
| 705 | } |
| 706 | EXPORT_SYMBOL_GPL(dm_array_get_value); |
| 707 | |
| 708 | static int array_set_value(struct dm_array_info *info, dm_block_t root, |
| 709 | uint32_t index, const void *value, dm_block_t *new_root) |
| 710 | { |
| 711 | int r; |
| 712 | struct dm_block *block; |
| 713 | struct array_block *ab; |
| 714 | size_t size_of_block; |
| 715 | unsigned max_entries; |
| 716 | unsigned entry; |
| 717 | void *old_value; |
| 718 | struct dm_btree_value_type *vt = &info->value_type; |
| 719 | |
| 720 | size_of_block = dm_bm_block_size(dm_tm_get_bm(info->btree_info.tm)); |
| 721 | max_entries = calc_max_entries(info->value_type.size, size_of_block); |
| 722 | |
| 723 | r = shadow_ablock(info, &root, index / max_entries, &block, &ab); |
| 724 | if (r) |
| 725 | return r; |
| 726 | *new_root = root; |
| 727 | |
| 728 | entry = index % max_entries; |
| 729 | if (entry >= le32_to_cpu(ab->nr_entries)) { |
| 730 | r = -ENODATA; |
| 731 | goto out; |
| 732 | } |
| 733 | |
| 734 | old_value = element_at(info, ab, entry); |
| 735 | if (vt->dec && |
| 736 | (!vt->equal || !vt->equal(vt->context, old_value, value))) { |
| 737 | vt->dec(vt->context, old_value); |
| 738 | if (vt->inc) |
| 739 | vt->inc(vt->context, value); |
| 740 | } |
| 741 | |
| 742 | memcpy(old_value, value, info->value_type.size); |
| 743 | |
| 744 | out: |
| 745 | unlock_ablock(info, block); |
| 746 | return r; |
| 747 | } |
| 748 | |
| 749 | int dm_array_set_value(struct dm_array_info *info, dm_block_t root, |
| 750 | uint32_t index, const void *value, dm_block_t *new_root) |
| 751 | __dm_written_to_disk(value) |
| 752 | { |
| 753 | int r; |
| 754 | |
| 755 | r = array_set_value(info, root, index, value, new_root); |
| 756 | __dm_unbless_for_disk(value); |
| 757 | return r; |
| 758 | } |
| 759 | EXPORT_SYMBOL_GPL(dm_array_set_value); |
| 760 | |
| 761 | struct walk_info { |
| 762 | struct dm_array_info *info; |
| 763 | int (*fn)(void *context, uint64_t key, void *leaf); |
| 764 | void *context; |
| 765 | }; |
| 766 | |
| 767 | static int walk_ablock(void *context, uint64_t *keys, void *leaf) |
| 768 | { |
| 769 | struct walk_info *wi = context; |
| 770 | |
| 771 | int r; |
| 772 | unsigned i; |
| 773 | __le64 block_le; |
| 774 | unsigned nr_entries, max_entries; |
| 775 | struct dm_block *block; |
| 776 | struct array_block *ab; |
| 777 | |
| 778 | memcpy(&block_le, leaf, sizeof(block_le)); |
| 779 | r = get_ablock(wi->info, le64_to_cpu(block_le), &block, &ab); |
| 780 | if (r) |
| 781 | return r; |
| 782 | |
| 783 | max_entries = le32_to_cpu(ab->max_entries); |
| 784 | nr_entries = le32_to_cpu(ab->nr_entries); |
| 785 | for (i = 0; i < nr_entries; i++) { |
| 786 | r = wi->fn(wi->context, keys[0] * max_entries + i, |
| 787 | element_at(wi->info, ab, i)); |
| 788 | |
| 789 | if (r) |
| 790 | break; |
| 791 | } |
| 792 | |
| 793 | unlock_ablock(wi->info, block); |
| 794 | return r; |
| 795 | } |
| 796 | |
| 797 | int dm_array_walk(struct dm_array_info *info, dm_block_t root, |
| 798 | int (*fn)(void *, uint64_t key, void *leaf), |
| 799 | void *context) |
| 800 | { |
| 801 | struct walk_info wi; |
| 802 | |
| 803 | wi.info = info; |
| 804 | wi.fn = fn; |
| 805 | wi.context = context; |
| 806 | |
| 807 | return dm_btree_walk(&info->btree_info, root, walk_ablock, &wi); |
| 808 | } |
| 809 | EXPORT_SYMBOL_GPL(dm_array_walk); |
| 810 | |
| 811 | /*----------------------------------------------------------------*/ |