xref: /freebsd/contrib/jemalloc/src/rtree.c (revision 82872ac08650a49b356e99f9bf640b8d7201849f)
1a4bd5210SJason Evans #define	JEMALLOC_RTREE_C_
2a4bd5210SJason Evans #include "jemalloc/internal/jemalloc_internal.h"
3a4bd5210SJason Evans 
4a4bd5210SJason Evans rtree_t *
5a4bd5210SJason Evans rtree_new(unsigned bits)
6a4bd5210SJason Evans {
7a4bd5210SJason Evans 	rtree_t *ret;
8a4bd5210SJason Evans 	unsigned bits_per_level, height, i;
9a4bd5210SJason Evans 
10a4bd5210SJason Evans 	bits_per_level = ffs(pow2_ceil((RTREE_NODESIZE / sizeof(void *)))) - 1;
11a4bd5210SJason Evans 	height = bits / bits_per_level;
12a4bd5210SJason Evans 	if (height * bits_per_level != bits)
13a4bd5210SJason Evans 		height++;
14a4bd5210SJason Evans 	assert(height * bits_per_level >= bits);
15a4bd5210SJason Evans 
16a4bd5210SJason Evans 	ret = (rtree_t*)base_alloc(offsetof(rtree_t, level2bits) +
17a4bd5210SJason Evans 	    (sizeof(unsigned) * height));
18a4bd5210SJason Evans 	if (ret == NULL)
19a4bd5210SJason Evans 		return (NULL);
20a4bd5210SJason Evans 	memset(ret, 0, offsetof(rtree_t, level2bits) + (sizeof(unsigned) *
21a4bd5210SJason Evans 	    height));
22a4bd5210SJason Evans 
23a4bd5210SJason Evans 	if (malloc_mutex_init(&ret->mutex)) {
24a4bd5210SJason Evans 		/* Leak the rtree. */
25a4bd5210SJason Evans 		return (NULL);
26a4bd5210SJason Evans 	}
27a4bd5210SJason Evans 	ret->height = height;
28a4bd5210SJason Evans 	if (bits_per_level * height > bits)
29a4bd5210SJason Evans 		ret->level2bits[0] = bits % bits_per_level;
30a4bd5210SJason Evans 	else
31a4bd5210SJason Evans 		ret->level2bits[0] = bits_per_level;
32a4bd5210SJason Evans 	for (i = 1; i < height; i++)
33a4bd5210SJason Evans 		ret->level2bits[i] = bits_per_level;
34a4bd5210SJason Evans 
35a4bd5210SJason Evans 	ret->root = (void**)base_alloc(sizeof(void *) << ret->level2bits[0]);
36a4bd5210SJason Evans 	if (ret->root == NULL) {
37a4bd5210SJason Evans 		/*
38a4bd5210SJason Evans 		 * We leak the rtree here, since there's no generic base
39a4bd5210SJason Evans 		 * deallocation.
40a4bd5210SJason Evans 		 */
41a4bd5210SJason Evans 		return (NULL);
42a4bd5210SJason Evans 	}
43a4bd5210SJason Evans 	memset(ret->root, 0, sizeof(void *) << ret->level2bits[0]);
44a4bd5210SJason Evans 
45a4bd5210SJason Evans 	return (ret);
46a4bd5210SJason Evans }
47*82872ac0SJason Evans 
48*82872ac0SJason Evans void
49*82872ac0SJason Evans rtree_prefork(rtree_t *rtree)
50*82872ac0SJason Evans {
51*82872ac0SJason Evans 
52*82872ac0SJason Evans 	malloc_mutex_prefork(&rtree->mutex);
53*82872ac0SJason Evans }
54*82872ac0SJason Evans 
55*82872ac0SJason Evans void
56*82872ac0SJason Evans rtree_postfork_parent(rtree_t *rtree)
57*82872ac0SJason Evans {
58*82872ac0SJason Evans 
59*82872ac0SJason Evans 	malloc_mutex_postfork_parent(&rtree->mutex);
60*82872ac0SJason Evans }
61*82872ac0SJason Evans 
62*82872ac0SJason Evans void
63*82872ac0SJason Evans rtree_postfork_child(rtree_t *rtree)
64*82872ac0SJason Evans {
65*82872ac0SJason Evans 
66*82872ac0SJason Evans 	malloc_mutex_postfork_child(&rtree->mutex);
67*82872ac0SJason Evans }
68