Linux内核中流量控制(11)
本文档的Copyleft归yfydz所有，使用GPL发布，可以自由拷贝，转载，转载时请保持文档的完整性，
严禁用于任何商业用途。
msn: yfydz_no1@hotmail.com
来源：http://yfydz.cublog.cn

5.11 HTB(Hierarchical token bucket, 递阶令牌桶)

HTB, 从名称看就是TBF的扩展, 所不同的是TBF就一个节点处理所有数据, 而HTB是基于分类的流控方
法, 以前那些流控一般用一个"tc qdisc"命令就可以完成配置, 而要配置好HTB, 通常情况下tc
qdisc, class, filter三种命令都要用到, 用于将不同数据包分为不同的类别, 然后针对每种类别数
据再设置相应的流控方法, 因此基于分类的流控方法远比以前所述的流控方法复杂。

HTB将各种类别的流控处理节点组合成一个节点树, 每个叶节点是一个流控结构, 可在叶子节点使用
不同的流控方法，如将pfifo, tbf等。HTB一个重要的特点是能设置每种类型的基本带宽，当本类带
宽满而其他类型带宽空闲时可以向其他类型借带宽。注意这个树是静态的, 一旦TC命令配置好后就不
变了, 而具体的实现是HASH表实现的, 只是逻辑上是树, 而且不是二叉树, 每个节点可以有多个子节
点。

HTB运行过程中会将不同类别不同优先权的数据包进行有序排列，用到了有序表, 其数据结构实际是
一种特殊的二叉树, 称为红黑树(Red Black Tree), 这种树的结构是动态变化的，而且数量不只一个
，最大可有8×8个树。

红黑树的特征是:
1) 每个节点不是红的就是黑的;
2) 根节点必须是黑的;
3) 所有叶子节点必须也是黑的;
4) 每个红节点的子节点必须是黑的, 也就是红节点的父节点必须是黑节点;
5) 从每个节点到最底层节点的所有路径必须包含相同数量的黑节点;

关于红黑树的数据结构和操作在include/linux/rbtree.h和lib/rbtree.c中定义.
 
5.11.1 HTB操作结构定义

// HTB操作数据包模式
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 */
};
但HTB模式是HTB_CAN_SEND时, 表示是可以发送, 没有阻塞; 为HTB_CANT_SEND时表示阻塞, 根本不能
发送数据包了; 为HTB_MAY_BORROW时也属于阻塞状态, 但可以向其他类别借带宽来发送.

/* interior & leaf nodes; props specific to leaves are marked L: */
// HTB类别, 用于定义HTB的节点
struct htb_class {
 /* general class parameters */
// 类别ID值, 高16位用于区分不同的HTB流控, 低16位为区分同一HTB流控中的不同类别
 u32 classid;
// 字节数, 包数统计
 struct gnet_stats_basic bstats;
// 队列信息统计
 struct gnet_stats_queue qstats;
// 速率统计, 字节率, 包率
 struct gnet_stats_rate_est rate_est;
// HTB统计信息, 借出, 借入, 令牌等参数
 struct tc_htb_xstats xstats; /* our special stats */
// HTB类别引用计数
 int refcnt;  /* usage count of this class */
#ifdef HTB_RATECM
 /* rate measurement counters */
// 流率控制参数
 unsigned long rate_bytes, sum_bytes;
 unsigned long rate_packets, sum_packets;
#endif
 /* topology */
// 在树中的层次, 0表示叶子节点, 根节点层次是TC_HTB_MAXDEPTH-1(7)
 int level;  /* our level (see above) */
// 父类别结构节点
 struct htb_class *parent; /* parent class */
// 挂接到类别ID链表
 struct hlist_node hlist; /* classid hash list item */
// 兄弟节点链表
 struct list_head sibling; /* sibling list item */
// 子节点链表
 struct list_head children; /* children list */
// 联合:
 union {
// 如果该节点是叶子节点， 则使用leaf结构, 实现具体的流控处理；
  struct htb_class_leaf {
// 叶子节点的内部流控结构
   struct Qdisc *q;
// 优先权
   int prio;
   int aprio;
// 定额参数, 缺省是取物理网卡的队列长度值
   int quantum;
// 不同层次深度的赤字
   int deficit[TC_HTB_MAXDEPTH];
// 挂接到丢包链表
   struct list_head drop_list;
  } leaf;
// 如果非叶子节点, 使用HTB内部类别结构inner, 用于形成分类树
  struct htb_class_inner {
// 提供数据包的红黑树结构, 是一个按类别ID进行排序的有序表, 以二叉树实现,
// 不同优先权对应不同的二叉树
   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). */
// 上一个有效的树节点的类别ID
   u32 last_ptr_id[TC_HTB_NUMPRIO];
  } inner;
 } un;
// 类别结构自己的数据包供应树
 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
// 事件树, 实际是等待树, 当带宽超过限制时会将该类别节点挂接到HTB流控节点的
// 等待队列wait_pq
 struct rb_node pq_node; /* node for event queue */
 unsigned long pq_key; /* the same type as jiffies global */
// 激活的优先权参数, 非0表示相应位数的数据队列有数据包可用
 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;
// 警告标志
 int warned;  /* only one warning about non work conserving .. */
 /* 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 mb