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

[Thomas Gleixner <tglx@linutronix.de>]

On Fri, May 05 2023 at 16:50, Frederic Weisbecker wrote:
> On Tue, Apr 25, 2023 at 08:48:58PM +0200, Thomas Gleixner wrote:
>>  
>> -	do {
>> +	/* Can be written by a different task concurrently in the loop below */
>> +	start = READ_ONCE(sig->next_posix_timer_id);
>> +
>> +	for (id = ~start; start != id; id++) {
>>  		spin_lock(&hash_lock);
>> -		head = &posix_timers_hashtable[hash(sig, sig->posix_timer_id)];
>> -		if (!__posix_timers_find(head, sig, sig->posix_timer_id)) {
>> +		id = sig->next_posix_timer_id;
>> +
>> +		/* Write the next ID back. Clamp it to the positive space */
>> +		WRITE_ONCE(sig->next_posix_timer_id, (id + 1) & INT_MAX);
>
> Isn't that looping forever?

No. The loop breaks when @id reaches the locklessly read out @start
value again.

I admit that the 'id = ~start' part in the for() expression is confusing
without a comment. That initial @id value is in the invalid space to
make sure that the termination condition 'start != id' does not trigger
right away. But that value gets immediately overwritten after acquiring
hash_lock by the real sig->next_posix_timer_id value.

The clamp to the positive space has nothing to do with that. That's
required because the ID must be positive as a negative value would be an
error when returned, right?

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?

Admittedly this can be written less obscure, but not tonight :)

Thanks,

        tglx