1#ifndef JEMALLOC_INTERNAL_ARENA_INLINES_B_H
2#define JEMALLOC_INTERNAL_ARENA_INLINES_B_H
3
4#include "jemalloc/internal/div.h"
5#include "jemalloc/internal/emap.h"
6#include "jemalloc/internal/jemalloc_internal_types.h"
7#include "jemalloc/internal/mutex.h"
8#include "jemalloc/internal/rtree.h"
9#include "jemalloc/internal/safety_check.h"
10#include "jemalloc/internal/sc.h"
11#include "jemalloc/internal/sz.h"
12#include "jemalloc/internal/ticker.h"
13
14static inline arena_t *
15arena_get_from_edata(edata_t *edata) {
16 return (arena_t *)atomic_load_p(&arenas[edata_arena_ind_get(edata)],
17 ATOMIC_RELAXED);
18}
19
20JEMALLOC_ALWAYS_INLINE arena_t *
21arena_choose_maybe_huge(tsd_t *tsd, arena_t *arena, size_t size) {
22 if (arena != NULL) {
23 return arena;
24 }
25
26 /*
27 * For huge allocations, use the dedicated huge arena if both are true:
28 * 1) is using auto arena selection (i.e. arena == NULL), and 2) the
29 * thread is not assigned to a manual arena.
30 */
31 if (unlikely(size >= oversize_threshold)) {
32 arena_t *tsd_arena = tsd_arena_get(tsd);
33 if (tsd_arena == NULL || arena_is_auto(tsd_arena)) {
34 return arena_choose_huge(tsd);
35 }
36 }
37
38 return arena_choose(tsd, NULL);
39}
40
41JEMALLOC_ALWAYS_INLINE void
42arena_prof_info_get(tsd_t *tsd, const void *ptr, emap_alloc_ctx_t *alloc_ctx,
43 prof_info_t *prof_info, bool reset_recent) {
44 cassert(config_prof);
45 assert(ptr != NULL);
46 assert(prof_info != NULL);
47
48 edata_t *edata = NULL;
49 bool is_slab;
50
51 /* Static check. */
52 if (alloc_ctx == NULL) {
53 edata = emap_edata_lookup(tsd_tsdn(tsd), &arena_emap_global,
54 ptr);
55 is_slab = edata_slab_get(edata);
56 } else if (unlikely(!(is_slab = alloc_ctx->slab))) {
57 edata = emap_edata_lookup(tsd_tsdn(tsd), &arena_emap_global,
58 ptr);
59 }
60
61 if (unlikely(!is_slab)) {
62 /* edata must have been initialized at this point. */
63 assert(edata != NULL);
64 large_prof_info_get(tsd, edata, prof_info, reset_recent);
65 } else {
66 prof_info->alloc_tctx = (prof_tctx_t *)(uintptr_t)1U;
67 /*
68 * No need to set other fields in prof_info; they will never be
69 * accessed if (uintptr_t)alloc_tctx == (uintptr_t)1U.
70 */
71 }
72}
73
74JEMALLOC_ALWAYS_INLINE void
75arena_prof_tctx_reset(tsd_t *tsd, const void *ptr,
76 emap_alloc_ctx_t *alloc_ctx) {
77 cassert(config_prof);
78 assert(ptr != NULL);
79
80 /* Static check. */
81 if (alloc_ctx == NULL) {
82 edata_t *edata = emap_edata_lookup(tsd_tsdn(tsd),
83 &arena_emap_global, ptr);
84 if (unlikely(!edata_slab_get(edata))) {
85 large_prof_tctx_reset(edata);
86 }
87 } else {
88 if (unlikely(!alloc_ctx->slab)) {
89 edata_t *edata = emap_edata_lookup(tsd_tsdn(tsd),
90 &arena_emap_global, ptr);
91 large_prof_tctx_reset(edata);
92 }
93 }
94}
95
96JEMALLOC_ALWAYS_INLINE void
97arena_prof_tctx_reset_sampled(tsd_t *tsd, const void *ptr) {
98 cassert(config_prof);
99 assert(ptr != NULL);
100
101 edata_t *edata = emap_edata_lookup(tsd_tsdn(tsd), &arena_emap_global,
102 ptr);
103 assert(!edata_slab_get(edata));
104
105 large_prof_tctx_reset(edata);
106}
107
108JEMALLOC_ALWAYS_INLINE void
109arena_prof_info_set(tsd_t *tsd, edata_t *edata, prof_tctx_t *tctx,
110 size_t size) {
111 cassert(config_prof);
112
113 assert(!edata_slab_get(edata));
114 large_prof_info_set(edata, tctx, size);
115}
116
117JEMALLOC_ALWAYS_INLINE void
118arena_decay_ticks(tsdn_t *tsdn, arena_t *arena, unsigned nticks) {
119 if (unlikely(tsdn_null(tsdn))) {
120 return;
121 }
122 tsd_t *tsd = tsdn_tsd(tsdn);
123 /*
124 * We use the ticker_geom_t to avoid having per-arena state in the tsd.
125 * Instead of having a countdown-until-decay timer running for every
126 * arena in every thread, we flip a coin once per tick, whose
127 * probability of coming up heads is 1/nticks; this is effectively the
128 * operation of the ticker_geom_t. Each arena has the same chance of a
129 * coinflip coming up heads (1/ARENA_DECAY_NTICKS_PER_UPDATE), so we can
130 * use a single ticker for all of them.
131 */
132 ticker_geom_t *decay_ticker = tsd_arena_decay_tickerp_get(tsd);
133 uint64_t *prng_state = tsd_prng_statep_get(tsd);
134 if (unlikely(ticker_geom_ticks(decay_ticker, prng_state, nticks))) {
135 arena_decay(tsdn, arena, false, false);
136 }
137}
138
139JEMALLOC_ALWAYS_INLINE void
140arena_decay_tick(tsdn_t *tsdn, arena_t *arena) {
141 arena_decay_ticks(tsdn, arena, 1);
142}
143
144JEMALLOC_ALWAYS_INLINE void *
145arena_malloc(tsdn_t *tsdn, arena_t *arena, size_t size, szind_t ind, bool zero,
146 tcache_t *tcache, bool slow_path) {
147 assert(!tsdn_null(tsdn) || tcache == NULL);
148
149 if (likely(tcache != NULL)) {
150 if (likely(size <= SC_SMALL_MAXCLASS)) {
151 return tcache_alloc_small(tsdn_tsd(tsdn), arena,
152 tcache, size, ind, zero, slow_path);
153 }
154 if (likely(size <= tcache_maxclass)) {
155 return tcache_alloc_large(tsdn_tsd(tsdn), arena,
156 tcache, size, ind, zero, slow_path);
157 }
158 /* (size > tcache_maxclass) case falls through. */
159 assert(size > tcache_maxclass);
160 }
161
162 return arena_malloc_hard(tsdn, arena, size, ind, zero);
163}
164
165JEMALLOC_ALWAYS_INLINE arena_t *
166arena_aalloc(tsdn_t *tsdn, const void *ptr) {
167 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global, ptr);
168 unsigned arena_ind = edata_arena_ind_get(edata);
169 return (arena_t *)atomic_load_p(&arenas[arena_ind], ATOMIC_RELAXED);
170}
171
172JEMALLOC_ALWAYS_INLINE size_t
173arena_salloc(tsdn_t *tsdn, const void *ptr) {
174 assert(ptr != NULL);
175 emap_alloc_ctx_t alloc_ctx;
176 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr, &alloc_ctx);
177 assert(alloc_ctx.szind != SC_NSIZES);
178
179 return sz_index2size(alloc_ctx.szind);
180}
181
182JEMALLOC_ALWAYS_INLINE size_t
183arena_vsalloc(tsdn_t *tsdn, const void *ptr) {
184 /*
185 * Return 0 if ptr is not within an extent managed by jemalloc. This
186 * function has two extra costs relative to isalloc():
187 * - The rtree calls cannot claim to be dependent lookups, which induces
188 * rtree lookup load dependencies.
189 * - The lookup may fail, so there is an extra branch to check for
190 * failure.
191 */
192
193 emap_full_alloc_ctx_t full_alloc_ctx;
194 bool missing = emap_full_alloc_ctx_try_lookup(tsdn, &arena_emap_global,
195 ptr, &full_alloc_ctx);
196 if (missing) {
197 return 0;
198 }
199
200 if (full_alloc_ctx.edata == NULL) {
201 return 0;
202 }
203 assert(edata_state_get(full_alloc_ctx.edata) == extent_state_active);
204 /* Only slab members should be looked up via interior pointers. */
205 assert(edata_addr_get(full_alloc_ctx.edata) == ptr
206 || edata_slab_get(full_alloc_ctx.edata));
207
208 assert(full_alloc_ctx.szind != SC_NSIZES);
209
210 return sz_index2size(full_alloc_ctx.szind);
211}
212
213JEMALLOC_ALWAYS_INLINE bool
214large_dalloc_safety_checks(edata_t *edata, void *ptr, szind_t szind) {
215 if (!config_opt_safety_checks) {
216 return false;
217 }
218
219 /*
220 * Eagerly detect double free and sized dealloc bugs for large sizes.
221 * The cost is low enough (as edata will be accessed anyway) to be
222 * enabled all the time.
223 */
224 if (unlikely(edata == NULL ||
225 edata_state_get(edata) != extent_state_active)) {
226 safety_check_fail("Invalid deallocation detected: "
227 "pages being freed (%p) not currently active, "
228 "possibly caused by double free bugs.",
229 (uintptr_t)edata_addr_get(edata));
230 return true;
231 }
232 size_t input_size = sz_index2size(szind);
233 if (unlikely(input_size != edata_usize_get(edata))) {
234 safety_check_fail_sized_dealloc(/* current_dealloc */ true, ptr,
235 /* true_size */ edata_usize_get(edata), input_size);
236 return true;
237 }
238
239 return false;
240}
241
242static inline void
243arena_dalloc_large_no_tcache(tsdn_t *tsdn, void *ptr, szind_t szind) {
244 if (config_prof && unlikely(szind < SC_NBINS)) {
245 arena_dalloc_promoted(tsdn, ptr, NULL, true);
246 } else {
247 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global,
248 ptr);
249 if (large_dalloc_safety_checks(edata, ptr, szind)) {
250 /* See the comment in isfree. */
251 return;
252 }
253 large_dalloc(tsdn, edata);
254 }
255}
256
257static inline void
258arena_dalloc_no_tcache(tsdn_t *tsdn, void *ptr) {
259 assert(ptr != NULL);
260
261 emap_alloc_ctx_t alloc_ctx;
262 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr, &alloc_ctx);
263
264 if (config_debug) {
265 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global,
266 ptr);
267 assert(alloc_ctx.szind == edata_szind_get(edata));
268 assert(alloc_ctx.szind < SC_NSIZES);
269 assert(alloc_ctx.slab == edata_slab_get(edata));
270 }
271
272 if (likely(alloc_ctx.slab)) {
273 /* Small allocation. */
274 arena_dalloc_small(tsdn, ptr);
275 } else {
276 arena_dalloc_large_no_tcache(tsdn, ptr, alloc_ctx.szind);
277 }
278}
279
280JEMALLOC_ALWAYS_INLINE void
281arena_dalloc_large(tsdn_t *tsdn, void *ptr, tcache_t *tcache, szind_t szind,
282 bool slow_path) {
283 if (szind < nhbins) {
284 if (config_prof && unlikely(szind < SC_NBINS)) {
285 arena_dalloc_promoted(tsdn, ptr, tcache, slow_path);
286 } else {
287 tcache_dalloc_large(tsdn_tsd(tsdn), tcache, ptr, szind,
288 slow_path);
289 }
290 } else {
291 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global,
292 ptr);
293 if (large_dalloc_safety_checks(edata, ptr, szind)) {
294 /* See the comment in isfree. */
295 return;
296 }
297 large_dalloc(tsdn, edata);
298 }
299}
300
301JEMALLOC_ALWAYS_INLINE void
302arena_dalloc(tsdn_t *tsdn, void *ptr, tcache_t *tcache,
303 emap_alloc_ctx_t *caller_alloc_ctx, bool slow_path) {
304 assert(!tsdn_null(tsdn) || tcache == NULL);
305 assert(ptr != NULL);
306
307 if (unlikely(tcache == NULL)) {
308 arena_dalloc_no_tcache(tsdn, ptr);
309 return;
310 }
311
312 emap_alloc_ctx_t alloc_ctx;
313 if (caller_alloc_ctx != NULL) {
314 alloc_ctx = *caller_alloc_ctx;
315 } else {
316 util_assume(!tsdn_null(tsdn));
317 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr,
318 &alloc_ctx);
319 }
320
321 if (config_debug) {
322 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global,
323 ptr);
324 assert(alloc_ctx.szind == edata_szind_get(edata));
325 assert(alloc_ctx.szind < SC_NSIZES);
326 assert(alloc_ctx.slab == edata_slab_get(edata));
327 }
328
329 if (likely(alloc_ctx.slab)) {
330 /* Small allocation. */
331 tcache_dalloc_small(tsdn_tsd(tsdn), tcache, ptr,
332 alloc_ctx.szind, slow_path);
333 } else {
334 arena_dalloc_large(tsdn, ptr, tcache, alloc_ctx.szind,
335 slow_path);
336 }
337}
338
339static inline void
340arena_sdalloc_no_tcache(tsdn_t *tsdn, void *ptr, size_t size) {
341 assert(ptr != NULL);
342 assert(size <= SC_LARGE_MAXCLASS);
343
344 emap_alloc_ctx_t alloc_ctx;
345 if (!config_prof || !opt_prof) {
346 /*
347 * There is no risk of being confused by a promoted sampled
348 * object, so base szind and slab on the given size.
349 */
350 alloc_ctx.szind = sz_size2index(size);
351 alloc_ctx.slab = (alloc_ctx.szind < SC_NBINS);
352 }
353
354 if ((config_prof && opt_prof) || config_debug) {
355 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr,
356 &alloc_ctx);
357
358 assert(alloc_ctx.szind == sz_size2index(size));
359 assert((config_prof && opt_prof)
360 || alloc_ctx.slab == (alloc_ctx.szind < SC_NBINS));
361
362 if (config_debug) {
363 edata_t *edata = emap_edata_lookup(tsdn,
364 &arena_emap_global, ptr);
365 assert(alloc_ctx.szind == edata_szind_get(edata));
366 assert(alloc_ctx.slab == edata_slab_get(edata));
367 }
368 }
369
370 if (likely(alloc_ctx.slab)) {
371 /* Small allocation. */
372 arena_dalloc_small(tsdn, ptr);
373 } else {
374 arena_dalloc_large_no_tcache(tsdn, ptr, alloc_ctx.szind);
375 }
376}
377
378JEMALLOC_ALWAYS_INLINE void
379arena_sdalloc(tsdn_t *tsdn, void *ptr, size_t size, tcache_t *tcache,
380 emap_alloc_ctx_t *caller_alloc_ctx, bool slow_path) {
381 assert(!tsdn_null(tsdn) || tcache == NULL);
382 assert(ptr != NULL);
383 assert(size <= SC_LARGE_MAXCLASS);
384
385 if (unlikely(tcache == NULL)) {
386 arena_sdalloc_no_tcache(tsdn, ptr, size);
387 return;
388 }
389
390 emap_alloc_ctx_t alloc_ctx;
391 if (config_prof && opt_prof) {
392 if (caller_alloc_ctx == NULL) {
393 /* Uncommon case and should be a static check. */
394 emap_alloc_ctx_lookup(tsdn, &arena_emap_global, ptr,
395 &alloc_ctx);
396 assert(alloc_ctx.szind == sz_size2index(size));
397 } else {
398 alloc_ctx = *caller_alloc_ctx;
399 }
400 } else {
401 /*
402 * There is no risk of being confused by a promoted sampled
403 * object, so base szind and slab on the given size.
404 */
405 alloc_ctx.szind = sz_size2index(size);
406 alloc_ctx.slab = (alloc_ctx.szind < SC_NBINS);
407 }
408
409 if (config_debug) {
410 edata_t *edata = emap_edata_lookup(tsdn, &arena_emap_global,
411 ptr);
412 assert(alloc_ctx.szind == edata_szind_get(edata));
413 assert(alloc_ctx.slab == edata_slab_get(edata));
414 }
415
416 if (likely(alloc_ctx.slab)) {
417 /* Small allocation. */
418 tcache_dalloc_small(tsdn_tsd(tsdn), tcache, ptr,
419 alloc_ctx.szind, slow_path);
420 } else {
421 arena_dalloc_large(tsdn, ptr, tcache, alloc_ctx.szind,
422 slow_path);
423 }
424}
425
426static inline void
427arena_cache_oblivious_randomize(tsdn_t *tsdn, arena_t *arena, edata_t *edata,
428 size_t alignment) {
429 assert(edata_base_get(edata) == edata_addr_get(edata));
430
431 if (alignment < PAGE) {
432 unsigned lg_range = LG_PAGE -
433 lg_floor(CACHELINE_CEILING(alignment));
434 size_t r;
435 if (!tsdn_null(tsdn)) {
436 tsd_t *tsd = tsdn_tsd(tsdn);
437 r = (size_t)prng_lg_range_u64(
438 tsd_prng_statep_get(tsd), lg_range);
439 } else {
440 uint64_t stack_value = (uint64_t)(uintptr_t)&r;
441 r = (size_t)prng_lg_range_u64(&stack_value, lg_range);
442 }
443 uintptr_t random_offset = ((uintptr_t)r) << (LG_PAGE -
444 lg_range);
445 edata->e_addr = (void *)((uintptr_t)edata->e_addr +
446 random_offset);
447 assert(ALIGNMENT_ADDR2BASE(edata->e_addr, alignment) ==
448 edata->e_addr);
449 }
450}
451
452/*
453 * The dalloc bin info contains just the information that the common paths need
454 * during tcache flushes. By force-inlining these paths, and using local copies
455 * of data (so that the compiler knows it's constant), we avoid a whole bunch of
456 * redundant loads and stores by leaving this information in registers.
457 */
458typedef struct arena_dalloc_bin_locked_info_s arena_dalloc_bin_locked_info_t;
459struct arena_dalloc_bin_locked_info_s {
460 div_info_t div_info;
461 uint32_t nregs;
462 uint64_t ndalloc;
463};
464
465JEMALLOC_ALWAYS_INLINE size_t
466arena_slab_regind(arena_dalloc_bin_locked_info_t *info, szind_t binind,
467 edata_t *slab, const void *ptr) {
468 size_t diff, regind;
469
470 /* Freeing a pointer outside the slab can cause assertion failure. */
471 assert((uintptr_t)ptr >= (uintptr_t)edata_addr_get(slab));
472 assert((uintptr_t)ptr < (uintptr_t)edata_past_get(slab));
473 /* Freeing an interior pointer can cause assertion failure. */
474 assert(((uintptr_t)ptr - (uintptr_t)edata_addr_get(slab)) %
475 (uintptr_t)bin_infos[binind].reg_size == 0);
476
477 diff = (size_t)((uintptr_t)ptr - (uintptr_t)edata_addr_get(slab));
478
479 /* Avoid doing division with a variable divisor. */
480 regind = div_compute(&info->div_info, diff);
481
482 assert(regind < bin_infos[binind].nregs);
483
484 return regind;
485}
486
487JEMALLOC_ALWAYS_INLINE void
488arena_dalloc_bin_locked_begin(arena_dalloc_bin_locked_info_t *info,
489 szind_t binind) {
490 info->div_info = arena_binind_div_info[binind];
491 info->nregs = bin_infos[binind].nregs;
492 info->ndalloc = 0;
493}
494
495/*
496 * Does the deallocation work associated with freeing a single pointer (a
497 * "step") in between a arena_dalloc_bin_locked begin and end call.
498 *
499 * Returns true if arena_slab_dalloc must be called on slab. Doesn't do
500 * stats updates, which happen during finish (this lets running counts get left
501 * in a register).
502 */
503JEMALLOC_ALWAYS_INLINE bool
504arena_dalloc_bin_locked_step(tsdn_t *tsdn, arena_t *arena, bin_t *bin,
505 arena_dalloc_bin_locked_info_t *info, szind_t binind, edata_t *slab,
506 void *ptr) {
507 const bin_info_t *bin_info = &bin_infos[binind];
508 size_t regind = arena_slab_regind(info, binind, slab, ptr);
509 slab_data_t *slab_data = edata_slab_data_get(slab);
510
511 assert(edata_nfree_get(slab) < bin_info->nregs);
512 /* Freeing an unallocated pointer can cause assertion failure. */
513 assert(bitmap_get(slab_data->bitmap, &bin_info->bitmap_info, regind));
514
515 bitmap_unset(slab_data->bitmap, &bin_info->bitmap_info, regind);
516 edata_nfree_inc(slab);
517
518 if (config_stats) {
519 info->ndalloc++;
520 }
521
522 unsigned nfree = edata_nfree_get(slab);
523 if (nfree == bin_info->nregs) {
524 arena_dalloc_bin_locked_handle_newly_empty(tsdn, arena, slab,
525 bin);
526 return true;
527 } else if (nfree == 1 && slab != bin->slabcur) {
528 arena_dalloc_bin_locked_handle_newly_nonempty(tsdn, arena, slab,
529 bin);
530 }
531 return false;
532}
533
534JEMALLOC_ALWAYS_INLINE void
535arena_dalloc_bin_locked_finish(tsdn_t *tsdn, arena_t *arena, bin_t *bin,
536 arena_dalloc_bin_locked_info_t *info) {
537 if (config_stats) {
538 bin->stats.ndalloc += info->ndalloc;
539 assert(bin->stats.curregs >= (size_t)info->ndalloc);
540 bin->stats.curregs -= (size_t)info->ndalloc;
541 }
542}
543
544static inline bin_t *
545arena_get_bin(arena_t *arena, szind_t binind, unsigned binshard) {
546 bin_t *shard0 = (bin_t *)((uintptr_t)arena + arena_bin_offsets[binind]);
547 return shard0 + binshard;
548}
549
550#endif /* JEMALLOC_INTERNAL_ARENA_INLINES_B_H */
551