QUESTION
heap은 언제 준비되고 어떤 backend가 쓰이는가?
lk_main()은 early arch·platform·target 작업 뒤 heap_init()을 호출하고, 그 다음 static constructor·HEAP 구간 hook·kernel_init()으로 간다. 이 시점은 새 bootstrap2 thread를 만들고 scheduler를 시작하기 전이다 (top/main.c:89).
heap_init() 자체는 HEAP_INIT() 위임 한 줄이다. 빌드 기본값 miniheap은 page_first_alloc()의 초기 영역을 받고, cmpctmalloc은 자체 초기 grow를 하며, dlmalloc wrapper의 초기 함수는 비어 있다. backend별 내부 block 동작을 공통 계약으로 섞지 않는다 (lib/heap/heap_wrapper.c:34, lib/heap/rules.mk:12).
STRUCTURE
부트 순서와 backend 선택 구조
backend 선택은 LK_HEAP_IMPLEMENTATION 빌드 값이다. 기본은 miniheap이며 하나의 backend가 wrapper의 HEAP_*에 연결된다 (lib/heap/rules.mk:12).
CALL PATH
할당과 두 해제 경로
heap_delayed_free()는 즉시 backend에 반환하지 않는다. 대상 block이 struct list_node를 담을 만큼 크다고 가정한다 (lib/heap/heap_wrapper.c:120, lib/heap/heap_wrapper.c:217).
STATE LEDGER
초기화와 할당 책임
| 시점·조건 | 실제 작업 | 그 뒤 가능한 사용 | 근거 |
|---|---|---|---|
| HEAP 이전 | early platform/target와 hook 실행 | heap wrapper 준비를 아직 가정하지 않음 | top/main.c:69 |
| heap_init | 선택된 HEAP_INIT 호출 | backend별 초기 상태 성립 | lib/heap/heap_wrapper.c:140 |
| miniheap 기본값 | page_first_alloc 초기 영역 + free list·mutex | 부족하면 page_alloc으로 grow 재시도 | lib/heap/heap_wrapper.c:50 |
| malloc | delayed list drain 후 HEAP_MALLOC | 성공 ptr은 caller가 보유; 실패는 NULL | lib/heap/heap_wrapper.c:153 |
| free / delayed free | 즉시 backend free / 이후 drain 대기 | delayed block은 재사용 전까지 pending | lib/heap/heap_wrapper.c:209 |
miniheap의 초기 영역은 WITH_KERNEL_VM이면 한 페이지, 아니면 novm_alloc_unaligned 결과다. 고정 static arena나 모든 backend의 같은 크기를 뜻하지 않는다 (lib/heap/page_alloc.c:68).
VISUAL WALKTHROUGH
기본 backend와 wrapper의 다른 책임
miniheap 내부 그림과 모든 backend에 공통인 wrapper 소유권을 분리했다. 실제 초기 영역은 page allocator와 선택한 platform 설정으로 확인한다.
split과 coalesce는 기본 miniheap의 free list를 대상으로 한다.
일반 free와 delayed free는 backend에 block을 반환하는 시점이 다르다.
caller가 보유한 ptr
01HEAP_MALLOC이 반환
02해제 전까지 caller 소유
03free면 HEAP_FREE 즉시 호출
04backend별 header·guard 상이
delayed_free_list의 ptr
01ptr 주소에 list node 기록
02아직 HEAP_FREE 전
03drain에서 임시 list로 이동
04lock 밖에서 backend free
UPSTREAM SOURCE
원본 코드
아래 코드는 LK upstream 1eb9917의 lib/heap/heap_wrapper.c에서 116-204줄을 그대로 가져온 것이다.
116#else
117#error need to select valid heap implementation or provide wrapper
118#endif
119
120static void heap_free_delayed_list(void) {
121 struct list_node list;
122
123 list_initialize(&list);
124
125 spin_lock_saved_state_t state;
126 spin_lock_irqsave(&delayed_free_lock, state);
127
128 struct list_node *node;
129 while ((node = list_remove_head(&delayed_free_list))) {
130 list_add_head(&list, node);
131 }
132 spin_unlock_irqrestore(&delayed_free_lock, state);
133
134 while ((node = list_remove_head(&list))) {
135 LTRACEF("freeing node %p\n", node);
136 HEAP_FREE(node);
137 }
138}
139
140void heap_init(void) {
141 HEAP_INIT();
142}
143
144void heap_trim(void) {
145 // deal with the pending free list
146 if (unlikely(!list_is_empty(&delayed_free_list))) {
147 heap_free_delayed_list();
148 }
149
150 HEAP_TRIM();
151}
152
153void *malloc(size_t size) {
154 LTRACEF("size %zd\n", size);
155
156 // deal with the pending free list
157 if (unlikely(!list_is_empty(&delayed_free_list))) {
158 heap_free_delayed_list();
159 }
160
161 void *ptr = HEAP_MALLOC(size);
162 if (heap_trace)
163 printf("caller %p malloc %zu -> %p\n", __GET_CALLER(), size, ptr);
164 return ptr;
165}
166
167void *memalign(size_t boundary, size_t size) {
168 LTRACEF("boundary %zu, size %zd\n", boundary, size);
169
170 // deal with the pending free list
171 if (unlikely(!list_is_empty(&delayed_free_list))) {
172 heap_free_delayed_list();
173 }
174
175 void *ptr = HEAP_MEMALIGN(boundary, size);
176 if (heap_trace)
177 printf("caller %p memalign %zu, %zu -> %p\n", __GET_CALLER(), boundary, size, ptr);
178 return ptr;
179}
180
181void *calloc(size_t count, size_t size) {
182 LTRACEF("count %zu, size %zd\n", count, size);
183
184 // deal with the pending free list
185 if (unlikely(!list_is_empty(&delayed_free_list))) {
186 heap_free_delayed_list();
187 }
188
189 void *ptr = HEAP_CALLOC(count, size);
190 if (heap_trace)
191 printf("caller %p calloc %zu, %zu -> %p\n", __GET_CALLER(), count, size, ptr);
192 return ptr;
193}
194
195void *realloc(void *ptr, size_t size) {
196 LTRACEF("ptr %p, size %zd\n", ptr, size);
197
198 // deal with the pending free list
199 if (unlikely(!list_is_empty(&delayed_free_list))) {
200 heap_free_delayed_list();
201 }
202
203 void *ptr2 = HEAP_REALLOC(ptr, size);
204 if (heap_trace)
READING CONTRACT
원본 발췌와 빠진 backend 분기
기존 주 원본 lib/heap/heap_wrapper.c 116–204행과 보충 145–211행은 고정 원문과 일치해 보존했다. L140의 heap_init()은 HEAP_INIT() 위임이고, 그 매크로 선택은 주 발췌보다 앞에 있다.
miniheap·cmpctmalloc 분기
lib/heap/heap_wrapper.c L34–68
34 #if WITH_LIB_HEAP_MINIHEAP
35 /* miniheap implementation */
36 #include <lib/miniheap.h>
37
38 static inline void *HEAP_MALLOC(size_t s) { return miniheap_alloc(s, 0); }
39 static inline void *HEAP_REALLOC(void *ptr, size_t s) { return miniheap_realloc(ptr, s); }
40 static inline void *HEAP_MEMALIGN(size_t boundary, size_t s) { return miniheap_alloc(s, boundary); }
41 #define HEAP_FREE miniheap_free
42 static inline void *HEAP_CALLOC(size_t n, size_t s) {
43 size_t realsize = n * s;
44
45 void *ptr = miniheap_alloc(realsize, 0);
46 if (likely(ptr))
47 memset(ptr, 0, realsize);
48 return ptr;
49 }
50 static inline void HEAP_INIT(void) {
51 /* start the heap off with some spare memory in the page allocator */
52 size_t len;
53 void *ptr = page_first_alloc(&len);
54 miniheap_init(ptr, len);
55 }
56 #define HEAP_DUMP miniheap_dump
57 #define HEAP_TRIM miniheap_trim
58
59 /* end miniheap implementation */
60 #elif WITH_LIB_HEAP_CMPCTMALLOC
61 /* cmpctmalloc implementation */
62 #include <lib/cmpctmalloc.h>
63
64 #define HEAP_MEMALIGN(boundary, s) cmpct_memalign(s, boundary)
65 #define HEAP_MALLOC cmpct_alloc
66 #define HEAP_REALLOC cmpct_realloc
67 #define HEAP_FREE cmpct_free
68 #define HEAP_INIT cmpct_initheap_init과 constructors 순서
89 // bring up the kernel heap
90 lk_primary_cpu_init_level(LK_INIT_LEVEL_TARGET_EARLY, LK_INIT_LEVEL_HEAP - 1);
91 dprintf(SPEW, "initializing heap\n");
92 heap_init();
93
94 // deal with any static constructors
95 dprintf(SPEW, "calling constructors\n");
96 call_constructors();
97
98 // initialize the kernel
99 lk_primary_cpu_init_level(LK_INIT_LEVEL_HEAP, LK_INIT_LEVEL_KERNEL - 1);
100 kernel_init();miniheap 기본값과 dlmalloc 선택은 lib/heap/rules.mk:12와 lib/heap/heap_wrapper.c:81에서 확인한다. miniheap 초기 영역 정렬·등록은 lib/heap/miniheap/miniheap.c:484에 있다.
RELATED SOURCE
함께 읽어야 하는 원본 코드
첫 코드 조각만으로 동작이 완성되지 않는 경우 호출 매크로, 객체 정의와 실제 실행 목록을 같은 페이지에 묶었다. 각 조각은 같은 기준 commit에서 가져왔다.
01. heap wrapper에서 실제 allocation으로 들어가는 malloc
lib/heap/heap_wrapper.c 145-211줄이다.
145 // deal with the pending free list
146 if (unlikely(!list_is_empty(&delayed_free_list))) {
147 heap_free_delayed_list();
148 }
149
150 HEAP_TRIM();
151}
152
153void *malloc(size_t size) {
154 LTRACEF("size %zd\n", size);
155
156 // deal with the pending free list
157 if (unlikely(!list_is_empty(&delayed_free_list))) {
158 heap_free_delayed_list();
159 }
160
161 void *ptr = HEAP_MALLOC(size);
162 if (heap_trace)
163 printf("caller %p malloc %zu -> %p\n", __GET_CALLER(), size, ptr);
164 return ptr;
165}
166
167void *memalign(size_t boundary, size_t size) {
168 LTRACEF("boundary %zu, size %zd\n", boundary, size);
169
170 // deal with the pending free list
171 if (unlikely(!list_is_empty(&delayed_free_list))) {
172 heap_free_delayed_list();
173 }
174
175 void *ptr = HEAP_MEMALIGN(boundary, size);
176 if (heap_trace)
177 printf("caller %p memalign %zu, %zu -> %p\n", __GET_CALLER(), boundary, size, ptr);
178 return ptr;
179}
180
181void *calloc(size_t count, size_t size) {
182 LTRACEF("count %zu, size %zd\n", count, size);
183
184 // deal with the pending free list
185 if (unlikely(!list_is_empty(&delayed_free_list))) {
186 heap_free_delayed_list();
187 }
188
189 void *ptr = HEAP_CALLOC(count, size);
190 if (heap_trace)
191 printf("caller %p calloc %zu, %zu -> %p\n", __GET_CALLER(), count, size, ptr);
192 return ptr;
193}
194
195void *realloc(void *ptr, size_t size) {
196 LTRACEF("ptr %p, size %zd\n", ptr, size);
197
198 // deal with the pending free list
199 if (unlikely(!list_is_empty(&delayed_free_list))) {
200 heap_free_delayed_list();
201 }
202
203 void *ptr2 = HEAP_REALLOC(ptr, size);
204 if (heap_trace)
205 printf("caller %p realloc %p, %zu -> %p\n", __GET_CALLER(), ptr, size, ptr2);
206 return ptr2;
207}
208
209void free(void *ptr) {
210 LTRACEF("ptr %p\n", ptr);
211 if (heap_trace)
DETAILS
heap_init 뒤 실제로 준비되는 것
부트 순서를 고정한다
thread_init_early()와 early hook, arch/platform/target early init이 먼저다. heap_init() 뒤 constructor가 실행되고 이어 kernel_init이 온다. heap 초기화를 새 bootstrap2 thread의 일로 옮겨 해석하지 않는다 (top/main.c:58).
HEAP_INIT의 backend별 효과를 나눈다
기본 miniheap은 page_first_alloc() 영역을 초기 free chunk로 둔다. cmpctmalloc은 bucket을 초기화하고 page allocator grow를 시도한다. dlmalloc wrapper의 HEAP_INIT은 빈 함수다 (lib/heap/heap_wrapper.c:34, lib/heap/cmpctmalloc/cmpctmalloc.c:840).
miniheap의 두 획득 경로를 구별한다
초기 영역을 먼저 쓰지만 맞는 free chunk가 없으면 lock 밖에서 heap_grow()로 page_alloc을 호출해 한 번 재시도한다. 따라서 단일 고정 arena 크기만으로 실패를 계산할 수 없다 (lib/heap/miniheap/miniheap.c:203, lib/heap/miniheap/miniheap.c:460).
wrapper의 delayed free를 별도로 본다
critical section의 heap_delayed_free()는 list node를 ptr 자리에 써 대기열에 넣는다. 다음 allocation 계열 또는 heap_trim이 목록을 잠금 아래 떼어낸 후 잠금 밖에서 HEAP_FREE한다 (lib/heap/heap_wrapper.c:120, lib/heap/heap_wrapper.c:217).
실제 사용량은 backend에 묻는다
miniheap은 header·정렬·최소 free chunk 크기를 반영하며, 충분한 chunk만 split한다. poison/padding 검사 등 debug 효과는 build option별로 다르다 (lib/heap/miniheap/miniheap.c:165).
IMPLEMENTATION NOTES
세 가지 확인 지점
초기 영역은 page allocator가 준다
page_first_alloc()은 VM 구성에서는 한 페이지, novm 구성에서는 novm_alloc_unaligned() 결과를 반환한다. miniheap은 받은 ptr를 pointer 크기로 맞춰 초기 free chunk에 넣는다 (lib/heap/page_alloc.c:68, lib/heap/miniheap/miniheap.c:484).
block 메타데이터는 miniheap에만 고정한다
miniheap에는 free chunk의 node·len과 allocated block 앞의 base pointer·size가 있다. cmpctmalloc과 dlmalloc의 내부 형식을 이 구조로 설명하지 않는다 (lib/heap/miniheap/miniheap.c:38, lib/heap/miniheap/miniheap.c:55).
realloc도 backend 분기를 따른다
wrapper는 HEAP_REALLOC로 넘긴다. 이 commit의 miniheap 구현은 새 크기만큼 memcpy하며 소스에 XXX wrong 주석이 있다. 기존 크기 이하만 복사한다고 가정하면 안 된다 (lib/heap/heap_wrapper.c:195, lib/heap/miniheap/miniheap.c:288).
OBJECT LIFETIME
영역과 포인터의 소유권
| 대상 | 획득·등록 | 사용·회수 | 조건 |
|---|---|---|---|
| miniheap 초기 page 영역 | page_first_alloc 뒤 miniheap_init | 초기 free chunk; 이후 backend 관리 | lib/heap/heap_wrapper.c:50 |
| miniheap 추가 pages | fit 실패 시 heap_grow | free chunk로 삽입; trim 조건은 backend 구현 | lib/heap/miniheap/miniheap.c:460 |
| malloc 반환 ptr | 선택 backend의 HEAP_MALLOC | caller가 보유, free 또는 realloc | lib/heap/heap_wrapper.c:153 |
| delayed ptr | heap_delayed_free가 list에 넣음 | 다음 drain 때 HEAP_FREE | lib/heap/heap_wrapper.c:217 |
FAILURE PATH
초기화와 회수 실패를 구분
| 관찰 | 먼저 확인할 조건 | 근거 |
|---|---|---|
| 초기 malloc 실패 | backend 선택, 초기 page 획득, miniheap grow 결과 | lib/heap/heap_wrapper.c:34 |
| 초기 영역 크기 예상과 다름 | WITH_KERNEL_VM와 novm 분기, 정렬 손실 | lib/heap/page_alloc.c:68 |
| free 뒤 곧바로 공간이 늘지 않음 | heap_delayed_free로 pending인지, drain이 실행됐는지 | lib/heap/heap_wrapper.c:120 |
| miniheap alloc NULL | free list fit 실패와 1회 heap_grow 실패 | lib/heap/miniheap/miniheap.c:274 |
| miniheap realloc에서 이상 읽기 | 요청 크기 기반 memcpy와 기존 block 크기 | lib/heap/miniheap/miniheap.c:288 |
dlmalloc·cmpctmalloc의 metadata와 failure policy는 각 backend에서 확인한다. 이 표의 miniheap 내부 동작을 공통 구현으로 옮기지 않는다.
EVIDENCE
선택한 LK 빌드에서 확인
아래 ELF는 실제 project 산출물로 대체한다. nm은 C 선언이 아닌 symbol 이름을 출력한다.
| 목적 | 명령 또는 계측 | 판정 |
|---|---|---|
| backend 선택 | 빌드의 LK_HEAP_IMPLEMENTATION과 map 확인 | miniheap/cmpctmalloc/dlmalloc 중 하나의 코드 |
| heap symbol | nm -an <ELF> | grep -E '[[:space:]](heap_init|malloc|heap_delayed_free)$' | 심볼이 남은 빌드에서 주소 확인 |
| 초기 영역 | page_first_alloc의 ptr·len과 miniheap_init 인자 기록 | VM/novm 분기와 정렬 후 크기 일치 |
| allocation·drain | malloc ptr, delayed list 길이, heap_trim 시각 기록 | pending에서 backend free까지의 지연 구분 |
LAB
세 가지 확인 실험
- 01초기화 순서를 log로 고정
heap_init, constructor, kernel_init에 짧은 log를 넣어 selected project에서 실제 순서를 기록한다.
- 02miniheap 성장과 실패를 구분
초기 free chunk보다 큰 요청에 대해 page_alloc grow 횟수와 malloc NULL을 별도 기록한다.
- 03delayed free drain 추적
heap_delayed_free 뒤 list 길이와 다음 malloc 또는 heap_trim 뒤 길이를 비교한다.
PRIMARY REFERENCES