CHOKe flow scheduler (0.7)

This implements the CHOKe packet scheduler based on the existing Linux RED scheduler based on the algorithm described in the paper.

The core idea is:
For every packet arrival:
Calculate Qave
if (Qave < minth)
Queue the new packet
else
Select randomly a packet from the queue if (both packets from same flow)
then Drop both the packets
else if (Qave > maxth)
Drop packet
else
Admit packet with proability p (same as RED)

See also:
Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
queue management scheme for approximating fair bandwidth allocation",
Proceeding of INFOCOM'2000, March 2000.

Signed-off-by Stephen Hemminger <[email protected]>

---
Patch versions
0.3 (Eric) uses table for queue.
0.4 allows classification with TC filters
fixes crash when peek_random() finds a hole
0.5 (Eric) that fixes qlen with holes and peek 0.7 change to use separate params / stats than RED
account for drops in backlog

Almost ready, still need to make sure API (netlink) is right

 net/sched/Kconfig     |   11 +
 net/sched/Makefile    |    1 
 net/sched/sch_choke.c |  536 ++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 548 insertions(+)

net/sched/Kconfig +11 -0

@@ -205,6 +205,17 @@ config NET_SCH_DRR
 
 	  If unsure, say N.
 
+config NET_SCH_CHOKE
+	tristate "CHOose and Keep responsive flow scheduler (CHOKE)"
+	help
+	  Say Y here if you want to use the CHOKe packet scheduler (CHOose
+	  and Keep for responsive flows, CHOose and Kill for unresponsive
+	  flows). This is a variation of RED which trys to penalize flows
+	  that monopolize the queue.
+
+	  To compile this code as a module, choose M here: the
+	  module will be called sch_choke.
+
 config NET_SCH_INGRESS
 	tristate "Ingress Qdisc"
 	depends on NET_CLS_ACT

net/sched/Makefile +1 -0

@@ -32,6 +32,7 @@ obj-$(CONFIG_NET_SCH_MULTIQ)	+= sch_mult
 obj-$(CONFIG_NET_SCH_ATM)	+= sch_atm.o
 obj-$(CONFIG_NET_SCH_NETEM)	+= sch_netem.o
 obj-$(CONFIG_NET_SCH_DRR)	+= sch_drr.o
+obj-$(CONFIG_NET_SCH_CHOKE)	+= sch_choke.o
 obj-$(CONFIG_NET_CLS_U32)	+= cls_u32.o
 obj-$(CONFIG_NET_CLS_ROUTE4)	+= cls_route.o
 obj-$(CONFIG_NET_CLS_FW)	+= cls_fw.o

net/sched/sch_choke.c new file +215 -0

@@ -0,0 +1,556 @@
+/*
+ * net/sched/sch_choke.c	CHOKE scheduler
+ *
+ * Copyright (c) 2011 Stephen Hemminger <[email protected]>
+ * Copyright (c) 2011 Eric Dumazet <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * version 2 as published by the Free Software Foundation.
+ *
+ */
+
+#include <linux/module.h>
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/skbuff.h>
+#include <linux/reciprocal_div.h>
+#include <net/pkt_sched.h>
+#include <net/inet_ecn.h>
+#include <net/red.h>
+
+/*	CHOKe stateless AQM for fair bandwidth allocation
+        =================================================
+
+   CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for
+   unresponsive flows) is a variant of RED that penalizes misbehaving flows but
+   maintains no flow state. The difference from RED is an additional step
+   during the enqueuing process. If average queue size is over the
+   low threshold (qmin), a packet is chosen at random from the queue.
+   If both the new and chosen packet are from the same flow, both
+   are dropped. Unlike RED, CHOKe is not really a "classful" qdisc because it
+   needs to access packets in queue randomly. It has a minimal class
+   interface to allow overriding the builtin flow classifier with
+   filters.
+
+   Source:
+   R. Pan, B. Prabhakar, and K. Psounis, "CHOKe, A Stateless
+   Active Queue Management Scheme for Approximating Fair Bandwidth Allocation",
+   IEEE INFOCOM, 2000.
+
+   A. Tang, J. Wang, S. Low, "Understanding CHOKe: Throughput and Spatial
+   Characteristics", IEEE/ACM Transactions on Networking, 2004
+
+ */
+
+/* Upper bound on size of sk_buff table */
+#define CHOKE_MAX_QUEUE	(128*1024 - 1)
+
+struct choke_sched_data {
+/* Parameters */
+	u32		 limit;
+	unsigned char	 flags;
+
+	struct red_parms parms;
+
+/* Variables */
+	struct tcf_proto *filter_list;
+	struct {
+		u32	prob_drop;	/* Early probability drops */
+		u32	prob_mark;	/* Early probability marks */
+		u32	forced_drop;	/* Forced drops, qavg > max_thresh */
+		u32	forced_mark;	/* Forced marks, qavg > max_thresh */
+		u32	pdrop;          /* Drops due to queue limits */
+		u32	other;          /* Drops due to drop() calls */
+		u32	matched;	/* Drops to flow match */
+	} stats;
+
+	unsigned int	 head;
+	unsigned int	 tail;
+	unsigned int	 holes;
+	unsigned int	 tab_mask; /* size - 1 */
+
+	struct sk_buff **tab;
+};
+
+static inline unsigned int choke_len(const struct choke_sched_data *q)
+{
+	return (q->tail - q->head) & q->tab_mask;
+}
+
+/* deliver a random number between 0 and N - 1 */
+static inline u32 random_N(unsigned int N)
+{
+	return reciprocal_divide(random32(), N);
+}
+
+/* Select a packet at random from the queue in O(1) and handle holes */
+static struct sk_buff *choke_peek_random(struct choke_sched_data *q,
+					 unsigned int *pidx)
+{
+	struct sk_buff *skb;
+	int retrys = 3;
+
+	do {
+		*pidx = (q->head + random_N(choke_len(q))) & q->tab_mask;
+		skb = q->tab[*pidx];
+		if (skb)
+			return skb;
+	} while (--retrys > 0);
+
+	/* queue is has lots of holes use the head which is known to exist */
+	return q->tab[*pidx = q->head];
+}
+
+/* Is ECN parameter configured */
+static inline int use_ecn(const struct choke_sched_data *q)
+{
+	return q->flags & TC_RED_ECN;
+}
+
+/* Should packets over max just be dropped (versus marked) */
+static inline int use_harddrop(const struct choke_sched_data *q)
+{
+	return q->flags & TC_RED_HARDDROP;
+}
+
+/* Move head pointer forward to skip over holes */
+static void choke_zap_head_holes(struct choke_sched_data *q)
+{
+	while (q->holes && q->tab[q->head] == NULL) {
+		q->head = (q->head + 1) & q->tab_mask;
+		q->holes--;
+	}
+}
+
+/* Move tail pointer backwards to reuse holes */
+static void choke_zap_tail_holes(struct choke_sched_data *q)
+{
+	while (q->holes && q->tab[q->tail - 1] == NULL) {
+		q->tail = (q->tail - 1) & q->tab_mask;
+		q->holes--;
+	}
+}
+
+/* Drop packet from queue array by creating a "hole" */
+static void choke_drop_by_idx(struct choke_sched_data *q, unsigned int idx)
+{
+	q->tab[idx] = NULL;
+	q->holes++;
+
+	if (idx == q->head)
+		choke_zap_head_holes(q);
+	if (idx == q->tail)
+		choke_zap_tail_holes(q);
+}
+
+/* Classify flow using either:
+   1. pre-existing classification result in skb
+   2. fast internal classification
+   3. use TC filter based classification
+*/
+static inline unsigned int choke_classify(struct sk_buff *skb,
+					  struct Qdisc *sch, int *qerr)
+
+{
+	struct choke_sched_data *q = qdisc_priv(sch);
+	struct tcf_result res;
+	int result;
+
+	*qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
+
+	if (TC_H_MAJ(skb->priority) == sch->handle &&
+	    TC_H_MIN(skb->priority) > 0)
+		return TC_H_MIN(skb->priority);
+
+	if (!q->filter_list)
+		return skb_get_rxhash(skb);
+
+	result = tc_classify(skb, q->filter_list, &res);
+	if (result >= 0) {
+#ifdef CONFIG_NET_CLS_ACT
+		switch (result) {
+		case TC_ACT_STOLEN:
+		case TC_ACT_QUEUED:
+			*qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
+		case TC_ACT_SHOT:
+			return 0;
+		}
+#endif
+		return TC_H_MIN(res.classid);
+	}
+
+	return 0;
+}
+
+static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
+	struct choke_sched_data *q = qdisc_priv(sch);
+	struct red_parms *p = &q->parms;
+	unsigned int hash;
+	int uninitialized_var(ret);
+
+	hash = choke_classify(skb, sch, &ret);
+	if (!hash) {
+		/* Packet was eaten by filter */
+		if (ret & __NET_XMIT_BYPASS)
+			sch->qstats.drops++;
+		kfree_skb(skb);
+		return ret;
+	}
+
+	/* Maybe add hash as field in struct qdisc_skb_cb? */
+	*(unsigned int *)(qdisc_skb_cb(skb)->data) = hash;
+
+	/* Compute average queue usage (see RED) */
+	p->qavg = red_calc_qavg(p, choke_len(q) - q->holes);
+	if (red_is_idling(p))
+		red_end_of_idle_period(p);
+
+	/* Is queue small? */
+	if (p->qavg <= p->qth_min)
+		p->qcount = -1;
+	else {
+		struct sk_buff *oskb;
+		unsigned int idx;

net/sched/sch_choke.c new file +31 -0

+			goto congestion_drop;
+		}
+
+		/* Queue is large, always mark/drop */
+		if (p->qavg > p->qth_max) {
+			p->qcount = -1;
+
+			sch->qstats.overlimits++;
+			if (use_harddrop(q) || !use_ecn(q) ||
+			    !INET_ECN_set_ce(skb)) {
+				q->stats.forced_drop++;
+				goto congestion_drop;
+			}
+
+			q->stats.forced_mark++;
+		} else if (++p->qcount) {
+			if (red_mark_probability(p, p->qavg)) {
+				p->qcount = 0;
+				p->qR = red_random(p);
+
+				sch->qstats.overlimits++;
+				if (!use_ecn(q) || !INET_ECN_set_ce(skb)) {
+					q->stats.prob_drop++;
+					goto congestion_drop;
+				}
+
+				q->stats.prob_mark++;
+			}
+		} else
+			p->qR = red_random(p);
+	}

net/sched/sch_choke.c new file +19 -0

+		return NET_XMIT_SUCCESS;
+	}
+
+	q->stats.pdrop++;
+	sch->qstats.drops++;
+	kfree_skb(skb);
+	return NET_XMIT_DROP;
+
+ congestion_drop:
+	qdisc_drop(skb, sch);
+	return NET_XMIT_CN;
+}
+
+static struct sk_buff *choke_dequeue(struct Qdisc *sch)
+{
+	struct choke_sched_data *q = qdisc_priv(sch);
+	struct sk_buff *skb;
+
+	if (q->head == q->tail) {

net/sched/sch_choke.c new file +20 -0

+
+	return skb;
+}
+
+static unsigned int choke_drop(struct Qdisc *sch)
+{
+	struct choke_sched_data *q = qdisc_priv(sch);
+	unsigned int len;
+
+	len = qdisc_queue_drop(sch);
+	if (len > 0)
+		q->stats.other++;
+	else {
+		if (!red_is_idling(&q->parms))
+			red_start_of_idle_period(&q->parms);
+	}
+
+	return len;
+}
+

Quoted 4 lines · Stephen Hemminger

This implements the CHOKe packet scheduler based on the existing Linux RED scheduler based on the algorithm described in the paper.

CHOKe ("CHOose and Kill" or "CHOose and Keep") is an alternative packet scheduler based on the Random Exponential Drop (RED) algorithm.

The core idea is:
For every packet arrival:
Calculate Qave
if (Qave < minth)
Queue the new packet
else
Select randomly a packet from the queue if (both packets from same flow)
then Drop both the packets
else if (Qave > maxth)
Drop packet
else
Admit packet with probability P (same as RED)

See also:
Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
queue management scheme for approximating fair bandwidth allocation",
Proceeding of INFOCOM'2000, March 2000.

Signed-off-by Stephen Hemminger <[email protected]>

---
0.8 change queue length and holes account.

    keep sch->q.qlen updated, and holes counter not needed.

---
 net/sched/Kconfig     |   11 +
 net/sched/Makefile    |    1 
 net/sched/sch_choke.c |  536 ++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 548 insertions(+)

Quoted 26 lines · Stephen Hemminger

CHOKe ("CHOose and Kill" or "CHOose and Keep") is an alternative packet scheduler based on the Random Exponential Drop (RED) algorithm.

The core idea is:
For every packet arrival:
Calculate Qave
if (Qave < minth)
Queue the new packet
else
Select randomly a packet from the queue if (both packets from same flow)
then Drop both the packets
else if (Qave > maxth)
Drop packet
else
Admit packet with probability P (same as RED)

See also:
Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
queue management scheme for approximating fair bandwidth allocation",
Proceeding of INFOCOM'2000, March 2000.

Signed-off-by Stephen Hemminger <[email protected]>

---
0.8 change queue length and holes account.

Quoted 8 lines

    keep sch->q.qlen updated, and holes counter not needed.

---
 net/sched/Kconfig     |   11 +
 net/sched/Makefile    |    1 
 net/sched/sch_choke.c |  536 ++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 548 insertions(+)

Hi Stephen

Your diffstat was an old one, here the right one.

 include/linux/pkt_sched.h |   29 +
 net/sched/Kconfig         |   11 
 net/sched/Makefile        |    1 
 net/sched/sch_choke.c     |  552 ++++++++++++++++++++++++++++++++++++

I tested v8 and found several serious problems, please find a diff of my latest changes :

- wrong oskb/skb used in choke_enqueue()
- choke_zap_head_holes() is called from choke_dequeue() and crash if we dequeued last packet. (!!!)
- out of bound access in choke_zap_tail_holes()
- choke_dequeue() can be shorter
- choke_change() must dequeue/drop in excess packets or risk new array overfill (if we reduce queue limit by tc qdisc change ...)
- inline is not needed, space errors in include file

Thanks !

Hmm, please wait a bit, I had another crash when I stopped my bench/stress

Quoted 2 lines · Eric Dumazet

Hmm, please wait a bit, I had another crash when I stopped my bench/stress

I am not sure p->qavg is correctly computed.

Crash happened because choke_peek_random() was called while no packet was in queue.

With my params (min=10833 max=32500 burst=18055 limit=130000) this implies qavg was very big while qlen==0 !

qdisc choke 11: dev ifb0 parent 1:11 limit 130000b min 10833b max 32500b ewma 13 Plog 21 Scell_log 30
Sent 200857857 bytes 365183 pkt (dropped 1010937, overlimits 557577 requeues 0)
rate 32253Kbit 7330pps backlog 17875996b 32505p requeues 0
marked 0 early 557577 pdrop 0 other 0 matched 226680

net/sched/sch_choke.c new file +10 -0

+static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
...
+	/* Is queue small? */
+	if (p->qavg <= p->qth_min)
+		p->qcount = -1;
+	else {
+		struct sk_buff *oskb;
+		unsigned int idx;
+
+		/* Draw a packet at random from queue */

net/sched/sch_choke.c new file +3 -0

+			goto congestion_drop;
+		}
+

Quoted 17 lines · Stephen Hemminger

net/sched/sch_choke.c new file +16 -0

+static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
...
+	/* Is queue small? */
+	if (p->qavg <= p->qth_min)
+		p->qcount = -1;
+	else {
+		struct sk_buff *oskb;
+		unsigned int idx;
+
+		/* Draw a packet at random from queue */
+		oskb = choke_peek_random(sch, &idx);
+
+		/* Both packets from same flow ? */
+		if (*(unsigned int *)(qdisc_skb_cb(oskb)->data) == hash) {
+			/* Drop both packets */
+			q->stats.matched++;

net/sched/sch_choke.c line 223

Quoted 4 lines

net/sched/sch_choke.c new file +4 -0

+			choke_drop_by_idx(q, idx);
+			sch->qstats.backlog -= qdisc_pkt_len(skb);
+			--sch->q.qlen;
+			qdisc_drop(oskb, sch);

You need to adjust the qlen values of parent qdiscs by calling qdisc_tree_decrease_qlen(), they are not aware that a second packet has been dropped.

Quoted 18 lines · Patrick McHardy

Quoted 17 lines · Stephen Hemminger

(quoted diff) +16 -0

+static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch)
+{
...
+	/* Is queue small? */
+	if (p->qavg <= p->qth_min)
+		p->qcount = -1;
+	else {
+		struct sk_buff *oskb;
+		unsigned int idx;
+
+		/* Draw a packet at random from queue */
+		oskb = choke_peek_random(sch, &idx);
+
+		/* Both packets from same flow ? */
+		if (*(unsigned int *)(qdisc_skb_cb(oskb)->data) == hash) {
+			/* Drop both packets */
+			q->stats.matched++;

Quoted 8 lines

Review

Quoted 4 lines

(quoted diff) +4 -0

+			choke_drop_by_idx(q, idx);
+			sch->qstats.backlog -= qdisc_pkt_len(skb);
+			--sch->q.qlen;
+			qdisc_drop(oskb, sch);

You need to adjust the qlen values of parent qdiscs by calling qdisc_tree_decrease_qlen(), they are not aware that a second packet has been dropped.

I just saw that Eric already fixed this :)
--

CHOKe ("CHOose and Kill" or "CHOose and Keep") is an alternative packet scheduler based on the Random Exponential Drop (RED) algorithm.

The core idea is:
For every packet arrival:
Calculate Qave
if (Qave < minth)
Queue the new packet
else
Select randomly a packet from the queue if (both packets from same flow)
then Drop both the packets
else if (Qave > maxth)
Drop packet
else
Admit packet with proability p (same as RED)

See also:
Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
queue management scheme for approximating fair bandwidth allocation",
Proceeding of INFOCOM'2000, March 2000.

Help from:
Eric Dumazet <[email protected]>
Patrick McHardy <[email protected]>

Signed-off-by Stephen Hemminger <[email protected]>

---
This version is based on net-next, and assumes Eric's patch for corrected bstats is already applied.

0.9 incorporate patches from Patrick/Eric
rework the peek_random and drop code to simplify and fix bug where random_N needs to called with full length (including holes).

Quoted 28 lines · Stephen Hemminger

CHOKe ("CHOose and Kill" or "CHOose and Keep") is an alternative packet scheduler based on the Random Exponential Drop (RED) algorithm.

The core idea is:
For every packet arrival:
Calculate Qave
if (Qave < minth)
Queue the new packet
else
Select randomly a packet from the queue if (both packets from same flow)
then Drop both the packets
else if (Qave > maxth)
Drop packet
else
Admit packet with proability p (same as RED)

See also:
Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
queue management scheme for approximating fair bandwidth allocation",
Proceeding of INFOCOM'2000, March 2000.

Help from:
Eric Dumazet <[email protected]>
Patrick McHardy <[email protected]>

Signed-off-by Stephen Hemminger <[email protected]>

Quoted 7 lines

---
This version is based on net-next, and assumes Eric's patch for corrected bstats is already applied.

0.9 incorporate patches from Patrick/Eric
rework the peek_random and drop code to simplify and fix bug where random_N needs to called with full length (including holes).

Nice catch, I now have more "matched" counts after my test :

qdisc choke 11: parent 1:11 limit 130000b min 10833b max 32500b ewma 13 Plog 21 Scell_log 30
Sent 93944198 bytes 170889 pkt (dropped 829140, overlimits 436686 requeues 0) rate 48bit 0pps backlog 0b 0p requeues 0
marked 0 early 436686 pdrop 0 other 0 matched 196227

You missed the qdisc_bstats_update() move from enqueue() to dequeue()

And some minor CodingStyle / checkpatch.pl changes, here is my latest diff on top of 0.9

I believe you can release v1 :)

Thanks !

I rolled in your changes. But there is one more change I want to make. The existing flow match based on hash is vulnerable to side-channel DoS attack. It is possible for a hostile flow to send packets that match the same hash value which would effectively kill a targeted flow.

The solution is to match based on full source and destination, not hash value. Still coding that up.

Quoted 5 lines · Stephen Hemminger

I rolled in your changes. But there is one more change I want to make. The existing flow match based on hash is vulnerable to side-channel DoS attack. It is possible for a hostile flow to send packets that match the same hash value which would effectively kill a targeted flow.

Quoted 2 lines

The solution is to match based on full source and destination, not hash value. Still coding that up.

I see, but you only want to make this full test if (!q->filter_list) ?

(or precisely only if skb_get_rxhash() was used to get the cookie )

net/sched/sch_choke.c new file +10 -0

+static bool choke_match_flow(struct sk_buff *skb1, struct sk_buff *skb2)
+{
+	int off1, off2, poff;
+	u8 ip_proto;
+	u32 ihl;
+
+	if (skb1->protocol != skb2->protocol)
+		return false;
+
+	off1 = skb_network_offset(skb1);

net/sched/sch_choke.c new file +16 -0

+		ip2 = (struct ipv6hdr *) (skb2->data + off2);
+
+		if (ip1->nexthdr != ip2->nexthdr ||
+		    ipv6_addr_cmp(&ip1->saddr, &ip2->saddr) != 0 ||
+		    ipv6_addr_cmp(&ip1->daddr, &ip2->daddr))
+			return false;
+
+		ihl = (40 >> 2);
+		ip_proto = ip1->nexthdr;
+		break;
+	}
+
+	default:
+		return false;
+	}
+

net/sched/sch_choke.c new file +91 -0

+/* Make sure network and transport headers can be dereferenced */
+static bool choke_linearize_header(struct sk_buff *skb)
+{
+	int nhoff, poff;
+	struct ipv6hdr *ip6;
+	struct iphdr *ip;
+	u8 ip_proto;
+	u32 ihl;
+
+	nhoff = skb_network_offset(skb);
+
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP):
+		if (!pskb_may_pull(skb, sizeof(*ip) + nhoff))
+			return false;
+
+		ip = (struct iphdr *) (skb->data + nhoff);
+		if (ip->frag_off & htons(IP_MF | IP_OFFSET))
+			return false;
+
+		ip_proto = ip->protocol;
+		ihl = ip->ihl;
+		break;
+	case __constant_htons(ETH_P_IPV6):
+		if (!pskb_may_pull(skb, sizeof(*ip6) + nhoff))
+			return false;
+
+		ip6 = (struct ipv6hdr *) (skb->data + nhoff);
+		ip_proto = ip6->nexthdr;
+		ihl = (40 >> 2);
+		break;
+	default:
+		return true;
+	}
+
+	poff = proto_ports_offset(ip_proto);
+	if (poff >= 0) {
+		nhoff += ihl * 4 + poff;
+		if (!pskb_may_pull(skb, nhoff + 4))
+			return false;
+	}
+
+	return true;
+}
+
 
 
+/*
+ * Compare flow of two packets
+ *  Returns true only if source and destination address and port match.
+ *          false for special cases
+ */
+static bool choke_match_flow(const struct sk_buff *skb1,
+			     const struct sk_buff *skb2)
+{
+	int off1, off2, poff;
+
+	if (skb1->protocol != skb2->protocol)
+		return false;
+
+	off1 = skb_network_offset(skb1);
+	off2 = skb_network_offset(skb2);
+
+	switch (skb1->protocol) {
+	case __constant_htons(ETH_P_IP): {
+		const struct iphdr *ip1, *ip2;
+
+		ip1 = (struct iphdr *) (skb1->data + off1);
+		ip2 = (struct iphdr *) (skb2->data + off2);
+
+		if (ip1->protocol != ip2->protocol ||
+		    ip1->saddr != ip2->saddr || ip1->daddr != ip2->daddr)
+			return false;
+
+		if (ip1->frag_off & htons(IP_MF | IP_OFFSET) ||
+		    ip2->frag_off & htons(IP_MF | IP_OFFSET))
+			return ip1->id == ip2->id;
+
+		poff = proto_ports_offset(ip1->protocol);
+		if (poff < 0)
+			return true;
+		else {
+			const u32 *ports1, *ports2;
+
+			ports1 = (__force u32 *) (skb1->data + off1
+						  + ip1->ihl * 4 + poff);
+			ports2 = (__force u32 *) (skb2->data + off2
+						  + ip2->ihl * 4 + poff);
+
+			return *ports1 == *ports2;
+		}
+		break;
+	}

Le jeudi 20 janvier 2011 à 09:38 -0800, Stephen Hemminger a écrit :

...

Hi Stephen

I am contemplating choke_linearize_header() (yet another hash function... oh well...) and say :

Instead of this boolean return, just use skb_get_rxhash(). It performs what you want, and return 32bits of information, instead of one bit.

(if result (rxhash) is zero, it means you can drop packet because it is not linearized)

So choke_match_flow() can be faster if rxhash differs (no cache miss on skb->data on an old skb)
(Do the full check only if rxhash is equal on skb1 / skb2)

More over, the skb_get_rxhash() call is _really_ needed only if CHOKe triggers :
if (p->qavg <= p->qth_min)
we dont have to compute rxhash at all.

If you want, I can send a diff on your v0.10, just tell me !

Subject: sched: CHOKe flow scheduler

CHOKe ("CHOose and Kill" or "CHOose and Keep") is an alternative packet scheduler based on the Random Exponential Drop (RED) algorithm.

The core idea is:
For every packet arrival:
Calculate Qave
if (Qave < minth)
Queue the new packet
else
Select randomly a packet from the queue if (both packets from same flow)
then Drop both the packets
else if (Qave > maxth)
Drop packet
else
Admit packet with proability p (same as RED)

See also:
Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
queue management scheme for approximating fair bandwidth allocation",
Proceeding of INFOCOM'2000, March 2000.

Help from:
Eric Dumazet <[email protected]>
Patrick McHardy <[email protected]>

Signed-off-by Stephen Hemminger <[email protected]>

---
0.11 - incorporates Eric's change to use rxhash

Quoted 28 lines

Subject: sched: CHOKe flow scheduler

CHOKe ("CHOose and Kill" or "CHOose and Keep") is an alternative packet scheduler based on the Random Exponential Drop (RED) algorithm.

The core idea is:
For every packet arrival:
Calculate Qave
if (Qave < minth)
Queue the new packet
else
Select randomly a packet from the queue if (both packets from same flow)
then Drop both the packets
else if (Qave > maxth)
Drop packet
else
Admit packet with proability p (same as RED)

See also:
Rong Pan, Balaji Prabhakar, Konstantinos Psounis, "CHOKe: a stateless active
queue management scheme for approximating fair bandwidth allocation",
Proceeding of INFOCOM'2000, March 2000.

Help from:
Eric Dumazet <[email protected]>
Patrick McHardy <[email protected]>

Quoted 6 lines

Signed-off-by Stephen Hemminger <[email protected]>

---
0.11 - incorporates Eric's change to use rxhash

Signed-off-by Eric Dumazet <[email protected]>