xref: /titanic_44/usr/src/cmd/isns/isnsd/sched.c (revision a38ddfee9c8c6b6c5a2947ff52fd2338362a4444)
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 (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  */
26 
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <unistd.h>
31 #include <pthread.h>
32 
33 #include "isns_server.h"
34 #include "isns_protocol.h"
35 #include "isns_log.h"
36 #include "isns_sched.h"
37 #include "isns_scn.h"
38 #include "isns_esi.h"
39 
40 /*
41  * extern variables.
42  */
43 
44 /*
45  * global variables.
46  */
47 pthread_mutex_t el_mtx = PTHREAD_MUTEX_INITIALIZER;
48 
49 /*
50  * local variables.
51  */
52 static el_key_t **il;
53 static int icurr = 0;
54 static el_notice_t *curr = NULL;
55 
56 static uint32_t DU;
57 static uint32_t DT;
58 static uint32_t LB;
59 static uint32_t NLIM;
60 
61 /*
62  * external variables.
63  */
64 
65 /*
66  * local functions.
67  */
68 
69 /*
70  * ****************************************************************************
71  *
72  * il_shift:
73  *	Shift the indexed-list to the most current time.
74  *
75  * t	- most current time.
76  *
77  * ****************************************************************************
78  */
79 static void
80 il_shift(
81 	uint32_t t
82 )
83 {
84 	el_notice_t *fn, *n;
85 	el_key_t *fk, *k;
86 	uint32_t nt;
87 	int c;
88 
89 	k = il[icurr];
90 	while (k->time < t) {
91 		fk = k;
92 		fn = k->notice;
93 		/* remove the dummy key and dummy notice */
94 		fk->left->right = fk->right;
95 		fk->right->left = fk->left;
96 		fn->pred->sucd = fn->sucd;
97 		fn->sucd->pred = fn->pred;
98 
99 		/* find the place where the dummy goes to */
100 		k = il[(icurr + DU - 1) % DU];
101 		if (k->time < INFINITY - DT) {
102 			nt = k->time + DT; /* next key time */
103 		} else {
104 			nt = INFINITY - 1; /* the last second */
105 		}
106 		while (k->time < nt) {
107 			k = k->right;
108 		}
109 		n = k->notice->pred;
110 		c = 1;
111 		while (n->time >= nt) {
112 			c ++;
113 			n = n->pred;
114 		}
115 		n = n->sucd;
116 
117 		/* update lower bound */
118 		LB = fk->time;
119 
120 		/* insert the dummy key */
121 		fk->time = nt;
122 		fk->count = k->count - c + 1;
123 		fk->left = k->left;
124 		fk->right = k;
125 		k->left->right = fk;
126 		k->left = fk;
127 		k->count = c;
128 		/* insert the dummy notice */
129 		fn->time = nt;
130 		fn->pred = n->pred;
131 		fn->sucd = n;
132 		n->pred->sucd = fn;
133 		n->pred = fn;
134 
135 		/* shift the current index */
136 		icurr = (icurr + 1) % DU;
137 		k = il[icurr];
138 	}
139 }
140 
141 /*
142  * global functions.
143  */
144 
145 /*
146  * ****************************************************************************
147  *
148  * el_init:
149  *	Initialize the element list.
150  *
151  * du	- Number of uint in the indexed-list.
152  * dt	- Time interval of the indexed-list.
153  * nlim	- Limit number of each notice.
154  * return - 0: successful, otherwise failed.
155  *
156  * ****************************************************************************
157  */
158 int
159 el_init(
160 	uint32_t du,
161 	uint32_t dt,
162 	uint32_t nlim
163 )
164 {
165 	el_key_t *k, *kleft;
166 	el_notice_t *n, *npred;
167 
168 	uint32_t t = 0;
169 
170 	int i;
171 
172 	if (du < 1 || dt < 1 || nlim < 1) {
173 		return (1);
174 	}
175 
176 	DU = du;
177 	DT = dt;
178 	LB = 0;
179 	NLIM = nlim;
180 
181 	/*
182 	 * initialize the event set
183 	 */
184 
185 	/* first dummy notice */
186 	n = (el_notice_t *)malloc(sizeof (el_notice_t));
187 	if (n == NULL) {
188 		return (1);
189 	}
190 	n->time = LB;
191 	n->event = NULL;
192 	n->isdummy = 1;
193 	n->pred = NULL;
194 	npred = n;
195 
196 	/* first dummy key */
197 	k = (el_key_t *)malloc(sizeof (el_key_t));
198 	if (k == NULL) {
199 		return (1);
200 	}
201 	k->time = LB;
202 	k->count = 1;
203 	k->notice = n;
204 	k->left = NULL;
205 	kleft = k;
206 
207 	n->key = k;
208 
209 	/* index list */
210 	il = (el_key_t **)malloc((DU + 1) * sizeof (el_key_t *));
211 	if (il == NULL) {
212 		return (1);
213 	}
214 
215 	/* create notice list, key list & index list */
216 	for (i = 0; i < DU; i++) {
217 		t += DT;
218 
219 		n = (el_notice_t *)malloc(sizeof (el_notice_t));
220 		if (n == NULL) {
221 			return (1);
222 		}
223 		n->time = t;
224 		n->event = NULL;
225 		n->isdummy = 1;
226 		n->pred = npred;
227 		npred->sucd = n;
228 		npred = n;
229 
230 		k = (el_key_t *)malloc(sizeof (el_key_t));
231 		if (k == NULL) {
232 			return (1);
233 		}
234 		k->time = t;
235 		k->count = 1;
236 		k->notice = n;
237 		k->left = kleft;
238 		kleft->right = k;
239 		kleft = k;
240 
241 		n->key = k;
242 
243 		il[i] = k;
244 	}
245 
246 	/* last dummy notice */
247 	n = (el_notice_t *)malloc(sizeof (el_notice_t));
248 	if (n == NULL) {
249 		return (1);
250 	}
251 	n->time = INFINITY; /* the end of the world */
252 	n->event = NULL;
253 	n->isdummy = 1;
254 	n->pred = npred;
255 	n->sucd = NULL;
256 	npred->sucd = n;
257 
258 	/* last dummy key */
259 	k = (el_key_t *)malloc(sizeof (el_key_t));
260 	if (k == NULL) {
261 		return (1);
262 	}
263 	k->time = INFINITY; /* the end of the world */
264 	k->count = 1;
265 	k->notice = n;
266 	k->left = kleft;
267 	k->right = NULL;
268 	kleft->right = k;
269 
270 	n->key = k;
271 
272 	/* last index */
273 	il[DU] = k;
274 
275 	return (0);
276 }
277 
278 /*
279  * ****************************************************************************
280  *
281  * el_add:
282  *	Add an event to the element list with it's execution time.
283  *	It might not actually put the event to the list if the event
284  *	is the most current one for execution.
285  *
286  * ev	- The Event.
287  * t	- The time when the event is scheduled at.
288  * evp	- Pointer of event for returning.
289  * return - Error code.
290  *
291  * ****************************************************************************
292  */
293 int
294 el_add(
295 	void *ev,
296 	uint32_t t,
297 	void **evp
298 )
299 {
300 	int ec = 0;
301 
302 	uint32_t t1 = 0;
303 
304 	int i, j;
305 	el_key_t *k;
306 	el_notice_t *n;
307 
308 	el_key_t *y;
309 	el_notice_t *x;
310 
311 	/* lock the event set */
312 	(void) pthread_mutex_lock(&el_mtx);
313 
314 	/* strip it off from the event list which is being handled */
315 	if (evf_again(ev) != 0) {
316 		/* if it is rescheduling an event and the event */
317 		/* was waiting for execution after idle finishes */
318 		if (evf_rem(ev) == 0 &&
319 		    evp != NULL &&
320 		    (curr == NULL || t <= curr->time)) {
321 			/* no need to reschedule it */
322 			*evp = ev;
323 			goto add_done;
324 		}
325 		evl_strip(ev);
326 		/* if it is marked as a removed event, do not add it */
327 		if (evf_rem(ev) != 0) {
328 			ev_free(ev);
329 			goto add_done;
330 		}
331 	}
332 
333 	/* get the index in the il */
334 	if (t == 0) {
335 		t = ev_intval(ev);
336 		/* not initialization time */
337 		if (evf_init(ev) || evf_again(ev)) {
338 			t1 = get_stopwatch(evf_wakeup(ev));
339 			/* make il up to date */
340 			il_shift(t1);
341 			/* avoid overflow */
342 			if (t1 >= INFINITY - t) {
343 				/* the last second */
344 				t1 = INFINITY - t1 - 1;
345 			}
346 		}
347 		t += t1;
348 	}
349 	i = (t - LB) / DT;
350 	if (i >= DU) {
351 		i = DU;
352 	} else {
353 		i = (i + icurr) % DU;
354 	}
355 
356 	/* find the right key */
357 	k = (il[i])->left;
358 	while (k->time > t) {
359 		k = k->left;
360 	}
361 	k = k->right;
362 
363 	/* need to split */
364 	if (k->count == NLIM) {
365 		/* insert a new key */
366 		y = (el_key_t *)malloc(sizeof (el_key_t));
367 		if (y == NULL) {
368 			ec = ISNS_RSP_INTERNAL_ERROR;
369 			goto add_done;
370 		}
371 		k->count = NLIM / 2;
372 		x = k->notice;
373 		for (j = 1; j <= NLIM / 2; j++) {
374 			x = x->pred;
375 		}
376 		y->time = x->time;
377 		y->count = NLIM - NLIM / 2;
378 		y->notice = x;
379 		y->right = k;
380 		y->left = k->left;
381 		k->left->right = y;
382 		k->left = y;
383 
384 		/* update the key */
385 		x->key = y;
386 
387 		/* shift */
388 		if (y->time > t) {
389 			k = y;
390 		}
391 	}
392 
393 	/* make a new notice */
394 	x = (el_notice_t *)malloc(sizeof (el_notice_t));
395 	if (x == NULL) {
396 		ec = ISNS_RSP_INTERNAL_ERROR;
397 		goto add_done;
398 	}
399 	x->time = t;
400 	x->event = ev;
401 	x->isdummy = 0;
402 	x->key = NULL;
403 
404 	/* insert it */
405 	n = k->notice;
406 	while (n->time > t) {
407 		n = n->pred;
408 	}
409 	x->pred = n;
410 	x->sucd = n->sucd;
411 	n->sucd->pred = x;
412 	n->sucd = x;
413 
414 	/* increase number of notice */
415 	k->count ++;
416 
417 	/* reset current notice and wake up idle */
418 	if (curr == NULL || curr->time > t) {
419 		curr = x;
420 	}
421 
422 	/* clear event flags */
423 	evf_zero(ev);
424 
425 	isnslog(LOG_DEBUG, "el_add", "%s [%d] is scheduled at %d.",
426 	    ((ev_t *)ev)->type == EV_ESI ? "ESI" : "REG_EXP",
427 	    ((ev_t *)ev)->uid,
428 	    t);
429 
430 add_done:
431 	/* unlock the event set */
432 	(void) pthread_mutex_unlock(&el_mtx);
433 
434 	/* failed, free it */
435 	if (ec != 0) {
436 		ev_free(ev);
437 		isnslog(LOG_DEBUG, "el_add", "failed, no memory.");
438 	}
439 
440 	return (ec);
441 }
442 
443 /*
444  * ****************************************************************************
445  *
446  * el_remove:
447  *	Remove or update an event from the element list. If the event is
448  *	currently not in the element list, it must be in a queue which
449  *	contains all of event which are being executing at the moment.
450  *	So it seeks the event from the list prior to the element list.
451  *
452  * id1	- The event ID.
453  * id2	- The second ID for the event update.
454  * pending - Do not actually remove, mark it for removal pending.
455  * return - Error code.
456  *
457  * ****************************************************************************
458  */
459 int
460 el_remove(
461 	uint32_t id1,
462 	uint32_t id2,
463 	int pending
464 )
465 {
466 	el_key_t *k, *kl, *kr;
467 	el_notice_t *n, *n2;
468 
469 	(void) pthread_mutex_lock(&el_mtx);
470 
471 	/* search the event from the event list which is being handled */
472 	if (evl_remove(id1, id2, pending) != 0) {
473 		(void) pthread_mutex_unlock(&el_mtx);
474 		return (0);
475 	}
476 
477 	/* search the notice starting from current */
478 	n = curr;
479 	while (n != NULL) {
480 		/* found the match notice */
481 		if (!n->isdummy && ev_match(n->event, id1) != 0) {
482 			if (ev_remove(n->event, id2, 1, pending) == 0) {
483 				/* update the key of the match notice */
484 				k = n->key;
485 				if (k != NULL && k->count == 1) {
486 					/* no more notice */
487 					k->left->right = k->right;
488 					k->right->left = k->left;
489 					free(k);
490 				} else {
491 					if (k != NULL) {
492 						k->notice = n->pred;
493 						k->notice->key = k;
494 						k->time = k->notice->time;
495 					}
496 					n2 = n;
497 					k = n2->key;
498 					while (k == NULL) {
499 						n2 = n2->sucd;
500 						k = n2->key;
501 					}
502 					/* decrease the count by one */
503 					k->count --;
504 					/* merge the keys */
505 					kl = k->left;
506 					kr = k->right;
507 					if (!kl->notice->isdummy &&
508 					    (kl->count + k->count) <= NLIM) {
509 						/* delete the left key */
510 						k->count += kl->count;
511 						k->left = kl->left;
512 						k->left->right = k;
513 						kl->notice->key = NULL;
514 						free(kl);
515 					} else if (!k->notice->isdummy &&
516 					    (kr->count + k->count) <= NLIM) {
517 						/* delete this key */
518 						kr->count += k->count;
519 						kr->left = k->left;
520 						kr->left->right = kr;
521 						k->notice->key = NULL;
522 						free(k);
523 					}
524 				}
525 				/* delete the match notice */
526 				n->pred->sucd = n->sucd;
527 				n->sucd->pred = n->pred;
528 				/* update current */
529 				if (n == curr) {
530 					n2 = n->sucd;
531 					while (n2 != NULL && n2->isdummy) {
532 						n2 = n2->sucd;
533 					}
534 					curr = n2;
535 				}
536 				free(n);
537 			}
538 			break; /* exit while loop */
539 		}
540 		n = n->sucd;
541 	}
542 
543 	(void) pthread_mutex_unlock(&el_mtx);
544 
545 	return (0);
546 }
547 
548 /*
549  * ****************************************************************************
550  *
551  * el_first:
552  *	Fetch the first event from the element list.
553  *
554  * t	- Pointer of time of the event for returning.
555  * return - The event.
556  *
557  * ****************************************************************************
558  */
559 void *
560 el_first(
561 	uint32_t *t
562 )
563 {
564 	void *p = NULL;
565 
566 	el_notice_t *n;
567 	el_key_t *k;
568 
569 	(void) pthread_mutex_lock(&el_mtx);
570 
571 	if (curr != NULL) {
572 		/* remove current from the event set */
573 		curr->pred->sucd = curr->sucd;
574 		curr->sucd->pred = curr->pred;
575 
576 		/* decrease number of notice */
577 		n = curr;
578 		while (n->key == NULL) {
579 			n = n->sucd;
580 		}
581 		k = n->key;
582 		k->count --;
583 
584 		/* empty not-dummy key */
585 		if (k->count == 0) {
586 			k->left->right = k->right;
587 			k->right->left = k->left;
588 			free(k);
589 		}
590 
591 		/* get next notice */
592 		n = curr->sucd;
593 		while (n != NULL && n->isdummy) {
594 			n = n->sucd;
595 		}
596 
597 		/* return the time */
598 		*t = curr->time;
599 		/* reset current notice */
600 		p = curr->event;
601 		free(curr);
602 		curr = n;
603 	}
604 
605 	/* the one that is being handled by esi_proc */
606 	if (p) {
607 		evl_append(p);
608 	}
609 
610 	(void) pthread_mutex_unlock(&el_mtx);
611 
612 	if (p) {
613 		isnslog(LOG_DEBUG, "el_first", "%s [%d] is fetched.",
614 		    ((ev_t *)p)->type == EV_ESI ? "ESI" : "REG_EXP",
615 		    ((ev_t *)p)->uid);
616 	}
617 
618 	return (p);
619 }
620