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