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 fprintf(stderr
, "\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 fprintf(stderr
, "\t\t\t--> (%llu -> %llu)\n",
83 ext
->start
, ext
->start
+ ext
->count
);
85 fprintf(stderr
, "\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 fprintf(stderr
, "Tree Error: count is zero\n");
98 fprintf(stderr
, "extent: %llu -> %llu (%llu)\n",
99 ext
->start
, ext
->start
+ ext
->count
,
103 if (ext
->start
+ ext
->count
< ext
->start
) {
105 "Tree Error: start or count is crazy\n");
106 fprintf(stderr
, "extent: %llu -> %llu (%llu)\n",
107 ext
->start
, ext
->start
+ ext
->count
,
113 if (old
->start
> ext
->start
) {
114 fprintf(stderr
, "Tree Error: start is crazy\n");
115 fprintf(stderr
, "extent: %llu -> %llu (%llu)\n",
116 old
->start
, old
->start
+ old
->count
,
119 "extent next: %llu -> %llu (%llu)\n",
120 ext
->start
, ext
->start
+ ext
->count
,
124 if ((old
->start
+ old
->count
) >= ext
->start
) {
126 "Tree Error: extent is crazy\n");
127 fprintf(stderr
, "extent: %llu -> %llu (%llu)\n",
128 old
->start
, old
->start
+ old
->count
,
131 "extent next: %llu -> %llu (%llu)\n",
132 ext
->start
, ext
->start
+ ext
->count
,
142 fprintf(stderr
, "%s\n", msg
);
147 #define check_tree(root, msg) do {} while (0)
148 #define print_tree(root) do {} while (0)
151 static void rb_get_new_extent(struct bmap_rb_extent
**ext
, __u64 start
,
154 struct bmap_rb_extent
*new_ext
;
157 retval
= ext2fs_get_mem(sizeof (struct bmap_rb_extent
),
162 new_ext
->start
= start
;
163 new_ext
->count
= count
;
168 static void rb_free_extent(struct ext2fs_rb_private
*bp
,
169 struct bmap_rb_extent
*ext
)
171 if (bp
->wcursor
== ext
)
173 if (bp
->rcursor
== ext
)
175 if (bp
->rcursor_next
== ext
)
176 bp
->rcursor_next
= NULL
;
177 ext2fs_free_mem(&ext
);
180 static errcode_t
rb_alloc_private_data (ext2fs_generic_bitmap_64 bitmap
)
182 struct ext2fs_rb_private
*bp
;
185 retval
= ext2fs_get_mem(sizeof (struct ext2fs_rb_private
), &bp
);
191 bp
->rcursor_next
= NULL
;
194 #ifdef ENABLE_BMAP_STATS_OPS
199 bitmap
->private = (void *) bp
;
203 static errcode_t
rb_new_bmap(ext2_filsys fs
EXT2FS_ATTR((unused
)),
204 ext2fs_generic_bitmap_64 bitmap
)
208 retval
= rb_alloc_private_data (bitmap
);
215 static void rb_free_tree(struct rb_root
*root
)
217 struct bmap_rb_extent
*ext
;
218 struct rb_node
*node
, *next
;
220 for (node
= ext2fs_rb_first(root
); node
; node
= next
) {
221 next
= ext2fs_rb_next(node
);
222 ext
= node_to_extent(node
);
223 ext2fs_rb_erase(node
, root
);
224 ext2fs_free_mem(&ext
);
228 static void rb_free_bmap(ext2fs_generic_bitmap_64 bitmap
)
230 struct ext2fs_rb_private
*bp
;
232 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
234 rb_free_tree(&bp
->root
);
235 ext2fs_free_mem(&bp
);
239 static errcode_t
rb_copy_bmap(ext2fs_generic_bitmap_64 src
,
240 ext2fs_generic_bitmap_64 dest
)
242 struct ext2fs_rb_private
*src_bp
, *dest_bp
;
243 struct bmap_rb_extent
*src_ext
, *dest_ext
;
244 struct rb_node
*dest_node
, *src_node
, *dest_last
, **n
;
245 errcode_t retval
= 0;
247 retval
= rb_alloc_private_data (dest
);
251 src_bp
= (struct ext2fs_rb_private
*) src
->private;
252 dest_bp
= (struct ext2fs_rb_private
*) dest
->private;
253 src_bp
->rcursor
= NULL
;
254 dest_bp
->rcursor
= NULL
;
256 src_node
= ext2fs_rb_first(&src_bp
->root
);
258 src_ext
= node_to_extent(src_node
);
259 retval
= ext2fs_get_mem(sizeof (struct bmap_rb_extent
),
264 memcpy(dest_ext
, src_ext
, sizeof(struct bmap_rb_extent
));
266 dest_node
= &dest_ext
->node
;
267 n
= &dest_bp
->root
.rb_node
;
271 dest_last
= ext2fs_rb_last(&dest_bp
->root
);
272 n
= &(dest_last
)->rb_right
;
275 ext2fs_rb_link_node(dest_node
, dest_last
, n
);
276 ext2fs_rb_insert_color(dest_node
, &dest_bp
->root
);
278 src_node
= ext2fs_rb_next(src_node
);
284 static void rb_truncate(__u64 new_max
, struct rb_root
*root
)
286 struct bmap_rb_extent
*ext
;
287 struct rb_node
*node
;
289 node
= ext2fs_rb_last(root
);
291 ext
= node_to_extent(node
);
293 if ((ext
->start
+ ext
->count
- 1) <= new_max
)
295 else if (ext
->start
> new_max
) {
296 ext2fs_rb_erase(node
, root
);
297 ext2fs_free_mem(&ext
);
298 node
= ext2fs_rb_last(root
);
301 ext
->count
= new_max
- ext
->start
+ 1;
305 static errcode_t
rb_resize_bmap(ext2fs_generic_bitmap_64 bmap
,
306 __u64 new_end
, __u64 new_real_end
)
308 struct ext2fs_rb_private
*bp
;
310 bp
= (struct ext2fs_rb_private
*) bmap
->private;
314 rb_truncate(((new_end
< bmap
->end
) ? new_end
: bmap
->end
) - bmap
->start
,
318 bmap
->real_end
= new_real_end
;
320 if (bmap
->end
< bmap
->real_end
)
321 rb_insert_extent(bmap
->end
+ 1 - bmap
->start
,
322 bmap
->real_end
- bmap
->end
, bp
);
328 rb_test_bit(struct ext2fs_rb_private
*bp
, __u64 bit
)
330 struct bmap_rb_extent
*rcursor
, *next_ext
= NULL
;
331 struct rb_node
*parent
= NULL
, *next
;
332 struct rb_node
**n
= &bp
->root
.rb_node
;
333 struct bmap_rb_extent
*ext
;
335 rcursor
= bp
->rcursor
;
339 if (bit
>= rcursor
->start
&& bit
< rcursor
->start
+ rcursor
->count
) {
340 #ifdef ENABLE_BMAP_STATS_OPS
346 next_ext
= bp
->rcursor_next
;
348 next
= ext2fs_rb_next(&rcursor
->node
);
350 next_ext
= node_to_extent(next
);
351 bp
->rcursor_next
= next_ext
;
354 if ((bit
>= rcursor
->start
+ rcursor
->count
) &&
355 (bit
< next_ext
->start
)) {
356 #ifdef BMAP_STATS_OPS
363 bp
->rcursor_next
= NULL
;
365 rcursor
= bp
->wcursor
;
369 if (bit
>= rcursor
->start
&& bit
< rcursor
->start
+ rcursor
->count
)
376 ext
= node_to_extent(parent
);
377 if (bit
< ext
->start
)
379 else if (bit
>= (ext
->start
+ ext
->count
))
383 bp
->rcursor_next
= NULL
;
390 static int rb_insert_extent(__u64 start
, __u64 count
,
391 struct ext2fs_rb_private
*bp
)
393 struct rb_root
*root
= &bp
->root
;
394 struct rb_node
*parent
= NULL
, **n
= &root
->rb_node
;
395 struct rb_node
*new_node
, *node
, *next
;
396 struct bmap_rb_extent
*new_ext
;
397 struct bmap_rb_extent
*ext
;
403 bp
->rcursor_next
= NULL
;
406 if (start
>= ext
->start
&&
407 start
<= (ext
->start
+ ext
->count
)) {
408 #ifdef ENABLE_BMAP_STATS_OPS
417 ext
= node_to_extent(parent
);
419 if (start
< ext
->start
) {
421 } else if (start
> (ext
->start
+ ext
->count
)) {
425 if ((start
+ count
) <= (ext
->start
+ ext
->count
))
428 if ((ext
->start
+ ext
->count
) == start
)
433 count
+= (start
- ext
->start
);
436 new_node
= &ext
->node
;
442 rb_get_new_extent(&new_ext
, start
, count
);
444 new_node
= &new_ext
->node
;
445 ext2fs_rb_link_node(new_node
, parent
, n
);
446 ext2fs_rb_insert_color(new_node
, root
);
447 bp
->wcursor
= new_ext
;
449 node
= ext2fs_rb_prev(new_node
);
451 ext
= node_to_extent(node
);
452 if ((ext
->start
+ ext
->count
) == start
) {
455 ext2fs_rb_erase(node
, root
);
456 rb_free_extent(bp
, ext
);
461 /* See if we can merge extent to the right */
462 for (node
= ext2fs_rb_next(new_node
); node
!= NULL
; node
= next
) {
463 next
= ext2fs_rb_next(node
);
464 ext
= node_to_extent(node
);
466 if ((ext
->start
+ ext
->count
) <= start
)
469 /* No more merging */
470 if ((start
+ count
) < ext
->start
)
473 /* ext is embedded in new_ext interval */
474 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
475 ext2fs_rb_erase(node
, root
);
476 rb_free_extent(bp
, ext
);
479 /* merge ext with new_ext */
480 count
+= ((ext
->start
+ ext
->count
) -
482 ext2fs_rb_erase(node
, root
);
483 rb_free_extent(bp
, ext
);
488 new_ext
->start
= start
;
489 new_ext
->count
= count
;
494 static int rb_remove_extent(__u64 start
, __u64 count
,
495 struct ext2fs_rb_private
*bp
)
497 struct rb_root
*root
= &bp
->root
;
498 struct rb_node
*parent
= NULL
, **n
= &root
->rb_node
;
499 struct rb_node
*node
;
500 struct bmap_rb_extent
*ext
;
501 __u64 new_start
, new_count
;
504 if (ext2fs_rb_empty_root(root
))
509 ext
= node_to_extent(parent
);
510 if (start
< ext
->start
) {
513 } else if (start
>= (ext
->start
+ ext
->count
)) {
518 if ((start
> ext
->start
) &&
519 (start
+ count
) < (ext
->start
+ ext
->count
)) {
520 /* We have to split extent into two */
521 new_start
= start
+ count
;
522 new_count
= (ext
->start
+ ext
->count
) - new_start
;
524 ext
->count
= start
- ext
->start
;
526 rb_insert_extent(new_start
, new_count
, bp
);
530 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
531 ext
->count
= start
- ext
->start
;
535 if (0 == ext
->count
) {
536 parent
= ext2fs_rb_next(&ext
->node
);
537 ext2fs_rb_erase(&ext
->node
, root
);
538 rb_free_extent(bp
, ext
);
542 if (start
== ext
->start
) {
549 /* See if we should delete or truncate extent on the right */
550 for (; parent
!= NULL
; parent
= node
) {
551 node
= ext2fs_rb_next(parent
);
552 ext
= node_to_extent(parent
);
553 if ((ext
->start
+ ext
->count
) <= start
)
556 /* No more extents to be removed/truncated */
557 if ((start
+ count
) < ext
->start
)
560 /* The entire extent is within the region to be removed */
561 if ((start
+ count
) >= (ext
->start
+ ext
->count
)) {
562 ext2fs_rb_erase(parent
, root
);
563 rb_free_extent(bp
, ext
);
567 /* modify the last extent in region to be removed */
568 ext
->count
-= ((start
+ count
) - ext
->start
);
569 ext
->start
= start
+ count
;
578 static int rb_mark_bmap(ext2fs_generic_bitmap_64 bitmap
, __u64 arg
)
580 struct ext2fs_rb_private
*bp
;
583 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
584 arg
-= bitmap
->start
;
586 retval
= rb_insert_extent(arg
, 1, bp
);
587 check_tree(&bp
->root
, __func__
);
591 static int rb_unmark_bmap(ext2fs_generic_bitmap_64 bitmap
, __u64 arg
)
593 struct ext2fs_rb_private
*bp
;
596 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
597 arg
-= bitmap
->start
;
599 retval
= rb_remove_extent(arg
, 1, bp
);
600 check_tree(&bp
->root
, __func__
);
606 static int rb_test_bmap(ext2fs_generic_bitmap_64 bitmap
, __u64 arg
)
608 struct ext2fs_rb_private
*bp
;
610 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
611 arg
-= bitmap
->start
;
613 return rb_test_bit(bp
, arg
);
616 static void rb_mark_bmap_extent(ext2fs_generic_bitmap_64 bitmap
, __u64 arg
,
619 struct ext2fs_rb_private
*bp
;
621 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
622 arg
-= bitmap
->start
;
624 rb_insert_extent(arg
, num
, bp
);
625 check_tree(&bp
->root
, __func__
);
628 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap_64 bitmap
, __u64 arg
,
631 struct ext2fs_rb_private
*bp
;
633 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
634 arg
-= bitmap
->start
;
636 rb_remove_extent(arg
, num
, bp
);
637 check_tree(&bp
->root
, __func__
);
640 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap_64 bitmap
,
641 __u64 start
, unsigned int len
)
643 struct rb_node
*parent
= NULL
, **n
;
644 struct rb_node
*node
, *next
;
645 struct ext2fs_rb_private
*bp
;
646 struct bmap_rb_extent
*ext
;
649 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
650 n
= &bp
->root
.rb_node
;
651 start
-= bitmap
->start
;
653 if (len
== 0 || ext2fs_rb_empty_root(&bp
->root
))
657 * If we find nothing, we should examine whole extent, but
658 * when we find match, the extent is not clean, thus be return
663 ext
= node_to_extent(parent
);
664 if (start
< ext
->start
) {
666 } else if (start
>= (ext
->start
+ ext
->count
)) {
670 * We found extent int the tree -> extent is not
679 next
= ext2fs_rb_next(node
);
680 ext
= node_to_extent(node
);
683 if ((ext
->start
+ ext
->count
) <= start
)
686 /* No more merging */
687 if ((start
+ len
) <= ext
->start
)
696 static errcode_t
rb_set_bmap_range(ext2fs_generic_bitmap_64 bitmap
,
697 __u64 start
, size_t num
, void *in
)
699 struct ext2fs_rb_private
*bp
;
700 unsigned char *cp
= in
;
704 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
706 for (i
= 0; i
< num
; i
++) {
708 unsigned char c
= cp
[i
/8];
715 if ((c
== 0x00) && (first_set
== -1)) {
720 if (ext2fs_test_bit(i
, in
)) {
728 rb_insert_extent(start
+ first_set
- bitmap
->start
,
730 check_tree(&bp
->root
, __func__
);
733 if (first_set
!= -1) {
734 rb_insert_extent(start
+ first_set
- bitmap
->start
,
735 num
- first_set
, bp
);
736 check_tree(&bp
->root
, __func__
);
742 static errcode_t
rb_get_bmap_range(ext2fs_generic_bitmap_64 bitmap
,
743 __u64 start
, size_t num
, void *out
)
746 struct rb_node
*parent
= NULL
, *next
, **n
;
747 struct ext2fs_rb_private
*bp
;
748 struct bmap_rb_extent
*ext
;
751 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
752 n
= &bp
->root
.rb_node
;
753 start
-= bitmap
->start
;
755 if (ext2fs_rb_empty_root(&bp
->root
))
760 ext
= node_to_extent(parent
);
761 if (start
< ext
->start
) {
763 } else if (start
>= (ext
->start
+ ext
->count
)) {
769 memset(out
, 0, (num
+ 7) >> 3);
771 for (; parent
!= NULL
; parent
= next
) {
772 next
= ext2fs_rb_next(parent
);
773 ext
= node_to_extent(parent
);
777 if (pos
>= start
+ num
)
780 if (pos
+ count
< start
)
782 count
-= start
- pos
;
785 if (pos
+ count
> start
+ num
)
786 count
= start
+ num
- pos
;
790 ((pos
- start
) % 8) == 0) {
791 int nbytes
= count
>> 3;
792 int offset
= (pos
- start
) >> 3;
794 memset(((char *) out
) + offset
, 0xFF, nbytes
);
796 count
-= nbytes
<< 3;
799 ext2fs_fast_set_bit64((pos
- start
), out
);
807 static void rb_clear_bmap(ext2fs_generic_bitmap_64 bitmap
)
809 struct ext2fs_rb_private
*bp
;
811 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
813 rb_free_tree(&bp
->root
);
815 bp
->rcursor_next
= NULL
;
817 check_tree(&bp
->root
, __func__
);
820 static errcode_t
rb_find_first_zero(ext2fs_generic_bitmap_64 bitmap
,
821 __u64 start
, __u64 end
, __u64
*out
)
823 struct rb_node
*parent
= NULL
, **n
;
824 struct ext2fs_rb_private
*bp
;
825 struct bmap_rb_extent
*ext
;
827 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
828 n
= &bp
->root
.rb_node
;
829 start
-= bitmap
->start
;
830 end
-= bitmap
->start
;
835 if (ext2fs_rb_empty_root(&bp
->root
))
840 ext
= node_to_extent(parent
);
841 if (start
< ext
->start
) {
843 } else if (start
>= (ext
->start
+ ext
->count
)) {
845 } else if (ext
->start
+ ext
->count
<= end
) {
846 *out
= ext
->start
+ ext
->count
+ bitmap
->start
;
852 *out
= start
+ bitmap
->start
;
856 static errcode_t
rb_find_first_set(ext2fs_generic_bitmap_64 bitmap
,
857 __u64 start
, __u64 end
, __u64
*out
)
859 struct rb_node
*parent
= NULL
, **n
;
860 struct rb_node
*node
;
861 struct ext2fs_rb_private
*bp
;
862 struct bmap_rb_extent
*ext
;
864 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
865 n
= &bp
->root
.rb_node
;
866 start
-= bitmap
->start
;
867 end
-= bitmap
->start
;
872 if (ext2fs_rb_empty_root(&bp
->root
))
877 ext
= node_to_extent(parent
);
878 if (start
< ext
->start
) {
880 } else if (start
>= (ext
->start
+ ext
->count
)) {
883 /* The start bit is set */
884 *out
= start
+ bitmap
->start
;
890 ext
= node_to_extent(node
);
891 if (ext
->start
< start
) {
892 node
= ext2fs_rb_next(node
);
895 ext
= node_to_extent(node
);
897 if (ext
->start
<= end
) {
898 *out
= ext
->start
+ bitmap
->start
;
904 #ifdef ENABLE_BMAP_STATS
905 static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap
)
907 struct ext2fs_rb_private
*bp
;
908 struct rb_node
*node
= NULL
;
909 struct bmap_rb_extent
*ext
;
912 __u64 min_size
= ULONG_MAX
;
913 __u64 size
= 0, avg_size
= 0;
915 #ifdef ENABLE_BMAP_STATS_OPS
916 __u64 mark_all
, test_all
;
917 double m_hit
= 0.0, t_hit
= 0.0;
920 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
922 for (node
= ext2fs_rb_first(&bp
->root
); node
!= NULL
;
923 node
= ext2fs_rb_next(node
)) {
924 ext
= node_to_extent(node
);
926 if (ext
->count
> max_size
)
927 max_size
= ext
->count
;
928 if (ext
->count
< min_size
)
929 min_size
= ext
->count
;
934 avg_size
= size
/ count
;
935 if (min_size
== ULONG_MAX
)
937 eff
= (double)((count
* sizeof(struct bmap_rb_extent
)) << 3) /
938 (bitmap
->real_end
- bitmap
->start
);
939 #ifdef ENABLE_BMAP_STATS_OPS
940 mark_all
= bitmap
->stats
.mark_count
+ bitmap
->stats
.mark_ext_count
;
941 test_all
= bitmap
->stats
.test_count
+ bitmap
->stats
.test_ext_count
;
943 m_hit
= ((double)bp
->mark_hit
/ mark_all
) * 100;
945 t_hit
= ((double)bp
->test_hit
/ test_all
) * 100;
947 fprintf(stderr
, "%16llu cache hits on test (%.2f%%)\n"
948 "%16llu cache hits on mark (%.2f%%)\n",
949 bp
->test_hit
, t_hit
, bp
->mark_hit
, m_hit
);
951 fprintf(stderr
, "%16llu extents (%llu bytes)\n",
952 count
, ((count
* sizeof(struct bmap_rb_extent
)) +
953 sizeof(struct ext2fs_rb_private
)));
954 fprintf(stderr
, "%16llu bits minimum size\n",
956 fprintf(stderr
, "%16llu bits maximum size\n"
957 "%16llu bits average size\n",
959 fprintf(stderr
, "%16llu bits set in bitmap (out of %llu)\n", size
,
960 bitmap
->real_end
- bitmap
->start
);
962 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
966 static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap
EXT2FS_ATTR((unused
)))
971 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree
= {
972 .type
= EXT2FS_BMAP64_RBTREE
,
973 .new_bmap
= rb_new_bmap
,
974 .free_bmap
= rb_free_bmap
,
975 .copy_bmap
= rb_copy_bmap
,
976 .resize_bmap
= rb_resize_bmap
,
977 .mark_bmap
= rb_mark_bmap
,
978 .unmark_bmap
= rb_unmark_bmap
,
979 .test_bmap
= rb_test_bmap
,
980 .test_clear_bmap_extent
= rb_test_clear_bmap_extent
,
981 .mark_bmap_extent
= rb_mark_bmap_extent
,
982 .unmark_bmap_extent
= rb_unmark_bmap_extent
,
983 .set_bmap_range
= rb_set_bmap_range
,
984 .get_bmap_range
= rb_get_bmap_range
,
985 .clear_bmap
= rb_clear_bmap
,
986 .print_stats
= rb_print_stats
,
987 .find_first_zero
= rb_find_first_zero
,
988 .find_first_set
= rb_find_first_set
,