Function ext4_mb_mark_free_simple could search order for bit clearing in
O(1) cost while mb_mark_used will search order in O(distance from chunk
order to target order) and introduce unnecessary bit flips.
Consider we have 4 continuous free bits and going to mark bit 0-2 inuse.
initial state of buddy bitmap:
order 2 | 0 |
order 1 | 1 | 1 |
order 0 | 1 | 1 | 1 | 1 |
mark whole chunk inuse
order 2 | 1 |
order 1 | 1 | 1 |
order 0 | 1 | 1 | 1 | 1 |
split chunk to order 1
order 2 | 1 |
order 1 | 0 | 0 |
order 0 | 1 | 1 | 1 | 1 |
set the first bit in order 1 to mark bit 0-1 inuse
set the second bit in order 1 for split
order 2 | 1 |
order 1 | 1 | 1 |
order 0 | 1 | 1 | 1 | 1 |
step 3: split the second bit in order 1 to order 0
order 2 | 1 |
order 1 | 1 | 1 |
order 0 | 1 | 1 | 0 | 0 |
step 4: set the third bit in order 0 to mark bit 2 inuse.
order 2 | 1 |
order 1 | 1 | 1 |
order 0 | 1 | 1 | 1 | 0 |
There are two unnecessary splits and three unnecessary bit flips.
With ext4_mb_mark_free_simple, we will clear the 4th bit in order 0
with O(1) search and no extra bit flip.
The cost estimated by test_mb_mark_used_cost is as following:
Before (three runs of test):
# test_mb_mark_used_cost: costed jiffies 311
# test_mb_mark_used_cost: costed jiffies 304
# test_mb_mark_used_cost: costed jiffies 305
# test_mb_mark_used_cost: costed jiffies 323
# test_mb_mark_used_cost: costed jiffies 317
# test_mb_mark_used_cost: costed jiffies 317
After (three runs of test):
# test_mb_mark_used_cost: costed jiffies 166
# test_mb_mark_used_cost: costed jiffies 152
# test_mb_mark_used_cost: costed jiffies 159
# test_mb_mark_used_cost: costed jiffies 138
# test_mb_mark_used_cost: costed jiffies 149
Signed-off-by: Kemeng Shi <shikemeng@xxxxxxxxxxxxxxx>
---
fs/ext4/mballoc.c | 37 ++++++++++++++++++++-----------------
1 file changed, 20 insertions(+), 17 deletions(-)
diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
index a61fc52956b2..62d468379722 100644
--- a/fs/ext4/mballoc.c
+++ b/fs/ext4/mballoc.c
@@ -2040,13 +2040,12 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
int ord;
int mlen = 0;
int max = 0;
- int cur;
int start = ex->fe_start;
int len = ex->fe_len;
unsigned ret = 0;
int len0 = len;
void *buddy;
- bool split = false;
+ int ord_start, ord_end;
BUG_ON(start + len > (e4b->bd_sb->s_blocksize << 3));
BUG_ON(e4b->bd_group != ex->fe_group);
@@ -2071,16 +2070,12 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
/* let's maintain buddy itself */
while (len) {
- if (!split)
- ord = mb_find_order_for_block(e4b, start);
+ ord = mb_find_order_for_block(e4b, start);
if (((start >> ord) << ord) == start && len >= (1 << ord)) {
/* the whole chunk may be allocated at once! */
mlen = 1 << ord;
- if (!split)
- buddy = mb_find_buddy(e4b, ord, &max);
- else
- split = false;
+ buddy = mb_find_buddy(e4b, ord, &max);
BUG_ON((start >> ord) >= max);
mb_set_bit(start >> ord, buddy);
e4b->bd_info->bb_counters[ord]--;
@@ -2094,20 +2089,28 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
if (ret == 0)
ret = len | (ord << 16);
- /* we have to split large buddy */
BUG_ON(ord <= 0);
buddy = mb_find_buddy(e4b, ord, &max);
mb_set_bit(start >> ord, buddy);
e4b->bd_info->bb_counters[ord]--;
- ord--;
- cur = (start >> ord) & ~1U;
- buddy = mb_find_buddy(e4b, ord, &max);
- mb_clear_bit(cur, buddy);
- mb_clear_bit(cur + 1, buddy);
- e4b->bd_info->bb_counters[ord]++;
- e4b->bd_info->bb_counters[ord]++;
- split = true;
+ ord_start = (start >> ord) << ord;
+ ord_end = ord_start + (1 << ord);
+ if (start > ord_start)
+ ext4_mb_mark_free_simple(e4b->bd_sb, e4b->bd_buddy,
+ ord_start, start - ord_start,
+ e4b->bd_info);
+
+ if (start + len < ord_end) {
+ ext4_mb_mark_free_simple(e4b->bd_sb, e4b->bd_buddy,
+ start + len,
+ ord_end - (start + len),
+ e4b->bd_info);
+ break;
+ }
+
+ len = start + len - ord_end;
+ start = ord_end;
}
mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
--
2.30.0
