Re: [Mesa-dev] [PATCH 3/9] compiler: guard list iteration macros against undefined behavior

[Nicolai Hähnle]

On 10.05.2016 14:17, Ian Romanick wrote:
On 04/30/2016 12:24 AM, Nicolai Hähnle wrote:
From: Nicolai Hähnle <nicolai.haeh...@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).

Bwah.  I was going to suggest a different method, but I found that my
other ideas wouldn't work for various reasons.

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
                                                   ^^^^^^^^^^
You mean __flag, right?

Yes, sorry.

ensures that the outer loop is only run once. gcc is able to optimize the
outer loop away in the cases I have examined.

Does 'size' report any difference on the resulting .so?

I just ran the experiment on a build with -g -O2 
-fno-omit-frame-pointer, and the results are (first line before the 
series, each subsequent line after the next patch in the pure compiler 
series that I sent out):

   text    data     bss     dec     hex filename
7314874  229656 2051744 9596274  926d72 ./lib/gallium/radeonsi_dri.so
7310166  229656 2051744 9591566  925b0e ./lib/gallium/radeonsi_dri.so
7310214  229656 2051744 9591614  925b3e ./lib/gallium/radeonsi_dri.so
7310150  229656 2051744 9591550  925afe ./lib/gallium/radeonsi_dri.so
7310134  229656 2051744 9591534  925aee ./lib/gallium/radeonsi_dri.so
7310134  229656 2051744 9591534  925aee ./lib/gallium/radeonsi_dri.so

I did not expect that! Turns out that there's some arithmetic involved 
in the casts - apparently the compiler decides to put the VMT before the 
exec_node part - and that could explain the change in code size.

I'm sending out a v2 of this patch in a moment - Shawn pointed out a 
compiler error in the Intel driver caused by someone directly accessing 
the __next variable, tsk tsk! ;-)

Cheers,
Nicolai

---
  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 */


_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
https://lists.freedesktop.org/mailman/listinfo/mesa-dev