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