2 * blkmap64_rb.c --- Simple rb-tree implementation for bitmaps
4 * (C)2010 Red Hat, Inc., Lukas Czerner <lczerner@redhat.com>
7 * This file may be redistributed under the terms of the GNU Public
23 #include <sys/types.h>
33 struct bmap_rb_extent {
39 struct ext2fs_rb_private {
41 struct bmap_rb_extent **wcursor;
42 struct bmap_rb_extent **rcursor;
45 static int rb_insert_extent(__u64 start, __u64 count,
46 struct ext2fs_rb_private *);
47 static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64);
49 /* #define DEBUG_RB */
52 static void print_tree(struct rb_root *root)
54 struct rb_node *node = NULL;
55 struct bmap_rb_extent *ext;
57 printf("\t\t\t=================================\n");
58 node = ext2fs_rb_first(root);
59 for (node = ext2fs_rb_first(root); node != NULL;
60 node = ext2fs_rb_next(node)) {
61 ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
62 printf("\t\t\t--> (%llu -> %llu)\n",
63 ext->start, ext->start + ext->count);
65 printf("\t\t\t=================================\n");
68 static int check_tree(struct rb_root *root, const char *msg)
70 struct rb_node *new_node, *node, *next;
71 struct bmap_rb_extent *ext, *old = NULL;
73 for (node = ext2fs_rb_first(root); node;
74 node = ext2fs_rb_next(node)) {
75 ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
76 if (ext->count <= 0) {
77 printf("Tree Error: count is crazy\n");
78 printf("extent: %llu -> %llu (%u)\n", ext->start,
79 ext->start + ext->count, ext->count);
83 printf("Tree Error: start is crazy\n");
84 printf("extent: %llu -> %llu (%u)\n", ext->start,
85 ext->start + ext->count, ext->count);
90 if (old->start > ext->start) {
91 printf("Tree Error: start is crazy\n");
92 printf("extent: %llu -> %llu (%u)\n",
93 old->start, old->start + old->count,
95 printf("extent next: %llu -> %llu (%u)\n",
96 ext->start, ext->start + ext->count,
100 if ((old->start + old->count) >= ext->start) {
101 printf("Tree Error: extent is crazy\n");
102 printf("extent: %llu -> %llu (%u)\n",
103 old->start, old->start + old->count,
105 printf("extent next: %llu -> %llu (%u)\n",
106 ext->start, ext->start + ext->count,
121 #define check_tree(root, msg) 0
122 #define print_tree(root, msg) 0
125 static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start,
128 struct bmap_rb_extent *new_ext;
131 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
134 perror("ext2fs_get_mem");
138 new_ext->start = start;
139 new_ext->count = count;
144 static void rb_free_extent(struct ext2fs_rb_private *bp,
145 struct bmap_rb_extent *ext)
147 if (*bp->wcursor == ext)
149 if (*bp->rcursor == ext)
151 ext2fs_free_mem(&ext);
154 static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
156 struct ext2fs_rb_private *bp;
159 retval = ext2fs_get_mem(sizeof (struct ext2fs_rb_private), &bp);
164 retval = ext2fs_get_mem(sizeof(struct bmap_rb_extent *), &bp->rcursor);
167 retval = ext2fs_get_mem(sizeof(struct bmap_rb_extent *), &bp->wcursor);
173 bitmap->private = (void *) bp;
177 static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
178 ext2fs_generic_bitmap bitmap)
182 retval = rb_alloc_private_data (bitmap);
189 static void rb_free_tree(struct rb_root *root)
191 struct bmap_rb_extent *ext;
192 struct rb_node *node, *next;
194 for (node = ext2fs_rb_first(root); node; node = next) {
195 next = ext2fs_rb_next(node);
196 ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
197 ext2fs_rb_erase(node, root);
198 ext2fs_free_mem(&ext);
202 static void rb_free_bmap(ext2fs_generic_bitmap bitmap)
204 struct ext2fs_rb_private *bp;
206 bp = (struct ext2fs_rb_private *) bitmap->private;
208 rb_free_tree(&bp->root);
209 ext2fs_free_mem(&bp->rcursor);
210 ext2fs_free_mem(&bp->wcursor);
211 ext2fs_free_mem(&bp);
215 static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src,
216 ext2fs_generic_bitmap dest)
218 struct ext2fs_rb_private *src_bp, *dest_bp;
219 struct bmap_rb_extent *src_ext, *dest_ext;
220 struct rb_node *dest_node, *src_node, *dest_last, **n;
221 errcode_t retval = 0;
223 retval = rb_alloc_private_data (dest);
227 src_bp = (struct ext2fs_rb_private *) src->private;
228 dest_bp = (struct ext2fs_rb_private *) dest->private;
229 *src_bp->rcursor = NULL;
230 *dest_bp->rcursor = NULL;
232 src_node = ext2fs_rb_first(&src_bp->root);
234 src_ext = ext2fs_rb_entry(src_node, struct bmap_rb_extent, node);
235 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
240 memcpy(dest_ext, src_ext, sizeof(struct bmap_rb_extent));
242 dest_node = &dest_ext->node;
243 n = &dest_bp->root.rb_node;
247 dest_last = ext2fs_rb_last(&dest_bp->root);
248 n = &(dest_last)->rb_right;
251 ext2fs_rb_link_node(dest_node, dest_last, n);
252 ext2fs_rb_insert_color(dest_node, &dest_bp->root);
254 src_node = ext2fs_rb_next(src_node);
260 static void rb_truncate(__u64 new_max, struct rb_root *root)
262 struct bmap_rb_extent *ext;
263 struct rb_node *node;
265 node = ext2fs_rb_last(root);
267 ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
269 if ((ext->start + ext->count - 1) <= new_max)
271 else if (ext->start > new_max) {
272 ext2fs_rb_erase(node, root);
273 ext2fs_free_mem(&ext);
274 node = ext2fs_rb_last(root);
277 ext->count = new_max - ext->start + 1;
281 static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
282 __u64 new_end, __u64 new_real_end)
284 struct ext2fs_rb_private *bp;
286 if (new_real_end >= bmap->real_end) {
288 bmap->real_end = new_real_end;
292 bp = (struct ext2fs_rb_private *) bmap->private;
296 /* truncate tree to new_real_end size */
297 rb_truncate(new_real_end, &bp->root);
300 bmap->real_end = new_real_end;
306 rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
308 struct bmap_rb_extent *rcursor;
309 struct rb_node *parent = NULL;
310 struct rb_node **n = &bp->root.rb_node;
311 struct bmap_rb_extent *ext;
314 rcursor = *bp->rcursor;
318 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
321 rcursor = *bp->wcursor;
325 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
332 ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
333 if (bit < ext->start)
335 else if (bit >= (ext->start + ext->count))
345 static int rb_insert_extent(__u64 start, __u64 count,
346 struct ext2fs_rb_private *bp)
348 struct rb_root *root = &bp->root;
349 struct rb_node *parent = NULL, **n = &root->rb_node;
350 struct rb_node *new_node, *node, *next;
351 struct bmap_rb_extent *new_ext;
352 struct bmap_rb_extent *ext;
357 if (start >= ext->start &&
358 start <= (ext->start + ext->count))
364 ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
366 if (start < ext->start) {
368 } else if (start > (ext->start + ext->count)) {
372 if ((start + count) <= (ext->start + ext->count))
375 if ((ext->start + ext->count) == start)
380 count += (start - ext->start);
383 new_node = &ext->node;
389 rb_get_new_extent(&new_ext, start, count);
391 new_node = &new_ext->node;
392 ext2fs_rb_link_node(new_node, parent, n);
393 ext2fs_rb_insert_color(new_node, root);
394 *bp->wcursor = new_ext;
396 node = ext2fs_rb_prev(new_node);
398 ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
399 if ((ext->start + ext->count) == start) {
402 ext2fs_rb_erase(node, root);
403 rb_free_extent(bp, ext);
408 /* See if we can merge extent to the right */
409 for (node = ext2fs_rb_next(new_node); node != NULL; node = next) {
410 next = ext2fs_rb_next(node);
411 ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
413 if ((ext->start + ext->count) <= start)
416 /* No more merging */
417 if ((start + count) < ext->start)
420 /* ext is embedded in new_ext interval */
421 if ((start + count) >= (ext->start + ext->count)) {
422 ext2fs_rb_erase(node, root);
423 rb_free_extent(bp, ext);
426 /* merge ext with new_ext */
427 count += ((ext->start + ext->count) -
429 ext2fs_rb_erase(node, root);
430 rb_free_extent(bp, ext);
435 new_ext->start = start;
436 new_ext->count = count;
441 static int rb_remove_extent(__u64 start, __u64 count,
442 struct ext2fs_rb_private *bp)
444 struct rb_root *root = &bp->root;
445 struct rb_node *parent = NULL, **n = &root->rb_node;
446 struct rb_node *node;
447 struct bmap_rb_extent *ext;
448 __u64 new_start, new_count;
451 if (EXT2FS_RB_EMPTY_ROOT(root))
456 ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
457 if (start < ext->start) {
460 } else if (start >= (ext->start + ext->count)) {
465 if ((start > ext->start) &&
466 (start + count) < (ext->start + ext->count)) {
467 /* We have to split extent into two */
468 new_start = start + count;
469 new_count = (ext->start + ext->count) - new_start;
471 ext->count = start - ext->start;
473 rb_insert_extent(new_start, new_count, bp);
477 if ((start + count) >= (ext->start + ext->count)) {
478 ext->count = start - ext->start;
482 if (0 == ext->count) {
483 parent = ext2fs_rb_next(&ext->node);
484 ext2fs_rb_erase(&ext->node, root);
485 rb_free_extent(bp, ext);
489 if (start == ext->start) {
496 /* See if we should delete or truncate extent on the right */
497 for (; parent != NULL; parent = node) {
498 node = ext2fs_rb_next(parent);
499 ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
500 if ((ext->start + ext->count) <= start)
503 /* No more extents to be removed/truncated */
504 if ((start + count) < ext->start)
507 /* The entire extent is within the region to be removed */
508 if ((start + count) >= (ext->start + ext->count)) {
509 ext2fs_rb_erase(parent, root);
510 rb_free_extent(bp, ext);
514 /* modify the last extent in reigon to be removed */
515 ext->count -= ((start + count) - ext->start);
516 ext->start = start + count;
525 static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
527 struct ext2fs_rb_private *bp;
531 bp = (struct ext2fs_rb_private *) bitmap->private;
532 arg -= bitmap->start;
534 return rb_insert_extent(arg, 1, bp);
537 static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
539 struct ext2fs_rb_private *bp;
542 bp = (struct ext2fs_rb_private *) bitmap->private;
543 arg -= bitmap->start;
545 retval = rb_remove_extent(arg, 1, bp);
546 check_tree(&bp->root, __func__);
552 static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
554 struct ext2fs_rb_private *bp;
556 bp = (struct ext2fs_rb_private *) bitmap->private;
557 arg -= bitmap->start;
559 return rb_test_bit(bp, arg);
562 static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
565 struct ext2fs_rb_private *bp;
566 struct bmap_rb_extent *new_ext;
568 bp = (struct ext2fs_rb_private *) bitmap->private;
569 arg -= bitmap->start;
571 rb_insert_extent(arg, num, bp);
574 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
577 struct ext2fs_rb_private *bp;
580 bp = (struct ext2fs_rb_private *) bitmap->private;
581 arg -= bitmap->start;
583 rb_remove_extent(arg, num, bp);
584 check_tree(&bp->root, __func__);
587 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
588 __u64 start, unsigned int len)
590 struct rb_node *parent = NULL, **n;
591 struct rb_node *node, *next;
592 struct ext2fs_rb_private *bp;
593 struct bmap_rb_extent *ext;
596 bp = (struct ext2fs_rb_private *) bitmap->private;
597 n = &bp->root.rb_node;
598 start -= bitmap->start;
600 if ((len == 0) || EXT2FS_RB_EMPTY_ROOT(&bp->root))
604 * If we find nothing, we should examine whole extent, but
605 * when we find match, the extent is not clean, thus be return
610 ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
611 if (start < ext->start) {
613 } else if (start >= (ext->start + ext->count)) {
617 * We found extent int the tree -> extent is not
626 next = ext2fs_rb_next(node);
627 ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
630 if ((ext->start + ext->count) <= start)
633 /* No more merging */
634 if ((start + len) <= ext->start)
643 static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
644 __u64 start, size_t num, void *in)
646 struct ext2fs_rb_private *bp;
650 bp = (struct ext2fs_rb_private *) bitmap->private;
652 for (i = 0; i < num; i++) {
653 ret = ext2fs_test_bit(i, in);
655 rb_insert_extent(start + i - bitmap->start, 1, bp);
661 static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
662 __u64 start, size_t num, void *out)
665 struct rb_node *parent = NULL, *next, **n;
666 struct ext2fs_rb_private *bp;
667 struct bmap_rb_extent *ext;
670 bp = (struct ext2fs_rb_private *) bitmap->private;
671 n = &bp->root.rb_node;
672 start -= bitmap->start;
674 if (EXT2FS_RB_EMPTY_ROOT(&bp->root))
679 ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
680 if (start < ext->start) {
682 } else if (start >= (ext->start + ext->count)) {
689 for (; parent != NULL; parent = next) {
690 next = ext2fs_rb_next(parent);
691 ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
693 while (((pos - start) < num) &&
694 (pos < ext->start)) {
695 ext2fs_fast_clear_bit64((pos - start), out);
699 if ((pos - start) >= num)
702 while (((pos - start) < num) &&
703 (pos < (ext->start + ext->count))) {
704 ext2fs_fast_set_bit64((pos - start), out);
709 while ((pos - start) < num) {
710 ext2fs_fast_clear_bit64((pos - start), out);
717 static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
719 struct ext2fs_rb_private *bp;
721 bp = (struct ext2fs_rb_private *) bitmap->private;
723 rb_free_tree(&bp->root);
728 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
729 .type = EXT2FS_BMAP64_RBTREE,
730 .new_bmap = rb_new_bmap,
731 .free_bmap = rb_free_bmap,
732 .copy_bmap = rb_copy_bmap,
733 .resize_bmap = rb_resize_bmap,
734 .mark_bmap = rb_mark_bmap,
735 .unmark_bmap = rb_unmark_bmap,
736 .test_bmap = rb_test_bmap,
737 .test_clear_bmap_extent = rb_test_clear_bmap_extent,
738 .mark_bmap_extent = rb_mark_bmap_extent,
739 .unmark_bmap_extent = rb_unmark_bmap_extent,
740 .set_bmap_range = rb_set_bmap_range,
741 .get_bmap_range = rb_get_bmap_range,
742 .clear_bmap = rb_clear_bmap,