Capture Memory Leak

[rcolyer]

Capture from function literals leaks memory. Repeatedly previewing with the leaker line uncommented leaks 2GB more each preview. Having just the nonleaker line uncommented does not do this.

function nonleaker(v) =
  0;

function leaker(v) = let(
    capture = function() 0
  )
  0;

//x = [ for (j=[1:100000]) nonleaker(rands(0,1000,200))[0] ];
x = [ for (j=[1:100000]) leaker(rands(0,1000,200))[0] ];

[thehans]

Here's a single line simplified case which leaks about 50MB per F5 preview.

x = [for (i=[1:100000]) let(capture = function() 1 ) 0 ];

I've also built OpenSCAD using LLVM's LeakSanitizer and made this log of the results (scroll down to the first "Indirect leak" to see the more significant leaks):
https://gist.github.com/thehans/9a2b58c9f400730c5223b8f67b1a8c19

The build was basically created using clang and enabling -fsanitize=address during compile and link (and linking with clang, not ld ). More info in the AddressSanitizer documentation. LeakSanitizer is automatically included as part of AddressSanitizer.

[thehans]

From some discussion on IRC, its suspected that the issue relates to shared_ptr objects forming cycles somewhere, which are then unable to be automatically destroyed in the normal way.

But I still haven't pinpointed the exact cause yet.

[rcolyer]

The cause of this appears to be that in value.h, class FunctionType for function literals stores a shared_ptr<Context>. Context, defined in context.h, contains a std::unordered_map<std::string, ValuePtr> (where ValuePtr in value.h is derived from shared_ptr) of every variable, including the function literal itself. This produces a direct shared_ptr loop which preserves the variables in the context of the function literal until program termination.

I was not able to spot a simple resolution. It appears to be a complicated side-effect of the closure nature of function literals requiring their captured contexts to stick around as long as the function literal does, combined with the extremely varied ways that function literals can be returned past the lifetime of the function. Because multiple function literals in the same context can call each other, and multiple function literals can be returned (as the function literals can reside inside of vectors), it seems to be a complicated issue of redefining ownership for this data in some more sensible manner.

If anyone has ideas of how to do this, please speak up or help.

[kintel]

After the recent shared_ptr cleanup, we may be able to more strongly define object ownership and use weak_ptr for non-owning references to such objects.

[redlizard]

I can confirm that there is a shared_ptr cycle between captured contexts. But I don't think a system with non-owning context references can fix this on its own.

Consider the following example:

apply_if_positive = function(f) function(n) n > 0 ? f(n) : n;
make_nonpositive_modulo_5 = let(
    x = apply_if_positive(function(n) x(n - 5))
) x;
echo(make_nonpositive_modulo_5(3));

This creates two mutually dependent contexts:
C1: x = [function(n) n > 0 ? f(n) : n], in context C2;
C2: f = [function(n) x(n - 5)], in context C1;
where neither context is an ancestor of the other. This cannot be replaced with non-owning references anywhere in the cycle without breaking things, unless these contexts are owned by some external memory management subsystem rather than being locally reference counted.

Most languages solve this problem with a reachability-analyzing garbage collector. Strictly immutable languages can often avoid this because they can avoid reference cycles in the first place, but openscad it not such a language; contexts can be added to after a reference to the context is captured (the example above relies on this), which makes contexts mutable for all memory-management-related intents and purposes.

I can think of a couple of solutions to this bug that use some form of reference tracing, and a few that sidestep the issue entirely:

• Capturing contexts by copying values at capture time avoids the reference loop. But it also changes the semantics of the language: it would make recursion impossible. My example above would be invalid, because of an undefined reference to x when defining x.
• We could track all contexts created during the course of a single evaluation run, and purge them all at the end of the run. This uses a lot of memory during evaluation, though; rcolyer's example wouldn't leak 2GB per run, but it would still use 2GB per run, which is quite unnecessary.
• When a context is created for an AST evaluation which then finishes, if that evaluation is one that cannot retain long-term external references to the context (module invocation, function call that returns something other than a function literal or vector, ...], that context as well as all remaining contexts created in that evaluation subtree can be deleted. This would clean up used memory as soon as possible in most cases. But not in all cases; examples can still be constructed that use unnecessarily huge amounts of memory during evaluation. It also requires careful case-specific logic for each type of context.
• We could use a simple mark-and-sweep garbage collector, which gets invoked regularly according to some schedule. With a sensible schedule, this would use constant-time extra processing power and memory per context variable, and clears out memory during evaluation close to optimally. It also makes memory management nondeterministic and not very predictable, and casts memory-management tendrils at several places in the evaluation codebase.
• Alternatively, there could be some form of incremental reachability analysis that runs each time a context or variable becomes unreachable on the stack. This could be exactly optimal in regards to memory usage, and avoid nondeterminism; but it comes at a hefty processing power cost (I think all algorithms that could be used for this require more than amortized constant processing time to clean out contexts, which could become a very substantial part of total processing time of complex evaluations). It would also be at least as complex as the mark-and-sweep GC.

Looking at these options, I'd say the best solution is to bite the bullet and write that mark-and-sweep garbage collector. The predictable-memory-management-purity alternatives do not seem worth it.

[rcolyer]

After fairly thorough discussion of these avenues and alternatives, I reluctantly concur with redlizard's above comment. A mark-and-sweep or similar garbage collector appears to be the only performant and scalable solution to this issue.

[redlizard]

I implemented this garbage collector, above.

The essence is a mark and sweep garbage collection algorithm. It doesn't keep track of roots; instead, it keeps track of all existent contexts, and when performing a sweep, it computes which contexts only have inbound references from other contexts, and those that do not are considered roots. From there a standard reachability and deletion are done.

Running time of a garbage collection run is proportional to the total size of all allocated values in the managed contexts. This consists of context variables, but also of elements of vectors in those context variables. Garbage is collected whenever this total size gets too big; to that end, vector values do some bookkeeping to keep track of this total size. Which is a bit messy, but necessary.

[rcolyer]

Fixed by #3765.