Bit Bucket

Introduction

This document explains an implementation of the malloc function based on buckets.

Main characteristics:

• No fragmentation inside a bucket (all blocks have the same size).
• Very fast allocation and deallocation.
• Poor memory efficiency, since block sizes are always powers of two and may waste space.

Principle of Buckets

The memory is divided into buckets, each one containing blocks of the same size.
Some important rules:

• Block sizes are always powers of 2 (8, 16, 32, ...).
• When the user requests memory of size s, we find the smallest power of 2 greater or equal to s (s2p).
• No metadata inside blocks. All metadata is stored in the bucket header.
• If no bucket exists or all are full, a new bucket is created.

Bucket Structure

Memory Management

Allocation

1. User calls malloc(s).
2. Compute s2p = smallest power of 2 ≥ s.
3. Find or create a bucket with blocks of size s2p.
4. Find the first free block.
5. Return the address of the block and mark it as used.

Free

1. Given the pointer, find the start of the memory page to locate the bucket metadata.
2. Update the free-list to mark the block as free.
3. If all blocks in a bucket are free, then munmap the bucket.

Metadata

Each bucket starts with a metadata structure, typically including:

• Block size (in the bucket).
• A free-list or a pointer to it.

This metadata allows the allocator to retrieve bucket information from any block’s address.

Free-list Implementations

There are two main approaches to represent the free-list:

Flag (Bitmap) Method

• Metadata contains a bitmap of bits, each representing a block.
• 0 = used, 1 = free.
• Easy to compute block address from its index.

Internal Linked List

• Each free block stores a pointer to the next free block.
• Metadata only stores a pointer to the first free block.
• Used blocks contain user data; free blocks act as list nodes.

danger

This method manipulates raw memory and pointers, which can lead to undefined behavior if not handled carefully.