Re: [PATCH v4 1/3] math.h: add DIV_ROUND_UP_NO_OVERFLOW

[Linus Torvalds]

On Tue, 24 Oct 2023 at 09:32, Linus Torvalds
<torvalds@xxxxxxxxxxxxxxxxxxxx> wrote:
>
> I would really prefer to just make our regular DIV_ROUND_UP() DTRT.  But:
>
>  - people do use it with complex first arguments (ie function calls
> etc) that we don't want to evaluate twice
>
>  - we can't make it an inline function, because the types aren't fixed
>
>  - we can't even use a statement expression and __auto_type, because
> these things are used in type definitions etc and need to be constant
> expressions

Ok. I have a potential beginning of a solution.

It is unbelievably disgustingly complicated. But it might approach
being correct.

And by that "it might approach being correct" I obviously mean "this
is untested, but builds at least some kernel code".

I'm almost certain it will fail on more complex cases, because I
already found a lot of questionable stuff that was simply hidden by
the old macro just silently doing the C arithmetic type conversions,
and this thing does type handling manually.

I'm hoping that somebody will go "Linus, you're just being
*completely* silly, it's much easier to do XYZ".

            Linus
From 712c9eacded5b717cbb88db1df5e430342012269 Mon Sep 17 00:00:00 2001
From: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
Date: Tue, 24 Oct 2023 12:51:06 -1000
Subject: [PATCH] Introduce (complicated) non-overflowing DIV_ROUND_UP()

Doing a non-overflowing DIV_ROUND_UP() that is usable in all contexts is
actually very nasty.

This is a trial balloon..  The signed cases need more thought.  The best
option would be to disallow them (by not listing them in the _Generic()
rules). But they currently happen, often for bad reasons, ie wireless has

	DIV_ROUND_UP(interval, MSEC_PER_SEC);

and while 'interval' is a proper u32, MSEC_PER_SEC is defined to be
'1000L', so the resulting C arithmetic is done in signed 'long'.

We also have things like

	DIV_ROUND_UP(max_pfn << PAGE_SHIFT, 1UL << TB_SHIFT)

in the kaslr code, where the compiler complains if we ever then use that
'1UL << TB_SHIFT' as an 'int' in the macro expansion, so the
type-specific macros all take the divisor as a 'unsigned long' even if
that might be wider than the target type.

Not-yet-signed-off-by: Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx>
---
 include/linux/div_round_up.h | 104 +++++++++++++++++++++++++++++++++++
 include/uapi/linux/const.h   |   6 +-
 2 files changed, 108 insertions(+), 2 deletions(-)
 create mode 100644 include/linux/div_round_up.h

diff --git a/include/linux/div_round_up.h b/include/linux/div_round_up.h
new file mode 100644
index 000000000000..d7fd319ba5c1
--- /dev/null
+++ b/include/linux/div_round_up.h
@@ -0,0 +1,104 @@
+#ifndef _DIV_ROUND_UP_H
+#define _DIV_ROUND_UP_H
+
+/*
+ * 'DIV_ROUND_UP(n,d)' is annoyingly complicated to do, because while
+ * we've historically evaluated 'd' multiple times using the simple
+ * expression
+ *
+ *    (((n) + (d) - 1) / (d))
+ *
+ * we do _not_ want to evaluate 'n' multiple times. And the simple
+ * expression can overflow to zero for big values of 'n'.
+ *
+ * A non-overflowing version (by David Laight) is
+ *
+ *    (((n) - 1)/(d) + 1)
+ *
+ * but there the 'n-1' will underflow when 'n' is zero, and adding the
+ * conditional for that would then evaluate 'n' twice.
+ *
+ * Avoiding the double evaluation with a statement expression using
+ *
+ *    ({ __auto_type __n = (n) .... })
+ *
+ * like we do with the similarly constrained 'min()' and 'max()'
+ * defines would be trivial, but cannot be used in a top-level
+ * context like a type definition, which is a common case.
+ *
+ * Even using __builtin_choose_expr() and only using the statement
+ * expression for the non-constant case, gcc refuses to even parse
+ * statement expressions outside of function context:
+ *
+ *   error: braced-group within expression allowed only inside a function
+ *
+ * The obvious solution is to use an inline function, but that fails
+ * due to forced type conversion. And widening the types to the maximum
+ * size generates horrific code.
+ *
+ * End result: this horror.
+ */
+
+/*
+ * Split the logic into the constant case (which can be used everywhere)
+ * and the non-constant case (limited to function context, but needs to
+ * parse everywhere).
+ */
+#define __keep_const(cond, expr) \
+	__builtin_choose_expr(__is_constexpr(cond), __const_##expr, __##expr)
+#define __KERNEL_DIV_ROUND_UP(n, d) \
+	__keep_const(n, div_round_up(n,d))
+
+/*
+ * The constant case is trivial, since then we can just re-evaluate to
+ * our hearts content.
+ */
+#define __const_div_round_up(n,d) ((n) != 0 ? ((n)-1)/(d)+1 : 0)
+
+/*
+ * The other cases need to be split by type.
+ *
+ * Signed cases seem badly defined, but do exist. We should
+ * consider removing them from this _Generic(), and fixing any
+ * result 'not compatible with any association' cases.
+ */
+#define __div_round_up(n,d) _Generic((n)+(d),		\
+	unsigned long long: __div_round_up_ull(n,d),	\
+	long long: __div_round_up_ll(n,d),		\
+	unsigned long: __div_round_up_ul(n,d),		\
+	long: __div_round_up_l(n,d),			\
+	unsigned int: __div_round_up_u(n,d),		\
+	int: __div_round_up_i(n,d))
+
+static inline unsigned long long __div_round_up_ull(unsigned long long n, unsigned long d)
+{
+#ifdef CONFIG_32BIT
+	if (!n)
+		return 0
+	do_div(n-1, d);
+	return n+1;
+#else
+	return __const_div_round_up(n,d);
+#endif
+}
+
+static inline unsigned long __div_round_up_ul(unsigned long n, unsigned long d)
+{ return __const_div_round_up(n,d); }
+
+static inline unsigned int __div_round_up_u(unsigned int n, unsigned long d)
+{ return __const_div_round_up(n,(unsigned int)d); }
+
+// Very questionable signed cases...
+static inline long long __div_round_up_ll(long long n, unsigned long d)
+{
+	if (n < 0) return 0;
+	return __div_round_up_ull(n,d);
+}
+
+static inline long __div_round_up_l(long n, unsigned long d)
+{ return __const_div_round_up(n,(long)d); }
+
+static inline int __div_round_up_i(int n, unsigned long d)
+{ return __const_div_round_up(n,(int)d); }
+
+#endif
diff --git a/include/uapi/linux/const.h b/include/uapi/linux/const.h
index a429381e7ca5..8efa1d77c414 100644
--- a/include/uapi/linux/const.h
+++ b/include/uapi/linux/const.h
@@ -20,6 +20,10 @@
 #define __AC(X,Y)	(X##Y)
 #define _AC(X,Y)	__AC(X,Y)
 #define _AT(T,X)	((T)(X))
+
+/* Odd historical placement */
+#include <linux/div_round_up.h>
+
 #endif
 
 #define _UL(x)		(_AC(x, UL))
@@ -31,6 +35,4 @@
 #define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (__typeof__(x))(a) - 1)
 #define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))
 
-#define __KERNEL_DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
-
 #endif /* _UAPI_LINUX_CONST_H */
-- 
2.42.0.398.ga9ecda2788