Skip to main content

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​

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.

Video example of a bit buckets implementation​

warning

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