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;
43 struct bmap_rb_extent *rcursor_next;
44 #ifdef ENABLE_BMAP_STATS_OPS
50 inline static struct bmap_rb_extent *node_to_extent(struct rb_node *node)
53 * This depends on the fact the struct rb_node is at the
54 * beginning of the bmap_rb_extent structure. We use this
55 * instead of the ext2fs_rb_entry macro because it causes gcc
56 * -Wall to generate a huge amount of noise.
58 return (struct bmap_rb_extent *) node;
61 static int rb_insert_extent(__u64 start, __u64 count,
62 struct ext2fs_rb_private *);
63 static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64);
65 /* #define DEBUG_RB */
68 static void print_tree(struct rb_root *root)
70 struct rb_node *node = NULL;
71 struct bmap_rb_extent *ext;
73 printf("\t\t\t=================================\n");
74 node = ext2fs_rb_first(root);
75 for (node = ext2fs_rb_first(root); node != NULL;
76 node = ext2fs_rb_next(node)) {
77 ext = node_to_extent(node);
78 printf("\t\t\t--> (%llu -> %llu)\n",
79 ext->start, ext->start + ext->count);
81 printf("\t\t\t=================================\n");
84 static void check_tree(struct rb_root *root, const char *msg)
87 struct bmap_rb_extent *ext, *old = NULL;
89 for (node = ext2fs_rb_first(root); node;
90 node = ext2fs_rb_next(node)) {
91 ext = node_to_extent(node);
92 if (ext->count == 0) {
93 printf("Tree Error: count is zero\n");
94 printf("extent: %llu -> %llu (%llu)\n", ext->start,
95 ext->start + ext->count, ext->count);
98 if (ext->start + ext->count < ext->start) {
99 printf("Tree Error: start or count is crazy\n");
100 printf("extent: %llu -> %llu (%llu)\n", ext->start,
101 ext->start + ext->count, ext->count);
106 if (old->start > ext->start) {
107 printf("Tree Error: start is crazy\n");
108 printf("extent: %llu -> %llu (%llu)\n",
109 old->start, old->start + old->count,
111 printf("extent next: %llu -> %llu (%llu)\n",
112 ext->start, ext->start + ext->count,
116 if ((old->start + old->count) >= ext->start) {
117 printf("Tree Error: extent is crazy\n");
118 printf("extent: %llu -> %llu (%llu)\n",
119 old->start, old->start + old->count,
121 printf("extent next: %llu -> %llu (%llu)\n",
122 ext->start, ext->start + ext->count,
137 #define check_tree(root, msg) do {} while (0)
138 #define print_tree(root) do {} while (0)
141 static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start,
144 struct bmap_rb_extent *new_ext;
147 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
152 new_ext->start = start;
153 new_ext->count = count;
158 static void rb_free_extent(struct ext2fs_rb_private *bp,
159 struct bmap_rb_extent *ext)
161 if (bp->wcursor == ext)
163 if (bp->rcursor == ext)
165 if (bp->rcursor_next == ext)
166 bp->rcursor_next = NULL;
167 ext2fs_free_mem(&ext);
170 static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
172 struct ext2fs_rb_private *bp;
175 retval = ext2fs_get_mem(sizeof (struct ext2fs_rb_private), &bp);
181 bp->rcursor_next = NULL;
184 #ifdef ENABLE_BMAP_STATS_OPS
189 bitmap->private = (void *) bp;
193 static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
194 ext2fs_generic_bitmap bitmap)
198 retval = rb_alloc_private_data (bitmap);
205 static void rb_free_tree(struct rb_root *root)
207 struct bmap_rb_extent *ext;
208 struct rb_node *node, *next;
210 for (node = ext2fs_rb_first(root); node; node = next) {
211 next = ext2fs_rb_next(node);
212 ext = node_to_extent(node);
213 ext2fs_rb_erase(node, root);
214 ext2fs_free_mem(&ext);
218 static void rb_free_bmap(ext2fs_generic_bitmap bitmap)
220 struct ext2fs_rb_private *bp;
222 bp = (struct ext2fs_rb_private *) bitmap->private;
224 rb_free_tree(&bp->root);
225 ext2fs_free_mem(&bp);
229 static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src,
230 ext2fs_generic_bitmap dest)
232 struct ext2fs_rb_private *src_bp, *dest_bp;
233 struct bmap_rb_extent *src_ext, *dest_ext;
234 struct rb_node *dest_node, *src_node, *dest_last, **n;
235 errcode_t retval = 0;
237 retval = rb_alloc_private_data (dest);
241 src_bp = (struct ext2fs_rb_private *) src->private;
242 dest_bp = (struct ext2fs_rb_private *) dest->private;
243 src_bp->rcursor = NULL;
244 dest_bp->rcursor = NULL;
246 src_node = ext2fs_rb_first(&src_bp->root);
248 src_ext = node_to_extent(src_node);
249 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
254 memcpy(dest_ext, src_ext, sizeof(struct bmap_rb_extent));
256 dest_node = &dest_ext->node;
257 n = &dest_bp->root.rb_node;
261 dest_last = ext2fs_rb_last(&dest_bp->root);
262 n = &(dest_last)->rb_right;
265 ext2fs_rb_link_node(dest_node, dest_last, n);
266 ext2fs_rb_insert_color(dest_node, &dest_bp->root);
268 src_node = ext2fs_rb_next(src_node);
274 static void rb_truncate(__u64 new_max, struct rb_root *root)
276 struct bmap_rb_extent *ext;
277 struct rb_node *node;
279 node = ext2fs_rb_last(root);
281 ext = node_to_extent(node);
283 if ((ext->start + ext->count - 1) <= new_max)
285 else if (ext->start > new_max) {
286 ext2fs_rb_erase(node, root);
287 ext2fs_free_mem(&ext);
288 node = ext2fs_rb_last(root);
291 ext->count = new_max - ext->start + 1;
295 static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
296 __u64 new_end, __u64 new_real_end)
298 struct ext2fs_rb_private *bp;
300 bp = (struct ext2fs_rb_private *) bmap->private;
304 rb_truncate(((new_end < bmap->end) ? new_end : bmap->end) - bmap->start,
308 bmap->real_end = new_real_end;
310 if (bmap->end < bmap->real_end)
311 rb_insert_extent(bmap->end + 1 - bmap->start,
312 bmap->real_end - bmap->end, bp);
318 rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
320 struct bmap_rb_extent *rcursor, *next_ext = NULL;
321 struct rb_node *parent = NULL, *next;
322 struct rb_node **n = &bp->root.rb_node;
323 struct bmap_rb_extent *ext;
325 rcursor = bp->rcursor;
329 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) {
330 #ifdef ENABLE_BMAP_STATS_OPS
336 next_ext = bp->rcursor_next;
338 next = ext2fs_rb_next(&rcursor->node);
340 next_ext = node_to_extent(next);
341 bp->rcursor_next = next_ext;
344 if ((bit >= rcursor->start + rcursor->count) &&
345 (bit < next_ext->start)) {
346 #ifdef BMAP_STATS_OPS
353 bp->rcursor_next = NULL;
355 rcursor = bp->wcursor;
359 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
366 ext = node_to_extent(parent);
367 if (bit < ext->start)
369 else if (bit >= (ext->start + ext->count))
373 bp->rcursor_next = NULL;
380 static int rb_insert_extent(__u64 start, __u64 count,
381 struct ext2fs_rb_private *bp)
383 struct rb_root *root = &bp->root;
384 struct rb_node *parent = NULL, **n = &root->rb_node;
385 struct rb_node *new_node, *node, *next;
386 struct bmap_rb_extent *new_ext;
387 struct bmap_rb_extent *ext;
390 bp->rcursor_next = NULL;
393 if (start >= ext->start &&
394 start <= (ext->start + ext->count)) {
395 #ifdef ENABLE_BMAP_STATS_OPS
404 ext = node_to_extent(parent);
406 if (start < ext->start) {
408 } else if (start > (ext->start + ext->count)) {
412 if ((start + count) <= (ext->start + ext->count))
415 if ((ext->start + ext->count) == start)
420 count += (start - ext->start);
423 new_node = &ext->node;
429 rb_get_new_extent(&new_ext, start, count);
431 new_node = &new_ext->node;
432 ext2fs_rb_link_node(new_node, parent, n);
433 ext2fs_rb_insert_color(new_node, root);
434 bp->wcursor = new_ext;
436 node = ext2fs_rb_prev(new_node);
438 ext = node_to_extent(node);
439 if ((ext->start + ext->count) == start) {
442 ext2fs_rb_erase(node, root);
443 rb_free_extent(bp, ext);
448 /* See if we can merge extent to the right */
449 for (node = ext2fs_rb_next(new_node); node != NULL; node = next) {
450 next = ext2fs_rb_next(node);
451 ext = node_to_extent(node);
453 if ((ext->start + ext->count) <= start)
456 /* No more merging */
457 if ((start + count) < ext->start)
460 /* ext is embedded in new_ext interval */
461 if ((start + count) >= (ext->start + ext->count)) {
462 ext2fs_rb_erase(node, root);
463 rb_free_extent(bp, ext);
466 /* merge ext with new_ext */
467 count += ((ext->start + ext->count) -
469 ext2fs_rb_erase(node, root);
470 rb_free_extent(bp, ext);
475 new_ext->start = start;
476 new_ext->count = count;
481 static int rb_remove_extent(__u64 start, __u64 count,
482 struct ext2fs_rb_private *bp)
484 struct rb_root *root = &bp->root;
485 struct rb_node *parent = NULL, **n = &root->rb_node;
486 struct rb_node *node;
487 struct bmap_rb_extent *ext;
488 __u64 new_start, new_count;
491 if (ext2fs_rb_empty_root(root))
496 ext = node_to_extent(parent);
497 if (start < ext->start) {
500 } else if (start >= (ext->start + ext->count)) {
505 if ((start > ext->start) &&
506 (start + count) < (ext->start + ext->count)) {
507 /* We have to split extent into two */
508 new_start = start + count;
509 new_count = (ext->start + ext->count) - new_start;
511 ext->count = start - ext->start;
513 rb_insert_extent(new_start, new_count, bp);
517 if ((start + count) >= (ext->start + ext->count)) {
518 ext->count = start - ext->start;
522 if (0 == ext->count) {
523 parent = ext2fs_rb_next(&ext->node);
524 ext2fs_rb_erase(&ext->node, root);
525 rb_free_extent(bp, ext);
529 if (start == ext->start) {
536 /* See if we should delete or truncate extent on the right */
537 for (; parent != NULL; parent = node) {
538 node = ext2fs_rb_next(parent);
539 ext = node_to_extent(parent);
540 if ((ext->start + ext->count) <= start)
543 /* No more extents to be removed/truncated */
544 if ((start + count) < ext->start)
547 /* The entire extent is within the region to be removed */
548 if ((start + count) >= (ext->start + ext->count)) {
549 ext2fs_rb_erase(parent, root);
550 rb_free_extent(bp, ext);
554 /* modify the last extent in reigon to be removed */
555 ext->count -= ((start + count) - ext->start);
556 ext->start = start + count;
565 static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
567 struct ext2fs_rb_private *bp;
570 bp = (struct ext2fs_rb_private *) bitmap->private;
571 arg -= bitmap->start;
573 retval = rb_insert_extent(arg, 1, bp);
574 check_tree(&bp->root, __func__);
578 static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
580 struct ext2fs_rb_private *bp;
583 bp = (struct ext2fs_rb_private *) bitmap->private;
584 arg -= bitmap->start;
586 retval = rb_remove_extent(arg, 1, bp);
587 check_tree(&bp->root, __func__);
593 static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
595 struct ext2fs_rb_private *bp;
597 bp = (struct ext2fs_rb_private *) bitmap->private;
598 arg -= bitmap->start;
600 return rb_test_bit(bp, arg);
603 static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
606 struct ext2fs_rb_private *bp;
608 bp = (struct ext2fs_rb_private *) bitmap->private;
609 arg -= bitmap->start;
611 rb_insert_extent(arg, num, bp);
612 check_tree(&bp->root, __func__);
615 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
618 struct ext2fs_rb_private *bp;
620 bp = (struct ext2fs_rb_private *) bitmap->private;
621 arg -= bitmap->start;
623 rb_remove_extent(arg, num, bp);
624 check_tree(&bp->root, __func__);
627 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
628 __u64 start, unsigned int len)
630 struct rb_node *parent = NULL, **n;
631 struct rb_node *node, *next;
632 struct ext2fs_rb_private *bp;
633 struct bmap_rb_extent *ext;
636 bp = (struct ext2fs_rb_private *) bitmap->private;
637 n = &bp->root.rb_node;
638 start -= bitmap->start;
640 if (len == 0 || ext2fs_rb_empty_root(&bp->root))
644 * If we find nothing, we should examine whole extent, but
645 * when we find match, the extent is not clean, thus be return
650 ext = node_to_extent(parent);
651 if (start < ext->start) {
653 } else if (start >= (ext->start + ext->count)) {
657 * We found extent int the tree -> extent is not
666 next = ext2fs_rb_next(node);
667 ext = node_to_extent(node);
670 if ((ext->start + ext->count) <= start)
673 /* No more merging */
674 if ((start + len) <= ext->start)
683 static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
684 __u64 start, size_t num, void *in)
686 struct ext2fs_rb_private *bp;
687 unsigned char *cp = in;
691 bp = (struct ext2fs_rb_private *) bitmap->private;
693 for (i = 0; i < num; i++) {
695 unsigned char c = cp[i/8];
702 if ((c == 0x00) && (first_set == -1)) {
707 if (ext2fs_test_bit(i, in)) {
715 rb_insert_extent(start + first_set - bitmap->start,
717 check_tree(&bp->root, __func__);
720 if (first_set != -1) {
721 rb_insert_extent(start + first_set - bitmap->start,
722 num - first_set, bp);
723 check_tree(&bp->root, __func__);
729 static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
730 __u64 start, size_t num, void *out)
733 struct rb_node *parent = NULL, *next, **n;
734 struct ext2fs_rb_private *bp;
735 struct bmap_rb_extent *ext;
738 bp = (struct ext2fs_rb_private *) bitmap->private;
739 n = &bp->root.rb_node;
740 start -= bitmap->start;
742 if (ext2fs_rb_empty_root(&bp->root))
747 ext = node_to_extent(parent);
748 if (start < ext->start) {
750 } else if (start >= (ext->start + ext->count)) {
756 memset(out, 0, (num + 7) >> 3);
758 for (; parent != NULL; parent = next) {
759 next = ext2fs_rb_next(parent);
760 ext = node_to_extent(parent);
764 if (pos >= start + num)
767 if (pos + count < start)
769 count -= start - pos;
772 if (pos + count > start + num)
773 count = start + num - pos;
777 ((pos - start) % 8) == 0) {
778 int nbytes = count >> 3;
779 int offset = (pos - start) >> 3;
781 memset(((char *) out) + offset, 0xFF, nbytes);
783 count -= nbytes << 3;
786 ext2fs_fast_set_bit64((pos - start), out);
794 static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
796 struct ext2fs_rb_private *bp;
798 bp = (struct ext2fs_rb_private *) bitmap->private;
800 rb_free_tree(&bp->root);
802 bp->rcursor_next = NULL;
804 check_tree(&bp->root, __func__);
807 static errcode_t rb_find_first_zero(ext2fs_generic_bitmap bitmap,
808 __u64 start, __u64 end, __u64 *out)
810 struct rb_node *parent = NULL, **n;
811 struct ext2fs_rb_private *bp;
812 struct bmap_rb_extent *ext;
814 bp = (struct ext2fs_rb_private *) bitmap->private;
815 n = &bp->root.rb_node;
816 start -= bitmap->start;
817 end -= bitmap->start;
822 if (ext2fs_rb_empty_root(&bp->root))
827 ext = node_to_extent(parent);
828 if (start < ext->start) {
830 } else if (start >= (ext->start + ext->count)) {
832 } else if (ext->start + ext->count <= end) {
833 *out = ext->start + ext->count + bitmap->start;
839 *out = start + bitmap->start;
843 static errcode_t rb_find_first_set(ext2fs_generic_bitmap bitmap,
844 __u64 start, __u64 end, __u64 *out)
846 struct rb_node *parent = NULL, **n;
847 struct rb_node *node;
848 struct ext2fs_rb_private *bp;
849 struct bmap_rb_extent *ext;
851 bp = (struct ext2fs_rb_private *) bitmap->private;
852 n = &bp->root.rb_node;
853 start -= bitmap->start;
854 end -= bitmap->start;
859 if (ext2fs_rb_empty_root(&bp->root))
864 ext = node_to_extent(parent);
865 if (start < ext->start) {
867 } else if (start >= (ext->start + ext->count)) {
870 /* The start bit is set */
871 *out = start + bitmap->start;
877 ext = node_to_extent(node);
878 if (ext->start < start) {
879 node = ext2fs_rb_next(node);
882 ext = node_to_extent(node);
884 if (ext->start <= end) {
885 *out = ext->start + bitmap->start;
891 #ifdef ENABLE_BMAP_STATS
892 static void rb_print_stats(ext2fs_generic_bitmap bitmap)
894 struct ext2fs_rb_private *bp;
895 struct rb_node *node = NULL;
896 struct bmap_rb_extent *ext;
899 __u64 min_size = ULONG_MAX;
900 __u64 size = 0, avg_size = 0;
902 #ifdef ENABLE_BMAP_STATS_OPS
903 __u64 mark_all, test_all;
904 double m_hit = 0.0, t_hit = 0.0;
907 bp = (struct ext2fs_rb_private *) bitmap->private;
909 for (node = ext2fs_rb_first(&bp->root); node != NULL;
910 node = ext2fs_rb_next(node)) {
911 ext = node_to_extent(node);
913 if (ext->count > max_size)
914 max_size = ext->count;
915 if (ext->count < min_size)
916 min_size = ext->count;
921 avg_size = size / count;
922 if (min_size == ULONG_MAX)
924 eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) /
925 (bitmap->real_end - bitmap->start);
926 #ifdef ENABLE_BMAP_STATS_OPS
927 mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count;
928 test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count;
930 m_hit = ((double)bp->mark_hit / mark_all) * 100;
932 t_hit = ((double)bp->test_hit / test_all) * 100;
934 fprintf(stderr, "%16llu cache hits on test (%.2f%%)\n"
935 "%16llu cache hits on mark (%.2f%%)\n",
936 bp->test_hit, t_hit, bp->mark_hit, m_hit);
938 fprintf(stderr, "%16llu extents (%llu bytes)\n",
939 count, ((count * sizeof(struct bmap_rb_extent)) +
940 sizeof(struct ext2fs_rb_private)));
941 fprintf(stderr, "%16llu bits minimum size\n",
943 fprintf(stderr, "%16llu bits maximum size\n"
944 "%16llu bits average size\n",
946 fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", size,
947 bitmap->real_end - bitmap->start);
949 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
953 static void rb_print_stats(ext2fs_generic_bitmap bitmap EXT2FS_ATTR((unused)))
958 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
959 .type = EXT2FS_BMAP64_RBTREE,
960 .new_bmap = rb_new_bmap,
961 .free_bmap = rb_free_bmap,
962 .copy_bmap = rb_copy_bmap,
963 .resize_bmap = rb_resize_bmap,
964 .mark_bmap = rb_mark_bmap,
965 .unmark_bmap = rb_unmark_bmap,
966 .test_bmap = rb_test_bmap,
967 .test_clear_bmap_extent = rb_test_clear_bmap_extent,
968 .mark_bmap_extent = rb_mark_bmap_extent,
969 .unmark_bmap_extent = rb_unmark_bmap_extent,
970 .set_bmap_range = rb_set_bmap_range,
971 .get_bmap_range = rb_get_bmap_range,
972 .clear_bmap = rb_clear_bmap,
973 .print_stats = rb_print_stats,
974 .find_first_zero = rb_find_first_zero,
975 .find_first_set = rb_find_first_set,