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
)
86 struct rb_node
*new_node
, *node
, *next
;
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 crazy\n");
94 printf("extent: %llu -> %llu (%u)\n", ext
->start
,
95 ext
->start
+ ext
->count
, ext
->count
);
99 printf("Tree Error: start is crazy\n");
100 printf("extent: %llu -> %llu (%u)\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 (%u)\n",
109 old
->start
, old
->start
+ old
->count
,
111 printf("extent next: %llu -> %llu (%u)\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 (%u)\n",
119 old
->start
, old
->start
+ old
->count
,
121 printf("extent next: %llu -> %llu (%u)\n",
122 ext
->start
, ext
->start
+ ext
->count
,
137 #define check_tree(root, msg) do {} while (0)
138 #define print_tree(root, msg) 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 if (new_real_end
>= bmap
->real_end
) {
302 bmap
->real_end
= new_real_end
;
306 bp
= (struct ext2fs_rb_private
*) bmap
->private;
310 /* truncate tree to new_real_end size */
311 rb_truncate(new_real_end
, &bp
->root
);
314 bmap
->real_end
= new_real_end
;
320 rb_test_bit(struct ext2fs_rb_private
*bp
, __u64 bit
)
322 struct bmap_rb_extent
*rcursor
, *next_ext
= NULL
;
323 struct rb_node
*parent
= NULL
, *next
;
324 struct rb_node
**n
= &bp
->root
.rb_node
;
325 struct bmap_rb_extent
*ext
;
327 rcursor
= bp
->rcursor
;
331 if (bit
>= rcursor
->start
&& bit
< rcursor
->start
+ rcursor
->count
) {
332 #ifdef ENABLE_BMAP_STATS_OPS
338 next_ext
= bp
->rcursor_next
;
340 next
= ext2fs_rb_next(&rcursor
->node
);
342 next_ext
= node_to_extent(next
);
343 bp
->rcursor_next
= next_ext
;
346 if ((bit
>= rcursor
->start
+ rcursor
->count
) &&
347 (bit
< next_ext
->start
)) {
348 #ifdef BMAP_STATS_OPS
355 bp
->rcursor_next
= NULL
;
357 rcursor
= bp
->wcursor
;
361 if (bit
>= rcursor
->start
&& bit
< rcursor
->start
+ rcursor
->count
)
368 ext
= node_to_extent(parent
);
369 if (bit
< ext
->start
)
371 else if (bit
>= (ext
->start
+ ext
->count
))
375 bp
->rcursor_next
= NULL
;
382 static int rb_insert_extent(__u64 start
, __u64 count
,
383 struct ext2fs_rb_private
*bp
)
385 struct rb_root
*root
= &bp
->root
;
386 struct rb_node
*parent
= NULL
, **n
= &root
->rb_node
;
387 struct rb_node
*new_node
, *node
, *next
;
388 struct bmap_rb_extent
*new_ext
;
389 struct bmap_rb_extent
*ext
;
392 bp
->rcursor_next
= NULL
;
395 if (start
>= ext
->start
&&
396 start
<= (ext
->start
+ ext
->count
)) {
397 #ifdef ENABLE_BMAP_STATS_OPS
406 ext
= node_to_extent(parent
);
408 if (start
< ext
->start
) {
410 } else if (start
> (ext
->start
+ ext
->count
)) {
414 if ((start
+ count
) <= (ext
->start
+ ext
->count
))
417 if ((ext
->start
+ ext
->count
) == start
)
422 count
+= (start
- ext
->start
);
425 new_node
= &ext
->node
;
431 rb_get_new_extent(&new_ext
, start
, count
);
433 new_node
= &new_ext
->node
;
434 ext2fs_rb_link_node(new_node
, parent
, n
);
435 ext2fs_rb_insert_color(new_node
, root
);
436 bp
->wcursor
= new_ext
;
438 node
= ext2fs_rb_prev(new_node
);
440 ext
= node_to_extent(node
);
441 if ((ext
->start
+ ext
->count
) == start
) {
444 ext2fs_rb_erase(node
, root
);
445 rb_free_extent(bp
, ext
);
450 /* See if we can merge extent to the right */
451 for (node
= ext2fs_rb_next(new_node
); node
!= NULL
; node
= next
) {
452 next
= ext2fs_rb_next(node
);
453 ext
= node_to_extent(node
);
455 if ((ext
->start
+ ext
->count
) <= start
)
458 /* No more merging */
459 if ((start
+ count
) < ext
->start
)
462 /* ext is embedded in new_ext interval */
463 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
464 ext2fs_rb_erase(node
, root
);
465 rb_free_extent(bp
, ext
);
468 /* merge ext with new_ext */
469 count
+= ((ext
->start
+ ext
->count
) -
471 ext2fs_rb_erase(node
, root
);
472 rb_free_extent(bp
, ext
);
477 new_ext
->start
= start
;
478 new_ext
->count
= count
;
483 static int rb_remove_extent(__u64 start
, __u64 count
,
484 struct ext2fs_rb_private
*bp
)
486 struct rb_root
*root
= &bp
->root
;
487 struct rb_node
*parent
= NULL
, **n
= &root
->rb_node
;
488 struct rb_node
*node
;
489 struct bmap_rb_extent
*ext
;
490 __u64 new_start
, new_count
;
493 if (EXT2FS_RB_EMPTY_ROOT(root
))
498 ext
= node_to_extent(parent
);
499 if (start
< ext
->start
) {
502 } else if (start
>= (ext
->start
+ ext
->count
)) {
507 if ((start
> ext
->start
) &&
508 (start
+ count
) < (ext
->start
+ ext
->count
)) {
509 /* We have to split extent into two */
510 new_start
= start
+ count
;
511 new_count
= (ext
->start
+ ext
->count
) - new_start
;
513 ext
->count
= start
- ext
->start
;
515 rb_insert_extent(new_start
, new_count
, bp
);
519 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
520 ext
->count
= start
- ext
->start
;
524 if (0 == ext
->count
) {
525 parent
= ext2fs_rb_next(&ext
->node
);
526 ext2fs_rb_erase(&ext
->node
, root
);
527 rb_free_extent(bp
, ext
);
531 if (start
== ext
->start
) {
538 /* See if we should delete or truncate extent on the right */
539 for (; parent
!= NULL
; parent
= node
) {
540 node
= ext2fs_rb_next(parent
);
541 ext
= node_to_extent(parent
);
542 if ((ext
->start
+ ext
->count
) <= start
)
545 /* No more extents to be removed/truncated */
546 if ((start
+ count
) < ext
->start
)
549 /* The entire extent is within the region to be removed */
550 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
551 ext2fs_rb_erase(parent
, root
);
552 rb_free_extent(bp
, ext
);
556 /* modify the last extent in reigon to be removed */
557 ext
->count
-= ((start
+ count
) - ext
->start
);
558 ext
->start
= start
+ count
;
567 static int rb_mark_bmap(ext2fs_generic_bitmap bitmap
, __u64 arg
)
569 struct ext2fs_rb_private
*bp
;
571 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
572 arg
-= bitmap
->start
;
574 return rb_insert_extent(arg
, 1, bp
);
577 static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap
, __u64 arg
)
579 struct ext2fs_rb_private
*bp
;
582 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
583 arg
-= bitmap
->start
;
585 retval
= rb_remove_extent(arg
, 1, bp
);
586 check_tree(&bp
->root
, __func__
);
592 static int rb_test_bmap(ext2fs_generic_bitmap bitmap
, __u64 arg
)
594 struct ext2fs_rb_private
*bp
;
596 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
597 arg
-= bitmap
->start
;
599 return rb_test_bit(bp
, arg
);
602 static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap
, __u64 arg
,
605 struct ext2fs_rb_private
*bp
;
607 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
608 arg
-= bitmap
->start
;
610 rb_insert_extent(arg
, num
, bp
);
613 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap
, __u64 arg
,
616 struct ext2fs_rb_private
*bp
;
618 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
619 arg
-= bitmap
->start
;
621 rb_remove_extent(arg
, num
, bp
);
622 check_tree(&bp
->root
, __func__
);
625 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap
,
626 __u64 start
, unsigned int len
)
628 struct rb_node
*parent
= NULL
, **n
;
629 struct rb_node
*node
, *next
;
630 struct ext2fs_rb_private
*bp
;
631 struct bmap_rb_extent
*ext
;
634 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
635 n
= &bp
->root
.rb_node
;
636 start
-= bitmap
->start
;
638 if ((len
== 0) || EXT2FS_RB_EMPTY_ROOT(&bp
->root
))
642 * If we find nothing, we should examine whole extent, but
643 * when we find match, the extent is not clean, thus be return
648 ext
= node_to_extent(parent
);
649 if (start
< ext
->start
) {
651 } else if (start
>= (ext
->start
+ ext
->count
)) {
655 * We found extent int the tree -> extent is not
664 next
= ext2fs_rb_next(node
);
665 ext
= node_to_extent(node
);
668 if ((ext
->start
+ ext
->count
) <= start
)
671 /* No more merging */
672 if ((start
+ len
) <= ext
->start
)
681 static errcode_t
rb_set_bmap_range(ext2fs_generic_bitmap bitmap
,
682 __u64 start
, size_t num
, void *in
)
684 struct ext2fs_rb_private
*bp
;
685 unsigned char *cp
= in
;
689 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
691 for (i
= 0; i
< num
; i
++) {
693 unsigned char c
= cp
[i
/8];
700 if ((c
== 0x00) && (first_set
== -1)) {
705 if (ext2fs_test_bit(i
, in
)) {
713 rb_insert_extent(start
+ first_set
- bitmap
->start
,
718 rb_insert_extent(start
+ first_set
- bitmap
->start
,
719 num
- first_set
, bp
);
724 static errcode_t
rb_get_bmap_range(ext2fs_generic_bitmap bitmap
,
725 __u64 start
, size_t num
, void *out
)
728 struct rb_node
*parent
= NULL
, *next
, **n
;
729 struct ext2fs_rb_private
*bp
;
730 struct bmap_rb_extent
*ext
;
734 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
735 n
= &bp
->root
.rb_node
;
736 start
-= bitmap
->start
;
738 if (EXT2FS_RB_EMPTY_ROOT(&bp
->root
))
743 ext
= node_to_extent(parent
);
744 if (start
< ext
->start
) {
746 } else if (start
>= (ext
->start
+ ext
->count
)) {
752 memset(out
, 0, (num
+ 7) >> 3);
754 for (; parent
!= NULL
; parent
= next
) {
755 next
= ext2fs_rb_next(parent
);
756 ext
= node_to_extent(parent
);
760 if (pos
>= start
+ num
)
763 count
-= start
- pos
;
768 if (pos
+ count
> start
+ num
)
769 count
= start
+ num
- pos
;
773 ((pos
- start
) % 8) == 0) {
774 int nbytes
= count
>> 3;
775 int offset
= (pos
- start
) >> 3;
777 memset(((char *) out
) + offset
, 0xFF, nbytes
);
779 count
-= nbytes
<< 3;
782 ext2fs_fast_set_bit64((pos
- start
), out
);
790 static void rb_clear_bmap(ext2fs_generic_bitmap bitmap
)
792 struct ext2fs_rb_private
*bp
;
794 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
796 rb_free_tree(&bp
->root
);
798 bp
->rcursor_next
= NULL
;
802 #ifdef ENABLE_BMAP_STATS
803 static void rb_print_stats(ext2fs_generic_bitmap bitmap
)
805 struct ext2fs_rb_private
*bp
;
806 struct rb_node
*node
= NULL
;
807 struct bmap_rb_extent
*ext
;
810 __u64 min_size
= ULONG_MAX
;
811 __u64 size
= 0, avg_size
= 0;
813 #ifdef ENABLE_BMAP_STATS_OPS
814 __u64 mark_all
, test_all
;
815 double m_hit
= 0.0, t_hit
= 0.0;
818 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
820 for (node
= ext2fs_rb_first(&bp
->root
); node
!= NULL
;
821 node
= ext2fs_rb_next(node
)) {
822 ext
= node_to_extent(node
);
824 if (ext
->count
> max_size
)
825 max_size
= ext
->count
;
826 if (ext
->count
< min_size
)
827 min_size
= ext
->count
;
832 avg_size
= size
/ count
;
833 if (min_size
== ULONG_MAX
)
835 eff
= (double)((count
* sizeof(struct bmap_rb_extent
)) << 3) /
836 (bitmap
->real_end
- bitmap
->start
);
837 #ifdef ENABLE_BMAP_STATS_OPS
838 mark_all
= bitmap
->stats
.mark_count
+ bitmap
->stats
.mark_ext_count
;
839 test_all
= bitmap
->stats
.test_count
+ bitmap
->stats
.test_ext_count
;
841 m_hit
= ((double)bp
->mark_hit
/ mark_all
) * 100;
843 t_hit
= ((double)bp
->test_hit
/ test_all
) * 100;
845 fprintf(stderr
, "%16llu cache hits on test (%.2f%%)\n"
846 "%16llu cache hits on mark (%.2f%%)\n",
847 bp
->test_hit
, t_hit
, bp
->mark_hit
, m_hit
);
849 fprintf(stderr
, "%16llu extents (%llu bytes)\n",
850 count
, ((count
* sizeof(struct bmap_rb_extent
)) +
851 sizeof(struct ext2fs_rb_private
)));
852 fprintf(stderr
, "%16llu bits minimum size\n",
854 fprintf(stderr
, "%16llu bits maximum size\n"
855 "%16llu bits average size\n",
857 fprintf(stderr
, "%16llu bits set in bitmap (out of %llu)\n", size
,
858 bitmap
->real_end
- bitmap
->start
);
860 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
864 static void rb_print_stats(ext2fs_generic_bitmap bitmap
EXT2FS_ATTR((unused
)))
869 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree
= {
870 .type
= EXT2FS_BMAP64_RBTREE
,
871 .new_bmap
= rb_new_bmap
,
872 .free_bmap
= rb_free_bmap
,
873 .copy_bmap
= rb_copy_bmap
,
874 .resize_bmap
= rb_resize_bmap
,
875 .mark_bmap
= rb_mark_bmap
,
876 .unmark_bmap
= rb_unmark_bmap
,
877 .test_bmap
= rb_test_bmap
,
878 .test_clear_bmap_extent
= rb_test_clear_bmap_extent
,
879 .mark_bmap_extent
= rb_mark_bmap_extent
,
880 .unmark_bmap_extent
= rb_unmark_bmap_extent
,
881 .set_bmap_range
= rb_set_bmap_range
,
882 .get_bmap_range
= rb_get_bmap_range
,
883 .clear_bmap
= rb_clear_bmap
,
884 .print_stats
= rb_print_stats
,