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
37void
38reset_time(struct time_filter *tf, uint32_t time_len)
39{
40	tf->cur_time_limit = time_len;
41}
42
43void
44reset_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 */
74int
75setup_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
105int
106setup_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
136static void
137check_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
171static void
172check_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
206void
207filter_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
226void
227filter_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
246void
247filter_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
263void
264filter_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
280void
281forward_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
294void
295forward_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
308void
309tick_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
339void
340tick_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 measurment).
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
370uint32_t
371apply_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
396uint32_t
397apply_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
423uint32_t
424apply_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
449uint32_t
450apply_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