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  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 
  26 #include <stdlib.h>
  27 #include <limits.h>
  28 #include <sys/time.h>
  29 #include <sys/types.h>
  30 #include <sys/sysmacros.h>
  31 #include <sys/stropts.h>  /* INFTIM */
  32 
  33 #include <libinetutil.h>
  34 #include "libinetutil_impl.h"
  35 
  36 static iu_timer_node_t  *pending_delete_chain = NULL;
  37 
  38 static void             destroy_timer(iu_tq_t *, iu_timer_node_t *);
  39 static iu_timer_id_t    get_timer_id(iu_tq_t *);
  40 static void             release_timer_id(iu_tq_t *, iu_timer_id_t);
  41 
  42 /*
  43  * iu_tq_create(): creates, initializes and returns a timer queue for use
  44  *
  45  *   input: void
  46  *  output: iu_tq_t *: the new timer queue
  47  */
  48 
  49 iu_tq_t *
  50 iu_tq_create(void)
  51 {
  52         return (calloc(1, sizeof (iu_tq_t)));
  53 }
  54 
  55 /*
  56  * iu_tq_destroy(): destroys an existing timer queue
  57  *
  58  *   input: iu_tq_t *: the timer queue to destroy
  59  *  output: void
  60  */
  61 
  62 void
  63 iu_tq_destroy(iu_tq_t *tq)
  64 {
  65         iu_timer_node_t *node, *next_node;
  66 
  67         for (node = tq->iutq_head; node != NULL; node = next_node) {
  68                 next_node = node->iutn_next;
  69                 destroy_timer(tq, node);
  70         }
  71 
  72         free(tq);
  73 }
  74 
  75 /*
  76  * insert_timer(): inserts a timer node into a tq's timer list
  77  *
  78  *   input: iu_tq_t *: the timer queue
  79  *          iu_timer_node_t *: the timer node to insert into the list
  80  *          uint64_t: the number of milliseconds before this timer fires
  81  *  output: void
  82  */
  83 
  84 static void
  85 insert_timer(iu_tq_t *tq, iu_timer_node_t *node, uint64_t msec)
  86 {
  87         iu_timer_node_t *after = NULL;
  88 
  89         /*
  90          * find the node to insert this new node "after".  we do this
  91          * instead of the more intuitive "insert before" because with
  92          * the insert before approach, a null `before' node pointer
  93          * is overloaded in meaning (it could be null because there
  94          * are no items in the list, or it could be null because this
  95          * is the last item on the list, which are very different cases).
  96          */
  97 
  98         node->iutn_abs_timeout = gethrtime() + (msec * (NANOSEC / MILLISEC));
  99 
 100         if (tq->iutq_head != NULL &&
 101             tq->iutq_head->iutn_abs_timeout < node->iutn_abs_timeout)
 102                 for (after = tq->iutq_head; after->iutn_next != NULL;
 103                     after = after->iutn_next)
 104                         if (after->iutn_next->iutn_abs_timeout >
 105                             node->iutn_abs_timeout)
 106                                 break;
 107 
 108         node->iutn_next = after ? after->iutn_next : tq->iutq_head;
 109         node->iutn_prev = after;
 110         if (after == NULL)
 111                 tq->iutq_head = node;
 112         else
 113                 after->iutn_next = node;
 114 
 115         if (node->iutn_next != NULL)
 116                 node->iutn_next->iutn_prev = node;
 117 }
 118 
 119 /*
 120  * remove_timer(): removes a timer node from the tq's timer list
 121  *
 122  *   input: iu_tq_t *: the timer queue
 123  *          iu_timer_node_t *: the timer node to remove from the list
 124  *  output: void
 125  */
 126 
 127 static void
 128 remove_timer(iu_tq_t *tq, iu_timer_node_t *node)
 129 {
 130         if (node->iutn_next != NULL)
 131                 node->iutn_next->iutn_prev = node->iutn_prev;
 132         if (node->iutn_prev != NULL)
 133                 node->iutn_prev->iutn_next = node->iutn_next;
 134         else
 135                 tq->iutq_head = node->iutn_next;
 136 }
 137 
 138 /*
 139  * destroy_timer(): destroy a timer node
 140  *
 141  *  input: iu_tq_t *: the timer queue the timer node is associated with
 142  *         iu_timer_node_t *: the node to free
 143  * output: void
 144  */
 145 
 146 static void
 147 destroy_timer(iu_tq_t *tq, iu_timer_node_t *node)
 148 {
 149         release_timer_id(tq, node->iutn_timer_id);
 150 
 151         /*
 152          * if we're in expire, don't delete the node yet, since it may
 153          * still be referencing it (through the expire_next pointers)
 154          */
 155 
 156         if (tq->iutq_in_expire) {
 157                 node->iutn_pending_delete++;
 158                 node->iutn_next = pending_delete_chain;
 159                 pending_delete_chain = node;
 160         } else
 161                 free(node);
 162 
 163 }
 164 
 165 /*
 166  * iu_schedule_timer(): creates and inserts a timer in the tq's timer list
 167  *
 168  *   input: iu_tq_t *: the timer queue
 169  *          uint32_t: the number of seconds before this timer fires
 170  *          iu_tq_callback_t *: the function to call when the timer fires
 171  *          void *: an argument to pass to the called back function
 172  *  output: iu_timer_id_t: the new timer's timer id on success, -1 on failure
 173  */
 174 
 175 iu_timer_id_t
 176 iu_schedule_timer(iu_tq_t *tq, uint32_t sec, iu_tq_callback_t *callback,
 177     void *arg)
 178 {
 179         return (iu_schedule_timer_ms(tq, sec * MILLISEC, callback, arg));
 180 }
 181 
 182 /*
 183  * iu_schedule_ms_timer(): creates and inserts a timer in the tq's timer list,
 184  *                         using millisecond granularity
 185  *
 186  *   input: iu_tq_t *: the timer queue
 187  *          uint64_t: the number of milliseconds before this timer fires
 188  *          iu_tq_callback_t *: the function to call when the timer fires
 189  *          void *: an argument to pass to the called back function
 190  *  output: iu_timer_id_t: the new timer's timer id on success, -1 on failure
 191  */
 192 iu_timer_id_t
 193 iu_schedule_timer_ms(iu_tq_t *tq, uint64_t ms, iu_tq_callback_t *callback,
 194     void *arg)
 195 {
 196         iu_timer_node_t *node = calloc(1, sizeof (iu_timer_node_t));
 197 
 198         if (node == NULL)
 199                 return (-1);
 200 
 201         node->iutn_callback  = callback;
 202         node->iutn_arg       = arg;
 203         node->iutn_timer_id  = get_timer_id(tq);
 204         if (node->iutn_timer_id == -1) {
 205                 free(node);
 206                 return (-1);
 207         }
 208 
 209         insert_timer(tq, node, ms);
 210 
 211         return (node->iutn_timer_id);
 212 }
 213 
 214 /*
 215  * iu_cancel_timer(): cancels a pending timer from a timer queue's timer list
 216  *
 217  *   input: iu_tq_t *: the timer queue
 218  *          iu_timer_id_t: the timer id returned from iu_schedule_timer
 219  *          void **: if non-NULL, a place to return the argument passed to
 220  *                   iu_schedule_timer
 221  *  output: int: 1 on success, 0 on failure
 222  */
 223 
 224 int
 225 iu_cancel_timer(iu_tq_t *tq, iu_timer_id_t timer_id, void **arg)
 226 {
 227         iu_timer_node_t *node;
 228 
 229         if (timer_id == -1)
 230                 return (0);
 231 
 232         for (node = tq->iutq_head; node != NULL; node = node->iutn_next) {
 233                 if (node->iutn_timer_id == timer_id) {
 234                         if (arg != NULL)
 235                                 *arg = node->iutn_arg;
 236                         remove_timer(tq, node);
 237                         destroy_timer(tq, node);
 238                         return (1);
 239                 }
 240         }
 241         return (0);
 242 }
 243 
 244 /*
 245  * iu_adjust_timer(): adjusts the fire time of a timer in the tq's timer list
 246  *
 247  *   input: iu_tq_t *: the timer queue
 248  *          iu_timer_id_t: the timer id returned from iu_schedule_timer
 249  *          uint32_t: the number of seconds before this timer fires
 250  *  output: int: 1 on success, 0 on failure
 251  */
 252 
 253 int
 254 iu_adjust_timer(iu_tq_t *tq, iu_timer_id_t timer_id, uint32_t sec)
 255 {
 256         iu_timer_node_t *node;
 257 
 258         if (timer_id == -1)
 259                 return (0);
 260 
 261         for (node = tq->iutq_head; node != NULL; node = node->iutn_next) {
 262                 if (node->iutn_timer_id == timer_id) {
 263                         remove_timer(tq, node);
 264                         insert_timer(tq, node, sec * MILLISEC);
 265                         return (1);
 266                 }
 267         }
 268         return (0);
 269 }
 270 
 271 /*
 272  * iu_earliest_timer(): returns the time until the next timer fires on a tq
 273  *
 274  *   input: iu_tq_t *: the timer queue
 275  *  output: int: the number of milliseconds until the next timer (up to
 276  *          a maximum value of INT_MAX), or INFTIM if no timers are pending.
 277  */
 278 
 279 int
 280 iu_earliest_timer(iu_tq_t *tq)
 281 {
 282         unsigned long long      timeout_interval;
 283         hrtime_t                current_time = gethrtime();
 284 
 285         if (tq->iutq_head == NULL)
 286                 return (INFTIM);
 287 
 288         /*
 289          * event might've already happened if we haven't gotten a chance to
 290          * run in a while; return zero and pretend it just expired.
 291          */
 292 
 293         if (tq->iutq_head->iutn_abs_timeout <= current_time)
 294                 return (0);
 295 
 296         /*
 297          * since the timers are ordered in absolute time-to-fire, just
 298          * subtract from the head of the list.
 299          */
 300 
 301         timeout_interval =
 302             (tq->iutq_head->iutn_abs_timeout - current_time) / 1000000;
 303 
 304         return (MIN(timeout_interval, INT_MAX));
 305 }
 306 
 307 /*
 308  * iu_expire_timers(): expires all pending timers on a given timer queue
 309  *
 310  *   input: iu_tq_t *: the timer queue
 311  *  output: int: the number of timers expired
 312  */
 313 
 314 int
 315 iu_expire_timers(iu_tq_t *tq)
 316 {
 317         iu_timer_node_t *node, *next_node;
 318         int             n_expired = 0;
 319         hrtime_t        current_time = gethrtime();
 320 
 321         /*
 322          * in_expire is in the iu_tq_t instead of being passed through as
 323          * an argument to remove_timer() below since the callback
 324          * function may call iu_cancel_timer() itself as well.
 325          */
 326 
 327         tq->iutq_in_expire++;
 328 
 329         /*
 330          * this function builds another linked list of timer nodes
 331          * through `expire_next' because the normal linked list
 332          * may be changed as a result of callbacks canceling and
 333          * scheduling timeouts, and thus can't be trusted.
 334          */
 335 
 336         for (node = tq->iutq_head; node != NULL; node = node->iutn_next)
 337                 node->iutn_expire_next = node->iutn_next;
 338 
 339         for (node = tq->iutq_head; node != NULL;
 340             node = node->iutn_expire_next) {
 341 
 342                 /*
 343                  * If the timeout is within 1 millisec of current time,
 344                  * consider it as expired already.  We do this because
 345                  * iu_earliest_timer() only has millisec granularity.
 346                  * So we should also use millisec grandularity in
 347                  * comparing timeout values.
 348                  */
 349                 if (node->iutn_abs_timeout - current_time > 1000000)
 350                         break;
 351 
 352                 /*
 353                  * fringe condition: two timers fire at the "same
 354                  * time" (i.e., they're both scheduled called back in
 355                  * this loop) and one cancels the other.  in this
 356                  * case, the timer which has already been "cancelled"
 357                  * should not be called back.
 358                  */
 359 
 360                 if (node->iutn_pending_delete)
 361                         continue;
 362 
 363                 /*
 364                  * we remove the timer before calling back the callback
 365                  * so that a callback which accidentally tries to cancel
 366                  * itself (through whatever means) doesn't succeed.
 367                  */
 368 
 369                 n_expired++;
 370                 remove_timer(tq, node);
 371                 destroy_timer(tq, node);
 372                 node->iutn_callback(tq, node->iutn_arg);
 373         }
 374 
 375         tq->iutq_in_expire--;
 376 
 377         /*
 378          * any cancels that took place whilst we were expiring timeouts
 379          * ended up on the `pending_delete_chain'.  delete them now
 380          * that it's safe.
 381          */
 382 
 383         for (node = pending_delete_chain; node != NULL; node = next_node) {
 384                 next_node = node->iutn_next;
 385                 free(node);
 386         }
 387         pending_delete_chain = NULL;
 388 
 389         return (n_expired);
 390 }
 391 
 392 /*
 393  * get_timer_id(): allocates a timer id from the pool
 394  *
 395  *   input: iu_tq_t *: the timer queue
 396  *  output: iu_timer_id_t: the allocated timer id, or -1 if none available
 397  */
 398 
 399 static iu_timer_id_t
 400 get_timer_id(iu_tq_t *tq)
 401 {
 402         unsigned int    map_index;
 403         unsigned char   map_bit;
 404         boolean_t       have_wrapped = B_FALSE;
 405 
 406         for (; ; tq->iutq_next_timer_id++) {
 407 
 408                 if (tq->iutq_next_timer_id >= IU_TIMER_ID_MAX) {
 409                         if (have_wrapped)
 410                                 return (-1);
 411 
 412                         have_wrapped = B_TRUE;
 413                         tq->iutq_next_timer_id = 0;
 414                 }
 415 
 416                 map_index = tq->iutq_next_timer_id / CHAR_BIT;
 417                 map_bit   = tq->iutq_next_timer_id % CHAR_BIT;
 418 
 419                 if ((tq->iutq_timer_id_map[map_index] & (1 << map_bit)) == 0)
 420                         break;
 421         }
 422 
 423         tq->iutq_timer_id_map[map_index] |= (1 << map_bit);
 424         return (tq->iutq_next_timer_id++);
 425 }
 426 
 427 /*
 428  * release_timer_id(): releases a timer id back into the pool
 429  *
 430  *   input: iu_tq_t *: the timer queue
 431  *          iu_timer_id_t: the timer id to release
 432  *  output: void
 433  */
 434 
 435 static void
 436 release_timer_id(iu_tq_t *tq, iu_timer_id_t timer_id)
 437 {
 438         unsigned int    map_index = timer_id / CHAR_BIT;
 439         unsigned char   map_bit   = timer_id % CHAR_BIT;
 440 
 441         tq->iutq_timer_id_map[map_index] &= ~(1 << map_bit);
 442 }