lib/win_minmax.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * lib/minmax.c: windowed min/max tracker
   4  *
   5  * Kathleen Nichols' algorithm for tracking the minimum (or maximum)
   6  * value of a data stream over some fixed time interval.  (E.g.,
   7  * the minimum RTT over the past five minutes.) It uses constant
   8  * space and constant time per update yet almost always delivers
   9  * the same minimum as an implementation that has to keep all the
  10  * data in the window.
  11  *
  12  * The algorithm keeps track of the best, 2nd best & 3rd best min
  13  * values, maintaining an invariant that the measurement time of
  14  * the n'th best >= n-1'th best. It also makes sure that the three
  15  * values are widely separated in the time window since that bounds
  16  * the worse case error when that data is monotonically increasing
  17  * over the window.
  18  *
  19  * Upon getting a new min, we can forget everything earlier because
  20  * it has no value - the new min is <= everything else in the window
  21  * by definition and it's the most recent. So we restart fresh on
  22  * every new min and overwrites 2nd & 3rd choices. The same property
  23  * holds for 2nd & 3rd best.
  24  */
  25 #include <linux/module.h>
  26 #include <linux/win_minmax.h>
  27
  28 /* As time advances, update the 1st, 2nd, and 3rd choices. */
  29 static u32 minmax_subwin_update(struct minmax *m, u32 win,
  30                                 const struct minmax_sample *val)
  31 {
  32         u32 dt = val->t - m->s[0].t;
  33
  34         if (unlikely(dt > win)) {
  35                 /*
  36                  * Passed entire window without a new val so make 2nd
  37                  * choice the new val & 3rd choice the new 2nd choice.
  38                  * we may have to iterate this since our 2nd choice
  39                  * may also be outside the window (we checked on entry
  40                  * that the third choice was in the window).
  41                  */
  42                 m->s[0] = m->s[1];
  43                 m->s[1] = m->s[2];
  44                 m->s[2] = *val;
  45                 if (unlikely(val->t - m->s[0].t > win)) {
  46                         m->s[0] = m->s[1];
  47                         m->s[1] = m->s[2];
  48                         m->s[2] = *val;
  49                 }
  50         } else if (unlikely(m->s[1].t == m->s[0].t) && dt > win/4) {
  51                 /*
  52                  * We've passed a quarter of the window without a new val
  53                  * so take a 2nd choice from the 2nd quarter of the window.
  54                  */
  55                 m->s[2] = m->s[1] = *val;
  56         } else if (unlikely(m->s[2].t == m->s[1].t) && dt > win/2) {
  57                 /*
  58                  * We've passed half the window without finding a new val
  59                  * so take a 3rd choice from the last half of the window
  60                  */
  61                 m->s[2] = *val;
  62         }
  63         return m->s[0].v;
  64 }
  65
  66 /* Check if new measurement updates the 1st, 2nd or 3rd choice max. */
  67 u32 minmax_running_max(struct minmax *m, u32 win, u32 t, u32 meas)
  68 {
  69         struct minmax_sample val = { .t = t, .v = meas };
  70
  71         if (unlikely(val.v >= m->s[0].v) ||       /* found new max? */
  72             unlikely(val.t - m->s[2].t > win))    /* nothing left in window? */
  73                 return minmax_reset(m, t, meas);  /* forget earlier samples */
  74
  75         if (unlikely(val.v >= m->s[1].v))
  76                 m->s[2] = m->s[1] = val;
  77         else if (unlikely(val.v >= m->s[2].v))
  78                 m->s[2] = val;
  79
  80         return minmax_subwin_update(m, win, &val);
  81 }
  82 EXPORT_SYMBOL(minmax_running_max);
  83
  84 /* Check if new measurement updates the 1st, 2nd or 3rd choice min. */
  85 u32 minmax_running_min(struct minmax *m, u32 win, u32 t, u32 meas)
  86 {
  87         struct minmax_sample val = { .t = t, .v = meas };
  88
  89         if (unlikely(val.v <= m->s[0].v) ||       /* found new min? */
  90             unlikely(val.t - m->s[2].t > win))    /* nothing left in window? */
  91                 return minmax_reset(m, t, meas);  /* forget earlier samples */
  92
  93         if (unlikely(val.v <= m->s[1].v))
  94                 m->s[2] = m->s[1] = val;
  95         else if (unlikely(val.v <= m->s[2].v))
  96                 m->s[2] = val;
  97
  98         return minmax_subwin_update(m, win, &val);
  99 }