Re: [PATCH v2 5/5] ext4: add proc files to monitor new structures

Re: [PATCH v2 5/5] ext4: add proc files to monitor new structures

[kernel test robot]

[-- Attachment #1: Type: text/plain, Size: 3620 bytes --]

CC: kbuild-all(a)lists.01.org
In-Reply-To: <20210209202857.4185846-6-harshadshirwadkar@gmail.com>
References: <20210209202857.4185846-6-harshadshirwadkar@gmail.com>
TO: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
TO: linux-ext4(a)vger.kernel.org
CC: tytso(a)mit.edu
CC: bzzz(a)whamcloud.com
CC: artem.blagodarenko(a)gmail.com
CC: sihara(a)ddn.com
CC: adilger(a)dilger.ca
CC: Harshad Shirwadkar <harshadshirwadkar@gmail.com>

Hi Harshad,

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on ext4/dev]
[also build test WARNING on v5.11-rc7 next-20210125]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]

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
:::::: branch date: 10 hours ago
:::::: commit date: 10 hours ago
config: x86_64-randconfig-s021-20210209 (attached as .config)
compiler: gcc-9 (Debian 9.3.0-15) 9.3.0
reproduce:
        # apt-get install sparse
        # sparse version: v0.6.3-215-g0fb77bb6-dirty
        # https://github.com/0day-ci/linux/commit/51dc3ee0ba379809b113ad2bd596888e8b55b534
        git remote add linux-review https://github.com/0day-ci/linux
        git fetch --no-tags linux-review Harshad-Shirwadkar/ext4-drop-s_mb_bal_lock-and-convert-protected-fields-to-atomic/20210210-054647
        git checkout 51dc3ee0ba379809b113ad2bd596888e8b55b534
        # save the attached .config to linux build tree
        make W=1 C=1 CF='-fdiagnostic-prefix -D__CHECK_ENDIAN__' ARCH=x86_64 

If you fix the issue, kindly add following tag as appropriate
Reported-by: kernel test robot <lkp@intel.com>


"sparse warnings: (new ones prefixed by >>)"
   fs/ext4/mballoc.c:2460:9: sparse: sparse: context imbalance in 'ext4_mb_good_group_nolock' - different lock contexts for basic block
>> fs/ext4/mballoc.c:2867:13: sparse: sparse: context imbalance in 'ext4_mb_seq_structs_summary_start' - wrong count at exit
   fs/ext4/mballoc.c:2937:13: sparse: sparse: context imbalance in 'ext4_mb_seq_structs_summary_stop' - unexpected unlock

vim +/ext4_mb_seq_structs_summary_start +2867 fs/ext4/mballoc.c

251fb84975e8df Harshad Shirwadkar 2021-02-09  2866  
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09 @2867  static void *ext4_mb_seq_structs_summary_start(struct seq_file *seq, loff_t *pos)
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2868  {
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2869  	struct super_block *sb = PDE_DATA(file_inode(seq->file));
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2870  	unsigned long position;
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2871  
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2872  	read_lock(&EXT4_SB(sb)->s_mb_rb_lock);
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2873  
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2874  	if (*pos < 0 || *pos >= MB_NUM_ORDERS(sb) + 1)
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2875  		return NULL;
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2876  	position = *pos + 1;
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2877  	return (void *) ((unsigned long) position);
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2878  }
51dc3ee0ba3798 Harshad Shirwadkar 2021-02-09  2879  

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

[-- Attachment #2: config.gz --]
[-- Type: application/gzip, Size: 39006 bytes --]

Improve group scanning in mballoc

[Harshad Shirwadkar]

This patch series improves cr 0 and cr 1 passes of the allocator
signficantly. Currently, at cr 0 and 1, we perform linear lookups to
find the matching groups. That's very inefficient for large file
systems where there are millions of block groups. At cr 0, we only
care about the groups that have the largest free order >= the
request's order and at cr 1 we only care about groups where average
fragment size > the request size. so, this patchset introduces new
data structures that allow us to perform cr 0 lookup in constant time
and cr 1 lookup in log (number of groups) time instead of linear.

For cr 0, we add a list for each order and all the groups are enqueued
to the appropriate list based on the largest free order in its buddy
bitmap. This allows us to lookup a match at cr 0 in constant time.

For cr 1, we add a new rb tree of groups sorted by largest fragment
size. This allows us to lookup a match for cr 1 in log (num groups)
time.

These optimizations can be enabled by passing "mb_optimize_scan" mount
option.

These changes may result in allocations to be spread across the block
device. While that would not matter some block devices (such as flash)
it may be a cause of concern for other block devices that benefit from
storing related content togetther such as disk. However, it can be
argued that in high fragmentation scenrio, especially for large disks,
it's still worth optimizing the scanning since in such cases, we get
cpu bound on group scanning instead of getting IO bound. Perhaps, in
future, we could dynamically turn this new optimization on based on
fragmentation levels for such devices.

Verified that there are no regressions in smoke tests (-g quick -c 4k).

Also, to demonstrate the effectiveness for the patch series, following
experiment was performed:

Created a highly fragmented disk of size 65TB. The disk had no
contiguous 2M regions. Following command was run consecutively for 3
times:

time dd if=/dev/urandom of=file bs=2M count=10

Here are the results with and without cr 0/1 optimizations:

|---------+------------------------------+---------------------------|
|         | Without CR 0/1 Optimizations | With CR 0/1 Optimizations |
|---------+------------------------------+---------------------------|
| 1st run | 5m1.871s                     | 2m47.642s                 |
| 2nd run | 2m28.390s                    | 0m0.611s                  |
| 3rd run | 2m26.530s                    | 0m1.255s                  |
|---------+------------------------------+---------------------------|

The patch [2/5] "ext4: add mballoc stats proc file" is a modified
version of the patch originally written by Artem Blagodarenko
(artem.blagodarenko@gmail.com). With that patch, I ran following
command with and without optimizations.

dd if=/dev/zero of=/mnt/file bs=2M count=2 conv=fsync

Without optimizations:
mballoc:
        reqs: 41
        success: 1
        groups_scanned: 63
        groups_considered: 20643620
        extents_scanned: 7851
                goal_hits: 0
                2^n_hits: 1
                breaks: 39
                lost: 0
        useless_c0_loops: 3
        useless_c1_loops: 39
        useless_c2_loops: 0
        useless_c3_loops: 0
        buddies_generated: 491561/491520
        buddies_time_used: 13078539152
        preallocated: 0
        discarded: 0

With optimizations:
mballoc:
        reqs: 42
        success: 1
        groups_scanned: 62
        groups_considered: 1011
        extents_scanned: 8062
                goal_hits: 0
                2^n_hits: 0
                breaks: 40
                lost: 0
        useless_c0_loops: 0
        useless_c1_loops: 0
        useless_c2_loops: 0
        useless_c3_loops: 0
        buddies_generated: 491561/491520
        buddies_time_used: 13165943648
        preallocated: 0
        discarded: 0

This shows that CR0 and CR1 optimizations get rid of useless CR0 and
CR1 loops altogether thereby significantly reducing the number of
groups that get considered.

Changes from V1:
---------------
- Incorporated Artem's patch that adds a few useful statistics for
  mballoc performace
- Added more fine grained locking for CR0 lists and CR1 tree
- Broke up ext4_mb_choose_next_group function to make code more
  readable
- Added a new mount option to provide a switch for these changes

Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>

Harshad Shirwadkar (5):
  ext4: drop s_mb_bal_lock and convert protected fields to atomic
  ext4: add mballoc stats proc file
  ext4: add MB_NUM_ORDERS macro
  ext4: improve cr 0 / cr 1 group scanning
  ext4: add proc files to monitor new structures

 fs/ext4/ext4.h    |  23 ++-
 fs/ext4/mballoc.c | 477 +++++++++++++++++++++++++++++++++++++++++++---
 fs/ext4/mballoc.h |   7 +
 fs/ext4/super.c   |   6 +-
 fs/ext4/sysfs.c   |   4 +
 5 files changed, 485 insertions(+), 32 deletions(-)

-- 
2.30.0.478.g8a0d178c01-goog

[PATCH v2 5/5] ext4: add proc files to monitor new structures

[Harshad Shirwadkar]

This patch adds a new file "mb_structs_summary" which allows us to see the
summary of the new allocator structures added in this series.

Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
---
 fs/ext4/ext4.h    |  1 +
 fs/ext4/mballoc.c | 84 +++++++++++++++++++++++++++++++++++++++++++++++
 fs/ext4/sysfs.c   |  2 ++
 3 files changed, 87 insertions(+)

diff --git a/fs/ext4/ext4.h b/fs/ext4/ext4.h
index 0601c997c87f..39830c07c27e 100644
--- a/fs/ext4/ext4.h
+++ b/fs/ext4/ext4.h
@@ -2817,6 +2817,7 @@ int __init ext4_fc_init_dentry_cache(void);
 
 /* mballoc.c */
 extern const struct seq_operations ext4_mb_seq_groups_ops;
+extern const struct seq_operations ext4_mb_seq_structs_summary_ops;
 extern long ext4_mb_stats;
 extern long ext4_mb_max_to_scan;
 extern int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset);
diff --git a/fs/ext4/mballoc.c b/fs/ext4/mballoc.c
index 63562f5f42f1..d9cb74787a47 100644
--- a/fs/ext4/mballoc.c
+++ b/fs/ext4/mballoc.c
@@ -2864,6 +2864,90 @@ int ext4_seq_mb_stats_show(struct seq_file *seq, void *offset)
 	return 0;
 }
 
+static void *ext4_mb_seq_structs_summary_start(struct seq_file *seq, loff_t *pos)
+{
+	struct super_block *sb = PDE_DATA(file_inode(seq->file));
+	unsigned long position;
+
+	read_lock(&EXT4_SB(sb)->s_mb_rb_lock);
+
+	if (*pos < 0 || *pos >= MB_NUM_ORDERS(sb) + 1)
+		return NULL;
+	position = *pos + 1;
+	return (void *) ((unsigned long) position);
+}
+
+static void *ext4_mb_seq_structs_summary_next(struct seq_file *seq, void *v, loff_t *pos)
+{
+	struct super_block *sb = PDE_DATA(file_inode(seq->file));
+	unsigned long position;
+
+	++*pos;
+	if (*pos < 0 || *pos >= MB_NUM_ORDERS(sb) + 1)
+		return NULL;
+	position = *pos + 1;
+	return (void *) ((unsigned long) position);
+}
+
+static int ext4_mb_seq_structs_summary_show(struct seq_file *seq, void *v)
+{
+	struct super_block *sb = PDE_DATA(file_inode(seq->file));
+	struct ext4_sb_info *sbi = EXT4_SB(sb);
+	unsigned long position = ((unsigned long) v);
+	struct ext4_group_info *grp;
+	struct rb_node *n;
+	int count, min, max;
+
+	position--;
+
+	if (position >= MB_NUM_ORDERS(sb)) {
+		seq_puts(seq, "Tree\n");
+		n = rb_first(&sbi->s_mb_avg_fragment_size_root);
+		if (!n) {
+			seq_puts(seq, "<Empty>\n");
+			return 0;
+		}
+		grp = rb_entry(n, struct ext4_group_info, bb_avg_fragment_size_rb);
+		min = grp->bb_fragments ? grp->bb_free / grp->bb_fragments : 0;
+		count = 1;
+		while (rb_next(n)) {
+			count++;
+			n = rb_next(n);
+		}
+		grp = rb_entry(n, struct ext4_group_info, bb_avg_fragment_size_rb);
+		max = grp->bb_fragments ? grp->bb_free / grp->bb_fragments : 0;
+
+		seq_printf(seq, "Min: %d, Max: %d, Num Nodes: %d\n",
+			   min, max, count);
+		return 0;
+	}
+
+	if (position == 0)
+		seq_puts(seq, "Largest Free Order Lists:\n");
+
+	seq_printf(seq, "Order %ld list: ", position);
+	count = 0;
+	list_for_each_entry(grp, &sbi->s_mb_largest_free_orders[position],
+			    bb_largest_free_order_node)
+		count++;
+	seq_printf(seq, "%d Groups\n", count);
+	return 0;
+}
+
+static void ext4_mb_seq_structs_summary_stop(struct seq_file *seq, void *v)
+{
+	struct super_block *sb = PDE_DATA(file_inode(seq->file));
+
+	read_unlock(&EXT4_SB(sb)->s_mb_rb_lock);
+}
+
+const struct seq_operations ext4_mb_seq_structs_summary_ops = {
+	.start  = ext4_mb_seq_structs_summary_start,
+	.next   = ext4_mb_seq_structs_summary_next,
+	.stop   = ext4_mb_seq_structs_summary_stop,
+	.show   = ext4_mb_seq_structs_summary_show,
+};
+
 static struct kmem_cache *get_groupinfo_cache(int blocksize_bits)
 {
 	int cache_index = blocksize_bits - EXT4_MIN_BLOCK_LOG_SIZE;
diff --git a/fs/ext4/sysfs.c b/fs/ext4/sysfs.c
index 752d1c261e2a..b78bc6b57bce 100644
--- a/fs/ext4/sysfs.c
+++ b/fs/ext4/sysfs.c
@@ -529,6 +529,8 @@ int ext4_register_sysfs(struct super_block *sb)
 				&ext4_mb_seq_groups_ops, sb);
 		proc_create_single_data("mb_stats", 0444, sbi->s_proc,
 				ext4_seq_mb_stats_show, sb);
+		proc_create_seq_data("mb_structs_summary", 0444, sbi->s_proc,
+				&ext4_mb_seq_structs_summary_ops, sb);
 	}
 	return 0;
 }
-- 
2.30.0.478.g8a0d178c01-goog

Re: [PATCH v2 5/5] ext4: add proc files to monitor new structures

[Andreas Dilger]

[-- Attachment #1: Type: text/plain, Size: 3210 bytes --]

On Feb 9, 2021, at 1:28 PM, Harshad Shirwadkar <harshadshirwadkar@gmail.com> wrote:
> 
> This patch adds a new file "mb_structs_summary" which allows us to see the
> summary of the new allocator structures added in this series.

Hmm, it is hard to visualize what these files will look like, could you
please include an example output in the commit message?  It looks like
they will no longer have one line per group, which is good, but maybe
one line per order?

If at all possible, it makes sense to have well-formatted output that
follows YAML formatting (https://yaml-online-parser.appspot.com/ can
verify this) so that it can be easily parsed (both as YAML and via
awk or other text processing tools).  That doesn't mean you need to
embed a YAML parser, just a few well-placed ':' and spaces...

Unfortunately, files like "mb_groups" were created before that wisdom
was learned, and are a bit of a nightmare to parse today.

A few comments inline...

> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
> 
> +static int ext4_mb_seq_structs_summary_show(struct seq_file *seq, void *v)
> +{
> +

Extra blank line here can be removed

> +	if (position >= MB_NUM_ORDERS(sb)) {
> +		seq_puts(seq, "Tree\n");

Prefer not to use capitalized words.

This should have a ':' like "tree:", but this still leaves the question
"what is the tree for?" so using "fragment_size_tree:" or similar would
be better.

> +		n = rb_first(&sbi->s_mb_avg_fragment_size_root);
> +		if (!n) {
> +			seq_puts(seq, "<Empty>\n");

I'm guessing this won't happen very often, but it might be easier if it
kept the same output format, so "min: 0, max: 0, num_nodes: 0", or just
initialize those values and then skip the intermediate processing below
before printing out the summary line (better because there is only one
place that is formatting the output, so it will be consistent)?

> +			return 0;
> +		}
> +		grp = rb_entry(n, struct ext4_group_info, bb_avg_fragment_size_rb);
> +		min = grp->bb_fragments ? grp->bb_free / grp->bb_fragments : 0;
> +		count = 1;
> +		while (rb_next(n)) {
> +			count++;
> +			n = rb_next(n);
> +		}
> +		grp = rb_entry(n, struct ext4_group_info, bb_avg_fragment_size_rb);
> +		max = grp->bb_fragments ? grp->bb_free / grp->bb_fragments : 0;
> +
> +		seq_printf(seq, "Min: %d, Max: %d, Num Nodes: %d\n",

These should be "%u" and not "%d"?  I'd assume none will ever be negative.

Prefer not to have spaces within keys, so that it is possible to use
e.g. 'awk /field:/ { print $2 }' to extract a value.  "num_nodes:" or
"tree_nodes: is better. To be a subset of "tree:" they should be
indented with 4 spaces or a tab:

    fragment_size_tree:
        tree_min: nnn
        tree_max: mmm
        tree_nodes: ooo


> +	if (position == 0)
> +		seq_puts(seq, "Largest Free Order Lists:\n");

Similarly, avoiding spaces in the key makes this easier to parse,
like "max_free_order_lists:" or similar.

> +	seq_printf(seq, "Order %ld list: ", position);

Here, "    list_order_%u: %u groups\n" would be more clear, and
can be printed in a single call instead of being split up.


Cheers, Andreas






[-- Attachment #2: Message signed with OpenPGP --]
[-- Type: application/pgp-signature, Size: 873 bytes --]

Re: [PATCH v2 5/5] ext4: add proc files to monitor new structures

[harshad shirwadkar]

On Fri, Feb 12, 2021 at 2:37 PM Andreas Dilger <adilger@dilger.ca> wrote:
>
> On Feb 9, 2021, at 1:28 PM, Harshad Shirwadkar <harshadshirwadkar@gmail.com> wrote:
> >
> > This patch adds a new file "mb_structs_summary" which allows us to see the
> > summary of the new allocator structures added in this series.
>
> Hmm, it is hard to visualize what these files will look like, could you
> please include an example output in the commit message?  It looks like
> they will no longer have one line per group, which is good, but maybe
> one line per order?
Sure, will do that in the next version.
>
> If at all possible, it makes sense to have well-formatted output that
> follows YAML formatting (https://yaml-online-parser.appspot.com/ can
> verify this) so that it can be easily parsed (both as YAML and via
> awk or other text processing tools).  That doesn't mean you need to
> embed a YAML parser, just a few well-placed ':' and spaces...
Yeah I like the idea. YAML sounds good to me!
>
> Unfortunately, files like "mb_groups" were created before that wisdom
> was learned, and are a bit of a nightmare to parse today.
>
> A few comments inline...
>
> > Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
> >
> > +static int ext4_mb_seq_structs_summary_show(struct seq_file *seq, void *v)
> > +{
> > +
>
> Extra blank line here can be removed
Ack
>
> > +     if (position >= MB_NUM_ORDERS(sb)) {
> > +             seq_puts(seq, "Tree\n");
>
> Prefer not to use capitalized words.
>
> This should have a ':' like "tree:", but this still leaves the question
> "what is the tree for?" so using "fragment_size_tree:" or similar would
> be better.
Ack
>
> > +             n = rb_first(&sbi->s_mb_avg_fragment_size_root);
> > +             if (!n) {
> > +                     seq_puts(seq, "<Empty>\n");
>
> I'm guessing this won't happen very often, but it might be easier if it
> kept the same output format, so "min: 0, max: 0, num_nodes: 0", or just
> initialize those values and then skip the intermediate processing below
> before printing out the summary line (better because there is only one
> place that is formatting the output, so it will be consistent)?
Sounds good!
>
> > +                     return 0;
> > +             }
> > +             grp = rb_entry(n, struct ext4_group_info, bb_avg_fragment_size_rb);
> > +             min = grp->bb_fragments ? grp->bb_free / grp->bb_fragments : 0;
> > +             count = 1;
> > +             while (rb_next(n)) {
> > +                     count++;
> > +                     n = rb_next(n);
> > +             }
> > +             grp = rb_entry(n, struct ext4_group_info, bb_avg_fragment_size_rb);
> > +             max = grp->bb_fragments ? grp->bb_free / grp->bb_fragments : 0;
> > +
> > +             seq_printf(seq, "Min: %d, Max: %d, Num Nodes: %d\n",
>
> These should be "%u" and not "%d"?  I'd assume none will ever be negative.
Ack
>
> Prefer not to have spaces within keys, so that it is possible to use
> e.g. 'awk /field:/ { print $2 }' to extract a value.  "num_nodes:" or
> "tree_nodes: is better. To be a subset of "tree:" they should be
> indented with 4 spaces or a tab:
>
>     fragment_size_tree:
>         tree_min: nnn
>         tree_max: mmm
>         tree_nodes: ooo
Ack
>
>
> > +     if (position == 0)
> > +             seq_puts(seq, "Largest Free Order Lists:\n");
>
> Similarly, avoiding spaces in the key makes this easier to parse,
> like "max_free_order_lists:" or similar.
>
> > +     seq_printf(seq, "Order %ld list: ", position);
>
> Here, "    list_order_%u: %u groups\n" would be more clear, and
> can be printed in a single call instead of being split up.
Ack

Sounds good, thanks for the feedback. I'll incorporate these changes
in the next version.

Thanks,
Harshad
>
>
> Cheers, Andreas
>
>
>
>
>