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