1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * Dynamic byte queue limits. See include/linux/dynamic_queue_limits.h |
4 | * |
5 | * Copyright (c) 2011, Tom Herbert <therbert@google.com> |
6 | */ |
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 | |
14 | #define POSDIFF(A, B) ((int)((A) - (B)) > 0 ? (A) - (B) : 0) |
15 | #define AFTER_EQ(A, B) ((int)((A) - (B)) >= 0) |
16 | |
17 | /* Records completed count and recalculates the queue limit */ |
18 | void dql_completed(struct dql *dql, unsigned int count) |
19 | { |
20 | unsigned int inprogress, prev_inprogress, limit; |
21 | unsigned int ovlimit, completed, num_queued; |
22 | bool all_prev_completed; |
23 | |
24 | num_queued = READ_ONCE(dql->num_queued); |
25 | |
26 | /* Can't complete more than what's in queue */ |
27 | BUG_ON(count > num_queued - dql->num_completed); |
28 | |
29 | completed = dql->num_completed + count; |
30 | limit = dql->limit; |
31 | ovlimit = POSDIFF(num_queued - dql->num_completed, limit); |
32 | inprogress = num_queued - completed; |
33 | prev_inprogress = dql->prev_num_queued - dql->num_completed; |
34 | all_prev_completed = AFTER_EQ(completed, dql->prev_num_queued); |
35 | |
36 | if ((ovlimit && !inprogress) || |
37 | (dql->prev_ovlimit && all_prev_completed)) { |
38 | /* |
39 | * Queue considered starved if: |
40 | * - The queue was over-limit in the last interval, |
41 | * and there is no more data in the queue. |
42 | * OR |
43 | * - The queue was over-limit in the previous interval and |
44 | * when enqueuing it was possible that all queued data |
45 | * had been consumed. This covers the case when queue |
46 | * may have becomes starved between completion processing |
47 | * running and next time enqueue was scheduled. |
48 | * |
49 | * When queue is starved increase the limit by the amount |
50 | * of bytes both sent and completed in the last interval, |
51 | * plus any previous over-limit. |
52 | */ |
53 | limit += POSDIFF(completed, dql->prev_num_queued) + |
54 | dql->prev_ovlimit; |
55 | dql->slack_start_time = jiffies; |
56 | dql->lowest_slack = UINT_MAX; |
57 | } else if (inprogress && prev_inprogress && !all_prev_completed) { |
58 | /* |
59 | * Queue was not starved, check if the limit can be decreased. |
60 | * A decrease is only considered if the queue has been busy in |
61 | * the whole interval (the check above). |
62 | * |
63 | * If there is slack, the amount of excess data queued above |
64 | * the amount needed to prevent starvation, the queue limit |
65 | * can be decreased. To avoid hysteresis we consider the |
66 | * minimum amount of slack found over several iterations of the |
67 | * completion routine. |
68 | */ |
69 | unsigned int slack, slack_last_objs; |
70 | |
71 | /* |
72 | * Slack is the maximum of |
73 | * - The queue limit plus previous over-limit minus twice |
74 | * the number of objects completed. Note that two times |
75 | * number of completed bytes is a basis for an upper bound |
76 | * of the limit. |
77 | * - Portion of objects in the last queuing operation that |
78 | * was not part of non-zero previous over-limit. That is |
79 | * "round down" by non-overlimit portion of the last |
80 | * queueing operation. |
81 | */ |
82 | slack = POSDIFF(limit + dql->prev_ovlimit, |
83 | 2 * (completed - dql->num_completed)); |
84 | slack_last_objs = dql->prev_ovlimit ? |
85 | POSDIFF(dql->prev_last_obj_cnt, dql->prev_ovlimit) : 0; |
86 | |
87 | slack = max(slack, slack_last_objs); |
88 | |
89 | if (slack < dql->lowest_slack) |
90 | dql->lowest_slack = slack; |
91 | |
92 | if (time_after(jiffies, |
93 | dql->slack_start_time + dql->slack_hold_time)) { |
94 | limit = POSDIFF(limit, dql->lowest_slack); |
95 | dql->slack_start_time = jiffies; |
96 | dql->lowest_slack = UINT_MAX; |
97 | } |
98 | } |
99 | |
100 | /* Enforce bounds on limit */ |
101 | limit = clamp(limit, dql->min_limit, dql->max_limit); |
102 | |
103 | if (limit != dql->limit) { |
104 | dql->limit = limit; |
105 | ovlimit = 0; |
106 | } |
107 | |
108 | dql->adj_limit = limit + completed; |
109 | dql->prev_ovlimit = ovlimit; |
110 | dql->prev_last_obj_cnt = dql->last_obj_cnt; |
111 | dql->num_completed = completed; |
112 | dql->prev_num_queued = num_queued; |
113 | } |
114 | EXPORT_SYMBOL(dql_completed); |
115 | |
116 | void dql_reset(struct dql *dql) |
117 | { |
118 | /* Reset all dynamic values */ |
119 | dql->limit = 0; |
120 | dql->num_queued = 0; |
121 | dql->num_completed = 0; |
122 | dql->last_obj_cnt = 0; |
123 | dql->prev_num_queued = 0; |
124 | dql->prev_last_obj_cnt = 0; |
125 | dql->prev_ovlimit = 0; |
126 | dql->lowest_slack = UINT_MAX; |
127 | dql->slack_start_time = jiffies; |
128 | } |
129 | EXPORT_SYMBOL(dql_reset); |
130 | |
131 | void dql_init(struct dql *dql, unsigned int hold_time) |
132 | { |
133 | dql->max_limit = DQL_MAX_LIMIT; |
134 | dql->min_limit = 0; |
135 | dql->slack_hold_time = hold_time; |
136 | dql_reset(dql); |
137 | } |
138 | EXPORT_SYMBOL(dql_init); |
139 | |