[PATCH net-next 6/9] net: bridge: vlan: use an RCU array for large flood sets

[Nikolay Aleksandrov <razor@blackwall.org>]

Walking the master VLAN's port-VLAN list avoids considering ports outside
the VLAN but its pointer chasing becomes more expensive than array when
many ports participate. Add an rcu array of port-VLAN pointers for larger
flood sets. Rebuild and publish the array under RTNL when VLAN membership
changes. Continue using the list for small flood sets and as a fallback
if the array allocation fails.

Signed-off-by: Nikolay Aleksandrov <razor@blackwall.org>
---
 From local sashiko run:
 [Severity: Medium]
 Could these rebuilds be amortized or batched for large VLAN memberships?

 In net/bridge/br_vlan.c, br_vlan_rebuild_port_array() allocates and copies the
 complete masterv->port_vlist whenever count exceeds
 BR_VLAN_PORT_ARRAY_THRESHOLD. It then defers freeing the previous complete
 array through kvfree_rcu(), so sustained updates can retain several full-array
 generations until their RCU grace periods finish.

 Every successful individual port-VLAN addition calls this helper from
 __vlan_add(), while every individual deletion calls it from __vlan_del().
 Growing a flood set from nine entries to N therefore copies
 9 + 10 + ... + N pointers, and shrinking it performs the same quadratic work
 while RTNL is held.

 Can this cause a control-plane CPU and transient-memory regression during
 large incremental bridge VLAN updates? The later patches in the series retain
 this rebuild-on-add/delete path in the final series state.

 Nik: Yes, that is well understood but it is control path and I have tested
      sustained 2k / sec VLAN add/delete with 64 VLAN ports in each VLAN.
      If it ever becomes a problem we can optimize it, I think for the
      initial implementation would be best to keep it simple.

 net/bridge/br_forward.c | 39 ++++++++++++++++++++++++++++++---------
 net/bridge/br_private.h | 13 +++++++++++++
 net/bridge/br_vlan.c    | 37 ++++++++++++++++++++++++++++++++++++-
 3 files changed, 79 insertions(+), 10 deletions(-)

diff --git a/net/bridge/br_forward.c b/net/bridge/br_forward.c
index 251d61e7c312..e8f30f2df1ed 100644
--- a/net/bridge/br_forward.c
+++ b/net/bridge/br_forward.c
@@ -261,6 +261,35 @@ static void br_flood_port(struct net_bridge_port **prev,
 	*prev = maybe_deliver(*prev, p, skb, local_orig);
 }
 
+static void br_flood_vlan(struct net_bridge_port **prev,
+			  struct net_bridge_vlan *v, struct sk_buff *skb,
+			  enum br_pkt_type pkt_type, bool local_orig)
+{
+	struct net_bridge_vlan_port_array *array;
+	struct net_bridge_vlan *masterv, *pv;
+
+	masterv = br_vlan_is_master(v) ? v : v->brvlan;
+	array = rcu_dereference(masterv->port_array);
+	if (array) {
+		unsigned int i;
+
+		for (i = 0; i < array->count; i++) {
+			pv = array->vlans[i];
+			br_flood_port(prev, pv->port, skb, pkt_type,
+				      local_orig, v->vid);
+			if (IS_ERR(*prev))
+				break;
+		}
+	} else {
+		list_for_each_entry_rcu(pv, &masterv->port_vlist, port_vlist) {
+			br_flood_port(prev, pv->port, skb, pkt_type,
+				      local_orig, v->vid);
+			if (IS_ERR(*prev))
+				break;
+		}
+	}
+}
+
 /* called under rcu_read_lock */
 void br_flood(struct net_bridge *br, struct net_bridge_vlan *v,
 	      struct sk_buff *skb, enum br_pkt_type pkt_type,
@@ -271,15 +300,7 @@ void br_flood(struct net_bridge *br, struct net_bridge_vlan *v,
 	br_tc_skb_miss_set(skb, pkt_type != BR_PKT_BROADCAST);
 
 	if (v) {
-		struct net_bridge_vlan *masterv, *pv;
-
-		masterv = br_vlan_is_master(v) ? v : v->brvlan;
-		list_for_each_entry_rcu(pv, &masterv->port_vlist, port_vlist) {
-			br_flood_port(&prev, pv->port, skb, pkt_type,
-				      local_orig, v->vid);
-			if (IS_ERR(prev))
-				break;
-		}
+		br_flood_vlan(&prev, v, skb, pkt_type, local_orig);
 	} else {
 		struct net_bridge_port *p;
 
diff --git a/net/bridge/br_private.h b/net/bridge/br_private.h
index 239cf58d2268..a33da6e9765f 100644
--- a/net/bridge/br_private.h
+++ b/net/bridge/br_private.h
@@ -190,6 +190,17 @@ enum {
 	BR_VLFLAG_NEIGH_FORWARD_GRAT_ENABLED = BIT(6),
 };
 
+/* start publishing arrays when there're > BR_VLAN_PORT_ARRAY_THRESHOLD
+ * port-VLANs
+ */
+#define BR_VLAN_PORT_ARRAY_THRESHOLD 8
+
+struct net_bridge_vlan_port_array {
+	struct rcu_head		rcu;
+	unsigned int		count;
+	struct net_bridge_vlan	*vlans[];
+};
+
 /**
  * struct net_bridge_vlan - per-vlan entry
  *
@@ -210,6 +221,7 @@ enum {
  * @port_mcast_ctx: if MASTER flag unset, this is the per-port/vlan multicast
  *                  context
  * @msti: if MASTER flag set, this holds the VLANs MST instance
+ * @port_array: if MASTER flag set, this is the port-VLAN array
  * @port_vlist: if MASTER flag set, this is the port-VLAN list
  * @vlist: sorted list of VLAN entries
  * @rcu: used for entry destruction
@@ -245,6 +257,7 @@ struct net_bridge_vlan {
 
 	u16				msti;
 
+	struct net_bridge_vlan_port_array __rcu *port_array;
 	struct list_head		port_vlist;
 	struct list_head		vlist;
 
diff --git a/net/bridge/br_vlan.c b/net/bridge/br_vlan.c
index 34d1df59d190..d750581df64d 100644
--- a/net/bridge/br_vlan.c
+++ b/net/bridge/br_vlan.c
@@ -258,6 +258,36 @@ static void br_vlan_init_state(struct net_bridge_vlan *v)
 	v->msti = 0;
 }
 
+static unsigned int br_vlan_num_ports(const struct net_bridge_vlan *masterv)
+{
+	return refcount_read(&masterv->refcnt) - br_vlan_is_brentry(masterv);
+}
+
+static void br_vlan_rebuild_port_array(struct net_bridge_vlan *masterv,
+				       unsigned int count)
+{
+	struct net_bridge_vlan_port_array *array = NULL, *old;
+	unsigned int i = 0;
+
+	WARN_ON(!br_vlan_is_master(masterv));
+
+	if (count > BR_VLAN_PORT_ARRAY_THRESHOLD)
+		array = kvmalloc(struct_size(array, vlans, count), GFP_KERNEL);
+
+	if (array) {
+		struct net_bridge_vlan *pv;
+
+		array->count = count;
+		list_for_each_entry(pv, &masterv->port_vlist, port_vlist)
+			array->vlans[i++] = pv;
+	}
+
+	old = rtnl_dereference(masterv->port_array);
+	rcu_assign_pointer(masterv->port_array, array);
+	if (old)
+		kvfree_rcu(old, rcu);
+}
+
 /* This is the shared VLAN add function which works for both ports and bridge
  * devices. There are four possible calls to this function in terms of the
  * vlan entry type:
@@ -368,8 +398,10 @@ static int __vlan_add(struct net_bridge_vlan *v, u16 flags,
 	__vlan_flags_commit(v, flags);
 	br_multicast_toggle_one_vlan(v, true);
 
-	if (p)
+	if (p) {
+		br_vlan_rebuild_port_array(masterv, br_vlan_num_ports(masterv));
 		nbp_vlan_set_vlan_dev_state(p, v->vid);
+	}
 out:
 	return err;
 
@@ -438,6 +470,9 @@ static void __vlan_del(struct net_bridge_vlan *v)
 		rhashtable_remove_fast(&vg->vlan_hash, &v->vnode,
 				       br_vlan_rht_params);
 		__vlan_del_list(v);
+		/* -1 because br_vlan_put_master() is called later */
+		br_vlan_rebuild_port_array(masterv,
+					   br_vlan_num_ports(masterv) - 1);
 		nbp_vlan_set_vlan_dev_state(p, v->vid);
 		br_multicast_toggle_one_vlan(v, false);
 		br_multicast_port_ctx_deinit(&v->port_mcast_ctx);
-- 
2.47.3