posix-timers: Fixes and cleanups

itimer_delete() has a retry loop when the timer is concurrently expired. On non-RT kernels this just spin-waits until the timer callback has completed. On RT kernels this is a potential livelock when the exiting task preempted the hrtimer soft interrupt.

This only affects hrtimer based timers as Posix CPU timers cannot be concurrently expired. For CONFIG_POSIX_CPU_TIMERS_TASK_WORK=y this is obviously impossible as the task cannot run task work and exit at the same time. The CONFIG_POSIX_CPU_TIMERS_TASK_WORK=n (only non-RT) is prevented because interrupts are disabled.

Quoted 10 lines · Thomas Gleixner

itimer_delete() has a retry loop when the timer is concurrently expired. On non-RT kernels this just spin-waits until the timer callback has completed. On RT kernels this is a potential livelock when the exiting task preempted the hrtimer soft interrupt.

This only affects hrtimer based timers as Posix CPU timers cannot be concurrently expired. For CONFIG_POSIX_CPU_TIMERS_TASK_WORK=y this is obviously impossible as the task cannot run task work and exit at the same time. The CONFIG_POSIX_CPU_TIMERS_TASK_WORK=n (only non-RT) is prevented because interrupts are disabled.

But the owner of the timer is not the same as the target of the timer, right?

Though I seem to remember that we forbid setting a timer to a target outside the current process, in which case the owner and the target are the same at this exit stage. But I can't remember what enforces that permission in pid_for_clock()..

Quoted 12 lines · Frederic Weisbecker

Quoted 10 lines · Thomas Gleixner

itimer_delete() has a retry loop when the timer is concurrently expired. On non-RT kernels this just spin-waits until the timer callback has completed. On RT kernels this is a potential livelock when the exiting task preempted the hrtimer soft interrupt.

This only affects hrtimer based timers as Posix CPU timers cannot be concurrently expired. For CONFIG_POSIX_CPU_TIMERS_TASK_WORK=y this is obviously impossible as the task cannot run task work and exit at the same time. The CONFIG_POSIX_CPU_TIMERS_TASK_WORK=n (only non-RT) is prevented because interrupts are disabled.

Quoted 6 lines

But the owner of the timer is not the same as the target of the timer, right?

Though I seem to remember that we forbid setting a timer to a target outside the current process, in which case the owner and the target are the same at this exit stage. But I can't remember what enforces that permission in pid_for_clock()..

The owner of the timer is always the one which needs to find the entity to synchronize on, whether that's the right hrtimer base or the task which runs the expiry code.

wait_for_running_timer() is taking that into account:

- The hrtimer timer based posix timers lock the hrtimer base expiry lock on the base to which the timer is currently associated

- Posix CPU timers can be armed on a differnet process (only per thread timers are restricted to currents threadgroup) but the wait_for_running() callback "knows" how to find that process:

When the timer is moved to the expiry list it gets:

cputimer->firing = 1; rcu_assign_pointer(ctmr->handling, current);

and the wait for running side does:

       rcu_read_lock()
       tsk = rcu_dereference(timr->it.cpu.handling);
       ....
       mutex_lock(&tsk->posix_cputimers_work.mutex);

See collect_timerqueue(), handle_posix_cpu_timers() and posix_cpu_timer_wait_running() for details.

commit f7abf14f0001 ("posix-cpu-timers: Implement the missing timer_wait_running callback") has quite some prose in the changelog.

itimer_delete() has a retry loop when the timer is concurrently expired. On non-RT kernels this just spin-waits until the timer callback has completed. On RT kernels this is a potential livelock when the exiting task preempted the hrtimer soft interrupt.

Replace spin_unlock() with an invocation of timer_wait_running() to handle it the same way as the other retry loops in the posix timer code.

Fixes ec8f954a40da ("posix-timers: Use a callback for cancel synchronization on PREEMPT_RT")

Signed-off-by Thomas Gleixner <[email protected]>

---

V2:  Remove bogus comments vs. posix CPU timers - Frederic
V2a: Send the real fixed up version
---
 kernel/time/posix-timers.c |   43 +++++++++++++++++++++++++++++++++++--------
 1 file changed, 35 insertions(+), 8 deletions(-)

kernel/time/posix-timers.c +10 -3

@@ -1037,27 +1037,52 @@ SYSCALL_DEFINE1(timer_delete, timer_t, t
 }
 
 /*
- * return timer owned by the process, used by exit_itimers
+ * Delete a timer if it is armed, remove it from the hash and schedule it
+ * for RCU freeing.
  */
 static void itimer_delete(struct k_itimer *timer)
 {
-retry_delete:
-	spin_lock_irq(&timer->it_lock);
+	unsigned long flags;
 
+retry_delete:
+	/*
+	 * irqsave is required to make timer_wait_running() work.
+	 */
+	spin_lock_irqsave(&timer->it_lock, flags);
+
+	/*

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 [email protected]

Reported-by Dmitry Vyukov <[email protected]>

Signed-off-by Thomas Gleixner <[email protected]>

---
 include/linux/sched/signal.h |    2 +-
 kernel/time/posix-timers.c   |   30 +++++++++++++++++-------------
 2 files changed, 18 insertions(+), 14 deletions(-)

include/linux/sched/signal.h +1 -1

@@ -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 */

kernel/time/posix-timers.c +2 -3

@@ -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 */

kernel/time/posix-timers.c static struct k_itimer *posix_timer_by_i · line 154

Quoted 13 lines · Thomas Gleixner

kernel/time/posix-timers.c +8 -3

-	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?

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?

Quoted 3 lines · Thomas Gleixner

On Fri, May 05 2023 at 16:50, Frederic Weisbecker wrote:
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?

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.

Quoted 13 lines · Thomas Gleixner

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.

Quoted 1 line

Not sure whether that's worth it though.

More thoughts on this. If we go there and accept the extra page of memory then we can just go all the way and make the xarray per process, actually per signal.

Quoted 3 lines · Thomas Gleixner

More thoughts on this. If we go there and accept the extra page of memory then we can just go all the way and make the xarray per process, actually per signal.

Thinking more about it. The current scheme how timer ID allocation works is really interesting vs. CRIU.

Assume a process creates/deletes timers frequently. It's not hard to move the next ID close to INT_MAX, i.e. 2G

Now checkpoint that thing and restore it which means to do the create/delete dance to move next ID up to the last one-1. Will only take a couple of hours....

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/[email protected]/
     https://lore.kernel.org/lkml/[email protected]

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?

Thanks,

tglx

Quoted 5 lines · Thomas Gleixner

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?

Maybe we can do something similar to /proc/sys/kernel/ns_last_pid? Switch to per-(process->signal) idr based approach with idr_set_cursor to set next id for next posix timer from new sysctl?

Pavel!

Quoted 5 lines · Pavel Tikhomirov

Quoted 4 lines · Thomas Gleixner

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.

Quoted 5 lines

Quoted 1 line

Thoughts?

Maybe we can do something similar to /proc/sys/kernel/ns_last_pid? Switch to per-(process->signal) idr based approach with idr_set_cursor to set next id for next posix timer from new sysctl?

I'm not a fan of such sysctls. We have already too many of them and that particular one does not buy much.

We can simply let timer_create() or a new syscall create a timer at a given ID.

That allows CRIU to restore any checkpointed process no matter which kernel version it came from without doing this insane create/delete dance.

The downside is that this allows to create stupidly sparse timer IDs even for the non CRIU case, which increases per process kernel memory consumption and creates slightly more overhead in the signal delivery path. The latter is a burden on the process owning the timer and not affecting expiry, which is a context stealing operation. The memory part needs eventually some thoughts vs. accounting.

If the 'explicit at ID' option is not used then the ID mechanism is optimzied for dense IDs by using the first available ID in a bottom up search, which recovers holes created by a timer_delete() operation.

Thanks,

tglx

Not sure how kernel memory consumption increases with sparse timer IDs, global hashtable (posix_timers_hashtable) is the same size anyway, entries in hlists can be distributed differently as hash depends on id directly but we have same number of entries. Probably I miss something, why do we need dense IDs?

Quoted 10 lines · Thomas Gleixner

The downside is that this allows to create stupidly sparse timer IDs even for the non CRIU case, which increases per process kernel memory consumption and creates slightly more overhead in the signal delivery path. The latter is a burden on the process owning the timer and not affecting expiry, which is a context stealing operation. The memory part needs eventually some thoughts vs. accounting.

If the 'explicit at ID' option is not used then the ID mechanism is optimzied for dense IDs by using the first available ID in a bottom up search, which recovers holes created by a timer_delete() operation.

Not sure how kernel memory consumption increases with sparse timer IDs, global hashtable (posix_timers_hashtable) is the same size anyway, entries in hlists can be distributed differently as hash depends on id directly but we have same number of entries. Probably I miss something, why do we need dense IDs?

Sent: 10 May 2023 05:37

Quoted 4 lines

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.

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/[email protected]/
    https://lore.kernel.org/lkml/[email protected]

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?

Quoted 92 lines · Thomas Gleixner

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/[email protected]/
     https://lore.kernel.org/lkml/[email protected]

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.

Quoted 1 line

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

Quoted 5 lines · Andrey Vagin

Quoted 5 lines

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.

Quoted 4 lines

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.

I agree, any API to create timers with specified id-s would work for new CRIU versions.

Quoted 11 lines · Pavel Tikhomirov

Quoted 9 lines · Andrey Vagin

Quoted 5 lines

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.

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.

Quoted 2 lines

I agree, any API to create timers with specified id-s would work for new CRIU versions.

The real question is whether this will cause any upheaval when a new kernel meets a non-updated CRIU stack.

You know the UABI regression rules of the kernel...

Thanks,

tglx

Quoted 15 lines · Thomas Gleixner

Quoted 13 lines · Pavel Tikhomirov

Quoted 9 lines · Andrey Vagin

Quoted 5 lines

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.

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.

I agree, any API to create timers with specified id-s would work for new CRIU versions.

Quoted 2 lines

The real question is whether this will cause any upheaval when a new kernel meets a non-updated CRIU stack.

Creation of posix timer would hang forever in this loop
https://github.com/checkpoint-restore/criu/blob/33dd66c6fc93c47213aaa0447a94d97ba1fa56ba/criu/pie/restorer.c#L1185
if old criu is run on new kernel (without consecutive id allocation) AFAICS.

Quoted 16 lines · Pavel Tikhomirov

Quoted 15 lines · Thomas Gleixner

Quoted 13 lines · Pavel Tikhomirov

Quoted 9 lines · Andrey Vagin

Quoted 5 lines

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.

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.

I agree, any API to create timers with specified id-s would work for new CRIU versions.

Quoted 6 lines

Quoted 2 lines

The real question is whether this will cause any upheaval when a new kernel meets a non-updated CRIU stack.

Creation of posix timer would hang forever in this loop
https://github.com/checkpoint-restore/criu/blob/33dd66c6fc93c47213aaa0447a94d97ba1fa56ba/criu/pie/restorer.c#L1185
if old criu is run on new kernel (without consecutive id allocation) AFAICS.

Yes, because that "sanity" check

      if ((long)next_id > args->posix_timers[i].spt.it_id)

which tries to establish whether the kernel provides timer IDs in strict increasing order does not work for that case.

It "works" to detect the IDR case on older kernels by chance, but not under all circumstances. Assume the following case:

Global IDR has a free slot at index 1

Restore tries to create a timer for index 2

That will also loop forever, unless some other process creates a timer and occupies the free slot at index 1, right?

So this needs a fix anyway, which should be done so that the new kernel case is at least properly detected.

But even then there is still the problem of "it worked before I upgraded the kernel".

IOW, we are still up a creek without a paddle, unless you would be willing to utilize the existing CRIU bug to distribute the 'deal with new kernel' mechanics as a bug bounty :) >
Fix for the loop termination below.

Thanks,

tglx

---
  criu/pie/restorer.c |   24 +++++++++++++-----------
  1 file changed, 13 insertions(+), 11 deletions(-)

criu/pie/restorer.c +13 -11

@@ -1169,10 +1169,10 @@ static int timerfd_arm(struct task_resto
  static int create_posix_timers(struct task_restore_args *args)
  {
  	int ret, i;
-	kernel_timer_t next_id;
+	kernel_timer_t next_id, timer_id;
  	struct sigevent sev;
 
-	for (i = 0; i < args->posix_timers_n; i++) {
+	for (i = 0, next_id = 0; i < args->posix_timers_n; i++) {
  		sev.sigev_notify = args->posix_timers[i].spt.it_sigev_notify;
  		sev.sigev_signo = args->posix_timers[i].spt.si_signo;
  #ifdef __GLIBC__

@@ -1183,25 +1183,27 @@ static int create_posix_timers(struct ta
  		sev.sigev_value.sival_ptr = args->posix_timers[i].spt.sival_ptr;
 
  		while (1) {
-			ret = sys_timer_create(args->posix_timers[i].spt.clock_id, &sev, &next_id);
+			ret = sys_timer_create(args->posix_timers[i].spt.clock_id, &sev, &timer_id);
  			if (ret < 0) {
  				pr_err("Can't create posix timer - %d\n", i);
  				return ret;
  			}
 
-			if (next_id == args->posix_timers[i].spt.it_id)
+			if (timer_id != next_id) {
+				pr_err("Can't create timers, kernel don't give them consequently\n");
+				return -1;
+			}
+
+			next_id++;
+
+			if (timer_id == args->posix_timers[i].spt.it_id)
  				break;
 
-			ret = sys_timer_delete(next_id);
+			ret = sys_timer_delete(timer_id);
  			if (ret < 0) {
-				pr_err("Can't remove temporaty posix timer 0x%x\n", next_id);
+				pr_err("Can't remove temporaty posix timer 0x%x\n", timer_id);
  				return ret;
  			}
-
-			if ((long)next_id > args->posix_timers[i].spt.it_id) {
-				pr_err("Can't create timers, kernel don't give them consequently\n");
-				return -1;
-			}
  		}
  	}
 

Quoted 16 lines · Pavel Tikhomirov

Quoted 15 lines · Thomas Gleixner

Quoted 13 lines · Pavel Tikhomirov

Quoted 9 lines · Andrey Vagin

Quoted 5 lines

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.

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.

I agree, any API to create timers with specified id-s would work for new CRIU versions.

Quoted 6 lines

Quoted 2 lines

The real question is whether this will cause any upheaval when a new kernel meets a non-updated CRIU stack.

Creation of posix timer would hang forever in this loop
https://github.com/checkpoint-restore/criu/blob/33dd66c6fc93c47213aaa0447a94d97ba1fa56ba/criu/pie/restorer.c#L1185
if old criu is run on new kernel (without consecutive id allocation) AFAICS.

Yes, because that "sanity" check

      if ((long)next_id > args->posix_timers[i].spt.it_id)

which tries to establish whether the kernel provides timer IDs in strict increasing order does not work for that case.

It "works" to detect the IDR case on older kernels by chance, but not under all circumstances. Assume the following case:

Global IDR has a free slot at index 1

Restore tries to create a timer for index 2

That will also loop forever, unless some other process creates a timer and occupies the free slot at index 1, right?

So this needs a fix anyway, which should be done so that the new kernel case is at least properly detected.

But even then there is still the problem of "it worked before I upgraded the kernel".

IOW, we are still up a creek without a paddle, unless you would be willing to utilize the existing CRIU bug to distribute the 'deal with new kernel' mechanics as a bug bounty :)

Fix for the loop termination below.

Thanks,

tglx

---
  criu/pie/restorer.c |   24 +++++++++++++-----------
  1 file changed, 13 insertions(+), 11 deletions(-)

criu/pie/restorer.c +13 -11

@@ -1169,10 +1169,10 @@ static int timerfd_arm(struct task_resto
  static int create_posix_timers(struct task_restore_args *args)
  {
  	int ret, i;
-	kernel_timer_t next_id;
+	kernel_timer_t next_id, timer_id;
  	struct sigevent sev;
 
-	for (i = 0; i < args->posix_timers_n; i++) {
+	for (i = 0, next_id = 0; i < args->posix_timers_n; i++) {
  		sev.sigev_notify = args->posix_timers[i].spt.it_sigev_notify;
  		sev.sigev_signo = args->posix_timers[i].spt.si_signo;
  #ifdef __GLIBC__

@@ -1183,25 +1183,27 @@ static int create_posix_timers(struct ta
  		sev.sigev_value.sival_ptr = args->posix_timers[i].spt.sival_ptr;
 
  		while (1) {
-			ret = sys_timer_create(args->posix_timers[i].spt.clock_id, &sev, &next_id);
+			ret = sys_timer_create(args->posix_timers[i].spt.clock_id, &sev, &timer_id);
  			if (ret < 0) {
  				pr_err("Can't create posix timer - %d\n", i);
  				return ret;
  			}
 
-			if (next_id == args->posix_timers[i].spt.it_id)
+			if (timer_id != next_id) {
+				pr_err("Can't create timers, kernel don't give them consequently\n");
+				return -1;
+			}
+
+			next_id++;
+
+			if (timer_id == args->posix_timers[i].spt.it_id)
  				break;
 
-			ret = sys_timer_delete(next_id);
+			ret = sys_timer_delete(timer_id);
  			if (ret < 0) {
-				pr_err("Can't remove temporaty posix timer 0x%x\n", next_id);
+				pr_err("Can't remove temporaty posix timer 0x%x\n", timer_id);
  				return ret;
  			}
-
-			if ((long)next_id > args->posix_timers[i].spt.it_id) {
-				pr_err("Can't create timers, kernel don't give them consequently\n");
-				return -1;
-			}
  		}
  	}
 

Quoted 11 lines · Pavel Tikhomirov

Quoted 9 lines · Andrey Vagin

Quoted 5 lines

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.

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.

Quoted 2 lines

I agree, any API to create timers with specified id-s would work for new CRIU versions.

The real question is whether this will cause any upheaval when a new kernel meets a non-updated CRIU stack.

You know the UABI regression rules of the kernel...

Quoted 2 lines · Thomas Gleixner

You know the UABI regression rules of the kernel...

There is no rule without exceptions... With all pros and cons, we may consider this case as an exception. From our side, we will try to make everything to minimize the impact. Here are steps off the top of my head:
* releasing the criu fix before the kernel release.
* update packages in Linux distros (Debian, Ubuntu, Fedora, and others that we will find).
* send an announcement to the criu mailing list and to users that we know.
* add the error to FAQ.
* create a GitHub issue with a full description.

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.

Quoted 8 lines · Thomas Gleixner

Quoted 3 lines · Thomas Gleixner

More thoughts on this. If we go there and accept the extra page of memory then we can just go all the way and make the xarray per process, actually per signal.

Thinking more about it. The current scheme how timer ID allocation works is really interesting vs. CRIU.

Quoted 6 lines

Assume a process creates/deletes timers frequently. It's not hard to move the next ID close to INT_MAX, i.e. 2G

Now checkpoint that thing and restore it which means to do the create/delete dance to move next ID up to the last one-1. Will only take a couple of hours....

I'm cursing myself for overlooking this back then when the CRIU changes to the timer ID management were made. Why?

Because that created an ABI which CRIU relies on.

The proper solution for this would be to make it possible to create a timer with a given ID. That's not rocket science, but we need buy in from the CRIU folks. Otherwise we are up the regression creek without a paddle.

Quoted 24 lines · Thomas Gleixner

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;

Quoted 2 lines

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.

Quoted 5 lines · Thomas Gleixner

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.

Not sure either...

Quoted 5 lines · Thomas Gleixner

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 didn't go that far actually, it was just me misunderstanding that loop and especially the (id =~start) part. Now I got it.

I guess the for statement can just be:

for (; start != id; id++)

Quoted 10 lines · Frederic Weisbecker

Quoted 5 lines · Thomas Gleixner

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 didn't go that far actually, it was just me misunderstanding that loop and especially the (id =~start) part. Now I got it.

Quoted 3 lines

I guess the for statement can just be:

for (; start != id; id++)

My brain based compiler complains about uninitialized usage of @id. I'm pretty sure it's rightfully complaining and a real compiler would agree, no?

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 all id operations are under the hash lock.

Reported-by [email protected]

Reported-by Dmitry Vyukov <[email protected]>

Signed-off-by Thomas Gleixner <[email protected]>

Explain it better and add the CONFIG_POSIX_CPU_TIMERS_TASK_WORK=y aspect for completeness.

Signed-off-by Thomas Gleixner <[email protected]>

Describe the hash table properly and remove the IDR leftover comments.

Signed-off-by Thomas Gleixner <[email protected]>

Document how the timer ID validation in the hash table works.

Signed-off-by Thomas Gleixner <[email protected]>

k_itimer::it_signal is read lockless in the RCU protected hash lookup, but it can be written concurrently in the timer_create() and timer_delete() path. Annotate these places with READ_ONCE() and WRITE_ONCE()

Signed-off-by Thomas Gleixner <[email protected]>

Technically it's not required to set k_itimer::it_signal to NULL on exit() because there is no other thread anymore which could lookup the timer concurrently.

Set it to NULL for consistency sake and add a comment to that effect.

Signed-off-by Thomas Gleixner <[email protected]>

All usage of hash_lock is in thread context. No point in using spin_lock_irqsave()/irqrestore() for a single usage site.

Signed-off-by Thomas Gleixner <[email protected]>

release_posix_timers() is called for cleaning up both hashed and unhashed timers. The cases are differentiated by an argument and the usage is hideous.

Seperate the actual free path out and use it for unhashed timers. Provide a function for hashed timers.

No functional change.

Signed-off-by Thomas Gleixner <[email protected]>

+/**
+ * sys_clock_getres - Get the resolution of a clock
+ * @which_clock: The clock to get the resolution for
+ * @tp: Pointer to a a user space timespec64 for storage