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