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 <[email protected]>
---
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
+ Petr Štetiar <[email protected]>,
+ Greg Kroah-Hartman <[email protected]>
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 <[email protected]>
> ---
> 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
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 <[email protected]>,
> > + Greg Kroah-Hartman <[email protected]>
> >
> > 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 <[email protected]>
> > > ---
> > > 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
On Thu, Sep 22, 2022 at 01:41:40PM -0700 Yury Norov wrote:
> + Petr Štetiar <[email protected]>,
> + Greg Kroah-Hartman <[email protected]>
>
> 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 <[email protected]>
> > ---
> > 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
>
--
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 <[email protected]>
Tested-by: Phil Auld <[email protected]>
>
> Signed-off-by: Andy Shevchenko <[email protected]>
> ---
> 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
--
On Thu, Sep 22, 2022 at 5:38 PM Phil Auld <[email protected]> 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 <[email protected]>
> Tested-by: Phil Auld <[email protected]>
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?
On Thu, Sep 22, 2022 at 01:41:40PM -0700, Yury Norov wrote:
> + Petr Štetiar <[email protected]>,
> + Greg Kroah-Hartman <[email protected]>
>
> 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 <[email protected]>
> > ---
> > 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
On Thu, Sep 22, 2022 at 01:41:40PM -0700, Yury Norov wrote:
> + Petr Štetiar <[email protected]>,
> + Greg Kroah-Hartman <[email protected]>
>
> 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 <[email protected]>
> > ---
> > 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
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 <[email protected]>
> Tested-by: Phil Auld <[email protected]>
Thank you!
--
With Best Regards,
Andy Shevchenko
On Thu, Sep 22, 2022 at 06:45:27PM -0700 Yury Norov wrote:
> On Thu, Sep 22, 2022 at 5:38 PM Phil Auld <[email protected]> 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 <[email protected]>
> > Tested-by: Phil Auld <[email protected]>
>
> 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
--
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
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 <[email protected]>,
> > + Greg Kroah-Hartman <[email protected]>
> >
> > 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 <[email protected]>
> > > ---
> > > 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
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