Stack Manipulation

[Pie Squared]

I've read some about creating garbage collectors (for other languages)
in C, and conservative garbage collectors sometimes manipulate the
program stack to look for pointers.

How would I do it?

Where can I find functions to manipulate/find things out about the
program stack?

Also in a similar vein, how can I dump all the processor registers to
the stack?

I realize this probably isn't cross-platform AT ALL. I would just
appreciate a few pointers on how to do this, especially on Linux/x86
set ups.

Thanks

PieSquared

 

[Kenny McCormack]

I've read some about creating garbage collectors (for other languages)
in C, and conservative garbage collectors sometimes manipulate the
program stack to look for pointers.

How would I do it?

Where can I find functions to manipulate/find things out about the
program stack?

(Beavis & Butthead) He said "stack"!!!

 

[user923005]

I've read some about creating garbage collectors (for other languages)
in C, and conservative garbage collectors sometimes manipulate the
program stack to look for pointers.

How would I do it?

Where can I find functions to manipulate/find things out about the
program stack?

Also in a similar vein, how can I dump all the processor registers to
the stack?

I realize this probably isn't cross-platform AT ALL. I would just
appreciate a few pointers on how to do this, especially on Linux/x86
set ups.

http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

 

[Gordon Burditt]

I've read some about creating garbage collectors (for other languages)

in C, and conservative garbage collectors sometimes manipulate the
program stack to look for pointers.

I have to seriously wonder about any garbage collector that *modified*
the stack to look for pointers (in ways other than normal function
call linkage).

It is possible to get an approximation of the value of the stack
pointer (assuming there really is a stack) by declaring an auto
variable and taking its address. Now, you need to know what direction
the stack grows (likely to be fixed for a given CPU), and where it
started (maybe take the address of an auto variable in main(), or
from before main() was invoked). This gives you the boundaries of
the stack. Now you can look for things that might be pointers in
that memory range.

How would I do it?

Where can I find functions to manipulate/find things out about the
program stack?

Once you have an approximation of the value of the stack pointer,
put it in a pointer variable and use it.

Also in a similar vein, how can I dump all the processor registers to
the stack?

There's no portable way, but calling a function may save all the
registers that need to be preserved across function calls.

What's where in the stack frame is very compiler-specific (and to
some extent, compiler-option-specific). Try compiling a few C
functions that call each other to assembly language, read the
code, and figure out what goes where, and how things are passed
between functions.

 

[Richard Tobin]

I've read some about creating garbage collectors (for other languages)
in C, and conservative garbage collectors sometimes manipulate the
program stack to look for pointers.

How would I do it?

Where can I find functions to manipulate/find things out about the
program stack?

Also in a similar vein, how can I dump all the processor registers to
the stack?

I realize this probably isn't cross-platform AT ALL. I would just
appreciate a few pointers on how to do this, especially on Linux/x86
set ups.

I'd suggest looking at the documentation and published papers
concerning the Boehm conservative garbage collector.

A quick Google brings up
http://www.hpl.hp.com/personal/Hans_Boehm/gc/
which looks like a good starting point.

-- Richard

 

[Bartc]

I've read some about creating garbage collectors (for other languages)
in C, and conservative garbage collectors sometimes manipulate the
program stack to look for pointers.

How would I do it?

Where can I find functions to manipulate/find things out about the
program stack?

Also in a similar vein, how can I dump all the processor registers to
the stack?

Have you considered using x86 assembly? It would be a lot easier! Either
properly or as in-line C statements. To dump the registers:

pusha

But, given access to the stack (almost certainly there is one), I couldn't
tell you how to traverse it looking for pointers. This would be difficult
without special access to the compiler and the runtime of the target
language. Maybe some stack location will correspond to an allocated block,
or maybe it's just coincidence.

 

[Pie Squared]

Have you considered using x86 assembly? It would be a lot easier! Either
properly or as in-line C statements. To dump the registers:

    pusha

But, given access to the stack (almost certainly there is one), I couldn't
tell you how to traverse it looking for pointers. This would be difficult
without special access to the compiler and the runtime of the target
language. Maybe some stack location will correspond to an allocated block,
or maybe it's just coincidence.

Thanks for the replies!

As for the helpful "pointer" to http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
- Thanks, but that doesn't give any hints on how to actually DO it,
not DESIGN it. (And I've probably read that at least 30 or so times by
now )

I'll look into the Boehm GC; I hadn't thought of that.

And... I don't think I understood the, "(Beavis & Butthead) He said
"stack"!!!"...

 

[Gene]

Thanks for the replies!

As for the helpful "pointer" tohttp://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
- Thanks, but that doesn't give any hints on how to actually DO it,
not DESIGN it. (And I've probably read that at least 30 or so times by
now )

I'll look into the Boehm GC; I hadn't thought of that.

And... I don't think I understood the, "(Beavis & Butthead) He said
"stack"!!!"...- Hide quoted text -

Emacs also has a conservative scan of the stack as a compile-time
option to find GC roots. The code is IMHO a little easier to
understand than Boehm.

A technique I have seen to get at registers is to use setjmp() and
then scan the jump buffer conservatively.

For what it's worth, a consensus seems to be developing that for
serious projects you cannot rely on conservative GC used with language
implementations that aren't designed for it from the outset.

I have been experimenting with augmenting and preprocessing C to allow
for perfect discovery of pointers on the stack. This augmented
language has structure like this (obviously my test case is a little
lisp interpreter)...

@defun PTR eval(PTR expr, ENV_PTR env, int line_no)
{
PTR p;

if (expr->type == O_CONS)
p = eval(cons(expr), env, line_no);
}

is rewritten to

struct __eval_stack_frame_s {
struct __stack_frame_s *prev;
PTR expr;
ENV_PTR env;
PTR p;
};

PTR __eval(struct __eval_stack_frame *__o, int line_no);

PTR eval(struct __stack_frame_s *prev, PTR expr, ENV_PTR env, int
line_no)
{
struct __eval_stack_frame_s __o = { prev, expr, env, NIL };
return __eval(&__o, line_no);
}

PTR __eval(struct __eval_stack_frame *__o, int line_no)
{
if (__o->expr->type == O_CONS)
__o->p = eval( (struct __stack_frame_s*)__o, line_no);
}

In this manner you always have access to all pointers in all stack
records through the __o stack frame chain. The method has the
overhead of passing one additional pointer per function call and also
threatening high quality register allocation of pointer variables.

The interesting thing is that the top eval() call is automatically
inlined by 3 of 3 optimizers I've tried. Then in some cases the
struct fields are fused with the original parameters so there is no
copying or extra stack space required.

This is not a new idea. I discovered after "inventing" it that it was
tried in a Smalltalk implementation with good success several years
ago.

 

[Keith Thompson]

And... I don't think I understood the, "(Beavis & Butthead) He said
"stack"!!!"...

Don't worry about it. That was written by one of our resident trolls.
Please ignore him. Really.