Malloc( ) - Decision between a new page(s) request or re-cycling previously allocated memory

Question

I am relatively new to 'C' and this doubt has been bugging me for days. Hope you guys can come to the rescue!

I can't seem to fathom how and when malloc( ) decides between recycling the memory that was previously allocated, now freed from the same process and requesting the OS for a new page(s). Can you guys help me understand the underlying mechanism? It will be greatly appreciated!

Here is a sample test code I have:

#include <stdio.h>
#include <stdlib.h>

int main(){

    char *ptr;
    int mem_size1, mem_size2; 
    printf("\nEnter the size (in bytes) for malloc: ");
    scanf("%d", &mem_size1);
    ptr = (char *)malloc(mem_size1);
    if (ptr!=NULL){
        printf("\nAllocated %d bytes at addr=%p\n\n", mem_size1, ptr);
    }
    free(ptr); //free-up the addresses for re-allocation

    printf("\nAgain, enter the size (in bytes) for malloc: ");
    scanf("%d", &mem_size2);
    ptr = (char *)malloc(sizeof(char)*mem_size2);
    if (ptr!=NULL){
        //check if the memory address is being re-allocated
        printf("\nAllocated %d bytes at addr=%p\n\n", mem_size2, ptr);
    }
    free(ptr); //free-up the addresses for re-allocation
return(0);
}

Here is my output sequence:

Case I: With 10 bytes as the initial allocation size and 24 bytes as re-allocation size

Enter the size (in bytes) for malloc: 10

Allocated 10 bytes at addr=9C7010 

Again, enter the size (in bytes) for malloc: 24

Allocated 24 bytes at addr=9C7010 //Same address space is being reused

Case II: With 10 bytes as the initial allocation size and 25 bytes as the re-allocation size

 Enter the size (in bytes) for malloc: 10

 Allocated 10 bytes at addr=23F6010

 Again, enter the size (in bytes) for malloc: 25

 Allocated 25 bytes at addr=23F6030 //Different address space

I am using a 64-bit Linux OS and my system pagesize is 4096B.

So, I do not understand why a completely new address space from the OS is being requested by the malloc( ) in Case II even when the re-allocation requests exceeds only by a byte. Thanks!

Answer 1

It depends on the malloc implementation, but one of the techniques involve allocate a heap space and have a pointer to the top of the heap. the memory returned must be continous, and it can increase the size of the heap when needed.

From this malloc implementation based on sbrk syscall

The OS reserves stack and heap space for processes and sbrk lets us manipulate the heap. sbrk(0) returns a pointer to the current top of the heap. sbrk(foo) increments the heap size by foo and returns a pointer to the previous top of the heap.

If you free your pointer you may get a free space in the middle of a continuous space, in this case the malloc simply marks the space as free, and then in a next allocation malloc finds the next continuous space big enough to hold the allocation you asked:

For our malloc, we’ll want to re-use free space if possible, allocating space when we can’t re-use existing space. Given that we have this linked list structure, checking if we have a free block and returning it is straightforward. When we get a request of some size, we iterate through our linked list to see if there’s a free block that’s large enough.

If we don’t find a free block, we’ll have to request space from the OS using sbrk and add our new block to the end of the linked list.

Answer 2

wither or not malloc returns the same address from the heap for different calls to malloc has several criteria and can vary across different executions of the same program.

1) the first malloc'd memory must be passed to free() 
   before the second call to malloc

2) (here the user has no control)  
   the algorithm used by the malloc function
   can be implemented in several different ways.
   -some will keep re-allocating from the same memory address as long as space is available
   -some will cycle through a pre-allocated set of memory buffers
   -some use a randomizer for where in memory to start allocating
   -etc

One detail, most malloc calls slightly over allocate. I.E. actually allocate slightly more than is actually ask for (don't depend on this 'feature' as doing so leads to undefined behaviour and can/will lead to a seg fault event.)

In the OPs case, I suspect the malloc function used pre-allocates tables of areas to be allocated. It just happens that there is a break over between table sizes between 24 and 25