The job of malloc(3) is to turn the rather simple brk(2) facility into a service programs can actually use without getting hurt.
The archetypical malloc(3) implementation keeps track of the memory between the end of the bss section, as defined by the _end symbol, and the current brk(2) point using a linked list of chunks of memory. Each item on the list has a status as either free or used, a pointer to the next entry and in most cases to the previous as well, to speed up inserts and deletes in the list.
When a malloc(3) request comes in, the list is traversed from the front and if a free chunk big enough to hold the request is found, it is returned, if the free chunk is bigger than the size requested, a new free chunk is made from the excess and put back on the list.
When a chunk is free(3)'ed, the chunk is found in the list, its status is changed to free and if one or both of the surrounding chunks are free, they are collapsed to one.
A third kind of request, realloc(3), will resize a chunk, trying to avoid copying the contents if possible. It is seldom used, and has only had a significant impact on performance in a few special situations. The typical pattern of use is to malloc(3) a chunk of the maximum size needed, read in the data and adjust the size of the chunk to match the size of the data read using realloc(3).
For reasons of efficiency, the original implementation of malloc(3) put the small structure used to contain the next and previous pointers plus the state of the chunk right before the chunk itself.
As a matter of fact, the canonical malloc(3) implementation can be studied in the ``Old testament'', chapter 8 verse 7 [Kernighan & Ritchie]
Various optimisations can be applied to the above basic algorithm: