NET: Generic network statistics/estimator

Dave,

The following patchset introduces generic network statistics for netlink users. It uses nested TLV which prevents further compatibility problems when introducing new statistics. Backward compatibility to existing TLV types TCA_STATS and TCA_XSTATS is ensured but can be easly removed once it is no longer needed. Therefore prior users of struct tc_stats can be converted to this API and existing userspace applications will not notice a difference while converted applications can use the new extendable statistic interface.

Generic network statistics API for netlink users.

@@ -0,0 +1,45 @@
+#ifndef __NET_GEN_STATS_H
+#define __NET_GEN_STATS_H
+
+#include <linux/gen_stats.h>
+#include <linux/socket.h>
+#include <linux/rtnetlink.h>
+#include <linux/pkt_sched.h>
+
+struct gnet_dump
+{
+	spinlock_t *      lock;
+	struct sk_buff *  skb;
+	struct rtattr *   tail;
+
+	/* Backward compatability */
+	int               compat_tc_stats;
+	int               compat_xstats;
+	struct rtattr *   xstats;
+	struct tc_stats   tc_stats;
+};
+
+extern int gnet_stats_start_copy(struct sk_buff *skb, int type,
+				 spinlock_t *lock, struct gnet_dump *d);
+
+extern int gnet_stats_start_copy_compat(struct sk_buff *skb, int type,
+					int tc_stats_type,int xstats_type,
+					spinlock_t *lock, struct gnet_dump *d);
+
+extern int gnet_stats_copy_basic(struct gnet_dump *d,
+				 struct gnet_stats_basic *b);
+extern int gnet_stats_copy_rate_est(struct gnet_dump *d,
+				    struct gnet_stats_rate_est *r);
+extern int gnet_stats_copy_queue(struct gnet_dump *d,
+				 struct gnet_stats_queue *q);
+extern int gnet_stats_copy_app(struct gnet_dump *d, void *st, int len);
+
+extern int gnet_stats_finish_copy(struct gnet_dump *d);
+
+extern int gen_new_estimator(struct gnet_stats_basic *bstats,
+			     struct gnet_stats_rate_est *rate_est,
+			     spinlock_t *stats_lock, struct rtattr *opt);
+extern void gen_kill_estimator(struct gnet_stats_basic *bstats,
+			       struct gnet_stats_rate_est *rate_est);
+
+#endif

Introduces a generic rate estimator based on timers. Patch is based on Jamal's patch and adapted to the new generic network statistics API.

@@ -47,4 +47,16 @@
 	__u32	requeues;
 	__u32	overlimits;
 };
+
+/**
+ * @interval: sampling period
+ * @ewma_log: the log of measurement window weight
+ */
+struct gnet_estimator
+{
+	signed char	interval;
+	unsigned char	ewma_log;
+};
+
+
 #endif /* __LINUX_GEN_STATS_H */

First, how does this new thing ever get built into the tree?

Second:

* David S. Miller <[email protected]> 2004-10-03 16:14

Once we converted all Qdiscs to use the new splitted up stats structs we can replace all calls to qdisc_new_estimator with gen_new_estimator.

I already have a patch in my tree which does this but I want to test it a little longer before submitting it. It also involves a change to struct Qdisc and Qdisc_ops which means that we break all qdiscs not in the tree. Is this acceptable?

Benefit would be:
No compatibility mess anymore when introducing new stats for both, all qdiscs or just a single one.

This was taken over from net/sched/estimator.c so I guess there was no person ever using the rate estimator on such an arch ;)

Can we simply remove the check?

It allocates space for the TLV header in the skb, will result in an empty header. Nested TLVs are appened to it and the header is filled out afterwards once the size of all nested TLVs are known.

The granularity of the timing is dependent on this - 250msec increments. Find a common demonitor for all Hz values which results in something along 200ms range and we should be set.

cheers,
jamal

* jamal <[email protected]> 2004-10-03 21:16

I don't think this is possible:

octave:1> gcd([1000,1024,1200,200,128,100,32,50,122,24]) ans = 2

Why not let userspace provide it? ticks/usec and usec/ticks are exported via /proc/net/psched.

Easier to define a compile time constant in the kernel.
What you need is to replace the HZ/4 in the creation and execution of the timer with a constant. And that the value of said constant would be preferably in the 250ms range.

If you fix this also would be worth fixing the ones in net/sched/estimator.c

cheers,
jamal

* jamal <[email protected]> 2004-10-04 09:24

HZ/4 == 250ms works except for HZ=122 (~246ms) and HZ=50 (~240ms). I don't know how you think it is possible to find a constant around 250ms which works for all HZ values. The problem gets even minor if we do (HZ<<idx)/4 instead of (HZ/4)<<idx in which the inaccuracy only happens if idx is 0, i.e. interval == -2.

is that bad to let those have a slight different innacurate value? BTW wasnt there a jiffies2ms converter somewhere that we could use? I thought i saw something posted of that nature recently.

There should really be no difference between the two;-> you realize /4 is merely <<2 ?

cheers,
jamal

* jamal <[email protected]> 2004-10-04 10:59

I don't see this as a problem, I think the timers will be more inacurate anyway.

#define PSCHED_US2JIFFIE(delay)
#define PSCHED_JIFFIE2US(delay)

but we don't have half a jiffie ;) The only way to make it accurate in the case of 122 and 50 would be to set timer_expires based on a flip-flop adding HZ/4 and (HZ/4)+1 repeaditly and this only works if HZ%2==0.

I would be fine using PSCHED_ because the user can decide accuracy over performance and vice versa. It would make the code dependant on sch_api.c though.

Oh yes there is: HZ=50, idx=2

(HZ/4)<<idx:
octave:8> 50/4
ans = 12.500
octave:9> dec2bin(12)
ans = 1100
octave:10> bin2dec('110000')
ans = 48

(HZ<<idx)/4:
octave:11> dec2bin(50)
ans = 110010
octave:12> bin2dec('11001000')
ans = 200
octave:13> 200/4
ans = 50

It avoids carrying on the inaccuracy, of course this only works because (2*HZ)%4==0 is true for all existing HZ values. Or do I misundstand the compiler and it's all in floating points?

Resend of generic rate estimator patch. The HZ%4 check has been removed and jiffies calculation has been adapted to avoid carrying on unacuracy. Small variance for 250ms interval happens with HZ values of 122 and 50.

I suggest to apply this and think about using psched tick<->usec code later because it wouldn't really solve any problem but would be nice to have.

Introduces a generic rate estimator based on timers. Patch is based on Jamal's patch and adapted to the new generic network statistics API.

@@ -47,4 +47,16 @@
 	__u32	requeues;
 	__u32	overlimits;
 };
+
+/**
+ * @interval: sampling period
+ * @ewma_log: the log of measurement window weight
+ */
+struct gnet_estimator
+{
+	signed char	interval;
+	unsigned char	ewma_log;
+};
+
+
 #endif /* __LINUX_GEN_STATS_H */

Ok, I did some test as well here - and the change you made gives better results.
Can you also change net/sched/estimator.c to behave the same way? BTW, anything else that changed since last time other than the timer adjustment ?

cheers,
jamal

* jamal <[email protected]> 2004-10-04 16:07

Sure, will do.

No, I removed the check, adjusted the timer calculation and updated the notes in the documentation.

* David S. Miller <[email protected]> 2004-10-03 16:14

I misunderstood you before and didn't realize I missed to diff the Makefile part. Sorry about that.

@@ -2,7 +2,7 @@
 # Makefile for the Linux networking core.
 #
 
-obj-y := sock.o skbuff.o iovec.o datagram.o stream.o scm.o
+obj-y := sock.o skbuff.o iovec.o datagram.o stream.o scm.o gen_stats.o gen_estimator.o
 
 obj-$(CONFIG_SYSCTL) += sysctl_net_core.o
 

Ok, so I combined all of the work into one big patch and checked it into my tree as follows:

# This is a BitKeeper generated diff -Nru style patch. #
# ChangeSet
# 2004/10/05 13:38:47-07:00 [email protected]
# [NET]: Generic network statistics/estimator
#
# Work done by Thomas Graf <[email protected]> and
# Jamal Hadi Salim <[email protected]>
#

#   The following patchset introduces generic network statistics for
#   netlink users. It uses nested TLV which prevents further compatibility
#   problems when introducing new statistics. Backward compatibility to
#   existing TLV types TCA_STATS and TCA_XSTATS is ensured but can be
#   easly removed once it is no longer needed. Therefore prior users of
#   struct tc_stats can be converted to this API and existing userspace
#   applications will not notice a difference while converted applications
#   can use the new extendable statistic interface.
#   
#   Changes:
#   - Add generic network statistics API for netlink users.
#   - Introduces a generic rate estimator based on timers. Patch is based

# on Jamals patch and adapted to the new generic network statistics
# API.
# - Add documentation of generic network statistics and estimator API.
#

#   Signed-off-by: Thomas Graf <[email protected]>
#   Signed-off-by: Jamal Hadi Salim <[email protected]>
#   Signed-off-by: David S. Miller <[email protected]>

#
# net/core/Makefile
# 2004/10/05 13:36:58-07:00 [email protected] +1 -1
# [NET]: Generic network statistics/estimator
#

# net/core/gen_stats.c
#   2004/10/05 13:36:52-07:00 [email protected] +132 -0
#   [NET]: Generic network statistics/estimator
# 
# net/core/gen_estimator.c
#   2004/10/05 13:36:52-07:00 [email protected] +204 -0
#   [NET]: Generic network statistics/estimator
# 
# include/net/gen_stats.h
#   2004/10/05 13:36:52-07:00 [email protected] +45 -0
#   [NET]: Generic network statistics/estimator
# 
# Documentation/networking/gen_stats.txt
#   2004/10/05 13:36:52-07:00 [email protected] +117 -0
#   [NET]: Generic network statistics/estimator
# 
# net/core/gen_stats.c
#   2004/10/05 13:36:52-07:00 [email protected] +0 -0
#   BitKeeper file /disk1/BK/net-2.6/net/core/gen_stats.c
# 
# net/core/gen_estimator.c
#   2004/10/05 13:36:52-07:00 [email protected] +0 -0
#   BitKeeper file /disk1/BK/net-2.6/net/core/gen_estimator.c
# 
# include/net/gen_stats.h
#   2004/10/05 13:36:52-07:00 [email protected] +0 -0
#   BitKeeper file /disk1/BK/net-2.6/include/net/gen_stats.h
# 
# include/linux/gen_stats.h
#   2004/10/05 13:36:51-07:00 [email protected] +62 -0
#   [NET]: Generic network statistics/estimator
# 
# Documentation/networking/gen_stats.txt
#   2004/10/05 13:36:52-07:00 [email protected] +0 -0
#   BitKeeper file /disk1/BK/net-2.6/Documentation/networking/gen_stats.txt
# 
# include/linux/gen_stats.h
#   2004/10/05 13:36:51-07:00 [email protected] +0 -0
#   BitKeeper file /disk1/BK/net-2.6/include/linux/gen_stats.h
# 
diff -Nru a/Documentation/networking/gen_stats.txt b/Documentation/networking/gen_stats.txt
--- /dev/null	Wed Dec 31 16:00:00 196900
+++ b/Documentation/networking/gen_stats.txt	2004-10-05 13:41:59 -07:00
@@ -0,0 +1,117 @@
+Generic networking statistics for netlink users
+======================================================================
+
+Statistic counters are grouped into structs:
+
+Struct               TLV type              Description
+----------------------------------------------------------------------
+gnet_stats_basic     TCA_STATS_BASIC       Basic statistics
+gnet_stats_rate_est  TCA_STATS_RATE_EST    Rate estimator
+gnet_stats_queue     TCA_STATS_QUEUE       Queue statistics
+none                 TCA_STATS_APP         Application specific
+
+
+Collecting:
+-----------
+
+Declare the statistic structs you need:
+struct mystruct {
+	struct gnet_stats_basic	bstats;
+	struct gnet_stats_queue	qstats;
+	...
+};
+
+Update statistics:
+mystruct->tstats.packet++;
+mystruct->qstats.backlog += skb->pkt_len;
+
+
+Export to userspace (Dump):
+---------------------------
+
+my_dumping_routine(struct sk_buff *skb, ...)
+{
+	struct gnet_dump dump;
+
+	if (gnet_stats_start_copy(skb, TCA_STATS2, &mystruct->lock, &dump) < 0)
+		goto rtattr_failure;
+
+	if (gnet_stats_copy_basic(&dump, &mystruct->bstats) < 0 ||
+	    gnet_stats_copy_queue(&dump, &mystruct->qstats) < 0 ||
+		gnet_stats_copy_app(&dump, &xstats, sizeof(xstats)) < 0)
+		goto rtattr_failure;
+
+	if (gnet_stats_finish_copy(&dump) < 0)
+		goto rtattr_failure;
+	...
+}
+
+TCA_STATS/TCA_XSTATS backward compatibility:
+--------------------------------------------
+
+Prior users of struct tc_stats and xstats can maintain backward
+compatibility by calling the compat wrappers to keep providing the
+existing TLV types.
+
+my_dumping_routine(struct sk_buff *skb, ...)
+{
+    if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
+		TCA_XSTATS, &mystruct->lock, &dump) < 0)
+		goto rtattr_failure;
+	...
+}
+
+A struct tc_stats will be filled out during gnet_stats_copy_* calls
+and appended to the skb. TCA_XSTATS is provided if gnet_stats_copy_app
+was called.
+
+
+Locking:
+--------
+
+Locks are taken before writing and released once all statistics have
+been written. Locks are always released in case of an error. You
+are responsible for making sure that the lock is initialized.
+
+
+Rate Estimator:
+--------------
+
+0) Prepare an estimator attribute. Most likely this would be in user
+   space. The value of this TLV should contain a tc_estimator structure.
+   As usual, such a TLV nees to be 32 bit aligned and therefore the
+   length needs to be appropriately set etc. The estimator interval
+   and ewma log need to be converted to the appropriate values.
+   tc_estimator.c::tc_setup_estimator() is advisable to be used as the
+   conversion routine. It does a few clever things. It takes a time
+   interval in microsecs, a time constant also in microsecs and a struct
+   tc_estimator to  be populated. The returned tc_estimator can be
+   transported to the kernel.  Transfer such a structure in a TLV of type
+   TCA_RATE to your code in the kernel.
+
+In the kernel when setting up:
+1) make sure you have basic stats and rate stats setup first.
+2) make sure you have initialized stats lock that is used to setup such
+   stats.
+3) Now initialize a new estimator:
+
+   int ret = gen_new_estimator(my_basicstats,my_rate_est_stats,
+       mystats_lock, attr_with_tcestimator_struct);
+
+   if ret == 0
+       success
+   else
+       failed
+
+From now on, everytime you dump my_rate_est_stats it will contain
+uptodate info.
+
+Once you are done, call gen_kill_estimator(my_basicstats,
+my_rate_est_stats) Make sure that my_basicstats and my_rate_est_stats
+are still valid (i.e still exist) at the time of making this call.
+
+
+Authors:
+--------
+Thomas Graf <[email protected]>
+Jamal Hadi Salim <[email protected]>
diff -Nru a/include/linux/gen_stats.h b/include/linux/gen_stats.h
--- /dev/null	Wed Dec 31 16:00:00 196900
+++ b/include/linux/gen_stats.h	2004-10-05 13:41:59 -07:00
@@ -0,0 +1,62 @@
+#ifndef __LINUX_GEN_STATS_H
+#define __LINUX_GEN_STATS_H
+
+#include <linux/types.h>
+
+enum {
+	TCA_STATS_UNSPEC,
+	TCA_STATS_BASIC,
+	TCA_STATS_RATE_EST,
+	TCA_STATS_QUEUE,
+	TCA_STATS_APP,
+	__TCA_STATS_MAX,
+};
+#define TCA_STATS_MAX (__TCA_STATS_MAX - 1)
+
+/**
+ * @bytes: number of seen bytes
+ * @packets: number of seen packets
+ */
+struct gnet_stats_basic
+{
+	__u64	bytes;
+	__u32	packets;
+};
+
+/**
+ * @bps: current byte rate
+ * @pps: current packet rate
+ */
+struct gnet_stats_rate_est
+{
+	__u32	bps;
+	__u32	pps;
+};
+
+/**
+ * @qlen: queue length
+ * @backlog: backlog size of queue
+ * @drops: number of dropped packets
+ * @requeues: number of requeues
+ */
+struct gnet_stats_queue
+{
+	__u32	qlen;
+	__u32	backlog;
+	__u32	drops;
+	__u32	requeues;
+	__u32	overlimits;
+};
+
+/**
+ * @interval: sampling period
+ * @ewma_log: the log of measurement window weight
+ */
+struct gnet_estimator
+{
+	signed char	interval;
+	unsigned char	ewma_log;
+};
+
+
+#endif /* __LINUX_GEN_STATS_H */
diff -Nru a/include/net/gen_stats.h b/include/net/gen_stats.h
--- /dev/null	Wed Dec 31 16:00:00 196900
+++ b/include/net/gen_stats.h	2004-10-05 13:41:59 -07:00
@@ -0,0 +1,45 @@
+#ifndef __NET_GEN_STATS_H
+#define __NET_GEN_STATS_H
+
+#include <linux/gen_stats.h>
+#include <linux/socket.h>
+#include <linux/rtnetlink.h>
+#include <linux/pkt_sched.h>
+
+struct gnet_dump
+{
+	spinlock_t *      lock;
+	struct sk_buff *  skb;
+	struct rtattr *   tail;
+
+	/* Backward compatability */
+	int               compat_tc_stats;
+	int               compat_xstats;
+	struct rtattr *   xstats;
+	struct tc_stats   tc_stats;
+};
+
+extern int gnet_stats_start_copy(struct sk_buff *skb, int type,
+				 spinlock_t *lock, struct gnet_dump *d);
+
+extern int gnet_stats_start_copy_compat(struct sk_buff *skb, int type,
+					int tc_stats_type,int xstats_type,
+					spinlock_t *lock, struct gnet_dump *d);
+
+extern int gnet_stats_copy_basic(struct gnet_dump *d,
+				 struct gnet_stats_basic *b);
+extern int gnet_stats_copy_rate_est(struct gnet_dump *d,
+				    struct gnet_stats_rate_est *r);
+extern int gnet_stats_copy_queue(struct gnet_dump *d,
+				 struct gnet_stats_queue *q);
+extern int gnet_stats_copy_app(struct gnet_dump *d, void *st, int len);
+
+extern int gnet_stats_finish_copy(struct gnet_dump *d);
+
+extern int gen_new_estimator(struct gnet_stats_basic *bstats,
+			     struct gnet_stats_rate_est *rate_est,
+			     spinlock_t *stats_lock, struct rtattr *opt);
+extern void gen_kill_estimator(struct gnet_stats_basic *bstats,
+			       struct gnet_stats_rate_est *rate_est);
+
+#endif
diff -Nru a/net/core/Makefile b/net/core/Makefile
--- a/net/core/Makefile	2004-10-05 13:41:59 -07:00
+++ b/net/core/Makefile	2004-10-05 13:41:59 -07:00
@@ -2,7 +2,7 @@
 # Makefile for the Linux networking core.
 #

-obj-y := sock.o skbuff.o iovec.o datagram.o stream.o scm.o
+obj-y := sock.o skbuff.o iovec.o datagram.o stream.o scm.o gen_stats.o gen_estimator.o

obj-$(CONFIG_SYSCTL) += sysctl_net_core.o

diff -Nru a/net/core/gen_estimator.c b/net/core/gen_estimator.c
@@ -0,0 +1,204 @@
+/*
+ * net/sched/gen_estimator.c	Simple rate estimator.
+ *
+ *		This program is free software; you can redistribute it and/or
+ *		modify it under the terms of the GNU General Public License
+ *		as published by the Free Software Foundation; either version
+ *		2 of the License, or (at your option) any later version.
+ *
+ * Authors:	Alexey Kuznetsov, <[email protected]>
+ *
+ * Changes:
+ *              Jamal Hadi Salim - moved it to net/core and reshulfed
+ *              names to make it usable in general net subsystem.
+ */
+
+#include <asm/uaccess.h>
+#include <asm/system.h>
+#include <asm/bitops.h>
+#include <linux/module.h>
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/jiffies.h>
+#include <linux/string.h>
+#include <linux/mm.h>
+#include <linux/socket.h>
+#include <linux/sockios.h>
+#include <linux/in.h>
+#include <linux/errno.h>
+#include <linux/interrupt.h>
+#include <linux/netdevice.h>
+#include <linux/skbuff.h>
+#include <linux/rtnetlink.h>
+#include <linux/init.h>
+#include <net/sock.h>
+#include <net/gen_stats.h>
+
+/*
+   This code is NOT intended to be used for statistics collection,
+   its purpose is to provide a base for statistical multiplexing
+   for controlled load service.
+   If you need only statistics, run a user level daemon which
+   periodically reads byte counters.
+
+   Unfortunately, rate estimation is not a very easy task.
+   F.e. I did not find a simple way to estimate the current peak rate
+   and even failed to formulate the problem 8)8)
+
+   So I preferred not to built an estimator into the scheduler,
+   but run this task separately.
+   Ideally, it should be kernel thread(s), but for now it runs
+   from timers, which puts apparent top bounds on the number of rated
+   flows, has minimal overhead on small, but is enough
+   to handle controlled load service, sets of aggregates.
+
+   We measure rate over A=(1<<interval) seconds and evaluate EWMA:
+
+   avrate = avrate*(1-W) + rate*W
+
+   where W is chosen as negative power of 2: W = 2^(-ewma_log)
+
+   The resulting time constant is:
+
+   T = A/(-ln(1-W))
+
+
+   NOTES.
+
+   * The stored value for avbps is scaled by 2^5, so that maximal
+     rate is ~1Gbit, avpps is scaled by 2^10.
+
+   * Minimal interval is HZ/4=250msec (it is the greatest common divisor
+     for HZ=100 and HZ=1024 8)), maximal interval
+     is (HZ*2^EST_MAX_INTERVAL)/4 = 8sec. Shorter intervals
+     are too expensive, longer ones can be implemented
+     at user level painlessly.
+ */
+
+#define EST_MAX_INTERVAL	5
+
+struct gen_estimator
+{
+	struct gen_estimator	*next;
+	struct gnet_stats_basic	*bstats;
+	struct gnet_stats_rate_est	*rate_est;
+	spinlock_t		*stats_lock;
+	unsigned		interval;
+	int			ewma_log;
+	u64			last_bytes;
+	u32			last_packets;
+	u32			avpps;
+	u32			avbps;
+};
+
+struct gen_estimator_head
+{
+	struct timer_list	timer;
+	struct gen_estimator	*list;
+};
+
+static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
+
+/* Estimator array lock */
+static rwlock_t est_lock = RW_LOCK_UNLOCKED;
+
+static void est_timer(unsigned long arg)
+{
+	int idx = (int)arg;
+	struct gen_estimator *e;
+
+	read_lock(&est_lock);
+	for (e = elist[idx].list; e; e = e->next) {
+		u64 nbytes;
+		u32 npackets;
+		u32 rate;
+
+		spin_lock(e->stats_lock);
+		nbytes = e->bstats->bytes;
+		npackets = e->bstats->packets;
+		rate = (nbytes - e->last_bytes)<<(7 - idx);
+		e->last_bytes = nbytes;
+		e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log;
+		e->rate_est->bps = (e->avbps+0xF)>>5;
+
+		rate = (npackets - e->last_packets)<<(12 - idx);
+		e->last_packets = npackets;
+		e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log;
+		e->rate_est->pps = (e->avpps+0x1FF)>>10;
+		spin_unlock(e->stats_lock);
+	}
+
+	mod_timer(&elist[idx].timer, jiffies + ((HZ<<idx)/4));
+	read_unlock(&est_lock);
+}
+
+int gen_new_estimator(struct gnet_stats_basic *bstats,
+	struct gnet_stats_rate_est *rate_est, spinlock_t *stats_lock, struct rtattr *opt)
+{
+	struct gen_estimator *est;
+	struct gnet_estimator *parm = RTA_DATA(opt);
+
+	if (RTA_PAYLOAD(opt) < sizeof(*parm))
+		return -EINVAL;
+
+	if (parm->interval < -2 || parm->interval > 3)
+		return -EINVAL;
+
+	est = kmalloc(sizeof(*est), GFP_KERNEL);
+	if (est == NULL)
+		return -ENOBUFS;
+
+	memset(est, 0, sizeof(*est));
+	est->interval = parm->interval + 2;
+	est->bstats = bstats;
+	est->rate_est = rate_est;
+	est->stats_lock = stats_lock;
+	est->ewma_log = parm->ewma_log;
+	est->last_bytes = bstats->bytes;
+	est->avbps = rate_est->bps<<5;
+	est->last_packets = bstats->packets;
+	est->avpps = rate_est->pps<<10;
+
+	est->next = elist[est->interval].list;
+	if (est->next == NULL) {
+		init_timer(&elist[est->interval].timer);
+		elist[est->interval].timer.data = est->interval;
+		elist[est->interval].timer.expires = jiffies + ((HZ<<est->interval)/4);
+		elist[est->interval].timer.function = est_timer;
+		add_timer(&elist[est->interval].timer);
+	}
+	write_lock_bh(&est_lock);
+	elist[est->interval].list = est;
+	write_unlock_bh(&est_lock);
+	return 0;
+}
+
+void gen_kill_estimator(struct gnet_stats_basic *bstats,
+	struct gnet_stats_rate_est *rate_est)
+{
+	int idx;
+	struct gen_estimator *est, **pest;
+
+	for (idx=0; idx <= EST_MAX_INTERVAL; idx++) {
+		int killed = 0;
+		pest = &elist[idx].list;
+		while ((est=*pest) != NULL) {
+			if (est->rate_est != rate_est || est->bstats != bstats) {
+				pest = &est->next;
+				continue;
+			}
+
+			write_lock_bh(&est_lock);
+			*pest = est->next;
+			write_unlock_bh(&est_lock);
+
+			kfree(est);
+			killed++;
+		}
+		if (killed && elist[idx].list == NULL)
+			del_timer(&elist[idx].timer);
+	}
+}
+
+EXPORT_SYMBOL(gen_kill_estimator);
+EXPORT_SYMBOL(gen_new_estimator);

* David S. Miller <[email protected]> 2004-10-05 14:03

Looks good.

I have the following idea in mind, regarding on howto actually use this code.

(Qdisc API is being used for explanation)

1) Introduce new qdisc op dump_stats in struct Qdisc_ops. (minor)
+ int (*dump_stats)(struct Qdisc *, struct sk_buff *, struct gnet_dump *);

2) Replace struct tc_stats in struct Qdisc with a list of generic network statistics common to all qdiscs (basic/queue/rate_est) (minor)

3) Fix all statistic updates to use new structs (minor)

4) Use new generic estimator (minor)

5) Adapt tc_fill_qdisc and to use new gnet_stats API in compatibilty mode and call dump_stats if available.

+ if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
+ TCA_XSTATS, q->stats_lock, &dump) < 0)
+ goto rtattr_failure;
+
+ if (q->ops->dump_stats && q->ops->dump_stats(q, skb, &dump) < 0)
+ goto rtattr_failure;
+
+ if (gnet_stats_copy_basic(&dump, &q->bstats) < 0 ||
+#ifdef CONFIG_NET_ESTIMATOR
+ gnet_stats_copy_rate_est(&dump, &q->rate_est) < 0 ||
+#endif
+ gnet_stats_copy_queue(&dump, &q->qstats) < 0)
+ goto rtattr_failure;
+
+ if (gnet_stats_finish_copy(&dump) < 0)

        goto rtattr_failure;

6) The qdisc implements dump_stats and dumps qdisc specific statistics such as the existing xstats. It may dump other generic statistics which are only used by this qdisc. The implementation of this callback is optional and only required if the qdisc has own statistics.

+static int cbq_dump_stats(struct Qdisc *sch, struct sk_buff *skb, struct gnet_dump *d) +{
+ struct cbq_sched_data *q = qdisc_priv(sch);
+
+ q->link.xstats.avgidle = q->link.avgidle;
+ if (gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats)) < 0)
+ return -1;
+ return 0;
+}

7) Remove old xstats copying code (some qdiscs, namely HTB, even copy TCA_STATS on their own which doesn't make sense)

Pros:
- All statistics nicely organized in one TLV (replaces TCA_STATS and TCA_XSTATS as a long term goal.)
- TCA_STATS and TCA_XSTATS are still provided without the qdisc actually noticing.
- Easy to add new statistics without the need to even think about compatibility.
- The whole dumping process is correctly locked.
- Qdiscs may add their own generic statistics if needed.
- Qdiscs can correct/update statistics right before dumping to be as accurate as possible.

Cons:
- Requires changing all qdiscs. (mostly minor changes)
- (Would) break binary only qdiscs.

I've tested the above code for a few days but will continue to do so for a few days.

Since this is pretty major and will touch a lot of code I'd be interested if this is the right way to go and how to do it to make patch submission as easy as possible.
Here would be my scenario on howto do it in several steps not breaking anything in between:
Step 1: Use new generic networking statistics, update all qdiscs and
switch to new estimator. Doesn't break anything but must be atomic.
Step 2-N: Add dump_stats and update qdiscs one after each other.

Thoughts?

This sounds fine to me. Don't be concerned about breaking binary-only qdiscs :-)

Documentation of generic network statistics and estimator API.

@@ -0,0 +1,117 @@
+Generic networking statistics for netlink users
+======================================================================
+
+Statistic counters are grouped into structs:
+
+Struct               TLV type              Description
+----------------------------------------------------------------------
+gnet_stats_basic     TCA_STATS_BASIC       Basic statistics
+gnet_stats_rate_est  TCA_STATS_RATE_EST    Rate estimator
+gnet_stats_queue     TCA_STATS_QUEUE       Queue statistics
+none                 TCA_STATS_APP         Application specific
+
+
+Collecting:
+-----------
+
+Declare the statistic structs you need:
+struct mystruct {
+	struct gnet_stats_basic	bstats;
+	struct gnet_stats_queue	qstats;
+	...
+};
+
+Update statistics:
+mystruct->tstats.packet++;
+mystruct->qstats.backlog += skb->pkt_len;
+
+
+Export to userspace (Dump):
+---------------------------
+
+my_dumping_routine(struct sk_buff *skb, ...)
+{
+	struct gnet_dump dump;
+
+	if (gnet_stats_start_copy(skb, TCA_STATS2, &mystruct->lock, &dump) < 0)
+		goto rtattr_failure;
+
+	if (gnet_stats_copy_basic(&dump, &mystruct->bstats) < 0 ||
+	    gnet_stats_copy_queue(&dump, &mystruct->qstats) < 0 ||
+		gnet_stats_copy_app(&dump, &xstats, sizeof(xstats)) < 0)
+		goto rtattr_failure;
+
+	if (gnet_stats_finish_copy(&dump) < 0)
+		goto rtattr_failure;
+	...
+}
+
+TCA_STATS/TCA_XSTATS backward compatibility:
+--------------------------------------------
+
+Prior users of struct tc_stats and xstats can maintain backward
+compatibility by calling the compat wrappers to keep providing the
+existing TLV types.
+
+my_dumping_routine(struct sk_buff *skb, ...)
+{
+    if (gnet_stats_start_copy_compat(skb, TCA_STATS2, TCA_STATS,
+		TCA_XSTATS, &mystruct->lock, &dump) < 0)
+		goto rtattr_failure;
+	...
+}
+
+A struct tc_stats will be filled out during gnet_stats_copy_* calls
+and appended to the skb. TCA_XSTATS is provided if gnet_stats_copy_app
+was called.
+
+
+Locking:
+--------
+
+Locks are taken before writing and released once all statistics have
+been written. Locks are always released in case of an error. You
+are responsible for making sure that the lock is initialized.
+
+
+Rate Estimator:
+--------------
+
+0) Prepare an estimator attribute. Most likely this would be in user
+   space. The value of this TLV should contain a tc_estimator structure.
+   As usual, such a TLV nees to be 32 bit aligned and therefore the
+   length needs to be appropriately set etc. The estimator interval
+   and ewma log need to be converted to the appropriate values.
+   tc_estimator.c::tc_setup_estimator() is advisable to be used as the
+   conversion routine. It does a few clever things. It takes a time
+   interval in microsecs, a time constant also in microsecs and a struct
+   tc_estimator to  be populated. The returned tc_estimator can be
+   transported to the kernel.  Transfer such a structure in a TLV of type
+   TCA_RATE to your code in the kernel.
+
+In the kernel when setting up:
+1) make sure you have basic stats and rate stats setup first.
+2) make sure you have initialized stats lock that is used to setup such
+   stats.
+3) Now initialize a new estimator:
+
+   int ret = gen_new_estimator(my_basicstats,my_rate_est_stats,
+       mystats_lock, attr_with_tcestimator_struct);
+
+   if ret == 0
+       success
+   else
+       failed
+
+From now on, everytime you dump my_rate_est_stats it will contain
+uptodate info.
+
+Once you are done, call gen_kill_estimator(my_basicstats,
+my_rate_est_stats) Make sure that my_basicstats and my_rate_est_stats
+are still valid (i.e still exist) at the time of making this call.
+
+
+Authors:
+--------
+Thomas Graf <[email protected]>
+Jamal Hadi Salim <[email protected]>

Forgot to mention that Jamal was heavily involved in this work and is the actual initiator of this idea. See previous discussion in:
* RFC/PATCH capture qdisc requeue event in stats
* [PATCH 2.6] generic network statistics

Jamal give me a quick public ACK on this work by Thomas then :-)

Done well. We may end up finding issues in the future - cant see any at the moment.

cheers,
jamal