svn commit: r201967 - in user/luigi/ipfw3-head/sys/netinet: . ipfw
Luigi Rizzo
luigi at FreeBSD.org
Sun Jan 10 00:46:38 UTC 2010
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;
More information about the svn-src-user
mailing list