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.
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:
12 * Redistribution and use in source and binary forms, with or
13 * without modification, are permitted provided that the following
16 * - Redistributions of source code must retain the above
17 * copyright notice, this list of conditions and the following
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.
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
38 #endif /* HAVE_CONFIG_H */
42 #include <complib/cl_event_wheel.h>
43 #include <complib/cl_debug.h>
45 #define CL_DBG(fmt, ...)
47 static cl_status_t __event_will_age_before(IN const cl_list_item_t *
48 const p_list_item, IN void *context)
50 uint64_t aging_time = *((uint64_t *) context);
51 cl_event_wheel_reg_info_t *p_event;
54 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t, list_item);
56 if (p_event->aging_time < aging_time)
62 static void __cl_event_wheel_callback(IN void *context)
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;
71 cl_status_t cl_status;
73 /* might be during closing ... */
74 if (p_event_wheel->closing)
77 current_time = cl_get_time_stamp();
79 if (NULL != p_event_wheel->p_external_lock)
81 /* Take care of the order of acquiring locks to avoid the deadlock!
82 * The external lock goes first.
84 cl_spinlock_acquire(p_event_wheel->p_external_lock);
86 cl_spinlock_acquire(&p_event_wheel->lock);
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 */
93 /* we found such an item. get the p_event */
95 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t, list_item);
97 while (p_event->aging_time <= current_time) {
98 /* this object has aged - invoke it's callback */
99 if (p_event->pfn_aged_callback)
101 p_event->pfn_aged_callback(p_event->key,
107 /* point to the next object in the wheel */
108 p_list_next_item = cl_qlist_next(p_list_item);
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));
116 /* pop p_event from the wheel */
117 cl_qlist_remove_head(&p_event_wheel->events_wheel);
119 /* delete the event info object - allocated by cl_event_wheel_reg */
122 /* update the required aging time */
123 p_event->aging_time = next_aging_time;
126 /* do not remove from the map - but remove from the list head and
127 place in the correct position */
129 /* pop p_event from the wheel */
130 cl_qlist_remove_head(&p_event_wheel->events_wheel);
132 /* find the event that ages just before */
133 p_prev_event_list_item =
134 cl_qlist_find_from_tail(&p_event_wheel->
136 __event_will_age_before,
137 &p_event->aging_time);
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);
144 /* as we have modified the list - restart from first item: */
146 cl_qlist_head(&p_event_wheel->events_wheel);
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 */
155 /* get the p_event */
157 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
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 */
165 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
168 /* start the timer to the timeout [msec] */
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");
180 /* release the lock */
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);
188 * Construct and Initialize
190 void cl_event_wheel_construct(IN cl_event_wheel_t * const p_event_wheel)
192 cl_spinlock_construct(&(p_event_wheel->lock));
193 cl_timer_construct(&(p_event_wheel->timer));
196 cl_status_t cl_event_wheel_init(IN cl_event_wheel_t * const p_event_wheel)
198 cl_status_t cl_status = CL_SUCCESS;
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)
206 cl_qlist_init(&p_event_wheel->events_wheel);
207 cl_qmap_init(&p_event_wheel->events_map);
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 */
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)
218 cl_status_t cl_status;
220 cl_status = cl_event_wheel_init(p_event_wheel);
221 if (CL_SUCCESS != cl_status)
224 p_event_wheel->p_external_lock = p_external_lock;
228 void cl_event_wheel_dump(IN cl_event_wheel_t * const p_event_wheel)
230 cl_list_item_t *p_list_item;
231 cl_event_wheel_reg_info_t __attribute__((__unused__)) *p_event;
233 p_list_item = cl_qlist_head(&p_event_wheel->events_wheel);
235 while (p_list_item != cl_qlist_end(&p_event_wheel->events_wheel)) {
237 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
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);
246 void cl_event_wheel_destroy(IN cl_event_wheel_t * const p_event_wheel)
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;
252 /* we need to get a lock */
253 cl_spinlock_acquire(&p_event_wheel->lock);
255 cl_event_wheel_dump(p_event_wheel);
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)) {
261 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
264 CL_DBG("cl_event_wheel_destroy: Found outstanding event"
265 " key:<0x%" PRIx64 ">\n", p_event->key);
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 */
272 cl_qlist_remove_head(&p_event_wheel->events_wheel);
275 /* destroy the timer */
276 cl_timer_destroy(&p_event_wheel->timer);
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));
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)
290 cl_event_wheel_reg_info_t *p_event;
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;
297 /* Get the lock on the manager */
298 cl_spinlock_acquire(&(p_event_wheel->lock));
300 cl_event_wheel_dump(p_event_wheel);
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%"
308 /* already there - remove it from the list as it is getting a new time */
310 PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
313 /* remove the item from the qlist */
314 cl_qlist_remove_item(&p_event_wheel->events_wheel,
315 &p_event->list_item);
317 cl_qmap_remove_item(&p_event_wheel->events_map,
321 p_event = (cl_event_wheel_reg_info_t *)
322 malloc(sizeof(cl_event_wheel_reg_info_t));
323 p_event->num_regs = 0;
327 p_event->aging_time = aging_time_usec;
328 p_event->pfn_aged_callback = pfn_callback;
329 p_event->context = context;
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));
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.
342 /* calculate the new timeout */
344 (p_event->aging_time - cl_get_time_stamp() + 500) / 1000;
346 /* stop the timer if it is running */
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.
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.
358 * cl_timer_stop(&p_event_wheel->timer);
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);
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");
379 /* insert the object to the qlist and the qmap */
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);
387 cl_qlist_insert_next(&p_event_wheel->events_wheel,
388 prev_event_list_item, &p_event->list_item);
390 cl_qmap_insert(&p_event_wheel->events_map, key, &(p_event->map_item));
393 cl_spinlock_release(&p_event_wheel->lock);
398 void cl_event_wheel_unreg(IN cl_event_wheel_t * const p_event_wheel,
401 cl_event_wheel_reg_info_t *p_event;
402 cl_map_item_t *p_map_item;
404 CL_DBG("cl_event_wheel_unreg: " "Removing key:0x%" PRIx64 "\n", key);
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. */
411 PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
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));
421 CL_DBG("cl_event_wheel_unreg: Removed key:0x%" PRIx64 "\n",
427 CL_DBG("cl_event_wheel_unreg: did not find key:0x%" PRIx64
431 cl_spinlock_release(&p_event_wheel->lock);
434 uint32_t cl_event_wheel_num_regs(IN cl_event_wheel_t * const p_event_wheel,
438 cl_event_wheel_reg_info_t *p_event;
439 cl_map_item_t *p_map_item;
440 uint32_t num_regs = 0;
442 /* try to find the key in the map */
443 CL_DBG("cl_event_wheel_num_regs: Looking for key:0x%" PRIx64 "\n", key);
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 */
450 PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
452 num_regs = p_event->num_regs;
455 cl_spinlock_release(&p_event_wheel->lock);
459 #ifdef __CL_EVENT_WHEEL_TEST__
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)
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;
468 printf("************** Event Wheel Dump ***********************\n");
469 printf("Event Wheel List has %u items:\n",
470 cl_qlist_count(&p_event_wheel->events_wheel));
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)) {
475 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
477 printf("Event key:0x%" PRIx64 " Context:%s NumRegs:%u\n",
478 p_event->key, (char *)p_event->context,
482 p_list_item = cl_qlist_next(p_list_item);
485 printf("Event Map has %u items:\n",
486 cl_qmap_count(&p_event_wheel->events_map));
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)) {
491 PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
493 printf("Event key:0x%" PRIx64 " Context:%s NumRegs:%u\n",
494 p_event->key, (char *)p_event->context,
498 p_map_item = cl_qmap_next(p_map_item);
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)
507 printf("*****************************************************\n");
508 printf("Aged key: 0x%" PRIx64 " Context:%s\n", key, (char *)context);
513 cl_event_wheel_t event_wheel;
520 cl_event_wheel_construct(&event_wheel);
523 cl_event_wheel_init(&event_wheel);
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");
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");
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");
541 __cl_event_wheel_dump(&event_wheel);
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");
549 __cl_event_wheel_dump(&event_wheel);
552 /* remove the third event */
553 cl_event_wheel_unreg(&event_wheel, 3); /* key */
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));
563 cl_event_wheel_destroy(&event_wheel);
570 #endif /* __CL_EVENT_WHEEL_TEST__ */