4 * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
8 * The floating proportion is a time derivative with an exponentially decaying
11 * p_{j} = \Sum_{i=0} (dx_{j}/dt_{-i}) / 2^(1+i)
13 * Where j is an element from {prop_local}, x_{j} is j's number of events,
14 * and i the time period over which the differential is taken. So d/dt_{-i} is
15 * the differential over the i-th last period.
17 * The decaying history gives smooth transitions. The time differential carries
18 * the notion of speed.
20 * The denominator is 2^(1+i) because we want the series to be normalised, ie.
22 * \Sum_{i=0} 1/2^(1+i) = 1
24 * Further more, if we measure time (t) in the same events as x; so that:
32 * Writing this in an iterative fashion we get (dropping the 'd's):
34 * if (++x_{j}, ++t > period)
43 * We optimize away the '/= 2' for the global time delta by noting that:
45 * if (++t > period) t /= 2:
47 * Can be approximated by:
49 * period/2 + (++t % period/2)
51 * [ Furthermore, when we choose period to be 2^n it can be written in terms of
52 * binary operations and wraparound artefacts disappear. ]
54 * Also note that this yields a natural counter of the elapsed periods:
58 * [ Its monotonic increasing property can be applied to mitigate the wrap-
61 * This allows us to do away with the loop over all prop_locals on each period
62 * expiration. By remembering the period count under which it was last accessed
63 * as c_{j}, we can obtain the number of 'missed' cycles from:
67 * We can then lazily catch up to the global period count every time we are
68 * going to use x_{j}, by doing:
70 * x_{j} /= 2^(c - c_{j}), c_{j} = c
73 #include <linux/proportions.h>
74 #include <linux/rcupdate.h>
77 * Limit the time part in order to ensure there are some bits left for the
80 #define PROP_MAX_SHIFT (3*BITS_PER_LONG/4)
82 int prop_descriptor_init(struct prop_descriptor
*pd
, int shift
)
84 if (shift
> PROP_MAX_SHIFT
)
85 shift
= PROP_MAX_SHIFT
;
88 pd
->pg
[0].shift
= shift
;
89 mutex_init(&pd
->mutex
);
90 percpu_counter_init(&pd
->pg
[0].events
, 0);
91 percpu_counter_init(&pd
->pg
[1].events
, 0);
97 * We have two copies, and flip between them to make it seem like an atomic
98 * update. The update is not really atomic wrt the events counter, but
99 * it is internally consistent with the bit layout depending on shift.
101 * We copy the events count, move the bits around and flip the index.
103 void prop_change_shift(struct prop_descriptor
*pd
, int shift
)
110 if (shift
> PROP_MAX_SHIFT
)
111 shift
= PROP_MAX_SHIFT
;
113 mutex_lock(&pd
->mutex
);
115 index
= pd
->index
^ 1;
116 offset
= pd
->pg
[pd
->index
].shift
- shift
;
120 pd
->pg
[index
].shift
= shift
;
122 local_irq_save(flags
);
123 events
= percpu_counter_sum(&pd
->pg
[pd
->index
].events
);
128 percpu_counter_init(&pd
->pg
[index
].events
, events
);
131 * ensure the new pg is fully written before the switch
135 local_irq_restore(flags
);
140 mutex_unlock(&pd
->mutex
);
144 * wrap the access to the data in an rcu_read_lock() section;
145 * this is used to track the active references.
147 static struct prop_global
*prop_get_global(struct prop_descriptor
*pd
)
154 * match the wmb from vcd_flip()
157 return &pd
->pg
[index
];
160 static void prop_put_global(struct prop_descriptor
*pd
, struct prop_global
*pg
)
166 prop_adjust_shift(int *pl_shift
, unsigned long *pl_period
, int new_shift
)
168 int offset
= *pl_shift
- new_shift
;
174 *pl_period
<<= -offset
;
176 *pl_period
>>= offset
;
178 *pl_shift
= new_shift
;
185 int prop_local_init_percpu(struct prop_local_percpu
*pl
)
187 spin_lock_init(&pl
->lock
);
190 percpu_counter_init(&pl
->events
, 0);
194 void prop_local_destroy_percpu(struct prop_local_percpu
*pl
)
196 percpu_counter_destroy(&pl
->events
);
200 * Catch up with missed period expirations.
207 void prop_norm_percpu(struct prop_global
*pg
, struct prop_local_percpu
*pl
)
209 unsigned long period
= 1UL << (pg
->shift
- 1);
210 unsigned long period_mask
= ~(period
- 1);
211 unsigned long global_period
;
214 global_period
= percpu_counter_read(&pg
->events
);
215 global_period
&= period_mask
;
218 * Fast path - check if the local and global period count still match
219 * outside of the lock.
221 if (pl
->period
== global_period
)
224 spin_lock_irqsave(&pl
->lock
, flags
);
225 prop_adjust_shift(&pl
->shift
, &pl
->period
, pg
->shift
);
227 * For each missed period, we half the local counter.
229 * pl->events >> (global_period - pl->period);
231 * but since the distributed nature of percpu counters make division
232 * rather hard, use a regular subtraction loop. This is safe, because
233 * the events will only every be incremented, hence the subtraction
234 * can never result in a negative number.
236 while (pl
->period
!= global_period
) {
237 unsigned long val
= percpu_counter_read(&pl
->events
);
238 unsigned long half
= (val
+ 1) >> 1;
241 * Half of zero won't be much less, break out.
242 * This limits the loop to shift iterations, even
243 * if we missed a million.
248 percpu_counter_mod(&pl
->events
, -half
);
249 pl
->period
+= period
;
251 pl
->period
= global_period
;
252 spin_unlock_irqrestore(&pl
->lock
, flags
);
258 void __prop_inc_percpu(struct prop_descriptor
*pd
, struct prop_local_percpu
*pl
)
260 struct prop_global
*pg
= prop_get_global(pd
);
262 prop_norm_percpu(pg
, pl
);
263 percpu_counter_mod(&pl
->events
, 1);
264 percpu_counter_mod(&pg
->events
, 1);
265 prop_put_global(pd
, pg
);
269 * Obtain a fraction of this proportion
271 * p_{j} = x_{j} / (period/2 + t % period/2)
273 void prop_fraction_percpu(struct prop_descriptor
*pd
,
274 struct prop_local_percpu
*pl
,
275 long *numerator
, long *denominator
)
277 struct prop_global
*pg
= prop_get_global(pd
);
278 unsigned long period_2
= 1UL << (pg
->shift
- 1);
279 unsigned long counter_mask
= period_2
- 1;
280 unsigned long global_count
;
282 prop_norm_percpu(pg
, pl
);
283 *numerator
= percpu_counter_read_positive(&pl
->events
);
285 global_count
= percpu_counter_read(&pg
->events
);
286 *denominator
= period_2
+ (global_count
& counter_mask
);
288 prop_put_global(pd
, pg
);
295 int prop_local_init_single(struct prop_local_single
*pl
)
297 spin_lock_init(&pl
->lock
);
304 void prop_local_destroy_single(struct prop_local_single
*pl
)
309 * Catch up with missed period expirations.
312 void prop_norm_single(struct prop_global
*pg
, struct prop_local_single
*pl
)
314 unsigned long period
= 1UL << (pg
->shift
- 1);
315 unsigned long period_mask
= ~(period
- 1);
316 unsigned long global_period
;
319 global_period
= percpu_counter_read(&pg
->events
);
320 global_period
&= period_mask
;
323 * Fast path - check if the local and global period count still match
324 * outside of the lock.
326 if (pl
->period
== global_period
)
329 spin_lock_irqsave(&pl
->lock
, flags
);
330 prop_adjust_shift(&pl
->shift
, &pl
->period
, pg
->shift
);
332 * For each missed period, we half the local counter.
334 period
= (global_period
- pl
->period
) >> (pg
->shift
- 1);
335 if (likely(period
< BITS_PER_LONG
))
336 pl
->events
>>= period
;
339 pl
->period
= global_period
;
340 spin_unlock_irqrestore(&pl
->lock
, flags
);
346 void __prop_inc_single(struct prop_descriptor
*pd
, struct prop_local_single
*pl
)
348 struct prop_global
*pg
= prop_get_global(pd
);
350 prop_norm_single(pg
, pl
);
352 percpu_counter_mod(&pg
->events
, 1);
353 prop_put_global(pd
, pg
);
357 * Obtain a fraction of this proportion
359 * p_{j} = x_{j} / (period/2 + t % period/2)
361 void prop_fraction_single(struct prop_descriptor
*pd
,
362 struct prop_local_single
*pl
,
363 long *numerator
, long *denominator
)
365 struct prop_global
*pg
= prop_get_global(pd
);
366 unsigned long period_2
= 1UL << (pg
->shift
- 1);
367 unsigned long counter_mask
= period_2
- 1;
368 unsigned long global_count
;
370 prop_norm_single(pg
, pl
);
371 *numerator
= pl
->events
;
373 global_count
= percpu_counter_read(&pg
->events
);
374 *denominator
= period_2
+ (global_count
& counter_mask
);
376 prop_put_global(pd
, pg
);