Jason Evans | c0cc5db | 2017-01-19 21:41:41 -0800 | [diff] [blame] | 1 | #define JEMALLOC_BITMAP_C_ |
David Goldblatt | 743d940 | 2017-04-10 18:17:55 -0700 | [diff] [blame] | 2 | #include "jemalloc/internal/jemalloc_preamble.h" |
| 3 | #include "jemalloc/internal/jemalloc_internal_includes.h" |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 4 | |
David Goldblatt | d9ec36e | 2017-04-11 14:43:12 -0700 | [diff] [blame] | 5 | #include "jemalloc/internal/assert.h" |
| 6 | |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 7 | /******************************************************************************/ |
Jason Evans | 84c8eef | 2011-03-16 10:30:13 -0700 | [diff] [blame] | 8 | |
Jason Evans | 45f087e | 2017-04-16 09:25:56 -0700 | [diff] [blame] | 9 | #ifdef BITMAP_USE_TREE |
| 10 | |
| 11 | void |
| 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 |
| 40 | bitmap_info_ngroups(const bitmap_info_t *binfo) { |
| 41 | return binfo->levels[binfo->nlevels].group_offset; |
| 42 | } |
| 43 | |
| 44 | void |
| 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 | |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 85 | void |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 86 | bitmap_info_init(bitmap_info_t *binfo, size_t nbits) { |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 87 | assert(nbits > 0); |
| 88 | assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); |
| 89 | |
Jason Evans | 2ee2f1e | 2016-04-06 10:38:47 -0700 | [diff] [blame] | 90 | binfo->ngroups = BITMAP_BITS2GROUPS(nbits); |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 91 | binfo->nbits = nbits; |
| 92 | } |
| 93 | |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 94 | static size_t |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 95 | bitmap_info_ngroups(const bitmap_info_t *binfo) { |
Jason Evans | f408643 | 2017-01-19 18:15:45 -0800 | [diff] [blame] | 96 | return binfo->ngroups; |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 97 | } |
| 98 | |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 99 | void |
Jason Evans | c8021d0 | 2017-03-23 17:59:47 -0700 | [diff] [blame] | 100 | bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo, bool fill) { |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 101 | size_t extra; |
| 102 | |
Jason Evans | c8021d0 | 2017-03-23 17:59:47 -0700 | [diff] [blame] | 103 | if (fill) { |
| 104 | memset(bitmap, 0, bitmap_size(binfo)); |
| 105 | return; |
| 106 | } |
| 107 | |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 108 | memset(bitmap, 0xffU, bitmap_size(binfo)); |
Jason Evans | 2ee2f1e | 2016-04-06 10:38:47 -0700 | [diff] [blame] | 109 | extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) |
| 110 | & BITMAP_GROUP_NBITS_MASK; |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 111 | if (extra != 0) { |
Jason Evans | 2ee2f1e | 2016-04-06 10:38:47 -0700 | [diff] [blame] | 112 | bitmap[binfo->ngroups - 1] >>= extra; |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 113 | } |
Dave Watson | b8823ab | 2016-02-24 08:04:43 -0800 | [diff] [blame] | 114 | } |
| 115 | |
Jason Evans | 45f087e | 2017-04-16 09:25:56 -0700 | [diff] [blame] | 116 | #endif /* BITMAP_USE_TREE */ |
| 117 | |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 118 | size_t |
Jason Evans | c4c2592 | 2017-01-15 16:56:30 -0800 | [diff] [blame] | 119 | bitmap_size(const bitmap_info_t *binfo) { |
Jason Evans | 01ecdf3 | 2016-02-26 13:59:41 -0800 | [diff] [blame] | 120 | return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP); |
| 121 | } |