Date: Sun, 10 Jan 2010 00:46:38 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r201967 - in user/luigi/ipfw3-head/sys/netinet: . ipfw Message-ID: <201001100046.o0A0kcCm065657@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: luigi Date: Sun Jan 10 00:46:38 2010 New Revision: 201967 URL: http://svn.freebsd.org/changeset/base/201967 Log: add a fifo scheduler Added: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c (contents, props changed) Modified: user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Modified: user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h Sun Jan 10 00:14:04 2010 (r201966) +++ user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h Sun Jan 10 00:46:38 2010 (r201967) @@ -84,16 +84,6 @@ enum { /* user flags */ DN_NOERROR = 0x0010, }; -/* kernel-side flags */ -enum { - DN_RECONFIGURE = 0x0001, /* (k) */ - DN_DELETE = 0x0004, /* (k) */ - DN_REENQUEUE = 0x0008, /* (k) */ - DN_ACTIVE = 0x0010, /* (k) */ -// DN_SCH_BUSY = 0x0020, /* (k) */ - DN_SCH_DELETE_DELAY_LINE = 0x0040, /* (k) */ -}; - typedef uint64_t dn_key; struct new_cmd { /* header for all sockopt */ Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Sun Jan 10 00:14:04 2010 (r201966) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Sun Jan 10 00:46:38 2010 (r201967) @@ -114,14 +114,14 @@ struct dn_sched { * drain_queue called to free all idle queues, or possibly all of * them (this is a subset of delete_scheduler_instance) */ - int (*enqueue)(void *s, struct dn_id *f, struct mbuf *m, + int (*enqueue)(struct new_sch_inst *s, void *f, struct mbuf *m, struct ipfw_flow_id *id); - struct mbuf * (*dequeue)(void *s); + struct mbuf * (*dequeue)(struct new_sch_inst *); int (*config)(char *command, void *sch, int reconfigure); int (*destroy)(void* sch); - int (*new_sched)(void *sch_priv, void *sch_t_priv); - int (*free_sched)(void *s); + int (*new_sched)(struct new_schk *s, struct new_sch_inst *si); + int (*free_sched)(struct new_sch_inst *si); int (*new_fs)(void *command, struct dn_id *g, int reconfigure); int (*free_fs)(struct dn_id *f); @@ -202,6 +202,21 @@ int dn_i_hash_id(struct ipfw_flow_id *id struct new_queue * dn_q_hash_id(struct ipfw_flow_id *id, int i, struct new_queue **rq, struct dn_id *f); +/* + * Function that need to be called before returning a packet from dequeue. + * Update queue statistic + */ +static __inline struct mbuf* +dn_return_packet(struct mbuf *pkt, struct new_queue *q) +{ + + q->head = pkt->m_nextpkt; + q->lenght--; + q->len_bytes -= pkt->m_pkthdr.len; + + return pkt; +} + int dn_sched_modevent(module_t mod, int cmd, void *arg); #define DECLARE_DNSCHED_MODULE(name, dnsched) \ Added: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c Sun Jan 10 00:46:38 2010 (r201967) @@ -0,0 +1,221 @@ +/* + * Copyright (c) 2010 Riccardo Panicucci, Universita` di Pisa + * Copyright (c) 1998-2002 Luigi Rizzo, 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 <net/if.h> /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */ +#include <netinet/in.h> +#include <netinet/ip.h> /* ip_len, ip_off */ +#include <netinet/ip_var.h> /* ip_len, ip_off */ +#include <netinet/ip_fw.h> +#include <netinet/ip_dummynet.h> +#include <netinet/ipfw/dn_heap.h> +#include <netinet/ipfw/ip_fw_private.h> +#include <netinet/ipfw/ip_dn_private.h> +#include <sys/kernel.h> +#include <sys/module.h> +#include <netinet/ipfw/dn_sched.h> + +#define DN_FIFO 1 +/* + * This file implements a FIFO scheduler. + * A FIFO scheduler is a simple scheduler algorithm that can be use to + * scheduling internet packets. + * The scheduler receive a packet (by enqueue() function) and put in in the + * unique queue that manages. + * When the scheduler can transmit, the first packet in the queue is sent + * out (First In First Out) + * The complexity of this algorithm is O(1), all flows use the same queue. + * + * No parameters are required to configure a FIFO scheduler or a + * FIFO flowset. + * + */ + +/* A scheduler instance of a FIFO scheduler requires only a queue. */ +struct fifo_si { + struct new_queue *q; +}; + +static int +fifo_enqueue(struct new_sch_inst *_si, void *f, + struct mbuf *m, struct ipfw_flow_id *id) +{ + /* + * The system pass to the enqueue() function 4 parameters: + * - s: scheduler instance which the packet belongs + * - f: flowset scheduler private data + * - m: the packet + * - id: flow id of the packet, the mask is applyed by system + * + * The scheduler should save all data needs into variables in the + * scheduler instance. In the FIFO scheduling algorithm there is only + * one queue, so a queue should be saved in the scheduler instance. + * When the first packet arrives, the queue doesn't exist and the + * scheduler must create it calling the dn_create_queue() function. + * To really enqueue the packet, the scheduler must call the + * dn_queue_packet() function that insert the packet in the queue passes. + * If for some reason (for example the queue is full) the packet can't + * be enqueued, dn_queue_packet() returns 1. + * + * See the enqueue() function for wf2q+ scheduler algorithm for + * another examples of enqueue() + */ + + /* Access to specific scheduler instance data */ + struct fifo_si *si = (struct fifo_si *)(_si+1); + struct new_queue *q = (struct new_queue *)f; + + if (si->q == NULL) { + si->q = q; + } else if (si->q != q) { + printf("%s queue changed from %p to %p?\n", + __FUNCTION__, si->q, q); + return 1; + } + /* Now the si->q is valid, so insert the packet in this queue */ + if (dn_queue_packet(si->q, m)) { + /* packet was dropped */ + return 1; + } + + /* Ok, the packet is now in the queue. + * The dequeue() function will be called when the scheduler + * instance has credit to transmit packets + */ + return 0; +} + +static struct mbuf * +fifo_dequeue(struct new_sch_inst *_si) +{ + /* + * The dequeue() function is called by the system when the scheduler + * instance can transmit packets. The dequeue() is called until the + * instance has credit and packet to send. + * If the scheduler wants to dequeue a packet, it should call the + * dn_return_packet() function, that take a packet pkt and the relative + * queue and update. + * If the queue is empty, no packet can be send and the dequeue() must + * return NULL. + */ + + /* Pointer to the packet to return , if exists*/ + struct mbuf *pkt; + + /* Accessing to scheduler instance private data */ + struct fifo_si *si = (struct fifo_si *)(_si + 1); + + struct new_queue *q = si->q; + + if (q == NULL) { + /* Queue is not valid, no packet to dequeue */ + return NULL; + } + + /* Take the first packet from the queue, if exists */ + pkt = q->head; + + if (pkt != NULL) { + /* Packet exists, return it */ + return dn_return_packet(pkt, q); + } + + /* No packets in queue, return NULL */ + return NULL; +} + +static int +fifo_new_sched(struct new_schk *s, struct new_sch_inst *_si) +{ + /* This scheduler instance only has a queue pointer. */ + struct fifo_si *si = (struct fifo_si *)(_si + 1); + + /* Initialize scheduler instance private data */ + si->q = NULL; + + return 0; +} + +static int +fifo_free_sched(struct new_sch_inst *_si) +{ + /* + * Delete a FIFO scheduler instance + * - Deallocate memory if the create_scheduler_instance() function + * allocate memory + * - Delete the queue if exists + */ + struct fifo_si *si = (struct fifo_si *)(_si + 1); + + if (si->q) + dn_delete_queue(si->q, 0); + + return 0; +} + +static int +drain_queue_fifo(void *s, int flag) +{ + /* + * Called by the system to free memory. + * Remove the queue if it is empty or if the DN_FORCE flag is set + */ + + struct fifo_si *si = (struct fifo_si *)s; + + if (si->q && (si->q->head == NULL || flag & DN_FORCE)) { + dn_delete_queue(si->q, 0); + si->q = NULL; + } + + return 0; +} + +/* + * FIFO scheduler descriptor + * contains the type of the scheduler, the name, the size of the various + * structures and function pointers. If a function is not implemented, + * the pointer is initialized to NULL + */ +static struct dn_sched fifo_desc = { + .type = DN_FIFO, + .name = "FIFO scheduler algorithm descriptor", + + .scheduler_i_size = sizeof(struct fifo_si), + .queue_size = sizeof(struct new_queue), + + .enqueue = fifo_enqueue, + .dequeue = fifo_dequeue, + + .new_sched = fifo_new_sched, + .free_sched = fifo_free_sched, + .drain_queue = drain_queue_fifo, +}; + +DECLARE_DNSCHED_MODULE(dn_fifo, &fifo_desc); Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Sun Jan 10 00:14:04 2010 (r201966) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Sun Jan 10 00:46:38 2010 (r201967) @@ -477,10 +477,12 @@ create_scheduler_instance(struct new_sch si->sched = s; /* XXX do we make assumption on this starting with dn_id ? */ - ret = s->fp->new_sched(si + 1, s + 1); - if (ret) { - msg = "new_sched error"; - goto error; + if (s->fp->new_sched) { + ret = s->fp->new_sched(s, si); + if (ret) { + msg = "new_sched error"; + goto error; + } } /* Initialize scheduler instance queues list */ @@ -1174,11 +1176,6 @@ dummynet_io(struct mbuf **m0, int dir, s if (sch == NULL) goto dropit; pipe = sch->pipe; - if (pipe == NULL) { /* should not happen ? */ - printf("%s strange, scheduler without a pipe\n", __FUNCTION__); - goto dropit; - } - sch_inst = find_scheduler(sch, fs, &(fwa->f_id)); if (sch_inst == NULL) goto dropit; Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h Sun Jan 10 00:14:04 2010 (r201966) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_private.h Sun Jan 10 00:46:38 2010 (r201967) @@ -251,15 +251,16 @@ struct new_sch_inst { dn_key sched_time ; /* time pipe was scheduled in ready_heap */ dn_key idle_time; /* start of scheduler instance idle time */ }; -/* These values are in the flag field of a flowset - * Some of them are used only by kernel (k) - */ -enum flowset_flag { - DN_FS_DELETE = 0x0001, /* (k) */ - DN_FS_REENQUEUE = 0x0002, /* (k) */ - DN_FS_HAVE_MASK = 0x0004, - DN_FS_QSIZE_BYTES = 0x0008, - DN_FS_NOERROR = 0x0010, /* (k) do not report ENOBUFS on drops */ + +/* kernel-side flags */ +enum { + DN_RECONFIGURE = 0x0001, /* (k) */ + DN_DELETE = 0x0004, /* (k) */ + DN_REENQUEUE = 0x0008, /* (k) */ + DN_ACTIVE = 0x0010, /* (k) */ +// DN_SCH_BUSY = 0x0020, /* (k) */ + DN_SCH_DELETE_DELAY_LINE = 0x0040, /* (k) */ + DN_FORCE = 0x0080 }; extern struct dn_parms dn_cfg; Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c ============================================================================== --- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Sun Jan 10 00:14:04 2010 (r201966) +++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Sun Jan 10 00:46:38 2010 (r201967) @@ -490,7 +490,7 @@ dn_fs_config(struct new_fsk *fs) free(fs->alg_fs, M_DUMMYNET); free(fs, M_DUMMYNET); } else - fs->kflags |= DN_FS_DELETE; + fs->kflags |= DN_DELETE; DN_S_UNLOCK(fs->ptr_sched); fs = newfs; fs->fp = s;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001100046.o0A0kcCm065657>