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