svn commit: r201762 - user/luigi/ipfw3-head/sys/netinet/ipfw
Luigi Rizzo
luigi at FreeBSD.org
Thu Jan 7 23:17:49 UTC 2010
Author: luigi
Date: Thu Jan 7 23:17:48 2010
New Revision: 201762
URL: http://svn.freebsd.org/changeset/base/201762
Log:
snapshot of current version
Modified:
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_dummynet.c
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Thu Jan 7 22:59:08 2010 (r201761)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_sched.h Thu Jan 7 23:17:48 2010 (r201762)
@@ -114,7 +114,7 @@ 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 gen *f, struct mbuf *m,
+ int (*enqueue)(void *s, struct dn_id *f, struct mbuf *m,
struct ipfw_flow_id *id);
struct mbuf * (*dequeue)(void *s);
@@ -123,15 +123,15 @@ struct dn_sched {
int (*new_sched)(void *v);
int (*free_sched)(void *s);
- int (*new_fs)(char *command, struct gen *g, int reconfigure);
- int (*free_fs)(struct gen *f);
+ int (*new_fs)(char *command, struct dn_id *g, int reconfigure);
+ int (*free_fs)(struct dn_id *f);
- int (*new_queue)(struct new_queue *q, struct gen *f);
+ int (*new_queue)(struct new_queue *q, struct dn_id *f);
int (*free_queue)(struct new_queue *q);
int (*drain_queue)(void *s, int flag);
};
-SLIST_HEAD(scheduler_head, dn_sched);
+SLIST_HEAD(dn_sched_head, dn_sched);
/*
* Additionally, dummynet exports some variables, functions and macros
@@ -158,7 +158,7 @@ int dn_delete_queue (struct new_queue *q
* - id: flow id for this queue
* - size: size of the queue, including the private data
*/
-struct new_queue * dn_create_queue(struct gen *f, void *s, int i,
+struct new_queue * dn_create_queue(struct dn_id *f, void *s, int i,
struct ipfw_flow_id *id);
/* Allocate an hash table.
@@ -189,7 +189,7 @@ int dn_drop_packet(struct new_queue *q,
* - f: pointer to the flowset (private data)
* - rq_size: size of the hash table
*/
-int dn_i_hash_id(struct ipfw_flow_id *id, struct gen *f, int rq_size);
+int dn_i_hash_id(struct ipfw_flow_id *id, struct dn_id *f, int rq_size);
/* Returns the queue that match the flowid at the index i, if exists.
* Returns NULL if the queue doesn't exist.
@@ -200,7 +200,7 @@ int dn_i_hash_id(struct ipfw_flow_id *id
* the flowset generic data
*/
struct new_queue * dn_q_hash_id(struct ipfw_flow_id *id, int i,
- struct new_queue **rq, struct gen *f);
+ struct new_queue **rq, struct dn_id *f);
int dn_sched_modevent(module_t mod, int cmd, void *arg);
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Thu Jan 7 22:59:08 2010 (r201761)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dn_io.c Thu Jan 7 23:17:48 2010 (r201762)
@@ -59,6 +59,7 @@ __FBSDID("$FreeBSD$");
#include <netinet/ipfw/dn_heap.h>
#include <netinet/ip_dummynet.h>
#include <netinet/ipfw/ip_dn_private.h>
+#include <netinet/ipfw/dn_sched.h>
#include <netinet/if_ether.h> /* various ether_* routines */
@@ -86,12 +87,11 @@ struct dn_parms dn_cfg = {
.red_max_pkt_size = 1500, /* RED - default max packet size */
};
-//static struct timeval t;
-static long tick_last; /* Last tick duration (usec). */
-static long tick_delta; /* Last vs standard tick diff (usec). */
-static long tick_delta_sum; /* Accumulated tick difference (usec).*/
-static long tick_adjustment; /* Tick adjustments done. */
-static long tick_lost; /* Lost(coalesced) ticks number. */
+//static long tick_last; /* Last tick duration (usec). */
+static long tick_delta; /* Last vs standard tick diff (usec). */
+static long tick_delta_sum; /* Accumulated tick difference (usec).*/
+static long tick_adjustment; /* Tick adjustments done. */
+static long tick_lost; /* Lost(coalesced) ticks number. */
/* Adjusted vs non-adjusted curr_time difference (ticks). */
static long tick_diff;
@@ -100,6 +100,13 @@ static unsigned long io_pkt_fast;
static unsigned long io_pkt_drop;
/*
+ * We use a heap to store entities for which we have pending timer events.
+ * The heap is checked at every tick and all entities with expired events
+ * are extracted.
+ */
+static struct dn_heap *system_heap;
+
+/*
* Three heaps contain queues and pipes that the scheduler handles:
*
* ready_heap contains all dn_flow_queue related to fixed-rate pipes.
@@ -125,7 +132,7 @@ static unsigned long io_pkt_drop;
* (a better name would be useful...).
*/
#define MAX64(x,y) (( (int64_t) ( (y)-(x) )) > 0 ) ? (y) : (x)
-#define MY_M 16 /* number of left shift to obtain a larger precision */
+#define MY_M 16 /* shift for fixed point arithmetic */
/*
* XXX With this scaling, max 1000 flows, max weight 100, 1Gbit/s, the
@@ -134,16 +141,9 @@ static unsigned long io_pkt_drop;
MALLOC_DEFINE(M_DUMMYNET, "dummynet", "dummynet heap");
-static void transmit_event(struct dn_pipe *pipe, struct mbuf **head,
- struct mbuf **tail);
-static void ready_event(struct dn_flow_queue *q, struct mbuf **head,
- struct mbuf **tail);
-static void ready_event_wfq(struct dn_pipe *p, struct mbuf **head,
- struct mbuf **tail);
-
struct dn_heap ready_heap, extract_heap, wfq_ready_heap ;
-struct dn_pipe_head pipehash[DN_HASHSIZE]; /* all pipes */
-struct dn_flow_set_head flowsethash[DN_HASHSIZE]; /* all flowsets */
+struct new_pipe_head pipehash[DN_HASHSIZE]; /* all pipes */
+struct new_fs_head flowsethash[DN_HASHSIZE]; /* all flowsets */
extern void (*bridge_dn_p)(struct mbuf *, struct ifnet *);
@@ -244,11 +244,11 @@ struct dn_pkt_tag {
struct ipfw_rule_ref rule; /* matching rule */
/* second part, dummynet specific */
- int dn_dir; /* action when packet comes out. */
- /* see ip_fw_private.h */
- dn_key output_time; /* when the pkt is due for delivery */
- struct ifnet *ifp; /* interface, for ip_output */
- struct _ip6dn_args ip6opt; /* XXX ipv6 options */
+ int dn_dir; /* action when packet comes out.*/
+ /* see ip_fw_private.h */
+ dn_key output_time; /* when the pkt is due for delivery*/
+ struct ifnet *ifp; /* interface, for ip_output */
+ struct _ip6dn_args ip6opt; /* XXX ipv6 options */
};
/*
@@ -268,55 +268,43 @@ dn_tag_get(struct mbuf *m)
}
/*
- * Scheduler functions:
- *
- * transmit_event() is called when the delay-line needs to enter
- * the scheduler, either because of existing pkts getting ready,
- * or new packets entering the queue. The event handled is the delivery
- * time of the packet.
- *
- * ready_event() does something similar with fixed-rate queues, and the
- * event handled is the finish time of the head pkt.
- *
- * wfq_ready_event() does something similar with WF2Q queues, and the
- * event handled is the start time of the head pkt.
- *
- * In all cases, we make sure that the data structures are consistent
- * before passing pkts out, because this might trigger recursive
- * invocations of the procedures.
+ * It is called when we have some packet from delay line to send.
+ * If there are leftover packets, this delay line is reinserted into extract
+ * heap
*/
-static void
-transmit_event(struct dn_pipe *pipe, struct mbuf **head, struct mbuf **tail)
+static
+struct mbuf *
+transmit_event(struct delay_line *dline, dn_key l_curr_time)
{
- struct mbuf *m;
- struct dn_pkt_tag *pkt;
-
- DUMMYNET_LOCK_ASSERT();
+ struct mbuf *m;
+ struct dn_pkt_tag *pkt;
- while ((m = pipe->head) != NULL) {
- pkt = dn_tag_get(m);
- if (!DN_KEY_LEQ(pkt->output_time, curr_time))
- break;
+ struct mbuf *head = NULL, *tail = NULL;
+ /* XXX scheduler lock */
+ while ((m = dline->head) != NULL) {
+ pkt = dn_tag_get(m);
+ if (!DN_KEY_LEQ(pkt->output_time, l_curr_time))
+ break;
+ dline->head = m->m_nextpkt;
+ if (tail != NULL)
+ tail->m_nextpkt = m;
+ else
+ head = m;
+ tail = m;
+ }
- pipe->head = m->m_nextpkt;
- if (*tail != NULL)
- (*tail)->m_nextpkt = m;
- else
- *head = m;
- *tail = m;
- }
- if (*tail != NULL)
- (*tail)->m_nextpkt = NULL;
+ if (tail != NULL)
+ tail->m_nextpkt = NULL;
- /* If there are leftover packets, put into the heap for next event. */
- if ((m = pipe->head) != NULL) {
- pkt = dn_tag_get(m);
- /*
- * XXX Should check errors on heap_insert, by draining the
- * whole pipe p and hoping in the future we are more successful.
- */
- heap_insert(&extract_heap, pkt->output_time, pipe);
- }
+ /* If there are leftover packets, put into the heap for next event. */
+ if ((m = dline->head) != NULL) {
+ pkt = dn_tag_get(m);
+ //DN_HEAP_LOCK();
+ heap_insert(system_heap, pkt->output_time, dline);
+ //DN_HEAP_UNLOCK();
+ }
+ /* XXX scheduler unlock */
+ return head;
}
#define div64(a, b) ((int64_t)(a) / (int64_t)(b))
@@ -345,7 +333,7 @@ set_ticks(struct mbuf *m, struct dn_flow
* so we need to divide by 1000.
*/
static dn_key
-compute_extra_bits(struct mbuf *pkt, struct dn_pipe *p)
+compute_extra_bits(struct mbuf *pkt, struct new_pipe *p)
{
int index;
dn_key extra_bits;
@@ -362,253 +350,27 @@ compute_extra_bits(struct mbuf *pkt, str
return extra_bits;
}
-/*
- * extract pkt from queue, compute output time (could be now)
- * and put into delay line (p_queue)
- */
+/* Insert packet pkt into delay line of si. */
static void
-move_pkt(struct mbuf *pkt, struct dn_flow_queue *q, struct dn_pipe *p,
- int len)
+move_pkt(struct mbuf *pkt, struct new_pipe *p, struct new_sch_inst *si,
+ dn_key l_curr_time)
{
struct dn_pkt_tag *dt = dn_tag_get(pkt);
+ struct delay_line *d = si->dline;
+
+ dt->output_time = l_curr_time + p->delay ;
- q->head = pkt->m_nextpkt ;
- q->len-- ;
- q->len_bytes -= len ;
-
- dt->output_time = curr_time + p->delay ;
-
- if (p->head == NULL)
- p->head = pkt;
+ if (d->head == NULL)
+ d->head = pkt;
else
- p->tail->m_nextpkt = pkt;
- p->tail = pkt;
- p->tail->m_nextpkt = NULL;
-}
-
-/*
- * ready_event() is invoked every time the queue must enter the
- * scheduler, either because the first packet arrives, or because
- * a previously scheduled event fired.
- * On invokation, drain as many pkts as possible (could be 0) and then
- * if there are leftover packets reinsert the pkt in the scheduler.
- */
-static void
-ready_event(struct dn_flow_queue *q, struct mbuf **head, struct mbuf **tail)
-{
- struct mbuf *pkt;
- struct dn_pipe *p = q->fs->pipe;
- int p_was_empty;
-
- DUMMYNET_LOCK_ASSERT();
-
- if (p == NULL) {
- printf("dummynet: ready_event- pipe is gone\n");
- return;
- }
- p_was_empty = (p->head == NULL);
-
- /*
- * Schedule fixed-rate queues linked to this pipe:
- * account for the bw accumulated since last scheduling, then
- * drain as many pkts as allowed by q->numbytes and move to
- * the delay line (in p) computing output time.
- * bandwidth==0 (no limit) means we can drain the whole queue,
- * setting len_scaled = 0 does the job.
- */
- q->numbytes += (curr_time - q->sched_time) * p->bandwidth;
- while ((pkt = q->head) != NULL) {
- int len = pkt->m_pkthdr.len;
- dn_key len_scaled = p->bandwidth ? len*8*hz
- + q->extra_bits*hz
- : 0;
-
- if (DN_KEY_GT(len_scaled, q->numbytes))
- break;
- q->numbytes -= len_scaled;
- move_pkt(pkt, q, p, len);
- if (q->head)
- q->extra_bits = compute_extra_bits(q->head, p);
- }
- /*
- * If we have more packets queued, schedule next ready event
- * (can only occur when bandwidth != 0, otherwise we would have
- * flushed the whole queue in the previous loop).
- * To this purpose we record the current time and compute how many
- * ticks to go for the finish time of the packet.
- */
- if ((pkt = q->head) != NULL) { /* this implies bandwidth != 0 */
- dn_key t = set_ticks(pkt, q, p); /* ticks i have to wait */
-
- q->sched_time = curr_time;
- heap_insert(&ready_heap, curr_time + t, (void *)q);
- /*
- * XXX Should check errors on heap_insert, and drain the whole
- * queue on error hoping next time we are luckier.
- */
- } else /* RED needs to know when the queue becomes empty. */
- q->idle_time = curr_time;
-
- /*
- * If the delay line was empty call transmit_event() now.
- * Otherwise, the scheduler will take care of it.
- */
- if (p_was_empty)
- transmit_event(p, head, tail);
-}
-
-/* callback to clean the idle heap */
-static int
-clean_fq(void *_q, uintptr_t arg)
-{
- struct dn_flow_queue *q = _q;
-
- q->F = 0;
- q->S = q->F + 1;
- return HEAP_SCAN_DEL;
+ d->tail->m_nextpkt = pkt;
+ d->tail = pkt;
+ d->tail->m_nextpkt = NULL;
}
-/*
- * Called when we can transmit packets on WF2Q queues. Take pkts out of
- * the queues at their start time, and enqueue into the delay line.
- * Packets are drained until p->numbytes < 0. As long as
- * len_scaled >= p->numbytes, the packet goes into the delay line
- * with a deadline p->delay. For the last packet, if p->numbytes < 0,
- * there is an additional delay.
- */
-static void
-ready_event_wfq(struct dn_pipe *p, struct mbuf **head, struct mbuf **tail)
-{
- int p_was_empty = (p->head == NULL);
- struct dn_heap *sch = p->scheduler_heap;
- struct dn_heap *neh = p->not_eligible_heap;
- int64_t p_numbytes = p->numbytes;
-
- /*
- * p->numbytes is only 32bits in FBSD7, but we might need 64 bits.
- * Use a local variable for the computations, and write back the
- * results when done, saturating if needed.
- * The local variable has no impact on performance and helps
- * reducing diffs between the various branches.
- */
-
- DUMMYNET_LOCK_ASSERT();
-
- if (p->if_name[0] == 0) /* tx clock is simulated */
- p_numbytes += (curr_time - p->sched_time) * p->bandwidth;
- else { /*
- * tx clock is for real,
- * the ifq must be empty or this is a NOP.
- */
- if (p->ifp && p->ifp->if_snd.ifq_head != NULL)
- return;
- else {
- DPRINTF(("dummynet: pipe %d ready from %s --\n",
- p->pipe_nr, p->if_name));
- }
- }
-
- /*
- * While we have backlogged traffic AND credit, we need to do
- * something on the queue.
- */
- while (p_numbytes >= 0 && (sch->elements > 0 || neh->elements > 0)) {
- if (sch->elements > 0) {
- /* Have some eligible pkts to send out. */
- struct dn_flow_queue *q = HEAP_TOP(sch)->object;
- struct mbuf *pkt = q->head;
- struct dn_flow_set *fs = q->fs;
- uint64_t len = pkt->m_pkthdr.len;
- int len_scaled = p->bandwidth ? len * 8 * hz : 0;
-
- heap_extract(sch, NULL); /* Remove queue from heap. */
- p_numbytes -= len_scaled;
- move_pkt(pkt, q, p, len);
-
- p->V += div64((len << MY_M), p->sum); /* Update V. */
- q->S = q->F; /* Update start time. */
- if (q->len == 0) {
- /* Flow not backlogged any more. */
- fs->backlogged--;
- heap_insert(p->idle_heap, q->F, q);
- } else {
- /* Still backlogged. */
-
- /*
- * Update F and position in backlogged queue,
- * then put flow in not_eligible_heap
- * (we will fix this later).
- */
- len = (q->head)->m_pkthdr.len;
- q->F += div64((len << MY_M), fs->weight);
- if (DN_KEY_LEQ(q->S, p->V))
- heap_insert(neh, q->S, q);
- else
- heap_insert(sch, q->F, q);
- }
- }
- /*
- * Now compute V = max(V, min(S_i)). Remember that all elements
- * in sch have by definition S_i <= V so if sch is not empty,
- * V is surely the max and we must not update it. Conversely,
- * if sch is empty we only need to look at neh.
- */
- if (sch->elements == 0 && neh->elements > 0)
- p->V = MAX64(p->V, HEAP_TOP(neh)->key);
- /* Move from neh to sch any packets that have become eligible */
- while (neh->elements > 0 && DN_KEY_LEQ(HEAP_TOP(neh)->key, p->V)) {
- struct dn_flow_queue *q = HEAP_TOP(neh)->object;
- heap_extract(neh, NULL);
- heap_insert(sch, q->F, q);
- }
-
- if (p->if_name[0] != '\0') { /* Tx clock is from a real thing */
- p_numbytes = -1; /* Mark not ready for I/O. */
- break;
- }
- }
- if (sch->elements == 0 && neh->elements == 0 && p_numbytes >= 0) {
- p->idle_time = curr_time;
- /*
- * No traffic and no events scheduled.
- * We can get rid of idle-heap.
- */
- if (p->idle_heap->elements > 0) {
- heap_scan(p->idle_heap, clean_fq, 0);
- p->sum = 0;
- p->V = 0;
- p->idle_heap->elements = 0;
- }
- }
- /*
- * If we are getting clocks from dummynet (not a real interface) and
- * If we are under credit, schedule the next ready event.
- * Also fix the delivery time of the last packet.
- */
- if (p->if_name[0]==0 && p_numbytes < 0) { /* This implies bw > 0. */
- dn_key t = 0; /* Number of ticks i have to wait. */
-
- if (p->bandwidth > 0)
- t = div64(p->bandwidth - 1 - p_numbytes, p->bandwidth);
- dn_tag_get(p->tail)->output_time += t;
- p->sched_time = curr_time;
- heap_insert(&wfq_ready_heap, curr_time + t, (void *)p);
- /*
- * XXX Should check errors on heap_insert, and drain the whole
- * queue on error hoping next time we are luckier.
- */
- }
-
- /* Write back p_numbytes (adjust 64->32bit if necessary). */
- p->numbytes = p_numbytes;
-
- /*
- * If the delay line was empty call transmit_event() now.
- * Otherwise, the scheduler will take care of it.
- */
- if (p_was_empty)
- transmit_event(p, head, tail);
-}
+struct new_sch_inst *
+find_scheduler(struct new_sch *sch_t, struct new_fs *fs,
+ struct ipfw_flow_id *id, dn_key l_curr_time);
/*
* The timer handler for dummynet. Time is computed in ticks, but
@@ -618,8 +380,9 @@ ready_event_wfq(struct dn_pipe *p, struc
void
dummynet_task(void *context, int pending)
{
+#if 0
struct mbuf *head = NULL, *tail = NULL;
- struct dn_pipe *pipe;
+ struct new_pipe *pipe;
struct dn_heap *heaps[3];
struct dn_heap *h;
void *p; /* generic parameter to handler */
@@ -713,7 +476,7 @@ dummynet_task(void *context, int pending
if (head != NULL)
dummynet_send(head);
-
+#endif
dn_reschedule();
}
@@ -800,6 +563,7 @@ dummynet_send(struct mbuf *m)
}
}
+#if 0
/*
* Unconditionally expire empty queues in case of shortage.
* Returns the number of queues freed.
@@ -1081,11 +845,12 @@ red_drops(struct dn_flow_set *fs, struct
return (0); /* accept */
}
+#endif
-struct dn_flow_set *
+struct new_fs *
ipdn_locate_flowset(int fs_nr)
{
- struct dn_flow_set *fs;
+ struct new_fs *fs;
SLIST_FOREACH(fs, &flowsethash[HASH(fs_nr)], next)
if (fs->fs_nr == fs_nr)
@@ -1094,10 +859,10 @@ ipdn_locate_flowset(int fs_nr)
return (NULL);
}
-struct dn_pipe *
+struct new_pipe *
ipdn_locate_pipe(int pipe_nr)
{
- struct dn_pipe *pipe;
+ struct new_pipe *pipe;
SLIST_FOREACH(pipe, &pipehash[HASH(pipe_nr)], next)
if (pipe->pipe_nr == pipe_nr)
@@ -1106,6 +871,31 @@ ipdn_locate_pipe(int pipe_nr)
return (NULL);
}
+struct ipfw_flow_id *
+do_mask(struct ipfw_flow_id *mask, struct ipfw_flow_id *id);
+/* Do masking depending of flow id */
+struct ipfw_flow_id *
+do_mask(struct ipfw_flow_id *mask, struct ipfw_flow_id *id)
+{
+ int is_v6 = IS_IP6_FLOW_ID(id);
+
+ id->dst_port &= mask->dst_port;
+ id->src_port &= mask->src_port;
+ id->proto &= mask->proto;
+ id->flags = 0; /* we don't care about this one */
+ if (is_v6) {
+ APPLY_MASK(&id->dst_ip6, &mask->dst_ip6);
+ APPLY_MASK(&id->src_ip6, &mask->src_ip6);
+ id->flow_id6 &= mask->flow_id6;
+ }
+ else {
+ id->dst_ip &= mask->dst_ip;
+ id->src_ip &= mask->src_ip;
+ }
+
+ return id;
+}
+
/*
* dummynet hook for packets. Below 'pipe' is a pipe or a queue
* depending on whether WF2Q or fixed bw is used.
@@ -1124,15 +914,19 @@ ipdn_locate_pipe(int pipe_nr)
int
dummynet_io(struct mbuf **m0, int dir, struct ip_fw_args *fwa)
{
- struct mbuf *m = *m0, *head = NULL, *tail = NULL;
+ struct mbuf *m = *m0, *head = NULL;
struct dn_pkt_tag *pkt;
struct m_tag *mtag;
- struct dn_flow_set *fs = NULL;
- struct dn_pipe *pipe = NULL;
- uint64_t len = m->m_pkthdr.len;
- struct dn_flow_queue *q = NULL;
+ struct new_fs *fs = NULL;
+ struct new_pipe *pipe = NULL;
+ struct new_queue *q = NULL;
int fs_id = fwa->rule.info & IPFW_INFO_MASK;
- int is_pipe = 0;
+ struct new_sch *sch;
+ struct new_sch_inst *sch_inst;
+ struct delay_line *dline;
+ int ret;
+ dn_key l_curr_time; /* save a copy of curr_time */
+ int delay_line_idle;
if (fwa->rule.info & IPFW_IS_PIPE)
fs_id += DN_PIPEOFFSET;
@@ -1146,10 +940,10 @@ dummynet_io(struct mbuf **m0, int dir, s
if (fs == NULL)
goto dropit; /* This queue/pipe does not exist! */
-#if 0
+
if (fs->sched_id != dn_cfg.id) {
/* configuration changed, update */
- int ret = reconfigure(fs);
+ int ret = dn_fs_config(fs);
if (ret)
goto dropit;
/* find again, just in case things changed */
@@ -1160,25 +954,19 @@ dummynet_io(struct mbuf **m0, int dir, s
sch = fs->sched;
if (sch == NULL)
goto dropit;
-#endif
- q = find_queue(fs, &(fwa->f_id));
- if (q == NULL)
- goto dropit; /* Cannot allocate queue. */
-
- /* Update statistics, then check reasons to drop pkt. */
- q->tot_bytes += len;
- q->tot_pkts++;
- if (fs->plr && random() < fs->plr)
- goto dropit; /* Random pkt drop. */
- if (fs->flags_fs & DN_QSIZE_IS_BYTES) {
- if (q->len_bytes > fs->qsize)
- goto dropit; /* Queue size overflow. */
- } else {
- if (q->len >= fs->qsize)
- goto dropit; /* Queue count overflow. */
- }
- if (fs->flags_fs & DN_IS_RED && red_drops(fs, q, len))
+ pipe = sch->pipe;
+ if (pipe == NULL) /* should not happen ? */
+ goto dropit;
+
+ l_curr_time = curr_time;
+ sch_inst = find_scheduler(sch, fs, &(fwa->f_id), l_curr_time);
+ if (sch_inst == NULL)
goto dropit;
+ dline = sch_inst->dline;
+ delay_line_idle = (dline->head == NULL);
+
+ /* Now do the masking */
+ do_mask(&fs->flow_mask, &(fwa->f_id));
/* tag the mbuf */
mtag = m_tag_get(PACKET_TAG_DUMMYNET,
@@ -1197,128 +985,96 @@ dummynet_io(struct mbuf **m0, int dir, s
pkt->dn_dir = dir;
pkt->ifp = fwa->oif;
- if (q->head == NULL)
- q->head = m;
- else
- q->tail->m_nextpkt = m;
- q->tail = m;
- q->len++;
- q->len_bytes += len;
-
- if (q->head != m) /* Flow was not idle, we are done. */
- goto done;
-
- if (is_pipe) { /* Fixed rate queues. */
- if (q->idle_time < curr_time) {
- /* Calculate available burst size. */
- q->numbytes +=
- (curr_time - q->idle_time - 1) * pipe->bandwidth;
- if (q->numbytes > pipe->burst)
- q->numbytes = pipe->burst;
- if (dn_cfg.io_fast)
- q->numbytes += pipe->bandwidth;
- }
- } else { /* WF2Q. */
- if (pipe->idle_time < curr_time &&
- pipe->scheduler_heap->elements == 0 &&
- pipe->not_eligible_heap->elements == 0) {
- /* Calculate available burst size. */
- pipe->numbytes +=
- (curr_time - pipe->idle_time - 1) * pipe->bandwidth;
- if (pipe->numbytes > 0 && pipe->numbytes > pipe->burst)
- pipe->numbytes = pipe->burst;
- if (dn_cfg.io_fast)
- pipe->numbytes += pipe->bandwidth;
- }
- pipe->idle_time = curr_time;
- }
- /* Necessary for both: fixed rate & WF2Q queues. */
- q->idle_time = curr_time;
-
/*
- * If we reach this point the flow was previously idle, so we need
- * to schedule it. This involves different actions for fixed-rate or
- * WF2Q queues.
+ * - 'sch_inst + 1' is the pointer to scheduler instance's
+ * private data, 'fs->alg_fs' is the flowset's private data,
+ * 'm' is the packet, 'id' is the masked flowid of the packet
+ *
+ * NOTE: If the scheduler function wants really enqueue the
+ * packet, it must call the queue_packet()
*/
- if (is_pipe) {
- /* Fixed-rate queue: just insert into the ready_heap. */
- dn_key t = 0;
-
- if (pipe->bandwidth) {
- q->extra_bits = compute_extra_bits(m, pipe);
- t = set_ticks(m, q, pipe);
- }
- q->sched_time = curr_time;
- if (t == 0) /* Must process it now. */
- ready_event(q, &head, &tail);
- else
- heap_insert(&ready_heap, curr_time + t , q);
- } else {
- /*
- * WF2Q. First, compute start time S: if the flow was
- * idle (S = F + 1) set S to the virtual time V for the
- * controlling pipe, and update the sum of weights for the pipe;
- * otherwise, remove flow from idle_heap and set S to max(F,V).
- * Second, compute finish time F = S + len / weight.
- * Third, if pipe was idle, update V = max(S, V).
- * Fourth, count one more backlogged flow.
- */
- if (DN_KEY_GT(q->S, q->F)) { /* Means timestamps are invalid. */
- q->S = pipe->V;
- pipe->sum += fs->weight; /* Add weight of new queue. */
- } else {
- heap_extract(pipe->idle_heap, q);
- q->S = MAX64(q->F, pipe->V);
- }
- q->F = q->S + div64(len << MY_M, fs->weight);
- if (pipe->not_eligible_heap->elements == 0 &&
- pipe->scheduler_heap->elements == 0)
- pipe->V = MAX64(q->S, pipe->V);
- fs->backlogged++;
- /*
- * Look at eligibility. A flow is not eligibile if S>V (when
- * this happens, it means that there is some other flow already
- * scheduled for the same pipe, so the scheduler_heap cannot be
- * empty). If the flow is not eligible we just store it in the
- * not_eligible_heap. Otherwise, we store in the scheduler_heap
- * and possibly invoke ready_event_wfq() right now if there is
- * leftover credit.
- * Note that for all flows in scheduler_heap (SCH), S_i <= V,
- * and for all flows in not_eligible_heap (NEH), S_i > V.
- * So when we need to compute max(V, min(S_i)) forall i in
- * SCH+NEH, we only need to look into NEH.
- */
- if (DN_KEY_GT(q->S, pipe->V)) { /* Not eligible. */
- if (pipe->scheduler_heap->elements == 0)
- printf("dummynet: ++ ouch! not eligible but empty scheduler!\n");
- heap_insert(pipe->not_eligible_heap, q->S, q);
- } else {
- heap_insert(pipe->scheduler_heap, q->F, q);
- if (pipe->numbytes >= 0) { /* Pipe is idle. */
- if (pipe->scheduler_heap->elements != 1)
- printf("dummynet: OUCH! pipe should have been idle!\n");
- DPRINTF(("dummynet: waking up pipe %d at %d\n",
- pipe->pipe_nr, (int)(q->F >> MY_M)));
- pipe->sched_time = curr_time;
- ready_event_wfq(pipe, &head, &tail);
- }
- }
+ ret = sch->fp->enqueue(
+ (sch_inst + 1), fs->alg_fs, m,
+ &(fwa->f_id));
+
+ if (ret) { /* packet was dropped by enqueue() */
+ *m0 = NULL;
+ goto dropit;
}
-done:
- if (head == m && (dir & PROTO_LAYER2) == 0 ) {
- /* Fast io. */
- io_pkt_fast++;
- if (m->m_nextpkt != NULL)
- printf("dummynet: fast io: pkt chain detected!\n");
- head = m->m_nextpkt = NULL;
- } else
- *m0 = NULL; /* Normal io. */
- DUMMYNET_UNLOCK();
- if (head != NULL)
- dummynet_send(head);
- return (0);
+ /*
+ * Now check if the dequeue should be called now.
+ * If the instance is in the heap, the dequeue() will be called later,
+ * else if the instance has credit the dequeue() is called now.
+ */
+ if (!(sch_inst->flags & DN_SCH_ACTIVE)) {
+ /* If the instance is not in the heap, credit must be >= 0 */
+ struct mbuf *tosend;
+ dn_key len_scaled;
+
+ /* If the instance isn't in the heap, it is idle, so we can skip
+ * some checks XXX
+ */
+ if (sch->burst) {
+ sch_inst->numbytes = (l_curr_time - sch_inst->idle_time) *
+ pipe->bandwidth;
+ if (sch_inst->numbytes > sch->burst)
+ sch_inst->numbytes = sch->burst;
+ sch_inst->numbytes += dn_cfg.io_fast ? pipe->bandwidth : 0;
+ } else
+ sch_inst->numbytes = dn_cfg.io_fast ? pipe->bandwidth : 0;
+
+ sch_inst->idle_time = l_curr_time;
+
+ /* Doing an 'if' instead of 'while' because only the packet
+ * just enqueued can be returned by dequeue() */
+ tosend = sch->fp->dequeue(sch_inst + 1);
+ if (tosend) {
+ len_scaled = pipe->bandwidth ? tosend->m_pkthdr.len * 8 * hz +
+ compute_extra_bits(tosend, pipe) * hz : 0;
+ sch_inst->numbytes -= len_scaled;
+ /* Move packet in the delay line XXX three parameters? */
+ move_pkt(tosend, pipe, sch_inst, l_curr_time);
+ if (sch_inst->numbytes < 0) {
+ /*
+ * Credit became negative, so insert the instance in the
+ * heap so that it will not be wake up until credit come
+ * back positive
+ * NOTE: numbytes < 0 implies bandwidth != 0.
+ */
+ dn_key t = 0, tmp;
+ t = (pipe->bandwidth - 1 - sch_inst->numbytes) /
+ pipe->bandwidth;
+ /* Delay the output time because under credit */
+ (dn_tag_get(dline->tail))->output_time += t;
+
+ sch_inst->ptr_sched->inst_counter++;
+ sch_inst->flags |= DN_SCH_ACTIVE;
+ tmp = l_curr_time + t;
+ //DN_HEAP_LOCK();
+ heap_insert(system_heap, (uint64_t)tmp, sch_inst);
+ //DN_HEAP_UNLOCK();
+ }
+ if (delay_line_idle)
+ head = transmit_event(dline, l_curr_time);
+ }
+ }
+
+ if (dn_cfg.io_fast && head == m && (dir & PROTO_LAYER2) == 0 ) {
+ /* fast io */
+ io_pkt_fast++;
+ printf("dummynet TEST: ** IOFAST **\n");
+ if (m->m_nextpkt != NULL)
+ printf("dummynet: fast io: pkt chain detected!\n");
+ head = m->m_nextpkt = NULL;
+ } else
+ *m0 = NULL;
+ DUMMYNET_UNLOCK();
+ if (head != NULL)
+ dummynet_send(head);
+
+ return 0;
dropit:
io_pkt_drop++;
@@ -1327,5 +1083,5 @@ dropit:
DUMMYNET_UNLOCK();
FREE_PKT(m);
*m0 = NULL;
- return ((fs && (fs->flags_fs & DN_NOERROR)) ? 0 : ENOBUFS);
+ return ((fs && (fs->flags & DN_NOERROR)) ? 0 : ENOBUFS);
}
Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Thu Jan 7 22:59:08 2010 (r201761)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/ip_dummynet.c Thu Jan 7 23:17:48 2010 (r201762)
@@ -107,7 +107,7 @@ static __inline void dn_free_pkts(struct
}
static void
-free_pipe(struct dn_pipe *p)
+free_pipe(struct new_pipe *p)
{
if (p->samples)
free(p->samples, M_DUMMYNET);
@@ -121,9 +121,10 @@ free_pipe(struct dn_pipe *p)
* For the one in dn_pipe MUST also cleanup ready_heap...
*/
static void
-purge_flow_set(struct dn_flow_set *fs, int all)
+purge_flow_set(struct new_fs *fs, int all)
{
- struct dn_flow_queue *q, *qn;
+#if 0
+ struct new_queue *q, *qn;
int i;
DUMMYNET_LOCK_ASSERT();
@@ -148,6 +149,7 @@ purge_flow_set(struct dn_flow_set *fs, i
if (fs->pipe == NULL || fs != &(fs->pipe->fs))
free(fs, M_DUMMYNET);
}
+#endif
}
/*
@@ -156,9 +158,9 @@ purge_flow_set(struct dn_flow_set *fs, i
* to be deleted.
*/
static void
-purge_pipe(struct dn_pipe *pipe)
+purge_pipe(struct new_pipe *pipe)
{
-
+#if 0
purge_flow_set( &(pipe->fs), 1 );
dn_free_pkts(pipe->head);
@@ -166,6 +168,7 @@ purge_pipe(struct dn_pipe *pipe)
heap_free( pipe->scheduler_heap );
heap_free( pipe->not_eligible_heap );
heap_free( pipe->idle_heap );
+#endif
}
/*
@@ -175,8 +178,8 @@ purge_pipe(struct dn_pipe *pipe)
static void
dummynet_flush(void)
{
- struct dn_pipe *pipe, *pipe1;
- struct dn_flow_set *fs, *fs1;
+ struct new_pipe *pipe, *pipe1;
+ struct new_fs *fs, *fs1;
int i;
DUMMYNET_LOCK();
@@ -192,12 +195,12 @@ dummynet_flush(void)
*/
for (i = 0; i < DN_HASHSIZE; i++)
SLIST_FOREACH_SAFE(fs, &flowsethash[i], next, fs1) {
- SLIST_REMOVE(&flowsethash[i], fs, dn_flow_set, next);
+ SLIST_REMOVE(&flowsethash[i], fs, new_fs, next);
purge_flow_set(fs, 1);
}
for (i = 0; i < DN_HASHSIZE; i++)
SLIST_FOREACH_SAFE(pipe, &pipehash[i], next, pipe1) {
- SLIST_REMOVE(&pipehash[i], pipe, dn_pipe, next);
+ SLIST_REMOVE(&pipehash[i], pipe, new_pipe, next);
purge_pipe(pipe);
free_pipe(pipe);
}
@@ -263,7 +266,8 @@ config_red(struct dn_flow_set *p, struct
return (0);
}
-static int
+int alloc_hash(struct dn_flow_set *x, struct dn_flow_set *pfs);
+int
alloc_hash(struct dn_flow_set *x, struct dn_flow_set *pfs)
{
if (x->flags_fs & DN_HAVE_FLOW_MASK) { /* allocate some slots */
@@ -288,7 +292,8 @@ alloc_hash(struct dn_flow_set *x, struct
return 0 ;
}
-static void
+void set_fs_parms(struct dn_flow_set *x, struct dn_flow_set *src);
+void
set_fs_parms(struct dn_flow_set *x, struct dn_flow_set *src)
{
x->flags_fs = src->flags_fs;
@@ -333,6 +338,7 @@ do_config(void *p, int l)
static int
config_pipe(struct dn_pipe *p)
{
+#if 0
struct dn_flow_set *pfs = &(p->fs);
*** DIFF OUTPUT TRUNCATED AT 1000 LINES ***
More information about the svn-src-user
mailing list