This is really neat. Somehow I always assumed realloc() copied stuff instead of using the page table.
But say you have 4K page table size. You malloc() in turn a 2K object, a 256K object, and another 2K object, ending up with 2K, 256K, 2K in memory. Then your 256K is not aligned on a page boundary. If you realloc() the 256K it has to move since it's surrounded by two objects. When you do that, you'll wind up with the two pages on the end being mapped to multiple addresses. Which is actually just fine...Interesting...
The libc memory allocator does not simply hand out memory contiguously. In your example, the 256K block will end up being 4K aligned.
In fact, that's what the article already explains: the large alloc will just end up being passed through to the kernel, which only deals at page granularity.
What the article revealed to me is that there is no guarantee a contiguous block of allocated virtual memory will be backed by contiguous physical memory. In hindsight, that should be obvious.
But what does this mean for locality? Will I be thrashing the cache if I use realloc frequently? Do I even have the promise that malloc will return unfragmented memory?
Do I even have the promise that malloc will return unfragmented memory?
What do you mean by this? malloc returns memory that is contiguous in the virtual address space. It may not be contiguous in the physical address space, but that should be irrelevant for cache behavior.
Will I be thrashing the cache if I use realloc frequently?
I suppose. But if you use realloc, you should anyway ensure that you realloc geometrically growing chunks of memory (e.g., whenever you need a new buffer, you multiply its size by a constant factor like 1.2 instead of just adding an element at a time). As a result, realloc() should be infrequent enough that it normally doesn't matter.
But say you have 4K page table size. You malloc() in turn a 2K object, a 256K object, and another 2K object, ending up with 2K, 256K, 2K in memory. Then your 256K is not aligned on a page boundary. If you realloc() the 256K it has to move since it's surrounded by two objects. When you do that, you'll wind up with the two pages on the end being mapped to multiple addresses. Which is actually just fine...Interesting...