Finding the roots of a function on the stack

Question

I am a CS major and my class had a lab to create a linked list hold memory information (location, size, etc) to emulate a simple garbage collector in C. One of the things we were required to do was to find the base pointers of our system. The issue is that almost none of us were able to do it, and the professor has hinted that the concepts will be on the final.

The lab is over, so don't worry about this being worth a grade or anything, I'm trying to grasp the idea so I'm ready for my finals.

I'm not sure if a "root" is a common term, but the idea is that we save the location of the base of the main function, and then when we call out roots function we immediately save the location of that function, and iterate over all the memory between the two, looking for pointers that point into our linked list. The pointers that do are considered "roots."

---

Here is my code from the lab. Maybe it'll be easier just to look at it than to try and explain it. I realize it may not be great code, and that it doesn't really do anything, but I just do what they tell me.

*My issue is that my "start" and "finish" ranges inside my linked list are never pointed to while I traverse the stack, so I believe I must be doing something wrong with my pointers. my &start and &fin are always very close to the iterator, but never overlap and I don't understand why.

With both files saved as .c files compiling it should be as simple as gcc -g *.c

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>
//#include "gc_lib.h"

typedef struct hnode{

    bool used;
    long size;
    void* loc;
    struct hnode* next;
    struct hnode* prev;
}hnode;

//Globals
long HEAP_SIZE = 0;
bool AUTO_FREE = false;
void* MAIN_BASE = NULL;
void* MY_HEAP = NULL;
hnode* head = 0;


bool gc_init( long heapsize, void* main_base, bool autofree ){

    if( heapsize <= 0 )
        return false;

    HEAP_SIZE = heapsize;
    AUTO_FREE = autofree;
    MAIN_BASE = main_base;

    if( ( MY_HEAP = malloc( HEAP_SIZE ) ) == NULL )
        return false;

    return true;    
}


void* gc_malloc( unsigned long size ){

    if( size <= 0 )
        return NULL;

    //first malloc
    if( !head ){

        head = malloc( sizeof( hnode ) );
        head -> size = size;
        head -> loc = MY_HEAP;
        head -> used = true;        
        head -> prev = 0;

        hnode* hMem = malloc( sizeof( hnode ) );
        hMem -> size = HEAP_SIZE - size;
        hMem -> loc = (void*)((char*)(MY_HEAP) + size);
        hMem -> used = false;
        hMem -> next = 0;
        hMem -> prev = head;

        head -> next = hMem;

        return head -> loc;
    }

    hnode* findSpot = head;
    void* tempLoc = MY_HEAP;    
    int tempS = 0;

    while( findSpot ){

        //Used node
        if( findSpot -> used == true ){

            tempS += findSpot -> size;
            tempLoc = (void*)((char*)(MY_HEAP) + tempS);
            findSpot = findSpot -> next;
        }
        //Empty node; fits perfectly
        else if( ( findSpot -> used == false ) && ( findSpot -> size == size ) ){

            findSpot -> used = true;
            return findSpot -> loc;
        }
        //Empty node; fits imperfectly
        else if( ( findSpot -> used == false ) && ( findSpot -> size > size ) ){

            int splitSize = ( findSpot -> size ) - size;

            findSpot -> used = true;
            findSpot -> size = size; 

            hnode* newNode = malloc ( sizeof( hnode ) );
            newNode -> prev = findSpot;
            newNode -> next = findSpot -> next;
            newNode -> size = splitSize;
            newNode -> used = false;

            if( findSpot -> next )
                findSpot -> next -> prev = newNode;

            findSpot -> next = newNode;
            tempS += findSpot -> size;
            tempLoc = (void*)((char*)(MY_HEAP) + tempS);

            newNode -> loc = tempLoc;
            return findSpot -> loc;
        }
        //Empty node; too small
        else if( ( findSpot -> used == false ) && ( findSpot -> size < size ) ){

            tempS += findSpot -> size;
            tempLoc = (void*)((char*)(MY_HEAP) + tempS);
            findSpot = findSpot -> next;
        }
    }

    return NULL;
}


void print_roots( void ){

    register void* base asm("ebp");

    void* iter = base;
    printf( "Roots:\n" );

    if( head ){

        void* mBase = MAIN_BASE;
        hnode* nTemp = head;
        void* start = 0;
        void* fin = 0;

        while( iter != mBase ){

            if( nTemp )
                start = nTemp -> loc;

            while( nTemp && nTemp -> used)                
                nTemp = nTemp -> next;

            fin = nTemp -> loc + nTemp -> size;


            if( iter >= start && iter <= fin )
                fprintf( stdout, ">>>>%p\n", iter );

            printf("iter: %p\n", (iter)++ );
        }

        printf("MAIN_BASE: %p\n", MAIN_BASE );
        printf("base: %p\n", base );
        printf("\tstart: %p\n", &start );
        printf("\tfin: %p\n", &fin );
    }
}

---

Here is a testing file we were provided:

#include <stdio.h>
#include <stdbool.h>
#include <assert.h>

#include "gc_lib.h"



int main(int argc, char** argv){
    register void* base asm("ebp");
    gc_init(100, base, false);

    void* x1 = gc_malloc(8);
    assert(x1 != NULL);
    void* x2 = gc_malloc(8);
    assert(x2 != NULL);
    assert((x2 == x1 + 8) || (x2 == x1 - 8));

    printf("%p\n", x1);
    printf("%p\n", x2);

    print_roots();

    return 0;
}

Answer 1

If I'm correct, you wonder why the following condition is never satisfied, and the corresponding printf never executes:

 if( iter >= start && iter <= fin )
            fprintf( stdout, ">>>>%p\n", iter );

As far as I know, the code register void* base asm("ebp"); places the base variable in the EBP register. Although, it seems that it is merely a recommendation for compilers to place it there and therefore can get ignored - from gcc docs:

This option does not guarantee that GCC generates code that has this variable in the register you specify at all times.

Thus, obtaining the EBP value is not guaranteed.

But it doesn't seem to be the case here. iter starts from the base value, that is a pointer to wherever the void print_roots( void ) was called from (I may be wrong here, but it doesn't matter much - it points at some place in the stack). It iterates by increasing it's value until it equals MAIN_BASE, that points to a stack, where the int main(int argc, char** argv) function stores something about itself. Between these two values the local variables of the main function are expected to be found (x1 and x2), that point to someplace in the heap (where some hnode->loc points to).

The following code defines the values of the start and fin variables:

nTemp = head;
if( nTemp )
    start = nTemp -> loc;

while( nTemp && nTemp -> used)                
    nTemp = nTemp -> next;

fin = nTemp -> loc + nTemp -> size;

So, start and fin point to the heap (since any hnode in the list is a pointer to the heap), while iter points to the stack. That's why the condition iter >= start && iter <= fin is never satisfied.