ILD

HTB theory and implementation
作者:Yuan Jianpeng 邮箱:yuanjp89@163.com
发布时间:2024-6-19 站点:Inside Linux Development

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 = 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,那么就进入等待队列,等待一段时间。


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


Copyright © linuxdev.cc 2017-2024. Some Rights Reserved.