Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 8BIT
To: Matthew Wilcox <willy@infradead.org>, linux-kernel@vger.kernel.org
From: Chris Wilson <chris@chris-wilson.co.uk>
In-Reply-To: <20171130173630.GA15948@bombadil.infradead.org>
Cc: "Tejun Heo" <tj@kernel.org>, "Eric Biggers" <ebiggers@google.com>,
        "Daniel Vetter" <daniel.vetter@ffwll.ch>,
        "Chris Mi" <chrism@mellanox.com>
References: <20171130173630.GA15948@bombadil.infradead.org>
Message-ID: <151298969175.4445.1226930193594726551@mail.alporthouse.com>
User-Agent: alot/0.3.6
Subject: Re: [RFC] Rebasing the IDR
Date: Mon, 11 Dec 2017 10:54:51 +0000
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1261
Lines: 23

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