Add generic exponentially weighted moving average (EWMA) function
PATCH v6 1/1 Add generic exponentially weighted moving average (EWMA) function
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.
--
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
include/linux/average.h new file +32 -0
@@ -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 */
lib/Makefile +1 -1
@@ -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
lib/average.c new file +58 -0
58 lines not on this page · raw message
Andrew Morton
maintainerQuoted 9 lines · 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.
Quoted 7 lines
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??
Quoted 10 lines
+/**
+ * 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:".
Quoted 14 lines · On Thu November 11 2010 12:53:29 Andrew Morton wrote:
Quoted 13 lines · 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]>
Quoted 7 lines
Quoted 4 lines
--
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
Andrew Morton
maintainerQuoted 12 lines · 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....
lib/Makefile lib-y += kobject.o kref.o klist.o · line 24
Quoted 5 lines
lib/Makefile +1
-1@@ -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).
Quoted 30 lines · On Thu November 11 2010 13:02:31 Andrew Morton wrote:
Quoted 12 lines · 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....
lib/Makefile lib-y += kobject.o kref.o klist.o · line 27
Quoted 8 lines
lib/Makefile +1
-1@@ -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.oIt 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.
Quoted 7 lines
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.
Quoted 3 lines
(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
Quoted 13 lines · Bruno Randolf
Quoted 11 lines · 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?
Quoted 8 lines
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.
Quoted 5 lines
Quoted 3 lines
(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
Quoted 4 lines
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.
Signature · 3 lines
Stefan Richter -=====-==-=- =-== -=-== http://arcgraph.de/sr/
Quoted 3 lines · 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.
Quoted 10 lines
Quoted 5 lines
Quoted 3 lines
(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
Kconfigvariable for it which is SELECTed by thoseKconfigprompts that require it? That's the good solution that we use for a number of similar library functions.$ cat lib/Makefile
Ok.
Quoted 1 line
You use
WARN_ONinlib/average.c. You should include <linux/bug.h>.
Thanks.
Quoted 2 lines
Why do
ewma_init()andewma_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
Quoted 9 lines
Quoted 2 lines
Why do
ewma_init()andewma_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 usingewma_get(ewma_add(&ewma, val));
ewma_add(&ewma, val); ewma_get(&ewma);
is enough simpler and cleaner. I don't oppse this :)
Quoted 9 lines · KOSAKI Motohiro
Quoted 8 lines
Quoted 2 lines
Why do
ewma_init()andewma_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 usingewma_get(ewma_add(&ewma, val));
Quoted 4 lines
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".
Signature · 3 lines
Stefan Richter -=====-==-=- =-== -===- http://arcgraph.de/sr/
Quoted 10 lines · On Sun November 14 2010 17:51:08 Stefan Richter wrote:
Quoted 10 lines
Quoted 10 lines
Quoted 2 lines
Why do
ewma_init()andewma_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 usingewma_get(ewma_add(&ewma, val));
Quoted 7 lines
Quoted 4 lines
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: :-)
- anewma_add_returncould do what ewma_get(ewma_add(...)) is meant for,
I think this would be overkill. We're just talking about a return pointer...
Quoted 1 line
- or
ewma_additself 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.
Quoted 3 lines
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
Quoted 9 lines · On Nov 15 Bruno Randolf wrote:
Quoted 4 lines · 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.
Signature · 3 lines
Stefan Richter -=====-==-=- =-== -==== http://arcgraph.de/sr/
Quoted 17 lines · On Mon November 15 2010 16:38:39 Stefan Richter wrote:
Quoted 9 lines · On Nov 15 Bruno Randolf wrote:
Quoted 4 lines · 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_getvs.get_unalignedand many more. I for one immediately think of "something is having its reference count incremented here" when I come across asomething_getwhen reading code.
Quoted 6 lines
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( ininclude/. 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
Quoted 1 line · Bruno Randolf
So what would you prefer? And what is the opinion of other people?
ewma_read()