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