Linux内核中流量控制(11)

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

Java代码 复制代码  收藏代码
  1. 5.11 HTB(Hierarchical token bucket, 递阶令牌桶)   
  2.   
  3. HTB, 从名称看就是TBF的扩展, 所不同的是TBF就一个节点处理所有数据, 而HTB是基于分类的流控方   
  4. 法, 以前那些流控一般用一个"tc qdisc"命令就可以完成配置, 而要配置好HTB, 通常情况下tc   
  5. qdisc, class, filter三种命令都要用到, 用于将不同数据包分为不同的类别, 然后针对每种类别数   
  6. 据再设置相应的流控方法, 因此基于分类的流控方法远比以前所述的流控方法复杂。   
  7.   
  8. HTB将各种类别的流控处理节点组合成一个节点树, 每个叶节点是一个流控结构, 可在叶子节点使用   
  9. 不同的流控方法，如将pfifo, tbf等。HTB一个重要的特点是能设置每种类型的基本带宽，当本类带   
  10. 宽满而其他类型带宽空闲时可以向其他类型借带宽。注意这个树是静态的, 一旦TC命令配置好后就不   
  11. 变了, 而具体的实现是HASH表实现的, 只是逻辑上是树, 而且不是二叉树, 每个节点可以有多个子节   
  12. 点。   
  13.   
  14. HTB运行过程中会将不同类别不同优先权的数据包进行有序排列，用到了有序表, 其数据结构实际是   
  15. 一种特殊的二叉树, 称为红黑树(Red Black Tree), 这种树的结构是动态变化的，而且数量不只一个   
  16. ，最大可有8×8个树。   
  17.   
  18. 红黑树的特征是:   
  19. 1) 每个节点不是红的就是黑的;   
  20. 2) 根节点必须是黑的;   
  21. 3) 所有叶子节点必须也是黑的;   
  22. 4) 每个红节点的子节点必须是黑的, 也就是红节点的父节点必须是黑节点;   
  23. 5) 从每个节点到最底层节点的所有路径必须包含相同数量的黑节点;   
  24.   
  25. 关于红黑树的数据结构和操作在include/linux/rbtree.h和lib/rbtree.c中定义.   
  26.     
  27. 5.11.1 HTB操作结构定义   
  28.   
  29. // HTB操作数据包模式   
  30. enum htb_cmode {   
  31. // 不能发送   
  32.  HTB_CANT_SEND,  /* class can't send and can't borrow */  
  33. // 借带宽   
  34.  HTB_MAY_BORROW,  /* class can't send but may borrow */  
  35. // 可发送   
  36.  HTB_CAN_SEND  /* class can send */  
  37. };   
  38. 但HTB模式是HTB_CAN_SEND时, 表示是可以发送, 没有阻塞; 为HTB_CANT_SEND时表示阻塞, 根本不能   
  39. 发送数据包了; 为HTB_MAY_BORROW时也属于阻塞状态, 但可以向其他类别借带宽来发送.   
  40.   
  41. /* interior & leaf nodes; props specific to leaves are marked L: */  
  42. // HTB类别, 用于定义HTB的节点   
  43. struct htb_class {   
  44.  /* general class parameters */  
  45. // 类别ID值, 高16位用于区分不同的HTB流控, 低16位为区分同一HTB流控中的不同类别   
  46.  u32 classid;   
  47. // 字节数, 包数统计   
  48.  struct gnet_stats_basic bstats;   
  49. // 队列信息统计   
  50.  struct gnet_stats_queue qstats;   
  51. // 速率统计, 字节率, 包率   
  52.  struct gnet_stats_rate_est rate_est;   
  53. // HTB统计信息, 借出, 借入, 令牌等参数   
  54.  struct tc_htb_xstats xstats; /* our special stats */  
  55. // HTB类别引用计数   
  56.  int refcnt;  /* usage count of this class */  
  57. #ifdef HTB_RATECM   
  58.  /* rate measurement counters */  
  59. // 流率控制参数   
  60.  unsigned long rate_bytes, sum_bytes;   
  61.  unsigned long rate_packets, sum_packets;   
  62. #endif   
  63.  /* topology */  
  64. // 在树中的层次, 0表示叶子节点, 根节点层次是TC_HTB_MAXDEPTH-1(7)   
  65.  int level;  /* our level (see above) */  
  66. // 父类别结构节点   
  67.  struct htb_class *parent; /* parent class */  
  68. // 挂接到类别ID链表   
  69.  struct hlist_node hlist; /* classid hash list item */  
  70. // 兄弟节点链表   
  71.  struct list_head sibling; /* sibling list item */  
  72. // 子节点链表   
  73.  struct list_head children; /* children list */  
  74. // 联合:   
  75.  union {   
  76. // 如果该节点是叶子节点， 则使用leaf结构, 实现具体的流控处理；   
  77.   struct htb_class_leaf {   
  78. // 叶子节点的内部流控结构   
  79.    struct Qdisc *q;   
  80. // 优先权   
  81.    int prio;   
  82.    int aprio;   
  83. // 定额参数, 缺省是取物理网卡的队列长度值   
  84.    int quantum;   
  85. // 不同层次深度的赤字   
  86.    int deficit[TC_HTB_MAXDEPTH];   
  87. // 挂接到丢包链表   
  88.    struct list_head drop_list;   
  89.   } leaf;   
  90. // 如果非叶子节点, 使用HTB内部类别结构inner, 用于形成分类树   
  91.   struct htb_class_inner {   
  92. // 提供数据包的红黑树结构, 是一个按类别ID进行排序的有序表, 以二叉树实现,   
  93. // 不同优先权对应不同的二叉树   
  94.    struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */  
  95. // 当前优先权树中正在处理的那个节点的指针   
  96.    struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */  
  97.    /* When class changes from state 1->2 and disconnects from  
  98.       parent's feed then we lost ptr value and start from the  
  99.       first child again. Here we store classid of the  
  100.       last valid ptr (used when ptr is NULL). */  
  101. // 上一个有效的树节点的类别ID   
  102.    u32 last_ptr_id[TC_HTB_NUMPRIO];   
  103.   } inner;   
  104.  } un;   
  105. // 类别结构自己的数据包供应树   
  106.  struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */  
  107. // 事件树, 实际是等待树, 当带宽超过限制时会将该类别节点挂接到HTB流控节点的   
  108. // 等待队列wait_pq   
  109.  struct rb_node pq_node; /* node for event queue */  
  110.  unsigned long pq_key; /* the same type as jiffies global */  
  111. // 激活的优先权参数, 非0表示相应位数的数据队列有数据包可用   
  112.  int prio_activity; /* for which prios are we active */  
  113. // 当前模式, 表示是否可发送数据包   
  114.  enum htb_cmode cmode; /* current mode of the class */  
  115.  /* class attached filters */  
  116. // 过滤规则表   
  117.  struct tcf_proto *filter_list;   
  118. // 过滤器使用计数   
  119.  int filter_cnt;   
  120. // 警告标志   
  121.  int warned;  /* only one warning about non work conserving .. */  
  122.  /* token bucket parameters */  
  123. // 令牌率   
  124.  struct qdisc_rate_table *rate; /* rate table of the class itself */  
  125. // 峰值率   
  126.  struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */  
  127. // 缓冲区/峰值缓冲区   
  128.  long buffer, cbuffer; /* token bucket depth/rate */  
  129. // 最大等待时间   
  130.  psched_tdiff_t mbuffer; /* max wait time */  
  131. // 当前令牌数/峰值令牌   
  132.  long tokens, ctokens; /* current number of tokens */  
  133. // 检查点时间   
  134.  psched_time_t t_c; /* checkpoint time */  
  135. };   
  136.   
  137. // HTB私有数据结构   
  138. struct htb_sched {   
  139. // HTB根节点链表   
  140.  struct list_head root; /* root classes list */  
  141. // HTB哈希表, 根据类别ID进行哈希   
  142.  struct hlist_head hash[HTB_HSIZE]; /* hashed by classid */  
  143. // 8级丢包链表   
  144.  struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */  
  145.  /* self list - roots of self generating tree */  
  146. // RB树根节点, 对应每一层的每一个优先权值都有一个RB树   
  147.  struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];   
  148. // 掩码, 表示该层的哪些优先权值的树有效   
  149.  int row_mask[TC_HTB_MAXDEPTH];   
  150. // 父节点指针   
  151.  struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];   
  152. // 上次使用的非空父节点的类别ID   
  153.  u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];   
  154.  /* self wait list - roots of wait PQs per row */  
  155. // 等待队列, 用来挂接那些带宽超出限制的节点   
  156.  struct rb_root wait_pq[TC_HTB_MAXDEPTH];   
  157.  /* time of nearest event per level (row) */  
  158.  unsigned long near_ev_cache[TC_HTB_MAXDEPTH];   
  159.  /* cached value of jiffies in dequeue */  
  160. // 当前时间, 在dequeue时更新   
  161.  unsigned long jiffies;   
  162.  /* whether we hit non-work conserving class during this dequeue; we use */  
  163.  int nwc_hit;  /* this to disable mindelay complaint in dequeue */  
  164. // 缺省类别   
  165.  int defcls;  /* class where unclassified flows go to */  
  166.  /* filters for qdisc itself */  
  167. // 过滤规则表   
  168.  struct tcf_proto *filter_list;   
  169.  int filter_cnt;   
  170. // 速率到定额转换参数   
  171.  int rate2quantum; /* quant = rate / rate2quantum */  
  172. // 当前时间   
  173.  psched_time_t now; /* cached dequeue time */  
  174. // 定时器   
  175.  struct timer_list timer; /* send delay timer */  
  176. #ifdef HTB_RATECM   
  177. // 速率定时器   
  178.  struct timer_list rttim; /* rate computer timer */  
  179.  int recmp_bucket; /* which hash bucket to recompute next */  
  180. #endif   
  181.  /* non shaped skbs; let them go directly thru */  
  182. // 直接处理数据包队列   
  183.  struct sk_buff_head direct_queue;   
  184.  int direct_qlen; /* max qlen of above */  
  185. // 直接处理的数据包计数   
  186.  long direct_pkts;   
  187. };   
  188.     
  189. // HTB类别操作结构   
  190. static struct Qdisc_class_ops htb_class_ops = {   
  191.  .graft  = htb_graft,   
  192.  .leaf  = htb_leaf,   
  193.  .get  = htb_get,   
  194.  .put  = htb_put,   
  195.  .change  = htb_change_class,   
  196.  .delete  = htb_delete,   
  197.  .walk  = htb_walk,   
  198.  .tcf_chain = htb_find_tcf,   
  199.  .bind_tcf = htb_bind_filter,   
  200.  .unbind_tcf = htb_unbind_filter,   
  201.  .dump  = htb_dump_class,   
  202.  .dump_stats = htb_dump_class_stats,   
  203. };   
  204.   
  205. // HTB 流控操作结构   
  206. static struct Qdisc_ops htb_qdisc_ops = {   
  207.  .next  = NULL,   
  208.  .cl_ops  = &htb_class_ops,   
  209.  .id  = "htb",   
  210.  .priv_size = sizeof(struct htb_sched),   
  211.  .enqueue = htb_enqueue,   
  212.  .dequeue = htb_dequeue,   
  213.  .requeue = htb_requeue,   
  214.  .drop  = htb_drop,   
  215.  .init  = htb_init,   
  216.  .reset  = htb_reset,   
  217.  .destroy = htb_destroy,   
  218. // 更改操作为空   
  219.  .change  = NULL /* htb_change */,   
  220.  .dump  = htb_dump,   
  221.  .owner  = THIS_MODULE,   
  222. };   
  223.   
  224. 5.11.1 HTB的TC操作命令   
  225.   
  226. 为了更好理解HTB各处理函数，先用HTB的配置实例过程来说明各种操作调用了哪些HTB处理函数，以   
  227. 下的配置实例取自HTB Manual, 属于最简单分类配置:   
  228.   
  229. 1) 配置网卡的根流控节点为HTB   
  230.   
  231. #根节点ID是0x10000, 缺省类别是0x10012,   
  232. # handle x:y, x定义的是类别ID的高16位, y定义低16位   
  233. #注意命令中的ID参数都被理解为16进制的数   
  234. tc qdisc add dev eth0 root handle 1: htb default 12  
  235.   
  236. 在内核中将调用htb_init()函数初始化HTB流控结构.   
  237.     
  238. 2) 建立分类树   
  239.   
  240. #根节点总流量带宽100kbps, 内部类别ID是0x10001  
  241. tc class add dev eth0 parent 1: classid 1:1 htb rate 100kbps ceil 100kbps   
  242. #第一类别数据分30kbps, 最大可用100kbps, 内部类别ID是0x10010(注意这里确实是16进制的10)   
  243. tc class add dev eth0 parent 1:1 classid 1:10 htb rate 30kbps ceil 100kbps   
  244. #第二类别数据分30kbps, 最大可用100kbps, 内部类别ID是0x10011  
  245. tc class add dev eth0 parent 1:1 classid 1:11 htb rate 10kbps ceil 100kbps   
  246. #第三类别(缺省类别)数据分60kbps, 最大可用100kbps, 内部类别ID是0x10012  
  247. tc class add dev eth0 parent 1:1 classid 1:12 htb rate 60kbps ceil 100kbps   
  248.   
  249. 在内核中将调用htb_change_class()函数来修改HTB参数   
  250.   
  251. 3) 数据包分类   
  252.   
  253. #对源地址为1.2.3.4, 目的端口是80的数据包为第一类, 0x10010  
  254. tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip src 1.2.3.4 match ip   
  255. dport 80 0xffff flowid 1:10  
  256. #对源地址是1.2.3.4的其他类型数据包是第2类, 0x10011  
  257. tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip src 1.2.3.4 flowid   
  258. 1:11  
  259. #其他数据包将作为缺省类, 0x10012  
  260.   
  261. 在内核中将调用htb_find_tcf(), htb_bind_filter()函数来将为HTB绑定过滤表   
  262.   
  263. 4) 设置每个叶子节点的流控方法   
  264.   
  265. # 1:10节点为pfifo   
  266. tc qdisc add dev eth0 parent 1:10 handle 20: pfifo limit 10  
  267. # 1:11节点也为pfifo   
  268. tc qdisc add dev eth0 parent 1:11 handle 30: pfifo limit 10  
  269. # 1:12节点使用sfq, 扰动时间10秒   
  270. tc qdisc add dev eth0 parent 1:12 handle 40: sfq perturb 10  
  271.   
  272. 在内核中会使用htb_leaf()查找HTB叶子节点, 使用htb_graft()函数来设置叶子节点的流控方法.   
  273.     
  274. 5.11.2 HTB类别操作   
  275.   
  276. 5.11.2.1 嫁接   
  277.   
  278. // 设置HTB叶子节点的流控方法   
  279. static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,   
  280.        struct Qdisc **old)   
  281. {   
  282.  struct htb_class *cl = (struct htb_class *)arg;   
  283. // 类别结构非空而且层次为0(叶子节点)   
  284.  if (cl && !cl->level) {   
  285. // 如果没定义专门的流控方法, 则缺省定义pfifo作为缺省的流控方法   
  286.   if (new == NULL && (new = qdisc_create_dflt(sch->dev,   
  287.            &pfifo_qdisc_ops))   
  288.       == NULL)   
  289.    return -ENOBUFS;   
  290.   sch_tree_lock(sch);   
  291. // 将新的流控方法作为类别结构叶子节点的流控方法   
  292.   if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {   
  293. // 如果该类别还处于活动状态, 停止, 因为其原来的流控方法已经要被释放掉,   
  294. // 不再处理数据包   
  295.    if (cl->prio_activity)   
  296.     htb_deactivate(qdisc_priv(sch), cl);   
  297.    /* TODO: is it correct ? Why CBQ doesn't do it ? */  
  298. // 将老流控节点释放掉   
  299.    sch->q.qlen -= (*old)->q.qlen;   
  300.    qdisc_reset(*old);   
  301.   }   
  302.   sch_tree_unlock(sch);   
  303.   return 0;   
  304.  }   
  305. // 否则出错   
  306.  return -ENOENT;   
  307. }   
  308.   
  309. 5.11.2.2  获取叶子节点   
  310.   
  311. static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)   
  312. {   
  313.  struct htb_class *cl = (struct htb_class *)arg;   
  314. // 如果类别结构非空而且是叶子节点, 返回该类别叶子节点的流控   
  315.  return (cl && !cl->level) ? cl->un.leaf.q : NULL;   
  316. }   
  317.   
  318. 5.11.2.3 增加类别的引用计数   
  319.   
  320. static unsigned long htb_get(struct Qdisc *sch, u32 classid)   
  321. {   
  322. // 查找类别ID对应的HTB类别结构   
  323.  struct htb_class *cl = htb_find(classid, sch);   
  324. // 找到的话增加其引用计数   
  325.  if (cl)   
  326.   cl->refcnt++;   
  327.  return (unsigned long)cl;   
  328. }   
  329.   
  330. 5.11.2.4 减少类别引用计数   
  331.   
  332. static void htb_put(struct Qdisc *sch, unsigned long arg)   
  333. {   
  334.  struct htb_class *cl = (struct htb_class *)arg;   
  335. // 减少类别引用计数, 如果减到0, 释放该类别   
  336.  if (--cl->refcnt == 0)   
  337.   htb_destroy_class(sch, cl);   
  338. }   
  339. // 释放类别   
  340. static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)   
  341. {   
  342. // HTB私有数据结构   
  343.  struct htb_sched *q = qdisc_priv(sch);   
  344.  if (!cl->level) {   
  345. // 属于叶子节点的情况   
  346.   BUG_TRAP(cl->un.leaf.q);   
  347. // HTB流控总队列长度减少该叶子流控节点的队列长度   
  348.   sch->q.qlen -= cl->un.leaf.q->q.qlen;   
  349. // 释放叶子流控节点   
  350.   qdisc_destroy(cl->un.leaf.q);   
  351.  }   
  352. // 释放流量处理结构: 普通速率和峰值速率   
  353.  qdisc_put_rtab(cl->rate);   
  354.  qdisc_put_rtab(cl->ceil);   
  355. // 释放类别过滤规则表   
  356.  htb_destroy_filters(&cl->filter_list);   
  357. // 递归调用htb_destroy_class释放该节点的子节点   
  358.  while (!list_empty(&cl->children))   
  359.   htb_destroy_class(sch, list_entry(cl->children.next,   
  360.         struct htb_class, sibling));   
  361.  /* note: this delete may happen twice (see htb_delete) */  
  362. // 删除类别ID链表   
  363.  hlist_del_init(&cl->hlist);   
  364. // 释放子类别链表   
  365.  list_del(&cl->sibling);   
  366. // 停止类别结构   
  367.  if (cl->prio_activity)   
  368.   htb_deactivate(q, cl);   
  369. // 如果类别结构属于需要等待模式, 将该节点从等待RB树中删除   
  370.  if (cl->cmode != HTB_CAN_SEND)   
  371.   htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);   
  372. // 释放类别本身   
  373.  kfree(cl);   
  374. }   
  375.   
  376. 注意: 由于使用了递归处理, 因此HTB树不能太大, 否则就会使内核堆栈溢出而导致内核崩溃, HTB定   
  377. 义的最大深度是8层.   
  378.   
  379. 5.11.2.5 更改类别结构内部参数   
  380.   
  381. static int htb_change_class(struct Qdisc *sch, u32 classid,   
  382.        u32 parentid, struct rtattr **tca,   
  383.        unsigned long *arg)   
  384. {   
  385.  int err = -EINVAL;   
  386. // HTB私有数据结构   
  387.  struct htb_sched *q = qdisc_priv(sch);   
  388. // 类别结构指针, 从上层传入   
  389.  struct htb_class *cl = (struct htb_class *)*arg, *parent;   
  390. // 通过netlink接口传来的配置参数   
  391.  struct rtattr *opt = tca[TCA_OPTIONS - 1];   
  392. // 速率表, 峰值速率表结构   
  393.  struct qdisc_rate_table *rtab = NULL, *ctab = NULL;   
  394. // 保存解析后的参数   
  395.  struct rtattr *tb[TCA_HTB_RTAB];   
  396. // HTB选项   
  397.  struct tc_htb_opt *hopt;   
  398.  /* extract all subattrs from opt attr */  
  399. // 解析输入参数, 进行相关合法性检查   
  400.  if (!opt || rtattr_parse_nested(tb, TCA_HTB_RTAB, opt) ||   
  401.      tb[TCA_HTB_PARMS - 1] == NULL ||   
  402.      RTA_PAYLOAD(tb[TCA_HTB_PARMS - 1]) < sizeof(*hopt))   
  403.   goto failure;   
  404. // 如果父节点ID不是根ID, 根据此ID查找父节点, 否则为父节点空   
  405.  parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);   
  406.   
  407.  hopt = RTA_DATA(tb[TCA_HTB_PARMS - 1]);   
  408. // 从输入参数中获取速率表结构: 普通速率和峰值速率   
  409.  rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB - 1]);   
  410.  ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB - 1]);   
  411.  if (!rtab || !ctab)   
  412.   goto failure;   
  413.   
  414.  if (!cl) {  /* new class */  
  415. // 如果类别结构为空, 是需要构造的新类别   
  416.   struct Qdisc *new_q;   
  417.   int prio;   
  418.   /* check for valid classid */  
  419. // 类别ID合法性检查   
  420.   if (!classid || TC_H_MAJ(classid ^ sch->handle)   
  421.       || htb_find(classid, sch))   
  422.    goto failure;   
  423.   /* check maximal depth */  
  424. // 如果祖父节点层次都小于2, 也就是最大是1, 表示HTB节点树太深了, 叶子节点都没法表示了   
  425.   if (parent && parent->parent && parent->parent->level < 2) {   
  426.    printk(KERN_ERR "htb: tree is too deep\n");   
  427.    goto failure;   
  428.   }   
  429.   err = -ENOBUFS;   
  430. // 分配类别空间   
  431.   if ((cl = kzalloc(sizeof(*cl), GFP_KERNEL)) == NULL)   
  432.    goto failure;   
  433. // 初始化引用计数   
  434.   cl->refcnt = 1;   
  435. // 初始化兄弟链表   
  436.   INIT_LIST_HEAD(&cl->sibling);   
  437. // 初始化哈希链表   
  438.   INIT_HLIST_NODE(&cl->hlist);   
  439. // 初始化子节点链表   
  440.   INIT_LIST_HEAD(&cl->children);   
  441. // 初始化丢包链表   
  442.   INIT_LIST_HEAD(&cl->un.leaf.drop_list);   
  443. // 设置为空节点(父节点是本身)   
  444.   RB_CLEAR_NODE(&cl->pq_node);   
  445. // 初始化self or feed tree节点   
  446.   for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)   
  447.    RB_CLEAR_NODE(&cl->node[prio]);   
  448.   /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)  
  449.      so that can't be used inside of sch_tree_lock  
  450.      -- thanks to Karlis Peisenieks */  
  451. // 新的流控节点缺省是使用pfifo   
  452.   new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);   
  453.   sch_tree_lock(sch);   
  454. // 以下调整父节点的状态参数   
  455.   if (parent && !parent->level) {   
  456. // 如果父节点原先是叶子节点, 将其转为中间节点, 因为现在已经有新的叶子节点作为其子节点   
  457.    /* turn parent into inner node */  
  458. // 释放父节点的流控结构   
  459.    sch->q.qlen -= parent->un.leaf.q->q.qlen;   
  460.    qdisc_destroy(parent->un.leaf.q);   
  461. // 如果该父节点正处于活动情况, 停止   
  462.    if (parent->prio_activity)   
  463.     htb_deactivate(q, parent);   
  464.    /* remove from evt list because of level change */  
  465. // 如果不是HTB_CAN_SEND模式, 说明该节点在等待节点树中, 从该树中删除   
  466.    if (parent->cmode != HTB_CAN_SEND) {   
  467.     htb_safe_rb_erase(&parent->pq_node, q->wait_pq);   
  468.     parent->cmode = HTB_CAN_SEND;   
  469.    }   
  470. // 更新父节点的层次, 如果不存在祖父节点, 则层次为根节点, 否则使用祖父节点的层次值   
  471.    parent->level = (parent->parent ? parent->parent->level   
  472.       : TC_HTB_MAXDEPTH) - 1;   
  473. // 不再使用内部叶子结构, 而是改为使用HTB内部结构, 参数清零   
  474.    memset(&parent->un.inner, 0, sizeof(parent->un.inner));   
  475.   }   
  476.   /* leaf (we) needs elementary qdisc */  
  477. // 设置类别结构的叶子流控节点   
  478.   cl->un.leaf.q = new_q ? new_q : &noop_qdisc;   
  479. // 类别结构的ID和父   
  480.   cl->classid = classid;   
  481.   cl->parent = parent;   
  482.   /* set class to be in HTB_CAN_SEND state */  
  483. // 令牌和峰值令牌   
  484.   cl->tokens = hopt->buffer;   
  485.   cl->ctokens = hopt->cbuffer;   
  486. // 缓冲区大小   
  487.   cl->mbuffer = PSCHED_JIFFIE2US(HZ * 60); /* 1min */  
  488. // 初始化时间   
  489.   PSCHED_GET_TIME(cl->t_c);   
  490. // 模式为可以发送模式   
  491.   cl->cmode = HTB_CAN_SEND;   
  492.   /* attach to the hash list and parent's family */  
  493. // 挂接到哈希链表   
  494.   hlist_add_head(&cl->hlist, q->hash + htb_hash(classid));   
  495. // 添加到父节点的子节点链表   
  496.   list_add_tail(&cl->sibling,   
  497.          parent ? &parent->children : &q->root);   
  498.  } else  
  499.   sch_tree_lock(sch);   
  500.  /* it used to be a nasty bug here, we have to check that node  
  501.     is really leaf before changing cl->un.leaf ! */  
  502.  if (!cl->level) {   
  503. // 如果是叶子节点, 设置其定额, 当出现赤字时会按定额大小增加   
  504.   cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum;   
  505. // 如果计算出的定额量太小或太大, 说明rate2quantum参数该调整了, 这就是tc命令中的r2q参数   
  506. // 对于不同的带宽, 要选择不同的r2q值   
  507.   if (!hopt->quantum && cl->un.leaf.quantum < 1000) {   
  508. // 定额太小   
  509.    printk(KERN_WARNING   
  510.           "HTB: quantum of class %X is small. Consider r2q   
  511. change.\n",   
  512.           cl->classid);   
  513.    cl->un.leaf.quantum = 1000;   
  514.   }   
  515.   if (!hopt->quantum && cl->un.leaf.quantum > 200000) {   
  516. // 定额太大   
  517.    printk(KERN_WARNING   
  518.           "HTB: quantum of class %X is big. Consider r2q   
  519. change.\n",   
  520.           cl->classid);   
  521.    cl->un.leaf.quantum = 200000;   
  522.   }   
  523.   if (hopt->quantum)   
  524.    cl->un.leaf.quantum = hopt->quantum;   
  525. // 设置该节点的优先权值, 最大限制为TC_HTB_NUMPRIO - 1   
  526.   if ((cl->un.leaf.prio = hopt->prio) >= TC_HTB_NUMPRIO)   
  527.    cl->un.leaf.prio = TC_HTB_NUMPRIO - 1;   
  528.  }   
  529. // 缓冲区   
  530.  cl->buffer = hopt->buffer;   
  531. // 峰值流控缓冲区   
  532.  cl->cbuffer = hopt->cbuffer;   
  533. // 如果该类别原先有速率控制结构, 先释放掉再更新为新的速率控制结构   
  534. // 普通速率控制结构更新   
  535.  if (cl->rate)   
  536.   qdisc_put_rtab(cl->rate);   
  537.  cl->rate = rtab;   
  538. // 峰值速率控制结构更新   
  539.  if (cl->ceil)   
  540.   qdisc_put_rtab(cl->ceil);   
  541.  cl->ceil = ctab;   
  542.  sch_tree_unlock(sch);   
  543.  *arg = (unsigned long)cl;   
  544.  return 0;   
  545. failure:   
  546.  if (rtab)   
  547.   qdisc_put_rtab(rtab);   
  548.  if (ctab)   
  549.   qdisc_put_rtab(ctab);   
  550.  return err;   
  551. }   
  552.     
  553. 5.11.2.6 查找过滤规则表   
  554.   
  555. static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)   
  556. {   
  557.  struct htb_sched *q = qdisc_priv(sch);   
  558.  struct htb_class *cl = (struct htb_class *)arg;   
  559. // 如果类别结构非空,使用类别结构的过滤表, 否则使用HTB私有结构的过滤表   
  560.  struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;   
  561.  return fl;   
  562. }   
  563.   
  564. 5.11.2.7 绑定过滤器   
  565.   
  566. static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,   
  567.          u32 classid)   
  568. {   
  569.  struct htb_sched *q = qdisc_priv(sch);   
  570. // 根据类别ID查找类别结构   
  571.  struct htb_class *cl = htb_find(classid, sch);   
  572.  /*if (cl && !cl->level) return 0;  
  573.     The line above used to be there to prevent attaching filters to  
  574.     leaves. But at least tc_index filter uses this just to get class  
  575.     for other reasons so that we have to allow for it.  
  576.     ----  
  577.     19.6.2002 As Werner explained it is ok - bind filter is just  
  578.     another way to "lock" the class - unlike "get" this lock can  
  579.     be broken by class during destroy IIUC.  
  580.   */  
  581. // 如果流控类别结构有效, 增加其使用计数   
  582.  if (cl)   
  583.   cl->filter_cnt++;   
  584.  else  
  585. // 否则是增加整个HTB流控结构的使用计数   
  586.   q->filter_cnt++;   
  587.  return (unsigned long)cl;   
  588. }   
  589.   
  590. 5.11.2.8 解开过滤器   
  591.   
  592. static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)   
  593. {   
  594.  struct htb_sched *q = qdisc_priv(sch);   
  595.  struct htb_class *cl = (struct htb_class *)arg;   
  596. // 实际就是对过滤器引用计数减一   
  597.  if (cl)   
  598.   cl->filter_cnt--;   
  599.  else  
  600.   q->filter_cnt--;   
  601. }   
  602.   
  603. 5.11.2.9 遍历HTB   
  604.   
  605. static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)   
  606. {   
  607. // HTB流控私有数据   
  608.  struct htb_sched *q = qdisc_priv(sch);   
  609.  int i;   
  610. // 如果设置停止标志, 返回   
  611.  if (arg->stop)   
  612.   return;   
  613. // 遍历所有HTB哈希表   
  614.  for (i = 0; i < HTB_HSIZE; i++) {   
  615.   struct hlist_node *p;   
  616.   struct htb_class *cl;   
  617. // 遍历哈希表中每个元素, 即HTB类别结构   
  618.   hlist_for_each_entry(cl, p, q->hash + i, hlist) {   
  619. // 如果要跳过skip个开始的一些节点, 跳过这些节点   
  620.    if (arg->count < arg->skip) {   
  621.     arg->count++;   
  622.     continue;   
  623.    }   
  624. // 对类别结构进行相关操作   
  625.    if (arg->fn(sch, (unsigned long)cl, arg) < 0) {   
  626.     arg->stop = 1;   
  627.     return;   
  628.    }   
  629.    arg->count++;   
  630.   }   
  631.  }   
  632. }   
  633.   
  634. 5.11.2.10 类别参数输出   
  635.   
  636. static int htb_dump_class(struct Qdisc *sch, unsigned long arg,   
  637.      struct sk_buff *skb, struct tcmsg *tcm)   
  638. {   
  639.  struct htb_class *cl = (struct htb_class *)arg;   
  640.  unsigned char *b = skb->tail;   
  641.  struct rtattr *rta;   
  642.  struct tc_htb_opt opt;   
  643.  spin_lock_bh(&sch->dev->queue_lock);   
  644. // 父节点的类别ID   
  645.  tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;   
  646. // 本节点的类别ID   
  647.  tcm->tcm_handle = cl->classid;   
  648. // 如果是叶子节点, 提供叶子节点的流控节点的ID   
  649.  if (!cl->level && cl->un.leaf.q)   
  650.   tcm->tcm_info = cl->un.leaf.q->handle;   
  651.  rta = (struct rtattr *)b;   
  652.  RTA_PUT(skb, TCA_OPTIONS, 0, NULL);   
  653. // 以下提供该类别的各种参数   
  654.  memset(&opt, 0, sizeof(opt));   
  655. // 速率   
  656.  opt.rate = cl->rate->rate;   
  657. // 数据缓冲区   
  658.  opt.buffer = cl->buffer;   
  659. // 峰值速率   
  660.  opt.ceil = cl->ceil->rate;   
  661. // 峰值数据缓冲区   
  662.  opt.cbuffer = cl->cbuffer;   
  663. // 定额   
  664.  opt.quantum = cl->un.leaf.quantum;   
  665. // 优先权值   
  666.  opt.prio = cl->un.leaf.prio;   
  667. // 层次值   
  668.  opt.level = cl->level;   
  669.  RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);   
  670. // 实际数据长度   
  671.  rta->rta_len = skb->tail - b;   
  672.  spin_unlock_bh(&sch->dev->queue_lock);   
  673.  return skb->len;   
  674. rtattr_failure:   
  675.  spin_unlock_bh(&sch->dev->queue_lock);   
  676.  skb_trim(skb, b - skb->data);   
  677.  return -1;   
  678. }   
  679.   
  680. 5.11.2.10 类别统计信息输出   
  681.   
  682. static int  
  683. htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)   
  684. {   
  685.  struct htb_class *cl = (struct htb_class *)arg;   
  686. #ifdef HTB_RATECM   
  687. // HTB_EWMAC=2, HTB_HSIZE=16   
  688. // 字节和包速率参数   
  689.  cl->rate_est.bps = cl->rate_bytes / (HTB_EWMAC * HTB_HSIZE);   
  690.  cl->rate_est.pps = cl->rate_packets / (HTB_EWMAC * HTB_HSIZE);   
  691. #endif   
  692. // 叶子节点, 提供当前内部流控结构的队列长度   
  693.  if (!cl->level && cl->un.leaf.q)   
  694.   cl->qstats.qlen = cl->un.leaf.q->q.qlen;   
  695. // 令牌数   
  696.  cl->xstats.tokens = cl->tokens;   
  697. // 峰值令牌数   
  698.  cl->xstats.ctokens = cl->ctokens;   
  699. // 分别将基本参数, 速率参数, 队列参数拷贝到目的缓存, 这些都是标准参数   
  700.  if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||   
  701.      gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||   
  702.      gnet_stats_copy_queue(d, &cl->qstats) < 0)   
  703.   return -1;   
  704. // 将应用数据(HTB自身统计数据)拷贝到目的缓存   
  705.  return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));   
  706. }   
  707.     
  708. ...... 待续 ......  
# 数据结构 # list
Logo
Linux

更多推荐

网卡速率和双工模式的配置

http://linux.chinaitlab.com/system/792187.html1、mii-tool 配置网络设备协商方式的工具；    1.1 mii-tool 介绍；    mii-tool - view, manipulate media-independent interface status （mii-tool 是查看，管理介质的网络接口的状态）

avatar Linux

Linux虚拟文件系统之文件系统卸载（sys_umount())

Linux中卸载文件系统由umount系统调用实现，入口函数为sys_umount()。较于文件系统的安装较为简单，下面是具体的实现。1. /*sys_umont系统调用*/2. SYSCALL_DEFINE2(umount, char __user *, name, int, flags)3. {4.struct path path;

avatar Linux

Linux系统下超级终端Minicom的使用方法（例如：连接交换机，路由器等）转http://baike.baidu.com/view/2911642.htm?fr=ala0_1

<br />　　Linux系统下超级终端Minicom的使用方法 <br />　　Linux下的Minicom的功能与下的超级终端功能相似，适于在通过超级终端对设备的管理以及对嵌入操作系统的升级，现写出Minicom的使用手册： <br />　　1． 启动minicom <br />　　以root权限登录系统 <br />　　使用命令 <br />　　minicom –s 则minicom启动，屏

avatar Linux