Sylvan : Crash in Lib-BDD reconstruction

[ssoelvsten]

Sylvan seems to crash due to a LACE Stack overflow during the reconstruction of the input for the RelProd benchmark. This would presumably also happen in the Apply benchmark.

[jacopol]

Could increase the stacksize through ulimit -s <size> (in KiB?)

[ssoelvsten]

The only operation that is used during reconstruction of the input (serialized BDDs) is the ITE . Simultaneously, the BDD is built bottom-up, meaning the ITE should take O(1) . Hence, the issue is something much more subtle and weird.

[ssoelvsten]

The issue lies in the fact, that Sylvan's garbage collection has the following undocumented assumption:

The number of BDD roots (i.e. references from the user's program) is smaller than the size of the Lace queue.

Hence, Sylvan breaks when the vector<sylvan:Bdd> out in common/libbdd_parser.h::reconstruct<Adapter>(...), which contains all BDD nodes for reconstruction, is larger than the Lace stack.

[ssoelvsten]

Merging that PR does not fully resolve the issue - just push the boundary of what Sylvan can deserialize. Closing this was not the intention.

[trolando]

There are two stacks here:

1. Program stack, which is set with ulimit -s, BUT, it is better to tell Lace to initialize its workers with a large enough program stack. Lace 1 uses "lace_set_stacksize" for that I think. If you need more program stack, the symptom is a hard seg fault.
2. Task stack, which is by default 100K tasks. But if you have a recursive function that requires more than 100K tasks deep for some reason, then you run into a Lace stack overflow. Now 100K tasks is 6.4MB which isn't that much, so you could initialize Lace (lace_start) with a much larger task size if necessary, or you could consider instead to do it a bit less fine grained and at some depth just go with a loop instead of recursion. This moves the data from the stack to the heap and it might even be faster.

Does that help?

[ssoelvsten]

As mentioned in the comment above, I could increase the Task stack size to be larger than the (1-level cut of the) BDD being loaded. But, that quickly grows to an absurd size. Question is, whether you believe said assumption is reasonable in practice? It seems reasonable to me that you don't want to support third-party deserialization like this.