ctree.c (bb8039515d7c1b521ea22f095b43618ccc771885) ctree.c (79f95c82dca7665f32bafd68b7cdf4a01fab0840)
1#include <stdio.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h"
6#include "disk-io.h"
7#include "print-tree.h"
8
9static int split_node(struct ctree_root *root, struct ctree_path *path,
10 int level);
11static int split_leaf(struct ctree_root *root, struct ctree_path *path,
12 int data_size);
13static int push_node_left(struct ctree_root *root, struct tree_buffer *dst,
14 struct tree_buffer *src);
1#include <stdio.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h"
6#include "disk-io.h"
7#include "print-tree.h"
8
9static int split_node(struct ctree_root *root, struct ctree_path *path,
10 int level);
11static int split_leaf(struct ctree_root *root, struct ctree_path *path,
12 int data_size);
13static int push_node_left(struct ctree_root *root, struct tree_buffer *dst,
14 struct tree_buffer *src);
15static int balance_node_right(struct ctree_root *root,
16 struct tree_buffer *dst_buf,
17 struct tree_buffer *src_buf);
15static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level,
16 int slot);
17
18inline void init_path(struct ctree_path *p)
19{
20 memset(p, 0, sizeof(*p));
21}
22

--- 189 unchanged lines hidden (view full) ---

212 struct tree_buffer *parent_buf = NULL;
213 struct node *right = NULL;
214 struct node *mid;
215 struct node *left = NULL;
216 struct node *parent = NULL;
217 int ret = 0;
218 int wret;
219 int pslot;
18static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level,
19 int slot);
20
21inline void init_path(struct ctree_path *p)
22{
23 memset(p, 0, sizeof(*p));
24}
25

--- 189 unchanged lines hidden (view full) ---

215 struct tree_buffer *parent_buf = NULL;
216 struct node *right = NULL;
217 struct node *mid;
218 struct node *left = NULL;
219 struct node *parent = NULL;
220 int ret = 0;
221 int wret;
222 int pslot;
220 int used = 0;
221 int count;
222 int orig_slot = path->slots[level];
223 int orig_slot = path->slots[level];
224 u64 orig_ptr;
223
224 if (level == 0)
225 return 0;
226
227 mid_buf = path->nodes[level];
228 mid = &mid_buf->node;
225
226 if (level == 0)
227 return 0;
228
229 mid_buf = path->nodes[level];
230 mid = &mid_buf->node;
231 orig_ptr = mid->blockptrs[orig_slot];
232
229 if (level < MAX_LEVEL - 1)
230 parent_buf = path->nodes[level + 1];
231 pslot = path->slots[level + 1];
232
233 if (!parent_buf) {
234 struct tree_buffer *child;
235 u64 blocknr = mid_buf->blocknr;
236

--- 11 unchanged lines hidden (view full) ---

248 tree_block_release(root, mid_buf);
249 return free_extent(root, blocknr, 1);
250 }
251 parent = &parent_buf->node;
252
253 if (mid->header.nritems > NODEPTRS_PER_BLOCK / 4)
254 return 0;
255
233 if (level < MAX_LEVEL - 1)
234 parent_buf = path->nodes[level + 1];
235 pslot = path->slots[level + 1];
236
237 if (!parent_buf) {
238 struct tree_buffer *child;
239 u64 blocknr = mid_buf->blocknr;
240

--- 11 unchanged lines hidden (view full) ---

252 tree_block_release(root, mid_buf);
253 return free_extent(root, blocknr, 1);
254 }
255 parent = &parent_buf->node;
256
257 if (mid->header.nritems > NODEPTRS_PER_BLOCK / 4)
258 return 0;
259
256 // print_tree(root, root->node);
257 left_buf = read_node_slot(root, parent_buf, pslot - 1);
258 right_buf = read_node_slot(root, parent_buf, pslot + 1);
260 left_buf = read_node_slot(root, parent_buf, pslot - 1);
261 right_buf = read_node_slot(root, parent_buf, pslot + 1);
259 if (right_buf) {
260 right = &right_buf->node;
261 used = right->header.nritems;
262 count = 1;
263 }
262
263 /* first, try to make some room in the middle buffer */
264 if (left_buf) {
265 left = &left_buf->node;
264 if (left_buf) {
265 left = &left_buf->node;
266 used += left->header.nritems;
267 orig_slot += left->header.nritems;
266 orig_slot += left->header.nritems;
268 count++;
267 wret = push_node_left(root, left_buf, mid_buf);
268 if (wret < 0)
269 ret = wret;
269 }
270 }
270 if (left_buf)
271 push_node_left(root, left_buf, mid_buf);
271
272 /*
273 * then try to empty the right most buffer into the middle
274 */
272 if (right_buf) {
275 if (right_buf) {
273 push_node_left(root, mid_buf, right_buf);
276 right = &right_buf->node;
277 wret = push_node_left(root, mid_buf, right_buf);
278 if (wret < 0)
279 ret = wret;
274 if (right->header.nritems == 0) {
275 u64 blocknr = right_buf->blocknr;
276 tree_block_release(root, right_buf);
277 right_buf = NULL;
278 right = NULL;
279 wret = del_ptr(root, path, level + 1, pslot + 1);
280 if (wret)
281 ret = wret;
282 wret = free_extent(root, blocknr, 1);
283 if (wret)
284 ret = wret;
285 } else {
286 memcpy(parent->keys + pslot + 1, right->keys,
287 sizeof(struct key));
280 if (right->header.nritems == 0) {
281 u64 blocknr = right_buf->blocknr;
282 tree_block_release(root, right_buf);
283 right_buf = NULL;
284 right = NULL;
285 wret = del_ptr(root, path, level + 1, pslot + 1);
286 if (wret)
287 ret = wret;
288 wret = free_extent(root, blocknr, 1);
289 if (wret)
290 ret = wret;
291 } else {
292 memcpy(parent->keys + pslot + 1, right->keys,
293 sizeof(struct key));
294 wret = write_tree_block(root, parent_buf);
295 if (wret)
296 ret = wret;
288 }
289 }
297 }
298 }
299 if (mid->header.nritems == 1) {
300 /*
301 * we're not allowed to leave a node with one item in the
302 * tree during a delete. A deletion from lower in the tree
303 * could try to delete the only pointer in this node.
304 * So, pull some keys from the left.
305 * There has to be a left pointer at this point because
306 * otherwise we would have pulled some pointers from the
307 * right
308 */
309 BUG_ON(!left_buf);
310 wret = balance_node_right(root, mid_buf, left_buf);
311 if (wret < 0)
312 ret = wret;
313 BUG_ON(wret == 1);
314 }
290 if (mid->header.nritems == 0) {
315 if (mid->header.nritems == 0) {
316 /* we've managed to empty the middle node, drop it */
291 u64 blocknr = mid_buf->blocknr;
292 tree_block_release(root, mid_buf);
293 mid_buf = NULL;
294 mid = NULL;
295 wret = del_ptr(root, path, level + 1, pslot);
296 if (wret)
297 ret = wret;
298 wret = free_extent(root, blocknr, 1);
299 if (wret)
300 ret = wret;
317 u64 blocknr = mid_buf->blocknr;
318 tree_block_release(root, mid_buf);
319 mid_buf = NULL;
320 mid = NULL;
321 wret = del_ptr(root, path, level + 1, pslot);
322 if (wret)
323 ret = wret;
324 wret = free_extent(root, blocknr, 1);
325 if (wret)
326 ret = wret;
301 } else
327 } else {
328 /* update the parent key to reflect our changes */
302 memcpy(parent->keys + pslot, mid->keys, sizeof(struct key));
329 memcpy(parent->keys + pslot, mid->keys, sizeof(struct key));
330 wret = write_tree_block(root, parent_buf);
331 if (wret)
332 ret = wret;
333 }
303
334
335 /* update the path */
304 if (left_buf) {
336 if (left_buf) {
305 if (left->header.nritems >= orig_slot) {
337 if (left->header.nritems > orig_slot) {
306 left_buf->count++; // released below
307 path->nodes[level] = left_buf;
308 path->slots[level + 1] -= 1;
309 path->slots[level] = orig_slot;
310 if (mid_buf)
311 tree_block_release(root, mid_buf);
312 } else {
313 orig_slot -= left->header.nritems;
314 path->slots[level] = orig_slot;
315 }
316 }
338 left_buf->count++; // released below
339 path->nodes[level] = left_buf;
340 path->slots[level + 1] -= 1;
341 path->slots[level] = orig_slot;
342 if (mid_buf)
343 tree_block_release(root, mid_buf);
344 } else {
345 orig_slot -= left->header.nritems;
346 path->slots[level] = orig_slot;
347 }
348 }
349 /* double check we haven't messed things up */
350 check_block(path, level);
351 if (orig_ptr != path->nodes[level]->node.blockptrs[path->slots[level]])
352 BUG();
317
318 if (right_buf)
319 tree_block_release(root, right_buf);
320 if (left_buf)
321 tree_block_release(root, left_buf);
353
354 if (right_buf)
355 tree_block_release(root, right_buf);
356 if (left_buf)
357 tree_block_release(root, left_buf);
322
323 return ret;
324}
325
326/*
327 * look for key in the tree. path is filled in with nodes along the way
328 * if key is found, we return zero and you can find the item in the leaf
329 * level of the path (level 0)
330 *

--- 42 unchanged lines hidden (view full) ---

373 int sret = balance_level(root, p, level);
374 if (sret)
375 return sret;
376 b = p->nodes[level];
377 if (!b)
378 goto again;
379 c = &b->node;
380 slot = p->slots[level];
358 return ret;
359}
360
361/*
362 * look for key in the tree. path is filled in with nodes along the way
363 * if key is found, we return zero and you can find the item in the leaf
364 * level of the path (level 0)
365 *

--- 42 unchanged lines hidden (view full) ---

408 int sret = balance_level(root, p, level);
409 if (sret)
410 return sret;
411 b = p->nodes[level];
412 if (!b)
413 goto again;
414 c = &b->node;
415 slot = p->slots[level];
416 BUG_ON(c->header.nritems == 1);
381 }
382 b = read_tree_block(root, c->blockptrs[slot]);
383 } else {
384 struct leaf *l = (struct leaf *)c;
385 p->slots[level] = slot;
386 if (ins_len > 0 && leaf_free_space(l) <
387 sizeof(struct item) + ins_len) {
388 int sret = split_leaf(root, p, ins_len);

--- 39 unchanged lines hidden (view full) ---

428 if (tslot != 0)
429 break;
430 }
431 return ret;
432}
433
434/*
435 * try to push data from one node into the next node left in the
417 }
418 b = read_tree_block(root, c->blockptrs[slot]);
419 } else {
420 struct leaf *l = (struct leaf *)c;
421 p->slots[level] = slot;
422 if (ins_len > 0 && leaf_free_space(l) <
423 sizeof(struct item) + ins_len) {
424 int sret = split_leaf(root, p, ins_len);

--- 39 unchanged lines hidden (view full) ---

464 if (tslot != 0)
465 break;
466 }
467 return ret;
468}
469
470/*
471 * try to push data from one node into the next node left in the
436 * tree. The src node is found at specified level in the path.
437 * If some bytes were pushed, return 0, otherwise return 1.
472 * tree.
438 *
473 *
439 * Lower nodes/leaves in the path are not touched, higher nodes may
440 * be modified to reflect the push.
441 *
442 * The path is altered to reflect the push.
443 *
444 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
445 * error, and > 0 if there was no room in the left hand block.
446 */
447static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf,
448 struct tree_buffer *src_buf)
449{
450 struct node *src = &src_buf->node;
451 struct node *dst = &dst_buf->node;

--- 6 unchanged lines hidden (view full) ---

458 src_nritems = src->header.nritems;
459 dst_nritems = dst->header.nritems;
460 push_items = NODEPTRS_PER_BLOCK - dst_nritems;
461 if (push_items <= 0) {
462 return 1;
463 }
464
465 if (src_nritems < push_items)
474 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
475 * error, and > 0 if there was no room in the left hand block.
476 */
477static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf,
478 struct tree_buffer *src_buf)
479{
480 struct node *src = &src_buf->node;
481 struct node *dst = &dst_buf->node;

--- 6 unchanged lines hidden (view full) ---

488 src_nritems = src->header.nritems;
489 dst_nritems = dst->header.nritems;
490 push_items = NODEPTRS_PER_BLOCK - dst_nritems;
491 if (push_items <= 0) {
492 return 1;
493 }
494
495 if (src_nritems < push_items)
466 push_items =src_nritems;
496 push_items = src_nritems;
497
467 memcpy(dst->keys + dst_nritems, src->keys,
468 push_items * sizeof(struct key));
469 memcpy(dst->blockptrs + dst_nritems, src->blockptrs,
470 push_items * sizeof(u64));
471 if (push_items < src_nritems) {
472 memmove(src->keys, src->keys + push_items,
473 (src_nritems - push_items) * sizeof(struct key));
474 memmove(src->blockptrs, src->blockptrs + push_items,

--- 8 unchanged lines hidden (view full) ---

483
484 wret = write_tree_block(root, dst_buf);
485 if (wret < 0)
486 ret = wret;
487 return ret;
488}
489
490/*
498 memcpy(dst->keys + dst_nritems, src->keys,
499 push_items * sizeof(struct key));
500 memcpy(dst->blockptrs + dst_nritems, src->blockptrs,
501 push_items * sizeof(u64));
502 if (push_items < src_nritems) {
503 memmove(src->keys, src->keys + push_items,
504 (src_nritems - push_items) * sizeof(struct key));
505 memmove(src->blockptrs, src->blockptrs + push_items,

--- 8 unchanged lines hidden (view full) ---

514
515 wret = write_tree_block(root, dst_buf);
516 if (wret < 0)
517 ret = wret;
518 return ret;
519}
520
521/*
522 * try to push data from one node into the next node right in the
523 * tree.
524 *
525 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
526 * error, and > 0 if there was no room in the right hand block.
527 *
528 * this will only push up to 1/2 the contents of the left node over
529 */
530static int balance_node_right(struct ctree_root *root,
531 struct tree_buffer *dst_buf,
532 struct tree_buffer *src_buf)
533{
534 struct node *src = &src_buf->node;
535 struct node *dst = &dst_buf->node;
536 int push_items = 0;
537 int max_push;
538 int src_nritems;
539 int dst_nritems;
540 int ret = 0;
541 int wret;
542
543 src_nritems = src->header.nritems;
544 dst_nritems = dst->header.nritems;
545 push_items = NODEPTRS_PER_BLOCK - dst_nritems;
546 if (push_items <= 0) {
547 return 1;
548 }
549
550 max_push = src_nritems / 2 + 1;
551 /* don't try to empty the node */
552 if (max_push > src_nritems)
553 return 1;
554 if (max_push < push_items)
555 push_items = max_push;
556
557 memmove(dst->keys + push_items, dst->keys,
558 dst_nritems * sizeof(struct key));
559 memmove(dst->blockptrs + push_items, dst->blockptrs,
560 dst_nritems * sizeof(u64));
561 memcpy(dst->keys, src->keys + src_nritems - push_items,
562 push_items * sizeof(struct key));
563 memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items,
564 push_items * sizeof(u64));
565
566 src->header.nritems -= push_items;
567 dst->header.nritems += push_items;
568
569 wret = write_tree_block(root, src_buf);
570 if (wret < 0)
571 ret = wret;
572
573 wret = write_tree_block(root, dst_buf);
574 if (wret < 0)
575 ret = wret;
576 return ret;
577}
578
579/*
491 * helper function to insert a new root level in the tree.
492 * A new node is allocated, and a single item is inserted to
493 * point to the existing root
494 *
495 * returns zero on success or < 0 on failure.
496 */
497static int insert_new_root(struct ctree_root *root,
498 struct ctree_path *path, int level)

--- 714 unchanged lines hidden --- 		580 * helper function to insert a new root level in the tree.
581 * A new node is allocated, and a single item is inserted to
582 * point to the existing root
583 *
584 * returns zero on success or < 0 on failure.
585 */
586static int insert_new_root(struct ctree_root *root,
587 struct ctree_path *path, int level)

--- 714 unchanged lines hidden ---