core: Factor out flow calculation from get_rps_cpu

From: Krishna Kumar <[email protected]>

Implement multiqueue facility for macvtap driver. The idea is that a macvtap device can be opened multiple times and the fd's can be used to register eg, as backend for vhost.

Signed-off-by Krishna Kumar <[email protected]>

---
 drivers/net/macvtap.c      |   89 ++++++++++++++++++++++++++++------- include/linux/if_macvlan.h |    9 +++

 2 files changed, 80 insertions(+), 18 deletions(-)

diff -ruNp org/drivers/net/macvtap.c new/drivers/net/macvtap.c

drivers/net/macvtap.c   2010-08-04 16:19:32.000000000 +0530 renamed from drivers/net/macvtap.c   2010-07-28 15:10:10.000000000 +0530 +22 -3

@@ -84,26 +84,45 @@ static const struct proto_ops macvtap_so
  static DEFINE_SPINLOCK(macvtap_lock);
 
  /*
- * Choose the next free queue, for now there is only one
+ * get_slot: return a [unused/occupied] slot in vlan->taps[]:
+ *     - if 'q' is NULL, return the first empty slot;
+ *     - otherwise, return the slot this pointer occupies.
  */
+static int get_slot(struct macvlan_dev *vlan, struct macvtap_queue *q)
+{
+       int i;
+
+       for (i = 0; i < MAX_MACVTAP_QUEUES; i++) {
+               if (rcu_dereference(vlan->taps[i]) == q)
+                       return i;
+       }
+
+       /* Should never happen */
+       BUG_ON(1);
+}
+
  static int macvtap_set_queue(struct net_device *dev, struct file *file,
                                struct macvtap_queue *q)
  {
        struct macvlan_dev *vlan = netdev_priv(dev);
+       int index;
        int err = -EBUSY;
 
        spin_lock(&macvtap_lock);
-       if (rcu_dereference(vlan->tap))
+       if (vlan->numvtaps == MAX_MACVTAP_QUEUES)
                goto out;
 
        err = 0;
+       index = get_slot(vlan, NULL);
        rcu_assign_pointer(q->vlan, vlan);
-       rcu_assign_pointer(vlan->tap, q);
+       rcu_assign_pointer(vlan->taps[index], q);
        sock_hold(&q->sk);
 
        q->file = file;
        file->private_data = q;
 
+       vlan->numvtaps++;
+

 out:
       spin_unlock(&macvtap_lock);
       return err;

drivers/net/macvtap.c   2010-08-04 16:19:32.000000000 +0530 renamed from drivers/net/macvtap.c   2010-07-28 15:10:10.000000000 +0530 +21 -3

@@ -124,9 +143,12 @@ static void macvtap_put_queue(struct mac
        spin_lock(&macvtap_lock);
        vlan = rcu_dereference(q->vlan);
        if (vlan) {
-               rcu_assign_pointer(vlan->tap, NULL);
+               int index = get_slot(vlan, q);
+
+               rcu_assign_pointer(vlan->taps[index], NULL);
                rcu_assign_pointer(q->vlan, NULL);
                sock_put(&q->sk);
+               --vlan->numvtaps;
        }
 
        spin_unlock(&macvtap_lock);

@@ -136,39 +158,72 @@ static void macvtap_put_queue(struct mac
  }
 
  /*
- * Since we only support one queue, just dereference the pointer.
+ * Select a queue based on the rxq of the device on which this packet
+ * arrived. If the incoming device is not mq, calculate a flow hash to
+ * select a queue. vlan->numvtaps is cached in case it reduces during
+ * the execution of this function.
  */
  static struct macvtap_queue *macvtap_get_queue(struct net_device *dev,
                                               struct sk_buff *skb)
  {
        struct macvlan_dev *vlan = netdev_priv(dev);
+       struct macvtap_queue *tap = NULL;
+       int numvtaps = vlan->numvtaps;
+       __u32 rxq;
+
+       if (!numvtaps)
+               goto out;
+
+       if (likely(skb_rx_queue_recorded(skb))) {
+               rxq = skb_get_rx_queue(skb);
+
+               while (unlikely(rxq >= numvtaps))
+                       rxq -= numvtaps;
 
-       return rcu_dereference(vlan->tap);
+               tap = rcu_dereference(vlan->taps[rxq]);

drivers/net/macvtap.c   2010-08-04 16:19:32.000000000 +0530 renamed from drivers/net/macvtap.c   2010-07-28 15:10:10.000000000 +0530 +19 -11

+out:
+       return tap;
  }
 
  /*
  * The net_device is going away, give up the reference
- * that it holds on the queue (all the queues one day)
- * and safely set the pointer from the queues to NULL.
+ * that it holds on all queues and safely set the pointer
+ * from the queues to NULL.
  */
  static void macvtap_del_queues(struct net_device *dev)
  {
        struct macvlan_dev *vlan = netdev_priv(dev);
-       struct macvtap_queue *q;
+       struct macvtap_queue *q, *qlist[MAX_MACVTAP_QUEUES];
+       int i, j = 0;
 
+       /* macvtap_put_queue can free some slots, so go through all slots */
        spin_lock(&macvtap_lock);
-       q = rcu_dereference(vlan->tap);
-       if (!q) {
-               spin_unlock(&macvtap_lock);
-               return;
+       for (i = 0; i < MAX_MACVTAP_QUEUES && vlan->numvtaps; i++) {
+               q = rcu_dereference(vlan->taps[i]);
+               if (q) {
+                       qlist[j++] = q;
+                       rcu_assign_pointer(vlan->taps[i], NULL);
+                       rcu_assign_pointer(q->vlan, NULL);
+                       vlan->numvtaps--;
+               }
        }
-
-       rcu_assign_pointer(vlan->tap, NULL);
-       rcu_assign_pointer(q->vlan, NULL);
+       BUG_ON(vlan->numvtaps != 0);
        spin_unlock(&macvtap_lock);
 
        synchronize_rcu();
-       sock_put(&q->sk);
+
+       for (--j; j >= 0; j--)
+               sock_put(&qlist[j]->sk);
  }
 
  /*

diff -ruNp org/include/linux/if_macvlan.h new/include/linux/if_macvlan.h

include/linux/if_macvlan.h      2010-08-04 16:19:32.000000000 +0530 renamed from include/linux/if_macvlan.h      2010-07-28 15:10:10.000000000 +0530 +8 -1

@@ -40,6 +40,12 @@ struct macvlan_rx_stats {
        unsigned long           rx_errors;
  };
 
+/*
+ * Maximum times a macvtap device can be opened. This can be used to
+ * configure the number of receive queue, e.g. for multiqueue virtio.
+ */
+#define MAX_MACVTAP_QUEUES     (NR_CPUS < 16 ? NR_CPUS : 16)
+
  struct macvlan_dev {
        struct net_device       *dev;
        struct list_head        list;

@@ -50,7 +56,8 @@ struct macvlan_dev {
        enum macvlan_mode       mode;
        int (*receive)(struct sk_buff *skb);
        int (*forward)(struct net_device *dev, struct sk_buff *skb);
-       struct macvtap_queue    *tap;
+       struct macvtap_queue    *taps[MAX_MACVTAP_QUEUES];
+       int                     numvtaps;
  };
 
  static inline void macvlan_count_rx(const struct macvlan_dev *vlan,

Quoted 19 lines

 static struct macvtap_queue *macvtap_get_queue(struct net_device *dev, struct sk_buff *skb) {
       struct macvlan_dev *vlan = netdev_priv(dev);
+       struct macvtap_queue *tap = NULL;
+       int numvtaps = vlan->numvtaps;
+       __u32 rxq;

drivers/net/macvtap.c +10 -1

+
+       if (!numvtaps)
+               goto out;
+
+       if (likely(skb_rx_queue_recorded(skb))) {
+               rxq = skb_get_rx_queue(skb);
+
+               while (unlikely(rxq >= numvtaps))
+                       rxq -= numvtaps;
 
-       return rcu_dereference(vlan->tap);
+               tap = rcu_dereference(vlan->taps[rxq]);

drivers/net/macvtap.c static void macvtap_put_queue(struct mac · line 193

Quoted 10 lines

drivers/net/macvtap.c +10 -0

+               if (tap)
+                       goto out;
+       }
+
+       rxq = skb_get_rxhash(skb);
+       if (!rxq)
+               rxq = smp_processor_id();
+
+       tap = rcu_dereference(vlan->taps[rxq & (numvtaps - 1)]);
+

numvtaps maybe not power of 2. So some queue maybe can't be used. You'd better maintain a online queue map and get the index as get_rps_cpu() dones.

((u64)rxhash * numvtaps) >> 32

for the sbks, we can't get a valid rxhash, we'd better pass them to a specified queue, such as queue 0.

Changli Gao <[email protected]> wrote on 08/04/2010 05:07:23 PM:

Thanks for your review and comments!

Quoted 34 lines

Quoted 19 lines

 static struct macvtap_queue *macvtap_get_queue(struct net_device *dev, struct sk_buff *skb) {
       struct macvlan_dev *vlan = netdev_priv(dev);
+       struct macvtap_queue *tap = NULL;
+       int numvtaps = vlan->numvtaps;
+       __u32 rxq;

drivers/net/macvtap.c +10 -1

+
+       if (!numvtaps)
+               goto out;
+
+       if (likely(skb_rx_queue_recorded(skb))) {
+               rxq = skb_get_rx_queue(skb);
+
+               while (unlikely(rxq >= numvtaps))
+                       rxq -= numvtaps;
 
-       return rcu_dereference(vlan->tap);
+               tap = rcu_dereference(vlan->taps[rxq]);

drivers/net/macvtap.c static void macvtap_put_queue(struct mac · line 193

Quoted 10 lines

drivers/net/macvtap.c +10 -0

+               if (tap)
+                       goto out;
+       }
+
+       rxq = skb_get_rxhash(skb);
+       if (!rxq)
+               rxq = smp_processor_id();
+
+       tap = rcu_dereference(vlan->taps[rxq & (numvtaps - 1)]);
+

numvtaps maybe not power of 2. So some queue maybe can't be used. You'd better maintain a online queue map and get the index as get_rps_cpu() dones.

Quoted 4 lines

((u64)rxhash * numvtaps) >> 32

for the sbks, we can't get a valid rxhash, we'd better pass them to a specified queue, such as queue 0.

macvtap *with* mq support would be used with mq devices - you open multiple queues on the macvtap device depending on the number of queues for the physical device. So since this is an unlikely case (as can be seen in the patch, and I guess I should add another "likely" to the "if (tap)" check since fd's should not be closed), I guess a simple % can be used. Does the following sound reasonable?

1. Use % to find the slot.

2. If slot is null - I don't want to handle this since I think it is better to return NULL if some fd's were closed by user. Typically this should never happen since fd's are opened and passed to vhost for setting up the backend. So if they are closed, then I think NULL is OK.

Arnd, please let me know what you would also suggest.

- KK

1. Use % to find the slot.
2. If slot is null - I don't want to handle this since I think it is better to return NULL if some fd's were closed by user. Typically this should never happen since fd's are opened and passed to vhost for setting up the backend. So if they are closed, then I think NULL is OK.

From: Krishna Kumar <[email protected]>

Factor out flow calculation code from get_rps_cpu, since other functions can use the same code.

Revisions:

v2 - Ben: Separate flow calcuation out and use in select queue. v3 - Arnd: Don't re-implement MIN.
v4 - Changli: skb->data points to ethernet header in macvtap, and make a fast path.

Tested macvtap with this patch.

Signed-off-by Krishna Kumar <[email protected]>

---
 include/linux/skbuff.h |   11 ++++
 net/core/dev.c         |  107 ++++++++++++++++++++++-----------------

 2 files changed, 74 insertions(+), 44 deletions(-)

diff -ruNp org/include/linux/skbuff.h new/include/linux/skbuff.h

include/linux/skbuff.h  2010-08-04 16:19:30.000000000 +0530 renamed from include/linux/skbuff.h  2010-08-04 09:07:05.000000000 +0530 +11 -0

@@ -558,6 +558,17 @@ extern unsigned int   skb_find_text(stru
                                    unsigned int to, struct ts_config *config,
                                    struct ts_state *state);
 
+extern __u32 __skb_get_rxhash(struct sk_buff *skb);
+static inline __u32 skb_get_rxhash(struct sk_buff *skb)
+{
+       __u32 rxhash = skb->rxhash;
+
+       if (!rxhash)
+               rxhash = __skb_get_rxhash(skb);
+
+       return rxhash;
+}
+
  #ifdef NET_SKBUFF_DATA_USES_OFFSET
  static inline unsigned char *skb_end_pointer(const struct sk_buff *skb)
  {

diff -ruNp org/net/core/dev.c new/net/core/dev.c

net/core/dev.c  2010-08-04 16:19:30.000000000 +0530 renamed from net/core/dev.c  2010-08-04 09:07:05.000000000 +0530 +6 -34

@@ -2259,69 +2259,41 @@ static inline void ____napi_schedule(str
        __raise_softirq_irqoff(NET_RX_SOFTIRQ);
  }
 
-#ifdef CONFIG_RPS
-
-/* One global table that all flow-based protocols share. */
-struct rps_sock_flow_table *rps_sock_flow_table __read_mostly;
-EXPORT_SYMBOL(rps_sock_flow_table);
-
  /*
- * get_rps_cpu is called from netif_receive_skb and returns the target
- * CPU from the RPS map of the receiving queue for a given skb.
- * rcu_read_lock must be held on entry.
+ * __skb_get_rxhash: calculate a flow hash based on src/dst addresses
+ * and src/dst port numbers. On success, returns a non-zero hash number,
+ * otherwise 0.
  */
-static int get_rps_cpu(struct net_device *dev, struct sk_buff *skb,
-                      struct rps_dev_flow **rflowp)
+__u32 __skb_get_rxhash(struct sk_buff *skb)
  {
+       int nhoff, hash = 0;
        struct ipv6hdr *ip6;
        struct iphdr *ip;
-       struct netdev_rx_queue *rxqueue;
-       struct rps_map *map;
-       struct rps_dev_flow_table *flow_table;
-       struct rps_sock_flow_table *sock_flow_table;
-       int cpu = -1;
        u8 ip_proto;
-       u16 tcpu;
        u32 addr1, addr2, ihl;
        union {
                u32 v32;
                u16 v16[2];
        } ports;
 
-       if (skb_rx_queue_recorded(skb)) {
-               u16 index = skb_get_rx_queue(skb);
-               if (unlikely(index >= dev->num_rx_queues)) {
-                       WARN_ONCE(dev->num_rx_queues > 1, "%s received packet "
-                               "on queue %u, but number of RX queues is %u\n",
-                               dev->name, index, dev->num_rx_queues);
-                       goto done;
-               }
-               rxqueue = dev->_rx + index;
-       } else
-               rxqueue = dev->_rx;
-
-       if (!rxqueue->rps_map && !rxqueue->rps_flow_table)
-               goto done;
-
-       if (skb->rxhash)
-               goto got_hash; /* Skip hash computation on packet header */
+       nhoff = skb_network_offset(skb);
 
        switch (skb->protocol) {

       case __constant_htons(ETH_P_IP):
-               if (!pskb_may_pull(skb, sizeof(*ip)))
+               if (!pskb_may_pull(skb, sizeof(*ip) + nhoff)) goto done;

-               ip = (struct iphdr *) skb->data;
+               ip = (struct iphdr *) skb->data + nhoff; ip_proto = ip->protocol;
               addr1 = (__force u32) ip->saddr; addr2 = (__force u32) ip->daddr;
               ihl = ip->ihl;
               break;
       case __constant_htons(ETH_P_IPV6):
-               if (!pskb_may_pull(skb, sizeof(*ip6)))
+               if (!pskb_may_pull(skb, sizeof(*ip6) + nhoff)) goto done;

-               ip6 = (struct ipv6hdr *) skb->data;
+               ip6 = (struct ipv6hdr *) skb->data + nhoff; ip_proto = ip6->nexthdr;
               addr1 = (__force u32) ip6->saddr.s6_addr32[3]; addr2 = (__force u32) ip6->daddr.s6_addr32[3];

net/core/dev.c  2010-08-04 16:19:30.000000000 +0530 renamed from net/core/dev.c  2010-08-04 09:07:05.000000000 +0530 +0 -0

@@ -2330,6 +2302,7 @@ static int get_rps_cpu(struct net_device

       default:
               goto done;
       }
+
       switch (ip_proto) {
       case IPPROTO_TCP:
       case IPPROTO_UDP:

net/core/dev.c  2010-08-04 16:19:30.000000000 +0530 renamed from net/core/dev.c  2010-08-04 09:07:05.000000000 +0530 +0 -0

@@ -2338,8 +2311,9 @@ static int get_rps_cpu(struct net_device

       case IPPROTO_AH:
       case IPPROTO_SCTP:
       case IPPROTO_UDPLITE:
-               if (pskb_may_pull(skb, (ihl * 4) + 4)) {
-                       ports.v32 = * (__force u32 *) (skb->data + (ihl * 4));
+               if (pskb_may_pull(skb, (ihl * 4) + 4 + nhoff)) {
+                       ports.v32 = * (__force u32 *) (skb->data + nhoff +
+                                                      (ihl * 4)); if (ports.v16[1] < ports.v16[0]) swap(ports.v16[0], ports.v16[1]); break;

net/core/dev.c  2010-08-04 16:19:30.000000000 +0530 renamed from net/core/dev.c  2010-08-04 09:07:05.000000000 +0530 +36 -4

@@ -2352,11 +2326,56 @@ static int get_rps_cpu(struct net_device
        /* get a consistent hash (same value on both flow directions) */
        if (addr2 < addr1)
                swap(addr1, addr2);
-       skb->rxhash = jhash_3words(addr1, addr2, ports.v32, hashrnd);
-       if (!skb->rxhash)
-               skb->rxhash = 1;
 
-got_hash:
+       hash = jhash_3words(addr1, addr2, ports.v32, hashrnd);
+       if (!hash)
+               hash = 1;
+
+done:
+       return hash;
+}
+EXPORT_SYMBOL(__skb_get_rxhash);
+
+#ifdef CONFIG_RPS
+
+/* One global table that all flow-based protocols share. */
+struct rps_sock_flow_table *rps_sock_flow_table __read_mostly;
+EXPORT_SYMBOL(rps_sock_flow_table);
+
+/*
+ * get_rps_cpu is called from netif_receive_skb and returns the target
+ * CPU from the RPS map of the receiving queue for a given skb.
+ * rcu_read_lock must be held on entry.
+ */
+static int get_rps_cpu(struct net_device *dev, struct sk_buff *skb,
+                      struct rps_dev_flow **rflowp)
+{
+       struct netdev_rx_queue *rxqueue;
+       struct rps_map *map;
+       struct rps_dev_flow_table *flow_table;
+       struct rps_sock_flow_table *sock_flow_table;
+       int cpu = -1;
+       u16 tcpu;
+
+       if (skb_rx_queue_recorded(skb)) {
+               u16 index = skb_get_rx_queue(skb);
+               if (unlikely(index >= dev->num_rx_queues)) {
+                       WARN_ONCE(dev->num_rx_queues > 1, "%s received packet "
+                               "on queue %u, but number of RX queues is %u\n",
+                               dev->name, index, dev->num_rx_queues);

net/core/dev.c  2010-08-04 16:19:30.000000000 +0530 renamed from net/core/dev.c  2010-08-04 09:07:05.000000000 +0530 +3 -0

+       if (skb->rxhash < 0)
+               goto done;
+
        flow_table = rcu_dereference(rxqueue->rps_flow_table);
        sock_flow_table = rcu_dereference(rps_sock_flow_table);
        if (flow_table && sock_flow_table) {

Quoted 15 lines

net/core/dev.c +15 -0

+#ifdef CONFIG_RPS
+
+/* One global table that all flow-based protocols share. */
+struct rps_sock_flow_table *rps_sock_flow_table __read_mostly;
+EXPORT_SYMBOL(rps_sock_flow_table);
+
+/*
+ * get_rps_cpu is called from netif_receive_skb and returns the target
+ * CPU from the RPS map of the receiving queue for a given skb.
+ * rcu_read_lock must be held on entry.
+ */
+static int get_rps_cpu(struct net_device *dev, struct sk_buff *skb,
+                      struct rps_dev_flow **rflowp)
+{
+       struct netdev_rx_queue *rxqueue;

net/core/dev.c static int get_rps_cpu(struct net_device

Quoted 10 lines

net/core/dev.c +10 -0

+       struct rps_map *map;
+       struct rps_dev_flow_table *flow_table;
+       struct rps_sock_flow_table *sock_flow_table;
+       int cpu = -1;
+       u16 tcpu;
+
+       if (skb_rx_queue_recorded(skb)) {
+               u16 index = skb_get_rx_queue(skb);
+               if (unlikely(index >= dev->num_rx_queues)) {
+                       WARN_ONCE(dev->num_rx_queues > 1, "%s

received packet "

Quoted 1 line

+                               "on queue %u, but number of RX

queues is %u\n",

net/core/dev.c static int get_rps_cpu(struct net_device · line 2375

Quoted 11 lines

+                               dev->name, index, dev->num_rx_queues);
+                       goto done;
+               }
+               rxqueue = dev->_rx + index;
+       } else
+               rxqueue = dev->_rx;

net/core/dev.c +5 -0

+
+       if (!rxqueue->rps_map && !rxqueue->rps_flow_table)
+               goto done;
+
+       skb->rxhash = skb_get_rxhash(skb);

the return value of skb_get_rxhash() maybe skb->rxhash, so we don't need to assign it to skb->rxhash again. Use a local variable to save the value and __skb_get_rxhash() should cache the rxhash into skb->rxhash for future use.

Changli Gao <[email protected]> wrote on 08/04/2010 04:52:58 PM:

Quoted 5 lines

the return value of skb_get_rxhash() maybe skb->rxhash, so we don't need to assign it to skb->rxhash again. Use a local variable to save the value and __skb_get_rxhash() should cache the rxhash into skb->rxhash for future use.

I wanted the function to return a rxhash instead of save+return, since other users, eg macvtap, doesn't need the rxhash beyond calculating a rxq with that hash. So for those users, we can avoid updating both skb->rxhash and a local variable (since with your suggestion, rps will update either one or two variables depending on whether rxhash is cached or not). I am not sure which is better.

Changli Gao <[email protected]>
08/04/2010 07:08 PM

To

Krishna Kumar2/India/IBM@IBMIN

cc

[email protected], [email protected], [email protected], [email protected], [email protected], [email protected]

Subject

Re: [PATCH v4 1/2] core: Factor out flow calculation from get_rps_cpu

On Wed, Aug 4, 2010 at 8:02 PM, Krishna Kumar2 <[email protected]>

Quoted 7 lines

Changli Gao <[email protected]> wrote on 08/04/2010 04:52:58 PM:

Quoted 5 lines

the return value of skb_get_rxhash() maybe skb->rxhash, so we don't need to assign it to skb->rxhash again. Use a local variable to save the value and __skb_get_rxhash() should cache the rxhash into skb->rxhash for future use.

Quoted 8 lines

I wanted the function to return a rxhash instead of save+return, since other users, eg macvtap, doesn't need the rxhash beyond calculating a rxq with that hash. So for those users, we can avoid updating both skb->rxhash and a local variable (since with your suggestion, rps will update either one or two variables depending on whether rxhash is cached or not). I am not sure which is better.

rxhash can also be generated by NIC(hardware) and used some where else. So for these users, generating the rxhash again is wasting time.

Quoted 9 lines

macvtap *with* mq support would be used with mq devices - you open multiple queues on the macvtap device depending on the number of queues for the physical device. So since this is an unlikely case (as can be seen in the patch, and I guess I should add another "likely" to the "if (tap)" check since fd's should not be closed), I guess a simple % can be used. Does the following sound reasonable?

1. Use % to find the slot.

It is slower than the method used by get_rps_cpu().