add FILE argument to debug functions
[dpdk.git] / lib / librte_timer / rte_timer.c
1 /*-
2  *   BSD LICENSE
3  * 
4  *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
5  *   All rights reserved.
6  * 
7  *   Redistribution and use in source and binary forms, with or without
8  *   modification, are permitted provided that the following conditions
9  *   are met:
10  * 
11  *     * Redistributions of source code must retain the above copyright
12  *       notice, this list of conditions and the following disclaimer.
13  *     * Redistributions in binary form must reproduce the above copyright
14  *       notice, this list of conditions and the following disclaimer in
15  *       the documentation and/or other materials provided with the
16  *       distribution.
17  *     * Neither the name of Intel Corporation nor the names of its
18  *       contributors may be used to endorse or promote products derived
19  *       from this software without specific prior written permission.
20  * 
21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32  */
33
34 #include <string.h>
35 #include <stdio.h>
36 #include <stdint.h>
37 #include <inttypes.h>
38
39 #include <rte_atomic.h>
40 #include <rte_common.h>
41 #include <rte_cycles.h>
42 #include <rte_per_lcore.h>
43 #include <rte_memory.h>
44 #include <rte_memzone.h>
45 #include <rte_launch.h>
46 #include <rte_tailq.h>
47 #include <rte_eal.h>
48 #include <rte_per_lcore.h>
49 #include <rte_lcore.h>
50 #include <rte_branch_prediction.h>
51 #include <rte_spinlock.h>
52 #include <rte_random.h>
53
54 #include "rte_timer.h"
55
56 LIST_HEAD(rte_timer_list, rte_timer);
57
58 struct priv_timer {
59         struct rte_timer pending_head;  /**< dummy timer instance to head up list */
60         rte_spinlock_t list_lock;       /**< lock to protect list access */
61
62         /** per-core variable that true if a timer was updated on this
63          *  core since last reset of the variable */
64         int updated;
65
66         /** track the current depth of the skiplist */
67         unsigned curr_skiplist_depth;
68
69         unsigned prev_lcore;              /**< used for lcore round robin */
70
71 #ifdef RTE_LIBRTE_TIMER_DEBUG
72         /** per-lcore statistics */
73         struct rte_timer_debug_stats stats;
74 #endif
75 } __rte_cache_aligned;
76
77 /** per-lcore private info for timers */
78 static struct priv_timer priv_timer[RTE_MAX_LCORE];
79
80 /* when debug is enabled, store some statistics */
81 #ifdef RTE_LIBRTE_TIMER_DEBUG
82 #define __TIMER_STAT_ADD(name, n) do {                          \
83                 unsigned __lcore_id = rte_lcore_id();           \
84                 priv_timer[__lcore_id].stats.name += (n);       \
85         } while(0)
86 #else
87 #define __TIMER_STAT_ADD(name, n) do {} while(0)
88 #endif
89
90 /* Init the timer library. */
91 void
92 rte_timer_subsystem_init(void)
93 {
94         unsigned lcore_id;
95
96         /* since priv_timer is static, it's zeroed by default, so only init some
97          * fields.
98          */
99         for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id ++) {
100                 rte_spinlock_init(&priv_timer[lcore_id].list_lock);
101                 priv_timer[lcore_id].prev_lcore = lcore_id;
102         }
103 }
104
105 /* Initialize the timer handle tim for use */
106 void
107 rte_timer_init(struct rte_timer *tim)
108 {
109         union rte_timer_status status;
110
111         status.state = RTE_TIMER_STOP;
112         status.owner = RTE_TIMER_NO_OWNER;
113         tim->status.u32 = status.u32;
114 }
115
116 /*
117  * if timer is pending or stopped (or running on the same core than
118  * us), mark timer as configuring, and on success return the previous
119  * status of the timer
120  */
121 static int
122 timer_set_config_state(struct rte_timer *tim,
123                        union rte_timer_status *ret_prev_status)
124 {
125         union rte_timer_status prev_status, status;
126         int success = 0;
127         unsigned lcore_id;
128
129         lcore_id = rte_lcore_id();
130
131         /* wait that the timer is in correct status before update,
132          * and mark it as being configured */
133         while (success == 0) {
134                 prev_status.u32 = tim->status.u32;
135
136                 /* timer is running on another core, exit */
137                 if (prev_status.state == RTE_TIMER_RUNNING &&
138                     (unsigned)prev_status.owner != lcore_id)
139                         return -1;
140
141                 /* timer is being configured on another core */
142                 if (prev_status.state == RTE_TIMER_CONFIG)
143                         return -1;
144
145                 /* here, we know that timer is stopped or pending,
146                  * mark it atomically as being configured */
147                 status.state = RTE_TIMER_CONFIG;
148                 status.owner = (int16_t)lcore_id;
149                 success = rte_atomic32_cmpset(&tim->status.u32,
150                                               prev_status.u32,
151                                               status.u32);
152         }
153
154         ret_prev_status->u32 = prev_status.u32;
155         return 0;
156 }
157
158 /*
159  * if timer is pending, mark timer as running
160  */
161 static int
162 timer_set_running_state(struct rte_timer *tim)
163 {
164         union rte_timer_status prev_status, status;
165         unsigned lcore_id = rte_lcore_id();
166         int success = 0;
167
168         /* wait that the timer is in correct status before update,
169          * and mark it as running */
170         while (success == 0) {
171                 prev_status.u32 = tim->status.u32;
172
173                 /* timer is not pending anymore */
174                 if (prev_status.state != RTE_TIMER_PENDING)
175                         return -1;
176
177                 /* here, we know that timer is stopped or pending,
178                  * mark it atomically as beeing configured */
179                 status.state = RTE_TIMER_RUNNING;
180                 status.owner = (int16_t)lcore_id;
181                 success = rte_atomic32_cmpset(&tim->status.u32,
182                                               prev_status.u32,
183                                               status.u32);
184         }
185
186         return 0;
187 }
188
189 /*
190  * Return a skiplist level for a new entry.
191  * This probabalistically gives a level with p=1/4 that an entry at level n
192  * will also appear at level n+1.
193  */
194 static uint32_t
195 timer_get_skiplist_level(unsigned curr_depth)
196 {
197 #ifdef RTE_LIBRTE_TIMER_DEBUG
198         static uint32_t i, count = 0;
199         static uint32_t levels[MAX_SKIPLIST_DEPTH] = {0};
200 #endif
201
202         /* probability value is 1/4, i.e. all at level 0, 1 in 4 is at level 1,
203          * 1 in 16 at level 2, 1 in 64 at level 3, etc. Calculated using lowest
204          * bit position of a (pseudo)random number.
205          */
206         uint32_t rand = rte_rand() & (UINT32_MAX - 1);
207         uint32_t level = rand == 0 ? MAX_SKIPLIST_DEPTH : (rte_bsf32(rand)-1) / 2;
208
209         /* limit the levels used to one above our current level, so we don't,
210          * for instance, have a level 0 and a level 7 without anything between
211          */
212         if (level > curr_depth)
213                 level = curr_depth;
214         if (level >= MAX_SKIPLIST_DEPTH)
215                 level = MAX_SKIPLIST_DEPTH-1;
216 #ifdef RTE_LIBRTE_TIMER_DEBUG
217         count ++;
218         levels[level]++;
219         if (count % 10000 == 0)
220                 for (i = 0; i < MAX_SKIPLIST_DEPTH; i++)
221                         printf("Level %u: %u\n", (unsigned)i, (unsigned)levels[i]);
222 #endif
223         return level;
224 }
225
226 /*
227  * For a given time value, get the entries at each level which
228  * are <= that time value.
229  */
230 static void
231 timer_get_prev_entries(uint64_t time_val, unsigned tim_lcore,
232                 struct rte_timer **prev)
233 {
234         unsigned lvl = priv_timer[tim_lcore].curr_skiplist_depth;
235         prev[lvl] = &priv_timer[tim_lcore].pending_head;
236         while(lvl != 0) {
237                 lvl--;
238                 prev[lvl] = prev[lvl+1];
239                 while (prev[lvl]->sl_next[lvl] &&
240                                 prev[lvl]->sl_next[lvl]->expire <= time_val)
241                         prev[lvl] = prev[lvl]->sl_next[lvl];
242         }
243 }
244
245 /*
246  * Given a timer node in the skiplist, find the previous entries for it at
247  * all skiplist levels.
248  */
249 static void
250 timer_get_prev_entries_for_node(struct rte_timer *tim, unsigned tim_lcore,
251                 struct rte_timer **prev)
252 {
253         int i;
254         /* to get a specific entry in the list, look for just lower than the time
255          * values, and then increment on each level individually if necessary
256          */
257         timer_get_prev_entries(tim->expire - 1, tim_lcore, prev);
258         for (i = priv_timer[tim_lcore].curr_skiplist_depth - 1; i >= 0; i--) {
259                 while (prev[i]->sl_next[i] != NULL &&
260                                 prev[i]->sl_next[i] != tim &&
261                                 prev[i]->sl_next[i]->expire <= tim->expire)
262                         prev[i] = prev[i]->sl_next[i];
263         }
264 }
265
266 /*
267  * add in list, lock if needed
268  * timer must be in config state
269  * timer must not be in a list
270  */
271 static void
272 timer_add(struct rte_timer *tim, unsigned tim_lcore, int local_is_locked)
273 {
274         unsigned lcore_id = rte_lcore_id();
275         unsigned lvl;
276         struct rte_timer *prev[MAX_SKIPLIST_DEPTH+1];
277
278         /* if timer needs to be scheduled on another core, we need to
279          * lock the list; if it is on local core, we need to lock if
280          * we are not called from rte_timer_manage() */
281         if (tim_lcore != lcore_id || !local_is_locked)
282                 rte_spinlock_lock(&priv_timer[tim_lcore].list_lock);
283
284         /* find where exactly this element goes in the list of elements
285          * for each depth. */
286         timer_get_prev_entries(tim->expire, tim_lcore, prev);
287
288         /* now assign it a new level and add at that level */
289         const unsigned tim_level = timer_get_skiplist_level(
290                         priv_timer[tim_lcore].curr_skiplist_depth);
291         if (tim_level == priv_timer[tim_lcore].curr_skiplist_depth)
292                 priv_timer[tim_lcore].curr_skiplist_depth++;
293
294         lvl = tim_level;
295         while (lvl > 0) {
296                 tim->sl_next[lvl] = prev[lvl]->sl_next[lvl];
297                 prev[lvl]->sl_next[lvl] = tim;
298                 lvl--;
299         }
300         tim->sl_next[0] = prev[0]->sl_next[0];
301         prev[0]->sl_next[0] = tim;
302
303         /* save the lowest list entry into the expire field of the dummy hdr
304          * NOTE: this is not atomic on 32-bit*/
305         priv_timer[tim_lcore].pending_head.expire = priv_timer[tim_lcore].\
306                         pending_head.sl_next[0]->expire;
307
308         if (tim_lcore != lcore_id || !local_is_locked)
309                 rte_spinlock_unlock(&priv_timer[tim_lcore].list_lock);
310 }
311
312 /*
313  * del from list, lock if needed
314  * timer must be in config state
315  * timer must be in a list
316  */
317 static void
318 timer_del(struct rte_timer *tim, union rte_timer_status prev_status,
319                 int local_is_locked)
320 {
321         unsigned lcore_id = rte_lcore_id();
322         unsigned prev_owner = prev_status.owner;
323         int i;
324         struct rte_timer *prev[MAX_SKIPLIST_DEPTH+1];
325
326         /* if timer needs is pending another core, we need to lock the
327          * list; if it is on local core, we need to lock if we are not
328          * called from rte_timer_manage() */
329         if (prev_owner != lcore_id || !local_is_locked)
330                 rte_spinlock_lock(&priv_timer[prev_owner].list_lock);
331
332         /* save the lowest list entry into the expire field of the dummy hdr.
333          * NOTE: this is not atomic on 32-bit */
334         if (tim == priv_timer[prev_owner].pending_head.sl_next[0])
335                 priv_timer[prev_owner].pending_head.expire =
336                                 ((tim->sl_next[0] == NULL) ? 0 : tim->sl_next[0]->expire);
337
338         /* adjust pointers from previous entries to point past this */
339         timer_get_prev_entries_for_node(tim, prev_owner, prev);
340         for (i = priv_timer[prev_owner].curr_skiplist_depth - 1; i >= 0; i--) {
341                 if (prev[i]->sl_next[i] == tim)
342                         prev[i]->sl_next[i] = tim->sl_next[i];
343         }
344
345         /* in case we deleted last entry at a level, adjust down max level */
346         for (i = priv_timer[prev_owner].curr_skiplist_depth - 1; i >= 0; i--)
347                 if (priv_timer[prev_owner].pending_head.sl_next[i] == NULL)
348                         priv_timer[prev_owner].curr_skiplist_depth --;
349                 else
350                         break;
351
352         if (prev_owner != lcore_id || !local_is_locked)
353                 rte_spinlock_unlock(&priv_timer[prev_owner].list_lock);
354 }
355
356 /* Reset and start the timer associated with the timer handle (private func) */
357 static int
358 __rte_timer_reset(struct rte_timer *tim, uint64_t expire,
359                   uint64_t period, unsigned tim_lcore,
360                   rte_timer_cb_t fct, void *arg,
361                   int local_is_locked)
362 {
363         union rte_timer_status prev_status, status;
364         int ret;
365         unsigned lcore_id = rte_lcore_id();
366
367         /* round robin for tim_lcore */
368         if (tim_lcore == (unsigned)LCORE_ID_ANY) {
369                 tim_lcore = rte_get_next_lcore(priv_timer[lcore_id].prev_lcore,
370                                                0, 1);
371                 priv_timer[lcore_id].prev_lcore = tim_lcore;
372         }
373
374         /* wait that the timer is in correct status before update,
375          * and mark it as being configured */
376         ret = timer_set_config_state(tim, &prev_status);
377         if (ret < 0)
378                 return -1;
379
380         __TIMER_STAT_ADD(reset, 1);
381         priv_timer[lcore_id].updated = 1;
382
383         /* remove it from list */
384         if (prev_status.state == RTE_TIMER_PENDING) {
385                 timer_del(tim, prev_status, local_is_locked);
386                 __TIMER_STAT_ADD(pending, -1);
387         }
388
389         tim->period = period;
390         tim->expire = expire;
391         tim->f = fct;
392         tim->arg = arg;
393
394         __TIMER_STAT_ADD(pending, 1);
395         timer_add(tim, tim_lcore, local_is_locked);
396
397         /* update state: as we are in CONFIG state, only us can modify
398          * the state so we don't need to use cmpset() here */
399         rte_wmb();
400         status.state = RTE_TIMER_PENDING;
401         status.owner = (int16_t)tim_lcore;
402         tim->status.u32 = status.u32;
403
404         return 0;
405 }
406
407 /* Reset and start the timer associated with the timer handle tim */
408 int
409 rte_timer_reset(struct rte_timer *tim, uint64_t ticks,
410                 enum rte_timer_type type, unsigned tim_lcore,
411                 rte_timer_cb_t fct, void *arg)
412 {
413         uint64_t cur_time = rte_get_timer_cycles();
414         uint64_t period;
415
416         if (unlikely((tim_lcore != (unsigned)LCORE_ID_ANY) &&
417                         !rte_lcore_is_enabled(tim_lcore)))
418                 return -1;
419
420         if (type == PERIODICAL)
421                 period = ticks;
422         else
423                 period = 0;
424
425         __rte_timer_reset(tim,  cur_time + ticks, period, tim_lcore,
426                           fct, arg, 0);
427
428         return 0;
429 }
430
431 /* loop until rte_timer_reset() succeed */
432 void
433 rte_timer_reset_sync(struct rte_timer *tim, uint64_t ticks,
434                      enum rte_timer_type type, unsigned tim_lcore,
435                      rte_timer_cb_t fct, void *arg)
436 {
437         while (rte_timer_reset(tim, ticks, type, tim_lcore,
438                                fct, arg) != 0);
439 }
440
441 /* Stop the timer associated with the timer handle tim */
442 int
443 rte_timer_stop(struct rte_timer *tim)
444 {
445         union rte_timer_status prev_status, status;
446         unsigned lcore_id = rte_lcore_id();
447         int ret;
448
449         /* wait that the timer is in correct status before update,
450          * and mark it as being configured */
451         ret = timer_set_config_state(tim, &prev_status);
452         if (ret < 0)
453                 return -1;
454
455         __TIMER_STAT_ADD(stop, 1);
456         priv_timer[lcore_id].updated = 1;
457
458         /* remove it from list */
459         if (prev_status.state == RTE_TIMER_PENDING) {
460                 timer_del(tim, prev_status, 0);
461                 __TIMER_STAT_ADD(pending, -1);
462         }
463
464         /* mark timer as stopped */
465         rte_wmb();
466         status.state = RTE_TIMER_STOP;
467         status.owner = RTE_TIMER_NO_OWNER;
468         tim->status.u32 = status.u32;
469
470         return 0;
471 }
472
473 /* loop until rte_timer_stop() succeed */
474 void
475 rte_timer_stop_sync(struct rte_timer *tim)
476 {
477         while (rte_timer_stop(tim) != 0)
478                 rte_pause();
479 }
480
481 /* Test the PENDING status of the timer handle tim */
482 int
483 rte_timer_pending(struct rte_timer *tim)
484 {
485         return tim->status.state == RTE_TIMER_PENDING;
486 }
487
488 /* must be called periodically, run all timer that expired */
489 void rte_timer_manage(void)
490 {
491         union rte_timer_status status;
492         struct rte_timer *tim, *next_tim;
493         unsigned lcore_id = rte_lcore_id();
494         struct rte_timer *prev[MAX_SKIPLIST_DEPTH + 1];
495         uint64_t cur_time;
496         int i, ret;
497
498         __TIMER_STAT_ADD(manage, 1);
499         /* optimize for the case where per-cpu list is empty */
500         if (priv_timer[lcore_id].pending_head.sl_next[0] == NULL)
501                 return;
502         cur_time = rte_get_timer_cycles();
503
504 #ifdef RTE_ARCH_X86_64
505         /* on 64-bit the value cached in the pending_head.expired will be updated
506          * atomically, so we can consult that for a quick check here outside the
507          * lock */
508         if (likely(priv_timer[lcore_id].pending_head.expire > cur_time))
509                 return;
510 #endif
511
512         /* browse ordered list, add expired timers in 'expired' list */
513         rte_spinlock_lock(&priv_timer[lcore_id].list_lock);
514
515         /* if nothing to do just unlock and return */
516         if (priv_timer[lcore_id].pending_head.sl_next[0] == NULL ||
517                         priv_timer[lcore_id].pending_head.sl_next[0]->expire > cur_time)
518                 goto done;
519
520         /* save start of list of expired timers */
521         tim = priv_timer[lcore_id].pending_head.sl_next[0];
522
523         /* break the existing list at current time point */
524         timer_get_prev_entries(cur_time, lcore_id, prev);
525         for (i = priv_timer[lcore_id].curr_skiplist_depth -1; i >= 0; i--) {
526                 priv_timer[lcore_id].pending_head.sl_next[i] = prev[i]->sl_next[i];
527                 if (prev[i]->sl_next[i] == NULL)
528                         priv_timer[lcore_id].curr_skiplist_depth--;
529                 prev[i] ->sl_next[i] = NULL;
530         }
531
532         /* now scan expired list and call callbacks */
533         for ( ; tim != NULL; tim = next_tim) {
534                 next_tim = tim->sl_next[0];
535
536                 ret = timer_set_running_state(tim);
537
538                 /* this timer was not pending, continue */
539                 if (ret < 0)
540                         continue;
541
542                 rte_spinlock_unlock(&priv_timer[lcore_id].list_lock);
543
544                 priv_timer[lcore_id].updated = 0;
545
546                 /* execute callback function with list unlocked */
547                 tim->f(tim, tim->arg);
548
549                 rte_spinlock_lock(&priv_timer[lcore_id].list_lock);
550
551                 /* the timer was stopped or reloaded by the callback
552                  * function, we have nothing to do here */
553                 if (priv_timer[lcore_id].updated == 1)
554                         continue;
555
556                 if (tim->period == 0) {
557                         /* remove from done list and mark timer as stopped */
558                         __TIMER_STAT_ADD(pending, -1);
559                         status.state = RTE_TIMER_STOP;
560                         status.owner = RTE_TIMER_NO_OWNER;
561                         rte_wmb();
562                         tim->status.u32 = status.u32;
563                 }
564                 else {
565                         /* keep it in list and mark timer as pending */
566                         status.state = RTE_TIMER_PENDING;
567                         status.owner = (int16_t)lcore_id;
568                         rte_wmb();
569                         tim->status.u32 = status.u32;
570                         __rte_timer_reset(tim, cur_time + tim->period,
571                                         tim->period, lcore_id, tim->f, tim->arg, 1);
572                 }
573         }
574
575         /* update the next to expire timer value */
576         priv_timer[lcore_id].pending_head.expire =
577                         (priv_timer[lcore_id].pending_head.sl_next[0] == NULL) ? 0 :
578                                         priv_timer[lcore_id].pending_head.sl_next[0]->expire;
579 done:
580         /* job finished, unlock the list lock */
581         rte_spinlock_unlock(&priv_timer[lcore_id].list_lock);
582 }
583
584 /* dump statistics about timers */
585 void rte_timer_dump_stats(FILE *f)
586 {
587 #ifdef RTE_LIBRTE_TIMER_DEBUG
588         struct rte_timer_debug_stats sum;
589         unsigned lcore_id;
590
591         memset(&sum, 0, sizeof(sum));
592         for (lcore_id = 0; lcore_id < RTE_MAX_LCORE; lcore_id++) {
593                 sum.reset += priv_timer[lcore_id].stats.reset;
594                 sum.stop += priv_timer[lcore_id].stats.stop;
595                 sum.manage += priv_timer[lcore_id].stats.manage;
596                 sum.pending += priv_timer[lcore_id].stats.pending;
597         }
598         fprintf(f, "Timer statistics:\n");
599         fprintf(f, "  reset = %"PRIu64"\n", sum.reset);
600         fprintf(f, "  stop = %"PRIu64"\n", sum.stop);
601         fprintf(f, "  manage = %"PRIu64"\n", sum.manage);
602         fprintf(f, "  pending = %"PRIu64"\n", sum.pending);
603 #else
604         fprintf(f, "No timer statistics, RTE_LIBRTE_TIMER_DEBUG is disabled\n");
605 #endif
606 }