1204591Sluigi/* 2204591Sluigi * $FreeBSD: releng/10.3/sys/netpfil/ipfw/test/main.c 204591 2010-03-02 17:40:48Z luigi $ 3204591Sluigi * 4204591Sluigi * Testing program for schedulers 5204591Sluigi * 6204591Sluigi * The framework include a simple controller which, at each 7204591Sluigi * iteration, decides whether we can enqueue and/or dequeue. 8204591Sluigi * Then the mainloop runs the required number of tests, 9204591Sluigi * keeping track of statistics. 10204591Sluigi */ 11204591Sluigi 12204591Sluigi#include "dn_test.h" 13204591Sluigi 14204591Sluigistruct q_list { 15204591Sluigi struct list_head h; 16204591Sluigi}; 17204591Sluigi 18204591Sluigistruct cfg_s { 19204591Sluigi int ac; 20204591Sluigi char * const *av; 21204591Sluigi 22204591Sluigi const char *name; 23204591Sluigi int loops; 24204591Sluigi struct timeval time; 25204591Sluigi 26204591Sluigi /* running counters */ 27204591Sluigi uint32_t _enqueue; 28204591Sluigi uint32_t drop; 29204591Sluigi uint32_t pending; 30204591Sluigi uint32_t dequeue; 31204591Sluigi 32204591Sluigi /* generator parameters */ 33204591Sluigi int th_min, th_max; 34204591Sluigi int maxburst; 35204591Sluigi int lmin, lmax; /* packet len */ 36204591Sluigi int flows; /* number of flows */ 37204591Sluigi int flowsets; /* number of flowsets */ 38204591Sluigi int wsum; /* sum of weights of all flows */ 39204591Sluigi int max_y; /* max random number in the generation */ 40204591Sluigi int cur_y, cur_fs; /* used in generation, between 0 and max_y - 1 */ 41204591Sluigi const char *fs_config; /* flowset config */ 42204591Sluigi int can_dequeue; 43204591Sluigi int burst; /* count of packets sent in a burst */ 44204591Sluigi struct mbuf *tosend; /* packet to send -- also flag to enqueue */ 45204591Sluigi 46204591Sluigi struct mbuf *freelist; 47204591Sluigi 48204591Sluigi struct mbuf *head, *tail; /* a simple tailq */ 49204591Sluigi 50204591Sluigi /* scheduler hooks */ 51204591Sluigi int (*enq)(struct dn_sch_inst *, struct dn_queue *, 52204591Sluigi struct mbuf *); 53204591Sluigi struct mbuf * (*deq)(struct dn_sch_inst *); 54204591Sluigi /* size of the three fields including sched-specific areas */ 55204591Sluigi int schk_len; 56204591Sluigi int q_len; /* size of a queue including sched-fields */ 57204591Sluigi int si_len; /* size of a sch_inst including sched-fields */ 58204591Sluigi char *q; /* array of flow queues */ 59204591Sluigi /* use a char* because size is variable */ 60204591Sluigi struct dn_fsk *fs; /* array of flowsets */ 61204591Sluigi struct dn_sch_inst *si; 62204591Sluigi struct dn_schk *sched; 63204591Sluigi 64204591Sluigi /* generator state */ 65204591Sluigi int state; /* 0 = going up, 1: going down */ 66204591Sluigi 67204591Sluigi /* 68204591Sluigi * We keep lists for each backlog level, and always serve 69204591Sluigi * the one with shortest backlog. llmask contains a bitmap 70204591Sluigi * of lists, and ll are the heads of the lists. The last 71204591Sluigi * entry (BACKLOG) contains all entries considered 'full' 72204591Sluigi * XXX to optimize things, entry i could contain queues with 73204591Sluigi * 2^{i-1}+1 .. 2^i entries. 74204591Sluigi */ 75204591Sluigi#define BACKLOG 30 76204591Sluigi uint32_t llmask; 77204591Sluigi struct list_head ll[BACKLOG + 10]; 78204591Sluigi}; 79204591Sluigi 80204591Sluigi/* FI2Q and Q2FI converts from flow_id to dn_queue and back. 81204591Sluigi * We cannot easily use pointer arithmetic because it is variable size. 82204591Sluigi */ 83204591Sluigi#define FI2Q(c, i) ((struct dn_queue *)((c)->q + (c)->q_len * (i))) 84204591Sluigi#define Q2FI(c, q) (((char *)(q) - (c)->q)/(c)->q_len) 85204591Sluigi 86204591Sluigiint debug = 0; 87204591Sluigi 88204591Sluigistruct dn_parms dn_cfg; 89204591Sluigi 90204591Sluigistatic void controller(struct cfg_s *c); 91204591Sluigi 92204591Sluigi/* release a packet: put the mbuf in the freelist, and the queue in 93204591Sluigi * the bucket. 94204591Sluigi */ 95204591Sluigiint 96204591Sluigidrop(struct cfg_s *c, struct mbuf *m) 97204591Sluigi{ 98204591Sluigi struct dn_queue *q; 99204591Sluigi int i; 100204591Sluigi 101204591Sluigi c->drop++; 102204591Sluigi q = FI2Q(c, m->flow_id); 103204591Sluigi i = q->ni.length; // XXX or ffs... 104204591Sluigi 105204591Sluigi ND("q %p id %d current length %d", q, m->flow_id, i); 106204591Sluigi if (i < BACKLOG) { 107204591Sluigi struct list_head *h = &q->ni.h; 108204591Sluigi c->llmask &= ~(1<<(i+1)); 109204591Sluigi c->llmask |= (1<<(i)); 110204591Sluigi list_del(h); 111204591Sluigi list_add_tail(h, &c->ll[i]); 112204591Sluigi } 113204591Sluigi m->m_nextpkt = c->freelist; 114204591Sluigi c->freelist = m; 115204591Sluigi return 0; 116204591Sluigi} 117204591Sluigi 118204591Sluigi/* dequeue returns NON-NULL when a packet is dropped */ 119204591Sluigistatic int 120204591Sluigienqueue(struct cfg_s *c, void *_m) 121204591Sluigi{ 122204591Sluigi struct mbuf *m = _m; 123204591Sluigi if (c->enq) 124204591Sluigi return c->enq(c->si, FI2Q(c, m->flow_id), m); 125204591Sluigi if (c->head == NULL) 126204591Sluigi c->head = m; 127204591Sluigi else 128204591Sluigi c->tail->m_nextpkt = m; 129204591Sluigi c->tail = m; 130204591Sluigi return 0; /* default - success */ 131204591Sluigi} 132204591Sluigi 133204591Sluigi/* dequeue returns NON-NULL when a packet is available */ 134204591Sluigistatic void * 135204591Sluigidequeue(struct cfg_s *c) 136204591Sluigi{ 137204591Sluigi struct mbuf *m; 138204591Sluigi if (c->deq) 139204591Sluigi return c->deq(c->si); 140204591Sluigi if ((m = c->head)) { 141204591Sluigi m = c->head; 142204591Sluigi c->head = m->m_nextpkt; 143204591Sluigi m->m_nextpkt = NULL; 144204591Sluigi } 145204591Sluigi return m; 146204591Sluigi} 147204591Sluigi 148204591Sluigistatic int 149204591Sluigimainloop(struct cfg_s *c) 150204591Sluigi{ 151204591Sluigi int i; 152204591Sluigi struct mbuf *m; 153204591Sluigi 154204591Sluigi for (i=0; i < c->loops; i++) { 155204591Sluigi /* implement histeresis */ 156204591Sluigi controller(c); 157204591Sluigi DX(3, "loop %d enq %d send %p rx %d", 158204591Sluigi i, c->_enqueue, c->tosend, c->can_dequeue); 159204591Sluigi if ( (m = c->tosend) ) { 160204591Sluigi c->_enqueue++; 161204591Sluigi if (enqueue(c, m)) { 162204591Sluigi drop(c, m); 163204591Sluigi ND("loop %d enqueue fail", i ); 164204591Sluigi } else { 165204591Sluigi ND("enqueue ok"); 166204591Sluigi c->pending++; 167204591Sluigi } 168204591Sluigi } 169204591Sluigi if (c->can_dequeue) { 170204591Sluigi c->dequeue++; 171204591Sluigi if ((m = dequeue(c))) { 172204591Sluigi c->pending--; 173204591Sluigi drop(c, m); 174204591Sluigi c->drop--; /* compensate */ 175204591Sluigi } 176204591Sluigi } 177204591Sluigi } 178204591Sluigi DX(1, "mainloop ends %d", i); 179204591Sluigi return 0; 180204591Sluigi} 181204591Sluigi 182204591Sluigiint 183204591Sluigidump(struct cfg_s *c) 184204591Sluigi{ 185204591Sluigi int i; 186204591Sluigi struct dn_queue *q; 187204591Sluigi 188204591Sluigi for (i=0; i < c->flows; i++) { 189204591Sluigi q = FI2Q(c, i); 190204591Sluigi DX(1, "queue %4d tot %10lld", i, q->ni.tot_bytes); 191204591Sluigi } 192204591Sluigi DX(1, "done %d loops\n", c->loops); 193204591Sluigi return 0; 194204591Sluigi} 195204591Sluigi 196204591Sluigi/* interpret a number in human form */ 197204591Sluigistatic long 198204591Sluigigetnum(const char *s, char **next, const char *key) 199204591Sluigi{ 200204591Sluigi char *end = NULL; 201204591Sluigi long l; 202204591Sluigi 203204591Sluigi if (next) /* default */ 204204591Sluigi *next = NULL; 205204591Sluigi if (s && *s) { 206204591Sluigi DX(3, "token is <%s> %s", s, key ? key : "-"); 207204591Sluigi l = strtol(s, &end, 0); 208204591Sluigi } else { 209204591Sluigi DX(3, "empty string"); 210204591Sluigi l = -1; 211204591Sluigi } 212204591Sluigi if (l < 0) { 213204591Sluigi DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") ); 214204591Sluigi return 0; // invalid 215204591Sluigi } 216204591Sluigi if (!end || !*end) 217204591Sluigi return l; 218204591Sluigi if (*end == 'n') 219204591Sluigi l = -l; /* multiply by n */ 220204591Sluigi else if (*end == 'K') 221204591Sluigi l = l*1000; 222204591Sluigi else if (*end == 'M') 223204591Sluigi l = l*1000000; 224204591Sluigi else if (*end == 'k') 225204591Sluigi l = l*1024; 226204591Sluigi else if (*end == 'm') 227204591Sluigi l = l*1024*1024; 228204591Sluigi else if (*end == 'w') 229204591Sluigi ; 230204591Sluigi else {/* not recognized */ 231204591Sluigi D("suffix %s for %s, next %p", end, key, next); 232204591Sluigi end--; 233204591Sluigi } 234204591Sluigi end++; 235204591Sluigi DX(3, "suffix now %s for %s, next %p", end, key, next); 236204591Sluigi if (next && *end) { 237204591Sluigi DX(3, "setting next to %s for %s", end, key); 238204591Sluigi *next = end; 239204591Sluigi } 240204591Sluigi return l; 241204591Sluigi} 242204591Sluigi 243204591Sluigi/* 244204591Sluigi * flowsets are a comma-separated list of 245204591Sluigi * weight:maxlen:flows 246204591Sluigi * indicating how many flows are hooked to that fs. 247204591Sluigi * Both weight and range can be min-max-steps. 248204591Sluigi * In a first pass we just count the number of flowsets and flows, 249204591Sluigi * in a second pass we complete the setup. 250204591Sluigi */ 251204591Sluigistatic void 252204591Sluigiparse_flowsets(struct cfg_s *c, const char *fs, int pass) 253204591Sluigi{ 254204591Sluigi char *s, *cur, *next; 255204591Sluigi int n_flows = 0, n_fs = 0, wsum = 0; 256204591Sluigi int i, j; 257204591Sluigi struct dn_fs *prev = NULL; 258204591Sluigi 259204591Sluigi DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets); 260204591Sluigi if (pass == 0) 261204591Sluigi c->fs_config = fs; 262204591Sluigi s = c->fs_config ? strdup(c->fs_config) : NULL; 263204591Sluigi if (s == NULL) { 264204591Sluigi if (pass == 0) 265204591Sluigi D("no fsconfig"); 266204591Sluigi return; 267204591Sluigi } 268204591Sluigi for (next = s; (cur = strsep(&next, ","));) { 269204591Sluigi char *p = NULL; 270204591Sluigi int w, w_h, w_steps, wi; 271204591Sluigi int len, len_h, l_steps, li; 272204591Sluigi int flows; 273204591Sluigi 274204591Sluigi w = getnum(strsep(&cur, ":"), &p, "weight"); 275204591Sluigi if (w <= 0) 276204591Sluigi w = 1; 277204591Sluigi w_h = p ? getnum(p+1, &p, "weight_max") : w; 278204591Sluigi w_steps = p ? getnum(p+1, &p, "w_steps") : (w_h == w ?1:2); 279204591Sluigi len = getnum(strsep(&cur, ":"), &p, "len"); 280204591Sluigi if (len <= 0) 281204591Sluigi len = 1000; 282204591Sluigi len_h = p ? getnum(p+1, &p, "len_max") : len; 283204591Sluigi l_steps = p ? getnum(p+1, &p, "l_steps") : (len_h == len ? 1 : 2); 284204591Sluigi flows = getnum(strsep(&cur, ":"), NULL, "flows"); 285204591Sluigi if (flows == 0) 286204591Sluigi flows = 1; 287204591Sluigi DX(4, "weight %d..%d (%d) len %d..%d (%d) flows %d", 288204591Sluigi w, w_h, w_steps, len, len_h, l_steps, flows); 289204591Sluigi if (w == 0 || w_h < w || len == 0 || len_h < len || 290204591Sluigi flows == 0) { 291204591Sluigi DX(4,"wrong parameters %s", fs); 292204591Sluigi return; 293204591Sluigi } 294204591Sluigi n_flows += flows * w_steps * l_steps; 295204591Sluigi for (i = 0; i < w_steps; i++) { 296204591Sluigi wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1)); 297204591Sluigi for (j = 0; j < l_steps; j++, n_fs++) { 298204591Sluigi struct dn_fs *fs = &c->fs[n_fs].fs; // tentative 299204591Sluigi int x; 300204591Sluigi 301204591Sluigi li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1)); 302204591Sluigi x = (wi*2048)/li; 303204591Sluigi DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d", 304204591Sluigi n_fs, wi, li, x, flows); 305204591Sluigi if (pass == 0) 306204591Sluigi continue; 307204591Sluigi if (c->fs == NULL || c->flowsets <= n_fs) { 308204591Sluigi D("error in number of flowsets"); 309204591Sluigi return; 310204591Sluigi } 311204591Sluigi wsum += wi * flows; 312204591Sluigi fs->par[0] = wi; 313204591Sluigi fs->par[1] = li; 314204591Sluigi fs->index = n_fs; 315204591Sluigi fs->n_flows = flows; 316204591Sluigi fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow; 317204591Sluigi fs->next_flow = fs->first_flow + fs->n_flows; 318204591Sluigi fs->y = x * flows; 319204591Sluigi fs->base_y = (prev == NULL) ? 0 : prev->next_y; 320204591Sluigi fs->next_y = fs->base_y + fs->y; 321204591Sluigi prev = fs; 322204591Sluigi } 323204591Sluigi } 324204591Sluigi } 325204591Sluigi c->max_y = prev ? prev->base_y + prev->y : 0; 326204591Sluigi c->flows = n_flows; 327204591Sluigi c->flowsets = n_fs; 328204591Sluigi c->wsum = wsum; 329204591Sluigi if (pass == 0) 330204591Sluigi return; 331204591Sluigi 332204591Sluigi /* now link all flows to their parent flowsets */ 333204591Sluigi DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y); 334204591Sluigi for (i=0; i < c->flowsets; i++) { 335204591Sluigi struct dn_fs *fs = &c->fs[i].fs; 336204591Sluigi DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d", 337204591Sluigi i, fs->par[0], fs->par[1], 338204591Sluigi fs->first_flow, fs->next_flow, 339204591Sluigi fs->base_y, fs->next_y); 340204591Sluigi for (j = fs->first_flow; j < fs->next_flow; j++) { 341204591Sluigi struct dn_queue *q = FI2Q(c, j); 342204591Sluigi q->fs = &c->fs[i]; 343204591Sluigi } 344204591Sluigi } 345204591Sluigi} 346204591Sluigi 347204591Sluigistatic int 348204591Sluigiinit(struct cfg_s *c) 349204591Sluigi{ 350204591Sluigi int i; 351204591Sluigi int ac = c->ac; 352204591Sluigi char * const *av = c->av; 353204591Sluigi 354204591Sluigi c->si_len = sizeof(struct dn_sch_inst); 355204591Sluigi c->q_len = sizeof(struct dn_queue); 356204591Sluigi moduledata_t *mod = NULL; 357204591Sluigi struct dn_alg *p = NULL; 358204591Sluigi 359204591Sluigi c->th_min = 0; 360204591Sluigi c->th_max = -20;/* 20 packets per flow */ 361204591Sluigi c->lmin = c->lmax = 1280; /* packet len */ 362204591Sluigi c->flows = 1; 363204591Sluigi c->flowsets = 1; 364204591Sluigi c->name = "null"; 365204591Sluigi ac--; av++; 366204591Sluigi while (ac > 1) { 367204591Sluigi if (!strcmp(*av, "-n")) { 368204591Sluigi c->loops = getnum(av[1], NULL, av[0]); 369204591Sluigi } else if (!strcmp(*av, "-d")) { 370204591Sluigi debug = atoi(av[1]); 371204591Sluigi } else if (!strcmp(*av, "-alg")) { 372204591Sluigi extern moduledata_t *_g_dn_fifo; 373204591Sluigi extern moduledata_t *_g_dn_wf2qp; 374204591Sluigi extern moduledata_t *_g_dn_rr; 375204591Sluigi extern moduledata_t *_g_dn_qfq; 376204591Sluigi#ifdef WITH_KPS 377204591Sluigi extern moduledata_t *_g_dn_kps; 378204591Sluigi#endif 379204591Sluigi if (!strcmp(av[1], "rr")) 380204591Sluigi mod = _g_dn_rr; 381204591Sluigi else if (!strcmp(av[1], "wf2qp")) 382204591Sluigi mod = _g_dn_wf2qp; 383204591Sluigi else if (!strcmp(av[1], "fifo")) 384204591Sluigi mod = _g_dn_fifo; 385204591Sluigi else if (!strcmp(av[1], "qfq")) 386204591Sluigi mod = _g_dn_qfq; 387204591Sluigi#ifdef WITH_KPS 388204591Sluigi else if (!strcmp(av[1], "kps")) 389204591Sluigi mod = _g_dn_kps; 390204591Sluigi#endif 391204591Sluigi else 392204591Sluigi mod = NULL; 393204591Sluigi c->name = mod ? mod->name : "NULL"; 394204591Sluigi DX(3, "using scheduler %s", c->name); 395204591Sluigi } else if (!strcmp(*av, "-len")) { 396204591Sluigi c->lmin = getnum(av[1], NULL, av[0]); 397204591Sluigi c->lmax = c->lmin; 398204591Sluigi DX(3, "setting max to %d", c->th_max); 399204591Sluigi } else if (!strcmp(*av, "-burst")) { 400204591Sluigi c->maxburst = getnum(av[1], NULL, av[0]); 401204591Sluigi DX(3, "setting max to %d", c->th_max); 402204591Sluigi } else if (!strcmp(*av, "-qmax")) { 403204591Sluigi c->th_max = getnum(av[1], NULL, av[0]); 404204591Sluigi DX(3, "setting max to %d", c->th_max); 405204591Sluigi } else if (!strcmp(*av, "-qmin")) { 406204591Sluigi c->th_min = getnum(av[1], NULL, av[0]); 407204591Sluigi DX(3, "setting min to %d", c->th_min); 408204591Sluigi } else if (!strcmp(*av, "-flows")) { 409204591Sluigi c->flows = getnum(av[1], NULL, av[0]); 410204591Sluigi DX(3, "setting flows to %d", c->flows); 411204591Sluigi } else if (!strcmp(*av, "-flowsets")) { 412204591Sluigi parse_flowsets(c, av[1], 0); 413204591Sluigi DX(3, "setting flowsets to %d", c->flowsets); 414204591Sluigi } else { 415204591Sluigi D("option %s not recognised, ignore", *av); 416204591Sluigi } 417204591Sluigi ac -= 2; av += 2; 418204591Sluigi } 419204591Sluigi if (c->maxburst <= 0) 420204591Sluigi c->maxburst = 1; 421204591Sluigi if (c->loops <= 0) 422204591Sluigi c->loops = 1; 423204591Sluigi if (c->flows <= 0) 424204591Sluigi c->flows = 1; 425204591Sluigi if (c->flowsets <= 0) 426204591Sluigi c->flowsets = 1; 427204591Sluigi if (c->lmin <= 0) 428204591Sluigi c->lmin = 1; 429204591Sluigi if (c->lmax <= 0) 430204591Sluigi c->lmax = 1; 431204591Sluigi /* multiply by N */ 432204591Sluigi if (c->th_min < 0) 433204591Sluigi c->th_min = c->flows * -c->th_min; 434204591Sluigi if (c->th_max < 0) 435204591Sluigi c->th_max = c->flows * -c->th_max; 436204591Sluigi if (c->th_max <= c->th_min) 437204591Sluigi c->th_max = c->th_min + 1; 438204591Sluigi if (mod) { 439204591Sluigi p = mod->p; 440204591Sluigi DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p); 441204591Sluigi DX(3, "modname %s ty %d", p->name, p->type); 442204591Sluigi c->enq = p->enqueue; 443204591Sluigi c->deq = p->dequeue; 444204591Sluigi c->si_len += p->si_datalen; 445204591Sluigi c->q_len += p->q_datalen; 446204591Sluigi c->schk_len += p->schk_datalen; 447204591Sluigi } 448204591Sluigi /* allocate queues, flowsets and one scheduler */ 449204591Sluigi c->q = calloc(c->flows, c->q_len); 450204591Sluigi c->fs = calloc(c->flowsets, sizeof(struct dn_fsk)); 451204591Sluigi c->si = calloc(1, c->si_len); 452204591Sluigi c->sched = calloc(c->flows, c->schk_len); 453204591Sluigi if (c->q == NULL || c->fs == NULL) { 454204591Sluigi D("error allocating memory for flows"); 455204591Sluigi exit(1); 456204591Sluigi } 457204591Sluigi c->si->sched = c->sched; 458204591Sluigi if (p) { 459204591Sluigi if (p->config) 460204591Sluigi p->config(c->sched); 461204591Sluigi if (p->new_sched) 462204591Sluigi p->new_sched(c->si); 463204591Sluigi } 464204591Sluigi /* parse_flowsets links queues to their flowsets */ 465204591Sluigi parse_flowsets(c, av[1], 1); 466204591Sluigi /* complete the work calling new_fsk */ 467204591Sluigi for (i = 0; i < c->flowsets; i++) { 468204591Sluigi if (c->fs[i].fs.par[1] == 0) 469204591Sluigi c->fs[i].fs.par[1] = 1000; /* default pkt len */ 470204591Sluigi c->fs[i].sched = c->sched; 471204591Sluigi if (p && p->new_fsk) 472204591Sluigi p->new_fsk(&c->fs[i]); 473204591Sluigi } 474204591Sluigi 475204591Sluigi /* initialize the lists for the generator, and put 476204591Sluigi * all flows in the list for backlog = 0 477204591Sluigi */ 478204591Sluigi for (i=0; i <= BACKLOG+5; i++) 479204591Sluigi INIT_LIST_HEAD(&c->ll[i]); 480204591Sluigi 481204591Sluigi for (i = 0; i < c->flows; i++) { 482204591Sluigi struct dn_queue *q = FI2Q(c, i); 483204591Sluigi if (q->fs == NULL) 484204591Sluigi q->fs = &c->fs[0]; /* XXX */ 485204591Sluigi q->_si = c->si; 486204591Sluigi if (p && p->new_queue) 487204591Sluigi p->new_queue(q); 488204591Sluigi INIT_LIST_HEAD(&q->ni.h); 489204591Sluigi list_add_tail(&q->ni.h, &c->ll[0]); 490204591Sluigi } 491204591Sluigi c->llmask = 1; 492204591Sluigi return 0; 493204591Sluigi} 494204591Sluigi 495204591Sluigi 496204591Sluigiint 497204591Sluigimain(int ac, char *av[]) 498204591Sluigi{ 499204591Sluigi struct cfg_s c; 500204591Sluigi struct timeval end; 501204591Sluigi double ll; 502204591Sluigi int i; 503204591Sluigi char msg[40]; 504204591Sluigi 505204591Sluigi bzero(&c, sizeof(c)); 506204591Sluigi c.ac = ac; 507204591Sluigi c.av = av; 508204591Sluigi init(&c); 509204591Sluigi gettimeofday(&c.time, NULL); 510204591Sluigi mainloop(&c); 511204591Sluigi gettimeofday(&end, NULL); 512204591Sluigi end.tv_sec -= c.time.tv_sec; 513204591Sluigi end.tv_usec -= c.time.tv_usec; 514204591Sluigi if (end.tv_usec < 0) { 515204591Sluigi end.tv_usec += 1000000; 516204591Sluigi end.tv_sec--; 517204591Sluigi } 518204591Sluigi c.time = end; 519204591Sluigi ll = end.tv_sec*1000000 + end.tv_usec; 520204591Sluigi ll *= 1000; /* convert to nanoseconds */ 521204591Sluigi ll /= c._enqueue; 522204591Sluigi sprintf(msg, "1::%d", c.flows); 523204591Sluigi D("%-8s n %d %d time %d.%06d %8.3f qlen %d %d flows %s drops %d", 524204591Sluigi c.name, c._enqueue, c.loops, 525204591Sluigi (int)c.time.tv_sec, (int)c.time.tv_usec, ll, 526204591Sluigi c.th_min, c.th_max, 527204591Sluigi c.fs_config ? c.fs_config : msg, c.drop); 528204591Sluigi dump(&c); 529204591Sluigi DX(1, "done ac %d av %p", ac, av); 530204591Sluigi for (i=0; i < ac; i++) 531204591Sluigi DX(1, "arg %d %s", i, av[i]); 532204591Sluigi return 0; 533204591Sluigi} 534204591Sluigi 535204591Sluigi/* 536204591Sluigi * The controller decides whether in this iteration we should send 537204591Sluigi * (the packet is in c->tosend) and/or receive (flag c->can_dequeue) 538204591Sluigi */ 539204591Sluigistatic void 540204591Sluigicontroller(struct cfg_s *c) 541204591Sluigi{ 542204591Sluigi struct mbuf *m; 543204591Sluigi struct dn_fs *fs; 544204591Sluigi int flow_id; 545204591Sluigi 546204591Sluigi /* histeresis between max and min */ 547204591Sluigi if (c->state == 0 && c->pending >= c->th_max) 548204591Sluigi c->state = 1; 549204591Sluigi else if (c->state == 1 && c->pending <= c->th_min) 550204591Sluigi c->state = 0; 551204591Sluigi ND(1, "state %d pending %2d", c->state, c->pending); 552204591Sluigi c->can_dequeue = c->state; 553204591Sluigi c->tosend = NULL; 554204591Sluigi if (c->state) 555204591Sluigi return; 556204591Sluigi 557204591Sluigi if (1) { 558204591Sluigi int i; 559204591Sluigi struct dn_queue *q; 560204591Sluigi struct list_head *h; 561204591Sluigi 562204591Sluigi i = ffs(c->llmask) - 1; 563204591Sluigi if (i < 0) { 564204591Sluigi DX(2, "no candidate"); 565204591Sluigi c->can_dequeue = 1; 566204591Sluigi return; 567204591Sluigi } 568204591Sluigi h = &c->ll[i]; 569204591Sluigi ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next); 570204591Sluigi q = list_first_entry(h, struct dn_queue, ni.h); 571204591Sluigi list_del(&q->ni.h); 572204591Sluigi flow_id = Q2FI(c, q); 573204591Sluigi DX(2, "extracted flow %p %d backlog %d", q, flow_id, i); 574204591Sluigi if (list_empty(h)) { 575204591Sluigi ND(2, "backlog %d empty", i); 576204591Sluigi c->llmask &= ~(1<<i); 577204591Sluigi } 578204591Sluigi ND(1, "before %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); 579204591Sluigi list_add_tail(&q->ni.h, h+1); 580204591Sluigi ND(1, " after %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); 581204591Sluigi if (i < BACKLOG) { 582204591Sluigi ND(2, "backlog %d full", i+1); 583204591Sluigi c->llmask |= 1<<(1+i); 584204591Sluigi } 585204591Sluigi fs = &q->fs->fs; 586204591Sluigi c->cur_fs = q->fs - c->fs; 587204591Sluigi fs->cur = flow_id; 588204591Sluigi } else { 589204591Sluigi /* XXX this does not work ? */ 590204591Sluigi /* now decide whom to send the packet, and the length */ 591204591Sluigi /* lookup in the flow table */ 592204591Sluigi if (c->cur_y >= c->max_y) { /* handle wraparound */ 593204591Sluigi c->cur_y = 0; 594204591Sluigi c->cur_fs = 0; 595204591Sluigi } 596204591Sluigi fs = &c->fs[c->cur_fs].fs; 597204591Sluigi flow_id = fs->cur++; 598204591Sluigi if (fs->cur >= fs->next_flow) 599204591Sluigi fs->cur = fs->first_flow; 600204591Sluigi c->cur_y++; 601204591Sluigi if (c->cur_y >= fs->next_y) 602204591Sluigi c->cur_fs++; 603204591Sluigi } 604204591Sluigi 605204591Sluigi /* construct a packet */ 606204591Sluigi if (c->freelist) { 607204591Sluigi m = c->tosend = c->freelist; 608204591Sluigi c->freelist = c->freelist->m_nextpkt; 609204591Sluigi } else { 610204591Sluigi m = c->tosend = calloc(1, sizeof(struct mbuf)); 611204591Sluigi } 612204591Sluigi if (m == NULL) 613204591Sluigi return; 614204591Sluigi 615204591Sluigi m->cfg = c; 616204591Sluigi m->m_nextpkt = NULL; 617204591Sluigi m->m_pkthdr.len = fs->par[1]; // XXX maxlen 618204591Sluigi m->flow_id = flow_id; 619204591Sluigi 620204591Sluigi ND(2,"y %6d flow %5d fs %3d weight %4d len %4d", 621204591Sluigi c->cur_y, m->flow_id, c->cur_fs, 622204591Sluigi fs->par[0], m->m_pkthdr.len); 623204591Sluigi 624204591Sluigi} 625204591Sluigi 626204591Sluigi/* 627204591SluigiPacket allocation: 628204591Sluigito achieve a distribution that matches weights, for each X=w/lmax class 629204591Sluigiwe should generate a number of packets proportional to Y = X times the number 630204591Sluigiof flows in the class. 631204591SluigiSo we construct an array with the cumulative distribution of Y's, 632204591Sluigiand use it to identify the flow via inverse mapping (if the Y's are 633204591Sluiginot too many we can use an array for the lookup). In practice, 634204591Sluigieach flow will have X entries [virtually] pointing to it. 635204591Sluigi 636204591Sluigi*/ 637