Changeset View
Changeset View
Standalone View
Standalone View
head/sys/kern/subr_filter.c
Property | Old Value | New Value |
---|---|---|
svn:eol-style | null | native \ No newline at end of property |
svn:keywords | null | FreeBSD=%H \ No newline at end of property |
svn:mime-type | null | text/plain \ No newline at end of property |
/*- | |||||
* Copyright (c) 2016-2019 Netflix, Inc. | |||||
* All rights reserved. | |||||
* | |||||
* Redistribution and use in source and binary forms, with or without | |||||
* modification, are permitted provided that the following conditions | |||||
* are met: | |||||
* 1. Redistributions of source code must retain the above copyright | |||||
* notice, this list of conditions and the following disclaimer. | |||||
* 2. Redistributions in binary form must reproduce the above copyright | |||||
* notice, this list of conditions and the following disclaimer in the | |||||
* documentation and/or other materials provided with the distribution. | |||||
* | |||||
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | |||||
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |||||
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |||||
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |||||
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |||||
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |||||
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |||||
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |||||
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |||||
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |||||
* SUCH DAMAGE. | |||||
*/ | |||||
/* | |||||
* Author: Randall Stewart <rrs@netflix.com> | |||||
*/ | |||||
#include <sys/cdefs.h> | |||||
__FBSDID("$FreeBSD$"); | |||||
#include <sys/types.h> | |||||
#include <sys/time.h> | |||||
#include <sys/errno.h> | |||||
#include <sys/tim_filter.h> | |||||
void | |||||
reset_time(struct time_filter *tf, uint32_t time_len) | |||||
{ | |||||
tf->cur_time_limit = time_len; | |||||
} | |||||
void | |||||
reset_time_small(struct time_filter_small *tf, uint32_t time_len) | |||||
{ | |||||
tf->cur_time_limit = time_len; | |||||
} | |||||
/* | |||||
* A time filter can be a filter for MIN or MAX. | |||||
* You call setup_time_filter() with the pointer to | |||||
* the filter structure, the type (FILTER_TYPE_MIN/MAX) and | |||||
* the time length. You can optionally reset the time length | |||||
* later with reset_time(). | |||||
* | |||||
* You generally call apply_filter_xxx() to apply the new value | |||||
* to the filter. You also provide a time (now). The filter will | |||||
* age out entries based on the time now and your time limit | |||||
* so that you are always maintaining the min or max in that | |||||
* window of time. Time is a relative thing, it might be ticks | |||||
* in milliseconds, it might be round trip times, its really | |||||
* up to you to decide what it is. | |||||
* | |||||
* To access the current flitered value you can use the macro | |||||
* get_filter_value() which returns the correct entry that | |||||
* has the "current" value in the filter. | |||||
* | |||||
* One thing that used to be here is a single apply_filter(). But | |||||
* this meant that we then had to store the type of filter in | |||||
* the time_filter structure. In order to keep it at a cache | |||||
* line size I split it to two functions. | |||||
* | |||||
*/ | |||||
int | |||||
setup_time_filter(struct time_filter *tf, int fil_type, uint32_t time_len) | |||||
{ | |||||
uint64_t set_val; | |||||
int i; | |||||
/* | |||||
* You must specify either a MIN or MAX filter, | |||||
* though its up to the user to use the correct | |||||
* apply. | |||||
*/ | |||||
if ((fil_type != FILTER_TYPE_MIN) && | |||||
(fil_type != FILTER_TYPE_MAX)) | |||||
return(EINVAL); | |||||
if (time_len < NUM_FILTER_ENTRIES) | |||||
return(EINVAL); | |||||
if (fil_type == FILTER_TYPE_MIN) | |||||
set_val = 0xffffffffffffffff; | |||||
else | |||||
set_val = 0; | |||||
for(i=0; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = set_val; | |||||
tf->entries[i].time_up = 0; | |||||
} | |||||
tf->cur_time_limit = time_len; | |||||
return(0); | |||||
} | |||||
int | |||||
setup_time_filter_small(struct time_filter_small *tf, int fil_type, uint32_t time_len) | |||||
{ | |||||
uint32_t set_val; | |||||
int i; | |||||
/* | |||||
* You must specify either a MIN or MAX filter, | |||||
* though its up to the user to use the correct | |||||
* apply. | |||||
*/ | |||||
if ((fil_type != FILTER_TYPE_MIN) && | |||||
(fil_type != FILTER_TYPE_MAX)) | |||||
return(EINVAL); | |||||
if (time_len < NUM_FILTER_ENTRIES) | |||||
return(EINVAL); | |||||
if (fil_type == FILTER_TYPE_MIN) | |||||
set_val = 0xffffffff; | |||||
else | |||||
set_val = 0; | |||||
for(i=0; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = set_val; | |||||
tf->entries[i].time_up = 0; | |||||
} | |||||
tf->cur_time_limit = time_len; | |||||
return(0); | |||||
} | |||||
static void | |||||
check_update_times(struct time_filter *tf, uint64_t value, uint32_t now) | |||||
{ | |||||
int i, j, fnd; | |||||
uint32_t tim; | |||||
uint32_t time_limit; | |||||
for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) { | |||||
tim = now - tf->entries[i].time_up; | |||||
time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES; | |||||
if (tim >= time_limit) { | |||||
fnd = 0; | |||||
for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) { | |||||
if (tf->entries[i].time_up < tf->entries[j].time_up) { | |||||
tf->entries[i].value = tf->entries[j].value; | |||||
tf->entries[i].time_up = tf->entries[j].time_up; | |||||
fnd = 1; | |||||
break; | |||||
} | |||||
} | |||||
if (fnd == 0) { | |||||
/* Nothing but the same old entry */ | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
} | |||||
} | |||||
i = NUM_FILTER_ENTRIES-1; | |||||
tim = now - tf->entries[i].time_up; | |||||
time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES; | |||||
if (tim >= time_limit) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
} | |||||
static void | |||||
check_update_times_small(struct time_filter_small *tf, uint32_t value, uint32_t now) | |||||
{ | |||||
int i, j, fnd; | |||||
uint32_t tim; | |||||
uint32_t time_limit; | |||||
for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) { | |||||
tim = now - tf->entries[i].time_up; | |||||
time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES; | |||||
if (tim >= time_limit) { | |||||
fnd = 0; | |||||
for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) { | |||||
if (tf->entries[i].time_up < tf->entries[j].time_up) { | |||||
tf->entries[i].value = tf->entries[j].value; | |||||
tf->entries[i].time_up = tf->entries[j].time_up; | |||||
fnd = 1; | |||||
break; | |||||
} | |||||
} | |||||
if (fnd == 0) { | |||||
/* Nothing but the same old entry */ | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
} | |||||
} | |||||
i = NUM_FILTER_ENTRIES-1; | |||||
tim = now - tf->entries[i].time_up; | |||||
time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES; | |||||
if (tim >= time_limit) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
} | |||||
void | |||||
filter_reduce_by(struct time_filter *tf, uint64_t reduce_by, uint32_t now) | |||||
{ | |||||
int i; | |||||
/* | |||||
* Reduce our filter main by reduce_by and | |||||
* update its time. Then walk other's and | |||||
* make them the new value too. | |||||
*/ | |||||
if (reduce_by < tf->entries[0].value) | |||||
tf->entries[0].value -= reduce_by; | |||||
else | |||||
tf->entries[0].value = 0; | |||||
tf->entries[0].time_up = now; | |||||
for(i=1; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = tf->entries[0].value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
} | |||||
void | |||||
filter_reduce_by_small(struct time_filter_small *tf, uint32_t reduce_by, uint32_t now) | |||||
{ | |||||
int i; | |||||
/* | |||||
* Reduce our filter main by reduce_by and | |||||
* update its time. Then walk other's and | |||||
* make them the new value too. | |||||
*/ | |||||
if (reduce_by < tf->entries[0].value) | |||||
tf->entries[0].value -= reduce_by; | |||||
else | |||||
tf->entries[0].value = 0; | |||||
tf->entries[0].time_up = now; | |||||
for(i=1; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = tf->entries[0].value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
} | |||||
void | |||||
filter_increase_by(struct time_filter *tf, uint64_t incr_by, uint32_t now) | |||||
{ | |||||
int i; | |||||
/* | |||||
* Increase our filter main by incr_by and | |||||
* update its time. Then walk other's and | |||||
* make them the new value too. | |||||
*/ | |||||
tf->entries[0].value += incr_by; | |||||
tf->entries[0].time_up = now; | |||||
for(i=1; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = tf->entries[0].value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
} | |||||
void | |||||
filter_increase_by_small(struct time_filter_small *tf, uint32_t incr_by, uint32_t now) | |||||
{ | |||||
int i; | |||||
/* | |||||
* Increase our filter main by incr_by and | |||||
* update its time. Then walk other's and | |||||
* make them the new value too. | |||||
*/ | |||||
tf->entries[0].value += incr_by; | |||||
tf->entries[0].time_up = now; | |||||
for(i=1; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = tf->entries[0].value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
} | |||||
void | |||||
forward_filter_clock(struct time_filter *tf, uint32_t ticks_forward) | |||||
{ | |||||
/* | |||||
* Bring forward all time values by N ticks. This | |||||
* postpones expiring slots by that amount. | |||||
*/ | |||||
int i; | |||||
for(i=0; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].time_up += ticks_forward; | |||||
} | |||||
} | |||||
void | |||||
forward_filter_clock_small(struct time_filter_small *tf, uint32_t ticks_forward) | |||||
{ | |||||
/* | |||||
* Bring forward all time values by N ticks. This | |||||
* postpones expiring slots by that amount. | |||||
*/ | |||||
int i; | |||||
for(i=0; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].time_up += ticks_forward; | |||||
} | |||||
} | |||||
void | |||||
tick_filter_clock(struct time_filter *tf, uint32_t now) | |||||
{ | |||||
int i; | |||||
uint32_t tim, time_limit; | |||||
/* | |||||
* We start at two positions back. This | |||||
* is because the oldest worst value is | |||||
* preserved always, i.e. it can't expire | |||||
* due to clock ticking with no updated value. | |||||
* | |||||
* The other choice would be to fill it in with | |||||
* zero, but I don't like that option since | |||||
* some measurement is better than none (even | |||||
* if its your oldest measurment). | |||||
*/ | |||||
for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) { | |||||
tim = now - tf->entries[i].time_up; | |||||
time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES; | |||||
if (tim >= time_limit) { | |||||
/* | |||||
* This entry is expired, pull down | |||||
* the next one up. | |||||
*/ | |||||
tf->entries[i].value = tf->entries[(i+1)].value; | |||||
tf->entries[i].time_up = tf->entries[(i+1)].time_up; | |||||
} | |||||
} | |||||
} | |||||
void | |||||
tick_filter_clock_small(struct time_filter_small *tf, uint32_t now) | |||||
{ | |||||
int i; | |||||
uint32_t tim, time_limit; | |||||
/* | |||||
* We start at two positions back. This | |||||
* is because the oldest worst value is | |||||
* preserved always, i.e. it can't expire | |||||
* due to clock ticking with no updated value. | |||||
* | |||||
* The other choice would be to fill it in with | |||||
* zero, but I don't like that option since | |||||
* some measurement is better than none (even | |||||
* if its your oldest measurment). | |||||
*/ | |||||
for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) { | |||||
tim = now - tf->entries[i].time_up; | |||||
time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES; | |||||
if (tim >= time_limit) { | |||||
/* | |||||
* This entry is expired, pull down | |||||
* the next one up. | |||||
*/ | |||||
tf->entries[i].value = tf->entries[(i+1)].value; | |||||
tf->entries[i].time_up = tf->entries[(i+1)].time_up; | |||||
} | |||||
} | |||||
} | |||||
uint32_t | |||||
apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now) | |||||
{ | |||||
int i, j; | |||||
if (value <= tf->entries[0].value) { | |||||
/* Zap them all */ | |||||
for(i=0; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
return (tf->entries[0].value); | |||||
} | |||||
for (j=1; j<NUM_FILTER_ENTRIES; j++) { | |||||
if (value <= tf->entries[j].value) { | |||||
for(i=j; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
break; | |||||
} | |||||
} | |||||
check_update_times(tf, value, now); | |||||
return (tf->entries[0].value); | |||||
} | |||||
uint32_t | |||||
apply_filter_min_small(struct time_filter_small *tf, | |||||
uint32_t value, uint32_t now) | |||||
{ | |||||
int i, j; | |||||
if (value <= tf->entries[0].value) { | |||||
/* Zap them all */ | |||||
for(i=0; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
return (tf->entries[0].value); | |||||
} | |||||
for (j=1; j<NUM_FILTER_ENTRIES; j++) { | |||||
if (value <= tf->entries[j].value) { | |||||
for(i=j; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
break; | |||||
} | |||||
} | |||||
check_update_times_small(tf, value, now); | |||||
return (tf->entries[0].value); | |||||
} | |||||
uint32_t | |||||
apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now) | |||||
{ | |||||
int i, j; | |||||
if (value >= tf->entries[0].value) { | |||||
/* Zap them all */ | |||||
for(i=0; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
return (tf->entries[0].value); | |||||
} | |||||
for (j=1; j<NUM_FILTER_ENTRIES; j++) { | |||||
if (value >= tf->entries[j].value) { | |||||
for(i=j; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
break; | |||||
} | |||||
} | |||||
check_update_times(tf, value, now); | |||||
return (tf->entries[0].value); | |||||
} | |||||
uint32_t | |||||
apply_filter_max_small(struct time_filter_small *tf, | |||||
uint32_t value, uint32_t now) | |||||
{ | |||||
int i, j; | |||||
if (value >= tf->entries[0].value) { | |||||
/* Zap them all */ | |||||
for(i=0; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
return (tf->entries[0].value); | |||||
} | |||||
for (j=1; j<NUM_FILTER_ENTRIES; j++) { | |||||
if (value >= tf->entries[j].value) { | |||||
for(i=j; i<NUM_FILTER_ENTRIES; i++) { | |||||
tf->entries[i].value = value; | |||||
tf->entries[i].time_up = now; | |||||
} | |||||
break; | |||||
} | |||||
} | |||||
check_update_times_small(tf, value, now); | |||||
return (tf->entries[0].value); | |||||
} |