LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: "Song Bao Hua (Barry Song)" <song.bao.hua@hisilicon.com>
To: Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
	Yury Norov <yury.norov@gmail.com>
Cc: Andy Shevchenko <andy.shevchenko@gmail.com>,
	Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
	Andrew Morton <akpm@linux-foundation.org>,
	Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
	Dave Hansen <dave.hansen@intel.com>,
	"Rasmus Villemoes" <linux@rasmusvillemoes.dk>,
	"Rafael J. Wysocki" <rafael@kernel.org>,
	Randy Dunlap <rdunlap@infradead.org>,
	Alexander Gordeev <agordeev@linux.ibm.com>,
	Stefano Brivio <sbrivio@redhat.com>,
	"Ma, Jianpeng" <jianpeng.ma@intel.com>,
	Valentin Schneider <valentin.schneider@arm.com>,
	"Peter Zijlstra (Intel)" <peterz@infradead.org>,
	Daniel Bristot de Oliveira <bristot@redhat.com>,
	Guodong Xu <guodong.xu@linaro.org>,
	tangchengchang <tangchengchang@huawei.com>,
	"Zengtao (B)" <prime.zeng@hisilicon.com>,
	yangyicong <yangyicong@huawei.com>,
	"tim.c.chen@linux.intel.com" <tim.c.chen@linux.intel.com>,
	Linuxarm <linuxarm@huawei.com>
Subject: RE: [PATCH v7 4/4] lib: test_bitmap: add bitmap_print_to_buf test cases
Date: Wed, 28 Jul 2021 09:08:30 +0000	[thread overview]
Message-ID: <e185c0c722b74da3baff1cb4e1c1eaf4@hisilicon.com> (raw)
In-Reply-To: <YPm8xVFSvola+RII@kroah.com>



> -----Original Message-----
> From: Greg Kroah-Hartman [mailto:gregkh@linuxfoundation.org]
> Sent: Friday, July 23, 2021 6:45 AM
> To: Yury Norov <yury.norov@gmail.com>
> Cc: Andy Shevchenko <andy.shevchenko@gmail.com>; Andy Shevchenko
> <andriy.shevchenko@linux.intel.com>; Song Bao Hua (Barry Song)
> <song.bao.hua@hisilicon.com>; Andrew Morton <akpm@linux-foundation.org>;
> Linux Kernel Mailing List <linux-kernel@vger.kernel.org>; Dave Hansen
> <dave.hansen@intel.com>; Rasmus Villemoes <linux@rasmusvillemoes.dk>; Rafael
> J. Wysocki <rafael@kernel.org>; Randy Dunlap <rdunlap@infradead.org>;
> Alexander Gordeev <agordeev@linux.ibm.com>; Stefano Brivio
> <sbrivio@redhat.com>; Ma, Jianpeng <jianpeng.ma@intel.com>; Valentin
> Schneider <valentin.schneider@arm.com>; Peter Zijlstra (Intel)
> <peterz@infradead.org>; Daniel Bristot de Oliveira <bristot@redhat.com>;
> Guodong Xu <guodong.xu@linaro.org>; tangchengchang
> <tangchengchang@huawei.com>; Zengtao (B) <prime.zeng@hisilicon.com>;
> yangyicong <yangyicong@huawei.com>; tim.c.chen@linux.intel.com; Linuxarm
> <linuxarm@huawei.com>
> Subject: Re: [PATCH v7 4/4] lib: test_bitmap: add bitmap_print_to_buf test cases
> 
> On Thu, Jul 22, 2021 at 11:27:05AM -0700, Yury Norov wrote:
> > On Thu, Jul 22, 2021 at 07:47:28PM +0200, Greg Kroah-Hartman wrote:
> > > On Thu, Jul 22, 2021 at 10:09:27AM -0700, Yury Norov wrote:
> > > > On Wed, Jul 21, 2021 at 01:40:36PM +0200, Greg Kroah-Hartman wrote:
> > > > > On Thu, Jul 15, 2021 at 04:23:32PM -0700, Yury Norov wrote:
> > > > > > On Fri, Jul 16, 2021 at 12:32:45AM +0300, Andy Shevchenko wrote:
> > > > > > > On Thu, Jul 15, 2021 at 11:48 PM Yury Norov <yury.norov@gmail.com>
> wrote:
> > > > > > > > On Thu, Jul 15, 2021 at 03:09:39PM +0300, Andy Shevchenko wrote:
> > > > > > > > > On Thu, Jul 15, 2021 at 11:58:56PM +1200, Barry Song wrote:
> > > > > > > > > > The added test items cover both cases where bitmap buf of
> the printed
> > > > > > > > > > result is greater than and less than 4KB.
> > > > > > > > > > And it also covers the case where offset for bitmap_print_to_buf
> is
> > > > > > > > > > non-zero which will happen when printed buf is larger than
> one page
> > > > > > > > > > in sysfs bin_attribute.
> > > > > > > > >
> > > > > > > > > More test cases is always a good thing, thanks!
> > > > > > > >
> > > > > > > > Generally yes. But in this case... I believe, Barry didn't write
> that
> > > > > > > > huge line below by himself. Most probably he copy-pasted the output
> of
> > > > > > > > his bitmap_print_buf() into the test. If so, this code tests nothing,
> > > > > > > > and just enforces current behavior of snprintf.
> > > > > > >
> > > > > > > I'm not sure I got what you are telling me. The big line is to test
> > > > > > > strings that are bigger than 4k.
> > > > > >
> > > > > > I'm trying to say that human are not able to verify correctness of
> > > > > > this line. The test is supposed to check bitmap_print_to_buf(), but
> > > > > > reference output itself is generated by bitmap_print_to_buf(). This
> > > > > > test will always pass by design, even if there's an error somewhere
> > > > > > in the middle, isn't it?
> > > > >
> > > > > Then please manually check it to verify it is correct or not.  Once we
> > > > > have it verified, that's fine, it will remain static in this test for
> > > > > always going forward.
> > > > >
> > > > > That's what "oracles" are for, there is nothing wrong with this test
> > > > > case or "proof" that I can see.
> > > > >

I have manually verified the test case from multiple 
different sides. The purpose is verifying large_bitmap,
large_mask and large_list in the test case are consistent.

What I have done includes:
1. snprintf(%*pbl) from large_bitmap to an intermediate buffer - vbf, 
and strcmp(vbf, large_list)
2. snprintf(%*pb) from large_bitmap to an intermediate buffer - vbf, 
and strcmp(vbf, large_mask)
3. bitmap_parselist from large_list to an intermediate bitmap - vb, 
and bitmap_equal(vb, large_bitmap)
4. bitmap_parse from large_mask to an intermediate bitmap - vb, 
and bitmap_equal(vb, large_bitmap)

diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index eb8ebaf12865..3efedc86a1b9 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -781,10 +781,45 @@ static const struct test_bitmap_print
test_print[] __initconst = {
        { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
 };

+#define NEW_API_VERIFIED
+
+#ifdef  NEW_API_VERIFIED
+#define VBF_SIZE (2 * PAGE_SIZE)
+static char vbf[VBF_SIZE];
+static int vb_bits = sizeof(large_bitmap) * BITS_PER_BYTE;
+DECLARE_BITMAP(vbmap, sizeof(large_bitmap) * BITS_PER_BYTE);
+#endif
+
 static void __init test_bitmap_print_buf(void)
 {
        int i;

+#ifdef NEW_API_VERIFIED
+               snprintf(vbf, VBF_SIZE, "%*pbl\n", vb_bits, large_bitmap);
+               if (strcmp(vbf, large_list))
+                       printk("%s WRONG large bitmap list, print pbl verified\n", __func__);
+               else
+                       printk("%s CORRECT large bitmap list, print pbl verified\n", __func__);
+
+               snprintf(vbf, VBF_SIZE, "%*pb\n", vb_bits, large_bitmap);
+               if (strcmp(vbf, large_mask))
+                       printk("%s WRONG large bitmap mask, print pb verified\n", __func__);
+               else
+                       printk("%s CORRECT large bitmap mask, print pb verified\n", __func__);
+
+               bitmap_parselist(large_list, vbmap, vb_bits);
+               if (bitmap_equal(vbmap, large_bitmap, vb_bits))
+                       printk("%s CORRECT large bitmap mask, parselist verified\n", __func__);
+               else
+                       printk("%s WRONG large bitmap mask, parselist verified\n", __func__);
+
+               bitmap_parse(large_mask, sizeof(large_mask), vbmap, vb_bits);
+               if (bitmap_equal(vbmap, large_bitmap, vb_bits))
+                       printk("%s CORRECT large bitmap mask, parselist verified\n", __func__);
+               else
+                       printk("%s WRONG large bitmap mask, parselist verified\n", __func__);
+#endif
+
        for (i = 0; i < ARRAY_SIZE(test_print); i++) {
                const struct test_bitmap_print *t = &test_print[i];
                int n;

Those cases are all good:
[    1.490355] test_bitmap: loaded.
[    1.494449] test_bitmap: parselist: 14: input is '0-2047:128/256'
OK, Time: 8384
[    1.507611] test_bitmap_print_buf CORRECT large bitmap list, print pbl verified
[    1.508415] test_bitmap_print_buf CORRECT large bitmap mask, print pb verified
[    1.510337] test_bitmap_print_buf CORRECT large bitmap mask, parselist verified
[    1.510770] test_bitmap_print_buf CORRECT large bitmap mask, parse verified
[    1.512833] test_bitmap: all 1945 tests passed

> > > > > > >
> > > > > > > ...
> > > > > > >
> > > > > > > > > > +static const char large_list[] __initconst = /* more than
> 4KB */
> > > > > > > > > > +
> "0,4,8,12,16,20,24,28,32-33,36-37,40-41,44-45,48-49,52-53,56-57,60-61,64,6
> 8,72,76,80,84,88,92,96-97,100-101,104-1"
> > > > > > > > > > +
> "05,108-109,112-113,116-117,120-121,124-125,128,132,136,140,144,148,152,15
> 6,160-161,164-165,168-169,172-173,176-1"
> > > > > > > > > > +
> "77,180-181,184-185,188-189,192,196,200,204,208,212,216,220,224-225,228-22
> 9,232-233,236-237,240-241,244-245,248-2"
> > > > > > > >
> > > > > > > > I don't like this behavior of the code: each individual line is
> not a
> > > > > > > > valid bitmap_list. I would prefer to split original bitmap and
> print
> > > > > > > > list representation of parts in a compatible format; considering
> a
> > > > > > > > receiving part of this splitting machinery.
> > > > > > >
> > > > > > > I agree that split is not the best here, but after all it's only
> 1
> > > > > > > line and this is on purpose.
> > > > > >
> > > > > > What I see is that bitmap_print_to_buf() is called many times,
> > > > >
> > > > > That is not what the above list shows at all, it's one long string all
> > > > > together, only split up to make it easier for us to work with.
> > > > >
> > > > > > and
> > > > > > each time it returns something that is not a valid bitmap list string.
> > > > > > If the caller was be able to concatenate all the lines returned by
> > > > > > bitmap_print_to_buf(), he'd probably get correct result. But in such
> > > > > > case, why don't he use scnprintf("pbl") directly?
> > > > >
> > > > > I do not understand the objection here at all.  This series is fixing
> a
> > > > > real problem that eeople are having
> > > >
> > > > I explicitly asked about an example of this problem. Barry answered in
> > > > a great length, but the key points are:
> > > >
> > > >
> https://lore.kernel.org/lkml/4ab928f1fb3e4420974dfafe4b32f5b7@hisilicon.co
> m/
> > > >
> > > >         > > So, the root problem here is that some machines have so many
> CPUs that
> > > >         > > their cpumask text representation may not fit into the full
> page in the
> > > >         > > worst case. Is my understanding correct? Can you share an example
> of
> > > >         > > such configuration?
> > > >         >
> > > >         > in my understanding, I have not found any machine which has really
> > > >         > caused the problem till now.
> > > >
> > > >         > [...]
> > > >         >
> > > >         > This doesn't really happen nowadays as the maximum
> > > >         > NR_CPUS is 8196 for X86_64 and 4096 for ARM64 since 8196 * 9 /
> 32 = 2305
> > > >         > is still smaller than 4KB page size.
> > > >
> > > >
> > > > If it's not true, can you or Barry please share such an example?
> > >
> > > So for a 4k page size, if you have every-other-cpu-enabled on x86, it
> > > will overflow this, right?
> > >
> > > And I have heard of systems much bigger than this as well.  Why do you
> > > not think that large number of CPUs are not around?
> >
> > I asked a question: is it urgent?, and I've got an answer: not urgent.
> 
> Just because people can not publically state that they are running Linux
> on bigger boxes than this, does NOT mean that they are not running Linux
> on bigger boxes than this.
> 
> So sometimes, you just have to trust that if someone says "hey, this is
> a problem over here", that maybe it really is a problem.
> 
> > > > > and your complaining about test
> > > > > strings is _VERY_ odd.
> > > >
> > > > The test itself is bad, but it's a minor issue.
> > > >
> > > > My main complain is that the bitmap part of this series introduces a
> > > > function that requires O(N^2) of CPU time and O(N) of memory to just
> > > > print a string. The existing snprintf does this in O(N) and O(1)
> > > > respectively. Additionally to that, the proposed function has some
> > > > flaws in design.
> > >
> > > Can you propose a better solution?
> >
> > Yes. Fix sysfs to let bin_attr store a pointer to relevant data.
> 
> Why?  It changes all the time and should be generated dynamically.
> 
> > Meanwhile, use this O(N^2) hack locally.
> 
> Who else uses this that it matters?
> 
> > > And is O(N^2) even an issue for this?
> >
> > If it's in lib/bitmap than yes, because it's exposed to the whole
> > kernel.
> 
> Who else will use it that it matters for speed?
> 

My understanding is that nobody else will print bitmap to a human-readable
mask or list except things like sysfs ABI for userspace. So I have been
arguing performance wouldn't be a concern here.
Those kernel modules who care about performance will directly run bit
operations like and/or/andnot etc on bitmap binaries rather than on a
list or a mask.

On the other hand, Yury's comment on providing a bitmap_max_string(),
which can estimate the max size of the mask or the list according to
bitmap size, might be able to help set a relatively more precise size
for the ABI sysfs file if people care about the file size of the sysfs
entry.

int bitmap_max_string_mask(int nbits)
{
	/* each 32bits need 9 bytes like "ffffffff,"
	return DIV_ROUND_UP(nbits, 32) * 9;
}
int bitmap_max_string_list(int nbits)
{
	...
}

Perhaps this could be an incremental patch after the current patchset
settle down.
Though I'm not quite sure it can really apply to bin_attribute, maybe
we can set the ret value to bin_attribute->bsize in some way?
But, not quite sure bin_attribute->bsize can use a dynamic value since
the size is needed while sysfs file is created:
int sysfs_add_file_mode_ns(struct kernfs_node *parent,
			   const struct attribute *attr, bool is_bin,
			   umode_t mode, kuid_t uid, kgid_t gid, const void *ns)
{
	struct lock_class_key *key = NULL;
	const struct kernfs_ops *ops;
	struct kernfs_node *kn;
	loff_t size;

	if (!is_bin) {
		...

		size = PAGE_SIZE;
	} else {
		struct bin_attribute *battr = (void *)attr;

		if (battr->mmap)
			ops = &sysfs_bin_kfops_mmap;
		...

		size = battr->size;
	}


	kn = __kernfs_create_file(parent, attr->name, mode & 0777, uid, gid,
				  size, ops, (void *)attr, ns, key);
	...
	return 0;
}

> And did you measure the speed of this?
> 
> thanks,
> 
> greg k-h

Thanks
Barry

  reply	other threads:[~2021-07-28  9:08 UTC|newest]

Thread overview: 35+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-07-15 11:58 [PATCH v7 0/4] use bin_attribute to break the size limitation of cpumap ABI Barry Song
2021-07-15 11:58 ` [PATCH v7 1/4] cpumask: introduce cpumap_print_to_buf to support large bitmask and list Barry Song
2021-07-15 15:28   ` Yury Norov
2021-07-15 21:08     ` Song Bao Hua (Barry Song)
2021-07-16  0:57     ` Song Bao Hua (Barry Song)
2021-07-15 11:58 ` [PATCH v7 2/4] topology: use bin_attribute to break the size limitation of cpumap ABI Barry Song
2021-07-16  8:49   ` Song Bao Hua (Barry Song)
2021-07-16 20:04     ` Yury Norov
2021-07-17  0:16       ` Song Bao Hua (Barry Song)
2021-07-17  1:12         ` Yury Norov
2021-07-19  9:07           ` andriy.shevchenko
2021-07-19 11:10             ` Song Bao Hua (Barry Song)
2021-07-19 17:10               ` Yury Norov
2021-07-21  9:30                 ` Song Bao Hua (Barry Song)
2021-07-15 11:58 ` [PATCH v7 3/4] drivers/base/node.c: " Barry Song
2021-07-15 11:58 ` [PATCH v7 4/4] lib: test_bitmap: add bitmap_print_to_buf test cases Barry Song
2021-07-15 12:09   ` Andy Shevchenko
2021-07-15 20:47     ` Yury Norov
2021-07-15 21:32       ` Andy Shevchenko
2021-07-15 23:23         ` Yury Norov
2021-07-16  0:41           ` Song Bao Hua (Barry Song)
2021-07-21 11:40           ` Greg Kroah-Hartman
2021-07-22 17:09             ` Yury Norov
2021-07-22 17:47               ` Greg Kroah-Hartman
2021-07-22 18:27                 ` Yury Norov
2021-07-22 18:36                   ` Andy Shevchenko
2021-07-22 18:45                   ` Greg Kroah-Hartman
2021-07-28  9:08                     ` Song Bao Hua (Barry Song) [this message]
2021-07-28  9:24                       ` Andy Shevchenko
2021-07-15 15:36   ` Yury Norov
2021-07-28 13:41 ` [PATCH v7 0/4] use bin_attribute to break the size limitation of cpumap ABI Greg KH
2021-07-28 14:53   ` Yury Norov
2021-07-28 15:25     ` Greg KH
2021-07-28 18:58 ` [PATCH] bitmap: extend comment to bitmap_print_to_buf Yury Norov
2021-07-29  6:04   ` Song Bao Hua (Barry Song)

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=e185c0c722b74da3baff1cb4e1c1eaf4@hisilicon.com \
    --to=song.bao.hua@hisilicon.com \
    --cc=agordeev@linux.ibm.com \
    --cc=akpm@linux-foundation.org \
    --cc=andriy.shevchenko@linux.intel.com \
    --cc=andy.shevchenko@gmail.com \
    --cc=bristot@redhat.com \
    --cc=dave.hansen@intel.com \
    --cc=gregkh@linuxfoundation.org \
    --cc=guodong.xu@linaro.org \
    --cc=jianpeng.ma@intel.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux@rasmusvillemoes.dk \
    --cc=linuxarm@huawei.com \
    --cc=peterz@infradead.org \
    --cc=prime.zeng@hisilicon.com \
    --cc=rafael@kernel.org \
    --cc=rdunlap@infradead.org \
    --cc=sbrivio@redhat.com \
    --cc=tangchengchang@huawei.com \
    --cc=tim.c.chen@linux.intel.com \
    --cc=valentin.schneider@arm.com \
    --cc=yangyicong@huawei.com \
    --cc=yury.norov@gmail.com \
    --subject='RE: [PATCH v7 4/4] lib: test_bitmap: add bitmap_print_to_buf test cases' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).