Re: [PATCH 20/24] irqchip/gic-v5: Add GICv5 LPI/IPI support

[Lorenzo Pieralisi <lpieralisi@kernel.org>]

On Sat, Apr 12, 2025 at 09:01:18AM -0400, Liam R. Howlett wrote:
> * Lorenzo Pieralisi <lpieralisi@kernel.org> [250411 08:37]:
> 
> Thanks for the Cc.
> 
> > On Fri, Apr 11, 2025 at 11:55:22AM +0200, Thomas Gleixner wrote:
> > > On Fri, Apr 11 2025 at 11:26, Lorenzo Pieralisi wrote:
> > > > On Tue, Apr 08, 2025 at 12:50:19PM +0200, Lorenzo Pieralisi wrote:
> > > >> Maple tree entries are not used by the driver, only the range tracking
> > > >> is required - therefore the driver first finds an empty area large
> > > >> enough to contain the required number of LPIs then checks the
> > > >> adjacent (and possibly occupied) LPI ranges and try to merge them
> > > >> together, reducing maple tree slots usage.
> > > >
> > > > The maple tree usage for this purpose is an RFC at this stage.
> > > >
> > > > Added Alexei because I know BPF arena used the maple tree in
> > > > a similar way in the past and moved to a range tree because
> > > > the BPF arena requires a special purpose mem allocator.
> > > >
> > > > As Thomas already pointed out a plain bitmap could do even though
> > > > it requires preallocating memory up to 2MB (or we can grow it
> > > > dynamically).
> > > >
> > > > We could allocate IDs using an IDA as well, though that's 1 by 1,
> > > > we allocate LPI INTIDs 1 by 1 - mostly, upon MSI allocation, so
> > > > using an IDA could do (AFAIU it works for 0..INT_MAX we need
> > > > 0..2^24 worst case).
> > > 
> > > The point is that you really only need a 1-bit storage per entry,
> > > i.e. used/unused. You won't use any of the storage functions of maple
> > > tree, idr or whatever.
> > 
> > IDA does use the XArray entries (i.e. the pointers) to store bitmaps,
> > the only drawback I see is that it allocates IDs one by one (but that's
> > not really a problem).
> > 
> > I wonder if it is used in the kernel for IDs larger than 16 bits, it
> > should work for 0..INT_MAX.
> > 
> > > So the obvious choice is a bitmap and as you said, it's trivial to start
> > > with a reasonably sized one and reallocate during runtime if the need
> > > arises.
> 
> I think the IDA or the bitmap for space saving would be better - the
> xarray does do something under the hood for IDA space savings.
> 
> If you want to compare, I can suggest some changes to your maple tree
> code (mas_{next/prev}_range might help).

Thank you.

> > Yes I can do that too but to avoid fiddling with alloc/free ranges crossing
> > bitmap chunks we need a single bitmap, AFAICS that may require realloc+copy,
> > if the need arises.
> 
> That is the advantage of the IDA or maple tree, the expansion is handled
> for you. I'd be inclined to suggest using the IDA, but I'm not sure how
> important storing an entire range is for your usecase?

The point is, IDs represent interrupt IDs. We allocate them in batches,
whose length varies, it can be 1 but it can also be a larger vector
(ie 1024).

It is obviously faster to allocate a range than allocating them 1 by 1,
that's the only reason why we have not used an IDA (and also because I
did not know whether an IDA is recommended for a larger ID space > than,
say, 2^16 - but I think it is because it is designed to cover 0..INT_MAX
and I noticed that -mm folks may even ask to extend it).
> 
> Are there other reasons you want to use the maple tree besides the range
> support?

We used the maple tree because it handles ranges, we have not found a
sound usage for the 8 byte entry pointer (there may be some but it is
overengineering), that's why I try to merge adjacent ranges on
allocation, for vectors that are length 1 or 2 it is gross to waste
8 bytes for nothing.

Using an IDA and allocating 1 by 1 has its advantages (ie if the ID
space is fragmented it is easier to find free IDs - even though,
again, given the expected allocation pattern, freeing IRQ IDs is rarer
than allocating them so I am not sure we would end up having a very
sparse ID space).

All in all, other than looking sloppy (allocating 1 by 1 when we could
allocate a range), using an IDA would work.

In terms of memory space efficiency, I think this depends on allocation
patterns (and what I did minimise wasting slot entries for nothing).

I added Alexei because, memory allocation notwithstanding, handling
ranges is what the BPF range tree does:

commit b795379757eb

the reason a range tree was implemented to replace a MT was the
memory allocation requirements - they were using a maple tree before
(with unused entries).

I can go for an IDA unless someone see a point in pursuing the current
approach - that I would update according to feedback, at least with
this thread you get the full picture.

Thanks !
Lorenzo