1 // SPDX-License-Identifier: GPL-2.0
29  *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
38 	/* after bounds checking we can collapse to 32-bit */  in decay_load()
42 	 * As y^PERIOD = 1/2, we can combine  in decay_load()
43 	 *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)  in decay_load()
44 	 * With a look-up table which covers y^n (n<PERIOD)  in decay_load()
59 	u32 c1, c2, c3 = d3; /* y^0 == 1 */  in __accumulate_pelt_segments()
67 	 *            p-1  in __accumulate_pelt_segments()
68 	 * c2 = 1024 \Sum y^n  in __accumulate_pelt_segments()
69 	 *            n=1  in __accumulate_pelt_segments()
72 	 *    = 1024 ( \Sum y^n - \Sum y^n - y^0 )  in __accumulate_pelt_segments()
75 	c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;  in __accumulate_pelt_segments()
88  *         |<->|<----------------->|<--->|
89  * ... |---x---|------| ... |------|-----x (now)
91  *                           p-1
92  * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
93  *                           n=1
95  *    = u y^p +					(Step 1)
97  *                     p-1
98  *      d1 y^p + 1024 \Sum y^n + d3 y^0		(Step 2)
99  *                     n=1
105 	u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */  in accumulate_sum()
108 	delta += sa->period_contrib;  in accumulate_sum()
109 	periods = delta / 1024; /* A period is 1024us (~1ms) */  in accumulate_sum()
112 	 * Step 1: decay old *_sum if we crossed period boundaries.  in accumulate_sum()
115 		sa->load_sum = decay_load(sa->load_sum, periods);  in accumulate_sum()
116 		sa->runnable_sum =  in accumulate_sum()
117 			decay_load(sa->runnable_sum, periods);  in accumulate_sum()
118 		sa->util_sum = decay_load((u64)(sa->util_sum), periods);  in accumulate_sum()
123 		delta %= 1024;  in accumulate_sum()
136 					1024 - sa->period_contrib, delta);  in accumulate_sum()
139 	sa->period_contrib = delta;  in accumulate_sum()
142 		sa->load_sum += load * contrib;  in accumulate_sum()
144 		sa->runnable_sum += runnable * contrib << SCHED_CAPACITY_SHIFT;  in accumulate_sum()
146 		sa->util_sum += contrib << SCHED_CAPACITY_SHIFT;  in accumulate_sum()
153  * coefficients of a geometric series.  To do this we sub-divide our runnable
154  * history into segments of approximately 1ms (1024us); label the segment that
155  * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
157  * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
159  *     (now)       (~1ms ago)  (~2ms ago)
163  * We then designate the fractions u_i as our co-efficients, yielding the
177  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
185 	delta = now - sa->last_update_time;  in ___update_load_sum()
191 		sa->last_update_time = now;  in ___update_load_sum()
196 	 * Use 1024ns as the unit of measurement since it's a reasonable  in ___update_load_sum()
197 	 * approximation of 1us and fast to compute.  in ___update_load_sum()
203 	sa->last_update_time += delta << 10;  in ___update_load_sum()
208 	 * se has been already dequeued but cfs_rq->curr still points to it.  in ___update_load_sum()
223 	 * Step 1: accumulate *_sum since last_update_time. If we haven't  in ___update_load_sum()
229 	return 1;  in ___update_load_sum()
236  * generate unwanted oscillation in the range [1002..1024[.
241  *   LOAD_AVG_MAX*y + sa->period_contrib
245  *   LOAD_AVG_MAX - 1024 + sa->period_contrib
247  * because LOAD_AVG_MAX*y == LOAD_AVG_MAX-1024
264 	sa->load_avg = div_u64(load * sa->load_sum, divider);  in ___update_load_avg()
265 	sa->runnable_avg = div_u64(sa->runnable_sum, divider);  in ___update_load_avg()
266 	WRITE_ONCE(sa->util_avg, sa->util_sum / divider);  in ___update_load_avg()
273  *     se_weight()   = se->load.weight
277  *     se_weight()   = tg->weight * grq->load_avg / tg->load_avg
278  *     se_runnable() = grq->h_nr_runnable
280  *   runnable_sum = se_runnable() * runnable = grq->runnable_sum
288  *   runnable_sum = \Sum se->avg.runnable_sum
289  *   runnable_avg = \Sum se->avg.runnable_avg
291  *   load_sum = \Sum se_weight(se) * se->avg.load_sum
292  *   load_avg = \Sum se->avg.load_avg
297 	if (___update_load_sum(now, &se->avg, 0, 0, 0)) {  in __update_load_avg_blocked_se()
298 		___update_load_avg(&se->avg, se_weight(se));  in __update_load_avg_blocked_se()
300 		return 1;  in __update_load_avg_blocked_se()
308 	if (___update_load_sum(now, &se->avg, !!se->on_rq, se_runnable(se),  in __update_load_avg_se()
309 				cfs_rq->curr == se)) {  in __update_load_avg_se()
311 		___update_load_avg(&se->avg, se_weight(se));  in __update_load_avg_se()
312 		cfs_se_util_change(&se->avg);  in __update_load_avg_se()
314 		return 1;  in __update_load_avg_se()
322 	if (___update_load_sum(now, &cfs_rq->avg,  in __update_load_avg_cfs_rq()
323 				scale_load_down(cfs_rq->load.weight),  in __update_load_avg_cfs_rq()
324 				cfs_rq->h_nr_runnable,  in __update_load_avg_cfs_rq()
325 				cfs_rq->curr != NULL)) {  in __update_load_avg_cfs_rq()
327 		___update_load_avg(&cfs_rq->avg, 1);  in __update_load_avg_cfs_rq()
329 		return 1;  in __update_load_avg_cfs_rq()
338  *   util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked
348 	if (___update_load_sum(now, &rq->avg_rt,  in update_rt_rq_load_avg()
353 		___update_load_avg(&rq->avg_rt, 1);  in update_rt_rq_load_avg()
355 		return 1;  in update_rt_rq_load_avg()
364  *   util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked
374 	if (___update_load_sum(now, &rq->avg_dl,  in update_dl_rq_load_avg()
379 		___update_load_avg(&rq->avg_dl, 1);  in update_dl_rq_load_avg()
381 		return 1;  in update_dl_rq_load_avg()
391  *   load_sum = \Sum se->avg.load_sum but se->avg.load_sum is not tracked
399  * "delta capacity" =  actual capacity  -
405 	if (___update_load_sum(now, &rq->avg_hw,  in update_hw_load_avg()
409 		___update_load_avg(&rq->avg_hw, 1);  in update_hw_load_avg()
411 		return 1;  in update_hw_load_avg()
422  *   util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked
450 	 * We can safely remove running from rq->clock because  in update_irq_load_avg()
451 	 * rq->clock += delta with delta >= running  in update_irq_load_avg()
453 	ret = ___update_load_sum(rq->clock - running, &rq->avg_irq,  in update_irq_load_avg()
457 	ret += ___update_load_sum(rq->clock, &rq->avg_irq,  in update_irq_load_avg()
458 				1,  in update_irq_load_avg()
459 				1,  in update_irq_load_avg()
460 				1);  in update_irq_load_avg()
463 		___update_load_avg(&rq->avg_irq, 1);  in update_irq_load_avg()
479 	const struct sched_class *curr_class = rq->donor->sched_class;  in update_other_load_avgs()