When you try to extend your memory allocation with realloc(), does Linux arrange a part of memory, copy and destroy old one ? If so, the maximum size of realloc() is limited to less than half of total non-kernel memory.
Am I right on that, or what algorithm is currently applying ?
The glibc realloc implementation makes use of the kernel's mremap interface to extend or relocate the allocated region in the process's virtual address space without making an extra copy in physical memory. This behavior kicks in when glibc considers the allocation "large", which was anything over 128K last time I checked. For smaller allocations it'll make a copy.
mremap could fail if the process's virtual memory map doesn't have enough contiguous space available for the new allocation either at its current address or in any other unused region, but it doesn't need enough space to hold the old and new allocations at the same time.
Generally, the heap segment grows from lower address to higher address. A certain amount of heap space is allocated to the process and has to be managed by the process only.
When you extend your memory space, if space exists to extend it directly without moving old contents, it does so. Else, it copies the old contents to a new space which it finds, and then extends it from that new space. The old memory area is "freed" and can be used in further allocations if needed. However, the old space is NOT returned back to the kernel.
The amount of space that can be allocated by realloc() thus is limited only by the amount of heap space allocated to the process (size of heap segment).
Also, many Linux implementations make use of the sbrk() system call for changing process' segment sizes. You might want to have a look at this link to get a better understanding - How are sbrk/brk implemented in Linux?
