How is memory allocated on heap without a system call?

The basic idea is that when your program starts, the heap is very small, but not necessarily zero. If you only allocate (malloc) a small amount of memory, the library is able to handle it within the small amount of space it has when it is loaded. However, when malloc runs out of that space, it needs to make a system call to get more memory.

Up vote 0 down vote favorite share g+ share fb share tw.

I was wondering that if the space required on heap is not large enough such that there is no need for a brk/sbrk system all (to shift the break pointer (brk) of data segment), how does a library function (such as malloc) allocates space on heap. I am not asking about the data-structures and algorithms for heap management. I am just asking how does malloc get the address of the first location of the heap if it doesn't invoke a system call.

I am asking this because I have heard that it is not always necessary to invoke a system call (brk/sbrk) as these are only required to expand the space. Please correct me if I am wrong. Linux memory-management operating-system memory-allocation link|improve this question edited Feb 4 at 1:27 asked Feb 4 at 0:41vjain2738919 47% accept rate.

My answer at stackoverflow.com/questions/667177/heap-... shows some sample data structures for how a heap could be implemented. – Michael Feb 4 at 1:08 possible duplicate of How to implement a memory heap – Michael Feb 4 at 1:09.

The basic idea is that when your program starts, the heap is very small, but not necessarily zero. If you only allocate (malloc) a small amount of memory, the library is able to handle it within the small amount of space it has when it is loaded. However, when malloc runs out of that space, it needs to make a system call to get more memory.

That system call is often sbrk(), which moves the top of the heap's memory region up by a certain amount. Usually, the malloc library routine increases the heap by larger than what is needed for the current allocation, with the hope that future allocations can be performed w/o making a system call. Other implementations of malloc use mmap() instead -- this allows the program to create a sparse virtual memory mapping.

However, mmap() based malloc implementations do the same thing as the sbrk()-based ones: each system call reserves more memory than what is necessarily needed for the current call. One way to look at this is to trace a program that uses malloc: you'll see that for N calls to malloc, you will see M system calls (where M is much smaller than N).

J Teller: Thanks for the explanation. Actually I was taking about the case when the heap space is small that the library can handle (as you mentioned in the first para). What does calling malloc does then?

– vjain27 Feb 4 at 18:26 Let's think of a contrived and simple illustrative example. Assume that malloc starts out with a region of memory it can use, with a pointer to its base (void *base_ptr) and a count of what is free (int free_bytes). We'll refer to this as its starting bucket.

Then, when calling malloc, if the size is small enough to fit in the starting bucket, the returned pointer will be base_ptr, base_ptr+=alloc_size and free_bytes-=alloc_size. This continues until the free_bytes isn't big enough to satisfy the allocation, and then it does sbrk or mmap – J Teller Feb 8 at 17:36 Of course, my last comment skipped all the interesting data-structures, tracking of what is free, fragmentation, etc. You can look at the wikipedia article for good introduction to further reading: en.wikipedia.org/wiki/C_dynamic_memory_a... – J Teller Feb 8 at 17:39 @J Teller: This may be a stupid question but how does malloc get the base_ptr? If a system call such as sbrk or mmap is used it will return a pointer.

But if no such call is there then what is the base address? – vjain27 Feb 8 at 19:11 1 Malloc gets the base pointer essentially from the code that loads the binary (and for embedded systems, sometime the linker script). Basically, there is a convention between the launching program and the launched program, where the brand-new program "just knows" where the beginning and the end of the heap is when it is loaded.

I'll try to find a more in-depth explanation somewhere online ... – J Teller Feb 8 at 18:02.

The short answer is that it uses sbrk() to allocate a big hunk, which at that point belongs to your app process. It can then further parcel out subsections of that as individual malloc calls without needing to ask the system for anything, until it exhausts that space and needs to resort sbrk() again. You said you didn't want the details on the data structures, but suffice it to say that the implementation of malloc (i.e.

Your own process, not the OS kernel) is keeping track of which space in the region it got from the system is spoken for and which is still available to dole out as individual mallocs. It's like buying a big tract of land, then subdividing it into lots for individual houses.

Use sbrk() or mmap() — linux.die.net/man/2/sbrk, linux.die.net/man/2/mmap.

The question mentions "without a system call". – vjain27 Feb 4 at 1:01 -1: doesn't seem to answer the question at all. – Larry Gritz Feb 4 at 2:36.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.