isns/isnsd/sched.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (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 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>

#include "isns_server.h"
#include "isns_protocol.h"
#include "isns_log.h"
#include "isns_sched.h"
#include "isns_scn.h"
#include "isns_esi.h"

/*
 * extern variables.
 */

/*
 * global variables.
 */
pthread_mutex_t el_mtx = PTHREAD_MUTEX_INITIALIZER;

/*
 * local variables.
 */
static el_key_t **il;
static int icurr = 0;
static el_notice_t *curr = NULL;

static uint32_t DU;
static uint32_t DT;
static uint32_t LB;
static uint32_t NLIM;

/*
 * external variables.
 */

/*
 * local functions.
 */

/*
 * ****************************************************************************
 *
 * il_shift:
 *	Shift the indexed-list to the most current time.
 *
 * t	- most current time.
 *
 * ****************************************************************************
 */
static void
il_shift(
	uint32_t t
)
{
	el_notice_t *fn, *n;
	el_key_t *fk, *k;
	uint32_t nt;
	int c;

	k = il[icurr];
	while (k->time < t) {
		fk = k;
		fn = k->notice;
		/* remove the dummy key and dummy notice */
		fk->left->right = fk->right;
		fk->right->left = fk->left;
		fn->pred->sucd = fn->sucd;
		fn->sucd->pred = fn->pred;

		/* find the place where the dummy goes to */
		k = il[(icurr + DU - 1) % DU];
		if (k->time < INFINITY - DT) {
			nt = k->time + DT; /* next key time */
		} else {
			nt = INFINITY - 1; /* the last second */
		}
		while (k->time < nt) {
			k = k->right;
		}
		n = k->notice->pred;
		c = 1;
		while (n->time >= nt) {
			c ++;
			n = n->pred;
		}
		n = n->sucd;

		/* update lower bound */
		LB = fk->time;

		/* insert the dummy key */
		fk->time = nt;
		fk->count = k->count - c + 1;
		fk->left = k->left;
		fk->right = k;
		k->left->right = fk;
		k->left = fk;
		k->count = c;
		/* insert the dummy notice */
		fn->time = nt;
		fn->pred = n->pred;
		fn->sucd = n;
		n->pred->sucd = fn;
		n->pred = fn;

		/* shift the current index */
		icurr = (icurr + 1) % DU;
		k = il[icurr];
	}
}

/*
 * global functions.
 */

/*
 * ****************************************************************************
 *
 * el_init:
 *	Initialize the element list.
 *
 * du	- Number of uint in the indexed-list.
 * dt	- Time interval of the indexed-list.
 * nlim	- Limit number of each notice.
 * return - 0: successful, otherwise failed.
 *
 * ****************************************************************************
 */
int
el_init(
	uint32_t du,
	uint32_t dt,
	uint32_t nlim
)
{
	el_key_t *k, *kleft;
	el_notice_t *n, *npred;

	uint32_t t = 0;

	int i;

	if (du < 1 || dt < 1 || nlim < 1) {
		return (1);
	}

	DU = du;
	DT = dt;
	LB = 0;
	NLIM = nlim;

	/*
	 * initialize the event set
	 */

	/* first dummy notice */
	n = (el_notice_t *)malloc(sizeof (el_notice_t));
	if (n == NULL) {
		return (1);
	}
	n->time = LB;
	n->event = NULL;
	n->isdummy = 1;
	n->pred = NULL;
	npred = n;

	/* first dummy key */
	k = (el_key_t *)malloc(sizeof (el_key_t));
	if (k == NULL) {
		return (1);
	}
	k->time = LB;
	k->count = 1;
	k->notice = n;
	k->left = NULL;
	kleft = k;

	n->key = k;

	/* index list */
	il = (el_key_t **)malloc((DU + 1) * sizeof (el_key_t *));
	if (il == NULL) {
		return (1);
	}

	/* create notice list, key list & index list */
	for (i = 0; i < DU; i++) {
		t += DT;

		n = (el_notice_t *)malloc(sizeof (el_notice_t));
		if (n == NULL) {
			return (1);
		}
		n->time = t;
		n->event = NULL;
		n->isdummy = 1;
		n->pred = npred;
		npred->sucd = n;
		npred = n;

		k = (el_key_t *)malloc(sizeof (el_key_t));
		if (k == NULL) {
			return (1);
		}
		k->time = t;
		k->count = 1;
		k->notice = n;
		k->left = kleft;
		kleft->right = k;
		kleft = k;

		n->key = k;

		il[i] = k;
	}

	/* last dummy notice */
	n = (el_notice_t *)malloc(sizeof (el_notice_t));
	if (n == NULL) {
		return (1);
	}
	n->time = INFINITY; /* the end of the world */
	n->event = NULL;
	n->isdummy = 1;
	n->pred = npred;
	n->sucd = NULL;
	npred->sucd = n;

	/* last dummy key */
	k = (el_key_t *)malloc(sizeof (el_key_t));
	if (k == NULL) {
		return (1);
	}
	k->time = INFINITY; /* the end of the world */
	k->count = 1;
	k->notice = n;
	k->left = kleft;
	k->right = NULL;
	kleft->right = k;

	n->key = k;

	/* last index */
	il[DU] = k;

	return (0);
}

/*
 * ****************************************************************************
 *
 * el_add:
 *	Add an event to the element list with it's execution time.
 *	It might not actually put the event to the list if the event
 *	is the most current one for execution.
 *
 * ev	- The Event.
 * t	- The time when the event is scheduled at.
 * evp	- Pointer of event for returning.
 * return - Error code.
 *
 * ****************************************************************************
 */
int
el_add(
	void *ev,
	uint32_t t,
	void **evp
)
{
	int ec = 0;

	uint32_t t1 = 0;

	int i, j;
	el_key_t *k;
	el_notice_t *n;

	el_key_t *y;
	el_notice_t *x;

	/* lock the event set */
	(void) pthread_mutex_lock(&el_mtx);

	/* strip it off from the event list which is being handled */
	if (evf_again(ev) != 0) {
		/* if it is rescheduling an event and the event */
		/* was waiting for execution after idle finishes */
		if (evf_rem(ev) == 0 &&
		    evp != NULL &&
		    (curr == NULL || t <= curr->time)) {
			/* no need to reschedule it */
			*evp = ev;
			goto add_done;
		}
		evl_strip(ev);
		/* if it is marked as a removed event, do not add it */
		if (evf_rem(ev) != 0) {
			ev_free(ev);
			goto add_done;
		}
	}

	/* get the index in the il */
	if (t == 0) {
		t = ev_intval(ev);
		/* not initialization time */
		if (evf_init(ev) || evf_again(ev)) {
			t1 = get_stopwatch(evf_wakeup(ev));
			/* make il up to date */
			il_shift(t1);
			/* avoid overflow */
			if (t1 >= INFINITY - t) {
				/* the last second */
				t1 = INFINITY - t1 - 1;
			}
		}
		t += t1;
	}
	i = (t - LB) / DT;
	if (i >= DU) {
		i = DU;
	} else {
		i = (i + icurr) % DU;
	}

	/* find the right key */
	k = (il[i])->left;
	while (k->time > t) {
		k = k->left;
	}
	k = k->right;

	/* need to split */
	if (k->count == NLIM) {
		/* insert a new key */
		y = (el_key_t *)malloc(sizeof (el_key_t));
		if (y == NULL) {
			ec = ISNS_RSP_INTERNAL_ERROR;
			goto add_done;
		}
		k->count = NLIM / 2;
		x = k->notice;
		for (j = 1; j <= NLIM / 2; j++) {
			x = x->pred;
		}
		y->time = x->time;
		y->count = NLIM - NLIM / 2;
		y->notice = x;
		y->right = k;
		y->left = k->left;
		k->left->right = y;
		k->left = y;

		/* update the key */
		x->key = y;

		/* shift */
		if (y->time > t) {
			k = y;
		}
	}

	/* make a new notice */
	x = (el_notice_t *)malloc(sizeof (el_notice_t));
	if (x == NULL) {
		ec = ISNS_RSP_INTERNAL_ERROR;
		goto add_done;
	}
	x->time = t;
	x->event = ev;
	x->isdummy = 0;
	x->key = NULL;

	/* insert it */
	n = k->notice;
	while (n->time > t) {
		n = n->pred;
	}
	x->pred = n;
	x->sucd = n->sucd;
	n->sucd->pred = x;
	n->sucd = x;

	/* increase number of notice */
	k->count ++;

	/* reset current notice and wake up idle */
	if (curr == NULL || curr->time > t) {
		curr = x;
	}

	/* clear event flags */
	evf_zero(ev);

	isnslog(LOG_DEBUG, "el_add", "%s [%d] is scheduled at %d.",
	    ((ev_t *)ev)->type == EV_ESI ? "ESI" : "REG_EXP",
	    ((ev_t *)ev)->uid,
	    t);

add_done:
	/* unlock the event set */
	(void) pthread_mutex_unlock(&el_mtx);

	/* failed, free it */
	if (ec != 0) {
		ev_free(ev);
		isnslog(LOG_DEBUG, "el_add", "failed, no memory.");
	}

	return (ec);
}

/*
 * ****************************************************************************
 *
 * el_remove:
 *	Remove or update an event from the element list. If the event is
 *	currently not in the element list, it must be in a queue which
 *	contains all of event which are being executing at the moment.
 *	So it seeks the event from the list prior to the element list.
 *
 * id1	- The event ID.
 * id2	- The second ID for the event update.
 * pending - Do not actually remove, mark it for removal pending.
 * return - Error code.
 *
 * ****************************************************************************
 */
int
el_remove(
	uint32_t id1,
	uint32_t id2,
	int pending
)
{
	el_key_t *k, *kl, *kr;
	el_notice_t *n, *n2;

	(void) pthread_mutex_lock(&el_mtx);

	/* search the event from the event list which is being handled */
	if (evl_remove(id1, id2, pending) != 0) {
		(void) pthread_mutex_unlock(&el_mtx);
		return (0);
	}

	/* search the notice starting from current */
	n = curr;
	while (n != NULL) {
		/* found the match notice */
		if (!n->isdummy && ev_match(n->event, id1) != 0) {
			if (ev_remove(n->event, id2, 1, pending) == 0) {
				/* update the key of the match notice */
				k = n->key;
				if (k != NULL && k->count == 1) {
					/* no more notice */
					k->left->right = k->right;
					k->right->left = k->left;
					free(k);
				} else {
					if (k != NULL) {
						k->notice = n->pred;
						k->notice->key = k;
						k->time = k->notice->time;
					}
					n2 = n;
					k = n2->key;
					while (k == NULL) {
						n2 = n2->sucd;
						k = n2->key;
					}
					/* decrease the count by one */
					k->count --;
					/* merge the keys */
					kl = k->left;
					kr = k->right;
					if (!kl->notice->isdummy &&
					    (kl->count + k->count) <= NLIM) {
						/* delete the left key */
						k->count += kl->count;
						k->left = kl->left;
						k->left->right = k;
						kl->notice->key = NULL;
						free(kl);
					} else if (!k->notice->isdummy &&
					    (kr->count + k->count) <= NLIM) {
						/* delete this key */
						kr->count += k->count;
						kr->left = k->left;
						kr->left->right = kr;
						k->notice->key = NULL;
						free(k);
					}
				}
				/* delete the match notice */
				n->pred->sucd = n->sucd;
				n->sucd->pred = n->pred;
				/* update current */
				if (n == curr) {
					n2 = n->sucd;
					while (n2 != NULL && n2->isdummy) {
						n2 = n2->sucd;
					}
					curr = n2;
				}
				free(n);
			}
			break; /* exit while loop */
		}
		n = n->sucd;
	}

	(void) pthread_mutex_unlock(&el_mtx);

	return (0);
}

/*
 * ****************************************************************************
 *
 * el_first:
 *	Fetch the first event from the element list.
 *
 * t	- Pointer of time of the event for returning.
 * return - The event.
 *
 * ****************************************************************************
 */
void *
el_first(
	uint32_t *t
)
{
	void *p = NULL;

	el_notice_t *n;
	el_key_t *k;

	(void) pthread_mutex_lock(&el_mtx);

	if (curr != NULL) {
		/* remove current from the event set */
		curr->pred->sucd = curr->sucd;
		curr->sucd->pred = curr->pred;

		/* decrease number of notice */
		n = curr;
		while (n->key == NULL) {
			n = n->sucd;
		}
		k = n->key;
		k->count --;

		/* empty not-dummy key */
		if (k->count == 0) {
			k->left->right = k->right;
			k->right->left = k->left;
			free(k);
		}

		/* get next notice */
		n = curr->sucd;
		while (n != NULL && n->isdummy) {
			n = n->sucd;
		}

		/* return the time */
		*t = curr->time;
		/* reset current notice */
		p = curr->event;
		free(curr);
		curr = n;
	}

	/* the one that is being handled by esi_proc */
	if (p) {
		evl_append(p);
	}

	(void) pthread_mutex_unlock(&el_mtx);

	if (p) {
		isnslog(LOG_DEBUG, "el_first", "%s [%d] is fetched.",
		    ((ev_t *)p)->type == EV_ESI ? "ESI" : "REG_EXP",
		    ((ev_t *)p)->uid);
	}

	return (p);
}