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
,