infra-whale 님의 블로그
PINTOS : va를 찾아서 (작성중) 본문
핀토스 3주차가 끝나갈 무렵 의문이 생겼다.
palloc 함수를 쓰면 kva(kernel virtual address)를 반환받는 것 까지는 이해하였다. 4kb 단위로 받을 수 있으니 곧 프레임을 할당받는 것과 다름 없으리라.
그런데 pml4 페이지 테이블에서 매핑을 해줄 땐, 프레임의 kva만 있으면 안된다. 페이지의 va(virtual address)와 프레임의 kva를 연결시켜 줘야 os가 mmu를 통해 "아 이 va는 이 kva의 프레임으로 가면 찾을 수 있었지!" 하고 야무지게 쓸 것 아닌가. 그런데 우리가 va를 할당받는 법을 막상 찾아보려 하니, 생각외로 찾기 힘들었다. 이 글은 그 여정을 다뤄보려 한다.
맨 처음에는 malloc을 통해 va를 할당받는게 아닐까라는 생각을 가졌다. 구조체를 할당받을 때 malloc을 사용하니 이게 결국 va 아닐까 하는 생각이었다. 각 프로세스의 heap 영역이 있을 것이고, 여기서 메모리를 동적 할당 받고 그 주소를 가져오면 그게 va겠지!
하지만 함수를 하나씩 까보더니 그런 건 아니었다.
palloc
우선 malloc을 까보기 전에 palloc을 까보았다. 단순히 kva를 반환받는것만 알았지 정확히 이게 어떻게 동작하는진 몰랐기 때문이다. 제일 먼저 palloc.c에 있는 소개글부터 읽어보았다.
페이지 할당기. 페이지 크기(또는 페이지 배수) 단위로 메모리를 할당합니다. 더 작은 단위의 메모리를 할당하는 할당기에 대한 내용은 malloc.h를 참조하세요.
시스템 메모리는 커널과 사용자 풀이라는 두 개의 "풀"로 나뉩니다. 사용자 풀은 사용자(가상) 메모리 페이지를 위한 것이고, 커널 풀은 나머지 모든 것을 위한 것입니다. 여기서의 아이디어는 커널이 사용자 프로세스가 매우 바쁘게 스와핑(swap) 중일지라도 자체 작업을 위한 메모리를 확보할 수 있어야 한다는 것입니다.
기본적으로 시스템 RAM의 절반은 커널 풀에 할당되고 나머지 절반은 사용자 풀에 할당됩니다. 이는 커널 풀에 대해 과잉 할당(overkill)이지만, 교육 목적에서는 괜찮습니다.
핀토스 짬 3주차라면 익히 아는 내용이다. 시스템 메모리, 즉 kva 영역은 커널 풀과 사용자 풀로 나뉜다. 더 작은 단위 어쩌고 하면서 malloc 이야기가 나오는 것 같긴 하지만 우선은 넘어가자.
palloc을 쓰고 싶으면 우선 이 함수부터 실행하여야 한다. palloc_init. 페이지 할당기를 초기화하고 메모리 크기를 가져온다고 한다.
/* Initializes the page allocator and get the memory size */
uint64_t
palloc_init (void) {
/* End of the kernel as recorded by the linker.
See kernel.lds.S. */
// 링커에 의해 정의된 커널의 끝 주소
extern char _end;
// 기본 메모리 및 확장 메모리를 나타내는 구조체를 초기화한다.
struct area base_mem = { .size = 0 };
struct area ext_mem = { .size = 0 };
// 메모리 영역 정보를 수집하여 base_mem, ext_mem 구조체에 설정한다. (아래에서 볼 것)
resolve_area_info (&base_mem, &ext_mem);
// 부팅 정보를 출력한다.
printf ("Pintos booting with: \n");
printf ("\tbase_mem: 0x%llx ~ 0x%llx (Usable: %'llu kB)\n",
base_mem.start, base_mem.end, base_mem.size / 1024);
printf ("\text_mem: 0x%llx ~ 0x%llx (Usable: %'llu kB)\n",
ext_mem.start, ext_mem.end, ext_mem.size / 1024);
// 기본 메모리 및 확장 메모리 풀을 초기화한다. (아래에서 볼 것)
populate_pools (&base_mem, &ext_mem);
return ext_mem.end;
}
여기선 2개의 함수가 핵심이다. resolve_area_info 와 populate_pools.
resolve_area_info의 경우 메모리 시작부터 1MB 까지를 커버하는 구조체 base_mem이랑, 1MB부터 메모리 끝까지를 커버하는 구조체 ext_mem을 초기화한다.
populate_pools의 경우 앞서 설명한 2개의 풀을 초기화 해준다. 정확히는 init_pool을 2번 써주는데 이를 좀 더 자세히 보자.
/* Initializes pool P as starting at START and ending at END */
static void
// struct pool *p : 초기화할 풀 구조체의 포인터
// void **bm_base : 비트맵을 저장할 메모리 주소에 대한 포인터. 비트맵이 이 메모리 주소부터 할당
// uint64_t start, uint64_t end : 풀의 시작 주소와 끝 주소
init_pool (struct pool *p, void **bm_base, uint64_t start, uint64_t end) {
// 풀에 포함된 총 페이지 수
uint64_t pgcnt = (end - start) / PGSIZE;
// bitmap_buf_size (pgcnt) : 총 페이지 수를 넣기 위해 필요한 비트맵의 크기
// bm_pages : 비트맵이 차지하는 실제 페이지 수
size_t bm_pages = DIV_ROUND_UP (bitmap_buf_size (pgcnt), PGSIZE) * PGSIZE;
lock_init(&p->lock);
// bm_base를 시작으로 bm_pages의 크기 만큼의 공간을 사용하여 pgcnt만큼의 비트를 저장한다.
p->used_map = bitmap_create_in_buf (pgcnt, *bm_base, bm_pages);
p->base = (void *) start;
// Mark all to unusable.
// 비트를 모두 사용중으로 바꿔줌
bitmap_set_all(p->used_map, true);
// 다음 풀이나 데이터는 bm_base이후에 저장될 수 있도록, 크기를 늘려줌
*bm_base += bm_pages;
}간단히 말하면, bm_base 주소를 시작으로,
각 풀에 최대로 할당 될 수 있는 프레임의 수(pgcnt) 만큼의 비트를
bm_pages 만큼의 페이지에 넣어준다.
이렇게 할당한 비트를 가지고 어떤 프레임이 할당되었고 사용 가능한지를 관리 해 줄 것이다.
그러면 실제 palloc_get_multiple에선 어떻게 쓸까?
void *
palloc_get_multiple (enum palloc_flags flags, size_t page_cnt) {
// PAL_USER 플래그가 설정되어있다(4) -> user_pool
// 그 이외 -> kernel_pool
struct pool *pool = flags & PAL_USER ? &user_pool : &kernel_pool;
lock_acquire (&pool->lock);
// used_map 비트맵에서,
// 연속된 page_cnt 만큼의 비트가 false인 영역을 찾아 해당 비트를 true로 변경
// 할당 가능한 페이지가 없다면 BITMAP_ERROR를 반환
size_t page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false);
lock_release (&pool->lock);
void *pages;
// 에러 반환하지 않았다면 -> 페이지의 시작 주소를 계산한다.
if (page_idx != BITMAP_ERROR)
pages = pool->base + PGSIZE * page_idx;
else
pages = NULL;
// 할당 성공 시
if (pages) {
// 플래그에 PAL_ZERO(2)가 있다면 -> 모두 0으로 초기화
if (flags & PAL_ZERO)
memset (pages, 0, PGSIZE * page_cnt);
// 할당 실패 시
} else {
// 플래그에 PAL_ASSERT(1)가 있다면 -> 커널 패닉
if (flags & PAL_ASSERT)
PANIC ("palloc_get: out of pages");
}
return pages;
}기타 부가적인 로직을 제외한다면, 저기서 핵심은
size_t page_idx = bitmap_scan_and_flip (pool->used_map, 0, page_cnt, false); lock_release (&pool->lock);
부분이다.
해당하는 pool의 page_cnt만큼 연속되는 false 비트를 찾고, 있다면 true로 바꿔준다. 이때 몇 번째 비트가 바뀌었는지 확인하고, 이걸 이용해서 kva 공간의 어느 주소가 할당되는지 계산한다.
말이 길었지만 우리가 익히 알듯, palloc은 kva를 반환한단 걸 알 수 있다.
여기까지 온 김에 palloc_free_multiple도 보고 가면 좋을 듯 하다.
void
palloc_free_multiple (void *pages, size_t page_cnt) {
struct pool *pool;
size_t page_idx;
// 페이지 정렬 여부, 등등 체크
ASSERT (pg_ofs (pages) == 0);
if (pages == NULL || page_cnt == 0)
return;
// 현재 쓰이는 풀 결정
if (page_from_pool (&kernel_pool, pages))
pool = &kernel_pool;
else if (page_from_pool (&user_pool, pages))
pool = &user_pool;
else
NOT_REACHED ();
// 페이지 인덱스 계산
page_idx = pg_no (pages) - pg_no (pool->base);
#ifndef NDEBUG
memset (pages, 0xcc, PGSIZE * page_cnt);
#endif
// 해제하려는 페이지 모두가 사용중인지 확인
ASSERT (bitmap_all (pool->used_map, page_idx, page_cnt));
// 사용중이었던(true) 비트 모두 false로 설정
bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false);
}가장 중요한건 1줄이다.
bitmap_set_multiple (pool->used_map, page_idx, page_cnt, false)을 사용하여, 해당 kva가 비트맵의 몇 번째인지를 넘겨주고, 그 비트 모두를 false(사용 가능)으로 설정한다.
지금까지 설명한 내용을 그림으로 표현하면 이렇게 된다.
맨 위 페이지는 비트맵으로 쓰이고, 그 이후는 실제 프레임이 할당된다. 그림상에서 커널 풀에 할당된 비트맵이 1101이 아니라 0101로 보이지만 넘어가는걸로.
malloc
그 다음은 앞서서 말했듯 malloc을 살펴보았다. 우선 malloc.c의 소개글은 다음과 같다.
malloc()의 간단한 구현:
각 요청의 크기(바이트 단위)는 2의 거듭제곱으로 반올림되고, 해당 크기의 블록을 관리하는 "디스크립터(descriptor)"에 할당됩니다. 디스크립터는 빈 블록의 목록을 유지합니다. 만약 이 목록이 비어 있지 않다면, 목록에 있는 블록 중 하나를 사용하여 요청을 처리합니다.
그렇지 않으면, "arena"라고 불리는 새로운 페이지의 메모리가 페이지 할당자로부터 획득됩니다 (만약 사용할 수 있는 페이지가 없다면, malloc()은 null 포인터를 반환합니다). 새로 할당된 arena는 여러 블록으로 나누어지며, 이 블록들은 모두 디스크립터의 빈 블록 목록에 추가됩니다. 이후 새 블록 중 하나를 반환합니다.
블록을 해제(free)할 때는 그 블록을 해당 디스크립터의 빈 블록 목록에 추가합니다. 그러나 그 블록이 속한 arena에 더 이상 사용 중인 블록이 없다면, arena의 모든 블록을 빈 블록 목록에서 제거하고, 해당 arena를 페이지 할당자에게 다시 반환합니다.
이 방식으로는 2KB보다 큰 블록은 처리할 수 없습니다. 왜냐하면 그것들은 디스크립터와 함께 단일 페이지에 맞추기에는 너무 크기 때문입니다. 이러한 경우에는 페이지 할당자로부터 연속된 페이지들을 할당받고, 할당된 블록의 arena 헤더에 할당 크기를 기록하여 처리합니다.
블록을 할당받거나 페이지를 할당받는다고 한다. 페이지? 프레임이랑 매핑되는 그 페이지? 드디어 va가 어디서 나온지 찾은 걸까?
아까처럼 순서대로 차근차근 보도록 하자. 먼저 malloc_init이다.
void
malloc_init (void) {
size_t block_size;
// 각 블록 사이즈별로 경우를 나눈다..
// 2^4 ~ 2^10
for (block_size = 16; block_size < PGSIZE / 2; block_size *= 2) {
struct desc *d = &descs[desc_cnt++];
// 배열의 총 크기를 하나의 요소 크기로 나누어서, 배열 안에 있는 요소의 개수를 구한다.
ASSERT (desc_cnt <= sizeof descs / sizeof *descs);
d->block_size = block_size;
// PGSIZE에서 struct arena의 크기를 제외한 나머지를 블록 크기로 나눈다 -> 블록 개수를 구한다.
d->blocks_per_arena = (PGSIZE - sizeof (struct arena)) / block_size;
list_init (&d->free_list);
lock_init (&d->lock);
}
}위에서 설명한 대로 블록 크기별로 각 디스크럽터를 정의하고 있다. PGSIZE는 4kb이니, 블록사이즈는 2kb보다 작으면서 2의 제곱수여야 하고, 즉 16부터 1024 바이트까지 사용이 가능하다.
여기까지 많이 헤메었다. 이제 malloc이 어떻게 이루어지는지 볼 차례다.
void *
malloc (size_t size) {
struct desc *d;
struct block *b;
struct arena *a;
/* A null pointer satisfies a request for 0 bytes. */
if (size == 0)
return NULL;
/* Find the smallest descriptor that satisfies a SIZE-byte
request. */
// 배열을 돌면서, size에 맞는 디스크립터를 찾는다.
// ex : size가 92 -> 블록 크기 128
for (d = descs; d < descs + desc_cnt; d++)
if (d->block_size >= size)
break;
// 디스크립터가 없는 경우 : 블록 단위로 할당할 수 없는 경우(너무 커서)
if (d == descs + desc_cnt) {
/* SIZE is too big for any descriptor.
Allocate enough pages to hold SIZE plus an arena. */
// 필요한 페이지 수를 구한다.
size_t page_cnt = DIV_ROUND_UP (size + sizeof *a, PGSIZE);
// 구한 수 만큼 palloc을 해준다.
// 첫 인자 0 -> 커널 풀에 할당한다.
a = palloc_get_multiple (0, page_cnt);
if (a == NULL)
return NULL;
/* Initialize the arena to indicate a big block of PAGE_CNT
pages, and return it. */
// 아레나 구조체를 세팅하고, 아레나 바로 다음 메모리 주소를 반환한다.
// 이 주소부터 저장하면 된다.
a->magic = ARENA_MAGIC;
a->desc = NULL;
a->free_cnt = page_cnt;
return a + 1;
}
lock_acquire (&d->lock);
/* If the free list is empty, create a new arena. */
// 리스트 비어있을 경우 palloc으로 가져와서 블록 사이즈로 나눠준다.
if (list_empty (&d->free_list)) {
size_t i;
/* Allocate a page. */
a = palloc_get_page (0);
if (a == NULL) {
lock_release (&d->lock);
return NULL;
}
// 아레나 구조체를 세팅한다.
/* Initialize arena and add its blocks to the free list. */
a->magic = ARENA_MAGIC;
a->desc = d;
a->free_cnt = d->blocks_per_arena;
// 해당 디스크립터의 블록 수 만큼 반복
for (i = 0; i < d->blocks_per_arena; i++) {
// 페이지에서 아레나 뺀 나머지 크기로 블록을 만들어서 free list에 넣어준다.
struct block *b = arena_to_block (a, i);
list_push_back (&d->free_list, &b->free_elem);
}
}
/* Get a block from free list and return it. */
// free list에서 블록 하나 뺀다.
b = list_entry (list_pop_front (&d->free_list), struct block, free_elem);
// 블록에 해당하는 아레나를 찾는다.
a = block_to_arena (b);
a->free_cnt--;
lock_release (&d->lock);
return b;
}뭔가 좀 이상하다.
아레나 구조체 같은 처음 보는 개념은 제쳐두고라도, malloc은 2가지 경우의 로직을 가진다.
1. size가 디스크럽터를 할당하지 못 할 정도로 큰 경우, malloc은 내부적으로 palloc_get_multiple을 호출한다.
2. 디스크럽터를 호출하였으나, free 리스트가 비어있는 경우, malloc은 내부적으로 palloc_get_page를 호출한다.
즉 malloc이라고 va를 계산하는 것이 아니라, 단순히 프레임을 받아온 후, 그것을 블럭 단위로 자르거나 프레임을 묶어서 반환할 뿐이다.
역시 아쉬우니 free 까지는 보고가자.
void
free (void *p) {
if (p != NULL) {
struct block *b = p;
struct arena *a = block_to_arena (b);
struct desc *d = a->desc;
// 디스크럽터 존재 -> 사이즈가 엄청 크지 않음
if (d != NULL) {
/* It's a normal block. We handle it here. */
// NDEBUG가 정의되지 않은 경우 -> 디버깅 목적인 경우
#ifndef NDEBUG
/* Clear the block to help detect use-after-free bugs. */
// 블록 전체를 0xcc로 초기화 한다.
// 이를 통해, 잘못된 접근을 시도 시 오류를 발생시킨다.
memset (b, 0xcc, d->block_size);
#endif
lock_acquire (&d->lock);
/* Add block to free list. */
// free_list에 추가한다.
list_push_front (&d->free_list, &b->free_elem);
/* If the arena is now entirely unused, free it. */
// 아레나의 free_cnt가 blocks_per_arena 이상 : 안 쓰는 아레나
if (++a->free_cnt >= d->blocks_per_arena) {
size_t i;
ASSERT (a->free_cnt == d->blocks_per_arena);
// 요소를 전부 삭제
for (i = 0; i < d->blocks_per_arena; i++) {
struct block *b = arena_to_block (a, i);
list_remove (&b->free_elem);
}
// 페이지도 free
palloc_free_page (a);
}
lock_release (&d->lock);
// 디스크럽터가 없음 -> 사이즈 엄청 큼
} else {
/* It's a big block. Free its pages. */
// 페이지 여러개 free
palloc_free_multiple (a, a->free_cnt);
return;
}
}
}이 경우도 마찬가지로 메모리 해제를 해줄 시, palloc_free_page 혹은 palloc_free_multiple를 호출한다. malloc 역시 kva를 다룬다는 것이다.
이를 그림으로 정리하면 아래와 같이 된다.
총정리
위 2가지 개념을 하나의 그림에 정리하면 아래와 같이 된다.
죄다 팀원이 그려준 그림뿐이다. 내가 그린 그림도 있지만 워낙 처참해서 올리긴 힘드니 이해바란다. 각설하고 malloc을 하던 palloc을 하던 간에 결국 kva 공간에서만 할당이 되고 커널 베이스 아래는 전혀 쓰질 않는 것을 알 수 있다.
이렇게 결론을 내린 직후, 팀원들이랑 함께 혼란에 빠졌다. 어떠한 경우에도 va를 만들수가 없다니. 그러면 우리가 여태껏 잘 써왔던 va는 대체 어디서 왔다는 걸까? 가상 주소이니 모든것은 허상이라 생각하고 넘겨야 하는걸까? 그렇다기엔 우린 PML4에 매핑 할때 va를 실제로 쓴 기억이 있는데?
이말인 즉슨 va를 썼던 함수부터 역으로 따라가면 이 친구가 어디에서 온 건지 알수 있는 것 아닐까?