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

[Vlad Yasevich <vyasevic@redhat.com>]

On 01/20/2013 02:38 PM, Stephen Hemminger wrote:
> On Sun, 20 Jan 2013 12:59:22 -0500
> Vlad Yasevich <vyasevic@redhat.com> wrote:
>
>> On 01/17/2013 08:57 PM, Michał Mirosław wrote:
>>> 2013/1/16 Vlad Yasevich <vyasevic@redhat.com>:
>>> [...]
>>>> --- /dev/null
>>>> +++ b/net/bridge/br_vlan.c
>>> [...]
>>>> +struct net_port_vlan *nbp_vlan_find(const struct net_port_vlans *v, u16 vid)
>>>> +{
>>>> +       struct net_port_vlan *pve;
>>>> +
>>>> +       /* Must be done either in rcu critical section or with RTNL held */
>>>> +       WARN_ON_ONCE(!rcu_read_lock_held() && !rtnl_is_locked());
>>>> +
>>>> +       list_for_each_entry_rcu(pve, &v->vlan_list, list) {
>>>> +               if (pve->vid == vid)
>>>> +                       return pve;
>>>> +       }
>>>> +
>>>> +       return NULL;
>>>> +}
>>>
>>> This looks expensive - it's O(n) with n = number of configured VLANs on a port.
>>> And this is called for every packet. The bridge already has a hash of VLAN
>>> structures found by br_vlan_find(). You could add a second bitmap there
>>> (eg. ingres_ports[]) and check port's bit instead of walking the list.
>>> You would use a bit more memory (64 bytes minus the removed list-head)
>>> per configured VLAN but save some cycles in hot path.
>>>
>>
>> Technically wouldn't even need another bitmap as an existing membership
>> bitmap would cover this case.  I did some profiling and the list is
>> faster for 3 vlans per port.  Hash is faster for more then 3 vlans.
>>
>> I can easily switch to hash if that is what others think.
>>
>> -vlad
>
> 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.

This is why I went with the list.  Interestingly enough, VLAN 
implementation in the kernel is a list and noone is complaining that it 
is really slow on the fast path.

-vlad