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;
138 check_update_times(struct time_filter *tf, uint64_t value, uint32_t now)
143 for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
144 tim = now - tf->entries[i].time_up;
145 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
146 if (tim >= time_limit) {
148 for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
149 if (tf->entries[i].time_up < tf->entries[j].time_up) {
150 tf->entries[i].value = tf->entries[j].value;
151 tf->entries[i].time_up = tf->entries[j].time_up;
157 /* Nothing but the same old entry */
158 tf->entries[i].value = value;
159 tf->entries[i].time_up = now;
163 i = NUM_FILTER_ENTRIES-1;
164 tim = now - tf->entries[i].time_up;
165 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
166 if (tim >= time_limit) {
167 tf->entries[i].value = value;
168 tf->entries[i].time_up = now;
173 check_update_times_small(struct time_filter_small *tf, uint32_t value, uint32_t now)
178 for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
179 tim = now - tf->entries[i].time_up;
180 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
181 if (tim >= time_limit) {
183 for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
184 if (tf->entries[i].time_up < tf->entries[j].time_up) {
185 tf->entries[i].value = tf->entries[j].value;
186 tf->entries[i].time_up = tf->entries[j].time_up;
192 /* Nothing but the same old entry */
193 tf->entries[i].value = value;
194 tf->entries[i].time_up = now;
198 i = NUM_FILTER_ENTRIES-1;
199 tim = now - tf->entries[i].time_up;
200 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
201 if (tim >= time_limit) {
202 tf->entries[i].value = value;
203 tf->entries[i].time_up = now;
210 filter_reduce_by(struct time_filter *tf, uint64_t reduce_by, uint32_t now)
214 * Reduce our filter main by reduce_by and
215 * update its time. Then walk other's and
216 * make them the new value too.
218 if (reduce_by < tf->entries[0].value)
219 tf->entries[0].value -= reduce_by;
221 tf->entries[0].value = 0;
222 tf->entries[0].time_up = now;
223 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
224 tf->entries[i].value = tf->entries[0].value;
225 tf->entries[i].time_up = now;
230 filter_reduce_by_small(struct time_filter_small *tf, uint32_t reduce_by, uint32_t now)
234 * Reduce our filter main by reduce_by and
235 * update its time. Then walk other's and
236 * make them the new value too.
238 if (reduce_by < tf->entries[0].value)
239 tf->entries[0].value -= reduce_by;
241 tf->entries[0].value = 0;
242 tf->entries[0].time_up = now;
243 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
244 tf->entries[i].value = tf->entries[0].value;
245 tf->entries[i].time_up = now;
250 filter_increase_by(struct time_filter *tf, uint64_t incr_by, uint32_t now)
254 * Increase our filter main by incr_by and
255 * update its time. Then walk other's and
256 * make them the new value too.
258 tf->entries[0].value += incr_by;
259 tf->entries[0].time_up = now;
260 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
261 tf->entries[i].value = tf->entries[0].value;
262 tf->entries[i].time_up = now;
267 filter_increase_by_small(struct time_filter_small *tf, uint32_t incr_by, uint32_t now)
271 * Increase our filter main by incr_by and
272 * update its time. Then walk other's and
273 * make them the new value too.
275 tf->entries[0].value += incr_by;
276 tf->entries[0].time_up = now;
277 for(i=1; i<NUM_FILTER_ENTRIES; i++) {
278 tf->entries[i].value = tf->entries[0].value;
279 tf->entries[i].time_up = now;
284 forward_filter_clock(struct time_filter *tf, uint32_t ticks_forward)
287 * Bring forward all time values by N ticks. This
288 * postpones expiring slots by that amount.
292 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
293 tf->entries[i].time_up += ticks_forward;
299 forward_filter_clock_small(struct time_filter_small *tf, uint32_t ticks_forward)
302 * Bring forward all time values by N ticks. This
303 * postpones expiring slots by that amount.
307 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
308 tf->entries[i].time_up += ticks_forward;
314 tick_filter_clock(struct time_filter *tf, uint32_t now)
317 uint32_t tim, time_limit;
320 * We start at two positions back. This
321 * is because the oldest worst value is
322 * preserved always, i.e. it can't expire
323 * due to clock ticking with no updated value.
325 * The other choice would be to fill it in with
326 * zero, but I don't like that option since
327 * some measurement is better than none (even
328 * if its your oldest measurment).
330 for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
331 tim = now - tf->entries[i].time_up;
332 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
333 if (tim >= time_limit) {
335 * This entry is expired, pull down
338 tf->entries[i].value = tf->entries[(i+1)].value;
339 tf->entries[i].time_up = tf->entries[(i+1)].time_up;
346 tick_filter_clock_small(struct time_filter_small *tf, uint32_t now)
349 uint32_t tim, time_limit;
352 * We start at two positions back. This
353 * is because the oldest worst value is
354 * preserved always, i.e. it can't expire
355 * due to clock ticking with no updated value.
357 * The other choice would be to fill it in with
358 * zero, but I don't like that option since
359 * some measurement is better than none (even
360 * if its your oldest measurment).
362 for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
363 tim = now - tf->entries[i].time_up;
364 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
365 if (tim >= time_limit) {
367 * This entry is expired, pull down
370 tf->entries[i].value = tf->entries[(i+1)].value;
371 tf->entries[i].time_up = tf->entries[(i+1)].time_up;
378 apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now)
382 if (value <= tf->entries[0].value) {
384 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
385 tf->entries[i].value = value;
386 tf->entries[i].time_up = now;
388 return (tf->entries[0].value);
390 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
391 if (value <= tf->entries[j].value) {
392 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
393 tf->entries[i].value = value;
394 tf->entries[i].time_up = now;
399 check_update_times(tf, value, now);
400 return (tf->entries[0].value);
404 apply_filter_min_small(struct time_filter_small *tf,
405 uint32_t value, uint32_t now)
409 if (value <= tf->entries[0].value) {
411 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
412 tf->entries[i].value = value;
413 tf->entries[i].time_up = now;
415 return (tf->entries[0].value);
417 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
418 if (value <= tf->entries[j].value) {
419 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
420 tf->entries[i].value = value;
421 tf->entries[i].time_up = now;
426 check_update_times_small(tf, value, now);
427 return (tf->entries[0].value);
431 apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now)
435 if (value >= tf->entries[0].value) {
437 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
438 tf->entries[i].value = value;
439 tf->entries[i].time_up = now;
441 return (tf->entries[0].value);
443 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
444 if (value >= tf->entries[j].value) {
445 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
446 tf->entries[i].value = value;
447 tf->entries[i].time_up = now;
452 check_update_times(tf, value, now);
453 return (tf->entries[0].value);
458 apply_filter_max_small(struct time_filter_small *tf,
459 uint32_t value, uint32_t now)
463 if (value >= tf->entries[0].value) {
465 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
466 tf->entries[i].value = value;
467 tf->entries[i].time_up = now;
469 return (tf->entries[0].value);
471 for (j=1; j<NUM_FILTER_ENTRIES; j++) {
472 if (value >= tf->entries[j].value) {
473 for(i=j; i<NUM_FILTER_ENTRIES; i++) {
474 tf->entries[i].value = value;
475 tf->entries[i].time_up = now;
480 check_update_times_small(tf, value, now);
481 return (tf->entries[0].value);