I noticed that the O(n log n) behaviour of free_lpi_range could easily be made O(n) (patch 4), though I don't suppose n is ever large enough to actually matter. While there, I also stumbled on two other micro-optimizations (2 and 3).
Then while writing the commit log for the last patch, I noticed that the cmp callback I was removing was actually buggy, so I went back and added a patch in front suitable for -stable. I'll leave it to others to decide if it's important enough for that.
Please note that this is only compile-tested.
Rasmus Villemoes (4): irqchip/gic-v3-its: fix comparison logic in lpi_range_cmp irqchip/gic-v3-its: move allocation outside mutex irqchip/gic-v3-its: drop redundant initialization in mk_lpi_range irqchip/gic-v3-its: make free_lpi_range a little cheaper
drivers/irqchip/irq-gic-v3-its.c | 75 +++++++++++++++----------------- 1 file changed, 36 insertions(+), 39 deletions(-)
The lpi_range_list is supposed to be sorted in ascending order of ->base_id (at least if the range merging is to work), but the current comparison function returns a positive value if rb->base_id > ra->base_id, which means that list_sort() will put A after B in that case - and vice versa, of course.
Fixes: 880cb3cddd16 (irqchip/gic-v3-its: Refactor LPI allocator) Cc: stable@vger.kernel.org (v4.19+) Signed-off-by: Rasmus Villemoes linux@rasmusvillemoes.dk --- drivers/irqchip/irq-gic-v3-its.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/drivers/irqchip/irq-gic-v3-its.c b/drivers/irqchip/irq-gic-v3-its.c index 2dd1ff0cf558..7577755bdcf4 100644 --- a/drivers/irqchip/irq-gic-v3-its.c +++ b/drivers/irqchip/irq-gic-v3-its.c @@ -1482,7 +1482,7 @@ static int lpi_range_cmp(void *priv, struct list_head *a, struct list_head *b) ra = container_of(a, struct lpi_range, entry); rb = container_of(b, struct lpi_range, entry);
- return rb->base_id - ra->base_id; + return ra->base_id - rb->base_id; }
static void merge_lpi_ranges(void)
Hi Rasmus,
On 12/03/2019 17:33, Rasmus Villemoes wrote:
I noticed that the O(n log n) behaviour of free_lpi_range could easily be made O(n) (patch 4), though I don't suppose n is ever large enough to actually matter. While there, I also stumbled on two other micro-optimizations (2 and 3).
n is usually in the range 1 .. nr_cpus, so pretty small, even on the biggest machines we have around (256 threads). And actually, nobody ever frees LPIs, because hey, why would you?
Then while writing the commit log for the last patch, I noticed that the cmp callback I was removing was actually buggy, so I went back and added a patch in front suitable for -stable. I'll leave it to others to decide if it's important enough for that.
Thanks for that. I'll have a look at the whole thing anyway (I've just glanced over it so far).
Please note that this is only compile-tested.
Right, this needs some actual testing then. /me needs to build a guest that shakes the allocator a bit.
Cheers,
M.
linux-stable-mirror@lists.linaro.org
-
Marc Zyngier -
Rasmus Villemoes