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

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

[Hagen Paul Pfeifer]

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(-)

diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h
index 2d56726..42dc85a 100644
--- a/include/net/pkt_sched.h
+++ b/include/net/pkt_sched.h
@@ -71,6 +71,8 @@ extern void qdisc_watchdog_cancel(struct qdisc_watchdog *wd);
 
 extern struct Qdisc_ops pfifo_qdisc_ops;
 extern struct Qdisc_ops bfifo_qdisc_ops;
+extern struct Qdisc_ops pfifo_head_drop_qdisc_ops;
+extern struct Qdisc_ops bfifo_head_drop_qdisc_ops;
 
 extern int fifo_set_limit(struct Qdisc *q, unsigned int limit);
 extern struct Qdisc *fifo_create_dflt(struct Qdisc *sch, struct Qdisc_ops *ops,
diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 75fd1c6..6eaa35d 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -1707,6 +1707,8 @@ static int __init pktsched_init(void)
 {
 	register_qdisc(&pfifo_qdisc_ops);
 	register_qdisc(&bfifo_qdisc_ops);
+	register_qdisc(&pfifo_head_drop_qdisc_ops);
+	register_qdisc(&bfifo_head_drop_qdisc_ops);
 	register_qdisc(&mq_qdisc_ops);
 	proc_net_fops_create(&init_net, "psched", 0, &psched_fops);
 
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--;
+		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--;
+	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))
 			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)
 {
-- 
1.6.5

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

[Patrick McHardy]

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)
>  {

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

[Hagen Paul Pfeifer]

This add an additional queuing strategy, called pfifo_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    |   37 +++++++++++++++++++++++++++++++++++++
 3 files changed, 41 insertions(+), 0 deletions(-)

diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h
index 2d56726..42dc85a 100644
--- a/include/net/pkt_sched.h
+++ b/include/net/pkt_sched.h
@@ -71,6 +71,8 @@ extern void qdisc_watchdog_cancel(struct qdisc_watchdog *wd);
 
 extern struct Qdisc_ops pfifo_qdisc_ops;
 extern struct Qdisc_ops bfifo_qdisc_ops;
+extern struct Qdisc_ops pfifo_head_drop_qdisc_ops;
+extern struct Qdisc_ops bfifo_head_drop_qdisc_ops;
 
 extern int fifo_set_limit(struct Qdisc *q, unsigned int limit);
 extern struct Qdisc *fifo_create_dflt(struct Qdisc *sch, struct Qdisc_ops *ops,
diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 75fd1c6..6eaa35d 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -1707,6 +1707,8 @@ static int __init pktsched_init(void)
 {
 	register_qdisc(&pfifo_qdisc_ops);
 	register_qdisc(&bfifo_qdisc_ops);
+	register_qdisc(&pfifo_head_drop_qdisc_ops);
+	register_qdisc(&bfifo_head_drop_qdisc_ops);
 	register_qdisc(&mq_qdisc_ops);
 	proc_net_fops_create(&init_net, "psched", 0, &psched_fops);
 
diff --git a/net/sched/sch_fifo.c b/net/sched/sch_fifo.c
index 69188e8..44f80ca 100644
--- a/net/sched/sch_fifo.c
+++ b/net/sched/sch_fifo.c
@@ -43,6 +43,28 @@ static int pfifo_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 	return qdisc_reshape_fail(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--;
+	sch->qstats.drops++;
+	kfree_skb(skb_head);
+
+	qdisc_enqueue_tail(skb, sch);
+
+	return NET_XMIT_CN;
+}
+
+
 static int fifo_init(struct Qdisc *sch, struct nlattr *opt)
 {
 	struct fifo_sched_data *q = qdisc_priv(sch);
@@ -108,6 +130,21 @@ 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);
+
 /* Pass size change message down to embedded FIFO */
 int fifo_set_limit(struct Qdisc *q, unsigned int limit)
 {
-- 
1.6.6.196.g1f735.dirty

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

[Hagen Paul Pfeifer]

Drop this patch - I forgot to git add include/net/pkt_sched.h and
net/sched/sch_api.c

HGN

-- 
Hagen Paul Pfeifer <hagen@jauu.net>  ||  http://jauu.net/
Telephone: +49 174 5455209           ||  Key Id: 0x98350C22
Key Fingerprint: 490F 557B 6C48 6D7E 5706 2EA2 4A22 8D45 9835 0C22
Always in motion, the future is. 

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

[Hagen Paul Pfeifer]

This add an additional queuing strategy, called pfifo_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 |    1 +
 net/sched/sch_api.c     |    1 +
 net/sched/sch_fifo.c    |   37 +++++++++++++++++++++++++++++++++++++
 3 files changed, 39 insertions(+), 0 deletions(-)

diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h
index 2d56726..b6cdc33 100644
--- a/include/net/pkt_sched.h
+++ b/include/net/pkt_sched.h
@@ -71,6 +71,7 @@ extern void qdisc_watchdog_cancel(struct qdisc_watchdog *wd);
 
 extern struct Qdisc_ops pfifo_qdisc_ops;
 extern struct Qdisc_ops bfifo_qdisc_ops;
+extern struct Qdisc_ops pfifo_head_drop_qdisc_ops;
 
 extern int fifo_set_limit(struct Qdisc *q, unsigned int limit);
 extern struct Qdisc *fifo_create_dflt(struct Qdisc *sch, struct Qdisc_ops *ops,
diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 75fd1c6..6cd4910 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -1707,6 +1707,7 @@ static int __init pktsched_init(void)
 {
 	register_qdisc(&pfifo_qdisc_ops);
 	register_qdisc(&bfifo_qdisc_ops);
+	register_qdisc(&pfifo_head_drop_qdisc_ops);
 	register_qdisc(&mq_qdisc_ops);
 	proc_net_fops_create(&init_net, "psched", 0, &psched_fops);
 
diff --git a/net/sched/sch_fifo.c b/net/sched/sch_fifo.c
index 69188e8..44f80ca 100644
--- a/net/sched/sch_fifo.c
+++ b/net/sched/sch_fifo.c
@@ -43,6 +43,28 @@ static int pfifo_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 	return qdisc_reshape_fail(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--;
+	sch->qstats.drops++;
+	kfree_skb(skb_head);
+
+	qdisc_enqueue_tail(skb, sch);
+
+	return NET_XMIT_CN;
+}
+
+
 static int fifo_init(struct Qdisc *sch, struct nlattr *opt)
 {
 	struct fifo_sched_data *q = qdisc_priv(sch);
@@ -108,6 +130,21 @@ 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);
+
 /* Pass size change message down to embedded FIFO */
 int fifo_set_limit(struct Qdisc *q, unsigned int limit)
 {
-- 
1.6.6.196.g1f735.dirty

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

[Patrick McHardy]

Hagen Paul Pfeifer wrote:
> This add an additional queuing strategy, called pfifo_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>

This looks better than the last one :)

A last comment below, than you can add my

Acked-by: Patrick McHardy <kaber@trash.net>

> +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);

The EXPORT_SYMBOL shouldn't be needed as sch_fifo can only be
linked statically and no other modules are using this as default.

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

[Hagen Paul Pfeifer]

This add an additional queuing strategy, called pfifo_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>
Acked-by: Patrick McHardy <kaber@trash.net>
Signed-off-by: Hagen Paul Pfeifer <hagen@jauu.net>
---
 include/net/pkt_sched.h |    1 +
 net/sched/sch_api.c     |    1 +
 net/sched/sch_fifo.c    |   36 ++++++++++++++++++++++++++++++++++++
 3 files changed, 38 insertions(+), 0 deletions(-)

diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h
index 2d56726..b6cdc33 100644
--- a/include/net/pkt_sched.h
+++ b/include/net/pkt_sched.h
@@ -71,6 +71,7 @@ extern void qdisc_watchdog_cancel(struct qdisc_watchdog *wd);
 
 extern struct Qdisc_ops pfifo_qdisc_ops;
 extern struct Qdisc_ops bfifo_qdisc_ops;
+extern struct Qdisc_ops pfifo_head_drop_qdisc_ops;
 
 extern int fifo_set_limit(struct Qdisc *q, unsigned int limit);
 extern struct Qdisc *fifo_create_dflt(struct Qdisc *sch, struct Qdisc_ops *ops,
diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 75fd1c6..6cd4910 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -1707,6 +1707,7 @@ static int __init pktsched_init(void)
 {
 	register_qdisc(&pfifo_qdisc_ops);
 	register_qdisc(&bfifo_qdisc_ops);
+	register_qdisc(&pfifo_head_drop_qdisc_ops);
 	register_qdisc(&mq_qdisc_ops);
 	proc_net_fops_create(&init_net, "psched", 0, &psched_fops);
 
diff --git a/net/sched/sch_fifo.c b/net/sched/sch_fifo.c
index 69188e8..b719272 100644
--- a/net/sched/sch_fifo.c
+++ b/net/sched/sch_fifo.c
@@ -43,6 +43,28 @@ static int pfifo_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 	return qdisc_reshape_fail(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--;
+	sch->qstats.drops++;
+	kfree_skb(skb_head);
+
+	qdisc_enqueue_tail(skb, sch);
+
+	return NET_XMIT_CN;
+}
+
+
 static int fifo_init(struct Qdisc *sch, struct nlattr *opt)
 {
 	struct fifo_sched_data *q = qdisc_priv(sch);
@@ -108,6 +130,20 @@ 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,
+};
+
 /* Pass size change message down to embedded FIFO */
 int fifo_set_limit(struct Qdisc *q, unsigned int limit)
 {
-- 
1.6.6.196.g1f735.dirty

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

[Jarek Poplawski]

Hagen Paul Pfeifer wrote, On 01/18/2010 05:44 PM:

> This add an additional queuing strategy, called pfifo_head_drop,

"This adds"...

> 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

"skb in congested situations"...

> where newer packets reflects the superior information.

"where newer packets reflect"...

> 
> Reviewed-by: Florian Westphal <fw@strlen.de>
> Acked-by: Patrick McHardy <kaber@trash.net>
> Signed-off-by: Hagen Paul Pfeifer <hagen@jauu.net>
> ---
>  include/net/pkt_sched.h |    1 +
>  net/sched/sch_api.c     |    1 +
>  net/sched/sch_fifo.c    |   36 ++++++++++++++++++++++++++++++++++++
>  3 files changed, 38 insertions(+), 0 deletions(-)

...

> +static int pfifo_front_enqueue(struct sk_buff *skb, struct Qdisc* sch)

Why do you call it "front_enqueue" if always does "enqueue_tail"?
Btw, usually these methods take name from the qdisc.

> +{
> +	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--;

I don't think this is needed; qdisc_dequeue_head() updated it already.

> +	sch->qstats.drops++;
> +	kfree_skb(skb_head);
> +
> +	qdisc_enqueue_tail(skb, sch);
> +
> +	return NET_XMIT_CN;
> +}
> +
> +
>  static int fifo_init(struct Qdisc *sch, struct nlattr *opt)
>  {
>  	struct fifo_sched_data *q = qdisc_priv(sch);
> @@ -108,6 +130,20 @@ 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,

Probably it isn't used much, but it seems for consistency this drop
should be implemented as a head drop.

Jarek P.

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

[Hagen Paul Pfeifer]

* Jarek Poplawski | 2010-01-18 20:25:17 [+0100]:

>I don't think this is needed; qdisc_dequeue_head() updated it already.

No, the bookkeeping stuff is done in the previous call layer. It is not really
nice solved but to generalize this stuff adds unnecessary overhead.

>> +	.drop		=	qdisc_queue_drop,
>
>Probably it isn't used much, but it seems for consistency this drop
>should be implemented as a head drop.

Sounds coherent, Patrick should I brew a new patch?

HGN

PS: Jarek thank you for your notes, I will incorporate these!

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

[Jarek Poplawski]

On Mon, Jan 18, 2010 at 08:36:45PM +0100, Hagen Paul Pfeifer wrote:
> * Jarek Poplawski | 2010-01-18 20:25:17 [+0100]:
> 
> >I don't think this is needed; qdisc_dequeue_head() updated it already.
> 
> No, the bookkeeping stuff is done in the previous call layer. It is not really
> nice solved but to generalize this stuff adds unnecessary overhead.

Did you test it? IMHO "sch->q.qlen--" is done 2 times.

Jarek P.

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

[Hagen Paul Pfeifer]

* Jarek Poplawski | 2010-01-18 20:51:00 [+0100]:

>Did you test it? IMHO "sch->q.qlen--" is done 2 times.

The test setup was a little but cumbersome, but yes. But you are right, good
catch: qlen-- via __skb_unlink(). Thank you!

HGN

-- 
Hagen Paul Pfeifer <hagen@jauu.net>  ||  http://jauu.net/
Telephone: +49 174 5455209           ||  Key Id: 0x98350C22
Key Fingerprint: 490F 557B 6C48 6D7E 5706 2EA2 4A22 8D45 9835 0C22

[PATCH V2] sched: add head drop fifo queue

[Hagen Paul Pfeifer]

This adds an additional queuing strategy, called pfifo_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 congested situations is useful for sensor network environments
where newer packets reflect the superior information.

Reviewed-by: Florian Westphal <fw@strlen.de>
Acked-by: Patrick McHardy <kaber@trash.net>
Signed-off-by: Hagen Paul Pfeifer <hagen@jauu.net>
---

This patch additionaly add the function qdisc_queue_drop_head() to be
consistent with drop. Additionally some suggestions from Jarek.

 include/net/pkt_sched.h   |    1 +
 include/net/sch_generic.h |   19 +++++++++++++++++++
 net/sched/sch_api.c       |    1 +
 net/sched/sch_fifo.c      |   34 ++++++++++++++++++++++++++++++++++
 4 files changed, 55 insertions(+), 0 deletions(-)

diff --git a/include/net/pkt_sched.h b/include/net/pkt_sched.h
index 2d56726..b6cdc33 100644
--- a/include/net/pkt_sched.h
+++ b/include/net/pkt_sched.h
@@ -71,6 +71,7 @@ extern void qdisc_watchdog_cancel(struct qdisc_watchdog *wd);
 
 extern struct Qdisc_ops pfifo_qdisc_ops;
 extern struct Qdisc_ops bfifo_qdisc_ops;
+extern struct Qdisc_ops pfifo_head_drop_qdisc_ops;
 
 extern int fifo_set_limit(struct Qdisc *q, unsigned int limit);
 extern struct Qdisc *fifo_create_dflt(struct Qdisc *sch, struct Qdisc_ops *ops,
diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
index dad558b..67dc08e 100644
--- a/include/net/sch_generic.h
+++ b/include/net/sch_generic.h
@@ -427,6 +427,25 @@ static inline struct sk_buff *qdisc_dequeue_head(struct Qdisc *sch)
 	return __qdisc_dequeue_head(sch, &sch->q);
 }
 
+static inline unsigned int __qdisc_queue_drop_head(struct Qdisc *sch,
+					      struct sk_buff_head *list)
+{
+	struct sk_buff *skb = __qdisc_dequeue_head(sch, list);
+
+	if (likely(skb != NULL)) {
+		unsigned int len = qdisc_pkt_len(skb);
+		kfree_skb(skb);
+		return len;
+	}
+
+	return 0;
+}
+
+static inline unsigned int qdisc_queue_drop_head(struct Qdisc *sch)
+{
+	return __qdisc_queue_drop_head(sch, &sch->q);
+}
+
 static inline struct sk_buff *__qdisc_dequeue_tail(struct Qdisc *sch,
 						   struct sk_buff_head *list)
 {
diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 75fd1c6..6cd4910 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -1707,6 +1707,7 @@ static int __init pktsched_init(void)
 {
 	register_qdisc(&pfifo_qdisc_ops);
 	register_qdisc(&bfifo_qdisc_ops);
+	register_qdisc(&pfifo_head_drop_qdisc_ops);
 	register_qdisc(&mq_qdisc_ops);
 	proc_net_fops_create(&init_net, "psched", 0, &psched_fops);
 
diff --git a/net/sched/sch_fifo.c b/net/sched/sch_fifo.c
index 69188e8..4b0a6cc 100644
--- a/net/sched/sch_fifo.c
+++ b/net/sched/sch_fifo.c
@@ -43,6 +43,26 @@ static int pfifo_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 	return qdisc_reshape_fail(skb, sch);
 }
 
+static int pfifo_tail_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->qstats.drops++;
+	kfree_skb(skb_head);
+
+	qdisc_enqueue_tail(skb, sch);
+
+	return NET_XMIT_CN;
+}
+
 static int fifo_init(struct Qdisc *sch, struct nlattr *opt)
 {
 	struct fifo_sched_data *q = qdisc_priv(sch);
@@ -108,6 +128,20 @@ 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_tail_enqueue,
+	.dequeue	=	qdisc_dequeue_head,
+	.peek		=	qdisc_peek_head,
+	.drop		=	qdisc_queue_drop_head,
+	.init		=	fifo_init,
+	.reset		=	qdisc_reset_queue,
+	.change		=	fifo_init,
+	.dump		=	fifo_dump,
+	.owner		=	THIS_MODULE,
+};
+
 /* Pass size change message down to embedded FIFO */
 int fifo_set_limit(struct Qdisc *q, unsigned int limit)
 {
-- 
1.6.6.196.g1f735.dirty