~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/proportions.c

Version: ~ [ linux-5.5-rc6 ] ~ [ linux-5.4.11 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.95 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.164 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.209 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.209 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.81 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * Floating proportions
  3  *
  4  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
  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 int prop_descriptor_init(struct prop_descriptor *pd, int shift, gfp_t gfp)
 77 {
 78         int err;
 79 
 80         if (shift > PROP_MAX_SHIFT)
 81                 shift = PROP_MAX_SHIFT;
 82 
 83         pd->index = 0;
 84         pd->pg[0].shift = shift;
 85         mutex_init(&pd->mutex);
 86         err = percpu_counter_init(&pd->pg[0].events, 0, gfp);
 87         if (err)
 88                 goto out;
 89 
 90         err = percpu_counter_init(&pd->pg[1].events, 0, gfp);
 91         if (err)
 92                 percpu_counter_destroy(&pd->pg[0].events);
 93 
 94 out:
 95         return err;
 96 }
 97 
 98 /*
 99  * We have two copies, and flip between them to make it seem like an atomic
100  * update. The update is not really atomic wrt the events counter, but
101  * it is internally consistent with the bit layout depending on shift.
102  *
103  * We copy the events count, move the bits around and flip the index.
104  */
105 void prop_change_shift(struct prop_descriptor *pd, int shift)
106 {
107         int index;
108         int offset;
109         u64 events;
110         unsigned long flags;
111 
112         if (shift > PROP_MAX_SHIFT)
113                 shift = PROP_MAX_SHIFT;
114 
115         mutex_lock(&pd->mutex);
116 
117         index = pd->index ^ 1;
118         offset = pd->pg[pd->index].shift - shift;
119         if (!offset)
120                 goto out;
121 
122         pd->pg[index].shift = shift;
123 
124         local_irq_save(flags);
125         events = percpu_counter_sum(&pd->pg[pd->index].events);
126         if (offset < 0)
127                 events <<= -offset;
128         else
129                 events >>= offset;
130         percpu_counter_set(&pd->pg[index].events, events);
131 
132         /*
133          * ensure the new pg is fully written before the switch
134          */
135         smp_wmb();
136         pd->index = index;
137         local_irq_restore(flags);
138 
139         synchronize_rcu();
140 
141 out:
142         mutex_unlock(&pd->mutex);
143 }
144 
145 /*
146  * wrap the access to the data in an rcu_read_lock() section;
147  * this is used to track the active references.
148  */
149 static struct prop_global *prop_get_global(struct prop_descriptor *pd)
150 __acquires(RCU)
151 {
152         int index;
153 
154         rcu_read_lock();
155         index = pd->index;
156         /*
157          * match the wmb from vcd_flip()
158          */
159         smp_rmb();
160         return &pd->pg[index];
161 }
162 
163 static void prop_put_global(struct prop_descriptor *pd, struct prop_global *pg)
164 __releases(RCU)
165 {
166         rcu_read_unlock();
167 }
168 
169 static void
170 prop_adjust_shift(int *pl_shift, unsigned long *pl_period, int new_shift)
171 {
172         int offset = *pl_shift - new_shift;
173 
174         if (!offset)
175                 return;
176 
177         if (offset < 0)
178                 *pl_period <<= -offset;
179         else
180                 *pl_period >>= offset;
181 
182         *pl_shift = new_shift;
183 }
184 
185 /*
186  * PERCPU
187  */
188 
189 #define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
190 
191 int prop_local_init_percpu(struct prop_local_percpu *pl, gfp_t gfp)
192 {
193         raw_spin_lock_init(&pl->lock);
194         pl->shift = 0;
195         pl->period = 0;
196         return percpu_counter_init(&pl->events, 0, gfp);
197 }
198 
199 void prop_local_destroy_percpu(struct prop_local_percpu *pl)
200 {
201         percpu_counter_destroy(&pl->events);
202 }
203 
204 /*
205  * Catch up with missed period expirations.
206  *
207  *   until (c_{j} == c)
208  *     x_{j} -= x_{j}/2;
209  *     c_{j}++;
210  */
211 static
212 void prop_norm_percpu(struct prop_global *pg, struct prop_local_percpu *pl)
213 {
214         unsigned long period = 1UL << (pg->shift - 1);
215         unsigned long period_mask = ~(period - 1);
216         unsigned long global_period;
217         unsigned long flags;
218 
219         global_period = percpu_counter_read(&pg->events);
220         global_period &= period_mask;
221 
222         /*
223          * Fast path - check if the local and global period count still match
224          * outside of the lock.
225          */
226         if (pl->period == global_period)
227                 return;
228 
229         raw_spin_lock_irqsave(&pl->lock, flags);
230         prop_adjust_shift(&pl->shift, &pl->period, pg->shift);
231 
232         /*
233          * For each missed period, we half the local counter.
234          * basically:
235          *   pl->events >> (global_period - pl->period);
236          */
237         period = (global_period - pl->period) >> (pg->shift - 1);
238         if (period < BITS_PER_LONG) {
239                 s64 val = percpu_counter_read(&pl->events);
240 
241                 if (val < (nr_cpu_ids * PROP_BATCH))
242                         val = percpu_counter_sum(&pl->events);
243 
244                 __percpu_counter_add(&pl->events, -val + (val >> period),
245                                         PROP_BATCH);
246         } else
247                 percpu_counter_set(&pl->events, 0);
248 
249         pl->period = global_period;
250         raw_spin_unlock_irqrestore(&pl->lock, flags);
251 }
252 
253 /*
254  *   ++x_{j}, ++t
255  */
256 void __prop_inc_percpu(struct prop_descriptor *pd, struct prop_local_percpu *pl)
257 {
258         struct prop_global *pg = prop_get_global(pd);
259 
260         prop_norm_percpu(pg, pl);
261         __percpu_counter_add(&pl->events, 1, PROP_BATCH);
262         percpu_counter_add(&pg->events, 1);
263         prop_put_global(pd, pg);
264 }
265 
266 /*
267  * identical to __prop_inc_percpu, except that it limits this pl's fraction to
268  * @frac/PROP_FRAC_BASE by ignoring events when this limit has been exceeded.
269  */
270 void __prop_inc_percpu_max(struct prop_descriptor *pd,
271                            struct prop_local_percpu *pl, long frac)
272 {
273         struct prop_global *pg = prop_get_global(pd);
274 
275         prop_norm_percpu(pg, pl);
276 
277         if (unlikely(frac != PROP_FRAC_BASE)) {
278                 unsigned long period_2 = 1UL << (pg->shift - 1);
279                 unsigned long counter_mask = period_2 - 1;
280                 unsigned long global_count;
281                 long numerator, denominator;
282 
283                 numerator = percpu_counter_read_positive(&pl->events);
284                 global_count = percpu_counter_read(&pg->events);
285                 denominator = period_2 + (global_count & counter_mask);
286 
287                 if (numerator > ((denominator * frac) >> PROP_FRAC_SHIFT))
288                         goto out_put;
289         }
290 
291         percpu_counter_add(&pl->events, 1);
292         percpu_counter_add(&pg->events, 1);
293 
294 out_put:
295         prop_put_global(pd, pg);
296 }
297 
298 /*
299  * Obtain a fraction of this proportion
300  *
301  *   p_{j} = x_{j} / (period/2 + t % period/2)
302  */
303 void prop_fraction_percpu(struct prop_descriptor *pd,
304                 struct prop_local_percpu *pl,
305                 long *numerator, long *denominator)
306 {
307         struct prop_global *pg = prop_get_global(pd);
308         unsigned long period_2 = 1UL << (pg->shift - 1);
309         unsigned long counter_mask = period_2 - 1;
310         unsigned long global_count;
311 
312         prop_norm_percpu(pg, pl);
313         *numerator = percpu_counter_read_positive(&pl->events);
314 
315         global_count = percpu_counter_read(&pg->events);
316         *denominator = period_2 + (global_count & counter_mask);
317 
318         prop_put_global(pd, pg);
319 }
320 
321 /*
322  * SINGLE
323  */
324 
325 int prop_local_init_single(struct prop_local_single *pl)
326 {
327         raw_spin_lock_init(&pl->lock);
328         pl->shift = 0;
329         pl->period = 0;
330         pl->events = 0;
331         return 0;
332 }
333 
334 void prop_local_destroy_single(struct prop_local_single *pl)
335 {
336 }
337 
338 /*
339  * Catch up with missed period expirations.
340  */
341 static
342 void prop_norm_single(struct prop_global *pg, struct prop_local_single *pl)
343 {
344         unsigned long period = 1UL << (pg->shift - 1);
345         unsigned long period_mask = ~(period - 1);
346         unsigned long global_period;
347         unsigned long flags;
348 
349         global_period = percpu_counter_read(&pg->events);
350         global_period &= period_mask;
351 
352         /*
353          * Fast path - check if the local and global period count still match
354          * outside of the lock.
355          */
356         if (pl->period == global_period)
357                 return;
358 
359         raw_spin_lock_irqsave(&pl->lock, flags);
360         prop_adjust_shift(&pl->shift, &pl->period, pg->shift);
361         /*
362          * For each missed period, we half the local counter.
363          */
364         period = (global_period - pl->period) >> (pg->shift - 1);
365         if (likely(period < BITS_PER_LONG))
366                 pl->events >>= period;
367         else
368                 pl->events = 0;
369         pl->period = global_period;
370         raw_spin_unlock_irqrestore(&pl->lock, flags);
371 }
372 
373 /*
374  *   ++x_{j}, ++t
375  */
376 void __prop_inc_single(struct prop_descriptor *pd, struct prop_local_single *pl)
377 {
378         struct prop_global *pg = prop_get_global(pd);
379 
380         prop_norm_single(pg, pl);
381         pl->events++;
382         percpu_counter_add(&pg->events, 1);
383         prop_put_global(pd, pg);
384 }
385 
386 /*
387  * Obtain a fraction of this proportion
388  *
389  *   p_{j} = x_{j} / (period/2 + t % period/2)
390  */
391 void prop_fraction_single(struct prop_descriptor *pd,
392                 struct prop_local_single *pl,
393                 long *numerator, long *denominator)
394 {
395         struct prop_global *pg = prop_get_global(pd);
396         unsigned long period_2 = 1UL << (pg->shift - 1);
397         unsigned long counter_mask = period_2 - 1;
398         unsigned long global_count;
399 
400         prop_norm_single(pg, pl);
401         *numerator = pl->events;
402 
403         global_count = percpu_counter_read(&pg->events);
404         *denominator = period_2 + (global_count & counter_mask);
405 
406         prop_put_global(pd, pg);
407 }
408 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp