usr/src/uts/common/io/vuid_queue.c

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