1204591Sluigi/* 2204591Sluigi * $FreeBSD: releng/11.0/sys/netpfil/ipfw/test/main.c 294882 2016-01-27 02:22:31Z 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 12294882Sluigi// #define USE_BURST // what is this for ? 13294882Sluigi 14204591Sluigi#include "dn_test.h" 15204591Sluigi 16204591Sluigistruct cfg_s { 17204591Sluigi int ac; 18204591Sluigi char * const *av; 19204591Sluigi 20204591Sluigi const char *name; 21204591Sluigi int loops; 22204591Sluigi struct timeval time; 23204591Sluigi 24204591Sluigi /* running counters */ 25204591Sluigi uint32_t _enqueue; 26204591Sluigi uint32_t drop; 27204591Sluigi uint32_t pending; 28204591Sluigi uint32_t dequeue; 29204591Sluigi 30204591Sluigi /* generator parameters */ 31294882Sluigi int32_t th_min, th_max; /* thresholds for hysteresis; negative means per flow */ 32294882Sluigi#ifdef USE_BURST 33204591Sluigi int maxburst; 34294882Sluigi#endif /* USE_BURST */ 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 */ 39294882Sluigi#ifdef USE_CUR 40204591Sluigi int max_y; /* max random number in the generation */ 41294882Sluigi int cur_y 42294882Sluigi int cur_fs; /* used in generation, between 0 and max_y - 1 */ 43294882Sluigi#endif /* USE_CUR */ 44204591Sluigi const char *fs_config; /* flowset config */ 45204591Sluigi int can_dequeue; 46204591Sluigi int burst; /* count of packets sent in a burst */ 47204591Sluigi struct mbuf *tosend; /* packet to send -- also flag to enqueue */ 48204591Sluigi 49204591Sluigi struct mbuf *freelist; 50204591Sluigi 51204591Sluigi struct mbuf *head, *tail; /* a simple tailq */ 52204591Sluigi 53204591Sluigi /* scheduler hooks */ 54204591Sluigi int (*enq)(struct dn_sch_inst *, struct dn_queue *, 55204591Sluigi struct mbuf *); 56204591Sluigi struct mbuf * (*deq)(struct dn_sch_inst *); 57204591Sluigi /* size of the three fields including sched-specific areas */ 58294882Sluigi uint32_t schk_len; 59294882Sluigi uint32_t q_len; /* size of a queue including sched-fields */ 60294882Sluigi uint32_t si_len; /* size of a sch_inst including sched-fields */ 61204591Sluigi char *q; /* array of flow queues */ 62204591Sluigi /* use a char* because size is variable */ 63294882Sluigi /* 64294882Sluigi * The scheduler template (one) followd by schk_datalen bytes 65294882Sluigi * for scheduler-specific parameters, total size is schk_len 66294882Sluigi */ 67294882Sluigi struct dn_schk *sched; 68294882Sluigi /* 69294882Sluigi * one scheduler instance, followed by si_datalen bytes 70294882Sluigi * for scheduler specific parameters of this instance, 71294882Sluigi * total size is si_len. si->sched points to sched 72294882Sluigi */ 73294882Sluigi struct dn_sch_inst *si; 74204591Sluigi struct dn_fsk *fs; /* array of flowsets */ 75204591Sluigi 76204591Sluigi /* generator state */ 77294882Sluigi int state; /* 0 = going up (enqueue), 1: going down (dequeue) */ 78204591Sluigi 79204591Sluigi /* 80204591Sluigi * We keep lists for each backlog level, and always serve 81204591Sluigi * the one with shortest backlog. llmask contains a bitmap 82204591Sluigi * of lists, and ll are the heads of the lists. The last 83204591Sluigi * entry (BACKLOG) contains all entries considered 'full' 84204591Sluigi * XXX to optimize things, entry i could contain queues with 85204591Sluigi * 2^{i-1}+1 .. 2^i entries. 86204591Sluigi */ 87294882Sluigi#define BACKLOG 30 /* this many backlogged classes, we only need BACKLOG+1 */ 88294882Sluigi uint64_t llmask; 89204591Sluigi struct list_head ll[BACKLOG + 10]; 90285360Sluigi 91285360Sluigi double *q_wfi; /* (byte) Worst-case Fair Index of the flows */ 92285360Sluigi double wfi; /* (byte) Worst-case Fair Index of the system */ 93204591Sluigi}; 94204591Sluigi 95294882Sluigi/* FI2Q and Q2FI converts from flow_id (i.e. queue index) 96294882Sluigi * to dn_queue and back. We cannot simply use pointer arithmetic 97294882Sluigi * because the queu has variable size, q_len 98294882Sluigi */ 99204591Sluigi#define FI2Q(c, i) ((struct dn_queue *)((c)->q + (c)->q_len * (i))) 100204591Sluigi#define Q2FI(c, q) (((char *)(q) - (c)->q)/(c)->q_len) 101204591Sluigi 102204591Sluigiint debug = 0; 103204591Sluigi 104204591Sluigistruct dn_parms dn_cfg; 105204591Sluigi 106204591Sluigistatic void controller(struct cfg_s *c); 107204591Sluigi 108294882Sluigi/* release a packet for a given flow_id. 109294882Sluigi * Put the mbuf in the freelist, and in case move the 110294882Sluigi * flow to the end of the bucket. 111204591Sluigi */ 112294882Sluigistatic int 113204591Sluigidrop(struct cfg_s *c, struct mbuf *m) 114204591Sluigi{ 115204591Sluigi struct dn_queue *q; 116204591Sluigi int i; 117204591Sluigi 118204591Sluigi c->drop++; 119204591Sluigi q = FI2Q(c, m->flow_id); 120204591Sluigi i = q->ni.length; // XXX or ffs... 121204591Sluigi 122204591Sluigi ND("q %p id %d current length %d", q, m->flow_id, i); 123204591Sluigi if (i < BACKLOG) { 124204591Sluigi struct list_head *h = &q->ni.h; 125204591Sluigi c->llmask &= ~(1<<(i+1)); 126204591Sluigi c->llmask |= (1<<(i)); 127204591Sluigi list_del(h); 128204591Sluigi list_add_tail(h, &c->ll[i]); 129204591Sluigi } 130204591Sluigi m->m_nextpkt = c->freelist; 131204591Sluigi c->freelist = m; 132204591Sluigi return 0; 133204591Sluigi} 134204591Sluigi 135294882Sluigi 136294882Sluigi/* 137294882Sluigi * dn_sch_inst does not have a queue, for the RR we 138294882Sluigi * allocate a mq right after si 139294882Sluigi */ 140204591Sluigistatic int 141294882Sluigidefault_enqueue(struct dn_sch_inst *si, struct dn_queue *q, struct mbuf *m) 142204591Sluigi{ 143294882Sluigi struct mq *mq = (struct mq *)si; 144294882Sluigi 145294882Sluigi (void)q; 146294882Sluigi /* this is the default function if no scheduler is provided */ 147294882Sluigi if (mq->head == NULL) 148294882Sluigi mq->head = m; 149204591Sluigi else 150294882Sluigi mq->tail->m_nextpkt = m; 151294882Sluigi mq->tail = m; 152204591Sluigi return 0; /* default - success */ 153204591Sluigi} 154204591Sluigi 155294882Sluigi 156294882Sluigistatic struct mbuf * 157294882Sluigidefault_dequeue(struct dn_sch_inst *si) 158204591Sluigi{ 159294882Sluigi struct mq *mq = (struct mq *)si; 160204591Sluigi struct mbuf *m; 161294882Sluigi /* this is the default function if no scheduler is provided */ 162294882Sluigi if ((m = mq->head)) { 163294882Sluigi m = mq->head; 164294882Sluigi mq->head = m->m_nextpkt; 165204591Sluigi m->m_nextpkt = NULL; 166204591Sluigi } 167204591Sluigi return m; 168204591Sluigi} 169204591Sluigi 170285360Sluigistatic void 171285360Sluigignet_stats_enq(struct cfg_s *c, struct mbuf *mb) 172285360Sluigi{ 173285360Sluigi struct dn_sch_inst *si = c->si; 174285360Sluigi struct dn_queue *_q = FI2Q(c, mb->flow_id); 175285360Sluigi 176285360Sluigi if (_q->ni.length == 1) { 177285360Sluigi _q->ni.bytes = 0; 178285360Sluigi _q->ni.sch_bytes = si->ni.bytes; 179285360Sluigi } 180285360Sluigi} 181285360Sluigi 182285360Sluigistatic void 183285360Sluigignet_stats_deq(struct cfg_s *c, struct mbuf *mb) 184285360Sluigi{ 185285360Sluigi struct dn_sch_inst *si = c->si; 186285360Sluigi struct dn_queue *_q = FI2Q(c, mb->flow_id); 187285360Sluigi int len = mb->m_pkthdr.len; 188285360Sluigi 189285360Sluigi _q->ni.bytes += len; 190285360Sluigi si->ni.bytes += len; 191285360Sluigi 192285360Sluigi if (_q->ni.length == 0) { 193285360Sluigi double bytes = (double)_q->ni.bytes; 194285360Sluigi double sch_bytes = (double)si->ni.bytes - _q->ni.sch_bytes; 195285360Sluigi double weight = (double)_q->fs->fs.par[0] / c->wsum; 196285360Sluigi double wfi = sch_bytes * weight - bytes; 197285360Sluigi 198285360Sluigi if (c->q_wfi[mb->flow_id] < wfi) 199285360Sluigi c->q_wfi[mb->flow_id] = wfi; 200285360Sluigi } 201285360Sluigi} 202285360Sluigi 203204591Sluigistatic int 204204591Sluigimainloop(struct cfg_s *c) 205204591Sluigi{ 206204591Sluigi int i; 207204591Sluigi struct mbuf *m; 208204591Sluigi 209204591Sluigi for (i=0; i < c->loops; i++) { 210204591Sluigi /* implement histeresis */ 211204591Sluigi controller(c); 212204591Sluigi DX(3, "loop %d enq %d send %p rx %d", 213204591Sluigi i, c->_enqueue, c->tosend, c->can_dequeue); 214204591Sluigi if ( (m = c->tosend) ) { 215294882Sluigi int ret; 216294882Sluigi struct dn_queue *q = FI2Q(c, m->flow_id); 217204591Sluigi c->_enqueue++; 218294882Sluigi ret = c->enq(c->si, q, m); 219294882Sluigi if (ret) { 220204591Sluigi drop(c, m); 221294882Sluigi D("loop %d enqueue fail", i ); 222294882Sluigi /* 223294882Sluigi * XXX do not insist; rather, try dequeue 224294882Sluigi */ 225294882Sluigi goto do_dequeue; 226204591Sluigi } else { 227204591Sluigi ND("enqueue ok"); 228204591Sluigi c->pending++; 229285360Sluigi gnet_stats_enq(c, m); 230204591Sluigi } 231294882Sluigi } else if (c->can_dequeue) { 232294882Sluigido_dequeue: 233204591Sluigi c->dequeue++; 234294882Sluigi m = c->deq(c->si); 235294882Sluigi if (m) { 236204591Sluigi c->pending--; 237204591Sluigi drop(c, m); 238204591Sluigi c->drop--; /* compensate */ 239285360Sluigi gnet_stats_deq(c, m); 240294882Sluigi } else { 241294882Sluigi D("--- ouch, cannot operate on iteration %d, pending %d", i, c->pending); 242294882Sluigi break; 243204591Sluigi } 244204591Sluigi } 245204591Sluigi } 246204591Sluigi DX(1, "mainloop ends %d", i); 247204591Sluigi return 0; 248204591Sluigi} 249204591Sluigi 250204591Sluigiint 251204591Sluigidump(struct cfg_s *c) 252204591Sluigi{ 253204591Sluigi int i; 254204591Sluigi 255204591Sluigi for (i=0; i < c->flows; i++) { 256294882Sluigi //struct dn_queue *q = FI2Q(c, i); 257294882Sluigi ND(1, "queue %4d tot %10llu", i, 258285360Sluigi (unsigned long long)q->ni.tot_bytes); 259204591Sluigi } 260204591Sluigi DX(1, "done %d loops\n", c->loops); 261204591Sluigi return 0; 262204591Sluigi} 263204591Sluigi 264204591Sluigi/* interpret a number in human form */ 265204591Sluigistatic long 266204591Sluigigetnum(const char *s, char **next, const char *key) 267204591Sluigi{ 268204591Sluigi char *end = NULL; 269204591Sluigi long l; 270204591Sluigi 271204591Sluigi if (next) /* default */ 272204591Sluigi *next = NULL; 273204591Sluigi if (s && *s) { 274204591Sluigi DX(3, "token is <%s> %s", s, key ? key : "-"); 275204591Sluigi l = strtol(s, &end, 0); 276204591Sluigi } else { 277204591Sluigi DX(3, "empty string"); 278204591Sluigi l = -1; 279204591Sluigi } 280204591Sluigi if (l < 0) { 281204591Sluigi DX(2, "invalid %s for %s", s ? s : "NULL", (key ? key : "") ); 282204591Sluigi return 0; // invalid 283204591Sluigi } 284204591Sluigi if (!end || !*end) 285204591Sluigi return l; 286204591Sluigi if (*end == 'n') 287204591Sluigi l = -l; /* multiply by n */ 288204591Sluigi else if (*end == 'K') 289204591Sluigi l = l*1000; 290204591Sluigi else if (*end == 'M') 291204591Sluigi l = l*1000000; 292204591Sluigi else if (*end == 'k') 293204591Sluigi l = l*1024; 294204591Sluigi else if (*end == 'm') 295204591Sluigi l = l*1024*1024; 296204591Sluigi else if (*end == 'w') 297204591Sluigi ; 298204591Sluigi else {/* not recognized */ 299204591Sluigi D("suffix %s for %s, next %p", end, key, next); 300204591Sluigi end--; 301204591Sluigi } 302204591Sluigi end++; 303204591Sluigi DX(3, "suffix now %s for %s, next %p", end, key, next); 304204591Sluigi if (next && *end) { 305204591Sluigi DX(3, "setting next to %s for %s", end, key); 306204591Sluigi *next = end; 307204591Sluigi } 308204591Sluigi return l; 309204591Sluigi} 310204591Sluigi 311204591Sluigi/* 312204591Sluigi * flowsets are a comma-separated list of 313204591Sluigi * weight:maxlen:flows 314204591Sluigi * indicating how many flows are hooked to that fs. 315204591Sluigi * Both weight and range can be min-max-steps. 316294882Sluigi * The first pass (fs != NULL) justs count the number of flowsets and flows, 317294882Sluigi * the second pass (fs == NULL) we complete the setup. 318204591Sluigi */ 319204591Sluigistatic void 320294882Sluigiparse_flowsets(struct cfg_s *c, const char *fs) 321204591Sluigi{ 322204591Sluigi char *s, *cur, *next; 323204591Sluigi int n_flows = 0, n_fs = 0, wsum = 0; 324204591Sluigi int i, j; 325204591Sluigi struct dn_fs *prev = NULL; 326294882Sluigi int pass = (fs == NULL); 327204591Sluigi 328204591Sluigi DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets); 329294882Sluigi if (fs != NULL) { /* first pass */ 330294882Sluigi if (c->fs_config) 331294882Sluigi D("warning, overwriting fs %s with %s", 332294882Sluigi c->fs_config, fs); 333204591Sluigi c->fs_config = fs; 334294882Sluigi } 335204591Sluigi s = c->fs_config ? strdup(c->fs_config) : NULL; 336204591Sluigi if (s == NULL) { 337204591Sluigi if (pass == 0) 338204591Sluigi D("no fsconfig"); 339204591Sluigi return; 340204591Sluigi } 341204591Sluigi for (next = s; (cur = strsep(&next, ","));) { 342204591Sluigi char *p = NULL; 343204591Sluigi int w, w_h, w_steps, wi; 344204591Sluigi int len, len_h, l_steps, li; 345204591Sluigi int flows; 346204591Sluigi 347204591Sluigi w = getnum(strsep(&cur, ":"), &p, "weight"); 348204591Sluigi if (w <= 0) 349204591Sluigi w = 1; 350204591Sluigi w_h = p ? getnum(p+1, &p, "weight_max") : w; 351204591Sluigi w_steps = p ? getnum(p+1, &p, "w_steps") : (w_h == w ?1:2); 352204591Sluigi len = getnum(strsep(&cur, ":"), &p, "len"); 353204591Sluigi if (len <= 0) 354204591Sluigi len = 1000; 355204591Sluigi len_h = p ? getnum(p+1, &p, "len_max") : len; 356204591Sluigi l_steps = p ? getnum(p+1, &p, "l_steps") : (len_h == len ? 1 : 2); 357204591Sluigi flows = getnum(strsep(&cur, ":"), NULL, "flows"); 358204591Sluigi if (flows == 0) 359204591Sluigi flows = 1; 360204591Sluigi DX(4, "weight %d..%d (%d) len %d..%d (%d) flows %d", 361204591Sluigi w, w_h, w_steps, len, len_h, l_steps, flows); 362204591Sluigi if (w == 0 || w_h < w || len == 0 || len_h < len || 363204591Sluigi flows == 0) { 364294882Sluigi DX(4,"wrong parameters %s", s); 365204591Sluigi return; 366204591Sluigi } 367204591Sluigi n_flows += flows * w_steps * l_steps; 368204591Sluigi for (i = 0; i < w_steps; i++) { 369204591Sluigi wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1)); 370204591Sluigi for (j = 0; j < l_steps; j++, n_fs++) { 371204591Sluigi struct dn_fs *fs = &c->fs[n_fs].fs; // tentative 372204591Sluigi int x; 373204591Sluigi 374204591Sluigi li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1)); 375204591Sluigi x = (wi*2048)/li; 376204591Sluigi DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d", 377204591Sluigi n_fs, wi, li, x, flows); 378204591Sluigi if (pass == 0) 379204591Sluigi continue; 380204591Sluigi if (c->fs == NULL || c->flowsets <= n_fs) { 381204591Sluigi D("error in number of flowsets"); 382204591Sluigi return; 383204591Sluigi } 384204591Sluigi wsum += wi * flows; 385204591Sluigi fs->par[0] = wi; 386204591Sluigi fs->par[1] = li; 387204591Sluigi fs->index = n_fs; 388204591Sluigi fs->n_flows = flows; 389204591Sluigi fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow; 390204591Sluigi fs->next_flow = fs->first_flow + fs->n_flows; 391204591Sluigi fs->y = x * flows; 392204591Sluigi fs->base_y = (prev == NULL) ? 0 : prev->next_y; 393204591Sluigi fs->next_y = fs->base_y + fs->y; 394204591Sluigi prev = fs; 395204591Sluigi } 396204591Sluigi } 397204591Sluigi } 398204591Sluigi c->flows = n_flows; 399204591Sluigi c->flowsets = n_fs; 400204591Sluigi c->wsum = wsum; 401204591Sluigi if (pass == 0) 402204591Sluigi return; 403204591Sluigi 404204591Sluigi /* now link all flows to their parent flowsets */ 405294882Sluigi DX(1,"%d flows on %d flowsets", c->flows, c->flowsets); 406294882Sluigi#ifdef USE_CUR 407294882Sluigi c->max_y = prev ? prev->base_y + prev->y : 0; 408204591Sluigi DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y); 409294882Sluigi#endif /* USE_CUR */ 410204591Sluigi for (i=0; i < c->flowsets; i++) { 411204591Sluigi struct dn_fs *fs = &c->fs[i].fs; 412204591Sluigi DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d", 413204591Sluigi i, fs->par[0], fs->par[1], 414204591Sluigi fs->first_flow, fs->next_flow, 415204591Sluigi fs->base_y, fs->next_y); 416204591Sluigi for (j = fs->first_flow; j < fs->next_flow; j++) { 417204591Sluigi struct dn_queue *q = FI2Q(c, j); 418204591Sluigi q->fs = &c->fs[i]; 419204591Sluigi } 420204591Sluigi } 421204591Sluigi} 422204591Sluigi 423294882Sluigi/* available schedulers */ 424294882Sluigiextern moduledata_t *_g_dn_fifo; 425294882Sluigiextern moduledata_t *_g_dn_wf2qp; 426294882Sluigiextern moduledata_t *_g_dn_rr; 427294882Sluigiextern moduledata_t *_g_dn_qfq; 428294882Sluigi#ifdef WITH_QFQP 429294882Sluigiextern moduledata_t *_g_dn_qfqp; 430294882Sluigi#endif 431294882Sluigi#ifdef WITH_KPS 432294882Sluigiextern moduledata_t *_g_dn_kps; 433294882Sluigi#endif 434294882Sluigi 435204591Sluigistatic int 436204591Sluigiinit(struct cfg_s *c) 437204591Sluigi{ 438204591Sluigi int i; 439204591Sluigi int ac = c->ac; 440204591Sluigi char * const *av = c->av; 441204591Sluigi 442204591Sluigi c->si_len = sizeof(struct dn_sch_inst); 443204591Sluigi c->q_len = sizeof(struct dn_queue); 444204591Sluigi moduledata_t *mod = NULL; 445204591Sluigi struct dn_alg *p = NULL; 446204591Sluigi 447294882Sluigi c->th_min = -1; /* 1 packet per flow */ 448204591Sluigi c->th_max = -20;/* 20 packets per flow */ 449204591Sluigi c->lmin = c->lmax = 1280; /* packet len */ 450204591Sluigi c->flows = 1; 451204591Sluigi c->flowsets = 1; 452204591Sluigi c->name = "null"; 453204591Sluigi ac--; av++; 454204591Sluigi while (ac > 1) { 455204591Sluigi if (!strcmp(*av, "-n")) { 456204591Sluigi c->loops = getnum(av[1], NULL, av[0]); 457204591Sluigi } else if (!strcmp(*av, "-d")) { 458204591Sluigi debug = atoi(av[1]); 459204591Sluigi } else if (!strcmp(*av, "-alg")) { 460204591Sluigi if (!strcmp(av[1], "rr")) 461204591Sluigi mod = _g_dn_rr; 462204591Sluigi else if (!strcmp(av[1], "wf2qp")) 463204591Sluigi mod = _g_dn_wf2qp; 464204591Sluigi else if (!strcmp(av[1], "fifo")) 465204591Sluigi mod = _g_dn_fifo; 466204591Sluigi else if (!strcmp(av[1], "qfq")) 467204591Sluigi mod = _g_dn_qfq; 468285360Sluigi#ifdef WITH_QFQP 469285360Sluigi else if (!strcmp(av[1], "qfq+") || 470285360Sluigi !strcmp(av[1], "qfqp") ) 471285360Sluigi mod = _g_dn_qfqp; 472285360Sluigi#endif 473204591Sluigi#ifdef WITH_KPS 474204591Sluigi else if (!strcmp(av[1], "kps")) 475204591Sluigi mod = _g_dn_kps; 476204591Sluigi#endif 477204591Sluigi else 478204591Sluigi mod = NULL; 479204591Sluigi c->name = mod ? mod->name : "NULL"; 480204591Sluigi DX(3, "using scheduler %s", c->name); 481204591Sluigi } else if (!strcmp(*av, "-len")) { 482204591Sluigi c->lmin = getnum(av[1], NULL, av[0]); 483204591Sluigi c->lmax = c->lmin; 484204591Sluigi DX(3, "setting max to %d", c->th_max); 485294882Sluigi#ifdef USE_BURST 486204591Sluigi } else if (!strcmp(*av, "-burst")) { 487204591Sluigi c->maxburst = getnum(av[1], NULL, av[0]); 488204591Sluigi DX(3, "setting max to %d", c->th_max); 489294882Sluigi#endif /* USE_BURST */ 490204591Sluigi } else if (!strcmp(*av, "-qmax")) { 491204591Sluigi c->th_max = getnum(av[1], NULL, av[0]); 492204591Sluigi DX(3, "setting max to %d", c->th_max); 493204591Sluigi } else if (!strcmp(*av, "-qmin")) { 494204591Sluigi c->th_min = getnum(av[1], NULL, av[0]); 495204591Sluigi DX(3, "setting min to %d", c->th_min); 496204591Sluigi } else if (!strcmp(*av, "-flows")) { 497204591Sluigi c->flows = getnum(av[1], NULL, av[0]); 498204591Sluigi DX(3, "setting flows to %d", c->flows); 499204591Sluigi } else if (!strcmp(*av, "-flowsets")) { 500294882Sluigi parse_flowsets(c, av[1]); /* first pass */ 501204591Sluigi DX(3, "setting flowsets to %d", c->flowsets); 502204591Sluigi } else { 503204591Sluigi D("option %s not recognised, ignore", *av); 504204591Sluigi } 505204591Sluigi ac -= 2; av += 2; 506204591Sluigi } 507294882Sluigi#ifdef USE_BURST 508204591Sluigi if (c->maxburst <= 0) 509204591Sluigi c->maxburst = 1; 510294882Sluigi#endif /* USE_BURST */ 511204591Sluigi if (c->loops <= 0) 512204591Sluigi c->loops = 1; 513204591Sluigi if (c->flows <= 0) 514204591Sluigi c->flows = 1; 515204591Sluigi if (c->flowsets <= 0) 516204591Sluigi c->flowsets = 1; 517204591Sluigi if (c->lmin <= 0) 518204591Sluigi c->lmin = 1; 519204591Sluigi if (c->lmax <= 0) 520204591Sluigi c->lmax = 1; 521204591Sluigi /* multiply by N */ 522204591Sluigi if (c->th_min < 0) 523204591Sluigi c->th_min = c->flows * -c->th_min; 524204591Sluigi if (c->th_max < 0) 525204591Sluigi c->th_max = c->flows * -c->th_max; 526204591Sluigi if (c->th_max <= c->th_min) 527204591Sluigi c->th_max = c->th_min + 1; 528294882Sluigi 529294882Sluigi /* now load parameters from the module */ 530204591Sluigi if (mod) { 531204591Sluigi p = mod->p; 532204591Sluigi DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p); 533204591Sluigi DX(3, "modname %s ty %d", p->name, p->type); 534294882Sluigi // XXX check enq and deq not null 535204591Sluigi c->enq = p->enqueue; 536204591Sluigi c->deq = p->dequeue; 537204591Sluigi c->si_len += p->si_datalen; 538204591Sluigi c->q_len += p->q_datalen; 539204591Sluigi c->schk_len += p->schk_datalen; 540294882Sluigi } else { 541294882Sluigi /* make sure c->si has room for a queue */ 542294882Sluigi c->enq = default_enqueue; 543294882Sluigi c->deq = default_dequeue; 544204591Sluigi } 545294882Sluigi 546204591Sluigi /* allocate queues, flowsets and one scheduler */ 547294882Sluigi D("using %d flows, %d flowsets", c->flows, c->flowsets); 548294882Sluigi D("q_len %d dn_fsk %d si %d sched %d", 549294882Sluigi c->q_len, (int)sizeof(struct dn_fsk), 550294882Sluigi c->si_len, c->schk_len); 551294882Sluigi c->sched = calloc(1, c->schk_len); /* one parent scheduler */ 552294882Sluigi c->si = calloc(1, c->si_len); /* one scheduler instance */ 553204591Sluigi c->fs = calloc(c->flowsets, sizeof(struct dn_fsk)); 554294882Sluigi c->q = calloc(c->flows, c->q_len); /* one queue per flow */ 555294882Sluigi c->q_wfi = calloc(c->flows, sizeof(double)); /* stats, one per flow */ 556294882Sluigi if (!c->sched || !c->si || !c->fs || !c->q || !c->q_wfi) { 557294882Sluigi D("error allocating memory"); 558204591Sluigi exit(1); 559204591Sluigi } 560294882Sluigi c->si->sched = c->sched; /* link scheduler instance to template */ 561204591Sluigi if (p) { 562294882Sluigi /* run initialization code if needed */ 563204591Sluigi if (p->config) 564294882Sluigi p->config(c->si->sched); 565204591Sluigi if (p->new_sched) 566204591Sluigi p->new_sched(c->si); 567204591Sluigi } 568204591Sluigi /* parse_flowsets links queues to their flowsets */ 569294882Sluigi parse_flowsets(c, NULL); /* second pass */ 570204591Sluigi /* complete the work calling new_fsk */ 571204591Sluigi for (i = 0; i < c->flowsets; i++) { 572294882Sluigi struct dn_fsk *fsk = &c->fs[i]; 573294882Sluigi if (fsk->fs.par[1] == 0) 574294882Sluigi fsk->fs.par[1] = 1000; /* default pkt len */ 575294882Sluigi fsk->sched = c->si->sched; 576204591Sluigi if (p && p->new_fsk) 577294882Sluigi p->new_fsk(fsk); 578204591Sluigi } 579294882Sluigi /* --- now the scheduler is initialized --- */ 580204591Sluigi 581294882Sluigi /* 582294882Sluigi * initialize the lists for the generator, and put 583204591Sluigi * all flows in the list for backlog = 0 584204591Sluigi */ 585204591Sluigi for (i=0; i <= BACKLOG+5; i++) 586204591Sluigi INIT_LIST_HEAD(&c->ll[i]); 587204591Sluigi 588204591Sluigi for (i = 0; i < c->flows; i++) { 589204591Sluigi struct dn_queue *q = FI2Q(c, i); 590204591Sluigi if (q->fs == NULL) 591204591Sluigi q->fs = &c->fs[0]; /* XXX */ 592204591Sluigi q->_si = c->si; 593204591Sluigi if (p && p->new_queue) 594204591Sluigi p->new_queue(q); 595204591Sluigi INIT_LIST_HEAD(&q->ni.h); 596204591Sluigi list_add_tail(&q->ni.h, &c->ll[0]); 597204591Sluigi } 598294882Sluigi c->llmask = 1; /* all flows are in the first list */ 599204591Sluigi return 0; 600204591Sluigi} 601204591Sluigi 602204591Sluigi 603204591Sluigiint 604204591Sluigimain(int ac, char *av[]) 605204591Sluigi{ 606204591Sluigi struct cfg_s c; 607204591Sluigi double ll; 608204591Sluigi int i; 609204591Sluigi char msg[40]; 610204591Sluigi 611204591Sluigi bzero(&c, sizeof(c)); 612204591Sluigi c.ac = ac; 613204591Sluigi c.av = av; 614204591Sluigi init(&c); 615204591Sluigi gettimeofday(&c.time, NULL); 616294882Sluigi D("th_min %d th_max %d", c.th_min, c.th_max); 617294882Sluigi 618204591Sluigi mainloop(&c); 619294882Sluigi { 620294882Sluigi struct timeval end; 621294882Sluigi gettimeofday(&end, NULL); 622294882Sluigi timersub(&end, &c.time, &c.time); 623204591Sluigi } 624294882Sluigi ll = c.time.tv_sec*1000000 + c.time.tv_usec; 625204591Sluigi ll *= 1000; /* convert to nanoseconds */ 626204591Sluigi ll /= c._enqueue; 627204591Sluigi sprintf(msg, "1::%d", c.flows); 628285360Sluigi for (i = 0; i < c.flows; i++) { 629285360Sluigi if (c.wfi < c.q_wfi[i]) 630285360Sluigi c.wfi = c.q_wfi[i]; 631285360Sluigi } 632294882Sluigi D("sched=%-12s\ttime=%d.%03d sec (%.0f nsec) enq %lu %lu deq\n" 633294882Sluigi "\twfi=%.02f\tflow=%-16s", 634294882Sluigi c.name, (int)c.time.tv_sec, (int)c.time.tv_usec / 1000, ll, 635294882Sluigi (unsigned long)c._enqueue, (unsigned long)c.dequeue, c.wfi, 636285360Sluigi c.fs_config ? c.fs_config : msg); 637204591Sluigi dump(&c); 638204591Sluigi DX(1, "done ac %d av %p", ac, av); 639204591Sluigi for (i=0; i < ac; i++) 640204591Sluigi DX(1, "arg %d %s", i, av[i]); 641204591Sluigi return 0; 642204591Sluigi} 643204591Sluigi 644204591Sluigi/* 645204591Sluigi * The controller decides whether in this iteration we should send 646204591Sluigi * (the packet is in c->tosend) and/or receive (flag c->can_dequeue) 647204591Sluigi */ 648204591Sluigistatic void 649204591Sluigicontroller(struct cfg_s *c) 650204591Sluigi{ 651204591Sluigi struct mbuf *m; 652204591Sluigi struct dn_fs *fs; 653204591Sluigi int flow_id; 654204591Sluigi 655294882Sluigi /* hysteresis between max and min */ 656294859Sluigi if (c->state == 0 && c->pending >= (uint32_t)c->th_max) 657204591Sluigi c->state = 1; 658294859Sluigi else if (c->state == 1 && c->pending <= (uint32_t)c->th_min) 659204591Sluigi c->state = 0; 660204591Sluigi ND(1, "state %d pending %2d", c->state, c->pending); 661204591Sluigi c->can_dequeue = c->state; 662204591Sluigi c->tosend = NULL; 663294882Sluigi if (c->can_dequeue) 664204591Sluigi return; 665204591Sluigi 666294882Sluigi /* 667294882Sluigi * locate the flow to use for enqueueing 668294882Sluigi * We take the queue with the lowest number of queued packets, 669294882Sluigi * generate a packet for it, and put the queue in the next highest. 670294882Sluigi */ 671204591Sluigi if (1) { 672204591Sluigi int i; 673204591Sluigi struct dn_queue *q; 674204591Sluigi struct list_head *h; 675204591Sluigi 676204591Sluigi i = ffs(c->llmask) - 1; 677204591Sluigi if (i < 0) { 678294882Sluigi D("no candidate"); 679204591Sluigi c->can_dequeue = 1; 680204591Sluigi return; 681204591Sluigi } 682204591Sluigi h = &c->ll[i]; 683204591Sluigi ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next); 684204591Sluigi q = list_first_entry(h, struct dn_queue, ni.h); 685204591Sluigi list_del(&q->ni.h); 686204591Sluigi flow_id = Q2FI(c, q); 687204591Sluigi DX(2, "extracted flow %p %d backlog %d", q, flow_id, i); 688204591Sluigi if (list_empty(h)) { 689204591Sluigi ND(2, "backlog %d empty", i); 690204591Sluigi c->llmask &= ~(1<<i); 691204591Sluigi } 692204591Sluigi ND(1, "before %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); 693204591Sluigi list_add_tail(&q->ni.h, h+1); 694204591Sluigi ND(1, " after %d p %p prev %p next %p", i+1, h+1, h[1].prev, h[1].next); 695204591Sluigi if (i < BACKLOG) { 696204591Sluigi ND(2, "backlog %d full", i+1); 697204591Sluigi c->llmask |= 1<<(1+i); 698204591Sluigi } 699204591Sluigi fs = &q->fs->fs; 700294882Sluigi fs->cur = flow_id; 701294882Sluigi#ifdef USE_CUR 702204591Sluigi c->cur_fs = q->fs - c->fs; 703204591Sluigi } else { 704204591Sluigi /* XXX this does not work ? */ 705204591Sluigi /* now decide whom to send the packet, and the length */ 706204591Sluigi /* lookup in the flow table */ 707204591Sluigi if (c->cur_y >= c->max_y) { /* handle wraparound */ 708204591Sluigi c->cur_y = 0; 709204591Sluigi c->cur_fs = 0; 710204591Sluigi } 711204591Sluigi fs = &c->fs[c->cur_fs].fs; 712204591Sluigi flow_id = fs->cur++; 713204591Sluigi if (fs->cur >= fs->next_flow) 714204591Sluigi fs->cur = fs->first_flow; 715204591Sluigi c->cur_y++; 716204591Sluigi if (c->cur_y >= fs->next_y) 717204591Sluigi c->cur_fs++; 718294882Sluigi#endif /* USE_CUR */ 719204591Sluigi } 720204591Sluigi 721204591Sluigi /* construct a packet */ 722204591Sluigi if (c->freelist) { 723204591Sluigi m = c->tosend = c->freelist; 724204591Sluigi c->freelist = c->freelist->m_nextpkt; 725204591Sluigi } else { 726204591Sluigi m = c->tosend = calloc(1, sizeof(struct mbuf)); 727204591Sluigi } 728204591Sluigi if (m == NULL) 729204591Sluigi return; 730204591Sluigi 731294882Sluigi //m->cfg = c; 732204591Sluigi m->m_nextpkt = NULL; 733204591Sluigi m->m_pkthdr.len = fs->par[1]; // XXX maxlen 734204591Sluigi m->flow_id = flow_id; 735204591Sluigi 736204591Sluigi ND(2,"y %6d flow %5d fs %3d weight %4d len %4d", 737204591Sluigi c->cur_y, m->flow_id, c->cur_fs, 738204591Sluigi fs->par[0], m->m_pkthdr.len); 739204591Sluigi 740204591Sluigi} 741