1 #include "jemalloc/internal/jemalloc_preamble.h" 2 #include "jemalloc/internal/jemalloc_internal_includes.h" 3 4 #include "jemalloc/internal/eset.h" 5 6 #define ESET_NPSIZES (SC_NPSIZES + 1) 7 8 static void 9 eset_bin_init(eset_bin_t *bin) { 10 edata_heap_new(&bin->heap); 11 /* 12 * heap_min doesn't need initialization; it gets filled in when the bin 13 * goes from non-empty to empty. 14 */ 15 } 16 17 static void 18 eset_bin_stats_init(eset_bin_stats_t *bin_stats) { 19 atomic_store_zu(&bin_stats->nextents, 0, ATOMIC_RELAXED); 20 atomic_store_zu(&bin_stats->nbytes, 0, ATOMIC_RELAXED); 21 } 22 23 void 24 eset_init(eset_t *eset, extent_state_t state) { 25 for (unsigned i = 0; i < ESET_NPSIZES; i++) { 26 eset_bin_init(&eset->bins[i]); 27 eset_bin_stats_init(&eset->bin_stats[i]); 28 } 29 fb_init(eset->bitmap, ESET_NPSIZES); 30 edata_list_inactive_init(&eset->lru); 31 eset->state = state; 32 } 33 34 size_t 35 eset_npages_get(eset_t *eset) { 36 return atomic_load_zu(&eset->npages, ATOMIC_RELAXED); 37 } 38 39 size_t 40 eset_nextents_get(eset_t *eset, pszind_t pind) { 41 return atomic_load_zu(&eset->bin_stats[pind].nextents, ATOMIC_RELAXED); 42 } 43 44 size_t 45 eset_nbytes_get(eset_t *eset, pszind_t pind) { 46 return atomic_load_zu(&eset->bin_stats[pind].nbytes, ATOMIC_RELAXED); 47 } 48 49 static void 50 eset_stats_add(eset_t *eset, pszind_t pind, size_t sz) { 51 size_t cur = atomic_load_zu(&eset->bin_stats[pind].nextents, 52 ATOMIC_RELAXED); 53 atomic_store_zu(&eset->bin_stats[pind].nextents, cur + 1, 54 ATOMIC_RELAXED); 55 cur = atomic_load_zu(&eset->bin_stats[pind].nbytes, ATOMIC_RELAXED); 56 atomic_store_zu(&eset->bin_stats[pind].nbytes, cur + sz, 57 ATOMIC_RELAXED); 58 } 59 60 static void 61 eset_stats_sub(eset_t *eset, pszind_t pind, size_t sz) { 62 size_t cur = atomic_load_zu(&eset->bin_stats[pind].nextents, 63 ATOMIC_RELAXED); 64 atomic_store_zu(&eset->bin_stats[pind].nextents, cur - 1, 65 ATOMIC_RELAXED); 66 cur = atomic_load_zu(&eset->bin_stats[pind].nbytes, ATOMIC_RELAXED); 67 atomic_store_zu(&eset->bin_stats[pind].nbytes, cur - sz, 68 ATOMIC_RELAXED); 69 } 70 71 void 72 eset_insert(eset_t *eset, edata_t *edata) { 73 assert(edata_state_get(edata) == eset->state); 74 75 size_t size = edata_size_get(edata); 76 size_t psz = sz_psz_quantize_floor(size); 77 pszind_t pind = sz_psz2ind(psz); 78 79 edata_cmp_summary_t edata_cmp_summary = edata_cmp_summary_get(edata); 80 if (edata_heap_empty(&eset->bins[pind].heap)) { 81 fb_set(eset->bitmap, ESET_NPSIZES, (size_t)pind); 82 /* Only element is automatically the min element. */ 83 eset->bins[pind].heap_min = edata_cmp_summary; 84 } else { 85 /* 86 * There's already a min element; update the summary if we're 87 * about to insert a lower one. 88 */ 89 if (edata_cmp_summary_comp(edata_cmp_summary, 90 eset->bins[pind].heap_min) < 0) { 91 eset->bins[pind].heap_min = edata_cmp_summary; 92 } 93 } 94 edata_heap_insert(&eset->bins[pind].heap, edata); 95 96 if (config_stats) { 97 eset_stats_add(eset, pind, size); 98 } 99 100 edata_list_inactive_append(&eset->lru, edata); 101 size_t npages = size >> LG_PAGE; 102 /* 103 * All modifications to npages hold the mutex (as asserted above), so we 104 * don't need an atomic fetch-add; we can get by with a load followed by 105 * a store. 106 */ 107 size_t cur_eset_npages = 108 atomic_load_zu(&eset->npages, ATOMIC_RELAXED); 109 atomic_store_zu(&eset->npages, cur_eset_npages + npages, 110 ATOMIC_RELAXED); 111 } 112 113 void 114 eset_remove(eset_t *eset, edata_t *edata) { 115 assert(edata_state_get(edata) == eset->state || 116 edata_state_in_transition(edata_state_get(edata))); 117 118 size_t size = edata_size_get(edata); 119 size_t psz = sz_psz_quantize_floor(size); 120 pszind_t pind = sz_psz2ind(psz); 121 if (config_stats) { 122 eset_stats_sub(eset, pind, size); 123 } 124 125 edata_cmp_summary_t edata_cmp_summary = edata_cmp_summary_get(edata); 126 edata_heap_remove(&eset->bins[pind].heap, edata); 127 if (edata_heap_empty(&eset->bins[pind].heap)) { 128 fb_unset(eset->bitmap, ESET_NPSIZES, (size_t)pind); 129 } else { 130 /* 131 * This is a little weird; we compare if the summaries are 132 * equal, rather than if the edata we removed was the heap 133 * minimum. The reason why is that getting the heap minimum 134 * can cause a pairing heap merge operation. We can avoid this 135 * if we only update the min if it's changed, in which case the 136 * summaries of the removed element and the min element should 137 * compare equal. 138 */ 139 if (edata_cmp_summary_comp(edata_cmp_summary, 140 eset->bins[pind].heap_min) == 0) { 141 eset->bins[pind].heap_min = edata_cmp_summary_get( 142 edata_heap_first(&eset->bins[pind].heap)); 143 } 144 } 145 edata_list_inactive_remove(&eset->lru, edata); 146 size_t npages = size >> LG_PAGE; 147 /* 148 * As in eset_insert, we hold eset->mtx and so don't need atomic 149 * operations for updating eset->npages. 150 */ 151 size_t cur_extents_npages = 152 atomic_load_zu(&eset->npages, ATOMIC_RELAXED); 153 assert(cur_extents_npages >= npages); 154 atomic_store_zu(&eset->npages, 155 cur_extents_npages - (size >> LG_PAGE), ATOMIC_RELAXED); 156 } 157 158 /* 159 * Find an extent with size [min_size, max_size) to satisfy the alignment 160 * requirement. For each size, try only the first extent in the heap. 161 */ 162 static edata_t * 163 eset_fit_alignment(eset_t *eset, size_t min_size, size_t max_size, 164 size_t alignment) { 165 pszind_t pind = sz_psz2ind(sz_psz_quantize_ceil(min_size)); 166 pszind_t pind_max = sz_psz2ind(sz_psz_quantize_ceil(max_size)); 167 168 for (pszind_t i = 169 (pszind_t)fb_ffs(eset->bitmap, ESET_NPSIZES, (size_t)pind); 170 i < pind_max; 171 i = (pszind_t)fb_ffs(eset->bitmap, ESET_NPSIZES, (size_t)i + 1)) { 172 assert(i < SC_NPSIZES); 173 assert(!edata_heap_empty(&eset->bins[i].heap)); 174 edata_t *edata = edata_heap_first(&eset->bins[i].heap); 175 uintptr_t base = (uintptr_t)edata_base_get(edata); 176 size_t candidate_size = edata_size_get(edata); 177 assert(candidate_size >= min_size); 178 179 uintptr_t next_align = ALIGNMENT_CEILING((uintptr_t)base, 180 PAGE_CEILING(alignment)); 181 if (base > next_align || base + candidate_size <= next_align) { 182 /* Overflow or not crossing the next alignment. */ 183 continue; 184 } 185 186 size_t leadsize = next_align - base; 187 if (candidate_size - leadsize >= min_size) { 188 return edata; 189 } 190 } 191 192 return NULL; 193 } 194 195 /* 196 * Do first-fit extent selection, i.e. select the oldest/lowest extent that is 197 * large enough. 198 * 199 * lg_max_fit is the (log of the) maximum ratio between the requested size and 200 * the returned size that we'll allow. This can reduce fragmentation by 201 * avoiding reusing and splitting large extents for smaller sizes. In practice, 202 * it's set to opt_lg_extent_max_active_fit for the dirty eset and SC_PTR_BITS 203 * for others. 204 */ 205 static edata_t * 206 eset_first_fit(eset_t *eset, size_t size, bool exact_only, 207 unsigned lg_max_fit) { 208 edata_t *ret = NULL; 209 edata_cmp_summary_t ret_summ JEMALLOC_CC_SILENCE_INIT({0}); 210 211 pszind_t pind = sz_psz2ind(sz_psz_quantize_ceil(size)); 212 213 if (exact_only) { 214 return edata_heap_empty(&eset->bins[pind].heap) ? NULL : 215 edata_heap_first(&eset->bins[pind].heap); 216 } 217 218 for (pszind_t i = 219 (pszind_t)fb_ffs(eset->bitmap, ESET_NPSIZES, (size_t)pind); 220 i < ESET_NPSIZES; 221 i = (pszind_t)fb_ffs(eset->bitmap, ESET_NPSIZES, (size_t)i + 1)) { 222 assert(!edata_heap_empty(&eset->bins[i].heap)); 223 if (lg_max_fit == SC_PTR_BITS) { 224 /* 225 * We'll shift by this below, and shifting out all the 226 * bits is undefined. Decreasing is safe, since the 227 * page size is larger than 1 byte. 228 */ 229 lg_max_fit = SC_PTR_BITS - 1; 230 } 231 if ((sz_pind2sz(i) >> lg_max_fit) > size) { 232 break; 233 } 234 if (ret == NULL || edata_cmp_summary_comp( 235 eset->bins[i].heap_min, ret_summ) < 0) { 236 /* 237 * We grab the edata as early as possible, even though 238 * we might change it later. Practically, a large 239 * portion of eset_fit calls succeed at the first valid 240 * index, so this doesn't cost much, and we get the 241 * effect of prefetching the edata as early as possible. 242 */ 243 edata_t *edata = edata_heap_first(&eset->bins[i].heap); 244 assert(edata_size_get(edata) >= size); 245 assert(ret == NULL || edata_snad_comp(edata, ret) < 0); 246 assert(ret == NULL || edata_cmp_summary_comp( 247 eset->bins[i].heap_min, 248 edata_cmp_summary_get(edata)) == 0); 249 ret = edata; 250 ret_summ = eset->bins[i].heap_min; 251 } 252 if (i == SC_NPSIZES) { 253 break; 254 } 255 assert(i < SC_NPSIZES); 256 } 257 258 return ret; 259 } 260 261 edata_t * 262 eset_fit(eset_t *eset, size_t esize, size_t alignment, bool exact_only, 263 unsigned lg_max_fit) { 264 size_t max_size = esize + PAGE_CEILING(alignment) - PAGE; 265 /* Beware size_t wrap-around. */ 266 if (max_size < esize) { 267 return NULL; 268 } 269 270 edata_t *edata = eset_first_fit(eset, max_size, exact_only, lg_max_fit); 271 272 if (alignment > PAGE && edata == NULL) { 273 /* 274 * max_size guarantees the alignment requirement but is rather 275 * pessimistic. Next we try to satisfy the aligned allocation 276 * with sizes in [esize, max_size). 277 */ 278 edata = eset_fit_alignment(eset, esize, max_size, alignment); 279 } 280 281 return edata; 282 } 283