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 "config.h"
13 #include <stdio.h>
14 #include <string.h>
15 #if HAVE_UNISTD_H
16 #include <unistd.h>
17 #endif
18 #include <fcntl.h>
19 #include <time.h>
20 #if HAVE_SYS_STAT_H
21 #include <sys/stat.h>
22 #endif
23 #if HAVE_SYS_TYPES_H
24 #include <sys/types.h>
25 #endif
26 #if HAVE_LINUX_TYPES_H
27 #include <linux/types.h>
28 #endif
29
30 #include "ext2_fs.h"
31 #include "ext2fsP.h"
32 #include "bmap64.h"
33 #include "rbtree.h"
34
35 #include <limits.h>
36
37 struct bmap_rb_extent {
38 struct rb_node node;
39 __u64 start;
40 __u64 count;
41 };
42
43 struct ext2fs_rb_private {
44 struct rb_root root;
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
49 __u64 mark_hit;
50 __u64 test_hit;
51 #endif
52 };
53
node_to_extent(struct rb_node * node)54 inline static struct bmap_rb_extent *node_to_extent(struct rb_node *node)
55 {
56 /*
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.
61 */
62 return (struct bmap_rb_extent *) node;
63 }
64
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);
68
69 /* #define DEBUG_RB */
70
71 #ifdef DEBUG_RB
print_tree(struct rb_root * root)72 static void print_tree(struct rb_root *root)
73 {
74 struct rb_node *node = NULL;
75 struct bmap_rb_extent *ext;
76
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 (unsigned long long) ext->start,
84 (unsigned long long) ext->start + ext->count);
85 }
86 fprintf(stderr, "\t\t\t=================================\n");
87 }
88
check_tree(struct rb_root * root,const char * msg)89 static void check_tree(struct rb_root *root, const char *msg)
90 {
91 struct rb_node *node;
92 struct bmap_rb_extent *ext, *old = NULL;
93
94 for (node = ext2fs_rb_first(root); node;
95 node = ext2fs_rb_next(node)) {
96 ext = node_to_extent(node);
97 if (ext->count == 0) {
98 fprintf(stderr, "Tree Error: count is zero\n");
99 fprintf(stderr, "extent: %llu -> %llu (%llu)\n",
100 (unsigned long long) ext->start,
101 (unsigned long long) ext->start + ext->count,
102 (unsigned long long) ext->count);
103 goto err_out;
104 }
105 if (ext->start + ext->count < ext->start) {
106 fprintf(stderr,
107 "Tree Error: start or count is crazy\n");
108 fprintf(stderr, "extent: %llu -> %llu (%llu)\n",
109 (unsigned long long) ext->start,
110 (unsigned long long) ext->start + ext->count,
111 (unsigned long long) ext->count);
112 goto err_out;
113 }
114
115 if (old) {
116 if (old->start > ext->start) {
117 fprintf(stderr, "Tree Error: start is crazy\n");
118 fprintf(stderr, "extent: %llu -> %llu (%llu)\n",
119 (unsigned long long) old->start,
120 (unsigned long long) old->start + old->count,
121 (unsigned long long) old->count);
122 fprintf(stderr,
123 "extent next: %llu -> %llu (%llu)\n",
124 (unsigned long long) ext->start,
125 (unsigned long long) ext->start + ext->count,
126 (unsigned long long) ext->count);
127 goto err_out;
128 }
129 if ((old->start + old->count) >= ext->start) {
130 fprintf(stderr,
131 "Tree Error: extent is crazy\n");
132 fprintf(stderr, "extent: %llu -> %llu (%llu)\n",
133 (unsigned long long) old->start,
134 (unsigned long long) old->start + old->count,
135 (unsigned long long) old->count);
136 fprintf(stderr,
137 "extent next: %llu -> %llu (%llu)\n",
138 (unsigned long long) ext->start,
139 (unsigned long long) ext->start + ext->count,
140 (unsigned long long) ext->count);
141 goto err_out;
142 }
143 }
144 old = ext;
145 }
146 return;
147
148 err_out:
149 fprintf(stderr, "%s\n", msg);
150 print_tree(root);
151 exit(1);
152 }
153 #else
154 #define check_tree(root, msg) do {} while (0)
155 #define print_tree(root) do {} while (0)
156 #endif
157
rb_get_new_extent(struct bmap_rb_extent ** ext,__u64 start,__u64 count)158 static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start,
159 __u64 count)
160 {
161 struct bmap_rb_extent *new_ext;
162 int retval;
163
164 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
165 &new_ext);
166 if (retval)
167 abort();
168
169 new_ext->start = start;
170 new_ext->count = count;
171 *ext = new_ext;
172 }
173
174 inline
rb_free_extent(struct ext2fs_rb_private * bp,struct bmap_rb_extent * ext)175 static void rb_free_extent(struct ext2fs_rb_private *bp,
176 struct bmap_rb_extent *ext)
177 {
178 if (bp->wcursor == ext)
179 bp->wcursor = NULL;
180 if (bp->rcursor == ext)
181 bp->rcursor = NULL;
182 if (bp->rcursor_next == ext)
183 bp->rcursor_next = NULL;
184 ext2fs_free_mem(&ext);
185 }
186
rb_alloc_private_data(ext2fs_generic_bitmap_64 bitmap)187 static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap_64 bitmap)
188 {
189 struct ext2fs_rb_private *bp;
190 errcode_t retval;
191
192 retval = ext2fs_get_mem(sizeof (struct ext2fs_rb_private), &bp);
193 if (retval)
194 return retval;
195
196 bp->root = RB_ROOT;
197 bp->rcursor = NULL;
198 bp->rcursor_next = NULL;
199 bp->wcursor = NULL;
200
201 #ifdef ENABLE_BMAP_STATS_OPS
202 bp->test_hit = 0;
203 bp->mark_hit = 0;
204 #endif
205
206 bitmap->private = (void *) bp;
207 return 0;
208 }
209
rb_new_bmap(ext2_filsys fs EXT2FS_ATTR ((unused)),ext2fs_generic_bitmap_64 bitmap)210 static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
211 ext2fs_generic_bitmap_64 bitmap)
212 {
213 errcode_t retval;
214
215 retval = rb_alloc_private_data (bitmap);
216 if (retval)
217 return retval;
218
219 return 0;
220 }
221
rb_free_tree(struct rb_root * root)222 static void rb_free_tree(struct rb_root *root)
223 {
224 struct bmap_rb_extent *ext;
225 struct rb_node *node, *next;
226
227 for (node = ext2fs_rb_first(root); node; node = next) {
228 next = ext2fs_rb_next(node);
229 ext = node_to_extent(node);
230 ext2fs_rb_erase(node, root);
231 ext2fs_free_mem(&ext);
232 }
233 }
234
rb_free_bmap(ext2fs_generic_bitmap_64 bitmap)235 static void rb_free_bmap(ext2fs_generic_bitmap_64 bitmap)
236 {
237 struct ext2fs_rb_private *bp;
238
239 bp = (struct ext2fs_rb_private *) bitmap->private;
240
241 rb_free_tree(&bp->root);
242 ext2fs_free_mem(&bp);
243 bp = 0;
244 }
245
rb_copy_bmap(ext2fs_generic_bitmap_64 src,ext2fs_generic_bitmap_64 dest)246 static errcode_t rb_copy_bmap(ext2fs_generic_bitmap_64 src,
247 ext2fs_generic_bitmap_64 dest)
248 {
249 struct ext2fs_rb_private *src_bp, *dest_bp;
250 struct bmap_rb_extent *src_ext, *dest_ext;
251 struct rb_node *dest_node, *src_node, *dest_last, **n;
252 errcode_t retval = 0;
253
254 retval = rb_alloc_private_data (dest);
255 if (retval)
256 return retval;
257
258 src_bp = (struct ext2fs_rb_private *) src->private;
259 dest_bp = (struct ext2fs_rb_private *) dest->private;
260 src_bp->rcursor = NULL;
261 dest_bp->rcursor = NULL;
262
263 src_node = ext2fs_rb_first(&src_bp->root);
264 while (src_node) {
265 src_ext = node_to_extent(src_node);
266 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
267 &dest_ext);
268 if (retval)
269 break;
270
271 memcpy(dest_ext, src_ext, sizeof(struct bmap_rb_extent));
272
273 dest_node = &dest_ext->node;
274 n = &dest_bp->root.rb_node;
275
276 dest_last = NULL;
277 if (*n) {
278 dest_last = ext2fs_rb_last(&dest_bp->root);
279 n = &(dest_last)->rb_right;
280 }
281
282 ext2fs_rb_link_node(dest_node, dest_last, n);
283 ext2fs_rb_insert_color(dest_node, &dest_bp->root);
284
285 src_node = ext2fs_rb_next(src_node);
286 }
287
288 return retval;
289 }
290
rb_truncate(__u64 new_max,struct rb_root * root)291 static void rb_truncate(__u64 new_max, struct rb_root *root)
292 {
293 struct bmap_rb_extent *ext;
294 struct rb_node *node;
295
296 node = ext2fs_rb_last(root);
297 while (node) {
298 ext = node_to_extent(node);
299
300 if ((ext->start + ext->count - 1) <= new_max)
301 break;
302 else if (ext->start > new_max) {
303 ext2fs_rb_erase(node, root);
304 ext2fs_free_mem(&ext);
305 node = ext2fs_rb_last(root);
306 continue;
307 } else
308 ext->count = new_max - ext->start + 1;
309 }
310 }
311
rb_resize_bmap(ext2fs_generic_bitmap_64 bmap,__u64 new_end,__u64 new_real_end)312 static errcode_t rb_resize_bmap(ext2fs_generic_bitmap_64 bmap,
313 __u64 new_end, __u64 new_real_end)
314 {
315 struct ext2fs_rb_private *bp;
316
317 bp = (struct ext2fs_rb_private *) bmap->private;
318 bp->rcursor = NULL;
319 bp->wcursor = NULL;
320
321 rb_truncate(((new_end < bmap->end) ? new_end : bmap->end) - bmap->start,
322 &bp->root);
323
324 bmap->end = new_end;
325 bmap->real_end = new_real_end;
326
327 if (bmap->end < bmap->real_end)
328 rb_insert_extent(bmap->end + 1 - bmap->start,
329 bmap->real_end - bmap->end, bp);
330 return 0;
331
332 }
333
334 inline static int
rb_test_bit(struct ext2fs_rb_private * bp,__u64 bit)335 rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
336 {
337 struct bmap_rb_extent *rcursor, *next_ext = NULL;
338 struct rb_node *parent = NULL, *next;
339 struct rb_node **n = &bp->root.rb_node;
340 struct bmap_rb_extent *ext;
341
342 rcursor = bp->rcursor;
343 if (!rcursor)
344 goto search_tree;
345
346 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) {
347 #ifdef ENABLE_BMAP_STATS_OPS
348 bp->test_hit++;
349 #endif
350 return 1;
351 }
352
353 next_ext = bp->rcursor_next;
354 if (!next_ext) {
355 next = ext2fs_rb_next(&rcursor->node);
356 if (next)
357 next_ext = node_to_extent(next);
358 bp->rcursor_next = next_ext;
359 }
360 if (next_ext) {
361 if ((bit >= rcursor->start + rcursor->count) &&
362 (bit < next_ext->start)) {
363 #ifdef BMAP_STATS_OPS
364 bp->test_hit++;
365 #endif
366 return 0;
367 }
368 }
369 bp->rcursor = NULL;
370 bp->rcursor_next = NULL;
371
372 rcursor = bp->wcursor;
373 if (!rcursor)
374 goto search_tree;
375
376 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
377 return 1;
378
379 search_tree:
380
381 while (*n) {
382 parent = *n;
383 ext = node_to_extent(parent);
384 if (bit < ext->start)
385 n = &(*n)->rb_left;
386 else if (bit >= (ext->start + ext->count))
387 n = &(*n)->rb_right;
388 else {
389 bp->rcursor = ext;
390 bp->rcursor_next = NULL;
391 return 1;
392 }
393 }
394 return 0;
395 }
396
rb_insert_extent(__u64 start,__u64 count,struct ext2fs_rb_private * bp)397 static int rb_insert_extent(__u64 start, __u64 count,
398 struct ext2fs_rb_private *bp)
399 {
400 struct rb_root *root = &bp->root;
401 struct rb_node *parent = NULL, **n = &root->rb_node;
402 struct rb_node *new_node, *node, *next;
403 struct bmap_rb_extent *new_ext;
404 struct bmap_rb_extent *ext;
405 int retval = 0;
406
407 if (count == 0)
408 return 0;
409
410 bp->rcursor_next = NULL;
411 ext = bp->wcursor;
412 if (ext) {
413 if (start >= ext->start &&
414 start <= (ext->start + ext->count)) {
415 #ifdef ENABLE_BMAP_STATS_OPS
416 bp->mark_hit++;
417 #endif
418 goto got_extent;
419 }
420 }
421
422 while (*n) {
423 parent = *n;
424 ext = node_to_extent(parent);
425
426 if (start < ext->start) {
427 n = &(*n)->rb_left;
428 } else if (start > (ext->start + ext->count)) {
429 n = &(*n)->rb_right;
430 } else {
431 got_extent:
432 if ((start + count) <= (ext->start + ext->count))
433 return 1;
434
435 if ((ext->start + ext->count) == start)
436 retval = 0;
437 else
438 retval = 1;
439
440 count += (start - ext->start);
441 start = ext->start;
442 new_ext = ext;
443 new_node = &ext->node;
444
445 goto skip_insert;
446 }
447 }
448
449 rb_get_new_extent(&new_ext, start, count);
450
451 new_node = &new_ext->node;
452 ext2fs_rb_link_node(new_node, parent, n);
453 ext2fs_rb_insert_color(new_node, root);
454 bp->wcursor = new_ext;
455
456 node = ext2fs_rb_prev(new_node);
457 if (node) {
458 ext = node_to_extent(node);
459 if ((ext->start + ext->count) == start) {
460 start = ext->start;
461 count += ext->count;
462 ext2fs_rb_erase(node, root);
463 rb_free_extent(bp, ext);
464 }
465 }
466
467 skip_insert:
468 /* See if we can merge extent to the right */
469 for (node = ext2fs_rb_next(new_node); node != NULL; node = next) {
470 next = ext2fs_rb_next(node);
471 ext = node_to_extent(node);
472
473 if ((ext->start + ext->count) <= start)
474 continue;
475
476 /* No more merging */
477 if ((start + count) < ext->start)
478 break;
479
480 /* ext is embedded in new_ext interval */
481 if ((start + count) >= (ext->start + ext->count)) {
482 ext2fs_rb_erase(node, root);
483 rb_free_extent(bp, ext);
484 continue;
485 } else {
486 /* merge ext with new_ext */
487 count += ((ext->start + ext->count) -
488 (start + count));
489 ext2fs_rb_erase(node, root);
490 rb_free_extent(bp, ext);
491 break;
492 }
493 }
494
495 new_ext->start = start;
496 new_ext->count = count;
497
498 return retval;
499 }
500
rb_remove_extent(__u64 start,__u64 count,struct ext2fs_rb_private * bp)501 static int rb_remove_extent(__u64 start, __u64 count,
502 struct ext2fs_rb_private *bp)
503 {
504 struct rb_root *root = &bp->root;
505 struct rb_node *parent = NULL, **n = &root->rb_node;
506 struct rb_node *node;
507 struct bmap_rb_extent *ext;
508 __u64 new_start, new_count;
509 int retval = 0;
510
511 if (ext2fs_rb_empty_root(root))
512 return 0;
513
514 while (*n) {
515 parent = *n;
516 ext = node_to_extent(parent);
517 if (start < ext->start) {
518 n = &(*n)->rb_left;
519 continue;
520 } else if (start >= (ext->start + ext->count)) {
521 n = &(*n)->rb_right;
522 continue;
523 }
524
525 if ((start > ext->start) &&
526 (start + count) < (ext->start + ext->count)) {
527 /* We have to split extent into two */
528 new_start = start + count;
529 new_count = (ext->start + ext->count) - new_start;
530
531 ext->count = start - ext->start;
532
533 rb_insert_extent(new_start, new_count, bp);
534 return 1;
535 }
536
537 if ((start + count) >= (ext->start + ext->count)) {
538 ext->count = start - ext->start;
539 retval = 1;
540 }
541
542 if (0 == ext->count) {
543 parent = ext2fs_rb_next(&ext->node);
544 ext2fs_rb_erase(&ext->node, root);
545 rb_free_extent(bp, ext);
546 break;
547 }
548
549 if (start == ext->start) {
550 ext->start += count;
551 ext->count -= count;
552 return 1;
553 }
554 }
555
556 /* See if we should delete or truncate extent on the right */
557 for (; parent != NULL; parent = node) {
558 node = ext2fs_rb_next(parent);
559 ext = node_to_extent(parent);
560 if ((ext->start + ext->count) <= start)
561 continue;
562
563 /* No more extents to be removed/truncated */
564 if ((start + count) < ext->start)
565 break;
566
567 /* The entire extent is within the region to be removed */
568 if ((start + count) >= (ext->start + ext->count)) {
569 ext2fs_rb_erase(parent, root);
570 rb_free_extent(bp, ext);
571 retval = 1;
572 continue;
573 } else {
574 /* modify the last extent in region to be removed */
575 ext->count -= ((start + count) - ext->start);
576 ext->start = start + count;
577 retval = 1;
578 break;
579 }
580 }
581
582 return retval;
583 }
584
rb_mark_bmap(ext2fs_generic_bitmap_64 bitmap,__u64 arg)585 static int rb_mark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg)
586 {
587 struct ext2fs_rb_private *bp;
588 int retval;
589
590 bp = (struct ext2fs_rb_private *) bitmap->private;
591 arg -= bitmap->start;
592
593 retval = rb_insert_extent(arg, 1, bp);
594 check_tree(&bp->root, __func__);
595 return retval;
596 }
597
rb_unmark_bmap(ext2fs_generic_bitmap_64 bitmap,__u64 arg)598 static int rb_unmark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg)
599 {
600 struct ext2fs_rb_private *bp;
601 int retval;
602
603 bp = (struct ext2fs_rb_private *) bitmap->private;
604 arg -= bitmap->start;
605
606 retval = rb_remove_extent(arg, 1, bp);
607 check_tree(&bp->root, __func__);
608
609 return retval;
610 }
611
612 inline
rb_test_bmap(ext2fs_generic_bitmap_64 bitmap,__u64 arg)613 static int rb_test_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg)
614 {
615 struct ext2fs_rb_private *bp;
616
617 bp = (struct ext2fs_rb_private *) bitmap->private;
618 arg -= bitmap->start;
619
620 return rb_test_bit(bp, arg);
621 }
622
rb_mark_bmap_extent(ext2fs_generic_bitmap_64 bitmap,__u64 arg,unsigned int num)623 static void rb_mark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg,
624 unsigned int num)
625 {
626 struct ext2fs_rb_private *bp;
627
628 bp = (struct ext2fs_rb_private *) bitmap->private;
629 arg -= bitmap->start;
630
631 rb_insert_extent(arg, num, bp);
632 check_tree(&bp->root, __func__);
633 }
634
rb_unmark_bmap_extent(ext2fs_generic_bitmap_64 bitmap,__u64 arg,unsigned int num)635 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg,
636 unsigned int num)
637 {
638 struct ext2fs_rb_private *bp;
639
640 bp = (struct ext2fs_rb_private *) bitmap->private;
641 arg -= bitmap->start;
642
643 rb_remove_extent(arg, num, bp);
644 check_tree(&bp->root, __func__);
645 }
646
rb_test_clear_bmap_extent(ext2fs_generic_bitmap_64 bitmap,__u64 start,unsigned int len)647 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap_64 bitmap,
648 __u64 start, unsigned int len)
649 {
650 struct rb_node *parent = NULL, **n;
651 struct rb_node *node, *next;
652 struct ext2fs_rb_private *bp;
653 struct bmap_rb_extent *ext;
654 int retval = 1;
655
656 bp = (struct ext2fs_rb_private *) bitmap->private;
657 n = &bp->root.rb_node;
658 start -= bitmap->start;
659
660 if (len == 0 || ext2fs_rb_empty_root(&bp->root))
661 return 1;
662
663 /*
664 * If we find nothing, we should examine whole extent, but
665 * when we find match, the extent is not clean, thus be return
666 * false.
667 */
668 while (*n) {
669 parent = *n;
670 ext = node_to_extent(parent);
671 if (start < ext->start) {
672 n = &(*n)->rb_left;
673 } else if (start >= (ext->start + ext->count)) {
674 n = &(*n)->rb_right;
675 } else {
676 /*
677 * We found extent int the tree -> extent is not
678 * clean
679 */
680 return 0;
681 }
682 }
683
684 node = parent;
685 while (node) {
686 next = ext2fs_rb_next(node);
687 ext = node_to_extent(node);
688 node = next;
689
690 if ((ext->start + ext->count) <= start)
691 continue;
692
693 /* No more merging */
694 if ((start + len) <= ext->start)
695 break;
696
697 retval = 0;
698 break;
699 }
700 return retval;
701 }
702
rb_set_bmap_range(ext2fs_generic_bitmap_64 bitmap,__u64 start,size_t num,void * in)703 static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap_64 bitmap,
704 __u64 start, size_t num, void *in)
705 {
706 struct ext2fs_rb_private *bp;
707 unsigned char *cp = in;
708 size_t i;
709 int first_set = -1;
710
711 bp = (struct ext2fs_rb_private *) bitmap->private;
712
713 for (i = 0; i < num; i++) {
714 if ((i & 7) == 0) {
715 unsigned char c = cp[i/8];
716 if (c == 0xFF) {
717 if (first_set == -1)
718 first_set = i;
719 i += 7;
720 continue;
721 }
722 if ((c == 0x00) && (first_set == -1)) {
723 i += 7;
724 continue;
725 }
726 }
727 if (ext2fs_test_bit(i, in)) {
728 if (first_set == -1)
729 first_set = i;
730 continue;
731 }
732 if (first_set == -1)
733 continue;
734
735 rb_insert_extent(start + first_set - bitmap->start,
736 i - first_set, bp);
737 check_tree(&bp->root, __func__);
738 first_set = -1;
739 }
740 if (first_set != -1) {
741 rb_insert_extent(start + first_set - bitmap->start,
742 num - first_set, bp);
743 check_tree(&bp->root, __func__);
744 }
745
746 return 0;
747 }
748
rb_get_bmap_range(ext2fs_generic_bitmap_64 bitmap,__u64 start,size_t num,void * out)749 static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap_64 bitmap,
750 __u64 start, size_t num, void *out)
751 {
752
753 struct rb_node *parent = NULL, *next, **n;
754 struct ext2fs_rb_private *bp;
755 struct bmap_rb_extent *ext;
756 __u64 count, pos;
757
758 bp = (struct ext2fs_rb_private *) bitmap->private;
759 n = &bp->root.rb_node;
760 start -= bitmap->start;
761
762 if (ext2fs_rb_empty_root(&bp->root))
763 return 0;
764
765 while (*n) {
766 parent = *n;
767 ext = node_to_extent(parent);
768 if (start < ext->start) {
769 n = &(*n)->rb_left;
770 } else if (start >= (ext->start + ext->count)) {
771 n = &(*n)->rb_right;
772 } else
773 break;
774 }
775
776 memset(out, 0, (num + 7) >> 3);
777
778 for (; parent != NULL; parent = next) {
779 next = ext2fs_rb_next(parent);
780 ext = node_to_extent(parent);
781
782 pos = ext->start;
783 count = ext->count;
784 if (pos >= start + num)
785 break;
786 if (pos < start) {
787 if (pos + count < start)
788 continue;
789 count -= start - pos;
790 pos = start;
791 }
792 if (pos + count > start + num)
793 count = start + num - pos;
794
795 while (count > 0) {
796 if ((count >= 8) &&
797 ((pos - start) % 8) == 0) {
798 int nbytes = count >> 3;
799 int offset = (pos - start) >> 3;
800
801 memset(((char *) out) + offset, 0xFF, nbytes);
802 pos += nbytes << 3;
803 count -= nbytes << 3;
804 continue;
805 }
806 ext2fs_fast_set_bit64((pos - start), out);
807 pos++;
808 count--;
809 }
810 }
811 return 0;
812 }
813
rb_clear_bmap(ext2fs_generic_bitmap_64 bitmap)814 static void rb_clear_bmap(ext2fs_generic_bitmap_64 bitmap)
815 {
816 struct ext2fs_rb_private *bp;
817
818 bp = (struct ext2fs_rb_private *) bitmap->private;
819
820 rb_free_tree(&bp->root);
821 bp->rcursor = NULL;
822 bp->rcursor_next = NULL;
823 bp->wcursor = NULL;
824 check_tree(&bp->root, __func__);
825 }
826
rb_find_first_zero(ext2fs_generic_bitmap_64 bitmap,__u64 start,__u64 end,__u64 * out)827 static errcode_t rb_find_first_zero(ext2fs_generic_bitmap_64 bitmap,
828 __u64 start, __u64 end, __u64 *out)
829 {
830 struct rb_node *parent = NULL, **n;
831 struct ext2fs_rb_private *bp;
832 struct bmap_rb_extent *ext;
833
834 bp = (struct ext2fs_rb_private *) bitmap->private;
835 n = &bp->root.rb_node;
836 start -= bitmap->start;
837 end -= bitmap->start;
838
839 if (start > end)
840 return EINVAL;
841
842 if (ext2fs_rb_empty_root(&bp->root))
843 return ENOENT;
844
845 while (*n) {
846 parent = *n;
847 ext = node_to_extent(parent);
848 if (start < ext->start) {
849 n = &(*n)->rb_left;
850 } else if (start >= (ext->start + ext->count)) {
851 n = &(*n)->rb_right;
852 } else if (ext->start + ext->count <= end) {
853 *out = ext->start + ext->count + bitmap->start;
854 return 0;
855 } else
856 return ENOENT;
857 }
858
859 *out = start + bitmap->start;
860 return 0;
861 }
862
rb_find_first_set(ext2fs_generic_bitmap_64 bitmap,__u64 start,__u64 end,__u64 * out)863 static errcode_t rb_find_first_set(ext2fs_generic_bitmap_64 bitmap,
864 __u64 start, __u64 end, __u64 *out)
865 {
866 struct rb_node *parent = NULL, **n;
867 struct rb_node *node;
868 struct ext2fs_rb_private *bp;
869 struct bmap_rb_extent *ext;
870
871 bp = (struct ext2fs_rb_private *) bitmap->private;
872 n = &bp->root.rb_node;
873 start -= bitmap->start;
874 end -= bitmap->start;
875
876 if (start > end)
877 return EINVAL;
878
879 if (ext2fs_rb_empty_root(&bp->root))
880 return ENOENT;
881
882 while (*n) {
883 parent = *n;
884 ext = node_to_extent(parent);
885 if (start < ext->start) {
886 n = &(*n)->rb_left;
887 } else if (start >= (ext->start + ext->count)) {
888 n = &(*n)->rb_right;
889 } else {
890 /* The start bit is set */
891 *out = start + bitmap->start;
892 return 0;
893 }
894 }
895
896 node = parent;
897 ext = node_to_extent(node);
898 if (ext->start < start) {
899 node = ext2fs_rb_next(node);
900 if (node == NULL)
901 return ENOENT;
902 ext = node_to_extent(node);
903 }
904 if (ext->start <= end) {
905 *out = ext->start + bitmap->start;
906 return 0;
907 }
908 return ENOENT;
909 }
910
911 #ifdef ENABLE_BMAP_STATS
rb_print_stats(ext2fs_generic_bitmap_64 bitmap)912 static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap)
913 {
914 struct ext2fs_rb_private *bp;
915 struct rb_node *node = NULL;
916 struct bmap_rb_extent *ext;
917 __u64 count = 0;
918 __u64 max_size = 0;
919 __u64 min_size = ULONG_MAX;
920 __u64 size = 0, avg_size = 0;
921 double eff;
922 #ifdef ENABLE_BMAP_STATS_OPS
923 __u64 mark_all, test_all;
924 double m_hit = 0.0, t_hit = 0.0;
925 #endif
926
927 bp = (struct ext2fs_rb_private *) bitmap->private;
928
929 for (node = ext2fs_rb_first(&bp->root); node != NULL;
930 node = ext2fs_rb_next(node)) {
931 ext = node_to_extent(node);
932 count++;
933 if (ext->count > max_size)
934 max_size = ext->count;
935 if (ext->count < min_size)
936 min_size = ext->count;
937 size += ext->count;
938 }
939
940 if (count)
941 avg_size = size / count;
942 if (min_size == ULONG_MAX)
943 min_size = 0;
944 eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) /
945 (bitmap->real_end - bitmap->start);
946 #ifdef ENABLE_BMAP_STATS_OPS
947 mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count;
948 test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count;
949 if (mark_all)
950 m_hit = ((double)bp->mark_hit / mark_all) * 100;
951 if (test_all)
952 t_hit = ((double)bp->test_hit / test_all) * 100;
953
954 fprintf(stderr, "%16llu cache hits on test (%.2f%%)\n"
955 "%16llu cache hits on mark (%.2f%%)\n",
956 bp->test_hit, t_hit, bp->mark_hit, m_hit);
957 #endif
958 fprintf(stderr, "%16llu extents (%llu bytes)\n",
959 (unsigned long long) count, (unsigned long long)
960 ((count * sizeof(struct bmap_rb_extent)) +
961 sizeof(struct ext2fs_rb_private)));
962 fprintf(stderr, "%16llu bits minimum size\n",
963 (unsigned long long) min_size);
964 fprintf(stderr, "%16llu bits maximum size\n"
965 "%16llu bits average size\n",
966 (unsigned long long) max_size, (unsigned long long) avg_size);
967 fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n",
968 (unsigned long long) size,
969 (unsigned long long) bitmap->real_end - bitmap->start);
970 fprintf(stderr,
971 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
972 eff);
973 }
974 #else
rb_print_stats(ext2fs_generic_bitmap_64 bitmap EXT2FS_ATTR ((unused)))975 static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap EXT2FS_ATTR((unused)))
976 {
977 }
978 #endif
979
980 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
981 .type = EXT2FS_BMAP64_RBTREE,
982 .new_bmap = rb_new_bmap,
983 .free_bmap = rb_free_bmap,
984 .copy_bmap = rb_copy_bmap,
985 .resize_bmap = rb_resize_bmap,
986 .mark_bmap = rb_mark_bmap,
987 .unmark_bmap = rb_unmark_bmap,
988 .test_bmap = rb_test_bmap,
989 .test_clear_bmap_extent = rb_test_clear_bmap_extent,
990 .mark_bmap_extent = rb_mark_bmap_extent,
991 .unmark_bmap_extent = rb_unmark_bmap_extent,
992 .set_bmap_range = rb_set_bmap_range,
993 .get_bmap_range = rb_get_bmap_range,
994 .clear_bmap = rb_clear_bmap,
995 .print_stats = rb_print_stats,
996 .find_first_zero = rb_find_first_zero,
997 .find_first_set = rb_find_first_set,
998 };
999