lib/wheel.h

   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 #ifndef __WHEEL_H__
  21 #define __WHEEL_H__
  22
  23 #ifdef __cplusplus
  24 extern "C" {
  25 #endif
  26
  27 struct timer_wheel {
  28         char *name;
  29         struct thread_master *master;
  30         int slots;
  31         long long curr_slot;
  32         unsigned int period;
  33         unsigned int nexttime;
  34         unsigned int slots_to_skip;
  35
  36         struct list **wheel_slot_lists;
  37         struct thread *timer;
  38         /*
  39          * Key to determine what slot the item belongs in
  40          */
  41         unsigned int (*slot_key)(const void *);
  42
  43         void (*slot_run)(void *);
  44 };
  45
  46 /*
  47  * Creates a timer wheel
  48  *
  49  * master - Thread master structure for the process
  50  * period - The Time in seconds that the timer wheel will
  51  *          take before it starts issuing commands again
  52  *          for items in each slot
  53  * slots  - The number of slots to have in this particular
  54  *          timer wheel
  55  * slot_key - A hashing function of some sort that will allow
  56  *            the timer wheel to put items into individual slots
  57  * slot_run - The function to run over each item in a particular slot
  58  *
  59  * Creates a timer wheel that will wake up 'slots' times over the entire
  60  * wheel.  Each time the timer wheel wakes up it will iterate through
  61  * and run the slot_run function for each item stored in that particular
  62  * slot.
  63  *
  64  * The timer code is 'intelligent' in that it notices if anything is
  65  * in a particular slot and can schedule the next timer to skip
  66  * the empty slot.
  67  *
  68  * The general purpose of a timer wheel is to reduce events in a system.
  69  * A perfect example of usage for this is say hello packets that need
  70  * to be sent out to all your neighbors.  Suppose a large routing protocol
  71  * has to send keepalive packets every Y seconds to each of it's peers.
  72  * At scale we can have a very large number of peers, X.
  73  * This means that we will have X timing events every Y seconds.
  74  * If you replace these events with a timer wheel that has Z slots
  75  * you will have at most Y/Z timer events if each slot has a work item
  76  * in it.
  77  *
  78  * When X is large the number of events in a system can quickly escalate
  79  * and cause significant amount of time handling thread events instead
  80  * of running your code.
  81  */
  82 struct timer_wheel *wheel_init(struct thread_master *master, int period,
  83                                size_t slots,
  84                                unsigned int (*slot_key)(const void *),
  85                                void (*slot_run)(void *), const char *run_name);
  86
  87 /*
  88  * Delete the specified timer wheel created
  89  */
  90 void wheel_delete(struct timer_wheel *);
  91
  92 /*
  93  * Pause the Wheel from running
  94  */
  95 int wheel_stop(struct timer_wheel *wheel);
  96
  97 /*
  98  * Start the wheel running again
  99  */
 100 int wheel_start(struct timer_wheel *wheel);
 101
 102 /*
 103  * wheel - The Timer wheel being modified
 104  * item - The generic data structure that will be handed
 105  *        to the slot_run function.
 106  *
 107  * Add item to a slot setup by the slot_key,
 108  * possibly change next time pop.
 109  */
 110 int wheel_add_item(struct timer_wheel *wheel, void *item);
 111
 112 /*
 113  * wheel - The Timer wheel being modified.
 114  * item - The item to remove from one of the slots in
 115  *        the timer wheel.
 116  *
 117  * Remove a item to a slot setup by the slot_key,
 118  * possibly change next time pop.
 119  */
 120 int wheel_remove_item(struct timer_wheel *wheel, void *item);
 121
 122 #ifdef __cplusplus
 123 }
 124 #endif
 125
 126 #endif