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: Problem: heterogeneous slab은 per-slab tail waste를 줄이지만 size demand가 바뀔 때 다른 크기의 slab로 즉시 바꿀 수 없다. 반대로 큰 uniform slab은 object 하나가 남아도 slab 전체가 pinned되는 footprint 문제가 있다.; Design: half-page 이하 size class에 한 OS page(4KB)의 uniform slab을 사용하고, slab 크기를 바꾸는 대신 size class를 가능한 딱 맞는 크기로 조절하여 최대한 4KB slab에 많은 오브젝트를 넣을 수 있도록 한다. 이를 통해서 tail fragmentation을 줄일 수 있다. 완전히 빈 slab은 per-thread shared pool에 plain memory로 보관했다가 어느 frontend class로든 reinitialize한다.; Why it helps / tradeoff: coalescing 없이 class 간 즉시 재사용할 수 있고 common-path instruction 수가 줄어든다. 다만 page에 가까운 size에서는 uniform slab의 이점이 약해지므로, 2–16KB object는 별도의 process-wide midend가 담당한다.

Size-Class-Exact Range Backend

저자들은 기존 메모리 할당자와 마찬가지로 R=3 resolution의 size-class set을 사용하여 allocation request의 rounding으로 인한 internal fragmentation을 제한한다. 그러나 기존 allocator의 backend는 이러한 size classes와 별개로 memory ranges를 관리한다. 예를 들어 jemalloc과 tcmalloc은 각각 4KB와 8KB 단위로 range를 split/coalesce하기 때문에 실제 size class에 해당하지 않는 intermediate-sized free ranges가 다수 생성될 수 있다. 저자들은 이러한 intermediate ranges를 없애기 위해, backend에서 관리되는 모든 range의 크기가 항상 size-class set에 속하도록 하는 size-class-exact range management를 제안한다. 이를 위해서 Closed Sibliing Tree와 Per-Granule Metadata with Metadata shifting을 이용한 Eager subdivision과 On-demand coalescing을 제시하였다.

Closed Sibling Tree: Backend에서 관리하는 모든 range의 크기를 size class에 정확히 맞추기 위해, 저자들은 기존 buddy allocator의 일반화된 형태인 Closed Sibling Tree를 제안한다. Classical buddy allocator는 (2^k) 크기의 range만 표현할 수 있고, weighted buddy나 dual buddy와 같은 변형도 (2^k)와 (3\times2^k) 등 제한된 크기만 지원하므로, 임의의 resolution-(R) size-class set을 정확히 표현할 수 없다. Closed Sibling Tree는 각 node와 subdivision으로 생성되는 모든 child의 크기가 size class에 속하도록 구성함으로써, 임의의 resolution-(R) size-class set을 backend range로 표현할 수 있도록 한다.

Reclaimable Per-Granule Metadata: Closed Sibling Tree를 일반적인 pointer-based tree로 저장하면 metadata overhead가 커지므로, 저자들은 4KB granule마다 12B의 작은 metadata entry를 두고 이를 1차원 배열로 관리한다. Parent나 sibling을 가리키는 pointer를 직접 저장하는 대신, 각 node의 크기와 tree 내 위치 정보를 이용해 대상 node가 현재 위치에서 몇 개의 metadata entry만큼 떨어져 있는지를 계산한다. 저자들은 이러한 pointer-free tree traversal 방식을 metadata shifting이라 명명하였다.

Lifetime-Based Reclamation: free range의 나이뿐 아니라 향후 sibling과 coalesce될 가능성을 고려해 reclamation 순서를 정하고, 이를 active/standby 두 buffer만으로 근사하였다.

Non-Blocking Interface and Ownership Transfer: shared allocator state에 대한 lock 경쟁이 발생하면 기다리지 않고, allocation은 다른 larger range를 임시로 이용하고 free는 deferred list로 미룸으로써 UI thread 등의 allocator-induced blocking을 방지하였다.

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을 검사하였다.

Result

Workload characterization

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이 있었다.

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

Contribution

모바일 allocation workload를 profile하여 frequent reformatting, peak–trough swing, aggressive reclamation, oversubscription이라는 네 가지 allocator mismatch를 제시하였다.
화웨이 휴대폰 사용자를 대상으로 Mass-test를 진행하여서 Allocator가 효과적으로 성능 향상을 보임을 실증하였다.

Conclusion

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

Minor comments

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

Major comments

기존의 Size-class방식이 더 잘 작동하는 Workload가 어떤 것인지 제시되어 있지 않다. Size-class로 나누는 이유는 Metadata management의 용이성 + Long-runnning시의 Fragmentation관리 때문인데, 본 시스템이 Size-class를 없앰으로서 어떤 Cons를 가지는지 분석한 결과가 있었으면 더 Complete했을 듯 하다.
본 논문의 Motivation은 잘 알려진 부분이고, 또한 Design이 Collection of optimization이라는 점은, 본 논문의 Novelty측면에서 다른 Work들 대비 제한적이게 만드는 요소라고 생각한다. 그러나 Memory Allocator을 본 연구처럼 기존 대비 성능 향상을 10%단위로 보일정도로 최적화 하는 연구는 (1) 생각보다 매우 어렵고 (2) 필연적으로 Optimization work이라는 점을 고려하였을때, 중요한 Memory Allocator연구라고 생각한다.