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
__event_will_age_before(IN const cl_list_item_t * const p_list_item,IN void * context)47 static 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
__cl_event_wheel_callback(IN void * context)62 static 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 */
181 Exit:
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 */
cl_event_wheel_construct(IN cl_event_wheel_t * const p_event_wheel)190 void 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
cl_event_wheel_init(IN cl_event_wheel_t * const p_event_wheel)196 cl_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
cl_event_wheel_init_ex(IN cl_event_wheel_t * const p_event_wheel,IN cl_spinlock_t * p_external_lock)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)
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
cl_event_wheel_dump(IN cl_event_wheel_t * const p_event_wheel)228 void 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
cl_event_wheel_destroy(IN cl_event_wheel_t * const p_event_wheel)246 void 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
cl_event_wheel_reg(IN cl_event_wheel_t * const p_event_wheel,IN const uint64_t key,IN const uint64_t aging_time_usec,IN cl_pfn_event_aged_cb_t pfn_callback,IN void * const context)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)
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
392 Exit:
393 cl_spinlock_release(&p_event_wheel->lock);
394
395 return cl_status;
396 }
397
cl_event_wheel_unreg(IN cl_event_wheel_t * const p_event_wheel,IN uint64_t key)398 void 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
cl_event_wheel_num_regs(IN cl_event_wheel_t * const p_event_wheel,IN uint64_t key)434 uint32_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 */
__cl_event_wheel_dump(IN cl_event_wheel_t * const p_event_wheel)462 void __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 */
__test_event_aging(uint64_t key,uint32_t num_regs,void * context)505 static 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
main()511 int 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