contrib/ofed/opensm/complib/cl_event_wheel.c

   1 /*
   2  * Copyright (c) 2004-2007 Voltaire, Inc. All rights reserved.
   3  * Copyright (c) 2002-2005 Mellanox Technologies LTD. All rights reserved.
   4  * Copyright (c) 1996-2003 Intel Corporation. All rights reserved.
   5  *
   6  * This software is available to you under a choice of one of two
   7  * licenses.  You may choose to be licensed under the terms of the GNU
   8  * General Public License (GPL) Version 2, available from the file
   9  * COPYING in the main directory of this source tree, or the
  10  * OpenIB.org BSD license below:
  11  *
  12  *     Redistribution and use in source and binary forms, with or
  13  *     without modification, are permitted provided that the following
  14  *     conditions are met:
  15  *
  16  *      - Redistributions of source code must retain the above
  17  *        copyright notice, this list of conditions and the following
  18  *        disclaimer.
  19  *
  20  *      - Redistributions in binary form must reproduce the above
  21  *        copyright notice, this list of conditions and the following
  22  *        disclaimer in the documentation and/or other materials
  23  *        provided with the distribution.
  24  *
  25  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  28  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  29  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  30  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  31  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  32  * SOFTWARE.
  33  *
  34  */
  35
  36 #if HAVE_CONFIG_H
  37 #  include <config.h>
  38 #endif                          /* HAVE_CONFIG_H */
  39
  40 #include <math.h>
  41 #include <stdlib.h>
  42 #include <complib/cl_event_wheel.h>
  43 #include <complib/cl_debug.h>
  44
  45 #define CL_DBG(fmt, ...)
  46
  47 static cl_status_t __event_will_age_before(IN const cl_list_item_t *
  48                                            const p_list_item, IN void *context)
  49 {
  50         uint64_t aging_time = *((uint64_t *) context);
  51         cl_event_wheel_reg_info_t *p_event;
  52
  53         p_event =
  54             PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t, list_item);
  55
  56         if (p_event->aging_time < aging_time)
  57                 return CL_SUCCESS;
  58         else
  59                 return CL_NOT_FOUND;
  60 }
  61
  62 static void __cl_event_wheel_callback(IN void *context)
  63 {
  64         cl_event_wheel_t *p_event_wheel = (cl_event_wheel_t *) context;
  65         cl_list_item_t *p_list_item, *p_prev_event_list_item;
  66         cl_list_item_t *p_list_next_item;
  67         cl_event_wheel_reg_info_t *p_event;
  68         uint64_t current_time;
  69         uint64_t next_aging_time;
  70         uint32_t new_timeout;
  71         cl_status_t cl_status;
  72
  73         /* might be during closing ...  */
  74         if (p_event_wheel->closing)
  75                 return;
  76
  77         current_time = cl_get_time_stamp();
  78
  79         if (NULL != p_event_wheel->p_external_lock)
  80
  81                 /* Take care of the order of acquiring locks to avoid the deadlock!
  82                  * The external lock goes first.
  83                  */
  84                 cl_spinlock_acquire(p_event_wheel->p_external_lock);
  85
  86         cl_spinlock_acquire(&p_event_wheel->lock);
  87
  88         p_list_item = cl_qlist_head(&p_event_wheel->events_wheel);
  89         if (p_list_item == cl_qlist_end(&p_event_wheel->events_wheel))
  90                 /* the list is empty - nothing to do */
  91                 goto Exit;
  92
  93         /* we found such an item.  get the p_event */
  94         p_event =
  95             PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t, list_item);
  96
  97         while (p_event->aging_time <= current_time) {
  98                 /* this object has aged - invoke it's callback */
  99                 if (p_event->pfn_aged_callback)
 100                         next_aging_time =
 101                             p_event->pfn_aged_callback(p_event->key,
 102                                                        p_event->num_regs,
 103                                                        p_event->context);
 104                 else
 105                         next_aging_time = 0;
 106
 107                 /* point to the next object in the wheel */
 108                 p_list_next_item = cl_qlist_next(p_list_item);
 109
 110                 /* We need to retire the event if the next aging time passed */
 111                 if (next_aging_time < current_time) {
 112                         /* remove it from the map */
 113                         cl_qmap_remove_item(&p_event_wheel->events_map,
 114                                             &(p_event->map_item));
 115
 116                         /* pop p_event from the wheel */
 117                         cl_qlist_remove_head(&p_event_wheel->events_wheel);
 118
 119                         /* delete the event info object - allocated by cl_event_wheel_reg */
 120                         free(p_event);
 121                 } else {
 122                         /* update the required aging time */
 123                         p_event->aging_time = next_aging_time;
 124                         p_event->num_regs++;
 125
 126                         /* do not remove from the map  - but remove from the list head and
 127                            place in the correct position */
 128
 129                         /* pop p_event from the wheel */
 130                         cl_qlist_remove_head(&p_event_wheel->events_wheel);
 131
 132                         /* find the event that ages just before */
 133                         p_prev_event_list_item =
 134                             cl_qlist_find_from_tail(&p_event_wheel->
 135                                                     events_wheel,
 136                                                     __event_will_age_before,
 137                                                     &p_event->aging_time);
 138
 139                         /* insert just after */
 140                         cl_qlist_insert_next(&p_event_wheel->events_wheel,
 141                                              p_prev_event_list_item,
 142                                              &p_event->list_item);
 143
 144                         /* as we have modified the list - restart from first item: */
 145                         p_list_next_item =
 146                             cl_qlist_head(&p_event_wheel->events_wheel);
 147                 }
 148
 149                 /* advance to next event */
 150                 p_list_item = p_list_next_item;
 151                 if (p_list_item == cl_qlist_end(&p_event_wheel->events_wheel))
 152                         /* the list is empty - nothing to do */
 153                         break;
 154
 155                 /* get the p_event */
 156                 p_event =
 157                     PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
 158                                   list_item);
 159         }
 160
 161         /* We need to restart the timer only if the list is not empty now */
 162         if (p_list_item != cl_qlist_end(&p_event_wheel->events_wheel)) {
 163                 /* get the p_event */
 164                 p_event =
 165                     PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
 166                                   list_item);
 167
 168                 /* start the timer to the timeout [msec] */
 169                 new_timeout =
 170                     (uint32_t) ((p_event->aging_time - current_time + 500) / 1000);
 171                 CL_DBG("__cl_event_wheel_callback: Restart timer in: "
 172                        "%u [msec]\n", new_timeout);
 173                 cl_status = cl_timer_start(&p_event_wheel->timer, new_timeout);
 174                 if (cl_status != CL_SUCCESS) {
 175                         CL_DBG("__cl_event_wheel_callback : ERR 6200: "
 176                                "Failed to start timer\n");
 177                 }
 178         }
 179
 180         /* release the lock */
 181 Exit:
 182         cl_spinlock_release(&p_event_wheel->lock);
 183         if (NULL != p_event_wheel->p_external_lock)
 184                 cl_spinlock_release(p_event_wheel->p_external_lock);
 185 }
 186
 187 /*
 188  * Construct and Initialize
 189  */
 190 void cl_event_wheel_construct(IN cl_event_wheel_t * const p_event_wheel)
 191 {
 192         cl_spinlock_construct(&(p_event_wheel->lock));
 193         cl_timer_construct(&(p_event_wheel->timer));
 194 }
 195
 196 cl_status_t cl_event_wheel_init(IN cl_event_wheel_t * const p_event_wheel)
 197 {
 198         cl_status_t cl_status = CL_SUCCESS;
 199
 200         /* initialize */
 201         p_event_wheel->p_external_lock = NULL;
 202         p_event_wheel->closing = FALSE;
 203         cl_status = cl_spinlock_init(&(p_event_wheel->lock));
 204         if (cl_status != CL_SUCCESS)
 205                 return cl_status;
 206         cl_qlist_init(&p_event_wheel->events_wheel);
 207         cl_qmap_init(&p_event_wheel->events_map);
 208
 209         /* init the timer with timeout */
 210         cl_status = cl_timer_init(&p_event_wheel->timer, __cl_event_wheel_callback, p_event_wheel);     /* cb context */
 211
 212         return cl_status;
 213 }
 214
 215 cl_status_t cl_event_wheel_init_ex(IN cl_event_wheel_t * const p_event_wheel,
 216                                    IN cl_spinlock_t * p_external_lock)
 217 {
 218         cl_status_t cl_status;
 219
 220         cl_status = cl_event_wheel_init(p_event_wheel);
 221         if (CL_SUCCESS != cl_status)
 222                 return cl_status;
 223
 224         p_event_wheel->p_external_lock = p_external_lock;
 225         return cl_status;
 226 }
 227
 228 void cl_event_wheel_dump(IN cl_event_wheel_t * const p_event_wheel)
 229 {
 230         cl_list_item_t *p_list_item;
 231         cl_event_wheel_reg_info_t __attribute__((__unused__)) *p_event;
 232
 233         p_list_item = cl_qlist_head(&p_event_wheel->events_wheel);
 234
 235         while (p_list_item != cl_qlist_end(&p_event_wheel->events_wheel)) {
 236                 p_event =
 237                     PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
 238                                   list_item);
 239                 CL_DBG("cl_event_wheel_dump: Found event key:<0x%"
 240                        PRIx64 ">, num_regs:%d, aging time:%" PRIu64 "\n",
 241                        p_event->key, p_event->num_regs, p_event->aging_time);
 242                 p_list_item = cl_qlist_next(p_list_item);
 243         }
 244 }
 245
 246 void cl_event_wheel_destroy(IN cl_event_wheel_t * const p_event_wheel)
 247 {
 248         cl_list_item_t *p_list_item;
 249         cl_map_item_t *p_map_item;
 250         cl_event_wheel_reg_info_t *p_event;
 251
 252         /* we need to get a lock */
 253         cl_spinlock_acquire(&p_event_wheel->lock);
 254
 255         cl_event_wheel_dump(p_event_wheel);
 256
 257         /* go over all the items in the list and remove them */
 258         p_list_item = cl_qlist_remove_head(&p_event_wheel->events_wheel);
 259         while (p_list_item != cl_qlist_end(&p_event_wheel->events_wheel)) {
 260                 p_event =
 261                     PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
 262                                   list_item);
 263
 264                 CL_DBG("cl_event_wheel_destroy: Found outstanding event"
 265                        " key:<0x%" PRIx64 ">\n", p_event->key);
 266
 267                 /* remove it from the map */
 268                 p_map_item = &(p_event->map_item);
 269                 cl_qmap_remove_item(&p_event_wheel->events_map, p_map_item);
 270                 free(p_event);  /* allocated by cl_event_wheel_reg */
 271                 p_list_item =
 272                     cl_qlist_remove_head(&p_event_wheel->events_wheel);
 273         }
 274
 275         /* destroy the timer */
 276         cl_timer_destroy(&p_event_wheel->timer);
 277
 278         /* destroy the lock (this should be done without releasing - we don't want
 279            any other run to grab the lock at this point. */
 280         cl_spinlock_release(&p_event_wheel->lock);
 281         cl_spinlock_destroy(&(p_event_wheel->lock));
 282 }
 283
 284 cl_status_t cl_event_wheel_reg(IN cl_event_wheel_t * const p_event_wheel,
 285                                IN const uint64_t key,
 286                                IN const uint64_t aging_time_usec,
 287                                IN cl_pfn_event_aged_cb_t pfn_callback,
 288                                IN void *const context)
 289 {
 290         cl_event_wheel_reg_info_t *p_event;
 291         uint64_t timeout;
 292         uint32_t to;
 293         cl_status_t cl_status = CL_SUCCESS;
 294         cl_list_item_t *prev_event_list_item;
 295         cl_map_item_t *p_map_item;
 296
 297         /* Get the lock on the manager */
 298         cl_spinlock_acquire(&(p_event_wheel->lock));
 299
 300         cl_event_wheel_dump(p_event_wheel);
 301
 302         /* Make sure such a key does not exists */
 303         p_map_item = cl_qmap_get(&p_event_wheel->events_map, key);
 304         if (p_map_item != cl_qmap_end(&p_event_wheel->events_map)) {
 305                 CL_DBG("cl_event_wheel_reg: Already exists key:0x%"
 306                        PRIx64 "\n", key);
 307
 308                 /* already there - remove it from the list as it is getting a new time */
 309                 p_event =
 310                     PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
 311                                   map_item);
 312
 313                 /* remove the item from the qlist */
 314                 cl_qlist_remove_item(&p_event_wheel->events_wheel,
 315                                      &p_event->list_item);
 316                 /* and the qmap */
 317                 cl_qmap_remove_item(&p_event_wheel->events_map,
 318                                     &p_event->map_item);
 319         } else {
 320                 /* make a new one */
 321                 p_event = (cl_event_wheel_reg_info_t *)
 322                     malloc(sizeof(cl_event_wheel_reg_info_t));
 323                 p_event->num_regs = 0;
 324         }
 325
 326         p_event->key = key;
 327         p_event->aging_time = aging_time_usec;
 328         p_event->pfn_aged_callback = pfn_callback;
 329         p_event->context = context;
 330         p_event->num_regs++;
 331
 332         CL_DBG("cl_event_wheel_reg: Registering event key:0x%" PRIx64
 333                " aging in %u [msec]\n", p_event->key,
 334                (uint32_t) ((p_event->aging_time - cl_get_time_stamp()) / 1000));
 335
 336         /* If the list is empty - need to start the timer */
 337         if (cl_is_qlist_empty(&p_event_wheel->events_wheel)) {
 338                 /* Edward Bortnikov 03/29/2003
 339                  * ++TBD Consider moving the timer manipulation behind the list manipulation.
 340                  */
 341
 342                 /* calculate the new timeout */
 343                 timeout =
 344                     (p_event->aging_time - cl_get_time_stamp() + 500) / 1000;
 345
 346                 /* stop the timer if it is running */
 347
 348                 /* Edward Bortnikov 03/29/2003
 349                  * Don't call cl_timer_stop() because it spins forever.
 350                  * cl_timer_start() will invoke cl_timer_stop() by itself.
 351                  *
 352                  * The problematic scenario is when __cl_event_wheel_callback()
 353                  * is in race condition with this code. It sets timer.in_timer_cb
 354                  * to TRUE and then blocks on p_event_wheel->lock. Following this,
 355                  * the call to cl_timer_stop() hangs. Following this, the whole system
 356                  * enters into a deadlock.
 357                  *
 358                  * cl_timer_stop(&p_event_wheel->timer);
 359                  */
 360
 361                 /* The timeout for the cl_timer_start should be given as uint32_t.
 362                    if there is an overflow - warn about it. */
 363                 to = (uint32_t) timeout;
 364                 if (timeout > (uint32_t) timeout) {
 365                         to = 0xffffffff;        /* max 32 bit timer */
 366                         CL_DBG("cl_event_wheel_reg: timeout requested is "
 367                                "too large. Using timeout: %u\n", to);
 368                 }
 369
 370                 /* start the timer to the timeout [msec] */
 371                 cl_status = cl_timer_start(&p_event_wheel->timer, to);
 372                 if (cl_status != CL_SUCCESS) {
 373                         CL_DBG("cl_event_wheel_reg : ERR 6203: "
 374                                "Failed to start timer\n");
 375                         goto Exit;
 376                 }
 377         }
 378
 379         /* insert the object to the qlist and the qmap */
 380
 381         /* BUT WE MUST INSERT IT IN A SORTED MANNER */
 382         prev_event_list_item =
 383             cl_qlist_find_from_tail(&p_event_wheel->events_wheel,
 384                                     __event_will_age_before,
 385                                     &p_event->aging_time);
 386
 387         cl_qlist_insert_next(&p_event_wheel->events_wheel,
 388                              prev_event_list_item, &p_event->list_item);
 389
 390         cl_qmap_insert(&p_event_wheel->events_map, key, &(p_event->map_item));
 391
 392 Exit:
 393         cl_spinlock_release(&p_event_wheel->lock);
 394
 395         return cl_status;
 396 }
 397
 398 void cl_event_wheel_unreg(IN cl_event_wheel_t * const p_event_wheel,
 399                           IN uint64_t key)
 400 {
 401         cl_event_wheel_reg_info_t *p_event;
 402         cl_map_item_t *p_map_item;
 403
 404         CL_DBG("cl_event_wheel_unreg: " "Removing key:0x%" PRIx64 "\n", key);
 405
 406         cl_spinlock_acquire(&p_event_wheel->lock);
 407         p_map_item = cl_qmap_get(&p_event_wheel->events_map, key);
 408         if (p_map_item != cl_qmap_end(&p_event_wheel->events_map)) {
 409                 /* we found such an item. */
 410                 p_event =
 411                     PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
 412                                   map_item);
 413
 414                 /* remove the item from the qlist */
 415                 cl_qlist_remove_item(&p_event_wheel->events_wheel,
 416                                      &(p_event->list_item));
 417                 /* remove the item from the qmap */
 418                 cl_qmap_remove_item(&p_event_wheel->events_map,
 419                                     &(p_event->map_item));
 420
 421                 CL_DBG("cl_event_wheel_unreg: Removed key:0x%" PRIx64 "\n",
 422                        key);
 423
 424                 /* free the item */
 425                 free(p_event);
 426         } else {
 427                 CL_DBG("cl_event_wheel_unreg: did not find key:0x%" PRIx64
 428                        "\n", key);
 429         }
 430
 431         cl_spinlock_release(&p_event_wheel->lock);
 432 }
 433
 434 uint32_t cl_event_wheel_num_regs(IN cl_event_wheel_t * const p_event_wheel,
 435                                  IN uint64_t key)
 436 {
 437
 438         cl_event_wheel_reg_info_t *p_event;
 439         cl_map_item_t *p_map_item;
 440         uint32_t num_regs = 0;
 441
 442         /* try to find the key in the map */
 443         CL_DBG("cl_event_wheel_num_regs: Looking for key:0x%" PRIx64 "\n", key);
 444
 445         cl_spinlock_acquire(&p_event_wheel->lock);
 446         p_map_item = cl_qmap_get(&p_event_wheel->events_map, key);
 447         if (p_map_item != cl_qmap_end(&p_event_wheel->events_map)) {
 448                 /* ok so we can simply return it's num_regs */
 449                 p_event =
 450                     PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
 451                                   map_item);
 452                 num_regs = p_event->num_regs;
 453         }
 454
 455         cl_spinlock_release(&p_event_wheel->lock);
 456         return (num_regs);
 457 }
 458
 459 #ifdef __CL_EVENT_WHEEL_TEST__
 460
 461 /* Dump out the complete state of the event wheel */
 462 void __cl_event_wheel_dump(IN cl_event_wheel_t * const p_event_wheel)
 463 {
 464         cl_list_item_t *p_list_item;
 465         cl_map_item_t *p_map_item;
 466         cl_event_wheel_reg_info_t *p_event;
 467
 468         printf("************** Event Wheel Dump ***********************\n");
 469         printf("Event Wheel List has %u items:\n",
 470                cl_qlist_count(&p_event_wheel->events_wheel));
 471
 472         p_list_item = cl_qlist_head(&p_event_wheel->events_wheel);
 473         while (p_list_item != cl_qlist_end(&p_event_wheel->events_wheel)) {
 474                 p_event =
 475                     PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
 476                                   list_item);
 477                 printf("Event key:0x%" PRIx64 " Context:%s NumRegs:%u\n",
 478                        p_event->key, (char *)p_event->context,
 479                        p_event->num_regs);
 480
 481                 /* next */
 482                 p_list_item = cl_qlist_next(p_list_item);
 483         }
 484
 485         printf("Event Map has %u items:\n",
 486                cl_qmap_count(&p_event_wheel->events_map));
 487
 488         p_map_item = cl_qmap_head(&p_event_wheel->events_map);
 489         while (p_map_item != cl_qmap_end(&p_event_wheel->events_map)) {
 490                 p_event =
 491                     PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
 492                                   map_item);
 493                 printf("Event key:0x%" PRIx64 " Context:%s NumRegs:%u\n",
 494                        p_event->key, (char *)p_event->context,
 495                        p_event->num_regs);
 496
 497                 /* next */
 498                 p_map_item = cl_qmap_next(p_map_item);
 499         }
 500
 501 }
 502
 503 /* The callback for aging event */
 504 /* We assume we pass a text context */
 505 static uint64_t __test_event_aging(uint64_t key, uint32_t num_regs, void *context)
 506 {
 507         printf("*****************************************************\n");
 508         printf("Aged key: 0x%" PRIx64 " Context:%s\n", key, (char *)context);
 509 }
 510
 511 int main()
 512 {
 513         cl_event_wheel_t event_wheel;
 514         /*  uint64_t key; */
 515
 516         /* init complib */
 517         complib_init();
 518
 519         /* construct */
 520         cl_event_wheel_construct(&event_wheel);
 521
 522         /* init */
 523         cl_event_wheel_init(&event_wheel);
 524
 525         /* Start Playing */
 526         cl_event_wheel_reg(&event_wheel, 1,     /*  key */
 527                            cl_get_time_stamp() + 3000000,       /*  3 sec lifetime */
 528                            __test_event_aging,  /*  cb */
 529                            "The first Aging Event");
 530
 531         cl_event_wheel_reg(&event_wheel, 2,     /*  key */
 532                            cl_get_time_stamp() + 3000000,       /*  3 sec lifetime */
 533                            __test_event_aging,  /*  cb */
 534                            "The Second Aging Event");
 535
 536         cl_event_wheel_reg(&event_wheel, 3,     /*  key */
 537                            cl_get_time_stamp() + 3500000,       /*  3 sec lifetime */
 538                            __test_event_aging,  /*  cb */
 539                            "The Third Aging Event");
 540
 541         __cl_event_wheel_dump(&event_wheel);
 542
 543         sleep(2);
 544         cl_event_wheel_reg(&event_wheel, 2,     /*  key */
 545                            cl_get_time_stamp() + 8000000,       /*  3 sec lifetime */
 546                            __test_event_aging,  /*  cb */
 547                            "The Second Aging Event Moved");
 548
 549         __cl_event_wheel_dump(&event_wheel);
 550
 551         sleep(1);
 552         /* remove the third event */
 553         cl_event_wheel_unreg(&event_wheel, 3);  /*  key */
 554
 555         /* get the number of registrations for the keys */
 556         printf("Event 1 Registered: %u\n",
 557                cl_event_wheel_num_regs(&event_wheel, 1));
 558         printf("Event 2 Registered: %u\n",
 559                cl_event_wheel_num_regs(&event_wheel, 2));
 560
 561         sleep(5);
 562         /* destroy */
 563         cl_event_wheel_destroy(&event_wheel);
 564
 565         complib_exit();
 566
 567         return (0);
 568 }
 569
 570 #endif                          /* __CL_EVENT_WHEEL_TEST__ */