LK · source analysis

heap_init과 allocator backend

heap_init의 부트 시점, 선택된 backend, 즉시 free와 지연 free의 소유권을 구분합니다.

이 글은 LK upstream 고정 commit 1eb9917의 구현을 설명한다. backend와 platform timer 설정은 선택한 project에서 확인한다.

Series
09 / 20
Baseline
upstream 1eb9917
Commit
1eb99171efae
Source
lib/heap/heap_wrapper.c:116-204 (발췌 범위)

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).

부트 순서와 backend 선택 구조

그림 1. heap_init 전후의 호출 경계와 세 backend
lk_main()early hook·arch/platform/target early init 뒤
heap_init()HEAP_INIT() 호출
constructors → kernel_initHEAP hook 구간은 그 사이
기본 miniheappage_first_alloc → miniheap_initfree list·mutex 초기화, 초기 영역을 free chunk로 등록
cmpctmalloccmpct_initbucket·bit 초기화 후 page allocator로 grow 시도
dlmallocHEAP_INIT은 빈 함수실제 할당은 dlmalloc backend 경로에서 수행

backend 선택은 LK_HEAP_IMPLEMENTATION 빌드 값이다. 기본은 miniheap이며 하나의 backend가 wrapper의 HEAP_*에 연결된다 (lib/heap/rules.mk:12).

할당과 두 해제 경로

그림 2. wrapper가 backend와 delayed free를 연결하는 조건
malloc(size)delayed_free_list가 비어 있지 않으면 먼저 drain
HEAP_MALLOC(size)선택된 backend로 전달
ptr 또는 NULL소유권은 반환 포인터를 받은 caller에게
일반 free(ptr)wrapper가 곧바로 HEAP_FREE(ptr) 호출
heap_delayed_free(ptr)ptr을 list node로 써서 대기열에 넣음; 다음 malloc/memalign/calloc/realloc/heap_trim이 drain
miniheap만 보면 free list 탐색 → 필요 시 chunk split → 실패 시 page_alloc grow 재시도 → free 시 이웃 chunk 병합이다. 다른 backend의 metadata는 별도로 읽는다.

heap_delayed_free()는 즉시 backend에 반환하지 않는다. 대상 block이 struct list_node를 담을 만큼 크다고 가정한다 (lib/heap/heap_wrapper.c:120, lib/heap/heap_wrapper.c:217).

초기화와 할당 책임

시점·조건실제 작업그 뒤 가능한 사용근거
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
mallocdelayed list drain 후 HEAP_MALLOC성공 ptr은 caller가 보유; 실패는 NULLlib/heap/heap_wrapper.c:153
free / delayed free즉시 backend free / 이후 drain 대기delayed block은 재사용 전까지 pendinglib/heap/heap_wrapper.c:209

miniheap의 초기 영역은 WITH_KERNEL_VM이면 한 페이지, 아니면 novm_alloc_unaligned 결과다. 고정 static arena나 모든 backend의 같은 크기를 뜻하지 않는다 (lib/heap/page_alloc.c:68).

기본 backend와 wrapper의 다른 책임

miniheap 내부 그림과 모든 backend에 공통인 wrapper 소유권을 분리했다. 실제 초기 영역은 page allocator와 선택한 platform 설정으로 확인한다.

그림 3. 기본 miniheap의 free chunk 수명

split과 coalesce는 기본 miniheap의 free list를 대상으로 한다.

01page_first_alloc 영역
02miniheap_init free chunk
03fit 탐색·충분하면 split
04없으면 page_alloc grow·1회 재시도
05ptr 또는 NULL 반환
06miniheap_free → free chunk 병합
그림 4. 할당 block과 지연 해제 block

일반 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

원본 코드

아래 코드는 LK upstream 1eb9917의 lib/heap/heap_wrapper.c에서 116-204줄을 그대로 가져온 것이다.

commit1eb99171efae98867d4be4a5bd6479ea03f43ac9anchor · L140void heap_init(void)
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)

원본 발췌와 빠진 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_init

heap_init과 constructors 순서

top/main.c L89–100

  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에 있다.

함께 읽어야 하는 원본 코드

첫 코드 조각만으로 동작이 완성되지 않는 경우 호출 매크로, 객체 정의와 실제 실행 목록을 같은 페이지에 묶었다. 각 조각은 같은 기준 commit에서 가져왔다.

01. heap wrapper에서 실제 allocation으로 들어가는 malloc

lib/heap/heap_wrapper.c 145-211줄이다.

filelib/heap/heap_wrapper.canchor · L153void *malloc(size_t size)
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)

heap_init 뒤 실제로 준비되는 것

01

부트 순서를 고정한다

thread_init_early()와 early hook, arch/platform/target early init이 먼저다. heap_init() 뒤 constructor가 실행되고 이어 kernel_init이 온다. heap 초기화를 새 bootstrap2 thread의 일로 옮겨 해석하지 않는다 (top/main.c:58).

02

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).

03

miniheap의 두 획득 경로를 구별한다

초기 영역을 먼저 쓰지만 맞는 free chunk가 없으면 lock 밖에서 heap_grow()로 page_alloc을 호출해 한 번 재시도한다. 따라서 단일 고정 arena 크기만으로 실패를 계산할 수 없다 (lib/heap/miniheap/miniheap.c:203, lib/heap/miniheap/miniheap.c:460).

04

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).

05

실제 사용량은 backend에 묻는다

miniheap은 header·정렬·최소 free chunk 크기를 반영하며, 충분한 chunk만 split한다. poison/padding 검사 등 debug 효과는 build option별로 다르다 (lib/heap/miniheap/miniheap.c:165).

세 가지 확인 지점

01

초기 영역은 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).

02

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).

03

realloc도 backend 분기를 따른다

wrapper는 HEAP_REALLOC로 넘긴다. 이 commit의 miniheap 구현은 새 크기만큼 memcpy하며 소스에 XXX wrong 주석이 있다. 기존 크기 이하만 복사한다고 가정하면 안 된다 (lib/heap/heap_wrapper.c:195, lib/heap/miniheap/miniheap.c:288).

영역과 포인터의 소유권

대상획득·등록사용·회수조건
miniheap 초기 page 영역page_first_alloc 뒤 miniheap_init초기 free chunk; 이후 backend 관리lib/heap/heap_wrapper.c:50
miniheap 추가 pagesfit 실패 시 heap_growfree chunk로 삽입; trim 조건은 backend 구현lib/heap/miniheap/miniheap.c:460
malloc 반환 ptr선택 backend의 HEAP_MALLOCcaller가 보유, free 또는 realloclib/heap/heap_wrapper.c:153
delayed ptrheap_delayed_free가 list에 넣음다음 drain 때 HEAP_FREElib/heap/heap_wrapper.c:217

초기화와 회수 실패를 구분

관찰먼저 확인할 조건근거
초기 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 NULLfree 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 내부 동작을 공통 구현으로 옮기지 않는다.

선택한 LK 빌드에서 확인

아래 ELF는 실제 project 산출물로 대체한다. nm은 C 선언이 아닌 symbol 이름을 출력한다.

목적명령 또는 계측판정
backend 선택빌드의 LK_HEAP_IMPLEMENTATION과 map 확인miniheap/cmpctmalloc/dlmalloc 중 하나의 코드
heap symbolnm -an <ELF> | grep -E '[[:space:]](heap_init|malloc|heap_delayed_free)$'심볼이 남은 빌드에서 주소 확인
초기 영역page_first_alloc의 ptr·len과 miniheap_init 인자 기록VM/novm 분기와 정렬 후 크기 일치
allocation·drainmalloc ptr, delayed list 길이, heap_trim 시각 기록pending에서 backend free까지의 지연 구분

세 가지 확인 실험

  1. 01
    초기화 순서를 log로 고정

    heap_init, constructor, kernel_init에 짧은 log를 넣어 selected project에서 실제 순서를 기록한다.

  2. 02
    miniheap 성장과 실패를 구분

    초기 free chunk보다 큰 요청에 대해 page_alloc grow 횟수와 malloc NULL을 별도 기록한다.

  3. 03
    delayed free drain 추적

    heap_delayed_free 뒤 list 길이와 다음 malloc 또는 heap_trim 뒤 길이를 비교한다.

원문과 다음 글