Classes:
-
RTree–RTree is used by jemalloc to keep track of extents that are allocated by jemalloc.
-
Extent–Concept of extent (edata) is similar to chunk in glibc malloc but allocation algorithm differs a lot.
Functions:
-
mask– -
lg_floor_1– -
lg_floor_2– -
lg_floor_4– -
lg_floor_8– -
lg_floor_16– -
lg_floor_32– -
lg_floor_64– -
lg_floor– -
lg_ceil–
Attributes:
-
LG_VADDR– -
LG_PAGE– -
MALLOCX_ARENA_BITS– -
LG_SIZEOF_PTR– -
RTREE_NHIB– -
RTREE_NLIB– -
RTREE_NSB– -
RTREE_HEIGHT– -
LG_QUANTUM– -
SC_LG_TINY_MIN– -
SC_NTINY– -
SC_LG_NGROUP– -
SC_NGROUP– -
SC_NPSEUDO– -
SC_PTR_BITS– -
SC_LG_BASE_MAX– -
SC_LG_FIRST_REGULAR_BASE– -
SC_NREGULAR– -
SC_NSIZES– -
SC_LG_SLAB_MAXREGS– -
EDATA_BITS_ARENA_WIDTH– -
EDATA_BITS_ARENA_SHIFT– -
EDATA_BITS_ARENA_MASK– -
EDATA_BITS_SLAB_WIDTH– -
EDATA_BITS_SLAB_SHIFT– -
EDATA_BITS_SLAB_MASK– -
EDATA_BITS_COMMITTED_WIDTH– -
EDATA_BITS_COMMITTED_SHIFT– -
EDATA_BITS_COMMITTED_MASK– -
EDATA_BITS_PAI_WIDTH– -
EDATA_BITS_PAI_SHIFT– -
EDATA_BITS_PAI_MASK– -
EDATA_BITS_ZEROED_WIDTH– -
EDATA_BITS_ZEROED_SHIFT– -
EDATA_BITS_ZEROED_MASK– -
EDATA_BITS_GUARDED_WIDTH– -
EDATA_BITS_GUARDED_SHIFT– -
EDATA_BITS_GUARDED_MASK– -
EDATA_BITS_STATE_WIDTH– -
EDATA_BITS_STATE_SHIFT– -
EDATA_BITS_STATE_MASK– -
EDATA_BITS_SZIND_WIDTH– -
EDATA_BITS_SZIND_SHIFT– -
EDATA_BITS_SZIND_MASK– -
EDATA_BITS_NFREE_WIDTH– -
EDATA_BITS_NFREE_SHIFT– -
EDATA_BITS_NFREE_MASK– -
EDATA_BITS_BINSHARD_WIDTH– -
EDATA_BITS_BINSHARD_SHIFT– -
EDATA_BITS_BINSHARD_MASK– -
EDATA_BITS_IS_HEAD_WIDTH– -
EDATA_BITS_IS_HEAD_SHIFT– -
EDATA_BITS_IS_HEAD_MASK– -
rtree_levels–
module-attribute ¤
SC_NREGULAR = SC_NGROUP * (SC_LG_BASE_MAX - SC_LG_FIRST_REGULAR_BASE + 1) - 1
module-attribute ¤
EDATA_BITS_ARENA_MASK = mask(EDATA_BITS_ARENA_WIDTH, EDATA_BITS_ARENA_SHIFT)
module-attribute ¤
EDATA_BITS_SLAB_SHIFT = EDATA_BITS_ARENA_WIDTH + EDATA_BITS_ARENA_SHIFT
module-attribute ¤
EDATA_BITS_SLAB_MASK = mask(EDATA_BITS_SLAB_WIDTH, EDATA_BITS_SLAB_SHIFT)
module-attribute ¤
EDATA_BITS_COMMITTED_SHIFT = EDATA_BITS_SLAB_WIDTH + EDATA_BITS_SLAB_SHIFT
module-attribute ¤
EDATA_BITS_COMMITTED_MASK = mask(
EDATA_BITS_COMMITTED_WIDTH, EDATA_BITS_COMMITTED_SHIFT
)
module-attribute ¤
EDATA_BITS_PAI_SHIFT = EDATA_BITS_COMMITTED_WIDTH + EDATA_BITS_COMMITTED_SHIFT
module-attribute ¤
EDATA_BITS_PAI_MASK = mask(EDATA_BITS_PAI_WIDTH, EDATA_BITS_PAI_SHIFT)
module-attribute ¤
EDATA_BITS_ZEROED_SHIFT = EDATA_BITS_PAI_WIDTH + EDATA_BITS_PAI_SHIFT
module-attribute ¤
EDATA_BITS_ZEROED_MASK = mask(EDATA_BITS_ZEROED_WIDTH, EDATA_BITS_ZEROED_SHIFT)
module-attribute ¤
EDATA_BITS_GUARDED_SHIFT = EDATA_BITS_ZEROED_WIDTH + EDATA_BITS_ZEROED_SHIFT
module-attribute ¤
EDATA_BITS_GUARDED_MASK = mask(
EDATA_BITS_GUARDED_WIDTH, EDATA_BITS_GUARDED_SHIFT
)
module-attribute ¤
EDATA_BITS_STATE_SHIFT = EDATA_BITS_GUARDED_WIDTH + EDATA_BITS_GUARDED_SHIFT
module-attribute ¤
EDATA_BITS_STATE_MASK = mask(EDATA_BITS_STATE_WIDTH, EDATA_BITS_STATE_SHIFT)
module-attribute ¤
EDATA_BITS_SZIND_SHIFT = EDATA_BITS_STATE_WIDTH + EDATA_BITS_STATE_SHIFT
module-attribute ¤
EDATA_BITS_SZIND_MASK = mask(EDATA_BITS_SZIND_WIDTH, EDATA_BITS_SZIND_SHIFT)
module-attribute ¤
EDATA_BITS_NFREE_SHIFT = EDATA_BITS_SZIND_WIDTH + EDATA_BITS_SZIND_SHIFT
module-attribute ¤
EDATA_BITS_NFREE_MASK = mask(EDATA_BITS_NFREE_WIDTH, EDATA_BITS_NFREE_SHIFT)
module-attribute ¤
EDATA_BITS_BINSHARD_SHIFT = EDATA_BITS_NFREE_WIDTH + EDATA_BITS_NFREE_SHIFT
module-attribute ¤
EDATA_BITS_BINSHARD_MASK = mask(
EDATA_BITS_BINSHARD_WIDTH, EDATA_BITS_BINSHARD_SHIFT
)
module-attribute ¤
EDATA_BITS_IS_HEAD_SHIFT = EDATA_BITS_BINSHARD_WIDTH + EDATA_BITS_BINSHARD_SHIFT
module-attribute ¤
EDATA_BITS_IS_HEAD_MASK = mask(
EDATA_BITS_IS_HEAD_WIDTH, EDATA_BITS_IS_HEAD_SHIFT
)
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,
},
],
]
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/
Methods:
-
get_rtree– -
lookup_hard–Lookup the key in the rtree and return the extent that owns it.
Attributes:
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
Extract the edata pointer from the first word of a rtree leaf element.
On compact leaves that word is le_bits (the edata pointer packed with szind/slab metadata); on non-compact leaves it is le_edata (a plain edata pointer with its metadata kept in a separate word). Either way the edata pointer lives at offset 0, so a single word read covers both.
Lookup the key in the rtree and return the extent that owns it.
Jemalloc stores each mapped page's owning extent in the rtree, keyed by the page address. We walk every level of the tree: interior levels hold child pointers to the next level, the final level holds leaf elements that encode the extent (edata) pointer. The number of levels, the per-level bit splits and the leaf layout all come from the target (see :func:_load_rtree_geom).
Credits: 盏一's jegdb https://web.archive.org/web/20221114090949/https://github.com/hidva/hidva.github.io/blob/dev/_drafts/jegdb.py
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).
Attributes:
-
size–May be larger in case of large size class allocation when cache_oblivious is enabled.
-
extent_address(int) –Address of the extent data structure (not the actual memory).
-
allocated_address(int) –Starting address of allocated memory
-
bsize(int) – -
bits(int) – -
bitfields(dict[str, int]) –Extract bitfields
-
state_name(str) – -
has_slab(bool) –Returns True if the extent is used for small size classes.
-
is_free(bool) –Returns True if the extent is free.
-
pai(str) –Page Allocator Interface
property ¤
May be larger in case of large size class allocation when cache_oblivious is enabled.
property ¤
Address of the extent data structure (not the actual memory).
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
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.
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.