Lines Matching +full:1 +full:q
68 - max mtu to 2^18-1;
76 #define SFQ_MAX_FLOWS (0x10000 - SFQ_MAX_DEPTH - 1) /* max number of flows */
80 /* This type should contain at least SFQ_MAX_DEPTH + 1 + SFQ_MAX_FLOWS values */
85 * Small indexes [0 ... SFQ_MAX_FLOWS - 1] are 'pointers' to slots[] array
126 struct sfq_head dep[SFQ_MAX_DEPTH + 1];
129 * dep[1] : list of flows with 1 packet
143 static inline struct sfq_head *sfq_dep_head(struct sfq_sched_data *q, sfq_index val) in sfq_dep_head() argument
146 return &q->slots[val].dep; in sfq_dep_head()
147 return &q->dep[val - SFQ_MAX_FLOWS]; in sfq_dep_head()
150 static unsigned int sfq_hash(const struct sfq_sched_data *q, in sfq_hash() argument
153 return skb_get_hash_perturb(skb, &q->perturbation) & (q->divisor - 1); in sfq_hash()
159 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_classify() local
166 TC_H_MIN(skb->priority) <= q->divisor) in sfq_classify()
169 fl = rcu_dereference_bh(q->filter_list); in sfq_classify()
171 return sfq_hash(q, skb) + 1; in sfq_classify()
187 if (TC_H_MIN(res.classid) <= q->divisor) in sfq_classify()
194 * x : slot number [0 .. SFQ_MAX_FLOWS - 1]
196 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x) in sfq_link() argument
199 struct sfq_slot *slot = &q->slots[x]; in sfq_link()
203 n = q->dep[qlen].next; in sfq_link()
208 q->dep[qlen].next = x; /* sfq_dep_head(q, p)->next = x */ in sfq_link()
209 sfq_dep_head(q, n)->prev = x; in sfq_link()
212 #define sfq_unlink(q, x, n, p) \ argument
214 n = q->slots[x].dep.next; \
215 p = q->slots[x].dep.prev; \
216 sfq_dep_head(q, p)->next = n; \
217 sfq_dep_head(q, n)->prev = p; \
221 static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x) in sfq_dec() argument
226 sfq_unlink(q, x, n, p); in sfq_dec()
228 d = q->slots[x].qlen--; in sfq_dec()
229 if (n == p && q->cur_depth == d) in sfq_dec()
230 q->cur_depth--; in sfq_dec()
231 sfq_link(q, x); in sfq_dec()
234 static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x) in sfq_inc() argument
239 sfq_unlink(q, x, n, p); in sfq_inc()
241 d = ++q->slots[x].qlen; in sfq_inc()
242 if (q->cur_depth < d) in sfq_inc()
243 q->cur_depth = d; in sfq_inc()
244 sfq_link(q, x); in sfq_inc()
288 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_drop() local
289 sfq_index x, d = q->cur_depth; in sfq_drop()
295 if (d > 1) { in sfq_drop()
296 x = q->dep[d].next; in sfq_drop()
297 slot = &q->slots[x]; in sfq_drop()
299 skb = q->headdrop ? slot_dequeue_head(slot) : slot_dequeue_tail(slot); in sfq_drop()
302 sfq_dec(q, x); in sfq_drop()
303 sch->q.qlen--; in sfq_drop()
309 if (d == 1) { in sfq_drop()
310 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */ in sfq_drop()
311 x = q->tail->next; in sfq_drop()
312 slot = &q->slots[x]; in sfq_drop()
313 q->tail->next = slot->next; in sfq_drop()
314 q->ht[slot->hash] = SFQ_EMPTY_SLOT; in sfq_drop()
322 static int sfq_prob_mark(const struct sfq_sched_data *q) in sfq_prob_mark() argument
324 return q->flags & TC_RED_ECN; in sfq_prob_mark()
328 static int sfq_hard_mark(const struct sfq_sched_data *q) in sfq_hard_mark() argument
330 return (q->flags & (TC_RED_ECN | TC_RED_HARDDROP)) == TC_RED_ECN; in sfq_hard_mark()
333 static int sfq_headdrop(const struct sfq_sched_data *q) in sfq_headdrop() argument
335 return q->headdrop; in sfq_headdrop()
341 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_enqueue() local
358 x = q->ht[hash]; in sfq_enqueue()
359 slot = &q->slots[x]; in sfq_enqueue()
361 x = q->dep[0].next; /* get a free slot */ in sfq_enqueue()
364 q->ht[hash] = x; in sfq_enqueue()
365 slot = &q->slots[x]; in sfq_enqueue()
371 if (q->red_parms) { in sfq_enqueue()
372 slot->vars.qavg = red_calc_qavg_no_idle_time(q->red_parms, in sfq_enqueue()
375 switch (red_action(q->red_parms, in sfq_enqueue()
383 if (sfq_prob_mark(q)) { in sfq_enqueue()
385 if (sfq_headdrop(q) && in sfq_enqueue()
387 q->stats.prob_mark_head++; in sfq_enqueue()
391 q->stats.prob_mark++; in sfq_enqueue()
395 q->stats.prob_drop++; in sfq_enqueue()
400 if (sfq_hard_mark(q)) { in sfq_enqueue()
402 if (sfq_headdrop(q) && in sfq_enqueue()
404 q->stats.forced_mark_head++; in sfq_enqueue()
408 q->stats.forced_mark++; in sfq_enqueue()
412 q->stats.forced_drop++; in sfq_enqueue()
417 if (slot->qlen >= q->maxdepth) { in sfq_enqueue()
419 if (!sfq_headdrop(q)) in sfq_enqueue()
438 sfq_inc(q, x); in sfq_enqueue()
439 if (slot->qlen == 1) { /* The flow is new */ in sfq_enqueue()
440 if (q->tail == NULL) { /* It is the first flow */ in sfq_enqueue()
443 slot->next = q->tail->next; in sfq_enqueue()
444 q->tail->next = x; in sfq_enqueue()
450 q->tail = slot; in sfq_enqueue()
452 slot->allot = q->quantum; in sfq_enqueue()
454 if (++sch->q.qlen <= q->limit) in sfq_enqueue()
468 qdisc_tree_reduce_backlog(sch, 1, dropped); in sfq_enqueue()
475 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_dequeue() local
481 if (q->tail == NULL) in sfq_dequeue()
485 a = q->tail->next; in sfq_dequeue()
486 slot = &q->slots[a]; in sfq_dequeue()
488 q->tail = slot; in sfq_dequeue()
489 slot->allot += q->quantum; in sfq_dequeue()
493 sfq_dec(q, a); in sfq_dequeue()
495 sch->q.qlen--; in sfq_dequeue()
500 q->ht[slot->hash] = SFQ_EMPTY_SLOT; in sfq_dequeue()
503 q->tail = NULL; /* no more active slots */ in sfq_dequeue()
506 q->tail->next = next_a; in sfq_dequeue()
523 * When q->perturbation is changed, we rehash all queued skbs
530 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_rehash() local
540 for (i = 0; i < q->maxflows; i++) { in sfq_rehash()
541 slot = &q->slots[i]; in sfq_rehash()
546 sfq_dec(q, i); in sfq_rehash()
551 q->ht[slot->hash] = SFQ_EMPTY_SLOT; in sfq_rehash()
553 q->tail = NULL; in sfq_rehash()
556 unsigned int hash = sfq_hash(q, skb); in sfq_rehash()
557 sfq_index x = q->ht[hash]; in sfq_rehash()
559 slot = &q->slots[x]; in sfq_rehash()
561 x = q->dep[0].next; /* get a free slot */ in sfq_rehash()
570 q->ht[hash] = x; in sfq_rehash()
571 slot = &q->slots[x]; in sfq_rehash()
574 if (slot->qlen >= q->maxdepth) in sfq_rehash()
577 if (q->red_parms) in sfq_rehash()
578 slot->vars.qavg = red_calc_qavg(q->red_parms, in sfq_rehash()
582 sfq_inc(q, x); in sfq_rehash()
583 if (slot->qlen == 1) { /* The flow is new */ in sfq_rehash()
584 if (q->tail == NULL) { /* It is the first flow */ in sfq_rehash()
587 slot->next = q->tail->next; in sfq_rehash()
588 q->tail->next = x; in sfq_rehash()
590 q->tail = slot; in sfq_rehash()
591 slot->allot = q->quantum; in sfq_rehash()
594 sch->q.qlen -= dropped; in sfq_rehash()
600 struct sfq_sched_data *q = from_timer(q, t, perturb_timer); in sfq_perturbation() local
601 struct Qdisc *sch = q->sch; in sfq_perturbation()
610 q->perturbation = nkey; in sfq_perturbation()
611 if (!q->filter_list && q->tail) in sfq_perturbation()
615 /* q->perturb_period can change under us from in sfq_perturbation()
618 period = READ_ONCE(q->perturb_period); in sfq_perturbation()
620 mod_timer(&q->perturb_timer, jiffies + period); in sfq_perturbation()
627 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_change() local
667 limit = q->limit; in sfq_change()
668 divisor = q->divisor; in sfq_change()
669 headdrop = q->headdrop; in sfq_change()
670 maxdepth = q->maxdepth; in sfq_change()
671 maxflows = q->maxflows; in sfq_change()
672 perturb_period = q->perturb_period; in sfq_change()
673 quantum = q->quantum; in sfq_change()
674 flags = q->flags; in sfq_change()
704 if (limit == 1) { in sfq_change()
712 q->limit = limit; in sfq_change()
713 q->divisor = divisor; in sfq_change()
714 q->headdrop = headdrop; in sfq_change()
715 q->maxdepth = maxdepth; in sfq_change()
716 q->maxflows = maxflows; in sfq_change()
717 WRITE_ONCE(q->perturb_period, perturb_period); in sfq_change()
718 q->quantum = quantum; in sfq_change()
719 q->flags = flags; in sfq_change()
721 swap(q->red_parms, p); in sfq_change()
723 qlen = sch->q.qlen; in sfq_change()
724 while (sch->q.qlen > q->limit) { in sfq_change()
731 qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, dropped); in sfq_change()
733 del_timer(&q->perturb_timer); in sfq_change()
734 if (q->perturb_period) { in sfq_change()
735 mod_timer(&q->perturb_timer, jiffies + q->perturb_period); in sfq_change()
736 get_random_bytes(&q->perturbation, sizeof(q->perturbation)); in sfq_change()
755 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_destroy() local
757 tcf_block_put(q->block); in sfq_destroy()
758 WRITE_ONCE(q->perturb_period, 0); in sfq_destroy()
759 del_timer_sync(&q->perturb_timer); in sfq_destroy()
760 sfq_free(q->ht); in sfq_destroy()
761 sfq_free(q->slots); in sfq_destroy()
762 kfree(q->red_parms); in sfq_destroy()
768 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_init() local
772 q->sch = sch; in sfq_init()
773 timer_setup(&q->perturb_timer, sfq_perturbation, TIMER_DEFERRABLE); in sfq_init()
775 err = tcf_block_get(&q->block, &q->filter_list, sch, extack); in sfq_init()
779 for (i = 0; i < SFQ_MAX_DEPTH + 1; i++) { in sfq_init()
780 q->dep[i].next = i + SFQ_MAX_FLOWS; in sfq_init()
781 q->dep[i].prev = i + SFQ_MAX_FLOWS; in sfq_init()
784 q->limit = SFQ_MAX_DEPTH; in sfq_init()
785 q->maxdepth = SFQ_MAX_DEPTH; in sfq_init()
786 q->cur_depth = 0; in sfq_init()
787 q->tail = NULL; in sfq_init()
788 q->divisor = SFQ_DEFAULT_HASH_DIVISOR; in sfq_init()
789 q->maxflows = SFQ_DEFAULT_FLOWS; in sfq_init()
790 q->quantum = psched_mtu(qdisc_dev(sch)); in sfq_init()
791 q->perturb_period = 0; in sfq_init()
792 get_random_bytes(&q->perturbation, sizeof(q->perturbation)); in sfq_init()
800 q->ht = sfq_alloc(sizeof(q->ht[0]) * q->divisor); in sfq_init()
801 q->slots = sfq_alloc(sizeof(q->slots[0]) * q->maxflows); in sfq_init()
802 if (!q->ht || !q->slots) { in sfq_init()
807 for (i = 0; i < q->divisor; i++) in sfq_init()
808 q->ht[i] = SFQ_EMPTY_SLOT; in sfq_init()
810 for (i = 0; i < q->maxflows; i++) { in sfq_init()
811 slot_queue_init(&q->slots[i]); in sfq_init()
812 sfq_link(q, i); in sfq_init()
814 if (q->limit >= 1) in sfq_init()
823 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_dump() local
826 struct red_parms *p = q->red_parms; in sfq_dump()
829 opt.v0.quantum = q->quantum; in sfq_dump()
830 opt.v0.perturb_period = q->perturb_period / HZ; in sfq_dump()
831 opt.v0.limit = q->limit; in sfq_dump()
832 opt.v0.divisor = q->divisor; in sfq_dump()
833 opt.v0.flows = q->maxflows; in sfq_dump()
834 opt.depth = q->maxdepth; in sfq_dump()
835 opt.headdrop = q->headdrop; in sfq_dump()
845 memcpy(&opt.stats, &q->stats, sizeof(opt.stats)); in sfq_dump()
846 opt.flags = q->flags; in sfq_dump()
855 return -1; in sfq_dump()
874 static void sfq_unbind(struct Qdisc *q, unsigned long cl) in sfq_unbind() argument
881 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_tcf_block() local
885 return q->block; in sfq_tcf_block()
898 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_dump_class_stats() local
899 sfq_index idx = q->ht[cl - 1]; in sfq_dump_class_stats()
904 const struct sfq_slot *slot = &q->slots[idx]; in sfq_dump_class_stats()
911 return -1; in sfq_dump_class_stats()
917 struct sfq_sched_data *q = qdisc_priv(sch); in sfq_walk() local
923 for (i = 0; i < q->divisor; i++) { in sfq_walk()
924 if (q->ht[i] == SFQ_EMPTY_SLOT) { in sfq_walk()
928 if (!tc_qdisc_stats_dump(sch, i + 1, arg)) in sfq_walk()