[PATCH 0/2] Clang: avoid undefined behavior in llist iterators

[PATCH 0/2] Clang: avoid undefined behavior in llist iterators

[Alexander Potapenko]

This patch set fixes problems with pointer arithmetics overflow in
llist iterators, llist_for_each_entry() and llist_for_each_entry_safe().
Clang turns those macros into infinite loops, because they're operating
with "negative" pointers.

As a follow-up it may make sense to convert other uses of llist_entry()
to llist_entry_safe(), or even replace uses of container_of() with
container_of_safe().

Alexander Potapenko (2):
  include/linux: provide a safe version of container_of()
  llist: introduce llist_entry_safe()

 include/linux/kernel.h | 15 +++++++++++++++
 include/linux/llist.h  | 26 +++++++++++++++++++-------
 2 files changed, 34 insertions(+), 7 deletions(-)

-- 
2.8.0.rc3.226.g39d4020

[PATCH 1/2] include/linux: provide a safe version of container_of()

[Alexander Potapenko]

Some code relies on "negative" (i.e. too big) pointer values being
returned by container_of() when its first argument is NULL. But doing
so breaks the compiler's assumptions that pointer arithmetic never
overflows.

container_of_safe() checks its arguments and returns NULL in the case
the member offset within the container is greater than the pointer to
the member, otherwise it returns the result of container_of().

Signed-off-by: Alexander Potapenko <glider@google.com>
---
Note that checkpatch.pl reports whitespace problems in this patch, but
the diff is consistent with the rest of the file.
---
 include/linux/kernel.h | 15 +++++++++++++++
 1 file changed, 15 insertions(+)

diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index d96a611..820b134 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -831,6 +831,21 @@ static inline void ftrace_dump(enum ftrace_dump_mode oops_dump_mode) { }
 	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
 	(type *)( (char *)__mptr - offsetof(type,member) );})
 
+/**
+ * container_of_safe - safe version of container_of
+ * @ptr:	the pointer to the member.
+ * @type:	the type of the container struct this is embedded in.
+ * @member:	the name of the member within the struct.
+ *
+ * In the case the value of @ptr is smaller than the offset of @member within
+ * @type, return 0.
+ */
+#define container_of_safe(ptr, type, member) ({			\
+	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
+        (size_t)__mptr >= offsetof(type,member) ?		\
+	(type *)( (char *)__mptr - offsetof(type,member) ) : (type *)0 ;})
+
+
 /* Rebuild everything on CONFIG_FTRACE_MCOUNT_RECORD */
 #ifdef CONFIG_FTRACE_MCOUNT_RECORD
 # define REBUILD_DUE_TO_FTRACE_MCOUNT_RECORD
-- 
2.8.0.rc3.226.g39d4020

[PATCH 2/2] llist: introduce llist_entry_safe()

[Alexander Potapenko]

Currently llist_for_each_entry() and llist_for_each_entry_safe() iterate
until &pos->member != NULL. But when building the kernel with Clang, the
compiler assumes &pos->member cannot be NULL if the member's offset is
greater than 0. Therefore the loop condition is always true, and the
loops become infinite.

To work around this, introduce llist_entry_safe(), which returns NULL
for NULL pointers, and additionally check that pos is not NULL in the
list iterators before dereferencing it.

Signed-off-by: Alexander Potapenko <glider@google.com>
---
 include/linux/llist.h | 26 +++++++++++++++++++-------
 1 file changed, 19 insertions(+), 7 deletions(-)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index fd4ca0b..e17ae8a 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -88,6 +88,16 @@ static inline void init_llist_head(struct llist_head *list)
 	container_of(ptr, type, member)
 
 /**
+ * llist_entry_safe - get the struct of this entry without overflowing
+ * @ptr:	the &struct llist_node pointer.
+ * @type:	the type of the struct this is embedded in.
+ * @member:	the name of the llist_node within the struct.
+ */
+#define llist_entry_safe(ptr, type, member)		\
+	container_of_safe(ptr, type, member)
+
+
+/**
  * llist_for_each - iterate over some deleted entries of a lock-less list
  * @pos:	the &struct llist_node to use as a loop cursor
  * @node:	the first entry of deleted list entries
@@ -120,9 +130,10 @@ static inline void init_llist_head(struct llist_head *list)
  * reverse the order by yourself before traversing.
  */
 #define llist_for_each_entry(pos, node, member)				\
-	for ((pos) = llist_entry((node), typeof(*(pos)), member);	\
-	     &(pos)->member != NULL;					\
-	     (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
+	for ((pos) = llist_entry_safe((node), typeof(*(pos)), member);	\
+	     pos != NULL && &(pos)->member != NULL;			\
+	     (pos) = llist_entry_safe((pos)->member.next, \
+					typeof(*(pos)), member))
 
 /**
  * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type
@@ -141,10 +152,11 @@ static inline void init_llist_head(struct llist_head *list)
  * you want to traverse from the oldest to the newest, you must
  * reverse the order by yourself before traversing.
  */
-#define llist_for_each_entry_safe(pos, n, node, member)			       \
-	for (pos = llist_entry((node), typeof(*pos), member);		       \
-	     &pos->member != NULL &&					       \
-	        (n = llist_entry(pos->member.next, typeof(*n), member), true); \
+#define llist_for_each_entry_safe(pos, n, node, member)			     \
+	for (pos = llist_entry_safe((node), typeof(*pos), member);	     \
+	     pos != NULL && &pos->member != NULL &&			     \
+		(n = llist_entry_safe(pos->member.next, typeof(*n), member), \
+		 true); \
 	     pos = n)
 
 /**
-- 
2.8.0.rc3.226.g39d4020