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 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 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
;
572 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
573 arg
-= bitmap
->start
;
575 retval
= rb_insert_extent(arg
, 1, bp
);
576 check_tree(&bp
->root
, __func__
);
580 static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap
, __u64 arg
)
582 struct ext2fs_rb_private
*bp
;
585 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
586 arg
-= bitmap
->start
;
588 retval
= rb_remove_extent(arg
, 1, bp
);
589 check_tree(&bp
->root
, __func__
);
595 static int rb_test_bmap(ext2fs_generic_bitmap bitmap
, __u64 arg
)
597 struct ext2fs_rb_private
*bp
;
599 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
600 arg
-= bitmap
->start
;
602 return rb_test_bit(bp
, arg
);
605 static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap
, __u64 arg
,
608 struct ext2fs_rb_private
*bp
;
610 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
611 arg
-= bitmap
->start
;
613 rb_insert_extent(arg
, num
, bp
);
614 check_tree(&bp
->root
, __func__
);
617 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap
, __u64 arg
,
620 struct ext2fs_rb_private
*bp
;
622 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
623 arg
-= bitmap
->start
;
625 rb_remove_extent(arg
, num
, bp
);
626 check_tree(&bp
->root
, __func__
);
629 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap
,
630 __u64 start
, unsigned int len
)
632 struct rb_node
*parent
= NULL
, **n
;
633 struct rb_node
*node
, *next
;
634 struct ext2fs_rb_private
*bp
;
635 struct bmap_rb_extent
*ext
;
638 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
639 n
= &bp
->root
.rb_node
;
640 start
-= bitmap
->start
;
642 if ((len
== 0) || EXT2FS_RB_EMPTY_ROOT(&bp
->root
))
646 * If we find nothing, we should examine whole extent, but
647 * when we find match, the extent is not clean, thus be return
652 ext
= node_to_extent(parent
);
653 if (start
< ext
->start
) {
655 } else if (start
>= (ext
->start
+ ext
->count
)) {
659 * We found extent int the tree -> extent is not
668 next
= ext2fs_rb_next(node
);
669 ext
= node_to_extent(node
);
672 if ((ext
->start
+ ext
->count
) <= start
)
675 /* No more merging */
676 if ((start
+ len
) <= ext
->start
)
685 static errcode_t
rb_set_bmap_range(ext2fs_generic_bitmap bitmap
,
686 __u64 start
, size_t num
, void *in
)
688 struct ext2fs_rb_private
*bp
;
689 unsigned char *cp
= in
;
693 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
695 for (i
= 0; i
< num
; i
++) {
697 unsigned char c
= cp
[i
/8];
704 if ((c
== 0x00) && (first_set
== -1)) {
709 if (ext2fs_test_bit(i
, in
)) {
717 rb_insert_extent(start
+ first_set
- bitmap
->start
,
719 check_tree(&bp
->root
, __func__
);
722 if (first_set
!= -1) {
723 rb_insert_extent(start
+ first_set
- bitmap
->start
,
724 num
- first_set
, bp
);
725 check_tree(&bp
->root
, __func__
);
731 static errcode_t
rb_get_bmap_range(ext2fs_generic_bitmap bitmap
,
732 __u64 start
, size_t num
, void *out
)
735 struct rb_node
*parent
= NULL
, *next
, **n
;
736 struct ext2fs_rb_private
*bp
;
737 struct bmap_rb_extent
*ext
;
741 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
742 n
= &bp
->root
.rb_node
;
743 start
-= bitmap
->start
;
745 if (EXT2FS_RB_EMPTY_ROOT(&bp
->root
))
750 ext
= node_to_extent(parent
);
751 if (start
< ext
->start
) {
753 } else if (start
>= (ext
->start
+ ext
->count
)) {
759 memset(out
, 0, (num
+ 7) >> 3);
761 for (; parent
!= NULL
; parent
= next
) {
762 next
= ext2fs_rb_next(parent
);
763 ext
= node_to_extent(parent
);
767 if (pos
>= start
+ num
)
770 count
-= start
- pos
;
775 if (pos
+ count
> start
+ num
)
776 count
= start
+ num
- pos
;
780 ((pos
- start
) % 8) == 0) {
781 int nbytes
= count
>> 3;
782 int offset
= (pos
- start
) >> 3;
784 memset(((char *) out
) + offset
, 0xFF, nbytes
);
786 count
-= nbytes
<< 3;
789 ext2fs_fast_set_bit64((pos
- start
), out
);
797 static void rb_clear_bmap(ext2fs_generic_bitmap bitmap
)
799 struct ext2fs_rb_private
*bp
;
801 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
803 rb_free_tree(&bp
->root
);
805 bp
->rcursor_next
= NULL
;
807 check_tree(&bp
->root
, __func__
);
810 static errcode_t
rb_find_first_zero(ext2fs_generic_bitmap bitmap
,
811 __u64 start
, __u64 end
, __u64
*out
)
813 struct rb_node
*parent
= NULL
, **n
;
814 struct rb_node
*node
, *next
;
815 struct ext2fs_rb_private
*bp
;
816 struct bmap_rb_extent
*ext
;
819 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
820 n
= &bp
->root
.rb_node
;
821 start
-= bitmap
->start
;
822 end
-= bitmap
->start
;
827 if (EXT2FS_RB_EMPTY_ROOT(&bp
->root
))
832 ext
= node_to_extent(parent
);
833 if (start
< ext
->start
) {
835 } else if (start
>= (ext
->start
+ ext
->count
)) {
837 } else if (ext
->start
+ ext
->count
<= end
) {
838 *out
= ext
->start
+ ext
->count
+ bitmap
->start
;
844 *out
= start
+ bitmap
->start
;
848 static errcode_t
rb_find_first_set(ext2fs_generic_bitmap bitmap
,
849 __u64 start
, __u64 end
, __u64
*out
)
851 struct rb_node
*parent
= NULL
, **n
;
852 struct rb_node
*node
, *next
;
853 struct ext2fs_rb_private
*bp
;
854 struct bmap_rb_extent
*ext
;
857 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
858 n
= &bp
->root
.rb_node
;
859 start
-= bitmap
->start
;
860 end
-= bitmap
->start
;
865 if (EXT2FS_RB_EMPTY_ROOT(&bp
->root
))
870 ext
= node_to_extent(parent
);
871 if (start
< ext
->start
) {
873 } else if (start
>= (ext
->start
+ ext
->count
)) {
876 /* The start bit is set */
877 *out
= start
+ bitmap
->start
;
883 ext
= node_to_extent(node
);
884 if (ext
->start
< start
) {
885 node
= ext2fs_rb_next(node
);
888 ext
= node_to_extent(node
);
890 if (ext
->start
<= end
) {
891 *out
= ext
->start
+ bitmap
->start
;
897 #ifdef ENABLE_BMAP_STATS
898 static void rb_print_stats(ext2fs_generic_bitmap bitmap
)
900 struct ext2fs_rb_private
*bp
;
901 struct rb_node
*node
= NULL
;
902 struct bmap_rb_extent
*ext
;
905 __u64 min_size
= ULONG_MAX
;
906 __u64 size
= 0, avg_size
= 0;
908 #ifdef ENABLE_BMAP_STATS_OPS
909 __u64 mark_all
, test_all
;
910 double m_hit
= 0.0, t_hit
= 0.0;
913 bp
= (struct ext2fs_rb_private
*) bitmap
->private;
915 for (node
= ext2fs_rb_first(&bp
->root
); node
!= NULL
;
916 node
= ext2fs_rb_next(node
)) {
917 ext
= node_to_extent(node
);
919 if (ext
->count
> max_size
)
920 max_size
= ext
->count
;
921 if (ext
->count
< min_size
)
922 min_size
= ext
->count
;
927 avg_size
= size
/ count
;
928 if (min_size
== ULONG_MAX
)
930 eff
= (double)((count
* sizeof(struct bmap_rb_extent
)) << 3) /
931 (bitmap
->real_end
- bitmap
->start
);
932 #ifdef ENABLE_BMAP_STATS_OPS
933 mark_all
= bitmap
->stats
.mark_count
+ bitmap
->stats
.mark_ext_count
;
934 test_all
= bitmap
->stats
.test_count
+ bitmap
->stats
.test_ext_count
;
936 m_hit
= ((double)bp
->mark_hit
/ mark_all
) * 100;
938 t_hit
= ((double)bp
->test_hit
/ test_all
) * 100;
940 fprintf(stderr
, "%16llu cache hits on test (%.2f%%)\n"
941 "%16llu cache hits on mark (%.2f%%)\n",
942 bp
->test_hit
, t_hit
, bp
->mark_hit
, m_hit
);
944 fprintf(stderr
, "%16llu extents (%llu bytes)\n",
945 count
, ((count
* sizeof(struct bmap_rb_extent
)) +
946 sizeof(struct ext2fs_rb_private
)));
947 fprintf(stderr
, "%16llu bits minimum size\n",
949 fprintf(stderr
, "%16llu bits maximum size\n"
950 "%16llu bits average size\n",
952 fprintf(stderr
, "%16llu bits set in bitmap (out of %llu)\n", size
,
953 bitmap
->real_end
- bitmap
->start
);
955 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
959 static void rb_print_stats(ext2fs_generic_bitmap bitmap
EXT2FS_ATTR((unused
)))
964 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree
= {
965 .type
= EXT2FS_BMAP64_RBTREE
,
966 .new_bmap
= rb_new_bmap
,
967 .free_bmap
= rb_free_bmap
,
968 .copy_bmap
= rb_copy_bmap
,
969 .resize_bmap
= rb_resize_bmap
,
970 .mark_bmap
= rb_mark_bmap
,
971 .unmark_bmap
= rb_unmark_bmap
,
972 .test_bmap
= rb_test_bmap
,
973 .test_clear_bmap_extent
= rb_test_clear_bmap_extent
,
974 .mark_bmap_extent
= rb_mark_bmap_extent
,
975 .unmark_bmap_extent
= rb_unmark_bmap_extent
,
976 .set_bmap_range
= rb_set_bmap_range
,
977 .get_bmap_range
= rb_get_bmap_range
,
978 .clear_bmap
= rb_clear_bmap
,
979 .print_stats
= rb_print_stats
,
980 .find_first_zero
= rb_find_first_zero
,
981 .find_first_set
= rb_find_first_set
,