The uninitialized state 0 involves the danger of reaching that state in
normal operation. Since the weight_rcp value needs to be bigger than one
(otherwise no averaging takes place), the final shifting in add ensures,
that the internal state never reach ULONG_MAX. Therefore use this value
to signal, that the ewma has no initial value.
The add function needs to check, that val is not to big, otherwise the new
value can overflow the internal state, which results in unexpected outputs.
Move the compile time checks into a separate macro, as they are used
multiple times and noise up the functions.
Signed-off-by: Benjamin Beichler <[email protected]>
---
include/linux/average.h | 82 ++++++++++++++++++++++-------------------
1 file changed, 45 insertions(+), 37 deletions(-)
diff --git a/include/linux/average.h b/include/linux/average.h
index a1a8f09631ce..4fb170ed0225 100644
--- a/include/linux/average.h
+++ b/include/linux/average.h
@@ -22,50 +22,58 @@
* The third argument, the weight reciprocal, determines how the
* new values will be weighed vs. the old state, new values will
* get weight 1/weight_rcp and old values 1-1/weight_rcp. Note
- * that this parameter must be a power of two for efficiency.
+ * that this parameter must be a power of two for efficiency. A
+ * weight of 1 is not allowed, because of the internal init function,
+ * but nevertheless it makes no sense, since it means no averaging at all.
*/
-#define DECLARE_EWMA(name, _precision, _weight_rcp) \
- struct ewma_##name { \
- unsigned long internal; \
- }; \
- static inline void ewma_##name##_init(struct ewma_##name *e) \
- { \
+#define EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp) \
+ do { \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
- /* \
- * Even if you want to feed it just 0/1 you should have \
- * some bits for the non-fractional part... \
- */ \
- BUILD_BUG_ON((_precision) > 30); \
- BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
- e->internal = 0; \
- } \
- static inline unsigned long \
- ewma_##name##_read(struct ewma_##name *e) \
- { \
- BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
- BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
- BUILD_BUG_ON((_precision) > 30); \
- BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
- return e->internal >> (_precision); \
- } \
- static inline void ewma_##name##_add(struct ewma_##name *e, \
- unsigned long val) \
- { \
- unsigned long internal = READ_ONCE(e->internal); \
- unsigned long weight_rcp = ilog2(_weight_rcp); \
- unsigned long precision = _precision; \
\
- BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
- BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
- \
- WRITE_ONCE(e->internal, internal ? \
- (((internal << weight_rcp) - internal) + \
- (val << precision)) >> weight_rcp : \
- (val << precision)); \
+ BUILD_BUG_ON(_weight_rcp <= 1); \
+ } while (0)
+
+#define DECLARE_EWMA(name, _precision, _weight_rcp) \
+ struct ewma_##name { \
+ unsigned long internal; \
+ }; \
+ static inline void ewma_##name##_init(struct ewma_##name *e) \
+ { \
+ EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp); \
+ e->internal = ULONG_MAX; \
+ } \
+ static inline void ewma_##name##_init_val(struct ewma_##name *e \
+ unsigned long val) \
+ { \
+ EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp); \
+ e->internal = val; \
+ } \
+ static inline unsigned long \
+ ewma_##name##_read(struct ewma_##name *e) \
+ { \
+ EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp); \
+ return unlikely(e->internal == ULONG_MAX) ? \
+ 0 : e->internal >> (_precision); \
+ } \
+ static inline void ewma_##name##_add(struct ewma_##name *e, \
+ unsigned long val) \
+ { \
+ unsigned long internal = READ_ONCE(e->internal); \
+ unsigned long weight_rcp = ilog2(_weight_rcp); \
+ unsigned long precision = _precision; \
+ unsigned long max_val = ULONG_MAX >> (precision + weight_rcp); \
+ \
+ EWMA_BUILD_TIME_CHECKS(_precision, _weight_rcp); \
+ WARN_ONCE(val > max_val, "Value (%lu) is too large for ewma_##name##_add, this will result in unexpected values of the ewma filter. Max valid value is %lu",\
+ val, max_val); \
+ WRITE_ONCE(e->internal, unlikely(internal != ULONG_MAX) ? \
+ (((internal << weight_rcp) - internal) + \
+ (val << precision)) >> weight_rcp : \
+ (val << precision)); \
}
#endif /* _LINUX_AVERAGE_H */
--
2.25.1
On Mon, 2023-04-24 at 21:04 +0000, Benjamin Beichler wrote:
> The uninitialized state 0 involves the danger of reaching that state in
> normal operation. Since the weight_rcp value needs to be bigger than one
> (otherwise no averaging takes place), the final shifting in add ensures,
> that the internal state never reach ULONG_MAX. Therefore use this value
> to signal, that the ewma has no initial value.
>
> The add function needs to check, that val is not to big, otherwise the new
> value can overflow the internal state, which results in unexpected outputs.
This seems nice to me, FWIW.
> Move the compile time checks into a separate macro, as they are used
> multiple times and noise up the functions.
Why do we even have those multiple times? Should be enough to have them
once, since we always compile the static inline functions?
johannes
Am 25.04.2023 um 20:18 schrieb Johannes Berg:
> ________________________________
> Achtung! Externe E-Mail: Klicken Sie erst dann auf Links und Anhänge, nachdem Sie die Vertrauenswürdigkeit der Absenderadresse geprüft haben.
> ________________________________
>
> On Mon, 2023-04-24 at 21:04 +0000, Benjamin Beichler wrote:
>> The uninitialized state 0 involves the danger of reaching that state in
>> normal operation. Since the weight_rcp value needs to be bigger than one
>> (otherwise no averaging takes place), the final shifting in add ensures,
>> that the internal state never reach ULONG_MAX. Therefore use this value
>> to signal, that the ewma has no initial value.
>>
>> The add function needs to check, that val is not to big, otherwise the new
>> value can overflow the internal state, which results in unexpected outputs.
> This seems nice to me, FWIW.
Okay. I would split up the patch into sensible parts and send it later.
You are also fine with the extra init function with explicit init value?
Of course this one also needs the check, that it really fits into the
internal state :-D
>
>> Move the compile time checks into a separate macro, as they are used
>> multiple times and noise up the functions.
> Why do we even have those multiple times? Should be enough to have them
> once, since we always compile the static inline functions?
Good question ... my assumption was, that the build-bug macro may not
work, if the function is unused and maybe optimized away, but I'm not
that familiar with those details. I'm more in favor with the
static_asserts of C++, which have defined semantics. :-D
It would be nice to put the check into the struct, as some zero size bad
member, but I found no example in the kernel, so maybe this is not
easily doable.
One may argue, that we only put it in init and if the users do not use
init, we call it shit-in-shit-out, but I'm not really in favor of that.
Anyone with more experiences on build time asserts in the kernel?
Benjamin
Am 26.04.2023 um 08:19 schrieb Benjamin Beichler:
> Am 25.04.2023 um 20:18 schrieb Johannes Berg:
>> ________________________________
>> Achtung! Externe E-Mail: Klicken Sie erst dann auf Links und
>> Anhänge, nachdem Sie die Vertrauenswürdigkeit der Absenderadresse
>> geprüft haben.
>> ________________________________
>>
>> On Mon, 2023-04-24 at 21:04 +0000, Benjamin Beichler wrote:
>>> The uninitialized state 0 involves the danger of reaching that state in
>>> normal operation. Since the weight_rcp value needs to be bigger than
>>> one
>>> (otherwise no averaging takes place), the final shifting in add
>>> ensures,
>>> that the internal state never reach ULONG_MAX. Therefore use this value
>>> to signal, that the ewma has no initial value.
>>>
>>> The add function needs to check, that val is not to big, otherwise
>>> the new
>>> value can overflow the internal state, which results in unexpected
>>> outputs.
>> This seems nice to me, FWIW.
> Okay. I would split up the patch into sensible parts and send it
> later. You are also fine with the extra init function with explicit
> init value? Of course this one also needs the check, that it really
> fits into the internal state :-D
>>
>>> Move the compile time checks into a separate macro, as they are used
>>> multiple times and noise up the functions.
>> Why do we even have those multiple times? Should be enough to have them
>> once, since we always compile the static inline functions?
>
> Good question ... my assumption was, that the build-bug macro may not
> work, if the function is unused and maybe optimized away, but I'm not
> that familiar with those details. I'm more in favor with the
> static_asserts of C++, which have defined semantics. :-D
>
> It would be nice to put the check into the struct, as some zero size
> bad member, but I found no example in the kernel, so maybe this is not
> easily doable.
>
> One may argue, that we only put it in init and if the users do not use
> init, we call it shit-in-shit-out, but I'm not really in favor of that.
>
> Anyone with more experiences on build time asserts in the kernel?
>
>
I just checked out of curiosity the kernel for static_assert, and voilà
it already contains it as a wrapper to the C11 _Static_assert, which
should work better than BUILD_BUG. I will transform it and remove the
multiple insertions.
Benjamin
--
M.Sc. Benjamin Beichler
Universität Rostock, Fakultät für Informatik und Elektrotechnik
Institut für Angewandte Mikroelektronik und Datentechnik
University of Rostock, Department of CS and EE
Institute of Applied Microelectronics and CE
Albert-Einstein-Str. 26
18059 Rostock
Deutschland/Germany
phone: +49 (0) 381 498 - 7278
email: [email protected]
www: http://www.imd.uni-rostock.de/