diff options
Diffstat (limited to 'sys/netinet/ipfw/test')
| -rw-r--r-- | sys/netinet/ipfw/test/Makefile | 50 | ||||
| -rw-r--r-- | sys/netinet/ipfw/test/dn_test.h | 155 | ||||
| -rw-r--r-- | sys/netinet/ipfw/test/main.c | 636 | ||||
| -rw-r--r-- | sys/netinet/ipfw/test/mylist.h | 49 | ||||
| -rw-r--r-- | sys/netinet/ipfw/test/test_dn_heap.c | 162 | ||||
| -rw-r--r-- | sys/netinet/ipfw/test/test_dn_sched.c | 76 |
6 files changed, 1128 insertions, 0 deletions
diff --git a/sys/netinet/ipfw/test/Makefile b/sys/netinet/ipfw/test/Makefile new file mode 100644 index 0000000..bbeb942 --- /dev/null +++ b/sys/netinet/ipfw/test/Makefile @@ -0,0 +1,50 @@ +# +# $FreeBSD$ +# +# Makefile for building userland tests +# this is written in a form compatible with gmake + +SCHED_SRCS = test_dn_sched.c +SCHED_SRCS += dn_sched_fifo.c +SCHED_SRCS += dn_sched_wf2q.c +SCHED_SRCS += dn_sched_qfq.c +SCHED_SRCS += dn_sched_rr.c +SCHED_SRCS += dn_heap.c +SCHED_SRCS += main.c + +SCHED_OBJS=$(SCHED_SRCS:.c=.o) + +HEAP_SRCS = dn_heap.c test_dn_heap.c +HEAP_OBJS=$(HEAP_SRCS:.c=.o) + +VPATH= .:.. + +CFLAGS = -I.. -I. -Wall -Werror -O3 -DIPFW +TARGETS= test_sched # no test_heap by default + +all: $(TARGETS) + +test_heap : $(HEAP_OBJS) + $(CC) -o $@ $(HEAP_OBJS) + +test_sched : $(SCHED_OBJS) + $(CC) -o $@ $(SCHED_OBJS) + +$(SCHED_OBJS): dn_test.h +main.o: mylist.h + +clean: + - rm *.o $(TARGETS) *.core + +ALLSRCS = $(SCHED_SRCS) dn_test.h mylist.h \ + dn_sched.h dn_heap.h ip_dn_private.h Makefile +TMPBASE = /tmp/testXYZ +TMPDIR = $(TMPBASE)/test + +tgz: + -rm -rf $(TMPDIR) + mkdir -p $(TMPDIR) + -cp -p $(ALLSRCS) $(TMPDIR) + -(cd ..; cp -p $(ALLSRCS) $(TMPDIR)) + ls -la $(TMPDIR) + (cd $(TMPBASE); tar cvzf /tmp/test.tgz test) diff --git a/sys/netinet/ipfw/test/dn_test.h b/sys/netinet/ipfw/test/dn_test.h new file mode 100644 index 0000000..c56aa6a --- /dev/null +++ b/sys/netinet/ipfw/test/dn_test.h @@ -0,0 +1,155 @@ +/* + * $FreeBSD$ + * + * userspace compatibility code for dummynet schedulers + */ + +#ifndef _DN_TEST_H +#define _DN_TEST_H +#include <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <strings.h> /* bzero, ffs, ... */ +#include <string.h> /* strcmp */ +#include <errno.h> +#include <inttypes.h> +#include <sys/queue.h> +#include <sys/time.h> + + +extern int debug; +#define ND(fmt, args...) do {} while (0) +#define D1(fmt, args...) do {} while (0) +#define D(fmt, args...) fprintf(stderr, "%-8s " fmt "\n", \ + __FUNCTION__, ## args) +#define DX(lev, fmt, args...) do { \ + if (debug > lev) D(fmt, ## args); } while (0) + + +#define offsetof(t,m) (int)((&((t *)0L)->m)) + +#include <mylist.h> + +/* prevent include of other system headers */ +#define _NETINET_IP_VAR_H_ /* ip_fw_args */ +#define _IPFW2_H +#define _SYS_MBUF_H_ + +enum { + DN_QUEUE, +}; + +enum { + DN_SCHED_FIFO, + DN_SCHED_WF2QP, +}; + +struct dn_id { + int type, subtype, len, id; +}; +struct dn_fs { + int par[4]; /* flowset parameters */ + + /* simulation entries. + * 'index' is not strictly necessary + * y is used for the inverse mapping , + */ + int index; + int y; /* inverse mapping */ + int base_y; /* inverse mapping */ + int next_y; /* inverse mapping */ + int n_flows; + int first_flow; + int next_flow; /* first_flow + n_flows */ + /* + * when generating, let 'cur' go from 0 to n_flows-1, + * then point to flow first_flow + cur + */ + int cur; +}; +struct dn_sch { +}; +struct dn_flow { + struct dn_id oid; + int length; + int len_bytes; + int drops; + uint64_t tot_bytes; + uint32_t flow_id; + struct list_head h; /* used by the generator */ +}; +struct dn_link { +}; + +struct ip_fw_args { +}; + +struct mbuf { + struct { + int len; + } m_pkthdr; + struct mbuf *m_nextpkt; + int flow_id; /* for testing, index of a flow */ + //int flowset_id; /* for testing, index of a flowset */ + void *cfg; /* config args */ +}; + +#define MALLOC_DECLARE(x) +#define KASSERT(x, y) do { if (!(x)) printf y ; exit(0); } while (0) +struct ipfw_flow_id { +}; + +typedef void * module_t; +struct _md_t { + const char *name; + int (*f)(module_t, int, void *); + void *p; +}; +typedef struct _md_t moduledata_t; +#define DECLARE_MODULE(name, b, c, d) \ + moduledata_t *_g_##name = & b +#define MODULE_DEPEND(a, b, c, d, e) + +#ifdef IPFW +#include <dn_heap.h> +#include <ip_dn_private.h> +#include <dn_sched.h> +#else +struct dn_queue { + struct dn_fsk *fs; /* parent flowset. */ + struct dn_sch_inst *_si; /* parent sched instance. */ +}; +struct dn_schk { +}; +struct dn_fsk { + struct dn_fs fs; + struct dn_schk *sched; +}; +struct dn_sch_inst { + struct dn_schk *sched; +}; +struct dn_alg { + int type; + const char *name; + void *enqueue, *dequeue; + int q_datalen, si_datalen, schk_datalen; + int (*config)(struct dn_schk *); + int (*new_sched)(struct dn_sch_inst *); + int (*new_fsk)(struct dn_fsk *); + int (*new_queue)(struct dn_queue *q); +}; + +#endif + +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; +} + +#endif /* _DN_TEST_H */ diff --git a/sys/netinet/ipfw/test/main.c b/sys/netinet/ipfw/test/main.c new file mode 100644 index 0000000..be9fdf5 --- /dev/null +++ b/sys/netinet/ipfw/test/main.c @@ -0,0 +1,636 @@ +/* + * $FreeBSD$ + * + * Testing program for schedulers + * + * The framework include a simple controller which, at each + * iteration, decides whether we can enqueue and/or dequeue. + * Then the mainloop runs the required number of tests, + * keeping track of statistics. + */ + +#include "dn_test.h" + +struct q_list { + struct list_head h; +}; + +struct cfg_s { + int ac; + char * const *av; + + const char *name; + int loops; + struct timeval time; + + /* running counters */ + uint32_t _enqueue; + uint32_t drop; + uint32_t pending; + uint32_t dequeue; + + /* generator parameters */ + int th_min, th_max; + int maxburst; + int lmin, lmax; /* packet len */ + int flows; /* number of flows */ + int flowsets; /* number of flowsets */ + int wsum; /* sum of weights of all flows */ + int max_y; /* max random number in the generation */ + int cur_y, cur_fs; /* used in generation, between 0 and max_y - 1 */ + const char *fs_config; /* flowset config */ + int can_dequeue; + int burst; /* count of packets sent in a burst */ + struct mbuf *tosend; /* packet to send -- also flag to enqueue */ + + struct mbuf *freelist; + + struct mbuf *head, *tail; /* a simple tailq */ + + /* scheduler hooks */ + int (*enq)(struct dn_sch_inst *, struct dn_queue *, + struct mbuf *); + struct mbuf * (*deq)(struct dn_sch_inst *); + /* size of the three fields including sched-specific areas */ + int schk_len; + int q_len; /* size of a queue including sched-fields */ + int si_len; /* size of a sch_inst including sched-fields */ + char *q; /* array of flow queues */ + /* use a char* because size is variable */ + struct dn_fsk *fs; /* array of flowsets */ + struct dn_sch_inst *si; + struct dn_schk *sched; + + /* generator state */ + int state; /* 0 = going up, 1: going down */ + + /* + * We keep lists for each backlog level, and always serve + * the one with shortest backlog. llmask contains a bitmap + * of lists, and ll are the heads of the lists. The last + * entry (BACKLOG) contains all entries considered 'full' + * XXX to optimize things, entry i could contain queues with + * 2^{i-1}+1 .. 2^i entries. + */ +#define BACKLOG 30 + uint32_t llmask; + struct list_head ll[BACKLOG + 10]; +}; + +/* FI2Q and Q2FI converts from flow_id to dn_queue and back. + * We cannot easily use pointer arithmetic because it is variable size. + */ +#define FI2Q(c, i) ((struct dn_queue *)((c)->q + (c)->q_len * (i))) +#define Q2FI(c, q) (((char *)(q) - (c)->q)/(c)->q_len) + +int debug = 0; + +struct dn_parms dn_cfg; + +static void controller(struct cfg_s *c); + +/* release a packet: put the mbuf in the freelist, and the queue in + * the bucket. + */ +int +drop(struct cfg_s *c, struct mbuf *m) +{ + struct dn_queue *q; + int i; + + c->drop++; + q = FI2Q(c, m->flow_id); + i = q->ni.length; // XXX or ffs... + + ND("q %p id %d current length %d", q, m->flow_id, i); + if (i < BACKLOG) { + struct list_head *h = &q->ni.h; + c->llmask &= ~(1<<(i+1)); + c->llmask |= (1<<(i)); + list_del(h); + list_add_tail(h, &c->ll[i]); + } + m->m_nextpkt = c->freelist; + c->freelist = m; + return 0; +} + +/* dequeue returns NON-NULL when a packet is dropped */ +static int +enqueue(struct cfg_s *c, void *_m) +{ + struct mbuf *m = _m; + if (c->enq) + return c->enq(c->si, FI2Q(c, m->flow_id), m); + if (c->head == NULL) + c->head = m; + else + c->tail->m_nextpkt = m; + c->tail = m; + return 0; /* default - success */ +} + +/* dequeue returns NON-NULL when a packet is available */ +static void * +dequeue(struct cfg_s *c) +{ + struct mbuf *m; + if (c->deq) + return c->deq(c->si); + if ((m = c->head)) { + m = c->head; + c->head = m->m_nextpkt; + m->m_nextpkt = NULL; + } + return m; +} + +static int +mainloop(struct cfg_s *c) +{ + int i; + struct mbuf *m; + + for (i=0; i < c->loops; i++) { + /* implement histeresis */ + controller(c); + DX(3, "loop %d enq %d send %p rx %d", + i, c->_enqueue, c->tosend, c->can_dequeue); + if ( (m = c->tosend) ) { + c->_enqueue++; + if (enqueue(c, m)) { + drop(c, m); + ND("loop %d enqueue fail", i ); + } else { + ND("enqueue ok"); + c->pending++; + } + } + if (c->can_dequeue) { + c->dequeue++; + if ((m = dequeue(c))) { + c->pending--; + drop(c, m); + c->drop--; /* compensate */ + } + } + } + DX(1, "mainloop ends %d", i); + return 0; +} + +int +dump(struct cfg_s *c) +{ + int i; + struct dn_queue *q; + + for (i=0; i < c->flows; i++) { + q = FI2Q(c, i); + DX(1, "queue %4d tot %10lld", i, q->ni.tot_bytes); + } + DX(1, "done %d loops\n", c->loops); + return 0; +} + +/* interpret a number in human form */ +static long +getnum(const char *s, char **next, const char *key) +{ + char *end = NULL; + long l; + + if (next) /* default */ + *next = NULL; + if (s && *s) { + DX(3, "token is <%s> %s", s, key ? key : "-"); + l = strtol(s, &end, 0); + } else { + DX(3, "empty string"); + l = -1; + } + if (l < 0) { + DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") ); + return 0; // invalid + } + if (!end || !*end) + return l; + if (*end == 'n') + l = -l; /* multiply by n */ + else if (*end == 'K') + l = l*1000; + else if (*end == 'M') + l = l*1000000; + else if (*end == 'k') + l = l*1024; + else if (*end == 'm') + l = l*1024*1024; + else if (*end == 'w') + ; + else {/* not recognized */ + D("suffix %s for %s, next %p", end, key, next); + end--; + } + end++; + DX(3, "suffix now %s for %s, next %p", end, key, next); + if (next && *end) { + DX(3, "setting next to %s for %s", end, key); + *next = end; + } + return l; +} + +/* + * flowsets are a comma-separated list of + * weight:maxlen:flows + * indicating how many flows are hooked to that fs. + * Both weight and range can be min-max-steps. + * In a first pass we just count the number of flowsets and flows, + * in a second pass we complete the setup. + */ +static void +parse_flowsets(struct cfg_s *c, const char *fs, int pass) +{ + char *s, *cur, *next; + int n_flows = 0, n_fs = 0, wsum = 0; + int i, j; + struct dn_fs *prev = NULL; + + DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets); + if (pass == 0) + c->fs_config = fs; + s = c->fs_config ? strdup(c->fs_config) : NULL; + if (s == NULL) { + if (pass == 0) + D("no fsconfig"); + return; + } + for (next = s; (cur = strsep(&next, ","));) { + char *p = NULL; + int w, w_h, w_steps, wi; + int len, len_h, l_steps, li; + int flows; + + w = getnum(strsep(&cur, ":"), &p, "weight"); + if (w <= 0) + w = 1; + w_h = p ? getnum(p+1, &p, "weight_max") : w; + w_steps = p ? getnum(p+1, &p, "w_steps") : (w_h == w ?1:2); + len = getnum(strsep(&cur, ":"), &p, "len"); + if (len <= 0) + len = 1000; + len_h = p ? getnum(p+1, &p, "len_max") : len; + l_steps = p ? getnum(p+1, &p, "l_steps") : (len_h == len ? 1 : 2); + flows = getnum(strsep(&cur, ":"), NULL, "flows"); + if (flows == 0) + flows = 1; + DX(4, "weight %d..%d (%d) len %d..%d (%d) flows %d", + w, w_h, w_steps, len, len_h, l_steps, flows); + if (w == 0 || w_h < w || len == 0 || len_h < len || + flows == 0) { + DX(4,"wrong parameters %s", fs); + return; + } + n_flows += flows * w_steps * l_steps; + for (i = 0; i < w_steps; i++) { + wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1)); + for (j = 0; j < l_steps; j++, n_fs++) { + struct dn_fs *fs = &c->fs[n_fs].fs; // tentative + int x; + + li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1)); + x = (wi*2048)/li; + DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d", + n_fs, wi, li, x, flows); + if (pass == 0) + continue; + if (c->fs == NULL || c->flowsets <= n_fs) { + D("error in number of flowsets"); + return; + } + wsum += wi * flows; + fs->par[0] = wi; + fs->par[1] = li; + fs->index = n_fs; + fs->n_flows = flows; + fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow; + fs->next_flow = fs->first_flow + fs->n_flows; + fs->y = x * flows; + fs->base_y = (prev == NULL) ? 0 : prev->next_y; + fs->next_y = fs->base_y + fs->y; + prev = fs; + } + } + } + c->max_y = prev ? prev->base_y + prev->y : 0; + c->flows = n_flows; + c->flowsets = n_fs; + c->wsum = wsum; + if (pass == 0) + return; + + /* now link all flows to their parent flowsets */ + DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y); + for (i=0; i < c->flowsets; i++) { + struct dn_fs *fs = &c->fs[i].fs; + DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d", + i, fs->par[0], fs->par[1], + fs->first_flow, fs->next_flow, + fs->base_y, fs->next_y); + for (j = fs->first_flow; j < fs->next_flow; j++) { + struct dn_queue *q = FI2Q(c, j); + q->fs = &c->fs[i]; + } + } +} + +static int +init(struct cfg_s *c) +{ + int i; + int ac = c->ac; + char * const *av = c->av; + + c->si_len = sizeof(struct dn_sch_inst); + c->q_len = sizeof(struct dn_queue); + moduledata_t *mod = NULL; + struct dn_alg *p = NULL; + + c->th_min = 0; + c->th_max = -20;/* 20 packets per flow */ + c->lmin = c->lmax = 1280; /* packet len */ + c->flows = 1; + c->flowsets = 1; + c->name = "null"; + ac--; av++; + while (ac > 1) { + if (!strcmp(*av, "-n")) { + c->loops = getnum(av[1], NULL, av[0]); + } else if (!strcmp(*av, "-d")) { + debug = atoi(av[1]); + } else if (!strcmp(*av, "-alg")) { + extern moduledata_t *_g_dn_fifo; + extern moduledata_t *_g_dn_wf2qp; + extern moduledata_t *_g_dn_rr; + extern moduledata_t *_g_dn_qfq; +#ifdef WITH_KPS + extern moduledata_t *_g_dn_kps; +#endif + if (!strcmp(av[1], "rr")) + mod = _g_dn_rr; + else if (!strcmp(av[1], "wf2qp")) + mod = _g_dn_wf2qp; + else if (!strcmp(av[1], "fifo")) + mod = _g_dn_fifo; + else if (!strcmp(av[1], "qfq")) + mod = _g_dn_qfq; +#ifdef WITH_KPS + else if (!strcmp(av[1], "kps")) + mod = _g_dn_kps; +#endif + else + mod = NULL; + c->name = mod ? mod->name : "NULL"; + DX(3, "using scheduler %s", c->name); + } else if (!strcmp(*av, "-len")) { + c->lmin = getnum(av[1], NULL, av[0]); + c->lmax = c->lmin; + DX(3, "setting max to %d", c->th_max); + } else if (!strcmp(*av, "-burst")) { + c->maxburst = getnum(av[1], NULL, av[0]); + DX(3, "setting max to %d", c->th_max); + } else if (!strcmp(*av, "-qmax")) { + c->th_max = getnum(av[1], NULL, av[0]); + DX(3, "setting max to %d", c->th_max); + } else if (!strcmp(*av, "-qmin")) { + c->th_min = getnum(av[1], NULL, av[0]); + DX(3, "setting min to %d", c->th_min); + } else if (!strcmp(*av, "-flows")) { + c->flows = getnum(av[1], NULL, av[0]); + DX(3, "setting flows to %d", c->flows); + } else if (!strcmp(*av, "-flowsets")) { + parse_flowsets(c, av[1], 0); + DX(3, "setting flowsets to %d", c->flowsets); + } else { + D("option %s not recognised, ignore", *av); + } + ac -= 2; av += 2; + } + if (c->maxburst <= 0) + c->maxburst = 1; + if (c->loops <= 0) + c->loops = 1; + if (c->flows <= 0) + c->flows = 1; + if (c->flowsets <= 0) + c->flowsets = 1; + if (c->lmin <= 0) + c->lmin = 1; + if (c->lmax <= 0) + c->lmax = 1; + /* multiply by N */ + if (c->th_min < 0) + c->th_min = c->flows * -c->th_min; + if (c->th_max < 0) + c->th_max = c->flows * -c->th_max; + if (c->th_max <= c->th_min) + c->th_max = c->th_min + 1; + if (mod) { + p = mod->p; + DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p); + DX(3, "modname %s ty %d", p->name, p->type); + c->enq = p->enqueue; + c->deq = p->dequeue; + c->si_len += p->si_datalen; + c->q_len += p->q_datalen; + c->schk_len += p->schk_datalen; + } + /* allocate queues, flowsets and one scheduler */ + c->q = calloc(c->flows, c->q_len); + c->fs = calloc(c->flowsets, sizeof(struct dn_fsk)); + c->si = calloc(1, c->si_len); + c->sched = calloc(c->flows, c->schk_len); + if (c->q == NULL || c->fs == NULL) { + D("error allocating memory for flows"); + exit(1); + } + c->si->sched = c->sched; + if (p) { + if (p->config) + p->config(c->sched); + if (p->new_sched) + p->new_sched(c->si); + } + /* parse_flowsets links queues to their flowsets */ + parse_flowsets(c, av[1], 1); + /* complete the work calling new_fsk */ + for (i = 0; i < c->flowsets; i++) { + if (c->fs[i].fs.par[1] == 0) + c->fs[i].fs.par[1] = 1000; /* default pkt len */ + c->fs[i].sched = c->sched; + if (p && p->new_fsk) + p->new_fsk(&c->fs[i]); + } + + /* initialize the lists for the generator, and put + * all flows in the list for backlog = 0 + */ + for (i=0; i <= BACKLOG+5; i++) + INIT_LIST_HEAD(&c->ll[i]); + + for (i = 0; i < c->flows; i++) { + struct dn_queue *q = FI2Q(c, i); + if (q->fs == NULL) + q->fs = &c->fs[0]; /* XXX */ + q->_si = c->si; + if (p && p->new_queue) + p->new_queue(q); + INIT_LIST_HEAD(&q->ni.h); + list_add_tail(&q->ni.h, &c->ll[0]); + } + c->llmask = 1; + return 0; +} + + +int +main(int ac, char *av[]) +{ + struct cfg_s c; + struct timeval end; + double ll; + int i; + char msg[40]; + + bzero(&c, sizeof(c)); + c.ac = ac; + c.av = av; + init(&c); + gettimeofday(&c.time, NULL); + mainloop(&c); + gettimeofday(&end, NULL); + end.tv_sec -= c.time.tv_sec; + end.tv_usec -= c.time.tv_usec; + if (end.tv_usec < 0) { + end.tv_usec += 1000000; + end.tv_sec--; + } + c.time = end; + ll = end.tv_sec*1000000 + end.tv_usec; + ll *= 1000; /* convert to nanoseconds */ + ll /= c._enqueue; + sprintf(msg, "1::%d", c.flows); + D("%-8s n %d %d time %d.%06d %8.3f qlen %d %d flows %s drops %d", + c.name, c._enqueue, c.loops, + (int)c.time.tv_sec, (int)c.time.tv_usec, ll, + c.th_min, c.th_max, + c.fs_config ? c.fs_config : msg, c.drop); + dump(&c); + DX(1, "done ac %d av %p", ac, av); + for (i=0; i < ac; i++) + DX(1, "arg %d %s", i, av[i]); + return 0; +} + +/* + * The controller decides whether in this iteration we should send + * (the packet is in c->tosend) and/or receive (flag c->can_dequeue) + */ +static void +controller(struct cfg_s *c) +{ + struct mbuf *m; + struct dn_fs *fs; + int flow_id; + + /* histeresis between max and min */ + if (c->state == 0 && c->pending >= c->th_max) + c->state = 1; + else if (c->state == 1 && c->pending <= c->th_min) + c->state = 0; + ND(1, "state %d pending %2d", c->state, c->pending); + c->can_dequeue = c->state; + c->tosend = NULL; + if (c->state) + return; + + if (1) { + int i; + struct dn_queue *q; + struct list_head *h; + + i = ffs(c->llmask) - 1; + if (i < 0) { + DX(2, "no candidate"); + c->can_dequeue = 1; + return; + } + h = &c->ll[i]; + ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next); + q = list_first_entry(h, struct dn_queue, ni.h); + list_del(&q->ni.h); + flow_id = Q2FI(c, q); + DX(2, "extracted flow %p %d backlog %d", q, flow_id, i); + if (list_empty(h)) { + ND(2, "backlog %d empty", i); + c->llmask &= ~(1<<i); + } + ND(1, "before %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); + list_add_tail(&q->ni.h, h+1); + ND(1, " after %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); + if (i < BACKLOG) { + ND(2, "backlog %d full", i+1); + c->llmask |= 1<<(1+i); + } + fs = &q->fs->fs; + c->cur_fs = q->fs - c->fs; + fs->cur = flow_id; + } else { + /* XXX this does not work ? */ + /* now decide whom to send the packet, and the length */ + /* lookup in the flow table */ + if (c->cur_y >= c->max_y) { /* handle wraparound */ + c->cur_y = 0; + c->cur_fs = 0; + } + fs = &c->fs[c->cur_fs].fs; + flow_id = fs->cur++; + if (fs->cur >= fs->next_flow) + fs->cur = fs->first_flow; + c->cur_y++; + if (c->cur_y >= fs->next_y) + c->cur_fs++; + } + + /* construct a packet */ + if (c->freelist) { + m = c->tosend = c->freelist; + c->freelist = c->freelist->m_nextpkt; + } else { + m = c->tosend = calloc(1, sizeof(struct mbuf)); + } + if (m == NULL) + return; + + m->cfg = c; + m->m_nextpkt = NULL; + m->m_pkthdr.len = fs->par[1]; // XXX maxlen + m->flow_id = flow_id; + + ND(2,"y %6d flow %5d fs %3d weight %4d len %4d", + c->cur_y, m->flow_id, c->cur_fs, + fs->par[0], m->m_pkthdr.len); + +} + +/* +Packet allocation: +to achieve a distribution that matches weights, for each X=w/lmax class +we should generate a number of packets proportional to Y = X times the number +of flows in the class. +So we construct an array with the cumulative distribution of Y's, +and use it to identify the flow via inverse mapping (if the Y's are +not too many we can use an array for the lookup). In practice, +each flow will have X entries [virtually] pointing to it. + +*/ diff --git a/sys/netinet/ipfw/test/mylist.h b/sys/netinet/ipfw/test/mylist.h new file mode 100644 index 0000000..ebc7d11 --- /dev/null +++ b/sys/netinet/ipfw/test/mylist.h @@ -0,0 +1,49 @@ +/* + * $FreeBSD$ + * + * linux-like bidirectional lists + */ + +#ifndef _MYLIST_H +#define _MYLIST_H +struct list_head { + struct list_head *prev, *next; +}; + +#define INIT_LIST_HEAD(l) do { (l)->prev = (l)->next = (l); } while (0) +#define list_empty(l) ( (l)->next == l ) +static inline void +__list_add(struct list_head *new, struct list_head *prev, + struct list_head *next) +{ + next->prev = new; + new->next = next; + new->prev = prev; + prev->next = new; +} + +static inline void +list_add_tail(struct list_head *new, struct list_head *head) +{ + __list_add(new, head->prev, head); +} + +#define list_first_entry(pL, ty, member) \ + (ty *)((char *)((pL)->next) - offsetof(ty, member)) + +static inline void +__list_del(struct list_head *prev, struct list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +static inline void +list_del(struct list_head *entry) +{ + ND("called on %p", entry); + __list_del(entry->prev, entry->next); + entry->next = entry->prev = NULL; +} + +#endif /* _MYLIST_H */ diff --git a/sys/netinet/ipfw/test/test_dn_heap.c b/sys/netinet/ipfw/test/test_dn_heap.c new file mode 100644 index 0000000..d460cf2 --- /dev/null +++ b/sys/netinet/ipfw/test/test_dn_heap.c @@ -0,0 +1,162 @@ +/*- + * Copyright (c) 1998-2002,2010 Luigi Rizzo, Universita` di Pisa + * All rights reserved + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +/* + * Userland code for testing binary heaps and hash tables + * + * $FreeBSD$ + */ + +#include <sys/cdefs.h> +#include <sys/param.h> + +#include <stdio.h> +#include <strings.h> +#include <stdlib.h> + +#include "dn_heap.h" +#define log(x, arg...) fprintf(stderr, ## arg) +#define panic(x...) fprintf(stderr, ## x), exit(1) + +#include <string.h> + +struct x { + struct x *ht_link; + char buf[0]; +}; + +uint32_t hf(uintptr_t key, int flags, void *arg) +{ + return (flags & DNHT_KEY_IS_OBJ) ? + ((struct x *)key)->buf[0] : *(char *)key; +} + +int matchf(void *obj, uintptr_t key, int flags, void *arg) +{ + char *s = (flags & DNHT_KEY_IS_OBJ) ? + ((struct x *)key)->buf : (char *)key; + return (strcmp(((struct x *)obj)->buf, s) == 0); +} + +void *newfn(uintptr_t key, int flags, void *arg) +{ + char *s = (char *)key; + struct x *p = malloc(sizeof(*p) + 1 + strlen(s)); + if (p) + strcpy(p->buf, s); + return p; +} + +char *strings[] = { + "undici", "unico", "doppio", "devoto", + "uno", "due", "tre", "quattro", "cinque", "sei", + "uno", "due", "tre", "quattro", "cinque", "sei", + NULL, +}; + +int doprint(void *_x, void *arg) +{ + struct x *x = _x; + printf("found element <%s>\n", x->buf); + return (int)arg; +} + +static void +test_hash() +{ + char **p; + struct dn_ht *h; + uintptr_t x = 0; + uintptr_t x1 = 0; + + /* first, find and allocate */ + h = dn_ht_init(NULL, 10, 0, hf, matchf, newfn); + + for (p = strings; *p; p++) { + dn_ht_find(h, (uintptr_t)*p, DNHT_INSERT, NULL); + } + dn_ht_scan(h, doprint, 0); + printf("/* second -- find without allocate */\n"); + h = dn_ht_init(NULL, 10, 0, hf, matchf, NULL); + for (p = strings; *p; p++) { + void **y = newfn((uintptr_t)*p, 0, NULL); + if (x == 0) + x = (uintptr_t)y; + else { + if (x1 == 0) + x1 = (uintptr_t)*p; + } + dn_ht_find(h, (uintptr_t)y, DNHT_INSERT | DNHT_KEY_IS_OBJ, NULL); + } + dn_ht_scan(h, doprint, 0); + printf("remove %p gives %p\n", (void *)x, + dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); + printf("remove %p gives %p\n", (void *)x, + dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); + printf("remove %p gives %p\n", (void *)x, + dn_ht_find(h, x1, DNHT_REMOVE, NULL)); + printf("remove %p gives %p\n", (void *)x, + dn_ht_find(h, x1, DNHT_REMOVE, NULL)); + dn_ht_scan(h, doprint, 0); +} + +int +main(int argc, char *argv[]) +{ + struct dn_heap h; + int i, n, n2, n3; + + test_hash(); + return 0; + + /* n = elements, n2 = cycles */ + n = (argc > 1) ? atoi(argv[1]) : 0; + if (n <= 0 || n > 1000000) + n = 100; + n2 = (argc > 2) ? atoi(argv[2]) : 0; + if (n2 <= 0) + n = 1000000; + n3 = (argc > 3) ? atoi(argv[3]) : 0; + bzero(&h, sizeof(h)); + heap_init(&h, n, -1); + while (n2-- > 0) { + uint64_t prevk = 0; + for (i=0; i < n; i++) + heap_insert(&h, n3 ? n-i: random(), (void *)(100+i)); + + for (i=0; h.elements > 0; i++) { + uint64_t k = h.p[0].key; + if (k < prevk) + panic("wrong sequence\n"); + prevk = k; + if (0) + printf("%d key %llu, val %p\n", + i, h.p[0].key, h.p[0].object); + heap_extract(&h, NULL); + } + } + return 0; +} diff --git a/sys/netinet/ipfw/test/test_dn_sched.c b/sys/netinet/ipfw/test/test_dn_sched.c new file mode 100644 index 0000000..667c42e --- /dev/null +++ b/sys/netinet/ipfw/test/test_dn_sched.c @@ -0,0 +1,76 @@ +/* + * $FreeBSD$ + * + * library functions for userland testing of dummynet schedulers + */ + +#include "dn_test.h" + +void +m_freem(struct mbuf *m) +{ + printf("free %p\n", m); +} + +int +dn_sched_modevent(module_t mod, int cmd, void *arg) +{ + return 0; +} + +void +dn_free_pkts(struct mbuf *m) +{ + struct mbuf *x; + while ( (x = m) ) { + m = m->m_nextpkt; + m_freem(x); + } +} + +int +dn_delete_queue(void *_q, void *do_free) +{ + struct dn_queue *q = _q; + if (q->mq.head) + dn_free_pkts(q->mq.head); + free(q); + return 0; +} + +/* + * This is a simplified function for testing purposes, which does + * not implement statistics or random loss. + * Enqueue a packet in q, subject to space and queue management policy + * (whose parameters are in q->fs). + * Update stats for the queue and the scheduler. + * Return 0 on success, 1 on drop. The packet is consumed anyways. + */ +int +dn_enqueue(struct dn_queue *q, struct mbuf* m, int drop) +{ + if (drop) + goto drop; + if (q->ni.length >= 200) + goto drop; + mq_append(&q->mq, m); + q->ni.length++; + q->ni.tot_bytes += m->m_pkthdr.len; + return 0; + +drop: + q->ni.drops++; + return 1; +} + +int +ipdn_bound_var(int *v, int dflt, int lo, int hi, const char *msg) +{ + if (*v < lo) { + *v = dflt; + } else if (*v > hi) { + *v = hi; + } + return *v; +} + |
