glsl/list: Fix undefined behaviour of foreach_* macros

These macros produced a lot of errors with ubsan preventing us from
expanding the ubsan coverage on CIs.

C++ spec has such clause:

 "If the prvalue of type "pointer to cv1 B" points to a B that is
  actually a subobject of an object of type D, the resulting pointer
  points to the enclosing object of type D. Otherwise, the result
  of the cast is undefined."

Ubsan error example:

 ../src/compiler/glsl/builtin_functions.cpp:4945:4: runtime error: downcast of address 0x559b926abb50 which does not point to an object of type 'ir_instruction'
 0x559b926abb50: note: object has invalid vptr
  9b 55 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  58 ba 6a 92 9b 55 00 00  01 00 00 00
               ^~~~~~~~~~~~~~~~~~~~~~~
               invalid vptr
     #0 0x559b914dbe1a in call ../src/compiler/glsl/builtin_functions.cpp:4945

Signed-off-by: Danylo Piliaiev <[email protected]>
Acked-by: Matt Turner <[email protected]>
Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4129>

3 files changed, 352 insertions, 60 deletions

diff --git a/src/compiler/glsl/list.h b/src/compiler/glsl/list.h
index c80f776ae16..9153d07cb9a 100644
--- a/src/compiler/glsl/list.h
+++ b/src/compiler/glsl/list.h
@@ -679,36 +679,44 @@ inline void exec_node::insert_before(exec_list *before)
 }
 #endif
 
-#define foreach_in_list(__type, __inst, __list)      \
-   for (__type *__inst = (__type *)(__list)->head_sentinel.next; \
-        !(__inst)->is_tail_sentinel();               \
-        (__inst) = (__type *)(__inst)->next)
+#define exec_node_typed_forward(__node, __type) \
+   (!exec_node_is_tail_sentinel(__node) ? (__type) (__node) : NULL)
 
-#define foreach_in_list_reverse(__type, __inst, __list)   \
-   for (__type *__inst = (__type *)(__list)->tail_sentinel.prev; \
-        !(__inst)->is_head_sentinel();                    \
-        (__inst) = (__type *)(__inst)->prev)
+#define exec_node_typed_backward(__node, __type) \
+   (!exec_node_is_head_sentinel(__node) ? (__type) (__node) : NULL)
+
+#define foreach_in_list(__type, __inst, __list)                                           \
+   for (__type *__inst = exec_node_typed_forward((__list)->head_sentinel.next, __type *); \
+        (__inst) != NULL;                                                                 \
+        (__inst) = exec_node_typed_forward((__inst)->next, __type *))
+
+#define foreach_in_list_reverse(__type, __inst, __list)                                      \
+   for (__type *__inst = exec_node_typed_backward((__list)->tail_sentinel.prev, __type *);   \
+        (__inst) != NULL;                                                                    \
+        (__inst) = exec_node_typed_backward((__inst)->prev, __type *))
 
 /**
  * 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_sentinel.next,   \
-               *__next = (__type *)__node->next;     \
-        __next != NULL;                              \
-        __node = __next, __next = (__type *)__next->next)
-
-#define foreach_in_list_reverse_safe(__type, __node, __list) \
-   for (__type *__node = (__type *)(__list)->tail_sentinel.prev,      \
-               *__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_sentinel.next; \
-        !(__inst)->is_tail_sentinel();                    \
-        (__inst) = (__type *)(__inst)->next)
+ */
+
+#define foreach_in_list_safe(__type, __node, __list)                                                              \
+   for (__type *__node = exec_node_typed_forward((__list)->head_sentinel.next, __type *),                         \
+               *__next = (__node) ? exec_node_typed_forward((__list)->head_sentinel.next->next, __type *) : NULL; \
+        (__node) != NULL;                                                                                         \
+        (__node) = __next, __next = __next ? exec_node_typed_forward(__next->next, __type *) : NULL)
+
+#define foreach_in_list_reverse_safe(__type, __node, __list)                                                        \
+   for (__type *__node = exec_node_typed_backward((__list)->tail_sentinel.prev, __type *),                          \
+               *__prev = (__node) ? exec_node_typed_backward((__list)->tail_sentinel.prev->prev, __type *) : NULL;  \
+        (__node) != NULL;                                                                                           \
+        (__node) = __prev, __prev = __prev ? exec_node_typed_backward(__prev->prev, __type *) : NULL)
+
+#define foreach_in_list_use_after(__type, __inst, __list)                           \
+   __type *__inst;                                                                  \
+   for ((__inst) = exec_node_typed_forward((__list)->head_sentinel.next, __type *); \
+        (__inst) != NULL;                                                           \
+        (__inst) = exec_node_typed_forward((__inst)->next, __type *))
+
 /**
  * Iterate through two lists at once.  Stops at the end of the shorter list.
  *
@@ -725,39 +733,45 @@ inline void exec_node::insert_before(exec_list *before)
           __next1 = __next1->next,                            \
           __next2 = __next2->next)
 
-#define foreach_list_typed(__type, __node, __field, __list)		\
-   for (__type * __node =						\
-         exec_node_data(__type, (__list)->head_sentinel.next, __field); \
-	(__node)->__field.next != NULL; 				\
-	(__node) = exec_node_data(__type, (__node)->__field.next, __field))
-
-#define foreach_list_typed_from(__type, __node, __field, __list, __start)  \
-   for (__type * __node = exec_node_data(__type, (__start), __field);      \
-	(__node)->__field.next != NULL;                                    \
-	(__node) = exec_node_data(__type, (__node)->__field.next, __field))
-
-#define foreach_list_typed_reverse(__type, __node, __field, __list)        \
-   for (__type * __node =                                                \
-           exec_node_data(__type, (__list)->tail_sentinel.prev, __field);  \
-        (__node)->__field.prev != NULL;                                 \
-        (__node) = exec_node_data(__type, (__node)->__field.prev, __field))
-
-#define foreach_list_typed_safe(__type, __node, __field, __list)           \
-   for (__type * __node =                                                  \
-           exec_node_data(__type, (__list)->head_sentinel.next, __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))
-
-#define foreach_list_typed_reverse_safe(__type, __node, __field, __list)   \
-   for (__type * __node =                                                  \
-           exec_node_data(__type, (__list)->tail_sentinel.prev, __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))
+#define exec_node_data_forward(type, node, field) \
+   (!exec_node_is_tail_sentinel(node) ? exec_node_data(type, node, field) : NULL)
+
+#define exec_node_data_backward(type, node, field) \
+   (!exec_node_is_head_sentinel(node) ? exec_node_data(type, node, field) : NULL)
+
+#define foreach_list_typed(__type, __node, __field, __list)                     \
+   for (__type * __node =                                                       \
+         exec_node_data_forward(__type, (__list)->head_sentinel.next, __field); \
+   (__node) != NULL;                                                            \
+   (__node) = exec_node_data_forward(__type, (__node)->__field.next, __field))
+
+#define foreach_list_typed_from(__type, __node, __field, __list, __start)        \
+   for (__type * __node = exec_node_data_forward(__type, (__start), __field);    \
+   (__node) != NULL;                                                             \
+   (__node) = exec_node_data_forward(__type, (__node)->__field.next, __field))
+
+#define foreach_list_typed_reverse(__type, __node, __field, __list)                 \
+   for (__type * __node =                                                           \
+           exec_node_data_backward(__type, (__list)->tail_sentinel.prev, __field);  \
+        (__node) != NULL;                                                           \
+        (__node) = exec_node_data_backward(__type, (__node)->__field.prev, __field))
+
+#define foreach_list_typed_safe(__type, __node, __field, __list)                    \
+   for (__type * __node =                                                           \
+           exec_node_data_forward(__type, (__list)->head_sentinel.next, __field),   \
+               * __next = (__node) ?                                                \
+           exec_node_data_forward(__type, (__node)->__field.next, __field) : NULL;  \
+        (__node) != NULL;                                                           \
+        (__node) = __next, __next = (__next && (__next)->__field.next) ?            \
+           exec_node_data_forward(__type, (__next)->__field.next, __field) : NULL)
+
+#define foreach_list_typed_reverse_safe(__type, __node, __field, __list)            \
+   for (__type * __node =                                                           \
+           exec_node_data_backward(__type, (__list)->tail_sentinel.prev, __field),  \
+               * __prev = (__node) ?                                                \
+           exec_node_data_backward(__type, (__node)->__field.prev, __field) : NULL; \
+        (__node) != NULL;                                                           \
+        (__node) = __prev, __prev = (__prev && (__prev)->__field.prev) ?            \
+           exec_node_data_backward(__type, (__prev)->__field.prev, __field) : NULL)
 
 #endif /* LIST_CONTAINER_H */
diff --git a/src/compiler/glsl/tests/list_iterators.cpp b/src/compiler/glsl/tests/list_iterators.cpp
new file mode 100644
index 00000000000..c68f85b6436
--- /dev/null
+++ b/src/compiler/glsl/tests/list_iterators.cpp
@@ -0,0 +1,265 @@
+/*
+ * Copyright © 2020 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+#include <gtest/gtest.h>
+
+#include "list.h"
+
+class test_node_inherite : public exec_node  {
+public:
+   uint32_t value;
+
+   virtual ~test_node_inherite() = default;
+};
+
+class list_iterators_node_inherite : public ::testing::TestWithParam<size_t> {
+public:
+   virtual void SetUp();
+   virtual void TearDown();
+
+   void *mem_ctx;
+
+   exec_list node_list;
+};
+
+void
+list_iterators_node_inherite::SetUp()
+{
+   mem_ctx = ralloc_context(NULL);
+
+   exec_list_make_empty(&node_list);
+
+   for (size_t i = 0; i < GetParam(); i++) {
+      test_node_inherite *node = new(mem_ctx) test_node_inherite();
+      node->value = i;
+      exec_list_push_tail(&node_list, node);
+   }
+}
+
+void
+list_iterators_node_inherite::TearDown()
+{
+   exec_list_make_empty(&node_list);
+
+   ralloc_free(mem_ctx);
+   mem_ctx = NULL;
+}
+
+INSTANTIATE_TEST_CASE_P(
+   list_iterators_node_inherite,
+   list_iterators_node_inherite,
+   ::testing::Values(0, 1, 10)
+);
+
+TEST_P(list_iterators_node_inherite, foreach_in_list)
+{
+   size_t i = 0;
+   foreach_in_list(test_node_inherite, n, &node_list) {
+      EXPECT_EQ(n->value, i);
+      i++;
+   }
+}
+
+TEST_P(list_iterators_node_inherite, foreach_in_list_reverse)
+{
+   size_t i = GetParam() - 1;
+   foreach_in_list_reverse(test_node_inherite, n, &node_list) {
+      EXPECT_EQ(n->value, i);
+      i--;
+   }
+}
+
+TEST_P(list_iterators_node_inherite, foreach_in_list_safe)
+{
+   size_t i = 0;
+   foreach_in_list_safe(test_node_inherite, n, &node_list) {
+      EXPECT_EQ(n->value, i);
+
+      if (i % 2 == 0) {
+         n->remove();
+      }
+
+      i++;
+   }
+
+   exec_list_validate(&node_list);
+}
+
+TEST_P(list_iterators_node_inherite, foreach_in_list_reverse_safe)
+{
+   size_t i = GetParam() - 1;
+   foreach_in_list_reverse_safe(test_node_inherite, n, &node_list) {
+      EXPECT_EQ(n->value, i);
+
+      if (i % 2 == 0) {
+         n->remove();
+      }
+
+      i--;
+   }
+
+   exec_list_validate(&node_list);
+}
+
+TEST_P(list_iterators_node_inherite, foreach_in_list_use_after)
+{
+   size_t i = 0;
+   foreach_in_list_use_after(test_node_inherite, n, &node_list) {
+      EXPECT_EQ(n->value, i);
+
+      if (i == GetParam() / 2) {
+         break;
+      }
+
+      i++;
+   }
+
+   if (GetParam() > 0) {
+      EXPECT_EQ(n->value, GetParam() / 2);
+   }
+}
+
+class test_node_embed {
+   DECLARE_RZALLOC_CXX_OPERATORS(test_node_embed)
+public:
+
+   uint32_t value_header;
+   exec_node node;
+   uint32_t value_footer;
+
+   virtual ~test_node_embed() = default;
+};
+
+class list_iterators_node_embed : public ::testing::TestWithParam<size_t> {
+public:
+   virtual void SetUp();
+   virtual void TearDown();
+
+   void *mem_ctx;
+
+   exec_list node_list;
+};
+
+void
+list_iterators_node_embed::SetUp()
+{
+   mem_ctx = ralloc_context(NULL);
+
+   exec_list_make_empty(&node_list);
+
+   for (size_t i = 0; i < GetParam(); i++) {
+      test_node_embed *node = new(mem_ctx) test_node_embed();
+      node->value_header = i;
+      node->value_footer = i;
+      exec_list_push_tail(&node_list, &node->node);
+   }
+}
+
+void
+list_iterators_node_embed::TearDown()
+{
+   exec_list_make_empty(&node_list);
+
+   ralloc_free(mem_ctx);
+   mem_ctx = NULL;
+}
+
+INSTANTIATE_TEST_CASE_P(
+   list_iterators_node_embed,
+   list_iterators_node_embed,
+   ::testing::Values(0, 1, 10)
+);
+
+TEST_P(list_iterators_node_embed, foreach_list_typed)
+{
+   size_t i = 0;
+   foreach_list_typed(test_node_embed, n, node, &node_list) {
+      EXPECT_EQ(n->value_header, i);
+      EXPECT_EQ(n->value_footer, i);
+      i++;
+   }
+}
+
+TEST_P(list_iterators_node_embed, foreach_list_typed_from)
+{
+   if (GetParam() == 0) {
+      return;
+   }
+
+   exec_node *start_node = node_list.get_head();
+
+   size_t i = 0;
+   for (; i < GetParam() / 2; i++) {
+      start_node = start_node->get_next();
+   }
+
+   foreach_list_typed_from(test_node_embed, n, node, &node_list, start_node) {
+      EXPECT_EQ(n->value_header, i);
+      EXPECT_EQ(n->value_footer, i);
+      i++;
+   }
+}
+
+TEST_P(list_iterators_node_embed, foreach_list_typed_reverse)
+{
+   size_t i = GetParam() - 1;
+   foreach_list_typed_reverse(test_node_embed, n, node, &node_list) {
+      EXPECT_EQ(n->value_header, i);
+      EXPECT_EQ(n->value_footer, i);
+      i--;
+   }
+}
+
+TEST_P(list_iterators_node_embed, foreach_list_typed_safe)
+{
+   size_t i = 0;
+   foreach_list_typed_safe(test_node_embed, n, node, &node_list) {
+      EXPECT_EQ(n->value_header, i);
+      EXPECT_EQ(n->value_footer, i);
+
+      if (i % 2 == 0) {
+         exec_node_remove(&n->node);
+      }
+
+      i++;
+   }
+
+   exec_list_validate(&node_list);
+}
+
+TEST_P(list_iterators_node_embed, foreach_list_typed_reverse_safe)
+{
+   size_t i = GetParam() - 1;
+   foreach_list_typed_reverse_safe(test_node_embed, n, node, &node_list) {
+      EXPECT_EQ(n->value_header, i);
+      EXPECT_EQ(n->value_footer, i);
+
+      if (i % 2 == 0) {
+         exec_node_remove(&n->node);
+      }
+
+      i--;
+   }
+
+   exec_list_validate(&node_list);
+}
diff --git a/src/compiler/glsl/tests/meson.build b/src/compiler/glsl/tests/meson.build
index 41f8ae615d1..c887a5a7e4c 100644
--- a/src/compiler/glsl/tests/meson.build
+++ b/src/compiler/glsl/tests/meson.build
@@ -78,6 +78,19 @@ test(
 )
 
 test(
+  'list_iterators',
+  executable(
+    'list_iterators',
+    ['list_iterators.cpp'],
+    cpp_args : [cpp_vis_args, cpp_msvc_compat_args],
+    include_directories : [inc_include, inc_src, inc_glsl],
+    link_with : [libglsl, libglsl_util],
+    dependencies : [dep_thread, idep_gtest],
+  ),
+  suite : ['compiler', 'glsl'],
+)
+
+test(
   'glsl compiler warnings',
   prog_python,
   args : [