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 } 483