]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
75957ba3 TH |
2 | /* |
3 | * Dynamic byte queue limits. See include/linux/dynamic_queue_limits.h | |
4 | * | |
5 | * Copyright (c) 2011, Tom Herbert <therbert@google.com> | |
6 | */ | |
75957ba3 | 7 | #include <linux/types.h> |
75957ba3 | 8 | #include <linux/kernel.h> |
930c514f | 9 | #include <linux/jiffies.h> |
75957ba3 | 10 | #include <linux/dynamic_queue_limits.h> |
565ac23b RV |
11 | #include <linux/compiler.h> |
12 | #include <linux/export.h> | |
6025b913 | 13 | #include <trace/events/napi.h> |
75957ba3 | 14 | |
0cfd32b7 | 15 | #define POSDIFF(A, B) ((int)((A) - (B)) > 0 ? (A) - (B) : 0) |
25426b79 | 16 | #define AFTER_EQ(A, B) ((int)((A) - (B)) >= 0) |
75957ba3 | 17 | |
6025b913 JK |
18 | static void dql_check_stall(struct dql *dql) |
19 | { | |
20 | unsigned short stall_thrs; | |
21 | unsigned long now; | |
22 | ||
23 | stall_thrs = READ_ONCE(dql->stall_thrs); | |
24 | if (!stall_thrs) | |
25 | return; | |
26 | ||
27 | now = jiffies; | |
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; | |
31 | ||
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. | |
35 | */ | |
36 | dqs_again: | |
37 | hist_head = READ_ONCE(dql->history_head); | |
38 | /* pairs with smp_wmb() in dql_queued() */ | |
39 | smp_rmb(); | |
40 | ||
41 | /* Get the previous entry in the ring buffer, which is the | |
42 | * oldest sample. | |
43 | */ | |
44 | start = (hist_head - DQL_HIST_LEN + 1) * BITS_PER_LONG; | |
45 | ||
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; | |
49 | ||
50 | /* Newest sample we should have already seen a completion for */ | |
51 | end = hist_head * BITS_PER_LONG + (BITS_PER_LONG - 1); | |
52 | ||
53 | /* Shrink the search space to [start, (now - start_thrs/2)] if | |
54 | * `end` is beyond the stall zone | |
55 | */ | |
56 | if (time_before(now, end + stall_thrs / 2)) | |
57 | end = now - stall_thrs / 2; | |
58 | ||
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), | |
62 | dql->history)) | |
63 | break; | |
64 | ||
65 | /* Variable t contains the time of the queue */ | |
66 | if (!time_before_eq(t, end)) | |
67 | goto no_stall; | |
68 | ||
69 | /* The ring buffer was modified in the meantime, retry */ | |
70 | if (hist_head != READ_ONCE(dql->history_head)) | |
71 | goto dqs_again; | |
72 | ||
73 | dql->stall_cnt++; | |
74 | dql->stall_max = max_t(unsigned short, dql->stall_max, now - t); | |
75 | ||
76 | trace_dql_stall_detected(dql->stall_thrs, now - t, | |
77 | dql->last_reap, dql->history_head, | |
78 | now, dql->history); | |
79 | } | |
80 | no_stall: | |
81 | dql->last_reap = now; | |
82 | } | |
83 | ||
75957ba3 TH |
84 | /* Records completed count and recalculates the queue limit */ |
85 | void dql_completed(struct dql *dql, unsigned int count) | |
86 | { | |
87 | unsigned int inprogress, prev_inprogress, limit; | |
914bec10 | 88 | unsigned int ovlimit, completed, num_queued; |
25426b79 | 89 | bool all_prev_completed; |
75957ba3 | 90 | |
6aa7de05 | 91 | num_queued = READ_ONCE(dql->num_queued); |
914bec10 | 92 | |
75957ba3 | 93 | /* Can't complete more than what's in queue */ |
914bec10 | 94 | BUG_ON(count > num_queued - dql->num_completed); |
75957ba3 TH |
95 | |
96 | completed = dql->num_completed + count; | |
97 | limit = dql->limit; | |
914bec10 HS |
98 | ovlimit = POSDIFF(num_queued - dql->num_completed, limit); |
99 | inprogress = num_queued - completed; | |
75957ba3 | 100 | prev_inprogress = dql->prev_num_queued - dql->num_completed; |
25426b79 | 101 | all_prev_completed = AFTER_EQ(completed, dql->prev_num_queued); |
75957ba3 TH |
102 | |
103 | if ((ovlimit && !inprogress) || | |
104 | (dql->prev_ovlimit && all_prev_completed)) { | |
105 | /* | |
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. | |
109 | * OR | |
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. | |
115 | * | |
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. | |
119 | */ | |
120 | limit += POSDIFF(completed, dql->prev_num_queued) + | |
121 | dql->prev_ovlimit; | |
122 | dql->slack_start_time = jiffies; | |
123 | dql->lowest_slack = UINT_MAX; | |
124 | } else if (inprogress && prev_inprogress && !all_prev_completed) { | |
125 | /* | |
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). | |
129 | * | |
dde57fe0 RD |
130 | * If there is slack, the amount of excess data queued above |
131 | * the amount needed to prevent starvation, the queue limit | |
75957ba3 TH |
132 | * can be decreased. To avoid hysteresis we consider the |
133 | * minimum amount of slack found over several iterations of the | |
134 | * completion routine. | |
135 | */ | |
136 | unsigned int slack, slack_last_objs; | |
137 | ||
138 | /* | |
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 | |
143 | * of the limit. | |
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. | |
148 | */ | |
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; | |
153 | ||
154 | slack = max(slack, slack_last_objs); | |
155 | ||
156 | if (slack < dql->lowest_slack) | |
157 | dql->lowest_slack = slack; | |
158 | ||
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; | |
164 | } | |
165 | } | |
166 | ||
167 | /* Enforce bounds on limit */ | |
168 | limit = clamp(limit, dql->min_limit, dql->max_limit); | |
169 | ||
170 | if (limit != dql->limit) { | |
171 | dql->limit = limit; | |
172 | ovlimit = 0; | |
173 | } | |
174 | ||
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; | |
914bec10 | 179 | dql->prev_num_queued = num_queued; |
6025b913 JK |
180 | |
181 | dql_check_stall(dql); | |
75957ba3 TH |
182 | } |
183 | EXPORT_SYMBOL(dql_completed); | |
184 | ||
185 | void dql_reset(struct dql *dql) | |
186 | { | |
187 | /* Reset all dynamic values */ | |
188 | dql->limit = 0; | |
189 | dql->num_queued = 0; | |
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; | |
6025b913 JK |
197 | |
198 | dql->last_reap = jiffies; | |
199 | dql->history_head = jiffies / BITS_PER_LONG; | |
200 | memset(dql->history, 0, sizeof(dql->history)); | |
75957ba3 TH |
201 | } |
202 | EXPORT_SYMBOL(dql_reset); | |
203 | ||
7a0947e7 | 204 | void dql_init(struct dql *dql, unsigned int hold_time) |
75957ba3 TH |
205 | { |
206 | dql->max_limit = DQL_MAX_LIMIT; | |
207 | dql->min_limit = 0; | |
208 | dql->slack_hold_time = hold_time; | |
6025b913 | 209 | dql->stall_thrs = 0; |
75957ba3 | 210 | dql_reset(dql); |
75957ba3 TH |
211 | } |
212 | EXPORT_SYMBOL(dql_init); |