* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-09 20:28 ` [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning Harshad Shirwadkar
@ 2021-02-10 9:00 ` Dan Carpenter
2021-02-11 7:43 ` Alexey Lyashkov
` (4 subsequent siblings)
5 siblings, 0 replies; 17+ messages in thread
From: Dan Carpenter @ 2021-02-10 9:00 UTC (permalink / raw)
To: kbuild
[-- Attachment #1: Type: text/plain, Size: 6768 bytes --]
Hi Harshad,
url: https://github.com/0day-ci/linux/commits/Harshad-Shirwadkar/ext4-drop-s_mb_bal_lock-and-convert-protected-fields-to-atomic/20210210-054647
base: https://git.kernel.org/pub/scm/linux/kernel/git/tytso/ext4.git dev
config: s390-randconfig-m031-20210209 (attached as .config)
compiler: s390-linux-gcc (GCC) 9.3.0
If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>
Reported-by: Dan Carpenter <dan.carpenter@oracle.com>
New smatch warnings:
fs/ext4/mballoc.c:930 ext4_mb_choose_next_group_cr1() error: uninitialized symbol 'avg_fragment_size'.
vim +/avg_fragment_size +930 fs/ext4/mballoc.c
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 878 static int ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac,
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 879 int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 880 {
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 881 struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 882 int avg_fragment_size, best_so_far;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 883 struct rb_node *node, *found;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 884 struct ext4_group_info *grp;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 885
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 886 /*
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 887 * If there is contention on the lock, instead of waiting for the lock
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 888 * to become available, just continue searching lineraly. We'll resume
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 889 * our rb tree search later starting at ac->ac_last_optimal_group.
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 890 */
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 891 if (!read_trylock(&sbi->s_mb_rb_lock))
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 892 return 1;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 893
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 894 if (ac->ac_flags & EXT4_MB_CR1_OPTIMIZED) {
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 895 /* We have found something at CR 1 in the past */
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 896 grp = ext4_get_group_info(ac->ac_sb, ac->ac_last_optimal_group);
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 897 for (found = rb_next(&grp->bb_avg_fragment_size_rb); found != NULL;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 898 found = rb_next(found)) {
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 899 grp = rb_entry(found, struct ext4_group_info,
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 900 bb_avg_fragment_size_rb);
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 901 /*
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 902 * Perform this check without locking, we'll lock later
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 903 * to confirm.
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 904 */
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 905 if (likely(ext4_mb_good_group(ac, grp->bb_group, 1)))
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 906 break;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 907 }
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 908
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 909 goto done;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 910 }
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 911
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 912 node = sbi->s_mb_avg_fragment_size_root.rb_node;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 913 best_so_far = 0;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 914 found = NULL;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 915
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 916 while (node) {
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 917 grp = rb_entry(node, struct ext4_group_info,
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 918 bb_avg_fragment_size_rb);
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 919 /*
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 920 * Perform this check without locking, we'll lock later to confirm.
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 921 */
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 922 if (ext4_mb_good_group(ac, grp->bb_group, 1)) {
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 923 avg_fragment_size = grp->bb_fragments ?
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 924 grp->bb_free / grp->bb_fragments : 0;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 925 if (!best_so_far || avg_fragment_size < best_so_far) {
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 926 best_so_far = avg_fragment_size;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 927 found = node;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 928 }
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 929 }
avg_fragment_size not initialized on else path.
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 @930 if (avg_fragment_size > ac->ac_g_ex.fe_len)
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 931 node = node->rb_right;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 932 else
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 933 node = node->rb_left;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 934 }
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 935
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 936 done:
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 937 if (found) {
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 938 grp = rb_entry(found, struct ext4_group_info,
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 939 bb_avg_fragment_size_rb);
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 940 *group = grp->bb_group;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 941 ac->ac_flags |= EXT4_MB_CR1_OPTIMIZED;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 942 } else {
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 943 *new_cr = 2;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 944 }
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 945
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 946 read_unlock(&sbi->s_mb_rb_lock);
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 947 ac->ac_last_optimal_group = *group;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 948 return 0;
ef4eebad9c018a Harshad Shirwadkar 2021-02-09 949 }
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
_______________________________________________
kbuild mailing list -- kbuild(a)lists.01.org
To unsubscribe send an email to kbuild-leave(a)lists.01.org
[-- Attachment #2: config.gz --]
[-- Type: application/gzip, Size: 28871 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-09 20:28 ` [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning Harshad Shirwadkar
2021-02-10 9:00 ` Dan Carpenter
@ 2021-02-11 7:43 ` Alexey Lyashkov
2021-02-11 7:53 ` Alex Zhuravlev
2021-02-11 10:30 ` Andreas Dilger
` (3 subsequent siblings)
5 siblings, 1 reply; 17+ messages in thread
From: Alexey Lyashkov @ 2021-02-11 7:43 UTC (permalink / raw)
To: Harshad Shirwadkar
Cc: linux-ext4, tytso, bzzz, artem.blagodarenko, sihara, adilger
Hi Harshad,
I glad you look into this complex code. I have one note about groups scanning a specially with raid devices and cr0 loop.
Once we have enough free space, cr 0 loop can found an unaligned for the stripe fragment.
in case raid devices, cr1 don’t produce an average size check - just find an aligned chunk.
So for raid devices CR 0 is useless, and CR1 don’t provide a good results.
Can you look to this problem also ?
Alex
> 9 февр. 2021 г., в 23:28, Harshad Shirwadkar <harshadshirwadkar@gmail.com> написал(а):
>
> Instead of traversing through groups linearly, scan groups in specific
> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
> largest free order >= the order of the request. So, with this patch,
> we maintain lists for each possible order and insert each group into a
> list based on the largest free order in its buddy bitmap. During cr 0
> allocation, we traverse these lists in the increasing order of largest
> free orders. This allows us to find a group with the best available cr
> 0 match in constant time. If nothing can be found, we fallback to cr 1
> immediately.
>
> At CR1, the story is slightly different. We want to traverse in the
> order of increasing average fragment size. For CR1, we maintain a rb
> tree of groupinfos which is sorted by average fragment size. Instead
> of traversing linearly, at CR1, we traverse in the order of increasing
> average fragment size, starting at the most optimal group. This brings
> down cr 1 search complexity to log(num groups).
>
> For cr >= 2, we just perform the linear search as before. Also, in
> case of lock contention, we intermittently fallback to linear search
> even in CR 0 and CR 1 cases. This allows us to proceed during the
> allocation path even in case of high contention.
>
> There is an opportunity to do optimization at CR2 too. That's because
> at CR2 we only consider groups where bb_free counter (number of free
> blocks) is greater than the request extent size. That's left as future
> work.
>
> All the changes introduced in this patch are protected under a new
> mount option "mb_optimize_scan".
>
> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
> ---
> fs/ext4/ext4.h | 13 +-
> fs/ext4/mballoc.c | 316 ++++++++++++++++++++++++++++++++++++++++++++--
> fs/ext4/mballoc.h | 1 +
> fs/ext4/super.c | 6 +-
> 4 files changed, 322 insertions(+), 14 deletions(-)
>
> diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
> index 317b43420ecf..0601c997c87f 100644
> --- a/fs/ext4/ext4.h
> +++ b/fs/ext4/ext4.h
> @@ -162,6 +162,8 @@ enum SHIFT_DIRECTION {
> #define EXT4_MB_USE_RESERVED 0x2000
> /* Do strict check for free blocks while retrying block allocation */
> #define EXT4_MB_STRICT_CHECK 0x4000
> +/* Avg fragment size rb tree lookup succeeded at least once for cr = 1 */
> +#define EXT4_MB_CR1_OPTIMIZED 0x8000
>
> struct ext4_allocation_request {
> /* target inode for block we're allocating */
> @@ -1247,7 +1249,9 @@ struct ext4_inode_info {
> #define EXT4_MOUNT2_JOURNAL_FAST_COMMIT 0x00000010 /* Journal fast commit */
> #define EXT4_MOUNT2_DAX_NEVER 0x00000020 /* Do not allow Direct Access */
> #define EXT4_MOUNT2_DAX_INODE 0x00000040 /* For printing options only */
> -
> +#define EXT4_MOUNT2_MB_OPTIMIZE_SCAN 0x00000080 /* Optimize group
> + * scanning in mballoc
> + */
>
> #define clear_opt(sb, opt) EXT4_SB(sb)->s_mount_opt &= \
> ~EXT4_MOUNT_##opt
> @@ -1527,6 +1531,10 @@ struct ext4_sb_info {
> unsigned int s_mb_free_pending;
> struct list_head s_freed_data_list; /* List of blocks to be freed
> after commit completed */
> + struct rb_root s_mb_avg_fragment_size_root;
> + rwlock_t s_mb_rb_lock;
> + struct list_head *s_mb_largest_free_orders;
> + rwlock_t *s_mb_largest_free_orders_locks;
>
> /* tunables */
> unsigned long s_stripe;
> @@ -3308,11 +3316,14 @@ struct ext4_group_info {
> ext4_grpblk_t bb_free; /* total free blocks */
> ext4_grpblk_t bb_fragments; /* nr of freespace fragments */
> ext4_grpblk_t bb_largest_free_order;/* order of largest frag in BG */
> + ext4_group_t bb_group; /* Group number */
> struct list_head bb_prealloc_list;
> #ifdef DOUBLE_CHECK
> void *bb_bitmap;
> #endif
> struct rw_semaphore alloc_sem;
> + struct rb_node bb_avg_fragment_size_rb;
> + struct list_head bb_largest_free_order_node;
> ext4_grpblk_t bb_counters[]; /* Nr of free power-of-two-block
> * regions, index is order.
> * bb_counters[3] = 5 means
> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
> index b7f25120547d..63562f5f42f1 100644
> --- a/fs/ext4/mballoc.c
> +++ b/fs/ext4/mballoc.c
> @@ -147,7 +147,12 @@
> * the group specified as the goal value in allocation context via
> * ac_g_ex. Each group is first checked based on the criteria whether it
> * can be used for allocation. ext4_mb_good_group explains how the groups are
> - * checked.
> + * checked. If "mb_optimize_scan" mount option is set, instead of traversing
> + * groups linearly starting at the goal, the groups are traversed in an optimal
> + * order according to each cr level, so as to minimize considering groups which
> + * would anyway be rejected by ext4_mb_good_group. This has a side effect
> + * though - subsequent allocations may not be close to each other. And so,
> + * the underlying device may get filled up in a non-linear fashion.
> *
> * Both the prealloc space are getting populated as above. So for the first
> * request we will hit the buddy cache which will result in this prealloc
> @@ -299,6 +304,8 @@
> * - bitlock on a group (group)
> * - object (inode/locality) (object)
> * - per-pa lock (pa)
> + * - cr0 lists lock (cr0)
> + * - cr1 tree lock (cr1)
> *
> * Paths:
> * - new pa
> @@ -328,6 +335,9 @@
> * group
> * object
> *
> + * - allocation path (ext4_mb_regular_allocator)
> + * group
> + * cr0/cr1
> */
> static struct kmem_cache *ext4_pspace_cachep;
> static struct kmem_cache *ext4_ac_cachep;
> @@ -351,6 +361,9 @@ static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
> ext4_group_t group);
> static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);
>
> +static bool ext4_mb_good_group(struct ext4_allocation_context *ac,
> + ext4_group_t group, int cr);
> +
> /*
> * The algorithm using this percpu seq counter goes below:
> * 1. We sample the percpu discard_pa_seq counter before trying for block
> @@ -744,6 +757,243 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> }
> }
>
> +static void ext4_mb_rb_insert(struct rb_root *root, struct rb_node *new,
> + int (*cmp)(struct rb_node *, struct rb_node *))
> +{
> + struct rb_node **iter = &root->rb_node, *parent = NULL;
> +
> + while (*iter) {
> + parent = *iter;
> + if (cmp(new, *iter))
> + iter = &((*iter)->rb_left);
> + else
> + iter = &((*iter)->rb_right);
> + }
> +
> + rb_link_node(new, parent, iter);
> + rb_insert_color(new, root);
> +}
> +
> +static int
> +ext4_mb_avg_fragment_size_cmp(struct rb_node *rb1, struct rb_node *rb2)
> +{
> + struct ext4_group_info *grp1 = rb_entry(rb1,
> + struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + struct ext4_group_info *grp2 = rb_entry(rb2,
> + struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + int num_frags_1, num_frags_2;
> +
> + num_frags_1 = grp1->bb_fragments ?
> + grp1->bb_free / grp1->bb_fragments : 0;
> + num_frags_2 = grp2->bb_fragments ?
> + grp2->bb_free / grp2->bb_fragments : 0;
> +
> + return (num_frags_1 < num_frags_2);
> +}
> +
> +/*
> + * Reinsert grpinfo into the avg_fragment_size tree with new average
> + * fragment size.
> + */
> +static void
> +mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> +
> + if (!test_opt2(sb, MB_OPTIMIZE_SCAN))
> + return;
> +
> + write_lock(&sbi->s_mb_rb_lock);
> + if (!RB_EMPTY_NODE(&grp->bb_avg_fragment_size_rb)) {
> + rb_erase(&grp->bb_avg_fragment_size_rb,
> + &sbi->s_mb_avg_fragment_size_root);
> + RB_CLEAR_NODE(&grp->bb_avg_fragment_size_rb);
> + }
> +
> + ext4_mb_rb_insert(&sbi->s_mb_avg_fragment_size_root,
> + &grp->bb_avg_fragment_size_rb,
> + ext4_mb_avg_fragment_size_cmp);
> + write_unlock(&sbi->s_mb_rb_lock);
> +}
> +
> +/*
> + * Choose next group by traversing largest_free_order lists. Return 0 if next
> + * group was selected optimally. Return 1 if next group was not selected
> + * optimally. Updates *new_cr if cr level needs an update.
> + */
> +static int ext4_mb_choose_next_group_cr0(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
> + struct ext4_group_info *iter, *grp;
> + int i;
> +
> + if (ac->ac_status == AC_STATUS_FOUND)
> + return 1;
> +
> + grp = NULL;
> + for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
> + if (list_empty(&sbi->s_mb_largest_free_orders[i]))
> + continue;
> + read_lock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (list_empty(&sbi->s_mb_largest_free_orders[i])) {
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + continue;
> + }
> + grp = NULL;
> + list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],
> + bb_largest_free_order_node) {
> + /*
> + * Perform this check without a lock, once we lock
> + * the group, we'll perform this check again.
> + */
> + if (likely(ext4_mb_good_group(ac, iter->bb_group, 0))) {
> + grp = iter;
> + break;
> + }
> + }
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (grp)
> + break;
> + }
> +
> + if (!grp) {
> + /* Increment cr and search again */
> + *new_cr = 1;
> + } else {
> + *group = grp->bb_group;
> + ac->ac_last_optimal_group = *group;
> + }
> + return 0;
> +}
> +
> +/*
> + * Choose next group by traversing average fragment size tree. Return 0 if next
> + * group was selected optimally. Return 1 if next group could not selected
> + * optimally (due to lock contention). Updates *new_cr if cr lvel needs an
> + * update.
> + */
> +static int ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
> + int avg_fragment_size, best_so_far;
> + struct rb_node *node, *found;
> + struct ext4_group_info *grp;
> +
> + /*
> + * If there is contention on the lock, instead of waiting for the lock
> + * to become available, just continue searching lineraly. We'll resume
> + * our rb tree search later starting at ac->ac_last_optimal_group.
> + */
> + if (!read_trylock(&sbi->s_mb_rb_lock))
> + return 1;
> +
> + if (ac->ac_flags & EXT4_MB_CR1_OPTIMIZED) {
> + /* We have found something at CR 1 in the past */
> + grp = ext4_get_group_info(ac->ac_sb, ac->ac_last_optimal_group);
> + for (found = rb_next(&grp->bb_avg_fragment_size_rb); found != NULL;
> + found = rb_next(found)) {
> + grp = rb_entry(found, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + /*
> + * Perform this check without locking, we'll lock later
> + * to confirm.
> + */
> + if (likely(ext4_mb_good_group(ac, grp->bb_group, 1)))
> + break;
> + }
> +
> + goto done;
> + }
> +
> + node = sbi->s_mb_avg_fragment_size_root.rb_node;
> + best_so_far = 0;
> + found = NULL;
> +
> + while (node) {
> + grp = rb_entry(node, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + /*
> + * Perform this check without locking, we'll lock later to confirm.
> + */
> + if (ext4_mb_good_group(ac, grp->bb_group, 1)) {
> + avg_fragment_size = grp->bb_fragments ?
> + grp->bb_free / grp->bb_fragments : 0;
> + if (!best_so_far || avg_fragment_size < best_so_far) {
> + best_so_far = avg_fragment_size;
> + found = node;
> + }
> + }
> + if (avg_fragment_size > ac->ac_g_ex.fe_len)
> + node = node->rb_right;
> + else
> + node = node->rb_left;
> + }
> +
> +done:
> + if (found) {
> + grp = rb_entry(found, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + *group = grp->bb_group;
> + ac->ac_flags |= EXT4_MB_CR1_OPTIMIZED;
> + } else {
> + *new_cr = 2;
> + }
> +
> + read_unlock(&sbi->s_mb_rb_lock);
> + ac->ac_last_optimal_group = *group;
> + return 0;
> +}
> +
> +/*
> + * ext4_mb_choose_next_group: choose next group for allocation.
> + *
> + * @ac Allocation Context
> + * @new_cr This is an output parameter. If the there is no good group available
> + * at current CR level, this field is updated to indicate the new cr
> + * level that should be used.
> + * @group This is an input / output parameter. As an input it indicates the last
> + * group used for allocation. As output, this field indicates the
> + * next group that should be used.
> + * @ngroups Total number of groups
> + */
> +static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + int ret;
> +
> + *new_cr = ac->ac_criteria;
> +
> + if (!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN) ||
> + *new_cr >= 2 ||
> + !ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))
> + goto inc_and_return;
> +
> + if (*new_cr == 0) {
> + ret = ext4_mb_choose_next_group_cr0(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + if (*new_cr == 1) {
> + ret = ext4_mb_choose_next_group_cr1(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + return;
> +
> +inc_and_return:
> + /*
> + * Artificially restricted ngroups for non-extent
> + * files makes group > ngroups possible on first loop.
> + */
> + *group = *group + 1;
> + if (*group >= ngroups)
> + *group = 0;
> +}
> +
> /*
> * Cache the order of the largest free extent we have available in this block
> * group.
> @@ -751,18 +1001,32 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> static void
> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
> {
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> int i;
> - int bits;
>
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_del_init(&grp->bb_largest_free_order_node);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> grp->bb_largest_free_order = -1; /* uninit */
>
> - bits = MB_NUM_ORDERS(sb) - 1;
> - for (i = bits; i >= 0; i--) {
> + for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
> if (grp->bb_counters[i] > 0) {
> grp->bb_largest_free_order = i;
> break;
> }
> }
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_add_tail(&grp->bb_largest_free_order_node,
> + &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> }
>
> static noinline_for_stack
> @@ -818,6 +1082,7 @@ void ext4_mb_generate_buddy(struct super_block *sb,
> period = get_cycles() - period;
> atomic_inc(&sbi->s_mb_buddies_generated);
> atomic64_add(period, &sbi->s_mb_generation_time);
> + mb_update_avg_fragment_size(sb, grp);
> }
>
> /* The buddy information is attached the buddy cache inode
> @@ -1517,6 +1782,7 @@ static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
>
> done:
> mb_set_largest_free_order(sb, e4b->bd_info);
> + mb_update_avg_fragment_size(sb, e4b->bd_info);
> mb_check_buddy(e4b);
> }
>
> @@ -1653,6 +1919,7 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
> }
> mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
>
> + mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);
> ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
> mb_check_buddy(e4b);
>
> @@ -2346,17 +2613,20 @@ ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
> * from the goal value specified
> */
> group = ac->ac_g_ex.fe_group;
> + ac->ac_last_optimal_group = group;
> prefetch_grp = group;
>
> - for (i = 0; i < ngroups; group++, i++) {
> - int ret = 0;
> + for (i = 0; i < ngroups; i++) {
> + int ret = 0, new_cr;
> +
> cond_resched();
> - /*
> - * Artificially restricted ngroups for non-extent
> - * files makes group > ngroups possible on first loop.
> - */
> - if (group >= ngroups)
> - group = 0;
> +
> + ext4_mb_choose_next_group(ac, &new_cr, &group, ngroups);
> +
> + if (new_cr != cr) {
> + cr = new_cr;
> + goto repeat;
> + }
>
> /*
> * Batch reads of the block allocation bitmaps
> @@ -2696,7 +2966,10 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
> INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
> init_rwsem(&meta_group_info[i]->alloc_sem);
> meta_group_info[i]->bb_free_root = RB_ROOT;
> + INIT_LIST_HEAD(&meta_group_info[i]->bb_largest_free_order_node);
> + RB_CLEAR_NODE(&meta_group_info[i]->bb_avg_fragment_size_rb);
> meta_group_info[i]->bb_largest_free_order = -1; /* uninit */
> + meta_group_info[i]->bb_group = group;
>
> mb_group_bb_bitmap_alloc(sb, meta_group_info[i], group);
> return 0;
> @@ -2886,6 +3159,22 @@ int ext4_mb_init(struct super_block *sb)
> i++;
> } while (i < MB_NUM_ORDERS(sb));
>
> + sbi->s_mb_avg_fragment_size_root = RB_ROOT;
> + sbi->s_mb_largest_free_orders =
> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(struct list_head),
> + GFP_KERNEL);
> + if (!sbi->s_mb_largest_free_orders)
> + goto out;
> + sbi->s_mb_largest_free_orders_locks =
> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(rwlock_t),
> + GFP_KERNEL);
> + if (!sbi->s_mb_largest_free_orders_locks)
> + goto out;
> + for (i = 0; i < MB_NUM_ORDERS(sb); i++) {
> + INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]);
> + rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);
> + }
> + rwlock_init(&sbi->s_mb_rb_lock);
>
> spin_lock_init(&sbi->s_md_lock);
> sbi->s_mb_free_pending = 0;
> @@ -2949,6 +3238,8 @@ int ext4_mb_init(struct super_block *sb)
> free_percpu(sbi->s_locality_groups);
> sbi->s_locality_groups = NULL;
> out:
> + kfree(sbi->s_mb_largest_free_orders);
> + kfree(sbi->s_mb_largest_free_orders_locks);
> kfree(sbi->s_mb_offsets);
> sbi->s_mb_offsets = NULL;
> kfree(sbi->s_mb_maxs);
> @@ -3005,6 +3296,7 @@ int ext4_mb_release(struct super_block *sb)
> kvfree(group_info);
> rcu_read_unlock();
> }
> + kfree(sbi->s_mb_largest_free_orders);
> kfree(sbi->s_mb_offsets);
> kfree(sbi->s_mb_maxs);
> iput(sbi->s_buddy_cache);
> diff --git a/fs/ext4/mballoc.h b/fs/ext4/mballoc.h
> index 02861406932f..1e86a8a0460d 100644
> --- a/fs/ext4/mballoc.h
> +++ b/fs/ext4/mballoc.h
> @@ -166,6 +166,7 @@ struct ext4_allocation_context {
> /* copy of the best found extent taken before preallocation efforts */
> struct ext4_free_extent ac_f_ex;
>
> + ext4_group_t ac_last_optimal_group;
> __u32 ac_groups_considered;
> __u16 ac_groups_scanned;
> __u16 ac_found;
> diff --git a/fs/ext4/super.c b/fs/ext4/super.c
> index 0f0db49031dc..a14363654cfd 100644
> --- a/fs/ext4/super.c
> +++ b/fs/ext4/super.c
> @@ -154,6 +154,7 @@ static inline void __ext4_read_bh(struct buffer_head *bh, int op_flags,
> clear_buffer_verified(bh);
>
> bh->b_end_io = end_io ? end_io : end_buffer_read_sync;
> +
> get_bh(bh);
> submit_bh(REQ_OP_READ, op_flags, bh);
> }
> @@ -1687,7 +1688,7 @@ enum {
> Opt_dioread_nolock, Opt_dioread_lock,
> Opt_discard, Opt_nodiscard, Opt_init_itable, Opt_noinit_itable,
> Opt_max_dir_size_kb, Opt_nojournal_checksum, Opt_nombcache,
> - Opt_prefetch_block_bitmaps,
> + Opt_prefetch_block_bitmaps, Opt_mb_optimize_scan,
> #ifdef CONFIG_EXT4_DEBUG
> Opt_fc_debug_max_replay, Opt_fc_debug_force
> #endif
> @@ -1788,6 +1789,7 @@ static const match_table_t tokens = {
> {Opt_nombcache, "nombcache"},
> {Opt_nombcache, "no_mbcache"}, /* for backward compatibility */
> {Opt_prefetch_block_bitmaps, "prefetch_block_bitmaps"},
> + {Opt_mb_optimize_scan, "mb_optimize_scan"},
> {Opt_removed, "check=none"}, /* mount option from ext2/3 */
> {Opt_removed, "nocheck"}, /* mount option from ext2/3 */
> {Opt_removed, "reservation"}, /* mount option from ext2/3 */
> @@ -2008,6 +2010,8 @@ static const struct mount_opts {
> {Opt_nombcache, EXT4_MOUNT_NO_MBCACHE, MOPT_SET},
> {Opt_prefetch_block_bitmaps, EXT4_MOUNT_PREFETCH_BLOCK_BITMAPS,
> MOPT_SET},
> + {Opt_mb_optimize_scan, EXT4_MOUNT2_MB_OPTIMIZE_SCAN,
> + MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
> #ifdef CONFIG_EXT4_DEBUG
> {Opt_fc_debug_force, EXT4_MOUNT2_JOURNAL_FAST_COMMIT,
> MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
> --
> 2.30.0.478.g8a0d178c01-goog
>
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-11 7:43 ` Alexey Lyashkov
@ 2021-02-11 7:53 ` Alex Zhuravlev
2021-02-11 10:13 ` Alexey Lyashkov
0 siblings, 1 reply; 17+ messages in thread
From: Alex Zhuravlev @ 2021-02-11 7:53 UTC (permalink / raw)
To: Alexey Lyashkov
Cc: Harshad Shirwadkar, linux-ext4, tytso@mit.edu,
artem.blagodarenko@gmail.com, Shuichi Ihara, adilger@dilger.ca
There is a mechanism to help mballoc to work better with RAID devices - you can specify stripe size as a mount option,
Then mballoc will be trying to normalise allocation requests to stripe size and then, having stripe size is not 2^N size,
mballoc will skip rc=0 and cr=1 in some cases.
Thanks, Alex
> On 11 Feb 2021, at 10:43, Alexey Lyashkov <alexey.lyashkov@gmail.com> wrote:
>
> Hi Harshad,
>
> I glad you look into this complex code. I have one note about groups scanning a specially with raid devices and cr0 loop.
> Once we have enough free space, cr 0 loop can found an unaligned for the stripe fragment.
> in case raid devices, cr1 don’t produce an average size check - just find an aligned chunk.
> So for raid devices CR 0 is useless, and CR1 don’t provide a good results.
>
> Can you look to this problem also ?
>
> Alex
>
>> 9 февр. 2021 г., в 23:28, Harshad Shirwadkar <harshadshirwadkar@gmail.com> написал(а):
>>
>> Instead of traversing through groups linearly, scan groups in specific
>> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
>> largest free order >= the order of the request. So, with this patch,
>> we maintain lists for each possible order and insert each group into a
>> list based on the largest free order in its buddy bitmap. During cr 0
>> allocation, we traverse these lists in the increasing order of largest
>> free orders. This allows us to find a group with the best available cr
>> 0 match in constant time. If nothing can be found, we fallback to cr 1
>> immediately.
>>
>> At CR1, the story is slightly different. We want to traverse in the
>> order of increasing average fragment size. For CR1, we maintain a rb
>> tree of groupinfos which is sorted by average fragment size. Instead
>> of traversing linearly, at CR1, we traverse in the order of increasing
>> average fragment size, starting at the most optimal group. This brings
>> down cr 1 search complexity to log(num groups).
>>
>> For cr >= 2, we just perform the linear search as before. Also, in
>> case of lock contention, we intermittently fallback to linear search
>> even in CR 0 and CR 1 cases. This allows us to proceed during the
>> allocation path even in case of high contention.
>>
>> There is an opportunity to do optimization at CR2 too. That's because
>> at CR2 we only consider groups where bb_free counter (number of free
>> blocks) is greater than the request extent size. That's left as future
>> work.
>>
>> All the changes introduced in this patch are protected under a new
>> mount option "mb_optimize_scan".
>>
>> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
>> ---
>> fs/ext4/ext4.h | 13 +-
>> fs/ext4/mballoc.c | 316 ++++++++++++++++++++++++++++++++++++++++++++--
>> fs/ext4/mballoc.h | 1 +
>> fs/ext4/super.c | 6 +-
>> 4 files changed, 322 insertions(+), 14 deletions(-)
>>
>> diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
>> index 317b43420ecf..0601c997c87f 100644
>> --- a/fs/ext4/ext4.h
>> +++ b/fs/ext4/ext4.h
>> @@ -162,6 +162,8 @@ enum SHIFT_DIRECTION {
>> #define EXT4_MB_USE_RESERVED 0x2000
>> /* Do strict check for free blocks while retrying block allocation */
>> #define EXT4_MB_STRICT_CHECK 0x4000
>> +/* Avg fragment size rb tree lookup succeeded at least once for cr = 1 */
>> +#define EXT4_MB_CR1_OPTIMIZED 0x8000
>>
>> struct ext4_allocation_request {
>> /* target inode for block we're allocating */
>> @@ -1247,7 +1249,9 @@ struct ext4_inode_info {
>> #define EXT4_MOUNT2_JOURNAL_FAST_COMMIT 0x00000010 /* Journal fast commit */
>> #define EXT4_MOUNT2_DAX_NEVER 0x00000020 /* Do not allow Direct Access */
>> #define EXT4_MOUNT2_DAX_INODE 0x00000040 /* For printing options only */
>> -
>> +#define EXT4_MOUNT2_MB_OPTIMIZE_SCAN 0x00000080 /* Optimize group
>> + * scanning in mballoc
>> + */
>>
>> #define clear_opt(sb, opt) EXT4_SB(sb)->s_mount_opt &= \
>> ~EXT4_MOUNT_##opt
>> @@ -1527,6 +1531,10 @@ struct ext4_sb_info {
>> unsigned int s_mb_free_pending;
>> struct list_head s_freed_data_list; /* List of blocks to be freed
>> after commit completed */
>> + struct rb_root s_mb_avg_fragment_size_root;
>> + rwlock_t s_mb_rb_lock;
>> + struct list_head *s_mb_largest_free_orders;
>> + rwlock_t *s_mb_largest_free_orders_locks;
>>
>> /* tunables */
>> unsigned long s_stripe;
>> @@ -3308,11 +3316,14 @@ struct ext4_group_info {
>> ext4_grpblk_t bb_free; /* total free blocks */
>> ext4_grpblk_t bb_fragments; /* nr of freespace fragments */
>> ext4_grpblk_t bb_largest_free_order;/* order of largest frag in BG */
>> + ext4_group_t bb_group; /* Group number */
>> struct list_head bb_prealloc_list;
>> #ifdef DOUBLE_CHECK
>> void *bb_bitmap;
>> #endif
>> struct rw_semaphore alloc_sem;
>> + struct rb_node bb_avg_fragment_size_rb;
>> + struct list_head bb_largest_free_order_node;
>> ext4_grpblk_t bb_counters[]; /* Nr of free power-of-two-block
>> * regions, index is order.
>> * bb_counters[3] = 5 means
>> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
>> index b7f25120547d..63562f5f42f1 100644
>> --- a/fs/ext4/mballoc.c
>> +++ b/fs/ext4/mballoc.c
>> @@ -147,7 +147,12 @@
>> * the group specified as the goal value in allocation context via
>> * ac_g_ex. Each group is first checked based on the criteria whether it
>> * can be used for allocation. ext4_mb_good_group explains how the groups are
>> - * checked.
>> + * checked. If "mb_optimize_scan" mount option is set, instead of traversing
>> + * groups linearly starting at the goal, the groups are traversed in an optimal
>> + * order according to each cr level, so as to minimize considering groups which
>> + * would anyway be rejected by ext4_mb_good_group. This has a side effect
>> + * though - subsequent allocations may not be close to each other. And so,
>> + * the underlying device may get filled up in a non-linear fashion.
>> *
>> * Both the prealloc space are getting populated as above. So for the first
>> * request we will hit the buddy cache which will result in this prealloc
>> @@ -299,6 +304,8 @@
>> * - bitlock on a group (group)
>> * - object (inode/locality) (object)
>> * - per-pa lock (pa)
>> + * - cr0 lists lock (cr0)
>> + * - cr1 tree lock (cr1)
>> *
>> * Paths:
>> * - new pa
>> @@ -328,6 +335,9 @@
>> * group
>> * object
>> *
>> + * - allocation path (ext4_mb_regular_allocator)
>> + * group
>> + * cr0/cr1
>> */
>> static struct kmem_cache *ext4_pspace_cachep;
>> static struct kmem_cache *ext4_ac_cachep;
>> @@ -351,6 +361,9 @@ static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
>> ext4_group_t group);
>> static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);
>>
>> +static bool ext4_mb_good_group(struct ext4_allocation_context *ac,
>> + ext4_group_t group, int cr);
>> +
>> /*
>> * The algorithm using this percpu seq counter goes below:
>> * 1. We sample the percpu discard_pa_seq counter before trying for block
>> @@ -744,6 +757,243 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
>> }
>> }
>>
>> +static void ext4_mb_rb_insert(struct rb_root *root, struct rb_node *new,
>> + int (*cmp)(struct rb_node *, struct rb_node *))
>> +{
>> + struct rb_node **iter = &root->rb_node, *parent = NULL;
>> +
>> + while (*iter) {
>> + parent = *iter;
>> + if (cmp(new, *iter))
>> + iter = &((*iter)->rb_left);
>> + else
>> + iter = &((*iter)->rb_right);
>> + }
>> +
>> + rb_link_node(new, parent, iter);
>> + rb_insert_color(new, root);
>> +}
>> +
>> +static int
>> +ext4_mb_avg_fragment_size_cmp(struct rb_node *rb1, struct rb_node *rb2)
>> +{
>> + struct ext4_group_info *grp1 = rb_entry(rb1,
>> + struct ext4_group_info,
>> + bb_avg_fragment_size_rb);
>> + struct ext4_group_info *grp2 = rb_entry(rb2,
>> + struct ext4_group_info,
>> + bb_avg_fragment_size_rb);
>> + int num_frags_1, num_frags_2;
>> +
>> + num_frags_1 = grp1->bb_fragments ?
>> + grp1->bb_free / grp1->bb_fragments : 0;
>> + num_frags_2 = grp2->bb_fragments ?
>> + grp2->bb_free / grp2->bb_fragments : 0;
>> +
>> + return (num_frags_1 < num_frags_2);
>> +}
>> +
>> +/*
>> + * Reinsert grpinfo into the avg_fragment_size tree with new average
>> + * fragment size.
>> + */
>> +static void
>> +mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp)
>> +{
>> + struct ext4_sb_info *sbi = EXT4_SB(sb);
>> +
>> + if (!test_opt2(sb, MB_OPTIMIZE_SCAN))
>> + return;
>> +
>> + write_lock(&sbi->s_mb_rb_lock);
>> + if (!RB_EMPTY_NODE(&grp->bb_avg_fragment_size_rb)) {
>> + rb_erase(&grp->bb_avg_fragment_size_rb,
>> + &sbi->s_mb_avg_fragment_size_root);
>> + RB_CLEAR_NODE(&grp->bb_avg_fragment_size_rb);
>> + }
>> +
>> + ext4_mb_rb_insert(&sbi->s_mb_avg_fragment_size_root,
>> + &grp->bb_avg_fragment_size_rb,
>> + ext4_mb_avg_fragment_size_cmp);
>> + write_unlock(&sbi->s_mb_rb_lock);
>> +}
>> +
>> +/*
>> + * Choose next group by traversing largest_free_order lists. Return 0 if next
>> + * group was selected optimally. Return 1 if next group was not selected
>> + * optimally. Updates *new_cr if cr level needs an update.
>> + */
>> +static int ext4_mb_choose_next_group_cr0(struct ext4_allocation_context *ac,
>> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
>> +{
>> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
>> + struct ext4_group_info *iter, *grp;
>> + int i;
>> +
>> + if (ac->ac_status == AC_STATUS_FOUND)
>> + return 1;
>> +
>> + grp = NULL;
>> + for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
>> + if (list_empty(&sbi->s_mb_largest_free_orders[i]))
>> + continue;
>> + read_lock(&sbi->s_mb_largest_free_orders_locks[i]);
>> + if (list_empty(&sbi->s_mb_largest_free_orders[i])) {
>> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
>> + continue;
>> + }
>> + grp = NULL;
>> + list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],
>> + bb_largest_free_order_node) {
>> + /*
>> + * Perform this check without a lock, once we lock
>> + * the group, we'll perform this check again.
>> + */
>> + if (likely(ext4_mb_good_group(ac, iter->bb_group, 0))) {
>> + grp = iter;
>> + break;
>> + }
>> + }
>> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
>> + if (grp)
>> + break;
>> + }
>> +
>> + if (!grp) {
>> + /* Increment cr and search again */
>> + *new_cr = 1;
>> + } else {
>> + *group = grp->bb_group;
>> + ac->ac_last_optimal_group = *group;
>> + }
>> + return 0;
>> +}
>> +
>> +/*
>> + * Choose next group by traversing average fragment size tree. Return 0 if next
>> + * group was selected optimally. Return 1 if next group could not selected
>> + * optimally (due to lock contention). Updates *new_cr if cr lvel needs an
>> + * update.
>> + */
>> +static int ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac,
>> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
>> +{
>> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
>> + int avg_fragment_size, best_so_far;
>> + struct rb_node *node, *found;
>> + struct ext4_group_info *grp;
>> +
>> + /*
>> + * If there is contention on the lock, instead of waiting for the lock
>> + * to become available, just continue searching lineraly. We'll resume
>> + * our rb tree search later starting at ac->ac_last_optimal_group.
>> + */
>> + if (!read_trylock(&sbi->s_mb_rb_lock))
>> + return 1;
>> +
>> + if (ac->ac_flags & EXT4_MB_CR1_OPTIMIZED) {
>> + /* We have found something at CR 1 in the past */
>> + grp = ext4_get_group_info(ac->ac_sb, ac->ac_last_optimal_group);
>> + for (found = rb_next(&grp->bb_avg_fragment_size_rb); found != NULL;
>> + found = rb_next(found)) {
>> + grp = rb_entry(found, struct ext4_group_info,
>> + bb_avg_fragment_size_rb);
>> + /*
>> + * Perform this check without locking, we'll lock later
>> + * to confirm.
>> + */
>> + if (likely(ext4_mb_good_group(ac, grp->bb_group, 1)))
>> + break;
>> + }
>> +
>> + goto done;
>> + }
>> +
>> + node = sbi->s_mb_avg_fragment_size_root.rb_node;
>> + best_so_far = 0;
>> + found = NULL;
>> +
>> + while (node) {
>> + grp = rb_entry(node, struct ext4_group_info,
>> + bb_avg_fragment_size_rb);
>> + /*
>> + * Perform this check without locking, we'll lock later to confirm.
>> + */
>> + if (ext4_mb_good_group(ac, grp->bb_group, 1)) {
>> + avg_fragment_size = grp->bb_fragments ?
>> + grp->bb_free / grp->bb_fragments : 0;
>> + if (!best_so_far || avg_fragment_size < best_so_far) {
>> + best_so_far = avg_fragment_size;
>> + found = node;
>> + }
>> + }
>> + if (avg_fragment_size > ac->ac_g_ex.fe_len)
>> + node = node->rb_right;
>> + else
>> + node = node->rb_left;
>> + }
>> +
>> +done:
>> + if (found) {
>> + grp = rb_entry(found, struct ext4_group_info,
>> + bb_avg_fragment_size_rb);
>> + *group = grp->bb_group;
>> + ac->ac_flags |= EXT4_MB_CR1_OPTIMIZED;
>> + } else {
>> + *new_cr = 2;
>> + }
>> +
>> + read_unlock(&sbi->s_mb_rb_lock);
>> + ac->ac_last_optimal_group = *group;
>> + return 0;
>> +}
>> +
>> +/*
>> + * ext4_mb_choose_next_group: choose next group for allocation.
>> + *
>> + * @ac Allocation Context
>> + * @new_cr This is an output parameter. If the there is no good group available
>> + * at current CR level, this field is updated to indicate the new cr
>> + * level that should be used.
>> + * @group This is an input / output parameter. As an input it indicates the last
>> + * group used for allocation. As output, this field indicates the
>> + * next group that should be used.
>> + * @ngroups Total number of groups
>> + */
>> +static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,
>> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
>> +{
>> + int ret;
>> +
>> + *new_cr = ac->ac_criteria;
>> +
>> + if (!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN) ||
>> + *new_cr >= 2 ||
>> + !ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))
>> + goto inc_and_return;
>> +
>> + if (*new_cr == 0) {
>> + ret = ext4_mb_choose_next_group_cr0(ac, new_cr, group, ngroups);
>> + if (ret)
>> + goto inc_and_return;
>> + }
>> + if (*new_cr == 1) {
>> + ret = ext4_mb_choose_next_group_cr1(ac, new_cr, group, ngroups);
>> + if (ret)
>> + goto inc_and_return;
>> + }
>> + return;
>> +
>> +inc_and_return:
>> + /*
>> + * Artificially restricted ngroups for non-extent
>> + * files makes group > ngroups possible on first loop.
>> + */
>> + *group = *group + 1;
>> + if (*group >= ngroups)
>> + *group = 0;
>> +}
>> +
>> /*
>> * Cache the order of the largest free extent we have available in this block
>> * group.
>> @@ -751,18 +1001,32 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
>> static void
>> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
>> {
>> + struct ext4_sb_info *sbi = EXT4_SB(sb);
>> int i;
>> - int bits;
>>
>> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
>> + write_lock(&sbi->s_mb_largest_free_orders_locks[
>> + grp->bb_largest_free_order]);
>> + list_del_init(&grp->bb_largest_free_order_node);
>> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
>> + grp->bb_largest_free_order]);
>> + }
>> grp->bb_largest_free_order = -1; /* uninit */
>>
>> - bits = MB_NUM_ORDERS(sb) - 1;
>> - for (i = bits; i >= 0; i--) {
>> + for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
>> if (grp->bb_counters[i] > 0) {
>> grp->bb_largest_free_order = i;
>> break;
>> }
>> }
>> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
>> + write_lock(&sbi->s_mb_largest_free_orders_locks[
>> + grp->bb_largest_free_order]);
>> + list_add_tail(&grp->bb_largest_free_order_node,
>> + &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
>> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
>> + grp->bb_largest_free_order]);
>> + }
>> }
>>
>> static noinline_for_stack
>> @@ -818,6 +1082,7 @@ void ext4_mb_generate_buddy(struct super_block *sb,
>> period = get_cycles() - period;
>> atomic_inc(&sbi->s_mb_buddies_generated);
>> atomic64_add(period, &sbi->s_mb_generation_time);
>> + mb_update_avg_fragment_size(sb, grp);
>> }
>>
>> /* The buddy information is attached the buddy cache inode
>> @@ -1517,6 +1782,7 @@ static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
>>
>> done:
>> mb_set_largest_free_order(sb, e4b->bd_info);
>> + mb_update_avg_fragment_size(sb, e4b->bd_info);
>> mb_check_buddy(e4b);
>> }
>>
>> @@ -1653,6 +1919,7 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
>> }
>> mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
>>
>> + mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);
>> ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
>> mb_check_buddy(e4b);
>>
>> @@ -2346,17 +2613,20 @@ ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
>> * from the goal value specified
>> */
>> group = ac->ac_g_ex.fe_group;
>> + ac->ac_last_optimal_group = group;
>> prefetch_grp = group;
>>
>> - for (i = 0; i < ngroups; group++, i++) {
>> - int ret = 0;
>> + for (i = 0; i < ngroups; i++) {
>> + int ret = 0, new_cr;
>> +
>> cond_resched();
>> - /*
>> - * Artificially restricted ngroups for non-extent
>> - * files makes group > ngroups possible on first loop.
>> - */
>> - if (group >= ngroups)
>> - group = 0;
>> +
>> + ext4_mb_choose_next_group(ac, &new_cr, &group, ngroups);
>> +
>> + if (new_cr != cr) {
>> + cr = new_cr;
>> + goto repeat;
>> + }
>>
>> /*
>> * Batch reads of the block allocation bitmaps
>> @@ -2696,7 +2966,10 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
>> INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
>> init_rwsem(&meta_group_info[i]->alloc_sem);
>> meta_group_info[i]->bb_free_root = RB_ROOT;
>> + INIT_LIST_HEAD(&meta_group_info[i]->bb_largest_free_order_node);
>> + RB_CLEAR_NODE(&meta_group_info[i]->bb_avg_fragment_size_rb);
>> meta_group_info[i]->bb_largest_free_order = -1; /* uninit */
>> + meta_group_info[i]->bb_group = group;
>>
>> mb_group_bb_bitmap_alloc(sb, meta_group_info[i], group);
>> return 0;
>> @@ -2886,6 +3159,22 @@ int ext4_mb_init(struct super_block *sb)
>> i++;
>> } while (i < MB_NUM_ORDERS(sb));
>>
>> + sbi->s_mb_avg_fragment_size_root = RB_ROOT;
>> + sbi->s_mb_largest_free_orders =
>> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(struct list_head),
>> + GFP_KERNEL);
>> + if (!sbi->s_mb_largest_free_orders)
>> + goto out;
>> + sbi->s_mb_largest_free_orders_locks =
>> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(rwlock_t),
>> + GFP_KERNEL);
>> + if (!sbi->s_mb_largest_free_orders_locks)
>> + goto out;
>> + for (i = 0; i < MB_NUM_ORDERS(sb); i++) {
>> + INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]);
>> + rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);
>> + }
>> + rwlock_init(&sbi->s_mb_rb_lock);
>>
>> spin_lock_init(&sbi->s_md_lock);
>> sbi->s_mb_free_pending = 0;
>> @@ -2949,6 +3238,8 @@ int ext4_mb_init(struct super_block *sb)
>> free_percpu(sbi->s_locality_groups);
>> sbi->s_locality_groups = NULL;
>> out:
>> + kfree(sbi->s_mb_largest_free_orders);
>> + kfree(sbi->s_mb_largest_free_orders_locks);
>> kfree(sbi->s_mb_offsets);
>> sbi->s_mb_offsets = NULL;
>> kfree(sbi->s_mb_maxs);
>> @@ -3005,6 +3296,7 @@ int ext4_mb_release(struct super_block *sb)
>> kvfree(group_info);
>> rcu_read_unlock();
>> }
>> + kfree(sbi->s_mb_largest_free_orders);
>> kfree(sbi->s_mb_offsets);
>> kfree(sbi->s_mb_maxs);
>> iput(sbi->s_buddy_cache);
>> diff --git a/fs/ext4/mballoc.h b/fs/ext4/mballoc.h
>> index 02861406932f..1e86a8a0460d 100644
>> --- a/fs/ext4/mballoc.h
>> +++ b/fs/ext4/mballoc.h
>> @@ -166,6 +166,7 @@ struct ext4_allocation_context {
>> /* copy of the best found extent taken before preallocation efforts */
>> struct ext4_free_extent ac_f_ex;
>>
>> + ext4_group_t ac_last_optimal_group;
>> __u32 ac_groups_considered;
>> __u16 ac_groups_scanned;
>> __u16 ac_found;
>> diff --git a/fs/ext4/super.c b/fs/ext4/super.c
>> index 0f0db49031dc..a14363654cfd 100644
>> --- a/fs/ext4/super.c
>> +++ b/fs/ext4/super.c
>> @@ -154,6 +154,7 @@ static inline void __ext4_read_bh(struct buffer_head *bh, int op_flags,
>> clear_buffer_verified(bh);
>>
>> bh->b_end_io = end_io ? end_io : end_buffer_read_sync;
>> +
>> get_bh(bh);
>> submit_bh(REQ_OP_READ, op_flags, bh);
>> }
>> @@ -1687,7 +1688,7 @@ enum {
>> Opt_dioread_nolock, Opt_dioread_lock,
>> Opt_discard, Opt_nodiscard, Opt_init_itable, Opt_noinit_itable,
>> Opt_max_dir_size_kb, Opt_nojournal_checksum, Opt_nombcache,
>> - Opt_prefetch_block_bitmaps,
>> + Opt_prefetch_block_bitmaps, Opt_mb_optimize_scan,
>> #ifdef CONFIG_EXT4_DEBUG
>> Opt_fc_debug_max_replay, Opt_fc_debug_force
>> #endif
>> @@ -1788,6 +1789,7 @@ static const match_table_t tokens = {
>> {Opt_nombcache, "nombcache"},
>> {Opt_nombcache, "no_mbcache"}, /* for backward compatibility */
>> {Opt_prefetch_block_bitmaps, "prefetch_block_bitmaps"},
>> + {Opt_mb_optimize_scan, "mb_optimize_scan"},
>> {Opt_removed, "check=none"}, /* mount option from ext2/3 */
>> {Opt_removed, "nocheck"}, /* mount option from ext2/3 */
>> {Opt_removed, "reservation"}, /* mount option from ext2/3 */
>> @@ -2008,6 +2010,8 @@ static const struct mount_opts {
>> {Opt_nombcache, EXT4_MOUNT_NO_MBCACHE, MOPT_SET},
>> {Opt_prefetch_block_bitmaps, EXT4_MOUNT_PREFETCH_BLOCK_BITMAPS,
>> MOPT_SET},
>> + {Opt_mb_optimize_scan, EXT4_MOUNT2_MB_OPTIMIZE_SCAN,
>> + MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
>> #ifdef CONFIG_EXT4_DEBUG
>> {Opt_fc_debug_force, EXT4_MOUNT2_JOURNAL_FAST_COMMIT,
>> MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
>> --
>> 2.30.0.478.g8a0d178c01-goog
>>
>
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-11 7:53 ` Alex Zhuravlev
@ 2021-02-11 10:13 ` Alexey Lyashkov
0 siblings, 0 replies; 17+ messages in thread
From: Alexey Lyashkov @ 2021-02-11 10:13 UTC (permalink / raw)
To: Alex Zhuravlev
Cc: Harshad Shirwadkar, linux-ext4, tytso@mit.edu,
artem.blagodarenko@gmail.com, Shuichi Ihara, adilger@dilger.ca
Alex,
Yes, request normalize in place to match stripe size.
But, CR 0 don’t check a offset is stripe aligned as well.
static noinline_for_stack
void ext4_mb_simple_scan_group(struct ext4_allocation_context *ac,
struct ext4_buddy *e4b)
{
struct super_block *sb = ac->ac_sb;
struct ext4_group_info *grp = e4b->bd_info;
void *buddy;
int i;
int k;
int max;
BUG_ON(ac->ac_2order <= 0);
for (i = ac->ac_2order; i <= sb->s_blocksize_bits + 1; i++) {
if (grp->bb_counters[i] == 0)
continue;
buddy = mb_find_buddy(e4b, i, &max);
BUG_ON(buddy == NULL);
k = mb_find_next_zero_bit(buddy, max, 0); <<< don’t have aligned with sbi->s_stripe
if (k >= max) {
ext4_grp_locked_error(ac->ac_sb, e4b->bd_group, 0, 0,
"%d free clusters of order %d. But found 0",
grp->bb_counters[i], i);
ext4_mark_group_bitmap_corrupted(ac->ac_sb,
e4b->bd_group,
EXT4_GROUP_INFO_BBITMAP_CORRUPT);
break;
}
ac->ac_found++;
ac->ac_b_ex.fe_len = 1 << i;
ac->ac_b_ex.fe_start = k << i; <<< don’t know about stripe align.
ac->ac_b_ex.fe_group = e4b->bd_group;
In additional to the
if (cr == 0)
ext4_mb_simple_scan_group(ac, &e4b);
else if (cr == 1 && sbi->s_stripe &&
!(ac->ac_g_ex.fe_len % sbi->s_stripe))
ext4_mb_scan_aligned(ac, &e4b);
it mean - CR0 can lost any stripe alignment.
Alex
> 11 февр. 2021 г., в 10:53, Alex Zhuravlev <azhuravlev@whamcloud.com> написал(а):
>
>
> There is a mechanism to help mballoc to work better with RAID devices - you can specify stripe size as a mount option,
> Then mballoc will be trying to normalise allocation requests to stripe size and then, having stripe size is not 2^N size,
> mballoc will skip rc=0 and cr=1 in some cases.
>
> Thanks, Alex
>
>
>> On 11 Feb 2021, at 10:43, Alexey Lyashkov <alexey.lyashkov@gmail.com> wrote:
>>
>> Hi Harshad,
>>
>> I glad you look into this complex code. I have one note about groups scanning a specially with raid devices and cr0 loop.
>> Once we have enough free space, cr 0 loop can found an unaligned for the stripe fragment.
>> in case raid devices, cr1 don’t produce an average size check - just find an aligned chunk.
>> So for raid devices CR 0 is useless, and CR1 don’t provide a good results.
>>
>> Can you look to this problem also ?
>>
>> Alex
>>
>>> 9 февр. 2021 г., в 23:28, Harshad Shirwadkar <harshadshirwadkar@gmail.com> написал(а):
>>>
>>> Instead of traversing through groups linearly, scan groups in specific
>>> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
>>> largest free order >= the order of the request. So, with this patch,
>>> we maintain lists for each possible order and insert each group into a
>>> list based on the largest free order in its buddy bitmap. During cr 0
>>> allocation, we traverse these lists in the increasing order of largest
>>> free orders. This allows us to find a group with the best available cr
>>> 0 match in constant time. If nothing can be found, we fallback to cr 1
>>> immediately.
>>>
>>> At CR1, the story is slightly different. We want to traverse in the
>>> order of increasing average fragment size. For CR1, we maintain a rb
>>> tree of groupinfos which is sorted by average fragment size. Instead
>>> of traversing linearly, at CR1, we traverse in the order of increasing
>>> average fragment size, starting at the most optimal group. This brings
>>> down cr 1 search complexity to log(num groups).
>>>
>>> For cr >= 2, we just perform the linear search as before. Also, in
>>> case of lock contention, we intermittently fallback to linear search
>>> even in CR 0 and CR 1 cases. This allows us to proceed during the
>>> allocation path even in case of high contention.
>>>
>>> There is an opportunity to do optimization at CR2 too. That's because
>>> at CR2 we only consider groups where bb_free counter (number of free
>>> blocks) is greater than the request extent size. That's left as future
>>> work.
>>>
>>> All the changes introduced in this patch are protected under a new
>>> mount option "mb_optimize_scan".
>>>
>>> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
>>> ---
>>> fs/ext4/ext4.h | 13 +-
>>> fs/ext4/mballoc.c | 316 ++++++++++++++++++++++++++++++++++++++++++++--
>>> fs/ext4/mballoc.h | 1 +
>>> fs/ext4/super.c | 6 +-
>>> 4 files changed, 322 insertions(+), 14 deletions(-)
>>>
>>> diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
>>> index 317b43420ecf..0601c997c87f 100644
>>> --- a/fs/ext4/ext4.h
>>> +++ b/fs/ext4/ext4.h
>>> @@ -162,6 +162,8 @@ enum SHIFT_DIRECTION {
>>> #define EXT4_MB_USE_RESERVED 0x2000
>>> /* Do strict check for free blocks while retrying block allocation */
>>> #define EXT4_MB_STRICT_CHECK 0x4000
>>> +/* Avg fragment size rb tree lookup succeeded at least once for cr = 1 */
>>> +#define EXT4_MB_CR1_OPTIMIZED 0x8000
>>>
>>> struct ext4_allocation_request {
>>> /* target inode for block we're allocating */
>>> @@ -1247,7 +1249,9 @@ struct ext4_inode_info {
>>> #define EXT4_MOUNT2_JOURNAL_FAST_COMMIT 0x00000010 /* Journal fast commit */
>>> #define EXT4_MOUNT2_DAX_NEVER 0x00000020 /* Do not allow Direct Access */
>>> #define EXT4_MOUNT2_DAX_INODE 0x00000040 /* For printing options only */
>>> -
>>> +#define EXT4_MOUNT2_MB_OPTIMIZE_SCAN 0x00000080 /* Optimize group
>>> + * scanning in mballoc
>>> + */
>>>
>>> #define clear_opt(sb, opt) EXT4_SB(sb)->s_mount_opt &= \
>>> ~EXT4_MOUNT_##opt
>>> @@ -1527,6 +1531,10 @@ struct ext4_sb_info {
>>> unsigned int s_mb_free_pending;
>>> struct list_head s_freed_data_list; /* List of blocks to be freed
>>> after commit completed */
>>> + struct rb_root s_mb_avg_fragment_size_root;
>>> + rwlock_t s_mb_rb_lock;
>>> + struct list_head *s_mb_largest_free_orders;
>>> + rwlock_t *s_mb_largest_free_orders_locks;
>>>
>>> /* tunables */
>>> unsigned long s_stripe;
>>> @@ -3308,11 +3316,14 @@ struct ext4_group_info {
>>> ext4_grpblk_t bb_free; /* total free blocks */
>>> ext4_grpblk_t bb_fragments; /* nr of freespace fragments */
>>> ext4_grpblk_t bb_largest_free_order;/* order of largest frag in BG */
>>> + ext4_group_t bb_group; /* Group number */
>>> struct list_head bb_prealloc_list;
>>> #ifdef DOUBLE_CHECK
>>> void *bb_bitmap;
>>> #endif
>>> struct rw_semaphore alloc_sem;
>>> + struct rb_node bb_avg_fragment_size_rb;
>>> + struct list_head bb_largest_free_order_node;
>>> ext4_grpblk_t bb_counters[]; /* Nr of free power-of-two-block
>>> * regions, index is order.
>>> * bb_counters[3] = 5 means
>>> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
>>> index b7f25120547d..63562f5f42f1 100644
>>> --- a/fs/ext4/mballoc.c
>>> +++ b/fs/ext4/mballoc.c
>>> @@ -147,7 +147,12 @@
>>> * the group specified as the goal value in allocation context via
>>> * ac_g_ex. Each group is first checked based on the criteria whether it
>>> * can be used for allocation. ext4_mb_good_group explains how the groups are
>>> - * checked.
>>> + * checked. If "mb_optimize_scan" mount option is set, instead of traversing
>>> + * groups linearly starting at the goal, the groups are traversed in an optimal
>>> + * order according to each cr level, so as to minimize considering groups which
>>> + * would anyway be rejected by ext4_mb_good_group. This has a side effect
>>> + * though - subsequent allocations may not be close to each other. And so,
>>> + * the underlying device may get filled up in a non-linear fashion.
>>> *
>>> * Both the prealloc space are getting populated as above. So for the first
>>> * request we will hit the buddy cache which will result in this prealloc
>>> @@ -299,6 +304,8 @@
>>> * - bitlock on a group (group)
>>> * - object (inode/locality) (object)
>>> * - per-pa lock (pa)
>>> + * - cr0 lists lock (cr0)
>>> + * - cr1 tree lock (cr1)
>>> *
>>> * Paths:
>>> * - new pa
>>> @@ -328,6 +335,9 @@
>>> * group
>>> * object
>>> *
>>> + * - allocation path (ext4_mb_regular_allocator)
>>> + * group
>>> + * cr0/cr1
>>> */
>>> static struct kmem_cache *ext4_pspace_cachep;
>>> static struct kmem_cache *ext4_ac_cachep;
>>> @@ -351,6 +361,9 @@ static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
>>> ext4_group_t group);
>>> static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);
>>>
>>> +static bool ext4_mb_good_group(struct ext4_allocation_context *ac,
>>> + ext4_group_t group, int cr);
>>> +
>>> /*
>>> * The algorithm using this percpu seq counter goes below:
>>> * 1. We sample the percpu discard_pa_seq counter before trying for block
>>> @@ -744,6 +757,243 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
>>> }
>>> }
>>>
>>> +static void ext4_mb_rb_insert(struct rb_root *root, struct rb_node *new,
>>> + int (*cmp)(struct rb_node *, struct rb_node *))
>>> +{
>>> + struct rb_node **iter = &root->rb_node, *parent = NULL;
>>> +
>>> + while (*iter) {
>>> + parent = *iter;
>>> + if (cmp(new, *iter))
>>> + iter = &((*iter)->rb_left);
>>> + else
>>> + iter = &((*iter)->rb_right);
>>> + }
>>> +
>>> + rb_link_node(new, parent, iter);
>>> + rb_insert_color(new, root);
>>> +}
>>> +
>>> +static int
>>> +ext4_mb_avg_fragment_size_cmp(struct rb_node *rb1, struct rb_node *rb2)
>>> +{
>>> + struct ext4_group_info *grp1 = rb_entry(rb1,
>>> + struct ext4_group_info,
>>> + bb_avg_fragment_size_rb);
>>> + struct ext4_group_info *grp2 = rb_entry(rb2,
>>> + struct ext4_group_info,
>>> + bb_avg_fragment_size_rb);
>>> + int num_frags_1, num_frags_2;
>>> +
>>> + num_frags_1 = grp1->bb_fragments ?
>>> + grp1->bb_free / grp1->bb_fragments : 0;
>>> + num_frags_2 = grp2->bb_fragments ?
>>> + grp2->bb_free / grp2->bb_fragments : 0;
>>> +
>>> + return (num_frags_1 < num_frags_2);
>>> +}
>>> +
>>> +/*
>>> + * Reinsert grpinfo into the avg_fragment_size tree with new average
>>> + * fragment size.
>>> + */
>>> +static void
>>> +mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp)
>>> +{
>>> + struct ext4_sb_info *sbi = EXT4_SB(sb);
>>> +
>>> + if (!test_opt2(sb, MB_OPTIMIZE_SCAN))
>>> + return;
>>> +
>>> + write_lock(&sbi->s_mb_rb_lock);
>>> + if (!RB_EMPTY_NODE(&grp->bb_avg_fragment_size_rb)) {
>>> + rb_erase(&grp->bb_avg_fragment_size_rb,
>>> + &sbi->s_mb_avg_fragment_size_root);
>>> + RB_CLEAR_NODE(&grp->bb_avg_fragment_size_rb);
>>> + }
>>> +
>>> + ext4_mb_rb_insert(&sbi->s_mb_avg_fragment_size_root,
>>> + &grp->bb_avg_fragment_size_rb,
>>> + ext4_mb_avg_fragment_size_cmp);
>>> + write_unlock(&sbi->s_mb_rb_lock);
>>> +}
>>> +
>>> +/*
>>> + * Choose next group by traversing largest_free_order lists. Return 0 if next
>>> + * group was selected optimally. Return 1 if next group was not selected
>>> + * optimally. Updates *new_cr if cr level needs an update.
>>> + */
>>> +static int ext4_mb_choose_next_group_cr0(struct ext4_allocation_context *ac,
>>> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
>>> +{
>>> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
>>> + struct ext4_group_info *iter, *grp;
>>> + int i;
>>> +
>>> + if (ac->ac_status == AC_STATUS_FOUND)
>>> + return 1;
>>> +
>>> + grp = NULL;
>>> + for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
>>> + if (list_empty(&sbi->s_mb_largest_free_orders[i]))
>>> + continue;
>>> + read_lock(&sbi->s_mb_largest_free_orders_locks[i]);
>>> + if (list_empty(&sbi->s_mb_largest_free_orders[i])) {
>>> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
>>> + continue;
>>> + }
>>> + grp = NULL;
>>> + list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],
>>> + bb_largest_free_order_node) {
>>> + /*
>>> + * Perform this check without a lock, once we lock
>>> + * the group, we'll perform this check again.
>>> + */
>>> + if (likely(ext4_mb_good_group(ac, iter->bb_group, 0))) {
>>> + grp = iter;
>>> + break;
>>> + }
>>> + }
>>> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
>>> + if (grp)
>>> + break;
>>> + }
>>> +
>>> + if (!grp) {
>>> + /* Increment cr and search again */
>>> + *new_cr = 1;
>>> + } else {
>>> + *group = grp->bb_group;
>>> + ac->ac_last_optimal_group = *group;
>>> + }
>>> + return 0;
>>> +}
>>> +
>>> +/*
>>> + * Choose next group by traversing average fragment size tree. Return 0 if next
>>> + * group was selected optimally. Return 1 if next group could not selected
>>> + * optimally (due to lock contention). Updates *new_cr if cr lvel needs an
>>> + * update.
>>> + */
>>> +static int ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac,
>>> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
>>> +{
>>> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
>>> + int avg_fragment_size, best_so_far;
>>> + struct rb_node *node, *found;
>>> + struct ext4_group_info *grp;
>>> +
>>> + /*
>>> + * If there is contention on the lock, instead of waiting for the lock
>>> + * to become available, just continue searching lineraly. We'll resume
>>> + * our rb tree search later starting at ac->ac_last_optimal_group.
>>> + */
>>> + if (!read_trylock(&sbi->s_mb_rb_lock))
>>> + return 1;
>>> +
>>> + if (ac->ac_flags & EXT4_MB_CR1_OPTIMIZED) {
>>> + /* We have found something at CR 1 in the past */
>>> + grp = ext4_get_group_info(ac->ac_sb, ac->ac_last_optimal_group);
>>> + for (found = rb_next(&grp->bb_avg_fragment_size_rb); found != NULL;
>>> + found = rb_next(found)) {
>>> + grp = rb_entry(found, struct ext4_group_info,
>>> + bb_avg_fragment_size_rb);
>>> + /*
>>> + * Perform this check without locking, we'll lock later
>>> + * to confirm.
>>> + */
>>> + if (likely(ext4_mb_good_group(ac, grp->bb_group, 1)))
>>> + break;
>>> + }
>>> +
>>> + goto done;
>>> + }
>>> +
>>> + node = sbi->s_mb_avg_fragment_size_root.rb_node;
>>> + best_so_far = 0;
>>> + found = NULL;
>>> +
>>> + while (node) {
>>> + grp = rb_entry(node, struct ext4_group_info,
>>> + bb_avg_fragment_size_rb);
>>> + /*
>>> + * Perform this check without locking, we'll lock later to confirm.
>>> + */
>>> + if (ext4_mb_good_group(ac, grp->bb_group, 1)) {
>>> + avg_fragment_size = grp->bb_fragments ?
>>> + grp->bb_free / grp->bb_fragments : 0;
>>> + if (!best_so_far || avg_fragment_size < best_so_far) {
>>> + best_so_far = avg_fragment_size;
>>> + found = node;
>>> + }
>>> + }
>>> + if (avg_fragment_size > ac->ac_g_ex.fe_len)
>>> + node = node->rb_right;
>>> + else
>>> + node = node->rb_left;
>>> + }
>>> +
>>> +done:
>>> + if (found) {
>>> + grp = rb_entry(found, struct ext4_group_info,
>>> + bb_avg_fragment_size_rb);
>>> + *group = grp->bb_group;
>>> + ac->ac_flags |= EXT4_MB_CR1_OPTIMIZED;
>>> + } else {
>>> + *new_cr = 2;
>>> + }
>>> +
>>> + read_unlock(&sbi->s_mb_rb_lock);
>>> + ac->ac_last_optimal_group = *group;
>>> + return 0;
>>> +}
>>> +
>>> +/*
>>> + * ext4_mb_choose_next_group: choose next group for allocation.
>>> + *
>>> + * @ac Allocation Context
>>> + * @new_cr This is an output parameter. If the there is no good group available
>>> + * at current CR level, this field is updated to indicate the new cr
>>> + * level that should be used.
>>> + * @group This is an input / output parameter. As an input it indicates the last
>>> + * group used for allocation. As output, this field indicates the
>>> + * next group that should be used.
>>> + * @ngroups Total number of groups
>>> + */
>>> +static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,
>>> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
>>> +{
>>> + int ret;
>>> +
>>> + *new_cr = ac->ac_criteria;
>>> +
>>> + if (!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN) ||
>>> + *new_cr >= 2 ||
>>> + !ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))
>>> + goto inc_and_return;
>>> +
>>> + if (*new_cr == 0) {
>>> + ret = ext4_mb_choose_next_group_cr0(ac, new_cr, group, ngroups);
>>> + if (ret)
>>> + goto inc_and_return;
>>> + }
>>> + if (*new_cr == 1) {
>>> + ret = ext4_mb_choose_next_group_cr1(ac, new_cr, group, ngroups);
>>> + if (ret)
>>> + goto inc_and_return;
>>> + }
>>> + return;
>>> +
>>> +inc_and_return:
>>> + /*
>>> + * Artificially restricted ngroups for non-extent
>>> + * files makes group > ngroups possible on first loop.
>>> + */
>>> + *group = *group + 1;
>>> + if (*group >= ngroups)
>>> + *group = 0;
>>> +}
>>> +
>>> /*
>>> * Cache the order of the largest free extent we have available in this block
>>> * group.
>>> @@ -751,18 +1001,32 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
>>> static void
>>> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
>>> {
>>> + struct ext4_sb_info *sbi = EXT4_SB(sb);
>>> int i;
>>> - int bits;
>>>
>>> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
>>> + write_lock(&sbi->s_mb_largest_free_orders_locks[
>>> + grp->bb_largest_free_order]);
>>> + list_del_init(&grp->bb_largest_free_order_node);
>>> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
>>> + grp->bb_largest_free_order]);
>>> + }
>>> grp->bb_largest_free_order = -1; /* uninit */
>>>
>>> - bits = MB_NUM_ORDERS(sb) - 1;
>>> - for (i = bits; i >= 0; i--) {
>>> + for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
>>> if (grp->bb_counters[i] > 0) {
>>> grp->bb_largest_free_order = i;
>>> break;
>>> }
>>> }
>>> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
>>> + write_lock(&sbi->s_mb_largest_free_orders_locks[
>>> + grp->bb_largest_free_order]);
>>> + list_add_tail(&grp->bb_largest_free_order_node,
>>> + &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
>>> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
>>> + grp->bb_largest_free_order]);
>>> + }
>>> }
>>>
>>> static noinline_for_stack
>>> @@ -818,6 +1082,7 @@ void ext4_mb_generate_buddy(struct super_block *sb,
>>> period = get_cycles() - period;
>>> atomic_inc(&sbi->s_mb_buddies_generated);
>>> atomic64_add(period, &sbi->s_mb_generation_time);
>>> + mb_update_avg_fragment_size(sb, grp);
>>> }
>>>
>>> /* The buddy information is attached the buddy cache inode
>>> @@ -1517,6 +1782,7 @@ static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
>>>
>>> done:
>>> mb_set_largest_free_order(sb, e4b->bd_info);
>>> + mb_update_avg_fragment_size(sb, e4b->bd_info);
>>> mb_check_buddy(e4b);
>>> }
>>>
>>> @@ -1653,6 +1919,7 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
>>> }
>>> mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
>>>
>>> + mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);
>>> ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
>>> mb_check_buddy(e4b);
>>>
>>> @@ -2346,17 +2613,20 @@ ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
>>> * from the goal value specified
>>> */
>>> group = ac->ac_g_ex.fe_group;
>>> + ac->ac_last_optimal_group = group;
>>> prefetch_grp = group;
>>>
>>> - for (i = 0; i < ngroups; group++, i++) {
>>> - int ret = 0;
>>> + for (i = 0; i < ngroups; i++) {
>>> + int ret = 0, new_cr;
>>> +
>>> cond_resched();
>>> - /*
>>> - * Artificially restricted ngroups for non-extent
>>> - * files makes group > ngroups possible on first loop.
>>> - */
>>> - if (group >= ngroups)
>>> - group = 0;
>>> +
>>> + ext4_mb_choose_next_group(ac, &new_cr, &group, ngroups);
>>> +
>>> + if (new_cr != cr) {
>>> + cr = new_cr;
>>> + goto repeat;
>>> + }
>>>
>>> /*
>>> * Batch reads of the block allocation bitmaps
>>> @@ -2696,7 +2966,10 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
>>> INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
>>> init_rwsem(&meta_group_info[i]->alloc_sem);
>>> meta_group_info[i]->bb_free_root = RB_ROOT;
>>> + INIT_LIST_HEAD(&meta_group_info[i]->bb_largest_free_order_node);
>>> + RB_CLEAR_NODE(&meta_group_info[i]->bb_avg_fragment_size_rb);
>>> meta_group_info[i]->bb_largest_free_order = -1; /* uninit */
>>> + meta_group_info[i]->bb_group = group;
>>>
>>> mb_group_bb_bitmap_alloc(sb, meta_group_info[i], group);
>>> return 0;
>>> @@ -2886,6 +3159,22 @@ int ext4_mb_init(struct super_block *sb)
>>> i++;
>>> } while (i < MB_NUM_ORDERS(sb));
>>>
>>> + sbi->s_mb_avg_fragment_size_root = RB_ROOT;
>>> + sbi->s_mb_largest_free_orders =
>>> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(struct list_head),
>>> + GFP_KERNEL);
>>> + if (!sbi->s_mb_largest_free_orders)
>>> + goto out;
>>> + sbi->s_mb_largest_free_orders_locks =
>>> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(rwlock_t),
>>> + GFP_KERNEL);
>>> + if (!sbi->s_mb_largest_free_orders_locks)
>>> + goto out;
>>> + for (i = 0; i < MB_NUM_ORDERS(sb); i++) {
>>> + INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]);
>>> + rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);
>>> + }
>>> + rwlock_init(&sbi->s_mb_rb_lock);
>>>
>>> spin_lock_init(&sbi->s_md_lock);
>>> sbi->s_mb_free_pending = 0;
>>> @@ -2949,6 +3238,8 @@ int ext4_mb_init(struct super_block *sb)
>>> free_percpu(sbi->s_locality_groups);
>>> sbi->s_locality_groups = NULL;
>>> out:
>>> + kfree(sbi->s_mb_largest_free_orders);
>>> + kfree(sbi->s_mb_largest_free_orders_locks);
>>> kfree(sbi->s_mb_offsets);
>>> sbi->s_mb_offsets = NULL;
>>> kfree(sbi->s_mb_maxs);
>>> @@ -3005,6 +3296,7 @@ int ext4_mb_release(struct super_block *sb)
>>> kvfree(group_info);
>>> rcu_read_unlock();
>>> }
>>> + kfree(sbi->s_mb_largest_free_orders);
>>> kfree(sbi->s_mb_offsets);
>>> kfree(sbi->s_mb_maxs);
>>> iput(sbi->s_buddy_cache);
>>> diff --git a/fs/ext4/mballoc.h b/fs/ext4/mballoc.h
>>> index 02861406932f..1e86a8a0460d 100644
>>> --- a/fs/ext4/mballoc.h
>>> +++ b/fs/ext4/mballoc.h
>>> @@ -166,6 +166,7 @@ struct ext4_allocation_context {
>>> /* copy of the best found extent taken before preallocation efforts */
>>> struct ext4_free_extent ac_f_ex;
>>>
>>> + ext4_group_t ac_last_optimal_group;
>>> __u32 ac_groups_considered;
>>> __u16 ac_groups_scanned;
>>> __u16 ac_found;
>>> diff --git a/fs/ext4/super.c b/fs/ext4/super.c
>>> index 0f0db49031dc..a14363654cfd 100644
>>> --- a/fs/ext4/super.c
>>> +++ b/fs/ext4/super.c
>>> @@ -154,6 +154,7 @@ static inline void __ext4_read_bh(struct buffer_head *bh, int op_flags,
>>> clear_buffer_verified(bh);
>>>
>>> bh->b_end_io = end_io ? end_io : end_buffer_read_sync;
>>> +
>>> get_bh(bh);
>>> submit_bh(REQ_OP_READ, op_flags, bh);
>>> }
>>> @@ -1687,7 +1688,7 @@ enum {
>>> Opt_dioread_nolock, Opt_dioread_lock,
>>> Opt_discard, Opt_nodiscard, Opt_init_itable, Opt_noinit_itable,
>>> Opt_max_dir_size_kb, Opt_nojournal_checksum, Opt_nombcache,
>>> - Opt_prefetch_block_bitmaps,
>>> + Opt_prefetch_block_bitmaps, Opt_mb_optimize_scan,
>>> #ifdef CONFIG_EXT4_DEBUG
>>> Opt_fc_debug_max_replay, Opt_fc_debug_force
>>> #endif
>>> @@ -1788,6 +1789,7 @@ static const match_table_t tokens = {
>>> {Opt_nombcache, "nombcache"},
>>> {Opt_nombcache, "no_mbcache"}, /* for backward compatibility */
>>> {Opt_prefetch_block_bitmaps, "prefetch_block_bitmaps"},
>>> + {Opt_mb_optimize_scan, "mb_optimize_scan"},
>>> {Opt_removed, "check=none"}, /* mount option from ext2/3 */
>>> {Opt_removed, "nocheck"}, /* mount option from ext2/3 */
>>> {Opt_removed, "reservation"}, /* mount option from ext2/3 */
>>> @@ -2008,6 +2010,8 @@ static const struct mount_opts {
>>> {Opt_nombcache, EXT4_MOUNT_NO_MBCACHE, MOPT_SET},
>>> {Opt_prefetch_block_bitmaps, EXT4_MOUNT_PREFETCH_BLOCK_BITMAPS,
>>> MOPT_SET},
>>> + {Opt_mb_optimize_scan, EXT4_MOUNT2_MB_OPTIMIZE_SCAN,
>>> + MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
>>> #ifdef CONFIG_EXT4_DEBUG
>>> {Opt_fc_debug_force, EXT4_MOUNT2_JOURNAL_FAST_COMMIT,
>>> MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
>>> --
>>> 2.30.0.478.g8a0d178c01-goog
>>>
>>
>
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-09 20:28 ` [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning Harshad Shirwadkar
2021-02-10 9:00 ` Dan Carpenter
2021-02-11 7:43 ` Alexey Lyashkov
@ 2021-02-11 10:30 ` Andreas Dilger
2021-02-12 22:46 ` Andreas Dilger
` (2 subsequent siblings)
5 siblings, 0 replies; 17+ messages in thread
From: Andreas Dilger @ 2021-02-11 10:30 UTC (permalink / raw)
To: Harshad Shirwadkar
Cc: linux-ext4, tytso, Alex Zhuravlev, artem.blagodarenko,
Shuichi Ihara
[-- Attachment #1: Type: text/plain, Size: 7654 bytes --]
On Feb 9, 2021, at 1:28 PM, Harshad Shirwadkar <harshadshirwadkar@gmail.com> wrote:
>
> Instead of traversing through groups linearly, scan groups in specific
> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
> largest free order >= the order of the request. So, with this patch,
> we maintain lists for each possible order and insert each group into a
> list based on the largest free order in its buddy bitmap. During cr 0
> allocation, we traverse these lists in the increasing order of largest
> free orders. This allows us to find a group with the best available cr
> 0 match in constant time. If nothing can be found, we fallback to cr 1
> immediately.
>
> At CR1, the story is slightly different. We want to traverse in the
> order of increasing average fragment size. For CR1, we maintain a rb
> tree of groupinfos which is sorted by average fragment size. Instead
> of traversing linearly, at CR1, we traverse in the order of increasing
> average fragment size, starting at the most optimal group. This brings
> down cr 1 search complexity to log(num groups).
>
> For cr >= 2, we just perform the linear search as before. Also, in
> case of lock contention, we intermittently fallback to linear search
> even in CR 0 and CR 1 cases. This allows us to proceed during the
> allocation path even in case of high contention.
>
> There is an opportunity to do optimization at CR2 too. That's because
> at CR2 we only consider groups where bb_free counter (number of free
> blocks) is greater than the request extent size. That's left as future
> work.
>
> All the changes introduced in this patch are protected under a new
> mount option "mb_optimize_scan".
>
> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
> ---
>
> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
> index b7f25120547d..63562f5f42f1 100644
> --- a/fs/ext4/mballoc.c
> +++ b/fs/ext4/mballoc.c
>
> +/*
> + * Choose next group by traversing largest_free_order lists. Return 0 if next
> + * group was selected optimally. Return 1 if next group was not selected
> + * optimally. Updates *new_cr if cr level needs an update.
> + */
> +static int ext4_mb_choose_next_group_cr0(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
> + if (list_empty(&sbi->s_mb_largest_free_orders[i]))
> + continue;
> + read_lock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (list_empty(&sbi->s_mb_largest_free_orders[i])) {
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + continue;
> + }
> + grp = NULL;
> + list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],
> + bb_largest_free_order_node) {
> + /*
> + * Perform this check without a lock, once we lock
> + * the group, we'll perform this check again.
> + */
This comment is no longer correct.
> + if (likely(ext4_mb_good_group(ac, iter->bb_group, 0))) {
> + grp = iter;
> + break;
> + }
> + }
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (grp)
> + break;
> + }
> +}
> +/*
> + * ext4_mb_choose_next_group: choose next group for allocation.
> + *
> + * @ac Allocation Context
> + * @new_cr This is an output parameter. If the there is no good group available
> + * at current CR level, this field is updated to indicate the new cr
> + * level that should be used.
> + * @group This is an input / output parameter. As an input it indicates the last
> + * group used for allocation. As output, this field indicates the
> + * next group that should be used.
> + * @ngroups Total number of groups
> + */
> +static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + int ret;
> +
> + *new_cr = ac->ac_criteria;
> +
> + if (!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN) ||
> + *new_cr >= 2 ||
> + !ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))
> + goto inc_and_return;
I still think it would be beneficial to check if the next group is good
before going to the list/tree. That will reduce lock contention, and
will also avoid needless seeking between groups if possible.
> + if (*new_cr == 0) {
> + ret = ext4_mb_choose_next_group_cr0(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + if (*new_cr == 1) {
> + ret = ext4_mb_choose_next_group_cr1(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + return;
> +
> +inc_and_return:
> + /*
> + * Artificially restricted ngroups for non-extent
> + * files makes group > ngroups possible on first loop.
> + */
> + *group = *group + 1;
> + if (*group >= ngroups)
> + *group = 0;
> +}
> +
> /*
> * Cache the order of the largest free extent we have available in this block
> * group.
> @@ -751,18 +1001,32 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> static void
> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
> {
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> int i;
> - int bits;
>
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_del_init(&grp->bb_largest_free_order_node);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> grp->bb_largest_free_order = -1; /* uninit */
>
> - bits = MB_NUM_ORDERS(sb) - 1;
> - for (i = bits; i >= 0; i--) {
> + for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
> if (grp->bb_counters[i] > 0) {
> grp->bb_largest_free_order = i;
> break;
> }
> }
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_add_tail(&grp->bb_largest_free_order_node,
> + &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> }
This function would be more efficient to do the list move under a single
write lock if the order doesn't change. The order loop would just
save the largest free order, then grab the write lock, do the list_del(),
set bb_largest_free_order, and list_add_tail():
mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
{
struct ext4_sb_info *sbi = EXT4_SB(sb);
int i, new_order = -1;
for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
if (grp->bb_counters[i] > 0) {
new_order = i;
break;
}
}
if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
write_lock(&sbi->s_mb_largest_free_orders_locks[
grp->bb_largest_free_order]);
list_del_init(&grp->bb_largest_free_order_node);
if (new_order != grp->bb_largest_free_order) {
write_unlock(&sbi->s_mb_largest_free_orders_locks[
grp->bb_largest_free_order]);
grp->bb_largest_free_order = new_order;
write_lock(&sbi->s_mb_largest_free_orders_locks[
grp->bb_largest_free_order]);
}
list_add_tail(&grp->bb_largest_free_order_node,
&sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
write_unlock(&sbi->s_mb_largest_free_orders_locks[
grp->bb_largest_free_order]);
}
}
Cheers, Andreas
[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-09 20:28 ` [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning Harshad Shirwadkar
` (2 preceding siblings ...)
2021-02-11 10:30 ` Andreas Dilger
@ 2021-02-12 22:46 ` Andreas Dilger
2021-02-16 19:39 ` Благодаренко Артём
2021-02-17 19:41 ` Благодаренко Артём
5 siblings, 0 replies; 17+ messages in thread
From: Andreas Dilger @ 2021-02-12 22:46 UTC (permalink / raw)
To: Harshad Shirwadkar
Cc: linux-ext4, tytso, Alex Zhuravlev, artem.blagodarenko,
Shuichi Ihara
[-- Attachment #1: Type: text/plain, Size: 19214 bytes --]
On Feb 9, 2021, at 1:28 PM, Harshad Shirwadkar <harshadshirwadkar@gmail.com> wrote:
>
> Instead of traversing through groups linearly, scan groups in specific
> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
> largest free order >= the order of the request. So, with this patch,
> we maintain lists for each possible order and insert each group into a
> list based on the largest free order in its buddy bitmap. During cr 0
> allocation, we traverse these lists in the increasing order of largest
> free orders. This allows us to find a group with the best available cr
> 0 match in constant time. If nothing can be found, we fallback to cr 1
> immediately.
>
> At CR1, the story is slightly different. We want to traverse in the
> order of increasing average fragment size. For CR1, we maintain a rb
> tree of groupinfos which is sorted by average fragment size. Instead
> of traversing linearly, at CR1, we traverse in the order of increasing
> average fragment size, starting at the most optimal group. This brings
> down cr 1 search complexity to log(num groups).
>
> For cr >= 2, we just perform the linear search as before. Also, in
> case of lock contention, we intermittently fallback to linear search
> even in CR 0 and CR 1 cases. This allows us to proceed during the
> allocation path even in case of high contention.
>
> There is an opportunity to do optimization at CR2 too. That's because
> at CR2 we only consider groups where bb_free counter (number of free
> blocks) is greater than the request extent size. That's left as future
> work.
>
> All the changes introduced in this patch are protected under a new
> mount option "mb_optimize_scan".
Harshad, if you are going to refresh this patch, I would recommend to
include all or most of what you write in the commit message into the
below comment at the start of mballoc.c, possibly with some editing in
the expectation that "mb_optimized_scan" will become the default so
that the description of the list/rbtree for cr0/cr1 is mentioned first,
and the sequential group scanning is mentioned afterward.
Otherwise, the existing comment only mentions "groups are traversed in
an optimal order" which doesn't really explain much useful to the reader.
Cheers, Andreas
> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
> index b7f25120547d..63562f5f42f1 100644
> --- a/fs/ext4/mballoc.c
> +++ b/fs/ext4/mballoc.c
> @@ -147,7 +147,12 @@
> * the group specified as the goal value in allocation context via
> * ac_g_ex. Each group is first checked based on the criteria whether it
> * can be used for allocation. ext4_mb_good_group explains how the groups are
> - * checked.
> + * checked. If "mb_optimize_scan" mount option is set, instead of traversing
> + * groups linearly starting at the goal, the groups are traversed in an optimal
> + * order according to each cr level, so as to minimize considering groups which
> + * would anyway be rejected by ext4_mb_good_group. This has a side effect
> + * though - subsequent allocations may not be close to each other. And so,
> + * the underlying device may get filled up in a non-linear fashion.
> *
> * Both the prealloc space are getting populated as above. So for the first
> * request we will hit the buddy cache which will result in this prealloc
> @@ -299,6 +304,8 @@
> * - bitlock on a group (group)
> * - object (inode/locality) (object)
> * - per-pa lock (pa)
> + * - cr0 lists lock (cr0)
> + * - cr1 tree lock (cr1)
> *
> * Paths:
> * - new pa
> @@ -328,6 +335,9 @@
> * group
> * object
> *
> + * - allocation path (ext4_mb_regular_allocator)
> + * group
> + * cr0/cr1
> */
> static struct kmem_cache *ext4_pspace_cachep;
> static struct kmem_cache *ext4_ac_cachep;
> @@ -351,6 +361,9 @@ static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
> ext4_group_t group);
> static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);
>
> +static bool ext4_mb_good_group(struct ext4_allocation_context *ac,
> + ext4_group_t group, int cr);
> +
> /*
> * The algorithm using this percpu seq counter goes below:
> * 1. We sample the percpu discard_pa_seq counter before trying for block
> @@ -744,6 +757,243 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> }
> }
>
> +static void ext4_mb_rb_insert(struct rb_root *root, struct rb_node *new,
> + int (*cmp)(struct rb_node *, struct rb_node *))
> +{
> + struct rb_node **iter = &root->rb_node, *parent = NULL;
> +
> + while (*iter) {
> + parent = *iter;
> + if (cmp(new, *iter))
> + iter = &((*iter)->rb_left);
> + else
> + iter = &((*iter)->rb_right);
> + }
> +
> + rb_link_node(new, parent, iter);
> + rb_insert_color(new, root);
> +}
> +
> +static int
> +ext4_mb_avg_fragment_size_cmp(struct rb_node *rb1, struct rb_node *rb2)
> +{
> + struct ext4_group_info *grp1 = rb_entry(rb1,
> + struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + struct ext4_group_info *grp2 = rb_entry(rb2,
> + struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + int num_frags_1, num_frags_2;
> +
> + num_frags_1 = grp1->bb_fragments ?
> + grp1->bb_free / grp1->bb_fragments : 0;
> + num_frags_2 = grp2->bb_fragments ?
> + grp2->bb_free / grp2->bb_fragments : 0;
> +
> + return (num_frags_1 < num_frags_2);
> +}
> +
> +/*
> + * Reinsert grpinfo into the avg_fragment_size tree with new average
> + * fragment size.
> + */
> +static void
> +mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> +
> + if (!test_opt2(sb, MB_OPTIMIZE_SCAN))
> + return;
> +
> + write_lock(&sbi->s_mb_rb_lock);
> + if (!RB_EMPTY_NODE(&grp->bb_avg_fragment_size_rb)) {
> + rb_erase(&grp->bb_avg_fragment_size_rb,
> + &sbi->s_mb_avg_fragment_size_root);
> + RB_CLEAR_NODE(&grp->bb_avg_fragment_size_rb);
> + }
> +
> + ext4_mb_rb_insert(&sbi->s_mb_avg_fragment_size_root,
> + &grp->bb_avg_fragment_size_rb,
> + ext4_mb_avg_fragment_size_cmp);
> + write_unlock(&sbi->s_mb_rb_lock);
> +}
> +
> +/*
> + * Choose next group by traversing largest_free_order lists. Return 0 if next
> + * group was selected optimally. Return 1 if next group was not selected
> + * optimally. Updates *new_cr if cr level needs an update.
> + */
> +static int ext4_mb_choose_next_group_cr0(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
> + struct ext4_group_info *iter, *grp;
> + int i;
> +
> + if (ac->ac_status == AC_STATUS_FOUND)
> + return 1;
> +
> + grp = NULL;
> + for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
> + if (list_empty(&sbi->s_mb_largest_free_orders[i]))
> + continue;
> + read_lock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (list_empty(&sbi->s_mb_largest_free_orders[i])) {
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + continue;
> + }
> + grp = NULL;
> + list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],
> + bb_largest_free_order_node) {
> + /*
> + * Perform this check without a lock, once we lock
> + * the group, we'll perform this check again.
> + */
> + if (likely(ext4_mb_good_group(ac, iter->bb_group, 0))) {
> + grp = iter;
> + break;
> + }
> + }
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (grp)
> + break;
> + }
> +
> + if (!grp) {
> + /* Increment cr and search again */
> + *new_cr = 1;
> + } else {
> + *group = grp->bb_group;
> + ac->ac_last_optimal_group = *group;
> + }
> + return 0;
> +}
> +
> +/*
> + * Choose next group by traversing average fragment size tree. Return 0 if next
> + * group was selected optimally. Return 1 if next group could not selected
> + * optimally (due to lock contention). Updates *new_cr if cr lvel needs an
> + * update.
> + */
> +static int ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
> + int avg_fragment_size, best_so_far;
> + struct rb_node *node, *found;
> + struct ext4_group_info *grp;
> +
> + /*
> + * If there is contention on the lock, instead of waiting for the lock
> + * to become available, just continue searching lineraly. We'll resume
> + * our rb tree search later starting at ac->ac_last_optimal_group.
> + */
> + if (!read_trylock(&sbi->s_mb_rb_lock))
> + return 1;
> +
> + if (ac->ac_flags & EXT4_MB_CR1_OPTIMIZED) {
> + /* We have found something at CR 1 in the past */
> + grp = ext4_get_group_info(ac->ac_sb, ac->ac_last_optimal_group);
> + for (found = rb_next(&grp->bb_avg_fragment_size_rb); found != NULL;
> + found = rb_next(found)) {
> + grp = rb_entry(found, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + /*
> + * Perform this check without locking, we'll lock later
> + * to confirm.
> + */
> + if (likely(ext4_mb_good_group(ac, grp->bb_group, 1)))
> + break;
> + }
> +
> + goto done;
> + }
> +
> + node = sbi->s_mb_avg_fragment_size_root.rb_node;
> + best_so_far = 0;
> + found = NULL;
> +
> + while (node) {
> + grp = rb_entry(node, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + /*
> + * Perform this check without locking, we'll lock later to confirm.
> + */
> + if (ext4_mb_good_group(ac, grp->bb_group, 1)) {
> + avg_fragment_size = grp->bb_fragments ?
> + grp->bb_free / grp->bb_fragments : 0;
> + if (!best_so_far || avg_fragment_size < best_so_far) {
> + best_so_far = avg_fragment_size;
> + found = node;
> + }
> + }
> + if (avg_fragment_size > ac->ac_g_ex.fe_len)
> + node = node->rb_right;
> + else
> + node = node->rb_left;
> + }
> +
> +done:
> + if (found) {
> + grp = rb_entry(found, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + *group = grp->bb_group;
> + ac->ac_flags |= EXT4_MB_CR1_OPTIMIZED;
> + } else {
> + *new_cr = 2;
> + }
> +
> + read_unlock(&sbi->s_mb_rb_lock);
> + ac->ac_last_optimal_group = *group;
> + return 0;
> +}
> +
> +/*
> + * ext4_mb_choose_next_group: choose next group for allocation.
> + *
> + * @ac Allocation Context
> + * @new_cr This is an output parameter. If the there is no good group available
> + * at current CR level, this field is updated to indicate the new cr
> + * level that should be used.
> + * @group This is an input / output parameter. As an input it indicates the last
> + * group used for allocation. As output, this field indicates the
> + * next group that should be used.
> + * @ngroups Total number of groups
> + */
> +static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + int ret;
> +
> + *new_cr = ac->ac_criteria;
> +
> + if (!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN) ||
> + *new_cr >= 2 ||
> + !ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))
> + goto inc_and_return;
> +
> + if (*new_cr == 0) {
> + ret = ext4_mb_choose_next_group_cr0(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + if (*new_cr == 1) {
> + ret = ext4_mb_choose_next_group_cr1(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + return;
> +
> +inc_and_return:
> + /*
> + * Artificially restricted ngroups for non-extent
> + * files makes group > ngroups possible on first loop.
> + */
> + *group = *group + 1;
> + if (*group >= ngroups)
> + *group = 0;
> +}
> +
> /*
> * Cache the order of the largest free extent we have available in this block
> * group.
> @@ -751,18 +1001,32 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> static void
> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
> {
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> int i;
> - int bits;
>
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_del_init(&grp->bb_largest_free_order_node);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> grp->bb_largest_free_order = -1; /* uninit */
>
> - bits = MB_NUM_ORDERS(sb) - 1;
> - for (i = bits; i >= 0; i--) {
> + for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
> if (grp->bb_counters[i] > 0) {
> grp->bb_largest_free_order = i;
> break;
> }
> }
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_add_tail(&grp->bb_largest_free_order_node,
> + &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> }
>
> static noinline_for_stack
> @@ -818,6 +1082,7 @@ void ext4_mb_generate_buddy(struct super_block *sb,
> period = get_cycles() - period;
> atomic_inc(&sbi->s_mb_buddies_generated);
> atomic64_add(period, &sbi->s_mb_generation_time);
> + mb_update_avg_fragment_size(sb, grp);
> }
>
> /* The buddy information is attached the buddy cache inode
> @@ -1517,6 +1782,7 @@ static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
>
> done:
> mb_set_largest_free_order(sb, e4b->bd_info);
> + mb_update_avg_fragment_size(sb, e4b->bd_info);
> mb_check_buddy(e4b);
> }
>
> @@ -1653,6 +1919,7 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
> }
> mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
>
> + mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);
> ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
> mb_check_buddy(e4b);
>
> @@ -2346,17 +2613,20 @@ ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
> * from the goal value specified
> */
> group = ac->ac_g_ex.fe_group;
> + ac->ac_last_optimal_group = group;
> prefetch_grp = group;
>
> - for (i = 0; i < ngroups; group++, i++) {
> - int ret = 0;
> + for (i = 0; i < ngroups; i++) {
> + int ret = 0, new_cr;
> +
> cond_resched();
> - /*
> - * Artificially restricted ngroups for non-extent
> - * files makes group > ngroups possible on first loop.
> - */
> - if (group >= ngroups)
> - group = 0;
> +
> + ext4_mb_choose_next_group(ac, &new_cr, &group, ngroups);
> +
> + if (new_cr != cr) {
> + cr = new_cr;
> + goto repeat;
> + }
>
> /*
> * Batch reads of the block allocation bitmaps
> @@ -2696,7 +2966,10 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
> INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
> init_rwsem(&meta_group_info[i]->alloc_sem);
> meta_group_info[i]->bb_free_root = RB_ROOT;
> + INIT_LIST_HEAD(&meta_group_info[i]->bb_largest_free_order_node);
> + RB_CLEAR_NODE(&meta_group_info[i]->bb_avg_fragment_size_rb);
> meta_group_info[i]->bb_largest_free_order = -1; /* uninit */
> + meta_group_info[i]->bb_group = group;
>
> mb_group_bb_bitmap_alloc(sb, meta_group_info[i], group);
> return 0;
> @@ -2886,6 +3159,22 @@ int ext4_mb_init(struct super_block *sb)
> i++;
> } while (i < MB_NUM_ORDERS(sb));
>
> + sbi->s_mb_avg_fragment_size_root = RB_ROOT;
> + sbi->s_mb_largest_free_orders =
> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(struct list_head),
> + GFP_KERNEL);
> + if (!sbi->s_mb_largest_free_orders)
> + goto out;
> + sbi->s_mb_largest_free_orders_locks =
> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(rwlock_t),
> + GFP_KERNEL);
> + if (!sbi->s_mb_largest_free_orders_locks)
> + goto out;
> + for (i = 0; i < MB_NUM_ORDERS(sb); i++) {
> + INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]);
> + rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);
> + }
> + rwlock_init(&sbi->s_mb_rb_lock);
>
> spin_lock_init(&sbi->s_md_lock);
> sbi->s_mb_free_pending = 0;
> @@ -2949,6 +3238,8 @@ int ext4_mb_init(struct super_block *sb)
> free_percpu(sbi->s_locality_groups);
> sbi->s_locality_groups = NULL;
> out:
> + kfree(sbi->s_mb_largest_free_orders);
> + kfree(sbi->s_mb_largest_free_orders_locks);
> kfree(sbi->s_mb_offsets);
> sbi->s_mb_offsets = NULL;
> kfree(sbi->s_mb_maxs);
> @@ -3005,6 +3296,7 @@ int ext4_mb_release(struct super_block *sb)
> kvfree(group_info);
> rcu_read_unlock();
> }
> + kfree(sbi->s_mb_largest_free_orders);
> kfree(sbi->s_mb_offsets);
> kfree(sbi->s_mb_maxs);
> iput(sbi->s_buddy_cache);
> diff --git a/fs/ext4/mballoc.h b/fs/ext4/mballoc.h
> index 02861406932f..1e86a8a0460d 100644
> --- a/fs/ext4/mballoc.h
> +++ b/fs/ext4/mballoc.h
> @@ -166,6 +166,7 @@ struct ext4_allocation_context {
> /* copy of the best found extent taken before preallocation efforts */
> struct ext4_free_extent ac_f_ex;
>
> + ext4_group_t ac_last_optimal_group;
> __u32 ac_groups_considered;
> __u16 ac_groups_scanned;
> __u16 ac_found;
> diff --git a/fs/ext4/super.c b/fs/ext4/super.c
> index 0f0db49031dc..a14363654cfd 100644
> --- a/fs/ext4/super.c
> +++ b/fs/ext4/super.c
> @@ -154,6 +154,7 @@ static inline void __ext4_read_bh(struct buffer_head *bh, int op_flags,
> clear_buffer_verified(bh);
>
> bh->b_end_io = end_io ? end_io : end_buffer_read_sync;
> +
> get_bh(bh);
> submit_bh(REQ_OP_READ, op_flags, bh);
> }
> @@ -1687,7 +1688,7 @@ enum {
> Opt_dioread_nolock, Opt_dioread_lock,
> Opt_discard, Opt_nodiscard, Opt_init_itable, Opt_noinit_itable,
> Opt_max_dir_size_kb, Opt_nojournal_checksum, Opt_nombcache,
> - Opt_prefetch_block_bitmaps,
> + Opt_prefetch_block_bitmaps, Opt_mb_optimize_scan,
> #ifdef CONFIG_EXT4_DEBUG
> Opt_fc_debug_max_replay, Opt_fc_debug_force
> #endif
> @@ -1788,6 +1789,7 @@ static const match_table_t tokens = {
> {Opt_nombcache, "nombcache"},
> {Opt_nombcache, "no_mbcache"}, /* for backward compatibility */
> {Opt_prefetch_block_bitmaps, "prefetch_block_bitmaps"},
> + {Opt_mb_optimize_scan, "mb_optimize_scan"},
> {Opt_removed, "check=none"}, /* mount option from ext2/3 */
> {Opt_removed, "nocheck"}, /* mount option from ext2/3 */
> {Opt_removed, "reservation"}, /* mount option from ext2/3 */
> @@ -2008,6 +2010,8 @@ static const struct mount_opts {
> {Opt_nombcache, EXT4_MOUNT_NO_MBCACHE, MOPT_SET},
> {Opt_prefetch_block_bitmaps, EXT4_MOUNT_PREFETCH_BLOCK_BITMAPS,
> MOPT_SET},
> + {Opt_mb_optimize_scan, EXT4_MOUNT2_MB_OPTIMIZE_SCAN,
> + MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
> #ifdef CONFIG_EXT4_DEBUG
> {Opt_fc_debug_force, EXT4_MOUNT2_JOURNAL_FAST_COMMIT,
> MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
> --
> 2.30.0.478.g8a0d178c01-goog
>
Cheers, Andreas
[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-09 20:28 ` [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning Harshad Shirwadkar
` (3 preceding siblings ...)
2021-02-12 22:46 ` Andreas Dilger
@ 2021-02-16 19:39 ` Благодаренко Артём
2021-02-16 22:36 ` Andreas Dilger
2021-02-17 19:41 ` Благодаренко Артём
5 siblings, 1 reply; 17+ messages in thread
From: Благодаренко Артём @ 2021-02-16 19:39 UTC (permalink / raw)
To: Harshad Shirwadkar
Cc: linux-ext4, Theodore Y. Ts'o, bzzz, sihara, Andreas Dilger
Hello Harshad,
Thanks for this useful optimisation.
Some comments bellow.
> On 9 Feb 2021, at 23:28, Harshad Shirwadkar <harshadshirwadkar@gmail.com> wrote:
>
> Instead of traversing through groups linearly, scan groups in specific
> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
> largest free order >= the order of the request. So, with this patch,
> we maintain lists for each possible order and insert each group into a
> list based on the largest free order in its buddy bitmap. During cr 0
> allocation, we traverse these lists in the increasing order of largest
> free orders. This allows us to find a group with the best available cr
> 0 match in constant time. If nothing can be found, we fallback to cr 1
> immediately.
>
> At CR1, the story is slightly different. We want to traverse in the
> order of increasing average fragment size. For CR1, we maintain a rb
> tree of groupinfos which is sorted by average fragment size. Instead
> of traversing linearly, at CR1, we traverse in the order of increasing
> average fragment size, starting at the most optimal group. This brings
> down cr 1 search complexity to log(num groups).
>
> For cr >= 2, we just perform the linear search as before. Also, in
> case of lock contention, we intermittently fallback to linear search
> even in CR 0 and CR 1 cases. This allows us to proceed during the
> allocation path even in case of high contention.
>
> There is an opportunity to do optimization at CR2 too. That's because
> at CR2 we only consider groups where bb_free counter (number of free
> blocks) is greater than the request extent size. That's left as future
> work.
>
> All the changes introduced in this patch are protected under a new
> mount option "mb_optimize_scan".
>
> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
> ---
> fs/ext4/ext4.h | 13 +-
> fs/ext4/mballoc.c | 316 ++++++++++++++++++++++++++++++++++++++++++++--
> fs/ext4/mballoc.h | 1 +
> fs/ext4/super.c | 6 +-
> 4 files changed, 322 insertions(+), 14 deletions(-)
>
> diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
> index 317b43420ecf..0601c997c87f 100644
> --- a/fs/ext4/ext4.h
> +++ b/fs/ext4/ext4.h
> @@ -162,6 +162,8 @@ enum SHIFT_DIRECTION {
> #define EXT4_MB_USE_RESERVED 0x2000
> /* Do strict check for free blocks while retrying block allocation */
> #define EXT4_MB_STRICT_CHECK 0x4000
> +/* Avg fragment size rb tree lookup succeeded at least once for cr = 1 */
> +#define EXT4_MB_CR1_OPTIMIZED 0x8000
>
> struct ext4_allocation_request {
> /* target inode for block we're allocating */
> @@ -1247,7 +1249,9 @@ struct ext4_inode_info {
> #define EXT4_MOUNT2_JOURNAL_FAST_COMMIT 0x00000010 /* Journal fast commit */
> #define EXT4_MOUNT2_DAX_NEVER 0x00000020 /* Do not allow Direct Access */
> #define EXT4_MOUNT2_DAX_INODE 0x00000040 /* For printing options only */
> -
> +#define EXT4_MOUNT2_MB_OPTIMIZE_SCAN 0x00000080 /* Optimize group
> + * scanning in mballoc
> + */
>
> #define clear_opt(sb, opt) EXT4_SB(sb)->s_mount_opt &= \
> ~EXT4_MOUNT_##opt
> @@ -1527,6 +1531,10 @@ struct ext4_sb_info {
> unsigned int s_mb_free_pending;
> struct list_head s_freed_data_list; /* List of blocks to be freed
> after commit completed */
> + struct rb_root s_mb_avg_fragment_size_root;
> + rwlock_t s_mb_rb_lock;
> + struct list_head *s_mb_largest_free_orders;
> + rwlock_t *s_mb_largest_free_orders_locks;
>
> /* tunables */
> unsigned long s_stripe;
> @@ -3308,11 +3316,14 @@ struct ext4_group_info {
> ext4_grpblk_t bb_free; /* total free blocks */
> ext4_grpblk_t bb_fragments; /* nr of freespace fragments */
> ext4_grpblk_t bb_largest_free_order;/* order of largest frag in BG */
> + ext4_group_t bb_group; /* Group number */
> struct list_head bb_prealloc_list;
> #ifdef DOUBLE_CHECK
> void *bb_bitmap;
> #endif
> struct rw_semaphore alloc_sem;
> + struct rb_node bb_avg_fragment_size_rb;
> + struct list_head bb_largest_free_order_node;
> ext4_grpblk_t bb_counters[]; /* Nr of free power-of-two-block
> * regions, index is order.
> * bb_counters[3] = 5 means
> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
> index b7f25120547d..63562f5f42f1 100644
> --- a/fs/ext4/mballoc.c
> +++ b/fs/ext4/mballoc.c
> @@ -147,7 +147,12 @@
> * the group specified as the goal value in allocation context via
> * ac_g_ex. Each group is first checked based on the criteria whether it
> * can be used for allocation. ext4_mb_good_group explains how the groups are
> - * checked.
> + * checked. If "mb_optimize_scan" mount option is set, instead of traversing
> + * groups linearly starting at the goal, the groups are traversed in an optimal
> + * order according to each cr level, so as to minimize considering groups which
> + * would anyway be rejected by ext4_mb_good_group. This has a side effect
> + * though - subsequent allocations may not be close to each other. And so,
> + * the underlying device may get filled up in a non-linear fashion.
> *
> * Both the prealloc space are getting populated as above. So for the first
> * request we will hit the buddy cache which will result in this prealloc
> @@ -299,6 +304,8 @@
> * - bitlock on a group (group)
> * - object (inode/locality) (object)
> * - per-pa lock (pa)
> + * - cr0 lists lock (cr0)
> + * - cr1 tree lock (cr1)
> *
> * Paths:
> * - new pa
> @@ -328,6 +335,9 @@
> * group
> * object
> *
> + * - allocation path (ext4_mb_regular_allocator)
> + * group
> + * cr0/cr1
> */
> static struct kmem_cache *ext4_pspace_cachep;
> static struct kmem_cache *ext4_ac_cachep;
> @@ -351,6 +361,9 @@ static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
> ext4_group_t group);
> static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);
>
> +static bool ext4_mb_good_group(struct ext4_allocation_context *ac,
> + ext4_group_t group, int cr);
> +
> /*
> * The algorithm using this percpu seq counter goes below:
> * 1. We sample the percpu discard_pa_seq counter before trying for block
> @@ -744,6 +757,243 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> }
> }
>
> +static void ext4_mb_rb_insert(struct rb_root *root, struct rb_node *new,
> + int (*cmp)(struct rb_node *, struct rb_node *))
> +{
> + struct rb_node **iter = &root->rb_node, *parent = NULL;
> +
> + while (*iter) {
> + parent = *iter;
> + if (cmp(new, *iter))
> + iter = &((*iter)->rb_left);
> + else
> + iter = &((*iter)->rb_right);
> + }
> +
> + rb_link_node(new, parent, iter);
> + rb_insert_color(new, root);
> +}
> +
> +static int
> +ext4_mb_avg_fragment_size_cmp(struct rb_node *rb1, struct rb_node *rb2)
> +{
> + struct ext4_group_info *grp1 = rb_entry(rb1,
> + struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + struct ext4_group_info *grp2 = rb_entry(rb2,
> + struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + int num_frags_1, num_frags_2;
> +
> + num_frags_1 = grp1->bb_fragments ?
> + grp1->bb_free / grp1->bb_fragments : 0;
> + num_frags_2 = grp2->bb_fragments ?
> + grp2->bb_free / grp2->bb_fragments : 0;
> +
> + return (num_frags_1 < num_frags_2);
> +}
> +
> +/*
> + * Reinsert grpinfo into the avg_fragment_size tree with new average
> + * fragment size.
> + */
Walk along the ngroups linked elements in worst case for every mb_free_blocks and mb_mark_used which are quite frequently executed actions.
If double-linked list is used for avg_fragments this function will make this change without iterating through the list:
1. Check with previous element. If smaller, then commute
2. Check with next element. If greater, then commute.
> +static void
> +mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> +
> + if (!test_opt2(sb, MB_OPTIMIZE_SCAN))
> + return;
> +
> + write_lock(&sbi->s_mb_rb_lock);
> + if (!RB_EMPTY_NODE(&grp->bb_avg_fragment_size_rb)) {
> + rb_erase(&grp->bb_avg_fragment_size_rb,
> + &sbi->s_mb_avg_fragment_size_root);
> + RB_CLEAR_NODE(&grp->bb_avg_fragment_size_rb);
> + }
> +
> + ext4_mb_rb_insert(&sbi->s_mb_avg_fragment_size_root,
> + &grp->bb_avg_fragment_size_rb,
> + ext4_mb_avg_fragment_size_cmp);
> + write_unlock(&sbi->s_mb_rb_lock);
> +}
> +
> +/*
> + * Choose next group by traversing largest_free_order lists. Return 0 if next
> + * group was selected optimally. Return 1 if next group was not selected
> + * optimally. Updates *new_cr if cr level needs an update.
> + */
> +static int ext4_mb_choose_next_group_cr0(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
> + struct ext4_group_info *iter, *grp;
> + int i;
> +
> + if (ac->ac_status == AC_STATUS_FOUND)
> + return 1;
> +
> + grp = NULL;
> + for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
> + if (list_empty(&sbi->s_mb_largest_free_orders[i]))
> + continue;
> + read_lock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (list_empty(&sbi->s_mb_largest_free_orders[i])) {
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + continue;
> + }
> + grp = NULL;
> + list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],
> + bb_largest_free_order_node) {
> + /*
> + * Perform this check without a lock, once we lock
> + * the group, we'll perform this check again.
> + */
> + if (likely(ext4_mb_good_group(ac, iter->bb_group, 0))) {
> + grp = iter;
> + break;
> + }
> + }
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (grp)
> + break;
> + }
> +
> + if (!grp) {
> + /* Increment cr and search again */
> + *new_cr = 1;
> + } else {
> + *group = grp->bb_group;
> + ac->ac_last_optimal_group = *group;
> + }
> + return 0;
> +}
> +
> +/*
> + * Choose next group by traversing average fragment size tree. Return 0 if next
> + * group was selected optimally. Return 1 if next group could not selected
> + * optimally (due to lock contention). Updates *new_cr if cr lvel needs an
> + * update.
> + */
> +static int ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
> + int avg_fragment_size, best_so_far;
> + struct rb_node *node, *found;
> + struct ext4_group_info *grp;
> +
> + /*
> + * If there is contention on the lock, instead of waiting for the lock
> + * to become available, just continue searching lineraly. We'll resume
> + * our rb tree search later starting at ac->ac_last_optimal_group.
> + */
> + if (!read_trylock(&sbi->s_mb_rb_lock))
> + return 1;
> +
> + if (ac->ac_flags & EXT4_MB_CR1_OPTIMIZED) {
> + /* We have found something at CR 1 in the past */
> + grp = ext4_get_group_info(ac->ac_sb, ac->ac_last_optimal_group);
> + for (found = rb_next(&grp->bb_avg_fragment_size_rb); found != NULL;
> + found = rb_next(found)) {
> + grp = rb_entry(found, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + /*
> + * Perform this check without locking, we'll lock later
> + * to confirm.
> + */
> + if (likely(ext4_mb_good_group(ac, grp->bb_group, 1)))
> + break;
> + }
> +
> + goto done;
> + }
> +
> + node = sbi->s_mb_avg_fragment_size_root.rb_node;
> + best_so_far = 0;
> + found = NULL;
> +
> + while (node) {
> + grp = rb_entry(node, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + /*
> + * Perform this check without locking, we'll lock later to confirm.
> + */
> + if (ext4_mb_good_group(ac, grp->bb_group, 1)) {
> + avg_fragment_size = grp->bb_fragments ?
> + grp->bb_free / grp->bb_fragments : 0;
> + if (!best_so_far || avg_fragment_size < best_so_far) {
> + best_so_far = avg_fragment_size;
> + found = node;
> + }
> + }
> + if (avg_fragment_size > ac->ac_g_ex.fe_len)
> + node = node->rb_right;
> + else
> + node = node->rb_left;
> + }
> +
> +done:
> + if (found) {
> + grp = rb_entry(found, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + *group = grp->bb_group;
> + ac->ac_flags |= EXT4_MB_CR1_OPTIMIZED;
> + } else {
> + *new_cr = 2;
> + }
> +
> + read_unlock(&sbi->s_mb_rb_lock);
> + ac->ac_last_optimal_group = *group;
> + return 0;
> +}
> +
> +/*
> + * ext4_mb_choose_next_group: choose next group for allocation.
> + *
> + * @ac Allocation Context
> + * @new_cr This is an output parameter. If the there is no good group available
> + * at current CR level, this field is updated to indicate the new cr
> + * level that should be used.
> + * @group This is an input / output parameter. As an input it indicates the last
> + * group used for allocation. As output, this field indicates the
> + * next group that should be used.
> + * @ngroups Total number of groups
> + */
> +static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + int ret;
> +
> + *new_cr = ac->ac_criteria;
> +
> + if (!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN) ||
> + *new_cr >= 2 ||
> + !ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))
> + goto inc_and_return;
> +
> + if (*new_cr == 0) {
> + ret = ext4_mb_choose_next_group_cr0(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + if (*new_cr == 1) {
> + ret = ext4_mb_choose_next_group_cr1(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + return;
> +
> +inc_and_return:
> + /*
> + * Artificially restricted ngroups for non-extent
> + * files makes group > ngroups possible on first loop.
> + */
> + *group = *group + 1;
> + if (*group >= ngroups)
> + *group = 0;
> +}
> +
> /*
> * Cache the order of the largest free extent we have available in this block
> * group.
> @@ -751,18 +1001,32 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> static void
> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
> {
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> int i;
> - int bits;
>
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_del_init(&grp->bb_largest_free_order_node);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> grp->bb_largest_free_order = -1; /* uninit */
>
> - bits = MB_NUM_ORDERS(sb) - 1;
> - for (i = bits; i >= 0; i--) {
> + for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
> if (grp->bb_counters[i] > 0) {
> grp->bb_largest_free_order = i;
> break;
> }
> }
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_add_tail(&grp->bb_largest_free_order_node,
> + &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> }
>
> static noinline_for_stack
> @@ -818,6 +1082,7 @@ void ext4_mb_generate_buddy(struct super_block *sb,
> period = get_cycles() - period;
> atomic_inc(&sbi->s_mb_buddies_generated);
> atomic64_add(period, &sbi->s_mb_generation_time);
> + mb_update_avg_fragment_size(sb, grp);
> }
>
> /* The buddy information is attached the buddy cache inode
> @@ -1517,6 +1782,7 @@ static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
>
> done:
> mb_set_largest_free_order(sb, e4b->bd_info);
> + mb_update_avg_fragment_size(sb, e4b->bd_info);
> mb_check_buddy(e4b);
> }
>
> @@ -1653,6 +1919,7 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
> }
> mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
>
> + mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);
> ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
> mb_check_buddy(e4b);
>
> @@ -2346,17 +2613,20 @@ ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
> * from the goal value specified
> */
> group = ac->ac_g_ex.fe_group;
> + ac->ac_last_optimal_group = group;
> prefetch_grp = group;
>
> - for (i = 0; i < ngroups; group++, i++) {
> - int ret = 0;
> + for (i = 0; i < ngroups; i++) {
> + int ret = 0, new_cr;
> +
> cond_resched();
> - /*
> - * Artificially restricted ngroups for non-extent
> - * files makes group > ngroups possible on first loop.
> - */
> - if (group >= ngroups)
> - group = 0;
> +
> + ext4_mb_choose_next_group(ac, &new_cr, &group, ngroups);
> +
> + if (new_cr != cr) {
> + cr = new_cr;
> + goto repeat;
> + }
>
> /*
> * Batch reads of the block allocation bitmaps
> @@ -2696,7 +2966,10 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
> INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
> init_rwsem(&meta_group_info[i]->alloc_sem);
> meta_group_info[i]->bb_free_root = RB_ROOT;
> + INIT_LIST_HEAD(&meta_group_info[i]->bb_largest_free_order_node);
> + RB_CLEAR_NODE(&meta_group_info[i]->bb_avg_fragment_size_rb);
> meta_group_info[i]->bb_largest_free_order = -1; /* uninit */
> + meta_group_info[i]->bb_group = group;
>
> mb_group_bb_bitmap_alloc(sb, meta_group_info[i], group);
> return 0;
> @@ -2886,6 +3159,22 @@ int ext4_mb_init(struct super_block *sb)
> i++;
> } while (i < MB_NUM_ORDERS(sb));
>
> + sbi->s_mb_avg_fragment_size_root = RB_ROOT;
> + sbi->s_mb_largest_free_orders =
> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(struct list_head),
> + GFP_KERNEL);
> + if (!sbi->s_mb_largest_free_orders)
> + goto out;
> + sbi->s_mb_largest_free_orders_locks =
> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(rwlock_t),
> + GFP_KERNEL);
> + if (!sbi->s_mb_largest_free_orders_locks)
> + goto out;
> + for (i = 0; i < MB_NUM_ORDERS(sb); i++) {
> + INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]);
> + rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);
> + }
> + rwlock_init(&sbi->s_mb_rb_lock);
>
> spin_lock_init(&sbi->s_md_lock);
> sbi->s_mb_free_pending = 0;
> @@ -2949,6 +3238,8 @@ int ext4_mb_init(struct super_block *sb)
> free_percpu(sbi->s_locality_groups);
> sbi->s_locality_groups = NULL;
> out:
> + kfree(sbi->s_mb_largest_free_orders);
> + kfree(sbi->s_mb_largest_free_orders_locks);
> kfree(sbi->s_mb_offsets);
> sbi->s_mb_offsets = NULL;
> kfree(sbi->s_mb_maxs);
> @@ -3005,6 +3296,7 @@ int ext4_mb_release(struct super_block *sb)
> kvfree(group_info);
> rcu_read_unlock();
> }
> + kfree(sbi->s_mb_largest_free_orders);
> kfree(sbi->s_mb_offsets);
> kfree(sbi->s_mb_maxs);
> iput(sbi->s_buddy_cache);
> diff --git a/fs/ext4/mballoc.h b/fs/ext4/mballoc.h
> index 02861406932f..1e86a8a0460d 100644
> --- a/fs/ext4/mballoc.h
> +++ b/fs/ext4/mballoc.h
> @@ -166,6 +166,7 @@ struct ext4_allocation_context {
> /* copy of the best found extent taken before preallocation efforts */
> struct ext4_free_extent ac_f_ex;
>
> + ext4_group_t ac_last_optimal_group;
> __u32 ac_groups_considered;
> __u16 ac_groups_scanned;
> __u16 ac_found;
> diff --git a/fs/ext4/super.c b/fs/ext4/super.c
> index 0f0db49031dc..a14363654cfd 100644
> --- a/fs/ext4/super.c
> +++ b/fs/ext4/super.c
> @@ -154,6 +154,7 @@ static inline void __ext4_read_bh(struct buffer_head *bh, int op_flags,
> clear_buffer_verified(bh);
>
> bh->b_end_io = end_io ? end_io : end_buffer_read_sync;
> +
> get_bh(bh);
> submit_bh(REQ_OP_READ, op_flags, bh);
> }
> @@ -1687,7 +1688,7 @@ enum {
> Opt_dioread_nolock, Opt_dioread_lock,
> Opt_discard, Opt_nodiscard, Opt_init_itable, Opt_noinit_itable,
> Opt_max_dir_size_kb, Opt_nojournal_checksum, Opt_nombcache,
> - Opt_prefetch_block_bitmaps,
> + Opt_prefetch_block_bitmaps, Opt_mb_optimize_scan,
> #ifdef CONFIG_EXT4_DEBUG
> Opt_fc_debug_max_replay, Opt_fc_debug_force
> #endif
> @@ -1788,6 +1789,7 @@ static const match_table_t tokens = {
> {Opt_nombcache, "nombcache"},
> {Opt_nombcache, "no_mbcache"}, /* for backward compatibility */
> {Opt_prefetch_block_bitmaps, "prefetch_block_bitmaps"},
> + {Opt_mb_optimize_scan, "mb_optimize_scan"},
> {Opt_removed, "check=none"}, /* mount option from ext2/3 */
> {Opt_removed, "nocheck"}, /* mount option from ext2/3 */
> {Opt_removed, "reservation"}, /* mount option from ext2/3 */
> @@ -2008,6 +2010,8 @@ static const struct mount_opts {
> {Opt_nombcache, EXT4_MOUNT_NO_MBCACHE, MOPT_SET},
> {Opt_prefetch_block_bitmaps, EXT4_MOUNT_PREFETCH_BLOCK_BITMAPS,
> MOPT_SET},
> + {Opt_mb_optimize_scan, EXT4_MOUNT2_MB_OPTIMIZE_SCAN,
> + MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
> #ifdef CONFIG_EXT4_DEBUG
> {Opt_fc_debug_force, EXT4_MOUNT2_JOURNAL_FAST_COMMIT,
> MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
> --
> 2.30.0.478.g8a0d178c01-goog
>
With your parch we have actual information about all groups in memory but ext4_mb_seq_groups_show() process all groups to show output. Should we improve this function somehow? Or probably add new statistics there? Or news seq, that outputs sorted lists. This is optional. Just for discussion.
Best regards,
Artem Blagodarenko.
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-16 19:39 ` Благодаренко Артём
@ 2021-02-16 22:36 ` Andreas Dilger
2021-02-22 3:59 ` harshad shirwadkar
0 siblings, 1 reply; 17+ messages in thread
From: Andreas Dilger @ 2021-02-16 22:36 UTC (permalink / raw)
To: Благодаренко Артём
Cc: Harshad Shirwadkar, linux-ext4, Theodore Y. Ts'o,
Alex Zhuravlev, Shuichi Ihara
[-- Attachment #1: Type: text/plain, Size: 7028 bytes --]
On Feb 16, 2021, at 12:39 PM, Благодаренко Артём <artem.blagodarenko@gmail.com> wrote:
> Thanks for this useful optimisation.
>
> Some comments bellow.
>
>> On 9 Feb 2021, at 23:28, Harshad Shirwadkar <harshadshirwadkar@gmail.com> wrote:
>>
>> Instead of traversing through groups linearly, scan groups in specific
>> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
>> largest free order >= the order of the request. So, with this patch,
>> we maintain lists for each possible order and insert each group into a
>> list based on the largest free order in its buddy bitmap. During cr 0
>> allocation, we traverse these lists in the increasing order of largest
>> free orders. This allows us to find a group with the best available cr
>> 0 match in constant time. If nothing can be found, we fallback to cr 1
>> immediately.
>>
>> At CR1, the story is slightly different. We want to traverse in the
>> order of increasing average fragment size. For CR1, we maintain a rb
>> tree of groupinfos which is sorted by average fragment size. Instead
>> of traversing linearly, at CR1, we traverse in the order of increasing
>> average fragment size, starting at the most optimal group. This brings
>> down cr 1 search complexity to log(num groups).
>>
>> For cr >= 2, we just perform the linear search as before. Also, in
>> case of lock contention, we intermittently fallback to linear search
>> even in CR 0 and CR 1 cases. This allows us to proceed during the
>> allocation path even in case of high contention.
>>
>> There is an opportunity to do optimization at CR2 too. That's because
>> at CR2 we only consider groups where bb_free counter (number of free
>> blocks) is greater than the request extent size. That's left as future
>> work.
>>
>> +static int
>> +ext4_mb_avg_fragment_size_cmp(struct rb_node *rb1, struct rb_node *rb2)
>> +{
>> + struct ext4_group_info *grp1 = rb_entry(rb1,
>> + struct ext4_group_info,
>> + bb_avg_fragment_size_rb);
>> + struct ext4_group_info *grp2 = rb_entry(rb2,
>> + struct ext4_group_info,
>> + bb_avg_fragment_size_rb);
>> + int num_frags_1, num_frags_2;
>> +
>> + num_frags_1 = grp1->bb_fragments ?
>> + grp1->bb_free / grp1->bb_fragments : 0;
>> + num_frags_2 = grp2->bb_fragments ?
>> + grp2->bb_free / grp2->bb_fragments : 0;
>> +
>> + return (num_frags_1 < num_frags_2);
>> +}
>> +
>> +/*
>> + * Reinsert grpinfo into the avg_fragment_size tree with new average
>> + * fragment size.
>> + */
>
> Walk along the ngroups linked elements in worst case for every mb_free_blocks and mb_mark_used which are quite frequently executed actions.
> If double-linked list is used for avg_fragments this function will make this change without iterating through the list:
> 1. Check with previous element. If smaller, then commute
> 2. Check with next element. If greater, then commute.
I was wondering about the cost of the list/tree maintenance as well,
especially since there was a post from "kernel test robot" that this
patch introduced a performance regression.
The tree insertion/removal overhead I think Artem's proposal above would
improve, since it may be that a group will not move in the tree much?
It would also make sense for totally full groups to be kept out of the
rb tree entirely, since they do not provide any value in that case (the
full groups will never be selected for allocations), and they just add
to the tree depth and potentially cause an imbalance if there are many
of them. That also has the benefit of the rbtree efficiency *improving*
as the filesystem gets more full, which is right when it is most needed.
It might also make sense to keep totally empty groups out of the rbtree,
since they should always be found in cr0 already if the allocation is
large enough to fill the whole group? Having a smaller rbtree makes
every insertion/removal that much more efficient.
Those groups will naturally be re-added into the rbtree when they have
blocks freed or allocated, so not much added complexity.
Does it make sense to disable "mb_optimize_scan" if filesystems are
smaller than a certain threshold? Clearly, if there are only 1-2
groups, maintaining a list and rbtree has no real value, and with
only a handful of groups (< 16?) linear searching is probably as fast
or faster than maintaining the two data structures. That is similar
to e.g. bubble sort vs. quicksort, where it is more efficient to sort
a list of ~5-8 entries with a dumb/fast algorithm instead of a complex
algorithm that is more efficient at larger scales. That would also
(likely) quiet the kernel test robot, if we think that its testing is
not representative of real-world usage.
> On Feb 11, 2021, at 3:30 AM, Andreas Dilger <adilger@dilger.ca> wrote:
>> This function would be more efficient to do the list move under a single
>> write lock if the order doesn't change. The order loop would just
>> save the largest free order, then grab the write lock, do the list_del(),
>> set bb_largest_free_order, and list_add_tail():
>>
>> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
>> {
>> struct ext4_sb_info *sbi = EXT4_SB(sb);
>> int i, new_order = -1;
>>
>> for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
>> if (grp->bb_counters[i] > 0) {
>> new_order = i;
>> break;
>> }
>> }
>> if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
>> write_lock(&sbi->s_mb_largest_free_orders_locks[
>> grp->bb_largest_free_order]);
>> list_del_init(&grp->bb_largest_free_order_node);
>>
>> if (new_order != grp->bb_largest_free_order) {
>> write_unlock(&sbi->s_mb_largest_free_orders_locks[
>> grp->bb_largest_free_order]);
>> grp->bb_largest_free_order = new_order;
>> write_lock(&sbi->s_mb_largest_free_orders_locks[
>> grp->bb_largest_free_order]);
>> }
>> list_add_tail(&grp->bb_largest_free_order_node,
>> &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
>> write_unlock(&sbi->s_mb_largest_free_orders_locks[
>> grp->bb_largest_free_order]);
>> }
>> }
In looking at my previous comment, I wonder if we could further reduce
the list locking here by not moving an entry to the end of the *same*
list if it is not currently at the head? Since it was (presumably)
just moved to the end of the list by a recent allocation, it is very
likely that some other group will be chosen from the list head, so
moving within the list to maintain strict LRU is probably just extra
locking overhead that can be avoided...
Also, it isn't clear if *freeing* blocks from a group should move it
to the end of the same list, or just leave it as-is? If there are
more frees from the list it is likely to be added to a new list soon,
and if there are no more frees, then it could stay in the same order.
Cheers, Andreas
[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-16 22:36 ` Andreas Dilger
@ 2021-02-22 3:59 ` harshad shirwadkar
2021-02-23 18:39 ` harshad shirwadkar
2021-02-26 3:43 ` Andreas Dilger
0 siblings, 2 replies; 17+ messages in thread
From: harshad shirwadkar @ 2021-02-22 3:59 UTC (permalink / raw)
To: Andreas Dilger
Cc: Благодаренко Артём,
Ext4 Developers List, Theodore Y. Ts'o, Alex Zhuravlev,
Shuichi Ihara
Thank you for all the feedback Andreas and Artem. Some comments below:
> >
> > Walk along the ngroups linked elements in worst case for every mb_free_blocks and mb_mark_used which are quite frequently executed actions.
> > If double-linked list is used for avg_fragments this function will make this change without iterating through the list:
> > 1. Check with previous element. If smaller, then commute
> > 2. Check with next element. If greater, then commute.
So given that groups are organized by avg_fragment_size in a tree, the
worst case for every mb_free_blocks() and mb_mark_used() is actually
log(ngroups). But I get your idea. Problem with doing that with
rb_tree though is that rb_next() and rb_prev() are not constant time
functions since these functions would need to traverse a part of the
tree to determine the next / previous element. So I think this
optimization may not result in performance improvement.
>
> I was wondering about the cost of the list/tree maintenance as well,
> especially since there was a post from "kernel test robot" that this
> patch introduced a performance regression.
Yeah, I'm pretty sure that the kernel test robot is complaining mainly
because of list/tree maintenance. I think if this optimization is
turned off, we probably should not even maintain the tree / lists.
That has one downside that is that we will have to disallow setting
this option during remount, which I guess is okay?
>
> The tree insertion/removal overhead I think Artem's proposal above would
> improve, since it may be that a group will not move in the tree much?
Like I mentioned above, given that we have an average fragment size
tree, checking neighboring groups is not a constant time operation. So
I don't think that will change performance much.
>
> It would also make sense for totally full groups to be kept out of the
> rb tree entirely, since they do not provide any value in that case (the
> full groups will never be selected for allocations), and they just add
> to the tree depth and potentially cause an imbalance if there are many
> of them. That also has the benefit of the rbtree efficiency *improving*
> as the filesystem gets more full, which is right when it is most needed.
Ack
>
> It might also make sense to keep totally empty groups out of the rbtree,
> since they should always be found in cr0 already if the allocation is
> large enough to fill the whole group? Having a smaller rbtree makes
> every insertion/removal that much more efficient.
Ack
>
> Those groups will naturally be re-added into the rbtree when they have
> blocks freed or allocated, so not much added complexity.
>
>
> Does it make sense to disable "mb_optimize_scan" if filesystems are
> smaller than a certain threshold? Clearly, if there are only 1-2
> groups, maintaining a list and rbtree has no real value, and with
> only a handful of groups (< 16?) linear searching is probably as fast
> or faster than maintaining the two data structures. That is similar
> to e.g. bubble sort vs. quicksort, where it is more efficient to sort
> a list of ~5-8 entries with a dumb/fast algorithm instead of a complex
> algorithm that is more efficient at larger scales. That would also
> (likely) quiet the kernel test robot, if we think that its testing is
> not representative of real-world usage.
Ack, these are good optimizations. I'll add these in V3.
Besides the optimizations mentioned here, I also think we should add
"mb_optimize_linear_limit" or such sysfs tunable which will control
how many groups should mballoc search linearly before using tree /
lists for allocation? That would help us with the disk seek time
performance.
We discussed on our last call that we probably should consult with the
block device's request queue to check if the underlying block device
is rotational or not. However, we also discussed that for more complex
devices (such as DMs setup on top of HDD and SSD etc), whether the
device is rotational or not is not a binary answer and we would need a
more complex interface (such as logical range to "is_rotational"
table) to make intelligent choice in the file system. Also, in such
cases, it is not clear if such a table needs to be passed to the file
system during mkfs time? or at mount time? or at run time?
Given the number of unknowns in the above discussion, I propose that
we start simple and evolve later. So my proposal is that we add a
"mb_optimize_linear_limit" tunable that accepts an integer value. In
the kernel, for non-rotational devices, that value will be defaulted
to 0 (which means no linear scan) and for rotational devices, that
value will be defaulted to a reasonable value (-- not sure what that
value would be though - 4?). This default can be overridden using the
sysfs interface. We can later evolve this interface to accept more
complex input such as logical range to rotational status.
Does that sound reasonable?
Thanks,
Harshad
>
> > On Feb 11, 2021, at 3:30 AM, Andreas Dilger <adilger@dilger.ca> wrote:
>
> >> This function would be more efficient to do the list move under a single
> >> write lock if the order doesn't change. The order loop would just
> >> save the largest free order, then grab the write lock, do the list_del(),
> >> set bb_largest_free_order, and list_add_tail():
> >>
> >> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
> >> {
> >> struct ext4_sb_info *sbi = EXT4_SB(sb);
> >> int i, new_order = -1;
> >>
> >> for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
> >> if (grp->bb_counters[i] > 0) {
> >> new_order = i;
> >> break;
> >> }
> >> }
> >> if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> >> write_lock(&sbi->s_mb_largest_free_orders_locks[
> >> grp->bb_largest_free_order]);
> >> list_del_init(&grp->bb_largest_free_order_node);
> >>
> >> if (new_order != grp->bb_largest_free_order) {
> >> write_unlock(&sbi->s_mb_largest_free_orders_locks[
> >> grp->bb_largest_free_order]);
> >> grp->bb_largest_free_order = new_order;
> >> write_lock(&sbi->s_mb_largest_free_orders_locks[
> >> grp->bb_largest_free_order]);
> >> }
> >> list_add_tail(&grp->bb_largest_free_order_node,
> >> &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
> >> write_unlock(&sbi->s_mb_largest_free_orders_locks[
> >> grp->bb_largest_free_order]);
> >> }
> >> }
>
> In looking at my previous comment, I wonder if we could further reduce
> the list locking here by not moving an entry to the end of the *same*
> list if it is not currently at the head? Since it was (presumably)
> just moved to the end of the list by a recent allocation, it is very
> likely that some other group will be chosen from the list head, so
> moving within the list to maintain strict LRU is probably just extra
> locking overhead that can be avoided...
>
> Also, it isn't clear if *freeing* blocks from a group should move it
> to the end of the same list, or just leave it as-is? If there are
> more frees from the list it is likely to be added to a new list soon,
> and if there are no more frees, then it could stay in the same order.
>
>
> Cheers, Andreas
>
>
>
>
>
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-22 3:59 ` harshad shirwadkar
@ 2021-02-23 18:39 ` harshad shirwadkar
2021-02-26 3:43 ` Andreas Dilger
1 sibling, 0 replies; 17+ messages in thread
From: harshad shirwadkar @ 2021-02-23 18:39 UTC (permalink / raw)
To: Andreas Dilger
Cc: Благодаренко Артём,
Ext4 Developers List, Theodore Y. Ts'o, Alex Zhuravlev,
Shuichi Ihara
Hmmm, while I was going through my patches, I realized that if
MB_OPTIMIZE_SCAN mount option is not set, we don't maintain the lists
as well as the tree. Also, if this option is not set, no new locks are
taken (list locks, tree lock). This makes me wonder why does intel bot
see regression with these patches when this mount option is turned
off? I'll try to reproduce the regression to see what's going on, but
thought that I'd just drop a note here since we have assumed in our
discussions that intel bot regression is coming due to data structure
maintenance.
- Harshad
On Sun, Feb 21, 2021 at 7:59 PM harshad shirwadkar
<harshadshirwadkar@gmail.com> wrote:
>
> Thank you for all the feedback Andreas and Artem. Some comments below:
>
> > >
> > > Walk along the ngroups linked elements in worst case for every mb_free_blocks and mb_mark_used which are quite frequently executed actions.
> > > If double-linked list is used for avg_fragments this function will make this change without iterating through the list:
> > > 1. Check with previous element. If smaller, then commute
> > > 2. Check with next element. If greater, then commute.
> So given that groups are organized by avg_fragment_size in a tree, the
> worst case for every mb_free_blocks() and mb_mark_used() is actually
> log(ngroups). But I get your idea. Problem with doing that with
> rb_tree though is that rb_next() and rb_prev() are not constant time
> functions since these functions would need to traverse a part of the
> tree to determine the next / previous element. So I think this
> optimization may not result in performance improvement.
> >
> > I was wondering about the cost of the list/tree maintenance as well,
> > especially since there was a post from "kernel test robot" that this
> > patch introduced a performance regression.
> Yeah, I'm pretty sure that the kernel test robot is complaining mainly
> because of list/tree maintenance. I think if this optimization is
> turned off, we probably should not even maintain the tree / lists.
> That has one downside that is that we will have to disallow setting
> this option during remount, which I guess is okay?
> >
> > The tree insertion/removal overhead I think Artem's proposal above would
> > improve, since it may be that a group will not move in the tree much?
> Like I mentioned above, given that we have an average fragment size
> tree, checking neighboring groups is not a constant time operation. So
> I don't think that will change performance much.
> >
> > It would also make sense for totally full groups to be kept out of the
> > rb tree entirely, since they do not provide any value in that case (the
> > full groups will never be selected for allocations), and they just add
> > to the tree depth and potentially cause an imbalance if there are many
> > of them. That also has the benefit of the rbtree efficiency *improving*
> > as the filesystem gets more full, which is right when it is most needed.
> Ack
> >
> > It might also make sense to keep totally empty groups out of the rbtree,
> > since they should always be found in cr0 already if the allocation is
> > large enough to fill the whole group? Having a smaller rbtree makes
> > every insertion/removal that much more efficient.
> Ack
> >
> > Those groups will naturally be re-added into the rbtree when they have
> > blocks freed or allocated, so not much added complexity.
> >
> >
> > Does it make sense to disable "mb_optimize_scan" if filesystems are
> > smaller than a certain threshold? Clearly, if there are only 1-2
> > groups, maintaining a list and rbtree has no real value, and with
> > only a handful of groups (< 16?) linear searching is probably as fast
> > or faster than maintaining the two data structures. That is similar
> > to e.g. bubble sort vs. quicksort, where it is more efficient to sort
> > a list of ~5-8 entries with a dumb/fast algorithm instead of a complex
> > algorithm that is more efficient at larger scales. That would also
> > (likely) quiet the kernel test robot, if we think that its testing is
> > not representative of real-world usage.
> Ack, these are good optimizations. I'll add these in V3.
>
> Besides the optimizations mentioned here, I also think we should add
> "mb_optimize_linear_limit" or such sysfs tunable which will control
> how many groups should mballoc search linearly before using tree /
> lists for allocation? That would help us with the disk seek time
> performance.
>
> We discussed on our last call that we probably should consult with the
> block device's request queue to check if the underlying block device
> is rotational or not. However, we also discussed that for more complex
> devices (such as DMs setup on top of HDD and SSD etc), whether the
> device is rotational or not is not a binary answer and we would need a
> more complex interface (such as logical range to "is_rotational"
> table) to make intelligent choice in the file system. Also, in such
> cases, it is not clear if such a table needs to be passed to the file
> system during mkfs time? or at mount time? or at run time?
>
> Given the number of unknowns in the above discussion, I propose that
> we start simple and evolve later. So my proposal is that we add a
> "mb_optimize_linear_limit" tunable that accepts an integer value. In
> the kernel, for non-rotational devices, that value will be defaulted
> to 0 (which means no linear scan) and for rotational devices, that
> value will be defaulted to a reasonable value (-- not sure what that
> value would be though - 4?). This default can be overridden using the
> sysfs interface. We can later evolve this interface to accept more
> complex input such as logical range to rotational status.
>
> Does that sound reasonable?
>
> Thanks,
> Harshad
>
> >
> > > On Feb 11, 2021, at 3:30 AM, Andreas Dilger <adilger@dilger.ca> wrote:
> >
> > >> This function would be more efficient to do the list move under a single
> > >> write lock if the order doesn't change. The order loop would just
> > >> save the largest free order, then grab the write lock, do the list_del(),
> > >> set bb_largest_free_order, and list_add_tail():
> > >>
> > >> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
> > >> {
> > >> struct ext4_sb_info *sbi = EXT4_SB(sb);
> > >> int i, new_order = -1;
> > >>
> > >> for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
> > >> if (grp->bb_counters[i] > 0) {
> > >> new_order = i;
> > >> break;
> > >> }
> > >> }
> > >> if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> > >> write_lock(&sbi->s_mb_largest_free_orders_locks[
> > >> grp->bb_largest_free_order]);
> > >> list_del_init(&grp->bb_largest_free_order_node);
> > >>
> > >> if (new_order != grp->bb_largest_free_order) {
> > >> write_unlock(&sbi->s_mb_largest_free_orders_locks[
> > >> grp->bb_largest_free_order]);
> > >> grp->bb_largest_free_order = new_order;
> > >> write_lock(&sbi->s_mb_largest_free_orders_locks[
> > >> grp->bb_largest_free_order]);
> > >> }
> > >> list_add_tail(&grp->bb_largest_free_order_node,
> > >> &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
> > >> write_unlock(&sbi->s_mb_largest_free_orders_locks[
> > >> grp->bb_largest_free_order]);
> > >> }
> > >> }
> >
> > In looking at my previous comment, I wonder if we could further reduce
> > the list locking here by not moving an entry to the end of the *same*
> > list if it is not currently at the head? Since it was (presumably)
> > just moved to the end of the list by a recent allocation, it is very
> > likely that some other group will be chosen from the list head, so
> > moving within the list to maintain strict LRU is probably just extra
> > locking overhead that can be avoided...
> >
> > Also, it isn't clear if *freeing* blocks from a group should move it
> > to the end of the same list, or just leave it as-is? If there are
> > more frees from the list it is likely to be added to a new list soon,
> > and if there are no more frees, then it could stay in the same order.
> >
> >
> > Cheers, Andreas
> >
> >
> >
> >
> >
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-22 3:59 ` harshad shirwadkar
2021-02-23 18:39 ` harshad shirwadkar
@ 2021-02-26 3:43 ` Andreas Dilger
2021-02-26 4:06 ` harshad shirwadkar
1 sibling, 1 reply; 17+ messages in thread
From: Andreas Dilger @ 2021-02-26 3:43 UTC (permalink / raw)
To: harshad shirwadkar
Cc: Благодаренко Артём,
Ext4 Developers List, Theodore Y. Ts'o, Alex Zhuravlev,
Shuichi Ihara
[-- Attachment #1: Type: text/plain, Size: 8088 bytes --]
On Feb 21, 2021, at 8:59 PM, harshad shirwadkar <harshadshirwadkar@gmail.com> wrote:
>
> Thank you for all the feedback Andreas and Artem. Some comments below:
Thank you for working on this. It is definitely an area that can use
this improvement.
>> I was wondering about the cost of the list/tree maintenance as well,
>> especially since there was a post from "kernel test robot" that this
>> patch introduced a performance regression.
>
> Yeah, I'm pretty sure that the kernel test robot is complaining mainly
> because of list/tree maintenance. I think if this optimization is
> turned off, we probably should not even maintain the tree / lists.
> That has one downside that is that we will have to disallow setting
> this option during remount, which I guess is okay?
I think it is reasonable to not be able to change this at runtime.
This would only make a difference for a limited number of testers,
and virtually all users will never know it exists at all.
>> It would also make sense for totally full groups to be kept out of the
>> rb tree entirely, since they do not provide any value in that case (the
>> full groups will never be selected for allocations), and they just add
>> to the tree depth and potentially cause an imbalance if there are many
>> of them. That also has the benefit of the rbtree efficiency *improving*
>> as the filesystem gets more full, which is right when it is most needed.
>
> Ack
>
>> It might also make sense to keep totally empty groups out of the rbtree,
>> since they should always be found in cr0 already if the allocation is
>> large enough to fill the whole group? Having a smaller rbtree makes
>> every insertion/removal that much more efficient.
>
> Ack
>
>> Those groups will naturally be re-added into the rbtree when they have
>> blocks freed or allocated, so not much added complexity.
>>
>>
>> Does it make sense to disable "mb_optimize_scan" if filesystems are
>> smaller than a certain threshold? Clearly, if there are only 1-2
>> groups, maintaining a list and rbtree has no real value, and with
>> only a handful of groups (< 16?) linear searching is probably as fast
>> or faster than maintaining the two data structures. That is similar
>> to e.g. bubble sort vs. quicksort, where it is more efficient to sort
>> a list of ~5-8 entries with a dumb/fast algorithm instead of a complex
>> algorithm that is more efficient at larger scales. That would also
>> (likely) quiet the kernel test robot, if we think that its testing is
>> not representative of real-world usage.
>
> Ack, these are good optimizations. I'll add these in V3.
For testing purposes it should be possible to have "mb_optimize_scan=1"
force the use of this option, even if the filesystem is small.
> Besides the optimizations mentioned here, I also think we should add
> "mb_optimize_linear_limit" or such sysfs tunable which will control
> how many groups should mballoc search linearly before using tree /
> lists for allocation? That would help us with the disk seek time
> performance.
There is already a linear search threshold parameters for mballoc,
namely mb_min_to_scan and mb_max_to_scan that could be used for this.
I think we could use "mb_min_to_scan=10" (the current default), or
maybe shrink this a bit (4?) if "mb_optimize_scan" is enabled.
> We discussed on our last call that we probably should consult with the
> block device's request queue to check if the underlying block device
> is rotational or not. However, we also discussed that for more complex
> devices (such as DMs setup on top of HDD and SSD etc), whether the
> device is rotational or not is not a binary answer and we would need a
> more complex interface (such as logical range to "is_rotational"
> table) to make intelligent choice in the file system. Also, in such
> cases, it is not clear if such a table needs to be passed to the file
> system during mkfs time? or at mount time? or at run time?
I don't think the hybrid case is very important yet. By far the
most common case is going to be "rotational=1" or "rotational=0"
for the whole device, so we should start by only optimizing for
those cases. DM looks like it returns "rotational=0" correctly
when a composite device it is made of entirely non-rotational
devices and "rotational=1" as it should when it is a hybrid
HDD/SSD device (which I have in my local system).
> Given the number of unknowns in the above discussion, I propose that
> we start simple and evolve later. So my proposal is that we add a
> "mb_optimize_linear_limit" tunable that accepts an integer value. In
> the kernel, for non-rotational devices, that value will be defaulted
> to 0 (which means no linear scan) and for rotational devices, that
> value will be defaulted to a reasonable value (-- not sure what that
> value would be though - 4?). This default can be overridden using the
> sysfs interface. We can later evolve this interface to accept more
> complex input such as logical range to rotational status.
>
> Does that sound reasonable?
Yes, modulo using the existing "mb_min_to_scan" parameter for this.
I think 4 or 8 or 10 groups is reasonable (512MB, 1GB, 1.25GB),
since if it needs a seek anyway then we may as well find a good
group for this.
Cheers, Andreas
>
>>
>>> On Feb 11, 2021, at 3:30 AM, Andreas Dilger <adilger@dilger.ca> wrote:
>>
>>>> This function would be more efficient to do the list move under a single
>>>> write lock if the order doesn't change. The order loop would just
>>>> save the largest free order, then grab the write lock, do the list_del(),
>>>> set bb_largest_free_order, and list_add_tail():
>>>>
>>>> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
>>>> {
>>>> struct ext4_sb_info *sbi = EXT4_SB(sb);
>>>> int i, new_order = -1;
>>>>
>>>> for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
>>>> if (grp->bb_counters[i] > 0) {
>>>> new_order = i;
>>>> break;
>>>> }
>>>> }
>>>> if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
>>>> write_lock(&sbi->s_mb_largest_free_orders_locks[
>>>> grp->bb_largest_free_order]);
>>>> list_del_init(&grp->bb_largest_free_order_node);
>>>>
>>>> if (new_order != grp->bb_largest_free_order) {
>>>> write_unlock(&sbi->s_mb_largest_free_orders_locks[
>>>> grp->bb_largest_free_order]);
>>>> grp->bb_largest_free_order = new_order;
>>>> write_lock(&sbi->s_mb_largest_free_orders_locks[
>>>> grp->bb_largest_free_order]);
>>>> }
>>>> list_add_tail(&grp->bb_largest_free_order_node,
>>>> &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
>>>> write_unlock(&sbi->s_mb_largest_free_orders_locks[
>>>> grp->bb_largest_free_order]);
>>>> }
>>>> }
>>
>> In looking at my previous comment, I wonder if we could further reduce
>> the list locking here by not moving an entry to the end of the *same*
>> list if it is not currently at the head? Since it was (presumably)
>> just moved to the end of the list by a recent allocation, it is very
>> likely that some other group will be chosen from the list head, so
>> moving within the list to maintain strict LRU is probably just extra
>> locking overhead that can be avoided...
>>
>> Also, it isn't clear if *freeing* blocks from a group should move it
>> to the end of the same list, or just leave it as-is? If there are
>> more frees from the list it is likely to be added to a new list soon,
>> and if there are no more frees, then it could stay in the same order.
>>
>>
>> Cheers, Andreas
>>
>>
>>
>>
>>
Cheers, Andreas
[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-26 3:43 ` Andreas Dilger
@ 2021-02-26 4:06 ` harshad shirwadkar
2021-02-26 4:42 ` Andreas Dilger
0 siblings, 1 reply; 17+ messages in thread
From: harshad shirwadkar @ 2021-02-26 4:06 UTC (permalink / raw)
To: Andreas Dilger
Cc: Благодаренко Артём,
Ext4 Developers List, Theodore Y. Ts'o, Alex Zhuravlev,
Shuichi Ihara
Hi Andreas,
On Thu, Feb 25, 2021 at 7:43 PM Andreas Dilger <adilger@dilger.ca> wrote:
>
> On Feb 21, 2021, at 8:59 PM, harshad shirwadkar <harshadshirwadkar@gmail.com> wrote:
> >
> > Thank you for all the feedback Andreas and Artem. Some comments below:
>
> Thank you for working on this. It is definitely an area that can use
> this improvement.
>
> >> I was wondering about the cost of the list/tree maintenance as well,
> >> especially since there was a post from "kernel test robot" that this
> >> patch introduced a performance regression.
> >
> > Yeah, I'm pretty sure that the kernel test robot is complaining mainly
> > because of list/tree maintenance. I think if this optimization is
> > turned off, we probably should not even maintain the tree / lists.
> > That has one downside that is that we will have to disallow setting
> > this option during remount, which I guess is okay?
>
> I think it is reasonable to not be able to change this at runtime.
> This would only make a difference for a limited number of testers,
> and virtually all users will never know it exists at all.
>
> >> It would also make sense for totally full groups to be kept out of the
> >> rb tree entirely, since they do not provide any value in that case (the
> >> full groups will never be selected for allocations), and they just add
> >> to the tree depth and potentially cause an imbalance if there are many
> >> of them. That also has the benefit of the rbtree efficiency *improving*
> >> as the filesystem gets more full, which is right when it is most needed.
> >
> > Ack
> >
> >> It might also make sense to keep totally empty groups out of the rbtree,
> >> since they should always be found in cr0 already if the allocation is
> >> large enough to fill the whole group? Having a smaller rbtree makes
> >> every insertion/removal that much more efficient.
> >
> > Ack
> >
> >> Those groups will naturally be re-added into the rbtree when they have
> >> blocks freed or allocated, so not much added complexity.
> >>
> >>
> >> Does it make sense to disable "mb_optimize_scan" if filesystems are
> >> smaller than a certain threshold? Clearly, if there are only 1-2
> >> groups, maintaining a list and rbtree has no real value, and with
> >> only a handful of groups (< 16?) linear searching is probably as fast
> >> or faster than maintaining the two data structures. That is similar
> >> to e.g. bubble sort vs. quicksort, where it is more efficient to sort
> >> a list of ~5-8 entries with a dumb/fast algorithm instead of a complex
> >> algorithm that is more efficient at larger scales. That would also
> >> (likely) quiet the kernel test robot, if we think that its testing is
> >> not representative of real-world usage.
> >
> > Ack, these are good optimizations. I'll add these in V3.
>
> For testing purposes it should be possible to have "mb_optimize_scan=1"
> force the use of this option, even if the filesystem is small.
Ack
>
> > Besides the optimizations mentioned here, I also think we should add
> > "mb_optimize_linear_limit" or such sysfs tunable which will control
> > how many groups should mballoc search linearly before using tree /
> > lists for allocation? That would help us with the disk seek time
> > performance.
>
> There is already a linear search threshold parameters for mballoc,
> namely mb_min_to_scan and mb_max_to_scan that could be used for this.
> I think we could use "mb_min_to_scan=10" (the current default), or
> maybe shrink this a bit (4?) if "mb_optimize_scan" is enabled.
>
> > We discussed on our last call that we probably should consult with the
> > block device's request queue to check if the underlying block device
> > is rotational or not. However, we also discussed that for more complex
> > devices (such as DMs setup on top of HDD and SSD etc), whether the
> > device is rotational or not is not a binary answer and we would need a
> > more complex interface (such as logical range to "is_rotational"
> > table) to make intelligent choice in the file system. Also, in such
> > cases, it is not clear if such a table needs to be passed to the file
> > system during mkfs time? or at mount time? or at run time?
>
> I don't think the hybrid case is very important yet. By far the
> most common case is going to be "rotational=1" or "rotational=0"
> for the whole device, so we should start by only optimizing for
> those cases. DM looks like it returns "rotational=0" correctly
> when a composite device it is made of entirely non-rotational
> devices and "rotational=1" as it should when it is a hybrid
> HDD/SSD device (which I have in my local system).
Ack
>
> > Given the number of unknowns in the above discussion, I propose that
> > we start simple and evolve later. So my proposal is that we add a
> > "mb_optimize_linear_limit" tunable that accepts an integer value. In
> > the kernel, for non-rotational devices, that value will be defaulted
> > to 0 (which means no linear scan) and for rotational devices, that
> > value will be defaulted to a reasonable value (-- not sure what that
> > value would be though - 4?). This default can be overridden using the
> > sysfs interface. We can later evolve this interface to accept more
> > complex input such as logical range to rotational status.
> >
> > Does that sound reasonable?
>
> Yes, modulo using the existing "mb_min_to_scan" parameter for this.
> I think 4 or 8 or 10 groups is reasonable (512MB, 1GB, 1.25GB),
> since if it needs a seek anyway then we may as well find a good
> group for this.
If I understand it right, the meaning of mb_min_to_scan is the number
of *extents* that the allocator should try to find before choosing the
best one. However, what we want here is the number of *groups* that
the allocator should travel linearly before trying to optimize the
search. So, even if mb_min_to_scan is set to 1, by the current
definition of it, it means that the allocator may still traverse the
entire file system if it doesn't find a match. Is my understanding
right?
Thanks,
Harshad
>
> Cheers, Andreas
>
> >
> >>
> >>> On Feb 11, 2021, at 3:30 AM, Andreas Dilger <adilger@dilger.ca> wrote:
> >>
> >>>> This function would be more efficient to do the list move under a single
> >>>> write lock if the order doesn't change. The order loop would just
> >>>> save the largest free order, then grab the write lock, do the list_del(),
> >>>> set bb_largest_free_order, and list_add_tail():
> >>>>
> >>>> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
> >>>> {
> >>>> struct ext4_sb_info *sbi = EXT4_SB(sb);
> >>>> int i, new_order = -1;
> >>>>
> >>>> for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
> >>>> if (grp->bb_counters[i] > 0) {
> >>>> new_order = i;
> >>>> break;
> >>>> }
> >>>> }
> >>>> if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> >>>> write_lock(&sbi->s_mb_largest_free_orders_locks[
> >>>> grp->bb_largest_free_order]);
> >>>> list_del_init(&grp->bb_largest_free_order_node);
> >>>>
> >>>> if (new_order != grp->bb_largest_free_order) {
> >>>> write_unlock(&sbi->s_mb_largest_free_orders_locks[
> >>>> grp->bb_largest_free_order]);
> >>>> grp->bb_largest_free_order = new_order;
> >>>> write_lock(&sbi->s_mb_largest_free_orders_locks[
> >>>> grp->bb_largest_free_order]);
> >>>> }
> >>>> list_add_tail(&grp->bb_largest_free_order_node,
> >>>> &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
> >>>> write_unlock(&sbi->s_mb_largest_free_orders_locks[
> >>>> grp->bb_largest_free_order]);
> >>>> }
> >>>> }
> >>
> >> In looking at my previous comment, I wonder if we could further reduce
> >> the list locking here by not moving an entry to the end of the *same*
> >> list if it is not currently at the head? Since it was (presumably)
> >> just moved to the end of the list by a recent allocation, it is very
> >> likely that some other group will be chosen from the list head, so
> >> moving within the list to maintain strict LRU is probably just extra
> >> locking overhead that can be avoided...
> >>
> >> Also, it isn't clear if *freeing* blocks from a group should move it
> >> to the end of the same list, or just leave it as-is? If there are
> >> more frees from the list it is likely to be added to a new list soon,
> >> and if there are no more frees, then it could stay in the same order.
> >>
> >>
> >> Cheers, Andreas
> >>
> >>
> >>
> >>
> >>
>
>
> Cheers, Andreas
>
>
>
>
>
^ permalink raw reply [flat|nested] 17+ messages in thread* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-26 4:06 ` harshad shirwadkar
@ 2021-02-26 4:42 ` Andreas Dilger
0 siblings, 0 replies; 17+ messages in thread
From: Andreas Dilger @ 2021-02-26 4:42 UTC (permalink / raw)
To: harshad shirwadkar
Cc: Благодаренко Артём,
Ext4 Developers List, Theodore Y. Ts'o, Alex Zhuravlev,
Shuichi Ihara
[-- Attachment #1: Type: text/plain, Size: 1047 bytes --]
On Feb 25, 2021, at 9:06 PM, harshad shirwadkar <harshadshirwadkar@gmail.com> wrote:
>
> Hi Andreas,
>
> On Thu, Feb 25, 2021 at 7:43 PM Andreas Dilger <adilger@dilger.ca> wrote:
>>
>> Yes, modulo using the existing "mb_min_to_scan" parameter for this.
>> I think 4 or 8 or 10 groups is reasonable (512MB, 1GB, 1.25GB),
>> since if it needs a seek anyway then we may as well find a good
>> group for this.
> If I understand it right, the meaning of mb_min_to_scan is the number
> of *extents* that the allocator should try to find before choosing the
> best one. However, what we want here is the number of *groups* that
> the allocator should travel linearly before trying to optimize the
> search. So, even if mb_min_to_scan is set to 1, by the current
> definition of it, it means that the allocator may still traverse the
> entire file system if it doesn't find a match. Is my understanding
> right?
Sorry, you are right. It is the number of extents to scan and not
the number of groups.
Cheers, Andreas
[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning
2021-02-09 20:28 ` [PATCH v2 4/5] ext4: improve cr 0 / cr 1 group scanning Harshad Shirwadkar
` (4 preceding siblings ...)
2021-02-16 19:39 ` Благодаренко Артём
@ 2021-02-17 19:41 ` Благодаренко Артём
5 siblings, 0 replies; 17+ messages in thread
From: Благодаренко Артём @ 2021-02-17 19:41 UTC (permalink / raw)
To: Harshad Shirwadkar
Cc: linux-ext4, Theodore Y. Ts'o, bzzz, sihara, Andreas Dilger
Hello Harshad,
Simple test with empty filesystem.
[root@CO82 linux]# dd if=/dev/zero of=/mnt/foomount/foofile bs=2M count=2 conv=fsync
2+0 records in
2+0 records out
4194304 bytes (4.2 MB, 4.0 MiB) copied, 0.0406173 s, 103 MB/s
Let’s output structures
[root@CO82 linux]# cat /proc/fs/ext4/loop0/mb_structs_summary
Largest Free Order Lists:
Order 0 list: 0 Groups
Order 1 list: 0 Groups
Order 2 list: 0 Groups
Order 3 list: 0 Groups
Order 4 list: 0 Groups
Order 5 list: 0 Groups
Order 6 list: 0 Groups
Order 7 list: 0 Groups
Order 8 list: 0 Groups
Order 9 list: 0 Groups
Order 10 list: 0 Groups
Order 11 list: 0 Groups
Order 12 list: 0 Groups
Order 13 list: 1 Groups
Tree
Min: 31620, Max: 31620, Num Nodes: 1
[root@CO82 linux]#
There is information only about one group 13. I suppose because it was accessed.
So this lists are not filled initially, but only when a group is accessed. Is this expected?
Here is information about free orders of all groups that captured from mb_groups
[root@CO82 linux]# cat /proc/fs/ext4/loop0/mb_groups
#group: free frags first [ 2^0 2^1 2^2 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10 2^11 2^12 2^13 ]
#0 : 28710 1 4058 [ 0 1 1 0 0 1 0 0 0 0 0 0 1 3 ]
#1 : 31620 1 1148 [ 0 0 1 0 0 0 0 1 1 1 0 1 1 3 ]
#2 : 28672 1 4096 [ 0 0 0 0 0 0 0 0 0 0 0 0 1 3 ]
#3 : 32644 1 124 [ 0 0 1 0 0 0 0 1 1 1 1 1 1 3 ]
#4 : 32768 1 0 [ 0 0 0 0 0 0 0 0 0 0 0 0 0 4 ]
#5 : 32644 1 124 [ 0 0 1 0 0 0 0 1 1 1 1 1 1 3 ]
#6 : 32768 1 0 [ 0 0 0 0 0 0 0 0 0 0 0 0 0 4 ]
#7 : 20500 1 124 [ 0 0 1 0 1 0 0 2 1 1 1 1 2 1 ]
There are a lot of different free ranges on this filesystem.
Best regards,
Artem Blagodarenko.
> On 9 Feb 2021, at 23:28, Harshad Shirwadkar <harshadshirwadkar@gmail.com> wrote:
>
> Instead of traversing through groups linearly, scan groups in specific
> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
> largest free order >= the order of the request. So, with this patch,
> we maintain lists for each possible order and insert each group into a
> list based on the largest free order in its buddy bitmap. During cr 0
> allocation, we traverse these lists in the increasing order of largest
> free orders. This allows us to find a group with the best available cr
> 0 match in constant time. If nothing can be found, we fallback to cr 1
> immediately.
>
> At CR1, the story is slightly different. We want to traverse in the
> order of increasing average fragment size. For CR1, we maintain a rb
> tree of groupinfos which is sorted by average fragment size. Instead
> of traversing linearly, at CR1, we traverse in the order of increasing
> average fragment size, starting at the most optimal group. This brings
> down cr 1 search complexity to log(num groups).
>
> For cr >= 2, we just perform the linear search as before. Also, in
> case of lock contention, we intermittently fallback to linear search
> even in CR 0 and CR 1 cases. This allows us to proceed during the
> allocation path even in case of high contention.
>
> There is an opportunity to do optimization at CR2 too. That's because
> at CR2 we only consider groups where bb_free counter (number of free
> blocks) is greater than the request extent size. That's left as future
> work.
>
> All the changes introduced in this patch are protected under a new
> mount option "mb_optimize_scan".
>
> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
> ---
> fs/ext4/ext4.h | 13 +-
> fs/ext4/mballoc.c | 316 ++++++++++++++++++++++++++++++++++++++++++++--
> fs/ext4/mballoc.h | 1 +
> fs/ext4/super.c | 6 +-
> 4 files changed, 322 insertions(+), 14 deletions(-)
>
> diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
> index 317b43420ecf..0601c997c87f 100644
> --- a/fs/ext4/ext4.h
> +++ b/fs/ext4/ext4.h
> @@ -162,6 +162,8 @@ enum SHIFT_DIRECTION {
> #define EXT4_MB_USE_RESERVED 0x2000
> /* Do strict check for free blocks while retrying block allocation */
> #define EXT4_MB_STRICT_CHECK 0x4000
> +/* Avg fragment size rb tree lookup succeeded at least once for cr = 1 */
> +#define EXT4_MB_CR1_OPTIMIZED 0x8000
>
> struct ext4_allocation_request {
> /* target inode for block we're allocating */
> @@ -1247,7 +1249,9 @@ struct ext4_inode_info {
> #define EXT4_MOUNT2_JOURNAL_FAST_COMMIT 0x00000010 /* Journal fast commit */
> #define EXT4_MOUNT2_DAX_NEVER 0x00000020 /* Do not allow Direct Access */
> #define EXT4_MOUNT2_DAX_INODE 0x00000040 /* For printing options only */
> -
> +#define EXT4_MOUNT2_MB_OPTIMIZE_SCAN 0x00000080 /* Optimize group
> + * scanning in mballoc
> + */
>
> #define clear_opt(sb, opt) EXT4_SB(sb)->s_mount_opt &= \
> ~EXT4_MOUNT_##opt
> @@ -1527,6 +1531,10 @@ struct ext4_sb_info {
> unsigned int s_mb_free_pending;
> struct list_head s_freed_data_list; /* List of blocks to be freed
> after commit completed */
> + struct rb_root s_mb_avg_fragment_size_root;
> + rwlock_t s_mb_rb_lock;
> + struct list_head *s_mb_largest_free_orders;
> + rwlock_t *s_mb_largest_free_orders_locks;
>
> /* tunables */
> unsigned long s_stripe;
> @@ -3308,11 +3316,14 @@ struct ext4_group_info {
> ext4_grpblk_t bb_free; /* total free blocks */
> ext4_grpblk_t bb_fragments; /* nr of freespace fragments */
> ext4_grpblk_t bb_largest_free_order;/* order of largest frag in BG */
> + ext4_group_t bb_group; /* Group number */
> struct list_head bb_prealloc_list;
> #ifdef DOUBLE_CHECK
> void *bb_bitmap;
> #endif
> struct rw_semaphore alloc_sem;
> + struct rb_node bb_avg_fragment_size_rb;
> + struct list_head bb_largest_free_order_node;
> ext4_grpblk_t bb_counters[]; /* Nr of free power-of-two-block
> * regions, index is order.
> * bb_counters[3] = 5 means
> diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
> index b7f25120547d..63562f5f42f1 100644
> --- a/fs/ext4/mballoc.c
> +++ b/fs/ext4/mballoc.c
> @@ -147,7 +147,12 @@
> * the group specified as the goal value in allocation context via
> * ac_g_ex. Each group is first checked based on the criteria whether it
> * can be used for allocation. ext4_mb_good_group explains how the groups are
> - * checked.
> + * checked. If "mb_optimize_scan" mount option is set, instead of traversing
> + * groups linearly starting at the goal, the groups are traversed in an optimal
> + * order according to each cr level, so as to minimize considering groups which
> + * would anyway be rejected by ext4_mb_good_group. This has a side effect
> + * though - subsequent allocations may not be close to each other. And so,
> + * the underlying device may get filled up in a non-linear fashion.
> *
> * Both the prealloc space are getting populated as above. So for the first
> * request we will hit the buddy cache which will result in this prealloc
> @@ -299,6 +304,8 @@
> * - bitlock on a group (group)
> * - object (inode/locality) (object)
> * - per-pa lock (pa)
> + * - cr0 lists lock (cr0)
> + * - cr1 tree lock (cr1)
> *
> * Paths:
> * - new pa
> @@ -328,6 +335,9 @@
> * group
> * object
> *
> + * - allocation path (ext4_mb_regular_allocator)
> + * group
> + * cr0/cr1
> */
> static struct kmem_cache *ext4_pspace_cachep;
> static struct kmem_cache *ext4_ac_cachep;
> @@ -351,6 +361,9 @@ static void ext4_mb_generate_from_freelist(struct super_block *sb, void *bitmap,
> ext4_group_t group);
> static void ext4_mb_new_preallocation(struct ext4_allocation_context *ac);
>
> +static bool ext4_mb_good_group(struct ext4_allocation_context *ac,
> + ext4_group_t group, int cr);
> +
> /*
> * The algorithm using this percpu seq counter goes below:
> * 1. We sample the percpu discard_pa_seq counter before trying for block
> @@ -744,6 +757,243 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> }
> }
>
> +static void ext4_mb_rb_insert(struct rb_root *root, struct rb_node *new,
> + int (*cmp)(struct rb_node *, struct rb_node *))
> +{
> + struct rb_node **iter = &root->rb_node, *parent = NULL;
> +
> + while (*iter) {
> + parent = *iter;
> + if (cmp(new, *iter))
> + iter = &((*iter)->rb_left);
> + else
> + iter = &((*iter)->rb_right);
> + }
> +
> + rb_link_node(new, parent, iter);
> + rb_insert_color(new, root);
> +}
> +
> +static int
> +ext4_mb_avg_fragment_size_cmp(struct rb_node *rb1, struct rb_node *rb2)
> +{
> + struct ext4_group_info *grp1 = rb_entry(rb1,
> + struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + struct ext4_group_info *grp2 = rb_entry(rb2,
> + struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + int num_frags_1, num_frags_2;
> +
> + num_frags_1 = grp1->bb_fragments ?
> + grp1->bb_free / grp1->bb_fragments : 0;
> + num_frags_2 = grp2->bb_fragments ?
> + grp2->bb_free / grp2->bb_fragments : 0;
> +
> + return (num_frags_1 < num_frags_2);
> +}
> +
> +/*
> + * Reinsert grpinfo into the avg_fragment_size tree with new average
> + * fragment size.
> + */
> +static void
> +mb_update_avg_fragment_size(struct super_block *sb, struct ext4_group_info *grp)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> +
> + if (!test_opt2(sb, MB_OPTIMIZE_SCAN))
> + return;
> +
> + write_lock(&sbi->s_mb_rb_lock);
> + if (!RB_EMPTY_NODE(&grp->bb_avg_fragment_size_rb)) {
> + rb_erase(&grp->bb_avg_fragment_size_rb,
> + &sbi->s_mb_avg_fragment_size_root);
> + RB_CLEAR_NODE(&grp->bb_avg_fragment_size_rb);
> + }
> +
> + ext4_mb_rb_insert(&sbi->s_mb_avg_fragment_size_root,
> + &grp->bb_avg_fragment_size_rb,
> + ext4_mb_avg_fragment_size_cmp);
> + write_unlock(&sbi->s_mb_rb_lock);
> +}
> +
> +/*
> + * Choose next group by traversing largest_free_order lists. Return 0 if next
> + * group was selected optimally. Return 1 if next group was not selected
> + * optimally. Updates *new_cr if cr level needs an update.
> + */
> +static int ext4_mb_choose_next_group_cr0(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
> + struct ext4_group_info *iter, *grp;
> + int i;
> +
> + if (ac->ac_status == AC_STATUS_FOUND)
> + return 1;
> +
> + grp = NULL;
> + for (i = ac->ac_2order; i < MB_NUM_ORDERS(ac->ac_sb); i++) {
> + if (list_empty(&sbi->s_mb_largest_free_orders[i]))
> + continue;
> + read_lock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (list_empty(&sbi->s_mb_largest_free_orders[i])) {
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + continue;
> + }
> + grp = NULL;
> + list_for_each_entry(iter, &sbi->s_mb_largest_free_orders[i],
> + bb_largest_free_order_node) {
> + /*
> + * Perform this check without a lock, once we lock
> + * the group, we'll perform this check again.
> + */
> + if (likely(ext4_mb_good_group(ac, iter->bb_group, 0))) {
> + grp = iter;
> + break;
> + }
> + }
> + read_unlock(&sbi->s_mb_largest_free_orders_locks[i]);
> + if (grp)
> + break;
> + }
> +
> + if (!grp) {
> + /* Increment cr and search again */
> + *new_cr = 1;
> + } else {
> + *group = grp->bb_group;
> + ac->ac_last_optimal_group = *group;
> + }
> + return 0;
> +}
> +
> +/*
> + * Choose next group by traversing average fragment size tree. Return 0 if next
> + * group was selected optimally. Return 1 if next group could not selected
> + * optimally (due to lock contention). Updates *new_cr if cr lvel needs an
> + * update.
> + */
> +static int ext4_mb_choose_next_group_cr1(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + struct ext4_sb_info *sbi = EXT4_SB(ac->ac_sb);
> + int avg_fragment_size, best_so_far;
> + struct rb_node *node, *found;
> + struct ext4_group_info *grp;
> +
> + /*
> + * If there is contention on the lock, instead of waiting for the lock
> + * to become available, just continue searching lineraly. We'll resume
> + * our rb tree search later starting at ac->ac_last_optimal_group.
> + */
> + if (!read_trylock(&sbi->s_mb_rb_lock))
> + return 1;
> +
> + if (ac->ac_flags & EXT4_MB_CR1_OPTIMIZED) {
> + /* We have found something at CR 1 in the past */
> + grp = ext4_get_group_info(ac->ac_sb, ac->ac_last_optimal_group);
> + for (found = rb_next(&grp->bb_avg_fragment_size_rb); found != NULL;
> + found = rb_next(found)) {
> + grp = rb_entry(found, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + /*
> + * Perform this check without locking, we'll lock later
> + * to confirm.
> + */
> + if (likely(ext4_mb_good_group(ac, grp->bb_group, 1)))
> + break;
> + }
> +
> + goto done;
> + }
> +
> + node = sbi->s_mb_avg_fragment_size_root.rb_node;
> + best_so_far = 0;
> + found = NULL;
> +
> + while (node) {
> + grp = rb_entry(node, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + /*
> + * Perform this check without locking, we'll lock later to confirm.
> + */
> + if (ext4_mb_good_group(ac, grp->bb_group, 1)) {
> + avg_fragment_size = grp->bb_fragments ?
> + grp->bb_free / grp->bb_fragments : 0;
> + if (!best_so_far || avg_fragment_size < best_so_far) {
> + best_so_far = avg_fragment_size;
> + found = node;
> + }
> + }
> + if (avg_fragment_size > ac->ac_g_ex.fe_len)
> + node = node->rb_right;
> + else
> + node = node->rb_left;
> + }
> +
> +done:
> + if (found) {
> + grp = rb_entry(found, struct ext4_group_info,
> + bb_avg_fragment_size_rb);
> + *group = grp->bb_group;
> + ac->ac_flags |= EXT4_MB_CR1_OPTIMIZED;
> + } else {
> + *new_cr = 2;
> + }
> +
> + read_unlock(&sbi->s_mb_rb_lock);
> + ac->ac_last_optimal_group = *group;
> + return 0;
> +}
> +
> +/*
> + * ext4_mb_choose_next_group: choose next group for allocation.
> + *
> + * @ac Allocation Context
> + * @new_cr This is an output parameter. If the there is no good group available
> + * at current CR level, this field is updated to indicate the new cr
> + * level that should be used.
> + * @group This is an input / output parameter. As an input it indicates the last
> + * group used for allocation. As output, this field indicates the
> + * next group that should be used.
> + * @ngroups Total number of groups
> + */
> +static void ext4_mb_choose_next_group(struct ext4_allocation_context *ac,
> + int *new_cr, ext4_group_t *group, ext4_group_t ngroups)
> +{
> + int ret;
> +
> + *new_cr = ac->ac_criteria;
> +
> + if (!test_opt2(ac->ac_sb, MB_OPTIMIZE_SCAN) ||
> + *new_cr >= 2 ||
> + !ext4_test_inode_flag(ac->ac_inode, EXT4_INODE_EXTENTS))
> + goto inc_and_return;
> +
> + if (*new_cr == 0) {
> + ret = ext4_mb_choose_next_group_cr0(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + if (*new_cr == 1) {
> + ret = ext4_mb_choose_next_group_cr1(ac, new_cr, group, ngroups);
> + if (ret)
> + goto inc_and_return;
> + }
> + return;
> +
> +inc_and_return:
> + /*
> + * Artificially restricted ngroups for non-extent
> + * files makes group > ngroups possible on first loop.
> + */
> + *group = *group + 1;
> + if (*group >= ngroups)
> + *group = 0;
> +}
> +
> /*
> * Cache the order of the largest free extent we have available in this block
> * group.
> @@ -751,18 +1001,32 @@ static void ext4_mb_mark_free_simple(struct super_block *sb,
> static void
> mb_set_largest_free_order(struct super_block *sb, struct ext4_group_info *grp)
> {
> + struct ext4_sb_info *sbi = EXT4_SB(sb);
> int i;
> - int bits;
>
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_del_init(&grp->bb_largest_free_order_node);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> grp->bb_largest_free_order = -1; /* uninit */
>
> - bits = MB_NUM_ORDERS(sb) - 1;
> - for (i = bits; i >= 0; i--) {
> + for (i = MB_NUM_ORDERS(sb) - 1; i >= 0; i--) {
> if (grp->bb_counters[i] > 0) {
> grp->bb_largest_free_order = i;
> break;
> }
> }
> + if (test_opt2(sb, MB_OPTIMIZE_SCAN) && grp->bb_largest_free_order >= 0) {
> + write_lock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + list_add_tail(&grp->bb_largest_free_order_node,
> + &sbi->s_mb_largest_free_orders[grp->bb_largest_free_order]);
> + write_unlock(&sbi->s_mb_largest_free_orders_locks[
> + grp->bb_largest_free_order]);
> + }
> }
>
> static noinline_for_stack
> @@ -818,6 +1082,7 @@ void ext4_mb_generate_buddy(struct super_block *sb,
> period = get_cycles() - period;
> atomic_inc(&sbi->s_mb_buddies_generated);
> atomic64_add(period, &sbi->s_mb_generation_time);
> + mb_update_avg_fragment_size(sb, grp);
> }
>
> /* The buddy information is attached the buddy cache inode
> @@ -1517,6 +1782,7 @@ static void mb_free_blocks(struct inode *inode, struct ext4_buddy *e4b,
>
> done:
> mb_set_largest_free_order(sb, e4b->bd_info);
> + mb_update_avg_fragment_size(sb, e4b->bd_info);
> mb_check_buddy(e4b);
> }
>
> @@ -1653,6 +1919,7 @@ static int mb_mark_used(struct ext4_buddy *e4b, struct ext4_free_extent *ex)
> }
> mb_set_largest_free_order(e4b->bd_sb, e4b->bd_info);
>
> + mb_update_avg_fragment_size(e4b->bd_sb, e4b->bd_info);
> ext4_set_bits(e4b->bd_bitmap, ex->fe_start, len0);
> mb_check_buddy(e4b);
>
> @@ -2346,17 +2613,20 @@ ext4_mb_regular_allocator(struct ext4_allocation_context *ac)
> * from the goal value specified
> */
> group = ac->ac_g_ex.fe_group;
> + ac->ac_last_optimal_group = group;
> prefetch_grp = group;
>
> - for (i = 0; i < ngroups; group++, i++) {
> - int ret = 0;
> + for (i = 0; i < ngroups; i++) {
> + int ret = 0, new_cr;
> +
> cond_resched();
> - /*
> - * Artificially restricted ngroups for non-extent
> - * files makes group > ngroups possible on first loop.
> - */
> - if (group >= ngroups)
> - group = 0;
> +
> + ext4_mb_choose_next_group(ac, &new_cr, &group, ngroups);
> +
> + if (new_cr != cr) {
> + cr = new_cr;
> + goto repeat;
> + }
>
> /*
> * Batch reads of the block allocation bitmaps
> @@ -2696,7 +2966,10 @@ int ext4_mb_add_groupinfo(struct super_block *sb, ext4_group_t group,
> INIT_LIST_HEAD(&meta_group_info[i]->bb_prealloc_list);
> init_rwsem(&meta_group_info[i]->alloc_sem);
> meta_group_info[i]->bb_free_root = RB_ROOT;
> + INIT_LIST_HEAD(&meta_group_info[i]->bb_largest_free_order_node);
> + RB_CLEAR_NODE(&meta_group_info[i]->bb_avg_fragment_size_rb);
> meta_group_info[i]->bb_largest_free_order = -1; /* uninit */
> + meta_group_info[i]->bb_group = group;
>
> mb_group_bb_bitmap_alloc(sb, meta_group_info[i], group);
> return 0;
> @@ -2886,6 +3159,22 @@ int ext4_mb_init(struct super_block *sb)
> i++;
> } while (i < MB_NUM_ORDERS(sb));
>
> + sbi->s_mb_avg_fragment_size_root = RB_ROOT;
> + sbi->s_mb_largest_free_orders =
> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(struct list_head),
> + GFP_KERNEL);
> + if (!sbi->s_mb_largest_free_orders)
> + goto out;
> + sbi->s_mb_largest_free_orders_locks =
> + kmalloc_array(MB_NUM_ORDERS(sb), sizeof(rwlock_t),
> + GFP_KERNEL);
> + if (!sbi->s_mb_largest_free_orders_locks)
> + goto out;
> + for (i = 0; i < MB_NUM_ORDERS(sb); i++) {
> + INIT_LIST_HEAD(&sbi->s_mb_largest_free_orders[i]);
> + rwlock_init(&sbi->s_mb_largest_free_orders_locks[i]);
> + }
> + rwlock_init(&sbi->s_mb_rb_lock);
>
> spin_lock_init(&sbi->s_md_lock);
> sbi->s_mb_free_pending = 0;
> @@ -2949,6 +3238,8 @@ int ext4_mb_init(struct super_block *sb)
> free_percpu(sbi->s_locality_groups);
> sbi->s_locality_groups = NULL;
> out:
> + kfree(sbi->s_mb_largest_free_orders);
> + kfree(sbi->s_mb_largest_free_orders_locks);
> kfree(sbi->s_mb_offsets);
> sbi->s_mb_offsets = NULL;
> kfree(sbi->s_mb_maxs);
> @@ -3005,6 +3296,7 @@ int ext4_mb_release(struct super_block *sb)
> kvfree(group_info);
> rcu_read_unlock();
> }
> + kfree(sbi->s_mb_largest_free_orders);
> kfree(sbi->s_mb_offsets);
> kfree(sbi->s_mb_maxs);
> iput(sbi->s_buddy_cache);
> diff --git a/fs/ext4/mballoc.h b/fs/ext4/mballoc.h
> index 02861406932f..1e86a8a0460d 100644
> --- a/fs/ext4/mballoc.h
> +++ b/fs/ext4/mballoc.h
> @@ -166,6 +166,7 @@ struct ext4_allocation_context {
> /* copy of the best found extent taken before preallocation efforts */
> struct ext4_free_extent ac_f_ex;
>
> + ext4_group_t ac_last_optimal_group;
> __u32 ac_groups_considered;
> __u16 ac_groups_scanned;
> __u16 ac_found;
> diff --git a/fs/ext4/super.c b/fs/ext4/super.c
> index 0f0db49031dc..a14363654cfd 100644
> --- a/fs/ext4/super.c
> +++ b/fs/ext4/super.c
> @@ -154,6 +154,7 @@ static inline void __ext4_read_bh(struct buffer_head *bh, int op_flags,
> clear_buffer_verified(bh);
>
> bh->b_end_io = end_io ? end_io : end_buffer_read_sync;
> +
> get_bh(bh);
> submit_bh(REQ_OP_READ, op_flags, bh);
> }
> @@ -1687,7 +1688,7 @@ enum {
> Opt_dioread_nolock, Opt_dioread_lock,
> Opt_discard, Opt_nodiscard, Opt_init_itable, Opt_noinit_itable,
> Opt_max_dir_size_kb, Opt_nojournal_checksum, Opt_nombcache,
> - Opt_prefetch_block_bitmaps,
> + Opt_prefetch_block_bitmaps, Opt_mb_optimize_scan,
> #ifdef CONFIG_EXT4_DEBUG
> Opt_fc_debug_max_replay, Opt_fc_debug_force
> #endif
> @@ -1788,6 +1789,7 @@ static const match_table_t tokens = {
> {Opt_nombcache, "nombcache"},
> {Opt_nombcache, "no_mbcache"}, /* for backward compatibility */
> {Opt_prefetch_block_bitmaps, "prefetch_block_bitmaps"},
> + {Opt_mb_optimize_scan, "mb_optimize_scan"},
> {Opt_removed, "check=none"}, /* mount option from ext2/3 */
> {Opt_removed, "nocheck"}, /* mount option from ext2/3 */
> {Opt_removed, "reservation"}, /* mount option from ext2/3 */
> @@ -2008,6 +2010,8 @@ static const struct mount_opts {
> {Opt_nombcache, EXT4_MOUNT_NO_MBCACHE, MOPT_SET},
> {Opt_prefetch_block_bitmaps, EXT4_MOUNT_PREFETCH_BLOCK_BITMAPS,
> MOPT_SET},
> + {Opt_mb_optimize_scan, EXT4_MOUNT2_MB_OPTIMIZE_SCAN,
> + MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
> #ifdef CONFIG_EXT4_DEBUG
> {Opt_fc_debug_force, EXT4_MOUNT2_JOURNAL_FAST_COMMIT,
> MOPT_SET | MOPT_2 | MOPT_EXT4_ONLY},
> --
> 2.30.0.478.g8a0d178c01-goog
>
^ permalink raw reply [flat|nested] 17+ messages in thread