lib/wheel.c

   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 "thread.h"
  10 #include "memory.h"
  11 #include "wheel.h"
  12 #include "log.h"
  13
  14 DEFINE_MTYPE_STATIC(LIB, TIMER_WHEEL, "Timer Wheel");
  15 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 thread *t);
  20
  21 static void wheel_timer_thread_helper(struct thread *t)
  22 {
  23         struct listnode *node, *nextnode;
  24         unsigned long long curr_slot;
  25         unsigned int slots_to_skip = 1;
  26         struct timer_wheel *wheel;
  27         void *data;
  28
  29         wheel = THREAD_ARG(t);
  30
  31         wheel->curr_slot += wheel->slots_to_skip;
  32
  33         curr_slot = wheel->curr_slot % wheel->slots;
  34
  35         if (debug_timer_wheel)
  36                 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         for (ALL_LIST_ELEMENTS(wheel->wheel_slot_lists[curr_slot], node,
  41                                nextnode, data))
  42                 (*wheel->slot_run)(data);
  43
  44         while (list_isempty(wheel->wheel_slot_lists[(curr_slot + slots_to_skip)
  45                                                     % wheel->slots])
  46                && (curr_slot + slots_to_skip) % wheel->slots != curr_slot)
  47                 slots_to_skip++;
  48
  49         wheel->slots_to_skip = slots_to_skip;
  50         thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
  51                               wheel->nexttime * slots_to_skip, &wheel->timer);
  52 }
  53
  54 static void wheel_timer_thread(struct thread *t)
  55 {
  56         struct timer_wheel *wheel;
  57
  58         wheel = THREAD_ARG(t);
  59
  60         thread_execute(wheel->master, wheel_timer_thread_helper, wheel, 0);
  61 }
  62
  63 struct timer_wheel *wheel_init(struct thread_master *master, int period,
  64                                size_t slots, unsigned int (*slot_key)(const void *),
  65                                void (*slot_run)(void *),
  66                                const char *run_name)
  67 {
  68         struct timer_wheel *wheel;
  69         size_t i;
  70
  71         wheel = XCALLOC(MTYPE_TIMER_WHEEL, sizeof(struct timer_wheel));
  72
  73         wheel->name = XSTRDUP(MTYPE_TIMER_WHEEL, run_name);
  74         wheel->slot_key = slot_key;
  75         wheel->slot_run = slot_run;
  76
  77         wheel->period = period;
  78         wheel->slots = slots;
  79         wheel->curr_slot = 0;
  80         wheel->master = master;
  81         wheel->nexttime = period / slots;
  82
  83         wheel->wheel_slot_lists = XCALLOC(MTYPE_TIMER_WHEEL_LIST,
  84                                           slots * sizeof(struct list *));
  85         for (i = 0; i < slots; i++)
  86                 wheel->wheel_slot_lists[i] = list_new();
  87
  88         thread_add_timer_msec(wheel->master, wheel_timer_thread, wheel,
  89                               wheel->nexttime, &wheel->timer);
  90
  91         return wheel;
  92 }
  93
  94 void wheel_delete(struct timer_wheel *wheel)
  95 {
  96         int i;
  97
  98         for (i = 0; i < wheel->slots; i++) {
  99                 list_delete(&wheel->wheel_slot_lists[i]);
 100         }
 101
 102         THREAD_OFF(wheel->timer);
 103         XFREE(MTYPE_TIMER_WHEEL_LIST, wheel->wheel_slot_lists);
 104         XFREE(MTYPE_TIMER_WHEEL, wheel->name);
 105         XFREE(MTYPE_TIMER_WHEEL, wheel);
 106 }
 107
 108 int wheel_add_item(struct timer_wheel *wheel, void *item)
 109 {
 110         long long slot;
 111
 112         slot = (*wheel->slot_key)(item);
 113
 114         if (debug_timer_wheel)
 115                 zlog_debug("%s: Inserting %p: %lld %lld", __func__, item, slot,
 116                            slot % wheel->slots);
 117         listnode_add(wheel->wheel_slot_lists[slot % wheel->slots], item);
 118
 119         return 0;
 120 }
 121
 122 int wheel_remove_item(struct timer_wheel *wheel, void *item)
 123 {
 124         long long slot;
 125
 126         slot = (*wheel->slot_key)(item);
 127
 128         if (debug_timer_wheel)
 129                 zlog_debug("%s: Removing %p: %lld %lld", __func__, item, slot,
 130                            slot % wheel->slots);
 131         listnode_delete(wheel->wheel_slot_lists[slot % wheel->slots], item);
 132
 133         return 0;
 134 }