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 알고리즘을 이용한 할당 소스 분석입니다.