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