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

1. Buddy 할당

할당하는 방법은 매우 단순하다 할당에 필요한 memory size를 확인하고 해당 size를 커버할 수 있는 가장 작은 order로 alloc 요청을 진행한다.

단 이 과정에서 free memory area 부족으로 실패가 되면 그 바로 위 order의 MOVABLE_HIGHATOMIC type의 page를 대상으로 다시 alloc을 진행한다.

 

예를 들어 위와 같이 buddy system이 구성되어있을 때 8KB 메모리를 할당한다고 하자(Page당 4KB로 가정) 이 경우 order = 1 에 할당을 시도하게 되고

위와 같이 free_list를 참조하여 linked list를 확인했을 때 정상적으로 page area가 존재한다면 해당 page 할당을 진행하게 된다.

할당을 진행할 때는 따로 옵션을 설정하지 않는다면 HOT을 우선적으로 사용하게 된다.

 

만약 free_list로 갔는데 위와같이 할당할 page가 존재하지 않는다면 order 2를(MIGRATE_HIGHATOMIC) 참조하게 된다.

order 2를 쪼개서 order 1의 2개의 Linked List Index를 만들게되고 할당을 진행한다.

 

 

할당이 완료되면 결국에는 위와 같은 free_list가 만들어질 것이다.

 

mm/page_alloc.c

struct page *__rmqueue_smallest(struct zone *zone, unsigned int order, int migratetype) { unsigned int current_order; struct free_area *area; struct page *page; /* Find a page of the appropriate size in the preferred list */ for (current_order = order; current_order < MAX_ORDER; ++current_order) { area = &(zone->free_area[current_order]); page = get_page_from_free_area(area, migratetype); if (!page) continue; del_page_from_free_list(page, zone, current_order); expand(zone, page, order, current_order, migratetype); set_pcppage_migratetype(page, migratetype); return page; } }

할당하고자 하는 size에 맞는 가장작은 order부터 호출함으로써 alloc을 진행하는 function이다. function을 보면 반복문을 통해 가장 작은 order에서부터 free_list를 확인하고 할당을 진행하고 있다.

과정 중에 del_page_from_free_list() funtion은 free_list에서 할당한 영역만큼 제거를 해주는 역할을 진행한다.

그리고 expand()의 경우 위에서 언급한 바와 같이 만약 해당 order에 적당한 page가 없어서 더 상위 order로부터 분해해서 할당을 진행한 경우 분해하고 남은 page들을 정리하는 작업이다.

 

 

1) rmqueue_fallback

먼저 Buddy system은 page block단위로 동작한다고 했다. 그리고 page block은 다양한 order를 가지는 page들로 구성되어 있다. 그리고 이러한 page 중 가장 많은 type을 대표 type을 가진다.

다시 할당얘기로 돌아와서 alloc을 진행할 때 상위 order로 가면서 찾아보아도 할당가능한 MIGRATE_HIGHATOMIC page공간이 부족한 경우가 있을 수 있다.

이 경우 rmqueue_fallback을 통해서 MOVABLE type의 page를 분리하여 alloc할 area를 확보한다.

 

mm/page_alloc.c

static __always_inline bool __rmqueue_fallback(struct zone *zone, int order, int start_migratetype, unsigned int alloc_flags) { struct free_area *area; int current_order; int min_order = order; struct page *page; int fallback_mt; bool can_steal; /*  * Do not steal pages from freelists belonging to other pageblocks  * i.e. orders < pageblock_order. If there are no local zones free,  * the zonelists will be reiterated without ALLOC_NOFRAGMENT.  */ if (alloc_flags & ALLOC_NOFRAGMENT) min_order = pageblock_order; /*  * Find the largest available free page in the other list. This roughly  * approximates finding the pageblock with the most free pages, which  * would be too costly to do exactly.  */ for (current_order = MAX_ORDER - 1; current_order >= min_order; --current_order) { area = &(zone->free_area[current_order]); fallback_mt = find_suitable_fallback(area, current_order, start_migratetype, false, &can_steal); if (fallback_mt == -1) continue; /*  * We cannot steal all free pages from the pageblock and the  * requested migratetype is movable. In that case it's better to  * steal and split the smallest available page instead of the  * largest available page, because even if the next movable  * allocation falls back into a different pageblock than this  * one, it won't cause permanent fragmentation.  */ if (!can_steal && start_migratetype == MIGRATE_MOVABLE && current_order > order) goto find_smallest; goto do_steal; } return false; find_smallest: for (current_order = order; current_order < MAX_ORDER; current_order++) { area = &(zone->free_area[current_order]); fallback_mt = find_suitable_fallback(area, current_order, start_migratetype, false, &can_steal); if (fallback_mt != -1) break; } /*  * This should not happen - we already found a suitable fallback  * when looking for the largest page.  */ VM_BUG_ON(current_order == MAX_ORDER); do_steal: page = get_page_from_free_area(area, fallback_mt); steal_suitable_fallback(zone, page, alloc_flags, start_migratetype, can_steal); trace_mm_page_alloc_extfrag(page, order, current_order, start_migratetype, fallback_mt); return true; }

위와 같이 MOVABLE 을 이용해서 분리 및 공간을 확보할 때는 바로 위 order가 아닌 가장 큰 order부터 진행한다. 이러한 이유는 분리하는 작업을 memory process가 동작하는 동안 최소한 발생하도록 하기 위함이다.(이러한 머지, 분리 작업이 buddy system의 성능 저하가 되는 단점이기 때문이다)

 

정리하면 위와 같이 가장 큰 order부터 반복문을 통해서 area를 찾고 찾은 area는 MOVABLE type의 page를 쪼개서 여러 개의 page로 분리한다. 추가로 이 때 요청한 page type이 UNMOVABLE이라면 MOVABLE타입을 UNMOVABLE 타입으로 바꾸게 된다.(요청한 type의 공간이 부족해서 다른 type을가져와서 해당 type으로 변경하고 할당하는 과정을 steal이라 한다.)

이 과정에서 만약 MOVABLE type의 page block이 존재하는데 UNMOVABLE type이 MOVABLE type보다 많아지게 된다면 page block의 대표 type값은 UNMOVABLE type이 된다.

 

 

 

 

2. 해제

할당한 page를 해제할 때는 할당 작업과 반대로 진행하면 된다 단, MIGRATE_HIGHATOMIC type의 page를 해제할 때는 MOVABLE type으로 변경해서 pcp로 마이그레이션 한다.

해제 과정은 우선 memory free를 진행해서 해당 order의 free_list에 추가하고 free_list에서 buddy(짝)을 맞춰본 뒤 order 차수를 MAX-1까지 반복문을 진행하면서 buddy가 이루어진 free memory를 merge하여 위 order로 넘겨주는 작업을 진행한다.

 

buddy에 조금 더 자세히 보면 다음과 같다.

결국 page들도 address에 존재하는 area들이다 여기서 buddy 즉 짝이란 단순히 page 2개를 하나로 묶는 개념이 아니라 주소 값과 연관 있다.

즉 Buddy란 위와 같이 주소 값이 연속적으로 이루어진 page들의 묶음을 의미한다. 위에서 page 0x1000이 order=1에 있다. 여기서 page = 4KB로 가정하면 order=1이므로 page는 2개 즉 0x1000~0x1008까지가 범위가 될 것이고 해당 address와 연속적인 0x1008~0x100F와 buddy를 만들 수 있다.

결과적으로 Buddy는 다음 order로 올라가서 위와 같은 메모리 구조를 가지게 될 것이다.

 

 

• ref

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

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

https://wogh8732.tistory.com/402