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
 137 static void
 138 check_update_times(struct time_filter *tf, uint64_t value, uint32_t now)
 139 {
 140         int i, j, fnd;
 141         uint32_t tim;
 142         uint32_t time_limit;
 143         for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
 144                 tim = now - tf->entries[i].time_up;
 145                 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 146                 if (tim >= time_limit) {
 147                         fnd = 0;
 148                         for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
 149                                 if (tf->entries[i].time_up < tf->entries[j].time_up) {
 150                                         tf->entries[i].value = tf->entries[j].value;
 151                                         tf->entries[i].time_up = tf->entries[j].time_up;
 152                                         fnd = 1;
 153                                         break;
 154                                 }
 155                         }
 156                         if (fnd == 0) {
 157                                 /* Nothing but the same old entry */
 158                                 tf->entries[i].value = value;
 159                                 tf->entries[i].time_up = now;
 160                         }
 161                 }
 162         }
 163         i = NUM_FILTER_ENTRIES-1;
 164         tim = now - tf->entries[i].time_up;
 165         time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 166         if (tim >= time_limit) {
 167                 tf->entries[i].value = value;
 168                 tf->entries[i].time_up = now;
 169         }
 170 }
 171
 172 static void
 173 check_update_times_small(struct time_filter_small *tf, uint32_t value, uint32_t now)
 174 {
 175         int i, j, fnd;
 176         uint32_t tim;
 177         uint32_t time_limit;
 178         for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
 179                 tim = now - tf->entries[i].time_up;
 180                 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 181                 if (tim >= time_limit) {
 182                         fnd = 0;
 183                         for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
 184                                 if (tf->entries[i].time_up < tf->entries[j].time_up) {
 185                                         tf->entries[i].value = tf->entries[j].value;
 186                                         tf->entries[i].time_up = tf->entries[j].time_up;
 187                                         fnd = 1;
 188                                         break;
 189                                 }
 190                         }
 191                         if (fnd == 0) {
 192                                 /* Nothing but the same old entry */
 193                                 tf->entries[i].value = value;
 194                                 tf->entries[i].time_up = now;
 195                         }
 196                 }
 197         }
 198         i = NUM_FILTER_ENTRIES-1;
 199         tim = now - tf->entries[i].time_up;
 200         time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 201         if (tim >= time_limit) {
 202                 tf->entries[i].value = value;
 203                 tf->entries[i].time_up = now;
 204         }
 205 }
 206
 207
 208
 209 void
 210 filter_reduce_by(struct time_filter *tf, uint64_t reduce_by, uint32_t now)
 211 {
 212         int i;
 213         /*
 214          * Reduce our filter main by reduce_by and
 215          * update its time. Then walk other's and
 216          * make them the new value too.
 217          */
 218         if (reduce_by < tf->entries[0].value)
 219                 tf->entries[0].value -= reduce_by;
 220         else
 221                 tf->entries[0].value = 0;
 222         tf->entries[0].time_up = now;
 223         for(i=1; i<NUM_FILTER_ENTRIES; i++) {
 224                 tf->entries[i].value = tf->entries[0].value;
 225                 tf->entries[i].time_up = now;
 226         }
 227 }
 228
 229 void
 230 filter_reduce_by_small(struct time_filter_small *tf, uint32_t reduce_by, uint32_t now)
 231 {
 232         int i;
 233         /*
 234          * Reduce our filter main by reduce_by and
 235          * update its time. Then walk other's and
 236          * make them the new value too.
 237          */
 238         if (reduce_by < tf->entries[0].value)
 239                 tf->entries[0].value -= reduce_by;
 240         else
 241                 tf->entries[0].value = 0;
 242         tf->entries[0].time_up = now;
 243         for(i=1; i<NUM_FILTER_ENTRIES; i++) {
 244                 tf->entries[i].value = tf->entries[0].value;
 245                 tf->entries[i].time_up = now;
 246         }
 247 }
 248
 249 void
 250 filter_increase_by(struct time_filter *tf, uint64_t incr_by, uint32_t now)
 251 {
 252         int i;
 253         /*
 254          * Increase our filter main by incr_by and
 255          * update its time. Then walk other's and
 256          * make them the new value too.
 257          */
 258         tf->entries[0].value += incr_by;
 259         tf->entries[0].time_up = now;
 260         for(i=1; i<NUM_FILTER_ENTRIES; i++) {
 261                 tf->entries[i].value = tf->entries[0].value;
 262                 tf->entries[i].time_up = now;
 263         }
 264 }
 265
 266 void
 267 filter_increase_by_small(struct time_filter_small *tf, uint32_t incr_by, uint32_t now)
 268 {
 269         int i;
 270         /*
 271          * Increase our filter main by incr_by and
 272          * update its time. Then walk other's and
 273          * make them the new value too.
 274          */
 275         tf->entries[0].value += incr_by;
 276         tf->entries[0].time_up = now;
 277         for(i=1; i<NUM_FILTER_ENTRIES; i++) {
 278                 tf->entries[i].value = tf->entries[0].value;
 279                 tf->entries[i].time_up = now;
 280         }
 281 }
 282
 283 void
 284 forward_filter_clock(struct time_filter *tf, uint32_t ticks_forward)
 285 {
 286         /*
 287          * Bring forward all time values by N ticks. This
 288          * postpones expiring slots by that amount.
 289          */
 290         int i;
 291
 292         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 293                 tf->entries[i].time_up += ticks_forward;
 294         }
 295 }
 296
 297
 298 void
 299 forward_filter_clock_small(struct time_filter_small *tf, uint32_t ticks_forward)
 300 {
 301         /*
 302          * Bring forward all time values by N ticks. This
 303          * postpones expiring slots by that amount.
 304          */
 305         int i;
 306
 307         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 308                 tf->entries[i].time_up += ticks_forward;
 309         }
 310 }
 311
 312
 313 void
 314 tick_filter_clock(struct time_filter *tf, uint32_t now)
 315 {
 316         int i;
 317         uint32_t tim, time_limit;
 318
 319         /*
 320          * We start at two positions back. This
 321          * is because the oldest worst value is
 322          * preserved always, i.e. it can't expire
 323          * due to clock ticking with no updated value.
 324          *
 325          * The other choice would be to fill it in with
 326          * zero, but I don't like that option since
 327          * some measurement is better than none (even
 328          * if its your oldest measurment).
 329          */
 330         for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
 331                 tim = now - tf->entries[i].time_up;
 332                 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 333                 if (tim >= time_limit) {
 334                         /*
 335                          * This entry is expired, pull down
 336                          * the next one up.
 337                          */
 338                         tf->entries[i].value = tf->entries[(i+1)].value;
 339                         tf->entries[i].time_up = tf->entries[(i+1)].time_up;
 340                 }
 341
 342         }
 343 }
 344
 345 void
 346 tick_filter_clock_small(struct time_filter_small *tf, uint32_t now)
 347 {
 348         int i;
 349         uint32_t tim, time_limit;
 350
 351         /*
 352          * We start at two positions back. This
 353          * is because the oldest worst value is
 354          * preserved always, i.e. it can't expire
 355          * due to clock ticking with no updated value.
 356          *
 357          * The other choice would be to fill it in with
 358          * zero, but I don't like that option since
 359          * some measurement is better than none (even
 360          * if its your oldest measurment).
 361          */
 362         for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
 363                 tim = now - tf->entries[i].time_up;
 364                 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 365                 if (tim >= time_limit) {
 366                         /*
 367                          * This entry is expired, pull down
 368                          * the next one up.
 369                          */
 370                         tf->entries[i].value = tf->entries[(i+1)].value;
 371                         tf->entries[i].time_up = tf->entries[(i+1)].time_up;
 372                 }
 373
 374         }
 375 }
 376
 377 uint32_t
 378 apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now)
 379 {
 380         int i, j;
 381
 382         if (value <= tf->entries[0].value) {
 383                 /* Zap them all */
 384                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 385                         tf->entries[i].value = value;
 386                         tf->entries[i].time_up = now;
 387                 }
 388                 return (tf->entries[0].value);
 389         }
 390         for (j=1; j<NUM_FILTER_ENTRIES; j++) {
 391                 if (value <= tf->entries[j].value) {
 392                         for(i=j; i<NUM_FILTER_ENTRIES; i++) {
 393                                 tf->entries[i].value = value;
 394                                 tf->entries[i].time_up = now;
 395                         }
 396                         break;
 397                 }
 398         }
 399         check_update_times(tf, value, now);
 400         return (tf->entries[0].value);
 401 }
 402
 403 uint32_t
 404 apply_filter_min_small(struct time_filter_small *tf,
 405                        uint32_t value, uint32_t now)
 406 {
 407         int i, j;
 408
 409         if (value <= tf->entries[0].value) {
 410                 /* Zap them all */
 411                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 412                         tf->entries[i].value = value;
 413                         tf->entries[i].time_up = now;
 414                 }
 415                 return (tf->entries[0].value);
 416         }
 417         for (j=1; j<NUM_FILTER_ENTRIES; j++) {
 418                 if (value <= tf->entries[j].value) {
 419                         for(i=j; i<NUM_FILTER_ENTRIES; i++) {
 420                                 tf->entries[i].value = value;
 421                                 tf->entries[i].time_up = now;
 422                         }
 423                         break;
 424                 }
 425         }
 426         check_update_times_small(tf, value, now);
 427         return (tf->entries[0].value);
 428 }
 429
 430 uint32_t
 431 apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now)
 432 {
 433         int i, j;
 434
 435         if (value >= tf->entries[0].value) {
 436                 /* Zap them all */
 437                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 438                         tf->entries[i].value = value;
 439                         tf->entries[i].time_up = now;
 440                 }
 441                 return (tf->entries[0].value);
 442         }
 443         for (j=1; j<NUM_FILTER_ENTRIES; j++) {
 444                 if (value >= tf->entries[j].value) {
 445                         for(i=j; i<NUM_FILTER_ENTRIES; i++) {
 446                                 tf->entries[i].value = value;
 447                                 tf->entries[i].time_up = now;
 448                         }
 449                         break;
 450                 }
 451         }
 452         check_update_times(tf, value, now);
 453         return (tf->entries[0].value);
 454 }
 455
 456
 457 uint32_t
 458 apply_filter_max_small(struct time_filter_small *tf,
 459                        uint32_t value, uint32_t now)
 460 {
 461         int i, j;
 462
 463         if (value >= tf->entries[0].value) {
 464                 /* Zap them all */
 465                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 466                         tf->entries[i].value = value;
 467                         tf->entries[i].time_up = now;
 468                 }
 469                 return (tf->entries[0].value);
 470         }
 471         for (j=1; j<NUM_FILTER_ENTRIES; j++) {
 472                 if (value >= tf->entries[j].value) {
 473                         for(i=j; i<NUM_FILTER_ENTRIES; i++) {
 474                                 tf->entries[i].value = value;
 475                                 tf->entries[i].time_up = now;
 476                         }
 477                         break;
 478                 }
 479         }
 480         check_update_times_small(tf, value, now);
 481         return (tf->entries[0].value);
 482 }