[PATCH v1 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 .. 1860	4096		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 less than 1861 and
more than 1 million CPUs the old is being used.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>
---
 include/linux/cpumask.h | 45 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 1b442fb2001f..7c6416fa038d 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -1122,6 +1122,18 @@ 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 less than 1861 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 +1144,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