1 /*- 2 * Copyright (c) 2010 Luigi Rizzo, Riccardo Panicucci, Universita` di Pisa 3 * All rights reserved 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27 /* 28 * internal dummynet APIs. 29 * 30 * $FreeBSD$ 31 */ 32 33 #ifndef _IP_DN_PRIVATE_H 34 #define _IP_DN_PRIVATE_H 35 36 /* debugging support 37 * use ND() to remove debugging, D() to print a line, 38 * DX(level, ...) to print above a certain level 39 * If you redefine D() you are expected to redefine all. 40 */ 41 #ifndef D 42 #define ND(fmt, ...) do {} while (0) 43 #define D1(fmt, ...) do {} while (0) 44 #define D(fmt, ...) printf("%-10s " fmt "\n", \ 45 __FUNCTION__, ## __VA_ARGS__) 46 #define DX(lev, fmt, ...) do { \ 47 if (dn_cfg.debug > lev) D(fmt, ## __VA_ARGS__); } while (0) 48 #endif 49 50 MALLOC_DECLARE(M_DUMMYNET); 51 52 #ifndef __linux__ 53 #define div64(a, b) ((int64_t)(a) / (int64_t)(b)) 54 #endif 55 56 #define DN_LOCK_INIT() do { \ 57 mtx_init(&dn_cfg.uh_mtx, "dn_uh", NULL, MTX_DEF); \ 58 mtx_init(&dn_cfg.bh_mtx, "dn_bh", NULL, MTX_DEF); \ 59 } while (0) 60 #define DN_LOCK_DESTROY() do { \ 61 mtx_destroy(&dn_cfg.uh_mtx); \ 62 mtx_destroy(&dn_cfg.bh_mtx); \ 63 } while (0) 64 #if 0 /* not used yet */ 65 #define DN_UH_RLOCK() mtx_lock(&dn_cfg.uh_mtx) 66 #define DN_UH_RUNLOCK() mtx_unlock(&dn_cfg.uh_mtx) 67 #define DN_UH_WLOCK() mtx_lock(&dn_cfg.uh_mtx) 68 #define DN_UH_WUNLOCK() mtx_unlock(&dn_cfg.uh_mtx) 69 #define DN_UH_LOCK_ASSERT() mtx_assert(&dn_cfg.uh_mtx, MA_OWNED) 70 #endif 71 72 #define DN_BH_RLOCK() mtx_lock(&dn_cfg.uh_mtx) 73 #define DN_BH_RUNLOCK() mtx_unlock(&dn_cfg.uh_mtx) 74 #define DN_BH_WLOCK() mtx_lock(&dn_cfg.uh_mtx) 75 #define DN_BH_WUNLOCK() mtx_unlock(&dn_cfg.uh_mtx) 76 #define DN_BH_LOCK_ASSERT() mtx_assert(&dn_cfg.uh_mtx, MA_OWNED) 77 78 SLIST_HEAD(dn_schk_head, dn_schk); 79 SLIST_HEAD(dn_sch_inst_head, dn_sch_inst); 80 SLIST_HEAD(dn_fsk_head, dn_fsk); 81 SLIST_HEAD(dn_queue_head, dn_queue); 82 SLIST_HEAD(dn_alg_head, dn_alg); 83 84 #ifdef NEW_AQM 85 SLIST_HEAD(dn_aqm_head, dn_aqm); /* for new AQMs */ 86 #endif 87 88 struct mq { /* a basic queue of packets*/ 89 struct mbuf *head, *tail; 90 int count; 91 }; 92 93 static inline void 94 set_oid(struct dn_id *o, int type, int len) 95 { 96 o->type = type; 97 o->len = len; 98 o->subtype = 0; 99 } 100 101 /* 102 * configuration and global data for a dummynet instance 103 * 104 * When a configuration is modified from userland, 'id' is incremented 105 * so we can use the value to check for stale pointers. 106 */ 107 struct dn_parms { 108 uint32_t id; /* configuration version */ 109 110 /* defaults (sysctl-accessible) */ 111 int red_lookup_depth; 112 int red_avg_pkt_size; 113 int red_max_pkt_size; 114 int hash_size; 115 int max_hash_size; 116 long byte_limit; /* max queue sizes */ 117 long slot_limit; 118 119 int io_fast; 120 int debug; 121 122 /* timekeeping */ 123 struct timeval prev_t; /* last time dummynet_tick ran */ 124 struct dn_heap evheap; /* scheduled events */ 125 126 /* counters of objects -- used for reporting space */ 127 int schk_count; 128 int si_count; 129 int fsk_count; 130 int queue_count; 131 132 /* ticks and other stuff */ 133 uint64_t curr_time; 134 /* flowsets and schedulers are in hash tables, with 'hash_size' 135 * buckets. fshash is looked up at every packet arrival 136 * so better be generous if we expect many entries. 137 */ 138 struct dn_ht *fshash; 139 struct dn_ht *schedhash; 140 /* list of flowsets without a scheduler -- use sch_chain */ 141 struct dn_fsk_head fsu; /* list of unlinked flowsets */ 142 struct dn_alg_head schedlist; /* list of algorithms */ 143 #ifdef NEW_AQM 144 struct dn_aqm_head aqmlist; /* list of AQMs */ 145 #endif 146 147 /* Store the fs/sch to scan when draining. The value is the 148 * bucket number of the hash table. Expire can be disabled 149 * with net.inet.ip.dummynet.expire=0, or it happens every 150 * expire ticks. 151 **/ 152 int drain_fs; 153 int drain_sch; 154 uint32_t expire; 155 uint32_t expire_cycle; /* tick count */ 156 157 int init_done; 158 159 /* if the upper half is busy doing something long, 160 * can set the busy flag and we will enqueue packets in 161 * a queue for later processing. 162 */ 163 int busy; 164 struct mq pending; 165 166 #ifdef _KERNEL 167 /* 168 * This file is normally used in the kernel, unless we do 169 * some userland tests, in which case we do not need a mtx. 170 * uh_mtx arbitrates between system calls and also 171 * protects fshash, schedhash and fsunlinked. 172 * These structures are readonly for the lower half. 173 * bh_mtx protects all other structures which may be 174 * modified upon packet arrivals 175 */ 176 #if defined( __linux__ ) || defined( _WIN32 ) 177 spinlock_t uh_mtx; 178 spinlock_t bh_mtx; 179 #else 180 struct mtx uh_mtx; 181 struct mtx bh_mtx; 182 #endif 183 184 #endif /* _KERNEL */ 185 }; 186 187 /* 188 * Delay line, contains all packets on output from a link. 189 * Every scheduler instance has one. 190 */ 191 struct delay_line { 192 struct dn_id oid; 193 struct dn_sch_inst *si; 194 struct mq mq; 195 }; 196 197 /* 198 * The kernel side of a flowset. It is linked in a hash table 199 * of flowsets, and in a list of children of their parent scheduler. 200 * qht is either the queue or (if HAVE_MASK) a hash table queues. 201 * Note that the mask to use is the (flow_mask|sched_mask), which 202 * changes as we attach/detach schedulers. So we store it here. 203 * 204 * XXX If we want to add scheduler-specific parameters, we need to 205 * put them in external storage because the scheduler may not be 206 * available when the fsk is created. 207 */ 208 struct dn_fsk { /* kernel side of a flowset */ 209 struct dn_fs fs; 210 SLIST_ENTRY(dn_fsk) fsk_next; /* hash chain for fshash */ 211 212 struct ipfw_flow_id fsk_mask; 213 214 /* qht is a hash table of queues, or just a single queue 215 * a bit in fs.flags tells us which one 216 */ 217 struct dn_ht *qht; 218 struct dn_schk *sched; /* Sched we are linked to */ 219 SLIST_ENTRY(dn_fsk) sch_chain; /* list of fsk attached to sched */ 220 221 /* bucket index used by drain routine to drain queues for this 222 * flowset 223 */ 224 int drain_bucket; 225 /* Parameter realted to RED / GRED */ 226 /* original values are in dn_fs*/ 227 int w_q ; /* queue weight (scaled) */ 228 int max_th ; /* maximum threshold for queue (scaled) */ 229 int min_th ; /* minimum threshold for queue (scaled) */ 230 int max_p ; /* maximum value for p_b (scaled) */ 231 232 u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */ 233 u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */ 234 u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */ 235 u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */ 236 u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */ 237 u_int lookup_depth ; /* depth of lookup table */ 238 int lookup_step ; /* granularity inside the lookup table */ 239 int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */ 240 int avg_pkt_size ; /* medium packet size */ 241 int max_pkt_size ; /* max packet size */ 242 #ifdef NEW_AQM 243 struct dn_aqm *aqmfp; /* Pointer to AQM functions */ 244 void *aqmcfg; /* configuration parameters for AQM */ 245 #endif 246 }; 247 248 /* 249 * A queue is created as a child of a flowset unless it belongs to 250 * a !MULTIQUEUE scheduler. It is normally in a hash table in the 251 * flowset. fs always points to the parent flowset. 252 * si normally points to the sch_inst, unless the flowset has been 253 * detached from the scheduler -- in this case si == NULL and we 254 * should not enqueue. 255 */ 256 struct dn_queue { 257 struct dn_flow ni; /* oid, flow_id, stats */ 258 struct mq mq; /* packets queue */ 259 struct dn_sch_inst *_si; /* owner scheduler instance */ 260 SLIST_ENTRY(dn_queue) q_next; /* hash chain list for qht */ 261 struct dn_fsk *fs; /* parent flowset. */ 262 263 /* RED parameters */ 264 int avg; /* average queue length est. (scaled) */ 265 int count; /* arrivals since last RED drop */ 266 int random; /* random value (scaled) */ 267 uint64_t q_time; /* start of queue idle time */ 268 #ifdef NEW_AQM 269 void *aqm_status; /* per-queue status variables*/ 270 #endif 271 272 }; 273 274 /* 275 * The kernel side of a scheduler. Contains the userland config, 276 * a link, pointer to extra config arguments from command line, 277 * kernel flags, and a pointer to the scheduler methods. 278 * It is stored in a hash table, and holds a list of all 279 * flowsets and scheduler instances. 280 * XXX sch must be at the beginning, see schk_hash(). 281 */ 282 struct dn_schk { 283 struct dn_sch sch; 284 struct dn_alg *fp; /* Pointer to scheduler functions */ 285 struct dn_link link; /* The link, embedded */ 286 struct dn_profile *profile; /* delay profile, if any */ 287 struct dn_id *cfg; /* extra config arguments */ 288 289 SLIST_ENTRY(dn_schk) schk_next; /* hash chain for schedhash */ 290 291 struct dn_fsk_head fsk_list; /* all fsk linked to me */ 292 struct dn_fsk *fs; /* Flowset for !MULTIQUEUE */ 293 294 /* bucket index used by the drain routine to drain the scheduler 295 * instance for this flowset. 296 */ 297 int drain_bucket; 298 299 /* Hash table of all instances (through sch.sched_mask) 300 * or single instance if no mask. Always valid. 301 */ 302 struct dn_ht *siht; 303 }; 304 305 306 /* 307 * Scheduler instance. 308 * Contains variables and all queues relative to a this instance. 309 * This struct is created a runtime. 310 */ 311 struct dn_sch_inst { 312 struct dn_flow ni; /* oid, flowid and stats */ 313 SLIST_ENTRY(dn_sch_inst) si_next; /* hash chain for siht */ 314 struct delay_line dline; 315 struct dn_schk *sched; /* the template */ 316 int kflags; /* DN_ACTIVE */ 317 318 int64_t credit; /* bits I can transmit (more or less). */ 319 uint64_t sched_time; /* time link was scheduled in ready_heap */ 320 uint64_t idle_time; /* start of scheduler instance idle time */ 321 322 /* q_count is the number of queues that this instance is using. 323 * The counter is incremented or decremented when 324 * a reference from the queue is created or deleted. 325 * It is used to make sure that a scheduler instance can be safely 326 * deleted by the drain routine. See notes below. 327 */ 328 int q_count; 329 330 }; 331 332 /* 333 * NOTE about object drain. 334 * The system will automatically (XXX check when) drain queues and 335 * scheduler instances when they are idle. 336 * A queue is idle when it has no packets; an instance is idle when 337 * it is not in the evheap heap, and the corresponding delay line is empty. 338 * A queue can be safely deleted when it is idle because of the scheduler 339 * function xxx_free_queue() will remove any references to it. 340 * An instance can be only deleted when no queues reference it. To be sure 341 * of that, a counter (q_count) stores the number of queues that are pointing 342 * to the instance. 343 * 344 * XXX 345 * Order of scan: 346 * - take all flowset in a bucket for the flowset hash table 347 * - take all queues in a bucket for the flowset 348 * - increment the queue bucket 349 * - scan next flowset bucket 350 * Nothing is done if a bucket contains no entries. 351 * 352 * The same schema is used for sceduler instances 353 */ 354 355 356 /* kernel-side flags. Linux has DN_DELETE in fcntl.h 357 */ 358 enum { 359 /* 1 and 2 are reserved for the SCAN flags */ 360 DN_DESTROY = 0x0004, /* destroy */ 361 DN_DELETE_FS = 0x0008, /* destroy flowset */ 362 DN_DETACH = 0x0010, 363 DN_ACTIVE = 0x0020, /* object is in evheap */ 364 DN_F_DLINE = 0x0040, /* object is a delay line */ 365 DN_DEL_SAFE = 0x0080, /* delete a queue only if no longer needed 366 * by scheduler */ 367 DN_QHT_IS_Q = 0x0100, /* in flowset, qht is a single queue */ 368 }; 369 370 extern struct dn_parms dn_cfg; 371 //VNET_DECLARE(struct dn_parms, _base_dn_cfg); 372 //#define dn_cfg VNET(_base_dn_cfg) 373 374 int dummynet_io(struct mbuf **, int , struct ip_fw_args *); 375 void dummynet_task(void *context, int pending); 376 void dn_reschedule(void); 377 378 struct dn_queue *ipdn_q_find(struct dn_fsk *, struct dn_sch_inst *, 379 struct ipfw_flow_id *); 380 struct dn_sch_inst *ipdn_si_find(struct dn_schk *, struct ipfw_flow_id *); 381 382 /* 383 * copy_range is a template for requests for ranges of pipes/queues/scheds. 384 * The number of ranges is variable and can be derived by o.len. 385 * As a default, we use a small number of entries so that the struct 386 * fits easily on the stack and is sufficient for most common requests. 387 */ 388 #define DEFAULT_RANGES 5 389 struct copy_range { 390 struct dn_id o; 391 uint32_t r[ 2 * DEFAULT_RANGES ]; 392 }; 393 394 struct copy_args { 395 char **start; 396 char *end; 397 int flags; 398 int type; 399 struct copy_range *extra; /* extra filtering */ 400 }; 401 402 struct sockopt; 403 int ip_dummynet_compat(struct sockopt *sopt); 404 int dummynet_get(struct sockopt *sopt, void **compat); 405 int dn_c_copy_q (void *_ni, void *arg); 406 int dn_c_copy_pipe(struct dn_schk *s, struct copy_args *a, int nq); 407 int dn_c_copy_fs(struct dn_fsk *f, struct copy_args *a, int nq); 408 int dn_compat_copy_queue(struct copy_args *a, void *_o); 409 int dn_compat_copy_pipe(struct copy_args *a, void *_o); 410 int copy_data_helper_compat(void *_o, void *_arg); 411 int dn_compat_calc_size(void); 412 int do_config(void *p, int l); 413 414 /* function to drain idle object */ 415 void dn_drain_scheduler(void); 416 void dn_drain_queue(void); 417 418 #ifdef NEW_AQM 419 int ecn_mark(struct mbuf* m); 420 421 /* moved from ip_dn_io.c to here to be available for AQMs modules*/ 422 static inline void 423 mq_append(struct mq *q, struct mbuf *m) 424 { 425 #ifdef USERSPACE 426 // buffers from netmap need to be copied 427 // XXX note that the routine is not expected to fail 428 ND("append %p to %p", m, q); 429 if (m->m_flags & M_STACK) { 430 struct mbuf *m_new; 431 void *p; 432 int l, ofs; 433 434 ofs = m->m_data - m->__m_extbuf; 435 // XXX allocate 436 MGETHDR(m_new, M_NOWAIT, MT_DATA); 437 ND("*** WARNING, volatile buf %p ext %p %d dofs %d m_new %p", 438 m, m->__m_extbuf, m->__m_extlen, ofs, m_new); 439 p = m_new->__m_extbuf; /* new pointer */ 440 l = m_new->__m_extlen; /* new len */ 441 if (l <= m->__m_extlen) { 442 panic("extlen too large"); 443 } 444 445 *m_new = *m; // copy 446 m_new->m_flags &= ~M_STACK; 447 m_new->__m_extbuf = p; // point to new buffer 448 _pkt_copy(m->__m_extbuf, p, m->__m_extlen); 449 m_new->m_data = p + ofs; 450 m = m_new; 451 } 452 #endif /* USERSPACE */ 453 if (q->head == NULL) 454 q->head = m; 455 else 456 q->tail->m_nextpkt = m; 457 q->count++; 458 q->tail = m; 459 m->m_nextpkt = NULL; 460 } 461 #endif /* NEW_AQM */ 462 463 #endif /* _IP_DN_PRIVATE_H */ 464