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