[PATCH 1/2] average: provide macro to create static EWMA

[PATCH 1/2] average: provide macro to create static EWMA

[Johannes Berg]

From: Johannes Berg <johannes.berg@intel.com>

Having the EWMA parameters stored in the runtime struct imposes
memory requirements for the constant values that could just be
inlined in the code. This particularly makes sense if there are
a lot of such structs, for example in mac80211 in the station
table where each station has a number of these in an array, and
there can be many stations.

Provide a macro DECLARE_EWMA() that declares the necessary struct
and inline functions to access it with the parameters hard-coded;
using this also means the user no longer needs to 'select AVERAGE'
as it's entirely self-contained.

In the mac80211 case, on x86-64, this actually slightly *reduces*
code size, while also saving 80 bytes of runtime memory per sta.

Signed-off-by: Johannes Berg <johannes.berg@intel.com>
---
As the next patch relies on this, I'll take this through my tree
unless I hear objections.
---
 include/linux/average.h | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/include/linux/average.h b/include/linux/average.h
index c6028fd742c1..802adeab7037 100644
--- a/include/linux/average.h
+++ b/include/linux/average.h
@@ -27,4 +27,43 @@ static inline unsigned long ewma_read(const struct ewma *avg)
 	return avg->internal >> avg->factor;
 }
 
+#define DECLARE_EWMA(name, _factor, _weight)				\
+	struct ewma_##name {						\
+		unsigned long internal;					\
+	};								\
+	static inline void ewma_##name##_init(struct ewma_##name *e)	\
+	{								\
+		BUILD_BUG_ON(!__builtin_constant_p(_factor));		\
+		BUILD_BUG_ON(!__builtin_constant_p(_weight));		\
+		BUILD_BUG_ON(!is_power_of_2(_factor));			\
+		BUILD_BUG_ON(!is_power_of_2(_weight));			\
+		e->internal = 0;					\
+	}								\
+	static inline unsigned long					\
+	ewma_##name##_read(struct ewma_##name *e)			\
+	{								\
+		BUILD_BUG_ON(!__builtin_constant_p(_factor));		\
+		BUILD_BUG_ON(!__builtin_constant_p(_weight));		\
+		BUILD_BUG_ON(!is_power_of_2(_factor));			\
+		BUILD_BUG_ON(!is_power_of_2(_weight));			\
+		return e->internal >> ilog2(_factor);			\
+	}								\
+	static inline void ewma_##name##_add(struct ewma_##name *e,	\
+					     unsigned long val)		\
+	{								\
+		unsigned long internal = ACCESS_ONCE(e->internal);	\
+		unsigned long weight = ilog2(_weight);			\
+		unsigned long factor = ilog2(_factor);			\
+									\
+		BUILD_BUG_ON(!__builtin_constant_p(_factor));		\
+		BUILD_BUG_ON(!__builtin_constant_p(_weight));		\
+		BUILD_BUG_ON(!is_power_of_2(_factor));			\
+		BUILD_BUG_ON(!is_power_of_2(_weight));			\
+									\
+		ACCESS_ONCE(e->internal) = internal ?			\
+			(((internal << weight) - internal) +		\
+				(val << factor)) >> weight :		\
+			(val << factor);				\
+	}
+
 #endif /* _LINUX_AVERAGE_H */
-- 
2.1.4

[PATCH 2/2] mac80211: use DECLARE_EWMA

[Johannes Berg]

From: Johannes Berg <johannes.berg-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>

Instead of using the out-of-line average calculation, use the new
DECLARE_EWMA() macro to declare a signal EWMA, and use that.

This actually *reduces* the code size slightly (on x86-64) while
also reducing the station info size by 80 bytes.

Signed-off-by: Johannes Berg <johannes.berg-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>
---
 net/mac80211/Kconfig      | 1 -
 net/mac80211/mesh_plink.c | 2 +-
 net/mac80211/rx.c         | 4 ++--
 net/mac80211/sta_info.c   | 9 +++++----
 net/mac80211/sta_info.h   | 6 ++++--
 5 files changed, 12 insertions(+), 10 deletions(-)

diff --git a/net/mac80211/Kconfig b/net/mac80211/Kconfig
index 086de496a4c1..3891cbd2adea 100644
--- a/net/mac80211/Kconfig
+++ b/net/mac80211/Kconfig
@@ -7,7 +7,6 @@ config MAC80211
 	select CRYPTO_CCM
 	select CRYPTO_GCM
 	select CRC32
-	select AVERAGE
 	---help---
 	  This option enables the hardware independent IEEE 802.11
 	  networking stack.
diff --git a/net/mac80211/mesh_plink.c b/net/mac80211/mesh_plink.c
index 1a7d98398626..6fa6606fce55 100644
--- a/net/mac80211/mesh_plink.c
+++ b/net/mac80211/mesh_plink.c
@@ -64,7 +64,7 @@ static bool rssi_threshold_check(struct ieee80211_sub_if_data *sdata,
 {
 	s32 rssi_threshold = sdata->u.mesh.mshcfg.rssi_threshold;
 	return rssi_threshold == 0 ||
-	       (sta && (s8) -ewma_read(&sta->avg_signal) > rssi_threshold);
+	       (sta && (s8) -ewma_signal_read(&sta->avg_signal) > rssi_threshold);
 }
 
 /**
diff --git a/net/mac80211/rx.c b/net/mac80211/rx.c
index 3a1462810c8e..e3cff02bde07 100644
--- a/net/mac80211/rx.c
+++ b/net/mac80211/rx.c
@@ -1428,7 +1428,7 @@ ieee80211_rx_h_sta_process(struct ieee80211_rx_data *rx)
 	sta->rx_bytes += rx->skb->len;
 	if (!(status->flag & RX_FLAG_NO_SIGNAL_VAL)) {
 		sta->last_signal = status->signal;
-		ewma_add(&sta->avg_signal, -status->signal);
+		ewma_signal_add(&sta->avg_signal, -status->signal);
 	}
 
 	if (status->chains) {
@@ -1440,7 +1440,7 @@ ieee80211_rx_h_sta_process(struct ieee80211_rx_data *rx)
 				continue;
 
 			sta->chain_signal_last[i] = signal;
-			ewma_add(&sta->chain_signal_avg[i], -signal);
+			ewma_signal_add(&sta->chain_signal_avg[i], -signal);
 		}
 	}
 
diff --git a/net/mac80211/sta_info.c b/net/mac80211/sta_info.c
index 9da7d2bc271a..dd9541c51de1 100644
--- a/net/mac80211/sta_info.c
+++ b/net/mac80211/sta_info.c
@@ -341,9 +341,9 @@ struct sta_info *sta_info_alloc(struct ieee80211_sub_if_data *sdata,
 
 	ktime_get_ts(&uptime);
 	sta->last_connected = uptime.tv_sec;
-	ewma_init(&sta->avg_signal, 1024, 8);
+	ewma_signal_init(&sta->avg_signal);
 	for (i = 0; i < ARRAY_SIZE(sta->chain_signal_avg); i++)
-		ewma_init(&sta->chain_signal_avg[i], 1024, 8);
+		ewma_signal_init(&sta->chain_signal_avg[i]);
 
 	if (local->ops->wake_tx_queue) {
 		void *txq_data;
@@ -1899,7 +1899,8 @@ void sta_set_sinfo(struct sta_info *sta, struct station_info *sinfo)
 		}
 
 		if (!(sinfo->filled & BIT(NL80211_STA_INFO_SIGNAL_AVG))) {
-			sinfo->signal_avg = (s8) -ewma_read(&sta->avg_signal);
+			sinfo->signal_avg =
+				(s8) -ewma_signal_read(&sta->avg_signal);
 			sinfo->filled |= BIT(NL80211_STA_INFO_SIGNAL_AVG);
 		}
 	}
@@ -1914,7 +1915,7 @@ void sta_set_sinfo(struct sta_info *sta, struct station_info *sinfo)
 		for (i = 0; i < ARRAY_SIZE(sinfo->chain_signal); i++) {
 			sinfo->chain_signal[i] = sta->chain_signal_last[i];
 			sinfo->chain_signal_avg[i] =
-				(s8) -ewma_read(&sta->chain_signal_avg[i]);
+				(s8) -ewma_signal_read(&sta->chain_signal_avg[i]);
 		}
 	}
 
diff --git a/net/mac80211/sta_info.h b/net/mac80211/sta_info.h
index 6dcb33484eac..1c5333448bde 100644
--- a/net/mac80211/sta_info.h
+++ b/net/mac80211/sta_info.h
@@ -318,6 +318,8 @@ struct mesh_sta {
 	unsigned int fail_avg;
 };
 
+DECLARE_EWMA(signal, 1024, 8)
+
 /**
  * struct sta_info - STA information
  *
@@ -460,12 +462,12 @@ struct sta_info {
 	unsigned long rx_fragments;
 	unsigned long rx_dropped;
 	int last_signal;
-	struct ewma avg_signal;
+	struct ewma_signal avg_signal;
 	int last_ack_signal;
 
 	u8 chains;
 	s8 chain_signal_last[IEEE80211_MAX_CHAINS];
-	struct ewma chain_signal_avg[IEEE80211_MAX_CHAINS];
+	struct ewma_signal chain_signal_avg[IEEE80211_MAX_CHAINS];
 
 	/* Plus 1 for non-QoS frames */
 	__le16 last_seq_ctrl[IEEE80211_NUM_TIDS + 1];
-- 
2.1.4

--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 1/2] average: provide macro to create static EWMA

[David Miller]

From: Johannes Berg <johannes-cdvu00un1VgdHxzADdlk8Q@public.gmane.org>
Date: Thu, 13 Aug 2015 11:11:48 +0200

> From: Johannes Berg <johannes.berg-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>
> 
> Having the EWMA parameters stored in the runtime struct imposes
> memory requirements for the constant values that could just be
> inlined in the code. This particularly makes sense if there are
> a lot of such structs, for example in mac80211 in the station
> table where each station has a number of these in an array, and
> there can be many stations.
> 
> Provide a macro DECLARE_EWMA() that declares the necessary struct
> and inline functions to access it with the parameters hard-coded;
> using this also means the user no longer needs to 'select AVERAGE'
> as it's entirely self-contained.
> 
> In the mac80211 case, on x86-64, this actually slightly *reduces*
> code size, while also saving 80 bytes of runtime memory per sta.
> 
> Signed-off-by: Johannes Berg <johannes.berg-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>
> ---
> As the next patch relies on this, I'll take this through my tree
> unless I hear objections.

This looks fine to me.
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH 1/2] average: provide macro to create static EWMA

[Johannes Berg]

On Thu, 2015-08-13 at 17:26 -0700, David Miller wrote:
> From: Johannes Berg <johannes-cdvu00un1VgdHxzADdlk8Q@public.gmane.org>
> Date: Thu, 13 Aug 2015 11:11:48 +0200
> 
> > From: Johannes Berg <johannes.berg-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>
> > 
> > Having the EWMA parameters stored in the runtime struct imposes
> > memory requirements for the constant values that could just be
> > inlined in the code. This particularly makes sense if there are
> > a lot of such structs, for example in mac80211 in the station
> > table where each station has a number of these in an array, and
> > there can be many stations.
> > 
> > Provide a macro DECLARE_EWMA() that declares the necessary struct
> > and inline functions to access it with the parameters hard-coded;
> > using this also means the user no longer needs to 'select AVERAGE'
> > as it's entirely self-contained.
> > 
> > In the mac80211 case, on x86-64, this actually slightly *reduces*
> > code size, while also saving 80 bytes of runtime memory per sta.
> > 
> > Signed-off-by: Johannes Berg <johannes.berg-ral2JQCrhuEAvxtiuMwx3w@public.gmane.org>
> > ---
> > As the next patch relies on this, I'll take this through my tree
> > unless I hear objections.
> 
> This looks fine to me.
> 

Thanks, I've applied both.

johannes
--
To unsubscribe from this list: send the line "unsubscribe linux-wireless" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

GCOV_PROFILE_ALL breaks BUILD_BUG_ON(!is_power_of_2(8))

[Johannes Berg]

+linux-kernel

> +#define DECLARE_EWMA(name, _factor, _weight)> 	> 	> 	> 	> \
> +> 	> struct ewma_##name {> 	> 	> 	> 	> 	> 	> \
> +> 	> 	> unsigned long internal;> 	> 	> 	> 	> 	> \
> +> 	> };> 	> 	> 	> 	> 	> 	> 	> 	> \
> +> 	> static inline void ewma_##name##_init(struct ewma_##name *e)> 	> \
> +> 	> {> 	> 	> 	> 	> 	> 	> 	> 	> \
> +> 	> 	> BUILD_BUG_ON(!__builtin_constant_p(_factor));> 	> 	> \
> +> 	> 	> BUILD_BUG_ON(!__builtin_constant_p(_weight));> 	> 	> \
> +> 	> 	> BUILD_BUG_ON(!is_power_of_2(_factor));> 	> 	> 	> \
> +> 	> 	> BUILD_BUG_ON(!is_power_of_2(_weight));> 	> 	> 	> \
> 

So this seemed fine to me, but for some reason the compiler is saying
the BUILD_BUG_ON(!is_power_of_2(x)) fails, if and only if (!)
CONFIG_GCOV_PROFILE_ALL is enabled, which seems to boil down to the
compiler option -fprofile-arcs.

I'm going to replace this with just the code itself, i.e.

                /* both must be a power of 2 */
                BUILD_BUG_ON(_factor & (_factor - 1));
                BUILD_BUG_ON(_weight & (_weight - 1));

but should I have expected this?

johannes

Re: GCOV_PROFILE_ALL breaks BUILD_BUG_ON(!is_power_of_2(8))

[Michal Kubecek]

On Fri, Aug 14, 2015 at 10:29:04AM +0200, Johannes Berg wrote:
> +linux-kernel
> 
> > +#define DECLARE_EWMA(name, _factor, _weight)> 	> 	> 	> 	> \
> > +> 	> struct ewma_##name {> 	> 	> 	> 	> 	> 	> \
> > +> 	> 	> unsigned long internal;> 	> 	> 	> 	> 	> \
> > +> 	> };> 	> 	> 	> 	> 	> 	> 	> 	> \
> > +> 	> static inline void ewma_##name##_init(struct ewma_##name *e)> 	> \
> > +> 	> {> 	> 	> 	> 	> 	> 	> 	> 	> \
> > +> 	> 	> BUILD_BUG_ON(!__builtin_constant_p(_factor));> 	> 	> \
> > +> 	> 	> BUILD_BUG_ON(!__builtin_constant_p(_weight));> 	> 	> \
> > +> 	> 	> BUILD_BUG_ON(!is_power_of_2(_factor));> 	> 	> 	> \
> > +> 	> 	> BUILD_BUG_ON(!is_power_of_2(_weight));> 	> 	> 	> \
> > 
> 
> So this seemed fine to me, but for some reason the compiler is saying
> the BUILD_BUG_ON(!is_power_of_2(x)) fails, if and only if (!)
> CONFIG_GCOV_PROFILE_ALL is enabled, which seems to boil down to the
> compiler option -fprofile-arcs.
> 
> I'm going to replace this with just the code itself, i.e.
> 
>                 /* both must be a power of 2 */
>                 BUILD_BUG_ON(_factor & (_factor - 1));
>                 BUILD_BUG_ON(_weight & (_weight - 1));
> 
> but should I have expected this?

It might have something to do with the fact that is_power_of_2() being
an inline function, perhaps with this compiler option it translates to
something that can't be used in the context BUILD_BUG_ON() uses it in.

There is a BUILD_BUG_ON_NOT_POWER_OF_2() macro you could use.

                                                        Michal Kubecek

Re: GCOV_PROFILE_ALL breaks BUILD_BUG_ON(!is_power_of_2(8))

[Johannes Berg]

On Fri, 2015-08-14 at 11:00 +0200, Michal Kubecek wrote:

> > but should I have expected this?
> 
> It might have something to do with the fact that is_power_of_2() 
> being an inline function, perhaps with this compiler option it 
> translates to something that can't be used in the context 
> BUILD_BUG_ON() uses it in.

Evidently, yeah.

> There is a BUILD_BUG_ON_NOT_POWER_OF_2() macro you could use.
> 

Good point, I'll do that, thanks.

johannes