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