1 /* See the DRL-LICENSE file for this file's software license. */
5 * Defines the main types used by DRL.
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"
20 #include "bsd_queue.h"
22 #include "drl_state.h"
23 #include "common_accounting.h"
25 #include "samplehold.h"
27 #include "multipleinterval.h"
30 /** Represents a DRL entitiy/group. */
31 typedef struct identity {
33 /** A unique id for the identity. */
36 /** The global rate limit. */
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;
43 /** The local rate limit. */
46 /** Pointer to the identity's parent in the HTB hierarchy. */
47 struct identity *parent;
49 /** For sets, indicates the parent should be 0x10. Meaningless for machines. */
52 /** Array of the leaves that are limited by this identity. Points into the
53 * leaves array for the identity's instance. */
56 /** The number of leaves for which this identity is responsible. */
59 /** The fixed (per second) EWMA weight. */
60 double fixed_ewma_weight;
62 /** The real EWMA weight, based on the fixed weight and estimate interval.*/
65 /** Used for average rate graph generation. */
70 /** Communication data for this identity. */
75 /** The node in the HTB hierarchy whose limits will be modified by this
76 * identity. (1:1<htb_node>)*/
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.) */
83 /** FPS current weight value. */
86 /** FPS previous weight value. */
87 double last_localweight;
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. */
96 /** Keeps track of the state of FPS dampening for this identity. */
97 enum dampenings dampen_state;
101 /** GRD drop probability information. */
104 /** GRD previous drop probability information. */
105 double last_drop_prob;
107 /* Flow accounting machinery. */
109 /** Flow information that is common to all types of tables.
110 * This includes aggregate rates, update times, etc. */
111 common_accounting_t common;
113 /** The actual table. Uses a void pointer because it could be one
114 * of several different types. (standard, sample&hold, etc. ) */
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.
122 pthread_mutex_t table_mutex;
124 /* Function pointers to functions to act on the table. */
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 *);
130 /** Function to call on the table when it is periodically cleaned. */
131 int (*table_cleanup_function)(void *);
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);
137 /** Function to call when the table should be destroyed. */
138 void (*table_destroy_function)(void *);
140 #ifdef SHADOW_ACCTING
142 common_accounting_t shadow_common;
146 double localweight_copy;
147 double last_localweight_copy;
149 enum dampenings dampen_state_copy;
153 /* Scheduling bookkeeping. */
155 /** Scheduling unit that tells the limiter when to execute the main loop.*/
156 struct ident_action *loop_action;
158 /** Scheduling unit that tells the limiter when to communicate.*/
159 struct ident_action *comm_action;
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;
165 /** The number of limiter ticks that should pass before this identity should
166 * be scheduled for communication. */
167 uint32_t communication_intervals;
171 enum identity_actions { ACTION_MAINLOOP = 1, ACTION_COMMUNICATE = 2 };
173 typedef struct ident_action {
174 struct identity *ident;
175 enum identity_actions action;
178 TAILQ_ENTRY(ident_action) calendar;
182 * Represents the bottom most entity in the HTB hierarchy. For PlanetLab,
183 * this corresponds to sliver (identified by Vserver context id, or xid).
185 typedef struct leaf {
186 /** The leaf identifier. */
189 /** The leaf's parent in the hierarchy. This is the identity to which this
193 /** GRD: The leaf's packet drop probability. */
196 /** Only used for experimentation. */
202 * Contains all of the identity and sliver information associated with a
203 * runnable instance of a local DRL node.
205 typedef struct drl_instance {
206 /** An array of the node's viable leaves (slivers). */
209 /** The number of items in the leaf array. */
212 /** Maps sliver xid to the leaf_t in the leaves array. */
215 /** An array of the node's machine-type identities. */
216 identity_t **machines;
218 /** The number of items in the machines array. */
221 /** An array of the node's set-type identities. */
224 /** The number of items in the sets array. */
227 /** Maps identity guid to the identity_t in either the machines or sets
229 map_handle ident_map;
231 /** The lowest machine identity in the hierarchy. This acts as the root
232 * for the set-identity subtree. */
233 identity_t *last_machine;
235 /** Acts as a circular array of lists used to schedule identities at
236 * some number of intervals. */
237 struct ident_calendar *cal;
239 /** The slot for the "current" tick in the calendar. */
244 /** Represents the local node. */
245 typedef struct limiter {
246 /** The limiter's local address in dotted quad notation. */
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. */
253 /** The DRL policy (GRD, FPS) this node is using. */
254 enum policies policy;
256 /** The estimate interval (in milliseconds). */
259 /** A lock to protect the state of identities so that they can be
260 * created/destroyed without harming any other, currently active idents.
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;
267 /** The currently running DRL instance. */
268 drl_instance_t stable_instance;
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;
276 /* Communication fields. */
278 /** The limiter's local address as an integer (net byte order). */
281 /** The local port on which to listen (net byte order). */
284 /** Local UDP communication socket. */
288 /** Local TCP communication socket. */
292 /** Limiter-wide UDP receive thread. */
293 pthread_t udp_recv_thread;
296 /** Limiter-wide TCP thread for accepting incoming connections. */
297 pthread_t tcp_acpt_thread;