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