Hierarchical token bucket （HTB），作者 Martin Devera。HTB Home：http://luxik.cdi.cz/~devik/qos/htb/
HTB可以限速，可以共享空闲带宽，还支持优先级。
1 简单例子
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
2 Qdisc time
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
2.1 长度转换成时间
换算成时间，需要知道速度，速度用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内部有定时器，所以用时间度量，那么就统一起来了。
2.2 /proc/net/psched
这个文件导出内核的时间参数，供用户层用来转换，输出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
3 HTB参数
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
4 原理
这里主要是参考HTB作者的paper。
4.1 enqueue
入队是相对简单的，它不做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。
4.2 dequeue
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 = bufferwhile 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，那么就进入等待队列，等待一段时间。
5 实现
粗糙的代码分析
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
6 References
内核源码：
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