compat: backport FQ CoDel support down to 2.6.25
authorLuis R. Rodriguez <mcgrof@frijolero.org>
Fri, 25 May 2012 02:53:15 +0000 (19:53 -0700)
committerLuis R. Rodriguez <mcgrof@frijolero.org>
Fri, 25 May 2012 02:57:33 +0000 (19:57 -0700)
FQ CoDel is available as a module, sch_fq_codel.

This backports:

commit 4b549a2ef4bef9965d97cbd992ba67930cd3e0fe
Author: Eric Dumazet <edumazet@google.com>
Date:   Fri May 11 09:30:50 2012 +0000

    fq_codel: Fair Queue Codel AQM

    Fair Queue Codel packet scheduler

    Principles :

    - Packets are classified (internal classifier or external) on flows.
    - This is a Stochastic model (as we use a hash, several flows might
                                  be hashed on same slot)
    - Each flow has a CoDel managed queue.
    - Flows are linked onto two (Round Robin) lists,
      so that new flows have priority on old ones.

    - For a given flow, packets are not reordered (CoDel uses a FIFO)
    - head drops only.
    - ECN capability is on by default.
    - Very low memory footprint (64 bytes per flow)

I should note that this is different than CoDel. This code is GPL,
CoDel is Dual BSD/GPL licensed. This goes only compile tested against
all the below kernels, run time test results would be appreciated.

mcgrof@tux ~/compat (git::master)$ ckmake
Trying kernel                  3.4.0-030400rc1-generic  [OK]
Trying kernel                     3.3.7-030307-generic  [OK]
Trying kernel                     3.2.2-030202-generic  [OK]
Trying kernel                    3.1.10-030110-generic  [OK]
Trying kernel                    3.0.18-030018-generic  [OK]
Trying kernel                  2.6.39-02063904-generic  [OK]
Trying kernel                  2.6.38-02063808-generic  [OK]
Trying kernel                  2.6.37-02063706-generic  [OK]
Trying kernel                  2.6.36-02063604-generic  [OK]
Trying kernel                  2.6.35-02063512-generic  [OK]
Trying kernel                  2.6.34-02063410-generic  [OK]
Trying kernel                  2.6.33-02063305-generic  [OK]
Trying kernel                  2.6.32-02063255-generic  [OK]
Trying kernel                  2.6.31-02063113-generic  [OK]
Trying kernel                  2.6.30-02063010-generic  [OK]
Trying kernel                  2.6.29-02062906-generic  [OK]
Trying kernel                  2.6.28-02062810-generic  [OK]
Trying kernel                    2.6.27-020627-generic  [OK]
Trying kernel                    2.6.26-020626-generic  [OK]
Trying kernel                    2.6.25-020625-generic  [OK]
Trying kernel                    2.6.24-020624-generic  [OK]

Signed-off-by: Luis R. Rodriguez <mcgrof@frijolero.org>
compat/Makefile
compat/flow_dissector.c
compat/sch_fq_codel.c
include/linux/compat-2.6.25.h
include/linux/compat-2.6.27.h
include/linux/compat-2.6.37.h
include/linux/compat-3.1.h
include/linux/compat-3.5.h
include/net/flow_keys.h
scripts/gen-compat-config.sh

index 8397714..eb4eda1 100644 (file)
@@ -3,6 +3,7 @@ obj-m += compat.o
 
 obj-$(CONFIG_COMPAT_FIRMWARE_CLASS) += compat_firmware_class.o
 obj-$(CONFIG_COMPAT_NET_SCH_CODEL) += sch_codel.o
+obj-$(CONFIG_COMPAT_NET_SCH_FQ_CODEL) += sch_fq_codel.o
 
 compat-y += main.o
 
@@ -37,7 +38,9 @@ compat-$(CONFIG_COMPAT_KERNEL_2_6_39) += \
        kstrtox.o
 compat-$(CONFIG_COMPAT_KERNEL_3_0) += compat-3.0.o
 compat-$(CONFIG_COMPAT_KERNEL_3_2) += compat-3.2.o
-compat-$(CONFIG_COMPAT_KERNEL_3_3) += compat-3.3.o
+compat-$(CONFIG_COMPAT_KERNEL_3_3) += \
+       compat-3.3.o \
+       flow_dissector.o
 compat-$(CONFIG_COMPAT_KERNEL_3_4) += compat-3.4.o
 
 compat-$(CONFIG_COMPAT_CORDIC) += cordic.o
index a225089..8affda0 100644 (file)
@@ -141,4 +141,4 @@ ipv6:
 
        return true;
 }
-EXPORT_SYMBOL(skb_flow_dissect);
+EXPORT_SYMBOL_GPL(skb_flow_dissect);
index 9fc1c62..f03df2a 100644 (file)
@@ -65,6 +65,9 @@ struct fq_codel_sched_data {
 
        struct list_head new_flows;     /* list of new flows */
        struct list_head old_flows;     /* list of old flows */
+#if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
+       u32 limit;
+#endif
 };
 
 static unsigned int fq_codel_hash(const struct fq_codel_sched_data *q,
@@ -196,7 +199,11 @@ static int fq_codel_enqueue(struct sk_buff *skb, struct Qdisc *sch)
                flow->deficit = q->quantum;
                flow->dropped = 0;
        }
+#if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
+       if (++sch->q.qlen < q->limit)
+#else
        if (++sch->q.qlen < sch->limit)
+#endif
                return NET_XMIT_SUCCESS;
 
        q->drop_overlimit++;
@@ -334,7 +341,11 @@ static int fq_codel_change(struct Qdisc *sch, struct nlattr *opt)
        }
 
        if (tb[TCA_FQ_CODEL_LIMIT])
+#if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
+               q->limit = nla_get_u32(tb[TCA_FQ_CODEL_LIMIT]);
+#else
                sch->limit = nla_get_u32(tb[TCA_FQ_CODEL_LIMIT]);
+#endif
 
        if (tb[TCA_FQ_CODEL_ECN])
                q->cparams.ecn = !!nla_get_u32(tb[TCA_FQ_CODEL_ECN]);
@@ -342,7 +353,11 @@ static int fq_codel_change(struct Qdisc *sch, struct nlattr *opt)
        if (tb[TCA_FQ_CODEL_QUANTUM])
                q->quantum = max(256U, nla_get_u32(tb[TCA_FQ_CODEL_QUANTUM]));
 
+#if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
+       while (sch->q.qlen > q->limit) {
+#else
        while (sch->q.qlen > sch->limit) {
+#endif
                struct sk_buff *skb = fq_codel_dequeue(sch);
 
                kfree_skb(skb);
@@ -378,7 +393,11 @@ static void fq_codel_destroy(struct Qdisc *sch)
 {
        struct fq_codel_sched_data *q = qdisc_priv(sch);
 
+#if (LINUX_VERSION_CODE > KERNEL_VERSION(2,6,25))
        tcf_destroy_chain(&q->filter_list);
+#else
+       tcf_destroy_chain(q->filter_list);
+#endif
        fq_codel_free(q->backlogs);
        fq_codel_free(q->flows);
 }
@@ -388,7 +407,11 @@ static int fq_codel_init(struct Qdisc *sch, struct nlattr *opt)
        struct fq_codel_sched_data *q = qdisc_priv(sch);
        int i;
 
+#if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
+       q->limit = 10*1024;
+#else
        sch->limit = 10*1024;
+#endif
        q->flows_cnt = 1024;
        q->quantum = psched_mtu(qdisc_dev(sch));
        q->perturbation = net_random();
@@ -420,7 +443,11 @@ static int fq_codel_init(struct Qdisc *sch, struct nlattr *opt)
                        INIT_LIST_HEAD(&flow->flowchain);
                }
        }
+#if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
+       if (q->limit >= 1)
+#else
        if (sch->limit >= 1)
+#endif
                sch->flags |= TCQ_F_CAN_BYPASS;
        else
                sch->flags &= ~TCQ_F_CAN_BYPASS;
@@ -439,7 +466,11 @@ static int fq_codel_dump(struct Qdisc *sch, struct sk_buff *skb)
        if (nla_put_u32(skb, TCA_FQ_CODEL_TARGET,
                        codel_time_to_us(q->cparams.target)) ||
            nla_put_u32(skb, TCA_FQ_CODEL_LIMIT,
+#if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
+                       q->limit) ||
+#else
                        sch->limit) ||
+#endif
            nla_put_u32(skb, TCA_FQ_CODEL_INTERVAL,
                        codel_time_to_us(q->cparams.interval)) ||
            nla_put_u32(skb, TCA_FQ_CODEL_ECN,
@@ -599,7 +630,9 @@ static struct Qdisc_ops fq_codel_qdisc_ops __read_mostly = {
        .priv_size      =       sizeof(struct fq_codel_sched_data),
        .enqueue        =       fq_codel_enqueue,
        .dequeue        =       fq_codel_dequeue,
+#if (LINUX_VERSION_CODE > KERNEL_VERSION(2,6,28))
        .peek           =       qdisc_peek_dequeued,
+#endif
        .drop           =       fq_codel_drop,
        .init           =       fq_codel_init,
        .reset          =       fq_codel_reset,
index 356186d..563b65f 100644 (file)
@@ -36,7 +36,6 @@ int __must_check pci_enable_device_mem(struct pci_dev *dev);
 
 /*
  * backports 2658fa803111dae1353602e7f586de8e537803e2
- * We skip proto_ports_offset() as I'm lazy.
  */
 
 static inline bool ipv4_is_loopback(__be32 addr)
index 106e7ee..ece825d 100644 (file)
 #include <net/sch_generic.h>
 #include <linux/ethtool.h>
 
+static inline struct net_device *qdisc_dev(const struct Qdisc *qdisc)
+{
+       return qdisc->dev;
+}
+
+/*
+ * Backports 378a2f09 and c27f339a
+ * This may need a bit more work.
+ */
+enum net_xmit_qdisc_t {
+       __NET_XMIT_STOLEN = 0x00010000,
+       __NET_XMIT_BYPASS = 0x00020000,
+};
+
 struct qdisc_skb_cb {
        unsigned int            pkt_len;
        char                    data[];
index c19e781..7e14853 100644 (file)
@@ -7,6 +7,25 @@
 
 #include <linux/skbuff.h>
 #include <linux/leds.h>
+#include <linux/in.h>
+#include <linux/errno.h>
+
+static inline int proto_ports_offset(int proto)
+{
+       switch (proto) {
+       case IPPROTO_TCP:
+       case IPPROTO_UDP:
+       case IPPROTO_DCCP:
+       case IPPROTO_ESP:       /* SPI */
+       case IPPROTO_SCTP:
+       case IPPROTO_UDPLITE:
+               return 0;
+       case IPPROTO_AH:        /* SPI */
+               return 4;
+       default:
+               return -EINVAL;
+       }
+}
 
 #define SDIO_CLASS_BT_AMP      0x09    /* Type-A Bluetooth AMP interface */
 
index 3fdcbf8..fdd27d4 100644 (file)
@@ -7,6 +7,13 @@
 
 #include <linux/security.h>
 #include <linux/skbuff.h>
+#include <net/ip.h>
+
+/* Backports 56f8a75c */
+static inline bool ip_is_fragment(const struct iphdr *iph)
+{
+       return (iph->frag_off & htons(IP_MF | IP_OFFSET)) != 0;
+}
 
 static inline struct sk_buff *__netdev_alloc_skb_ip_align(struct net_device *dev,
                                                          unsigned int length, gfp_t gfp)
index c6d478e..c9ba6af 100644 (file)
@@ -45,6 +45,69 @@ struct tc_codel_xstats {
        __u32   dropping;  /* are we in dropping state ? */
 };
 
+/* This backports:
+ *
+ * commit 4b549a2ef4bef9965d97cbd992ba67930cd3e0fe
+ * Author: Eric Dumazet <edumazet@google.com>
+ * Date:   Fri May 11 09:30:50 2012 +0000
+ *    fq_codel: Fair Queue Codel AQM
+ */
+
+/* FQ_CODEL */
+
+enum {
+       TCA_FQ_CODEL_UNSPEC,
+       TCA_FQ_CODEL_TARGET,
+       TCA_FQ_CODEL_LIMIT,
+       TCA_FQ_CODEL_INTERVAL,
+       TCA_FQ_CODEL_ECN,
+       TCA_FQ_CODEL_FLOWS,
+       TCA_FQ_CODEL_QUANTUM,
+       __TCA_FQ_CODEL_MAX
+};
+
+#define TCA_FQ_CODEL_MAX       (__TCA_FQ_CODEL_MAX - 1)
+
+enum {
+       TCA_FQ_CODEL_XSTATS_QDISC,
+       TCA_FQ_CODEL_XSTATS_CLASS,
+};
+
+struct tc_fq_codel_qd_stats {
+       __u32   maxpacket;      /* largest packet we've seen so far */
+       __u32   drop_overlimit; /* number of time max qdisc
+                                * packet limit was hit
+                                */
+       __u32   ecn_mark;       /* number of packets we ECN marked
+                                * instead of being dropped
+                                */
+       __u32   new_flow_count; /* number of time packets
+                                * created a 'new flow'
+                                */
+       __u32   new_flows_len;  /* count of flows in new list */
+       __u32   old_flows_len;  /* count of flows in old list */
+};
+
+struct tc_fq_codel_cl_stats {
+       __s32   deficit;
+       __u32   ldelay;         /* in-queue delay seen by most recently
+                                * dequeued packet
+                                */
+       __u32   count;
+       __u32   lastcount;
+       __u32   dropping;
+       __s32   drop_next;
+};
+
+struct tc_fq_codel_xstats {
+       __u32   type;
+       union {
+               struct tc_fq_codel_qd_stats qdisc_stats;
+               struct tc_fq_codel_cl_stats class_stats;
+       };
+};
+
+
 /* Backports tty_lock: Localise the lock */
 #define tty_lock(__tty) tty_lock()
 #define tty_unlock(__tty) tty_unlock()
index 80461c1..a875ee6 100644 (file)
@@ -1,3 +1,7 @@
+#if (LINUX_VERSION_CODE >= KERNEL_VERSION(3,3,0))
+#include_next <net/flow_keys.h>
+#else
+
 #ifndef _NET_FLOW_KEYS_H
 #define _NET_FLOW_KEYS_H
 
@@ -14,3 +18,4 @@ struct flow_keys {
 
 extern bool skb_flow_dissect(const struct sk_buff *skb, struct flow_keys *flow);
 #endif
+#endif
index be90fdb..3eba34e 100755 (executable)
@@ -64,7 +64,7 @@ if [[ ${CONFIG_COMPAT_KERNEL_2_6_36} = "y" ]]; then
 fi
 
 if [[ ${CONFIG_COMPAT_KERNEL_3_5} = "y" ]]; then
-       # We don't have 2.6.24 backport support yet for Codel
+       # We don't have 2.6.24 backport support yet for Codel / FQ CoDel
        # For those who want to try this is what is required that I can tell
        # so far:
        #  * struct Qdisc_ops
@@ -72,5 +72,6 @@ if [[ ${CONFIG_COMPAT_KERNEL_3_5} = "y" ]]; then
        #       - you need to parse data received from userspace differently
        if [[ ${CONFIG_COMPAT_KERNEL_2_6_25} != "y" ]]; then
                echo "export CONFIG_COMPAT_NET_SCH_CODEL=m"
+               echo "export CONFIG_COMPAT_NET_SCH_FQ_CODEL=m"
        fi
 fi