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