1204591Sluigi/* 2204591Sluigi * Copyright (c) 2010 Riccardo Panicucci, Luigi Rizzo, Universita` di Pisa 3204591Sluigi * All rights reserved 4204591Sluigi * 5204591Sluigi * Redistribution and use in source and binary forms, with or without 6204591Sluigi * modification, are permitted provided that the following conditions 7204591Sluigi * are met: 8204591Sluigi * 1. Redistributions of source code must retain the above copyright 9204591Sluigi * notice, this list of conditions and the following disclaimer. 10204591Sluigi * 2. Redistributions in binary form must reproduce the above copyright 11204591Sluigi * notice, this list of conditions and the following disclaimer in the 12204591Sluigi * documentation and/or other materials provided with the distribution. 13204591Sluigi * 14204591Sluigi * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15204591Sluigi * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16204591Sluigi * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17204591Sluigi * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18204591Sluigi * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19204591Sluigi * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20204591Sluigi * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21204591Sluigi * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22204591Sluigi * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23204591Sluigi * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24204591Sluigi * SUCH DAMAGE. 25204591Sluigi */ 26204591Sluigi 27204591Sluigi/* 28204591Sluigi * The API to write a packet scheduling algorithm for dummynet. 29204591Sluigi * 30204591Sluigi * $FreeBSD$ 31204591Sluigi */ 32204591Sluigi 33204591Sluigi#ifndef _DN_SCHED_H 34204591Sluigi#define _DN_SCHED_H 35204591Sluigi 36204591Sluigi#define DN_MULTIQUEUE 0x01 37204591Sluigi/* 38204591Sluigi * Descriptor for a scheduling algorithm. 39204591Sluigi * Contains all function pointers for a given scheduler 40204591Sluigi * This is typically created when a module is loaded, and stored 41204591Sluigi * in a global list of schedulers. 42204591Sluigi */ 43204591Sluigistruct dn_alg { 44204591Sluigi uint32_t type; /* the scheduler type */ 45204591Sluigi const char *name; /* scheduler name */ 46204591Sluigi uint32_t flags; /* DN_MULTIQUEUE if supports multiple queues */ 47204591Sluigi 48204591Sluigi /* 49204591Sluigi * The following define the size of 3 optional data structures 50204591Sluigi * that may need to be allocated at runtime, and are appended 51204591Sluigi * to each of the base data structures: scheduler, sched.inst, 52204591Sluigi * and queue. We don't have a per-flowset structure. 53204591Sluigi */ 54204591Sluigi /* + parameters attached to the template, e.g. 55204591Sluigi * default queue sizes, weights, quantum size, and so on; 56204591Sluigi */ 57204591Sluigi size_t schk_datalen; 58204591Sluigi 59204591Sluigi /* + per-instance parameters, such as timestamps, 60204591Sluigi * containers for queues, etc; 61204591Sluigi */ 62204591Sluigi size_t si_datalen; 63204591Sluigi 64204591Sluigi size_t q_datalen; /* per-queue parameters (e.g. S,F) */ 65204591Sluigi 66204591Sluigi /* 67204591Sluigi * Methods implemented by the scheduler: 68204591Sluigi * enqueue enqueue packet 'm' on scheduler 's', queue 'q'. 69204591Sluigi * q is NULL for !MULTIQUEUE. 70204591Sluigi * Return 0 on success, 1 on drop (packet consumed anyways). 71205414Sluigi * Note that q should be interpreted only as a hint 72205414Sluigi * on the flow that the mbuf belongs to: while a 73205414Sluigi * scheduler will normally enqueue m into q, it is ok 74205414Sluigi * to leave q alone and put the mbuf elsewhere. 75205414Sluigi * This function is called in two cases: 76205414Sluigi * - when a new packet arrives to the scheduler; 77205414Sluigi * - when a scheduler is reconfigured. In this case the 78205414Sluigi * call is issued by the new_queue callback, with a 79205414Sluigi * non empty queue (q) and m pointing to the first 80205414Sluigi * mbuf in the queue. For this reason, the function 81205414Sluigi * should internally check for (m != q->mq.head) 82205414Sluigi * before calling dn_enqueue(). 83204591Sluigi * 84204591Sluigi * dequeue Called when scheduler instance 's' can 85204591Sluigi * dequeue a packet. Return NULL if none are available. 86204591Sluigi * XXX what about non work-conserving ? 87204591Sluigi * 88204591Sluigi * config called on 'sched X config ...', normally writes 89204591Sluigi * in the area of size sch_arg 90204591Sluigi * 91204591Sluigi * destroy called on 'sched delete', frees everything 92204591Sluigi * in sch_arg (other parts are handled by more specific 93204591Sluigi * functions) 94204591Sluigi * 95204591Sluigi * new_sched called when a new instance is created, e.g. 96204591Sluigi * to create the local queue for !MULTIQUEUE, set V or 97204591Sluigi * copy parameters for WFQ, and so on. 98204591Sluigi * 99204591Sluigi * free_sched called when deleting an instance, cleans 100204591Sluigi * extra data in the per-instance area. 101204591Sluigi * 102204591Sluigi * new_fsk called when a flowset is linked to a scheduler, 103204591Sluigi * e.g. to validate parameters such as weights etc. 104204591Sluigi * free_fsk when a flowset is unlinked from a scheduler. 105204591Sluigi * (probably unnecessary) 106204591Sluigi * 107204591Sluigi * new_queue called to set the per-queue parameters, 108204591Sluigi * e.g. S and F, adjust sum of weights in the parent, etc. 109204591Sluigi * 110205414Sluigi * The new_queue callback is normally called from when 111205414Sluigi * creating a new queue. In some cases (such as a 112205414Sluigi * scheduler change or reconfiguration) it can be called 113205414Sluigi * with a non empty queue. In this case, the queue 114205414Sluigi * In case of non empty queue, the new_queue callback could 115205414Sluigi * need to call the enqueue function. In this case, 116205414Sluigi * the callback should eventually call enqueue() passing 117205414Sluigi * as m the first element in the queue. 118205414Sluigi * 119204591Sluigi * free_queue actions related to a queue removal, e.g. undo 120204591Sluigi * all the above. If the queue has data in it, also remove 121204591Sluigi * from the scheduler. This can e.g. happen during a reconfigure. 122204591Sluigi */ 123204591Sluigi int (*enqueue)(struct dn_sch_inst *, struct dn_queue *, 124204591Sluigi struct mbuf *); 125204591Sluigi struct mbuf * (*dequeue)(struct dn_sch_inst *); 126204591Sluigi 127204591Sluigi int (*config)(struct dn_schk *); 128204591Sluigi int (*destroy)(struct dn_schk*); 129204591Sluigi int (*new_sched)(struct dn_sch_inst *); 130204591Sluigi int (*free_sched)(struct dn_sch_inst *); 131204591Sluigi int (*new_fsk)(struct dn_fsk *f); 132204591Sluigi int (*free_fsk)(struct dn_fsk *f); 133204591Sluigi int (*new_queue)(struct dn_queue *q); 134204591Sluigi int (*free_queue)(struct dn_queue *q); 135204591Sluigi 136204591Sluigi /* run-time fields */ 137204591Sluigi int ref_count; /* XXX number of instances in the system */ 138204591Sluigi SLIST_ENTRY(dn_alg) next; /* Next scheduler in the list */ 139204591Sluigi}; 140204591Sluigi 141204591Sluigi/* MSVC does not support initializers so we need this ugly macro */ 142204591Sluigi#ifdef _WIN32 143206845Sluigi#define _SI(fld) 144204591Sluigi#else 145206845Sluigi#define _SI(fld) fld 146204591Sluigi#endif 147204591Sluigi 148204591Sluigi/* 149204591Sluigi * Additionally, dummynet exports some functions and macros 150204591Sluigi * to be used by schedulers: 151204591Sluigi */ 152204591Sluigi 153204591Sluigivoid dn_free_pkts(struct mbuf *mnext); 154204591Sluigiint dn_enqueue(struct dn_queue *q, struct mbuf* m, int drop); 155204591Sluigi/* bound a variable between min and max */ 156204591Sluigiint ipdn_bound_var(int *v, int dflt, int lo, int hi, const char *msg); 157204591Sluigi 158204591Sluigi/* 159204591Sluigi * Extract the head of a queue, update stats. Must be the very last 160204591Sluigi * thing done on a dequeue as the queue itself may go away. 161204591Sluigi */ 162204591Sluigistatic __inline struct mbuf* 163204591Sluigidn_dequeue(struct dn_queue *q) 164204591Sluigi{ 165204591Sluigi struct mbuf *m = q->mq.head; 166204591Sluigi if (m == NULL) 167204591Sluigi return NULL; 168204591Sluigi q->mq.head = m->m_nextpkt; 169213267Sluigi 170213267Sluigi /* Update stats for the queue */ 171204591Sluigi q->ni.length--; 172204591Sluigi q->ni.len_bytes -= m->m_pkthdr.len; 173204591Sluigi if (q->_si) { 174204591Sluigi q->_si->ni.length--; 175204591Sluigi q->_si->ni.len_bytes -= m->m_pkthdr.len; 176204591Sluigi } 177204591Sluigi if (q->ni.length == 0) /* queue is now idle */ 178204591Sluigi q->q_time = dn_cfg.curr_time; 179204591Sluigi return m; 180204591Sluigi} 181204591Sluigi 182204591Sluigiint dn_sched_modevent(module_t mod, int cmd, void *arg); 183204591Sluigi 184204591Sluigi#define DECLARE_DNSCHED_MODULE(name, dnsched) \ 185204591Sluigi static moduledata_t name##_mod = { \ 186204591Sluigi #name, dn_sched_modevent, dnsched \ 187204591Sluigi }; \ 188204591Sluigi DECLARE_MODULE(name, name##_mod, \ 189204591Sluigi SI_SUB_PROTO_IFATTACHDOMAIN, SI_ORDER_ANY); \ 190204591Sluigi MODULE_DEPEND(name, dummynet, 3, 3, 3); 191204591Sluigi#endif /* _DN_SCHED_H */ 192