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]

Message-ID: <20130121134534.78032a54.shmulik.ladkani@gmail.com>
Date:	Mon, 21 Jan 2013 13:45:34 +0200
From:	Shmulik Ladkani <shmulik.ladkani@...il.com>
To:	vyasevic@...hat.com, bridge@...ts.linux-foundation.org
Cc:	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

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?

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