sys/kern/subr_filter.c

   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 measurment).
 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 measurment).
 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 }