"Fossies" - the Fresh Open Source Software Archive

Member "haproxy-2.0.0/include/proto/freq_ctr.h" (16 Jun 2019, 10968 Bytes) of package /linux/misc/haproxy-2.0.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "freq_ctr.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 1.9.8_vs_2.0.0.

    1 /*
    2  * include/proto/freq_ctr.h
    3  * This file contains macros and inline functions for frequency counters.
    4  *
    5  * Copyright (C) 2000-2014 Willy Tarreau - w@1wt.eu
    6  *
    7  * This library is free software; you can redistribute it and/or
    8  * modify it under the terms of the GNU Lesser General Public
    9  * License as published by the Free Software Foundation, version 2.1
   10  * exclusively.
   11  *
   12  * This library is distributed in the hope that it will be useful,
   13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   15  * Lesser General Public License for more details.
   16  *
   17  * You should have received a copy of the GNU Lesser General Public
   18  * License along with this library; if not, write to the Free Software
   19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
   20  */
   21 
   22 #ifndef _PROTO_FREQ_CTR_H
   23 #define _PROTO_FREQ_CTR_H
   24 
   25 #include <common/config.h>
   26 #include <common/time.h>
   27 #include <common/hathreads.h>
   28 #include <types/freq_ctr.h>
   29 
   30 
   31 /* Update a frequency counter by <inc> incremental units. It is automatically
   32  * rotated if the period is over. It is important that it correctly initializes
   33  * a null area.
   34  */
   35 static inline unsigned int update_freq_ctr(struct freq_ctr *ctr, unsigned int inc)
   36 {
   37     int elapsed;
   38     unsigned int curr_sec;
   39 
   40 
   41     /* we manipulate curr_ctr using atomic ops out of the lock, since
   42      * it's the most frequent access. However if we detect that a change
   43      * is needed, it's done under the date lock. We don't care whether
   44      * the value we're adding is considered as part of the current or
   45      * new period if another thread starts to rotate the period while
   46      * we operate, since timing variations would have resulted in the
   47      * same uncertainty as well.
   48      */
   49     curr_sec = ctr->curr_sec;
   50     if (curr_sec == (now.tv_sec & 0x7fffffff))
   51         return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc);
   52 
   53     do {
   54         /* remove the bit, used for the lock */
   55         curr_sec &= 0x7fffffff;
   56     } while (!_HA_ATOMIC_CAS(&ctr->curr_sec, &curr_sec, curr_sec | 0x80000000));
   57     __ha_barrier_atomic_store();
   58 
   59     elapsed = (now.tv_sec & 0x7fffffff)- curr_sec;
   60     if (unlikely(elapsed > 0)) {
   61         ctr->prev_ctr = ctr->curr_ctr;
   62         _HA_ATOMIC_SUB(&ctr->curr_ctr, ctr->prev_ctr);
   63         if (likely(elapsed != 1)) {
   64             /* we missed more than one second */
   65             ctr->prev_ctr = 0;
   66         }
   67         curr_sec = now.tv_sec;
   68     }
   69 
   70     /* release the lock and update the time in case of rotate. */
   71     _HA_ATOMIC_STORE(&ctr->curr_sec, curr_sec & 0x7fffffff);
   72 
   73     return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc);
   74 }
   75 
   76 /* Update a frequency counter by <inc> incremental units. It is automatically
   77  * rotated if the period is over. It is important that it correctly initializes
   78  * a null area. This one works on frequency counters which have a period
   79  * different from one second.
   80  */
   81 static inline unsigned int update_freq_ctr_period(struct freq_ctr_period *ctr,
   82                           unsigned int period, unsigned int inc)
   83 {
   84     unsigned int curr_tick;
   85 
   86     curr_tick = ctr->curr_tick;
   87     if (now_ms - curr_tick < period)
   88         return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc);
   89 
   90     do {
   91         /* remove the bit, used for the lock */
   92         curr_tick &= ~1;
   93     } while (!_HA_ATOMIC_CAS(&ctr->curr_tick, &curr_tick, curr_tick | 0x1));
   94     __ha_barrier_atomic_store();
   95 
   96     if (now_ms - curr_tick >= period) {
   97         ctr->prev_ctr = ctr->curr_ctr;
   98         _HA_ATOMIC_SUB(&ctr->curr_ctr, ctr->prev_ctr);
   99         curr_tick += period;
  100         if (likely(now_ms - curr_tick >= period)) {
  101             /* we missed at least two periods */
  102             ctr->prev_ctr = 0;
  103             curr_tick = now_ms;
  104         }
  105         curr_tick &= ~1;
  106     }
  107 
  108     /* release the lock and update the time in case of rotate. */
  109     _HA_ATOMIC_STORE(&ctr->curr_tick, curr_tick);
  110 
  111     return _HA_ATOMIC_ADD(&ctr->curr_ctr, inc);
  112 }
  113 
  114 /* Read a frequency counter taking history into account for missing time in
  115  * current period.
  116  */
  117 unsigned int read_freq_ctr(struct freq_ctr *ctr);
  118 
  119 /* returns the number of remaining events that can occur on this freq counter
  120  * while respecting <freq> and taking into account that <pend> events are
  121  * already known to be pending. Returns 0 if limit was reached.
  122  */
  123 unsigned int freq_ctr_remain(struct freq_ctr *ctr, unsigned int freq, unsigned int pend);
  124 
  125 /* return the expected wait time in ms before the next event may occur,
  126  * respecting frequency <freq>, and assuming there may already be some pending
  127  * events. It returns zero if we can proceed immediately, otherwise the wait
  128  * time, which will be rounded down 1ms for better accuracy, with a minimum
  129  * of one ms.
  130  */
  131 unsigned int next_event_delay(struct freq_ctr *ctr, unsigned int freq, unsigned int pend);
  132 
  133 /* process freq counters over configurable periods */
  134 unsigned int read_freq_ctr_period(struct freq_ctr_period *ctr, unsigned int period);
  135 unsigned int freq_ctr_remain_period(struct freq_ctr_period *ctr, unsigned int period,
  136                     unsigned int freq, unsigned int pend);
  137 
  138 /* While the functions above report average event counts per period, we are
  139  * also interested in average values per event. For this we use a different
  140  * method. The principle is to rely on a long tail which sums the new value
  141  * with a fraction of the previous value, resulting in a sliding window of
  142  * infinite length depending on the precision we're interested in.
  143  *
  144  * The idea is that we always keep (N-1)/N of the sum and add the new sampled
  145  * value. The sum over N values can be computed with a simple program for a
  146  * constant value 1 at each iteration :
  147  *
  148  *     N
  149  *   ,---
  150  *    \       N - 1              e - 1
  151  *     >  ( --------- )^x ~= N * -----
  152  *    /         N                  e
  153  *   '---
  154  *   x = 1
  155  *
  156  * Note: I'm not sure how to demonstrate this but at least this is easily
  157  * verified with a simple program, the sum equals N * 0.632120 for any N
  158  * moderately large (tens to hundreds).
  159  *
  160  * Inserting a constant sample value V here simply results in :
  161  *
  162  *    sum = V * N * (e - 1) / e
  163  *
  164  * But we don't want to integrate over a small period, but infinitely. Let's
  165  * cut the infinity in P periods of N values. Each period M is exactly the same
  166  * as period M-1 with a factor of ((N-1)/N)^N applied. A test shows that given a
  167  * large N :
  168  *
  169  *      N - 1           1
  170  *   ( ------- )^N ~=  ---
  171  *        N             e
  172  *
  173  * Our sum is now a sum of each factor times  :
  174  *
  175  *    N*P                                     P
  176  *   ,---                                   ,---
  177  *    \         N - 1               e - 1    \     1
  178  *     >  v ( --------- )^x ~= VN * -----  *  >   ---
  179  *    /           N                   e      /    e^x
  180  *   '---                                   '---
  181  *   x = 1                                  x = 0
  182  *
  183  * For P "large enough", in tests we get this :
  184  *
  185  *    P
  186  *  ,---
  187  *   \     1        e
  188  *    >   --- ~=  -----
  189  *   /    e^x     e - 1
  190  *  '---
  191  *  x = 0
  192  *
  193  * This simplifies the sum above :
  194  *
  195  *    N*P
  196  *   ,---
  197  *    \         N - 1
  198  *     >  v ( --------- )^x = VN
  199  *    /           N
  200  *   '---
  201  *   x = 1
  202  *
  203  * So basically by summing values and applying the last result an (N-1)/N factor
  204  * we just get N times the values over the long term, so we can recover the
  205  * constant value V by dividing by N. In order to limit the impact of integer
  206  * overflows, we'll use this equivalence which saves us one multiply :
  207  *
  208  *               N - 1                   1             x0
  209  *    x1 = x0 * -------   =  x0 * ( 1 - --- )  = x0 - ----
  210  *                 N                     N              N
  211  *
  212  * And given that x0 is discrete here we'll have to saturate the values before
  213  * performing the divide, so the value insertion will become :
  214  *
  215  *               x0 + N - 1
  216  *    x1 = x0 - ------------
  217  *                    N
  218  *
  219  * A value added at the entry of the sliding window of N values will thus be
  220  * reduced to 1/e or 36.7% after N terms have been added. After a second batch,
  221  * it will only be 1/e^2, or 13.5%, and so on. So practically speaking, each
  222  * old period of N values represents only a quickly fading ratio of the global
  223  * sum :
  224  *
  225  *   period    ratio
  226  *     1       36.7%
  227  *     2       13.5%
  228  *     3       4.98%
  229  *     4       1.83%
  230  *     5       0.67%
  231  *     6       0.25%
  232  *     7       0.09%
  233  *     8       0.033%
  234  *     9       0.012%
  235  *    10       0.0045%
  236  *
  237  * So after 10N samples, the initial value has already faded out by a factor of
  238  * 22026, which is quite fast. If the sliding window is 1024 samples wide, it
  239  * means that a sample will only count for 1/22k of its initial value after 10k
  240  * samples went after it, which results in half of the value it would represent
  241  * using an arithmetic mean. The benefit of this method is that it's very cheap
  242  * in terms of computations when N is a power of two. This is very well suited
  243  * to record response times as large values will fade out faster than with an
  244  * arithmetic mean and will depend on sample count and not time.
  245  *
  246  * Demonstrating all the above assumptions with maths instead of a program is
  247  * left as an exercise for the reader.
  248  */
  249 
  250 /* Adds sample value <v> to sliding window sum <sum> configured for <n> samples.
  251  * The sample is returned. Better if <n> is a power of two.
  252  */
  253 static inline unsigned int swrate_add(unsigned int *sum, unsigned int n, unsigned int v)
  254 {
  255     return *sum = *sum - (*sum + n - 1) / n + v;
  256 }
  257 
  258 /* Adds sample value <v> spanning <s> samples to sliding window sum <sum>
  259  * configured for <n> samples, where <n> is supposed to be "much larger" than
  260  * <s>. The sample is returned. Better if <n> is a power of two. Note that this
  261  * is only an approximate. Indeed, as can be seen with two samples only over a
  262  * 8-sample window, the original function would return :
  263  *  sum1 = sum  - (sum + 7) / 8 + v
  264  *  sum2 = sum1 - (sum1 + 7) / 8 + v
  265  *       = (sum - (sum + 7) / 8 + v) - (sum - (sum + 7) / 8 + v + 7) / 8 + v
  266  *      ~= 7sum/8 - 7/8 + v - sum/8 + sum/64 - 7/64 - v/8 - 7/8 + v
  267  *      ~= (3sum/4 + sum/64) - (7/4 + 7/64) + 15v/8
  268  *
  269  * while the function below would return :
  270  *  sum  = sum + 2*v - (sum + 8) * 2 / 8
  271  *       = 3sum/4 + 2v - 2
  272  *
  273  * this presents an error of ~ (sum/64 + 9/64 + v/8) = (sum+n+1)/(n^s) + v/n
  274  *
  275  * Thus the simplified function effectively replaces a part of the history with
  276  * a linear sum instead of applying the exponential one. But as long as s/n is
  277  * "small enough", the error fades away and remains small for both small and
  278  * large values of n and s (typically < 0.2% measured).
  279  */
  280 static inline unsigned int swrate_add_scaled(unsigned int *sum, unsigned int n, unsigned int v, unsigned int s)
  281 {
  282     return *sum = *sum + v * s - div64_32((unsigned long long)(*sum + n) * s, n);
  283 }
  284 
  285 /* Returns the average sample value for the sum <sum> over a sliding window of
  286  * <n> samples. Better if <n> is a power of two. It must be the same <n> as the
  287  * one used above in all additions.
  288  */
  289 static inline unsigned int swrate_avg(unsigned int sum, unsigned int n)
  290 {
  291     return (sum + n - 1) / n;
  292 }
  293 
  294 #endif /* _PROTO_FREQ_CTR_H */
  295 
  296 /*
  297  * Local variables:
  298  *  c-indent-level: 8
  299  *  c-basic-offset: 8
  300  * End:
  301   */