libgap API: Problems with GASMAN and StackBottom

[embray]

I have brought this issue up previously on the Sage Trac, but this is a generic problem with embedding libgap in larger applications, and it is a multi-faceted problem which I thought should be clearly summarized somewhere.

The core of the problem is that the GAP kernel, as designed, assumes that all code which uses GAP objects (tracked through the GASMAN GC), is going to run in a context with either a call to InitializeGap as a parent stack frame, or at least have a common parent with the call to InitializeGap. This is illustrated in the fact that InitializeGap uses a pointer to some main function's argc variable to set the StackBottom variable in the GC (this itself is a problem which I'll list later).

This assumption for setting StackBottom is safe for GAP itself, but not for embedding in another application with libgap. Consider the following scenario, where GAP_Initialize is called by some program embedding GAP, where GAP initialization is delayed until necessary, and possibly not called until deep into some other function call (forgive my ASCII art):

#0 main()
#1  |-<some func>
#2      |- <some func 2>
             .
             .
#42           |- <some func 3>   // 42 stack frames deep (or any arbitrary large N)
#43                |- GAP_Initialize()  // We need to use GAP now for some computation
                                         // StackBottom is set *here*

Now imagine that later in the application there is some other function called which uses GAP, but less deeply nested than the one that happened to call GAP_Initialize; it also happens to result in some nested GAP function calls:

#0 main()
#1  |-<some func>
#2      |- <some func 2>
             .
             .
#10           |- <some func 3>
#11                |- GAP_EvalString(....)
                       .
                       .
#22                    |- CALL_NARGS(....)  // Some objects are allocated on the stack here
#23                         |- CALL_NARGS(...)  // "top" of stack is here; garbage collection occurs
.  
.
.
#43 (old)          // StackBottom is still down here somewhere...

Now we have (on x86 architectures) StackTop > StackBottom. GenStackFuncBags does handle the case where top > bottom, but that "seems" to be more in order to handle different architectures where the stack grows in different directions, than some deliberate attempt to handle this case. Because now there are stack frames possibly containing young bags that haven't been swept yet which are above the current "top" of the stack.

So in the illustration above, GenStackFuncBags will sweep from #43, up through a bunch of garbage, dead stack frames, until #23, and will stop there without continuing upward to #22 and so on which may still contain some unmarked bags in local variables which will then be marked dead despite being still very much in use.

This seems to be a problem to me, but is there something obvious I'm missing in this analysis.

@sebasguts , is this problem handled in any way by GAPJulia?

As far as I can tell, if the above analysis is a real problem, then that places the onus on any application which embeds GAP to ensure that GAP is initialized very early on in the application so that anything else that uses GAP and creates GAP objects happens in a "deeper" stack frame.

For a custom application this is less of a problem as one has more control over when GAP_Initialize is actually called (though it is still a problem if one wants to avoid the overhead of GAP_Initialize by calling it lazily only when needed).

For embedding in library for another language like Python, however, it's a bigger problem. Because in writing a Python module that wraps GAP we cannot easily guarantee when that module will be imported relative to execution of the rest of the application (much less relative to Python's main() function).

There are multiple possible solutions to this problem and I'm not sure which is the best one. If nothing else it ought to be possible, when calling GAP_Initialize, to provide a custom value for what address should be set to StackBottom, rather than just assuming it's where GAP_Initialize is called from. Additionally I don't think it should double as a pointer to the argc value passed to InitializeGap, as that then places the undue burden on the client code of ensuring that whatever we pass as StackBottom points to the argc argument we want to pass to GAP.

Even then, however, it's not always obvious from the perspective of client code where an appropriate address is to set StackBottom to--this is a rather low-level concern for most users of the code. ISTM the best option is to provide some GAP_Enter and GAP_Exit gates that should surround any client code that calls libgap functions, and that possibly has GAP objects on the stack. GAP_Enter would mark the location of StackBottom from where it is called (it would likely be a macro), and would include protection for recursion (hence the need for a GAP_Exit as well).

I'm not sure that there's really a better way, unless there were some way this could be managed automatically by the API-level functions, but my experience with GAP's GC is not at a level where I can see a better way.

[dimpase]

On Julia they run GAP with Julia's GC replacing GAP's GC.

[fingolfin]

While it is true that we are using the Julia GC for GAPJulia, this StackBottom actually still is relevant there, because we still need to implement stack scanning there. But we actually deduce the correct StackBottom dynamically (Julia has multiple stacks, one for each "task", so we must do that anyway). In any case, the Julia situation is really not relevant here.

Beyond that: We are aware of this problem, and discussed it before. And we arrived essentially at the two possible solutions you also describe; and I think both should be implemented.:

• Solution 1 is to add an explicit argument to GAP_Initialize for deriving the initial StackBottom value (we might want to allow it to be NULL, and then fall back to the current behavior). This is the more convenient solution, but only workable for clients which have can insert code into their main function, or at least something high enough up in the callstack.

• Solution 2 is to add explicit GAP_Enter/GAP_Leave functions (aside: I don't like GAP_Exit, it's too confusing in light of the existence of the POSIX API exit(3)). Then any code which calls into GAP must make sure to use use them (and extra care needs to be taken if that code also keeps references to GAP objects on the stack: the GAP_Enter must come "before" those stack allocations, naturally). This is much more intrusive, but at least should work in arbitrary client code. (Actually, for GC purposes, I don't think one needs GAP_Leave at all; but it might be handy to have it for future needs, e.g. related to error handling)

One might now suggest to insert such enter/leave calls into each GAP API, but that would add a performance burden on clients which can happily use solution 1 (or a variant thereof, as GAPJulia does, in effect). Also, if the calling code has references to GAP objects on the stack, these would now be invisible (unless one adds additional dirty hacks, like: "if the previous StackBottom is "close" to the new one, then use the smaller of the two values).

[embray]

@dimpase That makes sense, though then doesn't that mean having to have a GAP compiled specifically for Julia?

[embray]

@fingolfin Thank you for at least confirming that my analysis seems right.

I agree with you about offering both solutions 1 and 2. I've already been working on a patch with which I've been experimenting with something like this. I added a _MarkStackBottomBags function in gasman.c which simply handles setting StackBottomBags to a given address; it is then wrapped by a macro that calls it with the appropriate address. For other GC's this function could be implemented differently.

Also agree about GAP_Leave as opposed to GAP_Exit. And yes, it is more "intrusive" and places more burden on the client code, but it's also quite clear for users as long as it's well documented. They don't even have to know understand what it does or what it's for: Just say "Make sure you put GAP_Enter() at the beginning of any code that uses GAP objects, and GAP_Leave() at the end of any such code."

I do believe GAP_Leave is necessary because in GAP_Enter() I increment a counter to prevent resetting StackBottom on recursive calls into GAP_Enter(), and also for debugging purposes (e.g. being able to ensure every Enter is paired correctly with an Exit.

And yes, I'm also trying to wedge better error handling into this, but right now I'm mostly concerned about the stack/GC issue.

[stevelinton]

I'm not sure if it's better than any of the other approaches, but one could deduce a valid value for stackbottom but simply scanning until you get a sigsegv. That might result in scanning too large an area, but the worst that does is a small performance hit in GC and a small increase in objects incorrectly kept alive.

Regarding GAP_Enter and GAP_Leave, since they would be very cheap you could always do GAP_Enter in some initialization code that is run once when the programme starts or the module is loaded and then GAP_Leave in coresponding finalization code. Most systems will have something in that role. and you still get to defer the cost of GAP_Initialize.

[dimpase]

doesn't that mean having to have a GAP compiled specifically for Julia?

that's correct. Also, AFAIK there is currently no way to use Julia's GC outside of Julia, which is monolitic in design and does not hav GC as a separately useable module.

And another possible scenario would be GAP built with Boehm GC rather than GASMAN.
(Boehm GC is the only option for GAPs still experimental multi-threaded HPC GAP).

[fingolfin]

@stevelinton That's a technique similar to one of the things we do in GAPJulia -- but catching sigsegv reliably and portably is a bit tricky. And if the host system already has a SIGSEGV handler, then GAP using one can be problematic. And in the context of Julia as a host, it does not work as such on OS X, because Julia already handles SIGSEGV, but via Mach-O interfaces, meaning that the "portable" approach using sigaction may not work, as @rbehrends found out the hard way (in the end, we were able to piggy back on an interface provided by Julia to solve this problem).

[fingolfin]

But to be clear: please do not worry about Boehm or Julia GC here. Perhaps on the very long run, this might become relevant, but let's focus on providing a solution that works with GASMAN first

[embray]

See #3096 for my (thus far quite successful, at least for practical purposes) prototype of a solution.