Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
dm-space-map-common.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2011 Red Hat, Inc.
3  *
4  * This file is released under the GPL.
5  */
6 
7 #include "dm-space-map-common.h"
9 
10 #include <linux/bitops.h>
11 #include <linux/device-mapper.h>
12 
13 #define DM_MSG_PREFIX "space map common"
14 
15 /*----------------------------------------------------------------*/
16 
17 /*
18  * Index validator.
19  */
20 #define INDEX_CSUM_XOR 160478
21 
22 static void index_prepare_for_write(struct dm_block_validator *v,
23  struct dm_block *b,
24  size_t block_size)
25 {
26  struct disk_metadata_index *mi_le = dm_block_data(b);
27 
29  mi_le->csum = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
30  block_size - sizeof(__le32),
32 }
33 
34 static int index_check(struct dm_block_validator *v,
35  struct dm_block *b,
36  size_t block_size)
37 {
38  struct disk_metadata_index *mi_le = dm_block_data(b);
39  __le32 csum_disk;
40 
41  if (dm_block_location(b) != le64_to_cpu(mi_le->blocknr)) {
42  DMERR("index_check failed blocknr %llu wanted %llu",
44  return -ENOTBLK;
45  }
46 
47  csum_disk = cpu_to_le32(dm_bm_checksum(&mi_le->padding,
48  block_size - sizeof(__le32),
50  if (csum_disk != mi_le->csum) {
51  DMERR("index_check failed csum %u wanted %u",
52  le32_to_cpu(csum_disk), le32_to_cpu(mi_le->csum));
53  return -EILSEQ;
54  }
55 
56  return 0;
57 }
58 
59 static struct dm_block_validator index_validator = {
60  .name = "index",
61  .prepare_for_write = index_prepare_for_write,
62  .check = index_check
63 };
64 
65 /*----------------------------------------------------------------*/
66 
67 /*
68  * Bitmap validator
69  */
70 #define BITMAP_CSUM_XOR 240779
71 
72 static void bitmap_prepare_for_write(struct dm_block_validator *v,
73  struct dm_block *b,
74  size_t block_size)
75 {
77 
78  disk_header->blocknr = cpu_to_le64(dm_block_location(b));
79  disk_header->csum = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
80  block_size - sizeof(__le32),
82 }
83 
84 static int bitmap_check(struct dm_block_validator *v,
85  struct dm_block *b,
86  size_t block_size)
87 {
89  __le32 csum_disk;
90 
91  if (dm_block_location(b) != le64_to_cpu(disk_header->blocknr)) {
92  DMERR("bitmap check failed blocknr %llu wanted %llu",
93  le64_to_cpu(disk_header->blocknr), dm_block_location(b));
94  return -ENOTBLK;
95  }
96 
97  csum_disk = cpu_to_le32(dm_bm_checksum(&disk_header->not_used,
98  block_size - sizeof(__le32),
100  if (csum_disk != disk_header->csum) {
101  DMERR("bitmap check failed csum %u wanted %u",
102  le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum));
103  return -EILSEQ;
104  }
105 
106  return 0;
107 }
108 
109 static struct dm_block_validator dm_sm_bitmap_validator = {
110  .name = "sm_bitmap",
111  .prepare_for_write = bitmap_prepare_for_write,
112  .check = bitmap_check
113 };
114 
115 /*----------------------------------------------------------------*/
116 
117 #define ENTRIES_PER_WORD 32
118 #define ENTRIES_SHIFT 5
119 
120 static void *dm_bitmap_data(struct dm_block *b)
121 {
122  return dm_block_data(b) + sizeof(struct disk_bitmap_header);
123 }
124 
125 #define WORD_MASK_HIGH 0xAAAAAAAAAAAAAAAAULL
126 
127 static unsigned bitmap_word_used(void *addr, unsigned b)
128 {
129  __le64 *words_le = addr;
130  __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
131 
132  uint64_t bits = le64_to_cpu(*w_le);
133  uint64_t mask = (bits + WORD_MASK_HIGH + 1) & WORD_MASK_HIGH;
134 
135  return !(~bits & mask);
136 }
137 
138 static unsigned sm_lookup_bitmap(void *addr, unsigned b)
139 {
140  __le64 *words_le = addr;
141  __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
142  unsigned hi, lo;
143 
144  b = (b & (ENTRIES_PER_WORD - 1)) << 1;
145  hi = !!test_bit_le(b, (void *) w_le);
146  lo = !!test_bit_le(b + 1, (void *) w_le);
147  return (hi << 1) | lo;
148 }
149 
150 static void sm_set_bitmap(void *addr, unsigned b, unsigned val)
151 {
152  __le64 *words_le = addr;
153  __le64 *w_le = words_le + (b >> ENTRIES_SHIFT);
154 
155  b = (b & (ENTRIES_PER_WORD - 1)) << 1;
156 
157  if (val & 2)
158  __set_bit_le(b, (void *) w_le);
159  else
160  __clear_bit_le(b, (void *) w_le);
161 
162  if (val & 1)
163  __set_bit_le(b + 1, (void *) w_le);
164  else
165  __clear_bit_le(b + 1, (void *) w_le);
166 }
167 
168 static int sm_find_free(void *addr, unsigned begin, unsigned end,
169  unsigned *result)
170 {
171  while (begin < end) {
172  if (!(begin & (ENTRIES_PER_WORD - 1)) &&
173  bitmap_word_used(addr, begin)) {
174  begin += ENTRIES_PER_WORD;
175  continue;
176  }
177 
178  if (!sm_lookup_bitmap(addr, begin)) {
179  *result = begin;
180  return 0;
181  }
182 
183  begin++;
184  }
185 
186  return -ENOSPC;
187 }
188 
189 /*----------------------------------------------------------------*/
190 
191 static int sm_ll_init(struct ll_disk *ll, struct dm_transaction_manager *tm)
192 {
193  ll->tm = tm;
194 
195  ll->bitmap_info.tm = tm;
196  ll->bitmap_info.levels = 1;
197 
198  /*
199  * Because the new bitmap blocks are created via a shadow
200  * operation, the old entry has already had its reference count
201  * decremented and we don't need the btree to do any bookkeeping.
202  */
203  ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry);
204  ll->bitmap_info.value_type.inc = NULL;
205  ll->bitmap_info.value_type.dec = NULL;
206  ll->bitmap_info.value_type.equal = NULL;
207 
208  ll->ref_count_info.tm = tm;
209  ll->ref_count_info.levels = 1;
210  ll->ref_count_info.value_type.size = sizeof(uint32_t);
211  ll->ref_count_info.value_type.inc = NULL;
212  ll->ref_count_info.value_type.dec = NULL;
213  ll->ref_count_info.value_type.equal = NULL;
214 
216 
217  if (ll->block_size > (1 << 30)) {
218  DMERR("block size too big to hold bitmaps");
219  return -EINVAL;
220  }
221 
222  ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) *
224  ll->nr_blocks = 0;
225  ll->bitmap_root = 0;
226  ll->ref_count_root = 0;
227  ll->bitmap_index_changed = false;
228 
229  return 0;
230 }
231 
232 int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks)
233 {
234  int r;
235  dm_block_t i, nr_blocks, nr_indexes;
236  unsigned old_blocks, blocks;
237 
238  nr_blocks = ll->nr_blocks + extra_blocks;
239  old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block);
240  blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block);
241 
242  nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block);
243  if (nr_indexes > ll->max_entries(ll)) {
244  DMERR("space map too large");
245  return -EINVAL;
246  }
247 
248  for (i = old_blocks; i < blocks; i++) {
249  struct dm_block *b;
250  struct disk_index_entry idx;
251 
252  r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b);
253  if (r < 0)
254  return r;
256 
257  r = dm_tm_unlock(ll->tm, b);
258  if (r < 0)
259  return r;
260 
262  idx.none_free_before = 0;
263 
264  r = ll->save_ie(ll, i, &idx);
265  if (r < 0)
266  return r;
267  }
268 
269  ll->nr_blocks = nr_blocks;
270  return 0;
271 }
272 
273 int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result)
274 {
275  int r;
276  dm_block_t index = b;
277  struct disk_index_entry ie_disk;
278  struct dm_block *blk;
279 
280  b = do_div(index, ll->entries_per_block);
281  r = ll->load_ie(ll, index, &ie_disk);
282  if (r < 0)
283  return r;
284 
285  r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
286  &dm_sm_bitmap_validator, &blk);
287  if (r < 0)
288  return r;
289 
290  *result = sm_lookup_bitmap(dm_bitmap_data(blk), b);
291 
292  return dm_tm_unlock(ll->tm, blk);
293 }
294 
295 int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result)
296 {
297  __le32 le_rc;
298  int r = sm_ll_lookup_bitmap(ll, b, result);
299 
300  if (r)
301  return r;
302 
303  if (*result != 3)
304  return r;
305 
306  r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc);
307  if (r < 0)
308  return r;
309 
310  *result = le32_to_cpu(le_rc);
311 
312  return r;
313 }
314 
316  dm_block_t end, dm_block_t *result)
317 {
318  int r;
319  struct disk_index_entry ie_disk;
320  dm_block_t i, index_begin = begin;
321  dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block);
322 
323  /*
324  * FIXME: Use shifts
325  */
326  begin = do_div(index_begin, ll->entries_per_block);
327  end = do_div(end, ll->entries_per_block);
328 
329  for (i = index_begin; i < index_end; i++, begin = 0) {
330  struct dm_block *blk;
331  unsigned position;
332  uint32_t bit_end;
333 
334  r = ll->load_ie(ll, i, &ie_disk);
335  if (r < 0)
336  return r;
337 
338  if (le32_to_cpu(ie_disk.nr_free) == 0)
339  continue;
340 
341  r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr),
342  &dm_sm_bitmap_validator, &blk);
343  if (r < 0)
344  return r;
345 
346  bit_end = (i == index_end - 1) ? end : ll->entries_per_block;
347 
348  r = sm_find_free(dm_bitmap_data(blk),
349  max_t(unsigned, begin, le32_to_cpu(ie_disk.none_free_before)),
350  bit_end, &position);
351  if (r == -ENOSPC) {
352  /*
353  * This might happen because we started searching
354  * part way through the bitmap.
355  */
356  dm_tm_unlock(ll->tm, blk);
357  continue;
358 
359  } else if (r < 0) {
360  dm_tm_unlock(ll->tm, blk);
361  return r;
362  }
363 
364  r = dm_tm_unlock(ll->tm, blk);
365  if (r < 0)
366  return r;
367 
368  *result = i * ll->entries_per_block + (dm_block_t) position;
369  return 0;
370  }
371 
372  return -ENOSPC;
373 }
374 
375 int sm_ll_insert(struct ll_disk *ll, dm_block_t b,
376  uint32_t ref_count, enum allocation_event *ev)
377 {
378  int r;
379  uint32_t bit, old;
380  struct dm_block *nb;
381  dm_block_t index = b;
382  struct disk_index_entry ie_disk;
383  void *bm_le;
384  int inc;
385 
386  bit = do_div(index, ll->entries_per_block);
387  r = ll->load_ie(ll, index, &ie_disk);
388  if (r < 0)
389  return r;
390 
391  r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr),
392  &dm_sm_bitmap_validator, &nb, &inc);
393  if (r < 0) {
394  DMERR("dm_tm_shadow_block() failed");
395  return r;
396  }
397  ie_disk.blocknr = cpu_to_le64(dm_block_location(nb));
398 
399  bm_le = dm_bitmap_data(nb);
400  old = sm_lookup_bitmap(bm_le, bit);
401 
402  if (ref_count <= 2) {
403  sm_set_bitmap(bm_le, bit, ref_count);
404 
405  r = dm_tm_unlock(ll->tm, nb);
406  if (r < 0)
407  return r;
408 
409  if (old > 2) {
411  ll->ref_count_root,
412  &b, &ll->ref_count_root);
413  if (r)
414  return r;
415  }
416 
417  } else {
418  __le32 le_rc = cpu_to_le32(ref_count);
419 
420  sm_set_bitmap(bm_le, bit, 3);
421  r = dm_tm_unlock(ll->tm, nb);
422  if (r < 0)
423  return r;
424 
425  __dm_bless_for_disk(&le_rc);
427  &b, &le_rc, &ll->ref_count_root);
428  if (r < 0) {
429  DMERR("ref count insert failed");
430  return r;
431  }
432  }
433 
434  if (ref_count && !old) {
435  *ev = SM_ALLOC;
436  ll->nr_allocated++;
437  le32_add_cpu(&ie_disk.nr_free, -1);
438  if (le32_to_cpu(ie_disk.none_free_before) == bit)
439  ie_disk.none_free_before = cpu_to_le32(bit + 1);
440 
441  } else if (old && !ref_count) {
442  *ev = SM_FREE;
443  ll->nr_allocated--;
444  le32_add_cpu(&ie_disk.nr_free, 1);
445  ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit));
446  }
447 
448  return ll->save_ie(ll, index, &ie_disk);
449 }
450 
451 int sm_ll_inc(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev)
452 {
453  int r;
454  uint32_t rc;
455 
456  r = sm_ll_lookup(ll, b, &rc);
457  if (r)
458  return r;
459 
460  return sm_ll_insert(ll, b, rc + 1, ev);
461 }
462 
463 int sm_ll_dec(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev)
464 {
465  int r;
466  uint32_t rc;
467 
468  r = sm_ll_lookup(ll, b, &rc);
469  if (r)
470  return r;
471 
472  if (!rc)
473  return -EINVAL;
474 
475  return sm_ll_insert(ll, b, rc - 1, ev);
476 }
477 
478 int sm_ll_commit(struct ll_disk *ll)
479 {
480  int r = 0;
481 
482  if (ll->bitmap_index_changed) {
483  r = ll->commit(ll);
484  if (!r)
485  ll->bitmap_index_changed = false;
486  }
487 
488  return r;
489 }
490 
491 /*----------------------------------------------------------------*/
492 
493 static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index,
494  struct disk_index_entry *ie)
495 {
496  memcpy(ie, ll->mi_le.index + index, sizeof(*ie));
497  return 0;
498 }
499 
500 static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index,
501  struct disk_index_entry *ie)
502 {
503  ll->bitmap_index_changed = true;
504  memcpy(ll->mi_le.index + index, ie, sizeof(*ie));
505  return 0;
506 }
507 
508 static int metadata_ll_init_index(struct ll_disk *ll)
509 {
510  int r;
511  struct dm_block *b;
512 
513  r = dm_tm_new_block(ll->tm, &index_validator, &b);
514  if (r < 0)
515  return r;
516 
517  memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
519 
520  return dm_tm_unlock(ll->tm, b);
521 }
522 
523 static int metadata_ll_open(struct ll_disk *ll)
524 {
525  int r;
526  struct dm_block *block;
527 
528  r = dm_tm_read_lock(ll->tm, ll->bitmap_root,
529  &index_validator, &block);
530  if (r)
531  return r;
532 
533  memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le));
534  return dm_tm_unlock(ll->tm, block);
535 }
536 
537 static dm_block_t metadata_ll_max_entries(struct ll_disk *ll)
538 {
539  return MAX_METADATA_BITMAPS;
540 }
541 
542 static int metadata_ll_commit(struct ll_disk *ll)
543 {
544  int r, inc;
545  struct dm_block *b;
546 
547  r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc);
548  if (r)
549  return r;
550 
551  memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le));
553 
554  return dm_tm_unlock(ll->tm, b);
555 }
556 
558 {
559  int r;
560 
561  r = sm_ll_init(ll, tm);
562  if (r < 0)
563  return r;
564 
565  ll->load_ie = metadata_ll_load_ie;
566  ll->save_ie = metadata_ll_save_ie;
567  ll->init_index = metadata_ll_init_index;
568  ll->open_index = metadata_ll_open;
569  ll->max_entries = metadata_ll_max_entries;
570  ll->commit = metadata_ll_commit;
571 
572  ll->nr_blocks = 0;
573  ll->nr_allocated = 0;
574 
575  r = ll->init_index(ll);
576  if (r < 0)
577  return r;
578 
580  if (r < 0)
581  return r;
582 
583  return 0;
584 }
585 
587  void *root_le, size_t len)
588 {
589  int r;
590  struct disk_sm_root *smr = root_le;
591 
592  if (len < sizeof(struct disk_sm_root)) {
593  DMERR("sm_metadata root too small");
594  return -ENOMEM;
595  }
596 
597  r = sm_ll_init(ll, tm);
598  if (r < 0)
599  return r;
600 
601  ll->load_ie = metadata_ll_load_ie;
602  ll->save_ie = metadata_ll_save_ie;
603  ll->init_index = metadata_ll_init_index;
604  ll->open_index = metadata_ll_open;
605  ll->max_entries = metadata_ll_max_entries;
606  ll->commit = metadata_ll_commit;
607 
608  ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
610  ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
612 
613  return ll->open_index(ll);
614 }
615 
616 /*----------------------------------------------------------------*/
617 
618 static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index,
619  struct disk_index_entry *ie)
620 {
621  return dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie);
622 }
623 
624 static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index,
625  struct disk_index_entry *ie)
626 {
628  return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root,
629  &index, ie, &ll->bitmap_root);
630 }
631 
632 static int disk_ll_init_index(struct ll_disk *ll)
633 {
634  return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root);
635 }
636 
637 static int disk_ll_open(struct ll_disk *ll)
638 {
639  /* nothing to do */
640  return 0;
641 }
642 
643 static dm_block_t disk_ll_max_entries(struct ll_disk *ll)
644 {
645  return -1ULL;
646 }
647 
648 static int disk_ll_commit(struct ll_disk *ll)
649 {
650  return 0;
651 }
652 
653 int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm)
654 {
655  int r;
656 
657  r = sm_ll_init(ll, tm);
658  if (r < 0)
659  return r;
660 
661  ll->load_ie = disk_ll_load_ie;
662  ll->save_ie = disk_ll_save_ie;
663  ll->init_index = disk_ll_init_index;
664  ll->open_index = disk_ll_open;
665  ll->max_entries = disk_ll_max_entries;
666  ll->commit = disk_ll_commit;
667 
668  ll->nr_blocks = 0;
669  ll->nr_allocated = 0;
670 
671  r = ll->init_index(ll);
672  if (r < 0)
673  return r;
674 
676  if (r < 0)
677  return r;
678 
679  return 0;
680 }
681 
682 int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm,
683  void *root_le, size_t len)
684 {
685  int r;
686  struct disk_sm_root *smr = root_le;
687 
688  if (len < sizeof(struct disk_sm_root)) {
689  DMERR("sm_metadata root too small");
690  return -ENOMEM;
691  }
692 
693  r = sm_ll_init(ll, tm);
694  if (r < 0)
695  return r;
696 
697  ll->load_ie = disk_ll_load_ie;
698  ll->save_ie = disk_ll_save_ie;
699  ll->init_index = disk_ll_init_index;
700  ll->open_index = disk_ll_open;
701  ll->max_entries = disk_ll_max_entries;
702  ll->commit = disk_ll_commit;
703 
704  ll->nr_blocks = le64_to_cpu(smr->nr_blocks);
706  ll->bitmap_root = le64_to_cpu(smr->bitmap_root);
708 
709  return ll->open_index(ll);
710 }
711 
712 /*----------------------------------------------------------------*/