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 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 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 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 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 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 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 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 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 * 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 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 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 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 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 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 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