This was a memory allocator made for the vrig group as a fun internal competion seeing who could make the best memory allocator - enjoy !
The SHARE_RD, allocator is a 3 tiered allocator based on the fundamental idea that we, allocate a lot of OS VM memory during initializations and have very fast allocations after that.
Its overall design is a mix of several modern allocators with a good bit of inspirations from Google's TC allocator. Which also has a similar choice of tier allocations paths,
though the Google general purpose allocator does quite a bit more processing to decide how certain things in its primary fast path can be stored (lots of sampling). The name of the allocator
is based on an amazing joke where I kept calling a friend of mine Shard for like 3 hours lol.
some funny results:
Allocator Workload Throughput p50 p99 p999 RSS
(ops/sec) (ns) (ns) (ns) (KB)
share_rdalloc WL-SYN-001 4.73e+07 20 31 41 5832
share_rdalloc WL-SYN-002 3.98e+07 30 31 50 14024
share_rdalloc WL-SYN-003 4.01e+07 30 41 60 16072
share_rdalloc WL-SYN-004 3.72e+07 30 41 60 26184
share_rdalloc WL-SYN-005 4.17e+07 30 31 31 26188
share_rdalloc WL-SYN-006 3.42e+07 30 41 41 29908
share_rdalloc WL-SYN-007 3.03e+07 30 50 70 31972
share_rdalloc WL-SYN-008 3.36e+07 40 51 70 31972
share_rdalloc WL-SYN-009 3.14e+07 30 31 50 31972
share_rdalloc WL-SYN-010 2.42e+07 40 60 61 31972
Test Suite: Correctness
Allocator: share_rdalloc (0.1.0)
[TC-BASIC-001] malloc single allocation... PASS
[TC-BASIC-002] free single allocation... PASS
[TC-BASIC-003] malloc/free cycle... PASS
[TC-BASIC-004] free(NULL) is no-op... PASS
[TC-BASIC-005] malloc(0) behavior... PASS
[TC-SIZE-001] sizes 1-256 bytes... PASS
[TC-SIZE-002] sizes 256B-64KB... PASS
[TC-SIZE-003] sizes 64KB-16MB... PASS
[TC-SIZE-004] sizes 16MB-256MB... PASS
[TC-SIZE-005] sizes near SIZE_MAX... PASS
[TC-SIZE-006] tier and size-class boundaries... PASS
[TC-ALIGN-001] 16-byte alignment... PASS
[TC-ALIGN-002] memalign power-of-2... PASS
[TC-ALIGN-003] memalign 4KB page... PASS
[TC-REALLOC-001] grow allocation... PASS
[TC-REALLOC-002] shrink allocation... PASS
[TC-REALLOC-003] realloc(NULL, n)... PASS
[TC-REALLOC-004] realloc(ptr, 0)... PASS
[TC-REALLOC-005] realloc same size... PASS
[TC-REALLOC-006] contents preserved grow... PASS
[TC-REALLOC-007] contents preserved shrink... PASS
[TC-REALLOC-008] realloc aligned memory... PASS
[TC-CALLOC-001] zero initialization... PASS
[TC-CALLOC-002] overflow SIZE_MAXx2... PASS
[TC-CALLOC-003] overflow (SIZE_MAX/2+2)x2... PASS
[TC-CALLOC-004] large array... PASS
[TC-USABLE-001] usable_size >= requested... PASS
[TC-USABLE-002] write full usable size... PASS
Test Suite: Stress
Allocator: share_rdalloc (0.1.0)
Completed 1000000 ops
PASS
Completed 1000000 ops
PASS
Completed 1000000 ops
PASS
Completed 1000 realloc chains
PASS
Completed 100 peak cycles ...
PASS
Completed 100K simultaneous allocs
PASS
[TC-STRESS-THREAD-02] producer-consumer threads... PASS
[TC-STRESS-THREAD-003] same-size threaded hammer... PASS
[TC-STRESS-THREAD-004] mixed-size threaded hammer... PASS
[TC-STRESS-OOM-001] oom recovery... PASS
Test Suite: Edge Cases
Allocator: share_rdalloc (0.1.0)
[TC-EDGE-001] malloc(SIZE_MAX)... PASS
[TC-EDGE-002] malloc(SIZE_MAX - 4096)... PASS
Completed 100K 1-byte allocations
PASS
[TC-EDGE-004] page boundary allocations... PASS
[TC-EDGE-005] init/teardown cycles... PASS
[TC-EDGE-006] alternating small/large... PASS
[TC-EDGE-007] exact power-of-2 sizes... PASS
[TC-EDGE-008] size class boundaries... PASS
[TC-EDGE-009] zero-size calloc... PASS
[TC-EDGE-010] realloc doubling pattern... PASS
[TC-EDGE-011] invalid free behavior... PASS
[TC-EDGE-012] double init behavior... PASS
[TC-EDGE-FORK-001] fork safety check... PASS
Test Suite: Fragmentation
Allocator: share_rdalloc (0.1.0)
Swiss cheese pattern test passed ap...
PASS
Cycle 9: peak RSS=18492 KB, post-free RSS=18492 KB
Baseline: 12224 KB, Final: 18492 KB, Max: 18492 KB
PASS
Progress: 90000/100000, RSS=28732 KB
Baseline: 18492 KB, Final: 28732 KB
PASS
Op 450000/500000: live=9796, RSS=41608 KB
Baseline: 28732 KB, Max: 41608 KB, Final: 41608 KB
PASS
[TC-FRAG-005] medium-tier fragmentation... PASS
[TC-FRAG-006] large-tier fragmentation... PASS
Test Suite: Optional Features
Allocator: share_rdalloc (0.1.0)
[TC-FEAT-THREAD-001] basic thread safety... PASS
[TC-FEAT-ZERO-001] zero-on-free check... SKIP
[TC-FEAT-QUAR-001] quarantine delay reuse... SKIP
[TC-FEAT-CANARY-001] canary overflow detect... SKIP
[TC-FEAT-GUARD-001] guard page access check... SKIP
[TC-FEAT-HUGE-001] huge page allocation... PASS
[TC-FEAT-PTCACHE-001] per-thread cache check... PASS
[TC-SEC-DBLFREE] double free detection... PASS
[TC-SEC-CORRUPT] metadata corruption (header)... PASS
[TC-SEC-SPIRIT] house of spirit (stack free)... PASS
[TC-SEC-LORE] house of lore (poisoning)... PASS
[TC-SEC-FORCE] house of force (top size)... PASS
Test Suite: Realistic Workloads
Allocator: share_rdalloc (0.1.0)
[WL-REAL-001] Redis YCSB workload trace... PASS
[WL-REAL-002] SQLite TPC-C trace... PASS
[WL-REAL-003] Firefox Page load trace... PASS
[WL-REAL-004] Custom Application-burst workload... PASS
[WL-REAL-005] Non-Standard Allocations... PASS
[WL-REAL-006] Pseudo-SIMD allocations... PASS
[WL-REAL-007] Mixed lifetime workload... PASS
OVERALL RESULTS
Summary: 76 total, 72 passed, 0 failed, 4 skipped
Allocator Workload Throughput p50 p99 p999 RSS
(ops/sec) (ns) (ns) (ns) (KB)
glibc WL-SYN-001 4.50e+07 20 31 50 3776
glibc WL-SYN-002 4.41e+07 20 31 50 3776
glibc WL-SYN-003 3.64e+07 30 41 60 3776
glibc WL-SYN-004 3.15e+07 40 41 60 3776
glibc WL-SYN-005 3.56e+07 30 50 70 3780
glibc WL-SYN-006 2.88e+07 30 60 291 7092
glibc WL-SYN-007 2.11e+07 30 70 4228 7096
glibc WL-SYN-008 2.36e+07 60 61 110 7096
glibc WL-SYN-009 2.70e+07 30 31 31 7096
glibc WL-SYN-010 1.59e+07 60 110 140 7096
dudcom@spl make test-glibc
rm -f build/allocator.o
make run-tests ALLOCATOR=allocators/glibc/glibc_allocator.c
make[1]: Entering directory '/home/dudcom/allocator-project/allocator-project-template'
cc -std=c17 -Wall -Wextra -Wpedantic -Werror -fno-strict-aliasing -D_GNU_SOURCE -I./include -O2 -g -c -o build/allocator.o allocators/glibc/glibc_allocator.c
cc -std=c17 -Wall -Wextra -Wpedantic -Werror -fno-strict-aliasing -D_GNU_SOURCE -I./include -O2 -g -o bin/run_tests build/src/tests/test_correctness.o build/src/tests/test_stress.o build/src/tests/test_edge.o build/src/tests/test_fragmentation.o build/src/tests/test_features.o build/src/tests/test_realistic.o build/src/harness/main_tests.o build/allocator.o -lm -lpthread
Built test runner: bin/run_tests
Allocator: allocators/glibc/glibc_allocator.c
Running tests...
./bin/run_tests
Allocator Test Suite v1.0.0
Testing: glibc vbaseline by GNU
Backend: glibc-internal
Description: Standard glibc malloc wrapper for baseline testing
Features:
Thread-safe: yes
Per-thread cache: yes
Huge pages: no
Guard pages: no
Canaries: no
Quarantine: no
Zero-on-free: no
Alignment: 16 - 4096 bytes
Test Suite: Correctness
Allocator: glibc (baseline)
[TC-BASIC-001] malloc single allocation... PASS
[TC-BASIC-002] free single allocation... PASS
[TC-BASIC-003] malloc/free cycle... PASS
[TC-BASIC-004] free(NULL) is no-op... PASS
[TC-BASIC-005] malloc(0) behavior... PASS
[TC-SIZE-001] sizes 1-256 bytes... PASS
[TC-SIZE-002] sizes 256B-64KB... PASS
[TC-SIZE-003] sizes 64KB-16MB... PASS
[TC-SIZE-004] sizes 16MB-256MB... PASS
[TC-SIZE-005] sizes near SIZE_MAX... PASS
[TC-SIZE-006] tier and size-class boundaries... PASS
[TC-ALIGN-001] 16-byte alignment... PASS
[TC-ALIGN-002] memalign power-of-2... PASS
[TC-ALIGN-003] memalign 4KB page... PASS
[TC-REALLOC-001] grow allocation... PASS
[TC-REALLOC-002] shrink allocation... PASS
[TC-REALLOC-003] realloc(NULL, n)... PASS
[TC-REALLOC-004] realloc(ptr, 0)... PASS
[TC-REALLOC-005] realloc same size... PASS
[TC-REALLOC-006] contents preserved grow... PASS
[TC-REALLOC-007] contents preserved shrink... PASS
[TC-REALLOC-008] realloc aligned memory... PASS
[TC-CALLOC-001] zero initialization... PASS
[TC-CALLOC-002] overflow SIZE_MAXx2... PASS
[TC-CALLOC-003] overflow (SIZE_MAX/2+2)x2... PASS
[TC-CALLOC-004] large array... PASS
[TC-USABLE-001] usable_size >= requested... PASS
[TC-USABLE-002] write full usable size... PASS
Test Suite: Stress
Allocator: glibc (baseline)
Completed 1000000 ops
PASS
Completed 1000000 ops
PASS
Completed 1000000 ops
PASS
Completed 1000 realloc chains
PASS
Completed 100 peak cycles ...
PASS
Completed 100K simultaneous allocs
PASS
[TC-STRESS-THREAD-02] producer-consumer threads... PASS
[TC-STRESS-THREAD-003] same-size threaded hammer... PASS
[TC-STRESS-THREAD-004] mixed-size threaded hammer... PASS
[TC-STRESS-OOM-001] oom recovery... PASS
Test Suite: Edge Cases
Allocator: glibc (baseline)
[TC-EDGE-001] malloc(SIZE_MAX)... PASS
[TC-EDGE-002] malloc(SIZE_MAX - 4096)... PASS
Completed 100K 1-byte allocations
PASS
[TC-EDGE-004] page boundary allocations... PASS
[TC-EDGE-005] init/teardown cycles... PASS
[TC-EDGE-006] alternating small/large... PASS
[TC-EDGE-007] exact power-of-2 sizes... PASS
[TC-EDGE-008] size class boundaries... PASS
[TC-EDGE-009] zero-size calloc... PASS
[TC-EDGE-010] realloc doubling pattern... PASS
[TC-EDGE-011] invalid free behavior... PASS
[TC-EDGE-012] double init behavior... PASS
[TC-EDGE-FORK-001] fork safety check... PASS
Test Suite: Fragmentation
Allocator: glibc (baseline)
Swiss cheese pattern test passed ap...
PASS
Cycle 9: peak RSS=20972 KB, post-free RSS=20972 KB
Baseline: 20884 KB, Final: 20972 KB, Max: 20972 KB
PASS
Progress: 90000/100000, RSS=20972 KB
Baseline: 20972 KB, Final: 20972 KB
PASS
Op 450000/500000: live=9796, RSS=23928 KB
Baseline: 20972 KB, Max: 23928 KB, Final: 24076 KB
PASS
[TC-FRAG-005] medium-tier fragmentation... PASS
[TC-FRAG-006] large-tier fragmentation... PASS
Test Suite: Optional Features
Allocator: glibc (baseline)
[TC-FEAT-THREAD-001] basic thread safety... PASS
[TC-FEAT-ZERO-001] zero-on-free check... SKIP
[TC-FEAT-QUAR-001] quarantine delay reuse... SKIP
[TC-FEAT-CANARY-001] canary overflow detect... SKIP
[TC-FEAT-GUARD-001] guard page access check... SKIP
[TC-FEAT-HUGE-001] huge page allocation... SKIP
[TC-FEAT-PTCACHE-001] per-thread cache check... PASS
[TC-SEC-DBLFREE] double free detection... free(): double free detected in tcache 2
PASS
[TC-SEC-CORRUPT] metadata corruption (header)... PASS
[TC-SEC-SPIRIT] house of spirit (stack free)...
[CRITICAL] House of Spirit Succeeded! Stack ptr 0x7ffd68dafd10 freed.
FAIL
[TC-SEC-LORE] house of lore (poisoning)... PASS
[TC-SEC-FORCE] house of force (top size)... PASS
Test Suite: Realistic Workloads
Allocator: glibc (baseline)
[WL-REAL-001] Redis YCSB workload trace... PASS
[WL-REAL-002] SQLite TPC-C trace... PASS
[WL-REAL-003] Firefox Page load trace... PASS
[WL-REAL-004] Custom Application-burst workload... PASS
[WL-REAL-005] Non-Standard Allocations... PASS
[WL-REAL-006] Pseudo-SIMD allocations... PASS
[WL-REAL-007] Mixed lifetime workload... PASS
OVERALL RESULTS
Summary: 76 total, 70 passed, 1 failed, 5 skipped
Allocations: 671057
Frees: 671091
Reallocs: 0
Bytes in use: 72
Total alloc'd: 4236683190