From 712c9eacded5b717cbb88db1df5e430342012269 Mon Sep 17 00:00:00 2001 From: Linus Torvalds 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 --- 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 + #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