Skip to contentSkip to conversation

sched: QFQ - quick fair queue scheduler (v2)

PATCH In review Stephen Hemminger 5 participants 37 messages Mar 1, 2011 – Mar 24, 2011 19 messages not in the archive

Subsystems (3)
Networking Network drivers Traffic control (tc)
lore
Share & tools
lore

Stephen Hemminger

author
#0 lore raw

PATCH 1/1 sched: QFQ - quick fair queue scheduler (v2)

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up and tested it. All bugs are mine.

This version is still experimental, do not use for production.

Signed-off-by Stephen Hemminger <[email protected]>

---
v2 - Did some debugging, and rebased against net-next tree.

 include/linux/pkt_sched.h |   14 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1124 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1150 insertions(+)
include/linux/pkt_sched.h +14 -0
@@ -588,4 +588,18 @@ struct tc_sfb_xstats {
 
 #define SFB_MAX_PROB 0xFFFF
 
+/* QFQ */
+enum {
+	TCA_QFQ_WEIGHT,
+	TCA_QFQ_LMAX,
+	__TCA_QFQ_MAX
+};
+
+#define TCA_QFQ_MAX	(__TCA_QFQ_MAX - 1)
+
+struct tc_qfq_stats {
+	__u32 weight;
+	__u32 lmax;
+};
+
 #endif
net/sched/Kconfig +11 -0
@@ -239,6 +239,17 @@ config NET_SCH_CHOKE
 	  To compile this code as a module, choose M here: the
 	  module will be called sch_choke.
 
+config NET_SCH_QFQ
+	tristate "Quick Fair Queueing scheduler (QFQ)"
+	help
+	  Say Y here if you want to use the Quick Fair Queueing Scheduler (QFQ)
+	  packet scheduling algorithm.
+
+	  To compile this driver as a module, choose M here: the module
+	  will be called sch_qfq.
+
+	  If unsure, say N.
+
 config NET_SCH_INGRESS
 	tristate "Ingress Qdisc"
 	depends on NET_CLS_ACT
net/sched/Makefile +1 -0
@@ -35,6 +35,7 @@ obj-$(CONFIG_NET_SCH_NETEM)	+= sch_netem
 obj-$(CONFIG_NET_SCH_DRR)	+= sch_drr.o
 obj-$(CONFIG_NET_SCH_MQPRIO)	+= sch_mqprio.o
 obj-$(CONFIG_NET_SCH_CHOKE)	+= sch_choke.o
+obj-$(CONFIG_NET_SCH_QFQ)	+= sch_qfq.o
 
 obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
 obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o
net/sched/sch_qfq.c new file +1124 -0

1,124 lines not on this page · raw message

Reviewed-by on v1 1/1
#1 lore raw
Quoted 8 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up and tested it. All bugs are mine.

This version is still experimental, do not use for production.

Signed-off-by Stephen Hemminger <[email protected]>

Seems very complex stuff ;)

Reviewed-by Eric Dumazet <[email protected]>

I'll perform some tests today with QFQ, thanks !

#2 lore raw
In reply to Stephen Hemminger

Hi,

Quoted 8 lines

From: Stephen Hemminger <[email protected]>
Date: Mon, Feb 28, 2011 05:17:38PM -0800

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up and tested it. All bugs are mine.

thanks for posting, I'm pretty sure that bugs are more likely to be
ours than yours :)

During the development of the algorithm we used a simple traffic simulator to verify (informally) the timestamping and the guarantees provided. I've tested this version of the code with the simulator and so far it worked fine, so I think that timestamping and guarantees should be OK.

Please let us know if we can be of any help,
fabio

#3 lore raw
Quoted 14 lines · Fabio Checconi

Hi,

Quoted 8 lines

From: Stephen Hemminger <[email protected]>
Date: Mon, Feb 28, 2011 05:17:38PM -0800

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up and tested it. All bugs are mine.

thanks for posting, I'm pretty sure that bugs are more likely to be
ours than yours :)

Quoted 8 lines

During the development of the algorithm we used a simple traffic simulator to verify (informally) the timestamping and the guarantees provided. I've tested this version of the code with the simulator and so far it worked fine, so I think that timestamping and guarantees should be OK.

Please let us know if we can be of any help,
fabio

Hmm, I tried to setup QFQ (using iproute2patch
http://patchwork.ozlabs.org/patch/77902/ ) but failed

Do you have a link to a script/sample ?

Thanks

author
#4 lore raw
Quoted 24 lines · On Wed, 02 Mar 2011 12:17:47 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 14 lines · Fabio Checconi

Hi,

Quoted 8 lines

From: Stephen Hemminger <[email protected]>
Date: Mon, Feb 28, 2011 05:17:38PM -0800

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up and tested it. All bugs are mine.

thanks for posting, I'm pretty sure that bugs are more likely to be
ours than yours :)

Quoted 8 lines

During the development of the algorithm we used a simple traffic simulator to verify (informally) the timestamping and the guarantees provided. I've tested this version of the code with the simulator and so far it worked fine, so I think that timestamping and guarantees should be OK.

Please let us know if we can be of any help,
fabio

Quoted 6 lines

Hmm, I tried to setup QFQ (using iproute2patch
http://patchwork.ozlabs.org/patch/77902/ ) but failed

Do you have a link to a script/sample ?

Thanks

I put the iproute2 code into the repository in the experimental branch.

#5 lore raw
Quoted 2 lines · Stephen Hemminger

I put the iproute2 code into the repository in the experimental branch.

Thanks

It seems as soon as packets are dropped, qdisc is frozen (no more packets dequeued)

Hmm...

#6 lore raw
Quoted 5 lines · Eric Dumazet
Quoted 2 lines · Stephen Hemminger

I put the iproute2 code into the repository in the experimental branch.

Quoted 7 lines

Thanks

It seems as soon as packets are dropped, qdisc is frozen (no more packets dequeued)

Hmm...

It seems class deletes are buggy.

After one "tc class del dev $ETH classid 11:1 ..."

a "tc -s -d qdisc show dev $ETH" triggers an Oops

[  414.517709] general protection fault: 0000 [#1] SMP 
[  414.517894] last sysfs file: /sys/devices/virtual/net/gre34/ifindex
[  414.517956] CPU 3 
[  414.517995] Modules linked in: sch_qfq sch_cbq ip_gre gre dummy ipmi_devintf ipmi_si ipmi_msghandler dm_mod video tg3 libphy sg [last unloaded: ip_tables]
[  414.518663] 
[  414.518717] Pid: 4692, comm: tc Not tainted 2.6.38-rc5-02726-gd486b8c-dirty #554 HP ProLiant BL460c G6
[  414.518905] RIP: 0010:[<ffffffff8145118e>]  [<ffffffff8145118e>] tc_fill_qdisc+0xbe/0x300
[  414.519025] RSP: 0018:ffff88011a123878  EFLAGS: 00010283
[  414.519085] RAX: a00e6660ffffffff RBX: 0000000000000002 RCX: 0000000000000024
[  414.519149] RDX: ffff880078683334 RSI: 0000000000000000 RDI: ffff88007867b400
[  414.519212] RBP: ffff88011a123928 R08: ffff880078683000 R09: 0000000000000002
[  414.519276] R10: 00000000000001f0 R11: 00000000000001e0 R12: ffff88007867b400
[  414.519340] R13: ffff88011cb1779c R14: ffff880078683324 R15: 0000000000001254
[  414.519405] FS:  0000000000000000(0000) GS:ffff88007fc40000(0063) knlGS:00000000f77778e0
[  414.519486] CS:  0010 DS: 002b ES: 002b CR0: 0000000080050033
[  414.519553] CR2: 00000000005ffc80 CR3: 0000000078087000 CR4: 00000000000006e0
[  414.519616] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[  414.519680] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400
[  414.519744] Process tc (pid: 4692, threadinfo ffff88011a122000, task ffff88011a1715d0)
[  414.519823] Stack:
[  414.519876]  ffff88011bbfb570 000000004d6e7c8e ffff880078683324 0000000000000000
[  414.520095]  ffff88011cb1789c ffff88007867b400 ffff8800786832bc 0000000400000003
[  414.520312]  0000000000000000 0000000000000000 0000000000000000 0000000000000000
[  414.520531] Call Trace:
[  414.520602]  [<ffffffff81451469>] tc_dump_qdisc_root+0x99/0x100
[  414.520666]  [<ffffffff81452680>] tc_dump_qdisc+0x80/0x100
[  414.520729]  [<ffffffff8146a50b>] netlink_dump+0x6b/0x1e0
[  414.520791]  [<ffffffff810f5d16>] ? kmem_cache_alloc_trace+0xb6/0x100
[  414.520855]  [<ffffffff8146d2ef>] netlink_dump_start+0x16f/0x190
[  414.520918]  [<ffffffff81452600>] ? tc_dump_qdisc+0x0/0x100
[  414.520981]  [<ffffffff81443b36>] rtnetlink_rcv_msg+0xb6/0x270
[  414.521043]  [<ffffffff81443a80>] ? rtnetlink_rcv_msg+0x0/0x270
[  414.521106]  [<ffffffff8146b609>] netlink_rcv_skb+0x99/0xc0
[  414.521167]  [<ffffffff81443a65>] rtnetlink_rcv+0x25/0x40
[  414.521229]  [<ffffffff8146b379>] netlink_unicast+0x2a9/0x2b0
[  414.521292]  [<ffffffff8142c3e3>] ? memcpy_fromiovec+0x63/0x80
[  414.521354]  [<ffffffff8146c30d>] netlink_sendmsg+0x24d/0x390
[  414.521418]  [<ffffffff81421510>] sock_sendmsg+0xc0/0xf0
[  414.521482]  [<ffffffff810b699a>] ? unlock_page+0x2a/0x40
[  414.521545]  [<ffffffff81421262>] ? move_addr_to_kernel+0x62/0x70
[  414.521608]  [<ffffffff8144d59f>] ? verify_compat_iovec+0x8f/0x100
[  414.521685]  [<ffffffff814222b0>] sys_sendmsg+0x180/0x300
[  414.521747]  [<ffffffff810d682c>] ? __pte_alloc+0xdc/0x100
[  414.521809]  [<ffffffff810d6992>] ? handle_mm_fault+0x142/0x1c0
[  414.521872]  [<ffffffff81569594>] ? do_page_fault+0x274/0x490
[  414.521935]  [<ffffffff81421f41>] ? sys_getsockname+0xa1/0xb0
[  414.521997]  [<ffffffff81421909>] ? sys_recvmsg+0x49/0x80
[  414.522059]  [<ffffffff8144d164>] compat_sys_sendmsg+0x14/0x20
[  414.522121]  [<ffffffff8144e08d>] compat_sys_socketcall+0x19d/0x1f0
[  414.522185]  [<ffffffff8102d640>] sysenter_dispatch+0x7/0x2e
[  414.522246] Code: 06 49 8d 56 10 45 89 7e 0c 66 41 89 46 04 8b 85 58 ff ff ff 41 c6 46 10 00 41 89 46 08 c6 42 01 00 66 c7 42 02 00 00 49 8b 45 68 <48> 8b 00 8b 80 c0 00 00 00 89 42 04 8b 85 5c ff ff ff 89 42 0c 
[  414.524636] RIP  [<ffffffff8145118e>] tc_fill_qdisc+0xbe/0x300
[  414.524734]  RSP <ffff88011a123878>
[  414.524799] ---[ end trace 513a4307e5c34d00 ]---
#7 lore raw

Am 02.03.2011 18:31, schrieb Eric Dumazet:

Quoted 11 lines · Eric Dumazet
Quoted 10 lines · Stephen Hemminger
Quoted 3 lines

I put the iproute2 code into the repository in the experimental branch.

Thanks

It seems as soon as packets are dropped, qdisc is frozen (no more packets dequeued)

Quoted 8 lines
Quoted 2 lines

Hmm...

It seems class deletes are buggy.

After one "tc class del dev $ETH classid 11:1 ..."

a "tc -s -d qdisc show dev $ETH" triggers an Oops

What classes and filters did you have before issuing that command?

#8 lore raw
Quoted 15 lines · Patrick McHardy

Am 02.03.2011 18:31, schrieb Eric Dumazet:

Quoted 14 lines · Eric Dumazet
Quoted 12 lines · Stephen Hemminger
Quoted 3 lines

I put the iproute2 code into the repository in the experimental branch.

Thanks

It seems as soon as packets are dropped, qdisc is frozen (no more packets dequeued)

Hmm...

Quoted 7 lines
Quoted 5 lines

It seems class deletes are buggy.

After one "tc class del dev $ETH classid 11:1 ..."

a "tc -s -d qdisc show dev $ETH" triggers an Oops

What classes and filters did you have before issuing that command?

(Fabio found the origin of the problem in qfq_destroy_class())

Here is the script I wrote to use QFQ on dummy0 device (I then use a normal udpflood workload to stress the thing)

More or less copied from other stuff I had, so its probably very stupid ;)

# cat egress_dummy0.sh
ETH=dummy0
RATE="rate 40Mbit"
PRIVNETS="172.16.0.0/12 192.168.0.0/16 10.0.0.0/8"
ALLOT="allot 20000"

ethtool -K $ETH tso off

tc qdisc del dev $ETH root 2>/dev/null

tc qdisc add dev $ETH root handle 1: cbq avpkt 1000 rate 1000Mbit \
bandwidth 1000Mbit
tc class add dev $ETH parent 1: classid 1:1 \

	est 1sec 8sec cbq allot 10000 mpu 64 \
	rate 1000Mbit prio 1 avpkt 1500 bounded
# output to private nets :  40 Mbit limit
tc class add dev $ETH parent 1:1 classid 1:11 \
	est 1sec 8sec cbq $ALLOT mpu 64      \
	$RATE prio 2 avpkt 1400 bounded

tc qdisc add dev $ETH parent 1:11 handle 11: \
est 1sec 8sec qfq

tc filter add dev $ETH protocol ip parent 11: handle 3 \
flow hash keys rxhash divisor 16

tc class add dev $ETH classid 11:1 est 0.5sec 2sec qfq weight 100 maxpkt 1100 tc class add dev $ETH classid 11:2 est 0.5sec 2sec qfq weight 200 maxpkt 1200 tc class add dev $ETH classid 11:3 est 0.5sec 2sec qfq weight 300 maxpkt 1300 tc class add dev $ETH classid 11:4 est 0.5sec 2sec qfq weight 400 maxpkt 1400 tc class add dev $ETH classid 11:5 est 0.5sec 2sec qfq weight 500 maxpkt 1500 tc class add dev $ETH classid 11:6 est 0.5sec 2sec qfq weight 600 maxpkt 1600 tc class add dev $ETH classid 11:7 est 0.5sec 2sec qfq weight 700 maxpkt 1700 tc class add dev $ETH classid 11:8 est 0.5sec 2sec qfq weight 800 maxpkt 1800 tc class add dev $ETH classid 11:9 est 0.5sec 2sec qfq weight 900 maxpkt 1900 tc class add dev $ETH classid 11:a est 0.5sec 2sec qfq weight 1000 maxpkt 2000 tc class add dev $ETH classid 11:b est 0.5sec 2sec qfq weight 1100 maxpkt 2048 tc class add dev $ETH classid 11:c est 0.5sec 2sec qfq weight 1200 maxpkt 2048 tc class add dev $ETH classid 11:d est 0.5sec 2sec qfq weight 1300 maxpkt 2048 tc class add dev $ETH classid 11:e est 0.5sec 2sec qfq weight 1400 maxpkt 2048 tc class add dev $ETH classid 11:f est 0.5sec 2sec qfq weight 1500 maxpkt 2048 tc class add dev $ETH classid 11:10 est 0.5sec 2sec qfq weight 1600 maxpkt 2048

for privnet in $PRIVNETS
do

	tc filter add dev $ETH parent 1: protocol ip prio 100 u32 \
		match ip dst $privnet flowid 1:11

done

tc filter add dev $ETH parent 1: protocol ip prio 100 u32 \

	match ip protocol 0 0x00 flowid 1:1
author
#9 lore raw
In reply to Eric Dumazet
Quoted 66 lines · On Wed, 02 Mar 2011 18:31:27 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 5 lines · Eric Dumazet
Quoted 2 lines · Stephen Hemminger

I put the iproute2 code into the repository in the experimental branch.

Quoted 7 lines

Thanks

It seems as soon as packets are dropped, qdisc is frozen (no more packets dequeued)

Hmm...

It seems class deletes are buggy.

After one "tc class del dev $ETH classid 11:1 ..."

a "tc -s -d qdisc show dev $ETH" triggers an Oops

[  414.517709] general protection fault: 0000 [#1] SMP 
[  414.517894] last sysfs file: /sys/devices/virtual/net/gre34/ifindex
[  414.517956] CPU 3 
[  414.517995] Modules linked in: sch_qfq sch_cbq ip_gre gre dummy ipmi_devintf ipmi_si ipmi_msghandler dm_mod video tg3 libphy sg [last unloaded: ip_tables]
[  414.518663] 
[  414.518717] Pid: 4692, comm: tc Not tainted 2.6.38-rc5-02726-gd486b8c-dirty #554 HP ProLiant BL460c G6
[  414.518905] RIP: 0010:[<ffffffff8145118e>]  [<ffffffff8145118e>] tc_fill_qdisc+0xbe/0x300
[  414.519025] RSP: 0018:ffff88011a123878  EFLAGS: 00010283
[  414.519085] RAX: a00e6660ffffffff RBX: 0000000000000002 RCX: 0000000000000024
[  414.519149] RDX: ffff880078683334 RSI: 0000000000000000 RDI: ffff88007867b400
[  414.519212] RBP: ffff88011a123928 R08: ffff880078683000 R09: 0000000000000002
[  414.519276] R10: 00000000000001f0 R11: 00000000000001e0 R12: ffff88007867b400
[  414.519340] R13: ffff88011cb1779c R14: ffff880078683324 R15: 0000000000001254
[  414.519405] FS:  0000000000000000(0000) GS:ffff88007fc40000(0063) knlGS:00000000f77778e0
[  414.519486] CS:  0010 DS: 002b ES: 002b CR0: 0000000080050033
[  414.519553] CR2: 00000000005ffc80 CR3: 0000000078087000 CR4: 00000000000006e0
[  414.519616] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
[  414.519680] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400
[  414.519744] Process tc (pid: 4692, threadinfo ffff88011a122000, task ffff88011a1715d0)
[  414.519823] Stack:
[  414.519876]  ffff88011bbfb570 000000004d6e7c8e ffff880078683324 0000000000000000
[  414.520095]  ffff88011cb1789c ffff88007867b400 ffff8800786832bc 0000000400000003
[  414.520312]  0000000000000000 0000000000000000 0000000000000000 0000000000000000
[  414.520531] Call Trace:
[  414.520602]  [<ffffffff81451469>] tc_dump_qdisc_root+0x99/0x100
[  414.520666]  [<ffffffff81452680>] tc_dump_qdisc+0x80/0x100
[  414.520729]  [<ffffffff8146a50b>] netlink_dump+0x6b/0x1e0
[  414.520791]  [<ffffffff810f5d16>] ? kmem_cache_alloc_trace+0xb6/0x100
[  414.520855]  [<ffffffff8146d2ef>] netlink_dump_start+0x16f/0x190
[  414.520918]  [<ffffffff81452600>] ? tc_dump_qdisc+0x0/0x100
[  414.520981]  [<ffffffff81443b36>] rtnetlink_rcv_msg+0xb6/0x270
[  414.521043]  [<ffffffff81443a80>] ? rtnetlink_rcv_msg+0x0/0x270
[  414.521106]  [<ffffffff8146b609>] netlink_rcv_skb+0x99/0xc0
[  414.521167]  [<ffffffff81443a65>] rtnetlink_rcv+0x25/0x40
[  414.521229]  [<ffffffff8146b379>] netlink_unicast+0x2a9/0x2b0
[  414.521292]  [<ffffffff8142c3e3>] ? memcpy_fromiovec+0x63/0x80
[  414.521354]  [<ffffffff8146c30d>] netlink_sendmsg+0x24d/0x390
[  414.521418]  [<ffffffff81421510>] sock_sendmsg+0xc0/0xf0
[  414.521482]  [<ffffffff810b699a>] ? unlock_page+0x2a/0x40
[  414.521545]  [<ffffffff81421262>] ? move_addr_to_kernel+0x62/0x70
[  414.521608]  [<ffffffff8144d59f>] ? verify_compat_iovec+0x8f/0x100
[  414.521685]  [<ffffffff814222b0>] sys_sendmsg+0x180/0x300
[  414.521747]  [<ffffffff810d682c>] ? __pte_alloc+0xdc/0x100
[  414.521809]  [<ffffffff810d6992>] ? handle_mm_fault+0x142/0x1c0
[  414.521872]  [<ffffffff81569594>] ? do_page_fault+0x274/0x490
[  414.521935]  [<ffffffff81421f41>] ? sys_getsockname+0xa1/0xb0
Quoted 10 lines
[  414.521997]  [<ffffffff81421909>] ? sys_recvmsg+0x49/0x80
[  414.522059]  [<ffffffff8144d164>] compat_sys_sendmsg+0x14/0x20
[  414.522121]  [<ffffffff8144e08d>] compat_sys_socketcall+0x19d/0x1f0
[  414.522185]  [<ffffffff8102d640>] sysenter_dispatch+0x7/0x2e
[  414.522246] Code: 06 49 8d 56 10 45 89 7e 0c 66 41 89 46 04 8b 85 58 ff ff ff 41 c6 46 10 00 41 89 46 08 c6 42 01 00 66 c7 42 02 00 00 49 8b 45 68 <48> 8b 00 8b 80 c0 00 00 00 89 42 04 8b 85 5c ff ff ff 89 42 0c 
[  414.524636] RIP  [<ffffffff8145118e>] tc_fill_qdisc+0xbe/0x300
[  414.524734]  RSP <ffff88011a123878>
[  414.524799] ---[ end trace 513a4307e5c34d00 ]---

Most of the class code was copied from DRR. Does it have the same problem?

#10 lore raw
In reply to Eric Dumazet

Hi,

Quoted 13 lines

From: Eric Dumazet <[email protected]>
Date: Wed, Mar 02, 2011 06:31:27PM +0100

Quoted 9 lines · Eric Dumazet
Quoted 2 lines · Stephen Hemminger

I put the iproute2 code into the repository in the experimental branch.

Thanks

It seems as soon as packets are dropped, qdisc is frozen (no more packets dequeued)

I've been able to reproduce this problem using netem, and it seems to
be due to this check:

net/sched/sch_qfq.c line 860

Quoted 3 lines
net/sched/sch_qfq.c new file +3 -0
+	/* If the new skb is not the head of queue, then done here. */
+	if (skb != qdisc_peek_head(cl->qdisc))
+		return err;

changing it to:

	if (cl->qdisc->q.qlen != 1)
		return err;

seems to make things work. I think this is because qdisc_peek_head() looks at the wrong list, as the skb is not queued directly in q, but ends up in the child qdisc attached to cl->qdisc.

Quoted 10 lines
Quoted 3 lines

Hmm...

It seems class deletes are buggy.

After one "tc class del dev $ETH classid 11:1 ..."

a "tc -s -d qdisc show dev $ETH" triggers an Oops

This seems to be due to:

net/sched/sch_qfq.c line 308

Quoted 3 lines
net/sched/sch_qfq.c new file +3 -0
+static void qfq_destroy_class(struct Qdisc *sch, struct qfq_class *cl)
+{
+	struct qfq_sched *q = (struct qfq_sched *)sch;

it should be:

	struct qfq_sched *q = sched_priv(sch);

The same bug you identified in qfq_reset_qdisc() is present also in qfq_drop(), both loops need to be corrected...

It should also be noted that this scheduler (like HFSC, IIRC) depends on the child qdisc not to reorder packets for the guarantees to be met, as the timestamps need to be in sync with the length of the packet at the head of the queue. If this can't be guaranteed, to preserve the formal correctness it should be changed to always use the maximum packet size to calculate the timestamps.

@Stephen: not that I'm proud of that, but all the bugs found so far are mine...

#11 lore raw
Quoted 25 lines · Fabio Checconi

Hi,

Quoted 13 lines

From: Eric Dumazet <[email protected]>
Date: Wed, Mar 02, 2011 06:31:27PM +0100

Quoted 9 lines · Eric Dumazet
Quoted 2 lines · Stephen Hemminger

I put the iproute2 code into the repository in the experimental branch.

Thanks

It seems as soon as packets are dropped, qdisc is frozen (no more packets dequeued)

I've been able to reproduce this problem using netem, and it seems to
be due to this check:

Review

Quoted 3 lines
(quoted diff) +3 -0
+	/* If the new skb is not the head of queue, then done here. */
+	if (skb != qdisc_peek_head(cl->qdisc))
+		return err;

changing it to:

Quoted 7 lines
	if (cl->qdisc->q.qlen != 1)
		return err;

seems to make things work. I think this is because qdisc_peek_head() looks at the wrong list, as the skb is not queued directly in q, but ends up in the child qdisc attached to cl->qdisc.

Strange, I used the default qdisc (pfifo) created in qfq classes

Quoted 25 lines
Quoted 11 lines
Quoted 4 lines

Hmm...

It seems class deletes are buggy.

After one "tc class del dev $ETH classid 11:1 ..."

a "tc -s -d qdisc show dev $ETH" triggers an Oops

This seems to be due to:

Review

Quoted 3 lines
(quoted diff) +3 -0
+static void qfq_destroy_class(struct Qdisc *sch, struct qfq_class *cl)
+{
+	struct qfq_sched *q = (struct qfq_sched *)sch;

it should be:

	struct qfq_sched *q = sched_priv(sch);

The same bug you identified in qfq_reset_qdisc() is present also in qfq_drop(), both loops need to be corrected...

Quoted 8 lines

It should also be noted that this scheduler (like HFSC, IIRC) depends on the child qdisc not to reorder packets for the guarantees to be met, as the timestamps need to be in sync with the length of the packet at the head of the queue. If this can't be guaranteed, to preserve the formal correctness it should be changed to always use the maximum packet size to calculate the timestamps.

@Stephen: not that I'm proud of that, but all the bugs found so far are mine...

I am going to test an updated version, thanks for all these hints !

#12 lore raw
Quoted 2 lines · Eric Dumazet

I am going to test an updated version, thanks for all these hints !

Same problem in qfq_qlen_notify()

Should use :

struct qfq_sched *q = qdisc_priv(sch);

After a stress (and no more trafic) I still have some packets in backlog:

(8 packets here)

# tc -s -d qdisc show dev dummy0
qdisc cbq 1: root refcnt 2 rate 1000Mbit cell 8b (bounded,isolated) prio no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 109916000 bytes 549580 pkt (dropped 350412, overlimits 1180608 requeues 0) 
 backlog 0b 8p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
qdisc qfq 11: parent 1:11 
 Sent 109916000 bytes 549580 pkt (dropped 350412, overlimits 0 requeues 0) 
 rate 2848bit 2pps backlog 0b 8p requeues 0 
# tc -s -d class show dev dummy0
class cbq 1:11 parent 1:1 leaf 11: rate 40000Kbit cell 128b mpu 64b (bounded) prio 2/2 weight 40000Kbit allot 20000b 
level 0 ewma 5 avpkt 1400b maxidle 0us 
 Sent 109916000 bytes 549580 pkt (dropped 350412, overlimits 675712 requeues 0) 
 rate 1516Kbit 947pps backlog 0b 8p requeues 0 
  borrowed 0 overactions 285254 avgidle -22 undertime -24
class cbq 1: root rate 1000Mbit cell 8b (bounded,isolated) prio no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 109916000 bytes 549580 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 0p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
class cbq 1:1 parent 1: rate 1000Mbit cell 64b mpu 64b (bounded) prio 1/1 weight 1000Mbit allot 10000b 
level 1 ewma 5 avpkt 1500b maxidle 0us 
 Sent 109916000 bytes 549580 pkt (dropped 0, overlimits 0 requeues 0) 
 rate 1516Kbit 947pps backlog 0b 0p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
class qfq 11:10 root weight 1600 maxpkt 2048 
 Sent 200 bytes 1 pkt (dropped 18181, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:1 root weight 100 maxpkt 1100 
 Sent 2731200 bytes 13656 pkt (dropped 40889, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:2 root weight 200 maxpkt 1200 
 Sent 10899800 bytes 54499 pkt (dropped 47, overlimits 0 requeues 0) 
 rate 24bit 0pps backlog 0b 0p requeues 0 
class qfq 11:3 root weight 300 maxpkt 1300 
 Sent 12714400 bytes 63572 pkt (dropped 65, overlimits 0 requeues 0) 
 rate 32bit 0pps backlog 0b 0p requeues 0 
class qfq 11:4 root weight 400 maxpkt 1400 
 Sent 400 bytes 2 pkt (dropped 36362, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:5 root weight 500 maxpkt 1500 
 Sent 400 bytes 2 pkt (dropped 45452, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:6 root weight 600 maxpkt 1600 
 Sent 800 bytes 4 pkt (dropped 27269, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:7 root weight 700 maxpkt 1700 
 Sent 600 bytes 3 pkt (dropped 45452, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:8 root weight 800 maxpkt 1800 
 Sent 1000 bytes 5 pkt (dropped 72722, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:9 root weight 900 maxpkt 1900 
 Sent 1200 bytes 6 pkt (dropped 63631, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:a root weight 1000 maxpkt 2000 
 Sent 14535200 bytes 72676 pkt (dropped 51, overlimits 0 requeues 0) 
 rate 32bit 0pps backlog 0b 0p requeues 0 
class qfq 11:b root weight 1100 maxpkt 2048 
 Sent 14531200 bytes 72656 pkt (dropped 72, overlimits 0 requeues 0) 
 rate 32bit 0pps backlog 0b 0p requeues 0 
class qfq 11:c root weight 1200 maxpkt 2048 
 Sent 10905800 bytes 54529 pkt (dropped 16, overlimits 0 requeues 0) 
 rate 24bit 0pps backlog 0b 0p requeues 0 
class qfq 11:d root weight 1300 maxpkt 2048 
 Sent 14538200 bytes 72691 pkt (dropped 36, overlimits 0 requeues 0) 
 rate 32bit 0pps backlog 0b 0p requeues 0 
class qfq 11:e root weight 1400 maxpkt 2048 
 Sent 18162200 bytes 90811 pkt (dropped 96, overlimits 0 requeues 0) 
 rate 40bit 0pps backlog 0b 0p requeues 0 
class qfq 11:f root weight 1500 maxpkt 2048 
 Sent 10895000 bytes 54475 pkt (dropped 71, overlimits 0 requeues 0) 
 rate 24bit 0pps backlog 0b 0p requeues 0
#13 lore raw
Quoted 5 lines

From: Eric Dumazet <[email protected]>
Date: Thu, Mar 03, 2011 11:40:20AM +0100

Le jeudi 03 mars 2011 à 09:27 +0100, Eric Dumazet a écrit :

Quoted 9 lines
Quoted 2 lines

I am going to test an updated version, thanks for all these hints !

Same problem in qfq_qlen_notify()

Should use :

struct qfq_sched *q = qdisc_priv(sch);

Absolutely right, as you're right about qfq_drop(). I'll be able to take a look when I'm back from work this evening.

A question on the data below:

Quoted 5 lines

After a stress (and no more trafic) I still have some packets in backlog:

(8 packets here)

...

Quoted 3 lines

class qfq 11:10 root weight 1600 maxpkt 2048
Sent 200 bytes 1 pkt (dropped 18181, overlimits 0 requeues 0) rate 0bit 0pps backlog 200b 0p requeues 0

Any other reason, apart from a bug in QFQ, why there could be 200b and 0p of backlog? A packet count out of sync could explain also why you were experiencing problems with pfifo in presence of drops...

Thanks for your help, fixes, and testing,
fabio

#14 lore raw
Quoted 7 lines · Fabio Checconi

A question on the data below:

Quoted 5 lines

After a stress (and no more trafic) I still have some packets in backlog:

(8 packets here)

Quoted 8 lines

...

Quoted 3 lines

class qfq 11:10 root weight 1600 maxpkt 2048
Sent 200 bytes 1 pkt (dropped 18181, overlimits 0 requeues 0) rate 0bit 0pps backlog 200b 0p requeues 0

Any other reason, apart from a bug in QFQ, why there could be 200b and 0p of backlog? A packet count out of sync could explain also why you were experiencing problems with pfifo in presence of drops...

My packets are all 200 bytes (from my packet generator)

qfq_dump_class_stats() probably miss one line :

scl->bstats.qlen = cl->qdisc->q.qlen;

#15 lore raw
Quoted 5 lines · Eric Dumazet

qfq_dump_class_stats() probably miss one line :

scl->bstats.qlen = cl->qdisc->q.qlen;

Hmm,

cl->qdisc->qstats.qlen = cl->qdisc->q.qlen;

It should be better ;)

#16 lore raw
Quoted 8 lines · Eric Dumazet
Quoted 5 lines · Eric Dumazet

qfq_dump_class_stats() probably miss one line :

scl->bstats.qlen = cl->qdisc->q.qlen;

Quoted 7 lines

Hmm,

cl->qdisc->qstats.qlen = cl->qdisc->q.qlen;

It should be better ;)

Indeed, 'packet count' is now correct in qfq classes

# tc -s -d qdisc show dev dummy0
qdisc cbq 1: root refcnt 2 rate 1000Mbit cell 8b (bounded,isolated) prio no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 800 bytes 4 pkt (dropped 0, overlimits 83 requeues 0) 
 backlog 0b 86p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
qdisc qfq 11: parent 1:11 
 Sent 800 bytes 4 pkt (dropped 0, overlimits 0 requeues 0) 
 rate 360bit 0pps backlog 0b 86p requeues 0 
qdisc pfifo 8001: parent 11:1 limit 30p
 Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 2400b 12p requeues 0 
qdisc pfifo 8002: parent 11:2 limit 30p
 Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 2000b 10p requeues 0 
qdisc pfifo 8003: parent 11:3 limit 30p
 Sent 200 bytes 1 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 3400b 17p requeues 0 
qdisc pfifo 8004: parent 11:4 limit 30p
 Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 1200b 6p requeues 0 
qdisc pfifo 8005: parent 11:5 limit 30p
 Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 2400b 12p requeues 0 
qdisc pfifo 8006: parent 11:6 limit 30p
 Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 1400b 7p requeues 0 
qdisc pfifo 8007: parent 11:7 limit 30p
 Sent 400 bytes 2 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 1400b 7p requeues 0 
qdisc pfifo 8008: parent 11:8 limit 30p
 Sent 200 bytes 1 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 3000b 15p requeues 0
#17 lore raw
In reply to Eric Dumazet
Quoted 82 lines · Eric Dumazet
Quoted 2 lines · Eric Dumazet

I am going to test an updated version, thanks for all these hints !

Same problem in qfq_qlen_notify()

Should use :

struct qfq_sched *q = qdisc_priv(sch);

After a stress (and no more trafic) I still have some packets in backlog:

(8 packets here)

# tc -s -d qdisc show dev dummy0
qdisc cbq 1: root refcnt 2 rate 1000Mbit cell 8b (bounded,isolated) prio no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 109916000 bytes 549580 pkt (dropped 350412, overlimits 1180608 requeues 0) 
 backlog 0b 8p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
qdisc qfq 11: parent 1:11 
 Sent 109916000 bytes 549580 pkt (dropped 350412, overlimits 0 requeues 0) 
 rate 2848bit 2pps backlog 0b 8p requeues 0 
# tc -s -d class show dev dummy0
class cbq 1:11 parent 1:1 leaf 11: rate 40000Kbit cell 128b mpu 64b (bounded) prio 2/2 weight 40000Kbit allot 20000b 
level 0 ewma 5 avpkt 1400b maxidle 0us 
 Sent 109916000 bytes 549580 pkt (dropped 350412, overlimits 675712 requeues 0) 
 rate 1516Kbit 947pps backlog 0b 8p requeues 0 
  borrowed 0 overactions 285254 avgidle -22 undertime -24
class cbq 1: root rate 1000Mbit cell 8b (bounded,isolated) prio no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 109916000 bytes 549580 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 0p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
class cbq 1:1 parent 1: rate 1000Mbit cell 64b mpu 64b (bounded) prio 1/1 weight 1000Mbit allot 10000b 
level 1 ewma 5 avpkt 1500b maxidle 0us 
 Sent 109916000 bytes 549580 pkt (dropped 0, overlimits 0 requeues 0) 
 rate 1516Kbit 947pps backlog 0b 0p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
class qfq 11:10 root weight 1600 maxpkt 2048 
 Sent 200 bytes 1 pkt (dropped 18181, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:1 root weight 100 maxpkt 1100 
 Sent 2731200 bytes 13656 pkt (dropped 40889, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:2 root weight 200 maxpkt 1200 
 Sent 10899800 bytes 54499 pkt (dropped 47, overlimits 0 requeues 0) 
 rate 24bit 0pps backlog 0b 0p requeues 0 
class qfq 11:3 root weight 300 maxpkt 1300 
 Sent 12714400 bytes 63572 pkt (dropped 65, overlimits 0 requeues 0) 
 rate 32bit 0pps backlog 0b 0p requeues 0 
class qfq 11:4 root weight 400 maxpkt 1400 
 Sent 400 bytes 2 pkt (dropped 36362, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:5 root weight 500 maxpkt 1500 
 Sent 400 bytes 2 pkt (dropped 45452, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:6 root weight 600 maxpkt 1600 
 Sent 800 bytes 4 pkt (dropped 27269, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:7 root weight 700 maxpkt 1700 
 Sent 600 bytes 3 pkt (dropped 45452, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:8 root weight 800 maxpkt 1800 
 Sent 1000 bytes 5 pkt (dropped 72722, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:9 root weight 900 maxpkt 1900 
 Sent 1200 bytes 6 pkt (dropped 63631, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 200b 0p requeues 0 
class qfq 11:a root weight 1000 maxpkt 2000 
 Sent 14535200 bytes 72676 pkt (dropped 51, overlimits 0 requeues 0) 
 rate 32bit 0pps backlog 0b 0p requeues 0 
class qfq 11:b root weight 1100 maxpkt 2048 
 Sent 14531200 bytes 72656 pkt (dropped 72, overlimits 0 requeues 0) 
 rate 32bit 0pps backlog 0b 0p requeues 0 
class qfq 11:c root weight 1200 maxpkt 2048 
 Sent 10905800 bytes 54529 pkt (dropped 16, overlimits 0 requeues 0) 
 rate 24bit 0pps backlog 0b 0p requeues 0 
class qfq 11:d root weight 1300 maxpkt 2048
Quoted 11 lines
 Sent 14538200 bytes 72691 pkt (dropped 36, overlimits 0 requeues 0) 
 rate 32bit 0pps backlog 0b 0p requeues 0 
class qfq 11:e root weight 1400 maxpkt 2048 
 Sent 18162200 bytes 90811 pkt (dropped 96, overlimits 0 requeues 0) 
 rate 40bit 0pps backlog 0b 0p requeues 0 
class qfq 11:f root weight 1500 maxpkt 2048 
 Sent 10895000 bytes 54475 pkt (dropped 71, overlimits 0 requeues 0) 
 rate 24bit 0pps backlog 0b 0p requeues 0

With debugging, I see dequeue() returns early because bitmaps[ER] is null

	if (!q->bitmaps[ER]) {
		pr_err("qfq_dequeue bitmaps[ER] is null, return NULL\n");
		return NULL;
	}
[ 3319.540984] qfq calc_index: W = 1, L = 2048, I = 19
[ 3319.544098] qfq calc_index: W = 1, L = 2048, I = 19
[ 3319.547184] qfq calc_index: W = 1, L = 2048, I = 19
[ 3319.550272] qfq calc_index: W = 1, L = 2048, I = 19
[ 3319.553354] qfq calc_index: W = 1, L = 2048, I = 19
[ 3319.556435] qfq calc_index: W = 1, L = 2048, I = 19
[ 3319.559533] qfq calc_index: W = 1, L = 2048, I = 19
[ 3319.562627] qfq calc_index: W = 1, L = 2048, I = 19
[ 3322.993412] qfq_enqueue: cl = 110004
[ 3322.993457] qfq enqueue: new state 0 0x80000 S 0 F 214748364800 V 0
[ 3322.993493] qfq dequeue: cl ffff880077d45380 len 200 F 214748364800 now 1638400
[ 3322.993543] qfq slot_scan: grp 19 full 0x0
[ 3322.993575] qfq_enqueue: cl = 110007
[ 3322.993603] qfq enqueue: new state 0 0x80000 S 1638400 F 214750003200 V 1638400
[ 3322.993653] qfq_enqueue: cl = 110006
[ 3322.993684] qfq dequeue: cl ffff880077d45100 len 200 F 214750003200 now 3276800
[ 3322.993735] qfq slot_scan: grp 19 full 0x1
[ 3322.993766] qfq_enqueue: cl = 110003
[ 3322.993797] qfq dequeue: cl ffff88011d10e080 len 200 F 214751641600 now 4915200
[ 3322.993847] qfq slot_scan: grp 19 full 0x1
[ 3322.993877] qfq_enqueue: cl = 110002
[ 3322.993906] qfq dequeue: cl ffff880077d45c00 len 200 F 214753280000 now 6553600
[ 3322.997895] qfq slot_scan: grp 19 full 0x1
[ 3322.997925] qfq_enqueue: cl = 110003
[ 3322.997956] qfq_enqueue: cl = 110004
[ 3322.997989] qfq dequeue: cl ffff880077d45380 len 200 F 429496729600 now 8192000
[ 3322.998040] qfq slot_scan: grp 19 full 0x1
[ 3322.998070] qfq_enqueue: cl = 110006
[ 3322.998099] qfq_enqueue: cl = 110008
[ 3322.998130] qfq_enqueue: cl = 110002
[ 3322.998160] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998192] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998224] qfq_enqueue: cl = 110002
[ 3322.998249] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998276] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998305] qfq_enqueue: cl = 110007
[ 3322.998333] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998363] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998395] qfq_enqueue: cl = 110001
[ 3322.998421] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998449] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998478] qfq_enqueue: cl = 110004
[ 3322.998502] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998530] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998558] qfq_enqueue: cl = 110006
[ 3322.998585] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998616] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998649] qfq_enqueue: cl = 110004
[ 3322.998677] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998708] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998739] qfq_enqueue: cl = 110007
[ 3322.998763] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998790] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998832] qfq_enqueue: cl = 110004
[ 3322.998875] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998907] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998937] qfq_enqueue: cl = 110001
[ 3322.998964] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.998997] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.999029] qfq_enqueue: cl = 110003
[ 3322.999057] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.999087] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.999120] qfq_enqueue: cl = 110007
[ 3322.999147] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.999178] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.999210] qfq_enqueue: cl = 110001
[ 3322.999234] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.999261] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.999290] qfq_enqueue: cl = 110005
[ 3322.999316] qfq_dequeue bitmaps[ER] is null, return NULL
[ 3322.999343] qfq_dequeue bitmaps[ER] is null, return NULL

[...]

Only 5 packets sent ...

qdisc cbq 1: root refcnt 2 rate 1000Mbit cell 8b (bounded,isolated) prio no-transmit/8 weight 1000Mbit allot 1514b level 2 ewma 5 avpkt 1000b maxidle 0us
Sent 1000 bytes 5 pkt (dropped 0, overlimits 82 requeues 0)
backlog 0b 85p requeues 0
borrowed 0 overactions 0 avgidle 125 undertime 0
qdisc qfq 11: parent 1:11
Sent 1000 bytes 5 pkt (dropped 0, overlimits 0 requeues 0)
rate 0bit 0pps backlog 0b 85p requeues 0
qdisc pfifo 8011: parent 11:1 limit 30p
Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0)
backlog 2600b 13p requeues 0
qdisc pfifo 8012: parent 11:2 limit 30p
Sent 200 bytes 1 pkt (dropped 0, overlimits 0 requeues 0)
backlog 2400b 12p requeues 0
qdisc pfifo 8013: parent 11:3 limit 30p
Sent 200 bytes 1 pkt (dropped 0, overlimits 0 requeues 0)
backlog 2200b 11p requeues 0
qdisc pfifo 8014: parent 11:4 limit 30p
Sent 400 bytes 2 pkt (dropped 0, overlimits 0 requeues 0)
backlog 2400b 12p requeues 0
qdisc pfifo 8015: parent 11:5 limit 30p
Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0)
backlog 2000b 10p requeues 0
qdisc pfifo 8016: parent 11:6 limit 30p
Sent 200 bytes 1 pkt (dropped 0, overlimits 0 requeues 0)
backlog 2000b 10p requeues 0
qdisc pfifo 8017: parent 11:7 limit 30p
Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0)
backlog 2400b 12p requeues 0
qdisc pfifo 8018: parent 11:8 limit 30p
Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0)
backlog 1000b 5p requeues 0

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 1299170053.2983.134.camel@edumazet-laptop

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 1299180567.2547.4.camel@edumazet-laptop

A message that is not in the archive (sent off-list or not yet received): 1299192974.2547.13.camel@edumazet-laptop

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 1299222074.2547.50.camel@edumazet-laptop

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 1299274468.2758.4.camel@edumazet-laptop

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 1299277003.2758.52.camel@edumazet-laptop

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 1299278778.2758.53.camel@edumazet-laptop

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 20110304150741.5d4aa354@nehalam

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 20110309110242.3307ca69@nehalam

A message that is not in the archive (sent off-list or not yet received): 1300016057.2761.16.camel@edumazet-laptop

A message that is not in the archive (sent off-list or not yet received): 1300034690.2761.29.camel@edumazet-laptop

#37 lore raw

[BUG] net_sched: failed bisection

Quoted 25 lines · Eric Dumazet
Quoted 10 lines · Eric Dumazet
Quoted 8 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>
Quoted 7 lines

Hi Stephen

My stress tests run fine on this version, please send it to David and netdev and feel free to add my :

Signed-off-by Eric Dumazet <[email protected]>

Ah well, no... sorry

After a while, I restarted some udpflood tests and no packet was going through my dummy0 device. So I wanted to restart my qfq_setup script and it froze :

Quoted 8 lines
root      9265 97.0  0.0  2056  440 pts/1    R+   17:41   0:29 tc qdisc del dev dummy0 root
root      9268  0.0  0.0  2452  760 pts/0    R+   17:42   0:00 ps auxw

a bit later :

root 9265 99.3 0.0 2056 440 pts/1 R+ 17:41 2:43 tc qdisc del dev dummy0 root

Hi guys

QFQ scheduler update :

While polishing QFQ scheduler, and tracking a bug in it, I finally replaced in my tc scripts "QFQ experimental" by "SFQ rock solid" and found I could have a hang in some situations :(

I made a bisection and found :

# git bisect good
7a6362800cb7d1d618a697a650c7aaed3eb39320 is the first bad commit

It seems I am stuck...

# git bisect log
git bisect start
# bad: [c360d5b53a7fec44ae4402e1f13fc888f57ddc3b] Merge branch 'master'
of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6
git bisect bad c360d5b53a7fec44ae4402e1f13fc888f57ddc3b
# good: [07a2039b8eb0af4ff464efd3dfd95de5c02648c6] Linux 2.6.30
git bisect good 07a2039b8eb0af4ff464efd3dfd95de5c02648c6
# good: [2ec8c6bb5d8f3a62a79f463525054bae1e3d4487] Merge branch 'master'
of /home/davem/src/GIT/linux-2.6/
git bisect good 2ec8c6bb5d8f3a62a79f463525054bae1e3d4487
# good: [e0e170bd7ded2ec16e2813d63c0faff43193fde8] Merge branch 'next'
of git://git.monstr.eu/linux-2.6-microblaze
git bisect good e0e170bd7ded2ec16e2813d63c0faff43193fde8
# good: [40c73abbb37e399eba274fe49e520ffa3dd65bdb] Merge branch
'for_linus' of
git://git.kernel.org/pub/scm/linux/kernel/git/jack/linux-fs-2.6
git bisect good 40c73abbb37e399eba274fe49e520ffa3dd65bdb
# good: [4b66fef9b591b95f447aea12242a1133deb0bd22] mcast: net_device dev
not used
git bisect good 4b66fef9b591b95f447aea12242a1133deb0bd22
# bad: [7a6362800cb7d1d618a697a650c7aaed3eb39320] Merge
git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next-2.6
git bisect bad 7a6362800cb7d1d618a697a650c7aaed3eb39320
# good: [971f115a50afbe409825c9f3399d5a3b9aca4381] Merge branch
'usb-next' of
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/usb-2.6
git bisect good 971f115a50afbe409825c9f3399d5a3b9aca4381
# good: [5917def58ab9f5848f2d1da835a33a490d0c8c69] staging/easycap:
reduce code nesting in easycap_sound.c
git bisect good 5917def58ab9f5848f2d1da835a33a490d0c8c69
# good: [6445ced8670f37cfc2c5e24a9de9b413dbfc788d] Merge branch
'staging-next' of
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging-2.6
git bisect good 6445ced8670f37cfc2c5e24a9de9b413dbfc788d
# good: [da91981bee8de20bcd06ee0dbddd53d62d23b1bd] ipv4: Use flowi4 in
ipmr code.
git bisect good da91981bee8de20bcd06ee0dbddd53d62d23b1bd
# good: [106af2c99a5249b809aaed45b8353ac087821f4a] Merge branch 'master'
of
git://git.kernel.org/pub/scm/linux/kernel/git/linville/wireless-next-2.6
into for-davem
git bisect good 106af2c99a5249b809aaed45b8353ac087821f4a
# good: [638be344593b66ccca6802c6076a5b3d9200829d] Phonet: fix
aligned-mode pipe socket buffer header reserve
git bisect good 638be344593b66ccca6802c6076a5b3d9200829d
# good: [c337ffb68e1e71bad069b14d2246fa1e0c31699c] Merge branch 'master'
of master.kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6
git bisect good c337ffb68e1e71bad069b14d2246fa1e0c31699c
# good: [ee0caa79569a9c44febc18480beef4847aa8cecd] Merge branch 'master'
of git://git.kernel.org/pub/scm/linux/kernel/git/kaber/nf-next-2.6
git bisect good ee0caa79569a9c44febc18480beef4847aa8cecd
# good: [0bd80dad57d82676ee484fb1f9aa4c5e8b5bc469] net: get rid of
multiple bond-related netdevice->priv_flags
git bisect good 0bd80dad57d82676ee484fb1f9aa4c5e8b5bc469
# good: [8a4eb5734e8d1dc60a8c28576bbbdfdcc643626d] net: introduce
rx_handler results and logic around that
git bisect good 8a4eb5734e8d1dc60a8c28576bbbdfdcc643626d
# good: [ceda86a108671294052cbf51660097b6534672f5] bonding: enable
netpoll without checking link status
git bisect good ceda86a108671294052cbf51660097b6534672f5

Any idea how we can find the problem ?

Script to reproduce the problem :

modprobe dummy

ifconfig dummy0 10.2.2.254 netmask 255.255.255.0 up

for i in seq 1 240
do
arp -H ether -i dummy0 -s 10.2.2.$i 00:00:0c:07:ac:$(printf %02x $i)
done

DEV=dummy0
RATE="rate 40Mbit"
TNETS="10.2.2.0/25"
ALLOT="allot 20000"

tc qdisc del dev dummy0 root 2>/dev/null

tc qdisc add dev $DEV root handle 1: est 1sec 8sec cbq avpkt 1000 rate 100Mbit \
bandwidth 100Mbit
tc class add dev $DEV parent 1: classid 1:1 \

	est 1sec 8sec cbq allot 10000 mpu 64 \
	rate 100Mbit prio 1 avpkt 1500 bounded
# output to test nets :  40 Mbit limit
tc class add dev $DEV parent 1:1 classid 1:11 \
	est 1sec 8sec cbq $ALLOT mpu 64      \
	$RATE prio 2 avpkt 1400 bounded

tc qdisc add dev $DEV parent 1:11 handle 11: \
est 1sec 8sec sfq

for privnet in $TNETS
do

	tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \
		match ip dst $privnet flowid 1:11

done

tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \

	match ip protocol 0 0x00 flowid 1:1

iperf -u -c 10.2.2.1 -P 32 -l 50
iperf -u -c 10.2.2.1 -P 32 -l 50
iperf -u -c 10.2.2.1 -P 32 -l 50
tc -s -d qdisc show dev dummy0

#38 lore raw

PATCH 1/1 net_sched: fix THROTTLED/RUNNING race

Quoted 117 lines · Eric Dumazet

While polishing QFQ scheduler, and tracking a bug in it, I finally replaced in my tc scripts "QFQ experimental" by "SFQ rock solid" and found I could have a hang in some situations :(

I made a bisection and found :

# git bisect good
7a6362800cb7d1d618a697a650c7aaed3eb39320 is the first bad commit

It seems I am stuck...

# git bisect log
git bisect start
# bad: [c360d5b53a7fec44ae4402e1f13fc888f57ddc3b] Merge branch 'master'
of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6
git bisect bad c360d5b53a7fec44ae4402e1f13fc888f57ddc3b
# good: [07a2039b8eb0af4ff464efd3dfd95de5c02648c6] Linux 2.6.30
git bisect good 07a2039b8eb0af4ff464efd3dfd95de5c02648c6
# good: [2ec8c6bb5d8f3a62a79f463525054bae1e3d4487] Merge branch 'master'
of /home/davem/src/GIT/linux-2.6/
git bisect good 2ec8c6bb5d8f3a62a79f463525054bae1e3d4487
# good: [e0e170bd7ded2ec16e2813d63c0faff43193fde8] Merge branch 'next'
of git://git.monstr.eu/linux-2.6-microblaze
git bisect good e0e170bd7ded2ec16e2813d63c0faff43193fde8
# good: [40c73abbb37e399eba274fe49e520ffa3dd65bdb] Merge branch
'for_linus' of
git://git.kernel.org/pub/scm/linux/kernel/git/jack/linux-fs-2.6
git bisect good 40c73abbb37e399eba274fe49e520ffa3dd65bdb
# good: [4b66fef9b591b95f447aea12242a1133deb0bd22] mcast: net_device dev
not used
git bisect good 4b66fef9b591b95f447aea12242a1133deb0bd22
# bad: [7a6362800cb7d1d618a697a650c7aaed3eb39320] Merge
git://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next-2.6
git bisect bad 7a6362800cb7d1d618a697a650c7aaed3eb39320
# good: [971f115a50afbe409825c9f3399d5a3b9aca4381] Merge branch
'usb-next' of
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/usb-2.6
git bisect good 971f115a50afbe409825c9f3399d5a3b9aca4381
# good: [5917def58ab9f5848f2d1da835a33a490d0c8c69] staging/easycap:
reduce code nesting in easycap_sound.c
git bisect good 5917def58ab9f5848f2d1da835a33a490d0c8c69
# good: [6445ced8670f37cfc2c5e24a9de9b413dbfc788d] Merge branch
'staging-next' of
git://git.kernel.org/pub/scm/linux/kernel/git/gregkh/staging-2.6
git bisect good 6445ced8670f37cfc2c5e24a9de9b413dbfc788d
# good: [da91981bee8de20bcd06ee0dbddd53d62d23b1bd] ipv4: Use flowi4 in
ipmr code.
git bisect good da91981bee8de20bcd06ee0dbddd53d62d23b1bd
# good: [106af2c99a5249b809aaed45b8353ac087821f4a] Merge branch 'master'
of
git://git.kernel.org/pub/scm/linux/kernel/git/linville/wireless-next-2.6
into for-davem
git bisect good 106af2c99a5249b809aaed45b8353ac087821f4a
# good: [638be344593b66ccca6802c6076a5b3d9200829d] Phonet: fix
aligned-mode pipe socket buffer header reserve
git bisect good 638be344593b66ccca6802c6076a5b3d9200829d
# good: [c337ffb68e1e71bad069b14d2246fa1e0c31699c] Merge branch 'master'
of master.kernel.org:/pub/scm/linux/kernel/git/davem/net-2.6
git bisect good c337ffb68e1e71bad069b14d2246fa1e0c31699c
# good: [ee0caa79569a9c44febc18480beef4847aa8cecd] Merge branch 'master'
of git://git.kernel.org/pub/scm/linux/kernel/git/kaber/nf-next-2.6
git bisect good ee0caa79569a9c44febc18480beef4847aa8cecd
# good: [0bd80dad57d82676ee484fb1f9aa4c5e8b5bc469] net: get rid of
multiple bond-related netdevice->priv_flags
git bisect good 0bd80dad57d82676ee484fb1f9aa4c5e8b5bc469
# good: [8a4eb5734e8d1dc60a8c28576bbbdfdcc643626d] net: introduce
rx_handler results and logic around that
git bisect good 8a4eb5734e8d1dc60a8c28576bbbdfdcc643626d
# good: [ceda86a108671294052cbf51660097b6534672f5] bonding: enable
netpoll without checking link status
git bisect good ceda86a108671294052cbf51660097b6534672f5

Any idea how we can find the problem ?

Script to reproduce the problem :

modprobe dummy

ifconfig dummy0 10.2.2.254 netmask 255.255.255.0 up

for i in seq 1 240
do
arp -H ether -i dummy0 -s 10.2.2.$i 00:00:0c:07:ac:$(printf %02x $i)
done

DEV=dummy0
RATE="rate 40Mbit"
TNETS="10.2.2.0/25"
ALLOT="allot 20000"

tc qdisc del dev dummy0 root 2>/dev/null

tc qdisc add dev $DEV root handle 1: est 1sec 8sec cbq avpkt 1000 rate 100Mbit \
bandwidth 100Mbit
tc class add dev $DEV parent 1: classid 1:1 \

	est 1sec 8sec cbq allot 10000 mpu 64 \
	rate 100Mbit prio 1 avpkt 1500 bounded
# output to test nets :  40 Mbit limit
tc class add dev $DEV parent 1:1 classid 1:11 \
	est 1sec 8sec cbq $ALLOT mpu 64      \
	$RATE prio 2 avpkt 1400 bounded

tc qdisc add dev $DEV parent 1:11 handle 11: \
est 1sec 8sec sfq

for privnet in $TNETS
do

	tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \
		match ip dst $privnet flowid 1:11

done

Quoted 9 lines

tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \

	match ip protocol 0 0x00 flowid 1:1

iperf -u -c 10.2.2.1 -P 32 -l 50
iperf -u -c 10.2.2.1 -P 32 -l 50
iperf -u -c 10.2.2.1 -P 32 -l 50
tc -s -d qdisc show dev dummy0

Okay... this bug was hard to find.

David, would you be OK if we send QFQ patch for 2.6.39 ?

I know its a bit late but its a new qdisc, very well tested now, just tell us :)

Thanks

[PATCH] net_sched: fix THROTTLED/RUNNING race

commit fd245a4adb52 (net_sched: move TCQ_F_THROTTLED flag) added a race.

qdisc_watchdog() is run from softirq, so special care should be taken or we can lose one state transition (THROTTLED/RUNNING)

Prior to fd245a4adb52, we were manipulating q->flags (qdisc->flags &= ~TCQ_F_THROTTLED;) and this manipulation could only race with qdisc_warn_nonwc().

Since we want to avoid atomic ops in qdisc fast path - it was the meaning of commit 371121057607e (QDISC_STATE_RUNNING dont need atomic bit ops) - fix is to move THROTTLE bit into 'state' field, this one being manipulated with SMP and IRQ safe operations.

Signed-off-by Eric Dumazet <[email protected]>
Cc Stephen Hemminger <[email protected]>
Cc Fabio Checconi <[email protected]>
---
 include/net/sch_generic.h |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
include/net/sch_generic.h +4 -4
index a9505b6..b931f02 100644
@@ -25,6 +25,7 @@ struct qdisc_rate_table {
 enum qdisc_state_t {
 	__QDISC_STATE_SCHED,
 	__QDISC_STATE_DEACTIVATED,
+	__QDISC_STATE_THROTTLED,
 };
 
 /*

@@ -32,7 +33,6 @@ enum qdisc_state_t {
  */
 enum qdisc___state_t {
 	__QDISC___STATE_RUNNING = 1,
-	__QDISC___STATE_THROTTLED = 2,
 };
 
 struct qdisc_size_table {

@@ -106,17 +106,17 @@ static inline void qdisc_run_end(struct Qdisc *qdisc)
 
 static inline bool qdisc_is_throttled(const struct Qdisc *qdisc)
 {
-	return (qdisc->__state & __QDISC___STATE_THROTTLED) ? true : false;
+	return test_bit(__QDISC_STATE_THROTTLED, &qdisc->state) ? true : false;
 }
 
 static inline void qdisc_throttled(struct Qdisc *qdisc)
 {
-	qdisc->__state |= __QDISC___STATE_THROTTLED;
+	set_bit(__QDISC_STATE_THROTTLED, &qdisc->state);
 }
 
 static inline void qdisc_unthrottled(struct Qdisc *qdisc)
 {
-	qdisc->__state &= ~__QDISC___STATE_THROTTLED;
+	clear_bit(__QDISC_STATE_THROTTLED, &qdisc->state);
 }
 
 struct Qdisc_class_ops {
maintainer Applied
#39 lore raw

Re: [PATCH] net_sched: fix THROTTLED/RUNNING race

From: Eric Dumazet <[email protected]>
Date: Thu, 24 Mar 2011 07:53:57 +0100

Quoted 12 lines

[PATCH] net_sched: fix THROTTLED/RUNNING race

commit fd245a4adb52 (net_sched: move TCQ_F_THROTTLED flag) added a race.

qdisc_watchdog() is run from softirq, so special care should be taken or we can lose one state transition (THROTTLED/RUNNING)

Prior to fd245a4adb52, we were manipulating q->flags (qdisc->flags &= ~TCQ_F_THROTTLED;) and this manipulation could only race with qdisc_warn_nonwc().

Quoted 6 lines

Since we want to avoid atomic ops in qdisc fast path - it was the meaning of commit 371121057607e (QDISC_STATE_RUNNING dont need atomic bit ops) - fix is to move THROTTLE bit into 'state' field, this one being manipulated with SMP and IRQ safe operations.

Signed-off-by Eric Dumazet <[email protected]>

Applied, thanks a lot for tracking this down Eric.

#40 lore raw
In reply to Fabio Checconi
Quoted 2 lines · Fabio Checconi

The same bug you identified in qfq_reset_qdisc() is present also in qfq_drop(), both loops need to be corrected...

I dont think so, because in qfq_drop() we exit from qfq_drop() right after call to qfq_deactivate_class()

But I agree code should be same ;)

#41 lore raw
In reply to Stephen Hemminger

Am 01.03.2011 02:17, schrieb Stephen Hemminger:

Quoted 8 lines

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up and tested it. All bugs are mine.

This version is still experimental, do not use for production.

Signed-off-by Stephen Hemminger <[email protected]>

Looks good to me from a qdisc API POV.

#42 lore raw
In reply to Stephen Hemminger

include/linux/pkt_sched.h struct tc_sfb_xstats { · line 592

Quoted 8 lines · Stephen Hemminger
include/linux/pkt_sched.h +2 -0
@@ -588,4 +588,18 @@ struct tc_sfb_xstats {
 
 #define SFB_MAX_PROB 0xFFFF
 
+/* QFQ */
+enum {

+ TCA_QFQ_UNSPEC,

include/linux/pkt_sched.h struct tc_sfb_xstats { · line 599

Quoted 7 lines
include/linux/pkt_sched.h +7 -0
+	TCA_QFQ_WEIGHT,
+	TCA_QFQ_LMAX,
+	__TCA_QFQ_MAX
+};
+
+#define TCA_QFQ_MAX	(__TCA_QFQ_MAX - 1)
+

With TCA_QFQ_UNSPEC bit (and mirror the change in iproute2), it seems to work better.

Oh wait, I had a crash in qfq_reset_qdisc() when re-running my setup script.

#43 lore raw
In reply to Stephen Hemminger
Quoted 4 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up and tested it. All bugs are mine.

Here is my crash analysis :

Quoted 5 lines
net/sched/sch_qfq.c new file +5 -0
+static void qfq_reset_qdisc(struct Qdisc *sch)
+{
+	struct qfq_sched *q = qdisc_priv(sch);
+	struct qfq_group *grp;
+	struct qfq_class *cl, **pp;

net/sched/sch_qfq.c line 1053

Quoted 10 lines
net/sched/sch_qfq.c new file +10 -0
+	struct hlist_node *n;
+	unsigned int i, j;
+
+	for (i = 0; i <= QFQ_MAX_INDEX; i++) {
+		grp = &q->groups[i];
+		for (j = 0; j < QFQ_MAX_SLOTS; j++) {
+			for (pp = &grp->slots[j]; *pp; pp = &(*pp)->next) {
+				cl = *pp;
+				if (cl->qdisc->q.qlen)
+					qfq_deactivate_class(q, cl, pp);

Here, if we deactivated last class in chain, *pp is NULL, but

pp = &(*pp)->next put 0x50 (on 64bit arches) in pp, so we crash ...

Quoted 11 lines
net/sched/sch_qfq.c new file +11 -0
+			}
+		}
+	}
+
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
+			qdisc_reset(cl->qdisc);
+	}
+	sch->q.qlen = 0;
+}
+
#44 lore raw
In reply to Stephen Hemminger

net/sched/sch_qfq.c line 445

Quoted 11 lines · Stephen Hemminger
net/sched/sch_qfq.c new file +11 -0
+static int qfq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
+				struct gnet_dump *d)
+{
+	struct qfq_class *cl = (struct qfq_class *)arg;
+	struct tc_qfq_stats xstats;
+
+	memset(&xstats, 0, sizeof(xstats));
+
+	xstats.weight = ONE_FP/cl->inv_w;
+	xstats.lmax = cl->lmax;
+

cl->qdisc->qstats.qlen = cl->qdisc->q.qlen;

net/sched/sch_qfq.c line 453

Quoted 8 lines
net/sched/sch_qfq.c new file +8 -0
+	if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
+	    gnet_stats_copy_rate_est(d, NULL, &cl->rate_est) < 0 ||
+	    gnet_stats_copy_queue(d, &cl->qdisc->qstats) < 0)
+		return -1;
+
+	return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
+}
+

using

	gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0

is better : We avoid dumping null rate estimation, if admin never asked a rate estimation...

author
#45 lore raw

PATCH 1/1 sched: QFQ - quick fair queue scheduler (v3)

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>

---
v3 - bug fixes found by Eric

 include/linux/pkt_sched.h |   15 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1125 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1152 insertions(+)
include/linux/pkt_sched.h +15 -0
@@ -588,4 +588,19 @@ struct tc_sfb_xstats {
 
 #define SFB_MAX_PROB 0xFFFF
 
+/* QFQ */
+enum {
+	TCA_QFQ_UNSPEC,
+	TCA_QFQ_WEIGHT,
+	TCA_QFQ_LMAX,
+	__TCA_QFQ_MAX
+};
+
+#define TCA_QFQ_MAX	(__TCA_QFQ_MAX - 1)
+
+struct tc_qfq_stats {
+	__u32 weight;
+	__u32 lmax;
+};
+
 #endif
net/sched/Kconfig +11 -0
@@ -239,6 +239,17 @@ config NET_SCH_CHOKE
 	  To compile this code as a module, choose M here: the
 	  module will be called sch_choke.
 
+config NET_SCH_QFQ
+	tristate "Quick Fair Queueing scheduler (QFQ)"
+	help
+	  Say Y here if you want to use the Quick Fair Queueing Scheduler (QFQ)
+	  packet scheduling algorithm.
+
+	  To compile this driver as a module, choose M here: the module
+	  will be called sch_qfq.
+
+	  If unsure, say N.
+
 config NET_SCH_INGRESS
 	tristate "Ingress Qdisc"
 	depends on NET_CLS_ACT
net/sched/Makefile +1 -0
@@ -35,6 +35,7 @@ obj-$(CONFIG_NET_SCH_NETEM)	+= sch_netem
 obj-$(CONFIG_NET_SCH_DRR)	+= sch_drr.o
 obj-$(CONFIG_NET_SCH_MQPRIO)	+= sch_mqprio.o
 obj-$(CONFIG_NET_SCH_CHOKE)	+= sch_choke.o
+obj-$(CONFIG_NET_SCH_QFQ)	+= sch_qfq.o
 
 obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
 obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o
net/sched/sch_qfq.c new file +1125 -0

1,125 lines not on this page · raw message

#46 lore raw

Re: [PATCH] sched: QFQ - quick fair queue scheduler (v3)

Quoted 8 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>
Quoted 9 lines

---
v3 - bug fixes found by Eric

 include/linux/pkt_sched.h |   15 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1125 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1152 insertions(+)

Hmm... please compile before sending your patches ;)

You used sched_priv(sch) calls instead of qdisc_priv(sch)

net/sched/sch_qfq.c line 308

Quoted 5 lines
net/sched/sch_qfq.c new file +5 -0
+}
+
+static void qfq_destroy_class(struct Qdisc *sch, struct qfq_class *cl)
+{
+	struct qfq_sched *q = sched_priv(sch);

	q = qdisc_priv(sch);
Quoted 5 lines
net/sched/sch_qfq.c new file +5 -0
+
+	if (cl->inv_w) {
+		q->wsum -= ONE_FP / cl->inv_w;
+		cl->inv_w = 0;
+	}

net/sched/sch_qfq.c

Quoted 10 lines
net/sched/sch_qfq.c new file +9 -0
+
+	gen_kill_estimator(&cl->bstats, &cl->rate_est);
+	qdisc_destroy(cl->qdisc);
+	kfree(cl);
+}
 
+
+static void qfq_qlen_notify(struct Qdisc *sch, unsigned long arg)
+{
+	struct qfq_sched *q = sched_priv(sch);

	q = qdisc_priv(sch);
Quoted 14 lines
net/sched/sch_qfq.c new file +11 -0
+	struct qfq_class *cl = (struct qfq_class *)arg;
+
+	if (cl->qdisc->q.qlen == 0)
+		qfq_deactivate_class(q, cl, NULL);
+}
+
 
 
 
+static void qfq_reset_qdisc(struct Qdisc *sch)
+{
+	struct qfq_sched *q = qdisc_priv(sch);
+	struct qfq_group *grp;
+	struct qfq_class *cl, **pp;

net/sched/sch_qfq.c line 1054

Quoted 10 lines
net/sched/sch_qfq.c new file +10 -0
+	struct hlist_node *n;
+	unsigned int i, j;
+
+	for (i = 0; i <= QFQ_MAX_INDEX; i++) {
+		grp = &q->groups[i];
+		for (j = 0; j < QFQ_MAX_SLOTS; j++) {
+			for (pp = &grp->slots[j]; *pp; pp = &(*pp)->next) {
+				cl = *pp;
+				if (cl->qdisc->q.qlen)
+					qfq_deactivate_class(q, cl, pp);

Here there is the problem of *pp = cl->next (possibly NULL)

		maybe use

	for (pp = &grp->slots[j]; (cl = *pp) != NULL;) {
		if (cl->qdisc->q.len)
			qfq_deactivate_class(...);
		else
			pp = &cl->next;
	}
Quoted 11 lines
net/sched/sch_qfq.c new file +11 -0
+			}
+		}
+	}
+
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
+			qdisc_reset(cl->qdisc);
+	}
+	sch->q.qlen = 0;
+}
+
author
#47 lore raw

Re: [PATCH] sched: QFQ - quick fair queue scheduler (v3)

Quoted 20 lines · On Thu, 03 Mar 2011 23:28:53 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 8 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>
Quoted 9 lines

---
v3 - bug fixes found by Eric

 include/linux/pkt_sched.h |   15 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1125 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1152 insertions(+)
Quoted 3 lines

Hmm... please compile before sending your patches ;)

You used sched_priv(sch) calls instead of qdisc_priv(sch)

Argh, forgot to do quilt --refresh

author
#48 lore raw

PATCH 1/1 sched: QFQ - quick fair queue scheduler (v3.1)

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>

---
v3 - fix bugs in statistics and initialization

 include/linux/pkt_sched.h |   15 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1125 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1152 insertions(+)
include/linux/pkt_sched.h +15 -0
@@ -588,4 +588,19 @@ struct tc_sfb_xstats {
 
 #define SFB_MAX_PROB 0xFFFF
 
+/* QFQ */
+enum {
+	TCA_QFQ_UNSPEC,
+	TCA_QFQ_WEIGHT,
+	TCA_QFQ_LMAX,
+	__TCA_QFQ_MAX
+};
+
+#define TCA_QFQ_MAX	(__TCA_QFQ_MAX - 1)
+
+struct tc_qfq_stats {
+	__u32 weight;
+	__u32 lmax;
+};
+
 #endif
net/sched/Kconfig +11 -0
@@ -239,6 +239,17 @@ config NET_SCH_CHOKE
 	  To compile this code as a module, choose M here: the
 	  module will be called sch_choke.
 
+config NET_SCH_QFQ
+	tristate "Quick Fair Queueing scheduler (QFQ)"
+	help
+	  Say Y here if you want to use the Quick Fair Queueing Scheduler (QFQ)
+	  packet scheduling algorithm.
+
+	  To compile this driver as a module, choose M here: the module
+	  will be called sch_qfq.
+
+	  If unsure, say N.
+
 config NET_SCH_INGRESS
 	tristate "Ingress Qdisc"
 	depends on NET_CLS_ACT
net/sched/Makefile +1 -0
@@ -35,6 +35,7 @@ obj-$(CONFIG_NET_SCH_NETEM)	+= sch_netem
 obj-$(CONFIG_NET_SCH_DRR)	+= sch_drr.o
 obj-$(CONFIG_NET_SCH_MQPRIO)	+= sch_mqprio.o
 obj-$(CONFIG_NET_SCH_CHOKE)	+= sch_choke.o
+obj-$(CONFIG_NET_SCH_QFQ)	+= sch_qfq.o
 
 obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
 obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o
net/sched/sch_qfq.c new file +1125 -0

1,125 lines not on this page · raw message

#49 lore raw

Re: [PATCH] sched: QFQ - quick fair queue scheduler (v3.1)

Quoted 8 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>

Oh well, did you read my previous mail ?

Quoted 6 lines
net/sched/sch_qfq.c new file +6 -0
+
+static void qfq_reset_qdisc(struct Qdisc *sch)
+{
+	struct qfq_sched *q = qdisc_priv(sch);
+	struct qfq_group *grp;
+	struct qfq_class *cl, **pp;

net/sched/sch_qfq.c line 1054

Quoted 10 lines
net/sched/sch_qfq.c new file +10 -0
+	struct hlist_node *n;
+	unsigned int i, j;
+
+	for (i = 0; i <= QFQ_MAX_INDEX; i++) {
+		grp = &q->groups[i];
+		for (j = 0; j < QFQ_MAX_SLOTS; j++) {
+			for (pp = &grp->slots[j]; *pp; pp = &(*pp)->next) {
+				cl = *pp;
+				if (cl->qdisc->q.qlen)
+					qfq_deactivate_class(q, cl, pp);

Here there is the problem of *pp = cl->next (possibly NULL)

maybe use

        for (pp = &grp->slots[j]; (cl = *pp) != NULL;) {
                if (cl->qdisc->q.len)
                        qfq_deactivate_class(...);
                else
                        pp = &cl->next;
        }
Quoted 11 lines
net/sched/sch_qfq.c new file +11 -0
+			}
+		}
+	}
+
+	for (i = 0; i < q->clhash.hashsize; i++) {
+		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
+			qdisc_reset(cl->qdisc);
+	}
+	sch->q.qlen = 0;
+}
+
author
#50 lore raw

Re: [PATCH] sched: QFQ - quick fair queue scheduler (v3)

In reply to Eric Dumazet
Quoted 11 lines · On Thu, 03 Mar 2011 23:28:53 +0100 Eric Dumazet <[email protected]> wrote:

Here there is the problem of *pp = cl->next (possibly NULL)

		maybe use

	for (pp = &grp->slots[j]; (cl = *pp) != NULL;) {
		if (cl->qdisc->q.len)
			qfq_deactivate_class(...);
		else
			pp = &cl->next;
	}

I think changing slots from open coded linked list to double linked list (list_for_each) would be clearer and avoid these kind of bugs. That is what DRR does.

author
#51 lore raw

Re: [PATCH] sched: QFQ - quick fair queue scheduler (v4)

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>

---
v4 - change slots[] to hlist from simple linked list

 include/linux/pkt_sched.h |   15 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1133 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1160 insertions(+)
include/linux/pkt_sched.h +15 -0
@@ -588,4 +588,19 @@ struct tc_sfb_xstats {
 
 #define SFB_MAX_PROB 0xFFFF
 
+/* QFQ */
+enum {
+	TCA_QFQ_UNSPEC,
+	TCA_QFQ_WEIGHT,
+	TCA_QFQ_LMAX,
+	__TCA_QFQ_MAX
+};
+
+#define TCA_QFQ_MAX	(__TCA_QFQ_MAX - 1)
+
+struct tc_qfq_stats {
+	__u32 weight;
+	__u32 lmax;
+};
+
 #endif
net/sched/Kconfig +11 -0
@@ -239,6 +239,17 @@ config NET_SCH_CHOKE
 	  To compile this code as a module, choose M here: the
 	  module will be called sch_choke.
 
+config NET_SCH_QFQ
+	tristate "Quick Fair Queueing scheduler (QFQ)"
+	help
+	  Say Y here if you want to use the Quick Fair Queueing Scheduler (QFQ)
+	  packet scheduling algorithm.
+
+	  To compile this driver as a module, choose M here: the module
+	  will be called sch_qfq.
+
+	  If unsure, say N.
+
 config NET_SCH_INGRESS
 	tristate "Ingress Qdisc"
 	depends on NET_CLS_ACT
net/sched/Makefile +1 -0
@@ -35,6 +35,7 @@ obj-$(CONFIG_NET_SCH_NETEM)	+= sch_netem
 obj-$(CONFIG_NET_SCH_DRR)	+= sch_drr.o
 obj-$(CONFIG_NET_SCH_MQPRIO)	+= sch_mqprio.o
 obj-$(CONFIG_NET_SCH_CHOKE)	+= sch_choke.o
+obj-$(CONFIG_NET_SCH_QFQ)	+= sch_qfq.o
 
 obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
 obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o
net/sched/sch_qfq.c new file +1133 -0

1,133 lines not on this page · raw message

#52 lore raw

Re: [PATCH] sched: QFQ - quick fair queue scheduler (v4)

Quoted 8 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>
Quoted 8 lines

---
v4 - change slots[] to hlist from simple linked list

 include/linux/pkt_sched.h |   15 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1133 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1160 insertions(+)

Thanks

Still crashing hard here in qfq_reset_qdisc(), when packets are present in queues.

Probably hlist_for_each_entry_safe() is needed, since qfq_deactivate_class() is called ...

Also rename cl->next to cl->hnode so that following is clearer ?

- hlist_for_each_entry(cl, n, &grp->slots[j], next) {
+ hlist_for_each_entry_safe(cl, n, next, &grp->slots[j], hnode) {

Fabio, any idea why everything is blocked after a few packets for me ?

Here is script to reproduce the problem :

# cat qfq_setup.sh
modprobe dummy

ifconfig dummy0 10.2.2.254 netmask 255.255.255.0 up

for i in seq 1 16
do
arp -H ether -i dummy0 -s 10.2.2.$i 00:00:0c:07:ac:$(printf %02x $i)
done

DEV=dummy0
RATE="rate 40Mbit"
TNETS="10.2.2.0/25"
ALLOT="allot 20000"

tc qdisc del dev dummy0 root 2>/dev/null

tc qdisc add dev $DEV root handle 1: cbq avpkt 1000 rate 1000Mbit \
bandwidth 1000Mbit
tc class add dev $DEV parent 1: classid 1:1 \

	est 1sec 8sec cbq allot 10000 mpu 64 \
	rate 1000Mbit prio 1 avpkt 1500 bounded
# output to test nets :  40 Mbit limit
tc class add dev $DEV parent 1:1 classid 1:11 \
	est 1sec 8sec cbq $ALLOT mpu 64      \
	$RATE prio 2 avpkt 1400 bounded

tc qdisc add dev $DEV parent 1:11 handle 11: \
est 1sec 8sec qfq

tc filter add dev $DEV protocol ip parent 11: handle 3 \
flow hash keys rxhash divisor 8

for i in seq 1 8
do
classid=11:$(printf %x $i)
tc class add dev $DEV classid $classid qfq tc qdisc add dev $DEV parent $classid pfifo limit 30
done

for privnet in $TNETS
do

	tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \
		match ip dst $privnet flowid 1:11

done

tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \

	match ip protocol 0 0x00 flowid 1:1

iperf -u -c 10.2.2.1 -P 32 -l 50

------------------------------------------------------------------------------

After a run I get only 5 packets sent, 240 queued in backlog, and all other packets dropped.

# tc -s -d qdisc show dev dummy0
qdisc cbq 1: root refcnt 2 rate 1000Mbit cell 8b (bounded,isolated) prio
no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 460 bytes 5 pkt (dropped 198800, overlimits 199043 requeues 0) 
 backlog 0b 240p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
qdisc qfq 11: parent 1:11 
 Sent 460 bytes 5 pkt (dropped 198800, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 0b 240p requeues 0 
qdisc pfifo 8011: parent 11:1 limit 30p
 Sent 0 bytes 0 pkt (dropped 6178, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8012: parent 11:2 limit 30p
 Sent 92 bytes 1 pkt (dropped 37048, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8013: parent 11:3 limit 30p
 Sent 0 bytes 0 pkt (dropped 24856, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8014: parent 11:4 limit 30p
 Sent 276 bytes 3 pkt (dropped 37358, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8015: parent 11:5 limit 30p
 Sent 0 bytes 0 pkt (dropped 24934, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8016: parent 11:6 limit 30p
 Sent 0 bytes 0 pkt (dropped 24882, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8017: parent 11:7 limit 30p
 Sent 0 bytes 0 pkt (dropped 12328, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8018: parent 11:8 limit 30p
 Sent 92 bytes 1 pkt (dropped 31216, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0

and :

# tc -s -d class show dev dummy0
class cbq 1:11 parent 1:1 leaf 11: rate 40000Kbit cell 128b mpu 64b
(bounded) prio 2/2 weight 40000Kbit allot 20000b 
level 0 ewma 5 avpkt 1400b maxidle 0us 
 Sent 460 bytes 5 pkt (dropped 198800, overlimits 15 requeues 0) 
 rate 0bit 0pps backlog 0b 240p requeues 0 
  borrowed 0 overactions 3 avgidle -225 undertime -6.46702e+07
class cbq 1: root rate 1000Mbit cell 8b (bounded,isolated) prio
no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 460 bytes 5 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 0p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
class cbq 1:1 parent 1: rate 1000Mbit cell 64b mpu 64b (bounded) prio
1/1 weight 1000Mbit allot 10000b 
level 1 ewma 5 avpkt 1500b maxidle 0us 
 Sent 460 bytes 5 pkt (dropped 0, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 0b 0p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
class qfq 11:1 root leaf 8011: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 6178, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:2 root leaf 8012: weight 1 maxpkt 2048 
 Sent 2852 bytes 31 pkt (dropped 37048, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:3 root leaf 8013: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 24856, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:4 root leaf 8014: weight 1 maxpkt 2048 
 Sent 3036 bytes 33 pkt (dropped 37358, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:5 root leaf 8015: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 24934, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:6 root leaf 8016: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 24882, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:7 root leaf 8017: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 12328, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:8 root leaf 8018: weight 1 maxpkt 2048 
 Sent 2852 bytes 31 pkt (dropped 31216, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0

Then this crashes :

# tc qdisc del dev dummy0 root
author
#53 lore raw

Re: [PATCH] sched: QFQ - quick fair queue scheduler (v4)

Quoted 180 lines · On Fri, 04 Mar 2011 07:50:26 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 8 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>
Quoted 8 lines

---
v4 - change slots[] to hlist from simple linked list

 include/linux/pkt_sched.h |   15 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1133 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1160 insertions(+)

Thanks

Still crashing hard here in qfq_reset_qdisc(), when packets are present in queues.

Probably hlist_for_each_entry_safe() is needed, since qfq_deactivate_class() is called ...

Also rename cl->next to cl->hnode so that following is clearer ?

(quoted diff) +1 -1
-	hlist_for_each_entry(cl, n, &grp->slots[j], next) {
+	hlist_for_each_entry_safe(cl, n, next, &grp->slots[j], hnode) {

Fabio, any idea why everything is blocked after a few packets for me ?

Here is script to reproduce the problem :

# cat qfq_setup.sh
modprobe dummy

ifconfig dummy0 10.2.2.254 netmask 255.255.255.0 up

for i in seq 1 16
do
arp -H ether -i dummy0 -s 10.2.2.$i 00:00:0c:07:ac:$(printf %02x $i)
done

DEV=dummy0
RATE="rate 40Mbit"
TNETS="10.2.2.0/25"
ALLOT="allot 20000"

tc qdisc del dev dummy0 root 2>/dev/null

tc qdisc add dev $DEV root handle 1: cbq avpkt 1000 rate 1000Mbit \
bandwidth 1000Mbit
tc class add dev $DEV parent 1: classid 1:1 \

	est 1sec 8sec cbq allot 10000 mpu 64 \
	rate 1000Mbit prio 1 avpkt 1500 bounded
# output to test nets :  40 Mbit limit
tc class add dev $DEV parent 1:1 classid 1:11 \
	est 1sec 8sec cbq $ALLOT mpu 64      \
	$RATE prio 2 avpkt 1400 bounded

tc qdisc add dev $DEV parent 1:11 handle 11: \
est 1sec 8sec qfq

tc filter add dev $DEV protocol ip parent 11: handle 3 \
flow hash keys rxhash divisor 8

for i in seq 1 8
do
classid=11:$(printf %x $i)
tc class add dev $DEV classid $classid qfq tc qdisc add dev $DEV parent $classid pfifo limit 30
done

for privnet in $TNETS
do

	tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \
		match ip dst $privnet flowid 1:11

done

tc filter add dev $DEV parent 1: protocol ip prio 100 u32 \

	match ip protocol 0 0x00 flowid 1:1

iperf -u -c 10.2.2.1 -P 32 -l 50

------------------------------------------------------------------------------

After a run I get only 5 packets sent, 240 queued in backlog, and all other packets dropped.

# tc -s -d qdisc show dev dummy0
qdisc cbq 1: root refcnt 2 rate 1000Mbit cell 8b (bounded,isolated) prio
no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 460 bytes 5 pkt (dropped 198800, overlimits 199043 requeues 0) 
 backlog 0b 240p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
qdisc qfq 11: parent 1:11 
 Sent 460 bytes 5 pkt (dropped 198800, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 0b 240p requeues 0 
qdisc pfifo 8011: parent 11:1 limit 30p
 Sent 0 bytes 0 pkt (dropped 6178, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8012: parent 11:2 limit 30p
 Sent 92 bytes 1 pkt (dropped 37048, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8013: parent 11:3 limit 30p
 Sent 0 bytes 0 pkt (dropped 24856, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8014: parent 11:4 limit 30p
 Sent 276 bytes 3 pkt (dropped 37358, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8015: parent 11:5 limit 30p
 Sent 0 bytes 0 pkt (dropped 24934, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8016: parent 11:6 limit 30p
 Sent 0 bytes 0 pkt (dropped 24882, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8017: parent 11:7 limit 30p
 Sent 0 bytes 0 pkt (dropped 12328, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
qdisc pfifo 8018: parent 11:8 limit 30p
 Sent 92 bytes 1 pkt (dropped 31216, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0

and :

# tc -s -d class show dev dummy0
class cbq 1:11 parent 1:1 leaf 11: rate 40000Kbit cell 128b mpu 64b
(bounded) prio 2/2 weight 40000Kbit allot 20000b 
level 0 ewma 5 avpkt 1400b maxidle 0us 
 Sent 460 bytes 5 pkt (dropped 198800, overlimits 15 requeues 0) 
 rate 0bit 0pps backlog 0b 240p requeues 0 
  borrowed 0 overactions 3 avgidle -225 undertime -6.46702e+07
class cbq 1: root rate 1000Mbit cell 8b (bounded,isolated) prio
no-transmit/8 weight 1000Mbit allot 1514b 
level 2 ewma 5 avpkt 1000b maxidle 0us 
 Sent 460 bytes 5 pkt (dropped 0, overlimits 0 requeues 0) 
 backlog 0b 0p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
class cbq 1:1 parent 1: rate 1000Mbit cell 64b mpu 64b (bounded) prio
1/1 weight 1000Mbit allot 10000b 
level 1 ewma 5 avpkt 1500b maxidle 0us 
 Sent 460 bytes 5 pkt (dropped 0, overlimits 0 requeues 0) 
 rate 0bit 0pps backlog 0b 0p requeues 0 
  borrowed 0 overactions 0 avgidle 125 undertime 0
class qfq 11:1 root leaf 8011: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 6178, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:2 root leaf 8012: weight 1 maxpkt 2048 
 Sent 2852 bytes 31 pkt (dropped 37048, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:3 root leaf 8013: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 24856, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:4 root leaf 8014: weight 1 maxpkt 2048 
 Sent 3036 bytes 33 pkt (dropped 37358, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:5 root leaf 8015: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 24934, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:6 root leaf 8016: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 24882, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:7 root leaf 8017: weight 1 maxpkt 2048 
 Sent 2760 bytes 30 pkt (dropped 12328, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0 
class qfq 11:8 root leaf 8018: weight 1 maxpkt 2048 
 Sent 2852 bytes 31 pkt (dropped 31216, overlimits 0 requeues 0) 
 backlog 2760b 30p requeues 0
Quoted 3 lines

Then this crashes :

# tc qdisc del dev dummy0 root

hlist_for_each_entry_safe fixes that.

Can you reproduce without putting cbq on the root?

author
#54 lore raw

Re: [PATCH] sched: QFQ - quick fair queue scheduler (v4)

In reply to Eric Dumazet
Quoted 50 lines · On Fri, 04 Mar 2011 07:50:26 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 8 lines · Stephen Hemminger

This is an implementation of the Quick Fair Queue scheduler developed by Fabio Checconi. The same algorithm is already implemented in ipfw in FreeBSD. Fabio had an earlier version developed on Linux, I just cleaned it up. Thanks to Eric Dumazet for doing the testing and finding bugs.

Signed-off-by Stephen Hemminger <[email protected]>
Quoted 8 lines

---
v4 - change slots[] to hlist from simple linked list

 include/linux/pkt_sched.h |   15 
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_qfq.c       | 1133 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1160 insertions(+)

Thanks

Still crashing hard here in qfq_reset_qdisc(), when packets are present in queues.

Probably hlist_for_each_entry_safe() is needed, since qfq_deactivate_class() is called ...

Also rename cl->next to cl->hnode so that following is clearer ?

(quoted diff) +1 -1
-	hlist_for_each_entry(cl, n, &grp->slots[j], next) {
+	hlist_for_each_entry_safe(cl, n, next, &grp->slots[j], hnode) {

Fabio, any idea why everything is blocked after a few packets for me ?

Here is script to reproduce the problem :

# cat qfq_setup.sh
modprobe dummy

ifconfig dummy0 10.2.2.254 netmask 255.255.255.0 up

for i in seq 1 16
do
arp -H ether -i dummy0 -s 10.2.2.$i 00:00:0c:07:ac:$(printf %02x $i)
done

DEV=dummy0
RATE="rate 40Mbit"
TNETS="10.2.2.0/25"
ALLOT="allot 20000"

Quoted 4 lines

tc qdisc del dev dummy0 root 2>/dev/null

tc qdisc add dev $DEV root handle 1: cbq avpkt 1000 rate 1000Mbit \
bandwidth 1000Mbit

QFQ is non work conserving, it may choose to send a smaller packet ahead of a larger packet in other flow...

author
#55 lore raw

QFQ debugfs

In reply to Eric Dumazet

This is quick hack to put a debugfs hook on:
debug/qfq/<device>

dumps internal state

---
 net/sched/sch_qfq.c |   59 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 59 insertions(+)
net/sched/sch_qfq.c +59 -0
@@ -14,6 +14,7 @@
 #include <linux/errno.h>
 #include <linux/netdevice.h>
 #include <linux/pkt_sched.h>
+#include <linux/debugfs.h>
 #include <net/sch_generic.h>
 #include <net/pkt_sched.h>
 #include <net/pkt_cls.h>

@@ -144,6 +145,7 @@ struct qfq_group {
 struct qfq_sched {
 	struct tcf_proto *filter_list;
 	struct Qdisc_class_hash clhash;
+	struct dentry	     *debugfs;
 
 	u64		V;		/* Precise virtual time. */
 	u32		wsum;		/* weight sum */

@@ -1025,6 +1027,55 @@ static unsigned int qfq_drop(struct Qdis
 	return 0;
 }
 
+static struct dentry *qfq_debug;
+
+static int qfq_debug_show(struct seq_file *seq, void *v)
+{
+	struct Qdisc *sch = seq->private;
+	const struct qfq_sched *q = qdisc_priv(sch);
+	unsigned int i, j;
+
+	seq_printf(seq, "V=%llu wsum=%u\n", q->V, q->wsum);
+	for (i = 0; i < QFQ_MAX_STATE; i++)
+		seq_printf(seq, "%lx%c", q->bitmaps[i],
+			   (i & 3) == 3 ? '\n' : ' ');
+
+	for (i = 0; i <= QFQ_MAX_INDEX; i++) {
+		const struct qfq_group *grp = &q->groups[i];
+		seq_printf(seq, "%d: S=%llu F=%llu shift=%u index=%u front=%u full=%#lx\n",
+			   i, (unsigned long long)grp->S,
+			   (unsigned long long)grp->F,
+			   grp->slot_shift, grp->index,
+			   grp->front, grp->full_slots);
+
+		for (j = 0; j < QFQ_MAX_SLOTS; j++) {
+			const struct qfq_class *cl;
+			struct hlist_node *n;
+
+			hlist_for_each_entry(cl, n, &grp->slots[j], next) {
+				seq_printf(seq, "  %d: S=%llu F=%llu inv_w=%u lmax=%u\n",
+					   j, cl->S, cl->F,
+					   cl->inv_w, cl->lmax);
+			}
+		}
+	}
+	return 0;
+}
+
+static int qfq_debug_open(struct inode *inode, struct file *file)
+{
+	return single_open(file, qfq_debug_show, inode->i_private);
+}
+
+static const struct file_operations qfq_debug_fops = {
+	.owner		= THIS_MODULE,
+	.open		= qfq_debug_open,
+	.read		= seq_read,
+	.llseek		= seq_lseek,
+	.release	= single_release,
+};
+
+
 static int qfq_init_qdisc(struct Qdisc *sch, struct nlattr *opt)
 {
 	struct qfq_sched *q = qdisc_priv(sch);

@@ -1042,6 +1093,9 @@ static int qfq_init_qdisc(struct Qdisc *
 			INIT_HLIST_HEAD(&grp->slots[j]);
 	}
 
+	q->debugfs = debugfs_create_file(sch->dev_queue->dev->name,
+					 S_IRUGO, qfq_debug, sch,
+					 &qfq_debug_fops);
 	return 0;
 }
 

@@ -1121,11 +1175,16 @@ static struct Qdisc_ops qfq_qdisc_ops __
 
 static int __init qfq_init(void)
 {
+	qfq_debug = debugfs_create_dir("qfq", NULL);
+
 	return register_qdisc(&qfq_qdisc_ops);
 }
 
 static void __exit qfq_exit(void)
 {
+	if (qfq_debug)
+		debugfs_remove(qfq_debug);
+
 	unregister_qdisc(&qfq_qdisc_ops);
 }