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 wheel_timer_thread(struct thread *t)
  34 {
  35         struct listnode *node, *nextnode;
  36         unsigned long long curr_slot;
  37         unsigned int slots_to_skip = 1;
  38         struct timer_wheel *wheel;
  39         void *data;
  40
  41         wheel = THREAD_ARG(t);
  42         THREAD_OFF(wheel->timer);
  43
  44         wheel->curr_slot += wheel->slots_to_skip;
  45
  46         curr_slot = wheel->curr_slot % wheel->slots;
  47
  48         if (debug_timer_wheel)
  49                 zlog_debug("%s: Wheel Slot: %lld(%lld) count: %d",
  50                            __PRETTY_FUNCTION__, wheel->curr_slot, curr_slot,
  51                            listcount(wheel->wheel_slot_lists[curr_slot]));
  52
  53         for (ALL_LIST_ELEMENTS(wheel->wheel_slot_lists[curr_slot], node,
  54                                nextnode, data))
  55                 (*wheel->slot_run)(data);
  56
  57         while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip)
  58                                                     % 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, wheel_timer_thread,
  64                              wheel, wheel->nexttime * slots_to_skip);
  65
  66         return 0;
  67 }
  68
  69 struct timer_wheel *wheel_init(struct thread_master *master, int period,
  70                                size_t slots, unsigned int (*slot_key)(void *),
  71                                void (*slot_run)(void *))
  72 {
  73         struct timer_wheel *wheel;
  74         size_t i;
  75
  76         wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof(struct timer_wheel));
  77
  78         wheel->slot_key = slot_key;
  79         wheel->slot_run = slot_run;
  80
  81         wheel->period = period;
  82         wheel->slots = slots;
  83         wheel->curr_slot = 0;
  84         wheel->master = master;
  85         wheel->nexttime = period / slots;
  86
  87         wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
  88                                           slots * sizeof(struct listnode *));
  89         for (i = 0; i < slots; i++)
  90                 wheel->wheel_slot_lists[i] = list_new();
  91
  92         THREAD_TIMER_MSEC_ON(wheel->master, wheel->timer, wheel_timer_thread,
  93                              wheel, wheel->nexttime);
  94
  95         return wheel;
  96 }
  97
  98 void wheel_delete(struct timer_wheel *wheel)
  99 {
 100         int i;
 101
 102         for (i = 0; i < wheel->slots; i++) {
 103                 list_delete(wheel->wheel_slot_lists[i]);
 104         }
 105
 106         THREAD_OFF(wheel->timer);
 107         XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
 108         XFREE(MTYPE_TIMER_WHEEL, wheel);
 109 }
 110
 111 int wheel_stop(struct timer_wheel *wheel)
 112 {
 113         THREAD_OFF(wheel->timer);
 114         return 0;
 115 }
 116
 117 int wheel_start(struct timer_wheel *wheel)
 118 {
 119         if (!wheel->timer)
 120                 THREAD_TIMER_MSEC_ON(wheel->master, wheel->timer,
 121                                      wheel_timer_thread, wheel,
 122                                      wheel->nexttime);
 123
 124         return 0;
 125 }
 126
 127 int wheel_add_item(struct timer_wheel *wheel, void *item)
 128 {
 129         long long slot;
 130
 131         slot = (*wheel->slot_key)(item);
 132
 133         if (debug_timer_wheel)
 134                 zlog_debug("%s: Inserting %p: %lld %lld", __PRETTY_FUNCTION__,
 135                            item, slot, slot % wheel->slots);
 136         listnode_add(wheel->wheel_slot_lists[slot % wheel->slots], item);
 137
 138         return 0;
 139 }
 140
 141 int wheel_remove_item(struct timer_wheel *wheel, void *item)
 142 {
 143         long long slot;
 144
 145         slot = (*wheel->slot_key)(item);
 146
 147         if (debug_timer_wheel)
 148                 zlog_debug("%s: Removing %p: %lld %lld", __PRETTY_FUNCTION__,
 149                            item, slot, slot % wheel->slots);
 150         listnode_delete(wheel->wheel_slot_lists[slot % wheel->slots], item);
 151
 152         return 0;
 153 }