usr/src/uts/common/io/vuid_queue.c - illumos-gate - Gitiles

 /*
  * CDDL HEADER START
  *
  * The contents of this file are subject to the terms of the
  * Common Development and Distribution License, Version 1.0 only
  * (the "License").  You may not use this file except in compliance
  * with the License.
  *
  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
  * or http://www.opensolaris.org/os/licensing.
  * See the License for the specific language governing permissions
  * and limitations under the License.
  *
  * When distributing Covered Code, include this CDDL HEADER in each
  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  * If applicable, add the following below this CDDL HEADER, with the
  * fields enclosed by brackets "[]" replaced with your own identifying
  * information: Portions Copyright [yyyy] [name of copyright owner]
  *
  * CDDL HEADER END
  */
 /*
  * Copyright (c) 1985, 1997 by Sun Microsystems, Inc.
  * All rights reserved.
  */

 #pragma ident	"%Z%%M%	%I%	%E% SMI"

 /*
  * Vuid (Virtual User Input Device) queue management.
  */

 #include <sys/types.h>
 #include <sys/time.h>
 #include <sys/vuid_event.h>
 #include <sys/vuid_queue.h>

 static Vuid_q_node *vq_alloc_node(Vuid_queue *vq);
 static void vq_free_node(Vuid_queue *vq, Vuid_q_node *vqn);

 static int tv_equal(struct timeval32 a, struct timeval32 b);
 static struct timeval32 tv_subt(struct timeval32 atv, struct timeval32 btv);
 static struct timeval32 tv_divide(struct timeval32 tv, int dividend);
 static struct timeval32 tv_mult(struct timeval32 tv, int multiplier);
 #define	tv_to_usec(tv)	(((tv).tv_sec * 1000000) + (tv).tv_usec)
 		/* Works for small numbers (< 1000) of seconds */
 static struct timeval32 usec_to_tv(int usec);

 void
 vq_initialize(Vuid_queue *vq, caddr_t data, u_int bytes)
 {
 	Vuid_q_node *new_vqns, *vqn;

 	/* Initialize vq */
 	vq->top = vq->bottom = vq->free = VUID_Q_NODE_NULL;
 	vq->size = 1 + (bytes - sizeof (Vuid_q_node)) / sizeof (Vuid_q_node);
 	/* Place in pool by freeing all nodes (fudge vq->num for this) */
 	new_vqns = (Vuid_q_node *)data;
 	vq->num = vq->size;
 	for (vqn = new_vqns; vqn < new_vqns + vq->size; vqn++)
 		vq_free_node(vq, vqn);
 }

 Vuid_q_code
 vq_put(Vuid_queue *vq, Firm_event *firm_event)
 {
 	Vuid_q_node *vp;

 	/* Merge into existing events based on time stamp */
 	for (vp = vq->bottom; vp; vp = vp->prev) {
 		/* Put later times closer to the bottom than earlier ones */
 		if (timercmp(&vp->firm_event.time, &firm_event->time,
 		    < /* comment to make cstyle happy - heinous! */) ||
 		    tv_equal(vp->firm_event.time, firm_event->time)) {
 			Vuid_q_node *vqn = vq_alloc_node(vq);

 			if (vqn == VUID_Q_NODE_NULL)
 				return (VUID_Q_OVERFLOW);
 			vqn->firm_event = *firm_event;
 			/* Insert vqn before vq (neither are null) */
 			/* Initialize vqn's next and prev */
 			vqn->next = vp->next;
 			vqn->prev = vp;
 			/* Fix up vp next's prev */
 			if (vp->next != VUID_Q_NODE_NULL)
 				vp->next->prev = vqn;
 			/* Fix up vp's next */
 			vp->next = vqn;
 			/* Change bottom */
 			if (vp == vq->bottom)
 				vq->bottom = vqn;
 			/* Change top */
 			if (vq->top == VUID_Q_NODE_NULL)
 				vq->top = vqn;
 			return (VUID_Q_OK);
 		}
 	}
 	/* Place at top of queue */
 	return (vq_putback(vq, firm_event));
 }

 Vuid_q_code
 vq_get(Vuid_queue *vq, Firm_event *firm_event)
 {
 	Vuid_q_node *vqn = vq->top;

 	if (vqn == VUID_Q_NODE_NULL)
 		return (VUID_Q_EMPTY);
 	/* Conditionally copy data */
 	if (firm_event != FIRM_EVENT_NULL)
 		*firm_event = vqn->firm_event;
 	/* Change top */
 	vq->top = vqn->next;
 	/* Null new top's prev */
 	if (vq->top != VUID_Q_NODE_NULL)
 		vq->top->prev = VUID_Q_NODE_NULL;
 	/* Change bottom */
 	if (vq->bottom == vqn)
 		vq->bottom = VUID_Q_NODE_NULL;
 	/* Release storage */
 	vq_free_node(vq, vqn);
 	return (VUID_Q_OK);
 }

 Vuid_q_code
 vq_peek(Vuid_queue *vq, Firm_event *firm_event)
 {
 	if (vq->top == VUID_Q_NODE_NULL)
 		return (VUID_Q_EMPTY);
 	*firm_event = vq->top->firm_event;
 	return (VUID_Q_OK);
 }

 Vuid_q_code
 vq_putback(Vuid_queue *vq, Firm_event *firm_event)
 {
 	Vuid_q_node *vqn = vq_alloc_node(vq);

 	if (vqn == VUID_Q_NODE_NULL)
 		return (VUID_Q_OVERFLOW);
 	vqn->firm_event = *firm_event;
 	/* Change new top's next */
 	vqn->next = vq->top;
 	/* Null new top's prev */
 	vqn->prev = VUID_Q_NODE_NULL;
 	/* Change old top's prev */
 	if (vq->top != VUID_Q_NODE_NULL)
 		vq->top->prev = vqn;
 	/* Change top */
 	vq->top = vqn;
 	/* Change bottom */
 	if (vq->bottom == VUID_Q_NODE_NULL)
 		vq->bottom = vqn;
 	return (VUID_Q_OK);
 }

 int
 vq_compress(Vuid_queue *vq, int factor)
 {
 	struct timeval32 tv_interval, tv_avg_diff, tv_diff; /* Intermediates */
 	struct timeval32 tv_threshold;
 	Vuid_q_node *base, *victim;
 	Vuid_q_node *victim_next;
 	int num_start;

 	if (vq->top == VUID_Q_NODE_NULL)
 		return (0);
 	num_start = vq->num;
 	/*
 	 * Determine the threshold time interval under which events of
 	 * the same type (valuator only) are collapsed.
 	 * min_time_betvqnen_values = ((first_entry_time - last_entry_time) /
 	 * max_number_of_queue_entries) * factor_by_which_to_compress_queue;
 	 */
 	tv_interval = tv_subt(vq->bottom->firm_event.time,
 	    vq->top->firm_event.time);
 	tv_avg_diff = tv_divide(tv_interval, vq->num);
 	tv_threshold = tv_mult(tv_avg_diff, factor);
 	/* March down list */
 	for (base = vq->top; base; base = base->next) {
 		/* See if valuator event */
 		if (!vq_is_valuator(base))
 			continue;
 		/* Run down list looking for a collapse victim */
 		for (victim = base->next; victim; victim = victim_next) {
 			/* Remember next victim incase axe victim below */
 			victim_next = victim->next;
 			/* Fail if not valuator event */
 			if (!vq_is_valuator(victim))
 				goto Advance_Base;
 			/*
 			 * May peek ahead and do the collapse as long as the
 			 * intervening times of other valuator event types
 			 * are the same.  Fail if intervening event's time
 			 * differs from victim's.
 			 */
 			if (victim->prev != base) {
 				if (!tv_equal(victim->prev->firm_event.time,
 				    victim->firm_event.time))
 					goto Advance_Base;
 			}
 			/* Fail if time difference is above threshold */
 			tv_diff = tv_subt(victim->firm_event.time,
 			    base->firm_event.time);
 			/* Zero factor means collapse regardless of threshold */
 			if ((factor > 0) &&
 			    (timercmp(&tv_diff, &tv_threshold, > /* cstyle */)))
 				goto Advance_Base;
 			/* Do collapse if same event id */
 			if (victim->firm_event.id == base->firm_event.id) {
 				/* Collapse value into base event */
 				switch (base->firm_event.pair_type) {
 				case FE_PAIR_ABSOLUTE:
 					/* id is delta */
 					base->firm_event.value +=
 					    victim->firm_event.value;
 					break;
 				case FE_PAIR_DELTA:
 					/* id is absolute */
 					/* Fall through */
 				default:
 					/* Assume id is absolute */
 					base->firm_event.value =
 					    victim->firm_event.value;
 					break;
 				}
 				/* Remove victim node */
 				vq_delete_node(vq, victim);
 			}
 		}
 Advance_Base:
 	{}
 	}
 	return (num_start - vq->num);
 }

 int
 vq_is_valuator(Vuid_q_node *vqn)
 {
 	return ((vqn->firm_event.value < 1 && vqn->firm_event.value > -1) ||
 	    (vqn->firm_event.pair_type == FE_PAIR_DELTA) ||
 	    (vqn->firm_event.pair_type == FE_PAIR_ABSOLUTE));
 }

 void
 vq_delete_node(Vuid_queue *vq, Vuid_q_node *vqn)
 {
 	/* Use get if removing off top of queue */
 	if (vqn == vq->top) {
 		(void) vq_get(vq, FIRM_EVENT_NULL);
 		return;
 	}
 	/* Update previous next link (not null else vqn would be top) */
 	vqn->prev->next = vqn->next;
 	/* Change bottom */
 	if (vq->bottom == vqn)
 		vq->bottom = vqn->prev;
 	else
 		/* Update next previous link (if null else vqn is bottom) */
 		vqn->next->prev = vqn->prev;
 	/* Release storage */
 	vq_free_node(vq, vqn);
 }

 /*
  * Caller must initialize data returned from vq_alloc_node.
  * VUID_Q_NODE_NULL is possible.
  */
 static Vuid_q_node *
 vq_alloc_node(Vuid_queue *vq)
 {
 	Vuid_q_node *vqn;

 	if (vq->free == VUID_Q_NODE_NULL)
 		return (VUID_Q_NODE_NULL);
 	vqn = vq->free;
 	vq->free = vq->free->next;
 	vq->num++;
 	vqn->next = VUID_Q_NODE_NULL;
 	return (vqn);
 }

 static void
 vq_free_node(Vuid_queue *vq, Vuid_q_node *vqn)
 {
 	vqn->next = vq->free;
 	vqn->prev = VUID_Q_NODE_NULL;
 	vq->free = vqn;
 	vq->num--;
 }

 static int
 tv_equal(struct timeval32 a, struct timeval32 b)
 {
 	return (a.tv_sec == b.tv_sec && a.tv_usec == b.tv_usec);
 }

 /* atv-btv */
 static struct timeval32
 tv_subt(struct timeval32 atv, struct timeval32 btv)
 {
 	if ((atv.tv_usec < btv.tv_usec) && atv.tv_sec) {
 		atv.tv_usec += 1000000;
 		atv.tv_sec--;
 	}
 	if (atv.tv_usec > btv.tv_usec)
 		atv.tv_usec -= btv.tv_usec;
 	else
 		atv.tv_usec = 0;
 	if (atv.tv_sec > btv.tv_sec)
 		atv.tv_sec -= btv.tv_sec;
 	else {
 		if (atv.tv_sec < btv.tv_sec)
 			atv.tv_usec = 0;
 		atv.tv_sec = 0;
 	}
 	return (atv);
 }

 /* tv / dividend */
 static struct timeval32
 tv_divide(struct timeval32 tv, int dividend)
 {
 	int usecs;

 	if (dividend == 0)
 		return (tv);
 	usecs = tv_to_usec(tv);
 	usecs /= dividend;
 	tv = usec_to_tv(usecs);
 	return (tv);
 }

 /* tv * multiplier (works for small multipliers * seconds, < 1000) */
 static struct timeval32
 tv_mult(struct timeval32 tv, int multiplier)
 {
 	int usecs;

 	usecs = tv_to_usec(tv);
 	usecs *= multiplier;
 	tv = usec_to_tv(usecs);
 	return (tv);
 }

 static struct timeval32
 usec_to_tv(int usec)
 {
 	struct timeval32 tv;

 	tv.tv_sec = usec / 1000000;
 	tv.tv_usec = usec % 1000000;
 	return (tv);
 }
	/*
	* CDDL HEADER START
	*
	* The contents of this file are subject to the terms of the
	* Common Development and Distribution License, Version 1.0 only
	* (the "License"). You may not use this file except in compliance
	* with the License.
	*
	* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
	* or http://www.opensolaris.org/os/licensing.
	* See the License for the specific language governing permissions
	* and limitations under the License.
	*
	* When distributing Covered Code, include this CDDL HEADER in each
	* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
	* If applicable, add the following below this CDDL HEADER, with the
	* fields enclosed by brackets "[]" replaced with your own identifying
	* information: Portions Copyright [yyyy] [name of copyright owner]
	*
	* CDDL HEADER END
	*/
	/*
	* Copyright (c) 1985, 1997 by Sun Microsystems, Inc.
	* All rights reserved.
	*/

	#pragma ident "%Z%%M% %I% %E% SMI"

	/*
	* Vuid (Virtual User Input Device) queue management.
	*/

	#include <sys/types.h>
	#include <sys/time.h>
	#include <sys/vuid_event.h>
	#include <sys/vuid_queue.h>

	static Vuid_q_node vq_alloc_node(Vuid_queue vq);
	static void vq_free_node(Vuid_queue vq, Vuid_q_node vqn);

	static int tv_equal(struct timeval32 a, struct timeval32 b);
	static struct timeval32 tv_subt(struct timeval32 atv, struct timeval32 btv);
	static struct timeval32 tv_divide(struct timeval32 tv, int dividend);
	static struct timeval32 tv_mult(struct timeval32 tv, int multiplier);
	#define tv_to_usec(tv) (((tv).tv_sec * 1000000) + (tv).tv_usec)
	/* Works for small numbers (< 1000) of seconds */
	static struct timeval32 usec_to_tv(int usec);

	void
	vq_initialize(Vuid_queue *vq, caddr_t data, u_int bytes)
	{
	Vuid_q_node new_vqns, vqn;

	/* Initialize vq */
	vq->top = vq->bottom = vq->free = VUID_Q_NODE_NULL;
	vq->size = 1 + (bytes - sizeof (Vuid_q_node)) / sizeof (Vuid_q_node);
	/* Place in pool by freeing all nodes (fudge vq->num for this) */
	new_vqns = (Vuid_q_node *)data;
	vq->num = vq->size;
	for (vqn = new_vqns; vqn < new_vqns + vq->size; vqn++)
	vq_free_node(vq, vqn);
	}

	Vuid_q_code
	vq_put(Vuid_queue vq, Firm_event firm_event)
	{
	Vuid_q_node *vp;

	/* Merge into existing events based on time stamp */
	for (vp = vq->bottom; vp; vp = vp->prev) {
	/* Put later times closer to the bottom than earlier ones */
	if (timercmp(&vp->firm_event.time, &firm_event->time,
	< /* comment to make cstyle happy - heinous! */) \|\|
	tv_equal(vp->firm_event.time, firm_event->time)) {
	Vuid_q_node *vqn = vq_alloc_node(vq);

	if (vqn == VUID_Q_NODE_NULL)
	return (VUID_Q_OVERFLOW);
	vqn->firm_event = *firm_event;
	/* Insert vqn before vq (neither are null) */
	/* Initialize vqn's next and prev */
	vqn->next = vp->next;
	vqn->prev = vp;
	/* Fix up vp next's prev */
	if (vp->next != VUID_Q_NODE_NULL)
	vp->next->prev = vqn;
	/* Fix up vp's next */
	vp->next = vqn;
	/* Change bottom */
	if (vp == vq->bottom)
	vq->bottom = vqn;
	/* Change top */
	if (vq->top == VUID_Q_NODE_NULL)
	vq->top = vqn;
	return (VUID_Q_OK);
	}
	}
	/* Place at top of queue */
	return (vq_putback(vq, firm_event));
	}

	Vuid_q_code
	vq_get(Vuid_queue vq, Firm_event firm_event)
	{
	Vuid_q_node *vqn = vq->top;

	if (vqn == VUID_Q_NODE_NULL)
	return (VUID_Q_EMPTY);
	/* Conditionally copy data */
	if (firm_event != FIRM_EVENT_NULL)
	*firm_event = vqn->firm_event;
	/* Change top */
	vq->top = vqn->next;
	/* Null new top's prev */
	if (vq->top != VUID_Q_NODE_NULL)
	vq->top->prev = VUID_Q_NODE_NULL;
	/* Change bottom */
	if (vq->bottom == vqn)
	vq->bottom = VUID_Q_NODE_NULL;
	/* Release storage */
	vq_free_node(vq, vqn);
	return (VUID_Q_OK);
	}

	Vuid_q_code
	vq_peek(Vuid_queue vq, Firm_event firm_event)
	{
	if (vq->top == VUID_Q_NODE_NULL)
	return (VUID_Q_EMPTY);
	*firm_event = vq->top->firm_event;
	return (VUID_Q_OK);
	}

	Vuid_q_code
	vq_putback(Vuid_queue vq, Firm_event firm_event)
	{
	Vuid_q_node *vqn = vq_alloc_node(vq);

	if (vqn == VUID_Q_NODE_NULL)
	return (VUID_Q_OVERFLOW);
	vqn->firm_event = *firm_event;
	/* Change new top's next */
	vqn->next = vq->top;
	/* Null new top's prev */
	vqn->prev = VUID_Q_NODE_NULL;
	/* Change old top's prev */
	if (vq->top != VUID_Q_NODE_NULL)
	vq->top->prev = vqn;
	/* Change top */
	vq->top = vqn;
	/* Change bottom */
	if (vq->bottom == VUID_Q_NODE_NULL)
	vq->bottom = vqn;
	return (VUID_Q_OK);
	}

	int
	vq_compress(Vuid_queue *vq, int factor)
	{
	struct timeval32 tv_interval, tv_avg_diff, tv_diff; /* Intermediates */
	struct timeval32 tv_threshold;
	Vuid_q_node base, victim;
	Vuid_q_node *victim_next;
	int num_start;

	if (vq->top == VUID_Q_NODE_NULL)
	return (0);
	num_start = vq->num;
	/*
	* Determine the threshold time interval under which events of
	* the same type (valuator only) are collapsed.
	* min_time_betvqnen_values = ((first_entry_time - last_entry_time) /
	* max_number_of_queue_entries) * factor_by_which_to_compress_queue;
	*/
	tv_interval = tv_subt(vq->bottom->firm_event.time,
	vq->top->firm_event.time);
	tv_avg_diff = tv_divide(tv_interval, vq->num);
	tv_threshold = tv_mult(tv_avg_diff, factor);
	/* March down list */
	for (base = vq->top; base; base = base->next) {
	/* See if valuator event */
	if (!vq_is_valuator(base))
	continue;
	/* Run down list looking for a collapse victim */
	for (victim = base->next; victim; victim = victim_next) {
	/* Remember next victim incase axe victim below */
	victim_next = victim->next;
	/* Fail if not valuator event */
	if (!vq_is_valuator(victim))
	goto Advance_Base;
	/*
	* May peek ahead and do the collapse as long as the
	* intervening times of other valuator event types
	* are the same. Fail if intervening event's time
	* differs from victim's.
	*/
	if (victim->prev != base) {
	if (!tv_equal(victim->prev->firm_event.time,
	victim->firm_event.time))
	goto Advance_Base;
	}
	/* Fail if time difference is above threshold */
	tv_diff = tv_subt(victim->firm_event.time,
	base->firm_event.time);
	/* Zero factor means collapse regardless of threshold */
	if ((factor > 0) &&
	(timercmp(&tv_diff, &tv_threshold, > /* cstyle */)))
	goto Advance_Base;
	/* Do collapse if same event id */
	if (victim->firm_event.id == base->firm_event.id) {
	/* Collapse value into base event */
	switch (base->firm_event.pair_type) {
	case FE_PAIR_ABSOLUTE:
	/* id is delta */
	base->firm_event.value +=
	victim->firm_event.value;
	break;
	case FE_PAIR_DELTA:
	/* id is absolute */
	/* Fall through */
	default:
	/* Assume id is absolute */
	base->firm_event.value =
	victim->firm_event.value;
	break;
	}
	/* Remove victim node */
	vq_delete_node(vq, victim);
	}
	}
	Advance_Base:
	{}
	}
	return (num_start - vq->num);
	}

	int
	vq_is_valuator(Vuid_q_node *vqn)
	{
	return ((vqn->firm_event.value < 1 && vqn->firm_event.value > -1) \|\|
	(vqn->firm_event.pair_type == FE_PAIR_DELTA) \|\|
	(vqn->firm_event.pair_type == FE_PAIR_ABSOLUTE));
	}

	void
	vq_delete_node(Vuid_queue vq, Vuid_q_node vqn)
	{
	/* Use get if removing off top of queue */
	if (vqn == vq->top) {
	(void) vq_get(vq, FIRM_EVENT_NULL);
	return;
	}
	/* Update previous next link (not null else vqn would be top) */
	vqn->prev->next = vqn->next;
	/* Change bottom */
	if (vq->bottom == vqn)
	vq->bottom = vqn->prev;
	else
	/* Update next previous link (if null else vqn is bottom) */
	vqn->next->prev = vqn->prev;
	/* Release storage */
	vq_free_node(vq, vqn);
	}

	/*
	* Caller must initialize data returned from vq_alloc_node.
	* VUID_Q_NODE_NULL is possible.
	*/
	static Vuid_q_node *
	vq_alloc_node(Vuid_queue *vq)
	{
	Vuid_q_node *vqn;

	if (vq->free == VUID_Q_NODE_NULL)
	return (VUID_Q_NODE_NULL);
	vqn = vq->free;
	vq->free = vq->free->next;
	vq->num++;
	vqn->next = VUID_Q_NODE_NULL;
	return (vqn);
	}

	static void
	vq_free_node(Vuid_queue vq, Vuid_q_node vqn)
	{
	vqn->next = vq->free;
	vqn->prev = VUID_Q_NODE_NULL;
	vq->free = vqn;
	vq->num--;
	}

	static int
	tv_equal(struct timeval32 a, struct timeval32 b)
	{
	return (a.tv_sec == b.tv_sec && a.tv_usec == b.tv_usec);
	}

	/* atv-btv */
	static struct timeval32
	tv_subt(struct timeval32 atv, struct timeval32 btv)
	{
	if ((atv.tv_usec < btv.tv_usec) && atv.tv_sec) {
	atv.tv_usec += 1000000;
	atv.tv_sec--;
	}
	if (atv.tv_usec > btv.tv_usec)
	atv.tv_usec -= btv.tv_usec;
	else
	atv.tv_usec = 0;
	if (atv.tv_sec > btv.tv_sec)
	atv.tv_sec -= btv.tv_sec;
	else {
	if (atv.tv_sec < btv.tv_sec)
	atv.tv_usec = 0;
	atv.tv_sec = 0;
	}
	return (atv);
	}

	/* tv / dividend */
	static struct timeval32
	tv_divide(struct timeval32 tv, int dividend)
	{
	int usecs;

	if (dividend == 0)
	return (tv);
	usecs = tv_to_usec(tv);
	usecs /= dividend;
	tv = usec_to_tv(usecs);
	return (tv);
	}

	/* tv * multiplier (works for small multipliers * seconds, < 1000) */
	static struct timeval32
	tv_mult(struct timeval32 tv, int multiplier)
	{
	int usecs;

	usecs = tv_to_usec(tv);
	usecs *= multiplier;
	tv = usec_to_tv(usecs);
	return (tv);
	}

	static struct timeval32
	usec_to_tv(int usec)
	{
	struct timeval32 tv;

	tv.tv_sec = usec / 1000000;
	tv.tv_usec = usec % 1000000;
	return (tv);
	}