1 // SPDX-License-Identifier: GPL-2.0
3 * kernel/sched/loadavg.c
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.
10 #include <linux/export.h>
11 #include <linux/sched/loadavg.h>
16 * Global load-average calculations
18 * We take a distributed and async approach to calculating the global load-avg
19 * in order to minimize overhead.
21 * The global load average is an exponentially decaying average of nr_running +
24 * Once every LOAD_FREQ:
27 * for_each_possible_cpu(cpu)
28 * nr_active += cpu_of(cpu)->nr_running + cpu_of(cpu)->nr_uninterruptible;
30 * avenrun[n] = avenrun[0] * exp_n + nr_active * (1 - exp_n)
32 * Due to a number of reasons the above turns in the mess below:
34 * - for_each_possible_cpu() is prohibitively expensive on machines with
35 * serious number of cpus, therefore we need to take a distributed approach
36 * to calculating nr_active.
38 * \Sum_i x_i(t) = \Sum_i x_i(t) - x_i(t_0) | x_i(t_0) := 0
39 * = \Sum_i { \Sum_j=1 x_i(t_j) - x_i(t_j-1) }
41 * So assuming nr_active := 0 when we start out -- true per definition, we
42 * can simply take per-cpu deltas and fold those into a global accumulate
43 * to obtain the same result. See calc_load_fold_active().
45 * Furthermore, in order to avoid synchronizing all per-cpu delta folding
46 * across the machine, we assume 10 ticks is sufficient time for every
47 * cpu to have completed this task.
49 * This places an upper-bound on the IRQ-off latency of the machine. Then
50 * again, being late doesn't loose the delta, just wrecks the sample.
52 * - cpu_rq()->nr_uninterruptible isn't accurately tracked per-cpu because
53 * this would add another cross-cpu cacheline miss and atomic operation
54 * to the wakeup path. Instead we increment on whatever cpu the task ran
55 * when it went into uninterruptible state and decrement on whatever cpu
56 * did the wakeup. This means that only the sum of nr_uninterruptible over
57 * all cpus yields the correct result.
59 * This covers the NO_HZ=n code, for extra head-aches, see the comment below.
62 /* Variables and functions for calc_load */
63 atomic_long_t calc_load_tasks
;
64 unsigned long calc_load_update
;
65 unsigned long avenrun
[3];
66 EXPORT_SYMBOL(avenrun
); /* should be removed */
69 * get_avenrun - get the load average array
70 * @loads: pointer to dest load array
71 * @offset: offset to add
72 * @shift: shift count to shift the result left
74 * These values are estimates at best, so no need for locking.
76 void get_avenrun(unsigned long *loads
, unsigned long offset
, int shift
)
78 loads
[0] = (avenrun
[0] + offset
) << shift
;
79 loads
[1] = (avenrun
[1] + offset
) << shift
;
80 loads
[2] = (avenrun
[2] + offset
) << shift
;
83 long calc_load_fold_active(struct rq
*this_rq
, long adjust
)
85 long nr_active
, delta
= 0;
87 nr_active
= this_rq
->nr_running
- adjust
;
88 nr_active
+= (long)this_rq
->nr_uninterruptible
;
90 if (nr_active
!= this_rq
->calc_load_active
) {
91 delta
= nr_active
- this_rq
->calc_load_active
;
92 this_rq
->calc_load_active
= nr_active
;
99 * a1 = a0 * e + a * (1 - e)
102 calc_load(unsigned long load
, unsigned long exp
, unsigned long active
)
104 unsigned long newload
;
106 newload
= load
* exp
+ active
* (FIXED_1
- exp
);
108 newload
+= FIXED_1
-1;
110 return newload
/ FIXED_1
;
113 #ifdef CONFIG_NO_HZ_COMMON
115 * Handle NO_HZ for the global load-average.
117 * Since the above described distributed algorithm to compute the global
118 * load-average relies on per-cpu sampling from the tick, it is affected by
121 * The basic idea is to fold the nr_active delta into a global NO_HZ-delta upon
122 * entering NO_HZ state such that we can include this as an 'extra' cpu delta
123 * when we read the global state.
125 * Obviously reality has to ruin such a delightfully simple scheme:
127 * - When we go NO_HZ idle during the window, we can negate our sample
128 * contribution, causing under-accounting.
130 * We avoid this by keeping two NO_HZ-delta counters and flipping them
131 * when the window starts, thus separating old and new NO_HZ load.
133 * The only trick is the slight shift in index flip for read vs write.
137 * |-|-----------|-|-----------|-|-----------|-|
138 * r:0 0 1 1 0 0 1 1 0
139 * w:0 1 1 0 0 1 1 0 0
141 * This ensures we'll fold the old NO_HZ contribution in this window while
142 * accumlating the new one.
144 * - When we wake up from NO_HZ during the window, we push up our
145 * contribution, since we effectively move our sample point to a known
148 * This is solved by pushing the window forward, and thus skipping the
149 * sample, for this cpu (effectively using the NO_HZ-delta for this cpu which
150 * was in effect at the time the window opened). This also solves the issue
151 * of having to deal with a cpu having been in NO_HZ for multiple LOAD_FREQ
154 * When making the ILB scale, we should try to pull this in as well.
156 static atomic_long_t calc_load_nohz
[2];
157 static int calc_load_idx
;
159 static inline int calc_load_write_idx(void)
161 int idx
= calc_load_idx
;
164 * See calc_global_nohz(), if we observe the new index, we also
165 * need to observe the new update time.
170 * If the folding window started, make sure we start writing in the
173 if (!time_before(jiffies
, READ_ONCE(calc_load_update
)))
179 static inline int calc_load_read_idx(void)
181 return calc_load_idx
& 1;
184 void calc_load_nohz_start(void)
186 struct rq
*this_rq
= this_rq();
190 * We're going into NO_HZ mode, if there's any pending delta, fold it
191 * into the pending NO_HZ delta.
193 delta
= calc_load_fold_active(this_rq
, 0);
195 int idx
= calc_load_write_idx();
197 atomic_long_add(delta
, &calc_load_nohz
[idx
]);
201 void calc_load_nohz_stop(void)
203 struct rq
*this_rq
= this_rq();
206 * If we're still before the pending sample window, we're done.
208 this_rq
->calc_load_update
= READ_ONCE(calc_load_update
);
209 if (time_before(jiffies
, this_rq
->calc_load_update
))
213 * We woke inside or after the sample window, this means we're already
214 * accounted through the nohz accounting, so skip the entire deal and
215 * sync up for the next window.
217 if (time_before(jiffies
, this_rq
->calc_load_update
+ 10))
218 this_rq
->calc_load_update
+= LOAD_FREQ
;
221 static long calc_load_nohz_fold(void)
223 int idx
= calc_load_read_idx();
226 if (atomic_long_read(&calc_load_nohz
[idx
]))
227 delta
= atomic_long_xchg(&calc_load_nohz
[idx
], 0);
233 * fixed_power_int - compute: x^n, in O(log n) time
235 * @x: base of the power
236 * @frac_bits: fractional bits of @x
237 * @n: power to raise @x to.
239 * By exploiting the relation between the definition of the natural power
240 * function: x^n := x*x*...*x (x multiplied by itself for n times), and
241 * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
242 * (where: n_i \elem {0, 1}, the binary vector representing n),
243 * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
244 * of course trivially computable in O(log_2 n), the length of our binary
248 fixed_power_int(unsigned long x
, unsigned int frac_bits
, unsigned int n
)
250 unsigned long result
= 1UL << frac_bits
;
256 result
+= 1UL << (frac_bits
- 1);
257 result
>>= frac_bits
;
263 x
+= 1UL << (frac_bits
- 1);
272 * a1 = a0 * e + a * (1 - e)
274 * a2 = a1 * e + a * (1 - e)
275 * = (a0 * e + a * (1 - e)) * e + a * (1 - e)
276 * = a0 * e^2 + a * (1 - e) * (1 + e)
278 * a3 = a2 * e + a * (1 - e)
279 * = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
280 * = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
284 * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
285 * = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
286 * = a0 * e^n + a * (1 - e^n)
288 * [1] application of the geometric series:
291 * S_n := \Sum x^i = -------------
295 calc_load_n(unsigned long load
, unsigned long exp
,
296 unsigned long active
, unsigned int n
)
298 return calc_load(load
, fixed_power_int(exp
, FSHIFT
, n
), active
);
302 * NO_HZ can leave us missing all per-cpu ticks calling
303 * calc_load_fold_active(), but since a NO_HZ CPU folds its delta into
304 * calc_load_nohz per calc_load_nohz_start(), all we need to do is fold
305 * in the pending NO_HZ delta if our NO_HZ period crossed a load cycle boundary.
307 * Once we've updated the global active value, we need to apply the exponential
308 * weights adjusted to the number of cycles missed.
310 static void calc_global_nohz(void)
312 unsigned long sample_window
;
313 long delta
, active
, n
;
315 sample_window
= READ_ONCE(calc_load_update
);
316 if (!time_before(jiffies
, sample_window
+ 10)) {
318 * Catch-up, fold however many we are behind still
320 delta
= jiffies
- sample_window
- 10;
321 n
= 1 + (delta
/ LOAD_FREQ
);
323 active
= atomic_long_read(&calc_load_tasks
);
324 active
= active
> 0 ? active
* FIXED_1
: 0;
326 avenrun
[0] = calc_load_n(avenrun
[0], EXP_1
, active
, n
);
327 avenrun
[1] = calc_load_n(avenrun
[1], EXP_5
, active
, n
);
328 avenrun
[2] = calc_load_n(avenrun
[2], EXP_15
, active
, n
);
330 WRITE_ONCE(calc_load_update
, sample_window
+ n
* LOAD_FREQ
);
334 * Flip the NO_HZ index...
336 * Make sure we first write the new time then flip the index, so that
337 * calc_load_write_idx() will see the new time when it reads the new
338 * index, this avoids a double flip messing things up.
343 #else /* !CONFIG_NO_HZ_COMMON */
345 static inline long calc_load_nohz_fold(void) { return 0; }
346 static inline void calc_global_nohz(void) { }
348 #endif /* CONFIG_NO_HZ_COMMON */
351 * calc_load - update the avenrun load estimates 10 ticks after the
352 * CPUs have updated calc_load_tasks.
354 * Called from the global timer code.
356 void calc_global_load(unsigned long ticks
)
358 unsigned long sample_window
;
361 sample_window
= READ_ONCE(calc_load_update
);
362 if (time_before(jiffies
, sample_window
+ 10))
366 * Fold the 'old' NO_HZ-delta to include all NO_HZ cpus.
368 delta
= calc_load_nohz_fold();
370 atomic_long_add(delta
, &calc_load_tasks
);
372 active
= atomic_long_read(&calc_load_tasks
);
373 active
= active
> 0 ? active
* FIXED_1
: 0;
375 avenrun
[0] = calc_load(avenrun
[0], EXP_1
, active
);
376 avenrun
[1] = calc_load(avenrun
[1], EXP_5
, active
);
377 avenrun
[2] = calc_load(avenrun
[2], EXP_15
, active
);
379 WRITE_ONCE(calc_load_update
, sample_window
+ LOAD_FREQ
);
382 * In case we went to NO_HZ for multiple LOAD_FREQ intervals
389 * Called from scheduler_tick() to periodically update this CPU's
392 void calc_global_load_tick(struct rq
*this_rq
)
396 if (time_before(jiffies
, this_rq
->calc_load_update
))
399 delta
= calc_load_fold_active(this_rq
, 0);
401 atomic_long_add(delta
, &calc_load_tasks
);
403 this_rq
->calc_load_update
+= LOAD_FREQ
;