]>
git.ipfire.org Git - thirdparty/kernel/linux.git/blob - lib/dynamic_queue_limits.c
1 // SPDX-License-Identifier: GPL-2.0
3 * Dynamic byte queue limits. See include/linux/dynamic_queue_limits.h
5 * Copyright (c) 2011, Tom Herbert <therbert@google.com>
7 #include <linux/types.h>
8 #include <linux/kernel.h>
9 #include <linux/jiffies.h>
10 #include <linux/dynamic_queue_limits.h>
11 #include <linux/compiler.h>
12 #include <linux/export.h>
13 #include <trace/events/napi.h>
15 #define POSDIFF(A, B) ((int)((A) - (B)) > 0 ? (A) - (B) : 0)
16 #define AFTER_EQ(A, B) ((int)((A) - (B)) >= 0)
18 static void dql_check_stall(struct dql
*dql
)
20 unsigned short stall_thrs
;
23 stall_thrs
= READ_ONCE(dql
->stall_thrs
);
28 /* Check for a potential stall */
29 if (time_after_eq(now
, dql
->last_reap
+ stall_thrs
)) {
30 unsigned long hist_head
, t
, start
, end
;
32 /* We are trying to detect a period of at least @stall_thrs
33 * jiffies without any Tx completions, but during first half
34 * of which some Tx was posted.
37 hist_head
= READ_ONCE(dql
->history_head
);
38 /* pairs with smp_wmb() in dql_queued() */
41 /* Get the previous entry in the ring buffer, which is the
44 start
= (hist_head
- DQL_HIST_LEN
+ 1) * BITS_PER_LONG
;
46 /* Advance start to continue from the last reap time */
47 if (time_before(start
, dql
->last_reap
+ 1))
48 start
= dql
->last_reap
+ 1;
50 /* Newest sample we should have already seen a completion for */
51 end
= hist_head
* BITS_PER_LONG
+ (BITS_PER_LONG
- 1);
53 /* Shrink the search space to [start, (now - start_thrs/2)] if
54 * `end` is beyond the stall zone
56 if (time_before(now
, end
+ stall_thrs
/ 2))
57 end
= now
- stall_thrs
/ 2;
59 /* Search for the queued time in [t, end] */
60 for (t
= start
; time_before_eq(t
, end
); t
++)
61 if (test_bit(t
% (DQL_HIST_LEN
* BITS_PER_LONG
),
65 /* Variable t contains the time of the queue */
66 if (!time_before_eq(t
, end
))
69 /* The ring buffer was modified in the meantime, retry */
70 if (hist_head
!= READ_ONCE(dql
->history_head
))
74 dql
->stall_max
= max_t(unsigned short, dql
->stall_max
, now
- t
);
76 trace_dql_stall_detected(dql
->stall_thrs
, now
- t
,
77 dql
->last_reap
, dql
->history_head
,
84 /* Records completed count and recalculates the queue limit */
85 void dql_completed(struct dql
*dql
, unsigned int count
)
87 unsigned int inprogress
, prev_inprogress
, limit
;
88 unsigned int ovlimit
, completed
, num_queued
;
89 bool all_prev_completed
;
91 num_queued
= READ_ONCE(dql
->num_queued
);
93 /* Can't complete more than what's in queue */
94 BUG_ON(count
> num_queued
- dql
->num_completed
);
96 completed
= dql
->num_completed
+ count
;
98 ovlimit
= POSDIFF(num_queued
- dql
->num_completed
, limit
);
99 inprogress
= num_queued
- completed
;
100 prev_inprogress
= dql
->prev_num_queued
- dql
->num_completed
;
101 all_prev_completed
= AFTER_EQ(completed
, dql
->prev_num_queued
);
103 if ((ovlimit
&& !inprogress
) ||
104 (dql
->prev_ovlimit
&& all_prev_completed
)) {
106 * Queue considered starved if:
107 * - The queue was over-limit in the last interval,
108 * and there is no more data in the queue.
110 * - The queue was over-limit in the previous interval and
111 * when enqueuing it was possible that all queued data
112 * had been consumed. This covers the case when queue
113 * may have becomes starved between completion processing
114 * running and next time enqueue was scheduled.
116 * When queue is starved increase the limit by the amount
117 * of bytes both sent and completed in the last interval,
118 * plus any previous over-limit.
120 limit
+= POSDIFF(completed
, dql
->prev_num_queued
) +
122 dql
->slack_start_time
= jiffies
;
123 dql
->lowest_slack
= UINT_MAX
;
124 } else if (inprogress
&& prev_inprogress
&& !all_prev_completed
) {
126 * Queue was not starved, check if the limit can be decreased.
127 * A decrease is only considered if the queue has been busy in
128 * the whole interval (the check above).
130 * If there is slack, the amount of excess data queued above
131 * the amount needed to prevent starvation, the queue limit
132 * can be decreased. To avoid hysteresis we consider the
133 * minimum amount of slack found over several iterations of the
134 * completion routine.
136 unsigned int slack
, slack_last_objs
;
139 * Slack is the maximum of
140 * - The queue limit plus previous over-limit minus twice
141 * the number of objects completed. Note that two times
142 * number of completed bytes is a basis for an upper bound
144 * - Portion of objects in the last queuing operation that
145 * was not part of non-zero previous over-limit. That is
146 * "round down" by non-overlimit portion of the last
147 * queueing operation.
149 slack
= POSDIFF(limit
+ dql
->prev_ovlimit
,
150 2 * (completed
- dql
->num_completed
));
151 slack_last_objs
= dql
->prev_ovlimit
?
152 POSDIFF(dql
->prev_last_obj_cnt
, dql
->prev_ovlimit
) : 0;
154 slack
= max(slack
, slack_last_objs
);
156 if (slack
< dql
->lowest_slack
)
157 dql
->lowest_slack
= slack
;
159 if (time_after(jiffies
,
160 dql
->slack_start_time
+ dql
->slack_hold_time
)) {
161 limit
= POSDIFF(limit
, dql
->lowest_slack
);
162 dql
->slack_start_time
= jiffies
;
163 dql
->lowest_slack
= UINT_MAX
;
167 /* Enforce bounds on limit */
168 limit
= clamp(limit
, dql
->min_limit
, dql
->max_limit
);
170 if (limit
!= dql
->limit
) {
175 dql
->adj_limit
= limit
+ completed
;
176 dql
->prev_ovlimit
= ovlimit
;
177 dql
->prev_last_obj_cnt
= dql
->last_obj_cnt
;
178 dql
->num_completed
= completed
;
179 dql
->prev_num_queued
= num_queued
;
181 dql_check_stall(dql
);
183 EXPORT_SYMBOL(dql_completed
);
185 void dql_reset(struct dql
*dql
)
187 /* Reset all dynamic values */
190 dql
->num_completed
= 0;
191 dql
->last_obj_cnt
= 0;
192 dql
->prev_num_queued
= 0;
193 dql
->prev_last_obj_cnt
= 0;
194 dql
->prev_ovlimit
= 0;
195 dql
->lowest_slack
= UINT_MAX
;
196 dql
->slack_start_time
= jiffies
;
198 dql
->last_reap
= jiffies
;
199 dql
->history_head
= jiffies
/ BITS_PER_LONG
;
200 memset(dql
->history
, 0, sizeof(dql
->history
));
202 EXPORT_SYMBOL(dql_reset
);
204 void dql_init(struct dql
*dql
, unsigned int hold_time
)
206 dql
->max_limit
= DQL_MAX_LIMIT
;
208 dql
->slack_hold_time
= hold_time
;
212 EXPORT_SYMBOL(dql_init
);