[분석] Linux kernel physical memory allocator (Buddy) - Part 1

Linux kernel physical memory allocator (Buddy) - Part 1

Linux Kernel 에서 physical memory 를 할당/해제 관리하는 code를 분석해 보려고 한다. Linux kernel 은 physical memory를 page 단위로 (내가 아는 system 에서는 4KB 단위) 관리하는데 이런 단위로 할당 해제하다보면 system memory 의 단편화가 발생한다.(연속적인 큰 chunk 의 메모리 부재 등) 이런 단편화를 줄이기 위해 사용하는 memory 할당/해제 알고리즘으로 Buddy를 이용한다. Buddy를 통해 연속적인 page(block) 단위의 관리가 가능하기 때문이다.

간단히 Buddy 알고리즘으로 할당/해제 하는 방식만을 알아보고 Part 1 에서는 시스템이 부팅하는 과정에서 memory를 사용한 뒤(bootmem) 시스템이 사용가능한 메모리를  physical memory allocator로 전달하기 까지 과정의 code를 분석한다.

Buddy 는 free_area 라는 구조체로 관리가 되며, 이 구조체는 zone 이라는 구조체 내부에 MAX_ORDER 크기의 배열로 선언되어 있다. MAX_ORDER 는 강제 설정이 아니라면 11 로 사용하게 된다. 

free_area 구조체를 보면

struct free_area { struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free; };

두 개의 field 가 있는데 하나는 linked list 인 free_list 이고 하나는 현재 order 의 free 한 page 들의 개수를 나타내는 항목이다. 여기서 order 의 의미를 살펴보면, buddy는 연속적인 page 관리를 위한 것이라는 것을 확인했듯이 order 라는 것은 몇 개의 연속적인 page 가 한묶음(?)인지 나타태는 숫자이다. 예를 들어, order 가 1이라면 2^1 으로 2개의 page 가 하나의 block 이 되고 order 가 10이라면 2^10으로 1024개의 page들이(4MB) 하나의 묶음이라는 것이다. 그래서 시스템이 16KB 의 메모리를 요청했다면 2^4(16), 즉 order 4인 free_area[4].free_list 에 연결되어 있는 page 를 받게 된다는 것이다. 

free_area 구조체에 page 가 매달려(?) 있는 형상을 보면 아래의 그림과 같다.

이로써 요청되는 order 에 연속적인 page 를 할당해줄 수 있는 것이다. 물론 꼭 연속적이지 않더라고 할당은 할 수 있는데 최대한 연속적인 메모리를 할당해 주려고 노력하기 위한 알고리즘인 것이다.

간단히 buddy에서 할당/해제 되는 과정을 살펴보면,

0. 가정.

  시스템의 메모리가 64KB 가 있다고 가정. 그렇다면 4KB page 가 16개 존재한다.

현재 system memory 상태,

1. Memory Allocation.

  현재 상태는 5, 10, 12, 13, 14, 15 번의 page 가 free 하다. 이와 중에 2page 를 요청하게 되면, 

  a. order 1번(2^1=2) 에서 찾는다.

  b. order 1번에 없으니 상위 order 인 2번에 가서 확인한다. 

  c. 12번 부터 연속적으로 4개가 free하덴다.

  d. 그렇다면 12번을 order 1 두개로 쪼개자.

  e. 11번 부터 요청한 2개의 page를 할당 해준다.

  f. 남은 14, 15 번은 order 1번에 가서 매달리게 된다. 

2. Memory de-allocation.

  처음 system memory 상태로 다시 돌아가서, 0 번 page 가 할당 해제 요청이 오면

  a. 0번이 해제되고 order 0 의 free_list 로 가서 붙는다.

  다시 1번의 page 가 해제 요청이 들어오면,

  a. 1번이 해제되고 order 0의 free_list 로 가서 붙는다.

  b. 해제하고 나서 buddy를 찾는다. 바로 0번 page 가 buddy가 되고(buddy 찾는 방법은 나중에...)

      두 녀석이 합쳐서 상위 order 로 가서 붙게 된다. 

  c. 결과적으로 order 0에 있던 0,1 번 page는 없어지고, order 1에 0번의 page가 붙게 되는 것이다.

여기까지 간단히 buddy 알고리즘으로 할당 해제 하는 것을 살펴 보았다. 더 상세한 내용은 코드를 분석하면서 다시 다루어 볼예정이다. 이번 part는 간략하게만 정리하고 시스템 부팅 time에 free_area로 메모리가 등록되는 과정까지 다루어 볼것이다.

Linux 가 부팅하는 일련의 과정이 start_kernel() 이라는 함수에서 시작한다.

그 중 mem_init() 함수에서 free_area 설정하는 과정까지만 살펴보도록 하자. (현재 분석하려는 소스에는 크게 상관이 없지만, ARM 기준으로 설명한다.)

<linux kernel 3.4.39 version ARM 기준>

/* * mem_init() marks the free areas in the mem_map and tells us how much * memory is free. This is done after various parts of the system have * claimed their memory after the kernel image. */ void __init mem_init(void) { unsigned long reserved_pages, free_pages; struct memblock_region *reg; int i; #ifdef CONFIG_HAVE_TCM /* These pointers are filled in on TCM detection */ extern u32 dtcm_end; extern u32 itcm_end; #endif max_mapnr = pfn_to_page(max_pfn + PHYS_PFN_OFFSET) - mem_map; /* this will put all unused low memory onto the freelists */ free_unused_memmap(&meminfo); totalram_pages += free_all_bootmem(); #ifdef CONFIG_SA1111 /* now that our DMA memory is actually so designated, we can free it */ totalram_pages += free_area(PHYS_PFN_OFFSET, __phys_to_pfn(__pa(swapper_pg_dir)), NULL); #endif free_highpages();

mem_init() 은 기본적으로 memory zone 에 있는 free page 를 찾고, memory 정보를 출력한다. 

위의 소스에서 free_all_bootmem() 내부만 살펴 볼 예정이다.

free_all_bootmem() - arch/arm/mm/init.c ==> free_all_bootmem_core() - mm/bootmem.c ==> __free_pages_bootmem() - mm/bootmem.c ==> __free_pages() - mm/page_alloc.c ==> __free_pages_ok() - mm/page_alloc.c ==> free_one_page() - mm/page_alloc.c 

위의 call flow 만 보면, 실제 system 가용한  page 들을 buddy allocator 로 전달하는 과정으로 볼 수 있다.

여기서 free_all_bootmem_core() 함수를 살펴 보자.

static unsigned long __init free_all_bootmem_core(bootmem_data_t *bdata) { struct page *page; unsigned long start, end, pages, count = 0; if (!bdata->node_bootmem_map) return 0; start = bdata->node_min_pfn; end = bdata->node_low_pfn; bdebug("nid=%td start=%lx end=%lx\n", bdata - bootmem_node_data, start, end); while (start < end) { unsigned long *map, idx, vec; map = bdata->node_bootmem_map; // bdata->node_min_pfn == 0 in my system(daeseok) idx = start - bdata->node_min_pfn; vec = ~map[idx / BITS_PER_LONG]; /* * If we have a properly aligned and fully unreserved * BITS_PER_LONG block of pages in front of us, free * it in one go. */ if (IS_ALIGNED(start, BITS_PER_LONG) && vec == ~0UL) { int order = ilog2(BITS_PER_LONG); __free_pages_bootmem(pfn_to_page(start), order); count += BITS_PER_LONG; start += BITS_PER_LONG; } else { // NOTE(Daeseok Youn) : // If bitmap has used or reserved page, each a page // passed to buddy within BITS_PER_LONG. unsigned long off = 0; while (vec && off < BITS_PER_LONG) { if (vec & 1) { page = pfn_to_page(start + off); __free_pages_bootmem(page, 0); count++; } vec >>= 1; off++; } start = ALIGN(start + 1, BITS_PER_LONG); } } page = virt_to_page(bdata->node_bootmem_map); pages = bdata->node_low_pfn - bdata->node_min_pfn; pages = bootmem_bootmap_pages(pages); count += pages; while (pages--) __free_pages_bootmem(page++, 0); bdebug("nid=%td released=%lx\n", bdata - bootmem_node_data, count); return count; }

line 9, 10 start 는 0 이 되고(아닐수도 있다.), end는 total page 개수가 된다(start 가 0 이라면) 

line 15 에서 start 에서 end 까지 loop 을 돌면서, (시스템이 부팅하면서 모든 page 는 reserved 상태였다.)

__free_pages_bootmem() 을 호출하고 마지막 단계로 free_one_page() 에서 page 들을 buddy로 넘겨 주게된다.

line 27 node_bootmem_map 은 bitmap 변수로써 page 들을 사용중인지 아닌지를 bit 로 mapping 해놓았는데, 0이면 이미 사용가능한 상태여서 free해줄 필요가 없고 1인 경우에만 free_pages_bootmem으로 넘겨주면 된다. 

(대부분이 reserved 상태이므로 1일 듯.) 예전 2.6.XX code를 봤을 때는 page 하나씩 bitmap을 비교하여 시도하지만 이 line 에서 보는 바와 같이 32bit system 이면 bit 비교 연산을 통해 한꺼번에 free를 시도하는 것이다.

예를 들어 bitmap 앞쪽 32bit가 모두 1이라면 if 문 내로 들어갈 것이며, 이는 32개의 page들이 free가능하다는 의미이므로 order 를 5로 넘겨주면 된다.(ilog2() 함수는 밑을 2로 하는 log 함수. 즉 5가된다) 

이렇게 하면 한꺼번에 free 시켜주게 된다. 

line 31 count 는 현재 free되는 page의 개수를 counting 하는 것이다.

line 33 현재 검사하는 32bit 내부에 0 이 있으면 그 32개의 bitmap은 하나씩 검사하여 free 하도록 하는 code임.

line 52 bootmem 에서 사용했던 bitmap 의 virtual address로 page 를 얻어온다. 

line 53 은 total page 개수를 계산 한 것이다.

line 54 는 전체 page 를 관리하기 위한 bitmap으로 node_bootmem_map 이라는 것을 할당 했을 것인데, 이 bitmap이 이제 사용되지 않으니 이를 위해 할당한 page 들도 해제 해준다. 만약 total page 가 4096 * 8 개 였다면 bitmap 변수는 한 page 를 차지 했을 것이고, 이를 line 56~57 에서 해제 해주는 것이다. 

이 과정이 모두 완료 된다면 buddy 에서 system memory의 형태는 대략, 

위와 같은 모양을 하게 될 것이다. 이 그림과 같이 이 시점에서는 사용하는 메모리가 거의 없으므로, 2^10(1024) page block 에 대부분 묶여 있을 것이고, 자잘하게 align 이 맞지 않거나 실제 쓰고 있는 메모리를 하위 order 에 매달아 놓게 된다. 시스템이 만약 128MB 라면(물론 kernel image가 올라가는 1M~XM, page table이 사용하는 메모리 등등 앞부분에 필요한 메모리를 빼게되면 128MB가 정확이 안떨어진다. 정말 가정인 것이다.) 

10 order free_list 에 32 개의 page 가 매달려 있을 것이다.

다음 part 에서는 실제 memory allocation 과 free 하는 code를 중심으로 분석을 해볼 예정이다.

kernel source 에 보면 free_list 에 type 이 5가지가 있는데 그것은 고려하지 않은 분석임.