loadavg.c

  1// SPDX-License-Identifier: GPL-2.0
  2/*
  3 * kernel/sched/loadavg.c
  4 *
  5 * This file contains the magic bits required to compute the global loadavg
  6 * figure. Its a silly number but people think its important. We go through
  7 * great pains to make it work on big machines and tickless kernels.
  8 */
  9#include <linux/sched/nohz.h>
 10#include "sched.h"
 11
 12/*
 13 * Global load-average calculations
 14 *
 15 * We take a distributed and async approach to calculating the global load-avg
 16 * in order to minimize overhead.
 17 *
 18 * The global load average is an exponentially decaying average of nr_running +
 19 * nr_uninterruptible.
 20 *
 21 * Once every LOAD_FREQ:
 22 *
 23 *   nr_active = 0;
 24 *   for_each_possible_cpu(cpu)
 25 *	nr_active += cpu_of(cpu)->nr_running + cpu_of(cpu)->nr_uninterruptible;
 26 *
 27 *   avenrun[n] = avenrun[0] * exp_n + nr_active * (1 - exp_n)
 28 *
 29 * Due to a number of reasons the above turns in the mess below:
 30 *
 31 *  - for_each_possible_cpu() is prohibitively expensive on machines with
 32 *    serious number of CPUs, therefore we need to take a distributed approach
 33 *    to calculating nr_active.
 34 *
 35 *        \Sum_i x_i(t) = \Sum_i x_i(t) - x_i(t_0) | x_i(t_0) := 0
 36 *                      = \Sum_i { \Sum_j=1 x_i(t_j) - x_i(t_j-1) }
 37 *
 38 *    So assuming nr_active := 0 when we start out -- true per definition, we
 39 *    can simply take per-CPU deltas and fold those into a global accumulate
 40 *    to obtain the same result. See calc_load_fold_active().
 41 *
 42 *    Furthermore, in order to avoid synchronizing all per-CPU delta folding
 43 *    across the machine, we assume 10 ticks is sufficient time for every
 44 *    CPU to have completed this task.
 45 *
 46 *    This places an upper-bound on the IRQ-off latency of the machine. Then
 47 *    again, being late doesn't loose the delta, just wrecks the sample.
 48 *
 49 *  - cpu_rq()->nr_uninterruptible isn't accurately tracked per-CPU because
 50 *    this would add another cross-CPU cache-line miss and atomic operation
 51 *    to the wakeup path. Instead we increment on whatever CPU the task ran
 52 *    when it went into uninterruptible state and decrement on whatever CPU
 53 *    did the wakeup. This means that only the sum of nr_uninterruptible over
 54 *    all CPUs yields the correct result.
 55 *
 56 *  This covers the NO_HZ=n code, for extra head-aches, see the comment below.
 57 */
 58
 59/* Variables and functions for calc_load */
 60atomic_long_t calc_load_tasks;
 61unsigned long calc_load_update;
 62unsigned long avenrun[3];
 63EXPORT_SYMBOL(avenrun); /* should be removed */
 64
 65/**
 66 * get_avenrun - get the load average array
 67 * @loads:	pointer to destination load array
 68 * @offset:	offset to add
 69 * @shift:	shift count to shift the result left
 70 *
 71 * These values are estimates at best, so no need for locking.
 72 */
 73void get_avenrun(unsigned long *loads, unsigned long offset, int shift)
 74{
 75	loads[0] = (avenrun[0] + offset) << shift;
 76	loads[1] = (avenrun[1] + offset) << shift;
 77	loads[2] = (avenrun[2] + offset) << shift;
 78}
 79
 80long calc_load_fold_active(struct rq *this_rq, long adjust)
 81{
 82	long nr_active, delta = 0;
 83
 84	nr_active = this_rq->nr_running - adjust;
 85	nr_active += (long)this_rq->nr_uninterruptible;
 86
 87	if (nr_active != this_rq->calc_load_active) {
 88		delta = nr_active - this_rq->calc_load_active;
 89		this_rq->calc_load_active = nr_active;
 90	}
 91
 92	return delta;
 93}
 94
 95/**
 96 * fixed_power_int - compute: x^n, in O(log n) time
 97 *
 98 * @x:         base of the power
 99 * @frac_bits: fractional bits of @x
100 * @n:         power to raise @x to.
101 *
102 * By exploiting the relation between the definition of the natural power
103 * function: x^n := x*x*...*x (x multiplied by itself for n times), and
104 * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
105 * (where: n_i \elem {0, 1}, the binary vector representing n),
106 * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
107 * of course trivially computable in O(log_2 n), the length of our binary
108 * vector.
109 */
110static unsigned long
111fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
112{
113	unsigned long result = 1UL << frac_bits;
114
115	if (n) {
116		for (;;) {
117			if (n & 1) {
118				result *= x;
119				result += 1UL << (frac_bits - 1);
120				result >>= frac_bits;
121			}
122			n >>= 1;
123			if (!n)
124				break;
125			x *= x;
126			x += 1UL << (frac_bits - 1);
127			x >>= frac_bits;
128		}
129	}
130
131	return result;
132}
133
134/*
135 * a1 = a0 * e + a * (1 - e)
136 *
137 * a2 = a1 * e + a * (1 - e)
138 *    = (a0 * e + a * (1 - e)) * e + a * (1 - e)
139 *    = a0 * e^2 + a * (1 - e) * (1 + e)
140 *
141 * a3 = a2 * e + a * (1 - e)
142 *    = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
143 *    = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
144 *
145 *  ...
146 *
147 * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
148 *    = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
149 *    = a0 * e^n + a * (1 - e^n)
150 *
151 * [1] application of the geometric series:
152 *
153 *              n         1 - x^(n+1)
154 *     S_n := \Sum x^i = -------------
155 *             i=0          1 - x
156 */
157unsigned long
158calc_load_n(unsigned long load, unsigned long exp,
159	    unsigned long active, unsigned int n)
160{
161	return calc_load(load, fixed_power_int(exp, FSHIFT, n), active);
162}
163
164#ifdef CONFIG_NO_HZ_COMMON
165/*
166 * Handle NO_HZ for the global load-average.
167 *
168 * Since the above described distributed algorithm to compute the global
169 * load-average relies on per-CPU sampling from the tick, it is affected by
170 * NO_HZ.
171 *
172 * The basic idea is to fold the nr_active delta into a global NO_HZ-delta upon
173 * entering NO_HZ state such that we can include this as an 'extra' CPU delta
174 * when we read the global state.
175 *
176 * Obviously reality has to ruin such a delightfully simple scheme:
177 *
178 *  - When we go NO_HZ idle during the window, we can negate our sample
179 *    contribution, causing under-accounting.
180 *
181 *    We avoid this by keeping two NO_HZ-delta counters and flipping them
182 *    when the window starts, thus separating old and new NO_HZ load.
183 *
184 *    The only trick is the slight shift in index flip for read vs write.
185 *
186 *        0s            5s            10s           15s
187 *          +10           +10           +10           +10
188 *        |-|-----------|-|-----------|-|-----------|-|
189 *    r:0 0 1           1 0           0 1           1 0
190 *    w:0 1 1           0 0           1 1           0 0
191 *
192 *    This ensures we'll fold the old NO_HZ contribution in this window while
193 *    accumulating the new one.
194 *
195 *  - When we wake up from NO_HZ during the window, we push up our
196 *    contribution, since we effectively move our sample point to a known
197 *    busy state.
198 *
199 *    This is solved by pushing the window forward, and thus skipping the
200 *    sample, for this CPU (effectively using the NO_HZ-delta for this CPU which
201 *    was in effect at the time the window opened). This also solves the issue
202 *    of having to deal with a CPU having been in NO_HZ for multiple LOAD_FREQ
203 *    intervals.
204 *
205 * When making the ILB scale, we should try to pull this in as well.
206 */
207static atomic_long_t calc_load_nohz[2];
208static int calc_load_idx;
209
210static inline int calc_load_write_idx(void)
211{
212	int idx = calc_load_idx;
213
214	/*
215	 * See calc_global_nohz(), if we observe the new index, we also
216	 * need to observe the new update time.
217	 */
218	smp_rmb();
219
220	/*
221	 * If the folding window started, make sure we start writing in the
222	 * next NO_HZ-delta.
223	 */
224	if (!time_before(jiffies, READ_ONCE(calc_load_update)))
225		idx++;
226
227	return idx & 1;
228}
229
230static inline int calc_load_read_idx(void)
231{
232	return calc_load_idx & 1;
233}
234
235static void calc_load_nohz_fold(struct rq *rq)
236{
237	long delta;
238
239	delta = calc_load_fold_active(rq, 0);
240	if (delta) {
241		int idx = calc_load_write_idx();
242
243		atomic_long_add(delta, &calc_load_nohz[idx]);
244	}
245}
246
247void calc_load_nohz_start(void)
248{
249	/*
250	 * We're going into NO_HZ mode, if there's any pending delta, fold it
251	 * into the pending NO_HZ delta.
252	 */
253	calc_load_nohz_fold(this_rq());
254}
255
256/*
257 * Keep track of the load for NOHZ_FULL, must be called between
258 * calc_load_nohz_{start,stop}().
259 */
260void calc_load_nohz_remote(struct rq *rq)
261{
262	calc_load_nohz_fold(rq);
263}
264
265void calc_load_nohz_stop(void)
266{
267	struct rq *this_rq = this_rq();
268
269	/*
270	 * If we're still before the pending sample window, we're done.
271	 */
272	this_rq->calc_load_update = READ_ONCE(calc_load_update);
273	if (time_before(jiffies, this_rq->calc_load_update))
274		return;
275
276	/*
277	 * We woke inside or after the sample window, this means we're already
278	 * accounted through the nohz accounting, so skip the entire deal and
279	 * sync up for the next window.
280	 */
281	if (time_before(jiffies, this_rq->calc_load_update + 10))
282		this_rq->calc_load_update += LOAD_FREQ;
283}
284
285static long calc_load_nohz_read(void)
286{
287	int idx = calc_load_read_idx();
288	long delta = 0;
289
290	if (atomic_long_read(&calc_load_nohz[idx]))
291		delta = atomic_long_xchg(&calc_load_nohz[idx], 0);
292
293	return delta;
294}
295
296/*
297 * NO_HZ can leave us missing all per-CPU ticks calling
298 * calc_load_fold_active(), but since a NO_HZ CPU folds its delta into
299 * calc_load_nohz per calc_load_nohz_start(), all we need to do is fold
300 * in the pending NO_HZ delta if our NO_HZ period crossed a load cycle boundary.
301 *
302 * Once we've updated the global active value, we need to apply the exponential
303 * weights adjusted to the number of cycles missed.
304 */
305static void calc_global_nohz(void)
306{
307	unsigned long sample_window;
308	long delta, active, n;
309
310	sample_window = READ_ONCE(calc_load_update);
311	if (!time_before(jiffies, sample_window + 10)) {
312		/*
313		 * Catch-up, fold however many we are behind still
314		 */
315		delta = jiffies - sample_window - 10;
316		n = 1 + (delta / LOAD_FREQ);
317
318		active = atomic_long_read(&calc_load_tasks);
319		active = active > 0 ? active * FIXED_1 : 0;
320
321		avenrun[0] = calc_load_n(avenrun[0], EXP_1, active, n);
322		avenrun[1] = calc_load_n(avenrun[1], EXP_5, active, n);
323		avenrun[2] = calc_load_n(avenrun[2], EXP_15, active, n);
324
325		WRITE_ONCE(calc_load_update, sample_window + n * LOAD_FREQ);
326	}
327
328	/*
329	 * Flip the NO_HZ index...
330	 *
331	 * Make sure we first write the new time then flip the index, so that
332	 * calc_load_write_idx() will see the new time when it reads the new
333	 * index, this avoids a double flip messing things up.
334	 */
335	smp_wmb();
336	calc_load_idx++;
337}
338#else /* !CONFIG_NO_HZ_COMMON: */
339
340static inline long calc_load_nohz_read(void) { return 0; }
341static inline void calc_global_nohz(void) { }
342
343#endif /* !CONFIG_NO_HZ_COMMON */
344
345/*
346 * calc_load - update the avenrun load estimates 10 ticks after the
347 * CPUs have updated calc_load_tasks.
348 *
349 * Called from the global timer code.
350 */
351void calc_global_load(void)
352{
353	unsigned long sample_window;
354	long active, delta;
355
356	sample_window = READ_ONCE(calc_load_update);
357	if (time_before(jiffies, sample_window + 10))
358		return;
359
360	/*
361	 * Fold the 'old' NO_HZ-delta to include all NO_HZ CPUs.
362	 */
363	delta = calc_load_nohz_read();
364	if (delta)
365		atomic_long_add(delta, &calc_load_tasks);
366
367	active = atomic_long_read(&calc_load_tasks);
368	active = active > 0 ? active * FIXED_1 : 0;
369
370	avenrun[0] = calc_load(avenrun[0], EXP_1, active);
371	avenrun[1] = calc_load(avenrun[1], EXP_5, active);
372	avenrun[2] = calc_load(avenrun[2], EXP_15, active);
373
374	WRITE_ONCE(calc_load_update, sample_window + LOAD_FREQ);
375
376	/*
377	 * In case we went to NO_HZ for multiple LOAD_FREQ intervals
378	 * catch up in bulk.
379	 */
380	calc_global_nohz();
381}
382
383/*
384 * Called from sched_tick() to periodically update this CPU's
385 * active count.
386 */
387void calc_global_load_tick(struct rq *this_rq)
388{
389	long delta;
390
391	if (time_before(jiffies, this_rq->calc_load_update))
392		return;
393
394	delta  = calc_load_fold_active(this_rq, 0);
395	if (delta)
396		atomic_long_add(delta, &calc_load_tasks);
397
398	this_rq->calc_load_update += LOAD_FREQ;
399}