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