From: David Laight <David.Laight@ACULAB.COM>
To: 'Pavel Tikhomirov' <ptikhomirov@virtuozzo.com>,
Thomas Gleixner <tglx@linutronix.de>,
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"
<syzbot+5c54bd3eb218bb595aa9@syzkaller.appspotmail.com>,
Dmitry Vyukov <dvyukov@google.com>,
Sebastian Siewior <bigeasy@linutronix.de>,
"Michael Kerrisk" <mtk.manpages@gmail.com>,
Andrei Vagin <avagin@openvz.org>,
"Christian Brauner" <brauner@kernel.org>,
Alexander Mikhalitsyn <aleksandr.mikhalitsyn@canonical.com>,
Pavel Emelyanov <xemul@openvz.org>
Subject: RE: [RFD] posix-timers: CRIU woes
Date: Thu, 11 May 2023 10:13:20 +0000 [thread overview]
Message-ID: <8a42097629844e5eacf733328eac2d02@AcuMS.aculab.com> (raw)
In-Reply-To: <009e7658-1377-cc79-7a42-4dda8fec5af0@virtuozzo.com>
From: Pavel Tikhomirov
> Sent: 10 May 2023 05:37
...
> > 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.
While it doesn't help at all for creating items with fixed ids,
my 'favourite' scheme for allocating ids it to allocate a number
that will be a perfect hash onto an empty hash table slot.
The lookup check is then just array[id & mask].id == id.
A FIFO freelist can be run through the free entries and
the high bits incremented each time a slot is used.
So allocation is usually fixed cost.
If the table is full it's size can easily be doubled.
If the number of unused entries is doubled each time
the table size is doubled then the you (more or less)
guarantee that an id won't get reused any time soon
after it is freed.
This would be ok for restoring ids allocated by the same
scheme. But would need a fallback for restoring pathological
list of ids.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
next prev parent reply other threads:[~2023-05-11 10:13 UTC|newest]
Thread overview: 122+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-04-25 18:48 [patch 00/20] posix-timers: Fixes and cleanups Thomas Gleixner
2023-04-25 18:48 ` [patch 01/20] posix-timers: Prevent RT livelock in itimer_delete() Thomas Gleixner
2023-05-04 17:06 ` Frederic Weisbecker
2023-05-04 18:20 ` Thomas Gleixner
2023-05-05 7:57 ` Thomas Gleixner
2023-06-01 19:00 ` [patch v2 " Thomas Gleixner
2023-06-01 20:16 ` [patch v2a " Thomas Gleixner
2023-06-05 10:59 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:48 ` [patch 02/20] posix-timers: Ensure timer ID search-loop limit is valid Thomas Gleixner
2023-05-05 14:50 ` Frederic Weisbecker
2023-05-05 22:58 ` Thomas Gleixner
2023-05-05 23:36 ` Thomas Gleixner
2023-05-08 21:57 ` Thomas Gleixner
2023-05-09 9:30 ` Thomas Gleixner
2023-05-09 12:50 ` Thomas Gleixner
2023-05-09 21:42 ` [RFD] posix-timers: CRIU woes Thomas Gleixner
2023-05-10 4:36 ` Pavel Tikhomirov
2023-05-10 8:30 ` Thomas Gleixner
2023-05-11 4:12 ` Pavel Tikhomirov
2023-05-11 7:56 ` Peter Zijlstra
2023-05-11 9:32 ` Thomas Gleixner
2023-05-11 10:13 ` David Laight [this message]
2023-05-10 8:16 ` Andrey Vagin
2023-05-11 3:17 ` Pavel Tikhomirov
2023-05-11 9:36 ` Thomas Gleixner
2023-05-11 9:52 ` Pavel Tikhomirov
2023-05-11 13:42 ` Thomas Gleixner
2023-05-11 14:54 ` Pavel Tikhomirov
2023-05-11 15:25 ` Pavel Tikhomirov
2023-05-12 1:21 ` Andrey Vagin
2023-05-31 17:38 ` Thomas Gleixner
2023-05-11 7:49 ` Cyrill Gorcunov
2023-05-10 0:42 ` [patch 02/20] posix-timers: Ensure timer ID search-loop limit is valid Andrey Vagin
2023-05-09 9:42 ` Frederic Weisbecker
2023-05-09 12:04 ` Thomas Gleixner
2023-05-09 12:38 ` Thomas Gleixner
2023-05-09 14:18 ` Frederic Weisbecker
2023-06-01 18:58 ` [patch v2 " Thomas Gleixner
2023-06-05 14:17 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 03/20] posix-timers: Clarify timer_wait_running() comment Thomas Gleixner
2023-05-09 9:50 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 04/20] posix-timers: Cleanup comments about timer ID tracking Thomas Gleixner
2023-05-09 9:58 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 05/20] posix-timers: Add comments about timer lookup Thomas Gleixner
2023-05-09 10:58 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 06/20] posix-timers: Annotate concurrent access to k_itimer::it_signal Thomas Gleixner
2023-05-09 11:04 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] posix-timers: Annotate concurrent access to k_itimer:: It_signal tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 07/20] posix-timers: Set k_itimer::it_signal to NULL on exit() Thomas Gleixner
2023-06-01 10:09 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] posix-timers: Set k_itimer:: It_signal " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 08/20] posix-timers: Remove pointless irqsafe from hash_lock Thomas Gleixner
2023-06-01 10:12 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 09/20] posix-timers: Split release_posix_timers() Thomas Gleixner
2023-06-01 10:25 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 10/20] posix-timers: Document sys_clock_getres() correctly Thomas Gleixner
2023-06-01 10:44 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 11/20] posix-timers: Document common_clock_get() correctly Thomas Gleixner
2023-06-01 11:00 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 12/20] posix-timers: Document sys_clock_getoverrun() Thomas Gleixner
2023-06-01 11:06 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 13/20] posix-timers: Document sys_clock_settime() permissions in place Thomas Gleixner
2023-06-01 11:22 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:50 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 14/20] posix-timers: Document nanosleep() details Thomas Gleixner
2023-06-01 12:30 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:49 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 15/20] posix-timers: Add proper comments in do_timer_create() Thomas Gleixner
2023-06-01 12:43 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:49 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 16/20] posix-timers: Comment SIGEV_THREAD_ID properly Thomas Gleixner
2023-06-01 12:47 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:49 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 17/20] posix-timers: Clarify posix_timer_rearm() comment Thomas Gleixner
2023-06-01 12:52 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-18 20:49 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 18/20] posix-timers: Clarify posix_timer_fn() comments Thomas Gleixner
2023-06-01 13:21 ` Frederic Weisbecker
2023-06-01 18:43 ` Thomas Gleixner
2023-06-01 19:07 ` Thomas Gleixner
2023-06-05 14:26 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-05 22:17 ` tip-bot2 for Thomas Gleixner
2023-06-18 20:49 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 19/20] posix-timers: Remove pointless comments Thomas Gleixner
2023-06-01 13:48 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-05 22:17 ` tip-bot2 for Thomas Gleixner
2023-06-18 20:49 ` tip-bot2 for Thomas Gleixner
2023-04-25 18:49 ` [patch 20/20] posix-timers: Polish coding style in a few places Thomas Gleixner
2023-06-01 13:50 ` Frederic Weisbecker
2023-06-05 15:08 ` [tip: timers/core] " tip-bot2 for Thomas Gleixner
2023-06-05 22:17 ` tip-bot2 for Thomas Gleixner
2023-06-18 20:49 ` tip-bot2 for Thomas Gleixner
2023-06-05 14:32 ` [patch 00/20] posix-timers: Fixes and cleanups Frederic Weisbecker
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=8a42097629844e5eacf733328eac2d02@AcuMS.aculab.com \
--to=david.laight@aculab.com \
--cc=aleksandr.mikhalitsyn@canonical.com \
--cc=anna-maria@linutronix.de \
--cc=avagin@openvz.org \
--cc=bigeasy@linutronix.de \
--cc=brauner@kernel.org \
--cc=dvyukov@google.com \
--cc=frederic@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mtk.manpages@gmail.com \
--cc=peterz@infradead.org \
--cc=ptikhomirov@virtuozzo.com \
--cc=syzbot+5c54bd3eb218bb595aa9@syzkaller.appspotmail.com \
--cc=tglx@linutronix.de \
--cc=xemul@openvz.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.