From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.8 required=3.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_PASS,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id A47F7C10F00 for ; Tue, 12 Mar 2019 10:20:14 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 69FD8214AE for ; Tue, 12 Mar 2019 10:20:14 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ecJrvTTj" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726193AbfCLKUN (ORCPT ); Tue, 12 Mar 2019 06:20:13 -0400 Received: from mail-ed1-f68.google.com ([209.85.208.68]:35571 "EHLO mail-ed1-f68.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726330AbfCLKUN (ORCPT ); Tue, 12 Mar 2019 06:20:13 -0400 Received: by mail-ed1-f68.google.com with SMTP id g19so1804918edp.2 for ; Tue, 12 Mar 2019 03:20:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=CZNEWysFVnPWiT9f/Br2Um9WsTEcPXzKouD+VX9B+Fs=; b=ecJrvTTjlzWRbL5RF7z27qD8U5p9WU4C7sgexSANihSgEIJMY20eMCnugPrIOt29H0 QwdqbYHIdZYRpf3gBqUp9IKpVrB7E6130XrDIQd7SXna1UrhrsnAKHsPH+1315TQ+jEp zLkG1ubVgUAM2VS//aYv3KVeab8O/+lGDnZZQUg2aARTkdlGWtmSANWDWPXjHYFxd1zV JX4MWyUwjfRrnmlHTPkJLkE7yWRJ0XmEjSogZpJPWQ8KCb4WlrsTRoiocGl4yHqnnvOb mrOfjRKH0p6c+9IElAtsYvLJ5Acp+nwCYs56slDNYhwHoSuyhzMAxM1nBScqRmVrmWtj xiJw== 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=CZNEWysFVnPWiT9f/Br2Um9WsTEcPXzKouD+VX9B+Fs=; b=bf8MFUc31bKwvLUV14mhmEnmnO1c0qOx8XOsN1xcVNGG5jFpsoA1vdlZLXr5giTLMW WZjhs4wWEAB+HCygDRQ2p8CZPqyJjkUgk7DYmIpbxob2czW6QWIw4Tq2OLrUKuFlaAjA E/hwIENepvuDNuollrZbTPLQluq0N1bbH8KgmHlQJRKrtO8unVt1wlYKdF03k46cUj8B cmtCWeZqgGYVxSlVHPzfvgWpzJSQb9+dA0ruaHTjCSOLMu/SvFL3BGkv14iwuNQgE70G jtGlvJYbpY+6AKpl53u8r8BxHsTUKjtSD6G9hblIjJNajb6bzweup5oJbyTPA26Y3gWn Og1A== X-Gm-Message-State: APjAAAVp5Jq4S/XjrUNrbr6GqIcuxTyVY4FqNEAGA5LpP7YxrfYYsubK yuQMO17RYUWPVqsULTrtYKw= X-Google-Smtp-Source: APXvYqzMqVswpj+eJXwVFESIDbVI9MV33CV5YFLUf3nyGbffSdYdl0ZnL6dUe4U7grcyTVgL0HJ2kA== X-Received: by 2002:a05:6402:1682:: with SMTP id a2mr2719092edv.158.1552386011526; Tue, 12 Mar 2019 03:20:11 -0700 (PDT) Received: from jwang-pc.pb.local ([2001:1438:4010:254c:1e6f:65ff:fed4:d10]) by smtp.gmail.com with ESMTPSA id q12sm408698edd.12.2019.03.12.03.20.10 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 12 Mar 2019 03:20:10 -0700 (PDT) From: Jack Wang To: gregkh@linuxfoundation.org, stable@vger.kernel.org Cc: Johannes Weiner , Christopher Lameter , Ingo Molnar , Johannes Weiner , Mike Galbraith , Peter Enderborg , Randy Dunlap , Shakeel Butt , Tejun Heo , Vinayak Menon , Andrew Morton , Linus Torvalds , Jack Wang Subject: [stable-4.14 05/11] sched: loadavg: make calc_load_n() public Date: Tue, 12 Mar 2019 11:19:56 +0100 Message-Id: <20190312102002.31737-6-jinpuwang@gmail.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20190312102002.31737-1-jinpuwang@gmail.com> References: <20190312102002.31737-1-jinpuwang@gmail.com> Sender: stable-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: stable@vger.kernel.org From: Johannes Weiner It's going to be used in a later patch. Keep the churn separate. Link: http://lkml.kernel.org/r/20180828172258.3185-6-hannes@cmpxchg.org Signed-off-by: Johannes Weiner Acked-by: Peter Zijlstra (Intel) Tested-by: Suren Baghdasaryan Tested-by: Daniel Drake Cc: Christopher Lameter Cc: Ingo Molnar Cc: Johannes Weiner Cc: Mike Galbraith Cc: Peter Enderborg Cc: Randy Dunlap Cc: Shakeel Butt Cc: Tejun Heo Cc: Vinayak Menon Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds (cherry picked from commit b56b064dcf9358d4d5869130483c4e2d0ff5df6f) Signed-off-by: Jack Wang --- 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 d37eb9fe8aa8..73157e882918 100644 --- a/kernel/sched/loadavg.c +++ b/kernel/sched/loadavg.c @@ -95,6 +95,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. @@ -214,75 +283,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 -- 2.17.1