xref: /illumos-gate/usr/src/uts/common/io/vuid_queue.c (revision 2d6eb4a5e0a47d30189497241345dc5466bb68ab)

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

/*
 * 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);
}