本文记录tc tbf qdisc使用netlink与内核通信的参数格式、数据含义、tc命令中tbf相关实现与内核中相关实现。增加老版本内核中tbf队列bug分析

tc命令中tbf qdisc实现位于iproute2项目文件iproute2/tc/q_tbf.c

内核中实现位于文件net/sched/sch_tbf.c

参考内核版本：4.18.0-193.el8.x86_64

tc tbf 命令参数

  • rate
    限速速率，输入根据单位不同可以是字节每秒也可以是比特每秒
  • burst、buffer、maxburst
    也可以是burst/cell形式输入，cell用于配合rtab使用，cell只在旧版本内核有使用，当前已经不再使用
    令牌桶累积最大令牌量对应的可以传输的数据量，允许突发的最大数据量。根据单位不同可以是字节也可以是比特
  • limit
    缓冲区可以缓存的最大数据量，根据单位不同可以是字节也可以比特，k、m、g之间乘1024，接收输入后先转换为字节
  • latency
    缓冲区可以缓存数据包的最大延迟时间，与limit互相冲突，接收输入后会用于计算出来limit
  • peakrate
    在burst范围内的突发数据无法限制到rate速率。因此可以增加配置peakrate和mtu对突发的数据做进一步的流量整形限速
  • mtu、minburst
    也可以是mtu/cell形式输入，cell用于配合ptab使用，cell只在旧版本内核有使用，当前已经不再使用
  • mpu
    数据包最小尺寸字节数。比如以太网是64字节，小于该尺寸的数据包也会被填充到该尺寸再发送到链路中
  • overhead
    数据包在链路传播需要额外占用的字节数
  • linklayer
    指定链路层类型，输入可以是ethernet、atm、adsl

传输参数

tbf qdic使用netlink与内核交互的传输参数类型

1
2
3
4
5
6
7
8
9
10
11
12
enum {                   
    TCA_TBF_UNSPEC,      
    TCA_TBF_PARMS,       
    TCA_TBF_RTAB,        
    TCA_TBF_PTAB,        
    TCA_TBF_RATE64,      
    TCA_TBF_PRATE64,     
    TCA_TBF_BURST,       
    TCA_TBF_PBURST,      
    TCA_TBF_PAD,         
    __TCA_TBF_MAX,       
};

TCA_TBF_PARMS

TCA_TBF_PARMS对应的数据结构为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct tc_tbf_qopt {              
    struct tc_ratespec rate;      // 限速速率相关

    struct tc_ratespec peakrate;  // 峰值限速速率。因为累积的token，也就是buffer的存在，会有突发数据，单纯的rate无法限制该突发。
                                  // 因此使用peakrate进一步限制突发速率

    __u32       limit;            // 数据包队列可以缓存的最大字节数。
                                  // tc命令行参数中latency也是作用于该参数，因为发送速率限制的原因，缓存最大字节数与最大延迟时间直接相关

    __u32       buffer;           // 该数据结构中buffer存储的是令牌桶允许累积的最大token数
                                  // tc命令在计算这个数值时，会先将整形的字节数转换为double再计算除法，由于double精度损失和最终再转换为整形的损失，传输的这个数值会比理论值小。
                                  // 这个值也会经过换算体现为允许突发的数据字节数，突发字节数需要不小于设备实际mtu。

    __u32       mtu;              // minburst，这个可以看作peakrate所对应的buffer，也就是peakrate的突发，意义相同。如果mtu设置小于设备实际mtu，会发生数据包无法发送的问题，直接被丢弃。
                                  // tc命令在计算这个数值时，情况与buffer一样，传输的数值会比理论值小。
                                  // 一般mtu设置小于buffer，peakrate大于rate，达到削峰效果。
};

struct tc_ratespec {                                
    unsigned char   cell_log;                     // cell的2的对数。比如cell为128，既每128字节长度作为一个粒度，则cell_log为7
                                                  // 采用对数是为了使用较小的数组保存更多的尺寸对应的传输所需token
                                                  // 匹配rtab、ptab使用，只在旧版本内核有使用

    __u8        linklayer; /* lower 4 bits */     // 链路层类型。3种值TC_LINKLAYER_UNAWARE、TC_LINKLAYER_ETHERNET、TC_LINKLAYER_ATM

    unsigned short  overhead;                     // 数据包在链路传播需要额外占用的字节数。

    short       cell_align;                       // tc工具固定设置为-1，与cell_log配合计算字节到所需token的转换

    unsigned short  mpu;                          // 数据包最小尺寸字节数。比如以太网是64字节，小于该尺寸的数据包也会被填充到该尺寸再发送到链路中
                                                  // 这个用于内核接收配置时做链路层类型检测

    __u32       rate;                             // 限速速率。如果限速每秒字节数小于1<<32，也就是不超过32位，使用该字段。否则该字段置~0U（也就是所有位置1），并使用TCA_TBF_RATE64及TCA_TBF_PRATE64。
};

这里提到的tc_tbf_qopt.buffer和tc_tbf_qopt.mtu存储的是token数，但是tc命令输入参数是字节数，换算过程如下：

  1. 将字节数size转换为发送所需要的时间，size / rate * USEC_PER_SEC，得到发送size字节需要的微秒数time，这里USEC_PER_SEC在iproute2项目中实际使用的宏为TIME_UNITS_PER_SEC
  2. 计算微秒数time对应的token，time * tick_in_usec

其中tick_in_usec在函数tc_core_init中被预先计算出了，这个函数中对读取值存入的变量命名会引起误解，因此下面使用内核代码说明。
读取/proc/net/psched文件，该文件输出4个值，实现为内核代码中函数psched_show，位于文件net/sched/sch_api.c

  • 第一个值为NSEC_PER_USEC，一微秒包含多少纳秒，值为1000
  • 第二个值为PSCHED_TICKS2NS(1)，该宏实现为左移6位。一个tick包含多少纳秒，这里的tick为模拟的假tick，可以理解为token，只用于数据包调度整形使用，最终值为64
  • 第三个值写死为1000000。
  • 第四个值应该与时钟分辨率有关，tc用不到，不管了

tick_in_usec的计算方式为 值1 / 值2 * 值3 / TIME_UNITS_PER_SEC
由于值3与TIME_UNITS_PER_SEC相等，tick_in_usec最终即为一微秒包含的token数，1000/64=15.625

TCA_TBF_RTAB/TCA_TBF_PTAB

这两个在当前的内核中已经不再使用。后面旧版本BUG章节记录了内核版本变更过程中出现过的该表格有关的bug。

u32类型256项数组，tc工具中生成，由cell_log和rate确定

rtab/ptab的生成函数如下

  • 计算rtab时，cell_log为buffer对应的cell的2为底的对数，未配置cell时为-1，mtu为peakrate对应的mtu，如果没有配置peakrate则传入mtu为0。
  • 计算ptab时，cell_log为mtu对应的cell的2为底的对数，未配置cell时为-1，mtu为peakrate对应的mtu。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int tc_calc_rtable(struct tc_ratespec *r, __u32 *rtab,
        int cell_log, unsigned int mtu,
        enum link_layer linklayer)
{
    int i;
    unsigned int sz;
    unsigned int bps = r->rate;
    unsigned int mpu = r->mpu;

    // 如果未配置mtu，默认设置为2047，它影响的是cell_log的计算，如果cell_log配置过，传入mtu没有作用
    if (mtu == 0)
        mtu = 2047;

    // 如果未配置cell_log，计算出一个合适的值，标准是mtu右移cell_log，刚刚不大于数组最大索引255
    // 这样size不超过mtu尺寸的数据包，size >> cell_log不会大于255，可以落在rtab中
    if (cell_log < 0) {
        cell_log = 0;
        while ((mtu >> cell_log) > 255)
            cell_log++;
    }

    // 以cell_log为7为例，rtab[0]对应128字节所需token，rtab[1]对应256字节所需token
    // rtab[i]存储了 (s+1)<<cell_log 字节传输所需的token
    for (i = 0; i < 256; i++) {
        sz = tc_adjust_size((i + 1) << cell_log, mpu, linklayer);
        // 尺寸和速率计算出所需token
        rtab[i] = tc_calc_xmittime(bps, sz);
    }

    r->cell_align =  -1;
    r->cell_log = cell_log;
    r->linklayer = (linklayer & TC_LINKLAYER_MASK);
    return cell_log;
}

TCA_TBF_RATE64/TCA_TBF_PRATE64

当限速每秒字节数大于等于1<<32，也就是超过32位表示时，使用这两个参数，不再使用tc_ratespec.rate字段

TCA_TBF_BURST

这里对应的也是tc_tbf_qopt.buffer，但是这里存储的是字节数，而不是token数

TCA_TBF_PBURST

这里对应的也是tc_tbf_qopt.mtu，但是这里存储的是字节数，而不是token数

内核实现

配置 tbf_change

内核使用数据结构tbf_sched_data保存配置参数，内核源码中该结构的注释记录了tbf的计算原理，这里不重复了
这个结构中有些成员记录的是字节数，有些是时间，但是这里的时间又不是传输中使用的token数，而是经过换算后的纳秒数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct tbf_sched_data {                                                     
    /* Parameters */                                                            
    u32     limit;      /* Maximal length of backlog: bytes */
                        /* 对应传输进来的limit，数据队列字节数。生效于qdisc成员包含的bfifo队列中 */

    u32     max_size;   /* 突发数据字节数，实际运行时便于比较。取buffer和mtu对应的字节数的较小值 */
                        /* enqueue时使用，如果数据包尺寸超过该值将会尝试gso分片或丢弃 */

    s64     buffer;     /* Token bucket depth/rate: MUST BE >= MTU/B */
                        /* rate对应突发数据限额对应的纳秒数，dequeue时使用 */

    s64     mtu;        /* prate对应的突发数据限额对应的纳秒数，dequeue时使用 */

    struct psched_ratecfg rate;                                             
    struct psched_ratecfg peak;                                             

    /* Variables */                                                             
    s64 tokens;         /* Current number of B tokens */                    
    s64 ptokens;        /* Current number of P tokens */                    
    s64 t_c;            /* Time check-point */                              
    struct Qdisc    *qdisc;     /* Inner qdisc, default - bfifo queue */                   
    struct qdisc_watchdog watchdog; /* Watchdog timer */                    
};
1
2
3
4
5
6
7
struct psched_ratecfg {                            
    u64 rate_bytes_ps; /* bytes per second */      
    u32 mult;          /* 用于加速计算字节数到纳秒数的计算 */                           
    u16 overhead;      /* 见上文 */
    u8  linklayer;     /* 见上文 */                            
    u8  shift;         /* 用于加速计算字节数到纳秒数的计算 */                        
};

使用函数psched_ratecfg_precompute保存及计算限速速率及用于加速字节数到对应时间长度的算法参数，存储到结构体psched_ratecfg中，overhead、linklayer均在这里被保存

  • 普通的计算方式为time_in_ns = (NSEC_PER_SEC * len) / rate_bps
  • 加速的计算方式为time_in_ns = (len * mult) >> shift

mult和shift计算方式的原因，(len * mult) >> shift计算得到的time_in_ns会比理论值小一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void psched_ratecfg_precompute(struct psched_ratecfg *r,
        const struct tc_ratespec *conf,
        u64 rate64)
{
    memset(r, 0, sizeof(*r));
    r->overhead = conf->overhead;
    r->rate_bytes_ps = max_t(u64, conf->rate, rate64);
    r->linklayer = (conf->linklayer & TC_LINKLAYER_MASK);
    r->mult = 1;
    /*
     * The deal here is to replace a divide by a reciprocal one
     * in fast path (a reciprocal divide is a multiply and a shift)
     *
     * Normal formula would be :
     *  time_in_ns = (NSEC_PER_SEC * len) / rate_bps
     *
     * We compute mult/shift to use instead :
     *  time_in_ns = (len * mult) >> shift;
     *
     * We try to get the highest possible mult value for accuracy,
     * but have to make sure no overflows will ever happen.
     */
    if (r->rate_bytes_ps > 0) {
        u64 factor = NSEC_PER_SEC;

        for (;;) {
            r->mult = div64_u64(factor, r->rate_bytes_ps);
            if (r->mult & (1U << 31) || factor & (1ULL << 63))
                break;
            factor <<= 1;
            r->shift++;
        }
    }
}

入队列 tbf_enqueue

入队列出队列都比较简单，简略记录一下

对于外发数据包来说，__dev_queue_xmit中调用函数qdisc_pkt_len_init初始化了qdisc_skb_cb(skb)->pkt_len = skb->len

  • 入队列时获取该长度，与max_size比较，并综合判断gso相关字段
  • 符合条件会调用qdisc_enqueue
    • 调用qdisc_calculate_pkt_len，尝试使用Qdisc->stab更新qdisc_skb_cb(skb)->pkt_len。没有看到stab哪里初始化的，就当不存在吧
    • 调用Qdisc.enqueue函数指针，这里应该是bfifo_enqueue函数。判断数据包队列是否会超出limit，不超出则入队列
  • 如果qdisc_enqueue失败
    • 根据返回码判断是否需要计数drop数值，Qdisc.qstats.drops字段表示丢包数
  • 如果qdisc_enqueue成功
    • 更新统计信息，Qdisc.qstats.backlog表示队列中字节数，Qdisc.q.qlen表示队列中数据包数

出队列 tbf_dequeue

  • 获取队列首包
  • qdisc_pkt_len(skb)获取数据包长度
  • 获取当前时间纳秒值
  • 当前时间纳秒值与上次检查点时间纳秒值做减法，并与tbf_sched_data.buffer做比较、取较小值赋值给toks。含义是取得当前新累积的令牌数量，这里令牌使用了纳秒代替，该数量不能超过突发量。
  • 如果有配置峰值速率，之前剩余q->ptokens加toks获取可用峰值ptoks，注意这里mtu相当于峰值限速的buffer，因此ptoks不能大于mtu。ptoks减掉当前数据包长度需要消耗的纳秒值（这里使用了overhead及linklayer）
  • q->tokens加toks获取当前可用toks，限制toks不能大于buffer
  • toks减去当前数据包需要消耗的纳秒值（这里使用了overhead及linklayer）
  • 如果toks与ptoks都大于0，说明当前资源满足发送该数据包
    • 更新检查点为当前时间
    • 更新tbf_sched_data的tokens与ptokens成员
    • 更新统计信息，Qdisc.qstats.backlog，Qdisc.q.qlen，Qdisc.bstats.bytes队列发出的字节数，Qdisc.bstats.packets队列发出的包数
    • 返回skb
  • 如果不满足发包要求
    • 设置定时器
    • 更新超限速统计信息，Qdisc.qstats.overlimits表示超出限速没有成功从队列取出数据包的次数，数据包只是暂时保留在队列中。这个数值会出现超过发出包数的情况

旧版本BUG

3.9rc1之前

内核收到的buffer和mtu为token值，rate为字节数，rtab、ptab为tc计算生成。内核对以上数据均为原值原单位保存。

max_size

在旧版本内核中，使用rtab和ptab计算max_size，位于tbf_change函数中，可以看到这里将buffer和mtu的token值通过rtab、ptab换算回了字节数(该cell对应最大字节数-1)，并取两个的较小值。由于cell颗粒度的原因，这个max_size可能比buffer和mtu对应的理论字节数大。

max_size计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (n = 0; n < 256; n++)
    if (rtab->data[n] > qopt->buffer)
        break;
max_size = (n << qopt->rate.cell_log) - 1;
if (ptab) {
    int size;

    for (n = 0; n < 256; n++)
        if (ptab->data[n] > qopt->mtu)
            break;
    size = (n << qopt->peakrate.cell_log) - 1;
    if (size < max_size)
        max_size = size;
}

可以先假设未配置peakrate，那么只考虑rtab

  • 选择最小的rtab[s] > qopt->buffer，若遍历结束也未符合，则s取到256
  • max_size = s << cell_log - 1
  • 上面rtab[s]值对应的是(s+1) << cell_log字节传输所需的token
  • max_size相当于选择了前一个cell的最大字节数-1
  • 这个选择方式下，前一个cell，也就是rtab[s-1]小于等于qopt->buffer这个token值。
  • 如果刚好是等于，那么max_size+1的传输时间就等于buffer，而这个buffer的token值是经历过精度损失的，也就是说可能存在一个范围的字节数的传输时间都等于这个buffer。
例1
  • 以rate 500mbit（62500000字节每秒），cell值128为例，cell_log=7，
  • rtab[240]的值对应的是241 << 7（也就是30848字节）传输所需的7703token
  • 由于计算所需token时double精度原因，[30813, 30874]字节范围内buffer计算均为7703
  • 也就是说，tc命令配置的buffer在[30813，30874]范围内时，max_size均为30847
  • 在dequeue时，[30721,30848]范围内，查找对应token时都会落在rtab[240]中。
例2
  • 以rate100mbit（12500000字节每秒），cell值8为例，cell_log=3（未配置cell和mtu时默认值）
  • rtab[200]的值对应的是201<<3（也就是1608字节）传输所需的2000token
  • 由于计算所需token时double精度原因，[1600, 1612]字节范围内buffer计算均为2000
  • 也就是说，tc命令配置的buffer在[1600，1612]范围内时，max_size均为1607
  • 在dequeue时，[1601,1608]范围内，查找对应token时都会落在rtab[200]中。

enqueue/dequeue

enqueue时检查数据包不大于max_size，超过做drop处理

dequeue时通过rtab查找传输数据包需要的token，与当前可用的token比较，当前可用的token被限制不超过buffer，max_size尺寸需要的token不会超过buffer

dequeue时将字节转换为传输需要的token
1
2
3
4
5
6
7
8
9
10
static inline u32 qdisc_l2t(struct qdisc_rate_table* rtab, unsigned int pktlen)
{
    int slot = pktlen + rtab->rate.cell_align + rtab->rate.overhead;
    if (slot < 0)
        slot = 0;
    slot >>= rtab->rate.cell_log;
    if (slot > 255)
        return rtab->data[255]*(slot >> 8) + rtab->data[slot & 0xFF];
    return rtab->data[slot];
}

这一系列流程是可以正确工作的

3.9rc1

3.9rc1开始包含了这个提交b757c93 tbf: improved accuracy at high rates

也导致了bug的出现。centos7.2 3.10.0-327.el7.x86_64内核含有该bug

这个提交没有变更内核中max_size计算逻辑，依然通过遍历rtab并与buffer的token值对比确定

但是

  • 内核保存的配置buffer和mtu都由token转换到了纳秒
  • dequeue时不再查rtab表，而是通过(size * mult) >> shift计算传输数据包所需纳秒，方式参考，这种方式计算字节到纳秒的转换，精度损失很低

以例1数据

  • max_size为30847，buffer对应token值7703，对应纳秒值492992
  • 30813字节的数据包可以enqueue，dequeue时计算传输所需纳秒(30813 * 2147483648) >> 27 = 493008，超过了buffer的纳秒值，会导致dequeue失败，阻塞在队列头，该队列就无法正常发送数据包了。

以例2数据

  • max_size为1607，buffer对应token值2000，对应纳秒值128000
  • 1601字节的数据包可以enqueue，dequeue时计算传输所需纳秒(1601 * 2684354560) >> 25 = 128080，超过了buffer的纳秒值，会导致dequeue失败，阻塞在队列头，该队列就无法正常发送数据包了。

因为在一些情况下，buffer对应的token值可以等于rtab中一个槽位的token值，max_size就对应了这个cell所代表的最大字节数，但是token是有精度损失的，也就是说这个token实际对应的是更小的字节数，将buffer转换为纳秒后，这个纳秒也对应的也是相比max_size更小的字节数。当一个比这个字节数大又不超过max_size的数据包enqueue以后，在dequeue时计算出的传输所需纳秒数就会检查到比buffer的纳秒数更大，导致dequeue失败。
以上是以buffer为例，mtu的影响也是同buffer一样的。

3.13rc4

3.13rc4开始包含了这个提交cc106e4 net: sched: tbf: fix the calculation of max_size

这个提交修复了上面的bug。centos7.5 3.10.0-862.el7.x86_64内核修复了该bug。7.3和7.4未检查验证

该提交先将token值的buffer和mtu转换为纳秒值的buffer和mtu，再使用纳秒值和限速速率计算出max_size。
这样dequeue时通过字节数计算得到的纳秒数就可以匹配buffer和mtu的纳秒数了。
这里开始rtab、ptab不再有作用了。

3.14rc1

3.14rc1开始包含了这个提交2e04ad4 sch_tbf: add TBF_BURST/TBF_PBURST attribute

加了TCA_TBF_BURST/TCA_TBF_PBURST这两个参数，直接传递buffer和mtu的字节数。
当新增的参数存在时，用于确定max_size，内核保存的buffer和mtu纳秒值由新增的字节单位参数计算得到。
这时使用tc命令配置tbf时，可以精确生效字节单位配置。
但是截止2024年7月，linux内核tbf_dump时依然未输出这两个参数，v6.10.0版本iproute2项目中tc命令也未读取这两个参数，两者都只使用了旧版本的token值的buffer和mtu。导致展示配置时与内核保存的实际配置有偏差。

BUG规避

对比存在bug的内核，bug的触发，是由于计算出的max_size相对buffer对应的字节数大了，导致dequeue检查失败。
max_size的计算受buffer和cell_log共同影响，只要确保max_size绝对小于buffer对应的字节数就可以规避bug。
因此，配置合适的buffer和cell_log就可以确保bug不会发生。

比如例1数据中，buffer设置30813，cell_log为7时，max_size为30847，bug可能触发。
修改cell_log为6，buffer不变，max_size变为16383。(16383 * 2147483648) >> 27 = 262128，远小于buffer的纳秒值492992，bug不会触发。

比如例2数据中，buffer设置1601，cell_log默认为3时，max_size为1607，bug可能触发。
修改buffer设置为3200，cell_log手动指定为3，max_size变为2047。(2047 * 2684354560) >> 25 = 163760，远小于buffer的纳秒值256000，bug不会触发。

如果以修改cell_log规避，可以使用如下方式确定合适的cell_log。原方式计算出cell_log后，以该cell_log计算临时rtab和max_size，并计算该max_size的token，该token应该是不大于buffer的token的，如果刚好相等则cell_log减1，再重复回到计算临时rtab和max_size。循环该过程，直到临时max_size的token小于buffer的token，这时的cell_log就是可用的。这个循环不超过2次就可以达成目标。

mtu和其cell_log同理

实际业务中，简单起见，可以考虑固定buffer，使用调整过的cell_log，比如65535字节buffer，其cell指定为128(cell_log为7)，则bug不会触发。