On 01/20/2013 02:38 PM, Stephen Hemminger wrote:
On Sun, 20 Jan 2013 12:59:22 -0500
Vlad Yasevich <vyasevic@xxxxxxxxxx> wrote:
On 01/17/2013 08:57 PM, Michał Mirosław wrote:
2013/1/16 Vlad Yasevich <vyasevic@xxxxxxxxxx>:
[...]
--- /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
