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