Branch data Line data Source code
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 : 0 : static u32 minmax_subwin_update(struct minmax *m, u32 win, 30 : : const struct minmax_sample *val) 31 : : { 32 : 0 : u32 dt = val->t - m->s[0].t; 33 : : 34 [ # # ]: 0 : 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 : 0 : m->s[0] = m->s[1]; 43 : 0 : m->s[1] = m->s[2]; 44 : 0 : m->s[2] = *val; 45 [ # # ]: 0 : if (unlikely(val->t - m->s[0].t > win)) { 46 : 0 : m->s[0] = m->s[1]; 47 : 0 : m->s[1] = m->s[2]; 48 : 0 : m->s[2] = *val; 49 : : } 50 [ # # # # ]: 0 : } 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 : 0 : m->s[2] = m->s[1] = *val; 56 [ # # # # ]: 0 : } 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 : 0 : m->s[2] = *val; 62 : : } 63 : 0 : return m->s[0].v; 64 : : } 65 : : 66 : : /* Check if new measurement updates the 1st, 2nd or 3rd choice max. */ 67 : 0 : u32 minmax_running_max(struct minmax *m, u32 win, u32 t, u32 meas) 68 : : { 69 : 0 : struct minmax_sample val = { .t = t, .v = meas }; 70 : : 71 [ # # ]: 0 : if (unlikely(val.v >= m->s[0].v) || /* found new max? */ 72 [ # # ]: 0 : unlikely(val.t - m->s[2].t > win)) /* nothing left in window? */ 73 : 0 : return minmax_reset(m, t, meas); /* forget earlier samples */ 74 : : 75 [ # # ]: 0 : if (unlikely(val.v >= m->s[1].v)) 76 : 0 : m->s[2] = m->s[1] = val; 77 [ # # ]: 0 : else if (unlikely(val.v >= m->s[2].v)) 78 : 0 : m->s[2] = val; 79 : : 80 : 0 : 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 : 0 : u32 minmax_running_min(struct minmax *m, u32 win, u32 t, u32 meas) 86 : : { 87 : 0 : struct minmax_sample val = { .t = t, .v = meas }; 88 : : 89 [ # # ]: 0 : if (unlikely(val.v <= m->s[0].v) || /* found new min? */ 90 [ # # ]: 0 : unlikely(val.t - m->s[2].t > win)) /* nothing left in window? */ 91 : 0 : return minmax_reset(m, t, meas); /* forget earlier samples */ 92 : : 93 [ # # ]: 0 : if (unlikely(val.v <= m->s[1].v)) 94 : 0 : m->s[2] = m->s[1] = val; 95 [ # # ]: 0 : else if (unlikely(val.v <= m->s[2].v)) 96 : 0 : m->s[2] = val; 97 : : 98 : 0 : return minmax_subwin_update(m, win, &val); 99 : : }