sys/netinet/ipfw/dn_sched.h

   1 /*
   2  * Copyright (c) 2010 Riccardo Panicucci, Luigi Rizzo, 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  * The API to write a packet scheduling algorithm for dummynet.
  29  *
  30  * $FreeBSD: head/sys/netinet/ipfw/dn_sched.h 204591 2010-03-02 17:40:48Z luigi $
  31  */
  32
  33 #ifndef _DN_SCHED_H
  34 #define _DN_SCHED_H
  35
  36 #define DN_MULTIQUEUE   0x01
  37 /*
  38  * Descriptor for a scheduling algorithm.
  39  * Contains all function pointers for a given scheduler
  40  * This is typically created when a module is loaded, and stored
  41  * in a global list of schedulers.
  42  */
  43 struct dn_alg {
  44         uint32_t type;           /* the scheduler type */
  45         const char *name;   /* scheduler name */
  46         uint32_t flags; /* DN_MULTIQUEUE if supports multiple queues */
  47
  48         /*
  49          * The following define the size of 3 optional data structures
  50          * that may need to be allocated at runtime, and are appended
  51          * to each of the base data structures: scheduler, sched.inst,
  52          * and queue. We don't have a per-flowset structure.
  53          */
  54         /*    + parameters attached to the template, e.g.
  55          *      default queue sizes, weights, quantum size, and so on;
  56          */
  57         size_t schk_datalen;
  58
  59         /*    + per-instance parameters, such as timestamps,
  60          *      containers for queues, etc;
  61          */
  62         size_t si_datalen;
  63
  64         size_t q_datalen;       /* per-queue parameters (e.g. S,F) */
  65
  66         /*
  67          * Methods implemented by the scheduler:
  68          * enqueue      enqueue packet 'm' on scheduler 's', queue 'q'.
  69          *      q is NULL for !MULTIQUEUE.
  70          *      Return 0 on success, 1 on drop (packet consumed anyways).
  71          *      Note that q should be interpreted only as a hint
  72          *      on the flow that the mbuf belongs to: while a
  73          *      scheduler will normally enqueue m into q, it is ok
  74          *      to leave q alone and put the mbuf elsewhere.
  75          *      This function is called in two cases:
  76          *       - when a new packet arrives to the scheduler;
  77          *       - when a scheduler is reconfigured. In this case the
  78          *         call is issued by the new_queue callback, with a
  79          *         non empty queue (q) and m pointing to the first
  80          *         mbuf in the queue. For this reason, the function
  81          *         should internally check for (m != q->mq.head)
  82          *         before calling dn_enqueue().
  83          *
  84          * dequeue      Called when scheduler instance 's' can
  85          *      dequeue a packet. Return NULL if none are available.
  86          *      XXX what about non work-conserving ?
  87          *
  88          * config       called on 'sched X config ...', normally writes
  89          *      in the area of size sch_arg
  90          *
  91          * destroy      called on 'sched delete', frees everything
  92          *      in sch_arg (other parts are handled by more specific
  93          *      functions)
  94          *
  95          * new_sched    called when a new instance is created, e.g.
  96          *      to create the local queue for !MULTIQUEUE, set V or
  97          *      copy parameters for WFQ, and so on.
  98          *
  99          * free_sched   called when deleting an instance, cleans
 100          *      extra data in the per-instance area.
 101          *
 102          * new_fsk      called when a flowset is linked to a scheduler,
 103          *      e.g. to validate parameters such as weights etc.
 104          * free_fsk     when a flowset is unlinked from a scheduler.
 105          *      (probably unnecessary)
 106          *
 107          * new_queue    called to set the per-queue parameters,
 108          *      e.g. S and F, adjust sum of weights in the parent, etc.
 109          *
 110          *      The new_queue callback is normally called from when
 111          *      creating a new queue. In some cases (such as a
 112          *      scheduler change or reconfiguration) it can be called
 113          *      with a non empty queue. In this case, the queue
 114          *      In case of non empty queue, the new_queue callback could
 115          *      need to call the enqueue function. In this case,
 116          *      the callback should eventually call enqueue() passing
 117          *      as m the first element in the queue.
 118          *
 119          * free_queue   actions related to a queue removal, e.g. undo
 120          *      all the above. If the queue has data in it, also remove
 121          *      from the scheduler. This can e.g. happen during a reconfigure.
 122          *      If safe == 1 remove the queue only if the scheduler no longer
 123          *      need it, otherwise delete it even if the scheduler is using
 124          *      it. Usually, the flag safe is set when the drain routine is
 125          *      running to delete idle queues.
 126          */
 127         int (*enqueue)(struct dn_sch_inst *, struct dn_queue *,
 128                 struct mbuf *);
 129         struct mbuf * (*dequeue)(struct dn_sch_inst *);
 130
 131         int (*config)(struct dn_schk *);
 132         int (*destroy)(struct dn_schk*);
 133         int (*new_sched)(struct dn_sch_inst *);
 134         int (*free_sched)(struct dn_sch_inst *);
 135         int (*new_fsk)(struct dn_fsk *f);
 136         int (*free_fsk)(struct dn_fsk *f);
 137         int (*new_queue)(struct dn_queue *q);
 138         int (*free_queue)(struct dn_queue *q, int safe);
 139
 140         /* run-time fields */
 141         int ref_count;      /* XXX number of instances in the system */
 142         SLIST_ENTRY(dn_alg) next; /* Next scheduler in the list */
 143 };
 144
 145 /* MSVC does not support initializers so we need this ugly macro */
 146 #ifdef _WIN32
 147 #define _SI(fld)
 148 #else
 149 #define _SI(fld)        fld
 150 #endif
 151
 152 /*
 153  * Additionally, dummynet exports some functions and macros
 154  * to be used by schedulers:
 155  */
 156
 157 void dn_free_pkts(struct mbuf *mnext);
 158 int dn_enqueue(struct dn_queue *q, struct mbuf* m, int drop);
 159 /* bound a variable between min and max */
 160 int ipdn_bound_var(int *v, int dflt, int lo, int hi, const char *msg);
 161
 162 /*
 163  * Extract the head of a queue, update stats. Must be the very last
 164  * thing done on a dequeue as the queue itself may go away.
 165  */
 166 static __inline struct mbuf*
 167 dn_dequeue(struct dn_queue *q)
 168 {
 169         struct mbuf *m = q->mq.head;
 170         if (m == NULL)
 171                 return NULL;
 172         q->mq.head = m->m_nextpkt;
 173
 174         /* Update stats for the queue */
 175         q->ni.length--;
 176         q->ni.len_bytes -= m->m_pkthdr.len;
 177         /* When the queue becomes idle, update idle_time (used by RED)
 178          * and also update the count of idle queues (for garbage collection).
 179          */
 180         if (q->ni.length == 0) {
 181                 dn_cfg.idle_queue++;
 182                 q->q_time = dn_cfg.curr_time;
 183         }
 184         if (q->_si) {
 185                 struct dn_flow *ni = &(q->_si->ni);
 186                 /* update stats for the scheduler instance, and keep track
 187                  * of idle scheduler instances if needed
 188                  */
 189                 ni->length--;
 190                 ni->len_bytes -= m->m_pkthdr.len;
 191                 if (ni->length == 0)
 192                         dn_cfg.idle_si++;
 193         }
 194         return m;
 195 }
 196
 197 int dn_sched_modevent(module_t mod, int cmd, void *arg);
 198
 199 #define DECLARE_DNSCHED_MODULE(name, dnsched)                   \
 200         static moduledata_t name##_mod = {                      \
 201                 #name, dn_sched_modevent, dnsched               \
 202         };                                                      \
 203         DECLARE_MODULE(name, name##_mod,                        \
 204                 SI_SUB_PROTO_IFATTACHDOMAIN, SI_ORDER_ANY);     \
 205         MODULE_DEPEND(name, dummynet, 3, 3, 3);
 206 #endif /* _DN_SCHED_H */