On Wed, 2020-08-05 at 20:33 +0100, Matthew Wilcox wrote:

On Wed, Aug 05, 2020 at 04:30:10PM +0100, David Howells wrote:

quoted

Miklos Szeredi [off-list ref] wrote:

quoted

idr_alloc_cyclic() seems to be a good template for doing the
lower
32bit allocation, and we can add code to increment the high 32bit
on
wraparound.

Lots of code uses idr_alloc_cyclic() so I guess it shouldn't be
too
bad in terms of memory use or performance.

It's optimised for shortness of path and trades memory for
performance.  It's
currently implemented using an xarray, so memory usage is dependent
on the
sparseness of the tree.  Each node in the tree is 576 bytes and in
the worst
case, each one node will contain one mount - and then you have to
backfill the
ancestry, though for lower memory costs.

Systemd makes life more interesting since it sets up a whole load
of
propagations.  Each mount you make may cause several others to be
created, but
that would likely make the tree more efficient.

I would recommend using xa_alloc and ignoring the ID assigned from
xa_alloc.  Looking up by unique ID is then a matter of iterating
every
mount (xa_for_each()) looking for a matching unique ID in the mount
struct.  That's O(n) search, but it's faster than a linked list, and
we
don't have that many mounts in a system.

How many is not many, 5000, 10000, I agree that 30000 plus is fairly
rare, even for the autofs direct mount case I hope the implementation
here will help to fix.

Ian