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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 22 Jan 2013 09:31:43 -0500
From:	Vlad Yasevich <vyasevic@...hat.com>
To:	Shmulik Ladkani <shmulik.ladkani@...il.com>
CC:	bridge@...ts.linux-foundation.org,
	Stephen Hemminger <stephen@...workplumber.org>,
	Michał Mirosław <mirqus@...il.com>,
	netdev@...r.kernel.org, davem@...emloft.net, shemminger@...tta.com,
	mst@...hat.com
Subject: Re: [PATCH net-next V6 02/14] bridge: Add vlan filtering infrastructure

On 01/21/2013 06:45 AM, Shmulik Ladkani wrote:
> Hi Vlad,
>
> On Sun, 20 Jan 2013 20:50:59 -0500 Vlad Yasevich <vyasevic@...hat.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
>

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html