linux-kernel - Re: [RFC] Rebasing the IDR

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 for Android: free password hash cracker in your pocket

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

Message-ID: <151298969175.4445.1226930193594726551@mail.alporthouse.com>
Date:   Mon, 11 Dec 2017 10:54:51 +0000
From:   Chris Wilson <chris@...is-wilson.co.uk>
To:     Matthew Wilcox <willy@...radead.org>, linux-kernel@...r.kernel.org
Cc:     "Tejun Heo" <tj@...nel.org>, "Eric Biggers" <ebiggers@...gle.com>,
        "Daniel Vetter" <daniel.vetter@...ll.ch>,
        "Chris Mi" <chrism@...lanox.com>
Subject: Re: [RFC] Rebasing the IDR

Quoting Matthew Wilcox (2017-11-30 17:36:30)
> About 40 of the approximately 180 users of the IDR in the kernel are
> "1-based" instead of "0-based".  That is, they never want to have ID 0
> allocated; they want to see IDs allocated between 1 and N.  Usually, that's
> expressed like this:
> 
>         /* Get the user-visible handle using idr. */
>         ret = idr_alloc(&file_priv->object_idr, obj, 1, 0, GFP_KERNEL);
> 
> The current implementation of this grieves me.  You see, we mark each
> node of the radix tree according to whether it has any free entries
> or not, and entry 0 is always free!  If we've already allocated 10,000
> entries from this IDR, and see this call, we'll walk all the way down
> the left side of the tree looking for entry 1, get to the bottom,
> see that entries 1-63 are allocated, then walk up to the next level,
> see that 64-4095 are allocated, walk up to the next level, see that
> 8192-12287 has a free entry, and then start walking down again.

Hmm, missing the baseline to apply this patch. But I did the quick hack
of allocating index 0 of the idr and that did eradicate the
idr_get_free_cmn() from being at the top of the profiles for the
many-object stress tests. This improvement will be much appreciated.
-Chris