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
11 void
bitmap_info_init(bitmap_info_t * binfo,size_t nbits)12 bitmap_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
39 static size_t
bitmap_info_ngroups(const bitmap_info_t * binfo)40 bitmap_info_ngroups(const bitmap_info_t *binfo) {
41 return binfo->levels[binfo->nlevels].group_offset;
42 }
43
44 void
bitmap_init(bitmap_t * bitmap,const bitmap_info_t * binfo,bool fill)45 bitmap_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
85 void
bitmap_info_init(bitmap_info_t * binfo,size_t nbits)86 bitmap_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
94 static size_t
bitmap_info_ngroups(const bitmap_info_t * binfo)95 bitmap_info_ngroups(const bitmap_info_t *binfo) {
96 return binfo->ngroups;
97 }
98
99 void
bitmap_init(bitmap_t * bitmap,const bitmap_info_t * binfo,bool fill)100 bitmap_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
118 size_t
bitmap_size(const bitmap_info_t * binfo)119 bitmap_size(const bitmap_info_t *binfo) {
120 return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP);
121 }
122