1 #define JEMALLOC_BITMAP_C_
2 #include "jemalloc/internal/jemalloc_internal.h"
3
4 /******************************************************************************/
5
6 void
bitmap_info_init(bitmap_info_t * binfo,size_t nbits)7 bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
8 {
9 unsigned i;
10 size_t group_count;
11
12 assert(nbits > 0);
13 assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
14
15 /*
16 * Compute the number of groups necessary to store nbits bits, and
17 * progressively work upward through the levels until reaching a level
18 * that requires only one group.
19 */
20 binfo->levels[0].group_offset = 0;
21 group_count = BITMAP_BITS2GROUPS(nbits);
22 for (i = 1; group_count > 1; i++) {
23 assert(i < BITMAP_MAX_LEVELS);
24 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
25 + group_count;
26 group_count = BITMAP_BITS2GROUPS(group_count);
27 }
28 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
29 + group_count;
30 assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX);
31 binfo->nlevels = i;
32 binfo->nbits = nbits;
33 }
34
35 size_t
bitmap_info_ngroups(const bitmap_info_t * binfo)36 bitmap_info_ngroups(const bitmap_info_t *binfo)
37 {
38
39 return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP);
40 }
41
42 size_t
bitmap_size(size_t nbits)43 bitmap_size(size_t nbits)
44 {
45 bitmap_info_t binfo;
46
47 bitmap_info_init(&binfo, nbits);
48 return (bitmap_info_ngroups(&binfo));
49 }
50
51 void
bitmap_init(bitmap_t * bitmap,const bitmap_info_t * binfo)52 bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
53 {
54 size_t extra;
55 unsigned i;
56
57 /*
58 * Bits are actually inverted with regard to the external bitmap
59 * interface, so the bitmap starts out with all 1 bits, except for
60 * trailing unused bits (if any). Note that each group uses bit 0 to
61 * correspond to the first logical bit in the group, so extra bits
62 * are the most significant bits of the last group.
63 */
64 memset(bitmap, 0xffU, binfo->levels[binfo->nlevels].group_offset <<
65 LG_SIZEOF_BITMAP);
66 extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
67 & BITMAP_GROUP_NBITS_MASK;
68 if (extra != 0)
69 bitmap[binfo->levels[1].group_offset - 1] >>= extra;
70 for (i = 1; i < binfo->nlevels; i++) {
71 size_t group_count = binfo->levels[i].group_offset -
72 binfo->levels[i-1].group_offset;
73 extra = (BITMAP_GROUP_NBITS - (group_count &
74 BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK;
75 if (extra != 0)
76 bitmap[binfo->levels[i+1].group_offset - 1] >>= extra;
77 }
78 }
79