Re: [PATCH] x86/gen-cpuid: correct cycle detection

[Andrew Cooper <andrew.cooper3@xxxxxxxxxx>]

On 16/07/2025 7:59 am, Jan Beulich wrote:
> With the processing done linearly (rather than recursively), checking
> whether any of the features was previously seen is wrong: That would
> e.g. trigger for this simple set of dependencies
>
>     X: [A, B]
>     A: [C]
>     B: [C]
>
> (observed in reality when making AMX-AVX512 dependent upon both
> AMX-TILE and AVX512F, causing XSAVE to see AMX-AVX512 twice in its list
> of dependents). But checking the whole accumulated set also isn't
> necessary - just checking the feature we're processing dependents of is
> sufficient. We may detect a cycle later that way, but we still will
> detect it. What we need to avoid is adding a feature again when we've
> already seen it.
>
> As a result, seeding "seen[]" with "feat" isn't necessary anymore.
>
> Fixes: fe4408d180f4 ("xen/x86: Generate deep dependencies of features")
> Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
> ---
> Doing AMX-AVX512's dependencies like mentioned above still isn't quite
> right; we really need AVX512F || AVX10, which can't be expressed right
> now.
>
> This contextually collides with patch 2 of "x86/cpu-policy: minor
> adjustments", posted almost 2 years ago and still pending (afair) any
> kind of feedback.
>
> I'd like to note that the commented out code in the loop (sitting
> between the two hunks beklow) doesn't really work for ARCH_CAPS: The
> first unused bit (between XAPIC_STATUS and OVRCLK_STATUS) triggers
>
> Traceback (most recent call last):
>   File ".../xen/../xen/tools/gen-cpuid.py", line 608, in <module>
>     sys.exit(main())
>   File ".../xen/../xen/tools/gen-cpuid.py", line 602, in main
>     crunch_numbers(state)
>   File ".../xen/../xen/tools/gen-cpuid.py", line 382, in crunch_numbers
>     (state.names[feat], repl(seen)))
>   File ".../xen/../xen/tools/gen-cpuid.py", line 378, in repl
>     return "[" + ", ".join((state.names[x] for x in l)) + "]"
>   File ".../xen/../xen/tools/gen-cpuid.py", line 378, in <genexpr>
>     return "[" + ", ".join((state.names[x] for x in l)) + "]"
> KeyError: 534
>
> (line numbers slightly shifted due to other debugging code I had added).
> My Python clearly isn't good enough to try to guess how to fix that.

I've posted a fix for this.


>
> --- a/xen/tools/gen-cpuid.py
> +++ b/xen/tools/gen-cpuid.py
> @@ -350,7 +350,7 @@ def crunch_numbers(state):
>  
>      for feat in deep_features:
>  
> -        seen = [feat]
> +        seen = []
>          to_process = list(deps[feat])
>  
>          while len(to_process):
> @@ -363,14 +363,14 @@ def crunch_numbers(state):
>  
>              f = to_process.pop(0)
>  
> -            if f in seen:
> -                raise Fail("ERROR: Cycle found with %s when processing %s"
> -                           % (state.names[f], state.names[feat]))
> +            if f == feat:
> +                raise Fail("ERROR: Cycle found with %s" % (state.names[f], ))

Despite f and feat being the same now, I think this wants to keep the
other part of the sentence.  i.e. "Cycle found when processing %s".

It's a little awkward that there's no sensible way to reverse engineer
the cycle and print it, but it's also been far too long since I last did
graph theory.

>  
> -            seen.append(f)
> -            to_process = list(set(to_process + deps.get(f, [])))
> +            if not (f in seen):
> +                seen.append(f)
> +                to_process = list(set(to_process + deps.get(f, [])))

    if f not in seen:

But this will be a simpler patch if you do:

    if f in seen:
        continue

and don't change the indentation of of seen.append()

After this fix goes in, and now because the order is less relevant, I
probably ought to rewrite this to use sets rather than lists.  I have a
suspicion it can be done better than one-at-a-time; all that matters if
we don't see a repeat feature in deps.  We don't need to check the
feature bits outside of deps because they're (by definition) leaf values.

~Andrew