Date: Mon, 11 Jan 2010 10:12:35 +0000 (UTC) From: Luigi Rizzo <luigi@FreeBSD.org> To: src-committers@freebsd.org, svn-src-user@freebsd.org Subject: svn commit: r202072 - in user/luigi/ipfw3-head: sbin/ipfw sys/netinet sys/netinet/ipfw Message-ID: <201001111012.o0BACZOr025242@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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 ***
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001111012.o0BACZOr025242>