1 /*
2 * blkmap64_rb.c --- Simple rb-tree implementation for bitmaps
3 *
4 * (C)2010 Red Hat, Inc., Lukas Czerner <lczerner@redhat.com>
5 *
6 * %Begin-Header%
7 * This file may be redistributed under the terms of the GNU Public
8 * License.
9 * %End-Header%
10 */
11
12 #include <stdio.h>
13 #include <string.h>
14 #if HAVE_UNISTD_H
15 #include <unistd.h>
16 #endif
17 #include <fcntl.h>
18 #include <time.h>
19 #if HAVE_SYS_STAT_H
20 #include <sys/stat.h>
21 #endif
22 #if HAVE_SYS_TYPES_H
23 #include <sys/types.h>
24 #endif
25
26 #include "ext2_fs.h"
27 #include "ext2fsP.h"
28 #include "bmap64.h"
29 #include "rbtree.h"
30
31 #include <limits.h>
32
33 struct bmap_rb_extent {
34 struct rb_node node;
35 __u64 start;
36 __u64 count;
37 };
38
39 struct ext2fs_rb_private {
40 struct rb_root root;
41 struct bmap_rb_extent *wcursor;
42 struct bmap_rb_extent *rcursor;
43 struct bmap_rb_extent *rcursor_next;
44 #ifdef BMAP_STATS_OPS
45 __u64 mark_hit;
46 __u64 test_hit;
47 #endif
48 };
49
node_to_extent(struct rb_node * node)50 inline static struct bmap_rb_extent *node_to_extent(struct rb_node *node)
51 {
52 /*
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.
57 */
58 return (struct bmap_rb_extent *) node;
59 }
60
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);
64
65 /* #define DEBUG_RB */
66
67 #ifdef DEBUG_RB
print_tree(struct rb_root * root)68 static void print_tree(struct rb_root *root)
69 {
70 struct rb_node *node = NULL;
71 struct bmap_rb_extent *ext;
72
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);
80 }
81 printf("\t\t\t=================================\n");
82 }
83
check_tree(struct rb_root * root,const char * msg)84 static void check_tree(struct rb_root *root, const char *msg)
85 {
86 struct rb_node *new_node, *node, *next;
87 struct bmap_rb_extent *ext, *old = NULL;
88
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);
96 goto err_out;
97 }
98 if (ext->start < 0) {
99 printf("Tree Error: start is crazy\n");
100 printf("extent: %llu -> %llu (%u)\n", ext->start,
101 ext->start + ext->count, ext->count);
102 goto err_out;
103 }
104
105 if (old) {
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,
110 old->count);
111 printf("extent next: %llu -> %llu (%u)\n",
112 ext->start, ext->start + ext->count,
113 ext->count);
114 goto err_out;
115 }
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,
120 old->count);
121 printf("extent next: %llu -> %llu (%u)\n",
122 ext->start, ext->start + ext->count,
123 ext->count);
124 goto err_out;
125 }
126 }
127 old = ext;
128 }
129 return;
130
131 err_out:
132 printf("%s\n", msg);
133 print_tree(root);
134 exit(1);
135 }
136 #else
137 #define check_tree(root, msg) do {} while (0)
138 #define print_tree(root, msg) do {} while (0)
139 #endif
140
rb_get_new_extent(struct bmap_rb_extent ** ext,__u64 start,__u64 count)141 static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start,
142 __u64 count)
143 {
144 struct bmap_rb_extent *new_ext;
145 int retval;
146
147 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
148 &new_ext);
149 if (retval) {
150 perror("ext2fs_get_mem");
151 exit(1);
152 }
153
154 new_ext->start = start;
155 new_ext->count = count;
156 *ext = new_ext;
157 }
158
159 inline
rb_free_extent(struct ext2fs_rb_private * bp,struct bmap_rb_extent * ext)160 static void rb_free_extent(struct ext2fs_rb_private *bp,
161 struct bmap_rb_extent *ext)
162 {
163 if (bp->wcursor == ext)
164 bp->wcursor = NULL;
165 if (bp->rcursor == ext)
166 bp->rcursor = NULL;
167 if (bp->rcursor_next == ext)
168 bp->rcursor_next = NULL;
169 ext2fs_free_mem(&ext);
170 }
171
rb_alloc_private_data(ext2fs_generic_bitmap bitmap)172 static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
173 {
174 struct ext2fs_rb_private *bp;
175 errcode_t retval;
176
177 retval = ext2fs_get_mem(sizeof (struct ext2fs_rb_private), &bp);
178 if (retval)
179 return retval;
180
181 bp->root = RB_ROOT;
182 bp->rcursor = NULL;
183 bp->rcursor_next = NULL;
184 bp->wcursor = NULL;
185
186 #ifdef BMAP_STATS_OPS
187 bp->test_hit = 0;
188 bp->mark_hit = 0;
189 #endif
190
191 bitmap->private = (void *) bp;
192 return 0;
193 }
194
rb_new_bmap(ext2_filsys fs EXT2FS_ATTR ((unused)),ext2fs_generic_bitmap bitmap)195 static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
196 ext2fs_generic_bitmap bitmap)
197 {
198 errcode_t retval;
199
200 retval = rb_alloc_private_data (bitmap);
201 if (retval)
202 return retval;
203
204 return 0;
205 }
206
rb_free_tree(struct rb_root * root)207 static void rb_free_tree(struct rb_root *root)
208 {
209 struct bmap_rb_extent *ext;
210 struct rb_node *node, *next;
211
212 for (node = ext2fs_rb_first(root); node; node = next) {
213 next = ext2fs_rb_next(node);
214 ext = node_to_extent(node);
215 ext2fs_rb_erase(node, root);
216 ext2fs_free_mem(&ext);
217 }
218 }
219
rb_free_bmap(ext2fs_generic_bitmap bitmap)220 static void rb_free_bmap(ext2fs_generic_bitmap bitmap)
221 {
222 struct ext2fs_rb_private *bp;
223
224 bp = (struct ext2fs_rb_private *) bitmap->private;
225
226 rb_free_tree(&bp->root);
227 ext2fs_free_mem(&bp);
228 bp = 0;
229 }
230
rb_copy_bmap(ext2fs_generic_bitmap src,ext2fs_generic_bitmap dest)231 static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src,
232 ext2fs_generic_bitmap dest)
233 {
234 struct ext2fs_rb_private *src_bp, *dest_bp;
235 struct bmap_rb_extent *src_ext, *dest_ext;
236 struct rb_node *dest_node, *src_node, *dest_last, **n;
237 errcode_t retval = 0;
238
239 retval = rb_alloc_private_data (dest);
240 if (retval)
241 return retval;
242
243 src_bp = (struct ext2fs_rb_private *) src->private;
244 dest_bp = (struct ext2fs_rb_private *) dest->private;
245 src_bp->rcursor = NULL;
246 dest_bp->rcursor = NULL;
247
248 src_node = ext2fs_rb_first(&src_bp->root);
249 while (src_node) {
250 src_ext = node_to_extent(src_node);
251 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
252 &dest_ext);
253 if (retval)
254 break;
255
256 memcpy(dest_ext, src_ext, sizeof(struct bmap_rb_extent));
257
258 dest_node = &dest_ext->node;
259 n = &dest_bp->root.rb_node;
260
261 dest_last = NULL;
262 if (*n) {
263 dest_last = ext2fs_rb_last(&dest_bp->root);
264 n = &(dest_last)->rb_right;
265 }
266
267 ext2fs_rb_link_node(dest_node, dest_last, n);
268 ext2fs_rb_insert_color(dest_node, &dest_bp->root);
269
270 src_node = ext2fs_rb_next(src_node);
271 }
272
273 return retval;
274 }
275
rb_truncate(__u64 new_max,struct rb_root * root)276 static void rb_truncate(__u64 new_max, struct rb_root *root)
277 {
278 struct bmap_rb_extent *ext;
279 struct rb_node *node;
280
281 node = ext2fs_rb_last(root);
282 while (node) {
283 ext = node_to_extent(node);
284
285 if ((ext->start + ext->count - 1) <= new_max)
286 break;
287 else if (ext->start > new_max) {
288 ext2fs_rb_erase(node, root);
289 ext2fs_free_mem(&ext);
290 node = ext2fs_rb_last(root);
291 continue;
292 } else
293 ext->count = new_max - ext->start + 1;
294 }
295 }
296
rb_resize_bmap(ext2fs_generic_bitmap bmap,__u64 new_end,__u64 new_real_end)297 static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
298 __u64 new_end, __u64 new_real_end)
299 {
300 struct ext2fs_rb_private *bp;
301
302 if (new_real_end >= bmap->real_end) {
303 bmap->end = new_end;
304 bmap->real_end = new_real_end;
305 return 0;
306 }
307
308 bp = (struct ext2fs_rb_private *) bmap->private;
309 bp->rcursor = NULL;
310 bp->wcursor = NULL;
311
312 /* truncate tree to new_real_end size */
313 rb_truncate(new_real_end, &bp->root);
314
315 bmap->end = new_end;
316 bmap->real_end = new_real_end;
317 return 0;
318
319 }
320
321 inline static int
rb_test_bit(struct ext2fs_rb_private * bp,__u64 bit)322 rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
323 {
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;
328
329 rcursor = bp->rcursor;
330 if (!rcursor)
331 goto search_tree;
332
333 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) {
334 #ifdef BMAP_STATS_OPS
335 bp->test_hit++;
336 #endif
337 return 1;
338 }
339
340 next_ext = bp->rcursor_next;
341 if (!next_ext) {
342 next = ext2fs_rb_next(&rcursor->node);
343 if (next)
344 next_ext = node_to_extent(next);
345 bp->rcursor_next = next_ext;
346 }
347 if (next_ext) {
348 if ((bit >= rcursor->start + rcursor->count) &&
349 (bit < next_ext->start)) {
350 #ifdef BMAP_STATS_OPS
351 bp->test_hit++;
352 #endif
353 return 0;
354 }
355 }
356 bp->rcursor = NULL;
357 bp->rcursor_next = NULL;
358
359 rcursor = bp->wcursor;
360 if (!rcursor)
361 goto search_tree;
362
363 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
364 return 1;
365
366 search_tree:
367
368 while (*n) {
369 parent = *n;
370 ext = node_to_extent(parent);
371 if (bit < ext->start)
372 n = &(*n)->rb_left;
373 else if (bit >= (ext->start + ext->count))
374 n = &(*n)->rb_right;
375 else {
376 bp->rcursor = ext;
377 bp->rcursor_next = NULL;
378 return 1;
379 }
380 }
381 return 0;
382 }
383
rb_insert_extent(__u64 start,__u64 count,struct ext2fs_rb_private * bp)384 static int rb_insert_extent(__u64 start, __u64 count,
385 struct ext2fs_rb_private *bp)
386 {
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;
392 int retval = 0;
393
394 bp->rcursor_next = NULL;
395 ext = bp->wcursor;
396 if (ext) {
397 if (start >= ext->start &&
398 start <= (ext->start + ext->count)) {
399 #ifdef BMAP_STATS_OPS
400 bp->mark_hit++;
401 #endif
402 goto got_extent;
403 }
404 }
405
406 while (*n) {
407 parent = *n;
408 ext = node_to_extent(parent);
409
410 if (start < ext->start) {
411 n = &(*n)->rb_left;
412 } else if (start > (ext->start + ext->count)) {
413 n = &(*n)->rb_right;
414 } else {
415 got_extent:
416 if ((start + count) <= (ext->start + ext->count))
417 return 1;
418
419 if ((ext->start + ext->count) == start)
420 retval = 0;
421 else
422 retval = 1;
423
424 count += (start - ext->start);
425 start = ext->start;
426 new_ext = ext;
427 new_node = &ext->node;
428
429 goto skip_insert;
430 }
431 }
432
433 rb_get_new_extent(&new_ext, start, count);
434
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;
439
440 node = ext2fs_rb_prev(new_node);
441 if (node) {
442 ext = node_to_extent(node);
443 if ((ext->start + ext->count) == start) {
444 start = ext->start;
445 count += ext->count;
446 ext2fs_rb_erase(node, root);
447 rb_free_extent(bp, ext);
448 }
449 }
450
451 skip_insert:
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);
456
457 if ((ext->start + ext->count) <= start)
458 continue;
459
460 /* No more merging */
461 if ((start + count) < ext->start)
462 break;
463
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);
468 continue;
469 } else {
470 /* merge ext with new_ext */
471 count += ((ext->start + ext->count) -
472 (start + count));
473 ext2fs_rb_erase(node, root);
474 rb_free_extent(bp, ext);
475 break;
476 }
477 }
478
479 new_ext->start = start;
480 new_ext->count = count;
481
482 return retval;
483 }
484
rb_remove_extent(__u64 start,__u64 count,struct ext2fs_rb_private * bp)485 static int rb_remove_extent(__u64 start, __u64 count,
486 struct ext2fs_rb_private *bp)
487 {
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;
493 int retval = 0;
494
495 if (EXT2FS_RB_EMPTY_ROOT(root))
496 return 0;
497
498 while (*n) {
499 parent = *n;
500 ext = node_to_extent(parent);
501 if (start < ext->start) {
502 n = &(*n)->rb_left;
503 continue;
504 } else if (start >= (ext->start + ext->count)) {
505 n = &(*n)->rb_right;
506 continue;
507 }
508
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;
514
515 ext->count = start - ext->start;
516
517 rb_insert_extent(new_start, new_count, bp);
518 return 1;
519 }
520
521 if ((start + count) >= (ext->start + ext->count)) {
522 ext->count = start - ext->start;
523 retval = 1;
524 }
525
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);
530 break;
531 }
532
533 if (start == ext->start) {
534 ext->start += count;
535 ext->count -= count;
536 return 1;
537 }
538 }
539
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)
545 continue;
546
547 /* No more extents to be removed/truncated */
548 if ((start + count) < ext->start)
549 break;
550
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);
555 retval = 1;
556 continue;
557 } else {
558 /* modify the last extent in reigon to be removed */
559 ext->count -= ((start + count) - ext->start);
560 ext->start = start + count;
561 retval = 1;
562 break;
563 }
564 }
565
566 return retval;
567 }
568
rb_mark_bmap(ext2fs_generic_bitmap bitmap,__u64 arg)569 static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
570 {
571 struct ext2fs_rb_private *bp;
572
573 bp = (struct ext2fs_rb_private *) bitmap->private;
574 arg -= bitmap->start;
575
576 return rb_insert_extent(arg, 1, bp);
577 }
578
rb_unmark_bmap(ext2fs_generic_bitmap bitmap,__u64 arg)579 static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
580 {
581 struct ext2fs_rb_private *bp;
582 int retval;
583
584 bp = (struct ext2fs_rb_private *) bitmap->private;
585 arg -= bitmap->start;
586
587 retval = rb_remove_extent(arg, 1, bp);
588 check_tree(&bp->root, __func__);
589
590 return retval;
591 }
592
593 inline
rb_test_bmap(ext2fs_generic_bitmap bitmap,__u64 arg)594 static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
595 {
596 struct ext2fs_rb_private *bp;
597
598 bp = (struct ext2fs_rb_private *) bitmap->private;
599 arg -= bitmap->start;
600
601 return rb_test_bit(bp, arg);
602 }
603
rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap,__u64 arg,unsigned int num)604 static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
605 unsigned int num)
606 {
607 struct ext2fs_rb_private *bp;
608
609 bp = (struct ext2fs_rb_private *) bitmap->private;
610 arg -= bitmap->start;
611
612 rb_insert_extent(arg, num, bp);
613 }
614
rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap,__u64 arg,unsigned int num)615 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
616 unsigned int num)
617 {
618 struct ext2fs_rb_private *bp;
619
620 bp = (struct ext2fs_rb_private *) bitmap->private;
621 arg -= bitmap->start;
622
623 rb_remove_extent(arg, num, bp);
624 check_tree(&bp->root, __func__);
625 }
626
rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,__u64 start,unsigned int len)627 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
628 __u64 start, unsigned int len)
629 {
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;
634 int retval = 1;
635
636 bp = (struct ext2fs_rb_private *) bitmap->private;
637 n = &bp->root.rb_node;
638 start -= bitmap->start;
639
640 if ((len == 0) || EXT2FS_RB_EMPTY_ROOT(&bp->root))
641 return 1;
642
643 /*
644 * If we find nothing, we should examine whole extent, but
645 * when we find match, the extent is not clean, thus be return
646 * false.
647 */
648 while (*n) {
649 parent = *n;
650 ext = node_to_extent(parent);
651 if (start < ext->start) {
652 n = &(*n)->rb_left;
653 } else if (start >= (ext->start + ext->count)) {
654 n = &(*n)->rb_right;
655 } else {
656 /*
657 * We found extent int the tree -> extent is not
658 * clean
659 */
660 return 0;
661 }
662 }
663
664 node = parent;
665 while (node) {
666 next = ext2fs_rb_next(node);
667 ext = node_to_extent(node);
668 node = next;
669
670 if ((ext->start + ext->count) <= start)
671 continue;
672
673 /* No more merging */
674 if ((start + len) <= ext->start)
675 break;
676
677 retval = 0;
678 break;
679 }
680 return retval;
681 }
682
rb_set_bmap_range(ext2fs_generic_bitmap bitmap,__u64 start,size_t num,void * in)683 static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
684 __u64 start, size_t num, void *in)
685 {
686 struct ext2fs_rb_private *bp;
687 unsigned char *cp = in;
688 size_t i;
689 int first_set = -1;
690
691 bp = (struct ext2fs_rb_private *) bitmap->private;
692
693 for (i = 0; i < num; i++) {
694 if ((i & 7) == 0) {
695 unsigned char c = cp[i/8];
696 if (c == 0xFF) {
697 if (first_set == -1)
698 first_set = i;
699 i += 7;
700 continue;
701 }
702 if ((c == 0x00) && (first_set == -1)) {
703 i += 7;
704 continue;
705 }
706 }
707 if (ext2fs_test_bit(i, in)) {
708 if (first_set == -1)
709 first_set = i;
710 continue;
711 }
712 if (first_set == -1)
713 continue;
714
715 rb_insert_extent(start + first_set - bitmap->start,
716 i - first_set, bp);
717 first_set = -1;
718 }
719 if (first_set != -1)
720 rb_insert_extent(start + first_set - bitmap->start,
721 num - first_set, bp);
722
723 return 0;
724 }
725
rb_get_bmap_range(ext2fs_generic_bitmap bitmap,__u64 start,size_t num,void * out)726 static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
727 __u64 start, size_t num, void *out)
728 {
729
730 struct rb_node *parent = NULL, *next, **n;
731 struct ext2fs_rb_private *bp;
732 struct bmap_rb_extent *ext;
733 int count;
734 __u64 pos;
735
736 bp = (struct ext2fs_rb_private *) bitmap->private;
737 n = &bp->root.rb_node;
738 start -= bitmap->start;
739
740 if (EXT2FS_RB_EMPTY_ROOT(&bp->root))
741 return 0;
742
743 while (*n) {
744 parent = *n;
745 ext = node_to_extent(parent);
746 if (start < ext->start) {
747 n = &(*n)->rb_left;
748 } else if (start >= (ext->start + ext->count)) {
749 n = &(*n)->rb_right;
750 } else
751 break;
752 }
753
754 memset(out, 0, (num + 7) >> 3);
755
756 for (; parent != NULL; parent = next) {
757 next = ext2fs_rb_next(parent);
758 ext = node_to_extent(parent);
759
760 pos = ext->start;
761 count = ext->count;
762 if (pos >= start + num)
763 break;
764 if (pos < start) {
765 count -= start - pos;
766 if (count < 0)
767 continue;
768 pos = start;
769 }
770 if (pos + count > start + num)
771 count = start + num - pos;
772
773 while (count > 0) {
774 if ((count >= 8) &&
775 ((pos - start) % 8) == 0) {
776 int nbytes = count >> 3;
777 int offset = (pos - start) >> 3;
778
779 memset(((char *) out) + offset, 0xFF, nbytes);
780 pos += nbytes << 3;
781 count -= nbytes << 3;
782 continue;
783 }
784 ext2fs_fast_set_bit64((pos - start), out);
785 pos++;
786 count--;
787 }
788 }
789 return 0;
790 }
791
rb_clear_bmap(ext2fs_generic_bitmap bitmap)792 static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
793 {
794 struct ext2fs_rb_private *bp;
795
796 bp = (struct ext2fs_rb_private *) bitmap->private;
797
798 rb_free_tree(&bp->root);
799 bp->rcursor = NULL;
800 bp->rcursor_next = NULL;
801 bp->wcursor = NULL;
802 }
803
804 #ifdef BMAP_STATS
rb_print_stats(ext2fs_generic_bitmap bitmap)805 static void rb_print_stats(ext2fs_generic_bitmap bitmap)
806 {
807 struct ext2fs_rb_private *bp;
808 struct rb_node *node = NULL;
809 struct bmap_rb_extent *ext;
810 __u64 count = 0;
811 __u64 max_size = 0;
812 __u64 min_size = ULONG_MAX;
813 __u64 size = 0, avg_size = 0;
814 double eff;
815 #ifdef BMAP_STATS_OPS
816 __u64 mark_all, test_all;
817 double m_hit = 0.0, t_hit = 0.0;
818 #endif
819
820 bp = (struct ext2fs_rb_private *) bitmap->private;
821
822 node = ext2fs_rb_first(&bp->root);
823 for (node = ext2fs_rb_first(&bp->root); node != NULL;
824 node = ext2fs_rb_next(node)) {
825 ext = node_to_extent(node);
826 count++;
827 if (ext->count > max_size)
828 max_size = ext->count;
829 if (ext->count < min_size)
830 min_size = ext->count;
831 size += ext->count;
832 }
833
834 if (count)
835 avg_size = size / count;
836 if (min_size == ULONG_MAX)
837 min_size = 0;
838 eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) /
839 (bitmap->real_end - bitmap->start);
840 #ifdef BMAP_STATS_OPS
841 mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count;
842 test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count;
843 if (mark_all)
844 m_hit = ((double)bp->mark_hit / mark_all) * 100;
845 if (test_all)
846 t_hit = ((double)bp->test_hit / test_all) * 100;
847
848 fprintf(stderr, "%16llu cache hits on test (%.2f%%)\n"
849 "%16llu cache hits on mark (%.2f%%)\n",
850 bp->test_hit, t_hit, bp->mark_hit, m_hit);
851 #endif
852 fprintf(stderr, "%16llu extents (%llu bytes)\n",
853 count, ((count * sizeof(struct bmap_rb_extent)) +
854 sizeof(struct ext2fs_rb_private)));
855 fprintf(stderr, "%16llu bits minimum size\n",
856 min_size);
857 fprintf(stderr, "%16llu bits maximum size\n"
858 "%16llu bits average size\n",
859 max_size, avg_size);
860 fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", size,
861 bitmap->real_end - bitmap->start);
862 fprintf(stderr,
863 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
864 eff);
865 }
866 #else
rb_print_stats(ext2fs_generic_bitmap bitmap)867 static void rb_print_stats(ext2fs_generic_bitmap bitmap){}
868 #endif
869
870 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
871 .type = EXT2FS_BMAP64_RBTREE,
872 .new_bmap = rb_new_bmap,
873 .free_bmap = rb_free_bmap,
874 .copy_bmap = rb_copy_bmap,
875 .resize_bmap = rb_resize_bmap,
876 .mark_bmap = rb_mark_bmap,
877 .unmark_bmap = rb_unmark_bmap,
878 .test_bmap = rb_test_bmap,
879 .test_clear_bmap_extent = rb_test_clear_bmap_extent,
880 .mark_bmap_extent = rb_mark_bmap_extent,
881 .unmark_bmap_extent = rb_unmark_bmap_extent,
882 .set_bmap_range = rb_set_bmap_range,
883 .get_bmap_range = rb_get_bmap_range,
884 .clear_bmap = rb_clear_bmap,
885 .print_stats = rb_print_stats,
886 };
887