# Structures in jemalloc

> Deeper look at the structures in jemalloc memory allocator.

By Kaushik Iska · 2017-10-05 · https://iska.is/writing/structures-in-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](/img/jemalloc/jm-thread.jpeg 'Arena can correspond to multiple threads')

```java
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.

```java
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.

```java
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.

```java
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**.

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

**Picture Time**

![jemalloc structures](/img/jemalloc/structures.jpeg '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:

- [phrack.org post](http://phrack.org/issues/68/10.html)

- [Facebook's Blog Post](https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919/)

- [Reverberate's Blog Post](http://blog.reverberate.org/2009/02/one-malloc-to-rule-them-all.html)

- [Ground Truth](https://github.com/jemalloc/jemalloc)