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 double *q_wfi; /* (byte) Worst-case Fair Index of the flows */ 80 double wfi; /* (byte) Worst-case Fair Index of the system */ 81 }; 82 83 /* FI2Q and Q2FI converts from flow_id to dn_queue and back. 84 * We cannot easily use pointer arithmetic because it is variable size. 85 */ 86 #define FI2Q(c, i) ((struct dn_queue *)((c)->q + (c)->q_len * (i))) 87 #define Q2FI(c, q) (((char *)(q) - (c)->q)/(c)->q_len) 88 89 int debug = 0; 90 91 struct dn_parms dn_cfg; 92 93 static void controller(struct cfg_s *c); 94 95 /* release a packet: put the mbuf in the freelist, and the queue in 96 * the bucket. 97 */ 98 int 99 drop(struct cfg_s *c, struct mbuf *m) 100 { 101 struct dn_queue *q; 102 int i; 103 104 c->drop++; 105 q = FI2Q(c, m->flow_id); 106 i = q->ni.length; // XXX or ffs... 107 108 ND("q %p id %d current length %d", q, m->flow_id, i); 109 if (i < BACKLOG) { 110 struct list_head *h = &q->ni.h; 111 c->llmask &= ~(1<<(i+1)); 112 c->llmask |= (1<<(i)); 113 list_del(h); 114 list_add_tail(h, &c->ll[i]); 115 } 116 m->m_nextpkt = c->freelist; 117 c->freelist = m; 118 return 0; 119 } 120 121 /* dequeue returns NON-NULL when a packet is dropped */ 122 static int 123 enqueue(struct cfg_s *c, void *_m) 124 { 125 struct mbuf *m = _m; 126 if (c->enq) 127 return c->enq(c->si, FI2Q(c, m->flow_id), m); 128 if (c->head == NULL) 129 c->head = m; 130 else 131 c->tail->m_nextpkt = m; 132 c->tail = m; 133 return 0; /* default - success */ 134 } 135 136 /* dequeue returns NON-NULL when a packet is available */ 137 static void * 138 dequeue(struct cfg_s *c) 139 { 140 struct mbuf *m; 141 if (c->deq) 142 return c->deq(c->si); 143 if ((m = c->head)) { 144 m = c->head; 145 c->head = m->m_nextpkt; 146 m->m_nextpkt = NULL; 147 } 148 return m; 149 } 150 151 static void 152 gnet_stats_enq(struct cfg_s *c, struct mbuf *mb) 153 { 154 struct dn_sch_inst *si = c->si; 155 struct dn_queue *_q = FI2Q(c, mb->flow_id); 156 157 if (_q->ni.length == 1) { 158 _q->ni.bytes = 0; 159 _q->ni.sch_bytes = si->ni.bytes; 160 } 161 } 162 163 static void 164 gnet_stats_deq(struct cfg_s *c, struct mbuf *mb) 165 { 166 struct dn_sch_inst *si = c->si; 167 struct dn_queue *_q = FI2Q(c, mb->flow_id); 168 int len = mb->m_pkthdr.len; 169 170 _q->ni.bytes += len; 171 si->ni.bytes += len; 172 173 if (_q->ni.length == 0) { 174 double bytes = (double)_q->ni.bytes; 175 double sch_bytes = (double)si->ni.bytes - _q->ni.sch_bytes; 176 double weight = (double)_q->fs->fs.par[0] / c->wsum; 177 double wfi = sch_bytes * weight - bytes; 178 179 if (c->q_wfi[mb->flow_id] < wfi) 180 c->q_wfi[mb->flow_id] = wfi; 181 } 182 } 183 184 static int 185 mainloop(struct cfg_s *c) 186 { 187 int i; 188 struct mbuf *m; 189 190 for (i=0; i < c->loops; i++) { 191 /* implement histeresis */ 192 controller(c); 193 DX(3, "loop %d enq %d send %p rx %d", 194 i, c->_enqueue, c->tosend, c->can_dequeue); 195 if ( (m = c->tosend) ) { 196 c->_enqueue++; 197 if (enqueue(c, m)) { 198 drop(c, m); 199 ND("loop %d enqueue fail", i ); 200 } else { 201 ND("enqueue ok"); 202 c->pending++; 203 gnet_stats_enq(c, m); 204 } 205 } 206 if (c->can_dequeue) { 207 c->dequeue++; 208 if ((m = dequeue(c))) { 209 c->pending--; 210 drop(c, m); 211 c->drop--; /* compensate */ 212 gnet_stats_deq(c, m); 213 } 214 } 215 } 216 DX(1, "mainloop ends %d", i); 217 return 0; 218 } 219 220 int 221 dump(struct cfg_s *c) 222 { 223 int i; 224 struct dn_queue *q; 225 226 for (i=0; i < c->flows; i++) { 227 q = FI2Q(c, i); 228 DX(1, "queue %4d tot %10llu", i, 229 (unsigned long long)q->ni.tot_bytes); 230 } 231 DX(1, "done %d loops\n", c->loops); 232 return 0; 233 } 234 235 /* interpret a number in human form */ 236 static long 237 getnum(const char *s, char **next, const char *key) 238 { 239 char *end = NULL; 240 long l; 241 242 if (next) /* default */ 243 *next = NULL; 244 if (s && *s) { 245 DX(3, "token is <%s> %s", s, key ? key : "-"); 246 l = strtol(s, &end, 0); 247 } else { 248 DX(3, "empty string"); 249 l = -1; 250 } 251 if (l < 0) { 252 DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") ); 253 return 0; // invalid 254 } 255 if (!end || !*end) 256 return l; 257 if (*end == 'n') 258 l = -l; /* multiply by n */ 259 else if (*end == 'K') 260 l = l*1000; 261 else if (*end == 'M') 262 l = l*1000000; 263 else if (*end == 'k') 264 l = l*1024; 265 else if (*end == 'm') 266 l = l*1024*1024; 267 else if (*end == 'w') 268 ; 269 else {/* not recognized */ 270 D("suffix %s for %s, next %p", end, key, next); 271 end--; 272 } 273 end++; 274 DX(3, "suffix now %s for %s, next %p", end, key, next); 275 if (next && *end) { 276 DX(3, "setting next to %s for %s", end, key); 277 *next = end; 278 } 279 return l; 280 } 281 282 /* 283 * flowsets are a comma-separated list of 284 * weight:maxlen:flows 285 * indicating how many flows are hooked to that fs. 286 * Both weight and range can be min-max-steps. 287 * In a first pass we just count the number of flowsets and flows, 288 * in a second pass we complete the setup. 289 */ 290 static void 291 parse_flowsets(struct cfg_s *c, const char *fs, int pass) 292 { 293 char *s, *cur, *next; 294 int n_flows = 0, n_fs = 0, wsum = 0; 295 int i, j; 296 struct dn_fs *prev = NULL; 297 298 DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets); 299 if (pass == 0) 300 c->fs_config = fs; 301 s = c->fs_config ? strdup(c->fs_config) : NULL; 302 if (s == NULL) { 303 if (pass == 0) 304 D("no fsconfig"); 305 return; 306 } 307 for (next = s; (cur = strsep(&next, ","));) { 308 char *p = NULL; 309 int w, w_h, w_steps, wi; 310 int len, len_h, l_steps, li; 311 int flows; 312 313 w = getnum(strsep(&cur, ":"), &p, "weight"); 314 if (w <= 0) 315 w = 1; 316 w_h = p ? getnum(p+1, &p, "weight_max") : w; 317 w_steps = p ? getnum(p+1, &p, "w_steps") : (w_h == w ?1:2); 318 len = getnum(strsep(&cur, ":"), &p, "len"); 319 if (len <= 0) 320 len = 1000; 321 len_h = p ? getnum(p+1, &p, "len_max") : len; 322 l_steps = p ? getnum(p+1, &p, "l_steps") : (len_h == len ? 1 : 2); 323 flows = getnum(strsep(&cur, ":"), NULL, "flows"); 324 if (flows == 0) 325 flows = 1; 326 DX(4, "weight %d..%d (%d) len %d..%d (%d) flows %d", 327 w, w_h, w_steps, len, len_h, l_steps, flows); 328 if (w == 0 || w_h < w || len == 0 || len_h < len || 329 flows == 0) { 330 DX(4,"wrong parameters %s", fs); 331 return; 332 } 333 n_flows += flows * w_steps * l_steps; 334 for (i = 0; i < w_steps; i++) { 335 wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1)); 336 for (j = 0; j < l_steps; j++, n_fs++) { 337 struct dn_fs *fs = &c->fs[n_fs].fs; // tentative 338 int x; 339 340 li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1)); 341 x = (wi*2048)/li; 342 DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d", 343 n_fs, wi, li, x, flows); 344 if (pass == 0) 345 continue; 346 if (c->fs == NULL || c->flowsets <= n_fs) { 347 D("error in number of flowsets"); 348 return; 349 } 350 wsum += wi * flows; 351 fs->par[0] = wi; 352 fs->par[1] = li; 353 fs->index = n_fs; 354 fs->n_flows = flows; 355 fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow; 356 fs->next_flow = fs->first_flow + fs->n_flows; 357 fs->y = x * flows; 358 fs->base_y = (prev == NULL) ? 0 : prev->next_y; 359 fs->next_y = fs->base_y + fs->y; 360 prev = fs; 361 } 362 } 363 } 364 c->max_y = prev ? prev->base_y + prev->y : 0; 365 c->flows = n_flows; 366 c->flowsets = n_fs; 367 c->wsum = wsum; 368 if (pass == 0) 369 return; 370 371 /* now link all flows to their parent flowsets */ 372 DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y); 373 for (i=0; i < c->flowsets; i++) { 374 struct dn_fs *fs = &c->fs[i].fs; 375 DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d", 376 i, fs->par[0], fs->par[1], 377 fs->first_flow, fs->next_flow, 378 fs->base_y, fs->next_y); 379 for (j = fs->first_flow; j < fs->next_flow; j++) { 380 struct dn_queue *q = FI2Q(c, j); 381 q->fs = &c->fs[i]; 382 } 383 } 384 } 385 386 static int 387 init(struct cfg_s *c) 388 { 389 int i; 390 int ac = c->ac; 391 char * const *av = c->av; 392 393 c->si_len = sizeof(struct dn_sch_inst); 394 c->q_len = sizeof(struct dn_queue); 395 moduledata_t *mod = NULL; 396 struct dn_alg *p = NULL; 397 398 c->th_min = 0; 399 c->th_max = -20;/* 20 packets per flow */ 400 c->lmin = c->lmax = 1280; /* packet len */ 401 c->flows = 1; 402 c->flowsets = 1; 403 c->name = "null"; 404 ac--; av++; 405 while (ac > 1) { 406 if (!strcmp(*av, "-n")) { 407 c->loops = getnum(av[1], NULL, av[0]); 408 } else if (!strcmp(*av, "-d")) { 409 debug = atoi(av[1]); 410 } else if (!strcmp(*av, "-alg")) { 411 extern moduledata_t *_g_dn_fifo; 412 extern moduledata_t *_g_dn_wf2qp; 413 extern moduledata_t *_g_dn_rr; 414 extern moduledata_t *_g_dn_qfq; 415 #ifdef WITH_QFQP 416 extern moduledata_t *_g_dn_qfqp; 417 #endif 418 #ifdef WITH_KPS 419 extern moduledata_t *_g_dn_kps; 420 #endif 421 if (!strcmp(av[1], "rr")) 422 mod = _g_dn_rr; 423 else if (!strcmp(av[1], "wf2qp")) 424 mod = _g_dn_wf2qp; 425 else if (!strcmp(av[1], "fifo")) 426 mod = _g_dn_fifo; 427 else if (!strcmp(av[1], "qfq")) 428 mod = _g_dn_qfq; 429 #ifdef WITH_QFQP 430 else if (!strcmp(av[1], "qfq+") || 431 !strcmp(av[1], "qfqp") ) 432 mod = _g_dn_qfqp; 433 #endif 434 #ifdef WITH_KPS 435 else if (!strcmp(av[1], "kps")) 436 mod = _g_dn_kps; 437 #endif 438 else 439 mod = NULL; 440 c->name = mod ? mod->name : "NULL"; 441 DX(3, "using scheduler %s", c->name); 442 } else if (!strcmp(*av, "-len")) { 443 c->lmin = getnum(av[1], NULL, av[0]); 444 c->lmax = c->lmin; 445 DX(3, "setting max to %d", c->th_max); 446 } else if (!strcmp(*av, "-burst")) { 447 c->maxburst = getnum(av[1], NULL, av[0]); 448 DX(3, "setting max to %d", c->th_max); 449 } else if (!strcmp(*av, "-qmax")) { 450 c->th_max = getnum(av[1], NULL, av[0]); 451 DX(3, "setting max to %d", c->th_max); 452 } else if (!strcmp(*av, "-qmin")) { 453 c->th_min = getnum(av[1], NULL, av[0]); 454 DX(3, "setting min to %d", c->th_min); 455 } else if (!strcmp(*av, "-flows")) { 456 c->flows = getnum(av[1], NULL, av[0]); 457 DX(3, "setting flows to %d", c->flows); 458 } else if (!strcmp(*av, "-flowsets")) { 459 parse_flowsets(c, av[1], 0); 460 DX(3, "setting flowsets to %d", c->flowsets); 461 } else { 462 D("option %s not recognised, ignore", *av); 463 } 464 ac -= 2; av += 2; 465 } 466 if (c->maxburst <= 0) 467 c->maxburst = 1; 468 if (c->loops <= 0) 469 c->loops = 1; 470 if (c->flows <= 0) 471 c->flows = 1; 472 if (c->flowsets <= 0) 473 c->flowsets = 1; 474 if (c->lmin <= 0) 475 c->lmin = 1; 476 if (c->lmax <= 0) 477 c->lmax = 1; 478 /* multiply by N */ 479 if (c->th_min < 0) 480 c->th_min = c->flows * -c->th_min; 481 if (c->th_max < 0) 482 c->th_max = c->flows * -c->th_max; 483 if (c->th_max <= c->th_min) 484 c->th_max = c->th_min + 1; 485 if (mod) { 486 p = mod->p; 487 DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p); 488 DX(3, "modname %s ty %d", p->name, p->type); 489 c->enq = p->enqueue; 490 c->deq = p->dequeue; 491 c->si_len += p->si_datalen; 492 c->q_len += p->q_datalen; 493 c->schk_len += p->schk_datalen; 494 } 495 /* allocate queues, flowsets and one scheduler */ 496 c->q = calloc(c->flows, c->q_len); 497 c->q_wfi = (double *)calloc(c->flows, sizeof(double)); 498 c->fs = calloc(c->flowsets, sizeof(struct dn_fsk)); 499 c->si = calloc(1, c->si_len); 500 c->sched = calloc(c->flows, c->schk_len); 501 if (c->q == NULL || c->fs == NULL || !c->q_wfi) { 502 D("error allocating memory for flows"); 503 exit(1); 504 } 505 c->si->sched = c->sched; 506 if (p) { 507 if (p->config) 508 p->config(c->sched); 509 if (p->new_sched) 510 p->new_sched(c->si); 511 } 512 /* parse_flowsets links queues to their flowsets */ 513 parse_flowsets(c, av[1], 1); 514 /* complete the work calling new_fsk */ 515 for (i = 0; i < c->flowsets; i++) { 516 if (c->fs[i].fs.par[1] == 0) 517 c->fs[i].fs.par[1] = 1000; /* default pkt len */ 518 c->fs[i].sched = c->sched; 519 if (p && p->new_fsk) 520 p->new_fsk(&c->fs[i]); 521 } 522 523 /* initialize the lists for the generator, and put 524 * all flows in the list for backlog = 0 525 */ 526 for (i=0; i <= BACKLOG+5; i++) 527 INIT_LIST_HEAD(&c->ll[i]); 528 529 for (i = 0; i < c->flows; i++) { 530 struct dn_queue *q = FI2Q(c, i); 531 if (q->fs == NULL) 532 q->fs = &c->fs[0]; /* XXX */ 533 q->_si = c->si; 534 if (p && p->new_queue) 535 p->new_queue(q); 536 INIT_LIST_HEAD(&q->ni.h); 537 list_add_tail(&q->ni.h, &c->ll[0]); 538 } 539 c->llmask = 1; 540 return 0; 541 } 542 543 544 int 545 main(int ac, char *av[]) 546 { 547 struct cfg_s c; 548 struct timeval end; 549 double ll; 550 int i; 551 char msg[40]; 552 553 bzero(&c, sizeof(c)); 554 c.ac = ac; 555 c.av = av; 556 init(&c); 557 gettimeofday(&c.time, NULL); 558 mainloop(&c); 559 gettimeofday(&end, NULL); 560 end.tv_sec -= c.time.tv_sec; 561 end.tv_usec -= c.time.tv_usec; 562 if (end.tv_usec < 0) { 563 end.tv_usec += 1000000; 564 end.tv_sec--; 565 } 566 c.time = end; 567 ll = end.tv_sec*1000000 + end.tv_usec; 568 ll *= 1000; /* convert to nanoseconds */ 569 ll /= c._enqueue; 570 sprintf(msg, "1::%d", c.flows); 571 for (i = 0; i < c.flows; i++) { 572 if (c.wfi < c.q_wfi[i]) 573 c.wfi = c.q_wfi[i]; 574 } 575 D("sched=%-12s\ttime=%d.%03d sec (%.0f nsec)\twfi=%.02f\tflow=%-16s", 576 c.name, (int)c.time.tv_sec, (int)c.time.tv_usec / 1000, ll, c.wfi, 577 c.fs_config ? c.fs_config : msg); 578 dump(&c); 579 DX(1, "done ac %d av %p", ac, av); 580 for (i=0; i < ac; i++) 581 DX(1, "arg %d %s", i, av[i]); 582 return 0; 583 } 584 585 /* 586 * The controller decides whether in this iteration we should send 587 * (the packet is in c->tosend) and/or receive (flag c->can_dequeue) 588 */ 589 static void 590 controller(struct cfg_s *c) 591 { 592 struct mbuf *m; 593 struct dn_fs *fs; 594 int flow_id; 595 596 /* histeresis between max and min */ 597 if (c->state == 0 && c->pending >= c->th_max) 598 c->state = 1; 599 else if (c->state == 1 && c->pending <= c->th_min) 600 c->state = 0; 601 ND(1, "state %d pending %2d", c->state, c->pending); 602 c->can_dequeue = c->state; 603 c->tosend = NULL; 604 if (c->state) 605 return; 606 607 if (1) { 608 int i; 609 struct dn_queue *q; 610 struct list_head *h; 611 612 i = ffs(c->llmask) - 1; 613 if (i < 0) { 614 DX(2, "no candidate"); 615 c->can_dequeue = 1; 616 return; 617 } 618 h = &c->ll[i]; 619 ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next); 620 q = list_first_entry(h, struct dn_queue, ni.h); 621 list_del(&q->ni.h); 622 flow_id = Q2FI(c, q); 623 DX(2, "extracted flow %p %d backlog %d", q, flow_id, i); 624 if (list_empty(h)) { 625 ND(2, "backlog %d empty", i); 626 c->llmask &= ~(1<<i); 627 } 628 ND(1, "before %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); 629 list_add_tail(&q->ni.h, h+1); 630 ND(1, " after %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); 631 if (i < BACKLOG) { 632 ND(2, "backlog %d full", i+1); 633 c->llmask |= 1<<(1+i); 634 } 635 fs = &q->fs->fs; 636 c->cur_fs = q->fs - c->fs; 637 fs->cur = flow_id; 638 } else { 639 /* XXX this does not work ? */ 640 /* now decide whom to send the packet, and the length */ 641 /* lookup in the flow table */ 642 if (c->cur_y >= c->max_y) { /* handle wraparound */ 643 c->cur_y = 0; 644 c->cur_fs = 0; 645 } 646 fs = &c->fs[c->cur_fs].fs; 647 flow_id = fs->cur++; 648 if (fs->cur >= fs->next_flow) 649 fs->cur = fs->first_flow; 650 c->cur_y++; 651 if (c->cur_y >= fs->next_y) 652 c->cur_fs++; 653 } 654 655 /* construct a packet */ 656 if (c->freelist) { 657 m = c->tosend = c->freelist; 658 c->freelist = c->freelist->m_nextpkt; 659 } else { 660 m = c->tosend = calloc(1, sizeof(struct mbuf)); 661 } 662 if (m == NULL) 663 return; 664 665 m->cfg = c; 666 m->m_nextpkt = NULL; 667 m->m_pkthdr.len = fs->par[1]; // XXX maxlen 668 m->flow_id = flow_id; 669 670 ND(2,"y %6d flow %5d fs %3d weight %4d len %4d", 671 c->cur_y, m->flow_id, c->cur_fs, 672 fs->par[0], m->m_pkthdr.len); 673 674 } 675 676 /* 677 Packet allocation: 678 to achieve a distribution that matches weights, for each X=w/lmax class 679 we should generate a number of packets proportional to Y = X times the number 680 of flows in the class. 681 So we construct an array with the cumulative distribution of Y's, 682 and use it to identify the flow via inverse mapping (if the Y's are 683 not too many we can use an array for the lookup). In practice, 684 each flow will have X entries [virtually] pointing to it. 685 686 */ 687