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