Memory allocation is an important consideration often overlooked by users. Allocating and deallocating memory efficiently is essential for good performance. Reducing wasted memory increases the dependability of the allocator. Much research has been done on different implementations and enhancements to those implementations. Generally there are at least two memory allocators on a system, a kernel level allocator and a user-space allocator.
A memory allocator's job is to respond to memory requests and allocate memory based on its knowledge of free and used memory. Ideally, an allocator will avoid internal and external fragmentation and respond to memory requests quickly and efficiently. Unfortunately this is difficult because the allocator can only respond to the request for allocation and deallocation.
Reducing memory fragmentation is important to the design and implementation of a memory allocator. Initially when a client makes a request for memory, the allocator must respond to this request. It does this by looking to see what memory is free. The request must be satisfied by allocating a block, at least the size of the request, or larger. Internal fragmentation is the result of wasted memory in a block of allocated memory because the size requested by the client was smaller than the size of block allocated internally by the allocator; therefore, there exists a part of the block that is unusable, because it is marked as allocated memory, when in actuality it is not being used. External fragmentation is the result of blocks being allocated and freed, leaving "holes" in memory that are not contiguous and possibly not useful for continued requests because of their size. This results in unusable memory.
This discussion will **briefly** introduce three general categories of memory allocators, for background, and then specifically introduce slab allocation and its use of object caching and slab coloring.