main.c revision 302408
1/*
2 * $FreeBSD: stable/11/sys/netpfil/ipfw/test/main.c 294882 2016-01-27 02:22:31Z luigi $
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// #define USE_BURST	// what is this for ?
13
14#include "dn_test.h"
15
16struct cfg_s {
17	int ac;
18	char * const *av;
19
20	const char *name;
21	int loops;
22	struct timeval time;
23
24	/* running counters */
25	uint32_t	_enqueue;
26	uint32_t	drop;
27	uint32_t	pending;
28	uint32_t	dequeue;
29
30	/* generator parameters */
31	int32_t th_min, th_max;	/* thresholds for hysteresis; negative means per flow */
32#ifdef USE_BURST
33	int maxburst;
34#endif /* USE_BURST */
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#ifdef USE_CUR
40	int max_y;	/* max random number in the generation */
41	int cur_y
42	int cur_fs;	/* used in generation, between 0 and max_y - 1 */
43#endif /* USE_CUR */
44	const char *fs_config; /* flowset config */
45	int can_dequeue;
46	int burst;	/* count of packets sent in a burst */
47	struct mbuf *tosend;	/* packet to send -- also flag to enqueue */
48
49	struct mbuf *freelist;
50
51	struct mbuf *head, *tail;	/* a simple tailq */
52
53	/* scheduler hooks */
54	int (*enq)(struct dn_sch_inst *, struct dn_queue *,
55		struct mbuf *);
56	struct mbuf * (*deq)(struct dn_sch_inst *);
57	/* size of the three fields including sched-specific areas */
58	uint32_t schk_len;
59	uint32_t q_len; /* size of a queue including sched-fields */
60	uint32_t si_len; /* size of a sch_inst including sched-fields */
61	char *q;	/* array of flow queues */
62		/* use a char* because size is variable */
63	/*
64	 * The scheduler template (one) followd by schk_datalen bytes
65	 * for scheduler-specific parameters, total size is schk_len
66	 */
67	struct dn_schk *sched;
68	/*
69	 * one scheduler instance, followed by si_datalen bytes
70	 * for scheduler specific parameters of this instance,
71	 * total size is si_len. si->sched points to sched
72	 */
73	struct dn_sch_inst *si;
74	struct dn_fsk *fs;	/* array of flowsets */
75
76	/* generator state */
77	int state;	/* 0 = going up (enqueue), 1: going down (dequeue) */
78
79	/*
80	 * We keep lists for each backlog level, and always serve
81	 * the one with shortest backlog. llmask contains a bitmap
82	 * of lists, and ll are the heads of the lists. The last
83	 * entry (BACKLOG) contains all entries considered 'full'
84	 * XXX to optimize things, entry i could contain queues with
85	 * 2^{i-1}+1 .. 2^i entries.
86	 */
87#define BACKLOG	30 /* this many backlogged classes, we only need BACKLOG+1 */
88	uint64_t	llmask;
89	struct list_head ll[BACKLOG + 10];
90
91	double *q_wfi;	/* (byte) Worst-case Fair Index of the flows  */
92	double wfi;	/* (byte) Worst-case Fair Index of the system */
93};
94
95/* FI2Q and Q2FI converts from flow_id (i.e. queue index)
96 * to dn_queue and back. We cannot simply use pointer arithmetic
97 * because the queu has variable size, q_len
98 */
99#define FI2Q(c, i)	((struct dn_queue *)((c)->q + (c)->q_len * (i)))
100#define Q2FI(c, q)	(((char *)(q) - (c)->q)/(c)->q_len)
101
102int debug = 0;
103
104struct dn_parms dn_cfg;
105
106static void controller(struct cfg_s *c);
107
108/* release a packet for a given flow_id.
109 * Put the mbuf in the freelist, and in case move the
110 * flow to the end of the bucket.
111 */
112static int
113drop(struct cfg_s *c, struct mbuf *m)
114{
115	struct dn_queue *q;
116	int i;
117
118	c->drop++;
119	q = FI2Q(c, m->flow_id);
120	i = q->ni.length; // XXX or ffs...
121
122	ND("q %p id %d current length %d", q, m->flow_id, i);
123	if (i < BACKLOG) {
124		struct list_head *h = &q->ni.h;
125		c->llmask &= ~(1<<(i+1));
126		c->llmask |= (1<<(i));
127		list_del(h);
128		list_add_tail(h, &c->ll[i]);
129	}
130	m->m_nextpkt = c->freelist;
131	c->freelist = m;
132	return 0;
133}
134
135
136/*
137 * dn_sch_inst does not have a queue, for the RR we
138 * allocate a mq right after si
139 */
140static int
141default_enqueue(struct dn_sch_inst *si, struct dn_queue *q, struct mbuf *m)
142{
143	struct mq *mq = (struct mq *)si;
144
145	(void)q;
146	/* this is the default function if no scheduler is provided */
147	if (mq->head == NULL)
148		mq->head = m;
149	else
150		mq->tail->m_nextpkt = m;
151	mq->tail = m;
152	return 0; /* default - success */
153}
154
155
156static struct mbuf *
157default_dequeue(struct dn_sch_inst *si)
158{
159	struct mq *mq = (struct mq *)si;
160	struct mbuf *m;
161	/* this is the default function if no scheduler is provided */
162	if ((m = mq->head)) {
163		m = mq->head;
164		mq->head = m->m_nextpkt;
165		m->m_nextpkt = NULL;
166	}
167	return m;
168}
169
170static void
171gnet_stats_enq(struct cfg_s *c, struct mbuf *mb)
172{
173	struct dn_sch_inst *si = c->si;
174	struct dn_queue *_q = FI2Q(c, mb->flow_id);
175
176	if (_q->ni.length == 1) {
177		_q->ni.bytes = 0;
178		_q->ni.sch_bytes = si->ni.bytes;
179	}
180}
181
182static void
183gnet_stats_deq(struct cfg_s *c, struct mbuf *mb)
184{
185	struct dn_sch_inst *si = c->si;
186	struct dn_queue *_q = FI2Q(c, mb->flow_id);
187	int len = mb->m_pkthdr.len;
188
189	_q->ni.bytes += len;
190	si->ni.bytes += len;
191
192	if (_q->ni.length == 0) {
193		double bytes = (double)_q->ni.bytes;
194		double sch_bytes = (double)si->ni.bytes - _q->ni.sch_bytes;
195		double weight = (double)_q->fs->fs.par[0] / c->wsum;
196		double wfi = sch_bytes * weight - bytes;
197
198		if (c->q_wfi[mb->flow_id] < wfi)
199			c->q_wfi[mb->flow_id] = wfi;
200	}
201}
202
203static int
204mainloop(struct cfg_s *c)
205{
206	int i;
207	struct mbuf *m;
208
209	for (i=0; i < c->loops; i++) {
210		/* implement histeresis */
211		controller(c);
212		DX(3, "loop %d enq %d send %p rx %d",
213			i, c->_enqueue, c->tosend, c->can_dequeue);
214		if ( (m = c->tosend) ) {
215			int ret;
216			struct dn_queue *q = FI2Q(c, m->flow_id);
217			c->_enqueue++;
218			ret = c->enq(c->si, q, m);
219			if (ret) {
220				drop(c, m);
221				D("loop %d enqueue fail", i );
222				/*
223				 * XXX do not insist; rather, try dequeue
224				 */
225				goto do_dequeue;
226			} else {
227				ND("enqueue ok");
228				c->pending++;
229				gnet_stats_enq(c, m);
230			}
231		} else if (c->can_dequeue) {
232do_dequeue:
233			c->dequeue++;
234			m = c->deq(c->si);
235			if (m) {
236				c->pending--;
237				drop(c, m);
238				c->drop--;	/* compensate */
239				gnet_stats_deq(c, m);
240			} else {
241				D("--- ouch, cannot operate on iteration %d, pending %d", i, c->pending);
242				break;
243			}
244		}
245	}
246	DX(1, "mainloop ends %d", i);
247	return 0;
248}
249
250int
251dump(struct cfg_s *c)
252{
253	int i;
254
255	for (i=0; i < c->flows; i++) {
256		//struct dn_queue *q = FI2Q(c, i);
257		ND(1, "queue %4d tot %10llu", i,
258		    (unsigned long long)q->ni.tot_bytes);
259	}
260	DX(1, "done %d loops\n", c->loops);
261	return 0;
262}
263
264/* interpret a number in human form */
265static long
266getnum(const char *s, char **next, const char *key)
267{
268	char *end = NULL;
269	long l;
270
271	if (next)	/* default */
272		*next = NULL;
273	if (s && *s) {
274		DX(3, "token is <%s> %s", s, key ? key : "-");
275		l = strtol(s, &end, 0);
276	} else {
277		DX(3, "empty string");
278		l = -1;
279	}
280	if (l < 0) {
281		DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") );
282		return 0;	// invalid
283	}
284	if (!end || !*end)
285		return l;
286	if (*end == 'n')
287		l = -l;	/* multiply by n */
288	else if (*end == 'K')
289		l = l*1000;
290	else if (*end == 'M')
291		l = l*1000000;
292	else if (*end == 'k')
293		l = l*1024;
294	else if (*end == 'm')
295		l = l*1024*1024;
296	else if (*end == 'w')
297		;
298	else {/* not recognized */
299		D("suffix %s for %s, next %p", end, key, next);
300		end--;
301	}
302	end++;
303	DX(3, "suffix now %s for %s, next %p", end, key, next);
304	if (next && *end) {
305		DX(3, "setting next to %s for %s", end, key);
306		*next = end;
307	}
308	return l;
309}
310
311/*
312 * flowsets are a comma-separated list of
313 *     weight:maxlen:flows
314 * indicating how many flows are hooked to that fs.
315 * Both weight and range can be min-max-steps.
316 * The first pass (fs != NULL) justs count the number of flowsets and flows,
317 * the second pass (fs == NULL) we complete the setup.
318 */
319static void
320parse_flowsets(struct cfg_s *c, const char *fs)
321{
322	char *s, *cur, *next;
323	int n_flows = 0, n_fs = 0, wsum = 0;
324	int i, j;
325	struct dn_fs *prev = NULL;
326	int pass = (fs == NULL);
327
328	DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets);
329	if (fs != NULL) { /* first pass */
330		if (c->fs_config)
331			D("warning, overwriting fs %s with %s",
332				c->fs_config, fs);
333		c->fs_config = fs;
334	}
335	s = c->fs_config ? strdup(c->fs_config) : NULL;
336	if (s == NULL) {
337		if (pass == 0)
338			D("no fsconfig");
339		return;
340	}
341	for (next = s; (cur = strsep(&next, ","));) {
342		char *p = NULL;
343		int w, w_h, w_steps, wi;
344		int len, len_h, l_steps, li;
345		int flows;
346
347		w = getnum(strsep(&cur, ":"), &p, "weight");
348		if (w <= 0)
349			w = 1;
350		w_h = p ? getnum(p+1, &p, "weight_max") : w;
351		w_steps = p ? getnum(p+1, &p, "w_steps") : (w_h == w ?1:2);
352		len = getnum(strsep(&cur, ":"), &p, "len");
353		if (len <= 0)
354			len = 1000;
355		len_h = p ? getnum(p+1, &p, "len_max") : len;
356		l_steps = p ? getnum(p+1, &p, "l_steps") : (len_h == len ? 1 : 2);
357		flows = getnum(strsep(&cur, ":"), NULL, "flows");
358		if (flows == 0)
359			flows = 1;
360		DX(4, "weight %d..%d (%d) len %d..%d (%d) flows %d",
361			w, w_h, w_steps, len, len_h, l_steps, flows);
362		if (w == 0 || w_h < w || len == 0 || len_h < len ||
363				flows == 0) {
364			DX(4,"wrong parameters %s", s);
365			return;
366		}
367		n_flows += flows * w_steps * l_steps;
368		for (i = 0; i < w_steps; i++) {
369			wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1));
370			for (j = 0; j < l_steps; j++, n_fs++) {
371				struct dn_fs *fs = &c->fs[n_fs].fs; // tentative
372				int x;
373
374				li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1));
375				x = (wi*2048)/li;
376				DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d",
377					n_fs, wi, li, x, flows);
378				if (pass == 0)
379					continue;
380				if (c->fs == NULL || c->flowsets <= n_fs) {
381					D("error in number of flowsets");
382					return;
383				}
384				wsum += wi * flows;
385				fs->par[0] = wi;
386				fs->par[1] = li;
387				fs->index = n_fs;
388				fs->n_flows = flows;
389				fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow;
390				fs->next_flow = fs->first_flow + fs->n_flows;
391				fs->y = x * flows;
392				fs->base_y = (prev == NULL) ? 0 : prev->next_y;
393				fs->next_y = fs->base_y + fs->y;
394				prev = fs;
395			}
396		}
397	}
398	c->flows = n_flows;
399	c->flowsets = n_fs;
400	c->wsum = wsum;
401	if (pass == 0)
402		return;
403
404	/* now link all flows to their parent flowsets */
405	DX(1,"%d flows on %d flowsets", c->flows, c->flowsets);
406#ifdef USE_CUR
407	c->max_y = prev ? prev->base_y + prev->y : 0;
408	DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y);
409#endif /* USE_CUR */
410	for (i=0; i < c->flowsets; i++) {
411		struct dn_fs *fs = &c->fs[i].fs;
412		DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d",
413			i, fs->par[0], fs->par[1],
414			fs->first_flow, fs->next_flow,
415			fs->base_y, fs->next_y);
416		for (j = fs->first_flow; j < fs->next_flow; j++) {
417			struct dn_queue *q = FI2Q(c, j);
418			q->fs = &c->fs[i];
419		}
420	}
421}
422
423/* available schedulers */
424extern moduledata_t *_g_dn_fifo;
425extern moduledata_t *_g_dn_wf2qp;
426extern moduledata_t *_g_dn_rr;
427extern moduledata_t *_g_dn_qfq;
428#ifdef WITH_QFQP
429extern moduledata_t *_g_dn_qfqp;
430#endif
431#ifdef WITH_KPS
432extern moduledata_t *_g_dn_kps;
433#endif
434
435static int
436init(struct cfg_s *c)
437{
438	int i;
439	int ac = c->ac;
440	char * const *av = c->av;
441
442	c->si_len = sizeof(struct dn_sch_inst);
443	c->q_len = sizeof(struct dn_queue);
444	moduledata_t *mod = NULL;
445	struct dn_alg *p = NULL;
446
447	c->th_min = -1; /* 1 packet per flow */
448	c->th_max = -20;/* 20 packets per flow */
449	c->lmin = c->lmax = 1280;	/* packet len */
450	c->flows = 1;
451	c->flowsets = 1;
452	c->name = "null";
453	ac--; av++;
454	while (ac > 1) {
455		if (!strcmp(*av, "-n")) {
456			c->loops = getnum(av[1], NULL, av[0]);
457		} else if (!strcmp(*av, "-d")) {
458			debug = atoi(av[1]);
459		} else if (!strcmp(*av, "-alg")) {
460			if (!strcmp(av[1], "rr"))
461				mod = _g_dn_rr;
462			else if (!strcmp(av[1], "wf2qp"))
463				mod = _g_dn_wf2qp;
464			else if (!strcmp(av[1], "fifo"))
465				mod = _g_dn_fifo;
466			else if (!strcmp(av[1], "qfq"))
467				mod = _g_dn_qfq;
468#ifdef WITH_QFQP
469			else if (!strcmp(av[1], "qfq+") ||
470			    !strcmp(av[1], "qfqp") )
471				mod = _g_dn_qfqp;
472#endif
473#ifdef WITH_KPS
474			else if (!strcmp(av[1], "kps"))
475				mod = _g_dn_kps;
476#endif
477			else
478				mod = NULL;
479			c->name = mod ? mod->name : "NULL";
480			DX(3, "using scheduler %s", c->name);
481		} else if (!strcmp(*av, "-len")) {
482			c->lmin = getnum(av[1], NULL, av[0]);
483			c->lmax = c->lmin;
484			DX(3, "setting max to %d", c->th_max);
485#ifdef USE_BURST
486		} else if (!strcmp(*av, "-burst")) {
487			c->maxburst = getnum(av[1], NULL, av[0]);
488			DX(3, "setting max to %d", c->th_max);
489#endif /* USE_BURST */
490		} else if (!strcmp(*av, "-qmax")) {
491			c->th_max = getnum(av[1], NULL, av[0]);
492			DX(3, "setting max to %d", c->th_max);
493		} else if (!strcmp(*av, "-qmin")) {
494			c->th_min = getnum(av[1], NULL, av[0]);
495			DX(3, "setting min to %d", c->th_min);
496		} else if (!strcmp(*av, "-flows")) {
497			c->flows = getnum(av[1], NULL, av[0]);
498			DX(3, "setting flows to %d", c->flows);
499		} else if (!strcmp(*av, "-flowsets")) {
500			parse_flowsets(c, av[1]); /* first pass */
501			DX(3, "setting flowsets to %d", c->flowsets);
502		} else {
503			D("option %s not recognised, ignore", *av);
504		}
505		ac -= 2; av += 2;
506	}
507#ifdef USE_BURST
508	if (c->maxburst <= 0)
509		c->maxburst = 1;
510#endif /* USE_BURST */
511	if (c->loops <= 0)
512		c->loops = 1;
513	if (c->flows <= 0)
514		c->flows = 1;
515	if (c->flowsets <= 0)
516		c->flowsets = 1;
517	if (c->lmin <= 0)
518		c->lmin = 1;
519	if (c->lmax <= 0)
520		c->lmax = 1;
521	/* multiply by N */
522	if (c->th_min < 0)
523		c->th_min = c->flows * -c->th_min;
524	if (c->th_max < 0)
525		c->th_max = c->flows * -c->th_max;
526	if (c->th_max <= c->th_min)
527		c->th_max = c->th_min + 1;
528
529	/* now load parameters from the module */
530	if (mod) {
531		p = mod->p;
532		DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p);
533		DX(3, "modname %s ty %d", p->name, p->type);
534		// XXX check enq and deq not null
535		c->enq = p->enqueue;
536		c->deq = p->dequeue;
537		c->si_len += p->si_datalen;
538		c->q_len += p->q_datalen;
539		c->schk_len += p->schk_datalen;
540	} else {
541		/* make sure c->si has room for a queue */
542		c->enq = default_enqueue;
543		c->deq = default_dequeue;
544	}
545
546	/* allocate queues, flowsets and one scheduler */
547	D("using %d flows, %d flowsets", c->flows, c->flowsets);
548	D("q_len %d dn_fsk %d si %d sched %d",
549		c->q_len, (int)sizeof(struct dn_fsk),
550		c->si_len, c->schk_len);
551	c->sched = calloc(1, c->schk_len); /* one parent scheduler */
552	c->si = calloc(1, c->si_len); /* one scheduler instance */
553	c->fs = calloc(c->flowsets, sizeof(struct dn_fsk));
554	c->q = calloc(c->flows, c->q_len);	/* one queue per flow */
555	c->q_wfi = calloc(c->flows, sizeof(double)); /* stats, one per flow */
556	if (!c->sched || !c->si || !c->fs || !c->q || !c->q_wfi) {
557		D("error allocating memory");
558		exit(1);
559	}
560	c->si->sched = c->sched; /* link scheduler instance to template */
561	if (p) {
562		/* run initialization code if needed */
563		if (p->config)
564			p->config(c->si->sched);
565		if (p->new_sched)
566			p->new_sched(c->si);
567	}
568	/* parse_flowsets links queues to their flowsets */
569	parse_flowsets(c, NULL); /* second pass */
570	/* complete the work calling new_fsk */
571	for (i = 0; i < c->flowsets; i++) {
572		struct dn_fsk *fsk = &c->fs[i];
573		if (fsk->fs.par[1] == 0)
574			fsk->fs.par[1] = 1000;	/* default pkt len */
575		fsk->sched = c->si->sched;
576		if (p && p->new_fsk)
577			p->new_fsk(fsk);
578	}
579	/* --- now the scheduler is initialized --- */
580
581	/*
582	 * initialize the lists for the generator, and put
583	 * all flows in the list for backlog = 0
584	 */
585	for (i=0; i <= BACKLOG+5; i++)
586		INIT_LIST_HEAD(&c->ll[i]);
587
588	for (i = 0; i < c->flows; i++) {
589		struct dn_queue *q = FI2Q(c, i);
590		if (q->fs == NULL)
591			q->fs = &c->fs[0]; /* XXX */
592		q->_si = c->si;
593		if (p && p->new_queue)
594			p->new_queue(q);
595		INIT_LIST_HEAD(&q->ni.h);
596		list_add_tail(&q->ni.h, &c->ll[0]);
597	}
598	c->llmask = 1; /* all flows are in the first list */
599	return 0;
600}
601
602
603int
604main(int ac, char *av[])
605{
606	struct cfg_s c;
607	double ll;
608	int i;
609	char msg[40];
610
611	bzero(&c, sizeof(c));
612	c.ac = ac;
613	c.av = av;
614	init(&c);
615	gettimeofday(&c.time, NULL);
616	D("th_min %d th_max %d", c.th_min, c.th_max);
617
618	mainloop(&c);
619	{
620		struct timeval end;
621		gettimeofday(&end, NULL);
622		timersub(&end, &c.time, &c.time);
623	}
624	ll = c.time.tv_sec*1000000 + c.time.tv_usec;
625	ll *= 1000;	/* convert to nanoseconds */
626	ll /= c._enqueue;
627	sprintf(msg, "1::%d", c.flows);
628	for (i = 0; i < c.flows; i++) {
629		if (c.wfi < c.q_wfi[i])
630			c.wfi = c.q_wfi[i];
631	}
632	D("sched=%-12s\ttime=%d.%03d sec (%.0f nsec) enq %lu %lu deq\n"
633	   "\twfi=%.02f\tflow=%-16s",
634	   c.name, (int)c.time.tv_sec, (int)c.time.tv_usec / 1000, ll,
635	   (unsigned long)c._enqueue, (unsigned long)c.dequeue, c.wfi,
636	   c.fs_config ? c.fs_config : msg);
637	dump(&c);
638	DX(1, "done ac %d av %p", ac, av);
639	for (i=0; i < ac; i++)
640		DX(1, "arg %d %s", i, av[i]);
641	return 0;
642}
643
644/*
645 * The controller decides whether in this iteration we should send
646 * (the packet is in c->tosend) and/or receive (flag c->can_dequeue)
647 */
648static void
649controller(struct cfg_s *c)
650{
651	struct mbuf *m;
652	struct dn_fs *fs;
653	int flow_id;
654
655	/* hysteresis between max and min */
656	if (c->state == 0 && c->pending >= (uint32_t)c->th_max)
657		c->state = 1;
658	else if (c->state == 1 && c->pending <= (uint32_t)c->th_min)
659		c->state = 0;
660	ND(1, "state %d pending %2d", c->state, c->pending);
661	c->can_dequeue = c->state;
662	c->tosend = NULL;
663	if (c->can_dequeue)
664		return;
665
666	/*
667	 * locate the flow to use for enqueueing
668	 * We take the queue with the lowest number of queued packets,
669	 * generate a packet for it, and put the queue in the next highest.
670	 */
671    if (1) {
672	int i;
673	struct dn_queue *q;
674	struct list_head *h;
675
676	i = ffs(c->llmask) - 1;
677	if (i < 0) {
678		D("no candidate");
679		c->can_dequeue = 1;
680		return;
681	}
682	h = &c->ll[i];
683	ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next);
684	q = list_first_entry(h, struct dn_queue, ni.h);
685	list_del(&q->ni.h);
686	flow_id = Q2FI(c, q);
687	DX(2, "extracted flow %p %d backlog %d", q, flow_id, i);
688	if (list_empty(h)) {
689		ND(2, "backlog %d empty", i);
690		c->llmask &= ~(1<<i);
691	}
692	ND(1, "before %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next);
693	list_add_tail(&q->ni.h, h+1);
694	ND(1, " after %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next);
695	if (i < BACKLOG) {
696		ND(2, "backlog %d full", i+1);
697		c->llmask |= 1<<(1+i);
698	}
699	fs = &q->fs->fs;
700	fs->cur = flow_id;
701#ifdef USE_CUR
702	c->cur_fs = q->fs - c->fs;
703    } else {
704	/* XXX this does not work ? */
705	/* now decide whom to send the packet, and the length */
706	/* lookup in the flow table */
707	if (c->cur_y >= c->max_y) {	/* handle wraparound */
708		c->cur_y = 0;
709		c->cur_fs = 0;
710	}
711	fs = &c->fs[c->cur_fs].fs;
712	flow_id = fs->cur++;
713	if (fs->cur >= fs->next_flow)
714		fs->cur = fs->first_flow;
715	c->cur_y++;
716	if (c->cur_y >= fs->next_y)
717		c->cur_fs++;
718#endif /* USE_CUR */
719    }
720
721	/* construct a packet */
722	if (c->freelist) {
723		m = c->tosend = c->freelist;
724		c->freelist = c->freelist->m_nextpkt;
725	} else {
726		m = c->tosend = calloc(1, sizeof(struct mbuf));
727	}
728	if (m == NULL)
729		return;
730
731	//m->cfg = c;
732	m->m_nextpkt = NULL;
733	m->m_pkthdr.len = fs->par[1]; // XXX maxlen
734	m->flow_id = flow_id;
735
736	ND(2,"y %6d flow %5d fs %3d weight %4d len %4d",
737		c->cur_y, m->flow_id, c->cur_fs,
738		fs->par[0], m->m_pkthdr.len);
739
740}
741