lib/wheel.c

   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
  17  * along with this program; see the file COPYING; if not, write to the
  18  * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
  19  * MA 02110-1301 USA
  20  */
  21 #include "zebra.h"
  22 #include "linklist.h"
  23 #include "thread.h"
  24 #include "memory.h"
  25 #include "wheel.h"
  26 #include "log.h"
  27
  28 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL,   "Timer Wheel")
  29 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL_LIST, "Timer Wheel Slot List")
  30
  31 static int debug_timer_wheel = 0;
  32
  33 static int
  34 wheel_timer_thread (struct thread *t)
  35 {
  36   struct listnode *node, *nextnode;
  37   unsigned long long curr_slot;
  38   unsigned int slots_to_skip = 1;
  39   struct timer_wheel *wheel;
  40   void *data;
  41
  42   wheel = THREAD_ARG(t);
  43   THREAD_OFF(wheel->timer);
  44
  45   wheel->curr_slot += wheel->slots_to_skip;
  46
  47   curr_slot = wheel->curr_slot % wheel->slots;
  48
  49   if (debug_timer_wheel)
  50     zlog_debug ("%s: Wheel Slot: %lld(%lld) count: %d",
  51                 __PRETTY_FUNCTION__,
  52                 wheel->curr_slot,
  53                 curr_slot, listcount(wheel->wheel_slot_lists[curr_slot]));
  54
  55   for (ALL_LIST_ELEMENTS (wheel->wheel_slot_lists[curr_slot], node, nextnode, data))
  56     (*wheel->slot_run)(data);
  57
  58   while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip) % wheel->slots]) &&
  59          (curr_slot + slots_to_skip ) % wheel->slots != curr_slot)
  60     slots_to_skip++;
  61
  62   wheel->slots_to_skip = slots_to_skip;
  63   THREAD_TIMER_MSEC_ON (wheel->master, wheel->timer,
  64                         wheel_timer_thread, wheel,
  65                         wheel->nexttime * slots_to_skip);
  66
  67   return 0;
  68 }
  69
  70 struct timer_wheel *
  71 wheel_init (struct thread_master *master, int period, size_t slots,
  72             unsigned int (*slot_key) (void *),
  73             void (*slot_run) (void *))
  74 {
  75   struct timer_wheel *wheel;
  76   size_t i;
  77
  78   wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof (struct timer_wheel));
  79
  80   wheel->slot_key = slot_key;
  81   wheel->slot_run = slot_run;
  82
  83   wheel->period = period;
  84   wheel->slots = slots;
  85   wheel->curr_slot = 0;
  86   wheel->master = master;
  87   wheel->nexttime = period / slots;
  88
  89   wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
  90                                     slots * sizeof (struct listnode *));
  91   for (i = 0; i < slots; i++)
  92     wheel->wheel_slot_lists[i] = list_new ();
  93
  94   THREAD_TIMER_MSEC_ON (wheel->master, wheel->timer,
  95                         wheel_timer_thread, wheel,
  96                         wheel->nexttime);
  97
  98   return wheel;
  99 }
 100
 101 void
 102 wheel_delete (struct timer_wheel *wheel)
 103 {
 104   int i;
 105
 106   for (i = 0; i < wheel->slots; i++)
 107     {
 108       list_delete(wheel->wheel_slot_lists[i]);
 109     }
 110
 111   THREAD_OFF(wheel->timer);
 112   XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
 113   XFREE(MTYPE_TIMER_WHEEL, wheel);
 114 }
 115
 116 int
 117 wheel_stop (struct timer_wheel *wheel)
 118 {
 119   THREAD_OFF(wheel->timer);
 120   return 0;
 121 }
 122
 123 int
 124 wheel_start (struct timer_wheel *wheel)
 125 {
 126   if (!wheel->timer)
 127     THREAD_TIMER_MSEC_ON (wheel->master, wheel->timer,
 128                           wheel_timer_thread, wheel,
 129                           wheel->nexttime);
 130
 131   return 0;
 132 }
 133
 134 int
 135 wheel_add_item (struct timer_wheel *wheel, void *item)
 136 {
 137   long long slot;
 138
 139   slot = (*wheel->slot_key)(item);
 140
 141   if (debug_timer_wheel)
 142     zlog_debug ("%s: Inserting %p: %lld %lld",
 143                 __PRETTY_FUNCTION__, item,
 144                 slot, slot % wheel->slots);
 145   listnode_add (wheel->wheel_slot_lists[slot % wheel->slots], item);
 146
 147   return 0;
 148 }
 149
 150 int
 151 wheel_remove_item (struct timer_wheel *wheel, void *item)
 152 {
 153   long long slot;
 154
 155   slot = (*wheel->slot_key)(item);
 156
 157   if (debug_timer_wheel)
 158     zlog_debug ("%s: Removing %p: %lld %lld",
 159                 __PRETTY_FUNCTION__, item,
 160                 slot, slot % wheel->slots);
 161   listnode_delete (wheel->wheel_slot_lists[slot % wheel->slots], item);
 162
 163   return 0;
 164 }