[1/1] sched: add head drop fifo queue

This add an additional queuing strategy, called {p,b}fifo_head_drop,
to remove the oldest skb in the case of an overflow within the queue -
the head element - instead of the last skb (tail). To remove the oldest
skb in a congested situations is useful for sensor network environments
where newer packets reflects the superior information.

Reviewed-by: Florian Westphal <fw@strlen.de>
Signed-off-by: Hagen Paul Pfeifer <hagen@jauu.net>
---
 include/net/pkt_sched.h |    2 +
 net/sched/sch_api.c     |    2 +
 net/sched/sch_fifo.c    |   78 ++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 81 insertions(+), 1 deletions(-)

Hagen Paul Pfeifer wrote:
> diff --git a/net/sched/sch_fifo.c b/net/sched/sch_fifo.c
> index 69188e8..8286882 100644
> --- a/net/sched/sch_fifo.c
> +++ b/net/sched/sch_fifo.c
> @@ -43,6 +43,50 @@ static int pfifo_enqueue(struct sk_buff *skb, struct Qdisc* sch)
>  	return qdisc_reshape_fail(skb, sch);
>  }
>  
> +static int bfifo_front_enqueue(struct sk_buff *skb, struct Qdisc* sch)
> +{
> +	struct fifo_sched_data *q = qdisc_priv(sch);
> +	const unsigned int skb_len = qdisc_pkt_len(skb);
> +
> +	if (likely(sch->qstats.backlog + qdisc_pkt_len(skb) <= q->limit))
> +		return qdisc_enqueue_tail(skb, sch);
> +
> +	/* queue full -> remove skb's from the queue head until we
> +	 * undershoot the queue limit in bytes */
> +	do {
> +		struct sk_buff *skb_head = qdisc_dequeue_head(sch);
> +		if (skb_head == NULL)
> +			return qdisc_reshape_fail(skb, sch);
> +		sch->bstats.bytes -= qdisc_pkt_len(skb_head);
> +		sch->bstats.packets--;
> +		sch->q.qlen--;

This won't work if the qdisc is used as leaf qdisc. The upper qdisc
will increment q.qlen by one when the skb was successfully enqueued,
so it will differ from the real queue length, which is not allowed.
You need to call qdisc_tree_decrease_qlen() to adjust all qlen values
in the hierarchy. Additionally you might want to consider returning
NET_XMIT_CN in this case to inform the upper layers of congestion.
Be aware though that in this case, the upper qdisc won't increment
its q.qlen, so qdisc_tree_decrease_qlen() needs to use one less that
the actual number of dropped packets.

If you don't actually need the bfifo, I'd suggest to only add the
pfifo head drop qdisc since qdisc_tree_decrease_qlen() is kind of
expensive and mainly meant for exceptional cases.

> +		sch->qstats.drops++;
> +		kfree_skb(skb_head);
> +	} while (sch->qstats.backlog + skb_len > q->limit);
> +
> +	return qdisc_enqueue_tail(skb, sch);
> +}
> +
> +static int pfifo_front_enqueue(struct sk_buff *skb, struct Qdisc* sch)
> +{
> +	struct sk_buff *skb_head;
> +	struct fifo_sched_data *q = qdisc_priv(sch);
> +
> +	if (likely(skb_queue_len(&sch->q) < q->limit))
> +		return qdisc_enqueue_tail(skb, sch);
> +
> +	/* queue full, remove one skb to fulfill the limit */
> +	skb_head = qdisc_dequeue_head(sch);
> +	sch->bstats.bytes -= qdisc_pkt_len(skb_head);
> +	sch->bstats.packets--;
> +	sch->q.qlen--;

Same problem here. Returning NET_XMIT_CN will fix this case.

> +	sch->qstats.drops++;
> +	kfree_skb(skb_head);
> +
> +	return qdisc_enqueue_tail(skb, sch);
> +}
> +
> +
>  static int fifo_init(struct Qdisc *sch, struct nlattr *opt)
>  {
>  	struct fifo_sched_data *q = qdisc_priv(sch);
> @@ -50,7 +94,8 @@ static int fifo_init(struct Qdisc *sch, struct nlattr *opt)
>  	if (opt == NULL) {
>  		u32 limit = qdisc_dev(sch)->tx_queue_len ? : 1;
>  
> -		if (sch->ops == &bfifo_qdisc_ops)
> +		if ((sch->ops == &bfifo_qdisc_ops) ||
> +			(sch->ops == &bfifo_head_drop_qdisc_ops))

No need for the extra parentheses, also please align the beginning
of both lines.

>  			limit *= psched_mtu(qdisc_dev(sch));
>  
>  		q->limit = limit;
> @@ -108,6 +153,37 @@ struct Qdisc_ops bfifo_qdisc_ops __read_mostly = {
>  };
>  EXPORT_SYMBOL(bfifo_qdisc_ops);
>  
> +struct Qdisc_ops pfifo_head_drop_qdisc_ops __read_mostly = {
> +	.id		=	"pfifo_head_drop",
> +	.priv_size	=	sizeof(struct fifo_sched_data),
> +	.enqueue	=	pfifo_front_enqueue,
> +	.dequeue	=	qdisc_dequeue_head,
> +	.peek		=	qdisc_peek_head,
> +	.drop		=	qdisc_queue_drop,
> +	.init		=	fifo_init,
> +	.reset		=	qdisc_reset_queue,
> +	.change		=	fifo_init,
> +	.dump		=	fifo_dump,
> +	.owner		=	THIS_MODULE,
> +};
> +EXPORT_SYMBOL(pfifo_head_drop_qdisc_ops);
> +
> +struct Qdisc_ops bfifo_head_drop_qdisc_ops __read_mostly = {
> +	.id		=	"bfifo_head_drop",
> +	.priv_size	=	sizeof(struct fifo_sched_data),
> +	.enqueue	=	bfifo_front_enqueue,
> +	.dequeue	=	qdisc_dequeue_head,
> +	.peek		=	qdisc_peek_head,
> +	.drop		=	qdisc_queue_drop,
> +	.init		=	fifo_init,
> +	.reset		=	qdisc_reset_queue,
> +	.change		=	fifo_init,
> +	.dump		=	fifo_dump,
> +	.owner		=	THIS_MODULE,
> +};
> +EXPORT_SYMBOL(bfifo_head_drop_qdisc_ops);
> +
> +
>  /* Pass size change message down to embedded FIFO */
>  int fifo_set_limit(struct Qdisc *q, unsigned int limit)
>  {

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html