linux-kernel - Re: [PATCH] Add generic exponentially weighted moving average function

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 15 Oct 2010 08:55:23 -0500
From:	kevin granade <kevin.granade@...il.com>
To:	Bruno Randolf <br1@...fach.org>
Cc:	linux-kernel@...r.kernel.org,
	Randy Dunlap <randy.dunlap@...cle.com>,
	akpm <akpm@...ux-foundation.org>
Subject: Re: [PATCH] Add generic exponentially weighted moving average function

On Wed, Oct 13, 2010 at 8:19 PM, Bruno Randolf <br1@...fach.org> wrote:
> On Wed October 13 2010 23:01:16 kevin granade wrote:
>> On Wed, Oct 6, 2010 at 4:32 AM, Bruno Randolf <br1@...fach.org> wrote:
>> > This adds a generic exponentially weighted moving average function. This
>> > implementation makes use of a structure which keeps a scaled up internal
>> > representation to reduce rounding errors.
>> >
>> > The idea for this implementation comes from the rt2x00 driver
>> > (rt2x00link.c) and i would like to use it in several places in the
>> > mac80211 and ath5k code.
>> >
>> > Signed-off-by: Bruno Randolf <br1@...fach.org>
>> >
>> > --
>> > Is this the right place to add it? Who to CC:?
>> > ---
>> >  include/linux/average.h |   32 ++++++++++++++++++++++++++++++++
>> >  1 files changed, 32 insertions(+), 0 deletions(-)
>> >  create mode 100644 include/linux/average.h
>> >
>> > diff --git a/include/linux/average.h b/include/linux/average.h
>> > new file mode 100644
>> > index 0000000..2a00d3d
>> > --- /dev/null
>> > +++ b/include/linux/average.h
>> > @@ -0,0 +1,32 @@
>> > +#ifndef _LINUX_AVERAGE_H
>> > +#define _LINUX_AVERAGE_H
>> > +
>> > +#define AVG_FACTOR     1000
>>
>> If this is going to be general use, wouldn't it be a good feature to
>> make AVG_FACTOR adjustable?
>
> Yes, could be, but how? Another argument to the function call?
> Actually AVG_FACTOR and 'samples' should stay constant for each struct, so we
> could also store them in the struct, but that would require an inititalization
> of the struct before we can use it.

That's true, I can't think of a way of adding this without
significantly dirtying the interface.  And to be honest, it isn't a,
"I might be using this, so it'd be nice to have", but rather a general
observation.  I guess if someone needs a different decay rate at some
point then they can worry about it.

>
>> > +
>> > +struct avg_val {
>> > +       int value;
>> > +       int internal;
>> > +};
>>
>> This has a scaled up copy of the moving average, which reduces the
>> available range for the average to MAX_INT/(AVG_FACTOR*num_samples)
>> instead of +/- MAX_INT, is that acceptable?  Even if it is, shouldn't
>> it be documented?  For example, with num_samples = 10, it will roll
>> over to a negative value if the average exceeds 214,748.  This seems
>> like a potentially surprising outcome.
>
> Yes. I'll document this in the next version of the patch. Or should I use
> 64bit for the internal representation?

If you don't expect the size or speed impact to be significant, it
seems like just throwing a bigger number at the problem might be the
better option.  That will move the rollover to MAX_INT/AVG_FACTOR,
unless you also make AVG_FACTOR 64bit, which will promote all of the
multiplications to 64bit and provide full MAX_INT range for input and
output.

>
>> > +/**
>> > + * moving_average -  Exponentially weighted moving average
>> > + * @avg: average structure
>> > + * @val: current value
>> > + * @samples: number of samples
>> > + *
>> > + * This implementation make use of a struct avg_val to prevent rounding
>> > + * errors.
>> > + */
>> > +static inline struct avg_val
>> > +moving_average(const struct avg_val avg, const int val, const int
>> > samples) +{
>> > +       struct avg_val ret;
>> > +       ret.internal = avg.internal  ?
>> > +               (((avg.internal * (samples - 1)) +
>>
>> > +                       (val * AVG_FACTOR)) / samples) :
>> I'm not sure what the kernel standard is on this, but is it ok to have
>> this potential div/0 in a general purpose function?
>
> Samples should never be 0. But I can add a WARN_ON...
>
> bruno
>

I couldn't find anything that clearly indicated what the expected
precaution is in this case.  It probably isn't an issue now that I
understand that samples is intended to remain constant.  I initially
thought samples would scale from 1 - n as you were initially "loading"
samples into the structure, but now I understand that samples remains
at n throughout the process.

Kevin Granade
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/