From patchwork Fri Mar 8 21:20:44 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Daniel Lezcano X-Patchwork-Id: 10845441 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 8ED8E1803 for ; Fri, 8 Mar 2019 21:21:26 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7B52B301D5 for ; Fri, 8 Mar 2019 21:21:26 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 6F3D330206; Fri, 8 Mar 2019 21:21:26 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.0 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 0FC4D301EA for ; Fri, 8 Mar 2019 21:21:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726418AbfCHVVF (ORCPT ); Fri, 8 Mar 2019 16:21:05 -0500 Received: from mail-wr1-f65.google.com ([209.85.221.65]:32816 "EHLO mail-wr1-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726279AbfCHVVF (ORCPT ); Fri, 8 Mar 2019 16:21:05 -0500 Received: by mail-wr1-f65.google.com with SMTP id i12so22809963wrw.0 for ; Fri, 08 Mar 2019 13:21:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=from:to:cc:subject:date:message-id; bh=Ne9yb9VUqbc5mhujnU04vF9d+jUVhs1WNFkzZ9SVc1I=; b=j5eVKL1YtiJo+d4hr1Y8V48gVOeI68d2COvxTtMyUTN2ne0EUUqkCxWw/rhq4x1jwV b5waafFFke5yiJCgmu0tIKVv42kGWWXctVwqaKoKs7vCVq8gwL3q+junKGytIIDPV3qF amCBWScoo7+1Yw3sWw3/Gu0pvSMPO0nu6DKmBzEVCR7gF2M7b58Am0C98i4wHHQ01qyk bb+CEJ/FhBXC6nN+v3e5/EQOp/RJ+VRT+yZ2L880aQ8Y7vPHkx0rN0sHV1O4wjBuLbMs QtDZ+NcYEjfBtngv4l3B18d5kJLllNbZFLss7FZNLSm0FJl6zlRMcXcq6oZYczUL2qx2 KyVQ== 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; bh=Ne9yb9VUqbc5mhujnU04vF9d+jUVhs1WNFkzZ9SVc1I=; b=lOfBapFGQYPLuuarCupz7NqdaocpXEyZHC5RxQtAwgpHMYmLTXFqGRqFRSCNpeTwaX LiekkgIk5fpA3i6ARCbYX+ZpXwodweCqiaEPhjBZDPm+h2mvzq71ujlYdzxjE8+MC5IE KX+Ixf97PV70ymA6gTmozmj+Y2UslDc/RB+PL25FLAPtNs2ZAQWa8kfTJYicgBr0/MWV 5ksN7gNg09ZKko7Q9TFXVJ886QjNNO2O/E2eCU22Cyg9IdZn3TP4+DTsF/pO0EW+Jryj Ns2hkYCzs+EdnlPeg5gsV2yGU7/t9l/yOp1Hsf70bDFOJA8LHzyqK0/Z7ppsrEBuuh5+ YUyw== X-Gm-Message-State: APjAAAX1EuDbHpaNCiNESK3kCSf0Uv4jMNaz9wf/WppzRlHCmkvVztns +y9QhP3/vCe0R8i60ihzNfc1DjwM1xU= X-Google-Smtp-Source: APXvYqy5sMQ046cz6qeeE/yGsSleSz0fXJZqOrl28rQBGCtM3B0TkZMqWr28/KDrvuFpKurv1+XvTg== X-Received: by 2002:adf:f711:: with SMTP id r17mr4243207wrp.38.1552080063146; Fri, 08 Mar 2019 13:21:03 -0800 (PST) Received: from clegane.local (246.127.130.77.rev.sfr.net. [77.130.127.246]) by smtp.gmail.com with ESMTPSA id d2sm13568507wrq.94.2019.03.08.13.21.01 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 08 Mar 2019 13:21:02 -0800 (PST) From: Daniel Lezcano To: rjw@rjwysocki.net, tglx@linutronix.de Cc: ulf.hansson@linaro.org, linux-pm@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH 0/3] IRQ next prediction and mbed governor Date: Fri, 8 Mar 2019 22:20:44 +0100 Message-Id: <20190308212047.28767-1-daniel.lezcano@linaro.org> X-Mailer: git-send-email 2.17.1 Sender: linux-pm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-pm@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP The following patchset provides the missing bits to predict the next event on the the current CPU by identifying three categories of wakeup sources, the interrupts from the devices, the timers and the IPI rescheduling. Initially, the interrupt prediction was based on the statistical normal law, discarding interrupt intervals out of the gaussian curve, thus allowing to predict only interrupts coming in regular intervals. Unfortunately this approach prevents to handle any kind of irregular intervals, closing the door for more accuracy in the prediction. With a derived array suffixes algorithm, it is possible to quickly detect the repeating patterns in less than 1us per interrupt on x86. The algorithm is described in the documentation. It is simple in in apparence but it needs some attention to understand how it allows to detect the pattern and return a guess estimate of the next event. And finally, a new cpuidle governor is added to make use of these predictions for the different wake up sources but targetting embedded systems. Daniel Lezcano (3): genirq/timings: Remove variance computation code genirq/timings: Add array suffix computation code cpuidle/drivers/mbed: Add new governor for embedded systems drivers/cpuidle/Kconfig | 11 +- drivers/cpuidle/governors/Makefile | 1 + drivers/cpuidle/governors/mbed.c | 143 +++++++++ kernel/irq/timings.c | 488 +++++++++++++++++++---------- 4 files changed, 485 insertions(+), 158 deletions(-) create mode 100644 drivers/cpuidle/governors/mbed.c