Skip to contentSkip to conversation

Generic exponentially weighted moving average (EWMA)

PATCH Superseded Bruno Randolf 9 participants 24 messages Nov 12, 2010 – Dec 2, 2010

Subsystems (4)

v7 of 8 Superseded Latest is v8 →

lore
Share & tools
lore
#0 lore raw

v7 cover Generic exponentially weighted moving average (EWMA)

This series adds a generic exponentially weighted moving average (EWMA) library function and uses it from ath5k and mac80211. There are more places within mac80211 and other wireless drivers which could benefit from this function, which I'm going to update later and I hope this function can be useful in many places all over the kernel.

As it has been discussed on LKML, the preferred way of merging this is thru wireless-testing, since this is where the first callers will be
(http://marc.info/?l=linux-kernel&m=128949956117559&w=2).

Thanks,
Bruno

---

Bruno Randolf (3):
Add generic exponentially weighted moving average (EWMA) function
ath5k: Use generic EWMA library
nl80211/mac80211: Report signal average

 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 +
 include/linux/average.h                |   32 ++++++++++++++++++
 include/linux/nl80211.h                |    2 +
 include/net/cfg80211.h                 |    4 ++
 lib/Kconfig                            |    3 ++
 lib/Makefile                           |    2 +
 lib/average.c                          |   57 ++++++++++++++++++++++++++++++++
 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 ++
 17 files changed, 120 insertions(+), 30 deletions(-)
 create mode 100644 include/linux/average.h
 create mode 100644 lib/average.c
Signature · 1 line
Signature
#1 lore raw

PATCH v7 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.

--

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
new file mode 100644
index 0000000..ee3da51
@@ -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_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/Kconfig +3 -0
index fa9bf2c..3116aa6 100644
@@ -210,4 +210,7 @@ config GENERIC_ATOMIC64
 config LRU_CACHE
 	tristate
 
+config AVERAGE
+	bool
+
 endmenu
lib/Makefile +2 -0
index e6a3763..76d3b85 100644
@@ -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

#2 lore raw

PATCH v7 2/3 ath5k: Use generic EWMA library

In reply to Bruno Randolf

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
index eb83b7b..4784457 100644
@@ -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
index f141919..545e489 100644
@@ -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_get(&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_get(&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
index 308b79e..2718136 100644
@@ -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
index 4d21202..ae069b7 100644
@@ -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
index 54dcf77..043cb15 100644
@@ -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_get(&sc->ah->ah_beacon_rssi_avg));
 
 #define CC_PRINT(_struct, _field) \
 	_struct._field, \
#3 lore raw

PATCH v7 3/3 nl80211/mac80211: Report signal average

In reply to 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.

---
 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
index fb877b5..0ceb552 100644
@@ -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
index e5702f5..f21f701 100644
@@ -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
index 4d6f865..798d9b9 100644
@@ -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
index 18bd0e5..d327918 100644
@@ -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_get(&sta->avg_signal);
 	}
 
 	sinfo->txrate.flags = 0;
net/mac80211/rx.c +1 -0
index 902b03e..34bcc84 100644
@@ -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
index 6d8f897..bed23e1 100644
@@ -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
index 9265aca..84062e2 100644
@@ -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
index 4e78e3f..660987d 100644
@@ -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)
#4 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 5 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.

Isn't that generic EWMA library function making this much more CPU intensive than necessary? I would assume the compiler is not able to optimize the unsigned long division in ewma_add() when the weight value is "hidden" in this way through ewma_init() call. While generic library functions can be nice, it could be useful to have an option for using an inline version of ewma_add that takes in avg->weight as one of the arguments to allow cases like weight=8 here to be implemented using shift right instead of unsigned long division especially when done on hot path..

net/mac80211/rx.c ieee80211_rx_h_sta_process(struct ieee80211_rx_data *rx) · line 1159

Quoted 3 lines
net/mac80211/rx.c +1 -0
@@ -1158,6 +1158,7 @@ ieee80211_rx_h_sta_process(struct ieee80211_rx_data *rx)
 	sta->last_signal = status->signal;
+	ewma_add(&sta->avg_signal, -status->signal);

This one here would be done for every frame received and by using a function call that ends up doing a potentially expensive division.

net/mac80211/sta_info.c struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata, · line 241

Quoted 2 lines
net/mac80211/sta_info.c +1 -0
@@ -241,6 +241,8 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
+	ewma_init(&sta->avg_signal, 1000, 8);

The divisor (weight) is set to 8 here which should allow for quite a bit more efficient ewma_add implementation if it were to be done in a way that makes it easier for the compiler to see what value is being used (e.g., passing this 8 to ewma_add_inline()) to allow shift right to be used..

Or am I missing something here and we have a compiler that is actually able to take care of this kind of optimizations by itself in the current ewma library design? Or is the unsigned long division with the expected weight values going to be fast enough to not justify caring about it even on any of the embedded boards anyway?

Signature · 1 line
Jouni Malinen                                            PGP id EFC895FA
#5 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 38 lines · On Tue November 16 2010 18:37:43 Jouni Malinen wrote:
Quoted 6 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.

Isn't that generic EWMA library function making this much more CPU intensive than necessary? I would assume the compiler is not able to optimize the unsigned long division in ewma_add() when the weight value is "hidden" in this way through ewma_init() call. While generic library functions can be nice, it could be useful to have an option for using an inline version of ewma_add that takes in avg->weight as one of the arguments to allow cases like weight=8 here to be implemented using shift right instead of unsigned long division especially when done on hot path..

Review ieee80211_rx_h_sta_process(struct ieee80211_rx_data · line 1162

Quoted 6 lines
(quoted diff) +1 -0
@@ -1158,6 +1158,7 @@ ieee80211_rx_h_sta_process(struct ieee80211_rx_data
 *rx)
 
 	sta->last_signal = status->signal;
 
+	ewma_add(&sta->avg_signal, -status->signal);

This one here would be done for every frame received and by using a function call that ends up doing a potentially expensive division.

Review struct sta_info *sta_info_alloc(struct · line 241

Quoted 2 lines
(quoted diff) +0 -0
@@ -241,6 +241,8 @@ struct sta_info *sta_info_alloc(struct
 ieee80211_sub_if_data *sdata, +	ewma_init(&sta->avg_signal, 1000, 8);

The divisor (weight) is set to 8 here which should allow for quite a bit more efficient ewma_add implementation if it were to be done in a way that makes it easier for the compiler to see what value is being used (e.g., passing this 8 to ewma_add_inline()) to allow shift right to be used..

Quoted 5 lines

Or am I missing something here and we have a compiler that is actually able to take care of this kind of optimizations by itself in the current ewma library design? Or is the unsigned long division with the expected weight values going to be fast enough to not justify caring about it even on any of the embedded boards anyway?

I understand that this could be more efficient, but if it matters or not - honestly, I don't know. Can a more knowledgeable person than me comment on this?

bruno

maintainer
#6 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 9 lines · Bruno Randolf
Quoted 5 lines

Or am I missing something here and we have a compiler that is actually able to take care of this kind of optimizations by itself in the current ewma library design? Or is the unsigned long division with the expected weight values going to be fast enough to not justify caring about it even on any of the embedded boards anyway?

I understand that this could be more efficient, but if it matters or not - honestly, I don't know. Can a more knowledgeable person than me comment on this?

Yes, it does matter -- think of an embedded MIPS board running at 500MHz and trying to push 11n speeds.

johannes

#7 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 7 lines · Johannes Berg
Quoted 3 lines · Bruno Randolf

I understand that this could be more efficient, but if it matters or not - honestly, I don't know. Can a more knowledgeable person than me comment on this?

Yes, it does matter -- think of an embedded MIPS board running at 500MHz and trying to push 11n speeds.

I assume the number of samples (weight) is the more important tunable. One option is you can require factor to be a power of two that is much larger than weight, then at least you can store factor/weight precomputed and multiply by it instead of doing a divide in ewma_add. Then ewma_get can also just be a shift as well.

Signature · 1 line
Bob Copeland %% www.bobcopeland.com
#8 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 9 lines · On Thu November 18 2010 08:11:18 Bob Copeland wrote:
Quoted 7 lines · Johannes Berg
Quoted 3 lines · Bruno Randolf

I understand that this could be more efficient, but if it matters or not
- honestly, I don't know. Can a more knowledgeable person than me comment on this?

Yes, it does matter -- think of an embedded MIPS board running at 500MHz and trying to push 11n speeds.

OK, I have done tests with a 266MHz x86 board, pushing 30Mbps UDP thru it. It can handle maximum around 18Mbps thuput in both cases, with and without the average. And that is using the ewma function two times (ath5k beacons and signal average). Here are the results of iperf -u -c IP -b 30M -t 120 (2min of 30Mbps UDP):

With average:

0.0-120.4 sec    269 MBytes  18.7 Mbits/sec  0.370 ms 114323/306094 (37%)
0.0-120.4 sec    263 MBytes  18.3 Mbits/sec  0.336 ms 118668/306110 (39%)
0.0-120.4 sec    265 MBytes  18.5 Mbits/sec  0.229 ms 117036/306120 (38%)

Without:

0.0-120.4 sec    267 MBytes  18.6 Mbits/sec  0.385 ms 115457/306123 (38%)
0.0-120.4 sec    267 MBytes  18.6 Mbits/sec  0.374 ms 115868/306063 (38%)
0.0-120.4 sec    261 MBytes  18.2 Mbits/sec  0.566 ms 119603/306112 (39%)

So I conclude that compared to all the other things we do when we receive a packet having one division more or less does not have a huge performance impact.

Quoted 6 lines

I assume the number of samples (weight) is the more important tunable. One option is you can require factor to be a power of two that is much larger than weight, then at least you can store factor/weight precomputed and multiply by it instead of doing a divide in ewma_add. Then ewma_get can also just be a shift as well.

That's a good idea! I will try to improve the code.

bruno

#9 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 1 line · On Nov 19 Bruno Randolf wrote:

Here are the results of iperf -u -c IP -b 30M -t 120

You only showed that CPU utilization is not so high that an effect on network throughput can be seen. You did not measure what the increase in CPU utilization actually was. :-)

Signature · 3 lines
Stefan Richter
-=====-==-=- =-== =--==
http://arcgraph.de/sr/
#10 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 6 lines · On Fri November 19 2010 23:04:51 Stefan Richter wrote:
Quoted 1 line · On Nov 19 Bruno Randolf wrote:

Here are the results of iperf -u -c IP -b 30M -t 120

You only showed that CPU utilization is not so high that an effect on network throughput can be seen. You did not measure what the increase in CPU utilization actually was. :-)

True. That's exactly the point: "CPU utilization is not so high that an effect on network throughput can be seen", which was what people were worrying about. So IMHO: No problem! :) But of course it makes sense to optimize and I'll try to do that in subsequent patches.

bruno

#11 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 7 lines · On Nov 22 Bruno Randolf wrote:
Quoted 3 lines · On Fri November 19 2010 23:04:51 Stefan Richter wrote:

You only showed that CPU utilization is not so high that an effect on network throughput can be seen. You did not measure what the increase in CPU utilization actually was. :-)

True. That's exactly the point: "CPU utilization is not so high that an effect on network throughput can be seen", which was what people were worrying about.

No, people worried about CPU utilization that can be reduced.

Quoted 2 lines

So IMHO: No problem! :) But of course it makes sense to optimize and I'll try to do that in subsequent patches.

Good.

Signature · 3 lines
Stefan Richter
-=====-==-=- =-== =-==-
http://arcgraph.de/sr/
maintainer
#12 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

In reply to Bruno Randolf
Quoted 2 lines · Bruno Randolf

OK, I have done tests with a 266MHz x86 board, pushing 30Mbps UDP thru it. It can handle maximum around 18Mbps thuput in both cases, with and without the

That sounds like you're limited by 11g, not by the CPU ...

johannes

#13 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 6 lines · On Sat November 20 2010 02:52:31 Johannes Berg wrote:
Quoted 3 lines · Bruno Randolf

OK, I have done tests with a 266MHz x86 board, pushing 30Mbps UDP thru it. It can handle maximum around 18Mbps thuput in both cases, with and without the

That sounds like you're limited by 11g, not by the CPU ...

Nope. I forgot to mention that I was testing in A mode and I expect 30Mbps thruput here (I get that consistently on other boards). Also I see my CPU is at 100% with top.

bruno

#14 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

In reply to Bob Copeland
Quoted 11 lines · On Thu November 18 2010 08:11:18 Bob Copeland wrote:

On Wed, Nov 17, 2010 at 11:16 AM, Johannes Berg

Quoted 7 lines · <[email protected]> wrote:
Quoted 3 lines · Bruno Randolf

I understand that this could be more efficient, but if it matters or not
- honestly, I don't know. Can a more knowledgeable person than me comment on this?

Yes, it does matter -- think of an embedded MIPS board running at 500MHz and trying to push 11n speeds.

Quoted 6 lines

I assume the number of samples (weight) is the more important tunable. One option is you can require factor to be a power of two that is much larger than weight, then at least you can store factor/weight precomputed and multiply by it instead of doing a divide in ewma_add. Then ewma_get can also just be a shift as well.

Hmm, maybe I suck in mathemathics, but I don't see a way to do that given the formula:

(((internal * (weight - 1)) + (val * factor)) / weight

bruno

#15 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 4 lines · Bruno Randolf

Hmm, maybe I suck in mathemathics, but I don't see a way to do that given the formula:

(((internal * (weight - 1)) + (val * factor)) / weight

If you assume weight == 2^n, you can write that as:

(((internal << n) - internal) + (val * factor)) >> n

#16 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

In reply to Bruno Randolf
Quoted 4 lines · Bruno Randolf

Hmm, maybe I suck in mathemathics, but I don't see a way to do that given the formula:

(((internal * (weight - 1)) + (val * factor)) / weight

I was thinking something along the lines of:

round = (1 << n) - 1;
(((internal * (weight - 1) + round) >> n) + val) * ((1 << n) / weight)

where (1 << n) is the factor and ((1 << n) / weight) can be precomputed. If you think about it, this is just reciprocal multiplication in fixed- point math with n bits of decimal resolution.

The problem is the shift of the older terms introduces roundoff error, but there are some tricks you can do to maintain bounded error, e.g. shifting by some smaller factor of n and scaling other terms -- in the limit you reinvent floating point and then it's slower than division :)

Signature · 1 line
Bob Copeland %% www.bobcopeland.com
#17 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 11 lines · Bob Copeland
Quoted 4 lines · Bruno Randolf

Hmm, maybe I suck in mathemathics, but I don't see a way to do that given the formula:

(((internal * (weight - 1)) + (val * factor)) / weight

I was thinking something along the lines of:

round = (1 << n) - 1;
(((internal * (weight - 1) + round) >> n) + val) * ((1 << n) / weight)

Quoted 8 lines

where (1 << n) is the factor and ((1 << n) / weight) can be precomputed. If you think about it, this is just reciprocal multiplication in fixed- point math with n bits of decimal resolution.

The problem is the shift of the older terms introduces roundoff error, but there are some tricks you can do to maintain bounded error, e.g. shifting by some smaller factor of n and scaling other terms -- in the limit you reinvent floating point and then it's slower than division :)

Sure, x/y := x/z * z/y, and by picking z := 2^n, we can pre-compute z/y and write x/z using a shift. The problem however is always range vs granularity, you chose to first /z and then *z/y, this avoids some overflow issues but truncates the lower n bits of x.

If you first *z/y and then /z you keep your low bits but risk loosing the top bits to an overflow.

I guess the question is do we really need weights outside of 2^n? If not, you can use the weight := 2^n version. If you do, you get to pick either of the previously mentioned options.

Sadly gcc doesn't sanely support a u128 type, which would be very useful to avoid some of these overflow issues (like we used to use u64 mults for u32 fixed points mults).

#18 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 29 lines · On Sat November 20 2010 08:01:55 Peter Zijlstra wrote:
Quoted 11 lines · Bob Copeland
Quoted 4 lines · Bruno Randolf

Hmm, maybe I suck in mathemathics, but I don't see a way to do that given the formula:

(((internal * (weight - 1)) + (val * factor)) / weight

I was thinking something along the lines of:

round = (1 << n) - 1;
(((internal * (weight - 1) + round) >> n) + val) * ((1 << n) / weight)

Quoted 8 lines

where (1 << n) is the factor and ((1 << n) / weight) can be precomputed. If you think about it, this is just reciprocal multiplication in fixed- point math with n bits of decimal resolution.

The problem is the shift of the older terms introduces roundoff error, but there are some tricks you can do to maintain bounded error, e.g. shifting by some smaller factor of n and scaling other terms -- in the limit you reinvent floating point and then it's slower than division :)

Sure, x/y := x/z * z/y, and by picking z := 2^n, we can pre-compute z/y and write x/z using a shift. The problem however is always range vs granularity, you chose to first /z and then *z/y, this avoids some overflow issues but truncates the lower n bits of x.

If you first *z/y and then /z you keep your low bits but risk loosing the top bits to an overflow.

Quoted 7 lines

I guess the question is do we really need weights outside of 2^n? If not, you can use the weight := 2^n version. If you do, you get to pick either of the previously mentioned options.

Sadly gcc doesn't sanely support a u128 type, which would be very useful to avoid some of these overflow issues (like we used to use u64 mults for u32 fixed points mults).

Thank you all for your help and sorry for following up so late!

I think we don't really need weights outside of 2^n and i'm going to post a patch based on Peter Zijlstra's formula. Thanks again! Would it make sense to have the factor 2^n too, so we can bitshift there too?

bruno

maintainer
#19 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

In reply to Jouni Malinen
Quoted 9 lines · Jouni Malinen
Quoted 5 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.

Isn't that generic EWMA library function making this much more CPU intensive than necessary?

John, is there any reason you completely ignored Jouni's feedback here? This wasn't addressed in v8.

johannes

#20 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 6 lines · Johannes Berg
Quoted 5 lines · Jouni Malinen
Quoted 4 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.

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

This uses the recently added generic EWMA library function.

Isn't that generic EWMA library function making this much more CPU intensive than necessary?

John, is there any reason you completely ignored Jouni's feedback here? This wasn't addressed in v8.

Well, I confess that I didn't fully appreciate Jouni's point.

Is there any reason to presume that Bruno cannot (or will not) improve the performance from here? Do you have any measurement of the actual performance impact?

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.
#21 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

In reply to Bruno Randolf
Quoted 160 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.

---
 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
index fb877b5..0ceb552 100644
@@ -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
index e5702f5..f21f701 100644
@@ -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 +0 -0
index 4d6f865..798d9b9 100644
@@ -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 +0 -0
index 18bd0e5..d327918 100644
@@ -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_get(&sta->avg_signal); }

       sinfo->txrate.flags = 0;

net/mac80211/rx.c +1 -0
index 902b03e..34bcc84 100644
@@ -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
index 6d8f897..bed23e1 100644
@@ -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
index 9265aca..84062e2 100644
@@ -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 +0 -0
index 4e78e3f..660987d 100644

net/wireless/nl80211.c static int nl80211_send_station(struct sk_buff *msg, u32 pid, u32 seq, · line 1849

Quoted 9 lines
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)

Someone's probably already on this, but these signal averaging patches have broken compat-wireless. Seeing as how this is a compat-wireless issue, I trimmed the recipients. compat-wireless-2010-11-19 under 2.6.32.23 fails with the following error:

In file included from compat-wireless-2010-11-19/drivers/net/wireless/ath/ath5k/caps.c:24:
compat-wireless-2010-11-19/drivers/net/wireless/ath/ath5k/ath5k.h:28:27:
error: linux/average.h: No such file or directory
In file included from compat-wireless-2010-11-19/drivers/net/wireless/ath/ath5k/caps.c:24:
compat-wireless-2010-11-19/drivers/net/wireless/ath/ath5k/ath5k.h:1106:
error: field ‘ah_beacon_rssi_avg’ has incomplete type

maintainer
#22 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

In reply to Bruno Randolf
Quoted 5 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.

John, please revert this patch ASAP -- it completely messed up some ABI, and the performance discussion is also not over yet.

johannes

#23 lore raw

Re: [PATCH v7 3/3] nl80211/mac80211: Report signal average

Quoted 9 lines · Johannes Berg
Quoted 5 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.

John, please revert this patch ASAP -- it completely messed up some ABI, and the performance discussion is also not over yet.

Just so I understand: Is the ABI issue because the netlink enum was added in the middle, or are there other ABI problems?

Thanks,
Ben

Signature · 2 lines
Ben Greear <[email protected]>
Candela Technologies Inc  http://www.candelatech.com