drl/ratetypes.h

   1 /* See the DRL-LICENSE file for this file's software license. */
   2
   3 /* ratetypes.h
   4  *
   5  * Defines the main types used by DRL.
   6  */
   7
   8 #ifndef _RATETYPES_H_
   9 #define _RATETYPES_H_
  10
  11 #include <inttypes.h>
  12
  13 #if 0
  14 #include "rate_accounting/common_accounting.h"
  15 #include "rate_accounting/standard.h"
  16 #include "rate_accounting/samplehold.h"
  17 #include "rate_accounting/simple.h"
  18 #endif
  19
  20 #include "bsd_queue.h"
  21 #include "config.h"
  22 #include "drl_state.h"
  23 #include "common_accounting.h"
  24 #include "standard.h"
  25 #include "samplehold.h"
  26 #include "simple.h"
  27 #include "multipleinterval.h"
  28
  29
  30 /** Represents a DRL entitiy/group. */
  31 typedef struct identity {
  32
  33     /** A unique id for the identity. */
  34     uint32_t id;
  35
  36     /** The global rate limit. */
  37     uint32_t limit;
  38
  39     /** The effective global rate limit.  Can be lower than the nominal global
  40      * rate limit due to the failure of one or more peers. */
  41     uint32_t effective_limit;
  42
  43     /** The local rate limit. */
  44     uint32_t locallimit;
  45
  46     /** Pointer to the identity's parent in the HTB hierarchy. */
  47     struct identity *parent;
  48
  49     /** For sets, indicates the parent should be 0x10.  Meaningless for machines. */
  50     int independent;
  51
  52     /** Array of the leaves that are limited by this identity. Points into the
  53      * leaves array for the identity's instance. */
  54     struct leaf **leaves;
  55
  56     /** The number of leaves for which this identity is responsible. */
  57     int leaf_count;
  58
  59     /** The fixed (per second) EWMA weight. */
  60     double fixed_ewma_weight;
  61
  62     /** The real EWMA weight, based on the fixed weight and estimate interval.*/
  63     double ewma_weight;
  64
  65     /** Used for average rate graph generation. */
  66     double avg_bytes;
  67
  68     /* Communication */
  69
  70     /** Communication data for this identity. */
  71     comm_t comm;
  72
  73     /* FPS */
  74
  75     /** The node in the HTB hierarchy whose limits will be modified by this
  76      * identity.  (1:1<htb_node>)*/
  77     uint32_t htb_node;
  78
  79     /** The parent of this node in the HTB hierarchy. (tc requires that the
  80      * parent be specified in all calls the modify a node.) */
  81     uint32_t htb_parent;
  82
  83     /** FPS current weight value. */
  84     double localweight;
  85
  86     /** FPS previous weight value. */
  87     double last_localweight;
  88
  89     double total_weight;
  90
  91     /** A flag to indicate whether or not the identity is in the flowstart
  92      * state.  During flowstart, the identity's limit is raised to allow for
  93      * flows to grow before incurring losses. */
  94     int flowstart;
  95
  96     /** Keeps track of the state of FPS dampening for this identity. */
  97     enum dampenings dampen_state;
  98
  99     /* GRD */
 100
 101     /** GRD drop probability information. */
 102     double drop_prob;
 103
 104     /** GRD previous drop probability information. */
 105     double last_drop_prob;
 106
 107     /* Flow accounting machinery. */
 108
 109     /** Flow information that is common to all types of tables.
 110      * This includes aggregate rates, update times, etc. */
 111     common_accounting_t common;
 112
 113     /** The actual table.  Uses a void pointer because it could be one
 114      * of several different types. (standard, sample&hold, etc. ) */
 115     void *table;
 116
 117     /** Protects the table, as it gets updated in two separate threads:
 118      * 1) ulogd_DRL.c: the table is updated as new packet information arrives.
 119      * 2) estimate.c: the table is used to determine rates, and it's also
 120      * periodically cleaned.
 121      */
 122     pthread_mutex_t table_mutex;
 123
 124     /* Function pointers to functions to act on the table. */
 125
 126     /** Function to call for each packet.  Updates the byte count for flows
 127      * that are being tracked. */
 128     int (*table_sample_function)(void *, const key_flow *);
 129
 130     /** Function to call on the table when it is periodically cleaned. */
 131     int (*table_cleanup_function)(void *);
 132
 133     /** Function to call once per estimate interval to update the table's
 134      * rate estimation. */
 135     void (*table_update_function)(void *, struct timeval, double);
 136
 137     /** Function to call when the table should be destroyed. */
 138     void (*table_destroy_function)(void *);
 139
 140 #ifdef SHADOW_ACCTING
 141
 142     common_accounting_t shadow_common;
 143
 144     void *shadow_table;
 145
 146     double localweight_copy;
 147     double last_localweight_copy;
 148
 149     enum dampenings dampen_state_copy;
 150
 151 #endif
 152
 153     /* Scheduling bookkeeping. */
 154
 155     /** Scheduling unit that tells the limiter when to execute the main loop.*/
 156     struct ident_action *loop_action;
 157
 158     /** Scheduling unit that tells the limiter when to communicate.*/
 159     struct ident_action *comm_action;
 160
 161     /** The number of limiter ticks that should pass before this identity should
 162      * be scheduled to execute its main estimate/allocate/enforce loop. */
 163     uint32_t mainloop_intervals;
 164
 165     /** The number of limiter ticks that should pass before this identity should
 166      * be scheduled for communication. */
 167     uint32_t communication_intervals;
 168
 169 } identity_t;
 170
 171 enum identity_actions { ACTION_MAINLOOP = 1, ACTION_COMMUNICATE = 2 };
 172
 173 typedef struct ident_action {
 174     struct identity *ident;
 175     enum identity_actions action;
 176     int valid;
 177
 178     TAILQ_ENTRY(ident_action) calendar;
 179 } identity_action;
 180
 181 /**
 182  * Represents the bottom most entity in the HTB hierarchy.  For PlanetLab,
 183  * this corresponds to sliver (identified by Vserver context id, or xid).
 184  */
 185 typedef struct leaf {
 186     /** The leaf identifier. */
 187     uint32_t xid;
 188
 189     /** The leaf's parent in the hierarchy.  This is the identity to which this
 190      * leaf belongs. */
 191     identity_t *parent;
 192
 193     /** GRD: The leaf's packet drop probability. */
 194     double drop_prob;
 195
 196     /** Only used for experimentation. */
 197     int delay;
 198
 199 } leaf_t;
 200
 201 /**
 202  * Contains all of the identity and sliver information associated with a
 203  * runnable instance of a local DRL node.
 204  */
 205 typedef struct drl_instance {
 206     /** An array of the node's viable leaves (slivers). */
 207     leaf_t *leaves;
 208
 209     /** The number of items in the leaf array. */
 210     int leaf_count;
 211
 212     /** Maps sliver xid to the leaf_t in the leaves array. */
 213     map_handle leaf_map;
 214
 215     /** An array of the node's machine-type identities. */
 216     identity_t **machines;
 217
 218     /** The number of items in the machines array. */
 219     int machine_count;
 220
 221     /** An array of the node's set-type identities. */
 222     identity_t **sets;
 223
 224     /** The number of items in the sets array. */
 225     int set_count;
 226
 227     /** Maps identity guid to the identity_t in either the machines or sets
 228      * arrays. */
 229     map_handle ident_map;
 230
 231     /** The lowest machine identity in the hierarchy.  This acts as the root
 232      * for the set-identity subtree. */
 233     identity_t *last_machine;
 234
 235     /** Acts as a circular array of lists used to schedule identities at
 236      * some number of intervals. */
 237     struct ident_calendar *cal;
 238
 239     /** The slot for the "current" tick in the calendar. */
 240     uint32_t cal_slot;
 241
 242 } drl_instance_t;
 243
 244 /** Represents the local node. */
 245 typedef struct limiter {
 246     /** The limiter's local address in dotted quad notation. */
 247     char *ip;
 248
 249     /** The node's individual (administrative) limit.  This node should set a
 250      * limit above this value, even when DRL says it can do so. */
 251     uint32_t nodelimit;
 252
 253     /** The DRL policy (GRD, FPS) this node is using. */
 254     enum policies policy;
 255
 256     /** The estimate interval (in milliseconds). */
 257     int estintms;
 258
 259     /** A lock to protect the state of identities so that they can be
 260      * created/destroyed without harming any other, currently active idents.
 261      *
 262      * I made this an rwlock because it allows for much better parallelism.
 263      * Creating/removing identities is uncommon, and most of the time this
 264      * doesn't need to be held for writing. */
 265     pthread_rwlock_t limiter_lock;
 266
 267     /** The currently running DRL instance. */
 268     drl_instance_t stable_instance;
 269
 270     /** The next instance - if it validates.  When the XML config file is
 271      * re-read, the new structures will be incorporated into this instance.  If
 272      * everything checks out, the old (stable) instance will be freed, and this
 273      * will be copied into stable_instance. */
 274     drl_instance_t new_instance;
 275
 276     /* Communication fields. */
 277
 278     /** The limiter's local address as an integer (net byte order). */
 279     in_addr_t localaddr;
 280
 281     /** The local port on which to listen (net byte order). */
 282     in_port_t port;
 283
 284     /** Local UDP communication socket. */
 285     int udp_socket;
 286
 287 #if 0
 288     /** Local TCP communication socket. */
 289     int tcp_socket;
 290 #endif
 291
 292     /** Limiter-wide UDP receive thread. */
 293     pthread_t udp_recv_thread;
 294
 295 #if 0
 296     /** Limiter-wide TCP thread for accepting incoming connections. */
 297     pthread_t tcp_acpt_thread;
 298 #endif
 299
 300 } limiter_t;
 301
 302 #endif