Stack Manipulation

Discussion in 'C Programming' started by Pie Squared, Mar 3, 2008.

  1. Pie Squared

    Pie Squared Guest

    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
    Pie Squared, Mar 3, 2008
    #1
    1. Advertising

  2. In article <>,
    Pie Squared <> wrote:
    >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"!!!
    Kenny McCormack, Mar 4, 2008
    #2
    1. Advertising

  3. Pie Squared

    user923005 Guest

    On Mar 3, 3:48 pm, Pie Squared <> wrote:
    > 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)
    user923005, Mar 4, 2008
    #3
  4. >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.

    >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.
    Gordon Burditt, Mar 4, 2008
    #4
  5. In article <>,
    Pie Squared <> wrote:
    >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
    --
    :wq
    Richard Tobin, Mar 4, 2008
    #5
  6. Pie Squared

    Bartc Guest

    "Pie Squared" <> wrote in message
    news:...
    > 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.

    --
    Bart
    Bartc, Mar 4, 2008
    #6
  7. Pie Squared

    Pie Squared Guest

    On Mar 3, 8:49 pm, "Bartc" <> wrote:
    > "Pie Squared" <> wrote in message
    >
    > news:...
    >
    > > 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.
    >
    > --
    > Bart


    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"!!!"...
    Pie Squared, Mar 4, 2008
    #7
  8. Pie Squared

    Gene Guest

    On Mar 3, 9:18 pm, Pie Squared <> wrote:
    > On Mar 3, 8:49 pm, "Bartc" <> wrote:
    >
    >
    >
    >
    >
    > > "Pie Squared" <> wrote in message

    >
    > >news:...

    >
    > > > 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.

    >
    > > --
    > > Bart

    >
    > 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.
    Gene, Mar 4, 2008
    #8
  9. Pie Squared <> writes:
    [...]
    > 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.

    --
    Keith Thompson (The_Other_Keith) <>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Mar 5, 2008
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Surinder Singh
    Replies:
    1
    Views:
    1,175
    Richard Bos
    Dec 20, 2007
  2. Casey Hawthorne
    Replies:
    3
    Views:
    1,065
    Flash Gordon
    Nov 1, 2009
  3. Debajit Adhikary
    Replies:
    36
    Views:
    2,247
    Andre Kaufmann
    Feb 10, 2011
  4. Sam Roberts
    Replies:
    1
    Views:
    212
    Yukihiro Matsumoto
    Feb 11, 2005
  5. Kenneth McDonald

    Why stack overflow with such a small stack?

    Kenneth McDonald, Aug 30, 2007, in forum: Ruby
    Replies:
    7
    Views:
    247
    Kenneth McDonald
    Sep 1, 2007
Loading...

Share This Page