Skip to content

Commit 259c5e3

Browse files
davidtgoldblattdavidtgoldblatt
committed
psset: Add stats
1 parent 018b162 commit 259c5e3

File tree

4 files changed

+178
-13
lines changed

4 files changed

+178
-13
lines changed

‎include/jemalloc/internal/edata.h‎

Lines changed: 8 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -218,13 +218,17 @@ struct edata_s {
218218
*/
219219
edata_t *ps;
220220
/*
221-
* If this edata *is* a pageslab, then it has some longest free
222-
* range in it. Track it.
221+
* If this edata *is* a pageslab, then we cache some useful
222+
* information about its associated bitmap.
223223
*/
224224
struct {
225+
/*
226+
* The longest free range a pageslab contains determines
227+
* the heap it lives in. If we know that it didn't
228+
* change after an operation, we can avoid moving it
229+
* between heaps.
230+
*/
225231
uint32_t longest_free_range;
226-
/* Not yet tracked. */
227-
/* uint32_t longest_free_range_pos; */
228232
};
229233
};
230234

‎include/jemalloc/internal/psset.h‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,16 @@
2121
*/
2222
#define PSSET_NPSIZES 64
2323

24+
typedef struct psset_bin_stats_s psset_bin_stats_t;
25+
struct psset_bin_stats_s {
26+
/* How many pageslabs are in this bin? */
27+
size_t npageslabs;
28+
/* Of them, how many pages are active? */
29+
size_t nactive;
30+
/* How many are inactive? */
31+
size_t ninactive;
32+
};
33+
2434
typedef struct psset_s psset_t;
2535
struct psset_s {
2636
/*
@@ -29,6 +39,12 @@ struct psset_s {
2939
*/
3040
edata_heap_t pageslabs[PSSET_NPSIZES];
3141
bitmap_t bitmap[BITMAP_GROUPS(PSSET_NPSIZES)];
42+
/*
43+
* Full slabs don't live in any edata heap. But we still track their
44+
* stats.
45+
*/
46+
psset_bin_stats_t full_slab_stats;
47+
psset_bin_stats_t slab_stats[PSSET_NPSIZES];
3248
};
3349

3450
void psset_init(psset_t *psset);

‎src/psset.c‎

Lines changed: 77 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,48 @@ psset_init(psset_t *psset) {
1414
edata_heap_new(&psset->pageslabs[i]);
1515
}
1616
bitmap_init(psset->bitmap, &psset_bitmap_info, /* fill */ true);
17+
psset->full_slab_stats.npageslabs = 0;
18+
psset->full_slab_stats.nactive = 0;
19+
psset->full_slab_stats.ninactive = 0;
20+
for (unsigned i = 0; i < PSSET_NPSIZES; i++) {
21+
psset->slab_stats[i].npageslabs = 0;
22+
psset->slab_stats[i].nactive = 0;
23+
psset->slab_stats[i].ninactive = 0;
24+
}
25+
}
26+
27+
/*
28+
* The stats maintenance strategy is simple, but not necessarily obvious.
29+
* edata_nfree and the bitmap must remain consistent at all times. If they
30+
* change while an edata is within an edata_heap (or full), then the associated
31+
* stats bin (or the full bin) must also change. If they change while not in a
32+
* bin (say, in between extraction and reinsertion), then the bin stats need not
33+
* change. If a pageslab is removed from a bin (or becomes nonfull), it should
34+
* no longer contribute to that bin's stats (or the full stats). These help
35+
* ensure we don't miss any heap modification operations.
36+
*/
37+
JEMALLOC_ALWAYS_INLINE void
38+
psset_bin_stats_adjust(psset_bin_stats_t *binstats, edata_t *ps, bool inc) {
39+
size_t mul = inc ? (size_t)1 : (size_t)-1;
40+
41+
size_t npages = edata_size_get(ps) >> LG_PAGE;
42+
size_t ninactive = edata_nfree_get(ps);
43+
size_t nactive = npages - ninactive;
44+
binstats->npageslabs += mul * 1;
45+
binstats->nactive += mul * nactive;
46+
binstats->ninactive += mul * ninactive;
47+
}
48+
49+
static void
50+
psset_edata_heap_remove(psset_t *psset, pszind_t pind, edata_t *ps) {
51+
edata_heap_remove(&psset->pageslabs[pind], ps);
52+
psset_bin_stats_adjust(&psset->slab_stats[pind], ps, /* inc */ false);
53+
}
54+
55+
static void
56+
psset_edata_heap_insert(psset_t *psset, pszind_t pind, edata_t *ps) {
57+
edata_heap_insert(&psset->pageslabs[pind], ps);
58+
psset_bin_stats_adjust(&psset->slab_stats[pind], ps, /* inc */ true);
1759
}
1860

1961
JEMALLOC_ALWAYS_INLINE void
@@ -46,7 +88,8 @@ psset_recycle_extract(psset_t *psset, size_t size) {
4688
if (ret == NULL) {
4789
return NULL;
4890
}
49-
edata_heap_remove(&psset->pageslabs[ret_ind], ret);
91+
92+
psset_edata_heap_remove(psset, ret_ind, ret);
5093
if (edata_heap_empty(&psset->pageslabs[ret_ind])) {
5194
bitmap_set(psset->bitmap, &psset_bitmap_info, ret_ind);
5295
}
@@ -67,7 +110,7 @@ psset_insert(psset_t *psset, edata_t *ps, size_t largest_range) {
67110
if (edata_heap_empty(&psset->pageslabs[pind])) {
68111
bitmap_unset(psset->bitmap, &psset_bitmap_info, (size_t)pind);
69112
}
70-
edata_heap_insert(&psset->pageslabs[pind], ps);
113+
psset_edata_heap_insert(psset, pind, ps);
71114
}
72115

73116
/*
@@ -120,6 +163,9 @@ psset_ps_alloc_insert(psset_t *psset, edata_t *ps, edata_t *r_edata,
120163
EXTENT_NOT_HEAD);
121164
edata_ps_set(r_edata, ps);
122165
fb_set_range(ps_fb, ps_npages, begin, npages);
166+
edata_nfree_set(ps, (uint32_t)(edata_nfree_get(ps) - npages));
167+
/* The pageslab isn't in a bin, so no bin stats need to change. */
168+
123169
/*
124170
* OK, we've got to put the pageslab back. First we have to figure out
125171
* where, though; we've only checked run sizes before the pageslab we
@@ -144,7 +190,10 @@ psset_ps_alloc_insert(psset_t *psset, edata_t *ps, edata_t *r_edata,
144190
start = begin + len;
145191
}
146192
edata_longest_free_range_set(ps, (uint32_t)largest_unchosen_range);
147-
if (largest_unchosen_range != 0) {
193+
if (largest_unchosen_range == 0) {
194+
psset_bin_stats_adjust(&psset->full_slab_stats, ps,
195+
/* inc */ true);
196+
} else {
148197
psset_insert(psset, ps, largest_unchosen_range);
149198
}
150199
}
@@ -164,8 +213,8 @@ psset_alloc_new(psset_t *psset, edata_t *ps, edata_t *r_edata, size_t size) {
164213
fb_group_t *ps_fb = edata_slab_data_get(ps)->bitmap;
165214
size_t ps_npages = edata_size_get(ps) >> LG_PAGE;
166215
assert(fb_empty(ps_fb, ps_npages));
167-
168216
assert(ps_npages >= (size >> LG_PAGE));
217+
edata_nfree_set(ps, (uint32_t)ps_npages);
169218
psset_ps_alloc_insert(psset, ps, r_edata, size);
170219
}
171220

@@ -177,13 +226,35 @@ psset_dalloc(psset_t *psset, edata_t *edata) {
177226
edata_t *ps = edata_ps_get(edata);
178227
fb_group_t *ps_fb = edata_slab_data_get(ps)->bitmap;
179228
size_t ps_old_longest_free_range = edata_longest_free_range_get(ps);
229+
pszind_t old_pind = SC_NPSIZES;
230+
if (ps_old_longest_free_range != 0) {
231+
old_pind = sz_psz2ind(sz_psz_quantize_floor(
232+
ps_old_longest_free_range << LG_PAGE));
233+
}
180234

181235
size_t ps_npages = edata_size_get(ps) >> LG_PAGE;
182236
size_t begin =
183237
((uintptr_t)edata_base_get(edata) - (uintptr_t)edata_base_get(ps))
184238
>> LG_PAGE;
185239
size_t len = edata_size_get(edata) >> LG_PAGE;
186240
fb_unset_range(ps_fb, ps_npages, begin, len);
241+
if (ps_old_longest_free_range == 0) {
242+
/* We were in the (imaginary) full bin; update stats for it. */
243+
psset_bin_stats_adjust(&psset->full_slab_stats, ps,
244+
/* inc */ false);
245+
} else {
246+
/*
247+
* The edata is still in the bin, need to update its
248+
* contribution.
249+
*/
250+
psset->slab_stats[old_pind].nactive -= len;
251+
psset->slab_stats[old_pind].ninactive += len;
252+
}
253+
/*
254+
* Note that we want to do this after the stats updates, since if it was
255+
* full it psset_bin_stats_adjust would have looked at the old version.
256+
*/
257+
edata_nfree_set(ps, (uint32_t)(edata_nfree_get(ps) + len));
187258

188259
/* We might have just created a new, larger range. */
189260
size_t new_begin = (size_t)(fb_fls(ps_fb, ps_npages, begin) + 1);
@@ -215,9 +286,7 @@ psset_dalloc(psset_t *psset, edata_t *edata) {
215286
* and the issue becomes moot).
216287
*/
217288
if (ps_old_longest_free_range > 0) {
218-
pszind_t old_pind = sz_psz2ind(sz_psz_quantize_floor(
219-
ps_old_longest_free_range<< LG_PAGE));
220-
edata_heap_remove(&psset->pageslabs[old_pind], ps);
289+
psset_edata_heap_remove(psset, old_pind, ps);
221290
if (edata_heap_empty(&psset->pageslabs[old_pind])) {
222291
bitmap_set(psset->bitmap, &psset_bitmap_info,
223292
(size_t)old_pind);
@@ -234,6 +303,6 @@ psset_dalloc(psset_t *psset, edata_t *edata) {
234303
bitmap_unset(psset->bitmap, &psset_bitmap_info,
235304
(size_t)new_pind);
236305
}
237-
edata_heap_insert(&psset->pageslabs[new_pind], ps);
306+
psset_edata_heap_insert(psset, new_pind, ps);
238307
return NULL;
239308
}

‎test/unit/psset.c‎

Lines changed: 77 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -295,12 +295,88 @@ TEST_BEGIN(test_multi_pageslab) {
295295
}
296296
TEST_END
297297

298+
static void
299+
stats_expect_empty(psset_bin_stats_t *stats) {
300+
assert_zu_eq(0, stats->npageslabs,
301+
"Supposedly empty bin had positive npageslabs");
302+
expect_zu_eq(0, stats->nactive, "Unexpected nonempty bin"
303+
"Supposedly empty bin had positive nactive");
304+
expect_zu_eq(0, stats->ninactive, "Unexpected nonempty bin"
305+
"Supposedly empty bin had positive ninactive");
306+
}
307+
308+
static void
309+
stats_expect(psset_t *psset, size_t nactive) {
310+
if (nactive == PAGESLAB_PAGES) {
311+
expect_zu_eq(1, psset->full_slab_stats.npageslabs,
312+
"Expected a full slab");
313+
expect_zu_eq(PAGESLAB_PAGES, psset->full_slab_stats.nactive,
314+
"Should have exactly filled the bin");
315+
expect_zu_eq(0, psset->full_slab_stats.ninactive,
316+
"Should never have inactive pages in a full slab");
317+
} else {
318+
stats_expect_empty(&psset->full_slab_stats);
319+
}
320+
size_t ninactive = PAGESLAB_PAGES - nactive;
321+
pszind_t nonempty_pind = PSSET_NPSIZES;
322+
if (ninactive != 0 && ninactive < PAGESLAB_PAGES) {
323+
nonempty_pind = sz_psz2ind(sz_psz_quantize_floor(
324+
ninactive << LG_PAGE));
325+
}
326+
for (pszind_t i = 0; i < PSSET_NPSIZES; i++) {
327+
if (i == nonempty_pind) {
328+
assert_zu_eq(1, psset->slab_stats[i].npageslabs,
329+
"Should have found a slab");
330+
expect_zu_eq(nactive, psset->slab_stats[i].nactive,
331+
"Mismatch in active pages");
332+
expect_zu_eq(ninactive, psset->slab_stats[i].ninactive,
333+
"Mismatch in inactive pages");
334+
} else {
335+
stats_expect_empty(&psset->slab_stats[i]);
336+
}
337+
}
338+
}
339+
340+
TEST_BEGIN(test_stats) {
341+
bool err;
342+
edata_t pageslab;
343+
memset(&pageslab, 0, sizeof(pageslab));
344+
edata_t alloc[PAGESLAB_PAGES];
345+
346+
edata_init(&pageslab, /* arena_ind */ 0, PAGESLAB_ADDR, PAGESLAB_SIZE,
347+
/* slab */ true, SC_NSIZES, PAGESLAB_SN, extent_state_active,
348+
/* zeroed */ false, /* comitted */ true, EXTENT_PAI_HPA,
349+
EXTENT_IS_HEAD);
350+
351+
psset_t psset;
352+
psset_init(&psset);
353+
stats_expect(&psset, 0);
354+
355+
edata_init_test(&alloc[0]);
356+
psset_alloc_new(&psset, &pageslab, &alloc[0], PAGE);
357+
for (size_t i = 1; i < PAGESLAB_PAGES; i++) {
358+
stats_expect(&psset, i);
359+
edata_init_test(&alloc[i]);
360+
err = psset_alloc_reuse(&psset, &alloc[i], PAGE);
361+
expect_false(err, "Nonempty psset failed page allocation.");
362+
}
363+
stats_expect(&psset, PAGESLAB_PAGES);
364+
for (ssize_t i = PAGESLAB_PAGES - 1; i >= 0; i--) {
365+
edata_t *ps = psset_dalloc(&psset, &alloc[i]);
366+
expect_true((ps == NULL) == (i != 0),
367+
"psset_dalloc should only evict a slab on the last free");
368+
stats_expect(&psset, i);
369+
}
370+
}
371+
TEST_END
372+
298373
int
299374
main(void) {
300375
return test_no_reentrancy(
301376
test_empty,
302377
test_fill,
303378
test_reuse,
304379
test_evict,
305-
test_multi_pageslab);
380+
test_multi_pageslab,
381+
test_stats);
306382
}

0 commit comments

Comments
 (0)