[ovs-dev] [ovs-discuss] [PATCH] datapath: Use hash table more tolerant of collisions for flow table.

Justin Pettit jpettit at nicira.com
Tue Sep 1 02:13:11 UTC 2009


On Aug 26, 2009, at 5:00 PM, Ben Pfaff wrote:

> 		/* Expand table, if necessary, to make room. */
> -		if (dp->n_flows * 4 >= table->n_buckets &&
> -		    table->n_buckets < DP_MAX_BUCKETS) {
> +		if (dp->n_flows >= table->n_buckets) {
> 			error = dp_table_expand(dp);

I don't see where the table size is bounded to DP_MAX_BUCKETS.  The  
check should probably be in that "if" statement, since if it were in  
dp_table_expand(), then the max number of flows would be equal to  
DP_MAX_BUCKETS.

> +int dp_table_insert(struct dp_table *table, struct sw_flow *target)

Any thoughts on making the new entry first instead of last, so it's  
found faster.  I guess the question is: Is a new flow or old flow more  
likely to be more active, since the timeouts are relatively short?

Would it make sense to make the buckets a bit larger, so an insertion  
is less expensive?  Would using a kmem_cache of a common size (maybe  
even one entry) make sense?  I suppose all of this may complicate  
things, since we're hoping collisions are rare.

> int dp_table_delete(struct dp_table *table, struct sw_flow *target)

Similar to insert, would it make sense to leave a few slots open so  
insertion is less expensive?

Otherwise, I think this commit looks great.

--Justin






More information about the dev mailing list