From d7c816733d501b59dbdc2483f2cc8e4431fd9160 Mon Sep 17 00:00:00 2001 From: Kees Cook Date: Wed, 17 Aug 2016 14:42:08 -0700 Subject: list: Split list_add() debug checking into separate function Right now, __list_add() code is repeated either in list.h or in list_debug.c, but the only differences between the two versions are the debug checks. This commit therefore extracts these debug checks into a separate __list_add_valid() function and consolidates __list_add(). Additionally this new __list_add_valid() function will stop list manipulations if a corruption is detected, instead of allowing for further corruption that may lead to even worse conditions. This is slight refactoring of the same hardening done in PaX and Grsecurity. Signed-off-by: Kees Cook Acked-by: Steven Rostedt Signed-off-by: Paul E. McKenney Acked-by: Rik van Riel --- include/linux/list.h | 22 ++++++++++++++++------ 1 file changed, 16 insertions(+), 6 deletions(-) (limited to 'include') diff --git a/include/linux/list.h b/include/linux/list.h index 5809e9a2de5b..b6da9b1dce4d 100644 --- a/include/linux/list.h +++ b/include/linux/list.h @@ -28,27 +28,37 @@ static inline void INIT_LIST_HEAD(struct list_head *list) list->prev = list; } +#ifdef CONFIG_DEBUG_LIST +extern bool __list_add_valid(struct list_head *new, + struct list_head *prev, + struct list_head *next); +#else +static inline bool __list_add_valid(struct list_head *new, + struct list_head *prev, + struct list_head *next) +{ + return true; +} +#endif + /* * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ -#ifndef CONFIG_DEBUG_LIST static inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next) { + if (!__list_add_valid(new, prev, next)) + return; + next->prev = new; new->next = next; new->prev = prev; WRITE_ONCE(prev->next, new); } -#else -extern void __list_add(struct list_head *new, - struct list_head *prev, - struct list_head *next); -#endif /** * list_add - add a new entry -- cgit v1.2.3 From 54acd4397d7e7a725c94101180cd9f38ef701acc Mon Sep 17 00:00:00 2001 From: Kees Cook Date: Wed, 17 Aug 2016 14:42:09 -0700 Subject: rculist: Consolidate DEBUG_LIST for list_add_rcu() This commit consolidates the debug checking for list_add_rcu() into the new single __list_add_valid() debug function. Notably, this commit fixes the sanity check that was added in commit 17a801f4bfeb ("list_debug: WARN for adding something already in the list"), which wasn't checking RCU-protected lists. Signed-off-by: Kees Cook Acked-by: Steven Rostedt Signed-off-by: Paul E. McKenney Acked-by: Rik van Riel --- include/linux/rculist.h | 8 +++----- lib/list_debug.c | 19 ------------------- 2 files changed, 3 insertions(+), 24 deletions(-) (limited to 'include') diff --git a/include/linux/rculist.h b/include/linux/rculist.h index 8beb98dcf14f..4f7a9561b8c4 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -45,19 +45,17 @@ static inline void INIT_LIST_HEAD_RCU(struct list_head *list) * This is only for internal list manipulation where we know * the prev/next entries already! */ -#ifndef CONFIG_DEBUG_LIST static inline void __list_add_rcu(struct list_head *new, struct list_head *prev, struct list_head *next) { + if (!__list_add_valid(new, prev, next)) + return; + new->next = next; new->prev = prev; rcu_assign_pointer(list_next_rcu(prev), new); next->prev = new; } -#else -void __list_add_rcu(struct list_head *new, - struct list_head *prev, struct list_head *next); -#endif /** * list_add_rcu - add a new entry to rcu-protected list diff --git a/lib/list_debug.c b/lib/list_debug.c index 149dd57b583b..d0b89b9d0736 100644 --- a/lib/list_debug.c +++ b/lib/list_debug.c @@ -77,22 +77,3 @@ void list_del(struct list_head *entry) entry->prev = LIST_POISON2; } EXPORT_SYMBOL(list_del); - -/* - * RCU variants. - */ -void __list_add_rcu(struct list_head *new, - struct list_head *prev, struct list_head *next) -{ - WARN(next->prev != prev, - "list_add_rcu corruption. next->prev should be prev (%p), but was %p. (next=%p).\n", - prev, next->prev, next); - WARN(prev->next != next, - "list_add_rcu corruption. prev->next should be next (%p), but was %p. (prev=%p).\n", - next, prev->next, prev); - new->next = next; - new->prev = prev; - rcu_assign_pointer(list_next_rcu(prev), new); - next->prev = new; -} -EXPORT_SYMBOL(__list_add_rcu); -- cgit v1.2.3 From 0cd340dcb05c4a43742fe156f36737bb2a321bfd Mon Sep 17 00:00:00 2001 From: Kees Cook Date: Wed, 17 Aug 2016 14:42:10 -0700 Subject: list: Split list_del() debug checking into separate function Similar to the list_add() debug consolidation, this commit consolidates the debug checking performed during CONFIG_DEBUG_LIST into a new __list_del_entry_valid() function, and stops list updates when corruption is found. Refactored from same hardening in PaX and Grsecurity. Signed-off-by: Kees Cook Acked-by: Steven Rostedt Signed-off-by: Paul E. McKenney Acked-by: Rik van Riel --- include/linux/list.h | 15 +++++++++------ lib/list_debug.c | 53 +++++++++++++++++++++++----------------------------- 2 files changed, 32 insertions(+), 36 deletions(-) (limited to 'include') diff --git a/include/linux/list.h b/include/linux/list.h index b6da9b1dce4d..d1039ecaf94f 100644 --- a/include/linux/list.h +++ b/include/linux/list.h @@ -32,6 +32,7 @@ static inline void INIT_LIST_HEAD(struct list_head *list) extern bool __list_add_valid(struct list_head *new, struct list_head *prev, struct list_head *next); +extern bool __list_del_entry_valid(struct list_head *entry); #else static inline bool __list_add_valid(struct list_head *new, struct list_head *prev, @@ -39,6 +40,10 @@ static inline bool __list_add_valid(struct list_head *new, { return true; } +static inline bool __list_del_entry_valid(struct list_head *entry) +{ + return true; +} #endif /* @@ -106,22 +111,20 @@ static inline void __list_del(struct list_head * prev, struct list_head * next) * Note: list_empty() on entry does not return true after this, the entry is * in an undefined state. */ -#ifndef CONFIG_DEBUG_LIST static inline void __list_del_entry(struct list_head *entry) { + if (!__list_del_entry_valid(entry)) + return; + __list_del(entry->prev, entry->next); } static inline void list_del(struct list_head *entry) { - __list_del(entry->prev, entry->next); + __list_del_entry(entry); entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } -#else -extern void __list_del_entry(struct list_head *entry); -extern void list_del(struct list_head *entry); -#endif /** * list_replace - replace old entry by new one diff --git a/lib/list_debug.c b/lib/list_debug.c index d0b89b9d0736..276565fca2a6 100644 --- a/lib/list_debug.c +++ b/lib/list_debug.c @@ -39,41 +39,34 @@ bool __list_add_valid(struct list_head *new, struct list_head *prev, } EXPORT_SYMBOL(__list_add_valid); -void __list_del_entry(struct list_head *entry) +bool __list_del_entry_valid(struct list_head *entry) { struct list_head *prev, *next; prev = entry->prev; next = entry->next; - if (WARN(next == LIST_POISON1, - "list_del corruption, %p->next is LIST_POISON1 (%p)\n", - entry, LIST_POISON1) || - WARN(prev == LIST_POISON2, - "list_del corruption, %p->prev is LIST_POISON2 (%p)\n", - entry, LIST_POISON2) || - WARN(prev->next != entry, - "list_del corruption. prev->next should be %p, " - "but was %p\n", entry, prev->next) || - WARN(next->prev != entry, - "list_del corruption. next->prev should be %p, " - "but was %p\n", entry, next->prev)) - return; - - __list_del(prev, next); -} -EXPORT_SYMBOL(__list_del_entry); + if (unlikely(next == LIST_POISON1)) { + WARN(1, "list_del corruption, %p->next is LIST_POISON1 (%p)\n", + entry, LIST_POISON1); + return false; + } + if (unlikely(prev == LIST_POISON2)) { + WARN(1, "list_del corruption, %p->prev is LIST_POISON2 (%p)\n", + entry, LIST_POISON2); + return false; + } + if (unlikely(prev->next != entry)) { + WARN(1, "list_del corruption. prev->next should be %p, but was %p\n", + entry, prev->next); + return false; + } + if (unlikely(next->prev != entry)) { + WARN(1, "list_del corruption. next->prev should be %p, but was %p\n", + entry, next->prev); + return false; + } + return true; -/** - * list_del - deletes entry from list. - * @entry: the element to delete from the list. - * Note: list_empty on entry does not return true after this, the entry is - * in an undefined state. - */ -void list_del(struct list_head *entry) -{ - __list_del_entry(entry); - entry->next = LIST_POISON1; - entry->prev = LIST_POISON2; } -EXPORT_SYMBOL(list_del); +EXPORT_SYMBOL(__list_del_entry_valid); -- cgit v1.2.3 From de54ebbe26bb371a6f1fbc0593372232f04e3107 Mon Sep 17 00:00:00 2001 From: Kees Cook Date: Wed, 17 Aug 2016 14:42:11 -0700 Subject: bug: Provide toggle for BUG on data corruption The kernel checks for cases of data structure corruption under some CONFIGs (e.g. CONFIG_DEBUG_LIST). When corruption is detected, some systems may want to BUG() immediately instead of letting the system run with known corruption. Usually these kinds of manipulation primitives can be used by security flaws to gain arbitrary memory write control. This provides a new config CONFIG_BUG_ON_DATA_CORRUPTION and a corresponding macro CHECK_DATA_CORRUPTION for handling these situations. Notably, even if not BUGing, the kernel should not continue processing the corrupted structure. This is inspired by similar hardening by Syed Rameez Mustafa in MSM kernels, and in PaX and Grsecurity, which is likely in response to earlier removal of the BUG calls in commit 924d9addb9b1 ("list debugging: use WARN() instead of BUG()"). Signed-off-by: Kees Cook Acked-by: Steven Rostedt Signed-off-by: Paul E. McKenney Acked-by: Rik van Riel --- include/linux/bug.h | 17 ++++++++++++++++ lib/Kconfig.debug | 10 ++++++++++ lib/list_debug.c | 57 +++++++++++++++++++++-------------------------------- 3 files changed, 49 insertions(+), 35 deletions(-) (limited to 'include') diff --git a/include/linux/bug.h b/include/linux/bug.h index 292d6a10b0c2..baff2e8fc8a8 100644 --- a/include/linux/bug.h +++ b/include/linux/bug.h @@ -121,4 +121,21 @@ static inline enum bug_trap_type report_bug(unsigned long bug_addr, } #endif /* CONFIG_GENERIC_BUG */ + +/* + * Since detected data corruption should stop operation on the affected + * structures, this returns false if the corruption condition is found. + */ +#define CHECK_DATA_CORRUPTION(condition, fmt, ...) \ + do { \ + if (unlikely(condition)) { \ + if (IS_ENABLED(CONFIG_BUG_ON_DATA_CORRUPTION)) { \ + pr_err(fmt, ##__VA_ARGS__); \ + BUG(); \ + } else \ + WARN(1, fmt, ##__VA_ARGS__); \ + return false; \ + } \ + } while (0) + #endif /* _LINUX_BUG_H */ diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 33bc56cf60d7..07a6fac930c5 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1960,6 +1960,16 @@ config TEST_STATIC_KEYS If unsure, say N. +config BUG_ON_DATA_CORRUPTION + bool "Trigger a BUG when data corruption is detected" + select CONFIG_DEBUG_LIST + help + Select this option if the kernel should BUG when it encounters + data corruption in kernel memory structures when they get checked + for validity. + + If unsure, say N. + source "samples/Kconfig" source "lib/Kconfig.kgdb" diff --git a/lib/list_debug.c b/lib/list_debug.c index 276565fca2a6..7f7bfa55eb6d 100644 --- a/lib/list_debug.c +++ b/lib/list_debug.c @@ -20,21 +20,16 @@ bool __list_add_valid(struct list_head *new, struct list_head *prev, struct list_head *next) { - if (unlikely(next->prev != prev)) { - WARN(1, "list_add corruption. next->prev should be prev (%p), but was %p. (next=%p).\n", - prev, next->prev, next); - return false; - } - if (unlikely(prev->next != next)) { - WARN(1, "list_add corruption. prev->next should be next (%p), but was %p. (prev=%p).\n", - next, prev->next, prev); - return false; - } - if (unlikely(new == prev || new == next)) { - WARN(1, "list_add double add: new=%p, prev=%p, next=%p.\n", - new, prev, next); - return false; - } + CHECK_DATA_CORRUPTION(next->prev != prev, + "list_add corruption. next->prev should be prev (%p), but was %p. (next=%p).\n", + prev, next->prev, next); + CHECK_DATA_CORRUPTION(prev->next != next, + "list_add corruption. prev->next should be next (%p), but was %p. (prev=%p).\n", + next, prev->next, prev); + CHECK_DATA_CORRUPTION(new == prev || new == next, + "list_add double add: new=%p, prev=%p, next=%p.\n", + new, prev, next); + return true; } EXPORT_SYMBOL(__list_add_valid); @@ -46,26 +41,18 @@ bool __list_del_entry_valid(struct list_head *entry) prev = entry->prev; next = entry->next; - if (unlikely(next == LIST_POISON1)) { - WARN(1, "list_del corruption, %p->next is LIST_POISON1 (%p)\n", - entry, LIST_POISON1); - return false; - } - if (unlikely(prev == LIST_POISON2)) { - WARN(1, "list_del corruption, %p->prev is LIST_POISON2 (%p)\n", - entry, LIST_POISON2); - return false; - } - if (unlikely(prev->next != entry)) { - WARN(1, "list_del corruption. prev->next should be %p, but was %p\n", - entry, prev->next); - return false; - } - if (unlikely(next->prev != entry)) { - WARN(1, "list_del corruption. next->prev should be %p, but was %p\n", - entry, next->prev); - return false; - } + CHECK_DATA_CORRUPTION(next == LIST_POISON1, + "list_del corruption, %p->next is LIST_POISON1 (%p)\n", + entry, LIST_POISON1); + CHECK_DATA_CORRUPTION(prev == LIST_POISON2, + "list_del corruption, %p->prev is LIST_POISON2 (%p)\n", + entry, LIST_POISON2); + CHECK_DATA_CORRUPTION(prev->next != entry, + "list_del corruption. prev->next should be %p, but was %p\n", + entry, prev->next); + CHECK_DATA_CORRUPTION(next->prev != entry, + "list_del corruption. next->prev should be %p, but was %p\n", + entry, next->prev); return true; } -- cgit v1.2.3 From d0af39e89ec59fe7c92c4bcbc2d652ea4c0ee644 Mon Sep 17 00:00:00 2001 From: "Paul E. McKenney" Date: Mon, 10 Oct 2016 18:26:04 -0700 Subject: torture: Trace long read-side delays Although rcutorture will occasionally do a 50-millisecond grace-period delay, these delays are quite rare. And rightly so, because otherwise the read rate would be quite low. Thie means that it can be important to identify whether or not a given run contained a long-delay read. This commit therefore inserts a trace_rcu_torture_read() event to flag runs containing long delays. Signed-off-by: Paul E. McKenney --- include/trace/events/rcu.h | 5 ++++- kernel/rcu/rcutorture.c | 11 ++++++++++- 2 files changed, 14 insertions(+), 2 deletions(-) (limited to 'include') diff --git a/include/trace/events/rcu.h b/include/trace/events/rcu.h index d3e756539d44..9d4f9b3a2b7b 100644 --- a/include/trace/events/rcu.h +++ b/include/trace/events/rcu.h @@ -698,7 +698,10 @@ TRACE_EVENT(rcu_batch_end, /* * Tracepoint for rcutorture readers. The first argument is the name * of the RCU flavor from rcutorture's viewpoint and the second argument - * is the callback address. + * is the callback address. The third argument is the start time in + * seconds, and the last two arguments are the grace period numbers + * at the beginning and end of the read, respectively. Note that the + * callback address can be NULL. */ TRACE_EVENT(rcu_torture_read, diff --git a/kernel/rcu/rcutorture.c b/kernel/rcu/rcutorture.c index bf08fee53dc7..87c51225ceec 100644 --- a/kernel/rcu/rcutorture.c +++ b/kernel/rcu/rcutorture.c @@ -289,15 +289,24 @@ static int rcu_torture_read_lock(void) __acquires(RCU) static void rcu_read_delay(struct torture_random_state *rrsp) { + unsigned long started; + unsigned long completed; const unsigned long shortdelay_us = 200; const unsigned long longdelay_ms = 50; + unsigned long long ts; /* We want a short delay sometimes to make a reader delay the grace * period, and we want a long delay occasionally to trigger * force_quiescent_state. */ - if (!(torture_random(rrsp) % (nrealreaders * 2000 * longdelay_ms))) + if (!(torture_random(rrsp) % (nrealreaders * 2000 * longdelay_ms))) { + started = cur_ops->completed(); + ts = rcu_trace_clock_local(); mdelay(longdelay_ms); + completed = cur_ops->completed(); + do_trace_rcu_torture_read(cur_ops->name, NULL, ts, + started, completed); + } if (!(torture_random(rrsp) % (nrealreaders * 2 * shortdelay_us))) udelay(shortdelay_us); #ifdef CONFIG_PREEMPT -- cgit v1.2.3