1 /******************************************************************************/
2 #ifdef JEMALLOC_H_TYPES
4 /* Maximum number of regions in one run. */
5 #define LG_RUN_MAXREGS (LG_PAGE - LG_TINY_MIN)
6 #define RUN_MAXREGS (1U << LG_RUN_MAXREGS)
9 * Minimum redzone size. Redzones may be larger than this if necessary to
10 * preserve region alignment.
12 #define REDZONE_MINSIZE 16
15 * The minimum ratio of active:dirty pages per arena is computed as:
17 * (nactive >> opt_lg_dirty_mult) >= ndirty
19 * So, supposing that opt_lg_dirty_mult is 3, there can be no less than 8 times
20 * as many active pages as dirty pages.
22 #define LG_DIRTY_MULT_DEFAULT 3
24 typedef struct arena_run_s arena_run_t
;
25 typedef struct arena_chunk_map_bits_s arena_chunk_map_bits_t
;
26 typedef struct arena_chunk_map_misc_s arena_chunk_map_misc_t
;
27 typedef struct arena_chunk_s arena_chunk_t
;
28 typedef struct arena_bin_info_s arena_bin_info_t
;
29 typedef struct arena_bin_s arena_bin_t
;
30 typedef struct arena_s arena_t
;
32 #endif /* JEMALLOC_H_TYPES */
33 /******************************************************************************/
34 #ifdef JEMALLOC_H_STRUCTS
37 /* Bin this run is associated with. */
40 /* Index of next region that has never been allocated, or nregs. */
43 /* Number of free regions in run. */
46 /* Per region allocated/deallocated bitmap. */
47 bitmap_t bitmap
[BITMAP_GROUPS_MAX
];
50 /* Each element of the chunk map corresponds to one page within the chunk. */
51 struct arena_chunk_map_bits_s
{
53 * Run address (or size) and various flags are stored together. The bit
54 * layout looks like (assuming 32-bit system):
56 * ???????? ???????? ????nnnn nnnndula
58 * ? : Unallocated: Run address for first/last pages, unset for internal
60 * Small: Run page offset.
61 * Large: Run size for first page, unset for trailing pages.
62 * n : binind for small size class, BININD_INVALID for large size class.
68 * Following are example bit patterns for the three types of runs.
72 * n : binind for size class; large objects set these to BININD_INVALID
79 * Unallocated (clean):
80 * ssssssss ssssssss ssss++++ ++++du-a
81 * xxxxxxxx xxxxxxxx xxxxxxxx xxxx-Uxx
82 * ssssssss ssssssss ssss++++ ++++dU-a
84 * Unallocated (dirty):
85 * ssssssss ssssssss ssss++++ ++++D--a
86 * xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
87 * ssssssss ssssssss ssss++++ ++++D--a
90 * pppppppp pppppppp ppppnnnn nnnnd--A
91 * pppppppp pppppppp ppppnnnn nnnn---A
92 * pppppppp pppppppp ppppnnnn nnnnd--A
95 * ssssssss ssssssss ssss++++ ++++D-LA
96 * xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx
97 * -------- -------- ----++++ ++++D-LA
99 * Large (sampled, size <= PAGE):
100 * ssssssss ssssssss ssssnnnn nnnnD-LA
102 * Large (not sampled, size == PAGE):
103 * ssssssss ssssssss ssss++++ ++++D-LA
106 #define CHUNK_MAP_BININD_SHIFT 4
107 #define BININD_INVALID ((size_t)0xffU)
108 /* CHUNK_MAP_BININD_MASK == (BININD_INVALID << CHUNK_MAP_BININD_SHIFT) */
109 #define CHUNK_MAP_BININD_MASK ((size_t)0xff0U)
110 #define CHUNK_MAP_BININD_INVALID CHUNK_MAP_BININD_MASK
111 #define CHUNK_MAP_FLAGS_MASK ((size_t)0xcU)
112 #define CHUNK_MAP_DIRTY ((size_t)0x8U)
113 #define CHUNK_MAP_UNZEROED ((size_t)0x4U)
114 #define CHUNK_MAP_LARGE ((size_t)0x2U)
115 #define CHUNK_MAP_ALLOCATED ((size_t)0x1U)
116 #define CHUNK_MAP_KEY CHUNK_MAP_ALLOCATED
120 * Each arena_chunk_map_misc_t corresponds to one page within the chunk, just
121 * like arena_chunk_map_bits_t. Two separate arrays are stored within each
122 * chunk header in order to improve cache locality.
124 struct arena_chunk_map_misc_s
{
126 * Linkage for run trees. There are two disjoint uses:
128 * 1) arena_t's runs_avail tree.
129 * 2) arena_run_t conceptually uses this linkage for in-use non-full
130 * runs, rather than directly embedding linkage.
132 rb_node(arena_chunk_map_misc_t
) rb_link
;
135 /* Linkage for list of dirty runs. */
136 ql_elm(arena_chunk_map_misc_t
) dr_link
;
138 /* Profile counters, used for large object runs. */
139 prof_tctx_t
*prof_tctx
;
141 /* Small region run metadata. */
145 typedef rb_tree(arena_chunk_map_misc_t
) arena_avail_tree_t
;
146 typedef rb_tree(arena_chunk_map_misc_t
) arena_run_tree_t
;
147 typedef ql_head(arena_chunk_map_misc_t
) arena_chunk_miscelms_t
;
149 /* Arena chunk header. */
150 struct arena_chunk_s
{
151 /* Arena that owns the chunk. */
155 * Map of pages within chunk that keeps track of free/large/small. The
156 * first map_bias entries are omitted, since the chunk header does not
157 * need to be tracked in the map. This omission saves a header page
158 * for common chunk sizes (e.g. 4 MiB).
160 arena_chunk_map_bits_t map_bits
[1]; /* Dynamically sized. */
164 * Read-only information associated with each element of arena_t's bins array
165 * is stored separately, partly to reduce memory usage (only one copy, rather
166 * than one per arena), but mainly to avoid false cacheline sharing.
168 * Each run has the following layout:
170 * /--------------------\
172 * |--------------------|
174 * reg0_offset | region 0 |
176 * |--------------------| \
178 * | region 1 | > reg_interval
180 * |--------------------|
184 * |--------------------|
188 * |--------------------|
190 * \--------------------/
192 * reg_interval has at least the same minimum alignment as reg_size; this
193 * preserves the alignment constraint that sa2u() depends on. Alignment pad is
194 * either 0 or redzone_size; it is present only if needed to align reg0_offset.
196 struct arena_bin_info_s
{
197 /* Size of regions in a run for this bin's size class. */
203 /* Interval between regions (reg_size + (redzone_size << 1)). */
206 /* Total size of a run for this bin's size class. */
209 /* Total number of regions in a run for this bin's size class. */
213 * Metadata used to manipulate bitmaps for runs associated with this
216 bitmap_info_t bitmap_info
;
218 /* Offset of first region in a run for this bin's size class. */
219 uint32_t reg0_offset
;
224 * All operations on runcur, runs, and stats require that lock be
225 * locked. Run allocation/deallocation are protected by the arena lock,
226 * which may be acquired while holding one or more bin locks, but not
232 * Current run being used to service allocations of this bin's size
238 * Tree of non-full runs. This tree is used when looking for an
239 * existing run when runcur is no longer usable. We choose the
240 * non-full run that is lowest in memory; this policy tends to keep
241 * objects packed well, and it can also help reduce the number of
242 * almost-empty chunks.
244 arena_run_tree_t runs
;
246 /* Bin statistics. */
247 malloc_bin_stats_t stats
;
251 /* This arena's index within the arenas array. */
255 * Number of threads currently assigned to this arena. This field is
256 * protected by arenas_lock.
261 * There are three classes of arena operations from a locking
263 * 1) Thread asssignment (modifies nthreads) is protected by
265 * 2) Bin-related operations are protected by bin locks.
266 * 3) Chunk- and run-related operations are protected by this mutex.
272 * List of tcaches for extant threads associated with this arena.
273 * Stats from these are merged incrementally, and at exit.
275 ql_head(tcache_t
) tcache_ql
;
277 uint64_t prof_accumbytes
;
282 * In order to avoid rapid chunk allocation/deallocation when an arena
283 * oscillates right on the cusp of needing a new chunk, cache the most
284 * recently freed chunk. The spare is left in the arena's chunk trees
285 * until it is deleted.
287 * There is one spare chunk per arena, rather than one spare total, in
288 * order to avoid interactions between multiple threads that could make
289 * a single spare inadequate.
291 arena_chunk_t
*spare
;
293 /* Number of pages in active runs and huge regions. */
297 * Current count of pages within unused runs that are potentially
298 * dirty, and for which madvise(... MADV_DONTNEED) has not been called.
299 * By tracking this, we can institute a limit on how much dirty unused
300 * memory is mapped for each arena.
305 * Size/address-ordered trees of this arena's available runs. The trees
306 * are used for first-best-fit run allocation.
308 arena_avail_tree_t runs_avail
;
310 /* List of dirty runs this arena manages. */
311 arena_chunk_miscelms_t runs_dirty
;
314 * user-configureable chunk allocation and deallocation functions.
316 chunk_alloc_t
*chunk_alloc
;
317 chunk_dalloc_t
*chunk_dalloc
;
319 /* bins is used to store trees of free regions. */
320 arena_bin_t bins
[NBINS
];
323 #endif /* JEMALLOC_H_STRUCTS */
324 /******************************************************************************/
325 #ifdef JEMALLOC_H_EXTERNS
327 extern ssize_t opt_lg_dirty_mult
;
329 * small_size2bin_tab is a compact lookup table that rounds request sizes up to
330 * size classes. In order to reduce cache footprint, the table is compressed,
331 * and all accesses are via small_size2bin().
333 extern uint8_t const small_size2bin_tab
[];
335 * small_bin2size_tab duplicates information in arena_bin_info, but in a const
336 * array, for which it is easier for the compiler to optimize repeated
339 extern uint32_t const small_bin2size_tab
[NBINS
];
341 extern arena_bin_info_t arena_bin_info
[NBINS
];
343 /* Number of large size classes. */
344 #define nlclasses (chunk_npages - map_bias)
346 void *arena_chunk_alloc_huge(arena_t
*arena
, void *new_addr
, size_t size
,
347 size_t alignment
, bool *zero
);
348 void arena_chunk_dalloc_huge(arena_t
*arena
, void *chunk
, size_t size
);
349 void arena_purge_all(arena_t
*arena
);
350 void arena_tcache_fill_small(arena_t
*arena
, tcache_bin_t
*tbin
,
351 size_t binind
, uint64_t prof_accumbytes
);
352 void arena_alloc_junk_small(void *ptr
, arena_bin_info_t
*bin_info
,
355 typedef void (arena_redzone_corruption_t
)(void *, size_t, bool, size_t,
357 extern arena_redzone_corruption_t
*arena_redzone_corruption
;
358 typedef void (arena_dalloc_junk_small_t
)(void *, arena_bin_info_t
*);
359 extern arena_dalloc_junk_small_t
*arena_dalloc_junk_small
;
361 void arena_dalloc_junk_small(void *ptr
, arena_bin_info_t
*bin_info
);
363 void arena_quarantine_junk_small(void *ptr
, size_t usize
);
364 void *arena_malloc_small(arena_t
*arena
, size_t size
, bool zero
);
365 void *arena_malloc_large(arena_t
*arena
, size_t size
, bool zero
);
366 void *arena_palloc(arena_t
*arena
, size_t size
, size_t alignment
, bool zero
);
367 void arena_prof_promoted(const void *ptr
, size_t size
);
368 void arena_dalloc_bin_locked(arena_t
*arena
, arena_chunk_t
*chunk
, void *ptr
,
369 arena_chunk_map_bits_t
*bitselm
);
370 void arena_dalloc_bin(arena_t
*arena
, arena_chunk_t
*chunk
, void *ptr
,
371 size_t pageind
, arena_chunk_map_bits_t
*bitselm
);
372 void arena_dalloc_small(arena_t
*arena
, arena_chunk_t
*chunk
, void *ptr
,
375 typedef void (arena_dalloc_junk_large_t
)(void *, size_t);
376 extern arena_dalloc_junk_large_t
*arena_dalloc_junk_large
;
378 void arena_dalloc_large_locked(arena_t
*arena
, arena_chunk_t
*chunk
,
380 void arena_dalloc_large(arena_t
*arena
, arena_chunk_t
*chunk
, void *ptr
);
382 typedef void (arena_ralloc_junk_large_t
)(void *, size_t, size_t);
383 extern arena_ralloc_junk_large_t
*arena_ralloc_junk_large
;
385 bool arena_ralloc_no_move(void *ptr
, size_t oldsize
, size_t size
,
386 size_t extra
, bool zero
);
387 void *arena_ralloc(tsd_t
*tsd
, arena_t
*arena
, void *ptr
, size_t oldsize
,
388 size_t size
, size_t extra
, size_t alignment
, bool zero
,
389 bool try_tcache_alloc
, bool try_tcache_dalloc
);
390 dss_prec_t
arena_dss_prec_get(arena_t
*arena
);
391 bool arena_dss_prec_set(arena_t
*arena
, dss_prec_t dss_prec
);
392 void arena_stats_merge(arena_t
*arena
, const char **dss
, size_t *nactive
,
393 size_t *ndirty
, arena_stats_t
*astats
, malloc_bin_stats_t
*bstats
,
394 malloc_large_stats_t
*lstats
);
395 bool arena_new(arena_t
*arena
, unsigned ind
);
396 void arena_boot(void);
397 void arena_prefork(arena_t
*arena
);
398 void arena_postfork_parent(arena_t
*arena
);
399 void arena_postfork_child(arena_t
*arena
);
401 #endif /* JEMALLOC_H_EXTERNS */
402 /******************************************************************************/
403 #ifdef JEMALLOC_H_INLINES
405 #ifndef JEMALLOC_ENABLE_INLINE
406 size_t small_size2bin_compute(size_t size
);
407 size_t small_size2bin_lookup(size_t size
);
408 size_t small_size2bin(size_t size
);
409 size_t small_bin2size_compute(size_t binind
);
410 size_t small_bin2size_lookup(size_t binind
);
411 size_t small_bin2size(size_t binind
);
412 size_t small_s2u_compute(size_t size
);
413 size_t small_s2u_lookup(size_t size
);
414 size_t small_s2u(size_t size
);
415 arena_chunk_map_bits_t
*arena_bitselm_get(arena_chunk_t
*chunk
,
417 arena_chunk_map_misc_t
*arena_miscelm_get(arena_chunk_t
*chunk
,
419 size_t arena_miscelm_to_pageind(arena_chunk_map_misc_t
*miscelm
);
420 void *arena_miscelm_to_rpages(arena_chunk_map_misc_t
*miscelm
);
421 arena_chunk_map_misc_t
*arena_run_to_miscelm(arena_run_t
*run
);
422 size_t *arena_mapbitsp_get(arena_chunk_t
*chunk
, size_t pageind
);
423 size_t arena_mapbitsp_read(size_t *mapbitsp
);
424 size_t arena_mapbits_get(arena_chunk_t
*chunk
, size_t pageind
);
425 size_t arena_mapbits_unallocated_size_get(arena_chunk_t
*chunk
,
427 size_t arena_mapbits_large_size_get(arena_chunk_t
*chunk
, size_t pageind
);
428 size_t arena_mapbits_small_runind_get(arena_chunk_t
*chunk
, size_t pageind
);
429 size_t arena_mapbits_binind_get(arena_chunk_t
*chunk
, size_t pageind
);
430 size_t arena_mapbits_dirty_get(arena_chunk_t
*chunk
, size_t pageind
);
431 size_t arena_mapbits_unzeroed_get(arena_chunk_t
*chunk
, size_t pageind
);
432 size_t arena_mapbits_large_get(arena_chunk_t
*chunk
, size_t pageind
);
433 size_t arena_mapbits_allocated_get(arena_chunk_t
*chunk
, size_t pageind
);
434 void arena_mapbitsp_write(size_t *mapbitsp
, size_t mapbits
);
435 void arena_mapbits_unallocated_set(arena_chunk_t
*chunk
, size_t pageind
,
436 size_t size
, size_t flags
);
437 void arena_mapbits_unallocated_size_set(arena_chunk_t
*chunk
, size_t pageind
,
439 void arena_mapbits_large_set(arena_chunk_t
*chunk
, size_t pageind
,
440 size_t size
, size_t flags
);
441 void arena_mapbits_large_binind_set(arena_chunk_t
*chunk
, size_t pageind
,
443 void arena_mapbits_small_set(arena_chunk_t
*chunk
, size_t pageind
,
444 size_t runind
, size_t binind
, size_t flags
);
445 void arena_mapbits_unzeroed_set(arena_chunk_t
*chunk
, size_t pageind
,
447 bool arena_prof_accum_impl(arena_t
*arena
, uint64_t accumbytes
);
448 bool arena_prof_accum_locked(arena_t
*arena
, uint64_t accumbytes
);
449 bool arena_prof_accum(arena_t
*arena
, uint64_t accumbytes
);
450 size_t arena_ptr_small_binind_get(const void *ptr
, size_t mapbits
);
451 size_t arena_bin_index(arena_t
*arena
, arena_bin_t
*bin
);
452 unsigned arena_run_regind(arena_run_t
*run
, arena_bin_info_t
*bin_info
,
454 prof_tctx_t
*arena_prof_tctx_get(const void *ptr
);
455 void arena_prof_tctx_set(const void *ptr
, prof_tctx_t
*tctx
);
456 void *arena_malloc(tsd_t
*tsd
, arena_t
*arena
, size_t size
, bool zero
,
458 size_t arena_salloc(const void *ptr
, bool demote
);
459 void arena_dalloc(tsd_t
*tsd
, arena_chunk_t
*chunk
, void *ptr
,
461 void arena_sdalloc(tsd_t
*tsd
, arena_chunk_t
*chunk
, void *ptr
, size_t size
,
465 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_ARENA_C_))
466 # ifdef JEMALLOC_ARENA_INLINE_A
467 JEMALLOC_INLINE
size_t
468 small_size2bin_compute(size_t size
)
471 if (size
<= (ZU(1) << LG_TINY_MAXCLASS
)) {
472 size_t lg_tmin
= LG_TINY_MAXCLASS
- NTBINS
+ 1;
473 size_t lg_ceil
= lg_floor(pow2_ceil(size
));
474 return (lg_ceil
< lg_tmin
? 0 : lg_ceil
- lg_tmin
);
478 size_t x
= lg_floor((size
<<1)-1);
479 size_t shift
= (x
< LG_SIZE_CLASS_GROUP
+ LG_QUANTUM
) ? 0 :
480 x
- (LG_SIZE_CLASS_GROUP
+ LG_QUANTUM
);
481 size_t grp
= shift
<< LG_SIZE_CLASS_GROUP
;
483 size_t lg_delta
= (x
< LG_SIZE_CLASS_GROUP
+ LG_QUANTUM
+ 1)
484 ? LG_QUANTUM
: x
- LG_SIZE_CLASS_GROUP
- 1;
486 size_t delta_inverse_mask
= ZI(-1) << lg_delta
;
487 size_t mod
= ((((size
-1) & delta_inverse_mask
) >> lg_delta
)) &
488 ((ZU(1) << LG_SIZE_CLASS_GROUP
) - 1);
490 size_t bin
= NTBINS
+ grp
+ mod
;
495 JEMALLOC_ALWAYS_INLINE
size_t
496 small_size2bin_lookup(size_t size
)
499 assert(size
<= LOOKUP_MAXCLASS
);
501 size_t ret
= ((size_t)(small_size2bin_tab
[(size
-1) >>
503 assert(ret
== small_size2bin_compute(size
));
508 JEMALLOC_ALWAYS_INLINE
size_t
509 small_size2bin(size_t size
)
513 if (likely(size
<= LOOKUP_MAXCLASS
))
514 return (small_size2bin_lookup(size
));
516 return (small_size2bin_compute(size
));
519 JEMALLOC_INLINE
size_t
520 small_bin2size_compute(size_t binind
)
524 return (ZU(1) << (LG_TINY_MAXCLASS
- NTBINS
+ 1 + binind
));
528 size_t reduced_binind
= binind
- NTBINS
;
529 size_t grp
= reduced_binind
>> LG_SIZE_CLASS_GROUP
;
530 size_t mod
= reduced_binind
& ((ZU(1) << LG_SIZE_CLASS_GROUP
) -
533 size_t grp_size_mask
= ~((!!grp
)-1);
534 size_t grp_size
= ((ZU(1) << (LG_QUANTUM
+
535 (LG_SIZE_CLASS_GROUP
-1))) << grp
) & grp_size_mask
;
537 size_t shift
= (grp
== 0) ? 1 : grp
;
538 size_t lg_delta
= shift
+ (LG_QUANTUM
-1);
539 size_t mod_size
= (mod
+1) << lg_delta
;
541 size_t usize
= grp_size
+ mod_size
;
546 JEMALLOC_ALWAYS_INLINE
size_t
547 small_bin2size_lookup(size_t binind
)
550 assert(binind
< NBINS
);
552 size_t ret
= (size_t)small_bin2size_tab
[binind
];
553 assert(ret
== small_bin2size_compute(binind
));
558 JEMALLOC_ALWAYS_INLINE
size_t
559 small_bin2size(size_t binind
)
562 return (small_bin2size_lookup(binind
));
565 JEMALLOC_ALWAYS_INLINE
size_t
566 small_s2u_compute(size_t size
)
569 if (size
<= (ZU(1) << LG_TINY_MAXCLASS
)) {
570 size_t lg_tmin
= LG_TINY_MAXCLASS
- NTBINS
+ 1;
571 size_t lg_ceil
= lg_floor(pow2_ceil(size
));
572 return (lg_ceil
< lg_tmin
? (ZU(1) << lg_tmin
) :
577 size_t x
= lg_floor((size
<<1)-1);
578 size_t lg_delta
= (x
< LG_SIZE_CLASS_GROUP
+ LG_QUANTUM
+ 1)
579 ? LG_QUANTUM
: x
- LG_SIZE_CLASS_GROUP
- 1;
580 size_t delta
= ZU(1) << lg_delta
;
581 size_t delta_mask
= delta
- 1;
582 size_t usize
= (size
+ delta_mask
) & ~delta_mask
;
587 JEMALLOC_ALWAYS_INLINE
size_t
588 small_s2u_lookup(size_t size
)
590 size_t ret
= small_bin2size(small_size2bin(size
));
592 assert(ret
== small_s2u_compute(size
));
596 JEMALLOC_ALWAYS_INLINE
size_t
597 small_s2u(size_t size
)
601 if (likely(size
<= LOOKUP_MAXCLASS
))
602 return (small_s2u_lookup(size
));
604 return (small_s2u_compute(size
));
606 # endif /* JEMALLOC_ARENA_INLINE_A */
608 # ifdef JEMALLOC_ARENA_INLINE_B
609 JEMALLOC_ALWAYS_INLINE arena_chunk_map_bits_t
*
610 arena_bitselm_get(arena_chunk_t
*chunk
, size_t pageind
)
613 assert(pageind
>= map_bias
);
614 assert(pageind
< chunk_npages
);
616 return (&chunk
->map_bits
[pageind
-map_bias
]);
619 JEMALLOC_ALWAYS_INLINE arena_chunk_map_misc_t
*
620 arena_miscelm_get(arena_chunk_t
*chunk
, size_t pageind
)
623 assert(pageind
>= map_bias
);
624 assert(pageind
< chunk_npages
);
626 return ((arena_chunk_map_misc_t
*)((uintptr_t)chunk
+
627 (uintptr_t)map_misc_offset
) + pageind
-map_bias
);
630 JEMALLOC_ALWAYS_INLINE
size_t
631 arena_miscelm_to_pageind(arena_chunk_map_misc_t
*miscelm
)
633 arena_chunk_t
*chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(miscelm
);
634 size_t pageind
= ((uintptr_t)miscelm
- ((uintptr_t)chunk
+
635 map_misc_offset
)) / sizeof(arena_chunk_map_misc_t
) + map_bias
;
637 assert(pageind
>= map_bias
);
638 assert(pageind
< chunk_npages
);
643 JEMALLOC_ALWAYS_INLINE
void *
644 arena_miscelm_to_rpages(arena_chunk_map_misc_t
*miscelm
)
646 arena_chunk_t
*chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(miscelm
);
647 size_t pageind
= arena_miscelm_to_pageind(miscelm
);
649 return ((void *)((uintptr_t)chunk
+ (pageind
<< LG_PAGE
)));
652 JEMALLOC_ALWAYS_INLINE arena_chunk_map_misc_t
*
653 arena_run_to_miscelm(arena_run_t
*run
)
655 arena_chunk_map_misc_t
*miscelm
= (arena_chunk_map_misc_t
656 *)((uintptr_t)run
- offsetof(arena_chunk_map_misc_t
, run
));
658 assert(arena_miscelm_to_pageind(miscelm
) >= map_bias
);
659 assert(arena_miscelm_to_pageind(miscelm
) < chunk_npages
);
664 JEMALLOC_ALWAYS_INLINE
size_t *
665 arena_mapbitsp_get(arena_chunk_t
*chunk
, size_t pageind
)
668 return (&arena_bitselm_get(chunk
, pageind
)->bits
);
671 JEMALLOC_ALWAYS_INLINE
size_t
672 arena_mapbitsp_read(size_t *mapbitsp
)
678 JEMALLOC_ALWAYS_INLINE
size_t
679 arena_mapbits_get(arena_chunk_t
*chunk
, size_t pageind
)
682 return (arena_mapbitsp_read(arena_mapbitsp_get(chunk
, pageind
)));
685 JEMALLOC_ALWAYS_INLINE
size_t
686 arena_mapbits_unallocated_size_get(arena_chunk_t
*chunk
, size_t pageind
)
690 mapbits
= arena_mapbits_get(chunk
, pageind
);
691 assert((mapbits
& (CHUNK_MAP_LARGE
|CHUNK_MAP_ALLOCATED
)) == 0);
692 return (mapbits
& ~PAGE_MASK
);
695 JEMALLOC_ALWAYS_INLINE
size_t
696 arena_mapbits_large_size_get(arena_chunk_t
*chunk
, size_t pageind
)
700 mapbits
= arena_mapbits_get(chunk
, pageind
);
701 assert((mapbits
& (CHUNK_MAP_LARGE
|CHUNK_MAP_ALLOCATED
)) ==
702 (CHUNK_MAP_LARGE
|CHUNK_MAP_ALLOCATED
));
703 return (mapbits
& ~PAGE_MASK
);
706 JEMALLOC_ALWAYS_INLINE
size_t
707 arena_mapbits_small_runind_get(arena_chunk_t
*chunk
, size_t pageind
)
711 mapbits
= arena_mapbits_get(chunk
, pageind
);
712 assert((mapbits
& (CHUNK_MAP_LARGE
|CHUNK_MAP_ALLOCATED
)) ==
713 CHUNK_MAP_ALLOCATED
);
714 return (mapbits
>> LG_PAGE
);
717 JEMALLOC_ALWAYS_INLINE
size_t
718 arena_mapbits_binind_get(arena_chunk_t
*chunk
, size_t pageind
)
723 mapbits
= arena_mapbits_get(chunk
, pageind
);
724 binind
= (mapbits
& CHUNK_MAP_BININD_MASK
) >> CHUNK_MAP_BININD_SHIFT
;
725 assert(binind
< NBINS
|| binind
== BININD_INVALID
);
729 JEMALLOC_ALWAYS_INLINE
size_t
730 arena_mapbits_dirty_get(arena_chunk_t
*chunk
, size_t pageind
)
734 mapbits
= arena_mapbits_get(chunk
, pageind
);
735 return (mapbits
& CHUNK_MAP_DIRTY
);
738 JEMALLOC_ALWAYS_INLINE
size_t
739 arena_mapbits_unzeroed_get(arena_chunk_t
*chunk
, size_t pageind
)
743 mapbits
= arena_mapbits_get(chunk
, pageind
);
744 return (mapbits
& CHUNK_MAP_UNZEROED
);
747 JEMALLOC_ALWAYS_INLINE
size_t
748 arena_mapbits_large_get(arena_chunk_t
*chunk
, size_t pageind
)
752 mapbits
= arena_mapbits_get(chunk
, pageind
);
753 return (mapbits
& CHUNK_MAP_LARGE
);
756 JEMALLOC_ALWAYS_INLINE
size_t
757 arena_mapbits_allocated_get(arena_chunk_t
*chunk
, size_t pageind
)
761 mapbits
= arena_mapbits_get(chunk
, pageind
);
762 return (mapbits
& CHUNK_MAP_ALLOCATED
);
765 JEMALLOC_ALWAYS_INLINE
void
766 arena_mapbitsp_write(size_t *mapbitsp
, size_t mapbits
)
772 JEMALLOC_ALWAYS_INLINE
void
773 arena_mapbits_unallocated_set(arena_chunk_t
*chunk
, size_t pageind
, size_t size
,
776 size_t *mapbitsp
= arena_mapbitsp_get(chunk
, pageind
);
778 assert((size
& PAGE_MASK
) == 0);
779 assert((flags
& ~CHUNK_MAP_FLAGS_MASK
) == 0);
780 assert((flags
& (CHUNK_MAP_DIRTY
|CHUNK_MAP_UNZEROED
)) == flags
);
781 arena_mapbitsp_write(mapbitsp
, size
| CHUNK_MAP_BININD_INVALID
| flags
);
784 JEMALLOC_ALWAYS_INLINE
void
785 arena_mapbits_unallocated_size_set(arena_chunk_t
*chunk
, size_t pageind
,
788 size_t *mapbitsp
= arena_mapbitsp_get(chunk
, pageind
);
789 size_t mapbits
= arena_mapbitsp_read(mapbitsp
);
791 assert((size
& PAGE_MASK
) == 0);
792 assert((mapbits
& (CHUNK_MAP_LARGE
|CHUNK_MAP_ALLOCATED
)) == 0);
793 arena_mapbitsp_write(mapbitsp
, size
| (mapbits
& PAGE_MASK
));
796 JEMALLOC_ALWAYS_INLINE
void
797 arena_mapbits_large_set(arena_chunk_t
*chunk
, size_t pageind
, size_t size
,
800 size_t *mapbitsp
= arena_mapbitsp_get(chunk
, pageind
);
801 size_t mapbits
= arena_mapbitsp_read(mapbitsp
);
804 assert((size
& PAGE_MASK
) == 0);
805 assert((flags
& CHUNK_MAP_DIRTY
) == flags
);
806 unzeroed
= mapbits
& CHUNK_MAP_UNZEROED
; /* Preserve unzeroed. */
807 arena_mapbitsp_write(mapbitsp
, size
| CHUNK_MAP_BININD_INVALID
| flags
808 | unzeroed
| CHUNK_MAP_LARGE
| CHUNK_MAP_ALLOCATED
);
811 JEMALLOC_ALWAYS_INLINE
void
812 arena_mapbits_large_binind_set(arena_chunk_t
*chunk
, size_t pageind
,
815 size_t *mapbitsp
= arena_mapbitsp_get(chunk
, pageind
);
816 size_t mapbits
= arena_mapbitsp_read(mapbitsp
);
818 assert(binind
<= BININD_INVALID
);
819 assert(arena_mapbits_large_size_get(chunk
, pageind
) == PAGE
);
820 arena_mapbitsp_write(mapbitsp
, (mapbits
& ~CHUNK_MAP_BININD_MASK
) |
821 (binind
<< CHUNK_MAP_BININD_SHIFT
));
824 JEMALLOC_ALWAYS_INLINE
void
825 arena_mapbits_small_set(arena_chunk_t
*chunk
, size_t pageind
, size_t runind
,
826 size_t binind
, size_t flags
)
828 size_t *mapbitsp
= arena_mapbitsp_get(chunk
, pageind
);
829 size_t mapbits
= arena_mapbitsp_read(mapbitsp
);
832 assert(binind
< BININD_INVALID
);
833 assert(pageind
- runind
>= map_bias
);
834 assert((flags
& CHUNK_MAP_DIRTY
) == flags
);
835 unzeroed
= mapbits
& CHUNK_MAP_UNZEROED
; /* Preserve unzeroed. */
836 arena_mapbitsp_write(mapbitsp
, (runind
<< LG_PAGE
) | (binind
<<
837 CHUNK_MAP_BININD_SHIFT
) | flags
| unzeroed
| CHUNK_MAP_ALLOCATED
);
840 JEMALLOC_ALWAYS_INLINE
void
841 arena_mapbits_unzeroed_set(arena_chunk_t
*chunk
, size_t pageind
,
844 size_t *mapbitsp
= arena_mapbitsp_get(chunk
, pageind
);
845 size_t mapbits
= arena_mapbitsp_read(mapbitsp
);
847 arena_mapbitsp_write(mapbitsp
, (mapbits
& ~CHUNK_MAP_UNZEROED
) |
852 arena_prof_accum_impl(arena_t
*arena
, uint64_t accumbytes
)
855 cassert(config_prof
);
856 assert(prof_interval
!= 0);
858 arena
->prof_accumbytes
+= accumbytes
;
859 if (arena
->prof_accumbytes
>= prof_interval
) {
860 arena
->prof_accumbytes
-= prof_interval
;
867 arena_prof_accum_locked(arena_t
*arena
, uint64_t accumbytes
)
870 cassert(config_prof
);
872 if (likely(prof_interval
== 0))
874 return (arena_prof_accum_impl(arena
, accumbytes
));
878 arena_prof_accum(arena_t
*arena
, uint64_t accumbytes
)
881 cassert(config_prof
);
883 if (likely(prof_interval
== 0))
889 malloc_mutex_lock(&arena
->lock
);
890 ret
= arena_prof_accum_impl(arena
, accumbytes
);
891 malloc_mutex_unlock(&arena
->lock
);
896 JEMALLOC_ALWAYS_INLINE
size_t
897 arena_ptr_small_binind_get(const void *ptr
, size_t mapbits
)
901 binind
= (mapbits
& CHUNK_MAP_BININD_MASK
) >> CHUNK_MAP_BININD_SHIFT
;
904 arena_chunk_t
*chunk
;
907 size_t actual_mapbits
;
911 size_t actual_binind
;
912 arena_bin_info_t
*bin_info
;
913 arena_chunk_map_misc_t
*miscelm
;
916 assert(binind
!= BININD_INVALID
);
917 assert(binind
< NBINS
);
918 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ptr
);
919 arena
= chunk
->arena
;
920 pageind
= ((uintptr_t)ptr
- (uintptr_t)chunk
) >> LG_PAGE
;
921 actual_mapbits
= arena_mapbits_get(chunk
, pageind
);
922 assert(mapbits
== actual_mapbits
);
923 assert(arena_mapbits_large_get(chunk
, pageind
) == 0);
924 assert(arena_mapbits_allocated_get(chunk
, pageind
) != 0);
925 rpages_ind
= pageind
- arena_mapbits_small_runind_get(chunk
,
927 miscelm
= arena_miscelm_get(chunk
, rpages_ind
);
930 actual_binind
= bin
- arena
->bins
;
931 assert(binind
== actual_binind
);
932 bin_info
= &arena_bin_info
[actual_binind
];
933 rpages
= arena_miscelm_to_rpages(miscelm
);
934 assert(((uintptr_t)ptr
- ((uintptr_t)rpages
+
935 (uintptr_t)bin_info
->reg0_offset
)) % bin_info
->reg_interval
941 # endif /* JEMALLOC_ARENA_INLINE_B */
943 # ifdef JEMALLOC_ARENA_INLINE_C
944 JEMALLOC_INLINE
size_t
945 arena_bin_index(arena_t
*arena
, arena_bin_t
*bin
)
947 size_t binind
= bin
- arena
->bins
;
948 assert(binind
< NBINS
);
952 JEMALLOC_INLINE
unsigned
953 arena_run_regind(arena_run_t
*run
, arena_bin_info_t
*bin_info
, const void *ptr
)
955 unsigned shift
, diff
, regind
;
957 arena_chunk_map_misc_t
*miscelm
= arena_run_to_miscelm(run
);
958 void *rpages
= arena_miscelm_to_rpages(miscelm
);
961 * Freeing a pointer lower than region zero can cause assertion
964 assert((uintptr_t)ptr
>= (uintptr_t)rpages
+
965 (uintptr_t)bin_info
->reg0_offset
);
968 * Avoid doing division with a variable divisor if possible. Using
969 * actual division here can reduce allocator throughput by over 20%!
971 diff
= (unsigned)((uintptr_t)ptr
- (uintptr_t)rpages
-
972 bin_info
->reg0_offset
);
974 /* Rescale (factor powers of 2 out of the numerator and denominator). */
975 interval
= bin_info
->reg_interval
;
976 shift
= jemalloc_ffs(interval
) - 1;
981 /* The divisor was a power of 2. */
985 * To divide by a number D that is not a power of two we
986 * multiply by (2^21 / D) and then right shift by 21 positions.
992 * (X * interval_invs[D - 3]) >> SIZE_INV_SHIFT
994 * We can omit the first three elements, because we never
995 * divide by 0, and 1 and 2 are both powers of two, which are
998 #define SIZE_INV_SHIFT ((sizeof(unsigned) << 3) - LG_RUN_MAXREGS)
999 #define SIZE_INV(s) (((1U << SIZE_INV_SHIFT) / (s)) + 1)
1000 static const unsigned interval_invs
[] = {
1002 SIZE_INV(4), SIZE_INV(5), SIZE_INV(6), SIZE_INV(7),
1003 SIZE_INV(8), SIZE_INV(9), SIZE_INV(10), SIZE_INV(11),
1004 SIZE_INV(12), SIZE_INV(13), SIZE_INV(14), SIZE_INV(15),
1005 SIZE_INV(16), SIZE_INV(17), SIZE_INV(18), SIZE_INV(19),
1006 SIZE_INV(20), SIZE_INV(21), SIZE_INV(22), SIZE_INV(23),
1007 SIZE_INV(24), SIZE_INV(25), SIZE_INV(26), SIZE_INV(27),
1008 SIZE_INV(28), SIZE_INV(29), SIZE_INV(30), SIZE_INV(31)
1011 if (likely(interval
<= ((sizeof(interval_invs
) /
1012 sizeof(unsigned)) + 2))) {
1013 regind
= (diff
* interval_invs
[interval
- 3]) >>
1016 regind
= diff
/ interval
;
1018 #undef SIZE_INV_SHIFT
1020 assert(diff
== regind
* interval
);
1021 assert(regind
< bin_info
->nregs
);
1026 JEMALLOC_INLINE prof_tctx_t
*
1027 arena_prof_tctx_get(const void *ptr
)
1030 arena_chunk_t
*chunk
;
1031 size_t pageind
, mapbits
;
1033 cassert(config_prof
);
1034 assert(ptr
!= NULL
);
1035 assert(CHUNK_ADDR2BASE(ptr
) != ptr
);
1037 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ptr
);
1038 pageind
= ((uintptr_t)ptr
- (uintptr_t)chunk
) >> LG_PAGE
;
1039 mapbits
= arena_mapbits_get(chunk
, pageind
);
1040 assert((mapbits
& CHUNK_MAP_ALLOCATED
) != 0);
1041 if (likely((mapbits
& CHUNK_MAP_LARGE
) == 0))
1042 ret
= (prof_tctx_t
*)(uintptr_t)1U;
1044 ret
= arena_miscelm_get(chunk
, pageind
)->prof_tctx
;
1049 JEMALLOC_INLINE
void
1050 arena_prof_tctx_set(const void *ptr
, prof_tctx_t
*tctx
)
1052 arena_chunk_t
*chunk
;
1055 cassert(config_prof
);
1056 assert(ptr
!= NULL
);
1057 assert(CHUNK_ADDR2BASE(ptr
) != ptr
);
1059 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ptr
);
1060 pageind
= ((uintptr_t)ptr
- (uintptr_t)chunk
) >> LG_PAGE
;
1061 assert(arena_mapbits_allocated_get(chunk
, pageind
) != 0);
1063 if (unlikely(arena_mapbits_large_get(chunk
, pageind
) != 0))
1064 arena_miscelm_get(chunk
, pageind
)->prof_tctx
= tctx
;
1067 JEMALLOC_ALWAYS_INLINE
void *
1068 arena_malloc(tsd_t
*tsd
, arena_t
*arena
, size_t size
, bool zero
,
1074 assert(size
<= arena_maxclass
);
1076 if (likely(size
<= SMALL_MAXCLASS
)) {
1077 if (likely(try_tcache
) && likely((tcache
= tcache_get(tsd
,
1079 return (tcache_alloc_small(tcache
, size
, zero
));
1081 return (arena_malloc_small(choose_arena(tsd
, arena
),
1086 * Initialize tcache after checking size in order to avoid
1087 * infinite recursion during tcache initialization.
1089 if (try_tcache
&& size
<= tcache_maxclass
&& likely((tcache
=
1090 tcache_get(tsd
, true)) != NULL
))
1091 return (tcache_alloc_large(tcache
, size
, zero
));
1093 return (arena_malloc_large(choose_arena(tsd
, arena
),
1099 /* Return the size of the allocation pointed to by ptr. */
1100 JEMALLOC_ALWAYS_INLINE
size_t
1101 arena_salloc(const void *ptr
, bool demote
)
1104 arena_chunk_t
*chunk
;
1105 size_t pageind
, binind
;
1107 assert(ptr
!= NULL
);
1108 assert(CHUNK_ADDR2BASE(ptr
) != ptr
);
1110 chunk
= (arena_chunk_t
*)CHUNK_ADDR2BASE(ptr
);
1111 pageind
= ((uintptr_t)ptr
- (uintptr_t)chunk
) >> LG_PAGE
;
1112 assert(arena_mapbits_allocated_get(chunk
, pageind
) != 0);
1113 binind
= arena_mapbits_binind_get(chunk
, pageind
);
1114 if (unlikely(binind
== BININD_INVALID
|| (config_prof
&& !demote
&&
1115 arena_mapbits_large_get(chunk
, pageind
) != 0))) {
1117 * Large allocation. In the common case (demote), and as this
1118 * is an inline function, most callers will only end up looking
1119 * at binind to determine that ptr is a small allocation.
1121 assert(((uintptr_t)ptr
& PAGE_MASK
) == 0);
1122 ret
= arena_mapbits_large_size_get(chunk
, pageind
);
1124 assert(pageind
+ (ret
>>LG_PAGE
) <= chunk_npages
);
1125 assert(ret
== PAGE
|| arena_mapbits_large_size_get(chunk
,
1126 pageind
+(ret
>>LG_PAGE
)-1) == 0);
1127 assert(binind
== arena_mapbits_binind_get(chunk
,
1128 pageind
+(ret
>>LG_PAGE
)-1));
1129 assert(arena_mapbits_dirty_get(chunk
, pageind
) ==
1130 arena_mapbits_dirty_get(chunk
, pageind
+(ret
>>LG_PAGE
)-1));
1132 /* Small allocation (possibly promoted to a large object). */
1133 assert(arena_mapbits_large_get(chunk
, pageind
) != 0 ||
1134 arena_ptr_small_binind_get(ptr
, arena_mapbits_get(chunk
,
1135 pageind
)) == binind
);
1136 ret
= small_bin2size(binind
);
1142 JEMALLOC_ALWAYS_INLINE
void
1143 arena_dalloc(tsd_t
*tsd
, arena_chunk_t
*chunk
, void *ptr
, bool try_tcache
)
1145 size_t pageind
, mapbits
;
1148 assert(ptr
!= NULL
);
1149 assert(CHUNK_ADDR2BASE(ptr
) != ptr
);
1151 pageind
= ((uintptr_t)ptr
- (uintptr_t)chunk
) >> LG_PAGE
;
1152 mapbits
= arena_mapbits_get(chunk
, pageind
);
1153 assert(arena_mapbits_allocated_get(chunk
, pageind
) != 0);
1154 if (likely((mapbits
& CHUNK_MAP_LARGE
) == 0)) {
1155 /* Small allocation. */
1156 if (likely(try_tcache
) && likely((tcache
= tcache_get(tsd
,
1158 size_t binind
= arena_ptr_small_binind_get(ptr
,
1160 tcache_dalloc_small(tcache
, ptr
, binind
);
1162 arena_dalloc_small(chunk
->arena
, chunk
, ptr
, pageind
);
1164 size_t size
= arena_mapbits_large_size_get(chunk
, pageind
);
1166 assert(((uintptr_t)ptr
& PAGE_MASK
) == 0);
1168 if (try_tcache
&& size
<= tcache_maxclass
&& likely((tcache
=
1169 tcache_get(tsd
, false)) != NULL
)) {
1170 tcache_dalloc_large(tcache
, ptr
, size
);
1172 arena_dalloc_large(chunk
->arena
, chunk
, ptr
);
1176 JEMALLOC_ALWAYS_INLINE
void
1177 arena_sdalloc(tsd_t
*tsd
, arena_chunk_t
*chunk
, void *ptr
, size_t size
,
1182 assert(ptr
!= NULL
);
1183 assert(CHUNK_ADDR2BASE(ptr
) != ptr
);
1185 if (likely(size
<= SMALL_MAXCLASS
)) {
1186 /* Small allocation. */
1187 if (likely(try_tcache
) && likely((tcache
= tcache_get(tsd
,
1189 size_t binind
= small_size2bin(size
);
1190 tcache_dalloc_small(tcache
, ptr
, binind
);
1192 size_t pageind
= ((uintptr_t)ptr
- (uintptr_t)chunk
) >>
1194 arena_dalloc_small(chunk
->arena
, chunk
, ptr
, pageind
);
1197 assert(((uintptr_t)ptr
& PAGE_MASK
) == 0);
1199 if (try_tcache
&& size
<= tcache_maxclass
&& (tcache
=
1200 tcache_get(tsd
, false)) != NULL
) {
1201 tcache_dalloc_large(tcache
, ptr
, size
);
1203 arena_dalloc_large(chunk
->arena
, chunk
, ptr
);
1206 # endif /* JEMALLOC_ARENA_INLINE_C */
1209 #endif /* JEMALLOC_H_INLINES */
1210 /******************************************************************************/