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