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, arg...)
48 __event_will_age_before(IN const cl_list_item_t * const p_list_item,
51 uint64_t aging_time = *((uint64_t *) context);
52 cl_event_wheel_reg_info_t *p_event;
55 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t, list_item);
57 if (p_event->aging_time < aging_time)
63 static void __cl_event_wheel_callback(IN void *context)
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;
72 cl_status_t cl_status;
74 /* might be during closing ... */
75 if (p_event_wheel->closing)
78 current_time = cl_get_time_stamp();
80 if (NULL != p_event_wheel->p_external_lock)
82 /* Take care of the order of acquiring locks to avoid the deadlock!
83 * The external lock goes first.
85 cl_spinlock_acquire(p_event_wheel->p_external_lock);
87 cl_spinlock_acquire(&p_event_wheel->lock);
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 */
94 /* we found such an item. get the p_event */
96 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t, list_item);
98 while (p_event->aging_time <= current_time) {
99 /* this object has aged - invoke it's callback */
100 if (p_event->pfn_aged_callback)
102 p_event->pfn_aged_callback(p_event->key,
108 /* point to the next object in the wheel */
109 p_list_next_item = cl_qlist_next(p_list_item);
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));
117 /* pop p_event from the wheel */
118 cl_qlist_remove_head(&p_event_wheel->events_wheel);
120 /* delete the event info object - allocated by cl_event_wheel_reg */
123 /* update the required aging time */
124 p_event->aging_time = next_aging_time;
127 /* do not remove from the map - but remove from the list head and
128 place in the correct position */
130 /* pop p_event from the wheel */
131 cl_qlist_remove_head(&p_event_wheel->events_wheel);
133 /* find the event that ages just before */
134 p_prev_event_list_item =
135 cl_qlist_find_from_tail(&p_event_wheel->
137 __event_will_age_before,
138 &p_event->aging_time);
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);
145 /* as we have modified the list - restart from first item: */
147 cl_qlist_head(&p_event_wheel->events_wheel);
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 */
156 /* get the p_event */
158 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
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 */
166 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
169 /* start the timer to the timeout [msec] */
171 (uint32_t) (((p_event->aging_time - current_time) / 1000) +
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");
182 /* release the lock */
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);
190 * Construct and Initialize
192 void cl_event_wheel_construct(IN cl_event_wheel_t * const p_event_wheel)
194 cl_spinlock_construct(&(p_event_wheel->lock));
195 cl_timer_construct(&(p_event_wheel->timer));
199 cl_event_wheel_init(IN cl_event_wheel_t * const p_event_wheel)
201 cl_status_t cl_status = CL_SUCCESS;
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)
209 cl_qlist_init(&p_event_wheel->events_wheel);
210 cl_qmap_init(&p_event_wheel->events_map);
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 */
219 cl_event_wheel_init_ex(IN cl_event_wheel_t * const p_event_wheel,
220 IN cl_spinlock_t * p_external_lock)
222 cl_status_t cl_status;
224 cl_status = cl_event_wheel_init(p_event_wheel);
225 if (CL_SUCCESS != cl_status)
228 p_event_wheel->p_external_lock = p_external_lock;
232 void cl_event_wheel_dump(IN cl_event_wheel_t * const p_event_wheel)
234 cl_list_item_t *p_list_item;
235 cl_event_wheel_reg_info_t *p_event;
237 p_list_item = cl_qlist_head(&p_event_wheel->events_wheel);
239 while (p_list_item != cl_qlist_end(&p_event_wheel->events_wheel)) {
241 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
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);
250 void cl_event_wheel_destroy(IN cl_event_wheel_t * const p_event_wheel)
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;
256 /* we need to get a lock */
257 cl_spinlock_acquire(&p_event_wheel->lock);
259 cl_event_wheel_dump(p_event_wheel);
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)) {
265 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
268 CL_DBG("cl_event_wheel_destroy: Found outstanding event"
269 " key:<0x%" PRIx64 ">\n", p_event->key);
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 */
276 cl_qlist_remove_head(&p_event_wheel->events_wheel);
279 /* destroy the timer */
280 cl_timer_destroy(&p_event_wheel->timer);
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));
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)
295 cl_event_wheel_reg_info_t *p_event;
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;
302 /* Get the lock on the manager */
303 cl_spinlock_acquire(&(p_event_wheel->lock));
305 cl_event_wheel_dump(p_event_wheel);
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%"
313 /* already there - remove it from the list as it is getting a new time */
315 PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
318 /* remove the item from the qlist */
319 cl_qlist_remove_item(&p_event_wheel->events_wheel,
320 &p_event->list_item);
322 cl_qmap_remove_item(&p_event_wheel->events_map,
326 p_event = (cl_event_wheel_reg_info_t *)
327 malloc(sizeof(cl_event_wheel_reg_info_t));
328 p_event->num_regs = 0;
332 p_event->aging_time = aging_time_usec;
333 p_event->pfn_aged_callback = pfn_callback;
334 p_event->context = context;
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));
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.
348 /* calculate the new timeout */
350 (p_event->aging_time - cl_get_time_stamp() + 500) / 1000;
352 /* stop the timer if it is running */
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.
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.
364 * cl_timer_stop(&p_event_wheel->timer);
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);
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");
385 /* insert the object to the qlist and the qmap */
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);
393 cl_qlist_insert_next(&p_event_wheel->events_wheel,
394 prev_event_list_item, &p_event->list_item);
396 cl_qmap_insert(&p_event_wheel->events_map, key, &(p_event->map_item));
399 cl_spinlock_release(&p_event_wheel->lock);
405 cl_event_wheel_unreg(IN cl_event_wheel_t * const p_event_wheel, IN uint64_t key)
407 cl_event_wheel_reg_info_t *p_event;
408 cl_map_item_t *p_map_item;
410 CL_DBG("cl_event_wheel_unreg: " "Removing key:0x%" PRIx64 "\n", key);
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. */
417 PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
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));
427 CL_DBG("cl_event_wheel_unreg: Removed key:0x%" PRIx64 "\n",
433 CL_DBG("cl_event_wheel_unreg: did not find key:0x%" PRIx64
437 cl_spinlock_release(&p_event_wheel->lock);
441 cl_event_wheel_num_regs(IN cl_event_wheel_t * const p_event_wheel,
445 cl_event_wheel_reg_info_t *p_event;
446 cl_map_item_t *p_map_item;
447 uint32_t num_regs = 0;
449 /* try to find the key in the map */
450 CL_DBG("cl_event_wheel_num_regs: Looking for key:0x%"
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 */
458 PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
460 num_regs = p_event->num_regs;
463 cl_spinlock_release(&p_event_wheel->lock);
467 #ifdef __CL_EVENT_WHEEL_TEST__
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)
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;
476 printf("************** Event Wheel Dump ***********************\n");
477 printf("Event Wheel List has %u items:\n",
478 cl_qlist_count(&p_event_wheel->events_wheel));
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)) {
483 PARENT_STRUCT(p_list_item, cl_event_wheel_reg_info_t,
485 printf("Event key:0x%" PRIx64 " Context:%s NumRegs:%u\n",
486 p_event->key, (char *)p_event->context,
490 p_list_item = cl_qlist_next(p_list_item);
493 printf("Event Map has %u items:\n",
494 cl_qmap_count(&p_event_wheel->events_map));
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)) {
499 PARENT_STRUCT(p_map_item, cl_event_wheel_reg_info_t,
501 printf("Event key:0x%" PRIx64 " Context:%s NumRegs:%u\n",
502 p_event->key, (char *)p_event->context,
506 p_map_item = cl_qmap_next(p_map_item);
511 /* The callback for aging event */
512 /* We assume we pass a text context */
513 void __test_event_aging(uint64_t key, void *context)
515 printf("*****************************************************\n");
516 printf("Aged key: 0x%" PRIx64 " Context:%s\n", key, (char *)context);
521 cl_event_wheel_t event_wheel;
525 cl_event_wheel_construct(&event_wheel);
528 cl_event_wheel_init(&event_wheel);
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");
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");
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");
546 __cl_event_wheel_dump(&event_wheel);
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");
554 __cl_event_wheel_dump(&event_wheel);
557 /* remove the third event */
558 cl_event_wheel_unreg(&event_wheel, 3); /* key */
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));
568 cl_event_wheel_destroy(&event_wheel);
573 #endif /* __CL_EVENT_WHEEL_TEST__ */