Re: [patch 02/20] posix-timers: Ensure timer ID search-loop limit is valid

Frederic Weisbecker
2023-05-09T09:42:35Z

On Sat, May 06, 2023 at 01:36:22AM +0200, Thomas Gleixner wrote:
> On Sat, May 06 2023 at 00:58, Thomas Gleixner wrote:
> > On Fri, May 05 2023 at 16:50, Frederic Weisbecker wrote:
> > So the whole thing works like this:
> >
> > start = READ_LOCKLESS(sig->next_id);
> >
> > // Enfore that id and start are different to not terminate right away
> > id = ~start;
> >
> > loop:
> > if (id == start)
> > goto fail;
> > lock()
> > id = sig->next_id; <-- stable readout
> > sig->next_id = (id + 1) & INT_MAX; <-- prevent going negative
> >
> > if (unused_id(id)) {
> > add_timer_to_hash(timer, id);
> > unlock();
> > return id;
> > }
> > id++;
> > unlock();
> > goto loop;
> >
> > As the initial lockless readout is guaranteed to be in the positive
> > space, how is that supposed to be looping forever?
>
> Unless you think about the theoretical case of an unlimited number of
> threads sharing the signal_struct which all concurrently try to allocate
> a timer id and then releasing it immediately again (to avoid resource
> limit exhaustion). Theoretically possible, but is this a real concern
> with a timer ID space of 2G?

I didn't go that far actually, it was just me misunderstanding that loop and
especially the (id =~start) part. Now I got it.

I guess the for statement can just be:

for (; start != id; id++)

>
> I'm sure that it's incredibly hard to exploit this, but what's really
> bothering me is the hash table itself. The only reason why we have that
> is CRIU.
>
> The only alternative solution I could come up with is a paritioned
> xarray where the index space would be segmented for each TGID, i.e.
>
> segment.start = TGID * MAX_TIMERS_PER_PROCESS
> segment.end = segment.start + MAX_TIMERS_PER_PROCESS - 1
>
> where MAX_TIMERS_PER_PROCESS could be a copius 2^16 which would work for
> both 32bit and 64bit TID limits.
>
> That would avoid the hash table lookups and the related issues, but OTH
> it would require to allocate one extra page per TGID if the application
> uses a single posix timer.
>
> Not sure whether that's worth it though.

Not sure either...

Thanks.