Fix build breakage occuring when INVARIANTS not defined and introduced
[dragonfly.git] / sys / vfs / hammer / hammer_btree.c
CommitLineData
427e5fc6
MD
1/*
2 * Copyright (c) 2007 The DragonFly Project. All rights reserved.
3 *
4 * This code is derived from software contributed to The DragonFly Project
5 * by Matthew Dillon <dillon@backplane.com>
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 *
eaeff70d 34 * $DragonFly: src/sys/vfs/hammer/hammer_btree.c,v 1.22 2008/01/21 00:00:19 dillon Exp $
427e5fc6
MD
35 */
36
37/*
8cd0a023 38 * HAMMER B-Tree index
427e5fc6
MD
39 *
40 * HAMMER implements a modified B+Tree. In documentation this will
9944ae54 41 * simply be refered to as the HAMMER B-Tree. Basically a HAMMER B-Tree
427e5fc6
MD
42 * looks like a B+Tree (A B-Tree which stores its records only at the leafs
43 * of the tree), but adds two additional boundary elements which describe
44 * the left-most and right-most element a node is able to represent. In
8cd0a023 45 * otherwords, we have boundary elements at the two ends of a B-Tree node
427e5fc6
MD
46 * instead of sub-tree pointers.
47 *
8cd0a023 48 * A B-Tree internal node looks like this:
427e5fc6
MD
49 *
50 * B N N N N N N B <-- boundary and internal elements
51 * S S S S S S S <-- subtree pointers
52 *
8cd0a023 53 * A B-Tree leaf node basically looks like this:
427e5fc6
MD
54 *
55 * L L L L L L L L <-- leaf elemenets
56 *
8cd0a023
MD
57 * The radix for an internal node is 1 less then a leaf but we get a
58 * number of significant benefits for our troubles.
427e5fc6 59 *
8cd0a023
MD
60 * The big benefit to using a B-Tree containing boundary information
61 * is that it is possible to cache pointers into the middle of the tree
62 * and not have to start searches, insertions, OR deletions at the root
63 * node. In particular, searches are able to progress in a definitive
64 * direction from any point in the tree without revisting nodes. This
65 * greatly improves the efficiency of many operations, most especially
66 * record appends.
427e5fc6 67 *
8cd0a023
MD
68 * B-Trees also make the stacking of trees fairly straightforward.
69 *
eaeff70d
MD
70 * SPIKES: Two leaf elements denoting a sub-range of keys may represent
71 * a spike, or a recursion into another cluster. Most standard B-Tree
72 * searches traverse spikes. The ending spike element is range-exclusive
73 * and operates like a right-bound. Thus it may exactly match a record
74 * element directly following it.
8cd0a023 75 *
fe7678ee
MD
76 * INSERTIONS: A search performed with the intention of doing
77 * an insert will guarantee that the terminal leaf node is not full by
78 * splitting full nodes. Splits occur top-down during the dive down the
79 * B-Tree.
80 *
81 * DELETIONS: A deletion makes no attempt to proactively balance the
82 * tree and will recursively remove nodes that become empty. Empty
83 * nodes are not allowed and a deletion may recurse upwards from the leaf.
84 * Rather then allow a deadlock a deletion may terminate early by setting
85 * an internal node's element's subtree_offset to 0. The deletion will
86 * then be resumed the next time a search encounters the element.
8cd0a023
MD
87 */
88#include "hammer.h"
89#include <sys/buf.h>
90#include <sys/buf2.h>
66325755 91
8cd0a023
MD
92static int btree_search(hammer_cursor_t cursor, int flags);
93static int btree_split_internal(hammer_cursor_t cursor);
94static int btree_split_leaf(hammer_cursor_t cursor);
6a37e7e4
MD
95static int btree_remove(hammer_cursor_t cursor, int depth);
96static int btree_remove_deleted_element(hammer_cursor_t cursor);
7f7c1f84 97static int btree_set_parent(hammer_node_t node, hammer_btree_elm_t elm);
9944ae54 98static int btree_node_is_almost_full(hammer_node_ondisk_t node);
fe7678ee 99static int btree_node_is_full(hammer_node_ondisk_t node);
8cd0a023
MD
100static void hammer_make_separator(hammer_base_elm_t key1,
101 hammer_base_elm_t key2, hammer_base_elm_t dest);
66325755
MD
102
103/*
8cd0a023
MD
104 * Iterate records after a search. The cursor is iterated forwards past
105 * the current record until a record matching the key-range requirements
106 * is found. ENOENT is returned if the iteration goes past the ending
6a37e7e4 107 * key.
66325755 108 *
d26d0ae9
MD
109 * The iteration is inclusive of key_beg and can be inclusive or exclusive
110 * of key_end depending on whether HAMMER_CURSOR_END_INCLUSIVE is set.
66325755 111 *
eaeff70d
MD
112 * When doing an as-of search (cursor->asof != 0), key_beg.create_tid
113 * and key_beg.delete_tid may be modified by B-Tree functions.
d5530d22 114 *
8cd0a023 115 * cursor->key_beg may or may not be modified by this function during
d26d0ae9
MD
116 * the iteration. XXX future - in case of an inverted lock we may have
117 * to reinitiate the lookup and set key_beg to properly pick up where we
118 * left off.
6a37e7e4
MD
119 *
120 * NOTE! EDEADLK *CANNOT* be returned by this procedure.
66325755
MD
121 */
122int
8cd0a023 123hammer_btree_iterate(hammer_cursor_t cursor)
66325755 124{
8cd0a023
MD
125 hammer_node_ondisk_t node;
126 hammer_btree_elm_t elm;
66325755
MD
127 int error;
128 int r;
129 int s;
130
131 /*
8cd0a023 132 * Skip past the current record
66325755 133 */
8cd0a023 134 node = cursor->node->ondisk;
a89aec1b
MD
135 if (node == NULL)
136 return(ENOENT);
c0ade690
MD
137 if (cursor->index < node->count &&
138 (cursor->flags & HAMMER_CURSOR_ATEDISK)) {
66325755 139 ++cursor->index;
c0ade690 140 }
66325755 141
8cd0a023
MD
142 /*
143 * Loop until an element is found or we are done.
144 */
66325755
MD
145 for (;;) {
146 /*
8cd0a023
MD
147 * We iterate up the tree and then index over one element
148 * while we are at the last element in the current node.
149 *
150 * NOTE: This can pop us up to another cluster.
66325755 151 *
8cd0a023
MD
152 * If we are at the root of the root cluster, cursor_up
153 * returns ENOENT.
154 *
155 * NOTE: hammer_cursor_up() will adjust cursor->key_beg
156 * when told to re-search for the cluster tag.
66325755
MD
157 *
158 * XXX this could be optimized by storing the information in
159 * the parent reference.
195c19a1
MD
160 *
161 * XXX we can lose the node lock temporarily, this could mess
162 * up our scan.
66325755 163 */
8cd0a023 164 if (cursor->index == node->count) {
6a37e7e4 165 error = hammer_cursor_up(cursor);
8cd0a023
MD
166 if (error)
167 break;
168 node = cursor->node->ondisk;
169 KKASSERT(cursor->index != node->count);
170 ++cursor->index;
171 continue;
66325755
MD
172 }
173
174 /*
d26d0ae9
MD
175 * Check internal or leaf element. Determine if the record
176 * at the cursor has gone beyond the end of our range.
66325755 177 *
d26d0ae9
MD
178 * Generally we recurse down through internal nodes. An
179 * internal node can only be returned if INCLUSTER is set
d5530d22 180 * and the node represents a cluster-push record.
66325755 181 */
8cd0a023
MD
182 if (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
183 elm = &node->elms[cursor->index];
d26d0ae9
MD
184 r = hammer_btree_cmp(&cursor->key_end, &elm[0].base);
185 s = hammer_btree_cmp(&cursor->key_beg, &elm[1].base);
b3deaf57 186 if (hammer_debug_btree) {
eaeff70d
MD
187 kprintf("BRACKETL %d:%d:%08x[%d] %016llx %02x %016llx %d\n",
188 cursor->node->cluster->volume->vol_no,
189 cursor->node->cluster->clu_no,
190 cursor->node->node_offset,
191 cursor->index,
b3deaf57
MD
192 elm[0].internal.base.obj_id,
193 elm[0].internal.base.rec_type,
194 elm[0].internal.base.key,
195 r
196 );
eaeff70d
MD
197 kprintf("BRACKETR %d:%d:%08x[%d] %016llx %02x %016llx %d\n",
198 cursor->node->cluster->volume->vol_no,
199 cursor->node->cluster->clu_no,
200 cursor->node->node_offset,
201 cursor->index + 1,
b3deaf57
MD
202 elm[1].internal.base.obj_id,
203 elm[1].internal.base.rec_type,
204 elm[1].internal.base.key,
205 s
206 );
207 }
208
d26d0ae9
MD
209 if (r < 0) {
210 error = ENOENT;
211 break;
66325755 212 }
fe7678ee
MD
213 if (r == 0 && (cursor->flags &
214 HAMMER_CURSOR_END_INCLUSIVE) == 0) {
d26d0ae9 215 error = ENOENT;
8cd0a023 216 break;
d26d0ae9
MD
217 }
218 KKASSERT(s <= 0);
6a37e7e4
MD
219
220 /*
221 * When iterating try to clean up any deleted
222 * internal elements left over from btree_remove()
223 * deadlocks, but it is ok if we can't.
224 */
225 if (elm->internal.subtree_offset == 0)
226 btree_remove_deleted_element(cursor);
227 if (elm->internal.subtree_offset != 0) {
228 error = hammer_cursor_down(cursor);
229 if (error)
230 break;
231 KKASSERT(cursor->index == 0);
232 node = cursor->node->ondisk;
233 }
fe7678ee 234 continue;
d26d0ae9
MD
235 } else {
236 elm = &node->elms[cursor->index];
237 r = hammer_btree_cmp(&cursor->key_end, &elm->base);
b3deaf57 238 if (hammer_debug_btree) {
eaeff70d
MD
239 kprintf("ELEMENT %d:%d:%08x:%d %c %016llx %02x %016llx %d\n",
240 cursor->node->cluster->volume->vol_no,
241 cursor->node->cluster->clu_no,
242 cursor->node->node_offset,
243 cursor->index,
244 (elm[0].leaf.base.btype ?
245 elm[0].leaf.base.btype : '?'),
b3deaf57
MD
246 elm[0].leaf.base.obj_id,
247 elm[0].leaf.base.rec_type,
248 elm[0].leaf.base.key,
249 r
250 );
251 }
d26d0ae9
MD
252 if (r < 0) {
253 error = ENOENT;
254 break;
255 }
fe7678ee
MD
256 switch(elm->leaf.base.btype) {
257 case HAMMER_BTREE_TYPE_RECORD:
eaeff70d
MD
258 /*
259 * We support both end-inclusive and
260 * end-exclusive searches.
261 */
262 if (r == 0 &&
263 (cursor->flags &
264 HAMMER_CURSOR_END_INCLUSIVE) == 0) {
265 error = ENOENT;
266 break;
267 }
fe7678ee
MD
268 if ((cursor->flags & HAMMER_CURSOR_ASOF) &&
269 hammer_btree_chkts(cursor->asof, &elm->base)) {
270 ++cursor->index;
271 continue;
272 }
273 break;
274 case HAMMER_BTREE_TYPE_SPIKE_BEG:
eaeff70d
MD
275 /*
276 * We support both end-inclusive and
277 * end-exclusive searches.
278 *
279 * NOTE: This code assumes that the spike
280 * ending element immediately follows the
281 * spike beginning element.
282 */
283 if (r == 0 &&
284 (cursor->flags &
285 HAMMER_CURSOR_END_INCLUSIVE) == 0) {
286 error = ENOENT;
287 break;
288 }
fe7678ee
MD
289 /*
290 * We must cursor-down via the SPIKE_END
291 * element, otherwise cursor->parent will
292 * not be set correctly for deletions.
eaeff70d
MD
293 *
294 * fall-through to avoid an improper
295 * termination from the conditional above.
fe7678ee
MD
296 */
297 KKASSERT(cursor->index + 1 < node->count);
eaeff70d
MD
298 ++elm;
299 KKASSERT(elm->leaf.base.btype ==
300 HAMMER_BTREE_TYPE_SPIKE_END);
d26d0ae9 301 ++cursor->index;
fe7678ee
MD
302 /* fall through */
303 case HAMMER_BTREE_TYPE_SPIKE_END:
eaeff70d
MD
304 /*
305 * The SPIKE_END element is non-inclusive,
306 * just like a boundary, so if we match it
307 * there's no point pushing down. It is
308 * possible for an exactly matching element
309 * to follow it, however. Either stop
310 * or continue the iteration.
311 */
312 if (r == 0) {
313 if ((cursor->flags &
314 HAMMER_CURSOR_END_INCLUSIVE) == 0) {
315 error = ENOENT;
316 break;
317 }
318 continue;
319 }
320
fe7678ee
MD
321 if (cursor->flags & HAMMER_CURSOR_INCLUSTER)
322 break;
323 error = hammer_cursor_down(cursor);
324 if (error)
325 break;
326 KKASSERT(cursor->index == 0);
327 node = cursor->node->ondisk;
d26d0ae9 328 continue;
fe7678ee
MD
329 default:
330 error = EINVAL;
331 break;
d26d0ae9 332 }
fe7678ee
MD
333 if (error)
334 break;
66325755
MD
335 }
336
337 /*
d26d0ae9 338 * Return entry
66325755 339 */
b3deaf57
MD
340 if (hammer_debug_btree) {
341 int i = cursor->index;
342 hammer_btree_elm_t elm = &cursor->node->ondisk->elms[i];
343 kprintf("ITERATE %p:%d %016llx %02x %016llx\n",
344 cursor->node, i,
345 elm->internal.base.obj_id,
346 elm->internal.base.rec_type,
347 elm->internal.base.key
348 );
349 }
d26d0ae9 350 return(0);
427e5fc6 351 }
66325755 352 return(error);
427e5fc6
MD
353}
354
355/*
8cd0a023 356 * Lookup cursor->key_beg. 0 is returned on success, ENOENT if the entry
6a37e7e4
MD
357 * could not be found, EDEADLK if inserting and a retry is needed, and a
358 * fatal error otherwise. When retrying, the caller must terminate the
eaeff70d 359 * cursor and reinitialize it. EDEADLK cannot be returned if not inserting.
8cd0a023
MD
360 *
361 * The cursor is suitably positioned for a deletion on success, and suitably
eaeff70d
MD
362 * positioned for an insertion on ENOENT if HAMMER_CURSOR_INSERT was
363 * specified.
427e5fc6 364 *
8cd0a023
MD
365 * The cursor may begin anywhere, the search will traverse clusters in
366 * either direction to locate the requested element.
eaeff70d
MD
367 *
368 * Most of the logic implementing historical searches is handled here. We
369 * do an initial lookup with delete_tid set to the asof TID. Due to the
370 * way records are laid out, a forwards iteration may be required if
371 * ENOENT is returned to locate the historical record. Here's the
372 * problem:
373 *
374 * delete_tid: 10 15 20
375 * LEAF1 LEAF2
376 * records: (11) (18)
377 *
378 * Lets say we want to do a lookup AS-OF timestamp 12. We will traverse
379 * LEAF1 but the only record in LEAF1 has a termination (delete_tid) of 11,
380 * thus causing ENOENT to be returned. We really need to check record 18
381 * in LEAF2. If it also fails then the search fails (e.g. it might represent
382 * the range 14-18 and thus still not match our AS-OF timestamp of 12).
427e5fc6
MD
383 */
384int
8cd0a023 385hammer_btree_lookup(hammer_cursor_t cursor)
427e5fc6 386{
66325755
MD
387 int error;
388
d5530d22 389 if (cursor->flags & HAMMER_CURSOR_ASOF) {
eaeff70d
MD
390 KKASSERT((cursor->flags & HAMMER_CURSOR_INSERT) == 0);
391
d5530d22 392 cursor->key_beg.delete_tid = cursor->asof;
eaeff70d 393 for (;;) {
d5530d22 394 error = btree_search(cursor, 0);
eaeff70d
MD
395 if (error != ENOENT)
396 break;
397
398 /*
399 * ENOENT needs special handling, we may have gone
400 * the tree to the left of a matching record because
401 * any record with (delete_tid > asof) can potentially
402 * match.
403 *
404 * If we are AT a non-matching record we can stop,
405 * but if we are at a right-edge we have to loop.
406 * Since deletions don't always succeed completely
407 * we can wind up going through several empty nodes.
408 *
409 * NOTE: we can be at a leaf OR an internal node
410 * here, because we aren't inserting.
411 */
412 if (cursor->index != cursor->node->ondisk->count)
413 break;
414 if (cursor->key_beg.obj_id !=
415 cursor->right_bound->obj_id ||
416 cursor->key_beg.rec_type !=
417 cursor->right_bound->rec_type ||
418 cursor->key_beg.key !=
419 cursor->right_bound->key
420 ) {
421 break;
422 }
423 cursor->key_beg.delete_tid =
424 cursor->right_bound->delete_tid;
425 /* loop */
426 }
d5530d22
MD
427 } else {
428 error = btree_search(cursor, 0);
429 }
8cd0a023
MD
430 if (error == 0 && cursor->flags)
431 error = hammer_btree_extract(cursor, cursor->flags);
66325755
MD
432 return(error);
433}
434
d26d0ae9
MD
435/*
436 * Execute the logic required to start an iteration. The first record
437 * located within the specified range is returned and iteration control
438 * flags are adjusted for successive hammer_btree_iterate() calls.
439 */
440int
441hammer_btree_first(hammer_cursor_t cursor)
442{
443 int error;
444
445 error = hammer_btree_lookup(cursor);
446 if (error == ENOENT) {
447 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
448 error = hammer_btree_iterate(cursor);
449 }
450 cursor->flags |= HAMMER_CURSOR_ATEDISK;
451 return(error);
452}
453
8cd0a023
MD
454/*
455 * Extract the record and/or data associated with the cursor's current
456 * position. Any prior record or data stored in the cursor is replaced.
457 * The cursor must be positioned at a leaf node.
458 *
d26d0ae9
MD
459 * NOTE: Most extractions occur at the leaf of the B-Tree. The only
460 * extraction allowed at an internal element is at a cluster-push.
461 * Cluster-push elements have records but no data.
8cd0a023 462 */
66325755 463int
8cd0a023 464hammer_btree_extract(hammer_cursor_t cursor, int flags)
66325755 465{
8cd0a023
MD
466 hammer_node_ondisk_t node;
467 hammer_btree_elm_t elm;
468 hammer_cluster_t cluster;
c0ade690 469 u_int64_t buf_type;
427e5fc6 470 int32_t cloff;
d26d0ae9 471 int32_t roff;
427e5fc6 472 int error;
427e5fc6 473
8cd0a023 474 /*
427e5fc6 475 * A cluster record type has no data reference, the information
8cd0a023 476 * is stored directly in the record and B-Tree element.
427e5fc6
MD
477 *
478 * The case where the data reference resolves to the same buffer
479 * as the record reference must be handled.
480 */
8cd0a023 481 node = cursor->node->ondisk;
8cd0a023
MD
482 elm = &node->elms[cursor->index];
483 cluster = cursor->node->cluster;
d26d0ae9
MD
484 cursor->flags &= ~HAMMER_CURSOR_DATA_EMBEDDED;
485 cursor->data = NULL;
66325755 486
d26d0ae9 487 /*
fe7678ee 488 * There is nothing to extract for an internal element.
d26d0ae9 489 */
fe7678ee
MD
490 if (node->type == HAMMER_BTREE_TYPE_INTERNAL)
491 return(EINVAL);
492
493 KKASSERT(node->type == HAMMER_BTREE_TYPE_LEAF);
d26d0ae9
MD
494
495 /*
496 * Leaf element.
497 */
fe7678ee 498 if ((flags & HAMMER_CURSOR_GET_RECORD)) {
8cd0a023
MD
499 cloff = elm->leaf.rec_offset;
500 cursor->record = hammer_bread(cluster, cloff,
501 HAMMER_FSBUF_RECORDS, &error,
502 &cursor->record_buffer);
427e5fc6
MD
503 } else {
504 cloff = 0;
fe7678ee 505 error = 0;
427e5fc6 506 }
a89aec1b 507 if ((flags & HAMMER_CURSOR_GET_DATA) && error == 0) {
fe7678ee
MD
508 if (elm->leaf.base.btype != HAMMER_BTREE_TYPE_RECORD) {
509 /*
510 * Only records have data references. Spike elements
511 * do not.
512 */
513 cursor->data = NULL;
514 } else if ((cloff ^ elm->leaf.data_offset) & ~HAMMER_BUFMASK) {
8cd0a023 515 /*
c0ade690
MD
516 * The data is not in the same buffer as the last
517 * record we cached, but it could still be embedded
518 * in a record. Note that we may not have loaded the
519 * record's buffer above, depending on flags.
8cd0a023 520 */
c0ade690
MD
521 if ((elm->leaf.rec_offset ^ elm->leaf.data_offset) &
522 ~HAMMER_BUFMASK) {
523 if (elm->leaf.data_len & HAMMER_BUFMASK)
524 buf_type = HAMMER_FSBUF_DATA;
525 else
526 buf_type = 0; /* pure data buffer */
527 } else {
528 buf_type = HAMMER_FSBUF_RECORDS;
529 }
8cd0a023
MD
530 cursor->data = hammer_bread(cluster,
531 elm->leaf.data_offset,
c0ade690 532 buf_type, &error,
8cd0a023 533 &cursor->data_buffer);
427e5fc6 534 } else {
8cd0a023
MD
535 /*
536 * Data in same buffer as record. Note that we
537 * leave any existing data_buffer intact, even
538 * though we don't use it in this case, in case
539 * other records extracted during an iteration
540 * go back to it.
c0ade690 541 *
d26d0ae9
MD
542 * The data must be embedded in the record for this
543 * case to be hit.
544 *
c0ade690 545 * Just assume the buffer type is correct.
8cd0a023
MD
546 */
547 cursor->data = (void *)
548 ((char *)cursor->record_buffer->ondisk +
549 (elm->leaf.data_offset & HAMMER_BUFMASK));
d26d0ae9
MD
550 roff = (char *)cursor->data - (char *)cursor->record;
551 KKASSERT (roff >= 0 && roff < HAMMER_RECORD_SIZE);
552 cursor->flags |= HAMMER_CURSOR_DATA_EMBEDDED;
427e5fc6
MD
553 }
554 }
555 return(error);
556}
557
558
559/*
8cd0a023
MD
560 * Insert a leaf element into the B-Tree at the current cursor position.
561 * The cursor is positioned such that the element at and beyond the cursor
562 * are shifted to make room for the new record.
563 *
a89aec1b 564 * The caller must call hammer_btree_lookup() with the HAMMER_CURSOR_INSERT
8cd0a023
MD
565 * flag set and that call must return ENOENT before this function can be
566 * called.
567 *
568 * ENOSPC is returned if there is no room to insert a new record.
427e5fc6
MD
569 */
570int
8cd0a023 571hammer_btree_insert(hammer_cursor_t cursor, hammer_btree_elm_t elm)
427e5fc6 572{
8cd0a023 573 hammer_node_ondisk_t node;
427e5fc6 574 int i;
6a37e7e4
MD
575 int error;
576
577 if ((error = hammer_cursor_upgrade(cursor)) != 0)
578 return(error);
427e5fc6 579
427e5fc6
MD
580 /*
581 * Insert the element at the leaf node and update the count in the
582 * parent. It is possible for parent to be NULL, indicating that
8cd0a023 583 * the root of the B-Tree in the cluster is a leaf. It is also
427e5fc6
MD
584 * possible for the leaf to be empty.
585 *
586 * Remember that the right-hand boundary is not included in the
587 * count.
588 */
0b075555 589 hammer_modify_node(cursor->node);
8cd0a023 590 node = cursor->node->ondisk;
427e5fc6 591 i = cursor->index;
fe7678ee 592 KKASSERT(elm->base.btype != 0);
8cd0a023
MD
593 KKASSERT(node->type == HAMMER_BTREE_TYPE_LEAF);
594 KKASSERT(node->count < HAMMER_BTREE_LEAF_ELMS);
595 if (i != node->count) {
596 bcopy(&node->elms[i], &node->elms[i+1],
597 (node->count - i) * sizeof(*elm));
598 }
599 node->elms[i] = *elm;
600 ++node->count;
427e5fc6 601
eaeff70d
MD
602 /*
603 * Debugging sanity checks. Note that the element to the left
604 * can match the element we are inserting if it is a SPIKE_END,
605 * because spike-end's represent a non-inclusive end to a range.
606 */
b3deaf57
MD
607 KKASSERT(hammer_btree_cmp(cursor->left_bound, &elm->leaf.base) <= 0);
608 KKASSERT(hammer_btree_cmp(cursor->right_bound, &elm->leaf.base) > 0);
eaeff70d
MD
609 if (i) {
610 if (node->elms[i-1].base.btype == HAMMER_BTREE_TYPE_SPIKE_END){
611 KKASSERT(hammer_btree_cmp(&node->elms[i-1].leaf.base, &elm->leaf.base) <= 0);
612 } else {
613 KKASSERT(hammer_btree_cmp(&node->elms[i-1].leaf.base, &elm->leaf.base) < 0);
614 }
615 }
b3deaf57
MD
616 if (i != node->count - 1)
617 KKASSERT(hammer_btree_cmp(&node->elms[i+1].leaf.base, &elm->leaf.base) > 0);
618
427e5fc6
MD
619 return(0);
620}
621
9944ae54 622/*
eaeff70d
MD
623 * Insert a cluster spike into the B-Tree at the current cursor position.
624 * The caller pre-positions the insertion cursor at ncluster's
625 * left bound in the originating cluster. Both the originating cluster
626 * and the target cluster must be serialized, EDEADLK is fatal.
9944ae54 627 *
eaeff70d
MD
628 * Basically we have to lay down the two spike elements and assert that
629 * the leaf's right bound does not bisect the ending element. The ending
630 * spike element is non-inclusive, just like a boundary.
9944ae54 631 *
eaeff70d
MD
632 * NOTE: Serialization is usually accoplished by virtue of being the
633 * initial accessor of a cluster.
9944ae54
MD
634 */
635int
636hammer_btree_insert_cluster(hammer_cursor_t cursor, hammer_cluster_t ncluster,
637 int32_t rec_offset)
638{
9944ae54 639 hammer_node_ondisk_t node;
9944ae54
MD
640 hammer_btree_elm_t elm;
641 const int esize = sizeof(*elm);
6a37e7e4 642 int error;
eaeff70d 643 int i;
9944ae54 644
6a37e7e4
MD
645 if ((error = hammer_cursor_upgrade(cursor)) != 0)
646 return(error);
9944ae54 647 hammer_modify_node(cursor->node);
eaeff70d 648 hammer_modify_cluster(ncluster);
9944ae54
MD
649 node = cursor->node->ondisk;
650 i = cursor->index;
eaeff70d 651
9944ae54 652 KKASSERT(node->type == HAMMER_BTREE_TYPE_LEAF);
eaeff70d
MD
653 KKASSERT(node->count <= HAMMER_BTREE_LEAF_ELMS - 2);
654 KKASSERT(i >= 0 && i <= node->count);
9944ae54
MD
655
656 /*
657 * Make sure the spike is legal or the B-Tree code will get really
658 * confused.
eaeff70d
MD
659 *
660 * XXX the right bound my bisect the two spike elements. We
661 * need code here to 'fix' the right bound going up the tree
662 * instead of an assertion.
9944ae54
MD
663 */
664 KKASSERT(hammer_btree_cmp(&ncluster->ondisk->clu_btree_beg,
665 cursor->left_bound) >= 0);
666 KKASSERT(hammer_btree_cmp(&ncluster->ondisk->clu_btree_end,
667 cursor->right_bound) <= 0);
668 if (i != node->count) {
669 KKASSERT(hammer_btree_cmp(&ncluster->ondisk->clu_btree_end,
670 &node->elms[i].leaf.base) <= 0);
671 }
672
eaeff70d 673 ncluster->ondisk->clu_btree_parent_offset = cursor->node->node_offset;
9944ae54 674
eaeff70d
MD
675 elm = &node->elms[i];
676 bcopy(elm, elm + 2, (node->count - i) * esize);
677 bzero(elm, 2 * esize);
678 node->count += 2;
9944ae54 679
eaeff70d
MD
680 elm[0].leaf.base = ncluster->ondisk->clu_btree_beg;
681 elm[0].leaf.base.btype = HAMMER_BTREE_TYPE_SPIKE_BEG;
682 elm[0].leaf.spike_clu_no = ncluster->clu_no;
683 elm[0].leaf.spike_vol_no = ncluster->volume->vol_no;
9944ae54 684
eaeff70d
MD
685 elm[1].leaf.base = ncluster->ondisk->clu_btree_end;
686 elm[1].leaf.base.btype = HAMMER_BTREE_TYPE_SPIKE_END;
687 elm[1].leaf.spike_clu_no = ncluster->clu_no;
688 elm[1].leaf.spike_vol_no = ncluster->volume->vol_no;
9944ae54
MD
689 return(0);
690}
691
427e5fc6 692/*
fe7678ee 693 * Delete a record from the B-Tree at the current cursor position.
8cd0a023
MD
694 * The cursor is positioned such that the current element is the one
695 * to be deleted.
696 *
195c19a1
MD
697 * On return the cursor will be positioned after the deleted element and
698 * MAY point to an internal node. It will be suitable for the continuation
699 * of an iteration but not for an insertion or deletion.
8cd0a023 700 *
195c19a1 701 * Deletions will attempt to partially rebalance the B-Tree in an upward
fe7678ee
MD
702 * direction, but will terminate rather then deadlock. Empty leaves are
703 * not allowed except at the root node of a cluster. An early termination
704 * will leave an internal node with an element whos subtree_offset is 0,
705 * a case detected and handled by btree_search().
427e5fc6
MD
706 */
707int
8cd0a023 708hammer_btree_delete(hammer_cursor_t cursor)
427e5fc6 709{
8cd0a023
MD
710 hammer_node_ondisk_t ondisk;
711 hammer_node_t node;
712 hammer_node_t parent;
8cd0a023 713 int error;
427e5fc6
MD
714 int i;
715
6a37e7e4
MD
716 if ((error = hammer_cursor_upgrade(cursor)) != 0)
717 return(error);
718
427e5fc6 719 /*
8cd0a023 720 * Delete the element from the leaf node.
427e5fc6 721 *
8cd0a023 722 * Remember that leaf nodes do not have boundaries.
427e5fc6 723 */
8cd0a023
MD
724 node = cursor->node;
725 ondisk = node->ondisk;
427e5fc6
MD
726 i = cursor->index;
727
8cd0a023 728 KKASSERT(ondisk->type == HAMMER_BTREE_TYPE_LEAF);
fe7678ee 729 KKASSERT(i >= 0 && i < ondisk->count);
0b075555 730 hammer_modify_node(node);
8cd0a023
MD
731 if (i + 1 != ondisk->count) {
732 bcopy(&ondisk->elms[i+1], &ondisk->elms[i],
733 (ondisk->count - i - 1) * sizeof(ondisk->elms[0]));
734 }
735 --ondisk->count;
fe7678ee
MD
736
737 /*
738 * Validate local parent
739 */
740 if (ondisk->parent) {
8cd0a023 741 parent = cursor->parent;
fe7678ee
MD
742
743 KKASSERT(parent != NULL);
744 KKASSERT(parent->node_offset == ondisk->parent);
745 KKASSERT(parent->cluster == node->cluster);
427e5fc6 746 }
427e5fc6 747
8cd0a023 748 /*
fe7678ee
MD
749 * If the leaf becomes empty it must be detached from the parent,
750 * potentially recursing through to the cluster root.
195c19a1
MD
751 *
752 * This may reposition the cursor at one of the parent's of the
753 * current node.
6a37e7e4
MD
754 *
755 * Ignore deadlock errors, that simply means that btree_remove
756 * was unable to recurse and had to leave the subtree_offset
757 * in the parent set to 0.
8cd0a023 758 */
b3deaf57 759 KKASSERT(cursor->index <= ondisk->count);
8cd0a023 760 if (ondisk->count == 0) {
fe7678ee 761 do {
6a37e7e4 762 error = btree_remove(cursor, 0);
fe7678ee 763 } while (error == EAGAIN);
6a37e7e4
MD
764 if (error == EDEADLK)
765 error = 0;
8cd0a023 766 } else {
8cd0a023
MD
767 error = 0;
768 }
eaeff70d
MD
769 KKASSERT(cursor->parent == NULL ||
770 cursor->parent_index < cursor->parent->ondisk->count);
8cd0a023
MD
771 return(error);
772}
427e5fc6
MD
773
774/*
8cd0a023
MD
775 * PRIMAY B-TREE SEARCH SUPPORT PROCEDURE
776 *
777 * Search a cluster's B-Tree for cursor->key_beg, return the matching node.
778 *
d26d0ae9
MD
779 * The search can begin ANYWHERE in the B-Tree. As a first step the search
780 * iterates up the tree as necessary to properly position itself prior to
781 * actually doing the sarch.
782 *
8cd0a023 783 * INSERTIONS: The search will split full nodes and leaves on its way down
d26d0ae9
MD
784 * and guarentee that the leaf it ends up on is not full. If we run out
785 * of space the search continues to the leaf (to position the cursor for
786 * the spike), but ENOSPC is returned.
427e5fc6 787 *
fbc6e32a
MD
788 * The search is only guarenteed to end up on a leaf if an error code of 0
789 * is returned, or if inserting and an error code of ENOENT is returned.
d26d0ae9
MD
790 * Otherwise it can stop at an internal node. On success a search returns
791 * a leaf node unless INCLUSTER is set and the search located a cluster push
792 * node (which is an internal node).
eaeff70d
MD
793 *
794 * COMPLEXITY WARNING! This is the core B-Tree search code for the entire
795 * filesystem, and it is not simple code. Please note the following facts:
796 *
797 * - Internal node recursions have a boundary on the left AND right. The
798 * right boundary is non-inclusive. The delete_tid is a generic part
799 * of the key for internal nodes.
800 *
801 * - Leaf nodes contain terminal elements AND spikes. A spike recurses into
802 * another cluster and contains two leaf elements.. a beginning and an
803 * ending element. The SPIKE_END element is RANGE-EXCLUSIVE, just like a
804 * boundary. This means that it is possible to have two elements
805 * (a spike ending element and a record) side by side with the same key.
806 *
807 * - Because the SPIKE_END element is range exclusive, it can match the
808 * right boundary of the parent node. SPIKE_BEG and SPIKE_END elements
809 * always come in pairs, and always exist side by side in the same leaf.
810 *
811 * - Filesystem lookups typically set HAMMER_CURSOR_ASOF, indicating a
812 * historical search. This is true for current lookups too. Raw B-Tree
813 * operations such as insertions and recovery scans typically do NOT
814 * set this flag. When the flag is not set, create_tid and delete_tid
815 * are considered to be a generic part of the key for internal nodes.
816 *
817 * When the flag IS set the search code must check whether the record
818 * is actually visible to the search or not. btree_lookup() will also
819 * use failed results to poke around if necessary to locate the correct
820 * record.
427e5fc6 821 */
8cd0a023 822static
427e5fc6 823int
8cd0a023 824btree_search(hammer_cursor_t cursor, int flags)
427e5fc6 825{
8cd0a023
MD
826 hammer_node_ondisk_t node;
827 hammer_cluster_t cluster;
61aeeb33 828 hammer_btree_elm_t elm;
8cd0a023 829 int error;
d26d0ae9 830 int enospc = 0;
8cd0a023
MD
831 int i;
832 int r;
833
834 flags |= cursor->flags;
835
b3deaf57 836 if (hammer_debug_btree) {
eaeff70d
MD
837 kprintf("SEARCH %d:%d:%08x[%d] %016llx %02x key=%016llx did=%016llx\n",
838 cursor->node->cluster->volume->vol_no,
839 cursor->node->cluster->clu_no,
840 cursor->node->node_offset,
841 cursor->index,
b3deaf57
MD
842 cursor->key_beg.obj_id,
843 cursor->key_beg.rec_type,
d113fda1 844 cursor->key_beg.key,
d5530d22 845 cursor->key_beg.delete_tid
b3deaf57
MD
846 );
847 }
848
8cd0a023
MD
849 /*
850 * Move our cursor up the tree until we find a node whos range covers
851 * the key we are trying to locate. This may move us between
852 * clusters.
853 *
854 * The left bound is inclusive, the right bound is non-inclusive.
855 * It is ok to cursor up too far so when cursoring across a cluster
856 * boundary.
857 *
858 * First see if we can skip the whole cluster. hammer_cursor_up()
859 * handles both cases but this way we don't check the cluster
860 * bounds when going up the tree within a cluster.
d26d0ae9
MD
861 *
862 * NOTE: If INCLUSTER is set and we are at the root of the cluster,
863 * hammer_cursor_up() will return ENOENT.
8cd0a023
MD
864 */
865 cluster = cursor->node->cluster;
866 while (
867 hammer_btree_cmp(&cursor->key_beg, &cluster->clu_btree_beg) < 0 ||
868 hammer_btree_cmp(&cursor->key_beg, &cluster->clu_btree_end) >= 0) {
869 error = hammer_cursor_toroot(cursor);
870 if (error)
871 goto done;
9944ae54 872 KKASSERT(cursor->parent);
6a37e7e4 873 error = hammer_cursor_up(cursor);
8cd0a023
MD
874 if (error)
875 goto done;
876 cluster = cursor->node->cluster;
427e5fc6
MD
877 }
878
879 /*
8cd0a023
MD
880 * Deal with normal cursoring within a cluster. The right bound
881 * is non-inclusive. That is, the bounds form a separator.
427e5fc6 882 */
8cd0a023
MD
883 while (hammer_btree_cmp(&cursor->key_beg, cursor->left_bound) < 0 ||
884 hammer_btree_cmp(&cursor->key_beg, cursor->right_bound) >= 0) {
9944ae54 885 KKASSERT(cursor->parent);
6a37e7e4 886 error = hammer_cursor_up(cursor);
8cd0a023
MD
887 if (error)
888 goto done;
427e5fc6 889 }
427e5fc6 890
8cd0a023
MD
891 /*
892 * We better have ended up with a node somewhere, and our second
893 * while loop had better not have traversed up a cluster.
894 */
895 KKASSERT(cursor->node != NULL && cursor->node->cluster == cluster);
896
897 /*
898 * If we are inserting we can't start at a full node if the parent
899 * is also full (because there is no way to split the node),
900 * continue running up the tree until we hit the root of the
901 * root cluster or until the requirement is satisfied.
902 *
903 * NOTE: These cursor-up's CAN continue to cross cluster boundaries.
904 *
9944ae54
MD
905 * NOTE: We must guarantee at least two open spots in the parent
906 * to deal with hammer_btree_insert_cluster().
907 *
8cd0a023
MD
908 * XXX as an optimization it should be possible to unbalance the tree
909 * and stop at the root of the current cluster.
910 */
61aeeb33 911 while ((flags & HAMMER_CURSOR_INSERT) && enospc == 0) {
eaeff70d
MD
912 if (cursor->node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
913 if (btree_node_is_full(cursor->node->ondisk) == 0)
914 break;
915 } else {
916 if (btree_node_is_almost_full(cursor->node->ondisk) ==0)
917 break;
918 }
8cd0a023
MD
919 if (cursor->parent == NULL)
920 break;
921 if (cursor->parent->ondisk->count != HAMMER_BTREE_INT_ELMS)
922 break;
6a37e7e4 923 error = hammer_cursor_up(cursor);
8cd0a023
MD
924 /* cluster and node are now may become stale */
925 if (error)
926 goto done;
427e5fc6 927 }
8cd0a023 928 /* cluster = cursor->node->cluster; not needed until next cluster = */
427e5fc6 929
fe7678ee 930new_cluster:
8cd0a023
MD
931 /*
932 * Push down through internal nodes to locate the requested key.
933 */
934 cluster = cursor->node->cluster;
935 node = cursor->node->ondisk;
936 while (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
8cd0a023
MD
937 /*
938 * Scan the node to find the subtree index to push down into.
fbc6e32a 939 * We go one-past, then back-up.
d113fda1 940 *
fe7678ee
MD
941 * We must proactively remove deleted elements which may
942 * have been left over from a deadlocked btree_remove().
943 *
eaeff70d 944 * The left and right boundaries are included in the loop
d5530d22 945 * in order to detect edge cases.
9944ae54 946 *
d5530d22 947 * If the separator only differs by delete_tid (r == -1)
eaeff70d
MD
948 * and we are doing an as-of search, we may end up going
949 * down a branch to the left of the one containing the
950 * desired key. This requires numerous special cases.
8cd0a023 951 */
9944ae54 952 for (i = 0; i <= node->count; ++i) {
61aeeb33
MD
953 elm = &node->elms[i];
954 r = hammer_btree_cmp(&cursor->key_beg, &elm->base);
8cd0a023
MD
955 if (r < 0)
956 break;
957 }
eaeff70d
MD
958 if (hammer_debug_btree) {
959 kprintf("SEARCH-I %d:%d:%08x pre-i %d/%d\n",
960 cursor->node->cluster->volume->vol_no,
961 cursor->node->cluster->clu_no,
962 cursor->node->node_offset,
963 i, node->count);
964 }
8cd0a023
MD
965
966 /*
9944ae54
MD
967 * These cases occur when the parent's idea of the boundary
968 * is wider then the child's idea of the boundary, and
969 * require special handling. If not inserting we can
970 * terminate the search early for these cases but the
971 * child's boundaries cannot be unconditionally modified.
8cd0a023 972 */
fbc6e32a 973 if (i == 0) {
9944ae54
MD
974 /*
975 * If i == 0 the search terminated to the LEFT of the
976 * left_boundary but to the RIGHT of the parent's left
977 * boundary.
978 */
fbc6e32a 979 u_int8_t save;
d26d0ae9 980
eaeff70d
MD
981 elm = &node->elms[0];
982
983 /*
984 * If we aren't inserting we can stop here.
985 */
fbc6e32a
MD
986 if ((flags & HAMMER_CURSOR_INSERT) == 0) {
987 cursor->index = 0;
988 return(ENOENT);
989 }
9944ae54 990
d5530d22
MD
991 /*
992 * Correct a left-hand boundary mismatch.
6a37e7e4 993 *
eaeff70d 994 * We can only do this if we can upgrade the lock.
d5530d22 995 */
eaeff70d
MD
996 if ((error = hammer_cursor_upgrade(cursor)) != 0)
997 return(error);
d5530d22 998 hammer_modify_node(cursor->node);
fe7678ee 999 save = node->elms[0].base.btype;
d5530d22 1000 node->elms[0].base = *cursor->left_bound;
fe7678ee 1001 node->elms[0].base.btype = save;
9944ae54 1002 } else if (i == node->count + 1) {
d26d0ae9 1003 /*
9944ae54
MD
1004 * If i == node->count + 1 the search terminated to
1005 * the RIGHT of the right boundary but to the LEFT
eaeff70d
MD
1006 * of the parent's right boundary. If we aren't
1007 * inserting we can stop here.
d113fda1 1008 *
9944ae54
MD
1009 * Note that the last element in this case is
1010 * elms[i-2] prior to adjustments to 'i'.
d26d0ae9 1011 */
9944ae54 1012 --i;
d113fda1 1013 if ((flags & HAMMER_CURSOR_INSERT) == 0) {
9944ae54 1014 cursor->index = i;
eaeff70d 1015 return (ENOENT);
d26d0ae9
MD
1016 }
1017
d5530d22
MD
1018 /*
1019 * Correct a right-hand boundary mismatch.
1020 * (actual push-down record is i-2 prior to
1021 * adjustments to i).
6a37e7e4 1022 *
eaeff70d 1023 * We can only do this if we can upgrade the lock.
d5530d22 1024 */
eaeff70d
MD
1025 if ((error = hammer_cursor_upgrade(cursor)) != 0)
1026 return(error);
9944ae54 1027 elm = &node->elms[i];
d5530d22
MD
1028 hammer_modify_node(cursor->node);
1029 elm->base = *cursor->right_bound;
1030 --i;
fbc6e32a
MD
1031 } else {
1032 /*
9944ae54
MD
1033 * The push-down index is now i - 1. If we had
1034 * terminated on the right boundary this will point
1035 * us at the last element.
fbc6e32a
MD
1036 */
1037 --i;
1038 }
8cd0a023 1039 cursor->index = i;
6a37e7e4 1040 elm = &node->elms[i];
8cd0a023 1041
b3deaf57 1042 if (hammer_debug_btree) {
eaeff70d
MD
1043 kprintf("SEARCH-I %d:%d:%08x[%d] %016llx %02x key=%016llx did=%016llx\n",
1044 cursor->node->cluster->volume->vol_no,
1045 cursor->node->cluster->clu_no,
1046 cursor->node->node_offset,
1047 i,
b3deaf57
MD
1048 elm->internal.base.obj_id,
1049 elm->internal.base.rec_type,
d113fda1 1050 elm->internal.base.key,
d5530d22 1051 elm->internal.base.delete_tid
b3deaf57
MD
1052 );
1053 }
1054
6a37e7e4
MD
1055 /*
1056 * When searching try to clean up any deleted
1057 * internal elements left over from btree_remove()
1058 * deadlocks.
1059 *
1060 * If we fail and we are doing an insertion lookup,
1061 * we have to return EDEADLK, because an insertion lookup
1062 * must terminate at a leaf.
1063 */
1064 if (elm->internal.subtree_offset == 0) {
1065 error = btree_remove_deleted_element(cursor);
1066 if (error == 0)
1067 goto new_cluster;
eaeff70d
MD
1068 if (error == EDEADLK &&
1069 (flags & HAMMER_CURSOR_INSERT) == 0) {
1070 error = ENOENT;
1071 }
1072 return(error);
6a37e7e4
MD
1073 }
1074
1075
8cd0a023
MD
1076 /*
1077 * Handle insertion and deletion requirements.
1078 *
1079 * If inserting split full nodes. The split code will
1080 * adjust cursor->node and cursor->index if the current
1081 * index winds up in the new node.
61aeeb33 1082 *
9944ae54
MD
1083 * If inserting and a left or right edge case was detected,
1084 * we cannot correct the left or right boundary and must
1085 * prepend and append an empty leaf node in order to make
1086 * the boundary correction.
1087 *
61aeeb33
MD
1088 * If we run out of space we set enospc and continue on
1089 * to a leaf to provide the spike code with a good point
1090 * of entry. Enospc is reset if we cross a cluster boundary.
8cd0a023 1091 */
61aeeb33 1092 if ((flags & HAMMER_CURSOR_INSERT) && enospc == 0) {
fe7678ee 1093 if (btree_node_is_full(node)) {
8cd0a023 1094 error = btree_split_internal(cursor);
d26d0ae9
MD
1095 if (error) {
1096 if (error != ENOSPC)
1097 goto done;
1098 enospc = 1;
d26d0ae9 1099 }
8cd0a023
MD
1100 /*
1101 * reload stale pointers
1102 */
1103 i = cursor->index;
1104 node = cursor->node->ondisk;
1105 }
d26d0ae9 1106 }
427e5fc6
MD
1107
1108 /*
8cd0a023 1109 * Push down (push into new node, existing node becomes
d26d0ae9 1110 * the parent) and continue the search.
427e5fc6 1111 */
8cd0a023
MD
1112 error = hammer_cursor_down(cursor);
1113 /* node and cluster become stale */
1114 if (error)
1115 goto done;
1116 node = cursor->node->ondisk;
1117 cluster = cursor->node->cluster;
427e5fc6 1118 }
427e5fc6 1119
8cd0a023
MD
1120 /*
1121 * We are at a leaf, do a linear search of the key array.
d26d0ae9 1122 *
fe7678ee 1123 * If we encounter a spike element type within the necessary
eaeff70d
MD
1124 * range we push into it. Note that SPIKE_END is non-inclusive
1125 * of the spike range.
fe7678ee 1126 *
d26d0ae9
MD
1127 * On success the index is set to the matching element and 0
1128 * is returned.
1129 *
1130 * On failure the index is set to the insertion point and ENOENT
1131 * is returned.
8cd0a023
MD
1132 *
1133 * Boundaries are not stored in leaf nodes, so the index can wind
1134 * up to the left of element 0 (index == 0) or past the end of
1135 * the array (index == node->count).
1136 */
fe7678ee 1137 KKASSERT (node->type == HAMMER_BTREE_TYPE_LEAF);
8cd0a023
MD
1138 KKASSERT(node->count <= HAMMER_BTREE_LEAF_ELMS);
1139
1140 for (i = 0; i < node->count; ++i) {
fe7678ee
MD
1141 elm = &node->elms[i];
1142
1143 r = hammer_btree_cmp(&cursor->key_beg, &elm->leaf.base);
427e5fc6 1144
d5530d22
MD
1145 if (hammer_debug_btree > 1)
1146 kprintf(" ELM %p %d r=%d\n", &node->elms[i], i, r);
1147
fe7678ee
MD
1148 if (elm->leaf.base.btype == HAMMER_BTREE_TYPE_SPIKE_BEG) {
1149 /*
1150 * SPIKE_BEG. Stop if we are to the left of the
1151 * spike begin element.
1152 *
1153 * If we are not the last element in the leaf continue
1154 * the loop looking for the SPIKE_END. If we are
1155 * the last element, however, then push into the
1156 * spike.
1157 *
eaeff70d
MD
1158 * If doing an as-of search a Spike demark on a
1159 * delete_tid boundary must be pushed into and an
1160 * iteration will be forced if it turned out to be
1161 * the wrong choice.
1162 *
1163 * If not doing an as-of search exact comparisons
1164 * must be used.
fe7678ee
MD
1165 *
1166 * enospc must be reset because we have crossed a
1167 * cluster boundary.
1168 */
eaeff70d 1169 if (r < 0)
fe7678ee
MD
1170 goto failed;
1171 if (i != node->count - 1)
1172 continue;
1173 panic("btree_search: illegal spike, no SPIKE_END "
1174 "in leaf node! %p\n", cursor->node);
eaeff70d 1175#if 0
fe7678ee
MD
1176 /*
1177 * XXX This is not currently legal, you can only
1178 * cursor_down() from a SPIKE_END element, otherwise
1179 * the cursor parent is pointing at the wrong element
1180 * for deletions.
1181 */
eaeff70d 1182 if (flags & HAMMER_CURSOR_INCLUSTER)
fe7678ee
MD
1183 goto success;
1184 cursor->index = i;
1185 error = hammer_cursor_down(cursor);
1186 enospc = 0;
1187 if (error)
1188 goto done;
1189 goto new_cluster;
eaeff70d 1190#endif
fe7678ee
MD
1191 }
1192 if (elm->leaf.base.btype == HAMMER_BTREE_TYPE_SPIKE_END) {
1193 /*
1194 * SPIKE_END. We can only hit this case if we are
1195 * greater or equal to SPIKE_BEG.
1196 *
eaeff70d
MD
1197 * If we are less then SPIKE_END we must push into
1198 * it, otherwise continue the search. The SPIKE_END
1199 * element is range-exclusive and because of that
1200 * it is possible for it's key to match the next
1201 * record on the right.
fe7678ee
MD
1202 *
1203 * enospc must be reset because we have crossed a
1204 * cluster boundary.
1205 */
eaeff70d 1206 if (r >= 0)
fe7678ee 1207 continue;
eaeff70d 1208 if (flags & HAMMER_CURSOR_INCLUSTER)
fe7678ee
MD
1209 goto success;
1210 cursor->index = i;
1211 error = hammer_cursor_down(cursor);
1212 enospc = 0;
1213 if (error)
1214 goto done;
1215 goto new_cluster;
1216 }
1217
427e5fc6 1218 /*
fe7678ee
MD
1219 * We are at a record element. Stop if we've flipped past
1220 * key_beg, not counting the delete_tid test.
427e5fc6 1221 */
fe7678ee
MD
1222 KKASSERT (elm->leaf.base.btype == HAMMER_BTREE_TYPE_RECORD);
1223
d5530d22
MD
1224 if (r < -1)
1225 goto failed;
fe7678ee 1226 if (r > 0)
d5530d22 1227 continue;
427e5fc6 1228
66325755 1229 /*
eaeff70d
MD
1230 * Check our as-of timestamp against the element. A
1231 * delete_tid that matches exactly in an as-of search
1232 * is actually a no-match (the record was deleted as-of
1233 * our timestamp so it isn't visible).
66325755 1234 */
eaeff70d 1235 if (flags & HAMMER_CURSOR_ASOF) {
fe7678ee 1236 if (hammer_btree_chkts(cursor->asof,
d113fda1
MD
1237 &node->elms[i].base) != 0) {
1238 continue;
1239 }
eaeff70d
MD
1240 /* success */
1241 } else {
1242 if (r < 0) /* can only be -1 */
1243 goto failed;
1244 /* success */
66325755 1245 }
fe7678ee 1246success:
d5530d22
MD
1247 cursor->index = i;
1248 error = 0;
eaeff70d
MD
1249 if (hammer_debug_btree) {
1250 kprintf("SEARCH-L %d:%d:%08x[%d] (SUCCESS)\n",
1251 cursor->node->cluster->volume->vol_no,
1252 cursor->node->cluster->clu_no,
1253 cursor->node->node_offset,
1254 i);
1255 }
d5530d22
MD
1256 goto done;
1257 }
1258
1259 /*
eaeff70d 1260 * The search of the leaf node failed. i is the insertion point.
d5530d22 1261 */
d5530d22 1262failed:
b3deaf57 1263 if (hammer_debug_btree) {
eaeff70d
MD
1264 kprintf("SEARCH-L %d:%d:%08x[%d] (FAILED)\n",
1265 cursor->node->cluster->volume->vol_no,
1266 cursor->node->cluster->clu_no,
1267 cursor->node->node_offset,
1268 i);
b3deaf57
MD
1269 }
1270
8cd0a023
MD
1271 /*
1272 * No exact match was found, i is now at the insertion point.
1273 *
1274 * If inserting split a full leaf before returning. This
1275 * may have the side effect of adjusting cursor->node and
1276 * cursor->index.
eaeff70d
MD
1277 *
1278 * For now the leaf must have at least 2 free elements to accomodate
1279 * the insertion of a spike during recovery. See the
1280 * hammer_btree_insert_cluster() function.
8cd0a023
MD
1281 */
1282 cursor->index = i;
eaeff70d
MD
1283 if ((flags & HAMMER_CURSOR_INSERT) && enospc == 0 &&
1284 btree_node_is_almost_full(node)) {
8cd0a023 1285 error = btree_split_leaf(cursor);
d26d0ae9
MD
1286 if (error) {
1287 if (error != ENOSPC)
1288 goto done;
1289 enospc = 1;
d26d0ae9
MD
1290 }
1291 /*
1292 * reload stale pointers
1293 */
8cd0a023
MD
1294 /* NOT USED
1295 i = cursor->index;
1296 node = &cursor->node->internal;
1297 */
8cd0a023 1298 }
d26d0ae9
MD
1299
1300 /*
1301 * We reached a leaf but did not find the key we were looking for.
1302 * If this is an insert we will be properly positioned for an insert
1303 * (ENOENT) or spike (ENOSPC) operation.
1304 */
1305 error = enospc ? ENOSPC : ENOENT;
8cd0a023 1306done:
427e5fc6
MD
1307 return(error);
1308}
1309
8cd0a023 1310
427e5fc6 1311/************************************************************************
8cd0a023 1312 * SPLITTING AND MERGING *
427e5fc6
MD
1313 ************************************************************************
1314 *
1315 * These routines do all the dirty work required to split and merge nodes.
1316 */
1317
1318/*
8cd0a023 1319 * Split an internal node into two nodes and move the separator at the split
fe7678ee 1320 * point to the parent.
427e5fc6 1321 *
8cd0a023
MD
1322 * (cursor->node, cursor->index) indicates the element the caller intends
1323 * to push into. We will adjust node and index if that element winds
427e5fc6 1324 * up in the split node.
8cd0a023
MD
1325 *
1326 * If we are at the root of a cluster a new root must be created with two
1327 * elements, one pointing to the original root and one pointing to the
1328 * newly allocated split node.
1329 *
1330 * NOTE! Being at the root of a cluster is different from being at the
1331 * root of the root cluster. cursor->parent will not be NULL and
1332 * cursor->node->ondisk.parent must be tested against 0. Theoretically
1333 * we could propogate the algorithm into the parent and deal with multiple
1334 * 'roots' in the cluster header, but it's easier not to.
427e5fc6
MD
1335 */
1336static
1337int
8cd0a023 1338btree_split_internal(hammer_cursor_t cursor)
427e5fc6 1339{
8cd0a023
MD
1340 hammer_node_ondisk_t ondisk;
1341 hammer_node_t node;
1342 hammer_node_t parent;
1343 hammer_node_t new_node;
1344 hammer_btree_elm_t elm;
1345 hammer_btree_elm_t parent_elm;
427e5fc6
MD
1346 int parent_index;
1347 int made_root;
1348 int split;
1349 int error;
7f7c1f84 1350 int i;
8cd0a023 1351 const int esize = sizeof(*elm);
427e5fc6 1352
6a37e7e4
MD
1353 if ((error = hammer_cursor_upgrade(cursor)) != 0)
1354 return(error);
1355
427e5fc6
MD
1356 /*
1357 * We are splitting but elms[split] will be promoted to the parent,
1358 * leaving the right hand node with one less element. If the
1359 * insertion point will be on the left-hand side adjust the split
1360 * point to give the right hand side one additional node.
1361 */
8cd0a023
MD
1362 node = cursor->node;
1363 ondisk = node->ondisk;
1364 split = (ondisk->count + 1) / 2;
427e5fc6
MD
1365 if (cursor->index <= split)
1366 --split;
427e5fc6
MD
1367
1368 /*
8cd0a023 1369 * If we are at the root of the cluster, create a new root node with
427e5fc6
MD
1370 * 1 element and split normally. Avoid making major modifications
1371 * until we know the whole operation will work.
8cd0a023
MD
1372 *
1373 * The root of the cluster is different from the root of the root
1374 * cluster. Use the node's on-disk structure's parent offset to
1375 * detect the case.
427e5fc6 1376 */
8cd0a023
MD
1377 if (ondisk->parent == 0) {
1378 parent = hammer_alloc_btree(node->cluster, &error);
427e5fc6 1379 if (parent == NULL)
6a37e7e4 1380 goto done;
8cd0a023 1381 hammer_lock_ex(&parent->lock);
0b075555 1382 hammer_modify_node(parent);
8cd0a023
MD
1383 ondisk = parent->ondisk;
1384 ondisk->count = 1;
1385 ondisk->parent = 0;
1386 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1387 ondisk->elms[0].base = node->cluster->clu_btree_beg;
fe7678ee 1388 ondisk->elms[0].base.btype = node->ondisk->type;
8cd0a023
MD
1389 ondisk->elms[0].internal.subtree_offset = node->node_offset;
1390 ondisk->elms[1].base = node->cluster->clu_btree_end;
fe7678ee 1391 /* ondisk->elms[1].base.btype - not used */
427e5fc6 1392 made_root = 1;
8cd0a023 1393 parent_index = 0; /* index of current node in parent */
427e5fc6
MD
1394 } else {
1395 made_root = 0;
8cd0a023
MD
1396 parent = cursor->parent;
1397 parent_index = cursor->parent_index;
195c19a1 1398 KKASSERT(parent->cluster == node->cluster);
427e5fc6 1399 }
427e5fc6
MD
1400
1401 /*
1402 * Split node into new_node at the split point.
1403 *
1404 * B O O O P N N B <-- P = node->elms[split]
1405 * 0 1 2 3 4 5 6 <-- subtree indices
1406 *
1407 * x x P x x
1408 * s S S s
1409 * / \
1410 * B O O O B B N N B <--- inner boundary points are 'P'
1411 * 0 1 2 3 4 5 6
1412 *
1413 */
8cd0a023 1414 new_node = hammer_alloc_btree(node->cluster, &error);
427e5fc6 1415 if (new_node == NULL) {
8cd0a023
MD
1416 if (made_root) {
1417 hammer_unlock(&parent->lock);
b3deaf57 1418 parent->flags |= HAMMER_NODE_DELETED;
8cd0a023
MD
1419 hammer_rel_node(parent);
1420 }
6a37e7e4 1421 goto done;
427e5fc6 1422 }
8cd0a023 1423 hammer_lock_ex(&new_node->lock);
427e5fc6
MD
1424
1425 /*
8cd0a023 1426 * Create the new node. P becomes the left-hand boundary in the
427e5fc6
MD
1427 * new node. Copy the right-hand boundary as well.
1428 *
1429 * elm is the new separator.
1430 */
0b075555
MD
1431 hammer_modify_node(new_node);
1432 hammer_modify_node(node);
8cd0a023
MD
1433 ondisk = node->ondisk;
1434 elm = &ondisk->elms[split];
1435 bcopy(elm, &new_node->ondisk->elms[0],
1436 (ondisk->count - split + 1) * esize);
1437 new_node->ondisk->count = ondisk->count - split;
1438 new_node->ondisk->parent = parent->node_offset;
1439 new_node->ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1440 KKASSERT(ondisk->type == new_node->ondisk->type);
427e5fc6
MD
1441
1442 /*
fe7678ee
MD
1443 * Cleanup the original node. Elm (P) becomes the new boundary,
1444 * its subtree_offset was moved to the new node. If we had created
427e5fc6
MD
1445 * a new root its parent pointer may have changed.
1446 */
8cd0a023 1447 elm->internal.subtree_offset = 0;
c0ade690 1448 ondisk->count = split;
427e5fc6
MD
1449
1450 /*
1451 * Insert the separator into the parent, fixup the parent's
1452 * reference to the original node, and reference the new node.
1453 * The separator is P.
1454 *
1455 * Remember that base.count does not include the right-hand boundary.
1456 */
0b075555 1457 hammer_modify_node(parent);
8cd0a023 1458 ondisk = parent->ondisk;
d26d0ae9 1459 KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
8cd0a023 1460 parent_elm = &ondisk->elms[parent_index+1];
427e5fc6 1461 bcopy(parent_elm, parent_elm + 1,
8cd0a023
MD
1462 (ondisk->count - parent_index) * esize);
1463 parent_elm->internal.base = elm->base; /* separator P */
fe7678ee 1464 parent_elm->internal.base.btype = new_node->ondisk->type;
8cd0a023 1465 parent_elm->internal.subtree_offset = new_node->node_offset;
76376933 1466 ++ondisk->count;
427e5fc6 1467
7f7c1f84
MD
1468 /*
1469 * The children of new_node need their parent pointer set to new_node.
1470 */
1471 for (i = 0; i < new_node->ondisk->count; ++i) {
1472 elm = &new_node->ondisk->elms[i];
1473 error = btree_set_parent(new_node, elm);
1474 if (error) {
1475 panic("btree_split_internal: btree-fixup problem");
1476 }
1477 }
1478
427e5fc6
MD
1479 /*
1480 * The cluster's root pointer may have to be updated.
1481 */
1482 if (made_root) {
8cd0a023 1483 hammer_modify_cluster(node->cluster);
0b075555 1484 node->cluster->ondisk->clu_btree_root = parent->node_offset;
8cd0a023
MD
1485 node->ondisk->parent = parent->node_offset;
1486 if (cursor->parent) {
1487 hammer_unlock(&cursor->parent->lock);
1488 hammer_rel_node(cursor->parent);
1489 }
1490 cursor->parent = parent; /* lock'd and ref'd */
427e5fc6
MD
1491 }
1492
8cd0a023 1493
427e5fc6
MD
1494 /*
1495 * Ok, now adjust the cursor depending on which element the original
1496 * index was pointing at. If we are >= the split point the push node
1497 * is now in the new node.
1498 *
1499 * NOTE: If we are at the split point itself we cannot stay with the
1500 * original node because the push index will point at the right-hand
1501 * boundary, which is illegal.
8cd0a023
MD
1502 *
1503 * NOTE: The cursor's parent or parent_index must be adjusted for
1504 * the case where a new parent (new root) was created, and the case
1505 * where the cursor is now pointing at the split node.
427e5fc6
MD
1506 */
1507 if (cursor->index >= split) {
8cd0a023 1508 cursor->parent_index = parent_index + 1;
427e5fc6 1509 cursor->index -= split;
8cd0a023
MD
1510 hammer_unlock(&cursor->node->lock);
1511 hammer_rel_node(cursor->node);
1512 cursor->node = new_node; /* locked and ref'd */
1513 } else {
1514 cursor->parent_index = parent_index;
1515 hammer_unlock(&new_node->lock);
1516 hammer_rel_node(new_node);
427e5fc6 1517 }
76376933
MD
1518
1519 /*
1520 * Fixup left and right bounds
1521 */
1522 parent_elm = &parent->ondisk->elms[cursor->parent_index];
fbc6e32a
MD
1523 cursor->left_bound = &parent_elm[0].internal.base;
1524 cursor->right_bound = &parent_elm[1].internal.base;
b3deaf57
MD
1525 KKASSERT(hammer_btree_cmp(cursor->left_bound,
1526 &cursor->node->ondisk->elms[0].internal.base) <= 0);
1527 KKASSERT(hammer_btree_cmp(cursor->right_bound,
9944ae54 1528 &cursor->node->ondisk->elms[cursor->node->ondisk->count].internal.base) >= 0);
76376933 1529
6a37e7e4
MD
1530done:
1531 hammer_cursor_downgrade(cursor);
1532 return (error);
427e5fc6
MD
1533}
1534
1535/*
1536 * Same as the above, but splits a full leaf node.
6a37e7e4
MD
1537 *
1538 * This function
427e5fc6
MD
1539 */
1540static
1541int
8cd0a023 1542btree_split_leaf(hammer_cursor_t cursor)
427e5fc6 1543{
8cd0a023
MD
1544 hammer_node_ondisk_t ondisk;
1545 hammer_node_t parent;
1546 hammer_node_t leaf;
1547 hammer_node_t new_leaf;
1548 hammer_btree_elm_t elm;
1549 hammer_btree_elm_t parent_elm;
b3deaf57 1550 hammer_base_elm_t mid_boundary;
427e5fc6
MD
1551 int parent_index;
1552 int made_root;
1553 int split;
1554 int error;
fe7678ee 1555 int i;
8cd0a023 1556 const size_t esize = sizeof(*elm);
427e5fc6 1557
6a37e7e4
MD
1558 if ((error = hammer_cursor_upgrade(cursor)) != 0)
1559 return(error);
1560
427e5fc6 1561 /*
8cd0a023
MD
1562 * Calculate the split point. If the insertion point will be on
1563 * the left-hand side adjust the split point to give the right
1564 * hand side one additional node.
fe7678ee
MD
1565 *
1566 * Spikes are made up of two leaf elements which cannot be
1567 * safely split.
427e5fc6 1568 */
8cd0a023
MD
1569 leaf = cursor->node;
1570 ondisk = leaf->ondisk;
1571 split = (ondisk->count + 1) / 2;
427e5fc6
MD
1572 if (cursor->index <= split)
1573 --split;
1574 error = 0;
1575
fe7678ee
MD
1576 elm = &ondisk->elms[split];
1577 if (elm->leaf.base.btype == HAMMER_BTREE_TYPE_SPIKE_END) {
1578 KKASSERT(split &&
1579 elm[-1].leaf.base.btype == HAMMER_BTREE_TYPE_SPIKE_BEG);
1580 --split;
1581 }
1582
427e5fc6
MD
1583 /*
1584 * If we are at the root of the tree, create a new root node with
1585 * 1 element and split normally. Avoid making major modifications
1586 * until we know the whole operation will work.
1587 */
8cd0a023
MD
1588 if (ondisk->parent == 0) {
1589 parent = hammer_alloc_btree(leaf->cluster, &error);
427e5fc6 1590 if (parent == NULL)
6a37e7e4 1591 goto done;
8cd0a023 1592 hammer_lock_ex(&parent->lock);
0b075555 1593 hammer_modify_node(parent);
8cd0a023
MD
1594 ondisk = parent->ondisk;
1595 ondisk->count = 1;
1596 ondisk->parent = 0;
1597 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1598 ondisk->elms[0].base = leaf->cluster->clu_btree_beg;
fe7678ee 1599 ondisk->elms[0].base.btype = leaf->ondisk->type;
8cd0a023
MD
1600 ondisk->elms[0].internal.subtree_offset = leaf->node_offset;
1601 ondisk->elms[1].base = leaf->cluster->clu_btree_end;
fe7678ee 1602 /* ondisk->elms[1].base.btype = not used */
427e5fc6 1603 made_root = 1;
8cd0a023 1604 parent_index = 0; /* insertion point in parent */
427e5fc6
MD
1605 } else {
1606 made_root = 0;
8cd0a023
MD
1607 parent = cursor->parent;
1608 parent_index = cursor->parent_index;
195c19a1 1609 KKASSERT(parent->cluster == leaf->cluster);
427e5fc6 1610 }
427e5fc6
MD
1611
1612 /*
1613 * Split leaf into new_leaf at the split point. Select a separator
1614 * value in-between the two leafs but with a bent towards the right
1615 * leaf since comparisons use an 'elm >= separator' inequality.
1616 *
1617 * L L L L L L L L
1618 *
1619 * x x P x x
1620 * s S S s
1621 * / \
1622 * L L L L L L L L
1623 */
8cd0a023 1624 new_leaf = hammer_alloc_btree(leaf->cluster, &error);
427e5fc6 1625 if (new_leaf == NULL) {
8cd0a023
MD
1626 if (made_root) {
1627 hammer_unlock(&parent->lock);
b3deaf57 1628 parent->flags |= HAMMER_NODE_DELETED;
8cd0a023
MD
1629 hammer_rel_node(parent);
1630 }
6a37e7e4 1631 goto done;
427e5fc6 1632 }
8cd0a023 1633 hammer_lock_ex(&new_leaf->lock);
427e5fc6
MD
1634
1635 /*
eaeff70d 1636 * Create the new node. P (elm) become the left-hand boundary in the
427e5fc6
MD
1637 * new node. Copy the right-hand boundary as well.
1638 */
0b075555
MD
1639 hammer_modify_node(leaf);
1640 hammer_modify_node(new_leaf);
8cd0a023
MD
1641 ondisk = leaf->ondisk;
1642 elm = &ondisk->elms[split];
1643 bcopy(elm, &new_leaf->ondisk->elms[0], (ondisk->count - split) * esize);
1644 new_leaf->ondisk->count = ondisk->count - split;
1645 new_leaf->ondisk->parent = parent->node_offset;
1646 new_leaf->ondisk->type = HAMMER_BTREE_TYPE_LEAF;
1647 KKASSERT(ondisk->type == new_leaf->ondisk->type);
427e5fc6
MD
1648
1649 /*
8cd0a023
MD
1650 * Cleanup the original node. Because this is a leaf node and
1651 * leaf nodes do not have a right-hand boundary, there
c0ade690
MD
1652 * aren't any special edge cases to clean up. We just fixup the
1653 * count.
427e5fc6 1654 */
c0ade690 1655 ondisk->count = split;
427e5fc6
MD
1656
1657 /*
1658 * Insert the separator into the parent, fixup the parent's
1659 * reference to the original node, and reference the new node.
1660 * The separator is P.
1661 *
1662 * Remember that base.count does not include the right-hand boundary.
1663 * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1664 */
0b075555 1665 hammer_modify_node(parent);
8cd0a023 1666 ondisk = parent->ondisk;
d26d0ae9 1667 KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
8cd0a023 1668 parent_elm = &ondisk->elms[parent_index+1];
d26d0ae9
MD
1669 bcopy(parent_elm, parent_elm + 1,
1670 (ondisk->count - parent_index) * esize);
eaeff70d
MD
1671
1672 /*
1673 * Create the separator. XXX At the moment use exactly the
1674 * right-hand element if this is a recovery operation in order
1675 * to guarantee that it does not bisect the spike elements in a
1676 * later call to hammer_btree_insert_cluster().
1677 */
1678 if (cursor->flags & HAMMER_CURSOR_RECOVER) {
1679 parent_elm->base = elm[0].base;
1680 } else {
1681 hammer_make_separator(&elm[-1].base, &elm[0].base,
1682 &parent_elm->base);
1683 }
fe7678ee 1684 parent_elm->internal.base.btype = new_leaf->ondisk->type;
8cd0a023 1685 parent_elm->internal.subtree_offset = new_leaf->node_offset;
b3deaf57 1686 mid_boundary = &parent_elm->base;
76376933 1687 ++ondisk->count;
427e5fc6 1688
fe7678ee
MD
1689 /*
1690 * The children of new_leaf need their parent pointer set to new_leaf.
1691 *
1692 * The leaf's elements are either TYPE_RECORD or TYPE_SPIKE_*. Only
1693 * elements of BTREE_TYPE_SPIKE_END really requires any action.
1694 */
1695 for (i = 0; i < new_leaf->ondisk->count; ++i) {
1696 elm = &new_leaf->ondisk->elms[i];
1697 error = btree_set_parent(new_leaf, elm);
1698 if (error) {
1699 panic("btree_split_internal: btree-fixup problem");
1700 }
1701 }
1702
427e5fc6
MD
1703 /*
1704 * The cluster's root pointer may have to be updated.
1705 */
1706 if (made_root) {
8cd0a023 1707 hammer_modify_cluster(leaf->cluster);
0b075555 1708 leaf->cluster->ondisk->clu_btree_root = parent->node_offset;
8cd0a023
MD
1709 leaf->ondisk->parent = parent->node_offset;
1710 if (cursor->parent) {
1711 hammer_unlock(&cursor->parent->lock);
1712 hammer_rel_node(cursor->parent);
1713 }
1714 cursor->parent = parent; /* lock'd and ref'd */
427e5fc6 1715 }
8cd0a023 1716
427e5fc6
MD
1717 /*
1718 * Ok, now adjust the cursor depending on which element the original
1719 * index was pointing at. If we are >= the split point the push node
1720 * is now in the new node.
1721 *
b3deaf57
MD
1722 * NOTE: If we are at the split point itself we need to select the
1723 * old or new node based on where key_beg's insertion point will be.
1724 * If we pick the wrong side the inserted element will wind up in
1725 * the wrong leaf node and outside that node's bounds.
427e5fc6 1726 */
b3deaf57
MD
1727 if (cursor->index > split ||
1728 (cursor->index == split &&
1729 hammer_btree_cmp(&cursor->key_beg, mid_boundary) >= 0)) {
8cd0a023 1730 cursor->parent_index = parent_index + 1;
427e5fc6 1731 cursor->index -= split;
8cd0a023
MD
1732 hammer_unlock(&cursor->node->lock);
1733 hammer_rel_node(cursor->node);
1734 cursor->node = new_leaf;
1735 } else {
1736 cursor->parent_index = parent_index;
1737 hammer_unlock(&new_leaf->lock);
1738 hammer_rel_node(new_leaf);
427e5fc6 1739 }
76376933
MD
1740
1741 /*
1742 * Fixup left and right bounds
1743 */
1744 parent_elm = &parent->ondisk->elms[cursor->parent_index];
fbc6e32a
MD
1745 cursor->left_bound = &parent_elm[0].internal.base;
1746 cursor->right_bound = &parent_elm[1].internal.base;
eaeff70d
MD
1747
1748 /*
1749 * Note: The right assertion is typically > 0, but if the last element
1750 * is a SPIKE_END it can be == 0 because the spike-end is non-inclusive
1751 * of the range being spiked.
1752 *
1753 * This may seem a bit odd but it works.
1754 */
b3deaf57
MD
1755 KKASSERT(hammer_btree_cmp(cursor->left_bound,
1756 &cursor->node->ondisk->elms[0].leaf.base) <= 0);
1757 KKASSERT(hammer_btree_cmp(cursor->right_bound,
eaeff70d 1758 &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].leaf.base) >= 0);
76376933 1759
6a37e7e4
MD
1760done:
1761 hammer_cursor_downgrade(cursor);
1762 return (error);
427e5fc6
MD
1763}
1764
1765/*
195c19a1
MD
1766 * Attempt to remove the empty B-Tree node at (cursor->node). Returns 0
1767 * on success, EAGAIN if we could not acquire the necessary locks, or some
fe7678ee 1768 * other error. This node can be a leaf node or an internal node.
8cd0a023 1769 *
195c19a1 1770 * On return the cursor may end up pointing at an internal node, suitable
b3deaf57 1771 * for further iteration but not for an immediate insertion or deletion.
8cd0a023 1772 *
195c19a1 1773 * cursor->node may be an internal node or a leaf node.
b3deaf57
MD
1774 *
1775 * NOTE: If cursor->node has one element it is the parent trying to delete
1776 * that element, make sure cursor->index is properly adjusted on success.
8cd0a023
MD
1777 */
1778int
6a37e7e4 1779btree_remove(hammer_cursor_t cursor, int depth)
8cd0a023
MD
1780{
1781 hammer_node_ondisk_t ondisk;
195c19a1 1782 hammer_btree_elm_t elm;
195c19a1 1783 hammer_node_t node;
fe7678ee 1784 hammer_node_t save;
8cd0a023 1785 hammer_node_t parent;
fe7678ee 1786 const int esize = sizeof(*elm);
8cd0a023 1787 int error;
8cd0a023
MD
1788
1789 /*
fe7678ee
MD
1790 * If we are at the root of the cluster we must be able to
1791 * successfully delete the HAMMER_BTREE_SPIKE_* leaf elements in
1792 * the parent in order to be able to destroy the cluster.
8cd0a023 1793 */
fe7678ee
MD
1794 node = cursor->node;
1795
1796 if (node->ondisk->parent == 0) {
1797 hammer_modify_node(node);
1798 ondisk = node->ondisk;
195c19a1
MD
1799 ondisk->type = HAMMER_BTREE_TYPE_LEAF;
1800 ondisk->count = 0;
b3deaf57 1801 cursor->index = 0;
fe7678ee
MD
1802 error = 0;
1803
6a37e7e4
MD
1804 if (depth > 16) {
1805 Debugger("btree_remove: stack limit reached");
1806 return(EDEADLK);
1807 }
1808
fe7678ee 1809 /*
6a37e7e4
MD
1810 * When trying to delete a cluster we need to exclusively
1811 * lock the cluster root, its parent (leaf in parent cluster),
1812 * AND the parent of that leaf if it's going to be empty,
1813 * because we can't leave around an empty leaf.
1814 *
1815 * XXX this is messy due to potentially recursive locks.
1816 * downgrade the cursor, get a second shared lock on the
1817 * node that cannot deadlock because we only own shared locks
1818 * then, cursor-up, and re-upgrade everything. If the
1819 * upgrades EDEADLK then don't try to remove the cluster
1820 * at this time.
fe7678ee
MD
1821 */
1822 if ((parent = cursor->parent) != NULL) {
6a37e7e4 1823 hammer_cursor_downgrade(cursor);
fe7678ee
MD
1824 save = node;
1825 hammer_ref_node(save);
6a37e7e4
MD
1826 hammer_lock_sh(&save->lock);
1827
1828 error = hammer_cursor_up(cursor);
1829 if (error == 0)
1830 error = hammer_cursor_upgrade(cursor);
1831 if (error == 0)
1832 error = hammer_lock_upgrade(&save->lock);
1833
fe7678ee 1834 if (error) {
6a37e7e4 1835 /* may be EDEADLK */
fe7678ee
MD
1836 kprintf("BTREE_REMOVE: Cannot delete cluster\n");
1837 Debugger("BTREE_REMOVE");
fe7678ee
MD
1838 } else {
1839 /*
1840 * cursor->node is now the leaf in the parent
1841 * cluster containing the spike elements.
1842 *
1843 * The cursor should be pointing at the
1844 * SPIKE_END element.
1845 *
1846 * Remove the spike elements and recurse
1847 * if the leaf becomes empty.
1848 */
1849 node = cursor->node;
1850 hammer_modify_node(node);
1851 ondisk = node->ondisk;
1852 KKASSERT(cursor->index > 0);
1853 --cursor->index;
1854 elm = &ondisk->elms[cursor->index];
1855 KKASSERT(elm[0].leaf.base.btype ==
1856 HAMMER_BTREE_TYPE_SPIKE_BEG);
1857 KKASSERT(elm[1].leaf.base.btype ==
1858 HAMMER_BTREE_TYPE_SPIKE_END);
1859 bcopy(elm + 2, elm, (ondisk->count -
1860 cursor->index - 2) * esize);
1861 ondisk->count -= 2;
1862 if (ondisk->count == 0)
6a37e7e4 1863 error = btree_remove(cursor, depth + 1);
fe7678ee
MD
1864 hammer_flush_node(save);
1865 save->flags |= HAMMER_NODE_DELETED;
1866 }
1867 hammer_unlock(&save->lock);
1868 hammer_rel_node(save);
1869 }
1870 return(error);
8cd0a023
MD
1871 }
1872
1873 /*
fe7678ee
MD
1874 * Zero-out the parent's reference to the child and flag the
1875 * child for destruction. This ensures that the child is not
1876 * reused while other references to it exist.
8cd0a023 1877 */
fe7678ee
MD
1878 parent = cursor->parent;
1879 hammer_modify_node(parent);
1880 ondisk = parent->ondisk;
1881 KKASSERT(ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
1882 elm = &ondisk->elms[cursor->parent_index];
1883 KKASSERT(elm->internal.subtree_offset == node->node_offset);
1884 elm->internal.subtree_offset = 0;
1885
1886 hammer_flush_node(node);
1887 node->flags |= HAMMER_NODE_DELETED;
8cd0a023 1888
6a37e7e4
MD
1889 /*
1890 * Don't blow up the kernel stack.
1891 */
1892 if (depth > 20) {
1893 kprintf("btree_remove: stack limit reached");
1894 return(EDEADLK);
1895 }
1896
8cd0a023 1897 /*
fe7678ee
MD
1898 * If the parent would otherwise not become empty we can physically
1899 * remove the zero'd element. Note however that in order to
1900 * guarentee a valid cursor we still need to be able to cursor up
1901 * because we no longer have a node.
1902 *
1903 * This collapse will change the parent's boundary elements, making
1904 * them wider. The new boundaries are recursively corrected in
1905 * btree_search().
195c19a1 1906 *
fe7678ee
MD
1907 * XXX we can theoretically recalculate the midpoint but there isn't
1908 * much of a reason to do it.
8cd0a023 1909 */
6a37e7e4
MD
1910 error = hammer_cursor_up(cursor);
1911 if (error == 0)
1912 error = hammer_cursor_upgrade(cursor);
1913
195c19a1 1914 if (error) {
b3deaf57 1915 kprintf("BTREE_REMOVE: Cannot lock parent, skipping\n");
fe7678ee
MD
1916 Debugger("BTREE_REMOVE");
1917 return (0);
8cd0a023 1918 }
195c19a1
MD
1919
1920 /*
fe7678ee
MD
1921 * Remove the internal element from the parent. The bcopy must
1922 * include the right boundary element.
9944ae54 1923 */
fe7678ee
MD
1924 KKASSERT(parent == cursor->node && ondisk == parent->ondisk);
1925 node = parent;
1926 parent = NULL;
1927 /* ondisk is node's ondisk */
1928 /* elm is node's element */
1929
6a37e7e4
MD
1930 /*
1931 * Remove the internal element that we zero'd out. Tell the caller
1932 * to loop if it hits zero (to try to avoid eating up precious kernel
1933 * stack).
1934 */
fe7678ee
MD
1935 KKASSERT(ondisk->count > 0);
1936 bcopy(&elm[1], &elm[0], (ondisk->count - cursor->index) * esize);
195c19a1 1937 --ondisk->count;
fe7678ee
MD
1938 if (ondisk->count == 0)
1939 error = EAGAIN;
b3deaf57 1940 return(error);
8cd0a023
MD
1941}
1942
6a37e7e4
MD
1943/*
1944 * Attempt to remove the deleted internal element at the current cursor
1945 * position. If we are unable to remove the element we return EDEADLK.
1946 *
1947 * If the current internal node becomes empty we delete it in the parent
1948 * and cursor up, looping until we finish or we deadlock.
1949 *
1950 * On return, if successful, the cursor will be pointing at the next
1951 * iterative position in the B-Tree. If unsuccessful the cursor will be
1952 * pointing at the last deleted internal element that could not be
1953 * removed.
1954 */
1955static
1956int
1957btree_remove_deleted_element(hammer_cursor_t cursor)
1958{
1959 hammer_node_t node;
1960 hammer_btree_elm_t elm;
1961 int error;
1962
1963 if ((error = hammer_cursor_upgrade(cursor)) != 0)
1964 return(error);
1965 node = cursor->node;
1966 elm = &node->ondisk->elms[cursor->index];
1967 if (elm->internal.subtree_offset == 0) {
1968 do {
1969 error = btree_remove(cursor, 0);
1970 kprintf("BTREE REMOVE DELETED ELEMENT %d\n", error);
1971 } while (error == EAGAIN);
1972 }
1973 return(error);
1974}
1975
7f7c1f84 1976/*
fe7678ee
MD
1977 * The element (elm) has been moved to a new internal node (node).
1978 *
1979 * If the element represents a pointer to an internal node that node's
1980 * parent must be adjusted to the element's new location.
1981 *
1982 * If the element represents a spike the target cluster's header must
1983 * be adjusted to point to the element's new location. This only
1984 * applies to HAMMER_SPIKE_END.
6a37e7e4
MD
1985 *
1986 * XXX deadlock potential here with our exclusive locks
7f7c1f84
MD
1987 */
1988static
1989int
1990btree_set_parent(hammer_node_t node, hammer_btree_elm_t elm)
1991{
1992 hammer_volume_t volume;
1993 hammer_cluster_t cluster;
1994 hammer_node_t child;
1995 int error;
1996
1997 error = 0;
1998
fe7678ee 1999 switch(elm->base.btype) {
7f7c1f84 2000 case HAMMER_BTREE_TYPE_INTERNAL:
fe7678ee 2001 case HAMMER_BTREE_TYPE_LEAF:
7f7c1f84
MD
2002 child = hammer_get_node(node->cluster,
2003 elm->internal.subtree_offset, &error);
2004 if (error == 0) {
0b075555 2005 hammer_modify_node(child);
7f7c1f84
MD
2006 hammer_lock_ex(&child->lock);
2007 child->ondisk->parent = node->node_offset;
7f7c1f84
MD
2008 hammer_unlock(&child->lock);
2009 hammer_rel_node(child);
2010 }
2011 break;
fe7678ee 2012 case HAMMER_BTREE_TYPE_SPIKE_END:
7f7c1f84 2013 volume = hammer_get_volume(node->cluster->volume->hmp,
fe7678ee 2014 elm->leaf.spike_vol_no, &error);
7f7c1f84
MD
2015 if (error)
2016 break;
fe7678ee
MD
2017 cluster = hammer_get_cluster(volume, elm->leaf.spike_clu_no,
2018 &error, 0);
7f7c1f84
MD
2019 hammer_rel_volume(volume, 0);
2020 if (error)
2021 break;
0b075555 2022 hammer_modify_cluster(cluster);
7f7c1f84
MD
2023 hammer_lock_ex(&cluster->io.lock);
2024 cluster->ondisk->clu_btree_parent_offset = node->node_offset;
2025 hammer_unlock(&cluster->io.lock);
2026 KKASSERT(cluster->ondisk->clu_btree_parent_clu_no ==
2027 node->cluster->clu_no);
2028 KKASSERT(cluster->ondisk->clu_btree_parent_vol_no ==
2029 node->cluster->volume->vol_no);
7f7c1f84
MD
2030 hammer_rel_cluster(cluster, 0);
2031 break;
2032 default:
fe7678ee 2033 break;
7f7c1f84
MD
2034 }
2035 return(error);
2036}
2037
8cd0a023
MD
2038/************************************************************************
2039 * MISCELLANIOUS SUPPORT *
2040 ************************************************************************/
2041
2042/*
d26d0ae9 2043 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
8cd0a023 2044 *
d113fda1 2045 * Note that for this particular function a return value of -1, 0, or +1
d5530d22
MD
2046 * can denote a match if delete_tid is otherwise discounted. A delete_tid
2047 * of zero is considered to be 'infinity' in comparisons.
d113fda1 2048 *
8cd0a023 2049 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
8cd0a023
MD
2050 */
2051int
2052hammer_btree_cmp(hammer_base_elm_t key1, hammer_base_elm_t key2)
2053{
d26d0ae9
MD
2054 if (key1->obj_id < key2->obj_id)
2055 return(-4);
2056 if (key1->obj_id > key2->obj_id)
2057 return(4);
8cd0a023 2058
d26d0ae9
MD
2059 if (key1->rec_type < key2->rec_type)
2060 return(-3);
2061 if (key1->rec_type > key2->rec_type)
2062 return(3);
8cd0a023 2063
8cd0a023
MD
2064 if (key1->key < key2->key)
2065 return(-2);
2066 if (key1->key > key2->key)
2067 return(2);
d113fda1 2068
d5530d22
MD
2069 /*
2070 * A delete_tid of zero indicates a record which has not been
2071 * deleted yet and must be considered to have a value of positive
2072 * infinity.
2073 */
2074 if (key1->delete_tid == 0) {
2075 if (key2->delete_tid == 0)
2076 return(0);
2077 return(1);
2078 }
2079 if (key2->delete_tid == 0)
2080 return(-1);
2081 if (key1->delete_tid < key2->delete_tid)
d113fda1 2082 return(-1);
d5530d22 2083 if (key1->delete_tid > key2->delete_tid)
d113fda1 2084 return(1);
8cd0a023
MD
2085 return(0);
2086}
2087
c0ade690 2088/*
d5530d22
MD
2089 * Test a timestamp against an element to determine whether the
2090 * element is visible. A timestamp of 0 means 'infinity'.
c0ade690
MD
2091 */
2092int
d5530d22 2093hammer_btree_chkts(hammer_tid_t asof, hammer_base_elm_t base)
c0ade690 2094{
d5530d22
MD
2095 if (asof == 0) {
2096 if (base->delete_tid)
2097 return(1);
2098 return(0);
2099 }
2100 if (asof < base->create_tid)
d26d0ae9 2101 return(-1);
d5530d22 2102 if (base->delete_tid && asof >= base->delete_tid)
d26d0ae9 2103 return(1);
c0ade690
MD
2104 return(0);
2105}
2106
8cd0a023
MD
2107/*
2108 * Create a separator half way inbetween key1 and key2. For fields just
d5530d22
MD
2109 * one unit apart, the separator will match key2. key1 is on the left-hand
2110 * side and key2 is on the right-hand side.
8cd0a023 2111 *
d5530d22
MD
2112 * delete_tid has to be special cased because a value of 0 represents
2113 * infinity, and records with a delete_tid of 0 can be replaced with
2114 * a non-zero delete_tid when deleted and must maintain their proper
2115 * (as in the same) position in the B-Tree.
8cd0a023
MD
2116 */
2117#define MAKE_SEPARATOR(key1, key2, dest, field) \
2118 dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
2119
2120static void
2121hammer_make_separator(hammer_base_elm_t key1, hammer_base_elm_t key2,
2122 hammer_base_elm_t dest)
2123{
2124 bzero(dest, sizeof(*dest));
2125 MAKE_SEPARATOR(key1, key2, dest, obj_id);
2126 MAKE_SEPARATOR(key1, key2, dest, rec_type);
2127 MAKE_SEPARATOR(key1, key2, dest, key);
d5530d22 2128
d113fda1
MD
2129 if (key1->obj_id == key2->obj_id &&
2130 key1->rec_type == key2->rec_type &&
2131 key1->key == key2->key) {
d5530d22
MD
2132 if (key1->delete_tid == 0) {
2133 /*
2134 * key1 cannot be on the left hand side if everything
2135 * matches but it has an infinite delete_tid!
2136 */
2137 panic("hammer_make_separator: illegal delete_tid");
2138 } else if (key2->delete_tid == 0) {
2139 dest->delete_tid = key1->delete_tid + 1;
2140 } else {
2141 MAKE_SEPARATOR(key1, key2, dest, delete_tid);
2142 }
d113fda1 2143 } else {
d5530d22 2144 dest->delete_tid = 0;
d113fda1 2145 }
8cd0a023
MD
2146}
2147
2148#undef MAKE_SEPARATOR
2149
2150/*
2151 * Return whether a generic internal or leaf node is full
2152 */
2153static int
2154btree_node_is_full(hammer_node_ondisk_t node)
2155{
2156 switch(node->type) {
2157 case HAMMER_BTREE_TYPE_INTERNAL:
2158 if (node->count == HAMMER_BTREE_INT_ELMS)
2159 return(1);
2160 break;
2161 case HAMMER_BTREE_TYPE_LEAF:
2162 if (node->count == HAMMER_BTREE_LEAF_ELMS)
2163 return(1);
2164 break;
2165 default:
2166 panic("illegal btree subtype");
2167 }
2168 return(0);
2169}
9944ae54
MD
2170
2171/*
2172 * Return whether a generic internal or leaf node is almost full. This
2173 * routine is used as a helper for search insertions to guarentee at
2174 * least 2 available slots in the internal node(s) leading up to a leaf,
2175 * so hammer_btree_insert_cluster() will function properly.
2176 */
2177static int
2178btree_node_is_almost_full(hammer_node_ondisk_t node)
2179{
2180 switch(node->type) {
2181 case HAMMER_BTREE_TYPE_INTERNAL:
2182 if (node->count > HAMMER_BTREE_INT_ELMS - 2)
2183 return(1);
2184 break;
2185 case HAMMER_BTREE_TYPE_LEAF:
2186 if (node->count > HAMMER_BTREE_LEAF_ELMS - 2)
2187 return(1);
2188 break;
2189 default:
2190 panic("illegal btree subtype");
2191 }
2192 return(0);
2193}
8cd0a023
MD
2194
2195#if 0
2196static int
2197btree_max_elements(u_int8_t type)
2198{
2199 if (type == HAMMER_BTREE_TYPE_LEAF)
2200 return(HAMMER_BTREE_LEAF_ELMS);
2201 if (type == HAMMER_BTREE_TYPE_INTERNAL)
2202 return(HAMMER_BTREE_INT_ELMS);
2203 panic("btree_max_elements: bad type %d\n", type);
2204}
2205#endif
2206
c0ade690
MD
2207void
2208hammer_print_btree_node(hammer_node_ondisk_t ondisk)
2209{
2210 hammer_btree_elm_t elm;
2211 int i;
2212
2213 kprintf("node %p count=%d parent=%d type=%c\n",
2214 ondisk, ondisk->count, ondisk->parent, ondisk->type);
2215
2216 /*
2217 * Dump both boundary elements if an internal node
2218 */
2219 if (ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
2220 for (i = 0; i <= ondisk->count; ++i) {
2221 elm = &ondisk->elms[i];
2222 hammer_print_btree_elm(elm, ondisk->type, i);
2223 }
2224 } else {
2225 for (i = 0; i < ondisk->count; ++i) {
2226 elm = &ondisk->elms[i];
2227 hammer_print_btree_elm(elm, ondisk->type, i);
2228 }
2229 }
2230}
2231
2232void
2233hammer_print_btree_elm(hammer_btree_elm_t elm, u_int8_t type, int i)
2234{
2235 kprintf(" %2d", i);
2236 kprintf("\tobjid = %016llx\n", elm->base.obj_id);
2237 kprintf("\tkey = %016llx\n", elm->base.key);
2238 kprintf("\tcreate_tid = %016llx\n", elm->base.create_tid);
2239 kprintf("\tdelete_tid = %016llx\n", elm->base.delete_tid);
2240 kprintf("\trec_type = %04x\n", elm->base.rec_type);
2241 kprintf("\tobj_type = %02x\n", elm->base.obj_type);
fe7678ee
MD
2242 kprintf("\tbtype = %02x (%c)\n",
2243 elm->base.btype,
2244 (elm->base.btype ? elm->base.btype : '?'));
2245
2246 switch(type) {
2247 case HAMMER_BTREE_TYPE_INTERNAL:
2248 kprintf("\tsubtree_off = %08x\n",
2249 elm->internal.subtree_offset);
2250 break;
2251 case HAMMER_BTREE_TYPE_SPIKE_BEG:
2252 case HAMMER_BTREE_TYPE_SPIKE_END:
2253 kprintf("\tspike_clu_no = %d\n", elm->leaf.spike_clu_no);
2254 kprintf("\tspike_vol_no = %d\n", elm->leaf.spike_vol_no);
2255 break;
2256 case HAMMER_BTREE_TYPE_RECORD:
c0ade690
MD
2257 kprintf("\trec_offset = %08x\n", elm->leaf.rec_offset);
2258 kprintf("\tdata_offset = %08x\n", elm->leaf.data_offset);
2259 kprintf("\tdata_len = %08x\n", elm->leaf.data_len);
2260 kprintf("\tdata_crc = %08x\n", elm->leaf.data_crc);
fe7678ee 2261 break;
c0ade690
MD
2262 }
2263}