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

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

[Andy Shevchenko]

Currently the approximation is used which wastes the more memory
the more CPUs are present on the system. Proposed change calculates
the exact maximum needed in the worst case:

  NR_CPUS	old		new
  -------	---		---
  1 .. 1170	4096		4096
  1171 .. 1860	4098 ..	6510	4096
  ...		...		...
  2*4096	28672		19925
  4*4096	57344		43597
  8*4096	114688		92749
  16*4096	229376		191053
  32*4096	458752		403197
  64*4096	917504		861949
  128*4096	1835008		1779453
  256*4096	3670016		3670016

Under the hood the reccurent formula is being used:
  (5 - 0) * 2 +
    (50 - 5) * 3 +
      (500 - 50) * 4 +
        (5000 - 500) * 5 +
          ...
            (X[i] - X[i-1]) * i

which allows to count the exact maximum length in the worst case,
i.e. when each second CPU is being listed. For backward compatibility
for more than 1170 and less than 1861 CPUs the page size is preserved.

For less than 1171 and more than 1 million CPUs the old is being used.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
---
v2: described better the advantage for 1171..1860 CPUs cases
 include/linux/cpumask.h | 48 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 1b442fb2001f..12cf0905ca74 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -1122,6 +1122,21 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
  *
  * for cpumap NR_CPUS * 9/32 - 1 should be an exact length.
  *
+ * for cpulist the reccurent formula is being used:
+ *   (5 - 0) * 2 +
+ *     (50 - 5) * 3 +
+ *       (500 - 50) * 4 +
+ *         (5000 - 500) * 5 +
+ *           ...
+ *             (X[i] - X[i-1]) * i
+ *
+ * which allows to count the exact maximum length in the worst case,
+ * i.e. when each second CPU is being listed. For backward compatibility
+ * for more than 1170 and less than 1861 CPUs the page size is preserved.
+ *
+ * For less than 1171 and more than 1 million CPUs the old is being used
+ * as described below:
+ *
  * For cpulist 7 is (ceil(log10(NR_CPUS)) + 1) allowing for NR_CPUS to be up
  * to 2 orders of magnitude larger than 8192. And then we divide by 2 to
  * cover a worst-case of every other cpu being on one of two nodes for a
@@ -1132,6 +1147,39 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
  */
 #define CPUMAP_FILE_MAX_BYTES  (((NR_CPUS * 9)/32 > PAGE_SIZE) \
 					? (NR_CPUS * 9)/32 - 1 : PAGE_SIZE)
+
+#define __CPULIST_FOR_10(x)		(((x + 1) / 2 - 0)     * 2)
+#define __CPULIST_FOR_100(x)		(((x + 1) / 2 - 5)     * 3)
+#define __CPULIST_FOR_1000(x)		(((x + 1) / 2 - 50)    * 4)
+#define __CPULIST_FOR_10000(x)		(((x + 1) / 2 - 500)   * 5)
+#define __CPULIST_FOR_100000(x)		(((x + 1) / 2 - 5000)  * 6)
+#define __CPULIST_FOR_1000000(x)	(((x + 1) / 2 - 50000) * 7)
+
+#if NR_CPUS < 1861
+#define CPULIST_FILE_MAX_BYTES	PAGE_SIZE
+#elif NR_CPUS < 10000
+#define CPULIST_FILE_MAX_BYTES			\
+	 (__CPULIST_FOR_10(10) +		\
+	  __CPULIST_FOR_100(100) +		\
+	  __CPULIST_FOR_1000(1000) +		\
+	  __CPULIST_FOR_10000(NR_CPUS))
+#elif NR_CPUS < 100000
+#define CPULIST_FILE_MAX_BYTES			\
+	 (__CPULIST_FOR_10(10) +		\
+	  __CPULIST_FOR_100(100) +		\
+	  __CPULIST_FOR_1000(1000) +		\
+	  __CPULIST_FOR_10000(10000) +		\
+	  __CPULIST_FOR_100000(NR_CPUS))
+#elif NR_CPUS < 1000000
+#define CPULIST_FILE_MAX_BYTES			\
+	 (__CPULIST_FOR_10(10) +		\
+	  __CPULIST_FOR_100(100) +		\
+	  __CPULIST_FOR_1000(1000) +		\
+	  __CPULIST_FOR_10000(10000) +		\
+	  __CPULIST_FOR_100000(100000) +	\
+	  __CPULIST_FOR_1000000(NR_CPUS))
+#else
 #define CPULIST_FILE_MAX_BYTES  (((NR_CPUS * 7)/2 > PAGE_SIZE) ? (NR_CPUS * 7)/2 : PAGE_SIZE)
+#endif
 
 #endif /* __LINUX_CPUMASK_H */
-- 
2.35.1

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

[Yury Norov]

 + Petr Štetiar <ynezz@true.cz>,
 + Greg Kroah-Hartman <gregkh@linuxfoundation.org>

On Thu, Sep 22, 2022 at 10:49:54PM +0300, Andy Shevchenko wrote:
> Currently the approximation is used which wastes the more memory
> the more CPUs are present on the system. Proposed change calculates
> the exact maximum needed in the worst case:
> 
>   NR_CPUS	old		new
>   -------	---		---
>   1 .. 1170	4096		4096
>   1171 .. 1860	4098 ..	6510	4096
>   ...		...		...
>   2*4096	28672		19925
>   4*4096	57344		43597
>   8*4096	114688		92749
>   16*4096	229376		191053
>   32*4096	458752		403197
>   64*4096	917504		861949
>   128*4096	1835008		1779453
>   256*4096	3670016		3670016
> 
> Under the hood the reccurent formula is being used:
>   (5 - 0) * 2 +
>     (50 - 5) * 3 +
>       (500 - 50) * 4 +
>         (5000 - 500) * 5 +
>           ...
>             (X[i] - X[i-1]) * i
> 
> which allows to count the exact maximum length in the worst case,
> i.e. when each second CPU is being listed. For backward compatibility
> for more than 1170 and less than 1861 CPUs the page size is preserved.
> 
> For less than 1171 and more than 1 million CPUs the old is being used.

1861

> 
> Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> ---
> v2: described better the advantage for 1171..1860 CPUs cases
>  include/linux/cpumask.h | 48 +++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 48 insertions(+)
> 
> diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> index 1b442fb2001f..12cf0905ca74 100644
> --- a/include/linux/cpumask.h
> +++ b/include/linux/cpumask.h
> @@ -1122,6 +1122,21 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
>   *
>   * for cpumap NR_CPUS * 9/32 - 1 should be an exact length.
>   *
> + * for cpulist the reccurent formula is being used:
> + *   (5 - 0) * 2 +
> + *     (50 - 5) * 3 +
> + *       (500 - 50) * 4 +
> + *         (5000 - 500) * 5 +
> + *           ...
> + *             (X[i] - X[i-1]) * i
> + *
> + * which allows to count the exact maximum length in the worst case,
> + * i.e. when each second CPU is being listed. For backward compatibility
> + * for more than 1170 and less than 1861 CPUs the page size is preserved.
> + *
> + * For less than 1171 and more than 1 million CPUs the old is being used
> + * as described below:
> + *
>   * For cpulist 7 is (ceil(log10(NR_CPUS)) + 1) allowing for NR_CPUS to be up
>   * to 2 orders of magnitude larger than 8192. And then we divide by 2 to
>   * cover a worst-case of every other cpu being on one of two nodes for a
> @@ -1132,6 +1147,39 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
>   */
>  #define CPUMAP_FILE_MAX_BYTES  (((NR_CPUS * 9)/32 > PAGE_SIZE) \
>  					? (NR_CPUS * 9)/32 - 1 : PAGE_SIZE)
> +
> +#define __CPULIST_FOR_10(x)		(((x + 1) / 2 - 0)     * 2)
> +#define __CPULIST_FOR_100(x)		(((x + 1) / 2 - 5)     * 3)
> +#define __CPULIST_FOR_1000(x)		(((x + 1) / 2 - 50)    * 4)
> +#define __CPULIST_FOR_10000(x)		(((x + 1) / 2 - 500)   * 5)
> +#define __CPULIST_FOR_100000(x)		(((x + 1) / 2 - 5000)  * 6)
> +#define __CPULIST_FOR_1000000(x)	(((x + 1) / 2 - 50000) * 7)

The defs below will be nicer if you make it like this:

  #define __CPULIST_FOR_10(x)  (((x + 1) / 2 - 0)     * 2)
  #define __CPULIST_FOR_100(x) __CPULIST_FOR_10(10) + (((x + 1) / 2 - 5) * 3)
  #define __CPULIST_FOR_1000(x)	__CPULIST_FOR_100(100) + (((x + 1) / 2 - 50) * 4)
  ...



> +#if NR_CPUS < 1861
> +#define CPULIST_FILE_MAX_BYTES	PAGE_SIZE

The comment says:
  for more than 1170 and less than 1861 CPUs the page size is preserved.

Which doesn't look correct. Looks like it should be:
  for less than 1861 CPUs the page size is preserved.

Or I miss something?

> +#elif NR_CPUS < 10000
> +#define CPULIST_FILE_MAX_BYTES			\
> +	 (__CPULIST_FOR_10(10) +		\
> +	  __CPULIST_FOR_100(100) +		\
> +	  __CPULIST_FOR_1000(1000) +		\
> +	  __CPULIST_FOR_10000(NR_CPUS))
> +#elif NR_CPUS < 100000
> +#define CPULIST_FILE_MAX_BYTES			\
> +	 (__CPULIST_FOR_10(10) +		\
> +	  __CPULIST_FOR_100(100) +		\
> +	  __CPULIST_FOR_1000(1000) +		\
> +	  __CPULIST_FOR_10000(10000) +		\
> +	  __CPULIST_FOR_100000(NR_CPUS))
> +#elif NR_CPUS < 1000000
> +#define CPULIST_FILE_MAX_BYTES			\
> +	 (__CPULIST_FOR_10(10) +		\
> +	  __CPULIST_FOR_100(100) +		\
> +	  __CPULIST_FOR_1000(1000) +		\
> +	  __CPULIST_FOR_10000(10000) +		\
> +	  __CPULIST_FOR_100000(100000) +	\
> +	  __CPULIST_FOR_1000000(NR_CPUS))
> +#else
>  #define CPULIST_FILE_MAX_BYTES  (((NR_CPUS * 7)/2 > PAGE_SIZE) ? (NR_CPUS * 7)/2 : PAGE_SIZE)
> +#endif
>  
>  #endif /* __LINUX_CPUMASK_H */
> -- 
> 2.35.1

I'm OK to take this in replace for Phil's version, but the commit that
introduces CPULIST_FILE_MAX_BYTES is already in mainline: 7ee951acd31a8
("drivers/base: fix userspace break from using bin_attributes for cpumap
and cpulist"). Can you rebase it on top of v6.0-rc6?

Greg, since Andy's version is more precise, I'd like to send a pull
request with it in -rc7. Can you drop Phil's patch so I'll go with
this one?

Thanks,
Yury

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

[Phil Auld]

On Thu, Sep 22, 2022 at 01:41:40PM -0700 Yury Norov wrote:
>  + Petr Štetiar <ynezz@true.cz>,
>  + Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> 
> On Thu, Sep 22, 2022 at 10:49:54PM +0300, Andy Shevchenko wrote:
> > Currently the approximation is used which wastes the more memory
> > the more CPUs are present on the system. Proposed change calculates
> > the exact maximum needed in the worst case:
> > 
> >   NR_CPUS	old		new
> >   -------	---		---
> >   1 .. 1170	4096		4096
> >   1171 .. 1860	4098 ..	6510	4096
> >   ...		...		...
> >   2*4096	28672		19925
> >   4*4096	57344		43597
> >   8*4096	114688		92749
> >   16*4096	229376		191053
> >   32*4096	458752		403197
> >   64*4096	917504		861949
> >   128*4096	1835008		1779453
> >   256*4096	3670016		3670016
> > 
> > Under the hood the reccurent formula is being used:
> >   (5 - 0) * 2 +
> >     (50 - 5) * 3 +
> >       (500 - 50) * 4 +
> >         (5000 - 500) * 5 +
> >           ...
> >             (X[i] - X[i-1]) * i
> > 
> > which allows to count the exact maximum length in the worst case,
> > i.e. when each second CPU is being listed. For backward compatibility
> > for more than 1170 and less than 1861 CPUs the page size is preserved.
> > 
> > For less than 1171 and more than 1 million CPUs the old is being used.
> 
> 1861
> 
> > 
> > Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> > ---
> > v2: described better the advantage for 1171..1860 CPUs cases
> >  include/linux/cpumask.h | 48 +++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 48 insertions(+)
> > 
> > diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> > index 1b442fb2001f..12cf0905ca74 100644
> > --- a/include/linux/cpumask.h
> > +++ b/include/linux/cpumask.h
> > @@ -1122,6 +1122,21 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> >   *
> >   * for cpumap NR_CPUS * 9/32 - 1 should be an exact length.
> >   *
> > + * for cpulist the reccurent formula is being used:
> > + *   (5 - 0) * 2 +
> > + *     (50 - 5) * 3 +
> > + *       (500 - 50) * 4 +
> > + *         (5000 - 500) * 5 +
> > + *           ...
> > + *             (X[i] - X[i-1]) * i
> > + *
> > + * which allows to count the exact maximum length in the worst case,
> > + * i.e. when each second CPU is being listed. For backward compatibility
> > + * for more than 1170 and less than 1861 CPUs the page size is preserved.
> > + *
> > + * For less than 1171 and more than 1 million CPUs the old is being used
> > + * as described below:
> > + *
> >   * For cpulist 7 is (ceil(log10(NR_CPUS)) + 1) allowing for NR_CPUS to be up
> >   * to 2 orders of magnitude larger than 8192. And then we divide by 2 to
> >   * cover a worst-case of every other cpu being on one of two nodes for a
> > @@ -1132,6 +1147,39 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> >   */
> >  #define CPUMAP_FILE_MAX_BYTES  (((NR_CPUS * 9)/32 > PAGE_SIZE) \
> >  					? (NR_CPUS * 9)/32 - 1 : PAGE_SIZE)
> > +
> > +#define __CPULIST_FOR_10(x)		(((x + 1) / 2 - 0)     * 2)
> > +#define __CPULIST_FOR_100(x)		(((x + 1) / 2 - 5)     * 3)
> > +#define __CPULIST_FOR_1000(x)		(((x + 1) / 2 - 50)    * 4)
> > +#define __CPULIST_FOR_10000(x)		(((x + 1) / 2 - 500)   * 5)
> > +#define __CPULIST_FOR_100000(x)		(((x + 1) / 2 - 5000)  * 6)
> > +#define __CPULIST_FOR_1000000(x)	(((x + 1) / 2 - 50000) * 7)
> 
> The defs below will be nicer if you make it like this:
> 
>   #define __CPULIST_FOR_10(x)  (((x + 1) / 2 - 0)     * 2)
>   #define __CPULIST_FOR_100(x) __CPULIST_FOR_10(10) + (((x + 1) / 2 - 5) * 3)
>   #define __CPULIST_FOR_1000(x)	__CPULIST_FOR_100(100) + (((x + 1) / 2 - 50) * 4)
>   ...
> 
> 
> 
> > +#if NR_CPUS < 1861
> > +#define CPULIST_FILE_MAX_BYTES	PAGE_SIZE
> 
> The comment says:
>   for more than 1170 and less than 1861 CPUs the page size is preserved.
> 
> Which doesn't look correct. Looks like it should be:
>   for less than 1861 CPUs the page size is preserved.
> 
> Or I miss something?
> 
> > +#elif NR_CPUS < 10000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(NR_CPUS))
> > +#elif NR_CPUS < 100000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(10000) +		\
> > +	  __CPULIST_FOR_100000(NR_CPUS))
> > +#elif NR_CPUS < 1000000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(10000) +		\
> > +	  __CPULIST_FOR_100000(100000) +	\
> > +	  __CPULIST_FOR_1000000(NR_CPUS))
> > +#else
> >  #define CPULIST_FILE_MAX_BYTES  (((NR_CPUS * 7)/2 > PAGE_SIZE) ? (NR_CPUS * 7)/2 : PAGE_SIZE)
> > +#endif
> >  
> >  #endif /* __LINUX_CPUMASK_H */
> > -- 
> > 2.35.1
> 
> I'm OK to take this in replace for Phil's version, but the commit that
> introduces CPULIST_FILE_MAX_BYTES is already in mainline: 7ee951acd31a8
> ("drivers/base: fix userspace break from using bin_attributes for cpumap
> and cpulist"). Can you rebase it on top of v6.0-rc6?
> 
> Greg, since Andy's version is more precise, I'd like to send a pull
> request with it in -rc7. Can you drop Phil's patch so I'll go with
> this one?
>

This changes the other of the 2 macros and looks like it is already on
top of the fix to CPUMAP_FILE_MAX_BYTES.

It should be able to go right on top of a tree with that one in it, I think.

With the comment fixed up as you note above I'll git Reviewed-by:
and Tested-by: shortly.

This one is a refinement of 7ee951acd31a8 though and is not a critical as
the one Greg was talking about and Petr hit. 


Cheers,
Phil


> Thanks,
> Yury
> 

-- 

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

[Yury Norov]

On Thu, Sep 22, 2022 at 05:43:38PM -0400, Phil Auld wrote:
> On Thu, Sep 22, 2022 at 01:41:40PM -0700 Yury Norov wrote:
> >  + Petr Štetiar <ynezz@true.cz>,
> >  + Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> > 
> > On Thu, Sep 22, 2022 at 10:49:54PM +0300, Andy Shevchenko wrote:
> > > Currently the approximation is used which wastes the more memory
> > > the more CPUs are present on the system. Proposed change calculates
> > > the exact maximum needed in the worst case:
> > > 
> > >   NR_CPUS	old		new
> > >   -------	---		---
> > >   1 .. 1170	4096		4096
> > >   1171 .. 1860	4098 ..	6510	4096
> > >   ...		...		...
> > >   2*4096	28672		19925
> > >   4*4096	57344		43597
> > >   8*4096	114688		92749
> > >   16*4096	229376		191053
> > >   32*4096	458752		403197
> > >   64*4096	917504		861949
> > >   128*4096	1835008		1779453
> > >   256*4096	3670016		3670016
> > > 
> > > Under the hood the reccurent formula is being used:
> > >   (5 - 0) * 2 +
> > >     (50 - 5) * 3 +
> > >       (500 - 50) * 4 +
> > >         (5000 - 500) * 5 +
> > >           ...
> > >             (X[i] - X[i-1]) * i
> > > 
> > > which allows to count the exact maximum length in the worst case,
> > > i.e. when each second CPU is being listed. For backward compatibility
> > > for more than 1170 and less than 1861 CPUs the page size is preserved.
> > > 
> > > For less than 1171 and more than 1 million CPUs the old is being used.
> > 
> > 1861
> > 
> > > 
> > > Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> > > ---
> > > v2: described better the advantage for 1171..1860 CPUs cases
> > >  include/linux/cpumask.h | 48 +++++++++++++++++++++++++++++++++++++++++
> > >  1 file changed, 48 insertions(+)
> > > 
> > > diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> > > index 1b442fb2001f..12cf0905ca74 100644
> > > --- a/include/linux/cpumask.h
> > > +++ b/include/linux/cpumask.h
> > > @@ -1122,6 +1122,21 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> > >   *
> > >   * for cpumap NR_CPUS * 9/32 - 1 should be an exact length.
> > >   *
> > > + * for cpulist the reccurent formula is being used:
> > > + *   (5 - 0) * 2 +
> > > + *     (50 - 5) * 3 +
> > > + *       (500 - 50) * 4 +
> > > + *         (5000 - 500) * 5 +
> > > + *           ...
> > > + *             (X[i] - X[i-1]) * i
> > > + *
> > > + * which allows to count the exact maximum length in the worst case,
> > > + * i.e. when each second CPU is being listed. For backward compatibility
> > > + * for more than 1170 and less than 1861 CPUs the page size is preserved.
> > > + *
> > > + * For less than 1171 and more than 1 million CPUs the old is being used
> > > + * as described below:
> > > + *
> > >   * For cpulist 7 is (ceil(log10(NR_CPUS)) + 1) allowing for NR_CPUS to be up
> > >   * to 2 orders of magnitude larger than 8192. And then we divide by 2 to
> > >   * cover a worst-case of every other cpu being on one of two nodes for a
> > > @@ -1132,6 +1147,39 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> > >   */
> > >  #define CPUMAP_FILE_MAX_BYTES  (((NR_CPUS * 9)/32 > PAGE_SIZE) \
> > >  					? (NR_CPUS * 9)/32 - 1 : PAGE_SIZE)
> > > +
> > > +#define __CPULIST_FOR_10(x)		(((x + 1) / 2 - 0)     * 2)
> > > +#define __CPULIST_FOR_100(x)		(((x + 1) / 2 - 5)     * 3)
> > > +#define __CPULIST_FOR_1000(x)		(((x + 1) / 2 - 50)    * 4)
> > > +#define __CPULIST_FOR_10000(x)		(((x + 1) / 2 - 500)   * 5)
> > > +#define __CPULIST_FOR_100000(x)		(((x + 1) / 2 - 5000)  * 6)
> > > +#define __CPULIST_FOR_1000000(x)	(((x + 1) / 2 - 50000) * 7)
> > 
> > The defs below will be nicer if you make it like this:
> > 
> >   #define __CPULIST_FOR_10(x)  (((x + 1) / 2 - 0)     * 2)
> >   #define __CPULIST_FOR_100(x) __CPULIST_FOR_10(10) + (((x + 1) / 2 - 5) * 3)
> >   #define __CPULIST_FOR_1000(x)	__CPULIST_FOR_100(100) + (((x + 1) / 2 - 50) * 4)
> >   ...
> > 
> > 
> > 
> > > +#if NR_CPUS < 1861
> > > +#define CPULIST_FILE_MAX_BYTES	PAGE_SIZE
> > 
> > The comment says:
> >   for more than 1170 and less than 1861 CPUs the page size is preserved.
> > 
> > Which doesn't look correct. Looks like it should be:
> >   for less than 1861 CPUs the page size is preserved.
> > 
> > Or I miss something?
> > 
> > > +#elif NR_CPUS < 10000
> > > +#define CPULIST_FILE_MAX_BYTES			\
> > > +	 (__CPULIST_FOR_10(10) +		\
> > > +	  __CPULIST_FOR_100(100) +		\
> > > +	  __CPULIST_FOR_1000(1000) +		\
> > > +	  __CPULIST_FOR_10000(NR_CPUS))
> > > +#elif NR_CPUS < 100000
> > > +#define CPULIST_FILE_MAX_BYTES			\
> > > +	 (__CPULIST_FOR_10(10) +		\
> > > +	  __CPULIST_FOR_100(100) +		\
> > > +	  __CPULIST_FOR_1000(1000) +		\
> > > +	  __CPULIST_FOR_10000(10000) +		\
> > > +	  __CPULIST_FOR_100000(NR_CPUS))
> > > +#elif NR_CPUS < 1000000
> > > +#define CPULIST_FILE_MAX_BYTES			\
> > > +	 (__CPULIST_FOR_10(10) +		\
> > > +	  __CPULIST_FOR_100(100) +		\
> > > +	  __CPULIST_FOR_1000(1000) +		\
> > > +	  __CPULIST_FOR_10000(10000) +		\
> > > +	  __CPULIST_FOR_100000(100000) +	\
> > > +	  __CPULIST_FOR_1000000(NR_CPUS))
> > > +#else
> > >  #define CPULIST_FILE_MAX_BYTES  (((NR_CPUS * 7)/2 > PAGE_SIZE) ? (NR_CPUS * 7)/2 : PAGE_SIZE)
> > > +#endif
> > >  
> > >  #endif /* __LINUX_CPUMASK_H */
> > > -- 
> > > 2.35.1
> > 
> > I'm OK to take this in replace for Phil's version, but the commit that
> > introduces CPULIST_FILE_MAX_BYTES is already in mainline: 7ee951acd31a8
> > ("drivers/base: fix userspace break from using bin_attributes for cpumap
> > and cpulist"). Can you rebase it on top of v6.0-rc6?
> > 
> > Greg, since Andy's version is more precise, I'd like to send a pull
> > request with it in -rc7. Can you drop Phil's patch so I'll go with
> > this one?
> >
> 
> This changes the other of the 2 macros and looks like it is already on
> top of the fix to CPUMAP_FILE_MAX_BYTES.
> 
> It should be able to go right on top of a tree with that one in it, I think.

Indeed. (I reviewed it from a phone and missed that.)
 
> With the comment fixed up as you note above I'll git Reviewed-by:
> and Tested-by: shortly.
> 
> This one is a refinement of 7ee951acd31a8 though and is not a critical as
> the one Greg was talking about and Petr hit. 

OK with that. Let's see what Greg will say about how to handle it
better. I'm OK with both ways.

Thanks,
Yury

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

[Phil Auld]

Hi Andy,

On Thu, Sep 22, 2022 at 10:49:54PM +0300 Andy Shevchenko wrote:
> Currently the approximation is used which wastes the more memory
> the more CPUs are present on the system. Proposed change calculates
> the exact maximum needed in the worst case:
> 
>   NR_CPUS	old		new
>   -------	---		---
>   1 .. 1170	4096		4096
>   1171 .. 1860	4098 ..	6510	4096
>   ...		...		...
>   2*4096	28672		19925
>   4*4096	57344		43597
>   8*4096	114688		92749
>   16*4096	229376		191053
>   32*4096	458752		403197
>   64*4096	917504		861949
>   128*4096	1835008		1779453
>   256*4096	3670016		3670016
> 
> Under the hood the reccurent formula is being used:
>   (5 - 0) * 2 +
>     (50 - 5) * 3 +
>       (500 - 50) * 4 +
>         (5000 - 500) * 5 +
>           ...
>             (X[i] - X[i-1]) * i
> 
> which allows to count the exact maximum length in the worst case,
> i.e. when each second CPU is being listed. For backward compatibility
> for more than 1170 and less than 1861 CPUs the page size is preserved.
> 
> For less than 1171 and more than 1 million CPUs the old is being used.

The memory is not really wasted since it's probably temporary in userspace
and in the kernel it _is_ temporary and is only the length of the kasprintf
string, which is most of the time much less.

But that said, it is more accurate than the previous estimate.

I was wondering if you were going to try to come up with a suitable
compile time macro :)

I tested 2, 8192 and 16k since the kernel does not want to build for other
reasons with NR_CPUS at 32k.

Reviewed-by: Phil Auld <pauld@redhat.com>
Tested-by: Phil Auld <pauld@redhat.com>


> 
> Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> ---
> v2: described better the advantage for 1171..1860 CPUs cases
>  include/linux/cpumask.h | 48 +++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 48 insertions(+)
> 
> diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> index 1b442fb2001f..12cf0905ca74 100644
> --- a/include/linux/cpumask.h
> +++ b/include/linux/cpumask.h
> @@ -1122,6 +1122,21 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
>   *
>   * for cpumap NR_CPUS * 9/32 - 1 should be an exact length.
>   *
> + * for cpulist the reccurent formula is being used:
> + *   (5 - 0) * 2 +
> + *     (50 - 5) * 3 +
> + *       (500 - 50) * 4 +
> + *         (5000 - 500) * 5 +
> + *           ...
> + *             (X[i] - X[i-1]) * i
> + *
> + * which allows to count the exact maximum length in the worst case,
> + * i.e. when each second CPU is being listed. For backward compatibility
> + * for more than 1170 and less than 1861 CPUs the page size is preserved.
> + *
> + * For less than 1171 and more than 1 million CPUs the old is being used
> + * as described below:
> + *
>   * For cpulist 7 is (ceil(log10(NR_CPUS)) + 1) allowing for NR_CPUS to be up
>   * to 2 orders of magnitude larger than 8192. And then we divide by 2 to
>   * cover a worst-case of every other cpu being on one of two nodes for a
> @@ -1132,6 +1147,39 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
>   */
>  #define CPUMAP_FILE_MAX_BYTES  (((NR_CPUS * 9)/32 > PAGE_SIZE) \
>  					? (NR_CPUS * 9)/32 - 1 : PAGE_SIZE)
> +
> +#define __CPULIST_FOR_10(x)		(((x + 1) / 2 - 0)     * 2)
> +#define __CPULIST_FOR_100(x)		(((x + 1) / 2 - 5)     * 3)
> +#define __CPULIST_FOR_1000(x)		(((x + 1) / 2 - 50)    * 4)
> +#define __CPULIST_FOR_10000(x)		(((x + 1) / 2 - 500)   * 5)
> +#define __CPULIST_FOR_100000(x)		(((x + 1) / 2 - 5000)  * 6)
> +#define __CPULIST_FOR_1000000(x)	(((x + 1) / 2 - 50000) * 7)
> +
> +#if NR_CPUS < 1861
> +#define CPULIST_FILE_MAX_BYTES	PAGE_SIZE
> +#elif NR_CPUS < 10000
> +#define CPULIST_FILE_MAX_BYTES			\
> +	 (__CPULIST_FOR_10(10) +		\
> +	  __CPULIST_FOR_100(100) +		\
> +	  __CPULIST_FOR_1000(1000) +		\
> +	  __CPULIST_FOR_10000(NR_CPUS))
> +#elif NR_CPUS < 100000
> +#define CPULIST_FILE_MAX_BYTES			\
> +	 (__CPULIST_FOR_10(10) +		\
> +	  __CPULIST_FOR_100(100) +		\
> +	  __CPULIST_FOR_1000(1000) +		\
> +	  __CPULIST_FOR_10000(10000) +		\
> +	  __CPULIST_FOR_100000(NR_CPUS))
> +#elif NR_CPUS < 1000000
> +#define CPULIST_FILE_MAX_BYTES			\
> +	 (__CPULIST_FOR_10(10) +		\
> +	  __CPULIST_FOR_100(100) +		\
> +	  __CPULIST_FOR_1000(1000) +		\
> +	  __CPULIST_FOR_10000(10000) +		\
> +	  __CPULIST_FOR_100000(100000) +	\
> +	  __CPULIST_FOR_1000000(NR_CPUS))
> +#else
>  #define CPULIST_FILE_MAX_BYTES  (((NR_CPUS * 7)/2 > PAGE_SIZE) ? (NR_CPUS * 7)/2 : PAGE_SIZE)
> +#endif
>  
>  #endif /* __LINUX_CPUMASK_H */
> -- 
> 2.35.1
> 


Cheers,
Phil


-- 

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

[Yury Norov]

On Thu, Sep 22, 2022 at 5:38 PM Phil Auld <pauld@redhat.com> wrote:
>
> Hi Andy,
>
> On Thu, Sep 22, 2022 at 10:49:54PM +0300 Andy Shevchenko wrote:
> > Currently the approximation is used which wastes the more memory
> > the more CPUs are present on the system. Proposed change calculates
> > the exact maximum needed in the worst case:
> >
> >   NR_CPUS     old             new
> >   -------     ---             ---
> >   1 .. 1170   4096            4096
> >   1171 .. 1860        4098 .. 6510    4096
> >   ...         ...             ...
> >   2*4096      28672           19925
> >   4*4096      57344           43597
> >   8*4096      114688          92749
> >   16*4096     229376          191053
> >   32*4096     458752          403197
> >   64*4096     917504          861949
> >   128*4096    1835008         1779453
> >   256*4096    3670016         3670016
> >
> > Under the hood the reccurent formula is being used:
> >   (5 - 0) * 2 +
> >     (50 - 5) * 3 +
> >       (500 - 50) * 4 +
> >         (5000 - 500) * 5 +
> >           ...
> >             (X[i] - X[i-1]) * i
> >
> > which allows to count the exact maximum length in the worst case,
> > i.e. when each second CPU is being listed. For backward compatibility
> > for more than 1170 and less than 1861 CPUs the page size is preserved.
> >
> > For less than 1171 and more than 1 million CPUs the old is being used.
>
> The memory is not really wasted since it's probably temporary in userspace
> and in the kernel it _is_ temporary and is only the length of the kasprintf
> string, which is most of the time much less.
>
> But that said, it is more accurate than the previous estimate.
>
> I was wondering if you were going to try to come up with a suitable
> compile time macro :)
>
> I tested 2, 8192 and 16k since the kernel does not want to build for other
> reasons with NR_CPUS at 32k.
>
> Reviewed-by: Phil Auld <pauld@redhat.com>
> Tested-by: Phil Auld <pauld@redhat.com>

By the way, why don't we use nr_cpu_ids? It's set at boot-time, or even
at compile-time in some cases and never changed at runtime.

nr_cpu_ids is set very early, when ACPI tables are parsed. I don't think
it's possible for a userspace to observe it uninitialized. Am I wrong?

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

[Greg Kroah-Hartman]

On Thu, Sep 22, 2022 at 01:41:40PM -0700, Yury Norov wrote:
>  + Petr Štetiar <ynezz@true.cz>,
>  + Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> 
> On Thu, Sep 22, 2022 at 10:49:54PM +0300, Andy Shevchenko wrote:
> > Currently the approximation is used which wastes the more memory
> > the more CPUs are present on the system. Proposed change calculates
> > the exact maximum needed in the worst case:
> > 
> >   NR_CPUS	old		new
> >   -------	---		---
> >   1 .. 1170	4096		4096
> >   1171 .. 1860	4098 ..	6510	4096
> >   ...		...		...
> >   2*4096	28672		19925
> >   4*4096	57344		43597
> >   8*4096	114688		92749
> >   16*4096	229376		191053
> >   32*4096	458752		403197
> >   64*4096	917504		861949
> >   128*4096	1835008		1779453
> >   256*4096	3670016		3670016
> > 
> > Under the hood the reccurent formula is being used:
> >   (5 - 0) * 2 +
> >     (50 - 5) * 3 +
> >       (500 - 50) * 4 +
> >         (5000 - 500) * 5 +
> >           ...
> >             (X[i] - X[i-1]) * i
> > 
> > which allows to count the exact maximum length in the worst case,
> > i.e. when each second CPU is being listed. For backward compatibility
> > for more than 1170 and less than 1861 CPUs the page size is preserved.
> > 
> > For less than 1171 and more than 1 million CPUs the old is being used.
> 
> 1861
> 
> > 
> > Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> > ---
> > v2: described better the advantage for 1171..1860 CPUs cases
> >  include/linux/cpumask.h | 48 +++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 48 insertions(+)
> > 
> > diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> > index 1b442fb2001f..12cf0905ca74 100644
> > --- a/include/linux/cpumask.h
> > +++ b/include/linux/cpumask.h
> > @@ -1122,6 +1122,21 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> >   *
> >   * for cpumap NR_CPUS * 9/32 - 1 should be an exact length.
> >   *
> > + * for cpulist the reccurent formula is being used:
> > + *   (5 - 0) * 2 +
> > + *     (50 - 5) * 3 +
> > + *       (500 - 50) * 4 +
> > + *         (5000 - 500) * 5 +
> > + *           ...
> > + *             (X[i] - X[i-1]) * i
> > + *
> > + * which allows to count the exact maximum length in the worst case,
> > + * i.e. when each second CPU is being listed. For backward compatibility
> > + * for more than 1170 and less than 1861 CPUs the page size is preserved.
> > + *
> > + * For less than 1171 and more than 1 million CPUs the old is being used
> > + * as described below:
> > + *
> >   * For cpulist 7 is (ceil(log10(NR_CPUS)) + 1) allowing for NR_CPUS to be up
> >   * to 2 orders of magnitude larger than 8192. And then we divide by 2 to
> >   * cover a worst-case of every other cpu being on one of two nodes for a
> > @@ -1132,6 +1147,39 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> >   */
> >  #define CPUMAP_FILE_MAX_BYTES  (((NR_CPUS * 9)/32 > PAGE_SIZE) \
> >  					? (NR_CPUS * 9)/32 - 1 : PAGE_SIZE)
> > +
> > +#define __CPULIST_FOR_10(x)		(((x + 1) / 2 - 0)     * 2)
> > +#define __CPULIST_FOR_100(x)		(((x + 1) / 2 - 5)     * 3)
> > +#define __CPULIST_FOR_1000(x)		(((x + 1) / 2 - 50)    * 4)
> > +#define __CPULIST_FOR_10000(x)		(((x + 1) / 2 - 500)   * 5)
> > +#define __CPULIST_FOR_100000(x)		(((x + 1) / 2 - 5000)  * 6)
> > +#define __CPULIST_FOR_1000000(x)	(((x + 1) / 2 - 50000) * 7)
> 
> The defs below will be nicer if you make it like this:
> 
>   #define __CPULIST_FOR_10(x)  (((x + 1) / 2 - 0)     * 2)
>   #define __CPULIST_FOR_100(x) __CPULIST_FOR_10(10) + (((x + 1) / 2 - 5) * 3)
>   #define __CPULIST_FOR_1000(x)	__CPULIST_FOR_100(100) + (((x + 1) / 2 - 50) * 4)
>   ...
> 
> 
> 
> > +#if NR_CPUS < 1861
> > +#define CPULIST_FILE_MAX_BYTES	PAGE_SIZE
> 
> The comment says:
>   for more than 1170 and less than 1861 CPUs the page size is preserved.
> 
> Which doesn't look correct. Looks like it should be:
>   for less than 1861 CPUs the page size is preserved.
> 
> Or I miss something?
> 
> > +#elif NR_CPUS < 10000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(NR_CPUS))
> > +#elif NR_CPUS < 100000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(10000) +		\
> > +	  __CPULIST_FOR_100000(NR_CPUS))
> > +#elif NR_CPUS < 1000000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(10000) +		\
> > +	  __CPULIST_FOR_100000(100000) +	\
> > +	  __CPULIST_FOR_1000000(NR_CPUS))
> > +#else
> >  #define CPULIST_FILE_MAX_BYTES  (((NR_CPUS * 7)/2 > PAGE_SIZE) ? (NR_CPUS * 7)/2 : PAGE_SIZE)
> > +#endif
> >  
> >  #endif /* __LINUX_CPUMASK_H */
> > -- 
> > 2.35.1
> 
> I'm OK to take this in replace for Phil's version, but the commit that
> introduces CPULIST_FILE_MAX_BYTES is already in mainline: 7ee951acd31a8
> ("drivers/base: fix userspace break from using bin_attributes for cpumap
> and cpulist"). Can you rebase it on top of v6.0-rc6?
> 
> Greg, since Andy's version is more precise, I'd like to send a pull
> request with it in -rc7. Can you drop Phil's patch so I'll go with
> this one?

Let me get this fix to Linus now for 6.0-final as it is hitting people
right now.  Making it "cleaner" after that is fine to go through your
tree as that's less of an issue, right?

thanks,

greg k-h

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

[Andy Shevchenko]

On Thu, Sep 22, 2022 at 01:41:40PM -0700, Yury Norov wrote:
>  + Petr Štetiar <ynezz@true.cz>,
>  + Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> 
> On Thu, Sep 22, 2022 at 10:49:54PM +0300, Andy Shevchenko wrote:
> > Currently the approximation is used which wastes the more memory
> > the more CPUs are present on the system. Proposed change calculates
> > the exact maximum needed in the worst case:
> > 
> >   NR_CPUS	old		new
> >   -------	---		---
> >   1 .. 1170	4096		4096
> >   1171 .. 1860	4098 ..	6510	4096
> >   ...		...		...
> >   2*4096	28672		19925
> >   4*4096	57344		43597
> >   8*4096	114688		92749
> >   16*4096	229376		191053
> >   32*4096	458752		403197
> >   64*4096	917504		861949
> >   128*4096	1835008		1779453
> >   256*4096	3670016		3670016
> > 
> > Under the hood the reccurent formula is being used:
> >   (5 - 0) * 2 +
> >     (50 - 5) * 3 +
> >       (500 - 50) * 4 +
> >         (5000 - 500) * 5 +
> >           ...
> >             (X[i] - X[i-1]) * i
> > 
> > which allows to count the exact maximum length in the worst case,
> > i.e. when each second CPU is being listed. For backward compatibility
> > for more than 1170 and less than 1861 CPUs the page size is preserved.
> > 
> > For less than 1171 and more than 1 million CPUs the old is being used.
> 
> 1861

No, this is correct for the PAGE_SIZE == 4096.

> > Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> > ---
> > v2: described better the advantage for 1171..1860 CPUs cases
> >  include/linux/cpumask.h | 48 +++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 48 insertions(+)
> > 
> > diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> > index 1b442fb2001f..12cf0905ca74 100644
> > --- a/include/linux/cpumask.h
> > +++ b/include/linux/cpumask.h
> > @@ -1122,6 +1122,21 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> >   *
> >   * for cpumap NR_CPUS * 9/32 - 1 should be an exact length.
> >   *
> > + * for cpulist the reccurent formula is being used:
> > + *   (5 - 0) * 2 +
> > + *     (50 - 5) * 3 +
> > + *       (500 - 50) * 4 +
> > + *         (5000 - 500) * 5 +
> > + *           ...
> > + *             (X[i] - X[i-1]) * i
> > + *
> > + * which allows to count the exact maximum length in the worst case,
> > + * i.e. when each second CPU is being listed. For backward compatibility
> > + * for more than 1170 and less than 1861 CPUs the page size is preserved.
> > + *
> > + * For less than 1171 and more than 1 million CPUs the old is being used
> > + * as described below:
> > + *
> >   * For cpulist 7 is (ceil(log10(NR_CPUS)) + 1) allowing for NR_CPUS to be up
> >   * to 2 orders of magnitude larger than 8192. And then we divide by 2 to
> >   * cover a worst-case of every other cpu being on one of two nodes for a
> > @@ -1132,6 +1147,39 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> >   */
> >  #define CPUMAP_FILE_MAX_BYTES  (((NR_CPUS * 9)/32 > PAGE_SIZE) \
> >  					? (NR_CPUS * 9)/32 - 1 : PAGE_SIZE)
> > +
> > +#define __CPULIST_FOR_10(x)		(((x + 1) / 2 - 0)     * 2)
> > +#define __CPULIST_FOR_100(x)		(((x + 1) / 2 - 5)     * 3)
> > +#define __CPULIST_FOR_1000(x)		(((x + 1) / 2 - 50)    * 4)
> > +#define __CPULIST_FOR_10000(x)		(((x + 1) / 2 - 500)   * 5)
> > +#define __CPULIST_FOR_100000(x)		(((x + 1) / 2 - 5000)  * 6)
> > +#define __CPULIST_FOR_1000000(x)	(((x + 1) / 2 - 50000) * 7)
> 
> The defs below will be nicer if you make it like this:
> 
>   #define __CPULIST_FOR_10(x)  (((x + 1) / 2 - 0)     * 2)
>   #define __CPULIST_FOR_100(x) __CPULIST_FOR_10(10) + (((x + 1) / 2 - 5) * 3)
>   #define __CPULIST_FOR_1000(x)	__CPULIST_FOR_100(100) + (((x + 1) / 2 - 50) * 4)
>   ...

Not big deal, but I found my way more readable.

> > +#if NR_CPUS < 1861
> > +#define CPULIST_FILE_MAX_BYTES	PAGE_SIZE
> 
> The comment says:
>   for more than 1170 and less than 1861 CPUs the page size is preserved.
> 
> Which doesn't look correct. Looks like it should be:
>   for less than 1861 CPUs the page size is preserved.
> 
> Or I miss something?

Yes, you missed that the current formula gives an overhead already at 1171,
while it's room up to 1860. All these numbers are for PAGE_SIZE == 4096. In any
case, I was thinking more about this and I need to revert to my (locally)
initial approach to count the real size and then do like the old formula does,
i.e. max(PAGE_SIZE, real size) at the end.

> > +#elif NR_CPUS < 10000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(NR_CPUS))
> > +#elif NR_CPUS < 100000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(10000) +		\
> > +	  __CPULIST_FOR_100000(NR_CPUS))
> > +#elif NR_CPUS < 1000000
> > +#define CPULIST_FILE_MAX_BYTES			\
> > +	 (__CPULIST_FOR_10(10) +		\
> > +	  __CPULIST_FOR_100(100) +		\
> > +	  __CPULIST_FOR_1000(1000) +		\
> > +	  __CPULIST_FOR_10000(10000) +		\
> > +	  __CPULIST_FOR_100000(100000) +	\
> > +	  __CPULIST_FOR_1000000(NR_CPUS))
> > +#else
> >  #define CPULIST_FILE_MAX_BYTES  (((NR_CPUS * 7)/2 > PAGE_SIZE) ? (NR_CPUS * 7)/2 : PAGE_SIZE)
> > +#endif
> >  
> >  #endif /* __LINUX_CPUMASK_H */

> I'm OK to take this in replace for Phil's version, but the commit that
> introduces CPULIST_FILE_MAX_BYTES is already in mainline: 7ee951acd31a8
> ("drivers/base: fix userspace break from using bin_attributes for cpumap
> and cpulist"). Can you rebase it on top of v6.0-rc6?
> 
> Greg, since Andy's version is more precise, I'd like to send a pull
> request with it in -rc7. Can you drop Phil's patch so I'll go with
> this one?

If it's already in mainline, then there is no way we can drop it. Also note,
everything which is in -next branches are usually not for rebase (and IIRC Greg
never rebases his trees). Hence, my patch is for Linux Next, i.e. v6.1-rc1.

In any case, please wait for v3.
I'll Cc it to the people you mentioned above, if you think it's a right thing
to do. (The Cc list is based on MAINTAINERS + author of the previous patch)

-- 
With Best Regards,
Andy Shevchenko

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

[Andy Shevchenko]

On Thu, Sep 22, 2022 at 08:38:06PM -0400, Phil Auld wrote:
> On Thu, Sep 22, 2022 at 10:49:54PM +0300 Andy Shevchenko wrote:
> > Currently the approximation is used which wastes the more memory
> > the more CPUs are present on the system. Proposed change calculates
> > the exact maximum needed in the worst case:
> > 
> >   NR_CPUS	old		new
> >   -------	---		---
> >   1 .. 1170	4096		4096
> >   1171 .. 1860	4098 ..	6510	4096
> >   ...		...		...
> >   2*4096	28672		19925
> >   4*4096	57344		43597
> >   8*4096	114688		92749
> >   16*4096	229376		191053
> >   32*4096	458752		403197
> >   64*4096	917504		861949
> >   128*4096	1835008		1779453
> >   256*4096	3670016		3670016
> > 
> > Under the hood the reccurent formula is being used:
> >   (5 - 0) * 2 +
> >     (50 - 5) * 3 +
> >       (500 - 50) * 4 +
> >         (5000 - 500) * 5 +
> >           ...
> >             (X[i] - X[i-1]) * i
> > 
> > which allows to count the exact maximum length in the worst case,
> > i.e. when each second CPU is being listed. For backward compatibility
> > for more than 1170 and less than 1861 CPUs the page size is preserved.
> > 
> > For less than 1171 and more than 1 million CPUs the old is being used.
> 
> The memory is not really wasted since it's probably temporary in userspace
> and in the kernel it _is_ temporary and is only the length of the kasprintf
> string, which is most of the time much less.
> 
> But that said, it is more accurate than the previous estimate.
> 
> I was wondering if you were going to try to come up with a suitable
> compile time macro :)
> 
> I tested 2, 8192 and 16k since the kernel does not want to build for other
> reasons with NR_CPUS at 32k.
> 
> Reviewed-by: Phil Auld <pauld@redhat.com>
> Tested-by: Phil Auld <pauld@redhat.com>

Thank you!

-- 
With Best Regards,
Andy Shevchenko

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

[Phil Auld]

On Thu, Sep 22, 2022 at 06:45:27PM -0700 Yury Norov wrote:
> On Thu, Sep 22, 2022 at 5:38 PM Phil Auld <pauld@redhat.com> wrote:
> >
> > Hi Andy,
> >
> > On Thu, Sep 22, 2022 at 10:49:54PM +0300 Andy Shevchenko wrote:
> > > Currently the approximation is used which wastes the more memory
> > > the more CPUs are present on the system. Proposed change calculates
> > > the exact maximum needed in the worst case:
> > >
> > >   NR_CPUS     old             new
> > >   -------     ---             ---
> > >   1 .. 1170   4096            4096
> > >   1171 .. 1860        4098 .. 6510    4096
> > >   ...         ...             ...
> > >   2*4096      28672           19925
> > >   4*4096      57344           43597
> > >   8*4096      114688          92749
> > >   16*4096     229376          191053
> > >   32*4096     458752          403197
> > >   64*4096     917504          861949
> > >   128*4096    1835008         1779453
> > >   256*4096    3670016         3670016
> > >
> > > Under the hood the reccurent formula is being used:
> > >   (5 - 0) * 2 +
> > >     (50 - 5) * 3 +
> > >       (500 - 50) * 4 +
> > >         (5000 - 500) * 5 +
> > >           ...
> > >             (X[i] - X[i-1]) * i
> > >
> > > which allows to count the exact maximum length in the worst case,
> > > i.e. when each second CPU is being listed. For backward compatibility
> > > for more than 1170 and less than 1861 CPUs the page size is preserved.
> > >
> > > For less than 1171 and more than 1 million CPUs the old is being used.
> >
> > The memory is not really wasted since it's probably temporary in userspace
> > and in the kernel it _is_ temporary and is only the length of the kasprintf
> > string, which is most of the time much less.
> >
> > But that said, it is more accurate than the previous estimate.
> >
> > I was wondering if you were going to try to come up with a suitable
> > compile time macro :)
> >
> > I tested 2, 8192 and 16k since the kernel does not want to build for other
> > reasons with NR_CPUS at 32k.
> >
> > Reviewed-by: Phil Auld <pauld@redhat.com>
> > Tested-by: Phil Auld <pauld@redhat.com>
> 
> By the way, why don't we use nr_cpu_ids? It's set at boot-time, or even
> at compile-time in some cases and never changed at runtime.
> 
> nr_cpu_ids is set very early, when ACPI tables are parsed. I don't think
> it's possible for a userspace to observe it uninitialized. Am I wrong?
> 

I very much wanted it to be compile time so there was no overhead.

Is there a good place to init these bin_attrs at boottime, anyway?
I didn't dig into it farther, but it looks like the size is set
when declared. I suppose we could adjust it at the first read if
there was a way to do that. It's sort of all abstracted away to
common code though.

The fact that the values are larger than actually needed doesn't really
cause any harm.  In the kernel no extra memory is allocated since it uses
the size of the sprintf of the actual data.  And it's only allocated
while being read.

In userspace it may be a little extra memory while doing a read. But that's
also likely to be just temporary.

And if you have NR_CPUS 10000 you probably have a lot of wasted percpu
space anyway...


Cheers,
Phil

-- 

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

[Rasmus Villemoes]

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.

Rasmus

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

[Andy Shevchenko]

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

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

[Yury Norov]

On Fri, Sep 23, 2022 at 08:30:45AM +0200, Greg Kroah-Hartman wrote:
> On Thu, Sep 22, 2022 at 01:41:40PM -0700, Yury Norov wrote:
> >  + Petr Štetiar <ynezz@true.cz>,
> >  + Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> > 
> > On Thu, Sep 22, 2022 at 10:49:54PM +0300, Andy Shevchenko wrote:
> > > Currently the approximation is used which wastes the more memory
> > > the more CPUs are present on the system. Proposed change calculates
> > > the exact maximum needed in the worst case:
> > > 
> > >   NR_CPUS	old		new
> > >   -------	---		---
> > >   1 .. 1170	4096		4096
> > >   1171 .. 1860	4098 ..	6510	4096
> > >   ...		...		...
> > >   2*4096	28672		19925
> > >   4*4096	57344		43597
> > >   8*4096	114688		92749
> > >   16*4096	229376		191053
> > >   32*4096	458752		403197
> > >   64*4096	917504		861949
> > >   128*4096	1835008		1779453
> > >   256*4096	3670016		3670016
> > > 
> > > Under the hood the reccurent formula is being used:
> > >   (5 - 0) * 2 +
> > >     (50 - 5) * 3 +
> > >       (500 - 50) * 4 +
> > >         (5000 - 500) * 5 +
> > >           ...
> > >             (X[i] - X[i-1]) * i
> > > 
> > > which allows to count the exact maximum length in the worst case,
> > > i.e. when each second CPU is being listed. For backward compatibility
> > > for more than 1170 and less than 1861 CPUs the page size is preserved.
> > > 
> > > For less than 1171 and more than 1 million CPUs the old is being used.
> > 
> > 1861
> > 
> > > 
> > > Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> > > ---
> > > v2: described better the advantage for 1171..1860 CPUs cases
> > >  include/linux/cpumask.h | 48 +++++++++++++++++++++++++++++++++++++++++
> > >  1 file changed, 48 insertions(+)
> > > 
> > > diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> > > index 1b442fb2001f..12cf0905ca74 100644
> > > --- a/include/linux/cpumask.h
> > > +++ b/include/linux/cpumask.h
> > > @@ -1122,6 +1122,21 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> > >   *
> > >   * for cpumap NR_CPUS * 9/32 - 1 should be an exact length.
> > >   *
> > > + * for cpulist the reccurent formula is being used:
> > > + *   (5 - 0) * 2 +
> > > + *     (50 - 5) * 3 +
> > > + *       (500 - 50) * 4 +
> > > + *         (5000 - 500) * 5 +
> > > + *           ...
> > > + *             (X[i] - X[i-1]) * i
> > > + *
> > > + * which allows to count the exact maximum length in the worst case,
> > > + * i.e. when each second CPU is being listed. For backward compatibility
> > > + * for more than 1170 and less than 1861 CPUs the page size is preserved.
> > > + *
> > > + * For less than 1171 and more than 1 million CPUs the old is being used
> > > + * as described below:
> > > + *
> > >   * For cpulist 7 is (ceil(log10(NR_CPUS)) + 1) allowing for NR_CPUS to be up
> > >   * to 2 orders of magnitude larger than 8192. And then we divide by 2 to
> > >   * cover a worst-case of every other cpu being on one of two nodes for a
> > > @@ -1132,6 +1147,39 @@ cpumap_print_list_to_buf(char *buf, const struct cpumask *mask,
> > >   */
> > >  #define CPUMAP_FILE_MAX_BYTES  (((NR_CPUS * 9)/32 > PAGE_SIZE) \
> > >  					? (NR_CPUS * 9)/32 - 1 : PAGE_SIZE)
> > > +
> > > +#define __CPULIST_FOR_10(x)		(((x + 1) / 2 - 0)     * 2)
> > > +#define __CPULIST_FOR_100(x)		(((x + 1) / 2 - 5)     * 3)
> > > +#define __CPULIST_FOR_1000(x)		(((x + 1) / 2 - 50)    * 4)
> > > +#define __CPULIST_FOR_10000(x)		(((x + 1) / 2 - 500)   * 5)
> > > +#define __CPULIST_FOR_100000(x)		(((x + 1) / 2 - 5000)  * 6)
> > > +#define __CPULIST_FOR_1000000(x)	(((x + 1) / 2 - 50000) * 7)
> > 
> > The defs below will be nicer if you make it like this:
> > 
> >   #define __CPULIST_FOR_10(x)  (((x + 1) / 2 - 0)     * 2)
> >   #define __CPULIST_FOR_100(x) __CPULIST_FOR_10(10) + (((x + 1) / 2 - 5) * 3)
> >   #define __CPULIST_FOR_1000(x)	__CPULIST_FOR_100(100) + (((x + 1) / 2 - 50) * 4)
> >   ...
> > 
> > 
> > 
> > > +#if NR_CPUS < 1861
> > > +#define CPULIST_FILE_MAX_BYTES	PAGE_SIZE
> > 
> > The comment says:
> >   for more than 1170 and less than 1861 CPUs the page size is preserved.
> > 
> > Which doesn't look correct. Looks like it should be:
> >   for less than 1861 CPUs the page size is preserved.
> > 
> > Or I miss something?
> > 
> > > +#elif NR_CPUS < 10000
> > > +#define CPULIST_FILE_MAX_BYTES			\
> > > +	 (__CPULIST_FOR_10(10) +		\
> > > +	  __CPULIST_FOR_100(100) +		\
> > > +	  __CPULIST_FOR_1000(1000) +		\
> > > +	  __CPULIST_FOR_10000(NR_CPUS))
> > > +#elif NR_CPUS < 100000
> > > +#define CPULIST_FILE_MAX_BYTES			\
> > > +	 (__CPULIST_FOR_10(10) +		\
> > > +	  __CPULIST_FOR_100(100) +		\
> > > +	  __CPULIST_FOR_1000(1000) +		\
> > > +	  __CPULIST_FOR_10000(10000) +		\
> > > +	  __CPULIST_FOR_100000(NR_CPUS))
> > > +#elif NR_CPUS < 1000000
> > > +#define CPULIST_FILE_MAX_BYTES			\
> > > +	 (__CPULIST_FOR_10(10) +		\
> > > +	  __CPULIST_FOR_100(100) +		\
> > > +	  __CPULIST_FOR_1000(1000) +		\
> > > +	  __CPULIST_FOR_10000(10000) +		\
> > > +	  __CPULIST_FOR_100000(100000) +	\
> > > +	  __CPULIST_FOR_1000000(NR_CPUS))
> > > +#else
> > >  #define CPULIST_FILE_MAX_BYTES  (((NR_CPUS * 7)/2 > PAGE_SIZE) ? (NR_CPUS * 7)/2 : PAGE_SIZE)
> > > +#endif
> > >  
> > >  #endif /* __LINUX_CPUMASK_H */
> > > -- 
> > > 2.35.1
> > 
> > I'm OK to take this in replace for Phil's version, but the commit that
> > introduces CPULIST_FILE_MAX_BYTES is already in mainline: 7ee951acd31a8
> > ("drivers/base: fix userspace break from using bin_attributes for cpumap
> > and cpulist"). Can you rebase it on top of v6.0-rc6?
> > 
> > Greg, since Andy's version is more precise, I'd like to send a pull
> > request with it in -rc7. Can you drop Phil's patch so I'll go with
> > this one?
> 
> Let me get this fix to Linus now for 6.0-final as it is hitting people
> right now.  Making it "cleaner" after that is fine to go through your
> tree as that's less of an issue, right?

OK