Skip to content

Jemalloc

EDATA_BITS_ARENA_MASK = mask(EDATA_BITS_ARENA_WIDTH, EDATA_BITS_ARENA_SHIFT) module-attribute

EDATA_BITS_ARENA_SHIFT = 0 module-attribute

EDATA_BITS_ARENA_WIDTH = MALLOCX_ARENA_BITS module-attribute

EDATA_BITS_BINSHARD_MASK = mask(EDATA_BITS_BINSHARD_WIDTH, EDATA_BITS_BINSHARD_SHIFT) module-attribute

EDATA_BITS_BINSHARD_SHIFT = EDATA_BITS_NFREE_WIDTH + EDATA_BITS_NFREE_SHIFT module-attribute

EDATA_BITS_BINSHARD_WIDTH = 6 module-attribute

EDATA_BITS_COMMITTED_MASK = mask(EDATA_BITS_COMMITTED_WIDTH, EDATA_BITS_COMMITTED_SHIFT) module-attribute

EDATA_BITS_COMMITTED_SHIFT = EDATA_BITS_SLAB_WIDTH + EDATA_BITS_SLAB_SHIFT module-attribute

EDATA_BITS_COMMITTED_WIDTH = 1 module-attribute

EDATA_BITS_GUARDED_MASK = mask(EDATA_BITS_GUARDED_WIDTH, EDATA_BITS_GUARDED_SHIFT) module-attribute

EDATA_BITS_GUARDED_SHIFT = EDATA_BITS_ZEROED_WIDTH + EDATA_BITS_ZEROED_SHIFT module-attribute

EDATA_BITS_GUARDED_WIDTH = 1 module-attribute

EDATA_BITS_IS_HEAD_MASK = mask(EDATA_BITS_IS_HEAD_WIDTH, EDATA_BITS_IS_HEAD_SHIFT) module-attribute

EDATA_BITS_IS_HEAD_SHIFT = EDATA_BITS_BINSHARD_WIDTH + EDATA_BITS_BINSHARD_SHIFT module-attribute

EDATA_BITS_IS_HEAD_WIDTH = 1 module-attribute

EDATA_BITS_NFREE_MASK = mask(EDATA_BITS_NFREE_WIDTH, EDATA_BITS_NFREE_SHIFT) module-attribute

EDATA_BITS_NFREE_SHIFT = EDATA_BITS_SZIND_WIDTH + EDATA_BITS_SZIND_SHIFT module-attribute

EDATA_BITS_NFREE_WIDTH = SC_LG_SLAB_MAXREGS + 1 module-attribute

EDATA_BITS_PAI_MASK = mask(EDATA_BITS_PAI_WIDTH, EDATA_BITS_PAI_SHIFT) module-attribute

EDATA_BITS_PAI_SHIFT = EDATA_BITS_COMMITTED_WIDTH + EDATA_BITS_COMMITTED_SHIFT module-attribute

EDATA_BITS_PAI_WIDTH = 1 module-attribute

EDATA_BITS_SLAB_MASK = mask(EDATA_BITS_SLAB_WIDTH, EDATA_BITS_SLAB_SHIFT) module-attribute

EDATA_BITS_SLAB_SHIFT = EDATA_BITS_ARENA_WIDTH + EDATA_BITS_ARENA_SHIFT module-attribute

EDATA_BITS_SLAB_WIDTH = 1 module-attribute

EDATA_BITS_STATE_MASK = mask(EDATA_BITS_STATE_WIDTH, EDATA_BITS_STATE_SHIFT) module-attribute

EDATA_BITS_STATE_SHIFT = EDATA_BITS_GUARDED_WIDTH + EDATA_BITS_GUARDED_SHIFT module-attribute

EDATA_BITS_STATE_WIDTH = 3 module-attribute

EDATA_BITS_SZIND_MASK = mask(EDATA_BITS_SZIND_WIDTH, EDATA_BITS_SZIND_SHIFT) module-attribute

EDATA_BITS_SZIND_SHIFT = EDATA_BITS_STATE_WIDTH + EDATA_BITS_STATE_SHIFT module-attribute

EDATA_BITS_SZIND_WIDTH = lg_ceil(SC_NSIZES) module-attribute

EDATA_BITS_ZEROED_MASK = mask(EDATA_BITS_ZEROED_WIDTH, EDATA_BITS_ZEROED_SHIFT) module-attribute

EDATA_BITS_ZEROED_SHIFT = EDATA_BITS_PAI_WIDTH + EDATA_BITS_PAI_SHIFT module-attribute

EDATA_BITS_ZEROED_WIDTH = 1 module-attribute

LG_PAGE = 12 module-attribute

LG_QUANTUM = 4 module-attribute

LG_SIZEOF_PTR = 3 module-attribute

LG_VADDR = 48 module-attribute

MALLOCX_ARENA_BITS = 12 module-attribute

RTREE_HEIGHT = 1 module-attribute

RTREE_NHIB = 1 << LG_SIZEOF_PTR + 3 - LG_VADDR module-attribute

RTREE_NLIB = LG_PAGE module-attribute

RTREE_NSB = LG_VADDR - RTREE_NLIB module-attribute

SC_LG_BASE_MAX = SC_PTR_BITS - 2 module-attribute

SC_LG_FIRST_REGULAR_BASE = LG_QUANTUM + SC_LG_NGROUP module-attribute

SC_LG_NGROUP = 2 module-attribute

SC_LG_SLAB_MAXREGS = LG_PAGE - SC_LG_TINY_MIN module-attribute

SC_LG_TINY_MIN = 3 module-attribute

SC_NGROUP = 1 << SC_LG_NGROUP module-attribute

SC_NPSEUDO = SC_NGROUP module-attribute

SC_NREGULAR = SC_NGROUP * SC_LG_BASE_MAX - SC_LG_FIRST_REGULAR_BASE + 1 - 1 module-attribute

SC_NSIZES = SC_NTINY + SC_NPSEUDO + SC_NREGULAR module-attribute

SC_NTINY = LG_QUANTUM - SC_LG_TINY_MIN module-attribute

SC_PTR_BITS = 1 << LG_SIZEOF_PTR * 8 module-attribute

rtree_levels = [[{'bits': RTREE_NSB, 'cumbits': RTREE_NHIB + RTREE_NSB}], [{'bits': RTREE_NSB // 2, 'cumbits': RTREE_NHIB + RTREE_NSB // 2}, {'bits': RTREE_NSB // 2 + RTREE_NSB % 2, 'cumbits': RTREE_NHIB + RTREE_NSB}], [{'bits': RTREE_NSB // 3, 'cumbits': RTREE_NHIB + RTREE_NSB // 3}, {'bits': RTREE_NSB // 3 + RTREE_NSB % 3 // 2, 'cumbits': RTREE_NHIB + RTREE_NSB // 3 * 2 + RTREE_NSB % 3 // 2}, {'bits': RTREE_NSB // 3 + RTREE_NSB % 3 - RTREE_NSB % 3 // 2, 'cumbits': RTREE_NHIB + RTREE_NSB}]] module-attribute

Extent

Concept of extent (edata) is similar to chunk in glibc malloc but allocation algorithm differs a lot. - Extents are used to manage memory blocks (including jemalloc metadata) where extents sizes can vary but each block is always a multiple of the page size. - jemalloc will either allocate one large class request or multiple small class request (called slab) depending on request size. - Unlike chunks in glibc malloc, extents are not doubly linked list but are managed using rtree. - This tree is mostly used during deallocation to find the extent belonging to a pointer that is being freed. - Extents are also not stored as a header structure but externally (therefore extent metadata and actually mapped data may be very far apart).

allocated_address: int property

Starting address of allocated memory cache-oblivious large allocation alignment: When a large class allocation is made, jemalloc selects the closest size class that can fit the request and allocates that size + 4 KiB (0x1000). However, the pointer returned to user is randomized between the 'base' and 'base + 4 KiB' (0x1000) range. Source code: https://github.com/jemalloc/jemalloc/blob/a25b9b8ba91881964be3083db349991bbbbf1661/include/jemalloc/internal/arena_inlines_b.h#L505

bitfields: Dict[str, int] property

Extract bitfields

arena_ind: Arena from which this extent came, or all 1 bits if unassociated. slab: The slab flag indicates whether the extent is used for a slab of small regions. This helps differentiate small size classes, and it indicates whether interior pointers can be looked up via iealloc(). committed: The committed flag indicates whether physical memory is committed to the extent, whether explicitly or implicitly as on a system that overcommits and satisfies physical memory needs on demand via soft page faults. pai: The pai flag is an extent_pai_t. zeroed: The zeroed flag is used by extent recycling code to track whether memory is zero-filled. guarded: The guarded flag is used by the sanitizer to track whether the extent has page guards around it. state: The state flag is an extent_state_t. szind: The szind flag indicates usable size class index for allocations residing in this extent, regardless of whether the extent is a slab. Extent size and usable size often differ even for non-slabs, either due to sz_large_pad or promotion of sampled small regions. nfree: Number of free regions in slab. bin_shard: The shard of the bin from which this extent came.

bits: int property

bsize: int property

extent_address: int property

Address of the extent data structure (not the actual memory).

has_slab: bool property

Returns True if the extent is used for small size classes. Reference for size in Table 1 at https://jemalloc.net/jemalloc.3.html At time of writing, allocations <= 0x3800 are considered as small allocations and has slabs.

is_free: bool property

Returns True if the extent is free.

pai: str property

Page Allocator Interface

size property

May be larger in case of large size class allocation when cache_oblivious is enabled.

state_name: str property

__init__(addr)

RTree

RTree is used by jemalloc to keep track of extents that are allocated by jemalloc. Since extent data is not stored in a doubly linked list, rtree is used to find the extent belonging to a pointer that is being freed. Implementation of rtree is similar to Linux Radix tree: https://lwn.net/Articles/175432/

extents property

root property

__alignment_addr2base(addr, alignment=64) staticmethod

__init__(addr)

__rtree_leaf_maskbits(level)

__rtree_leafkey(key, level)

__subkey(key, level)

Return a portion of the key that is used to find the node/leaf in the rtree at a specific level. Source: https://github.com/jemalloc/jemalloc/blob/5b72ac098abce464add567869d082f2097bd59a2/include/jemalloc/internal/rtree.h#L161

get_rtree() staticmethod

lookup_hard(key)

Lookup the key in the rtree and return the value.

How it works: - Jemalloc stores the extent address in the rtree as a node and to find a specific node we need a address key.

lg_ceil(x)

lg_floor(x)

lg_floor_1(x)

lg_floor_16(x)

lg_floor_2(x)

lg_floor_32(x)

lg_floor_4(x)

lg_floor_64(x)

lg_floor_8(x)

mask(current_field_width, current_field_shift)