Line data    Source code

       1             : // SPDX-License-Identifier: GPL-2.0-or-later
       2             : /*
       3             :  * Timer Wheel
       4             :  * Copyright (C) 2016 Cumulus Networks, Inc.
       5             :  * Donald Sharp
       6             :  */
       7             : #include "zebra.h"
       8             : #include "linklist.h"
       9             : #include "frrevent.h"
      10             : #include "memory.h"
      11             : #include "wheel.h"
      12             : #include "log.h"
      13             : 
      14          12 : DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL, "Timer Wheel");
      15          12 : DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL_LIST, "Timer Wheel Slot List");
      16             : 
      17             : static int debug_timer_wheel = 0;
      18             : 
      19             : static void wheel_timer_thread(struct event *t);
      20             : 
      21           0 : static void wheel_timer_thread_helper(struct event *t)
      22             : {
      23           0 :         struct listnode *node, *nextnode;
      24           0 :         unsigned long long curr_slot;
      25           0 :         unsigned int slots_to_skip = 1;
      26           0 :         struct timer_wheel *wheel;
      27           0 :         void *data;
      28             : 
      29           0 :         wheel = EVENT_ARG(t);
      30             : 
      31           0 :         wheel->curr_slot += wheel->slots_to_skip;
      32             : 
      33           0 :         curr_slot = wheel->curr_slot % wheel->slots;
      34             : 
      35           0 :         if (debug_timer_wheel)
      36           0 :                 zlog_debug("%s: Wheel Slot: %lld(%lld) count: %d", __func__,
      37             :                            wheel->curr_slot, curr_slot,
      38             :                            listcount(wheel->wheel_slot_lists[curr_slot]));
      39             : 
      40           0 :         for (ALL_LIST_ELEMENTS(wheel->wheel_slot_lists[curr_slot], node,
      41             :                                nextnode, data))
      42           0 :                 (*wheel->slot_run)(data);
      43             : 
      44           0 :         while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip)
      45             :                                                     % wheel->slots])
      46           0 :                && (curr_slot + slots_to_skip) % wheel->slots != curr_slot)
      47           0 :                 slots_to_skip++;
      48             : 
      49           0 :         wheel->slots_to_skip = slots_to_skip;
      50           0 :         event_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
      51             :                              wheel->nexttime * slots_to_skip, &wheel->timer);
      52           0 : }
      53             : 
      54           0 : static void wheel_timer_thread(struct event *t)
      55             : {
      56           0 :         struct timer_wheel *wheel;
      57             : 
      58           0 :         wheel = EVENT_ARG(t);
      59             : 
      60           0 :         event_execute(wheel->master, wheel_timer_thread_helper, wheel, 0, NULL);
      61           0 : }
      62             : 
      63           0 : struct timer_wheel *wheel_init(struct event_loop *master, int period,
      64             :                                size_t slots,
      65             :                                unsigned int (*slot_key)(const void *),
      66             :                                void (*slot_run)(void *), const char *run_name)
      67             : {
      68           0 :         struct timer_wheel *wheel;
      69           0 :         size_t i;
      70             : 
      71           0 :         wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof(struct timer_wheel));
      72             : 
      73           0 :         wheel->name = XSTRDUP(MTYPE_TIMER_WHEEL, run_name);
      74           0 :         wheel->slot_key = slot_key;
      75           0 :         wheel->slot_run = slot_run;
      76             : 
      77           0 :         wheel->period = period;
      78           0 :         wheel->slots = slots;
      79           0 :         wheel->curr_slot = 0;
      80           0 :         wheel->master = master;
      81           0 :         wheel->nexttime = period / slots;
      82             : 
      83           0 :         wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
      84             :                                           slots * sizeof(struct list *));
      85           0 :         for (i = 0; i < slots; i++)
      86           0 :                 wheel->wheel_slot_lists[i] = list_new();
      87             : 
      88           0 :         event_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
      89             :                              wheel->nexttime, &wheel->timer);
      90             : 
      91           0 :         return wheel;
      92             : }
      93             : 
      94           0 : void wheel_delete(struct timer_wheel *wheel)
      95             : {
      96           0 :         int i;
      97             : 
      98           0 :         for (i = 0; i < wheel->slots; i++) {
      99           0 :                 list_delete(&wheel->wheel_slot_lists[i]);
     100             :         }
     101             : 
     102           0 :         EVENT_OFF(wheel->timer);
     103           0 :         XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
     104           0 :         XFREE(MTYPE_TIMER_WHEEL, wheel->name);
     105           0 :         XFREE(MTYPE_TIMER_WHEEL, wheel);
     106           0 : }
     107             : 
     108           0 : int wheel_add_item(struct timer_wheel *wheel, void *item)
     109             : {
     110           0 :         long long slot;
     111             : 
     112           0 :         slot = (*wheel->slot_key)(item);
     113             : 
     114           0 :         if (debug_timer_wheel)
     115           0 :                 zlog_debug("%s: Inserting %p: %lld %lld", __func__, item, slot,
     116             :                            slot % wheel->slots);
     117           0 :         listnode_add(wheel->wheel_slot_lists[slot % wheel->slots], item);
     118             : 
     119           0 :         return 0;
     120             : }
     121             : 
     122           0 : int wheel_remove_item(struct timer_wheel *wheel, void *item)
     123             : {
     124           0 :         long long slot;
     125             : 
     126           0 :         slot = (*wheel->slot_key)(item);
     127             : 
     128           0 :         if (debug_timer_wheel)
     129           0 :                 zlog_debug("%s: Removing %p: %lld %lld", __func__, item, slot,
     130             :                            slot % wheel->slots);
     131           0 :         listnode_delete(wheel->wheel_slot_lists[slot % wheel->slots], item);
     132             : 
     133           0 :         return 0;
     134             : }