the allocator's job (a request stream to an address range)
Imagine a coat-check counter at a busy event. People keep walking up handing you coats of all sizes — a tiny scarf, a bulky parka — and you must store each one and give back a ticket. Later, in no particular order, they come back with tickets and want their coat. Your storage room is one fixed, finite space, and you decide where each coat goes. A memory allocator does exactly this job for a running program: a stream of requests come in for chunks of memory of various sizes, the program later hands chunks back, and the allocator must fit them all into one big region of the program's address space.
Stated precisely: an allocator is the code behind malloc() and free(). It is given one large, contiguous range of virtual addresses (it grows this range from the operating system with calls like sbrk() or mmap()), and it must service an unpredictable interleaved stream: malloc(size) means find me an unused block of at least size bytes and give me its address, and free(p) means the block at address p is unused again, reclaim it. The allocator never gets to see the future — it does not know what requests come next, and it cannot move a block once it has handed out the pointer, because the program is using that exact address. So it must place each block well right now, and remember, in its own bookkeeping (free lists, headers, size classes), which parts of the region are in use and which are free.
This is a genuinely hard design problem because the goals fight each other. You want allocation and freeing to be fast (ideally a handful of instructions), you want to waste little memory (not leave the region full of small unusable gaps), and you want it to scale when many threads call malloc() at once. No single policy wins on all three. Every real allocator — the system malloc, jemalloc, tcmalloc, an arena, a pool — is a specific set of answers to where do I put this block, how do I track free space, and how do I keep threads from waiting on each other. The rest of this field is those answers.
void *p1 = malloc(64); /* allocator carves a 64-byte block out of its region */ void *p2 = malloc(8); /* and an 8-byte block somewhere */ free(p1); /* now that 64 bytes is reusable -- but only there */ void *p3 = malloc(40); /* maybe reuse p1's space; allocator decides */
The allocator maps an unpredictable malloc/free stream onto one fixed region, never moving live blocks.
A general-purpose allocator cannot relocate a live block (the program holds the raw pointer), which is why fragmentation is unavoidable in the worst case — unlike a moving garbage collector, which can compact.