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