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 47static 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 63static 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 */ 183Exit: 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 */ 192void 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 198cl_status_t 199cl_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 218cl_status_t 219cl_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 232void 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 250void 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 288cl_status_t 289cl_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 398Exit: 399 cl_spinlock_release(&p_event_wheel->lock); 400 401 return cl_status; 402} 403 404void 405cl_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 440uint32_t 441cl_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 */ 470void __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 */ 513void __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 519int 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__ */ 574