Add generic exponentially weighted moving average (EWMA) function
Subsystems (4)
PATCH v8 1/3 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.
--
v8: Rename ewma_get() to ewma_read().
v7: Include bug.h. ewma_init() returns void. Use CONFIG_AVERAGE.
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/Kconfig | 3 ++ lib/Makefile | 2 ++ lib/average.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 94 insertions(+), 0 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 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 DIV_ROUND_CLOSEST (avg->internal, avg->factor); +} + +#endif /* _LINUX_AVERAGE_H */
lib/Kconfig +3 -0
@@ -210,4 +210,7 @@ config GENERIC_ATOMIC64 config LRU_CACHE tristate +config AVERAGE + bool + endmenu
lib/Makefile +2 -0
@@ -106,6 +106,8 @@ obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o +obj-$(CONFIG_AVERAGE) += average.o + hostprogs-y := gen_crc32table clean-files := crc32table.h
lib/average.c new file +57 -0
57 lines not on this page · raw message
PATCH v8 2/3 ath5k: Use generic EWMA library
Remove ath5k's private moving average implementation in favour of the generic library version.
--- drivers/net/wireless/ath/ath5k/Kconfig | 1 + drivers/net/wireless/ath/ath5k/ani.c | 4 ++-- drivers/net/wireless/ath/ath5k/ath5k.h | 26 ++------------------------ drivers/net/wireless/ath/ath5k/base.c | 4 ++-- drivers/net/wireless/ath/ath5k/debug.c | 2 +- 5 files changed, 8 insertions(+), 29 deletions(-)
drivers/net/wireless/ath/ath5k/Kconfig +1 -0
@@ -4,6 +4,7 @@ config ATH5K select MAC80211_LEDS select LEDS_CLASS select NEW_LEDS + select AVERAGE ---help--- This module adds support for wireless adapters based on Atheros 5xxx chipset.
drivers/net/wireless/ath/ath5k/ani.c +2 -2
@@ -216,7 +216,7 @@ static void ath5k_ani_raise_immunity(struct ath5k_hw *ah, struct ath5k_ani_state *as, bool ofdm_trigger) { - int rssi = ah->ah_beacon_rssi_avg.avg; + int rssi = ewma_read(&ah->ah_beacon_rssi_avg);ATH5K_DBG_UNLIMIT (ah->ah_sc,ATH5K_DEBUG_ANI ,"raise immunity (%s)" , ofdm_trigger ?"ODFM" :"CCK" );
@@ -301,7 +301,7 @@ ath5k_ani_raise_immunity(struct ath5k_hw *ah, struct ath5k_ani_state *as,static void ath5k_ani_lower_immunity (struct ath5k_hw *ah,struct ath5k_ani_state *as) { -int rssi = ah->ah_beacon_rssi_avg.avg; +int rssi =ewma_read (&ah->ah_beacon_rssi_avg);ATH5K_DBG_UNLIMIT (ah->ah_sc,ATH5K_DEBUG_ANI ,"lower immunity" );
drivers/net/wireless/ath/ath5k/ath5k.h +2 -24
@@ -25,6 +25,7 @@#include <linux/io.h> #include <linux/types.h> +#include <linux/average.h> #include <net/mac80211.h> /* RX/TX descriptor hw structs
@@ -1102,7 +1103,7 @@ struct ath5k_hw {struct ath5k_nfcal_hist ah_nfcal_hist;/* average beacon RSSI in our BSS (used by ANI) */ -struct ath5k_avg_val ah_beacon_rssi_avg; +struct ewma ah_beacon_rssi_avg;/* noise floor from last periodic calibration */ s32 ah_noise_floor;
@@ -1315,27 +1316,4 @@ static inline u32 ath5k_hw_bitswap(u32 val, unsigned int bits) return retval; } -#define AVG_SAMPLES 8 -#define AVG_FACTOR 1000 - -/** -* ath5k_moving_average - Exponentially weighted moving average -* @avg: average structure -* @val: current value -* -* This implementation make use of a struct ath5k_avg_val to prevent rounding -* errors. -*/ -static inline struct ath5k_avg_val -ath5k_moving_average (const struct ath5k_avg_val avg,const int val) -{ -struct ath5k_avg_val new; - new.avg_weight = avg.avg_weight ? - (((avg.avg_weight * ((AVG_SAMPLES ) -1 )) + - (val * (AVG_FACTOR ))) / (AVG_SAMPLES )) : - (val * (AVG_FACTOR )); - new.avg = new.avg_weight / (AVG_FACTOR ); -return new; -} -#endif
drivers/net/wireless/ath/ath5k/base.c +2 -2
@@ -1307,8 +1307,7 @@ ath5k_update_beacon_rssi(struct ath5k_softc *sc, struct sk_buff *skb, int rssi) memcmp(mgmt->bssid, common->curbssid, ETH_ALEN) != 0)return ; - ah->ah_beacon_rssi_avg =ath5k_moving_average (ah->ah_beacon_rssi_avg, - rssi); +ewma_add (&ah->ah_beacon_rssi_avg, rssi);/* in IBSS mode we should keep RSSI statistics per neighbour */ /* le16_to_cpu(mgmt->u.beacon.capab_info) & WLAN_CAPABILITY_IBSS */
@@ -2562,6 +2561,7 @@ ath5k_reset(struct ath5k_softc *sc, struct ieee80211_channel *chan) ah->ah_cal_next_full = jiffies; ah->ah_cal_next_ani = jiffies; ah->ah_cal_next_nf = jiffies; +ewma_init (&ah->ah_beacon_rssi_avg,1000 ,8 );/* * Change channels and update the h/w rate map if we're switching;
drivers/net/wireless/ath/ath5k/debug.c +1 -1
@@ -719,7 +719,7 @@ static ssize_t read_file_ani(struct file *file, char __user *user_buf, st->mib_intr); len +=snprintf (buf+len,sizeof (buf)-len,"beacon RSSI average:\t%d\n" , - sc->ah->ah_beacon_rssi_avg.avg); + (int )ewma_read (&sc->ah->ah_beacon_rssi_avg));#define CC_PRINT (_struct, _field) \ _struct._field, \
PATCH v8 3/3 nl80211/mac80211: Report signal average
In reply to Bruno RandolfExtend nl80211 to report an exponential weighted moving average (EWMA) of the signal value. Since the signal value usually fluctuates between different packets, an average can be more useful than the value of the last packet.
This uses the recently added generic EWMA library function.
--- include/linux/nl80211.h | 2 ++ include/net/cfg80211.h | 4 ++++ net/mac80211/Kconfig | 1 + net/mac80211/cfg.c | 3 ++- net/mac80211/rx.c | 1 + net/mac80211/sta_info.c | 2 ++ net/mac80211/sta_info.h | 3 +++ net/wireless/nl80211.c | 3 +++ 8 files changed, 18 insertions(+), 1 deletions(-)
include/linux/nl80211.h +2 -0
@@ -1132,6 +1132,7 @@ enum nl80211_rate_info {* @__NL80211_STA_INFO_AFTER_LAST: internal * @NL80211_STA_INFO_MAX: highest possible station info attribute * @NL80211_STA_INFO_SIGNAL: signal strength of last received PPDU (u8, dBm) +* @NL80211_STA_INFO_SIGNAL_AVG: signal strength average (u8, dBm) * @NL80211_STA_INFO_TX_BITRATE: current unicast tx rate, nested attribute * containing info as possible, see &enum nl80211_sta_info_txrate. * @NL80211_STA_INFO_RX_PACKETS: total received packet (u32, from this station)
@@ -1149,6 +1150,7 @@ enum nl80211_sta_info {NL80211_STA_INFO_PLID ,NL80211_STA_INFO_PLINK_STATE ,NL80211_STA_INFO_SIGNAL , +NL80211_STA_INFO_SIGNAL_AVG ,NL80211_STA_INFO_TX_BITRATE ,NL80211_STA_INFO_RX_PACKETS , NL80211_STA_INFO_TX_PACKETS,
include/net/cfg80211.h +4 -0
@@ -424,6 +424,7 @@ struct station_parameters {* @STATION_INFO_TX_RETRIES: @tx_retries filled * @STATION_INFO_TX_FAILED: @tx_failed filled * @STATION_INFO_RX_DROP_MISC: @rx_dropped_misc filled +* @STATION_INFO_SIGNAL_AVG: @signal_avg filled */ enum station_info_flags {STATION_INFO_INACTIVE_TIME =1 <<0 ,
@@ -439,6 +440,7 @@ enum station_info_flags {STATION_INFO_TX_RETRIES =1 <<10 ,STATION_INFO_TX_FAILED =1 <<11 ,STATION_INFO_RX_DROP_MISC =1 <<12 , + STATION_INFO_SIGNAL_AVG = 1<<13, };/**
@@ -485,6 +487,7 @@ struct rate_info {* @plid: mesh peer link id * @plink_state: mesh peer link state * @signal: signal strength of last received packet in dBm +* @signal_avg: signal strength average in dBm * @txrate: current unicast bitrate to this station * @rx_packets: packets received from this station * @tx_packets: packets transmitted to this station
@@ -505,6 +508,7 @@ struct station_info {u16 plid;u8 plink_state;s8 signal; +s8 signal_avg;struct rate_info txrate;u32 rx_packets;u32 tx_packets;
net/mac80211/Kconfig +1 -0
@@ -6,6 +6,7 @@ config MAC80211 select CRYPTO_ARC4 select CRYPTO_AES select CRC32 + select AVERAGE ---help--- This option enables the hardware independent IEEE 802.11 networking stack.
net/mac80211/cfg.c +2 -1
@@ -343,8 +343,9 @@ static void sta_set_sinfo(struct sta_info *sta, struct station_info *sinfo)if ((sta->local->hw.flags &IEEE80211_HW_SIGNAL_DBM ) || (sta->local->hw.flags &IEEE80211_HW_SIGNAL_UNSPEC )) { - sinfo->filled |=STATION_INFO_SIGNAL ; + sinfo->filled |=STATION_INFO_SIGNAL |STATION_INFO_SIGNAL_AVG ; sinfo->signal = (s8 )sta->last_signal; + sinfo->signal_avg = (s8) -ewma_read (&sta->avg_signal); } sinfo->txrate.flags =0 ;
net/mac80211/rx.c +1 -0
@@ -1158,6 +1158,7 @@ ieee80211_rx_h_sta_process(struct ieee80211_rx_data *rx) sta->rx_fragments++; sta->rx_bytes += rx->skb->len; sta->last_signal = status->signal; +ewma_add (&sta->avg_signal, -status->signal);/* * Change STA power saving mode only at the end of a frame
net/mac80211/sta_info.c +2 -0
@@ -241,6 +241,8 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata, sta->local = local; sta->sdata = sdata; +ewma_init (&sta->avg_signal,1000 ,8 ); +if (sta_prepare_rate_control (local, sta, gfp)) {kfree (sta);return NULL ;
net/mac80211/sta_info.h +3 -0
@@ -13,6 +13,7 @@#include <linux/types.h> #include <linux/if_ether.h> #include <linux/workqueue.h> +#include <linux/average.h> #include "key.h" /**
@@ -224,6 +225,7 @@ enum plink_state {* @rx_fragments: number of received MPDUs * @rx_dropped: number of dropped MPDUs from this STA * @last_signal: signal of last received frame from this STA +* @avg_signal: moving average of signal of received frames from this STA * @last_seq_ctrl: last received seq/frag number from this STA (per RX queue) * @tx_filtered_count: number of frames the hardware filtered for this STA * @tx_retry_failed: number of frames that failed retry
@@ -291,6 +293,7 @@ struct sta_info {unsigned long rx_fragments;unsigned long rx_dropped;int last_signal; +struct ewma avg_signal;__le16 last_seq_ctrl[NUM_RX_DATA_QUEUES ];/* Updated from TX status path only, no locking requirements */
net/wireless/nl80211.c +3 -0
@@ -1841,6 +1841,9 @@ static int nl80211_send_station(struct sk_buff *msg, u32 pid, u32 seq,if (sinfo->filled &STATION_INFO_SIGNAL )NLA_PUT_U8 (msg,NL80211_STA_INFO_SIGNAL , sinfo->signal); +if (sinfo->filled &STATION_INFO_SIGNAL_AVG ) +NLA_PUT_U8 (msg,NL80211_STA_INFO_SIGNAL_AVG , + sinfo->signal_avg);if (sinfo->filled &STATION_INFO_TX_BITRATE ) { txrate =nla_nest_start (msg,NL80211_STA_INFO_TX_BITRATE );if (!txrate)
Re: [PATCH v8 3/3] nl80211/mac80211: Report signal average
Quoted 31 lines · Bruno Randolf
Extend nl80211 to report an exponential weighted moving average (EWMA) of the signal value. Since the signal value usually fluctuates between different packets, an average can be more useful than the value of the last packet.
This uses the recently added generic EWMA library function.
Signed-off-by Bruno Randolf <[email protected]>--- include/linux/nl80211.h | 2 ++ include/net/cfg80211.h | 4 ++++ net/mac80211/Kconfig | 1 + net/mac80211/cfg.c | 3 ++- net/mac80211/rx.c | 1 + net/mac80211/sta_info.c | 2 ++ net/mac80211/sta_info.h | 3 +++ net/wireless/nl80211.c | 3 +++ 8 files changed, 18 insertions(+), 1 deletions(-)include/linux/nl80211.h +1
-0@@ -1132,6 +1132,7 @@ enum nl80211_rate_info {* @__NL80211_STA_INFO_AFTER_LAST: internal * @NL80211_STA_INFO_MAX: highest possible station info attribute * @NL80211_STA_INFO_SIGNAL: signal strength of last received PPDU (u8, dBm) +* @NL80211_STA_INFO_SIGNAL_AVG: signal strength average (u8, dBm) * @NL80211_STA_INFO_TX_BITRATE: current unicast tx rate, nested attribute * containing info as possible, see &enum nl80211_sta_info_txrate. * @NL80211_STA_INFO_RX_PACKETS: total received packet (u32, from this station)
include/linux/nl80211.h enum nl80211_sta_info { · line 1156
Quoted 7 lines
include/linux/nl80211.h +1
-0@@ -1149,6 +1150,7 @@ enum nl80211_sta_info {NL80211_STA_INFO_PLID ,NL80211_STA_INFO_PLINK_STATE ,NL80211_STA_INFO_SIGNAL , +NL80211_STA_INFO_SIGNAL_AVG ,NL80211_STA_INFO_TX_BITRATE ,NL80211_STA_INFO_RX_PACKETS , NL80211_STA_INFO_TX_PACKETS,
It's been pointed-out that this breaks kernel->userland ABI.
That could be fixed rather easily, but due to the performance concerns I'm going to just revert this one for now. Please correct the ABI issue when submitting a new version that addresses the performance concerns raised by Jouni.
John
Signature · 2 lines
John W. Linville Someday the world will need a hero, and you [email protected] might be all we have. Be ready.