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
  31 #include <sys/types.h>
  32 #include <sys/time.h>
  33 #include <sys/errno.h>
  34 #include <sys/tim_filter.h>
  35
  36 void
  37 reset_time(struct time_filter *tf, uint32_t time_len)
  38 {
  39         tf->cur_time_limit = time_len;
  40 }
  41
  42 void
  43 reset_time_small(struct time_filter_small *tf, uint32_t time_len)
  44 {
  45         tf->cur_time_limit = time_len;
  46 }
  47
  48 /*
  49  * A time filter can be a filter for MIN or MAX.
  50  * You call setup_time_filter() with the pointer to
  51  * the filter structure, the type (FILTER_TYPE_MIN/MAX) and
  52  * the time length. You can optionally reset the time length
  53  * later with reset_time().
  54  *
  55  * You generally call apply_filter_xxx() to apply the new value
  56  * to the filter. You also provide a time (now). The filter will
  57  * age out entries based on the time now and your time limit
  58  * so that you are always maintaining the min or max in that
  59  * window of time. Time is a relative thing, it might be ticks
  60  * in milliseconds, it might be round trip times, its really
  61  * up to you to decide what it is.
  62  *
  63  * To access the current flitered value you can use the macro
  64  * get_filter_value() which returns the correct entry that
  65  * has the "current" value in the filter.
  66  *
  67  * One thing that used to be here is a single apply_filter(). But
  68  * this meant that we then had to store the type of filter in
  69  * the time_filter structure. In order to keep it at a cache
  70  * line size I split it to two functions.
  71  *
  72  */
  73 int
  74 setup_time_filter(struct time_filter *tf, int fil_type, uint32_t time_len)
  75 {
  76         uint64_t set_val;
  77         int i;
  78
  79         /*
  80          * You must specify either a MIN or MAX filter,
  81          * though its up to the user to use the correct
  82          * apply.
  83          */
  84         if ((fil_type != FILTER_TYPE_MIN) &&
  85             (fil_type != FILTER_TYPE_MAX))
  86                 return(EINVAL);
  87
  88         if (time_len < NUM_FILTER_ENTRIES)
  89                 return(EINVAL);
  90
  91         if (fil_type == FILTER_TYPE_MIN)
  92                 set_val = 0xffffffffffffffff;
  93         else
  94                 set_val = 0;
  95
  96         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
  97                 tf->entries[i].value = set_val;
  98                 tf->entries[i].time_up = 0;
  99         }
 100         tf->cur_time_limit = time_len;
 101         return(0);
 102 }
 103
 104 int
 105 setup_time_filter_small(struct time_filter_small *tf, int fil_type, uint32_t time_len)
 106 {
 107         uint32_t set_val;
 108         int i;
 109
 110         /*
 111          * You must specify either a MIN or MAX filter,
 112          * though its up to the user to use the correct
 113          * apply.
 114          */
 115         if ((fil_type != FILTER_TYPE_MIN) &&
 116             (fil_type != FILTER_TYPE_MAX))
 117                 return(EINVAL);
 118
 119         if (time_len < NUM_FILTER_ENTRIES)
 120                 return(EINVAL);
 121
 122         if (fil_type == FILTER_TYPE_MIN)
 123                 set_val = 0xffffffff;
 124         else
 125                 set_val = 0;
 126
 127         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 128                 tf->entries[i].value = set_val;
 129                 tf->entries[i].time_up = 0;
 130         }
 131         tf->cur_time_limit = time_len;
 132         return(0);
 133 }
 134
 135 static void
 136 check_update_times(struct time_filter *tf, uint64_t value, uint32_t now)
 137 {
 138         int i, j, fnd;
 139         uint32_t tim;
 140         uint32_t time_limit;
 141         for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
 142                 tim = now - tf->entries[i].time_up;
 143                 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 144                 if (tim >= time_limit) {
 145                         fnd = 0;
 146                         for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
 147                                 if (tf->entries[i].time_up < tf->entries[j].time_up) {
 148                                         tf->entries[i].value = tf->entries[j].value;
 149                                         tf->entries[i].time_up = tf->entries[j].time_up;
 150                                         fnd = 1;
 151                                         break;
 152                                 }
 153                         }
 154                         if (fnd == 0) {
 155                                 /* Nothing but the same old entry */
 156                                 tf->entries[i].value = value;
 157                                 tf->entries[i].time_up = now;
 158                         }
 159                 }
 160         }
 161         i = NUM_FILTER_ENTRIES-1;
 162         tim = now - tf->entries[i].time_up;
 163         time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 164         if (tim >= time_limit) {
 165                 tf->entries[i].value = value;
 166                 tf->entries[i].time_up = now;
 167         }
 168 }
 169
 170 static void
 171 check_update_times_small(struct time_filter_small *tf, uint32_t value, uint32_t now)
 172 {
 173         int i, j, fnd;
 174         uint32_t tim;
 175         uint32_t time_limit;
 176         for(i=0; i<(NUM_FILTER_ENTRIES-1); i++) {
 177                 tim = now - tf->entries[i].time_up;
 178                 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 179                 if (tim >= time_limit) {
 180                         fnd = 0;
 181                         for(j=(i+1); j<NUM_FILTER_ENTRIES; j++) {
 182                                 if (tf->entries[i].time_up < tf->entries[j].time_up) {
 183                                         tf->entries[i].value = tf->entries[j].value;
 184                                         tf->entries[i].time_up = tf->entries[j].time_up;
 185                                         fnd = 1;
 186                                         break;
 187                                 }
 188                         }
 189                         if (fnd == 0) {
 190                                 /* Nothing but the same old entry */
 191                                 tf->entries[i].value = value;
 192                                 tf->entries[i].time_up = now;
 193                         }
 194                 }
 195         }
 196         i = NUM_FILTER_ENTRIES-1;
 197         tim = now - tf->entries[i].time_up;
 198         time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 199         if (tim >= time_limit) {
 200                 tf->entries[i].value = value;
 201                 tf->entries[i].time_up = now;
 202         }
 203 }
 204
 205 void
 206 filter_reduce_by(struct time_filter *tf, uint64_t reduce_by, uint32_t now)
 207 {
 208         int i;
 209         /*
 210          * Reduce our filter main by reduce_by and
 211          * update its time. Then walk other's and
 212          * make them the new value too.
 213          */
 214         if (reduce_by < tf->entries[0].value)
 215                 tf->entries[0].value -= reduce_by;
 216         else
 217                 tf->entries[0].value = 0;
 218         tf->entries[0].time_up = now;
 219         for(i=1; i<NUM_FILTER_ENTRIES; i++) {
 220                 tf->entries[i].value = tf->entries[0].value;
 221                 tf->entries[i].time_up = now;
 222         }
 223 }
 224
 225 void
 226 filter_reduce_by_small(struct time_filter_small *tf, uint32_t reduce_by, uint32_t now)
 227 {
 228         int i;
 229         /*
 230          * Reduce our filter main by reduce_by and
 231          * update its time. Then walk other's and
 232          * make them the new value too.
 233          */
 234         if (reduce_by < tf->entries[0].value)
 235                 tf->entries[0].value -= reduce_by;
 236         else
 237                 tf->entries[0].value = 0;
 238         tf->entries[0].time_up = now;
 239         for(i=1; i<NUM_FILTER_ENTRIES; i++) {
 240                 tf->entries[i].value = tf->entries[0].value;
 241                 tf->entries[i].time_up = now;
 242         }
 243 }
 244
 245 void
 246 filter_increase_by(struct time_filter *tf, uint64_t incr_by, uint32_t now)
 247 {
 248         int i;
 249         /*
 250          * Increase our filter main by incr_by and
 251          * update its time. Then walk other's and
 252          * make them the new value too.
 253          */
 254         tf->entries[0].value += incr_by;
 255         tf->entries[0].time_up = now;
 256         for(i=1; i<NUM_FILTER_ENTRIES; i++) {
 257                 tf->entries[i].value = tf->entries[0].value;
 258                 tf->entries[i].time_up = now;
 259         }
 260 }
 261
 262 void
 263 filter_increase_by_small(struct time_filter_small *tf, uint32_t incr_by, uint32_t now)
 264 {
 265         int i;
 266         /*
 267          * Increase our filter main by incr_by and
 268          * update its time. Then walk other's and
 269          * make them the new value too.
 270          */
 271         tf->entries[0].value += incr_by;
 272         tf->entries[0].time_up = now;
 273         for(i=1; i<NUM_FILTER_ENTRIES; i++) {
 274                 tf->entries[i].value = tf->entries[0].value;
 275                 tf->entries[i].time_up = now;
 276         }
 277 }
 278
 279 void
 280 forward_filter_clock(struct time_filter *tf, uint32_t ticks_forward)
 281 {
 282         /*
 283          * Bring forward all time values by N ticks. This
 284          * postpones expiring slots by that amount.
 285          */
 286         int i;
 287
 288         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 289                 tf->entries[i].time_up += ticks_forward;
 290         }
 291 }
 292
 293 void
 294 forward_filter_clock_small(struct time_filter_small *tf, uint32_t ticks_forward)
 295 {
 296         /*
 297          * Bring forward all time values by N ticks. This
 298          * postpones expiring slots by that amount.
 299          */
 300         int i;
 301
 302         for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 303                 tf->entries[i].time_up += ticks_forward;
 304         }
 305 }
 306
 307 void
 308 tick_filter_clock(struct time_filter *tf, uint32_t now)
 309 {
 310         int i;
 311         uint32_t tim, time_limit;
 312
 313         /*
 314          * We start at two positions back. This
 315          * is because the oldest worst value is
 316          * preserved always, i.e. it can't expire
 317          * due to clock ticking with no updated value.
 318          *
 319          * The other choice would be to fill it in with
 320          * zero, but I don't like that option since
 321          * some measurement is better than none (even
 322          * if its your oldest measurement).
 323          */
 324         for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
 325                 tim = now - tf->entries[i].time_up;
 326                 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 327                 if (tim >= time_limit) {
 328                         /*
 329                          * This entry is expired, pull down
 330                          * the next one up.
 331                          */
 332                         tf->entries[i].value = tf->entries[(i+1)].value;
 333                         tf->entries[i].time_up = tf->entries[(i+1)].time_up;
 334                 }
 335         }
 336 }
 337
 338 void
 339 tick_filter_clock_small(struct time_filter_small *tf, uint32_t now)
 340 {
 341         int i;
 342         uint32_t tim, time_limit;
 343
 344         /*
 345          * We start at two positions back. This
 346          * is because the oldest worst value is
 347          * preserved always, i.e. it can't expire
 348          * due to clock ticking with no updated value.
 349          *
 350          * The other choice would be to fill it in with
 351          * zero, but I don't like that option since
 352          * some measurement is better than none (even
 353          * if its your oldest measurement).
 354          */
 355         for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) {
 356                 tim = now - tf->entries[i].time_up;
 357                 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES;
 358                 if (tim >= time_limit) {
 359                         /*
 360                          * This entry is expired, pull down
 361                          * the next one up.
 362                          */
 363                         tf->entries[i].value = tf->entries[(i+1)].value;
 364                         tf->entries[i].time_up = tf->entries[(i+1)].time_up;
 365                 }
 366         }
 367 }
 368
 369 uint32_t
 370 apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now)
 371 {
 372         int i, j;
 373
 374         if (value <= tf->entries[0].value) {
 375                 /* Zap them all */
 376                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 377                         tf->entries[i].value = value;
 378                         tf->entries[i].time_up = now;
 379                 }
 380                 return (tf->entries[0].value);
 381         }
 382         for (j=1; j<NUM_FILTER_ENTRIES; j++) {
 383                 if (value <= tf->entries[j].value) {
 384                         for(i=j; i<NUM_FILTER_ENTRIES; i++) {
 385                                 tf->entries[i].value = value;
 386                                 tf->entries[i].time_up = now;
 387                         }
 388                         break;
 389                 }
 390         }
 391         check_update_times(tf, value, now);
 392         return (tf->entries[0].value);
 393 }
 394
 395 uint32_t
 396 apply_filter_min_small(struct time_filter_small *tf,
 397                        uint32_t value, uint32_t now)
 398 {
 399         int i, j;
 400
 401         if (value <= tf->entries[0].value) {
 402                 /* Zap them all */
 403                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 404                         tf->entries[i].value = value;
 405                         tf->entries[i].time_up = now;
 406                 }
 407                 return (tf->entries[0].value);
 408         }
 409         for (j=1; j<NUM_FILTER_ENTRIES; j++) {
 410                 if (value <= tf->entries[j].value) {
 411                         for(i=j; i<NUM_FILTER_ENTRIES; i++) {
 412                                 tf->entries[i].value = value;
 413                                 tf->entries[i].time_up = now;
 414                         }
 415                         break;
 416                 }
 417         }
 418         check_update_times_small(tf, value, now);
 419         return (tf->entries[0].value);
 420 }
 421
 422 uint32_t
 423 apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now)
 424 {
 425         int i, j;
 426
 427         if (value >= tf->entries[0].value) {
 428                 /* Zap them all */
 429                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 430                         tf->entries[i].value = value;
 431                         tf->entries[i].time_up = now;
 432                 }
 433                 return (tf->entries[0].value);
 434         }
 435         for (j=1; j<NUM_FILTER_ENTRIES; j++) {
 436                 if (value >= tf->entries[j].value) {
 437                         for(i=j; i<NUM_FILTER_ENTRIES; i++) {
 438                                 tf->entries[i].value = value;
 439                                 tf->entries[i].time_up = now;
 440                         }
 441                         break;
 442                 }
 443         }
 444         check_update_times(tf, value, now);
 445         return (tf->entries[0].value);
 446 }
 447
 448 uint32_t
 449 apply_filter_max_small(struct time_filter_small *tf,
 450                        uint32_t value, uint32_t now)
 451 {
 452         int i, j;
 453
 454         if (value >= tf->entries[0].value) {
 455                 /* Zap them all */
 456                 for(i=0; i<NUM_FILTER_ENTRIES; i++) {
 457                         tf->entries[i].value = value;
 458                         tf->entries[i].time_up = now;
 459                 }
 460                 return (tf->entries[0].value);
 461         }
 462         for (j=1; j<NUM_FILTER_ENTRIES; j++) {
 463                 if (value >= tf->entries[j].value) {
 464                         for(i=j; i<NUM_FILTER_ENTRIES; i++) {
 465                                 tf->entries[i].value = value;
 466                                 tf->entries[i].time_up = now;
 467                         }
 468                         break;
 469                 }
 470         }
 471         check_update_times_small(tf, value, now);
 472         return (tf->entries[0].value);
 473 }