2 * Dynamic byte queue limits. See include/linux/dynamic_queue_limits.h
4 * Copyright (c) 2011, Tom Herbert <therbert@google.com>
6 #include <linux/types.h>
7 #include <linux/kernel.h>
8 #include <linux/jiffies.h>
9 #include <linux/dynamic_queue_limits.h>
10 #include <linux/compiler.h>
11 #include <linux/export.h>
13 #define POSDIFF(A, B) ((int)((A) - (B)) > 0 ? (A) - (B) : 0)
14 #define AFTER_EQ(A, B) ((int)((A) - (B)) >= 0)
16 /* Records completed count and recalculates the queue limit */
17 void dql_completed(struct dql
*dql
, unsigned int count
)
19 unsigned int inprogress
, prev_inprogress
, limit
;
20 unsigned int ovlimit
, completed
, num_queued
;
21 bool all_prev_completed
;
23 num_queued
= ACCESS_ONCE(dql
->num_queued
);
25 /* Can't complete more than what's in queue */
26 BUG_ON(count
> num_queued
- dql
->num_completed
);
28 completed
= dql
->num_completed
+ count
;
30 ovlimit
= POSDIFF(num_queued
- dql
->num_completed
, limit
);
31 inprogress
= num_queued
- completed
;
32 prev_inprogress
= dql
->prev_num_queued
- dql
->num_completed
;
33 all_prev_completed
= AFTER_EQ(completed
, dql
->prev_num_queued
);
35 if ((ovlimit
&& !inprogress
) ||
36 (dql
->prev_ovlimit
&& all_prev_completed
)) {
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.
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.
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.
52 limit
+= POSDIFF(completed
, dql
->prev_num_queued
) +
54 dql
->slack_start_time
= jiffies
;
55 dql
->lowest_slack
= UINT_MAX
;
56 } else if (inprogress
&& prev_inprogress
&& !all_prev_completed
) {
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).
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
68 unsigned int slack
, slack_last_objs
;
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
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
81 slack
= POSDIFF(limit
+ dql
->prev_ovlimit
,
82 2 * (completed
- dql
->num_completed
));
83 slack_last_objs
= dql
->prev_ovlimit
?
84 POSDIFF(dql
->prev_last_obj_cnt
, dql
->prev_ovlimit
) : 0;
86 slack
= max(slack
, slack_last_objs
);
88 if (slack
< dql
->lowest_slack
)
89 dql
->lowest_slack
= slack
;
91 if (time_after(jiffies
,
92 dql
->slack_start_time
+ dql
->slack_hold_time
)) {
93 limit
= POSDIFF(limit
, dql
->lowest_slack
);
94 dql
->slack_start_time
= jiffies
;
95 dql
->lowest_slack
= UINT_MAX
;
99 /* Enforce bounds on limit */
100 limit
= clamp(limit
, dql
->min_limit
, dql
->max_limit
);
102 if (limit
!= dql
->limit
) {
107 dql
->adj_limit
= limit
+ completed
;
108 dql
->prev_ovlimit
= ovlimit
;
109 dql
->prev_last_obj_cnt
= dql
->last_obj_cnt
;
110 dql
->num_completed
= completed
;
111 dql
->prev_num_queued
= num_queued
;
113 EXPORT_SYMBOL(dql_completed
);
115 void dql_reset(struct dql
*dql
)
117 /* Reset all dynamic values */
120 dql
->num_completed
= 0;
121 dql
->last_obj_cnt
= 0;
122 dql
->prev_num_queued
= 0;
123 dql
->prev_last_obj_cnt
= 0;
124 dql
->prev_ovlimit
= 0;
125 dql
->lowest_slack
= UINT_MAX
;
126 dql
->slack_start_time
= jiffies
;
128 EXPORT_SYMBOL(dql_reset
);
130 int dql_init(struct dql
*dql
, unsigned hold_time
)
132 dql
->max_limit
= DQL_MAX_LIMIT
;
134 dql
->slack_hold_time
= hold_time
;
138 EXPORT_SYMBOL(dql_init
);
This page took 0.03658 seconds and 6 git commands to generate.