CODEWITHSUNDEEP
cmemorysegmentation-faultblock
katiea
katiea

Reputation: 223

Memory Allocation with Nodes in C

I'm creating malloc for a project, and allocating space the hard way to understand how it works, but I'm getting null pointer issues.

(given) Block Structure: Linked List

 typedef struct block_hd{
  /* The blocks are maintained as a linked list */
  /* The blocks are ordered in the increasing order of addresses */
  struct block_hd* next;

  int size_status;

 }block_header;

block_header* list_head = NULL;

When I'm adding memory blocks, I'm running into an error with my temp Node. Basically, it's not dereferencing temp_node to get to its next and set it to the proper location. My print out statements:

 not empty: 4088
 there is space to add
 create temp
 f7758040
 f7754000
 00000000
 Segmentation fault (core dumped)

It's never getting to temp_node's next. Like it's not creating temp properly. Temp is pointing to headers of blocks. And I'm giving it a location. What is the problem?

My Mem_Alloc function *assume properly initiated linked list:

void* Mem_Alloc(int size)
{
if (size < 1) return NULL;
size = 1 + ((size - 1)/4);
size = size * 4;

if (list_head != NULL){

    block_header* head_node = list_head; 

    while (head_node != NULL){
        //get curr header size
        int node_size = head_node->size_status;



        printf("not empty: %d\n", node_size);

            //there is space to add
            if (node_size%2 == 0 && (size+sizeof(block_header)) < node_size){
                printf("there is space to add\n");                  

                //twocases
                if ((node_size - size - sizeof(block_header)) > 0){
                        printf("create temp\n");                        
                        block_header* temp_node = NULL;
                        temp_node = head_node + sizeof(block_header) + size;
                        printf("%08x\n", (unsigned int) temp_node);
                        printf("%08x\n", (unsigned int) head_node);
                        printf("%08x\n", (unsigned int) head_node->next);
                        printf("%08x\n", (unsigned int) temp_node->next);
                        printf("set temp next to head next\n");
                        temp_node->next = head_node->next;
                        printf("set temp size to remaining\n");
                        temp_node->size_status = (head_node->size_status - sizeof(block_header) - size);
                        printf("set head size to used status\n");
                        head_node->size_status = size + 1;
                        printf("set head next to temp\n");
                        head_node->next = temp_node;
                    }
                    else{
                        //if at end, and not enough space for another header
                        //keep current size_status - do not reduce current 
                        printf("Not enough space, set head size to used\n");
                        if (head_node->next != NULL) head_node->size_status = size + 1;

                    }


                //return location of (head_node_location+sizeof(block_header))
                return head_node + sizeof(block_header);    
            }//end if

            else{
                //headersize%2 equaled 1, so it's used - move on.
                printf("STEPPING THROUGH LINKED LIST\n");
                head_node = head_node->next;
            }
    }//end while
}//end if
return NULL;

Upvotes: 0

Views: 323

Answers (2)

jared_schmitz
jared_schmitz

Reputation: 593

You're getting tripped up by how pointer arithmetic interacts with types.

temp_node = head_node + sizeof(block_header) + size;

I assume that in this line you are trying to advance the pointer size + sizeof(block_header) bytes. But since the pointers are to block_headers, it is advancing by that byte count times the sizeof(block_header). You could do something like:

/* Advance the pointer then cast */
char *raw_tmp_node = head_node + sizeof(block_header) + size;
block_header *tmp_node = (block_header*)raw_tmp_node;

As an aside, you should read up on the importance of memory alignment. malloc guarantees that the memory it returns is suitably aligned for any type. Generally, this is done by forcing the alignment with a union, as mentioned in K&R.

union align_storage {
    most_strictly_aligned_type x; /* Usually a long; sometimes long long */
    char storage[BLOCK_SIZE];
};

Upvotes: 1

sth
sth

Reputation: 229603

temp_node is set here:

temp_node = head_node + sizeof(block_header) + size;

Incrementing pointers doesn't go by bytes, the addresses are calculated according to the type the pointer points to. So if p points to element 0 of an array of struct block_struct, then p+1 will point to the struct block_struct at index 1 and p+2 will point to the one at index 2.

The initialization of temp_node seems to assume that head_node will be incremented by a number of bytes.

You can either change your calculations to work on struct block_structs or you can cast your pointers to char* before doing the pointer arithmetic (char is one byte).

Upvotes: 2

Related Questions