linux-kernel - RE: [RFD] posix-timers: CRIU woes

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <8a42097629844e5eacf733328eac2d02@AcuMS.aculab.com>
Date:   Thu, 11 May 2023 10:13:20 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     'Pavel Tikhomirov' <ptikhomirov@...tuozzo.com>,
        Thomas Gleixner <tglx@...utronix.de>,
        Frederic Weisbecker <frederic@...nel.org>
CC:     LKML <linux-kernel@...r.kernel.org>,
        Anna-Maria Behnsen <anna-maria@...utronix.de>,
        Peter Zijlstra <peterz@...radead.org>,
        "syzbot+5c54bd3eb218bb595aa9@...kaller.appspotmail.com" 
        <syzbot+5c54bd3eb218bb595aa9@...kaller.appspotmail.com>,
        Dmitry Vyukov <dvyukov@...gle.com>,
        Sebastian Siewior <bigeasy@...utronix.de>,
        "Michael Kerrisk" <mtk.manpages@...il.com>,
        Andrei Vagin <avagin@...nvz.org>,
        "Christian Brauner" <brauner@...nel.org>,
        Alexander Mikhalitsyn <aleksandr.mikhalitsyn@...onical.com>,
        Pavel Emelyanov <xemul@...nvz.org>
Subject: RE: [RFD] posix-timers: CRIU woes

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)