svn commit: r202072 - in user/luigi/ipfw3-head: sbin/ipfw
sys/netinet sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Mon Jan 11 10:12:35 UTC 2010
Author: luigi
Date: Mon Jan 11 10:12:35 2010
New Revision: 202072
URL: http://svn.freebsd.org/changeset/base/202072
Log:
snapshot
Added:
user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c (contents, props changed)
Modified:
user/luigi/ipfw3-head/sbin/ipfw/dummynet.c
user/luigi/ipfw3-head/sbin/ipfw/ipfw2.h
user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h
user/luigi/ipfw3-head/sys/netinet/ip_fw.h
user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h
user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h
user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c
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
user/luigi/ipfw3-head/sys/netinet/ipfw/ip_fw2.c
user/luigi/ipfw3-head/sys/netinet/ipfw/ip_fw_private.h
Modified: user/luigi/ipfw3-head/sbin/ipfw/dummynet.c
==============================================================================
--- user/luigi/ipfw3-head/sbin/ipfw/dummynet.c Mon Jan 11 09:57:29 2010 (r202071)
+++ user/luigi/ipfw3-head/sbin/ipfw/dummynet.c Mon Jan 11 10:12:35 2010 (r202072)
@@ -71,6 +71,8 @@ static struct _s_x dummynet_params[] = {
{ "queue", TOK_FLOWSET },
{ "flowset", TOK_FLOWSET },
{ "sched", TOK_SCHED },
+ { "pri", TOK_PRI },
+ { "type", TOK_TYPE },
{ "flow-id", TOK_FLOWID},
{ "dst-ipv6", TOK_DSTIP6},
{ "dst-ip6", TOK_DSTIP6},
@@ -97,6 +99,7 @@ o_next(struct dn_id **o, int len, int ty
return ret;
}
+#if 0
static int
sort_q(void *arg, const void *pa, const void *pb)
{
@@ -284,10 +287,11 @@ print_extra_delay_parms(struct dn_pipe *
printf("\t profile: name \"%s\" loss %f samples %d\n",
p->name, loss, p->samples_no);
}
-
+#endif
void
ipfw_list_pipes(void *data, uint nbytes, int ac, char *av[])
{
+#if 0
int rulenum;
void *next = data;
struct dn_pipe *p = (struct dn_pipe *) data;
@@ -321,11 +325,6 @@ ipfw_list_pipes(void *data, uint nbytes,
/*
* Print rate (or clocking interface)
*/
-#if 0
- if (p->if_name[0] != '\0')
- sprintf(buf, "%s", p->if_name);
- else
-#endif
if (b == 0)
sprintf(buf, "unlimited");
else if (b >= 1000000)
@@ -371,6 +370,7 @@ ipfw_list_pipes(void *data, uint nbytes,
print_flowset_parms(fs, prefix);
list_queues(fs, q);
}
+#endif
}
/*
@@ -379,6 +379,7 @@ ipfw_list_pipes(void *data, uint nbytes,
int
ipfw_delete_pipe(int pipe_or_queue, int i)
{
+#if 0
struct dn_pipe p;
memset(&p, 0, sizeof p);
@@ -391,6 +392,7 @@ ipfw_delete_pipe(int pipe_or_queue, int
i = 1;
warn("rule %u: setsockopt(IP_DUMMYNET_DEL)", i);
}
+#endif
return i;
}
@@ -778,6 +780,7 @@ ipfw_config_pipe(int ac, char **av)
case 1:
sch = o_next(&buf, sizeof(*sch), DN_SCH);
sch->sched_nr = i + DN_PIPEOFFSET;
+ sch->oid.subtype = DN_SCHED_FIFO;
p = o_next(&buf, sizeof(*p), DN_PIPE);
p->pipe_nr = i + DN_PIPEOFFSET;
mask = &sch->sched_mask;
@@ -787,6 +790,7 @@ ipfw_config_pipe(int ac, char **av)
/* sch2 and p2 will be set later */
sch2 = o_next(&buf, sizeof(*sch2), DN_SCH);
+ sch2->oid.subtype = DN_SCHED_WF2QP;
p2 = o_next(&buf, sizeof(*p2), DN_PIPE);
break;
@@ -1015,14 +1019,25 @@ end_mask:
ac--; av++;
break;
-#if 0
+ case TOK_TYPE: {
+ int l;
+ NEED(sch, "type is only for schedulers");
+ NEED1("type needs a string");
+ l = strlen(av[0]);
+ if (l == 0 || l > 15)
+ errx(1, "type %s too long\n", av[0]);
+ strcpy(sch->type, av[0]);
+ sch->oid.subtype = 0; /* use string */
+ ac--; av++;
+ break;
+ }
+
case TOK_WEIGHT:
NEED(fs, "weight is only for flowsets");
NEED1("weight needs argument 0..100\n");
fs->weight = strtoul(av[0], &end, 0);
ac--; av++;
break;
-#endif
case TOK_SCHED:
case TOK_PIPE:
@@ -1171,6 +1186,7 @@ end_mask:
if (sch2) {
*sch2 = *sch;
sch2->sched_nr = i;
+ sch2->oid.subtype = DN_SCHED_WF2QP;
}
if (p2) {
*p2 = *p;
Modified: user/luigi/ipfw3-head/sbin/ipfw/ipfw2.h
==============================================================================
--- user/luigi/ipfw3-head/sbin/ipfw/ipfw2.h Mon Jan 11 09:57:29 2010 (r202071)
+++ user/luigi/ipfw3-head/sbin/ipfw/ipfw2.h Mon Jan 11 10:12:35 2010 (r202072)
@@ -163,7 +163,12 @@ enum tokens {
TOK_GRED,
TOK_DROPTAIL,
TOK_PROTO,
+ /* dummynet tokens */
TOK_WEIGHT,
+ TOK_PRI,
+ TOK_TYPE,
+ TOK_SLOTSIZE,
+
TOK_IP,
TOK_IF,
TOK_ALOG,
Modified: user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h Mon Jan 11 09:57:29 2010 (r202071)
+++ user/luigi/ipfw3-head/sys/netinet/ip_dummynet.h Mon Jan 11 10:12:35 2010 (r202072)
@@ -1,5 +1,5 @@
/*-
- * Copyright (c) 1998-2002 Luigi Rizzo, Universita` di Pisa
+ * Copyright (c) 1998-2010 Luigi Rizzo, Universita` di Pisa
* Portions Copyright (c) 2000 Akamba Corp.
* All rights reserved
*
@@ -56,6 +56,7 @@ struct dn_id {
* entries with the exception of DN_LAST
*/
enum {
+ DN_NONE = 0,
DN_PIPE = 1,
DN_FS,
DN_SCH,
@@ -74,7 +75,9 @@ enum {
};
enum { /* subtype for schedulers, flowset and the like */
- DN_UNKNOWN = 0,
+ DN_SCHED_UNKNOWN = 0,
+ DN_SCHED_FIFO = 1,
+ DN_SCHED_WF2QP = 2,
/* others are in individual modules */
};
@@ -107,19 +110,15 @@ struct new_profile {
};
/*
- * pipe template. In the kernel it is right after a scheduler.
+ * pipe template.
*/
struct new_pipe {
struct dn_id oid;
- /* these initial fields are set from the command line
- * pipe N config bw B delay D profile PRF (mask M1 plr P queue Q
- * buckets BB ) ...
- * The second set of parameters (M1, ...) belong to the
- * scheduler or the flowset. They can be specified in 'pipe config'
- * only for backward compatibility.
+ /*
* Userland sets bw and delay in bits/s and milliseconds.
* The kernel converts this back and forth to bits/tick and ticks.
+ * XXX what about burst ?
*/
int32_t pipe_nr ; /* N, number */
int bandwidth; /* B, really, bits/tick. */
@@ -160,6 +159,9 @@ struct new_fs {
/* mask to select the appropriate queue */
struct ipfw_flow_id flow_mask; /* M */
int sched_nr; /* the scheduler we attach to */
+ /* generic scheduler parameters */
+ int weight;
+ int slot_size;
};
/*
@@ -188,6 +190,7 @@ struct new_sch {
int bucket; /* number of buckets for the instances */
int flags; /* have_mask, ... */
+ char type[16]; /* null terminated */
/* mask to select the appropriate scheduler instance */
struct ipfw_flow_id sched_mask; /* M */
};
@@ -270,75 +273,6 @@ flow using a number of heaps defined int
*
*/
-/*
- * per flow queue. This contains the flow identifier, the queue
- * of packets, counters, and parameters used to support both RED and
- * WF2Q+.
- *
- * A dn_flow_queue is created and initialized whenever a packet for
- * a new flow arrives.
- */
-struct dn_flow_queue {
- struct dn_flow_queue *next ;
- struct ipfw_flow_id id ;
-
- struct mbuf *head, *tail ; /* queue of packets */
- u_int len ;
- u_int len_bytes ;
-
- /*
- * When we emulate MAC overheads, or channel unavailability due
- * to other traffic on a shared medium, we augment the packet at
- * the head of the queue with an 'extra_bits' field representsing
- * the additional delay the packet will be subject to:
- * extra_bits = bw*unavailable_time.
- * With large bandwidth and large delays, extra_bits (and also numbytes)
- * can become very large, so better play safe and use 64 bit
- */
- uint64_t numbytes ; /* credit for transmission (dynamic queues) */
- int64_t extra_bits; /* extra bits simulating unavailable channel */
-
- u_int64_t tot_pkts ; /* statistics counters */
- u_int64_t tot_bytes ;
- u_int32_t drops ;
-
- int hash_slot ; /* debugging/diagnostic */
-
- /* RED parameters */
- int avg ; /* average queue length est. (scaled) */
- int count ; /* arrivals since last RED drop */
- int random ; /* random value (scaled) */
- dn_key idle_time; /* start of queue idle time */
-
- /* WF2Q+ support */
- struct dn_flow_set *fs ; /* parent flow set */
- int heap_pos ; /* position (index) of struct in heap */
- dn_key sched_time ; /* current time when queue enters ready_heap */
-
- dn_key S,F ; /* start time, finish time */
- /*
- * Setting F < S means the timestamp is invalid. We only need
- * to test this when the queue is empty.
- */
-} ;
-
-/*
- * flow_set descriptor. Contains the "template" parameters for the
- * queue configuration, and pointers to the hash table of dn_flow_queue's.
- *
- * The hash table is an array of lists -- we identify the slot by
- * hashing the flow-id, then scan the list looking for a match.
- * The size of the hash table (buckets) is configurable on a per-queue
- * basis.
- *
- * A dn_flow_set is created whenever a new queue or pipe is created (in the
- * latter case, the structure is located inside the struct dn_pipe).
- */
-struct dn_flow_set {
- SLIST_ENTRY(dn_flow_set) next; /* linked list in a hash slot */
-
- u_short fs_nr ; /* flow_set number */
- u_short flags_fs;
#define DN_HAVE_FLOW_MASK 0x0001
#define DN_IS_RED 0x0002
#define DN_IS_GENTLE_RED 0x0004
@@ -348,100 +282,4 @@ struct dn_flow_set {
#define DN_IS_PIPE 0x4000
#define DN_IS_QUEUE 0x8000
- struct dn_pipe *pipe ; /* pointer to parent pipe */
- u_short parent_nr ; /* parent pipe#, 0 if local to a pipe */
-
- int weight ; /* WFQ queue weight */
- int qsize ; /* queue size in slots or bytes */
- int plr ; /* pkt loss rate (2^31-1 means 100%) */
-
- struct ipfw_flow_id flow_mask ;
-
- /* hash table of queues onto this flow_set */
- int rq_size ; /* number of slots */
- int rq_elements ; /* active elements */
- struct dn_flow_queue **rq; /* array of rq_size entries */
-
- u_int32_t last_expired ; /* do not expire too frequently */
- int backlogged ; /* #active queues for this flowset */
-
- /* RED parameters */
-#define SCALE_RED 16
-#define SCALE(x) ( (x) << SCALE_RED )
-#define SCALE_VAL(x) ( (x) >> SCALE_RED )
-#define SCALE_MUL(x,y) ( ( (x) * (y) ) >> SCALE_RED )
- int w_q ; /* queue weight (scaled) */
- int max_th ; /* maximum threshold for queue (scaled) */
- int min_th ; /* minimum threshold for queue (scaled) */
- int max_p ; /* maximum value for p_b (scaled) */
- u_int c_1 ; /* max_p/(max_th-min_th) (scaled) */
- u_int c_2 ; /* max_p*min_th/(max_th-min_th) (scaled) */
- u_int c_3 ; /* for GRED, (1-max_p)/max_th (scaled) */
- u_int c_4 ; /* for GRED, 1 - 2*max_p (scaled) */
- u_int * w_q_lookup ; /* lookup table for computing (1-w_q)^t */
- u_int lookup_depth ; /* depth of lookup table */
- int lookup_step ; /* granularity inside the lookup table */
- int lookup_weight ; /* equal to (1-w_q)^t / (1-w_q)^(t+1) */
- int avg_pkt_size ; /* medium packet size */
- int max_pkt_size ; /* max packet size */
-};
-
-struct dn_heap;
-/*
- * Pipe descriptor. Contains global parameters, delay-line queue,
- * and the flow_set used for fixed-rate queues.
- *
- * For WF2Q+ support it also has 3 heaps holding dn_flow_queue:
- * not_eligible_heap, for queues whose start time is higher
- * than the virtual time. Sorted by start time.
- * scheduler_heap, for queues eligible for scheduling. Sorted by
- * finish time.
- * idle_heap, all flows that are idle and can be removed. We
- * do that on each tick so we do not slow down too much
- * operations during forwarding.
- *
- */
-struct dn_pipe { /* a pipe */
- SLIST_ENTRY(dn_pipe) next; /* linked list in a hash slot */
-
- int pipe_nr ; /* number */
- int bandwidth; /* really, bytes/tick. */
- int delay ; /* really, ticks */
-
- struct mbuf *head, *tail ; /* packets in delay line */
-
- /* WF2Q+ */
- struct dn_heap *scheduler_heap ; /* top extract - key Finish time*/
- struct dn_heap *not_eligible_heap; /* top extract- key Start time */
- struct dn_heap *idle_heap ; /* random extract - key Start=Finish time */
-
- dn_key V ; /* virtual time */
- int sum; /* sum of weights of all active sessions */
-
- /* Same as in dn_flow_queue, numbytes can become large */
- int64_t numbytes; /* bits I can transmit (more or less). */
- uint64_t burst; /* burst size, scaled: bits * hz */
-
- dn_key sched_time ; /* time pipe was scheduled in ready_heap */
- dn_key idle_time; /* start of pipe idle time */
-
- /*
- * When the tx clock come from an interface (if_name[0] != '\0'), its name
- * is stored below, whereas the ifp is filled when the rule is configured.
- */
- char if_name[IFNAMSIZ];
- struct ifnet *ifp ;
- int ready ; /* set if ifp != NULL and we got a signal from it */
-
- struct dn_flow_set fs ; /* used with fixed-rate flows */
-
- /* fields to simulate a delay profile */
-
-#define ED_MAX_NAME_LEN 32
- char name[ED_MAX_NAME_LEN];
- int loss_level;
- int samples_no;
- int *samples;
-};
-
#endif /* _IP_DUMMYNET_H */
Modified: user/luigi/ipfw3-head/sys/netinet/ip_fw.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ip_fw.h Mon Jan 11 09:57:29 2010 (r202071)
+++ user/luigi/ipfw3-head/sys/netinet/ip_fw.h Mon Jan 11 10:12:35 2010 (r202072)
@@ -487,24 +487,26 @@ struct ip_fw {
#define RULESIZE(rule) (sizeof(struct ip_fw) + \
((struct ip_fw *)(rule))->cmd_len * 4 - 4)
+#if 1 // moved to in.h
/*
* This structure is used as a flow mask and a flow id for various
* parts of the code.
*/
struct ipfw_flow_id {
- u_int32_t dst_ip;
- u_int32_t src_ip;
- u_int16_t dst_port;
- u_int16_t src_port;
- u_int8_t fib;
- u_int8_t proto;
- u_int8_t flags; /* protocol-specific flags */
+ uint32_t dst_ip;
+ uint32_t src_ip;
+ uint16_t dst_port;
+ uint16_t src_port;
+ uint8_t fib;
+ uint8_t proto;
+ uint8_t flags; /* protocol-specific flags */
uint8_t addr_type; /* 4 = ipv4, 6 = ipv6, 1=ether ? */
- struct in6_addr dst_ip6; /* could also store MAC addr! */
+ struct in6_addr dst_ip6;
struct in6_addr src_ip6;
- u_int32_t flow_id6;
- u_int32_t frag_id6;
+ uint32_t flow_id6;
+ uint32_t frag_id6;
};
+#endif
#define IS_IP6_FLOW_ID(id) ((id)->addr_type == 6)
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Mon Jan 11 09:57:29 2010 (r202071)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h Mon Jan 11 10:12:35 2010 (r202072)
@@ -63,6 +63,7 @@ struct dn_heap {
/* HEAP_TOP returns the pointer to the top element of the heap */
#define HEAP_TOP(h) ((h)->p)
+#define SET_HEAP_OFS(h, n) do { (h)->ofs = n; } while (0)
int heap_init(struct dn_heap *h, int size);
int heap_insert (struct dn_heap *h, uint64_t key1, void *p);
void heap_extract(struct dn_heap *h, void *obj);
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Mon Jan 11 09:57:29 2010 (r202071)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Mon Jan 11 10:12:35 2010 (r202072)
@@ -121,19 +121,18 @@ struct dn_sched {
/* config or destroy the scheduler template */
int (*config)(struct new_schk *, int reconfigure);
- int (*destroy)(struct new_schk*);
+ int (*destroy)(struct new_schk*, int delete);
/* create, drain or destroy a new scheduler instance */
int (*new_sched)(struct new_schk *, struct new_sch_inst *);
- int (*drain_sched)(struct new_sch_inst *, int flag);
int (*free_sched)(struct new_sch_inst *);
- /* create or destroy a flowset attached to this scheduler */
+ /* init or deinit a flowset attached to this scheduler */
int (*new_fs)(void *command, struct dn_id *g, int reconfigure);
int (*free_fs)(struct new_fsk *);
- /* create or destroy a queue attached to this scheduler */
- int (*new_queue)(struct new_queue *q, struct dn_id *f);
+ /* init or destroy a queue attached to this scheduler */
+ int (*new_queue)(struct new_queue *q);
int (*free_queue)(struct new_queue *q);
};
@@ -152,20 +151,10 @@ SLIST_HEAD(dn_sched_head, dn_sched);
*/
struct mbuf* dn_pkt_done(struct mbuf *pkt, struct new_queue *q);
-/* Called to delete a queue 'q'. If packet belong to this queue should be
- * reenqueued, the 'reenqueue' should be set to 1
- */
-int dn_delete_queue (struct new_queue *q, int reenqueue);
-
-/* Called by enqueue() when it needs to create a new queue.
- * - f: extension of the flowset.
- * - s: scheduler specific scheduler instance data
- * - i: index of the hash table, or 0 if no hash table is used
- * - id: flow id for this queue
- * - size: size of the queue, including the private data
+/*
+ * delete a queue, which we assume nobody references
*/
-struct new_queue * dn_create_queue(struct dn_id *f, void *s, int i,
- struct ipfw_flow_id *id);
+int dn_delete_queue(struct new_queue *q);
/* Allocate an hash table.
* Returns the pointer to the table
@@ -209,18 +198,20 @@ struct new_queue * dn_q_hash_id(struct i
struct new_queue **rq, struct dn_id *f);
/*
- * Function that need to be called before returning a packet from dequeue.
- * Update queue statistic
+ * Extract the head of a queue, update stats. Must be the very last
+ * thing done on a queue as it may go away.
*/
static __inline struct mbuf*
-dn_return_packet(struct mbuf *pkt, struct new_queue *q)
+dn_return_packet(struct new_queue *q)
{
-
- q->head = pkt->m_nextpkt;
+ struct mbuf *m = q->mq.head;
+ q->mq.head = m->m_nextpkt;
q->lenght--;
- q->len_bytes -= pkt->m_pkthdr.len;
+ q->len_bytes -= m->m_pkthdr.len;
+ if (q->mq.head == NULL && q->fs->kflags & DN_DELETE)
+ dn_delete_queue(q);
- return pkt;
+ return m;
}
int dn_sched_modevent(module_t mod, int cmd, void *arg);
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c Mon Jan 11 09:57:29 2010 (r202071)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_fifo.c Mon Jan 11 10:12:35 2010 (r202072)
@@ -1,6 +1,5 @@
/*
* 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
@@ -28,20 +27,19 @@
#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 <sys/kernel.h>
+#include <sys/mbuf.h>
+#include <sys/module.h>
+#include <net/if.h> /* IFNAMSIZ */
#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_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_fw_private.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
@@ -59,11 +57,11 @@
/* A scheduler instance of a FIFO scheduler requires only a queue. */
struct fifo_si {
- struct new_queue *q;
+ struct new_queue *q;
};
static int
-fifo_enqueue(struct new_sch_inst *_si, struct new_fs *f,
+fifo_enqueue(struct new_sch_inst *_si, struct new_fsk *f,
struct mbuf *m, struct ipfw_flow_id *id)
{
/*
@@ -89,14 +87,13 @@ fifo_enqueue(struct new_sch_inst *_si, s
/* 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;
+ si->q = dn_create_queue(_si, f, id);
+ if (si->q == NULL) {
+ FREE_PKT(m);
+ return 1;
+ }
}
/* Now the si->q is valid, so insert the packet in this queue */
if (dn_queue_packet(si->q, m)) {
@@ -125,41 +122,24 @@ fifo_dequeue(struct new_sch_inst *_si)
* return NULL.
*/
- /* Pointer to the packet to return , if exists*/
- struct mbuf *pkt;
-
- /* Accessing to scheduler instance private data */
+ /* Access 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 */
+ if (q == NULL || q->mq.head == NULL)
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;
+ return dn_return_packet(q);
}
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);
+ /* 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;
+ si->q = NULL;
+ return 0;
}
static int
@@ -171,30 +151,12 @@ fifo_free_sched(struct new_sch_inst *_si
* 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);
+ struct fifo_si *si = (struct fifo_si *)(_si + 1);
- return 0;
-}
+ if (si->q)
+ dn_delete_queue(si->q);
-static int
-fifo_drain(struct new_sch_inst *_si, 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 *)(_si + 1);
-
- if (si->q && (si->q->head == NULL || flag & DN_FORCE)) {
- dn_delete_queue(si->q, 0);
- si->q = NULL;
- }
-
- return 0;
+ return 0;
}
/*
@@ -204,8 +166,8 @@ fifo_drain(struct new_sch_inst *_si, int
* the pointer is initialized to NULL
*/
static struct dn_sched fifo_desc = {
- .type = DN_FIFO,
- .name = "FIFO scheduler algorithm descriptor",
+ .type = DN_SCHED_FIFO,
+ .name = "FIFO",
.sch_inst_len = sizeof(struct fifo_si),
.queue_len = sizeof(struct new_queue),
@@ -215,7 +177,6 @@ static struct dn_sched fifo_desc = {
.new_sched = fifo_new_sched,
.free_sched = fifo_free_sched,
- .drain_sched = fifo_drain,
};
DECLARE_DNSCHED_MODULE(dn_fifo, &fifo_desc);
Added: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched_wf2q.c Mon Jan 11 10:12:35 2010 (r202072)
@@ -0,0 +1,183 @@
+/*
+ * 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.
+ */
+
+/* XXX this is only a stub for wf2q+ */
+#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_fw_private.h>
+#include <netinet/ipfw/ip_dn_private.h>
+#include <netinet/ipfw/dn_sched.h>
+
+/*
+ * 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, struct new_fsk *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);
+
+ if (si->q == NULL) {
+ si->q = dn_create_queue(_si, f, id);
+ if (si->q == NULL) {
+ FREE_PKT(m);
+ 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.
+ */
+
+ /* Access scheduler instance private data */
+ struct fifo_si *si = (struct fifo_si *)(_si + 1);
+ struct new_queue *q = si->q;
+
+ if (q == NULL || q->mq.head == NULL)
+ return NULL;
+
+ return dn_return_packet(q);
+}
+
+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);
+
+ 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);
+
+ 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_SCHED_WF2QP,
+ .name = "WF2Q+",
+
+ .sch_inst_len = sizeof(struct fifo_si),
+ .queue_len = sizeof(struct new_queue),
+
+ .enqueue = fifo_enqueue,
+ .dequeue = fifo_dequeue,
+
+ .new_sched = fifo_new_sched,
+ .free_sched = fifo_free_sched,
+};
+
+DECLARE_DNSCHED_MODULE(dn_wf2qp, &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 Mon Jan 11 09:57:29 2010 (r202071)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Mon Jan 11 10:12:35 2010 (r202072)
@@ -49,7 +49,6 @@ __FBSDID("$FreeBSD$");
//#include <sys/socketvar.h>
#include <sys/time.h>
#include <sys/sysctl.h>
-//#include <sys/taskqueue.h>
#include <net/if.h> /* IFNAMSIZ, struct ifaddr, ifq head, lock.h mutex.h */
#include <net/netisr.h>
#include <netinet/in.h>
@@ -140,10 +139,6 @@ SYSCTL_DECL(_net_inet_ip);
SYSCTL_NODE(_net_inet_ip, OID_AUTO, dummynet, CTLFLAG_RW, 0, "Dummynet");
SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, hash_size,
CTLFLAG_RW, &dn_cfg.hash_size, 0, "Default hash table size");
-#if 0 /* curr_time is 64 bit */
-SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, curr_time,
- CTLFLAG_RD, &curr_time, 0, "Current tick");
-#endif
SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, searches,
CTLFLAG_RD, &searches, 0, "Number of queue searches");
SYSCTL_LONG(_net_inet_ip_dummynet, OID_AUTO, search_steps,
@@ -188,33 +183,11 @@ SYSCTL_LONG(_net_inet_ip_dummynet, OID_A
CTLFLAG_RW, &dn_cfg.pipe_byte_limit, 0, "Upper limit in bytes for pipe queue.");
#endif
-#ifdef DUMMYNET_DEBUG
-int dummynet_debug = 0;
-#ifdef SYSCTL_NODE
-SYSCTL_INT(_net_inet_ip_dummynet, OID_AUTO, debug, CTLFLAG_RW, &dummynet_debug,
- 0, "control debugging printfs");
-#endif
-#define DPRINTF(X) if (dummynet_debug) printf X
-#else
-#define DPRINTF(X)
-#endif
-
struct mtx dummynet_mtx;
static void dummynet_send(struct mbuf *);
/*
- * Flow queue is idle if:
- * 1) it's empty for at least 1 tick
- * 2) it has invalid timestamp (WF2Q case)
- * 3) parent pipe has no 'exhausted' burst.
- */
-#define QUEUE_IS_IDLE(q) ((q)->head == NULL && (q)->S == (q)->F + 1 && \
- curr_time > (q)->idle_time + 1 && \
- ((q)->numbytes + (curr_time - (q)->idle_time - 1) * \
- (q)->fs->pipe->bandwidth >= (q)->fs->pipe->burst))
-
-/*
* Packets processed by dummynet have an mbuf tag associated with
* them that carries their dummynet state.
* Outside dummynet, only the 'rule' field is relevant, and it must
@@ -248,104 +221,112 @@ dn_tag_get(struct mbuf *m)
return (struct dn_pkt_tag *)(mtag+1);
}
+static inline void
+mq_append(struct mq *q, struct mbuf *m)
+{
+ if (q->head == NULL)
+ q->head = m;
+ else
+ q->tail->m_nextpkt = m;
+ q->tail = m;
+ m->m_nextpkt = NULL;
+}
+
+/*
+ * Check if the packet should be drop depending on the queue management
+ * or queue size overflow.
+ * Put the packet m into the queue q.
+ * Update statistics for the queue.
+ *
+ * The function returns 1 if the packet is dropped.
+ */
+int
+dn_queue_packet(struct new_queue *q, struct mbuf* m)
+{
+ struct new_fs *f = &(q->fs->fs);
+ uint64_t len = m->m_pkthdr.len;
+
+ /* Update statistics, then check reasons to drop pkt. */
+ q->tot_bytes += m->m_pkthdr.len;
+ q->tot_pkts++;
+
+ if (f->plr && random() < f->plr)
+ goto drop;
+ if (f->flags & DN_QSIZE_BYTES) {
+ if (q->len_bytes > f->qsize)
+ goto drop;
+ } else if (q->lenght >= f->qsize) {
+ goto drop;
+ }
+ mq_append(&q->mq, m);
+ q->lenght++;
+ q->len_bytes += len;
+ return 0;
+
+drop:
+ io_pkt_drop++;
+ q->drops++;
+ FREE_PKT(m);
+ return 1;
+}
+
/*
* Fetch packets from the delay line which are due now. If there are
* leftover packets, reinsert the delay line in the heap.
*/
-static struct mbuf *
-transmit_event(struct delay_line *dline, dn_key now)
+static void
+transmit_event(struct mq *q, struct delay_line *dline, dn_key now)
{
- struct mbuf *m;
- struct mbuf *head = NULL, *tail = NULL;
+ struct mbuf *m = NULL;
struct dn_pkt_tag *pkt = NULL;
/* XXX we are under scheduler lock */
- while ((m = dline->head) != NULL) {
+ while ((m = dline->mq.head) != NULL) {
pkt = dn_tag_get(m);
if (!DN_KEY_LEQ(pkt->output_time, now))
break;
- dline->head = m->m_nextpkt;
- if (tail != NULL)
- tail->m_nextpkt = m;
- else
*** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
More information about the svn-src-user
mailing list