1204591Sluigi/*
2204591Sluigi * $FreeBSD: releng/11.0/sys/netpfil/ipfw/test/main.c 294882 2016-01-27 02:22:31Z luigi $
3204591Sluigi *
4204591Sluigi * Testing program for schedulers
5204591Sluigi *
6204591Sluigi * The framework include a simple controller which, at each
7204591Sluigi * iteration, decides whether we can enqueue and/or dequeue.
8204591Sluigi * Then the mainloop runs the required number of tests,
9204591Sluigi * keeping track of statistics.
10204591Sluigi */
11204591Sluigi
12294882Sluigi// #define USE_BURST	// what is this for ?
13294882Sluigi
14204591Sluigi#include "dn_test.h"
15204591Sluigi
16204591Sluigistruct cfg_s {
17204591Sluigi	int ac;
18204591Sluigi	char * const *av;
19204591Sluigi
20204591Sluigi	const char *name;
21204591Sluigi	int loops;
22204591Sluigi	struct timeval time;
23204591Sluigi
24204591Sluigi	/* running counters */
25204591Sluigi	uint32_t	_enqueue;
26204591Sluigi	uint32_t	drop;
27204591Sluigi	uint32_t	pending;
28204591Sluigi	uint32_t	dequeue;
29204591Sluigi
30204591Sluigi	/* generator parameters */
31294882Sluigi	int32_t th_min, th_max;	/* thresholds for hysteresis; negative means per flow */
32294882Sluigi#ifdef USE_BURST
33204591Sluigi	int maxburst;
34294882Sluigi#endif /* USE_BURST */
35204591Sluigi	int lmin, lmax;	/* packet len */
36204591Sluigi	int flows;	/* number of flows */
37204591Sluigi	int flowsets;	/* number of flowsets */
38204591Sluigi	int wsum;	/* sum of weights of all flows */
39294882Sluigi#ifdef USE_CUR
40204591Sluigi	int max_y;	/* max random number in the generation */
41294882Sluigi	int cur_y
42294882Sluigi	int cur_fs;	/* used in generation, between 0 and max_y - 1 */
43294882Sluigi#endif /* USE_CUR */
44204591Sluigi	const char *fs_config; /* flowset config */
45204591Sluigi	int can_dequeue;
46204591Sluigi	int burst;	/* count of packets sent in a burst */
47204591Sluigi	struct mbuf *tosend;	/* packet to send -- also flag to enqueue */
48204591Sluigi
49204591Sluigi	struct mbuf *freelist;
50204591Sluigi
51204591Sluigi	struct mbuf *head, *tail;	/* a simple tailq */
52204591Sluigi
53204591Sluigi	/* scheduler hooks */
54204591Sluigi	int (*enq)(struct dn_sch_inst *, struct dn_queue *,
55204591Sluigi		struct mbuf *);
56204591Sluigi	struct mbuf * (*deq)(struct dn_sch_inst *);
57204591Sluigi	/* size of the three fields including sched-specific areas */
58294882Sluigi	uint32_t schk_len;
59294882Sluigi	uint32_t q_len; /* size of a queue including sched-fields */
60294882Sluigi	uint32_t si_len; /* size of a sch_inst including sched-fields */
61204591Sluigi	char *q;	/* array of flow queues */
62204591Sluigi		/* use a char* because size is variable */
63294882Sluigi	/*
64294882Sluigi	 * The scheduler template (one) followd by schk_datalen bytes
65294882Sluigi	 * for scheduler-specific parameters, total size is schk_len
66294882Sluigi	 */
67294882Sluigi	struct dn_schk *sched;
68294882Sluigi	/*
69294882Sluigi	 * one scheduler instance, followed by si_datalen bytes
70294882Sluigi	 * for scheduler specific parameters of this instance,
71294882Sluigi	 * total size is si_len. si->sched points to sched
72294882Sluigi	 */
73294882Sluigi	struct dn_sch_inst *si;
74204591Sluigi	struct dn_fsk *fs;	/* array of flowsets */
75204591Sluigi
76204591Sluigi	/* generator state */
77294882Sluigi	int state;	/* 0 = going up (enqueue), 1: going down (dequeue) */
78204591Sluigi
79204591Sluigi	/*
80204591Sluigi	 * We keep lists for each backlog level, and always serve
81204591Sluigi	 * the one with shortest backlog. llmask contains a bitmap
82204591Sluigi	 * of lists, and ll are the heads of the lists. The last
83204591Sluigi	 * entry (BACKLOG) contains all entries considered 'full'
84204591Sluigi	 * XXX to optimize things, entry i could contain queues with
85204591Sluigi	 * 2^{i-1}+1 .. 2^i entries.
86204591Sluigi	 */
87294882Sluigi#define BACKLOG	30 /* this many backlogged classes, we only need BACKLOG+1 */
88294882Sluigi	uint64_t	llmask;
89204591Sluigi	struct list_head ll[BACKLOG + 10];
90285360Sluigi
91285360Sluigi	double *q_wfi;	/* (byte) Worst-case Fair Index of the flows  */
92285360Sluigi	double wfi;	/* (byte) Worst-case Fair Index of the system */
93204591Sluigi};
94204591Sluigi
95294882Sluigi/* FI2Q and Q2FI converts from flow_id (i.e. queue index)
96294882Sluigi * to dn_queue and back. We cannot simply use pointer arithmetic
97294882Sluigi * because the queu has variable size, q_len
98294882Sluigi */
99204591Sluigi#define FI2Q(c, i)	((struct dn_queue *)((c)->q + (c)->q_len * (i)))
100204591Sluigi#define Q2FI(c, q)	(((char *)(q) - (c)->q)/(c)->q_len)
101204591Sluigi
102204591Sluigiint debug = 0;
103204591Sluigi
104204591Sluigistruct dn_parms dn_cfg;
105204591Sluigi
106204591Sluigistatic void controller(struct cfg_s *c);
107204591Sluigi
108294882Sluigi/* release a packet for a given flow_id.
109294882Sluigi * Put the mbuf in the freelist, and in case move the
110294882Sluigi * flow to the end of the bucket.
111204591Sluigi */
112294882Sluigistatic int
113204591Sluigidrop(struct cfg_s *c, struct mbuf *m)
114204591Sluigi{
115204591Sluigi	struct dn_queue *q;
116204591Sluigi	int i;
117204591Sluigi
118204591Sluigi	c->drop++;
119204591Sluigi	q = FI2Q(c, m->flow_id);
120204591Sluigi	i = q->ni.length; // XXX or ffs...
121204591Sluigi
122204591Sluigi	ND("q %p id %d current length %d", q, m->flow_id, i);
123204591Sluigi	if (i < BACKLOG) {
124204591Sluigi		struct list_head *h = &q->ni.h;
125204591Sluigi		c->llmask &= ~(1<<(i+1));
126204591Sluigi		c->llmask |= (1<<(i));
127204591Sluigi		list_del(h);
128204591Sluigi		list_add_tail(h, &c->ll[i]);
129204591Sluigi	}
130204591Sluigi	m->m_nextpkt = c->freelist;
131204591Sluigi	c->freelist = m;
132204591Sluigi	return 0;
133204591Sluigi}
134204591Sluigi
135294882Sluigi
136294882Sluigi/*
137294882Sluigi * dn_sch_inst does not have a queue, for the RR we
138294882Sluigi * allocate a mq right after si
139294882Sluigi */
140204591Sluigistatic int
141294882Sluigidefault_enqueue(struct dn_sch_inst *si, struct dn_queue *q, struct mbuf *m)
142204591Sluigi{
143294882Sluigi	struct mq *mq = (struct mq *)si;
144294882Sluigi
145294882Sluigi	(void)q;
146294882Sluigi	/* this is the default function if no scheduler is provided */
147294882Sluigi	if (mq->head == NULL)
148294882Sluigi		mq->head = m;
149204591Sluigi	else
150294882Sluigi		mq->tail->m_nextpkt = m;
151294882Sluigi	mq->tail = m;
152204591Sluigi	return 0; /* default - success */
153204591Sluigi}
154204591Sluigi
155294882Sluigi
156294882Sluigistatic struct mbuf *
157294882Sluigidefault_dequeue(struct dn_sch_inst *si)
158204591Sluigi{
159294882Sluigi	struct mq *mq = (struct mq *)si;
160204591Sluigi	struct mbuf *m;
161294882Sluigi	/* this is the default function if no scheduler is provided */
162294882Sluigi	if ((m = mq->head)) {
163294882Sluigi		m = mq->head;
164294882Sluigi		mq->head = m->m_nextpkt;
165204591Sluigi		m->m_nextpkt = NULL;
166204591Sluigi	}
167204591Sluigi	return m;
168204591Sluigi}
169204591Sluigi
170285360Sluigistatic void
171285360Sluigignet_stats_enq(struct cfg_s *c, struct mbuf *mb)
172285360Sluigi{
173285360Sluigi	struct dn_sch_inst *si = c->si;
174285360Sluigi	struct dn_queue *_q = FI2Q(c, mb->flow_id);
175285360Sluigi
176285360Sluigi	if (_q->ni.length == 1) {
177285360Sluigi		_q->ni.bytes = 0;
178285360Sluigi		_q->ni.sch_bytes = si->ni.bytes;
179285360Sluigi	}
180285360Sluigi}
181285360Sluigi
182285360Sluigistatic void
183285360Sluigignet_stats_deq(struct cfg_s *c, struct mbuf *mb)
184285360Sluigi{
185285360Sluigi	struct dn_sch_inst *si = c->si;
186285360Sluigi	struct dn_queue *_q = FI2Q(c, mb->flow_id);
187285360Sluigi	int len = mb->m_pkthdr.len;
188285360Sluigi
189285360Sluigi	_q->ni.bytes += len;
190285360Sluigi	si->ni.bytes += len;
191285360Sluigi
192285360Sluigi	if (_q->ni.length == 0) {
193285360Sluigi		double bytes = (double)_q->ni.bytes;
194285360Sluigi		double sch_bytes = (double)si->ni.bytes - _q->ni.sch_bytes;
195285360Sluigi		double weight = (double)_q->fs->fs.par[0] / c->wsum;
196285360Sluigi		double wfi = sch_bytes * weight - bytes;
197285360Sluigi
198285360Sluigi		if (c->q_wfi[mb->flow_id] < wfi)
199285360Sluigi			c->q_wfi[mb->flow_id] = wfi;
200285360Sluigi	}
201285360Sluigi}
202285360Sluigi
203204591Sluigistatic int
204204591Sluigimainloop(struct cfg_s *c)
205204591Sluigi{
206204591Sluigi	int i;
207204591Sluigi	struct mbuf *m;
208204591Sluigi
209204591Sluigi	for (i=0; i < c->loops; i++) {
210204591Sluigi		/* implement histeresis */
211204591Sluigi		controller(c);
212204591Sluigi		DX(3, "loop %d enq %d send %p rx %d",
213204591Sluigi			i, c->_enqueue, c->tosend, c->can_dequeue);
214204591Sluigi		if ( (m = c->tosend) ) {
215294882Sluigi			int ret;
216294882Sluigi			struct dn_queue *q = FI2Q(c, m->flow_id);
217204591Sluigi			c->_enqueue++;
218294882Sluigi			ret = c->enq(c->si, q, m);
219294882Sluigi			if (ret) {
220204591Sluigi				drop(c, m);
221294882Sluigi				D("loop %d enqueue fail", i );
222294882Sluigi				/*
223294882Sluigi				 * XXX do not insist; rather, try dequeue
224294882Sluigi				 */
225294882Sluigi				goto do_dequeue;
226204591Sluigi			} else {
227204591Sluigi				ND("enqueue ok");
228204591Sluigi				c->pending++;
229285360Sluigi				gnet_stats_enq(c, m);
230204591Sluigi			}
231294882Sluigi		} else if (c->can_dequeue) {
232294882Sluigido_dequeue:
233204591Sluigi			c->dequeue++;
234294882Sluigi			m = c->deq(c->si);
235294882Sluigi			if (m) {
236204591Sluigi				c->pending--;
237204591Sluigi				drop(c, m);
238204591Sluigi				c->drop--;	/* compensate */
239285360Sluigi				gnet_stats_deq(c, m);
240294882Sluigi			} else {
241294882Sluigi				D("--- ouch, cannot operate on iteration %d, pending %d", i, c->pending);
242294882Sluigi				break;
243204591Sluigi			}
244204591Sluigi		}
245204591Sluigi	}
246204591Sluigi	DX(1, "mainloop ends %d", i);
247204591Sluigi	return 0;
248204591Sluigi}
249204591Sluigi
250204591Sluigiint
251204591Sluigidump(struct cfg_s *c)
252204591Sluigi{
253204591Sluigi	int i;
254204591Sluigi
255204591Sluigi	for (i=0; i < c->flows; i++) {
256294882Sluigi		//struct dn_queue *q = FI2Q(c, i);
257294882Sluigi		ND(1, "queue %4d tot %10llu", i,
258285360Sluigi		    (unsigned long long)q->ni.tot_bytes);
259204591Sluigi	}
260204591Sluigi	DX(1, "done %d loops\n", c->loops);
261204591Sluigi	return 0;
262204591Sluigi}
263204591Sluigi
264204591Sluigi/* interpret a number in human form */
265204591Sluigistatic long
266204591Sluigigetnum(const char *s, char **next, const char *key)
267204591Sluigi{
268204591Sluigi	char *end = NULL;
269204591Sluigi	long l;
270204591Sluigi
271204591Sluigi	if (next)	/* default */
272204591Sluigi		*next = NULL;
273204591Sluigi	if (s && *s) {
274204591Sluigi		DX(3, "token is <%s> %s", s, key ? key : "-");
275204591Sluigi		l = strtol(s, &end, 0);
276204591Sluigi	} else {
277204591Sluigi		DX(3, "empty string");
278204591Sluigi		l = -1;
279204591Sluigi	}
280204591Sluigi	if (l < 0) {
281204591Sluigi		DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") );
282204591Sluigi		return 0;	// invalid
283204591Sluigi	}
284204591Sluigi	if (!end || !*end)
285204591Sluigi		return l;
286204591Sluigi	if (*end == 'n')
287204591Sluigi		l = -l;	/* multiply by n */
288204591Sluigi	else if (*end == 'K')
289204591Sluigi		l = l*1000;
290204591Sluigi	else if (*end == 'M')
291204591Sluigi		l = l*1000000;
292204591Sluigi	else if (*end == 'k')
293204591Sluigi		l = l*1024;
294204591Sluigi	else if (*end == 'm')
295204591Sluigi		l = l*1024*1024;
296204591Sluigi	else if (*end == 'w')
297204591Sluigi		;
298204591Sluigi	else {/* not recognized */
299204591Sluigi		D("suffix %s for %s, next %p", end, key, next);
300204591Sluigi		end--;
301204591Sluigi	}
302204591Sluigi	end++;
303204591Sluigi	DX(3, "suffix now %s for %s, next %p", end, key, next);
304204591Sluigi	if (next && *end) {
305204591Sluigi		DX(3, "setting next to %s for %s", end, key);
306204591Sluigi		*next = end;
307204591Sluigi	}
308204591Sluigi	return l;
309204591Sluigi}
310204591Sluigi
311204591Sluigi/*
312204591Sluigi * flowsets are a comma-separated list of
313204591Sluigi *     weight:maxlen:flows
314204591Sluigi * indicating how many flows are hooked to that fs.
315204591Sluigi * Both weight and range can be min-max-steps.
316294882Sluigi * The first pass (fs != NULL) justs count the number of flowsets and flows,
317294882Sluigi * the second pass (fs == NULL) we complete the setup.
318204591Sluigi */
319204591Sluigistatic void
320294882Sluigiparse_flowsets(struct cfg_s *c, const char *fs)
321204591Sluigi{
322204591Sluigi	char *s, *cur, *next;
323204591Sluigi	int n_flows = 0, n_fs = 0, wsum = 0;
324204591Sluigi	int i, j;
325204591Sluigi	struct dn_fs *prev = NULL;
326294882Sluigi	int pass = (fs == NULL);
327204591Sluigi
328204591Sluigi	DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets);
329294882Sluigi	if (fs != NULL) { /* first pass */
330294882Sluigi		if (c->fs_config)
331294882Sluigi			D("warning, overwriting fs %s with %s",
332294882Sluigi				c->fs_config, fs);
333204591Sluigi		c->fs_config = fs;
334294882Sluigi	}
335204591Sluigi	s = c->fs_config ? strdup(c->fs_config) : NULL;
336204591Sluigi	if (s == NULL) {
337204591Sluigi		if (pass == 0)
338204591Sluigi			D("no fsconfig");
339204591Sluigi		return;
340204591Sluigi	}
341204591Sluigi	for (next = s; (cur = strsep(&next, ","));) {
342204591Sluigi		char *p = NULL;
343204591Sluigi		int w, w_h, w_steps, wi;
344204591Sluigi		int len, len_h, l_steps, li;
345204591Sluigi		int flows;
346204591Sluigi
347204591Sluigi		w = getnum(strsep(&cur, ":"), &p, "weight");
348204591Sluigi		if (w <= 0)
349204591Sluigi			w = 1;
350204591Sluigi		w_h = p ? getnum(p+1, &p, "weight_max") : w;
351204591Sluigi		w_steps = p ? getnum(p+1, &p, "w_steps") : (w_h == w ?1:2);
352204591Sluigi		len = getnum(strsep(&cur, ":"), &p, "len");
353204591Sluigi		if (len <= 0)
354204591Sluigi			len = 1000;
355204591Sluigi		len_h = p ? getnum(p+1, &p, "len_max") : len;
356204591Sluigi		l_steps = p ? getnum(p+1, &p, "l_steps") : (len_h == len ? 1 : 2);
357204591Sluigi		flows = getnum(strsep(&cur, ":"), NULL, "flows");
358204591Sluigi		if (flows == 0)
359204591Sluigi			flows = 1;
360204591Sluigi		DX(4, "weight %d..%d (%d) len %d..%d (%d) flows %d",
361204591Sluigi			w, w_h, w_steps, len, len_h, l_steps, flows);
362204591Sluigi		if (w == 0 || w_h < w || len == 0 || len_h < len ||
363204591Sluigi				flows == 0) {
364294882Sluigi			DX(4,"wrong parameters %s", s);
365204591Sluigi			return;
366204591Sluigi		}
367204591Sluigi		n_flows += flows * w_steps * l_steps;
368204591Sluigi		for (i = 0; i < w_steps; i++) {
369204591Sluigi			wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1));
370204591Sluigi			for (j = 0; j < l_steps; j++, n_fs++) {
371204591Sluigi				struct dn_fs *fs = &c->fs[n_fs].fs; // tentative
372204591Sluigi				int x;
373204591Sluigi
374204591Sluigi				li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1));
375204591Sluigi				x = (wi*2048)/li;
376204591Sluigi				DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d",
377204591Sluigi					n_fs, wi, li, x, flows);
378204591Sluigi				if (pass == 0)
379204591Sluigi					continue;
380204591Sluigi				if (c->fs == NULL || c->flowsets <= n_fs) {
381204591Sluigi					D("error in number of flowsets");
382204591Sluigi					return;
383204591Sluigi				}
384204591Sluigi				wsum += wi * flows;
385204591Sluigi				fs->par[0] = wi;
386204591Sluigi				fs->par[1] = li;
387204591Sluigi				fs->index = n_fs;
388204591Sluigi				fs->n_flows = flows;
389204591Sluigi				fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow;
390204591Sluigi				fs->next_flow = fs->first_flow + fs->n_flows;
391204591Sluigi				fs->y = x * flows;
392204591Sluigi				fs->base_y = (prev == NULL) ? 0 : prev->next_y;
393204591Sluigi				fs->next_y = fs->base_y + fs->y;
394204591Sluigi				prev = fs;
395204591Sluigi			}
396204591Sluigi		}
397204591Sluigi	}
398204591Sluigi	c->flows = n_flows;
399204591Sluigi	c->flowsets = n_fs;
400204591Sluigi	c->wsum = wsum;
401204591Sluigi	if (pass == 0)
402204591Sluigi		return;
403204591Sluigi
404204591Sluigi	/* now link all flows to their parent flowsets */
405294882Sluigi	DX(1,"%d flows on %d flowsets", c->flows, c->flowsets);
406294882Sluigi#ifdef USE_CUR
407294882Sluigi	c->max_y = prev ? prev->base_y + prev->y : 0;
408204591Sluigi	DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y);
409294882Sluigi#endif /* USE_CUR */
410204591Sluigi	for (i=0; i < c->flowsets; i++) {
411204591Sluigi		struct dn_fs *fs = &c->fs[i].fs;
412204591Sluigi		DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d",
413204591Sluigi			i, fs->par[0], fs->par[1],
414204591Sluigi			fs->first_flow, fs->next_flow,
415204591Sluigi			fs->base_y, fs->next_y);
416204591Sluigi		for (j = fs->first_flow; j < fs->next_flow; j++) {
417204591Sluigi			struct dn_queue *q = FI2Q(c, j);
418204591Sluigi			q->fs = &c->fs[i];
419204591Sluigi		}
420204591Sluigi	}
421204591Sluigi}
422204591Sluigi
423294882Sluigi/* available schedulers */
424294882Sluigiextern moduledata_t *_g_dn_fifo;
425294882Sluigiextern moduledata_t *_g_dn_wf2qp;
426294882Sluigiextern moduledata_t *_g_dn_rr;
427294882Sluigiextern moduledata_t *_g_dn_qfq;
428294882Sluigi#ifdef WITH_QFQP
429294882Sluigiextern moduledata_t *_g_dn_qfqp;
430294882Sluigi#endif
431294882Sluigi#ifdef WITH_KPS
432294882Sluigiextern moduledata_t *_g_dn_kps;
433294882Sluigi#endif
434294882Sluigi
435204591Sluigistatic int
436204591Sluigiinit(struct cfg_s *c)
437204591Sluigi{
438204591Sluigi	int i;
439204591Sluigi	int ac = c->ac;
440204591Sluigi	char * const *av = c->av;
441204591Sluigi
442204591Sluigi	c->si_len = sizeof(struct dn_sch_inst);
443204591Sluigi	c->q_len = sizeof(struct dn_queue);
444204591Sluigi	moduledata_t *mod = NULL;
445204591Sluigi	struct dn_alg *p = NULL;
446204591Sluigi
447294882Sluigi	c->th_min = -1; /* 1 packet per flow */
448204591Sluigi	c->th_max = -20;/* 20 packets per flow */
449204591Sluigi	c->lmin = c->lmax = 1280;	/* packet len */
450204591Sluigi	c->flows = 1;
451204591Sluigi	c->flowsets = 1;
452204591Sluigi	c->name = "null";
453204591Sluigi	ac--; av++;
454204591Sluigi	while (ac > 1) {
455204591Sluigi		if (!strcmp(*av, "-n")) {
456204591Sluigi			c->loops = getnum(av[1], NULL, av[0]);
457204591Sluigi		} else if (!strcmp(*av, "-d")) {
458204591Sluigi			debug = atoi(av[1]);
459204591Sluigi		} else if (!strcmp(*av, "-alg")) {
460204591Sluigi			if (!strcmp(av[1], "rr"))
461204591Sluigi				mod = _g_dn_rr;
462204591Sluigi			else if (!strcmp(av[1], "wf2qp"))
463204591Sluigi				mod = _g_dn_wf2qp;
464204591Sluigi			else if (!strcmp(av[1], "fifo"))
465204591Sluigi				mod = _g_dn_fifo;
466204591Sluigi			else if (!strcmp(av[1], "qfq"))
467204591Sluigi				mod = _g_dn_qfq;
468285360Sluigi#ifdef WITH_QFQP
469285360Sluigi			else if (!strcmp(av[1], "qfq+") ||
470285360Sluigi			    !strcmp(av[1], "qfqp") )
471285360Sluigi				mod = _g_dn_qfqp;
472285360Sluigi#endif
473204591Sluigi#ifdef WITH_KPS
474204591Sluigi			else if (!strcmp(av[1], "kps"))
475204591Sluigi				mod = _g_dn_kps;
476204591Sluigi#endif
477204591Sluigi			else
478204591Sluigi				mod = NULL;
479204591Sluigi			c->name = mod ? mod->name : "NULL";
480204591Sluigi			DX(3, "using scheduler %s", c->name);
481204591Sluigi		} else if (!strcmp(*av, "-len")) {
482204591Sluigi			c->lmin = getnum(av[1], NULL, av[0]);
483204591Sluigi			c->lmax = c->lmin;
484204591Sluigi			DX(3, "setting max to %d", c->th_max);
485294882Sluigi#ifdef USE_BURST
486204591Sluigi		} else if (!strcmp(*av, "-burst")) {
487204591Sluigi			c->maxburst = getnum(av[1], NULL, av[0]);
488204591Sluigi			DX(3, "setting max to %d", c->th_max);
489294882Sluigi#endif /* USE_BURST */
490204591Sluigi		} else if (!strcmp(*av, "-qmax")) {
491204591Sluigi			c->th_max = getnum(av[1], NULL, av[0]);
492204591Sluigi			DX(3, "setting max to %d", c->th_max);
493204591Sluigi		} else if (!strcmp(*av, "-qmin")) {
494204591Sluigi			c->th_min = getnum(av[1], NULL, av[0]);
495204591Sluigi			DX(3, "setting min to %d", c->th_min);
496204591Sluigi		} else if (!strcmp(*av, "-flows")) {
497204591Sluigi			c->flows = getnum(av[1], NULL, av[0]);
498204591Sluigi			DX(3, "setting flows to %d", c->flows);
499204591Sluigi		} else if (!strcmp(*av, "-flowsets")) {
500294882Sluigi			parse_flowsets(c, av[1]); /* first pass */
501204591Sluigi			DX(3, "setting flowsets to %d", c->flowsets);
502204591Sluigi		} else {
503204591Sluigi			D("option %s not recognised, ignore", *av);
504204591Sluigi		}
505204591Sluigi		ac -= 2; av += 2;
506204591Sluigi	}
507294882Sluigi#ifdef USE_BURST
508204591Sluigi	if (c->maxburst <= 0)
509204591Sluigi		c->maxburst = 1;
510294882Sluigi#endif /* USE_BURST */
511204591Sluigi	if (c->loops <= 0)
512204591Sluigi		c->loops = 1;
513204591Sluigi	if (c->flows <= 0)
514204591Sluigi		c->flows = 1;
515204591Sluigi	if (c->flowsets <= 0)
516204591Sluigi		c->flowsets = 1;
517204591Sluigi	if (c->lmin <= 0)
518204591Sluigi		c->lmin = 1;
519204591Sluigi	if (c->lmax <= 0)
520204591Sluigi		c->lmax = 1;
521204591Sluigi	/* multiply by N */
522204591Sluigi	if (c->th_min < 0)
523204591Sluigi		c->th_min = c->flows * -c->th_min;
524204591Sluigi	if (c->th_max < 0)
525204591Sluigi		c->th_max = c->flows * -c->th_max;
526204591Sluigi	if (c->th_max <= c->th_min)
527204591Sluigi		c->th_max = c->th_min + 1;
528294882Sluigi
529294882Sluigi	/* now load parameters from the module */
530204591Sluigi	if (mod) {
531204591Sluigi		p = mod->p;
532204591Sluigi		DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p);
533204591Sluigi		DX(3, "modname %s ty %d", p->name, p->type);
534294882Sluigi		// XXX check enq and deq not null
535204591Sluigi		c->enq = p->enqueue;
536204591Sluigi		c->deq = p->dequeue;
537204591Sluigi		c->si_len += p->si_datalen;
538204591Sluigi		c->q_len += p->q_datalen;
539204591Sluigi		c->schk_len += p->schk_datalen;
540294882Sluigi	} else {
541294882Sluigi		/* make sure c->si has room for a queue */
542294882Sluigi		c->enq = default_enqueue;
543294882Sluigi		c->deq = default_dequeue;
544204591Sluigi	}
545294882Sluigi
546204591Sluigi	/* allocate queues, flowsets and one scheduler */
547294882Sluigi	D("using %d flows, %d flowsets", c->flows, c->flowsets);
548294882Sluigi	D("q_len %d dn_fsk %d si %d sched %d",
549294882Sluigi		c->q_len, (int)sizeof(struct dn_fsk),
550294882Sluigi		c->si_len, c->schk_len);
551294882Sluigi	c->sched = calloc(1, c->schk_len); /* one parent scheduler */
552294882Sluigi	c->si = calloc(1, c->si_len); /* one scheduler instance */
553204591Sluigi	c->fs = calloc(c->flowsets, sizeof(struct dn_fsk));
554294882Sluigi	c->q = calloc(c->flows, c->q_len);	/* one queue per flow */
555294882Sluigi	c->q_wfi = calloc(c->flows, sizeof(double)); /* stats, one per flow */
556294882Sluigi	if (!c->sched || !c->si || !c->fs || !c->q || !c->q_wfi) {
557294882Sluigi		D("error allocating memory");
558204591Sluigi		exit(1);
559204591Sluigi	}
560294882Sluigi	c->si->sched = c->sched; /* link scheduler instance to template */
561204591Sluigi	if (p) {
562294882Sluigi		/* run initialization code if needed */
563204591Sluigi		if (p->config)
564294882Sluigi			p->config(c->si->sched);
565204591Sluigi		if (p->new_sched)
566204591Sluigi			p->new_sched(c->si);
567204591Sluigi	}
568204591Sluigi	/* parse_flowsets links queues to their flowsets */
569294882Sluigi	parse_flowsets(c, NULL); /* second pass */
570204591Sluigi	/* complete the work calling new_fsk */
571204591Sluigi	for (i = 0; i < c->flowsets; i++) {
572294882Sluigi		struct dn_fsk *fsk = &c->fs[i];
573294882Sluigi		if (fsk->fs.par[1] == 0)
574294882Sluigi			fsk->fs.par[1] = 1000;	/* default pkt len */
575294882Sluigi		fsk->sched = c->si->sched;
576204591Sluigi		if (p && p->new_fsk)
577294882Sluigi			p->new_fsk(fsk);
578204591Sluigi	}
579294882Sluigi	/* --- now the scheduler is initialized --- */
580204591Sluigi
581294882Sluigi	/*
582294882Sluigi	 * initialize the lists for the generator, and put
583204591Sluigi	 * all flows in the list for backlog = 0
584204591Sluigi	 */
585204591Sluigi	for (i=0; i <= BACKLOG+5; i++)
586204591Sluigi		INIT_LIST_HEAD(&c->ll[i]);
587204591Sluigi
588204591Sluigi	for (i = 0; i < c->flows; i++) {
589204591Sluigi		struct dn_queue *q = FI2Q(c, i);
590204591Sluigi		if (q->fs == NULL)
591204591Sluigi			q->fs = &c->fs[0]; /* XXX */
592204591Sluigi		q->_si = c->si;
593204591Sluigi		if (p && p->new_queue)
594204591Sluigi			p->new_queue(q);
595204591Sluigi		INIT_LIST_HEAD(&q->ni.h);
596204591Sluigi		list_add_tail(&q->ni.h, &c->ll[0]);
597204591Sluigi	}
598294882Sluigi	c->llmask = 1; /* all flows are in the first list */
599204591Sluigi	return 0;
600204591Sluigi}
601204591Sluigi
602204591Sluigi
603204591Sluigiint
604204591Sluigimain(int ac, char *av[])
605204591Sluigi{
606204591Sluigi	struct cfg_s c;
607204591Sluigi	double ll;
608204591Sluigi	int i;
609204591Sluigi	char msg[40];
610204591Sluigi
611204591Sluigi	bzero(&c, sizeof(c));
612204591Sluigi	c.ac = ac;
613204591Sluigi	c.av = av;
614204591Sluigi	init(&c);
615204591Sluigi	gettimeofday(&c.time, NULL);
616294882Sluigi	D("th_min %d th_max %d", c.th_min, c.th_max);
617294882Sluigi
618204591Sluigi	mainloop(&c);
619294882Sluigi	{
620294882Sluigi		struct timeval end;
621294882Sluigi		gettimeofday(&end, NULL);
622294882Sluigi		timersub(&end, &c.time, &c.time);
623204591Sluigi	}
624294882Sluigi	ll = c.time.tv_sec*1000000 + c.time.tv_usec;
625204591Sluigi	ll *= 1000;	/* convert to nanoseconds */
626204591Sluigi	ll /= c._enqueue;
627204591Sluigi	sprintf(msg, "1::%d", c.flows);
628285360Sluigi	for (i = 0; i < c.flows; i++) {
629285360Sluigi		if (c.wfi < c.q_wfi[i])
630285360Sluigi			c.wfi = c.q_wfi[i];
631285360Sluigi	}
632294882Sluigi	D("sched=%-12s\ttime=%d.%03d sec (%.0f nsec) enq %lu %lu deq\n"
633294882Sluigi	   "\twfi=%.02f\tflow=%-16s",
634294882Sluigi	   c.name, (int)c.time.tv_sec, (int)c.time.tv_usec / 1000, ll,
635294882Sluigi	   (unsigned long)c._enqueue, (unsigned long)c.dequeue, c.wfi,
636285360Sluigi	   c.fs_config ? c.fs_config : msg);
637204591Sluigi	dump(&c);
638204591Sluigi	DX(1, "done ac %d av %p", ac, av);
639204591Sluigi	for (i=0; i < ac; i++)
640204591Sluigi		DX(1, "arg %d %s", i, av[i]);
641204591Sluigi	return 0;
642204591Sluigi}
643204591Sluigi
644204591Sluigi/*
645204591Sluigi * The controller decides whether in this iteration we should send
646204591Sluigi * (the packet is in c->tosend) and/or receive (flag c->can_dequeue)
647204591Sluigi */
648204591Sluigistatic void
649204591Sluigicontroller(struct cfg_s *c)
650204591Sluigi{
651204591Sluigi	struct mbuf *m;
652204591Sluigi	struct dn_fs *fs;
653204591Sluigi	int flow_id;
654204591Sluigi
655294882Sluigi	/* hysteresis between max and min */
656294859Sluigi	if (c->state == 0 && c->pending >= (uint32_t)c->th_max)
657204591Sluigi		c->state = 1;
658294859Sluigi	else if (c->state == 1 && c->pending <= (uint32_t)c->th_min)
659204591Sluigi		c->state = 0;
660204591Sluigi	ND(1, "state %d pending %2d", c->state, c->pending);
661204591Sluigi	c->can_dequeue = c->state;
662204591Sluigi	c->tosend = NULL;
663294882Sluigi	if (c->can_dequeue)
664204591Sluigi		return;
665204591Sluigi
666294882Sluigi	/*
667294882Sluigi	 * locate the flow to use for enqueueing
668294882Sluigi	 * We take the queue with the lowest number of queued packets,
669294882Sluigi	 * generate a packet for it, and put the queue in the next highest.
670294882Sluigi	 */
671204591Sluigi    if (1) {
672204591Sluigi	int i;
673204591Sluigi	struct dn_queue *q;
674204591Sluigi	struct list_head *h;
675204591Sluigi
676204591Sluigi	i = ffs(c->llmask) - 1;
677204591Sluigi	if (i < 0) {
678294882Sluigi		D("no candidate");
679204591Sluigi		c->can_dequeue = 1;
680204591Sluigi		return;
681204591Sluigi	}
682204591Sluigi	h = &c->ll[i];
683204591Sluigi	ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next);
684204591Sluigi	q = list_first_entry(h, struct dn_queue, ni.h);
685204591Sluigi	list_del(&q->ni.h);
686204591Sluigi	flow_id = Q2FI(c, q);
687204591Sluigi	DX(2, "extracted flow %p %d backlog %d", q, flow_id, i);
688204591Sluigi	if (list_empty(h)) {
689204591Sluigi		ND(2, "backlog %d empty", i);
690204591Sluigi		c->llmask &= ~(1<<i);
691204591Sluigi	}
692204591Sluigi	ND(1, "before %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next);
693204591Sluigi	list_add_tail(&q->ni.h, h+1);
694204591Sluigi	ND(1, " after %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next);
695204591Sluigi	if (i < BACKLOG) {
696204591Sluigi		ND(2, "backlog %d full", i+1);
697204591Sluigi		c->llmask |= 1<<(1+i);
698204591Sluigi	}
699204591Sluigi	fs = &q->fs->fs;
700294882Sluigi	fs->cur = flow_id;
701294882Sluigi#ifdef USE_CUR
702204591Sluigi	c->cur_fs = q->fs - c->fs;
703204591Sluigi    } else {
704204591Sluigi	/* XXX this does not work ? */
705204591Sluigi	/* now decide whom to send the packet, and the length */
706204591Sluigi	/* lookup in the flow table */
707204591Sluigi	if (c->cur_y >= c->max_y) {	/* handle wraparound */
708204591Sluigi		c->cur_y = 0;
709204591Sluigi		c->cur_fs = 0;
710204591Sluigi	}
711204591Sluigi	fs = &c->fs[c->cur_fs].fs;
712204591Sluigi	flow_id = fs->cur++;
713204591Sluigi	if (fs->cur >= fs->next_flow)
714204591Sluigi		fs->cur = fs->first_flow;
715204591Sluigi	c->cur_y++;
716204591Sluigi	if (c->cur_y >= fs->next_y)
717204591Sluigi		c->cur_fs++;
718294882Sluigi#endif /* USE_CUR */
719204591Sluigi    }
720204591Sluigi
721204591Sluigi	/* construct a packet */
722204591Sluigi	if (c->freelist) {
723204591Sluigi		m = c->tosend = c->freelist;
724204591Sluigi		c->freelist = c->freelist->m_nextpkt;
725204591Sluigi	} else {
726204591Sluigi		m = c->tosend = calloc(1, sizeof(struct mbuf));
727204591Sluigi	}
728204591Sluigi	if (m == NULL)
729204591Sluigi		return;
730204591Sluigi
731294882Sluigi	//m->cfg = c;
732204591Sluigi	m->m_nextpkt = NULL;
733204591Sluigi	m->m_pkthdr.len = fs->par[1]; // XXX maxlen
734204591Sluigi	m->flow_id = flow_id;
735204591Sluigi
736204591Sluigi	ND(2,"y %6d flow %5d fs %3d weight %4d len %4d",
737204591Sluigi		c->cur_y, m->flow_id, c->cur_fs,
738204591Sluigi		fs->par[0], m->m_pkthdr.len);
739204591Sluigi
740204591Sluigi}
741