2 * Copyright (c) 2016-2019 Netflix, Inc.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
28 * Author: Randall Stewart <rrs@netflix.com>
30 #include <sys/cdefs.h>
31 __FBSDID("$FreeBSD$");
32 #include <sys/types.h>
34 #include <sys/errno.h>
35 #include <sys/tim_filter.h>
38 reset_time(struct time_filter *tf, uint32_t time_len)
40 tf->cur_time_limit = time_len;
44 reset_time_small(struct time_filter_small *tf, uint32_t time_len)
46 tf->cur_time_limit = time_len;
50 * A time filter can be a filter for MIN or MAX.
51 * You call setup_time_filter() with the pointer to
52 * the filter structure, the type (FILTER_TYPE_MIN/MAX) and
53 * the time length. You can optionally reset the time length
54 * later with reset_time().
56 * You generally call apply_filter_xxx() to apply the new value
57 * to the filter. You also provide a time (now). The filter will
58 * age out entries based on the time now and your time limit
59 * so that you are always maintaining the min or max in that
60 * window of time. Time is a relative thing, it might be ticks
61 * in milliseconds, it might be round trip times, its really
62 * up to you to decide what it is.
64 * To access the current flitered value you can use the macro
65 * get_filter_value() which returns the correct entry that
66 * has the "current" value in the filter.
68 * One thing that used to be here is a single apply_filter(). But
69 * this meant that we then had to store the type of filter in
70 * the time_filter structure. In order to keep it at a cache
71 * line size I split it to two functions.
75 setup_time_filter(struct time_filter *tf, int fil_type, uint32_t time_len)
81 * You must specify either a MIN or MAX filter,
82 * though its up to the user to use the correct
85 if ((fil_type != FILTER_TYPE_MIN) &&
86 (fil_type != FILTER_TYPE_MAX))
89 if (time_len < NUM_FILTER_ENTRIES)
92 if (fil_type == FILTER_TYPE_MIN)
93 set_val = 0xffffffffffffffff;
97 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
98 tf->entries[i].value = set_val;
99 tf->entries[i].time_up = 0;
101 tf->cur_time_limit = time_len;
106 setup_time_filter_small(struct time_filter_small *tf, int fil_type, uint32_t time_len)
112 * You must specify either a MIN or MAX filter,
113 * though its up to the user to use the correct
116 if ((fil_type != FILTER_TYPE_MIN) &&
117 (fil_type != FILTER_TYPE_MAX))
120 if (time_len < NUM_FILTER_ENTRIES)
123 if (fil_type == FILTER_TYPE_MIN)
124 set_val = 0xffffffff;
128 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
129 tf->entries[i].value = set_val;
130 tf->entries[i].time_up = 0;
132 tf->cur_time_limit = time_len;
137 check_update_times(struct time_filter *tf, uint64_t value, uint32_t now)
142 for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
143 tim = now - tf->entries[i].time_up;
144 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
145 if (tim >= time_limit) {
147 for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
148 if (tf->entries[i].time_up < tf->entries[j].time_up) {
149 tf->entries[i].value = tf->entries[j].value;
150 tf->entries[i].time_up = tf->entries[j].time_up;
156 /* Nothing but the same old entry */
157 tf->entries[i].value = value;
158 tf->entries[i].time_up = now;
162 i = NUM_FILTER_ENTRIES-1;
163 tim = now - tf->entries[i].time_up;
164 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
165 if (tim >= time_limit) {
166 tf->entries[i].value = value;
167 tf->entries[i].time_up = now;
172 check_update_times_small(struct time_filter_small *tf, uint32_t value, uint32_t now)
177 for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
178 tim = now - tf->entries[i].time_up;
179 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
180 if (tim >= time_limit) {
182 for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
183 if (tf->entries[i].time_up < tf->entries[j].time_up) {
184 tf->entries[i].value = tf->entries[j].value;
185 tf->entries[i].time_up = tf->entries[j].time_up;
191 /* Nothing but the same old entry */
192 tf->entries[i].value = value;
193 tf->entries[i].time_up = now;
197 i = NUM_FILTER_ENTRIES-1;
198 tim = now - tf->entries[i].time_up;
199 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
200 if (tim >= time_limit) {
201 tf->entries[i].value = value;
202 tf->entries[i].time_up = now;
207 filter_reduce_by(struct time_filter *tf, uint64_t reduce_by, uint32_t now)
211 * Reduce our filter main by reduce_by and
212 * update its time. Then walk other's and
213 * make them the new value too.
215 if (reduce_by < tf->entries[0].value)
216 tf->entries[0].value -= reduce_by;
218 tf->entries[0].value = 0;
219 tf->entries[0].time_up = now;
220 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
221 tf->entries[i].value = tf->entries[0].value;
222 tf->entries[i].time_up = now;
227 filter_reduce_by_small(struct time_filter_small *tf, uint32_t reduce_by, uint32_t now)
231 * Reduce our filter main by reduce_by and
232 * update its time. Then walk other's and
233 * make them the new value too.
235 if (reduce_by < tf->entries[0].value)
236 tf->entries[0].value -= reduce_by;
238 tf->entries[0].value = 0;
239 tf->entries[0].time_up = now;
240 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
241 tf->entries[i].value = tf->entries[0].value;
242 tf->entries[i].time_up = now;
247 filter_increase_by(struct time_filter *tf, uint64_t incr_by, uint32_t now)
251 * Increase our filter main by incr_by and
252 * update its time. Then walk other's and
253 * make them the new value too.
255 tf->entries[0].value += incr_by;
256 tf->entries[0].time_up = now;
257 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
258 tf->entries[i].value = tf->entries[0].value;
259 tf->entries[i].time_up = now;
264 filter_increase_by_small(struct time_filter_small *tf, uint32_t incr_by, uint32_t now)
268 * Increase our filter main by incr_by and
269 * update its time. Then walk other's and
270 * make them the new value too.
272 tf->entries[0].value += incr_by;
273 tf->entries[0].time_up = now;
274 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
275 tf->entries[i].value = tf->entries[0].value;
276 tf->entries[i].time_up = now;
281 forward_filter_clock(struct time_filter *tf, uint32_t ticks_forward)
284 * Bring forward all time values by N ticks. This
285 * postpones expiring slots by that amount.
289 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
290 tf->entries[i].time_up += ticks_forward;
295 forward_filter_clock_small(struct time_filter_small *tf, uint32_t ticks_forward)
298 * Bring forward all time values by N ticks. This
299 * postpones expiring slots by that amount.
303 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
304 tf->entries[i].time_up += ticks_forward;
309 tick_filter_clock(struct time_filter *tf, uint32_t now)
312 uint32_t tim, time_limit;
315 * We start at two positions back. This
316 * is because the oldest worst value is
317 * preserved always, i.e. it can't expire
318 * due to clock ticking with no updated value.
320 * The other choice would be to fill it in with
321 * zero, but I don't like that option since
322 * some measurement is better than none (even
323 * if its your oldest measurment).
325 for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
326 tim = now - tf->entries[i].time_up;
327 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
328 if (tim >= time_limit) {
330 * This entry is expired, pull down
333 tf->entries[i].value = tf->entries[(i+1)].value;
334 tf->entries[i].time_up = tf->entries[(i+1)].time_up;
340 tick_filter_clock_small(struct time_filter_small *tf, uint32_t now)
343 uint32_t tim, time_limit;
346 * We start at two positions back. This
347 * is because the oldest worst value is
348 * preserved always, i.e. it can't expire
349 * due to clock ticking with no updated value.
351 * The other choice would be to fill it in with
352 * zero, but I don't like that option since
353 * some measurement is better than none (even
354 * if its your oldest measurment).
356 for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
357 tim = now - tf->entries[i].time_up;
358 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
359 if (tim >= time_limit) {
361 * This entry is expired, pull down
364 tf->entries[i].value = tf->entries[(i+1)].value;
365 tf->entries[i].time_up = tf->entries[(i+1)].time_up;
371 apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now)
375 if (value <= tf->entries[0].value) {
377 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
378 tf->entries[i].value = value;
379 tf->entries[i].time_up = now;
381 return (tf->entries[0].value);
383 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
384 if (value <= tf->entries[j].value) {
385 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
386 tf->entries[i].value = value;
387 tf->entries[i].time_up = now;
392 check_update_times(tf, value, now);
393 return (tf->entries[0].value);
397 apply_filter_min_small(struct time_filter_small *tf,
398 uint32_t value, uint32_t now)
402 if (value <= tf->entries[0].value) {
404 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
405 tf->entries[i].value = value;
406 tf->entries[i].time_up = now;
408 return (tf->entries[0].value);
410 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
411 if (value <= tf->entries[j].value) {
412 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
413 tf->entries[i].value = value;
414 tf->entries[i].time_up = now;
419 check_update_times_small(tf, value, now);
420 return (tf->entries[0].value);
424 apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now)
428 if (value >= tf->entries[0].value) {
430 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
431 tf->entries[i].value = value;
432 tf->entries[i].time_up = now;
434 return (tf->entries[0].value);
436 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
437 if (value >= tf->entries[j].value) {
438 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
439 tf->entries[i].value = value;
440 tf->entries[i].time_up = now;
445 check_update_times(tf, value, now);
446 return (tf->entries[0].value);
450 apply_filter_max_small(struct time_filter_small *tf,
451 uint32_t value, uint32_t now)
455 if (value >= tf->entries[0].value) {
457 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
458 tf->entries[i].value = value;
459 tf->entries[i].time_up = now;
461 return (tf->entries[0].value);
463 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
464 if (value >= tf->entries[j].value) {
465 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
466 tf->entries[i].value = value;
467 tf->entries[i].time_up = now;
472 check_update_times_small(tf, value, now);
473 return (tf->entries[0].value);