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
24 #include <sys/types.h>
26 #if HAVE_LINUX_TYPES_H
27 #include <linux/types.h>
37 struct bmap_rb_extent
{
43 struct ext2fs_rb_private
{
45 struct bmap_rb_extent
*wcursor
;
46 struct bmap_rb_extent
*rcursor
;
47 struct bmap_rb_extent
*rcursor_next
;
48 #ifdef ENABLE_BMAP_STATS_OPS
54 inline static struct bmap_rb_extent
*node_to_extent(struct rb_node
*node
)
57 * This depends on the fact the struct rb_node is at the
58 * beginning of the bmap_rb_extent structure. We use this
59 * instead of the ext2fs_rb_entry macro because it causes gcc
60 * -Wall to generate a huge amount of noise.
62 return (struct bmap_rb_extent
*) node
;
65 static int rb_insert_extent(__u64 start
, __u64 count
,
66 struct ext2fs_rb_private
*);
67 static void rb_get_new_extent(struct bmap_rb_extent
**, __u64
, __u64
);
69 /* #define DEBUG_RB */
72 static void print_tree(struct rb_root
*root
)
74 struct rb_node
*node
= NULL
;
75 struct bmap_rb_extent
*ext
;
77 printf("\t\t\t=================================\n");
78 node
= ext2fs_rb_first(root
);
79 for (node
= ext2fs_rb_first(root
); node
!= NULL
;
80 node
= ext2fs_rb_next(node
)) {
81 ext
= node_to_extent(node
);
82 printf("\t\t\t--> (%llu -> %llu)\n",
83 ext
->start
, ext
->start
+ ext
->count
);
85 printf("\t\t\t=================================\n");
88 static void check_tree(struct rb_root
*root
, const char *msg
)
91 struct bmap_rb_extent
*ext
, *old
= NULL
;
93 for (node
= ext2fs_rb_first(root
); node
;
94 node
= ext2fs_rb_next(node
)) {
95 ext
= node_to_extent(node
);
96 if (ext
->count
== 0) {
97 printf("Tree Error: count is zero\n");
98 printf("extent: %llu -> %llu (%llu)\n", ext
->start
,
99 ext
->start
+ ext
->count
, ext
->count
);
102 if (ext
->start
+ ext
->count
< ext
->start
) {
103 printf("Tree Error: start or count is crazy\n");
104 printf("extent: %llu -> %llu (%llu)\n", ext
->start
,
105 ext
->start
+ ext
->count
, ext
->count
);
110 if (old
->start
> ext
->start
) {
111 printf("Tree Error: start is crazy\n");
112 printf("extent: %llu -> %llu (%llu)\n",
113 old
->start
, old
->start
+ old
->count
,
115 printf("extent next: %llu -> %llu (%llu)\n",
116 ext
->start
, ext
->start
+ ext
->count
,
120 if ((old
->start
+ old
->count
) >= ext
->start
) {
121 printf("Tree Error: extent is crazy\n");
122 printf("extent: %llu -> %llu (%llu)\n",
123 old
->start
, old
->start
+ old
->count
,
125 printf("extent next: %llu -> %llu (%llu)\n",
126 ext
->start
, ext
->start
+ ext
->count
,
141 #define check_tree(root, msg) do {} while (0)
142 #define print_tree(root) do {} while (0)
145 static void rb_get_new_extent(struct bmap_rb_extent
**ext
, __u64 start
,
148 struct bmap_rb_extent
*new_ext
;
151 retval
= ext2fs_get_mem(sizeof (struct bmap_rb_extent
),
156 new_ext
->start
= start
;
157 new_ext
->count
= count
;
162 static void rb_free_extent(struct ext2fs_rb_private
*bp
,
163 struct bmap_rb_extent
*ext
)
165 if (bp
->wcursor
== ext
)
167 if (bp
->rcursor
== ext
)
169 if (bp
->rcursor_next
== ext
)
170 bp
->rcursor_next
= NULL
;
171 ext2fs_free_mem(&ext
);
174 static errcode_t
rb_alloc_private_data (ext2fs_generic_bitmap bitmap
)
176 struct ext2fs_rb_private
*bp
;
179 retval
= ext2fs_get_mem(sizeof (struct ext2fs_rb_private
), &bp
);
185 bp
->rcursor_next
= NULL
;
188 #ifdef ENABLE_BMAP_STATS_OPS
193 bitmap
->private = (void *) bp
;
197 static errcode_t
rb_new_bmap(ext2_filsys fs
EXT2FS_ATTR((unused
)),
198 ext2fs_generic_bitmap bitmap
)
202 retval
= rb_alloc_private_data (bitmap
);
209 static void rb_free_tree(struct rb_root
*root
)
211 struct bmap_rb_extent
*ext
;
212 struct rb_node
*node
, *next
;
214 for (node
= ext2fs_rb_first(root
); node
; node
= next
) {
215 next
= ext2fs_rb_next(node
);
216 ext
= node_to_extent(node
);
217 ext2fs_rb_erase(node
, root
);
218 ext2fs_free_mem(&ext
);
222 static void rb_free_bmap(ext2fs_generic_bitmap bitmap
)
224 struct ext2fs_rb_private
*bp
;
226 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
228 rb_free_tree(&bp
->root
);
229 ext2fs_free_mem(&bp
);
233 static errcode_t
rb_copy_bmap(ext2fs_generic_bitmap src
,
234 ext2fs_generic_bitmap dest
)
236 struct ext2fs_rb_private
*src_bp
, *dest_bp
;
237 struct bmap_rb_extent
*src_ext
, *dest_ext
;
238 struct rb_node
*dest_node
, *src_node
, *dest_last
, **n
;
239 errcode_t retval
= 0;
241 retval
= rb_alloc_private_data (dest
);
245 src_bp
= (struct ext2fs_rb_private
*) src
->private;
246 dest_bp
= (struct ext2fs_rb_private
*) dest
->private;
247 src_bp
->rcursor
= NULL
;
248 dest_bp
->rcursor
= NULL
;
250 src_node
= ext2fs_rb_first(&src_bp
->root
);
252 src_ext
= node_to_extent(src_node
);
253 retval
= ext2fs_get_mem(sizeof (struct bmap_rb_extent
),
258 memcpy(dest_ext
, src_ext
, sizeof(struct bmap_rb_extent
));
260 dest_node
= &dest_ext
->node
;
261 n
= &dest_bp
->root
.rb_node
;
265 dest_last
= ext2fs_rb_last(&dest_bp
->root
);
266 n
= &(dest_last
)->rb_right
;
269 ext2fs_rb_link_node(dest_node
, dest_last
, n
);
270 ext2fs_rb_insert_color(dest_node
, &dest_bp
->root
);
272 src_node
= ext2fs_rb_next(src_node
);
278 static void rb_truncate(__u64 new_max
, struct rb_root
*root
)
280 struct bmap_rb_extent
*ext
;
281 struct rb_node
*node
;
283 node
= ext2fs_rb_last(root
);
285 ext
= node_to_extent(node
);
287 if ((ext
->start
+ ext
->count
- 1) <= new_max
)
289 else if (ext
->start
> new_max
) {
290 ext2fs_rb_erase(node
, root
);
291 ext2fs_free_mem(&ext
);
292 node
= ext2fs_rb_last(root
);
295 ext
->count
= new_max
- ext
->start
+ 1;
299 static errcode_t
rb_resize_bmap(ext2fs_generic_bitmap bmap
,
300 __u64 new_end
, __u64 new_real_end
)
302 struct ext2fs_rb_private
*bp
;
304 bp
= (struct ext2fs_rb_private
*) bmap
->private;
308 rb_truncate(((new_end
< bmap
->end
) ? new_end
: bmap
->end
) - bmap
->start
,
312 bmap
->real_end
= new_real_end
;
314 if (bmap
->end
< bmap
->real_end
)
315 rb_insert_extent(bmap
->end
+ 1 - bmap
->start
,
316 bmap
->real_end
- bmap
->end
, bp
);
322 rb_test_bit(struct ext2fs_rb_private
*bp
, __u64 bit
)
324 struct bmap_rb_extent
*rcursor
, *next_ext
= NULL
;
325 struct rb_node
*parent
= NULL
, *next
;
326 struct rb_node
**n
= &bp
->root
.rb_node
;
327 struct bmap_rb_extent
*ext
;
329 rcursor
= bp
->rcursor
;
333 if (bit
>= rcursor
->start
&& bit
< rcursor
->start
+ rcursor
->count
) {
334 #ifdef ENABLE_BMAP_STATS_OPS
340 next_ext
= bp
->rcursor_next
;
342 next
= ext2fs_rb_next(&rcursor
->node
);
344 next_ext
= node_to_extent(next
);
345 bp
->rcursor_next
= next_ext
;
348 if ((bit
>= rcursor
->start
+ rcursor
->count
) &&
349 (bit
< next_ext
->start
)) {
350 #ifdef BMAP_STATS_OPS
357 bp
->rcursor_next
= NULL
;
359 rcursor
= bp
->wcursor
;
363 if (bit
>= rcursor
->start
&& bit
< rcursor
->start
+ rcursor
->count
)
370 ext
= node_to_extent(parent
);
371 if (bit
< ext
->start
)
373 else if (bit
>= (ext
->start
+ ext
->count
))
377 bp
->rcursor_next
= NULL
;
384 static int rb_insert_extent(__u64 start
, __u64 count
,
385 struct ext2fs_rb_private
*bp
)
387 struct rb_root
*root
= &bp
->root
;
388 struct rb_node
*parent
= NULL
, **n
= &root
->rb_node
;
389 struct rb_node
*new_node
, *node
, *next
;
390 struct bmap_rb_extent
*new_ext
;
391 struct bmap_rb_extent
*ext
;
394 bp
->rcursor_next
= NULL
;
397 if (start
>= ext
->start
&&
398 start
<= (ext
->start
+ ext
->count
)) {
399 #ifdef ENABLE_BMAP_STATS_OPS
408 ext
= node_to_extent(parent
);
410 if (start
< ext
->start
) {
412 } else if (start
> (ext
->start
+ ext
->count
)) {
416 if ((start
+ count
) <= (ext
->start
+ ext
->count
))
419 if ((ext
->start
+ ext
->count
) == start
)
424 count
+= (start
- ext
->start
);
427 new_node
= &ext
->node
;
433 rb_get_new_extent(&new_ext
, start
, count
);
435 new_node
= &new_ext
->node
;
436 ext2fs_rb_link_node(new_node
, parent
, n
);
437 ext2fs_rb_insert_color(new_node
, root
);
438 bp
->wcursor
= new_ext
;
440 node
= ext2fs_rb_prev(new_node
);
442 ext
= node_to_extent(node
);
443 if ((ext
->start
+ ext
->count
) == start
) {
446 ext2fs_rb_erase(node
, root
);
447 rb_free_extent(bp
, ext
);
452 /* See if we can merge extent to the right */
453 for (node
= ext2fs_rb_next(new_node
); node
!= NULL
; node
= next
) {
454 next
= ext2fs_rb_next(node
);
455 ext
= node_to_extent(node
);
457 if ((ext
->start
+ ext
->count
) <= start
)
460 /* No more merging */
461 if ((start
+ count
) < ext
->start
)
464 /* ext is embedded in new_ext interval */
465 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
466 ext2fs_rb_erase(node
, root
);
467 rb_free_extent(bp
, ext
);
470 /* merge ext with new_ext */
471 count
+= ((ext
->start
+ ext
->count
) -
473 ext2fs_rb_erase(node
, root
);
474 rb_free_extent(bp
, ext
);
479 new_ext
->start
= start
;
480 new_ext
->count
= count
;
485 static int rb_remove_extent(__u64 start
, __u64 count
,
486 struct ext2fs_rb_private
*bp
)
488 struct rb_root
*root
= &bp
->root
;
489 struct rb_node
*parent
= NULL
, **n
= &root
->rb_node
;
490 struct rb_node
*node
;
491 struct bmap_rb_extent
*ext
;
492 __u64 new_start
, new_count
;
495 if (ext2fs_rb_empty_root(root
))
500 ext
= node_to_extent(parent
);
501 if (start
< ext
->start
) {
504 } else if (start
>= (ext
->start
+ ext
->count
)) {
509 if ((start
> ext
->start
) &&
510 (start
+ count
) < (ext
->start
+ ext
->count
)) {
511 /* We have to split extent into two */
512 new_start
= start
+ count
;
513 new_count
= (ext
->start
+ ext
->count
) - new_start
;
515 ext
->count
= start
- ext
->start
;
517 rb_insert_extent(new_start
, new_count
, bp
);
521 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
522 ext
->count
= start
- ext
->start
;
526 if (0 == ext
->count
) {
527 parent
= ext2fs_rb_next(&ext
->node
);
528 ext2fs_rb_erase(&ext
->node
, root
);
529 rb_free_extent(bp
, ext
);
533 if (start
== ext
->start
) {
540 /* See if we should delete or truncate extent on the right */
541 for (; parent
!= NULL
; parent
= node
) {
542 node
= ext2fs_rb_next(parent
);
543 ext
= node_to_extent(parent
);
544 if ((ext
->start
+ ext
->count
) <= start
)
547 /* No more extents to be removed/truncated */
548 if ((start
+ count
) < ext
->start
)
551 /* The entire extent is within the region to be removed */
552 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
553 ext2fs_rb_erase(parent
, root
);
554 rb_free_extent(bp
, ext
);
558 /* modify the last extent in region to be removed */
559 ext
->count
-= ((start
+ count
) - ext
->start
);
560 ext
->start
= start
+ count
;
569 static int rb_mark_bmap(ext2fs_generic_bitmap bitmap
, __u64 arg
)
571 struct ext2fs_rb_private
*bp
;
574 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
575 arg
-= bitmap
->start
;
577 retval
= rb_insert_extent(arg
, 1, bp
);
578 check_tree(&bp
->root
, __func__
);
582 static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap
, __u64 arg
)
584 struct ext2fs_rb_private
*bp
;
587 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
588 arg
-= bitmap
->start
;
590 retval
= rb_remove_extent(arg
, 1, bp
);
591 check_tree(&bp
->root
, __func__
);
597 static int rb_test_bmap(ext2fs_generic_bitmap bitmap
, __u64 arg
)
599 struct ext2fs_rb_private
*bp
;
601 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
602 arg
-= bitmap
->start
;
604 return rb_test_bit(bp
, arg
);
607 static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap
, __u64 arg
,
610 struct ext2fs_rb_private
*bp
;
612 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
613 arg
-= bitmap
->start
;
615 rb_insert_extent(arg
, num
, bp
);
616 check_tree(&bp
->root
, __func__
);
619 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap
, __u64 arg
,
622 struct ext2fs_rb_private
*bp
;
624 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
625 arg
-= bitmap
->start
;
627 rb_remove_extent(arg
, num
, bp
);
628 check_tree(&bp
->root
, __func__
);
631 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap
,
632 __u64 start
, unsigned int len
)
634 struct rb_node
*parent
= NULL
, **n
;
635 struct rb_node
*node
, *next
;
636 struct ext2fs_rb_private
*bp
;
637 struct bmap_rb_extent
*ext
;
640 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
641 n
= &bp
->root
.rb_node
;
642 start
-= bitmap
->start
;
644 if (len
== 0 || ext2fs_rb_empty_root(&bp
->root
))
648 * If we find nothing, we should examine whole extent, but
649 * when we find match, the extent is not clean, thus be return
654 ext
= node_to_extent(parent
);
655 if (start
< ext
->start
) {
657 } else if (start
>= (ext
->start
+ ext
->count
)) {
661 * We found extent int the tree -> extent is not
670 next
= ext2fs_rb_next(node
);
671 ext
= node_to_extent(node
);
674 if ((ext
->start
+ ext
->count
) <= start
)
677 /* No more merging */
678 if ((start
+ len
) <= ext
->start
)
687 static errcode_t
rb_set_bmap_range(ext2fs_generic_bitmap bitmap
,
688 __u64 start
, size_t num
, void *in
)
690 struct ext2fs_rb_private
*bp
;
691 unsigned char *cp
= in
;
695 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
697 for (i
= 0; i
< num
; i
++) {
699 unsigned char c
= cp
[i
/8];
706 if ((c
== 0x00) && (first_set
== -1)) {
711 if (ext2fs_test_bit(i
, in
)) {
719 rb_insert_extent(start
+ first_set
- bitmap
->start
,
721 check_tree(&bp
->root
, __func__
);
724 if (first_set
!= -1) {
725 rb_insert_extent(start
+ first_set
- bitmap
->start
,
726 num
- first_set
, bp
);
727 check_tree(&bp
->root
, __func__
);
733 static errcode_t
rb_get_bmap_range(ext2fs_generic_bitmap bitmap
,
734 __u64 start
, size_t num
, void *out
)
737 struct rb_node
*parent
= NULL
, *next
, **n
;
738 struct ext2fs_rb_private
*bp
;
739 struct bmap_rb_extent
*ext
;
742 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
743 n
= &bp
->root
.rb_node
;
744 start
-= bitmap
->start
;
746 if (ext2fs_rb_empty_root(&bp
->root
))
751 ext
= node_to_extent(parent
);
752 if (start
< ext
->start
) {
754 } else if (start
>= (ext
->start
+ ext
->count
)) {
760 memset(out
, 0, (num
+ 7) >> 3);
762 for (; parent
!= NULL
; parent
= next
) {
763 next
= ext2fs_rb_next(parent
);
764 ext
= node_to_extent(parent
);
768 if (pos
>= start
+ num
)
771 if (pos
+ count
< start
)
773 count
-= start
- pos
;
776 if (pos
+ count
> start
+ num
)
777 count
= start
+ num
- pos
;
781 ((pos
- start
) % 8) == 0) {
782 int nbytes
= count
>> 3;
783 int offset
= (pos
- start
) >> 3;
785 memset(((char *) out
) + offset
, 0xFF, nbytes
);
787 count
-= nbytes
<< 3;
790 ext2fs_fast_set_bit64((pos
- start
), out
);
798 static void rb_clear_bmap(ext2fs_generic_bitmap bitmap
)
800 struct ext2fs_rb_private
*bp
;
802 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
804 rb_free_tree(&bp
->root
);
806 bp
->rcursor_next
= NULL
;
808 check_tree(&bp
->root
, __func__
);
811 static errcode_t
rb_find_first_zero(ext2fs_generic_bitmap bitmap
,
812 __u64 start
, __u64 end
, __u64
*out
)
814 struct rb_node
*parent
= NULL
, **n
;
815 struct ext2fs_rb_private
*bp
;
816 struct bmap_rb_extent
*ext
;
818 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
819 n
= &bp
->root
.rb_node
;
820 start
-= bitmap
->start
;
821 end
-= bitmap
->start
;
826 if (ext2fs_rb_empty_root(&bp
->root
))
831 ext
= node_to_extent(parent
);
832 if (start
< ext
->start
) {
834 } else if (start
>= (ext
->start
+ ext
->count
)) {
836 } else if (ext
->start
+ ext
->count
<= end
) {
837 *out
= ext
->start
+ ext
->count
+ bitmap
->start
;
843 *out
= start
+ bitmap
->start
;
847 static errcode_t
rb_find_first_set(ext2fs_generic_bitmap bitmap
,
848 __u64 start
, __u64 end
, __u64
*out
)
850 struct rb_node
*parent
= NULL
, **n
;
851 struct rb_node
*node
;
852 struct ext2fs_rb_private
*bp
;
853 struct bmap_rb_extent
*ext
;
855 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
856 n
= &bp
->root
.rb_node
;
857 start
-= bitmap
->start
;
858 end
-= bitmap
->start
;
863 if (ext2fs_rb_empty_root(&bp
->root
))
868 ext
= node_to_extent(parent
);
869 if (start
< ext
->start
) {
871 } else if (start
>= (ext
->start
+ ext
->count
)) {
874 /* The start bit is set */
875 *out
= start
+ bitmap
->start
;
881 ext
= node_to_extent(node
);
882 if (ext
->start
< start
) {
883 node
= ext2fs_rb_next(node
);
886 ext
= node_to_extent(node
);
888 if (ext
->start
<= end
) {
889 *out
= ext
->start
+ bitmap
->start
;
895 #ifdef ENABLE_BMAP_STATS
896 static void rb_print_stats(ext2fs_generic_bitmap bitmap
)
898 struct ext2fs_rb_private
*bp
;
899 struct rb_node
*node
= NULL
;
900 struct bmap_rb_extent
*ext
;
903 __u64 min_size
= ULONG_MAX
;
904 __u64 size
= 0, avg_size
= 0;
906 #ifdef ENABLE_BMAP_STATS_OPS
907 __u64 mark_all
, test_all
;
908 double m_hit
= 0.0, t_hit
= 0.0;
911 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
913 for (node
= ext2fs_rb_first(&bp
->root
); node
!= NULL
;
914 node
= ext2fs_rb_next(node
)) {
915 ext
= node_to_extent(node
);
917 if (ext
->count
> max_size
)
918 max_size
= ext
->count
;
919 if (ext
->count
< min_size
)
920 min_size
= ext
->count
;
925 avg_size
= size
/ count
;
926 if (min_size
== ULONG_MAX
)
928 eff
= (double)((count
* sizeof(struct bmap_rb_extent
)) << 3) /
929 (bitmap
->real_end
- bitmap
->start
);
930 #ifdef ENABLE_BMAP_STATS_OPS
931 mark_all
= bitmap
->stats
.mark_count
+ bitmap
->stats
.mark_ext_count
;
932 test_all
= bitmap
->stats
.test_count
+ bitmap
->stats
.test_ext_count
;
934 m_hit
= ((double)bp
->mark_hit
/ mark_all
) * 100;
936 t_hit
= ((double)bp
->test_hit
/ test_all
) * 100;
938 fprintf(stderr
, "%16llu cache hits on test (%.2f%%)\n"
939 "%16llu cache hits on mark (%.2f%%)\n",
940 bp
->test_hit
, t_hit
, bp
->mark_hit
, m_hit
);
942 fprintf(stderr
, "%16llu extents (%llu bytes)\n",
943 count
, ((count
* sizeof(struct bmap_rb_extent
)) +
944 sizeof(struct ext2fs_rb_private
)));
945 fprintf(stderr
, "%16llu bits minimum size\n",
947 fprintf(stderr
, "%16llu bits maximum size\n"
948 "%16llu bits average size\n",
950 fprintf(stderr
, "%16llu bits set in bitmap (out of %llu)\n", size
,
951 bitmap
->real_end
- bitmap
->start
);
953 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
957 static void rb_print_stats(ext2fs_generic_bitmap bitmap
EXT2FS_ATTR((unused
)))
962 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree
= {
963 .type
= EXT2FS_BMAP64_RBTREE
,
964 .new_bmap
= rb_new_bmap
,
965 .free_bmap
= rb_free_bmap
,
966 .copy_bmap
= rb_copy_bmap
,
967 .resize_bmap
= rb_resize_bmap
,
968 .mark_bmap
= rb_mark_bmap
,
969 .unmark_bmap
= rb_unmark_bmap
,
970 .test_bmap
= rb_test_bmap
,
971 .test_clear_bmap_extent
= rb_test_clear_bmap_extent
,
972 .mark_bmap_extent
= rb_mark_bmap_extent
,
973 .unmark_bmap_extent
= rb_unmark_bmap_extent
,
974 .set_bmap_range
= rb_set_bmap_range
,
975 .get_bmap_range
= rb_get_bmap_range
,
976 .clear_bmap
= rb_clear_bmap
,
977 .print_stats
= rb_print_stats
,
978 .find_first_zero
= rb_find_first_zero
,
979 .find_first_set
= rb_find_first_set
,