1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
2f3109a51SJan Kara /*
3f3109a51SJan Kara * Floating proportions with flexible aging period
4f3109a51SJan Kara *
5f3109a51SJan Kara * Copyright (C) 2011, SUSE, Jan Kara <jack@suse.cz>
6f3109a51SJan Kara *
7f3109a51SJan Kara * The goal of this code is: Given different types of event, measure proportion
8f3109a51SJan Kara * of each type of event over time. The proportions are measured with
9f3109a51SJan Kara * exponentially decaying history to give smooth transitions. A formula
10f3109a51SJan Kara * expressing proportion of event of type 'j' is:
11f3109a51SJan Kara *
12f3109a51SJan Kara * p_{j} = (\Sum_{i>=0} x_{i,j}/2^{i+1})/(\Sum_{i>=0} x_i/2^{i+1})
13f3109a51SJan Kara *
14f3109a51SJan Kara * Where x_{i,j} is j's number of events in i-th last time period and x_i is
15f3109a51SJan Kara * total number of events in i-th last time period.
16f3109a51SJan Kara *
17f3109a51SJan Kara * Note that p_{j}'s are normalised, i.e.
18f3109a51SJan Kara *
19f3109a51SJan Kara * \Sum_{j} p_{j} = 1,
20f3109a51SJan Kara *
21bdb428c8SBogdan Sikora * This formula can be straightforwardly computed by maintaining denominator
22f3109a51SJan Kara * (let's call it 'd') and for each event type its numerator (let's call it
23f3109a51SJan Kara * 'n_j'). When an event of type 'j' happens, we simply need to do:
24f3109a51SJan Kara * n_j++; d++;
25f3109a51SJan Kara *
26f3109a51SJan Kara * When a new period is declared, we could do:
27f3109a51SJan Kara * d /= 2
28f3109a51SJan Kara * for each j
29f3109a51SJan Kara * n_j /= 2
30f3109a51SJan Kara *
31f3109a51SJan Kara * To avoid iteration over all event types, we instead shift numerator of event
32f3109a51SJan Kara * j lazily when someone asks for a proportion of event j or when event j
33f3109a51SJan Kara * occurs. This can bit trivially implemented by remembering last period in
34f3109a51SJan Kara * which something happened with proportion of type j.
35f3109a51SJan Kara */
36f3109a51SJan Kara #include <linux/flex_proportions.h>
37f3109a51SJan Kara
fprop_global_init(struct fprop_global * p,gfp_t gfp)3820ae0079STejun Heo int fprop_global_init(struct fprop_global *p, gfp_t gfp)
39f3109a51SJan Kara {
40f3109a51SJan Kara int err;
41f3109a51SJan Kara
42f3109a51SJan Kara p->period = 0;
43f3109a51SJan Kara /* Use 1 to avoid dealing with periods with 0 events... */
4420ae0079STejun Heo err = percpu_counter_init(&p->events, 1, gfp);
45f3109a51SJan Kara if (err)
46f3109a51SJan Kara return err;
47f3109a51SJan Kara seqcount_init(&p->sequence);
48f3109a51SJan Kara return 0;
49f3109a51SJan Kara }
50f3109a51SJan Kara
fprop_global_destroy(struct fprop_global * p)51f3109a51SJan Kara void fprop_global_destroy(struct fprop_global *p)
52f3109a51SJan Kara {
53f3109a51SJan Kara percpu_counter_destroy(&p->events);
54f3109a51SJan Kara }
55f3109a51SJan Kara
56f3109a51SJan Kara /*
57f3109a51SJan Kara * Declare @periods new periods. It is upto the caller to make sure period
58f3109a51SJan Kara * transitions cannot happen in parallel.
59f3109a51SJan Kara *
60f3109a51SJan Kara * The function returns true if the proportions are still defined and false
61f3109a51SJan Kara * if aging zeroed out all events. This can be used to detect whether declaring
62f3109a51SJan Kara * further periods has any effect.
63f3109a51SJan Kara */
fprop_new_period(struct fprop_global * p,int periods)64f3109a51SJan Kara bool fprop_new_period(struct fprop_global *p, int periods)
65f3109a51SJan Kara {
66a91befdeSwuchi s64 events = percpu_counter_sum(&p->events);
67f3109a51SJan Kara
68f3109a51SJan Kara /*
69f3109a51SJan Kara * Don't do anything if there are no events.
70f3109a51SJan Kara */
71a91befdeSwuchi if (events <= 1)
72f3109a51SJan Kara return false;
73*9458e0a7SSebastian Andrzej Siewior preempt_disable_nested();
74f3109a51SJan Kara write_seqcount_begin(&p->sequence);
75f3109a51SJan Kara if (periods < 64)
76f3109a51SJan Kara events -= events >> periods;
77f3109a51SJan Kara /* Use addition to avoid losing events happening between sum and set */
78f3109a51SJan Kara percpu_counter_add(&p->events, -events);
79f3109a51SJan Kara p->period += periods;
80f3109a51SJan Kara write_seqcount_end(&p->sequence);
81*9458e0a7SSebastian Andrzej Siewior preempt_enable_nested();
82f3109a51SJan Kara
83f3109a51SJan Kara return true;
84f3109a51SJan Kara }
85f3109a51SJan Kara
86f3109a51SJan Kara /*
87f3109a51SJan Kara * ---- SINGLE ----
88f3109a51SJan Kara */
89f3109a51SJan Kara
fprop_local_init_single(struct fprop_local_single * pl)90f3109a51SJan Kara int fprop_local_init_single(struct fprop_local_single *pl)
91f3109a51SJan Kara {
92f3109a51SJan Kara pl->events = 0;
93f3109a51SJan Kara pl->period = 0;
94f3109a51SJan Kara raw_spin_lock_init(&pl->lock);
95f3109a51SJan Kara return 0;
96f3109a51SJan Kara }
97f3109a51SJan Kara
fprop_local_destroy_single(struct fprop_local_single * pl)98f3109a51SJan Kara void fprop_local_destroy_single(struct fprop_local_single *pl)
99f3109a51SJan Kara {
100f3109a51SJan Kara }
101f3109a51SJan Kara
fprop_reflect_period_single(struct fprop_global * p,struct fprop_local_single * pl)102f3109a51SJan Kara static void fprop_reflect_period_single(struct fprop_global *p,
103f3109a51SJan Kara struct fprop_local_single *pl)
104f3109a51SJan Kara {
105f3109a51SJan Kara unsigned int period = p->period;
106f3109a51SJan Kara unsigned long flags;
107f3109a51SJan Kara
108f3109a51SJan Kara /* Fast path - period didn't change */
109f3109a51SJan Kara if (pl->period == period)
110f3109a51SJan Kara return;
111f3109a51SJan Kara raw_spin_lock_irqsave(&pl->lock, flags);
112f3109a51SJan Kara /* Someone updated pl->period while we were spinning? */
113f3109a51SJan Kara if (pl->period >= period) {
114f3109a51SJan Kara raw_spin_unlock_irqrestore(&pl->lock, flags);
115f3109a51SJan Kara return;
116f3109a51SJan Kara }
117f3109a51SJan Kara /* Aging zeroed our fraction? */
118f3109a51SJan Kara if (period - pl->period < BITS_PER_LONG)
119f3109a51SJan Kara pl->events >>= period - pl->period;
120f3109a51SJan Kara else
121f3109a51SJan Kara pl->events = 0;
122f3109a51SJan Kara pl->period = period;
123f3109a51SJan Kara raw_spin_unlock_irqrestore(&pl->lock, flags);
124f3109a51SJan Kara }
125f3109a51SJan Kara
126f3109a51SJan Kara /* Event of type pl happened */
__fprop_inc_single(struct fprop_global * p,struct fprop_local_single * pl)127f3109a51SJan Kara void __fprop_inc_single(struct fprop_global *p, struct fprop_local_single *pl)
128f3109a51SJan Kara {
129f3109a51SJan Kara fprop_reflect_period_single(p, pl);
130f3109a51SJan Kara pl->events++;
131f3109a51SJan Kara percpu_counter_add(&p->events, 1);
132f3109a51SJan Kara }
133f3109a51SJan Kara
134f3109a51SJan Kara /* Return fraction of events of type pl */
fprop_fraction_single(struct fprop_global * p,struct fprop_local_single * pl,unsigned long * numerator,unsigned long * denominator)135f3109a51SJan Kara void fprop_fraction_single(struct fprop_global *p,
136f3109a51SJan Kara struct fprop_local_single *pl,
137f3109a51SJan Kara unsigned long *numerator, unsigned long *denominator)
138f3109a51SJan Kara {
139f3109a51SJan Kara unsigned int seq;
140f3109a51SJan Kara s64 num, den;
141f3109a51SJan Kara
142f3109a51SJan Kara do {
143f3109a51SJan Kara seq = read_seqcount_begin(&p->sequence);
144f3109a51SJan Kara fprop_reflect_period_single(p, pl);
145f3109a51SJan Kara num = pl->events;
146f3109a51SJan Kara den = percpu_counter_read_positive(&p->events);
147f3109a51SJan Kara } while (read_seqcount_retry(&p->sequence, seq));
148f3109a51SJan Kara
149f3109a51SJan Kara /*
150f3109a51SJan Kara * Make fraction <= 1 and denominator > 0 even in presence of percpu
151f3109a51SJan Kara * counter errors
152f3109a51SJan Kara */
153f3109a51SJan Kara if (den <= num) {
154f3109a51SJan Kara if (num)
155f3109a51SJan Kara den = num;
156f3109a51SJan Kara else
157f3109a51SJan Kara den = 1;
158f3109a51SJan Kara }
159f3109a51SJan Kara *denominator = den;
160f3109a51SJan Kara *numerator = num;
161f3109a51SJan Kara }
162f3109a51SJan Kara
163f3109a51SJan Kara /*
164f3109a51SJan Kara * ---- PERCPU ----
165f3109a51SJan Kara */
166f3109a51SJan Kara #define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
167f3109a51SJan Kara
fprop_local_init_percpu(struct fprop_local_percpu * pl,gfp_t gfp)16820ae0079STejun Heo int fprop_local_init_percpu(struct fprop_local_percpu *pl, gfp_t gfp)
169f3109a51SJan Kara {
170f3109a51SJan Kara int err;
171f3109a51SJan Kara
17220ae0079STejun Heo err = percpu_counter_init(&pl->events, 0, gfp);
173f3109a51SJan Kara if (err)
174f3109a51SJan Kara return err;
175f3109a51SJan Kara pl->period = 0;
176f3109a51SJan Kara raw_spin_lock_init(&pl->lock);
177f3109a51SJan Kara return 0;
178f3109a51SJan Kara }
179f3109a51SJan Kara
fprop_local_destroy_percpu(struct fprop_local_percpu * pl)180f3109a51SJan Kara void fprop_local_destroy_percpu(struct fprop_local_percpu *pl)
181f3109a51SJan Kara {
182f3109a51SJan Kara percpu_counter_destroy(&pl->events);
183f3109a51SJan Kara }
184f3109a51SJan Kara
fprop_reflect_period_percpu(struct fprop_global * p,struct fprop_local_percpu * pl)185f3109a51SJan Kara static void fprop_reflect_period_percpu(struct fprop_global *p,
186f3109a51SJan Kara struct fprop_local_percpu *pl)
187f3109a51SJan Kara {
188f3109a51SJan Kara unsigned int period = p->period;
189f3109a51SJan Kara unsigned long flags;
190f3109a51SJan Kara
191f3109a51SJan Kara /* Fast path - period didn't change */
192f3109a51SJan Kara if (pl->period == period)
193f3109a51SJan Kara return;
194f3109a51SJan Kara raw_spin_lock_irqsave(&pl->lock, flags);
195f3109a51SJan Kara /* Someone updated pl->period while we were spinning? */
196f3109a51SJan Kara if (pl->period >= period) {
197f3109a51SJan Kara raw_spin_unlock_irqrestore(&pl->lock, flags);
198f3109a51SJan Kara return;
199f3109a51SJan Kara }
200f3109a51SJan Kara /* Aging zeroed our fraction? */
201f3109a51SJan Kara if (period - pl->period < BITS_PER_LONG) {
202f3109a51SJan Kara s64 val = percpu_counter_read(&pl->events);
203f3109a51SJan Kara
204f3109a51SJan Kara if (val < (nr_cpu_ids * PROP_BATCH))
205f3109a51SJan Kara val = percpu_counter_sum(&pl->events);
206f3109a51SJan Kara
207104b4e51SNikolay Borisov percpu_counter_add_batch(&pl->events,
208f3109a51SJan Kara -val + (val >> (period-pl->period)), PROP_BATCH);
209f3109a51SJan Kara } else
210f3109a51SJan Kara percpu_counter_set(&pl->events, 0);
211f3109a51SJan Kara pl->period = period;
212f3109a51SJan Kara raw_spin_unlock_irqrestore(&pl->lock, flags);
213f3109a51SJan Kara }
214f3109a51SJan Kara
215f3109a51SJan Kara /* Event of type pl happened */
__fprop_add_percpu(struct fprop_global * p,struct fprop_local_percpu * pl,long nr)216be5f1797SMatthew Wilcox (Oracle) void __fprop_add_percpu(struct fprop_global *p, struct fprop_local_percpu *pl,
217be5f1797SMatthew Wilcox (Oracle) long nr)
218f3109a51SJan Kara {
219f3109a51SJan Kara fprop_reflect_period_percpu(p, pl);
220be5f1797SMatthew Wilcox (Oracle) percpu_counter_add_batch(&pl->events, nr, PROP_BATCH);
221be5f1797SMatthew Wilcox (Oracle) percpu_counter_add(&p->events, nr);
222f3109a51SJan Kara }
223f3109a51SJan Kara
fprop_fraction_percpu(struct fprop_global * p,struct fprop_local_percpu * pl,unsigned long * numerator,unsigned long * denominator)224f3109a51SJan Kara void fprop_fraction_percpu(struct fprop_global *p,
225f3109a51SJan Kara struct fprop_local_percpu *pl,
226f3109a51SJan Kara unsigned long *numerator, unsigned long *denominator)
227f3109a51SJan Kara {
228f3109a51SJan Kara unsigned int seq;
229f3109a51SJan Kara s64 num, den;
230f3109a51SJan Kara
231f3109a51SJan Kara do {
232f3109a51SJan Kara seq = read_seqcount_begin(&p->sequence);
233f3109a51SJan Kara fprop_reflect_period_percpu(p, pl);
234f3109a51SJan Kara num = percpu_counter_read_positive(&pl->events);
235f3109a51SJan Kara den = percpu_counter_read_positive(&p->events);
236f3109a51SJan Kara } while (read_seqcount_retry(&p->sequence, seq));
237f3109a51SJan Kara
238f3109a51SJan Kara /*
239f3109a51SJan Kara * Make fraction <= 1 and denominator > 0 even in presence of percpu
240f3109a51SJan Kara * counter errors
241f3109a51SJan Kara */
242f3109a51SJan Kara if (den <= num) {
243f3109a51SJan Kara if (num)
244f3109a51SJan Kara den = num;
245f3109a51SJan Kara else
246f3109a51SJan Kara den = 1;
247f3109a51SJan Kara }
248f3109a51SJan Kara *denominator = den;
249f3109a51SJan Kara *numerator = num;
250f3109a51SJan Kara }
251f3109a51SJan Kara
252f3109a51SJan Kara /*
253be5f1797SMatthew Wilcox (Oracle) * Like __fprop_add_percpu() except that event is counted only if the given
254f3109a51SJan Kara * type has fraction smaller than @max_frac/FPROP_FRAC_BASE
255f3109a51SJan Kara */
__fprop_add_percpu_max(struct fprop_global * p,struct fprop_local_percpu * pl,int max_frac,long nr)256be5f1797SMatthew Wilcox (Oracle) void __fprop_add_percpu_max(struct fprop_global *p,
257be5f1797SMatthew Wilcox (Oracle) struct fprop_local_percpu *pl, int max_frac, long nr)
258f3109a51SJan Kara {
259f3109a51SJan Kara if (unlikely(max_frac < FPROP_FRAC_BASE)) {
260f3109a51SJan Kara unsigned long numerator, denominator;
261be5f1797SMatthew Wilcox (Oracle) s64 tmp;
262f3109a51SJan Kara
263f3109a51SJan Kara fprop_fraction_percpu(p, pl, &numerator, &denominator);
264be5f1797SMatthew Wilcox (Oracle) /* Adding 'nr' to fraction exceeds max_frac/FPROP_FRAC_BASE? */
265be5f1797SMatthew Wilcox (Oracle) tmp = (u64)denominator * max_frac -
266be5f1797SMatthew Wilcox (Oracle) ((u64)numerator << FPROP_FRAC_SHIFT);
267be5f1797SMatthew Wilcox (Oracle) if (tmp < 0) {
268be5f1797SMatthew Wilcox (Oracle) /* Maximum fraction already exceeded? */
269f3109a51SJan Kara return;
270be5f1797SMatthew Wilcox (Oracle) } else if (tmp < nr * (FPROP_FRAC_BASE - max_frac)) {
271be5f1797SMatthew Wilcox (Oracle) /* Add just enough for the fraction to saturate */
272be5f1797SMatthew Wilcox (Oracle) nr = div_u64(tmp + FPROP_FRAC_BASE - max_frac - 1,
273be5f1797SMatthew Wilcox (Oracle) FPROP_FRAC_BASE - max_frac);
274be5f1797SMatthew Wilcox (Oracle) }
27563d7f816STan Hu }
27663d7f816STan Hu
277be5f1797SMatthew Wilcox (Oracle) __fprop_add_percpu(p, pl, nr);
278f3109a51SJan Kara }
279