Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Thomas Gleixner <tglx@linutronix.de>
To:     Frederic Weisbecker <frederic@kernel.org>
Cc:     LKML <linux-kernel@vger.kernel.org>,
        Anna-Maria Behnsen <anna-maria@linutronix.de>,
        Peter Zijlstra <peterz@infradead.org>,
        syzbot+5c54bd3eb218bb595aa9@syzkaller.appspotmail.com,
        Dmitry Vyukov <dvyukov@google.com>,
        Sebastian Siewior <bigeasy@linutronix.de>,
        Michael Kerrisk <mtk.manpages@gmail.com>
Subject: Re: [patch 02/20] posix-timers: Ensure timer ID search-loop limit
 is valid
In-Reply-To: <ZFUXrCZtWyNG3Esi@lothringen>
References: <20230425181827.219128101@linutronix.de>
 <20230425183312.932345089@linutronix.de> <ZFUXrCZtWyNG3Esi@lothringen>
Date:   Sat, 06 May 2023 00:58:56 +0200
Message-ID: <87zg6i2xn3.ffs@tglx>
MIME-Version: 1.0
Content-Type: text/plain
Precedence: bulk

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