git.saurik.com Git - redis.git/blob - deps/jemalloc/src/chunk.c

1 #define JEMALLOC_CHUNK_C_

2 #include "jemalloc/internal/jemalloc_internal.h"

4 /******************************************************************************/

5 /* Data. */

7 const char *opt_dss = DSS_DEFAULT;

8 size_t opt_lg_chunk = LG_CHUNK_DEFAULT;

10 malloc_mutex_t chunks_mtx;

11 chunk_stats_t stats_chunks;

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 */

19 static extent_tree_t chunks_szad_mmap;

20 static extent_tree_t chunks_ad_mmap;

21 static extent_tree_t chunks_szad_dss;

22 static extent_tree_t chunks_ad_dss;

24 rtree_t *chunks_rtree;

26 /* Various chunk-related settings. */

27 size_t chunksize;

28 size_t chunksize_mask; /* (chunksize - 1). */

29 size_t chunk_npages;

30 size_t map_bias;

31 size_t arena_maxclass; /* Max size class for arenas. */

33 /******************************************************************************/

34 /* Function prototypes for non-inline static functions. */

 static void     *chunk_recycle(extent_tree_t *chunks_szad,

     extent_tree_t *chunks_ad, size_t size, size_t alignment, bool base,

38 bool *zero);

 static void     chunk_record(extent_tree_t *chunks_szad,

     extent_tree_t *chunks_ad, void *chunk, size_t size);

42 /******************************************************************************/

44 static void *

 chunk_recycle(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, size_t size,

     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;

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 }

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);

         node = extent_tree_szad_nsearch(chunks_szad, &key);

72 if (node == NULL) {

73 malloc_mutex_unlock(&chunks_mtx);

74 return (NULL);

75 }

         leadsize = ALIGNMENT_CEILING((uintptr_t)node->addr, alignment) -

             (uintptr_t)node->addr;

         assert(node->size >= leadsize + size);

         trailsize = node->size - leadsize - size;

         ret = (void *)((uintptr_t)node->addr + leadsize);

81 /* Remove node from the tree. */

82 extent_tree_szad_remove(chunks_szad, node);

83 extent_tree_ad_remove(chunks_ad, node);

         if (leadsize != 0) {

85 /* Insert the leading space as a smaller chunk. */

86 node->size = leadsize;

87 extent_tree_szad_insert(chunks_szad, node);

88 extent_tree_ad_insert(chunks_ad, node);

89 node = NULL;

90 }

         if (trailsize != 0) {

92 /* Insert the trailing space as a smaller chunk. */

93 if (node == NULL) {

94 /*

95 * An additional node is required, but

96 * base_node_alloc() can cause a new base chunk to be

97 * allocated. Drop chunks_mtx in order to avoid

98 * deadlock, and if node allocation fails, deallocate

99 * the result before returning an error.

100 */

101 malloc_mutex_unlock(&chunks_mtx);

102 node = base_node_alloc();

103 if (node == NULL) {

                                 chunk_dealloc(ret, size, true);

105 return (NULL);

106 }

107 malloc_mutex_lock(&chunks_mtx);

108 }

                 node->addr = (void *)((uintptr_t)(ret) + size);

110 node->size = trailsize;

111 extent_tree_szad_insert(chunks_szad, node);

112 extent_tree_ad_insert(chunks_ad, node);

113 node = NULL;

114 }

115 malloc_mutex_unlock(&chunks_mtx);

116

117 zeroed = false;

118 if (node != NULL) {

119 if (node->zeroed) {

120 zeroed = true;

121 *zero = true;

122 }

123 base_node_dealloc(node);

124 }

         if (zeroed == false && *zero) {

126 VALGRIND_MAKE_MEM_UNDEFINED(ret, size);

                 memset(ret, 0, size);

128 }

129 return (ret);

130 }

131

132 /*

133 * If the caller specifies (*zero == false), it is still possible to receive

134 * zeroed memory, in which case *zero is toggled to true. arena_chunk_alloc()

135 * takes advantage of this to avoid demanding zeroed chunks, but taking

136 * advantage of them if they are returned.

137 */

138 void *

 chunk_alloc(size_t size, size_t alignment, bool base, bool *zero,

140 dss_prec_t dss_prec)

141 {

142 void *ret;

143

         assert(size != 0);

         assert((size & chunksize_mask) == 0);

         assert(alignment != 0);

         assert((alignment & chunksize_mask) == 0);

148

149 /* "primary" dss. */

         if (config_dss && dss_prec == dss_prec_primary) {

                 if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size,

152 alignment, base, zero)) != NULL)

153 goto label_return;

                 if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL)

155 goto label_return;

156 }

157 /* mmap. */

         if ((ret = chunk_recycle(&chunks_szad_mmap, &chunks_ad_mmap, size,

159 alignment, base, zero)) != NULL)

160 goto label_return;

         if ((ret = chunk_alloc_mmap(size, alignment, zero)) != NULL)

162 goto label_return;

163 /* "secondary" dss. */

         if (config_dss && dss_prec == dss_prec_secondary) {

                 if ((ret = chunk_recycle(&chunks_szad_dss, &chunks_ad_dss, size,

166 alignment, base, zero)) != NULL)

167 goto label_return;

                 if ((ret = chunk_alloc_dss(size, alignment, zero)) != NULL)

169 goto label_return;

170 }

171

172 /* All strategies for allocation failed. */

173 ret = NULL;

174 label_return:

         if (config_ivsalloc && base == false && ret != NULL) {

                 if (rtree_set(chunks_rtree, (uintptr_t)ret, ret)) {

                         chunk_dealloc(ret, size, true);

178 return (NULL);

179 }

180 }

         if ((config_stats || config_prof) && ret != NULL) {

182 bool gdump;

183 malloc_mutex_lock(&chunks_mtx);

184 if (config_stats)

185 stats_chunks.nchunks += (size / chunksize);

186 stats_chunks.curchunks += (size / chunksize);

                 if (stats_chunks.curchunks > stats_chunks.highchunks) {

188 stats_chunks.highchunks = stats_chunks.curchunks;

189 if (config_prof)

190 gdump = true;

191 } else if (config_prof)

192 gdump = false;

193 malloc_mutex_unlock(&chunks_mtx);

                 if (config_prof && opt_prof && opt_prof_gdump && gdump)

195 prof_gdump();

196 }

         if (config_debug && *zero && ret != NULL) {

198 size_t i;

                 size_t *p = (size_t *)(uintptr_t)ret;

200

201 VALGRIND_MAKE_MEM_DEFINED(ret, size);

                 for (i = 0; i < size / sizeof(size_t); i++)

                         assert(p[i] == 0);

204 }

         assert(CHUNK_ADDR2BASE(ret) == ret);

206 return (ret);

207 }

208

209 static void

 chunk_record(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, void *chunk,

211 size_t size)

212 {

213 bool unzeroed;

         extent_node_t *xnode, *node, *prev, key;

215

         unzeroed = pages_purge(chunk, size);

217

218 /*

219 * Allocate a node before acquiring chunks_mtx even though it might not

220 * be needed, because base_node_alloc() may cause a new base chunk to

221 * be allocated, which could cause deadlock if chunks_mtx were already

222 * held.

223 */

224 xnode = base_node_alloc();

225

226 malloc_mutex_lock(&chunks_mtx);

         key.addr = (void *)((uintptr_t)chunk + size);

         node = extent_tree_ad_nsearch(chunks_ad, &key);

229 /* Try to coalesce forward. */

         if (node != NULL && node->addr == key.addr) {

231 /*

232 * Coalesce chunk with the following address range. This does

233 * not change the position within chunks_ad, so only

234 * remove/insert from/into chunks_szad.

235 */

236 extent_tree_szad_remove(chunks_szad, node);

237 node->addr = chunk;

238 node->size += size;

                 node->zeroed = (node->zeroed && (unzeroed == false));

240 extent_tree_szad_insert(chunks_szad, node);

241 if (xnode != NULL)

242 base_node_dealloc(xnode);

243 } else {

244 /* Coalescing forward failed, so insert a new node. */

245 if (xnode == NULL) {

246 /*

247 * base_node_alloc() failed, which is an exceedingly

248 * unlikely failure. Leak chunk; its pages have

249 * already been purged, so this is only a virtual

250 * memory leak.

251 */

252 malloc_mutex_unlock(&chunks_mtx);

253 return;

254 }

255 node = xnode;

256 node->addr = chunk;

257 node->size = size;

                 node->zeroed = (unzeroed == false);

259 extent_tree_ad_insert(chunks_ad, node);

260 extent_tree_szad_insert(chunks_szad, node);

261 }

262

263 /* Try to coalesce backward. */

         prev = extent_tree_ad_prev(chunks_ad, node);

         if (prev != NULL && (void *)((uintptr_t)prev->addr + prev->size) ==

266 chunk) {

267 /*

268 * Coalesce chunk with the previous address range. This does

269 * not change the position within chunks_ad, so only

270 * remove/insert node from/into chunks_szad.

271 */

272 extent_tree_szad_remove(chunks_szad, prev);

273 extent_tree_ad_remove(chunks_ad, prev);

274

275 extent_tree_szad_remove(chunks_szad, node);

276 node->addr = prev->addr;

277 node->size += prev->size;

                 node->zeroed = (node->zeroed && prev->zeroed);

279 extent_tree_szad_insert(chunks_szad, node);

280

281 base_node_dealloc(prev);

282 }

283 malloc_mutex_unlock(&chunks_mtx);

284 }

285

286 void

 chunk_unmap(void *chunk, size_t size)

288 {

289 assert(chunk != NULL);

         assert(CHUNK_ADDR2BASE(chunk) == chunk);

         assert(size != 0);

         assert((size & chunksize_mask) == 0);

293

         if (config_dss && chunk_in_dss(chunk))

                 chunk_record(&chunks_szad_dss, &chunks_ad_dss, chunk, size);

         else if (chunk_dealloc_mmap(chunk, size))

                 chunk_record(&chunks_szad_mmap, &chunks_ad_mmap, chunk, size);

298 }

299

300 void

 chunk_dealloc(void *chunk, size_t size, bool unmap)

302 {

303

304 assert(chunk != NULL);

         assert(CHUNK_ADDR2BASE(chunk) == chunk);

         assert(size != 0);

         assert((size & chunksize_mask) == 0);

308

309 if (config_ivsalloc)

                 rtree_set(chunks_rtree, (uintptr_t)chunk, NULL);

311 if (config_stats || config_prof) {

312 malloc_mutex_lock(&chunks_mtx);

                 assert(stats_chunks.curchunks >= (size / chunksize));

314 stats_chunks.curchunks -= (size / chunksize);

315 malloc_mutex_unlock(&chunks_mtx);

316 }

317

318 if (unmap)

319 chunk_unmap(chunk, size);

320 }

321

322 bool

323 chunk_boot(void)

324 {

325

326 /* Set variables according to the value of opt_lg_chunk. */

         chunksize = (ZU(1) << opt_lg_chunk);

328 assert(chunksize >= PAGE);

329 chunksize_mask = chunksize - 1;

330 chunk_npages = (chunksize >> LG_PAGE);

331

332 if (config_stats || config_prof) {

                 if (malloc_mutex_init(&chunks_mtx))

334 return (true);

                 memset(&stats_chunks, 0, sizeof(chunk_stats_t));

336 }

         if (config_dss && chunk_dss_boot())

338 return (true);

339 extent_tree_szad_new(&chunks_szad_mmap);

340 extent_tree_ad_new(&chunks_ad_mmap);

341 extent_tree_szad_new(&chunks_szad_dss);

342 extent_tree_ad_new(&chunks_ad_dss);

343 if (config_ivsalloc) {

                 chunks_rtree = rtree_new((ZU(1) << (LG_SIZEOF_PTR+3)) -

345 opt_lg_chunk);

346 if (chunks_rtree == NULL)

347 return (true);

348 }

349

350 return (false);

351 }

352

353 void

354 chunk_prefork(void)

355 {

356

357 malloc_mutex_lock(&chunks_mtx);

358 if (config_ivsalloc)

359 rtree_prefork(chunks_rtree);

360 chunk_dss_prefork();

361 }

362

363 void

364 chunk_postfork_parent(void)

365 {

366

367 chunk_dss_postfork_parent();

368 if (config_ivsalloc)

369 rtree_postfork_parent(chunks_rtree);

370 malloc_mutex_postfork_parent(&chunks_mtx);

371 }

372

373 void

374 chunk_postfork_child(void)

375 {

376

377 chunk_dss_postfork_child();

378 if (config_ivsalloc)

379 rtree_postfork_child(chunks_rtree);

380 malloc_mutex_postfork_child(&chunks_mtx);

381 }