[PATCH] (4/4) bridge: forwarding table lockless update

[PATCH] (4/4) bridge: forwarding table lockless update

[Stephen Hemminger]

Optimize bridge forwarding table for the fastpath of updating
an existing entry. Use RCU to find the entry and change it's time.
Fallback to normal locking for insert. This gives about a 1/3
improvement in packets forwarding per second on SMP.

Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

diff -Nru a/net/bridge/br_fdb.c b/net/bridge/br_fdb.c
--- a/net/bridge/br_fdb.c	2005-03-10 15:25:50 -08:00
+++ b/net/bridge/br_fdb.c	2005-03-10 15:25:50 -08:00
@@ -25,7 +25,7 @@
 
 static kmem_cache_t *br_fdb_cache;
 static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
-		      const unsigned char *addr, int is_local);
+		      const unsigned char *addr);
 
 void __init br_fdb_init(void)
 {
@@ -101,8 +101,7 @@
 	}
  insert:
 	/* insert new address,  may fail if invalid address or dup. */
-	fdb_insert(br, p, newaddr, 1);
-
+	fdb_insert(br, p, newaddr);
 
 	spin_unlock_bh(&br->hash_lock);
 }
@@ -258,71 +257,108 @@
 	return num;
 }
 
-static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
-		  const unsigned char *addr, int is_local)
+static inline struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head,
+						    const unsigned char *addr)
 {
 	struct hlist_node *h;
 	struct net_bridge_fdb_entry *fdb;
-	int hash = br_mac_hash(addr);
 
-	if (!is_valid_ether_addr(addr))
-		return -EADDRNOTAVAIL;
+	hlist_for_each_entry_rcu(fdb, h, head, hlist) {
+		if (!memcmp(fdb->addr.addr, addr, ETH_ALEN))
+			return fdb;
+	}
+	return NULL;
+}
 
-	hlist_for_each_entry(fdb, h, &br->hash[hash], hlist) {
-		if (!memcmp(fdb->addr.addr, addr, ETH_ALEN)) {
-			/* attempt to update an entry for a local interface */
-			if (fdb->is_local) {
-				/* it is okay to have multiple ports with same 
-				 * address, just don't allow to be spoofed.
-				 */
-				if (is_local) 
-					return 0;
-
-				if (net_ratelimit()) 
-					printk(KERN_WARNING "%s: received packet with "
-					       " own address as source address\n",
-					       source->dev->name);
-				return -EEXIST;
-			}
+static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head,
+					       struct net_bridge_port *source,
+					       const unsigned char *addr, 
+					       int is_local)
+{
+	struct net_bridge_fdb_entry *fdb;
 
-			if (is_local) {
-				printk(KERN_WARNING "%s adding interface with same address "
-				       "as a received packet\n",
-				       source->dev->name);
-				goto update;
-			}
+	fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);
+	if (fdb) {
+		memcpy(fdb->addr.addr, addr, ETH_ALEN);
+		atomic_set(&fdb->use_count, 1);
+		hlist_add_head_rcu(&fdb->hlist, head);
+
+		fdb->dst = source;
+		fdb->is_local = is_local;
+		fdb->is_static = is_local;
+		fdb->ageing_timer = jiffies;
+	}
+	return fdb;
+}
 
-			if (fdb->is_static)
-				return 0;
+static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
+		  const unsigned char *addr)
+{
+	struct hlist_head *head = &br->hash[br_mac_hash(addr)];
+	struct net_bridge_fdb_entry *fdb;
 
-			goto update;
-		}
-	}
+	if (!is_valid_ether_addr(addr))
+		return -EINVAL;
 
-	fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);
-	if (!fdb)
-		return ENOMEM;
+	fdb = fdb_find(head, addr);
+	if (fdb) {
+		/* it is okay to have multiple ports with same 
+		 * address, just use the first one.
+		 */
+		if (fdb->is_local) 
+			return 0;
+
+		printk(KERN_WARNING "%s adding interface with same address "
+		       "as a received packet\n",
+		       source->dev->name);
+		fdb_delete(fdb);
+ 	}
 
-	memcpy(fdb->addr.addr, addr, ETH_ALEN);
-	atomic_set(&fdb->use_count, 1);
-	hlist_add_head_rcu(&fdb->hlist, &br->hash[hash]);
-
- update:
-	fdb->dst = source;
-	fdb->is_local = is_local;
-	fdb->is_static = is_local;
-	fdb->ageing_timer = jiffies;
+	if (!fdb_create(head, source, addr, 1))
+		return -ENOMEM;
 
 	return 0;
 }
 
 int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
-		  const unsigned char *addr, int is_local)
+		  const unsigned char *addr)
 {
 	int ret;
 
 	spin_lock_bh(&br->hash_lock);
-	ret = fdb_insert(br, source, addr, is_local);
+	ret = fdb_insert(br, source, addr);
 	spin_unlock_bh(&br->hash_lock);
 	return ret;
+}
+
+void br_fdb_update(struct net_bridge *br, struct net_bridge_port *source,
+		   const unsigned char *addr)
+{
+	struct hlist_head *head = &br->hash[br_mac_hash(addr)];
+	struct net_bridge_fdb_entry *fdb;
+
+	rcu_read_lock();
+	fdb = fdb_find(head, addr);
+	if (likely(fdb)) {
+		/* attempt to update an entry for a local interface */
+		if (unlikely(fdb->is_local)) {
+			if (net_ratelimit()) 
+				printk(KERN_WARNING "%s: received packet with "
+				       " own address as source address\n",
+				       source->dev->name);
+		} else {
+			/* fastpath: update of existing entry */
+			fdb->dst = source;
+			fdb->ageing_timer = jiffies;
+		}
+	} else {
+		spin_lock_bh(&br->hash_lock);
+		if (!fdb_find(head, addr))
+			fdb_create(head, source, addr, 0);
+		/* else  we lose race and someone else inserts
+		 * it first, don't bother updating
+		 */
+		spin_unlock_bh(&br->hash_lock);
+	}
+	rcu_read_unlock();
 }
diff -Nru a/net/bridge/br_if.c b/net/bridge/br_if.c
--- a/net/bridge/br_if.c	2005-03-10 15:25:50 -08:00
+++ b/net/bridge/br_if.c	2005-03-10 15:25:50 -08:00
@@ -332,7 +332,7 @@
 	if (IS_ERR(p = new_nbp(br, dev, br_initial_port_cost(dev))))
 		return PTR_ERR(p);
 
- 	if ((err = br_fdb_insert(br, p, dev->dev_addr, 1)))
+ 	if ((err = br_fdb_insert(br, p, dev->dev_addr)))
 		destroy_nbp(p);
  
 	else if ((err = br_sysfs_addif(p)))
diff -Nru a/net/bridge/br_input.c b/net/bridge/br_input.c
--- a/net/bridge/br_input.c	2005-03-10 15:25:50 -08:00
+++ b/net/bridge/br_input.c	2005-03-10 15:25:50 -08:00
@@ -105,12 +105,12 @@
 	if (p->state == BR_STATE_DISABLED)
 		goto err;
 
-	if (eth_hdr(skb)->h_source[0] & 1)
+	if (!is_valid_ether_addr(eth_hdr(skb)->h_source))
 		goto err;
 
 	if (p->state == BR_STATE_LEARNING ||
 	    p->state == BR_STATE_FORWARDING)
-		br_fdb_insert(p->br, p, eth_hdr(skb)->h_source, 0);
+		br_fdb_update(p->br, p, eth_hdr(skb)->h_source);
 
 	if (p->br->stp_enabled &&
 	    !memcmp(dest, bridge_ula, 5) &&
diff -Nru a/net/bridge/br_private.h b/net/bridge/br_private.h
--- a/net/bridge/br_private.h	2005-03-10 15:25:50 -08:00
+++ b/net/bridge/br_private.h	2005-03-10 15:25:50 -08:00
@@ -146,8 +146,10 @@
 			  unsigned long count, unsigned long off);
 extern int br_fdb_insert(struct net_bridge *br,
 			 struct net_bridge_port *source,
-			 const unsigned char *addr,
-			 int is_local);
+			 const unsigned char *addr);
+extern void br_fdb_update(struct net_bridge *br,
+			  struct net_bridge_port *source,
+			  const unsigned char *addr);
 
 /* br_forward.c */
 extern void br_deliver(const struct net_bridge_port *to,

Re: [PATCH] (4/4) bridge: forwarding table lockless update

[David S. Miller]

On Thu, 10 Mar 2005 15:44:37 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> Optimize bridge forwarding table for the fastpath of updating
> an existing entry. Use RCU to find the entry and change it's time.
> Fallback to normal locking for insert. This gives about a 1/3
> improvement in packets forwarding per second on SMP.
> 
> Signed-off-by: Stephen Hemminger <shemminger@osdl.org>

Applied, thanks.

[PATCH] bridge: no update when hold time is zero

[Stephen Hemminger]

[-- Attachment #1: Type: text/plain, Size: 686 bytes --]

Some users, set hold time to zero on bridge so it always does
flooding. This is usually when using it with wireless.  The new RCU
based code changed the behaviour so the bridge would not flood for
one GC interval. This patch restores the original behaviour.

diff -Nru a/net/bridge/br_fdb.c b/net/bridge/br_fdb.c
--- a/net/bridge/br_fdb.c	2005-03-11 10:23:44 -08:00
+++ b/net/bridge/br_fdb.c	2005-03-11 10:23:44 -08:00
@@ -337,6 +337,10 @@
 	struct hlist_head *head = &br->hash[br_mac_hash(addr)];
 	struct net_bridge_fdb_entry *fdb;
 
+	/* some users want to always flood. */
+	if (hold_time(br) == 0)
+		return;
+
 	rcu_read_lock();
 	fdb = fdb_find(head, addr);
 	if (likely(fdb)) {

[-- Attachment #2: Type: text/plain, Size: 140 bytes --]

_______________________________________________
Bridge mailing list
Bridge@lists.osdl.org
http://lists.osdl.org/mailman/listinfo/bridge

Re: [PATCH] bridge: no update when hold time is zero

[David S. Miller]

On Fri, 11 Mar 2005 10:26:36 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> Some users, set hold time to zero on bridge so it always does
> flooding. This is usually when using it with wireless.  The new RCU
> based code changed the behaviour so the bridge would not flood for
> one GC interval. This patch restores the original behaviour.

Applied, thanks Stephen.

Please don't forget the signed-off-by line next time :-)