Understanding and implementing malloc

Question

How is malloc implemented internally ? How to implement malloc with below necessary conditions

• Malloc allocates at least the number of bytes requested

• The pointer returned by malloc points to an allocated space ( i.e. a space where the program can read or write successfully;)

• No other call to malloc will allocate this space or any portion of it, unless the pointer has been freed before.

• malloc should be tractable: malloc must terminate in as soon as possible (it should not be NP-hard !;)

• Malloc should also provide resizing and freeing.

The function obey to the following signature: Void * malloc(size_t size);

Answer 1

Solution: In order to code a malloc, we need to know where the heap begin and the break position, and of course we need to be able to move the break. We shall use sbrk() sys call to achieve this.

Sbrk (n) move the break by the given increment n (in bytes.)

Special case of sbrk: when increment is null (i.e. sbrk (0)), the returned value is the actual break address (the previous and the new break addresses are the same.) sbrk is thus used to retrieve the beginning of the heap which is the initial position of the break

Step -1 Implementation (Does not satisfy all criteria)

But at high level goal is satisfied it would move the break point by size requested and user would get memory allocation on heap, without satisfying criteria to do realloc and allow it to free 1) So we need to know where each portion begins and when we are at beginning of each portion address of next one. 2) What is the size of that portion 3) If that portion is free or not

So basically we need a list with below content

Using int for free might seem a bad idea but since struct are aligned by default it wont matter.

Another condition we have to take care is malloc must return aligned address. As seen above meta part is already aligned we just need to make sure data part is as well.

Finding a chunk Base is a global pointer to starting point of heap

Extending Heap – Its simple we just move the break point.

Now we can do our malloc function which is just wrapper of all small blocks gone through

Answer 2

brk() and sbrk()

From the manual(2) of brk().

brk() and sbrk() change the location of the program break, which defines the end of the process's data segment (i.e., the program break is the first location after the end of the uninitialized data segment). Increasing the program break has the effect of allocating memory to the process; decreasing the break deallocates memory.

brk() sets the end of the data segment to the value specified by addr, when that value is reasonable, the system has enough memory, and the process does not exceed its maximum data size (see setrlimit(2)).

sbrk() increments the program's data space by increment bytes. Calling sbrk() with an increment of 0 can be used to find the current location of the program break.

I'll use that because, honestly, I can't define those functions any better. Keep in mind that both brk() and sbrk() are system calls provided by the Linux Kernel. This is the first main difference between them and the malloc() family - malloc() and brothers are GLibC Implementations.

This SO Question will tell you exactly what they do and what is the program break, so I won't copy all of that here.

malloc(), calloc(), free()

As said, they're implemented by GLibC and manage memory blocks on the system through a list. Simply put(and let me stress the simple part), malloc() will find a free block on that list that fits the size requested by the user and return that block's address and mark it as in use; free(), on the other hand, will return that block to the list.

You can download the sources from here. As of now, the latest is 2.22. Once downloaded, extract and go to glibc-2.22/malloc. Under this directory you'll find the source for malloc (malloc.c).

Extracted from the first comment section on the malloc.c file:

The main properties of the algorithms are:

• For large (>= 512 bytes) requests, it is a pure best-fit allocator, with ties normally decided via FIFO (i.e. least recently used).

• For small (<= 64 bytes by default) requests, it is a caching allocator, that maintains pools of quickly recycled chunks.

• In between, and for combinations of large and small requests, it does the best it can trying to meet both goals at once.

• For very large requests (>= 128KB by default), it relies on system memory mapping facilities, if supported.

For a longer but slightly out of date high-level description, see this.

I recommend following that last link and reading it.

Furthermore, this PDF file which explain the inner workings of malloc() and free().