linux-kernel - Re: [PATCH v2 1/1] cpumask: Don't waste memory for sysfs cpulist nodes

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <Yy3LwItsnEtQkngk@smile.fi.intel.com>
Date:   Fri, 23 Sep 2022 18:07:44 +0300
From:   Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
To:     Rasmus Villemoes <linux@...musvillemoes.dk>
Cc:     Yury Norov <yury.norov@...il.com>, linux-kernel@...r.kernel.org,
        Phil Auld <pauld@...hat.com>
Subject: Re: [PATCH v2 1/1] cpumask: Don't waste memory for sysfs cpulist
 nodes

On Fri, Sep 23, 2022 at 02:19:14PM +0200, Rasmus Villemoes wrote:
> On 22/09/2022 21.49, Andy Shevchenko wrote:
> 
> > + * which allows to count the exact maximum length in the worst case,
> > + * i.e. when each second CPU is being listed.
> 
> I don't think that's actually the worst case. I think that would be
> where 2 out of 3 cpus are listed. I.e., with 16 cpus
> 
> 0-1,3-4,6-7,9-10,12-13,15
> 
> is certainly longer than
> 
> 0,2,4,6,8,10,12,14
> 
> It's trivial to see that no bitmap with four consecutive bits can be a
> worst-case, and any bitmap with some three consecutive bits is as bad as
> the same one with the middle bit cleared (the rep just changes a - to a
> ,), so the worst case is definitely obtained among bitmaps with at most
> two consecutive bits.

Thanks, indeed, your variant seems aligned with the comment in the file.
I have checked on paper what could be the lengths for a few number of CPUs
and this what it comes:

  nCPUs		size

  10		13
  16		25 (13 + 12)
  32		59 (13 + 46)

and it's visible that the amount of numbers of the same order (in each 10th)
is up to 7. Which means that the worst case is like 7 numbers for the same
10th. On top it's up to 3 ranges, means adding 2 characters per each for
the delimiters.

So,
  10	7*1 + 3*2				=  13
  16	7*1 + 3*2 +  4*2 +  2*2			=  25
  32	7*1 + 3*2 + 15*2 +  7*2			=  57
  100	7*1 + 3*2 + 63*2 + 31*2			= 389

Where 4 is from (16-10)*7/10 and 2 is half of it (for the range delimiters).
In similar way the [15, 7] and [63, 31].

Not sure how we should round the numbers (perhaps 15 should be 16, it will
yield 61 in the 3rd line).

Hence we may see that for 100 we need almost 400 bytes to have, and formula
nCPUs * 7 / 2 won't work precisely.

That said, my patch is wrong (based on the wrong assumption of a worst case)
but current approximation seems undersized as well.

-- 
With Best Regards,
Andy Shevchenko