Skip to contentSkip to conversation

Improve list integrity checking

RFC PATCH Applied Will Deacon 8 participants 58 messages Mar 24, 2020 – May 8, 2020

Subsystems (19)
lore
Share & tools
lore
#0 lore raw

cover Improve list integrity checking

Hi all,

Linked lists appear extensively across the kernel tree in some form or another because they are simple to use and offer efficient addition and removal routines. Unfortunately, they are also an attractive target for people exploiting memory corruption bugs since not only are linked lists susceptible to use-after-free (UAF) issues when used with non-counted references to objects [1], but the APIs can also be abused as powerful stepping stones towards obtaining arbitrary read/write of kernel memory.

A concrete example with an excellent write-up is the exploitation of CVE-2019-2215 ("Bad Binder"):

https://googleprojectzero.blogspot.com/2019/11/bad-binder-android-in-wild-exploit.html

Some other examples are CVE-2015-3636 ("pingpongroot") and a variant of CVE-2019-2025 ("waterdrop").

Before you go and throw away all your computers: fear not! It is common for distributions to enable CONFIG_DEBUG_LIST, which prevents many of these attacks with very little runtime overhead by sanity checking node pointers during add() and del() operations.

Anyway, that's some background. Initially, I just set out to rename CONFIG_DEBUG_LIST to something less "debuggy", a bit like we did for CONFIG_DEBUG_{RODATA,MODULE_RONX} in 0f5bf6d0afe4. However, I quickly ran into some other issues:

1. The KCSAN work has led to some unusual WRITE_ONCE() additions to the list code. These make it difficult to reason about which list functions can run concurrently with one another, which in turn makes it difficult to write sanity checks without locks.

Patches 1-9 try to sort this out.

2. 'hlist' is missing checks, despite being the structure targetted by the "pingpongroot" attack mentioned earlier on. The same goes for 'hlist_nulls'.

Patches 11-13 add these checks.

3. 'list_bl' performs some partial inline checking.

Patches 16, 18 and 19 extend this checking and move it out-of-line to be consistent with the other list checking operations.

4. The LKDTM list tests are fairly limited.

Patch 21 adds tests for all of the new checks.

The other patches do the rename and generally tidy things up to keep the different list implementations consistent with each other. Due to issue (1), this series is based on tip/locking/kcsan [2]

Jann previously made a comment that renaming the CONFIG options could have unexpected results for people using an old config. In fact, building the 'oldconfig' target will prompt you about the new options, so I don't think this is a huge concern. I did try to find a way to leave the old options as dummy symbols, but it just cluttered the Kconfig (a bit like the approach taken by NETFILTER_XT_MATCH_CONNMARK).

Cheers,

Will

[1] https://lore.kernel.org/lkml/?q=%28%22KASAN%3A+use-after-free+in+__list_add_valid%22+OR+%22KASAN%3A+use-after-free+in+__list_del_entry_valid%22%29+-s%3A%22Re%3A%22+-s%3A%22%5BPATCH%22
[2] https://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git/log/?h=locking/kcsan

Cc Eric Dumazet <[email protected]>
Cc Greg Kroah-Hartman <[email protected]
Cc Jann Horn <[email protected]>
Cc Kees Cook <[email protected]>
Cc Maddie Stone <[email protected]>
Cc Marco Elver <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>

--->8

Will Deacon (21):
list: Remove hlist_unhashed_lockless()
list: Remove hlist_nulls_unhashed_lockless()
list: Annotate lockless list primitives with data_race()
timers: Use hlist_unhashed() instead of open-coding in timer_pending()
list: Comment missing WRITE_ONCE() in __list_del()
list: Remove superfluous WRITE_ONCE() from hlist_nulls implementation Revert "list: Use WRITE_ONCE() when adding to lists and hlists" Revert "list: Use WRITE_ONCE() when initializing list_head structures"
list: Remove unnecessary WRITE_ONCE() from hlist_bl_add_before()
kernel-hacking: Make DEBUG_{LIST,PLIST,SG,NOTIFIERS} non-debug options
list: Add integrity checking to hlist implementation
list: Poison ->next pointer for non-RCU deletion of 'hlist_nulls_node'
list: Add integrity checking to hlist_nulls implementation
plist: Use CHECK_DATA_CORRUPTION instead of explicit {BUG,WARN}_ON()
list_bl: Use CHECK_DATA_CORRUPTION instead of custom BUG_ON() wrapper
list_bl: Extend integrity checking in deletion routines linux/bit_spinlock.h: Include linux/processor.h
list_bl: Move integrity checking out of line
list_bl: Extend integrity checking to cover the same cases as 'hlist'
list: Format CHECK_DATA_CORRUPTION error messages consistently
lkdtm: Extend list corruption checks

 arch/arm/configs/tegra_defconfig              |   2 +-
 arch/mips/configs/bigsur_defconfig            |   2 +-
 arch/powerpc/configs/ppc6xx_defconfig         |   4 +-
 arch/powerpc/configs/ps3_defconfig            |   2 +-
 arch/powerpc/configs/skiroot_defconfig        |   4 +-
 arch/riscv/configs/defconfig                  |   6 +-
 arch/riscv/configs/rv32_defconfig             |   6 +-
 arch/s390/configs/debug_defconfig             |   4 +-
 arch/sh/configs/polaris_defconfig             |   2 +-
 arch/sh/configs/rsk7203_defconfig             |   4 +-
 arch/sh/configs/se7206_defconfig              |   2 +-
 drivers/gpu/drm/radeon/mkregtable.c           |   2 +-
 drivers/misc/lkdtm/Makefile                   |   1 +
 drivers/misc/lkdtm/bugs.c                     |  68 ---
 drivers/misc/lkdtm/core.c                     |  31 +-
 drivers/misc/lkdtm/list.c                     | 489 ++++++++++++++++++
 drivers/misc/lkdtm/lkdtm.h                    |  33 +-
 drivers/staging/wfx/fwio.c                    |   2 +-
 drivers/staging/wfx/hwio.c                    |   2 +-
 include/linux/bit_spinlock.h                  |   1 +
 include/linux/list.h                          |  95 ++--
 include/linux/list_bl.h                       |  52 +-
 include/linux/list_nulls.h                    |  50 +-
 include/linux/llist.h                         |   2 +-
 include/linux/plist.h                         |   4 +-
 include/linux/rculist.h                       |  80 +--
 include/linux/rculist_bl.h                    |  17 +-
 include/linux/scatterlist.h                   |   6 +-
 include/linux/timer.h                         |   5 +-
 kernel/notifier.c                             |   2 +-
 kernel/time/timer.c                           |   1 +
 lib/Kconfig.debug                             |  24 +-
 lib/Makefile                                  |   2 +-
 lib/list_debug.c                              | 200 ++++++-
 lib/plist.c                                   |  67 ++-
 tools/include/linux/list.h                    |   4 +-
 tools/testing/selftests/lkdtm/tests.txt       |  31 +-
 .../selftests/wireguard/qemu/debug.config     |   6 +-
 tools/virtio/linux/scatterlist.h              |   4 +-
 39 files changed, 1034 insertions(+), 285 deletions(-)
 create mode 100644 drivers/misc/lkdtm/list.c
Signature · 1 line
2.20.1
#1 lore raw

RFC PATCH 1/21 list: Remove hlist_unhashed_lockless()

Commit c54a2744497d ("list: Add hlist_unhashed_lockless()") added a "lockless" variant of hlist_unhashed() that uses READ_ONCE() to access the 'pprev' pointer of the 'hlist_node', the intention being that this could be used by 'timer_pending()' to silence a KCSAN warning. As well as forgetting to add the caller, the patch also sprinkles {READ,WRITE}_ONCE() invocations over the standard (i.e. non-RCU) hlist code, which is undesirable for a number of reasons:

1. It gives the misleading impression that the non-RCU hlist code is in some way lock-free (despite the notable absence of any memory barriers!) and silences KCSAN in such cases.

2. It unnecessarily penalises code generation for non-RCU hlist users

3. It makes it difficult to introduce list integrity checks because of the possibility of concurrent callers.

Retain the {READ,WRITE}_ONCE() invocations for the RCU hlist code, but remove them from the non-RCU implementation. Remove the unused 'hlist_unhashed_lockless()' function entirely and add the READ_ONCE() to hlist_unhashed(), as we do already for hlist_empty() already.

Cc Eric Dumazet <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list.h | 33 ++++++++++-----------------------
 1 file changed, 10 insertions(+), 23 deletions(-)
include/linux/list.h +10 -23
index 884216db3246..4fed5a0f9b77 100644
@@ -777,19 +777,6 @@ static inline void INIT_HLIST_NODE(struct hlist_node *h)
  * node in unhashed state, but hlist_nulls_del() does not.
  */
 static inline int hlist_unhashed(const struct hlist_node *h)
-{
-	return !h->pprev;
-}
-
-/**
- * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
- * @h: Node to be checked
- *
- * This variant of hlist_unhashed() must be used in lockless contexts
- * to avoid potential load-tearing.  The READ_ONCE() is paired with the
- * various WRITE_ONCE() in hlist helpers that are defined below.
- */
-static inline int hlist_unhashed_lockless(const struct hlist_node *h)
 {
 	return !READ_ONCE(h->pprev);
 }
@@ -852,11 +839,11 @@ static inline void hlist_del_init(struct hlist_node *n)
 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 {
 	struct hlist_node *first = h->first;
-	WRITE_ONCE(n->next, first);
+	n->next = first;
 	if (first)
-		WRITE_ONCE(first->pprev, &n->next);
+		first->pprev = &n->next;
 	WRITE_ONCE(h->first, n);
-	WRITE_ONCE(n->pprev, &h->first);
+	n->pprev = &h->first;
 }
 
 /**
@@ -867,9 +854,9 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 static inline void hlist_add_before(struct hlist_node *n,
 				    struct hlist_node *next)
 {
-	WRITE_ONCE(n->pprev, next->pprev);
-	WRITE_ONCE(n->next, next);
-	WRITE_ONCE(next->pprev, &n->next);
+	n->pprev = next->pprev;
+	n->next = next;
+	next->pprev = &n->next;
 	WRITE_ONCE(*(n->pprev), n);
 }
 
@@ -881,12 +868,12 @@ static inline void hlist_add_before(struct hlist_node *n,
 static inline void hlist_add_behind(struct hlist_node *n,
 				    struct hlist_node *prev)
 {
-	WRITE_ONCE(n->next, prev->next);
-	WRITE_ONCE(prev->next, n);
-	WRITE_ONCE(n->pprev, &prev->next);
+	n->next = prev->next;
+	prev->next = n;
+	n->pprev = &prev->next;
 
 	if (n->next)
-		WRITE_ONCE(n->next->pprev, &n->next);
+		n->next->pprev  = &n->next;
 }
 
 /**
Signature · 1 line
2.20.1
maintainer Reviewed-by on v1 1/21
#2 lore raw

Re: [RFC PATCH 01/21] list: Remove hlist_unhashed_lockless()

Quoted 22 lines · Will Deacon

Commit c54a2744497d ("list: Add hlist_unhashed_lockless()") added a "lockless" variant of hlist_unhashed() that uses READ_ONCE() to access the 'pprev' pointer of the 'hlist_node', the intention being that this could be used by 'timer_pending()' to silence a KCSAN warning. As well as forgetting to add the caller, the patch also sprinkles {READ,WRITE}_ONCE() invocations over the standard (i.e. non-RCU) hlist code, which is undesirable for a number of reasons:

1. It gives the misleading impression that the non-RCU hlist code is in some way lock-free (despite the notable absence of any memory barriers!) and silences KCSAN in such cases.

2. It unnecessarily penalises code generation for non-RCU hlist users

3. It makes it difficult to introduce list integrity checks because of the possibility of concurrent callers.

Retain the {READ,WRITE}_ONCE() invocations for the RCU hlist code, but remove them from the non-RCU implementation. Remove the unused 'hlist_unhashed_lockless()' function entirely and add the READ_ONCE() to hlist_unhashed(), as we do already for hlist_empty() already.

Quoted 8 lines
Cc Eric Dumazet <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list.h | 33 ++++++++++-----------------------
 1 file changed, 10 insertions(+), 23 deletions(-)
maintainer Acked-by on v1 1/21
#3 lore raw

Re: [RFC PATCH 01/21] list: Remove hlist_unhashed_lockless()

In reply to Will Deacon
Quoted 22 lines · Will Deacon

Commit c54a2744497d ("list: Add hlist_unhashed_lockless()") added a "lockless" variant of hlist_unhashed() that uses READ_ONCE() to access the 'pprev' pointer of the 'hlist_node', the intention being that this could be used by 'timer_pending()' to silence a KCSAN warning. As well as forgetting to add the caller, the patch also sprinkles {READ,WRITE}_ONCE() invocations over the standard (i.e. non-RCU) hlist code, which is undesirable for a number of reasons:

1. It gives the misleading impression that the non-RCU hlist code is in some way lock-free (despite the notable absence of any memory barriers!) and silences KCSAN in such cases.

2. It unnecessarily penalises code generation for non-RCU hlist users

3. It makes it difficult to introduce list integrity checks because of the possibility of concurrent callers.

Retain the {READ,WRITE}_ONCE() invocations for the RCU hlist code, but remove them from the non-RCU implementation. Remove the unused 'hlist_unhashed_lockless()' function entirely and add the READ_ONCE() to hlist_unhashed(), as we do already for hlist_empty() already.

Quoted 5 lines
Cc Eric Dumazet <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

No objection, however 90c018942c2b ("timer: Use hlist_unhashed_lockless() in timer_pending()") in -tip must change from hlist_unhashed_lockless() to hlist_unhashed(). Easy fix, though, so:

Quoted 76 lines
---
 include/linux/list.h | 33 ++++++++++-----------------------
 1 file changed, 10 insertions(+), 23 deletions(-)
include/linux/list.h +10 -23
index 884216db3246..4fed5a0f9b77 100644
@@ -777,19 +777,6 @@ static inline void INIT_HLIST_NODE(struct hlist_node *h)
  * node in unhashed state, but hlist_nulls_del() does not.
  */
 static inline int hlist_unhashed(const struct hlist_node *h)
-{
-	return !h->pprev;
-}
-
-/**
- * hlist_unhashed_lockless - Version of hlist_unhashed for lockless use
- * @h: Node to be checked
- *
- * This variant of hlist_unhashed() must be used in lockless contexts
- * to avoid potential load-tearing.  The READ_ONCE() is paired with the
- * various WRITE_ONCE() in hlist helpers that are defined below.
- */
-static inline int hlist_unhashed_lockless(const struct hlist_node *h)
 {
 	return !READ_ONCE(h->pprev);
 }
@@ -852,11 +839,11 @@ static inline void hlist_del_init(struct hlist_node *n)
 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 {
 	struct hlist_node *first = h->first;
-	WRITE_ONCE(n->next, first);
+	n->next = first;
 	if (first)
-		WRITE_ONCE(first->pprev, &n->next);
+		first->pprev = &n->next;
 	WRITE_ONCE(h->first, n);
-	WRITE_ONCE(n->pprev, &h->first);
+	n->pprev = &h->first;
 }
 
 /**
@@ -867,9 +854,9 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 static inline void hlist_add_before(struct hlist_node *n,
 				    struct hlist_node *next)
 {
-	WRITE_ONCE(n->pprev, next->pprev);
-	WRITE_ONCE(n->next, next);
-	WRITE_ONCE(next->pprev, &n->next);
+	n->pprev = next->pprev;
+	n->next = next;
+	next->pprev = &n->next;
 	WRITE_ONCE(*(n->pprev), n);
 }
 
@@ -881,12 +868,12 @@ static inline void hlist_add_before(struct hlist_node *n,
 static inline void hlist_add_behind(struct hlist_node *n,
 				    struct hlist_node *prev)
 {
-	WRITE_ONCE(n->next, prev->next);
-	WRITE_ONCE(prev->next, n);
-	WRITE_ONCE(n->pprev, &prev->next);
+	n->next = prev->next;
+	prev->next = n;
+	n->pprev = &prev->next;
 
 	if (n->next)
-		WRITE_ONCE(n->next->pprev, &n->next);
+		n->next->pprev  = &n->next;
 }
 
 /**
Signature · 1 line
2.20.1
#4 lore raw

RFC PATCH 2/21 list: Remove hlist_nulls_unhashed_lockless()

In reply to Will Deacon

Commit 02b99b38f3d9 ("rcu: Add a hlist_nulls_unhashed_lockless() function") introduced the (as yet unused) hlist_nulls_unhashed_lockless() function to avoid KCSAN reports when an RCU reader checks the 'hashed' status of an 'hlist_nulls' concurrently undergoing modification.

Remove the unused function and add a READ_ONCE() to hlist_nulls_unhashed(), just like we do already for hlist_nulls_empty().

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list_nulls.h | 14 --------------
 1 file changed, 14 deletions(-)
include/linux/list_nulls.h +0 -14
index fa6e8471bd22..3a9ff01e9a11 100644
@@ -65,20 +65,6 @@ static inline unsigned long get_nulls_value(const struct hlist_nulls_node *ptr)
  * but hlist_nulls_del() does not.
  */
 static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h)
-{
-	return !h->pprev;
-}
-
-/**
- * hlist_nulls_unhashed_lockless - Has node been removed and reinitialized?
- * @h: Node to be checked
- *
- * Not that not all removal functions will leave a node in unhashed state.
- * For example, hlist_del_init_rcu() leaves the node in unhashed state,
- * but hlist_nulls_del() does not.  Unlike hlist_nulls_unhashed(), this
- * function may be used locklessly.
- */
-static inline int hlist_nulls_unhashed_lockless(const struct hlist_nulls_node *h)
 {
 	return !READ_ONCE(h->pprev);
 }
Signature · 1 line
2.20.1
Reviewed-by Greg Kroah-Hartman on v1 2/21
#5 lore raw

Re: [RFC PATCH 02/21] list: Remove hlist_nulls_unhashed_lockless()

Quoted 8 lines · Will Deacon

Commit 02b99b38f3d9 ("rcu: Add a hlist_nulls_unhashed_lockless() function") introduced the (as yet unused) hlist_nulls_unhashed_lockless() function to avoid KCSAN reports when an RCU reader checks the 'hashed' status of an 'hlist_nulls' concurrently undergoing modification.

Remove the unused function and add a READ_ONCE() to hlist_nulls_unhashed(), just like we do already for hlist_nulls_empty().

Quoted 6 lines
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list_nulls.h | 14 --------------
 1 file changed, 14 deletions(-)
maintainer Acked-by on v1 2/21
#6 lore raw

Re: [RFC PATCH 02/21] list: Remove hlist_nulls_unhashed_lockless()

In reply to Will Deacon
Quoted 11 lines · Will Deacon

Commit 02b99b38f3d9 ("rcu: Add a hlist_nulls_unhashed_lockless() function") introduced the (as yet unused) hlist_nulls_unhashed_lockless() function to avoid KCSAN reports when an RCU reader checks the 'hashed' status of an 'hlist_nulls' concurrently undergoing modification.

Remove the unused function and add a READ_ONCE() to hlist_nulls_unhashed(), just like we do already for hlist_nulls_empty().

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

Well, I guess that the added docbook comment might be seen as worthwhile.

Quoted 32 lines
---
 include/linux/list_nulls.h | 14 --------------
 1 file changed, 14 deletions(-)
include/linux/list_nulls.h +0 -14
index fa6e8471bd22..3a9ff01e9a11 100644
@@ -65,20 +65,6 @@ static inline unsigned long get_nulls_value(const struct hlist_nulls_node *ptr)
  * but hlist_nulls_del() does not.
  */
 static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h)
-{
-	return !h->pprev;
-}
-
-/**
- * hlist_nulls_unhashed_lockless - Has node been removed and reinitialized?
- * @h: Node to be checked
- *
- * Not that not all removal functions will leave a node in unhashed state.
- * For example, hlist_del_init_rcu() leaves the node in unhashed state,
- * but hlist_nulls_del() does not.  Unlike hlist_nulls_unhashed(), this
- * function may be used locklessly.
- */
-static inline int hlist_nulls_unhashed_lockless(const struct hlist_nulls_node *h)
 {
 	return !READ_ONCE(h->pprev);
 }
Signature · 1 line
2.20.1
#7 lore raw

RFC PATCH 3/21 list: Annotate lockless list primitives with data_race()

In reply to Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Marco Elver <[email protected]>
---
 include/linux/list.h       | 10 +++++-----
 include/linux/list_bl.h    |  5 +++--
 include/linux/list_nulls.h |  6 +++---
 include/linux/llist.h      |  2 +-
 4 files changed, 12 insertions(+), 11 deletions(-)
include/linux/list.h +5 -5
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-	return READ_ONCE(head->next) == head;
+	return data_race(READ_ONCE(head->next) == head);
 }
 
 /**
@@ -524,7 +524,7 @@ static inline void list_splice_tail_init(struct list_head *list,
  */
 #define list_first_entry_or_null(ptr, type, member) ({ \
 	struct list_head *head__ = (ptr); \
-	struct list_head *pos__ = READ_ONCE(head__->next); \
+	struct list_head *pos__ = data_race(READ_ONCE(head__->next)); \
 	pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
 })
 
@@ -772,13 +772,13 @@ static inline void INIT_HLIST_NODE(struct hlist_node *h)
  * hlist_unhashed - Has node been removed from list and reinitialized?
  * @h: Node to be checked
  *
- * Not that not all removal functions will leave a node in unhashed
+ * Note that not all removal functions will leave a node in unhashed
  * state.  For example, hlist_nulls_del_init_rcu() does leave the
  * node in unhashed state, but hlist_nulls_del() does not.
  */
 static inline int hlist_unhashed(const struct hlist_node *h)
 {
-	return !READ_ONCE(h->pprev);
+	return data_race(!READ_ONCE(h->pprev));
 }
 
 /**
@@ -787,7 +787,7 @@ static inline int hlist_unhashed(const struct hlist_node *h)
  */
 static inline int hlist_empty(const struct hlist_head *h)
 {
-	return !READ_ONCE(h->first);
+	return data_race(!READ_ONCE(h->first));
 }
 
 static inline void __hlist_del(struct hlist_node *n)
include/linux/list_bl.h +3 -2
index ae1b541446c9..1804fdb84dda 100644
@@ -51,7 +51,7 @@ static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
 
 static inline bool  hlist_bl_unhashed(const struct hlist_bl_node *h)
 {
-	return !h->pprev;
+	return data_race(!READ_ONCE(h->pprev));
 }
 
 static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
@@ -71,7 +71,8 @@ static inline void hlist_bl_set_first(struct hlist_bl_head *h,
 
 static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
 {
-	return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
+	unsigned long first = data_race((unsigned long)READ_ONCE(h->first));
+	return !(first & ~LIST_BL_LOCKMASK);
 }
 
 static inline void hlist_bl_add_head(struct hlist_bl_node *n,
include/linux/list_nulls.h +3 -3
index 3a9ff01e9a11..fa51a801bf32 100644
@@ -60,18 +60,18 @@ static inline unsigned long get_nulls_value(const struct hlist_nulls_node *ptr)
  * hlist_nulls_unhashed - Has node been removed and reinitialized?
  * @h: Node to be checked
  *
- * Not that not all removal functions will leave a node in unhashed state.
+ * Note that not all removal functions will leave a node in unhashed state.
  * For example, hlist_del_init_rcu() leaves the node in unhashed state,
  * but hlist_nulls_del() does not.
  */
 static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h)
 {
-	return !READ_ONCE(h->pprev);
+	return data_race(!READ_ONCE(h->pprev));
 }
 
 static inline int hlist_nulls_empty(const struct hlist_nulls_head *h)
 {
-	return is_a_nulls(READ_ONCE(h->first));
+	return data_race(is_a_nulls(READ_ONCE(h->first)));
 }
 
 static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
include/linux/llist.h +1 -1
index 2e9c7215882b..c7f042b73899 100644
@@ -186,7 +186,7 @@ static inline void init_llist_head(struct llist_head *list)
  */
 static inline bool llist_empty(const struct llist_head *head)
 {
-	return READ_ONCE(head->first) == NULL;
+	return data_race(READ_ONCE(head->first) == NULL);
 }
 
 static inline struct llist_node *llist_next(struct llist_node *node)
Signature · 1 line
2.20.1
#8 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 11 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

[...]

Quoted 5 lines

static inline int list_empty(const struct list_head *head) {

include/linux/list.h +1 -1
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);
 }

[...]

include/linux/list.h static inline void INIT_HLIST_NODE(struct hlist_node *h) · line 782

Quoted 5 lines

static inline int hlist_unhashed(const struct hlist_node *h) {

include/linux/list.h +1 -1
-       return !READ_ONCE(h->pprev);
+       return data_race(!READ_ONCE(h->pprev));
 }

This is probably valid in practice for hlist_unhashed(), which compares with NULL, as long as the most significant byte of all kernel pointers is non-zero; but I think list_empty() could realistically return false positives in the presence of a concurrent tearing store? This could break the following code pattern:

/* optimistic lockless check */
if (!list_empty(&some_list)) {
/* slowpath */
mutex_lock(&some_mutex);

  list_for_each(tmp, &some_list) {
    ...

}
mutex_unlock(&some_mutex);
}

(I'm not sure whether patterns like this appear commonly though.)

#9 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 35 lines · Jann Horn
Quoted 11 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

[...]

Quoted 5 lines

static inline int list_empty(const struct list_head *head) {

include/linux/list.h +1 -1
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);
 }

[...]

include/linux/list.h static inline void INIT_HLIST_NODE(struct hlist_node *h) · line 782

Quoted 5 lines

static inline int hlist_unhashed(const struct hlist_node *h) {

include/linux/list.h +1 -1
-       return !READ_ONCE(h->pprev);
+       return data_race(!READ_ONCE(h->pprev));
 }

This is probably valid in practice for hlist_unhashed(), which compares with NULL, as long as the most significant byte of all kernel pointers is non-zero; but I think list_empty() could realistically return false positives in the presence of a concurrent tearing store? This could break the following code pattern:

/* optimistic lockless check */
if (!list_empty(&some_list)) {
/* slowpath */
mutex_lock(&some_mutex);

Quoted 7 lines
  list_for_each(tmp, &some_list) {
    ...

}
mutex_unlock(&some_mutex);
}

(I'm not sure whether patterns like this appear commonly though.)

I would hope not as the list could go "empty" before the lock is grabbed. That pattern would be wrong.

thanks,

greg k-h

#10 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 42 lines · Greg KH
Quoted 41 lines · Jann Horn
Quoted 11 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

[...]

Quoted 5 lines

static inline int list_empty(const struct list_head *head) {

include/linux/list.h +1 -1
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);
 }

[...]

include/linux/list.h static inline void INIT_HLIST_NODE(struct hlist_node *h) · line 782

Quoted 5 lines

static inline int hlist_unhashed(const struct hlist_node *h) {

include/linux/list.h +1 -1
-       return !READ_ONCE(h->pprev);
+       return data_race(!READ_ONCE(h->pprev));
 }

This is probably valid in practice for hlist_unhashed(), which compares with NULL, as long as the most significant byte of all kernel pointers is non-zero; but I think list_empty() could realistically return false positives in the presence of a concurrent tearing store? This could break the following code pattern:

/* optimistic lockless check */
if (!list_empty(&some_list)) {
/* slowpath */
mutex_lock(&some_mutex);

  list_for_each(tmp, &some_list) {
    ...

}
mutex_unlock(&some_mutex);
}

Quoted 5 lines
Quoted 1 line

(I'm not sure whether patterns like this appear commonly though.)

I would hope not as the list could go "empty" before the lock is grabbed. That pattern would be wrong.

If the list becomes empty in between, the loop just iterates over nothing, and the effect is no different from what you'd get if you had bailed out before. But sure, you have to be aware that that can happen.

#11 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 46 lines · Jann Horn
Quoted 45 lines · Greg KH
Quoted 42 lines · Jann Horn
Quoted 11 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

[...]

Quoted 5 lines

static inline int list_empty(const struct list_head *head) {

include/linux/list.h +1 -1
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);
 }

[...]

include/linux/list.h static inline void INIT_HLIST_NODE(struct hlist_node *h) · line 782

Quoted 5 lines

static inline int hlist_unhashed(const struct hlist_node *h) {

include/linux/list.h +1 -1
-       return !READ_ONCE(h->pprev);
+       return data_race(!READ_ONCE(h->pprev));
 }

This is probably valid in practice for hlist_unhashed(), which compares with NULL, as long as the most significant byte of all kernel pointers is non-zero; but I think list_empty() could realistically return false positives in the presence of a concurrent tearing store? This could break the following code pattern:

/* optimistic lockless check */
if (!list_empty(&some_list)) {
/* slowpath */
mutex_lock(&some_mutex);

  list_for_each(tmp, &some_list) {
    ...

}
mutex_unlock(&some_mutex);
}

(I'm not sure whether patterns like this appear commonly though.)

Quoted 7 lines
Quoted 2 lines

I would hope not as the list could go "empty" before the lock is grabbed. That pattern would be wrong.

If the list becomes empty in between, the loop just iterates over nothing, and the effect is no different from what you'd get if you had bailed out before. But sure, you have to be aware that that can happen.

Doh, yeah, so it is safe, crazy, but safe :)

#12 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 50 lines · Greg KH
Quoted 49 lines · Jann Horn
Quoted 47 lines · Greg KH
Quoted 35 lines · Jann Horn
Quoted 11 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

[...]

Quoted 5 lines

static inline int list_empty(const struct list_head *head) {

include/linux/list.h +1 -1
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);
 }

[...]

include/linux/list.h static inline void INIT_HLIST_NODE(struct hlist_node *h) · line 782

Quoted 5 lines

static inline int hlist_unhashed(const struct hlist_node *h) {

include/linux/list.h +1 -1
-       return !READ_ONCE(h->pprev);
+       return data_race(!READ_ONCE(h->pprev));
 }

This is probably valid in practice for hlist_unhashed(), which compares with NULL, as long as the most significant byte of all kernel pointers is non-zero; but I think list_empty() could realistically return false positives in the presence of a concurrent tearing store? This could break the following code pattern:

/* optimistic lockless check */
if (!list_empty(&some_list)) {
/* slowpath */
mutex_lock(&some_mutex);

Quoted 7 lines
  list_for_each(tmp, &some_list) {
    ...

}
mutex_unlock(&some_mutex);
}

(I'm not sure whether patterns like this appear commonly though.)

I would hope not as the list could go "empty" before the lock is grabbed. That pattern would be wrong.

Quoted 6 lines
Quoted 4 lines

If the list becomes empty in between, the loop just iterates over nothing, and the effect is no different from what you'd get if you had bailed out before. But sure, you have to be aware that that can happen.

Doh, yeah, so it is safe, crazy, but safe :)

Here's an example of that pattern, I think (which I think is technically incorrect if what peterz said is accurate?):

/**
* waitqueue_active -- locklessly test for waiters on the queue
* @wq_head: the waitqueue to test for waiters
*
* returns true if the wait list is not empty
*
* NOTE: this function is lockless and requires care, incorrect usage _will_
* lead to sporadic and non-obvious failure.
*
* Use either while holding wait_queue_head::lock or when used for wakeups
* with an extra smp_mb() like::
*
* CPU0 - waker CPU1 - waiter
*
* for (;;) {
* @cond = true; prepare_to_wait(&wq_head,
&wait, state);
* smp_mb(); // smp_mb() from set_current_state()
* if (waitqueue_active(wq_head)) if (@cond)
* wake_up(wq_head); break;
* schedule();
* }
* finish_wait(&wq_head, &wait);
*
* Because without the explicit smp_mb() it's possible for the
* waitqueue_active() load to get hoisted over the @cond store such that we'll
* observe an empty wait list while the waiter might not observe @cond. *
* Also note that this 'optimization' trades a spin_lock() for an smp_mb(),
* which (when the lock is uncontended) are of roughly equal cost. */
static inline int waitqueue_active(struct wait_queue_head *wq_head)

{
        return !list_empty(&wq_head->head);
}

void signalfd_cleanup(struct sighand_struct *sighand)

{
        wait_queue_head_t *wqh = &sighand->signalfd_wqh;
        /*
         * The lockless check can race with remove_wait_queue() in progress,
         * but in this case its caller should run under rcu_read_lock() and
         * sighand_cachep is SLAB_TYPESAFE_BY_RCU, we can safely return.
         */
        if (likely(!waitqueue_active(wqh)))
                return;

        /* wait_queue_entry_t->func(POLLFREE) should do remove_wait_queue() */
        wake_up_poll(wqh, EPOLLHUP | POLLFREE);
}

and __add_wait_queue() just uses plain list_add(&wq_entry->entry, &wq_head->head) under a lock.

#13 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

In reply to Will Deacon
Quoted 29 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Marco Elver <[email protected]>
---
 include/linux/list.h       | 10 +++++-----
 include/linux/list_bl.h    |  5 +++--
 include/linux/list_nulls.h |  6 +++---
 include/linux/llist.h      |  2 +-
 4 files changed, 12 insertions(+), 11 deletions(-)
include/linux/list.h +0 -0
index 4fed5a0f9b77..4d9f5f9ed1a8 100644

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 282

Quoted 5 lines
include/linux/list.h +1 -1
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);

Double-marking should never be necessary, at least if you want to make KCSAN happy. From what I gather there is an unmarked write somewhere, correct? In that case, KCSAN will still complain because if it sees a race between this read and the other write, then at least one is still plain (the write).

Then, my suggestion would be to mark the write with data_race() and just leave this as a READ_ONCE(). Having a data_race() somewhere only makes KCSAN stop reporting the race if the paired access is also marked (be it with data_race() or _ONCE, etc.).

Alternatively, if marking the write is impossible, you can surround the access with kcsan_disable_current()/kcsan_enable_current(). Or, as a last resort, just leaving as-is is fine too, because KCSAN's default config (still) has KCSAN_ASSUME_PLAIN_WRITES_ATOMIC selected.

Thanks,
-- Marco

Quoted 102 lines
include/linux/list.h +4 -4
 }
 
 /**
@@ -524,7 +524,7 @@ static inline void list_splice_tail_init(struct list_head *list,
  */
 #define list_first_entry_or_null(ptr, type, member) ({ \
        struct list_head *head__ = (ptr); \
-       struct list_head *pos__ = READ_ONCE(head__->next); \
+       struct list_head *pos__ = data_race(READ_ONCE(head__->next)); \
        pos__ != head__ ? list_entry(pos__, type, member) : NULL; \
 })
 
@@ -772,13 +772,13 @@ static inline void INIT_HLIST_NODE(struct hlist_node *h)
  * hlist_unhashed - Has node been removed from list and reinitialized?
  * @h: Node to be checked
  *
- * Not that not all removal functions will leave a node in unhashed
+ * Note that not all removal functions will leave a node in unhashed
  * state.  For example, hlist_nulls_del_init_rcu() does leave the
  * node in unhashed state, but hlist_nulls_del() does not.
  */
 static inline int hlist_unhashed(const struct hlist_node *h)
 {
-       return !READ_ONCE(h->pprev);
+       return data_race(!READ_ONCE(h->pprev));
 }
 
 /**
@@ -787,7 +787,7 @@ static inline int hlist_unhashed(const struct hlist_node *h)
  */
 static inline int hlist_empty(const struct hlist_head *h)
 {
-       return !READ_ONCE(h->first);
+       return data_race(!READ_ONCE(h->first));
 }
 
 static inline void __hlist_del(struct hlist_node *n)
include/linux/list_bl.h +3 -2
index ae1b541446c9..1804fdb84dda 100644
@@ -51,7 +51,7 @@ static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h)
 
 static inline bool  hlist_bl_unhashed(const struct hlist_bl_node *h)
 {
-       return !h->pprev;
+       return data_race(!READ_ONCE(h->pprev));
 }
 
 static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
@@ -71,7 +71,8 @@ static inline void hlist_bl_set_first(struct hlist_bl_head *h,
 
 static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
 {
-       return !((unsigned long)READ_ONCE(h->first) & ~LIST_BL_LOCKMASK);
+       unsigned long first = data_race((unsigned long)READ_ONCE(h->first));
+       return !(first & ~LIST_BL_LOCKMASK);
 }
 
 static inline void hlist_bl_add_head(struct hlist_bl_node *n,
include/linux/list_nulls.h +3 -3
index 3a9ff01e9a11..fa51a801bf32 100644
@@ -60,18 +60,18 @@ static inline unsigned long get_nulls_value(const struct hlist_nulls_node *ptr)
  * hlist_nulls_unhashed - Has node been removed and reinitialized?
  * @h: Node to be checked
  *
- * Not that not all removal functions will leave a node in unhashed state.
+ * Note that not all removal functions will leave a node in unhashed state.
  * For example, hlist_del_init_rcu() leaves the node in unhashed state,
  * but hlist_nulls_del() does not.
  */
 static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h)
 {
-       return !READ_ONCE(h->pprev);
+       return data_race(!READ_ONCE(h->pprev));
 }
 
 static inline int hlist_nulls_empty(const struct hlist_nulls_head *h)
 {
-       return is_a_nulls(READ_ONCE(h->first));
+       return data_race(is_a_nulls(READ_ONCE(h->first)));
 }
 
 static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
include/linux/llist.h +1 -2
index 2e9c7215882b..c7f042b73899 100644
@@ -186,7 +186,7 @@ static inline void init_llist_head(struct llist_head *list)
  */
 static inline bool llist_empty(const struct llist_head *head)
 {
-       return READ_ONCE(head->first) == NULL;
+       return data_race(READ_ONCE(head->first) == NULL);
 }
 
 static inline struct llist_node *llist_next(struct llist_node *node)
--

2.20.1

#14 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 47 lines · Marco Elver
Quoted 29 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Marco Elver <[email protected]>
---
 include/linux/list.h       | 10 +++++-----
 include/linux/list_bl.h    |  5 +++--
 include/linux/list_nulls.h |  6 +++---
 include/linux/llist.h      |  2 +-
 4 files changed, 12 insertions(+), 11 deletions(-)
include/linux/list.h +0 -0
index 4fed5a0f9b77..4d9f5f9ed1a8 100644

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 282

Quoted 5 lines
include/linux/list.h +1 -1
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);

Double-marking should never be necessary, at least if you want to make KCSAN happy. From what I gather there is an unmarked write somewhere, correct? In that case, KCSAN will still complain because if it sees a race between this read and the other write, then at least one is still plain (the write).

Then, my suggestion would be to mark the write with data_race() and just leave this as a READ_ONCE(). Having a data_race() somewhere only makes KCSAN stop reporting the race if the paired access is also marked (be it with data_race() or _ONCE, etc.).

Quoted 4 lines

Alternatively, if marking the write is impossible, you can surround the access with kcsan_disable_current()/kcsan_enable_current(). Or, as a last resort, just leaving as-is is fine too, because KCSAN's default config (still) has KCSAN_ASSUME_PLAIN_WRITES_ATOMIC selected.

Right, it looks like this is a bit of a smoking gun and we need to decide on whether list_empty() is actually usable without synchronisation first. Based on the outcome of that discussion, I'll update this patch accordingly.

The main thing I want to avoid is marking parts of the non-RCU list implementation with data_race() or {READ,WRITE}_ONCE() because that's a sure-fire way to hide real bugs.

Cheers,

Will

#15 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

In reply to Marco Elver
Quoted 24 lines · Marco Elver
Quoted 23 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Marco Elver <[email protected]>
---
 include/linux/list.h       | 10 +++++-----
 include/linux/list_bl.h    |  5 +++--
 include/linux/list_nulls.h |  6 +++---
 include/linux/llist.h      |  2 +-
 4 files changed, 12 insertions(+), 11 deletions(-)
Quoted 16 lines

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 282

Quoted 10 lines
include/linux/list.h +1 -1
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);

Double-marking should never be necessary, at least if you want to make KCSAN happy. From what I gather there is an unmarked write somewhere, correct? In that case, KCSAN will still complain because if it sees a race between this read and the other write, then at least one is still plain (the write).

Ok, then I should drop the data_race() annotation and stick to READ_ONCE(), I think (but see below).

Quoted 4 lines

Then, my suggestion would be to mark the write with data_race() and just leave this as a READ_ONCE(). Having a data_race() somewhere only makes KCSAN stop reporting the race if the paired access is also marked (be it with data_race() or _ONCE, etc.).

The problem with taking that approach is that it ends up much of the list implementation annotated with either WRITE_ONCE() or data_race(), meaning that concurrent, racy list operations will no longer be reported by KCSAN. I think that's a pretty big deal and I'm strongly against annotating the internals of library code such as this because it means that buggy callers will largely go undetected.

The situation we have here is that some calls, e.g. hlist_empty() are safe even in the presence of a racy write and I'd like to suppress KCSAN reports without annotating the writes at all.

Quoted 4 lines

Alternatively, if marking the write is impossible, you can surround the access with kcsan_disable_current()/kcsan_enable_current(). Or, as a last resort, just leaving as-is is fine too, because KCSAN's default config (still) has KCSAN_ASSUME_PLAIN_WRITES_ATOMIC selected.

Hmm, I suppose some bright spark will want to change the default at the some point though, no? ;) I'll look at using kcsan_disable_current()/kcsan_enable_current(), thanks.

Will

#16 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 62 lines · Will Deacon
Quoted 24 lines · Marco Elver
Quoted 23 lines · Will Deacon

Some list predicates can be used locklessly even with the non-RCU list implementations, since they effectively boil down to a test against NULL. For example, checking whether or not a list is empty is safe even in the presence of a concurrent, tearing write to the list head pointer. Similarly, checking whether or not an hlist node has been hashed is safe as well.

Annotate these lockless list predicates with data_race() and READ_ONCE() so that KCSAN and the compiler are aware of what's going on. The writer side can then avoid having to use WRITE_ONCE() in the non-RCU implementation.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Marco Elver <[email protected]>
---
 include/linux/list.h       | 10 +++++-----
 include/linux/list_bl.h    |  5 +++--
 include/linux/list_nulls.h |  6 +++---
 include/linux/llist.h      |  2 +-
 4 files changed, 12 insertions(+), 11 deletions(-)
Quoted 16 lines

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 282

Quoted 10 lines
include/linux/list.h +1 -1
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-       return READ_ONCE(head->next) == head;
+       return data_race(READ_ONCE(head->next) == head);

Double-marking should never be necessary, at least if you want to make KCSAN happy. From what I gather there is an unmarked write somewhere, correct? In that case, KCSAN will still complain because if it sees a race between this read and the other write, then at least one is still plain (the write).

Ok, then I should drop the data_race() annotation and stick to READ_ONCE(), I think (but see below).

Quoted 4 lines

Then, my suggestion would be to mark the write with data_race() and just leave this as a READ_ONCE(). Having a data_race() somewhere only makes KCSAN stop reporting the race if the paired access is also marked (be it with data_race() or _ONCE, etc.).

The problem with taking that approach is that it ends up much of the list implementation annotated with either WRITE_ONCE() or data_race(), meaning that concurrent, racy list operations will no longer be reported by KCSAN. I think that's a pretty big deal and I'm strongly against annotating the internals of library code such as this because it means that buggy callers will largely go undetected.

The situation we have here is that some calls, e.g. hlist_empty() are safe even in the presence of a racy write and I'd like to suppress KCSAN reports without annotating the writes at all.

Quoted 8 lines
Quoted 4 lines

Alternatively, if marking the write is impossible, you can surround the access with kcsan_disable_current()/kcsan_enable_current(). Or, as a last resort, just leaving as-is is fine too, because KCSAN's default config (still) has KCSAN_ASSUME_PLAIN_WRITES_ATOMIC selected.

Hmm, I suppose some bright spark will want to change the default at the some point though, no? ;) I'll look at using kcsan_disable_current()/kcsan_enable_current(), thanks.

I think this will come up again (it did already come up in some other patch I reviewed, and Paul also mentioned it), so it seems best to change data_race() to match the intuitive semantics of just completely ignoring the access marked with it. I.e. marking accesses racing with accesses marked with data_race() is now optional:
https://lkml.kernel.org/r/[email protected]

In which case, the original patch you had here works just fine.

Thanks,
-- Marco

#17 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 27 lines · Marco Elver
Quoted 17 lines · Will Deacon
Quoted 4 lines · Marco Elver

Then, my suggestion would be to mark the write with data_race() and just leave this as a READ_ONCE(). Having a data_race() somewhere only makes KCSAN stop reporting the race if the paired access is also marked (be it with data_race() or _ONCE, etc.).

The problem with taking that approach is that it ends up much of the list implementation annotated with either WRITE_ONCE() or data_race(), meaning that concurrent, racy list operations will no longer be reported by KCSAN. I think that's a pretty big deal and I'm strongly against annotating the internals of library code such as this because it means that buggy callers will largely go undetected.

The situation we have here is that some calls, e.g. hlist_empty() are safe even in the presence of a racy write and I'd like to suppress KCSAN reports without annotating the writes at all.

Quoted 8 lines
Quoted 4 lines

Alternatively, if marking the write is impossible, you can surround the access with kcsan_disable_current()/kcsan_enable_current(). Or, as a last resort, just leaving as-is is fine too, because KCSAN's default config (still) has KCSAN_ASSUME_PLAIN_WRITES_ATOMIC selected.

Hmm, I suppose some bright spark will want to change the default at the some point though, no? ;) I'll look at using kcsan_disable_current()/kcsan_enable_current(), thanks.

Quoted 6 lines

I think this will come up again (it did already come up in some other patch I reviewed, and Paul also mentioned it), so it seems best to change data_race() to match the intuitive semantics of just completely ignoring the access marked with it. I.e. marking accesses racing with accesses marked with data_race() is now optional:
https://lkml.kernel.org/r/[email protected]

/me goes look. Thanks!

Quoted 1 line

In which case, the original patch you had here works just fine.

Ah yes, so now data_race(READ_ONCE(...)) does make sense as a combination. It's tempting to wrap that up as an accessor, but actually forcing people to spell it out might not be a bad thing after all.

Will

merge bot Applied
#18 lore raw

[tip: locking/kcsan] kcsan: Change data_race() to no longer require marking racing accesses

In reply to Will Deacon
The following commit has been merged into the locking/kcsan branch of tip:

The following commit has been merged into the locking/kcsan branch of tip:

Commit-ID:     d071e91361bbfef524ae8abf7e560fb294d0ad64
Gitweb:        https://git.kernel.org/tip/d071e91361bbfef524ae8abf7e560fb294d0ad64
Author:        Marco Elver <[email protected]>
AuthorDate:    Tue, 31 Mar 2020 21:32:33 +02:00
Committer:     Paul E. McKenney <[email protected]>
CommitterDate: Mon, 13 Apr 2020 17:18:15 -07:00

kcsan: Change data_race() to no longer require marking racing accesses

Thus far, accesses marked with data_race() would still require the racing access to be marked in some way (be it with READ_ONCE(), WRITE_ONCE(), or data_race() itself), as otherwise KCSAN would still report a data race. This requirement, however, seems to be unintuitive, and some valid use-cases demand *not* marking other accesses, as it might hide more serious bugs (e.g. diagnostic reads).

Therefore, this commit changes data_race() to no longer require marking racing accesses (although it's still recommended if possible).

The alternative would have been introducing another variant of data_race(), however, since usage of data_race() already needs to be carefully reasoned about, distinguishing between these cases likely adds more complexity in the wrong place.

---
 include/linux/compiler.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/compiler.h +2 -2
index f504ede..1729bd1 100644
@@ -326,9 +326,9 @@ unsigned long read_word_at_a_time(const void *addr)
 #define data_race(expr)                                                        \
 	({                                                                     \
 		typeof(({ expr; })) __val;                                     \
-		kcsan_nestable_atomic_begin();                                 \
+		kcsan_disable_current();                                       \
 		__val = ({ expr; });                                           \
-		kcsan_nestable_atomic_end();                                   \
+		kcsan_enable_current();                                        \
 		__val;                                                         \
 	})
 #else
#19 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

In reply to Will Deacon

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 283

Quoted 11 lines · Will Deacon
include/linux/list.h +1 -1
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-	return READ_ONCE(head->next) == head;
+	return data_race(READ_ONCE(head->next) == head);
 }

list_empty() isn't lockless safe, that's what we have list_empty_careful() for.

#20 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 15 lines · Peter Zijlstra

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 283

Quoted 11 lines · Will Deacon
include/linux/list.h +1 -1
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-     return READ_ONCE(head->next) == head;
+     return data_race(READ_ONCE(head->next) == head);
 }

list_empty() isn't lockless safe, that's what we have list_empty_careful() for.

That thing looks like it could also use some READ_ONCE() sprinkled in...

#21 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

[mutt crashed while I was sending this; apologies if you receive it twice]

Quoted 17 lines · Jann Horn
Quoted 15 lines · Peter Zijlstra

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 283

Quoted 11 lines · Will Deacon
include/linux/list.h +1 -1
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-     return READ_ONCE(head->next) == head;
+     return data_race(READ_ONCE(head->next) == head);
 }

list_empty() isn't lockless safe, that's what we have list_empty_careful() for.

Quoted 1 line

That thing looks like it could also use some READ_ONCE() sprinkled in...

Crikey, how did I miss that? I need to spend some time understanding the ordering there.

So it sounds like the KCSAN splats relating to list_empty() and loosely referred to by 1c97be677f72 ("list: Use WRITE_ONCE() when adding to lists and hlists") are indicative of real bugs and we should actually restore list_empty() to its former glory prior to 1658d35ead5d ("list: Use READ_ONCE() when testing for empty lists"). Alternatively, assuming list_empty_careful() does what it says on the tin, we could just make that the default.

Will

maintainer
#22 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 25 lines · Will Deacon

[mutt crashed while I was sending this; apologies if you receive it twice]

Quoted 17 lines · Jann Horn
Quoted 15 lines · Peter Zijlstra

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 283

Quoted 11 lines · Will Deacon
include/linux/list.h +1 -1
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-     return READ_ONCE(head->next) == head;
+     return data_race(READ_ONCE(head->next) == head);
 }

list_empty() isn't lockless safe, that's what we have list_empty_careful() for.

Quoted 1 line

That thing looks like it could also use some READ_ONCE() sprinkled in...

Crikey, how did I miss that? I need to spend some time understanding the ordering there.

Quoted 7 lines

So it sounds like the KCSAN splats relating to list_empty() and loosely referred to by 1c97be677f72 ("list: Use WRITE_ONCE() when adding to lists and hlists") are indicative of real bugs and we should actually restore list_empty() to its former glory prior to 1658d35ead5d ("list: Use READ_ONCE() when testing for empty lists"). Alternatively, assuming list_empty_careful() does what it says on the tin, we could just make that the default.

The list_empty_careful() function (suitably annotated) returns false if the list is non-empty, including when it is in the process of becoming either empty or non-empty. It would be fine for the lockless use cases I have come across.

Thanx, Paul

#23 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 34 lines · Paul E. McKenney
Quoted 25 lines · Will Deacon

[mutt crashed while I was sending this; apologies if you receive it twice]

Quoted 17 lines · Jann Horn
Quoted 15 lines · Peter Zijlstra

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 283

Quoted 11 lines · Will Deacon
include/linux/list.h +1 -1
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-     return READ_ONCE(head->next) == head;
+     return data_race(READ_ONCE(head->next) == head);
 }

list_empty() isn't lockless safe, that's what we have list_empty_careful() for.

Quoted 1 line

That thing looks like it could also use some READ_ONCE() sprinkled in...

Crikey, how did I miss that? I need to spend some time understanding the ordering there.

Quoted 7 lines

So it sounds like the KCSAN splats relating to list_empty() and loosely referred to by 1c97be677f72 ("list: Use WRITE_ONCE() when adding to lists and hlists") are indicative of real bugs and we should actually restore list_empty() to its former glory prior to 1658d35ead5d ("list: Use READ_ONCE() when testing for empty lists"). Alternatively, assuming list_empty_careful() does what it says on the tin, we could just make that the default.

Quoted 4 lines

The list_empty_careful() function (suitably annotated) returns false if the list is non-empty, including when it is in the process of becoming either empty or non-empty. It would be fine for the lockless use cases I have come across.

Hmm, I had a look at the implementation and I'm not at all convinced that it's correct. First of all, the comment above it states:

* NOTE: using list_empty_careful() without synchronization
* can only be safe if the only activity that can happen
* to the list entry is list_del_init(). Eg. it cannot be used
* if another CPU could re-list_add() it.

but it seems that people disregard this note and instead use it as a general-purpose lockless test, taking a lock and rechecking if it returns non-empty. It would also mean we'd have to keep the WRITE_ONCE() in INIT_LIST_HEAD, which is something that I've been trying to remove.

In the face of something like a concurrent list_add(); list_add_tail() sequence, then the tearing writes to the head->{prev,next} pointers could cause list_empty_careful() to indicate that the list is momentarily empty.

I've started looking at whether we can use a NULL next pointer to indicate an empty list, which might allow us to kill the __list_del_clearprev() hack at the same time, but I've not found enough time to really get my teeth into it yet.

Will

maintainer
#24 lore raw

Re: [RFC PATCH 03/21] list: Annotate lockless list primitives with data_race()

Quoted 40 lines · Will Deacon
Quoted 34 lines · Paul E. McKenney
Quoted 25 lines · Will Deacon

[mutt crashed while I was sending this; apologies if you receive it twice]

Quoted 17 lines · Jann Horn
Quoted 15 lines · Peter Zijlstra

include/linux/list.h static inline int list_is_last(const struct list_head *list, · line 283

Quoted 11 lines · Will Deacon
include/linux/list.h +1 -1
index 4fed5a0f9b77..4d9f5f9ed1a8 100644
@@ -279,7 +279,7 @@ static inline int list_is_last(const struct list_head *list,
  */
 static inline int list_empty(const struct list_head *head)
 {
-     return READ_ONCE(head->next) == head;
+     return data_race(READ_ONCE(head->next) == head);
 }

list_empty() isn't lockless safe, that's what we have list_empty_careful() for.

Quoted 1 line

That thing looks like it could also use some READ_ONCE() sprinkled in...

Crikey, how did I miss that? I need to spend some time understanding the ordering there.

Quoted 7 lines

So it sounds like the KCSAN splats relating to list_empty() and loosely referred to by 1c97be677f72 ("list: Use WRITE_ONCE() when adding to lists and hlists") are indicative of real bugs and we should actually restore list_empty() to its former glory prior to 1658d35ead5d ("list: Use READ_ONCE() when testing for empty lists"). Alternatively, assuming list_empty_careful() does what it says on the tin, we could just make that the default.

Quoted 4 lines

The list_empty_careful() function (suitably annotated) returns false if the list is non-empty, including when it is in the process of becoming either empty or non-empty. It would be fine for the lockless use cases I have come across.

Quoted 7 lines

Hmm, I had a look at the implementation and I'm not at all convinced that it's correct. First of all, the comment above it states:

* NOTE: using list_empty_careful() without synchronization
* can only be safe if the only activity that can happen
* to the list entry is list_del_init(). Eg. it cannot be used
* if another CPU could re-list_add() it.

Huh. This thing is unchanged since 2.6.12-rc2, back in 2005:

static inline int list_empty_careful(const struct list_head *head)

{
	struct list_head *next = head->next;
	return (next == head) && (next == head->prev);
}

I can imagine compiler value-caching optimizations that would cause trouble, for example, if a previous obsolete fetch from head->prev was lying around in a register, causing this function to say "not empty" when it was in fact empty. Of course, if obsolete values for both head->next and head->prev were lying around, pretty much anything could happen.

Quoted 5 lines

but it seems that people disregard this note and instead use it as a general-purpose lockless test, taking a lock and rechecking if it returns non-empty. It would also mean we'd have to keep the WRITE_ONCE() in INIT_LIST_HEAD, which is something that I've been trying to remove.

Quoted 8 lines

In the face of something like a concurrent list_add(); list_add_tail() sequence, then the tearing writes to the head->{prev,next} pointers could cause list_empty_careful() to indicate that the list is momentarily empty.

I've started looking at whether we can use a NULL next pointer to indicate an empty list, which might allow us to kill the __list_del_clearprev() hack at the same time, but I've not found enough time to really get my teeth into it yet.

In the delete-only case, I kind of get it, other than the potential for optimization. Once the list becomes empty, it will forever remain empty. And the additional test of head->prev avoids this returning true while the deletion is half done (again, aside from the potential for optimization).

If insertions are allowed, the thing I haven't quite figured out yet is what is being gained by the additional check of head->prev. After all, if updates are not excluded, the return value can become obsolete immediately anyhow. Yes, it could be used as a heuristic, but it could report empty immediately before a list_add(), so there would need to either be a careful wakeup protocol or a periodic poll of the list.

Or am I missing a trick here?

Thanx, Paul

#25 lore raw

RFC PATCH 4/21 timers: Use hlist_unhashed() instead of open-coding in timer_pending()

In reply to Will Deacon

timer_pending() open-codes a version of hlist_unhashed() to check whether or not the 'timer' parameter has been queued in the timer wheel. KCSAN detects this as a racy operation and explodes at us:

  | BUG: KCSAN: data-race in del_timer / detach_if_pending
  |
  | write to 0xffff88808697d870 of 8 bytes by task 10 on cpu 0:
  |  __hlist_del include/linux/list.h:764 [inline]
  |  detach_timer kernel/time/timer.c:815 [inline]
  |  detach_if_pending+0xcd/0x2d0 kernel/time/timer.c:832
  |  try_to_del_timer_sync+0x60/0xb0 kernel/time/timer.c:1226
  |  del_timer_sync+0x6b/0xa0 kernel/time/timer.c:1365
  |  schedule_timeout+0x2d2/0x6e0 kernel/time/timer.c:1896
  |  rcu_gp_fqs_loop+0x37c/0x580 kernel/rcu/tree.c:1639
  |  rcu_gp_kthread+0x143/0x230 kernel/rcu/tree.c:1799
  |  kthread+0x1d4/0x200 drivers/block/aoe/aoecmd.c:1253
  |  ret_from_fork+0x1f/0x30 arch/x86/entry/entry_64.S:352
  |
  | read to 0xffff88808697d870 of 8 bytes by task 12060 on cpu 1:
  |  del_timer+0x3b/0xb0 kernel/time/timer.c:1198
  |  sk_stop_timer+0x25/0x60 net/core/sock.c:2845
  |  inet_csk_clear_xmit_timers+0x69/0xa0 net/ipv4/inet_connection_sock.c:523
  |  tcp_clear_xmit_timers include/net/tcp.h:606 [inline]
  |  tcp_v4_destroy_sock+0xa3/0x3f0 net/ipv4/tcp_ipv4.c:2096
  |  inet_csk_destroy_sock+0xf4/0x250 net/ipv4/inet_connection_sock.c:836
  |  tcp_close+0x6f3/0x970 net/ipv4/tcp.c:2497
  |  inet_release+0x86/0x100 net/ipv4/af_inet.c:427
  |  __sock_release+0x85/0x160 net/socket.c:590
  |  sock_close+0x24/0x30 net/socket.c:1268
  |  __fput+0x1e1/0x520 fs/file_table.c:280
  |  ____fput+0x1f/0x30 fs/file_table.c:313
  |  task_work_run+0xf6/0x130 kernel/task_work.c:113
  |  tracehook_notify_resume include/linux/tracehook.h:188 [inline]
  |  exit_to_usermode_loop+0x2b4/0x2c0 arch/x86/entry/common.c:163

Replace the explicit 'pprev' pointer comparison in timer_pending() with a call to hlist_unhashed() and initialise the 'expires' timer field explicitly in do_init_timer() so that the compiler doesn't emit bogus 'maybe used uninitialised' warnings now that it cannot reason statically about the result of timer_pending().

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Eric Dumazet <[email protected]>
---
 include/linux/timer.h | 5 +++--
 kernel/time/timer.c   | 1 +
 2 files changed, 4 insertions(+), 2 deletions(-)
include/linux/timer.h +3 -2
index 1e6650ed066d..e9610d2988ba 100644
@@ -158,13 +158,14 @@ static inline void destroy_timer_on_stack(struct timer_list *timer) { }
  *
  * timer_pending will tell whether a given timer is currently pending,
  * or not. Callers must ensure serialization wrt. other operations done
- * to this timer, eg. interrupt contexts, or other CPUs on SMP.
+ * to this timer, eg. interrupt contexts, or other CPUs on SMP if they
+ * cannot tolerate spurious results.
  *
  * return value: 1 if the timer is pending, 0 if not.
  */
 static inline int timer_pending(const struct timer_list * timer)
 {
-	return timer->entry.pprev != NULL;
+	return !hlist_unhashed(&timer->entry);
 }
 
 extern void add_timer_on(struct timer_list *timer, int cpu);
kernel/time/timer.c +1 -0
index 4820823515e9..9e1c6fc8433a 100644
@@ -780,6 +780,7 @@ static void do_init_timer(struct timer_list *timer,
 			  const char *name, struct lock_class_key *key)
 {
 	timer->entry.pprev = NULL;
+	timer->expires = 0; /* Avoid bogus 'maybe used uninitialized' warning */
 	timer->function = func;
 	timer->flags = flags | raw_smp_processor_id();
 	lockdep_init_map(&timer->lockdep_map, name, key, 0);
Signature · 1 line
2.20.1
maintainer Reviewed-by on v1 4/21
#26 lore raw

Re: [RFC PATCH 04/21] timers: Use hlist_unhashed() instead of open-coding in timer_pending()

Quoted 41 lines · Will Deacon

timer_pending() open-codes a version of hlist_unhashed() to check whether or not the 'timer' parameter has been queued in the timer wheel. KCSAN detects this as a racy operation and explodes at us:

  | BUG: KCSAN: data-race in del_timer / detach_if_pending
  |
  | write to 0xffff88808697d870 of 8 bytes by task 10 on cpu 0:
  |  __hlist_del include/linux/list.h:764 [inline]
  |  detach_timer kernel/time/timer.c:815 [inline]
  |  detach_if_pending+0xcd/0x2d0 kernel/time/timer.c:832
  |  try_to_del_timer_sync+0x60/0xb0 kernel/time/timer.c:1226
  |  del_timer_sync+0x6b/0xa0 kernel/time/timer.c:1365
  |  schedule_timeout+0x2d2/0x6e0 kernel/time/timer.c:1896
  |  rcu_gp_fqs_loop+0x37c/0x580 kernel/rcu/tree.c:1639
  |  rcu_gp_kthread+0x143/0x230 kernel/rcu/tree.c:1799
  |  kthread+0x1d4/0x200 drivers/block/aoe/aoecmd.c:1253
  |  ret_from_fork+0x1f/0x30 arch/x86/entry/entry_64.S:352
  |
  | read to 0xffff88808697d870 of 8 bytes by task 12060 on cpu 1:
  |  del_timer+0x3b/0xb0 kernel/time/timer.c:1198
  |  sk_stop_timer+0x25/0x60 net/core/sock.c:2845
  |  inet_csk_clear_xmit_timers+0x69/0xa0 net/ipv4/inet_connection_sock.c:523
  |  tcp_clear_xmit_timers include/net/tcp.h:606 [inline]
  |  tcp_v4_destroy_sock+0xa3/0x3f0 net/ipv4/tcp_ipv4.c:2096
  |  inet_csk_destroy_sock+0xf4/0x250 net/ipv4/inet_connection_sock.c:836
  |  tcp_close+0x6f3/0x970 net/ipv4/tcp.c:2497
  |  inet_release+0x86/0x100 net/ipv4/af_inet.c:427
  |  __sock_release+0x85/0x160 net/socket.c:590
  |  sock_close+0x24/0x30 net/socket.c:1268
  |  __fput+0x1e1/0x520 fs/file_table.c:280
  |  ____fput+0x1f/0x30 fs/file_table.c:313
  |  task_work_run+0xf6/0x130 kernel/task_work.c:113
  |  tracehook_notify_resume include/linux/tracehook.h:188 [inline]
  |  exit_to_usermode_loop+0x2b4/0x2c0 arch/x86/entry/common.c:163

Replace the explicit 'pprev' pointer comparison in timer_pending() with a call to hlist_unhashed() and initialise the 'expires' timer field explicitly in do_init_timer() so that the compiler doesn't emit bogus 'maybe used uninitialised' warnings now that it cannot reason statically about the result of timer_pending().

Quoted 5 lines
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Eric Dumazet <[email protected]>
#27 lore raw

RFC PATCH 5/21 list: Comment missing WRITE_ONCE() in __list_del()

In reply to Will Deacon

Although __list_del() is called from the RCU list implementation, it omits WRITE_ONCE() when updating the 'prev' pointer for the 'next' node. This is reasonable because concurrent RCU readers only access the 'next' pointers.

Although it's obvious after reading the code, add a comment.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list.h | 1 +
 1 file changed, 1 insertion(+)
include/linux/list.h +1 -0
index 4d9f5f9ed1a8..ec1f780d1449 100644
@@ -109,6 +109,7 @@ static inline void list_add_tail(struct list_head *new, struct list_head *head)
  */
 static inline void __list_del(struct list_head * prev, struct list_head * next)
 {
+	/* RCU readers don't read the 'prev' pointer */
 	next->prev = prev;
 	WRITE_ONCE(prev->next, next);
 }
Signature · 1 line
2.20.1
maintainer Reviewed-by on v1 5/21
#28 lore raw

Re: [RFC PATCH 05/21] list: Comment missing WRITE_ONCE() in __list_del()

Quoted 10 lines · Will Deacon

Although __list_del() is called from the RCU list implementation, it omits WRITE_ONCE() when updating the 'prev' pointer for the 'next' node. This is reasonable because concurrent RCU readers only access the 'next' pointers.

Although it's obvious after reading the code, add a comment.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

OK, I will take the easy one. ;-)

Quoted 19 lines
---
 include/linux/list.h | 1 +
 1 file changed, 1 insertion(+)
include/linux/list.h +1 -0
index 4d9f5f9ed1a8..ec1f780d1449 100644
@@ -109,6 +109,7 @@ static inline void list_add_tail(struct list_head *new, struct list_head *head)
  */
 static inline void __list_del(struct list_head * prev, struct list_head * next)
 {
+	/* RCU readers don't read the 'prev' pointer */
 	next->prev = prev;
 	WRITE_ONCE(prev->next, next);
 }
Signature · 1 line
2.20.1
#29 lore raw

RFC PATCH 6/21 list: Remove superfluous WRITE_ONCE() from hlist_nulls implementation

In reply to Will Deacon

Commit 860c8802ace1 ("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added WRITE_ONCE() invocations to hlist_nulls_add_head() and hlist_nulls_del().

Since these functions should not ordinarily run concurrently with other list accessors, restore the plain C assignments so that KCSAN can yell if a data race occurs.

Cc Eric Dumazet <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list_nulls.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
include/linux/list_nulls.h +3 -3
index fa51a801bf32..fd154ceb5b0d 100644
@@ -80,10 +80,10 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 	struct hlist_nulls_node *first = h->first;
 
 	n->next = first;
-	WRITE_ONCE(n->pprev, &h->first);
+	n->pprev = &h->first;
 	h->first = n;
 	if (!is_a_nulls(first))
-		WRITE_ONCE(first->pprev, &n->next);
+		first->pprev = &n->next;
 }
 
 static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
@@ -99,7 +99,7 @@ static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
 static inline void hlist_nulls_del(struct hlist_nulls_node *n)
 {
 	__hlist_nulls_del(n);
-	WRITE_ONCE(n->pprev, LIST_POISON2);
+	n->pprev = LIST_POISON2;
 }
 
 /**
Signature · 1 line
2.20.1
maintainer
#30 lore raw

Re: [RFC PATCH 06/21] list: Remove superfluous WRITE_ONCE() from hlist_nulls implementation

Quoted 4 lines · Will Deacon

Commit 860c8802ace1 ("rcu: Use WRITE_ONCE() for assignments to ->pprev for hlist_nulls") added WRITE_ONCE() invocations to hlist_nulls_add_head() and hlist_nulls_del().

Quoted 8 lines

Since these functions should not ordinarily run concurrently with other list accessors, restore the plain C assignments so that KCSAN can yell if a data race occurs.

Cc Eric Dumazet <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

And this means that the lockless uses of hlist_nulls_empty() need attention, correct?

Thanx, Paul

Quoted 33 lines
---
 include/linux/list_nulls.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
include/linux/list_nulls.h +3 -3
index fa51a801bf32..fd154ceb5b0d 100644
@@ -80,10 +80,10 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 	struct hlist_nulls_node *first = h->first;
 
 	n->next = first;
-	WRITE_ONCE(n->pprev, &h->first);
+	n->pprev = &h->first;
 	h->first = n;
 	if (!is_a_nulls(first))
-		WRITE_ONCE(first->pprev, &n->next);
+		first->pprev = &n->next;
 }
 
 static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
@@ -99,7 +99,7 @@ static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
 static inline void hlist_nulls_del(struct hlist_nulls_node *n)
 {
 	__hlist_nulls_del(n);
-	WRITE_ONCE(n->pprev, LIST_POISON2);
+	n->pprev = LIST_POISON2;
 }
 
 /**
Signature · 1 line
2.20.1
#31 lore raw

RFC PATCH 7/21 Revert "list: Use WRITE_ONCE() when adding to lists and hlists"

In reply to Will Deacon

This reverts commit 1c97be677f72b3c338312aecd36d8fff20322f32.

There is no need to use WRITE_ONCE() for the non-RCU list and hlist implementations.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
include/linux/list.h +3 -3
index ec1f780d1449..c7331c259792 100644
@@ -70,7 +70,7 @@ static inline void __list_add(struct list_head *new,
 	next->prev = new;
 	new->next = next;
 	new->prev = prev;
-	WRITE_ONCE(prev->next, new);
+	prev->next = new;
 }
 
 /**
@@ -843,7 +843,7 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 	n->next = first;
 	if (first)
 		first->pprev = &n->next;
-	WRITE_ONCE(h->first, n);
+	h->first = n;
 	n->pprev = &h->first;
 }
 
@@ -858,7 +858,7 @@ static inline void hlist_add_before(struct hlist_node *n,
 	n->pprev = next->pprev;
 	n->next = next;
 	next->pprev = &n->next;
-	WRITE_ONCE(*(n->pprev), n);
+	*(n->pprev) = n;
 }
 
 /**
Signature · 1 line
2.20.1
maintainer
#32 lore raw

Re: [RFC PATCH 07/21] Revert "list: Use WRITE_ONCE() when adding to lists and hlists"

Quoted 8 lines · Will Deacon

This reverts commit 1c97be677f72b3c338312aecd36d8fff20322f32.

There is no need to use WRITE_ONCE() for the non-RCU list and hlist implementations.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

Which means that the lockless uses of hlist_empty() will also need attention, correct?

Thanx, Paul

Quoted 38 lines
---
 include/linux/list.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
include/linux/list.h +3 -3
index ec1f780d1449..c7331c259792 100644
@@ -70,7 +70,7 @@ static inline void __list_add(struct list_head *new,
 	next->prev = new;
 	new->next = next;
 	new->prev = prev;
-	WRITE_ONCE(prev->next, new);
+	prev->next = new;
 }
 
 /**
@@ -843,7 +843,7 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 	n->next = first;
 	if (first)
 		first->pprev = &n->next;
-	WRITE_ONCE(h->first, n);
+	h->first = n;
 	n->pprev = &h->first;
 }
 
@@ -858,7 +858,7 @@ static inline void hlist_add_before(struct hlist_node *n,
 	n->pprev = next->pprev;
 	n->next = next;
 	next->pprev = &n->next;
-	WRITE_ONCE(*(n->pprev), n);
+	*(n->pprev) = n;
 }
 
 /**
Signature · 1 line
2.20.1
#33 lore raw

RFC PATCH 8/21 Revert "list: Use WRITE_ONCE() when initializing list_head structures"

In reply to Will Deacon

This reverts commit 2f073848c3cc8aff2655ab7c46d8c0de90cf4e50.

There is no need to use WRITE_ONCE() to initialise a non-RCU 'list_head'.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/list.h +1 -1
index c7331c259792..b86a3f9465d4 100644
@@ -32,7 +32,7 @@
  */
 static inline void INIT_LIST_HEAD(struct list_head *list)
 {
-	WRITE_ONCE(list->next, list);
+	list->next = list;
 	list->prev = list;
 }
 
Signature · 1 line
2.20.1
maintainer
#34 lore raw

Re: [RFC PATCH 08/21] Revert "list: Use WRITE_ONCE() when initializing list_head structures"

Quoted 7 lines · Will Deacon

This reverts commit 2f073848c3cc8aff2655ab7c46d8c0de90cf4e50.

There is no need to use WRITE_ONCE() to initialise a non-RCU 'list_head'.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

And attention to lockless uses of list_empty() here, correct?

Depending on the outcome of discussions on 3/21, I should have added in all three cases.

Thanx, Paul

Quoted 20 lines
---
 include/linux/list.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/list.h +1 -1
index c7331c259792..b86a3f9465d4 100644
@@ -32,7 +32,7 @@
  */
 static inline void INIT_LIST_HEAD(struct list_head *list)
 {
-	WRITE_ONCE(list->next, list);
+	list->next = list;
 	list->prev = list;
 }
 
Signature · 1 line
2.20.1
#35 lore raw

Re: [RFC PATCH 08/21] Revert "list: Use WRITE_ONCE() when initializing list_head structures"

Quoted 5 lines · Paul E. McKenney
Quoted 4 lines · Will Deacon

This reverts commit 2f073848c3cc8aff2655ab7c46d8c0de90cf4e50.

There is no need to use WRITE_ONCE() to initialise a non-RCU 'list_head'.

Quoted 8 lines
Quoted 3 lines
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

And attention to lockless uses of list_empty() here, correct?

Depending on the outcome of discussions on 3/21, I should have added in all three cases.

Yes, patch 3 is where this will get sorted. It looks like we'll have to disable KCSAN around the READ_ONCE() over there, but I also need to finish wrapping my head around list_empty_careful() because I'm deeply suspicious!

Will

maintainer
#36 lore raw

Re: [RFC PATCH 08/21] Revert "list: Use WRITE_ONCE() when initializing list_head structures"

Quoted 10 lines · Will Deacon
Quoted 9 lines · Paul E. McKenney
Quoted 7 lines · Will Deacon

This reverts commit 2f073848c3cc8aff2655ab7c46d8c0de90cf4e50.

There is no need to use WRITE_ONCE() to initialise a non-RCU 'list_head'.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
Quoted 8 lines
Quoted 4 lines

And attention to lockless uses of list_empty() here, correct?

Depending on the outcome of discussions on 3/21, I should have added in all three cases.

Yes, patch 3 is where this will get sorted. It looks like we'll have to disable KCSAN around the READ_ONCE() over there, but I also need to finish wrapping my head around list_empty_careful() because I'm deeply suspicious!

At the very least, it does have the disadvantage of touching an additional cache line, and up to two additional cache lines in the non-empty case. :-(

Thanx, Paul

#37 lore raw

RFC PATCH 9/21 list: Remove unnecessary WRITE_ONCE() from hlist_bl_add_before()

In reply to Will Deacon

There is no need to use WRITE_ONCE() when inserting into a non-RCU protected list.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list_bl.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
include/linux/list_bl.h +3 -3
index 1804fdb84dda..c93e7e3aa8fc 100644
@@ -91,15 +91,15 @@ static inline void hlist_bl_add_before(struct hlist_bl_node *n,
 				       struct hlist_bl_node *next)
 {
 	struct hlist_bl_node **pprev = next->pprev;
+	unsigned long val;
 
 	n->pprev = pprev;
 	n->next = next;
 	next->pprev = &n->next;
 
 	/* pprev may be `first`, so be careful not to lose the lock bit */
-	WRITE_ONCE(*pprev,
-		   (struct hlist_bl_node *)
-			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
+	val = (unsigned long)n | ((unsigned long)*pprev & LIST_BL_LOCKMASK);
+	*pprev = (struct hlist_bl_node *)val;
 }
 
 static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
Signature · 1 line
2.20.1
maintainer Reviewed-by on v1 9/21
#38 lore raw

Re: [RFC PATCH 09/21] list: Remove unnecessary WRITE_ONCE() from hlist_bl_add_before()

Quoted 6 lines · Will Deacon

There is no need to use WRITE_ONCE() when inserting into a non-RCU protected list.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

OK, I will bite... Why "unsigned long" instead of "uintptr_t"?

Not that it matters in the context of the Linux kernel, so:

Thanx, Paul

Quoted 30 lines
---
 include/linux/list_bl.h | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
include/linux/list_bl.h +3 -3
index 1804fdb84dda..c93e7e3aa8fc 100644
@@ -91,15 +91,15 @@ static inline void hlist_bl_add_before(struct hlist_bl_node *n,
 				       struct hlist_bl_node *next)
 {
 	struct hlist_bl_node **pprev = next->pprev;
+	unsigned long val;
 
 	n->pprev = pprev;
 	n->next = next;
 	next->pprev = &n->next;
 
 	/* pprev may be `first`, so be careful not to lose the lock bit */
-	WRITE_ONCE(*pprev,
-		   (struct hlist_bl_node *)
-			((uintptr_t)n | ((uintptr_t)*pprev & LIST_BL_LOCKMASK)));
+	val = (unsigned long)n | ((unsigned long)*pprev & LIST_BL_LOCKMASK);
+	*pprev = (struct hlist_bl_node *)val;
 }
 
 static inline void hlist_bl_add_behind(struct hlist_bl_node *n,
Signature · 1 line
2.20.1
#39 lore raw

Re: [RFC PATCH 09/21] list: Remove unnecessary WRITE_ONCE() from hlist_bl_add_before()

Quoted 9 lines · Paul E. McKenney
Quoted 6 lines · Will Deacon

There is no need to use WRITE_ONCE() when inserting into a non-RCU protected list.

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

OK, I will bite... Why "unsigned long" instead of "uintptr_t"?

I just did that for consistency with the rest of the file, e.g. hlist_bl_first(), hlist_bl_set_first(), hlist_bl_empty() and __hlist_bl_del() all cast to 'unsigned long', yet only hlist_bl_add_before() was using 'uintptr_t'

Quoted 3 lines

Not that it matters in the context of the Linux kernel, so:

Thanks, Paul!

Will

#40 lore raw

RFC PATCH 10/21 kernel-hacking: Make DEBUG_{LIST,PLIST,SG,NOTIFIERS} non-debug options

In reply to Will Deacon

The CONFIG_DEBUG_{LIST,PLIST,SG,NOTIFIERS} options can provide useful security hardening properties outside of debug scenarios. For example, CVE-2019-2215 and CVE-2019-2025 are mitigated with negligible runtime overhead by enabling CONFIG_DEBUG_LIST, and this option is already enabled by default on many distributions:

https://googleprojectzero.blogspot.com/2019/11/bad-binder-android-in-wild-exploit.html

Rename these options across the tree so that the naming better reflects their operation and remove the dependency on DEBUG_KERNEL.

Cc Maddie Stone <[email protected]>
Cc Jann Horn <[email protected]>
Cc Kees Cook <[email protected]>
Cc Greg Kroah-Hartman <[email protected]
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 arch/arm/configs/tegra_defconfig              |  2 +-
 arch/mips/configs/bigsur_defconfig            |  2 +-
 arch/powerpc/configs/ppc6xx_defconfig         |  4 ++--
 arch/powerpc/configs/ps3_defconfig            |  2 +-
 arch/powerpc/configs/skiroot_defconfig        |  4 ++--
 arch/riscv/configs/defconfig                  |  6 ++---
 arch/riscv/configs/rv32_defconfig             |  6 ++---
 arch/s390/configs/debug_defconfig             |  4 ++--
 arch/sh/configs/polaris_defconfig             |  2 +-
 arch/sh/configs/rsk7203_defconfig             |  4 ++--
 arch/sh/configs/se7206_defconfig              |  2 +-
 drivers/gpu/drm/radeon/mkregtable.c           |  2 +-
 drivers/staging/wfx/fwio.c                    |  2 +-
 drivers/staging/wfx/hwio.c                    |  2 +-
 include/linux/list.h                          |  2 +-
 include/linux/list_bl.h                       |  2 +-
 include/linux/plist.h                         |  4 ++--
 include/linux/scatterlist.h                   |  6 ++---
 kernel/notifier.c                             |  2 +-
 lib/Kconfig.debug                             | 24 ++++++++-----------
 lib/Makefile                                  |  2 +-
 lib/list_debug.c                              |  2 +-
 lib/plist.c                                   |  4 ++--
 tools/include/linux/list.h                    |  4 ++--
 .../selftests/wireguard/qemu/debug.config     |  6 ++---
 tools/virtio/linux/scatterlist.h              |  4 ++--
 26 files changed, 51 insertions(+), 55 deletions(-)
arch/arm/configs/tegra_defconfig +1 -1
index a27592d3b1fa..a7cadc9407e0 100644
@@ -299,6 +299,6 @@ CONFIG_DETECT_HUNG_TASK=y
 CONFIG_SCHEDSTATS=y
 # CONFIG_DEBUG_PREEMPT is not set
 CONFIG_DEBUG_MUTEXES=y
-CONFIG_DEBUG_SG=y
+CONFIG_CHECK_INTEGRITY_SG=y
 CONFIG_DEBUG_LL=y
 CONFIG_EARLY_PRINTK=y
arch/mips/configs/bigsur_defconfig +1 -1
index f14ad0538f4e..61fff4050486 100644
@@ -259,4 +259,4 @@ CONFIG_CRC7=m
 CONFIG_MAGIC_SYSRQ=y
 CONFIG_DEBUG_MEMORY_INIT=y
 CONFIG_DETECT_HUNG_TASK=y
-CONFIG_DEBUG_LIST=y
+CONFIG_CHECK_INTEGRITY_LIST=y
arch/powerpc/configs/ppc6xx_defconfig +2 -2
index 3e2f44f38ac5..6d46ff7dc1bc 100644
@@ -1133,8 +1133,8 @@ CONFIG_DEBUG_SHIRQ=y
 CONFIG_DEBUG_RT_MUTEXES=y
 CONFIG_DEBUG_SPINLOCK=y
 CONFIG_DEBUG_MUTEXES=y
-CONFIG_DEBUG_LIST=y
-CONFIG_DEBUG_SG=y
+CONFIG_CHECK_INTEGRITY_LIST=y
+CONFIG_CHECK_INTEGRITY_SG=y
 CONFIG_FAULT_INJECTION=y
 CONFIG_FAILSLAB=y
 CONFIG_FAIL_PAGE_ALLOC=y
arch/powerpc/configs/ps3_defconfig +1 -1
index 4db51719342a..12d0c10914ed 100644
@@ -160,7 +160,7 @@ CONFIG_DEBUG_STACKOVERFLOW=y
 CONFIG_DETECT_HUNG_TASK=y
 CONFIG_PROVE_LOCKING=y
 CONFIG_DEBUG_LOCKDEP=y
-CONFIG_DEBUG_LIST=y
+CONFIG_CHECK_INTEGRITY_LIST=y
 CONFIG_RCU_CPU_STALL_TIMEOUT=60
 # CONFIG_FTRACE is not set
 CONFIG_CRYPTO_PCBC=m
arch/powerpc/configs/skiroot_defconfig +2 -2
index 1b6bdad36b13..8ab17a33a1af 100644
@@ -306,8 +306,8 @@ CONFIG_HARDLOCKUP_DETECTOR=y
 CONFIG_BOOTPARAM_HARDLOCKUP_PANIC=y
 CONFIG_WQ_WATCHDOG=y
 # CONFIG_SCHED_DEBUG is not set
-CONFIG_DEBUG_SG=y
-CONFIG_DEBUG_NOTIFIERS=y
+CONFIG_CHECK_INTEGRITY_SG=y
+CONFIG_CHECK_INTEGRITY_NOTIFIERS=y
 CONFIG_BUG_ON_DATA_CORRUPTION=y
 CONFIG_DEBUG_CREDENTIALS=y
 # CONFIG_FTRACE is not set
arch/riscv/configs/defconfig +3 -3
index c8f084203067..dfa157c59822 100644
@@ -105,9 +105,9 @@ CONFIG_DEBUG_MUTEXES=y
 CONFIG_DEBUG_RWSEMS=y
 CONFIG_DEBUG_ATOMIC_SLEEP=y
 CONFIG_STACKTRACE=y
-CONFIG_DEBUG_LIST=y
-CONFIG_DEBUG_PLIST=y
-CONFIG_DEBUG_SG=y
+CONFIG_CHECK_INTEGRITY_LIST=y
+CONFIG_CHECK_INTEGRITY_PLIST=y
+CONFIG_CHECK_INTEGRITY_SG=y
 # CONFIG_RCU_TRACE is not set
 CONFIG_RCU_EQS_DEBUG=y
 CONFIG_DEBUG_BLOCK_EXT_DEVT=y
arch/riscv/configs/rv32_defconfig +3 -3
index a844920a261f..1893bfaf023e 100644
@@ -101,9 +101,9 @@ CONFIG_DEBUG_MUTEXES=y
 CONFIG_DEBUG_RWSEMS=y
 CONFIG_DEBUG_ATOMIC_SLEEP=y
 CONFIG_STACKTRACE=y
-CONFIG_DEBUG_LIST=y
-CONFIG_DEBUG_PLIST=y
-CONFIG_DEBUG_SG=y
+CONFIG_CHECK_INTEGRITY_LIST=y
+CONFIG_CHECK_INTEGRITY_PLIST=y
+CONFIG_CHECK_INTEGRITY_SG=y
 # CONFIG_RCU_TRACE is not set
 CONFIG_RCU_EQS_DEBUG=y
 CONFIG_DEBUG_BLOCK_EXT_DEVT=y
arch/s390/configs/debug_defconfig +2 -2
index 0c86ba19fa2b..438eb0ce4d64 100644
@@ -779,8 +779,8 @@ CONFIG_LOCK_STAT=y
 CONFIG_DEBUG_LOCKDEP=y
 CONFIG_DEBUG_ATOMIC_SLEEP=y
 CONFIG_DEBUG_LOCKING_API_SELFTESTS=y
-CONFIG_DEBUG_SG=y
-CONFIG_DEBUG_NOTIFIERS=y
+CONFIG_CHECK_INTEGRITY_SG=y
+CONFIG_CHECK_INTEGRITY_NOTIFIERS=y
 CONFIG_BUG_ON_DATA_CORRUPTION=y
 CONFIG_DEBUG_CREDENTIALS=y
 CONFIG_RCU_TORTURE_TEST=m
arch/sh/configs/polaris_defconfig +1 -1
index e3a1d3d2694a..699610cb4333 100644
@@ -81,4 +81,4 @@ CONFIG_DEBUG_RT_MUTEXES=y
 CONFIG_DEBUG_LOCK_ALLOC=y
 CONFIG_DEBUG_SPINLOCK_SLEEP=y
 CONFIG_DEBUG_INFO=y
-CONFIG_DEBUG_SG=y
+CONFIG_CHECK_INTEGRITY_SG=y
arch/sh/configs/rsk7203_defconfig +2 -2
index 10a32bd4cf66..74df7ab6a3e2 100644
@@ -118,7 +118,7 @@ CONFIG_DEBUG_MUTEXES=y
 CONFIG_DEBUG_SPINLOCK_SLEEP=y
 CONFIG_DEBUG_INFO=y
 CONFIG_DEBUG_VM=y
-CONFIG_DEBUG_LIST=y
-CONFIG_DEBUG_SG=y
+CONFIG_CHECK_INTEGRITY_LIST=y
+CONFIG_CHECK_INTEGRITY_SG=y
 CONFIG_FRAME_POINTER=y
 CONFIG_DEBUG_STACK_USAGE=y
arch/sh/configs/se7206_defconfig +1 -1
index a93402b3a319..612cba5e1fe3 100644
@@ -99,7 +99,7 @@ CONFIG_DEBUG_KERNEL=y
 CONFIG_DETECT_HUNG_TASK=y
 CONFIG_DEBUG_SPINLOCK_SLEEP=y
 CONFIG_DEBUG_VM=y
-CONFIG_DEBUG_LIST=y
+CONFIG_CHECK_INTEGRITY_LIST=y
 CONFIG_FRAME_POINTER=y
 CONFIG_DEBUG_STACK_USAGE=y
 CONFIG_CRYPTO_DEFLATE=y
drivers/gpu/drm/radeon/mkregtable.c +1 -1
index 52a7246fed9e..2765c9649056 100644
@@ -56,7 +56,7 @@ static inline void INIT_LIST_HEAD(struct list_head *list)
  * This is only for internal list manipulation where we know
  * the prev/next entries already!
  */
-#ifndef CONFIG_DEBUG_LIST
+#ifndef CONFIG_CHECK_INTEGRITY_LIST
 static inline void __list_add(struct list_head *new,
 			      struct list_head *prev, struct list_head *next)
 {
drivers/staging/wfx/fwio.c +1 -1
index 9d61082c1e6c..e10026ae7b13 100644
@@ -74,7 +74,7 @@ static const char * const fwio_errors[] = {
  * underlying hardware that use DMA. Function below detect this case and
  * allocate a bounce buffer if necessary.
  *
- * Notice that, in doubt, you can enable CONFIG_DEBUG_SG to ask kernel to
+ * Notice that, in doubt, you can enable CONFIG_CHECK_INTEGRITY_SG to ask kernel to
  * detect this problem at runtime  (else, kernel silently fail).
  *
  * NOTE: it may also be possible to use 'pages' from struct firmware and avoid
drivers/staging/wfx/hwio.c +1 -1
index 47e04c59ed93..3524b1b38d8e 100644
@@ -22,7 +22,7 @@
  * allocated data. Functions below that work with registers (aka functions
  * ending with "32") automatically reallocate buffers with kmalloc. However,
  * functions that work with arbitrary length buffers let's caller to handle
- * memory location. In doubt, enable CONFIG_DEBUG_SG to detect badly located
+ * memory location. In doubt, enable CONFIG_CHECK_INTEGRITY_SG to detect badly located
  * buffer.
  */
 
include/linux/list.h +1 -1
index b86a3f9465d4..2bef081afa69 100644
@@ -36,7 +36,7 @@ static inline void INIT_LIST_HEAD(struct list_head *list)
 	list->prev = list;
 }
 
-#ifdef CONFIG_DEBUG_LIST
+#ifdef CONFIG_CHECK_INTEGRITY_LIST
 extern bool __list_add_valid(struct list_head *new,
 			      struct list_head *prev,
 			      struct list_head *next);
include/linux/list_bl.h +1 -1
index c93e7e3aa8fc..9f8e29142324 100644
@@ -24,7 +24,7 @@
 #define LIST_BL_LOCKMASK	0UL
 #endif
 
-#ifdef CONFIG_DEBUG_LIST
+#ifdef CONFIG_CHECK_INTEGRITY_LIST
 #define LIST_BL_BUG_ON(x) BUG_ON(x)
 #else
 #define LIST_BL_BUG_ON(x)
include/linux/plist.h +2 -2
index 66bab1bca35c..da85b42c9ebf 100644
@@ -229,7 +229,7 @@ static inline int plist_node_empty(const struct plist_node *node)
  * @type:	the type of the struct this is embedded in
  * @member:	the name of the list_head within the struct
  */
-#ifdef CONFIG_DEBUG_PLIST
+#ifdef CONFIG_CHECK_INTEGRITY_PLIST
 # define plist_first_entry(head, type, member)	\
 ({ \
 	WARN_ON(plist_head_empty(head)); \
@@ -246,7 +246,7 @@ static inline int plist_node_empty(const struct plist_node *node)
  * @type:	the type of the struct this is embedded in
  * @member:	the name of the list_head within the struct
  */
-#ifdef CONFIG_DEBUG_PLIST
+#ifdef CONFIG_CHECK_INTEGRITY_PLIST
 # define plist_last_entry(head, type, member)	\
 ({ \
 	WARN_ON(plist_head_empty(head)); \
include/linux/scatterlist.h +3 -3
index 6eec50fb36c8..f9dc7e730a68 100644
@@ -93,7 +93,7 @@ static inline void sg_assign_page(struct scatterlist *sg, struct page *page)
 	 * must be aligned at a 32-bit boundary as a minimum.
 	 */
 	BUG_ON((unsigned long) page & (SG_CHAIN | SG_END));
-#ifdef CONFIG_DEBUG_SG
+#ifdef CONFIG_CHECK_INTEGRITY_SG
 	BUG_ON(sg_is_chain(sg));
 #endif
 	sg->page_link = page_link | (unsigned long) page;
@@ -123,7 +123,7 @@ static inline void sg_set_page(struct scatterlist *sg, struct page *page,
 
 static inline struct page *sg_page(struct scatterlist *sg)
 {
-#ifdef CONFIG_DEBUG_SG
+#ifdef CONFIG_CHECK_INTEGRITY_SG
 	BUG_ON(sg_is_chain(sg));
 #endif
 	return (struct page *)((sg)->page_link & ~(SG_CHAIN | SG_END));
@@ -139,7 +139,7 @@ static inline struct page *sg_page(struct scatterlist *sg)
 static inline void sg_set_buf(struct scatterlist *sg, const void *buf,
 			      unsigned int buflen)
 {
-#ifdef CONFIG_DEBUG_SG
+#ifdef CONFIG_CHECK_INTEGRITY_SG
 	BUG_ON(!virt_addr_valid(buf));
 #endif
 	sg_set_page(sg, virt_to_page(buf), buflen, offset_in_page(buf));
kernel/notifier.c +1 -1
index 63d7501ac638..b4c799b80227 100644
@@ -73,7 +73,7 @@ static int notifier_call_chain(struct notifier_block **nl,
 	while (nb && nr_to_call) {
 		next_nb = rcu_dereference_raw(nb->next);
 
-#ifdef CONFIG_DEBUG_NOTIFIERS
+#ifdef CONFIG_CHECK_INTEGRITY_NOTIFIERS
 		if (unlikely(!func_ptr_is_kernel_text(nb->notifier_call))) {
 			WARN(1, "Invalid notifier called!");
 			nb = next_nb;
lib/Kconfig.debug +10 -14
index 1458505192cd..f05ea01b30a7 100644
@@ -1312,20 +1312,18 @@ config DEBUG_KOBJECT_RELEASE
 config HAVE_DEBUG_BUGVERBOSE
 	bool
 
-menu "Debug kernel data structures"
+menu "Kernel data structure integrity"
 
-config DEBUG_LIST
-	bool "Debug linked list manipulation"
-	depends on DEBUG_KERNEL || BUG_ON_DATA_CORRUPTION
+config CHECK_INTEGRITY_LIST
+	bool "Check integrity of linked list manipulation"
 	help
 	  Enable this to turn on extended checks in the linked-list
 	  walking routines.
 
 	  If unsure, say N.
 
-config DEBUG_PLIST
-	bool "Debug priority linked list manipulation"
-	depends on DEBUG_KERNEL
+config CHECK_INTEGRITY_PLIST
+	bool "Check integrity of priority linked list manipulation"
 	help
 	  Enable this to turn on extended checks in the priority-ordered
 	  linked-list (plist) walking routines.  This checks the entire
@@ -1333,9 +1331,8 @@ config DEBUG_PLIST
 
 	  If unsure, say N.
 
-config DEBUG_SG
-	bool "Debug SG table operations"
-	depends on DEBUG_KERNEL
+config CHECK_INTEGRITY_SG
+	bool "Check integrity of SG table operations"
 	help
 	  Enable this to turn on checks on scatter-gather tables. This can
 	  help find problems with drivers that do not properly initialize
@@ -1343,9 +1340,8 @@ config DEBUG_SG
 
 	  If unsure, say N.
 
-config DEBUG_NOTIFIERS
-	bool "Debug notifier call chains"
-	depends on DEBUG_KERNEL
+config CHECK_INTEGRITY_NOTIFIERS
+	bool "Check integrity of notifier call chains"
 	help
 	  Enable this to turn on sanity checking for notifier call chains.
 	  This is most useful for kernel developers to make sure that
@@ -1355,7 +1351,7 @@ config DEBUG_NOTIFIERS
 
 config BUG_ON_DATA_CORRUPTION
 	bool "Trigger a BUG when data corruption is detected"
-	select DEBUG_LIST
+	select CHECK_INTEGRITY_LIST
 	help
 	  Select this option if the kernel should BUG when it encounters
 	  data corruption in kernel memory structures when they get checked
lib/Makefile +1 -1
index f19b85c87fda..6a3888dac634 100644
@@ -121,7 +121,7 @@ obj-$(CONFIG_BTREE) += btree.o
 obj-$(CONFIG_INTERVAL_TREE) += interval_tree.o
 obj-$(CONFIG_ASSOCIATIVE_ARRAY) += assoc_array.o
 obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o
-obj-$(CONFIG_DEBUG_LIST) += list_debug.o
+obj-$(CONFIG_CHECK_INTEGRITY_LIST) += list_debug.o
 obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
 
 obj-$(CONFIG_BITREVERSE) += bitrev.o
lib/list_debug.c +1 -1
index 5d5424b51b74..57bf685af2ef 100644
@@ -2,7 +2,7 @@
  * Copyright 2006, Red Hat, Inc., Dave Jones
  * Released under the General Public License (GPL).
  *
- * This file contains the linked list validation for DEBUG_LIST.
+ * This file contains the linked list validation for CHECK_INTEGRITY_LIST.
  */
 
 #include <linux/export.h>
lib/plist.c +2 -2
index 0d86ed7a76ac..c06e98e78259 100644
@@ -25,7 +25,7 @@
 #include <linux/bug.h>
 #include <linux/plist.h>
 
-#ifdef CONFIG_DEBUG_PLIST
+#ifdef CONFIG_CHECK_INTEGRITY_PLIST
 
 static struct plist_head test_head;
 
@@ -172,7 +172,7 @@ void plist_requeue(struct plist_node *node, struct plist_head *head)
 	plist_check_head(head);
 }
 
-#ifdef CONFIG_DEBUG_PLIST
+#ifdef CONFIG_CHECK_INTEGRITY_PLIST
 #include <linux/sched.h>
 #include <linux/sched/clock.h>
 #include <linux/module.h>
tools/include/linux/list.h +2 -2
index b2fc48d5478c..7a7a7f1cf380 100644
@@ -34,7 +34,7 @@ static inline void INIT_LIST_HEAD(struct list_head *list)
  * This is only for internal list manipulation where we know
  * the prev/next entries already!
  */
-#ifndef CONFIG_DEBUG_LIST
+#ifndef CONFIG_CHECK_INTEGRITY_LIST
 static inline void __list_add(struct list_head *new,
 			      struct list_head *prev,
 			      struct list_head *next)
@@ -96,7 +96,7 @@ 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
+#ifndef CONFIG_CHECK_INTEGRITY_LIST
 static inline void __list_del_entry(struct list_head *entry)
 {
 	__list_del(entry->prev, entry->next);
tools/testing/selftests/wireguard/qemu/debug.config +3 -3
index 5909e7ef2a5c..04f8ed0600e1 100644
@@ -48,7 +48,7 @@ CONFIG_LOCKDEP=y
 CONFIG_DEBUG_ATOMIC_SLEEP=y
 CONFIG_TRACE_IRQFLAGS=y
 CONFIG_DEBUG_BUGVERBOSE=y
-CONFIG_DEBUG_LIST=y
+CONFIG_CHECK_INTEGRITY_LIST=y
 CONFIG_DEBUG_PI_LIST=y
 CONFIG_PROVE_RCU=y
 CONFIG_SPARSE_RCU_POINTER=y
@@ -56,8 +56,8 @@ CONFIG_RCU_CPU_STALL_TIMEOUT=21
 CONFIG_RCU_TRACE=y
 CONFIG_RCU_EQS_DEBUG=y
 CONFIG_USER_STACKTRACE_SUPPORT=y
-CONFIG_DEBUG_SG=y
-CONFIG_DEBUG_NOTIFIERS=y
+CONFIG_CHECK_INTEGRITY_SG=y
+CONFIG_CHECK_INTEGRITY_NOTIFIERS=y
 CONFIG_DOUBLEFAULT=y
 CONFIG_X86_DEBUG_FPU=y
 CONFIG_DEBUG_SECTION_MISMATCH=y
tools/virtio/linux/scatterlist.h +2 -2
index 369ee308b668..9fe5341b5a4a 100644
@@ -35,7 +35,7 @@ static inline void sg_assign_page(struct scatterlist *sg, struct page *page)
 	 * must be aligned at a 32-bit boundary as a minimum.
 	 */
 	BUG_ON((unsigned long) page & 0x03);
-#ifdef CONFIG_DEBUG_SG
+#ifdef CONFIG_CHECK_INTEGRITY_SG
 	BUG_ON(sg_is_chain(sg));
 #endif
 	sg->page_link = page_link | (unsigned long) page;
@@ -65,7 +65,7 @@ static inline void sg_set_page(struct scatterlist *sg, struct page *page,
 
 static inline struct page *sg_page(struct scatterlist *sg)
 {
-#ifdef CONFIG_DEBUG_SG
+#ifdef CONFIG_CHECK_INTEGRITY_SG
 	BUG_ON(sg_is_chain(sg));
 #endif
 	return (struct page *)((sg)->page_link & ~0x3);
Signature · 1 line
2.20.1
maintainer Reviewed-by on v1 10/21
#41 lore raw

Re: [RFC PATCH 10/21] kernel-hacking: Make DEBUG_{LIST,PLIST,SG,NOTIFIERS} non-debug options

Quoted 11 lines · Will Deacon

The CONFIG_DEBUG_{LIST,PLIST,SG,NOTIFIERS} options can provide useful security hardening properties outside of debug scenarios. For example, CVE-2019-2215 and CVE-2019-2025 are mitigated with negligible runtime overhead by enabling CONFIG_DEBUG_LIST, and this option is already enabled by default on many distributions:

https://googleprojectzero.blogspot.com/2019/11/bad-binder-android-in-wild-exploit.html

Rename these options across the tree so that the naming better reflects their operation and remove the dependency on DEBUG_KERNEL.

Quoted 7 lines
Cc Maddie Stone <[email protected]>
Cc Jann Horn <[email protected]>
Cc Kees Cook <[email protected]>
Cc Greg Kroah-Hartman <[email protected]
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
#42 lore raw

RFC PATCH 11/21 list: Add integrity checking to hlist implementation

In reply to Will Deacon

Extend the 'hlist' implementation so that it can optionally perform integrity checking in a similar fashion to the standard 'list' code when CONFIG_CHECK_INTEGRITY_LIST=y.

Cc Kees Cook <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list.h    | 41 ++++++++++++++++++++-
 include/linux/rculist.h | 80 ++++++++++++++++++++++-------------------
 lib/list_debug.c        | 79 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 162 insertions(+), 38 deletions(-)
include/linux/list.h +40 -1
index 2bef081afa69..96ede36a5614 100644
@@ -41,6 +41,13 @@ 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);
+extern bool __hlist_add_before_valid(struct hlist_node *new,
+				     struct hlist_node *next);
+extern bool __hlist_add_behind_valid(struct hlist_node *new,
+				     struct hlist_node *prev);
+extern bool __hlist_add_head_valid(struct hlist_node *new,
+				   struct hlist_head *head);
+extern bool __hlist_del_valid(struct hlist_node *node);
 #else
 static inline bool __list_add_valid(struct list_head *new,
 				struct list_head *prev,
@@ -52,6 +59,25 @@ static inline bool __list_del_entry_valid(struct list_head *entry)
 {
 	return true;
 }
+static inline bool __hlist_add_before_valid(struct hlist_node *new,
+					    struct hlist_node *next)
+{
+	return true;
+}
+static inline bool __hlist_add_behind_valid(struct hlist_node *new,
+					    struct hlist_node *prev)
+{
+	return true;
+}
+static inline bool __hlist_add_head_valid(struct hlist_node *new,
+					  struct hlist_head *head)
+{
+	return true;
+}
+static inline bool __hlist_del_valid(struct hlist_node *node)
+{
+	return true;
+}
 #endif
 
 /*
@@ -796,6 +822,9 @@ static inline void __hlist_del(struct hlist_node *n)
 	struct hlist_node *next = n->next;
 	struct hlist_node **pprev = n->pprev;
 
+	if (!__hlist_del_valid(n))
+		return;
+
 	WRITE_ONCE(*pprev, next);
 	if (next)
 		WRITE_ONCE(next->pprev, pprev);
@@ -840,6 +869,10 @@ static inline void hlist_del_init(struct hlist_node *n)
 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 {
 	struct hlist_node *first = h->first;
+
+	if (!__hlist_add_head_valid(n, h))
+		return;
+
 	n->next = first;
 	if (first)
 		first->pprev = &n->next;
@@ -855,6 +888,9 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 static inline void hlist_add_before(struct hlist_node *n,
 				    struct hlist_node *next)
 {
+	if (!__hlist_add_before_valid(n, next))
+		return;
+
 	n->pprev = next->pprev;
 	n->next = next;
 	next->pprev = &n->next;
@@ -862,13 +898,16 @@ static inline void hlist_add_before(struct hlist_node *n,
 }
 
 /**
- * hlist_add_behing - add a new entry after the one specified
+ * hlist_add_behind - add a new entry after the one specified
  * @n: new entry to be added
  * @prev: hlist node to add it after, which must be non-NULL
  */
 static inline void hlist_add_behind(struct hlist_node *n,
 				    struct hlist_node *prev)
 {
+	if (!__hlist_add_behind_valid(n, prev))
+		return;
+
 	n->next = prev->next;
 	prev->next = n;
 	n->pprev = &prev->next;
include/linux/rculist.h +43 -37

110 lines not on this page · raw message

lib/list_debug.c +79 -0

82 lines not on this page · raw message

Signature · 1 line
2.20.1
#43 lore raw

RFC PATCH 12/21 list: Poison ->next pointer for non-RCU deletion of 'hlist_nulls_node'

In reply to Will Deacon

hlist_nulls_del() is used for non-RCU deletion of an 'hlist_nulls_node' and so we can safely poison the ->next pointer without having to worry about concurrent readers, just like we do for other non-RCU list deletion primitives

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list_nulls.h | 1 +
 1 file changed, 1 insertion(+)
include/linux/list_nulls.h +1 -0
index fd154ceb5b0d..48f33ae16381 100644
@@ -99,6 +99,7 @@ static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
 static inline void hlist_nulls_del(struct hlist_nulls_node *n)
 {
 	__hlist_nulls_del(n);
+	n->next = LIST_POISON1;
 	n->pprev = LIST_POISON2;
 }
 
Signature · 1 line
2.20.1
maintainer Reviewed-by on v1 12/21
#44 lore raw

Re: [RFC PATCH 12/21] list: Poison ->next pointer for non-RCU deletion of 'hlist_nulls_node'

Quoted 8 lines · Will Deacon

hlist_nulls_del() is used for non-RCU deletion of an 'hlist_nulls_node' and so we can safely poison the ->next pointer without having to worry about concurrent readers, just like we do for other non-RCU list deletion primitives

Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>

Agreed, any code having difficulty with this change should use instead hlist_nulls_del_rcu().

Quoted 19 lines
---
 include/linux/list_nulls.h | 1 +
 1 file changed, 1 insertion(+)
include/linux/list_nulls.h +1 -0
index fd154ceb5b0d..48f33ae16381 100644
@@ -99,6 +99,7 @@ static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
 static inline void hlist_nulls_del(struct hlist_nulls_node *n)
 {
 	__hlist_nulls_del(n);
+	n->next = LIST_POISON1;
 	n->pprev = LIST_POISON2;
 }
 
Signature · 1 line
2.20.1
#45 lore raw

RFC PATCH 13/21 list: Add integrity checking to hlist_nulls implementation

In reply to Will Deacon

Extend the 'hlist_nulls' implementation so that it can optionally perform integrity checking in a similar fashion to the standard 'list' code when CONFIG_CHECK_INTEGRITY_LIST=y.

On architectures without a trap value for ILLEGAL_POINTER_VALUE (i.e. all 32-bit architectures), explicit pointer/poison checks can help to mitigate UAF vulnerabilities such as the one exploited by "pingpongroot" (CVE-2015-3636).

Cc Kees Cook <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list_nulls.h | 23 +++++++++++++++++++
 lib/list_debug.c           | 47 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 70 insertions(+)
include/linux/list_nulls.h +23 -0
index 48f33ae16381..379e097e92b0 100644
@@ -35,6 +35,23 @@ struct hlist_nulls_node {
 	({ typeof(ptr) ____ptr = (ptr); \
 	   !is_a_nulls(____ptr) ? hlist_nulls_entry(____ptr, type, member) : NULL; \
 	})
+
+#ifdef CONFIG_CHECK_INTEGRITY_LIST
+extern bool __hlist_nulls_add_head_valid(struct hlist_nulls_node *new,
+					 struct hlist_nulls_head *head);
+extern bool __hlist_nulls_del_valid(struct hlist_nulls_node *node);
+#else
+static inline bool __hlist_nulls_add_head_valid(struct hlist_nulls_node *new,
+						struct hlist_nulls_head *head)
+{
+	return true;
+}
+static inline bool __hlist_nulls_del_valid(struct hlist_nulls_node *node)
+{
+	return true;
+}
+#endif
+
 /**
  * ptr_is_a_nulls - Test if a ptr is a nulls
  * @ptr: ptr to be tested
@@ -79,6 +96,9 @@ static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
 {
 	struct hlist_nulls_node *first = h->first;
 
+	if (!__hlist_nulls_add_head_valid(n, h))
+		return;
+
 	n->next = first;
 	n->pprev = &h->first;
 	h->first = n;
@@ -91,6 +111,9 @@ static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
 	struct hlist_nulls_node *next = n->next;
 	struct hlist_nulls_node **pprev = n->pprev;
 
+	if (!__hlist_nulls_del_valid(n))
+		return;
+
 	WRITE_ONCE(*pprev, next);
 	if (!is_a_nulls(next))
 		WRITE_ONCE(next->pprev, pprev);
lib/list_debug.c +47 -0

56 lines not on this page · raw message

Signature · 1 line
2.20.1
#46 lore raw

RFC PATCH 14/21 plist: Use CHECK_DATA_CORRUPTION instead of explicit {BUG,WARN}_ON()

In reply to Will Deacon

CHECK_DATA_CORRUPTION() allows detected data corruption to result consistently in either a BUG() or a WARN() depending on CONFIG_BUG_ON_DATA_CORRUPTION.

Use CHECK_DATA_CORRUPTION() to report plist integrity checking failures, rather than explicit use of BUG_ON() and WARN_ON().

Cc Kees Cook <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 lib/plist.c | 63 ++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 40 insertions(+), 23 deletions(-)
lib/plist.c +40 -23
index c06e98e78259..eb127eaab235 100644
@@ -29,39 +29,46 @@
 
 static struct plist_head test_head;
 
-static void plist_check_prev_next(struct list_head *t, struct list_head *p,
-				  struct list_head *n)
+static bool plist_prev_next_invalid(struct list_head *t, struct list_head *p,
+				    struct list_head *n)
 {
-	WARN(n->prev != p || p->next != n,
-			"top: %p, n: %p, p: %p\n"
-			"prev: %p, n: %p, p: %p\n"
-			"next: %p, n: %p, p: %p\n",
+	return CHECK_DATA_CORRUPTION(n->prev != p || p->next != n,
+			"plist corruption:\n"
+			"\ttop: %p, n: %p, p: %p\n"
+			"\tprev: %p, n: %p, p: %p\n"
+			"\tnext: %p, n: %p, p: %p\n",
 			 t, t->next, t->prev,
 			p, p->next, p->prev,
 			n, n->next, n->prev);
 }
 
-static void plist_check_list(struct list_head *top)
+static bool plist_list_invalid(struct list_head *top)
 {
 	struct list_head *prev = top, *next = top->next;
+	bool corruption;
 
-	plist_check_prev_next(top, prev, next);
+	corruption = plist_prev_next_invalid(top, prev, next);
 	while (next != top) {
 		prev = next;
 		next = prev->next;
-		plist_check_prev_next(top, prev, next);
+		corruption |= plist_prev_next_invalid(top, prev, next);
 	}
+
+	return corruption;
 }
 
-static void plist_check_head(struct plist_head *head)
+static bool plist_head_valid(struct plist_head *head)
 {
+	bool corruption = false;
+
 	if (!plist_head_empty(head))
-		plist_check_list(&plist_first(head)->prio_list);
-	plist_check_list(&head->node_list);
+		corruption |= plist_list_invalid(&plist_first(head)->prio_list);
+	corruption |= plist_list_invalid(&head->node_list);
+	return !corruption;
 }
 
 #else
-# define plist_check_head(h)	do { } while (0)
+# define plist_head_valid(h)	(true)
 #endif
 
 /**
@@ -75,9 +82,12 @@ void plist_add(struct plist_node *node, struct plist_head *head)
 	struct plist_node *first, *iter, *prev = NULL;
 	struct list_head *node_next = &head->node_list;
 
-	plist_check_head(head);
-	WARN_ON(!plist_node_empty(node));
-	WARN_ON(!list_empty(&node->prio_list));
+	if (!plist_head_valid(head) ||
+	    CHECK_DATA_CORRUPTION(!plist_node_empty(node),
+			"plist_add corruption. node list is not empty.\n") ||
+	    CHECK_DATA_CORRUPTION(!list_empty(&node->prio_list),
+			"plist_add corruption. node prio list is not empty.\n"))
+		return;
 
 	if (plist_head_empty(head))
 		goto ins_node;
@@ -100,7 +110,8 @@ void plist_add(struct plist_node *node, struct plist_head *head)
 ins_node:
 	list_add_tail(&node->node_list, node_next);
 
-	plist_check_head(head);
+	if (!plist_head_valid(head))
+		return;
 }
 
 /**
@@ -111,7 +122,8 @@ void plist_add(struct plist_node *node, struct plist_head *head)
  */
 void plist_del(struct plist_node *node, struct plist_head *head)
 {
-	plist_check_head(head);
+	if (!plist_head_valid(head))
+		return;
 
 	if (!list_empty(&node->prio_list)) {
 		if (node->node_list.next != &head->node_list) {
@@ -129,7 +141,8 @@ void plist_del(struct plist_node *node, struct plist_head *head)
 
 	list_del_init(&node->node_list);
 
-	plist_check_head(head);
+	if (!plist_head_valid(head))
+		return;
 }
 
 /**
@@ -147,9 +160,12 @@ void plist_requeue(struct plist_node *node, struct plist_head *head)
 	struct plist_node *iter;
 	struct list_head *node_next = &head->node_list;
 
-	plist_check_head(head);
-	BUG_ON(plist_head_empty(head));
-	BUG_ON(plist_node_empty(node));
+	if (!plist_head_valid(head) ||
+	    CHECK_DATA_CORRUPTION(plist_head_empty(head),
+			"plist_requeue corruption. head list is empty.\n") ||
+	    CHECK_DATA_CORRUPTION(plist_node_empty(node),
+			"plist_requeue corruption. node list is empty.\n"))
+		return;
 
 	if (node == plist_last(head))
 		return;
@@ -169,7 +185,8 @@ void plist_requeue(struct plist_node *node, struct plist_head *head)
 	}
 	list_add_tail(&node->node_list, node_next);
 
-	plist_check_head(head);
+	if (!plist_head_valid(head))
+		return;
 }
 
 #ifdef CONFIG_CHECK_INTEGRITY_PLIST
Signature · 1 line
2.20.1
maintainer Reviewed-by on v1 14/21
#47 lore raw

Re: [RFC PATCH 14/21] plist: Use CHECK_DATA_CORRUPTION instead of explicit {BUG,WARN}_ON()

Quoted 11 lines · Will Deacon

CHECK_DATA_CORRUPTION() allows detected data corruption to result consistently in either a BUG() or a WARN() depending on CONFIG_BUG_ON_DATA_CORRUPTION.

Use CHECK_DATA_CORRUPTION() to report plist integrity checking failures, rather than explicit use of BUG_ON() and WARN_ON().

Cc Kees Cook <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
#48 lore raw

RFC PATCH 15/21 list_bl: Use CHECK_DATA_CORRUPTION instead of custom BUG_ON() wrapper

In reply to Will Deacon

CHECK_DATA_CORRUPTION() allows detected data corruption to result consistently in either a BUG() or a WARN() depending on CONFIG_BUG_ON_DATA_CORRUPTION.

Use CHECK_DATA_CORRUPTION() to report list_bl integrity checking failures, rather than a custom wrapper around BUG_ON().

Cc Kees Cook <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list_bl.h    | 55 +++++++++++++++++++++++++-------------
 include/linux/rculist_bl.h | 17 ++++--------
 2 files changed, 42 insertions(+), 30 deletions(-)
include/linux/list_bl.h +37 -18
index 9f8e29142324..f48d8acb15b4 100644
@@ -24,13 +24,6 @@
 #define LIST_BL_LOCKMASK	0UL
 #endif
 
-#ifdef CONFIG_CHECK_INTEGRITY_LIST
-#define LIST_BL_BUG_ON(x) BUG_ON(x)
-#else
-#define LIST_BL_BUG_ON(x)
-#endif
-
-
 struct hlist_bl_head {
 	struct hlist_bl_node *first;
 };
@@ -38,6 +31,37 @@ struct hlist_bl_head {
 struct hlist_bl_node {
 	struct hlist_bl_node *next, **pprev;
 };
+
+#ifdef CONFIG_CHECK_INTEGRITY_LIST
+static inline bool __hlist_bl_add_head_valid(struct hlist_bl_head *h,
+					     struct hlist_bl_node *n)
+{
+	unsigned long hlock = (unsigned long)h->first & LIST_BL_LOCKMASK;
+	unsigned long nlock = (unsigned long)n & LIST_BL_LOCKMASK;
+
+	return !(CHECK_DATA_CORRUPTION(nlock,
+			"hlist_bl_add_head: node is locked\n") ||
+		 CHECK_DATA_CORRUPTION(hlock != LIST_BL_LOCKMASK,
+			"hlist_bl_add_head: head is unlocked\n"));
+}
+
+static inline bool __hlist_bl_del_valid(struct hlist_bl_node *n)
+{
+	unsigned long nlock = (unsigned long)n & LIST_BL_LOCKMASK;
+	return !CHECK_DATA_CORRUPTION(nlock, "hlist_bl_del_valid: node locked");
+}
+#else
+static inline bool __hlist_bl_add_head_valid(struct hlist_bl_head *h,
+					     struct hlist_bl_node *n)
+{
+	return true;
+}
+static inline bool __hlist_bl_del_valid(struct hlist_bl_node *n)
+{
+	return true;
+}
+#endif
+
 #define INIT_HLIST_BL_HEAD(ptr) \
 	((ptr)->first = NULL)
 
@@ -60,15 +84,6 @@ static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h)
 		((unsigned long)h->first & ~LIST_BL_LOCKMASK);
 }
 
-static inline void hlist_bl_set_first(struct hlist_bl_head *h,
-					struct hlist_bl_node *n)
-{
-	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
-	LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
-							LIST_BL_LOCKMASK);
-	h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
-}
-
 static inline bool hlist_bl_empty(const struct hlist_bl_head *h)
 {
 	unsigned long first = data_race((unsigned long)READ_ONCE(h->first));
@@ -80,11 +95,14 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
 {
 	struct hlist_bl_node *first = hlist_bl_first(h);
 
+	if (!__hlist_bl_add_head_valid(h, n))
+		return;
+
 	n->next = first;
 	if (first)
 		first->pprev = &n->next;
 	n->pprev = &h->first;
-	hlist_bl_set_first(h, n);
+	h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK);
 }
 
 static inline void hlist_bl_add_before(struct hlist_bl_node *n,
@@ -118,7 +136,8 @@ static inline void __hlist_bl_del(struct hlist_bl_node *n)
 	struct hlist_bl_node *next = n->next;
 	struct hlist_bl_node **pprev = n->pprev;
 
-	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
+	if (!__hlist_bl_del_valid(n))
+		return;
 
 	/* pprev may be `first`, so be careful not to lose the lock bit */
 	WRITE_ONCE(*pprev,
include/linux/rculist_bl.h +5 -12
index 0b952d06eb0b..553ce3cde104 100644
@@ -8,16 +8,6 @@
 #include <linux/list_bl.h>
 #include <linux/rcupdate.h>
 
-static inline void hlist_bl_set_first_rcu(struct hlist_bl_head *h,
-					struct hlist_bl_node *n)
-{
-	LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK);
-	LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) !=
-							LIST_BL_LOCKMASK);
-	rcu_assign_pointer(h->first,
-		(struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK));
-}
-
 static inline struct hlist_bl_node *hlist_bl_first_rcu(struct hlist_bl_head *h)
 {
 	return (struct hlist_bl_node *)
@@ -73,6 +63,9 @@ static inline void hlist_bl_add_head_rcu(struct hlist_bl_node *n,
 {
 	struct hlist_bl_node *first;
 
+	if (!__hlist_bl_add_head_valid(h, n))
+		return;
+
 	/* don't need hlist_bl_first_rcu because we're under lock */
 	first = hlist_bl_first(h);
 
@@ -81,8 +74,8 @@ static inline void hlist_bl_add_head_rcu(struct hlist_bl_node *n,
 		first->pprev = &n->next;
 	n->pprev = &h->first;
 
-	/* need _rcu because we can have concurrent lock free readers */
-	hlist_bl_set_first_rcu(h, n);
+	rcu_assign_pointer(h->first,
+		(struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK));
 }
 /**
  * hlist_bl_for_each_entry_rcu - iterate over rcu list of given type
Signature · 1 line
2.20.1
#49 lore raw

RFC PATCH 16/21 list_bl: Extend integrity checking in deletion routines

In reply to Will Deacon

Although deleting an entry from an 'hlist_bl' optionally checks that the node being removed is unlocked before subsequently removing it and poisoning its pointers, we don't actually check for the poison values like we do for other list implementations.

Add poison checks to __hlist_bl_del_valid() so that we can catch list corruption without relying on a later fault.

Cc Kees Cook <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 include/linux/list_bl.h | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
include/linux/list_bl.h +9 -1
index f48d8acb15b4..0839c4f43e6d 100644
@@ -48,7 +48,15 @@ static inline bool __hlist_bl_add_head_valid(struct hlist_bl_head *h,
 static inline bool __hlist_bl_del_valid(struct hlist_bl_node *n)
 {
 	unsigned long nlock = (unsigned long)n & LIST_BL_LOCKMASK;
-	return !CHECK_DATA_CORRUPTION(nlock, "hlist_bl_del_valid: node locked");
+
+	return !(CHECK_DATA_CORRUPTION(nlock,
+			"hlist_bl_del_valid: node locked") ||
+		 CHECK_DATA_CORRUPTION(n->next == LIST_POISON1,
+			"hlist_bl_del corruption, %px->next is LIST_POISON1 (%px)\n",
+			n, LIST_POISON1) ||
+		 CHECK_DATA_CORRUPTION(n->pprev == LIST_POISON2,
+			"hlist_bl_del corruption, %px->pprev is LIST_POISON2 (%px)\n",
+			n, LIST_POISON2));
 }
 #else
 static inline bool __hlist_bl_add_head_valid(struct hlist_bl_head *h,
Signature · 1 line
2.20.1
#50 lore raw

RFC PATCH 17/21 linux/bit_spinlock.h: Include linux/processor.h

In reply to Will Deacon

Needed for cpu_relax().

---
 include/linux/bit_spinlock.h | 1 +
 1 file changed, 1 insertion(+)
include/linux/bit_spinlock.h +1 -0
index bbc4730a6505..505daa942527 100644
@@ -6,6 +6,7 @@
 #include <linux/preempt.h>
 #include <linux/atomic.h>
 #include <linux/bug.h>
+#include <linux/processor.h>
 
 /*
  *  bit-based spin_lock()
Signature · 1 line
2.20.1
maintainer
#51 lore raw

Re: [RFC PATCH 17/21] linux/bit_spinlock.h: Include linux/processor.h

Quoted 1 line · Will Deacon

Needed for cpu_relax().

Is this needed now, or for the next patch? And if for next patch, why not just add it then?

thanks,

greg k-h

#52 lore raw

Re: [RFC PATCH 17/21] linux/bit_spinlock.h: Include linux/processor.h

Quoted 5 lines · Greg KH
Quoted 1 line · Will Deacon

Needed for cpu_relax().

Is this needed now, or for the next patch? And if for next patch, why not just add it then?

If the next patch correctly included linux/list_bl.h like it was supposed to, then yes, it's needed there. I'll sort that out and fold this in for v2.

Cheers,

Will

#53 lore raw

RFC PATCH 18/21 list_bl: Move integrity checking out of line

In reply to Will Deacon

In preparation for adding full integrity checking to 'hlist_bl', move the checks out of line before they become more bloated. At the same, swap the argument order for __hlist_bl_add_head_valid() so that it follows the same convention as __hlist_add_head_valid().

---
 include/linux/list_bl.h    | 34 ++++++----------------------------
 include/linux/rculist_bl.h |  2 +-
 lib/list_debug.c           | 28 ++++++++++++++++++++++++++++
 3 files changed, 35 insertions(+), 29 deletions(-)
include/linux/list_bl.h +6 -28
index 0839c4f43e6d..dd74043ebae6 100644
@@ -33,34 +33,12 @@ struct hlist_bl_node {
 };
 
 #ifdef CONFIG_CHECK_INTEGRITY_LIST
-static inline bool __hlist_bl_add_head_valid(struct hlist_bl_head *h,
-					     struct hlist_bl_node *n)
-{
-	unsigned long hlock = (unsigned long)h->first & LIST_BL_LOCKMASK;
-	unsigned long nlock = (unsigned long)n & LIST_BL_LOCKMASK;
-
-	return !(CHECK_DATA_CORRUPTION(nlock,
-			"hlist_bl_add_head: node is locked\n") ||
-		 CHECK_DATA_CORRUPTION(hlock != LIST_BL_LOCKMASK,
-			"hlist_bl_add_head: head is unlocked\n"));
-}
-
-static inline bool __hlist_bl_del_valid(struct hlist_bl_node *n)
-{
-	unsigned long nlock = (unsigned long)n & LIST_BL_LOCKMASK;
-
-	return !(CHECK_DATA_CORRUPTION(nlock,
-			"hlist_bl_del_valid: node locked") ||
-		 CHECK_DATA_CORRUPTION(n->next == LIST_POISON1,
-			"hlist_bl_del corruption, %px->next is LIST_POISON1 (%px)\n",
-			n, LIST_POISON1) ||
-		 CHECK_DATA_CORRUPTION(n->pprev == LIST_POISON2,
-			"hlist_bl_del corruption, %px->pprev is LIST_POISON2 (%px)\n",
-			n, LIST_POISON2));
-}
+extern bool __hlist_bl_add_head_valid(struct hlist_bl_node *n,
+				      struct hlist_bl_head *h);
+extern bool __hlist_bl_del_valid(struct hlist_bl_node *node);
 #else
-static inline bool __hlist_bl_add_head_valid(struct hlist_bl_head *h,
-					     struct hlist_bl_node *n)
+static inline bool __hlist_bl_add_head_valid(struct hlist_bl_node *n,
+					     struct hlist_bl_head *h)
 {
 	return true;
 }
@@ -103,7 +81,7 @@ static inline void hlist_bl_add_head(struct hlist_bl_node *n,
 {
 	struct hlist_bl_node *first = hlist_bl_first(h);
 
-	if (!__hlist_bl_add_head_valid(h, n))
+	if (!__hlist_bl_add_head_valid(n, h))
 		return;
 
 	n->next = first;
include/linux/rculist_bl.h +1 -1
index 553ce3cde104..9356e7283ff0 100644
@@ -63,7 +63,7 @@ static inline void hlist_bl_add_head_rcu(struct hlist_bl_node *n,
 {
 	struct hlist_bl_node *first;
 
-	if (!__hlist_bl_add_head_valid(h, n))
+	if (!__hlist_bl_add_head_valid(n, h))
 		return;
 
 	/* don't need hlist_bl_first_rcu because we're under lock */
lib/list_debug.c +28 -0
index b3560de4accc..9591fa6c9337 100644
@@ -186,3 +186,31 @@ bool __hlist_nulls_del_valid(struct hlist_nulls_node *node)
 	return true;
 }
 EXPORT_SYMBOL(__hlist_nulls_del_valid);
+
+bool __hlist_bl_add_head_valid(struct hlist_bl_node *new,
+			       struct hlist_bl_head *head)
+{
+	unsigned long hlock = (unsigned long)head->first & LIST_BL_LOCKMASK;
+	unsigned long nlock = (unsigned long)new & LIST_BL_LOCKMASK;
+
+	return !(CHECK_DATA_CORRUPTION(nlock,
+			"hlist_bl_add_head: node is locked\n") ||
+		 CHECK_DATA_CORRUPTION(hlock != LIST_BL_LOCKMASK,
+			"hlist_bl_add_head: head is unlocked\n"));
+}
+EXPORT_SYMBOL(__hlist_bl_add_head_valid);
+
+bool __hlist_bl_del_valid(struct hlist_bl_node *node)
+{
+	unsigned long nlock = (unsigned long)node & LIST_BL_LOCKMASK;
+
+	return !(CHECK_DATA_CORRUPTION(nlock,
+			"hlist_bl_del_valid: node locked") ||
+		 CHECK_DATA_CORRUPTION(node->next == LIST_POISON1,
+			"hlist_bl_del corruption, %px->next is LIST_POISON1 (%px)\n",
+			node, LIST_POISON1) ||
+		 CHECK_DATA_CORRUPTION(node->pprev == LIST_POISON2,
+			"hlist_bl_del corruption, %px->pprev is LIST_POISON2 (%px)\n",
+			node, LIST_POISON2));
+}
+EXPORT_SYMBOL(__hlist_bl_del_valid);
Signature · 1 line
2.20.1
#54 lore raw

RFC PATCH 19/21 list_bl: Extend integrity checking to cover the same cases as 'hlist'

In reply to Will Deacon

The list integrity checks for 'hlist_bl' are missing a number of cases that are covered by other list implementations (e.g. 'hlist'), such as validating 'next' and 'pprev' pointers when adding and deleting nodes.

Extend the list_bl integrity checks to bring them up to the same level as for other list implementations.

Cc Kees Cook <[email protected]>
Cc Paul E. McKenney <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 lib/list_debug.c | 48 ++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 40 insertions(+), 8 deletions(-)
lib/list_debug.c +40 -8
index 9591fa6c9337..3be50b5c8014 100644
@@ -7,6 +7,7 @@
 
 #include <linux/export.h>
 #include <linux/list.h>
+#include <linux/list_bl.h>
 #include <linux/bug.h>
 #include <linux/kernel.h>
 #include <linux/rculist.h>
@@ -190,27 +191,58 @@ EXPORT_SYMBOL(__hlist_nulls_del_valid);
 bool __hlist_bl_add_head_valid(struct hlist_bl_node *new,
 			       struct hlist_bl_head *head)
 {
+	struct hlist_bl_node *first = hlist_bl_first(head);
 	unsigned long hlock = (unsigned long)head->first & LIST_BL_LOCKMASK;
 	unsigned long nlock = (unsigned long)new & LIST_BL_LOCKMASK;
 
-	return !(CHECK_DATA_CORRUPTION(nlock,
+	if (CHECK_DATA_CORRUPTION(nlock,
 			"hlist_bl_add_head: node is locked\n") ||
-		 CHECK_DATA_CORRUPTION(hlock != LIST_BL_LOCKMASK,
-			"hlist_bl_add_head: head is unlocked\n"));
+	    CHECK_DATA_CORRUPTION(hlock != LIST_BL_LOCKMASK,
+			"hlist_bl_add_head: head is unlocked\n"))
+		return false;
+
+	if (CHECK_DATA_CORRUPTION(first && first->pprev != &head->first,
+			"hlist_bl_add_head corruption: first->pprev should be &head->first (%px), but was %px (first=%px)",
+			&head->first, first->pprev, first) ||
+	    CHECK_DATA_CORRUPTION(new == first,
+			"hlist_bl_add_head double add: new (%px) == first (%px)",
+			new, first))
+		return false;
+
+	return true;
 }
 EXPORT_SYMBOL(__hlist_bl_add_head_valid);
 
 bool __hlist_bl_del_valid(struct hlist_bl_node *node)
 {
+	struct hlist_bl_node *prev, *next = node->next;
 	unsigned long nlock = (unsigned long)node & LIST_BL_LOCKMASK;
+	unsigned long pnext;
 
-	return !(CHECK_DATA_CORRUPTION(nlock,
-			"hlist_bl_del_valid: node locked") ||
-		 CHECK_DATA_CORRUPTION(node->next == LIST_POISON1,
+	if (CHECK_DATA_CORRUPTION(nlock,
+			"hlist_bl_del corruption: node is locked") ||
+	    CHECK_DATA_CORRUPTION(next == LIST_POISON1,
 			"hlist_bl_del corruption, %px->next is LIST_POISON1 (%px)\n",
 			node, LIST_POISON1) ||
-		 CHECK_DATA_CORRUPTION(node->pprev == LIST_POISON2,
+	    CHECK_DATA_CORRUPTION(node->pprev == LIST_POISON2,
 			"hlist_bl_del corruption, %px->pprev is LIST_POISON2 (%px)\n",
-			node, LIST_POISON2));
+			node, LIST_POISON2))
+		return false;
+
+	BUILD_BUG_ON(offsetof(struct hlist_bl_node, next) !=
+		     offsetof(struct hlist_bl_head, first));
+	prev = container_of(node->pprev, struct hlist_bl_node, next);
+	pnext = (unsigned long)prev->next & ~LIST_BL_LOCKMASK;
+	if (CHECK_DATA_CORRUPTION((unsigned long)next & LIST_BL_LOCKMASK,
+			"hlist_bl_del_corruption: node->next is locked") ||
+	    CHECK_DATA_CORRUPTION((struct hlist_bl_node *)pnext != node,
+			"hlist_bl_del corruption: prev->next should be %px, but was %lx\n",
+			node, pnext) ||
+	    CHECK_DATA_CORRUPTION(next && next->pprev != &node->next,
+			"hlist_bl_del corruption: next->pprev should be %px, but was %px\n",
+			&node->next, next->pprev))
+		return false;
+
+	return true;
 }
 EXPORT_SYMBOL(__hlist_bl_del_valid);
Signature · 1 line
2.20.1
#55 lore raw

RFC PATCH 20/21 list: Format CHECK_DATA_CORRUPTION error messages consistently

In reply to Will Deacon

The error strings printed when list data corruption is detected are formatted inconsistently.

Satisfy my inner-pedant by consistently using ':' to limit the message from its prefix and drop the terminating full stops where they exist.

---
 lib/list_debug.c | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)
lib/list_debug.c +9 -9
index 3be50b5c8014..00e414508f93 100644
@@ -23,10 +23,10 @@ bool __list_add_valid(struct list_head *new, struct list_head *prev,
 		      struct list_head *next)
 {
 	if (CHECK_DATA_CORRUPTION(next->prev != prev,
-			"list_add corruption. next->prev should be prev (%px), but was %px. (next=%px).\n",
+			"list_add corruption: next->prev should be prev (%px), but was %px (next=%px)\n",
 			prev, next->prev, next) ||
 	    CHECK_DATA_CORRUPTION(prev->next != next,
-			"list_add corruption. prev->next should be next (%px), but was %px. (prev=%px).\n",
+			"list_add corruption: prev->next should be next (%px), but was %px (prev=%px)\n",
 			next, prev->next, prev) ||
 	    CHECK_DATA_CORRUPTION(new == prev || new == next,
 			"list_add double add: new=%px, prev=%px, next=%px.\n",
@@ -45,16 +45,16 @@ bool __list_del_entry_valid(struct list_head *entry)
 	next = entry->next;
 
 	if (CHECK_DATA_CORRUPTION(next == LIST_POISON1,
-			"list_del corruption, %px->next is LIST_POISON1 (%px)\n",
+			"list_del corruption: %px->next is LIST_POISON1 (%px)\n",
 			entry, LIST_POISON1) ||
 	    CHECK_DATA_CORRUPTION(prev == LIST_POISON2,
-			"list_del corruption, %px->prev is LIST_POISON2 (%px)\n",
+			"list_del corruption: %px->prev is LIST_POISON2 (%px)\n",
 			entry, LIST_POISON2) ||
 	    CHECK_DATA_CORRUPTION(prev->next != entry,
-			"list_del corruption. prev->next should be %px, but was %px\n",
+			"list_del corruption: prev->next should be %px, but was %px\n",
 			entry, prev->next) ||
 	    CHECK_DATA_CORRUPTION(next->prev != entry,
-			"list_del corruption. next->prev should be %px, but was %px\n",
+			"list_del corruption: next->prev should be %px, but was %px\n",
 			entry, next->prev))
 		return false;
 
@@ -196,7 +196,7 @@ bool __hlist_bl_add_head_valid(struct hlist_bl_node *new,
 	unsigned long nlock = (unsigned long)new & LIST_BL_LOCKMASK;
 
 	if (CHECK_DATA_CORRUPTION(nlock,
-			"hlist_bl_add_head: node is locked\n") ||
+			"hlist_bl_add_head corruption: node is locked\n") ||
 	    CHECK_DATA_CORRUPTION(hlock != LIST_BL_LOCKMASK,
 			"hlist_bl_add_head: head is unlocked\n"))
 		return false;
@@ -222,10 +222,10 @@ bool __hlist_bl_del_valid(struct hlist_bl_node *node)
 	if (CHECK_DATA_CORRUPTION(nlock,
 			"hlist_bl_del corruption: node is locked") ||
 	    CHECK_DATA_CORRUPTION(next == LIST_POISON1,
-			"hlist_bl_del corruption, %px->next is LIST_POISON1 (%px)\n",
+			"hlist_bl_del corruption: %px->next is LIST_POISON1 (%px)\n",
 			node, LIST_POISON1) ||
 	    CHECK_DATA_CORRUPTION(node->pprev == LIST_POISON2,
-			"hlist_bl_del corruption, %px->pprev is LIST_POISON2 (%px)\n",
+			"hlist_bl_del corruption: %px->pprev is LIST_POISON2 (%px)\n",
 			node, LIST_POISON2))
 		return false;
 
Signature · 1 line
2.20.1
maintainer Reviewed-by on v1 20/21
#56 lore raw

Re: [RFC PATCH 20/21] list: Format CHECK_DATA_CORRUPTION error messages consistently

Quoted 7 lines · Will Deacon

The error strings printed when list data corruption is detected are formatted inconsistently.

Satisfy my inner-pedant by consistently using ':' to limit the message from its prefix and drop the terminating full stops where they exist.

#57 lore raw

RFC PATCH 21/21 lkdtm: Extend list corruption checks

In reply to Will Deacon

Although lkdtm has a couple of simple tests for triggering list corruption, there are plenty of things it doesn't trigger, particularly now that we have forms of integrity checking for other list types.

Extend lkdtm to check a variety of list insertion and deletion routines.

---
 drivers/misc/lkdtm/Makefile             |   1 +
 drivers/misc/lkdtm/bugs.c               |  68 ----
 drivers/misc/lkdtm/core.c               |  31 +-
 drivers/misc/lkdtm/list.c               | 489 ++++++++++++++++++++++++
 drivers/misc/lkdtm/lkdtm.h              |  33 +-
 tools/testing/selftests/lkdtm/tests.txt |  31 +-
 6 files changed, 579 insertions(+), 74 deletions(-)
 create mode 100644 drivers/misc/lkdtm/list.c
drivers/misc/lkdtm/Makefile +1 -0
index c70b3822013f..833c6f7c78a3 100644
@@ -10,6 +10,7 @@ lkdtm-$(CONFIG_LKDTM)		+= rodata_objcopy.o
 lkdtm-$(CONFIG_LKDTM)		+= usercopy.o
 lkdtm-$(CONFIG_LKDTM)		+= stackleak.o
 lkdtm-$(CONFIG_LKDTM)		+= cfi.o
+lkdtm-$(CONFIG_LKDTM)		+= list.o
 
 KASAN_SANITIZE_stackleak.o	:= n
 KCOV_INSTRUMENT_rodata.o	:= n
drivers/misc/lkdtm/bugs.c +0 -68

86 lines not on this page · raw message

drivers/misc/lkdtm/core.c +29 -2
index ee0d6e721441..28aace88474f 100644
@@ -110,8 +110,6 @@ static const struct crashtype crashtypes[] = {
 	CRASHTYPE(EXHAUST_STACK),
 	CRASHTYPE(CORRUPT_STACK),
 	CRASHTYPE(CORRUPT_STACK_STRONG),
-	CRASHTYPE(CORRUPT_LIST_ADD),
-	CRASHTYPE(CORRUPT_LIST_DEL),
 	CRASHTYPE(CORRUPT_USER_DS),
 	CRASHTYPE(STACK_GUARD_PAGE_LEADING),
 	CRASHTYPE(STACK_GUARD_PAGE_TRAILING),
@@ -174,6 +172,35 @@ static const struct crashtype crashtypes[] = {
 #ifdef CONFIG_X86_32
 	CRASHTYPE(DOUBLE_FAULT),
 #endif
+	CRASHTYPE(LIST_ADD_NEXT_CORRUPTION),
+	CRASHTYPE(LIST_ADD_PREV_CORRUPTION),
+	CRASHTYPE(LIST_ADD_TWICE),
+	CRASHTYPE(LIST_DEL_NEXT_CORRUPTION),
+	CRASHTYPE(LIST_DEL_PREV_CORRUPTION),
+	CRASHTYPE(LIST_DEL_TWICE),
+	CRASHTYPE(HLIST_ADD_HEAD_CORRUPTION),
+	CRASHTYPE(HLIST_ADD_HEAD_TWICE),
+	CRASHTYPE(HLIST_ADD_BEFORE_CORRUPTION),
+	CRASHTYPE(HLIST_ADD_BEFORE_TWICE),
+	CRASHTYPE(HLIST_ADD_BEHIND_CORRUPTION),
+	CRASHTYPE(HLIST_ADD_BEHIND_TWICE),
+	CRASHTYPE(HLIST_DEL_PREV_CORRUPTION),
+	CRASHTYPE(HLIST_DEL_NEXT_CORRUPTION),
+	CRASHTYPE(HLIST_DEL_TWICE),
+	CRASHTYPE(HLIST_NULLS_ADD_HEAD_CORRUPTION),
+	CRASHTYPE(HLIST_NULLS_ADD_HEAD_TWICE),
+	CRASHTYPE(HLIST_NULLS_DEL_PREV_CORRUPTION),
+	CRASHTYPE(HLIST_NULLS_DEL_NEXT_CORRUPTION),
+	CRASHTYPE(HLIST_NULLS_DEL_TWICE),
+	CRASHTYPE(HLIST_BL_ADD_HEAD_UNLOCKED),
+	CRASHTYPE(HLIST_BL_ADD_HEAD_NODE_LOCKED),
+	CRASHTYPE(HLIST_BL_ADD_HEAD_CORRUPTION),
+	CRASHTYPE(HLIST_BL_ADD_HEAD_TWICE),
+	CRASHTYPE(HLIST_BL_DEL_NODE_LOCKED),
+	CRASHTYPE(HLIST_BL_DEL_NEXT_LOCKED),
+	CRASHTYPE(HLIST_BL_DEL_PREV_CORRUPTION),
+	CRASHTYPE(HLIST_BL_DEL_NEXT_CORRUPTION),
+	CRASHTYPE(HLIST_BL_DEL_TWICE),
 };
 
 
drivers/misc/lkdtm/list.c new file +489 -0

489 lines not on this page · raw message

drivers/misc/lkdtm/lkdtm.h +31 -2
index c56d23e37643..b5acce183473 100644
@@ -22,8 +22,6 @@ void lkdtm_SOFTLOCKUP(void);
 void lkdtm_HARDLOCKUP(void);
 void lkdtm_SPINLOCKUP(void);
 void lkdtm_HUNG_TASK(void);
-void lkdtm_CORRUPT_LIST_ADD(void);
-void lkdtm_CORRUPT_LIST_DEL(void);
 void lkdtm_CORRUPT_USER_DS(void);
 void lkdtm_STACK_GUARD_PAGE_LEADING(void);
 void lkdtm_STACK_GUARD_PAGE_TRAILING(void);
@@ -102,4 +100,35 @@ void lkdtm_STACKLEAK_ERASING(void);
 /* cfi.c */
 void lkdtm_CFI_FORWARD_PROTO(void);
 
+/* list.c */
+void lkdtm_LIST_ADD_NEXT_CORRUPTION(void);
+void lkdtm_LIST_ADD_PREV_CORRUPTION(void);
+void lkdtm_LIST_ADD_TWICE(void);
+void lkdtm_LIST_DEL_NEXT_CORRUPTION(void);
+void lkdtm_LIST_DEL_PREV_CORRUPTION(void);
+void lkdtm_LIST_DEL_TWICE(void);
+void lkdtm_HLIST_ADD_HEAD_CORRUPTION(void);
+void lkdtm_HLIST_ADD_HEAD_TWICE(void);
+void lkdtm_HLIST_ADD_BEFORE_CORRUPTION(void);
+void lkdtm_HLIST_ADD_BEFORE_TWICE(void);
+void lkdtm_HLIST_ADD_BEHIND_CORRUPTION(void);
+void lkdtm_HLIST_ADD_BEHIND_TWICE(void);
+void lkdtm_HLIST_DEL_PREV_CORRUPTION(void);
+void lkdtm_HLIST_DEL_NEXT_CORRUPTION(void);
+void lkdtm_HLIST_DEL_TWICE(void);
+void lkdtm_HLIST_NULLS_ADD_HEAD_CORRUPTION(void);
+void lkdtm_HLIST_NULLS_ADD_HEAD_TWICE(void);
+void lkdtm_HLIST_NULLS_DEL_PREV_CORRUPTION(void);
+void lkdtm_HLIST_NULLS_DEL_NEXT_CORRUPTION(void);
+void lkdtm_HLIST_NULLS_DEL_TWICE(void);
+void lkdtm_HLIST_BL_ADD_HEAD_UNLOCKED(void);
+void lkdtm_HLIST_BL_ADD_HEAD_NODE_LOCKED(void);
+void lkdtm_HLIST_BL_ADD_HEAD_CORRUPTION(void);
+void lkdtm_HLIST_BL_ADD_HEAD_TWICE(void);
+void lkdtm_HLIST_BL_DEL_NODE_LOCKED(void);
+void lkdtm_HLIST_BL_DEL_NEXT_LOCKED(void);
+void lkdtm_HLIST_BL_DEL_PREV_CORRUPTION(void);
+void lkdtm_HLIST_BL_DEL_NEXT_CORRUPTION(void);
+void lkdtm_HLIST_BL_DEL_TWICE(void);
+
 #endif
tools/testing/selftests/lkdtm/tests.txt +29 -2
index 92ca32143ae5..93901506a72f 100644
@@ -7,8 +7,6 @@ EXCEPTION
 #EXHAUST_STACK Corrupts memory on failure
 #CORRUPT_STACK Crashes entire system on success
 #CORRUPT_STACK_STRONG Crashes entire system on success
-CORRUPT_LIST_ADD list_add corruption
-CORRUPT_LIST_DEL list_del corruption
 CORRUPT_USER_DS Invalid address limit on user-mode return
 STACK_GUARD_PAGE_LEADING
 STACK_GUARD_PAGE_TRAILING
@@ -69,3 +67,32 @@ USERCOPY_KERNEL
 USERCOPY_KERNEL_DS
 STACKLEAK_ERASING OK: the rest of the thread stack is properly erased
 CFI_FORWARD_PROTO
+LIST_ADD_NEXT_CORRUPTION list_add corruption: next->prev should be prev
+LIST_ADD_PREV_CORRUPTION list_add corruption: prev->next should be next
+LIST_ADD_TWICE list_add double add:
+LIST_DEL_NEXT_CORRUPTION list_del corruption: next->prev should be
+LIST_DEL_PREV_CORRUPTION list_del corruption: prev->next should be
+LIST_DEL_TWICE list_del corruption:
+HLIST_ADD_HEAD_CORRUPTION hlist_add_head corruption: first->pprev should be &head->first
+HLIST_ADD_HEAD_TWICE hlist_add_head double add:
+HLIST_ADD_BEFORE_CORRUPTION hlist_add corruption: prev->next should be next
+HLIST_ADD_BEFORE_TWICE hlist_add double add:
+HLIST_ADD_BEHIND_CORRUPTION hlist_add corruption: next->pprev should be &prev->next
+HLIST_ADD_BEHIND_TWICE hlist_add double add:
+HLIST_DEL_PREV_CORRUPTION hlist_del corruption: prev->next should be
+HLIST_DEL_NEXT_CORRUPTION hlist_del corruption: next->pprev should be
+HLIST_DEL_TWICE hlist_del corruption:
+HLIST_NULLS_ADD_HEAD_CORRUPTION hlist_nulls_add_head corruption: first->pprev should be &head->first
+HLIST_NULLS_ADD_HEAD_TWICE hlist_nulls_add_head double add:
+HLIST_NULLS_DEL_PREV_CORRUPTION hlist_nulls_del corruption: prev->next should be
+HLIST_NULLS_DEL_NEXT_CORRUPTION hlist_nulls_del corruption: next->pprev should be
+HLIST_NULLS_DEL_TWICE hlist_nulls_del corruption:
+HLIST_BL_ADD_HEAD_UNLOCKED hlist_bl_add_head: head is unlocked
+#HLIST_BL_ADD_HEAD_NODE_LOCKED Corrupts memory on failure
+HLIST_BL_ADD_HEAD_CORRUPTION hlist_bl_add_head corruption: first->pprev should be &head->first
+HLIST_BL_ADD_HEAD_TWICE hlist_bl_add_head double add:
+#HLIST_BL_DEL_NODE_LOCKED Corrupts memory on failure
+#HLIST_BL_DEL_NEXT_LOCKED Corrupts memory on failure
+HLIST_BL_DEL_PREV_CORRUPTION hlist_bl_del corruption: prev->next should be
+HLIST_BL_DEL_NEXT_CORRUPTION hlist_bl_del corruption: next->pprev should be
+HLIST_BL_DEL_TWICE hlist_bl_del corruption:
Signature · 1 line
2.20.1