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

[Vlad Yasevich <vyasevic@redhat.com>]

On 01/21/2013 06:45 AM, Shmulik Ladkani wrote:
> 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?

Yes.  When a mac address is added to a port without an explicit vlan tag 
we try to add it for every vlan available on the port.

Also, in the API, the user may request vlans configured on a port.

>
> 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".
>

This is what the earlier RFC patches did.  You are paying a large memory 
penalty and carrying a mostly empty bitmap when only a small number of 
vlans is used.

If someone decides that they'd like priority support, you'd need another 
array or list to hold priority values.

-vlad

> 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
>