noriwiki - 최근 바뀜 [ko]

MDK: Rethinking the data center memory reclamation problem

Ahn9807 — Fri, 04 Sep 2026 02:37:49 GMT

차이 보기

MDK: Rethinking the data center memory reclamation problem

Noribot — Thu, 03 Sep 2026 04:23:16 GMT

Nori: update draft.wikitext

차이 보기

MDK: Rethinking the data center memory reclamation problem

Noribot — Thu, 03 Sep 2026 04:12:30 GMT

Nori: update draft.wikitext

새 문서

{{Paper
|title=MDK: Rethinking the data center memory reclamation problem
|author=Shaurya Patel, Suli Yang, Yawen Wang, Kan Wu, Alexandra (Sasha) Fedorova, Margo Seltzer, Kimberly Keeton
|conference=20th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2026)
|year=2026
}}

== 개요 ==

이 논문은 [[데이터 센터]]의 proactive [[Memory reclamation]]을 고정 크기 메모리에서 miss를 최소화하는 전통적 [[Page replacement]]와 다른 최적화 문제로 재정의하고, 성능 [[Service Level Objective|SLO]]를 지키면서 평균 메모리 절감량을 최대화하는 정책을 설계·평가하기 위한 offline toolkit인 '''Memory Designer's Kit (MDK)'''를 제안한다.

== Background ==

{| class="wikitable"
! 구분
! 전통적 page replacement
! 데이터 센터 memory reclamation
|-
! 목표와 제약
| 고정된 cache 크기에서 전체 실행의 miss ratio 최소화
| 모든 측정 window의 성능 proxy 한도를 지키면서 평균 메모리 절감량 최대화
|-
! 동작 시점
| 메모리 pressure가 발생한 뒤 reactive eviction
| 새 job을 배치할 여유를 만들기 위한 proactive reclamation
|-
! 대표 지표
| 전체 실행에 걸친 cache miss ratio
| window별 promotion rate, [[Pressure Stall Information|PSI]], Secondary Tier Access Ratio (STAR)
|-
! 설계 도구
| OPT와 [[Miss Ratio Curve|MRC]]
| OPP와 [[Memory Performance Curve|MPC]]
|}

이 논문이 주로 사용하는 '''promotion rate'''는 한 time window에서 발생한 non-compulsory page fault 수를 그 window에서 접근한 unique page 수로 정규화한 값이다. [[g-swap]]은 이 값을 2분마다 측정하며, 논문의 Cassandra/YCSB 실험에서는 promotion rate가 window별 tail latency와 함께 증가했다. 따라서 저자들은 이를 trace에서 계산할 수 있는 SLO-aligned proxy로 선택한다. 최적화 목표는 시간에 따른 '''평균 메모리 절감량'''이다.

== Motivation ==

[[DRAM]] 비용 때문에 서버당 더 많은 job을 수용하는 것은 데이터 센터의 total cost of ownership과 직결된다. 이를 위해 [[g-swap]]이나 [[TMO]] 같은 시스템은 cold page를 compressed memory, SSD, 또는 [[Compute Express Link|CXL]] 기반의 저렴한 tier로 미리 내보낸다. 이때 절감된 메모리는 cluster scheduler가 새 job을 배치할 만큼 오래 유지되어야 하고, reclamation 때문에 application SLO가 깨져서도 안 된다.

하지만 기존 도구는 이 목적에 맞지 않는다. [[Belady's algorithm|OPT]]와 VMIN은 전체 miss 수를 최소화할 수 있어도, 여러 page의 재접근과 fault를 같은 window에 몰아 promotion-rate 한도를 위반할 수 있다. MRC 역시 고정 cache 크기와 miss ratio의 관계를 나타내므로, 시간이 지나며 크기가 변하고 다양한 성능 proxy를 사용하는 reclamation policy를 비교하기 어렵다. 즉, 문제의 목표와 제약이 뒤집혔는데도 policy 설계 workflow에는 이에 대응하는 optimal bound, 비교 곡선, 빠른 탐색법이 없었다.

== Importance ==

이 논문의 연구적 가치는 새로운 reclamation heuristic 하나보다 '''정책 설계 문제의 좌표계를 바꾼 것'''에 있다. 전통적 caching 연구가 “주어진 용량에서 miss를 얼마나 줄일 수 있는가”를 물었다면, MDK는 “각 window의 성능 budget 안에서 메모리를 얼마나 더 내놓을 수 있는가”를 묻는다. 이에 맞춰 optimal oracle, policy curve, 이론적 nesting property, curve 생성기를 한 workflow로 제공한다.

또한 optimal policy를 실제 배포 대상으로 제시하는 데 그치지 않고, 기존 AGE policy의 headroom을 정량화하고 그 oracle의 결정을 PAW, PACE, L-OPP로 근사하는 과정을 보인다. 따라서 MDK는 characterization, upper-bound 분석, heuristic 설계, parameter 탐색을 연결하는 '''memory-policy design methodology'''로 기억할 가치가 있다.

== Main Idea ==

핵심 통찰은 reclamation policy가 miss의 총량만 보지 말고, '''미래의 각 time window가 허용하는 promotion budget을 first-class constraint로 취급해야 한다'''는 것이다. 같은 수의 page fault라도 한 window에 집중되면 SLO proxy를 위반할 수 있다. 반대로 미래 fault를 여러 window의 budget에 분산하면서 page를 가능한 한 일찍 reclaim하면, 제약을 지키면서 page가 DRAM 밖에 머무는 시간을 최대화할 수 있다.

MDK는 이 통찰을 네 도구로 구체화한다. MPC는 promotion rate와 평균 메모리 절감량의 tradeoff를 보여주고, OPP는 달성 가능한 최적 upper bound를 제공한다. Eviction decisions와 eviction times property는 여러 parameter setting의 결과가 어떻게 포함되는지를 나타내며, efficient MPC generator는 이 구조를 이용해 모든 setting을 각각 simulation하지 않고 trace를 linear time에 처리한다.

== Design ==

# '''Memory Performance Curve (MPC)'''
#* '''Local problem:''' MRC의 cache size–miss ratio 축은 가변 크기 reclamation과 window별 성능 제약을 표현하지 못한다.
#* '''Mechanism:''' x축에 target performance proxy(논문에서는 promotion rate), y축에 memory optimization goal(평균 메모리 절감량)을 둔다. 가능한 operating point가 연속적이라고 보장할 수 없으므로 선으로 잇지 않고 scatter plot으로 나타낸다.
#* '''효과와 tradeoff:''' 동일한 성능 budget에서 policy를 비교하고, 원하는 절감량에 필요한 성능 degradation을 찾을 수 있다. 다만 curve의 의미는 선택한 proxy와 workload trace에 종속된다.
# '''Optimal Performance Proxy (OPP)'''
#* '''Local problem:''' OPT와 VMIN은 미래 fault의 window별 집중을 고려하지 않는다.
#* '''Mechanism:''' 첫 pass에서 각 window의 unique accessed-page 수를 계산한다. 두 번째 pass에서는 page의 다음 접근 window를 미리 알고, 그 page가 만들 promotion을 추가해도 해당 window의 target rate를 넘지 않을 때 현재 접근 직후 즉시 reclaim한다. 각 미래 window별 예정 promotion 수를 갱신해 budget을 예약한다.
#* '''효과와 invariant:''' 허용된 fault slot을 지키면서 page를 가장 이른 시점에 내보내므로 평균 절감량을 최대화한다. Access-bit scan처럼 한 window 안의 접근 시각을 동일하게 취급한 trace에서는 first-difference argument로 optimal임을 보인다. 미래 접근을 요구하므로 OPP 자체는 offline oracle이다.
# '''Eviction decisions / eviction times properties'''
#* '''Local problem:''' parameter마다 policy를 독립 simulation하면 탐색 비용이 크다.
#* '''Mechanism:''' 더 aggressive한 setting이 덜 aggressive한 setting의 모든 eviction decision을 포함하면 eviction decisions property를 만족한다. 그 eviction들이 같은 시각에도 발생하면 더 강한 eviction times property를 만족한다. 각 접근에는 eviction을 처음 유발하는 least-aggressive '''critical parameter'''를 배정한다.
#* '''효과와 tradeoff:''' critical setting의 promotion과 saving만 계산한 뒤 더 aggressive한 setting으로 누적할 수 있다. VMIN과 OPP는 두 property를 모두 만족하지만, AGE는 eviction decision만 포함하고 더 aggressive할수록 더 일찍 reclaim하므로 시간 property는 만족하지 않는다.
# '''Efficient MPC generator'''
#* '''Local problem:''' trace마다 수많은 parameter를 simulation하는 방식은 정책 탐색을 느리게 만든다.
#* '''Mechanism:''' policy가 제공하는 parameter space, aggression order, critical parameter, per-access saving, saving accumulation 함수를 공통 template에 끼운다. Promotion과 saving을 critical parameter에 기록하고 aggression order를 따라 누적하여 전체 MPC를 만든다.
#* '''효과와 tradeoff:''' single-parameter policy의 생성은 trace 길이에 대해 linear time이며, 구현된 policy-specific code는 87 LOC 이하였다. 기본 template은 eviction decisions property를 만족하는 single-parameter policy를 대상으로 하며, two-parameter PACE에는 suffix-sum dynamic programming 기반의 약 300 LOC 전용 generator가 필요하다.
# '''OPP에서 유도한 practical policies'''
#* '''PAW (Prior Age with Wait):''' 직전 두 접근 사이의 reuse distance가 threshold ''P''보다 크고 마지막 접근 후 1분이 지나면 reclaim한다. OPP처럼 접근에 가까운 시점에 내보내되 hot page의 즉시 재회수를 막는다. 반복 access pattern에는 유리하지만 과거 reuse distance가 미래를 예측하지 못하면 AGE보다 나쁘다.
#* '''PACE (Prior Age and Current Elapsed):''' prior reuse distance가 ''P''보다 크면 즉시 reclaim하고, 그렇지 않으면 마지막 접근 뒤 ''A'' interval 동안 idle일 때 AGE처럼 reclaim한다. ''P''를 무한대로 두면 AGE로 퇴화하므로 offline 최적 parameter에서는 AGE보다 나쁘지 않지만, 두 parameter를 unseen workload에서 정하는 문제가 남는다.
#* '''L-OPP (Learned OPP):''' OPP의 2% target 결정을 label로 삼고 page별 최근 reuse distance 6개를 feature로 하는 gradient-boosted tree를 workload별로 학습한다. 미래 정보 없이 oracle을 모방할 가능성을 보이지만, model precision이 낮으면 promotion constraint를 지키지 못한다.

== Result ==

=== MPC의 정확도와 생성 비용 ===

저자들은 [[CloudSuite]]와 [[DCPerf]]의 8개 workload(Cassandra, Memcached, GraphX, NGINX, TaoBench, DjangoBench, FeedSim, MediaWiki)에서 30초 주기로 page-table access bit를 scan했다. Trace는 11–120분, application memory는 820 MB–160 GB 범위였다.

* Single-parameter policy의 10개 setting과 PACE의 15개 setting을 simulation과 대조했을 때 모든 MPC의 mean absolute error는 rounding 차이로 인해 1% 이내였다.
* 가장 느린 OPP에서도 모든 parameter의 MPC 생성은 0.4–583.2초가 걸렸고, 10개 parameter를 순차 simulation한 기준보다 '''12.5–208배''' 빨랐다. 저자들은 이를 linear-time generator와 quadratic-time simulation의 차이로 설명한다.

=== Optimal headroom과 새 policy ===

* OPP는 모든 workload와 promotion rate에서 가장 높은 평균 메모리 절감량을 보였다. Cassandra에서는 promotion rate 1% 미만에서 약 40%를 절감한 반면, VMIN은 10%까지 허용해도 같은 절감량에 도달하지 못했다. 이는 window budget을 직접 고려하는 결정의 headroom을 보여준다.
* PAW는 access pattern이 예측 가능한 GraphX, NGINX, TaoBench에서 AGE보다 최대 10% 더 많은 메모리를 절감했지만, Memcached와 FeedSim처럼 과거 pattern이 약한 workload에서는 AGE가 크게 앞섰다.
* PACE의 best configuration은 대부분의 workload에서 AGE보다 1–4% 더 절감했고 Cassandra와 GraphX에서는 8–10% 개선했다. 단, 같은 trace로 parameter를 고르고 평가한 maximum-potential 결과이다.
* L-OPP는 DjangoBench와 MediaWiki 두 DCPerf workload에서 PAW보다 나았고 DjangoBench에서는 AGE보다 소폭 나았다. 반면 TaoBench와 FeedSim에서는 낮은 offline precision 때문에 높은 promotion rate가 발생해, 학습 기반 정책에서 constraint 준수가 자동으로 보장되지 않음을 보였다.

=== Linux end-to-end 검증 ===

Linux 5.10에서 SSD swap과 30초 reclamation period를 사용해 GraphX PageRank를 실행한 결과는 다음과 같다. AGE는 10분간 사용되지 않은 page를, PAW는 prior reuse distance가 2.5분보다 큰 page를 reclaim했다.

{| class="wikitable"
! Policy
! Swap (GB)
! 평균 memory usage (GB)
! 실행 시간 (분)
|-
| PAW
| 0.59 ± 0.75
| 9.11 ± 0.84
| 16.9
|-
| AGE
| 0.23 ± 0.29
| 9.52 ± 0.27
| 17.1
|}

PAW는 성능 저하 없이 AGE보다 약 4% 더 많은 메모리를 절감하여 offline MPC의 방향성은 재현했다. 그러나 실제 promotion rate는 두 policy 모두 약 1.5%로, offline MPC에서 의도한 4%보다 낮았다. 실행 시간이 원 trace와 달라 page access와 reclamation이 속한 window가 바뀐 것이 원인으로 분석된다.

== Contribution ==

# 데이터 센터 reclamation을 '''모든 window의 성능 proxy 제약 아래 평균 메모리 절감량을 최대화하는 문제'''로 명시하여 전통적 page replacement와 구분했다.
# MRC에 대응하는 MPC와, promotion-rate budget을 지키는 offline upper bound인 OPP를 제안했다.
# Parameter aggressiveness 사이의 eviction decisions 및 eviction times property를 정의하고 이를 이용한 linear-time MPC 생성 framework를 구현했다.
# MDK를 이용해 AGE의 headroom을 분석하고 PAW, PACE, L-OPP를 설계했으며, 8개 trace와 GraphX Linux 실행으로 toolkit의 설계 workflow를 사례 검증했다.

== Criticisms ==

* '''Optimality의 적용 범위:''' OPP의 optimality proof는 access-bit scan trace처럼 한 window 안의 모든 접근이 같은 시각에 발생했다고 보는 모델에 성립한다. Appendix D는 exact timestamp를 보존하면 greedy OPP가 optimal이 아닌 반례를 제시하며, 대신 최적해와의 총 saving gap이 전체 fault budget × window size보다 작음을 보인다. 따라서 “provably optimal”이라는 요약은 trace 시간 모델을 함께 밝혀야 한다.
* '''Offline oracle와 parameter selection:''' OPP는 미래 접근을 알고 있어야 한다. PACE 결과도 evaluation trace 자체에서 최적 ''(P, A)''를 골라 얻은 upper bound라 overfitting 가능성이 있으며, unseen trace를 위한 train/test tuning이나 online tuner는 future work다.
* '''Proxy의 일반성:''' Promotion rate는 fault cost가 비교적 균일할 때 유용하지만 memory tier와 hardware별 fault latency 차이를 반영하지 못한다. PSI 같은 runtime-dependent metric을 offline MDK에 넣으려면 별도 analytical model이 필요하므로, 다른 metric으로의 일반화는 interface 수준의 주장에 더 가깝다.
* '''Trace와 workload 범위:''' 30초 access-bit scan은 한 period 안의 반복 접근을 세지 못하고, 실험은 hugepage를 끈 per-application trace를 사용한다. Frequency-sensitive policy, hugepage 환경, colocated workload 간 간섭에 대한 결론은 직접 검증되지 않았다.
* '''제한된 end-to-end 증거:''' Kernel 검증은 PAW와 AGE를 비교한 GraphX 한 workload에 한정되고, PACE와 L-OPP는 배포하지 않았다. 또한 offline target 4%와 실제 약 1.5% promotion rate가 어긋나므로, MPC 기반 parameter가 online SLO를 얼마나 정확히 제어하는지는 아직 입증되지 않았다.
* '''비교 비용의 해석:''' 12.5–208배 speedup의 simulation baseline은 10개 parameter를 순차 실행한 값이다. 병렬 simulation도 asymptotic cost는 남지만 wall-clock 격차는 줄일 수 있으므로, 수치는 해당 비교 설정과 함께 해석해야 한다.

== Conclusion ==

이 연구는 데이터 센터 memory reclamation을 고정 용량에서 miss를 줄이는 문제가 아니라, '''window별 SLO proxy budget을 지키며 reclaim 가능한 메모리를 최대화하는 문제'''로 바라보게 만든다. MDK의 MPC, OPP, nesting properties, efficient generator는 policy의 headroom을 측정하고 oracle의 통찰을 practical heuristic으로 옮기는 공통 workflow를 제공한다. 8개 workload의 offline 결과와 제한적인 Linux 검증은 기존 AGE보다 개선할 여지를 보여주지만, 실제 활용을 위해서는 unseen workload의 online tuning과 더 다양한 performance proxy 및 배포 환경에 대한 검증이 필요하다.

[[분류: USENIX OSDI]]

Memory Protection Keys

Ahn9807 — Wed, 02 Sep 2026 10:30:02 GMT

새 문서: #념겨주기 Intel Memory Protection Key

새 문서

#념겨주기 [[Intel Memory Protection Key]]

Ichnaea: A Framework for Precise Tracking of Memory Objects

Ahn9807 — Wed, 02 Sep 2026 10:05:00 GMT

← 이전 판		2026년 9월 2일 (수) 10:05 판
(같은 사용자의 중간 판 하나는 보이지 않습니다)
7번째 줄:		7번째 줄:

	== 개요 ==		== 개요 ==

	이 논문은 C/C++ 프로그램에서 관심 있는 memory object의 read/write를 정확하고 낮은 비용으로 추적하기 위해 [[Memory Protection Keys]](MPK)를 사용하는 framework Ichnaea를 제안한다.		이 논문은 C/C++ 프로그램에서 관심 있는 memory object의 read/write를 정확하고 낮은 비용으로 추적하기 위해 [[Memory Protection Keys]](MPK)를 사용하는 framework Ichnaea를 제안한다.

	== Motivation ==		== Motivation ==
			복잡한 C/C++ 프로그램에서는 pointer와 간접 control flow 때문에 특정 object를 누가 언제 변경했는지 찾기 어렵다. [[Static analysis]]는 접근 지점을 놓칠 수 있고, [[Intel Pin]] 같은 dynamic instrumentation은 거의 모든 load/store를 검사해 매우 느리다. 기존 <code>mprotect</code> 기반 방식은 page permission이 모든 thread에 적용되므로 multi-thread 환경에서 access를 놓칠 수도 있다. 따라서 모든 memory access를 검사하지 않고, 개발자가 선택한 object가 실제로 접근될 때만 동작하는 tracer가 필요하다.
	복잡한 C/C++ 프로그램에서는 pointer와 간접 control flow 때문에 특정 object를 누가 언제 변경했는지 찾기 어렵다. [[Static analysis]]는 접근 지점을 놓칠 수 있고, [[Intel Pin]] 같은 dynamic instrumentation은 거의 모든 load/store를 검사해 매우 느리다. 기존 <code>mprotect</code> 기반 방식은 page permission이 모든 thread에 적용되므로 multi-thread 환경에서 access를 놓칠 수도 있다.

	따라서 모든 memory access를 검사하지 않고, 개발자가 선택한 object가 실제로 접근될 때만 동작하는 tracer가 필요하다.

	== Importance ==		== Importance ==

	Ichnaea는 object tracing의 비용을 전체 instruction 수가 아니라 관심 object의 실제 access 수에 비례하게 만든다. 또한 기존 page-protection tracing에서 trace loss를 만드는 global permission, syscall window, atomic access와 [[False sharing]] 문제를 정리하고, MPK의 thread-local permission으로 이를 줄이는 방법을 보여 준다.		Ichnaea는 object tracing의 비용을 전체 instruction 수가 아니라 관심 object의 실제 access 수에 비례하게 만든다. 또한 기존 page-protection tracing에서 trace loss를 만드는 global permission, syscall window, atomic access와 [[False sharing]] 문제를 정리하고, MPK의 thread-local permission으로 이를 줄이는 방법을 보여 준다.

	== Main Idea ==		== Main Idea ==

	ObjOfInterest가 있는 page의 접근을 평소에는 막아 두고, 접근 시 발생한 <code>SIGSEGV</code>를 tracing event로 사용한다. Handler는 현재 thread에서만 page를 잠시 열고 faulting instruction을 실행·기록한 뒤 다시 접근을 막는다. 다른 thread의 permission은 계속 잠겨 있으므로 concurrent access도 각각 포착할 수 있다.		ObjOfInterest가 있는 page의 접근을 평소에는 막아 두고, 접근 시 발생한 <code>SIGSEGV</code>를 tracing event로 사용한다. Handler는 현재 thread에서만 page를 잠시 열고 faulting instruction을 실행·기록한 뒤 다시 접근을 막는다. 다른 thread의 permission은 계속 잠겨 있으므로 concurrent access도 각각 포착할 수 있다.

27번째 줄:		21번째 줄:

	== Design ==		== Design ==

	# '''Object 등록''': 개발자가 API와 간단한 annotation으로 추적할 global/heap object를 지정하면, runtime library가 backing page에 MPK를 설정한다.		# '''Object 등록''': 개발자가 API와 간단한 annotation으로 추적할 global/heap object를 지정하면, runtime library가 backing page에 MPK를 설정한다.
	# '''Fault 기반 tracing''': Object 접근에서 발생한 fault를 handler가 받아 현재 thread의 permission만 열고, instruction을 emulation한 후 access context를 기록한다.		# '''Fault 기반 tracing''': Object 접근에서 발생한 fault를 handler가 받아 현재 thread의 permission만 열고, instruction을 emulation한 후 access context를 기록한다.
33번째 줄:		26번째 줄:

	== Result ==		== Result ==
			'''SPEC CPU2017'''에서 Ichnaea는 대부분 native의 1–3배 runtime으로 동작했고, Intel Pin tracer보다 12–60배, <code>mprotect</code> tracer보다 1.3–7배
	# '''SPEC CPU2017''': Ichnaea는 대부분 native의 1–3배 runtime으로 동작했고, Intel Pin tracer보다 12–60배, <code>mprotect</code> tracer보다 1.3–7배 ~~빨랐다.~~
	~~# '''PostgreSQL''': Regression test의 real time은 native 17초, Ichnaea 35초, Intel Pin 944초로, Ichnaea가 Pin보다 약 26배 빨랐다.~~
	~~# '''Access cost''': Fast path의 object access당 median latency는 9.0 µs였다. MPK permission 변경 자체는 0.05 µs로 <code>mprotect</code>의 2.0 µs보다 훨씬 짧았다.~~
	~~# '''Fuzzing''': Synthetic [[AFL++]] workload에서 Ichnaea는 25분 안에 17개 target access를 모두 기록했지만, Intel Pin은 12시간 안에 target path에 도달하지 못했다.~~

	== Contribution ==		== Contribution ==
51번째 줄:		40번째 줄:
	* Emulation하지 못하는 instruction의 slow path는 shared code에 breakpoint를 삽입하므로 multi-thread execution을 방해할 가능성이 있다. 평가도 하나의 Intel MPK 시스템과 synthetic fuzzing workload에 집중되어 있다.		* Emulation하지 못하는 instruction의 slow path는 shared code에 breakpoint를 삽입하므로 multi-thread execution을 방해할 가능성이 있다. 평가도 하나의 Intel MPK 시스템과 synthetic fuzzing workload에 집중되어 있다.

	== Conclusion ==		== [[Conclusion]] ==
			Ichnaea의 핵심은 '''소수의 중요한 object만 선택하여, 실제 접근이 발생할 때 MPK fault로 추적한다'''는 것이다. 이 방식은 특정 Object를 추적하기 위해서, Intel Pin보다 크게 낮은 비용으로 풍부한 access context를 제공하지만, kernel·stack·all-object tracing을 대체하는 범용 도구는 아니다.

	~~Ichnaea의 핵심은 '''~~소수의 중요한 ~~object만 선택하여~~, ~~실제 접근이 발생할 때 MPK fault로 추적한다'''는 것이다~~. ~~이 방식은 Intel Pin보다 크게 낮은 비용으로 풍부한 access context를 제공하지만~~, ~~kernel·stack·all-object tracing을 대체하는 범용 도구는 아니다~~.		=== Major Concenrs ===
			# 제시한 방법에서 Evaluation을 할때, 특정 소수의 Selective한 오브젝트를 대상으로 하였다. 만약 Object가 Allocation보다 Instruction에 더 Senstive한 Object라면 본 논문에서 제시한 결과보다 결과가 안 좋게 보일 수도 있다.
			# Still성능이 매우 좋지 못하다. Runtime patch만으로 object pointer관계를 추적하는 더 좋은 방법은 없을지 궁금하다.
			# 또한 결국에는 Object annotation을 static time에 해주어야 한단는 점에서, Compiler 단계를 거쳐야 한다. 그렇다면 Compile time에 annotation을 삽입하는 방식과 어떤 차이가 있을지 궁금하다. 이미 Security field에서는 모든 오브젝트의 Control flow를 추적하지만 overhead는 본 논문과 비슷한(!) Compiler-time code injection방식이 소개되어 있다.
			# Locality가 중요한 Object, e.g., stack, 으로 확장하기 어렵다. 한 Object에 대한 Fault를 위해서 나머지 Object에도 Fault를 일으킬 가능성이 있기 떄문이다.

	[[분류: USENIX OSDI]]		[[분류: USENIX OSDI]]

Ichnaea: A Framework for Precise Tracking of Memory Objects

Noribot — Wed, 02 Sep 2026 09:20:02 GMT

Nori: update draft.wikitext

새 문서

{{Paper
|title=Ichnaea: A Framework for Precise Tracking of Memory Objects
|author=Samad Haque, Sibin Mohan, Aaron Paulos, Partha Pal
|conference=20th USENIX Symposium on Operating Systems Design and Implementation (OSDI '26)
|year=2026
}}

== 개요 ==

이 논문은 C/C++ 프로그램에서 관심 있는 memory object의 read/write를 정확하고 낮은 비용으로 추적하기 위해 [[Memory Protection Keys]](MPK)를 사용하는 framework Ichnaea를 제안한다.

== Motivation ==

복잡한 C/C++ 프로그램에서는 pointer와 간접 control flow 때문에 특정 object를 누가 언제 변경했는지 찾기 어렵다. [[Static analysis]]는 접근 지점을 놓칠 수 있고, [[Intel Pin]] 같은 dynamic instrumentation은 거의 모든 load/store를 검사해 매우 느리다. 기존 <code>mprotect</code> 기반 방식은 page permission이 모든 thread에 적용되므로 multi-thread 환경에서 access를 놓칠 수도 있다.

따라서 모든 memory access를 검사하지 않고, 개발자가 선택한 object가 실제로 접근될 때만 동작하는 tracer가 필요하다.

== Importance ==

Ichnaea는 object tracing의 비용을 전체 instruction 수가 아니라 관심 object의 실제 access 수에 비례하게 만든다. 또한 기존 page-protection tracing에서 trace loss를 만드는 global permission, syscall window, atomic access와 [[False sharing]] 문제를 정리하고, MPK의 thread-local permission으로 이를 줄이는 방법을 보여 준다.

== Main Idea ==

ObjOfInterest가 있는 page의 접근을 평소에는 막아 두고, 접근 시 발생한 <code>SIGSEGV</code>를 tracing event로 사용한다. Handler는 현재 thread에서만 page를 잠시 열고 faulting instruction을 실행·기록한 뒤 다시 접근을 막는다. 다른 thread의 permission은 계속 잠겨 있으므로 concurrent access도 각각 포착할 수 있다.

이 과정에서 thread ID, instruction pointer, call stack, timestamp, access type과 write 전후 값을 함께 기록한다.

== Design ==

# '''Object 등록''': 개발자가 API와 간단한 annotation으로 추적할 global/heap object를 지정하면, runtime library가 backing page에 MPK를 설정한다.
# '''Fault 기반 tracing''': Object 접근에서 발생한 fault를 handler가 받아 현재 thread의 permission만 열고, instruction을 emulation한 후 access context를 기록한다.
# '''Coverage 확장''': Shared library의 접근은 같은 fault 경로로 잡는다. Heap object는 별도 page에 배치하며, libc syscall wrapper를 이용해 일부 kernel write도 추적한다. 실행이 끝나면 결과를 JSON으로 저장한다.

== Result ==

# '''SPEC CPU2017''': Ichnaea는 대부분 native의 1–3배 runtime으로 동작했고, Intel Pin tracer보다 12–60배, <code>mprotect</code> tracer보다 1.3–7배 빨랐다.
# '''PostgreSQL''': Regression test의 real time은 native 17초, Ichnaea 35초, Intel Pin 944초로, Ichnaea가 Pin보다 약 26배 빨랐다.
# '''Access cost''': Fast path의 object access당 median latency는 9.0 µs였다. MPK permission 변경 자체는 0.05 µs로 <code>mprotect</code>의 2.0 µs보다 훨씬 짧았다.
# '''Fuzzing''': Synthetic [[AFL++]] workload에서 Ichnaea는 25분 안에 17개 target access를 모두 기록했지만, Intel Pin은 12시간 안에 target path에 도달하지 못했다.

== Contribution ==

# 기존 object tracer가 multi-thread 환경에서 access를 놓치는 원인을 정리하였다.
# MPK와 instruction emulation을 결합한 selective object-tracing framework를 설계하였다.
# SPEC CPU2017, PostgreSQL과 fuzzing 실험으로 기존 instrumentation 방식보다 낮은 비용을 보였다.

== Criticisms ==

* “Complete tracing”은 userspace 중심의 주장이다. 일부 syscall과 kernel write는 지원하지만 kernel read 전체를 추적하지 못하며 stack object도 지원하지 않는다.
* 모든 object가 아니라 미리 고른 소수의 object에 적합하다. Hot object는 access마다 약 9 µs의 fault 비용을 내고, heap object를 page별로 분리하면 10,000개 실험에서 memory 사용량이 19배 증가했다.
* Emulation하지 못하는 instruction의 slow path는 shared code에 breakpoint를 삽입하므로 multi-thread execution을 방해할 가능성이 있다. 평가도 하나의 Intel MPK 시스템과 synthetic fuzzing workload에 집중되어 있다.

== Conclusion ==

Ichnaea의 핵심은 '''소수의 중요한 object만 선택하여, 실제 접근이 발생할 때 MPK fault로 추적한다'''는 것이다. 이 방식은 Intel Pin보다 크게 낮은 비용으로 풍부한 access context를 제공하지만, kernel·stack·all-object tracing을 대체하는 범용 도구는 아니다.

[[분류: USENIX OSDI]]

Virtualizing eBPF with Late-Binding

Ahn9807 — Wed, 02 Sep 2026 06:23:23 GMT

← 이전 판		2026년 9월 2일 (수) 06:23 판
62번째 줄:		62번째 줄:

	최종적으로 여러 Per-tenent policy가 Global policy랑 Conflict될때 어떻게 Sound하게 처리할지에 대한 이야기가 없다. 만약 Global policy상 이 Process는 schedule out시켜야 하는데 per-tenent eBPF program이 schedule out시키지 않아야 한다고 주장하면 어떻게 할 것인가? Virtualization이 이 모든 Specific case를 보장할 수 있을 것인가? 어떤식으로 보장되는지 Restrict할수 있을 것인가?		최종적으로 여러 Per-tenent policy가 Global policy랑 Conflict될때 어떻게 Sound하게 처리할지에 대한 이야기가 없다. 만약 Global policy상 이 Process는 schedule out시켜야 하는데 per-tenent eBPF program이 schedule out시키지 않아야 한다고 주장하면 어떻게 할 것인가? Virtualization이 이 모든 Specific case를 보장할 수 있을 것인가? 어떤식으로 보장되는지 Restrict할수 있을 것인가?

			=== Major Concerns ===
			논문에는 또한 State overlay의 Semantic이 정의되어 있지 않다. 논문은 tenant별 patch가 어떻게 capture되고, 적용되며, 다시 되돌려지는지는 설명한다. 그러나 이러한 virtual modification이 실제 kernel의 canonical state와 어떻게 상호작용하는지는 불분명하다. 특히 여러 tenant가 동일한 shared object를 수정하는 경우, 그중 어떤 변경사항이 이후 kernel execution에 실제로 반영되는지가 명확하지 않다.

			더 중요한 문제는 tenant patch와 kernel이 정상적으로 수행하는 state update가 서로 어떻게 조정되는가이다. 예를 들어 overlay가 적용되는 사이 또는 동시에 kernel이 같은 object를 수정한다면, 두 변경사항 중 어떤 것이 우선하며 어떻게 병합되는지 설명되어 있지 않다. Discussion에서는 현재 설계가 exclusive access를 가정하며 RCU reader를 명시적으로 다루지 않는다고 인정하고 있지만, exclusive access만으로는 kernel과 tenant가 충돌하는 update를 어떻게 commit하거나 revert할지는 다루지 않는다.

	[[분류: USENIX OSDI]]		[[분류: USENIX OSDI]]

Virtualizing eBPF with Late-Binding

Noribot — Wed, 02 Sep 2026 05:56:29 GMT

Nori: update draft.wikitext

새 문서

{{Paper
|title=Virtualizing eBPF with Late-Binding
|author=Jing Zhang, Xiaguannan Song, Dong Du, Yubin Xia, Binyu Zang, Haibo Chen
|conference=20th USENIX Symposium on Operating Systems Design and Implementation (OSDI '26)
|year=2026
}}

== 개요 ==
이 논문은 단일 trust domain을 전제로 설계된 [[eBPF]]를 여러 tenant가 공유하면 왜 hook·execution context·kernel state 충돌이 발생하며, physical hook과 logical program의 결합을 실행 시점까지 미루는 '''late binding'''으로 이를 어떻게 가상화할 수 있는지를 다루었다.

== Motivation ==
점점 eBPF를 Process의 Customization을 위해서 사용되는 경우가 많아지고 있다. 그러나 native eBPF의 program은 load/attach 시 단순히 커널의 함수에 Hooking되기 때문에 Per-process context가 아니라 Kernel-context하에서 실행된다.

# '''Singleton conflict''': <code>struct_ops</code>, 일부 [[Linux Security Modules|LSM]] hook, <code>sched_ext</code>, eBPF iterator처럼 global callback을 교체하는 hook은 한 program만 수용하므로 tenant별 policy가 공존할 수 없다.
# '''Functionality conflict''': 같은 hook의 program은 packet header, return value, shared object 같은 execution context를 순차적으로 관찰·변경한다. 각 program이 단독으로는 올바르더라도 조합되면 forwarding loop나 후속 program의 관측 오염이 발생할 수 있다.
# '''Performance interference''': tenant scope와 무관한 program도 매 event마다 실행된다. 특히 global <code>sys_enter</code> [[Tracepoint|tracepoint]]에서는 한 tenant의 tracing 비용을 다른 모든 tenant가 부담하며, program 수가 늘수록 비용이 선형 증가한다.

기존 시스템은 다음과 같은 이유로 인해서 Per-process eBPF context에는 적합하지 않다.
# In-program filtering은 모든 program을 먼저 호출해야 하고 tenant가 filter를 빼는 것을 막지 못한다.
# [[cgroup]] BPF는 process context에는 유용하지만 [[XDP]] 같은 interrupt-context event와 singleton hook을 포괄하지 못하며 state도 분리하지 않는다.
# 중앙 orchestrator가 program을 하나의 binary나 <code>tail_call</code> chain으로 합치면 global policy와 verifier 부담, update latency, API 종속성이 생긴다.

== Main Idea ==
본 논문은 eBPF hook에서 직접 eBPF프로그램을 실행시키는 것이 아니라 '''generic interposition point'''로 바꾸고, event가 발생한 뒤 그 event의 tenant를 식별하여 실행하게 하였다.

각 process는 hierarchical eBPF namespace에 속한다. Event가 발생하면 vBPF Sniffer가 해당 namespace를 찾고, Dispatcher가 namespace에 등록된 program과 관찰 권한이 있는 eBPF program만 선택한다. 이어 state isolation framework가 “global” state access를 tenant-private instance 또는 semantic overlay로 redirect한다. 결과적으로 같은 physical hook을 공유해도 tenant마다 독립적인 eBPF environment가 보인다.

최종적으로, vBPF의 핵심 경로는 다음과 같다.
<pre>
physical event → tenant attribution → eBPF namespace
→ tenant program set + virtual state view → execution
</pre>

== Challenge ==
# '''Interrupt-context attribution''': packet arrival이나 I/O completion에는 신뢰할 process context가 없다. Process-context resource creation과 interrupt-time representation 사이를 잇는 stable key와 lifecycle 관리가 필요하다.
# '''Scalable dispatch''': native hook의 linked list/array를 tenant filter와 함께 순회하면 program 또는 tenant 수에 따라 <math>O(N)</math> 비용이 발생한다. Critical path에서는 tenant program의 직접 lookup이 필요하다.
# '''State isolation의 성능과 유지보수성''': page-table switching은 너무 무겁고, kernel state access마다 수작업으로 tenant logic을 넣으면 Linux 변화에 취약하다. 어떤 interface가 shared state를 변경하는지 compile time에 통제하면서, runtime에는 작은 object 단위의 virtual view를 제공해야 한다.

== Design ==

# '''Hierarchical eBPF namespace와 execution context'''
#: vBPF는 cgroup과 독립적인 namespace를 process에 결합하며 <code>clone</code>, <code>unshare</code>, <code>setns</code> semantics를 지원한다. Sidecar와 application처럼 resource group은 공유하되 tracing policy는 분리할 수 있고, child-to-root 순서로 program을 실행하여 host namespace가 tenant event를 audit·modify·veto할 수 있다. 이 hierarchy는 tenant isolation과 platform-level visibility를 동시에 보존하지만, parent가 child의 context와 return code에 미치는 우선순위를 policy로 명시해야 한다.
# '''vBPF Sniffer: resource-based two-phase attribution'''
#: Process context에서 <code>bind()</code>, <code>connect()</code>, I/O submission처럼 resource가 설정될 때 Sniffer가 stable resource key와 namespace의 mapping을 <code>insert</code>한다. Interrupt context에서는 packet header, <code>bio/request</code> 등의 reader가 같은 identity를 추출하고 <code>resolve</code>하여 namespace를 얻는다. Network sniffer는 5-tuple을 connection setup 단계에 따라 정제하고, request sniffer는 split/merge 시 namespace set을 전파하며, task sniffer는 teardown 뒤늦게 발생한 event를 처리한다. 모든 interrupt를 attribution하지 않고 tenant-bearing resource만 추적하며, tenant owner가 없는 platform interrupt는 host namespace에 남긴다.
# '''vBPF Dispatcher: virtual hook multiplexer와 hash index'''
#: Physical hook에는 tenant program 대신 하나의 multiplexer를 두고, namespace를 key로 하는 hash table에서 해당 program array를 직접 찾는다. Native eBPF의 global linear traversal을 tenant별 <math>O(1)</math> lookup과 cache-friendly sequential execution으로 바꾸므로 unrelated program 호출을 제거한다. Namespace ancestor chain은 attachment 시 flattened array로 미리 계산할 수 있다. 이는 runtime recursion을 없애는 대신 update 때 array를 atomically 재구성하고 namespace별 memory를 추가로 사용한다.
# '''Compiler-enforced state isolation'''
#: Customized Clang frontend의 static analyzer는 verifier-visible helper와 kfunc를 state-access checkpoint로 사용한다. <code>vbpf_helper</code>로 interface를 식별하고, global state를 변경할 가능성이 있는 call은 default-deny하며, kernel developer가 <code>vbpf_safe</code>로 승인한 경우만 허용한다. Pointer argument는 verifier의 type·memory-region 정보를 이용해 tenant-private/read-only 여부를 분류한다. 이 방식은 tenant code가 임의의 shared state mutation path를 우회하지 못한다는 invariant를 세우지만, annotation과 analyzer soundness를 trusted computing base에 포함한다.
# '''vBPF variables library'''
#: 복제 가능한 static state는 declarative API로 namespace별 instance를 lazy allocation한다. 여러 field와 이를 보호하는 lock은 한 storage group으로 배치해 일관되게 resolve한다. 반면 <code>sk_buff</code>처럼 복제할 수 없는 shared kernel object에는 [[BPF Type Format|BTF]] layout을 이용한 semantic state overlay를 적용한다. Helper 실행 전 clean base state를 복원하고 tenant patch를 apply하며, 실행 중 capture 또는 field-level update로 변경분을 기록한 뒤 namespace patch set에 finalize한다. Context switch 때 patch를 원자적으로 apply/restore하여 tenant별 view를 제공하며, full memory snapshot 대신 의미 있는 field 변경만 저장한다.
# '''Hot-path implementation'''
#: Sniffer registry와 Dispatcher table은 [[Read-copy-update|RCU]]-protected hash table로 구현하여 lookup을 lock-free로 수행한다. Critical-section allocation 실패와 latency variation을 줄이기 위해 object pool은 preallocate하고, tenant-private state는 첫 접근까지 lazy allocation한다. Hierarchy path와 BTF layout은 setup 시 precompute한다. 구현 규모는 Linux 6.12 kernel 약 12 KLoC와 LLVM 20 Clang plugin 약 1 KLoC이다.

== [[Conclusion]] ==
본 논문은 eBPF의 per-kernel context가 아니라 per-process context로 확장 시켜야 된다고 주장한다. 논문에서 제시하는 Motivation은<ref>Section 2.2 From Platform to Tenant eBPF</ref> 기존 논문이 다루지 않았다는 점에서 신선하였다. 그러나 본 논문은 필연적으로 커널의 여러 부분을 건드리기 때문에 여러 Corner case에 대한 의문이 생길 수 밖에 없었다.

우선, Motivation에서 궁금한 점이 있다. eBPF는 Per-process context로 실행시키는 프로그램이 있으면 새로운 BPF program type을 만들면 된다고 생각한다. XDP나 Storage같은 Device장치의 가속은 보통은 Per-process가 아니라 Per-kernel에서 작동해야만 효율적인 경우가 대부분인다. 따라서 eBPF의 현재 Execution model이 진짜 Per-process를 Support못해서가 아닌, 그렇게 하는 경우가 대부분인기 떄문에 지원하지 않는다고 보는 것이 좋아보인다. 그리고 eBPF는 기본적으로 CAP_BPF아니면 Root privileged를 요구하는 경우가 많다. 이 경우 단순히 그냥 namespace만 manual하게 체크할 수 있도록 하는 hook을 추가하면 될지 않을까 하는 생각이 든다.

Correctness측면에서의 의문은, 또한 Namespace로 묶는 vBPF Sniffer는 결국 Interrupt context -> task의 backward mapping인데, 이 부분이 모든 BPF Program type마다 다를텐데, 이를 어떻게 일이 태깅 하냐의 문제가 생길 것이라 생각한다. 또한 논문에서 주장하는 TCB에서 DoS가 빠져있는데, DoS는 Per-process context에서 매우 중요한 Threat model이다. 이를 뺴면 안된다고 생각한다. 또한 만약 Process에서 먼저 실행되지 않는 Context가 있으면 이는 어떻게 처리할 것인가? Kfunc는 이미 2022년 이후로 Default가 되었고, Helper function만 지원한다는 것도 큰 Limitation이다. Concurrency는 어떻게 할지도 의문이 남는다. RCU Lock을 잡고 Resource를 건들고 있다고 해보자. State overlay같은 경우에는 두개의 복사본이 있는 것인데, RCU Lock을 두 스레드가 공유하고 있다면? Merge할때 분명히 관련하여 문제가 생길것이라고 생각한다.

성능면에서는, 그리고 namespace lookup에 10ns-100ns가 걸린다고 하였는데, 이는 100Gb/s가 넘어가는 현재 시스템에 적용하기에는 큰 오버헤드이다.

최종적으로 여러 Per-tenent policy가 Global policy랑 Conflict될때 어떻게 Sound하게 처리할지에 대한 이야기가 없다. 만약 Global policy상 이 Process는 schedule out시켜야 하는데 per-tenent eBPF program이 schedule out시키지 않아야 한다고 주장하면 어떻게 할 것인가? Virtualization이 이 모든 Specific case를 보장할 수 있을 것인가? 어떤식으로 보장되는지 Restrict할수 있을 것인가?

[[분류: USENIX OSDI]]

Jwmalloc: A Verified Memory Allocator for Mobile Devices

Ahn9807 — Wed, 02 Sep 2026 03:12:00 GMT

차이 보기

파일:OSDI2026 jwmalloc figure9.png

Ahn9807 — Wed, 02 Sep 2026 02:55:13 GMT

Ahn9807님이 파일:OSDI2026 jwmalloc figure9.png 파일을 올렸습니다

새 문서

OSDI2026_jwmalloc_figure9

Jwmalloc: A Verified Memory Allocator for Mobile Devices

Noribot — Wed, 02 Sep 2026 02:25:38 GMT

Nori: update draft.wikitext

새 문서

{{Paper
|title=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
}}

== 개요 ==
이 논문은 기존 범용 [[Memory allocator|동적 메모리 할당기]]의 설계가 모바일 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의 [[Proportional set size|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했을 듯 하다.

[[분류: USENIX OSDI]]

PeeR: First-Class Scheduling for Latency-Critical eBPF Applications

Noribot — Tue, 01 Sep 2026 09:27:36 GMT

Nori: update draft.wikitext

새 문서

{{Paper
|title=PeeR: First-Class Scheduling for Latency-Critical eBPF Applications
|author=Jeremy Carin, Ben Holmes, Weiyang Wang, Ankit Bhardwaj, Manya Ghobadi
|conference=20th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2026)
|year=2026
}}

== 개요 ==

이 논문은 latency-critical [[eBPF]] application이 non-preemptable [[softirq]]에서 실행될 때 발생하는 [[Head-of-line blocking]]과 CPU accounting 부재를, verifier가 보장하는 helper boundary에서의 [[Cooperative scheduling|cooperative preemption]]과 [[sched_ext]] 기반 2-level scheduling으로 해결하였다.

== Motivation ==
eBPF는 kernel 안에서 application logic을 실행하여 context switch와 data copy를 줄이지만, 그 실행 모델은 짧고 예측 가능한 packet filter를 가정한 채 run-to-completion으로 남아 있다<ref>While eBPF programs have grown dramatically in complexity, their execution model, which was originally designed for tiny packet filters, has remained largely unchanged.</ref>. 반면 최신 eBPF application은 복잡한 기능을 담당하는 Helper function을 eBPF program의 instruction대비 매우 많은 빈도로 실행시킨다. 이러한 환경에서는 eBPF Verifier의 eBPF 프로그램은 Instruction limit이 있기 떄문에 non-preemtible하다는 가정이 깨진다.

즉, 현재 복잡한 eBPF workload가 latency-critical I/O path의 softirq에서 실행되면 두 문제가 생긴다.

# '''Intra-application blocking''': long request가 먼저 도착하면 뒤의 short request가 preempt할 수 없어 [[Tail latency]]가 증가한다.
# '''Inter-application unfairness''': softirq 실행 시간은 eBPF application이 아니라 interrupt된 process에 귀속된다. 따라서 만약 Process A가 eBPF를 사용하게 된다면, eBPF 프로그램을 사용하지 않는 Process B도 Process A의 eBPF time을 paying해, scheduling에서 불리한 위치에 놓여지게 된다.

ksoftirq를 사용하더라도, ksoftirq는 invocation 내부를 preempt하거나 개별 eBPF task의 CPU 사용량과 우선순위를 scheduler에 드러내지 못한다. 따라서 application을 kernel fast path에 유지하면서도 invocation을 scheduling 가능한 resource로 만드는 새로운 Scheduling unit을 만들어야 한다.

== Importance ==
# PeeR는 eBPF의 안전성을 verifier 통과 여부에만 한정하지 않고, scheduler-visible accounting, preemption, policy enforcement까지 포함하는 resource-management 문제로 확장한다.
# [[eBPF verifier]]의 compile-time type/liveness 정보를 runtime continuation 복원에 재사용한다는 점이 핵심적인 architecture/runtime co-design이다.

== Challenges ==
eBPF를 schedulable하게 만드는 것은 다음의 요소 때문에 도전적인 과제이다.
# Enaling fine-grained preemption with low overhead
# Preserving eBPF correctness under preemption
# Providing expressive scheduling abstractions

== Main Idea ==
eBPF program이 kernel state와 상호작용하기 위해 helper function이나 kfunc를 자주 호출하고, verifier가 각 call boundary에서 register, stack, lock, reference의 상태를 이미 추적한다는 것이다. PeeR는 안전한 helper boundary에 JIT budget check를 삽입하여, budget을 넘긴 invocation이 다음 safe point에서 자동으로 yield하도록 만든다. 즉 application code에 명시적 <code>yield()</code>를 요구하지 않으면서 verifier-guided cooperative preemption을 구현한다.

실행 모델은 hybrid fast/slow path이다. budget 안에서 끝나는 task는 softirq에서 기존처럼 FCFS로 완료한다. budget을 넘긴 task만 상태를 continuation에 저장하고 per-CPU PeeR-kthread에서 복원한다. [[sched_ext]]가 outer macro-scheduler로서 eBPF workload와 userspace process 사이의 총 CPU 배분을 제어하고, kthread 내부의 micro-scheduler가 FIFO, [[Shortest remaining processing time|SRPT]], weighted round-robin 같은 policy로 개별 continuation의 순서를 정한다.

== Design ==

# '''Verifier-guided preemption point'''
#: '''문제''': timer interrupt로 임의 지점에서 끊으면 fast-path overhead가 크고, register·stack·kernel resource가 복원 가능한 상태인지 보장할 수 없다.
#: '''Mechanism''': PeeR는 JIT compiler가 안전한 helper/kfunc call 직전에 per-CPU epoch flag를 확인하는 prologue와 고유 <code>site_id</code>를 삽입하게 한다. budget이 만료되면 helper 실행 전에 yield handler로 분기하여 11개 register(88 B), 512 B eBPF stack, hook-specific context를 저장한다. flag가 꺼진 일반 경로의 check는 helper call당 1 cycle, scheduler가 flag를 갱신할 때는 2 cycle이다.
#: '''효과와 tradeoff''': 대부분의 짧은 task는 context switch 없이 기존 fast path를 유지하지만, preemption granularity는 안전한 helper 사이의 실제 실행 시간에 제한된다.
# '''Continuation 저장과 정확한 resume'''
#: '''문제''': softirq에서 저장한 stack/context pointer를 다른 kernel stack의 worker thread에서 그대로 복원하면 stale pointer가 되어 memory corruption을 일으킨다.
#: '''Mechanism''': verifier가 각 yield site에서 추적한 <code>PTR_TO_STACK</code>과 <code>PTR_TO_CTX</code> 정보를 patch descriptor로 보존하고, resume 시 새 stack/context base에 맞게 pointer를 rebase한다. JIT가 site별 [[Control-flow integrity|CFI]]-safe trampoline을 생성하므로, worker는 저장된 <code>site_id</code>에 대응하는 helper call 직전으로 돌아가 helper의 side effect를 정확히 한 번만 수행한다.
#: '''효과와 tradeoff''': source eBPF program 수정 없이 context를 옮길 수 있지만, verifier type이 모든 incoming path에서 일치하는 위치만 patch할 수 있다.
# '''Kernel resource와 [[Read-copy-update|RCU]] 안전성'''
#: '''문제''': softirq가 끝나면 implicit RCU read-side critical section도 끝나므로, live map-value/RCU pointer를 가진 채 yield하면 resume 전에 대상이 변경되거나 해제될 수 있다.
#: '''Mechanism''': verifier의 type 및 liveness 정보로 RCU-protected pointer, acquired reference, active lock이 없는 helper site에만 preemption check를 넣는다. lock-held region이나 unsafe resource가 live한 site는 yield point가 아니다.
#: '''효과와 tradeoff''': memory safety invariant를 보존하지만 cooperative gap이 길어질 수 있다. 또한 invocation이 서로 interleave되고 per-core completion order가 바뀔 수 있으므로 shared state의 원자성을 가정한 program은 spin lock 등으로 명시적으로 동기화해야 한다.
# '''Hook-specific continuation'''
#: '''문제''': verifier는 eBPF 내부 상태만 검증하므로, caller가 즉시 verdict를 요구하거나 lock을 쥔 hook은 결과를 나중에 적용할 수 없다.
#: '''Mechanism''': compatible hook은 input lifetime을 연장할 수 있고, caller가 deferred result를 허용하며, caller-side lock이 없어야 한다. 구현된 native XDP path는 packet을 reference-counted <code>xdp_frame</code>으로 전환하고 <code>XDP_YIELD</code>를 반환하여 [[NAPI]] poll을 계속한 뒤, worker에서 실제 DROP, ABORTED, PASS, TX, REDIRECT verdict를 적용한다.
#: '''효과와 tradeoff''': fast path가 deferred task를 기다리지 않지만 현재 구현은 native single-buffer XDP만 지원하며 multi-buffer와 tail-call program은 거부한다. 논문은 direct-action tc/TCX와 XRP storage hook이 model에 맞는다고 분석하지만 구현하지 않았다.
# '''Two-level scheduling과 accounting'''
#: '''문제''': sched_ext는 여러 continuation을 담은 하나의 PeeR-kthread만 보므로 개별 eBPF invocation의 순서나 owner별 CPU 시간을 직접 구분할 수 없다.
#: '''Mechanism''': outer sched_ext macro-scheduler는 <code>runtime_event</code> per-CPU ring buffer의 owner, CPU, duration, completion/yield 정보를 userspace daemon이 집계한 결과로 application별 CPU allocation을 조정한다. <code>set_budget()</code>은 기본 5 μs quantum을 설정한다. 각 per-CPU kthread 안의 micro-scheduler는 continuation priority와 <code>enqueue()</code>/<code>requeue()</code> callback으로 FIFO, SRPT, WRR을 구현한다.
#: '''효과와 tradeoff''': userspace와 eBPF를 하나의 CPU-sharing policy 아래 둘 수 있고 short/long request 사이의 policy도 선택할 수 있지만, task는 originating CPU에 고정되어 migration하지 않으며 SRPT에는 application-provided remaining-work estimate가 필요하다.

== Result ==
논문이 보고한 전체 범위에서 PeeR는 mixed workload의 latency-sensitive request p99를 current eBPF runtime보다 3–19.8배 줄였으며, 위 결과는 그 개선이 safe-point preemption과 scheduler-visible accounting이라는 두 mechanism에서 각각 발생함을 뒷받침한다.

== Contribution ==
# 7개의 modern eBPF application을 static analysis와 runtime profiling으로 조사하여, run-to-completion fast-path assumption이 execution-time variance, head-of-line blocking, CPU misaccounting 때문에 깨졌음을 정량화했다.
# verifier의 helper-boundary invariant와 type/liveness 정보를 이용해 low-overhead cooperative preemption, state capture, pointer rebasing, CFI-safe resume를 구현했다.
# softirq fast path와 per-CPU worker slow path를 결합하고, sched_ext macro-scheduler와 per-kthread micro-scheduler를 통해 intra-/inter-application policy를 함께 표현하는 2-level scheduling architecture를 제시했다.
# Redis, Memcached, synthetic TPC-C, colocation 및 microbenchmark에서 tail-latency 개선, CPU allocation enforcement, 247 ns preemption-resumption cost를 검증하고 quantum의 성능 tradeoff를 밝혔다.

== Conclusion ==
이 연구는 복잡해진 eBPF fast path를 단순한 안전한 kernel extension이 아니라 CPU accounting과 scheduling이 필요한 first-class workload로 바라보게 만든다. PeeR는 verifier가 보장하는 helper boundary를 safe point로 재사용하고, 짧은 task는 softirq에 남기되 긴 task만 continuation으로 전환하여 low overhead preemption과 policy control을 양립시킬 수 있음을 보였다. 다만, Correctness측면에서 PeeR을 Support하기 위한 방법이 XDP가 아니라 좀더 복잡한 영역으로 확장 가능할지는 의문이다. 만약 할당된 Struct를 eBPF program내부에서 수정하고, Helper function에 의해서 Preemption된다면, 기본적으로 atomic을 가정하는 Helper function입장에서는 [[TOCTOU]]가 발생할 수 있다. 또한 전체 eBPF의 Kfunc라던지 이러한 시스템에 통합하기 위해서는 많은 Kernel-patch가 필요한 점도 Implementation측면에서의 약점이 될 수 있을듯 하다. 그러나 Motivation이 매우 좋고, Design또한 Motivation에 잘 이어지며, 전체적인 시스템의 Nolvety도 좋아보인다. 그리고 Implementation details들이 잘 나와 있어서, Sound하다는 인상을 받았다.

[[분류: USENIX OSDI]]