1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * net/sched/sch_fq.c Fair Queue Packet Scheduler (per flow pacing)
5 * Copyright (C) 2013-2015 Eric Dumazet <edumazet@google.com>
7 * Meant to be mostly used for locally generated traffic :
8 * Fast classification depends on skb->sk being set before reaching us.
9 * If not, (router workload), we use rxhash as fallback, with 32 bits wide hash.
10 * All packets belonging to a socket are considered as a 'flow'.
12 * Flows are dynamically allocated and stored in a hash table of RB trees
13 * They are also part of one Round Robin 'queues' (new or old flows)
15 * Burst avoidance (aka pacing) capability :
17 * Transport (eg TCP) can set in sk->sk_pacing_rate a rate, enqueue a
18 * bunch of packets, and this packet scheduler adds delay between
19 * packets to respect rate limitation.
22 * - lookup one RB tree (out of 1024 or more) to find the flow.
23 * If non existent flow, create it, add it to the tree.
24 * Add skb to the per flow list of skb (fifo).
25 * - Use a special fifo for high prio packets
27 * dequeue() : serves flows in Round Robin
28 * Note : When a flow becomes empty, we do not immediately remove it from
29 * rb trees, for performance reasons (its expected to send additional packets,
30 * or SLAB cache will reuse socket for another flow)
33 #include <linux/module.h>
34 #include <linux/types.h>
35 #include <linux/kernel.h>
36 #include <linux/jiffies.h>
37 #include <linux/string.h>
39 #include <linux/errno.h>
40 #include <linux/init.h>
41 #include <linux/skbuff.h>
42 #include <linux/slab.h>
43 #include <linux/rbtree.h>
44 #include <linux/hash.h>
45 #include <linux/prefetch.h>
46 #include <linux/vmalloc.h>
47 #include <net/netlink.h>
48 #include <net/pkt_sched.h>
50 #include <net/tcp_states.h>
57 static inline struct fq_skb_cb
*fq_skb_cb(struct sk_buff
*skb
)
59 qdisc_cb_private_validate(skb
, sizeof(struct fq_skb_cb
));
60 return (struct fq_skb_cb
*)qdisc_skb_cb(skb
)->data
;
64 * Per flow structure, dynamically allocated.
65 * If packets have monotically increasing time_to_send, they are placed in O(1)
66 * in linear list (head,tail), otherwise are placed in a rbtree (t_root).
69 struct rb_root t_root
;
70 struct sk_buff
*head
; /* list of skbs for this flow : first skb */
72 struct sk_buff
*tail
; /* last skb in the list */
73 unsigned long age
; /* jiffies when flow was emptied, for gc */
75 struct rb_node fq_node
; /* anchor in fq_root[] trees */
77 int qlen
; /* number of packets in flow queue */
79 u32 socket_hash
; /* sk_hash */
80 struct fq_flow
*next
; /* next pointer in RR lists, or &detached */
82 struct rb_node rate_node
; /* anchor in q->delayed tree */
87 struct fq_flow
*first
;
91 struct fq_sched_data
{
92 struct fq_flow_head new_flows
;
94 struct fq_flow_head old_flows
;
96 struct rb_root delayed
; /* for rate limited flows */
97 u64 time_next_delayed_flow
;
98 unsigned long unthrottle_latency_ns
;
100 struct fq_flow internal
; /* for non classified or high prio packets */
103 u32 flow_refill_delay
;
104 u32 flow_plimit
; /* max packets per flow */
105 unsigned long flow_max_rate
; /* optional max rate per flow */
107 u32 orphan_mask
; /* mask for orphaned skb */
108 u32 low_rate_threshold
;
109 struct rb_root
*fq_root
;
118 u64 stat_internal_packets
;
121 u64 stat_flows_plimit
;
122 u64 stat_pkts_too_long
;
123 u64 stat_allocation_errors
;
124 struct qdisc_watchdog watchdog
;
127 /* special value to mark a detached flow (not on old/new list) */
128 static struct fq_flow detached
, throttled
;
130 static void fq_flow_set_detached(struct fq_flow
*f
)
136 static bool fq_flow_is_detached(const struct fq_flow
*f
)
138 return f
->next
== &detached
;
141 static bool fq_flow_is_throttled(const struct fq_flow
*f
)
143 return f
->next
== &throttled
;
146 static void fq_flow_add_tail(struct fq_flow_head
*head
, struct fq_flow
*flow
)
149 head
->last
->next
= flow
;
156 static void fq_flow_unset_throttled(struct fq_sched_data
*q
, struct fq_flow
*f
)
158 rb_erase(&f
->rate_node
, &q
->delayed
);
159 q
->throttled_flows
--;
160 fq_flow_add_tail(&q
->old_flows
, f
);
163 static void fq_flow_set_throttled(struct fq_sched_data
*q
, struct fq_flow
*f
)
165 struct rb_node
**p
= &q
->delayed
.rb_node
, *parent
= NULL
;
171 aux
= rb_entry(parent
, struct fq_flow
, rate_node
);
172 if (f
->time_next_packet
>= aux
->time_next_packet
)
173 p
= &parent
->rb_right
;
175 p
= &parent
->rb_left
;
177 rb_link_node(&f
->rate_node
, parent
, p
);
178 rb_insert_color(&f
->rate_node
, &q
->delayed
);
179 q
->throttled_flows
++;
182 f
->next
= &throttled
;
183 if (q
->time_next_delayed_flow
> f
->time_next_packet
)
184 q
->time_next_delayed_flow
= f
->time_next_packet
;
188 static struct kmem_cache
*fq_flow_cachep __read_mostly
;
191 /* limit number of collected flows per round */
193 #define FQ_GC_AGE (3*HZ)
195 static bool fq_gc_candidate(const struct fq_flow
*f
)
197 return fq_flow_is_detached(f
) &&
198 time_after(jiffies
, f
->age
+ FQ_GC_AGE
);
201 static void fq_gc(struct fq_sched_data
*q
,
202 struct rb_root
*root
,
205 struct fq_flow
*f
, *tofree
[FQ_GC_MAX
];
206 struct rb_node
**p
, *parent
;
214 f
= rb_entry(parent
, struct fq_flow
, fq_node
);
218 if (fq_gc_candidate(f
)) {
220 if (fcnt
== FQ_GC_MAX
)
225 p
= &parent
->rb_right
;
227 p
= &parent
->rb_left
;
231 q
->inactive_flows
-= fcnt
;
232 q
->stat_gc_flows
+= fcnt
;
234 struct fq_flow
*f
= tofree
[--fcnt
];
236 rb_erase(&f
->fq_node
, root
);
237 kmem_cache_free(fq_flow_cachep
, f
);
241 static struct fq_flow
*fq_classify(struct sk_buff
*skb
, struct fq_sched_data
*q
)
243 struct rb_node
**p
, *parent
;
244 struct sock
*sk
= skb
->sk
;
245 struct rb_root
*root
;
248 /* warning: no starvation prevention... */
249 if (unlikely((skb
->priority
& TC_PRIO_MAX
) == TC_PRIO_CONTROL
))
252 /* SYNACK messages are attached to a TCP_NEW_SYN_RECV request socket
253 * or a listener (SYNCOOKIE mode)
254 * 1) request sockets are not full blown,
255 * they do not contain sk_pacing_rate
256 * 2) They are not part of a 'flow' yet
257 * 3) We do not want to rate limit them (eg SYNFLOOD attack),
258 * especially if the listener set SO_MAX_PACING_RATE
259 * 4) We pretend they are orphaned
261 if (!sk
|| sk_listener(sk
)) {
262 unsigned long hash
= skb_get_hash(skb
) & q
->orphan_mask
;
264 /* By forcing low order bit to 1, we make sure to not
265 * collide with a local flow (socket pointers are word aligned)
267 sk
= (struct sock
*)((hash
<< 1) | 1UL);
269 } else if (sk
->sk_state
== TCP_CLOSE
) {
270 unsigned long hash
= skb_get_hash(skb
) & q
->orphan_mask
;
272 * Sockets in TCP_CLOSE are non connected.
273 * Typical use case is UDP sockets, they can send packets
274 * with sendto() to many different destinations.
275 * We probably could use a generic bit advertising
276 * non connected sockets, instead of sk_state == TCP_CLOSE,
279 sk
= (struct sock
*)((hash
<< 1) | 1UL);
282 root
= &q
->fq_root
[hash_ptr(sk
, q
->fq_trees_log
)];
284 if (q
->flows
>= (2U << q
->fq_trees_log
) &&
285 q
->inactive_flows
> q
->flows
/2)
293 f
= rb_entry(parent
, struct fq_flow
, fq_node
);
295 /* socket might have been reallocated, so check
296 * if its sk_hash is the same.
297 * It not, we need to refill credit with
300 if (unlikely(skb
->sk
== sk
&&
301 f
->socket_hash
!= sk
->sk_hash
)) {
302 f
->credit
= q
->initial_quantum
;
303 f
->socket_hash
= sk
->sk_hash
;
305 smp_store_release(&sk
->sk_pacing_status
,
307 if (fq_flow_is_throttled(f
))
308 fq_flow_unset_throttled(q
, f
);
309 f
->time_next_packet
= 0ULL;
314 p
= &parent
->rb_right
;
316 p
= &parent
->rb_left
;
319 f
= kmem_cache_zalloc(fq_flow_cachep
, GFP_ATOMIC
| __GFP_NOWARN
);
321 q
->stat_allocation_errors
++;
324 /* f->t_root is already zeroed after kmem_cache_zalloc() */
326 fq_flow_set_detached(f
);
329 f
->socket_hash
= sk
->sk_hash
;
331 smp_store_release(&sk
->sk_pacing_status
,
334 f
->credit
= q
->initial_quantum
;
336 rb_link_node(&f
->fq_node
, parent
, p
);
337 rb_insert_color(&f
->fq_node
, root
);
344 static struct sk_buff
*fq_peek(struct fq_flow
*flow
)
346 struct sk_buff
*skb
= skb_rb_first(&flow
->t_root
);
347 struct sk_buff
*head
= flow
->head
;
355 if (fq_skb_cb(skb
)->time_to_send
< fq_skb_cb(head
)->time_to_send
)
360 static void fq_erase_head(struct Qdisc
*sch
, struct fq_flow
*flow
,
363 if (skb
== flow
->head
) {
364 flow
->head
= skb
->next
;
366 rb_erase(&skb
->rbnode
, &flow
->t_root
);
367 skb
->dev
= qdisc_dev(sch
);
371 /* remove one skb from head of flow queue */
372 static struct sk_buff
*fq_dequeue_head(struct Qdisc
*sch
, struct fq_flow
*flow
)
374 struct sk_buff
*skb
= fq_peek(flow
);
377 fq_erase_head(sch
, flow
, skb
);
378 skb_mark_not_on_list(skb
);
380 qdisc_qstats_backlog_dec(sch
, skb
);
386 static void flow_queue_add(struct fq_flow
*flow
, struct sk_buff
*skb
)
388 struct rb_node
**p
, *parent
;
389 struct sk_buff
*head
, *aux
;
391 fq_skb_cb(skb
)->time_to_send
= skb
->tstamp
?: ktime_get_ns();
395 fq_skb_cb(skb
)->time_to_send
>= fq_skb_cb(flow
->tail
)->time_to_send
) {
399 flow
->tail
->next
= skb
;
405 p
= &flow
->t_root
.rb_node
;
410 aux
= rb_to_skb(parent
);
411 if (fq_skb_cb(skb
)->time_to_send
>= fq_skb_cb(aux
)->time_to_send
)
412 p
= &parent
->rb_right
;
414 p
= &parent
->rb_left
;
416 rb_link_node(&skb
->rbnode
, parent
, p
);
417 rb_insert_color(&skb
->rbnode
, &flow
->t_root
);
420 static int fq_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
,
421 struct sk_buff
**to_free
)
423 struct fq_sched_data
*q
= qdisc_priv(sch
);
426 if (unlikely(sch
->q
.qlen
>= sch
->limit
))
427 return qdisc_drop(skb
, sch
, to_free
);
429 f
= fq_classify(skb
, q
);
430 if (unlikely(f
->qlen
>= q
->flow_plimit
&& f
!= &q
->internal
)) {
431 q
->stat_flows_plimit
++;
432 return qdisc_drop(skb
, sch
, to_free
);
436 qdisc_qstats_backlog_inc(sch
, skb
);
437 if (fq_flow_is_detached(f
)) {
438 fq_flow_add_tail(&q
->new_flows
, f
);
439 if (time_after(jiffies
, f
->age
+ q
->flow_refill_delay
))
440 f
->credit
= max_t(u32
, f
->credit
, q
->quantum
);
444 /* Note: this overwrites f->age */
445 flow_queue_add(f
, skb
);
447 if (unlikely(f
== &q
->internal
)) {
448 q
->stat_internal_packets
++;
452 return NET_XMIT_SUCCESS
;
455 static void fq_check_throttled(struct fq_sched_data
*q
, u64 now
)
457 unsigned long sample
;
460 if (q
->time_next_delayed_flow
> now
)
463 /* Update unthrottle latency EWMA.
464 * This is cheap and can help diagnosing timer/latency problems.
466 sample
= (unsigned long)(now
- q
->time_next_delayed_flow
);
467 q
->unthrottle_latency_ns
-= q
->unthrottle_latency_ns
>> 3;
468 q
->unthrottle_latency_ns
+= sample
>> 3;
470 q
->time_next_delayed_flow
= ~0ULL;
471 while ((p
= rb_first(&q
->delayed
)) != NULL
) {
472 struct fq_flow
*f
= rb_entry(p
, struct fq_flow
, rate_node
);
474 if (f
->time_next_packet
> now
) {
475 q
->time_next_delayed_flow
= f
->time_next_packet
;
478 fq_flow_unset_throttled(q
, f
);
482 static struct sk_buff
*fq_dequeue(struct Qdisc
*sch
)
484 struct fq_sched_data
*q
= qdisc_priv(sch
);
485 struct fq_flow_head
*head
;
495 skb
= fq_dequeue_head(sch
, &q
->internal
);
499 now
= ktime_get_ns();
500 fq_check_throttled(q
, now
);
502 head
= &q
->new_flows
;
504 head
= &q
->old_flows
;
506 if (q
->time_next_delayed_flow
!= ~0ULL)
507 qdisc_watchdog_schedule_ns(&q
->watchdog
,
508 q
->time_next_delayed_flow
);
514 if (f
->credit
<= 0) {
515 f
->credit
+= q
->quantum
;
516 head
->first
= f
->next
;
517 fq_flow_add_tail(&q
->old_flows
, f
);
523 u64 time_next_packet
= max_t(u64
, fq_skb_cb(skb
)->time_to_send
,
524 f
->time_next_packet
);
526 if (now
< time_next_packet
) {
527 head
->first
= f
->next
;
528 f
->time_next_packet
= time_next_packet
;
529 fq_flow_set_throttled(q
, f
);
532 if ((s64
)(now
- time_next_packet
- q
->ce_threshold
) > 0) {
533 INET_ECN_set_ce(skb
);
538 skb
= fq_dequeue_head(sch
, f
);
540 head
->first
= f
->next
;
541 /* force a pass through old_flows to prevent starvation */
542 if ((head
== &q
->new_flows
) && q
->old_flows
.first
) {
543 fq_flow_add_tail(&q
->old_flows
, f
);
545 fq_flow_set_detached(f
);
551 plen
= qdisc_pkt_len(skb
);
557 rate
= q
->flow_max_rate
;
559 /* If EDT time was provided for this skb, we need to
560 * update f->time_next_packet only if this qdisc enforces
565 rate
= min(skb
->sk
->sk_pacing_rate
, rate
);
567 if (rate
<= q
->low_rate_threshold
) {
570 plen
= max(plen
, q
->quantum
);
576 u64 len
= (u64
)plen
* NSEC_PER_SEC
;
579 len
= div64_ul(len
, rate
);
580 /* Since socket rate can change later,
581 * clamp the delay to 1 second.
582 * Really, providers of too big packets should be fixed !
584 if (unlikely(len
> NSEC_PER_SEC
)) {
586 q
->stat_pkts_too_long
++;
588 /* Account for schedule/timers drifts.
589 * f->time_next_packet was set when prior packet was sent,
590 * and current time (@now) can be too late by tens of us.
592 if (f
->time_next_packet
)
593 len
-= min(len
/2, now
- f
->time_next_packet
);
594 f
->time_next_packet
= now
+ len
;
597 qdisc_bstats_update(sch
, skb
);
601 static void fq_flow_purge(struct fq_flow
*flow
)
603 struct rb_node
*p
= rb_first(&flow
->t_root
);
606 struct sk_buff
*skb
= rb_to_skb(p
);
609 rb_erase(&skb
->rbnode
, &flow
->t_root
);
610 rtnl_kfree_skbs(skb
, skb
);
612 rtnl_kfree_skbs(flow
->head
, flow
->tail
);
617 static void fq_reset(struct Qdisc
*sch
)
619 struct fq_sched_data
*q
= qdisc_priv(sch
);
620 struct rb_root
*root
;
626 sch
->qstats
.backlog
= 0;
628 fq_flow_purge(&q
->internal
);
633 for (idx
= 0; idx
< (1U << q
->fq_trees_log
); idx
++) {
634 root
= &q
->fq_root
[idx
];
635 while ((p
= rb_first(root
)) != NULL
) {
636 f
= rb_entry(p
, struct fq_flow
, fq_node
);
641 kmem_cache_free(fq_flow_cachep
, f
);
644 q
->new_flows
.first
= NULL
;
645 q
->old_flows
.first
= NULL
;
646 q
->delayed
= RB_ROOT
;
648 q
->inactive_flows
= 0;
649 q
->throttled_flows
= 0;
652 static void fq_rehash(struct fq_sched_data
*q
,
653 struct rb_root
*old_array
, u32 old_log
,
654 struct rb_root
*new_array
, u32 new_log
)
656 struct rb_node
*op
, **np
, *parent
;
657 struct rb_root
*oroot
, *nroot
;
658 struct fq_flow
*of
, *nf
;
662 for (idx
= 0; idx
< (1U << old_log
); idx
++) {
663 oroot
= &old_array
[idx
];
664 while ((op
= rb_first(oroot
)) != NULL
) {
666 of
= rb_entry(op
, struct fq_flow
, fq_node
);
667 if (fq_gc_candidate(of
)) {
669 kmem_cache_free(fq_flow_cachep
, of
);
672 nroot
= &new_array
[hash_ptr(of
->sk
, new_log
)];
674 np
= &nroot
->rb_node
;
679 nf
= rb_entry(parent
, struct fq_flow
, fq_node
);
680 BUG_ON(nf
->sk
== of
->sk
);
683 np
= &parent
->rb_right
;
685 np
= &parent
->rb_left
;
688 rb_link_node(&of
->fq_node
, parent
, np
);
689 rb_insert_color(&of
->fq_node
, nroot
);
693 q
->inactive_flows
-= fcnt
;
694 q
->stat_gc_flows
+= fcnt
;
697 static void fq_free(void *addr
)
702 static int fq_resize(struct Qdisc
*sch
, u32 log
)
704 struct fq_sched_data
*q
= qdisc_priv(sch
);
705 struct rb_root
*array
;
709 if (q
->fq_root
&& log
== q
->fq_trees_log
)
712 /* If XPS was setup, we can allocate memory on right NUMA node */
713 array
= kvmalloc_node(sizeof(struct rb_root
) << log
, GFP_KERNEL
| __GFP_RETRY_MAYFAIL
,
714 netdev_queue_numa_node_read(sch
->dev_queue
));
718 for (idx
= 0; idx
< (1U << log
); idx
++)
719 array
[idx
] = RB_ROOT
;
723 old_fq_root
= q
->fq_root
;
725 fq_rehash(q
, old_fq_root
, q
->fq_trees_log
, array
, log
);
728 q
->fq_trees_log
= log
;
730 sch_tree_unlock(sch
);
732 fq_free(old_fq_root
);
737 static const struct nla_policy fq_policy
[TCA_FQ_MAX
+ 1] = {
738 [TCA_FQ_PLIMIT
] = { .type
= NLA_U32
},
739 [TCA_FQ_FLOW_PLIMIT
] = { .type
= NLA_U32
},
740 [TCA_FQ_QUANTUM
] = { .type
= NLA_U32
},
741 [TCA_FQ_INITIAL_QUANTUM
] = { .type
= NLA_U32
},
742 [TCA_FQ_RATE_ENABLE
] = { .type
= NLA_U32
},
743 [TCA_FQ_FLOW_DEFAULT_RATE
] = { .type
= NLA_U32
},
744 [TCA_FQ_FLOW_MAX_RATE
] = { .type
= NLA_U32
},
745 [TCA_FQ_BUCKETS_LOG
] = { .type
= NLA_U32
},
746 [TCA_FQ_FLOW_REFILL_DELAY
] = { .type
= NLA_U32
},
747 [TCA_FQ_LOW_RATE_THRESHOLD
] = { .type
= NLA_U32
},
748 [TCA_FQ_CE_THRESHOLD
] = { .type
= NLA_U32
},
751 static int fq_change(struct Qdisc
*sch
, struct nlattr
*opt
,
752 struct netlink_ext_ack
*extack
)
754 struct fq_sched_data
*q
= qdisc_priv(sch
);
755 struct nlattr
*tb
[TCA_FQ_MAX
+ 1];
756 int err
, drop_count
= 0;
757 unsigned drop_len
= 0;
763 err
= nla_parse_nested_deprecated(tb
, TCA_FQ_MAX
, opt
, fq_policy
,
770 fq_log
= q
->fq_trees_log
;
772 if (tb
[TCA_FQ_BUCKETS_LOG
]) {
773 u32 nval
= nla_get_u32(tb
[TCA_FQ_BUCKETS_LOG
]);
775 if (nval
>= 1 && nval
<= ilog2(256*1024))
780 if (tb
[TCA_FQ_PLIMIT
])
781 sch
->limit
= nla_get_u32(tb
[TCA_FQ_PLIMIT
]);
783 if (tb
[TCA_FQ_FLOW_PLIMIT
])
784 q
->flow_plimit
= nla_get_u32(tb
[TCA_FQ_FLOW_PLIMIT
]);
786 if (tb
[TCA_FQ_QUANTUM
]) {
787 u32 quantum
= nla_get_u32(tb
[TCA_FQ_QUANTUM
]);
789 if (quantum
> 0 && quantum
<= (1 << 20)) {
790 q
->quantum
= quantum
;
792 NL_SET_ERR_MSG_MOD(extack
, "invalid quantum");
797 if (tb
[TCA_FQ_INITIAL_QUANTUM
])
798 q
->initial_quantum
= nla_get_u32(tb
[TCA_FQ_INITIAL_QUANTUM
]);
800 if (tb
[TCA_FQ_FLOW_DEFAULT_RATE
])
801 pr_warn_ratelimited("sch_fq: defrate %u ignored.\n",
802 nla_get_u32(tb
[TCA_FQ_FLOW_DEFAULT_RATE
]));
804 if (tb
[TCA_FQ_FLOW_MAX_RATE
]) {
805 u32 rate
= nla_get_u32(tb
[TCA_FQ_FLOW_MAX_RATE
]);
807 q
->flow_max_rate
= (rate
== ~0U) ? ~0UL : rate
;
809 if (tb
[TCA_FQ_LOW_RATE_THRESHOLD
])
810 q
->low_rate_threshold
=
811 nla_get_u32(tb
[TCA_FQ_LOW_RATE_THRESHOLD
]);
813 if (tb
[TCA_FQ_RATE_ENABLE
]) {
814 u32 enable
= nla_get_u32(tb
[TCA_FQ_RATE_ENABLE
]);
817 q
->rate_enable
= enable
;
822 if (tb
[TCA_FQ_FLOW_REFILL_DELAY
]) {
823 u32 usecs_delay
= nla_get_u32(tb
[TCA_FQ_FLOW_REFILL_DELAY
]) ;
825 q
->flow_refill_delay
= usecs_to_jiffies(usecs_delay
);
828 if (tb
[TCA_FQ_ORPHAN_MASK
])
829 q
->orphan_mask
= nla_get_u32(tb
[TCA_FQ_ORPHAN_MASK
]);
831 if (tb
[TCA_FQ_CE_THRESHOLD
])
832 q
->ce_threshold
= (u64
)NSEC_PER_USEC
*
833 nla_get_u32(tb
[TCA_FQ_CE_THRESHOLD
]);
836 sch_tree_unlock(sch
);
837 err
= fq_resize(sch
, fq_log
);
840 while (sch
->q
.qlen
> sch
->limit
) {
841 struct sk_buff
*skb
= fq_dequeue(sch
);
845 drop_len
+= qdisc_pkt_len(skb
);
846 rtnl_kfree_skbs(skb
, skb
);
849 qdisc_tree_reduce_backlog(sch
, drop_count
, drop_len
);
851 sch_tree_unlock(sch
);
855 static void fq_destroy(struct Qdisc
*sch
)
857 struct fq_sched_data
*q
= qdisc_priv(sch
);
861 qdisc_watchdog_cancel(&q
->watchdog
);
864 static int fq_init(struct Qdisc
*sch
, struct nlattr
*opt
,
865 struct netlink_ext_ack
*extack
)
867 struct fq_sched_data
*q
= qdisc_priv(sch
);
871 q
->flow_plimit
= 100;
872 q
->quantum
= 2 * psched_mtu(qdisc_dev(sch
));
873 q
->initial_quantum
= 10 * psched_mtu(qdisc_dev(sch
));
874 q
->flow_refill_delay
= msecs_to_jiffies(40);
875 q
->flow_max_rate
= ~0UL;
876 q
->time_next_delayed_flow
= ~0ULL;
878 q
->new_flows
.first
= NULL
;
879 q
->old_flows
.first
= NULL
;
880 q
->delayed
= RB_ROOT
;
882 q
->fq_trees_log
= ilog2(1024);
883 q
->orphan_mask
= 1024 - 1;
884 q
->low_rate_threshold
= 550000 / 8;
886 /* Default ce_threshold of 4294 seconds */
887 q
->ce_threshold
= (u64
)NSEC_PER_USEC
* ~0U;
889 qdisc_watchdog_init_clockid(&q
->watchdog
, sch
, CLOCK_MONOTONIC
);
892 err
= fq_change(sch
, opt
, extack
);
894 err
= fq_resize(sch
, q
->fq_trees_log
);
899 static int fq_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
901 struct fq_sched_data
*q
= qdisc_priv(sch
);
902 u64 ce_threshold
= q
->ce_threshold
;
905 opts
= nla_nest_start_noflag(skb
, TCA_OPTIONS
);
907 goto nla_put_failure
;
909 /* TCA_FQ_FLOW_DEFAULT_RATE is not used anymore */
911 do_div(ce_threshold
, NSEC_PER_USEC
);
913 if (nla_put_u32(skb
, TCA_FQ_PLIMIT
, sch
->limit
) ||
914 nla_put_u32(skb
, TCA_FQ_FLOW_PLIMIT
, q
->flow_plimit
) ||
915 nla_put_u32(skb
, TCA_FQ_QUANTUM
, q
->quantum
) ||
916 nla_put_u32(skb
, TCA_FQ_INITIAL_QUANTUM
, q
->initial_quantum
) ||
917 nla_put_u32(skb
, TCA_FQ_RATE_ENABLE
, q
->rate_enable
) ||
918 nla_put_u32(skb
, TCA_FQ_FLOW_MAX_RATE
,
919 min_t(unsigned long, q
->flow_max_rate
, ~0U)) ||
920 nla_put_u32(skb
, TCA_FQ_FLOW_REFILL_DELAY
,
921 jiffies_to_usecs(q
->flow_refill_delay
)) ||
922 nla_put_u32(skb
, TCA_FQ_ORPHAN_MASK
, q
->orphan_mask
) ||
923 nla_put_u32(skb
, TCA_FQ_LOW_RATE_THRESHOLD
,
924 q
->low_rate_threshold
) ||
925 nla_put_u32(skb
, TCA_FQ_CE_THRESHOLD
, (u32
)ce_threshold
) ||
926 nla_put_u32(skb
, TCA_FQ_BUCKETS_LOG
, q
->fq_trees_log
))
927 goto nla_put_failure
;
929 return nla_nest_end(skb
, opts
);
935 static int fq_dump_stats(struct Qdisc
*sch
, struct gnet_dump
*d
)
937 struct fq_sched_data
*q
= qdisc_priv(sch
);
938 struct tc_fq_qd_stats st
;
942 st
.gc_flows
= q
->stat_gc_flows
;
943 st
.highprio_packets
= q
->stat_internal_packets
;
945 st
.throttled
= q
->stat_throttled
;
946 st
.flows_plimit
= q
->stat_flows_plimit
;
947 st
.pkts_too_long
= q
->stat_pkts_too_long
;
948 st
.allocation_errors
= q
->stat_allocation_errors
;
949 st
.time_next_delayed_flow
= q
->time_next_delayed_flow
- ktime_get_ns();
951 st
.inactive_flows
= q
->inactive_flows
;
952 st
.throttled_flows
= q
->throttled_flows
;
953 st
.unthrottle_latency_ns
= min_t(unsigned long,
954 q
->unthrottle_latency_ns
, ~0U);
955 st
.ce_mark
= q
->stat_ce_mark
;
956 sch_tree_unlock(sch
);
958 return gnet_stats_copy_app(d
, &st
, sizeof(st
));
961 static struct Qdisc_ops fq_qdisc_ops __read_mostly
= {
963 .priv_size
= sizeof(struct fq_sched_data
),
965 .enqueue
= fq_enqueue
,
966 .dequeue
= fq_dequeue
,
967 .peek
= qdisc_peek_dequeued
,
970 .destroy
= fq_destroy
,
973 .dump_stats
= fq_dump_stats
,
974 .owner
= THIS_MODULE
,
977 static int __init
fq_module_init(void)
981 fq_flow_cachep
= kmem_cache_create("fq_flow_cache",
982 sizeof(struct fq_flow
),
987 ret
= register_qdisc(&fq_qdisc_ops
);
989 kmem_cache_destroy(fq_flow_cachep
);
993 static void __exit
fq_module_exit(void)
995 unregister_qdisc(&fq_qdisc_ops
);
996 kmem_cache_destroy(fq_flow_cachep
);
999 module_init(fq_module_init
)
1000 module_exit(fq_module_exit
)
1001 MODULE_AUTHOR("Eric Dumazet");
1002 MODULE_LICENSE("GPL");