From patchwork Fri May 24 11:16:07 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Lezcano X-Patchwork-Id: 165104 Delivered-To: patch@linaro.org Received: by 2002:a92:9e1a:0:0:0:0:0 with SMTP id q26csp3437478ili; Fri, 24 May 2019 04:16:55 -0700 (PDT) X-Google-Smtp-Source: APXvYqyFQNELbZZUT4rRtSEwtoHFVRJVYyEljoT/05P+7F3LWLd6SCoP98b8nFd0efiyKxfCf89r X-Received: by 2002:a17:90a:8c90:: with SMTP id b16mr8605738pjo.85.1558696615324; Fri, 24 May 2019 04:16:55 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1558696615; cv=none; d=google.com; s=arc-20160816; b=seAjsFT1bu+NsLXD8Vxa8gOPk71a6JK4Dzs5lwO9g2Goj5b8tWHZZp3cjnnV03F8rQ kK0BU5Pjp2zw0H3NFLFvf64R8umwVeiHg2mzROkhxRwUoGVBNL8iyA2Du9uOtsmyHUOP RBJPXGj+9IunTHmcLlj2eGRprAn4XMlYPj0+oPiXoNL38JcvxplU9qCJCYHra6uKB698 Qlq9WSvrJoV6YxjOqYj2E1r1ipDVO4M/1W/u0olQujdTeD/2bOOXDWveOkFAav2F7p2+ NkX6e6dFJVfRTYdlY+f09L13jAoZo/SXQmmtEVqzkONp3JzFv5KuJbcC6LqPUoKQGb2r QPsQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:cc:to:from:dkim-signature; bh=A0HzfJ8leQV9/Ia+5j4PgeiH8O0rzgjlyMwyBqLrNY4=; b=Ttae8DmkssiZWHLfKEgagdo/YOAdxIu7o6LwIXOagA580nZo0hiVZ0oDnojc7jjoXW 9JEwHqS+Ib9wZiqRVk7g0rS19xfSsYFMIL0iTrbpeK8Q5/LA9J5rC2ZvjoQITKHNP3ZN oyifxavvMfEpn9avvaMe2/Dyrzuw4mPwXxWSb2LDEADFLCNCz/6NHiiX4dycu3z8nwvV NFOQHguc11PAQwwxoc+fMy5IeyK6gBwGSvUSNgAFPg6tUM2O127uUrVMSv93QFBlFs8J pkSUBs0PPgJgmQzI7l8kWXiZTEnvinswXcpctvMpmxTceg3pF/Pcw295lm2f039+BWZe pSKw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=pvNpKcLs; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id b1si3735560pgg.392.2019.05.24.04.16.54; Fri, 24 May 2019 04:16:55 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=pvNpKcLs; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2390894AbfEXLQl (ORCPT + 30 others); Fri, 24 May 2019 07:16:41 -0400 Received: from mail-wr1-f67.google.com ([209.85.221.67]:46503 "EHLO mail-wr1-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2390410AbfEXLQj (ORCPT ); Fri, 24 May 2019 07:16:39 -0400 Received: by mail-wr1-f67.google.com with SMTP id r7so9578114wrr.13 for ; Fri, 24 May 2019 04:16:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=A0HzfJ8leQV9/Ia+5j4PgeiH8O0rzgjlyMwyBqLrNY4=; b=pvNpKcLsEz+1W37HcVISnMK4xkdCyLtbas0+BI0hYTjlzR/fSpFpW7oqy0Nk7KvHwx BxHl44BzkSqRlNJhucVvuVCrgCGGQO6decnRTfn12JuxgpSvDQ+ouiu5kba2JFwy+OJR BTJbBFDg17pyytm0KbCGpghu4BjNRDIVEmfXZCKwARZSevQBe/bE0pjHs6sFqG0qDgyc HxZ/NMWbPrzbIVMbeHXTU2Na9e01X8aT7e7OIzCXs7cgJKeK8otHCzSESBjs8q+8/0kV U/rQUYpkoIqbdy865VwfoCkjhL5vFxFEqLtJw+hixLdQNJ+JEjKHWzFXC+ULshxJrIc9 nYew== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=A0HzfJ8leQV9/Ia+5j4PgeiH8O0rzgjlyMwyBqLrNY4=; b=Qg0BIgN9dDs0n4NAvSflcHsswb8dCK2IuRg/yyUpWNTkur6Ubm9BuKGOIltVeaGQ2b gCJDaYa0zXTkYpd588sn0haFz7719KuYMpDFVn51//jNs+rtx/onoae1JvAoCLkfzjWu 6l7P/HrJcK1BZwrC/0XOSDSeAuU0G6rNHvvTpkML8cM6sCiKmEbE3ma0VLijPZ8LYTWr FjiD4v3pA1D8LoOijavxHGXkS6wEb53CCTy1gfQ8HGivJptvZjqBp3oi3W1tEfAXUMbt FONgREhStDCQwgWKWZ5ETP5y4qmiqBZYZjUGzVcGmUER1B86M6RvKvy9FhbptCXnwrJX cRIA== X-Gm-Message-State: APjAAAU7q9Y5OriknPJZqgJiwu8qOTD8yF4pBihCm2pSq3ytIzPipAlS 0GuKfsMwFshilN7xbf8nl+dCziu5+pA= X-Received: by 2002:a5d:4945:: with SMTP id r5mr9522454wrs.328.1558696597623; Fri, 24 May 2019 04:16:37 -0700 (PDT) Received: from clegane.local (73.82.95.92.rev.sfr.net. [92.95.82.73]) by smtp.gmail.com with ESMTPSA id h12sm2575392wre.14.2019.05.24.04.16.36 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 24 May 2019 04:16:37 -0700 (PDT) From: Daniel Lezcano To: tglx@linutronix.de Cc: linux-kernel@vger.kernel.org, andriy.shevchenko@linux.intel.com Subject: [PATCH V2 1/9] genirq/timings: Fix next event index function Date: Fri, 24 May 2019 13:16:07 +0200 Message-Id: <20190524111615.4891-2-daniel.lezcano@linaro.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190524111615.4891-1-daniel.lezcano@linaro.org> References: <20190524111615.4891-1-daniel.lezcano@linaro.org> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org The current code was luckily working with most of the interval samples testing but actually it fails to correctly detect pattern repeatition breaking at the end of the buffer. Narrowing down the bug has been a real pain because of the pointers, so the routine is rewrite by using indexes instead. Fixes: bbba0e7c5cda "genirq/timings: Add array suffix computation code" Signed-off-by: Daniel Lezcano --- kernel/irq/timings.c | 53 ++++++++++++++++++++++++++++++++++++-------- 1 file changed, 44 insertions(+), 9 deletions(-) -- 2.17.1 diff --git a/kernel/irq/timings.c b/kernel/irq/timings.c index 90c735da15d0..60362aca4ca4 100644 --- a/kernel/irq/timings.c +++ b/kernel/irq/timings.c @@ -297,7 +297,18 @@ static u64 irq_timings_ema_new(u64 value, u64 ema_old) static int irq_timings_next_event_index(int *buffer, size_t len, int period_max) { - int i; + int period; + + /* + * Move the beginnning pointer to the end minus the max period + * x 3. We are at the point we can begin searching the pattern + */ + buffer = &buffer[len - (period_max * 3)]; + + /* + * Adjust the length to the maximum allowed period x 3 + */ + len = period_max * 3; /* * The buffer contains the suite of intervals, in a ilog2 @@ -306,21 +317,45 @@ static int irq_timings_next_event_index(int *buffer, size_t len, int period_max) * period beginning at the end of the buffer. We do that for * each suffix. */ - for (i = period_max; i >= PREDICTION_PERIOD_MIN ; i--) { + for (period = period_max; period >= PREDICTION_PERIOD_MIN ; period--) { - int *begin = &buffer[len - (i * 3)]; - int *ptr = begin; + /* + * The first comparison always succeed because the + * suffix is deduced from the first n-period bytes of + * the buffer and we compare the initial suffix with + * itself, so we can skip the first iteration. + */ + int idx = period; + size_t size = period; /* * We look if the suite with period 'i' repeat * itself. If it is truncated at the end, as it * repeats we can use the period to find out the next - * element. + * element with the modulo. */ - while (!memcmp(ptr, begin, i * sizeof(*ptr))) { - ptr += i; - if (ptr >= &buffer[len]) - return begin[((i * 3) % i)]; + while (!memcmp(buffer, &buffer[idx], size * sizeof(int))) { + + /* + * Move the index in a period basis + */ + idx += size; + + /* + * If this condition is reached, all previous + * memcmp were successful, so the period is + * found. + */ + if (idx == len) + return buffer[len % period]; + + /* + * If the remaining elements to compare are + * smaller than the period, readjust the size + * of the comparison for the last iteration. + */ + if (len - idx < period) + size = len - idx; } }