Roadblock for user-implemented JIT compiler

[Max]

Hello gophers,

My recent attempt at creating a JIT compiler in Go to speed up my interpreter https://github.com/cosmos72/gomacro hit an early roadblock.

In its current status, it can compile integer arithmetic and struct/array/slice/pointer access for amd64 and arm64, but it cannot allocate memory or call other functions, which severely limits its usefulness (and is thus not yet used by gomacro).

The reason is: there is a requirement that Go functions must have a "stack frame descriptors registered with the runtime", in brief a "stack map" that tells which bits on the stack are pointers and which ones are not.

See https://github.com/golang/go/issues/20123 for details.

But there is no API to associate a stack map to functions generated at runtime and running on the Go stack - currently the only supported mechanism to load Go code at runtime is to open a shared library file with `plugin.Open()`

Thus JIT-generated functions must avoid triggering the garbage collector, as it would panic as described in the link above.

In turn, this means they cannot:

* allocate memory

* call other functions

* grow the stack

or do anything else that may start the GC.

Now, I understand *why* Go functions must currently have a stack map, and I see at least two possible solutions:

1. implement an API to associate a stack map to functions generated at runtime - possibly by forking the Go compiler and/or standard library

2. replace Go GC and allocator with an alternative that does not require stack maps - for example Boehm GC https://www.hboehm.info/gc/

    Here too, forking the Go compiler and/or standard library if needed.

My questions are:

a. which one of the two solutions above is easier, and how long could it take to a full-time expert?

b. does anyone have an easier solution or workaround to achieve the same goal?

Regards,

cosmos72

[Rick Hudson]

One approach is to maintain a shadow stack holding the pointers in a place the GC already knows about, like an array allocated in the heap. This can be done in Go, the language. Dereferences would use a level of indirection. Perhaps one would pass an index into the array instead of the pointer and somehow know the location of the shadow stack from a VM structures. This way the stack contains no pointers _into the heap_ so the _GC_ is happy. You might still have to deal with pointers to stack allocated objects since stacks can be moved and so forth but that is not the problem being discussed.

Go the implementation, such as the Go 1.13, has a GC that does not move heap objects. This means that to keep a heap object live the GC only needs to know about a single pointer. That’s sort of handy since now you can push the pointer onto the shadow stack and also onto the call stack since as long as the shadow stack is visible the object will not be collected. I note that this involves a barrier on all pointer writes so it is more than just a change to the calling conventions. Reads on the other hand would be full speed and not require a level of indirection or barrier unless and until Go the implementation moved to a moving collector.

I would explore this approach first since all of the pieces are under your control. Developing an ABI for stack maps would include other people with differing agendas and would likely slow you down. Likewise forking would come with the usual maintenance/merge headaches.

[Max]

Thanks for the idea Rick,

there is one detail I do not understand:

JIT code does not have a stack map **at all**, not even an empty one, thus (if I remember correctly) calling any Go function from it may trigger a GC cycle, which will find on the Go stack the "unknown" return address to the JIT function, and panic even though the JIT code itself does not use the Go stack. How can I remove such "offending" return address from the Go stack?

[Gert]

This kind of low level is way out of my league but what about using https://github.com/tinygo-org/tinygo instead to build your JIT? I only know tinygo has no garbage collector at all.

[Kevin Chadwick]

Don't let this stop you getting things done but I would hope that any newly
developed JIT might be W^X compatible?

https://flak.tedunangst.com/post/now-or-never-exec

"People like their JITs, and JITs like their executable allocations. Hopefully
most JIT engines are structured so that they have some advance knowledge of what
allocations will become executable in advance."

[Max]

Update:

I found a solution using AMD64 assembly trickery to call arbitrary Go functions from JIT code, while the JIT code is running on the Go stack and accessing Go memory.

It is extremely hackish and guaranteed to break as soon as Go function call ABI changes.

I will try to implement the same trick in ARM64 assembler - there are differences, and I am not yet sure it will work.

cosmos72

[Sokolov Yura]

Don't forget about calling to write barriers.

[Max]

On Friday, November 1, 2019 at 8:58:13 AM UTC+1, Sokolov Yura wrote:

Don't forget about calling to write barriers.

Of course.

Second update: calling arbitrary Go functions from ARM64 JIT code works too :)

See https://github.com/cosmos72/gomacro/blob/master/jit/_hide_from_stack