C/C++: query stucked at SSA procedures

[iiins0mn1a]

Still a huge database about linux kernel... Looking for some help... My non-dataflow query stucked at SSA procedures:

[2023-06-02 08:05:27] (2417s) Starting to evaluate predicate SSA#1d123fb4::SsaDefinition::getAUse#1#dispred#fff/3@a217ba72

[2023-06-02 08:05:27] (2417s) Pausing evaluation to evict 1.20GiB ARRAYS at sequence stamp o+18465268

[2023-06-02 08:05:30] (2420s) Unpausing evaluation: 564.11MiB in memory written to disk, 1.20GiB forgotten: 545.16MiB UNREACHABLE (603 items up to o+18465225) 684.33MiB NORMAL (970 items up to o+7554768)

[2023-06-02 08:05:31] (2422s) Tuple counts for project#SSA#1d123fb4::SsaDefinition::getAUse#1#dispred#fff/2@ccf0c6ud after 810ms:

                      9791114 ~0%     {2} r1 = SCAN SSA#1d123fb4::SsaDefinition::getAUse#1#dispred#fff OUTPUT In.0 'ssa', In.2 'va'

                                      return r1

[2023-06-02 08:05:32] (2422s)  >>> Created relation project#SSA#1d123fb4::SsaDefinition::getAUse#1#dispred#fff/2@ccf0c6ud with 9791114 rows and digest 9336c41l833n64h5a50p7kbhv7e.

[2023-06-02 08:05:32] (2422s) Starting to evaluate predicate _Access#8878f617::Access::getTarget#0#dispred#ff_Call#39248e3c::Call::getArgument#1#dispred#fff_Call__#join_rhs/2@d2345842

[2023-06-02 08:05:33] (2424s) Tuple counts for SSA#1d123fb4::SsaDefinition::getAUse#1#dispred#fff_120#join_rhs/3@3caf2dhr after 2.8s:

                      9791114 ~2%     {3} r1 = SCAN SSA#1d123fb4::SsaDefinition::getAUse#1#dispred#fff OUTPUT In.1 'arg0', In.2 'arg1', In.0 'arg2'

                                      return r1

[2023-06-02 08:05:34] (2424s)  >>> Created relation SSA#1d123fb4::SsaDefinition::getAUse#1#dispred#fff_120#join_rhs/3@3caf2dhr with 9791114 rows and digest cc565aqmn8pavvop1pn22ls6992.

For days, not generating any logs any more, I don't know how to fix it... and only one thread about codeql is still working on my machine. Is it still working properly and it's just slow?

Related full logs with the additional flags --tuple-counting and --debug has been packed in my own private repo, ping me if you wanna check it in detail.

[hmakholm]

Thanks for the report, @iiins0mn1a. It looks like it must be _Access#8878f617::Access::getTarget#0#dispred#ff_Call#39248e3c::Call::getArgument#1#dispred#fff_Call__#join_rhs/2 that goes catatonic somehow. It's possible that it's "working properly" as far as the QL evaluation engine is concerned, but this library code shouldn't be running for days, even for something such as the Linux kernel.

Unfortunately, tuple counts in the log will not be immediately useful, since a non-recursive predicate like that won't log out its tuple counts until it manages to complete. We might still be be able to extract some information from the --debug output, but to help with local troubleshooting, would you be willing to share the exact QL source you're executing too?

(As well as which release of CodeQL you're getting this behavior with).

[iiins0mn1a]

Hi! @hmakholm , thank you for your replying~

My query is running with codeql-cli v2.13.1.

My ql module source is the commit 2dcdc71 on the main branch.

My query source can be found in my private repo, which I've already invited you in, and you can also find full logs in the latest release like I said before.

Again, I really appreciate.

EDIT: I've tried some older ql-module library about half year ago at commit b8e1aa6 but the same situation just repeated again and again.

Now I am trying to back to the codeql-cli at version 2.11.3 and rebuild the whole database to see whether this issue can be solved....

[iiins0mn1a]

I‘ve run my query on my tiny database for testing, and I notice that it's my parameter SSA procedure to blame.

My bad query, trying to use SSA to backtrace the definition of a VariableAccess:

Field fieldFromParameter(VariableAccess va, string res, int depth) {
    legalDepth(depth) and
    exists(
        SsaDefinition ssa, Parameter para, Function func, FunctionCall fc |
        ssa.definedByParameter(para) and va = ssa.getAUse(_) and 
        para.getType() = va.getType() and 
        para.getName() = va.getTarget().getName() |
        func = para.getFunction() and fc = func.getACallToThisFunction() and 
        result = parseFieldFromExpr(fc.getArgument(para.getIndex()), res, depth -1)
        )
}

And check the related logs about _Access#8878f617::Access::getTarget#0#dispred#ff_Call#39248e3c::Call::getArgument#1#dispred#fff_Call__#join_rhs/2:

[2023-06-08 16:31:16] (0s) Tuple counts for _Access#8878f617::Access::getTarget#0#dispred#ff_Call#39248e3c::Call::getArgument#1#dispred#fff_Call__#join_rhs/2@d2345842 after 13ms:
                      41    ~0%     {3} r1 = JOIN Parameter#ed81dd8f::Parameter::getFunction#0#dispred#bf WITH Parameter#ed81dd8f::Parameter::getIndex#0#dispred#bf ON FIRST 1 OUTPUT Lhs.0, Lhs.1, Rhs.1
                      41    ~0%     {4} r2 = JOIN r1 WITH SSA#1d123fb4::SsaDefinition::definedByParameter#1#dispred#ff_10#join_rhs ON FIRST 1 OUTPUT Lhs.0, Lhs.1, Lhs.2, Rhs.1
                      41    ~0%     {5} r3 = JOIN r2 WITH Parameter#ed81dd8f::Parameter::getName#0#dispred#bf ON FIRST 1 OUTPUT Lhs.1, Lhs.0, Lhs.2, Lhs.3, Rhs.1
                      108   ~0%     {5} r4 = JOIN r3 WITH Call#39248e3c::FunctionCall::getTarget#0#dispred#ff_10#join_rhs ON FIRST 1 OUTPUT Rhs.1, Lhs.2, Lhs.1, Lhs.3, Lhs.4
                      108   ~0%     {4} r5 = JOIN r4 WITH Call#39248e3c::Call::getArgument#1#dispred#fff ON FIRST 2 OUTPUT Lhs.2, Lhs.3, Lhs.4, Rhs.2 'arg0'
                      108   ~0%     {4} r6 = JOIN r5 WITH Parameter#ed81dd8f::Parameter::getType#0#dispred#bf ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2, Lhs.3 'arg0'
                      16121 ~0%     {4} r7 = JOIN r6 WITH Expr#ef463c5d::Expr::getType#0#dispred#ff_10#join_rhs ON FIRST 1 OUTPUT Lhs.1, Rhs.1 'arg1', Lhs.2, Lhs.3 'arg0'
                      197   ~1%     {3} r8 = JOIN r7 WITH project#SSA#1d123fb4::SsaDefinition::getAUse#1#dispred#fff ON FIRST 2 OUTPUT Lhs.1 'arg1', Lhs.2, Lhs.3 'arg0'
                      197   ~1%     {4} r9 = JOIN r8 WITH Access#8878f617::Access::getTarget#0#dispred#ff ON FIRST 1 OUTPUT Rhs.1, Lhs.1, Lhs.2 'arg0', Lhs.0 'arg1'
                      133   ~1%     {2} r10 = JOIN r9 WITH Variable#7a968d4e::Variable::getName#0#dispred#bf ON FIRST 2 OUTPUT Lhs.2 'arg0', Lhs.3 'arg1'
                                    return r10

The counts of Expr::getType is eye-catching, even in my tiny database it counts to 16121. Can not imagine what's the number would be in my kernel database.

I changed my query to this:

Field fieldFromParameter(VariableAccess va, string res, int depth) {
    legalDepth(depth) and
    exists(
        SsaDefinition ssa, Parameter para, Function func, FunctionCall fc |
        ssa.definedByParameter(para) and va = ssa.getAUse(_) and 
        para.getName() = va.toString() |
        func = para.getFunction() and fc = func.getACallToThisFunction() and 
        result = parseFieldFromExpr(fc.getArgument(para.getIndex()), res, depth -1)
        )
}

Reason I wrote query like before is that, I don't know what is the most efficient way to track SSA defined by paramter, and SsaDefinition ssa always returns the whole function block, leading the dis-matching of va and para, and I have to restrict the type/name for the matching.

Once I delete these matching restrict like this:

Field fieldFromParameter(VariableAccess va, string res, int depth) {
    legalDepth(depth) and
    exists(
        SsaDefinition ssa, Parameter para, Function func, FunctionCall fc |
        ssa.definedByParameter(para) and va = ssa.getAUse(_)  |
        func = para.getFunction() and fc = func.getACallToThisFunction() and 
        result = parseFieldFromExpr(fc.getArgument(para.getIndex()), res, depth -1)
        )
}

a VariableAccess will return all Parameter in its Function...

At the very moment I'm writing this comment, I realized that maybe SSA is not needed?

Field fieldFromParameter(VariableAccess va, string res, int depth) {
    legalDepth(depth) and
    exists(
        Parameter para, Function func, FunctionCall fc |
        func = para.getFunction() and va.getEnclosingFunction() = func and
        para.getName() = va.toString() |
        fc = func.getACallToThisFunction() and 
        result = parseFieldFromExpr(fc.getArgument(para.getIndex()), res, depth -1)
        )
}

LGTM.. Do you guys have any comments on backward tracking parameters?

[iiins0mn1a]

Update, querying the predicate at the end of last comment, field-tracing worked pretty good even on the database of allyesconfig kernel, awesome!

And I think this issue should be closed, since all problems mensioned have been solved.

THX for @hmakholm , if you didn't lock in the problematic predicate, I would still be at a loss. Thank you~

[hmakholm]

Glad you solved your problem.

It does look vaguely like the r7 join in your original might have quadratic performance behavior, which would certainly ruin your day if you're analyzing something as large as an allyesconfig Linux kernel.

I'm not super familiar with how SSA isimplemented in the C/C++ library, but https://codeql.github.com/codeql-standard-libraries/cpp/semmle/code/cpp/controlflow/SSA.qll/type.SSA$SsaDefinition.html sounds like a SsaDefinition can represent several variables defined at the same place in the function's control graph, and you'd to tell which of them as the argument to .getAUse. I think you could have avoided the name-and-type match by saying .getAUse(para) instead of .getAUse(_).

In general matching on names is kind of playing with fire because the QL optimizer might somehow decide it looks like a good idea to start the evaluation by finding all the combinations of "this"s and "that"s anywhere in the program that have the same name.

In your final code I think you could profitably replace va.getEnclosingFunction() = func and para.getName() = va.toString() by va = para.getAnAccess() -- then there's no matches by name left.

[iiins0mn1a]

@hmakholm , hi~
Reason for using .getAUse(_) is an exactly mistake, I did NOT take Parameter as a Variable, thanks for your correcting.

And with same reason, I could only match va with para like this. .getAnAccess() is better for sure. Thank you again!