1#define	JEMALLOC_CHUNK_C_
2#include "jemalloc/internal/jemalloc_internal.h"
3
4/******************************************************************************/
5/* Data. */
6
7const char	*opt_dss = DSS_DEFAULT;
8size_t		opt_lg_chunk = LG_CHUNK_DEFAULT;
9
10malloc_mutex_t	chunks_mtx;
11chunk_stats_t	stats_chunks;
12
13/*
14 * Trees of chunks that were previously allocated (trees differ only in node
15 * ordering).  These are used when allocating chunks, in an attempt to re-use
16 * address space.  Depending on function, different tree orderings are needed,
17 * which is why there are two trees with the same contents.
18 */
19static extent_tree_t	chunks_szad_mmap;
20static extent_tree_t	chunks_ad_mmap;
21static extent_tree_t	chunks_szad_dss;
22static extent_tree_t	chunks_ad_dss;
23
24rtree_t		*chunks_rtree;
25
26/* Various chunk-related settings. */
27size_t		chunksize;
28size_t		chunksize_mask; /* (chunksize - 1). */
29size_t		chunk_npages;
30size_t		map_bias;
31size_t		arena_maxclass; /* Max size class for arenas. */
32
33/******************************************************************************/
34/* Function prototypes for non-inline static functions. */
35
36static void	*chunk_recycle(extent_tree_t *chunks_szad,
37    extent_tree_t *chunks_ad, size_t size, size_t alignment, bool base,
38    bool *zero);
39static void	chunk_record(extent_tree_t *chunks_szad,
40    extent_tree_t *chunks_ad, void *chunk, size_t size);
41
42/******************************************************************************/
43
44static void *
45chunk_recycle(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, size_t size,
46    size_t alignment, bool base, bool *zero)
47{
48	void *ret;
49	extent_node_t *node;
50	extent_node_t key;
51	size_t alloc_size, leadsize, trailsize;
52	bool zeroed;
53
54	if (base) {
55		/*
56		 * This function may need to call base_node_{,de}alloc(), but
57		 * the current chunk allocation request is on behalf of the
58		 * base allocator.  Avoid deadlock (and if that weren't an
59		 * issue, potential for infinite recursion) by returning NULL.
60		 */
61		return (NULL);
62	}
63
64	alloc_size = size + alignment - chunksize;
65	/* Beware size_t wrap-around. */
66	if (alloc_size < size)
67		return (NULL);
68	key.addr = NULL;
69	key.size = alloc_size;
70	malloc_mutex_lock(&chunks_mtx);
71	node = extent_tree_szad_nsearch(chunks_szad, &key);
72	if (node == NULL) {
73		malloc_mutex_unlock(&chunks_mtx);
74		return (NULL);
75	}
76	leadsize = ALIGNMENT_CEILING((uintptr_t)node->addr, alignment) -
77	    (uintptr_t)node->addr;
78	assert(node->size >= leadsize + size);
79	trailsize = node->size - leadsize - size;
80	ret = (void *)((uintptr_t)node->addr + leadsize);
81	zeroed = node->zeroed;
82	if (zeroed)
83	    *zero = true;
84	/* Remove node from the tree. */
85	extent_tree_szad_remove(chunks_szad, node);
86	extent_tree_ad_remove(chunks_ad, node);
87	if (leadsize != 0) {
88		/* Insert the leading space as a smaller chunk. */
89		node->size = leadsize;
90		extent_tree_szad_insert(chunks_szad, node);
91		extent_tree_ad_insert(chunks_ad, node);
92		node = NULL;
93	}
94	if (trailsize != 0) {
95		/* Insert the trailing space as a smaller chunk. */
96		if (node == NULL) {
97			/*
98			 * An additional node is required, but
99			 * base_node_alloc() can cause a new base chunk to be
100			 * allocated.  Drop chunks_mtx in order to avoid
101			 * deadlock, and if node allocation fails, deallocate
102			 * the result before returning an error.
103			 */
104			malloc_mutex_unlock(&chunks_mtx);
105			node = base_node_alloc();
106			if (node == NULL) {
107				chunk_dealloc(ret, size, true);
108				return (NULL);
109			}
110			malloc_mutex_lock(&chunks_mtx);
111		}
112		node->addr = (void *)((uintptr_t)(ret) + size);
113		node->size = trailsize;
114		node->zeroed = zeroed;
115		extent_tree_szad_insert(chunks_szad, node);
116		extent_tree_ad_insert(chunks_ad, node);
117		node = NULL;
118	}
119	malloc_mutex_unlock(&chunks_mtx);
120
121	if (node != NULL)
122		base_node_dealloc(node);
123	if (*zero) {
124		if (zeroed == false)
125			memset(ret, 0, size);
126		else if (config_debug) {
127			size_t i;
128			size_t *p = (size_t *)(uintptr_t)ret;
129
130			VALGRIND_MAKE_MEM_DEFINED(ret, size);
131			for (i = 0; i < size / sizeof(size_t); i++)
132				assert(p[i] == 0);
133		}
134	}
135	return (ret);
136}
137
138/*
139 * If the caller specifies (*zero == false), it is still possible to receive
140 * zeroed memory, in which case *zero is toggled to true.  arena_chunk_alloc()
141 * takes advantage of this to avoid demanding zeroed chunks, but taking
142 * advantage of them if they are returned.
143 */
144void *
145chunk_alloc(size_t size, size_t alignment, bool base, bool *zero,
146    dss_prec_t dss_prec)
147{
148	void *ret;
149
150	assert(size != 0);
151	assert((size & chunksize_mask) == 0);
152	assert(alignment != 0);
153	assert((alignment & chunksize_mask) == 0);
154
155	/* "primary" dss. */
156	if (config_dss && dss_prec == dss_prec_primary) {
157		if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size,
158		    alignment, base, zero)) != NULL)
159			goto label_return;
160		if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL)
161			goto label_return;
162	}
163	/* mmap. */
164	if ((ret = chunk_recycle(&chunks_szad_mmap, &chunks_ad_mmap, size,
165	    alignment, base, zero)) != NULL)
166		goto label_return;
167	if ((ret = chunk_alloc_mmap(size, alignment, zero)) != NULL)
168		goto label_return;
169	/* "secondary" dss. */
170	if (config_dss && dss_prec == dss_prec_secondary) {
171		if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size,
172		    alignment, base, zero)) != NULL)
173			goto label_return;
174		if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL)
175			goto label_return;
176	}
177
178	/* All strategies for allocation failed. */
179	ret = NULL;
180label_return:
181	if (ret != NULL) {
182		if (config_ivsalloc && base == false) {
183			if (rtree_set(chunks_rtree, (uintptr_t)ret, ret)) {
184				chunk_dealloc(ret, size, true);
185				return (NULL);
186			}
187		}
188		if (config_stats || config_prof) {
189			bool gdump;
190			malloc_mutex_lock(&chunks_mtx);
191			if (config_stats)
192				stats_chunks.nchunks += (size / chunksize);
193			stats_chunks.curchunks += (size / chunksize);
194			if (stats_chunks.curchunks > stats_chunks.highchunks) {
195				stats_chunks.highchunks =
196				    stats_chunks.curchunks;
197				if (config_prof)
198					gdump = true;
199			} else if (config_prof)
200				gdump = false;
201			malloc_mutex_unlock(&chunks_mtx);
202			if (config_prof && opt_prof && opt_prof_gdump && gdump)
203				prof_gdump();
204		}
205		if (config_valgrind)
206			VALGRIND_MAKE_MEM_UNDEFINED(ret, size);
207	}
208	assert(CHUNK_ADDR2BASE(ret) == ret);
209	return (ret);
210}
211
212static void
213chunk_record(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, void *chunk,
214    size_t size)
215{
216	bool unzeroed;
217	extent_node_t *xnode, *node, *prev, *xprev, key;
218
219	unzeroed = pages_purge(chunk, size);
220	VALGRIND_MAKE_MEM_NOACCESS(chunk, size);
221
222	/*
223	 * Allocate a node before acquiring chunks_mtx even though it might not
224	 * be needed, because base_node_alloc() may cause a new base chunk to
225	 * be allocated, which could cause deadlock if chunks_mtx were already
226	 * held.
227	 */
228	xnode = base_node_alloc();
229	/* Use xprev to implement conditional deferred deallocation of prev. */
230	xprev = NULL;
231
232	malloc_mutex_lock(&chunks_mtx);
233	key.addr = (void *)((uintptr_t)chunk + size);
234	node = extent_tree_ad_nsearch(chunks_ad, &key);
235	/* Try to coalesce forward. */
236	if (node != NULL && node->addr == key.addr) {
237		/*
238		 * Coalesce chunk with the following address range.  This does
239		 * not change the position within chunks_ad, so only
240		 * remove/insert from/into chunks_szad.
241		 */
242		extent_tree_szad_remove(chunks_szad, node);
243		node->addr = chunk;
244		node->size += size;
245		node->zeroed = (node->zeroed && (unzeroed == false));
246		extent_tree_szad_insert(chunks_szad, node);
247	} else {
248		/* Coalescing forward failed, so insert a new node. */
249		if (xnode == NULL) {
250			/*
251			 * base_node_alloc() failed, which is an exceedingly
252			 * unlikely failure.  Leak chunk; its pages have
253			 * already been purged, so this is only a virtual
254			 * memory leak.
255			 */
256			goto label_return;
257		}
258		node = xnode;
259		xnode = NULL; /* Prevent deallocation below. */
260		node->addr = chunk;
261		node->size = size;
262		node->zeroed = (unzeroed == false);
263		extent_tree_ad_insert(chunks_ad, node);
264		extent_tree_szad_insert(chunks_szad, node);
265	}
266
267	/* Try to coalesce backward. */
268	prev = extent_tree_ad_prev(chunks_ad, node);
269	if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==
270	    chunk) {
271		/*
272		 * Coalesce chunk with the previous address range.  This does
273		 * not change the position within chunks_ad, so only
274		 * remove/insert node from/into chunks_szad.
275		 */
276		extent_tree_szad_remove(chunks_szad, prev);
277		extent_tree_ad_remove(chunks_ad, prev);
278
279		extent_tree_szad_remove(chunks_szad, node);
280		node->addr = prev->addr;
281		node->size += prev->size;
282		node->zeroed = (node->zeroed && prev->zeroed);
283		extent_tree_szad_insert(chunks_szad, node);
284
285		xprev = prev;
286	}
287
288label_return:
289	malloc_mutex_unlock(&chunks_mtx);
290	/*
291	 * Deallocate xnode and/or xprev after unlocking chunks_mtx in order to
292	 * avoid potential deadlock.
293	 */
294	if (xnode != NULL)
295		base_node_dealloc(xnode);
296	if (xprev != NULL)
297		base_node_dealloc(prev);
298}
299
300void
301chunk_unmap(void *chunk, size_t size)
302{
303	assert(chunk != NULL);
304	assert(CHUNK_ADDR2BASE(chunk) == chunk);
305	assert(size != 0);
306	assert((size & chunksize_mask) == 0);
307
308	if (config_dss && chunk_in_dss(chunk))
309		chunk_record(&chunks_szad_dss, &chunks_ad_dss, chunk, size);
310	else if (chunk_dealloc_mmap(chunk, size))
311		chunk_record(&chunks_szad_mmap, &chunks_ad_mmap, chunk, size);
312}
313
314void
315chunk_dealloc(void *chunk, size_t size, bool unmap)
316{
317
318	assert(chunk != NULL);
319	assert(CHUNK_ADDR2BASE(chunk) == chunk);
320	assert(size != 0);
321	assert((size & chunksize_mask) == 0);
322
323	if (config_ivsalloc)
324		rtree_set(chunks_rtree, (uintptr_t)chunk, NULL);
325	if (config_stats || config_prof) {
326		malloc_mutex_lock(&chunks_mtx);
327		assert(stats_chunks.curchunks >= (size / chunksize));
328		stats_chunks.curchunks -= (size / chunksize);
329		malloc_mutex_unlock(&chunks_mtx);
330	}
331
332	if (unmap)
333		chunk_unmap(chunk, size);
334}
335
336bool
337chunk_boot(void)
338{
339
340	/* Set variables according to the value of opt_lg_chunk. */
341	chunksize = (ZU(1) << opt_lg_chunk);
342	assert(chunksize >= PAGE);
343	chunksize_mask = chunksize - 1;
344	chunk_npages = (chunksize >> LG_PAGE);
345
346	if (config_stats || config_prof) {
347		if (malloc_mutex_init(&chunks_mtx))
348			return (true);
349		memset(&stats_chunks, 0, sizeof(chunk_stats_t));
350	}
351	if (config_dss && chunk_dss_boot())
352		return (true);
353	extent_tree_szad_new(&chunks_szad_mmap);
354	extent_tree_ad_new(&chunks_ad_mmap);
355	extent_tree_szad_new(&chunks_szad_dss);
356	extent_tree_ad_new(&chunks_ad_dss);
357	if (config_ivsalloc) {
358		chunks_rtree = rtree_new((ZU(1) << (LG_SIZEOF_PTR+3)) -
359		    opt_lg_chunk);
360		if (chunks_rtree == NULL)
361			return (true);
362	}
363
364	return (false);
365}
366
367void
368chunk_prefork(void)
369{
370
371	malloc_mutex_lock(&chunks_mtx);
372	if (config_ivsalloc)
373		rtree_prefork(chunks_rtree);
374	chunk_dss_prefork();
375}
376
377void
378chunk_postfork_parent(void)
379{
380
381	chunk_dss_postfork_parent();
382	if (config_ivsalloc)
383		rtree_postfork_parent(chunks_rtree);
384	malloc_mutex_postfork_parent(&chunks_mtx);
385}
386
387void
388chunk_postfork_child(void)
389{
390
391	chunk_dss_postfork_child();
392	if (config_ivsalloc)
393		rtree_postfork_child(chunks_rtree);
394	malloc_mutex_postfork_child(&chunks_mtx);
395}
396