In the implementation of a general purpose memory allocator, the special management of small memory blocks deserves special attention. In this paper we introduce a bitmap based memory management scheme for small blocks, called the Small Bitmap Based Allocator. The algorithm is very fast, and reduces the amount of header space required.
Dynamic memory allocation involves managing the heap space to satisfy memory allocation requests. There are a large body of research papers dealing with general purpose memory allocators. Some of the well known algorithms include first fit, and best fit. [Wilson95]
With the current generation of modern computers, it has become common practice to align memory blocks on double word (8 byte) boundaries. [HP94] Normally, a memory block is preceded by its memory header. By the same alignment requirement, the memory header often occupies 8 bytes as well.
If the memory allocation is for 1024 bytes, the header overhead is quite small (8 / 1032). However, if the memory allocation is for 8 bytes, the header overhead then becomes 50%! Previous research has shown that in some programs, the median size of memory blocks is only around 14 bytes to 32 bytes [Zorn92]. In fact, for some programs, 90% of all allocated memory blocks are below 64 bytes. [Zorn92]
For small memory blocks, we need some special management schemes to reduce the amount of overhead required.
The key to reduced header space is to group a number of small memory blocks together, and share a single header among them.
struct chunkheader_st;
struct {
size_t block_size; // number of bytes per block
struct chunkheader_st *prev_ptr; // free list previous pointer
struct chunkheader_st *next_ptr; // free list next pointer
unsigned int bitmap; // allocation bitmap
} chunkheader_st;
struct {
struct chunkheader_st header; // 16 bytes header
unsigned char chunk_storage[240]; // 240 bytes of data storage
} chunk_st;
A memory chunk is always 256 bytes. With a header of 16 bytes, a memory chunk can store 240 bytes of data. Since data alignment is 8 bytes, one can put at most 30 8-byte blocks in a memory chunk. A chunk would contain identical sized blocks all closely packed together. Blocks of 8, 16, 24, 40, and 48 bytes would fit completely. Blocks of 32 and 56 bytes would leave only 16 bytes unused.
There is one free list per each unique size. This allows fast look-up of memory requests. A compact bitmap in the header states whether a block is free or not. Using binary probing, it takes no more than 5 probes of the bitmap to obtain a free block.
When an entire chunk is no longer used, it can be recycled for blocks of a different size. This feature is important to prevent excessive external fragmentation. When an entire page is no longer used, it can be returned to the operating system.
To differentiate a pointer to a small memory block, versus a pointer to a large memory block, memory for the Small Bitmap Based Allocator can be obtained from using the mmap() system call, while the large memory blocks would be obtained from using the sbrk() call. Simply testing the memory address again the address of heap top would determine if the block belongs to the management of the Small Bitmap Based Allocator.
Small Bitmap Based Allocator's header overhead compares favorably against traditional allocation methods such as First Fit, or Best Fit. The table below compares the amount of overhead per memory block.
| Data Size in Bytes | Header Overhead of Small Bitmap Based Allocator | Header Overhead of First Fit and Best Fit |
|---|---|---|
| 8 | 1/16 | 1/2 |
| 16 | 1/16 | 1/3 |
| 24 | 1/16 | 1/4 |
| 32 | 1/8 | 1/5 |
| 40 | 1/16 | 1/6 |
| 48 | 1/16 | 1/7 |
| 56 | 1/8 | 1/8 |
Small Bitmap Based Allocator is a fast memory allocation algorithm. It has low header overhead compared with traditional allocators. Small Bitmap Based Allocator is well suited to handle the small memory block request of malloc() calls.
[HP94] PA-RISC 1.1 Architecture and Instruction Set Reference Manual, Hewlett Packard, HP Part Number 09740-90039, February 1994, Third Edition
[Wilson95] Dynamic Storage Allocation: A Survey and Critical Review, Paul Wilson, Mark Johnstone, Michael Neely, and David Boles, Proc. 1995 International Workshop on Memory Management, Kinross, Scotland, UK, September 27-29, 1995, Springer Verlag LNCS
[Zorn92] Empirical Measurements of Six Allocation-intensive C Programs, Benjamin Zorn, Dirk Grunwald, Technical Report CU-CS-604-92, University of Colorado at Boulder