diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig | 3 | ||||
| -rw-r--r-- | lib/Makefile | 2 | ||||
| -rw-r--r-- | lib/dynamic_queue_limits.c | 133 | ||||
| -rw-r--r-- | lib/reciprocal_div.c | 2 | ||||
| -rw-r--r-- | lib/vsprintf.c | 19 |
5 files changed, 159 insertions, 0 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index 32f3e5ae2be..63b5782732e 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -244,6 +244,9 @@ config CPU_RMAP bool depends on SMP +config DQL + bool + # # Netlink attribute parsing support is select'ed if needed # diff --git a/lib/Makefile b/lib/Makefile index a4da283f5dc..ff00d4dcb7e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -115,6 +115,8 @@ obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o obj-$(CONFIG_CORDIC) += cordic.o +obj-$(CONFIG_DQL) += dynamic_queue_limits.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/dynamic_queue_limits.c b/lib/dynamic_queue_limits.c new file mode 100644 index 00000000000..3d1bdcdd7db --- /dev/null +++ b/lib/dynamic_queue_limits.c @@ -0,0 +1,133 @@ +/* + * Dynamic byte queue limits. See include/linux/dynamic_queue_limits.h + * + * Copyright (c) 2011, Tom Herbert <therbert@google.com> + */ +#include <linux/module.h> +#include <linux/types.h> +#include <linux/ctype.h> +#include <linux/kernel.h> +#include <linux/dynamic_queue_limits.h> + +#define POSDIFF(A, B) ((A) > (B) ? (A) - (B) : 0) + +/* Records completed count and recalculates the queue limit */ +void dql_completed(struct dql *dql, unsigned int count) +{ + unsigned int inprogress, prev_inprogress, limit; + unsigned int ovlimit, all_prev_completed, completed; + + /* Can't complete more than what's in queue */ + BUG_ON(count > dql->num_queued - dql->num_completed); + + completed = dql->num_completed + count; + limit = dql->limit; + ovlimit = POSDIFF(dql->num_queued - dql->num_completed, limit); + inprogress = dql->num_queued - completed; + prev_inprogress = dql->prev_num_queued - dql->num_completed; + all_prev_completed = POSDIFF(completed, dql->prev_num_queued); + + if ((ovlimit && !inprogress) || + (dql->prev_ovlimit && all_prev_completed)) { + /* + * Queue considered starved if: + * - The queue was over-limit in the last interval, + * and there is no more data in the queue. + * OR + * - The queue was over-limit in the previous interval and + * when enqueuing it was possible that all queued data + * had been consumed. This covers the case when queue + * may have becomes starved between completion processing + * running and next time enqueue was scheduled. + * + * When queue is starved increase the limit by the amount + * of bytes both sent and completed in the last interval, + * plus any previous over-limit. + */ + limit += POSDIFF(completed, dql->prev_num_queued) + + dql->prev_ovlimit; + dql->slack_start_time = jiffies; + dql->lowest_slack = UINT_MAX; + } else if (inprogress && prev_inprogress && !all_prev_completed) { + /* + * Queue was not starved, check if the limit can be decreased. + * A decrease is only considered if the queue has been busy in + * the whole interval (the check above). + * + * If there is slack, the amount of execess data queued above + * the the amount needed to prevent starvation, the queue limit + * can be decreased. To avoid hysteresis we consider the + * minimum amount of slack found over several iterations of the + * completion routine. + */ + unsigned int slack, slack_last_objs; + + /* + * Slack is the maximum of + * - The queue limit plus previous over-limit minus twice + * the number of objects completed. Note that two times + * number of completed bytes is a basis for an upper bound + * of the limit. + * - Portion of objects in the last queuing operation that + * was not part of non-zero previous over-limit. That is + * "round down" by non-overlimit portion of the last + * queueing operation. + */ + slack = POSDIFF(limit + dql->prev_ovlimit, + 2 * (completed - dql->num_completed)); + slack_last_objs = dql->prev_ovlimit ? + POSDIFF(dql->prev_last_obj_cnt, dql->prev_ovlimit) : 0; + + slack = max(slack, slack_last_objs); + + if (slack < dql->lowest_slack) + dql->lowest_slack = slack; + + if (time_after(jiffies, + dql->slack_start_time + dql->slack_hold_time)) { + limit = POSDIFF(limit, dql->lowest_slack); + dql->slack_start_time = jiffies; + dql->lowest_slack = UINT_MAX; + } + } + + /* Enforce bounds on limit */ + limit = clamp(limit, dql->min_limit, dql->max_limit); + + if (limit != dql->limit) { + dql->limit = limit; + ovlimit = 0; + } + + dql->adj_limit = limit + completed; + dql->prev_ovlimit = ovlimit; + dql->prev_last_obj_cnt = dql->last_obj_cnt; + dql->num_completed = completed; + dql->prev_num_queued = dql->num_queued; +} +EXPORT_SYMBOL(dql_completed); + +void dql_reset(struct dql *dql) +{ + /* Reset all dynamic values */ + dql->limit = 0; + dql->num_queued = 0; + dql->num_completed = 0; + dql->last_obj_cnt = 0; + dql->prev_num_queued = 0; + dql->prev_last_obj_cnt = 0; + dql->prev_ovlimit = 0; + dql->lowest_slack = UINT_MAX; + dql->slack_start_time = jiffies; +} +EXPORT_SYMBOL(dql_reset); + +int dql_init(struct dql *dql, unsigned hold_time) +{ + dql->max_limit = DQL_MAX_LIMIT; + dql->min_limit = 0; + dql->slack_hold_time = hold_time; + dql_reset(dql); + return 0; +} +EXPORT_SYMBOL(dql_init); diff --git a/lib/reciprocal_div.c b/lib/reciprocal_div.c index 6a3bd48fa2a..75510e94f7d 100644 --- a/lib/reciprocal_div.c +++ b/lib/reciprocal_div.c @@ -1,5 +1,6 @@ #include <asm/div64.h> #include <linux/reciprocal_div.h> +#include <linux/export.h> u32 reciprocal_value(u32 k) { @@ -7,3 +8,4 @@ u32 reciprocal_value(u32 k) do_div(val, k); return (u32)val; } +EXPORT_SYMBOL(reciprocal_value); diff --git a/lib/vsprintf.c b/lib/vsprintf.c index 993599e66e5..8e75003d62f 100644 --- a/lib/vsprintf.c +++ b/lib/vsprintf.c @@ -777,6 +777,18 @@ char *uuid_string(char *buf, char *end, const u8 *addr, return string(buf, end, uuid, spec); } +static +char *netdev_feature_string(char *buf, char *end, const u8 *addr, + struct printf_spec spec) +{ + spec.flags |= SPECIAL | SMALL | ZEROPAD; + if (spec.field_width == -1) + spec.field_width = 2 + 2 * sizeof(netdev_features_t); + spec.base = 16; + + return number(buf, end, *(const netdev_features_t *)addr, spec); +} + int kptr_restrict __read_mostly; /* @@ -824,6 +836,7 @@ int kptr_restrict __read_mostly; * Do not use this feature without some mechanism to verify the * correctness of the format string and va_list arguments. * - 'K' For a kernel pointer that should be hidden from unprivileged users + * - 'NF' For a netdev_features_t * * Note: The difference between 'S' and 'F' is that on ia64 and ppc64 * function pointers are really function descriptors, which contain a @@ -896,6 +909,12 @@ char *pointer(const char *fmt, char *buf, char *end, void *ptr, has_capability_noaudit(current, CAP_SYSLOG)))) ptr = NULL; break; + case 'N': + switch (fmt[1]) { + case 'F': + return netdev_feature_string(buf, end, ptr, spec); + } + break; } spec.flags |= SMALL; if (spec.field_width == -1) { |