RE: [RFD] posix-timers: CRIU woes

[David Laight]

From: Pavel Tikhomirov
> Sent: 10 May 2023 05:37
...
> >      A dense ID space approach can create holes too, but they are
> >      recoverable and well within the resource limits, because the process
> >      has to be able to create enough timers in the first place in order
> >      to release those in the middle.

While it doesn't help at all for creating items with fixed ids,
my 'favourite' scheme for allocating ids it to allocate a number
that will be a perfect hash onto an empty hash table slot.

The lookup check is then just array[id & mask].id == id.
A FIFO freelist can be run through the free entries and
the high bits incremented each time a slot is used.
So allocation is usually fixed cost.

If the table is full it's size can easily be doubled.
If the number of unused entries is doubled each time
the table size is doubled then the you (more or less)
guarantee that an id won't get reused any time soon
after it is freed.

This would be ok for restoring ids allocated by the same
scheme. But would need a fallback for restoring pathological
list of ids.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)