From: Xu Kuohai <xukuohai@huawei.com>

There is a typo in comment for DFS algorithm in bpf/verifier.c. The top
element should not be popped until all its neighbors have been checked.
Fix it.

Fixes: 475fb78fbf48 ("bpf: verifier (add branch/goto checks)")
Signed-off-by: Xu Kuohai <xukuohai@huawei.com>
---
 kernel/bpf/verifier.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b83a8d420520..96ba5ea6d1a6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10662,7 +10662,7 @@ static int check_return_code(struct bpf_verifier_env *env)
  * 3      let S be a stack
  * 4      S.push(v)
  * 5      while S is not empty
- * 6            t <- S.pop()
+ * 6            t <- S.top()
  * 7            if t is what we're looking for:
  * 8                return t
  * 9            for all edges e in G.adjacentEdges(t) do
-- 
2.30.2

On Tue, Oct 25, 2022 at 7:42 PM Xu Kuohai <xukuohai@huaweicloud.com> wrote:
>
> From: Xu Kuohai <xukuohai@huawei.com>
>
> There is a typo in comment for DFS algorithm in bpf/verifier.c. The top
> element should not be popped until all its neighbors have been checked.
> Fix it.
>
> Fixes: 475fb78fbf48 ("bpf: verifier (add branch/goto checks)")
> Signed-off-by: Xu Kuohai <xukuohai@huawei.com>
> ---
>  kernel/bpf/verifier.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index b83a8d420520..96ba5ea6d1a6 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -10662,7 +10662,7 @@ static int check_return_code(struct bpf_verifier_env *env)
>   * 3      let S be a stack
>   * 4      S.push(v)
>   * 5      while S is not empty
> - * 6            t <- S.pop()
> + * 6            t <- S.top()

Even with this fix the comment is not quite accurate.
I wonder whether we should keep it or delete it completely.
At least please use 'peek' instead of 'top'.

On 10/26/2022 2:32 PM, Alexei Starovoitov wrote:
> On Tue, Oct 25, 2022 at 7:42 PM Xu Kuohai <xukuohai@huaweicloud.com> wrote:
>>
>> From: Xu Kuohai <xukuohai@huawei.com>
>>
>> There is a typo in comment for DFS algorithm in bpf/verifier.c. The top
>> element should not be popped until all its neighbors have been checked.
>> Fix it.
>>
>> Fixes: 475fb78fbf48 ("bpf: verifier (add branch/goto checks)")
>> Signed-off-by: Xu Kuohai <xukuohai@huawei.com>
>> ---
>>   kernel/bpf/verifier.c | 2 +-
>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index b83a8d420520..96ba5ea6d1a6 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -10662,7 +10662,7 @@ static int check_return_code(struct bpf_verifier_env *env)
>>    * 3      let S be a stack
>>    * 4      S.push(v)
>>    * 5      while S is not empty
>> - * 6            t <- S.pop()
>> + * 6            t <- S.top()
> 
> Even with this fix the comment is not quite accurate.
> I wonder whether we should keep it or delete it completely.

The comment describes the non-recursive DFS algorithm used by the C code.
Although it does not describe the full details, it helps us to understand
the code, so I think it should be kept.

> At least please use 'peek' instead of 'top'.

OK.

On Tue, Oct 25, 2022 at 11:32:55PM -0700, Alexei Starovoitov wrote:
> On Tue, Oct 25, 2022 at 7:42 PM Xu Kuohai <xukuohai@huaweicloud.com> wrote:
> >
> > From: Xu Kuohai <xukuohai@huawei.com>
> >
> > There is a typo in comment for DFS algorithm in bpf/verifier.c. The top
> > element should not be popped until all its neighbors have been checked.
> > Fix it.
> >
> > Fixes: 475fb78fbf48 ("bpf: verifier (add branch/goto checks)")
> > Signed-off-by: Xu Kuohai <xukuohai@huawei.com>
> > ---
> >  kernel/bpf/verifier.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index b83a8d420520..96ba5ea6d1a6 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -10662,7 +10662,7 @@ static int check_return_code(struct bpf_verifier_env *env)
> >   * 3      let S be a stack
> >   * 4      S.push(v)
> >   * 5      while S is not empty
> > - * 6            t <- S.pop()
> > + * 6            t <- S.top()
> 
> Even with this fix the comment is not quite accurate.
> I wonder whether we should keep it or delete it completely.
> At least please use 'peek' instead of 'top'.

I think the comment should be in words (like other code comments in the
kernel) instead.

-- 
An old man doll... just what I always wanted! - Clara

On 10/26/2022 3:52 PM, Bagas Sanjaya wrote:
> On Tue, Oct 25, 2022 at 11:32:55PM -0700, Alexei Starovoitov wrote:
>> On Tue, Oct 25, 2022 at 7:42 PM Xu Kuohai <xukuohai@huaweicloud.com> wrote:
>>>
>>> From: Xu Kuohai <xukuohai@huawei.com>
>>>
>>> There is a typo in comment for DFS algorithm in bpf/verifier.c. The top
>>> element should not be popped until all its neighbors have been checked.
>>> Fix it.
>>>
>>> Fixes: 475fb78fbf48 ("bpf: verifier (add branch/goto checks)")
>>> Signed-off-by: Xu Kuohai <xukuohai@huawei.com>
>>> ---
>>>   kernel/bpf/verifier.c | 2 +-
>>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>>
>>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>>> index b83a8d420520..96ba5ea6d1a6 100644
>>> --- a/kernel/bpf/verifier.c
>>> +++ b/kernel/bpf/verifier.c
>>> @@ -10662,7 +10662,7 @@ static int check_return_code(struct bpf_verifier_env *env)
>>>    * 3      let S be a stack
>>>    * 4      S.push(v)
>>>    * 5      while S is not empty
>>> - * 6            t <- S.pop()
>>> + * 6            t <- S.top()
>>
>> Even with this fix the comment is not quite accurate.
>> I wonder whether we should keep it or delete it completely.
>> At least please use 'peek' instead of 'top'.
> 
> I think the comment should be in words (like other code comments in the
> kernel) instead.
> 

The beginning of the comment already says this is a piece of pseudo code. And
I don't think it's clearer to describe the algorithm in words than to describe
it in pseudo code.