[Mesa-dev] [PATCH 1/5] compiler: guard list iteration macros against undefined behavior

[Nicolai Hähnle]

From: Nicolai Hähnle <nicolai.haehnle at amd.com>

The old iteration casts sentinel nodes (which are mere exec_nodes) into
whatever type we're looping over, which leads to badness (in fact, gcc's
undefined behaviour sanitizer crashes while trying to verify that we have
the correct type at hand).

These modified looping constructs postpone the cast until its correctness
has been established. The odd two-level loop construct is used to be able
to define variables of different types, and the __sentinel variable
ensures that the outer loop is only run once. gcc is able to optimize the
outer loop away in the cases I have examined.
---
 src/compiler/glsl/list.h | 109 ++++++++++++++++++++++++++++-------------------
 1 file changed, 64 insertions(+), 45 deletions(-)

diff --git a/src/compiler/glsl/list.h b/src/compiler/glsl/list.h
index a1c4d82..8da9514 100644
--- a/src/compiler/glsl/list.h
+++ b/src/compiler/glsl/list.h
@@ -621,36 +621,55 @@ inline void exec_node::insert_before(exec_list *before)
 }
 #endif
 
-#define foreach_in_list(__type, __inst, __list)      \
-   for (__type *(__inst) = (__type *)(__list)->head; \
-        !(__inst)->is_tail_sentinel();               \
-        (__inst) = (__type *)(__inst)->next)
-
-#define foreach_in_list_reverse(__type, __inst, __list)   \
-   for (__type *(__inst) = (__type *)(__list)->tail_pred; \
-        !(__inst)->is_head_sentinel();                    \
-        (__inst) = (__type *)(__inst)->prev)
+/* The somewhat odd-looking multi-loop construct here is to avoid casting
+ * sentinel nodes, which would be undefined behavior (which is indeed flagged /
+ * leads to crashes with gcc's ubsan).
+ */
+#define foreach_in_list(__type, __node, __list)      \
+   for (__type *(__node), **__flag = &(__node);      \
+        __flag; __flag = NULL)                       \
+      for (struct exec_node *__cur = (__list)->head; \
+           !__cur->is_tail_sentinel() &&             \
+           (((__node) = (__type *) __cur) || true);  \
+           __cur = __cur->next)                      \
+
+#define foreach_in_list_reverse(__type, __node, __list)   \
+   for (__type *(__node), **__flag = &(__node);           \
+        __flag; __flag = NULL)                            \
+      for (struct exec_node *__cur = (__list)->tail_pred; \
+           !__cur->is_head_sentinel() &&                  \
+           (((__node) = (__type *) __cur) || true);       \
+           __cur = __cur->prev)
 
 /**
  * This version is safe even if the current node is removed.
  */ 
 #define foreach_in_list_safe(__type, __node, __list) \
-   for (__type *__node = (__type *)(__list)->head,   \
-               *__next = (__type *)__node->next;     \
-        __next != NULL;                              \
-        __node = __next, __next = (__type *)__next->next)
+   for (__type *(__node), **__flag = &(__node);      \
+        __flag; __flag = NULL)                       \
+      for (struct exec_node *__cur = (__list)->head, \
+                            *__next = __cur->next;   \
+           __next != NULL &&                         \
+           (((__node) = (__type *) __cur) || true);  \
+           __cur = __next, __next = __next->next)
 
 #define foreach_in_list_reverse_safe(__type, __node, __list) \
-   for (__type *__node = (__type *)(__list)->tail_pred,      \
-               *__prev = (__type *)__node->prev;             \
-        __prev != NULL;                                      \
-        __node = __prev, __prev = (__type *)__prev->prev)
-
-#define foreach_in_list_use_after(__type, __inst, __list) \
-   __type *(__inst);                                      \
-   for ((__inst) = (__type *)(__list)->head;              \
-        !(__inst)->is_tail_sentinel();                    \
-        (__inst) = (__type *)(__inst)->next)
+   for (__type *(__node), **__flag = &(__node);              \
+        __flag; __flag = NULL)                               \
+      for (struct exec_node *__cur = (__list)->tail_pred,    \
+                            *__prev = __cur->prev;           \
+           __prev != NULL &&                                 \
+           (((__node) = (__type *) __cur) || true);          \
+           __cur = __prev, __prev = __prev->prev)
+
+#define foreach_in_list_use_after(__type, __node, __list) \
+   __type *(__node);                                      \
+   for (__type **__flag = &(__node);                      \
+        __flag; __flag = NULL)                            \
+      for (struct exec_node *__cur = (__list)->head;      \
+           !__cur->is_tail_sentinel() &&                  \
+           (((__node) = (__type *) __cur) || true);       \
+           __cur = __cur->next)
 /**
  * Iterate through two lists at once.  Stops at the end of the shorter list.
  *
@@ -668,33 +687,33 @@ inline void exec_node::insert_before(exec_list *before)
           __next2 = __next2->next)
 
 #define foreach_list_typed(__type, __node, __field, __list)		\
-   for (__type * __node =						\
-	   exec_node_data(__type, (__list)->head, __field);		\
-	(__node)->__field.next != NULL; 				\
-	(__node) = exec_node_data(__type, (__node)->__field.next, __field))
+   for (__type *(__node), **__flag = &(__node); __flag; __flag = NULL)    \
+      for (struct exec_node * __cur = (__list)->head;                     \
+           __cur->next != NULL &&                                         \
+           (((__node) = exec_node_data(__type, __cur, __field)) || true); \
+           __cur = __cur->next)
 
 #define foreach_list_typed_reverse(__type, __node, __field, __list)        \
-   for (__type * __node =                                                \
-           exec_node_data(__type, (__list)->tail_pred, __field);        \
-        (__node)->__field.prev != NULL;                                 \
-        (__node) = exec_node_data(__type, (__node)->__field.prev, __field))
+   for (__type *(__node), **__flag = &(__node); __flag; __flag = NULL)     \
+      for (struct exec_node * __cur = (__list)->tail_pred;                 \
+           __cur->prev != NULL &&                                          \
+           (((__node) = exec_node_data(__type, __cur, __field)) || true);  \
+           __cur = __cur->prev)
 
 #define foreach_list_typed_safe(__type, __node, __field, __list)           \
-   for (__type * __node =                                                  \
-           exec_node_data(__type, (__list)->head, __field),                \
-               * __next =                                                  \
-           exec_node_data(__type, (__node)->__field.next, __field);        \
-        (__node)->__field.next != NULL;                                    \
-        __node = __next, __next =                                          \
-           exec_node_data(__type, (__next)->__field.next, __field))
+   for (__type *(__node), **__flag = &(__node); __flag; __flag = NULL)     \
+      for (struct exec_node * __cur = (__list)->head,                      \
+                            * __next = __cur->next;                        \
+           __next != NULL &&                                               \
+           (((__node) = exec_node_data(__type, __cur, __field)) || true);  \
+           __cur = __next, __next = __next->next)
 
 #define foreach_list_typed_reverse_safe(__type, __node, __field, __list)   \
-   for (__type * __node =                                                  \
-           exec_node_data(__type, (__list)->tail_pred, __field),           \
-               * __prev =                                                  \
-           exec_node_data(__type, (__node)->__field.prev, __field);        \
-        (__node)->__field.prev != NULL;                                    \
-        __node = __prev, __prev =                                          \
-           exec_node_data(__type, (__prev)->__field.prev, __field))
+   for (__type *(__node), **__flag = &(__node); __flag; __flag = NULL)     \
+      for (struct exec_node * __cur = (__list)->tail_pred,                 \
+                            * __prev = __cur->prev;                        \
+           __prev != NULL &&                                               \
+           (((__node) = exec_node_data(__type, __cur, __field)) || true);  \
+           __cur = __prev, __prev = __prev->prev)
 
 #endif /* LIST_CONTAINER_H */
-- 
2.7.4