1 // SPDX-License-Identifier: GPL-2.0
13  * Global load-average calculations
15  * We take a distributed and async approach to calculating the global load-avg
25  *	nr_active += cpu_of(cpu)->nr_running + cpu_of(cpu)->nr_uninterruptible;
27  *   avenrun[n] = avenrun[0] * exp_n + nr_active * (1 - exp_n)
31  *  - for_each_possible_cpu() is prohibitively expensive on machines with
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) }
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
42  *    Furthermore, in order to avoid synchronizing all per-CPU delta folding
46  *    This places an upper-bound on the IRQ-off latency of the machine. Then
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
56  *  This covers the NO_HZ=n code, for extra head-aches, see the comment below.
66  * get_avenrun - get the load average array
84 	nr_active = this_rq->nr_running - adjust;  in calc_load_fold_active()
85 	nr_active += (long)this_rq->nr_uninterruptible;  in calc_load_fold_active()
87 	if (nr_active != this_rq->calc_load_active) {  in calc_load_fold_active()
88 		delta = nr_active - this_rq->calc_load_active;  in calc_load_fold_active()
89 		this_rq->calc_load_active = nr_active;  in calc_load_fold_active()
96  * fixed_power_int - compute: x^n, in O(log n) time
98  * @x:         base of the power
99  * @frac_bits: fractional bits of @x
100  * @n:         power to raise @x to.
103  * function: x^n := x*x*...*x (x multiplied by itself for n times), and
106  * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
111 fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)  in fixed_power_int()  argument
118 				result *= x;  in fixed_power_int()
119 				result += 1UL << (frac_bits - 1);  in fixed_power_int()
125 			x *= x;  in fixed_power_int()
126 			x += 1UL << (frac_bits - 1);  in fixed_power_int()
127 			x >>= frac_bits;  in fixed_power_int()
135  * a1 = a0 * e + a * (1 - e)
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)
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)
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)
153  *              n         1 - x^(n+1)
154  *     S_n := \Sum x^i = -------------
155  *             i=0          1 - x
166  * Handle NO_HZ for the global load-average.
169  * load-average relies on per-CPU sampling from the tick, it is affected by
172  * The basic idea is to fold the nr_active delta into a global NO_HZ-delta upon
178  *  - When we go NO_HZ idle during the window, we can negate our sample
179  *    contribution, causing under-accounting.
181  *    We avoid this by keeping two NO_HZ-delta counters and flipping them
184  *    The only trick is the slight shift in index flip for read vs write.
188  *        |-|-----------|-|-----------|-|-----------|-|
195  *  - When we wake up from NO_HZ during the window, we push up our
200  *    sample, for this CPU (effectively using the NO_HZ-delta for this CPU which
222 	 * next NO_HZ-delta.  in calc_load_write_idx()
272 	this_rq->calc_load_update = READ_ONCE(calc_load_update);  in calc_load_nohz_stop()
273 	if (time_before(jiffies, this_rq->calc_load_update))  in calc_load_nohz_stop()
281 	if (time_before(jiffies, this_rq->calc_load_update + 10))  in calc_load_nohz_stop()
282 		this_rq->calc_load_update += LOAD_FREQ;  in calc_load_nohz_stop()
297  * NO_HZ can leave us missing all per-CPU ticks calling
313 		 * Catch-up, fold however many we are behind still  in calc_global_nohz()
315 		delta = jiffies - sample_window - 10;  in calc_global_nohz()
329 	 * Flip the NO_HZ index...  in calc_global_nohz()
331 	 * Make sure we first write the new time then flip the index, so that  in calc_global_nohz()
333 	 * index, this avoids a double flip messing things up.  in calc_global_nohz()
346  * calc_load - update the avenrun load estimates 10 ticks after the
361 	 * Fold the 'old' NO_HZ-delta to include all NO_HZ CPUs.  in calc_global_load()
391 	if (time_before(jiffies, this_rq->calc_load_update))  in calc_global_load_tick()
398 	this_rq->calc_load_update += LOAD_FREQ;  in calc_global_load_tick()