[RFC 00/10] implement alternative and much simpler id allocator

[Matthew Wilcox]

From: Andrew Morton [mailto:akpm at linux-foundation.org]
> On Thu,  8 Dec 2016 02:22:55 +0100 Rasmus Villemoes
> <linux at rasmusvillemoes.dk> wrote:
> > TL;DR: these patches save 250 KB of memory, with more low-hanging
> > fruit ready to pick.
> >
> > While browsing through the lib/idr.c code, I noticed that the code at
> > the end of ida_get_new_above() probably doesn't work as intended: Most
> > users of ida use it via ida_simple_get(), and that starts by
> > unconditionally calling ida_pre_get(), ensuring that ida->idr has
> > 8==MAX_IDR_FREE idr_layers in its free list id_free. In the common
> > case, none (or at most one) of these get used during
> > ida_get_new_above(), and we only free one, leaving at least 6 (usually
> > 7) idr_layers in the free list.
> 
> I expect we'll be merging patches 1-32 of that series into 4.10-rc1 and
> the above patch (#33) into 4.11-rc1.

Hi Rasmus,

Thanks for your work on this; you've really put some effort into proving your work has value.  My motivation was purely aesthetic, but you've got some genuine savings here (admittedly it's about a quarter of a cent's worth of memory with DRAM selling for $10/GB).  Nevertheless, that adds up over a billion devices, and there are still people trying to fit Linux into 4MB embedded devices.

I think my reimplementation of the IDA on top of the radix tree is close enough to your tIDA in memory consumption that it doesn't warrant a new data structure.

On a 64-bit machine, your tIDA root is 24 bytes; my new IDA root is 16 bytes.  If you allocate only one entry, you'll allocate 8 bytes.  Thanks to the slab allocator, that gets rounded up to 32 bytes.  I allocate the full 128 byte leaf, but I store the pointer to it in the root (unlike the IDR, the radix tree doesn't need to allocate a layer for a single entry).  So tIDA wins on memory consumption between 1 and 511 IDs, and newIDA is slightly ahead between 512 and 1023 IDs.  Above 1024 IDs, I allocate a layer (576 bytes), and a second leaf (832 bytes total), while you just double to 256 bytes.  I think tIDA's memory consumption then stays ahead of new IDA.  But performance of 'allocate new ID' should be better for newIDA than tIDA as newIDA can skip over all the cachelines of full bitmaps.

Yesterday, I found a new problem with the IDA allocator that you hadn't mentioned -- about half of the users of the IDA data structure never call destroy_ida().  Which means that they're leaking the preloaded bitmap.  I have a patch which moves the preloaded IDA bitmap from being stored in the IDA to being stored in a percpu variable.  You can find it here: http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/idr-2016-12-16 I'd welcome more testing and code review.