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
47 static cl_status_t
__event_will_age_before(IN const cl_list_item_t * const p_list_item,IN void * context)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
__cl_event_wheel_callback(IN void * context)63 static 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 */
183 Exit:
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 */
cl_event_wheel_construct(IN cl_event_wheel_t * const p_event_wheel)192 void 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
198 cl_status_t
cl_event_wheel_init(IN cl_event_wheel_t * const p_event_wheel)199 cl_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
218 cl_status_t
cl_event_wheel_init_ex(IN cl_event_wheel_t * const p_event_wheel,IN cl_spinlock_t * p_external_lock)219 cl_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
cl_event_wheel_dump(IN cl_event_wheel_t * const p_event_wheel)232 void 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
cl_event_wheel_destroy(IN cl_event_wheel_t * const p_event_wheel)250 void 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
288 cl_status_t
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)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)
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
398 Exit:
399 cl_spinlock_release(&p_event_wheel->lock);
400
401 return cl_status;
402 }
403
404 void
cl_event_wheel_unreg(IN cl_event_wheel_t * const p_event_wheel,IN uint64_t key)405 cl_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
440 uint32_t
cl_event_wheel_num_regs(IN cl_event_wheel_t * const p_event_wheel,IN uint64_t key)441 cl_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 */
__cl_event_wheel_dump(IN cl_event_wheel_t * const p_event_wheel)470 void __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 */
__test_event_aging(uint64_t key,void * context)513 void __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
main()519 int 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