Jason Evans | c0cc5db | 2017-01-19 21:41:41 -0800 | [diff] [blame^] | 1 | #define JEMALLOC_BITMAP_C_ |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 2 | #include "jemalloc/internal/jemalloc_internal.h" |
| 3 | |
| 4 | /******************************************************************************/ |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 5 | |
Jason Evans | b683734 | 2016-04-06 18:30:02 -0700 | [diff] [blame] | 6 | #ifdef BITMAP_USE_TREE |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 7 | |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 8 | void |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 9 | bitmap_info_init(bitmap_info_t *binfo, size_t nbits) { |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 10 | unsigned i; |
| 11 | size_t group_count; |
| 12 | |
| 13 | assert(nbits > 0); |
| 14 | assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); |
| 15 | |
| 16 | /* |
| 17 | * Compute the number of groups necessary to store nbits bits, and |
| 18 | * progressively work upward through the levels until reaching a level |
| 19 | * that requires only one group. |
| 20 | */ |
| 21 | binfo->levels[0].group_offset = 0; |
Jason Evans | f97e5ac | 2014-09-28 14:43:11 -0700 | [diff] [blame] | 22 | group_count = BITMAP_BITS2GROUPS(nbits); |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 23 | for (i = 1; group_count > 1; i++) { |
| 24 | assert(i < BITMAP_MAX_LEVELS); |
| 25 | binfo->levels[i].group_offset = binfo->levels[i-1].group_offset |
| 26 | + group_count; |
Jason Evans | f97e5ac | 2014-09-28 14:43:11 -0700 | [diff] [blame] | 27 | group_count = BITMAP_BITS2GROUPS(group_count); |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 28 | } |
| 29 | binfo->levels[i].group_offset = binfo->levels[i-1].group_offset |
| 30 | + group_count; |
Jason Evans | f97e5ac | 2014-09-28 14:43:11 -0700 | [diff] [blame] | 31 | assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX); |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 32 | binfo->nlevels = i; |
| 33 | binfo->nbits = nbits; |
| 34 | } |
| 35 | |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 36 | static size_t |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 37 | bitmap_info_ngroups(const bitmap_info_t *binfo) { |
Jason Evans | f408643 | 2017-01-19 18:15:45 -0800 | [diff] [blame] | 38 | return binfo->levels[binfo->nlevels].group_offset; |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 39 | } |
| 40 | |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 41 | void |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 42 | bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo) { |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 43 | size_t extra; |
| 44 | unsigned i; |
| 45 | |
| 46 | /* |
| 47 | * Bits are actually inverted with regard to the external bitmap |
| 48 | * interface, so the bitmap starts out with all 1 bits, except for |
| 49 | * trailing unused bits (if any). Note that each group uses bit 0 to |
| 50 | * correspond to the first logical bit in the group, so extra bits |
| 51 | * are the most significant bits of the last group. |
| 52 | */ |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 53 | memset(bitmap, 0xffU, bitmap_size(binfo)); |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 54 | extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) |
| 55 | & BITMAP_GROUP_NBITS_MASK; |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 56 | if (extra != 0) { |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 57 | bitmap[binfo->levels[1].group_offset - 1] >>= extra; |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 58 | } |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 59 | for (i = 1; i < binfo->nlevels; i++) { |
| 60 | size_t group_count = binfo->levels[i].group_offset - |
| 61 | binfo->levels[i-1].group_offset; |
| 62 | extra = (BITMAP_GROUP_NBITS - (group_count & |
| 63 | BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK; |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 64 | if (extra != 0) { |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 65 | bitmap[binfo->levels[i+1].group_offset - 1] >>= extra; |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 66 | } |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 67 | } |
| 68 | } |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 69 | |
Jason Evans | b683734 | 2016-04-06 18:30:02 -0700 | [diff] [blame] | 70 | #else /* BITMAP_USE_TREE */ |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 71 | |
| 72 | void |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 73 | bitmap_info_init(bitmap_info_t *binfo, size_t nbits) { |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 74 | assert(nbits > 0); |
| 75 | assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); |
| 76 | |
Jason Evans | 2ee2f1e | 2016-04-06 10:38:47 -0700 | [diff] [blame] | 77 | binfo->ngroups = BITMAP_BITS2GROUPS(nbits); |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 78 | binfo->nbits = nbits; |
| 79 | } |
| 80 | |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 81 | static size_t |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 82 | bitmap_info_ngroups(const bitmap_info_t *binfo) { |
Jason Evans | f408643 | 2017-01-19 18:15:45 -0800 | [diff] [blame] | 83 | return binfo->ngroups; |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 84 | } |
| 85 | |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 86 | void |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 87 | bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo) { |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 88 | size_t extra; |
| 89 | |
| 90 | memset(bitmap, 0xffU, bitmap_size(binfo)); |
Jason Evans | 2ee2f1e | 2016-04-06 10:38:47 -0700 | [diff] [blame] | 91 | extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) |
| 92 | & BITMAP_GROUP_NBITS_MASK; |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 93 | if (extra != 0) { |
Jason Evans | 2ee2f1e | 2016-04-06 10:38:47 -0700 | [diff] [blame] | 94 | bitmap[binfo->ngroups - 1] >>= extra; |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 95 | } |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 96 | } |
| 97 | |
Jason Evans | b683734 | 2016-04-06 18:30:02 -0700 | [diff] [blame] | 98 | #endif /* BITMAP_USE_TREE */ |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 99 | |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 100 | size_t |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 101 | bitmap_size(const bitmap_info_t *binfo) { |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 102 | return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP); |
| 103 | } |