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
8static void
9eset_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
17static void
18eset_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
23void
24eset_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
34size_t
35eset_npages_get(eset_t *eset) {
36 return atomic_load_zu(&eset->npages, ATOMIC_RELAXED);
37}
38
39size_t
40eset_nextents_get(eset_t *eset, pszind_t pind) {
41 return atomic_load_zu(&eset->bin_stats[pind].nextents, ATOMIC_RELAXED);
42}
43
44size_t
45eset_nbytes_get(eset_t *eset, pszind_t pind) {
46 return atomic_load_zu(&eset->bin_stats[pind].nbytes, ATOMIC_RELAXED);
47}
48
49static void
50eset_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
60static void
61eset_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
71void
72eset_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
113void
114eset_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 */
162static edata_t *
163eset_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 */
205static edata_t *
206eset_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
261edata_t *
262eset_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