1

Every post about memory allocation seems to either explain how mmap is used or how sbrk was used, without regard for how these can be contextualized with the heap.

I have gathered that the heap plays an almost insignificant role in memory allocations -- in fact, I am not sure what it does :D, and I request that someone dis-confuse me.


This is what I understand:

1) When memory is malloced, the end of the uninitialized data segment, the BSS, is expanded. This expansion (which moves an address x to, say, x-n) takes place as a result of a call to sbrk. In this model, memory is allocated into the n bytes (assuming that each address is in correspondence with one byte) that sbrk decreased the position of the BSS segment header by. This model is now obsolete. Some define the heap to be the space that is the aggregate of all such expansions. Others do not -- in the latter case, what does the heap do?

2) In modern memory allocation schemes, a heap does exist (for what reason, again, I am not sure). To allocate memory, malloc internally uses mmap to store data into memory regions that are a collection of pages. These memory regions are independent of the heap.


TLDR:

For old sytems: If memory allocations are stored into address space that is obtained after increasing the offset of the end BSS, then does a heap serve any purpose?

For newer systems: Granted that mmap is mainly used for memory allocations, then what purpose does the heap serve?

In both cases, does the heap really do anything useful?

  • Are you asking about the concepts of dynamic memory allocation or about some specific system/implementation? Should this be on Stack Exchange as being about programming generally? Does the Q What and where are the stack and heap? over there in SE answer your question? Or are you asking why an OS would provide brk() if no-one uses it? – ilkkachu Dec 17 '17 at 18:29
1

mmap and sbrk are the system calls that the kernel provides for allocating address space to processes. These calls change the mapping of virtual addresses to physical page frames. Addressing memory outside the address limits of these mappings is a strict no-no, and results in a segmentation fault. This is the low level interface the kernel provides to a process, and the memory area that ends with the brk address is commonly called the heap.

The kernel does not know anything about malloc or free, these are library functions in libc. Libc maintains data structures and records which memory areas are free from the point of view of the memory allocation, for example as the . A call to malloc does not necessarily result in a call to sbrk or mmap (depending on how Libc implements dynamic memory allocation) to expand the mappings, if a call to malloc can be satisfied by reusing previously freed memory areas.

  • My answer maybe simplified things a bit regarding the "no-no" limits, because there's of course also the stack and static memory allocations for the text segment, the data segment and the BSS segment. My answer applies to dynamic memory allocation. – Johan Myréen Dec 17 '17 at 15:38
0

"The heap" is a high-level idea, not a low-level implementation. In C, the heap is whatever pool of memory malloc() uses to supply allocations.

Here's a fun, simple memory allocator implementation:

static char *heap[1000000];
int top = 0;

void *malloc(int size) {
    void *ret = &heap[top];
    top += size;
    return ret;
}

void free(void *ptr) {
    /* Eh; freeing is too hard */
    return;
}

This is an awful allocator, but for the right kind of program and if your system and compiler are forgiving about things like memory alignment, it sort of works. Its heap is the heap[] array, and it builds it at compile time using an array declaration, rather than assembling one with sbrk() or mmap().

A "real" allocator works the same way. When malloc() is called, it takes a small part of its pool of memory (its heap) and reserves it for that allocation. There are two important differences:

  • The real allocator knows how to free() an allocation so it can use it again later.
  • The real allocator can increase the size of its heap, by asking the operating system for more memory (using sbrk() or mmap()) when all of its existing blocks are full.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.