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
il_shift(uint32_t t)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
el_init(uint32_t du,uint32_t dt,uint32_t nlim)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
el_add(void * ev,uint32_t t,void ** evp)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
el_remove(uint32_t id1,uint32_t id2,int pending)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 *
el_first(uint32_t * t)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