1 /*-
2 * Copyright (c) 2016-2019 Netflix, Inc.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27 /*
28 * Author: Randall Stewart <rrs@netflix.com>
29 */
30
31 #include <sys/types.h>
32 #include <sys/time.h>
33 #include <sys/errno.h>
34 #include <sys/tim_filter.h>
35
36 void
reset_time(struct time_filter * tf,uint32_t time_len)37 reset_time(struct time_filter *tf, uint32_t time_len)
38 {
39 tf->cur_time_limit = time_len;
40 }
41
42 void
reset_time_small(struct time_filter_small * tf,uint32_t time_len)43 reset_time_small(struct time_filter_small *tf, uint32_t time_len)
44 {
45 tf->cur_time_limit = time_len;
46 }
47
48 /*
49 * A time filter can be a filter for MIN or MAX.
50 * You call setup_time_filter() with the pointer to
51 * the filter structure, the type (FILTER_TYPE_MIN/MAX) and
52 * the time length. You can optionally reset the time length
53 * later with reset_time().
54 *
55 * You generally call apply_filter_xxx() to apply the new value
56 * to the filter. You also provide a time (now). The filter will
57 * age out entries based on the time now and your time limit
58 * so that you are always maintaining the min or max in that
59 * window of time. Time is a relative thing, it might be ticks
60 * in milliseconds, it might be round trip times, its really
61 * up to you to decide what it is.
62 *
63 * To access the current flitered value you can use the macro
64 * get_filter_value() which returns the correct entry that
65 * has the "current" value in the filter.
66 *
67 * One thing that used to be here is a single apply_filter(). But
68 * this meant that we then had to store the type of filter in
69 * the time_filter structure. In order to keep it at a cache
70 * line size I split it to two functions.
71 *
72 */
73 int
setup_time_filter(struct time_filter * tf,int fil_type,uint32_t time_len)74 setup_time_filter(struct time_filter *tf, int fil_type, uint32_t time_len)
75 {
76 uint64_t set_val;
77 int i;
78
79 /*
80 * You must specify either a MIN or MAX filter,
81 * though its up to the user to use the correct
82 * apply.
83 */
84 if ((fil_type != FILTER_TYPE_MIN) &&
85 (fil_type != FILTER_TYPE_MAX))
86 return(EINVAL);
87
88 if (time_len < NUM_FILTER_ENTRIES)
89 return(EINVAL);
90
91 if (fil_type == FILTER_TYPE_MIN)
92 set_val = 0xffffffffffffffff;
93 else
94 set_val = 0;
95
96 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
97 tf->entries[i].value = set_val;
98 tf->entries[i].time_up = 0;
99 }
100 tf->cur_time_limit = time_len;
101 return(0);
102 }
103
104 int
setup_time_filter_small(struct time_filter_small * tf,int fil_type,uint32_t time_len)105 setup_time_filter_small(struct time_filter_small *tf, int fil_type, uint32_t time_len)
106 {
107 uint32_t set_val;
108 int i;
109
110 /*
111 * You must specify either a MIN or MAX filter,
112 * though its up to the user to use the correct
113 * apply.
114 */
115 if ((fil_type != FILTER_TYPE_MIN) &&
116 (fil_type != FILTER_TYPE_MAX))
117 return(EINVAL);
118
119 if (time_len < NUM_FILTER_ENTRIES)
120 return(EINVAL);
121
122 if (fil_type == FILTER_TYPE_MIN)
123 set_val = 0xffffffff;
124 else
125 set_val = 0;
126
127 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
128 tf->entries[i].value = set_val;
129 tf->entries[i].time_up = 0;
130 }
131 tf->cur_time_limit = time_len;
132 return(0);
133 }
134
135 static void
check_update_times(struct time_filter * tf,uint64_t value,uint32_t now)136 check_update_times(struct time_filter *tf, uint64_t value, uint32_t now)
137 {
138 int i, j, fnd;
139 uint32_t tim;
140 uint32_t time_limit;
141 for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
142 tim = now - tf->entries[i].time_up;
143 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
144 if (tim >= time_limit) {
145 fnd = 0;
146 for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
147 if (tf->entries[i].time_up < tf->entries[j].time_up) {
148 tf->entries[i].value = tf->entries[j].value;
149 tf->entries[i].time_up = tf->entries[j].time_up;
150 fnd = 1;
151 break;
152 }
153 }
154 if (fnd == 0) {
155 /* Nothing but the same old entry */
156 tf->entries[i].value = value;
157 tf->entries[i].time_up = now;
158 }
159 }
160 }
161 i = NUM_FILTER_ENTRIES-1;
162 tim = now - tf->entries[i].time_up;
163 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
164 if (tim >= time_limit) {
165 tf->entries[i].value = value;
166 tf->entries[i].time_up = now;
167 }
168 }
169
170 static void
check_update_times_small(struct time_filter_small * tf,uint32_t value,uint32_t now)171 check_update_times_small(struct time_filter_small *tf, uint32_t value, uint32_t now)
172 {
173 int i, j, fnd;
174 uint32_t tim;
175 uint32_t time_limit;
176 for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
177 tim = now - tf->entries[i].time_up;
178 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
179 if (tim >= time_limit) {
180 fnd = 0;
181 for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
182 if (tf->entries[i].time_up < tf->entries[j].time_up) {
183 tf->entries[i].value = tf->entries[j].value;
184 tf->entries[i].time_up = tf->entries[j].time_up;
185 fnd = 1;
186 break;
187 }
188 }
189 if (fnd == 0) {
190 /* Nothing but the same old entry */
191 tf->entries[i].value = value;
192 tf->entries[i].time_up = now;
193 }
194 }
195 }
196 i = NUM_FILTER_ENTRIES-1;
197 tim = now - tf->entries[i].time_up;
198 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
199 if (tim >= time_limit) {
200 tf->entries[i].value = value;
201 tf->entries[i].time_up = now;
202 }
203 }
204
205 void
filter_reduce_by(struct time_filter * tf,uint64_t reduce_by,uint32_t now)206 filter_reduce_by(struct time_filter *tf, uint64_t reduce_by, uint32_t now)
207 {
208 int i;
209 /*
210 * Reduce our filter main by reduce_by and
211 * update its time. Then walk other's and
212 * make them the new value too.
213 */
214 if (reduce_by < tf->entries[0].value)
215 tf->entries[0].value -= reduce_by;
216 else
217 tf->entries[0].value = 0;
218 tf->entries[0].time_up = now;
219 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
220 tf->entries[i].value = tf->entries[0].value;
221 tf->entries[i].time_up = now;
222 }
223 }
224
225 void
filter_reduce_by_small(struct time_filter_small * tf,uint32_t reduce_by,uint32_t now)226 filter_reduce_by_small(struct time_filter_small *tf, uint32_t reduce_by, uint32_t now)
227 {
228 int i;
229 /*
230 * Reduce our filter main by reduce_by and
231 * update its time. Then walk other's and
232 * make them the new value too.
233 */
234 if (reduce_by < tf->entries[0].value)
235 tf->entries[0].value -= reduce_by;
236 else
237 tf->entries[0].value = 0;
238 tf->entries[0].time_up = now;
239 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
240 tf->entries[i].value = tf->entries[0].value;
241 tf->entries[i].time_up = now;
242 }
243 }
244
245 void
filter_increase_by(struct time_filter * tf,uint64_t incr_by,uint32_t now)246 filter_increase_by(struct time_filter *tf, uint64_t incr_by, uint32_t now)
247 {
248 int i;
249 /*
250 * Increase our filter main by incr_by and
251 * update its time. Then walk other's and
252 * make them the new value too.
253 */
254 tf->entries[0].value += incr_by;
255 tf->entries[0].time_up = now;
256 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
257 tf->entries[i].value = tf->entries[0].value;
258 tf->entries[i].time_up = now;
259 }
260 }
261
262 void
filter_increase_by_small(struct time_filter_small * tf,uint32_t incr_by,uint32_t now)263 filter_increase_by_small(struct time_filter_small *tf, uint32_t incr_by, uint32_t now)
264 {
265 int i;
266 /*
267 * Increase our filter main by incr_by and
268 * update its time. Then walk other's and
269 * make them the new value too.
270 */
271 tf->entries[0].value += incr_by;
272 tf->entries[0].time_up = now;
273 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
274 tf->entries[i].value = tf->entries[0].value;
275 tf->entries[i].time_up = now;
276 }
277 }
278
279 void
forward_filter_clock(struct time_filter * tf,uint32_t ticks_forward)280 forward_filter_clock(struct time_filter *tf, uint32_t ticks_forward)
281 {
282 /*
283 * Bring forward all time values by N ticks. This
284 * postpones expiring slots by that amount.
285 */
286 int i;
287
288 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
289 tf->entries[i].time_up += ticks_forward;
290 }
291 }
292
293 void
forward_filter_clock_small(struct time_filter_small * tf,uint32_t ticks_forward)294 forward_filter_clock_small(struct time_filter_small *tf, uint32_t ticks_forward)
295 {
296 /*
297 * Bring forward all time values by N ticks. This
298 * postpones expiring slots by that amount.
299 */
300 int i;
301
302 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
303 tf->entries[i].time_up += ticks_forward;
304 }
305 }
306
307 void
tick_filter_clock(struct time_filter * tf,uint32_t now)308 tick_filter_clock(struct time_filter *tf, uint32_t now)
309 {
310 int i;
311 uint32_t tim, time_limit;
312
313 /*
314 * We start at two positions back. This
315 * is because the oldest worst value is
316 * preserved always, i.e. it can't expire
317 * due to clock ticking with no updated value.
318 *
319 * The other choice would be to fill it in with
320 * zero, but I don't like that option since
321 * some measurement is better than none (even
322 * if its your oldest measurement).
323 */
324 for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
325 tim = now - tf->entries[i].time_up;
326 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
327 if (tim >= time_limit) {
328 /*
329 * This entry is expired, pull down
330 * the next one up.
331 */
332 tf->entries[i].value = tf->entries[(i+1)].value;
333 tf->entries[i].time_up = tf->entries[(i+1)].time_up;
334 }
335 }
336 }
337
338 void
tick_filter_clock_small(struct time_filter_small * tf,uint32_t now)339 tick_filter_clock_small(struct time_filter_small *tf, uint32_t now)
340 {
341 int i;
342 uint32_t tim, time_limit;
343
344 /*
345 * We start at two positions back. This
346 * is because the oldest worst value is
347 * preserved always, i.e. it can't expire
348 * due to clock ticking with no updated value.
349 *
350 * The other choice would be to fill it in with
351 * zero, but I don't like that option since
352 * some measurement is better than none (even
353 * if its your oldest measurement).
354 */
355 for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
356 tim = now - tf->entries[i].time_up;
357 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
358 if (tim >= time_limit) {
359 /*
360 * This entry is expired, pull down
361 * the next one up.
362 */
363 tf->entries[i].value = tf->entries[(i+1)].value;
364 tf->entries[i].time_up = tf->entries[(i+1)].time_up;
365 }
366 }
367 }
368
369 uint32_t
apply_filter_min(struct time_filter * tf,uint64_t value,uint32_t now)370 apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now)
371 {
372 int i, j;
373
374 if (value <= tf->entries[0].value) {
375 /* Zap them all */
376 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
377 tf->entries[i].value = value;
378 tf->entries[i].time_up = now;
379 }
380 return (tf->entries[0].value);
381 }
382 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
383 if (value <= tf->entries[j].value) {
384 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
385 tf->entries[i].value = value;
386 tf->entries[i].time_up = now;
387 }
388 break;
389 }
390 }
391 check_update_times(tf, value, now);
392 return (tf->entries[0].value);
393 }
394
395 uint32_t
apply_filter_min_small(struct time_filter_small * tf,uint32_t value,uint32_t now)396 apply_filter_min_small(struct time_filter_small *tf,
397 uint32_t value, uint32_t now)
398 {
399 int i, j;
400
401 if (value <= tf->entries[0].value) {
402 /* Zap them all */
403 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
404 tf->entries[i].value = value;
405 tf->entries[i].time_up = now;
406 }
407 return (tf->entries[0].value);
408 }
409 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
410 if (value <= tf->entries[j].value) {
411 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
412 tf->entries[i].value = value;
413 tf->entries[i].time_up = now;
414 }
415 break;
416 }
417 }
418 check_update_times_small(tf, value, now);
419 return (tf->entries[0].value);
420 }
421
422 uint32_t
apply_filter_max(struct time_filter * tf,uint64_t value,uint32_t now)423 apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now)
424 {
425 int i, j;
426
427 if (value >= tf->entries[0].value) {
428 /* Zap them all */
429 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
430 tf->entries[i].value = value;
431 tf->entries[i].time_up = now;
432 }
433 return (tf->entries[0].value);
434 }
435 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
436 if (value >= tf->entries[j].value) {
437 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
438 tf->entries[i].value = value;
439 tf->entries[i].time_up = now;
440 }
441 break;
442 }
443 }
444 check_update_times(tf, value, now);
445 return (tf->entries[0].value);
446 }
447
448 uint32_t
apply_filter_max_small(struct time_filter_small * tf,uint32_t value,uint32_t now)449 apply_filter_max_small(struct time_filter_small *tf,
450 uint32_t value, uint32_t now)
451 {
452 int i, j;
453
454 if (value >= tf->entries[0].value) {
455 /* Zap them all */
456 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
457 tf->entries[i].value = value;
458 tf->entries[i].time_up = now;
459 }
460 return (tf->entries[0].value);
461 }
462 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
463 if (value >= tf->entries[j].value) {
464 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
465 tf->entries[i].value = value;
466 tf->entries[i].time_up = now;
467 }
468 break;
469 }
470 }
471 check_update_times_small(tf, value, now);
472 return (tf->entries[0].value);
473 }
474