1 #ifndef JEMALLOC_INTERNAL_BITMAP_INLINES_H
2 #define JEMALLOC_INTERNAL_BITMAP_INLINES_H
3
4 #ifndef JEMALLOC_ENABLE_INLINE
5 bool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo);
6 bool bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
7 void bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
8 size_t bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo);
9 void bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
10 #endif
11
12 #if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_BITMAP_C_))
13 JEMALLOC_INLINE bool
bitmap_full(bitmap_t * bitmap,const bitmap_info_t * binfo)14 bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo)
15 {
16 #ifdef BITMAP_USE_TREE
17 size_t rgoff = binfo->levels[binfo->nlevels].group_offset - 1;
18 bitmap_t rg = bitmap[rgoff];
19 /* The bitmap is full iff the root group is 0. */
20 return (rg == 0);
21 #else
22 size_t i;
23
24 for (i = 0; i < binfo->ngroups; i++) {
25 if (bitmap[i] != 0)
26 return (false);
27 }
28 return (true);
29 #endif
30 }
31
32 JEMALLOC_INLINE bool
bitmap_get(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)33 bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
34 {
35 size_t goff;
36 bitmap_t g;
37
38 assert(bit < binfo->nbits);
39 goff = bit >> LG_BITMAP_GROUP_NBITS;
40 g = bitmap[goff];
41 return (!(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))));
42 }
43
44 JEMALLOC_INLINE void
bitmap_set(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)45 bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
46 {
47 size_t goff;
48 bitmap_t *gp;
49 bitmap_t g;
50
51 assert(bit < binfo->nbits);
52 assert(!bitmap_get(bitmap, binfo, bit));
53 goff = bit >> LG_BITMAP_GROUP_NBITS;
54 gp = &bitmap[goff];
55 g = *gp;
56 assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)));
57 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
58 *gp = g;
59 assert(bitmap_get(bitmap, binfo, bit));
60 #ifdef BITMAP_USE_TREE
61 /* Propagate group state transitions up the tree. */
62 if (g == 0) {
63 unsigned i;
64 for (i = 1; i < binfo->nlevels; i++) {
65 bit = goff;
66 goff = bit >> LG_BITMAP_GROUP_NBITS;
67 gp = &bitmap[binfo->levels[i].group_offset + goff];
68 g = *gp;
69 assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)));
70 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
71 *gp = g;
72 if (g != 0)
73 break;
74 }
75 }
76 #endif
77 }
78
79 /* sfu: set first unset. */
80 JEMALLOC_INLINE size_t
bitmap_sfu(bitmap_t * bitmap,const bitmap_info_t * binfo)81 bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
82 {
83 size_t bit;
84 bitmap_t g;
85 unsigned i;
86
87 assert(!bitmap_full(bitmap, binfo));
88
89 #ifdef BITMAP_USE_TREE
90 i = binfo->nlevels - 1;
91 g = bitmap[binfo->levels[i].group_offset];
92 bit = ffs_lu(g) - 1;
93 while (i > 0) {
94 i--;
95 g = bitmap[binfo->levels[i].group_offset + bit];
96 bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffs_lu(g) - 1);
97 }
98 #else
99 i = 0;
100 g = bitmap[0];
101 while ((bit = ffs_lu(g)) == 0) {
102 i++;
103 g = bitmap[i];
104 }
105 bit = (i << LG_BITMAP_GROUP_NBITS) + (bit - 1);
106 #endif
107 bitmap_set(bitmap, binfo, bit);
108 return (bit);
109 }
110
111 JEMALLOC_INLINE void
bitmap_unset(bitmap_t * bitmap,const bitmap_info_t * binfo,size_t bit)112 bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
113 {
114 size_t goff;
115 bitmap_t *gp;
116 bitmap_t g;
117 UNUSED bool propagate;
118
119 assert(bit < binfo->nbits);
120 assert(bitmap_get(bitmap, binfo, bit));
121 goff = bit >> LG_BITMAP_GROUP_NBITS;
122 gp = &bitmap[goff];
123 g = *gp;
124 propagate = (g == 0);
125 assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) == 0);
126 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
127 *gp = g;
128 assert(!bitmap_get(bitmap, binfo, bit));
129 #ifdef BITMAP_USE_TREE
130 /* Propagate group state transitions up the tree. */
131 if (propagate) {
132 unsigned i;
133 for (i = 1; i < binfo->nlevels; i++) {
134 bit = goff;
135 goff = bit >> LG_BITMAP_GROUP_NBITS;
136 gp = &bitmap[binfo->levels[i].group_offset + goff];
137 g = *gp;
138 propagate = (g == 0);
139 assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)))
140 == 0);
141 g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
142 *gp = g;
143 if (!propagate)
144 break;
145 }
146 }
147 #endif /* BITMAP_USE_TREE */
148 }
149
150 #endif
151
152 #endif /* JEMALLOC_INTERNAL_BITMAP_INLINES_H */
153