1/*
2 * $FreeBSD$
3 *
4 * Testing program for schedulers
5 *
6 * The framework include a simple controller which, at each
7 * iteration, decides whether we can enqueue and/or dequeue.
8 * Then the mainloop runs the required number of tests,
9 * keeping track of statistics.
10 */
11
12#include "dn_test.h"
13
14struct q_list {
15	struct list_head h;
16};
17
18struct cfg_s {
19	int ac;
20	char * const *av;
21
22	const char *name;
23	int loops;
24	struct timeval time;
25
26	/* running counters */
27	uint32_t	_enqueue;
28	uint32_t	drop;
29	uint32_t	pending;
30	uint32_t	dequeue;
31
32	/* generator parameters */
33	int th_min, th_max;
34	int maxburst;
35	int lmin, lmax;	/* packet len */
36	int flows;	/* number of flows */
37	int flowsets;	/* number of flowsets */
38	int wsum;	/* sum of weights of all flows */
39	int max_y;	/* max random number in the generation */
40	int cur_y, cur_fs;	/* used in generation, between 0 and max_y - 1 */
41	const char *fs_config; /* flowset config */
42	int can_dequeue;
43	int burst;	/* count of packets sent in a burst */
44	struct mbuf *tosend;	/* packet to send -- also flag to enqueue */
45
46	struct mbuf *freelist;
47
48	struct mbuf *head, *tail;	/* a simple tailq */
49
50	/* scheduler hooks */
51	int (*enq)(struct dn_sch_inst *, struct dn_queue *,
52		struct mbuf *);
53	struct mbuf * (*deq)(struct dn_sch_inst *);
54	/* size of the three fields including sched-specific areas */
55	int schk_len;
56	int q_len; /* size of a queue including sched-fields */
57	int si_len; /* size of a sch_inst including sched-fields */
58	char *q;	/* array of flow queues */
59		/* use a char* because size is variable */
60	struct dn_fsk *fs;	/* array of flowsets */
61	struct dn_sch_inst *si;
62	struct dn_schk *sched;
63
64	/* generator state */
65	int state;		/* 0 = going up, 1: going down */
66
67	/*
68	 * We keep lists for each backlog level, and always serve
69	 * the one with shortest backlog. llmask contains a bitmap
70	 * of lists, and ll are the heads of the lists. The last
71	 * entry (BACKLOG) contains all entries considered 'full'
72	 * XXX to optimize things, entry i could contain queues with
73	 * 2^{i-1}+1 .. 2^i entries.
74	 */
75#define BACKLOG	30
76	uint32_t	llmask;
77	struct list_head ll[BACKLOG + 10];
78};
79
80/* FI2Q and Q2FI converts from flow_id to dn_queue and back.
81 * We cannot easily use pointer arithmetic because it is variable size.
82  */
83#define FI2Q(c, i)	((struct dn_queue *)((c)->q + (c)->q_len * (i)))
84#define Q2FI(c, q)	(((char *)(q) - (c)->q)/(c)->q_len)
85
86int debug = 0;
87
88struct dn_parms dn_cfg;
89
90static void controller(struct cfg_s *c);
91
92/* release a packet: put the mbuf in the freelist, and the queue in
93 * the bucket.
94 */
95int
96drop(struct cfg_s *c, struct mbuf *m)
97{
98	struct dn_queue *q;
99	int i;
100
101	c->drop++;
102	q = FI2Q(c, m->flow_id);
103	i = q->ni.length; // XXX or ffs...
104
105	ND("q %p id %d current length %d", q, m->flow_id, i);
106	if (i < BACKLOG) {
107		struct list_head *h = &q->ni.h;
108		c->llmask &= ~(1<<(i+1));
109		c->llmask |= (1<<(i));
110		list_del(h);
111		list_add_tail(h, &c->ll[i]);
112	}
113	m->m_nextpkt = c->freelist;
114	c->freelist = m;
115	return 0;
116}
117
118/* dequeue returns NON-NULL when a packet is dropped */
119static int
120enqueue(struct cfg_s *c, void *_m)
121{
122	struct mbuf *m = _m;
123	if (c->enq)
124		return c->enq(c->si, FI2Q(c, m->flow_id), m);
125	if (c->head == NULL)
126		c->head = m;
127	else
128		c->tail->m_nextpkt = m;
129	c->tail = m;
130	return 0; /* default - success */
131}
132
133/* dequeue returns NON-NULL when a packet is available */
134static void *
135dequeue(struct cfg_s *c)
136{
137	struct mbuf *m;
138	if (c->deq)
139		return c->deq(c->si);
140	if ((m = c->head)) {
141		m = c->head;
142		c->head = m->m_nextpkt;
143		m->m_nextpkt = NULL;
144	}
145	return m;
146}
147
148static int
149mainloop(struct cfg_s *c)
150{
151	int i;
152	struct mbuf *m;
153
154	for (i=0; i < c->loops; i++) {
155		/* implement histeresis */
156		controller(c);
157		DX(3, "loop %d enq %d send %p rx %d",
158			i, c->_enqueue, c->tosend, c->can_dequeue);
159		if ( (m = c->tosend) ) {
160			c->_enqueue++;
161			if (enqueue(c, m)) {
162				drop(c, m);
163				ND("loop %d enqueue fail", i );
164			} else {
165				ND("enqueue ok");
166				c->pending++;
167			}
168		}
169		if (c->can_dequeue) {
170			c->dequeue++;
171			if ((m = dequeue(c))) {
172				c->pending--;
173				drop(c, m);
174				c->drop--;	/* compensate */
175			}
176		}
177	}
178	DX(1, "mainloop ends %d", i);
179	return 0;
180}
181
182int
183dump(struct cfg_s *c)
184{
185	int i;
186	struct dn_queue *q;
187
188	for (i=0; i < c->flows; i++) {
189		q = FI2Q(c, i);
190		DX(1, "queue %4d tot %10lld", i, q->ni.tot_bytes);
191	}
192	DX(1, "done %d loops\n", c->loops);
193	return 0;
194}
195
196/* interpret a number in human form */
197static long
198getnum(const char *s, char **next, const char *key)
199{
200	char *end = NULL;
201	long l;
202
203	if (next)	/* default */
204		*next = NULL;
205	if (s && *s) {
206		DX(3, "token is <%s> %s", s, key ? key : "-");
207		l = strtol(s, &end, 0);
208	} else {
209		DX(3, "empty string");
210		l = -1;
211	}
212	if (l < 0) {
213		DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") );
214		return 0;	// invalid
215	}
216	if (!end || !*end)
217		return l;
218	if (*end == 'n')
219		l = -l;	/* multiply by n */
220	else if (*end == 'K')
221		l = l*1000;
222	else if (*end == 'M')
223		l = l*1000000;
224	else if (*end == 'k')
225		l = l*1024;
226	else if (*end == 'm')
227		l = l*1024*1024;
228	else if (*end == 'w')
229		;
230	else {/* not recognized */
231		D("suffix %s for %s, next %p", end, key, next);
232		end--;
233	}
234	end++;
235	DX(3, "suffix now %s for %s, next %p", end, key, next);
236	if (next && *end) {
237		DX(3, "setting next to %s for %s", end, key);
238		*next = end;
239	}
240	return l;
241}
242
243/*
244 * flowsets are a comma-separated list of
245 *     weight:maxlen:flows
246 * indicating how many flows are hooked to that fs.
247 * Both weight and range can be min-max-steps.
248 * In a first pass we just count the number of flowsets and flows,
249 * in a second pass we complete the setup.
250 */
251static void
252parse_flowsets(struct cfg_s *c, const char *fs, int pass)
253{
254	char *s, *cur, *next;
255	int n_flows = 0, n_fs = 0, wsum = 0;
256	int i, j;
257	struct dn_fs *prev = NULL;
258
259	DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets);
260	if (pass == 0)
261		c->fs_config = fs;
262	s = c->fs_config ? strdup(c->fs_config) : NULL;
263	if (s == NULL) {
264		if (pass == 0)
265			D("no fsconfig");
266		return;
267	}
268	for (next = s; (cur = strsep(&next, ","));) {
269		char *p = NULL;
270		int w, w_h, w_steps, wi;
271		int len, len_h, l_steps, li;
272		int flows;
273
274		w = getnum(strsep(&cur, ":"), &p, "weight");
275		if (w <= 0)
276			w = 1;
277		w_h = p ? getnum(p+1, &p, "weight_max") : w;
278		w_steps = p ? getnum(p+1, &p, "w_steps") : (w_h == w ?1:2);
279		len = getnum(strsep(&cur, ":"), &p, "len");
280		if (len <= 0)
281			len = 1000;
282		len_h = p ? getnum(p+1, &p, "len_max") : len;
283		l_steps = p ? getnum(p+1, &p, "l_steps") : (len_h == len ? 1 : 2);
284		flows = getnum(strsep(&cur, ":"), NULL, "flows");
285		if (flows == 0)
286			flows = 1;
287		DX(4, "weight %d..%d (%d) len %d..%d (%d) flows %d",
288			w, w_h, w_steps, len, len_h, l_steps, flows);
289		if (w == 0 || w_h < w || len == 0 || len_h < len ||
290				flows == 0) {
291			DX(4,"wrong parameters %s", fs);
292			return;
293		}
294		n_flows += flows * w_steps * l_steps;
295		for (i = 0; i < w_steps; i++) {
296			wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1));
297			for (j = 0; j < l_steps; j++, n_fs++) {
298				struct dn_fs *fs = &c->fs[n_fs].fs; // tentative
299				int x;
300
301				li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1));
302				x = (wi*2048)/li;
303				DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d",
304					n_fs, wi, li, x, flows);
305				if (pass == 0)
306					continue;
307				if (c->fs == NULL || c->flowsets <= n_fs) {
308					D("error in number of flowsets");
309					return;
310				}
311				wsum += wi * flows;
312				fs->par[0] = wi;
313				fs->par[1] = li;
314				fs->index = n_fs;
315				fs->n_flows = flows;
316				fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow;
317				fs->next_flow = fs->first_flow + fs->n_flows;
318				fs->y = x * flows;
319				fs->base_y = (prev == NULL) ? 0 : prev->next_y;
320				fs->next_y = fs->base_y + fs->y;
321				prev = fs;
322			}
323		}
324	}
325	c->max_y = prev ? prev->base_y + prev->y : 0;
326	c->flows = n_flows;
327	c->flowsets = n_fs;
328	c->wsum = wsum;
329	if (pass == 0)
330		return;
331
332	/* now link all flows to their parent flowsets */
333	DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y);
334	for (i=0; i < c->flowsets; i++) {
335		struct dn_fs *fs = &c->fs[i].fs;
336		DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d",
337			i, fs->par[0], fs->par[1],
338			fs->first_flow, fs->next_flow,
339			fs->base_y, fs->next_y);
340		for (j = fs->first_flow; j < fs->next_flow; j++) {
341			struct dn_queue *q = FI2Q(c, j);
342			q->fs = &c->fs[i];
343		}
344	}
345}
346
347static int
348init(struct cfg_s *c)
349{
350	int i;
351	int ac = c->ac;
352	char * const *av = c->av;
353
354	c->si_len = sizeof(struct dn_sch_inst);
355	c->q_len = sizeof(struct dn_queue);
356	moduledata_t *mod = NULL;
357	struct dn_alg *p = NULL;
358
359	c->th_min = 0;
360	c->th_max = -20;/* 20 packets per flow */
361	c->lmin = c->lmax = 1280;	/* packet len */
362	c->flows = 1;
363	c->flowsets = 1;
364	c->name = "null";
365	ac--; av++;
366	while (ac > 1) {
367		if (!strcmp(*av, "-n")) {
368			c->loops = getnum(av[1], NULL, av[0]);
369		} else if (!strcmp(*av, "-d")) {
370			debug = atoi(av[1]);
371		} else if (!strcmp(*av, "-alg")) {
372			extern moduledata_t *_g_dn_fifo;
373			extern moduledata_t *_g_dn_wf2qp;
374			extern moduledata_t *_g_dn_rr;
375			extern moduledata_t *_g_dn_qfq;
376#ifdef WITH_KPS
377			extern moduledata_t *_g_dn_kps;
378#endif
379			if (!strcmp(av[1], "rr"))
380				mod = _g_dn_rr;
381			else if (!strcmp(av[1], "wf2qp"))
382				mod = _g_dn_wf2qp;
383			else if (!strcmp(av[1], "fifo"))
384				mod = _g_dn_fifo;
385			else if (!strcmp(av[1], "qfq"))
386				mod = _g_dn_qfq;
387#ifdef WITH_KPS
388			else if (!strcmp(av[1], "kps"))
389				mod = _g_dn_kps;
390#endif
391			else
392				mod = NULL;
393			c->name = mod ? mod->name : "NULL";
394			DX(3, "using scheduler %s", c->name);
395		} else if (!strcmp(*av, "-len")) {
396			c->lmin = getnum(av[1], NULL, av[0]);
397			c->lmax = c->lmin;
398			DX(3, "setting max to %d", c->th_max);
399		} else if (!strcmp(*av, "-burst")) {
400			c->maxburst = getnum(av[1], NULL, av[0]);
401			DX(3, "setting max to %d", c->th_max);
402		} else if (!strcmp(*av, "-qmax")) {
403			c->th_max = getnum(av[1], NULL, av[0]);
404			DX(3, "setting max to %d", c->th_max);
405		} else if (!strcmp(*av, "-qmin")) {
406			c->th_min = getnum(av[1], NULL, av[0]);
407			DX(3, "setting min to %d", c->th_min);
408		} else if (!strcmp(*av, "-flows")) {
409			c->flows = getnum(av[1], NULL, av[0]);
410			DX(3, "setting flows to %d", c->flows);
411		} else if (!strcmp(*av, "-flowsets")) {
412			parse_flowsets(c, av[1], 0);
413			DX(3, "setting flowsets to %d", c->flowsets);
414		} else {
415			D("option %s not recognised, ignore", *av);
416		}
417		ac -= 2; av += 2;
418	}
419	if (c->maxburst <= 0)
420		c->maxburst = 1;
421	if (c->loops <= 0)
422		c->loops = 1;
423	if (c->flows <= 0)
424		c->flows = 1;
425	if (c->flowsets <= 0)
426		c->flowsets = 1;
427	if (c->lmin <= 0)
428		c->lmin = 1;
429	if (c->lmax <= 0)
430		c->lmax = 1;
431	/* multiply by N */
432	if (c->th_min < 0)
433		c->th_min = c->flows * -c->th_min;
434	if (c->th_max < 0)
435		c->th_max = c->flows * -c->th_max;
436	if (c->th_max <= c->th_min)
437		c->th_max = c->th_min + 1;
438	if (mod) {
439		p = mod->p;
440		DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p);
441		DX(3, "modname %s ty %d", p->name, p->type);
442		c->enq = p->enqueue;
443		c->deq = p->dequeue;
444		c->si_len += p->si_datalen;
445		c->q_len += p->q_datalen;
446		c->schk_len += p->schk_datalen;
447	}
448	/* allocate queues, flowsets and one scheduler */
449	c->q = calloc(c->flows, c->q_len);
450	c->fs = calloc(c->flowsets, sizeof(struct dn_fsk));
451	c->si = calloc(1, c->si_len);
452	c->sched = calloc(c->flows, c->schk_len);
453	if (c->q == NULL || c->fs == NULL) {
454		D("error allocating memory for flows");
455		exit(1);
456	}
457	c->si->sched = c->sched;
458	if (p) {
459		if (p->config)
460			p->config(c->sched);
461		if (p->new_sched)
462			p->new_sched(c->si);
463	}
464	/* parse_flowsets links queues to their flowsets */
465	parse_flowsets(c, av[1], 1);
466	/* complete the work calling new_fsk */
467	for (i = 0; i < c->flowsets; i++) {
468		if (c->fs[i].fs.par[1] == 0)
469			c->fs[i].fs.par[1] = 1000;	/* default pkt len */
470		c->fs[i].sched = c->sched;
471		if (p && p->new_fsk)
472			p->new_fsk(&c->fs[i]);
473	}
474
475	/* initialize the lists for the generator, and put
476	 * all flows in the list for backlog = 0
477	 */
478	for (i=0; i <= BACKLOG+5; i++)
479		INIT_LIST_HEAD(&c->ll[i]);
480
481	for (i = 0; i < c->flows; i++) {
482		struct dn_queue *q = FI2Q(c, i);
483		if (q->fs == NULL)
484			q->fs = &c->fs[0]; /* XXX */
485		q->_si = c->si;
486		if (p && p->new_queue)
487			p->new_queue(q);
488		INIT_LIST_HEAD(&q->ni.h);
489		list_add_tail(&q->ni.h, &c->ll[0]);
490	}
491	c->llmask = 1;
492	return 0;
493}
494
495
496int
497main(int ac, char *av[])
498{
499	struct cfg_s c;
500	struct timeval end;
501	double ll;
502	int i;
503	char msg[40];
504
505	bzero(&c, sizeof(c));
506	c.ac = ac;
507	c.av = av;
508	init(&c);
509	gettimeofday(&c.time, NULL);
510	mainloop(&c);
511	gettimeofday(&end, NULL);
512	end.tv_sec -= c.time.tv_sec;
513	end.tv_usec -= c.time.tv_usec;
514	if (end.tv_usec < 0) {
515		end.tv_usec += 1000000;
516		end.tv_sec--;
517	}
518	c.time = end;
519	ll = end.tv_sec*1000000 + end.tv_usec;
520	ll *= 1000;	/* convert to nanoseconds */
521	ll /= c._enqueue;
522	sprintf(msg, "1::%d", c.flows);
523	D("%-8s n %d %d time %d.%06d %8.3f qlen %d %d flows %s drops %d",
524		c.name, c._enqueue, c.loops,
525		(int)c.time.tv_sec, (int)c.time.tv_usec, ll,
526		c.th_min, c.th_max,
527		c.fs_config ? c.fs_config : msg, c.drop);
528	dump(&c);
529	DX(1, "done ac %d av %p", ac, av);
530	for (i=0; i < ac; i++)
531		DX(1, "arg %d %s", i, av[i]);
532	return 0;
533}
534
535/*
536 * The controller decides whether in this iteration we should send
537 * (the packet is in c->tosend) and/or receive (flag c->can_dequeue)
538 */
539static void
540controller(struct cfg_s *c)
541{
542	struct mbuf *m;
543	struct dn_fs *fs;
544	int flow_id;
545
546	/* histeresis between max and min */
547	if (c->state == 0 && c->pending >= c->th_max)
548		c->state = 1;
549	else if (c->state == 1 && c->pending <= c->th_min)
550		c->state = 0;
551	ND(1, "state %d pending %2d", c->state, c->pending);
552	c->can_dequeue = c->state;
553	c->tosend = NULL;
554	if (c->state)
555		return;
556
557    if (1) {
558	int i;
559	struct dn_queue *q;
560	struct list_head *h;
561
562	i = ffs(c->llmask) - 1;
563	if (i < 0) {
564		DX(2, "no candidate");
565		c->can_dequeue = 1;
566		return;
567	}
568	h = &c->ll[i];
569	ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next);
570	q = list_first_entry(h, struct dn_queue, ni.h);
571	list_del(&q->ni.h);
572	flow_id = Q2FI(c, q);
573	DX(2, "extracted flow %p %d backlog %d", q, flow_id, i);
574	if (list_empty(h)) {
575		ND(2, "backlog %d empty", i);
576		c->llmask &= ~(1<<i);
577	}
578	ND(1, "before %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next);
579	list_add_tail(&q->ni.h, h+1);
580	ND(1, " after %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next);
581	if (i < BACKLOG) {
582		ND(2, "backlog %d full", i+1);
583		c->llmask |= 1<<(1+i);
584	}
585	fs = &q->fs->fs;
586	c->cur_fs = q->fs - c->fs;
587	fs->cur = flow_id;
588    } else {
589	/* XXX this does not work ? */
590	/* now decide whom to send the packet, and the length */
591	/* lookup in the flow table */
592	if (c->cur_y >= c->max_y) {	/* handle wraparound */
593		c->cur_y = 0;
594		c->cur_fs = 0;
595	}
596	fs = &c->fs[c->cur_fs].fs;
597	flow_id = fs->cur++;
598	if (fs->cur >= fs->next_flow)
599		fs->cur = fs->first_flow;
600	c->cur_y++;
601	if (c->cur_y >= fs->next_y)
602		c->cur_fs++;
603    }
604
605	/* construct a packet */
606	if (c->freelist) {
607		m = c->tosend = c->freelist;
608		c->freelist = c->freelist->m_nextpkt;
609	} else {
610		m = c->tosend = calloc(1, sizeof(struct mbuf));
611	}
612	if (m == NULL)
613		return;
614
615	m->cfg = c;
616	m->m_nextpkt = NULL;
617	m->m_pkthdr.len = fs->par[1]; // XXX maxlen
618	m->flow_id = flow_id;
619
620	ND(2,"y %6d flow %5d fs %3d weight %4d len %4d",
621		c->cur_y, m->flow_id, c->cur_fs,
622		fs->par[0], m->m_pkthdr.len);
623
624}
625
626/*
627Packet allocation:
628to achieve a distribution that matches weights, for each X=w/lmax class
629we should generate a number of packets proportional to Y = X times the number
630of flows in the class.
631So we construct an array with the cumulative distribution of Y's,
632and use it to identify the flow via inverse mapping (if the Y's are
633not too many we can use an array for the lookup). In practice,
634each flow will have X entries [virtually] pointing to it.
635
636*/
637