linux-kernel - Re: [PATCH] irq: crossbar: improve allocate_free

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20140401224654.GA23786@saruman.home>
Date:	Tue, 1 Apr 2014 17:46:54 -0500
From:	Felipe Balbi <balbi@...com>
To:	Felipe Balbi <balbi@...com>
CC:	<r.sricharan@...com>, <tglx@...utronix.de>, <galak@...eaurora.org>,
	<santosh.shilimkar@...com>, Darren Etheridge <detheridge@...com>,
	Linux OMAP Mailing List <linux-omap@...r.kernel.org>,
	Linux ARM Kernel Mailing List 
	<linux-arm-kernel@...ts.infradead.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] irq: crossbar: improve allocate_free_irq() complexity

On Tue, Apr 01, 2014 at 05:44:19PM -0500, Felipe Balbi wrote:
> current algorithm in allocate_free_irq() is O(n),
> by just keeping track of last allocated IRQ with a
> simple unsigned integer, we can find a free IRQ
> in O(1).
> 
> Signed-off-by: Felipe Balbi <balbi@...com>
> ---
> 
> compile-tested only as J6 DTS is currently missing crossbar
> altogether :-(
> 
> There's a drawback with this patch which I'm not sure if we
> should care a lot because I couldn't entirely grasp when is
> domain->xlate() called and if we will map/unmap IRQs in runtime
> or will this *always* be done only during boot.
> 
> If we're talking about runtime IRQ remapping, then this, clearly,
> won't work. But if this will be done only during boot up, then we
> avoid iterating over the irq_map array each time we try to translate
> a new IRQ prior to mapping it.
> 
> Comments are highly welcome as I'll probably learn something new
> about the IRQ subsystem ;-)
> 
>  drivers/irqchip/irq-crossbar.c | 16 ++++++++--------
>  1 file changed, 8 insertions(+), 8 deletions(-)
> 
> diff --git a/drivers/irqchip/irq-crossbar.c b/drivers/irqchip/irq-crossbar.c
> index fc817d2..1c4da5a 100644
> --- a/drivers/irqchip/irq-crossbar.c
> +++ b/drivers/irqchip/irq-crossbar.c
> @@ -31,6 +31,7 @@ struct crossbar_device {
>  	void __iomem *crossbar_base;
>  	int *register_offsets;
>  	void (*write) (int, int);
> +	unsigned int current_irq;
>  };
>  
>  static struct crossbar_device *cb;
> @@ -52,16 +53,15 @@ static inline void crossbar_writeb(int irq_no, int cb_no)
>  
>  static inline int allocate_free_irq(int cb_no)
>  {
> -	int i;
> +	int current_irq;
>  
> -	for (i = 0; i < cb->int_max; i++) {
> -		if (cb->irq_map[i] == IRQ_FREE) {
> -			cb->irq_map[i] = cb_no;
> -			return i;
> -		}
> -	}
> +	if (cb->current_irq == cb->int_max)
> +		return -ENODEV;
> +
> +	current_irq = cb->current_irq++;
> +	cb->irq_map[current_irq++] = cb_no;

this increment is bogus, thought I had committed already, please ignore.

-- 
balbi

Download attachment "signature.asc" of type "application/pgp-signature" (820 bytes)