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 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 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL, "Timer Wheel")
  28 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL_LIST, "Timer Wheel Slot List")
  29
  30 static int debug_timer_wheel = 0;
  31
  32 static int wheel_timer_thread(struct thread *t);
  33
  34 static int wheel_timer_thread_helper(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__, wheel->curr_slot, curr_slot,
  52                            listcount(wheel->wheel_slot_lists[curr_slot]));
  53
  54         for (ALL_LIST_ELEMENTS(wheel->wheel_slot_lists[curr_slot], node,
  55                                nextnode, data))
  56                 (*wheel->slot_run)(data);
  57
  58         while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip)
  59                                                     % wheel->slots])
  60                && (curr_slot + slots_to_skip) % wheel->slots != curr_slot)
  61                 slots_to_skip++;
  62
  63         wheel->slots_to_skip = slots_to_skip;
  64         thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
  65                               wheel->nexttime * slots_to_skip, &wheel->timer);
  66
  67         return 0;
  68 }
  69
  70 static int wheel_timer_thread(struct thread *t)
  71 {
  72         struct timer_wheel *wheel;
  73
  74         wheel = THREAD_ARG(t);
  75
  76         thread_execute_name(wheel->master, wheel_timer_thread_helper,
  77                             wheel, 0, wheel->name);
  78
  79         return 0;
  80 }
  81
  82 struct timer_wheel *wheel_init(struct thread_master *master, int period,
  83                                size_t slots, unsigned int (*slot_key)(void *),
  84                                void (*slot_run)(void *),
  85                                const char *run_name)
  86 {
  87         struct timer_wheel *wheel;
  88         size_t i;
  89
  90         wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof(struct timer_wheel));
  91
  92         wheel->name = XSTRDUP(MTYPE_TIMER_WHEEL, run_name);
  93         wheel->slot_key = slot_key;
  94         wheel->slot_run = slot_run;
  95
  96         wheel->period = period;
  97         wheel->slots = slots;
  98         wheel->curr_slot = 0;
  99         wheel->master = master;
 100         wheel->nexttime = period / slots;
 101
 102         wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
 103                                           slots * sizeof(struct listnode *));
 104         for (i = 0; i < slots; i++)
 105                 wheel->wheel_slot_lists[i] = list_new();
 106
 107         thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
 108                               wheel->nexttime, &wheel->timer);
 109
 110         return wheel;
 111 }
 112
 113 void wheel_delete(struct timer_wheel *wheel)
 114 {
 115         int i;
 116
 117         for (i = 0; i < wheel->slots; i++) {
 118                 list_delete(&wheel->wheel_slot_lists[i]);
 119         }
 120
 121         THREAD_OFF(wheel->timer);
 122         XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
 123         XFREE(MTYPE_TIMER_WHEEL, wheel->name);
 124         XFREE(MTYPE_TIMER_WHEEL, wheel);
 125 }
 126
 127 int wheel_stop(struct timer_wheel *wheel)
 128 {
 129         THREAD_OFF(wheel->timer);
 130         return 0;
 131 }
 132
 133 int wheel_start(struct timer_wheel *wheel)
 134 {
 135         if (!wheel->timer)
 136                 thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
 137                                       wheel->nexttime, &wheel->timer);
 138
 139         return 0;
 140 }
 141
 142 int wheel_add_item(struct timer_wheel *wheel, void *item)
 143 {
 144         long long slot;
 145
 146         slot = (*wheel->slot_key)(item);
 147
 148         if (debug_timer_wheel)
 149                 zlog_debug("%s: Inserting %p: %lld %lld", __PRETTY_FUNCTION__,
 150                            item, slot, slot % wheel->slots);
 151         listnode_add(wheel->wheel_slot_lists[slot % wheel->slots], item);
 152
 153         return 0;
 154 }
 155
 156 int wheel_remove_item(struct timer_wheel *wheel, void *item)
 157 {
 158         long long slot;
 159
 160         slot = (*wheel->slot_key)(item);
 161
 162         if (debug_timer_wheel)
 163                 zlog_debug("%s: Removing %p: %lld %lld", __PRETTY_FUNCTION__,
 164                            item, slot, slot % wheel->slots);
 165         listnode_delete(wheel->wheel_slot_lists[slot % wheel->slots], item);
 166
 167         return 0;
 168 }