Re: [RFC] alternative to conntrack ID

[Pablo Neira <pablo@eurodev.net>]

Hi Jozsef,

Jozsef Kadlecsik wrote:
>>Pablo Neira wrote:
>>
>>>All the things I've though so far are burned by something. The cleanest
>>>way to do this looks the ID. Any other ideas?
>>
>>Hm, this idea just came to my head. We could use a unsigned 8 bit
>>per-bucket-id [blah... blah... blah]
> 
> Let the id be at least unsigned 16 bit. No hash function can guarantee
> that a given bucket won't happen to grow above 256 entries.
> 
> How are you going to handle id collision due to wraparound?

yes, 8 bits is too short. About the wraparound problem, I'm planning to 
re-use id's. The id of a new conntrack will be set to the lastest 
inserted in the bucket plus one.

However this wouldn't uniquely identify a conntrack: Say a connection is 
established, lastest conntrack in the bucket uses id A, so its id will 
be set to A+1. After quite some time the connection is closed. Then, in 
a very short period of time, another connection with the same tuples is 
established and lastest conntrack id is still A, in that case the id of 
the new conntrack will be set to A+1 again.

To avoid that, I could keep an array of lastest id's released per bucket 
and set the id based on:

if (id_of_lastest_ct_inserted > lastest_id_released[bucket])
	id_of_lastest_ct_inserted + 1
else
	lastest_id_released[bucket] + 1;

About memory comsumption. On my laptop, ip_conntrack version 2.1 (1787 
buckets, 14296 max)

This approach:
1787 * 2 = 3574 extra bytes to store the lastest id used
14296 * 2 (extra bytes per conntrack) = 28592 extra bytes (worst case)

With regards to current u64 id approach:
28592 * 8 (extra bytes per conntrack) = 228736 extra bytes (worst case)

--
Pablo