xref: /illumos-gate/usr/src/uts/common/io/vuid_queue.c (revision 7c478bd9)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License, Version 1.0 only
6  * (the "License").  You may not use this file except in compliance
7  * with the License.
8  *
9  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10  * or http://www.opensolaris.org/os/licensing.
11  * See the License for the specific language governing permissions
12  * and limitations under the License.
13  *
14  * When distributing Covered Code, include this CDDL HEADER in each
15  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16  * If applicable, add the following below this CDDL HEADER, with the
17  * fields enclosed by brackets "[]" replaced with your own identifying
18  * information: Portions Copyright [yyyy] [name of copyright owner]
19  *
20  * CDDL HEADER END
21  */
22 /*
23  * Copyright (c) 1985, 1997 by Sun Microsystems, Inc.
24  * All rights reserved.
25  */
26 
27 #pragma ident	"%Z%%M%	%I%	%E% SMI"
28 
29 /*
30  * Vuid (Virtual User Input Device) queue management.
31  */
32 
33 #include <sys/types.h>
34 #include <sys/time.h>
35 #include <sys/vuid_event.h>
36 #include <sys/vuid_queue.h>
37 
38 static Vuid_q_node *vq_alloc_node(Vuid_queue *vq);
39 static void vq_free_node(Vuid_queue *vq, Vuid_q_node *vqn);
40 
41 static int tv_equal(struct timeval32 a, struct timeval32 b);
42 static struct timeval32 tv_subt(struct timeval32 atv, struct timeval32 btv);
43 static struct timeval32 tv_divide(struct timeval32 tv, int dividend);
44 static struct timeval32 tv_mult(struct timeval32 tv, int multiplier);
45 #define	tv_to_usec(tv)	(((tv).tv_sec * 1000000) + (tv).tv_usec)
46 		/* Works for small numbers (< 1000) of seconds */
47 static struct timeval32 usec_to_tv(int usec);
48 
49 void
vq_initialize(Vuid_queue * vq,caddr_t data,u_int bytes)50 vq_initialize(Vuid_queue *vq, caddr_t data, u_int bytes)
51 {
52 	Vuid_q_node *new_vqns, *vqn;
53 
54 	/* Initialize vq */
55 	vq->top = vq->bottom = vq->free = VUID_Q_NODE_NULL;
56 	vq->size = 1 + (bytes - sizeof (Vuid_q_node)) / sizeof (Vuid_q_node);
57 	/* Place in pool by freeing all nodes (fudge vq->num for this) */
58 	new_vqns = (Vuid_q_node *)data;
59 	vq->num = vq->size;
60 	for (vqn = new_vqns; vqn < new_vqns + vq->size; vqn++)
61 		vq_free_node(vq, vqn);
62 }
63 
64 Vuid_q_code
vq_put(Vuid_queue * vq,Firm_event * firm_event)65 vq_put(Vuid_queue *vq, Firm_event *firm_event)
66 {
67 	Vuid_q_node *vp;
68 
69 	/* Merge into existing events based on time stamp */
70 	for (vp = vq->bottom; vp; vp = vp->prev) {
71 		/* Put later times closer to the bottom than earlier ones */
72 		if (timercmp(&vp->firm_event.time, &firm_event->time,
73 		    < /* comment to make cstyle happy - heinous! */) ||
74 		    tv_equal(vp->firm_event.time, firm_event->time)) {
75 			Vuid_q_node *vqn = vq_alloc_node(vq);
76 
77 			if (vqn == VUID_Q_NODE_NULL)
78 				return (VUID_Q_OVERFLOW);
79 			vqn->firm_event = *firm_event;
80 			/* Insert vqn before vq (neither are null) */
81 			/* Initialize vqn's next and prev */
82 			vqn->next = vp->next;
83 			vqn->prev = vp;
84 			/* Fix up vp next's prev */
85 			if (vp->next != VUID_Q_NODE_NULL)
86 				vp->next->prev = vqn;
87 			/* Fix up vp's next */
88 			vp->next = vqn;
89 			/* Change bottom */
90 			if (vp == vq->bottom)
91 				vq->bottom = vqn;
92 			/* Change top */
93 			if (vq->top == VUID_Q_NODE_NULL)
94 				vq->top = vqn;
95 			return (VUID_Q_OK);
96 		}
97 	}
98 	/* Place at top of queue */
99 	return (vq_putback(vq, firm_event));
100 }
101 
102 Vuid_q_code
vq_get(Vuid_queue * vq,Firm_event * firm_event)103 vq_get(Vuid_queue *vq, Firm_event *firm_event)
104 {
105 	Vuid_q_node *vqn = vq->top;
106 
107 	if (vqn == VUID_Q_NODE_NULL)
108 		return (VUID_Q_EMPTY);
109 	/* Conditionally copy data */
110 	if (firm_event != FIRM_EVENT_NULL)
111 		*firm_event = vqn->firm_event;
112 	/* Change top */
113 	vq->top = vqn->next;
114 	/* Null new top's prev */
115 	if (vq->top != VUID_Q_NODE_NULL)
116 		vq->top->prev = VUID_Q_NODE_NULL;
117 	/* Change bottom */
118 	if (vq->bottom == vqn)
119 		vq->bottom = VUID_Q_NODE_NULL;
120 	/* Release storage */
121 	vq_free_node(vq, vqn);
122 	return (VUID_Q_OK);
123 }
124 
125 Vuid_q_code
vq_peek(Vuid_queue * vq,Firm_event * firm_event)126 vq_peek(Vuid_queue *vq, Firm_event *firm_event)
127 {
128 	if (vq->top == VUID_Q_NODE_NULL)
129 		return (VUID_Q_EMPTY);
130 	*firm_event = vq->top->firm_event;
131 	return (VUID_Q_OK);
132 }
133 
134 Vuid_q_code
vq_putback(Vuid_queue * vq,Firm_event * firm_event)135 vq_putback(Vuid_queue *vq, Firm_event *firm_event)
136 {
137 	Vuid_q_node *vqn = vq_alloc_node(vq);
138 
139 	if (vqn == VUID_Q_NODE_NULL)
140 		return (VUID_Q_OVERFLOW);
141 	vqn->firm_event = *firm_event;
142 	/* Change new top's next */
143 	vqn->next = vq->top;
144 	/* Null new top's prev */
145 	vqn->prev = VUID_Q_NODE_NULL;
146 	/* Change old top's prev */
147 	if (vq->top != VUID_Q_NODE_NULL)
148 		vq->top->prev = vqn;
149 	/* Change top */
150 	vq->top = vqn;
151 	/* Change bottom */
152 	if (vq->bottom == VUID_Q_NODE_NULL)
153 		vq->bottom = vqn;
154 	return (VUID_Q_OK);
155 }
156 
157 int
vq_compress(Vuid_queue * vq,int factor)158 vq_compress(Vuid_queue *vq, int factor)
159 {
160 	struct timeval32 tv_interval, tv_avg_diff, tv_diff; /* Intermediates */
161 	struct timeval32 tv_threshold;
162 	Vuid_q_node *base, *victim;
163 	Vuid_q_node *victim_next;
164 	int num_start;
165 
166 	if (vq->top == VUID_Q_NODE_NULL)
167 		return (0);
168 	num_start = vq->num;
169 	/*
170 	 * Determine the threshold time interval under which events of
171 	 * the same type (valuator only) are collapsed.
172 	 * min_time_betvqnen_values = ((first_entry_time - last_entry_time) /
173 	 * max_number_of_queue_entries) * factor_by_which_to_compress_queue;
174 	 */
175 	tv_interval = tv_subt(vq->bottom->firm_event.time,
176 	    vq->top->firm_event.time);
177 	tv_avg_diff = tv_divide(tv_interval, vq->num);
178 	tv_threshold = tv_mult(tv_avg_diff, factor);
179 	/* March down list */
180 	for (base = vq->top; base; base = base->next) {
181 		/* See if valuator event */
182 		if (!vq_is_valuator(base))
183 			continue;
184 		/* Run down list looking for a collapse victim */
185 		for (victim = base->next; victim; victim = victim_next) {
186 			/* Remember next victim incase axe victim below */
187 			victim_next = victim->next;
188 			/* Fail if not valuator event */
189 			if (!vq_is_valuator(victim))
190 				goto Advance_Base;
191 			/*
192 			 * May peek ahead and do the collapse as long as the
193 			 * intervening times of other valuator event types
194 			 * are the same.  Fail if intervening event's time
195 			 * differs from victim's.
196 			 */
197 			if (victim->prev != base) {
198 				if (!tv_equal(victim->prev->firm_event.time,
199 				    victim->firm_event.time))
200 					goto Advance_Base;
201 			}
202 			/* Fail if time difference is above threshold */
203 			tv_diff = tv_subt(victim->firm_event.time,
204 			    base->firm_event.time);
205 			/* Zero factor means collapse regardless of threshold */
206 			if ((factor > 0) &&
207 			    (timercmp(&tv_diff, &tv_threshold, > /* cstyle */)))
208 				goto Advance_Base;
209 			/* Do collapse if same event id */
210 			if (victim->firm_event.id == base->firm_event.id) {
211 				/* Collapse value into base event */
212 				switch (base->firm_event.pair_type) {
213 				case FE_PAIR_ABSOLUTE:
214 					/* id is delta */
215 					base->firm_event.value +=
216 					    victim->firm_event.value;
217 					break;
218 				case FE_PAIR_DELTA:
219 					/* id is absolute */
220 					/* Fall through */
221 				default:
222 					/* Assume id is absolute */
223 					base->firm_event.value =
224 					    victim->firm_event.value;
225 					break;
226 				}
227 				/* Remove victim node */
228 				vq_delete_node(vq, victim);
229 			}
230 		}
231 Advance_Base:
232 	{}
233 	}
234 	return (num_start - vq->num);
235 }
236 
237 int
vq_is_valuator(Vuid_q_node * vqn)238 vq_is_valuator(Vuid_q_node *vqn)
239 {
240 	return ((vqn->firm_event.value < 1 && vqn->firm_event.value > -1) ||
241 	    (vqn->firm_event.pair_type == FE_PAIR_DELTA) ||
242 	    (vqn->firm_event.pair_type == FE_PAIR_ABSOLUTE));
243 }
244 
245 void
vq_delete_node(Vuid_queue * vq,Vuid_q_node * vqn)246 vq_delete_node(Vuid_queue *vq, Vuid_q_node *vqn)
247 {
248 	/* Use get if removing off top of queue */
249 	if (vqn == vq->top) {
250 		(void) vq_get(vq, FIRM_EVENT_NULL);
251 		return;
252 	}
253 	/* Update previous next link (not null else vqn would be top) */
254 	vqn->prev->next = vqn->next;
255 	/* Change bottom */
256 	if (vq->bottom == vqn)
257 		vq->bottom = vqn->prev;
258 	else
259 		/* Update next previous link (if null else vqn is bottom) */
260 		vqn->next->prev = vqn->prev;
261 	/* Release storage */
262 	vq_free_node(vq, vqn);
263 }
264 
265 /*
266  * Caller must initialize data returned from vq_alloc_node.
267  * VUID_Q_NODE_NULL is possible.
268  */
269 static Vuid_q_node *
vq_alloc_node(Vuid_queue * vq)270 vq_alloc_node(Vuid_queue *vq)
271 {
272 	Vuid_q_node *vqn;
273 
274 	if (vq->free == VUID_Q_NODE_NULL)
275 		return (VUID_Q_NODE_NULL);
276 	vqn = vq->free;
277 	vq->free = vq->free->next;
278 	vq->num++;
279 	vqn->next = VUID_Q_NODE_NULL;
280 	return (vqn);
281 }
282 
283 static void
vq_free_node(Vuid_queue * vq,Vuid_q_node * vqn)284 vq_free_node(Vuid_queue *vq, Vuid_q_node *vqn)
285 {
286 	vqn->next = vq->free;
287 	vqn->prev = VUID_Q_NODE_NULL;
288 	vq->free = vqn;
289 	vq->num--;
290 }
291 
292 static int
tv_equal(struct timeval32 a,struct timeval32 b)293 tv_equal(struct timeval32 a, struct timeval32 b)
294 {
295 	return (a.tv_sec == b.tv_sec && a.tv_usec == b.tv_usec);
296 }
297 
298 /* atv-btv */
299 static struct timeval32
tv_subt(struct timeval32 atv,struct timeval32 btv)300 tv_subt(struct timeval32 atv, struct timeval32 btv)
301 {
302 	if ((atv.tv_usec < btv.tv_usec) && atv.tv_sec) {
303 		atv.tv_usec += 1000000;
304 		atv.tv_sec--;
305 	}
306 	if (atv.tv_usec > btv.tv_usec)
307 		atv.tv_usec -= btv.tv_usec;
308 	else
309 		atv.tv_usec = 0;
310 	if (atv.tv_sec > btv.tv_sec)
311 		atv.tv_sec -= btv.tv_sec;
312 	else {
313 		if (atv.tv_sec < btv.tv_sec)
314 			atv.tv_usec = 0;
315 		atv.tv_sec = 0;
316 	}
317 	return (atv);
318 }
319 
320 /* tv / dividend */
321 static struct timeval32
tv_divide(struct timeval32 tv,int dividend)322 tv_divide(struct timeval32 tv, int dividend)
323 {
324 	int usecs;
325 
326 	if (dividend == 0)
327 		return (tv);
328 	usecs = tv_to_usec(tv);
329 	usecs /= dividend;
330 	tv = usec_to_tv(usecs);
331 	return (tv);
332 }
333 
334 /* tv * multiplier (works for small multipliers * seconds, < 1000) */
335 static struct timeval32
tv_mult(struct timeval32 tv,int multiplier)336 tv_mult(struct timeval32 tv, int multiplier)
337 {
338 	int usecs;
339 
340 	usecs = tv_to_usec(tv);
341 	usecs *= multiplier;
342 	tv = usec_to_tv(usecs);
343 	return (tv);
344 }
345 
346 static struct timeval32
usec_to_tv(int usec)347 usec_to_tv(int usec)
348 {
349 	struct timeval32 tv;
350 
351 	tv.tv_sec = usec / 1000000;
352 	tv.tv_usec = usec % 1000000;
353 	return (tv);
354 }
355