Back to home page

LXR

 
 

    


0001 /*
0002  *  Floating proportions with flexible aging period
0003  *
0004  *   Copyright (C) 2011, SUSE, Jan Kara <jack@suse.cz>
0005  *
0006  * The goal of this code is: Given different types of event, measure proportion
0007  * of each type of event over time. The proportions are measured with
0008  * exponentially decaying history to give smooth transitions. A formula
0009  * expressing proportion of event of type 'j' is:
0010  *
0011  *   p_{j} = (\Sum_{i>=0} x_{i,j}/2^{i+1})/(\Sum_{i>=0} x_i/2^{i+1})
0012  *
0013  * Where x_{i,j} is j's number of events in i-th last time period and x_i is
0014  * total number of events in i-th last time period.
0015  *
0016  * Note that p_{j}'s are normalised, i.e.
0017  *
0018  *   \Sum_{j} p_{j} = 1,
0019  *
0020  * This formula can be straightforwardly computed by maintaining denominator
0021  * (let's call it 'd') and for each event type its numerator (let's call it
0022  * 'n_j'). When an event of type 'j' happens, we simply need to do:
0023  *   n_j++; d++;
0024  *
0025  * When a new period is declared, we could do:
0026  *   d /= 2
0027  *   for each j
0028  *     n_j /= 2
0029  *
0030  * To avoid iteration over all event types, we instead shift numerator of event
0031  * j lazily when someone asks for a proportion of event j or when event j
0032  * occurs. This can bit trivially implemented by remembering last period in
0033  * which something happened with proportion of type j.
0034  */
0035 #include <linux/flex_proportions.h>
0036 
0037 int fprop_global_init(struct fprop_global *p, gfp_t gfp)
0038 {
0039     int err;
0040 
0041     p->period = 0;
0042     /* Use 1 to avoid dealing with periods with 0 events... */
0043     err = percpu_counter_init(&p->events, 1, gfp);
0044     if (err)
0045         return err;
0046     seqcount_init(&p->sequence);
0047     return 0;
0048 }
0049 
0050 void fprop_global_destroy(struct fprop_global *p)
0051 {
0052     percpu_counter_destroy(&p->events);
0053 }
0054 
0055 /*
0056  * Declare @periods new periods. It is upto the caller to make sure period
0057  * transitions cannot happen in parallel.
0058  *
0059  * The function returns true if the proportions are still defined and false
0060  * if aging zeroed out all events. This can be used to detect whether declaring
0061  * further periods has any effect.
0062  */
0063 bool fprop_new_period(struct fprop_global *p, int periods)
0064 {
0065     s64 events;
0066     unsigned long flags;
0067 
0068     local_irq_save(flags);
0069     events = percpu_counter_sum(&p->events);
0070     /*
0071      * Don't do anything if there are no events.
0072      */
0073     if (events <= 1) {
0074         local_irq_restore(flags);
0075         return false;
0076     }
0077     write_seqcount_begin(&p->sequence);
0078     if (periods < 64)
0079         events -= events >> periods;
0080     /* Use addition to avoid losing events happening between sum and set */
0081     percpu_counter_add(&p->events, -events);
0082     p->period += periods;
0083     write_seqcount_end(&p->sequence);
0084     local_irq_restore(flags);
0085 
0086     return true;
0087 }
0088 
0089 /*
0090  * ---- SINGLE ----
0091  */
0092 
0093 int fprop_local_init_single(struct fprop_local_single *pl)
0094 {
0095     pl->events = 0;
0096     pl->period = 0;
0097     raw_spin_lock_init(&pl->lock);
0098     return 0;
0099 }
0100 
0101 void fprop_local_destroy_single(struct fprop_local_single *pl)
0102 {
0103 }
0104 
0105 static void fprop_reflect_period_single(struct fprop_global *p,
0106                     struct fprop_local_single *pl)
0107 {
0108     unsigned int period = p->period;
0109     unsigned long flags;
0110 
0111     /* Fast path - period didn't change */
0112     if (pl->period == period)
0113         return;
0114     raw_spin_lock_irqsave(&pl->lock, flags);
0115     /* Someone updated pl->period while we were spinning? */
0116     if (pl->period >= period) {
0117         raw_spin_unlock_irqrestore(&pl->lock, flags);
0118         return;
0119     }
0120     /* Aging zeroed our fraction? */
0121     if (period - pl->period < BITS_PER_LONG)
0122         pl->events >>= period - pl->period;
0123     else
0124         pl->events = 0;
0125     pl->period = period;
0126     raw_spin_unlock_irqrestore(&pl->lock, flags);
0127 }
0128 
0129 /* Event of type pl happened */
0130 void __fprop_inc_single(struct fprop_global *p, struct fprop_local_single *pl)
0131 {
0132     fprop_reflect_period_single(p, pl);
0133     pl->events++;
0134     percpu_counter_add(&p->events, 1);
0135 }
0136 
0137 /* Return fraction of events of type pl */
0138 void fprop_fraction_single(struct fprop_global *p,
0139                struct fprop_local_single *pl,
0140                unsigned long *numerator, unsigned long *denominator)
0141 {
0142     unsigned int seq;
0143     s64 num, den;
0144 
0145     do {
0146         seq = read_seqcount_begin(&p->sequence);
0147         fprop_reflect_period_single(p, pl);
0148         num = pl->events;
0149         den = percpu_counter_read_positive(&p->events);
0150     } while (read_seqcount_retry(&p->sequence, seq));
0151 
0152     /*
0153      * Make fraction <= 1 and denominator > 0 even in presence of percpu
0154      * counter errors
0155      */
0156     if (den <= num) {
0157         if (num)
0158             den = num;
0159         else
0160             den = 1;
0161     }
0162     *denominator = den;
0163     *numerator = num;
0164 }
0165 
0166 /*
0167  * ---- PERCPU ----
0168  */
0169 #define PROP_BATCH (8*(1+ilog2(nr_cpu_ids)))
0170 
0171 int fprop_local_init_percpu(struct fprop_local_percpu *pl, gfp_t gfp)
0172 {
0173     int err;
0174 
0175     err = percpu_counter_init(&pl->events, 0, gfp);
0176     if (err)
0177         return err;
0178     pl->period = 0;
0179     raw_spin_lock_init(&pl->lock);
0180     return 0;
0181 }
0182 
0183 void fprop_local_destroy_percpu(struct fprop_local_percpu *pl)
0184 {
0185     percpu_counter_destroy(&pl->events);
0186 }
0187 
0188 static void fprop_reflect_period_percpu(struct fprop_global *p,
0189                     struct fprop_local_percpu *pl)
0190 {
0191     unsigned int period = p->period;
0192     unsigned long flags;
0193 
0194     /* Fast path - period didn't change */
0195     if (pl->period == period)
0196         return;
0197     raw_spin_lock_irqsave(&pl->lock, flags);
0198     /* Someone updated pl->period while we were spinning? */
0199     if (pl->period >= period) {
0200         raw_spin_unlock_irqrestore(&pl->lock, flags);
0201         return;
0202     }
0203     /* Aging zeroed our fraction? */
0204     if (period - pl->period < BITS_PER_LONG) {
0205         s64 val = percpu_counter_read(&pl->events);
0206 
0207         if (val < (nr_cpu_ids * PROP_BATCH))
0208             val = percpu_counter_sum(&pl->events);
0209 
0210         __percpu_counter_add(&pl->events,
0211             -val + (val >> (period-pl->period)), PROP_BATCH);
0212     } else
0213         percpu_counter_set(&pl->events, 0);
0214     pl->period = period;
0215     raw_spin_unlock_irqrestore(&pl->lock, flags);
0216 }
0217 
0218 /* Event of type pl happened */
0219 void __fprop_inc_percpu(struct fprop_global *p, struct fprop_local_percpu *pl)
0220 {
0221     fprop_reflect_period_percpu(p, pl);
0222     __percpu_counter_add(&pl->events, 1, PROP_BATCH);
0223     percpu_counter_add(&p->events, 1);
0224 }
0225 
0226 void fprop_fraction_percpu(struct fprop_global *p,
0227                struct fprop_local_percpu *pl,
0228                unsigned long *numerator, unsigned long *denominator)
0229 {
0230     unsigned int seq;
0231     s64 num, den;
0232 
0233     do {
0234         seq = read_seqcount_begin(&p->sequence);
0235         fprop_reflect_period_percpu(p, pl);
0236         num = percpu_counter_read_positive(&pl->events);
0237         den = percpu_counter_read_positive(&p->events);
0238     } while (read_seqcount_retry(&p->sequence, seq));
0239 
0240     /*
0241      * Make fraction <= 1 and denominator > 0 even in presence of percpu
0242      * counter errors
0243      */
0244     if (den <= num) {
0245         if (num)
0246             den = num;
0247         else
0248             den = 1;
0249     }
0250     *denominator = den;
0251     *numerator = num;
0252 }
0253 
0254 /*
0255  * Like __fprop_inc_percpu() except that event is counted only if the given
0256  * type has fraction smaller than @max_frac/FPROP_FRAC_BASE
0257  */
0258 void __fprop_inc_percpu_max(struct fprop_global *p,
0259                 struct fprop_local_percpu *pl, int max_frac)
0260 {
0261     if (unlikely(max_frac < FPROP_FRAC_BASE)) {
0262         unsigned long numerator, denominator;
0263 
0264         fprop_fraction_percpu(p, pl, &numerator, &denominator);
0265         if (numerator >
0266             (((u64)denominator) * max_frac) >> FPROP_FRAC_SHIFT)
0267             return;
0268     } else
0269         fprop_reflect_period_percpu(p, pl);
0270     __percpu_counter_add(&pl->events, 1, PROP_BATCH);
0271     percpu_counter_add(&p->events, 1);
0272 }