dm thin metadata: THIN_MAX_CONCURRENT_LOCKS should be 6
[pandora-kernel.git] / drivers / md / dm-thin-metadata.c
1 /*
2  * Copyright (C) 2011 Red Hat, Inc.
3  *
4  * This file is released under the GPL.
5  */
6
7 #include "dm-thin-metadata.h"
8 #include "persistent-data/dm-btree.h"
9 #include "persistent-data/dm-space-map.h"
10 #include "persistent-data/dm-space-map-disk.h"
11 #include "persistent-data/dm-transaction-manager.h"
12
13 #include <linux/list.h>
14 #include <linux/device-mapper.h>
15 #include <linux/workqueue.h>
16
17 /*--------------------------------------------------------------------------
18  * As far as the metadata goes, there is:
19  *
20  * - A superblock in block zero, taking up fewer than 512 bytes for
21  *   atomic writes.
22  *
23  * - A space map managing the metadata blocks.
24  *
25  * - A space map managing the data blocks.
26  *
27  * - A btree mapping our internal thin dev ids onto struct disk_device_details.
28  *
29  * - A hierarchical btree, with 2 levels which effectively maps (thin
30  *   dev id, virtual block) -> block_time.  Block time is a 64-bit
31  *   field holding the time in the low 24 bits, and block in the top 48
32  *   bits.
33  *
34  * BTrees consist solely of btree_nodes, that fill a block.  Some are
35  * internal nodes, as such their values are a __le64 pointing to other
36  * nodes.  Leaf nodes can store data of any reasonable size (ie. much
37  * smaller than the block size).  The nodes consist of the header,
38  * followed by an array of keys, followed by an array of values.  We have
39  * to binary search on the keys so they're all held together to help the
40  * cpu cache.
41  *
42  * Space maps have 2 btrees:
43  *
44  * - One maps a uint64_t onto a struct index_entry.  Which points to a
45  *   bitmap block, and has some details about how many free entries there
46  *   are etc.
47  *
48  * - The bitmap blocks have a header (for the checksum).  Then the rest
49  *   of the block is pairs of bits.  With the meaning being:
50  *
51  *   0 - ref count is 0
52  *   1 - ref count is 1
53  *   2 - ref count is 2
54  *   3 - ref count is higher than 2
55  *
56  * - If the count is higher than 2 then the ref count is entered in a
57  *   second btree that directly maps the block_address to a uint32_t ref
58  *   count.
59  *
60  * The space map metadata variant doesn't have a bitmaps btree.  Instead
61  * it has one single blocks worth of index_entries.  This avoids
62  * recursive issues with the bitmap btree needing to allocate space in
63  * order to insert.  With a small data block size such as 64k the
64  * metadata support data devices that are hundreds of terrabytes.
65  *
66  * The space maps allocate space linearly from front to back.  Space that
67  * is freed in a transaction is never recycled within that transaction.
68  * To try and avoid fragmenting _free_ space the allocator always goes
69  * back and fills in gaps.
70  *
71  * All metadata io is in THIN_METADATA_BLOCK_SIZE sized/aligned chunks
72  * from the block manager.
73  *--------------------------------------------------------------------------*/
74
75 #define DM_MSG_PREFIX   "thin metadata"
76
77 #define THIN_SUPERBLOCK_MAGIC 27022010
78 #define THIN_SUPERBLOCK_LOCATION 0
79 #define THIN_VERSION 1
80 #define THIN_METADATA_CACHE_SIZE 64
81 #define SECTOR_TO_BLOCK_SHIFT 3
82
83 /*
84  * For btree insert:
85  *  3 for btree insert +
86  *  2 for btree lookup used within space map
87  * For btree remove:
88  *  2 for shadow spine +
89  *  4 for rebalance 3 child node
90  */
91 #define THIN_MAX_CONCURRENT_LOCKS 6
92
93 /* This should be plenty */
94 #define SPACE_MAP_ROOT_SIZE 128
95
96 /*
97  * Little endian on-disk superblock and device details.
98  */
99 struct thin_disk_superblock {
100         __le32 csum;    /* Checksum of superblock except for this field. */
101         __le32 flags;
102         __le64 blocknr; /* This block number, dm_block_t. */
103
104         __u8 uuid[16];
105         __le64 magic;
106         __le32 version;
107         __le32 time;
108
109         __le64 trans_id;
110
111         /*
112          * Root held by userspace transactions.
113          */
114         __le64 held_root;
115
116         __u8 data_space_map_root[SPACE_MAP_ROOT_SIZE];
117         __u8 metadata_space_map_root[SPACE_MAP_ROOT_SIZE];
118
119         /*
120          * 2-level btree mapping (dev_id, (dev block, time)) -> data block
121          */
122         __le64 data_mapping_root;
123
124         /*
125          * Device detail root mapping dev_id -> device_details
126          */
127         __le64 device_details_root;
128
129         __le32 data_block_size;         /* In 512-byte sectors. */
130
131         __le32 metadata_block_size;     /* In 512-byte sectors. */
132         __le64 metadata_nr_blocks;
133
134         __le32 compat_flags;
135         __le32 compat_ro_flags;
136         __le32 incompat_flags;
137 } __packed;
138
139 struct disk_device_details {
140         __le64 mapped_blocks;
141         __le64 transaction_id;          /* When created. */
142         __le32 creation_time;
143         __le32 snapshotted_time;
144 } __packed;
145
146 struct dm_pool_metadata {
147         struct hlist_node hash;
148
149         struct block_device *bdev;
150         struct dm_block_manager *bm;
151         struct dm_space_map *metadata_sm;
152         struct dm_space_map *data_sm;
153         struct dm_transaction_manager *tm;
154         struct dm_transaction_manager *nb_tm;
155
156         /*
157          * Two-level btree.
158          * First level holds thin_dev_t.
159          * Second level holds mappings.
160          */
161         struct dm_btree_info info;
162
163         /*
164          * Non-blocking version of the above.
165          */
166         struct dm_btree_info nb_info;
167
168         /*
169          * Just the top level for deleting whole devices.
170          */
171         struct dm_btree_info tl_info;
172
173         /*
174          * Just the bottom level for creating new devices.
175          */
176         struct dm_btree_info bl_info;
177
178         /*
179          * Describes the device details btree.
180          */
181         struct dm_btree_info details_info;
182
183         struct rw_semaphore root_lock;
184         uint32_t time;
185         int need_commit;
186         dm_block_t root;
187         dm_block_t details_root;
188         struct list_head thin_devices;
189         uint64_t trans_id;
190         unsigned long flags;
191         sector_t data_block_size;
192 };
193
194 struct dm_thin_device {
195         struct list_head list;
196         struct dm_pool_metadata *pmd;
197         dm_thin_id id;
198
199         int open_count;
200         int changed;
201         uint64_t mapped_blocks;
202         uint64_t transaction_id;
203         uint32_t creation_time;
204         uint32_t snapshotted_time;
205 };
206
207 /*----------------------------------------------------------------
208  * superblock validator
209  *--------------------------------------------------------------*/
210
211 #define SUPERBLOCK_CSUM_XOR 160774
212
213 static void sb_prepare_for_write(struct dm_block_validator *v,
214                                  struct dm_block *b,
215                                  size_t block_size)
216 {
217         struct thin_disk_superblock *disk_super = dm_block_data(b);
218
219         disk_super->blocknr = cpu_to_le64(dm_block_location(b));
220         disk_super->csum = cpu_to_le32(dm_bm_checksum(&disk_super->flags,
221                                                       block_size - sizeof(__le32),
222                                                       SUPERBLOCK_CSUM_XOR));
223 }
224
225 static int sb_check(struct dm_block_validator *v,
226                     struct dm_block *b,
227                     size_t block_size)
228 {
229         struct thin_disk_superblock *disk_super = dm_block_data(b);
230         __le32 csum_le;
231
232         if (dm_block_location(b) != le64_to_cpu(disk_super->blocknr)) {
233                 DMERR("sb_check failed: blocknr %llu: "
234                       "wanted %llu", le64_to_cpu(disk_super->blocknr),
235                       (unsigned long long)dm_block_location(b));
236                 return -ENOTBLK;
237         }
238
239         if (le64_to_cpu(disk_super->magic) != THIN_SUPERBLOCK_MAGIC) {
240                 DMERR("sb_check failed: magic %llu: "
241                       "wanted %llu", le64_to_cpu(disk_super->magic),
242                       (unsigned long long)THIN_SUPERBLOCK_MAGIC);
243                 return -EILSEQ;
244         }
245
246         csum_le = cpu_to_le32(dm_bm_checksum(&disk_super->flags,
247                                              block_size - sizeof(__le32),
248                                              SUPERBLOCK_CSUM_XOR));
249         if (csum_le != disk_super->csum) {
250                 DMERR("sb_check failed: csum %u: wanted %u",
251                       le32_to_cpu(csum_le), le32_to_cpu(disk_super->csum));
252                 return -EILSEQ;
253         }
254
255         return 0;
256 }
257
258 static struct dm_block_validator sb_validator = {
259         .name = "superblock",
260         .prepare_for_write = sb_prepare_for_write,
261         .check = sb_check
262 };
263
264 /*----------------------------------------------------------------
265  * Methods for the btree value types
266  *--------------------------------------------------------------*/
267
268 static uint64_t pack_block_time(dm_block_t b, uint32_t t)
269 {
270         return (b << 24) | t;
271 }
272
273 static void unpack_block_time(uint64_t v, dm_block_t *b, uint32_t *t)
274 {
275         *b = v >> 24;
276         *t = v & ((1 << 24) - 1);
277 }
278
279 static void data_block_inc(void *context, void *value_le)
280 {
281         struct dm_space_map *sm = context;
282         __le64 v_le;
283         uint64_t b;
284         uint32_t t;
285
286         memcpy(&v_le, value_le, sizeof(v_le));
287         unpack_block_time(le64_to_cpu(v_le), &b, &t);
288         dm_sm_inc_block(sm, b);
289 }
290
291 static void data_block_dec(void *context, void *value_le)
292 {
293         struct dm_space_map *sm = context;
294         __le64 v_le;
295         uint64_t b;
296         uint32_t t;
297
298         memcpy(&v_le, value_le, sizeof(v_le));
299         unpack_block_time(le64_to_cpu(v_le), &b, &t);
300         dm_sm_dec_block(sm, b);
301 }
302
303 static int data_block_equal(void *context, void *value1_le, void *value2_le)
304 {
305         __le64 v1_le, v2_le;
306         uint64_t b1, b2;
307         uint32_t t;
308
309         memcpy(&v1_le, value1_le, sizeof(v1_le));
310         memcpy(&v2_le, value2_le, sizeof(v2_le));
311         unpack_block_time(le64_to_cpu(v1_le), &b1, &t);
312         unpack_block_time(le64_to_cpu(v2_le), &b2, &t);
313
314         return b1 == b2;
315 }
316
317 static void subtree_inc(void *context, void *value)
318 {
319         struct dm_btree_info *info = context;
320         __le64 root_le;
321         uint64_t root;
322
323         memcpy(&root_le, value, sizeof(root_le));
324         root = le64_to_cpu(root_le);
325         dm_tm_inc(info->tm, root);
326 }
327
328 static void subtree_dec(void *context, void *value)
329 {
330         struct dm_btree_info *info = context;
331         __le64 root_le;
332         uint64_t root;
333
334         memcpy(&root_le, value, sizeof(root_le));
335         root = le64_to_cpu(root_le);
336         if (dm_btree_del(info, root))
337                 DMERR("btree delete failed\n");
338 }
339
340 static int subtree_equal(void *context, void *value1_le, void *value2_le)
341 {
342         __le64 v1_le, v2_le;
343         memcpy(&v1_le, value1_le, sizeof(v1_le));
344         memcpy(&v2_le, value2_le, sizeof(v2_le));
345
346         return v1_le == v2_le;
347 }
348
349 /*----------------------------------------------------------------*/
350
351 static int superblock_all_zeroes(struct dm_block_manager *bm, int *result)
352 {
353         int r;
354         unsigned i;
355         struct dm_block *b;
356         __le64 *data_le, zero = cpu_to_le64(0);
357         unsigned block_size = dm_bm_block_size(bm) / sizeof(__le64);
358
359         /*
360          * We can't use a validator here - it may be all zeroes.
361          */
362         r = dm_bm_read_lock(bm, THIN_SUPERBLOCK_LOCATION, NULL, &b);
363         if (r)
364                 return r;
365
366         data_le = dm_block_data(b);
367         *result = 1;
368         for (i = 0; i < block_size; i++) {
369                 if (data_le[i] != zero) {
370                         *result = 0;
371                         break;
372                 }
373         }
374
375         return dm_bm_unlock(b);
376 }
377
378 static int init_pmd(struct dm_pool_metadata *pmd,
379                     struct dm_block_manager *bm,
380                     dm_block_t nr_blocks, int create)
381 {
382         int r;
383         struct dm_space_map *sm, *data_sm;
384         struct dm_transaction_manager *tm;
385         struct dm_block *sblock;
386
387         if (create) {
388                 r = dm_tm_create_with_sm(bm, THIN_SUPERBLOCK_LOCATION,
389                                          &sb_validator, &tm, &sm, &sblock);
390                 if (r < 0) {
391                         DMERR("tm_create_with_sm failed");
392                         return r;
393                 }
394
395                 data_sm = dm_sm_disk_create(tm, nr_blocks);
396                 if (IS_ERR(data_sm)) {
397                         DMERR("sm_disk_create failed");
398                         dm_tm_unlock(tm, sblock);
399                         r = PTR_ERR(data_sm);
400                         goto bad;
401                 }
402         } else {
403                 struct thin_disk_superblock *disk_super = NULL;
404                 size_t space_map_root_offset =
405                         offsetof(struct thin_disk_superblock, metadata_space_map_root);
406
407                 r = dm_tm_open_with_sm(bm, THIN_SUPERBLOCK_LOCATION,
408                                        &sb_validator, space_map_root_offset,
409                                        SPACE_MAP_ROOT_SIZE, &tm, &sm, &sblock);
410                 if (r < 0) {
411                         DMERR("tm_open_with_sm failed");
412                         return r;
413                 }
414
415                 disk_super = dm_block_data(sblock);
416                 data_sm = dm_sm_disk_open(tm, disk_super->data_space_map_root,
417                                           sizeof(disk_super->data_space_map_root));
418                 if (IS_ERR(data_sm)) {
419                         DMERR("sm_disk_open failed");
420                         r = PTR_ERR(data_sm);
421                         goto bad;
422                 }
423         }
424
425
426         r = dm_tm_unlock(tm, sblock);
427         if (r < 0) {
428                 DMERR("couldn't unlock superblock");
429                 goto bad_data_sm;
430         }
431
432         pmd->bm = bm;
433         pmd->metadata_sm = sm;
434         pmd->data_sm = data_sm;
435         pmd->tm = tm;
436         pmd->nb_tm = dm_tm_create_non_blocking_clone(tm);
437         if (!pmd->nb_tm) {
438                 DMERR("could not create clone tm");
439                 r = -ENOMEM;
440                 goto bad_data_sm;
441         }
442
443         pmd->info.tm = tm;
444         pmd->info.levels = 2;
445         pmd->info.value_type.context = pmd->data_sm;
446         pmd->info.value_type.size = sizeof(__le64);
447         pmd->info.value_type.inc = data_block_inc;
448         pmd->info.value_type.dec = data_block_dec;
449         pmd->info.value_type.equal = data_block_equal;
450
451         memcpy(&pmd->nb_info, &pmd->info, sizeof(pmd->nb_info));
452         pmd->nb_info.tm = pmd->nb_tm;
453
454         pmd->tl_info.tm = tm;
455         pmd->tl_info.levels = 1;
456         pmd->tl_info.value_type.context = &pmd->info;
457         pmd->tl_info.value_type.size = sizeof(__le64);
458         pmd->tl_info.value_type.inc = subtree_inc;
459         pmd->tl_info.value_type.dec = subtree_dec;
460         pmd->tl_info.value_type.equal = subtree_equal;
461
462         pmd->bl_info.tm = tm;
463         pmd->bl_info.levels = 1;
464         pmd->bl_info.value_type.context = pmd->data_sm;
465         pmd->bl_info.value_type.size = sizeof(__le64);
466         pmd->bl_info.value_type.inc = data_block_inc;
467         pmd->bl_info.value_type.dec = data_block_dec;
468         pmd->bl_info.value_type.equal = data_block_equal;
469
470         pmd->details_info.tm = tm;
471         pmd->details_info.levels = 1;
472         pmd->details_info.value_type.context = NULL;
473         pmd->details_info.value_type.size = sizeof(struct disk_device_details);
474         pmd->details_info.value_type.inc = NULL;
475         pmd->details_info.value_type.dec = NULL;
476         pmd->details_info.value_type.equal = NULL;
477
478         pmd->root = 0;
479
480         init_rwsem(&pmd->root_lock);
481         pmd->time = 0;
482         pmd->need_commit = 0;
483         pmd->details_root = 0;
484         pmd->trans_id = 0;
485         pmd->flags = 0;
486         INIT_LIST_HEAD(&pmd->thin_devices);
487
488         return 0;
489
490 bad_data_sm:
491         dm_sm_destroy(data_sm);
492 bad:
493         dm_tm_destroy(tm);
494         dm_sm_destroy(sm);
495
496         return r;
497 }
498
499 static int __begin_transaction(struct dm_pool_metadata *pmd)
500 {
501         int r;
502         u32 features;
503         struct thin_disk_superblock *disk_super;
504         struct dm_block *sblock;
505
506         /*
507          * __maybe_commit_transaction() resets these
508          */
509         WARN_ON(pmd->need_commit);
510
511         /*
512          * We re-read the superblock every time.  Shouldn't need to do this
513          * really.
514          */
515         r = dm_bm_read_lock(pmd->bm, THIN_SUPERBLOCK_LOCATION,
516                             &sb_validator, &sblock);
517         if (r)
518                 return r;
519
520         disk_super = dm_block_data(sblock);
521         pmd->time = le32_to_cpu(disk_super->time);
522         pmd->root = le64_to_cpu(disk_super->data_mapping_root);
523         pmd->details_root = le64_to_cpu(disk_super->device_details_root);
524         pmd->trans_id = le64_to_cpu(disk_super->trans_id);
525         pmd->flags = le32_to_cpu(disk_super->flags);
526         pmd->data_block_size = le32_to_cpu(disk_super->data_block_size);
527
528         features = le32_to_cpu(disk_super->incompat_flags) & ~THIN_FEATURE_INCOMPAT_SUPP;
529         if (features) {
530                 DMERR("could not access metadata due to "
531                       "unsupported optional features (%lx).",
532                       (unsigned long)features);
533                 r = -EINVAL;
534                 goto out;
535         }
536
537         /*
538          * Check for read-only metadata to skip the following RDWR checks.
539          */
540         if (get_disk_ro(pmd->bdev->bd_disk))
541                 goto out;
542
543         features = le32_to_cpu(disk_super->compat_ro_flags) & ~THIN_FEATURE_COMPAT_RO_SUPP;
544         if (features) {
545                 DMERR("could not access metadata RDWR due to "
546                       "unsupported optional features (%lx).",
547                       (unsigned long)features);
548                 r = -EINVAL;
549         }
550
551 out:
552         dm_bm_unlock(sblock);
553         return r;
554 }
555
556 static int __write_changed_details(struct dm_pool_metadata *pmd)
557 {
558         int r;
559         struct dm_thin_device *td, *tmp;
560         struct disk_device_details details;
561         uint64_t key;
562
563         list_for_each_entry_safe(td, tmp, &pmd->thin_devices, list) {
564                 if (!td->changed)
565                         continue;
566
567                 key = td->id;
568
569                 details.mapped_blocks = cpu_to_le64(td->mapped_blocks);
570                 details.transaction_id = cpu_to_le64(td->transaction_id);
571                 details.creation_time = cpu_to_le32(td->creation_time);
572                 details.snapshotted_time = cpu_to_le32(td->snapshotted_time);
573                 __dm_bless_for_disk(&details);
574
575                 r = dm_btree_insert(&pmd->details_info, pmd->details_root,
576                                     &key, &details, &pmd->details_root);
577                 if (r)
578                         return r;
579
580                 if (td->open_count)
581                         td->changed = 0;
582                 else {
583                         list_del(&td->list);
584                         kfree(td);
585                 }
586
587                 pmd->need_commit = 1;
588         }
589
590         return 0;
591 }
592
593 static int __commit_transaction(struct dm_pool_metadata *pmd)
594 {
595         /*
596          * FIXME: Associated pool should be made read-only on failure.
597          */
598         int r;
599         size_t metadata_len, data_len;
600         struct thin_disk_superblock *disk_super;
601         struct dm_block *sblock;
602
603         /*
604          * We need to know if the thin_disk_superblock exceeds a 512-byte sector.
605          */
606         BUILD_BUG_ON(sizeof(struct thin_disk_superblock) > 512);
607
608         r = __write_changed_details(pmd);
609         if (r < 0)
610                 goto out;
611
612         if (!pmd->need_commit)
613                 goto out;
614
615         r = dm_sm_commit(pmd->data_sm);
616         if (r < 0)
617                 goto out;
618
619         r = dm_tm_pre_commit(pmd->tm);
620         if (r < 0)
621                 goto out;
622
623         r = dm_sm_root_size(pmd->metadata_sm, &metadata_len);
624         if (r < 0)
625                 goto out;
626
627         r = dm_sm_root_size(pmd->metadata_sm, &data_len);
628         if (r < 0)
629                 goto out;
630
631         r = dm_bm_write_lock(pmd->bm, THIN_SUPERBLOCK_LOCATION,
632                              &sb_validator, &sblock);
633         if (r)
634                 goto out;
635
636         disk_super = dm_block_data(sblock);
637         disk_super->time = cpu_to_le32(pmd->time);
638         disk_super->data_mapping_root = cpu_to_le64(pmd->root);
639         disk_super->device_details_root = cpu_to_le64(pmd->details_root);
640         disk_super->trans_id = cpu_to_le64(pmd->trans_id);
641         disk_super->flags = cpu_to_le32(pmd->flags);
642
643         r = dm_sm_copy_root(pmd->metadata_sm, &disk_super->metadata_space_map_root,
644                             metadata_len);
645         if (r < 0)
646                 goto out_locked;
647
648         r = dm_sm_copy_root(pmd->data_sm, &disk_super->data_space_map_root,
649                             data_len);
650         if (r < 0)
651                 goto out_locked;
652
653         r = dm_tm_commit(pmd->tm, sblock);
654         if (!r)
655                 pmd->need_commit = 0;
656
657 out:
658         return r;
659
660 out_locked:
661         dm_bm_unlock(sblock);
662         return r;
663 }
664
665 struct dm_pool_metadata *dm_pool_metadata_open(struct block_device *bdev,
666                                                sector_t data_block_size)
667 {
668         int r;
669         struct thin_disk_superblock *disk_super;
670         struct dm_pool_metadata *pmd;
671         sector_t bdev_size = i_size_read(bdev->bd_inode) >> SECTOR_SHIFT;
672         struct dm_block_manager *bm;
673         int create;
674         struct dm_block *sblock;
675
676         pmd = kmalloc(sizeof(*pmd), GFP_KERNEL);
677         if (!pmd) {
678                 DMERR("could not allocate metadata struct");
679                 return ERR_PTR(-ENOMEM);
680         }
681
682         bm = dm_block_manager_create(bdev, THIN_METADATA_BLOCK_SIZE,
683                                      THIN_METADATA_CACHE_SIZE,
684                                      THIN_MAX_CONCURRENT_LOCKS);
685         if (!bm) {
686                 DMERR("could not create block manager");
687                 kfree(pmd);
688                 return ERR_PTR(-ENOMEM);
689         }
690
691         r = superblock_all_zeroes(bm, &create);
692         if (r) {
693                 dm_block_manager_destroy(bm);
694                 kfree(pmd);
695                 return ERR_PTR(r);
696         }
697
698
699         r = init_pmd(pmd, bm, 0, create);
700         if (r) {
701                 dm_block_manager_destroy(bm);
702                 kfree(pmd);
703                 return ERR_PTR(r);
704         }
705         pmd->bdev = bdev;
706
707         if (!create) {
708                 r = __begin_transaction(pmd);
709                 if (r < 0)
710                         goto bad;
711                 return pmd;
712         }
713
714         /*
715          * Create.
716          */
717         r = dm_bm_write_lock(pmd->bm, THIN_SUPERBLOCK_LOCATION,
718                              &sb_validator, &sblock);
719         if (r)
720                 goto bad;
721
722         disk_super = dm_block_data(sblock);
723         disk_super->magic = cpu_to_le64(THIN_SUPERBLOCK_MAGIC);
724         disk_super->version = cpu_to_le32(THIN_VERSION);
725         disk_super->time = 0;
726         disk_super->metadata_block_size = cpu_to_le32(THIN_METADATA_BLOCK_SIZE >> SECTOR_SHIFT);
727         disk_super->metadata_nr_blocks = cpu_to_le64(bdev_size >> SECTOR_TO_BLOCK_SHIFT);
728         disk_super->data_block_size = cpu_to_le32(data_block_size);
729
730         r = dm_bm_unlock(sblock);
731         if (r < 0)
732                 goto bad;
733
734         r = dm_btree_empty(&pmd->info, &pmd->root);
735         if (r < 0)
736                 goto bad;
737
738         r = dm_btree_empty(&pmd->details_info, &pmd->details_root);
739         if (r < 0) {
740                 DMERR("couldn't create devices root");
741                 goto bad;
742         }
743
744         pmd->flags = 0;
745         pmd->need_commit = 1;
746         r = dm_pool_commit_metadata(pmd);
747         if (r < 0) {
748                 DMERR("%s: dm_pool_commit_metadata() failed, error = %d",
749                       __func__, r);
750                 goto bad;
751         }
752
753         return pmd;
754
755 bad:
756         if (dm_pool_metadata_close(pmd) < 0)
757                 DMWARN("%s: dm_pool_metadata_close() failed.", __func__);
758         return ERR_PTR(r);
759 }
760
761 int dm_pool_metadata_close(struct dm_pool_metadata *pmd)
762 {
763         int r;
764         unsigned open_devices = 0;
765         struct dm_thin_device *td, *tmp;
766
767         down_read(&pmd->root_lock);
768         list_for_each_entry_safe(td, tmp, &pmd->thin_devices, list) {
769                 if (td->open_count)
770                         open_devices++;
771                 else {
772                         list_del(&td->list);
773                         kfree(td);
774                 }
775         }
776         up_read(&pmd->root_lock);
777
778         if (open_devices) {
779                 DMERR("attempt to close pmd when %u device(s) are still open",
780                        open_devices);
781                 return -EBUSY;
782         }
783
784         r = __commit_transaction(pmd);
785         if (r < 0)
786                 DMWARN("%s: __commit_transaction() failed, error = %d",
787                        __func__, r);
788
789         dm_tm_destroy(pmd->tm);
790         dm_tm_destroy(pmd->nb_tm);
791         dm_block_manager_destroy(pmd->bm);
792         dm_sm_destroy(pmd->metadata_sm);
793         dm_sm_destroy(pmd->data_sm);
794         kfree(pmd);
795
796         return 0;
797 }
798
799 /*
800  * __open_device: Returns @td corresponding to device with id @dev,
801  * creating it if @create is set and incrementing @td->open_count.
802  * On failure, @td is undefined.
803  */
804 static int __open_device(struct dm_pool_metadata *pmd,
805                          dm_thin_id dev, int create,
806                          struct dm_thin_device **td)
807 {
808         int r, changed = 0;
809         struct dm_thin_device *td2;
810         uint64_t key = dev;
811         struct disk_device_details details_le;
812
813         /*
814          * If the device is already open, return it.
815          */
816         list_for_each_entry(td2, &pmd->thin_devices, list)
817                 if (td2->id == dev) {
818                         /*
819                          * May not create an already-open device.
820                          */
821                         if (create)
822                                 return -EEXIST;
823
824                         td2->open_count++;
825                         *td = td2;
826                         return 0;
827                 }
828
829         /*
830          * Check the device exists.
831          */
832         r = dm_btree_lookup(&pmd->details_info, pmd->details_root,
833                             &key, &details_le);
834         if (r) {
835                 if (r != -ENODATA || !create)
836                         return r;
837
838                 /*
839                  * Create new device.
840                  */
841                 changed = 1;
842                 details_le.mapped_blocks = 0;
843                 details_le.transaction_id = cpu_to_le64(pmd->trans_id);
844                 details_le.creation_time = cpu_to_le32(pmd->time);
845                 details_le.snapshotted_time = cpu_to_le32(pmd->time);
846         }
847
848         *td = kmalloc(sizeof(**td), GFP_NOIO);
849         if (!*td)
850                 return -ENOMEM;
851
852         (*td)->pmd = pmd;
853         (*td)->id = dev;
854         (*td)->open_count = 1;
855         (*td)->changed = changed;
856         (*td)->mapped_blocks = le64_to_cpu(details_le.mapped_blocks);
857         (*td)->transaction_id = le64_to_cpu(details_le.transaction_id);
858         (*td)->creation_time = le32_to_cpu(details_le.creation_time);
859         (*td)->snapshotted_time = le32_to_cpu(details_le.snapshotted_time);
860
861         list_add(&(*td)->list, &pmd->thin_devices);
862
863         return 0;
864 }
865
866 static void __close_device(struct dm_thin_device *td)
867 {
868         --td->open_count;
869 }
870
871 static int __create_thin(struct dm_pool_metadata *pmd,
872                          dm_thin_id dev)
873 {
874         int r;
875         dm_block_t dev_root;
876         uint64_t key = dev;
877         struct disk_device_details details_le;
878         struct dm_thin_device *td;
879         __le64 value;
880
881         r = dm_btree_lookup(&pmd->details_info, pmd->details_root,
882                             &key, &details_le);
883         if (!r)
884                 return -EEXIST;
885
886         /*
887          * Create an empty btree for the mappings.
888          */
889         r = dm_btree_empty(&pmd->bl_info, &dev_root);
890         if (r)
891                 return r;
892
893         /*
894          * Insert it into the main mapping tree.
895          */
896         value = cpu_to_le64(dev_root);
897         __dm_bless_for_disk(&value);
898         r = dm_btree_insert(&pmd->tl_info, pmd->root, &key, &value, &pmd->root);
899         if (r) {
900                 dm_btree_del(&pmd->bl_info, dev_root);
901                 return r;
902         }
903
904         r = __open_device(pmd, dev, 1, &td);
905         if (r) {
906                 dm_btree_remove(&pmd->tl_info, pmd->root, &key, &pmd->root);
907                 dm_btree_del(&pmd->bl_info, dev_root);
908                 return r;
909         }
910         __close_device(td);
911
912         return r;
913 }
914
915 int dm_pool_create_thin(struct dm_pool_metadata *pmd, dm_thin_id dev)
916 {
917         int r;
918
919         down_write(&pmd->root_lock);
920         r = __create_thin(pmd, dev);
921         up_write(&pmd->root_lock);
922
923         return r;
924 }
925
926 static int __set_snapshot_details(struct dm_pool_metadata *pmd,
927                                   struct dm_thin_device *snap,
928                                   dm_thin_id origin, uint32_t time)
929 {
930         int r;
931         struct dm_thin_device *td;
932
933         r = __open_device(pmd, origin, 0, &td);
934         if (r)
935                 return r;
936
937         td->changed = 1;
938         td->snapshotted_time = time;
939
940         snap->mapped_blocks = td->mapped_blocks;
941         snap->snapshotted_time = time;
942         __close_device(td);
943
944         return 0;
945 }
946
947 static int __create_snap(struct dm_pool_metadata *pmd,
948                          dm_thin_id dev, dm_thin_id origin)
949 {
950         int r;
951         dm_block_t origin_root;
952         uint64_t key = origin, dev_key = dev;
953         struct dm_thin_device *td;
954         struct disk_device_details details_le;
955         __le64 value;
956
957         /* check this device is unused */
958         r = dm_btree_lookup(&pmd->details_info, pmd->details_root,
959                             &dev_key, &details_le);
960         if (!r)
961                 return -EEXIST;
962
963         /* find the mapping tree for the origin */
964         r = dm_btree_lookup(&pmd->tl_info, pmd->root, &key, &value);
965         if (r)
966                 return r;
967         origin_root = le64_to_cpu(value);
968
969         /* clone the origin, an inc will do */
970         dm_tm_inc(pmd->tm, origin_root);
971
972         /* insert into the main mapping tree */
973         value = cpu_to_le64(origin_root);
974         __dm_bless_for_disk(&value);
975         key = dev;
976         r = dm_btree_insert(&pmd->tl_info, pmd->root, &key, &value, &pmd->root);
977         if (r) {
978                 dm_tm_dec(pmd->tm, origin_root);
979                 return r;
980         }
981
982         pmd->time++;
983
984         r = __open_device(pmd, dev, 1, &td);
985         if (r)
986                 goto bad;
987
988         r = __set_snapshot_details(pmd, td, origin, pmd->time);
989         __close_device(td);
990
991         if (r)
992                 goto bad;
993
994         return 0;
995
996 bad:
997         dm_btree_remove(&pmd->tl_info, pmd->root, &key, &pmd->root);
998         dm_btree_remove(&pmd->details_info, pmd->details_root,
999                         &key, &pmd->details_root);
1000         return r;
1001 }
1002
1003 int dm_pool_create_snap(struct dm_pool_metadata *pmd,
1004                                  dm_thin_id dev,
1005                                  dm_thin_id origin)
1006 {
1007         int r;
1008
1009         down_write(&pmd->root_lock);
1010         r = __create_snap(pmd, dev, origin);
1011         up_write(&pmd->root_lock);
1012
1013         return r;
1014 }
1015
1016 static int __delete_device(struct dm_pool_metadata *pmd, dm_thin_id dev)
1017 {
1018         int r;
1019         uint64_t key = dev;
1020         struct dm_thin_device *td;
1021
1022         /* TODO: failure should mark the transaction invalid */
1023         r = __open_device(pmd, dev, 0, &td);
1024         if (r)
1025                 return r;
1026
1027         if (td->open_count > 1) {
1028                 __close_device(td);
1029                 return -EBUSY;
1030         }
1031
1032         list_del(&td->list);
1033         kfree(td);
1034         r = dm_btree_remove(&pmd->details_info, pmd->details_root,
1035                             &key, &pmd->details_root);
1036         if (r)
1037                 return r;
1038
1039         r = dm_btree_remove(&pmd->tl_info, pmd->root, &key, &pmd->root);
1040         if (r)
1041                 return r;
1042
1043         pmd->need_commit = 1;
1044
1045         return 0;
1046 }
1047
1048 int dm_pool_delete_thin_device(struct dm_pool_metadata *pmd,
1049                                dm_thin_id dev)
1050 {
1051         int r;
1052
1053         down_write(&pmd->root_lock);
1054         r = __delete_device(pmd, dev);
1055         up_write(&pmd->root_lock);
1056
1057         return r;
1058 }
1059
1060 int dm_pool_set_metadata_transaction_id(struct dm_pool_metadata *pmd,
1061                                         uint64_t current_id,
1062                                         uint64_t new_id)
1063 {
1064         down_write(&pmd->root_lock);
1065         if (pmd->trans_id != current_id) {
1066                 up_write(&pmd->root_lock);
1067                 DMERR("mismatched transaction id");
1068                 return -EINVAL;
1069         }
1070
1071         pmd->trans_id = new_id;
1072         pmd->need_commit = 1;
1073         up_write(&pmd->root_lock);
1074
1075         return 0;
1076 }
1077
1078 int dm_pool_get_metadata_transaction_id(struct dm_pool_metadata *pmd,
1079                                         uint64_t *result)
1080 {
1081         down_read(&pmd->root_lock);
1082         *result = pmd->trans_id;
1083         up_read(&pmd->root_lock);
1084
1085         return 0;
1086 }
1087
1088 static int __get_held_metadata_root(struct dm_pool_metadata *pmd,
1089                                     dm_block_t *result)
1090 {
1091         int r;
1092         struct thin_disk_superblock *disk_super;
1093         struct dm_block *sblock;
1094
1095         r = dm_bm_write_lock(pmd->bm, THIN_SUPERBLOCK_LOCATION,
1096                              &sb_validator, &sblock);
1097         if (r)
1098                 return r;
1099
1100         disk_super = dm_block_data(sblock);
1101         *result = le64_to_cpu(disk_super->held_root);
1102
1103         return dm_bm_unlock(sblock);
1104 }
1105
1106 int dm_pool_get_held_metadata_root(struct dm_pool_metadata *pmd,
1107                                    dm_block_t *result)
1108 {
1109         int r;
1110
1111         down_read(&pmd->root_lock);
1112         r = __get_held_metadata_root(pmd, result);
1113         up_read(&pmd->root_lock);
1114
1115         return r;
1116 }
1117
1118 int dm_pool_open_thin_device(struct dm_pool_metadata *pmd, dm_thin_id dev,
1119                              struct dm_thin_device **td)
1120 {
1121         int r;
1122
1123         down_write(&pmd->root_lock);
1124         r = __open_device(pmd, dev, 0, td);
1125         up_write(&pmd->root_lock);
1126
1127         return r;
1128 }
1129
1130 int dm_pool_close_thin_device(struct dm_thin_device *td)
1131 {
1132         down_write(&td->pmd->root_lock);
1133         __close_device(td);
1134         up_write(&td->pmd->root_lock);
1135
1136         return 0;
1137 }
1138
1139 dm_thin_id dm_thin_dev_id(struct dm_thin_device *td)
1140 {
1141         return td->id;
1142 }
1143
1144 static int __snapshotted_since(struct dm_thin_device *td, uint32_t time)
1145 {
1146         return td->snapshotted_time > time;
1147 }
1148
1149 int dm_thin_find_block(struct dm_thin_device *td, dm_block_t block,
1150                        int can_block, struct dm_thin_lookup_result *result)
1151 {
1152         int r;
1153         uint64_t block_time = 0;
1154         __le64 value;
1155         struct dm_pool_metadata *pmd = td->pmd;
1156         dm_block_t keys[2] = { td->id, block };
1157
1158         if (can_block) {
1159                 down_read(&pmd->root_lock);
1160                 r = dm_btree_lookup(&pmd->info, pmd->root, keys, &value);
1161                 if (!r)
1162                         block_time = le64_to_cpu(value);
1163                 up_read(&pmd->root_lock);
1164
1165         } else if (down_read_trylock(&pmd->root_lock)) {
1166                 r = dm_btree_lookup(&pmd->nb_info, pmd->root, keys, &value);
1167                 if (!r)
1168                         block_time = le64_to_cpu(value);
1169                 up_read(&pmd->root_lock);
1170
1171         } else
1172                 return -EWOULDBLOCK;
1173
1174         if (!r) {
1175                 dm_block_t exception_block;
1176                 uint32_t exception_time;
1177                 unpack_block_time(block_time, &exception_block,
1178                                   &exception_time);
1179                 result->block = exception_block;
1180                 result->shared = __snapshotted_since(td, exception_time);
1181         }
1182
1183         return r;
1184 }
1185
1186 static int __insert(struct dm_thin_device *td, dm_block_t block,
1187                     dm_block_t data_block)
1188 {
1189         int r, inserted;
1190         __le64 value;
1191         struct dm_pool_metadata *pmd = td->pmd;
1192         dm_block_t keys[2] = { td->id, block };
1193
1194         pmd->need_commit = 1;
1195         value = cpu_to_le64(pack_block_time(data_block, pmd->time));
1196         __dm_bless_for_disk(&value);
1197
1198         r = dm_btree_insert_notify(&pmd->info, pmd->root, keys, &value,
1199                                    &pmd->root, &inserted);
1200         if (r)
1201                 return r;
1202
1203         if (inserted) {
1204                 td->mapped_blocks++;
1205                 td->changed = 1;
1206         }
1207
1208         return 0;
1209 }
1210
1211 int dm_thin_insert_block(struct dm_thin_device *td, dm_block_t block,
1212                          dm_block_t data_block)
1213 {
1214         int r;
1215
1216         down_write(&td->pmd->root_lock);
1217         r = __insert(td, block, data_block);
1218         up_write(&td->pmd->root_lock);
1219
1220         return r;
1221 }
1222
1223 static int __remove(struct dm_thin_device *td, dm_block_t block)
1224 {
1225         int r;
1226         struct dm_pool_metadata *pmd = td->pmd;
1227         dm_block_t keys[2] = { td->id, block };
1228
1229         r = dm_btree_remove(&pmd->info, pmd->root, keys, &pmd->root);
1230         if (r)
1231                 return r;
1232
1233         td->mapped_blocks--;
1234         td->changed = 1;
1235         pmd->need_commit = 1;
1236
1237         return 0;
1238 }
1239
1240 int dm_thin_remove_block(struct dm_thin_device *td, dm_block_t block)
1241 {
1242         int r;
1243
1244         down_write(&td->pmd->root_lock);
1245         r = __remove(td, block);
1246         up_write(&td->pmd->root_lock);
1247
1248         return r;
1249 }
1250
1251 int dm_pool_alloc_data_block(struct dm_pool_metadata *pmd, dm_block_t *result)
1252 {
1253         int r;
1254
1255         down_write(&pmd->root_lock);
1256
1257         r = dm_sm_new_block(pmd->data_sm, result);
1258         pmd->need_commit = 1;
1259
1260         up_write(&pmd->root_lock);
1261
1262         return r;
1263 }
1264
1265 int dm_pool_commit_metadata(struct dm_pool_metadata *pmd)
1266 {
1267         int r;
1268
1269         down_write(&pmd->root_lock);
1270
1271         r = __commit_transaction(pmd);
1272         if (r <= 0)
1273                 goto out;
1274
1275         /*
1276          * Open the next transaction.
1277          */
1278         r = __begin_transaction(pmd);
1279 out:
1280         up_write(&pmd->root_lock);
1281         return r;
1282 }
1283
1284 int dm_pool_get_free_block_count(struct dm_pool_metadata *pmd, dm_block_t *result)
1285 {
1286         int r;
1287
1288         down_read(&pmd->root_lock);
1289         r = dm_sm_get_nr_free(pmd->data_sm, result);
1290         up_read(&pmd->root_lock);
1291
1292         return r;
1293 }
1294
1295 int dm_pool_get_free_metadata_block_count(struct dm_pool_metadata *pmd,
1296                                           dm_block_t *result)
1297 {
1298         int r;
1299
1300         down_read(&pmd->root_lock);
1301         r = dm_sm_get_nr_free(pmd->metadata_sm, result);
1302         up_read(&pmd->root_lock);
1303
1304         return r;
1305 }
1306
1307 int dm_pool_get_metadata_dev_size(struct dm_pool_metadata *pmd,
1308                                   dm_block_t *result)
1309 {
1310         int r;
1311
1312         down_read(&pmd->root_lock);
1313         r = dm_sm_get_nr_blocks(pmd->metadata_sm, result);
1314         up_read(&pmd->root_lock);
1315
1316         return r;
1317 }
1318
1319 int dm_pool_get_data_block_size(struct dm_pool_metadata *pmd, sector_t *result)
1320 {
1321         down_read(&pmd->root_lock);
1322         *result = pmd->data_block_size;
1323         up_read(&pmd->root_lock);
1324
1325         return 0;
1326 }
1327
1328 int dm_pool_get_data_dev_size(struct dm_pool_metadata *pmd, dm_block_t *result)
1329 {
1330         int r;
1331
1332         down_read(&pmd->root_lock);
1333         r = dm_sm_get_nr_blocks(pmd->data_sm, result);
1334         up_read(&pmd->root_lock);
1335
1336         return r;
1337 }
1338
1339 int dm_thin_get_mapped_count(struct dm_thin_device *td, dm_block_t *result)
1340 {
1341         struct dm_pool_metadata *pmd = td->pmd;
1342
1343         down_read(&pmd->root_lock);
1344         *result = td->mapped_blocks;
1345         up_read(&pmd->root_lock);
1346
1347         return 0;
1348 }
1349
1350 static int __highest_block(struct dm_thin_device *td, dm_block_t *result)
1351 {
1352         int r;
1353         __le64 value_le;
1354         dm_block_t thin_root;
1355         struct dm_pool_metadata *pmd = td->pmd;
1356
1357         r = dm_btree_lookup(&pmd->tl_info, pmd->root, &td->id, &value_le);
1358         if (r)
1359                 return r;
1360
1361         thin_root = le64_to_cpu(value_le);
1362
1363         return dm_btree_find_highest_key(&pmd->bl_info, thin_root, result);
1364 }
1365
1366 int dm_thin_get_highest_mapped_block(struct dm_thin_device *td,
1367                                      dm_block_t *result)
1368 {
1369         int r;
1370         struct dm_pool_metadata *pmd = td->pmd;
1371
1372         down_read(&pmd->root_lock);
1373         r = __highest_block(td, result);
1374         up_read(&pmd->root_lock);
1375
1376         return r;
1377 }
1378
1379 static int __resize_data_dev(struct dm_pool_metadata *pmd, dm_block_t new_count)
1380 {
1381         int r;
1382         dm_block_t old_count;
1383
1384         r = dm_sm_get_nr_blocks(pmd->data_sm, &old_count);
1385         if (r)
1386                 return r;
1387
1388         if (new_count == old_count)
1389                 return 0;
1390
1391         if (new_count < old_count) {
1392                 DMERR("cannot reduce size of data device");
1393                 return -EINVAL;
1394         }
1395
1396         r = dm_sm_extend(pmd->data_sm, new_count - old_count);
1397         if (!r)
1398                 pmd->need_commit = 1;
1399
1400         return r;
1401 }
1402
1403 int dm_pool_resize_data_dev(struct dm_pool_metadata *pmd, dm_block_t new_count)
1404 {
1405         int r;
1406
1407         down_write(&pmd->root_lock);
1408         r = __resize_data_dev(pmd, new_count);
1409         up_write(&pmd->root_lock);
1410
1411         return r;
1412 }