[분석] Linux kernel physical memory allocator (Buddy) - Part 2

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에 맞춘 것입니다.)

/* * This is the 'heart' of the zoned buddy allocator. */ struct page * __alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist, nodemask_t *nodemask) { enum zone_type high_zoneidx = gfp_zone(gfp_mask); struct zone *preferred_zone; struct page *page = NULL; int migratetype = allocflags_to_migratetype(gfp_mask); unsigned int cpuset_mems_cookie; gfp_mask &= gfp_allowed_mask; lockdep_trace_alloc(gfp_mask); might_sleep_if(gfp_mask & __GFP_WAIT); if (should_fail_alloc_page(gfp_mask, order)) return NULL; /* * Check the zones suitable for the gfp_mask contain at least one * valid zone. It's possible to have an empty zonelist as a result * of GFP_THISNODE and a memoryless node */ if (unlikely(!zonelist->_zonerefs->zone)) return NULL; retry_cpuset: cpuset_mems_cookie = get_mems_allowed(); /* The preferred zone is used for statistics later */ first_zones_zonelist(zonelist, high_zoneidx, nodemask ? : &cpuset_current_mems_allowed, &preferred_zone); // preferred_zone == NORMAL ZONE if (!preferred_zone) goto out; /* First allocation attempt */ /* buddy allocation */ page = get_page_from_freelist(gfp_mask|__GFP_HARDWALL, nodemask, order, zonelist, high_zoneidx, ALLOC_WMARK_LOW|ALLOC_CPUSET, preferred_zone, migratetype); if (unlikely(!page)) page = __alloc_pages_slowpath(gfp_mask, order, zonelist, high_zoneidx, nodemask, preferred_zone, migratetype); trace_mm_page_alloc(page, order, gfp_mask, migratetype); out: /* * When updating a task's mems_allowed, it is possible to race with * parallel threads in such a way that an allocation can fail while * the mask is being updated. If a page allocation is about to fail, * check if the cpuset changed during allocation and if so, retry. */ if (unlikely(!put_mems_allowed(cpuset_mems_cookie) && !page)) goto retry_cpuset; return page; }

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() 함수를 살펴 보자.

again: if (likely(order == 0)) { struct per_cpu_pages *pcp; struct list_head *list; local_irq_save(flags); pcp = &this_cpu_ptr(zone->pageset)->pcp; list = &pcp->lists[migratetype]; if (list_empty(list)) { pcp->count += rmqueue_bulk(zone, 0, pcp->batch, list, migratetype, cold); if (unlikely(list_empty(list))) goto failed; } if (cold) page = list_entry(list->prev, struct page, lru); else page = list_entry(list->next, struct page, lru); list_del(&page->lru); pcp->count--; } else { if (unlikely(gfp_flags & __GFP_NOFAIL)) { /* * __GFP_NOFAIL is not to be used in new code. * * All __GFP_NOFAIL callers should be fixed so that they * properly detect and handle allocation failures. * * We most definitely don't want callers attempting to * allocate greater than order-1 page units with * __GFP_NOFAIL. */ WARN_ON_ONCE(order > 1); } spin_lock_irqsave(&zone->lock, flags); page = __rmqueue(zone, order, migratetype); spin_unlock(&zone->lock); if (!page) goto failed; __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << order)); }

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()

/* * Go through the free lists for the given migratetype and remove * the smallest available page from the freelists */ static inline 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]); if (list_empty(&area->free_list[migratetype])) continue; page = list_entry(area->free_list[migratetype].next, struct page, lru); list_del(&page->lru); rmv_page_order(page); area->nr_free--; expand(zone, page, order, current_order, area, migratetype); return page; } return NULL;

이 함수로 넘어오는 경우의 시나리오를 먼저 세우면,(가장 간단한 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() 를 살펴보자.

static inline void expand(struct zone *zone, struct page *page, int low, int high, struct free_area *area, int migratetype) { unsigned long size = 1 << high; while (high > low) { area--; high--; size >>= 1; VM_BUG_ON(bad_range(zone, &page[size])); #ifdef CONFIG_DEBUG_PAGEALLOC if (high < debug_guardpage_minorder()) { /* * Mark as guard pages (or page), that will allow to * merge back to allocator when buddy will be freed. * Corresponding page table entries will not be touched, * pages will stay not present in virtual address space */ INIT_LIST_HEAD(&page[size].lru); set_page_guard_flag(&page[size]); set_page_private(&page[size], high); /* Guard pages are not available for any usage */ __mod_zone_page_state(zone, NR_FREE_PAGES, -(1 << high)); continue; } #endif list_add(&page[size].lru, &area->free_list[migratetype]); area->nr_free++; set_page_order(&page[size], high); } }

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