GNU Linux-libre 4.19.264-gnu1
[releases.git] / drivers / md / persistent-data / dm-btree.c
1 /*
2  * Copyright (C) 2011 Red Hat, Inc.
3  *
4  * This file is released under the GPL.
5  */
6
7 #include "dm-btree-internal.h"
8 #include "dm-space-map.h"
9 #include "dm-transaction-manager.h"
10
11 #include <linux/export.h>
12 #include <linux/device-mapper.h>
13
14 #define DM_MSG_PREFIX "btree"
15
16 /*----------------------------------------------------------------
17  * Array manipulation
18  *--------------------------------------------------------------*/
19 static void memcpy_disk(void *dest, const void *src, size_t len)
20         __dm_written_to_disk(src)
21 {
22         memcpy(dest, src, len);
23         __dm_unbless_for_disk(src);
24 }
25
26 static void array_insert(void *base, size_t elt_size, unsigned nr_elts,
27                          unsigned index, void *elt)
28         __dm_written_to_disk(elt)
29 {
30         if (index < nr_elts)
31                 memmove(base + (elt_size * (index + 1)),
32                         base + (elt_size * index),
33                         (nr_elts - index) * elt_size);
34
35         memcpy_disk(base + (elt_size * index), elt, elt_size);
36 }
37
38 /*----------------------------------------------------------------*/
39
40 /* makes the assumption that no two keys are the same. */
41 static int bsearch(struct btree_node *n, uint64_t key, int want_hi)
42 {
43         int lo = -1, hi = le32_to_cpu(n->header.nr_entries);
44
45         while (hi - lo > 1) {
46                 int mid = lo + ((hi - lo) / 2);
47                 uint64_t mid_key = le64_to_cpu(n->keys[mid]);
48
49                 if (mid_key == key)
50                         return mid;
51
52                 if (mid_key < key)
53                         lo = mid;
54                 else
55                         hi = mid;
56         }
57
58         return want_hi ? hi : lo;
59 }
60
61 int lower_bound(struct btree_node *n, uint64_t key)
62 {
63         return bsearch(n, key, 0);
64 }
65
66 static int upper_bound(struct btree_node *n, uint64_t key)
67 {
68         return bsearch(n, key, 1);
69 }
70
71 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
72                   struct dm_btree_value_type *vt)
73 {
74         unsigned i;
75         uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);
76
77         if (le32_to_cpu(n->header.flags) & INTERNAL_NODE)
78                 for (i = 0; i < nr_entries; i++)
79                         dm_tm_inc(tm, value64(n, i));
80         else if (vt->inc)
81                 for (i = 0; i < nr_entries; i++)
82                         vt->inc(vt->context, value_ptr(n, i));
83 }
84
85 static int insert_at(size_t value_size, struct btree_node *node, unsigned index,
86                      uint64_t key, void *value)
87         __dm_written_to_disk(value)
88 {
89         uint32_t nr_entries = le32_to_cpu(node->header.nr_entries);
90         uint32_t max_entries = le32_to_cpu(node->header.max_entries);
91         __le64 key_le = cpu_to_le64(key);
92
93         if (index > nr_entries ||
94             index >= max_entries ||
95             nr_entries >= max_entries) {
96                 DMERR("too many entries in btree node for insert");
97                 __dm_unbless_for_disk(value);
98                 return -ENOMEM;
99         }
100
101         __dm_bless_for_disk(&key_le);
102
103         array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le);
104         array_insert(value_base(node), value_size, nr_entries, index, value);
105         node->header.nr_entries = cpu_to_le32(nr_entries + 1);
106
107         return 0;
108 }
109
110 /*----------------------------------------------------------------*/
111
112 /*
113  * We want 3n entries (for some n).  This works more nicely for repeated
114  * insert remove loops than (2n + 1).
115  */
116 static uint32_t calc_max_entries(size_t value_size, size_t block_size)
117 {
118         uint32_t total, n;
119         size_t elt_size = sizeof(uint64_t) + value_size; /* key + value */
120
121         block_size -= sizeof(struct node_header);
122         total = block_size / elt_size;
123         n = total / 3;          /* rounds down */
124
125         return 3 * n;
126 }
127
128 int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root)
129 {
130         int r;
131         struct dm_block *b;
132         struct btree_node *n;
133         size_t block_size;
134         uint32_t max_entries;
135
136         r = new_block(info, &b);
137         if (r < 0)
138                 return r;
139
140         block_size = dm_bm_block_size(dm_tm_get_bm(info->tm));
141         max_entries = calc_max_entries(info->value_type.size, block_size);
142
143         n = dm_block_data(b);
144         memset(n, 0, block_size);
145         n->header.flags = cpu_to_le32(LEAF_NODE);
146         n->header.nr_entries = cpu_to_le32(0);
147         n->header.max_entries = cpu_to_le32(max_entries);
148         n->header.value_size = cpu_to_le32(info->value_type.size);
149
150         *root = dm_block_location(b);
151         unlock_block(info, b);
152
153         return 0;
154 }
155 EXPORT_SYMBOL_GPL(dm_btree_empty);
156
157 /*----------------------------------------------------------------*/
158
159 /*
160  * Deletion uses a recursive algorithm, since we have limited stack space
161  * we explicitly manage our own stack on the heap.
162  */
163 #define MAX_SPINE_DEPTH 64
164 struct frame {
165         struct dm_block *b;
166         struct btree_node *n;
167         unsigned level;
168         unsigned nr_children;
169         unsigned current_child;
170 };
171
172 struct del_stack {
173         struct dm_btree_info *info;
174         struct dm_transaction_manager *tm;
175         int top;
176         struct frame spine[MAX_SPINE_DEPTH];
177 };
178
179 static int top_frame(struct del_stack *s, struct frame **f)
180 {
181         if (s->top < 0) {
182                 DMERR("btree deletion stack empty");
183                 return -EINVAL;
184         }
185
186         *f = s->spine + s->top;
187
188         return 0;
189 }
190
191 static int unprocessed_frames(struct del_stack *s)
192 {
193         return s->top >= 0;
194 }
195
196 static void prefetch_children(struct del_stack *s, struct frame *f)
197 {
198         unsigned i;
199         struct dm_block_manager *bm = dm_tm_get_bm(s->tm);
200
201         for (i = 0; i < f->nr_children; i++)
202                 dm_bm_prefetch(bm, value64(f->n, i));
203 }
204
205 static bool is_internal_level(struct dm_btree_info *info, struct frame *f)
206 {
207         return f->level < (info->levels - 1);
208 }
209
210 static int push_frame(struct del_stack *s, dm_block_t b, unsigned level)
211 {
212         int r;
213         uint32_t ref_count;
214
215         if (s->top >= MAX_SPINE_DEPTH - 1) {
216                 DMERR("btree deletion stack out of memory");
217                 return -ENOMEM;
218         }
219
220         r = dm_tm_ref(s->tm, b, &ref_count);
221         if (r)
222                 return r;
223
224         if (ref_count > 1)
225                 /*
226                  * This is a shared node, so we can just decrement it's
227                  * reference counter and leave the children.
228                  */
229                 dm_tm_dec(s->tm, b);
230
231         else {
232                 uint32_t flags;
233                 struct frame *f = s->spine + ++s->top;
234
235                 r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b);
236                 if (r) {
237                         s->top--;
238                         return r;
239                 }
240
241                 f->n = dm_block_data(f->b);
242                 f->level = level;
243                 f->nr_children = le32_to_cpu(f->n->header.nr_entries);
244                 f->current_child = 0;
245
246                 flags = le32_to_cpu(f->n->header.flags);
247                 if (flags & INTERNAL_NODE || is_internal_level(s->info, f))
248                         prefetch_children(s, f);
249         }
250
251         return 0;
252 }
253
254 static void pop_frame(struct del_stack *s)
255 {
256         struct frame *f = s->spine + s->top--;
257
258         dm_tm_dec(s->tm, dm_block_location(f->b));
259         dm_tm_unlock(s->tm, f->b);
260 }
261
262 static void unlock_all_frames(struct del_stack *s)
263 {
264         struct frame *f;
265
266         while (unprocessed_frames(s)) {
267                 f = s->spine + s->top--;
268                 dm_tm_unlock(s->tm, f->b);
269         }
270 }
271
272 int dm_btree_del(struct dm_btree_info *info, dm_block_t root)
273 {
274         int r;
275         struct del_stack *s;
276
277         /*
278          * dm_btree_del() is called via an ioctl, as such should be
279          * considered an FS op.  We can't recurse back into the FS, so we
280          * allocate GFP_NOFS.
281          */
282         s = kmalloc(sizeof(*s), GFP_NOFS);
283         if (!s)
284                 return -ENOMEM;
285         s->info = info;
286         s->tm = info->tm;
287         s->top = -1;
288
289         r = push_frame(s, root, 0);
290         if (r)
291                 goto out;
292
293         while (unprocessed_frames(s)) {
294                 uint32_t flags;
295                 struct frame *f;
296                 dm_block_t b;
297
298                 r = top_frame(s, &f);
299                 if (r)
300                         goto out;
301
302                 if (f->current_child >= f->nr_children) {
303                         pop_frame(s);
304                         continue;
305                 }
306
307                 flags = le32_to_cpu(f->n->header.flags);
308                 if (flags & INTERNAL_NODE) {
309                         b = value64(f->n, f->current_child);
310                         f->current_child++;
311                         r = push_frame(s, b, f->level);
312                         if (r)
313                                 goto out;
314
315                 } else if (is_internal_level(info, f)) {
316                         b = value64(f->n, f->current_child);
317                         f->current_child++;
318                         r = push_frame(s, b, f->level + 1);
319                         if (r)
320                                 goto out;
321
322                 } else {
323                         if (info->value_type.dec) {
324                                 unsigned i;
325
326                                 for (i = 0; i < f->nr_children; i++)
327                                         info->value_type.dec(info->value_type.context,
328                                                              value_ptr(f->n, i));
329                         }
330                         pop_frame(s);
331                 }
332         }
333 out:
334         if (r) {
335                 /* cleanup all frames of del_stack */
336                 unlock_all_frames(s);
337         }
338         kfree(s);
339
340         return r;
341 }
342 EXPORT_SYMBOL_GPL(dm_btree_del);
343
344 /*----------------------------------------------------------------*/
345
346 static int btree_lookup_raw(struct ro_spine *s, dm_block_t block, uint64_t key,
347                             int (*search_fn)(struct btree_node *, uint64_t),
348                             uint64_t *result_key, void *v, size_t value_size)
349 {
350         int i, r;
351         uint32_t flags, nr_entries;
352
353         do {
354                 r = ro_step(s, block);
355                 if (r < 0)
356                         return r;
357
358                 i = search_fn(ro_node(s), key);
359
360                 flags = le32_to_cpu(ro_node(s)->header.flags);
361                 nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries);
362                 if (i < 0 || i >= nr_entries)
363                         return -ENODATA;
364
365                 if (flags & INTERNAL_NODE)
366                         block = value64(ro_node(s), i);
367
368         } while (!(flags & LEAF_NODE));
369
370         *result_key = le64_to_cpu(ro_node(s)->keys[i]);
371         memcpy(v, value_ptr(ro_node(s), i), value_size);
372
373         return 0;
374 }
375
376 int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,
377                     uint64_t *keys, void *value_le)
378 {
379         unsigned level, last_level = info->levels - 1;
380         int r = -ENODATA;
381         uint64_t rkey;
382         __le64 internal_value_le;
383         struct ro_spine spine;
384
385         init_ro_spine(&spine, info);
386         for (level = 0; level < info->levels; level++) {
387                 size_t size;
388                 void *value_p;
389
390                 if (level == last_level) {
391                         value_p = value_le;
392                         size = info->value_type.size;
393
394                 } else {
395                         value_p = &internal_value_le;
396                         size = sizeof(uint64_t);
397                 }
398
399                 r = btree_lookup_raw(&spine, root, keys[level],
400                                      lower_bound, &rkey,
401                                      value_p, size);
402
403                 if (!r) {
404                         if (rkey != keys[level]) {
405                                 exit_ro_spine(&spine);
406                                 return -ENODATA;
407                         }
408                 } else {
409                         exit_ro_spine(&spine);
410                         return r;
411                 }
412
413                 root = le64_to_cpu(internal_value_le);
414         }
415         exit_ro_spine(&spine);
416
417         return r;
418 }
419 EXPORT_SYMBOL_GPL(dm_btree_lookup);
420
421 static int dm_btree_lookup_next_single(struct dm_btree_info *info, dm_block_t root,
422                                        uint64_t key, uint64_t *rkey, void *value_le)
423 {
424         int r, i;
425         uint32_t flags, nr_entries;
426         struct dm_block *node;
427         struct btree_node *n;
428
429         r = bn_read_lock(info, root, &node);
430         if (r)
431                 return r;
432
433         n = dm_block_data(node);
434         flags = le32_to_cpu(n->header.flags);
435         nr_entries = le32_to_cpu(n->header.nr_entries);
436
437         if (flags & INTERNAL_NODE) {
438                 i = lower_bound(n, key);
439                 if (i < 0) {
440                         /*
441                          * avoid early -ENODATA return when all entries are
442                          * higher than the search @key.
443                          */
444                         i = 0;
445                 }
446                 if (i >= nr_entries) {
447                         r = -ENODATA;
448                         goto out;
449                 }
450
451                 r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le);
452                 if (r == -ENODATA && i < (nr_entries - 1)) {
453                         i++;
454                         r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le);
455                 }
456
457         } else {
458                 i = upper_bound(n, key);
459                 if (i < 0 || i >= nr_entries) {
460                         r = -ENODATA;
461                         goto out;
462                 }
463
464                 *rkey = le64_to_cpu(n->keys[i]);
465                 memcpy(value_le, value_ptr(n, i), info->value_type.size);
466         }
467 out:
468         dm_tm_unlock(info->tm, node);
469         return r;
470 }
471
472 int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root,
473                          uint64_t *keys, uint64_t *rkey, void *value_le)
474 {
475         unsigned level;
476         int r = -ENODATA;
477         __le64 internal_value_le;
478         struct ro_spine spine;
479
480         init_ro_spine(&spine, info);
481         for (level = 0; level < info->levels - 1u; level++) {
482                 r = btree_lookup_raw(&spine, root, keys[level],
483                                      lower_bound, rkey,
484                                      &internal_value_le, sizeof(uint64_t));
485                 if (r)
486                         goto out;
487
488                 if (*rkey != keys[level]) {
489                         r = -ENODATA;
490                         goto out;
491                 }
492
493                 root = le64_to_cpu(internal_value_le);
494         }
495
496         r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le);
497 out:
498         exit_ro_spine(&spine);
499         return r;
500 }
501
502 EXPORT_SYMBOL_GPL(dm_btree_lookup_next);
503
504 /*
505  * Splits a node by creating a sibling node and shifting half the nodes
506  * contents across.  Assumes there is a parent node, and it has room for
507  * another child.
508  *
509  * Before:
510  *        +--------+
511  *        | Parent |
512  *        +--------+
513  *           |
514  *           v
515  *      +----------+
516  *      | A ++++++ |
517  *      +----------+
518  *
519  *
520  * After:
521  *              +--------+
522  *              | Parent |
523  *              +--------+
524  *                |     |
525  *                v     +------+
526  *          +---------+        |
527  *          | A* +++  |        v
528  *          +---------+   +-------+
529  *                        | B +++ |
530  *                        +-------+
531  *
532  * Where A* is a shadow of A.
533  */
534 static int btree_split_sibling(struct shadow_spine *s, unsigned parent_index,
535                                uint64_t key)
536 {
537         int r;
538         size_t size;
539         unsigned nr_left, nr_right;
540         struct dm_block *left, *right, *parent;
541         struct btree_node *ln, *rn, *pn;
542         __le64 location;
543
544         left = shadow_current(s);
545
546         r = new_block(s->info, &right);
547         if (r < 0)
548                 return r;
549
550         ln = dm_block_data(left);
551         rn = dm_block_data(right);
552
553         nr_left = le32_to_cpu(ln->header.nr_entries) / 2;
554         nr_right = le32_to_cpu(ln->header.nr_entries) - nr_left;
555
556         ln->header.nr_entries = cpu_to_le32(nr_left);
557
558         rn->header.flags = ln->header.flags;
559         rn->header.nr_entries = cpu_to_le32(nr_right);
560         rn->header.max_entries = ln->header.max_entries;
561         rn->header.value_size = ln->header.value_size;
562         memcpy(rn->keys, ln->keys + nr_left, nr_right * sizeof(rn->keys[0]));
563
564         size = le32_to_cpu(ln->header.flags) & INTERNAL_NODE ?
565                 sizeof(uint64_t) : s->info->value_type.size;
566         memcpy(value_ptr(rn, 0), value_ptr(ln, nr_left),
567                size * nr_right);
568
569         /*
570          * Patch up the parent
571          */
572         parent = shadow_parent(s);
573
574         pn = dm_block_data(parent);
575         location = cpu_to_le64(dm_block_location(left));
576         __dm_bless_for_disk(&location);
577         memcpy_disk(value_ptr(pn, parent_index),
578                     &location, sizeof(__le64));
579
580         location = cpu_to_le64(dm_block_location(right));
581         __dm_bless_for_disk(&location);
582
583         r = insert_at(sizeof(__le64), pn, parent_index + 1,
584                       le64_to_cpu(rn->keys[0]), &location);
585         if (r) {
586                 unlock_block(s->info, right);
587                 return r;
588         }
589
590         if (key < le64_to_cpu(rn->keys[0])) {
591                 unlock_block(s->info, right);
592                 s->nodes[1] = left;
593         } else {
594                 unlock_block(s->info, left);
595                 s->nodes[1] = right;
596         }
597
598         return 0;
599 }
600
601 /*
602  * Splits a node by creating two new children beneath the given node.
603  *
604  * Before:
605  *        +----------+
606  *        | A ++++++ |
607  *        +----------+
608  *
609  *
610  * After:
611  *      +------------+
612  *      | A (shadow) |
613  *      +------------+
614  *          |   |
615  *   +------+   +----+
616  *   |               |
617  *   v               v
618  * +-------+     +-------+
619  * | B +++ |     | C +++ |
620  * +-------+     +-------+
621  */
622 static int btree_split_beneath(struct shadow_spine *s, uint64_t key)
623 {
624         int r;
625         size_t size;
626         unsigned nr_left, nr_right;
627         struct dm_block *left, *right, *new_parent;
628         struct btree_node *pn, *ln, *rn;
629         __le64 val;
630
631         new_parent = shadow_current(s);
632
633         pn = dm_block_data(new_parent);
634         size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ?
635                 sizeof(__le64) : s->info->value_type.size;
636
637         /* create & init the left block */
638         r = new_block(s->info, &left);
639         if (r < 0)
640                 return r;
641
642         ln = dm_block_data(left);
643         nr_left = le32_to_cpu(pn->header.nr_entries) / 2;
644
645         ln->header.flags = pn->header.flags;
646         ln->header.nr_entries = cpu_to_le32(nr_left);
647         ln->header.max_entries = pn->header.max_entries;
648         ln->header.value_size = pn->header.value_size;
649         memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0]));
650         memcpy(value_ptr(ln, 0), value_ptr(pn, 0), nr_left * size);
651
652         /* create & init the right block */
653         r = new_block(s->info, &right);
654         if (r < 0) {
655                 unlock_block(s->info, left);
656                 return r;
657         }
658
659         rn = dm_block_data(right);
660         nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left;
661
662         rn->header.flags = pn->header.flags;
663         rn->header.nr_entries = cpu_to_le32(nr_right);
664         rn->header.max_entries = pn->header.max_entries;
665         rn->header.value_size = pn->header.value_size;
666         memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0]));
667         memcpy(value_ptr(rn, 0), value_ptr(pn, nr_left),
668                nr_right * size);
669
670         /* new_parent should just point to l and r now */
671         pn->header.flags = cpu_to_le32(INTERNAL_NODE);
672         pn->header.nr_entries = cpu_to_le32(2);
673         pn->header.max_entries = cpu_to_le32(
674                 calc_max_entries(sizeof(__le64),
675                                  dm_bm_block_size(
676                                          dm_tm_get_bm(s->info->tm))));
677         pn->header.value_size = cpu_to_le32(sizeof(__le64));
678
679         val = cpu_to_le64(dm_block_location(left));
680         __dm_bless_for_disk(&val);
681         pn->keys[0] = ln->keys[0];
682         memcpy_disk(value_ptr(pn, 0), &val, sizeof(__le64));
683
684         val = cpu_to_le64(dm_block_location(right));
685         __dm_bless_for_disk(&val);
686         pn->keys[1] = rn->keys[0];
687         memcpy_disk(value_ptr(pn, 1), &val, sizeof(__le64));
688
689         unlock_block(s->info, left);
690         unlock_block(s->info, right);
691         return 0;
692 }
693
694 static int btree_insert_raw(struct shadow_spine *s, dm_block_t root,
695                             struct dm_btree_value_type *vt,
696                             uint64_t key, unsigned *index)
697 {
698         int r, i = *index, top = 1;
699         struct btree_node *node;
700
701         for (;;) {
702                 r = shadow_step(s, root, vt);
703                 if (r < 0)
704                         return r;
705
706                 node = dm_block_data(shadow_current(s));
707
708                 /*
709                  * We have to patch up the parent node, ugly, but I don't
710                  * see a way to do this automatically as part of the spine
711                  * op.
712                  */
713                 if (shadow_has_parent(s) && i >= 0) { /* FIXME: second clause unness. */
714                         __le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));
715
716                         __dm_bless_for_disk(&location);
717                         memcpy_disk(value_ptr(dm_block_data(shadow_parent(s)), i),
718                                     &location, sizeof(__le64));
719                 }
720
721                 node = dm_block_data(shadow_current(s));
722
723                 if (node->header.nr_entries == node->header.max_entries) {
724                         if (top)
725                                 r = btree_split_beneath(s, key);
726                         else
727                                 r = btree_split_sibling(s, i, key);
728
729                         if (r < 0)
730                                 return r;
731                 }
732
733                 node = dm_block_data(shadow_current(s));
734
735                 i = lower_bound(node, key);
736
737                 if (le32_to_cpu(node->header.flags) & LEAF_NODE)
738                         break;
739
740                 if (i < 0) {
741                         /* change the bounds on the lowest key */
742                         node->keys[0] = cpu_to_le64(key);
743                         i = 0;
744                 }
745
746                 root = value64(node, i);
747                 top = 0;
748         }
749
750         if (i < 0 || le64_to_cpu(node->keys[i]) != key)
751                 i++;
752
753         *index = i;
754         return 0;
755 }
756
757 static bool need_insert(struct btree_node *node, uint64_t *keys,
758                         unsigned level, unsigned index)
759 {
760         return ((index >= le32_to_cpu(node->header.nr_entries)) ||
761                 (le64_to_cpu(node->keys[index]) != keys[level]));
762 }
763
764 static int insert(struct dm_btree_info *info, dm_block_t root,
765                   uint64_t *keys, void *value, dm_block_t *new_root,
766                   int *inserted)
767                   __dm_written_to_disk(value)
768 {
769         int r;
770         unsigned level, index = -1, last_level = info->levels - 1;
771         dm_block_t block = root;
772         struct shadow_spine spine;
773         struct btree_node *n;
774         struct dm_btree_value_type le64_type;
775
776         init_le64_type(info->tm, &le64_type);
777         init_shadow_spine(&spine, info);
778
779         for (level = 0; level < (info->levels - 1); level++) {
780                 r = btree_insert_raw(&spine, block, &le64_type, keys[level], &index);
781                 if (r < 0)
782                         goto bad;
783
784                 n = dm_block_data(shadow_current(&spine));
785
786                 if (need_insert(n, keys, level, index)) {
787                         dm_block_t new_tree;
788                         __le64 new_le;
789
790                         r = dm_btree_empty(info, &new_tree);
791                         if (r < 0)
792                                 goto bad;
793
794                         new_le = cpu_to_le64(new_tree);
795                         __dm_bless_for_disk(&new_le);
796
797                         r = insert_at(sizeof(uint64_t), n, index,
798                                       keys[level], &new_le);
799                         if (r)
800                                 goto bad;
801                 }
802
803                 if (level < last_level)
804                         block = value64(n, index);
805         }
806
807         r = btree_insert_raw(&spine, block, &info->value_type,
808                              keys[level], &index);
809         if (r < 0)
810                 goto bad;
811
812         n = dm_block_data(shadow_current(&spine));
813
814         if (need_insert(n, keys, level, index)) {
815                 if (inserted)
816                         *inserted = 1;
817
818                 r = insert_at(info->value_type.size, n, index,
819                               keys[level], value);
820                 if (r)
821                         goto bad_unblessed;
822         } else {
823                 if (inserted)
824                         *inserted = 0;
825
826                 if (info->value_type.dec &&
827                     (!info->value_type.equal ||
828                      !info->value_type.equal(
829                              info->value_type.context,
830                              value_ptr(n, index),
831                              value))) {
832                         info->value_type.dec(info->value_type.context,
833                                              value_ptr(n, index));
834                 }
835                 memcpy_disk(value_ptr(n, index),
836                             value, info->value_type.size);
837         }
838
839         *new_root = shadow_root(&spine);
840         exit_shadow_spine(&spine);
841
842         return 0;
843
844 bad:
845         __dm_unbless_for_disk(value);
846 bad_unblessed:
847         exit_shadow_spine(&spine);
848         return r;
849 }
850
851 int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,
852                     uint64_t *keys, void *value, dm_block_t *new_root)
853                     __dm_written_to_disk(value)
854 {
855         return insert(info, root, keys, value, new_root, NULL);
856 }
857 EXPORT_SYMBOL_GPL(dm_btree_insert);
858
859 int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root,
860                            uint64_t *keys, void *value, dm_block_t *new_root,
861                            int *inserted)
862                            __dm_written_to_disk(value)
863 {
864         return insert(info, root, keys, value, new_root, inserted);
865 }
866 EXPORT_SYMBOL_GPL(dm_btree_insert_notify);
867
868 /*----------------------------------------------------------------*/
869
870 static int find_key(struct ro_spine *s, dm_block_t block, bool find_highest,
871                     uint64_t *result_key, dm_block_t *next_block)
872 {
873         int i, r;
874         uint32_t flags;
875
876         do {
877                 r = ro_step(s, block);
878                 if (r < 0)
879                         return r;
880
881                 flags = le32_to_cpu(ro_node(s)->header.flags);
882                 i = le32_to_cpu(ro_node(s)->header.nr_entries);
883                 if (!i)
884                         return -ENODATA;
885                 else
886                         i--;
887
888                 if (find_highest)
889                         *result_key = le64_to_cpu(ro_node(s)->keys[i]);
890                 else
891                         *result_key = le64_to_cpu(ro_node(s)->keys[0]);
892
893                 if (next_block || flags & INTERNAL_NODE) {
894                         if (find_highest)
895                                 block = value64(ro_node(s), i);
896                         else
897                                 block = value64(ro_node(s), 0);
898                 }
899
900         } while (flags & INTERNAL_NODE);
901
902         if (next_block)
903                 *next_block = block;
904         return 0;
905 }
906
907 static int dm_btree_find_key(struct dm_btree_info *info, dm_block_t root,
908                              bool find_highest, uint64_t *result_keys)
909 {
910         int r = 0, count = 0, level;
911         struct ro_spine spine;
912
913         init_ro_spine(&spine, info);
914         for (level = 0; level < info->levels; level++) {
915                 r = find_key(&spine, root, find_highest, result_keys + level,
916                              level == info->levels - 1 ? NULL : &root);
917                 if (r == -ENODATA) {
918                         r = 0;
919                         break;
920
921                 } else if (r)
922                         break;
923
924                 count++;
925         }
926         exit_ro_spine(&spine);
927
928         return r ? r : count;
929 }
930
931 int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
932                               uint64_t *result_keys)
933 {
934         return dm_btree_find_key(info, root, true, result_keys);
935 }
936 EXPORT_SYMBOL_GPL(dm_btree_find_highest_key);
937
938 int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
939                              uint64_t *result_keys)
940 {
941         return dm_btree_find_key(info, root, false, result_keys);
942 }
943 EXPORT_SYMBOL_GPL(dm_btree_find_lowest_key);
944
945 /*----------------------------------------------------------------*/
946
947 /*
948  * FIXME: We shouldn't use a recursive algorithm when we have limited stack
949  * space.  Also this only works for single level trees.
950  */
951 static int walk_node(struct dm_btree_info *info, dm_block_t block,
952                      int (*fn)(void *context, uint64_t *keys, void *leaf),
953                      void *context)
954 {
955         int r;
956         unsigned i, nr;
957         struct dm_block *node;
958         struct btree_node *n;
959         uint64_t keys;
960
961         r = bn_read_lock(info, block, &node);
962         if (r)
963                 return r;
964
965         n = dm_block_data(node);
966
967         nr = le32_to_cpu(n->header.nr_entries);
968         for (i = 0; i < nr; i++) {
969                 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) {
970                         r = walk_node(info, value64(n, i), fn, context);
971                         if (r)
972                                 goto out;
973                 } else {
974                         keys = le64_to_cpu(*key_ptr(n, i));
975                         r = fn(context, &keys, value_ptr(n, i));
976                         if (r)
977                                 goto out;
978                 }
979         }
980
981 out:
982         dm_tm_unlock(info->tm, node);
983         return r;
984 }
985
986 int dm_btree_walk(struct dm_btree_info *info, dm_block_t root,
987                   int (*fn)(void *context, uint64_t *keys, void *leaf),
988                   void *context)
989 {
990         BUG_ON(info->levels > 1);
991         return walk_node(info, root, fn, context);
992 }
993 EXPORT_SYMBOL_GPL(dm_btree_walk);
994
995 /*----------------------------------------------------------------*/
996
997 static void prefetch_values(struct dm_btree_cursor *c)
998 {
999         unsigned i, nr;
1000         __le64 value_le;
1001         struct cursor_node *n = c->nodes + c->depth - 1;
1002         struct btree_node *bn = dm_block_data(n->b);
1003         struct dm_block_manager *bm = dm_tm_get_bm(c->info->tm);
1004
1005         BUG_ON(c->info->value_type.size != sizeof(value_le));
1006
1007         nr = le32_to_cpu(bn->header.nr_entries);
1008         for (i = 0; i < nr; i++) {
1009                 memcpy(&value_le, value_ptr(bn, i), sizeof(value_le));
1010                 dm_bm_prefetch(bm, le64_to_cpu(value_le));
1011         }
1012 }
1013
1014 static bool leaf_node(struct dm_btree_cursor *c)
1015 {
1016         struct cursor_node *n = c->nodes + c->depth - 1;
1017         struct btree_node *bn = dm_block_data(n->b);
1018
1019         return le32_to_cpu(bn->header.flags) & LEAF_NODE;
1020 }
1021
1022 static int push_node(struct dm_btree_cursor *c, dm_block_t b)
1023 {
1024         int r;
1025         struct cursor_node *n = c->nodes + c->depth;
1026
1027         if (c->depth >= DM_BTREE_CURSOR_MAX_DEPTH - 1) {
1028                 DMERR("couldn't push cursor node, stack depth too high");
1029                 return -EINVAL;
1030         }
1031
1032         r = bn_read_lock(c->info, b, &n->b);
1033         if (r)
1034                 return r;
1035
1036         n->index = 0;
1037         c->depth++;
1038
1039         if (c->prefetch_leaves || !leaf_node(c))
1040                 prefetch_values(c);
1041
1042         return 0;
1043 }
1044
1045 static void pop_node(struct dm_btree_cursor *c)
1046 {
1047         c->depth--;
1048         unlock_block(c->info, c->nodes[c->depth].b);
1049 }
1050
1051 static int inc_or_backtrack(struct dm_btree_cursor *c)
1052 {
1053         struct cursor_node *n;
1054         struct btree_node *bn;
1055
1056         for (;;) {
1057                 if (!c->depth)
1058                         return -ENODATA;
1059
1060                 n = c->nodes + c->depth - 1;
1061                 bn = dm_block_data(n->b);
1062
1063                 n->index++;
1064                 if (n->index < le32_to_cpu(bn->header.nr_entries))
1065                         break;
1066
1067                 pop_node(c);
1068         }
1069
1070         return 0;
1071 }
1072
1073 static int find_leaf(struct dm_btree_cursor *c)
1074 {
1075         int r = 0;
1076         struct cursor_node *n;
1077         struct btree_node *bn;
1078         __le64 value_le;
1079
1080         for (;;) {
1081                 n = c->nodes + c->depth - 1;
1082                 bn = dm_block_data(n->b);
1083
1084                 if (le32_to_cpu(bn->header.flags) & LEAF_NODE)
1085                         break;
1086
1087                 memcpy(&value_le, value_ptr(bn, n->index), sizeof(value_le));
1088                 r = push_node(c, le64_to_cpu(value_le));
1089                 if (r) {
1090                         DMERR("push_node failed");
1091                         break;
1092                 }
1093         }
1094
1095         if (!r && (le32_to_cpu(bn->header.nr_entries) == 0))
1096                 return -ENODATA;
1097
1098         return r;
1099 }
1100
1101 int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root,
1102                           bool prefetch_leaves, struct dm_btree_cursor *c)
1103 {
1104         int r;
1105
1106         c->info = info;
1107         c->root = root;
1108         c->depth = 0;
1109         c->prefetch_leaves = prefetch_leaves;
1110
1111         r = push_node(c, root);
1112         if (r)
1113                 return r;
1114
1115         return find_leaf(c);
1116 }
1117 EXPORT_SYMBOL_GPL(dm_btree_cursor_begin);
1118
1119 void dm_btree_cursor_end(struct dm_btree_cursor *c)
1120 {
1121         while (c->depth)
1122                 pop_node(c);
1123 }
1124 EXPORT_SYMBOL_GPL(dm_btree_cursor_end);
1125
1126 int dm_btree_cursor_next(struct dm_btree_cursor *c)
1127 {
1128         int r = inc_or_backtrack(c);
1129         if (!r) {
1130                 r = find_leaf(c);
1131                 if (r)
1132                         DMERR("find_leaf failed");
1133         }
1134
1135         return r;
1136 }
1137 EXPORT_SYMBOL_GPL(dm_btree_cursor_next);
1138
1139 int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count)
1140 {
1141         int r = 0;
1142
1143         while (count-- && !r)
1144                 r = dm_btree_cursor_next(c);
1145
1146         return r;
1147 }
1148 EXPORT_SYMBOL_GPL(dm_btree_cursor_skip);
1149
1150 int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le)
1151 {
1152         if (c->depth) {
1153                 struct cursor_node *n = c->nodes + c->depth - 1;
1154                 struct btree_node *bn = dm_block_data(n->b);
1155
1156                 if (le32_to_cpu(bn->header.flags) & INTERNAL_NODE)
1157                         return -EINVAL;
1158
1159                 *key = le64_to_cpu(*key_ptr(bn, n->index));
1160                 memcpy(value_le, value_ptr(bn, n->index), c->info->value_type.size);
1161                 return 0;
1162
1163         } else
1164                 return -ENODATA;
1165 }
1166 EXPORT_SYMBOL_GPL(dm_btree_cursor_get_value);