From patchwork Tue Apr 1 22:44:19 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Felipe Balbi X-Patchwork-Id: 27587 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-pb0-f70.google.com (mail-pb0-f70.google.com [209.85.160.70]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id EA02720553 for ; Tue, 1 Apr 2014 22:46:53 +0000 (UTC) Received: by mail-pb0-f70.google.com with SMTP id rp16sf28546232pbb.9 for ; Tue, 01 Apr 2014 15:46:52 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:from:to:cc:subject:date:message-id :mime-version:sender:precedence:list-id:x-original-sender :x-original-authentication-results:mailing-list:list-post:list-help :list-archive:list-unsubscribe:content-type; bh=X1krh3MK68kZRft0RW1xNRwjyRfqfNUjIzwq/MqfTXE=; b=Ghp2iBHDUyJ5rJFxLEk8usk22O7ij0jIUGqfkETbFQAx/MSYWoPNPPLzOfKJlzOhAj UjmzRxOXGbhx8oZFgqBP/JDviBOIku0Hwiy4qbHfXJnlTyINM1FYS9m+1A5vgryarIKD 3UnToH0cukfotmH/yeF9BnUCKUGPMmBg6NYkGITVTDmM+7Ts3yp6PwnbpAsqoYXsGDV/ PoGJtYu6f7tXuU4kBvMSDNAXhAWpqTyxPPr6KGEnAmcljzQUYjowcyecGhJPqiVhIaSb Gbg4Nywu6DwkJ1EDMyq4PpngQKN4yPRgpgRaTgD2tsZzI+9NPMQte6XsimOSQDWAlX55 hO7A== X-Gm-Message-State: ALoCoQmn6X6slZL8RpPk0H0CXZ1hQF1sL45n326JCdloRG6hpjJpNuK0c4YjDvvrD//KS9V7FfXZ X-Received: by 10.66.140.8 with SMTP id rc8mr13405613pab.41.1396392412811; Tue, 01 Apr 2014 15:46:52 -0700 (PDT) X-BeenThere: patchwork-forward@linaro.org Received: by 10.140.96.132 with SMTP id k4ls153612qge.42.gmail; Tue, 01 Apr 2014 15:46:52 -0700 (PDT) X-Received: by 10.52.130.225 with SMTP id oh1mr26365498vdb.8.1396392412709; Tue, 01 Apr 2014 15:46:52 -0700 (PDT) Received: from mail-vc0-f170.google.com (mail-vc0-f170.google.com [209.85.220.170]) by mx.google.com with ESMTPS id rx10si16213vdc.42.2014.04.01.15.46.52 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 01 Apr 2014 15:46:52 -0700 (PDT) Received-SPF: neutral (google.com: 209.85.220.170 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) client-ip=209.85.220.170; Received: by mail-vc0-f170.google.com with SMTP id hu19so10951585vcb.29 for ; Tue, 01 Apr 2014 15:46:52 -0700 (PDT) X-Received: by 10.52.90.37 with SMTP id bt5mr26612733vdb.7.1396392412605; Tue, 01 Apr 2014 15:46:52 -0700 (PDT) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.220.12.8 with SMTP id v8csp275324vcv; Tue, 1 Apr 2014 15:46:52 -0700 (PDT) X-Received: by 10.66.164.70 with SMTP id yo6mr33930885pab.85.1396392411865; Tue, 01 Apr 2014 15:46:51 -0700 (PDT) Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id ym10si19262pab.146.2014.04.01.15.46.51; Tue, 01 Apr 2014 15:46:51 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-omap-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751833AbaDAWqu (ORCPT + 5 others); Tue, 1 Apr 2014 18:46:50 -0400 Received: from comal.ext.ti.com ([198.47.26.152]:56088 "EHLO comal.ext.ti.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751660AbaDAWqt (ORCPT ); Tue, 1 Apr 2014 18:46:49 -0400 Received: from dlelxv90.itg.ti.com ([172.17.2.17]) by comal.ext.ti.com (8.13.7/8.13.7) with ESMTP id s31MkJ8O030465; Tue, 1 Apr 2014 17:46:19 -0500 Received: from DLEE70.ent.ti.com (dlee70.ent.ti.com [157.170.170.113]) by dlelxv90.itg.ti.com (8.14.3/8.13.8) with ESMTP id s31MkJ08002356; Tue, 1 Apr 2014 17:46:19 -0500 Received: from dflp32.itg.ti.com (10.64.6.15) by DLEE70.ent.ti.com (157.170.170.113) with Microsoft SMTP Server id 14.3.174.1; Tue, 1 Apr 2014 17:46:18 -0500 Received: from localhost (ileax41-snat.itg.ti.com [10.172.224.153]) by dflp32.itg.ti.com (8.14.3/8.13.8) with ESMTP id s31MkI1S005570; Tue, 1 Apr 2014 17:46:18 -0500 From: Felipe Balbi To: , CC: , , Darren Etheridge , Linux OMAP Mailing List , Linux ARM Kernel Mailing List , Linux Kernel Mailing List , Felipe Balbi Subject: [PATCH] irq: crossbar: improve allocate_free_irq() complexity Date: Tue, 1 Apr 2014 17:44:19 -0500 Message-ID: <1396392259-27437-1-git-send-email-balbi@ti.com> X-Mailer: git-send-email 1.9.1.286.g5172cb3 MIME-Version: 1.0 Sender: linux-omap-owner@vger.kernel.org Precedence: list List-ID: X-Mailing-List: linux-omap@vger.kernel.org X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: balbi@ti.com X-Original-Authentication-Results: mx.google.com; spf=neutral (google.com: 209.85.220.170 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 List-Post: , List-Help: , List-Archive: List-Unsubscribe: , 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 --- 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; - return -ENODEV; + return current_irq; } static int crossbar_domain_map(struct irq_domain *d, unsigned int irq,