1#define JEMALLOC_BITMAP_C_
2#include "jemalloc/internal/jemalloc_preamble.h"
3#include "jemalloc/internal/jemalloc_internal_includes.h"
4
5#include "jemalloc/internal/assert.h"
6
7/******************************************************************************/
8
9#ifdef BITMAP_USE_TREE
10
11void
12bitmap_info_init(bitmap_info_t *binfo, size_t nbits) {
13	unsigned i;
14	size_t group_count;
15
16	assert(nbits > 0);
17	assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
18
19	/*
20	 * Compute the number of groups necessary to store nbits bits, and
21	 * progressively work upward through the levels until reaching a level
22	 * that requires only one group.
23	 */
24	binfo->levels[0].group_offset = 0;
25	group_count = BITMAP_BITS2GROUPS(nbits);
26	for (i = 1; group_count > 1; i++) {
27		assert(i < BITMAP_MAX_LEVELS);
28		binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
29		    + group_count;
30		group_count = BITMAP_BITS2GROUPS(group_count);
31	}
32	binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
33	    + group_count;
34	assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX);
35	binfo->nlevels = i;
36	binfo->nbits = nbits;
37}
38
39static size_t
40bitmap_info_ngroups(const bitmap_info_t *binfo) {
41	return binfo->levels[binfo->nlevels].group_offset;
42}
43
44void
45bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo, bool fill) {
46	size_t extra;
47	unsigned i;
48
49	/*
50	 * Bits are actually inverted with regard to the external bitmap
51	 * interface.
52	 */
53
54	if (fill) {
55		/* The "filled" bitmap starts out with all 0 bits. */
56		memset(bitmap, 0, bitmap_size(binfo));
57		return;
58	}
59
60	/*
61	 * The "empty" bitmap starts out with all 1 bits, except for trailing
62	 * unused bits (if any).  Note that each group uses bit 0 to correspond
63	 * to the first logical bit in the group, so extra bits are the most
64	 * significant bits of the last group.
65	 */
66	memset(bitmap, 0xffU, bitmap_size(binfo));
67	extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
68	    & BITMAP_GROUP_NBITS_MASK;
69	if (extra != 0) {
70		bitmap[binfo->levels[1].group_offset - 1] >>= extra;
71	}
72	for (i = 1; i < binfo->nlevels; i++) {
73		size_t group_count = binfo->levels[i].group_offset -
74		    binfo->levels[i-1].group_offset;
75		extra = (BITMAP_GROUP_NBITS - (group_count &
76		    BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK;
77		if (extra != 0) {
78			bitmap[binfo->levels[i+1].group_offset - 1] >>= extra;
79		}
80	}
81}
82
83#else /* BITMAP_USE_TREE */
84
85void
86bitmap_info_init(bitmap_info_t *binfo, size_t nbits) {
87	assert(nbits > 0);
88	assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
89
90	binfo->ngroups = BITMAP_BITS2GROUPS(nbits);
91	binfo->nbits = nbits;
92}
93
94static size_t
95bitmap_info_ngroups(const bitmap_info_t *binfo) {
96	return binfo->ngroups;
97}
98
99void
100bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo, bool fill) {
101	size_t extra;
102
103	if (fill) {
104		memset(bitmap, 0, bitmap_size(binfo));
105		return;
106	}
107
108	memset(bitmap, 0xffU, bitmap_size(binfo));
109	extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
110	    & BITMAP_GROUP_NBITS_MASK;
111	if (extra != 0) {
112		bitmap[binfo->ngroups - 1] >>= extra;
113	}
114}
115
116#endif /* BITMAP_USE_TREE */
117
118size_t
119bitmap_size(const bitmap_info_t *binfo) {
120	return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP);
121}
122