test/main.c

   1 /*
   2  * $Id: main.c 5626 2010-03-04 21:55:22Z 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 #include "dn_test.h"
  13
  14 struct q_list {
  15         struct list_head h;
  16 };
  17
  18 struct 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
  86 int debug = 0;
  87
  88 struct dn_parms dn_cfg;
  89
  90 static 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  */
  95 int
  96 drop(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 */
 119 static int
 120 enqueue(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 */
 134 static void *
 135 dequeue(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
 148 static int
 149 mainloop(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
 182 int
 183 dump(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 */
 197 static long
 198 getnum(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  */
 251 static void
 252 parse_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
 347 static int
 348 init(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
 496 int
 497 main(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  */
 539 static void
 540 controller(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 /*
 627 Packet allocation:
 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.
 635
 636 */