2 * $Id: main.c 5626 2010-03-04 21:55:22Z luigi $
4 * Testing program for schedulers
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.
26 /* running counters */
32 /* generator parameters */
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 */
43 int burst; /* count of packets sent in a burst */
44 struct mbuf *tosend; /* packet to send -- also flag to enqueue */
46 struct mbuf *freelist;
48 struct mbuf *head, *tail; /* a simple tailq */
51 int (*enq)(struct dn_sch_inst *, struct dn_queue *,
53 struct mbuf * (*deq)(struct dn_sch_inst *);
54 /* size of the three fields including sched-specific areas */
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;
65 int state; /* 0 = going up, 1: going down */
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.
77 struct list_head ll[BACKLOG + 10];
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.
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)
88 struct dn_parms dn_cfg;
90 static void controller(struct cfg_s *c);
92 /* release a packet: put the mbuf in the freelist, and the queue in
96 drop(struct cfg_s *c, struct mbuf *m)
102 q = FI2Q(c, m->flow_id);
103 i = q->ni.length; // XXX or ffs...
105 ND("q %p id %d current length %d", q, m->flow_id, i);
107 struct list_head *h = &q->ni.h;
108 c->llmask &= ~(1<<(i+1));
109 c->llmask |= (1<<(i));
111 list_add_tail(h, &c->ll[i]);
113 m->m_nextpkt = c->freelist;
118 /* dequeue returns NON-NULL when a packet is dropped */
120 enqueue(struct cfg_s *c, void *_m)
124 return c->enq(c->si, FI2Q(c, m->flow_id), m);
128 c->tail->m_nextpkt = m;
130 return 0; /* default - success */
133 /* dequeue returns NON-NULL when a packet is available */
135 dequeue(struct cfg_s *c)
139 return c->deq(c->si);
142 c->head = m->m_nextpkt;
149 mainloop(struct cfg_s *c)
154 for (i=0; i < c->loops; i++) {
155 /* implement histeresis */
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) ) {
163 ND("loop %d enqueue fail", i );
169 if (c->can_dequeue) {
171 if ((m = dequeue(c))) {
174 c->drop--; /* compensate */
178 DX(1, "mainloop ends %d", i);
183 dump(struct cfg_s *c)
188 for (i=0; i < c->flows; i++) {
190 DX(1, "queue %4d tot %10lld", i, q->ni.tot_bytes);
192 DX(1, "done %d loops\n", c->loops);
196 /* interpret a number in human form */
198 getnum(const char *s, char **next, const char *key)
203 if (next) /* default */
206 DX(3, "token is <%s> %s", s, key ? key : "-");
207 l = strtol(s, &end, 0);
209 DX(3, "empty string");
213 DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") );
219 l = -l; /* multiply by n */
220 else if (*end == 'K')
222 else if (*end == 'M')
224 else if (*end == 'k')
226 else if (*end == 'm')
228 else if (*end == 'w')
230 else {/* not recognized */
231 D("suffix %s for %s, next %p", end, key, next);
235 DX(3, "suffix now %s for %s, next %p", end, key, next);
237 DX(3, "setting next to %s for %s", end, key);
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.
252 parse_flowsets(struct cfg_s *c, const char *fs, int pass)
254 char *s, *cur, *next;
255 int n_flows = 0, n_fs = 0, wsum = 0;
257 struct dn_fs *prev = NULL;
259 DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets);
262 s = c->fs_config ? strdup(c->fs_config) : NULL;
268 for (next = s; (cur = strsep(&next, ","));) {
270 int w, w_h, w_steps, wi;
271 int len, len_h, l_steps, li;
274 w = getnum(strsep(&cur, ":"), &p, "weight");
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");
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");
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 ||
291 DX(4,"wrong parameters %s", fs);
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
301 li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1));
303 DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d",
304 n_fs, wi, li, x, flows);
307 if (c->fs == NULL || c->flowsets <= n_fs) {
308 D("error in number of flowsets");
316 fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow;
317 fs->next_flow = fs->first_flow + fs->n_flows;
319 fs->base_y = (prev == NULL) ? 0 : prev->next_y;
320 fs->next_y = fs->base_y + fs->y;
325 c->max_y = prev ? prev->base_y + prev->y : 0;
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);
348 init(struct cfg_s *c)
352 char * const *av = c->av;
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;
360 c->th_max = -20;/* 20 packets per flow */
361 c->lmin = c->lmax = 1280; /* packet len */
367 if (!strcmp(*av, "-n")) {
368 c->loops = getnum(av[1], NULL, av[0]);
369 } else if (!strcmp(*av, "-d")) {
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;
377 extern moduledata_t *_g_dn_kps;
379 if (!strcmp(av[1], "rr"))
381 else if (!strcmp(av[1], "wf2qp"))
383 else if (!strcmp(av[1], "fifo"))
385 else if (!strcmp(av[1], "qfq"))
388 else if (!strcmp(av[1], "kps"))
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]);
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);
415 D("option %s not recognised, ignore", *av);
419 if (c->maxburst <= 0)
425 if (c->flowsets <= 0)
433 c->th_min = c->flows * -c->th_min;
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;
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);
444 c->si_len += p->si_datalen;
445 c->q_len += p->q_datalen;
446 c->schk_len += p->schk_datalen;
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");
457 c->si->sched = c->sched;
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;
472 p->new_fsk(&c->fs[i]);
475 /* initialize the lists for the generator, and put
476 * all flows in the list for backlog = 0
478 for (i=0; i <= BACKLOG+5; i++)
479 INIT_LIST_HEAD(&c->ll[i]);
481 for (i = 0; i < c->flows; i++) {
482 struct dn_queue *q = FI2Q(c, i);
484 q->fs = &c->fs[0]; /* XXX */
486 if (p && p->new_queue)
488 INIT_LIST_HEAD(&q->ni.h);
489 list_add_tail(&q->ni.h, &c->ll[0]);
497 main(int ac, char *av[])
505 bzero(&c, sizeof(c));
509 gettimeofday(&c.time, NULL);
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;
519 ll = end.tv_sec*1000000 + end.tv_usec;
520 ll *= 1000; /* convert to nanoseconds */
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,
527 c.fs_config ? c.fs_config : msg, c.drop);
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]);
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)
540 controller(struct cfg_s *c)
546 /* histeresis between max and min */
547 if (c->state == 0 && c->pending >= c->th_max)
549 else if (c->state == 1 && c->pending <= c->th_min)
551 ND(1, "state %d pending %2d", c->state, c->pending);
552 c->can_dequeue = c->state;
562 i = ffs(c->llmask) - 1;
564 DX(2, "no candidate");
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);
572 flow_id = Q2FI(c, q);
573 DX(2, "extracted flow %p %d backlog %d", q, flow_id, i);
575 ND(2, "backlog %d empty", i);
576 c->llmask &= ~(1<<i);
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);
582 ND(2, "backlog %d full", i+1);
583 c->llmask |= 1<<(1+i);
586 c->cur_fs = q->fs - c->fs;
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 */
596 fs = &c->fs[c->cur_fs].fs;
598 if (fs->cur >= fs->next_flow)
599 fs->cur = fs->first_flow;
601 if (c->cur_y >= fs->next_y)
605 /* construct a packet */
607 m = c->tosend = c->freelist;
608 c->freelist = c->freelist->m_nextpkt;
610 m = c->tosend = calloc(1, sizeof(struct mbuf));
617 m->m_pkthdr.len = fs->par[1]; // XXX maxlen
618 m->flow_id = flow_id;
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);
628 to achieve a distribution that matches weights, for each X=w/lmax class
629 we should generate a number of packets proportional to Y = X times the number
630 of flows in the class.
631 So we construct an array with the cumulative distribution of Y's,
632 and use it to identify the flow via inverse mapping (if the Y's are
633 not too many we can use an array for the lookup). In practice,
634 each flow will have X entries [virtually] pointing to it.