Lines Matching +full:flow +full:- +full:controller
5 * The framework include a simple controller which, at each
30 int32_t th_min, th_max; /* thresholds for hysteresis; negative means per flow */
41 int cur_fs; /* used in generation, between 0 and max_y - 1 */
46 struct mbuf *tosend; /* packet to send -- also flag to enqueue */
56 /* size of the three fields including sched-specific areas */
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 */
64 * for scheduler-specific parameters, total size is schk_len
70 * total size is si_len. si->sched points to sched
84 * 2^{i-1}+1 .. 2^i entries.
90 double *q_wfi; /* (byte) Worst-case Fair Index of the flows */
91 double wfi; /* (byte) Worst-case Fair Index of the system */
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)
105 static void controller(struct cfg_s *c);
109 * flow to the end of the bucket.
117 c->drop++; in drop()
118 q = FI2Q(c, m->flow_id); in drop()
119 i = q->ni.length; // XXX or ffs... in drop()
121 ND("q %p id %d current length %d", q, m->flow_id, i); in drop()
123 struct list_head *h = &q->ni.h; in drop()
124 c->llmask &= ~(1<<(i+1)); in drop()
125 c->llmask |= (1<<(i)); in drop()
127 list_add_tail(h, &c->ll[i]); in drop()
129 m->m_nextpkt = c->freelist; in drop()
130 c->freelist = m; in drop()
145 if (mq->head == NULL) in default_enqueue()
146 mq->head = m; in default_enqueue()
148 mq->tail->m_nextpkt = m; in default_enqueue()
149 mq->tail = m; in default_enqueue()
150 return 0; /* default - success */ in default_enqueue()
159 if ((m = mq->head)) { in default_dequeue()
160 m = mq->head; in default_dequeue()
161 mq->head = m->m_nextpkt; in default_dequeue()
162 m->m_nextpkt = NULL; in default_dequeue()
170 struct dn_sch_inst *si = c->si; in gnet_stats_enq()
171 struct dn_queue *_q = FI2Q(c, mb->flow_id); in gnet_stats_enq()
173 if (_q->ni.length == 1) { in gnet_stats_enq()
174 _q->ni.bytes = 0; in gnet_stats_enq()
175 _q->ni.sch_bytes = si->ni.bytes; in gnet_stats_enq()
182 struct dn_sch_inst *si = c->si; in gnet_stats_deq()
183 struct dn_queue *_q = FI2Q(c, mb->flow_id); in gnet_stats_deq()
184 int len = mb->m_pkthdr.len; in gnet_stats_deq()
186 _q->ni.bytes += len; in gnet_stats_deq()
187 si->ni.bytes += len; in gnet_stats_deq()
189 if (_q->ni.length == 0) { in gnet_stats_deq()
190 double bytes = (double)_q->ni.bytes; in gnet_stats_deq()
191 double sch_bytes = (double)si->ni.bytes - _q->ni.sch_bytes; in gnet_stats_deq()
192 double weight = (double)_q->fs->fs.par[0] / c->wsum; in gnet_stats_deq()
193 double wfi = sch_bytes * weight - bytes; in gnet_stats_deq()
195 if (c->q_wfi[mb->flow_id] < wfi) in gnet_stats_deq()
196 c->q_wfi[mb->flow_id] = wfi; in gnet_stats_deq()
206 for (i=0; i < c->loops; i++) { in mainloop()
208 controller(c); in mainloop()
210 i, c->_enqueue, c->tosend, c->can_dequeue); in mainloop()
211 if ( (m = c->tosend) ) { in mainloop()
213 struct dn_queue *q = FI2Q(c, m->flow_id); in mainloop()
214 c->_enqueue++; in mainloop()
215 ret = c->enq(c->si, q, m); in mainloop()
225 c->pending++; in mainloop()
228 } else if (c->can_dequeue) { in mainloop()
230 c->dequeue++; in mainloop()
231 m = c->deq(c->si); in mainloop()
233 c->pending--; in mainloop()
235 c->drop--; /* compensate */ in mainloop()
238 D("--- ouch, cannot operate on iteration %d, pending %d", i, c->pending); in mainloop()
252 for (i=0; i < c->flows; i++) { in dump()
255 (unsigned long long)q->ni.tot_bytes); in dump()
257 DX(1, "done %d loops\n", c->loops); in dump()
271 DX(3, "token is <%s> %s", s, key ? key : "-"); in getnum()
275 l = -1; in getnum()
284 l = -l; /* multiply by n */ in getnum()
297 end--; in getnum()
309 * flowsets are a comma-separated list of
312 * Both weight and range can be min-max-steps.
325 DX(3, "--- pass %d flows %d flowsets %d", pass, c->flows, c->flowsets); in parse_flowsets()
327 if (c->fs_config) in parse_flowsets()
329 c->fs_config, fs); in parse_flowsets()
330 c->fs_config = fs; in parse_flowsets()
332 s = c->fs_config ? strdup(c->fs_config) : NULL; in parse_flowsets()
366 wi = w + ((w_h - w)* i)/(w_steps == 1 ? 1 : (w_steps-1)); in parse_flowsets()
368 struct dn_fs *fs = &c->fs[n_fs].fs; // tentative in parse_flowsets()
371 li = len + ((len_h - len)* j)/(l_steps == 1 ? 1 : (l_steps-1)); in parse_flowsets()
373 DX(3, "----- fs %4d weight %4d lmax %4d X %4d flows %d", in parse_flowsets()
377 if (c->fs == NULL || c->flowsets <= n_fs) { in parse_flowsets()
382 fs->par[0] = wi; in parse_flowsets()
383 fs->par[1] = li; in parse_flowsets()
384 fs->index = n_fs; in parse_flowsets()
385 fs->n_flows = flows; in parse_flowsets()
386 fs->cur = fs->first_flow = prev==NULL ? 0 : prev->next_flow; in parse_flowsets()
387 fs->next_flow = fs->first_flow + fs->n_flows; in parse_flowsets()
388 fs->y = x * flows; in parse_flowsets()
389 fs->base_y = (prev == NULL) ? 0 : prev->next_y; in parse_flowsets()
390 fs->next_y = fs->base_y + fs->y; in parse_flowsets()
395 c->flows = n_flows; in parse_flowsets()
396 c->flowsets = n_fs; in parse_flowsets()
397 c->wsum = wsum; in parse_flowsets()
402 DX(1,"%d flows on %d flowsets", c->flows, c->flowsets); in parse_flowsets()
404 c->max_y = prev ? prev->base_y + prev->y : 0; in parse_flowsets()
405 DX(1,"%d flows on %d flowsets max_y %d", c->flows, c->flowsets, c->max_y); in parse_flowsets()
407 for (i=0; i < c->flowsets; i++) { in parse_flowsets()
408 struct dn_fs *fs = &c->fs[i].fs; in parse_flowsets()
409 DX(1, "fs %3d w %5d l %4d flow %5d .. %5d y %6d .. %6d", in parse_flowsets()
410 i, fs->par[0], fs->par[1], in parse_flowsets()
411 fs->first_flow, fs->next_flow, in parse_flowsets()
412 fs->base_y, fs->next_y); in parse_flowsets()
413 for (j = fs->first_flow; j < fs->next_flow; j++) { in parse_flowsets()
415 q->fs = &c->fs[i]; in parse_flowsets()
436 int ac = c->ac; in init()
437 char * const *av = c->av; in init()
439 c->si_len = sizeof(struct dn_sch_inst); in init()
440 c->q_len = sizeof(struct dn_queue); in init()
444 c->th_min = -1; /* 1 packet per flow */ in init()
445 c->th_max = -20;/* 20 packets per flow */ in init()
446 c->lmin = c->lmax = 1280; /* packet len */ in init()
447 c->flows = 1; in init()
448 c->flowsets = 1; in init()
449 c->name = "null"; in init()
450 ac--; av++; in init()
452 if (!strcmp(*av, "-n")) { in init()
453 c->loops = getnum(av[1], NULL, av[0]); in init()
454 } else if (!strcmp(*av, "-d")) { in init()
456 } else if (!strcmp(*av, "-alg")) { in init()
476 c->name = mod ? mod->name : "NULL"; in init()
477 DX(3, "using scheduler %s", c->name); in init()
478 } else if (!strcmp(*av, "-len")) { in init()
479 c->lmin = getnum(av[1], NULL, av[0]); in init()
480 c->lmax = c->lmin; in init()
481 DX(3, "setting max to %d", c->th_max); in init()
483 } else if (!strcmp(*av, "-burst")) { in init()
484 c->maxburst = getnum(av[1], NULL, av[0]); in init()
485 DX(3, "setting max to %d", c->th_max); in init()
487 } else if (!strcmp(*av, "-qmax")) { in init()
488 c->th_max = getnum(av[1], NULL, av[0]); in init()
489 DX(3, "setting max to %d", c->th_max); in init()
490 } else if (!strcmp(*av, "-qmin")) { in init()
491 c->th_min = getnum(av[1], NULL, av[0]); in init()
492 DX(3, "setting min to %d", c->th_min); in init()
493 } else if (!strcmp(*av, "-flows")) { in init()
494 c->flows = getnum(av[1], NULL, av[0]); in init()
495 DX(3, "setting flows to %d", c->flows); in init()
496 } else if (!strcmp(*av, "-flowsets")) { in init()
498 DX(3, "setting flowsets to %d", c->flowsets); in init()
502 ac -= 2; av += 2; in init()
505 if (c->maxburst <= 0) in init()
506 c->maxburst = 1; in init()
508 if (c->loops <= 0) in init()
509 c->loops = 1; in init()
510 if (c->flows <= 0) in init()
511 c->flows = 1; in init()
512 if (c->flowsets <= 0) in init()
513 c->flowsets = 1; in init()
514 if (c->lmin <= 0) in init()
515 c->lmin = 1; in init()
516 if (c->lmax <= 0) in init()
517 c->lmax = 1; in init()
519 if (c->th_min < 0) in init()
520 c->th_min = c->flows * -c->th_min; in init()
521 if (c->th_max < 0) in init()
522 c->th_max = c->flows * -c->th_max; in init()
523 if (c->th_max <= c->th_min) in init()
524 c->th_max = c->th_min + 1; in init()
528 p = mod->p; in init()
529 DX(3, "using module %s f %p p %p", mod->name, mod->f, mod->p); in init()
530 DX(3, "modname %s ty %d", p->name, p->type); in init()
532 c->enq = p->enqueue; in init()
533 c->deq = p->dequeue; in init()
534 c->si_len += p->si_datalen; in init()
535 c->q_len += p->q_datalen; in init()
536 c->schk_len += p->schk_datalen; in init()
538 /* make sure c->si has room for a queue */ in init()
539 c->enq = default_enqueue; in init()
540 c->deq = default_dequeue; in init()
544 D("using %d flows, %d flowsets", c->flows, c->flowsets); in init()
546 c->q_len, (int)sizeof(struct dn_fsk), in init()
547 c->si_len, c->schk_len); in init()
548 c->sched = calloc(1, c->schk_len); /* one parent scheduler */ in init()
549 c->si = calloc(1, c->si_len); /* one scheduler instance */ in init()
550 c->fs = calloc(c->flowsets, sizeof(struct dn_fsk)); in init()
551 c->q = calloc(c->flows, c->q_len); /* one queue per flow */ in init()
552 c->q_wfi = calloc(c->flows, sizeof(double)); /* stats, one per flow */ in init()
553 if (!c->sched || !c->si || !c->fs || !c->q || !c->q_wfi) { in init()
557 c->si->sched = c->sched; /* link scheduler instance to template */ in init()
560 if (p->config) in init()
561 p->config(c->si->sched); in init()
562 if (p->new_sched) in init()
563 p->new_sched(c->si); in init()
568 for (i = 0; i < c->flowsets; i++) { in init()
569 struct dn_fsk *fsk = &c->fs[i]; in init()
570 if (fsk->fs.par[1] == 0) in init()
571 fsk->fs.par[1] = 1000; /* default pkt len */ in init()
572 fsk->sched = c->si->sched; in init()
573 if (p && p->new_fsk) in init()
574 p->new_fsk(fsk); in init()
576 /* --- now the scheduler is initialized --- */ in init()
583 INIT_LIST_HEAD(&c->ll[i]); in init()
585 for (i = 0; i < c->flows; i++) { in init()
587 if (q->fs == NULL) in init()
588 q->fs = &c->fs[0]; /* XXX */ in init()
589 q->_si = c->si; in init()
590 if (p && p->new_queue) in init()
591 p->new_queue(q); in init()
592 INIT_LIST_HEAD(&q->ni.h); in init()
593 list_add_tail(&q->ni.h, &c->ll[0]); in init()
595 c->llmask = 1; /* all flows are in the first list */ in init()
628 D("sched=%-12s\ttime=%d.%03d sec (%.0f nsec) enq %lu %lu deq\n" in main()
629 "\twfi=%.02f\tflow=%-16s", in main()
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)
645 controller(struct cfg_s *c) in controller() function
652 if (c->state == 0 && c->pending >= (uint32_t)c->th_max) in controller()
653 c->state = 1; in controller()
654 else if (c->state == 1 && c->pending <= (uint32_t)c->th_min) in controller()
655 c->state = 0; in controller()
656 ND(1, "state %d pending %2d", c->state, c->pending); in controller()
657 c->can_dequeue = c->state; in controller()
658 c->tosend = NULL; in controller()
659 if (c->can_dequeue) in controller()
663 * locate the flow to use for enqueueing in controller()
672 i = ffs(c->llmask) - 1; in controller()
675 c->can_dequeue = 1; in controller()
678 h = &c->ll[i]; in controller()
679 ND(1, "backlog %d p %p prev %p next %p", i, h, h->prev, h->next); in controller()
681 list_del(&q->ni.h); in controller()
683 DX(2, "extracted flow %p %d backlog %d", q, flow_id, i); in controller()
686 c->llmask &= ~(1<<i); in controller()
689 list_add_tail(&q->ni.h, h+1); in controller()
693 c->llmask |= 1<<(1+i); in controller()
695 fs = &q->fs->fs; in controller()
696 fs->cur = flow_id; in controller()
698 c->cur_fs = q->fs - c->fs; in controller()
702 /* lookup in the flow table */ in controller()
703 if (c->cur_y >= c->max_y) { /* handle wraparound */ in controller()
704 c->cur_y = 0; in controller()
705 c->cur_fs = 0; in controller()
707 fs = &c->fs[c->cur_fs].fs; in controller()
708 flow_id = fs->cur++; in controller()
709 if (fs->cur >= fs->next_flow) in controller()
710 fs->cur = fs->first_flow; in controller()
711 c->cur_y++; in controller()
712 if (c->cur_y >= fs->next_y) in controller()
713 c->cur_fs++; in controller()
718 if (c->freelist) { in controller()
719 m = c->tosend = c->freelist; in controller()
720 c->freelist = c->freelist->m_nextpkt; in controller()
722 m = c->tosend = calloc(1, sizeof(struct mbuf)); in controller()
727 //m->cfg = c; in controller()
728 m->m_nextpkt = NULL; in controller()
729 m->m_pkthdr.len = fs->par[1]; // XXX maxlen in controller()
730 m->flow_id = flow_id; in controller()
732 ND(2,"y %6d flow %5d fs %3d weight %4d len %4d", in controller()
733 c->cur_y, m->flow_id, c->cur_fs, in controller()
734 fs->par[0], m->m_pkthdr.len); in controller()