Linux sch_htb令牌桶层级令牌借贷与borrow传播HTBHierarchical Token Bucket位于net/sched/sch_htb.c构建层级令牌桶树形结构。每个class拥有rate保证速率和ceil上限速率两个令牌桶父子class间通过borrow机制传递令牌。令牌生成的入口在htb_charge_class每次出队报文后扣除相应class的令牌static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,int bytes, int level){long tokens;int deficit;long new_tokens;long new_etime;do {int mdiff;long diff;if (cl-level level)break;tokens atomic_long_read(cl-tokens);if (tokens HTB_HPRIORITY_LAST)break;new_tokens q-now cl-cbuffer;if (tokens new_tokens)tokens new_tokens;diff tokens - now;if (cl-cmode ! HTB_CAN_SEND)break;cl-tokens tokens - bytes;cl-age q-now;if (cl-tokens -cl-quantum) {htb_safe_rb_erase(cl-pq_node, q-hprio[cl-aprio]);RB_CLEAR_NODE(cl-pq_node);cl-cmode HTB_MAY_BORROW;}mdiff atomic_long_sub_return(bytes, cl-borrowed);if (mdiff cl-quantum) {htb_borrow_cb(cl, bytes);}cl cl-parent;} while (cl);}每个class的cmode有三种状态HTB_CAN_SEND令牌充足可直接发送、HTB_MAY_BORROW自身令牌不足允许向父class借贷、HTB_CANT_SEND父class也无令牌可用不可发送。状态切换通过htb_class_mode函数判定static void htb_class_mode(struct htb_class *cl, int *diff){WARN_ON_ONCE(!spin_is_locked(cl-sched-lock));if (cl-tokens 0) {*diff cl-quantum;cl-cmode HTB_CAN_SEND;} else if (cl-borrowed -cl-quantum) {*diff -cl-tokens;cl-cmode HTB_MAY_BORROW;} else {*diff 0;cl-cmode HTB_CANT_SEND;}}borrow传播的核心逻辑在htb_dequeue_tree中体现static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio){struct htb_class *cl, *start;struct sk_buff *skb;int m;start cl htb_lookup_leaf(q, prio);if (!cl)return NULL;do {if (cl-cmode HTB_CAN_SEND) {skb htb_dequeue_leaf(q, cl, prio);if (skb) {htb_charge_class(q, cl, skb-len, cl-level);return skb;}}if (cl-cmode HTB_MAY_BORROW) {if (!cl-parent || cl-parent-cmode HTB_CANT_SEND)continue;if (htb_borrow(q, cl)) {skb htb_dequeue_leaf(q, cl, prio);if (skb) {htb_charge_class(q, cl, skb-len, cl-level);return skb;}}}cl cl-next;} while (cl ! start);return NULL;}实际borrow执行在htb_borrow函数该函数尝试从父class借取令牌static int htb_borrow(struct htb_sched *q, struct htb_class *cl){struct htb_class *parent cl-parent;long tokens;long borrowed;long needed;if (!parent || parent-cmode HTB_CANT_SEND)return 0;needed cl-quantum;borrowed atomic_long_read(cl-borrowed);tokens atomic_long_read(parent-tokens);if (parent-cmode HTB_CAN_SEND) {if (tokens needed) {atomic_long_sub(needed, parent-tokens);atomic_long_add(needed, cl-borrowed);return 1;}return 0;}if (parent-cmode HTB_MAY_BORROW)return htb_borrow(q, parent);return 0;}令牌的定时补充通过htb_work_func高位精度定时器实现static void htb_work_func(struct hrb *work){struct htb_sched *q container_of(work, struct htb_sched,htimer.work);struct Qdisc *sch q-sch;struct htb_class *cl;u64 now ktime_get_ns();long diff;spin_lock_bh(sch-lock);q-jiffies jiffies;list_for_each_entry(cl, q-drops, drops_list) {do {diff cl-mbuffer - (long)(now - cl-age);if (diff 0) {cl-tokens min_t(long, cl-tokens cl-rate.rate *(long)TICK_NSEC, cl-buffer);cl-age now;}} while (0);htb_class_mode(cl, diff);if (diff)htb_activate(q, cl);}if (__netif_schedule(sch))hrtimer_start(q-htimer, ns_to_ktime(q-rate_delt),HRTIMER_MODE_REL_PINNED);spin_unlock_bh(sch-lock);}每个class维护两个令牌桶tokens对应rate保证带宽ctokens对应ceil上限带宽。htb_charge_class同时扣除两个桶的令牌。当ctokens桶用完时即使从父class借到了令牌报文仍会因超过ceil而被限流或丢弃。时间片用jiffies和ktime_get_ns混合计算保证在低速率下也能精确产生令牌。层级拓扑在htb_change_class时建立parent指针指向父classlevel字段标识层级深度。叶子class在htb_destroy_class时级联销毁子class。根class的rate必须为全qdisc总带宽否则上层的borrow调用会因父class令牌不足而失败导致下层的ceil限流失效。