linux-kernel - Re: [PATCH] ipc: optimize semget/shmget/msgget for lots of keys

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]

Date:   Mon, 31 Jul 2017 08:45:58 -0700
From:   Davidlohr Bueso <dave@...olabs.net>
To:     Guillaume Knispel <guillaume.knispel@...ersonicimagine.com>
Cc:     Andrew Morton <akpm@...ux-foundation.org>,
        Manfred Spraul <manfred@...orfullife.com>,
        Kees Cook <keescook@...omium.org>,
        Alexey Dobriyan <adobriyan@...il.com>,
        "Eric W. Biederman" <ebiederm@...ssion.com>,
        "Peter Zijlstra (Intel)" <peterz@...radead.org>,
        Ingo Molnar <mingo@...nel.org>,
        Sebastian Andrzej Siewior <bigeasy@...utronix.de>,
        Serge Hallyn <serge@...lyn.com>,
        Andrey Vagin <avagin@...nvz.org>,
        Marc Pardo <marc.pardo@...ersonicimagine.com>,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH] ipc: optimize semget/shmget/msgget for lots of keys

On Mon, 31 Jul 2017, Guillaume Knispel wrote:

>ipc_findkey() scanned all objects to look for the wanted key. This is
>slow when using a high number of keys, for example on an i5 laptop the
>following loop took 17 s, with last semget calls taking ~1 ms each.

I would argue that this is not the common case.

>
>    for (int i = 0, k=0x424242; i < 31900; ++i)
>        semget(k++, 1, IPC_CREAT | 0600);
>
>This change adds an rhashtable of kern_ipc_perm objects in ipc_ids, so
>that one lookup cease to be O(n). The above loop now takes ~10 ms. Each
>lookup-only semget() call can take between ~120 ns and a few µs. Rarely,
>some creations can take a few dozen of µs.

Could you please provide numbers for smaller amounts of keys?

Thanks,
Davidlohr