From patchwork Wed Aug 1 15:13:04 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Weiner X-Patchwork-Id: 10552433 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 A90D915E9 for ; Wed, 1 Aug 2018 15:10:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 969A62B8CA for ; Wed, 1 Aug 2018 15:10:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 941B52B8BE; Wed, 1 Aug 2018 15:10:52 +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=-2.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 760422B841 for ; Wed, 1 Aug 2018 15:10:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 347E66B000D; Wed, 1 Aug 2018 11:10:39 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 2F8F26B000E; Wed, 1 Aug 2018 11:10:39 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 1C5A06B0010; Wed, 1 Aug 2018 11:10:39 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt0-f199.google.com (mail-qt0-f199.google.com [209.85.216.199]) by kanga.kvack.org (Postfix) with ESMTP id DE2106B000D for ; Wed, 1 Aug 2018 11:10:38 -0400 (EDT) Received: by mail-qt0-f199.google.com with SMTP id d18-v6so16069737qtj.20 for ; Wed, 01 Aug 2018 08:10:38 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:dkim-signature:from:to:cc:subject:date :message-id:in-reply-to:references:reply-to; bh=7HJ/faUwNp70pvtX2vst2/bX0oNS92n5Rlox7XiLwSM=; b=nNYJU1AFaMULSpQcqOzn7GW2fQ+VXdXju1MxVF+j+khTrabDijTuTwVQAE9ioIYqAd rp2Vwvs1cFOw/qtrXTG4JVcSMPI2AhnCIsS2Y/JIgCiugIAsOkRBPPCU5YoOMwlZ7EFX wW+hmoJtMJEVPsgBBu2L0/UcDfKInOfiGiY0LvGaNKzqllIJdUyaDcrlZUwFT5pg3mnD qM0Xd3RKKiZmst1k5H0zWQqaL0maPbUqC7jnVUj01iEPYcvCHMI45bUrTi8b7NgNeThz 4VbnpdpZY4NZX3xOlOR2P+CGzJLvJpDCDHIVxl7O8oUNWuprrKzqjTdv8vY9FzKupWQL J6Iw== X-Gm-Message-State: AOUpUlHLXvjcEnnrbGV/1sJ+d28L64hTN1oykUZun8hx6XCbRO+qk0Fw 2uxWFHU/YjQWSztmsiD7e/q2/YqALF/Jli5UAVxHSpoKPcPUB2SaW7bwCDadkyqVCaSbDRv87kJ SbwYnoMYJKSFaxe6HqXgEGsnFr0qu2TUC2GO9MHrqVrZ0WMqmSaUe8c1VhyCr5DSO2HQ/Im+3VF 8yaHxtg1TKiKSgcvRxi2PgG3UpF+8WR2vw3dG4S03CfP8dQl4zy3ayFzK1UCPi5TXVoE9R3HqxZ CuYlvpsRsHqh0n0MGHhcAQ8qji0GpjMVN7FUaaYU7+645u+3CFVv7flqJO2fTghS+ip22neaHLv hg0TpTyFX9QNnJBypAiJh31QpWg0i64HWf16OvqCQtT2ydpyH+GAlxv4cJjMb74mrr0ckQFpZhR 5 X-Received: by 2002:a0c:e0c8:: with SMTP id x8-v6mr23692068qvk.74.1533136238630; Wed, 01 Aug 2018 08:10:38 -0700 (PDT) X-Received: by 2002:a0c:e0c8:: with SMTP id x8-v6mr23691994qvk.74.1533136237734; Wed, 01 Aug 2018 08:10:37 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1533136237; cv=none; d=google.com; s=arc-20160816; b=04grqvhs6okowGZIq3JDzsXtl8tvibjSlit/oBN/Pan55/iNIVPXm73BqLcMLjzWnO rOCA4l0DMvY93wwFDLMbNNXpsUiEJhDEjLJzPCDKoiIQCk2HQKDlHDcsAXEOPp1d1idx O6vaJ02kzrIqU/8SWgUZTyvRUAm5/LESUyXNmLwY9DQo2k+FNGici26y7SJJiTPLNCp8 WMVu48lBc7AkbSSONWBXz/G5DM8eqPwp2+MhQNILXtboycq9SBJYKtIk/xY83S2ReUW+ 55/GW17Zwh997xY3Xqx6eO1gu0mEkxtoevLk2egCt2fHsNr/1mnStooPRPEyjVyx9EOS wbBA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=reply-to:references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature:arc-authentication-results; bh=7HJ/faUwNp70pvtX2vst2/bX0oNS92n5Rlox7XiLwSM=; b=N7R9YnnmmL8UwLCxnALaishejBsLg2bRN6F1PhJ0SGhAmTdZkre1QihLRyvZGlUg5K Iki94E8XttqZmfcPJjRIW7YP3dGeyQQuXx5XUF+A/7SFLVSgi9nSoghD2uY4uUWD0k46 oWLgbVUsv8NLoZzoUtPy9Lrq3DQMhBJrCxjaaYY2lNGEozHvvQjod53F1tbIEoUrC0B9 J/4Bvg7XCQ1z8XVPHu5h32pBJdMhUGtfFMG6aqDpBbLwPb//eXNG2Vz+iuV8+FkGTr5z n2SwOdyr9JMAwrEoEvHnGJBEBlPNoadBH+KNVUbMYXQtitfhSAgec2czWpMcqWnm8WwD WDnw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@cmpxchg-org.20150623.gappssmtp.com header.s=20150623 header.b="19/OXUit"; spf=pass (google.com: domain of hannes@cmpxchg.org designates 209.85.220.65 as permitted sender) smtp.mailfrom=hannes@cmpxchg.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=cmpxchg.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id b14-v6sor7878557qvj.143.2018.08.01.08.10.37 for (Google Transport Security); Wed, 01 Aug 2018 08:10:37 -0700 (PDT) Received-SPF: pass (google.com: domain of hannes@cmpxchg.org designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; dkim=pass header.i=@cmpxchg-org.20150623.gappssmtp.com header.s=20150623 header.b="19/OXUit"; spf=pass (google.com: domain of hannes@cmpxchg.org designates 209.85.220.65 as permitted sender) smtp.mailfrom=hannes@cmpxchg.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=cmpxchg.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cmpxchg-org.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:in-reply-to:references:reply-to; bh=7HJ/faUwNp70pvtX2vst2/bX0oNS92n5Rlox7XiLwSM=; b=19/OXUitk9OIFkSFsVCX5dcIBMU6NIzgFeMkUjVxGA8mgaEufARo5yjb5mLA1TDJRJ 7tz3b4g/yMzi/ntkL0A/9eB4bW0HtC6VuyW+BeAGDFEpDYggF88h0aWBoViKtXBBWIMg 2wXxIycHuh3j6iyrOhMDr3Gv6lwOIHXovA+tRjIOcD2PbZhReG8Q0T12Ps7UPosb86rX F2lYPVMoAQughZy/YYoDPMPoXg+DBmZfpvmhgy5oLsoL0OZtAGPFrl/hzW6qOwon8jTr d7qTatvfrseQbH5LX20+ZEnOZyqv4aYFwyRARZZ5jJHU+5vPGjFNDn5cKv2L6/Ez9NI4 KPDQ== X-Google-Smtp-Source: AAOMgpeEj7LBP5DEkolXdB4GCMebS/5xLnIOX/Lx2qxntM2S8M0UuymiFyoewYFVUxtJnzsLc+p9jg== X-Received: by 2002:a0c:9dd0:: with SMTP id p16-v6mr23942032qvf.211.1533136237322; Wed, 01 Aug 2018 08:10:37 -0700 (PDT) Received: from localhost (216.49.36.201.res-cmts.bus.ptd.net. [216.49.36.201]) by smtp.gmail.com with ESMTPSA id a6-v6sm12448202qth.8.2018.08.01.08.10.35 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Wed, 01 Aug 2018 08:10:36 -0700 (PDT) From: Johannes Weiner To: Ingo Molnar , Peter Zijlstra , Andrew Morton , Linus Torvalds Cc: Tejun Heo , Suren Baghdasaryan , Daniel Drake , Vinayak Menon , Christopher Lameter , Mike Galbraith , Shakeel Butt , Peter Enderborg , linux-mm@kvack.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, kernel-team@fb.com Subject: [PATCH 5/9] sched: loadavg: make calc_load_n() public Date: Wed, 1 Aug 2018 11:13:04 -0400 Message-Id: <20180801151308.32234-6-hannes@cmpxchg.org> X-Mailer: git-send-email 2.18.0 In-Reply-To: <20180801151308.32234-1-hannes@cmpxchg.org> References: <20180801151308.32234-1-hannes@cmpxchg.org> Reply-To: "[PATCH 0/9]"@kvack.org, "psi:pressure"@kvack.org, stall@kvack.org, information@kvack.org, for@kvack.org, CPU@kvack.org, memory@kvack.org, and@kvack.org, IO@kvack.org, v3@kvack.org X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: X-Virus-Scanned: ClamAV using ClamSMTP It's going to be used in a later patch. Keep the churn separate. Signed-off-by: Johannes Weiner --- include/linux/sched/loadavg.h | 3 + kernel/sched/loadavg.c | 138 +++++++++++++++++----------------- 2 files changed, 72 insertions(+), 69 deletions(-) diff --git a/include/linux/sched/loadavg.h b/include/linux/sched/loadavg.h index cc9cc62bb1f8..4859bea47a7b 100644 --- a/include/linux/sched/loadavg.h +++ b/include/linux/sched/loadavg.h @@ -37,6 +37,9 @@ calc_load(unsigned long load, unsigned long exp, unsigned long active) return newload / FIXED_1; } +extern unsigned long calc_load_n(unsigned long load, unsigned long exp, + unsigned long active, unsigned int n); + #define LOAD_INT(x) ((x) >> FSHIFT) #define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100) diff --git a/kernel/sched/loadavg.c b/kernel/sched/loadavg.c index 54fbdfb2d86c..28a516575c18 100644 --- a/kernel/sched/loadavg.c +++ b/kernel/sched/loadavg.c @@ -91,6 +91,75 @@ long calc_load_fold_active(struct rq *this_rq, long adjust) return delta; } +/** + * fixed_power_int - compute: x^n, in O(log n) time + * + * @x: base of the power + * @frac_bits: fractional bits of @x + * @n: power to raise @x to. + * + * By exploiting the relation between the definition of the natural power + * function: x^n := x*x*...*x (x multiplied by itself for n times), and + * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i, + * (where: n_i \elem {0, 1}, the binary vector representing n), + * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is + * of course trivially computable in O(log_2 n), the length of our binary + * vector. + */ +static unsigned long +fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n) +{ + unsigned long result = 1UL << frac_bits; + + if (n) { + for (;;) { + if (n & 1) { + result *= x; + result += 1UL << (frac_bits - 1); + result >>= frac_bits; + } + n >>= 1; + if (!n) + break; + x *= x; + x += 1UL << (frac_bits - 1); + x >>= frac_bits; + } + } + + return result; +} + +/* + * a1 = a0 * e + a * (1 - e) + * + * a2 = a1 * e + a * (1 - e) + * = (a0 * e + a * (1 - e)) * e + a * (1 - e) + * = a0 * e^2 + a * (1 - e) * (1 + e) + * + * a3 = a2 * e + a * (1 - e) + * = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e) + * = a0 * e^3 + a * (1 - e) * (1 + e + e^2) + * + * ... + * + * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1] + * = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e) + * = a0 * e^n + a * (1 - e^n) + * + * [1] application of the geometric series: + * + * n 1 - x^(n+1) + * S_n := \Sum x^i = ------------- + * i=0 1 - x + */ +unsigned long +calc_load_n(unsigned long load, unsigned long exp, + unsigned long active, unsigned int n) +{ + return calc_load(load, fixed_power_int(exp, FSHIFT, n), active); +} + #ifdef CONFIG_NO_HZ_COMMON /* * Handle NO_HZ for the global load-average. @@ -210,75 +279,6 @@ static long calc_load_nohz_fold(void) return delta; } -/** - * fixed_power_int - compute: x^n, in O(log n) time - * - * @x: base of the power - * @frac_bits: fractional bits of @x - * @n: power to raise @x to. - * - * By exploiting the relation between the definition of the natural power - * function: x^n := x*x*...*x (x multiplied by itself for n times), and - * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i, - * (where: n_i \elem {0, 1}, the binary vector representing n), - * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is - * of course trivially computable in O(log_2 n), the length of our binary - * vector. - */ -static unsigned long -fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n) -{ - unsigned long result = 1UL << frac_bits; - - if (n) { - for (;;) { - if (n & 1) { - result *= x; - result += 1UL << (frac_bits - 1); - result >>= frac_bits; - } - n >>= 1; - if (!n) - break; - x *= x; - x += 1UL << (frac_bits - 1); - x >>= frac_bits; - } - } - - return result; -} - -/* - * a1 = a0 * e + a * (1 - e) - * - * a2 = a1 * e + a * (1 - e) - * = (a0 * e + a * (1 - e)) * e + a * (1 - e) - * = a0 * e^2 + a * (1 - e) * (1 + e) - * - * a3 = a2 * e + a * (1 - e) - * = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e) - * = a0 * e^3 + a * (1 - e) * (1 + e + e^2) - * - * ... - * - * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1] - * = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e) - * = a0 * e^n + a * (1 - e^n) - * - * [1] application of the geometric series: - * - * n 1 - x^(n+1) - * S_n := \Sum x^i = ------------- - * i=0 1 - x - */ -static unsigned long -calc_load_n(unsigned long load, unsigned long exp, - unsigned long active, unsigned int n) -{ - return calc_load(load, fixed_power_int(exp, FSHIFT, n), active); -} - /* * NO_HZ can leave us missing all per-CPU ticks calling * calc_load_fold_active(), but since a NO_HZ CPU folds its delta into