diff options
Diffstat (limited to 'lib/ext2fs/blkmap64_rb.c')
-rw-r--r-- | lib/ext2fs/blkmap64_rb.c | 331 |
1 files changed, 243 insertions, 88 deletions
diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c index aba7cfd3..4dcb03f9 100644 --- a/lib/ext2fs/blkmap64_rb.c +++ b/lib/ext2fs/blkmap64_rb.c @@ -33,19 +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); @@ -62,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 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; } @@ -93,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; @@ -114,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); @@ -122,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, @@ -148,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); } @@ -165,14 +179,9 @@ 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; @@ -202,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); } @@ -215,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; } @@ -235,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) @@ -273,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; @@ -299,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); @@ -314,13 +321,12 @@ 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; @@ -331,7 +337,26 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit) 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; @@ -342,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; } } @@ -365,7 +391,8 @@ 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)) { @@ -378,7 +405,7 @@ static int rb_insert_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; @@ -408,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; @@ -425,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; @@ -470,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; @@ -513,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; @@ -542,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) @@ -580,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; @@ -624,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)) { @@ -641,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) @@ -661,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; @@ -682,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; @@ -693,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)) { @@ -702,44 +758,139 @@ 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; - while ((pos - start) < num) { - ext2fs_fast_clear_bit64((pos - start), out); - pos++; + rb_free_tree(&bp->root); + bp->rcursor = NULL; + bp->rcursor_next = NULL; + bp->wcursor = NULL; + check_tree(&bp->root, __func__); +} + +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 @@ -752,15 +903,17 @@ static void rb_print_stats(ext2fs_generic_bitmap bitmap) __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 eff, m_hit = 0.0, t_hit = 0.0; + double m_hit = 0.0, t_hit = 0.0; +#endif bp = (struct ext2fs_rb_private *) bitmap->private; - node = ext2fs_rb_first(&bp->root); for (node = ext2fs_rb_first(&bp->root); node != NULL; node = ext2fs_rb_next(node)) { - ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node); + ext = node_to_extent(node); count++; if (ext->count > max_size) max_size = ext->count; @@ -821,4 +974,6 @@ struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { .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, }; |