net/sched: Fix backlog accounting in qdisc_dequeue_internal
Subsystems (4)
PATCH v5 1/2 net/sched: Fix backlog accounting in qdisc_dequeue_internal
This issue applies for the following qdiscs: hhf, fq, fq_codel, and fq_pie, and occurs in their change handlers when adjusting to the new limit. The problem is the following in the values passed to the subsequent qdisc_tree_reduce_backlog call given a tbf parent:
When the tbf parent runs out of tokens, skbs of these qdiscs will be placed in gso_skb. Their peek handlers are qdisc_peek_dequeued, which accounts for both qlen and backlog. However, in the case of qdisc_dequeue_internal, ONLY qlen is accounted for when pulling from gso_skb. This means that these qdiscs are missing a qdisc_qstats_backlog_dec when dropping packets to satisfy the new limit in their change handlers.
One can observe this issue with the following (with tc patched to support a limit of 0):
export TARGET=fq
tc qdisc del dev lo root
tc qdisc add dev lo root handle 1: tbf rate 8bit burst 100b latency 1ms tc qdisc replace dev lo handle 3: parent 1:1 $TARGET limit 1000 echo ''; echo 'add child'; tc -s -d qdisc show dev lo
ping -I lo -f -c2 -s32 -W0.001 127.0.0.1 2>&1 >/dev/null echo ''; echo 'after ping'; tc -s -d qdisc show dev lo
tc qdisc change dev lo handle 3: parent 1:1 $TARGET limit 0 echo ''; echo 'after limit drop'; tc -s -d qdisc show dev lo tc qdisc replace dev lo handle 2: parent 1:1 sfq
echo ''; echo 'post graft'; tc -s -d qdisc show dev lo
The second to last show command shows 0 packets but a positive number (74) of backlog bytes. The problem becomes clearer in the last show command, where qdisc_purge_queue triggers qdisc_tree_reduce_backlog with the positive backlog and causes an underflow in the tbf parent's backlog (4096 Mb instead of 0).
To fix this issue, the codepath for all clients of qdisc_dequeue_internal has been simplified: codel, pie, hhf, fq, fq_pie, and fq_codel. qdisc_dequeue_internal handles the backlog adjustments for all cases that do not directly use the dequeue handler.
The old fq_codel_change limit adjustment loop accumulated the arguments to the subsequent qdisc_tree_reduce_backlog call through the cstats field. However, this is confusing and error prone as fq_codel_dequeue could also potentially mutate this field (which qdisc_dequeue_internal calls in the non gso_skb case), so we have unified the code here with other qdiscs.
---
v4 -> v5:
- address formatting nit, update commit message with additional clarifications, unify limit adjustment loops to suggested style from Jakub
v1 -> v2:
- Fix commit formatting
- There was a suggestion to split the patch apart into one for each qdisc - however, individual qdisc behavior will be further broken by this split due to the reliance on qdisc_dequeue_internal
--- include/net/sch_generic.h | 11 ++++++++--- net/sched/sch_codel.c | 12 +++++++----- net/sched/sch_fq.c | 12 +++++++----- net/sched/sch_fq_codel.c | 12 +++++++----- net/sched/sch_fq_pie.c | 12 +++++++----- net/sched/sch_hhf.c | 12 +++++++----- net/sched/sch_pie.c | 12 +++++++----- 7 files changed, 50 insertions(+), 33 deletions(-)
include/net/sch_generic.h +8 -3
@@ -1038,12 +1038,17 @@ static inline struct sk_buff *qdisc_dequeue_internal(struct Qdisc *sch, bool dir skb =__skb_dequeue (&sch->gso_skb);if (skb) { sch->q.qlen--; +qdisc_qstats_backlog_dec (sch, skb);return skb; } -if (direct) -return __qdisc_dequeue_head (&sch->q); -else +if (direct) { + skb =__qdisc_dequeue_head (&sch->q); +if (skb) +qdisc_qstats_backlog_dec (sch, skb); +return skb; + }else {return sch->dequeue (sch); + } }static inline struct sk_buff *qdisc_dequeue_head (struct Qdisc *sch)
net/sched/sch_codel.c +7 -5
@@ -101,9 +101,9 @@ static const struct nla_policy codel_policy[TCA_CODEL_MAX + 1] = {static int codel_change (struct Qdisc *sch,struct nlattr *opt,struct netlink_ext_ack *extack) { +unsigned int dropped_pkts =0 , dropped_bytes =0 ;struct codel_sched_data *q =qdisc_priv (sch);struct nlattr *tb[TCA_CODEL_MAX +1 ]; -unsigned int qlen, dropped =0 ;int err; err = nla_parse_nested_deprecated(tb, TCA_CODEL_MAX, opt,
@@ -142,15 +142,17 @@ static int codel_change(struct Qdisc *sch, struct nlattr *opt,WRITE_ONCE (q->params.ecn, !!nla_get_u32 (tb[TCA_CODEL_ECN ])); - qlen = sch->q.qlen;while (sch->q.qlen > sch->limit) {struct sk_buff *skb =qdisc_dequeue_internal (sch, true); - dropped +=qdisc_pkt_len (skb); -qdisc_qstats_backlog_dec (sch, skb); +if (!skb) +break ; + + dropped_pkts++; + dropped_bytes +=qdisc_pkt_len (skb);rtnl_qdisc_drop (skb, sch); } -qdisc_tree_reduce_backlog (sch, qlen - sch->q.qlen, dropped); +qdisc_tree_reduce_backlog (sch, dropped_pkts, dropped_bytes);sch_tree_unlock (sch);return 0 ;
net/sched/sch_fq.c +7 -5
@@ -1013,11 +1013,11 @@ static int fq_load_priomap(struct fq_sched_data *q,static int fq_change (struct Qdisc *sch,struct nlattr *opt,struct netlink_ext_ack *extack) { +unsigned int dropped_pkts =0 , dropped_bytes =0 ;struct fq_sched_data *q =qdisc_priv (sch);struct nlattr *tb[TCA_FQ_MAX +1 ]; -int err, drop_count =0 ; -unsigned drop_len =0 ;u32 fq_log; +int err; err =nla_parse_nested_deprecated (tb,TCA_FQ_MAX , opt, fq_policy,NULL );
@@ -1135,16 +1135,18 @@ static int fq_change(struct Qdisc *sch, struct nlattr *opt, err =fq_resize (sch, fq_log);sch_tree_lock (sch); } +while (sch->q.qlen > sch->limit) {struct sk_buff *skb =qdisc_dequeue_internal (sch, false);if (!skb)break ; - drop_len +=qdisc_pkt_len (skb); + + dropped_pkts++; + dropped_bytes +=qdisc_pkt_len (skb);rtnl_kfree_skbs (skb, skb); - drop_count++; } -qdisc_tree_reduce_backlog (sch, drop_count, drop_len); +qdisc_tree_reduce_backlog (sch, dropped_pkts, dropped_bytes);sch_tree_unlock (sch);return err;
net/sched/sch_fq_codel.c +7 -5
@@ -366,6 +366,7 @@ static const struct nla_policy fq_codel_policy[TCA_FQ_CODEL_MAX + 1] = {static int fq_codel_change (struct Qdisc *sch,struct nlattr *opt,struct netlink_ext_ack *extack) { +unsigned int dropped_pkts =0 , dropped_bytes =0 ;struct fq_codel_sched_data *q =qdisc_priv (sch);struct nlattr *tb[TCA_FQ_CODEL_MAX +1 ];u32 quantum =0 ;
@@ -443,13 +444,14 @@ static int fq_codel_change(struct Qdisc *sch, struct nlattr *opt, q->memory_usage > q->memory_limit) {struct sk_buff *skb =qdisc_dequeue_internal (sch, false); - q->cstats.drop_len +=qdisc_pkt_len (skb); +if (!skb) +break ; + + dropped_pkts++; + dropped_bytes +=qdisc_pkt_len (skb);rtnl_kfree_skbs (skb, skb); - q->cstats.drop_count++; } -qdisc_tree_reduce_backlog (sch, q->cstats.drop_count, q->cstats.drop_len); - q->cstats.drop_count =0 ; - q->cstats.drop_len =0 ; +qdisc_tree_reduce_backlog (sch, dropped_pkts, dropped_bytes);sch_tree_unlock (sch);return 0 ;
net/sched/sch_fq_pie.c +7 -5
@@ -287,10 +287,9 @@ static struct sk_buff *fq_pie_qdisc_dequeue(struct Qdisc *sch)static int fq_pie_change (struct Qdisc *sch,struct nlattr *opt,struct netlink_ext_ack *extack) { +unsigned int dropped_pkts =0 , dropped_bytes =0 ;struct fq_pie_sched_data *q =qdisc_priv (sch);struct nlattr *tb[TCA_FQ_PIE_MAX +1 ]; -unsigned int len_dropped =0 ; -unsigned int num_dropped =0 ;int err; err =nla_parse_nested (tb,TCA_FQ_PIE_MAX , opt, fq_pie_policy, extack);
@@ -368,11 +367,14 @@ static int fq_pie_change(struct Qdisc *sch, struct nlattr *opt,while (sch->q.qlen > sch->limit) {struct sk_buff *skb =qdisc_dequeue_internal (sch, false); - len_dropped +=qdisc_pkt_len (skb); - num_dropped +=1 ; +if (!skb) +break ; + + dropped_pkts++; + dropped_bytes +=qdisc_pkt_len (skb);rtnl_kfree_skbs (skb, skb); } -qdisc_tree_reduce_backlog (sch, num_dropped, len_dropped); +qdisc_tree_reduce_backlog (sch, dropped_pkts, dropped_bytes);sch_tree_unlock (sch);return 0 ;
net/sched/sch_hhf.c +7 -5
@@ -508,9 +508,9 @@ static const struct nla_policy hhf_policy[TCA_HHF_MAX + 1] = {static int hhf_change (struct Qdisc *sch,struct nlattr *opt,struct netlink_ext_ack *extack) { +unsigned int dropped_pkts =0 , dropped_bytes =0 ;struct hhf_sched_data *q =qdisc_priv (sch);struct nlattr *tb[TCA_HHF_MAX +1 ]; -unsigned int qlen, prev_backlog;int err;u64 non_hh_quantum;u32 new_quantum = q->quantum;
@@ -561,15 +561,17 @@ static int hhf_change(struct Qdisc *sch, struct nlattr *opt, usecs_to_jiffies(us)); } - qlen = sch->q.qlen; - prev_backlog = sch->qstats.backlog;while (sch->q.qlen > sch->limit) {struct sk_buff *skb =qdisc_dequeue_internal (sch, false); +if (!skb) +break ; + + dropped_pkts++; + dropped_bytes +=qdisc_pkt_len (skb);rtnl_kfree_skbs (skb, skb); } -qdisc_tree_reduce_backlog (sch, qlen - sch->q.qlen, - prev_backlog - sch->qstats.backlog); +qdisc_tree_reduce_backlog (sch, dropped_pkts, dropped_bytes);sch_tree_unlock (sch);return 0 ;
net/sched/sch_pie.c +7 -5
@@ -141,9 +141,9 @@ static const struct nla_policy pie_policy[TCA_PIE_MAX + 1] = {static int pie_change (struct Qdisc *sch,struct nlattr *opt,struct netlink_ext_ack *extack) { +unsigned int dropped_pkts =0 , dropped_bytes =0 ;struct pie_sched_data *q =qdisc_priv (sch);struct nlattr *tb[TCA_PIE_MAX +1 ]; -unsigned int qlen, dropped =0 ;int err; err = nla_parse_nested_deprecated(tb, TCA_PIE_MAX, opt, pie_policy,
@@ -193,15 +193,17 @@ static int pie_change(struct Qdisc *sch, struct nlattr *opt, nla_get_u32(tb[TCA_PIE_DQ_RATE_ESTIMATOR]));/* Drop excess packets if new limit is lower */ - qlen = sch->q.qlen;while (sch->q.qlen > sch->limit) {struct sk_buff *skb =qdisc_dequeue_internal (sch, true); - dropped +=qdisc_pkt_len (skb); -qdisc_qstats_backlog_dec (sch, skb); +if (!skb) +break ; + + dropped_pkts++; + dropped_bytes +=qdisc_pkt_len (skb);rtnl_qdisc_drop (skb, sch); } -qdisc_tree_reduce_backlog (sch, qlen - sch->q.qlen, dropped); +qdisc_tree_reduce_backlog (sch, dropped_pkts, dropped_bytes);sch_tree_unlock (sch);return 0 ;
Signature · 1 line
2.43.0
PATCH v5 2/2 selftests/tc-testing: Check backlog stats in gso_skb case
Add tests to ensure proper backlog accounting in hhf, codel, pie, fq, fq_pie, and fq_codel qdiscs. We check for the bug pattern originally found in fq, fq_pie, and fq_codel, which was an underflow in the tbf parent backlog stats upon child qdisc removal.
---
v3 -> v4:
- Unify tests to check against underflow in tbf stats on purge
v2 -> v3:
- Simplify ping command in test cases
- Remove scapyPlugin dependency
--- .../tc-testing/tc-tests/infra/qdiscs.json | 198 ++++++++++++++++++ 1 file changed, 198 insertions(+)
tools/testing/selftests/tc-testing/tc-tests/infra/qdiscs.json +198 -0
@@ -185,6 +185,204 @@ "$IP addr del 10.10.10.10/24 dev $DUMMY || true" ] }, + { + "id": "34c0", + "name": "Test TBF with HHF Backlog Accounting in gso_skb case against underflow", + "category": [ + "qdisc", + "tbf", + "hhf" + ], + "plugins": { + "requires": [ + "nsPlugin" + ] + }, + "setup": [ + "$IP link set dev $DUMMY up || true", + "$IP addr add 10.10.11.10/24 dev $DUMMY || true", + "$TC qdisc add dev $DUMMY root handle 1: tbf rate 8bit burst 100b latency 100ms", + "$TC qdisc replace dev $DUMMY handle 2: parent 1:1 hhf limit 1000", + [ + "ping -I $DUMMY -c2 10.10.11.11", + 1 + ], + "$TC qdisc change dev $DUMMY handle 2: parent 1:1 hhf limit 1" + ], + "cmdUnderTest": "$TC qdisc del dev $DUMMY handle 2: parent 1:1", + "expExitCode": "0", + "verifyCmd": "$TC -s qdisc show dev $DUMMY", + "matchPattern": "backlog 0b 0p", + "matchCount": "1", + "teardown": [ + "$TC qdisc del dev $DUMMY handle 1: root" + ] + }, + { + "id": "fd68", + "name": "Test TBF with CODEL Backlog Accounting in gso_skb case against underflow", + "category": [ + "qdisc", + "tbf", + "codel" + ], + "plugins": { + "requires": [ + "nsPlugin" + ] + }, + "setup": [ + "$IP link set dev $DUMMY up || true", + "$IP addr add 10.10.11.10/24 dev $DUMMY || true", + "$TC qdisc add dev $DUMMY root handle 1: tbf rate 8bit burst 100b latency 100ms", + "$TC qdisc replace dev $DUMMY handle 2: parent 1:1 codel limit 1000", + [ + "ping -I $DUMMY -c2 10.10.11.11", + 1 + ], + "$TC qdisc change dev $DUMMY handle 2: parent 1:1 codel limit 1" + ], + "cmdUnderTest": "$TC qdisc del dev $DUMMY handle 2: parent 1:1", + "expExitCode": "0", + "verifyCmd": "$TC -s qdisc show dev $DUMMY", + "matchPattern": "backlog 0b 0p", + "matchCount": "1", + "teardown": [ + "$TC qdisc del dev $DUMMY handle 1: root" + ] + }, + { + "id": "514e", + "name": "Test TBF with PIE Backlog Accounting in gso_skb case against underflow", + "category": [ + "qdisc", + "tbf", + "pie" + ], + "plugins": { + "requires": [ + "nsPlugin" + ] + }, + "setup": [ + "$IP link set dev $DUMMY up || true", + "$IP addr add 10.10.11.10/24 dev $DUMMY || true", + "$TC qdisc add dev $DUMMY root handle 1: tbf rate 8bit burst 100b latency 100ms", + "$TC qdisc replace dev $DUMMY handle 2: parent 1:1 pie limit 1000", + [ + "ping -I $DUMMY -c2 10.10.11.11", + 1 + ], + "$TC qdisc change dev $DUMMY handle 2: parent 1:1 pie limit 1" + ], + "cmdUnderTest": "$TC qdisc del dev $DUMMY handle 2: parent 1:1", + "expExitCode": "0", + "verifyCmd": "$TC -s qdisc show dev $DUMMY", + "matchPattern": "backlog 0b 0p", + "matchCount": "1", + "teardown": [ + "$TC qdisc del dev $DUMMY handle 1: root" + ] + }, + { + "id": "6c97", + "name": "Test TBF with FQ Backlog Accounting in gso_skb case against underflow", + "category": [ + "qdisc", + "tbf", + "fq" + ], + "plugins": { + "requires": [ + "nsPlugin" + ] + }, + "setup": [ + "$IP link set dev $DUMMY up || true", + "$IP addr add 10.10.11.10/24 dev $DUMMY || true", + "$TC qdisc add dev $DUMMY root handle 1: tbf rate 8bit burst 100b latency 100ms", + "$TC qdisc replace dev $DUMMY handle 2: parent 1:1 fq limit 1000", + [ + "ping -I $DUMMY -c2 10.10.11.11", + 1 + ], + "$TC qdisc change dev $DUMMY handle 2: parent 1:1 fq limit 1" + ], + "cmdUnderTest": "$TC qdisc del dev $DUMMY handle 2: parent 1:1", + "expExitCode": "0", + "verifyCmd": "$TC -s qdisc show dev $DUMMY", + "matchPattern": "backlog 0b 0p", + "matchCount": "1", + "teardown": [ + "$TC qdisc del dev $DUMMY handle 1: root" + ] + }, + { + "id": "5d0b", + "name": "Test TBF with FQ_CODEL Backlog Accounting in gso_skb case against underflow", + "category": [ + "qdisc", + "tbf", + "fq_codel" + ], + "plugins": { + "requires": [ + "nsPlugin" + ] + }, + "setup": [ + "$IP link set dev $DUMMY up || true", + "$IP addr add 10.10.11.10/24 dev $DUMMY || true", + "$TC qdisc add dev $DUMMY root handle 1: tbf rate 8bit burst 100b latency 100ms", + "$TC qdisc replace dev $DUMMY handle 2: parent 1:1 fq_codel limit 1000", + [ + "ping -I $DUMMY -c2 10.10.11.11", + 1 + ], + "$TC qdisc change dev $DUMMY handle 2: parent 1:1 fq_codel limit 1" + ], + "cmdUnderTest": "$TC qdisc del dev $DUMMY handle 2: parent 1:1", + "expExitCode": "0", + "verifyCmd": "$TC -s qdisc show dev $DUMMY", + "matchPattern": "backlog 0b 0p", + "matchCount": "1", + "teardown": [ + "$TC qdisc del dev $DUMMY handle 1: root" + ] + }, + { + "id": "21c3", + "name": "Test TBF with FQ_PIE Backlog Accounting in gso_skb case against underflow", + "category": [ + "qdisc", + "tbf", + "fq_pie" + ], + "plugins": { + "requires": [ + "nsPlugin" + ] + }, + "setup": [ + "$IP link set dev $DUMMY up || true", + "$IP addr add 10.10.11.10/24 dev $DUMMY || true", + "$TC qdisc add dev $DUMMY root handle 1: tbf rate 8bit burst 100b latency 100ms", + "$TC qdisc replace dev $DUMMY handle 2: parent 1:1 fq_pie limit 1000", + [ + "ping -I $DUMMY -c2 10.10.11.11", + 1 + ], + "$TC qdisc change dev $DUMMY handle 2: parent 1:1 fq_pie limit 1" + ], + "cmdUnderTest": "$TC qdisc del dev $DUMMY handle 2: parent 1:1", + "expExitCode": "0", + "verifyCmd": "$TC -s qdisc show dev $DUMMY", + "matchPattern": "backlog 0b 0p", + "matchCount": "1", + "teardown": [ + "$TC qdisc del dev $DUMMY handle 1: root" + ] + }, { "id": "a4bb", "name": "Test FQ_CODEL with HTB parent - force packet drop with empty queue",
Signature · 1 line
2.43.0
This series was applied to netdev/net.git (main) by Jakub Kicinski <[email protected]>:
Hello:
This series was applied to netdev/net.git (main)
by Jakub Kicinski <[email protected]>:
Quoted 13 lines · On Tue, 12 Aug 2025 23:57:57 +0000 you wrote:
This issue applies for the following qdiscs: hhf, fq,
fq_codel, andfq_pie, and occurs in their change handlers when adjusting to the new limit. The problem is the following in the values passed to the subsequentqdisc_tree_reduce_backlogcall given a tbf parent:When the tbf parent runs out of tokens, skbs of these qdiscs will be placed in
gso_skb. Their peek handlers areqdisc_peek_dequeued, which accounts for both qlen and backlog. However, in the case ofqdisc_dequeue_internal, ONLY qlen is accounted for when pulling fromgso_skb. This means that these qdiscs are missing aqdisc_qstats_backlog_decwhen dropping packets to satisfy the new limit in their change handlers.
Quoted 1 line
[...]
Here is the summary with links:
- [net,v5,1/2] net/sched: Fix backlog accounting in qdisc_dequeue_internal
https://git.kernel.org/netdev/net/c/52bf272636bd
- [net,v5,2/2] selftests/tc-testing: Check backlog stats in gso_skb case
https://git.kernel.org/netdev/net/c/8c06cbdcbaea
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html