Lines Matching +full:slot +full:- +full:number
1 // SPDX-License-Identifier: GPL-2.0-or-later
34 "Interworking: Research and Experience", v.2, 1991, p.113-131.
44 processes queues in round-robin order.
48 - It is very cheap. Both CPU and memory requirements are minimal.
52 - "Stochastic" -> It is not 100% fair.
55 - "Round-robin" -> It introduces larger delays than virtual clock
57 traffic from non-interactive. It means, that this scheduler
67 - maximal queue length per flow to 127 packets.
68 - max mtu to 2^18-1;
69 - max 65408 flows,
70 - number of hash buckets to 65536.
74 #define SFQ_MAX_DEPTH 127 /* max number of packets per flow */
76 #define SFQ_MAX_FLOWS (0x10000 - SFQ_MAX_DEPTH - 1) /* max number of flows */
85 * Small indexes [0 ... SFQ_MAX_FLOWS - 1] are 'pointers' to slots[] array
97 sfq_index qlen; /* number of skbs in skblist */
98 sfq_index next; /* next slot in sfq RR chain */
101 int allot; /* credit for this slot */
109 int limit; /* limit of total number of packets in this qdisc */
110 unsigned int divisor; /* number of slots in hash table */
115 u8 cur_depth; /* depth of longest slot */
124 struct sfq_slot *tail; /* current slot in round */
133 unsigned int maxflows; /* number of flows in flows array */
146 return &q->slots[val].dep; in sfq_dep_head()
147 return &q->dep[val - SFQ_MAX_FLOWS]; in sfq_dep_head()
153 return skb_get_hash_perturb(skb, &q->perturbation) & (q->divisor - 1); in sfq_hash()
164 if (TC_H_MAJ(skb->priority) == sch->handle && in sfq_classify()
165 TC_H_MIN(skb->priority) > 0 && in sfq_classify()
166 TC_H_MIN(skb->priority) <= q->divisor) in sfq_classify()
167 return TC_H_MIN(skb->priority); in sfq_classify()
169 fl = rcu_dereference_bh(q->filter_list); in sfq_classify()
187 if (TC_H_MIN(res.classid) <= q->divisor) in sfq_classify()
194 * x : slot number [0 .. SFQ_MAX_FLOWS - 1]
199 struct sfq_slot *slot = &q->slots[x]; in sfq_link() local
200 int qlen = slot->qlen; in sfq_link()
203 n = q->dep[qlen].next; in sfq_link()
205 slot->dep.next = n; in sfq_link()
206 slot->dep.prev = p; 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()
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; \
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()
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()
249 /* remove one skb from tail of slot queue */
250 static inline struct sk_buff *slot_dequeue_tail(struct sfq_slot *slot) in slot_dequeue_tail() argument
252 struct sk_buff *skb = slot->skblist_prev; in slot_dequeue_tail()
254 slot->skblist_prev = skb->prev; in slot_dequeue_tail()
255 skb->prev->next = (struct sk_buff *)slot; in slot_dequeue_tail()
256 skb->next = skb->prev = NULL; in slot_dequeue_tail()
260 /* remove one skb from head of slot queue */
261 static inline struct sk_buff *slot_dequeue_head(struct sfq_slot *slot) in slot_dequeue_head() argument
263 struct sk_buff *skb = slot->skblist_next; in slot_dequeue_head()
265 slot->skblist_next = skb->next; in slot_dequeue_head()
266 skb->next->prev = (struct sk_buff *)slot; in slot_dequeue_head()
267 skb->next = skb->prev = NULL; in slot_dequeue_head()
271 static inline void slot_queue_init(struct sfq_slot *slot) in slot_queue_init() argument
273 memset(slot, 0, sizeof(*slot)); in slot_queue_init()
274 slot->skblist_prev = slot->skblist_next = (struct sk_buff *)slot; in slot_queue_init()
277 /* add skb to slot queue (tail add) */
278 static inline void slot_queue_add(struct sfq_slot *slot, struct sk_buff *skb) in slot_queue_add() argument
280 skb->prev = slot->skblist_prev; in slot_queue_add()
281 skb->next = (struct sk_buff *)slot; in slot_queue_add()
282 slot->skblist_prev->next = skb; in slot_queue_add()
283 slot->skblist_prev = skb; in slot_queue_add()
289 sfq_index x, d = q->cur_depth; in sfq_drop()
292 struct sfq_slot *slot; in sfq_drop() local
294 /* Queue is full! Find the longest slot and drop tail packet from it */ 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()
301 slot->backlog -= len; in sfq_drop()
303 sch->q.qlen--; in sfq_drop()
311 x = q->tail->next; in sfq_drop()
312 slot = &q->slots[x]; in sfq_drop()
313 if (slot->next == x) in sfq_drop()
314 q->tail = NULL; /* no more active slots */ in sfq_drop()
316 q->tail->next = slot->next; in sfq_drop()
317 q->ht[slot->hash] = SFQ_EMPTY_SLOT; in sfq_drop()
327 return q->flags & TC_RED_ECN; in sfq_prob_mark()
333 return (q->flags & (TC_RED_ECN | TC_RED_HARDDROP)) == TC_RED_ECN; in sfq_hard_mark()
338 return q->headdrop; in sfq_headdrop()
347 struct sfq_slot *slot; in sfq_enqueue() local
359 hash--; in sfq_enqueue()
361 x = q->ht[hash]; in sfq_enqueue()
362 slot = &q->slots[x]; in sfq_enqueue()
364 x = q->dep[0].next; /* get a free slot */ in sfq_enqueue()
367 q->ht[hash] = x; in sfq_enqueue()
368 slot = &q->slots[x]; in sfq_enqueue()
369 slot->hash = hash; in sfq_enqueue()
370 slot->backlog = 0; /* should already be 0 anyway... */ in sfq_enqueue()
371 red_set_vars(&slot->vars); in sfq_enqueue()
374 if (q->red_parms) { in sfq_enqueue()
375 slot->vars.qavg = red_calc_qavg_no_idle_time(q->red_parms, in sfq_enqueue()
376 &slot->vars, in sfq_enqueue()
377 slot->backlog); in sfq_enqueue()
378 switch (red_action(q->red_parms, in sfq_enqueue()
379 &slot->vars, in sfq_enqueue()
380 slot->vars.qavg)) { in sfq_enqueue()
389 INET_ECN_set_ce(slot->skblist_next)) { in sfq_enqueue()
390 q->stats.prob_mark_head++; in sfq_enqueue()
394 q->stats.prob_mark++; in sfq_enqueue()
398 q->stats.prob_drop++; in sfq_enqueue()
406 INET_ECN_set_ce(slot->skblist_next)) { in sfq_enqueue()
407 q->stats.forced_mark_head++; in sfq_enqueue()
411 q->stats.forced_mark++; in sfq_enqueue()
415 q->stats.forced_drop++; in sfq_enqueue()
420 if (slot->qlen >= q->maxdepth) { in sfq_enqueue()
426 head = slot_dequeue_head(slot); in sfq_enqueue()
427 delta = qdisc_pkt_len(head) - qdisc_pkt_len(skb); in sfq_enqueue()
428 sch->qstats.backlog -= delta; in sfq_enqueue()
429 slot->backlog -= delta; in sfq_enqueue()
432 slot_queue_add(slot, skb); in sfq_enqueue()
439 slot->backlog += qdisc_pkt_len(skb); in sfq_enqueue()
440 slot_queue_add(slot, skb); in sfq_enqueue()
442 if (slot->qlen == 1) { /* The flow is new */ in sfq_enqueue()
443 if (q->tail == NULL) { /* It is the first flow */ in sfq_enqueue()
444 slot->next = x; in sfq_enqueue()
446 slot->next = q->tail->next; in sfq_enqueue()
447 q->tail->next = x; in sfq_enqueue()
453 q->tail = slot; in sfq_enqueue()
455 slot->allot = q->quantum; in sfq_enqueue()
457 if (++sch->q.qlen <= q->limit) in sfq_enqueue()
460 qlen = slot->qlen; in sfq_enqueue()
465 if (qlen != slot->qlen) { in sfq_enqueue()
466 qdisc_tree_reduce_backlog(sch, 0, dropped - qdisc_pkt_len(skb)); in sfq_enqueue()
481 struct sfq_slot *slot; in sfq_dequeue() local
484 if (q->tail == NULL) in sfq_dequeue()
488 a = q->tail->next; in sfq_dequeue()
489 slot = &q->slots[a]; in sfq_dequeue()
490 if (slot->allot <= 0) { in sfq_dequeue()
491 q->tail = slot; in sfq_dequeue()
492 slot->allot += q->quantum; in sfq_dequeue()
495 skb = slot_dequeue_head(slot); in sfq_dequeue()
498 sch->q.qlen--; in sfq_dequeue()
500 slot->backlog -= qdisc_pkt_len(skb); in sfq_dequeue()
501 /* Is the slot empty? */ in sfq_dequeue()
502 if (slot->qlen == 0) { in sfq_dequeue()
503 q->ht[slot->hash] = SFQ_EMPTY_SLOT; in sfq_dequeue()
504 next_a = slot->next; in sfq_dequeue()
506 q->tail = NULL; /* no more active slots */ in sfq_dequeue()
509 q->tail->next = next_a; in sfq_dequeue()
511 slot->allot -= qdisc_pkt_len(skb); in sfq_dequeue()
526 * When q->perturbation is changed, we rehash all queued skbs
536 struct sfq_slot *slot; in sfq_rehash() local
543 for (i = 0; i < q->maxflows; i++) { in sfq_rehash()
544 slot = &q->slots[i]; in sfq_rehash()
545 if (!slot->qlen) in sfq_rehash()
547 while (slot->qlen) { in sfq_rehash()
548 skb = slot_dequeue_head(slot); in sfq_rehash()
552 slot->backlog = 0; in sfq_rehash()
553 red_set_vars(&slot->vars); in sfq_rehash()
554 q->ht[slot->hash] = SFQ_EMPTY_SLOT; in sfq_rehash()
556 q->tail = NULL; in sfq_rehash()
560 sfq_index x = q->ht[hash]; in sfq_rehash()
562 slot = &q->slots[x]; in sfq_rehash()
564 x = q->dep[0].next; /* get a free slot */ in sfq_rehash()
573 q->ht[hash] = x; in sfq_rehash()
574 slot = &q->slots[x]; in sfq_rehash()
575 slot->hash = hash; in sfq_rehash()
577 if (slot->qlen >= q->maxdepth) in sfq_rehash()
579 slot_queue_add(slot, skb); in sfq_rehash()
580 if (q->red_parms) in sfq_rehash()
581 slot->vars.qavg = red_calc_qavg(q->red_parms, in sfq_rehash()
582 &slot->vars, in sfq_rehash()
583 slot->backlog); in sfq_rehash()
584 slot->backlog += qdisc_pkt_len(skb); in sfq_rehash()
586 if (slot->qlen == 1) { /* The flow is new */ in sfq_rehash()
587 if (q->tail == NULL) { /* It is the first flow */ in sfq_rehash()
588 slot->next = x; in sfq_rehash()
590 slot->next = q->tail->next; in sfq_rehash()
591 q->tail->next = x; in sfq_rehash()
593 q->tail = slot; in sfq_rehash()
594 slot->allot = q->quantum; in sfq_rehash()
597 sch->q.qlen -= dropped; in sfq_rehash()
604 struct Qdisc *sch = q->sch; in sfq_perturbation()
613 q->perturbation = nkey; in sfq_perturbation()
614 if (!q->filter_list && q->tail) in sfq_perturbation()
618 /* q->perturb_period can change under us from in sfq_perturbation()
621 period = READ_ONCE(q->perturb_period); in sfq_perturbation()
623 mod_timer(&q->perturb_timer, jiffies + period); in sfq_perturbation()
647 if (opt->nla_len < nla_attr_size(sizeof(*ctl))) in sfq_change()
648 return -EINVAL; in sfq_change()
649 if (opt->nla_len >= nla_attr_size(sizeof(*ctl_v1))) in sfq_change()
651 if (ctl->divisor && in sfq_change()
652 (!is_power_of_2(ctl->divisor) || ctl->divisor > 65536)) in sfq_change()
653 return -EINVAL; in sfq_change()
655 if ((int)ctl->quantum < 0) { in sfq_change()
657 return -EINVAL; in sfq_change()
660 if (ctl->perturb_period < 0 || in sfq_change()
661 ctl->perturb_period > INT_MAX / HZ) { in sfq_change()
663 return -EINVAL; in sfq_change()
665 perturb_period = ctl->perturb_period * HZ; in sfq_change()
667 if (ctl_v1 && !red_check_params(ctl_v1->qth_min, ctl_v1->qth_max, in sfq_change()
668 ctl_v1->Wlog, ctl_v1->Scell_log, NULL)) in sfq_change()
669 return -EINVAL; in sfq_change()
670 if (ctl_v1 && ctl_v1->qth_min) { in sfq_change()
673 return -ENOMEM; in sfq_change()
678 limit = q->limit; in sfq_change()
679 divisor = q->divisor; in sfq_change()
680 headdrop = q->headdrop; in sfq_change()
681 maxdepth = q->maxdepth; in sfq_change()
682 maxflows = q->maxflows; in sfq_change()
683 quantum = q->quantum; in sfq_change()
684 flags = q->flags; in sfq_change()
687 if (ctl->quantum) in sfq_change()
688 quantum = ctl->quantum; in sfq_change()
689 if (ctl->flows) in sfq_change()
690 maxflows = min_t(u32, ctl->flows, SFQ_MAX_FLOWS); in sfq_change()
691 if (ctl->divisor) { in sfq_change()
692 divisor = ctl->divisor; in sfq_change()
696 if (ctl_v1->depth) in sfq_change()
697 maxdepth = min_t(u32, ctl_v1->depth, SFQ_MAX_DEPTH); in sfq_change()
700 ctl_v1->qth_min, ctl_v1->qth_max, in sfq_change()
701 ctl_v1->Wlog, in sfq_change()
702 ctl_v1->Plog, ctl_v1->Scell_log, in sfq_change()
704 ctl_v1->max_P); in sfq_change()
706 flags = ctl_v1->flags; in sfq_change()
707 headdrop = ctl_v1->headdrop; in sfq_change()
709 if (ctl->limit) { in sfq_change()
710 limit = min_t(u32, ctl->limit, maxdepth * maxflows); in sfq_change()
717 return -EINVAL; in sfq_change()
721 q->limit = limit; in sfq_change()
722 q->divisor = divisor; in sfq_change()
723 q->headdrop = headdrop; in sfq_change()
724 q->maxdepth = maxdepth; in sfq_change()
725 q->maxflows = maxflows; in sfq_change()
726 WRITE_ONCE(q->perturb_period, perturb_period); in sfq_change()
727 q->quantum = quantum; in sfq_change()
728 q->flags = flags; in sfq_change()
730 swap(q->red_parms, p); in sfq_change()
732 qlen = sch->q.qlen; in sfq_change()
733 while (sch->q.qlen > q->limit) { in sfq_change()
740 qdisc_tree_reduce_backlog(sch, qlen - sch->q.qlen, dropped); in sfq_change()
742 timer_delete(&q->perturb_timer); in sfq_change()
743 if (q->perturb_period) { in sfq_change()
744 mod_timer(&q->perturb_timer, jiffies + q->perturb_period); in sfq_change()
745 get_random_bytes(&q->perturbation, sizeof(q->perturbation)); in sfq_change()
766 tcf_block_put(q->block); in sfq_destroy()
767 WRITE_ONCE(q->perturb_period, 0); in sfq_destroy()
768 timer_delete_sync(&q->perturb_timer); in sfq_destroy()
769 sfq_free(q->ht); in sfq_destroy()
770 sfq_free(q->slots); in sfq_destroy()
771 kfree(q->red_parms); in sfq_destroy()
781 q->sch = sch; in sfq_init()
782 timer_setup(&q->perturb_timer, sfq_perturbation, TIMER_DEFERRABLE); in sfq_init()
784 err = tcf_block_get(&q->block, &q->filter_list, sch, extack); in sfq_init()
789 q->dep[i].next = i + SFQ_MAX_FLOWS; in sfq_init()
790 q->dep[i].prev = i + SFQ_MAX_FLOWS; in sfq_init()
793 q->limit = SFQ_MAX_DEPTH; in sfq_init()
794 q->maxdepth = SFQ_MAX_DEPTH; in sfq_init()
795 q->cur_depth = 0; in sfq_init()
796 q->tail = NULL; in sfq_init()
797 q->divisor = SFQ_DEFAULT_HASH_DIVISOR; in sfq_init()
798 q->maxflows = SFQ_DEFAULT_FLOWS; in sfq_init()
799 q->quantum = psched_mtu(qdisc_dev(sch)); in sfq_init()
800 q->perturb_period = 0; in sfq_init()
801 get_random_bytes(&q->perturbation, sizeof(q->perturbation)); in sfq_init()
809 q->ht = sfq_alloc(sizeof(q->ht[0]) * q->divisor); in sfq_init()
810 q->slots = sfq_alloc(sizeof(q->slots[0]) * q->maxflows); in sfq_init()
811 if (!q->ht || !q->slots) { in sfq_init()
813 return -ENOMEM; in sfq_init()
816 for (i = 0; i < q->divisor; i++) in sfq_init()
817 q->ht[i] = SFQ_EMPTY_SLOT; in sfq_init()
819 for (i = 0; i < q->maxflows; i++) { in sfq_init()
820 slot_queue_init(&q->slots[i]); in sfq_init()
823 if (q->limit >= 1) in sfq_init()
824 sch->flags |= TCQ_F_CAN_BYPASS; in sfq_init()
826 sch->flags &= ~TCQ_F_CAN_BYPASS; in sfq_init()
835 struct red_parms *p = q->red_parms; in sfq_dump()
838 opt.v0.quantum = q->quantum; in sfq_dump()
839 opt.v0.perturb_period = q->perturb_period / HZ; in sfq_dump()
840 opt.v0.limit = q->limit; in sfq_dump()
841 opt.v0.divisor = q->divisor; in sfq_dump()
842 opt.v0.flows = q->maxflows; in sfq_dump()
843 opt.depth = q->maxdepth; in sfq_dump()
844 opt.headdrop = q->headdrop; in sfq_dump()
847 opt.qth_min = p->qth_min >> p->Wlog; in sfq_dump()
848 opt.qth_max = p->qth_max >> p->Wlog; in sfq_dump()
849 opt.Wlog = p->Wlog; in sfq_dump()
850 opt.Plog = p->Plog; in sfq_dump()
851 opt.Scell_log = p->Scell_log; in sfq_dump()
852 opt.max_P = p->max_P; in sfq_dump()
854 memcpy(&opt.stats, &q->stats, sizeof(opt.stats)); in sfq_dump()
855 opt.flags = q->flags; in sfq_dump()
860 return skb->len; in sfq_dump()
864 return -1; in sfq_dump()
894 return q->block; in sfq_tcf_block()
900 tcm->tcm_handle |= TC_H_MIN(cl); in sfq_dump_class()
908 sfq_index idx = q->ht[cl - 1]; in sfq_dump_class_stats()
913 const struct sfq_slot *slot = &q->slots[idx]; in sfq_dump_class_stats() local
915 xstats.allot = slot->allot; in sfq_dump_class_stats()
916 qs.qlen = slot->qlen; in sfq_dump_class_stats()
917 qs.backlog = slot->backlog; in sfq_dump_class_stats()
920 return -1; in sfq_dump_class_stats()
929 if (arg->stop) in sfq_walk()
932 for (i = 0; i < q->divisor; i++) { in sfq_walk()
933 if (q->ht[i] == SFQ_EMPTY_SLOT) { in sfq_walk()
934 arg->count++; in sfq_walk()