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: <87zg6i2xn3.ffs@tglx>
References: <20230425181827.219128101@linutronix.de>
 <20230425183312.932345089@linutronix.de> <ZFUXrCZtWyNG3Esi@lothringen>
 <87zg6i2xn3.ffs@tglx>
Date:   Sat, 06 May 2023 01:36:22 +0200
Message-ID: <87v8h62vwp.ffs@tglx>
MIME-Version: 1.0
Content-Type: text/plain
Precedence: bulk

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'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.

Thanks,

        tglx