subr_filter.c

Go to the documentation of this file.

/*-
 * 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);
}