Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/netpfil/ipfw/test/main.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
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 // #define USE_BURST // what is this for ? 13 14 #include "dn_test.h" 15 16 struct cfg_s { 17 int ac; 18 char * const *av; 19 20 const char *name; 21 int loops; 22 struct timeval time; 23 24 /* running counters */ 25 uint32_t _enqueue; 26 uint32_t drop; 27 uint32_t pending; 28 uint32_t dequeue; 29 30 /* generator parameters */ 31 int32_t th_min, th_max; /* thresholds for hysteresis; negative means per flow */ 32 #ifdef USE_BURST 33 int maxburst; 34 #endif /* USE_BURST */ 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 #ifdef USE_CUR 40 int max_y; /* max random number in the generation */ 41 int cur_y 42 int cur_fs; /* used in generation, between 0 and max_y - 1 */ 43 #endif /* USE_CUR */ 44 const char *fs_config; /* flowset config */ 45 int can_dequeue; 46 int burst; /* count of packets sent in a burst */ 47 struct mbuf *tosend; /* packet to send -- also flag to enqueue */ 48 49 struct mbuf *freelist; 50 51 struct mbuf *head, *tail; /* a simple tailq */ 52 53 /* scheduler hooks */ 54 int (*enq)(struct dn_sch_inst *, struct dn_queue *, 55 struct mbuf *); 56 struct mbuf * (*deq)(struct dn_sch_inst *); 57 /* size of the three fields including sched-specific areas */ 58 uint32_t schk_len; 59 uint32_t q_len; /* size of a queue including sched-fields */ 60 uint32_t si_len; /* size of a sch_inst including sched-fields */ 61 char *q; /* array of flow queues */ 62 /* use a char* because size is variable */ 63 /* 64 * The scheduler template (one) followd by schk_datalen bytes 65 * for scheduler-specific parameters, total size is schk_len 66 */ 67 struct dn_schk *sched; 68 /* 69 * one scheduler instance, followed by si_datalen bytes 70 * for scheduler specific parameters of this instance, 71 * total size is si_len. si->sched points to sched 72 */ 73 struct dn_sch_inst *si; 74 struct dn_fsk *fs; /* array of flowsets */ 75 76 /* generator state */ 77 int state; /* 0 = going up (enqueue), 1: going down (dequeue) */ 78 79 /* 80 * We keep lists for each backlog level, and always serve 81 * the one with shortest backlog. llmask contains a bitmap 82 * of lists, and ll are the heads of the lists. The last 83 * entry (BACKLOG) contains all entries considered 'full' 84 * XXX to optimize things, entry i could contain queues with 85 * 2^{i-1}+1 .. 2^i entries. 86 */ 87 #define BACKLOG 30 /* this many backlogged classes, we only need BACKLOG+1 */ 88 uint64_t llmask; 89 struct list_head ll[BACKLOG + 10]; 90 91 double *q_wfi; /* (byte) Worst-case Fair Index of the flows */ 92 double wfi; /* (byte) Worst-case Fair Index of the system */ 93 }; 94 95 /* FI2Q and Q2FI converts from flow_id (i.e. queue index) 96 * to dn_queue and back. We cannot simply use pointer arithmetic 97 * because the queu has variable size, q_len 98 */ 99 #define FI2Q(c, i) ((struct dn_queue *)((c)->q + (c)->q_len * (i))) 100 #define Q2FI(c, q) (((char *)(q) - (c)->q)/(c)->q_len) 101 102 int debug = 0; 103 104 struct dn_parms dn_cfg; 105 106 static void controller(struct cfg_s *c); 107 108 /* release a packet for a given flow_id. 109 * Put the mbuf in the freelist, and in case move the 110 * flow to the end of the bucket. 111 */ 112 static int 113 drop(struct cfg_s *c, struct mbuf *m) 114 { 115 struct dn_queue *q; 116 int i; 117 118 c->drop++; 119 q = FI2Q(c, m->flow_id); 120 i = q->ni.length; // XXX or ffs... 121 122 ND("q %p id %d current length %d", q, m->flow_id, i); 123 if (i < BACKLOG) { 124 struct list_head *h = &q->ni.h; 125 c->llmask &= ~(1<<(i+1)); 126 c->llmask |= (1<<(i)); 127 list_del(h); 128 list_add_tail(h, &c->ll[i]); 129 } 130 m->m_nextpkt = c->freelist; 131 c->freelist = m; 132 return 0; 133 } 134 135 /* 136 * dn_sch_inst does not have a queue, for the RR we 137 * allocate a mq right after si 138 */ 139 static int 140 default_enqueue(struct dn_sch_inst *si, struct dn_queue *q, struct mbuf *m) 141 { 142 struct mq *mq = (struct mq *)si; 143 144 (void)q; 145 /* this is the default function if no scheduler is provided */ 146 if (mq->head == NULL) 147 mq->head = m; 148 else 149 mq->tail->m_nextpkt = m; 150 mq->tail = m; 151 return 0; /* default - success */ 152 } 153 154 static struct mbuf * 155 default_dequeue(struct dn_sch_inst *si) 156 { 157 struct mq *mq = (struct mq *)si; 158 struct mbuf *m; 159 /* this is the default function if no scheduler is provided */ 160 if ((m = mq->head)) { 161 m = mq->head; 162 mq->head = m->m_nextpkt; 163 m->m_nextpkt = NULL; 164 } 165 return m; 166 } 167 168 static void 169 gnet_stats_enq(struct cfg_s *c, struct mbuf *mb) 170 { 171 struct dn_sch_inst *si = c->si; 172 struct dn_queue *_q = FI2Q(c, mb->flow_id); 173 174 if (_q->ni.length == 1) { 175 _q->ni.bytes = 0; 176 _q->ni.sch_bytes = si->ni.bytes; 177 } 178 } 179 180 static void 181 gnet_stats_deq(struct cfg_s *c, struct mbuf *mb) 182 { 183 struct dn_sch_inst *si = c->si; 184 struct dn_queue *_q = FI2Q(c, mb->flow_id); 185 int len = mb->m_pkthdr.len; 186 187 _q->ni.bytes += len; 188 si->ni.bytes += len; 189 190 if (_q->ni.length == 0) { 191 double bytes = (double)_q->ni.bytes; 192 double sch_bytes = (double)si->ni.bytes - _q->ni.sch_bytes; 193 double weight = (double)_q->fs->fs.par[0] / c->wsum; 194 double wfi = sch_bytes * weight - bytes; 195 196 if (c->q_wfi[mb->flow_id] < wfi) 197 c->q_wfi[mb->flow_id] = wfi; 198 } 199 } 200 201 static int 202 mainloop(struct cfg_s *c) 203 { 204 int i; 205 struct mbuf *m; 206 207 for (i=0; i < c->loops; i++) { 208 /* implement histeresis */ 209 controller(c); 210 DX(3, "loop %d enq %d send %p rx %d", 211 i, c->_enqueue, c->tosend, c->can_dequeue); 212 if ( (m = c->tosend) ) { 213 int ret; 214 struct dn_queue *q = FI2Q(c, m->flow_id); 215 c->_enqueue++; 216 ret = c->enq(c->si, q, m); 217 if (ret) { 218 drop(c, m); 219 D("loop %d enqueue fail", i ); 220 /* 221 * XXX do not insist; rather, try dequeue 222 */ 223 goto do_dequeue; 224 } else { 225 ND("enqueue ok"); 226 c->pending++; 227 gnet_stats_enq(c, m); 228 } 229 } else if (c->can_dequeue) { 230 do_dequeue: 231 c->dequeue++; 232 m = c->deq(c->si); 233 if (m) { 234 c->pending--; 235 drop(c, m); 236 c->drop--; /* compensate */ 237 gnet_stats_deq(c, m); 238 } else { 239 D("--- ouch, cannot operate on iteration %d, pending %d", i, c->pending); 240 break; 241 } 242 } 243 } 244 DX(1, "mainloop ends %d", i); 245 return 0; 246 } 247 248 int 249 dump(struct cfg_s *c) 250 { 251 int i; 252 253 for (i=0; i < c->flows; i++) { 254 //struct dn_queue *q = FI2Q(c, i); 255 ND(1, "queue %4d tot %10llu", i, 256 (unsigned long long)q->ni.tot_bytes); 257 } 258 DX(1, "done %d loops\n", c->loops); 259 return 0; 260 } 261 262 /* interpret a number in human form */ 263 static long 264 getnum(const char *s, char **next, const char *key) 265 { 266 char *end = NULL; 267 long l; 268 269 if (next) /* default */ 270 *next = NULL; 271 if (s && *s) { 272 DX(3, "token is <%s> %s", s, key ? key : "-"); 273 l = strtol(s, &end, 0); 274 } else { 275 DX(3, "empty string"); 276 l = -1; 277 } 278 if (l < 0) { 279 DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") ); 280 return 0; // invalid 281 } 282 if (!end || !*end) 283 return l; 284 if (*end == 'n') 285 l = -l; /* multiply by n */ 286 else if (*end == 'K') 287 l = l*1000; 288 else if (*end == 'M') 289 l = l*1000000; 290 else if (*end == 'k') 291 l = l*1024; 292 else if (*end == 'm') 293 l = l*1024*1024; 294 else if (*end == 'w') 295 ; 296 else {/* not recognized */ 297 D("suffix %s for %s, next %p", end, key, next); 298 end--; 299 } 300 end++; 301 DX(3, "suffix now %s for %s, next %p", end, key, next); 302 if (next && *end) { 303 DX(3, "setting next to %s for %s", end, key); 304 *next = end; 305 } 306 return l; 307 } 308 309 /* 310 * flowsets are a comma-separated list of 311 * weight:maxlen:flows 312 * indicating how many flows are hooked to that fs. 313 * Both weight and range can be min-max-steps. 314 * The first pass (fs != NULL) justs count the number of flowsets and flows, 315 * the second pass (fs == NULL) we complete the setup. 316 */ 317 static void 318 parse_flowsets(struct cfg_s *c, const char *fs) 319 { 320 char *s, *cur, *next; 321 int n_flows = 0, n_fs = 0, wsum = 0; 322 int i, j; 323 struct dn_fs *prev = NULL; 324 int pass = (fs == NULL); 325 326 DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets); 327 if (fs != NULL) { /* first pass */ 328 if (c->fs_config) 329 D("warning, overwriting fs %s with %s", 330 c->fs_config, fs); 331 c->fs_config = fs; 332 } 333 s = c->fs_config ? strdup(c->fs_config) : NULL; 334 if (s == NULL) { 335 if (pass == 0) 336 D("no fsconfig"); 337 return; 338 } 339 for (next = s; (cur = strsep(&next, ","));) { 340 char *p = NULL; 341 int w, w_h, w_steps, wi; 342 int len, len_h, l_steps, li; 343 int flows; 344 345 w = getnum(strsep(&cur, ":"), &p, "weight"); 346 if (w <= 0) 347 w = 1; 348 w_h = p ? getnum(p+1, &p, "weight_max") : w; 349 w_steps = p ? getnum(p+1, &p, "w_steps") : (w_h == w ?1:2); 350 len = getnum(strsep(&cur, ":"), &p, "len"); 351 if (len <= 0) 352 len = 1000; 353 len_h = p ? getnum(p+1, &p, "len_max") : len; 354 l_steps = p ? getnum(p+1, &p, "l_steps") : (len_h == len ? 1 : 2); 355 flows = getnum(strsep(&cur, ":"), NULL, "flows"); 356 if (flows == 0) 357 flows = 1; 358 DX(4, "weight %d..%d (%d) len %d..%d (%d) flows %d", 359 w, w_h, w_steps, len, len_h, l_steps, flows); 360 if (w == 0 || w_h < w || len == 0 || len_h < len || 361 flows == 0) { 362 DX(4,"wrong parameters %s", s); 363 return; 364 } 365 n_flows += flows * w_steps * l_steps; 366 for (i = 0; i < w_steps; i++) { 367 wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1)); 368 for (j = 0; j < l_steps; j++, n_fs++) { 369 struct dn_fs *fs = &c->fs[n_fs].fs; // tentative 370 int x; 371 372 li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1)); 373 x = (wi*2048)/li; 374 DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d", 375 n_fs, wi, li, x, flows); 376 if (pass == 0) 377 continue; 378 if (c->fs == NULL || c->flowsets <= n_fs) { 379 D("error in number of flowsets"); 380 return; 381 } 382 wsum += wi * flows; 383 fs->par[0] = wi; 384 fs->par[1] = li; 385 fs->index = n_fs; 386 fs->n_flows = flows; 387 fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow; 388 fs->next_flow = fs->first_flow + fs->n_flows; 389 fs->y = x * flows; 390 fs->base_y = (prev == NULL) ? 0 : prev->next_y; 391 fs->next_y = fs->base_y + fs->y; 392 prev = fs; 393 } 394 } 395 } 396 c->flows = n_flows; 397 c->flowsets = n_fs; 398 c->wsum = wsum; 399 if (pass == 0) 400 return; 401 402 /* now link all flows to their parent flowsets */ 403 DX(1,"%d flows on %d flowsets", c->flows, c->flowsets); 404 #ifdef USE_CUR 405 c->max_y = prev ? prev->base_y + prev->y : 0; 406 DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y); 407 #endif /* USE_CUR */ 408 for (i=0; i < c->flowsets; i++) { 409 struct dn_fs *fs = &c->fs[i].fs; 410 DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d", 411 i, fs->par[0], fs->par[1], 412 fs->first_flow, fs->next_flow, 413 fs->base_y, fs->next_y); 414 for (j = fs->first_flow; j < fs->next_flow; j++) { 415 struct dn_queue *q = FI2Q(c, j); 416 q->fs = &c->fs[i]; 417 } 418 } 419 } 420 421 /* available schedulers */ 422 extern moduledata_t *_g_dn_fifo; 423 extern moduledata_t *_g_dn_wf2qp; 424 extern moduledata_t *_g_dn_rr; 425 extern moduledata_t *_g_dn_qfq; 426 #ifdef WITH_QFQP 427 extern moduledata_t *_g_dn_qfqp; 428 #endif 429 #ifdef WITH_KPS 430 extern moduledata_t *_g_dn_kps; 431 #endif 432 433 static int 434 init(struct cfg_s *c) 435 { 436 int i; 437 int ac = c->ac; 438 char * const *av = c->av; 439 440 c->si_len = sizeof(struct dn_sch_inst); 441 c->q_len = sizeof(struct dn_queue); 442 moduledata_t *mod = NULL; 443 struct dn_alg *p = NULL; 444 445 c->th_min = -1; /* 1 packet per flow */ 446 c->th_max = -20;/* 20 packets per flow */ 447 c->lmin = c->lmax = 1280; /* packet len */ 448 c->flows = 1; 449 c->flowsets = 1; 450 c->name = "null"; 451 ac--; av++; 452 while (ac > 1) { 453 if (!strcmp(*av, "-n")) { 454 c->loops = getnum(av[1], NULL, av[0]); 455 } else if (!strcmp(*av, "-d")) { 456 debug = atoi(av[1]); 457 } else if (!strcmp(*av, "-alg")) { 458 if (!strcmp(av[1], "rr")) 459 mod = _g_dn_rr; 460 else if (!strcmp(av[1], "wf2qp")) 461 mod = _g_dn_wf2qp; 462 else if (!strcmp(av[1], "fifo")) 463 mod = _g_dn_fifo; 464 else if (!strcmp(av[1], "qfq")) 465 mod = _g_dn_qfq; 466 #ifdef WITH_QFQP 467 else if (!strcmp(av[1], "qfq+") || 468 !strcmp(av[1], "qfqp") ) 469 mod = _g_dn_qfqp; 470 #endif 471 #ifdef WITH_KPS 472 else if (!strcmp(av[1], "kps")) 473 mod = _g_dn_kps; 474 #endif 475 else 476 mod = NULL; 477 c->name = mod ? mod->name : "NULL"; 478 DX(3, "using scheduler %s", c->name); 479 } else if (!strcmp(*av, "-len")) { 480 c->lmin = getnum(av[1], NULL, av[0]); 481 c->lmax = c->lmin; 482 DX(3, "setting max to %d", c->th_max); 483 #ifdef USE_BURST 484 } else if (!strcmp(*av, "-burst")) { 485 c->maxburst = getnum(av[1], NULL, av[0]); 486 DX(3, "setting max to %d", c->th_max); 487 #endif /* USE_BURST */ 488 } else if (!strcmp(*av, "-qmax")) { 489 c->th_max = getnum(av[1], NULL, av[0]); 490 DX(3, "setting max to %d", c->th_max); 491 } else if (!strcmp(*av, "-qmin")) { 492 c->th_min = getnum(av[1], NULL, av[0]); 493 DX(3, "setting min to %d", c->th_min); 494 } else if (!strcmp(*av, "-flows")) { 495 c->flows = getnum(av[1], NULL, av[0]); 496 DX(3, "setting flows to %d", c->flows); 497 } else if (!strcmp(*av, "-flowsets")) { 498 parse_flowsets(c, av[1]); /* first pass */ 499 DX(3, "setting flowsets to %d", c->flowsets); 500 } else { 501 D("option %s not recognised, ignore", *av); 502 } 503 ac -= 2; av += 2; 504 } 505 #ifdef USE_BURST 506 if (c->maxburst <= 0) 507 c->maxburst = 1; 508 #endif /* USE_BURST */ 509 if (c->loops <= 0) 510 c->loops = 1; 511 if (c->flows <= 0) 512 c->flows = 1; 513 if (c->flowsets <= 0) 514 c->flowsets = 1; 515 if (c->lmin <= 0) 516 c->lmin = 1; 517 if (c->lmax <= 0) 518 c->lmax = 1; 519 /* multiply by N */ 520 if (c->th_min < 0) 521 c->th_min = c->flows * -c->th_min; 522 if (c->th_max < 0) 523 c->th_max = c->flows * -c->th_max; 524 if (c->th_max <= c->th_min) 525 c->th_max = c->th_min + 1; 526 527 /* now load parameters from the module */ 528 if (mod) { 529 p = mod->p; 530 DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p); 531 DX(3, "modname %s ty %d", p->name, p->type); 532 // XXX check enq and deq not null 533 c->enq = p->enqueue; 534 c->deq = p->dequeue; 535 c->si_len += p->si_datalen; 536 c->q_len += p->q_datalen; 537 c->schk_len += p->schk_datalen; 538 } else { 539 /* make sure c->si has room for a queue */ 540 c->enq = default_enqueue; 541 c->deq = default_dequeue; 542 } 543 544 /* allocate queues, flowsets and one scheduler */ 545 D("using %d flows, %d flowsets", c->flows, c->flowsets); 546 D("q_len %d dn_fsk %d si %d sched %d", 547 c->q_len, (int)sizeof(struct dn_fsk), 548 c->si_len, c->schk_len); 549 c->sched = calloc(1, c->schk_len); /* one parent scheduler */ 550 c->si = calloc(1, c->si_len); /* one scheduler instance */ 551 c->fs = calloc(c->flowsets, sizeof(struct dn_fsk)); 552 c->q = calloc(c->flows, c->q_len); /* one queue per flow */ 553 c->q_wfi = calloc(c->flows, sizeof(double)); /* stats, one per flow */ 554 if (!c->sched || !c->si || !c->fs || !c->q || !c->q_wfi) { 555 D("error allocating memory"); 556 exit(1); 557 } 558 c->si->sched = c->sched; /* link scheduler instance to template */ 559 if (p) { 560 /* run initialization code if needed */ 561 if (p->config) 562 p->config(c->si->sched); 563 if (p->new_sched) 564 p->new_sched(c->si); 565 } 566 /* parse_flowsets links queues to their flowsets */ 567 parse_flowsets(c, NULL); /* second pass */ 568 /* complete the work calling new_fsk */ 569 for (i = 0; i < c->flowsets; i++) { 570 struct dn_fsk *fsk = &c->fs[i]; 571 if (fsk->fs.par[1] == 0) 572 fsk->fs.par[1] = 1000; /* default pkt len */ 573 fsk->sched = c->si->sched; 574 if (p && p->new_fsk) 575 p->new_fsk(fsk); 576 } 577 /* --- now the scheduler is initialized --- */ 578 579 /* 580 * initialize the lists for the generator, and put 581 * all flows in the list for backlog = 0 582 */ 583 for (i=0; i <= BACKLOG+5; i++) 584 INIT_LIST_HEAD(&c->ll[i]); 585 586 for (i = 0; i < c->flows; i++) { 587 struct dn_queue *q = FI2Q(c, i); 588 if (q->fs == NULL) 589 q->fs = &c->fs[0]; /* XXX */ 590 q->_si = c->si; 591 if (p && p->new_queue) 592 p->new_queue(q); 593 INIT_LIST_HEAD(&q->ni.h); 594 list_add_tail(&q->ni.h, &c->ll[0]); 595 } 596 c->llmask = 1; /* all flows are in the first list */ 597 return 0; 598 } 599 600 int 601 main(int ac, char *av[]) 602 { 603 struct cfg_s c; 604 double ll; 605 int i; 606 char msg[40]; 607 608 bzero(&c, sizeof(c)); 609 c.ac = ac; 610 c.av = av; 611 init(&c); 612 gettimeofday(&c.time, NULL); 613 D("th_min %d th_max %d", c.th_min, c.th_max); 614 615 mainloop(&c); 616 { 617 struct timeval end; 618 gettimeofday(&end, NULL); 619 timersub(&end, &c.time, &c.time); 620 } 621 ll = c.time.tv_sec*1000000 + c.time.tv_usec; 622 ll *= 1000; /* convert to nanoseconds */ 623 ll /= c._enqueue; 624 sprintf(msg, "1::%d", c.flows); 625 for (i = 0; i < c.flows; i++) { 626 if (c.wfi < c.q_wfi[i]) 627 c.wfi = c.q_wfi[i]; 628 } 629 D("sched=%-12s\ttime=%d.%03d sec (%.0f nsec) enq %lu %lu deq\n" 630 "\twfi=%.02f\tflow=%-16s", 631 c.name, (int)c.time.tv_sec, (int)c.time.tv_usec / 1000, ll, 632 (unsigned long)c._enqueue, (unsigned long)c.dequeue, c.wfi, 633 c.fs_config ? c.fs_config : msg); 634 dump(&c); 635 DX(1, "done ac %d av %p", ac, av); 636 for (i=0; i < ac; i++) 637 DX(1, "arg %d %s", i, av[i]); 638 return 0; 639 } 640 641 /* 642 * The controller decides whether in this iteration we should send 643 * (the packet is in c->tosend) and/or receive (flag c->can_dequeue) 644 */ 645 static void 646 controller(struct cfg_s *c) 647 { 648 struct mbuf *m; 649 struct dn_fs *fs; 650 int flow_id; 651 652 /* hysteresis between max and min */ 653 if (c->state == 0 && c->pending >= (uint32_t)c->th_max) 654 c->state = 1; 655 else if (c->state == 1 && c->pending <= (uint32_t)c->th_min) 656 c->state = 0; 657 ND(1, "state %d pending %2d", c->state, c->pending); 658 c->can_dequeue = c->state; 659 c->tosend = NULL; 660 if (c->can_dequeue) 661 return; 662 663 /* 664 * locate the flow to use for enqueueing 665 * We take the queue with the lowest number of queued packets, 666 * generate a packet for it, and put the queue in the next highest. 667 */ 668 if (1) { 669 int i; 670 struct dn_queue *q; 671 struct list_head *h; 672 673 i = ffs(c->llmask) - 1; 674 if (i < 0) { 675 D("no candidate"); 676 c->can_dequeue = 1; 677 return; 678 } 679 h = &c->ll[i]; 680 ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next); 681 q = list_first_entry(h, struct dn_queue, ni.h); 682 list_del(&q->ni.h); 683 flow_id = Q2FI(c, q); 684 DX(2, "extracted flow %p %d backlog %d", q, flow_id, i); 685 if (list_empty(h)) { 686 ND(2, "backlog %d empty", i); 687 c->llmask &= ~(1<<i); 688 } 689 ND(1, "before %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); 690 list_add_tail(&q->ni.h, h+1); 691 ND(1, " after %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); 692 if (i < BACKLOG) { 693 ND(2, "backlog %d full", i+1); 694 c->llmask |= 1<<(1+i); 695 } 696 fs = &q->fs->fs; 697 fs->cur = flow_id; 698 #ifdef USE_CUR 699 c->cur_fs = q->fs - c->fs; 700 } else { 701 /* XXX this does not work ? */ 702 /* now decide whom to send the packet, and the length */ 703 /* lookup in the flow table */ 704 if (c->cur_y >= c->max_y) { /* handle wraparound */ 705 c->cur_y = 0; 706 c->cur_fs = 0; 707 } 708 fs = &c->fs[c->cur_fs].fs; 709 flow_id = fs->cur++; 710 if (fs->cur >= fs->next_flow) 711 fs->cur = fs->first_flow; 712 c->cur_y++; 713 if (c->cur_y >= fs->next_y) 714 c->cur_fs++; 715 #endif /* USE_CUR */ 716 } 717 718 /* construct a packet */ 719 if (c->freelist) { 720 m = c->tosend = c->freelist; 721 c->freelist = c->freelist->m_nextpkt; 722 } else { 723 m = c->tosend = calloc(1, sizeof(struct mbuf)); 724 } 725 if (m == NULL) 726 return; 727 728 //m->cfg = c; 729 m->m_nextpkt = NULL; 730 m->m_pkthdr.len = fs->par[1]; // XXX maxlen 731 m->flow_id = flow_id; 732 733 ND(2,"y %6d flow %5d fs %3d weight %4d len %4d", 734 c->cur_y, m->flow_id, c->cur_fs, 735 fs->par[0], m->m_pkthdr.len); 736 737 }
Cache object: 2a14049c46c2618a7febe06fe1ae8b84
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]