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? - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
