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;
MIME-Version: 1.0
References: <20230425181827.219128101@linutronix.de> <20230425183312.932345089@linutronix.de>
 <ZFUXrCZtWyNG3Esi@lothringen> <87zg6i2xn3.ffs@tglx> <87v8h62vwp.ffs@tglx>
 <878rdy32ri.ffs@tglx> <87v8h126p2.ffs@tglx> <875y911xeg.ffs@tglx> <87ednpyyeo.ffs@tglx>
In-Reply-To: <87ednpyyeo.ffs@tglx>
From:   Andrey Vagin <avagin@openvz.org>
Date:   Wed, 10 May 2023 01:16:26 -0700
Message-ID: <CANaxB-wV9iUT6=Y9nZCWbJhiscMrnAQh4fUXs7Tb8pr=-HwSYQ@mail.gmail.com>
Subject: Re: [RFD] posix-timers: CRIU woes
To:     Thomas Gleixner <tglx@linutronix.de>
Cc:     Frederic Weisbecker <frederic@kernel.org>,
        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>,
        Christian Brauner <brauner@kernel.org>,
        Alexander Mikhalitsyn <aleksandr.mikhalitsyn@canonical.com>,
        Pavel Tikhomirov <ptikhomirov@virtuozzo.com>,
        Pavel Emelyanov <xemul@openvz.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8BIT
Precedence: bulk

On Tue, May 9, 2023 at 2:42 PM Thomas Gleixner <tglx@linutronix.de> wrote:
>
> Hi!
>
> This is a summary of several mails so that the CRIU people have the full
> picture.
>
> A recent syzbot report made me look at the timer ID management, which
> was modified 7 years ago to accomodate CRIU:
>
>     5ed67f05f66c ("posix timers: Allocate timer id per process (v2)")
>
> and introduced that reported issue along with a bogus loop termination
> problem. See
>
>     https://lore.kernel.org/lkml/000000000000a3723305f9d98fc3@google.com/
>     https://lore.kernel.org/lkml/20230425183312.932345089@linutronix.de
>
> for details.
>
> The intent to make the timer IDs per process is definitely correct, but
> the implementation is beyond suboptimal. I really regret that I did not
> catch this back then when picking those changes up.
>
> The way it works is that each process keeps a 'next_timer_id' which it
> uses to allocate the next timer. That allows CRIU to reconstruct timers
> with the same ID by walking the ID space via
>
>   do {
>      timer_create(&timer, ...., &id);
>      if (id == original_id)
>         goto success;
>      timer_delete(&timer);
>   } while (idspace_not_exhausted());
>
> That works by some definition of works, but it is problematic in two ways:
>
>  1) As the timer ID space is up to INT_MAX, a process which creates and
>     deletes timers frequently, can easily move up close to the INT_MAX
>     id space over time.
>
>     If such a process is checkpointed and restored, then the above loop
>     will run for at least an hour to restore a single timer.
>
>     And no, this is not only a hypothetical issue. There are legitimate
>     scenarios where threads are created and the control thread arms a
>     posix CPU timer on them. Such threads can be torn down on a regular
>     base due to thread pool consolidations. As CRIU does not happen
>     every 5 minutes it's not completely unlikely that such a process
>     surives quite some time on a particular host and thereby approaches
>     the ID space limit.
>
>     Sure we can restrict the ID space to a way smaller number so the
>     search wraps around earlier, but what's a sensible limit?
>
>     Though restricting the ID space has its own issue vs. backwards
>     compability. A process which created a timer on an older kernel with
>     an ID larger than the newer kernels ID limit cannot longer be
>     restored on that newer kernel.
>
>     Aside of that it does not solve the other problem this created:
>
>  2) That change created an user space ABI, which means that the kernel
>     side has to stick with this next ID search mechanism forever.
>
>     That prevents to get rid of that global lock and hash table by
>     sticking an xarray into task::signal which makes a lot of sense in
>     terms of cache locality and gets rid of the extra timer list
>     management in task::signal. Making this change would be very useful
>     to address some other issues in the posix-timer code without
>     creating yet more duct tape horrors.
>
>     Such a change obviously has to aim for a dense ID space to keep the
>     memory overhead low, but that breaks existing CRIU userspace because
>     dense ID space and next ID search does not fit together.
>
>     Next ID search is obviously creating non-recoverable holes in the
>     case that timers are deleted afterwards.
>
>     A dense ID space approach can create holes too, but they are
>     recoverable and well within the resource limits, because the process
>     has to be able to create enough timers in the first place in order
>     to release those in the middle.
>
>     With the next ID search brute force recovery is not possible on a
>     kernel with dense ID as there is no way to create all intermediate
>     timers first before reaching the one at the far end due to resource
>     limits.
>
> So because of that half thought out user space ABI we are now up the
> regression creek without a paddle, unless CRIU can accomodate to a
> different restore mechanism to lift this restriction from the kernel.
>
> Thoughts?

Hi Thomas,

If you give us a new API to create timers with specified id-s, we will
figure out how to live with it. It isn't good to ask users to update
CRIU to work on new kernels, but here are reasons and event improvements
for CRIU, so I think it's worth it.

As for API, we can use one bit of sigevent.sigev_notify to request a
timer with a specified id.

Thanks,
Andrei