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