From patchwork Mon May 7 21:01:33 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Johannes Weiner X-Patchwork-Id: 10384791 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id DC6C560353 for ; Mon, 7 May 2018 21:00:17 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B6B0928B24 for ; Mon, 7 May 2018 21:00:17 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A69C628B4A; Mon, 7 May 2018 21:00:17 +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 14DDC28B24 for ; Mon, 7 May 2018 21:00:17 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4F8986B026F; Mon, 7 May 2018 17:00:15 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 4A7C76B0270; Mon, 7 May 2018 17:00:15 -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 373C86B0271; Mon, 7 May 2018 17:00:15 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-wm0-f70.google.com (mail-wm0-f70.google.com [74.125.82.70]) by kanga.kvack.org (Postfix) with ESMTP id D4A866B0270 for ; Mon, 7 May 2018 17:00:14 -0400 (EDT) Received: by mail-wm0-f70.google.com with SMTP id t195-v6so85772wmt.9 for ; Mon, 07 May 2018 14:00:14 -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; bh=Q9tf/aX05pddBBcSMfINSla3wt3pXRBjeLsf3chgvp0=; b=kN9QEt9bW9zha61OCwqmdrmGYGDxwBMb4v0DyEbULLwMasFWZvqeyf8TCLLN49Im1K 6SjKYtLDdmmHPUGR2BPvuQBE9wDH5x6jf3ZTTg8/fqRXuOJJHzCbBNJuYuf4V+tbdTT0 SocSj53dhaqHaoOgfNQlyM1eoVZ9n4JdF494J5wsS7AdVBUmIUZX+TmQ2hPJklSySN+b qwnuKt3gS8ny330KIeNowzakwmC/ao+E5D+2ddth9KlSvGr0zrPg8NgGjFsRL3vreg68 yugV+h2xb72Dfo/Fs+ZBfaBFgyBc3Hh27WNcDkdUuF+4f+oYxO67dFXWstALGd5DfUnw bT8w== X-Gm-Message-State: ALQs6tDke/eq7+SrzXlUZVUj2WV3Al4NNX/vUG6cd0Q2lNLuK6PKg1xB Ad87rKLv98G7cNfU40O/8Z0uWaGLzuNmx2TjWHkgLFzmijk/Chirsb0vHRlu7GZStxGO2yBFvnM zXLbHMSsY4DmmidmuC7Hyl+Vk+0ej6eBiGufsSi9ZHa4gG6Ovipm1atha558xyZ/95g== X-Received: by 2002:a50:b1e2:: with SMTP id n31-v6mr52268530edd.197.1525726814412; Mon, 07 May 2018 14:00:14 -0700 (PDT) X-Google-Smtp-Source: AB8JxZq8tiSfEiorp63OslspB35g6gQr691N32AY2DwYfpth0Y+9/SY1RFgPMLnYw4qDq5Va3hln X-Received: by 2002:a50:b1e2:: with SMTP id n31-v6mr52268479edd.197.1525726813588; Mon, 07 May 2018 14:00:13 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1525726813; cv=none; d=google.com; s=arc-20160816; b=kXtzdkOklaFAJ/UDbgWJC8mVbcmaKLAGuTHLmS5eoieB51v7SE9HCdRw70iPFvYnTG YMVG1dG6JTC4uECT6CeZgSEC+F6w/2xhFXkFUESwtogooHWPwIzSf2Gcwj7oIBprKTox K55nHhdqkYPL/QPvpbZd8Nw8bJW13eahhHEWjz7+lStLar1z6885X8n9QJQfg7JgtH9Y MtcdNDdNTDmeqWKL8MKqMXJXVjXrcOpaB7rJc5tLTv8t+V8PHD1ypYlKE6KvRLmDb43d N1PZRchqxzL/L/mLzt1EkyQqJ5USafar61yJXJG/V7JE4TmzXKbkMresJONAch2+qt6W Zr8A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature:arc-authentication-results; bh=Q9tf/aX05pddBBcSMfINSla3wt3pXRBjeLsf3chgvp0=; b=i9HBoXSY1Vyb3E8lrn9jeppVyLsthr2zuQEdv9495PS2TN8KRPe7uzjXnGz36ap67p EuVfJiOmGxgSNeq5PKYSw7su3/wZFuk3pd5vFU9H/+xtDrcR+YnUcoNIrBshWjVgVfb/ s+R8q0g3Wyz7M1HCLH5+ryr3nUdAj1F6EycC0WSEmBiW2uxg2vfYu/BksmICh7ijnlbP yDReiPx6REo5H0Jej8HZb+9Fvjg2K4ZgUYeZKOYnVSWW5gSrr/EiXKcxoiOVmHqvLDbo ONdQ+pM+YRhXc/zz9XxINCeirYudSgeVroakOX28e9uv10jvZO2b3HaQthMedrHjuVER n8mA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@cmpxchg.org header.s=x header.b=RmO+/FrV; spf=pass (google.com: domain of hannes@cmpxchg.org designates 85.214.110.215 as permitted sender) smtp.mailfrom=hannes@cmpxchg.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=cmpxchg.org Received: from gum.cmpxchg.org (gum.cmpxchg.org. [85.214.110.215]) by mx.google.com with ESMTPS id y63-v6si2275439edy.418.2018.05.07.14.00.13 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 07 May 2018 14:00:13 -0700 (PDT) Received-SPF: pass (google.com: domain of hannes@cmpxchg.org designates 85.214.110.215 as permitted sender) client-ip=85.214.110.215; Authentication-Results: mx.google.com; dkim=pass header.i=@cmpxchg.org header.s=x header.b=RmO+/FrV; spf=pass (google.com: domain of hannes@cmpxchg.org designates 85.214.110.215 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; q=dns/txt; c=relaxed/relaxed; d=cmpxchg.org ; s=x; h=References:In-Reply-To:Message-Id:Date:Subject:Cc:To:From:Sender: Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding:Content-ID: Content-Description:Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc :Resent-Message-ID:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=Q9tf/aX05pddBBcSMfINSla3wt3pXRBjeLsf3chgvp0=; b=RmO+/FrVyVnL4yCOTItqEvd/iQ TGGGSTEsRQ1CxTOcEQiZ3iirslPVfEJ7qRa4kuQrHpSJNkYyvmfB+aPVMuLJ1up072cko4HSeeRKb 4BFouTtFYiN1UEWLsvwNwkfgi6de3ORl416bznDbdKbHd0diyBd4GuS59OU94E4trpyY=; From: Johannes Weiner To: linux-kernel@vger.kernel.org, linux-mm@kvack.org, linux-block@vger.kernel.org, cgroups@vger.kernel.org Cc: Ingo Molnar , Peter Zijlstra , Andrew Morton , Tejun Heo , Balbir Singh , Mike Galbraith , Oliver Yang , Shakeel Butt , xxx xxx , Taras Kondratiuk , Daniel Walker , Vinayak Menon , Ruslan Ruslichenko , kernel-team@fb.com Subject: [PATCH 5/7] sched: loadavg: make calc_load_n() public Date: Mon, 7 May 2018 17:01:33 -0400 Message-Id: <20180507210135.1823-6-hannes@cmpxchg.org> X-Mailer: git-send-email 2.17.0 In-Reply-To: <20180507210135.1823-1-hannes@cmpxchg.org> References: <20180507210135.1823-1-hannes@cmpxchg.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 the following patch. Keep the churn separate. Signed-off-by: Johannes Weiner --- include/linux/sched/loadavg.h | 69 +++++++++++++++++++++++++++++++++++ kernel/sched/loadavg.c | 69 ----------------------------------- 2 files changed, 69 insertions(+), 69 deletions(-) diff --git a/include/linux/sched/loadavg.h b/include/linux/sched/loadavg.h index cc9cc62bb1f8..0e4c24978751 100644 --- a/include/linux/sched/loadavg.h +++ b/include/linux/sched/loadavg.h @@ -37,6 +37,75 @@ calc_load(unsigned long load, unsigned long exp, unsigned long active) return newload / FIXED_1; } +/** + * 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 inline 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 inline 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); +} + #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..0736e349a54e 100644 --- a/kernel/sched/loadavg.c +++ b/kernel/sched/loadavg.c @@ -210,75 +210,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