This adds generic functions for calculating Exponentially Weighted Moving
Averages (EWMA). This implementation makes use of a structure which keeps the
EWMA parameters and a scaled up internal representation to reduce rounding
errors.
The original idea for this implementation came from the rt2x00 driver
(rt2x00link.c). I would like to use it in several places in the mac80211 and
ath5k code and I hope it can be useful in many other places in the kernel code.
Signed-off-by: Bruno Randolf <[email protected]>
Reviewed-by: KOSAKI Motohiro <[email protected]>
--
Excuse me, but can I expect this to be merged anytime soon? Where do I check if
it got merged? I'm resending the patch in case it got lost.
Thanks,
bruno
--
v6: Fixed ULONG_MAX in comment. Add reviewed by KOSAKI Motohiro.
v5: Use unsigned long instead of insigned int.
v4: Initialize internal variable to 0. Remove unneeded const qualifiers.
v3: Addressing Andrew Mortons comments: Implement in lib/average.c and make
access and initalization functions. Use unsigned int for values. Rename
functions to ewma_* since there might be other moving average
implementations which are not exponentially weighted.
v2: Renamed 'samples' to 'weight'. Added more documentation. Use avg_val
pointer. Add a WARN_ON_ONCE for invalid values of 'weight'. Divide
and round up/down.
---
include/linux/average.h | 32 ++++++++++++++++++++++++++
lib/Makefile | 2 +-
lib/average.c | 58 +++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 91 insertions(+), 1 deletions(-)
create mode 100644 include/linux/average.h
create mode 100644 lib/average.c
diff --git a/include/linux/average.h b/include/linux/average.h
new file mode 100644
index 0000000..f3b36d4
--- /dev/null
+++ b/include/linux/average.h
@@ -0,0 +1,32 @@
+#ifndef _LINUX_AVERAGE_H
+#define _LINUX_AVERAGE_H
+
+#include <linux/kernel.h>
+
+/* Exponentially weighted moving average (EWMA) */
+
+/* For more documentation see lib/average.c */
+
+struct ewma {
+ unsigned long internal;
+ unsigned long factor;
+ unsigned long weight;
+};
+
+extern struct ewma *ewma_init(struct ewma *avg, unsigned long factor,
+ unsigned long weight);
+
+extern struct ewma *ewma_add(struct ewma *avg, unsigned long val);
+
+/**
+ * ewma_get() - Get average value
+ * @avg: Average structure
+ *
+ * Returns the average value held in @avg.
+ */
+static inline unsigned long ewma_get(const struct ewma *avg)
+{
+ return DIV_ROUND_CLOSEST(avg->internal, avg->factor);
+}
+
+#endif /* _LINUX_AVERAGE_H */
diff --git a/lib/Makefile b/lib/Makefile
index e6a3763..f66acf7 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o
obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
- string_helpers.o gcd.o lcm.o list_sort.o uuid.o
+ string_helpers.o gcd.o lcm.o list_sort.o uuid.o average.o
ifeq ($(CONFIG_DEBUG_KOBJECT),y)
CFLAGS_kobject.o += -DDEBUG
diff --git a/lib/average.c b/lib/average.c
new file mode 100644
index 0000000..3262e04
--- /dev/null
+++ b/lib/average.c
@@ -0,0 +1,58 @@
+/*
+ * lib/average.c
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2. See the file COPYING for more details.
+ */
+
+#include <linux/module.h>
+#include <linux/average.h>
+
+/**
+ * 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).
+ * @weight: Exponential weight, or decay rate. This defines how fast the
+ * influence of older values decreases. Has to be bigger than 1.
+ *
+ * Initialize the EWMA parameters for a given struct ewma @avg.
+ */
+struct ewma *ewma_init(struct ewma *avg, unsigned long factor,
+ unsigned long weight)
+{
+ WARN_ON(weight <= 1 || factor == 0);
+ avg->internal = 0;
+ avg->weight = weight;
+ avg->factor = factor;
+ return avg;
+}
+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)
+{
+ avg->internal = avg->internal ?
+ (((avg->internal * (avg->weight - 1)) +
+ (val * avg->factor)) / avg->weight) :
+ (val * avg->factor);
+ return avg;
+}
+EXPORT_SYMBOL(ewma_add);
On Thu, 11 Nov 2010 12:47:56 +0900 Bruno Randolf <[email protected]> wrote:
> This adds generic functions for calculating Exponentially Weighted Moving
> Averages (EWMA). This implementation makes use of a structure which keeps the
> EWMA parameters and a scaled up internal representation to reduce rounding
> errors.
>
> The original idea for this implementation came from the rt2x00 driver
> (rt2x00link.c). I would like to use it in several places in the mac80211 and
> ath5k code and I hope it can be useful in many other places in the kernel code.
>
> Signed-off-by: Bruno Randolf <[email protected]>
> Reviewed-by: KOSAKI Motohiro <[email protected]>
>
> --
>
> Excuse me, but can I expect this to be merged anytime soon? Where do I check if
> it got merged? I'm resending the patch in case it got lost.
Yes, sorry, this is buried in my exponentially increasing backlog.
It's going to take me a while to catch up again.
Unless I just merge stuff without looking at it. hm, I wonder if that
would make any difference??
> +/**
> + * 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.
> + */
<reads Documentation/kernel-doc-nano-HOWTO.txt>
Well, I never knew about "DOC:".
On Thu November 11 2010 12:53:29 Andrew Morton wrote:
> On Thu, 11 Nov 2010 12:47:56 +0900 Bruno Randolf <[email protected]> wrote:
> > This adds generic functions for calculating Exponentially Weighted Moving
> > Averages (EWMA). This implementation makes use of a structure which keeps
> > the EWMA parameters and a scaled up internal representation to reduce
> > rounding errors.
> >
> > The original idea for this implementation came from the rt2x00 driver
> > (rt2x00link.c). I would like to use it in several places in the mac80211
> > and ath5k code and I hope it can be useful in many other places in the
> > kernel code.
> >
> > Signed-off-by: Bruno Randolf <[email protected]>
> > Reviewed-by: KOSAKI Motohiro <[email protected]>
> >
> > --
> >
> > Excuse me, but can I expect this to be merged anytime soon? Where do I
> > check if it got merged? I'm resending the patch in case it got lost.
>
> Yes, sorry, this is buried in my exponentially increasing backlog.
> It's going to take me a while to catch up again.
I don't mean to be pushy, so please take your time...
bruno
On Thu, 11 Nov 2010 12:47:56 +0900 Bruno Randolf <[email protected]> wrote:
>
> ...
>
> The original idea for this implementation came from the rt2x00 driver
> (rt2x00link.c). I would like to use it in several places in the mac80211 and
> ath5k code and I hope it can be useful in many other places in the kernel code.
>
> ...
>
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o
>
> obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o random32.o \
> bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
> - string_helpers.o gcd.o lcm.o list_sort.o uuid.o
> + string_helpers.o gcd.o lcm.o list_sort.o uuid.o average.o
It would be a bit strange to merge this into 2.6.36-rcX when there are
no callers. But you do want it to be present in some tree for your own
testing and distribution purposes.
So perhaps it would be best to merge this via the wireless tree, so
everything exists in one place and it can be fed into linux-next and
into mainline in an orderly fashion.
If that sounds like a plan then I can send this patch in John's
direction. Which means that if he merges it into mainline without also
merging any of your patches which _use_ this function then we still end
up with unused code in mainline, but at least that way it wasn't my fault ;)
Let me know your thoughts?
(And it's a bit sad that the function will exist in the base vmlinux
even for people who don't ever use it, but that's a problem which we
don't really have a good solution for).
On Thu November 11 2010 13:02:31 Andrew Morton wrote:
> On Thu, 11 Nov 2010 12:47:56 +0900 Bruno Randolf <[email protected]> wrote:
> > ...
> >
> > The original idea for this implementation came from the rt2x00 driver
> > (rt2x00link.c). I would like to use it in several places in the mac80211
> > and ath5k code and I hope it can be useful in many other places in the
> > kernel code.
> >
> > ...
> >
> > --- a/lib/Makefile
> > +++ b/lib/Makefile
> > @@ -21,7 +21,7 @@ lib-y += kobject.o kref.o klist.o
> >
> > obj-y += bcd.o div64.o sort.o parser.o halfmd4.o debug_locks.o
> > random32.o \
> >
> > bust_spinlocks.o hexdump.o kasprintf.o bitmap.o scatterlist.o \
> >
> > - string_helpers.o gcd.o lcm.o list_sort.o uuid.o
> > + string_helpers.o gcd.o lcm.o list_sort.o uuid.o average.o
>
> It would be a bit strange to merge this into 2.6.36-rcX when there are
> no callers. But you do want it to be present in some tree for your own
> testing and distribution purposes.
>
> So perhaps it would be best to merge this via the wireless tree, so
> everything exists in one place and it can be fed into linux-next and
> into mainline in an orderly fashion.
>
> If that sounds like a plan then I can send this patch in John's
> direction. Which means that if he merges it into mainline without also
> merging any of your patches which _use_ this function then we still end
> up with unused code in mainline, but at least that way it wasn't my fault
> ;)
>
> Let me know your thoughts?
Sounds like a good plan to me. But let's hear Johns opinion.
I have a patch or two using this function, which I hope will get merged into
wireless-testing soon after, but obviously it's up to John. There are more
places in the wireless part which could make use of this function (right now
each have their own EWMA implementation), and I'll try to get them all
updated, but finally it's the individual maintainers, who decide if they want
to make that change or not, I guess.
> (And it's a bit sad that the function will exist in the base vmlinux
> even for people who don't ever use it, but that's a problem which we
> don't really have a good solution for).
Hmm, should I switch it back to all inlines?
On the other hand, if a generic EWMA function is useful at all I guess it
could be used in many places all over the kernel. Unfortunately I don't have
time and knowledge to find all these places and update them to use the generic
code.
bruno
Bruno Randolf wrote:
> On Thu November 11 2010 13:02:31 Andrew Morton wrote:
>> So perhaps it would be best to merge this via the wireless tree, so
>> everything exists in one place and it can be fed into linux-next and
>> into mainline in an orderly fashion.
>>
>> If that sounds like a plan then I can send this patch in John's
>> direction. Which means that if he merges it into mainline without also
>> merging any of your patches which _use_ this function then we still end
>> up with unused code in mainline, but at least that way it wasn't my fault
>> ;)
>>
>> Let me know your thoughts?
>
> Sounds like a good plan to me. But let's hear Johns opinion.
>
> I have a patch or two using this function, which I hope will get merged into
> wireless-testing soon after, but obviously it's up to John. There are more
> places in the wireless part which could make use of this function (right now
> each have their own EWMA implementation), and I'll try to get them all
> updated, but finally it's the individual maintainers, who decide if they want
> to make that change or not, I guess.
It seems totally clear-cut to me that code like this is submitted together
with at least one call site, and it is submitted through the tree in which
that call site is maintained.
>> (And it's a bit sad that the function will exist in the base vmlinux
>> even for people who don't ever use it, but that's a problem which we
>> don't really have a good solution for).
>
> Hmm, should I switch it back to all inlines?
Add a hidden Kconfig variable for it which is SELECTed by those Kconfig
prompts that require it? That's the good solution that we use for a number of
similar library functions.
$ cat lib/Makefile
> On the other hand, if a generic EWMA function is useful at all I guess it
> could be used in many places all over the kernel. Unfortunately I don't have
> time and knowledge to find all these places and update them to use the generic
> code.
Don't worry. There are people who specialize in this sort of activity.
Two remarks on your patch:
You use WARN_ON in lib/average.c. You should include <linux/bug.h>.
Why do ewma_init() and ewma_add() return their first argument? They look to
me like they can be straight-forward void functions.
--
Stefan Richter
-=====-==-=- =-== -=-==
http://arcgraph.de/sr/
On Fri November 12 2010 03:17:34 Stefan Richter wrote:
> It seems totally clear-cut to me that code like this is submitted together
> with at least one call site, and it is submitted through the tree in which
> that call site is maintained.
Ok. So I'll re-send the patch thru John's wireless tree after I fixed up your
comments.
> >> (And it's a bit sad that the function will exist in the base vmlinux
> >> even for people who don't ever use it, but that's a problem which we
> >> don't really have a good solution for).
> >
> > Hmm, should I switch it back to all inlines?
>
> Add a hidden Kconfig variable for it which is SELECTed by those Kconfig
> prompts that require it? That's the good solution that we use for a number
> of similar library functions.
> $ cat lib/Makefile
Ok.
> You use WARN_ON in lib/average.c. You should include <linux/bug.h>.
Thanks.
> Why do ewma_init() and ewma_add() return their first argument? They look
> to me like they can be straight-forward void functions.
You are right, for ewma_init() it does not make sense.
For ewma_add() I think it does. This has been discussed before (e.g.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2010-10/msg09124.html).
Some people might want to get the value when they add a sample by using
ewma_get(ewma_add(&ewma, val));
Bruno
> > Why do ewma_init() and ewma_add() return their first argument? They look
> > to me like they can be straight-forward void functions.
>
> You are right, for ewma_init() it does not make sense.
>
> For ewma_add() I think it does. This has been discussed before (e.g.
> http://linux.derkeiler.com/Mailing-Lists/Kernel/2010-10/msg09124.html).
> Some people might want to get the value when they add a sample by using
> ewma_get(ewma_add(&ewma, val));
ewma_add(&ewma, val);
ewma_get(&ewma);
is enough simpler and cleaner. I don't oppse this :)
KOSAKI Motohiro wrote:
>>> Why do ewma_init() and ewma_add() return their first argument? They look
>>> to me like they can be straight-forward void functions.
>> You are right, for ewma_init() it does not make sense.
>>
>> For ewma_add() I think it does. This has been discussed before (e.g.
>> http://linux.derkeiler.com/Mailing-Lists/Kernel/2010-10/msg09124.html).
>> Some people might want to get the value when they add a sample by using
>> ewma_get(ewma_add(&ewma, val));
>
> ewma_add(&ewma, val);
> ewma_get(&ewma);
>
> is enough simpler and cleaner. I don't oppse this :)
There are more candidate colors for the bike shed: :-)
- an ewma_add_return could do what ewma_get(ewma_add(...)) is meant for,
- or ewma_add itself could return the result.
BTW, isn't "get" more usually used as a prefix for these kinds of functions in
kernel APIs? "get" as a suffix more often means "get a reference" alias
increase reference count rather than "get the value".
--
Stefan Richter
-=====-==-=- =-== -===-
http://arcgraph.de/sr/
On Sun November 14 2010 17:51:08 Stefan Richter wrote:
> >>> Why do ewma_init() and ewma_add() return their first argument? They
> >>> look to me like they can be straight-forward void functions.
> >>
> >> You are right, for ewma_init() it does not make sense.
> >>
> >> For ewma_add() I think it does. This has been discussed before (e.g.
> >> http://linux.derkeiler.com/Mailing-Lists/Kernel/2010-10/msg09124.html).
> >> Some people might want to get the value when they add a sample by using
> >> ewma_get(ewma_add(&ewma, val));
> >>
> > ewma_add(&ewma, val);
> > ewma_get(&ewma);
> >
> > is enough simpler and cleaner. I don't oppse this :)
>
> There are more candidate colors for the bike shed: :-)
> - an ewma_add_return could do what ewma_get(ewma_add(...)) is meant for,
I think this would be overkill. We're just talking about a return pointer...
> - or ewma_add itself could return the result.
The way I intend to use it, I will add samples much more often than I get a
value, so IMHO it makes sense to split it.
> BTW, isn't "get" more usually used as a prefix for these kinds of functions
> in kernel APIs? "get" as a suffix more often means "get a reference"
> alias increase reference count rather than "get the value".
Umm. I don't know and honstly I don't care. I think the API ewma_* is
consistent. If you have a good reason to change it please let me know,
otherwise i'd just leave it like it is now.
bruno
On Nov 15 Bruno Randolf wrote:
> On Sun November 14 2010 17:51:08 Stefan Richter wrote:
> > BTW, isn't "get" more usually used as a prefix for these kinds of
> > functions in kernel APIs? "get" as a suffix more often means "get
> > a reference" alias increase reference count rather than "get the
> > value".
>
> Umm. I don't know and honstly I don't care. I think the API ewma_* is
> consistent. If you have a good reason to change it please let me
> know, otherwise i'd just leave it like it is now.
It is not about consistency of the API in itself but about consistency
with the rest of the kernel. Cf. skb_get vs. get_unaligned and many
more. I for one immediately think of "something is having its
reference count incremented here" when I come across a something_get
when reading code.
I don't know of such a convention being documented anywhere. But for an
overkill of examples of "get" as prefix and suffix, grep for get_ and
_get( in include/. The same convention exists IME with "put" that
either writes a value or drops a reference.
Sorry for bringing this up so late but it is IMO not a trivial point.
--
Stefan Richter
-=====-==-=- =-== -====
http://arcgraph.de/sr/
On Mon November 15 2010 16:38:39 Stefan Richter wrote:
> On Nov 15 Bruno Randolf wrote:
> > On Sun November 14 2010 17:51:08 Stefan Richter wrote:
> > > BTW, isn't "get" more usually used as a prefix for these kinds of
> > > functions in kernel APIs? "get" as a suffix more often means "get
> > > a reference" alias increase reference count rather than "get the
> > > value".
> >
> > Umm. I don't know and honstly I don't care. I think the API ewma_* is
> > consistent. If you have a good reason to change it please let me
> > know, otherwise i'd just leave it like it is now.
>
> It is not about consistency of the API in itself but about consistency
> with the rest of the kernel. Cf. skb_get vs. get_unaligned and many
> more. I for one immediately think of "something is having its
> reference count incremented here" when I come across a something_get
> when reading code.
>
> I don't know of such a convention being documented anywhere. But for an
> overkill of examples of "get" as prefix and suffix, grep for get_ and
> _get( in include/. The same convention exists IME with "put" that
> either writes a value or drops a reference.
>
> Sorry for bringing this up so late but it is IMO not a trivial point.
That's allright, and I have no problem changing it.
So what would you prefer? And what is the opinion of other people?
bruno
On Mon, 2010-11-15 at 16:50 +0900, Bruno Randolf wrote:
> So what would you prefer? And what is the opinion of other people?
ewma_read()