sys/netpfil/ipfw/ip_dn_private.h

   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         /* counters of objects -- used for reporting space */
 129         int     schk_count;
 130         int     si_count;
 131         int     fsk_count;
 132         int     queue_count;
 133
 134         /* ticks and other stuff */
 135         uint64_t        curr_time;
 136         /* flowsets and schedulers are in hash tables, with 'hash_size'
 137          * buckets. fshash is looked up at every packet arrival
 138          * so better be generous if we expect many entries.
 139          */
 140         struct dn_ht    *fshash;
 141         struct dn_ht    *schedhash;
 142         /* list of flowsets without a scheduler -- use sch_chain */
 143         struct dn_fsk_head      fsu;    /* list of unlinked flowsets */
 144         struct dn_alg_head      schedlist;      /* list of algorithms */
 145 #ifdef NEW_AQM
 146         struct dn_aqm_head      aqmlist;        /* list of AQMs */
 147 #endif
 148
 149         /* Store the fs/sch to scan when draining. The value is the
 150          * bucket number of the hash table. Expire can be disabled
 151          * with net.inet.ip.dummynet.expire=0, or it happens every
 152          * expire ticks.
 153          **/
 154         int drain_fs;
 155         int drain_sch;
 156         uint32_t expire;
 157         uint32_t expire_cycle;  /* tick count */
 158
 159         int init_done;
 160
 161         /* if the upper half is busy doing something long,
 162          * can set the busy flag and we will enqueue packets in
 163          * a queue for later processing.
 164          */
 165         int     busy;
 166         struct  mq      pending;
 167
 168 #ifdef _KERNEL
 169         /*
 170          * This file is normally used in the kernel, unless we do
 171          * some userland tests, in which case we do not need a mtx.
 172          * uh_mtx arbitrates between system calls and also
 173          * protects fshash, schedhash and fsunlinked.
 174          * These structures are readonly for the lower half.
 175          * bh_mtx protects all other structures which may be
 176          * modified upon packet arrivals
 177          */
 178 #if defined( __linux__ ) || defined( _WIN32 )
 179         spinlock_t uh_mtx;
 180         spinlock_t bh_mtx;
 181 #else
 182         struct mtx uh_mtx;
 183         struct mtx bh_mtx;
 184 #endif
 185
 186 #endif /* _KERNEL */
 187 };
 188
 189 /*
 190  * Delay line, contains all packets on output from a link.
 191  * Every scheduler instance has one.
 192  */
 193 struct delay_line {
 194         struct dn_id oid;
 195         struct dn_sch_inst *si;
 196         struct mq mq;
 197 };
 198
 199 /*
 200  * The kernel side of a flowset. It is linked in a hash table
 201  * of flowsets, and in a list of children of their parent scheduler.
 202  * qht is either the queue or (if HAVE_MASK) a hash table queues.
 203  * Note that the mask to use is the (flow_mask|sched_mask), which
 204  * changes as we attach/detach schedulers. So we store it here.
 205  *
 206  * XXX If we want to add scheduler-specific parameters, we need to
 207  * put them in external storage because the scheduler may not be
 208  * available when the fsk is created.
 209  */
 210 struct dn_fsk { /* kernel side of a flowset */
 211         struct dn_fs fs;
 212         SLIST_ENTRY(dn_fsk) fsk_next;   /* hash chain for fshash */
 213
 214         struct ipfw_flow_id fsk_mask;
 215
 216         /* qht is a hash table of queues, or just a single queue
 217          * a bit in fs.flags tells us which one
 218          */
 219         struct dn_ht    *qht;
 220         struct dn_schk *sched;          /* Sched we are linked to */
 221         SLIST_ENTRY(dn_fsk) sch_chain;  /* list of fsk attached to sched */
 222
 223         /* bucket index used by drain routine to drain queues for this
 224          * flowset
 225          */
 226         int drain_bucket;
 227         /* Parameter realted to RED / GRED */
 228         /* original values are in dn_fs*/
 229         int w_q ;               /* queue weight (scaled) */
 230         int max_th ;            /* maximum threshold for queue (scaled) */
 231         int min_th ;            /* minimum threshold for queue (scaled) */
 232         int max_p ;             /* maximum value for p_b (scaled) */
 233
 234         u_int c_1 ;             /* max_p/(max_th-min_th) (scaled) */
 235         u_int c_2 ;             /* max_p*min_th/(max_th-min_th) (scaled) */
 236         u_int c_3 ;             /* for GRED, (1-max_p)/max_th (scaled) */
 237         u_int c_4 ;             /* for GRED, 1 - 2*max_p (scaled) */
 238         u_int * w_q_lookup ;    /* lookup table for computing (1-w_q)^t */
 239         u_int lookup_depth ;    /* depth of lookup table */
 240         int lookup_step ;       /* granularity inside the lookup table */
 241         int lookup_weight ;     /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
 242         int avg_pkt_size ;      /* medium packet size */
 243         int max_pkt_size ;      /* max packet size */
 244 #ifdef NEW_AQM
 245         struct dn_aqm *aqmfp;   /* Pointer to AQM functions */
 246         void *aqmcfg;   /* configuration parameters for AQM */
 247 #endif
 248 };
 249
 250 /*
 251  * A queue is created as a child of a flowset unless it belongs to
 252  * a !MULTIQUEUE scheduler. It is normally in a hash table in the
 253  * flowset. fs always points to the parent flowset.
 254  * si normally points to the sch_inst, unless the flowset has been
 255  * detached from the scheduler -- in this case si == NULL and we
 256  * should not enqueue.
 257  */
 258 struct dn_queue {
 259         struct dn_flow ni;      /* oid, flow_id, stats */
 260         struct mq mq;   /* packets queue */
 261         struct dn_sch_inst *_si;        /* owner scheduler instance */
 262         SLIST_ENTRY(dn_queue) q_next; /* hash chain list for qht */
 263         struct dn_fsk *fs;              /* parent flowset. */
 264
 265         /* RED parameters */
 266         int avg;                /* average queue length est. (scaled) */
 267         int count;              /* arrivals since last RED drop */
 268         int random;             /* random value (scaled) */
 269         uint64_t q_time;        /* start of queue idle time */
 270 #ifdef NEW_AQM
 271         void *aqm_status;       /* per-queue status variables*/
 272 #endif
 273
 274 };
 275
 276 /*
 277  * The kernel side of a scheduler. Contains the userland config,
 278  * a link, pointer to extra config arguments from command line,
 279  * kernel flags, and a pointer to the scheduler methods.
 280  * It is stored in a hash table, and holds a list of all
 281  * flowsets and scheduler instances.
 282  * XXX sch must be at the beginning, see schk_hash().
 283  */
 284 struct dn_schk {
 285         struct dn_sch sch;
 286         struct dn_alg *fp;      /* Pointer to scheduler functions */
 287         struct dn_link link;    /* The link, embedded */
 288         struct dn_profile *profile; /* delay profile, if any */
 289         struct dn_id *cfg;      /* extra config arguments */
 290
 291         SLIST_ENTRY(dn_schk) schk_next;  /* hash chain for schedhash */
 292
 293         struct dn_fsk_head fsk_list;  /* all fsk linked to me */
 294         struct dn_fsk *fs;      /* Flowset for !MULTIQUEUE */
 295
 296         /* bucket index used by the drain routine to drain the scheduler
 297          * instance for this flowset.
 298          */
 299         int drain_bucket;
 300
 301         /* Hash table of all instances (through sch.sched_mask)
 302          * or single instance if no mask. Always valid.
 303          */
 304         struct dn_ht    *siht;
 305 };
 306
 307 /*
 308  * Scheduler instance.
 309  * Contains variables and all queues relative to a this instance.
 310  * This struct is created a runtime.
 311  */
 312 struct dn_sch_inst {
 313         struct dn_flow  ni;     /* oid, flowid and stats */
 314         SLIST_ENTRY(dn_sch_inst) si_next; /* hash chain for siht */
 315         struct delay_line dline;
 316         struct dn_schk *sched;  /* the template */
 317         int             kflags; /* DN_ACTIVE */
 318
 319         int64_t credit;         /* bits I can transmit (more or less). */
 320         uint64_t sched_time;    /* time link was scheduled in ready_heap */
 321         uint64_t idle_time;     /* start of scheduler instance idle time */
 322
 323         /* q_count is the number of queues that this instance is using.
 324          * The counter is incremented or decremented when
 325          * a reference from the queue is created or deleted.
 326          * It is used to make sure that a scheduler instance can be safely
 327          * deleted by the drain routine. See notes below.
 328          */
 329         int q_count;
 330
 331 };
 332
 333 /*
 334  * NOTE about object drain.
 335  * The system will automatically (XXX check when) drain queues and
 336  * scheduler instances when they are idle.
 337  * A queue is idle when it has no packets; an instance is idle when
 338  * it is not in the evheap heap, and the corresponding delay line is empty.
 339  * A queue can be safely deleted when it is idle because of the scheduler
 340  * function xxx_free_queue() will remove any references to it.
 341  * An instance can be only deleted when no queues reference it. To be sure
 342  * of that, a counter (q_count) stores the number of queues that are pointing
 343  * to the instance.
 344  *
 345  * XXX
 346  * Order of scan:
 347  * - take all flowset in a bucket for the flowset hash table
 348  * - take all queues in a bucket for the flowset
 349  * - increment the queue bucket
 350  * - scan next flowset bucket
 351  * Nothing is done if a bucket contains no entries.
 352  *
 353  * The same schema is used for sceduler instances
 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 /*
 371  * Packets processed by dummynet have an mbuf tag associated with
 372  * them that carries their dummynet state.
 373  * Outside dummynet, only the 'rule' field is relevant, and it must
 374  * be at the beginning of the structure.
 375  */
 376 struct dn_pkt_tag {
 377         struct ipfw_rule_ref rule;      /* matching rule        */
 378
 379         /* second part, dummynet specific */
 380         int dn_dir;             /* action when packet comes out.*/
 381                                 /* see ip_fw_private.h          */
 382         uint64_t output_time;   /* when the pkt is due for delivery*/
 383         struct ifnet *ifp;      /* interface, for ip_output     */
 384         struct _ip6dn_args ip6opt;      /* XXX ipv6 options     */
 385         uint16_t iphdr_off;     /* IP header offset for mtodo() */
 386 };
 387
 388 /*
 389  * Possible values for dn_dir. XXXGL: this needs to be reviewed
 390  * and converted to same values ip_fw_args.flags use.
 391  */
 392 enum {
 393         DIR_OUT =       0,
 394         DIR_IN =        1,
 395         DIR_FWD =       2,
 396         DIR_DROP =      3,
 397         PROTO_LAYER2 =  0x4, /* set for layer 2 */
 398         PROTO_IPV4 =    0x08,
 399         PROTO_IPV6 =    0x10,
 400         PROTO_IFB =     0x0c, /* layer2 + ifbridge */
 401 };
 402
 403 extern struct dn_parms dn_cfg;
 404 //VNET_DECLARE(struct dn_parms, _base_dn_cfg);
 405 //#define dn_cfg        VNET(_base_dn_cfg)
 406
 407 int dummynet_io(struct mbuf **, struct ip_fw_args *);
 408 void dummynet_task(void *context, int pending);
 409 void dn_reschedule(void);
 410 struct dn_pkt_tag * dn_tag_get(struct mbuf *m);
 411
 412 struct dn_queue *ipdn_q_find(struct dn_fsk *, struct dn_sch_inst *,
 413         struct ipfw_flow_id *);
 414 struct dn_sch_inst *ipdn_si_find(struct dn_schk *, struct ipfw_flow_id *);
 415
 416 /*
 417  * copy_range is a template for requests for ranges of pipes/queues/scheds.
 418  * The number of ranges is variable and can be derived by o.len.
 419  * As a default, we use a small number of entries so that the struct
 420  * fits easily on the stack and is sufficient for most common requests.
 421  */
 422 #define DEFAULT_RANGES  5
 423 struct copy_range {
 424         struct dn_id o;
 425         uint32_t        r[ 2 * DEFAULT_RANGES ];
 426 };
 427
 428 struct copy_args {
 429         char **start;
 430         char *end;
 431         int flags;
 432         int type;
 433         struct copy_range *extra;       /* extra filtering */
 434 };
 435
 436 struct sockopt;
 437 int ip_dummynet_compat(struct sockopt *sopt);
 438 int dummynet_get(struct sockopt *sopt, void **compat);
 439 int dn_c_copy_q (void *_ni, void *arg);
 440 int dn_c_copy_pipe(struct dn_schk *s, struct copy_args *a, int nq);
 441 int dn_c_copy_fs(struct dn_fsk *f, struct copy_args *a, int nq);
 442 int dn_compat_copy_queue(struct copy_args *a, void *_o);
 443 int dn_compat_copy_pipe(struct copy_args *a, void *_o);
 444 int copy_data_helper_compat(void *_o, void *_arg);
 445 int dn_compat_calc_size(void);
 446 int do_config(void *p, int l);
 447
 448 /* function to drain idle object */
 449 void dn_drain_scheduler(void);
 450 void dn_drain_queue(void);
 451
 452 #ifdef NEW_AQM
 453 int ecn_mark(struct mbuf* m);
 454
 455 /* moved from ip_dn_io.c to here to be available for AQMs modules*/
 456 static inline void
 457 mq_append(struct mq *q, struct mbuf *m)
 458 {
 459 #ifdef USERSPACE
 460         // buffers from netmap need to be copied
 461         // XXX note that the routine is not expected to fail
 462         ND("append %p to %p", m, q);
 463         if (m->m_flags & M_STACK) {
 464                 struct mbuf *m_new;
 465                 void *p;
 466                 int l, ofs;
 467
 468                 ofs = m->m_data - m->__m_extbuf;
 469                 // XXX allocate
 470                 MGETHDR(m_new, M_NOWAIT, MT_DATA);
 471                 ND("*** WARNING, volatile buf %p ext %p %d dofs %d m_new %p",
 472                         m, m->__m_extbuf, m->__m_extlen, ofs, m_new);
 473                 p = m_new->__m_extbuf;  /* new pointer */
 474                 l = m_new->__m_extlen;  /* new len */
 475                 if (l <= m->__m_extlen) {
 476                         panic("extlen too large");
 477                 }
 478
 479                 *m_new = *m;    // copy
 480                 m_new->m_flags &= ~M_STACK;
 481                 m_new->__m_extbuf = p; // point to new buffer
 482                 _pkt_copy(m->__m_extbuf, p, m->__m_extlen);
 483                 m_new->m_data = p + ofs;
 484                 m = m_new;
 485         }
 486 #endif /* USERSPACE */
 487         if (q->head == NULL)
 488                 q->head = m;
 489         else
 490                 q->tail->m_nextpkt = m;
 491         q->count++;
 492         q->tail = m;
 493         m->m_nextpkt = NULL;
 494 }
 495 #endif /* NEW_AQM */
 496
 497 #endif /* _IP_DN_PRIVATE_H */