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

[Liam R. Howlett]

* Lorenzo Pieralisi <lpieralisi@xxxxxxxxxx> [250414 04:27]:
> On Sat, Apr 12, 2025 at 09:01:18AM -0400, Liam R. Howlett wrote:
> > * Lorenzo Pieralisi <lpieralisi@xxxxxxxxxx> [250411 08:37]:
> > 

...

> 
> > > 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).

Ah, that is a lot.

> 
> 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).

Yeah, I see this in the doc:
Some users need to allocate IDs larger than INT_MAX. So far all of these
users have been content with a UINT_MAX limit, and they use
idr_alloc_u32(). If you need IDs that will not fit in a u32, we will
work with you to address your needs.

> > 
> > 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).

Interesting, Alexei uses the bpf allocator.

> 
> 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.

Eventually, we plan to swap out the backing of the IDA to use the maple
tree.  I think we could add range support as part of this change.

If you were to add an interface to contiguous allocate a number of IDAs
by putting your loop in the IDA interface, we'd be able to switch that
to a range store during the conversion and keep the use case visible
during the planning stages.

Having that interface would make it obvious the change is necessary and
wouldn't be missed.

Unfortunately, I don't really have a timeline on changing the IDA to the
maple tree.

Please keep me Cc'ed on whatever you decide.

Thanks,
Liam