Re: [PATCH v2] btrfs: index free space entries on size
From: Nikolay Borisov <hidden>
Date: 2021-09-30 13:07:13
On 29.09.21 г. 18:17, Josef Bacik wrote: <snip>
quoted hunk ↗ jump to hunk
@@ -1887,15 +1928,37 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, if (!ctl->free_space_offset.rb_node) goto out; - entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1); - if (!entry) - goto out; + if (use_bytes_index) { + node = rb_first_cached(&ctl->free_space_bytes); + } else { + entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), + 0, 1); + if (!entry) + goto out; + node = &entry->offset_index; + } - for (node = &entry->offset_index; node; node = rb_next(node)) { - entry = rb_entry(node, struct btrfs_free_space, offset_index); + for (; node; node = rb_next(node)) { + if (use_bytes_index) + entry = rb_entry(node, struct btrfs_free_space, + bytes_index); + else + entry = rb_entry(node, struct btrfs_free_space, + offset_index); + + /* + * If we are using the bytes index then all subsequent entries + * in this tree are going to be < bytes, so simply set the max + * extent size and exit the loop. + * + * If we're using the offset index then we need to keep going + * through the rest of the tree. + */ if (entry->bytes < *bytes) { *max_extent_size = max(get_max_extent_size(entry), *max_extent_size); + if (use_bytes_index) + break;
I think we also need this check further then in the:
if (entry->bytes < *bytes + align_off) {
branch, because we can very well have the largest entry satisfy the
requested byte size, but adding the alignment might make it insufficient,
in this case we are going to loop again with the next smaller entry
which might still be larger than the requested bytes but insufficient
when factoring in the alignment. This isn't a correctness issue so
much as it causes some needless work depending on what we've cached.
Furthermore, the correct way to fix this is to simply eliminate
initial 'if (entry->bytes < *bytes)' check, calculate the offset
or set it to 0 and really leave the 2nd one i.e :
@@ -1946,22 +1954,6 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, entry = rb_entry(node, struct btrfs_free_space, offset_index); - /* - * If we are using the bytes index then all subsequent entries - * in this tree are going to be < bytes, so simply set the max - * extent size and exit the loop. - * - * If we're using the offset index then we need to keep going - * through the rest of the tree. - */W - if (entry->bytes < *bytes) { - *max_extent_size = max(get_max_extent_size(entry), - *max_extent_size); - if (use_bytes_index) - break; - continue; - } - /* make sure the space returned is big enough * to match our requested alignment */
@@ -1975,9 +1967,20 @@ find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, tmp = entry->offset; } + /* + * If we are using the bytes index then all subsequent entries + * in this tree are going to be < bytes, so simply set the max + * extent size and exit the loop. + * + * If we're using the offset index then we need to keep going + * through the rest of the tree. + */ + if (entry->bytes < *bytes + align_off) { *max_extent_size = max(get_max_extent_size(entry), *max_extent_size); + if (use_bytes_index) + break; continue; }
<snip>