From patchwork Mon May 27 20:55:14 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Lezcano X-Patchwork-Id: 165224 Delivered-To: patch@linaro.org Received: by 2002:a92:9e1a:0:0:0:0:0 with SMTP id q26csp7616494ili; Mon, 27 May 2019 13:55:47 -0700 (PDT) X-Google-Smtp-Source: APXvYqx/fgDOza6ysGhd5G1/UAm+z0RSra49CeXzyYdusUtmuYzkTgfxA6b2GRFTHVtTKvyEfM1f X-Received: by 2002:a63:fa4a:: with SMTP id g10mr127536463pgk.147.1558990546957; Mon, 27 May 2019 13:55:46 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1558990546; cv=none; d=google.com; s=arc-20160816; b=bTPMa2Q1/LItbkt7ypJcnkHopBisvfkG8DYkj4h4aP7fZ9ntNhq4QRPY5PeUBdcuMB X0Y0xNDigyhUxHHc1B16Kt3B/EXW9vjTc07rNnL+Ftlv/QCz6Y+pUJyj5HNvnudRTAzc NG8g5Vt2kDDt8dLv3XCYyiFVQMksuoPxm/XGWthdD1YQRRUYhbsZcf7rF1tyWHi4w6ZF SamzGOLQ9pRcYiZHRbCoLL3lH2DmWdsZG1FQKYMnARZ6/nA1Ts+ntSBHHeRKcn6jWc8d vq38XnecTNYMEclI7hi+koj+MJQCu+FH0aaXdwawRMpfcitSNfd1oQnwQ5u21si1NrnV pmLQ== 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=lTcJJUHPBZrrX04wBrI5geMIeaqBLm2JwprDLfuI4WQ=; b=mJr7in1rlZTLVT/AzLVZH8Arz48crh8e+NxLc7Foypk/UFaUHdajUeijJsXa/Jo1xk GghifqB3w/o3xSebQL9A47t0yD2QuXMQy4jGZV/bH7/JgySZCJ+RiR9sKD4BEQDIqgRD z1UqTgKFYpcKAcdgaljKe0ZRl1KwGNLNvTOWIYtbgGLpL3ecEedONKcEO07q6M2TZ5Tt Q4gqQUI+GuS2iFMRrSOJvog3M0i0ARVglNBPQSJoWG5ALL8rVufngMnlsqGggpkCpX1v NwM01C6AIJ3Ocsuy9w63pirS2+MruB3yjsmebtmljzdktAD5PP5m/+BUXAzpiuLuFC4j dSgg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=hRUituCU; 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 31si20378810plb.30.2019.05.27.13.55.46; Mon, 27 May 2019 13:55:46 -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=hRUituCU; 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 S1727295AbfE0Uzo (ORCPT + 30 others); Mon, 27 May 2019 16:55:44 -0400 Received: from mail-wm1-f68.google.com ([209.85.128.68]:39050 "EHLO mail-wm1-f68.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726693AbfE0Uzn (ORCPT ); Mon, 27 May 2019 16:55:43 -0400 Received: by mail-wm1-f68.google.com with SMTP id z23so609403wma.4 for ; Mon, 27 May 2019 13:55:42 -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=lTcJJUHPBZrrX04wBrI5geMIeaqBLm2JwprDLfuI4WQ=; b=hRUituCUL6zlQFvBPkeIcnyXJzilIaTWZfysfx2y5BvWZn1RBFzD9onDgp3PfrG3Za 7M/zPlqSqK2BBu1d//QEZwsidxL4WdKJMvPlpljHdztK0U22Ma/2IPA6RU0h+YyeTaKa 51wjGzMl5ZMHfIO4cA01nMy9owwGDXZGBOQi6ieahJ5oke91Hl36D5D9ZVgAvCoRnQ3e bKCV9gvijSDZzTOBUbTRcLuzfBRkevL5csRNLXyr5/gU4DRXIiIInF+SRcew3VyB2ifG Ho8h+wTDNMT+WcGt3EsXjkqnrN/C2BwrRMHO91QV4PKUPhQUaWvreWCnyv+NzI50megQ iAAg== 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=lTcJJUHPBZrrX04wBrI5geMIeaqBLm2JwprDLfuI4WQ=; b=py5HC6No34OxnpESPjZQyz2KuU0KjtmvKw3FzDig6LrjzKshnPLY8/VS5JUCNPecg9 fBizFriSpYdonFNKme3sg6T6b6TiTl2BYw9V2ZoRGqQY9j0CNQfr+F++326qEmyU3K2q /5XiGIZjkon3xrymI5WIIGYsLDetbty6cm+VedOwhSHBwDVgNUXqNe7MkKuc6cY+17jA eNFqBLBtGQQaovoMukd9UxFAnPakQK7Ok7xbAw5eTSp/PmvmNqeS87AGb3t17WV49/iS yuroB8h0gxzKPZfzC2ntALKX6uccDDhBvV+oglwVuhR6bMEbuQq+1IVSDIza+ezoo7UE FtFg== X-Gm-Message-State: APjAAAWDU4cwzhKKaMpjKPnj7MDt8PCE60D15xVXLo6bl39HSaWWwzb+ udmYKhfmhDskGrFqU0Glvns+SQ== X-Received: by 2002:a7b:ca43:: with SMTP id m3mr585012wml.45.1558990541563; Mon, 27 May 2019 13:55:41 -0700 (PDT) Received: from clegane.local (30.94.129.77.rev.sfr.net. [77.129.94.30]) by smtp.gmail.com with ESMTPSA id a1sm388565wmj.23.2019.05.27.13.55.40 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 27 May 2019 13:55:40 -0700 (PDT) From: Daniel Lezcano To: tglx@linutronix.de Cc: linux-kernel@vger.kernel.org, andriy.shevchenko@linux.intel.com Subject: [PATCH V3 1/8] genirq/timings: Fix next event index function Date: Mon, 27 May 2019 22:55:14 +0200 Message-Id: <20190527205521.12091-2-daniel.lezcano@linaro.org> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190527205521.12091-1-daniel.lezcano@linaro.org> References: <20190527205521.12091-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 | 51 ++++++++++++++++++++++++++++++++++++-------- 1 file changed, 42 insertions(+), 9 deletions(-) -- 2.17.1 diff --git a/kernel/irq/timings.c b/kernel/irq/timings.c index 90c735da15d0..4f5daf3db13b 100644 --- a/kernel/irq/timings.c +++ b/kernel/irq/timings.c @@ -297,7 +297,16 @@ 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 beginning 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 +315,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; } }