Jwmalloc: A Verified Memory Allocator for Mobile Devices

jwmalloc: A Verified Memory Allocator for Mobile Devices
Author	Jiawei Wang, Ming Fu, Ruixian Wang, Chao Xu, Jonas Oberhauser, Haibo Chen
Conference	USENIX OSDI
Year	2026

개요

이 논문은 기존 범용 동적 메모리 할당기의 설계가 모바일 workload의 잦은 memory reformatting, 큰 peak–trough memory swing, 공격적인 reclaim, 높은 thread oversubscription과 왜 맞지 않는지를 밝히고, uniform slab, closed sibling tree, lifetime-aware reclamation, non-blocking interface를 결합한 jwmalloc로 CPU·전력·메모리·tail latency를 함께 개선하였다.

Motivation

모바일기기에서 Allocator의 성능은 사용가가 보는 응답에 직접 영향을 준다. 따라서 모바일 기기는 제한된 리소스인 CPU, Enenergy, Low memory overhead를 Low tail latency와 함께 제공해야 한다. 논문에서는 jemalloc이 안드로이드에서는 8.2%, 하모니 OS에서는 12.4%의 instruction cycles를 차지한다고 리포트 하였다.

저자들은 기존 allocator와 모바일 workload 사이에서 네 가지 mismatch가 있다고 주장한다.

Frequent memory reformatting -> Size-class reuse overhead: 시간에 따라 지배적인 object size가 빠르게 바뀌지만 전체 in-use memory는 비교적 일정하다. size class마다 slab 크기가 다른 jemalloc은 freed memory를 다른 class에 재사용할 때 backend subdivision/coalescing을 반복해야 한다.
Large peak–trough swing -> Metadata overhead: foreground/background 전환과 bursty interaction 때문에 peak memory가 steady-state보다 크게 높다. 관찰한 graphics service에서는 peak가 steady-state의 5배를 넘었다. peak에 맞춰 커진 grow-only metadata는 수요가 내려간 뒤에도 남는다.
Aggressive reclamation -> System call overhead: server에서는 5–15초인 reclaim delay가 모바일에서는 흔히 1초 이하이다. 너무 빨리 page를 OS에 돌려주면 곧 free될 이웃 range와의 coalescing 기회를 잃고 system call을 반복하지만, 무조건 늦추면 footprint가 증가한다.
High oversubscription -> High parallelism requirement: 한 app-market scenario에서 8 core 위에 123 process와 742 thread가 실행되었다. lock을 잡은 thread가 deschedule되면 UI thread까지 기다리는 Priority inversion이 생길 수 있으며, producer–consumer workload에서 흔한 cross-thread free가 이 위험을 키운다.

Background

Memory Allocator는 대체로 small object를 slab에서 처리하는 frontend와, OS page 단위 virtual-memory range를 관리하며 slab 및 large object에 memory를 공급하는 backend로 나뉜다. jwmalloc은 4KB OS page 환경에서 2KB 미만을 thread-local frontend, 2–16KB를 process-wide slab-style midend, 16KB–4MB를 backend, 4MB 초과를 direct system call로 처리한다.

그러나, 모바일 allocation demand는 서버랑 다르게, 단순히 “작은 object가 많다”가 아니라, size별 demand가 빠르게 이동하고, page lifetime이 양극화되며, 적은 core에 많은 thread가 몰린다는 것이다.

따라서, 기존의 방식은 모바일 시스템에서 다음과 같은 4개의 문제가 있었다.

CPU cost와 Slab관리로 인한 메모리 오버헤드의 Trade-off측면: Size-class를 관리하기 위한 CPU overhead가 크기 때문에 Frequent memory reformatting상황에서 CPU utilization이 커진다.
OS에서 받아오는 Larger-size 단계의 존재: OS에서 메모리를 받아와서 각 size class별로 나누어 쓰기 때문에 Peak Memory상황에서 이 Two-level policy를 위한 Metadata의 Memory Overhead와 Division을 위한 CPU Utilization이 커진다.
Memory reclamation policy가 Lifetime을 고려하지 않음: 이를 통해서 모바일 시스템에서는 Reclamation이 너무 빨라져서 추가적인 오버헤드가 발생함
Coarse-grained lock을 통한 메타데이트 관리: High oversubscription이 자주 발생하는 모바일 환경에서는 적합하지 않은 디자인

Main Idea

Uniform and Pooled Slab Frontend: 모든 Slab이 같은 사이즈를 가지게 하였다.
Size-class-exact range backend:
Lifetime-based reclamation
Non-blocking interfaces
Verification under WMMs

Design

Uniform and Pooled Slab Frontend: Local problem: heterogeneous slab은 per-slab tail waste를 줄이지만 size demand가 바뀔 때 다른 크기의 slab로 즉시 바꿀 수 없어 backend churn을 만든다. 반대로 큰 uniform slab은 object 하나가 남아도 slab 전체가 pinned되는 footprint 문제가 있다.; Mechanism: half-page 이하 size class에 한 OS page(4KB)의 uniform slab을 사용하고, slab 크기를 바꾸는 대신 size class를 조절하여 tail fragmentation cap을 맞춘다. 완전히 빈 slab은 per-thread shared pool에 plain memory로 보관했다가 어느 frontend class로든 reinitialize한다. pool은 total slab count에 비례한 watermark와 LRU 정책으로 제한한다.; Why it helps / tradeoff: coalescing 없이 class 간 즉시 재사용할 수 있고 common-path instruction 수가 줄어든다. 다만 page에 가까운 size에서는 uniform slab의 이점이 약해지므로, 2–16KB object는 별도의 process-wide midend가 담당한다.
Size-Class-Exact Range Backend: Local problem: fixed-granularity backend는 size class에 속하지 않아 request를 직접 만족하지 못하는 intermediate range를 만들고, eager coalescing은 곧 다시 split할 range까지 합쳐 CPU를 낭비한다.; Mechanism: larger range를 요청된 class와 나머지 valid class들로 eagerly subdivide하되, adjacent free range는 합친 결과 역시 valid size class일 때만 on demand coalesce한다. 각 root range는 resolution-3 closed sibling tree로 표현된다. 모든 node의 weight가 size-class 집합에 속하고, contiguous sibling들의 어떤 부분합도 다시 valid class가 되도록 tree를 구성한다.; Why it helps / invariant: backend가 유지하는 모든 range가 직접 사용할 수 있는 class 크기라는 invariant를 지켜 lookup과 반복 split/join을 줄인다. size-friendly multi-step split은 큰 contiguous remainder를 보존한다. 대신 binary buddy보다 tree construction과 concurrent state management가 복잡하다.
Reclaimable Per-Granule Metadata: Local problem: fine-grained allocator의 per-range metadata는 빠른 direct indexing이 어렵고, 재사용되는 metadata record가 historical peak 이후 줄지 않을 수 있다.; Mechanism: closed sibling tree metadata를 4KB granule당 12B로 압축하고, 2차원 tree를 1차원 array에 mapping한다. internal-node 정보를 leaf에 encode하고 explicit parent/sibling pointer 대신 range size, depth, sibling index에서 address offset을 계산하는 metadata shifting을 사용한다.; Why it helps / tradeoff: direct lookup을 유지하면서 root range가 모두 free되면 metadata도 반환할 수 있다. 그러나 compact representation은 구현 추론을 어렵게 하며, 실제로 verification이 root node의 잘못된 sibling access bug를 발견했다.
Lifetime-Based Reclamation: Local problem: fixed-delay reclaim은 곧 free될 이웃과 합칠 기회를 놓치거나, background 진입 후 allocator call이 줄어 reclaim 자체가 늦어질 수 있다. 모든 cached range의 timestamp를 scan하는 방식도 CPU가 든다.; Mechanism: mergeable sibling이 없는 free range는 countdown을 시작하고, sibling과 합쳐지면 이를 reset한다. mapped range의 size class마다 active/standby buffer를 두어 새로 free/coalesced된 range를 active에 넣는다. reclaim thread는 두 buffer를 swap하고 500ms를 기다린 뒤 standby의 physical page를 madvise로 버려 unmapped buffer로 옮긴다. cache가 watermark를 넘으면 freeing thread의 synchronous reclaim과 reclaim thread 조기 wakeup을 함께 사용한다.; Why it helps / tradeoff: long-lived allocation 옆의 free range부터 돌려주고 short-lived 이웃과 합쳐질 가능성이 있는 range에는 시간을 주며, per-range timestamp와 full scan을 피한다. 정책은 workload의 generational behavior와 interval/watermark 선택에 의존한다.
Non-Blocking Interface and Ownership Transfer: Local problem: cross-thread free나 shared backend metadata의 coarse lock은 oversubscription에서 unbounded waiting과 UI stutter를 만들 수 있다.; Mechanism: 각 size class는 bounded concurrent bitmap을 fast path로 쓰고, bitmap이 비거나 가득 차면 locked unbounded list를 시도한다. lock 획득에 실패한 allocation은 더 큰 class의 range를 얻어 subdivide하고, free는 concurrent deferred list에 넣어 이후 operation이나 reclaim thread가 처리한다. Nest(search structure)와 Knit(contiguous-range tree)의 ownership은 staged acquire/release, rollback, atomic sibling-state update로 이전한다.; Why it helps / tradeoff: public allocation/free path가 lock holder를 기다리지 않고 진행하지만, rare contention을 extra subdivision, deferred work, 짧은 memory waste로 바꾼다. 따라서 non-blocking은 “비용이 없음”이 아니라 latency bound를 위해 일시적 resource overhead를 선택한 것이다.
Bounded Verification under Weak Memory Models: jwmalloc을 frontend/midend/backend의 library-style interface로 분리하고, cross-thread free, buffer drain, thread 생성·종료 등 edge case별 small concurrent client를 작성한다. VSync toolchain으로 각 client가 허용하는 weak-memory execution을 모두 탐색하여 assertion, memory safety, data-race absence, loop termination을 검사한다. state space를 감당하기 위해 bitmap entry 같은 constant는 logic을 유지한 채 축소했으며, 각 client는 10분 안에 완료되도록 구성했다.

Result

Workload characterization

Android와 HarmonyOS의 real-world workload에서 jemalloc instruction 비율은 평균 8.2%와 12.4%였다.
graphics service는 burst 동안 약 3 million allocation operations/s에 도달했고, size별 activity는 시간에 따라 크게 변했다.
streaming workload의 page 중 90%는 33.55ms 안에 free되지만 1% 이상은 3.22초 넘게 유지되었다. cross-thread free 비율은 대개 낮아도 짧은 구간에 80%, 일부 producer–consumer workload에서는 거의 100%에 접근했다.

이 결과는 jwmalloc의 세 정책 선택, 즉 cross-class slab reuse, lifetime-aware reclaim, non-blocking cross-thread path가 synthetic corner case만 겨냥한 것이 아니라 관찰된 모바일 behavior에 대응함을 보여준다.

Microbenchmarks

4-core x86 server에서 mobile oversubscription을 모사하고 rptest, xmalloc, mstress, mleak를 실행했다. jwmalloc은 jemalloc보다 평균 74% 높은 performance와 약 82% 적은 allocator-side instruction을 보였다.
Frontend만 jwmalloc로 바꾸고 jemalloc backend를 유지한 jw+jemalloc도 일부 test에서 크게 빨라져 uniform/pooling frontend의 독립적 효과를 보였다. Full jwmalloc의 rptest-8B-1MB-N에서는 jemalloc, mimalloc, tcmalloc의 allocator instruction이 각각 jwmalloc의 32.8×, 2.55×, 1.81×였다.
Sleep-augmented mstress-10N에서 jwmalloc의 peak/steady footprint는 906MB/29MB였고 jemalloc은 968MB/376MB였다. jw+jemalloc의 footprint가 jemalloc과 비슷했다는 점은 steady-state 감소의 주된 원인이 backend 및 reclamation임을 지지한다.
Heavy oversubscription인 mstress-10N에서 jwmalloc의 P99.99 operation latency는 1.5µs로, 가장 좋은 경쟁 allocator의 5.9µs보다 낮았다.
단, allocation 분포가 4KB 근처에 몰린 8B–4KB/10N 설정에서는 uniform slab의 의도적 tradeoff와 fallback work 때문에 일부 performance/load regression이 있었다.

Real-world mobile scenarios

Huawei Mate 70 Pro(8-core ARMv8-A, 12GB RAM, HarmonyOS 5.1)에서 system jemalloc을 jwmalloc 또는 mimalloc로 교체하고, 32개 smartphone interaction으로 구성된 약 2시간 suite를 각 5회 실행했다.

jwmalloc을 1로 normalize했을 때 jemalloc과 mimalloc의 전체 device instruction은 평균 1.10×와 1.13×였다. user-space allocation-related instruction은 각각 3.84×와 4.79×, kernel-space allocation-related instruction은 1.14×와 1.12×였다.
Article reading과 video playback에서는 jemalloc 대비 instruction을 7–21%, CPU cluster power를 5–11%, LPDDR power를 2–3% 줄였다. 저자들은 CPU 절감을 lower voltage/frequency point 사용과 big core에서 small core로의 thread migration에 연결한다.
주요 system service의 PSS는 대체로 jemalloc과 비슷하거나 낮았고, mimalloc은 흔히 더 많은 memory를 사용했다.

즉, microbenchmark의 allocator-side instruction 절감이 한 기기의 whole-system load와 CPU power 감소로 이어졌으며, 그 과정에서 jemalloc 대비 footprint가 악화되지 않았다는 것이 논문의 핵심 end-to-end evidence이다.

Verification and deployment

Bounded model checker는 개발 중 closed sibling tree의 root에 sibling이 있다고 잘못 가정하여 특정 data 값에서 out-of-bounds read와 crash를 일으키는 unknown bug를 약 10초 만에 찾았다. 이는 weak-memory-aware verification이 실제 구현 결함을 발견할 수 있음을 보이지만, 설정된 client와 bound 안의 보장이다.

저자들은 jwmalloc이 smartphone, tablet, smartwatch를 포함한 1,200만 대의 상용 기기에 배포되어 300억 user-hour 이상 안정적으로 동작했다고 보고한다. 이는 production maturity의 강한 관찰 증거이지만 formal correctness를 대체하지는 않는다.

Contribution

모바일 allocation workload를 profile하여 frequent reformatting, peak–trough swing, aggressive reclamation, oversubscription이라는 네 가지 allocator mismatch를 정량화하였다.
One-page uniform slab과 cross-size-class empty-slab pooling으로 frontend의 reformatting 비용을 줄였다.
임의 resolution-R size-class 집합을 exact하게 표현하는 closed sibling tree, eager subdivision/on-demand coalescing, reclaimable per-granule metadata를 제안하였다.
Generational lifetime 관찰을 two-buffer tracker로 구현하여 timestamp/scan 없이 coalescing 기회와 timely reclaim을 조절하였다.
Backend ownership protocol과 fallback/defer path를 통해 oversubscription에서도 allocation/free interface를 non-blocking으로 만들었다.
Weak memory model 아래 bounded verification, microbenchmark ablation, real-device energy/footprint 평가, 대규모 production deployment를 함께 제시하였다.

Conclusion

본 연구는 모바일 환경에서의 Unique한 특성을 Memory allocator에 반영시킬때 어떠한 점을 고려해야 하고, 어떠한 디자인을 적용시킬 수 있는지 제시하였다. 그 결과 Jemalloc대비 훨씬 더 좋은 성능을 보였다. Allocator만 최적화하여 10%단위의 성능 향상을 꾀하기에는 매우 힘들기에, 제시한 디자인의 최적화가 매우 효과적임을 시사한다.

Minor comments

섹션 2.2의 의도가 논문 전체에서 어떤 역활인지 모르겠다. Secure allocator가 모바일 환경에서 중요하지 않다는 정보가 갑자기 등장해서 굳이라는 생각이 들었다.

Major comments

기존의 Size-class방식이 더 잘 작동하는 Workload가 어떤 것인지 제시되어 있지 않다. Size-class로 나누는 이유는 Metadata management의 용이성 + Long-runnning시의 Fragmentation관리 때문인데, 본 시스템이 Size-class를 없앰으로서 어떤 Cons를 가지는지 분석한 결과가 있었으면 더 Complete했을 듯 하다.