Hierarchical token bucket (HTB),作者 Martin Devera。HTB Home:http://luxik.cdi.cz/~devik/qos/htb/
HTB可以限速,可以共享空闲带宽,还支持优先级。
two devices
192.168.2.205
192.168.2.195
给这两台设备的上传进行限速,限速500KB/S,但是最大可以达到1M/S。
在htb中对应rate和ceil。rate是可以保障的速率。
upstream interface
eth0
通过iptables给两台设备打上不同的mark,以便后面通过filter,匹配到对应的class:
iptables -t mangle -A PREROUTING --src 192.168.2.205 -j MARK --set-mark 1
iptables -t mangle -A PREROUTING --src 192.168.2.195 -j MARK --set-mark 2
添加一个root htb qdisc
tc qdisc add dev eth0 root handle 1:0 htb default 3
添加class
tc class add dev eth0 parent 1: classid 1:1 htb rate 5mbps ceil 5mbps
tc class add dev eth0 parent 1:1 classid 1:2 htb rate 2mbps ceil 5mbps
tc class add dev eth0 parent 1:1 classid 1:3 htb rate 3mbps ceil 4mbps
tc class add dev eth0 parent 1:2 classid 1:4 htb rate 500kbps ceil 1mbps
tc class add dev eth0 parent 1:2 classid 1:5 htb rate 500kbps ceil 1mbps
添加filter,根据fw来匹配
tc filter add dev eth0 parent 1: proto ip prio 1 handle 1 fw classid 1:4
tc filter add dev eth0 parent 1: proto ip prio 1 handle 2 fw classid 1:5
可选设置leaf qdisc1
叶子class,可以添加一个无状态qdisc,用来缓存包。每个包,最终进入叶子class下面的无状态qdisc的queue。
tc qdisc add dev eth0 parent 1:5 handle 2:0 fq_codel
tc qdisc add dev eth0 parent 1:4 handle 3:0 fq_codel
删除class
$ tc class del dev eth0 parent 1: classid 1:1
删除filter
$ tc filter del dev eth0 parent 1: handle 1 protocol ip prio 1 fw
删除整个qdisc,恢复默认
$ tc qdisc del dev eth0 root
qdisc里面有很多时间、长度的转换,需要弄清楚里面的逻辑。
首先,最重要的是qdisc tick,初学者很容易和内核tick混淆。
内核tick用HZ表示,是进程调度级别的tick,HZ通常在100到1000,是1ms到10ms级别的,对计算机来说,这个时间是非常久的。
qdisc tick,用shift来表示,单位是ns,定义在include/net/pkt_sched.h
#define PSCHED_SHIFT 6
那么tick就是1<<6,也就是64ns,
这个值之前是10,2009年一个提交,将其缩短为64ns,精度更高了。
commit a4a710c4a7490587406462bf1d54504b7783d7d7
Author: Jarek Poplawski <jarkao2@gmail.com>
Date: Mon Jun 8 22:05:13 2009 +0000
pkt_sched: Change PSCHED_SHIFT from 10 to 6
tick有2个宏,用来实现和时间相互转换
#define PSCHED_TICKS2NS(x) ((s64)(x) << PSCHED_SHIFT)
#define PSCHED_NS2TICKS(x) ((x) >> PSCHED_SHIFT)
qdisc定义了一个类型psched_time_t,它的单位是qdisc tick
typedef u64 psched_time_t;
获取当前时间的tick
static inline psched_time_t psched_get_time(void)
{
return PSCHED_NS2TICKS(ktime_get_ns());
}
ktime_get_ns()是获取Number of nanoseconds since boot
换算成时间,需要知道速度,速度用psched_ratecfg结构体存储。
rate_bytes_ps是速度的绝对值,单位是bytes/s。他会换算成mult和shift,用来避免除法运算。
overhead, mpu, linklayer,用来存储链路层参数。比如以太网,头是14个字节,最小长度mpu是60个字节。
struct psched_ratecfg {
u64 rate_bytes_ps; /* bytes per second */
u32 mult;
u16 overhead;
u16 mpu;
u8 linklayer;
u8 shift;
};
static inline u64 psched_l2t_ns(const struct psched_ratecfg *r,
unsigned int len)
{
len += r->overhead;
if (len < r->mpu)
len = r->mpu;
if (unlikely(r->linklayer == TC_LINKLAYER_ATM))
return ((u64)(DIV_ROUND_UP(len,48)*53) * r->mult) >> r->shift;
return ((u64)len * r->mult) >> r->shift;
}
最后
qdisc内部全部用时间度量,包括burst/token/quantum (quantum存储为字节数)。限速多少,实际是限制多少时间片。
因为qdisc内部有定时器,所以用时间度量,那么就统一起来了。
这个文件导出内核的时间参数,供用户层用来转换,输出4个数,输出格式为16进制
# cat /proc/net/psched
000003e8 00000040 000f4240 00000064
1 NSEC_PER_USEC,常量,1us与多少ns,1000
2 PSCHED_TICKS2NS(1),1个qdisc tick有多少ns
3 常量1000000
4 最高精度HZ,NSEC_PER_SEC / hrtimer_resolution
如果没有定义CONFIG_HIGH_RES_TIMERS,则这个值等于内核HZ
在x86上,高精度定时器是1ns精度,这个值是1000000000
tc程序的参数和内核存储的参数,存在换算。
qdsic参数:
r2q
DRR quantums are computed as rate in Bps/r2q,用来计算DDR (deficit round robin)quantum,默认是10。
当class没有指定quantum时,使用rate/r2q,得到一个默认值。
class参数:
速度
有两种速度,rate和ceil。
tc参数有:rate、ceil、mtu,mpu,overhead、linklayer、
内核存储为psched_ratecfg结构体,rate和ceil2个。
内核存储rate单位为bytes/s
burst/cburst
用户输入是字节数,传给内核是根据速率计算出来的qdisc tick数。
内核存储的是时间,单位为ns。cl->buffer = PSCHED_TICKS2NS(hopt->buffer);
quantum
用户和内核都是存储的字节数,只有叶子节点有这个参数
priority
优先级,只有叶子节点支持prio,最多有8个优先级,范围是:0-7
这里主要是参考HTB作者的paper。
入队是相对简单的,它不做traffic shaping。如下图:
首先只有叶子class,会附加一个classless qdisc。包都入队到这些classless qdisc中存储。
filter可以附加到htb,也可以附加到htb的中间class。
入队过程如下:
1 先进行qdisc filter匹配,找到一个class,如果没有找到一个class,则使用默认class。
2 如果找到class是一个叶子class,那么结束了,包进入这个叶子class的qdisc。
3 如果不是一个叶子class,那么这个class也有一个filter,再进行filter匹配,得到一个新的class,重复这个过程。直到得到一个叶子class。
4 如果得到的是默认class,且默认class不存在,则进入htb 的 direct queue。
dequeue就是将leaf qdisc中的skb取出,然后发送,关键是如何调度的问题,来实现速度控制、空闲带宽共享、优先级处理。
HTB有8个优先级,最大深度为8。叶子的level是0,根节点的level是7。
class有3个状态,可发送、可借用、不可发送。
当class当前速度小于rate参数值,处于可发送状态。
当前速度大于rate,小于ceil,处于可借用状态。
当前速度大于ceil,处于不可发送状态。
速度控制原理
token/wait/pkt_len/diff,这4个参数,伪代码如下:
1 2 3 4 5 6 7 8 9 10 11 | token = buffer while true { dequeue() token -= psched_l2t_ns(&rate, pkt_len); if (token < 0) { wait = -token sleep(wait) token += diff } } |
token有一个初始值buffer,单位是ns。发送一个包,就减去按限定速度发送这个包需要的ns数。如果token小于0,就休眠token时间。
休眠后,再次调度的时候,token加上一次到本次的时间差diff(单位ns),不是加休眠时间,是因为休眠可能并不精确。再发送下一个包。
所以如果休眠足够精确的话,那么限速可以均衡到单个包级别。
空闲带宽共享原理
使用的deficit round robin (DRR) 算法。一个父类,有多个子类共享带宽。每个子类有一个quantum数。那么每个子类分配的比例是:
Qn/Sum(Q)。子类A发送Qa,然后子类B发送Qb。
调度原理
如下图所示:
1 每个level的每个优先级都有一个红黑树(self slot)
一个class如果处于绿色(可发送)状态,那么就加入这个class所处level、优先级的slot。
叶子class只有一个自己的优先级,但是中间节点可能有多个优先级,因为中间节点可能有不同优先级的儿子。
2 中间class有一个每个优先级的红黑树(inner slot)
当儿子处于黄色(可借用)状态,就加入到父亲的对应优先级的inner slot中。
3 每个level有一个wait queue
如果class处于红色(不可发送)状态,那么加入class所处level的wait queue。
4 空闲的class或者空闲的优先级,不加入任何slot或者wait queue。
调度的时候,从底层level,最高优先级开始,遍历每一个红黑树中的每一个class,找到这个class的子孙叶子class,出队。
所以level大于0的self slot,总是找到一个叶子来出队的。
思考:
限速是通过叶子节点为绿色,加入多level 0的红黑树,调度实现的。
当叶子节点超速,但仍小于ceil后,变成黄色,就加入父亲的inner slot了。父亲如果是绿色,那么父亲加入父亲所在level的self slot。通过调度父亲来实现借带宽。
如果超过ceil,那么就进入等待队列,等待一段时间。
粗糙的代码分析
enum htb_cmode {
HTB_CANT_SEND, /* class can't send and can't borrow */
HTB_MAY_BORROW, /* class can't send but may borrow */
HTB_CAN_SEND /* class can send */
};
struct htb_prio {
union {
struct rb_root row;
struct rb_root feed;
};
struct rb_node *ptr;
/* When class changes from state 1->2 and disconnects from
* parent's feed then we lost ptr value and start from the
* first child again. Here we store classid of the
* last valid ptr (used when ptr is NULL).
*/
u32 last_ptr_id;
};
struct htb_class
{
union {
struct htb_class_inner {
struct htb_prio clprio[TC_HTB_NUMPRIO];
} inner;
};
struct rb_node pq_node;
struct rb_node node[TC_HTB_NUMPRIO];
};
struct htb_level {
struct rb_root wait_pq;
struct htb_prio hprio[TC_HTB_NUMPRIO];
};
struct htb_sched {
s64 now; /* cached dequeue time */
s64 near_ev_cache[TC_HTB_MAXDEPTH];
int row_mask[TC_HTB_MAXDEPTH];
struct htb_level hlevel[TC_HTB_MAXDEPTH];
}
==============================================
htb_enqueue()
htb_activate(struct htb_sched *q, struct htb_class *cl)
htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
入队,总是找到叶子class,进行入队操作
void htb_activate(struct htb_sched *q, struct htb_class *cl)
激活一个叶子class,进入调度状态。
是否是调度状态是由prio_activity字段控制的。它是一个priority的掩码
对于叶子节点,只有一个优先级,对于中间节点,可能有多个优先级,因为子孙节点的优先级可能不同。
来看下源码
static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
{
WARN_ON(cl->level || !cl->leaf.q || !cl->leaf.q->q.qlen);
if (!cl->prio_activity) {
cl->prio_activity = 1 << cl->prio;
htb_activate_prios(q, cl);
}
}
调用htb_active(),那cl->level肯定是0,表明是一个叶子class
cl->leaf.q非空,表明叶子节点有一个无状态qdisc。
cl->leaf.q->q.qlen非空,表明叶子节点的qdisc肯定有数据。因为htb_activate是在enqueue之后调用的,那肯定是有一个新鲜的数据的。
如果cl->prio_activity是非0,那表明已经激活了,那啥也不用干,
如果是0,则是第一次激活,设置prio_activity为class的优先级的掩码 1 << cl->prio,
然后调用 htb_activate_prios(q, cl);
static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
激活一个class,进入调度状态,不仅是叶子节点,中间节点也会调用这个接口
源码展示:
static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
{
struct htb_class *p = cl->parent;
long m, mask = cl->prio_activity;
while (cl->cmode == HTB_MAY_BORROW && p && mask) {
m = mask;
while (m) {
int prio = ffz(~m);
m &= ~(1 << prio);
if (p->inner.clprio[prio].feed.rb_node)
/* parent already has its feed in use so that
* reset bit in mask as parent is already ok
*/
mask &= ~(1 << prio);
htb_add_to_id_tree(&p->inner.clprio[prio].feed, cl, prio);
}
p->prio_activity |= mask;
cl = p;
p = cl->parent;
}
if (cl->cmode == HTB_CAN_SEND && mask)
htb_add_class_to_row(q, cl, mask);
}
解析
1 如果cl是may_borrow状态,且它有父亲,那么这个class,进入父亲的 inner feed 列表。
may_borrow表明,这个class的速率大于rate,小于ceil,所以,将其进入父亲的 feed列表,由父亲调度。
注意对于中间节点,cl->prio_activity,可能有多个优先级。所以每个优先级进入父亲对应的slot
if (p->inner.clprio[prio].feed.rb_node)
这条语句是表明,父亲已经加了此优先级的其它儿子了。
那么这个优先级,就不用往上冒泡了。
htb_add_to_id_tree接口是将class加到一个红黑树。
2 上述处理后,要么cl还是本class,要么是冒泡的终点。
如果这个cl是 HTB_CAN_SEND,且有mask,(mask为0,表明之前已经添加过了)
那么就调用htb_add_class_to_row,将class添加到qdisc的hlevel
注意,这里mask可能也有多个优先级。
htb_add_class_to_row()
===========================================================================
将class,添加到qdisc的slot中
源码展示:
static inline void htb_add_class_to_row(struct htb_sched *q,
struct htb_class *cl, int mask)
{
q->row_mask[cl->level] |= mask;
while (mask) {
int prio = ffz(~mask);
mask &= ~(1 << prio);
htb_add_to_id_tree(&q->hlevel[cl->level].hprio[prio].row, cl, prio);
}
}
解析
row_mask数组,存储了每个level,对应激活的优先级。
class的mask可能有多个优先级,每个优先级都将class加入到hlevel中。
htb_add_to_id_tree()这个函数就不讲了,就是一个红黑树的插入动作。
htb_dequeue()
===========================================================================
出队一个skb
源码展示:
static struct sk_buff *htb_dequeue(struct Qdisc *sch)
{
struct sk_buff *skb;
struct htb_sched *q = qdisc_priv(sch);
int level;
s64 next_event;
unsigned long start_at;
/* try to dequeue direct packets as high prio (!) to minimize cpu work */
skb = __qdisc_dequeue_head(&q->direct_queue);
if (skb != NULL) {
ok:
qdisc_bstats_update(sch, skb);
qdisc_qstats_backlog_dec(sch, skb);
sch->q.qlen--;
return skb;
}
if (!sch->q.qlen)
goto fin;
q->now = ktime_get_ns();
start_at = jiffies;
next_event = q->now + 5LLU * NSEC_PER_SEC;
for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
/* common case optimization - skip event handler quickly */
int m;
s64 event = q->near_ev_cache[level];
if (q->now >= event) {
event = htb_do_events(q, level, start_at);
if (!event)
event = q->now + NSEC_PER_SEC;
q->near_ev_cache[level] = event;
}
if (next_event > event)
next_event = event;
m = ~q->row_mask[level];
while (m != (int)(-1)) {
int prio = ffz(m);
m |= 1 << prio;
skb = htb_dequeue_tree(q, prio, level);
if (likely(skb != NULL))
goto ok;
}
}
if (likely(next_event > q->now))
qdisc_watchdog_schedule_ns(&q->watchdog, next_event);
else
schedule_work(&q->work);
fin:
return skb;
}
解析:
direct queue的先不关心,重点关注htb class如何调度的。
遍历每个level,处理这个level的event和dequeue
near_ev_cache存储每个level最近的事件的时间戳,如果当前时间大于等于这个时间。
那么就调用htb_do_events()处理事件
为每一个level的,每一个优先级,调用htb_dequeue_tree(),出队,
如果成功出队,整个循环退出。
最后,如果没有出队任何一个skb,那么就要
1 如果时间在未来,则添加watchdog
2 如果时间在当下,则直接调度work
watchdog和work干同一个事情: __netif_schedule(qdisc_root(sch));
先看htb_dequeue_tree()吧
===========================================================================
开始进入深水区了
static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, const int prio,
const int level)
代码太长,不展示全部,解析如下:
1 调用 htb_lookup_leaf(hprio, prio),找到下一个叶子节点,
htb_prio结构体内部会存储cursor,从上一次的位置开始找,遵循DRR顺序。
htb_lookup_leaf()非常复杂,这里先不分析
2 调用 skb = cl->leaf.q->dequeue(cl->leaf.q),进行出队
3 出队成功,则搞事情了,需要维护class的状态
if (likely(skb != NULL)) {
bstats_update(&cl->bstats, skb);
cl->leaf.deficit[level] -= qdisc_pkt_len(skb);
if (cl->leaf.deficit[level] < 0) {
cl->leaf.deficit[level] += cl->quantum;
htb_next_rb_node(level ? &cl->parent->inner.clprio[prio].ptr :
&q->hlevel[0].hprio[prio].ptr);
}
/* this used to be after charge_class but this constelation
* gives us slightly better performance
*/
if (!cl->leaf.q->q.qlen)
htb_deactivate(q, cl);
htb_charge_class(q, cl, level, skb);
}
上述level是hlevel,不是叶子class的level。
a. 首先将叶子节点对应level的deficit减去包长,如果deficit小于0,则补充quantum,并且将游标移到下一个位置,这样下次就遍历下一个节点。
b. 如果节点没数据了,则调用deactive
c. 调用htb_charge_class()更新class的状态。
先看看htb_deactivate
===========================================================================
只有叶子节点调用此接口,用来将叶子节点和其祖先从feed list拿走
static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
{
WARN_ON(!cl->prio_activity);
htb_deactivate_prios(q, cl);
cl->prio_activity = 0;
}
先调用htb_deactivate_prios()取消激活本叶子节点、及其祖先。
然后将prio_activity复位为0
htb_deactivate_prios
===========================================================================
代码展示:
static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
{
struct htb_class *p = cl->parent;
long m, mask = cl->prio_activity;
while (cl->cmode == HTB_MAY_BORROW && p && mask) {
m = mask;
mask = 0;
while (m) {
int prio = ffz(~m);
m &= ~(1 << prio);
if (p->inner.clprio[prio].ptr == cl->node + prio) {
/* we are removing child which is pointed to from
* parent feed - forget the pointer but remember
* classid
*/
p->inner.clprio[prio].last_ptr_id = cl->common.classid;
p->inner.clprio[prio].ptr = NULL;
}
htb_safe_rb_erase(cl->node + prio,
&p->inner.clprio[prio].feed);
if (!p->inner.clprio[prio].feed.rb_node)
mask |= 1 << prio;
}
p->prio_activity &= ~mask;
cl = p;
p = cl->parent;
}
if (cl->cmode == HTB_CAN_SEND && mask)
htb_remove_class_from_row(q, cl, mask);
}
解析:
完全是htb_activate_prios()的逆操作
接着看 htb_charge_class()
===========================================================================
这个接口就是 维护token,根据token的值,改变class、以及class先祖的状态,
根据状态的变更,做对应的处理
这里的代码不长,全是精华,值得全部展示
static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
int level, struct sk_buff *skb)
{
int bytes = qdisc_pkt_len(skb);
enum htb_cmode old_mode;
s64 diff;
while (cl) {
diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
if (cl->level >= level) {
if (cl->level == level)
cl->xstats.lends++;
htb_accnt_tokens(cl, bytes, diff);
} else {
cl->xstats.borrows++;
cl->tokens += diff; /* we moved t_c; update tokens */
}
htb_accnt_ctokens(cl, bytes, diff);
cl->t_c = q->now;
old_mode = cl->cmode;
diff = 0;
htb_change_class_mode(q, cl, &diff);
if (old_mode != cl->cmode) {
if (old_mode != HTB_CAN_SEND)
htb_safe_rb_erase(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
if (cl->cmode != HTB_CAN_SEND)
htb_add_to_wait_tree(q, cl, diff);
}
/* update basic stats except for leaves which are already updated */
if (cl->level)
bstats_update(&cl->bstats, skb);
cl = cl->parent;
}
}
分析:
传入的cl是一个叶子class,这个函数,会遍历所有的先祖,都做charge处理,如下:
1 首先计算出diff,diff是class从上次调度,到本次的时间差,单位是ns,和mbuffer取小的。mbuffer现在是个常量,初始化为60s。
2 a. 如果cl的level,小于level,上面源码中的else部分,表明是父亲触发的调度,走的是ceil的逻辑,是从兄弟节点借用带宽。
因此,这里只更新token,不消耗token
b. cl level大于等于level,则调用htb_accnt_tokens()更新、并消耗token
3 调用htb_accnt_ctokens()更新并消耗ctoken
4 调用htb_change_class_mode(),根据token值,更新mode,根据mode的状态变化,维护feed list
5 如果mode发生变化,如果旧mode不是可以发送,则肯定是在wait queue,先将其移除,如果新mode不是可以发送,将其加入到wait queue
总结:如果一个class不是可以发送(也就是HTB_CANT_SEND或者HTB_MAY_BORROW),那肯定是在wait queue。
6 更新祖先的字节统计
htb_accnt_tokens()
===========================================================================
更新token
源码展示:
static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, s64 diff)
{
s64 toks = diff + cl->tokens;
if (toks > cl->buffer)
toks = cl->buffer;
toks -= (s64) psched_l2t_ns(&cl->rate, bytes);
if (toks <= -cl->mbuffer)
toks = 1 - cl->mbuffer;
cl->tokens = toks;
}
解析:
逻辑非常简单,diff是过去空置的时间,要加到token上,加上后,如果大于cl->buffer,那么就等于buffer。
通过速率和bytes,计算出发送包消耗的时间,这个就是消耗的token,减去这个时间,得到新的token,
如果toks是负数,表明溢出了,负数的最小值是1 - cl->mbuffer。
htb_accnt_ctokens()函数更新ctoken,逻辑和token是完全一样的。
htb_change_class_mode()
===========================================================================
计算class的新mode,并根据mode值,维护feed list
代码展示:
static void
htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, s64 *diff)
{
enum htb_cmode new_mode = htb_class_mode(cl, diff);
if (new_mode == cl->cmode)
return;
if (new_mode == HTB_CANT_SEND) {
cl->overlimits++;
q->overlimits++;
}
if (cl->prio_activity) { /* not necessary: speed optimization */
if (cl->cmode != HTB_CANT_SEND)
htb_deactivate_prios(q, cl);
cl->cmode = new_mode;
if (new_mode != HTB_CANT_SEND)
htb_activate_prios(q, cl);
} else
cl->cmode = new_mode;
}
解析:
1 调用htb_class_mode()计算出新的模式
2 如果新模式和旧模式相同,则啥也不用干,直接返回
3 如果新模式,变成不能发送HTB_CANT_SEND,overlimit统计值加1
4
htb_class_mode()
===========================================================================
计算新的模式
源码展示:
static inline s64 htb_lowater(const struct htb_class *cl)
{
if (htb_hysteresis)
return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
else
return 0;
}
static inline s64 htb_hiwater(const struct htb_class *cl)
{
if (htb_hysteresis)
return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
else
return 0;
}
static inline enum htb_cmode
htb_class_mode(struct htb_class *cl, s64 *diff)
{
s64 toks;
if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
*diff = -toks;
return HTB_CANT_SEND;
}
if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
return HTB_CAN_SEND;
*diff = -toks;
return HTB_MAY_BORROW;
}
解析:
注意,上述并不更新token,diff有两种情况,第一种是调度的时候,diff已经更新到token了,此时diff为0。
第二种,是在htb_do_events(),diff是等待过的时间,它根据diff预估状态,然后根据状态将其加到feed list,等feed list真正运行的时候,再更新token。
htb_hysteresis模块参数,默认是0。所以htb_lowater()和htb_hiwater()均返回0。
1 如果ctoken小于0,则cmode是不能发送HTB_CANT_SEND,
2 如果token大于等于0,则是能发送状态HTB_CAN_SEND
3 如果token小于0,则是可借用的状态HTB_MAY_BORROW
如果状态是不能发送或者借用,则返回一个等待时间给diff,调用者会将这个class加入到等待队列,等待时间是这个diff。
htb_do_events()
===========================================================================
处理wait queue的中的class,有了上面的基础,这个函数的理解就顺理成章了。
wait queue,就是让class空置一段,其核心处理,如下:
htb_safe_rb_erase(p, wait_pq);
diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
htb_change_class_mode(q, cl, &diff);
if (cl->cmode != HTB_CAN_SEND)
htb_add_to_wait_tree(q, cl, diff);
1 先将其从wait queue移除。
2 计算空置的时长
3 根据空置时长,调用htb_change_class_mode,重新计算class mode,
4 如果class mode,仍然不是HTB_CAN_SEND,将其再次加入 wait queue
内核源码:
net/sched/sch_htb.c
include/uapi/linux/pkt_sched.h
参考文档:
Hierachical token bucket theory
http://luxik.cdi.cz/~devik/qos/htb/manual/theory.htm