[Linux Kernel] Kernel 분석(v5.14.16) - Buddy (1)

1. Buddy System

버디 시스템은 Linux Kernel에서 사용하는 단편화 문제를 해결하기 위한 메모리 관리 기법 중 하나이다.

버디 시스템은 외부단편화 문제를 적극적으로 해결하기 위한 방편이다.

 

1) 구조

버디 시스템은 2^n 단위로 할당을 요청한다. 때문에 order 개수가 중요하다. 예를 들어 order=3인경우 8장의 page 할당을 요청하는 것이다.

예를 들어 위와 같이 메모리구조를 나타낼 수 있다. 여기서 숫자는 Buddy의 order를 의미한다. 현재 메모리에서 할당가능한 page 구조를 보면

order 1짜리가 2개

order 2짜리가 3개

order 3짜리가 2개

order 4짜리가 1개이다.

이처럼 order별로 page를 관리하고 각 order별로 관리되는 메모리는 order 값만큼 연속적으로 존재한다.
예를 들어 위 메모리를 page단위로 더 쪼개보면 아래와 같이 연속적으로 존재한다.

2page-2page-4page-8page-4page-8page-4page-16page

버디 시스템에서 order의 최대 값(한 번에 할당할 수 있는 최대 page개수는)은 시스템 환경에 따라 다르며 MAX_ORDER로 나타낸다.

 

 

 

2) 관리

• Mobility 속성과 FREE_LIST

버디 시스템의 메모리 관리는 위와 같은 버디 시스템 메모리 구조에서 할당 가능한 order들들 free_list로 관리한다.

여기서 말하는 free_list란 현재 사용하지 않는 할당가능한 메모리 영역을 말하며 여기서 연속적인 order들에 대한 합병, 분할 등의 작업이 진행된다.

예를들어 order 1과 order 1과 order 2가 연속적으로 free_list에 존재한다면 2page-2page-4page로 총 8page이기 때문에 order 3한개로 병합이 가능하다.

free_list의 구조는 위와 같다. 각 order별로 free_list를 관리하며 각 order index마다 7개의 mobility 속성을표현하는 migrate type을 가지게 된다. mobility 속성이란 위에서 언급한 병합, 분할을 진행하기 위한 속성 값들을 가지고 있는 구조체를 의미하며 속성 값에 따라서 병합이 우선시되거나 병합이 불가능한 page들이 존재하게 된다.

 

그리고 order가 2이므로 2^2 즉 4개의 page를 한 쌍으로 Linked list구조로 연결된다.

정리하면 free_list[2]를 참조하면 할당되지 않은 4개 page를 한쌍으로 가지는 Linked List구조의 헤더파일을 가리키게 된다.

그리고 이 Linked List의 원소들은 mobility속성에 따라 7개의 타입으로 나누어진다. mobility속성에 따라 보통 바로바로 사용가능한 쌍은 Linked List의 Head쪽에 배치되며 Hot이라고한다. 그리고 병합 등의 목적으로 많이 사용되는 page쌍은 Linked List의 뒷 쪽에 배치되며 Cold라고 부른다.

 

MIGRATE_UNMOVABLE 이동과 병합, 메모리 회수가 불가능한 타입으로 I/O, slab등에 사용. MIGRATE_MOVABLE 연속된 큰 메모리가 필요한 경우 현재 사용되는 페이지를 이동해서 단편화를 최소화하는 방법으로 이용되는 type이다. MIGRATE_RECLAIMABLE 이동은 불가능하지만 메모리 부족시 회수가 가능하다. MIGRATE_RESERVE 메모리 부족시 컴팩션 작업을 목적으로 별도로 관리하는 예비 목적의 영역이다. MIGRATE_CMA CMA 메모리 할당자가 별도로 관리하는 타입이다. MIGRATE_ISOLATE 커널이 메모리 회수 시스템을 가동시킬 때 마다 블록들을 스캔해서 페이지 블록에서 isolation을 진행할 때 해당 타입으로 변경하여 관리한다.

 

 

 

• page block

버디 시스템의 실제 관리는 page block단위로 진행된다. page block이란 위에서 언급한 order-n 들이 섞인 것을 의미한다.

각 order들은 당연히 order에 맞는 page개수를 가지며 각각 mobility 속성을 가진다. page block은 속성 값 order들이 가지고 있는 migrate type중 가장 많은 type을 대표 migrate값으로 가진다. 위 page table은 MIGRATE_MOVABLE이 대표 type이다.

 

그리고 실제 메모리 관점에서 보면 메모리는 page단위로 나뉘어져있고 각각의 page들은 Buddy System의 관리단위인 Page Block의 order-n에 연결되어 관리되어 진다.

 

 

3) 초기화

버디 시스템은 가상메모리 공간을 처리하는 방법이다. 때문에 버디 시스템의 초기화는 부팅 초기 memblock을 통한 할당과 page 초기화작업이 모두 진행 된 이후에 시작한다. 버디 시스템을 초기화하기 위해서는 우선 memblock을 더 이상 사용하지 않는 경우 해당 영역을 모두 free하고 버디시스템은 해당 free영역을 가지고 시작하게 된다.

 

mm/memblock.c

static void __init free_unused_memmap(void) { unsigned long start, end, prev_end = 0; int i; if (!IS_ENABLED(CONFIG_HAVE_ARCH_PFN_VALID) ||     IS_ENABLED(CONFIG_SPARSEMEM_VMEMMAP)) return; /*  * This relies on each bank being in address order.  * The banks are sorted previously in bootmem_init().  */ for_each_mem_pfn_range(i, MAX_NUMNODES, &start, &end, NULL) { #ifdef CONFIG_SPARSEMEM /*  * Take care not to free memmap entries that don't exist  * due to SPARSEMEM sections which aren't present.  */ start = min(start, ALIGN(prev_end, PAGES_PER_SECTION)); #endif /*  * Align down here since many operations in VM subsystem  * presume that there are no holes in the memory map inside  * a pageblock  */ start = round_down(start, pageblock_nr_pages); /*  * If we had a previous bank, and there is a space  * between the current bank and the previous, free it.  */ if (prev_end && prev_end < start) free_memmap(prev_end, start); /*  * Align up here since many operations in VM subsystem  * presume that there are no holes in the memory map inside  * a pageblock  */ prev_end = ALIGN(end, pageblock_nr_pages); } #ifdef CONFIG_SPARSEMEM if (!IS_ALIGNED(prev_end, PAGES_PER_SECTION)) { prev_end = ALIGN(end, pageblock_nr_pages); free_memmap(prev_end, ALIGN(prev_end, PAGES_PER_SECTION)); } #endif }

memmap영역을 free해주는 동작이다. 이전 Zone 부분을 확인할 때 보았던 mem_map에 대한 부분으로 기존 mem_map으로 되어있는 사용하지 않는 부분을 free를 통해서 메모리 해제를 진행해주고 있다. 결정적으로 free를진행하는 function은 free_memmap()이다.

 

mm/memblock.c

static void __init free_memmap(unsigned long start_pfn, unsigned long end_pfn) { struct page *start_pg, *end_pg; phys_addr_t pg, pgend; /*  * Convert start_pfn/end_pfn to a struct page pointer.  */ start_pg = pfn_to_page(start_pfn - 1) + 1; end_pg = pfn_to_page(end_pfn - 1) + 1; /*  * Convert to physical addresses, and round start upwards and end  * downwards.  */ pg = PAGE_ALIGN(__pa(start_pg)); pgend = __pa(end_pg) & PAGE_MASK; /*  * If there are free pages between these, free the section of the  * memmap array.  */ if (pg < pgend) memblock_free(pg, pgend - pg); }

free_memmap() function을 확인하면 mem_map을 통해서 physical address주소를 구하고 physcial memory area free가 진행되고 있다.

 

mm/memblock.c

static unsigned long __init free_low_memory_core_early(void) { unsigned long count = 0; phys_addr_t start, end; u64 i; memblock_clear_hotplug(0, -1); memmap_init_reserved_pages(); /*  * We need to use NUMA_NO_NODE instead of NODE_DATA(0)->node_id  *  because in some case like Node0 doesn't have RAM installed  *  low ram will be on Node1  */ for_each_free_mem_range(i, NUMA_NO_NODE, MEMBLOCK_NONE, &start, &end, NULL) count += __free_memory_core(start, end); return count; }

다음으로 free영역을 Buddy System에 전달해주는 function으로 더 이상 memblock을 사용하지 않기 때문에 memblock의 사용하지 않는 부분을 clear진행한다. 그리고 해당 영역을 포함해서 전부 free한다.

이후 __free_memory_core()은 free된 영역을 buddy system에 알려주는 역할을 진행한다. __free_memory_core()내 존재하는 __free_pages_memory()이 실제적으로 2^n단위로 버디 시스템에 free area를 전달한다

 

mm/memblock.c

static void __init __free_pages_memory(unsigned long start, unsigned long end) { int order; while (start < end) { order = min(MAX_ORDER - 1UL, __ffs(start)); while (start + (1UL << order) > end) order--; memblock_free_pages(pfn_to_page(start), start, order); start += (1UL << order); } }

위 function은 실제적으로 free영역을 2^n으로 버디 시스템에 전달하는 역할을 진행한다. order를 구하고 2^order 페이지 공간을 버디에 free시켜주고 있다. 위 과정을 반복함으로써 free area를 buddy system에 연결하고 있다.

 

 

 

• ref

코드로 알아보는 Arm 리눅스 커널

https://wogh8732.tistory.com/402

https://elixir.bootlin.com/linux/v5.14.16/source/