lib: floating proportions
[linux-2.6.git] / lib / proportions.c
1 /*
2  * Floating proportions
3  *
4  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
5  *
6  * Description:
7  *
8  * The floating proportion is a time derivative with an exponentially decaying
9  * history:
10  *
11  *   p_{j} = \Sum_{i=0} (dx_{j}/dt_{-i}) / 2^(1+i)
12  *
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.
16  *
17  * The decaying history gives smooth transitions. The time differential carries
18  * the notion of speed.
19  *
20  * The denominator is 2^(1+i) because we want the series to be normalised, ie.
21  *
22  *   \Sum_{i=0} 1/2^(1+i) = 1
23  *
24  * Further more, if we measure time (t) in the same events as x; so that:
25  *
26  *   t = \Sum_{j} x_{j}
27  *
28  * we get that:
29  *
30  *   \Sum_{j} p_{j} = 1
31  *
32  * Writing this in an iterative fashion we get (dropping the 'd's):
33  *
34  *   if (++x_{j}, ++t > period)
35  *     t /= 2;
36  *     for_each (j)
37  *       x_{j} /= 2;
38  *
39  * so that:
40  *
41  *   p_{j} = x_{j} / t;
42  *
43  * We optimize away the '/= 2' for the global time delta by noting that:
44  *
45  *   if (++t > period) t /= 2:
46  *
47  * Can be approximated by:
48  *
49  *   period/2 + (++t % period/2)
50  *
51  * [ Furthermore, when we choose period to be 2^n it can be written in terms of
52  *   binary operations and wraparound artefacts disappear. ]
53  *
54  * Also note that this yields a natural counter of the elapsed periods:
55  *
56  *   c = t / (period/2)
57  *
58  * [ Its monotonic increasing property can be applied to mitigate the wrap-
59  *   around issue. ]
60  *
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:
64  *
65  *   c - c_{j}
66  *
67  * We can then lazily catch up to the global period count every time we are
68  * going to use x_{j}, by doing:
69  *
70  *   x_{j} /= 2^(c - c_{j}), c_{j} = c
71  */
72
73 #include <linux/proportions.h>
74 #include <linux/rcupdate.h>
75
76 /*
77  * Limit the time part in order to ensure there are some bits left for the
78  * cycle counter.
79  */
80 #define PROP_MAX_SHIFT (3*BITS_PER_LONG/4)
81
82 int prop_descriptor_init(struct prop_descriptor *pd, int shift)
83 {
84         int err;
85
86         if (shift > PROP_MAX_SHIFT)
87                 shift = PROP_MAX_SHIFT;
88
89         pd->index = 0;
90         pd->pg[0].shift = shift;
91         mutex_init(&pd->mutex);
92         err = percpu_counter_init_irq(&pd->pg[0].events, 0);
93         if (err)
94                 goto out;
95
96         err = percpu_counter_init_irq(&pd->pg[1].events, 0);
97         if (err)
98                 percpu_counter_destroy(&pd->pg[0].events);
99
100 out:
101         return err;
102 }
103
104 /*
105  * We have two copies, and flip between them to make it seem like an atomic
106  * update. The update is not really atomic wrt the events counter, but
107  * it is internally consistent with the bit layout depending on shift.
108  *
109  * We copy the events count, move the bits around and flip the index.
110  */
111 void prop_change_shift(struct prop_descriptor *pd, int shift)
112 {
113         int index;
114         int offset;
115         u64 events;
116         unsigned long flags;
117
118         if (shift > PROP_MAX_SHIFT)
119                 shift = PROP_MAX_SHIFT;
120
121         mutex_lock(&pd->mutex);
122
123         index = pd->index ^ 1;
124         offset = pd->pg[pd->index].shift - shift;
125         if (!offset)
126                 goto out;
127
128         pd->pg[index].shift = shift;
129
130         local_irq_save(flags);
131         events = percpu_counter_sum(&pd->pg[pd->index].events);
132         if (offset < 0)
133                 events <<= -offset;
134         else
135                 events >>= offset;
136         percpu_counter_set(&pd->pg[index].events, events);
137
138         /*
139          * ensure the new pg is fully written before the switch
140          */
141         smp_wmb();
142         pd->index = index;
143         local_irq_restore(flags);
144
145         synchronize_rcu();
146
147 out:
148         mutex_unlock(&pd->mutex);
149 }
150
151 /*
152  * wrap the access to the data in an rcu_read_lock() section;
153  * this is used to track the active references.
154  */
155 static struct prop_global *prop_get_global(struct prop_descriptor *pd)
156 {
157         int index;
158
159         rcu_read_lock();
160         index = pd->index;
161         /*
162          * match the wmb from vcd_flip()
163          */
164         smp_rmb();
165         return &pd->pg[index];
166 }
167
168 static void prop_put_global(struct prop_descriptor *pd, struct prop_global *pg)
169 {
170         rcu_read_unlock();
171 }
172
173 static void
174 prop_adjust_shift(int *pl_shift, unsigned long *pl_period, int new_shift)
175 {
176         int offset = *pl_shift - new_shift;
177
178         if (!offset)
179                 return;
180
181         if (offset < 0)
182                 *pl_period <<= -offset;
183         else
184                 *pl_period >>= offset;
185
186         *pl_shift = new_shift;
187 }
188
189 /*
190  * PERCPU
191  */
192
193 int prop_local_init_percpu(struct prop_local_percpu *pl)
194 {
195         spin_lock_init(&pl->lock);
196         pl->shift = 0;
197         pl->period = 0;
198         return percpu_counter_init_irq(&pl->events, 0);
199 }
200
201 void prop_local_destroy_percpu(struct prop_local_percpu *pl)
202 {
203         percpu_counter_destroy(&pl->events);
204 }
205
206 /*
207  * Catch up with missed period expirations.
208  *
209  *   until (c_{j} == c)
210  *     x_{j} -= x_{j}/2;
211  *     c_{j}++;
212  */
213 static
214 void prop_norm_percpu(struct prop_global *pg, struct prop_local_percpu *pl)
215 {
216         unsigned long period = 1UL << (pg->shift - 1);
217         unsigned long period_mask = ~(period - 1);
218         unsigned long global_period;
219         unsigned long flags;
220
221         global_period = percpu_counter_read(&pg->events);
222         global_period &= period_mask;
223
224         /*
225          * Fast path - check if the local and global period count still match
226          * outside of the lock.
227          */
228         if (pl->period == global_period)
229                 return;
230
231         spin_lock_irqsave(&pl->lock, flags);
232         prop_adjust_shift(&pl->shift, &pl->period, pg->shift);
233         /*
234          * For each missed period, we half the local counter.
235          * basically:
236          *   pl->events >> (global_period - pl->period);
237          *
238          * but since the distributed nature of percpu counters make division
239          * rather hard, use a regular subtraction loop. This is safe, because
240          * the events will only every be incremented, hence the subtraction
241          * can never result in a negative number.
242          */
243         while (pl->period != global_period) {
244                 unsigned long val = percpu_counter_read(&pl->events);
245                 unsigned long half = (val + 1) >> 1;
246
247                 /*
248                  * Half of zero won't be much less, break out.
249                  * This limits the loop to shift iterations, even
250                  * if we missed a million.
251                  */
252                 if (!val)
253                         break;
254
255                 percpu_counter_add(&pl->events, -half);
256                 pl->period += period;
257         }
258         pl->period = global_period;
259         spin_unlock_irqrestore(&pl->lock, flags);
260 }
261
262 /*
263  *   ++x_{j}, ++t
264  */
265 void __prop_inc_percpu(struct prop_descriptor *pd, struct prop_local_percpu *pl)
266 {
267         struct prop_global *pg = prop_get_global(pd);
268
269         prop_norm_percpu(pg, pl);
270         percpu_counter_add(&pl->events, 1);
271         percpu_counter_add(&pg->events, 1);
272         prop_put_global(pd, pg);
273 }
274
275 /*
276  * Obtain a fraction of this proportion
277  *
278  *   p_{j} = x_{j} / (period/2 + t % period/2)
279  */
280 void prop_fraction_percpu(struct prop_descriptor *pd,
281                 struct prop_local_percpu *pl,
282                 long *numerator, long *denominator)
283 {
284         struct prop_global *pg = prop_get_global(pd);
285         unsigned long period_2 = 1UL << (pg->shift - 1);
286         unsigned long counter_mask = period_2 - 1;
287         unsigned long global_count;
288
289         prop_norm_percpu(pg, pl);
290         *numerator = percpu_counter_read_positive(&pl->events);
291
292         global_count = percpu_counter_read(&pg->events);
293         *denominator = period_2 + (global_count & counter_mask);
294
295         prop_put_global(pd, pg);
296 }
297
298 /*
299  * SINGLE
300  */
301
302 int prop_local_init_single(struct prop_local_single *pl)
303 {
304         spin_lock_init(&pl->lock);
305         pl->shift = 0;
306         pl->period = 0;
307         pl->events = 0;
308         return 0;
309 }
310
311 void prop_local_destroy_single(struct prop_local_single *pl)
312 {
313 }
314
315 /*
316  * Catch up with missed period expirations.
317  */
318 static
319 void prop_norm_single(struct prop_global *pg, struct prop_local_single *pl)
320 {
321         unsigned long period = 1UL << (pg->shift - 1);
322         unsigned long period_mask = ~(period - 1);
323         unsigned long global_period;
324         unsigned long flags;
325
326         global_period = percpu_counter_read(&pg->events);
327         global_period &= period_mask;
328
329         /*
330          * Fast path - check if the local and global period count still match
331          * outside of the lock.
332          */
333         if (pl->period == global_period)
334                 return;
335
336         spin_lock_irqsave(&pl->lock, flags);
337         prop_adjust_shift(&pl->shift, &pl->period, pg->shift);
338         /*
339          * For each missed period, we half the local counter.
340          */
341         period = (global_period - pl->period) >> (pg->shift - 1);
342         if (likely(period < BITS_PER_LONG))
343                 pl->events >>= period;
344         else
345                 pl->events = 0;
346         pl->period = global_period;
347         spin_unlock_irqrestore(&pl->lock, flags);
348 }
349
350 /*
351  *   ++x_{j}, ++t
352  */
353 void __prop_inc_single(struct prop_descriptor *pd, struct prop_local_single *pl)
354 {
355         struct prop_global *pg = prop_get_global(pd);
356
357         prop_norm_single(pg, pl);
358         pl->events++;
359         percpu_counter_add(&pg->events, 1);
360         prop_put_global(pd, pg);
361 }
362
363 /*
364  * Obtain a fraction of this proportion
365  *
366  *   p_{j} = x_{j} / (period/2 + t % period/2)
367  */
368 void prop_fraction_single(struct prop_descriptor *pd,
369                 struct prop_local_single *pl,
370                 long *numerator, long *denominator)
371 {
372         struct prop_global *pg = prop_get_global(pd);
373         unsigned long period_2 = 1UL << (pg->shift - 1);
374         unsigned long counter_mask = period_2 - 1;
375         unsigned long global_count;
376
377         prop_norm_single(pg, pl);
378         *numerator = pl->events;
379
380         global_count = percpu_counter_read(&pg->events);
381         *denominator = period_2 + (global_count & counter_mask);
382
383         prop_put_global(pd, pg);
384 }