heap_init과 allocator backend

QUESTION

heap_init과 allocator backend 단계에서 실제로 바뀌는 상태는 무엇인가?

STRUCTURE

객체와 주소가 놓이는 구조

CALL PATH

실행 흐름

STATE LEDGER

단계별 입력과 출력

각 단계의 입력과 처리 후 바뀌는 상태를 정리한 표다. 사용 중인 소스 버전에서 다른 필드를 변경한다면 그에 맞춰 표도 수정한다.

분석 범위의 전제와 비교해, 다음 단계에 잘못된 입력을 넘긴 부분부터 조사한다.

VISUAL WALKTHROUGH

주소와 객체의 이동을 그림으로 읽기

아래 그림은 주소, 객체를 사용하는 기간, 제어권을 넘기는 시점을 중심으로 정리했다. 실제 주소와 크기는 사용 중인 보드의 bdinfo, 맵 파일과 링커 심벌로 확인한다.

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

발췌 범위와 읽기 기준

원문 116-204줄에는 앞뒤 문맥이 포함됩니다. 기준 구문 void heap_init(void)은 L140에 있습니다. 발췌 첫 줄을 함수 정의의 시작으로 해석하지 않습니다.

heap 시작·끝과 linker image, boot allocator 영역의 겹침을 먼저 확인한다. wrapper 아래 backend가 miniheap인지 dlmalloc인지도 project 설정에 따라 달라진다.

RELATED SOURCE

함께 읽어야 하는 원본 코드

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

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

내부 동작을 더 깊게 읽기

IMPLEMENTATION NOTES

구현을 읽을 때 놓치기 쉬운 부분

OBJECT LIFETIME

객체와 수명

FAILURE PATH

실패 지점과 증상

로그가 끊긴 함수뿐 아니라 그 함수에 주소, 크기, 플래그를 전달한 앞 단계도 조사한다. 오류 처리 후 등록된 객체나 하드웨어 설정이 그대로 남아 있는지도 확인한다.

EVIDENCE

소스 밖에서 확인할 증거

소스에서 파악한 동작을 실제 빌드 결과와 대상 보드의 로그로 확인한다. 아래 명령의 보드 이름과 툴체인 접두사는 사용 중인 빌드 환경에 맞게 바꾼다.

LAB

직접 확인할 실험

1. 01
   heap base/end를 map과 대조

   heap_init 진입 전후에 heap span의 주소·크기·반환값과 timestamp를 함께 남긴다.

2. 02
   할당 크기별 alignment 검사

   allocator metadata 진입 전후에 allocator headers의 주소·크기·반환값과 timestamp를 함께 남긴다.

3. 03
   allocation failure를 주입해 caller 처리 확인

   malloc/free 진입 전후에 allocated blocks의 주소·크기·반환값과 timestamp를 함께 남긴다.

PRIMARY REFERENCES

원문과 다음 글