X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=lib%2Fext2fs%2Fblkmap64_rb.c;h=a1dde6db8be44b0350df1ac03bde216312f56ea4;hb=8b90ab2b1cfa3974097b0466d8f7563323dda0c2;hp=31fc3934b850327f6562b568a9c6cce444825f18;hpb=c1359d91958cadfbc0987921ee5b4db717852e90;p=tools%2Fe2fsprogs.git diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c index 31fc393..a1dde6d 100644 --- a/lib/ext2fs/blkmap64_rb.c +++ b/lib/ext2fs/blkmap64_rb.c @@ -33,15 +33,31 @@ struct bmap_rb_extent { struct rb_node node; __u64 start; - __u32 count; + __u64 count; }; struct ext2fs_rb_private { struct rb_root root; - struct bmap_rb_extent **wcursor; - struct bmap_rb_extent **rcursor; + struct bmap_rb_extent *wcursor; + struct bmap_rb_extent *rcursor; + struct bmap_rb_extent *rcursor_next; +#ifdef BMAP_STATS_OPS + __u64 mark_hit; + __u64 test_hit; +#endif }; +inline static struct bmap_rb_extent *node_to_extent(struct rb_node *node) +{ + /* + * This depends on the fact the struct rb_node is at the + * beginning of the bmap_rb_extent structure. We use this + * instead of the ext2fs_rb_entry macro because it causes gcc + * -Wall to generate a huge amount of noise. + */ + return (struct bmap_rb_extent *) node; +} + static int rb_insert_extent(__u64 start, __u64 count, struct ext2fs_rb_private *); static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64); @@ -58,30 +74,30 @@ static void print_tree(struct rb_root *root) node = ext2fs_rb_first(root); for (node = ext2fs_rb_first(root); node != NULL; node = ext2fs_rb_next(node)) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); printf("\t\t\t--> (%llu -> %llu)\n", ext->start, ext->start + ext->count); } printf("\t\t\t=================================\n"); } -static int check_tree(struct rb_root *root, const char *msg) +static void check_tree(struct rb_root *root, const char *msg) { - struct rb_node *new_node, *node, *next; + struct rb_node *node; struct bmap_rb_extent *ext, *old = NULL; for (node = ext2fs_rb_first(root); node; node = ext2fs_rb_next(node)) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); - if (ext->count <= 0) { - printf("Tree Error: count is crazy\n"); - printf("extent: %llu -> %llu (%u)\n", ext->start, + ext = node_to_extent(node); + if (ext->count == 0) { + printf("Tree Error: count is zero\n"); + printf("extent: %llu -> %llu (%llu)\n", ext->start, ext->start + ext->count, ext->count); goto err_out; } - if (ext->start < 0) { - printf("Tree Error: start is crazy\n"); - printf("extent: %llu -> %llu (%u)\n", ext->start, + if (ext->start + ext->count < ext->start) { + printf("Tree Error: start or count is crazy\n"); + printf("extent: %llu -> %llu (%llu)\n", ext->start, ext->start + ext->count, ext->count); goto err_out; } @@ -89,20 +105,20 @@ static int check_tree(struct rb_root *root, const char *msg) if (old) { if (old->start > ext->start) { printf("Tree Error: start is crazy\n"); - printf("extent: %llu -> %llu (%u)\n", + printf("extent: %llu -> %llu (%llu)\n", old->start, old->start + old->count, old->count); - printf("extent next: %llu -> %llu (%u)\n", + printf("extent next: %llu -> %llu (%llu)\n", ext->start, ext->start + ext->count, ext->count); goto err_out; } if ((old->start + old->count) >= ext->start) { printf("Tree Error: extent is crazy\n"); - printf("extent: %llu -> %llu (%u)\n", + printf("extent: %llu -> %llu (%llu)\n", old->start, old->start + old->count, old->count); - printf("extent next: %llu -> %llu (%u)\n", + printf("extent next: %llu -> %llu (%llu)\n", ext->start, ext->start + ext->count, ext->count); goto err_out; @@ -110,7 +126,7 @@ static int check_tree(struct rb_root *root, const char *msg) } old = ext; } - return 0; + return; err_out: printf("%s\n", msg); @@ -118,8 +134,8 @@ err_out: exit(1); } #else -#define check_tree(root, msg) 0 -#define print_tree(root, msg) 0 +#define check_tree(root, msg) do {} while (0) +#define print_tree(root) do {} while (0) #endif static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start, @@ -144,10 +160,12 @@ inline static void rb_free_extent(struct ext2fs_rb_private *bp, struct bmap_rb_extent *ext) { - if (*bp->wcursor == ext) - *bp->wcursor = NULL; - if (*bp->rcursor == ext) - *bp->rcursor = NULL; + if (bp->wcursor == ext) + bp->wcursor = NULL; + if (bp->rcursor == ext) + bp->rcursor = NULL; + if (bp->rcursor_next == ext) + bp->rcursor_next = NULL; ext2fs_free_mem(&ext); } @@ -161,14 +179,14 @@ static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap) return retval; bp->root = RB_ROOT; - retval = ext2fs_get_mem(sizeof(struct bmap_rb_extent *), &bp->rcursor); - if (retval) - return retval; - retval = ext2fs_get_mem(sizeof(struct bmap_rb_extent *), &bp->wcursor); - if (retval) - return retval; - *bp->rcursor = NULL; - *bp->wcursor = NULL; + bp->rcursor = NULL; + bp->rcursor_next = NULL; + bp->wcursor = NULL; + +#ifdef BMAP_STATS_OPS + bp->test_hit = 0; + bp->mark_hit = 0; +#endif bitmap->private = (void *) bp; return 0; @@ -193,7 +211,7 @@ static void rb_free_tree(struct rb_root *root) for (node = ext2fs_rb_first(root); node; node = next) { next = ext2fs_rb_next(node); - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); ext2fs_rb_erase(node, root); ext2fs_free_mem(&ext); } @@ -206,8 +224,6 @@ static void rb_free_bmap(ext2fs_generic_bitmap bitmap) bp = (struct ext2fs_rb_private *) bitmap->private; rb_free_tree(&bp->root); - ext2fs_free_mem(&bp->rcursor); - ext2fs_free_mem(&bp->wcursor); ext2fs_free_mem(&bp); bp = 0; } @@ -226,12 +242,12 @@ static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src, src_bp = (struct ext2fs_rb_private *) src->private; dest_bp = (struct ext2fs_rb_private *) dest->private; - *src_bp->rcursor = NULL; - *dest_bp->rcursor = NULL; + src_bp->rcursor = NULL; + dest_bp->rcursor = NULL; src_node = ext2fs_rb_first(&src_bp->root); while (src_node) { - src_ext = ext2fs_rb_entry(src_node, struct bmap_rb_extent, node); + src_ext = node_to_extent(src_node); retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent), &dest_ext); if (retval) @@ -264,7 +280,7 @@ static void rb_truncate(__u64 new_max, struct rb_root *root) node = ext2fs_rb_last(root); while (node) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); if ((ext->start + ext->count - 1) <= new_max) break; @@ -290,8 +306,8 @@ static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap, } bp = (struct ext2fs_rb_private *) bmap->private; - *bp->rcursor = NULL; - *bp->wcursor = NULL; + bp->rcursor = NULL; + bp->wcursor = NULL; /* truncate tree to new_real_end size */ rb_truncate(new_real_end, &bp->root); @@ -305,20 +321,42 @@ static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap, inline static int rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit) { - struct bmap_rb_extent *rcursor; - struct rb_node *parent = NULL; + struct bmap_rb_extent *rcursor, *next_ext = NULL; + struct rb_node *parent = NULL, *next; struct rb_node **n = &bp->root.rb_node; struct bmap_rb_extent *ext; - int i=0; - rcursor = *bp->rcursor; + rcursor = bp->rcursor; if (!rcursor) goto search_tree; - if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) + if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) { +#ifdef BMAP_STATS_OPS + bp->test_hit++; +#endif return 1; + } - rcursor = *bp->wcursor; + next_ext = bp->rcursor_next; + if (!next_ext) { + next = ext2fs_rb_next(&rcursor->node); + if (next) + next_ext = node_to_extent(next); + bp->rcursor_next = next_ext; + } + if (next_ext) { + if ((bit >= rcursor->start + rcursor->count) && + (bit < next_ext->start)) { +#ifdef BMAP_STATS_OPS + bp->test_hit++; +#endif + return 0; + } + } + bp->rcursor = NULL; + bp->rcursor_next = NULL; + + rcursor = bp->wcursor; if (!rcursor) goto search_tree; @@ -329,13 +367,14 @@ search_tree: while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (bit < ext->start) n = &(*n)->rb_left; else if (bit >= (ext->start + ext->count)) n = &(*n)->rb_right; else { - *bp->rcursor = ext; + bp->rcursor = ext; + bp->rcursor_next = NULL; return 1; } } @@ -352,16 +391,21 @@ static int rb_insert_extent(__u64 start, __u64 count, struct bmap_rb_extent *ext; int retval = 0; - ext = *bp->wcursor; + bp->rcursor_next = NULL; + ext = bp->wcursor; if (ext) { if (start >= ext->start && - start <= (ext->start + ext->count)) + start <= (ext->start + ext->count)) { +#ifdef BMAP_STATS_OPS + bp->mark_hit++; +#endif goto got_extent; + } } while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (start < ext->start) { n = &(*n)->rb_left; @@ -391,11 +435,11 @@ got_extent: new_node = &new_ext->node; ext2fs_rb_link_node(new_node, parent, n); ext2fs_rb_insert_color(new_node, root); - *bp->wcursor = new_ext; + bp->wcursor = new_ext; node = ext2fs_rb_prev(new_node); if (node) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); if ((ext->start + ext->count) == start) { start = ext->start; count += ext->count; @@ -408,7 +452,7 @@ skip_insert: /* See if we can merge extent to the right */ for (node = ext2fs_rb_next(new_node); node != NULL; node = next) { next = ext2fs_rb_next(node); - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); if ((ext->start + ext->count) <= start) continue; @@ -453,7 +497,7 @@ static int rb_remove_extent(__u64 start, __u64 count, while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (start < ext->start) { n = &(*n)->rb_left; continue; @@ -496,7 +540,7 @@ static int rb_remove_extent(__u64 start, __u64 count, /* See if we should delete or truncate extent on the right */ for (; parent != NULL; parent = node) { node = ext2fs_rb_next(parent); - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if ((ext->start + ext->count) <= start) continue; @@ -525,13 +569,14 @@ static int rb_remove_extent(__u64 start, __u64 count, static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) { struct ext2fs_rb_private *bp; - int i; - + int retval; bp = (struct ext2fs_rb_private *) bitmap->private; arg -= bitmap->start; - return rb_insert_extent(arg, 1, bp); + retval = rb_insert_extent(arg, 1, bp); + check_tree(&bp->root, __func__); + return retval; } static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg) @@ -563,19 +608,18 @@ static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, unsigned int num) { struct ext2fs_rb_private *bp; - struct bmap_rb_extent *new_ext; bp = (struct ext2fs_rb_private *) bitmap->private; arg -= bitmap->start; rb_insert_extent(arg, num, bp); + check_tree(&bp->root, __func__); } static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg, unsigned int num) { struct ext2fs_rb_private *bp; - int ret; bp = (struct ext2fs_rb_private *) bitmap->private; arg -= bitmap->start; @@ -607,7 +651,7 @@ static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, */ while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (start < ext->start) { n = &(*n)->rb_left; } else if (start >= (ext->start + ext->count)) { @@ -624,7 +668,7 @@ static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap, node = parent; while (node) { next = ext2fs_rb_next(node); - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); node = next; if ((ext->start + ext->count) <= start) @@ -644,15 +688,43 @@ static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap, __u64 start, size_t num, void *in) { struct ext2fs_rb_private *bp; + unsigned char *cp = in; size_t i; - int ret; + int first_set = -1; bp = (struct ext2fs_rb_private *) bitmap->private; for (i = 0; i < num; i++) { - ret = ext2fs_test_bit(i, in); - if (ret) - rb_insert_extent(start + i - bitmap->start, 1, bp); + if ((i & 7) == 0) { + unsigned char c = cp[i/8]; + if (c == 0xFF) { + if (first_set == -1) + first_set = i; + i += 7; + continue; + } + if ((c == 0x00) && (first_set == -1)) { + i += 7; + continue; + } + } + if (ext2fs_test_bit(i, in)) { + if (first_set == -1) + first_set = i; + continue; + } + if (first_set == -1) + continue; + + rb_insert_extent(start + first_set - bitmap->start, + i - first_set, bp); + check_tree(&bp->root, __func__); + first_set = -1; + } + if (first_set != -1) { + rb_insert_extent(start + first_set - bitmap->start, + num - first_set, bp); + check_tree(&bp->root, __func__); } return 0; @@ -665,6 +737,7 @@ static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap, struct rb_node *parent = NULL, *next, **n; struct ext2fs_rb_private *bp; struct bmap_rb_extent *ext; + int count; __u64 pos; bp = (struct ext2fs_rb_private *) bitmap->private; @@ -676,7 +749,7 @@ static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap, while (*n) { parent = *n; - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); if (start < ext->start) { n = &(*n)->rb_left; } else if (start >= (ext->start + ext->count)) { @@ -685,45 +758,205 @@ static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap, break; } - pos = start; + memset(out, 0, (num + 7) >> 3); + for (; parent != NULL; parent = next) { next = ext2fs_rb_next(parent); - ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + ext = node_to_extent(parent); - while (((pos - start) < num) && - (pos < ext->start)) { - ext2fs_fast_clear_bit64((pos - start), out); - pos++; + pos = ext->start; + count = ext->count; + if (pos >= start + num) + break; + if (pos < start) { + count -= start - pos; + if (count < 0) + continue; + pos = start; } - - if ((pos - start) >= num) - return 0; - - while (((pos - start) < num) && - (pos < (ext->start + ext->count))) { + if (pos + count > start + num) + count = start + num - pos; + + while (count > 0) { + if ((count >= 8) && + ((pos - start) % 8) == 0) { + int nbytes = count >> 3; + int offset = (pos - start) >> 3; + + memset(((char *) out) + offset, 0xFF, nbytes); + pos += nbytes << 3; + count -= nbytes << 3; + continue; + } ext2fs_fast_set_bit64((pos - start), out); pos++; + count--; } } + return 0; +} + +static void rb_clear_bmap(ext2fs_generic_bitmap bitmap) +{ + struct ext2fs_rb_private *bp; + + bp = (struct ext2fs_rb_private *) bitmap->private; + + rb_free_tree(&bp->root); + bp->rcursor = NULL; + bp->rcursor_next = NULL; + bp->wcursor = NULL; + check_tree(&bp->root, __func__); +} - while ((pos - start) < num) { - ext2fs_fast_clear_bit64((pos - start), out); - pos++; +static errcode_t rb_find_first_zero(ext2fs_generic_bitmap bitmap, + __u64 start, __u64 end, __u64 *out) +{ + struct rb_node *parent = NULL, **n; + struct ext2fs_rb_private *bp; + struct bmap_rb_extent *ext; + + bp = (struct ext2fs_rb_private *) bitmap->private; + n = &bp->root.rb_node; + start -= bitmap->start; + end -= bitmap->start; + + if (start > end) + return EINVAL; + + if (EXT2FS_RB_EMPTY_ROOT(&bp->root)) + return ENOENT; + + while (*n) { + parent = *n; + ext = node_to_extent(parent); + if (start < ext->start) { + n = &(*n)->rb_left; + } else if (start >= (ext->start + ext->count)) { + n = &(*n)->rb_right; + } else if (ext->start + ext->count <= end) { + *out = ext->start + ext->count + bitmap->start; + return 0; + } else + return ENOENT; } + *out = start + bitmap->start; return 0; } -static void rb_clear_bmap(ext2fs_generic_bitmap bitmap) +static errcode_t rb_find_first_set(ext2fs_generic_bitmap bitmap, + __u64 start, __u64 end, __u64 *out) { + struct rb_node *parent = NULL, **n; + struct rb_node *node; struct ext2fs_rb_private *bp; + struct bmap_rb_extent *ext; bp = (struct ext2fs_rb_private *) bitmap->private; + n = &bp->root.rb_node; + start -= bitmap->start; + end -= bitmap->start; - rb_free_tree(&bp->root); - *bp->rcursor = NULL; - *bp->wcursor = NULL; + if (start > end) + return EINVAL; + + if (EXT2FS_RB_EMPTY_ROOT(&bp->root)) + return ENOENT; + + while (*n) { + parent = *n; + ext = node_to_extent(parent); + if (start < ext->start) { + n = &(*n)->rb_left; + } else if (start >= (ext->start + ext->count)) { + n = &(*n)->rb_right; + } else { + /* The start bit is set */ + *out = start + bitmap->start; + return 0; + } + } + + node = parent; + ext = node_to_extent(node); + if (ext->start < start) { + node = ext2fs_rb_next(node); + if (node == NULL) + return ENOENT; + ext = node_to_extent(node); + } + if (ext->start <= end) { + *out = ext->start + bitmap->start; + return 0; + } + return ENOENT; +} + +#ifdef BMAP_STATS +static void rb_print_stats(ext2fs_generic_bitmap bitmap) +{ + struct ext2fs_rb_private *bp; + struct rb_node *node = NULL; + struct bmap_rb_extent *ext; + __u64 count = 0; + __u64 max_size = 0; + __u64 min_size = ULONG_MAX; + __u64 size = 0, avg_size = 0; + double eff; +#ifdef BMAP_STATS_OPS + __u64 mark_all, test_all; + double m_hit = 0.0, t_hit = 0.0; +#endif + + bp = (struct ext2fs_rb_private *) bitmap->private; + + for (node = ext2fs_rb_first(&bp->root); node != NULL; + node = ext2fs_rb_next(node)) { + ext = node_to_extent(node); + count++; + if (ext->count > max_size) + max_size = ext->count; + if (ext->count < min_size) + min_size = ext->count; + size += ext->count; + } + + if (count) + avg_size = size / count; + if (min_size == ULONG_MAX) + min_size = 0; + eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) / + (bitmap->real_end - bitmap->start); +#ifdef BMAP_STATS_OPS + mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count; + test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count; + if (mark_all) + m_hit = ((double)bp->mark_hit / mark_all) * 100; + if (test_all) + t_hit = ((double)bp->test_hit / test_all) * 100; + + fprintf(stderr, "%16llu cache hits on test (%.2f%%)\n" + "%16llu cache hits on mark (%.2f%%)\n", + bp->test_hit, t_hit, bp->mark_hit, m_hit); +#endif + fprintf(stderr, "%16llu extents (%llu bytes)\n", + count, ((count * sizeof(struct bmap_rb_extent)) + + sizeof(struct ext2fs_rb_private))); + fprintf(stderr, "%16llu bits minimum size\n", + min_size); + fprintf(stderr, "%16llu bits maximum size\n" + "%16llu bits average size\n", + max_size, avg_size); + fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", size, + bitmap->real_end - bitmap->start); + fprintf(stderr, + "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n", + eff); } +#else +static void rb_print_stats(ext2fs_generic_bitmap bitmap){} +#endif struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { .type = EXT2FS_BMAP64_RBTREE, @@ -740,4 +973,7 @@ struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { .set_bmap_range = rb_set_bmap_range, .get_bmap_range = rb_get_bmap_range, .clear_bmap = rb_clear_bmap, + .print_stats = rb_print_stats, + .find_first_zero = rb_find_first_zero, + .find_first_set = rb_find_first_set, };