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 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 */ 637