From 3654654f7aa79a37dde130afb7409c55b11807e7 Mon Sep 17 00:00:00 2001 From: Jan Engelhardt Date: Tue, 16 Nov 2010 09:52:32 -0800 Subject: netlink: let nlmsg and nla functions take pointer-to-const args The changed functions do not modify the NL messages and/or attributes at all. They should use const (similar to strchr), so that callers which have a const nlmsg/nlattr around can make use of them without casting. While at it, constify a data array. Signed-off-by: Jan Engelhardt Signed-off-by: David S. Miller --- lib/nlattr.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'lib') diff --git a/lib/nlattr.c b/lib/nlattr.c index c4706eb98d3d..00e8a02681a6 100644 --- a/lib/nlattr.c +++ b/lib/nlattr.c @@ -15,7 +15,7 @@ #include #include -static u16 nla_attr_minlen[NLA_TYPE_MAX+1] __read_mostly = { +static const u16 nla_attr_minlen[NLA_TYPE_MAX+1] = { [NLA_U8] = sizeof(u8), [NLA_U16] = sizeof(u16), [NLA_U32] = sizeof(u32), @@ -23,7 +23,7 @@ static u16 nla_attr_minlen[NLA_TYPE_MAX+1] __read_mostly = { [NLA_NESTED] = NLA_HDRLEN, }; -static int validate_nla(struct nlattr *nla, int maxtype, +static int validate_nla(const struct nlattr *nla, int maxtype, const struct nla_policy *policy) { const struct nla_policy *pt; @@ -115,10 +115,10 @@ static int validate_nla(struct nlattr *nla, int maxtype, * * Returns 0 on success or a negative error code. */ -int nla_validate(struct nlattr *head, int len, int maxtype, +int nla_validate(const struct nlattr *head, int len, int maxtype, const struct nla_policy *policy) { - struct nlattr *nla; + const struct nlattr *nla; int rem, err; nla_for_each_attr(nla, head, len, rem) { @@ -173,10 +173,10 @@ nla_policy_len(const struct nla_policy *p, int n) * * Returns 0 on success or a negative error code. */ -int nla_parse(struct nlattr *tb[], int maxtype, struct nlattr *head, int len, - const struct nla_policy *policy) +int nla_parse(struct nlattr **tb, int maxtype, const struct nlattr *head, + int len, const struct nla_policy *policy) { - struct nlattr *nla; + const struct nlattr *nla; int rem, err; memset(tb, 0, sizeof(struct nlattr *) * (maxtype + 1)); @@ -191,7 +191,7 @@ int nla_parse(struct nlattr *tb[], int maxtype, struct nlattr *head, int len, goto errout; } - tb[type] = nla; + tb[type] = (struct nlattr *)nla; } } @@ -212,14 +212,14 @@ errout: * * Returns the first attribute in the stream matching the specified type. */ -struct nlattr *nla_find(struct nlattr *head, int len, int attrtype) +struct nlattr *nla_find(const struct nlattr *head, int len, int attrtype) { - struct nlattr *nla; + const struct nlattr *nla; int rem; nla_for_each_attr(nla, head, len, rem) if (nla_type(nla) == attrtype) - return nla; + return (struct nlattr *)nla; return NULL; } -- cgit v1.2.3 From c5485a7e7569ab32eea240c850198519e2a765ef Mon Sep 17 00:00:00 2001 From: Bruno Randolf Date: Tue, 16 Nov 2010 10:58:37 +0900 Subject: lib: Add generic exponentially weighted moving average (EWMA) function This adds generic functions for calculating Exponentially Weighted Moving Averages (EWMA). This implementation makes use of a structure which keeps the EWMA parameters and a scaled up internal representation to reduce rounding errors. The original idea for this implementation came from the rt2x00 driver (rt2x00link.c). I would like to use it in several places in the mac80211 and ath5k code and I hope it can be useful in many other places in the kernel code. Signed-off-by: Bruno Randolf Reviewed-by: KOSAKI Motohiro Signed-off-by: John W. Linville --- include/linux/average.h | 32 +++++++++++++++++++++++++++ lib/Kconfig | 3 +++ lib/Makefile | 2 ++ lib/average.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 94 insertions(+) create mode 100644 include/linux/average.h create mode 100644 lib/average.c (limited to 'lib') diff --git a/include/linux/average.h b/include/linux/average.h new file mode 100644 index 000000000000..7706e40f95fa --- /dev/null +++ b/include/linux/average.h @@ -0,0 +1,32 @@ +#ifndef _LINUX_AVERAGE_H +#define _LINUX_AVERAGE_H + +#include + +/* Exponentially weighted moving average (EWMA) */ + +/* For more documentation see lib/average.c */ + +struct ewma { + unsigned long internal; + unsigned long factor; + unsigned long weight; +}; + +extern void ewma_init(struct ewma *avg, unsigned long factor, + unsigned long weight); + +extern struct ewma *ewma_add(struct ewma *avg, unsigned long val); + +/** + * ewma_read() - Get average value + * @avg: Average structure + * + * Returns the average value held in @avg. + */ +static inline unsigned long ewma_read(const struct ewma *avg) +{ + return DIV_ROUND_CLOSEST(avg->internal, avg->factor); +} + +#endif /* _LINUX_AVERAGE_H */ diff --git a/lib/Kconfig b/lib/Kconfig index fa9bf2c06199..3116aa631af6 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -210,4 +210,7 @@ config GENERIC_ATOMIC64 config LRU_CACHE tristate +config AVERAGE + bool + endmenu diff --git a/lib/Makefile b/lib/Makefile index e6a3763b8212..76d3b8514903 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -106,6 +106,8 @@ obj-$(CONFIG_GENERIC_ATOMIC64) += atomic64.o obj-$(CONFIG_ATOMIC64_SELFTEST) += atomic64_test.o +obj-$(CONFIG_AVERAGE) += average.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/average.c b/lib/average.c new file mode 100644 index 000000000000..f1d1b4660c42 --- /dev/null +++ b/lib/average.c @@ -0,0 +1,57 @@ +/* + * lib/average.c + * + * This source code is licensed under the GNU General Public License, + * Version 2. See the file COPYING for more details. + */ + +#include +#include +#include + +/** + * DOC: Exponentially Weighted Moving Average (EWMA) + * + * These are generic functions for calculating Exponentially Weighted Moving + * Averages (EWMA). We keep a structure with the EWMA parameters and a scaled + * up internal representation of the average value to prevent rounding errors. + * The factor for scaling up and the exponential weight (or decay rate) have to + * be specified thru the init fuction. The structure should not be accessed + * directly but only thru the helper functions. + */ + +/** + * ewma_init() - Initialize EWMA parameters + * @avg: Average structure + * @factor: Factor to use for the scaled up internal value. The maximum value + * of averages can be ULONG_MAX/(factor*weight). + * @weight: Exponential weight, or decay rate. This defines how fast the + * influence of older values decreases. Has to be bigger than 1. + * + * Initialize the EWMA parameters for a given struct ewma @avg. + */ +void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight) +{ + WARN_ON(weight <= 1 || factor == 0); + avg->internal = 0; + avg->weight = weight; + avg->factor = factor; +} +EXPORT_SYMBOL(ewma_init); + +/** + * ewma_add() - Exponentially weighted moving average (EWMA) + * @avg: Average structure + * @val: Current value + * + * Add a sample to the average. + */ +struct ewma *ewma_add(struct ewma *avg, unsigned long val) +{ + avg->internal = avg->internal ? + (((avg->internal * (avg->weight - 1)) + + (val * avg->factor)) / avg->weight) : + (val * avg->factor); + return avg; +} +EXPORT_SYMBOL(ewma_add); -- cgit v1.2.3 From bcb38ceb225f5d5b2198a2755277cd441ed1e82b Mon Sep 17 00:00:00 2001 From: Dave Airlie Date: Tue, 30 Nov 2010 09:15:46 +1000 Subject: Revert "debug_locks: set oops_in_progress if we will log messages." This reverts commit e0fdace10e75dac67d906213b780ff1b1a4cc360. On-list discussion seems to suggest that the robustness fixes for printk make this unnecessary and DaveM has also agreed in person at Kernel Summit and on list. The main problem with this code is once we hit a lockdep splat we always keep oops_in_progress set, the console layer uses oops_in_progress with KMS to decide when it should be showing the oops and not showing X, so it causes problems around suspend/resume time when a userspace resume can cause a console switch away from X, only if oops_in_progress is set (which is what we want if an oops actually is in progress, but not because we had a lockdep splat 2 days prior). Cc: David S Miller Cc: Ingo Molnar Signed-off-by: Dave Airlie Signed-off-by: Linus Torvalds --- lib/debug_locks.c | 2 -- 1 file changed, 2 deletions(-) (limited to 'lib') diff --git a/lib/debug_locks.c b/lib/debug_locks.c index 5bf0020b9248..b1c177307677 100644 --- a/lib/debug_locks.c +++ b/lib/debug_locks.c @@ -8,7 +8,6 @@ * * Copyright (C) 2006 Red Hat, Inc., Ingo Molnar */ -#include #include #include #include @@ -39,7 +38,6 @@ int debug_locks_off(void) { if (__debug_locks_off()) { if (!debug_locks_silent) { - oops_in_progress = 1; console_verbose(); return 1; } -- cgit v1.2.3 From 87de5ac782761a3ebf806e434e8c9cc205a87274 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Mon, 20 Sep 2010 17:42:46 -0700 Subject: timers: Introduce timerlist infrastructure. The timerlist infrastructure is a thin layer over the rbtree code that implements a simple list of timers sorted by an expires value, and a getnext function that provides a pointer to the earliest timer. This infrastructure allows drivers and other kernel infrastructure to easily implement timers without duplicating code. Signed-off-by: John Stultz LKML Reference: <1290136329-18291-2-git-send-email-john.stultz@linaro.org> Reviewed-by: Thomas Gleixner CC: Alessandro Zummo CC: Thomas Gleixner CC: Richard Cochran --- include/linux/timerlist.h | 37 +++++++++++++++ lib/Makefile | 2 +- lib/timerlist.c | 118 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 156 insertions(+), 1 deletion(-) create mode 100644 include/linux/timerlist.h create mode 100644 lib/timerlist.c (limited to 'lib') diff --git a/include/linux/timerlist.h b/include/linux/timerlist.h new file mode 100644 index 000000000000..c46b28ae6e4d --- /dev/null +++ b/include/linux/timerlist.h @@ -0,0 +1,37 @@ +#ifndef _LINUX_TIMERLIST_H +#define _LINUX_TIMERLIST_H + +#include +#include + + +struct timerlist_node { + struct rb_node node; + ktime_t expires; +}; + +struct timerlist_head { + struct rb_root head; + struct timerlist_node *next; +}; + + +extern void timerlist_add(struct timerlist_head *head, + struct timerlist_node *node); +extern void timerlist_del(struct timerlist_head *head, + struct timerlist_node *node); +extern struct timerlist_node *timerlist_getnext(struct timerlist_head *head); +extern struct timerlist_node *timerlist_iterate_next( + struct timerlist_node *node); + +static inline void timerlist_init(struct timerlist_node *node) +{ + RB_CLEAR_NODE(&node->node); +} + +static inline void timerlist_init_head(struct timerlist_head *head) +{ + head->head = RB_ROOT; + head->next = NULL; +} +#endif /* _LINUX_TIMERLIST_H */ diff --git a/lib/Makefile b/lib/Makefile index e6a3763b8212..8b475cfb8195 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS)) endif lib-y := ctype.o string.o vsprintf.o cmdline.o \ - rbtree.o radix-tree.o dump_stack.o \ + rbtree.o radix-tree.o dump_stack.o timerlist.o\ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o prio_heap.o ratelimit.o show_mem.o \ diff --git a/lib/timerlist.c b/lib/timerlist.c new file mode 100644 index 000000000000..9101b42fd13d --- /dev/null +++ b/lib/timerlist.c @@ -0,0 +1,118 @@ +/* + * Generic Timer-list + * + * Manages a simple list of timers, ordered by expiration time. + * Uses rbtrees for quick list adds and expiration. + * + * NOTE: All of the following functions need to be serialized + * to avoid races. No locking is done by this libary code. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include +#include + +/** + * timerlist_add - Adds timer to timerlist. + * + * @head: head of timerlist + * @node: timer node to be added + * + * Adds the timer node to the timerlist, sorted by the + * node's expires value. + */ +void timerlist_add(struct timerlist_head *head, struct timerlist_node *node) +{ + struct rb_node **p = &head->head.rb_node; + struct rb_node *parent = NULL; + struct timerlist_node *ptr; + + /* Make sure we don't add nodes that are already added */ + WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); + + while (*p) { + parent = *p; + ptr = rb_entry(parent, struct timerlist_node, node); + if (node->expires.tv64 < ptr->expires.tv64) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + rb_link_node(&node->node, parent, p); + rb_insert_color(&node->node, &head->head); + + if (!head->next || node->expires.tv64 < head->next->expires.tv64) + head->next = node; +} + +/** + * timerlist_del - Removes a timer from the timerlist. + * + * @head: head of timerlist + * @node: timer node to be removed + * + * Removes the timer node from the timerlist. + */ +void timerlist_del(struct timerlist_head *head, struct timerlist_node *node) +{ + WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); + + /* update next pointer */ + if (head->next == node) { + struct rb_node *rbn = rb_next(&node->node); + + head->next = rbn ? + rb_entry(rbn, struct timerlist_node, node) : NULL; + } + rb_erase(&node->node, &head->head); + RB_CLEAR_NODE(&node->node); +} + + +/** + * timerlist_getnext - Returns the timer with the earlies expiration time + * + * @head: head of timerlist + * + * Returns a pointer to the timer node that has the + * earliest expiration time. + */ +struct timerlist_node *timerlist_getnext(struct timerlist_head *head) +{ + return head->next; +} + + +/** + * timerlist_iterate_next - Returns the timer after the provided timer + * + * @node: Pointer to a timer. + * + * Provides the timer that is after the given node. This is used, when + * necessary, to iterate through the list of timers in a timer list + * without modifying the list. + */ +struct timerlist_node *timerlist_iterate_next(struct timerlist_node *node) +{ + struct rb_node *next; + + if (!node) + return NULL; + next = rb_next(&node->node); + if (!next) + return NULL; + return container_of(next, struct timerlist_node, node); +} -- cgit v1.2.3 From af5568843594fb71055debe36e521fa8072fcecc Mon Sep 17 00:00:00 2001 From: Bruno Randolf Date: Thu, 2 Dec 2010 19:50:37 +0900 Subject: lib: Improve EWMA efficiency by using bitshifts Using bitshifts instead of division and multiplication should improve performance. That requires weight and factor to be powers of two, but i think this is something we can live with. Thanks to Peter Zijlstra for the improved formula! Signed-off-by: Bruno Randolf -- v2: use log2.h functions Signed-off-by: John W. Linville --- include/linux/average.h | 4 +--- lib/average.c | 20 ++++++++++++-------- 2 files changed, 13 insertions(+), 11 deletions(-) (limited to 'lib') diff --git a/include/linux/average.h b/include/linux/average.h index 7706e40f95fa..c6028fd742c1 100644 --- a/include/linux/average.h +++ b/include/linux/average.h @@ -1,8 +1,6 @@ #ifndef _LINUX_AVERAGE_H #define _LINUX_AVERAGE_H -#include - /* Exponentially weighted moving average (EWMA) */ /* For more documentation see lib/average.c */ @@ -26,7 +24,7 @@ extern struct ewma *ewma_add(struct ewma *avg, unsigned long val); */ static inline unsigned long ewma_read(const struct ewma *avg) { - return DIV_ROUND_CLOSEST(avg->internal, avg->factor); + return avg->internal >> avg->factor; } #endif /* _LINUX_AVERAGE_H */ diff --git a/lib/average.c b/lib/average.c index f1d1b4660c42..5576c2841496 100644 --- a/lib/average.c +++ b/lib/average.c @@ -8,6 +8,7 @@ #include #include #include +#include /** * DOC: Exponentially Weighted Moving Average (EWMA) @@ -24,18 +25,21 @@ * ewma_init() - Initialize EWMA parameters * @avg: Average structure * @factor: Factor to use for the scaled up internal value. The maximum value - * of averages can be ULONG_MAX/(factor*weight). + * of averages can be ULONG_MAX/(factor*weight). For performance reasons + * factor has to be a power of 2. * @weight: Exponential weight, or decay rate. This defines how fast the - * influence of older values decreases. Has to be bigger than 1. + * influence of older values decreases. For performance reasons weight has + * to be a power of 2. * * Initialize the EWMA parameters for a given struct ewma @avg. */ void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight) { - WARN_ON(weight <= 1 || factor == 0); + WARN_ON(!is_power_of_2(weight) || !is_power_of_2(factor)); + + avg->weight = ilog2(weight); + avg->factor = ilog2(factor); avg->internal = 0; - avg->weight = weight; - avg->factor = factor; } EXPORT_SYMBOL(ewma_init); @@ -49,9 +53,9 @@ EXPORT_SYMBOL(ewma_init); struct ewma *ewma_add(struct ewma *avg, unsigned long val) { avg->internal = avg->internal ? - (((avg->internal * (avg->weight - 1)) + - (val * avg->factor)) / avg->weight) : - (val * avg->factor); + (((avg->internal << avg->weight) - avg->internal) + + (val << avg->factor)) >> avg->weight : + (val << avg->factor); return avg; } EXPORT_SYMBOL(ewma_add); -- cgit v1.2.3 From 1f5a24794a54588ea3a9efd521be31d826e0b9d7 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Thu, 9 Dec 2010 12:02:18 -0800 Subject: timers: Rename timerlist infrastructure to timerqueue Thomas pointed out a namespace collision between the new timerlist infrastructure I introduced and the existing timer_list.c So to avoid confusion, I've renamed the timerlist infrastructure to timerqueue. Reported-by: Thomas Gleixner Signed-off-by: John Stultz --- include/linux/timerlist.h | 37 -------------- include/linux/timerqueue.h | 37 ++++++++++++++ lib/Makefile | 2 +- lib/timerlist.c | 118 --------------------------------------------- lib/timerqueue.c | 118 +++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 156 insertions(+), 156 deletions(-) delete mode 100644 include/linux/timerlist.h create mode 100644 include/linux/timerqueue.h delete mode 100644 lib/timerlist.c create mode 100644 lib/timerqueue.c (limited to 'lib') diff --git a/include/linux/timerlist.h b/include/linux/timerlist.h deleted file mode 100644 index c46b28ae6e4d..000000000000 --- a/include/linux/timerlist.h +++ /dev/null @@ -1,37 +0,0 @@ -#ifndef _LINUX_TIMERLIST_H -#define _LINUX_TIMERLIST_H - -#include -#include - - -struct timerlist_node { - struct rb_node node; - ktime_t expires; -}; - -struct timerlist_head { - struct rb_root head; - struct timerlist_node *next; -}; - - -extern void timerlist_add(struct timerlist_head *head, - struct timerlist_node *node); -extern void timerlist_del(struct timerlist_head *head, - struct timerlist_node *node); -extern struct timerlist_node *timerlist_getnext(struct timerlist_head *head); -extern struct timerlist_node *timerlist_iterate_next( - struct timerlist_node *node); - -static inline void timerlist_init(struct timerlist_node *node) -{ - RB_CLEAR_NODE(&node->node); -} - -static inline void timerlist_init_head(struct timerlist_head *head) -{ - head->head = RB_ROOT; - head->next = NULL; -} -#endif /* _LINUX_TIMERLIST_H */ diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h new file mode 100644 index 000000000000..406b103894bd --- /dev/null +++ b/include/linux/timerqueue.h @@ -0,0 +1,37 @@ +#ifndef _LINUX_TIMERQUEUE_H +#define _LINUX_TIMERQUEUE_H + +#include +#include + + +struct timerqueue_node { + struct rb_node node; + ktime_t expires; +}; + +struct timerqueue_head { + struct rb_root head; + struct timerqueue_node *next; +}; + + +extern void timerqueue_add(struct timerqueue_head *head, + struct timerqueue_node *node); +extern void timerqueue_del(struct timerqueue_head *head, + struct timerqueue_node *node); +extern struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head); +extern struct timerqueue_node *timerqueue_iterate_next( + struct timerqueue_node *node); + +static inline void timerqueue_init(struct timerqueue_node *node) +{ + RB_CLEAR_NODE(&node->node); +} + +static inline void timerqueue_init_head(struct timerqueue_head *head) +{ + head->head = RB_ROOT; + head->next = NULL; +} +#endif /* _LINUX_TIMERQUEUE_H */ diff --git a/lib/Makefile b/lib/Makefile index 8b475cfb8195..9e2db72d128e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -8,7 +8,7 @@ KBUILD_CFLAGS = $(subst -pg,,$(ORIG_CFLAGS)) endif lib-y := ctype.o string.o vsprintf.o cmdline.o \ - rbtree.o radix-tree.o dump_stack.o timerlist.o\ + rbtree.o radix-tree.o dump_stack.o timerqueue.o\ idr.o int_sqrt.o extable.o prio_tree.o \ sha1.o irq_regs.o reciprocal_div.o argv_split.o \ proportions.o prio_heap.o ratelimit.o show_mem.o \ diff --git a/lib/timerlist.c b/lib/timerlist.c deleted file mode 100644 index 9101b42fd13d..000000000000 --- a/lib/timerlist.c +++ /dev/null @@ -1,118 +0,0 @@ -/* - * Generic Timer-list - * - * Manages a simple list of timers, ordered by expiration time. - * Uses rbtrees for quick list adds and expiration. - * - * NOTE: All of the following functions need to be serialized - * to avoid races. No locking is done by this libary code. - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -#include -#include - -/** - * timerlist_add - Adds timer to timerlist. - * - * @head: head of timerlist - * @node: timer node to be added - * - * Adds the timer node to the timerlist, sorted by the - * node's expires value. - */ -void timerlist_add(struct timerlist_head *head, struct timerlist_node *node) -{ - struct rb_node **p = &head->head.rb_node; - struct rb_node *parent = NULL; - struct timerlist_node *ptr; - - /* Make sure we don't add nodes that are already added */ - WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); - - while (*p) { - parent = *p; - ptr = rb_entry(parent, struct timerlist_node, node); - if (node->expires.tv64 < ptr->expires.tv64) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } - rb_link_node(&node->node, parent, p); - rb_insert_color(&node->node, &head->head); - - if (!head->next || node->expires.tv64 < head->next->expires.tv64) - head->next = node; -} - -/** - * timerlist_del - Removes a timer from the timerlist. - * - * @head: head of timerlist - * @node: timer node to be removed - * - * Removes the timer node from the timerlist. - */ -void timerlist_del(struct timerlist_head *head, struct timerlist_node *node) -{ - WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); - - /* update next pointer */ - if (head->next == node) { - struct rb_node *rbn = rb_next(&node->node); - - head->next = rbn ? - rb_entry(rbn, struct timerlist_node, node) : NULL; - } - rb_erase(&node->node, &head->head); - RB_CLEAR_NODE(&node->node); -} - - -/** - * timerlist_getnext - Returns the timer with the earlies expiration time - * - * @head: head of timerlist - * - * Returns a pointer to the timer node that has the - * earliest expiration time. - */ -struct timerlist_node *timerlist_getnext(struct timerlist_head *head) -{ - return head->next; -} - - -/** - * timerlist_iterate_next - Returns the timer after the provided timer - * - * @node: Pointer to a timer. - * - * Provides the timer that is after the given node. This is used, when - * necessary, to iterate through the list of timers in a timer list - * without modifying the list. - */ -struct timerlist_node *timerlist_iterate_next(struct timerlist_node *node) -{ - struct rb_node *next; - - if (!node) - return NULL; - next = rb_next(&node->node); - if (!next) - return NULL; - return container_of(next, struct timerlist_node, node); -} diff --git a/lib/timerqueue.c b/lib/timerqueue.c new file mode 100644 index 000000000000..f46de84d9467 --- /dev/null +++ b/lib/timerqueue.c @@ -0,0 +1,118 @@ +/* + * Generic Timer-queue + * + * Manages a simple queue of timers, ordered by expiration time. + * Uses rbtrees for quick list adds and expiration. + * + * NOTE: All of the following functions need to be serialized + * to avoid races. No locking is done by this libary code. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + */ + +#include +#include + +/** + * timerqueue_add - Adds timer to timerqueue. + * + * @head: head of timerqueue + * @node: timer node to be added + * + * Adds the timer node to the timerqueue, sorted by the + * node's expires value. + */ +void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) +{ + struct rb_node **p = &head->head.rb_node; + struct rb_node *parent = NULL; + struct timerqueue_node *ptr; + + /* Make sure we don't add nodes that are already added */ + WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node)); + + while (*p) { + parent = *p; + ptr = rb_entry(parent, struct timerqueue_node, node); + if (node->expires.tv64 < ptr->expires.tv64) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + rb_link_node(&node->node, parent, p); + rb_insert_color(&node->node, &head->head); + + if (!head->next || node->expires.tv64 < head->next->expires.tv64) + head->next = node; +} + +/** + * timerqueue_del - Removes a timer from the timerqueue. + * + * @head: head of timerqueue + * @node: timer node to be removed + * + * Removes the timer node from the timerqueue. + */ +void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) +{ + WARN_ON_ONCE(RB_EMPTY_NODE(&node->node)); + + /* update next pointer */ + if (head->next == node) { + struct rb_node *rbn = rb_next(&node->node); + + head->next = rbn ? + rb_entry(rbn, struct timerqueue_node, node) : NULL; + } + rb_erase(&node->node, &head->head); + RB_CLEAR_NODE(&node->node); +} + + +/** + * timerqueue_getnext - Returns the timer with the earlies expiration time + * + * @head: head of timerqueue + * + * Returns a pointer to the timer node that has the + * earliest expiration time. + */ +struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) +{ + return head->next; +} + + +/** + * timerqueue_iterate_next - Returns the timer after the provided timer + * + * @node: Pointer to a timer. + * + * Provides the timer that is after the given node. This is used, when + * necessary, to iterate through the list of timers in a timer list + * without modifying the list. + */ +struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) +{ + struct rb_node *next; + + if (!node) + return NULL; + next = rb_next(&node->node); + if (!next) + return NULL; + return container_of(next, struct timerqueue_node, node); +} -- cgit v1.2.3 From 9bb99b147018945366c763b3d4d7008927dc8557 Mon Sep 17 00:00:00 2001 From: John Stultz Date: Mon, 6 Dec 2010 13:32:12 -0800 Subject: timers: Fixup allmodconfig build issue Adds missed EXPORT_SYMBOL lines that cause the following build failures with allmodconfig: ERROR: "timerqueue_add" [drivers/rtc/rtc-core.ko] undefined! ERROR: "timerqueue_getnext" [drivers/rtc/rtc-core.ko] undefined! ERROR: "timerqueue_del" [drivers/rtc/rtc-core.ko] undefined! Reported-by: Ingo Molnar Reported-by: Thomas Gleixner Signed-off-by: John Stultz --- lib/timerqueue.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/timerqueue.c b/lib/timerqueue.c index f46de84d9467..444b0934af92 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -24,6 +24,7 @@ #include #include +#include /** * timerqueue_add - Adds timer to timerqueue. @@ -57,6 +58,7 @@ void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node) if (!head->next || node->expires.tv64 < head->next->expires.tv64) head->next = node; } +EXPORT_SYMBOL_GPL(timerqueue_add); /** * timerqueue_del - Removes a timer from the timerqueue. @@ -80,7 +82,7 @@ void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) rb_erase(&node->node, &head->head); RB_CLEAR_NODE(&node->node); } - +EXPORT_SYMBOL_GPL(timerqueue_del); /** * timerqueue_getnext - Returns the timer with the earlies expiration time @@ -94,7 +96,7 @@ struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) { return head->next; } - +EXPORT_SYMBOL_GPL(timerqueue_getnext); /** * timerqueue_iterate_next - Returns the timer after the provided timer @@ -116,3 +118,4 @@ struct timerqueue_node *timerqueue_iterate_next(struct timerqueue_node *node) return NULL; return container_of(next, struct timerqueue_node, node); } +EXPORT_SYMBOL_GPL(timerqueue_iterate_next); -- cgit v1.2.3 From 45f74264e18449cf3c93cccaf098ee6e9524ab78 Mon Sep 17 00:00:00 2001 From: Thomas Gleixner Date: Sat, 11 Dec 2010 12:34:34 +0100 Subject: timerqueue: Make timerqueue_getnext() static inline No point in calling a function just to dereference a pointer. Signed-off-by: Thomas Gleixner Cc: John Stultz --- include/linux/timerqueue.h | 15 ++++++++++++++- lib/timerqueue.c | 14 -------------- 2 files changed, 14 insertions(+), 15 deletions(-) (limited to 'lib') diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h index 406b103894bd..d24aabaca474 100644 --- a/include/linux/timerqueue.h +++ b/include/linux/timerqueue.h @@ -20,10 +20,23 @@ extern void timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node); extern void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node); -extern struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head); extern struct timerqueue_node *timerqueue_iterate_next( struct timerqueue_node *node); +/** + * timerqueue_getnext - Returns the timer with the earlies expiration time + * + * @head: head of timerqueue + * + * Returns a pointer to the timer node that has the + * earliest expiration time. + */ +static inline +struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) +{ + return head->next; +} + static inline void timerqueue_init(struct timerqueue_node *node) { RB_CLEAR_NODE(&node->node); diff --git a/lib/timerqueue.c b/lib/timerqueue.c index 444b0934af92..e3a1050e6820 100644 --- a/lib/timerqueue.c +++ b/lib/timerqueue.c @@ -84,20 +84,6 @@ void timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node) } EXPORT_SYMBOL_GPL(timerqueue_del); -/** - * timerqueue_getnext - Returns the timer with the earlies expiration time - * - * @head: head of timerqueue - * - * Returns a pointer to the timer node that has the - * earliest expiration time. - */ -struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head) -{ - return head->next; -} -EXPORT_SYMBOL_GPL(timerqueue_getnext); - /** * timerqueue_iterate_next - Returns the timer after the provided timer * -- cgit v1.2.3 From 819a72af8d6653daa48334f24ce0a935ccdd33c7 Mon Sep 17 00:00:00 2001 From: Christoph Lameter Date: Mon, 6 Dec 2010 11:16:19 -0600 Subject: percpucounter: Optimize __percpu_counter_add a bit through the use of this_cpu() options. The this_cpu_* options can be used to optimize __percpu_counter_add a bit. Avoids some address arithmetic and saves 12 bytes. Before: 00000000000001d3 <__percpu_counter_add>: 1d3: 55 push %rbp 1d4: 48 89 e5 mov %rsp,%rbp 1d7: 41 55 push %r13 1d9: 41 54 push %r12 1db: 53 push %rbx 1dc: 48 89 fb mov %rdi,%rbx 1df: 48 83 ec 08 sub $0x8,%rsp 1e3: 4c 8b 67 30 mov 0x30(%rdi),%r12 1e7: 65 4c 03 24 25 00 00 add %gs:0x0,%r12 1ee: 00 00 1f0: 4d 63 2c 24 movslq (%r12),%r13 1f4: 48 63 c2 movslq %edx,%rax 1f7: 49 01 f5 add %rsi,%r13 1fa: 49 39 c5 cmp %rax,%r13 1fd: 7d 0a jge 209 <__percpu_counter_add+0x36> 1ff: f7 da neg %edx 201: 48 63 d2 movslq %edx,%rdx 204: 49 39 d5 cmp %rdx,%r13 207: 7f 1e jg 227 <__percpu_counter_add+0x54> 209: 48 89 df mov %rbx,%rdi 20c: e8 00 00 00 00 callq 211 <__percpu_counter_add+0x3e> 211: 4c 01 6b 18 add %r13,0x18(%rbx) 215: 48 89 df mov %rbx,%rdi 218: 41 c7 04 24 00 00 00 movl $0x0,(%r12) 21f: 00 220: e8 00 00 00 00 callq 225 <__percpu_counter_add+0x52> 225: eb 04 jmp 22b <__percpu_counter_add+0x58> 227: 45 89 2c 24 mov %r13d,(%r12) 22b: 5b pop %rbx 22c: 5b pop %rbx 22d: 41 5c pop %r12 22f: 41 5d pop %r13 231: c9 leaveq 232: c3 retq After: 00000000000001d3 <__percpu_counter_add>: 1d3: 55 push %rbp 1d4: 48 63 ca movslq %edx,%rcx 1d7: 48 89 e5 mov %rsp,%rbp 1da: 41 54 push %r12 1dc: 53 push %rbx 1dd: 48 89 fb mov %rdi,%rbx 1e0: 48 8b 47 30 mov 0x30(%rdi),%rax 1e4: 65 44 8b 20 mov %gs:(%rax),%r12d 1e8: 4d 63 e4 movslq %r12d,%r12 1eb: 49 01 f4 add %rsi,%r12 1ee: 49 39 cc cmp %rcx,%r12 1f1: 7d 0a jge 1fd <__percpu_counter_add+0x2a> 1f3: f7 da neg %edx 1f5: 48 63 d2 movslq %edx,%rdx 1f8: 49 39 d4 cmp %rdx,%r12 1fb: 7f 21 jg 21e <__percpu_counter_add+0x4b> 1fd: 48 89 df mov %rbx,%rdi 200: e8 00 00 00 00 callq 205 <__percpu_counter_add+0x32> 205: 4c 01 63 18 add %r12,0x18(%rbx) 209: 48 8b 43 30 mov 0x30(%rbx),%rax 20d: 48 89 df mov %rbx,%rdi 210: 65 c7 00 00 00 00 00 movl $0x0,%gs:(%rax) 217: e8 00 00 00 00 callq 21c <__percpu_counter_add+0x49> 21c: eb 04 jmp 222 <__percpu_counter_add+0x4f> 21e: 65 44 89 20 mov %r12d,%gs:(%rax) 222: 5b pop %rbx 223: 41 5c pop %r12 225: c9 leaveq 226: c3 retq Reviewed-by: Pekka Enberg Reviewed-by: Tejun Heo Reviewed-by: Mathieu Desnoyers Acked-by: H. Peter Anvin Signed-off-by: Christoph Lameter Signed-off-by: Tejun Heo --- lib/percpu_counter.c | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/percpu_counter.c b/lib/percpu_counter.c index 604678d7d06d..28f2c33c6b53 100644 --- a/lib/percpu_counter.c +++ b/lib/percpu_counter.c @@ -72,18 +72,16 @@ EXPORT_SYMBOL(percpu_counter_set); void __percpu_counter_add(struct percpu_counter *fbc, s64 amount, s32 batch) { s64 count; - s32 *pcount; preempt_disable(); - pcount = this_cpu_ptr(fbc->counters); - count = *pcount + amount; + count = __this_cpu_read(*fbc->counters) + amount; if (count >= batch || count <= -batch) { spin_lock(&fbc->lock); fbc->count += count; - *pcount = 0; + __this_cpu_write(*fbc->counters, 0); spin_unlock(&fbc->lock); } else { - *pcount = count; + __this_cpu_write(*fbc->counters, count); } preempt_enable(); } -- cgit v1.2.3 From 4a7863cc2eb5f9804f1c4e9156619a801cd7f14f Mon Sep 17 00:00:00 2001 From: Don Zickus Date: Wed, 22 Dec 2010 14:00:03 -0500 Subject: x86, nmi_watchdog: Remove ARCH_HAS_NMI_WATCHDOG and rely on CONFIG_HARDLOCKUP_DETECTOR The x86 arch has shifted its use of the nmi_watchdog from a local implementation to the global one provide by kernel/watchdog.c. This shift has caused a whole bunch of compile problems under different config options. I attempt to simplify things with the patch below. In order to simplify things, I had to come to terms with the meaning of two terms ARCH_HAS_NMI_WATCHDOG and CONFIG_HARDLOCKUP_DETECTOR. Basically they mean the same thing, the former on a local level and the latter on a global level. With the old x86 nmi watchdog gone, there is no need to rely on defining the ARCH_HAS_NMI_WATCHDOG variable because it doesn't make sense any more. x86 will now use the global implementation. The changes below do a few things. First it changes the few places that relied on ARCH_HAS_NMI_WATCHDOG to use CONFIG_X86_LOCAL_APIC (the former was an alias for the latter anyway, so nothing unusual here). Those pieces of code were relying more on local apic functionality the nmi watchdog functionality, so the change should make sense. Second, I removed the x86 implementation of touch_nmi_watchdog(). It isn't need now, instead x86 will rely on kernel/watchdog.c's implementation. Third, I removed the #define ARCH_HAS_NMI_WATCHDOG itself from x86. And tweaked the include/linux/nmi.h file to tell users to look for an externally defined touch_nmi_watchdog in the case of ARCH_HAS_NMI_WATCHDOG _or_ CONFIG_HARDLOCKUP_DETECTOR. This changes removes some of the ugliness in that file. Finally, I added a Kconfig dependency for CONFIG_HARDLOCKUP_DETECTOR that said you can't have ARCH_HAS_NMI_WATCHDOG _and_ CONFIG_HARDLOCKUP_DETECTOR. You can only have one nmi_watchdog. Tested with ARCH=i386: allnoconfig, defconfig, allyesconfig, (various broken configs) ARCH=x86_64: allnoconfig, defconfig, allyesconfig, (various broken configs) Hopefully, after this patch I won't get any more compile broken emails. :-) v3: changed a couple of 'linux/nmi.h' -> 'asm/nmi.h' to pick-up correct function prototypes when CONFIG_HARDLOCKUP_DETECTOR is not set. Signed-off-by: Don Zickus Cc: Peter Zijlstra Cc: fweisbec@gmail.com LKML-Reference: <1293044403-14117-1-git-send-email-dzickus@redhat.com> Signed-off-by: Ingo Molnar --- arch/x86/include/asm/irq.h | 4 ---- arch/x86/include/asm/nmi.h | 2 +- arch/x86/kernel/apic/hw_nmi.c | 10 ---------- arch/x86/kernel/cpu/perfctr-watchdog.c | 2 +- arch/x86/oprofile/op_model_p4.c | 2 +- drivers/watchdog/hpwdt.c | 4 ++-- include/linux/nmi.h | 6 +----- lib/Kconfig.debug | 3 ++- 8 files changed, 8 insertions(+), 25 deletions(-) (limited to 'lib') diff --git a/arch/x86/include/asm/irq.h b/arch/x86/include/asm/irq.h index 13b0ebaa512f..ba870bb6dd8e 100644 --- a/arch/x86/include/asm/irq.h +++ b/arch/x86/include/asm/irq.h @@ -15,10 +15,6 @@ static inline int irq_canonicalize(int irq) return ((irq == 2) ? 9 : irq); } -#ifdef CONFIG_X86_LOCAL_APIC -# define ARCH_HAS_NMI_WATCHDOG -#endif - #ifdef CONFIG_X86_32 extern void irq_ctx_init(int cpu); #else diff --git a/arch/x86/include/asm/nmi.h b/arch/x86/include/asm/nmi.h index 3545838cddeb..c4021b953510 100644 --- a/arch/x86/include/asm/nmi.h +++ b/arch/x86/include/asm/nmi.h @@ -5,7 +5,7 @@ #include #include -#ifdef ARCH_HAS_NMI_WATCHDOG +#ifdef CONFIG_X86_LOCAL_APIC extern void die_nmi(char *str, struct pt_regs *regs, int do_panic); extern int avail_to_resrv_perfctr_nmi_bit(unsigned int); diff --git a/arch/x86/kernel/apic/hw_nmi.c b/arch/x86/kernel/apic/hw_nmi.c index 93da91df5b38..c57d0b599448 100644 --- a/arch/x86/kernel/apic/hw_nmi.c +++ b/arch/x86/kernel/apic/hw_nmi.c @@ -17,7 +17,6 @@ #include #include -#ifdef ARCH_HAS_NMI_WATCHDOG #ifdef CONFIG_HARDLOCKUP_DETECTOR u64 hw_nmi_get_sample_period(void) { @@ -25,15 +24,6 @@ u64 hw_nmi_get_sample_period(void) } #endif -#ifndef CONFIG_HARDLOCKUP_DETECTOR -void touch_nmi_watchdog(void) -{ - touch_softlockup_watchdog(); -} -EXPORT_SYMBOL(touch_nmi_watchdog); -#endif -#endif - #ifdef arch_trigger_all_cpu_backtrace /* For reliability, we're prepared to waste bits here. */ static DECLARE_BITMAP(backtrace_mask, NR_CPUS) __read_mostly; diff --git a/arch/x86/kernel/cpu/perfctr-watchdog.c b/arch/x86/kernel/cpu/perfctr-watchdog.c index 14d45928c282..d5a236615501 100644 --- a/arch/x86/kernel/cpu/perfctr-watchdog.c +++ b/arch/x86/kernel/cpu/perfctr-watchdog.c @@ -16,7 +16,7 @@ #include #include #include -#include +#include #include #include diff --git a/arch/x86/oprofile/op_model_p4.c b/arch/x86/oprofile/op_model_p4.c index 182558dd5515..9fadec074142 100644 --- a/arch/x86/oprofile/op_model_p4.c +++ b/arch/x86/oprofile/op_model_p4.c @@ -11,7 +11,7 @@ #include #include #include -#include +#include #include #include #include diff --git a/drivers/watchdog/hpwdt.c b/drivers/watchdog/hpwdt.c index c19f4a20794a..dea7b5bf6e2c 100644 --- a/drivers/watchdog/hpwdt.c +++ b/drivers/watchdog/hpwdt.c @@ -642,7 +642,7 @@ static struct notifier_block die_notifier = { */ #ifdef CONFIG_HPWDT_NMI_DECODING -#ifdef ARCH_HAS_NMI_WATCHDOG +#ifdef CONFIG_X86_LOCAL_APIC static void __devinit hpwdt_check_nmi_decoding(struct pci_dev *dev) { /* @@ -657,7 +657,7 @@ static void __devinit hpwdt_check_nmi_decoding(struct pci_dev *dev) dev_warn(&dev->dev, "NMI decoding is disabled. " "Your kernel does not support a NMI Watchdog.\n"); } -#endif /* ARCH_HAS_NMI_WATCHDOG */ +#endif /* CONFIG_X86_LOCAL_APIC */ static int __devinit hpwdt_init_nmi_decoding(struct pci_dev *dev) { diff --git a/include/linux/nmi.h b/include/linux/nmi.h index 17ccf44e7dcb..c536f8545f74 100644 --- a/include/linux/nmi.h +++ b/include/linux/nmi.h @@ -14,18 +14,14 @@ * may be used to reset the timeout - for code which intentionally * disables interrupts for a long time. This call is stateless. */ -#ifdef ARCH_HAS_NMI_WATCHDOG +#if defined(ARCH_HAS_NMI_WATCHDOG) || defined(CONFIG_HARDLOCKUP_DETECTOR) #include extern void touch_nmi_watchdog(void); #else -#ifndef CONFIG_HARDLOCKUP_DETECTOR static inline void touch_nmi_watchdog(void) { touch_softlockup_watchdog(); } -#else -extern void touch_nmi_watchdog(void); -#endif #endif /* diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 28b42b9274d0..2d05adb98401 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -173,7 +173,8 @@ config LOCKUP_DETECTOR An NMI is generated every 60 seconds or so to check for hardlockups. config HARDLOCKUP_DETECTOR - def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI + def_bool LOCKUP_DETECTOR && PERF_EVENTS && HAVE_PERF_EVENTS_NMI && \ + !ARCH_HAS_NMI_WATCHDOG config BOOTPARAM_SOFTLOCKUP_PANIC bool "Panic (Reboot) On Soft Lockups" -- cgit v1.2.3