Make VLAN hash table fixed width

[cmiller_netapp.com]

Summary

There is a race that can happen between vlan_gethash and vlan_growhash that can result in vlan_gethash dereferencing a bad pointer.

This change increases the size of the hash table and makes it fixed so that there is no need for vlan_growhash, thus eliminating the race and also simplifying the code.

Performance testing showed that the maximum collision list of 16 resulted in no noticeable performance impact. However, this does increase the minimum number of hash buckets from 16 to 256.

Test Plan

Creation and deletion of VLAN interfaces.

[glebius]

Haven't yet looked in detail, but have a quick question. Did you try VLAN_ARRAY option? Many years ago we left it in assumption that in some cases a user may want a full array of VLANs. I wonder if it is still functioning, since it was never compiled by default or advertised.

[glebius]

sys/net/if_vlan.c

520

Yes, this doesn't look like a correct use of CK. I'm surprised the code arrives from Macy, who definitely knows how it works. Probably was doing a big sweeping change over the network stack and slipped through.

Chris, how do you test/reproduce this problem? I have better ideas on the fix rather than going with a static hash.

[kp]

I know there are users out there who run a very large number of vlans (>> 256) who might be affected by this. On the other hand, they ought to be using VLAN_ARRAY.

I'm tempted to suggest we should just make VLAN_ARRAY default, because it's not that much memory in the grand scheme of things, and it removes even more complexity.

[glebius]

Back then we added VLAN_ARRAY not to save memory (which sounds ridiculous today, but also was questionable in the 32-bit world), but to avoid cache misses in case if VLAN ids are selected with large gaps in their numbers.

[cmiller_netapp.com]

In D48896#1115702, @glebius wrote:

Haven't yet looked in detail, but have a quick question. Did you try VLAN_ARRAY option? Many years ago we left it in assumption that in some cases a user may want a full array of VLANs. I wonder if it is still functioning, since it was never compiled by default or advertised.

We did not try VLAN_ARRAY. We decided it was better to fix the broken code.

[cmiller_netapp.com]

In D48896#1115745, @kp wrote:

I know there are users out there who run a very large number of vlans (>> 256) who might be affected by this. On the other hand, they ought to be using VLAN_ARRAY.

I'm tempted to suggest we should just make VLAN_ARRAY default, because it's not that much memory in the grand scheme of things, and it removes even more complexity.

I think even with large numbers of VLANs the hash is still pretty performant.

[cmiller_netapp.com]

sys/net/if_vlan.c

520

It was reproduced by repeatedly adding and deleting VLANs to cause the hash to grow and shrink while running traffic on another VLAN.

[glebius]

sys/net/if_vlan.c

520

It was reproduced by repeatedly adding and deleting VLANs to cause the hash to grow and shrink while running traffic on another VLAN.

Sure, this is something obvious :) I was hoping may be you got a ready test case, that creates a vnet jail with epair(4) and bombs it with traffic and vlan reconfiguration requests. Such test would be helpful to exist inside the base system regression test suite.

[cmiller_netapp.com]

sys/net/if_vlan.c

520

No such luck on an automated test. I agree that would be a good test to add to the regression suite.

[cmiller_netapp.com]

What is needed to continue moving this forward?

[kp]

In D48896#1120826, @cmiller_netapp.com wrote:

What is needed to continue moving this forward?

I think it's acceptable as-is. We'll give Gleb a bit of time to respond and then we can push it in (absent objections, of course).

(An alternative to this might be to make the hash size a boot-time tunable. That'd avoid the race too, and give us more flexibility. I'm not sure it's worth it though.)

[glebius]

In D48896#1120826, @cmiller_netapp.com wrote:

What is needed to continue moving this forward?

This looks like a step back to me, to be fair. The resizing function is totally broken wrt the epoch, but it doesn't mean it cannot be implemented correctly. Ideally, we want a perfect hashing algorithm here, or a tree that is kept always balanced. Either solution would require proper pointer management on reconfiguration. I will try to come up with something. A good stressing script would be helpful though, as well as performance data on VLAN_ARRAY option.

[cmiller_netapp.com]

It probably can be implemented correctly, but I think it would require locking while the hash grows or shrinks. This change tries to strike a balance between the speed of VLAN_ARRAY and the memory savings of using the hash table, while avoiding the complexity associated with growing and shrinking the hash table. Growing and shrinking a hash table that can have a max 4096 entries just seems like overkill.

But like you said before Gleb, maybe the idea of saving the memory used by VLAN_ARRAY is silly these days.