usr/src/cmd/isns/isnsd/sched.c

   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 }