[LLVMdev] Stack roots and function parameters

[Kenneth Uildriks]

On Tue, Sep 21, 2010 at 8:20 PM, Talin <viridia at gmail.com> wrote:
> On Mon, Sep 20, 2010 at 3:16 PM, Talin <viridia at gmail.com> wrote:
>>
>> So I've managed to get my stack crawler working and passing its unit tests
>> - this is the one I've been working on as an alternative to shadow-stack: it
>> uses only static constant data structures (no global variables or
>> thread-local data), which means that it's fully compatible with a
>> multi-threaded environment.
>> One question that has arisen, however, is what to do about function
>> parameters that may be stack roots. You can't call llvm.gcroot() on a
>> function parameter. The only thing I can think of is to copy any function
>> parameter that is a pointer, or which contains a pointer, into a local
>> variable. This seems complicated and inefficient to me (for one thing, it
>> means that every stack frame just got 8 bytes bigger due to the need to
>> store the 'this' pointer locally)  - is there a better way?

If a function parameter is a stack root, then so is the value passed
through that parameter.  Since they both point to the same thing, only
one stack root is needed to keep it reachable.  If you've got a root
for it in the caller, you don't need one in the callee for the
argument.

>
> Anyone?
> Here's some examples of what I am talking about (I'll use Java for the
> examples):
> Example 1:
>   class Foo {
>     static String st = "Hello";
>     void f1() {
>        f2(st);
>     }
>     void f2(String s) {
>       st = null; // Destroy static root
>       // Now allocate something, which might trigger
>       // a garbage collection.
>       StringBuffer sb = new StringBuffer();
>       // Is 's' still live? It's not stored in any
>       // alloca, or in any global variable. It only
>       // exists as a function parameter, which cannot
>       // be declared as a root via llvm.gcroot.

s is definitely still live assuming f1 copied st into a root before
using it, which it generally should.

>       sb.append(s);
>     }
>   }
> Example 2:
>   class Foo {
>     static void f1() {
>       // Create a new 'Foo' but don't store it
>       // anywhere.
>       new Foo().f2();
>     }
>     void f2() {
>       // Possibly trigger a collection
>       StringBuffer sb = new StringBuffer();
>       // Is 'this' still live at this point?

Again, yes, if f1 copied the result of "new Foo()" into a root.

>       sb.append(toString());
>     }
>   }
> Now, I know that the LLVM "Accurate GC" document says that any "intermediate
> values" must be declared as a GC root. My question is, does merely _loading_
> a global variable - or any mutable, non-strictly-local variable for that
> matter - count as an "intermediate" value in this case?

Yes, I believe it would.  In a multithreaded system, if you load a
pointer from a global or the heap, and some other thread changes the
pointer you loaded, you'd better have a stack root for the original
pointer value you loaded while you're using it.

Now if the global is thread-local, you don't need another root for it
since no other threads can see it.  And if you can prove that a global
isn't going to change, you also don't need another root for it.


> My problem is that I can't see how to address this without generating
> horribly bloated and inefficient code. Pretty much every function argument
> that isn't a simple integer or float will have to be copied to a hidden
> local variable before every function call - in addition to copying it to the
> stack to create the call frame. Even local variables are not immune if you
> allow closures in your language. Under this scenario, calling conventions
> that pass arguments in registers are utterly futile and save nothing,
> because everything has to get copied to the stack anyway.

One way or another, stack roots *must* get copied to the stack, so
that the GC can find them.  Remember the GC is usually running in some
other thread and can *only* find pointers that live somewhere in
memory (either the stack or the heap).

> I really wish I could simply declare function arguments as llvm.gcroots. For
> arguments that are not in registers, it would treat it just like an alloca,
> since they both represent stack slots. For arguments that are passed in
> registers, LLVM should automatically lower it to a non-register argument,
> making a copy if needed. (I can't do this myself, since I'm not supposed to
> *know* which arguments are passed in registers or not - that depends on the
> target and the code generators and such).

I *believe* the code generator has some optimizations that eliminate
redundant copies within a block.  At any rate, if you keep your stack
roots in the caller rather than the callee, then there'll be a number
of cases where the caller needs to keep that stack root for purposes
other than that one call.  In those cases, having the stack root
doesn't impose a cost you aren't already paying just to allow the GC
to work.

> That still leaves me with the problem of declaring as roots function
> arguments that are the result of complex calculations, but those are far
> fewer - declaring temporary vars for those won't bloat the code so badly.
> But having to copy every single load of a non-local variable into a
> temporary is a nightmare.

You only have to copy pointers.  If you've got a struct, you only need
to keep a root for the pointer member(s) of that struct.