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 #include <sys/types.h>
33 #include <sys/errno.h>
34 #include <sys/tim_filter.h>
37 reset_time(struct time_filter *tf, uint32_t time_len)
39 tf->cur_time_limit = time_len;
43 reset_time_small(struct time_filter_small *tf, uint32_t time_len)
45 tf->cur_time_limit = time_len;
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().
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.
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.
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.
74 setup_time_filter(struct time_filter *tf, int fil_type, uint32_t time_len)
80 * You must specify either a MIN or MAX filter,
81 * though its up to the user to use the correct
84 if ((fil_type != FILTER_TYPE_MIN) &&
85 (fil_type != FILTER_TYPE_MAX))
88 if (time_len < NUM_FILTER_ENTRIES)
91 if (fil_type == FILTER_TYPE_MIN)
92 set_val = 0xffffffffffffffff;
96 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
97 tf->entries[i].value = set_val;
98 tf->entries[i].time_up = 0;
100 tf->cur_time_limit = time_len;
105 setup_time_filter_small(struct time_filter_small *tf, int fil_type, uint32_t time_len)
111 * You must specify either a MIN or MAX filter,
112 * though its up to the user to use the correct
115 if ((fil_type != FILTER_TYPE_MIN) &&
116 (fil_type != FILTER_TYPE_MAX))
119 if (time_len < NUM_FILTER_ENTRIES)
122 if (fil_type == FILTER_TYPE_MIN)
123 set_val = 0xffffffff;
127 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
128 tf->entries[i].value = set_val;
129 tf->entries[i].time_up = 0;
131 tf->cur_time_limit = time_len;
136 check_update_times(struct time_filter *tf, uint64_t value, uint32_t now)
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) {
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;
155 /* Nothing but the same old entry */
156 tf->entries[i].value = value;
157 tf->entries[i].time_up = now;
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;
171 check_update_times_small(struct time_filter_small *tf, uint32_t value, uint32_t now)
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) {
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;
190 /* Nothing but the same old entry */
191 tf->entries[i].value = value;
192 tf->entries[i].time_up = now;
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;
206 filter_reduce_by(struct time_filter *tf, uint64_t reduce_by, uint32_t now)
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.
214 if (reduce_by < tf->entries[0].value)
215 tf->entries[0].value -= reduce_by;
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;
226 filter_reduce_by_small(struct time_filter_small *tf, uint32_t reduce_by, uint32_t now)
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.
234 if (reduce_by < tf->entries[0].value)
235 tf->entries[0].value -= reduce_by;
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;
246 filter_increase_by(struct time_filter *tf, uint64_t incr_by, uint32_t now)
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.
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;
263 filter_increase_by_small(struct time_filter_small *tf, uint32_t incr_by, uint32_t now)
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.
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;
280 forward_filter_clock(struct time_filter *tf, uint32_t ticks_forward)
283 * Bring forward all time values by N ticks. This
284 * postpones expiring slots by that amount.
288 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
289 tf->entries[i].time_up += ticks_forward;
294 forward_filter_clock_small(struct time_filter_small *tf, uint32_t ticks_forward)
297 * Bring forward all time values by N ticks. This
298 * postpones expiring slots by that amount.
302 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
303 tf->entries[i].time_up += ticks_forward;
308 tick_filter_clock(struct time_filter *tf, uint32_t now)
311 uint32_t tim, time_limit;
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.
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).
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) {
329 * This entry is expired, pull down
332 tf->entries[i].value = tf->entries[(i+1)].value;
333 tf->entries[i].time_up = tf->entries[(i+1)].time_up;
339 tick_filter_clock_small(struct time_filter_small *tf, uint32_t now)
342 uint32_t tim, time_limit;
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.
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).
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) {
360 * This entry is expired, pull down
363 tf->entries[i].value = tf->entries[(i+1)].value;
364 tf->entries[i].time_up = tf->entries[(i+1)].time_up;
370 apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now)
374 if (value <= tf->entries[0].value) {
376 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
377 tf->entries[i].value = value;
378 tf->entries[i].time_up = now;
380 return (tf->entries[0].value);
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;
391 check_update_times(tf, value, now);
392 return (tf->entries[0].value);
396 apply_filter_min_small(struct time_filter_small *tf,
397 uint32_t value, uint32_t now)
401 if (value <= tf->entries[0].value) {
403 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
404 tf->entries[i].value = value;
405 tf->entries[i].time_up = now;
407 return (tf->entries[0].value);
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;
418 check_update_times_small(tf, value, now);
419 return (tf->entries[0].value);
423 apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now)
427 if (value >= tf->entries[0].value) {
429 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
430 tf->entries[i].value = value;
431 tf->entries[i].time_up = now;
433 return (tf->entries[0].value);
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;
444 check_update_times(tf, value, now);
445 return (tf->entries[0].value);
449 apply_filter_max_small(struct time_filter_small *tf,
450 uint32_t value, uint32_t now)
454 if (value >= tf->entries[0].value) {
456 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
457 tf->entries[i].value = value;
458 tf->entries[i].time_up = now;
460 return (tf->entries[0].value);
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;
471 check_update_times_small(tf, value, now);
472 return (tf->entries[0].value);