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