Date: Wed, 20 Jan 2010 13:50:30 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r202696 - in user/luigi/ipfw3-head/sys: conf netinet/ipfw Message-ID: <201001201350.o0KDoUd7018365@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: luigi Date: Wed Jan 20 13:50:30 2010 New Revision: 202696 URL: http://svn.freebsd.org/changeset/base/202696 Log: add a round-robin scheduler Added: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_rr.c (contents, props changed) Modified: user/luigi/ipfw3-head/sys/conf/files Modified: user/luigi/ipfw3-head/sys/conf/files ============================================================================== --- user/luigi/ipfw3-head/sys/conf/files Wed Jan 20 13:34:05 2010 (r202695) +++ user/luigi/ipfw3-head/sys/conf/files Wed Jan 20 13:50:30 2010 (r202696) @@ -2451,7 +2451,8 @@ netinet/in_rmx.c optional inet netinet/ip_divert.c optional inet ipdivert ipfirewall netinet/ipfw/dn_heap.c optional inet dummynet netinet/ipfw/dn_sched_fifo.c optional inet dummynet -netinet/ipfw/dn_sched_wf2q.c optional inet dummynet +netinet/ipfw/dn_sched_rr.c optional inet dummynet +netinet/ipfw/dn_sched_wf2q.c optional inet dummynet netinet/ipfw/ip_dummynet.c optional inet dummynet netinet/ipfw/ip_dn_io.c optional inet dummynet netinet/ip_ecn.c optional inet | inet6 Added: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_rr.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_rr.c Wed Jan 20 13:50:30 2010 (r202696) @@ -0,0 +1,282 @@ +/* + * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa + * All rights reserved + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include <sys/malloc.h> +#include <sys/socket.h> +#include <sys/socketvar.h> +#include <sys/kernel.h> +#include <sys/mbuf.h> +#include <sys/module.h> +#include <net/if.h> /* IFNAMSIZ */ +#include <netinet/in.h> +#include <netinet/ip_var.h> /* ipfw_rule_ref */ +#include <netinet/ip_fw.h> /* flow_id */ +#include <netinet/ip_dummynet.h> +#include <netinet/ipfw/dn_heap.h> +#include <netinet/ipfw/ip_dn_private.h> +#include <netinet/ipfw/dn_sched.h> + +#define DN_SCHED_RR 3 // XXX Where? + +/* rr_queue is appended to a struct new_queue */ +struct rr_queue { + struct new_queue *parent; /* Pointer to standard queue */ + int status; /* 1: queue is in the list */ + TAILQ_ENTRY(rr_queue) entries; /* List of active queue */ + int credit; /* Number of bytes to transmit */ + int quantum; /* quantum * C */ +}; +TAILQ_HEAD(rr_queue_head, rr_queue); + +/* struct rr_schk contains global config parameters + * and is right after new_schk + */ +struct rr_schk { + int min_q; /* Min quantum */ + int max_q; /* Max quantum */ + int q_bytes; /* Bytes per quantum */ +}; + +/* per-instance info, right after new_sch_inst */ +struct rr_si { + struct rr_queue *pointer; /* Pointer to current queue */ + struct rr_queue_head q_list; /* List of queues */ + int queue_n; /* number of queues in the list */ +}; + +static inline void +insert_queue(struct rr_queue *q, struct rr_si *si) +{ + + if (TAILQ_EMPTY(&si->q_list)) { /* or si->queue_n == 0 */ + TAILQ_INSERT_HEAD(&si->q_list, q, entries); + si->pointer = q; + } + else { + TAILQ_INSERT_BEFORE(si->pointer, q, entries); + } + q->status = 1; + si->queue_n++; +} + +static inline void +remove_queue(struct rr_queue *q, struct rr_si *si) +{ + TAILQ_REMOVE(&si->q_list, q, entries); + q->status = 0; + si->queue_n--; +} + +static inline struct rr_queue * +next_pointer(struct rr_si *si) +{ + if (si->queue_n == 0) { /* XXX needed? */ + si->pointer = NULL; + return NULL; + } + si->pointer = TAILQ_NEXT(si->pointer, entries); + if (si->pointer == NULL) + si->pointer = TAILQ_FIRST(&si->q_list); + + return si->pointer; +} + +static int +rr_enqueue(struct new_sch_inst *_si, struct new_queue *q, struct mbuf *m) +{ + struct rr_si *si; + struct rr_queue *alg_fq; + + if (m != q->mq.head) { + if (dn_enqueue(q, m, 0)) /* packet was dropped */ + return 1; + if (m == q->mq.head) + return 0; + } + + /* If reach this point, queue q was idle */ + si = (struct rr_si *)(_si + 1); + alg_fq = (struct rr_queue *)(q+1); + + if (alg_fq->status == 1) /* Queue is already in the queue list */ + return 0; + + /* Insert the queue in the queue list */ + insert_queue(alg_fq, si); + + return 0; +} + +static struct mbuf * +rr_dequeue(struct new_sch_inst *_si) +{ + /* Access scheduler instance private data */ + struct rr_si *si = (struct rr_si *)(_si + 1); + struct mbuf *pkt; + struct rr_queue *q; + struct new_queue *_q; + uint64_t len; + + if (si->queue_n == 0) /* scheduler empty */ + return NULL; + + while (si->queue_n > 0) { + q = si->pointer; + _q = q->parent; + /* or use: _q = ((struct new_queue *)q) - 1; */ + si->pointer = next_pointer(si); + if (_q->mq.head == NULL) { + /* empty queue, remove from list */ + remove_queue(q, si); + continue; + } + pkt = _q->mq.head; + len = pkt->m_pkthdr.len; + + if (len > q->credit) { + /* Packet too big */ + q->credit += q->quantum; + /* Try next queue */ + } else { + q->credit = q->credit - len + q->quantum; + return dn_dequeue(_q); + } + } + + /* no packet to dequeue*/ + return NULL; +} + +static int +rr_config(struct new_schk *_schk) +{ + struct rr_schk *schk = (struct rr_schk *)(_schk + 1); + printf("%s called\n", __FUNCTION__); + + schk->min_q = 1; + schk->max_q = 1000; + schk->q_bytes = 50; + + return 0; +} + +static int +rr_new_sched(struct new_sch_inst *_si) +{ + struct rr_si *si = (struct rr_si *)(_si + 1); + + printf("%s called\n", __FUNCTION__); + si->pointer = NULL; + si->queue_n = 0; + TAILQ_INIT(&si->q_list); + + return 0; +} + +static int +rr_free_sched(struct new_sch_inst *_si) +{ + printf("%s called\n", __FUNCTION__); + /* Nothing to do? */ + return 0; +} + +static int +rr_new_fsk(struct new_fsk *fs) +{ + struct rr_schk *schk = (struct rr_schk *)(fs->sched + 1); + printf("%s called\n", __FUNCTION__); + if (fs->fs.quantum < schk->min_q) + fs->fs.quantum = schk->min_q; + else if (fs->fs.quantum > schk->max_q) + fs->fs.quantum = schk->max_q; + return 0; +} + +static int +rr_new_queue(struct new_queue *_q) +{ + struct rr_queue *q = (struct rr_queue *)(_q + 1); + struct rr_schk *schk = (struct rr_schk *)(_q->_si->sched + 1); + + printf("%s called, schk->quantum=%d\n", __FUNCTION__, schk->q_bytes); + _q->ni.oid.subtype = DN_SCHED_RR; + + q->quantum = _q->fs->fs.quantum * schk->q_bytes; + q->credit = q->quantum; + q->status = 0; + q->parent = _q; + + if (_q->mq.head != NULL) { + /* Queue NOT empty, insert in the queue list */ + insert_queue(q, (struct rr_si *)(_q->_si + 1)); + } + return 0; +} + +static int +rr_free_queue(struct new_queue *_q) +{ + struct rr_queue *q = (struct rr_queue *)(_q + 1); + + printf("%s called\n", __FUNCTION__); + if (q->status == 1) { + struct rr_si *si = (struct rr_si *)(_q->_si + 1); + remove_queue(q, si); + if (si->pointer == q) + si->pointer = next_pointer(si); + } + return 0; +} + +/* + * RR scheduler descriptor + * contains the type of the scheduler, the name, the size of the + * structures and function pointers. + */ +static struct dn_sched rr_desc = { + .type = DN_SCHED_RR, + .name = "RR", + .flags = DN_MULTIQUEUE, + + .si_datalen = sizeof(struct rr_si), + .q_datalen = sizeof(struct rr_queue), + + .enqueue = rr_enqueue, + .dequeue = rr_dequeue, + + .config = rr_config, + .new_sched = rr_new_sched, + .free_sched = rr_free_sched, + + .new_fsk = rr_new_fsk, + + .new_queue = rr_new_queue, + .free_queue = rr_free_queue, +}; + + +DECLARE_DNSCHED_MODULE(dn_rr, &rr_desc);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001201350.o0KDoUd7018365>