project-base/server-skynet-source-3rd-jemalloc
2
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
master
server-skynet-source-3rd-je.../test/unit/cache_bin.c

385 lines
14 KiB
C
Raw Permalink Normal View History

Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
#include "test/jemalloc_test.h"
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
static void
do_fill_test(cache_bin_t *bin, cache_bin_info_t *info, void **ptrs,
cache_bin_sz_t ncached_max, cache_bin_sz_t nfill_attempt,
cache_bin_sz_t nfill_succeed) {
bool success;
void *ptr;
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
assert_true(cache_bin_ncached_get_local(bin, info) == 0, "");
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
CACHE_BIN_PTR_ARRAY_DECLARE(arr, nfill_attempt);
cache_bin_init_ptr_array_for_fill(bin, info, &arr, nfill_attempt);
for (cache_bin_sz_t i = 0; i < nfill_succeed; i++) {
arr.ptr[i] = &ptrs[i];
}
cache_bin_finish_fill(bin, info, &arr, nfill_succeed);
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(bin, info) == nfill_succeed,
"");
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
cache_bin_low_water_set(bin);
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
for (cache_bin_sz_t i = 0; i < nfill_succeed; i++) {
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc(bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_true(success, "");
expect_ptr_eq(ptr, (void *)&ptrs[i],
"Should pop in order filled");
expect_true(cache_bin_low_water_get(bin, info)
== nfill_succeed - i - 1, "");
}
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(bin, info) == 0, "");
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_true(cache_bin_low_water_get(bin, info) == 0, "");
}
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
static void
do_flush_test(cache_bin_t *bin, cache_bin_info_t *info, void **ptrs,
cache_bin_sz_t nfill, cache_bin_sz_t nflush) {
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
bool success;
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
assert_true(cache_bin_ncached_get_local(bin, info) == 0, "");
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
for (cache_bin_sz_t i = 0; i < nfill; i++) {
success = cache_bin_dalloc_easy(bin, &ptrs[i]);
expect_true(success, "");
}
CACHE_BIN_PTR_ARRAY_DECLARE(arr, nflush);
cache_bin_init_ptr_array_for_flush(bin, info, &arr, nflush);
for (cache_bin_sz_t i = 0; i < nflush; i++) {
Cache bin: Don't reverse flush order. The items we pick to flush matter a lot, but the order in which they get flushed doesn't; just use forward scans. This simplifies the accessing code, both in terms of the C and the generated assembly (i.e. this speeds up the flush pathways).
2021-01-30 05:10:44 +08:00
expect_ptr_eq(arr.ptr[i], &ptrs[nflush - i - 1], "");
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
}
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
cache_bin_finish_flush(bin, info, &arr, nflush);
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(bin, info) == nfill - nflush,
"");
while (cache_bin_ncached_get_local(bin, info) > 0) {
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
cache_bin_alloc(bin, &success);
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
}
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
}
Add a batch mode for cache_bin_alloc()
2020-10-23 07:07:25 +08:00
static void
do_batch_alloc_test(cache_bin_t *bin, cache_bin_info_t *info, void **ptrs,
cache_bin_sz_t nfill, size_t batch) {
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
assert_true(cache_bin_ncached_get_local(bin, info) == 0, "");
Add a batch mode for cache_bin_alloc()
2020-10-23 07:07:25 +08:00
CACHE_BIN_PTR_ARRAY_DECLARE(arr, nfill);
cache_bin_init_ptr_array_for_fill(bin, info, &arr, nfill);
for (cache_bin_sz_t i = 0; i < nfill; i++) {
arr.ptr[i] = &ptrs[i];
}
cache_bin_finish_fill(bin, info, &arr, nfill);
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
assert_true(cache_bin_ncached_get_local(bin, info) == nfill, "");
Add a batch mode for cache_bin_alloc()
2020-10-23 07:07:25 +08:00
cache_bin_low_water_set(bin);
void **out = malloc((batch + 1) * sizeof(void *));
size_t n = cache_bin_alloc_batch(bin, batch, out);
assert_true(n == ((size_t)nfill < batch ? (size_t)nfill : batch), "");
for (cache_bin_sz_t i = 0; i < (cache_bin_sz_t)n; i++) {
expect_ptr_eq(out[i], &ptrs[i], "");
}
expect_true(cache_bin_low_water_get(bin, info) == nfill -
(cache_bin_sz_t)n, "");
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
while (cache_bin_ncached_get_local(bin, info) > 0) {
Add a batch mode for cache_bin_alloc()
2020-10-23 07:07:25 +08:00
bool success;
cache_bin_alloc(bin, &success);
}
free(out);
}
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
static void
test_bin_init(cache_bin_t *bin, cache_bin_info_t *info) {
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
size_t size;
size_t alignment;
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
cache_bin_info_compute_alloc(info, 1, &size, &alignment);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
void *mem = mallocx(size, MALLOCX_ALIGN(alignment));
assert_ptr_not_null(mem, "Unexpected mallocx failure");
size_t cur_offset = 0;
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
cache_bin_preincrement(info, 1, mem, &cur_offset);
cache_bin_init(bin, info, mem, &cur_offset);
cache_bin_postincrement(info, 1, mem, &cur_offset);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
assert_zu_eq(cur_offset, size, "Should use all requested memory");
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
}
TEST_BEGIN(test_cache_bin) {
const int ncached_max = 100;
bool success;
void *ptr;
cache_bin_info_t info;
cache_bin_info_init(&info, ncached_max);
cache_bin_t bin;
test_bin_init(&bin, &info);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
/* Initialize to empty; should then have 0 elements. */
Tcache: make slot sizing configurable.
2020-05-12 06:03:06 +08:00
expect_d_eq(ncached_max, cache_bin_info_ncached_max(&info), "");
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(&bin, &info) == 0, "");
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_true(cache_bin_low_water_get(&bin, &info) == 0, "");
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc_easy(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_false(success, "Shouldn't successfully allocate when empty");
expect_ptr_null(ptr, "Shouldn't get a non-null pointer on failure");
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_false(success, "Shouldn't successfully allocate when empty");
expect_ptr_null(ptr, "Shouldn't get a non-null pointer on failure");
/*
* We allocate one more item than ncached_max, so we can test cache bin
* exhaustion.
*/
void **ptrs = mallocx(sizeof(void *) * (ncached_max + 1), 0);
assert_ptr_not_null(ptrs, "Unexpected mallocx failure");
for (cache_bin_sz_t i = 0; i < ncached_max; i++) {
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(&bin, &info) == i, "");
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
success = cache_bin_dalloc_easy(&bin, &ptrs[i]);
expect_true(success,
"Should be able to dalloc into a non-full cache bin.");
expect_true(cache_bin_low_water_get(&bin, &info) == 0,
"Pushes and pops shouldn't change low water of zero.");
}
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(&bin, &info) == ncached_max,
"");
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
success = cache_bin_dalloc_easy(&bin, &ptrs[ncached_max]);
expect_false(success, "Shouldn't be able to dalloc into a full bin.");
cache_bin_low_water_set(&bin);
for (cache_bin_sz_t i = 0; i < ncached_max; i++) {
expect_true(cache_bin_low_water_get(&bin, &info)
== ncached_max - i, "");
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(&bin, &info)
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
== ncached_max - i, "");
/*
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
* This should fail -- the easy variant can't change the low
* water mark.
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
*/
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc_easy(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_ptr_null(ptr, "");
expect_false(success, "");
expect_true(cache_bin_low_water_get(&bin, &info)
== ncached_max - i, "");
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(&bin, &info)
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
== ncached_max - i, "");
/* This should succeed, though. */
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_true(success, "");
expect_ptr_eq(ptr, &ptrs[ncached_max - i - 1],
"Alloc should pop in stack order");
expect_true(cache_bin_low_water_get(&bin, &info)
== ncached_max - i - 1, "");
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(&bin, &info)
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
== ncached_max - i - 1, "");
}
/* Now we're empty -- all alloc attempts should fail. */
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(&bin, &info) == 0, "");
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc_easy(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_ptr_null(ptr, "");
expect_false(success, "");
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_ptr_null(ptr, "");
expect_false(success, "");
for (cache_bin_sz_t i = 0; i < ncached_max / 2; i++) {
cache_bin_dalloc_easy(&bin, &ptrs[i]);
}
cache_bin_low_water_set(&bin);
for (cache_bin_sz_t i = ncached_max / 2; i < ncached_max; i++) {
cache_bin_dalloc_easy(&bin, &ptrs[i]);
}
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
expect_true(cache_bin_ncached_get_local(&bin, &info) == ncached_max,
"");
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
for (cache_bin_sz_t i = ncached_max - 1; i >= ncached_max / 2; i--) {
/*
* Size is bigger than low water -- the reduced version should
* succeed.
*/
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc_easy(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_true(success, "");
expect_ptr_eq(ptr, &ptrs[i], "");
}
/* But now, we've hit low-water. */
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
ptr = cache_bin_alloc_easy(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_false(success, "");
expect_ptr_null(ptr, "");
/* We're going to test filling -- we must be empty to start. */
cache_bin: Separate out local and remote accesses. This fixes an incorrect debug-mode assert: - T1 starts an arena stats update and reads stack_head from another thread's cache bin, when that cache bin has 1 item in it. - T2 allocates from that cache bin. The cache_bin's stack_head now points to a NULL pointer, since the cache bin is empty. - T1 Re-reads the cache_bin's stack_head to perform an assertion check (since it previously saw that the bin was empty, whatever stack_head points to should be non-NULL).
2021-01-08 05:22:08 +08:00
while (cache_bin_ncached_get_local(&bin, &info)) {
Fast path: allow low-water mark changes. This lets us put more allocations on an "almost as fast" path after a flush. This results in around a 4% reduction in malloc cycles in prod workloads (corresponding to about a 0.1% reduction in overall cycles).
2020-03-05 00:58:42 +08:00
cache_bin_alloc(&bin, &success);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
expect_true(success, "");
}
/* Test fill. */
/* Try to fill all, succeed fully. */
do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max, ncached_max);
/* Try to fill all, succeed partially. */
do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max,
ncached_max / 2);
/* Try to fill all, fail completely. */
do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max, 0);
/* Try to fill some, succeed fully. */
do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max / 2,
ncached_max / 2);
/* Try to fill some, succeed partially. */
do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max / 2,
Fix a cache bin test
2020-10-23 05:56:15 +08:00
ncached_max / 4);
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
/* Try to fill some, fail completely. */
do_fill_test(&bin, &info, ptrs, ncached_max, ncached_max / 2, 0);
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
Cache bin: Write the unit test in terms of the API I.e. stop allowing the unit test to have secret access to implementation internals.
2020-03-03 06:14:08 +08:00
do_flush_test(&bin, &info, ptrs, ncached_max, ncached_max);
do_flush_test(&bin, &info, ptrs, ncached_max, ncached_max / 2);
do_flush_test(&bin, &info, ptrs, ncached_max, 0);
do_flush_test(&bin, &info, ptrs, ncached_max / 2, ncached_max / 2);
do_flush_test(&bin, &info, ptrs, ncached_max / 2, ncached_max / 4);
do_flush_test(&bin, &info, ptrs, ncached_max / 2, 0);
Fix a cache bin test
2020-10-23 05:56:15 +08:00
Add a batch mode for cache_bin_alloc()
2020-10-23 07:07:25 +08:00
do_batch_alloc_test(&bin, &info, ptrs, ncached_max, ncached_max);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max, ncached_max * 2);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max, ncached_max / 2);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max, 2);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max, 1);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max, 0);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2,
ncached_max / 2);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, ncached_max);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2,
ncached_max / 4);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, 2);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, 1);
do_batch_alloc_test(&bin, &info, ptrs, ncached_max / 2, 0);
do_batch_alloc_test(&bin, &info, ptrs, 2, ncached_max);
do_batch_alloc_test(&bin, &info, ptrs, 2, 2);
do_batch_alloc_test(&bin, &info, ptrs, 2, 1);
do_batch_alloc_test(&bin, &info, ptrs, 2, 0);
do_batch_alloc_test(&bin, &info, ptrs, 1, 2);
do_batch_alloc_test(&bin, &info, ptrs, 1, 1);
do_batch_alloc_test(&bin, &info, ptrs, 1, 0);
do_batch_alloc_test(&bin, &info, ptrs, 0, 2);
do_batch_alloc_test(&bin, &info, ptrs, 0, 1);
do_batch_alloc_test(&bin, &info, ptrs, 0, 0);
Fix a cache bin test
2020-10-23 05:56:15 +08:00
free(ptrs);
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
}
TEST_END
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
static void
do_flush_stashed_test(cache_bin_t *bin, cache_bin_info_t *info, void **ptrs,
cache_bin_sz_t nfill, cache_bin_sz_t nstash) {
expect_true(cache_bin_ncached_get_local(bin, info) == 0,
"Bin not empty");
Add stats for stashed bytes in tcache.
2021-12-01 06:39:34 +08:00
expect_true(cache_bin_nstashed_get_local(bin, info) == 0,
"Bin not empty");
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
expect_true(nfill + nstash <= info->ncached_max, "Exceeded max");
bool ret;
/* Fill */
for (cache_bin_sz_t i = 0; i < nfill; i++) {
ret = cache_bin_dalloc_easy(bin, &ptrs[i]);
expect_true(ret, "Unexpected fill failure");
}
expect_true(cache_bin_ncached_get_local(bin, info) == nfill,
"Wrong cached count");
/* Stash */
for (cache_bin_sz_t i = 0; i < nstash; i++) {
ret = cache_bin_stash(bin, &ptrs[i + nfill]);
expect_true(ret, "Unexpected stash failure");
}
Add stats for stashed bytes in tcache.
2021-12-01 06:39:34 +08:00
expect_true(cache_bin_nstashed_get_local(bin, info) == nstash,
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
"Wrong stashed count");
if (nfill + nstash == info->ncached_max) {
ret = cache_bin_dalloc_easy(bin, &ptrs[0]);
expect_false(ret, "Should not dalloc into a full bin");
ret = cache_bin_stash(bin, &ptrs[0]);
expect_false(ret, "Should not stash into a full bin");
}
/* Alloc filled ones */
for (cache_bin_sz_t i = 0; i < nfill; i++) {
void *ptr = cache_bin_alloc(bin, &ret);
expect_true(ret, "Unexpected alloc failure");
/* Verify it's not from the stashed range. */
expect_true((uintptr_t)ptr < (uintptr_t)&ptrs[nfill],
"Should not alloc stashed ptrs");
}
expect_true(cache_bin_ncached_get_local(bin, info) == 0,
"Wrong cached count");
Add stats for stashed bytes in tcache.
2021-12-01 06:39:34 +08:00
expect_true(cache_bin_nstashed_get_local(bin, info) == nstash,
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
"Wrong stashed count");
cache_bin_alloc(bin, &ret);
expect_false(ret, "Should not alloc stashed");
/* Clear stashed ones */
cache_bin_finish_flush_stashed(bin, info);
expect_true(cache_bin_ncached_get_local(bin, info) == 0,
"Wrong cached count");
Add stats for stashed bytes in tcache.
2021-12-01 06:39:34 +08:00
expect_true(cache_bin_nstashed_get_local(bin, info) == 0,
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
"Wrong stashed count");
cache_bin_alloc(bin, &ret);
expect_false(ret, "Should not alloc from empty bin");
}
TEST_BEGIN(test_cache_bin_stash) {
const int ncached_max = 100;
cache_bin_t bin;
cache_bin_info_t info;
cache_bin_info_init(&info, ncached_max);
test_bin_init(&bin, &info);
/*
* The content of this array is not accessed; instead the interior
* addresses are used to insert / stash into the bins as test pointers.
*/
void **ptrs = mallocx(sizeof(void *) * (ncached_max + 1), 0);
assert_ptr_not_null(ptrs, "Unexpected mallocx failure");
bool ret;
for (cache_bin_sz_t i = 0; i < ncached_max; i++) {
expect_true(cache_bin_ncached_get_local(&bin, &info) ==
(i / 2 + i % 2), "Wrong ncached value");
Add stats for stashed bytes in tcache.
2021-12-01 06:39:34 +08:00
expect_true(cache_bin_nstashed_get_local(&bin, &info) == i / 2,
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
"Wrong nstashed value");
if (i % 2 == 0) {
cache_bin_dalloc_easy(&bin, &ptrs[i]);
} else {
ret = cache_bin_stash(&bin, &ptrs[i]);
expect_true(ret, "Should be able to stash into a "
"non-full cache bin");
}
}
ret = cache_bin_dalloc_easy(&bin, &ptrs[0]);
expect_false(ret, "Should not dalloc into a full cache bin");
ret = cache_bin_stash(&bin, &ptrs[0]);
expect_false(ret, "Should not stash into a full cache bin");
for (cache_bin_sz_t i = 0; i < ncached_max; i++) {
void *ptr = cache_bin_alloc(&bin, &ret);
if (i < ncached_max / 2) {
expect_true(ret, "Should be able to alloc");
uintptr_t diff = ((uintptr_t)ptr - (uintptr_t)&ptrs[0])
/ sizeof(void *);
expect_true(diff % 2 == 0, "Should be able to alloc");
} else {
expect_false(ret, "Should not alloc stashed");
Add stats for stashed bytes in tcache.
2021-12-01 06:39:34 +08:00
expect_true(cache_bin_nstashed_get_local(&bin, &info) ==
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
ncached_max / 2, "Wrong nstashed value");
}
}
test_bin_init(&bin, &info);
do_flush_stashed_test(&bin, &info, ptrs, ncached_max, 0);
do_flush_stashed_test(&bin, &info, ptrs, 0, ncached_max);
do_flush_stashed_test(&bin, &info, ptrs, ncached_max / 2, ncached_max / 2);
do_flush_stashed_test(&bin, &info, ptrs, ncached_max / 4, ncached_max / 2);
do_flush_stashed_test(&bin, &info, ptrs, ncached_max / 2, ncached_max / 4);
do_flush_stashed_test(&bin, &info, ptrs, ncached_max / 4, ncached_max / 4);
}
TEST_END
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
int
main(void) {
Implement use-after-free detection using junk and stash. On deallocation, sampled pointers (specially aligned) get junked and stashed into tcache (to prevent immediate reuse). The expected behavior is to have read-after-free corrupted and stopped by the junk-filling, while write-after-free is checked when flushing the stashed pointers.
2021-10-19 08:33:15 +08:00
return test(test_cache_bin,
test_cache_bin_stash);
Redesign the cache bin metadata for fast path. Implement the pointer-based metadata for tcache bins -- - 3 pointers are maintained to represent each bin; - 2 of the pointers are compressed on 64-bit; - is_full / is_empty done through pointer comparison; Comparing to the previous counter based design -- - fast-path speed up ~15% in benchmarks - direct pointer comparison and de-reference - no need to access tcache_bin_info in common case
2019-08-10 13:12:47 +08:00
}
Reference in New Issue Copy Permalink