Clang: avoid undefined behavior in llist iterators
cover Clang: avoid undefined behavior in llist iterators
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(-)
Signature · 1 line
2.8.0.rc3.226.g39d4020
PATCH 1/2 include/linux: provide a safe version of container_of()
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().
---
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(+)
include/linux/kernel.h +15 -0
@@ -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
Signature · 1 line
2.8.0.rc3.226.g39d4020
PATCH 2/2 llist: introduce llist_entry_safe()
In reply to Alexander PotapenkoCurrently 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.
--- include/linux/llist.h | 26 +++++++++++++++++++------- 1 file changed, 19 insertions(+), 7 deletions(-)
include/linux/llist.h +19 -7
@@ -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)/**
Signature · 1 line
2.8.0.rc3.226.g39d4020