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