Skip to content
Home

Structures in jemalloc

· First published on Medium (as "ELI5 jemalloc")

Times have changed. In modern systems, spatial locality of memory is more important than minimizing the total number of pages. Data that is allocated together is often used together. It is also optimized to reduce lock contention when multiple threads try to allocate memory.

jemalloc like every other malloc implementation, needs to support two primary API calls:

  1. Allocating memory

    • malloc: returns memory chunk
    • calloc: returns zeroed memory chunk

  2. free: Freeing allocated memory

Does OS not do this for us? Short answer, No. OS gives us two ways of requesting memory:

  1. mmap: maps device space memory (generally file system) to user space memory.

  2. brk: is used to change the program break address (which is the first location after the end of the uninitialized data segment). Increasing the program break allocates more memory, decreasing deallocates memory.

Structures

jemalloc uses the above two ways to get a memory that it will then manage for the user. To do this it uses various structures. The key structures are:

Arena

This is the highest unit of memory management structure that jemalloc uses. If we imagine a pool of arenas, each thread is given an arena based on the hash of its thread-id or a similar mechanism. This is to prevent lock contention, in an ideal case, if each thread has it’s own arena, there would be no contention.

Arena can correspond to multiple threads

class Arena {
  List<Thread> threads; // Threads that this arena is associated with
  List<Chunk> chunks; // Chunks that this arena manages
  Lock lock; // guard accesses to various things in this arena.
  RBTree<Run> runsAvailClean; // let's talk about runs in a little bit.
  // clean vs dirty = free zeroed data (calloc) vs free dirty data (malloc).
  RBTree<Run> runsAvailDirty;
  List<Bin> bins; // we will look at Bins soon.
}

Chunk

Chunks are virtual memory areas that available memory is conceptually divided into. They are typically of the same size: 2MB. Each chunk is associated with an Arena. Chunks are the highest abstraction used in jemalloc’s design, the rest of the structures described below are actually placed within a chunk somewhere.

class Chunk {
  Arena arena; // Arena that this chunk is associated with
  boolean dirtied; // this is set if the chunk has ever been dirtied
  List<Run> runs;
  // metadata about free pages for a region size
  RBTreeMultimap<RegionSize, Page> freePages;
}

Regions

A region is jemalloc term for the size of the allocation a user requests. Regions are divided into three classes according to their size, namely:

  1. small/medium: these regions are smaller than the page size (typically 4KB)

  2. large: these regions are between small/medium and huge.

  3. huge: size of these is greater than the chunk size. These are dealt with separately and not managed by arenas, they have a global allocator tree.

enum RegionSize {
  SM_2(2),
  SM_4(4),
  SM_8(8),
  SM_20(20),
  SM_40(40),
  .
  .
  .
  LARGE_2MB(2 * 1024 * 1024);

  int allocationSize;
}

Run

In essence, a chunk is broken into several runs. Each run is actually a set of one or more contiguous pages (but a run cannot be smaller than one page). Therefore, they are aligned to multiples of the page size.

class Run {
  Bin bin; // bins are further down in our discussion
  RegionSize regionSize; // the region size for this run.
  List<Page> pages; // pages that are a part of this run.
  int numFreeRegions;
  int totalNumRegions = pages.size() / regionSize;
  boolean freeRegions[totalNumRegions]; // initially all set to true
  // more metadata to quickly identify the first available region
}

The main responsibility of a run is to keep track of the state (i.e. free or used) of regions. Each run holds regions of a specific size and their state is tracked with a bitmask. Note: I simplified the bitmask to an array of booleans for clarity.

Bin

A bin is what keeps track of free regions of a specific size. All the runs in a Bin have the same region size, equal to the binRegionSize. Every Run is part of some Bin. A Bin can manage multiple Runs.

class Bin {
  RegionSize binRegionSize;
  List<Run> runs;
  Run currentRun; // current run of this bin
}

Picture Time

jemalloc structures

Example Allocation

Let’s start with a single call to malloc(2). Assuming that the smallest RegionSize we support is 2 (this is a pretty common smallest value) which corresponds to SM_2.

The Arena would start with no chunks and one Bin for every RegionSize. All the bins would start empty. The bin at index 0 in Arena.bins, would then end up with one Run, with one of its first available Page.region allocated to the caller of malloc(2). The Bin’s currentRun would be set to this Run.

If there was a follow up malloc(4) . We would to the same but for the bin at index 1 in Arena.bins. This would also have exactly one Run.

This hopefully gives you some insight into how jemalloc works. As I dug through this, i’ve noticed that theres a lot more subtleties to memory management thatn I first imagined.

References: