From 2377799c084d86d22074cd4acd20edc32024d669 Mon Sep 17 00:00:00 2001 From: Johannes Berg Date: Mon, 13 Jul 2015 12:17:25 +0200 Subject: average: provide macro to create static EWMA Having the EWMA parameters stored in the runtime struct imposes memory requirements for the constant values that could just be inlined in the code. This particularly makes sense if there are a lot of such structs, for example in mac80211 in the station table where each station has a number of these in an array, and there can be many stations. Provide a macro DECLARE_EWMA() that declares the necessary struct and inline functions to access it with the parameters hard-coded; using this also means the user no longer needs to 'select AVERAGE' as it's entirely self-contained. In the mac80211 case, on x86-64, this actually slightly *reduces* code size, while also saving 80 bytes of runtime memory per sta. Signed-off-by: Johannes Berg --- include/linux/average.h | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) (limited to 'include/linux/average.h') diff --git a/include/linux/average.h b/include/linux/average.h index c6028fd742c1..60f8226c5652 100644 --- a/include/linux/average.h +++ b/include/linux/average.h @@ -27,4 +27,43 @@ static inline unsigned long ewma_read(const struct ewma *avg) return avg->internal >> avg->factor; } +#define DECLARE_EWMA(name, _factor, _weight) \ + struct ewma_##name { \ + unsigned long internal; \ + }; \ + static inline void ewma_##name##_init(struct ewma_##name *e) \ + { \ + BUILD_BUG_ON(!__builtin_constant_p(_factor)); \ + BUILD_BUG_ON(!__builtin_constant_p(_weight)); \ + BUILD_BUG_ON_NOT_POWER_OF_2(_factor); \ + BUILD_BUG_ON_NOT_POWER_OF_2(_weight); \ + e->internal = 0; \ + } \ + static inline unsigned long \ + ewma_##name##_read(struct ewma_##name *e) \ + { \ + BUILD_BUG_ON(!__builtin_constant_p(_factor)); \ + BUILD_BUG_ON(!__builtin_constant_p(_weight)); \ + BUILD_BUG_ON_NOT_POWER_OF_2(_factor); \ + BUILD_BUG_ON_NOT_POWER_OF_2(_weight); \ + return e->internal >> ilog2(_factor); \ + } \ + static inline void ewma_##name##_add(struct ewma_##name *e, \ + unsigned long val) \ + { \ + unsigned long internal = ACCESS_ONCE(e->internal); \ + unsigned long weight = ilog2(_weight); \ + unsigned long factor = ilog2(_factor); \ + \ + BUILD_BUG_ON(!__builtin_constant_p(_factor)); \ + BUILD_BUG_ON(!__builtin_constant_p(_weight)); \ + BUILD_BUG_ON_NOT_POWER_OF_2(_factor); \ + BUILD_BUG_ON_NOT_POWER_OF_2(_weight); \ + \ + ACCESS_ONCE(e->internal) = internal ? \ + (((internal << weight) - internal) + \ + (val << factor)) >> weight : \ + (val << factor); \ + } + #endif /* _LINUX_AVERAGE_H */ -- cgit v1.2.3-71-gd317 From f4e774f55fe0bb568a0877b2eb9e1b4b5a6f5cbc Mon Sep 17 00:00:00 2001 From: Johannes Berg Date: Wed, 19 Aug 2015 09:46:22 +0200 Subject: average: remove out-of-line implementation Since all users are now converted to the inline implementation, remove the out-of-line implementation entirely. Signed-off-by: Johannes Berg Signed-off-by: David S. Miller --- include/linux/average.h | 24 ------------------- lib/Kconfig | 10 -------- lib/average.c | 64 ------------------------------------------------- 3 files changed, 98 deletions(-) delete mode 100644 lib/average.c (limited to 'include/linux/average.h') diff --git a/include/linux/average.h b/include/linux/average.h index 60f8226c5652..d04aa58280de 100644 --- a/include/linux/average.h +++ b/include/linux/average.h @@ -3,30 +3,6 @@ /* Exponentially weighted moving average (EWMA) */ -/* For more documentation see lib/average.c */ - -struct ewma { - unsigned long internal; - unsigned long factor; - unsigned long weight; -}; - -extern void ewma_init(struct ewma *avg, unsigned long factor, - unsigned long weight); - -extern struct ewma *ewma_add(struct ewma *avg, unsigned long val); - -/** - * ewma_read() - Get average value - * @avg: Average structure - * - * Returns the average value held in @avg. - */ -static inline unsigned long ewma_read(const struct ewma *avg) -{ - return avg->internal >> avg->factor; -} - #define DECLARE_EWMA(name, _factor, _weight) \ struct ewma_##name { \ unsigned long internal; \ diff --git a/lib/Kconfig b/lib/Kconfig index 3a2ef67db6c7..278890dd1049 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -460,16 +460,6 @@ config ARCH_HAS_ATOMIC64_DEC_IF_POSITIVE config LRU_CACHE tristate -config AVERAGE - bool "Averaging functions" - help - This option is provided for the case where no in-kernel-tree - modules require averaging functions, but a module built outside - the kernel tree does. Such modules that use library averaging - functions require Y here. - - If unsure, say N. - config CLZ_TAB bool diff --git a/lib/average.c b/lib/average.c deleted file mode 100644 index 114d1beae0c7..000000000000 --- a/lib/average.c +++ /dev/null @@ -1,64 +0,0 @@ -/* - * lib/average.c - * - * This source code is licensed under the GNU General Public License, - * Version 2. See the file COPYING for more details. - */ - -#include -#include -#include -#include -#include - -/** - * DOC: Exponentially Weighted Moving Average (EWMA) - * - * These are generic functions for calculating Exponentially Weighted Moving - * Averages (EWMA). We keep a structure with the EWMA parameters and a scaled - * up internal representation of the average value to prevent rounding errors. - * The factor for scaling up and the exponential weight (or decay rate) have to - * be specified thru the init fuction. The structure should not be accessed - * directly but only thru the helper functions. - */ - -/** - * ewma_init() - Initialize EWMA parameters - * @avg: Average structure - * @factor: Factor to use for the scaled up internal value. The maximum value - * of averages can be ULONG_MAX/(factor*weight). For performance reasons - * factor has to be a power of 2. - * @weight: Exponential weight, or decay rate. This defines how fast the - * influence of older values decreases. For performance reasons weight has - * to be a power of 2. - * - * Initialize the EWMA parameters for a given struct ewma @avg. - */ -void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight) -{ - WARN_ON(!is_power_of_2(weight) || !is_power_of_2(factor)); - - avg->weight = ilog2(weight); - avg->factor = ilog2(factor); - avg->internal = 0; -} -EXPORT_SYMBOL(ewma_init); - -/** - * ewma_add() - Exponentially weighted moving average (EWMA) - * @avg: Average structure - * @val: Current value - * - * Add a sample to the average. - */ -struct ewma *ewma_add(struct ewma *avg, unsigned long val) -{ - unsigned long internal = ACCESS_ONCE(avg->internal); - - ACCESS_ONCE(avg->internal) = internal ? - (((internal << avg->weight) - internal) + - (val << avg->factor)) >> avg->weight : - (val << avg->factor); - return avg; -} -EXPORT_SYMBOL(ewma_add); -- cgit v1.2.3-71-gd317