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 47static 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 62static 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 */ 181Exit: 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 */ 190void 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 196cl_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 215cl_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 228void 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 246void 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 284cl_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 392Exit: 393 cl_spinlock_release(&p_event_wheel->lock); 394 395 return cl_status; 396} 397 398void 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 434uint32_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 */ 462void __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 */ 505static 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 511int 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__ */ 571