Re: Netem tfifo implementation

[Patrick McHardy <kaber@trash.net>]

Ritesh Kumar wrote:
> Hi,
>    I recently saw the qdisc "tfifo" in the netem module
> (net/sched/sch_netem.c) when I migrated some of my patches from 2.6.14
> to 2.6.20. As I understand, tfifo helps in keeping the queue of
> packets sorted according to their "time_to_send". [tfifo was not
> present in 2.6.14 perhaps because arrival order of packets was always
> equal to the departure order]. However, tfifo uses a linear search in
> the packet queue to find where to enqueue the packet.
>    Quite some time ago (2.6.14 era), I needed a similar functionality
> from the netem module and I ended up coding a pointer based min-heap
> for the same. I was wondering if the community was interested in using
> the min-heap implementation to replace the linear search
> implementation. I have tested the min-heap quite a few times and it
> seems to work.
>    The implementation is slightly non-trivial because it uses
> pointers to maintain the heap structure instead if using good old
> fixed size arrays. I did this mainly so that the limit of the netem
> qdisc could be changed on the fly. However, because every sk_buff now
> needs two pointers for its children nodes, I added an extra
> (sk_buff*)next2 to struct sk_buff (sorry!). However, this can probably
> be changed to a pointer inside netem_skb_cb.  Also, because I needed
> this for personal work and 2.6.14 didn't contain tfifo, I basically
> removed the embedded qdisc and made netem a classless qdisc with my
> min heap as the native "queue" (sorry again! :) )

The tfifo qdisc has a limit, why not just allocate a fixed-size heap
based on that?