Re: [PATCH net-next V6 02/14] bridge: Add vlan filtering infrastructure

[Shmulik Ladkani <shmulik.ladkani@gmail.com>]

Hi Vlad,

On Sun, 20 Jan 2013 20:50:59 -0500 Vlad Yasevich <vyasevic@redhat.com> wrote:
> On 01/20/2013 02:38 PM, Stephen Hemminger wrote:
> > Let's assume the people that really want this feature are using a lot
> > of vlan's. i.e n = 1000 or so. A bitmap is O(1). Any hash list would
> > incur a just a big memory penalty for the list head. In other words
> > a full bitmap is 4096 bits = 512 bytes.  If you use hash list,
> > then the equivalent memory size would be only 64 list heads, therefore
> > a bitmap is a better choice than a hlist.
> >
> 
> This was the approach taken in the RFC v1 of this series.  What I found 
> was that while it worked very well as far as speed goes, it was a bit 
> cumbersome to extend it to support pvids and it would completely fall
> on its face for egress policy that Shmulik is suggesting.  So any kinds 
> of extensions to it were tough to do.

I don't see why this is the case.

How about (sketch only, names questionable...):

struct net_bridge {
+	unsigned long vlan_port_membership_bitmap[VLAN_N_VID][PORT_BITMAP_LEN];
+	unsigned long vlan_port_egress_policy_bitmap[VLAN_N_VID][PORT_BITMAP_LEN];
}

(can be alloc'ed instead of the arrays being part of the struct)

struct net_bridge_port {
+	u16 pvid;
};

Allows O(1) to the query "is port P member of vlan V".
Allows O(1) to the query "should vlan V egress tagged/untagged on port P".

I guess this might simplify the data structures involved, avoiding the
refcounts, etc...

The penaties are:
 - memory
 - aesthetics (?)
 - inefficient if query is "give me the entire list of VLANs port P is
   member of". But do we have such a query in bridge's code?

You say it went cumbersome. Am I missing something?

BTW, altenatively, you may:

struct net_bridge_port {
+	unsigned long vlan_membership_bitmap[BITS_TO_LONGS(VLAN_N_VID)];
+	unsigned long vlan_egress_policy_bitmap[BITS_TO_LONGS(VLAN_N_VID)];
+	u16 pvid;
};

Which also allows O(1) to "is port 'nbp' member of vlan V".

Difference:
- For the membership structure:
  former (within net_bridge) uses 4096 * BR_MAX_PORTS bits,
  latter (within net_bridge_port) uses NumOfNBPs * 4096 bits 
- better aesthetics (?)

Regards,
Shmulik