Buddy Memory Allocator (할당)

Buddy Memory Allocator는 페이지 단위의 할당관리를 위한 메모리 할당 관리 시스템으로 연속된(contiguous) free 페이지의 할당/해지를 관리하되 최대한 파편화되지 않도록 한다.

  • free 메모리 페이지를 2의 차수 페이지 크기로 나누어 관리한다.
    • 2^0=1 페이지부터 2^(MAX_ORDER-1)=1024 페이지 까지 총 11 slot으로 나누어 관리한다.
      • MAX_ORDER=11
        • 커널 2.4.x에서는 defalut로 10을 사용하였었다.
        • CONFIG_FORCE_MAX_ZONEORDER 커널 옵션을 사용하여 크기를 바꿀 수 있다.
  • 각 order slot 또한 파편화 되지 않도록 관리하기 위해 다음과 같은 구조가 준비되어 있다.
    • 같은 mobility 속성을 가진 페이지들끼리 가능하면 뭉쳐서 있도록 각 order slot은 migratetype 별로 나뉘어 관리한다.
      • 이렇게 나누어 관리함으로 페이지 회수 및 메모리 compaction 과정이 효율을 높일 수 있다.
      • NUMA 시스템에서는 특별히 MIGRATE_MOVABLE 타입을 더 도와주기 위해 ZONE_MOVABLE 영역을 만들 수도 있다.
    • 각 페이지를 담는 free_list에서 free page 들은 짝(버디)을 이루어 두 개의 짝(버디)이 모이면 더 큰 order로 합병되어 올라가고 필요시 분할하여 하나 더 적은 order로 나뉠 수 있다.
      • 이제 더 이상 짝(버디)을 관리할 때 map이라는 이름의 bitmap을 사용하지 않고 free_list라는 이름의 리스트와 페이지 정보만을 사용하여 관리한다.
    • free_list는 선두 방향으로 hot 속성을 갖고 후미 방향으로 cold 속성을 갖는다.
      • hot, cold 속성은 각각 리스트의 head와 tail의 위치로 대응하여 관리된다.
        • hot: 리스트 검색에서 앞부분에 놓인 페이지들은 다시 할당되어 사용될 가능성이 높은 page 이다.
        • cold: 리스트 검색에서 뒷부분에 놓인 페이지들은 order가 통합되어 점점 상위 order로 올라갈 가능성이 높은 page 이다. 이를 통해 free 페이지의 파편화를 최대한 억제할 수 있다.
  • MIGRATE_CMA는 CMA 영역을 버디 시스템에 구성 후 각 페이지들의 할당 관리는 별도로 CMA Memory Allocator에서 수행 한다.
  • 버디 시스템의 관리 기법이 계속 버전 업하면서 복잡도는 증가하고 있지만 최대한 버디 시스템의 효율(단편화, 비파편화)이 높아지고 있다

 

다음 그림은 Buddy 메모리 할당자의 core 부분의 모습을 보여준다.

buddy-1b

 

pageblock

  • 페이지를 페이지 블럭 단위로 나누어 페이지 블럭마다 4bit를 사용한 비트맵으로 각 비트는 다음과 같다.
    • 3bit를 사용하여 각 메모리 블럭을 migratetype으로 구분하여 mobility 속성을 관리한다.
      • 페이지블럭은 2^pageblock_order 만큼을 관리하고 그 페이지들이 가장 많이 사용하는 mobility 속성을 메모리블럭에서 대표 mobility 속성으로 기록하여 관리한다.
    • 1bit를 사용하여 compaction 기능에 의해 skip할 수 있도록 한다.
  • pageblock_order
    • 페이지 관리 단위
      • default로 MAX_ORDER-1을 사용한다.
        • arm, arm64에서 사용되며 10(4MB)이 사용된다.
      • HUGETLB_PAGE를 지원하는 x86등 특정 아키텍처에서 CONFIG_HUGETLB_PAGE_SIZE_VARIABLE 커널 옵션 사용 여부에 따라 다음과 같이 사용된다.
        • 커널 옵션 사용 시 커널의 부트업 타임에 MAX_ORDER-1을 사용하지 않고 PMD 크기에 일치하는 order를 사용한다.
        • 커널 옵션을 사용하지 않는 경우 컴파일 타임에 설정된 PMD 크기에 일치하는 order를 사용한다.

 

Migration type (migratetype)

  • 각 페이지는 각각 mobility 속성을 표현하기 위해 migration type을 갖고 있으며 가능하면 같은 속성을 가진 페이지들끼리 뭉쳐 있도록하여 연속된 메모리의 파편화를 억제하고 최대한 커다란 연속된 free 메모리를 유지하고자하는 목적으로 버디 시스템에 설계되었다.
  • migration 타입은 다음과 같고 처음 3개가 기본적인 사용형태이다.
    • MIGRATE_UNMOVABLE
      • 이동과 메모리 회수가 불가능한 페이지 타입
      • I/O buffers, kernel stacks, process page tables, slabs 등에 사용되는 페이지 타입
    • MIGRATE_RECLAIMABLE
      • 이동은 불가능하지만 메모리 부족 시 메모리 회수가 가능한 경우에 사용되는 페이지 타입
      • 매핑된 File 페이지
    • MIGRATE_MOVABLE
      • 연속된 큰 메모리가 필요시 현재 사용되는 페이지를 이동하여 최대한 파편화를 막기 위해 사용되는 페이지 타입
      • User application등에서 할당된 페이지
    • MIGRATE_RESERVE
      • 메모리 부족시 커널이 compaction 작업을 할 때 사용할 목적으로 약간의 메모리(수 페이지블럭)를 예비 목적으로 만들었다.
        • compaction 진행 시 이 영역을 잠시 할당 받을 때 atomic allocation 방법을 이용한다.
      • 커널 4.4-rc1에서 삭제되었고 대신 high-order atomic allocation을 지원하기 위해 MIGRATE_HIGHATOMIC이 추가되었다.
    • MIGRATE_CMA
      • CMA 메모리 할당자가 별도로 관리하는 페이지 타입
    • MIGRATE_ISOLATE
      • 커널이 메모리 회수 시스템을 가동시킬 때 페이지 블럭들을 스캔하면서 각 페이지블럭에서 isolation을 진행할 때 잠시 MIGRATE_ISOLATE 타입으로 지정하여 관리한다.

 

rpi2 예)

$ cat /proc/pagetypeinfo
Page block order: 10
Pages per block:  1024

Free pages count per migrate type at order       0      1      2      3      4      5      6      7      8      9     10
Node    0, zone   Normal, type    Unmovable     10     13      9      6      2      2      0      1      0      1      0
Node    0, zone   Normal, type  Reclaimable      1      2      2      3      0      0      1      0      1      0      0
Node    0, zone   Normal, type      Movable      6      3      1      1    447    109      4      0      0      1    147
Node    0, zone   Normal, type      Reserve      0      0      0      0      0      0      0      0      0      0      2
Node    0, zone   Normal, type          CMA      1      1      1      2      1      2      1      0      1      1      0
Node    0, zone   Normal, type      Isolate      0      0      0      0      0      0      0      0      0      0      0

Number of blocks type     Unmovable  Reclaimable      Movable      Reserve          CMA      Isolate
Node 0, zone   Normal            4            5          223            2            2            0
  • rpi2의 경우 MAX_ORDER=11로 설정되어 있고 pageblock_order 역시 MAX_ORDER-1로 설정되어 있는 것을 알 수 있다.
    • 커널 버전에 따라 MAX_ORDER값이 다르다. 기존에는 9, 10 등이 사용되었었다.

 

버디 시스템과 관련된 페이지 속성

  • _mapcount
    • 버디 시스템의 free page로 페이지=-128(PAGE_BUDDY_MAPCOUNT_VALUE)
    • 할당되어 버디 시스템에서 빠져나간 페이지=-1
  • private
    • 버디 시스템에서 구분되는 order slot 번호
  • index
    • 버디 시스템에서 구분되는 migratetype
  • count
    • 사용자 없이 free 된 페이지=0
    • 할당되고 사용되는 경우 증가

 

다음 그림은 12페이지가 버디 시스템의 free page로 등록되어 있고 짝(버디)이 되는 페이지들이 할당되어 사용되는 모습을 보여준다.

  • 4 페이지의 연속된 free page 2 건이 free_area[2]에 등록
  • 2 페이지의 연속된 free page 1 건이 free_area[1]에 등록

buddy-2

버디 페이지 할당

 

buffered_rmqueue-1

 

buffered_rmqueue()

mm/page_alloc.c

/*
 * Allocate a page from the given zone. Use pcplists for order-0 allocations.
 */
static inline
struct page *buffered_rmqueue(struct zone *preferred_zone,
                        struct zone *zone, unsigned int order,
                        gfp_t gfp_flags, int migratetype)
{
        unsigned long flags;
        struct page *page;
        bool cold = ((gfp_flags & __GFP_COLD) != 0);

        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_freepage_state(zone, -(1 << order),
                                          get_freepage_migratetype(page));
        }

0-order 페이지를 할당 받을 때 pcp(Per CPU Page Frame Cache)에서 할당을 받는다. cold 속성에 따라 pcp list의 후미(cold) 또는 선두(hot)에서 에서 free 페이지를 가져온다. pcp list가 비어있는 경우 버디 시스템으로 부터 batch 수 만큼 free 페이지를 받아와서 pcp list에 추가한다.

 

  • bool cold = ((gfp_flags & __GFP_COLD) != 0);
    • gfp_flags에 __GFP_COLD가 있는 경우 true
  • if (likely(order == 0)) {
    • 많은 확률로 0-order 페이지를 요청하는 경우
  • list = &pcp->lists[migratetype];
    • 요청한 migratetype의 pcp list를 지정한다.

pcp list가 비어있는 경우 버디 시스템으로 부터 0-order page를 batch 만큼 가져와서 pcp에 채운다.

  • if (list_empty(list)) {
    • 리스트가 비어있는 경우
  • pcp->count += rmqueue_bulk(zone, 0, pcp->batch, list, migratetype, cold);
    • batch 만큼 list에 채운다.
  • if (unlikely(list_empty(list))) goto failed;
    • 여전히 드문 확률로 list가 비어있는 경우 실패로 이동한다.

pcp list에서 페이지를 가져온다.

  • if (cold) page = list_entry(list->prev, struct page, lru);
    • list의 후미(cold)에 있는 페이지를 가져온다.
  • else page = list_entry(list->next, struct page, lru);
    • list의 선두(hot)에 있는 페이지를 가져온다.
  • list_del(&page->lru); pcp->count–;
    • list에서 페이지를 삭제하고 count를 감소시킨다.

0-order가 아닌 페이지를 요청한 경우

  •  page = __rmqueue(zone, order, migratetype);
    • 버디 시스템에서 2^order 페이지만큼 가져온다.
  • if (!page) goto failed;
    • 페이지 할당이 안된 경우 failed로 이동한다.
  • __mod_zone_freepage_state(zone, -(1 << order), get_freepage_migratetype(page));
    • free 페이지 카운터를 2^order 만큼 감소시킨다.

 

        __mod_zone_page_state(zone, NR_ALLOC_BATCH, -(1 << order));
        if (atomic_long_read(&zone->vm_stat[NR_ALLOC_BATCH]) <= 0 &&
            !test_bit(ZONE_FAIR_DEPLETED, &zone->flags))
                set_bit(ZONE_FAIR_DEPLETED, &zone->flags);

        __count_zone_vm_events(PGALLOC, zone, 1 << order);
        zone_statistics(preferred_zone, zone, gfp_flags);
        local_irq_restore(flags);

        VM_BUG_ON_PAGE(bad_range(zone, page), page);
        return page;

failed:
        local_irq_restore(flags);
        return NULL;
}

페이지 할당이 성공한 경우 관련 stat을 증/감 시킨다.

  • __mod_zone_page_state(zone, NR_ALLOC_BATCH, -(1 << order));
    • NR_ALLOC_BATCH 카운터를 2^order 만큼 감소시킨다.
  • if (atomic_long_read(&zone->vm_stat[NR_ALLOC_BATCH]) <= 0 && !test_bit(ZONE_FAIR_DEPLETED, &zone->flags)) set_bit(ZONE_FAIR_DEPLETED, &zone->flags);
    • NR_ALLOC_BATCH 카운터가 0보다 작거나 같으면서 zone->flags에 ZONE_FAIR_DEPLETED가 설정되지 않은 경우 해당 비트를 설정시킨다.
  • __count_zone_vm_events(PGALLOC, zone, 1 << order);
    • PGALLOC 카운터를 2^order 만큼 증가시킨다.
  • zone_statistics(preferred_zone, zone, gfp_flags);
    • CONFIG_NUMA 커널 옵션이 사용되는 경우 관련 stat을 증/감 시킨다.

 

rmqueue_bulk()

mm/page_alloc.c

/*
 * Obtain a specified number of elements from the buddy allocator, all under
 * a single hold of the lock, for efficiency.  Add them to the supplied list.
 * Returns the number of new pages which were placed at *list.
 */
static int rmqueue_bulk(struct zone *zone, unsigned int order,
                        unsigned long count, struct list_head *list,
                        int migratetype, bool cold)
{
        int i;

        spin_lock(&zone->lock);
        for (i = 0; i < count; ++i) {
                struct page *page = __rmqueue(zone, order, migratetype);
                if (unlikely(page == NULL))
                        break;

                /*
                 * Split buddy pages returned by expand() are received here
                 * in physical page order. The page is added to the callers and
                 * list and the list head then moves forward. From the callers
                 * perspective, the linked list is ordered by page number in
                 * some conditions. This is useful for IO devices that can
                 * merge IO requests if the physical pages are ordered
                 * properly.
                 */
                if (likely(!cold))
                        list_add(&page->lru, list);
                else
                        list_add_tail(&page->lru, list);
                list = &page->lru;
                if (is_migrate_cma(get_freepage_migratetype(page)))
                        __mod_zone_page_state(zone, NR_FREE_CMA_PAGES,
                                              -(1 << order));
        }
        __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
        spin_unlock(&zone->lock);
        return i;
}

버디 시스템의 order slot에서 batch 만큼 free 페이지를 가져와서 list에 추가한다.

  • for (i = 0; i < count; ++i) {
    • count 수 만큼 루프를 돈다.
  • struct page *page = __rmqueue(zone, order, migratetype);
    • 버디 시스템의 order slot에서 free 페이지를 알아온다.
  •  if (unlikely(page == NULL)) break;
    • 적은 확률로 free 페이지를 가져올 수 없는 경우 루프를 빠져나간다.
  • if (likely(!cold)) list_add(&page->lru, list);
    • list의 선두(hot)에 free 페이지를 추가한다.
  • else list_add_tail(&page->lru, list);
    • list의 후미(cold)에 free 페이지를 추가한다.
  • list = &page->lru;
    • list가 추가한 페이지를 가리키게 한다.
  • if (is_migrate_cma(get_freepage_migratetype(page))) __mod_zone_page_state(zone, NR_FREE_CMA_PAGES, -(1 << order));
    • cma 타입인 경우 NR_FREE_CMA stat 카운터를 2^order 만큼 감소시킨다.
  • __mod_zone_page_state(zone, NR_FREE_PAGES, -(i << order));
    • 루프 완료 후 NR_FREE_PAGES stat 카운터를 2^order 만큼 감소시킨다.

 

다음 그림은 free 페이지들이 bulk로 추가될 때 cold 방향과 hot 방향에 따라 달라지는 것을 보여준다.

rmqueue_bulk-1

 

__rmqueue()

mm/page_alloc.c

/*
 * Do the hard work of removing an element from the buddy allocator.
 * Call me with the zone->lock already held.
 */
static struct page *__rmqueue(struct zone *zone, unsigned int order,
                                                int migratetype)
{
        struct page *page;

retry_reserve:
        page = __rmqueue_smallest(zone, order, migratetype);

        if (unlikely(!page) && migratetype != MIGRATE_RESERVE) {
                page = __rmqueue_fallback(zone, order, migratetype);

                /*
                 * Use MIGRATE_RESERVE rather than fail an allocation. goto
                 * is used because __rmqueue_smallest is an inline function
                 * and we want just one call site
                 */
                if (!page) {
                        migratetype = MIGRATE_RESERVE;
                        goto retry_reserve;
                }
        }

        trace_mm_page_alloc_zone_locked(page, order, migratetype);
        return page;
}

버디 시스템으로 부터 free 페이지를 할당 받아온다.

  • page = __rmqueue_smallest(zone, order, migratetype);
    • migratetype으로 2^order 페이지 만큼의 free 페이지를 할당 받아온다.
  •  if (unlikely(!page) && migratetype != MIGRATE_RESERVE) { page = __rmqueue_fallback(zone, order, migratetype);
    • 페이지 할당이 실패하고 reserve 타입이 아닌 경우 migrate type fallback list 순서로 검색하여 free 페이지를 할당 받아온다.
  • if (!page) { migratetype = MIGRATE_RESERVE; goto retry_reserve; }
    • fallback list를 사용해서도 실패한 경우 reserve 타입으로 다시 한 번만 시도한다.

 

다음 그림은 버디 시스템으로 부터 요청된 migrate type과 order로 free 페이지를 할당 받아올 때 만일 할당이 실패하는 경우 migrate type fallback list를 사용하여 검색을 계속하는 것을 보여준다.

__rmqueue-1

 

__rmqueue_smallest()

mm/page_alloc.c

/*
 * 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);
                set_freepage_migratetype(page, migratetype);
                return page;
        }

        return NULL;
}

지정된 migratetype으로 요청 order 부터 MAX_ORDER-1 까지의 free_list의 선두에서 페이지를 꺼내온다.

  • for (current_order = order; current_order < MAX_ORDER; ++current_order) {
    • 요청 order 부터 MAX_ORDER-1까지 루프를 돈다.
  • area = &(zone->free_area[current_order]);
    • current_order slot 지정
  • if (list_empty(&area->free_list[migratetype])) continue;
    • free_list가 비어있는 경우 다음 order로 넘어간다.
  • page = list_entry(area->free_list[migratetype].next, struct page, lru);
    • free_list의 선두에서 페이지를 알아온다.
  • list_del(&page->lru);
    • free_list에서 페이지를 제거한다.
  • rmv_page_order(page);
    • 페이지 order를 제거한다.
      • page->_mapcount=-1, page->private(order)=0을 대입한다.
  • area->nr_free–;
    • order slot에서 등록된 free 엔트리 수를 감소시킨다.
  • expand(zone, page, order, current_order, area, migratetype);
    • 요청 order 보다 큰 current_order에서 페이지를 할당 받은 경우 current_order-1 부터 order 까지의 free 페이지를 등록한다.
  • set_freepage_migratetype(page, migratetype);
    • page->index에 migratetype을 저장한다.

 

expand()

/*
 * The order of subdivision here is critical for the IO subsystem.
 * Please do not alter this order without good reasons and regression
 * testing. Specifically, as large blocks of memory are subdivided,
 * the order in which smaller blocks are delivered depends on the order
 * they're subdivided in this function. This is the primary factor
 * influencing the order in which pages are delivered to the IO
 * subsystem according to empirical testing, and this is also justified
 * by considering the behavior of a buddy system containing a single
 * large block of memory acted on by a series of small allocations.
 * This behavior is a critical factor in sglist merging's success.
 *
 * -- nyc
 */
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_PAGE(bad_range(zone, &page[size]), &page[size]);

                if (IS_ENABLED(CONFIG_DEBUG_PAGEALLOC) &&
                        debug_guardpage_enabled() &&
                        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
                         */
                        set_page_guard(zone, &page[size], high, migratetype);
                        continue;
                }
                list_add(&page[size].lru, &area->free_list[migratetype]);
                area->nr_free++;
                set_page_order(&page[size], high);
        }
}

low보다 큰 high에서 페이지를 할당 받은 경우 high-1 부터 low까지의 free 페이지를 등록한다

  • unsigned long size = 1 << high;
    • size에 2^high 값을 대입한다.
  • while (high > low) { area–; high–; size >>= 1;
    • high order가 low order 보다 큰 경우 area 및 high를 감소시키고 size를 반으로 감소시킨다.
  • list_add(&page[size].lru, &area->free_list[migratetype]);
    • area->free_list[migratetype]에 page[size]를 추가한다.
  • area->nr_free++;
    • area의 free 엔트리 수를 증가시킨다.
  • set_page_order(&page[size], high);
    • 추가한 페이지에 high order 값을 저장한다.
      • page->_mapcount=-128, page->private(order)=high을 대입한다.

 

__rmqueue_fallback()

mm/page_alloc.c

/* Remove an element from the buddy allocator from the fallback list */
static inline struct page *
__rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype)
{
        struct free_area *area;
        unsigned int current_order;
        struct page *page;

        /* Find the largest possible block of pages in the other list */
        for (current_order = MAX_ORDER-1;
                                current_order >= order && current_order <= MAX_ORDER-1;
                                --current_order) {
                int i;
                for (i = 0;; i++) {
                        int migratetype = fallbacks[start_migratetype][i];
                        int buddy_type = start_migratetype;

                        /* MIGRATE_RESERVE handled later if necessary */
                        if (migratetype == MIGRATE_RESERVE)
                                break;

                        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);
                        area->nr_free--;

                        if (!is_migrate_cma(migratetype)) {
                                try_to_steal_freepages(zone, page,
                                                        start_migratetype,
                                                        migratetype);
                        } else {
                                /*
                                 * When borrowing from MIGRATE_CMA, we need to
                                 * release the excess buddy pages to CMA
                                 * itself, and we do not try to steal extra
                                 * free pages.
                                 */
                                buddy_type = migratetype;
                        }

                        /* Remove the page from the freelists */
                        list_del(&page->lru);
                        rmv_page_order(page);

                        expand(zone, page, order, current_order, area,
                                        buddy_type);

                        /*
                         * The freepage_migratetype may differ from pageblock's
                         * migratetype depending on the decisions in
                         * try_to_steal_freepages(). This is OK as long as it
                         * does not differ for MIGRATE_CMA pageblocks. For CMA
                         * we need to make sure unallocated pages flushed from
                         * pcp lists are returned to the correct freelist.
                         */
                        set_freepage_migratetype(page, buddy_type);

                        trace_mm_page_alloc_extfrag(page, order, current_order,
                                start_migratetype, migratetype);

                        return page;
                }
        }

        return NULL;
}

migrate type fallback list 순서로 검색하여 free 페이지를 할당 받아온다.

  • for (current_order = MAX_ORDER-1; current_order >= order && current_order <= MAX_ORDER-1; –current_order) {
    • MAX_ORDER-1 부터 order까지 감소시키며 루프를 돈다.
  • for (i = 0;; i++) { int migratetype = fallbacks[start_migratetype][i];
    • 시작 migratetype에 등록된 fallbacks[][]를 순차적으로 알아온다.
  • if (migratetype == MIGRATE_RESERVE) break;
    • 종료를 의미하는 reserve 타입이 나오면 루프를 중지한다.
  • area = &(zone->free_area[current_order]);
    • 현재 order slot용 free_area
  • if (list_empty(&area->free_list[migratetype])) continue;
    • free_list가 비어 있는 경우 처리를 생략하고 다음 루프를 수행한다.
  • page = list_entry(area->free_list[migratetype].next, struct page, lru);  area->nr_free–;
    • free_list에서 선두 페이지를 가져오고 free 카운터를 감소시킨다.
  • if (!is_migrate_cma(migratetype)) { try_to_steal_freepages(zone, page, start_migratetype, migratetype);
    • cma 타입이 아닌 경우 order 페이지가 pageblock의 50%를 넘어가는 경우 요청 타입인 start_type으로 steal 한다.
      • pageblock의 migratetype을 원 요청 타입인 start_type으로 바꾼다.
  • } else { buddy_type = migratetype; }
    • cma 타입인 경우 steal 하지 않는다.
      • 해당 페이지만 cma 타입을 사용하고 pageblock의 migratetype은 변경하지 않는다.
  • list_del(&page->lru);
    • free_list에서 등록된 페이지를 제거한다.
  • rmv_page_order(page);
    • page->_mapcount=-1 (clear buddy)
    • page->private=0 (order)
  • expand(zone, page, order, current_order, area, buddy_type);
    • 상위 free_area 슬롯에서 페이지를 분할하여 하위 free_area 슬롯으로 페이지를 추가한다.
    • 요청 order와 current_order가 차이가 발생한 경우 current_order에서 페이지를 삭제하고 current_order-1부터 요청 order까지 페이지를 각각 등록한다.
  • set_freepage_migratetype(page, buddy_type);
    • page->index=최종 결정된 타입

 

아래 그림은 unmovable 타입으로 5-order page를 할당 받으려는데 unmovable 타입에서 빈 페이지를 확보하지 못한 경우 migratetype의 fallback list를 통해 reclaimable 및 movable 타입을 검색하여 movable에서 할당받는 것을 보여준다.

__rmqueue_fallback-1

 

try_to_steal_freepages()

mm/page_alloc.c

static void try_to_steal_freepages(struct zone *zone, struct page *page,
                                  int start_type, int fallback_type)
{
        int current_order = page_order(page);

        /* Take ownership for orders >= pageblock_order */
        if (current_order >= pageblock_order) {
                change_pageblock_range(page, current_order, start_type);
                return;
        }

        if (current_order >= pageblock_order / 2 ||
            start_type == MIGRATE_RECLAIMABLE ||
            start_type == MIGRATE_UNMOVABLE ||
            page_group_by_mobility_disabled) {
                int pages;

                pages = move_freepages_block(zone, page, start_type);

                /* Claim the whole block if over half of it is free */
                if (pages >= (1 << (pageblock_order-1)) ||
                                page_group_by_mobility_disabled)
                        set_pageblock_migratetype(page, start_type);
        }
}

order 페이지가 pageblock의 50%를 넘어가는 경우 pageblock의 migratetype을 원 요청 타입인 start_type으로 바꾼다.

  • order가 pageblock_order보다 큰 경우 즉 100%인 경우 페이지블럭을 start_type으로 변경시키고 함수를 빠져나간다.
  • 다음 조건에 해당 하는 경우에는 order 페이지들이 속한 pageblock 하나를 start_type으로 이동시키고 이동 시킨 페이지가 pageblock의 50% 이상을 차지하거나 page_group_by_mobility_disabled가 true인 경우 페이지블럭을 start_type으로 변경시킨다.
    • current_order가 pageblock_order/2보다 큰 경우
      • pageblock_order가 10이라면 그 절반보다 current_order가 크거나 같은 경우 처음 요청한 타입으로 바꿔야 한다.
    • start_type이 reclaimable 또는 unmovable인 경우
      • 요청 페이지가 reclimable 인 경우 이동되는 페이지는 무조건 reclimable 타입으로 바꿔야 한다.
      • 요청 페이지가 unmovable 인 경우 이동되는 페이지는 무조건 unmovable 타입으로 바꿔야 한다
    • page_group_by_mobility_disable가 true인 경우
      • 이동되는 페이지는 무조건 처음 요청한 타입으로 바꿔야 한다.

 

  • int current_order = page_order(page);
    • page->private (order)를 가져온다.
  • if (current_order >= pageblock_order) { change_pageblock_range(page, current_order, start_type); return; }
    • current_order가 pageblock_order와 같거나 초과하는 경우  페이지블럭을 start_type으로 변경시키고 함수를 빠져나간다.
  • if (current_order >= pageblock_order / 2 || start_type == MIGRATE_RECLAIMABLE || start_type == MIGRATE_UNMOVABLE || page_group_by_mobility_disabled) {
    • current_order가 pageblock_order의 절반보다 같거나 초과하는 경우 또는 start_type이 reclaimable 이나 unmovable 또는 page_group_by_mobility_disable된 경우
  • pages = move_freepages_block(zone, page, start_type);
    • 요청한 페이지가 속한 하나의 pageblock내에 존재하는 모든 버디 free 페이지들을 start_type 으로 이동시킨다.
  • if (pages >= (1 << (pageblock_order-1)) || page_group_by_mobility_disabled) set_pageblock_migratetype(page, start_type);
    • 이동시킨 페이지가 pageblock의 50% 이상인 경우 또는 page_group_by_mobility_disabled인 경우 pageblock에서 start_type으로 설정한다.

 

change_pageblock_range()

mm/page_alloc.c

static void change_pageblock_range(struct page *pageblock_page,
                                        int start_order, int migratetype)
{
        int nr_pageblocks = 1 << (start_order - pageblock_order);

        while (nr_pageblocks--) {
                set_pageblock_migratetype(pageblock_page, migratetype);
                pageblock_page += pageblock_nr_pages;
        }
}

요청한 order 내에 있는 모든 페이지 블럭의 수 만큼 각 페이지 블럭에 대해 migratetype을 설정한다.

  • int nr_pageblocks = 1 << (start_order – pageblock_order);
    • start_order내에 들어갈 수 있는 pageblock의 수
  • while (nr_pageblocks–) { set_pageblock_migratetype(pageblock_page, migratetype); pageblock_page += pageblock_nr_pages; }
    • pageblock의 수 만큼 pageblock_page에 migratetype을 설정하고 pageblock_page에 2^pageblock_order를 더한다.
      • 만일 page_group_by_mobility_disabled가 설정된 경우 reclaimable 이나 movable 타입의 경우 unmovable로 변경하여 저장한다.

 

move_freepages_block()

mm/page_alloc.c

int move_freepages_block(struct zone *zone, struct page *page,
                                int migratetype)
{
        unsigned long start_pfn, end_pfn;
        struct page *start_page, *end_page;

        start_pfn = page_to_pfn(page);
        start_pfn = start_pfn & ~(pageblock_nr_pages-1);
        start_page = pfn_to_page(start_pfn);
        end_page = start_page + pageblock_nr_pages - 1;
        end_pfn = start_pfn + pageblock_nr_pages - 1;

        /* Do not cross zone boundaries */
        if (!zone_spans_pfn(zone, start_pfn))
                start_page = page;
        if (!zone_spans_pfn(zone, end_pfn))
                return 0;

        return move_freepages(zone, start_page, end_page, migratetype);
}

요청한 페이지가 속한 전체 pageblock의 페이지들을 지정된 migratetype 속성으로 이동시킨다.

  • start_pfn = start_pfn & ~(pageblock_nr_pages-1);
    • pageblock단위로 round down한 시작 페이지
  • end_pfn = start_pfn + pageblock_nr_pages – 1;
    • 시작 페이지에 pageblock의 페이지 수 -1을 한 끝 페이지
  • if (!zone_spans_pfn(zone, start_pfn)) start_page = page;
    • start_pfn이 zone 범위에 없는 pfn인 경우 start_page를 원래 인수 page로 바꾼다.
  • if (!zone_spans_pfn(zone, end_pfn)) return 0
    • end_pfn이 zone 범위를 벗어나는 pfn인 경우 함수를 빠져나간다.
  • return move_freepages(zone, start_page, end_page, migratetype);

 

move_freepages()

mm/page_alloc.c

/*
 * Move the free pages in a range to the free lists of the requested type.
 * Note that start_page and end_pages are not aligned on a pageblock
 * boundary. If alignment is required, use move_freepages_block()
 */
int move_freepages(struct zone *zone,
                          struct page *start_page, struct page *end_page,
                          int migratetype)
{
        struct page *page;
        unsigned long order;
        int pages_moved = 0;

#ifndef CONFIG_HOLES_IN_ZONE
        /*
         * page_zone is not safe to call in this context when
         * CONFIG_HOLES_IN_ZONE is set. This bug check is probably redundant
         * anyway as we check zone boundaries in move_freepages_block().
         * Remove at a later date when no bug reports exist related to
         * grouping pages by mobility
         */
        VM_BUG_ON(page_zone(start_page) != page_zone(end_page));
#endif

        for (page = start_page; page <= end_page;) {
                /* Make sure we are not inadvertently changing nodes */
                VM_BUG_ON_PAGE(page_to_nid(page) != zone_to_nid(zone), page);

                if (!pfn_valid_within(page_to_pfn(page))) {
                        page++;
                        continue;
                }

                if (!PageBuddy(page)) {
                        page++;
                        continue;
                }

                order = page_order(page);
                list_move(&page->lru,
                          &zone->free_area[order].free_list[migratetype]);
                set_freepage_migratetype(page, migratetype);
                page += 1 << order; 
                pages_moved += 1 << order;
        }
 
        return pages_moved;
}

start_page ~ end_page 까지를 지정한 migratetype으로 이동시킨다.

  • for (page = start_page; page <= end_page;) {
    • 시작 페이지부터 끝 페이지까지 루프를 돈다.
  • if (!pfn_valid_within(page_to_pfn(page))) { page++; continue; }
    • 페이지가 hole 영역인 경우 다음 페이지를 진행한다.
  • if (!PageBuddy(page)) { page++; continue; }
    • 버디 시스템에서 free되어 관리되는 페이지가 아니면 다음 페이지를 진행한다.
      • _mapcount != -128 (buddy가 아니면) .
  • order = page_order(page);
    • page->private (order)
  • list_move(&page->lru, &zone->free_area[order].free_list[migratetype]);
    • 현재 order slot의 지정한 migratetype으로 이동 시킨다.
  • set_freepage_migratetype(page, migratetype);
    • migratetype이 변경되었으므로 첫 페이지에 기록한다.
      • page->index = migratype
  • page += 1 << order;
    • 다음 2^order 페이지
  •  pages_moved += 1 << order;
    • 이동된 수 += 2^order

 

다음 그림은 요청 범위에 있는 페이지들을 찾아 버디 시스템에 존재하면 요청 migratetype으로 이주하는 모습을 보여준다.

move_freepages-1

 

참고

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.