HTB在Linux中的实现
HTB(Hierarchical Token Bucket)是一种层次化的调度方式，调度器的结构如下图所示，树形结构中的每个一个节点都是一个class，由根节点通过filter将pkt分类到叶子节点中，每个pkt的enqueue都是enqueue到叶子节点的Qdisc中。对树中每个class都有自己的CIR和PIR，因此节点随着自身所余deficit的不同可能处于GREEN, YELLOW和RED三种状态，GREEN就是rate小于CIR，YELLOW就是rate已经大于CIR，但是还小于PIR，此时此节点将通过向其父节点借用deficit来获得调度，RED就是rate已经大于PIR，此时class将被置于waiting queue中等待deficit的更新才可能从RED变为可调度的状态。
HTB的调度策略是按照低level优先，高优先级优先的原则，由于叶子节点都位于level 0，所有在level 0上可调度的class都必然是GREEN状态，应当优先调度，然后在同一level上，选择优先级最高的进行调度。对于非叶子节点，只有当其有子节点向其借用deficit的时候才会被调度，因此可能有多个不同的priority的子节点同时向其借用deficit，因此非叶子节点可能有多个priority，但调度仍然以高priority为准，并在level的调度中也严格按照priority优先的形式。
通过上面说明，实际上HTB的enqueue和dequeue都十分简单。Enqueue就是将pkt分类到叶子节点，然后enqueue到叶子节点的Qdisc中，如果此叶子节点之前为idle状态，则activate之。Dequeue就是选择现有可调度的最低level，最高priority的class进行调度。如果是同时存在多个相同level，priority的情况，则按照DRR进行调度。
下面对Linux中HTB的实现详细演示。
在图中，我们可以看到一共有三个level，每个level有两个优先级，分别为红色和蓝色，其中红色为高优先级。5个class，其中C，D，E为叶子节点，A，B为非叶子节点，即pkt只能enqueue到CDE上。对于每个level都有三个队列，分别对应两个不同priority和waiting queue（白色），当此level中class有pkt在Qdisc中时，对于非叶子节点来说是有子class向其借用deficit时，即一个class需要被调度时，这个class将被enqueue到其所在level的对应队列中。如图1，所有class都没有pkt在Qdisc中，所有level的队列都没有class。图2中，两个class，D，E都有pkt，其中C为BLUE，D为RED。因此调度时，就是选择level0，搞priority的D进行调度。
由于D的priority较高，可以一直占用，如图3所示，随着他的rate超出CIR，将不得不向B借用deficit，此时D将处于YELLOW，被放到level 0的waiting queue中，并且在B的借用队列中排队，由于D本身为RED，因此B也将在level 1的RED queue中。此时调度时，将选择C进行调度，因为C的level为0。如图4所示，C的rate随着调度超过了其PIR，此时C将处于RED，无法向其父节点借用deficit，因此只能放到level 0的waiting queue中等待deficit的更新。此时调度将只能调度B，从而继续调度D中的pkt，但是如果也超出了B的CIR，那么B也将处于YELLOW的状态，从而被enqueue到level 1的waiting queue中，并且向其父节点A开始借用deficit，此时A将被activate，从而被放到level 2的可调度队列中，优先级仍为RED。因此在图4中，BCD都在各自level的waiting queue中，但是BD都未超出其PIR，可以向其父节点借用deficit，因此仍然会得到调度。
但是不幸，A很快超出其PIR了，此时A将处于不可调度的状态，从而被加入到level 2的等待队列中。并且此时class E被enqueue新的pkt，从而被activate，处于GREEN，因此被加入到level 0的可调度队列中。因此图5中调度将会对E进行调度。
图6演示了非叶子节点会有多个priority的情况，BCDE都是YELLOW，向A借用deficit，此时A有RED和BLUE两个priority，调度时将首先对A的RED的B进行调度，B对RED的D进行调度，因此首先是对D进行调度。D的Qdisc为空后，A将会按照DRR对BC进行调度，如果调度到B将间接调度到E。
整个HTB的工作流程如上所述。下面对Linux中的实现进行简单介绍。首先看htb的class的定义：
struct htb_class {
struct Qdisc_class_common common;
/* general class parameters */
struct gnet_stats_basic_packed bstats;
struct gnet_stats_queue qstats;
struct gnet_stats_rate_est rate_est;
struct tc_htb_xstats xstats; /* our special stats */
int refcnt; /* usage count of this class */
/* topology */
int level; /* our level (see above) */
unsigned int children;
struct htb_class *parent; /* parent class */
int prio; /* these two are used only by leaves... */
int quantum; /* but stored for parent-to-leaf return */
union {
struct htb_class_leaf {
struct Qdisc *q;
int deficit[TC_HTB_MAXDEPTH];
struct list_head drop_list;
} leaf;
struct htb_class_inner {
struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */
struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class 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[TC_HTB_NUMPRIO];
} inner;
} un;
struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
struct rb_node pq_node; /* node for event queue */
psched_time_t pq_key;
int prio_activity; /* for which prios are we active */
enum htb_cmode cmode; /* current mode of the class */
/* class attached filters */
struct tcf_proto *filter_list;
int filter_cnt;
/* token bucket parameters */
struct qdisc_rate_table *rate; /* rate table of the class itself */
struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */
long buffer, cbuffer; /* token bucket depth/rate */
psched_tdiff_t mbuffer; /* max wait time */
long tokens, ctokens; /* current number of tokens */
psched_time_t t_c; /* checkpoint time */
};
|
还有htb_sched，负责管理htb整体的调度
struct htb_sched {
struct Qdisc_class_hash clhash;
struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
/* self list - roots of self generating tree */
struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
int row_mask[TC_HTB_MAXDEPTH];
struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
/* self wait list - roots of wait PQs per row */
struct rb_root wait_pq[TC_HTB_MAXDEPTH];
/* time of nearest event per level (row) */
psched_time_t near_ev_cache[TC_HTB_MAXDEPTH];
int defcls; /* class where unclassified flows go to */
/* filters for qdisc itself */
struct tcf_proto *filter_list;
int rate2quantum; /* quant = rate / rate2quantum */
psched_time_t now; /* cached dequeue time */
struct qdisc_watchdog watchdog;
/* non shaped skbs; let them go directly thru */
struct sk_buff_head direct_queue;
int direct_qlen; /* max qlen of above */
long direct_pkts;
#define HTB_WARN_TOOMANYEVENTS 0x1
unsigned int warned; /* only one warning */
struct work_struct work;
};
|
下面看enqueue的实现：
static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
{
int uninitialized_var(ret);
struct htb_sched *q = qdisc_priv(sch);
struct htb_class *cl = htb_classify(skb, sch, &ret); /* 首先对pkt进行分类，找到叶子class */
if (cl == HTB_DIRECT) {
/* enqueue to helper queue */
if (q->direct_queue.qlen < q->direct_qlen) {
__skb_queue_tail(&q->direct_queue, skb);
q->direct_pkts++;
} else {
kfree_skb(skb);
sch->qstats.drops++;
return NET_XMIT_DROP;
}
} else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
if (net_xmit_drop_count(ret)) { /* enqueue到叶子class，结束 */
sch->qstats.drops++;
cl->qstats.drops++;
}
return ret;
} else {
cl->bstats.packets +=
skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
cl->bstats.bytes += qdisc_pkt_len(skb);
htb_activate(q, cl); /* 叶子class之前可能队列为空，activate之 */
}
sch->q.qlen++;
sch->bstats.packets += skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
sch->bstats.bytes += qdisc_pkt_len(skb);
return NET_XMIT_SUCCESS;
}
|
Dequeue的实现：htb的dequeue首先检查bitmap，找出最低level最高priority的class list，然后对这个class list调用htb_dequeue_tree来实现dequeue，下面是htb_dequeue_tree的实现。
static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
int level)
{
struct sk_buff *skb = NULL;
struct htb_class *cl, *start;
/* look initial class up in the row */
start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
q->ptr[level] + prio,
q->last_ptr_id[level] + prio); /* 此处考虑的DRR的调度 */
do {
next:
if (unlikely(!cl))
return NULL;
/* class can be empty - it is unlikely but can be true if leaf
qdisc drops packets in enqueue routine or if someone used
graft operation on the leaf since last dequeue;
simply deactivate and skip such class */
if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
struct htb_class *next;
htb_deactivate(q, cl); /* 队列为空了？？deactivate之 */
/* row/level might become empty */
if ((q->row_mask[level] & (1 << prio)) == 0)
return NULL;
next = htb_lookup_leaf(q->row[level] + prio,
prio, q->ptr[level] + prio,
q->last_ptr_id[level] + prio); /* DRR */
if (cl == start) /* fix start if we just deleted it */
start = next;
cl = next;
goto next;
}
skb = cl->un.leaf.q->dequeue(cl->un.leaf.q); /* 从queue中dequeue一个pkt */
if (likely(skb != NULL))
break;
qdisc_warn_nonwc("htb", cl->un.leaf.q);
htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->ptr[0]) + prio); /* RR */
cl = htb_lookup_leaf(q->row[level] + prio, prio,
q->ptr[level] + prio,
q->last_ptr_id[level] + prio); /* DRR的实现 */
} while (cl != start);
if (likely(skb != NULL)) {
cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb); /* 更新deficit */
if (cl->un.leaf.deficit[level] < 0) { /* deficit不够了 */
cl->un.leaf.deficit[level] += cl->quantum;
htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
ptr[0]) + prio); /* 从此level的active queue中移除 */
}
/* this used to be after charge_class but this constelation
gives us slightly better performance */
if (!cl->un.leaf.q->q.qlen)
htb_deactivate(q, cl); /* 队列为空，deactivate之 */
htb_charge_class(q, cl, level, skb); /* 检查此class是否发生超标 */
}
return skb;
}
|
其中HTB层次化的实现主要体现在htb_activate, htb_deactivate, htb_charge_class, htb_change_class_mode等几个函数中，htb_activate_prios和htb_deactivate_prios完成子class向父class借用deficit的具体操作。
待续
