리눅스 Linux) Linux kernel physical memory allocator : 버디 (Buddy) 메모리 할당자의 개념, 메모리 할당 및 해제 프로세스, 구조

Linux kernel physical memory allocator : 버디 (Buddy) 메모리 할당자

---

Introduction

• 리눅스 커널은 phyical memory를 page 단위(보통 4KB)로 관리한다.
• 사이즈가 고정된 page 단위의 메모리 할당 및 해제는 메모리 fragmentation을 유발한다.
• fragmentation 문제를 줄이기 위해 Linux에서는 Buddy 메모리 할당 및 해제 알고리즘을 사용한다.

Buddy

• buddy란
  • 연속적인 page (block) 단위로 메모리 관리가 가능하다.
  • 즉, 연속적인 page 관리를 위한 메모리 할당/해제 알고리즘
  • buddy: 물리적 메모리 상에서 해당 page에 인접한 page들을 의미한다.
• struct free_area
  • free_list : 연결리스트
  • nr_free : 현재 order의 free한 page의 개수를 나타내는 변수, 몇 개의 연속적인 page가 한 block에 포함된 것인지 나타내는 값
  • ex) order = 8 ⇒ $1 block = page * 2^8$
  • 시스템이 16(2^4)KB의 메모리를 요청하면 free_area[4].free_list의 연속적인 page를 할당받는다.
  • 요청되는 order에 대하여 최대한 연속적인 page를 할당하려고 하는 greedy 알고리즘

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

 

• 할당 및 해제 프로세스
  • 시스템 메모리가 64KB (4KB * 16) 이라고 가정
  • 0-15 : 실제 physical memory를 나타낸다.
  • free : 5, 10, 12, 13, 14, 15
  • free_area[2]는 연속적인 page가 2^2개를 가지고 있다. 12-13-14-15는 4개의 page가 연속적이므로 order = 2에 있다.
  • free_area[0]는 연속적인 page가 2^0, 즉 1개 있는 free page 들을 연결리스트로 관리한다. 그래서 연속된 page가 없는 5와 10을 order=0에 연결한다.
  • free_area.free_list의 각 칸은 order를 나타낸다.

memory allocation

• a. 2 page 요청
• b. order = 1 (2^1)에서 찾는다.
• c. order = 1 d이 없기 때문에 상위 order = 2 에 가서 찾는다.
• d. 12-13-14-15, 4개가 연속적이므로 12번을 order = 1 두개로 쪼갠다.
• e. 12, 13 연속 page를 할당한다.
• f. 남은 14, 15는 order = 1에 연결된다.

memory de-allocation

• a. 처음 가정의 메모리 상태로 돌아가서 0번 page 할당 해제 요청
• b. 0번 할당이 해제되고 free_area[0]에 연결된다.
• c. 1번 할당 해제 요청이 들어오면 위와 같이 할당이 해제되고 free_area[0]에 연결된다.
• d. 해제 후, budd를 call한다.
• e. 0번 page가 buddy가 되고 1이 buddy인 0 과 합쳐져 order=1에 연결된다.

• 시스템 부팅시 free_area가 메모리로 등록되는 과정
  • Linux 부팅 과정은 start_kernel() 함수에서 시작
  • 그 중 mem_init() 함수에서 free_area를 설정하는 과정
  • mem_init() : memory zone에 있는 free page를 찾고, memory 정보를 출력
  • free_all_bootmem()
    • → start에서 end(total page 개수) 까지 loop을 돌면서 __free_pages_bootmem()을 호출하면서 free_one_page()에서 page들을 buddy로 넘겨준다.
    • → noew_bootmem_map은 bitmap의 변수로 page 사용여부를 bit로 mapping 해둔다. 0 이면 이미 사용가능한 상태이기 때문에 free 해 줄 필요가 없고 1 인 경우 free_pages_bootmem으로 넘긴다.
    • ** reserved한 상태의 page = 1

allocation : alloc_page()

• __alloc_pages_nodemask() 함수 내에서 get_page_from_freelist() 함수를 호출하여 page를 받아 return 한다.
• 선호하는 zone을 preferred_zone으로 가져온다.
• get_page_from_freelist()를 통해 특정 page를 할당받지 못하는 경우, memory 정리, retry를 위해 __alloc_pages_slowpath()를 호출하여 compaction을 하거나 process를 kill 하여 메모리를 확보한다. page가 정상적으로 할당 되면 page structure pointer를 넘기고, 아니면 NULL을 넘긴다. (NULL = allocation failed)
• buffered_rmqueue()
  • → order = 0 요청인 경우와 아닌 경우로 분리하여 할당 요청을 한다.
  • → per_cpu_page 구조체 list에서 할당하면 바로 page를 할당하고 return
  • → per_cpu_page가 없는 경우 __rmqueue_bulk()로 한번에 page들을 할당
  • ** 보통 per_cpu_page 구조체 리스트에 달린 page는 대부분 order = 0
  • → order = 0 보다 큰 요청이 들어오면 __rmqueue()를 호출하여 buddy를 이용하여 연속적인 메모리를 할당한다.
• __rmqeue() : __rmqueue_smallest()함수 순으로 호출하여 free_list의 page를 return한다.
  • → free_area의 free_list가 비어있는지 확인하고 비어있지 않다면 free_list에서 page 구조체를 가져온다.
  • → page LRU list에서 현재 할당될 page를 빼주고, 해당 page 구조체의 nr_free를 하나 감소시킨다.
  • ** expand() 함수는 현재 요청한 order에 맞는 free page가 없으면 상위의 order에서 제공하고 남는 부분을 하위 order에 붙이는 작업을 위해 호출된다.

de-allocation : free_pages()

• free_pages() 는 파라미터로 virtual address와 order을 받는다.
  • → virtual address를 page단위로 변환하고 order에 따라 그 사이즈를 계산한다.
  • **free_pages() ~ free_pages_ok() 이 사이에 free_hot_cold_page() 함수가 있다. 이 함수는 order = 0일 경우에만 동작하는데 order 0의 cold한 page를 per_cpu_page구조체에 가지고 있다가 필요한 경우 가져다 쓰는 것
• free_one_page()
• free_pages()로 넘어온 virtual address를 physical address로 변한한 주소와 해제하려는 size를 order로 변환하여 파라미터로 받는다.
• page_idx (page frame number)를 구하는 공식 :
  • __page_to_pfn(page) { return page (physical) address - mem_map + ARCH_PEN_OFFSET }
  • ⇒ page가 mem_map에서 몇번째에 있는 page인지 알 수 있다.
  • ex) 현재 free하려는 Index가 1이고, order 가 1이라면 page_idx 는 0이 된다. order = 1에서 2번 page frame의 buddy는 0번 page frame이다.
• page_is_buddy()
  • → buddy page가 사용가능한 page인지 확인
  • → 현재 요청한 page와 buddy가 같은 zone에 있는지 확인
  • → buddy의 order가 해제 요청한 page의 order와 같은지 비교
  • ⇒ buddy가 맞고, 같은 order의 free_list에 있다면 free_list[order]의 nr_free를 1 감소시키고, buddy의 page 속성 중 LRU list에서만 제거한다.

Structure of Buddy System

• zone 마다 free page를 관리하는 free list를 가지고 있다.

struct zone { 
	...
	struct free_list[MAX_ORDER]
	...
}

• free_area는 연속적인 page를 page block 별로 관리한다.
  
  • free_area[order].free_list = 2^order 개의 연속적인 free page 리스트를 가지고 있다.
  • free_area[order].free_list = 2^order 개의 연속적인 free page 리스트를 가지고 있다.
  • movable → user space 로 할당
  • unmovable → kernel space 로 할당
  • head 쪽으로 갈수록 hot, tail 쪽으로 갈수록 cold
  • hot은 다시 할당되어 사용될 가능성이 높은 것을 의미하고, cold는 병합되어 order가 올라갈 가능성이 높은 것을 의미한다.
  • 같은 migration type 끼리 가능한 붙어있게 하면 페이지 회수 및 메모리 컴팩션 과정의 효율성이 높아진다.
  • free_list에서 free page가 짝을 이루면 order가 더 높은 free_list로 합병되어 올라가고, 필요시 분할하여 더 작은 order로 나뉠 수 있다
  • nr_free는 현재 order의 모든 페이지 type들의 free page 수를 나낸다.

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

• fallback
  • order에 해당하는 free page block이 연결되고, node의 각 zone마다 가지고 있는 free_list에서 할당하게 되는데 이때, movable, unmovable이 부족한 경우, 서로 다른 종류의 페이지로 fall back
  • migrate_unmovable → migrate_reclamable → migrate_movable
  • migrate_movable → migrate_reclamable → migrate_unmovable
  • node_zones는 현재 노드에서 각 zone에 해당하는 zone struct 배열
    => node_zones는 현재 노드에서 각 zone에 해당하는 zone struct 배열
    
  • nr_zones는 현재 노드가 가진 zone의 수를 나타냄
  • node_zonelists
    1. 현재 zone에 할당할 수 있는 free page가 충분하지 않을 경우, 다른 node에 메모리를 할당하기 위한 node list
    2. 현재 node 내에서의 zone type 별 fallback list

struct pglist_data {
	struct zone node_zones[MAX_NR_ZONES];
	struct zonelist node_zonelists[MAX_ZONELISTS];
	int nr_zones;
	...
}

• order
  • 버디 시스템에서 페이지 할당 요청 단위
  • ex) order = 3 ⇒ 2^3 = 8개의 연속적인 page 요청을 의미
  • 한번에 최대 할당 가능한 페이지 수 = 2^(MAX_ORDER-1)개