• ** source navigation** • diff markup • identifier search • freetext search • Try Elixir Beta •

Version: 2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 *4.10*

12/**3* lib/minmax.c: windowed min/max tracker4*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 constant8* space and constant time per update yet almost always delivers9* the same minimum as an implementation that has to keep all the10* data in the window.11*12* The algorithm keeps track of the best, 2nd best & 3rd best min13* values, maintaining an invariant that the measurement time of14* the n'th best >= n-1'th best. It also makes sure that the three15* values are widely separated in the time window since that bounds16* the worse case error when that data is monotonically increasing17* over the window.18*19* Upon getting a new min, we can forget everything earlier because20* it has no value - the new min is <= everything else in the window21* by definition and it's the most recent. So we restart fresh on22* every new min and overwrites 2nd & 3rd choices. The same property23* holds for 2nd & 3rd best.24 #include <linux/module.h> 25 #include <linux/win_minmax.h> 26 27*/28 static u32 minmax_subwin_update(struct minmax *m, u32 win, 29 const struct minmax_sample *val) 30 { 31 u32 dt = val->t - m->s[0].t; 32 33 if (unlikely(dt > win)) { 34/* As time advances, update the 1st, 2nd, and 3rd choices. */35/*36* Passed entire window without a new val so make 2nd37* choice the new val & 3rd choice the new 2nd choice.38* we may have to iterate this since our 2nd choice39* may also be outside the window (we checked on entry40* that the third choice was in the window).41 m->s[0] = m->s[1]; 42 m->s[1] = m->s[2]; 43 m->s[2] = *val; 44 if (unlikely(val->t - m->s[0].t > win)) { 45 m->s[0] = m->s[1]; 46 m->s[1] = m->s[2]; 47 m->s[2] = *val; 48 } 49 } else if (unlikely(m->s[1].t == m->s[0].t) && dt > win/4) { 50*/51/*52* We've passed a quarter of the window without a new val53* so take a 2nd choice from the 2nd quarter of the window.54 m->s[2] = m->s[1] = *val; 55 } else if (unlikely(m->s[2].t == m->s[1].t) && dt > win/2) { 56*/57/*58* We've passed half the window without finding a new val59* so take a 3rd choice from the last half of the window60 m->s[2] = *val; 61 } 62 return m->s[0].v; 63 } 64 65*/66 u32 minmax_running_max(struct minmax *m, u32 win, u32 t, u32 meas) 67 { 68 struct minmax_sample val = { .t = t, .v = meas }; 69 70 if (unlikely(val.v >= m->s[0].v) ||/* Check if new measurement updates the 1st, 2nd or 3rd choice max. */71 unlikely(val.t - m->s[2].t > win))/* found new max? */72 return minmax_reset(m, t, meas);/* nothing left in window? */73 74 if (unlikely(val.v >= m->s[1].v)) 75 m->s[2] = m->s[1] = val; 76 else if (unlikely(val.v >= m->s[2].v)) 77 m->s[2] = val; 78 79 return minmax_subwin_update(m, win, &val); 80 } 81 EXPORT_SYMBOL(minmax_running_max); 82 83/* forget earlier samples */84 u32 minmax_running_min(struct minmax *m, u32 win, u32 t, u32 meas) 85 { 86 struct minmax_sample val = { .t = t, .v = meas }; 87 88 if (unlikely(val.v <= m->s[0].v) ||/* Check if new measurement updates the 1st, 2nd or 3rd choice min. */89 unlikely(val.t - m->s[2].t > win))/* found new min? */90 return minmax_reset(m, t, meas);/* nothing left in window? */91 92 if (unlikely(val.v <= m->s[1].v)) 93 m->s[2] = m->s[1] = val; 94 else if (unlikely(val.v <= m->s[2].v)) 95 m->s[2] = val; 96 97 return minmax_subwin_update(m, win, &val); 98 } 99/* forget earlier samples */

This page was automatically generated by LXR 0.3.1 (source). • Linux is a registered trademark of Linus Torvalds • Contact us