Skip to content

Modification via pointers to locals in recursive functions #252

@michael-schwarz

Description

@michael-schwarz

After some discussion at GobCon yesterday, we were able to come up with an example where locals "escape" to recursive calls.

int rec(int i,int* ptr) {
int top;
int x = 17;
if(i == 0) {
rec(5,&x);
// Recursive call may have modified x
assert(x == 17); //UNKNOWN!
} else {
x = 31;
// ptr points to the outer x, it is unaffected by this assignment
// and should be 17
assert(*ptr == 31); //UNKNOWN!
if(top) {
ptr = &x;
}
// ptr may now point to both the inner and the outer x
*ptr = 12;
assert(*ptr == 12); //UNKNOWN!
assert(x == 12); //UNKNOWN!
}
return 0;
}
int main() {
int t;
rec(0,&t);
return 0;
}

  • The program has one call to f(0,&t).
    • This call recursively calls f(5,&x) passing a reference to its local x (Let us call this variable x0 for convenience).
      • The call to f(5,&x) then sets its x (x5) to 31. The following *ptr has &x and this is understood to refer to x5, where x0 would be correct
      • After the nondeterministic branch ptr may point to x0 and x5
      • The assignment modifies one, meaning that the asserts should be unknown
      • The call returns, having potentially modified x of its caller (x0)
    • After f(5,&x) returns x (x0) may have the values 17 or 12, the assert should fail.

@jerhard and I discussed how one could fix this: Our conclusion was to modify the enter such that ptr would point to a different copy of x (the one from the caller). In combine, one would then take the value of this outer copy in the return state of the function as the new value for the local x. This ought to be enough, as one can only refer to the outer copies of variables via pointers, and references to the variable directly refer to the instance in the current stackframe.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions