| 1 | |
| 2 | |
| 3 | * Copyright (C) 2011 Red Hat, Inc.
|
| 4 | *
|
| 5 | * This file is released under the GPL.
|
| 6 |
|
| 7 |
|
| 8 | #include "dm-space-map-common.h"
|
| 9 | #include "dm-transaction-manager.h"
|
| 10 | #include "dm-btree-internal.h"
|
| 11 | #include "dm-persistent-data-internal.h"
|
| 12 |
|
| 13 | #include <linux/bitops.h>
|
| 14 | #include <linux/device-mapper.h>
|
| 15 |
|
| 16 | #define DM_MSG_PREFIX "space map common"
|
| 17 |
|
| 18 |
|
| 19 |
|
| 20 | |
| 21 | * Index validator.
|
| 22 |
|
| 23 | #define INDEX_CSUM_XOR 160478
|
| 24 |
|
| 25 | static void index_prepare_for_write(const struct dm_block_validator *v,
|
| 26 | struct dm_block *b,
|
| 27 | size_t block_size)
|
| 28 | {
|
| 29 | struct disk_metadata_index *mi_le = dm_block_data(b);
|
| 30 |
|
| 31 | mi_le->blocknr = cpu_to_le64(dm_block_location(b));
|
| 32 | mi_le->csum = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
|
| 33 | block_size - sizeof(__le32),
|
| 34 | INDEX_CSUM_XOR));
|
| 35 | }
|
| 36 |
|
| 37 | static int index_check(const struct dm_block_validator *v,
|
| 38 | struct dm_block *b,
|
| 39 | size_t block_size)
|
| 40 | {
|
| 41 | struct disk_metadata_index *mi_le = dm_block_data(b);
|
| 42 | __le32 csum_disk;
|
| 43 |
|
| 44 | if (dm_block_location(b) != le64_to_cpu(mi_le->blocknr)) {
|
| 45 | DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu", __func__,
|
| 46 | le64_to_cpu(mi_le->blocknr), dm_block_location(b));
|
| 47 | return -ENOTBLK;
|
| 48 | }
|
| 49 |
|
| 50 | csum_disk = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
|
| 51 | block_size - sizeof(__le32),
|
| 52 | INDEX_CSUM_XOR));
|
| 53 | if (csum_disk != mi_le->csum) {
|
| 54 | DMERR_LIMIT("%s failed: csum %u != wanted %u", __func__,
|
| 55 | le32_to_cpu(csum_disk), le32_to_cpu(mi_le->csum));
|
| 56 | return -EILSEQ;
|
| 57 | }
|
| 58 |
|
| 59 | return 0;
|
| 60 | }
|
| 61 |
|
| 62 | static const struct dm_block_validator index_validator = {
|
| 63 | .name = "index",
|
| 64 | .prepare_for_write = index_prepare_for_write,
|
| 65 | .check = index_check
|
| 66 | };
|
| 67 |
|
| 68 |
|
| 69 |
|
| 70 | |
| 71 | * Bitmap validator
|
| 72 |
|
| 73 | #define BITMAP_CSUM_XOR 240779
|
| 74 |
|
| 75 | static void dm_bitmap_prepare_for_write(const struct dm_block_validator *v,
|
| 76 | struct dm_block *b,
|
| 77 | size_t block_size)
|
| 78 | {
|
| 79 | struct disk_bitmap_header *disk_header = dm_block_data(b);
|
| 80 |
|
| 81 | disk_header->blocknr = cpu_to_le64(dm_block_location(b));
|
| 82 | disk_header->csum = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
|
| 83 | block_size - sizeof(__le32),
|
| 84 | BITMAP_CSUM_XOR));
|
| 85 | }
|
| 86 |
|
| 87 | static int dm_bitmap_check(const struct dm_block_validator *v,
|
| 88 | struct dm_block *b,
|
| 89 | size_t block_size)
|
| 90 | {
|
| 91 | struct disk_bitmap_header *disk_header = dm_block_data(b);
|
| 92 | __le32 csum_disk;
|
| 93 |
|
| 94 | if (dm_block_location(b) != le64_to_cpu(disk_header->blocknr)) {
|
| 95 | DMERR_LIMIT("bitmap check failed: blocknr %llu != wanted %llu",
|
| 96 | le64_to_cpu(disk_header->blocknr), dm_block_location(b));
|
| 97 | return -ENOTBLK;
|
| 98 | }
|
| 99 |
|
| 100 | csum_disk = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
|
| 101 | block_size - sizeof(__le32),
|
| 102 | BITMAP_CSUM_XOR));
|
| 103 | if (csum_disk != disk_header->csum) {
|
| 104 | DMERR_LIMIT("bitmap check failed: csum %u != wanted %u",
|
| 105 | le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum));
|
| 106 | return -EILSEQ;
|
| 107 | }
|
| 108 |
|
| 109 | return 0;
|
| 110 | }
|
| 111 |
|
| 112 | static const struct dm_block_validator dm_sm_bitmap_validator = {
|
| 113 | .name = "sm_bitmap",
|
| 114 | .prepare_for_write = dm_bitmap_prepare_for_write,
|
| 115 | .check = dm_bitmap_check,
|
| 116 | };
|
| 117 |
|
| 118 |
|
| 119 |
|
| 120 | #define ENTRIES_PER_WORD 32
|
| 121 | #define ENTRIES_SHIFT 5
|
| 122 |
|
| 123 | static void *dm_bitmap_data(struct dm_block *b)
|
| 124 | {
|
| 125 | return dm_block_data(b) + sizeof(struct disk_bitmap_header);
|
| 126 | }
|
| 127 |
|
| 128 | #define WORD_MASK_HIGH 0xAAAAAAAAAAAAAAAAULL
|
| 129 |
|
| 130 | static unsigned int dm_bitmap_word_used(void *addr, unsigned int b)
|
| 131 | {
|
| 132 | __le64 *words_le = addr;
|
| 133 | __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
|
| 134 |
|
| 135 | uint64_t bits = le64_to_cpu(*w_le);
|
| 136 | uint64_t mask = (bits + WORD_MASK_HIGH + 1) & WORD_MASK_HIGH;
|
| 137 |
|
| 138 | return !(~bits & mask);
|
| 139 | }
|
| 140 |
|
| 141 | static unsigned int sm_lookup_bitmap(void *addr, unsigned int b)
|
| 142 | {
|
| 143 | __le64 *words_le = addr;
|
| 144 | __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
|
| 145 | unsigned int hi, lo;
|
| 146 |
|
| 147 | b = (b & (ENTRIES_PER_WORD - 1)) << 1;
|
| 148 | hi = !!test_bit_le(b, (void *) w_le);
|
| 149 | lo = !!test_bit_le(b + 1, (void *) w_le);
|
| 150 | return (hi << 1) | lo;
|
| 151 | }
|
| 152 |
|
| 153 | static void sm_set_bitmap(void *addr, unsigned int b, unsigned int val)
|
| 154 | {
|
| 155 | __le64 *words_le = addr;
|
| 156 | __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
|
| 157 |
|
| 158 | b = (b & (ENTRIES_PER_WORD - 1)) << 1;
|
| 159 |
|
| 160 | if (val & 2)
|
| 161 | __set_bit_le(b, (void *) w_le);
|
| 162 | else
|
| 163 | __clear_bit_le(b, (void *) w_le);
|
| 164 |
|
| 165 | if (val & 1)
|
| 166 | __set_bit_le(b + 1, (void *) w_le);
|
| 167 | else
|
| 168 | __clear_bit_le(b + 1, (void *) w_le);
|
| 169 | }
|
| 170 |
|
| 171 | static int sm_find_free(void *addr, unsigned int begin, unsigned int end,
|
| 172 | unsigned int *result)
|
| 173 | {
|
| 174 | while (begin < end) {
|
| 175 | if (!(begin & (ENTRIES_PER_WORD - 1)) &&
|
| 176 | dm_bitmap_word_used(addr, begin)) {
|
| 177 | begin += ENTRIES_PER_WORD;
|
| 178 | continue;
|
| 179 | }
|
| 180 |
|
| 181 | if (!sm_lookup_bitmap(addr, begin)) {
|
| 182 | *result = begin;
|
| 183 | return 0;
|
| 184 | }
|
| 185 |
|
| 186 | begin++;
|
| 187 | }
|
| 188 |
|
| 189 | return -ENOSPC;
|
| 190 | }
|
| 191 |
|
| 192 |
|
| 193 |
|
| 194 | static int sm_ll_init(struct ll_disk *ll, struct dm_transaction_manager *tm)
|
| 195 | {
|
| 196 | memset(ll, 0, sizeof(struct ll_disk));
|
| 197 |
|
| 198 | ll->tm = tm;
|
| 199 |
|
| 200 | ll->bitmap_info.tm = tm;
|
| 201 | ll->bitmap_info.levels = 1;
|
| 202 |
|
| 203 | |
| 204 | * Because the new bitmap blocks are created via a shadow
|
| 205 | * operation, the old entry has already had its reference count
|
| 206 | * decremented and we don't need the btree to do any bookkeeping.
|
| 207 |
|
| 208 | ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry);
|
| 209 | ll->bitmap_info.value_type.inc = NULL;
|
| 210 | ll->bitmap_info.value_type.dec = NULL;
|
| 211 | ll->bitmap_info.value_type.equal = NULL;
|
| 212 |
|
| 213 | ll->ref_count_info.tm = tm;
|
| 214 | ll->ref_count_info.levels = 1;
|
| 215 | ll->ref_count_info.value_type.size = sizeof(uint32_t);
|
| 216 | ll->ref_count_info.value_type.inc = NULL;
|
| 217 | ll->ref_count_info.value_type.dec = NULL;
|
| 218 | ll->ref_count_info.value_type.equal = NULL;
|
| 219 |
|
| 220 | ll->block_size = dm_bm_block_size(dm_tm_get_bm(tm));
|
| 221 |
|
| 222 | if (ll->block_size > (1 << 30)) {
|
| 223 | DMERR("block size too big to hold bitmaps");
|
| 224 | return -EINVAL;
|
| 225 | }
|
| 226 |
|
| 227 | ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) *
|
| 228 | ENTRIES_PER_BYTE;
|
| 229 | ll->nr_blocks = 0;
|
| 230 | ll->bitmap_root = 0;
|
| 231 | ll->ref_count_root = 0;
|
| 232 | ll->bitmap_index_changed = false;
|
| 233 |
|
| 234 | return 0;
|
| 235 | }
|
| 236 |
|
| 237 | int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks)
|
| 238 | {
|
| 239 | int r;
|
| 240 | dm_block_t i, nr_blocks, nr_indexes;
|
| 241 | unsigned int old_blocks, blocks;
|
| 242 |
|
| 243 | nr_blocks = ll->nr_blocks + extra_blocks;
|
| 244 | old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block);
|
| 245 | blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block);
|
| 246 |
|
| 247 | nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block);
|
| 248 | if (nr_indexes > ll->max_entries(ll)) {
|
| 249 | DMERR("space map too large");
|
| 250 | return -EINVAL;
|
| 251 | }
|
| 252 |
|
| 253 | |
| 254 | * We need to set this before the dm_tm_new_block() call below.
|
| 255 |
|
| 256 | ll->nr_blocks = nr_blocks;
|
| 257 | for (i = old_blocks; i < blocks; i++) {
|
| 258 | struct dm_block *b;
|
| 259 | struct disk_index_entry idx;
|
| 260 |
|
| 261 | r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b);
|
| 262 | if (r < 0)
|
| 263 | return r;
|
| 264 |
|
| 265 | idx.blocknr = cpu_to_le64(dm_block_location(b));
|
| 266 |
|
| 267 | dm_tm_unlock(ll->tm, b);
|
| 268 |
|
| 269 | idx.nr_free = cpu_to_le32(ll->entries_per_block);
|
| 270 | idx.none_free_before = 0;
|
| 271 |
|
| 272 | r = ll->save_ie(ll, i, &idx);
|
| 273 | if (r < 0)
|
| 274 | return r;
|
| 275 | }
|
| 276 |
|
| 277 | return 0;
|
| 278 | }
|
| 279 |
|
| 280 | int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result)
|
| 281 | {
|
| 282 | int r;
|
| 283 | dm_block_t index = b;
|
| 284 | struct disk_index_entry ie_disk;
|
| 285 | struct dm_block *blk;
|
| 286 |
|
| 287 | if (b >= ll->nr_blocks) {
|
| 288 | DMERR_LIMIT("metadata block out of bounds");
|
| 289 | return -EINVAL;
|
| 290 | }
|
| 291 |
|
| 292 | b = do_div(index, ll->entries_per_block);
|
| 293 | r = ll->load_ie(ll, index, &ie_disk);
|
| 294 | if (r < 0)
|
| 295 | return r;
|
| 296 |
|
| 297 | r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
|
| 298 | &dm_sm_bitmap_validator, &blk);
|
| 299 | if (r < 0)
|
| 300 | return r;
|
| 301 |
|
| 302 | *result = sm_lookup_bitmap(dm_bitmap_data(blk), b);
|
| 303 |
|
| 304 | dm_tm_unlock(ll->tm, blk);
|
| 305 |
|
| 306 | return 0;
|
| 307 | }
|
| 308 |
|
| 309 | static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b,
|
| 310 | uint32_t *result)
|
| 311 | {
|
| 312 | __le32 le_rc;
|
| 313 | int r;
|
| 314 |
|
| 315 | r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc);
|
| 316 | if (r < 0)
|
| 317 | return r;
|
| 318 |
|
| 319 | *result = le32_to_cpu(le_rc);
|
| 320 |
|
| 321 | return r;
|
| 322 | }
|
| 323 |
|
| 324 | int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result)
|
| 325 | {
|
| 326 | int r = sm_ll_lookup_bitmap(ll, b, result);
|
| 327 |
|
| 328 | if (r)
|
| 329 | return r;
|
| 330 |
|
| 331 | if (*result != 3)
|
| 332 | return r;
|
| 333 |
|
| 334 | return sm_ll_lookup_big_ref_count(ll, b, result);
|
| 335 | }
|
| 336 |
|
| 337 | int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin,
|
| 338 | dm_block_t end, dm_block_t *result)
|
| 339 | {
|
| 340 | int r;
|
| 341 | struct disk_index_entry ie_disk;
|
| 342 | dm_block_t i, index_begin = begin;
|
| 343 | dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block);
|
| 344 |
|
| 345 | |
| 346 | * FIXME: Use shifts
|
| 347 |
|
| 348 | begin = do_div(index_begin, ll->entries_per_block);
|
| 349 | end = do_div(end, ll->entries_per_block);
|
| 350 | if (end == 0)
|
| 351 | end = ll->entries_per_block;
|
| 352 |
|
| 353 | for (i = index_begin; i < index_end; i++, begin = 0) {
|
| 354 | struct dm_block *blk;
|
| 355 | unsigned int position;
|
| 356 | uint32_t bit_end;
|
| 357 |
|
| 358 | r = ll->load_ie(ll, i, &ie_disk);
|
| 359 | if (r < 0)
|
| 360 | return r;
|
| 361 |
|
| 362 | if (le32_to_cpu(ie_disk.nr_free) == 0)
|
| 363 | continue;
|
| 364 |
|
| 365 | r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
|
| 366 | &dm_sm_bitmap_validator, &blk);
|
| 367 | if (r < 0)
|
| 368 | return r;
|
| 369 |
|
| 370 | bit_end = (i == index_end - 1) ? end : ll->entries_per_block;
|
| 371 |
|
| 372 | r = sm_find_free(dm_bitmap_data(blk),
|
| 373 | max_t(unsigned int, begin, le32_to_cpu(ie_disk.none_free_before)),
|
| 374 | bit_end, &position);
|
| 375 | if (r == -ENOSPC) {
|
| 376 | |
| 377 | * This might happen because we started searching
|
| 378 | * part way through the bitmap.
|
| 379 |
|
| 380 | dm_tm_unlock(ll->tm, blk);
|
| 381 | continue;
|
| 382 | }
|
| 383 |
|
| 384 | dm_tm_unlock(ll->tm, blk);
|
| 385 |
|
| 386 | *result = i * ll->entries_per_block + (dm_block_t) position;
|
| 387 | return 0;
|
| 388 | }
|
| 389 |
|
| 390 | return -ENOSPC;
|
| 391 | }
|
| 392 |
|
| 393 | int sm_ll_find_common_free_block(struct ll_disk *old_ll, struct ll_disk *new_ll,
|
| 394 | dm_block_t begin, dm_block_t end, dm_block_t *b)
|
| 395 | {
|
| 396 | int r;
|
| 397 | uint32_t count;
|
| 398 |
|
| 399 | do {
|
| 400 | r = sm_ll_find_free_block(new_ll, begin, new_ll->nr_blocks, b);
|
| 401 | if (r)
|
| 402 | break;
|
| 403 |
|
| 404 |
|
| 405 | if (*b >= old_ll->nr_blocks)
|
| 406 | count = 0;
|
| 407 | else {
|
| 408 | r = sm_ll_lookup(old_ll, *b, &count);
|
| 409 | if (r)
|
| 410 | break;
|
| 411 |
|
| 412 | if (count)
|
| 413 | begin = *b + 1;
|
| 414 | }
|
| 415 | } while (count);
|
| 416 |
|
| 417 | return r;
|
| 418 | }
|
| 419 |
|
| 420 |
|
| 421 |
|
| 422 | int sm_ll_insert(struct ll_disk *ll, dm_block_t b,
|
| 423 | uint32_t ref_count, int32_t *nr_allocations)
|
| 424 | {
|
| 425 | int r;
|
| 426 | uint32_t bit, old;
|
| 427 | struct dm_block *nb;
|
| 428 | dm_block_t index = b;
|
| 429 | struct disk_index_entry ie_disk;
|
| 430 | void *bm_le;
|
| 431 | int inc;
|
| 432 |
|
| 433 | bit = do_div(index, ll->entries_per_block);
|
| 434 | r = ll->load_ie(ll, index, &ie_disk);
|
| 435 | if (r < 0)
|
| 436 | return r;
|
| 437 |
|
| 438 | r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr),
|
| 439 | &dm_sm_bitmap_validator, &nb, &inc);
|
| 440 | if (r < 0) {
|
| 441 | DMERR("dm_tm_shadow_block() failed");
|
| 442 | return r;
|
| 443 | }
|
| 444 | ie_disk.blocknr = cpu_to_le64(dm_block_location(nb));
|
| 445 | bm_le = dm_bitmap_data(nb);
|
| 446 |
|
| 447 | old = sm_lookup_bitmap(bm_le, bit);
|
| 448 | if (old > 2) {
|
| 449 | r = sm_ll_lookup_big_ref_count(ll, b, &old);
|
| 450 | if (r < 0) {
|
| 451 | dm_tm_unlock(ll->tm, nb);
|
| 452 | return r;
|
| 453 | }
|
| 454 | }
|
| 455 |
|
| 456 | if (r) {
|
| 457 | dm_tm_unlock(ll->tm, nb);
|
| 458 | return r;
|
| 459 | }
|
| 460 |
|
| 461 | if (ref_count <= 2) {
|
| 462 | sm_set_bitmap(bm_le, bit, ref_count);
|
| 463 | dm_tm_unlock(ll->tm, nb);
|
| 464 |
|
| 465 | if (old > 2) {
|
| 466 | r = dm_btree_remove(&ll->ref_count_info,
|
| 467 | ll->ref_count_root,
|
| 468 | &b, &ll->ref_count_root);
|
| 469 | if (r)
|
| 470 | return r;
|
| 471 | }
|
| 472 |
|
| 473 | } else {
|
| 474 | __le32 le_rc = cpu_to_le32(ref_count);
|
| 475 |
|
| 476 | sm_set_bitmap(bm_le, bit, 3);
|
| 477 | dm_tm_unlock(ll->tm, nb);
|
| 478 |
|
| 479 | __dm_bless_for_disk(&le_rc);
|
| 480 | r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,
|
| 481 | &b, &le_rc, &ll->ref_count_root);
|
| 482 | if (r < 0) {
|
| 483 | DMERR("ref count insert failed");
|
| 484 | return r;
|
| 485 | }
|
| 486 | }
|
| 487 |
|
| 488 | if (ref_count && !old) {
|
| 489 | *nr_allocations = 1;
|
| 490 | ll->nr_allocated++;
|
| 491 | le32_add_cpu(&ie_disk.nr_free, -1);
|
| 492 | if (le32_to_cpu(ie_disk.none_free_before) == bit)
|
| 493 | ie_disk.none_free_before = cpu_to_le32(bit + 1);
|
| 494 |
|
| 495 | } else if (old && !ref_count) {
|
| 496 | *nr_allocations = -1;
|
| 497 | ll->nr_allocated--;
|
| 498 | le32_add_cpu(&ie_disk.nr_free, 1);
|
| 499 | ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit));
|
| 500 | } else
|
| 501 | *nr_allocations = 0;
|
| 502 |
|
| 503 | return ll->save_ie(ll, index, &ie_disk);
|
| 504 | }
|
| 505 |
|
| 506 |
|
| 507 |
|
| 508 | |
| 509 | * Holds useful intermediate results for the range based inc and dec
|
| 510 | * operations.
|
| 511 |
|
| 512 | struct inc_context {
|
| 513 | struct disk_index_entry ie_disk;
|
| 514 | struct dm_block *bitmap_block;
|
| 515 | void *bitmap;
|
| 516 |
|
| 517 | struct dm_block *overflow_leaf;
|
| 518 | };
|
| 519 |
|
| 520 | static inline void init_inc_context(struct inc_context *ic)
|
| 521 | {
|
| 522 | ic->bitmap_block = NULL;
|
| 523 | ic->bitmap = NULL;
|
| 524 | ic->overflow_leaf = NULL;
|
| 525 | }
|
| 526 |
|
| 527 | static inline void exit_inc_context(struct ll_disk *ll, struct inc_context *ic)
|
| 528 | {
|
| 529 | if (ic->bitmap_block)
|
| 530 | dm_tm_unlock(ll->tm, ic->bitmap_block);
|
| 531 | if (ic->overflow_leaf)
|
| 532 | dm_tm_unlock(ll->tm, ic->overflow_leaf);
|
| 533 | }
|
| 534 |
|
| 535 | static inline void reset_inc_context(struct ll_disk *ll, struct inc_context *ic)
|
| 536 | {
|
| 537 | exit_inc_context(ll, ic);
|
| 538 | init_inc_context(ic);
|
| 539 | }
|
| 540 |
|
| 541 | |
| 542 | * Confirms a btree node contains a particular key at an index.
|
| 543 |
|
| 544 | static bool contains_key(struct btree_node *n, uint64_t key, int index)
|
| 545 | {
|
| 546 | return index >= 0 &&
|
| 547 | index < le32_to_cpu(n->header.nr_entries) &&
|
| 548 | le64_to_cpu(n->keys[index]) == key;
|
| 549 | }
|
| 550 |
|
| 551 | static int __sm_ll_inc_overflow(struct ll_disk *ll, dm_block_t b, struct inc_context *ic)
|
| 552 | {
|
| 553 | int r;
|
| 554 | int index;
|
| 555 | struct btree_node *n;
|
| 556 | __le32 *v_ptr;
|
| 557 | uint32_t rc;
|
| 558 |
|
| 559 | |
| 560 | * bitmap_block needs to be unlocked because getting the
|
| 561 | * overflow_leaf may need to allocate, and thus use the space map.
|
| 562 |
|
| 563 | reset_inc_context(ll, ic);
|
| 564 |
|
| 565 | r = btree_get_overwrite_leaf(&ll->ref_count_info, ll->ref_count_root,
|
| 566 | b, &index, &ll->ref_count_root, &ic->overflow_leaf);
|
| 567 | if (r < 0)
|
| 568 | return r;
|
| 569 |
|
| 570 | n = dm_block_data(ic->overflow_leaf);
|
| 571 |
|
| 572 | if (!contains_key(n, b, index)) {
|
| 573 | DMERR("overflow btree is missing an entry");
|
| 574 | return -EINVAL;
|
| 575 | }
|
| 576 |
|
| 577 | v_ptr = value_ptr(n, index);
|
| 578 | rc = le32_to_cpu(*v_ptr) + 1;
|
| 579 | *v_ptr = cpu_to_le32(rc);
|
| 580 |
|
| 581 | return 0;
|
| 582 | }
|
| 583 |
|
| 584 | static int sm_ll_inc_overflow(struct ll_disk *ll, dm_block_t b, struct inc_context *ic)
|
| 585 | {
|
| 586 | int index;
|
| 587 | struct btree_node *n;
|
| 588 | __le32 *v_ptr;
|
| 589 | uint32_t rc;
|
| 590 |
|
| 591 | |
| 592 | * Do we already have the correct overflow leaf?
|
| 593 |
|
| 594 | if (ic->overflow_leaf) {
|
| 595 | n = dm_block_data(ic->overflow_leaf);
|
| 596 | index = lower_bound(n, b);
|
| 597 | if (contains_key(n, b, index)) {
|
| 598 | v_ptr = value_ptr(n, index);
|
| 599 | rc = le32_to_cpu(*v_ptr) + 1;
|
| 600 | *v_ptr = cpu_to_le32(rc);
|
| 601 |
|
| 602 | return 0;
|
| 603 | }
|
| 604 | }
|
| 605 |
|
| 606 | return __sm_ll_inc_overflow(ll, b, ic);
|
| 607 | }
|
| 608 |
|
| 609 | static inline int shadow_bitmap(struct ll_disk *ll, struct inc_context *ic)
|
| 610 | {
|
| 611 | int r, inc;
|
| 612 |
|
| 613 | r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ic->ie_disk.blocknr),
|
| 614 | &dm_sm_bitmap_validator, &ic->bitmap_block, &inc);
|
| 615 | if (r < 0) {
|
| 616 | DMERR("dm_tm_shadow_block() failed");
|
| 617 | return r;
|
| 618 | }
|
| 619 | ic->ie_disk.blocknr = cpu_to_le64(dm_block_location(ic->bitmap_block));
|
| 620 | ic->bitmap = dm_bitmap_data(ic->bitmap_block);
|
| 621 | return 0;
|
| 622 | }
|
| 623 |
|
| 624 | |
| 625 | * Once shadow_bitmap has been called, which always happens at the start of inc/dec,
|
| 626 | * we can reopen the bitmap with a simple write lock, rather than re calling
|
| 627 | * dm_tm_shadow_block().
|
| 628 |
|
| 629 | static inline int ensure_bitmap(struct ll_disk *ll, struct inc_context *ic)
|
| 630 | {
|
| 631 | if (!ic->bitmap_block) {
|
| 632 | int r = dm_bm_write_lock(dm_tm_get_bm(ll->tm), le64_to_cpu(ic->ie_disk.blocknr),
|
| 633 | &dm_sm_bitmap_validator, &ic->bitmap_block);
|
| 634 | if (r) {
|
| 635 | DMERR("unable to re-get write lock for bitmap");
|
| 636 | return r;
|
| 637 | }
|
| 638 | ic->bitmap = dm_bitmap_data(ic->bitmap_block);
|
| 639 | }
|
| 640 |
|
| 641 | return 0;
|
| 642 | }
|
| 643 |
|
| 644 | |
| 645 | * Loops round incrementing entries in a single bitmap.
|
| 646 |
|
| 647 | static inline int sm_ll_inc_bitmap(struct ll_disk *ll, dm_block_t b,
|
| 648 | uint32_t bit, uint32_t bit_end,
|
| 649 | int32_t *nr_allocations, dm_block_t *new_b,
|
| 650 | struct inc_context *ic)
|
| 651 | {
|
| 652 | int r;
|
| 653 | __le32 le_rc;
|
| 654 | uint32_t old;
|
| 655 |
|
| 656 | for (; bit != bit_end; bit++, b++) {
|
| 657 | |
| 658 | * We only need to drop the bitmap if we need to find a new btree
|
| 659 | * leaf for the overflow. So if it was dropped last iteration,
|
| 660 | * we now re-get it.
|
| 661 |
|
| 662 | r = ensure_bitmap(ll, ic);
|
| 663 | if (r)
|
| 664 | return r;
|
| 665 |
|
| 666 | old = sm_lookup_bitmap(ic->bitmap, bit);
|
| 667 | switch (old) {
|
| 668 | case 0:
|
| 669 |
|
| 670 | sm_set_bitmap(ic->bitmap, bit, 1);
|
| 671 | (*nr_allocations)++;
|
| 672 | ll->nr_allocated++;
|
| 673 | le32_add_cpu(&ic->ie_disk.nr_free, -1);
|
| 674 | if (le32_to_cpu(ic->ie_disk.none_free_before) == bit)
|
| 675 | ic->ie_disk.none_free_before = cpu_to_le32(bit + 1);
|
| 676 | break;
|
| 677 |
|
| 678 | case 1:
|
| 679 |
|
| 680 | sm_set_bitmap(ic->bitmap, bit, 2);
|
| 681 | break;
|
| 682 |
|
| 683 | case 2:
|
| 684 |
|
| 685 | sm_set_bitmap(ic->bitmap, bit, 3);
|
| 686 | reset_inc_context(ll, ic);
|
| 687 |
|
| 688 | le_rc = cpu_to_le32(3);
|
| 689 | __dm_bless_for_disk(&le_rc);
|
| 690 | r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root,
|
| 691 | &b, &le_rc, &ll->ref_count_root);
|
| 692 | if (r < 0) {
|
| 693 | DMERR("ref count insert failed");
|
| 694 | return r;
|
| 695 | }
|
| 696 | break;
|
| 697 |
|
| 698 | default:
|
| 699 | |
| 700 | * inc within the overflow tree only.
|
| 701 |
|
| 702 | r = sm_ll_inc_overflow(ll, b, ic);
|
| 703 | if (r < 0)
|
| 704 | return r;
|
| 705 | }
|
| 706 | }
|
| 707 |
|
| 708 | *new_b = b;
|
| 709 | return 0;
|
| 710 | }
|
| 711 |
|
| 712 | |
| 713 | * Finds a bitmap that contains entries in the block range, and increments
|
| 714 | * them.
|
| 715 |
|
| 716 | static int __sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e,
|
| 717 | int32_t *nr_allocations, dm_block_t *new_b)
|
| 718 | {
|
| 719 | int r;
|
| 720 | struct inc_context ic;
|
| 721 | uint32_t bit, bit_end;
|
| 722 | dm_block_t index = b;
|
| 723 |
|
| 724 | init_inc_context(&ic);
|
| 725 |
|
| 726 | bit = do_div(index, ll->entries_per_block);
|
| 727 | r = ll->load_ie(ll, index, &ic.ie_disk);
|
| 728 | if (r < 0)
|
| 729 | return r;
|
| 730 |
|
| 731 | r = shadow_bitmap(ll, &ic);
|
| 732 | if (r)
|
| 733 | return r;
|
| 734 |
|
| 735 | bit_end = min(bit + (e - b), (dm_block_t) ll->entries_per_block);
|
| 736 | r = sm_ll_inc_bitmap(ll, b, bit, bit_end, nr_allocations, new_b, &ic);
|
| 737 |
|
| 738 | exit_inc_context(ll, &ic);
|
| 739 |
|
| 740 | if (r)
|
| 741 | return r;
|
| 742 |
|
| 743 | return ll->save_ie(ll, index, &ic.ie_disk);
|
| 744 | }
|
| 745 |
|
| 746 | int sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e,
|
| 747 | int32_t *nr_allocations)
|
| 748 | {
|
| 749 | *nr_allocations = 0;
|
| 750 | while (b != e) {
|
| 751 | int r = __sm_ll_inc(ll, b, e, nr_allocations, &b);
|
| 752 |
|
| 753 | if (r)
|
| 754 | return r;
|
| 755 | }
|
| 756 |
|
| 757 | return 0;
|
| 758 | }
|
| 759 |
|
| 760 |
|
| 761 |
|
| 762 | static int __sm_ll_del_overflow(struct ll_disk *ll, dm_block_t b,
|
| 763 | struct inc_context *ic)
|
| 764 | {
|
| 765 | reset_inc_context(ll, ic);
|
| 766 | return dm_btree_remove(&ll->ref_count_info, ll->ref_count_root,
|
| 767 | &b, &ll->ref_count_root);
|
| 768 | }
|
| 769 |
|
| 770 | static int __sm_ll_dec_overflow(struct ll_disk *ll, dm_block_t b,
|
| 771 | struct inc_context *ic, uint32_t *old_rc)
|
| 772 | {
|
| 773 | int r;
|
| 774 | int index = -1;
|
| 775 | struct btree_node *n;
|
| 776 | __le32 *v_ptr;
|
| 777 | uint32_t rc;
|
| 778 |
|
| 779 | reset_inc_context(ll, ic);
|
| 780 | r = btree_get_overwrite_leaf(&ll->ref_count_info, ll->ref_count_root,
|
| 781 | b, &index, &ll->ref_count_root, &ic->overflow_leaf);
|
| 782 | if (r < 0)
|
| 783 | return r;
|
| 784 |
|
| 785 | n = dm_block_data(ic->overflow_leaf);
|
| 786 |
|
| 787 | if (!contains_key(n, b, index)) {
|
| 788 | DMERR("overflow btree is missing an entry");
|
| 789 | return -EINVAL;
|
| 790 | }
|
| 791 |
|
| 792 | v_ptr = value_ptr(n, index);
|
| 793 | rc = le32_to_cpu(*v_ptr);
|
| 794 | *old_rc = rc;
|
| 795 |
|
| 796 | if (rc == 3)
|
| 797 | return __sm_ll_del_overflow(ll, b, ic);
|
| 798 |
|
| 799 | rc--;
|
| 800 | *v_ptr = cpu_to_le32(rc);
|
| 801 | return 0;
|
| 802 | }
|
| 803 |
|
| 804 | static int sm_ll_dec_overflow(struct ll_disk *ll, dm_block_t b,
|
| 805 | struct inc_context *ic, uint32_t *old_rc)
|
| 806 | {
|
| 807 | |
| 808 | * Do we already have the correct overflow leaf?
|
| 809 |
|
| 810 | if (ic->overflow_leaf) {
|
| 811 | int index;
|
| 812 | struct btree_node *n;
|
| 813 | __le32 *v_ptr;
|
| 814 | uint32_t rc;
|
| 815 |
|
| 816 | n = dm_block_data(ic->overflow_leaf);
|
| 817 | index = lower_bound(n, b);
|
| 818 | if (contains_key(n, b, index)) {
|
| 819 | v_ptr = value_ptr(n, index);
|
| 820 | rc = le32_to_cpu(*v_ptr);
|
| 821 | *old_rc = rc;
|
| 822 |
|
| 823 | if (rc > 3) {
|
| 824 | rc--;
|
| 825 | *v_ptr = cpu_to_le32(rc);
|
| 826 | return 0;
|
| 827 | } else {
|
| 828 | return __sm_ll_del_overflow(ll, b, ic);
|
| 829 | }
|
| 830 |
|
| 831 | }
|
| 832 | }
|
| 833 |
|
| 834 | return __sm_ll_dec_overflow(ll, b, ic, old_rc);
|
| 835 | }
|
| 836 |
|
| 837 | |
| 838 | * Loops round incrementing entries in a single bitmap.
|
| 839 |
|
| 840 | static inline int sm_ll_dec_bitmap(struct ll_disk *ll, dm_block_t b,
|
| 841 | uint32_t bit, uint32_t bit_end,
|
| 842 | struct inc_context *ic,
|
| 843 | int32_t *nr_allocations, dm_block_t *new_b)
|
| 844 | {
|
| 845 | int r;
|
| 846 | uint32_t old;
|
| 847 |
|
| 848 | for (; bit != bit_end; bit++, b++) {
|
| 849 | |
| 850 | * We only need to drop the bitmap if we need to find a new btree
|
| 851 | * leaf for the overflow. So if it was dropped last iteration,
|
| 852 | * we now re-get it.
|
| 853 |
|
| 854 | r = ensure_bitmap(ll, ic);
|
| 855 | if (r)
|
| 856 | return r;
|
| 857 |
|
| 858 | old = sm_lookup_bitmap(ic->bitmap, bit);
|
| 859 | switch (old) {
|
| 860 | case 0:
|
| 861 | DMERR("unable to decrement block");
|
| 862 | return -EINVAL;
|
| 863 |
|
| 864 | case 1:
|
| 865 |
|
| 866 | sm_set_bitmap(ic->bitmap, bit, 0);
|
| 867 | (*nr_allocations)--;
|
| 868 | ll->nr_allocated--;
|
| 869 | le32_add_cpu(&ic->ie_disk.nr_free, 1);
|
| 870 | ic->ie_disk.none_free_before =
|
| 871 | cpu_to_le32(min(le32_to_cpu(ic->ie_disk.none_free_before), bit));
|
| 872 | break;
|
| 873 |
|
| 874 | case 2:
|
| 875 |
|
| 876 | sm_set_bitmap(ic->bitmap, bit, 1);
|
| 877 | break;
|
| 878 |
|
| 879 | case 3:
|
| 880 | r = sm_ll_dec_overflow(ll, b, ic, &old);
|
| 881 | if (r < 0)
|
| 882 | return r;
|
| 883 |
|
| 884 | if (old == 3) {
|
| 885 | r = ensure_bitmap(ll, ic);
|
| 886 | if (r)
|
| 887 | return r;
|
| 888 |
|
| 889 | sm_set_bitmap(ic->bitmap, bit, 2);
|
| 890 | }
|
| 891 | break;
|
| 892 | }
|
| 893 | }
|
| 894 |
|
| 895 | *new_b = b;
|
| 896 | return 0;
|
| 897 | }
|
| 898 |
|
| 899 | static int __sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e,
|
| 900 | int32_t *nr_allocations, dm_block_t *new_b)
|
| 901 | {
|
| 902 | int r;
|
| 903 | uint32_t bit, bit_end;
|
| 904 | struct inc_context ic;
|
| 905 | dm_block_t index = b;
|
| 906 |
|
| 907 | init_inc_context(&ic);
|
| 908 |
|
| 909 | bit = do_div(index, ll->entries_per_block);
|
| 910 | r = ll->load_ie(ll, index, &ic.ie_disk);
|
| 911 | if (r < 0)
|
| 912 | return r;
|
| 913 |
|
| 914 | r = shadow_bitmap(ll, &ic);
|
| 915 | if (r)
|
| 916 | return r;
|
| 917 |
|
| 918 | bit_end = min(bit + (e - b), (dm_block_t) ll->entries_per_block);
|
| 919 | r = sm_ll_dec_bitmap(ll, b, bit, bit_end, &ic, nr_allocations, new_b);
|
| 920 | exit_inc_context(ll, &ic);
|
| 921 |
|
| 922 | if (r)
|
| 923 | return r;
|
| 924 |
|
| 925 | return ll->save_ie(ll, index, &ic.ie_disk);
|
| 926 | }
|
| 927 |
|
| 928 | int sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e,
|
| 929 | int32_t *nr_allocations)
|
| 930 | {
|
| 931 | *nr_allocations = 0;
|
| 932 | while (b != e) {
|
| 933 | int r = __sm_ll_dec(ll, b, e, nr_allocations, &b);
|
| 934 |
|
| 935 | if (r)
|
| 936 | return r;
|
| 937 | }
|
| 938 |
|
| 939 | return 0;
|
| 940 | }
|
| 941 |
|
| 942 |
|
| 943 |
|
| 944 | int sm_ll_commit(struct ll_disk *ll)
|
| 945 | {
|
| 946 | int r = 0;
|
| 947 |
|
| 948 | if (ll->bitmap_index_changed) {
|
| 949 | r = ll->commit(ll);
|
| 950 | if (!r)
|
| 951 | ll->bitmap_index_changed = false;
|
| 952 | }
|
| 953 |
|
| 954 | return r;
|
| 955 | }
|
| 956 |
|
| 957 |
|
| 958 |
|
| 959 | static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index,
|
| 960 | struct disk_index_entry *ie)
|
| 961 | {
|
| 962 | memcpy(ie, ll->mi_le.index + index, sizeof(*ie));
|
| 963 | return 0;
|
| 964 | }
|
| 965 |
|
| 966 | static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index,
|
| 967 | struct disk_index_entry *ie)
|
| 968 | {
|
| 969 | ll->bitmap_index_changed = true;
|
| 970 | memcpy(ll->mi_le.index + index, ie, sizeof(*ie));
|
| 971 | return 0;
|
| 972 | }
|
| 973 |
|
| 974 | static int metadata_ll_init_index(struct ll_disk *ll)
|
| 975 | {
|
| 976 | int r;
|
| 977 | struct dm_block *b;
|
| 978 |
|
| 979 | r = dm_tm_new_block(ll->tm, &index_validator, &b);
|
| 980 | if (r < 0)
|
| 981 | return r;
|
| 982 |
|
| 983 | ll->bitmap_root = dm_block_location(b);
|
| 984 |
|
| 985 | dm_tm_unlock(ll->tm, b);
|
| 986 |
|
| 987 | return 0;
|
| 988 | }
|
| 989 |
|
| 990 | static int metadata_ll_open(struct ll_disk *ll)
|
| 991 | {
|
| 992 | int r;
|
| 993 | struct dm_block *block;
|
| 994 |
|
| 995 | r = dm_tm_read_lock(ll->tm, ll->bitmap_root,
|
| 996 | &index_validator, &block);
|
| 997 | if (r)
|
| 998 | return r;
|
| 999 |
|
| 1000 | memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le));
|
| 1001 | dm_tm_unlock(ll->tm, block);
|
| 1002 |
|
| 1003 | return 0;
|
| 1004 | }
|
| 1005 |
|
| 1006 | static dm_block_t metadata_ll_max_entries(struct ll_disk *ll)
|
| 1007 | {
|
| 1008 | return MAX_METADATA_BITMAPS;
|
| 1009 | }
|
| 1010 |
|
| 1011 | static int metadata_ll_commit(struct ll_disk *ll)
|
| 1012 | {
|
| 1013 | int r, inc;
|
| 1014 | struct dm_block *b;
|
| 1015 |
|
| 1016 | r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc);
|
| 1017 | if (r)
|
| 1018 | return r;
|
| 1019 |
|
| 1020 | memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
|
| 1021 | ll->bitmap_root = dm_block_location(b);
|
| 1022 |
|
| 1023 | dm_tm_unlock(ll->tm, b);
|
| 1024 |
|
| 1025 | return 0;
|
| 1026 | }
|
| 1027 |
|
| 1028 | int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm)
|
| 1029 | {
|
| 1030 | int r;
|
| 1031 |
|
| 1032 | r = sm_ll_init(ll, tm);
|
| 1033 | if (r < 0)
|
| 1034 | return r;
|
| 1035 |
|
| 1036 | ll->load_ie = metadata_ll_load_ie;
|
| 1037 | ll->save_ie = metadata_ll_save_ie;
|
| 1038 | ll->init_index = metadata_ll_init_index;
|
| 1039 | ll->open_index = metadata_ll_open;
|
| 1040 | ll->max_entries = metadata_ll_max_entries;
|
| 1041 | ll->commit = metadata_ll_commit;
|
| 1042 |
|
| 1043 | ll->nr_blocks = 0;
|
| 1044 | ll->nr_allocated = 0;
|
| 1045 |
|
| 1046 | r = ll->init_index(ll);
|
| 1047 | if (r < 0)
|
| 1048 | return r;
|
| 1049 |
|
| 1050 | r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
|
| 1051 | if (r < 0)
|
| 1052 | return r;
|
| 1053 |
|
| 1054 | return 0;
|
| 1055 | }
|
| 1056 |
|
| 1057 | int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm,
|
| 1058 | void *root_le, size_t len)
|
| 1059 | {
|
| 1060 | int r;
|
| 1061 | struct disk_sm_root smr;
|
| 1062 |
|
| 1063 | if (len < sizeof(struct disk_sm_root)) {
|
| 1064 | DMERR("sm_metadata root too small");
|
| 1065 | return -ENOMEM;
|
| 1066 | }
|
| 1067 |
|
| 1068 | |
| 1069 | * We don't know the alignment of the root_le buffer, so need to
|
| 1070 | * copy into a new structure.
|
| 1071 |
|
| 1072 | memcpy(&smr, root_le, sizeof(smr));
|
| 1073 |
|
| 1074 | r = sm_ll_init(ll, tm);
|
| 1075 | if (r < 0)
|
| 1076 | return r;
|
| 1077 |
|
| 1078 | ll->load_ie = metadata_ll_load_ie;
|
| 1079 | ll->save_ie = metadata_ll_save_ie;
|
| 1080 | ll->init_index = metadata_ll_init_index;
|
| 1081 | ll->open_index = metadata_ll_open;
|
| 1082 | ll->max_entries = metadata_ll_max_entries;
|
| 1083 | ll->commit = metadata_ll_commit;
|
| 1084 |
|
| 1085 | ll->nr_blocks = le64_to_cpu(smr.nr_blocks);
|
| 1086 | ll->nr_allocated = le64_to_cpu(smr.nr_allocated);
|
| 1087 | ll->bitmap_root = le64_to_cpu(smr.bitmap_root);
|
| 1088 | ll->ref_count_root = le64_to_cpu(smr.ref_count_root);
|
| 1089 |
|
| 1090 | return ll->open_index(ll);
|
| 1091 | }
|
| 1092 |
|
| 1093 |
|
| 1094 |
|
| 1095 | static inline int ie_cache_writeback(struct ll_disk *ll, struct ie_cache *iec)
|
| 1096 | {
|
| 1097 | iec->dirty = false;
|
| 1098 | __dm_bless_for_disk(iec->ie);
|
| 1099 | return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root,
|
| 1100 | &iec->index, &iec->ie, &ll->bitmap_root);
|
| 1101 | }
|
| 1102 |
|
| 1103 | static inline unsigned int hash_index(dm_block_t index)
|
| 1104 | {
|
| 1105 | return dm_hash_block(index, IE_CACHE_MASK);
|
| 1106 | }
|
| 1107 |
|
| 1108 | static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index,
|
| 1109 | struct disk_index_entry *ie)
|
| 1110 | {
|
| 1111 | int r;
|
| 1112 | unsigned int h = hash_index(index);
|
| 1113 | struct ie_cache *iec = ll->ie_cache + h;
|
| 1114 |
|
| 1115 | if (iec->valid) {
|
| 1116 | if (iec->index == index) {
|
| 1117 | memcpy(ie, &iec->ie, sizeof(*ie));
|
| 1118 | return 0;
|
| 1119 | }
|
| 1120 |
|
| 1121 | if (iec->dirty) {
|
| 1122 | r = ie_cache_writeback(ll, iec);
|
| 1123 | if (r)
|
| 1124 | return r;
|
| 1125 | }
|
| 1126 | }
|
| 1127 |
|
| 1128 | r = dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie);
|
| 1129 | if (!r) {
|
| 1130 | iec->valid = true;
|
| 1131 | iec->dirty = false;
|
| 1132 | iec->index = index;
|
| 1133 | memcpy(&iec->ie, ie, sizeof(*ie));
|
| 1134 | }
|
| 1135 |
|
| 1136 | return r;
|
| 1137 | }
|
| 1138 |
|
| 1139 | static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index,
|
| 1140 | struct disk_index_entry *ie)
|
| 1141 | {
|
| 1142 | int r;
|
| 1143 | unsigned int h = hash_index(index);
|
| 1144 | struct ie_cache *iec = ll->ie_cache + h;
|
| 1145 |
|
| 1146 | ll->bitmap_index_changed = true;
|
| 1147 | if (iec->valid) {
|
| 1148 | if (iec->index == index) {
|
| 1149 | memcpy(&iec->ie, ie, sizeof(*ie));
|
| 1150 | iec->dirty = true;
|
| 1151 | return 0;
|
| 1152 | }
|
| 1153 |
|
| 1154 | if (iec->dirty) {
|
| 1155 | r = ie_cache_writeback(ll, iec);
|
| 1156 | if (r)
|
| 1157 | return r;
|
| 1158 | }
|
| 1159 | }
|
| 1160 |
|
| 1161 | iec->valid = true;
|
| 1162 | iec->dirty = true;
|
| 1163 | iec->index = index;
|
| 1164 | memcpy(&iec->ie, ie, sizeof(*ie));
|
| 1165 | return 0;
|
| 1166 | }
|
| 1167 |
|
| 1168 | static int disk_ll_init_index(struct ll_disk *ll)
|
| 1169 | {
|
| 1170 | unsigned int i;
|
| 1171 |
|
| 1172 | for (i = 0; i < IE_CACHE_SIZE; i++) {
|
| 1173 | struct ie_cache *iec = ll->ie_cache + i;
|
| 1174 |
|
| 1175 | iec->valid = false;
|
| 1176 | iec->dirty = false;
|
| 1177 | }
|
| 1178 | return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root);
|
| 1179 | }
|
| 1180 |
|
| 1181 | static int disk_ll_open(struct ll_disk *ll)
|
| 1182 | {
|
| 1183 | return 0;
|
| 1184 | }
|
| 1185 |
|
| 1186 | static dm_block_t disk_ll_max_entries(struct ll_disk *ll)
|
| 1187 | {
|
| 1188 | return -1ULL;
|
| 1189 | }
|
| 1190 |
|
| 1191 | static int disk_ll_commit(struct ll_disk *ll)
|
| 1192 | {
|
| 1193 | int r = 0;
|
| 1194 | unsigned int i;
|
| 1195 |
|
| 1196 | for (i = 0; i < IE_CACHE_SIZE; i++) {
|
| 1197 | struct ie_cache *iec = ll->ie_cache + i;
|
| 1198 |
|
| 1199 | if (iec->valid && iec->dirty)
|
| 1200 | r = ie_cache_writeback(ll, iec);
|
| 1201 | }
|
| 1202 |
|
| 1203 | return r;
|
| 1204 | }
|
| 1205 |
|
| 1206 | int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm)
|
| 1207 | {
|
| 1208 | int r;
|
| 1209 |
|
| 1210 | r = sm_ll_init(ll, tm);
|
| 1211 | if (r < 0)
|
| 1212 | return r;
|
| 1213 |
|
| 1214 | ll->load_ie = disk_ll_load_ie;
|
| 1215 | ll->save_ie = disk_ll_save_ie;
|
| 1216 | ll->init_index = disk_ll_init_index;
|
| 1217 | ll->open_index = disk_ll_open;
|
| 1218 | ll->max_entries = disk_ll_max_entries;
|
| 1219 | ll->commit = disk_ll_commit;
|
| 1220 |
|
| 1221 | ll->nr_blocks = 0;
|
| 1222 | ll->nr_allocated = 0;
|
| 1223 |
|
| 1224 | r = ll->init_index(ll);
|
| 1225 | if (r < 0)
|
| 1226 | return r;
|
| 1227 |
|
| 1228 | r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root);
|
| 1229 | if (r < 0)
|
| 1230 | return r;
|
| 1231 |
|
| 1232 | return 0;
|
| 1233 | }
|
| 1234 |
|
| 1235 | int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm,
|
| 1236 | void *root_le, size_t len)
|
| 1237 | {
|
| 1238 | int r;
|
| 1239 | struct disk_sm_root *smr = root_le;
|
| 1240 |
|
| 1241 | if (len < sizeof(struct disk_sm_root)) {
|
| 1242 | DMERR("sm_metadata root too small");
|
| 1243 | return -ENOMEM;
|
| 1244 | }
|
| 1245 |
|
| 1246 | r = sm_ll_init(ll, tm);
|
| 1247 | if (r < 0)
|
| 1248 | return r;
|
| 1249 |
|
| 1250 | ll->load_ie = disk_ll_load_ie;
|
| 1251 | ll->save_ie = disk_ll_save_ie;
|
| 1252 | ll->init_index = disk_ll_init_index;
|
| 1253 | ll->open_index = disk_ll_open;
|
| 1254 | ll->max_entries = disk_ll_max_entries;
|
| 1255 | ll->commit = disk_ll_commit;
|
| 1256 |
|
| 1257 | ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
|
| 1258 | ll->nr_allocated = le64_to_cpu(smr->nr_allocated);
|
| 1259 | ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
|
| 1260 | ll->ref_count_root = le64_to_cpu(smr->ref_count_root);
|
| 1261 |
|
| 1262 | return ll->open_index(ll);
|
| 1263 | }
|
| 1264 |
|
| 1265 |
|