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 value.
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
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.
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.