xref: /netbsd-src/external/bsd/jemalloc.old/dist/src/tcache.c (revision 8e33eff89e26cf71871ead62f0d5063e1313c33a)
1*8e33eff8Schristos #define JEMALLOC_TCACHE_C_
2*8e33eff8Schristos #include "jemalloc/internal/jemalloc_preamble.h"
3*8e33eff8Schristos #include "jemalloc/internal/jemalloc_internal_includes.h"
4*8e33eff8Schristos 
5*8e33eff8Schristos #include "jemalloc/internal/assert.h"
6*8e33eff8Schristos #include "jemalloc/internal/mutex.h"
7*8e33eff8Schristos #include "jemalloc/internal/size_classes.h"
8*8e33eff8Schristos 
9*8e33eff8Schristos /******************************************************************************/
10*8e33eff8Schristos /* Data. */
11*8e33eff8Schristos 
12*8e33eff8Schristos bool	opt_tcache = true;
13*8e33eff8Schristos ssize_t	opt_lg_tcache_max = LG_TCACHE_MAXCLASS_DEFAULT;
14*8e33eff8Schristos 
15*8e33eff8Schristos cache_bin_info_t	*tcache_bin_info;
16*8e33eff8Schristos static unsigned		stack_nelms; /* Total stack elms per tcache. */
17*8e33eff8Schristos 
18*8e33eff8Schristos unsigned		nhbins;
19*8e33eff8Schristos size_t			tcache_maxclass;
20*8e33eff8Schristos 
21*8e33eff8Schristos tcaches_t		*tcaches;
22*8e33eff8Schristos 
23*8e33eff8Schristos /* Index of first element within tcaches that has never been used. */
24*8e33eff8Schristos static unsigned		tcaches_past;
25*8e33eff8Schristos 
26*8e33eff8Schristos /* Head of singly linked list tracking available tcaches elements. */
27*8e33eff8Schristos static tcaches_t	*tcaches_avail;
28*8e33eff8Schristos 
29*8e33eff8Schristos /* Protects tcaches{,_past,_avail}. */
30*8e33eff8Schristos static malloc_mutex_t	tcaches_mtx;
31*8e33eff8Schristos 
32*8e33eff8Schristos /******************************************************************************/
33*8e33eff8Schristos 
34*8e33eff8Schristos size_t
35*8e33eff8Schristos tcache_salloc(tsdn_t *tsdn, const void *ptr) {
36*8e33eff8Schristos 	return arena_salloc(tsdn, ptr);
37*8e33eff8Schristos }
38*8e33eff8Schristos 
39*8e33eff8Schristos void
40*8e33eff8Schristos tcache_event_hard(tsd_t *tsd, tcache_t *tcache) {
41*8e33eff8Schristos 	szind_t binind = tcache->next_gc_bin;
42*8e33eff8Schristos 
43*8e33eff8Schristos 	cache_bin_t *tbin;
44*8e33eff8Schristos 	if (binind < NBINS) {
45*8e33eff8Schristos 		tbin = tcache_small_bin_get(tcache, binind);
46*8e33eff8Schristos 	} else {
47*8e33eff8Schristos 		tbin = tcache_large_bin_get(tcache, binind);
48*8e33eff8Schristos 	}
49*8e33eff8Schristos 	if (tbin->low_water > 0) {
50*8e33eff8Schristos 		/*
51*8e33eff8Schristos 		 * Flush (ceiling) 3/4 of the objects below the low water mark.
52*8e33eff8Schristos 		 */
53*8e33eff8Schristos 		if (binind < NBINS) {
54*8e33eff8Schristos 			tcache_bin_flush_small(tsd, tcache, tbin, binind,
55*8e33eff8Schristos 			    tbin->ncached - tbin->low_water + (tbin->low_water
56*8e33eff8Schristos 			    >> 2));
57*8e33eff8Schristos 			/*
58*8e33eff8Schristos 			 * Reduce fill count by 2X.  Limit lg_fill_div such that
59*8e33eff8Schristos 			 * the fill count is always at least 1.
60*8e33eff8Schristos 			 */
61*8e33eff8Schristos 			cache_bin_info_t *tbin_info = &tcache_bin_info[binind];
62*8e33eff8Schristos 			if ((tbin_info->ncached_max >>
63*8e33eff8Schristos 			     (tcache->lg_fill_div[binind] + 1)) >= 1) {
64*8e33eff8Schristos 				tcache->lg_fill_div[binind]++;
65*8e33eff8Schristos 			}
66*8e33eff8Schristos 		} else {
67*8e33eff8Schristos 			tcache_bin_flush_large(tsd, tbin, binind, tbin->ncached
68*8e33eff8Schristos 			    - tbin->low_water + (tbin->low_water >> 2), tcache);
69*8e33eff8Schristos 		}
70*8e33eff8Schristos 	} else if (tbin->low_water < 0) {
71*8e33eff8Schristos 		/*
72*8e33eff8Schristos 		 * Increase fill count by 2X for small bins.  Make sure
73*8e33eff8Schristos 		 * lg_fill_div stays greater than 0.
74*8e33eff8Schristos 		 */
75*8e33eff8Schristos 		if (binind < NBINS && tcache->lg_fill_div[binind] > 1) {
76*8e33eff8Schristos 			tcache->lg_fill_div[binind]--;
77*8e33eff8Schristos 		}
78*8e33eff8Schristos 	}
79*8e33eff8Schristos 	tbin->low_water = tbin->ncached;
80*8e33eff8Schristos 
81*8e33eff8Schristos 	tcache->next_gc_bin++;
82*8e33eff8Schristos 	if (tcache->next_gc_bin == nhbins) {
83*8e33eff8Schristos 		tcache->next_gc_bin = 0;
84*8e33eff8Schristos 	}
85*8e33eff8Schristos }
86*8e33eff8Schristos 
87*8e33eff8Schristos void *
88*8e33eff8Schristos tcache_alloc_small_hard(tsdn_t *tsdn, arena_t *arena, tcache_t *tcache,
89*8e33eff8Schristos     cache_bin_t *tbin, szind_t binind, bool *tcache_success) {
90*8e33eff8Schristos 	void *ret;
91*8e33eff8Schristos 
92*8e33eff8Schristos 	assert(tcache->arena != NULL);
93*8e33eff8Schristos 	arena_tcache_fill_small(tsdn, arena, tcache, tbin, binind,
94*8e33eff8Schristos 	    config_prof ? tcache->prof_accumbytes : 0);
95*8e33eff8Schristos 	if (config_prof) {
96*8e33eff8Schristos 		tcache->prof_accumbytes = 0;
97*8e33eff8Schristos 	}
98*8e33eff8Schristos 	ret = cache_bin_alloc_easy(tbin, tcache_success);
99*8e33eff8Schristos 
100*8e33eff8Schristos 	return ret;
101*8e33eff8Schristos }
102*8e33eff8Schristos 
103*8e33eff8Schristos void
104*8e33eff8Schristos tcache_bin_flush_small(tsd_t *tsd, tcache_t *tcache, cache_bin_t *tbin,
105*8e33eff8Schristos     szind_t binind, unsigned rem) {
106*8e33eff8Schristos 	bool merged_stats = false;
107*8e33eff8Schristos 
108*8e33eff8Schristos 	assert(binind < NBINS);
109*8e33eff8Schristos 	assert((cache_bin_sz_t)rem <= tbin->ncached);
110*8e33eff8Schristos 
111*8e33eff8Schristos 	arena_t *arena = tcache->arena;
112*8e33eff8Schristos 	assert(arena != NULL);
113*8e33eff8Schristos 	unsigned nflush = tbin->ncached - rem;
114*8e33eff8Schristos 	/* Variable length array must have > 0 length. */
115*8e33eff8Schristos 	VARIABLE_ARRAY(extent_t *, item_extent, nflush + + 1);
116*8e33eff8Schristos 	/* Look up extent once per item. */
117*8e33eff8Schristos 	for (unsigned i = 0 ; i < nflush; i++) {
118*8e33eff8Schristos 		item_extent[i] = iealloc(tsd_tsdn(tsd), *(tbin->avail - 1 - i));
119*8e33eff8Schristos 	}
120*8e33eff8Schristos 
121*8e33eff8Schristos 	while (nflush > 0) {
122*8e33eff8Schristos 		/* Lock the arena bin associated with the first object. */
123*8e33eff8Schristos 		extent_t *extent = item_extent[0];
124*8e33eff8Schristos 		arena_t *bin_arena = extent_arena_get(extent);
125*8e33eff8Schristos 		bin_t *bin = &bin_arena->bins[binind];
126*8e33eff8Schristos 
127*8e33eff8Schristos 		if (config_prof && bin_arena == arena) {
128*8e33eff8Schristos 			if (arena_prof_accum(tsd_tsdn(tsd), arena,
129*8e33eff8Schristos 			    tcache->prof_accumbytes)) {
130*8e33eff8Schristos 				prof_idump(tsd_tsdn(tsd));
131*8e33eff8Schristos 			}
132*8e33eff8Schristos 			tcache->prof_accumbytes = 0;
133*8e33eff8Schristos 		}
134*8e33eff8Schristos 
135*8e33eff8Schristos 		malloc_mutex_lock(tsd_tsdn(tsd), &bin->lock);
136*8e33eff8Schristos 		if (config_stats && bin_arena == arena) {
137*8e33eff8Schristos 			assert(!merged_stats);
138*8e33eff8Schristos 			merged_stats = true;
139*8e33eff8Schristos 			bin->stats.nflushes++;
140*8e33eff8Schristos 			bin->stats.nrequests += tbin->tstats.nrequests;
141*8e33eff8Schristos 			tbin->tstats.nrequests = 0;
142*8e33eff8Schristos 		}
143*8e33eff8Schristos 		unsigned ndeferred = 0;
144*8e33eff8Schristos 		for (unsigned i = 0; i < nflush; i++) {
145*8e33eff8Schristos 			void *ptr = *(tbin->avail - 1 - i);
146*8e33eff8Schristos 			extent = item_extent[i];
147*8e33eff8Schristos 			assert(ptr != NULL && extent != NULL);
148*8e33eff8Schristos 
149*8e33eff8Schristos 			if (extent_arena_get(extent) == bin_arena) {
150*8e33eff8Schristos 				arena_dalloc_bin_junked_locked(tsd_tsdn(tsd),
151*8e33eff8Schristos 				    bin_arena, extent, ptr);
152*8e33eff8Schristos 			} else {
153*8e33eff8Schristos 				/*
154*8e33eff8Schristos 				 * This object was allocated via a different
155*8e33eff8Schristos 				 * arena bin than the one that is currently
156*8e33eff8Schristos 				 * locked.  Stash the object, so that it can be
157*8e33eff8Schristos 				 * handled in a future pass.
158*8e33eff8Schristos 				 */
159*8e33eff8Schristos 				*(tbin->avail - 1 - ndeferred) = ptr;
160*8e33eff8Schristos 				item_extent[ndeferred] = extent;
161*8e33eff8Schristos 				ndeferred++;
162*8e33eff8Schristos 			}
163*8e33eff8Schristos 		}
164*8e33eff8Schristos 		malloc_mutex_unlock(tsd_tsdn(tsd), &bin->lock);
165*8e33eff8Schristos 		arena_decay_ticks(tsd_tsdn(tsd), bin_arena, nflush - ndeferred);
166*8e33eff8Schristos 		nflush = ndeferred;
167*8e33eff8Schristos 	}
168*8e33eff8Schristos 	if (config_stats && !merged_stats) {
169*8e33eff8Schristos 		/*
170*8e33eff8Schristos 		 * The flush loop didn't happen to flush to this thread's
171*8e33eff8Schristos 		 * arena, so the stats didn't get merged.  Manually do so now.
172*8e33eff8Schristos 		 */
173*8e33eff8Schristos 		bin_t *bin = &arena->bins[binind];
174*8e33eff8Schristos 		malloc_mutex_lock(tsd_tsdn(tsd), &bin->lock);
175*8e33eff8Schristos 		bin->stats.nflushes++;
176*8e33eff8Schristos 		bin->stats.nrequests += tbin->tstats.nrequests;
177*8e33eff8Schristos 		tbin->tstats.nrequests = 0;
178*8e33eff8Schristos 		malloc_mutex_unlock(tsd_tsdn(tsd), &bin->lock);
179*8e33eff8Schristos 	}
180*8e33eff8Schristos 
181*8e33eff8Schristos 	memmove(tbin->avail - rem, tbin->avail - tbin->ncached, rem *
182*8e33eff8Schristos 	    sizeof(void *));
183*8e33eff8Schristos 	tbin->ncached = rem;
184*8e33eff8Schristos 	if (tbin->ncached < tbin->low_water) {
185*8e33eff8Schristos 		tbin->low_water = tbin->ncached;
186*8e33eff8Schristos 	}
187*8e33eff8Schristos }
188*8e33eff8Schristos 
189*8e33eff8Schristos void
190*8e33eff8Schristos tcache_bin_flush_large(tsd_t *tsd, cache_bin_t *tbin, szind_t binind,
191*8e33eff8Schristos     unsigned rem, tcache_t *tcache) {
192*8e33eff8Schristos 	bool merged_stats = false;
193*8e33eff8Schristos 
194*8e33eff8Schristos 	assert(binind < nhbins);
195*8e33eff8Schristos 	assert((cache_bin_sz_t)rem <= tbin->ncached);
196*8e33eff8Schristos 
197*8e33eff8Schristos 	arena_t *arena = tcache->arena;
198*8e33eff8Schristos 	assert(arena != NULL);
199*8e33eff8Schristos 	unsigned nflush = tbin->ncached - rem;
200*8e33eff8Schristos 	/* Variable length array must have > 0 length. */
201*8e33eff8Schristos 	VARIABLE_ARRAY(extent_t *, item_extent, nflush + 1);
202*8e33eff8Schristos 	/* Look up extent once per item. */
203*8e33eff8Schristos 	for (unsigned i = 0 ; i < nflush; i++) {
204*8e33eff8Schristos 		item_extent[i] = iealloc(tsd_tsdn(tsd), *(tbin->avail - 1 - i));
205*8e33eff8Schristos 	}
206*8e33eff8Schristos 
207*8e33eff8Schristos 	while (nflush > 0) {
208*8e33eff8Schristos 		/* Lock the arena associated with the first object. */
209*8e33eff8Schristos 		extent_t *extent = item_extent[0];
210*8e33eff8Schristos 		arena_t *locked_arena = extent_arena_get(extent);
211*8e33eff8Schristos 		UNUSED bool idump;
212*8e33eff8Schristos 
213*8e33eff8Schristos 		if (config_prof) {
214*8e33eff8Schristos 			idump = false;
215*8e33eff8Schristos 		}
216*8e33eff8Schristos 
217*8e33eff8Schristos 		malloc_mutex_lock(tsd_tsdn(tsd), &locked_arena->large_mtx);
218*8e33eff8Schristos 		for (unsigned i = 0; i < nflush; i++) {
219*8e33eff8Schristos 			void *ptr = *(tbin->avail - 1 - i);
220*8e33eff8Schristos 			assert(ptr != NULL);
221*8e33eff8Schristos 			extent = item_extent[i];
222*8e33eff8Schristos 			if (extent_arena_get(extent) == locked_arena) {
223*8e33eff8Schristos 				large_dalloc_prep_junked_locked(tsd_tsdn(tsd),
224*8e33eff8Schristos 				    extent);
225*8e33eff8Schristos 			}
226*8e33eff8Schristos 		}
227*8e33eff8Schristos 		if ((config_prof || config_stats) && locked_arena == arena) {
228*8e33eff8Schristos 			if (config_prof) {
229*8e33eff8Schristos 				idump = arena_prof_accum(tsd_tsdn(tsd), arena,
230*8e33eff8Schristos 				    tcache->prof_accumbytes);
231*8e33eff8Schristos 				tcache->prof_accumbytes = 0;
232*8e33eff8Schristos 			}
233*8e33eff8Schristos 			if (config_stats) {
234*8e33eff8Schristos 				merged_stats = true;
235*8e33eff8Schristos 				arena_stats_large_nrequests_add(tsd_tsdn(tsd),
236*8e33eff8Schristos 				    &arena->stats, binind,
237*8e33eff8Schristos 				    tbin->tstats.nrequests);
238*8e33eff8Schristos 				tbin->tstats.nrequests = 0;
239*8e33eff8Schristos 			}
240*8e33eff8Schristos 		}
241*8e33eff8Schristos 		malloc_mutex_unlock(tsd_tsdn(tsd), &locked_arena->large_mtx);
242*8e33eff8Schristos 
243*8e33eff8Schristos 		unsigned ndeferred = 0;
244*8e33eff8Schristos 		for (unsigned i = 0; i < nflush; i++) {
245*8e33eff8Schristos 			void *ptr = *(tbin->avail - 1 - i);
246*8e33eff8Schristos 			extent = item_extent[i];
247*8e33eff8Schristos 			assert(ptr != NULL && extent != NULL);
248*8e33eff8Schristos 
249*8e33eff8Schristos 			if (extent_arena_get(extent) == locked_arena) {
250*8e33eff8Schristos 				large_dalloc_finish(tsd_tsdn(tsd), extent);
251*8e33eff8Schristos 			} else {
252*8e33eff8Schristos 				/*
253*8e33eff8Schristos 				 * This object was allocated via a different
254*8e33eff8Schristos 				 * arena than the one that is currently locked.
255*8e33eff8Schristos 				 * Stash the object, so that it can be handled
256*8e33eff8Schristos 				 * in a future pass.
257*8e33eff8Schristos 				 */
258*8e33eff8Schristos 				*(tbin->avail - 1 - ndeferred) = ptr;
259*8e33eff8Schristos 				item_extent[ndeferred] = extent;
260*8e33eff8Schristos 				ndeferred++;
261*8e33eff8Schristos 			}
262*8e33eff8Schristos 		}
263*8e33eff8Schristos 		if (config_prof && idump) {
264*8e33eff8Schristos 			prof_idump(tsd_tsdn(tsd));
265*8e33eff8Schristos 		}
266*8e33eff8Schristos 		arena_decay_ticks(tsd_tsdn(tsd), locked_arena, nflush -
267*8e33eff8Schristos 		    ndeferred);
268*8e33eff8Schristos 		nflush = ndeferred;
269*8e33eff8Schristos 	}
270*8e33eff8Schristos 	if (config_stats && !merged_stats) {
271*8e33eff8Schristos 		/*
272*8e33eff8Schristos 		 * The flush loop didn't happen to flush to this thread's
273*8e33eff8Schristos 		 * arena, so the stats didn't get merged.  Manually do so now.
274*8e33eff8Schristos 		 */
275*8e33eff8Schristos 		arena_stats_large_nrequests_add(tsd_tsdn(tsd), &arena->stats,
276*8e33eff8Schristos 		    binind, tbin->tstats.nrequests);
277*8e33eff8Schristos 		tbin->tstats.nrequests = 0;
278*8e33eff8Schristos 	}
279*8e33eff8Schristos 
280*8e33eff8Schristos 	memmove(tbin->avail - rem, tbin->avail - tbin->ncached, rem *
281*8e33eff8Schristos 	    sizeof(void *));
282*8e33eff8Schristos 	tbin->ncached = rem;
283*8e33eff8Schristos 	if (tbin->ncached < tbin->low_water) {
284*8e33eff8Schristos 		tbin->low_water = tbin->ncached;
285*8e33eff8Schristos 	}
286*8e33eff8Schristos }
287*8e33eff8Schristos 
288*8e33eff8Schristos void
289*8e33eff8Schristos tcache_arena_associate(tsdn_t *tsdn, tcache_t *tcache, arena_t *arena) {
290*8e33eff8Schristos 	assert(tcache->arena == NULL);
291*8e33eff8Schristos 	tcache->arena = arena;
292*8e33eff8Schristos 
293*8e33eff8Schristos 	if (config_stats) {
294*8e33eff8Schristos 		/* Link into list of extant tcaches. */
295*8e33eff8Schristos 		malloc_mutex_lock(tsdn, &arena->tcache_ql_mtx);
296*8e33eff8Schristos 
297*8e33eff8Schristos 		ql_elm_new(tcache, link);
298*8e33eff8Schristos 		ql_tail_insert(&arena->tcache_ql, tcache, link);
299*8e33eff8Schristos 		cache_bin_array_descriptor_init(
300*8e33eff8Schristos 		    &tcache->cache_bin_array_descriptor, tcache->bins_small,
301*8e33eff8Schristos 		    tcache->bins_large);
302*8e33eff8Schristos 		ql_tail_insert(&arena->cache_bin_array_descriptor_ql,
303*8e33eff8Schristos 		    &tcache->cache_bin_array_descriptor, link);
304*8e33eff8Schristos 
305*8e33eff8Schristos 		malloc_mutex_unlock(tsdn, &arena->tcache_ql_mtx);
306*8e33eff8Schristos 	}
307*8e33eff8Schristos }
308*8e33eff8Schristos 
309*8e33eff8Schristos static void
310*8e33eff8Schristos tcache_arena_dissociate(tsdn_t *tsdn, tcache_t *tcache) {
311*8e33eff8Schristos 	arena_t *arena = tcache->arena;
312*8e33eff8Schristos 	assert(arena != NULL);
313*8e33eff8Schristos 	if (config_stats) {
314*8e33eff8Schristos 		/* Unlink from list of extant tcaches. */
315*8e33eff8Schristos 		malloc_mutex_lock(tsdn, &arena->tcache_ql_mtx);
316*8e33eff8Schristos 		if (config_debug) {
317*8e33eff8Schristos 			bool in_ql = false;
318*8e33eff8Schristos 			tcache_t *iter;
319*8e33eff8Schristos 			ql_foreach(iter, &arena->tcache_ql, link) {
320*8e33eff8Schristos 				if (iter == tcache) {
321*8e33eff8Schristos 					in_ql = true;
322*8e33eff8Schristos 					break;
323*8e33eff8Schristos 				}
324*8e33eff8Schristos 			}
325*8e33eff8Schristos 			assert(in_ql);
326*8e33eff8Schristos 		}
327*8e33eff8Schristos 		ql_remove(&arena->tcache_ql, tcache, link);
328*8e33eff8Schristos 		ql_remove(&arena->cache_bin_array_descriptor_ql,
329*8e33eff8Schristos 		    &tcache->cache_bin_array_descriptor, link);
330*8e33eff8Schristos 		tcache_stats_merge(tsdn, tcache, arena);
331*8e33eff8Schristos 		malloc_mutex_unlock(tsdn, &arena->tcache_ql_mtx);
332*8e33eff8Schristos 	}
333*8e33eff8Schristos 	tcache->arena = NULL;
334*8e33eff8Schristos }
335*8e33eff8Schristos 
336*8e33eff8Schristos void
337*8e33eff8Schristos tcache_arena_reassociate(tsdn_t *tsdn, tcache_t *tcache, arena_t *arena) {
338*8e33eff8Schristos 	tcache_arena_dissociate(tsdn, tcache);
339*8e33eff8Schristos 	tcache_arena_associate(tsdn, tcache, arena);
340*8e33eff8Schristos }
341*8e33eff8Schristos 
342*8e33eff8Schristos bool
343*8e33eff8Schristos tsd_tcache_enabled_data_init(tsd_t *tsd) {
344*8e33eff8Schristos 	/* Called upon tsd initialization. */
345*8e33eff8Schristos 	tsd_tcache_enabled_set(tsd, opt_tcache);
346*8e33eff8Schristos 	tsd_slow_update(tsd);
347*8e33eff8Schristos 
348*8e33eff8Schristos 	if (opt_tcache) {
349*8e33eff8Schristos 		/* Trigger tcache init. */
350*8e33eff8Schristos 		tsd_tcache_data_init(tsd);
351*8e33eff8Schristos 	}
352*8e33eff8Schristos 
353*8e33eff8Schristos 	return false;
354*8e33eff8Schristos }
355*8e33eff8Schristos 
356*8e33eff8Schristos /* Initialize auto tcache (embedded in TSD). */
357*8e33eff8Schristos static void
358*8e33eff8Schristos tcache_init(tsd_t *tsd, tcache_t *tcache, void *avail_stack) {
359*8e33eff8Schristos 	memset(&tcache->link, 0, sizeof(ql_elm(tcache_t)));
360*8e33eff8Schristos 	tcache->prof_accumbytes = 0;
361*8e33eff8Schristos 	tcache->next_gc_bin = 0;
362*8e33eff8Schristos 	tcache->arena = NULL;
363*8e33eff8Schristos 
364*8e33eff8Schristos 	ticker_init(&tcache->gc_ticker, TCACHE_GC_INCR);
365*8e33eff8Schristos 
366*8e33eff8Schristos 	size_t stack_offset = 0;
367*8e33eff8Schristos 	assert((TCACHE_NSLOTS_SMALL_MAX & 1U) == 0);
368*8e33eff8Schristos 	memset(tcache->bins_small, 0, sizeof(cache_bin_t) * NBINS);
369*8e33eff8Schristos 	memset(tcache->bins_large, 0, sizeof(cache_bin_t) * (nhbins - NBINS));
370*8e33eff8Schristos 	unsigned i = 0;
371*8e33eff8Schristos 	for (; i < NBINS; i++) {
372*8e33eff8Schristos 		tcache->lg_fill_div[i] = 1;
373*8e33eff8Schristos 		stack_offset += tcache_bin_info[i].ncached_max * sizeof(void *);
374*8e33eff8Schristos 		/*
375*8e33eff8Schristos 		 * avail points past the available space.  Allocations will
376*8e33eff8Schristos 		 * access the slots toward higher addresses (for the benefit of
377*8e33eff8Schristos 		 * prefetch).
378*8e33eff8Schristos 		 */
379*8e33eff8Schristos 		tcache_small_bin_get(tcache, i)->avail =
380*8e33eff8Schristos 		    (void **)((uintptr_t)avail_stack + (uintptr_t)stack_offset);
381*8e33eff8Schristos 	}
382*8e33eff8Schristos 	for (; i < nhbins; i++) {
383*8e33eff8Schristos 		stack_offset += tcache_bin_info[i].ncached_max * sizeof(void *);
384*8e33eff8Schristos 		tcache_large_bin_get(tcache, i)->avail =
385*8e33eff8Schristos 		    (void **)((uintptr_t)avail_stack + (uintptr_t)stack_offset);
386*8e33eff8Schristos 	}
387*8e33eff8Schristos 	assert(stack_offset == stack_nelms * sizeof(void *));
388*8e33eff8Schristos }
389*8e33eff8Schristos 
390*8e33eff8Schristos /* Initialize auto tcache (embedded in TSD). */
391*8e33eff8Schristos bool
392*8e33eff8Schristos tsd_tcache_data_init(tsd_t *tsd) {
393*8e33eff8Schristos 	tcache_t *tcache = tsd_tcachep_get_unsafe(tsd);
394*8e33eff8Schristos 	assert(tcache_small_bin_get(tcache, 0)->avail == NULL);
395*8e33eff8Schristos 	size_t size = stack_nelms * sizeof(void *);
396*8e33eff8Schristos 	/* Avoid false cacheline sharing. */
397*8e33eff8Schristos 	size = sz_sa2u(size, CACHELINE);
398*8e33eff8Schristos 
399*8e33eff8Schristos 	void *avail_array = ipallocztm(tsd_tsdn(tsd), size, CACHELINE, true,
400*8e33eff8Schristos 	    NULL, true, arena_get(TSDN_NULL, 0, true));
401*8e33eff8Schristos 	if (avail_array == NULL) {
402*8e33eff8Schristos 		return true;
403*8e33eff8Schristos 	}
404*8e33eff8Schristos 
405*8e33eff8Schristos 	tcache_init(tsd, tcache, avail_array);
406*8e33eff8Schristos 	/*
407*8e33eff8Schristos 	 * Initialization is a bit tricky here.  After malloc init is done, all
408*8e33eff8Schristos 	 * threads can rely on arena_choose and associate tcache accordingly.
409*8e33eff8Schristos 	 * However, the thread that does actual malloc bootstrapping relies on
410*8e33eff8Schristos 	 * functional tsd, and it can only rely on a0.  In that case, we
411*8e33eff8Schristos 	 * associate its tcache to a0 temporarily, and later on
412*8e33eff8Schristos 	 * arena_choose_hard() will re-associate properly.
413*8e33eff8Schristos 	 */
414*8e33eff8Schristos 	tcache->arena = NULL;
415*8e33eff8Schristos 	arena_t *arena;
416*8e33eff8Schristos 	if (!malloc_initialized()) {
417*8e33eff8Schristos 		/* If in initialization, assign to a0. */
418*8e33eff8Schristos 		arena = arena_get(tsd_tsdn(tsd), 0, false);
419*8e33eff8Schristos 		tcache_arena_associate(tsd_tsdn(tsd), tcache, arena);
420*8e33eff8Schristos 	} else {
421*8e33eff8Schristos 		arena = arena_choose(tsd, NULL);
422*8e33eff8Schristos 		/* This may happen if thread.tcache.enabled is used. */
423*8e33eff8Schristos 		if (tcache->arena == NULL) {
424*8e33eff8Schristos 			tcache_arena_associate(tsd_tsdn(tsd), tcache, arena);
425*8e33eff8Schristos 		}
426*8e33eff8Schristos 	}
427*8e33eff8Schristos 	assert(arena == tcache->arena);
428*8e33eff8Schristos 
429*8e33eff8Schristos 	return false;
430*8e33eff8Schristos }
431*8e33eff8Schristos 
432*8e33eff8Schristos /* Created manual tcache for tcache.create mallctl. */
433*8e33eff8Schristos tcache_t *
434*8e33eff8Schristos tcache_create_explicit(tsd_t *tsd) {
435*8e33eff8Schristos 	tcache_t *tcache;
436*8e33eff8Schristos 	size_t size, stack_offset;
437*8e33eff8Schristos 
438*8e33eff8Schristos 	size = sizeof(tcache_t);
439*8e33eff8Schristos 	/* Naturally align the pointer stacks. */
440*8e33eff8Schristos 	size = PTR_CEILING(size);
441*8e33eff8Schristos 	stack_offset = size;
442*8e33eff8Schristos 	size += stack_nelms * sizeof(void *);
443*8e33eff8Schristos 	/* Avoid false cacheline sharing. */
444*8e33eff8Schristos 	size = sz_sa2u(size, CACHELINE);
445*8e33eff8Schristos 
446*8e33eff8Schristos 	tcache = ipallocztm(tsd_tsdn(tsd), size, CACHELINE, true, NULL, true,
447*8e33eff8Schristos 	    arena_get(TSDN_NULL, 0, true));
448*8e33eff8Schristos 	if (tcache == NULL) {
449*8e33eff8Schristos 		return NULL;
450*8e33eff8Schristos 	}
451*8e33eff8Schristos 
452*8e33eff8Schristos 	tcache_init(tsd, tcache,
453*8e33eff8Schristos 	    (void *)((uintptr_t)tcache + (uintptr_t)stack_offset));
454*8e33eff8Schristos 	tcache_arena_associate(tsd_tsdn(tsd), tcache, arena_ichoose(tsd, NULL));
455*8e33eff8Schristos 
456*8e33eff8Schristos 	return tcache;
457*8e33eff8Schristos }
458*8e33eff8Schristos 
459*8e33eff8Schristos static void
460*8e33eff8Schristos tcache_flush_cache(tsd_t *tsd, tcache_t *tcache) {
461*8e33eff8Schristos 	assert(tcache->arena != NULL);
462*8e33eff8Schristos 
463*8e33eff8Schristos 	for (unsigned i = 0; i < NBINS; i++) {
464*8e33eff8Schristos 		cache_bin_t *tbin = tcache_small_bin_get(tcache, i);
465*8e33eff8Schristos 		tcache_bin_flush_small(tsd, tcache, tbin, i, 0);
466*8e33eff8Schristos 
467*8e33eff8Schristos 		if (config_stats) {
468*8e33eff8Schristos 			assert(tbin->tstats.nrequests == 0);
469*8e33eff8Schristos 		}
470*8e33eff8Schristos 	}
471*8e33eff8Schristos 	for (unsigned i = NBINS; i < nhbins; i++) {
472*8e33eff8Schristos 		cache_bin_t *tbin = tcache_large_bin_get(tcache, i);
473*8e33eff8Schristos 		tcache_bin_flush_large(tsd, tbin, i, 0, tcache);
474*8e33eff8Schristos 
475*8e33eff8Schristos 		if (config_stats) {
476*8e33eff8Schristos 			assert(tbin->tstats.nrequests == 0);
477*8e33eff8Schristos 		}
478*8e33eff8Schristos 	}
479*8e33eff8Schristos 
480*8e33eff8Schristos 	if (config_prof && tcache->prof_accumbytes > 0 &&
481*8e33eff8Schristos 	    arena_prof_accum(tsd_tsdn(tsd), tcache->arena,
482*8e33eff8Schristos 	    tcache->prof_accumbytes)) {
483*8e33eff8Schristos 		prof_idump(tsd_tsdn(tsd));
484*8e33eff8Schristos 	}
485*8e33eff8Schristos }
486*8e33eff8Schristos 
487*8e33eff8Schristos void
488*8e33eff8Schristos tcache_flush(tsd_t *tsd) {
489*8e33eff8Schristos 	assert(tcache_available(tsd));
490*8e33eff8Schristos 	tcache_flush_cache(tsd, tsd_tcachep_get(tsd));
491*8e33eff8Schristos }
492*8e33eff8Schristos 
493*8e33eff8Schristos static void
494*8e33eff8Schristos tcache_destroy(tsd_t *tsd, tcache_t *tcache, bool tsd_tcache) {
495*8e33eff8Schristos 	tcache_flush_cache(tsd, tcache);
496*8e33eff8Schristos 	tcache_arena_dissociate(tsd_tsdn(tsd), tcache);
497*8e33eff8Schristos 
498*8e33eff8Schristos 	if (tsd_tcache) {
499*8e33eff8Schristos 		/* Release the avail array for the TSD embedded auto tcache. */
500*8e33eff8Schristos 		void *avail_array =
501*8e33eff8Schristos 		    (void *)((uintptr_t)tcache_small_bin_get(tcache, 0)->avail -
502*8e33eff8Schristos 		    (uintptr_t)tcache_bin_info[0].ncached_max * sizeof(void *));
503*8e33eff8Schristos 		idalloctm(tsd_tsdn(tsd), avail_array, NULL, NULL, true, true);
504*8e33eff8Schristos 	} else {
505*8e33eff8Schristos 		/* Release both the tcache struct and avail array. */
506*8e33eff8Schristos 		idalloctm(tsd_tsdn(tsd), tcache, NULL, NULL, true, true);
507*8e33eff8Schristos 	}
508*8e33eff8Schristos }
509*8e33eff8Schristos 
510*8e33eff8Schristos /* For auto tcache (embedded in TSD) only. */
511*8e33eff8Schristos void
512*8e33eff8Schristos tcache_cleanup(tsd_t *tsd) {
513*8e33eff8Schristos 	tcache_t *tcache = tsd_tcachep_get(tsd);
514*8e33eff8Schristos 	if (!tcache_available(tsd)) {
515*8e33eff8Schristos 		assert(tsd_tcache_enabled_get(tsd) == false);
516*8e33eff8Schristos 		if (config_debug) {
517*8e33eff8Schristos 			assert(tcache_small_bin_get(tcache, 0)->avail == NULL);
518*8e33eff8Schristos 		}
519*8e33eff8Schristos 		return;
520*8e33eff8Schristos 	}
521*8e33eff8Schristos 	assert(tsd_tcache_enabled_get(tsd));
522*8e33eff8Schristos 	assert(tcache_small_bin_get(tcache, 0)->avail != NULL);
523*8e33eff8Schristos 
524*8e33eff8Schristos 	tcache_destroy(tsd, tcache, true);
525*8e33eff8Schristos 	if (config_debug) {
526*8e33eff8Schristos 		tcache_small_bin_get(tcache, 0)->avail = NULL;
527*8e33eff8Schristos 	}
528*8e33eff8Schristos }
529*8e33eff8Schristos 
530*8e33eff8Schristos void
531*8e33eff8Schristos tcache_stats_merge(tsdn_t *tsdn, tcache_t *tcache, arena_t *arena) {
532*8e33eff8Schristos 	unsigned i;
533*8e33eff8Schristos 
534*8e33eff8Schristos 	cassert(config_stats);
535*8e33eff8Schristos 
536*8e33eff8Schristos 	/* Merge and reset tcache stats. */
537*8e33eff8Schristos 	for (i = 0; i < NBINS; i++) {
538*8e33eff8Schristos 		bin_t *bin = &arena->bins[i];
539*8e33eff8Schristos 		cache_bin_t *tbin = tcache_small_bin_get(tcache, i);
540*8e33eff8Schristos 		malloc_mutex_lock(tsdn, &bin->lock);
541*8e33eff8Schristos 		bin->stats.nrequests += tbin->tstats.nrequests;
542*8e33eff8Schristos 		malloc_mutex_unlock(tsdn, &bin->lock);
543*8e33eff8Schristos 		tbin->tstats.nrequests = 0;
544*8e33eff8Schristos 	}
545*8e33eff8Schristos 
546*8e33eff8Schristos 	for (; i < nhbins; i++) {
547*8e33eff8Schristos 		cache_bin_t *tbin = tcache_large_bin_get(tcache, i);
548*8e33eff8Schristos 		arena_stats_large_nrequests_add(tsdn, &arena->stats, i,
549*8e33eff8Schristos 		    tbin->tstats.nrequests);
550*8e33eff8Schristos 		tbin->tstats.nrequests = 0;
551*8e33eff8Schristos 	}
552*8e33eff8Schristos }
553*8e33eff8Schristos 
554*8e33eff8Schristos static bool
555*8e33eff8Schristos tcaches_create_prep(tsd_t *tsd) {
556*8e33eff8Schristos 	bool err;
557*8e33eff8Schristos 
558*8e33eff8Schristos 	malloc_mutex_lock(tsd_tsdn(tsd), &tcaches_mtx);
559*8e33eff8Schristos 
560*8e33eff8Schristos 	if (tcaches == NULL) {
561*8e33eff8Schristos 		tcaches = base_alloc(tsd_tsdn(tsd), b0get(), sizeof(tcache_t *)
562*8e33eff8Schristos 		    * (MALLOCX_TCACHE_MAX+1), CACHELINE);
563*8e33eff8Schristos 		if (tcaches == NULL) {
564*8e33eff8Schristos 			err = true;
565*8e33eff8Schristos 			goto label_return;
566*8e33eff8Schristos 		}
567*8e33eff8Schristos 	}
568*8e33eff8Schristos 
569*8e33eff8Schristos 	if (tcaches_avail == NULL && tcaches_past > MALLOCX_TCACHE_MAX) {
570*8e33eff8Schristos 		err = true;
571*8e33eff8Schristos 		goto label_return;
572*8e33eff8Schristos 	}
573*8e33eff8Schristos 
574*8e33eff8Schristos 	err = false;
575*8e33eff8Schristos label_return:
576*8e33eff8Schristos 	malloc_mutex_unlock(tsd_tsdn(tsd), &tcaches_mtx);
577*8e33eff8Schristos 	return err;
578*8e33eff8Schristos }
579*8e33eff8Schristos 
580*8e33eff8Schristos bool
581*8e33eff8Schristos tcaches_create(tsd_t *tsd, unsigned *r_ind) {
582*8e33eff8Schristos 	witness_assert_depth(tsdn_witness_tsdp_get(tsd_tsdn(tsd)), 0);
583*8e33eff8Schristos 
584*8e33eff8Schristos 	bool err;
585*8e33eff8Schristos 
586*8e33eff8Schristos 	if (tcaches_create_prep(tsd)) {
587*8e33eff8Schristos 		err = true;
588*8e33eff8Schristos 		goto label_return;
589*8e33eff8Schristos 	}
590*8e33eff8Schristos 
591*8e33eff8Schristos 	tcache_t *tcache = tcache_create_explicit(tsd);
592*8e33eff8Schristos 	if (tcache == NULL) {
593*8e33eff8Schristos 		err = true;
594*8e33eff8Schristos 		goto label_return;
595*8e33eff8Schristos 	}
596*8e33eff8Schristos 
597*8e33eff8Schristos 	tcaches_t *elm;
598*8e33eff8Schristos 	malloc_mutex_lock(tsd_tsdn(tsd), &tcaches_mtx);
599*8e33eff8Schristos 	if (tcaches_avail != NULL) {
600*8e33eff8Schristos 		elm = tcaches_avail;
601*8e33eff8Schristos 		tcaches_avail = tcaches_avail->next;
602*8e33eff8Schristos 		elm->tcache = tcache;
603*8e33eff8Schristos 		*r_ind = (unsigned)(elm - tcaches);
604*8e33eff8Schristos 	} else {
605*8e33eff8Schristos 		elm = &tcaches[tcaches_past];
606*8e33eff8Schristos 		elm->tcache = tcache;
607*8e33eff8Schristos 		*r_ind = tcaches_past;
608*8e33eff8Schristos 		tcaches_past++;
609*8e33eff8Schristos 	}
610*8e33eff8Schristos 	malloc_mutex_unlock(tsd_tsdn(tsd), &tcaches_mtx);
611*8e33eff8Schristos 
612*8e33eff8Schristos 	err = false;
613*8e33eff8Schristos label_return:
614*8e33eff8Schristos 	witness_assert_depth(tsdn_witness_tsdp_get(tsd_tsdn(tsd)), 0);
615*8e33eff8Schristos 	return err;
616*8e33eff8Schristos }
617*8e33eff8Schristos 
618*8e33eff8Schristos static tcache_t *
619*8e33eff8Schristos tcaches_elm_remove(tsd_t *tsd, tcaches_t *elm) {
620*8e33eff8Schristos 	malloc_mutex_assert_owner(tsd_tsdn(tsd), &tcaches_mtx);
621*8e33eff8Schristos 
622*8e33eff8Schristos 	if (elm->tcache == NULL) {
623*8e33eff8Schristos 		return NULL;
624*8e33eff8Schristos 	}
625*8e33eff8Schristos 	tcache_t *tcache = elm->tcache;
626*8e33eff8Schristos 	elm->tcache = NULL;
627*8e33eff8Schristos 	return tcache;
628*8e33eff8Schristos }
629*8e33eff8Schristos 
630*8e33eff8Schristos void
631*8e33eff8Schristos tcaches_flush(tsd_t *tsd, unsigned ind) {
632*8e33eff8Schristos 	malloc_mutex_lock(tsd_tsdn(tsd), &tcaches_mtx);
633*8e33eff8Schristos 	tcache_t *tcache = tcaches_elm_remove(tsd, &tcaches[ind]);
634*8e33eff8Schristos 	malloc_mutex_unlock(tsd_tsdn(tsd), &tcaches_mtx);
635*8e33eff8Schristos 	if (tcache != NULL) {
636*8e33eff8Schristos 		tcache_destroy(tsd, tcache, false);
637*8e33eff8Schristos 	}
638*8e33eff8Schristos }
639*8e33eff8Schristos 
640*8e33eff8Schristos void
641*8e33eff8Schristos tcaches_destroy(tsd_t *tsd, unsigned ind) {
642*8e33eff8Schristos 	malloc_mutex_lock(tsd_tsdn(tsd), &tcaches_mtx);
643*8e33eff8Schristos 	tcaches_t *elm = &tcaches[ind];
644*8e33eff8Schristos 	tcache_t *tcache = tcaches_elm_remove(tsd, elm);
645*8e33eff8Schristos 	elm->next = tcaches_avail;
646*8e33eff8Schristos 	tcaches_avail = elm;
647*8e33eff8Schristos 	malloc_mutex_unlock(tsd_tsdn(tsd), &tcaches_mtx);
648*8e33eff8Schristos 	if (tcache != NULL) {
649*8e33eff8Schristos 		tcache_destroy(tsd, tcache, false);
650*8e33eff8Schristos 	}
651*8e33eff8Schristos }
652*8e33eff8Schristos 
653*8e33eff8Schristos bool
654*8e33eff8Schristos tcache_boot(tsdn_t *tsdn) {
655*8e33eff8Schristos 	/* If necessary, clamp opt_lg_tcache_max. */
656*8e33eff8Schristos 	if (opt_lg_tcache_max < 0 || (ZU(1) << opt_lg_tcache_max) <
657*8e33eff8Schristos 	    SMALL_MAXCLASS) {
658*8e33eff8Schristos 		tcache_maxclass = SMALL_MAXCLASS;
659*8e33eff8Schristos 	} else {
660*8e33eff8Schristos 		tcache_maxclass = (ZU(1) << opt_lg_tcache_max);
661*8e33eff8Schristos 	}
662*8e33eff8Schristos 
663*8e33eff8Schristos 	if (malloc_mutex_init(&tcaches_mtx, "tcaches", WITNESS_RANK_TCACHES,
664*8e33eff8Schristos 	    malloc_mutex_rank_exclusive)) {
665*8e33eff8Schristos 		return true;
666*8e33eff8Schristos 	}
667*8e33eff8Schristos 
668*8e33eff8Schristos 	nhbins = sz_size2index(tcache_maxclass) + 1;
669*8e33eff8Schristos 
670*8e33eff8Schristos 	/* Initialize tcache_bin_info. */
671*8e33eff8Schristos 	tcache_bin_info = (cache_bin_info_t *)base_alloc(tsdn, b0get(), nhbins
672*8e33eff8Schristos 	    * sizeof(cache_bin_info_t), CACHELINE);
673*8e33eff8Schristos 	if (tcache_bin_info == NULL) {
674*8e33eff8Schristos 		return true;
675*8e33eff8Schristos 	}
676*8e33eff8Schristos 	stack_nelms = 0;
677*8e33eff8Schristos 	unsigned i;
678*8e33eff8Schristos 	for (i = 0; i < NBINS; i++) {
679*8e33eff8Schristos 		if ((bin_infos[i].nregs << 1) <= TCACHE_NSLOTS_SMALL_MIN) {
680*8e33eff8Schristos 			tcache_bin_info[i].ncached_max =
681*8e33eff8Schristos 			    TCACHE_NSLOTS_SMALL_MIN;
682*8e33eff8Schristos 		} else if ((bin_infos[i].nregs << 1) <=
683*8e33eff8Schristos 		    TCACHE_NSLOTS_SMALL_MAX) {
684*8e33eff8Schristos 			tcache_bin_info[i].ncached_max =
685*8e33eff8Schristos 			    (bin_infos[i].nregs << 1);
686*8e33eff8Schristos 		} else {
687*8e33eff8Schristos 			tcache_bin_info[i].ncached_max =
688*8e33eff8Schristos 			    TCACHE_NSLOTS_SMALL_MAX;
689*8e33eff8Schristos 		}
690*8e33eff8Schristos 		stack_nelms += tcache_bin_info[i].ncached_max;
691*8e33eff8Schristos 	}
692*8e33eff8Schristos 	for (; i < nhbins; i++) {
693*8e33eff8Schristos 		tcache_bin_info[i].ncached_max = TCACHE_NSLOTS_LARGE;
694*8e33eff8Schristos 		stack_nelms += tcache_bin_info[i].ncached_max;
695*8e33eff8Schristos 	}
696*8e33eff8Schristos 
697*8e33eff8Schristos 	return false;
698*8e33eff8Schristos }
699*8e33eff8Schristos 
700*8e33eff8Schristos void
701*8e33eff8Schristos tcache_prefork(tsdn_t *tsdn) {
702*8e33eff8Schristos 	if (!config_prof && opt_tcache) {
703*8e33eff8Schristos 		malloc_mutex_prefork(tsdn, &tcaches_mtx);
704*8e33eff8Schristos 	}
705*8e33eff8Schristos }
706*8e33eff8Schristos 
707*8e33eff8Schristos void
708*8e33eff8Schristos tcache_postfork_parent(tsdn_t *tsdn) {
709*8e33eff8Schristos 	if (!config_prof && opt_tcache) {
710*8e33eff8Schristos 		malloc_mutex_postfork_parent(tsdn, &tcaches_mtx);
711*8e33eff8Schristos 	}
712*8e33eff8Schristos }
713*8e33eff8Schristos 
714*8e33eff8Schristos void
715*8e33eff8Schristos tcache_postfork_child(tsdn_t *tsdn) {
716*8e33eff8Schristos 	if (!config_prof && opt_tcache) {
717*8e33eff8Schristos 		malloc_mutex_postfork_child(tsdn, &tcaches_mtx);
718*8e33eff8Schristos 	}
719*8e33eff8Schristos }
720