Branch data 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 [ # # ]: 0 : 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 : 0 : dql->limit = 0;
119 : 0 : dql->num_queued = 0;
120 : 0 : dql->num_completed = 0;
121 : 0 : dql->last_obj_cnt = 0;
122 : 0 : dql->prev_num_queued = 0;
123 : 0 : dql->prev_last_obj_cnt = 0;
124 : 0 : dql->prev_ovlimit = 0;
125 : 0 : dql->lowest_slack = UINT_MAX;
126 : 0 : dql->slack_start_time = jiffies;
127 : 0 : }
128 : : EXPORT_SYMBOL(dql_reset);
129 : :
130 : 0 : int dql_init(struct dql *dql, unsigned hold_time)
131 : : {
132 : 0 : dql->max_limit = DQL_MAX_LIMIT;
133 : 0 : dql->min_limit = 0;
134 : 0 : dql->slack_hold_time = hold_time;
135 : : dql_reset(dql);
136 : 0 : return 0;
137 : : }
138 : : EXPORT_SYMBOL(dql_init);
|
