?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Add linux-next specific files for 20110831
[linux-2.6/next.git] / drivers / md / persistent-data / dm-btree.c
blob408b762532a777659905ca4870dc58b131b48396
1 /*
2 * Copyright (C) 2011 Red Hat, Inc. All rights reserved.
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 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 node *n, uint64_t key)
62 {
63 return bsearch(n, key, 0);
64 }
65
66 void inc_children(struct dm_transaction_manager *tm, struct node *n,
67 struct dm_btree_value_type *vt)
68 {
69 unsigned i;
70 uint32_t nr_entries = le32_to_cpu(n->header.nr_entries);
71
72 if (le32_to_cpu(n->header.flags) & INTERNAL_NODE)
73 for (i = 0; i < nr_entries; i++)
74 dm_tm_inc(tm, value64(n, i));
75 else if (vt->inc)
76 for (i = 0; i < nr_entries; i++)
77 vt->inc(vt->context,
78 value_ptr(n, i, vt->size));
79 }
80
81 static int insert_at(size_t value_size, struct node *node, unsigned index,
82 uint64_t key, void *value)
83 __dm_written_to_disk(value)
84 {
85 uint32_t nr_entries = le32_to_cpu(node->header.nr_entries);
86 __le64 key_le = cpu_to_le64(key);
87
88 if (index > nr_entries ||
89 index >= le32_to_cpu(node->header.max_entries)) {
90 DMERR("too many entries in btree node for insert");
91 __dm_unbless_for_disk(value);
92 return -ENOMEM;
93 }
94
95 __dm_bless_for_disk(&key_le);
96
97 array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le);
98 array_insert(value_base(node), value_size, nr_entries, index, value);
99 node->header.nr_entries = cpu_to_le32(nr_entries + 1);
100
101 return 0;
102 }
103
104 /*----------------------------------------------------------------*/
105
106 /*
107 * We want 3n entries (for some n). This works more nicely for repeated
108 * insert remove loops than (2n + 1).
109 */
110 static uint32_t calc_max_entries(size_t value_size, size_t block_size)
111 {
112 uint32_t total, n;
113 size_t elt_size = sizeof(uint64_t) + value_size; /* key + value */
114
115 block_size -= sizeof(struct node_header);
116 total = block_size / elt_size;
117 n = total / 3; /* rounds down */
118
119 return 3 * n;
120 }
121
122 int dm_btree_create(struct dm_btree_info *info, dm_block_t *root)
123 {
124 int r;
125 struct dm_block *b;
126 struct node *n;
127 size_t block_size;
128 uint32_t max_entries;
129
130 r = new_block(info, &b);
131 if (r < 0)
132 return r;
133
134 block_size = dm_bm_block_size(dm_tm_get_bm(info->tm));
135 max_entries = calc_max_entries(info->value_type.size, block_size);
136
137 n = dm_block_data(b);
138 memset(n, 0, block_size);
139 n->header.flags = cpu_to_le32(LEAF_NODE);
140 n->header.nr_entries = cpu_to_le32(0);
141 n->header.max_entries = cpu_to_le32(max_entries);
142 n->header.value_size = cpu_to_le32(info->value_type.size);
143
144 *root = dm_block_location(b);
145
146 return unlock_block(info, b);
147 }
148 EXPORT_SYMBOL_GPL(dm_btree_create);
149
150 /*----------------------------------------------------------------*/
151
152 /*
153 * Deletion uses a recursive algorithm, since we have limited stack space
154 * we explicitly manage our own stack on the heap.
155 */
156 #define MAX_SPINE_DEPTH 64
157 struct frame {
158 struct dm_block *b;
159 struct node *n;
160 unsigned level;
161 unsigned nr_children;
162 unsigned current_child;
163 };
164
165 struct del_stack {
166 struct dm_transaction_manager *tm;
167 int top;
168 struct frame spine[MAX_SPINE_DEPTH];
169 };
170
171 static int top_frame(struct del_stack *s, struct frame **f)
172 {
173 if (s->top < 0) {
174 DMERR("btree deletion stack empty");
175 return -EINVAL;
176 }
177
178 *f = s->spine + s->top;
179
180 return 0;
181 }
182
183 static int unprocessed_frames(struct del_stack *s)
184 {
185 return s->top >= 0;
186 }
187
188 static int push_frame(struct del_stack *s, dm_block_t b, unsigned level)
189 {
190 int r;
191 uint32_t ref_count;
192
193 if (s->top >= MAX_SPINE_DEPTH - 1) {
194 DMERR("btree deletion stack out of memory");
195 return -ENOMEM;
196 }
197
198 r = dm_tm_ref(s->tm, b, &ref_count);
199 if (r)
200 return r;
201
202 if (ref_count > 1)
203 /*
204 * This is a shared node, so we can just decrement its
205 * reference counter and leave the children.
206 */
207 dm_tm_dec(s->tm, b);
208
209 else {
210 struct frame *f = s->spine + ++s->top;
211
212 r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b);
213 if (r) {
214 s->top--;
215 return r;
216 }
217
218 f->n = dm_block_data(f->b);
219 f->level = level;
220 f->nr_children = le32_to_cpu(f->n->header.nr_entries);
221 f->current_child = 0;
222 }
223
224 return 0;
225 }
226
227 static void pop_frame(struct del_stack *s)
228 {
229 struct frame *f = s->spine + s->top--;
230
231 dm_tm_dec(s->tm, dm_block_location(f->b));
232 dm_tm_unlock(s->tm, f->b);
233 }
234
235 int dm_btree_destroy(struct dm_btree_info *info, dm_block_t root)
236 {
237 int r;
238 struct del_stack *s;
239
240 s = kmalloc(sizeof(*s), GFP_KERNEL);
241 if (!s)
242 return -ENOMEM;
243
244 s->tm = info->tm;
245 s->top = -1;
246
247 r = push_frame(s, root, 1);
248 if (r)
249 goto out;
250
251 while (unprocessed_frames(s)) {
252 uint32_t flags;
253 struct frame *f;
254 dm_block_t b;
255
256 r = top_frame(s, &f);
257 if (r)
258 goto out;
259
260 if (f->current_child >= f->nr_children) {
261 pop_frame(s);
262 continue;
263 }
264
265 flags = le32_to_cpu(f->n->header.flags);
266 if (flags & INTERNAL_NODE) {
267 b = value64(f->n, f->current_child);
268 f->current_child++;
269 r = push_frame(s, b, f->level);
270 if (r)
271 goto out;
272
273 } else if (f->level != (info->levels - 1)) {
274 b = value64(f->n, f->current_child);
275 f->current_child++;
276 r = push_frame(s, b, f->level + 1);
277 if (r)
278 goto out;
279
280 } else {
281 if (info->value_type.dec) {
282 unsigned i;
283
284 for (i = 0; i < f->nr_children; i++)
285 info->value_type.dec(info->value_type.context,
286 value_ptr(f->n, i, info->value_type.size));
287 }
288 f->current_child = f->nr_children;
289 }
290 }
291
292 out:
293 kfree(s);
294 return r;
295 }
296 EXPORT_SYMBOL_GPL(dm_btree_destroy);
297
298 // FIXME Implement or remove this fn before final submission.
299 int dm_btree_delete_gt(struct dm_btree_info *info, dm_block_t root, uint64_t *key,
300 dm_block_t *new_root)
301 {
302 /* FIXME: implement */
303 return 0;
304 }
305 EXPORT_SYMBOL_GPL(dm_btree_delete_gt);
306
307 /*----------------------------------------------------------------*/
308
309 static int btree_lookup_raw(struct ro_spine *s, dm_block_t block, uint64_t key,
310 int (*search_fn)(struct node *, uint64_t),
311 uint64_t *result_key, void *v, size_t value_size)
312 {
313 int i, r;
314 uint32_t flags, nr_entries;
315
316 do {
317 r = ro_step(s, block);
318 if (r < 0)
319 return r;
320
321 i = search_fn(ro_node(s), key);
322
323 flags = le32_to_cpu(ro_node(s)->header.flags);
324 nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries);
325 if (i < 0 || i >= nr_entries)
326 return -ENODATA;
327
328 if (flags & INTERNAL_NODE)
329 block = value64(ro_node(s), i);
330
331 } while (!(flags & LEAF_NODE));
332
333 *result_key = le64_to_cpu(ro_node(s)->keys[i]);
334 memcpy(v, value_ptr(ro_node(s), i, value_size), value_size);
335
336 return 0;
337 }
338
339 int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,
340 uint64_t *keys, void *value_le)
341 {
342 unsigned level, last_level = info->levels - 1;
343 int r = -ENODATA;
344 uint64_t rkey;
345 __le64 internal_value_le;
346 struct ro_spine spine;
347
348 init_ro_spine(&spine, info);
349 for (level = 0; level < info->levels; level++) {
350 size_t size;
351 void *value_p;
352
353 if (level == last_level) {
354 value_p = value_le;
355 size = info->value_type.size;
356
357 } else {
358 value_p = &internal_value_le;
359 size = sizeof(uint64_t);
360 }
361
362 r = btree_lookup_raw(&spine, root, keys[level],
363 lower_bound, &rkey,
364 value_p, size);
365
366 if (!r) {
367 if (rkey != keys[level]) {
368 exit_ro_spine(&spine);
369 return -ENODATA;
370 }
371 } else {
372 exit_ro_spine(&spine);
373 return r;
374 }
375
376 root = le64_to_cpu(internal_value_le);
377 }
378 exit_ro_spine(&spine);
379
380 return r;
381 }
382 EXPORT_SYMBOL_GPL(dm_btree_lookup);
383
384 /*
385 * Splits a node by creating a sibling node and shifting half the nodes
386 * contents across. Assumes there is a parent node, and it has room for
387 * another child.
388 *
389 * Before:
390 * +--------+
391 * | Parent |
392 * +--------+
393 * |
394 * v
395 * +----------+
396 * | A ++++++ |
397 * +----------+
398 *
399 *
400 * After:
401 * +--------+
402 * | Parent |
403 * +--------+
404 * | |
405 * v +------+
406 * +---------+ |
407 * | A* +++ | v
408 * +---------+ +-------+
409 * | B +++ |
410 * +-------+
411 *
412 * Where A* is a shadow of A.
413 */
414 static int btree_split_sibling(struct shadow_spine *s, dm_block_t root,
415 unsigned parent_index, uint64_t key)
416 {
417 int r;
418 size_t size;
419 unsigned nr_left, nr_right;
420 struct dm_block *left, *right, *parent;
421 struct node *ln, *rn, *pn;
422 __le64 location;
423
424 left = shadow_current(s);
425
426 r = new_block(s->info, &right);
427 if (r < 0)
428 return r;
429
430 ln = dm_block_data(left);
431 rn = dm_block_data(right);
432
433 nr_left = le32_to_cpu(ln->header.nr_entries) / 2;
434 nr_right = le32_to_cpu(ln->header.nr_entries) - nr_left;
435
436 ln->header.nr_entries = cpu_to_le32(nr_left);
437
438 rn->header.flags = ln->header.flags;
439 rn->header.nr_entries = cpu_to_le32(nr_right);
440 rn->header.max_entries = ln->header.max_entries;
441 rn->header.value_size = ln->header.value_size;
442 memcpy(rn->keys, ln->keys + nr_left, nr_right * sizeof(rn->keys[0]));
443
444 size = le32_to_cpu(ln->header.flags) & INTERNAL_NODE ?
445 sizeof(uint64_t) : s->info->value_type.size;
446 memcpy(value_ptr(rn, 0, size), value_ptr(ln, nr_left, size),
447 size * nr_right);
448
449 /*
450 * Patch up the parent
451 */
452 parent = shadow_parent(s);
453
454 pn = dm_block_data(parent);
455 location = cpu_to_le64(dm_block_location(left));
456 __dm_bless_for_disk(&location);
457 memcpy_disk(value_ptr(pn, parent_index, sizeof(__le64)),
458 &location, sizeof(__le64));
459
460 location = cpu_to_le64(dm_block_location(right));
461 __dm_bless_for_disk(&location);
462
463 r = insert_at(sizeof(__le64), pn, parent_index + 1,
464 le64_to_cpu(rn->keys[0]), &location);
465 if (r)
466 return r;
467
468 if (key < le64_to_cpu(rn->keys[0])) {
469 unlock_block(s->info, right);
470 s->nodes[1] = left;
471 } else {
472 unlock_block(s->info, left);
473 s->nodes[1] = right;
474 }
475
476 return 0;
477 }
478
479 /*
480 * Splits a node by creating two new children beneath the given node.
481 *
482 * Before:
483 * +----------+
484 * | A ++++++ |
485 * +----------+
486 *
487 *
488 * After:
489 * +------------+
490 * | A (shadow) |
491 * +------------+
492 * | |
493 * +------+ +----+
494 * | |
495 * v v
496 * +-------+ +-------+
497 * | B +++ | | C +++ |
498 * +-------+ +-------+
499 */
500 static int btree_split_beneath(struct shadow_spine *s, uint64_t key)
501 {
502 int r;
503 size_t size;
504 unsigned nr_left, nr_right;
505 struct dm_block *left, *right, *new_parent;
506 struct node *pn, *ln, *rn;
507 __le64 val;
508
509 new_parent = shadow_current(s);
510
511 r = new_block(s->info, &left);
512 if (r < 0)
513 return r;
514
515 r = new_block(s->info, &right);
516 if (r < 0) {
517 /* FIXME: put left */
518 return r;
519 }
520
521 pn = dm_block_data(new_parent);
522 ln = dm_block_data(left);
523 rn = dm_block_data(right);
524
525 nr_left = le32_to_cpu(pn->header.nr_entries) / 2;
526 nr_right = le32_to_cpu(pn->header.nr_entries) - nr_left;
527
528 ln->header.flags = pn->header.flags;
529 ln->header.nr_entries = cpu_to_le32(nr_left);
530 ln->header.max_entries = pn->header.max_entries;
531 ln->header.value_size = pn->header.value_size;
532
533 rn->header.flags = pn->header.flags;
534 rn->header.nr_entries = cpu_to_le32(nr_right);
535 rn->header.max_entries = pn->header.max_entries;
536 rn->header.value_size = pn->header.value_size;
537
538 memcpy(ln->keys, pn->keys, nr_left * sizeof(pn->keys[0]));
539 memcpy(rn->keys, pn->keys + nr_left, nr_right * sizeof(pn->keys[0]));
540
541 size = le32_to_cpu(pn->header.flags) & INTERNAL_NODE ?
542 sizeof(__le64) : s->info->value_type.size;
543 memcpy(value_ptr(ln, 0, size), value_ptr(pn, 0, size), nr_left * size);
544 memcpy(value_ptr(rn, 0, size), value_ptr(pn, nr_left, size),
545 nr_right * size);
546
547 /* new_parent should just point to l and r now */
548 pn->header.flags = cpu_to_le32(INTERNAL_NODE);
549 pn->header.nr_entries = cpu_to_le32(2);
550 pn->header.max_entries = cpu_to_le32(
551 calc_max_entries(sizeof(__le64),
552 dm_bm_block_size(
553 dm_tm_get_bm(s->info->tm))));
554 pn->header.value_size = cpu_to_le32(sizeof(__le64));
555
556 val = cpu_to_le64(dm_block_location(left));
557 __dm_bless_for_disk(&val);
558 pn->keys[0] = ln->keys[0];
559 memcpy_disk(value_ptr(pn, 0, sizeof(__le64)), &val, sizeof(__le64));
560
561 val = cpu_to_le64(dm_block_location(right));
562 __dm_bless_for_disk(&val);
563 pn->keys[1] = rn->keys[0];
564 memcpy_disk(value_ptr(pn, 1, sizeof(__le64)), &val, sizeof(__le64));
565
566 /*
567 * rejig the spine. This is ugly, since it knows too
568 * much about the spine
569 */
570 if (s->nodes[0] != new_parent) {
571 unlock_block(s->info, s->nodes[0]);
572 s->nodes[0] = new_parent;
573 }
574 if (key < le64_to_cpu(rn->keys[0])) {
575 unlock_block(s->info, right);
576 s->nodes[1] = left;
577 } else {
578 unlock_block(s->info, left);
579 s->nodes[1] = right;
580 }
581 s->count = 2;
582
583 return 0;
584 }
585
586 static int btree_insert_raw(struct shadow_spine *s, dm_block_t root,
587 struct dm_btree_value_type *vt,
588 uint64_t key, unsigned *index)
589 {
590 int r, i = *index, inc, top = 1;
591 struct node *node;
592
593 for (;;) {
594 r = shadow_step(s, root, vt, &inc);
595 if (r < 0)
596 return r;
597
598 node = dm_block_data(shadow_current(s));
599 if (inc)
600 inc_children(s->info->tm, node, vt);
601
602 /*
603 * We have to patch up the parent node, ugly, but I don't
604 * see a way to do this automatically as part of the spine
605 * op.
606 */
607 if (shadow_has_parent(s) && i >= 0) { /* FIXME: second clause unness. */
608 __le64 location = cpu_to_le64(dm_block_location(shadow_current(s)));
609
610 __dm_bless_for_disk(&location);
611 memcpy_disk(value_ptr(dm_block_data(shadow_parent(s)), i, sizeof(uint64_t)),
612 &location, sizeof(__le64));
613 }
614
615 node = dm_block_data(shadow_current(s));
616
617 if (node->header.nr_entries == node->header.max_entries) {
618 if (top)
619 r = btree_split_beneath(s, key);
620 else
621 r = btree_split_sibling(s, root, i, key);
622
623 if (r < 0)
624 return r;
625 }
626
627 node = dm_block_data(shadow_current(s));
628
629 i = lower_bound(node, key);
630
631 if (le32_to_cpu(node->header.flags) & LEAF_NODE)
632 break;
633
634 if (i < 0) {
635 /* change the bounds on the lowest key */
636 node->keys[0] = cpu_to_le64(key);
637 i = 0;
638 }
639
640 root = value64(node, i);
641 top = 0;
642 }
643
644 if (i < 0 || le64_to_cpu(node->keys[i]) != key)
645 i++;
646
647 /* we're about to overwrite this value, so undo the increment for it */
648 /* FIXME: shame that inc information is leaking outside the spine.
649 * Plus inc is just plain wrong in the event of a split */
650 if (le64_to_cpu(node->keys[i]) == key && inc)
651 if (vt->dec)
652 vt->dec(vt->context, value_ptr(node, i, vt->size));
653
654 *index = i;
655 return 0;
656 }
657
658 static int insert(struct dm_btree_info *info, dm_block_t root,
659 uint64_t *keys, void *value, dm_block_t *new_root,
660 int *inserted)
661 __dm_written_to_disk(value)
662 {
663 int r, need_insert;
664 unsigned level, index = -1, last_level = info->levels - 1;
665 dm_block_t block = root;
666 struct shadow_spine spine;
667 struct node *n;
668 struct dm_btree_value_type le64_type;
669
670 le64_type.context = NULL;
671 le64_type.size = sizeof(__le64);
672 le64_type.inc = NULL;
673 le64_type.dec = NULL;
674 le64_type.equal = NULL;
675
676 init_shadow_spine(&spine, info);
677
678 for (level = 0; level < (info->levels - 1); level++) {
679 r = btree_insert_raw(&spine, block, &le64_type, keys[level], &index);
680 if (r < 0)
681 goto bad;
682
683 n = dm_block_data(shadow_current(&spine));
684 need_insert = ((index >= le32_to_cpu(n->header.nr_entries)) ||
685 (le64_to_cpu(n->keys[index]) != keys[level]));
686
687 if (need_insert) {
688 dm_block_t new_tree;
689 __le64 new_le;
690
691 r = dm_btree_create(info, &new_tree);
692 if (r < 0)
693 goto bad;
694
695 new_le = cpu_to_le64(new_tree);
696 __dm_bless_for_disk(&new_le);
697
698 r = insert_at(sizeof(uint64_t), n, index,
699 keys[level], &new_le);
700 if (r)
701 goto bad;
702 }
703
704 if (level < last_level)
705 block = value64(n, index);
706 }
707
708 r = btree_insert_raw(&spine, block, &info->value_type,
709 keys[level], &index);
710 if (r < 0)
711 goto bad;
712
713 n = dm_block_data(shadow_current(&spine));
714 need_insert = ((index >= le32_to_cpu(n->header.nr_entries)) ||
715 (le64_to_cpu(n->keys[index]) != keys[level]));
716
717 if (need_insert) {
718 if (inserted)
719 *inserted = 1;
720
721 r = insert_at(info->value_type.size, n, index,
722 keys[level], value);
723 if (r)
724 goto bad_unblessed;
725 } else {
726 if (inserted)
727 *inserted = 0;
728
729 if (info->value_type.dec &&
730 (!info->value_type.equal ||
731 !info->value_type.equal(
732 info->value_type.context,
733 value_ptr(n, index, info->value_type.size),
734 value))) {
735 info->value_type.dec(info->value_type.context,
736 value_ptr(n, index, info->value_type.size));
737 }
738 memcpy_disk(value_ptr(n, index, info->value_type.size),
739 value, info->value_type.size);
740 }
741
742 *new_root = shadow_root(&spine);
743 exit_shadow_spine(&spine);
744
745 return 0;
746
747 bad:
748 __dm_unbless_for_disk(value);
749 bad_unblessed:
750 exit_shadow_spine(&spine);
751 return r;
752 }
753
754 int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,
755 uint64_t *keys, void *value, dm_block_t *new_root)
756 __dm_written_to_disk(value)
757 {
758 return insert(info, root, keys, value, new_root, NULL);
759 }
760 EXPORT_SYMBOL_GPL(dm_btree_insert);
761
762 int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root,
763 uint64_t *keys, void *value, dm_block_t *new_root,
764 int *inserted)
765 __dm_written_to_disk(value)
766 {
767 return insert(info, root, keys, value, new_root, inserted);
768 }
769 EXPORT_SYMBOL_GPL(dm_btree_insert_notify);
770
771 /*----------------------------------------------------------------*/
772
773 int dm_btree_clone(struct dm_btree_info *info, dm_block_t root,
774 dm_block_t *clone)
775 {
776 int r;
777 struct dm_block *b, *orig_b;
778 struct node *b_node, *orig_node;
779
780 /* Copy the root node */
781 r = new_block(info, &b);
782 if (r < 0)
783 return r;
784
785 r = dm_tm_read_lock(info->tm, root, &btree_node_validator, &orig_b);
786 if (r < 0) {
787 dm_block_t location = dm_block_location(b);
788
789 unlock_block(info, b);
790 dm_tm_dec(info->tm, location);
791 }
792
793 *clone = dm_block_location(b);
794 b_node = dm_block_data(b);
795 orig_node = dm_block_data(orig_b);
796
797 memcpy(b_node, orig_node,
798 dm_bm_block_size(dm_tm_get_bm(info->tm)));
799 dm_tm_unlock(info->tm, orig_b);
800 inc_children(info->tm, b_node, &info->value_type);
801 dm_tm_unlock(info->tm, b);
802
803 return 0;
804 }
805 EXPORT_SYMBOL_GPL(dm_btree_clone);
806
807 /*----------------------------------------------------------------*/
808
809 static int find_highest_key(struct ro_spine *s, dm_block_t block,
810 uint64_t *result_key, dm_block_t *next_block)
811 {
812 int i, r;
813 uint32_t flags;
814
815 do {
816 r = ro_step(s, block);
817 if (r < 0)
818 return r;
819
820 flags = le32_to_cpu(ro_node(s)->header.flags);
821 i = le32_to_cpu(ro_node(s)->header.nr_entries);
822 if (!i)
823 return -ENODATA;
824 else
825 i--;
826
827 *result_key = le64_to_cpu(ro_node(s)->keys[i]);
828 if (next_block || flags & INTERNAL_NODE)
829 block = value64(ro_node(s), i);
830
831 } while (flags & INTERNAL_NODE);
832
833 if (next_block)
834 *next_block = block;
835 return 0;
836 }
837
838 int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
839 uint64_t *result_keys)
840 {
841 int r = 0, count = 0, level;
842 struct ro_spine spine;
843
844 init_ro_spine(&spine, info);
845 for (level = 0; level < info->levels; level++) {
846 r = find_highest_key(&spine, root, result_keys + level,
847 level == info->levels - 1 ? NULL : &root);
848 if (r == -ENODATA) {
849 r = 0;
850 break;
851
852 } else if (r)
853 break;
854
855 count++;
856 }
857 exit_ro_spine(&spine);
858
859 return r ? r : count;
860 }
861 EXPORT_SYMBOL_GPL(dm_btree_find_highest_key);
linux-next