CODEWITHSUNDEEP
cgdbsegmentation-faultbinary-treec99
zayaefs
zayaefs

Reputation: 43

Trouble with binary tree structure implementation

I'm trying to implement a memory management simulation (buddy), using a binary tree in C. The idea of how the system works is outlined here:

http://en.wikipedia.org/wiki/Buddy_memory_allocation

The first time you input a value, the code works fine, and give the desired output. The issue arrises the second time a value is input. I am using a recursive function to traverse the tree, and i'm getting an error, whereby the struct exists, however the member of the struct does not. 

 Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 1 (LWP 1)]
 0x00010b2c in allocate (node=0x401ba18a, reqSize=1000) at temp.c:95
 95         if(node->flag == 1){
 (gdb) print node
 $1 = (struct block *) 0x401ba18a
 (gdb) print node->flag
 Cannot access memory at address 0x401ba192

The relevant code is posted below, any help would really be appreciated!

 static int allocate(struct block* node, int reqSize) {
 //BASE CASES!
 printf("We've called allocate\n");
 //check if the request is too small
 if(reqSize < minSize){
     printf("The request is too small!\n");
     return -1;
 }
 //check if the request is too large
 if(reqSize > memory){
     printf("The request is too large!\n");
     return -1;
 }
 //check if the current block is already allocated
 if(node->flag == 1){
     printf("This block has been allocated!\n");
    return -1;
  }
   //var to hold returned value
   int returnVal = 0;
   //If the size of the request is less than or equal to half the node
  if(reqSize<(node->size)/2){
    printf("The size of the request is less than or equal too half the node\n");
    //check if there is a left node, if not, make one and call allocate
    if(node->left == NULL){
        printf("There's no left node so we are making one and calling allocate with     it\n");

        struct block buddy1 = { .init =1.};
        buddy1 = findSpace();
        buddy1.init = 1;
        buddy1.size = ((node->size)/2);
        printf("with the size %d\n",(node->size)/2);
        buddy1.flag = 0;
        buddy1.parent = node;
        buddy1.left = NULL;
        buddy1.right = NULL;

        struct block buddy2 = { .init =1.};
        buddy2 = findSpace();
        buddy2.init = 1;
        buddy2.size = ((node->size)/2);
        printf("with the size %d\n",(node->size)/2);
        buddy2.flag = 0;
        buddy2.parent = node;
        buddy1.left = NULL;
        buddy1.right = NULL;

        node->left = &buddy1;
        node->right = &buddy2;
        returnVal = allocate(node->left,reqSize);
        return returnVal;
    }
    //otherwise call allocate on the left node
    printf("There is a left node so we are calling allocate on it\n");
    returnVal = allocate(node->left,reqSize);

    if(returnVal == -1){
        printf("couldn't allocate a left node for some reason, so we are checking if a right node exists\n");
        if(node->right ==NULL){
            printf("it doesn't. We're making one and calling allocate on it!\n");
            struct block buddy = { .init =1.};
            buddy = findSpace();
            buddy.init = 1;
            buddy.size = ((node->size)/2);
            printf("with the size %d\n",(node->size)/2);
            buddy.flag = 0;
            buddy.parent = node;
            //node->left = NULL;
            node->right = &buddy;
            returnVal = allocate(&buddy,reqSize);
            }
            printf("it did, so we are calling allocate on it\n");
            returnVal = allocate(node->right,reqSize);
            //return returnVal;

    }
    return returnVal;
}

if(node->flag == 1){
    return -1;
}

printf("This is the node we need!\n");
node->flag = 1;
printPostOrder(&blockArr[position]);
return 1;
}

Upvotes: 0

Views: 689

Answers (1)

pat
pat

Reputation: 12749

Your buddy nodes are local variables, allocated on the stack and are destroyed when the allocate function returns. You don't show the definition of the block struct or the findSpace function, so it's hard to give more help.

Why are you partially initializing each buddy (.init is assigned a floating point 1), and then immediately overwriting the whole struct with the return value of findSpace?

The third buddy (the right one when allocate from the left failed) is not initializing it's left and right pointers to NULL like the other two buddies. There is a lot of replicated code here that might better be placed in its own function.

Typically, the tree structure is implicit, and you simply make a free list out of structs located in the front of each free block. When coalescing blocks, you can determine the address of your buddy by XORing your address with your size. All you need is a single bit per block to tell you if the buddy is free (and has a header struct), and if so, you can check the header to make sure it is the same size. The only additional storage that is required is a bit vector with 1 bit per minimum allocatable block that allows you to quickly determine the presence of headers without having to scan the free list. Oh, the free list should be doubly linked to allow you to remove elements from the middle (without having to scan the list from the start). If you are willing to add a header to allocated blocks, the usable size will no longer be a power of 2, but you can avoid the need for an external bit vector.

Upvotes: 1

Related Questions