What does the address of allocated memory depend on?

Check out these two C codes:

char* char_pointer;
int* int_pointer;

char_pointer = (char*)malloc(5);
printf("location of char_pointer: %p\n", char_pointer);

int_pointer = (int*)malloc(10);
printf("location of int_pointer: %p\n", int_pointer);

free(char_pointer);

char_pointer = (char*)malloc(50);
printf("location of char_pointer: %p\n", char_pointer);

and

char* char_pointer;
int* int_pointer;

char_pointer = (char*)malloc(200);
printf("location of char_pointer: %p\n", char_pointer);

int_pointer = (int*)malloc(10);
printf("location of int_pointer: %p\n", int_pointer);

free(char_pointer);

char_pointer = (char*)malloc(50);
printf("location of char_pointer: %p\n", char_pointer);

The outputs are:

location of char_pointer: 0x23eb010
location of int_pointer: 0x23eb030
location of char_pointer: 0x23eb050

and

location of char_pointer: 0x1815010
location of int_pointer: 0x18150e0
location of char_pointer: 0x1815010

As you see, in first program, it decided to allocate char_pointer after int_pointer(after I freeing and reallocating) but in second program it decided to allocated char_pointer in place of freed memory 0x1815010.

The only difference between programs is the amount of memory allocated and freed.

So, my questions are:

What does the decision of allocation place depend on? (OS, compiler or hardware)

Why does "it" make a decision to allocate in place of freed memory if the amount of allocated memory is "big"?

P.S. I have read about this issue in this book

Solution

It depends on a lot of factors, and there's no simple description to describe the behavior. Every C runtime library implements malloc() differently -- you can take a look at your CRT's source code if you're curious how it works under the hood.

Here are some commonly used malloc() implementations:

Doug Lea's malloc (description)
GNU libc malloc
ptmalloc
Microsoft CRT's malloc: available in %PROGRAMFILES(X86)%\Microsoft Visual Studio <VERSION>\VC\crt\src\malloc.c if you have Visual Studio installed

The rough way most memory allocators work is that they keep track of available memory regions. When a request comes in to allocate memory, they'll see if the have a memory region available that's at least as big as the request, and if so, carve up that memory, update its internal data structures to reflect that that memory is now allocated, and return the corresponding pointer. If not enough free memory is available, the allocator will ask the OS for more virtual memory address space (typically through sbrk(2), mmap(2), or VirtualAlloc).

So if a block gets allocated and then freed, and then another request of the same size (or smaller) gets requested, often (but not always), the same or a similar pointer is returned as the first block.

If the requested allocation is very large, the allocator may decide to skip its internal block handling and instead satisfy the request directly from the OS -- when allocating hundreds of KB or more, it's usually more efficient to just directly mmap() or VirtualAlloc() that memory, rather than try to find a free block in the list of internal free memory areas. But not all allocators do that, and the exact breakover point is often variable.