drl/standard.h

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