Daeseok's Blog

Linux kernel physical memory allocator (Buddy) - Part 2

이전 buddy 초기화 관련 글에 이어 Buddy allocation/free 를 중심으로 Code 분석을 진행한다. 

(쓰다보니 allocation 만 해도 소스를 붙여 넣다 보니 분량이 조금 나와서 free 는 다음 파트로 넘기기로 했습니다. :) )

1. Allocation

  - alloc_page() 함수 call 에서 실제 buddy를 만지는(?) code까지 call flow 를 보면 아래와 같다.

  사실 call flow 의 __alloc_pages_nodemask() 까지는 특별히 내가 설명할 내용은 없어 보인다. 실제 __alloc_pages_nodemask() 함수 내에서 get_page_from_freelist() 함수를 통해 page를 받아 return 하는 것이다. 

code를 보자.(이 blog 에 syntax highlight를 위해 plugin 을 사용하는데, 아래의 code가 그냥 하얀 박스에 성의없이 나온다면 lxr.linux.no site 의 함수 link를 남겨 놓을테니 들어가서 보시면 됩니다. line number는 이 블로그의 code에 맞춘 것입니다.)

line 35 선호하는 zone 을 preferred_zone 으로 갖고 온다. 

line 44 get_page_from_freelist() 를 통해 특정 zone으로 부터 page 를 받아 온다.

line 48 get_page_from_freelist() 를 통해 page 를 할당 받지 못하는 경우에 수행하는 함수이다. 다음 part에서 살펴 보겠지만, 내가 아는 page allocation 실패의 주요 이유는 driver level 에서 kmalloc 을 통해 연속적인 page 를 요청했는데 free memory 는 충분하나 연속적인 메모리가 없는 경우이거나 정말 나눠줄 메모리가 없는 경우 등이 있다. 이런 경우에 정리 및 retry 를 위해 __alloc_pages_slowpath() 함수를 호출 하여 COMPACTION 을 하거나 process를 죽이고 메모리 확보등의 여러가지 행동 들을 한다. compaction 관련해서 lwn 을 번역해 놓은 문서가 이 블로그에 있다. ^^

line 61~64 정상적으로 할당이 되어얐다면 page structure pointer 를 넘기고 아니면 NULL 넘긴다. NULL 이라면 allocation 실패다. 

call flow 를 참조하시고, 이제 buffered_rmqueue() 함수를 살펴 보자.

line 2 order 가 0인 요청(page 1개 == 4096byte)의 경우와 아닌 경우로 분리하여 할당 요청함.

line 7 per_cpu_pages 구조체의 list 에서 바로 할당 해줄 수 있다면

line 20 에서 page 를 바로 얻고 return 해줄 수 있다. 하지만 per_cpu_pages 가 없다면 __rmqueue_bulk() 에서 한번에 page 들을 할당 해놓는다. 예상 컨데 per_cpu_pages 의 list 에 매달린 page의 단위는 order 0일 뿐일 것이다.

line 24 order 가 0 보다 크다면(요청 크기 > 4096) __rmqueue() 를 호출하여 Buddy를 이용하여 연속적인 physical memory를 할당해준다. buddy 를 이용하는 부분을 다음 소스에서 살펴 보자.

__rmqueue() 는 __rmqueue_smallest() 함수의 순으로 호출하는데, 일반적으로 잘 되는 경우에는 __rmqueue_smallest() 에서 free_list 의 page 를 return해준다. 아래는 __rmqueue_smallest()

이 함수로 넘어오는 경우의 시나리오를 먼저 세우면,(가장 간단한 case)

1. order 는 1 이상(4라고 하자)

2. 현재 order 4의 free_list 에는 free 한 page 가 여럿 있다.

line 14 에서 current_order 는 4 이고 MAX_ORDER 는 11 이다.

line 15 area 는 order 4의 free_area 의 주소를 갖고 있다. (free_area 그림을 다시 보고 싶다면 지난 part 1 블로그를 보시는 게 좋을 듯 한다.)

line 16 은 free_area 의 free_list 가 비어있는지 아닌지 확인 한 후에, 있다고 가정 했으니 다음으로

line 19 free_list 에서 page structure 를 갖고 온다. 

line 21 은 page lru list 에서 현재 할당될 page 를 빼주고

line 23 free_area structure 내부에서 page 하나가 빠졌으니 nr_free 를 하나 감소시킨다

line 23 expand() 함수는 현재 요청한 order(4) 에 free 한 page 가 하나도 없다면 상위의 order 에서 제공되고 제공된 뒤에 상위의 order 에서 갖고 왔으니 남은 부분은 하위의 order 에 다시 붙여 줘야 한다. 그 하위 order 에 남은 page 를 붙여주는 작업이 expand() 에서 일어난다.

이제 expand() 함수가 수행되는 과정으로 시나리오를 다시 잡아 보자.

1. order 는 1이상(4라고 하자)

2. 현재 order 4의 free_list 의 nr_free 값은 0 이다 (즉 가능한 page 가 없다는 것임.)

line 14 에서 current_order 4 에서 시작하는 것은 같다. 하지만

line 16 에서 order 4의 free_area의 free_list 에는 page 가 없기 때문에 

line 17 의 continue가 수행될 것이다.

line 14 로 다시 돌아가서 이제 current_order 가 5가 된다.

line 16 에서 확인 해보니 몇개가 있단다

line 19 에서 현재 order 5의 free_list 에서 page 를 갖고 온다.

자 여기서 문제(?)가 발생했다. 요청한 것은 order 4 인 (4K * 2^4) 인데 order 5에서 할당 해줬다.

일단 page 는 넘기되 상위 order 의 page 는 바로 하나 아래 하위 order 보다 딱 2배 더 많은 page 를 갖고 있으니까 반짤라서 남은 page 를 하위에 붙여 주면 된다. 

그일은 expand() 에서 하게 된다. expand() 를 살펴보자.

간단합니다. expand() 를 호출 하기 전에 low 는 실제로 요청한 4가 되고 high 는 order 4에서 받지 못해 상위에 요청을 했었으니 5가되고 area structure 는 order 5의 free_area[5] 입니다. migratetype 은 신경 안쓰도록 합니다. page 구조체는 order 5의 free_list 에서 가져온 page 입니다.

line 5 의 size 값은 1 << 5 가 되니 32 가 됩니다.

line 7 은 high(5) > low(4) 일때 까지~

line 8~11 area-- 합니다. 그렇게 되면 area는 order 4의 free_area 가 됩니다.(free_area[4]), high-- 합니다. high 는 4가 됩니다. size >>=1 은 32 에서 16으로 바뀝니다. VM_BUG_ON 은 그 page 의 address 가 유효한지 테스트 합니다.

CONFIG_DEBUG_PAGEALLOC 부분은 pass 합니다.

line 29 order 4의 free_list 에 &page[size] 를 메달아 줍니다. page[size] 는 현재 page address 는 order 5에 있던 것입니다. 그렇다는 것은 page address 에서 부터 32의 page 가 연속적인 상태로 있었단는 것이고, order 4에 내려와서 16개의 page를 할당 해줬으니 0~15까지는 allocated 상태인것이고 16~31 까지는 하위 order 인 4에 메달아 줘야 하는 것이다. 그래서 &page[size] 를 달아주면 16~31 까지를 order 4에 달아 주는 것이다.

line 30 order 4의 nr_free 를 증가.

line 31 현재 page 를 현재 order 에 맞게 설정함.

여기 까지가 buddy 알고리즘을 이용한 할당 소스 분석입니다. 

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 구조체를 보면

  현재 상태는 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() 은 기본적으로 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() 함수를 살펴 보자.

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가지가 있는데 그것은 고려하지 않은 분석임.