htb internel 转自：http://blog.csdn.net/liujianfeng1984/article/details/41922085 之前通过《默认FIFO_FAST出口排队规则分析》、《ingress入口排队规则分析》分析，已经对排队规则的基础架框有了简单的了解。那两种排队规则都是无类的，这里选出可以分类的HTB排队规则进行分析。
当前实例分析的基本对象关联图
//在eth0设备上创建一个根HTB排队规则，当未匹配任何过滤器时，将报文放入ID为20 //的分类中 tc qdisc add dev eth0 root handle 1: htb default 20
//在根HTB排队规则上创建ID为1的分类 tc class add dev eth0 parent 1: classid 1:1 htb rate 6mbit burst 15k
//在ID为1的分类上分别创建两个ID为10、ID为20的分类 tc class add dev eth0 parent 1:1 classid 1:10 htb rate 5mbit burst 15k tc class add dev eth0 parent 1:1 classid 1:20 htb rate 3mbit ceil 6mbit burst 15k
//创建两个U32分类器 U32=”tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32” U32matchipdport800xffffflowid1:10 U32 match ip sport 25 0xffff flowid 1:20
//初始化，获取每纳秒对应多少TICKET tc_core_init(); fp = fopen(“/proc/net/psched”, “r”); fscanf(fp, “xxx”, &t2us, &us2t, &clock_res); fclose(fp);
if (clock_res == 1000000000) t2us = us2t;
clock_factor = (double)clock_res / TIME_UNITS_PER_SEC; tick_in_usec = (double)t2us / us2t * clock_factor;
//创建一个ROUTE类型的netlink套接口 rtnl_open(&rth, 0) rtnl_open_byproto(rth, subscriptions, NETLINK_ROUTE); rth->fd = socket(AF_NETLINK, SOCK_RAW | SOCK_CLOEXEC, protocol); setsockopt(rth->fd,SOL_SOCKET,SO_SNDBUF,&sndbuf,sizeof(sndbuf)) setsockopt(rth->fd,SOL_SOCKET,SO_RCVBUF,&rcvbuf,sizeof(rcvbuf)) rth->local.nl_family = AF_NETLINK; rth->local.nl_groups = subscriptions; //0 bind(rth->fd, (struct sockaddr*)&rth->local, sizeof(rth->local)) rth->seq = time(NULL);
do_cmd(argc-1, argv+1); if (matches(*argv, “qdisc”) == 0) //执行设置排队规则的命令 do_qdisc(argc-1, argv+1); if (matches(*argv, “add”) == 0) tc_qdisc_modify(RTM_NEWQDISC, NLM_F_EXCL|NLM_F_CREATE, argc-1, argv+1); req.n.nlmsg_len = NLMSG_LENGTH(sizeof(struct tcmsg)); req.n.nlmsg_flags = NLM_F_REQUEST|flags; req.n.nlmsg_type = cmd; //RTM_NEWQDISC req.t.tcm_family = AF_UNSPEC;
while (argc > 0) if (strcmp(*argv, “dev”) == 0) NEXT_ARG(); strncpy(d, *argv, sizeof(d)-1); //eth0 else if (strcmp(*argv, “root”) == 0) req.t.tcm_parent = TC_H_ROOT; else if (strcmp(*argv, “handle”) == 0) NEXT_ARG(); get_qdisc_handle(&handle, *argv) req.t.tcm_handle = handle; //0x00010000 else //如果有/usr/lib/tc/htb.so动态库中则从中获 //取htb_qdisc_util符号结构，否则检测当前tc //程序是否有htb_qdisc_util符号结构则从中获取 //，否则返回q 为空。 q = get_qdisc_kind(k);
//在消息尾部追加KIND属性 //rta->rta_type = type; //TCA_KIND //rta->rta_len = len; //属性值为 “htb” addattr_l(&req.n, sizeof(req), TCA_KIND, k, strlen(k)+1);
//当前q为htb_qdisc_util，使用其中parse_qopt回调进行其它参数 //解析，当前回调函数为htb_parse_opt q->parse_qopt(q, argc, argv, &req.n) htb_parse_opt //默认参数 opt.rate2quantum = 10; opt.version = 3;
while (argc > 0) if (matches(*argv, “default”) == 0) NEXT_ARG(); get_u32(&opt.defcls, *argv, 16) //20
//添加扩展属性OPTIONS，标记后面都是htb的选项 addattr_l(n, 1024, TCA_OPTIONS, NULL, 0);
//添加扩展属性HTB_INIT addattr_l(n, 2024, TCA_HTB_INIT, &opt, NLMSG_ALIGN(sizeof(opt)));
//根据接口名获取接口索引 if (d[0]) idx = ll_name_to_index(d) req.t.tcm_ifindex = idx;
//给内核发送该netlink消息 rtnl_talk(&rth, &req.n, 0, 0, NULL)
rtnl_close(&rth);
用户侧发出RTM_NEWQDISC套接口消息后，在内核侧对应的处理回调函数为tc_modify_qdisc，该函数是在pktsched_init中初始化的。
tc_modify_qdisc tcm = NLMSG_DATA(n); clid = tcm->tcm_parent; //当前用户侧传入值为 TC_H_ROOT
//根据设备索引获取设备对象，上面用户侧传入设备名为eth0 dev = __dev_get_by_index(tcm->tcm_ifindex)
if (clid) if (clid != TC_H_ROOT) //当前为根排队规则，不走此流程 else q = dev->qdisc_sleeping;
//当前设备存储的是默认的排队规则，则忽略 if (q && q->handle == 0) q = NULL;
if (!q || !tcm->tcm_handle || q->handle != tcm->tcm_handle) if (tcm->tcm_handle) //用户侧传入为特定的0x1 //当前设备的qdisc_list排队规则链表中不含有此规则，进行创建 if ((q = qdisc_lookup(dev, tcm->tcm_handle)) == NULL) goto create_n_graft;
create_n_graft:
//创建排队规则 q = qdisc_create(dev, tcm->tcm_handle, tca, &err); //从已经注册到qdisc_base链表中获取匹配排队规则，当前htb已经注册 //，则ops = htb_qdisc_ops ops = qdisc_lookup_ops(kind);
sch = qdisc_alloc(dev, ops); INIT_LIST_HEAD(&sch->list); skb_queue_head_init(&sch->q); //初始化规则中的SKB队列 sch->ops = ops; //htb_qdisc_ops sch->enqueue = ops->enqueue; //ingress_enqueue sch->dequeue = ops->dequeue; //ingress_dequeue sch->dev = dev; //eth0设备对象 dev_hold(dev); //设备对象引用递增 sch->stats_lock = &dev->queue_lock; atomic_set(&sch->refcnt, 1);
sch->handle = handle; //0x00010000
//使用排队规则中的初始化回调进行初始化，当前htb的回调函数为 //htb_init ops->init(sch, tca[TCA_OPTIONS-1]) htb_init(tca[TCA_OPTIONS-1]) htb_sched *q = qdisc_priv(sch);
//HTB_INIT属性 gopt = RTA_DATA(tb[TCA_HTB_INIT - 1]);
//初始化根类链表 INIT_LIST_HEAD(&q->root);
for (i = 0; i < HTB_HSIZE; i++) INIT_HLIST_HEAD(q->hash + i);
for (i = 0; i < TC_HTB_NUMPRIO; i++) INIT_LIST_HEAD(q->drops + i);
init_timer(&q->timer); skb_queue_head_init(&q->direct_queue); q->direct_qlen = sch->dev->tx_queue_len; if (q->direct_qlen < 2) q->direct_qlen = 2; q->timer.function = htb_timer; q->timer.data = (unsigned long)sch;
//启动了速率定时器，每秒触发一下，其中htb_rate_timer函数在每秒 //触发会都会根据q->recmp_bucket索引来获取q->hash中的一个 //HASH链表，对该HASH链表所有条目进行速率计算，之后递增 //q->recmp_bucket索引，准备下一秒后对下一个HASH链表进行速 //率计算。当前计算方法也比较简单 //#define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0 //RT_GEN(cl->sum_bytes, cl->rate_bytes); //RT_GEN(cl->sum_packets, cl->rate_packets); init_timer(&q->rttim); q->rttim.function = htb_rate_timer; q->rttim.data = (unsigned long)sch; q->rttim.expires = jiffies + HZ; add_timer(&q->rttim);
if ((q->rate2quantum = gopt->rate2quantum) < 1) //用户默认值为10 q->rate2quantum = 1;
q->defcls = gopt->defcls; //20
//将当前排队规则加入到设备的qdisc_list链表中 qdisc_lock_tree(dev); list_add_tail(&sch->list, &dev->qdisc_list); qdisc_unlock_tree(dev);
//排队规则嫁接处理 qdisc_graft(dev, p, clid, q, &old_q); if (parent == NULL) //当前为根排队规则，未有父类 dev_graft_qdisc(dev, new); //设备激活的情况下，先去激活 if (dev->flags & IFF_UP) dev_deactivate(dev);
oqdisc = dev->qdisc_sleeping;
//假设当前仅使用的默认的fifo_fast排队规则，则当前这个老的排队规则 //已经存在，需要将老的排队规则进行复位，这里fifo_fast的reset回调函 //数为pfifo_fast_reset if (oqdisc && atomic_read(&oqdisc->refcnt) <= 1) qdisc_reset(oqdisc); pfifo_fast_reset //丢弃每个频道队列中的所有报文 for (prio = 0; prio < PFIFO_FAST_BANDS; prio++) __qdisc_reset_queue(qdisc, list + prio);
qdisc->qstats.backlog = 0; qdisc->q.qlen = 0;
//将新建的排队规则设置到qdisc_sleeping，qdisc的当前规则指向空规则 //noop_qdisc dev->qdisc_sleeping = qdisc; dev->qdisc = &noop_qdisc;
if (dev->flags & IFF_UP) //设备激活 dev_activate(dev); if (dev->qdisc_sleeping == &noop_qdisc) //当前已经有根排队规则，不走此流程
//没有载波则直接返回 if (!netif_carrier_ok(dev)) return;
//当前使用的排队规则设置为已经选择的根排队规则 //启动看门狗。 rcu_assign_pointer(dev->qdisc, dev->qdisc_sleeping); if (dev->qdisc != &noqueue_qdisc) dev->trans_start = jiffies; dev_watchdog_up(dev);
//发送netlink消息，告知添加成功，并且老的已经删除 qdisc_notify(skb, n, clid, old_q, q);
//将老的排队规则去除 qdisc_destroy(old_q); //属于内建规则，或者还有其它模块引用，则不进行去除。 if (qdisc->flags & TCQ_F_BUILTIN || !atomic_dec_and_test(&qdisc->refcnt)) return;
//从设备的排队规则链表中去除 list_del(&qdisc->list);
//如果老的排队规则有reset、destroy回调，则进行处理 if (ops->reset) ops->reset(qdisc); if (ops->destroy) ops->destroy(qdisc);
//资源销毁 module_put(ops->owner); dev_put(qdisc->dev); call_rcu(&qdisc->q_rcu, __qdisc_destroy);
//初始化，获取每纳秒对应多少TICKET tc_core_init(); fp = fopen(“/proc/net/psched”, “r”); fscanf(fp, “xxx”, &t2us, &us2t, &clock_res); fclose(fp);
if (clock_res == 1000000000) t2us = us2t;
clock_factor = (double)clock_res / TIME_UNITS_PER_SEC; tick_in_usec = (double)t2us / us2t * clock_factor;
//创建一个ROUTE类型的netlink套接口 rtnl_open(&rth, 0) rtnl_open_byproto(rth, subscriptions, NETLINK_ROUTE); rth->fd = socket(AF_NETLINK, SOCK_RAW | SOCK_CLOEXEC, protocol); setsockopt(rth->fd,SOL_SOCKET,SO_SNDBUF,&sndbuf,sizeof(sndbuf)) setsockopt(rth->fd,SOL_SOCKET,SO_RCVBUF,&rcvbuf,sizeof(rcvbuf)) rth->local.nl_family = AF_NETLINK; rth->local.nl_groups = subscriptions; //0 bind(rth->fd, (struct sockaddr*)&rth->local, sizeof(rth->local)) rth->seq = time(NULL);
do_cmd(argc-1, argv+1); if (matches(*argv, “class”) == 0) do_class(argc-1, argv+1); //创建新的类 tc_class_modify(RTM_NEWTCLASS, NLM_F_EXCL|NLM_F_CREATE, argc-1, argv+1); req.n.nlmsg_len = NLMSG_LENGTH(sizeof(struct tcmsg)); req.n.nlmsg_flags = NLM_F_REQUEST|flags; req.n.nlmsg_type = cmd; //RTM_NEWTCLASS req.t.tcm_family = AF_UNSPEC;
while (argc > 0) if (strcmp(*argv, “dev”) == 0) NEXT_ARG(); strncpy(d, *argv, sizeof(d)-1); //eth0 else if (strcmp(*argv, “parent”) == 0) NEXT_ARG(); get_tc_classid(&handle, *argv) req.t.tcm_parent = handle; //0x00010000 else if (strcmp(*argv, “classid”) == 0) NEXT_ARG(); get_tc_classid(&handle, *argv) req.t.tcm_handle = handle; //0x00010001 else //如果有/usr/lib/tc/htb.so动态库中则从中获取htb_qdisc_util符 //号结构，否则检测当前tc程序是否有htb_qdisc_util符号结构则 //从中获取，否则返回q 为空。 q = get_qdisc_kind(k);
//添加KIND属性项，当前值为“htb” addattr_l(&req.n, sizeof(req), TCA_KIND, k, strlen(k)+1);
//使用当前扩展排队规则的parse_copt回调去解析后续命令字符，当前 //htb的回调为htb_parse_class_opt q->parse_copt(q, argc, argv, &req.n) htb_parse_class_opt mtu = 1600;
while (argc > 0) if (strcmp(*argv, “rate”) == 0) NEXT_ARG(); get_rate64(&rate64, argv) //6 1000000 / 8 else if (matches(*argv, “burst”) == 0) NEXT_ARG(); //buffer = 15 * 1024 //cell_log = -1 get_size_and_cell(&buffer, &cell_log, *argv) if (!ceil64) ceil64 = rate64;
//超出32位最大值，则转换为全1？ opt.rate.rate = (rate64 >= (1ULL << 32)) ? ~0U : rate64; opt.ceil.rate = (ceil64 >= (1ULL << 32)) ? ~0U : ceil64;
//如果cbuffer为设置，则取值为当前mtu值加上最大速率下 //每ticket单位的比特数 if (!cbuffer) cbuffer = ceil64 / get_hz() + mtu;
opt.ceil.overhead = overhead; //0 opt.rate.overhead = overhead; //0
opt.ceil.mpu = mpu; //0 opt.rate.mpu = mpu; //0
//计算最小速率表 //cell_log = -1 //mtu = 1600 //linklayer = LINKLAYER_ETHERNET tc_calc_rtable(&opt.rate, rtab, cell_log, mtu, linklayer) //根据最大传输单元计算需要多少槽我理解是不可能每个 //字节都有准确速率，所以划定字节范围，从多少字节到 //多少字节的速率相同。 if (cell_log < 0) cell_log = 0; while ((mtu >> cell_log) > 255) cell_log++;
for (i=0; i<256; i++) //校正当前槽位的字节大小。这个算法比较简单，当前 //链路类型为以太网，则包根据原值处理，不会影响包 //大小。Mpu为最小包大小，如果槽位字节小于mpu， //则校正为mpu的值。 sz = tc_adjust_size((i + 1) << cell_log, mpu, linklayer);
//根据当前槽位字节大小，及用户配置的速率，计算当 //前槽位所需ticket时间 rtab[i] = tc_calc_xmittime(bps, sz);
r->cell_align=-1; r->cell_log=cell_log; r->linklayer = (linklayer & TC_LINKLAYER_MASK);
//计算单包正常速率下的传送峰值，这里通过包大小转换成所 //需要的ticket时间 opt.buffer = tc_calc_xmittime(rate64, buffer);
//计算最大速率表，仅在发包速率大于最小速率后，租借模式下 //有效。 tc_calc_rtable(&opt.ceil, ctab, ccell_log, mtu, linklayer)
//计算单包在租借模速率作用下，传送的峰值。 opt.cbuffer = tc_calc_xmittime(ceil64, cbuffer);
//添加扩展属性OPTIONS，标记后面都是htb的选项 addattr_l(n, 1024, TCA_OPTIONS, NULL, 0);
//超出32位，则添加扩展属性HTB_RATE64 //超出32位，则添加扩展属性HTB_CEIL64 if (rate64 >= (1ULL << 32)) addattr_l(n, 1124, TCA_HTB_RATE64, &rate64, sizeof(rate64)); if (ceil64 >= (1ULL << 32)) addattr_l(n, 1224, TCA_HTB_CEIL64, &ceil64, sizeof(ceil64));
//添加扩展属性HTB_PARMS addattr_l(n, 2024, TCA_HTB_PARMS, &opt, sizeof(opt));
//添加扩展属性HTB_RTAB addattr_l(n, 3024, TCA_HTB_RTAB, rtab, 1024);
//添加扩展属性HTB_CTAB addattr_l(n, 4024, TCA_HTB_CTAB, ctab, 1024);
//根据接口名获取接口索引 if (d[0]) idx = ll_name_to_index(d) req.t.tcm_ifindex = idx;
//给内核发送该netlink消息 rtnl_talk(&rth, &req.n, 0, 0, NULL)
rtnl_close(&rth);
用户侧发出RTM_NEWTCLASS套接口消息后，在内核侧对应的处理回调函数为tc_ctl_tclass，该函数是在pktsched_init中初始化的。
tc_ctl_tclass pid = tcm->tcm_parent //父类ID 0x00010000 clid = tcm->tcm_handle; //创建类ID 0x00010001 qid = TC_H_MAJ(clid); //队列ID 0x00010000
//eth0设备对象 dev = __dev_get_by_index(tcm->tcm_ifindex))
if (pid != TC_H_ROOT) pid = TC_H_MAKE(qid, pid); //0x00010000
//从当前设备的qdisc_list链表中找到已经创建的排队规则，当前q为之前创建的HTB q = qdisc_lookup(dev, qid)
//HTB的回调组为 cops = htb_class_ops cops = q->ops->cl_ops;
clid = TC_H_MAKE(qid, clid); //0x00010001
//get的回调函数为htb_get cl = cops->get(q, clid); htb_get htb_class *cl = htb_find(classid, sch); //使用类ID做HASH KEY在当前队列的HASH链表中查找已经创建的类 hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) if (cl->classid == handle) return cl; return NULL;
//如果找到则增加引用计数 if (cl) cl->refcnt++; return (unsigned long)cl;
//当前环境还没有该类存在，进行新类的属性设置 new_cl = cl; //当前回调为 htb_change_class cops->change(q, clid, pid, tca, &new_cl);/ htb_change_class //opt指向扩展属性基值索引，后续rtattr_parse_nested进行属性查找都从该 //基值索引之外进行查找。 rtattr *opt = tca[TCA_OPTIONS - 1];
//查看枚举定义，TCA_HTB_RTAB值是最后一个，所以rtattr_parse_nested //函数会把用户设置的所有扩展参数存储到临时变量tb中。 //enum //{ // TCA_HTB_UNSPEC, // TCA_HTB_PARMS, // TCA_HTB_INIT, // TCA_HTB_CTAB, // TCA_HTB_RTAB, // __TCA_HTB_MAX, //}; rtattr_parse_nested(tb, TCA_HTB_RTAB, opt)
//parentid = 0x00010000 //以类ID为HASH KEY向当前队规则的hash链表中查找父类，当前还未存在。 parent = htb_find(parentid, sch); htb_sched *q = qdisc_priv(sch); hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) if (cl->classid == handle) return cl; return NULL;
//取用户配置工具设置的HTB参数属性 hopt = RTA_DATA(tb[TCA_HTB_PARMS - 1]);
//将最小速率表加入到全局qdisc_rtab_list链表中 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB - 1]);
//将最大速率表加入到全局qdisc_rtab_list链表中 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB - 1]);
//当前为新类进行创建 if (!cl) cl = kzalloc(sizeof(*cl), GFP_KERNEL) cl->refcnt = 1; INIT_LIST_HEAD(&cl->sibling); INIT_HLIST_NODE(&cl->hlist); INIT_LIST_HEAD(&cl->children); INIT_LIST_HEAD(&cl->un.leaf.drop_list); RB_CLEAR_NODE(&cl->pq_node);
for (prio = 0; prio < TC_HTB_NUMPRIO; prio++) RB_CLEAR_NODE(&cl->node[prio]);
//创建默认的pfifo排队规则，同时将该排队规则的父亲设置为当前类 //sch->parent = parentid; 0x00010001 new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
//当前新建的类的默认排队规则设置为pfifo cl->un.leaf.q = new_q;
cl->classid = classid; //0x00010001 cl->parent = parent; //NULL
cl->tokens = hopt->buffer; //正常速率下单包峰值 cl->ctokens = hopt->cbuffer; //借用速率下单包峰值 cl->mbuffer = PSCHED_JIFFIE2US(HZ * 60); PSCHED_GET_TIME(cl->t_c); cl->cmode = HTB_CAN_SEND; //初始时可以发送报文
//当新建的类加入到根排队规则的hash表中 hlist_add_head(&cl->hlist, q->hash + htb_hash(classid));
//将新建的类加入到根排队规则的root链表中 list_add_tail(&cl->sibling, &q->root);
if (!cl->level) //在htb_init时，rate2quantum值默认为1 //设置quantum值，该值用于在进行带宽租借时的单位量 cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum; if (!hopt->quantum && cl->un.leaf.quantum < 1000) cl->un.leaf.quantum = 1000; if (!hopt->quantum && cl->un.leaf.quantum > 200000) cl->un.leaf.quantum = 200000;
cl->un.leaf.prio = hopt->prio; //0
cl->quantum = cl->un.leaf.quantum; cl->prio = cl->un.leaf.prio;
cl->buffer = hopt->buffer; //正常速率下单包峰值 cl->cbuffer = hopt->cbuffer; //借用速率下单包峰值
//设置当前类的最小、最大速率表 cl->rate = rtab; cl->ceil = ctab;
//发送netlink消息，告知添加成功 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
//初始化，获取每纳秒对应多少TICKET tc_core_init(); fp = fopen(“/proc/net/psched”, “r”); fscanf(fp, “xxx”, &t2us, &us2t, &clock_res); fclose(fp);
if (clock_res == 1000000000) t2us = us2t;
clock_factor = (double)clock_res / TIME_UNITS_PER_SEC; tick_in_usec = (double)t2us / us2t * clock_factor;
//创建一个ROUTE类型的netlink套接口 rtnl_open(&rth, 0) rtnl_open_byproto(rth, subscriptions, NETLINK_ROUTE); rth->fd = socket(AF_NETLINK, SOCK_RAW | SOCK_CLOEXEC, protocol); setsockopt(rth->fd,SOL_SOCKET,SO_SNDBUF,&sndbuf,sizeof(sndbuf)) setsockopt(rth->fd,SOL_SOCKET,SO_RCVBUF,&rcvbuf,sizeof(rcvbuf)) rth->local.nl_family = AF_NETLINK; rth->local.nl_groups = subscriptions; //0 bind(rth->fd, (struct sockaddr*)&rth->local, sizeof(rth->local)) rth->seq = time(NULL);
do_cmd(argc-1, argv+1); if (matches(*argv, “class”) == 0) do_class(argc-1, argv+1); //创建新的类 tc_class_modify(RTM_NEWTCLASS, NLM_F_EXCL|NLM_F_CREATE, argc-1, argv+1); req.n.nlmsg_len = NLMSG_LENGTH(sizeof(struct tcmsg)); req.n.nlmsg_flags = NLM_F_REQUEST|flags; req.n.nlmsg_type = cmd; //RTM_NEWTCLASS req.t.tcm_family = AF_UNSPEC;
while (argc > 0) if (strcmp(*argv, “dev”) == 0) NEXT_ARG(); strncpy(d, *argv, sizeof(d)-1); //eth0 else if (strcmp(*argv, “parent”) == 0) NEXT_ARG(); get_tc_classid(&handle, *argv) req.t.tcm_parent = handle; //0x00010001 else if (strcmp(*argv, “classid”) == 0) NEXT_ARG(); get_tc_classid(&handle, *argv) req.t.tcm_handle = handle; //0x00010014 (0x14 = 20) else //如果有/usr/lib/tc/htb.so动态库中则从中获取htb_qdisc_util符 //号结构，否则检测当前tc程序是否有htb_qdisc_util符号结构则 //从中获取，否则返回q 为空。 q = get_qdisc_kind(k);
//添加KIND属性项，当前值为“htb” addattr_l(&req.n, sizeof(req), TCA_KIND, k, strlen(k)+1);
//使用当前扩展排队规则的parse_copt回调去解析后续命令字符，当前 //htb的回调为htb_parse_class_opt q->parse_copt(q, argc, argv, &req.n) htb_parse_class_opt mtu = 1600;
while (argc > 0) if (strcmp(*argv, “rate”) == 0) NEXT_ARG(); get_rate64(&rate64, argv) //3 1000000 / 8 else if (matches(*argv, “burst”) == 0) NEXT_ARG(); //buffer = 15 * 1024 //cell_log = -1 get_size_and_cell(&buffer, &cell_log, *argv) else if (strcmp(*argv, “ceil”) == 0) NEXT_ARG(); get_rate64(&ceil64, argv); //6 1000000 / 8
//超出32位最大值，则转换为全1？ opt.rate.rate = (rate64 >= (1ULL << 32)) ? ~0U : rate64; opt.ceil.rate = (ceil64 >= (1ULL << 32)) ? ~0U : ceil64;
//如果cbuffer为设置，则取值为当前mtu值加上最大速率下 //每ticket单位的比特数 if (!cbuffer) cbuffer = ceil64 / get_hz() + mtu;
opt.ceil.overhead = overhead; //0 opt.rate.overhead = overhead; //0
opt.ceil.mpu = mpu; //0 opt.rate.mpu = mpu; //0
//计算最小速率表 //cell_log = -1 //mtu = 1600 //linklayer = LINKLAYER_ETHERNET tc_calc_rtable(&opt.rate, rtab, cell_log, mtu, linklayer) //根据最大传输单元计算需要多少槽我理解是不可能每个 //字节都有准确速率，所以划定字节范围，从多少字节到 //多少字节的速率相同。 if (cell_log < 0) cell_log = 0; while ((mtu >> cell_log) > 255) cell_log++;
for (i=0; i<256; i++) //校正当前槽位的字节大小。这个算法比较简单，当前 //链路类型为以太网，则包根据原值处理，不会影响包 //大小。Mpu为最小包大小，如果槽位字节小于mpu， //则校正为mpu的值。 sz = tc_adjust_size((i + 1) << cell_log, mpu, linklayer);
//根据当前槽位字节大小，及用户配置的速率，计算当 //前槽位所需ticket时间 rtab[i] = tc_calc_xmittime(bps, sz);
r->cell_align=-1; r->cell_log=cell_log; r->linklayer = (linklayer & TC_LINKLAYER_MASK);
//计算单包正常速率下的传送峰值，这里通过包大小转换成所 //需要的ticket时间 opt.buffer = tc_calc_xmittime(rate64, buffer);
//计算最大速率表，仅在发包速率大于最小速率后，租借模式下 //有效。 tc_calc_rtable(&opt.ceil, ctab, ccell_log, mtu, linklayer)
//计算单包在租借模速率作用下，传送的峰值。 opt.cbuffer = tc_calc_xmittime(ceil64, cbuffer);
//添加扩展属性OPTIONS，标记后面都是htb的选项 addattr_l(n, 1024, TCA_OPTIONS, NULL, 0);
//超出32位，则添加扩展属性HTB_RATE64 //超出32位，则添加扩展属性HTB_CEIL64 if (rate64 >= (1ULL << 32)) addattr_l(n, 1124, TCA_HTB_RATE64, &rate64, sizeof(rate64)); if (ceil64 >= (1ULL << 32)) addattr_l(n, 1224, TCA_HTB_CEIL64, &ceil64, sizeof(ceil64));
//添加扩展属性HTB_PARMS addattr_l(n, 2024, TCA_HTB_PARMS, &opt, sizeof(opt));
//添加扩展属性HTB_RTAB addattr_l(n, 3024, TCA_HTB_RTAB, rtab, 1024);
//添加扩展属性HTB_CTAB addattr_l(n, 4024, TCA_HTB_CTAB, ctab, 1024);
//根据接口名获取接口索引 if (d[0]) idx = ll_name_to_index(d) req.t.tcm_ifindex = idx;
//给内核发送该netlink消息 rtnl_talk(&rth, &req.n, 0, 0, NULL)
rtnl_close(&rth);
用户侧发出RTM_NEWTCLASS套接口消息后，在内核侧对应的处理回调函数为tc_ctl_tclass，该函数是在pktsched_init中初始化的。
tc_ctl_tclass pid = tcm->tcm_parent //父类ID 0x00010001 clid = tcm->tcm_handle; //创建类ID 0x00010014 qid = TC_H_MAJ(clid); //队列ID 0x00010000
//eth0设备对象 dev = __dev_get_by_index(tcm->tcm_ifindex))
if (pid != TC_H_ROOT) pid = TC_H_MAKE(qid, pid); //0x00010001
//从当前设备的qdisc_list链表中找到已经创建的排队规则，当前q为之前创建的HTB q = qdisc_lookup(dev, qid)
//HTB的回调组为 cops = htb_class_ops cops = q->ops->cl_ops;
clid = TC_H_MAKE(qid, clid); //0x00010014
//get的回调函数为htb_get cl = cops->get(q, clid); htb_get htb_class *cl = htb_find(classid, sch); //使用类ID做HASH KEY在当前队列的HASH链表中查找已经创建的类 hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) if (cl->classid == handle) return cl; return NULL;
//如果找到则增加引用计数 if (cl) cl->refcnt++; return (unsigned long)cl;
//当前环境还没有该类存在，进行新类的属性设置 new_cl = cl; //当前回调为 htb_change_class cops->change(q, clid, pid, tca, &new_cl);/ htb_change_class //opt指向扩展属性基值索引，后续rtattr_parse_nested进行属性查找都从该 //基值索引之外进行查找。 rtattr *opt = tca[TCA_OPTIONS - 1];
//查看枚举定义，TCA_HTB_RTAB值是最后一个，所以rtattr_parse_nested //函数会把用户设置的所有扩展参数存储到临时变量tb中。 //enum //{ // TCA_HTB_UNSPEC, // TCA_HTB_PARMS, // TCA_HTB_INIT, // TCA_HTB_CTAB, // TCA_HTB_RTAB, // __TCA_HTB_MAX, //}; rtattr_parse_nested(tb, TCA_HTB_RTAB, opt)
//parentid = 0x00010001 //以类ID为HASH KEY向当前队规则的hash链表中查找父类，之前已经创建。 parent = htb_find(parentid, sch); htb_sched *q = qdisc_priv(sch); hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) if (cl->classid == handle) return cl; return NULL;
//取用户配置工具设置的HTB参数属性 hopt = RTA_DATA(tb[TCA_HTB_PARMS - 1]);
//将最小速率表加入到全局qdisc_rtab_list链表中 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB - 1]);
//将最大速率表加入到全局qdisc_rtab_list链表中 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB - 1]);
//当前为新类进行创建 if (!cl) cl = kzalloc(sizeof(*cl), GFP_KERNEL) cl->refcnt = 1; INIT_LIST_HEAD(&cl->sibling); INIT_HLIST_NODE(&cl->hlist); INIT_LIST_HEAD(&cl->children); INIT_LIST_HEAD(&cl->un.leaf.drop_list); RB_CLEAR_NODE(&cl->pq_node);
for (prio = 0; prio < TC_HTB_NUMPRIO; prio++) RB_CLEAR_NODE(&cl->node[prio]);
//创建默认的pfifo排队规则，同时将该排队规则的父亲设置为当前类 //sch->parent = parentid; 0x00010014 new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
//当前存在父类，该父类还未有孩子节点 if (parent && !parent->level) //保留当前父类中排队规则的队列长度，在HTB队列机制仅叶子类 //含有队列，所以当父类有孩子类后，父类中的队列就要删除。 qlen = parent->un.leaf.q->q.qlen;
//调用父类中排队规则的reset回调，当前父类的排队规则为默认的 //pfifo，则回调为qdisc_reset_queue qdisc_reset(parent->un.leaf.q); ops = qdisc->ops; ops->reset(qdisc); //该函数的实现仅仅是删除队列中所有skb报文 qdisc_reset_queue
//通知父排队规则，队列长度减少。 qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen); while ((parentid = sch->parent)) //当前排队规则为父类的pfifo规则，其中parent为父类 //的ID，TC_H_MAJ(parentid)对应的就是父类所在的排 //队规则，当前父类所在的排队规则即为最早创建的根 //排队规则HTB。 sch = __qdisc_lookup(sch->dev, TC_H_MAJ(parentid));
cops = sch->ops->cl_ops;
//htb_get //在排队规则中获取指定ID的类对象，并增加引用计数 cl = cops->get(sch, parentid); htb_get(sch, parentid)
//htb_qlen_notify cops->qlen_notify(sch, cl); htb_qlen_notify(sch, cl) //如果当前父类中排队规则的队列长度为0,则进行 //去激活 if (cl->un.leaf.q->q.qlen == 0) htb_deactivate(qdisc_priv(sch), cl); htb_deactivate_prios(q, cl); mask = cl->prio_activity;
while (cl->cmode == HTB_MAY_BORROW && p && mask) //当前还未有激活项，不处理
if (cl->cmode == HTB_CAN_SEND && mask) //当前还未有激活项，不处理
cl->prio_activity = 0; list_del_init(&cl->un.leaf.drop_list);
//htb_put //减小类引用计数，如果没有其它对象引用该类，则调用 //htb_destroy_class进行类的销毁 cops->put(sch, cl); htb_put(sch, cl);
//子排队规则中队列长度减少，则父排队规则中的队列长度 //相应减少。 sch->q.qlen -= n;
//销毁父类中排队规则，当前父类的排队规则为pfifo类型 qdisc_destroy(parent->un.leaf.q); list_del(&qdisc->list);
//qdisc_reset_queue ops->reset(qdisc); //删除队列中skb链表 qdisc_reset_queue
//递减相关对象引用计数，并释放排队规则占用的分配内存块 module_put(ops->owner); dev_put(qdisc->dev); call_rcu(&qdisc->q_rcu, __qdisc_destroy);
//父类中还有未激活项则去激活 if (parent->prio_activity) htb_deactivate(q, parent);
//根类等级深度为最大值 parent->level = TC_HTB_MAXDEPTH) - 1; //7
memset(&parent->un.inner, 0, sizeof(parent->un.inner));
//当前新建的类的默认排队规则设置为pfifo cl->un.leaf.q = new_q;
cl->classid = classid; //0x00010014 cl->parent = parent; //指向当前ID为1:1的父类
cl->tokens = hopt->buffer; //正常速率下单包峰值 cl->ctokens = hopt->cbuffer; //借用速率下单包峰值 cl->mbuffer = PSCHED_JIFFIE2US(HZ * 60); PSCHED_GET_TIME(cl->t_c); cl->cmode = HTB_CAN_SEND; //初始时可以发送报文
//当新建的类加入到根排队规则的hash表中 hlist_add_head(&cl->hlist, q->hash + htb_hash(classid));
//将新建的类关联到当前父类上 list_add_tail(&cl->sibling, &parent->children);
if (!cl->level) //在htb_init时，rate2quantum值默认为1 //设置quantum值，该值用于在进行带宽租借时的单位量 cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum; if (!hopt->quantum && cl->un.leaf.quantum < 1000) cl->un.leaf.quantum = 1000; if (!hopt->quantum && cl->un.leaf.quantum > 200000) cl->un.leaf.quantum = 200000;
cl->un.leaf.prio = hopt->prio; //0
cl->quantum = cl->un.leaf.quantum; cl->prio = cl->un.leaf.prio;
cl->buffer = hopt->buffer; //正常速率下单包峰值 cl->cbuffer = hopt->cbuffer; //借用速率下单包峰值
//设置当前类的最小、最大速率表 cl->rate = rtab; cl->ceil = ctab;
//发送netlink消息，告知添加成功 tclass_notify(skb, n, q, new_cl, RTM_NEWTCLASS);
//初始化，获取每纳秒对应多少TICKET tc_core_init(); fp = fopen(“/proc/net/psched”, “r”); fscanf(fp, “xxx”, &t2us, &us2t, &clock_res); fclose(fp);
if (clock_res == 1000000000) t2us = us2t;
clock_factor = (double)clock_res / TIME_UNITS_PER_SEC; tick_in_usec = (double)t2us / us2t * clock_factor;
//创建一个ROUTE类型的netlink套接口 rtnl_open(&rth, 0) rtnl_open_byproto(rth, subscriptions, NETLINK_ROUTE); rth->fd = socket(AF_NETLINK, SOCK_RAW | SOCK_CLOEXEC, protocol); setsockopt(rth->fd,SOL_SOCKET,SO_SNDBUF,&sndbuf,sizeof(sndbuf)) setsockopt(rth->fd,SOL_SOCKET,SO_RCVBUF,&rcvbuf,sizeof(rcvbuf)) rth->local.nl_family = AF_NETLINK; rth->local.nl_groups = subscriptions; //0 bind(rth->fd, (struct sockaddr*)&rth->local, sizeof(rth->local)) rth->seq = time(NULL);
do_cmd(argc-1, argv+1); if (matches(*argv, “filter”) == 0) do_filter(argc-1, argv+1); tc_filter_modify(RTM_NEWTFILTER, NLM_F_EXCL|NLM_F_CREATE, argc-1, argv+1); req.n.nlmsg_len = NLMSG_LENGTH(sizeof(struct tcmsg)); req.n.nlmsg_flags = NLM_F_REQUEST|flags; req.n.nlmsg_type = cmd; //RTM_NEWTFILTER req.t.tcm_family = AF_UNSPEC;
while (argc > 0) if (strcmp(*argv, “dev”) == 0) NEXT_ARG(); strncpy(d, *argv, sizeof(d)-1); //eth0 else if (matches(*argv, “protocol”) == 0) NEXT_ARG(); ll_proto_a2n(&id, *argv) protocol = id; //ETH_P_IP else if (strcmp(*argv, “parent”) == 0) NEXT_ARG(); get_tc_classid(&handle, *argv) req.t.tcm_parent = handle; //0x00010000 else if (matches(*argv, “priority”) == 0) NEXT_ARG(); get_u32(&prio, *argv, 0) //1 Else //如果有/usr/lib/tc/f_u32.so动态库中则从中获取u32_filter_util符 //号结构，否则检测当前tc程序是否有u32_filter_util符号结构则 //从中获取，否则返回q 为空。 q = get_filter_kind(k);
//prio = 1，左移到前两个字节 //protocol = ETH_P_IP，在低两个字节 req.t.tcm_info = TC_H_MAKE(prio<<16, protocol);
//增加KIND扩展属性，值为u32 addattr_l(&req.n, sizeof(req), TCA_KIND, k, strlen(k)+1);
//使用u32扩展过滤器解析后续规则，当前回调为u32_parse_opt q->parse_fopt(q, fhandle, argc, argv, &req.n) u32_parse_opt //添加OPTIONS扩展属性，标识后续都属于u32的扩展项 addattr_l(n, MAX_MSG, TCA_OPTIONS, NULL, 0);
while (argc > 0) if (matches(*argv, “match”) == 0) NEXT_ARG(); parse_selector(&argc, &argv, &sel.sel, n) else if (matches(*argv, “ip”) == 0) NEXT_ARG(); parse_ip(&argc, &argv, sel); else if (strcmp(*argv, “dport”) == 0) NEXT_ARG();
//sel->keys[hwm].val = key; htos(80) //sel->keys[hwm].mask = mask;全1 //sel->keys[hwm].off = off; 20 //sel->keys[hwm].offmask=offmask; 0 //sel->nkeys++; 1 parse_u16(&argc, &argv, sel, 22,0);
sel_ok++; else if (strcmp(*argv, “flowid”) == 0) NEXT_ARG(); //0x0001000A（0xA=10） get_tc_classid(&handle, *argv)
//添加U32_CLASSID扩展属性 addattr_l(n, MAX_MSG, TCA_U32_CLASSID, &handle, 4); //添加终止标记TC_U32_TERMINAL，内核代码会根据 //此标记判断当前处理完成。 sel.sel.flags |= TC_U32_TERMINAL;
if (sel_ok) //添加U32_SEL扩展属性 addattr_l(n, MAX_MSG, TCA_U32_SEL, &sel, sizeof(sel.sel)+sel.sel.nkeys*sizeof(struct tc_u32_key));
//根据接口名获取接口索引 if (d[0]) idx = ll_name_to_index(d) req.t.tcm_ifindex = idx;
//给内核发送该netlink消息 rtnl_talk(&rth, &req.n, 0, 0, NULL)
rtnl_close(&rth);
用户侧发出RTM_NEWTFILTER套接口消息后，在内核侧对应的处理回调函数为tc_ctl_tfilter，该函数是在tc_filter_init中初始化的。
protocol = TC_H_MIN(t->tcm_info); //ETH_P_IP prio = TC_H_MAJ(t->tcm_info); //1 nprio = prio; parent = t->tcm_parent; //0x00010000
dev = __dev_get_by_index(t->tcm_ifindex) //eth0设备对象
//从设备的qdisc_list列表中查找排队规则，之前HTB排队规则已经加入到链表中，所以 //这里的q就等于HTB排队规则。 q = qdisc_lookup(dev, TC_H_MAJ(t->tcm_parent))
//前2个字节为排队规则索引，后2个字节为类索引，当前命令设置基于排队规则之上，后 //2个字节设置为0，该条件不满足，此时cl变量取值为初始的0。 if (TC_H_MIN(parent)) //不走此流程
//HTB排队规则中对应的回调为htb_find_tcf //获取该排队规则中的过滤链表。 chain = cops->tcf_chain(q, cl); htb_find_tcf htb_sched *q = qdisc_priv(sch); htb_class cl = (struct htb_class )arg; //当前cl为0，则取的是排队规则中的过滤链表 tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list; return fl;
//查找待插入的位置，优先级的值越小表示越高。 for (back = chain; (tp=*back) != NULL; back = &tp->next) if (tp->prio >= prio) if (tp->prio == prio) if (!nprio || (tp->protocol != protocol && protocol)) goto errout; else tp = NULL; break;
//新建过滤协议项 if (tp == NULL) //从tcf_proto_base链表中查找u32分类器，当前tp_ops为cls_u32_ops tp_ops = tcf_proto_lookup_ops(tca[TCA_KIND-1]);
tp->ops = tp_ops; //cls_u32_ops tp->protocol = protocol; //ETH_P_IP tp->prio = nprio; //1 tp->q = q; //指向根HTB类型排队规则 tp->classify = tp_ops->classify; //u32_classify tp->classid = parent; //0x00010000
//当前u32类的初始化回调为fw_ini。 tp_ops->init(tp) u32_init //查找u32_list链表中是否存在相同的排队规则对象的过滤通用项 for (tp_c = u32_list; tp_c; tp_c = tp_c->next) if (tp_c->q == tp->q) break;
root_ht = kzalloc(sizeof(*root_ht), GFP_KERNEL); root_ht->divisor = 0; root_ht->refcnt++; //当前在u32_list链表中还未存在相同的排队规则对象的过滤通用项，所以 //tp_c不为真。 root_ht->handle = tp_c ? gen_new_htid(tp_c) : 0x80000000; root_ht->prio = tp->prio; //1
//当前tp_c为空，创建一个并加入到u32_list链表中。 if (tp_c == NULL) tp_c = kzalloc(sizeof(*tp_c), GFP_KERNEL); tp_c->q = tp->q; tp_c->next = u32_list; u32_list = tp_c;
//将新建的root_ht与tc_c互相关联 tp_c->refcnt++; root_ht->next = tp_c->hlist; tp_c->hlist = root_ht; root_ht->tp_c = tp_c;
//当前过滤对象的root指向新分配HASH节点对象，同时data指 //向新分配的过滤通用项 tp->root = root_ht; tp->data = tp_c;
//将当前过滤器加入到当前排队规则的过滤链表中 tp->next = *back; *back = tp;
//u32分类器的get回调为u32_get，当前在命令行里没有handle值，所以这里返回为0 fh = tp->ops->get(tp, t->tcm_handle);
//u32分类器的change回调为u32_change tp->ops->change(tp, cl, t->tcm_handle, tca, &fh); u32_change //把用户配置的后续所有扩展属性提取到临时变量opt中 rtattr_parse_nested(tb, TCA_U32_MAX, opt)
if ((n = (struct tc_u_knode*)*arg) != NULL) //当前在调用u32_get后，还不存在对应的hash节点项，所以不走此流程。
//如果命令接口设置了divisor，则表示创建一个新的hash表对象，该hash表含有 //divisor个数量的列表项，主要用于规则数量很大时，加快匹配速度。 if (tb[TCA_U32_DIVISOR-1]) unsigned divisor = (unsigned)RTA_DATA(tb[TCA_U32_DIVISOR-1]);
ht = kzalloc(sizeof(ht) + divisor*sizeof(void), GFP_KERNEL); ht->tp_c = tp_c; //当前hash表与过滤通用项关联 ht->refcnt = 0; ht->divisor = divisor; ht->handle = handle; ht->prio = tp->prio; //通用项中的hlist指向第一hash表，这里将新建的hash插入到通用项的hlist //链头。 ht->next = tp_c->hlist; tp_c->hlist = ht;
*arg = (unsigned long)ht; return 0;
//当用户在命令接口指定了hash表的ID，则查找对应的hash表，否则如果在命令 //接口没有指定hash表ID，则使用过滤协议项中root指向的第一个hash链表。 if (tb[TCA_U32_HASH-1]) htid = (unsigned)RTA_DATA(tb[TCA_U32_HASH-1]);
if (TC_U32_HTID(htid) == TC_U32_ROOT) ht = tp->root; htid = ht->handle; else //tp->data指向过滤通用项，这里使用过滤通用项中hlist链表来进行hash //表查找。 ht = u32_lookup_ht(tp->data, TC_U32_HTID(htid)); else ht = tp->root; htid = ht->handle; //0x80000000，该值在上面u32_init中初始化
//当前命令行未设置handle，使用gen_new_kid生成hash节点id if (handle) //不走此流程 else handle = gen_new_kid(ht, htid); unsigned i = 0x7FF;
//handle = 0x80000000 //TC_U32_HASH(handle) = 0 //当前ht->ht[0]还未有值，所有这里返回值为 0x80000800 for (n=ht->ht[TC_U32_HASH(handle)]; n; n = n->next) if (i < TC_U32_NODE(n->handle)) i = TC_U32_NODE(n->handle); i++; return handle|(i>0xFFF ? 0xFFF : i);
//指向选择项属性值 s = RTA_DATA(tb[TCA_U32_SEL-1]);
//当前用户配置接口在当前规则中仅设置了一个匹配项，则nkeys为1 //这里分配内存空间为一个struct tc_u_knode大小，加上一个struct tc_u32_key大小 n = kzalloc(sizeof(*n) + s->nkeys*sizeof(struct tc_u32_key), GFP_KERNEL);
//把用户配置设置匹配规则复制到当前新的hash关键节点的sel中 memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
//当前hash关键节点的ht_up指向当前使用的hash表 n->ht_up = ht; n->handle = handle; // 0x80000800
//当前s->hmask为0，所以i最后为0 u8 i = 0; u32 mask = s->hmask if (mask) …… n->fshift = i;
//过滤节点参数设置 u32_set_parms(tp, base, ht, n, tb, tca[TCA_RATE-1]); //当前命令行没有输入action或police，所以无扩展属性 tcf_exts_validate(tp, tb, est, &e, &u32_ext_map);
//如果用户接口输入了link，则进行链接处理，这里链接是指在当前过滤项 //匹配成功后，可以跳到其它hash表项中去处理，如果在其它hash表项中 //分类成功，则直接返回成功，否则在其它hash表项中分类失败，还可以 //回来原来的hash表项继续处理。 if (tb[TCA_U32_LINK-1]) u32 handle = (u32)RTA_DATA(tb[TCA_U32_LINK-1]);
//根据用户接口设置的link索引，查找当前通用项中hlist对应的hash //表是否含有对应id的hash项。 ht_down = u32_lookup_ht(ht->tp_c, handle);
//没找到返回错误，找到则增加引用计数 if (ht_down == NULL) goto errout; ht_down->refcnt++;
//将hash关键节点的ht_down指向希望链接的hash表项，在进行分类处 //理里，如果当前hash关键节点匹配成功，会检测如果存在ht_down，则 //使用该hash表项的各hash关键节点项继续匹配处理。 ht_down = xchg(&n->ht_down, ht_down);
//如果之前ht_down已经关联了其它hash表项，当前已经不使用，则 //递减引用计数。 if (ht_down) ht_down->refcnt–;
if (tb[TCA_U32_CLASSID-1]) //0x0001000A n->res.classid = (u32)RTA_DATA(tb[TCA_U32_CLASSID-1]);
tcf_bind_filter(tp, &n->res, base); //当前回调为htb_bind_filter //查找绑定该hash关键节点对象的类 cl = tp->q->ops->cl_ops->bind_tcf(tp->q, base, r->classid); htb_bind_filter htb_sched *q = qdisc_priv(sch);
//当前classid为0x000100A htb_class *cl = htb_find(classid, sch);
//找到匹配的类，则类的过滤计数递增 if (cl) cl->filter_cnt++; else q->filter_cnt++; return (unsigned long)cl;
//将找到的类对象关联到hash关键节点对象中，同时返回hash关键 //节点对象中原有的关联类，当前没有老的关联类，所以old_cl为空 cl = cls_set_class(tp, &r->class, cl); old_cl = __cls_set_class(clp, cl); old_cl = *clp; *clp = cl; return old_cl; return old_cl;
//当前hash关键节点对象是新建的，没有老的关联类，不执行此流程。 if (cl) tp->q->ops->cl_ops->unbind_tcf(tp->q, cl);
//扩展参数设置，当前命令行没有输入action或police，所以无扩展属性。 tcf_exts_change(tp, &n->exts, &e);
//把新建的hash关键节点加入到hash对象的ht链表中 for (ins = &ht->ht[TC_U32_HASH(handle)]; *ins; ins = &(*ins)->next) if (TC_U32_NODE(handle) < TC_U32_NODE((*ins)->handle)) break;
n->next = *ins; wmb(); *ins = n;
//告知添加成功 tfilter_notify(skb, n, tp, fh, RTM_NEWTFILTER);
当上层发出报文，调用dev_queue_xmit，这里仅分析和出口排队规则相关的代码，其它详细 的代码分析可以参见《接口设备发包》 dev_queue_xmit ……
//如果当前使用出口排队规则 q = rcu_dereference(dev->qdisc); if (q->enqueue) spin_lock(&dev->queue_lock); q = dev->qdisc;
if (q->enqueue) //调用当前排队规则的入队回调，当前HTB类型排队规则回调为 //htb_enqueue rc = q->enqueue(skb, q); htb_enqueue htb_sched *q = qdisc_priv(sch);
//分类处理 htb_class *cl = htb_classify(skb, sch, &ret); //直报文的优先级字段与当前队列的句柄相同，则返回直接处理 if (skb->priority == sch->handle) return HTB_DIRECT;
//使用报文的优先级字段做为类ID，在htb_find函数中，从排队 //规则的hash表中查找指定类ID的类对象，找到指定类对象后， //根据cl->level判断当前类是否为叶子（0为叶子），如果是叶子 //类则返回。 if ((cl = htb_find(skb->priority, sch)) != NULL && cl->level == 0) return cl;
*qerr = NET_XMIT_BYPASS;
tcf = q->filter_list;
//使用过滤对象进行分类，tc_classify函数在下面单独分析。 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) switch (result) //这三种处理结果都会返回空类，在htb_enqueue对返回类 //为空的情况都会将报文丢弃。 case TC_ACT_QUEUED: case TC_ACT_STOLEN: *qerr = NET_XMIT_SUCCESS; case TC_ACT_SHOT: return NULL;
//如果返回结果的类不存在，则继续尝试 if ((cl = (void *)res.class) == NULL) //如果返回结果就classid为排队规则句柄，也就是说之 //前用户在命令接口配置过滤规则时，最后匹配的流ID //为排队规则句柄，则返回直接处理。 if (res.classid == sch->handle) return HTB_DIRECT;
//此时根据用户在命令接口配置过滤规则时指定的 //流ID查找当前排队规则是否存在该类，如果不存 //在，则直接跳出当前while循环，使用之前创建 //HTB排队规则时设置的默认的类 if ((cl = htb_find(res.classid, sch)) == NULL) break;
//如果找到了类，并且该类是叶子类，则返回，否则继续使 //用下一个过滤器进行查找。 if (!cl->level) return cl;
//使用非叶子类中的过滤器进行分类 tcf = cl->filter_list;
//到达这里，表明所有过滤器都已经遍历完了，但还没有找到 //对应的叶子类。这里则使用之前创建HTB排队规则时设置的 //默认类ID进行查找。 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
//如果使用默认类ID，还没找到对应的类，或者找到的类是非 //叶子类型的，则返回直接处理。 if (!cl || cl->level) return HTB_DIRECT;
//返回找到的默认类。 return cl;
//当前返回结果为直接处理 if (cl == HTB_DIRECT) //如果当前直接发送队列还未达到直接发送限额，则将报文放入 //直接发送队列中，否则将报文丢弃处理。 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; //使用叶子类中的排队规则的enqueue回调，将报文压入到该排队规 //则中，如果压入失败，则进行丢包统计。 else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) !=net_xmit_success) sch->qstats.drops++; cl->qstats.drops++; return NET_XMIT_DROP; else //包压入指定叶子类下的排队规则后，统计成功项，同时激活对 //应叶子类。 cl->bstats.packets++; cl->bstats.bytes += skb->len;
//激活叶子类，当前HTB的机制在对激活的类做了划分。首先 //分了8层，叶子类为第0层，根类为第7层，中间类在父类的 //层数上减1，在进行出队处理时从第0层开始优先进行处理。 //同时每层又分为8个优先级，0为第高优先级，当被激活的类 //层次相同时，则按优先级最高的优先进行处理。当被激活的类 //层次也相同，优先级也相同，则被根据类ID为对比值放入一 //棵红黑树中，类ID越小优先级越高。激活类的数据结构大概 //如下图所示：
htb_activate(q, cl); //设置当前类中被激活的优先级位图，这里cl->un.leaf.prio //是在类被用户接口创建时设置的，如果在用户接口未输入 //prio则默认为0。 cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);
//根据类中层次及优先级位图激活类 htb_activate_prios(q, cl); p = cl->parent; //当前类的父类 mask = cl->prio_activity; //当前类的优先级位图
//当前类如果已经进到了租借模式，同时该类存在父类 //则进行处理。这里会对父类进行激活，同时将当前类 //挂接到父类的feed供给树下。 while (cl->cmode == HTB_MAY_BORROW && p && mask) m = mask;
while (m) //将优先级位图取反，之后使用ffz查找第一 //为0的位为表示优先级索引。 int prio = ffz(~m);
//当前位处理后就去除。 m &= ~(1 << prio);
//当前父类如果已经在供给，则表明之前已经 //激活，则在mask中去除当前优先级位，否 //则下面会将cl变量指向父类，并对父类进行 //激活。 if (p->un.inner.feed[prio].rb_node) mask &= ~(1 << prio);
//这里将当前子类加入到父类的供给树中 //（un.inner.feed），表明当前父类在给哪些 //子类供给。 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
//父类可能租借给多个子类使用，这里在父类中保 //存子类的优先级。开始对父类准备激活处理。 p->prio_activity |= mask; cl = p; p = cl->parent;
//如果当前类为可发送模式，则在HTB排队规则中激 //活该优先级类。 if (cl->cmode == HTB_CAN_SEND && mask) htb_add_class_to_row(q, cl, mask); //记载当前层次哪些优先级被激活 q->row_mask[cl->level] |= mask;
//遍历所有待处理的优先级位，将当前类插入 //到排队规则row指定位置的树中。插入位置 //的实现可以参考上图激活类的数据结构来 //加深理解。 while (mask) int prio = ffz(~mask); mask &= ~(1 << prio); htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
//将当前叶子类插入到HTB排队规则的drops对应优先级的 //列表中。 list_add_tail(&cl->un.leaf.drop_list,q->drops + cl->un.leaf.aprio);
//更新统计，返回分类成功。 sch->q.qlen++; sch->bstats.packets++; sch->bstats.bytes += skb->len; return NET_XMIT_SUCCESS;
//队列处理 qdisc_run(dev); //如果队列发送没有关闭，并且队列调度还没有运行，则运行队列调度 if (!netif_queue_stopped(dev) &&!test_and_set_bit(__LINK_STATE_QDISC_RUNNING, &dev->state)) __qdisc_run(dev); //如果队列为noop_qdisc类型，则表明接口还未启动，则直接退 //出队列调度 if (unlikely(dev->qdisc == &noop_qdisc)) goto out;
//当还有待处理的数据，并且发送队列没有关闭，则循环从队列 //中取出数据，使用网卡驱动进行发送数据。该函数具体实现不 //详细列出。之前在《接口设备发包》中已经分析过，可以参考 //那节的分析。这里主要关注，从队列中取出数据是使用的队列 //的dequeue回调，当前HTB类型的排队规则回调为 //htb_dequeue，htb_dequeue在下面单独分析。 while (qdisc_restart(dev) < 0 && !netif_queue_stopped(dev)) ;
out: //去除正在进行队列调度标记 clear_bit(__LINK_STATE_QDISC_RUNNING, &dev->state);
spin_unlock(&dev->queue_lock);
rc = rc == NET_XMIT_BYPASS ? NET_XMIT_SUCCESS : rc; goto out;
spin_unlock(&dev->queue_lock);
//使用过滤器进行分类 tc_classify protocol = skb->protocol;
//遍历所有过滤器 for ( ; tp; tp = tp->next) //首先检测当前报文的协议与过滤器中的协议匹配，或者过滤器匹配任何协议类 //型，则进一步使用当前过滤器的classify回调进行分类处理，当前u32的回调 //函数为u32_classify，u32_classify在下面单独分析。 if ((tp->protocol == protocol ||tp->protocol == __constant_htons(ETH_P_ALL)) && (err = tp->classify(skb, tp, res)) >= 0) //返回处理结果 return err;
//返回-1，表明分类失败。 return -1;
使用u32分类器进行分类处理 u32_classify //过滤协议对象的root，即首hash链表对象 tc_u_hnode ht = (struct tc_u_hnode)tp->root; u8 *ptr = skb->nh.raw; //报文的IP头位置 int sel = 0;
next_ht:
n = ht->ht[sel];
next_knode:
//判断当前hash关键节点是否存在 if (n) struct tc_u32_key *key = n->sel.keys; //hash关键节点对象的匹配项
//遍历当前hash关键节点的所有匹配项，如果有任何一项匹配失败，则使用 //goto进入下一个hash关键节点进行匹配。这里匹配项中的off就是对应项 //（比如dport）在报文IP文件位置的偏移。 for (i = n->sel.nkeys; i>0; i–, key++) if (((u32)(ptr+key->off+(off2&key->offmask))^key->val)&key->mask) n = n->next; goto next_knode;
//ht_down和命令行中link配置相关，用于多层嵌套，可以实现跳转到其它hash链 //节点进行查找，当前测试实例没有配置嵌套，这里ht_down 为NULL。 if (n->ht_down == NULL) check_terminal: //在用户侧命令接口已经对当前过滤选择项设置了U32_TERMINAL if (n->sel.flags&TC_U32_TERMINAL) *res = n->res; //返回该过滤选择项的结果，这里含有绑定的类
//进行扩展属性处理，处理失败尝试下一个关键匹配点，当前命令接口 //没有设置相关扩展项，所以这里返回为0 r = tcf_exts_exec(skb, &n->exts, res); if (r < 0) n = n->next; goto next_knode;
//当前匹配完成，返回结果。 return r;
//如果hash关键节点匹配项匹配完成，但不含U32_TERMINAL处理结束的标 //记，则尝试下一个hash关键节点。 n = n->next; goto next_knode;
//n->ht_down不为空，表明有嵌套匹配处理
//先将当前hash关键节点及匹配指针压入临时变量stack栈中 stack[sdepth].knode = n; stack[sdepth].ptr = ptr; sdepth++;
//取出待跳转的hash链对象 ht = n->ht_down;
sel = 0; //如果当前hash链对象含有divisor值，表明该hash链对象是之前通过命令接口 //使用divisor关键字段创建的含有多个列表项的hash链对象，则这里根据之 //前命令接口设置的散列因子相关的参数（比如根据源IP地址最后1个字节进行散 //列因子处理）进行计算，来确定当前的报文应该在当前hash链对象的哪个列表 //项中进行处理。 if (ht->divisor) sel = ht->divisor&u32_hash_fold((u32)(ptr+n->sel.hoff), &n->sel,n->fshift);
//如果当前hash关键节点的选择项中不含有任何偏移属性，则直接跳转到下一个 //hash链节点中进行查找。 if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT))) goto next_ht;
//走到此流程，表明当前hash关键节点中含有相关的偏移属性，则根据用户接口 //配置进行对应的偏移处理，如果处理完后报文合法，则跳转到下一个hash链节 //点中进行查找。 if (n->sel.flags&(TC_U32_OFFSET|TC_U32_VAROFFSET)) off2 = n->sel.off + 3; if (n->sel.flags&TC_U32_VAROFFSET) off2 += ntohs(n->sel.offmask & (u16)(ptr+n->sel.offoff)) >>n->sel.offshift; off2 &= ~3; if (n->sel.flags&TC_U32_EAT) ptr += off2; off2 = 0; if (ptr < skb->tail) goto next_ht;
//用户接口含有link关键字时，则进行嵌套处理，每进行一次嵌套则将前一次处理结果 //存储到临时变量stack中，当最后的嵌套处理没有匹配成功时，会走到此流程，如果 //当前确定是嵌套处理，则取出前一次的hash链对象继续进行处理。 if (sdepth–) n = stack[sdepth].knode; ht = n->ht_up; ptr = stack[sdepth].ptr; goto check_terminal;
//分类失败 return -1;
//HTB数据包出队处理 htb_dequeue q->jiffies = jiffies; //记载当前滴答
//如果当前直接发送队列含有报文，则优先进行处理，直接将报文取出。 skb = __skb_dequeue(&q->direct_queue); if (skb != NULL) sch->flags &= ~TCQ_F_THROTTLED; sch->q.qlen–; return skb;
//队列无数据则返回为NULL if (!sch->q.qlen) goto fin;
//获取当前系统时间 PSCHED_GET_TIME(q->now);
min_delay = LONG_MAX;
q->nwc_hit = 0;
//从第0层开始遍历处理，第0层为叶子类层 for (level = 0; level < TC_HTB_MAXDEPTH; level++) //当前流逝时间已经超过最近事件的缓冲时间 if (time_after_eq(q->jiffies, q->near_ev_cache[level])) delay = htb_do_events(q, level); //最多处理500个被阻塞的报文 for (i = 0; i < 500; i++) //取当前层中第1个被阻塞的树节点 struct rb_node *p = rb_first(&q->wait_pq[level]);
//如果当前没有阻塞的报文，则返回0延时。 if (!p) return 0;
//获取包含该树节点的HTB类对象 cl = rb_entry(p, struct htb_class, pq_node);
//如果当前类的阻塞时间还未到，则继续阻塞，返回还有多长时间会 //到的时间差。 if (time_after(cl->pq_key, q->jiffies)) return cl->pq_key - q->jiffies;
//当前类的阻塞时间已到。
//将树节点从阻塞树中删除。 htb_safe_rb_erase(p, q->wait_pq + level);
//计算当前类最后一次处理到当前的时间差，该时间差不能超过 //mbuffer值（在创建类时该值为1分钟）。 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32) cl->mbuffer);
//进行类的模式改变 htb_change_class_mode(q, cl, &diff); new_mode = htb_class_mode(cl, diff); //这里ctokens是租借模式下令牌数，经过一段时间后令牌 //数就会进行补充。待补充后仍然小于低水位线，则状态变 //为HTB_CANT_SEND（不能进行发送），这里htb_lowater //低水位线根据当前类的模式不同而不同，如果当前类模式 //为HTB_CANT_SEND，则低水位线的值为-cl->cbuffer，也 //就是租借模式下单包最大可传达数据所需要的ticket，其它 //模块下低水位线的值为0。 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) *diff = -toks; //返回还需要多少令牌 return HTB_CANT_SEND;
//这里tokens是非租借模式下令牌数，经过一段时间补充后， //如果高于高水位线，则状态变为HTB_CAN_SEND //（可以发送） if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl)) return HTB_CAN_SEND;
//状态变为可租借，返回还需要多少令牌 *diff = -toks; return HTB_MAY_BORROW;
//当前模式相同则直接返回。 if (new_mode == cl->cmode) reutrn;
//如果当前类有激活，则根据新、老模式进行类的激活、去激活 //处理（之前为非不可发送模式，则将当前类去激活，该类后 //续暂时不能发包，当前新的模式为可发送模式，则将当前类 //激活，该类后续可以继续发包，当前新的模式为租借模式，则 //激活父类，并将当前类挂接到父类的feed供给树下）。 //否则当前类没有激活，则仅修改当前模式。 if (cl->prio_activity) 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;
//如果当前模式不可发送，则将类插入到q->wait_pq[level]等待树中。 //同时更新类的cl->pq_key等待关键字的值为当前jitter加上diff，其 //中diff是在上面htb_change_class_mode中计算得到。 if (cl->cmode != HTB_CAN_SEND) htb_add_to_wait_tree(q, cl, diff);
//在上面等待树中最多处理500个等待报文，超过则放到下轮再来处理， //同时返回延时时间为100ms。 return HZ / 10;
//更新最近事件处理时间，如果没有等待处理的包，则delay为0，下一次事件 //处理则加长一些（1秒），否则还有等待处理的包，则下一次事件处理的时间 //设置为上面的delay值。 q->near_ev_cache[level] =q->jiffies + (delay ? delay : HZ); else //如果当前流逝时间还未到达下一次事件处理时间，则delay取值为下一次事 //件处理所需要的时间点。 delay = q->near_ev_cache[level] - q->jiffies;
//因为最终在下面进行延时处理是使用min_delay的值，这里对该值进行校正 if (delay && min_delay > delay) min_delay = delay;
//row_mask[level]为当前层已经激活的类，这里取反是为了方便下面使用ffz进行 //查找第一个为0的位所在索引。 m = ~q->row_mask[level];
//优先级激活位图如果取反为全为1，则表明当前层的类都没有被激活。 while (m != (int)(-1)) //优先取最低优先级位进行处理。 int prio = ffz(m);
m |= 1 << prio; //每处理一次，当前优先级位就清除，以免二次进入。
//指定层次、指定优先级的树中取出待发送的skb报文。 skb = htb_dequeue_tree(q, prio, level); //q->row记载着激活的位图，仅类被激活后才可以发送报文，当子类未激 //活时，从父类中租借代宽，父类就会激活。 //q->ptr记载了最后处理的的类的树节点。 //q->last_ptr_id记载了最后处理的类ID。 //这里根据DDR算法，查找出可调度的HTB类。 //htb_lookup_leaf函数比较复杂，放在下面单独分析。
start = cl = htb_lookup_leaf(q->row[level] + prio, prio,q->ptr[level] + prio, q->last_ptr_id[level] + prio);
do next: //由于代宽受限等原因导致当前没有可出队的报文。 if (!cl) return NULL;
//如果当前类的队列为空 if (unlikely(cl->un.leaf.q->q.qlen == 0)) //该类去激活 htb_deactivate(q, cl); //检查如果当前层、当前优先级已经没有激活的类，则返回为 //NULL，让上面函数继续下一层、下一优先级类的处理。 if ((q->row_mask[level] & (1 << prio)) == 0) return NULL;
//当前调度的类没有队列，并且当前层、当前优先级下还有激活 //的类，则再次调用htb_lookup_leaf查找可调度的类。同时更新 //临时变量start、cl。 next = htb_lookup_leaf(q->row[level] + prio, prio, q->ptr[level] + prio,q->last_ptr_id[level] + prio);
if (cl == start) start = next; cl = next; goto next;
//使用当前类下的排队规则的dequeue回调进行将报文出队，这里 //dequeue回调实现取决于用户侧给该类下绑定什么排队规则，如 //果启用未设置，则默认HTB类下的排队规则为pfifo_qdisc，则 //对应的回调函数为qdisc_dequeue_head，该函数比较简单，仅仅 //是仅出双向链表中第一个节点的报文。 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
//报文取出后直接跳出do while循环，返回。 if (likely(skb != NULL)) break;
//当该类下标明有队列，但取出失败，则标记告警。 if (!cl->warned) cl->warned = 1;
q->nwc_hit++; //统计不工作的错误类计数 //将之前保存记录的ptr（最后处理的的类的树节点）更新为下一个节 //点。 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->ptr[0]) + prio);
//再次调用htb_lookup_leaf查找可调度的类 cl = htb_lookup_leaf(q->row[level] + prio, prio,q->ptr[level] + prio, q->last_ptr_id[level] + prio);
//走到这里，表明刚才调度类在出队报文时异常，又重新选择了新的调度 //类。重新进行出队处理。 while (cl != start)
//报文成功出队 if (likely(skb != null)) //htb_next_rb_node用来修改下一次使用htb_lookup_leaf选择调度 //类时先从哪个类进行处理，这里根据quantum值的限额来进行 //控制，可以防止htb_lookup_leaf在一段时间内始终使用相同的类 //进行调度。 if ((cl->un.leaf.deficit[level] -= skb->len) < 0) cl->un.leaf.deficit[level] += cl->un.leaf.quantum; htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->ptr[0]) + prio);
//当前类下的排队规则中已经没有报文，则将该类去激活。 if (!cl->un.leaf.q->q.qlen) htb_deactivate(q, cl);
//对该类进行收费计算。 htb_charge_class(q, cl, level, skb->len); //临时定义了一个计帐功能宏，这里T可以是tokens或ctokens， //B可以是buffer或cbuffer，R可以是rate或ceil。 //T表示租借模式或非租借模式下的令牌数。 //B表示租借模式或非租借模式下基于对应速率的单包峰值。 //R表示租借模式或非租借模式下不同速率。 //首先将根据流逝时间来对所剩的令牌数进行补充。
//对令牌数进行上限峰值限制 if (toks > cl->B) toks = cl->B; \ //根据当前报文字节数，在速率表中查找符合当前字节范围 //之内所需消耗的单位值，之后从令牌总数中扣除消耗的单 //位值。 toks -= L2T(cl, cl->R, bytes); \ //如果令牌数小于最大负等待峰值时间（1分钟），则对令牌 //数修正为最大负等待峰值时间。 if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \ //将剩余的令牌数保留，供下一次使用。 cl->T = toks
while (cl) //计算当前HTB类最后一个工作到当前已经流逝的时间， //不能超过mbuffer上限。 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32) cl->mbuffer);
//该函数第一次处理的cl类都是叶子类，之后在while //循环中cl类依次改变为当前类的父类，而level在循环 //中是始终保持不变的。如果当前level是0,表明叶子一直 //未超过最低速率，始终是可发送的。如果当前level非0， //表明叶子已经在借用父类的带宽。当cl->level >= level，则 //对当前类及父类都进行tokens计费处理，当 //cl->level < level则表明当前类是在对父类进行租借，不 //再对当前类进行tokens计费处理，仅对提供租借的父类 //进行tokens计费处理。但不管当前类是否在租借都会 //对ctokens进行计费处理。这里要理解tokens与ctokens //的差别，tokens是当前类的速率限制，ctokens是可向父类 //借用的速率限制。如果使用当前类发送报文时小于tokens， //则当前类速率还比较正常，可以继续处理，如果当前发送 //报文时大于tokens但小于ctokens，则表明当前类已经超出 //自己的速率限制，但还可以从父类借用带宽，如果当前发 //送报文时大于ctokens，则表明都超出了可借用速率，此时 //该类的模式会修改为不可发送模式，当前类暂时已经不能 //在发送任何报文。 if (cl->level >= level) if (cl->level == level) cl->xstats.lends++; HTB_ACCNT(tokens, buffer, rate); else cl->xstats.borrows++; cl->tokens += diff; HTB_ACCNT(ctokens, cbuffer, ceil);
//记载当前类最后处理时间，用于下一个时间点来统计已经 //流逝的时间。 cl->t_c = q->now;
//根据当前类中tokens、ctokens剩余令牌数，使用 //htb_change_class_mode进行HTB类的模式切换处理。 //同时根据是否还是可发送模式而确定是否将类插入到 //HTB排队规则的等待树中。 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->wait_pq + cl->level); if (cl->cmode != HTB_CAN_SEND) htb_add_to_wait_tree(q, cl, diff);
//非叶子类的统计。 if (cl->level) cl->bstats.bytes += bytes; cl->bstats.packets++;
//将cl修改为当前类的父类，在while循环中依次对父类 //进行处理。 cl = cl->parent;
//如果成功取出报文，则HTB排队规则的队列个数递减，同时去除受限标记， //将当前skb返回。 if (likely(skb != NULL)) sch->q.qlen–; sch->flags &= ~TCQ_F_THROTTLED; goto fin;
//当前HTB排队规则中有报文，但遍历完所有层、所有优先级的类后，没有成功取出 //报文，则进行延时处理。 htb_delay_by(sch, min_delay > 5 * HZ ? 5 * HZ : min_delay); //修改当前HTB排队规则的timer定时器时间，该定时器是在创建HTB排队规则 //时，通过htb_init函数创建，该定时器的超时处理函数为htb_timer，该函数比较 //简单，仅仅是去除TCQ_F_THROTTLED受限标记，之后调用netif_schedule进行 //发送队列的重新调度。 mod_timer(&q->timer, q->jiffies + delay);
//加上受限标记，更新overlimits超出限速的统计。 sch->flags |= TCQ_F_THROTTLED; sch->qstats.overlimits++;
查找可调度的叶子类（虽然代码不多，但这里是整个HTB排队规则中最难的一部分） htb_lookup_leaf(struct rb_root tree, int prio,struct rb_node **pptr, u32 pid) //定义了8个元素的数组，初始sp指向第0个元素。 struct { struct rb_node *root; struct rb_node **pptr; u32 *pid; } stk[TC_HTB_MAXDEPTH], *sp = stk;
//当前第0个元素的初始值由传入的参数提供，root指向当前层次、当前优先级下待处 //理的HTB类所在的树节点。pptr指向HTB排队规则中记载的最后处理的树节点， //注意这里使用了双层指针，在当前函数处理时就可以通过*pptr来对传入参数进行修 //改，更新HTB排队规则中记载的最后处理树节点，以方便下一次报文处理时使用。 //pid指向HTB排队规则中记载的最后处理的类ID，同样，这里可以通过*pid来对传 //入参数进行修改。 sp->root = tree->rb_node; sp->pptr = pptr; sp->pid = pid;
//尝试65535次处理 for (i = 0; i < 65535; i++) //当树节点不存在，但类ID存在，则使用类ID尝试在当前待处理的树中进行查 //找树节点。通过查看代码，发现有一种情景会走此流程，如果一个HTB叶子 //类为租借模式，当其发送报文后，队列中已经没有数据，则触发htb_deactivate_prios //函数，该函数会判断当前类为租借模式，并且正好匹配父类中un.inner.ptr //记载的最后处理树节点，则将父类的un.inner.ptr设置为空，同时父类的 //un.inner.last_ptr_id保留此叶子类的ID，并将该类的树节点从父类的供应树中 //删除。之后立即有一个新的报文使用htb_enqueue函数对该叶子类又进行入队 //操作，则触发htb_activate_prios函数将此叶子类又加入到父类的供应树中。 //那么当使用htb_lookup_leaf查找可调度类时，如果q->ptr队列的最后树节点 //处理正好是这个父类，在此函数中会将sp->root指向父类的供应树，sp->pptr //指向父类的un.inner.ptr，sp->pid指向父类的un.inner.last_ptr_id，此时正好满足 //当前IF的条件判断。 if (!*sp->pptr && *sp->pid) *sp->pptr = htb_id_find_next_upper(prio, sp->root, *sp->pid);
//清除pid，保证上面的条件判断仅触发一次。 *sp->pid = 0;
//如果当前树节点不存在 if (!*sp->pptr) //将树节点指向当前待处理的树根节点。一定要留意，使用了*sp也就意味着 //将sp->pptr之前指向的对象内容做了修改，即如果之前对象是指针类型，则 //把原对象的指针指向进行了修改。 *sp->pptr = sp->root;
//将pptr指向当前树中最小类ID的节点（生成该树时就是以类ID为索引进行 //的红黑树排序）。 while ((*sp->pptr)->rb_left) *sp->pptr = (*sp->pptr)->rb_left;
//这里stk就是上面的临时数组，也相当于数组的第0元素指针，刚进入该 //函数时，sp是指向数组的第0个元素的，当下面发现找到的调度类 //非叶子类时，sp就会递增，同时sp将指向该类的供给类（也就是该 //类的孩子类）。如果出现这种情况，则sp–来退到当前类的父类，同时 //对父类的sp->pptr最后使用的树节点进行更新，htb_next_rb_node函数 //是将sp->pptr值设置为比sp->pptr更大一点的节点（如果有右子树，则 //取右子树中最小的树节点；否则如果有父亲则取父亲中最小的树节点； //否则如果没有父子节点则取值为NULL）。 if (sp > stk) sp–; if (!*sp->pptr) return NULL; htb_next_rb_node(sp->pptr);
else //pptr找到了树节点，则取出包含该树节点的类对象 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
//检测如果当前是叶子类则表示查找成功，返回该叶子类。 if (!cl->level) return cl;
//走到此流程表明找到的类是非叶子类型，此时递增sp，使其指向stk的下一 //个数组元素，同时将该类的相关信息存储到这个新的数组元素中。root指向 //当前类供应的子类树节点，pptr指向当前类的最后处理树节点，pid指向当前 //类的最后处理类ID。 (++sp)->root = cl->un.inner.feed[prio].rb_node; sp->pptr = cl->un.inner.ptr + prio; sp->pid = cl->un.inner.last_ptr_id + prio;
//经过这么多次查找，仍然没找到可调度的叶子类，则查找失败，返回NULL。
（注意： 以下分析仅考虑htb_lookup_leaf函数配合类激活、去激活的流程分析，并未考虑数据报发送成功后，在其它条件下也会使用htb_next_rb_node进行下一个待处理的树节点修改的情况）。 一、到这里已经对htb_lookup_leaf怎样进行查找可调度的叶子类分析完成，但可能还是云里雾里，这里用一个实例来描述htb_lookup_leaf函数的晦涩算法机制。在如下实例中，我们假设仅创建了三个类（根父类、子类1、子类2），这里根类的层次为最高层7，叶子类的层次为最低层0，同时假设这三个类的优先级都为0级，所以可以看到下图中子类1与子类2在同层次、同优先级情况下构建了一棵树，并且假设子类1的ID比较小，所以子类1在红黑树的左侧。
1、最初时，子类1、与子类2都为可发送模式，并且随着报文进入对应类的队列，类分别被激活。 2、在出队时，根据第0层优先、0优先级优先的原则，此时会找到子类2的树对象上。 3、之后使用htb_lookup_leaf函数进行查找可调度的叶子类。 4、最初HTB排队规则的q->ptr最后处理的树节点为NULL，所以会走到if (!*sp->pptr)流程，在该流程中会更新q->ptr，使其指向子类2的树节点，之后又遍历该树中最小的类ID节点，所以q->ptr又被更新为子类1树节点。此时子类1是叶子类，查找成功，返回当前调度类为子类1。 5、后续由于q->ptr最后处理树节点指向了子类1，所有只要子类1一直有待发送的数据，则始终使用子类1进行调度。
二、当子类1不断发包，已经超出其带宽限制后。 1、子类1的模式由可发送模式变为租借模式，在模式变更时触发了两个关键动作，首先子类1进行去激活处理，在去激活处理过程中q->ptr指向了同层次、同优先级、比子类1略大一点的子类2上。其次，父类被激活，同时父类的供给树根节点指向了子类1的树节点。 2、在后续出队时，优先处理第0层、第0优先级的类，当前q->ptr已经指向子类2，所以后续始终用子类2进行调度。
三、当子类2不断发包，已经超出其带宽限制后。 1、子类2的模式由可发送模式变为租借模式，在模式变更时触发了两个关键动作，首先子类2进行去激活处理，在去激活处理过程中由于子类2已经是只含1个节点的树了，q->ptr指向了NULL。其次，子类2也被加入到了父类的供给树中，由于和子类1的优先级相同，所以子类2和子类1又成为一棵树上的节点。 2、此时第0层的类已经没有激活的，所以只能从当前只激活的第7层类中进行处理。首先检测当前q->ptr为NULL，则将q->ptr指向父类的树节点。（注意当前父类的树仅有一个节点，图中画的连线并非父节点的子节点，也就是说父类在HTB排队规则中指定层次、指定优先级的那棵树下仅自己一个节点，而父类自身有一个feed供给树，用来标识当前父类都给哪些孩子类提供带宽借用。） 3、之后判断当前父类并非叶子类，则将sp指向stk数组的第1个元素，第1个元素的 root指向当前父类feed供给树的根节点（子类1），第1个元素的pptr指向父类的cl->un.inner.ptr，第1个元素的pid指向父类的cl->un.inner.last_ptr_id。 4、由于最终父类的cl->un.inner.ptr还为NULL值，所有又走到if (!*sp->pptr)条件里去，在这里将父类的cl->un.inner.ptr指向了父类的供给树根节点（子类1）。 5、sp此时指向stk数组的第1个元素，所有if (sp > stk)条件成立，将sp指针递减回第0个数组元素，第0个数组元素在第2步中已经将q->ptr指向父类的树节点，由于父类树节点仅有一个树节点，所有在执行htb_next_rb_node(sp->pptr)时返回NULL，导致q->ptr又变成NULL值。 6、继续for循环处理，又将q->ptr指向父类，之后判断当前父类并非叶子类，则将sp指向stk数组的第1个元素，第1个元素的root指向当前父类feed供给树的根节点（子类1），第1个元素的pptr指向父类的cl->un.inner.ptr，第1个元素的pid指向父类的cl->un.inner.last_ptr_id。 7、此时父类的cl->un.inner.ptr已经指向子类1，所以判断子类1为叶子类，则对子类1进行调度。 8、后续只要子类1中始终有报文，则重复第6、7步对子类1进行调度处理。
