I realize that malloc calls mmap internally and pass NULL as the first argument to mmap so that the kernel will choose a suitable virtual address for the mapping, which means malloc will not necessarily create a mapping in the heap area(indicated by brk pointer).
If this is true, that means there will be a lot of gaps between each block in virtual memory after multiple malloc calls since each malloc return a new virtual address which is not contiguous to previous one
If there are gaps between each block, then does brk still have a reason to exist? since the definition of brk is to point to the top of the heap as the picture below shows:
Let's say the first malloc get a block(first block in the above picture) in the heap, the second malloc might get a second block whose starting address is below the first block's, then does brk points to the end of the first block or the second block? below is a picture depicting this problem:
So once we free one particular block, the allocator normally needs to coalesce adjacent free blocks with it so that those three blocks can be combined into a large free block. but since now each block is not contiguous in virtual memory, we cannot coalesce free those blocks then isn't this dynamic memory allocation very inefficient?
When malloc uses mmap, it doesn’t care about the program break. malloc has two sets of memory it uses: the heap (the area up to the program break), which it manages itself directly (using arenas in the GNU C library), and mmaped allocations, which are delegated to mmap. The program break keeps track of the first set of memory, not the second one. There’s no requirement that the second is contiguous.
Freed blocks are coalesced by their respective allocators. If the memory was allocated by malloc without mmap, that’s malloc’s responsibility (or free’s). If the memory was allocated using mmap, that’s mmap’s responsibility (or munmap’s). For mmaped blocks there might not even be any point in coalescing free blocks — if they’re removed from the address space, nothing else can be done. Coalescing can happen with mmaped blocks, but it happens on allocation, if two address space allocations are contiguous and have the same permissions.