subr_filter.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*-
    2  * Copyright (c) 2016-2019 Netflix, Inc.
    3  * All rights reserved.
    4  *
    5  * Redistribution and use in source and binary forms, with or without
    6  * modification, are permitted provided that the following conditions
    7  * are met:
    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.
   13  *
   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
   24  * SUCH DAMAGE.
   25  */
   26 
   27 /*
   28  * Author: Randall Stewart <rrs@netflix.com>
   29  */
   30 #include <sys/cdefs.h>
   31 __FBSDID("$FreeBSD$");
   32 #include <sys/types.h>
   33 #include <sys/time.h>
   34 #include <sys/errno.h>
   35 #include <sys/tim_filter.h>
   36 
   37 void
   38 reset_time(struct time_filter *tf, uint32_t time_len)
   39 {
   40         tf->cur_time_limit = time_len;
   41 }
   42 
   43 void
   44 reset_time_small(struct time_filter_small *tf, uint32_t time_len)
   45 {
   46         tf->cur_time_limit = time_len;
   47 }
   48 
   49 /*
   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().
   55  *
   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.
   63  *
   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.
   67  *
   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. 
   72  *
   73  */
   74 int
   75 setup_time_filter(struct time_filter *tf, int fil_type, uint32_t time_len)
   76 {
   77         uint64_t set_val;
   78         int i;
   79 
   80         /* 
   81          * You must specify either a MIN or MAX filter,
   82          * though its up to the user to use the correct
   83          * apply.
   84          */
   85         if ((fil_type != FILTER_TYPE_MIN) &&
   86             (fil_type != FILTER_TYPE_MAX))
   87                 return(EINVAL);
   88 
   89         if (time_len < NUM_FILTER_ENTRIES)
   90                 return(EINVAL);
   91                        
   92         if (fil_type == FILTER_TYPE_MIN)
   93                 set_val = 0xffffffffffffffff;
   94         else
   95                 set_val = 0;
   96 
   97         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
   98                 tf->entries[i].value = set_val;
   99                 tf->entries[i].time_up = 0;
  100         }
  101         tf->cur_time_limit = time_len;
  102         return(0);
  103 }
  104 
  105 int
  106 setup_time_filter_small(struct time_filter_small *tf, int fil_type, uint32_t time_len)
  107 {
  108         uint32_t set_val;
  109         int i;
  110 
  111         /* 
  112          * You must specify either a MIN or MAX filter,
  113          * though its up to the user to use the correct
  114          * apply.
  115          */
  116         if ((fil_type != FILTER_TYPE_MIN) &&
  117             (fil_type != FILTER_TYPE_MAX))
  118                 return(EINVAL);
  119 
  120         if (time_len < NUM_FILTER_ENTRIES)
  121                 return(EINVAL);
  122                        
  123         if (fil_type == FILTER_TYPE_MIN)
  124                 set_val = 0xffffffff;
  125         else
  126                 set_val = 0;
  127 
  128         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
  129                 tf->entries[i].value = set_val;
  130                 tf->entries[i].time_up = 0;
  131         }
  132         tf->cur_time_limit = time_len;
  133         return(0);
  134 }
  135 
  136 static void
  137 check_update_times(struct time_filter *tf, uint64_t value, uint32_t now)
  138 {
  139         int i, j, fnd;
  140         uint32_t tim;
  141         uint32_t time_limit;
  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) {
  146                         fnd = 0;
  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;
  151                                         fnd = 1;
  152                                         break;
  153                                 }
  154                         }
  155                         if (fnd == 0) {
  156                                 /* Nothing but the same old entry */
  157                                 tf->entries[i].value = value;
  158                                 tf->entries[i].time_up = now;
  159                         }
  160                 }
  161         }
  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;
  168         }
  169 }
  170 
  171 static void
  172 check_update_times_small(struct time_filter_small *tf, uint32_t value, uint32_t now)
  173 {
  174         int i, j, fnd;
  175         uint32_t tim;
  176         uint32_t time_limit;
  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) {
  181                         fnd = 0;
  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;
  186                                         fnd = 1;
  187                                         break;
  188                                 }
  189                         }
  190                         if (fnd == 0) {
  191                                 /* Nothing but the same old entry */
  192                                 tf->entries[i].value = value;
  193                                 tf->entries[i].time_up = now;
  194                         }
  195                 }
  196         }
  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;
  203         }
  204 }
  205 
  206 void
  207 filter_reduce_by(struct time_filter *tf, uint64_t reduce_by, uint32_t now)
  208 {
  209         int i;
  210         /* 
  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.
  214          */
  215         if (reduce_by < tf->entries[0].value)
  216                 tf->entries[0].value -= reduce_by;
  217         else
  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;
  223         }
  224 }
  225 
  226 void
  227 filter_reduce_by_small(struct time_filter_small *tf, uint32_t reduce_by, uint32_t now)
  228 {
  229         int i;
  230         /* 
  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.
  234          */
  235         if (reduce_by < tf->entries[0].value)
  236                 tf->entries[0].value -= reduce_by;
  237         else
  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;
  243         }
  244 }
  245 
  246 void
  247 filter_increase_by(struct time_filter *tf, uint64_t incr_by, uint32_t now)
  248 {
  249         int i;
  250         /* 
  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.
  254          */
  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;
  260         }
  261 }
  262 
  263 void
  264 filter_increase_by_small(struct time_filter_small *tf, uint32_t incr_by, uint32_t now)
  265 {
  266         int i;
  267         /* 
  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.
  271          */
  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;
  277         }
  278 }
  279 
  280 void
  281 forward_filter_clock(struct time_filter *tf, uint32_t ticks_forward)
  282 {
  283         /*
  284          * Bring forward all time values by N ticks. This
  285          * postpones expiring slots by that amount.
  286          */
  287         int i;
  288 
  289         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
  290                 tf->entries[i].time_up += ticks_forward;
  291         }
  292 }
  293 
  294 void
  295 forward_filter_clock_small(struct time_filter_small *tf, uint32_t ticks_forward)
  296 {
  297         /*
  298          * Bring forward all time values by N ticks. This
  299          * postpones expiring slots by that amount.
  300          */
  301         int i;
  302 
  303         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
  304                 tf->entries[i].time_up += ticks_forward;
  305         }
  306 }
  307 
  308 void
  309 tick_filter_clock(struct time_filter *tf, uint32_t now)
  310 {
  311         int i;
  312         uint32_t tim, time_limit;
  313 
  314         /*
  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.
  319          *
  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 measurement).
  324          */
  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) {
  329                         /*
  330                          * This entry is expired, pull down
  331                          * the next one up.
  332                          */
  333                         tf->entries[i].value = tf->entries[(i+1)].value;
  334                         tf->entries[i].time_up = tf->entries[(i+1)].time_up;
  335                 }
  336         }
  337 }
  338 
  339 void
  340 tick_filter_clock_small(struct time_filter_small *tf, uint32_t now)
  341 {
  342         int i;
  343         uint32_t tim, time_limit;
  344 
  345         /*
  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.
  350          *
  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 measurement).
  355          */
  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) {
  360                         /*
  361                          * This entry is expired, pull down
  362                          * the next one up.
  363                          */
  364                         tf->entries[i].value = tf->entries[(i+1)].value;
  365                         tf->entries[i].time_up = tf->entries[(i+1)].time_up;
  366                 }
  367         }
  368 }
  369 
  370 uint32_t
  371 apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now)
  372 {
  373         int i, j;
  374 
  375         if (value <= tf->entries[0].value) {
  376                 /* Zap them all */
  377                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
  378                         tf->entries[i].value = value;
  379                         tf->entries[i].time_up = now;
  380                 }
  381                 return (tf->entries[0].value);
  382         }
  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;
  388                         }
  389                         break;
  390                 }
  391         }
  392         check_update_times(tf, value, now);
  393         return (tf->entries[0].value);
  394 }
  395 
  396 uint32_t
  397 apply_filter_min_small(struct time_filter_small *tf,
  398                        uint32_t value, uint32_t now)
  399 {
  400         int i, j;
  401 
  402         if (value <= tf->entries[0].value) {
  403                 /* Zap them all */
  404                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
  405                         tf->entries[i].value = value;
  406                         tf->entries[i].time_up = now;
  407                 }
  408                 return (tf->entries[0].value);
  409         }
  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;
  415                         }
  416                         break;
  417                 }
  418         }
  419         check_update_times_small(tf, value, now);
  420         return (tf->entries[0].value);
  421 }
  422 
  423 uint32_t
  424 apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now)
  425 {
  426         int i, j;
  427 
  428         if (value >= tf->entries[0].value) {
  429                 /* Zap them all */
  430                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
  431                         tf->entries[i].value = value;
  432                         tf->entries[i].time_up = now;
  433                 }
  434                 return (tf->entries[0].value);
  435         }
  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;
  441                         }
  442                         break;
  443                 }
  444         }
  445         check_update_times(tf, value, now);
  446         return (tf->entries[0].value);
  447 }
  448 
  449 uint32_t
  450 apply_filter_max_small(struct time_filter_small *tf,
  451                        uint32_t value, uint32_t now)
  452 {
  453         int i, j;
  454 
  455         if (value >= tf->entries[0].value) {
  456                 /* Zap them all */
  457                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
  458                         tf->entries[i].value = value;
  459                         tf->entries[i].time_up = now;
  460                 }
  461                 return (tf->entries[0].value);
  462         }
  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;
  468                         }
  469                         break;
  470                 }
  471         }
  472         check_update_times_small(tf, value, now);
  473         return (tf->entries[0].value);
  474 }
Cache object: 6cc21a3f397ca44d9f221a1838ab0dc4
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/kern/subr_filter.c

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_filter.c
