Marking Stack Variables for Garbage Collection

Viewed 88

I'm trying to learn how to implement a simple mark-and-sweep garbage collection algorithm. I'm learning by looking at the tgc library.

I'm figuring out how to iterate through the stack to mark reachable heap allocated variables. This is done in the following lines in tgc.c:

static void tgc_mark_stack(tgc_t *gc) {

  void *stk, *bot, *top, *p;
  bot = gc->bottom; top = &stk;

  if (bot == top) { return; }

  if (bot < top) {
    for (p = top; p >= bot; p = ((char*)p) - sizeof(void*)) {
      tgc_mark_ptr(gc, *((void**)p));
    }
  }

  if (bot > top) {
    for (p = top; p <= bot; p = ((char*)p) + sizeof(void*)) {
      tgc_mark_ptr(gc, *((void**)p));
    }
  }

}

How does p = ((char*)p) - sizeof(void*) and p = ((char*)p) + sizeof(void*) not cause pointer p to overshoot or undershoot pointing at the correct address for the stack variable? As an example, my intuition is that we can possibly have something like this which wouldn't yield the correct heap address of char *:

                void *bottom ->  -----------   High address/bottom of stack
                                |           |
                                |   char a  |  1 byte
                                |           |
                                 -----------        
                                |           |
   (char*)p + sizeof(void*)  -> | char *str |  8 bytes
                                |           |
                                 ----------- 
                                |           |
                                |  int x    |  4 bytes
                                |           |
        void *p = void *top ->   ----------- 
                                |           |
                                | void *stk |  8 bytes
                                |           |
                                 -----------   Low address/top of stock

But I've tested this out, and the loop seems to work regardless of the stack layout. I figured that we'd do something like p = ((char*)p) - sizeof(char) which also seems to work but is a bit slower. Why does the method used in the above code work?

0 Answers
Related