HAMMER 15/many - user utility infrastructure, refactor alists, misc
[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 *
61aeeb33 34 * $DragonFly: src/sys/vfs/hammer/hammer_btree.c,v 1.16 2008/01/03 06:48:49 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
8cd0a023 41 * simply be refered to as the HAMMER B-Tree. Basically a 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 *
70 * INTER-CLUSTER ELEMENTS: An element of an internal node may reference
71 * the root of another cluster rather then a node in the current cluster.
72 * This is known as an inter-cluster references. Only B-Tree searches
73 * will cross cluster boundaries. The rebalancing and collapse code does
74 * not attempt to move children between clusters. A major effect of this
75 * is that we have to relax minimum element count requirements and allow
76 * trees to become somewhat unabalanced.
77 *
78 * INSERTIONS AND DELETIONS: When inserting we split full nodes on our
79 * way down as an optimization. I originally experimented with rebalancing
80 * nodes on the way down for deletions but it created a huge mess due to
81 * the way inter-cluster linkages work. Instead, now I simply allow
82 * the tree to become unbalanced and allow leaf nodes to become empty.
83 * The delete code will try to clean things up from the bottom-up but
84 * will stop if related elements are not in-core or if it cannot get a node
85 * lock.
86 */
87#include "hammer.h"
88#include <sys/buf.h>
89#include <sys/buf2.h>
66325755 90
8cd0a023
MD
91static int btree_search(hammer_cursor_t cursor, int flags);
92static int btree_split_internal(hammer_cursor_t cursor);
93static int btree_split_leaf(hammer_cursor_t cursor);
195c19a1 94static int btree_remove(hammer_cursor_t cursor);
7f7c1f84 95static int btree_set_parent(hammer_node_t node, hammer_btree_elm_t elm);
8cd0a023
MD
96#if 0
97static int btree_rebalance(hammer_cursor_t cursor);
98static int btree_collapse(hammer_cursor_t cursor);
99#endif
100static int btree_node_is_full(hammer_node_ondisk_t node);
101static void hammer_make_separator(hammer_base_elm_t key1,
102 hammer_base_elm_t key2, hammer_base_elm_t dest);
66325755
MD
103
104/*
8cd0a023
MD
105 * Iterate records after a search. The cursor is iterated forwards past
106 * the current record until a record matching the key-range requirements
107 * is found. ENOENT is returned if the iteration goes past the ending
108 * key.
66325755 109 *
d26d0ae9
MD
110 * The iteration is inclusive of key_beg and can be inclusive or exclusive
111 * of key_end depending on whether HAMMER_CURSOR_END_INCLUSIVE is set.
66325755 112 *
8cd0a023 113 * cursor->key_beg may or may not be modified by this function during
d26d0ae9
MD
114 * the iteration. XXX future - in case of an inverted lock we may have
115 * to reinitiate the lookup and set key_beg to properly pick up where we
116 * left off.
66325755
MD
117 */
118int
8cd0a023 119hammer_btree_iterate(hammer_cursor_t cursor)
66325755 120{
8cd0a023
MD
121 hammer_node_ondisk_t node;
122 hammer_btree_elm_t elm;
66325755
MD
123 int error;
124 int r;
125 int s;
126
127 /*
8cd0a023 128 * Skip past the current record
66325755 129 */
8cd0a023 130 node = cursor->node->ondisk;
a89aec1b
MD
131 if (node == NULL)
132 return(ENOENT);
c0ade690
MD
133 if (cursor->index < node->count &&
134 (cursor->flags & HAMMER_CURSOR_ATEDISK)) {
66325755 135 ++cursor->index;
c0ade690 136 }
66325755 137
8cd0a023
MD
138 /*
139 * Loop until an element is found or we are done.
140 */
66325755
MD
141 for (;;) {
142 /*
8cd0a023
MD
143 * We iterate up the tree and then index over one element
144 * while we are at the last element in the current node.
145 *
146 * NOTE: This can pop us up to another cluster.
66325755 147 *
8cd0a023
MD
148 * If we are at the root of the root cluster, cursor_up
149 * returns ENOENT.
150 *
151 * NOTE: hammer_cursor_up() will adjust cursor->key_beg
152 * when told to re-search for the cluster tag.
66325755
MD
153 *
154 * XXX this could be optimized by storing the information in
155 * the parent reference.
195c19a1
MD
156 *
157 * XXX we can lose the node lock temporarily, this could mess
158 * up our scan.
66325755 159 */
8cd0a023 160 if (cursor->index == node->count) {
195c19a1 161 error = hammer_cursor_up(cursor, 0);
8cd0a023
MD
162 if (error)
163 break;
164 node = cursor->node->ondisk;
165 KKASSERT(cursor->index != node->count);
166 ++cursor->index;
167 continue;
66325755
MD
168 }
169
170 /*
d26d0ae9
MD
171 * Check internal or leaf element. Determine if the record
172 * at the cursor has gone beyond the end of our range.
66325755 173 *
d26d0ae9
MD
174 * Generally we recurse down through internal nodes. An
175 * internal node can only be returned if INCLUSTER is set
176 * and the node represents a cluster-push record. Internal
177 * elements do not contain create_tid/delete_tid information.
66325755 178 */
8cd0a023
MD
179 if (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
180 elm = &node->elms[cursor->index];
d26d0ae9
MD
181 r = hammer_btree_cmp(&cursor->key_end, &elm[0].base);
182 s = hammer_btree_cmp(&cursor->key_beg, &elm[1].base);
b3deaf57
MD
183 if (hammer_debug_btree) {
184 kprintf("BRACKETL %p:%d %016llx %02x %016llx %d\n",
185 cursor->node, cursor->index,
186 elm[0].internal.base.obj_id,
187 elm[0].internal.base.rec_type,
188 elm[0].internal.base.key,
189 r
190 );
191 kprintf("BRACKETR %p:%d %016llx %02x %016llx %d\n",
192 cursor->node, cursor->index + 1,
193 elm[1].internal.base.obj_id,
194 elm[1].internal.base.rec_type,
195 elm[1].internal.base.key,
196 s
197 );
198 }
199
d26d0ae9
MD
200 if (r < 0) {
201 error = ENOENT;
202 break;
66325755 203 }
d26d0ae9
MD
204 if (r == 0 && (cursor->flags & HAMMER_CURSOR_END_INCLUSIVE) == 0) {
205 error = ENOENT;
8cd0a023 206 break;
d26d0ae9
MD
207 }
208 KKASSERT(s <= 0);
209 if ((cursor->flags & HAMMER_CURSOR_INCLUSTER) == 0 ||
210 elm->internal.rec_offset == 0) {
211 error = hammer_cursor_down(cursor);
212 if (error)
213 break;
214 KKASSERT(cursor->index == 0);
215 node = cursor->node->ondisk;
216 continue;
217 }
218 } else {
219 elm = &node->elms[cursor->index];
220 r = hammer_btree_cmp(&cursor->key_end, &elm->base);
b3deaf57
MD
221 if (hammer_debug_btree) {
222 kprintf("ELEMENT %p:%d %016llx %02x %016llx %d\n",
223 cursor->node, cursor->index,
224 elm[0].leaf.base.obj_id,
225 elm[0].leaf.base.rec_type,
226 elm[0].leaf.base.key,
227 r
228 );
229 }
d26d0ae9
MD
230 if (r < 0) {
231 error = ENOENT;
232 break;
233 }
234 if (r == 0 && (cursor->flags & HAMMER_CURSOR_END_INCLUSIVE) == 0) {
235 error = ENOENT;
236 break;
237 }
238 if ((cursor->flags & HAMMER_CURSOR_ALLHISTORY) == 0 &&
239 hammer_btree_chkts(cursor->key_beg.create_tid,
240 &elm->base) != 0) {
241 ++cursor->index;
242 continue;
243 }
66325755
MD
244 }
245
246 /*
d26d0ae9 247 * Return entry
66325755 248 */
b3deaf57
MD
249 if (hammer_debug_btree) {
250 int i = cursor->index;
251 hammer_btree_elm_t elm = &cursor->node->ondisk->elms[i];
252 kprintf("ITERATE %p:%d %016llx %02x %016llx\n",
253 cursor->node, i,
254 elm->internal.base.obj_id,
255 elm->internal.base.rec_type,
256 elm->internal.base.key
257 );
258 }
d26d0ae9 259 return(0);
427e5fc6 260 }
66325755 261 return(error);
427e5fc6
MD
262}
263
264/*
8cd0a023
MD
265 * Lookup cursor->key_beg. 0 is returned on success, ENOENT if the entry
266 * could not be found, and a fatal error otherwise.
267 *
268 * The cursor is suitably positioned for a deletion on success, and suitably
269 * positioned for an insertion on ENOENT.
427e5fc6 270 *
8cd0a023
MD
271 * The cursor may begin anywhere, the search will traverse clusters in
272 * either direction to locate the requested element.
427e5fc6
MD
273 */
274int
8cd0a023 275hammer_btree_lookup(hammer_cursor_t cursor)
427e5fc6 276{
66325755
MD
277 int error;
278
8cd0a023
MD
279 error = btree_search(cursor, 0);
280 if (error == 0 && cursor->flags)
281 error = hammer_btree_extract(cursor, cursor->flags);
66325755
MD
282 return(error);
283}
284
d26d0ae9
MD
285/*
286 * Execute the logic required to start an iteration. The first record
287 * located within the specified range is returned and iteration control
288 * flags are adjusted for successive hammer_btree_iterate() calls.
289 */
290int
291hammer_btree_first(hammer_cursor_t cursor)
292{
293 int error;
294
295 error = hammer_btree_lookup(cursor);
296 if (error == ENOENT) {
297 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
298 error = hammer_btree_iterate(cursor);
299 }
300 cursor->flags |= HAMMER_CURSOR_ATEDISK;
301 return(error);
302}
303
8cd0a023
MD
304/*
305 * Extract the record and/or data associated with the cursor's current
306 * position. Any prior record or data stored in the cursor is replaced.
307 * The cursor must be positioned at a leaf node.
308 *
d26d0ae9
MD
309 * NOTE: Most extractions occur at the leaf of the B-Tree. The only
310 * extraction allowed at an internal element is at a cluster-push.
311 * Cluster-push elements have records but no data.
8cd0a023 312 */
66325755 313int
8cd0a023 314hammer_btree_extract(hammer_cursor_t cursor, int flags)
66325755 315{
8cd0a023
MD
316 hammer_node_ondisk_t node;
317 hammer_btree_elm_t elm;
318 hammer_cluster_t cluster;
c0ade690 319 u_int64_t buf_type;
427e5fc6 320 int32_t cloff;
d26d0ae9 321 int32_t roff;
427e5fc6 322 int error;
427e5fc6 323
8cd0a023 324 /*
427e5fc6 325 * A cluster record type has no data reference, the information
8cd0a023 326 * is stored directly in the record and B-Tree element.
427e5fc6
MD
327 *
328 * The case where the data reference resolves to the same buffer
329 * as the record reference must be handled.
330 */
8cd0a023 331 node = cursor->node->ondisk;
8cd0a023
MD
332 elm = &node->elms[cursor->index];
333 cluster = cursor->node->cluster;
d26d0ae9
MD
334 cursor->flags &= ~HAMMER_CURSOR_DATA_EMBEDDED;
335 cursor->data = NULL;
66325755
MD
336 error = 0;
337
d26d0ae9
MD
338 /*
339 * Internal elements can only be cluster pushes. A cluster push has
340 * no data reference.
341 */
342 if (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
343 cloff = elm->leaf.rec_offset;
344 KKASSERT(cloff != 0);
345 cursor->record = hammer_bread(cluster, cloff,
346 HAMMER_FSBUF_RECORDS, &error,
347 &cursor->record_buffer);
348 return(error);
349 }
350
351 /*
352 * Leaf element.
353 */
a89aec1b 354 if ((flags & HAMMER_CURSOR_GET_RECORD) && error == 0) {
8cd0a023
MD
355 cloff = elm->leaf.rec_offset;
356 cursor->record = hammer_bread(cluster, cloff,
357 HAMMER_FSBUF_RECORDS, &error,
358 &cursor->record_buffer);
427e5fc6
MD
359 } else {
360 cloff = 0;
361 }
a89aec1b 362 if ((flags & HAMMER_CURSOR_GET_DATA) && error == 0) {
8cd0a023
MD
363 if ((cloff ^ elm->leaf.data_offset) & ~HAMMER_BUFMASK) {
364 /*
c0ade690
MD
365 * The data is not in the same buffer as the last
366 * record we cached, but it could still be embedded
367 * in a record. Note that we may not have loaded the
368 * record's buffer above, depending on flags.
8cd0a023 369 */
c0ade690
MD
370 if ((elm->leaf.rec_offset ^ elm->leaf.data_offset) &
371 ~HAMMER_BUFMASK) {
372 if (elm->leaf.data_len & HAMMER_BUFMASK)
373 buf_type = HAMMER_FSBUF_DATA;
374 else
375 buf_type = 0; /* pure data buffer */
376 } else {
377 buf_type = HAMMER_FSBUF_RECORDS;
378 }
8cd0a023
MD
379 cursor->data = hammer_bread(cluster,
380 elm->leaf.data_offset,
c0ade690 381 buf_type, &error,
8cd0a023 382 &cursor->data_buffer);
427e5fc6 383 } else {
8cd0a023
MD
384 /*
385 * Data in same buffer as record. Note that we
386 * leave any existing data_buffer intact, even
387 * though we don't use it in this case, in case
388 * other records extracted during an iteration
389 * go back to it.
c0ade690 390 *
d26d0ae9
MD
391 * The data must be embedded in the record for this
392 * case to be hit.
393 *
c0ade690 394 * Just assume the buffer type is correct.
8cd0a023
MD
395 */
396 cursor->data = (void *)
397 ((char *)cursor->record_buffer->ondisk +
398 (elm->leaf.data_offset & HAMMER_BUFMASK));
d26d0ae9
MD
399 roff = (char *)cursor->data - (char *)cursor->record;
400 KKASSERT (roff >= 0 && roff < HAMMER_RECORD_SIZE);
401 cursor->flags |= HAMMER_CURSOR_DATA_EMBEDDED;
427e5fc6
MD
402 }
403 }
404 return(error);
405}
406
407
408/*
8cd0a023
MD
409 * Insert a leaf element into the B-Tree at the current cursor position.
410 * The cursor is positioned such that the element at and beyond the cursor
411 * are shifted to make room for the new record.
412 *
a89aec1b 413 * The caller must call hammer_btree_lookup() with the HAMMER_CURSOR_INSERT
8cd0a023
MD
414 * flag set and that call must return ENOENT before this function can be
415 * called.
416 *
417 * ENOSPC is returned if there is no room to insert a new record.
427e5fc6
MD
418 */
419int
8cd0a023 420hammer_btree_insert(hammer_cursor_t cursor, hammer_btree_elm_t elm)
427e5fc6 421{
8cd0a023
MD
422 hammer_node_ondisk_t parent;
423 hammer_node_ondisk_t node;
427e5fc6
MD
424 int i;
425
66325755
MD
426#if 0
427 /* HANDLED BY CALLER */
427e5fc6
MD
428 /*
429 * Issue a search to get our cursor at the right place. The search
430 * will get us to a leaf node.
431 *
432 * The search also does some setup for our insert, so there is always
433 * room in the leaf.
434 */
a89aec1b 435 error = btree_search(cursor, HAMMER_CURSOR_INSERT);
427e5fc6
MD
436 if (error != ENOENT) {
437 if (error == 0)
438 error = EEXIST;
439 return (error);
440 }
66325755 441#endif
427e5fc6
MD
442
443 /*
444 * Insert the element at the leaf node and update the count in the
445 * parent. It is possible for parent to be NULL, indicating that
8cd0a023 446 * the root of the B-Tree in the cluster is a leaf. It is also
427e5fc6
MD
447 * possible for the leaf to be empty.
448 *
449 * Remember that the right-hand boundary is not included in the
450 * count.
451 */
0b075555 452 hammer_modify_node(cursor->node);
8cd0a023 453 node = cursor->node->ondisk;
427e5fc6 454 i = cursor->index;
8cd0a023
MD
455 KKASSERT(node->type == HAMMER_BTREE_TYPE_LEAF);
456 KKASSERT(node->count < HAMMER_BTREE_LEAF_ELMS);
457 if (i != node->count) {
458 bcopy(&node->elms[i], &node->elms[i+1],
459 (node->count - i) * sizeof(*elm));
460 }
461 node->elms[i] = *elm;
462 ++node->count;
0b075555 463 hammer_modify_node_done(cursor->node);
427e5fc6 464
b3deaf57
MD
465 KKASSERT(hammer_btree_cmp(cursor->left_bound, &elm->leaf.base) <= 0);
466 KKASSERT(hammer_btree_cmp(cursor->right_bound, &elm->leaf.base) > 0);
467 if (i)
468 KKASSERT(hammer_btree_cmp(&node->elms[i-1].leaf.base, &elm->leaf.base) < 0);
469 if (i != node->count - 1)
470 KKASSERT(hammer_btree_cmp(&node->elms[i+1].leaf.base, &elm->leaf.base) > 0);
471
c0ade690
MD
472 /*
473 * Adjust the sub-tree count in the parent. note that the parent
474 * may be in a different cluster.
475 */
476 if (cursor->parent) {
0b075555 477 hammer_modify_node(cursor->parent);
c0ade690 478 parent = cursor->parent->ondisk;
427e5fc6 479 i = cursor->parent_index;
8cd0a023 480 ++parent->elms[i].internal.subtree_count;
0b075555 481 hammer_modify_node_done(cursor->parent);
8cd0a023 482 KKASSERT(parent->elms[i].internal.subtree_count <= node->count);
427e5fc6 483 }
427e5fc6
MD
484 return(0);
485}
486
487/*
8cd0a023
MD
488 * Delete a record from the B-Tree's at the current cursor position.
489 * The cursor is positioned such that the current element is the one
490 * to be deleted.
491 *
195c19a1
MD
492 * On return the cursor will be positioned after the deleted element and
493 * MAY point to an internal node. It will be suitable for the continuation
494 * of an iteration but not for an insertion or deletion.
8cd0a023 495 *
195c19a1
MD
496 * Deletions will attempt to partially rebalance the B-Tree in an upward
497 * direction. It is possible to end up with empty leafs. An empty internal
498 * node is impossible (worst case: it has one element pointing to an empty
499 * leaf).
427e5fc6
MD
500 */
501int
8cd0a023 502hammer_btree_delete(hammer_cursor_t cursor)
427e5fc6 503{
8cd0a023
MD
504 hammer_node_ondisk_t ondisk;
505 hammer_node_t node;
506 hammer_node_t parent;
507 hammer_btree_elm_t elm;
508 int error;
427e5fc6
MD
509 int i;
510
66325755
MD
511#if 0
512 /* HANDLED BY CALLER */
427e5fc6
MD
513 /*
514 * Locate the leaf element to delete. The search is also responsible
515 * for doing some of the rebalancing work on its way down.
516 */
a89aec1b 517 error = btree_search(cursor, HAMMER_CURSOR_DELETE);
427e5fc6
MD
518 if (error)
519 return (error);
66325755 520#endif
427e5fc6
MD
521
522 /*
8cd0a023 523 * Delete the element from the leaf node.
427e5fc6 524 *
8cd0a023 525 * Remember that leaf nodes do not have boundaries.
427e5fc6 526 */
8cd0a023
MD
527 node = cursor->node;
528 ondisk = node->ondisk;
427e5fc6
MD
529 i = cursor->index;
530
8cd0a023 531 KKASSERT(ondisk->type == HAMMER_BTREE_TYPE_LEAF);
0b075555 532 hammer_modify_node(node);
8cd0a023
MD
533 if (i + 1 != ondisk->count) {
534 bcopy(&ondisk->elms[i+1], &ondisk->elms[i],
535 (ondisk->count - i - 1) * sizeof(ondisk->elms[0]));
536 }
537 --ondisk->count;
0b075555 538 hammer_modify_node_done(node);
8cd0a023 539 if (cursor->parent != NULL) {
427e5fc6
MD
540 /*
541 * Adjust parent's notion of the leaf's count. subtree_count
8cd0a023 542 * is only approximate, it is allowed to be too small but
427e5fc6
MD
543 * never allowed to be too large. Make sure we don't drop
544 * the count below 0.
545 */
8cd0a023 546 parent = cursor->parent;
0b075555 547 hammer_modify_node(parent);
8cd0a023
MD
548 elm = &parent->ondisk->elms[cursor->parent_index];
549 if (elm->internal.subtree_count)
550 --elm->internal.subtree_count;
0b075555 551 hammer_modify_node_done(parent);
8cd0a023 552 KKASSERT(elm->internal.subtree_count <= ondisk->count);
427e5fc6 553 }
427e5fc6 554
8cd0a023 555 /*
195c19a1
MD
556 * It is possible, but not desireable, to stop here. If the element
557 * count drops to 0 (which is allowed for a leaf), try recursively
558 * remove the B-Tree node.
8cd0a023 559 *
195c19a1
MD
560 * XXX rebalancing calls would go here too.
561 *
562 * This may reposition the cursor at one of the parent's of the
563 * current node.
8cd0a023 564 */
b3deaf57 565 KKASSERT(cursor->index <= ondisk->count);
8cd0a023 566 if (ondisk->count == 0) {
195c19a1
MD
567 error = btree_remove(cursor);
568 if (error == EAGAIN)
8cd0a023 569 error = 0;
8cd0a023 570 } else {
8cd0a023
MD
571 error = 0;
572 }
573 return(error);
574}
427e5fc6
MD
575
576/*
8cd0a023
MD
577 * PRIMAY B-TREE SEARCH SUPPORT PROCEDURE
578 *
579 * Search a cluster's B-Tree for cursor->key_beg, return the matching node.
580 *
d26d0ae9
MD
581 * The search can begin ANYWHERE in the B-Tree. As a first step the search
582 * iterates up the tree as necessary to properly position itself prior to
583 * actually doing the sarch.
584 *
8cd0a023 585 * INSERTIONS: The search will split full nodes and leaves on its way down
d26d0ae9
MD
586 * and guarentee that the leaf it ends up on is not full. If we run out
587 * of space the search continues to the leaf (to position the cursor for
588 * the spike), but ENOSPC is returned.
427e5fc6 589 *
61aeeb33
MD
590 * XXX this isn't optimal - we really need to just locate the end point and
591 * insert space going up, and if we get a deadlock just release and retry
592 * the operation. Or something like that. The insertion code can transit
593 * multiple clusters and run splits in unnecessary clusters.
594 *
d26d0ae9 595 * DELETIONS: The search will rebalance the tree on its way down. XXX
fbc6e32a
MD
596 *
597 * The search is only guarenteed to end up on a leaf if an error code of 0
598 * is returned, or if inserting and an error code of ENOENT is returned.
d26d0ae9
MD
599 * Otherwise it can stop at an internal node. On success a search returns
600 * a leaf node unless INCLUSTER is set and the search located a cluster push
601 * node (which is an internal node).
427e5fc6 602 */
8cd0a023 603static
427e5fc6 604int
8cd0a023 605btree_search(hammer_cursor_t cursor, int flags)
427e5fc6 606{
8cd0a023
MD
607 hammer_node_ondisk_t node;
608 hammer_cluster_t cluster;
61aeeb33 609 hammer_btree_elm_t elm;
8cd0a023 610 int error;
d26d0ae9 611 int enospc = 0;
8cd0a023
MD
612 int i;
613 int r;
614
615 flags |= cursor->flags;
616
b3deaf57 617 if (hammer_debug_btree) {
d113fda1 618 kprintf("SEARCH %p:%d %016llx %02x key=%016llx tid=%016llx\n",
b3deaf57
MD
619 cursor->node, cursor->index,
620 cursor->key_beg.obj_id,
621 cursor->key_beg.rec_type,
d113fda1
MD
622 cursor->key_beg.key,
623 cursor->key_beg.create_tid
b3deaf57
MD
624 );
625 }
626
8cd0a023
MD
627 /*
628 * Move our cursor up the tree until we find a node whos range covers
629 * the key we are trying to locate. This may move us between
630 * clusters.
631 *
632 * The left bound is inclusive, the right bound is non-inclusive.
633 * It is ok to cursor up too far so when cursoring across a cluster
634 * boundary.
635 *
636 * First see if we can skip the whole cluster. hammer_cursor_up()
637 * handles both cases but this way we don't check the cluster
638 * bounds when going up the tree within a cluster.
d26d0ae9
MD
639 *
640 * NOTE: If INCLUSTER is set and we are at the root of the cluster,
641 * hammer_cursor_up() will return ENOENT.
8cd0a023
MD
642 */
643 cluster = cursor->node->cluster;
644 while (
645 hammer_btree_cmp(&cursor->key_beg, &cluster->clu_btree_beg) < 0 ||
646 hammer_btree_cmp(&cursor->key_beg, &cluster->clu_btree_end) >= 0) {
647 error = hammer_cursor_toroot(cursor);
648 if (error)
649 goto done;
195c19a1 650 error = hammer_cursor_up(cursor, 0);
8cd0a023
MD
651 if (error)
652 goto done;
653 cluster = cursor->node->cluster;
427e5fc6
MD
654 }
655
656 /*
8cd0a023
MD
657 * Deal with normal cursoring within a cluster. The right bound
658 * is non-inclusive. That is, the bounds form a separator.
427e5fc6 659 */
8cd0a023
MD
660 while (hammer_btree_cmp(&cursor->key_beg, cursor->left_bound) < 0 ||
661 hammer_btree_cmp(&cursor->key_beg, cursor->right_bound) >= 0) {
195c19a1 662 error = hammer_cursor_up(cursor, 0);
8cd0a023
MD
663 if (error)
664 goto done;
427e5fc6 665 }
427e5fc6 666
8cd0a023
MD
667 /*
668 * We better have ended up with a node somewhere, and our second
669 * while loop had better not have traversed up a cluster.
670 */
671 KKASSERT(cursor->node != NULL && cursor->node->cluster == cluster);
672
673 /*
674 * If we are inserting we can't start at a full node if the parent
675 * is also full (because there is no way to split the node),
676 * continue running up the tree until we hit the root of the
677 * root cluster or until the requirement is satisfied.
678 *
679 * NOTE: These cursor-up's CAN continue to cross cluster boundaries.
680 *
681 * XXX as an optimization it should be possible to unbalance the tree
682 * and stop at the root of the current cluster.
683 */
61aeeb33 684 while ((flags & HAMMER_CURSOR_INSERT) && enospc == 0) {
8cd0a023
MD
685 if (btree_node_is_full(cursor->node->ondisk) == 0)
686 break;
687 if (cursor->parent == NULL)
688 break;
689 if (cursor->parent->ondisk->count != HAMMER_BTREE_INT_ELMS)
690 break;
195c19a1 691 error = hammer_cursor_up(cursor, 0);
8cd0a023
MD
692 /* cluster and node are now may become stale */
693 if (error)
694 goto done;
427e5fc6 695 }
8cd0a023 696 /* cluster = cursor->node->cluster; not needed until next cluster = */
427e5fc6 697
8cd0a023
MD
698#if 0
699 /*
700 * If we are deleting we can't start at an internal node with only
701 * one element unless it is root, because all of our code assumes
702 * that internal nodes will never be empty. Just do this generally
703 * for both leaf and internal nodes to get better balance.
704 *
705 * This handles the case where the cursor is sitting at a leaf and
706 * either the leaf or parent contain an insufficient number of
707 * elements.
708 *
709 * NOTE: These cursor-up's CAN continue to cross cluster boundaries.
a89aec1b
MD
710 *
711 * XXX NOTE: Iterations may not set this flag anyway.
8cd0a023 712 */
a89aec1b 713 while (flags & HAMMER_CURSOR_DELETE) {
8cd0a023
MD
714 if (cursor->node->ondisk->count > 1)
715 break;
716 if (cursor->parent == NULL)
717 break;
718 KKASSERT(cursor->node->ondisk->count != 0);
195c19a1 719 error = hammer_cursor_up(cursor, 0);
8cd0a023
MD
720 /* cluster and node are now may become stale */
721 if (error)
722 goto done;
723 }
724#endif
427e5fc6 725
8cd0a023
MD
726/*new_cluster:*/
727 /*
728 * Push down through internal nodes to locate the requested key.
729 */
730 cluster = cursor->node->cluster;
731 node = cursor->node->ondisk;
732 while (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
733#if 0
427e5fc6 734 /*
8cd0a023
MD
735 * If we are a the root node and deleting, try to collapse
736 * all of the root's children into the root. This is the
737 * only point where tree depth is reduced.
a89aec1b
MD
738 *
739 * XXX NOTE: Iterations may not set this flag anyway.
427e5fc6 740 */
a89aec1b 741 if ((flags & HAMMER_CURSOR_DELETE) && cursor->parent == NULL) {
8cd0a023
MD
742 error = btree_collapse(cursor);
743 /* node becomes stale after call */
d26d0ae9 744 /* XXX ENOSPC */
8cd0a023
MD
745 if (error)
746 goto done;
66325755 747 }
8cd0a023
MD
748 node = cursor->node->ondisk;
749#endif
8cd0a023
MD
750 /*
751 * Scan the node to find the subtree index to push down into.
fbc6e32a 752 * We go one-past, then back-up.
d113fda1
MD
753 *
754 * We have a serious issue with the midpoints for internal
755 * nodes when the midpoint bisects two historical records
756 * (where only create_tid is different). Short of iterating
757 * through the record's entire history the only solution is
758 * to calculate a midpoint that isn't a midpoint in that
759 * case. Please see hammer_make_separator() for more
760 * information.
8cd0a023
MD
761 */
762 for (i = 0; i < node->count; ++i) {
61aeeb33
MD
763 elm = &node->elms[i];
764 r = hammer_btree_cmp(&cursor->key_beg, &elm->base);
8cd0a023
MD
765 if (r < 0)
766 break;
767 }
8cd0a023
MD
768
769 /*
fbc6e32a
MD
770 * It is possible for the search to terminate at i == 0,
771 * which is to the LEFT of the LEFT boundary but the RIGHT
772 * of the parent's boundary on the left of the sub-tree
773 * element. This case can occur due to deletions (see
774 * btree_remove()).
775 *
776 * When this case occurs an ENOENT return is guarenteed but
777 * if inserting we must still terminate at a leaf. The
778 * solution is to make the node's left boundary inherit the
779 * boundary stored in the parent.
780 *
781 * When doing this inheritance some fields in 'base' are
782 * actually related to the internal element's child
783 * specification and not to the key. These have to be
784 * retained.
d26d0ae9
MD
785 *
786 * If we terminate at i == count it is still possible to
787 * be to the RIGHT of the RIGHT boundary but still to the
788 * LEFT of the parent's RIGHT boundary. The solution is to
789 * adjust the RIGHT boundary to match the parent. This
790 * case can occur due to deletions (see btree_remove()).
8cd0a023 791 */
fbc6e32a
MD
792 if (i == 0) {
793 u_int8_t save;
d26d0ae9 794
fbc6e32a
MD
795 if ((flags & HAMMER_CURSOR_INSERT) == 0) {
796 cursor->index = 0;
797 return(ENOENT);
798 }
0b075555 799 hammer_modify_node(cursor->node);
fbc6e32a
MD
800 save = node->elms[0].subtree_type;
801 node->elms[0].base = *cursor->left_bound;
802 node->elms[0].subtree_type = save;
0b075555 803 hammer_modify_node_done(cursor->node);
d26d0ae9
MD
804 } else if (i == node->count) {
805 /*
806 * Terminate early if not inserting and the key is
807 * beyond the uncorrected right hand boundary. The
808 * index must be PAST the last element to prevent an
809 * iteration from returning elements to the left of
810 * key_beg.
d113fda1
MD
811 *
812 * NOTE: For the case where the right hand boundary
813 * separates two historical records (where only
814 * create_tid differs), we rely on the boundary
815 * being exactly equal to the next record. This
816 * is handled by hammer_make_separator(). If this
817 * were not true we would have to fall through for
818 * the r == 1 case.
d26d0ae9 819 */
61aeeb33 820 elm = &node->elms[i];
d113fda1
MD
821 if ((flags & HAMMER_CURSOR_INSERT) == 0) {
822 r = hammer_btree_cmp(&cursor->key_beg,
61aeeb33 823 &elm->base);
d113fda1
MD
824 if (r >= 0) {
825 cursor->index = i;
826 return(ENOENT);
827 }
d26d0ae9
MD
828 }
829
830 /*
831 * Correct a right-hand boundary mismatch. The push
832 * index is the last element (i-1).
833 */
61aeeb33 834 if (hammer_btree_cmp(&elm->base,
d26d0ae9 835 cursor->right_bound) != 0) {
d26d0ae9 836 hammer_modify_node(cursor->node);
61aeeb33 837 elm->base = *cursor->right_bound;
0b075555 838 hammer_modify_node_done(cursor->node);
d26d0ae9
MD
839 }
840 --i;
fbc6e32a
MD
841 } else {
842 /*
843 * The push-down index is now i - 1.
844 */
845 --i;
846 }
8cd0a023
MD
847 cursor->index = i;
848
b3deaf57 849 if (hammer_debug_btree) {
61aeeb33 850 elm = &node->elms[i];
d113fda1 851 kprintf("SEARCH-I %p:%d %016llx %02x key=%016llx tid=%016llx\n",
b3deaf57
MD
852 cursor->node, i,
853 elm->internal.base.obj_id,
854 elm->internal.base.rec_type,
d113fda1
MD
855 elm->internal.base.key,
856 elm->internal.base.create_tid
b3deaf57
MD
857 );
858 }
859
8cd0a023
MD
860 /*
861 * Handle insertion and deletion requirements.
862 *
863 * If inserting split full nodes. The split code will
864 * adjust cursor->node and cursor->index if the current
865 * index winds up in the new node.
61aeeb33
MD
866 *
867 * If we run out of space we set enospc and continue on
868 * to a leaf to provide the spike code with a good point
869 * of entry. Enospc is reset if we cross a cluster boundary.
8cd0a023 870 */
61aeeb33 871 if ((flags & HAMMER_CURSOR_INSERT) && enospc == 0) {
8cd0a023
MD
872 if (node->count == HAMMER_BTREE_INT_ELMS) {
873 error = btree_split_internal(cursor);
d26d0ae9
MD
874 if (error) {
875 if (error != ENOSPC)
876 goto done;
877 enospc = 1;
d26d0ae9 878 }
8cd0a023
MD
879 /*
880 * reload stale pointers
881 */
882 i = cursor->index;
883 node = cursor->node->ondisk;
884 }
885 }
886
887#if 0
427e5fc6 888 /*
8cd0a023
MD
889 * If deleting rebalance - do not allow the child to have
890 * just one element or we will not be able to delete it.
891 *
892 * Neither internal or leaf nodes (except a root-leaf) are
893 * allowed to drop to 0 elements. (XXX - well, leaf nodes
894 * can at the moment).
895 *
896 * Our separators may have been reorganized after rebalancing,
897 * so we have to pop back up and rescan.
898 *
899 * XXX test for subtree_count < maxelms / 2, minus 1 or 2
900 * for hysteresis?
a89aec1b
MD
901 *
902 * XXX NOTE: Iterations may not set this flag anyway.
427e5fc6 903 */
a89aec1b 904 if (flags & HAMMER_CURSOR_DELETE) {
8cd0a023
MD
905 if (node->elms[i].internal.subtree_count <= 1) {
906 error = btree_rebalance(cursor);
907 if (error)
908 goto done;
909 /* cursor->index is invalid after call */
910 goto new_cluster;
911 }
912 }
913#endif
d26d0ae9 914 /*
61aeeb33
MD
915 * A non-zero rec_offset specifies a cluster push.
916 * If this is a cluster push we reset the enospc flag,
917 * which reenables the insertion code in the new cluster.
918 * This also ensures that if a spike occurs both its node
919 * and its parent will be in the same cluster.
d26d0ae9 920 *
61aeeb33
MD
921 * If INCLUSTER is set we terminate at the cluster boundary.
922 * In this case we must determine whether key_beg is within
923 * the cluster's boundary or not. XXX
d26d0ae9 924 */
61aeeb33
MD
925 elm = &node->elms[i];
926 if (elm->internal.rec_offset) {
927 KKASSERT(elm->subtree_type ==
928 HAMMER_BTREE_TYPE_CLUSTER);
929 enospc = 0;
930 if (flags & HAMMER_CURSOR_INCLUSTER) {
931 KKASSERT((flags & HAMMER_CURSOR_INSERT) == 0);
932 r = hammer_btree_cmp(&cursor->key_beg,
933 &elm[1].base);
934 error = (r < 0) ? 0 : ENOENT;
935 goto done;
936 }
d26d0ae9 937 }
427e5fc6
MD
938
939 /*
8cd0a023 940 * Push down (push into new node, existing node becomes
d26d0ae9 941 * the parent) and continue the search.
427e5fc6 942 */
8cd0a023
MD
943 error = hammer_cursor_down(cursor);
944 /* node and cluster become stale */
945 if (error)
946 goto done;
947 node = cursor->node->ondisk;
948 cluster = cursor->node->cluster;
427e5fc6 949 }
427e5fc6 950
8cd0a023
MD
951 /*
952 * We are at a leaf, do a linear search of the key array.
d26d0ae9
MD
953 *
954 * On success the index is set to the matching element and 0
955 * is returned.
956 *
957 * On failure the index is set to the insertion point and ENOENT
958 * is returned.
8cd0a023
MD
959 *
960 * Boundaries are not stored in leaf nodes, so the index can wind
961 * up to the left of element 0 (index == 0) or past the end of
962 * the array (index == node->count).
963 */
964 KKASSERT(node->count <= HAMMER_BTREE_LEAF_ELMS);
965
966 for (i = 0; i < node->count; ++i) {
967 r = hammer_btree_cmp(&cursor->key_beg, &node->elms[i].base);
427e5fc6 968
427e5fc6 969 /*
d113fda1
MD
970 * Stop if we've flipped past key_beg. This includes a
971 * record whos create_tid is larger then our asof id.
427e5fc6 972 */
8cd0a023
MD
973 if (r < 0)
974 break;
427e5fc6 975
66325755 976 /*
d113fda1
MD
977 * Return an exact match. In this case we have to do special
978 * checks if the only difference in the records is the
979 * create_ts, in order to properly match against our as-of
980 * query.
66325755 981 */
d113fda1
MD
982 if (r >= 0 && r <= 1) {
983 if ((cursor->flags & HAMMER_CURSOR_ALLHISTORY) == 0 &&
984 hammer_btree_chkts(cursor->key_beg.create_tid,
985 &node->elms[i].base) != 0) {
986 continue;
987 }
8cd0a023
MD
988 cursor->index = i;
989 error = 0;
b3deaf57
MD
990 if (hammer_debug_btree) {
991 kprintf("SEARCH-L %p:%d (SUCCESS)\n",
992 cursor->node, i);
993 }
8cd0a023 994 goto done;
66325755 995 }
427e5fc6 996 }
8cd0a023 997
b3deaf57
MD
998 if (hammer_debug_btree) {
999 kprintf("SEARCH-L %p:%d (FAILED)\n",
1000 cursor->node, i);
1001 }
1002
8cd0a023
MD
1003 /*
1004 * No exact match was found, i is now at the insertion point.
1005 *
1006 * If inserting split a full leaf before returning. This
1007 * may have the side effect of adjusting cursor->node and
1008 * cursor->index.
1009 */
1010 cursor->index = i;
a89aec1b 1011 if ((flags & HAMMER_CURSOR_INSERT) &&
8cd0a023
MD
1012 node->count == HAMMER_BTREE_LEAF_ELMS) {
1013 error = btree_split_leaf(cursor);
d26d0ae9
MD
1014 if (error) {
1015 if (error != ENOSPC)
1016 goto done;
1017 enospc = 1;
1018 flags &= ~HAMMER_CURSOR_INSERT;
1019 }
1020 /*
1021 * reload stale pointers
1022 */
8cd0a023
MD
1023 /* NOT USED
1024 i = cursor->index;
1025 node = &cursor->node->internal;
1026 */
8cd0a023 1027 }
d26d0ae9
MD
1028
1029 /*
1030 * We reached a leaf but did not find the key we were looking for.
1031 * If this is an insert we will be properly positioned for an insert
1032 * (ENOENT) or spike (ENOSPC) operation.
1033 */
1034 error = enospc ? ENOSPC : ENOENT;
8cd0a023 1035done:
427e5fc6
MD
1036 return(error);
1037}
1038
8cd0a023 1039
427e5fc6 1040/************************************************************************
8cd0a023 1041 * SPLITTING AND MERGING *
427e5fc6
MD
1042 ************************************************************************
1043 *
1044 * These routines do all the dirty work required to split and merge nodes.
1045 */
1046
1047/*
8cd0a023 1048 * Split an internal node into two nodes and move the separator at the split
427e5fc6
MD
1049 * point to the parent. Note that the parent's parent's element pointing
1050 * to our parent will have an incorrect subtree_count (we don't update it).
1051 * It will be low, which is ok.
1052 *
8cd0a023
MD
1053 * (cursor->node, cursor->index) indicates the element the caller intends
1054 * to push into. We will adjust node and index if that element winds
427e5fc6 1055 * up in the split node.
8cd0a023
MD
1056 *
1057 * If we are at the root of a cluster a new root must be created with two
1058 * elements, one pointing to the original root and one pointing to the
1059 * newly allocated split node.
1060 *
1061 * NOTE! Being at the root of a cluster is different from being at the
1062 * root of the root cluster. cursor->parent will not be NULL and
1063 * cursor->node->ondisk.parent must be tested against 0. Theoretically
1064 * we could propogate the algorithm into the parent and deal with multiple
1065 * 'roots' in the cluster header, but it's easier not to.
427e5fc6
MD
1066 */
1067static
1068int
8cd0a023 1069btree_split_internal(hammer_cursor_t cursor)
427e5fc6 1070{
8cd0a023
MD
1071 hammer_node_ondisk_t ondisk;
1072 hammer_node_t node;
1073 hammer_node_t parent;
1074 hammer_node_t new_node;
1075 hammer_btree_elm_t elm;
1076 hammer_btree_elm_t parent_elm;
427e5fc6
MD
1077 int parent_index;
1078 int made_root;
1079 int split;
1080 int error;
7f7c1f84 1081 int i;
8cd0a023 1082 const int esize = sizeof(*elm);
427e5fc6
MD
1083
1084 /*
1085 * We are splitting but elms[split] will be promoted to the parent,
1086 * leaving the right hand node with one less element. If the
1087 * insertion point will be on the left-hand side adjust the split
1088 * point to give the right hand side one additional node.
1089 */
8cd0a023
MD
1090 node = cursor->node;
1091 ondisk = node->ondisk;
1092 split = (ondisk->count + 1) / 2;
427e5fc6
MD
1093 if (cursor->index <= split)
1094 --split;
1095 error = 0;
1096
1097 /*
8cd0a023 1098 * If we are at the root of the cluster, create a new root node with
427e5fc6
MD
1099 * 1 element and split normally. Avoid making major modifications
1100 * until we know the whole operation will work.
8cd0a023
MD
1101 *
1102 * The root of the cluster is different from the root of the root
1103 * cluster. Use the node's on-disk structure's parent offset to
1104 * detect the case.
427e5fc6 1105 */
8cd0a023
MD
1106 if (ondisk->parent == 0) {
1107 parent = hammer_alloc_btree(node->cluster, &error);
427e5fc6
MD
1108 if (parent == NULL)
1109 return(error);
8cd0a023 1110 hammer_lock_ex(&parent->lock);
0b075555 1111 hammer_modify_node(parent);
8cd0a023
MD
1112 ondisk = parent->ondisk;
1113 ondisk->count = 1;
1114 ondisk->parent = 0;
1115 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1116 ondisk->elms[0].base = node->cluster->clu_btree_beg;
1117 ondisk->elms[0].internal.subtree_type = node->ondisk->type;
1118 ondisk->elms[0].internal.subtree_offset = node->node_offset;
1119 ondisk->elms[1].base = node->cluster->clu_btree_end;
427e5fc6 1120 made_root = 1;
8cd0a023 1121 parent_index = 0; /* index of current node in parent */
0b075555 1122 hammer_modify_node_done(parent);
427e5fc6
MD
1123 } else {
1124 made_root = 0;
8cd0a023
MD
1125 parent = cursor->parent;
1126 parent_index = cursor->parent_index;
195c19a1 1127 KKASSERT(parent->cluster == node->cluster);
427e5fc6 1128 }
427e5fc6
MD
1129
1130 /*
1131 * Split node into new_node at the split point.
1132 *
1133 * B O O O P N N B <-- P = node->elms[split]
1134 * 0 1 2 3 4 5 6 <-- subtree indices
1135 *
1136 * x x P x x
1137 * s S S s
1138 * / \
1139 * B O O O B B N N B <--- inner boundary points are 'P'
1140 * 0 1 2 3 4 5 6
1141 *
1142 */
8cd0a023 1143 new_node = hammer_alloc_btree(node->cluster, &error);
427e5fc6 1144 if (new_node == NULL) {
8cd0a023
MD
1145 if (made_root) {
1146 hammer_unlock(&parent->lock);
b3deaf57 1147 parent->flags |= HAMMER_NODE_DELETED;
8cd0a023
MD
1148 hammer_rel_node(parent);
1149 }
427e5fc6
MD
1150 return(error);
1151 }
8cd0a023 1152 hammer_lock_ex(&new_node->lock);
427e5fc6
MD
1153
1154 /*
8cd0a023 1155 * Create the new node. P becomes the left-hand boundary in the
427e5fc6
MD
1156 * new node. Copy the right-hand boundary as well.
1157 *
1158 * elm is the new separator.
1159 */
0b075555
MD
1160 hammer_modify_node(new_node);
1161 hammer_modify_node(node);
8cd0a023
MD
1162 ondisk = node->ondisk;
1163 elm = &ondisk->elms[split];
1164 bcopy(elm, &new_node->ondisk->elms[0],
1165 (ondisk->count - split + 1) * esize);
1166 new_node->ondisk->count = ondisk->count - split;
1167 new_node->ondisk->parent = parent->node_offset;
1168 new_node->ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1169 KKASSERT(ondisk->type == new_node->ondisk->type);
427e5fc6
MD
1170
1171 /*
1172 * Cleanup the original node. P becomes the new boundary, its
1173 * subtree_offset was moved to the new node. If we had created
1174 * a new root its parent pointer may have changed.
1175 */
8cd0a023 1176 elm->internal.subtree_offset = 0;
0b075555 1177 elm->internal.rec_offset = 0;
c0ade690 1178 ondisk->count = split;
427e5fc6
MD
1179
1180 /*
1181 * Insert the separator into the parent, fixup the parent's
1182 * reference to the original node, and reference the new node.
1183 * The separator is P.
1184 *
1185 * Remember that base.count does not include the right-hand boundary.
1186 */
0b075555 1187 hammer_modify_node(parent);
8cd0a023 1188 ondisk = parent->ondisk;
d26d0ae9 1189 KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
8cd0a023
MD
1190 ondisk->elms[parent_index].internal.subtree_count = split;
1191 parent_elm = &ondisk->elms[parent_index+1];
427e5fc6 1192 bcopy(parent_elm, parent_elm + 1,
8cd0a023
MD
1193 (ondisk->count - parent_index) * esize);
1194 parent_elm->internal.base = elm->base; /* separator P */
1195 parent_elm->internal.subtree_offset = new_node->node_offset;
1196 parent_elm->internal.subtree_count = new_node->ondisk->count;
7f7c1f84 1197 parent_elm->internal.subtree_type = new_node->ondisk->type;
0b075555
MD
1198 parent_elm->internal.subtree_vol_no = 0;
1199 parent_elm->internal.rec_offset = 0;
76376933 1200 ++ondisk->count;
0b075555 1201 hammer_modify_node_done(parent);
427e5fc6 1202
7f7c1f84
MD
1203 /*
1204 * The children of new_node need their parent pointer set to new_node.
1205 */
1206 for (i = 0; i < new_node->ondisk->count; ++i) {
1207 elm = &new_node->ondisk->elms[i];
1208 error = btree_set_parent(new_node, elm);
1209 if (error) {
1210 panic("btree_split_internal: btree-fixup problem");
1211 }
1212 }
1213
427e5fc6
MD
1214 /*
1215 * The cluster's root pointer may have to be updated.
1216 */
1217 if (made_root) {
8cd0a023 1218 hammer_modify_cluster(node->cluster);
0b075555
MD
1219 node->cluster->ondisk->clu_btree_root = parent->node_offset;
1220 hammer_modify_cluster_done(node->cluster);
8cd0a023
MD
1221 node->ondisk->parent = parent->node_offset;
1222 if (cursor->parent) {
1223 hammer_unlock(&cursor->parent->lock);
1224 hammer_rel_node(cursor->parent);
1225 }
1226 cursor->parent = parent; /* lock'd and ref'd */
427e5fc6 1227 }
0b075555
MD
1228 hammer_modify_node_done(new_node);
1229 hammer_modify_node_done(node);
427e5fc6 1230
8cd0a023 1231
427e5fc6
MD
1232 /*
1233 * Ok, now adjust the cursor depending on which element the original
1234 * index was pointing at. If we are >= the split point the push node
1235 * is now in the new node.
1236 *
1237 * NOTE: If we are at the split point itself we cannot stay with the
1238 * original node because the push index will point at the right-hand
1239 * boundary, which is illegal.
8cd0a023
MD
1240 *
1241 * NOTE: The cursor's parent or parent_index must be adjusted for
1242 * the case where a new parent (new root) was created, and the case
1243 * where the cursor is now pointing at the split node.
427e5fc6
MD
1244 */
1245 if (cursor->index >= split) {
8cd0a023 1246 cursor->parent_index = parent_index + 1;
427e5fc6 1247 cursor->index -= split;
8cd0a023
MD
1248 hammer_unlock(&cursor->node->lock);
1249 hammer_rel_node(cursor->node);
1250 cursor->node = new_node; /* locked and ref'd */
1251 } else {
1252 cursor->parent_index = parent_index;
1253 hammer_unlock(&new_node->lock);
1254 hammer_rel_node(new_node);
427e5fc6 1255 }
76376933
MD
1256
1257 /*
1258 * Fixup left and right bounds
1259 */
1260 parent_elm = &parent->ondisk->elms[cursor->parent_index];
fbc6e32a
MD
1261 cursor->left_bound = &parent_elm[0].internal.base;
1262 cursor->right_bound = &parent_elm[1].internal.base;
b3deaf57
MD
1263 KKASSERT(hammer_btree_cmp(cursor->left_bound,
1264 &cursor->node->ondisk->elms[0].internal.base) <= 0);
1265 KKASSERT(hammer_btree_cmp(cursor->right_bound,
1266 &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].internal.base) > 0);
76376933 1267
427e5fc6
MD
1268 return (0);
1269}
1270
1271/*
1272 * Same as the above, but splits a full leaf node.
1273 */
1274static
1275int
8cd0a023 1276btree_split_leaf(hammer_cursor_t cursor)
427e5fc6 1277{
8cd0a023
MD
1278 hammer_node_ondisk_t ondisk;
1279 hammer_node_t parent;
1280 hammer_node_t leaf;
1281 hammer_node_t new_leaf;
1282 hammer_btree_elm_t elm;
1283 hammer_btree_elm_t parent_elm;
b3deaf57 1284 hammer_base_elm_t mid_boundary;
427e5fc6
MD
1285 int parent_index;
1286 int made_root;
1287 int split;
1288 int error;
8cd0a023 1289 const size_t esize = sizeof(*elm);
427e5fc6
MD
1290
1291 /*
8cd0a023
MD
1292 * Calculate the split point. If the insertion point will be on
1293 * the left-hand side adjust the split point to give the right
1294 * hand side one additional node.
427e5fc6 1295 */
8cd0a023
MD
1296 leaf = cursor->node;
1297 ondisk = leaf->ondisk;
1298 split = (ondisk->count + 1) / 2;
427e5fc6
MD
1299 if (cursor->index <= split)
1300 --split;
1301 error = 0;
1302
1303 /*
1304 * If we are at the root of the tree, create a new root node with
1305 * 1 element and split normally. Avoid making major modifications
1306 * until we know the whole operation will work.
1307 */
8cd0a023
MD
1308 if (ondisk->parent == 0) {
1309 parent = hammer_alloc_btree(leaf->cluster, &error);
427e5fc6
MD
1310 if (parent == NULL)
1311 return(error);
8cd0a023 1312 hammer_lock_ex(&parent->lock);
0b075555 1313 hammer_modify_node(parent);
8cd0a023
MD
1314 ondisk = parent->ondisk;
1315 ondisk->count = 1;
1316 ondisk->parent = 0;
1317 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1318 ondisk->elms[0].base = leaf->cluster->clu_btree_beg;
1319 ondisk->elms[0].internal.subtree_type = leaf->ondisk->type;
1320 ondisk->elms[0].internal.subtree_offset = leaf->node_offset;
1321 ondisk->elms[1].base = leaf->cluster->clu_btree_end;
0b075555 1322 hammer_modify_node_done(parent);
427e5fc6 1323 made_root = 1;
8cd0a023 1324 parent_index = 0; /* insertion point in parent */
427e5fc6
MD
1325 } else {
1326 made_root = 0;
8cd0a023
MD
1327 parent = cursor->parent;
1328 parent_index = cursor->parent_index;
195c19a1 1329 KKASSERT(parent->cluster == leaf->cluster);
427e5fc6 1330 }
427e5fc6
MD
1331
1332 /*
1333 * Split leaf into new_leaf at the split point. Select a separator
1334 * value in-between the two leafs but with a bent towards the right
1335 * leaf since comparisons use an 'elm >= separator' inequality.
1336 *
1337 * L L L L L L L L
1338 *
1339 * x x P x x
1340 * s S S s
1341 * / \
1342 * L L L L L L L L
1343 */
8cd0a023 1344 new_leaf = hammer_alloc_btree(leaf->cluster, &error);
427e5fc6 1345 if (new_leaf == NULL) {
8cd0a023
MD
1346 if (made_root) {
1347 hammer_unlock(&parent->lock);
b3deaf57 1348 parent->flags |= HAMMER_NODE_DELETED;
8cd0a023
MD
1349 hammer_rel_node(parent);
1350 }
427e5fc6
MD
1351 return(error);
1352 }
8cd0a023 1353 hammer_lock_ex(&new_leaf->lock);
427e5fc6
MD
1354
1355 /*
1356 * Create the new node. P become the left-hand boundary in the
1357 * new node. Copy the right-hand boundary as well.
1358 */
0b075555
MD
1359 hammer_modify_node(leaf);
1360 hammer_modify_node(new_leaf);
8cd0a023
MD
1361 ondisk = leaf->ondisk;
1362 elm = &ondisk->elms[split];
1363 bcopy(elm, &new_leaf->ondisk->elms[0], (ondisk->count - split) * esize);
1364 new_leaf->ondisk->count = ondisk->count - split;
1365 new_leaf->ondisk->parent = parent->node_offset;
1366 new_leaf->ondisk->type = HAMMER_BTREE_TYPE_LEAF;
1367 KKASSERT(ondisk->type == new_leaf->ondisk->type);
427e5fc6
MD
1368
1369 /*
8cd0a023
MD
1370 * Cleanup the original node. Because this is a leaf node and
1371 * leaf nodes do not have a right-hand boundary, there
c0ade690
MD
1372 * aren't any special edge cases to clean up. We just fixup the
1373 * count.
427e5fc6 1374 */
c0ade690 1375 ondisk->count = split;
427e5fc6
MD
1376
1377 /*
1378 * Insert the separator into the parent, fixup the parent's
1379 * reference to the original node, and reference the new node.
1380 * The separator is P.
1381 *
1382 * Remember that base.count does not include the right-hand boundary.
1383 * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1384 */
0b075555 1385 hammer_modify_node(parent);
8cd0a023 1386 ondisk = parent->ondisk;
d26d0ae9 1387 KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
8cd0a023
MD
1388 ondisk->elms[parent_index].internal.subtree_count = split;
1389 parent_elm = &ondisk->elms[parent_index+1];
d26d0ae9
MD
1390 bcopy(parent_elm, parent_elm + 1,
1391 (ondisk->count - parent_index) * esize);
427e5fc6 1392 hammer_make_separator(&elm[-1].base, &elm[0].base, &parent_elm->base);
8cd0a023
MD
1393 parent_elm->internal.subtree_offset = new_leaf->node_offset;
1394 parent_elm->internal.subtree_count = new_leaf->ondisk->count;
7f7c1f84 1395 parent_elm->internal.subtree_type = new_leaf->ondisk->type;
0b075555
MD
1396 parent_elm->internal.subtree_vol_no = 0;
1397 parent_elm->internal.rec_offset = 0;
b3deaf57 1398 mid_boundary = &parent_elm->base;
76376933 1399 ++ondisk->count;
0b075555 1400 hammer_modify_node_done(parent);
427e5fc6
MD
1401
1402 /*
1403 * The cluster's root pointer may have to be updated.
1404 */
1405 if (made_root) {
8cd0a023 1406 hammer_modify_cluster(leaf->cluster);
0b075555
MD
1407 leaf->cluster->ondisk->clu_btree_root = parent->node_offset;
1408 hammer_modify_cluster_done(leaf->cluster);
8cd0a023
MD
1409 leaf->ondisk->parent = parent->node_offset;
1410 if (cursor->parent) {
1411 hammer_unlock(&cursor->parent->lock);
1412 hammer_rel_node(cursor->parent);
1413 }
1414 cursor->parent = parent; /* lock'd and ref'd */
427e5fc6 1415 }
0b075555
MD
1416 hammer_modify_node_done(leaf);
1417 hammer_modify_node_done(new_leaf);
8cd0a023 1418
427e5fc6
MD
1419 /*
1420 * Ok, now adjust the cursor depending on which element the original
1421 * index was pointing at. If we are >= the split point the push node
1422 * is now in the new node.
1423 *
b3deaf57
MD
1424 * NOTE: If we are at the split point itself we need to select the
1425 * old or new node based on where key_beg's insertion point will be.
1426 * If we pick the wrong side the inserted element will wind up in
1427 * the wrong leaf node and outside that node's bounds.
427e5fc6 1428 */
b3deaf57
MD
1429 if (cursor->index > split ||
1430 (cursor->index == split &&
1431 hammer_btree_cmp(&cursor->key_beg, mid_boundary) >= 0)) {
8cd0a023 1432 cursor->parent_index = parent_index + 1;
427e5fc6 1433 cursor->index -= split;
8cd0a023
MD
1434 hammer_unlock(&cursor->node->lock);
1435 hammer_rel_node(cursor->node);
1436 cursor->node = new_leaf;
1437 } else {
1438 cursor->parent_index = parent_index;
1439 hammer_unlock(&new_leaf->lock);
1440 hammer_rel_node(new_leaf);
427e5fc6 1441 }
76376933
MD
1442
1443 /*
1444 * Fixup left and right bounds
1445 */
1446 parent_elm = &parent->ondisk->elms[cursor->parent_index];
fbc6e32a
MD
1447 cursor->left_bound = &parent_elm[0].internal.base;
1448 cursor->right_bound = &parent_elm[1].internal.base;
b3deaf57
MD
1449 KKASSERT(hammer_btree_cmp(cursor->left_bound,
1450 &cursor->node->ondisk->elms[0].leaf.base) <= 0);
1451 KKASSERT(hammer_btree_cmp(cursor->right_bound,
1452 &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].leaf.base) > 0);
76376933 1453
427e5fc6
MD
1454 return (0);
1455}
1456
1457/*
195c19a1
MD
1458 * Attempt to remove the empty B-Tree node at (cursor->node). Returns 0
1459 * on success, EAGAIN if we could not acquire the necessary locks, or some
1460 * other error.
8cd0a023 1461 *
195c19a1 1462 * On return the cursor may end up pointing at an internal node, suitable
b3deaf57 1463 * for further iteration but not for an immediate insertion or deletion.
8cd0a023 1464 *
195c19a1 1465 * cursor->node may be an internal node or a leaf node.
b3deaf57
MD
1466 *
1467 * NOTE: If cursor->node has one element it is the parent trying to delete
1468 * that element, make sure cursor->index is properly adjusted on success.
8cd0a023
MD
1469 */
1470int
195c19a1 1471btree_remove(hammer_cursor_t cursor)
8cd0a023
MD
1472{
1473 hammer_node_ondisk_t ondisk;
195c19a1
MD
1474 hammer_btree_elm_t elm;
1475 hammer_node_t save;
1476 hammer_node_t node;
8cd0a023
MD
1477 hammer_node_t parent;
1478 int error;
195c19a1 1479 int i;
8cd0a023
MD
1480
1481 /*
195c19a1
MD
1482 * If we are at the root of the root cluster there is nothing to
1483 * remove, but an internal node at the root of a cluster is not
1484 * allowed to be empty so convert it to a leaf node.
8cd0a023 1485 */
195c19a1 1486 if (cursor->parent == NULL) {
0b075555 1487 hammer_modify_node(cursor->node);
195c19a1
MD
1488 ondisk = cursor->node->ondisk;
1489 KKASSERT(ondisk->parent == 0);
1490 ondisk->type = HAMMER_BTREE_TYPE_LEAF;
1491 ondisk->count = 0;
b3deaf57 1492 cursor->index = 0;
0b075555 1493 hammer_modify_node_done(cursor->node);
195c19a1 1494 kprintf("EMPTY ROOT OF ROOT CLUSTER -> LEAF\n");
8cd0a023
MD
1495 return(0);
1496 }
1497
1498 /*
195c19a1
MD
1499 * Retain a reference to cursor->node, ex-lock again (2 locks now)
1500 * so we do not lose the lock when we cursor around.
8cd0a023 1501 */
195c19a1
MD
1502 save = cursor->node;
1503 hammer_ref_node(save);
1504 hammer_lock_ex(&save->lock);
8cd0a023
MD
1505
1506 /*
195c19a1
MD
1507 * We need to be able to lock the parent of the parent. Do this
1508 * non-blocking and return EAGAIN if the lock cannot be acquired.
1509 * non-blocking is required in order to avoid a deadlock.
1510 *
1511 * After we cursor up, parent is moved to node and the new parent
1512 * is the parent of the parent.
8cd0a023 1513 */
195c19a1
MD
1514 error = hammer_cursor_up(cursor, 1);
1515 if (error) {
b3deaf57
MD
1516 kprintf("BTREE_REMOVE: Cannot lock parent, skipping\n");
1517 goto failure;
8cd0a023 1518 }
195c19a1
MD
1519
1520 /*
1521 * At this point we want to remove the element at (node, index),
1522 * which is now the (original) parent pointing to the saved node.
1523 * Removing the element allows us to then free the node it was
1524 * pointing to.
1525 *
1526 * However, an internal node is not allowed to have 0 elements, so
1527 * if the count would drop to 0 we have to recurse. It is possible
1528 * for the recursion to fail.
1529 *
1530 * NOTE: The cursor is in an indeterminant position after recursing,
1531 * but will still be suitable for an iteration.
1532 */
1533 node = cursor->node;
1534 KKASSERT(node->ondisk->count > 0);
1535 if (node->ondisk->count == 1) {
1536 error = btree_remove(cursor);
1537 if (error == 0) {
b3deaf57
MD
1538 /*kprintf("BTREE_REMOVE: Successful!\n");*/
1539 goto success;
195c19a1
MD
1540 } else {
1541 kprintf("BTREE_REMOVE: Recursion failed %d\n", error);
b3deaf57 1542 goto failure;
8cd0a023
MD
1543 }
1544 }
195c19a1
MD
1545
1546 /*
1547 * Remove the element at (node, index) and adjust the parent's
1548 * subtree_count.
fbc6e32a 1549 *
d26d0ae9
MD
1550 * NOTE! If removing element 0 an internal node's left-hand boundary
1551 * will no longer match its parent. If removing a mid-element the
1552 * boundary will no longer match a child's left hand or right hand
1553 * boundary.
1554 *
1555 * BxBxBxB remove a (x[0]): internal node's left-hand
1556 * | | | boundary no longer matches
1557 * a b c parent.
1558 *
1559 * remove b (x[1]): a's right hand boundary no
1560 * longer matches parent.
fbc6e32a 1561 *
d26d0ae9
MD
1562 * remove c (x[2]): b's right hand boundary no
1563 * longer matches parent.
1564 *
1565 * These cases are corrected in btree_search().
195c19a1 1566 */
fbc6e32a 1567#if 0
195c19a1 1568 kprintf("BTREE_REMOVE: Removing element %d\n", cursor->index);
fbc6e32a 1569#endif
b3deaf57
MD
1570 KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
1571 KKASSERT(cursor->index < node->ondisk->count);
0b075555 1572 hammer_modify_node(node);
195c19a1
MD
1573 ondisk = node->ondisk;
1574 i = cursor->index;
1575 bcopy(&ondisk->elms[i+1], &ondisk->elms[i],
1576 (ondisk->count - i) * sizeof(ondisk->elms[0]));
1577 --ondisk->count;
0b075555 1578 hammer_modify_node_done(node);
195c19a1
MD
1579
1580 /*
1581 * Adjust the parent-parent's (now parent) reference to the parent
1582 * (now node).
1583 */
1584 if ((parent = cursor->parent) != NULL) {
1585 elm = &parent->ondisk->elms[cursor->parent_index];
1586 if (elm->internal.subtree_count != ondisk->count) {
195c19a1 1587 hammer_modify_node(parent);
0b075555
MD
1588 elm->internal.subtree_count = ondisk->count;
1589 hammer_modify_node_done(parent);
195c19a1
MD
1590 }
1591 if (elm->subtree_type != HAMMER_BTREE_TYPE_CLUSTER &&
1592 elm->subtree_type != ondisk->type) {
195c19a1 1593 hammer_modify_node(parent);
0b075555
MD
1594 elm->subtree_type = ondisk->type;
1595 hammer_modify_node_done(parent);
8cd0a023
MD
1596 }
1597 }
b3deaf57
MD
1598
1599success:
195c19a1 1600 /*
b3deaf57
MD
1601 * Free the saved node. If the saved node was the root of a
1602 * cluster, free the entire cluster.
195c19a1
MD
1603 */
1604 hammer_flush_node(save);
b3deaf57
MD
1605 save->flags |= HAMMER_NODE_DELETED;
1606
1607 error = 0;
1608failure:
195c19a1
MD
1609 hammer_unlock(&save->lock);
1610 hammer_rel_node(save);
b3deaf57 1611 return(error);
8cd0a023
MD
1612}
1613
7f7c1f84
MD
1614/*
1615 * The child represented by the element in internal node node needs
1616 * to have its parent pointer adjusted.
1617 */
1618static
1619int
1620btree_set_parent(hammer_node_t node, hammer_btree_elm_t elm)
1621{
1622 hammer_volume_t volume;
1623 hammer_cluster_t cluster;
1624 hammer_node_t child;
1625 int error;
1626
1627 error = 0;
1628
1629 switch(elm->internal.subtree_type) {
1630 case HAMMER_BTREE_TYPE_LEAF:
1631 case HAMMER_BTREE_TYPE_INTERNAL:
1632 child = hammer_get_node(node->cluster,
1633 elm->internal.subtree_offset, &error);
1634 if (error == 0) {
0b075555 1635 hammer_modify_node(child);
7f7c1f84
MD
1636 hammer_lock_ex(&child->lock);
1637 child->ondisk->parent = node->node_offset;
7f7c1f84 1638 hammer_unlock(&child->lock);
0b075555 1639 hammer_modify_node_done(child);
7f7c1f84
MD
1640 hammer_rel_node(child);
1641 }
1642 break;
1643 case HAMMER_BTREE_TYPE_CLUSTER:
1644 volume = hammer_get_volume(node->cluster->volume->hmp,
d26d0ae9 1645 elm->internal.subtree_vol_no, &error);
7f7c1f84
MD
1646 if (error)
1647 break;
1648 cluster = hammer_get_cluster(volume,
d26d0ae9 1649 elm->internal.subtree_clu_no,
7f7c1f84
MD
1650 &error, 0);
1651 hammer_rel_volume(volume, 0);
1652 if (error)
1653 break;
0b075555 1654 hammer_modify_cluster(cluster);
7f7c1f84
MD
1655 hammer_lock_ex(&cluster->io.lock);
1656 cluster->ondisk->clu_btree_parent_offset = node->node_offset;
1657 hammer_unlock(&cluster->io.lock);
0b075555 1658 hammer_modify_cluster_done(cluster);
7f7c1f84
MD
1659 KKASSERT(cluster->ondisk->clu_btree_parent_clu_no ==
1660 node->cluster->clu_no);
1661 KKASSERT(cluster->ondisk->clu_btree_parent_vol_no ==
1662 node->cluster->volume->vol_no);
7f7c1f84
MD
1663 hammer_rel_cluster(cluster, 0);
1664 break;
1665 default:
1666 hammer_print_btree_elm(elm, HAMMER_BTREE_TYPE_INTERNAL, -1);
1667 panic("btree_set_parent: bad subtree_type");
1668 break; /* NOT REACHED */
1669 }
1670 return(error);
1671}
1672
8cd0a023
MD
1673#if 0
1674
427e5fc6
MD
1675/*
1676 * This routine is only called if the cursor is at the root node and the
1677 * root node is an internal node. We attempt to collapse the root node
1678 * by replacing it with all of its children, reducing tree depth by one.
1679 *
1680 * This is the only way to reduce tree depth in a HAMMER filesystem.
1681 * Note that all leaf nodes are at the same depth.
1682 *
1683 * This is a fairly expensive operation because we not only have to load
1684 * the root's children, we also have to scan each child and adjust the
1685 * parent offset for each element in each child. Nasty all around.
1686 */
1687static
1688int
8cd0a023 1689btree_collapse(hammer_cursor_t cursor)
427e5fc6 1690{
8cd0a023
MD
1691 hammer_btree_node_ondisk_t root, child;
1692 hammer_btree_node_ondisk_t children[HAMMER_BTREE_INT_ELMS];
427e5fc6
MD
1693 struct hammer_buffer *child_buffer[HAMMER_BTREE_INT_ELMS];
1694 int count;
1695 int i, j, n;
1696 int root_modified;
1697 int error;
1698 int32_t root_offset;
1699 u_int8_t subsubtype;
1700
1701 root = cursor->node;
1702 count = root->base.count;
1703 root_offset = hammer_bclu_offset(cursor->node_buffer, root);
1704
1705 /*
1706 * Sum up the number of children each element has. This value is
1707 * only approximate due to the way the insertion node works. It
1708 * may be too small but it will never be too large.
1709 *
1710 * Quickly terminate the collapse if the elements have too many
1711 * children.
1712 */
1713 KKASSERT(root->base.parent == 0); /* must be root node */
8cd0a023 1714 KKASSERT(root->base.type == HAMMER_BTREE_TYPE_INTERNAL);
427e5fc6
MD
1715 KKASSERT(count <= HAMMER_BTREE_INT_ELMS);
1716
1717 for (i = n = 0; i < count; ++i) {
1718 n += root->internal.elms[i].subtree_count;
1719 }
1720 if (n > btree_max_elements(root->base.subtype))
1721 return(0);
1722
1723 /*
1724 * Iterate through the elements again and correct the subtree_count.
1725 * Terminate the collapse if we wind up with too many.
1726 */
1727 error = 0;
1728 root_modified = 0;
1729
1730 for (i = n = 0; i < count; ++i) {
1731 struct hammer_btree_internal_elm *elm;
1732
1733 elm = &root->internal.elms[i];
1734 child_buffer[i] = NULL;
1735 children[i] = NULL;
1736 if (elm->subtree_offset == 0)
1737 continue;
1738 child = hammer_bread(cursor->cluster, elm->subtree_offset,
1739 HAMMER_FSBUF_BTREE, &error,
8cd0a023 1740 &child_buffer[i], XXX);
427e5fc6
MD
1741 children[i] = child;
1742 if (child == NULL)
1743 continue;
1744 KKASSERT(root->base.subtype == child->base.type);
1745
1746 /*
1747 * Accumulate n for a good child, update the root's count
1748 * if it was wrong.
1749 */
1750 if (root->internal.elms[i].subtree_count != child->base.count) {
1751 root->internal.elms[i].subtree_count = child->base.count;
1752 root_modified = 1;
1753 }
1754 n += root->internal.elms[i].subtree_count;
1755 }
1756 if (error || n > btree_max_elements(root->base.subtype))
1757 goto done;
1758
1759 /*
1760 * Ok, we can collapse the root. If the root's children are leafs
1761 * the collapse is really simple. If they are internal nodes the
1762 * collapse is not so simple because we have to fixup the parent
1763 * pointers for the root's children's children.
1764 *
1765 * When collapsing an internal node the far left and far right
1766 * element's boundaries should match the root's left and right
1767 * boundaries.
1768 */
8cd0a023 1769 if (root->base.subtype == HAMMER_BTREE_TYPE_LEAF) {
427e5fc6
MD
1770 for (i = n = 0; i < count; ++i) {
1771 child = children[i];
1772 for (j = 0; j < child->base.count; ++j) {
1773 root->leaf.elms[n] = child->leaf.elms[j];
1774 ++n;
1775 }
1776 }
1777 root->base.type = root->base.subtype;
1778 root->base.subtype = 0;
1779 root->base.count = n;
1780 root->leaf.link_left = 0;
1781 root->leaf.link_right = 0;
1782 } else {
1783 struct hammer_btree_internal_elm *elm;
1784 struct hammer_btree_internal_node *subchild;
1785 struct hammer_buffer *subchild_buffer = NULL;
1786
1787 if (count) {
1788 child = children[0];
1789 subsubtype = child->base.subtype;
1790 KKASSERT(child->base.count > 0);
1791 KKASSERT(root->internal.elms[0].base.key ==
1792 child->internal.elms[0].base.key);
1793 child = children[count-1];
1794 KKASSERT(child->base.count > 0);
1795 KKASSERT(root->internal.elms[count].base.key ==
1796 child->internal.elms[child->base.count].base.key);
1797 } else {
1798 subsubtype = 0;
1799 }
1800 for (i = n = 0; i < count; ++i) {
1801 child = children[i];
1802 KKASSERT(child->base.subtype == subsubtype);
1803 for (j = 0; j < child->base.count; ++j) {
1804 elm = &child->internal.elms[j];
1805
1806 root->internal.elms[n] = *elm;
1807 subchild = hammer_bread(cursor->cluster,
1808 elm->subtree_offset,
1809 HAMMER_FSBUF_BTREE,
1810 &error,
8cd0a023
MD
1811 &subchild_buffer,
1812 XXX);
427e5fc6
MD
1813 if (subchild) {
1814 subchild->base.parent = root_offset;
1815 hammer_modify_buffer(subchild_buffer);
1816 }
1817 ++n;
1818 }
1819 /* make sure the right boundary is correct */
1820 /* (this gets overwritten when the loop continues) */
1821 /* XXX generate a new separator? */
1822 root->internal.elms[n] = child->internal.elms[j];
1823 }
8cd0a023 1824 root->base.type = HAMMER_BTREE_TYPE_INTERNAL;
427e5fc6
MD
1825 root->base.subtype = subsubtype;
1826 if (subchild_buffer)
66325755 1827 hammer_put_buffer(subchild_buffer, 0);
427e5fc6
MD
1828 }
1829 root_modified = 1;
1830
1831 /*
1832 * Cleanup
1833 */
1834done:
1835 if (root_modified)
1836 hammer_modify_buffer(cursor->node_buffer);
1837 for (i = 0; i < count; ++i) {
1838 if (child_buffer[i])
66325755 1839 hammer_put_buffer(child_buffer[i], 0);
427e5fc6
MD
1840 }
1841 return(error);
1842}
1843
8cd0a023
MD
1844#endif
1845
1846/************************************************************************
1847 * MISCELLANIOUS SUPPORT *
1848 ************************************************************************/
1849
1850/*
d26d0ae9 1851 * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
8cd0a023 1852 *
d113fda1
MD
1853 * Note that for this particular function a return value of -1, 0, or +1
1854 * can denote a match if create_tid is otherwise discounted.
1855 *
8cd0a023 1856 * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
8cd0a023
MD
1857 */
1858int
1859hammer_btree_cmp(hammer_base_elm_t key1, hammer_base_elm_t key2)
1860{
d26d0ae9
MD
1861 if (key1->obj_id < key2->obj_id)
1862 return(-4);
1863 if (key1->obj_id > key2->obj_id)
1864 return(4);
8cd0a023 1865
d26d0ae9
MD
1866 if (key1->rec_type < key2->rec_type)
1867 return(-3);
1868 if (key1->rec_type > key2->rec_type)
1869 return(3);
8cd0a023 1870
8cd0a023
MD
1871 if (key1->key < key2->key)
1872 return(-2);
1873 if (key1->key > key2->key)
1874 return(2);
d113fda1
MD
1875
1876 if (key1->create_tid < key2->create_tid)
1877 return(-1);
1878 if (key1->create_tid > key2->create_tid)
1879 return(1);
8cd0a023
MD
1880 return(0);
1881}
1882
c0ade690 1883/*
d26d0ae9
MD
1884 * Test a non-zero timestamp against an element to determine whether the
1885 * element is visible.
c0ade690
MD
1886 */
1887int
d26d0ae9 1888hammer_btree_chkts(hammer_tid_t create_tid, hammer_base_elm_t base)
c0ade690 1889{
d26d0ae9
MD
1890 if (create_tid < base->create_tid)
1891 return(-1);
1892 if (base->delete_tid && create_tid >= base->delete_tid)
1893 return(1);
c0ade690
MD
1894 return(0);
1895}
1896
8cd0a023
MD
1897/*
1898 * Create a separator half way inbetween key1 and key2. For fields just
1899 * one unit apart, the separator will match key2.
1900 *
d113fda1 1901 * At the moment require that the separator never match key2 exactly.
8cd0a023 1902 *
d113fda1
MD
1903 * We have to special case the separator between two historical keys,
1904 * where all elements except create_tid match. In this case our B-Tree
1905 * searches can't figure out which branch of an internal node to go down
1906 * unless the mid point's create_tid is exactly key2.
1907 * (see btree_search()'s scan code on HAMMER_BTREE_TYPE_INTERNAL).
8cd0a023
MD
1908 */
1909#define MAKE_SEPARATOR(key1, key2, dest, field) \
1910 dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
1911
1912static void
1913hammer_make_separator(hammer_base_elm_t key1, hammer_base_elm_t key2,
1914 hammer_base_elm_t dest)
1915{
1916 bzero(dest, sizeof(*dest));
1917 MAKE_SEPARATOR(key1, key2, dest, obj_id);
1918 MAKE_SEPARATOR(key1, key2, dest, rec_type);
1919 MAKE_SEPARATOR(key1, key2, dest, key);
d113fda1
MD
1920 if (key1->obj_id == key2->obj_id &&
1921 key1->rec_type == key2->rec_type &&
1922 key1->key == key2->key) {
1923 dest->create_tid = key2->create_tid;
1924 } else {
1925 dest->create_tid = 0;
1926 }
8cd0a023
MD
1927}
1928
1929#undef MAKE_SEPARATOR
1930
1931/*
1932 * Return whether a generic internal or leaf node is full
1933 */
1934static int
1935btree_node_is_full(hammer_node_ondisk_t node)
1936{
1937 switch(node->type) {
1938 case HAMMER_BTREE_TYPE_INTERNAL:
1939 if (node->count == HAMMER_BTREE_INT_ELMS)
1940 return(1);
1941 break;
1942 case HAMMER_BTREE_TYPE_LEAF:
1943 if (node->count == HAMMER_BTREE_LEAF_ELMS)
1944 return(1);
1945 break;
1946 default:
1947 panic("illegal btree subtype");
1948 }
1949 return(0);
1950}
1951
1952#if 0
1953static int
1954btree_max_elements(u_int8_t type)
1955{
1956 if (type == HAMMER_BTREE_TYPE_LEAF)
1957 return(HAMMER_BTREE_LEAF_ELMS);
1958 if (type == HAMMER_BTREE_TYPE_INTERNAL)
1959 return(HAMMER_BTREE_INT_ELMS);
1960 panic("btree_max_elements: bad type %d\n", type);
1961}
1962#endif
1963
c0ade690
MD
1964void
1965hammer_print_btree_node(hammer_node_ondisk_t ondisk)
1966{
1967 hammer_btree_elm_t elm;
1968 int i;
1969
1970 kprintf("node %p count=%d parent=%d type=%c\n",
1971 ondisk, ondisk->count, ondisk->parent, ondisk->type);
1972
1973 /*
1974 * Dump both boundary elements if an internal node
1975 */
1976 if (ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
1977 for (i = 0; i <= ondisk->count; ++i) {
1978 elm = &ondisk->elms[i];
1979 hammer_print_btree_elm(elm, ondisk->type, i);
1980 }
1981 } else {
1982 for (i = 0; i < ondisk->count; ++i) {
1983 elm = &ondisk->elms[i];
1984 hammer_print_btree_elm(elm, ondisk->type, i);
1985 }
1986 }
1987}
1988
1989void
1990hammer_print_btree_elm(hammer_btree_elm_t elm, u_int8_t type, int i)
1991{
1992 kprintf(" %2d", i);
1993 kprintf("\tobjid = %016llx\n", elm->base.obj_id);
1994 kprintf("\tkey = %016llx\n", elm->base.key);
1995 kprintf("\tcreate_tid = %016llx\n", elm->base.create_tid);
1996 kprintf("\tdelete_tid = %016llx\n", elm->base.delete_tid);
1997 kprintf("\trec_type = %04x\n", elm->base.rec_type);
1998 kprintf("\tobj_type = %02x\n", elm->base.obj_type);
1999 kprintf("\tsubtree_type = %02x\n", elm->subtree_type);
2000
2001 if (type == HAMMER_BTREE_TYPE_INTERNAL) {
2002 if (elm->internal.rec_offset) {
2003 kprintf("\tcluster_rec = %08x\n",
2004 elm->internal.rec_offset);
2005 kprintf("\tcluster_id = %08x\n",
d26d0ae9 2006 elm->internal.subtree_clu_no);
c0ade690 2007 kprintf("\tvolno = %08x\n",
d26d0ae9 2008 elm->internal.subtree_vol_no);
c0ade690
MD
2009 } else {
2010 kprintf("\tsubtree_off = %08x\n",
2011 elm->internal.subtree_offset);
2012 }
2013 kprintf("\tsubtree_count= %d\n", elm->internal.subtree_count);
2014 } else {
2015 kprintf("\trec_offset = %08x\n", elm->leaf.rec_offset);
2016 kprintf("\tdata_offset = %08x\n", elm->leaf.data_offset);
2017 kprintf("\tdata_len = %08x\n", elm->leaf.data_len);
2018 kprintf("\tdata_crc = %08x\n", elm->leaf.data_crc);
2019 }
2020}