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 36void 37reset_time(struct time_filter *tf, uint32_t time_len) 38{ 39 tf->cur_time_limit = time_len; 40} 41 42void 43reset_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 */ 73int 74setup_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 104int 105setup_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 135static void 136check_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 170static void 171check_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 205void 206filter_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 225void 226filter_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 245void 246filter_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 262void 263filter_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 279void 280forward_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 293void 294forward_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 307void 308tick_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 338void 339tick_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 369uint32_t 370apply_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 395uint32_t 396apply_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 422uint32_t 423apply_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 448uint32_t 449apply_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} 474