| Message ID | ad68fad714efc8ab938ca69af099afd0e1201075.1657004556.git.wqu@suse.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | btrfs: introduce write-intent bitmaps for RAID56 | expand |
On 2022/7/5 15:39, Qu Wenruo wrote: > Signed-off-by: Qu Wenruo <wqu@suse.com> Unfortunately there seems to be corner case not handled properly. If we have a start=37617664, len=196608, and we have an existing entry 0 , bitmap=0x0700000000000000. Then after calling set_bits() with above range, we only got: entry 0 bitmap=0xc700000000000000. Note 0xc = 1100 binary, thus we didn't create a new entry for the remaining 1 bit, and triggered the later WARN_ON_ONCE() for clear_bits. I'll fix the bug in the code and add a selftest case for it. Thanks, Qu > --- > fs/btrfs/write-intent.c | 251 ++++++++++++++++++++++++++++++++++++++++ > fs/btrfs/write-intent.h | 16 +++ > 2 files changed, 267 insertions(+) > > diff --git a/fs/btrfs/write-intent.c b/fs/btrfs/write-intent.c > index a43c6d94f8cd..0650f168db79 100644 > --- a/fs/btrfs/write-intent.c > +++ b/fs/btrfs/write-intent.c > @@ -259,6 +259,257 @@ static int write_intent_init(struct btrfs_fs_info *fs_info) > return 0; > } > > +static struct write_intent_entry *write_intent_entry_nr( > + struct write_intent_ctrl *ctrl, int nr) > +{ > + > + ASSERT(nr < WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); > + return (page_address(ctrl->page) + > + sizeof(struct write_intent_super) + > + nr * sizeof(struct write_intent_entry)); > +} > + > +/* > + * Return <0 if the bytenr is before the given entry. > + * Return 0 if the bytenr is inside the given entry. > + * Return >0 if the bytenr is after the given entry. > + */ > +static int compare_bytenr_to_range(u64 bytenr, u64 start, u32 len) > +{ > + if (bytenr < start) > + return -1; > + if (start <= bytenr && bytenr < start + len) > + return 0; > + return 1; > +} > + > +/* > + * Move all non-empty entries starting from @nr, to the right, and make room > + * for @nr_new entries. > + * Those new entries will be all zero filled. > + * > + * Caller should ensure we have enough room for @nr_new new entries. > + */ > +static void move_entries_right(struct write_intent_ctrl *ctrl, int nr, > + int nr_new) > +{ > + struct write_intent_super *wis = page_address(ctrl->page); > + int move_size; > + > + ASSERT(nr_new > 0); > + ASSERT(wi_super_nr_entries(wis) + nr_new <= > + WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); > + > + move_size = (wi_super_nr_entries(wis) - nr) * > + sizeof(struct write_intent_entry); > + > + memmove(write_intent_entry_nr(ctrl, nr + nr_new), > + write_intent_entry_nr(ctrl, nr), move_size); > + memset(write_intent_entry_nr(ctrl, nr), 0, > + nr_new * sizeof(struct write_intent_entry)); > + wi_set_super_nr_entries(wis, wi_super_nr_entries(wis) + nr_new); > +} > + > +static void set_bits_in_one_entry(struct write_intent_ctrl *ctrl, > + struct write_intent_entry *entry, > + u64 bytenr, u32 len) > +{ > + const u64 entry_start = wi_entry_bytenr(entry); > + const u32 entry_len = write_intent_entry_size(ctrl); > + unsigned long bitmaps[WRITE_INTENT_BITS_PER_ENTRY / BITS_PER_LONG]; > + > + wie_get_bitmap(entry, bitmaps); > + > + ASSERT(entry_start <= bytenr && bytenr + len <= entry_start + entry_len); > + bitmap_set(bitmaps, (bytenr - entry_start) / ctrl->blocksize, > + len / ctrl->blocksize); > + wie_set_bitmap(entry, bitmaps); > +} > + > +/* > + * Insert new entries for the range [@bytenr, @bytenr + @len) at slot @nr > + * and fill the new entries with proper bytenr and bitmaps. > + */ > +static void insert_new_entries(struct write_intent_ctrl *ctrl, int nr, > + u64 bytenr, u32 len) > +{ > + const u32 entry_size = write_intent_entry_size(ctrl); > + u64 entry_start; > + u64 new_start = round_down(bytenr, entry_size); > + u64 new_end; > + int nr_new_entries; > + u64 cur; > + > + if (nr >= wi_super_nr_entries(page_address(ctrl->page)) || > + nr >= WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES) > + entry_start = U64_MAX; > + else > + entry_start = wi_entry_bytenr(write_intent_entry_nr(ctrl, nr)); > + > + ASSERT(bytenr < entry_start); > + > + new_end = min(entry_start, round_up(bytenr + len, entry_size)); > + nr_new_entries = (new_end - new_start) / entry_size; > + > + if (nr_new_entries == 0) > + return; > + > + move_entries_right(ctrl, nr, nr_new_entries); > + > + for (cur = new_start; cur < new_end; cur += entry_size, nr++) { > + struct write_intent_entry *entry = > + write_intent_entry_nr(ctrl, nr); > + u64 range_start = max(cur, bytenr); > + u64 range_len = min(cur + entry_size, bytenr + len) - > + range_start; > + > + /* Fill the bytenr into the new empty entries.*/ > + wi_set_entry_bytenr(entry, cur); > + > + /* And set the bitmap. */ > + set_bits_in_one_entry(ctrl, entry, range_start, range_len); > + } > +} > + > +/* > + * This should be only called when we have enough room in the bitmaps, and hold > + * the wi_ctrl->lock. > + */ > +static void write_intent_set_bits(struct write_intent_ctrl *ctrl, u64 bytenr, > + u32 len) > +{ > + struct write_intent_super *wis = page_address(ctrl->page); > + const u32 entry_size = write_intent_entry_size(ctrl); > + int i; > + u64 nr_entries = wi_super_nr_entries(wis); > + u64 cur_bytenr; > + > + /* > + * Currently we only accept full stripe length, which should be > + * aligned to 64KiB. > + */ > + ASSERT(IS_ALIGNED(len, BTRFS_STRIPE_LEN)); > + > + /* > + * We should have room to contain the worst case scenario, in which we > + * need to create one or more new entry. > + */ > + ASSERT(nr_entries + bytes_to_entries(bytenr, len, BTRFS_STRIPE_LEN) <= > + WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); > + > + /* Empty bitmap, just insert new ones. */ > + if (wi_super_nr_entries(wis) == 0) > + return insert_new_entries(ctrl, 0, bytenr, len); > + > + /* Go through entries to find the one covering our range. */ > + for (i = 0, cur_bytenr = bytenr; > + i < wi_super_nr_entries(wis) && cur_bytenr < bytenr + len; i++) { > + struct write_intent_entry *entry = write_intent_entry_nr(ctrl, i); > + u64 entry_start = wi_entry_bytenr(entry); > + u64 entry_end = entry_start + entry_size; > + > + /* > + * |<-- entry -->| > + * |<-- bytenr/len -->| > + * > + * Or > + * > + * |<-- entry -->| > + * |<-- bytenr/len -->| > + * > + * Or > + * > + * |<-- entry -->| > + * |<-- bytenr/len -->| > + * > + * We need to insert one or more new entries for the range not > + * covered by the existing entry. > + */ > + if (compare_bytenr_to_range(cur_bytenr, entry_start, > + entry_size) < 0) { > + u64 new_range_end; > + > + new_range_end = min(entry_start, bytenr + len); > + insert_new_entries(ctrl, i, cur_bytenr, > + new_range_end - cur_bytenr); > + > + cur_bytenr = new_range_end; > + continue; > + } > + /* > + * |<-- entry -->| > + * |<-- bytenr/len -->| > + * > + * Or > + * > + * |<-------- entry ------->| > + * |<- bytenr/len ->| > + * > + * In this case, we just set the bitmap in the current entry, and > + * advance @cur_bytenr to the end of the existing entry. > + * By this, we either go check the range against the next entry, > + * or we finish our current range. > + */ > + if (compare_bytenr_to_range(cur_bytenr, entry_start, > + entry_size) == 0) { > + u64 range_end = min(entry_end, bytenr + len); > + > + set_bits_in_one_entry(ctrl, entry, cur_bytenr, > + range_end - cur_bytenr); > + cur_bytenr = range_end; > + continue; > + } > + > + /* > + * (A) > + * |<-- entry -->| |<--- next -->| > + * |<-- bytenr/len -->| > + * > + * OR > + * > + * (B) > + * |<-- entry -->| |<--- next -->| > + * |<-- bytenr/len -->| > + * > + * OR > + * > + * (C) > + * |<-- entry -->|<--- next -->| > + * |<-- bytenr/len -->| > + */ > + if (i < wi_super_nr_entries(wis) - 1) { > + struct write_intent_entry *next = > + write_intent_entry_nr(ctrl, i + 1); > + u64 next_start = wi_entry_bytenr(next); > + > + > + /* Case (A) and (B), insert the new entries. */ > + if (cur_bytenr >= entry_end && cur_bytenr < next_start) { > + insert_new_entries(ctrl, i + 1, cur_bytenr, > + bytenr + len - cur_bytenr); > + cur_bytenr = next_start; > + continue; > + } > + > + /* Case (C), just skip to next item */ > + continue; > + } > + > + /* > + * The remaining case is, @entry is already the last one. > + * > + * |<-- entry -->| > + * |<-- bytenr/len -->| > + * > + * We're beyond the last entry. Need to insert new entries. > + */ > + insert_new_entries(ctrl, i + 1, cur_bytenr, > + bytenr + len - cur_bytenr); > + > + cur_bytenr = bytenr + len; > + } > +} > + > int btrfs_write_intent_init(struct btrfs_fs_info *fs_info) > { > struct btrfs_device *highest_dev = NULL; > diff --git a/fs/btrfs/write-intent.h b/fs/btrfs/write-intent.h > index 797e57aef0e1..d8f4d285512c 100644 > --- a/fs/btrfs/write-intent.h > +++ b/fs/btrfs/write-intent.h > @@ -106,6 +106,15 @@ struct write_intent_entry { > /* The number of bits we can have in one entry. */ > #define WRITE_INTENT_BITS_PER_ENTRY (64) > > +static inline u32 bytes_to_entries(u64 start, u32 length, u32 blocksize) > +{ > + u32 entry_len = blocksize * WRITE_INTENT_BITS_PER_ENTRY; > + u64 entry_start = round_down(start, entry_len); > + u64 entry_end = round_up(start + length, entry_len); > + > + return DIV_ROUND_UP((u32)(entry_end - entry_start), entry_len); > +} > + > /* In-memory write-intent control structure. */ > struct write_intent_ctrl { > /* For the write_intent super and entries. */ > @@ -189,6 +198,13 @@ WRITE_INTENT_SETGET_FUNCS(super_csum_type, struct write_intent_super, > csum_type, 16); > WRITE_INTENT_SETGET_FUNCS(entry_bytenr, struct write_intent_entry, bytenr, 64); > > +static inline u32 write_intent_entry_size(struct write_intent_ctrl *ctrl) > +{ > + struct write_intent_super *wis = page_address(ctrl->page); > + > + return wi_super_blocksize(wis) * WRITE_INTENT_BITS_PER_ENTRY; > +} > + > static inline void wie_get_bitmap(struct write_intent_entry *entry, > unsigned long *bitmap) > {
On 2022/7/6 14:16, Qu Wenruo wrote: > > > On 2022/7/5 15:39, Qu Wenruo wrote: >> Signed-off-by: Qu Wenruo <wqu@suse.com> > > Unfortunately there seems to be corner case not handled properly. > > If we have a start=37617664, len=196608, and we have an existing entry 0 > , bitmap=0x0700000000000000. > > Then after calling set_bits() with above range, we only got: > entry 0 bitmap=0xc700000000000000. > > Note 0xc = 1100 binary, thus we didn't create a new entry for the > remaining 1 bit, and triggered the later WARN_ON_ONCE() for clear_bits. > > I'll fix the bug in the code and add a selftest case for it. > > Thanks, > Qu > >> --- >> fs/btrfs/write-intent.c | 251 ++++++++++++++++++++++++++++++++++++++++ >> fs/btrfs/write-intent.h | 16 +++ >> 2 files changed, 267 insertions(+) >> >> diff --git a/fs/btrfs/write-intent.c b/fs/btrfs/write-intent.c >> index a43c6d94f8cd..0650f168db79 100644 >> --- a/fs/btrfs/write-intent.c >> +++ b/fs/btrfs/write-intent.c >> @@ -259,6 +259,257 @@ static int write_intent_init(struct >> btrfs_fs_info *fs_info) >> return 0; >> } >> +static struct write_intent_entry *write_intent_entry_nr( >> + struct write_intent_ctrl *ctrl, int nr) >> +{ >> + >> + ASSERT(nr < WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); >> + return (page_address(ctrl->page) + >> + sizeof(struct write_intent_super) + >> + nr * sizeof(struct write_intent_entry)); >> +} >> + >> +/* >> + * Return <0 if the bytenr is before the given entry. >> + * Return 0 if the bytenr is inside the given entry. >> + * Return >0 if the bytenr is after the given entry. >> + */ >> +static int compare_bytenr_to_range(u64 bytenr, u64 start, u32 len) >> +{ >> + if (bytenr < start) >> + return -1; >> + if (start <= bytenr && bytenr < start + len) >> + return 0; >> + return 1; >> +} >> + >> +/* >> + * Move all non-empty entries starting from @nr, to the right, and >> make room >> + * for @nr_new entries. >> + * Those new entries will be all zero filled. >> + * >> + * Caller should ensure we have enough room for @nr_new new entries. >> + */ >> +static void move_entries_right(struct write_intent_ctrl *ctrl, int nr, >> + int nr_new) >> +{ >> + struct write_intent_super *wis = page_address(ctrl->page); >> + int move_size; >> + >> + ASSERT(nr_new > 0); >> + ASSERT(wi_super_nr_entries(wis) + nr_new <= >> + WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); >> + >> + move_size = (wi_super_nr_entries(wis) - nr) * >> + sizeof(struct write_intent_entry); >> + >> + memmove(write_intent_entry_nr(ctrl, nr + nr_new), >> + write_intent_entry_nr(ctrl, nr), move_size); >> + memset(write_intent_entry_nr(ctrl, nr), 0, >> + nr_new * sizeof(struct write_intent_entry)); >> + wi_set_super_nr_entries(wis, wi_super_nr_entries(wis) + nr_new); >> +} >> + >> +static void set_bits_in_one_entry(struct write_intent_ctrl *ctrl, >> + struct write_intent_entry *entry, >> + u64 bytenr, u32 len) >> +{ >> + const u64 entry_start = wi_entry_bytenr(entry); >> + const u32 entry_len = write_intent_entry_size(ctrl); >> + unsigned long bitmaps[WRITE_INTENT_BITS_PER_ENTRY / BITS_PER_LONG]; >> + >> + wie_get_bitmap(entry, bitmaps); >> + >> + ASSERT(entry_start <= bytenr && bytenr + len <= entry_start + >> entry_len); >> + bitmap_set(bitmaps, (bytenr - entry_start) / ctrl->blocksize, >> + len / ctrl->blocksize); >> + wie_set_bitmap(entry, bitmaps); >> +} >> + >> +/* >> + * Insert new entries for the range [@bytenr, @bytenr + @len) at slot >> @nr >> + * and fill the new entries with proper bytenr and bitmaps. >> + */ >> +static void insert_new_entries(struct write_intent_ctrl *ctrl, int nr, >> + u64 bytenr, u32 len) >> +{ >> + const u32 entry_size = write_intent_entry_size(ctrl); >> + u64 entry_start; >> + u64 new_start = round_down(bytenr, entry_size); >> + u64 new_end; >> + int nr_new_entries; >> + u64 cur; >> + >> + if (nr >= wi_super_nr_entries(page_address(ctrl->page)) || >> + nr >= WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES) >> + entry_start = U64_MAX; >> + else >> + entry_start = wi_entry_bytenr(write_intent_entry_nr(ctrl, nr)); >> + >> + ASSERT(bytenr < entry_start); >> + >> + new_end = min(entry_start, round_up(bytenr + len, entry_size)); >> + nr_new_entries = (new_end - new_start) / entry_size; >> + >> + if (nr_new_entries == 0) >> + return; >> + >> + move_entries_right(ctrl, nr, nr_new_entries); >> + >> + for (cur = new_start; cur < new_end; cur += entry_size, nr++) { >> + struct write_intent_entry *entry = >> + write_intent_entry_nr(ctrl, nr); >> + u64 range_start = max(cur, bytenr); >> + u64 range_len = min(cur + entry_size, bytenr + len) - >> + range_start; >> + >> + /* Fill the bytenr into the new empty entries.*/ >> + wi_set_entry_bytenr(entry, cur); >> + >> + /* And set the bitmap. */ >> + set_bits_in_one_entry(ctrl, entry, range_start, range_len); >> + } >> +} >> + >> +/* >> + * This should be only called when we have enough room in the >> bitmaps, and hold >> + * the wi_ctrl->lock. >> + */ >> +static void write_intent_set_bits(struct write_intent_ctrl *ctrl, u64 >> bytenr, >> + u32 len) >> +{ >> + struct write_intent_super *wis = page_address(ctrl->page); >> + const u32 entry_size = write_intent_entry_size(ctrl); >> + int i; >> + u64 nr_entries = wi_super_nr_entries(wis); >> + u64 cur_bytenr; >> + >> + /* >> + * Currently we only accept full stripe length, which should be >> + * aligned to 64KiB. >> + */ >> + ASSERT(IS_ALIGNED(len, BTRFS_STRIPE_LEN)); >> + >> + /* >> + * We should have room to contain the worst case scenario, in >> which we >> + * need to create one or more new entry. >> + */ >> + ASSERT(nr_entries + bytes_to_entries(bytenr, len, >> BTRFS_STRIPE_LEN) <= >> + WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); >> + >> + /* Empty bitmap, just insert new ones. */ >> + if (wi_super_nr_entries(wis) == 0) >> + return insert_new_entries(ctrl, 0, bytenr, len); >> + >> + /* Go through entries to find the one covering our range. */ >> + for (i = 0, cur_bytenr = bytenr; >> + i < wi_super_nr_entries(wis) && cur_bytenr < bytenr + len; >> i++) { >> + struct write_intent_entry *entry = >> write_intent_entry_nr(ctrl, i); >> + u64 entry_start = wi_entry_bytenr(entry); >> + u64 entry_end = entry_start + entry_size; >> + >> + /* >> + * |<-- entry -->| >> + * |<-- bytenr/len -->| >> + * >> + * Or >> + * >> + * |<-- entry -->| >> + * |<-- bytenr/len -->| >> + * >> + * Or >> + * >> + * |<-- entry -->| >> + * |<-- bytenr/len -->| >> + * >> + * We need to insert one or more new entries for the range not >> + * covered by the existing entry. >> + */ >> + if (compare_bytenr_to_range(cur_bytenr, entry_start, >> + entry_size) < 0) { >> + u64 new_range_end; >> + >> + new_range_end = min(entry_start, bytenr + len); >> + insert_new_entries(ctrl, i, cur_bytenr, >> + new_range_end - cur_bytenr); >> + >> + cur_bytenr = new_range_end; >> + continue; >> + } >> + /* >> + * |<-- entry -->| >> + * |<-- bytenr/len -->| >> + * >> + * Or >> + * >> + * |<-------- entry ------->| >> + * |<- bytenr/len ->| >> + * >> + * In this case, we just set the bitmap in the current entry, >> and >> + * advance @cur_bytenr to the end of the existing entry. >> + * By this, we either go check the range against the next entry, >> + * or we finish our current range. >> + */ >> + if (compare_bytenr_to_range(cur_bytenr, entry_start, >> + entry_size) == 0) { >> + u64 range_end = min(entry_end, bytenr + len); >> + >> + set_bits_in_one_entry(ctrl, entry, cur_bytenr, >> + range_end - cur_bytenr); >> + cur_bytenr = range_end; >> + continue; This is where the problem happens. If this entry is also the last entry, and we still have something left, then we're screwed as we will no longer insert new entries for it, leaving some bits not properly set. Will rework the big for loop to make the last entry insert consistent. Thanks, Qu >> + } >> + >> + /* >> + * (A) >> + * |<-- entry -->| |<--- next -->| >> + * |<-- bytenr/len -->| >> + * >> + * OR >> + * >> + * (B) >> + * |<-- entry -->| |<--- next -->| >> + * |<-- bytenr/len -->| >> + * >> + * OR >> + * >> + * (C) >> + * |<-- entry -->|<--- next -->| >> + * |<-- bytenr/len -->| >> + */ >> + if (i < wi_super_nr_entries(wis) - 1) { >> + struct write_intent_entry *next = >> + write_intent_entry_nr(ctrl, i + 1); >> + u64 next_start = wi_entry_bytenr(next); >> + >> + >> + /* Case (A) and (B), insert the new entries. */ >> + if (cur_bytenr >= entry_end && cur_bytenr < next_start) { >> + insert_new_entries(ctrl, i + 1, cur_bytenr, >> + bytenr + len - cur_bytenr); >> + cur_bytenr = next_start; >> + continue; >> + } >> + >> + /* Case (C), just skip to next item */ >> + continue; >> + } >> + >> + /* >> + * The remaining case is, @entry is already the last one. >> + * >> + * |<-- entry -->| >> + * |<-- bytenr/len -->| >> + * >> + * We're beyond the last entry. Need to insert new entries. >> + */ >> + insert_new_entries(ctrl, i + 1, cur_bytenr, >> + bytenr + len - cur_bytenr); >> + >> + cur_bytenr = bytenr + len; >> + } >> +} >> + >> int btrfs_write_intent_init(struct btrfs_fs_info *fs_info) >> { >> struct btrfs_device *highest_dev = NULL; >> diff --git a/fs/btrfs/write-intent.h b/fs/btrfs/write-intent.h >> index 797e57aef0e1..d8f4d285512c 100644 >> --- a/fs/btrfs/write-intent.h >> +++ b/fs/btrfs/write-intent.h >> @@ -106,6 +106,15 @@ struct write_intent_entry { >> /* The number of bits we can have in one entry. */ >> #define WRITE_INTENT_BITS_PER_ENTRY (64) >> +static inline u32 bytes_to_entries(u64 start, u32 length, u32 blocksize) >> +{ >> + u32 entry_len = blocksize * WRITE_INTENT_BITS_PER_ENTRY; >> + u64 entry_start = round_down(start, entry_len); >> + u64 entry_end = round_up(start + length, entry_len); >> + >> + return DIV_ROUND_UP((u32)(entry_end - entry_start), entry_len); >> +} >> + >> /* In-memory write-intent control structure. */ >> struct write_intent_ctrl { >> /* For the write_intent super and entries. */ >> @@ -189,6 +198,13 @@ WRITE_INTENT_SETGET_FUNCS(super_csum_type, struct >> write_intent_super, >> csum_type, 16); >> WRITE_INTENT_SETGET_FUNCS(entry_bytenr, struct write_intent_entry, >> bytenr, 64); >> +static inline u32 write_intent_entry_size(struct write_intent_ctrl >> *ctrl) >> +{ >> + struct write_intent_super *wis = page_address(ctrl->page); >> + >> + return wi_super_blocksize(wis) * WRITE_INTENT_BITS_PER_ENTRY; >> +} >> + >> static inline void wie_get_bitmap(struct write_intent_entry *entry, >> unsigned long *bitmap) >> {
diff --git a/fs/btrfs/write-intent.c b/fs/btrfs/write-intent.c index a43c6d94f8cd..0650f168db79 100644 --- a/fs/btrfs/write-intent.c +++ b/fs/btrfs/write-intent.c @@ -259,6 +259,257 @@ static int write_intent_init(struct btrfs_fs_info *fs_info) return 0; } +static struct write_intent_entry *write_intent_entry_nr( + struct write_intent_ctrl *ctrl, int nr) +{ + + ASSERT(nr < WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); + return (page_address(ctrl->page) + + sizeof(struct write_intent_super) + + nr * sizeof(struct write_intent_entry)); +} + +/* + * Return <0 if the bytenr is before the given entry. + * Return 0 if the bytenr is inside the given entry. + * Return >0 if the bytenr is after the given entry. + */ +static int compare_bytenr_to_range(u64 bytenr, u64 start, u32 len) +{ + if (bytenr < start) + return -1; + if (start <= bytenr && bytenr < start + len) + return 0; + return 1; +} + +/* + * Move all non-empty entries starting from @nr, to the right, and make room + * for @nr_new entries. + * Those new entries will be all zero filled. + * + * Caller should ensure we have enough room for @nr_new new entries. + */ +static void move_entries_right(struct write_intent_ctrl *ctrl, int nr, + int nr_new) +{ + struct write_intent_super *wis = page_address(ctrl->page); + int move_size; + + ASSERT(nr_new > 0); + ASSERT(wi_super_nr_entries(wis) + nr_new <= + WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); + + move_size = (wi_super_nr_entries(wis) - nr) * + sizeof(struct write_intent_entry); + + memmove(write_intent_entry_nr(ctrl, nr + nr_new), + write_intent_entry_nr(ctrl, nr), move_size); + memset(write_intent_entry_nr(ctrl, nr), 0, + nr_new * sizeof(struct write_intent_entry)); + wi_set_super_nr_entries(wis, wi_super_nr_entries(wis) + nr_new); +} + +static void set_bits_in_one_entry(struct write_intent_ctrl *ctrl, + struct write_intent_entry *entry, + u64 bytenr, u32 len) +{ + const u64 entry_start = wi_entry_bytenr(entry); + const u32 entry_len = write_intent_entry_size(ctrl); + unsigned long bitmaps[WRITE_INTENT_BITS_PER_ENTRY / BITS_PER_LONG]; + + wie_get_bitmap(entry, bitmaps); + + ASSERT(entry_start <= bytenr && bytenr + len <= entry_start + entry_len); + bitmap_set(bitmaps, (bytenr - entry_start) / ctrl->blocksize, + len / ctrl->blocksize); + wie_set_bitmap(entry, bitmaps); +} + +/* + * Insert new entries for the range [@bytenr, @bytenr + @len) at slot @nr + * and fill the new entries with proper bytenr and bitmaps. + */ +static void insert_new_entries(struct write_intent_ctrl *ctrl, int nr, + u64 bytenr, u32 len) +{ + const u32 entry_size = write_intent_entry_size(ctrl); + u64 entry_start; + u64 new_start = round_down(bytenr, entry_size); + u64 new_end; + int nr_new_entries; + u64 cur; + + if (nr >= wi_super_nr_entries(page_address(ctrl->page)) || + nr >= WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES) + entry_start = U64_MAX; + else + entry_start = wi_entry_bytenr(write_intent_entry_nr(ctrl, nr)); + + ASSERT(bytenr < entry_start); + + new_end = min(entry_start, round_up(bytenr + len, entry_size)); + nr_new_entries = (new_end - new_start) / entry_size; + + if (nr_new_entries == 0) + return; + + move_entries_right(ctrl, nr, nr_new_entries); + + for (cur = new_start; cur < new_end; cur += entry_size, nr++) { + struct write_intent_entry *entry = + write_intent_entry_nr(ctrl, nr); + u64 range_start = max(cur, bytenr); + u64 range_len = min(cur + entry_size, bytenr + len) - + range_start; + + /* Fill the bytenr into the new empty entries.*/ + wi_set_entry_bytenr(entry, cur); + + /* And set the bitmap. */ + set_bits_in_one_entry(ctrl, entry, range_start, range_len); + } +} + +/* + * This should be only called when we have enough room in the bitmaps, and hold + * the wi_ctrl->lock. + */ +static void write_intent_set_bits(struct write_intent_ctrl *ctrl, u64 bytenr, + u32 len) +{ + struct write_intent_super *wis = page_address(ctrl->page); + const u32 entry_size = write_intent_entry_size(ctrl); + int i; + u64 nr_entries = wi_super_nr_entries(wis); + u64 cur_bytenr; + + /* + * Currently we only accept full stripe length, which should be + * aligned to 64KiB. + */ + ASSERT(IS_ALIGNED(len, BTRFS_STRIPE_LEN)); + + /* + * We should have room to contain the worst case scenario, in which we + * need to create one or more new entry. + */ + ASSERT(nr_entries + bytes_to_entries(bytenr, len, BTRFS_STRIPE_LEN) <= + WRITE_INTENT_INTERNAL_BITMAPS_MAX_ENTRIES); + + /* Empty bitmap, just insert new ones. */ + if (wi_super_nr_entries(wis) == 0) + return insert_new_entries(ctrl, 0, bytenr, len); + + /* Go through entries to find the one covering our range. */ + for (i = 0, cur_bytenr = bytenr; + i < wi_super_nr_entries(wis) && cur_bytenr < bytenr + len; i++) { + struct write_intent_entry *entry = write_intent_entry_nr(ctrl, i); + u64 entry_start = wi_entry_bytenr(entry); + u64 entry_end = entry_start + entry_size; + + /* + * |<-- entry -->| + * |<-- bytenr/len -->| + * + * Or + * + * |<-- entry -->| + * |<-- bytenr/len -->| + * + * Or + * + * |<-- entry -->| + * |<-- bytenr/len -->| + * + * We need to insert one or more new entries for the range not + * covered by the existing entry. + */ + if (compare_bytenr_to_range(cur_bytenr, entry_start, + entry_size) < 0) { + u64 new_range_end; + + new_range_end = min(entry_start, bytenr + len); + insert_new_entries(ctrl, i, cur_bytenr, + new_range_end - cur_bytenr); + + cur_bytenr = new_range_end; + continue; + } + /* + * |<-- entry -->| + * |<-- bytenr/len -->| + * + * Or + * + * |<-------- entry ------->| + * |<- bytenr/len ->| + * + * In this case, we just set the bitmap in the current entry, and + * advance @cur_bytenr to the end of the existing entry. + * By this, we either go check the range against the next entry, + * or we finish our current range. + */ + if (compare_bytenr_to_range(cur_bytenr, entry_start, + entry_size) == 0) { + u64 range_end = min(entry_end, bytenr + len); + + set_bits_in_one_entry(ctrl, entry, cur_bytenr, + range_end - cur_bytenr); + cur_bytenr = range_end; + continue; + } + + /* + * (A) + * |<-- entry -->| |<--- next -->| + * |<-- bytenr/len -->| + * + * OR + * + * (B) + * |<-- entry -->| |<--- next -->| + * |<-- bytenr/len -->| + * + * OR + * + * (C) + * |<-- entry -->|<--- next -->| + * |<-- bytenr/len -->| + */ + if (i < wi_super_nr_entries(wis) - 1) { + struct write_intent_entry *next = + write_intent_entry_nr(ctrl, i + 1); + u64 next_start = wi_entry_bytenr(next); + + + /* Case (A) and (B), insert the new entries. */ + if (cur_bytenr >= entry_end && cur_bytenr < next_start) { + insert_new_entries(ctrl, i + 1, cur_bytenr, + bytenr + len - cur_bytenr); + cur_bytenr = next_start; + continue; + } + + /* Case (C), just skip to next item */ + continue; + } + + /* + * The remaining case is, @entry is already the last one. + * + * |<-- entry -->| + * |<-- bytenr/len -->| + * + * We're beyond the last entry. Need to insert new entries. + */ + insert_new_entries(ctrl, i + 1, cur_bytenr, + bytenr + len - cur_bytenr); + + cur_bytenr = bytenr + len; + } +} + int btrfs_write_intent_init(struct btrfs_fs_info *fs_info) { struct btrfs_device *highest_dev = NULL; diff --git a/fs/btrfs/write-intent.h b/fs/btrfs/write-intent.h index 797e57aef0e1..d8f4d285512c 100644 --- a/fs/btrfs/write-intent.h +++ b/fs/btrfs/write-intent.h @@ -106,6 +106,15 @@ struct write_intent_entry { /* The number of bits we can have in one entry. */ #define WRITE_INTENT_BITS_PER_ENTRY (64) +static inline u32 bytes_to_entries(u64 start, u32 length, u32 blocksize) +{ + u32 entry_len = blocksize * WRITE_INTENT_BITS_PER_ENTRY; + u64 entry_start = round_down(start, entry_len); + u64 entry_end = round_up(start + length, entry_len); + + return DIV_ROUND_UP((u32)(entry_end - entry_start), entry_len); +} + /* In-memory write-intent control structure. */ struct write_intent_ctrl { /* For the write_intent super and entries. */ @@ -189,6 +198,13 @@ WRITE_INTENT_SETGET_FUNCS(super_csum_type, struct write_intent_super, csum_type, 16); WRITE_INTENT_SETGET_FUNCS(entry_bytenr, struct write_intent_entry, bytenr, 64); +static inline u32 write_intent_entry_size(struct write_intent_ctrl *ctrl) +{ + struct write_intent_super *wis = page_address(ctrl->page); + + return wi_super_blocksize(wis) * WRITE_INTENT_BITS_PER_ENTRY; +} + static inline void wie_get_bitmap(struct write_intent_entry *entry, unsigned long *bitmap) {
Signed-off-by: Qu Wenruo <wqu@suse.com> --- fs/btrfs/write-intent.c | 251 ++++++++++++++++++++++++++++++++++++++++ fs/btrfs/write-intent.h | 16 +++ 2 files changed, 267 insertions(+)