lib/wheel.h

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