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 340 void 341 tick_filter_clock_small(struct time_filter_small *tf, uint32_t now) 342 { 343 int i; 344 uint32_t tim, time_limit; 345 346 /* 347 * We start at two positions back. This 348 * is because the oldest worst value is 349 * preserved always, i.e. it can't expire 350 * due to clock ticking with no updated value. 351 * 352 * The other choice would be to fill it in with 353 * zero, but I don't like that option since 354 * some measurement is better than none (even 355 * if its your oldest measurment). 356 */ 357 for(i=(NUM_FILTER_ENTRIES-2); i>=0 ; i--) { 358 tim = now - tf->entries[i].time_up; 359 time_limit = (tf->cur_time_limit * (NUM_FILTER_ENTRIES-i))/NUM_FILTER_ENTRIES; 360 if (tim >= time_limit) { 361 /* 362 * This entry is expired, pull down 363 * the next one up. 364 */ 365 tf->entries[i].value = tf->entries[(i+1)].value; 366 tf->entries[i].time_up = tf->entries[(i+1)].time_up; 367 } 368 369 } 370 } 371 372 uint32_t 373 apply_filter_min(struct time_filter *tf, uint64_t value, uint32_t now) 374 { 375 int i, j; 376 377 if (value <= tf->entries[0].value) { 378 /* Zap them all */ 379 for(i=0; i<NUM_FILTER_ENTRIES; i++) { 380 tf->entries[i].value = value; 381 tf->entries[i].time_up = now; 382 } 383 return (tf->entries[0].value); 384 } 385 for (j=1; j<NUM_FILTER_ENTRIES; j++) { 386 if (value <= tf->entries[j].value) { 387 for(i=j; i<NUM_FILTER_ENTRIES; i++) { 388 tf->entries[i].value = value; 389 tf->entries[i].time_up = now; 390 } 391 break; 392 } 393 } 394 check_update_times(tf, value, now); 395 return (tf->entries[0].value); 396 } 397 398 uint32_t 399 apply_filter_min_small(struct time_filter_small *tf, 400 uint32_t value, uint32_t now) 401 { 402 int i, j; 403 404 if (value <= tf->entries[0].value) { 405 /* Zap them all */ 406 for(i=0; i<NUM_FILTER_ENTRIES; i++) { 407 tf->entries[i].value = value; 408 tf->entries[i].time_up = now; 409 } 410 return (tf->entries[0].value); 411 } 412 for (j=1; j<NUM_FILTER_ENTRIES; j++) { 413 if (value <= tf->entries[j].value) { 414 for(i=j; i<NUM_FILTER_ENTRIES; i++) { 415 tf->entries[i].value = value; 416 tf->entries[i].time_up = now; 417 } 418 break; 419 } 420 } 421 check_update_times_small(tf, value, now); 422 return (tf->entries[0].value); 423 } 424 425 uint32_t 426 apply_filter_max(struct time_filter *tf, uint64_t value, uint32_t now) 427 { 428 int i, j; 429 430 if (value >= tf->entries[0].value) { 431 /* Zap them all */ 432 for(i=0; i<NUM_FILTER_ENTRIES; i++) { 433 tf->entries[i].value = value; 434 tf->entries[i].time_up = now; 435 } 436 return (tf->entries[0].value); 437 } 438 for (j=1; j<NUM_FILTER_ENTRIES; j++) { 439 if (value >= tf->entries[j].value) { 440 for(i=j; i<NUM_FILTER_ENTRIES; i++) { 441 tf->entries[i].value = value; 442 tf->entries[i].time_up = now; 443 } 444 break; 445 } 446 } 447 check_update_times(tf, value, now); 448 return (tf->entries[0].value); 449 } 450 451 uint32_t 452 apply_filter_max_small(struct time_filter_small *tf, 453 uint32_t value, uint32_t now) 454 { 455 int i, j; 456 457 if (value >= tf->entries[0].value) { 458 /* Zap them all */ 459 for(i=0; i<NUM_FILTER_ENTRIES; i++) { 460 tf->entries[i].value = value; 461 tf->entries[i].time_up = now; 462 } 463 return (tf->entries[0].value); 464 } 465 for (j=1; j<NUM_FILTER_ENTRIES; j++) { 466 if (value >= tf->entries[j].value) { 467 for(i=j; i<NUM_FILTER_ENTRIES; i++) { 468 tf->entries[i].value = value; 469 tf->entries[i].time_up = now; 470 } 471 break; 472 } 473 } 474 check_update_times_small(tf, value, now); 475 return (tf->entries[0].value); 476 } 477