Hi Vlad,
On Sun, 20 Jan 2013 20:50:59 -0500 Vlad Yasevich <vyasevic@xxxxxxxxxx> 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
