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 | |