drl/multipleinterval.h

   1 /* See the DRL-LICENSE file for this file's software license. */
   2
   3 /*
   4  * Defines the multiple-interval "perfect" flow accounting table.
   5  *
   6  */
   7
   8 #ifndef _MULTIPLE_ACCOUNTING_H_
   9 #define _MULTIPLE_ACCOUNTING_H_
  10
  11 #include <inttypes.h>
  12
  13 //FIXME: Update comments on structure variables
  14
  15 /** The number of hash buckets in the table. */
  16 #define MUL_FLOW_HASH_SIZE 1024
  17
  18 /** The number of seconds after which a flow is considered to be inactive.
  19  * Inactive flows will be removed from the table during the next call to the
  20  * cleanup function. */
  21 #define MUL_FLOW_IDLE_TIME 15
  22
  23 #define MUL_INTERVAL_COUNT 10
  24
  25 typedef struct mul_interval {
  26     /** The number of bytes this flow has sent since the last update to this
  27      * interval structure. */
  28     uint32_t bytes_since;
  29
  30     /** The time at which this interval was last updated. */
  31     struct timeval last_update;
  32
  33     /** The time at which the most recent packet in this flow was received
  34      * in this interval. */
  35     time_t last_packet;
  36
  37     uint32_t valid;
  38
  39     struct mul_interval *next;
  40 } interval;
  41
  42 /** Representation of a flow in a multiple-interval table. */
  43 typedef struct mul_flow {
  44     /* Flow information. */
  45
  46     /** The rate of the flow in the current estimate interval. */
  47     uint32_t rate;
  48
  49     /** The rate of the flow in the previous estimate interval. */
  50     uint32_t last_rate;
  51
  52     time_t last_packet;
  53
  54     interval *current_interval;
  55
  56     interval *intervals;
  57
  58     /* Identification information. */
  59
  60     /** The flow's source IP address. */
  61     uint32_t source_ip;
  62
  63     /** The flow's destination IP address. */
  64     uint32_t dest_ip;
  65
  66     /** The flow's source port. */
  67     uint16_t source_port;
  68
  69     /** The flow's destination port. */
  70     uint16_t dest_port;
  71
  72     /** The flow's protocol.  This corresponds to the protocol field of the IP
  73      * header. */
  74     uint8_t protocol;
  75
  76     /* Table state. */
  77
  78     /** Pointer to the next flow in the hash list. */
  79     struct mul_flow *nexth;
  80
  81     /** Pointers to the next flow in the linked list. */
  82     struct mul_flow *next;
  83
  84     /** Pointers to the previous flow in the linked list. */
  85     struct mul_flow *prev;
  86
  87 } multiple_flow;
  88
  89 /**
  90  * The "table" that stores the flows.  It's constructed of two main pieces.
  91  *
  92  * The first is an array of hash buckets.  Flows are classified into buckets
  93  * by hashing the flow's values (key flow) using the table's hash function.
  94  * Flows are chained together as a list in each bucket to deal with collisions.
  95  *
  96  * The second is a simple doubly linked list containing every flow in the table.
  97  */
  98 struct mul_flow_table {
  99
 100     /** Pointer to the common flow information for the identity that owns this
 101      * sampled flow table.  This is updated with aggregate information. */
 102     common_accounting_t *common;
 103
 104     uint32_t interval_count;
 105
 106     interval *current_interval;
 107
 108     interval *intervals;
 109
 110     /* Table structures. */
 111
 112     /** Hash buckets - each is a list of flows. */
 113     struct mul_flow *flows[MUL_FLOW_HASH_SIZE];
 114
 115     /** The head of the linked list of flows. */
 116     struct mul_flow *flows_head;
 117
 118     /** The tail of the linked list of flows. */
 119     struct mul_flow *flows_tail;
 120
 121     /** Function pointer to the function that will yield the hash of a
 122      * key_flow.
 123      */
 124     uint32_t (*hash_function)(const key_flow *key);
 125
 126 };
 127
 128 /** The type multiple_flow_table is really a pointer to a struct
 129  * mul_flow_table. */
 130 typedef struct mul_flow_table *multiple_flow_table;
 131
 132 /**
 133  * Creates a new table that will use the specified hash function.
 134  *
 135  * Returns the new table or NULL on failure.
 136  */
 137 multiple_flow_table multiple_table_create(uint32_t (*hash_function)(const key_flow *key), uint32_t interval_count, common_accounting_t *common);
 138
 139 /**
 140  * Destroys the specified table.
 141  */
 142 void multiple_table_destroy(multiple_flow_table table);
 143
 144 /**
 145  * Looks for a flow that matches the given key in the specified table.  If a
 146  * matching flow is not found, this function will allocate a new flow for the
 147  * key.
 148  *
 149  * Returns a pointer to the flow that matches the key or NULL if there is no
 150  * matching flow and a new flow couldn't be allocated.
 151  */
 152 multiple_flow *multiple_table_lookup(multiple_flow_table table, const key_flow *key);
 153
 154 /**
 155  * Updates the state of the table given a newly acquired packet.
 156  *
 157  * Returns 1 if the flow is in the table.  0 otherwise (indicating that memory
 158  * could not be allocated to add a new flow to the table for the given key.
 159  */
 160 int multiple_table_sample(multiple_flow_table table, const key_flow *key);
 161
 162 /**
 163  * Cleans the table by removing flow entires for any flow that hasn't seen a
 164  * new packet in the interval specified by MUL_FLOW_IDLE_TIME seconds.
 165  */
 166 int multiple_table_cleanup(multiple_flow_table table);
 167
 168 /**
 169  * Updates the rate information for all flows in the table according to the
 170  * specified current time and EWMA weight.
 171  */
 172 void multiple_table_update_flows(multiple_flow_table table, struct timeval now, double ewma_weight);
 173
 174 #endif  /* _MULTIPLE_ACCOUNTING_H_ */