diff options
Diffstat (limited to 'sys/netinet/ipfw/test')
| -rw-r--r-- | sys/netinet/ipfw/test/Makefile | 51 | ||||
| -rw-r--r-- | sys/netinet/ipfw/test/dn_test.h | 175 | ||||
| -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 | 89 |
6 files changed, 0 insertions, 1162 deletions
diff --git a/sys/netinet/ipfw/test/Makefile b/sys/netinet/ipfw/test/Makefile deleted file mode 100644 index c556a4b..0000000 --- a/sys/netinet/ipfw/test/Makefile +++ /dev/null @@ -1,51 +0,0 @@ -# -# $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_prio.c -SCHED_SRCS += dn_sched_qfq.c -SCHED_SRCS += dn_sched_rr.c -SCHED_SRCS += dn_sched_wf2q.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 deleted file mode 100644 index 4e079bc..0000000 --- a/sys/netinet/ipfw/test/dn_test.h +++ /dev/null @@ -1,175 +0,0 @@ -/* - * $FreeBSD$ - * - * userspace compatibility code for dummynet schedulers - */ - -#ifndef _DN_TEST_H -#define _DN_TEST_H - -#ifdef __cplusplus -extern "C" { -#endif - -#include <inttypes.h> -#include <stdio.h> -#include <stdlib.h> -#include <strings.h> /* bzero, ffs, ... */ -#include <string.h> /* strcmp */ -#include <errno.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) - - -#ifndef offsetof -#define offsetof(t,m) (int)((&((t *)0L)->m)) -#endif - -#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 - -#ifndef __FreeBSD__ -int fls(int); -#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; -} - -#ifdef __cplusplus -} -#endif - -#endif /* _DN_TEST_H */ diff --git a/sys/netinet/ipfw/test/main.c b/sys/netinet/ipfw/test/main.c deleted file mode 100644 index be9fdf5..0000000 --- a/sys/netinet/ipfw/test/main.c +++ /dev/null @@ -1,636 +0,0 @@ -/* - * $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 deleted file mode 100644 index 6247f32..0000000 --- a/sys/netinet/ipfw/test/mylist.h +++ /dev/null @@ -1,49 +0,0 @@ -/* - * $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 *o, struct list_head *prev, - struct list_head *next) -{ - next->prev = o; - o->next = next; - o->prev = prev; - prev->next = o; -} - -static inline void -list_add_tail(struct list_head *o, struct list_head *head) -{ - __list_add(o, 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 deleted file mode 100644 index d460cf2..0000000 --- a/sys/netinet/ipfw/test/test_dn_heap.c +++ /dev/null @@ -1,162 +0,0 @@ -/*- - * 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 deleted file mode 100644 index ee46c95..0000000 --- a/sys/netinet/ipfw/test/test_dn_sched.c +++ /dev/null @@ -1,89 +0,0 @@ -/* - * $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; -} - -#ifndef __FreeBSD__ -int -fls(int mask) -{ - int bit; - - if (mask == 0) - return (0); - for (bit = 1; mask != 1; bit++) - mask = (unsigned int)mask >> 1; - return (bit); -} -#endif |
