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

Frederic Weisbecker
2023-05-05T14:50:36Z

On Tue, Apr 25, 2023 at 08:48:58PM +0200, Thomas Gleixner wrote:
> posix_timer_add() tries to allocate a posix timer ID by starting from the
> cached ID which was stored by the last successful allocation.
>
> This is done in a loop searching the ID space for a free slot one by
> one. The loop has to terminate when the search wrapped around to the
> starting point.
>
> But that's racy vs. establishing the starting point. That is read out
> lockless, which leads to the following problem:
>
> CPU0 CPU1
> posix_timer_add()
> start = sig->posix_timer_id;
> lock(hash_lock);
> ... posix_timer_add()
> if (++sig->posix_timer_id < 0)
> start = sig->posix_timer_id;
> sig->posix_timer_id = 0;
>
> So CPU1 can observe a negative start value, i.e. -1, and the loop break
> never happens because the condition can never be true:
>
> if (sig->posix_timer_id == start)
> break;
>
> While this is unlikely to ever turn into an endless loop as the ID space is
> huge (INT_MAX), the racy read of the start value caught the attention of
> KCSAN and Dmitry unearthed that incorrectness.
>
> Rewrite it so that the start condition can never observe the negative value
> and annotate the read and the write with READ_ONCE()/WRITE_ONCE().
>
> Reported-by: syzbot+5c54bd3eb218bb595aa9@syzkaller.appspotmail.com
> Reported-by: Dmitry Vyukov <dvyukov@google.com>
> Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
> ---
> include/linux/sched/signal.h | 2 +-
> kernel/time/posix-timers.c | 30 +++++++++++++++++-------------
> 2 files changed, 18 insertions(+), 14 deletions(-)
>
> --- a/include/linux/sched/signal.h
> +++ b/include/linux/sched/signal.h
> @@ -135,7 +135,7 @@ struct signal_struct {
> #ifdef CONFIG_POSIX_TIMERS
>
> /* POSIX.1b Interval Timers */
> - int posix_timer_id;
> + unsigned int next_posix_timer_id;
> struct list_head posix_timers;
>
> /* ITIMER_REAL timer for the process */
> --- a/kernel/time/posix-timers.c
> +++ b/kernel/time/posix-timers.c
> @@ -140,25 +140,29 @@ static struct k_itimer *posix_timer_by_i
> static int posix_timer_add(struct k_itimer *timer)
> {
> struct signal_struct *sig = current->signal;
> - int first_free_id = sig->posix_timer_id;
> struct hlist_head *head;
> - int ret = -ENOENT;
> + unsigned int start, id;
>
> - 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?

Thanks.