Line data    Source code

       1             : /*
       2             :  * Timer Wheel
       3             :  * Copyright (C) 2016 Cumulus Networks, Inc.
       4             :  * Donald Sharp
       5             :  *
       6             :  * This program is free software; you can redistribute it and/or modify
       7             :  * it under the terms of the GNU General Public License as published by
       8             :  * the Free Software Foundation; either version 2 of the License, or
       9             :  * (at your option) any later version.
      10             :  *
      11             :  * This program is distributed in the hope that it will be useful, but
      12             :  * WITHOUT ANY WARRANTY; without even the implied warranty of
      13             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      14             :  * General Public License for more details.
      15             :  *
      16             :  * You should have received a copy of the GNU General Public License along
      17             :  * with this program; see the file COPYING; if not, write to the Free Software
      18             :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
      19             :  */
      20             : #include "zebra.h"
      21             : #include "linklist.h"
      22             : #include "thread.h"
      23             : #include "memory.h"
      24             : #include "wheel.h"
      25             : #include "log.h"
      26             : 
      27          44 : DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL, "Timer Wheel");
      28          44 : DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL_LIST, "Timer Wheel Slot List");
      29             : 
      30             : static int debug_timer_wheel = 0;
      31             : 
      32             : static void wheel_timer_thread(struct thread *t);
      33             : 
      34           8 : static void wheel_timer_thread_helper(struct thread *t)
      35             : {
      36           8 :         struct listnode *node, *nextnode;
      37           8 :         unsigned long long curr_slot;
      38           8 :         unsigned int slots_to_skip = 1;
      39           8 :         struct timer_wheel *wheel;
      40           8 :         void *data;
      41             : 
      42           8 :         wheel = THREAD_ARG(t);
      43             : 
      44           8 :         wheel->curr_slot += wheel->slots_to_skip;
      45             : 
      46           8 :         curr_slot = wheel->curr_slot % wheel->slots;
      47             : 
      48           8 :         if (debug_timer_wheel)
      49           0 :                 zlog_debug("%s: Wheel Slot: %lld(%lld) count: %d", __func__,
      50             :                            wheel->curr_slot, curr_slot,
      51             :                            listcount(wheel->wheel_slot_lists[curr_slot]));
      52             : 
      53          20 :         for (ALL_LIST_ELEMENTS(wheel->wheel_slot_lists[curr_slot], node,
      54             :                                nextnode, data))
      55           4 :                 (*wheel->slot_run)(data);
      56             : 
      57         796 :         while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip)
      58             :                                                     % wheel->slots])
      59        1596 :                && (curr_slot + slots_to_skip) % wheel->slots != curr_slot)
      60         792 :                 slots_to_skip++;
      61             : 
      62           8 :         wheel->slots_to_skip = slots_to_skip;
      63           8 :         thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
      64             :                               wheel->nexttime * slots_to_skip, &wheel->timer);
      65           8 : }
      66             : 
      67           8 : static void wheel_timer_thread(struct thread *t)
      68             : {
      69           8 :         struct timer_wheel *wheel;
      70             : 
      71           8 :         wheel = THREAD_ARG(t);
      72             : 
      73           8 :         thread_execute(wheel->master, wheel_timer_thread_helper, wheel, 0);
      74           8 : }
      75             : 
      76           4 : struct timer_wheel *wheel_init(struct thread_master *master, int period,
      77             :                                size_t slots, unsigned int (*slot_key)(const void *),
      78             :                                void (*slot_run)(void *),
      79             :                                const char *run_name)
      80             : {
      81           4 :         struct timer_wheel *wheel;
      82           4 :         size_t i;
      83             : 
      84           4 :         wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof(struct timer_wheel));
      85             : 
      86           4 :         wheel->name = XSTRDUP(MTYPE_TIMER_WHEEL, run_name);
      87           4 :         wheel->slot_key = slot_key;
      88           4 :         wheel->slot_run = slot_run;
      89             : 
      90           4 :         wheel->period = period;
      91           4 :         wheel->slots = slots;
      92           4 :         wheel->curr_slot = 0;
      93           4 :         wheel->master = master;
      94           4 :         wheel->nexttime = period / slots;
      95             : 
      96           4 :         wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
      97             :                                           slots * sizeof(struct list *));
      98         404 :         for (i = 0; i < slots; i++)
      99         400 :                 wheel->wheel_slot_lists[i] = list_new();
     100             : 
     101           4 :         thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
     102             :                               wheel->nexttime, &wheel->timer);
     103             : 
     104           4 :         return wheel;
     105             : }
     106             : 
     107           4 : void wheel_delete(struct timer_wheel *wheel)
     108             : {
     109           4 :         int i;
     110             : 
     111         404 :         for (i = 0; i < wheel->slots; i++) {
     112         400 :                 list_delete(&wheel->wheel_slot_lists[i]);
     113             :         }
     114             : 
     115           4 :         THREAD_OFF(wheel->timer);
     116           4 :         XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
     117           4 :         XFREE(MTYPE_TIMER_WHEEL, wheel->name);
     118           4 :         XFREE(MTYPE_TIMER_WHEEL, wheel);
     119           4 : }
     120             : 
     121           4 : int wheel_add_item(struct timer_wheel *wheel, void *item)
     122             : {
     123           4 :         long long slot;
     124             : 
     125           4 :         slot = (*wheel->slot_key)(item);
     126             : 
     127           4 :         if (debug_timer_wheel)
     128           0 :                 zlog_debug("%s: Inserting %p: %lld %lld", __func__, item, slot,
     129             :                            slot % wheel->slots);
     130           4 :         listnode_add(wheel->wheel_slot_lists[slot % wheel->slots], item);
     131             : 
     132           4 :         return 0;
     133             : }
     134             : 
     135           4 : int wheel_remove_item(struct timer_wheel *wheel, void *item)
     136             : {
     137           4 :         long long slot;
     138             : 
     139           4 :         slot = (*wheel->slot_key)(item);
     140             : 
     141           4 :         if (debug_timer_wheel)
     142           0 :                 zlog_debug("%s: Removing %p: %lld %lld", __func__, item, slot,
     143             :                            slot % wheel->slots);
     144           4 :         listnode_delete(wheel->wheel_slot_lists[slot % wheel->slots], item);
     145             : 
     146           4 :         return 0;
     147             : }