[PATCH net-next] sch_netem: faster rb tree removal

[Eric Dumazet]

From: Eric Dumazet <eduma...@google.com>

While running TCP tests involving netem storing millions of packets,
I had the idea to speed up tfifo_reset() and did experiments.

I tried the rbtree_postorder_for_each_entry_safe() method that is
used in skb_rbtree_purge() but discovered it was slower than the
current tfifo_reset() method.

I measured time taken to release skbs with three occupation levels :
10^4, 10^5 and 10^6 skbs with three methods :

1) (current 'naive' method)

        while ((p = rb_first(&q->t_root))) {
                struct sk_buff *skb = netem_rb_to_skb(p);
 
                rb_erase(p, &q->t_root);
                rtnl_kfree_skbs(skb, skb);
        }

2) Use rb_next() instead of rb_first() in the loop :

        p = rb_first(&q->t_root);
        while (p) {
                struct sk_buff *skb = netem_rb_to_skb(p);

                p = rb_next(p);
                rb_erase(&skb->rbnode, &q->t_root);
                rtnl_kfree_skbs(skb, skb);
        }

3) "optimized" method using rbtree_postorder_for_each_entry_safe()

        struct sk_buff *skb, *next;

        rbtree_postorder_for_each_entry_safe(skb, next,
                                             &q->t_root, rbnode) {
               rtnl_kfree_skbs(skb, skb);
        }
        q->t_root = RB_ROOT;

Results :

method_1:while (rb_first()) rb_erase() 10000 skbs in 690378 ns (69 ns per skb)
method_2:rb_first; while (p) { p = rb_next(p); ...}  10000 skbs in 541846 ns 
(54 ns per skb)
method_3:rbtree_postorder_for_each_entry_safe() 10000 skbs in 868307 ns (86 ns 
per skb)

method_1:while (rb_first()) rb_erase() 99996 skbs in 7804021 ns (78 ns per skb)
method_2:rb_first; while (p) { p = rb_next(p); ...}  100000 skbs in 5942456 ns 
(59 ns per skb)
method_3:rbtree_postorder_for_each_entry_safe() 100000 skbs in 11584940 ns (115 
ns per skb)

method_1:while (rb_first()) rb_erase() 1000000 skbs in 108577838 ns (108 ns per 
skb)
method_2:rb_first; while (p) { p = rb_next(p); ...}  1000000 skbs in 82619635 
ns (82 ns per skb)
method_3:rbtree_postorder_for_each_entry_safe() 1000000 skbs in 127328743 ns 
(127 ns per skb)

Method 2) is simply faster, probably because it maintains a smaller
working size set.

Note that this is the method we use in tcp_ofo_queue() already.

I will also change skb_rbtree_purge() in a second patch.

Signed-off-by: Eric Dumazet <eduma...@google.com>
---
 net/sched/sch_netem.c |    7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 
063a4bdb9ee6f26b01387959e8f6ccd15ec16191..5a4f1008029068372019a965186e7a3c0a18aac3
 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -361,12 +361,13 @@ static psched_time_t packet_len_2_sched_time(unsigned int 
len, struct netem_sche
 static void tfifo_reset(struct Qdisc *sch)
 {
        struct netem_sched_data *q = qdisc_priv(sch);
-       struct rb_node *p;
+       struct rb_node *p = rb_first(&q->t_root);
 
-       while ((p = rb_first(&q->t_root))) {
+       while (p) {
                struct sk_buff *skb = netem_rb_to_skb(p);
 
-               rb_erase(p, &q->t_root);
+               p = rb_next(p);
+               rb_erase(&skb->rbnode, &q->t_root);
                rtnl_kfree_skbs(skb, skb);
        }
 }