[PATCH] radix-tree: don't left-shift negative values

[PATCH] radix-tree: don't left-shift negative values

[Jan Beulich]

Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
left shifting negative values is UB. Use an unsigned intermediate type,
reducing the impact to implementation defined behavior (for the
unsigned->signed conversion).

Also please Misra C:2012 rule 7.3 by dropping the lower case numeric 'l'
tag.

No difference in generated code, at least on x86.

Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions) radix_tree_int_to_ptr()")
Reported-by: Teddy Astie <teddy.astie@vates.tech>
Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
         tagging.ecl the codebase is clean for this rule, aiui.

--- a/xen/include/xen/radix-tree.h
+++ b/xen/include/xen/radix-tree.h
@@ -172,7 +172,7 @@ static inline void radix_tree_replace_sl
  */
 static inline void *radix_tree_int_to_ptr(int val)
 {
-    long _ptr = ((long)val << 2) | 0x2l;
+    long _ptr = ((unsigned long)val << 2) | 2;
     ASSERT((_ptr >> 2) == val);
     return (void *)_ptr;
 }

Re: [PATCH] radix-tree: don't left-shift negative values

[Nicola Vetrini]

On 2025-02-13 15:22, Jan Beulich wrote:
> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
> left shifting negative values is UB. Use an unsigned intermediate type,
> reducing the impact to implementation defined behavior (for the
> unsigned->signed conversion).
> 
> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric 
> 'l'
> tag.
> 
> No difference in generated code, at least on x86.
> 
> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions) 
> radix_tree_int_to_ptr()")
> Reported-by: Teddy Astie <teddy.astie@vates.tech>
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> ---
> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
>          tagging.ecl the codebase is clean for this rule, aiui.
> 

radix-tree.{c,h} is out of scope:

automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
docs/misra/exclude-list.json:153:            "rel_path": 
"common/radix-tree.c",

We are in the process of setting up a wider analysis (i.e. with a 
different exclusion set) with a broader configuration that may catch 
these issues.

> --- a/xen/include/xen/radix-tree.h
> +++ b/xen/include/xen/radix-tree.h
> @@ -172,7 +172,7 @@ static inline void radix_tree_replace_sl
>   */
>  static inline void *radix_tree_int_to_ptr(int val)
>  {
> -    long _ptr = ((long)val << 2) | 0x2l;
> +    long _ptr = ((unsigned long)val << 2) | 2;
>      ASSERT((_ptr >> 2) == val);
>      return (void *)_ptr;
>  }

-- 
Nicola Vetrini, B.Sc.
Software Engineer
BUGSENG (https://bugseng.com)
LinkedIn: https://www.linkedin.com/in/nicola-vetrini-a42471253

Re: [PATCH] radix-tree: don't left-shift negative values

[Andrew Cooper]

On 13/02/2025 2:52 pm, Nicola Vetrini wrote:
> On 2025-02-13 15:22, Jan Beulich wrote:
>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
>> left shifting negative values is UB. Use an unsigned intermediate type,
>> reducing the impact to implementation defined behavior (for the
>> unsigned->signed conversion).
>>
>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric 'l'
>> tag.
>>
>> No difference in generated code, at least on x86.
>>
>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
>> radix_tree_int_to_ptr()")
>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>> ---
>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
>>          tagging.ecl the codebase is clean for this rule, aiui.
>>
>
> radix-tree.{c,h} is out of scope:
>
> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
>
> docs/misra/exclude-list.json:153:            "rel_path":
> "common/radix-tree.c",

Why was this deemed out of scope?

Mostly rhetorical, as I expect the answer is "because this was vendored
from Linux".

And yet, it's still code in our project, buggy in genuine ways, and it's
perhaps escaped peoples notice that the TMEM subsystem (now deleted)
made largescale deviations to radix-tree, compared to its Linux
origins.  The fact we're deleting these to fix another bug is incidental.

tl;dr radix-tree is in scope and needs examining.

~Andrew

Re: [PATCH] radix-tree: don't left-shift negative values

[Jan Beulich]

On 13.02.2025 15:52, Nicola Vetrini wrote:
> On 2025-02-13 15:22, Jan Beulich wrote:
>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
>> left shifting negative values is UB. Use an unsigned intermediate type,
>> reducing the impact to implementation defined behavior (for the
>> unsigned->signed conversion).
>>
>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric 
>> 'l'
>> tag.
>>
>> No difference in generated code, at least on x86.
>>
>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions) 
>> radix_tree_int_to_ptr()")
>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>> ---
>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
>>          tagging.ecl the codebase is clean for this rule, aiui.
>>
> 
> radix-tree.{c,h} is out of scope:
> 
> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
> docs/misra/exclude-list.json:153:            "rel_path": 
> "common/radix-tree.c",

Is there a record of why they are excluded? Is it further explainable
why exclude-list.json mentions only the .c file and out_of_scope.ecl
mentions only the .h one? Shouldn't different parts be in sync?

> We are in the process of setting up a wider analysis (i.e. with a 
> different exclusion set) with a broader configuration that may catch 
> these issues.

Good.

Jan

Re: [PATCH] radix-tree: don't left-shift negative values

[Nicola Vetrini]

On 2025-02-13 16:01, Jan Beulich wrote:
> On 13.02.2025 15:52, Nicola Vetrini wrote:
>> On 2025-02-13 15:22, Jan Beulich wrote:
>>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), 
>>> yet
>>> left shifting negative values is UB. Use an unsigned intermediate 
>>> type,
>>> reducing the impact to implementation defined behavior (for the
>>> unsigned->signed conversion).
>>> 
>>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric
>>> 'l'
>>> tag.
>>> 
>>> No difference in generated code, at least on x86.
>>> 
>>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
>>> radix_tree_int_to_ptr()")
>>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>> ---
>>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According 
>>> to
>>>          tagging.ecl the codebase is clean for this rule, aiui.
>>> 
>> 
>> radix-tree.{c,h} is out of scope:
>> 
>> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
>> docs/misra/exclude-list.json:153:            "rel_path":
>> "common/radix-tree.c",
> 
> Is there a record of why they are excluded? Is it further explainable
> why exclude-list.json mentions only the .c file and out_of_scope.ecl
> mentions only the .h one? Shouldn't different parts be in sync?
> 

exclude-list.json is used to generate a configuration file for ECLAIR 
just before the analysis starts, so effectively both are excluded. It's 
a good point however to have only one file to handle exclusions, and use 
that file to generate the exclusion list dynamically, but then someone 
might want to exclude certain files only in some analyses and not 
others, which is not a good fit for exclude-list.json as it is now.

@Stefano, thoughts?

Thanks,
  Nicola

>> We are in the process of setting up a wider analysis (i.e. with a
>> different exclusion set) with a broader configuration that may catch
>> these issues.
> 
> Good.
> 
> Jan

-- 
Nicola Vetrini, B.Sc.
Software Engineer
BUGSENG (https://bugseng.com)
LinkedIn: https://www.linkedin.com/in/nicola-vetrini-a42471253

Re: [PATCH] radix-tree: don't left-shift negative values

[Nicola Vetrini]

On 2025-02-13 16:32, Nicola Vetrini wrote:
> On 2025-02-13 16:01, Jan Beulich wrote:
>> On 13.02.2025 15:52, Nicola Vetrini wrote:
>>> On 2025-02-13 15:22, Jan Beulich wrote:
>>>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), 
>>>> yet
>>>> left shifting negative values is UB. Use an unsigned intermediate 
>>>> type,
>>>> reducing the impact to implementation defined behavior (for the
>>>> unsigned->signed conversion).
>>>> 
>>>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric
>>>> 'l'
>>>> tag.
>>>> 
>>>> No difference in generated code, at least on x86.
>>>> 
>>>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
>>>> radix_tree_int_to_ptr()")
>>>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>> ---
>>>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According 
>>>> to
>>>>          tagging.ecl the codebase is clean for this rule, aiui.
>>>> 
>>> 
>>> radix-tree.{c,h} is out of scope:
>>> 
>>> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
>>> docs/misra/exclude-list.json:153:            "rel_path":
>>> "common/radix-tree.c",
>> 
>> Is there a record of why they are excluded? Is it further explainable
>> why exclude-list.json mentions only the .c file and out_of_scope.ecl
>> mentions only the .h one? Shouldn't different parts be in sync?
>> 
> 
> exclude-list.json is used to generate a configuration file for ECLAIR 
> just before the analysis starts, so effectively both are excluded. It's 
> a good point however to have only one file to handle exclusions, and 
> use that file to generate the exclusion list dynamically, but then 
> someone might want to exclude certain files only in some analyses and 
> not others, which is not a good fit for exclude-list.json as it is now.
> 
> @Stefano, thoughts?
> 

I forgot to address the first question: the (vague) reasons are listed 
in exclude-list.json as the "comment" field; in most cases, it's because 
the files have been imported from Linux, but the full rationale is 
something that should be asked to the original author, which is Luca 
Fancellu. Over the past months, I made small edits upon receiving 
feedback from the community (e.g., excluding gdbsx.c), but there's the 
possibility that the content should be re-evaulated in its entirety 
(which will likely lead to additional MISRA violations being generated, 
even for clean rules, as you correctly pointed out) and possibly lead to 
different sets of excluded files depending on the type of analysis 
(i.e., a restricted "safety" configuration and a wider "community" 
configuration).

> Thanks,
>  Nicola
> 
>>> We are in the process of setting up a wider analysis (i.e. with a
>>> different exclusion set) with a broader configuration that may catch
>>> these issues.
>> 
>> Good.
>> 
>> Jan

-- 
Nicola Vetrini, B.Sc.
Software Engineer
BUGSENG (https://bugseng.com)
LinkedIn: https://www.linkedin.com/in/nicola-vetrini-a42471253

Re: [PATCH] radix-tree: don't left-shift negative values

[Luca Fancellu]

Hi Nicola,

> On 13 Feb 2025, at 15:42, Nicola Vetrini <nicola.vetrini@bugseng.com> wrote:
> 
> On 2025-02-13 16:32, Nicola Vetrini wrote:
>> On 2025-02-13 16:01, Jan Beulich wrote:
>>> On 13.02.2025 15:52, Nicola Vetrini wrote:
>>>> On 2025-02-13 15:22, Jan Beulich wrote:
>>>>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
>>>>> left shifting negative values is UB. Use an unsigned intermediate type,
>>>>> reducing the impact to implementation defined behavior (for the
>>>>> unsigned->signed conversion).
>>>>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric
>>>>> 'l'
>>>>> tag.
>>>>> No difference in generated code, at least on x86.
>>>>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
>>>>> radix_tree_int_to_ptr()")
>>>>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
>>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>>> ---
>>>>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
>>>>>         tagging.ecl the codebase is clean for this rule, aiui.
>>>> radix-tree.{c,h} is out of scope:
>>>> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
>>>> docs/misra/exclude-list.json:153:            "rel_path":
>>>> "common/radix-tree.c",
>>> Is there a record of why they are excluded? Is it further explainable
>>> why exclude-list.json mentions only the .c file and out_of_scope.ecl
>>> mentions only the .h one? Shouldn't different parts be in sync?
>> exclude-list.json is used to generate a configuration file for ECLAIR just before the analysis starts, so effectively both are excluded. It's a good point however to have only one file to handle exclusions, and use that file to generate the exclusion list dynamically, but then someone might want to exclude certain files only in some analyses and not others, which is not a good fit for exclude-list.json as it is now.
>> @Stefano, thoughts?
> 
> I forgot to address the first question: the (vague) reasons are listed in exclude-list.json as the "comment" field; in most cases, it's because the files have been imported from Linux, but the full rationale is something that should be asked to the original author, which is Luca Fancellu.

So IIRC the full rationale is that since some files are imported from Linux, we would like to maintain them as they are
in order to ease backports. Misra fixes can be done, but they need to be upstreamed to Linux and backported to Xen.

Probably a re-evaluation could be done by the maintainers to see if some of these files could be removed from the exclusion
list.

Cheers,
Luca

Re: [PATCH] radix-tree: don't left-shift negative values

[Stefano Stabellini]

On Thu, 13 Feb 2025, Luca Fancellu wrote:
> > On 13 Feb 2025, at 15:42, Nicola Vetrini <nicola.vetrini@bugseng.com> wrote:
> > On 2025-02-13 16:32, Nicola Vetrini wrote:
> >> On 2025-02-13 16:01, Jan Beulich wrote:
> >>> On 13.02.2025 15:52, Nicola Vetrini wrote:
> >>>> On 2025-02-13 15:22, Jan Beulich wrote:
> >>>>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
> >>>>> left shifting negative values is UB. Use an unsigned intermediate type,
> >>>>> reducing the impact to implementation defined behavior (for the
> >>>>> unsigned->signed conversion).
> >>>>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric
> >>>>> 'l'
> >>>>> tag.
> >>>>> No difference in generated code, at least on x86.
> >>>>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
> >>>>> radix_tree_int_to_ptr()")
> >>>>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
> >>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> >>>>> ---
> >>>>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
> >>>>>         tagging.ecl the codebase is clean for this rule, aiui.
> >>>> radix-tree.{c,h} is out of scope:
> >>>> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
> >>>> docs/misra/exclude-list.json:153:            "rel_path":
> >>>> "common/radix-tree.c",
> >>> Is there a record of why they are excluded? Is it further explainable
> >>> why exclude-list.json mentions only the .c file and out_of_scope.ecl
> >>> mentions only the .h one? Shouldn't different parts be in sync?
> >> exclude-list.json is used to generate a configuration file for ECLAIR just before the analysis starts, so effectively both are excluded. It's a good point however to have only one file to handle exclusions, and use that file to generate the exclusion list dynamically, but then someone might want to exclude certain files only in some analyses and not others, which is not a good fit for exclude-list.json as it is now.
> >> @Stefano, thoughts?
> > 
> > I forgot to address the first question: the (vague) reasons are listed in exclude-list.json as the "comment" field; in most cases, it's because the files have been imported from Linux, but the full rationale is something that should be asked to the original author, which is Luca Fancellu.
> 
> So IIRC the full rationale is that since some files are imported from Linux, we would like to maintain them as they are
> in order to ease backports. Misra fixes can be done, but they need to be upstreamed to Linux and backported to Xen.
> 
> Probably a re-evaluation could be done by the maintainers to see if some of these files could be removed from the exclusion
> list.

Yes, it is as Luca said. At the beginning of the project, we reviewed
the codebase to define what was in scope and what was out of scope. One
area of contention was the files imported from Linux. Many of these
files were declared out of scope because we wanted to retain the ability
to easily synchronize them with their corresponding files in Linux.  

Now, years have passed, and we have gained significant experience from
running this project. It is completely acceptable to redefine the scope,
including making changes to exclude-list.json.

However, we do not necessarily need to modify exclude-list.json to
accept a single, clearly beneficial fix like this one. So, Jan, feel
free to proceed and commit it.  

I just wanted to provide some background. If you believe that removing
common/radix-tree.c from docs/misra/exclude-list.json, and thereby
including it in ECLAIR's regular scanning, would be the best approach, I
am also fine with that.

Re: [PATCH] radix-tree: don't left-shift negative values

[Andrew Cooper]

On 13/02/2025 7:26 pm, Stefano Stabellini wrote:
> On Thu, 13 Feb 2025, Luca Fancellu wrote:
>>> On 13 Feb 2025, at 15:42, Nicola Vetrini <nicola.vetrini@bugseng.com> wrote:
>>> On 2025-02-13 16:32, Nicola Vetrini wrote:
>>>> On 2025-02-13 16:01, Jan Beulich wrote:
>>>>> On 13.02.2025 15:52, Nicola Vetrini wrote:
>>>>>> On 2025-02-13 15:22, Jan Beulich wrote:
>>>>>>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
>>>>>>> left shifting negative values is UB. Use an unsigned intermediate type,
>>>>>>> reducing the impact to implementation defined behavior (for the
>>>>>>> unsigned->signed conversion).
>>>>>>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric
>>>>>>> 'l'
>>>>>>> tag.
>>>>>>> No difference in generated code, at least on x86.
>>>>>>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
>>>>>>> radix_tree_int_to_ptr()")
>>>>>>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
>>>>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>>>>> ---
>>>>>>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
>>>>>>>         tagging.ecl the codebase is clean for this rule, aiui.
>>>>>> radix-tree.{c,h} is out of scope:
>>>>>> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
>>>>>> docs/misra/exclude-list.json:153:            "rel_path":
>>>>>> "common/radix-tree.c",
>>>>> Is there a record of why they are excluded? Is it further explainable
>>>>> why exclude-list.json mentions only the .c file and out_of_scope.ecl
>>>>> mentions only the .h one? Shouldn't different parts be in sync?
>>>> exclude-list.json is used to generate a configuration file for ECLAIR just before the analysis starts, so effectively both are excluded. It's a good point however to have only one file to handle exclusions, and use that file to generate the exclusion list dynamically, but then someone might want to exclude certain files only in some analyses and not others, which is not a good fit for exclude-list.json as it is now.
>>>> @Stefano, thoughts?
>>> I forgot to address the first question: the (vague) reasons are listed in exclude-list.json as the "comment" field; in most cases, it's because the files have been imported from Linux, but the full rationale is something that should be asked to the original author, which is Luca Fancellu.
>> So IIRC the full rationale is that since some files are imported from Linux, we would like to maintain them as they are
>> in order to ease backports. Misra fixes can be done, but they need to be upstreamed to Linux and backported to Xen.
>>
>> Probably a re-evaluation could be done by the maintainers to see if some of these files could be removed from the exclusion
>> list.
> Yes, it is as Luca said. At the beginning of the project, we reviewed
> the codebase to define what was in scope and what was out of scope. One
> area of contention was the files imported from Linux. Many of these
> files were declared out of scope because we wanted to retain the ability
> to easily synchronize them with their corresponding files in Linux.  
>
> Now, years have passed, and we have gained significant experience from
> running this project. It is completely acceptable to redefine the scope,
> including making changes to exclude-list.json.
>
> However, we do not necessarily need to modify exclude-list.json to
> accept a single, clearly beneficial fix like this one. So, Jan, feel
> free to proceed and commit it.  
>
> I just wanted to provide some background. If you believe that removing
> common/radix-tree.c from docs/misra/exclude-list.json, and thereby
> including it in ECLAIR's regular scanning, would be the best approach, I
> am also fine with that.

I agree with Jan that it's important that we have a single source of truth.

Furthermore, it is critical that the justification of why things are in
certain categories are identified.  It only needs to be a single
sentence in a comment, but a developer needs to be able to look at the
file and figure out *why* a decision was taken...

... because as Stefano says, decisions change over time, opinions and
scope change, etc.


As to the specifics of radix-tree, I personally think is rather
disingenuous to say "here's a data-structure fundamental to the
operation of Xen, but because the code is written in Linux style we
chose to ignore problems in it."   A certifier would be well with their
rights to tell you where to go if you tried to argue that point.

It is code in Xen, and critical to Xen's behaviour.  It doesn't matter
if you want to do a Linux-first or Xen-first approach to fixing issues;
the issues need fixing.

~Andrew

Re: [PATCH] radix-tree: don't left-shift negative values

[Stefano Stabellini]

[-- Attachment #1: Type: text/plain, Size: 6785 bytes --]

On Thu, 13 Feb 2025, Andrew Cooper wrote:
> On 13/02/2025 7:26 pm, Stefano Stabellini wrote:
> > On Thu, 13 Feb 2025, Luca Fancellu wrote:
> >>> On 13 Feb 2025, at 15:42, Nicola Vetrini <nicola.vetrini@bugseng.com> wrote:
> >>> On 2025-02-13 16:32, Nicola Vetrini wrote:
> >>>> On 2025-02-13 16:01, Jan Beulich wrote:
> >>>>> On 13.02.2025 15:52, Nicola Vetrini wrote:
> >>>>>> On 2025-02-13 15:22, Jan Beulich wrote:
> >>>>>>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
> >>>>>>> left shifting negative values is UB. Use an unsigned intermediate type,
> >>>>>>> reducing the impact to implementation defined behavior (for the
> >>>>>>> unsigned->signed conversion).
> >>>>>>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric
> >>>>>>> 'l'
> >>>>>>> tag.
> >>>>>>> No difference in generated code, at least on x86.
> >>>>>>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
> >>>>>>> radix_tree_int_to_ptr()")
> >>>>>>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
> >>>>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> >>>>>>> ---
> >>>>>>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
> >>>>>>>         tagging.ecl the codebase is clean for this rule, aiui.
> >>>>>> radix-tree.{c,h} is out of scope:
> >>>>>> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
> >>>>>> docs/misra/exclude-list.json:153:            "rel_path":
> >>>>>> "common/radix-tree.c",
> >>>>> Is there a record of why they are excluded? Is it further explainable
> >>>>> why exclude-list.json mentions only the .c file and out_of_scope.ecl
> >>>>> mentions only the .h one? Shouldn't different parts be in sync?
> >>>> exclude-list.json is used to generate a configuration file for ECLAIR just before the analysis starts, so effectively both are excluded. It's a good point however to have only one file to handle exclusions, and use that file to generate the exclusion list dynamically, but then someone might want to exclude certain files only in some analyses and not others, which is not a good fit for exclude-list.json as it is now.
> >>>> @Stefano, thoughts?
> >>> I forgot to address the first question: the (vague) reasons are listed in exclude-list.json as the "comment" field; in most cases, it's because the files have been imported from Linux, but the full rationale is something that should be asked to the original author, which is Luca Fancellu.
> >> So IIRC the full rationale is that since some files are imported from Linux, we would like to maintain them as they are
> >> in order to ease backports. Misra fixes can be done, but they need to be upstreamed to Linux and backported to Xen.
> >>
> >> Probably a re-evaluation could be done by the maintainers to see if some of these files could be removed from the exclusion
> >> list.
> > Yes, it is as Luca said. At the beginning of the project, we reviewed
> > the codebase to define what was in scope and what was out of scope. One
> > area of contention was the files imported from Linux. Many of these
> > files were declared out of scope because we wanted to retain the ability
> > to easily synchronize them with their corresponding files in Linux.  
> >
> > Now, years have passed, and we have gained significant experience from
> > running this project. It is completely acceptable to redefine the scope,
> > including making changes to exclude-list.json.
> >
> > However, we do not necessarily need to modify exclude-list.json to
> > accept a single, clearly beneficial fix like this one. So, Jan, feel
> > free to proceed and commit it.  
> >
> > I just wanted to provide some background. If you believe that removing
> > common/radix-tree.c from docs/misra/exclude-list.json, and thereby
> > including it in ECLAIR's regular scanning, would be the best approach, I
> > am also fine with that.
> 
> I agree with Jan that it's important that we have a single source of truth.
> 
> Furthermore, it is critical that the justification of why things are in
> certain categories are identified.  It only needs to be a single
> sentence in a comment, but a developer needs to be able to look at the
> file and figure out *why* a decision was taken...
> 
> ... because as Stefano says, decisions change over time, opinions and
> scope change, etc.

The single source of truth is supposed to be
docs/misra/exclude-list.json, which has an entry for radix-tree with a
simple explanation:

        {
            "rel_path": "common/radix-tree.c",
            "comment": "Imported from Linux, ignore for now"
        },

However, reading the code and also Nicola's answer, I can see that
automation/eclair_analysis/ECLAIR/out_of_scope.ecl is adding extra
excludes on top of exclude-list.json. There are three groups of files:

1) Intel specific source files are out of scope
2) Build tools are out of scope
3) Out of scope headers


Nicola, I think that 2) and 3) should be in
docs/misra/exclude-list.json. Do you recall why it was not done this way
in the first place? Can we make the change now?


In regard to 1), I would leave it in out_of_scope.ecl for now. Ideally
we wouldn't need an exclude list for Intel files because we should be
able to exclude them using Kconfig options. But of course when we
started the MISRA project there was no way to do that and even now the
Kconfig infrastructure might not be able to remove all the files in
group 1).

As we are working on adding a second ECLAIR scan with a larger
configuration, it would make sense to add all the files in group 1) to
that scan.

I would prefer to keep them disabled in the smaller ECLAIR scan
configuration that we have today for a simple reason: I think our
priority for that scan should be to reach zero violations as fast as
possible to mark as many rules as possible as blocking. I am hesitant to
increase the scope until we do that because it could be
counter-productive.


> As to the specifics of radix-tree, I personally think is rather
> disingenuous to say "here's a data-structure fundamental to the
> operation of Xen, but because the code is written in Linux style we
> chose to ignore problems in it."   A certifier would be well with their
> rights to tell you where to go if you tried to argue that point.
> 
> It is code in Xen, and critical to Xen's behaviour.  It doesn't matter
> if you want to do a Linux-first or Xen-first approach to fixing issues;
> the issues need fixing.

I am happy to make the relevant changes to docs/misra/exclude-list.json
(and automation/eclair_analysis/ECLAIR/out_of_scope.ecl.)

Jan do you also agree as well? If yes, I'll work out exactly how to
proceed based on whether removing radix-tree from exclude-list.json
trigger other violations or not.

Re: [PATCH] radix-tree: don't left-shift negative values

[Jan Beulich]

On 13.02.2025 22:46, Stefano Stabellini wrote:
> On Thu, 13 Feb 2025, Andrew Cooper wrote:
>> On 13/02/2025 7:26 pm, Stefano Stabellini wrote:
>>> On Thu, 13 Feb 2025, Luca Fancellu wrote:
>>>>> On 13 Feb 2025, at 15:42, Nicola Vetrini <nicola.vetrini@bugseng.com> wrote:
>>>>> On 2025-02-13 16:32, Nicola Vetrini wrote:
>>>>>> On 2025-02-13 16:01, Jan Beulich wrote:
>>>>>>> On 13.02.2025 15:52, Nicola Vetrini wrote:
>>>>>>>> On 2025-02-13 15:22, Jan Beulich wrote:
>>>>>>>>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
>>>>>>>>> left shifting negative values is UB. Use an unsigned intermediate type,
>>>>>>>>> reducing the impact to implementation defined behavior (for the
>>>>>>>>> unsigned->signed conversion).
>>>>>>>>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric
>>>>>>>>> 'l'
>>>>>>>>> tag.
>>>>>>>>> No difference in generated code, at least on x86.
>>>>>>>>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
>>>>>>>>> radix_tree_int_to_ptr()")
>>>>>>>>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
>>>>>>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>>>>>>> ---
>>>>>>>>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
>>>>>>>>>         tagging.ecl the codebase is clean for this rule, aiui.
>>>>>>>> radix-tree.{c,h} is out of scope:
>>>>>>>> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
>>>>>>>> docs/misra/exclude-list.json:153:            "rel_path":
>>>>>>>> "common/radix-tree.c",
>>>>>>> Is there a record of why they are excluded? Is it further explainable
>>>>>>> why exclude-list.json mentions only the .c file and out_of_scope.ecl
>>>>>>> mentions only the .h one? Shouldn't different parts be in sync?
>>>>>> exclude-list.json is used to generate a configuration file for ECLAIR just before the analysis starts, so effectively both are excluded. It's a good point however to have only one file to handle exclusions, and use that file to generate the exclusion list dynamically, but then someone might want to exclude certain files only in some analyses and not others, which is not a good fit for exclude-list.json as it is now.
>>>>>> @Stefano, thoughts?
>>>>> I forgot to address the first question: the (vague) reasons are listed in exclude-list.json as the "comment" field; in most cases, it's because the files have been imported from Linux, but the full rationale is something that should be asked to the original author, which is Luca Fancellu.
>>>> So IIRC the full rationale is that since some files are imported from Linux, we would like to maintain them as they are
>>>> in order to ease backports. Misra fixes can be done, but they need to be upstreamed to Linux and backported to Xen.
>>>>
>>>> Probably a re-evaluation could be done by the maintainers to see if some of these files could be removed from the exclusion
>>>> list.
>>> Yes, it is as Luca said. At the beginning of the project, we reviewed
>>> the codebase to define what was in scope and what was out of scope. One
>>> area of contention was the files imported from Linux. Many of these
>>> files were declared out of scope because we wanted to retain the ability
>>> to easily synchronize them with their corresponding files in Linux.  
>>>
>>> Now, years have passed, and we have gained significant experience from
>>> running this project. It is completely acceptable to redefine the scope,
>>> including making changes to exclude-list.json.
>>>
>>> However, we do not necessarily need to modify exclude-list.json to
>>> accept a single, clearly beneficial fix like this one. So, Jan, feel
>>> free to proceed and commit it.  
>>>
>>> I just wanted to provide some background. If you believe that removing
>>> common/radix-tree.c from docs/misra/exclude-list.json, and thereby
>>> including it in ECLAIR's regular scanning, would be the best approach, I
>>> am also fine with that.
>>
>> I agree with Jan that it's important that we have a single source of truth.
>>
>> Furthermore, it is critical that the justification of why things are in
>> certain categories are identified.  It only needs to be a single
>> sentence in a comment, but a developer needs to be able to look at the
>> file and figure out *why* a decision was taken...
>>
>> ... because as Stefano says, decisions change over time, opinions and
>> scope change, etc.
> 
> The single source of truth is supposed to be
> docs/misra/exclude-list.json, which has an entry for radix-tree with a
> simple explanation:
> 
>         {
>             "rel_path": "common/radix-tree.c",
>             "comment": "Imported from Linux, ignore for now"
>         },

At the risk of stating the obvious: That's radix-tree.c only, not
radix-tree.h.

Jan

Re: [PATCH] radix-tree: don't left-shift negative values

[Jan Beulich]

On 13.02.2025 20:26, Stefano Stabellini wrote:
> On Thu, 13 Feb 2025, Luca Fancellu wrote:
>>> On 13 Feb 2025, at 15:42, Nicola Vetrini <nicola.vetrini@bugseng.com> wrote:
>>> On 2025-02-13 16:32, Nicola Vetrini wrote:
>>>> On 2025-02-13 16:01, Jan Beulich wrote:
>>>>> On 13.02.2025 15:52, Nicola Vetrini wrote:
>>>>>> On 2025-02-13 15:22, Jan Beulich wrote:
>>>>>>> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
>>>>>>> left shifting negative values is UB. Use an unsigned intermediate type,
>>>>>>> reducing the impact to implementation defined behavior (for the
>>>>>>> unsigned->signed conversion).
>>>>>>> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric
>>>>>>> 'l'
>>>>>>> tag.
>>>>>>> No difference in generated code, at least on x86.
>>>>>>> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions)
>>>>>>> radix_tree_int_to_ptr()")
>>>>>>> Reported-by: Teddy Astie <teddy.astie@vates.tech>
>>>>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>>>>> ---
>>>>>>> Bugseng: Why was the 7.3 violation not spotted by Eclair? According to
>>>>>>>         tagging.ecl the codebase is clean for this rule, aiui.
>>>>>> radix-tree.{c,h} is out of scope:
>>>>>> automation/eclair_analysis/ECLAIR/out_of_scope.ecl:32:-file_tag+={out_of_scope,"^xen/include/xen/radix-tree\\.h$"}
>>>>>> docs/misra/exclude-list.json:153:            "rel_path":
>>>>>> "common/radix-tree.c",
>>>>> Is there a record of why they are excluded? Is it further explainable
>>>>> why exclude-list.json mentions only the .c file and out_of_scope.ecl
>>>>> mentions only the .h one? Shouldn't different parts be in sync?
>>>> exclude-list.json is used to generate a configuration file for ECLAIR just before the analysis starts, so effectively both are excluded. It's a good point however to have only one file to handle exclusions, and use that file to generate the exclusion list dynamically, but then someone might want to exclude certain files only in some analyses and not others, which is not a good fit for exclude-list.json as it is now.
>>>> @Stefano, thoughts?
>>>
>>> I forgot to address the first question: the (vague) reasons are listed in exclude-list.json as the "comment" field; in most cases, it's because the files have been imported from Linux, but the full rationale is something that should be asked to the original author, which is Luca Fancellu.
>>
>> So IIRC the full rationale is that since some files are imported from Linux, we would like to maintain them as they are
>> in order to ease backports. Misra fixes can be done, but they need to be upstreamed to Linux and backported to Xen.
>>
>> Probably a re-evaluation could be done by the maintainers to see if some of these files could be removed from the exclusion
>> list.
> 
> Yes, it is as Luca said. At the beginning of the project, we reviewed
> the codebase to define what was in scope and what was out of scope. One
> area of contention was the files imported from Linux. Many of these
> files were declared out of scope because we wanted to retain the ability
> to easily synchronize them with their corresponding files in Linux.  
> 
> Now, years have passed, and we have gained significant experience from
> running this project. It is completely acceptable to redefine the scope,
> including making changes to exclude-list.json.
> 
> However, we do not necessarily need to modify exclude-list.json to
> accept a single, clearly beneficial fix like this one. So, Jan, feel
> free to proceed and commit it.  

FTAOD - I didn't think there was anything in the way of me doing so, once
the tree re-opens. Question here is how many _else_ issues there are in
the radix tree code we've got (and in anything else presently excluded).

Jan

Re: [PATCH] radix-tree: don't left-shift negative values

[Andrew Cooper]

On 13/02/2025 2:22 pm, Jan Beulich wrote:
> Any (signed) integer is okay to pass into radix_tree_int_to_ptr(), yet
> left shifting negative values is UB. Use an unsigned intermediate type,
> reducing the impact to implementation defined behavior (for the
> unsigned->signed conversion).
>
> Also please Misra C:2012 rule 7.3 by dropping the lower case numeric 'l'
> tag.
>
> No difference in generated code, at least on x86.
>
> Fixes: b004883e29bb ("Simplify and build-fix (for some gcc versions) radix_tree_int_to_ptr()")
> Reported-by: Teddy Astie <teddy.astie@vates.tech>
> Signed-off-by: Jan Beulich <jbeulich@suse.com>

Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>