6

I am trying to port an historical functional language interpreter (KRC for EMAS) to modern systems (C for Unix) and it has a garbage collector that expects to be able to scan the stack for pointers into the heap to know which pointers it must relocate when objects in the heap are moved during a GC. For this to work, all function arguments and local variables that point into the heap must be found in the stack.

Now, there was a time when the "register" keyword meant "you can put this variable in a register if you like" and otherwise it was on the stack, but nowadays all (GCC, Clang, Tinyc/tcc) C compilers seem to put local variables into registers regardless, with no way to disable this behaviour and the result is that that the GC is missing out on some values belonging to in-progress functions, failing to preserve them and corrupting the heap.

Is there a way to tell any of these compilers to use the original C semantics, whereby all local variables are on the stack unless you say "register"?

I have a few warty "solutions":

  • adding extra code everywhere to take the address of each heap-oriented local variable and passing it to a dummy function, as a way of forcing it to be in a memory location;
  • making all static functions global so as to avoid function inlining and the resultant optimising-out of the inlined function's parameters;
  • bracketing the GC() function with a stub that pushes all the machine registers onto the stack, calls the real GC() function and then pops them;

which all seem to improve matters, but are awfully hacky and unreliable.

Is there a better way to achieve the required result, of ensuring that all function parameters and local variables will be on the stack?

4
  • 1
    Have you considered using a different garbage collector? I think that e.g. the Boehme GC can be plugged into C code. Commented Mar 8, 2015 at 10:13
  • Read about calling conventions. They and their keywords define this , and some more stuff, for the compiling process .
    – icbytes
    Commented Mar 8, 2015 at 10:14
  • Yes, Ulrich, but the way the interpreter knows what heap items are in use and how to follow their contents to know what else to preserve are both very program-specific. For example, it never calls malloc(), but has a fixed-size heap of head-tail structures which it manages as it pleases, so I think that changing GC would require a complete rewrite of the program.
    – martinwguy
    Commented Mar 8, 2015 at 10:21
  • Related: stackoverflow.com/q/6682733/69456
    – alk
    Commented Mar 8, 2015 at 10:22

4 Answers 4

4

I suppose that you use a kind of "mark and sweep" GC. In such case you only need to save registers at the moment when marking phase starts. My advise is to examine your GC, find the place where the "mark and sweep" operation starts and to put a code placing all registers into an accessible memory here. setjmp is a semi-portable way to achieve this (unless you are working on sparc).

2
  • Not M&S: it has two equal-sized heaps and copies valid items from one to the other, sort of like pouring water between two buckets. Nice, the setjmp() trick, putting the environment on the stack in a portable way. Cheers!
    – martinwguy
    Commented Mar 8, 2015 at 11:01
  • 1
    The combination of a transposing GC with auto detection of pointers in system stack does not look very well. When relocating blocks in memory, your GC is probably changing values (pointers) within the system stack. It sounds dangerously. I would probably try to completely remove this GC and to link with Boehm.
    – Marian
    Commented Mar 8, 2015 at 11:30
4

Ok, that is an odd GC; well, you might have use for the volatile keyword.

It was originally meant for things like memory-mapped devices, where you'd want to force your compiler not to optimize away a variable. It's use and abuse has been a long standing topic of discussion.

Is there a better way to achieve the required result

Really really hard to answer. On one hand: obviously, yes: don't let your GC rely on things that can't be relied upon. But that means rewriting it. On the other hand: if things like additional code to ensure stack placement work, then why the hell not go for it? It's not like you're code-porting a historical interpreter for performance.

2
  • Thanks. Yes, my first attempts were to use "volatile", which is also for cases when an interrupt routine might modify some variables. I thought the cause might be that the GC modifies things that local variables point at, and that the pointed-to values might be cached, but it turns out that when a function calls another it is aware that the sub-function might modify memory, so volatile made no difference. You're right, speed is not at present an issue; the issue is ensuring that it works reliably, which these warts do not achieve.
    – martinwguy
    Commented Mar 8, 2015 at 10:33
  • 1
    If the GC takes place asynchronously, you also need to worry about the visibility of reads and writes to other CPU cores. I imagine each pointer will need to be atomic as well. This will be even worse in performance terms. I would echo other comments here: Find another approach to GC.
    – marko
    Commented Mar 8, 2015 at 15:00
0

There seems to be a simple solution to your problem: if the GC runs synchronously, for instance if called from the allocation function, it does not really matter if other functions store pointers on the stack or in registers as long as all registers are saved to the stack at some point before the GC is run and scans the stack. Wrap the GC code in a function that saves all registers on the stack and you are done. Inline assembly might be necessary for this, but setjmp should be sufficient, as mentioned by Marian.

1
  • It does. It is only ever called from inside CONS(). I'll try Marian's setjmp trick.
    – martinwguy
    Commented Mar 8, 2015 at 11:01
0

Just thought I'd let you know how it panned out. I found a couple of data items in the code that the GC wasn't being told about, put the registers on the stack with setjmp() before entering the GC, and the last thing was that some stacked variables pointed to the "tail" cell of linked lists in the heap instead of the head, to be able to append quickly. I was ignoring these as not being aligned to a cell boundary. Of these things, I would never have though t of the setjmp() trick, so many thanks. Your suggestion made the difference between the interp working and not. Blessings!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.