[bpf-next] bpf: make list_for_each_entry portable

Commit Message

Jose E. Marchesi May 9, 2024, 8:46 a.m. UTC

The macro list_for_each_entry is defined in bpf_arena_list.h as
follows:

  #define list_for_each_entry(pos, head, member)				\
	for (void * ___tmp = (pos = list_entry_safe((head)->first,		\
						    typeof(*(pos)), member),	\
			      (void *)0);					\
	     pos && ({ ___tmp = (void *)pos->member.next; 1; });		\
	     cond_break,							\
	     pos = list_entry_safe((void __arena *)___tmp, typeof(*(pos)), member))

The macro cond_break, in turn, expands to a statement expression that
contains a `break' statement.  Compound statement expressions, and the
subsequent ability of placing statements in the header of a `for'
loop, are GNU extensions.

Unfortunately, clang implements this GNU extension differently than
GCC:

- In GCC the `break' statement is bound to the containing "breakable"
  context in which the defining `for' appears.  If there is no such
  context, GCC emits a warning: break statement without enclosing `for'
  o `switch' statement.

- In clang the `break' statement is bound to the defining `for'.  If
  the defining `for' is itself inside some breakable construct, then
  clang emits a -Wgcc-compat warning.

This patch makes it possible to use the cond_break macro with GCC by
adding an outer breakable context __compat_break that expands to a
one-iteration `for' loop when compiling with GCC, and to nothing when
compiling with clang.  It is important to note that the __compat_break
one-iteration loop gets optimized away by GCC with -O1 and higher.

The list_for_each_entry macro is adapted to use __compat_break, as are
the pertinent loops in the few tests that use cond_break directly.

Tested in bpf-next master.
No regressions.

Signed-off-by: Jose E. Marchesi <[e-mail]>
Cc: [e-mail]
Cc: [e-mail]
Cc: Alexei Starovoitov <[e-mail]>
---
 tools/testing/selftests/bpf/bpf_arena_list.h          |  2 ++
 tools/testing/selftests/bpf/bpf_experimental.h        | 11 +++++++++++
 tools/testing/selftests/bpf/progs/arena_list.c        |  1 +
 .../bpf/progs/verifier_iterating_callbacks.c          |  3 +++
 4 files changed, 17 insertions(+)

Comments

Alexei Starovoitov May 9, 2024, 9:48 p.m. UTC | #1

On Thu, May 9, 2024 at 1:47 AM Jose E. Marchesi
<[e-mail]> wrote:
> +/* A `break' executed in the head of a `for' loop statement is bound
> +   to the current loop in clang, but it is bound to the enclosing loop
> +   in GCC.  Note both compilers optimize the outer loop out with -O1
> +   and higher.  This macro shall be used to annotate any loop that
> +   uses cond_break within its header.  */
> +#ifdef __clang__
> +#define __compat_break
> +#else
> +#define __compat_break for (int __control = 1; __control; --__control)
> +#endif
..
> +       __compat_break
>         for (i = zero; i < cnt; cond_break, i++) {
>                 struct elem __arena *n = bpf_alloc(sizeof(*n));

This is too ugly. It ruins the readability of the code.
Let's introduce can_loop macro similar to cond_break
that returns 0 or 1 instead of break/continue and use it as:

        for (i = zero; i < cnt && can_loop; i++) {

pw-bot: cr

Jose E. Marchesi May 10, 2024, 8:26 a.m. UTC | #2

> On Thu, May 9, 2024 at 1:47 AM Jose E. Marchesi
> <[e-mail]> wrote:
>> +/* A `break' executed in the head of a `for' loop statement is bound
>> +   to the current loop in clang, but it is bound to the enclosing loop
>> +   in GCC.  Note both compilers optimize the outer loop out with -O1
>> +   and higher.  This macro shall be used to annotate any loop that
>> +   uses cond_break within its header.  */
>> +#ifdef __clang__
>> +#define __compat_break
>> +#else
>> +#define __compat_break for (int __control = 1; __control; --__control)
>> +#endif
> ..
>> +       __compat_break
>>         for (i = zero; i < cnt; cond_break, i++) {
>>                 struct elem __arena *n = bpf_alloc(sizeof(*n));
>
> This is too ugly. It ruins the readability of the code.
> Let's introduce can_loop macro similar to cond_break
> that returns 0 or 1 instead of break/continue and use it as:
>
>         for (i = zero; i < cnt && can_loop; i++) {
>
> pw-bot: cr

I went with the ugliness because I was trying to avoid rewriting the
loops in the tests, assuming the tests were actually testing using
cond_break in these particular locations would result in a particular
number of iterations.

The loops

  for (i = zero; i < cnt; cond_break, i++) BODY

and

  for (i = zero; i < cnt && can_loop; i++) BODY

are not equivalent if can_loop implements the same logic than
cond_break.

The may_goto instructions are somehow patched at run-time, and in a
predictable way since the tests are checking for explicit iteration
counts, right?

Alexei Starovoitov May 10, 2024, 5:03 p.m. UTC | #3

On Fri, May 10, 2024 at 1:27 AM Jose E. Marchesi
<[e-mail]> wrote:
>
>
> > On Thu, May 9, 2024 at 1:47 AM Jose E. Marchesi
> > <[e-mail]> wrote:
> >> +/* A `break' executed in the head of a `for' loop statement is bound
> >> +   to the current loop in clang, but it is bound to the enclosing loop
> >> +   in GCC.  Note both compilers optimize the outer loop out with -O1
> >> +   and higher.  This macro shall be used to annotate any loop that
> >> +   uses cond_break within its header.  */
> >> +#ifdef __clang__
> >> +#define __compat_break
> >> +#else
> >> +#define __compat_break for (int __control = 1; __control; --__control)
> >> +#endif
> > ..
> >> +       __compat_break
> >>         for (i = zero; i < cnt; cond_break, i++) {
> >>                 struct elem __arena *n = bpf_alloc(sizeof(*n));
> >
> > This is too ugly. It ruins the readability of the code.
> > Let's introduce can_loop macro similar to cond_break
> > that returns 0 or 1 instead of break/continue and use it as:
> >
> >         for (i = zero; i < cnt && can_loop; i++) {
> >
> > pw-bot: cr
>
> I went with the ugliness because I was trying to avoid rewriting the
> loops in the tests, assuming the tests were actually testing using
> cond_break in these particular locations would result in a particular
> number of iterations.
>
> The loops
>
>   for (i = zero; i < cnt; cond_break, i++) BODY
>
> and
>
>   for (i = zero; i < cnt && can_loop; i++) BODY
>
> are not equivalent if can_loop implements the same logic than
> cond_break.

It's off by one and it's fine.
The loops don't and shouldn't expect the precise number allowed
by may_goto.

btw there are tests that use cond_break inside {}.
They don't need to change.

>
> The may_goto instructions are somehow patched at run-time, and in a
> predictable way since the tests are checking for explicit iteration
> counts, right?

They're patched by the verifier, but they're unpredictable.
Right now it's a simpler counter, but sooner or later
it will be time based.

Jose E. Marchesi May 10, 2024, 5:16 p.m. UTC | #4

> On Fri, May 10, 2024 at 1:27 AM Jose E. Marchesi
> <[e-mail]> wrote:
>>
>>
>> > On Thu, May 9, 2024 at 1:47 AM Jose E. Marchesi
>> > <[e-mail]> wrote:
>> >> +/* A `break' executed in the head of a `for' loop statement is bound
>> >> +   to the current loop in clang, but it is bound to the enclosing loop
>> >> +   in GCC.  Note both compilers optimize the outer loop out with -O1
>> >> +   and higher.  This macro shall be used to annotate any loop that
>> >> +   uses cond_break within its header.  */
>> >> +#ifdef __clang__
>> >> +#define __compat_break
>> >> +#else
>> >> +#define __compat_break for (int __control = 1; __control; --__control)
>> >> +#endif
>> > ..
>> >> +       __compat_break
>> >>         for (i = zero; i < cnt; cond_break, i++) {
>> >>                 struct elem __arena *n = bpf_alloc(sizeof(*n));
>> >
>> > This is too ugly. It ruins the readability of the code.
>> > Let's introduce can_loop macro similar to cond_break
>> > that returns 0 or 1 instead of break/continue and use it as:
>> >
>> >         for (i = zero; i < cnt && can_loop; i++) {
>> >
>> > pw-bot: cr
>>
>> I went with the ugliness because I was trying to avoid rewriting the
>> loops in the tests, assuming the tests were actually testing using
>> cond_break in these particular locations would result in a particular
>> number of iterations.
>>
>> The loops
>>
>>   for (i = zero; i < cnt; cond_break, i++) BODY
>>
>> and
>>
>>   for (i = zero; i < cnt && can_loop; i++) BODY
>>
>> are not equivalent if can_loop implements the same logic than
>> cond_break.
>
> It's off by one and it's fine.
> The loops don't and shouldn't expect the precise number allowed
> by may_goto.

Ok, understood.

I assume you also want to use can_loop also in the definition of
list_for_each_entry?

> btw there are tests that use cond_break inside {}.
> They don't need to change.

Yes I noticed these.  Won't touch them.

>
>>
>> The may_goto instructions are somehow patched at run-time, and in a
>> predictable way since the tests are checking for explicit iteration
>> counts, right?
>
> They're patched by the verifier, but they're unpredictable.
> Right now it's a simpler counter, but sooner or later
> it will be time based.

Patch

diff --git a/tools/testing/selftests/bpf/bpf_arena_list.h b/tools/testing/selftests/bpf/bpf_arena_list.h
index b99b9f408eff..5659c715a8a0 100644
--- a/tools/testing/selftests/bpf/bpf_arena_list.h
+++ b/tools/testing/selftests/bpf/bpf_arena_list.h
@@ -29,10 +29,12 @@  static inline void *bpf_iter_num_new(struct bpf_iter_num *it, int i, int j) { re
 static inline void bpf_iter_num_destroy(struct bpf_iter_num *it) {}
 static inline bool bpf_iter_num_next(struct bpf_iter_num *it) { return true; }
 #define cond_break ({})
+#define __compat_break
 #endif
 
 /* Safely walk link list elements. Deletion of elements is allowed. */
 #define list_for_each_entry(pos, head, member)					\
+	__compat_break								\
 	for (void * ___tmp = (pos = list_entry_safe((head)->first,		\
 						    typeof(*(pos)), member),	\
 			      (void *)0);					\
diff --git a/tools/testing/selftests/bpf/bpf_experimental.h b/tools/testing/selftests/bpf/bpf_experimental.h
index 8b9cc87be4c4..7f03570638a6 100644
--- a/tools/testing/selftests/bpf/bpf_experimental.h
+++ b/tools/testing/selftests/bpf/bpf_experimental.h
@@ -326,6 +326,17 @@  l_true:												\
        })
 #endif
 
+/* A `break' executed in the head of a `for' loop statement is bound
+   to the current loop in clang, but it is bound to the enclosing loop
+   in GCC.  Note both compilers optimize the outer loop out with -O1
+   and higher.  This macro shall be used to annotate any loop that
+   uses cond_break within its header.  */
+#ifdef __clang__
+#define __compat_break
+#else
+#define __compat_break for (int __control = 1; __control; --__control)
+#endif
+
 #ifdef __BPF_FEATURE_MAY_GOTO
 #define cond_break					\
 	({ __label__ l_break, l_continue;		\
diff --git a/tools/testing/selftests/bpf/progs/arena_list.c b/tools/testing/selftests/bpf/progs/arena_list.c
index c0422c58cee2..570c1e043257 100644
--- a/tools/testing/selftests/bpf/progs/arena_list.c
+++ b/tools/testing/selftests/bpf/progs/arena_list.c
@@ -49,6 +49,7 @@  int arena_list_add(void *ctx)
 
 	list_head = &global_head;
 
+	__compat_break
 	for (i = zero; i < cnt; cond_break, i++) {
 		struct elem __arena *n = bpf_alloc(sizeof(*n));
 
diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index 99e561f18f9b..e0437609af21 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -318,6 +318,7 @@  int cond_break1(const void *ctx)
 	unsigned long i;
 	unsigned int sum = 0;
 
+	__compat_break
 	for (i = zero; i < ARR_SZ; cond_break, i++)
 		sum += i;
 	for (i = zero; i < ARR_SZ; i++) {
@@ -336,6 +337,7 @@  int cond_break2(const void *ctx)
 	int i, j;
 	int sum = 0;
 
+	__compat_break
 	for (i = zero; i < 1000; cond_break, i++)
 		for (j = zero; j < 1000; j++) {
 			sum += i + j;
@@ -349,6 +351,7 @@  static __noinline int loop(void)
 {
 	int i, sum = 0;
 
+	__compat_break
 	for (i = zero; i <= 1000000; i++, cond_break)
 		sum += i;