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

 

참고

Buddy Memory Allocator (해지)

관련 커널 옵션들

CONFIG_KMEMCHECK

  • x86 아키텍처에서만 지원되며 할당된 kernel memory를 dynamic하게 tracing할 수 있게하는 커널 옵션이다.
  • cmdline에서 “kmemcheck=0” or “kmemcheck=1” early 커널 파라메터를 사용하여 enable/disable 시킬 수 있다.

 

CONFIG_MEMORY_ISOLATION

  • 최근 커널은 CONFIG_{CMA|MEMORY_HOTPLUG|MEMORY_FAILURE} 커널 옵션을 사용하지 않고 CONFIG_MEMORY_ISOLATION 커널 옵션만 사용해도 memory의 isolation 기능을 사용할 수 있도록 하였다.
  • rpi2: 이 커널 옵션을 사용한다.

 

CONFIG_KASAN

  • KASAN(Kernel Address Sanitizer) –  SLUB에 대한 런타임 메모리 디버거
  • 이 기능을 사용하면 최대 3배까지 성능 저하가 발생되고 약 1/8의 free 메모리를 소모한다.
  • 더 좋은 에러 감지를 위해 CONFIG_STACKTRACE 및 cmdline에 “slub_debug=U”를 같이 사용한다.

 

페이지 해지(free)

 

__free_pages-1a

 

__free_one_page-1

 

__free_pages()

mm/page_alloc.c

void __free_pages(struct page *page, unsigned int order)
{
        if (put_page_testzero(page)) {
                if (order == 0)
                        free_hot_cold_page(page, false);
                else
                        __free_pages_ok(page, order);
        }
}

사용이 완료된 2^order 페이지인 경우 free 하되 0-order 페이지의 경우 Per CPU Page Frame Cache로의 free를 시도한다.

  • 0-order 페이지를 pcp의 hot 페이지로 이주시킨다.
  • pcp 이주 시킬 때 migrate 타입에 따라 처리가 달라진다.
    • unmovable, reclaimable, movable 타입인 경우는 그대로 이주된다.
    • reserve, cma 타입인 경우는 movable 타입으로 변환하여 이주된다.
    • isolate 타입인 경우 pcp로 이주되지 않고 다시 buddy로 보낸다.

 

아래 그림은 order 비트에 따라 처리되는 모습을 보여준다.

  • order=0인 single page를 free할 때
    • pcp로 회수되는데 isolate 타입의 경우 페이지를 버디 시스템으로 회수시킨다.
    • pcp이주 시 overflow인 경우 cold 방향의 일부를 batch 수 만큼 버디 시스템으로 회수시킨다.
      • 회수 순서
        • 1st: reclaimable 타입의 cold 방향부터 hot 방향 페이지 순
        • 2nd: movable 타입의 cold 방향부터 hot 방향 페이지 순
        • 3rd: unmovable 타입의 cold 방향부터 hot 방향 페이지 순
  • order가 0이 아닌 multi page를 free할 때
    • pcp를 사용하지 않고 버디 시스템으로 회수시킨다.

free_pages-2a

 

put_page_testzero()

include/linux/mm.h

/*
 * Methods to modify the page usage count.
 *
 * What counts for a page usage:
 * - cache mapping   (page->mapping)
 * - private data    (page->private)
 * - page mapped in a task's page tables, each mapping
 *   is counted separately
 *
 * Also, many kernel routines increase the page count before a critical
 * routine so they can be sure the page doesn't go away from under them.
 */

/*
 * Drop a ref, return true if the refcount fell to zero (the page has no users)
 */
static inline int put_page_testzero(struct page *page)
{
        VM_BUG_ON_PAGE(atomic_read(&page->_count) == 0, page);
        return atomic_dec_and_test(&page->_count);
}

페이지의 참조카운터를 감소시키고 0(사용완료)인지 확인하여 사용완료 여부를 반환한다.

  • 0=사용중, 1=사용완료(참조 _count가 0이된 경우)

 

free_hot_cold_page()

mm/page_alloc.c

/*
 * Free a 0-order page
 * cold == true ? free a cold page : free a hot page
 */
void free_hot_cold_page(struct page *page, bool cold)
{
        struct zone *zone = page_zone(page);
        struct per_cpu_pages *pcp;
        unsigned long flags;
        unsigned long pfn = page_to_pfn(page);
        int migratetype;

        if (!free_pages_prepare(page, 0))
                return;

        migratetype = get_pfnblock_migratetype(page, pfn);
        set_freepage_migratetype(page, migratetype);
        local_irq_save(flags);
        __count_vm_event(PGFREE);

        /*
         * We only track unmovable, reclaimable and movable on pcp lists.
         * Free ISOLATE pages back to the allocator because they are being
         * offlined but treat RESERVE as movable pages so we can get those
         * areas back if necessary. Otherwise, we may have to free
         * excessively into the page allocator
         */
        if (migratetype >= MIGRATE_PCPTYPES) {
                if (unlikely(is_migrate_isolate(migratetype))) {
                        free_one_page(zone, page, pfn, 0, migratetype);
                        goto out;
                }
                migratetype = MIGRATE_MOVABLE;
        }

        pcp = &this_cpu_ptr(zone->pageset)->pcp;
        if (!cold)
                list_add(&page->lru, &pcp->lists[migratetype]);
        else
                list_add_tail(&page->lru, &pcp->lists[migratetype]);
        pcp->count++;
        if (pcp->count >= pcp->high) {
                unsigned long batch = ACCESS_ONCE(pcp->batch);
                free_pcppages_bulk(zone, batch, pcp);
                pcp->count -= batch;
        }

out:
        local_irq_restore(flags);
}

free할 0-order 페이지를 Per-CPU Page Frame Cache로 회수한다. 만일 pcp가 제한 수를 초과하는 경우 일부(batch)를 버디 시스템으로 회수시킨다.

  • if (!free_pages_prepare(page, 0)) return;
    • free page가 증명되지 않으면 루틴을 처리하지 않고 빠져나간다.
  • migratetype = get_pfnblock_migratetype(page, pfn);
    • pfnblock에서 요청 페이지의 migratetype을 알아온다.
  • set_freepage_migratetype(page, migratetype);
    • page->index에 migratetype을 설정한다.
  • __count_vm_event(PGFREE);
    • PGFREE++
  • if (migratetype >= MIGRATE_PCPTYPES) {
    • migratetype이 reserve, isolate, cma 등의 타입인 경우
  • if (unlikely(is_migrate_isolate(migratetype))) { free_one_page(zone, page, pfn, 0, migratetype); goto out; }
    • isolate 타입인 경우 pcp로 회수하지 않고 그냥 버디 시스템에서 곧바로 free 한다.
  • migratetype = MIGRATE_MOVABLE;
    • cma나 reserve가 free되는 경우 movable 타입으로 변환한다.
  • pcp = &this_cpu_ptr(zone->pageset)->pcp;
    • 현재 zone의 pcp
  • if (!cold) list_add(&page->lru, &pcp->lists[migratetype]);
    • cold 요청이 아닌 경우 페이지를 pcp의 선두(hot)에 추가한다.
  • else list_add_tail(&page->lru, &pcp->lists[migratetype]);
    • cold 요청인 경우 페이지를 pcp의 후미(cold)에 추가한다.
  • pcp->count++;
    • pcp 카운터를 1 증가시킨다.
  • if (pcp->count >= pcp->high) { unsigned long batch = ACCESS_ONCE(pcp->batch); free_pcppages_bulk(zone, batch, pcp); pcp->count -= batch; }
    • pcp 관리 카운터가 제한(high) 수를 넘기면 pcp의 일부(batch 수)를 버디 시스템으로 회수시키고 pcp 관리 카운터를 batch 만큼 뺀다.

 

free_pcppages_bulk()

mm/page_alloc.c

/*
 * Frees a number of pages from the PCP lists
 * Assumes all pages on list are in same zone, and of same order.
 * count is the number of pages to free.
 *
 * If the zone was previously in an "all pages pinned" state then look to
 * see if this freeing clears that state.
 *
 * And clear the zone's pages_scanned counter, to hold off the "all pages are
 * pinned" detection logic.
 */
static void free_pcppages_bulk(struct zone *zone, int count,
                                        struct per_cpu_pages *pcp)
{
        int migratetype = 0;
        int batch_free = 0;
        int to_free = count;
        unsigned long nr_scanned;

        spin_lock(&zone->lock);
        nr_scanned = zone_page_state(zone, NR_PAGES_SCANNED);
        if (nr_scanned)
                __mod_zone_page_state(zone, NR_PAGES_SCANNED, -nr_scanned);

        while (to_free) {
                struct page *page;
                struct list_head *list;

                /*
                 * Remove pages from lists in a round-robin fashion. A
                 * batch_free count is maintained that is incremented when an
                 * empty list is encountered.  This is so more pages are freed
                 * off fuller lists instead of spinning excessively around empty
                 * lists
                 */
                do {
                        batch_free++;
                        if (++migratetype == MIGRATE_PCPTYPES)
                                migratetype = 0;
                        list = &pcp->lists[migratetype];
                } while (list_empty(list));

                /* This is the only non-empty list. Free them all. */
                if (batch_free == MIGRATE_PCPTYPES)
                        batch_free = to_free;

                do {
                        int mt; /* migratetype of the to-be-freed page */

                        page = list_entry(list->prev, struct page, lru);
                        /* must delete as __free_one_page list manipulates */
                        list_del(&page->lru);
                        mt = get_freepage_migratetype(page);
                        if (unlikely(has_isolate_pageblock(zone)))
                                mt = get_pageblock_migratetype(page);

                        /* MIGRATE_MOVABLE list may include MIGRATE_RESERVEs */
                        __free_one_page(page, page_to_pfn(page), zone, 0, mt);
                        trace_mm_page_pcpu_drain(page, 0, mt);
                } while (--to_free && --batch_free && !list_empty(list));
        }
        spin_unlock(&zone->lock);
}

요청 zone에 대한 Per-Cpu Page Fram Cache를 비운다. 그리고 비운 페이지 수 만큼 vm_stat에서 감소시킨다.

  • nr_scanned = zone_page_state(zone, NR_PAGES_SCANNED);
    • zone->vm_stat[NR_PAGES_SCANNED]를 알아온다.
  • if (nr_scanned) __mod_zone_page_state(zone, NR_PAGES_SCANNED, -nr_scanned);
    • 읽어온 nr_scanned 만큼 zone->vm_stat[NR_PAGES_SCANNED]를 감소시킨다.
  • while (to_free) {
    • free할 페이지 수 만큼
  • do { batch_free++;
    • batch_free 카운터는 리스트가 empty될 때 마다 증가되게 하였다.
      • pcp의 3개 리스트에서 로드밸런싱을 위해 1개씩 처리하게한다.
      • 단 list가 비게 되는 경우 다음 list로 이동하게 되면 batch_free를 증가시킨다.
        • 리스트가 비게 되면 너무 spin 되는 것을 억제하게 하기 위해 batch_free를 추가 증가시킨다.
        • 처음에는 1, 리스트가 비면 2, 리스트가 두 개 비면 3이 된다.
  • if (++migratetype == MIGRATE_PCPTYPES) migratetype = 0;
    • migratetype를 1 -> 2 -> 0이 되도록 카운터를 조정한다.
      • MIGRATE_RECLAIMABLE(1)  -> MIGRATE_MOVABLE(2) -> MIGRATE_UNMOVABLE(0)
  • } while (list_empty(list));
    • 리스트가 비어 있는 경우 다른 migrate type의 리스트를 선택하도록 계속한다.
  • if (batch_free == MIGRATE_PCPTYPES) batch_free = to_free;
    • batch_free 카운터가 3이면 batch_free = to_free(free할 남은 페이지 수)를 대입한다.
      • 2개의 list[]가 빈 후 마지막 lists[]만 항목이 남아 있는 경우 batch_free 카운터가 3이될 수 있다.  이러한 경우 아래 루프에서 전체를 삭제할 수 있도록 batch_free 카운터를 to_free 카운터와 동일하게 한다.
  • page = list_entry(list->prev, struct page, lru);
    • 양방향 리스트의 마지막 페이지
  • list_del(&page->lru);
    • 리스트에서 연결을 삭제한다.
  • mt = get_freepage_migratetype(page);
    • page->index에 저장된 migratetype을 가져온다.
    • 버디 시스템에 보내기 위해 pcp의 list[]에서 사용된 migratetype을 사용하지 않고 페이지에 저장된 migratetype을 사용한다.
  • if (unlikely(has_isolate_pageblock(zone))) mt = get_pageblock_migratetype(page);
    • 드문 확률로 지정된 zone에 isolate page가 존재하는 경우 해당 페이지 블럭이 다시 갱신되었을 가능성이 있기 때문에 페이지 블럭에서 migratetype을 가져온다.
  • __free_one_page(page, page_to_pfn(page), zone, 0, mt);
    • pcp에서 제거된 페이지를 buddy 메모리 할당자로 이주한다.
      • 버디 시스템의 free_area[0].free_list[mt]에 페이지를 hot 방향으로 추가 한다.
  • } while (–to_free && –batch_free && !list_empty(list));
    • 감소시킨 to_free 카운터가 남아있으면서 역시 감소시킨 batch_free 카운터도 남아 있으면서 리스트가 비어 있지 않은 경우 계속 루프를 돈다.

 

아래 그림은 pcp가 overflow되어 batch 수 만큼 buddy로 이주하는 과정과 순서를 보여준다.

free_pcppages_bulk-2b

  • free_list[0] 슬롯으로 페이지가 이주될 때 free_list[0]에 buddy 페이지가 존재하는 경우 buddy 페이지를 제거하고 다음 order인 free_list[1]으로 합쳐서 추가한다. 동일하게 free_list[1]에서도 buddy 페이지가 발견되면 다음 order로 통합하면서 buddy 페이지가 발견되지 않을 때까지 통합한다.

 

다음 그림은 pcp에서 버디로 옮겨지는 페이지의 순서를 보여준다.

free_pcppages_bulk-1a

 

다음과 같이 zone별 pagesets에 대한 카운터 정보를 확인할 수 있다.

pi@pi /proc $ cat zoneinfo
Node 0, zone   Normal
  pages free     190861
        min      2048
        low      2560
        high     3072
        scanned  0
        spanned  241664
        present  241664
        managed  233403
    nr_free_pages 190861
    nr_alloc_batch 222
    nr_inactive_anon 43
    nr_active_anon 1709
    nr_inactive_file 3525
    nr_active_file 28293
    nr_unevictable 0
    nr_mlock     0
    nr_anon_pages 1698
    nr_mapped    1722
    nr_file_pages 31872
    nr_dirty     0
    nr_writeback 0
    nr_slab_reclaimable 4469
    nr_slab_unreclaimable 1884
    nr_page_table_pages 128
    nr_kernel_stack 88
    nr_unstable  0
    nr_bounce    0
    nr_vmscan_write 0
    nr_vmscan_immediate_reclaim 0
    nr_writeback_temp 0
    nr_isolated_anon 0
    nr_isolated_file 0
    nr_shmem     54
    nr_dirtied   47369
    nr_written   41212
    nr_pages_scanned 0
    workingset_refault 0
    workingset_activate 0
    workingset_nodereclaim 0
    nr_anon_transparent_hugepages 0
    nr_free_cma  935
        protection: (0, 0)
  pagesets
    cpu: 0
              count: 50
              high:  186
              batch: 31
  vm stats threshold: 24
    cpu: 1
              count: 106
              high:  186
              batch: 31
  vm stats threshold: 24
    cpu: 2
              count: 153
              high:  186
              batch: 31
  vm stats threshold: 24
    cpu: 3
              count: 156
              high:  186
              batch: 31
  vm stats threshold: 24
  all_unreclaimable: 0
  start_pfn:         0
  inactive_ratio:    1

 

get_freepage_migratetype()

include/linux/mm.h

/* It's valid only if the page is free path or free_list */
static inline int get_freepage_migratetype(struct page *page)
{
        return page->index;
}

page->index에 저장된 migratetype을 알아온다.

 

has_isolate_pageblock()

include/linux/page-isolation.h

#ifdef CONFIG_MEMORY_ISOLATION
static inline bool has_isolate_pageblock(struct zone *zone)
{
        return zone->nr_isolate_pageblock;
} 
#else
static inline bool has_isolate_pageblock(struct zone *zone)
{
        return false;
}
#endif

지정된 zone에 isolate된 페이지가 존재하는지 여부를 리턴한다.

 

free_pages_prepare()

mm/page_alloc.c

static bool free_pages_prepare(struct page *page, unsigned int order)
{
        bool compound = PageCompound(page);
        int i, bad = 0;

        VM_BUG_ON_PAGE(PageTail(page), page);
        VM_BUG_ON_PAGE(compound && compound_order(page) != order, page);

        trace_mm_page_free(page, order);
        kmemcheck_free_shadow(page, order);
        kasan_free_pages(page, order);

        if (PageAnon(page))
                page->mapping = NULL;
        bad += free_pages_check(page);
        for (i = 1; i < (1 << order); i++) {
                if (compound)
                        bad += free_tail_pages_check(page, page + i);
                bad += free_pages_check(page + i);
        }
        if (bad)
                return false;

        reset_page_owner(page, order);

        if (!PageHighMem(page)) {
                debug_check_no_locks_freed(page_address(page),
                                           PAGE_SIZE << order);
                debug_check_no_obj_freed(page_address(page),
                                           PAGE_SIZE << order);
        }
        arch_free_page(page, order);
        kernel_map_pages(page, 1 << order, 0);

        return true;
}

페이지들을 버디 시스템으로 free 하기 전에 각 페이지의 플래그들을 확인하여 bad 요건이 있는지 모두 확인한다. true=이상 없음, false=bad 페이지

  • if (PageAnon(page)) page->mapping = NULL;
    • PAGE_MAPPING_ANON으로 되어 있지 않는 경우 page->mapping=null로 초기화
  • bad += free_pages_check(page);
    • 첫 페이지가 bad 페이지인지 확인한다.
  • for (i = 1; i < (1 << order); i++) { if (compound) bad += free_tail_pages_check(page, page + i); bad += free_pages_check(page + i); }
    • 첫 페이지를 제외하고 2^order 페이지까지 루프를 돌며 다음 두 가지를 체크한다.
      • CONFIG_DEBUG_VM 커널 옵션이 사용되는 경우 compound 페이지 구성 확인을 위해 각 페이지를 조사한다.
      • 각 페이지를 확인하여 bad 페이지인지 확인한다.
  • if (bad) return false;
    • 하나라도 bad 조건이 발생하면 false를 반환한다.
  • reset_page_owner(page, order);
    • 2^order 페이지들에 해당하는 각각의 page_ext를 찾아 owner 플래그를 clear 한다.

 

free_pages_check()

mm/page_alloc.c

static inline int free_pages_check(struct page *page)
{
        const char *bad_reason = NULL;
        unsigned long bad_flags = 0;

        if (unlikely(page_mapcount(page)))
                bad_reason = "nonzero mapcount";
        if (unlikely(page->mapping != NULL))
                bad_reason = "non-NULL mapping";
        if (unlikely(atomic_read(&page->_count) != 0))
                bad_reason = "nonzero _count";
        if (unlikely(page->flags & PAGE_FLAGS_CHECK_AT_FREE)) {
                bad_reason = "PAGE_FLAGS_CHECK_AT_FREE flag(s) set";
                bad_flags = PAGE_FLAGS_CHECK_AT_FREE;
        }
#ifdef CONFIG_MEMCG
        if (unlikely(page->mem_cgroup))
                bad_reason = "page still charged to cgroup";
#endif
        if (unlikely(bad_reason)) {
                bad_page(page, bad_reason, bad_flags);
                return 1;
        }
        page_cpupid_reset_last(page);
        if (page->flags & PAGE_FLAGS_CHECK_AT_PREP)
                page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
        return 0;
}

페이지의 각 플래그 비트 설정에 문제가 있는지 확인한다. 1=bad 페이지, 0=정상 페이지

 

bad_page()

mm/page_alloc.c

static void bad_page(struct page *page, const char *reason,
                unsigned long bad_flags)
{
        static unsigned long resume;
        static unsigned long nr_shown;
        static unsigned long nr_unshown;

        /* Don't complain about poisoned pages */
        if (PageHWPoison(page)) {
                page_mapcount_reset(page); /* remove PageBuddy */
                return;
        }

        /*
         * Allow a burst of 60 reports, then keep quiet for that minute;
         * or allow a steady drip of one report per second.
         */
        if (nr_shown == 60) {
                if (time_before(jiffies, resume)) {
                        nr_unshown++;
                        goto out;
                }
                if (nr_unshown) {
                        printk(KERN_ALERT
                              "BUG: Bad page state: %lu messages suppressed\n",
                                nr_unshown);
                        nr_unshown = 0;
                }
                nr_shown = 0;
        }
        if (nr_shown++ == 0)
                resume = jiffies + 60 * HZ;

        printk(KERN_ALERT "BUG: Bad page state in process %s  pfn:%05lx\n",
                current->comm, page_to_pfn(page));
        dump_page_badflags(page, reason, bad_flags);

        print_modules();
        dump_stack();
out:
        /* Leave bad fields for debug, except PageBuddy could make trouble */
        page_mapcount_reset(page); /* remove PageBuddy */
        add_taint(TAINT_BAD_PAGE, LOCKDEP_NOW_UNRELIABLE);
}

 

free_tail_pages_check()

mm/page_alloc.c

static int free_tail_pages_check(struct page *head_page, struct page *page)
{
        if (!IS_ENABLED(CONFIG_DEBUG_VM))
                return 0;
        if (unlikely(!PageTail(page))) {
                bad_page(page, "PageTail not set", 0);
                return 1;
        }
        if (unlikely(page->first_page != head_page)) {
                bad_page(page, "first_page not consistent", 0);
                return 1;
        }
        return 0;
}

bad 페이지에 대한 정보를 KERN_ALERT 출력 레벨로 출력한다.

  • 메시지를 출력할 때 60개 까지 카운팅을 반복하여 출력하며 1번 메시지를 출력할 때 1분의 타이머가 동작하여 최대 burst하게 60개까지 출력 후 그 이후 메시지는 타이머가 리셋될 때 까지 출력을 하지 않는다.
    • 대량의 페이지에 대한 로그가 출력되는 경우를 막기 위해 분당 60개로 제한한다.

 

free_one_page()

mm/page_alloc.c

static void free_one_page(struct zone *zone,
                                struct page *page, unsigned long pfn,
                                unsigned int order,
                                int migratetype)
{
        unsigned long nr_scanned;
        spin_lock(&zone->lock);
        nr_scanned = zone_page_state(zone, NR_PAGES_SCANNED);
        if (nr_scanned)
                __mod_zone_page_state(zone, NR_PAGES_SCANNED, -nr_scanned);

        if (unlikely(has_isolate_pageblock(zone) ||
                is_migrate_isolate(migratetype))) {
                migratetype = get_pfnblock_migratetype(page, pfn);
        }
        __free_one_page(page, pfn, zone, order, migratetype);
        spin_unlock(&zone->lock);
}
  • nr_scanned = zone_page_state(zone, NR_PAGES_SCANNED);
    • zone->vm_stat[NR_PAGES_SCANNED] 값을 읽어온다.
  • if (nr_scanned) __mod_zone_page_state(zone, NR_PAGES_SCANNED, -nr_scanned);
    • zone->vm_stat[NR_PAGES_SCANNED] 값에 -nr_scanned를 더한다.
      • 0으로 만드는 효과
    • vm_stat[NR_PAGES_SCANNED] 값에 -nr_scanned를 더한다.
  • if (unlikely(has_isolate_pageblock(zone) || is_migrate_isolate(migratetype))) { migratetype = get_pfnblock_migratetype(page, pfn); }
    • zone에 isolate 타입이 존재하거나 인수로 isolate 타입이 지정된 경우 pfnblock에서 migratetype을 알아온다.
  • __free_one_page(page, pfn, zone, order, migratetype);
    • 최종적으로 버디 시스템에 free 요청

 

__free_one_page()

mm/page_alloc.c

/*
 * Freeing function for a buddy system allocator.
 *
 * The concept of a buddy system is to maintain direct-mapped table
 * (containing bit values) for memory blocks of various "orders".
 * The bottom level table contains the map for the smallest allocatable
 * units of memory (here, pages), and each level above it describes
 * pairs of units from the levels below, hence, "buddies".
 * At a high level, all that happens here is marking the table entry
 * at the bottom level available, and propagating the changes upward
 * as necessary, plus some accounting needed to play nicely with other
 * parts of the VM system.
 * At each level, we keep a list of pages, which are heads of continuous
 * free pages of length of (1 << order) and marked with _mapcount
 * PAGE_BUDDY_MAPCOUNT_VALUE. Page's order is recorded in page_private(page)
 * field.
 * So when we are allocating or freeing one, we can derive the state of the
 * other.  That is, if we allocate a small block, and both were
 * free, the remainder of the region must be split into blocks.
 * If a block is freed, and its buddy is also free, then this
 * triggers coalescing into a block of larger size.
 *
 * -- nyc
 */

static inline void __free_one_page(struct page *page,
                unsigned long pfn,
                struct zone *zone, unsigned int order,
                int migratetype)
{
        unsigned long page_idx;
        unsigned long combined_idx;
        unsigned long uninitialized_var(buddy_idx);
        struct page *buddy;
        int max_order = MAX_ORDER;

        VM_BUG_ON(!zone_is_initialized(zone));
        VM_BUG_ON_PAGE(page->flags & PAGE_FLAGS_CHECK_AT_PREP, page);

        VM_BUG_ON(migratetype == -1);
        if (is_migrate_isolate(migratetype)) {
                /*
                 * We restrict max order of merging to prevent merge
                 * between freepages on isolate pageblock and normal
                 * pageblock. Without this, pageblock isolation
                 * could cause incorrect freepage accounting.
                 */
                max_order = min(MAX_ORDER, pageblock_order + 1);
        } else {
                __mod_zone_freepage_state(zone, 1 << order, migratetype);
        }

        page_idx = pfn & ((1 << max_order) - 1);

        VM_BUG_ON_PAGE(page_idx & ((1 << order) - 1), page);
        VM_BUG_ON_PAGE(bad_range(zone, page), page);

 

        while (order < max_order - 1) {
                buddy_idx = __find_buddy_index(page_idx, order);
                buddy = page + (buddy_idx - page_idx);
                if (!page_is_buddy(page, buddy, order))
                        break;
                /*
                 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
                 * merge with it and move up one order.
                 */
                if (page_is_guard(buddy)) {
                        clear_page_guard(zone, buddy, order, migratetype);
                } else {
                        list_del(&buddy->lru);
                        zone->free_area[order].nr_free--;
                        rmv_page_order(buddy);
                }
                combined_idx = buddy_idx & page_idx;
                page = page + (combined_idx - page_idx);
                page_idx = combined_idx;
                order++;
        }
        set_page_order(page, order);

        /*
         * If this is not the largest possible page, check if the buddy
         * of the next-highest order is free. If it is, it's possible
         * that pages are being freed that will coalesce soon. In case,
         * that is happening, add the free page to the tail of the list
         * so it's less likely to be used soon and more likely to be merged
         * as a higher order page
         */
        if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
                struct page *higher_page, *higher_buddy;
                combined_idx = buddy_idx & page_idx;
                higher_page = page + (combined_idx - page_idx);
                buddy_idx = __find_buddy_index(combined_idx, order + 1);
                higher_buddy = higher_page + (buddy_idx - combined_idx);
                if (page_is_buddy(higher_page, higher_buddy, order + 1)) {
                        list_add_tail(&page->lru,
                                &zone->free_area[order].free_list[migratetype]);
                        goto out;
                }
        }

        list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
out:
        zone->free_area[order].nr_free++;
}

버디 시스템은 메모리 영역을 2^max_order(10) 페이지 단위로 align하여 관리하고 내부에서 order 슬롯으로 2^order 페이지 단위를 버디(쌍)으로 관리한다. 따라서 아래 루틴에서 free 페이지를 추가하기 전에 쌍이 되는 free 페이지가 있는 경우 해당 order 슬롯에서 제거한 후 order를 증가시키면서 루프를 돈다. 루프를 빠져나온 후 마지막 결정된 order 슬롯에 페이지를 추가한다.

  • int max_order = MAX_ORDER;
    • 11
  • if (is_migrate_isolate(migratetype)) { max_order = min(MAX_ORDER, pageblock_order + 1); }
    • isolate 타입인 경우 max_order가 pageblock_order+1을 초과하지 않게 한다.
    • arm에서는 MAX_ORDER와 pageblock_order+1이 동일하다.
  • else { __mod_zone_freepage_state(zone, 1 << order, migratetype); }
    • NR_FREE_PAGES 카운터 update
      • zone->vm_stat[NR_FREE_PAGES] 값에 2^order 를 더한다.
        • 0으로 만드는 효과
      • vm_stat[NR_FREE_PAGES,] 값에 2^order를 더한다.
    • cma 타입인 경우 NR_FREE_CMA_PAGES 카운터 update
      • zone->vm_stat[NR_FREE_CMA_PAGES] 값에 2^order를  더한다.
        • 0으로 만드는 효과
      • vm_stat[NR_FREE_CMA_PAGES,] 값에 2^order를 더한다.
  • page_idx = pfn & ((1 << max_order) – 1);
    • 페이지 인덱스가 max_order를 넘어가지 않도록 제한한다.
  • while (order < max_order – 1) {
    • order < max_order-1(10)인 동안 루프를 돈다.
    • 마지막 order(10) 페이지는 buddy 페이지를 찾아 combine할 일이 없으므로 while 문 내부를 진행할 필요 없이 그냥 해당 order의 list에 추가한다.
  • buddy_idx = __find_buddy_index(page_idx, order);
    • page_idx에 대응하는 버디(쌍) 페이지 인덱스를 알아온다.
  •  buddy = page + (buddy_idx – page_idx);
    • buddy 페이지는 page[buddy_idx – page_idx]
  • if (!page_is_buddy(page, buddy, order)) break;
    • 버디 시스템에 이미 짝을 이루는 버디 페이지가 존재하지 않는 경우 더 이상 combine할 필요가 없어서 루프를 빠져나온다.
  • if (page_is_guard(buddy)) { clear_page_guard(zone, buddy, order, migratetype); }
    • 버디 페이지가 guard 설정된 경우 버디 페이지들에서 guard를 clear한다.
  • else { list_del(&buddy->lru); zone->free_area[order].nr_free–; rmv_page_order(buddy); }
    • combine을 하기 전에 먼저 현재 슬롯에서 버디 페이지를 아래와 같은 순서로 제거한다.
      • buddy 페이지를 리스트에서 제거한다.
      • order 슬롯에서 nr_free를 감소시킨다.
      • 버디 표식인 page->_mapcount에 -1, page->private에 0을 대입한다.
  • combined_idx = buddy_idx & page_idx;
    • 상향된 order에서 사용할 페이지 인덱스를 계산한다.
      • page와 buddy 페이지 인덱스 중 작은 인덱스
      • 예) page_idx=0x100, buddy_idx=0x108, order=3
        • combine_idx=0x100
          • 다음 루프에서 order=4, page_idx=0x100, buddy_idx=0x110이 된다.
  • page = page + (combined_idx – page_idx);
    • 상향된 order에서 사용할 페이지
  • page_idx = combined_idx; order++;
    • page_idx <- 상향된 order에서 사용할 페이지 인덱스를 대입하고 order를 증가시킨다.

order가 MAX_ORDER-2보다 작은 경우 free_list[order]에 페이지를 등록하기 전에 더 상위 order에 buddy 페이지가 존재하는지 확인하여 존재하는 경우 combine될 확률이 높아졌으므로 order 슬롯의 후미(cold)에 페이지를 추가한다.

  • if ((order < MAX_ORDER-2) && pfn_valid_within(page_to_pfn(buddy))) {
    • order가 MAX_ORDER-2보다 작고 buddy 페이지가 valid 영역에 있는 경우
    • 가장 마지막 order(10) 리스트는 combine을 할 필요 없는 리스트이고, 따라서 order값이 마지막보다 2 작은 리스트 까지를 대상으로 그 상위 order와 비교하게 한다.
  • combined_idx = buddy_idx & page_idx;
    • 다시 상향된 order에서 사용할 페이지 인덱스를 준비한다.
  • higher_page = page + (combined_idx – page_idx);
    • 더 상향된 order 페이지
  • buddy_idx = __find_buddy_index(combined_idx, order + 1);
    • 더 상향된 order에서 짝이 되는 버디 페이지가 존재하는지 찾아본다.
  • higher_buddy = higher_page + (buddy_idx – combined_idx);
    • 더 상향된 버디 페이지
  • if (page_is_buddy(higher_page, higher_buddy, order + 1)) { list_add_tail(&page->lru, &zone->free_area[order].free_list[migratetype]); goto out; }
    • higher_page가 order+1 슬롯에서 짝이되는 버디 페이지가 존재하는 경우 order 슬롯의 후미(cold)에 페이지를 추가한다.

 

  •  list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);
    • order 슬롯의 선두(hot)에 페이지를 추가한다.
  • zone->free_area[order].nr_free++;
    • order 슬롯의 nr_free를 증가시킨다.

 

다음 그림은 unmovable 타입으로 0x7f_4000 ~ 0xb3_1000 까지의 메모리를 free할 때 버디 시스템의 pcp 및 free_area[]로 등록되는 과정을 보여준다.

__free_one_page-2b

 

아래 그림은 free할 페이지가 slot에 추가될 때 상위 slot에 버디 페이지가 발견되면 combine될 가능성이 높아진다. 따라서 free 페이지의 파편화를 최대한 억제하기 위해 cold 방향에 free 페이지들을 추가하는 모습을 보여준다.

__free_one_page-3

 

__find_buddy_index()

mm/internal.h

/*
 * Locate the struct page for both the matching buddy in our
 * pair (buddy1) and the combined O(n+1) page they form (page).
 *
 * 1) Any buddy B1 will have an order O twin B2 which satisfies
 * the following equation:
 *     B2 = B1 ^ (1 << O)
 * For example, if the starting buddy (buddy2) is #8 its order
 * 1 buddy is #10:
 *     B2 = 8 ^ (1 << 1) = 8 ^ 2 = 10
 *
 * 2) Any buddy B will have an order O+1 parent P which
 * satisfies the following equation:
 *     P = B & ~(1 << O)
 *
 * Assumption: *_mem_map is contiguous at least up to MAX_ORDER
 */
static inline unsigned long
__find_buddy_index(unsigned long page_idx, unsigned int order) 
{
        return page_idx ^ (1 << order);
}

요청한 페이지 인덱스와 짝을 이루는 버디 페이지의 인덱스를 반환한다.

  • 예) page_idx=0x1000, order=3
    • 버디 페이지 인덱스=0x1008
  • 예) page_idx=0x1008, order=3
    • 버디 페이지 인덱스0x1000

 

page_is_buddy()

mm/page_alloc.c

/*
 * This function checks whether a page is free && is the buddy
 * we can do coalesce a page and its buddy if
 * (a) the buddy is not in a hole &&
 * (b) the buddy is in the buddy system &&
 * (c) a page and its buddy have the same order &&
 * (d) a page and its buddy are in the same zone.
 *
 * For recording whether a page is in the buddy system, we set ->_mapcount
 * PAGE_BUDDY_MAPCOUNT_VALUE.
 * Setting, clearing, and testing _mapcount PAGE_BUDDY_MAPCOUNT_VALUE is
 * serialized by zone->lock.
 *
 * For recording page's order, we use page_private(page).
 */
static inline int page_is_buddy(struct page *page, struct page *buddy,
                                                        unsigned int order)
{
        if (!pfn_valid_within(page_to_pfn(buddy)))
                return 0;

        if (page_is_guard(buddy) && page_order(buddy) == order) {
                if (page_zone_id(page) != page_zone_id(buddy))
                        return 0;

                VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);

                return 1;
        }

        if (PageBuddy(buddy) && page_order(buddy) == order) {
                /*
                 * zone check is done late to avoid uselessly
                 * calculating zone/node ids for pages that could
                 * never merge.
                 */
                if (page_zone_id(page) != page_zone_id(buddy))
                        return 0;

                VM_BUG_ON_PAGE(page_count(buddy) != 0, buddy);

                return 1;
        }
        return 0;
}

buddy 페이지의 valid 및 order를 검사하여 정상이면 1, 그렇지 않으면 0을 반환한다.

  • buddy 페이지가 hole이 아닌 valid page 범위에 있고 해당 buddy 페이지의 order가 인수 요청과 동일하고 page와 buddy 페이지의 zone이 동일한지 검사한다.

 

참고

mem_init()

lowmem 및 highmem에 대한 모든 free memblock 영역에 대해 Buddy memory allocator의 빈 페이지로 이관 등록한다. memblock을 더 이상 사용하지 않는 경우 reserved & memory memblock 관리배열까지 Buddy로 free 시킨다.

mem_init-1

 

free_highpages-1

 

mem_init()

arch/arm/mm/init.c

/*
 * mem_init() marks the free areas in the mem_map and tells us how much
 * memory is free.  This is done after various parts of the system have
 * claimed their memory after the kernel image.
 */
void __init mem_init(void)
{
#ifdef CONFIG_HAVE_TCM
        /* These pointers are filled in on TCM detection */
        extern u32 dtcm_end;
        extern u32 itcm_end;
#endif

        set_max_mapnr(pfn_to_page(max_pfn) - mem_map);

        /* this will put all unused low memory onto the freelists */
        free_unused_memmap();
        free_all_bootmem();

#ifdef CONFIG_SA1111
        /* now that our DMA memory is actually so designated, we can free it */
        free_reserved_area(__va(PHYS_OFFSET), swapper_pg_dir, -1, NULL);
#endif

        free_highpages();

        mem_init_print_info(NULL);
  • set_max_mapnr(pfn_to_page(max_pfn) – mem_map);
    • UMA 시스템에서만 전역 max_mapnr에 mem_map[] 배열에 대한 인덱스 번호를 저장한다.
  • free_unused_memmap();
    • Sparse 메모리 모델 또는 Discontig 메모리 모델에서 메모리 사이의 사용되지 않는 공간이 상당히 클 수 있다. 따라서 이에 대해 메모리 낭비가 발생하지 않도록 미사용 공간에 대한 mem_map[]을 페이지 단위로 reserve memblock에서 free 시킨다.
  • free_all_bootmem();
    • free memblock 영역에 대해 모두 Buddy memory allocator의 빈 페이지로 이관 등록한다.
    • memblock을 더 이상 사용하지 않는 경우 reserved & memory memblock 관리배열까지 Buddy로 free 시킨다.
  • free_highpage();
    • highmem 메모리 영역을 모두 Buddy memory allocator의 free 페이지로 이관 등록한다.

 

#define MLK(b, t) b, t, ((t) - (b)) >> 10
#define MLM(b, t) b, t, ((t) - (b)) >> 20
#define MLK_ROUNDUP(b, t) b, t, DIV_ROUND_UP(((t) - (b)), SZ_1K)

        pr_notice("Virtual kernel memory layout:\n"
                        "    vector  : 0x%08lx - 0x%08lx   (%4ld kB)\n"
#ifdef CONFIG_HAVE_TCM
                        "    DTCM    : 0x%08lx - 0x%08lx   (%4ld kB)\n"
                        "    ITCM    : 0x%08lx - 0x%08lx   (%4ld kB)\n"
#endif
                        "    fixmap  : 0x%08lx - 0x%08lx   (%4ld kB)\n"
                        "    vmalloc : 0x%08lx - 0x%08lx   (%4ld MB)\n"
                        "    lowmem  : 0x%08lx - 0x%08lx   (%4ld MB)\n"
#ifdef CONFIG_HIGHMEM
                        "    pkmap   : 0x%08lx - 0x%08lx   (%4ld MB)\n"
#endif
#ifdef CONFIG_MODULES
                        "    modules : 0x%08lx - 0x%08lx   (%4ld MB)\n"
#endif
                        "      .text : 0x%p" " - 0x%p" "   (%4td kB)\n"
                        "      .init : 0x%p" " - 0x%p" "   (%4td kB)\n"
                        "      .data : 0x%p" " - 0x%p" "   (%4td kB)\n"
                        "       .bss : 0x%p" " - 0x%p" "   (%4td kB)\n",

                        MLK(UL(CONFIG_VECTORS_BASE), UL(CONFIG_VECTORS_BASE) +
                                (PAGE_SIZE)),
#ifdef CONFIG_HAVE_TCM
                        MLK(DTCM_OFFSET, (unsigned long) dtcm_end),
                        MLK(ITCM_OFFSET, (unsigned long) itcm_end),
#endif
                        MLK(FIXADDR_START, FIXADDR_END),
                        MLM(VMALLOC_START, VMALLOC_END),
                        MLM(PAGE_OFFSET, (unsigned long)high_memory),
#ifdef CONFIG_HIGHMEM
                        MLM(PKMAP_BASE, (PKMAP_BASE) + (LAST_PKMAP) *
                                (PAGE_SIZE)),
#endif
#ifdef CONFIG_MODULES
                        MLM(MODULES_VADDR, MODULES_END),
#endif

                        MLK_ROUNDUP(_text, _etext),
                        MLK_ROUNDUP(__init_begin, __init_end),
                        MLK_ROUNDUP(_sdata, _edata),
                        MLK_ROUNDUP(__bss_start, __bss_stop));

#undef MLK
#undef MLM
#undef MLK_ROUNDUP
  • ARMv7 아키텍처를 사용하는 rpi2
 Virtual kernel memory layout:
     vector  : 0xffff0000 - 0xffff1000   (   4 kB)
     fixmap  : 0xffc00000 - 0xfff00000   (3072 kB)
     vmalloc : 0xbb800000 - 0xff000000   (1080 MB)
     lowmem  : 0x80000000 - 0xbb000000   ( 944 MB)
     modules : 0x7f000000 - 0x80000000   (  16 MB)
       .text : 0x80008000 - 0x8081b128   (8269 kB)
       .init : 0x8081c000 - 0x809e4000   (1824 kB)
       .data : 0x809e4000 - 0x80a5b6a4   ( 478 kB)
       .bss : 0x80a5b6a4 - 0x81336908   (9069 kB)
  • 인텔 i5 cpu를 사용하는 virtual-box에서 ubuntu 예)
virtual kernel memory layout:
    fixmap  : 0xfff15000 - 0xfffff000   ( 936 kB)
    pkmap   : 0xffc00000 - 0xffe00000   (2048 kB)
    vmalloc : 0xf83fe000 - 0xffbfe000   ( 120 MB)
    lowmem  : 0xc0000000 - 0xf7bfe000   ( 891 MB)
      .init : 0xc1a9d000 - 0xc1b7c000   ( 892 kB)
      .data : 0xc16f5d02 - 0xc1a9bcc0   (3735 kB)
      .text : 0xc1000000 - 0xc16f5d02   (7127 kB)

 

        /*
         * Check boundaries twice: Some fundamental inconsistencies can
         * be detected at build time already.
         */
#ifdef CONFIG_MMU
        BUILD_BUG_ON(TASK_SIZE                          > MODULES_VADDR);
        BUG_ON(TASK_SIZE                                > MODULES_VADDR);
#endif

#ifdef CONFIG_HIGHMEM
        BUILD_BUG_ON(PKMAP_BASE + LAST_PKMAP * PAGE_SIZE > PAGE_OFFSET);
        BUG_ON(PKMAP_BASE + LAST_PKMAP * PAGE_SIZE      > PAGE_OFFSET);
#endif

        if (PAGE_SIZE >= 16384 && get_num_physpages() <= 128) {
                extern int sysctl_overcommit_memory;
                /*
                 * On a machine this small we won't get
                 * anywhere without overcommit, so turn
                 * it on by default.
                 */
                sysctl_overcommit_memory = OVERCOMMIT_ALWAYS;
        }
}

 

다음 그림은 early memory allocator 인 memblock 에서 buddy memory allocator로 free 메모리 관리가 전환되는 모습을 보여준다.

mem_init-2

 

free_unused_memmap()

arch/arm/mm/init.c

/*
 * The mem_map array can get very big.  Free the unused area of the memory map.
 */
static void __init free_unused_memmap(void)
{
        unsigned long start, prev_end = 0;
        struct memblock_region *reg;

        /*
         * This relies on each bank being in address order.
         * The banks are sorted previously in bootmem_init().
         */
        for_each_memblock(memory, reg) {
                start = memblock_region_memory_base_pfn(reg);

#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));
#else
                /*
                 * Align down here since the VM subsystem insists that the
                 * memmap entries are valid from the bank start aligned to
                 * MAX_ORDER_NR_PAGES.
                 */
                start = round_down(start, MAX_ORDER_NR_PAGES);
#endif
                /*
                 * 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 the VM subsystem insists that the
                 * memmap entries are valid from the bank end aligned to
                 * MAX_ORDER_NR_PAGES.
                 */
                prev_end = ALIGN(memblock_region_memory_end_pfn(reg),
                                 MAX_ORDER_NR_PAGES);
        }

#ifdef CONFIG_SPARSEMEM
        if (!IS_ALIGNED(prev_end, PAGES_PER_SECTION))
                free_memmap(prev_end,
                            ALIGN(prev_end, PAGES_PER_SECTION));
#endif
}

mem_map[]에서 메모리 영역에 해당하지 않는 부분만 memblock에서 페이지 단위로 free하는데 메모리 모델에 따라 다음과 같이 동작한다.

  • Sparse 메모리 모델 (O)
    • 메모리와 메모리 사이의 hole에 대해서는 섹션이 구성되어 있지 않아 관련 mem_map[] 배열이 없어서 삭제할 mem_map[]이 없다.
    • 하나의 섹션을 가득 채우지 못한 메모리의 경우 남는 공간만큼의 mem_map[] 배열에 페이지 단위로 free 시킬 수 있다.
  • Discontig 메모리 모델 (X)
    • hole에 해당하는 mem_map[] 배열을 페이지 단위로 free시킬 수 있으나 arm에서 Discontig 메모리 모델을 사용하지 않게 되어 해당 사항 없다.
  • Flat 메모리 모델 (X)
    • hole이 없어 해당 사항 없다.

 

  • for_each_memblock(memory, reg) {
    • memory memblock 엔트리 수 만큼 루프
  • start = memblock_region_memory_base_pfn(reg);
    • PFN_UP(reg->base);
      • 물리 시작 주소에 PAGE_SIZE 단위로 round up한 후 pfn으로 변환
  • start = min(start, ALIGN(prev_end, PAGES_PER_SECTION));
    • Sparse memory model을 사용하는 경우 물리 시작 주소가 이전 기억해둔 memblock의 끝 주소를 PAGES_PER_SECTION 단위로 round up한 수를 초과하지 않게 한다.
    • PAGES_PER_SECTION
      • Sparse memory model의 섹션당 페이지 수
        • ARM 페이지 테이블 매핑에서 사용하는 섹션과 혼동하면 안된다.
  • start = round_down(start, MAX_ORDER_NR_PAGES);
    • Sparse memory model이 아닌 경우 물리 시작 주소를 MAX_ORDER_NR_PAGES 단위로 round down 한다.
    • MAX_ORDER_NR_PAGES
      • (1 << (MAX_ORDER – 1))
        • 1024
  • if (prev_end && prev_end < start) free_memmap(prev_end, start)
    • hole이 있는 경우 hole 만큼의 page를 관리하는 mem_map[]을 free 시킨다.
  • prev_end = ALIGN(memblock_region_memory_end_pfn(reg), MAX_ORDER_NR_PAGES);
    • memblock의 끝 주소를 round down하여 pfn으로 변환한 수를 MAX_ORDER_NR_PAGES 단위로 round up한 pfn 값
  • if (!IS_ALIGNED(prev_end, PAGES_PER_SECTION)) free_memmap(prev_end, ALIGN(prev_end, PAGES_PER_SECTION));
    • Sparsemem에서 마지막 memory memblock의 끝이 PAGES_PER_SECTION 단위로 align되지 않은 경우 해당 영역에 해당하는 mem_map[]을 free 시킨다.

 

아래 그림은 두 개의 메모리 사이에 hole을 발생시켰고 각각의 섹션에 메모리가 일부만 채워진 경우 남는 공간에 대한 mem_map[] 배열에서 사용되지 않는 공간을 페이지 단위로 free 하는 것을  보여준다.

free_unused_memmap-1a

 

free_memmap()

arch/arm/mm/init.c

static inline void
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_early(pg, pgend - pg);
}

start_pfn ~ end_pfn에 해당하는 mem_map[] 영역을 reserve memblock에서 free(remove)한다.

  • start_pg = pfn_to_page(start_pfn – 1) + 1;
    • start_pfn으로 mem_map[]의 page 구조체 주소를 알아온다.
    • 인수로 주어진 start_pfn은 sparse memory의 경우 커널이 인식하지 못하는 unused 또는 hole 영역일 수 있기 때문에 이 주소를 사용하여 page 주소를 알아오려는 경우 잘못된 값을 알아올 수 있어서 패치를 하였다.
    • 참고: ARM: 5747/1: Fix the start_pg value in free_memmap()
  • end_pg = pfn_to_page(end_pfn – 1) + 1;
    • end_pfn으로 mem_map[]의 page 구조체 주소를 알아온다.
    • 역시 인수로 주어진 end_pfn은 sparse memory의 경우 커널이 인식하지 못하는 unused 또는 hole 영역일 수 있기 때문에 이 주소를 사용하여 page 주소를 알아오려는 경우 잘못된 값을 알아올 수 있어서 패치를 하였다
    • 참고: ARM: 6890/1: memmap: only free allocated memmap entries when using SPARSEMEM
  • pg = PAGE_ALIGN(__pa(start_pg));
    • start_pg를 물리주소로 변환하고 페이지 사이즈 단위로 round up 한다.
  • pgend = __pa(end_pg) & PAGE_MASK;
    • end_pg를 물리주소로 변환하고 페이지 사이즈 단위로 round down 한다.
  •  if (pg < pgend) memblock_free_early(pg, pgend – pg);
    • reserve memblock 영역에 등록된 mem_map[]의 unused 공간을 reserve memblock에서 free(remove) 한다.

 

free_all_bootmem()

이 함수는 CONFIG_NO_BOOTMEM 커널 옵션을 사용하는 소스를 분석한다. 즉 memblock을 바로 사용하는 mm/nobootmem.c 화일을 사용한다.

  • 최근에는 사용하지 않게된 bootmem을 사용하는 소스는 mm/bootmem.c를 사용하며 이 case는 추가로 분석하지 않는다. (deprecated)

mm/nobootmem.c

/**
 * free_all_bootmem - release free pages to the buddy allocator
 *
 * Returns the number of pages actually released.
 */
unsigned long __init free_all_bootmem(void)
{
        unsigned long pages;

        reset_all_zones_managed_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
         */
        pages = free_low_memory_core_early();
        totalram_pages += pages;

        return pages;
}

모든 free lowmem 영역을 모두 버디 시스템의 free_list에 이관 등록한다. hotplug memory를 사용하지 않는 대부분의 시스템은 버디 시스템이 활성화되면 memblock을 더 이상 사용하지 않게되는데 이 때 reserve & memory memblock의 관리 배열을 더 이상 사용하지 않으므로 이에 대한 영역도 버디 시스템에 이관한다.

  • reset_all_zones_managed_pages();
    • 모든 online 노드의 각 zone->managed_pages를 0으로 초기화한다.
    • zone->managed_pages
      • zone에서 사용가능한 free 페이지 수
  • pages = free_low_memory_core_early();
    • 모든 free lowmem 영역들을 버디 시스템의 free_list에 이관 등록한다.
    • memblock을 더 이상 사용하지 않는 경우 reserve & memory memblock 관리 배열도 버디 시스템의 free_list에 이관 등록한다.
  • totalram_pages += pages;
    • free된 페이지들을 전역 totalram_pages에 추가한다.

 

reset_all_zones_managed_pages()

mm/nobootmem.c

void __init reset_all_zones_managed_pages(void)
{
        struct pglist_data *pgdat;

        if (reset_managed_pages_done)
                return;

        for_each_online_pgdat(pgdat)
                reset_node_managed_pages(pgdat);

        reset_managed_pages_done = 1;
}

모든 online 노드의 각 zone->managed_pages를 0으로 초기화한다.

 

reset_node_managed_pages()

mm/nobootmem.c

void reset_node_managed_pages(pg_data_t *pgdat)
{
        struct zone *z;

        for (z = pgdat->node_zones; z < pgdat->node_zones + MAX_NR_ZONES; z++)
                z->managed_pages = 0;
}

해당 노드의 모든 zone->managed_pages를 0으로 초기화한다.

 

free_low_memory_core_early()

mm/nobootmem.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);

        for_each_free_mem_range(i, NUMA_NO_NODE, &start, &end, NULL)
                count += __free_memory_core(start, end);

#ifdef CONFIG_ARCH_DISCARD_MEMBLOCK
        {
                phys_addr_t size;

                /* Free memblock.reserved array if it was allocated */
                size = get_allocated_memblock_reserved_regions_info(&start);
                if (size)
                        count += __free_memory_core(start, start + size);

                /* Free memblock.memory array if it was allocated */
                size = get_allocated_memblock_memory_regions_info(&start);
                if (size)
                        count += __free_memory_core(start, start + size);
        }
#endif

        return count;
}

모든 free lowmem 영역을 모두 버디 시스템의 free_list에 이관 등록한다. CONFIG_ARCH_DISCARD_MEMBLOCK 커널 옵션을 사용하는 경우 reserve & memory memblock의 관리 배열을 더 이상 사용하지 않으므로 이에 대한 영역도 버디 시스템에 이관한다.

  • memblock_clear_hotplug(0, -1);
    • 전체 memory memblock 영역에 대해 MEMBLOCK_HOTPLUG 비트를 clear 한다.
  • for_each_free_mem_range(i, NUMA_NO_NODE, &start, &end, NULL) count += __free_memory_core(start, end);
    • 모든 free lowmem 영역을 모두 버디 시스템의 free_list에 이관 등록한다.
  • size = get_allocated_memblock_reserved_regions_info(&start);
    • reserved memblock의 regions[] 배열의 사이즈
  • if (size) count += __free_memory_core(start, start + size);
    • reserved memblock의 regions[] 배열에 대한 영역을 모두 버디 시스템의 free_list에 이관 등록한다.
  • size = get_allocated_memblock_memory_regions_info(&start);
    • memory memblock의 regions[] 배열의 사이즈
  • if (size) count += __free_memory_core(start, start + size);
    • memory memblock의 regions[] 배열에 대한 영역을 모두 버디 시스템의 free_list에 이관 등록한다.

 

__free_memory_core()

mm/nobootmem.c

static unsigned long __init __free_memory_core(phys_addr_t start,
                                 phys_addr_t end)
{
        unsigned long start_pfn = PFN_UP(start);
        unsigned long end_pfn = min_t(unsigned long,
                                      PFN_DOWN(end), max_low_pfn);

        if (start_pfn > end_pfn)
                return 0;

        __free_pages_memory(start_pfn, end_pfn);

        return end_pfn - start_pfn;
}

페이지 단위 round up한 시작 주소(start) ~ 페이지 round down 한 끝 주소(end)까지의 pfn에 대해 해당 영역을 버디 시스템의 free_list에 추가한다.

 

__free_pages_memory()

mm/nobootmem.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--;

                __free_pages_bootmem(pfn_to_page(start), order);

                start += (1UL << order);
        }
}

free 요청한 페이지들에 대해 2^order 단위로 잘라서 버디 시스템에 free 요청한다.

  • while (start < end) {
    • start ~ end pfn 까지 루프를 돈다.
  •  order = min(MAX_ORDER – 1UL, __ffs(start));
    • 2^n 단위로 잘라낸다.
      • __ffs()
        • lsb -> msb 순으로 1로 설정된 비트를 찾는다. (based 0) 못찾은 경우는 -1을 반환한다.
    • 예) start=0x10003
      • order=0
  • while (start + (1UL << order) > end) order–;
    • start + 2^order를 더한 페이지 번호가 end를 초과하는 경우 order를 1씩 감소시킨다.
  • __free_pages_bootmem(pfn_to_page(start), order);
    • 2^order 페이지 공간을 버디에서 free 시킨다.
      • 버디 시스템의 free_list[order] 슬롯에 free 영역을 추가한다.
  • start += (1UL << order);
    • start += 2^order를 한 후 다시 루프를 수행한다.

 

아래 그림은 0x10003 ~ 0x10013 pfn에 대해 버디에 free 할 때 5 조각으로 나누어 처리하는 과정을 보여준다.

__free_pages_memory-1

 

__free_pages_bootmem()

mm/page_alloc.c

void __init __free_pages_bootmem(struct page *page, unsigned int order)
{
        unsigned int nr_pages = 1 << order;
        struct page *p = page;
        unsigned int loop;

        prefetchw(p);
        for (loop = 0; loop < (nr_pages - 1); loop++, p++) {
                prefetchw(p + 1);
                __ClearPageReserved(p);
                set_page_count(p, 0);
        }
        __ClearPageReserved(p);
        set_page_count(p, 0);

        page_zone(page)->managed_pages += nr_pages;
        set_page_refcounted(page);
        __free_pages(page, order);
}

free 시킬 페이지에 대해 Reserve 비트를 clear하고 페이지가 참조되지 않음으로 설정(_count <- 0)한다. managed_pages에 free시킬 페이지 만큼 추가하고 첫 페이지를 참조 설정(_count <- 1)한 후 버디 시스템에서 free하게 한다.

  • 조작할 page 구조체 p를 조작하기 전에 pregetchw(p+1)를 호출하여 캐시 라인에 미리 로드를 하게되면 atomic operation 들이 한 번에 성공할 확률이 높아져서 성능 향상에 도움이 된다.
    • page 구조체 p에 해당하는 데이터를 캐시에 로드할 때 p->_count는 p 주소와 12바이트가 떨어져 있어서 p를 캐시에 prefetch하여도 p->_count 영역이 캐시에 prefetch 안될 수도 있다. 따라서 어짜피 다음 페이지 구조체 데이터도 로드할 계획이므로 미리 로드를 해 놓으면 p->_count의 조작 시 atomic operation이 한 번에 성공할 확률이 높아져 성능에 도움이 될 수 있다.
    • L1 d-cache가 최소 16 bytes인 시스템이 있다.
    • rpi2: L1 d-cache line=32 bytes, L2 d-cache line=64 bytes

 

다음 그림과 같이 prefetcw()를 사용하여 next page 구조체를 미리 prefetch하는 이유를 확인해보자.

 

get_allocated_memblock_reserved_regions_info()

mm/memblock.c

#ifdef CONFIG_ARCH_DISCARD_MEMBLOCK
phys_addr_t __init_memblock get_allocated_memblock_reserved_regions_info(
                                        phys_addr_t *addr)
{
        if (memblock.reserved.regions == memblock_reserved_init_regions)
                return 0;

        *addr = __pa(memblock.reserved.regions);

        return PAGE_ALIGN(sizeof(struct memblock_region) *
                          memblock.reserved.max);
}
#endif

CONFIG_ARCH_DISCARD_MEMBLOCK 커널 옵션이 설정된 경우 memblock이 buddy 시스템으로 전환된 후에는 memblock을 사용하지 않게 된다. 따라서 이 memblock 관리 영역을 free 하기 위한 목적으로 주소와 사이즈를 반환한다.

 

free_highpages()

arch/arm/mm/init.c

static void __init free_highpages(void)
{
#ifdef CONFIG_HIGHMEM
        unsigned long max_low = max_low_pfn;
        struct memblock_region *mem, *res;

        /* set highmem page free */
        for_each_memblock(memory, mem) {
                unsigned long start = memblock_region_memory_base_pfn(mem);
                unsigned long end = memblock_region_memory_end_pfn(mem);

                /* Ignore complete lowmem entries */
                if (end <= max_low)
                        continue;

                /* Truncate partial highmem entries */
                if (start < max_low)
                        start = max_low;

                /* Find and exclude any reserved regions */
                for_each_memblock(reserved, res) {
                        unsigned long res_start, res_end;

                        res_start = memblock_region_reserved_base_pfn(res);
                        res_end = memblock_region_reserved_end_pfn(res);

                        if (res_end < start)
                                continue;
                        if (res_start < start)
                                res_start = start;
                        if (res_start > end)
                                res_start = end;
                        if (res_end > end)
                                res_end = end;
                        if (res_start != start)
                                free_area_high(start, res_start);
                        start = res_end;
                        if (start == end)
                                break;
                }

                /* And now free anything which remains */
                if (start < end)
                        free_area_high(start, end);
        }
#endif
}

memblock에서 highmem에 해당하는 영역을 버디 시스템에 free 시킨다.

  • unsigned long max_low = max_low_pfn;
  • max lowmem pfn
  • for_each_memblock(memory, mem) {
    • memory memblock 수 만큼 루프
  • unsigned long start = memblock_region_memory_base_pfn(mem);
    • PFN_UP(reg->base);
      • 물리 시작 주소에 PAGE_SIZE 단위로 round up한 후 pfn으로 변환
  • unsigned long end = memblock_region_memory_end_pfn(mem);
    • PFN_DOWN(reg->base + reg->size);
      • 물리 끝 주소에 round down된 값을 pfn으로 변환
  • if (end <= max_low) continue;
    • memblock 엔트리가 lowmem인 경우는 무시
  • if (start < max_low) start = max_low;
    • memblock 엔트리가 lowmem/highmem 경계에 걸친 경우 lowmem 영역을 무시한다.

 

free_area_high()

arch/arm/mm/init.c

#ifdef CONFIG_HIGHMEM
static inline void free_area_high(unsigned long pfn, unsigned long end)
{
        for (; pfn < end; pfn++)
                free_highmem_page(pfn_to_page(pfn));
}
#endif

pfn ~ end 까지 각각의 pfn에 해당하는 highmem 페이지를 버디 시스템에서 free 처리 한다.

 

free_highmem_page()

mm/page_alloc.c

#ifdef  CONFIG_HIGHMEM
/*
 * Free a highmem page into the buddy system, adjusting totalhigh_pages
 * and totalram_pages.
 */
void free_highmem_page(struct page *page) 
{
        __free_reserved_page(page);
        totalram_pages++;
        page_zone(page)->managed_pages++;
        totalhigh_pages++;
}
#endif

해당 highmem 페이지에서 reserved 플래그를 clear하고 _count=1로 대입한 후 버디 시스템에서 free 처리 한다. 관련 stat들 또한 증가시킨다.

 

__free_reserved_page()

include/linux/mm.h

/* Free the reserved page into the buddy system, so it gets managed. */
static inline void __free_reserved_page(struct page *page)
{
        ClearPageReserved(page);
        init_page_count(page);
        __free_page(page);
}

해당 highmem 페이지에서 reserved 플래그를 clear하고 _count=1로 대입한 후 버디 시스템에서 free 처리 한다.

 

get_num_physpages()

include/linux/mm.h

static inline unsigned long get_num_physpages(void)
{
        int nid;
        unsigned long phys_pages = 0;

        for_each_online_node(nid) 
                phys_pages += node_present_pages(nid);  

        return phys_pages;
}

전체 노드의 present(hole 제외) 페이지 수를 알아온다.

 

include/linux/mmzone.h

#define node_present_pages(nid) (NODE_DATA(nid)->node_present_pages)

 

참고

page_ext_init_flatmem()

page extension

Flat memory model에서 page 구조체를 변경하지 않고 page_ext라는 별도의 구조체를 만들어 page 확장을 하여 디버깅에 도움을 줄 수 있게 하였다. Flat memory model이 아닌 경우 사용할 수 없다.

 

page_ext_init_flatmem-1

page_ext_init_flatmem-2

 

page_ext_init_flatmem()

mm/page_ext.c

void __init page_ext_init_flatmem(void)
{

        int nid, fail;

        if (!invoke_need_callbacks())
                return;

        for_each_online_node(nid)  {
                fail = alloc_node_page_ext(nid);
                if (fail)
                        goto fail;
        }
        pr_info("allocated %ld bytes of page_ext\n", total_usage);
        invoke_init_callbacks();
        return;

fail:
        pr_crit("allocation of page_ext failed.\n");
        panic("Out of memory");
}

page_ext가 필요한 경우 각 노드에 page_ext를 할당 받고 초기화한다.

 

invoke_need_callbacks()

mm/page_ext.c

static bool __init invoke_need_callbacks(void)
{
        int i;
        int entries = ARRAY_SIZE(page_ext_ops);

        for (i = 0; i < entries; i++) {
                if (page_ext_ops[i]->need && page_ext_ops[i]->need())
                        return true;
        }

        return false;
}

page_ext_ops 엔트리 수 만큼 루프를 돌며 엔트리에 등록된 need 함수를 수행시켜 엔트리 하나라도 초기화가 필요한 경우 true를 반환한다.

 

alloc_node_page_ext()

mm/page_ext.c

static int __init alloc_node_page_ext(int nid)
{
        struct page_ext *base;
        unsigned long table_size;
        unsigned long nr_pages;

        nr_pages = NODE_DATA(nid)->node_spanned_pages;
        if (!nr_pages)
                return 0;

        /*
         * Need extra space if node range is not aligned with
         * MAX_ORDER_NR_PAGES. When page allocator's buddy algorithm
         * checks buddy's status, range could be out of exact node range.
         */
        if (!IS_ALIGNED(node_start_pfn(nid), MAX_ORDER_NR_PAGES) ||
                !IS_ALIGNED(node_end_pfn(nid), MAX_ORDER_NR_PAGES))
                nr_pages += MAX_ORDER_NR_PAGES;

        table_size = sizeof(struct page_ext) * nr_pages;

        base = memblock_virt_alloc_try_nid_nopanic(
                        table_size, PAGE_SIZE, __pa(MAX_DMA_ADDRESS),
                        BOOTMEM_ALLOC_ACCESSIBLE, nid);
        if (!base)
                return -ENOMEM;
        NODE_DATA(nid)->node_page_ext = base;
        total_usage += table_size;
        return 0;
}

지정된 노드에 MAX_ORDER_NR_PAGES 단위로 align된 존재하는 페이지 수 만큼의 page_ext 구조체 영역을 memblock에 할당한다.

  • nr_pages = NODE_DATA(nid)->node_spanned_pages;
    • 해당 노드에서 absent page(hole)를 제외한 페이지
      • Sparsemem에서는 hole을 제외한 노드에 대한 전체 페이지 수
      • Flatmem에서는 노드에 대한 전체 페이지 수
  • if (!IS_ALIGNED(node_start_pfn(nid), MAX_ORDER_NR_PAGES) ||
    !IS_ALIGNED(node_end_pfn(nid), MAX_ORDER_NR_PAGES))
    nr_pages += MAX_ORDER_NR_PAGES;

    • 해당 노드의 시작과 끝 페이지가 1K page 단위로 align 되어 있지 않은 경우 할당할 페이지 수에 1024 pages를 더한다.
  • table_size = sizeof(struct page_ext) * nr_pages;
    • 할당할 크기를 구한다.
  • base = memblock_virt_alloc_try_nid_nopanic(table_size, PAGE_SIZE, __pa(MAX_DMA_ADDRESS), BOOTMEM_ALLOC_ACCESSIBLE, nid)
    • memblock의 DMA 주소 ~ lowmem 범위에 해당 노드에 대한 page_ext 공간을 reserve 한다.
      • 가능하면 지정된 노드의 memblock에 할당을 시도하고 메모리 공간이 부족한 경우 전체 노드를 대상으로 검색하여 할당한다.
  • NODE_DATA(nid)->node_page_ext = base;
    • 노드이 멤버 node_page_ext에 할당된 주소를 지정한다.
  • total_usage += table_size;
    • 전역 사용량(바이트)에 할당 사이즈 만큼 추가한다.

 

invoke_init_callbacks()

mm/page_ext.c

static void __init invoke_init_callbacks(void)
{
        int i;
        int entries = ARRAY_SIZE(page_ext_ops);

        for (i = 0; i < entries; i++) {
                if (page_ext_ops[i]->init)
                        page_ext_ops[i]->init();
        }
}

page_ext_ops 엔트리 수 만큼 루프를 돌며 초기화 핸들러 함수를 호출한다.

 

초기화 핸들러

need_debug_guardpage()

mm/page_alloc.c

static bool need_debug_guardpage(void)
{
        /* If we don't use debug_pagealloc, we don't need guard page */
        if (!debug_pagealloc_enabled())
                return false; 

        return true;
}

가드 페이지 디버깅이 필요한지 여부를 반환한다.

 

debug_pagealloc_enabled()

include/linux/mm.h

static inline bool debug_pagealloc_enabled(void) 
{       
        return _debug_pagealloc_enabled;
}

페이지 할당 디버깅 기능 사용 여부를 반환한다.

 

mm/page_alloc.c

bool _debug_pagealloc_enabled __read_mostly;

 

init_debug_guardpage()

mm/page_alloc.c

static void init_debug_guardpage(void)
{                           
        if (!debug_pagealloc_enabled())
                return;

        _debug_guardpage_enabled = true; 
}

가드 페이지 디버깅 기능을 enable 한다.

 

need_page_poisoning()

mm/debug-pagealloc.c

static bool need_page_poisoning(void)
{       
        if (!debug_pagealloc_enabled())
                return false;

        return true;
}

페이지 poisoning이 필요한지 여부를 반환한다.

init_page_poisoning()

mm/debug-pagealloc.c

static void init_page_poisoning(void)
{
        if (!debug_pagealloc_enabled())
                return;

        page_poisoning_enabled = true;
}

페이지 poisoning 기능을 enable한다.

 

mm/debug-pagealloc.c

static bool page_poisoning_enabled __read_mostly;

 

need_page_owner()

mm/page_owner.c

static bool need_page_owner(void)
{
        if (page_owner_disabled)
                return false;

        return true;
}

page owner 추적 기능이 필요한지 여부를 반환한다.

 

mm/page_owner.c

static bool page_owner_disabled = true;

 

init_page_owner()

mm/page_owner.c

static void init_page_owner(void)
{
        if (page_owner_disabled)
                return;

        page_owner_inited = true;
        init_early_allocated_pages();
}

page owner 추적 기능이 사용되는 경우 할당 페이지를 초기화한다.

 

mm/page_owner.c

bool page_owner_inited __read_mostly;

 

init_early_allocated_pages()

mm/page_owner.c

static void init_early_allocated_pages(void)
{
        pg_data_t *pgdat;

        drain_all_pages(NULL);
        for_each_online_pgdat(pgdat)
                init_zones_in_node(pgdat);
}

Per-CPU Page Frame Cache를 buddy allocator로 다시 돌려보내고 노드안에 있는 zone을 초기화한다.

 

init_zones_in_node()

mm/page_owner.c

static void init_zones_in_node(pg_data_t *pgdat)
{
        struct zone *zone;
        struct zone *node_zones = pgdat->node_zones;
        unsigned long flags;
        
        for (zone = node_zones; zone - node_zones < MAX_NR_ZONES; ++zone) {
                if (!populated_zone(zone))
                        continue;

                spin_lock_irqsave(&zone->lock, flags);
                init_pages_in_zone(pgdat, zone);
                spin_unlock_irqrestore(&zone->lock, flags);
        }       
}

해당 노드에 대해 populate zone에 속한 페이지를 초기화한다.

 

init_pages_in_zone()

mm/page_owner.c

static void init_pages_in_zone(pg_data_t *pgdat, struct zone *zone)
{
        struct page *page;
        struct page_ext *page_ext;
        unsigned long pfn = zone->zone_start_pfn, block_end_pfn;
        unsigned long end_pfn = pfn + zone->spanned_pages;
        unsigned long count = 0;

        /* Scan block by block. First and last block may be incomplete */
        pfn = zone->zone_start_pfn;

        /*
         * Walk the zone in pageblock_nr_pages steps. If a page block spans
         * a zone boundary, it will be double counted between zones. This does
         * not matter as the mixed block count will still be correct
         */
        for (; pfn < end_pfn; ) {
                if (!pfn_valid(pfn)) {
                        pfn = ALIGN(pfn + 1, MAX_ORDER_NR_PAGES);
                        continue;
                }

                block_end_pfn = ALIGN(pfn + 1, pageblock_nr_pages);
                block_end_pfn = min(block_end_pfn, end_pfn);

                page = pfn_to_page(pfn);

                for (; pfn < block_end_pfn; pfn++) {
                        if (!pfn_valid_within(pfn))
                                continue;

                        page = pfn_to_page(pfn);

                        /*
                         * We are safe to check buddy flag and order, because
                         * this is init stage and only single thread runs.
                         */
                        if (PageBuddy(page)) {
                                pfn += (1UL << page_order(page)) - 1;
                                continue;
                        }

                        if (PageReserved(page))
                                continue;

                        page_ext = lookup_page_ext(page);

                        /* Maybe overraping zone */
                        if (test_bit(PAGE_EXT_OWNER, &page_ext->flags))
                                continue;

                        /* Found early allocated page */
                        set_page_owner(page, 0, 0);
                        count++;
                }
        }

        pr_info("Node %d, zone %8s: page owner found early allocated %lu pages\n",
                pgdat->node_id, zone->name, count);
}

zone에 구성된 페이지 중 onwer 설정이 필요한 경우 page_ext[]에서 해당 페이지를 찾아 owner 비트를 설정한다.

 

set_page_owner()

include/linux/page_owner.h

static inline void set_page_owner(struct page *page,
                        unsigned int order, gfp_t gfp_mask)
{
        if (likely(!page_owner_inited))
                return; 

        __set_page_owner(page, order, gfp_mask);
}

page_ext[]의 해당 페이지에 owner 비트를 설정한다.

 

__set_page_owner()

mm/page_owner.c

void __set_page_owner(struct page *page, unsigned int order, gfp_t gfp_mask)
{
        struct page_ext *page_ext = lookup_page_ext(page);
        struct stack_trace trace = {
                .nr_entries = 0,
                .max_entries = ARRAY_SIZE(page_ext->trace_entries),
                .entries = &page_ext->trace_entries[0],
                .skip = 3,
        };

        save_stack_trace(&trace);

        page_ext->order = order;
        page_ext->gfp_mask = gfp_mask;
        page_ext->nr_entries = trace.nr_entries;

        __set_bit(PAGE_EXT_OWNER, &page_ext->flags);
}

page_ext에 owner를 설정한다.

 

reset_page_owner()

include/linux/page_owner.h

static inline void reset_page_owner(struct page *page, unsigned int order)
{
        if (likely(!page_owner_inited))
                return;

        __reset_page_owner(page, order);
}

2^order 만큼의 페이지들에 대항하는 page_ext의 owner 비트를 clear한다.

 

__reset_page_owner()

mm/page_owner.c

void __reset_page_owner(struct page *page, unsigned int order)
{
        int i;
        struct page_ext *page_ext;

        for (i = 0; i < (1 << order); i++) {
                page_ext = lookup_page_ext(page + i);
                __clear_bit(PAGE_EXT_OWNER, &page_ext->flags);
        }
}

2^order 만큼의 페이지들에 대항하는 page_ext의 owner 비트를 clear한다.

 

page_is_guard()

include/linux/mm.h

#ifdef CONFIG_DEBUG_PAGEALLOC
static inline bool page_is_guard(struct page *page)
{       
        struct page_ext *page_ext;

        if (!debug_guardpage_enabled())
                return false;

        page_ext = lookup_page_ext(page); 
        return test_bit(PAGE_EXT_DEBUG_GUARD, &page_ext->flags);
}
#endif

페이지에 대항하는 page_ext의 guard 플래그 비트가 설정되었는지 여부를 반환한다.

 

clear_page_guard()

mm/page_alloc.c

static inline void clear_page_guard(struct zone *zone, struct page *page,
                                unsigned int order, int migratetype)
{
        struct page_ext *page_ext;

        if (!debug_guardpage_enabled())
                return;

        page_ext = lookup_page_ext(page);
        __clear_bit(PAGE_EXT_DEBUG_GUARD, &page_ext->flags);

        set_page_private(page, 0);
        if (!is_migrate_isolate(migratetype))
                __mod_zone_freepage_state(zone, (1 << order), migratetype);
}

페이지에 대항하는 page_ext의 guard 플래그 비트를 clear 하고 _private에 0을 대입한다. zone에 대한 free page stat도 2^order 만큼 증가시킨다.

 

lookup_page_ext()

mm/page_ext.c

struct page_ext *lookup_page_ext(struct page *page)
{
        unsigned long pfn = page_to_pfn(page);
        unsigned long offset;
        struct page_ext *base;

        base = NODE_DATA(page_to_nid(page))->node_page_ext;
#ifdef CONFIG_DEBUG_VM
        /*
         * The sanity checks the page allocator does upon freeing a
         * page can reach here before the page_ext arrays are
         * allocated when feeding a range of pages to the allocator
         * for the first time during bootup or memory hotplug.
         */
        if (unlikely(!base))
                return NULL;
#endif
        offset = pfn - round_down(node_start_pfn(page_to_nid(page)),
                                        MAX_ORDER_NR_PAGES);
        return base + offset;
}

page로 page_ext 정보츨 찾아 반환한다.

 

Early 커널 파라메터

early_debug_pagealloc()

mm/page_alloc.c

static int __init early_debug_pagealloc(char *buf)
{
        if (!buf)
                return -EINVAL;

        if (strcmp(buf, "on") == 0)
                _debug_pagealloc_enabled = true;
        
        return 0;
}       
early_param("debug_pagealloc", early_debug_pagealloc);

“debug_pagealloc=on” early 커널 파라메터를 사용하는 경우 페이지 할당 디버깅 기능을 사용한다.

 

early_page_owner_param()

mm/page_owner.c

static int early_page_owner_param(char *buf)
{
        if (!buf)
                return -EINVAL;

        if (strcmp(buf, "on") == 0)
                page_owner_disabled = false;

        return 0;
}               
early_param("page_owner", early_page_owner_param);

“page_owner=on” early 커널 파라메터를 사용하는 경우 페이지 owner 추적 기능을 사용한다.

 

구조체

page_ext_operations 구조체

include/linux/page_ext.h

struct page_ext_operations {
        bool (*need)(void);       
        void (*init)(void);
};
  • need
    • 필요 여부 조회 핸들러 함수 등록
  • init
    • 초기화 핸들러 함수 등록

 

page_ext_ops[] 전역 객체

mm/page_ext.c

/*
 * struct page extension
 *
 * This is the feature to manage memory for extended data per page.
 *
 * Until now, we must modify struct page itself to store extra data per page.
 * This requires rebuilding the kernel and it is really time consuming process.
 * And, sometimes, rebuild is impossible due to third party module dependency.
 * At last, enlarging struct page could cause un-wanted system behaviour change.
 *
 * This feature is intended to overcome above mentioned problems. This feature
 * allocates memory for extended data per page in certain place rather than
 * the struct page itself. This memory can be accessed by the accessor
 * functions provided by this code. During the boot process, it checks whether
 * allocation of huge chunk of memory is needed or not. If not, it avoids
 * allocating memory at all. With this advantage, we can include this feature
 * into the kernel in default and can avoid rebuild and solve related problems.
 *
 * To help these things to work well, there are two callbacks for clients. One
 * is the need callback which is mandatory if user wants to avoid useless
 * memory allocation at boot-time. The other is optional, init callback, which
 * is used to do proper initialization after memory is allocated.
 *
 * The need callback is used to decide whether extended memory allocation is
 * needed or not. Sometimes users want to deactivate some features in this
 * boot and extra memory would be unneccessary. In this case, to avoid
 * allocating huge chunk of memory, each clients represent their need of
 * extra memory through the need callback. If one of the need callbacks
 * returns true, it means that someone needs extra memory so that
 * page extension core should allocates memory for page extension. If
 * none of need callbacks return true, memory isn't needed at all in this boot
 * and page extension core can skip to allocate memory. As result,
 * none of memory is wasted.
 *
 * The init callback is used to do proper initialization after page extension
 * is completely initialized. In sparse memory system, extra memory is
 * allocated some time later than memmap is allocated. In other words, lifetime
 * of memory for page extension isn't same with memmap for struct page.
 * Therefore, clients can't store extra data until page extension is
 * initialized, even if pages are allocated and used freely. This could
 * cause inadequate state of extra data per page, so, to prevent it, client
 * can utilize this callback to initialize the state of it correctly.
 */
static struct page_ext_operations *page_ext_ops[] = {
        &debug_guardpage_ops,
#ifdef CONFIG_PAGE_POISONING
        &page_poisoning_ops,
#endif
#ifdef CONFIG_PAGE_OWNER
        &page_owner_ops,
#endif
};

커널 옵션에 따라 현재 최대 3개의 핸들러 객체들이 등록되어 있다.

 

debug_guardpage_ops 전역 객체

mm/page_alloc.c

#ifdef CONFIG_DEBUG_PAGEALLOC
struct page_ext_operations debug_guardpage_ops = {
        .need = need_debug_guardpage,
        .init = init_debug_guardpage,
};
#else
struct page_ext_operations debug_guardpage_ops = { NULL, };
#endif

가드 페이지 디버깅에 관련된 핸들러 함수들이 등록되어 있다.

 

page_poisoning_ops 전역 객체

mm/debug-pagealloc.c

struct page_ext_operations page_poisoning_ops = {
        .need = need_page_poisoning, 
        .init = init_page_poisoning,
};

페이지 poisoning 디버깅에 관련된 핸들러 함수들이 등록되어 있다.

  • 디버그용으로 CONFIG_PAGE_POISONING 커널 옵션이 동작하는 경우에만 사용된다.

 

page_owner_ops 전역 객체

mm/page_owner.c

struct page_ext_operations page_owner_ops = {
        .need = need_page_owner,
        .init = init_page_owner,
};

페이지 owner 트래킹에 관련된 핸들러 함수들이 등록되어 있다.

  • 디버그용으로 CONFIG_PAGE_OWNER 커널 옵션이 동작하는 경우에만 사용된다.

 

참고

Interrupts -6- (IPI cross-call)

 

IPI (Inter Processor Interrupts)

인터럽트의 특별한 케이스로 SMP 시스템에서 하나의 cpu에서 다른 cpu로 발생시킨다.

ARM 리눅스에서 처리하는 IPI 타입은 다음과 같다.

  • IPI_WAKEUP
    • 다른 cpu를 깨운다.
  • IPI_TIMER
    • broadcast 타이머
  • IPI_RESCHEDULE
    • 리스케쥴링 인터럽트
  • IPI_CALL_FUNC
    • function call 인터럽트
  • IPI_CALL_FUNC_SINGLE
    • single function call 인터럽트
  • IPI_CPU_STOP
    • cpu stop 인터럽트
  • IPI_IRQ_WORK
    • IRQ work 인터럽트
  • IPI_COMPLETION
    • 완료 인터럽트

 

 

smp_call_function_many()

/**
 * smp_call_function_many(): Run a function on a set of other CPUs.
 * @mask: The set of cpus to run on (only runs on online subset).
 * @func: The function to run. This must be fast and non-blocking.
 * @info: An arbitrary pointer to pass to the function.
 * @wait: If true, wait (atomically) until function has completed
 *        on other CPUs.
 *
 * If @wait is true, then returns once @func has returned.
 *
 * You must not call this function with disabled interrupts or from a
 * hardware interrupt handler or from a bottom half handler. Preemption
 * must be disabled when calling this function.
 */
void smp_call_function_many(const struct cpumask *mask,
                            smp_call_func_t func, void *info, bool wait)
{
        struct call_function_data *cfd;
        int cpu, next_cpu, this_cpu = smp_processor_id();

        /*
         * Can deadlock when called with interrupts disabled.
         * We allow cpu's that are not yet online though, as no one else can
         * send smp call function interrupt to this cpu and as such deadlocks
         * can't happen.
         */
        WARN_ON_ONCE(cpu_online(this_cpu) && irqs_disabled()
                     && !oops_in_progress && !early_boot_irqs_disabled);

        /* Try to fastpath.  So, what's a CPU they want? Ignoring this one. */
        cpu = cpumask_first_and(mask, cpu_online_mask);
        if (cpu == this_cpu)
                cpu = cpumask_next_and(cpu, mask, cpu_online_mask);

        /* No online cpus?  We're done. */
        if (cpu >= nr_cpu_ids)
                return;

        /* Do we have another CPU which isn't us? */
        next_cpu = cpumask_next_and(cpu, mask, cpu_online_mask);
        if (next_cpu == this_cpu)
                next_cpu = cpumask_next_and(next_cpu, mask, cpu_online_mask);

        /* Fastpath: do that cpu by itself. */
        if (next_cpu >= nr_cpu_ids) {
                smp_call_function_single(cpu, func, info, wait);
                return;
        }

        cfd = this_cpu_ptr(&cfd_data);

        cpumask_and(cfd->cpumask, mask, cpu_online_mask);
        cpumask_clear_cpu(this_cpu, cfd->cpumask);

        /* Some callers race with other cpus changing the passed mask */
        if (unlikely(!cpumask_weight(cfd->cpumask)))
                return;

        for_each_cpu(cpu, cfd->cpumask) {
                struct call_single_data *csd = per_cpu_ptr(cfd->csd, cpu);

                csd_lock(csd);
                csd->func = func;
                csd->info = info;
                llist_add(&csd->llist, &per_cpu(call_single_queue, cpu));
        }

        /* Send a message to all CPUs in the map */
        arch_send_call_function_ipi_mask(cfd->cpumask);

        if (wait) {
                for_each_cpu(cpu, cfd->cpumask) {
                        struct call_single_data *csd;

                        csd = per_cpu_ptr(cfd->csd, cpu);
                        csd_lock_wait(csd);
                }
        }
}
EXPORT_SYMBOL(smp_call_function_many);

현재 cpu를 제외한 다른 cpu 모두에서 함수가 실행되게 한다. wait 인수를 true로 지정하는 경우 각 cpu에서 함수가 실행이 완료될 때 까지 기다린다.

fastpath: 실행해야 할 다른 cpu가 1개만 있는 경우

  • cpu = cpumask_first_and(mask, cpu_online_mask);
    • 첫 cpu를 알아온다.
    • 인수로 받은 비트맵 mask와 cpu_online _mask에 대해 가장 처음의 1로 설정된 cpu를 알아온다.
  • if (cpu == this_cpu) cpu = cpumask_next_and(cpu, mask, cpu_online_mask);
    • 알아온 첫 cpu가 현재 동작중인 cpu인 경우 다음 cpu를 알아온다.
  • if (cpu >= nr_cpu_ids) return;
    • 없으면 함수를 빠져나간다.
  • next_cpu = cpumask_next_and(cpu, mask, cpu_online_mask);
    • 두 번째 cpu를 알아온다.
  • if (next_cpu == this_cpu) next_cpu = cpumask_next_and(next_cpu, mask, cpu_online_mask);
    • 두 번째 cpu가 현재 cpu인 경우 두 번째 cpu를 다시 다음 cpu로 지정한다.
  • if (next_cpu >= nr_cpu_ids) { smp_call_function_single(cpu, func, info, wait); return; }
    • 두 번째 cpu가 없는 경우 즉 다른 cpu를 고려할 필요가 없는 경우

slowpath: 실행해야 할 다른 cpu가 2개 이상인 경우

  • cfd = this_cpu_ptr(&cfd_data)
    • cfd_data라는 이름의 전역 per-cpu 객체
  • cpumask_and(cfd->cpumask, mask, cpu_online_mask);
    • cfd->cpumask <- mask 비트맵과 cpu_online_mask 비트맵을 and 한 결과를 담는다.
  • cpumask_clear_cpu(this_cpu, cfd->cpumask);
    • cfd->cpumask에서 현재 cpu 비트를 clear 한다.
  • if (unlikely(!cpumask_weight(cfd->cpumask))) return;
    • 1로 설정된 비트가 하나도 없는 경우 함수를 빠져나간다.
  • for_each_cpu(cpu, cfd->cpumask) {
    • cfd->cpumask 에서 1로 설정된 cpu들을 대상으로 루프를 돈다.
  • struct call_single_data *csd = per_cpu_ptr(cfd->csd, cpu);
    • 현재 cpu의 cfd->csd
  • csd_lock(csd);
    • csd->flags에 lock 비트가 설정되어 있는 동안 sleep하고 설정되어 있지 않으면 lock 비트를 설정한다.
  • csd->func = func; csd->info = info;
    • csd 정보를 update한다.
  • llist_add(&csd->llist, &per_cpu(call_single_queue, cpu));
    • 현재 cpu의 call_single_queue의 선두에 추가한다.
  • arch_send_call_function_ipi_mask(cfd->cpumask);
    • cpu들에 대해 IPI single function call interrupt를 발생시킨다.

인수 wait이 true인 경우 다른 cpu에서 func이 모두 실행되어 complete될 때까지 기다린다.

  • if (wait) {
    • 인수 wait  옵션이 true인 경우
  • for_each_cpu(cpu, cfd->cpumask) {
    • cfd->cpumask 에서 1로 설정된 cpu들을 대상으로 루프를 돈다.
  • csd_lock_wait(csd);
    • csd->flags에 lock 비트가 설정되어 있는 동안 sleep 한다.

 

kernel/smp.c

static DEFINE_PER_CPU_SHARED_ALIGNED(struct call_function_data, cfd_data);

 

다음 그림은 other cpu(요청 cpu 중 현재 cpu가 아닌 online된 cpu)가 fastpath와 slowpath로 나뉘어 처리되는 과정을 보여주며 큐에 들어간 구조체들은 해당 cpu에 소프트 인터럽트가 호출되어 처리되는 과정을 보여준다.

smp_call_function_many-1b

 

smp_call_function_single()

kernel/smp.c

/*
 * smp_call_function_single - Run a function on a specific CPU
 * @func: The function to run. This must be fast and non-blocking.
 * @info: An arbitrary pointer to pass to the function.
 * @wait: If true, wait until function has completed on other CPUs.
 *
 * Returns 0 on success, else a negative status code.
 */
int smp_call_function_single(int cpu, smp_call_func_t func, void *info,
                             int wait)
{
        int this_cpu;
        int err;

        /*
         * prevent preemption and reschedule on another processor,
         * as well as CPU removal
         */
        this_cpu = get_cpu();

        /*
         * Can deadlock when called with interrupts disabled.
         * We allow cpu's that are not yet online though, as no one else can
         * send smp call function interrupt to this cpu and as such deadlocks
         * can't happen.
         */
        WARN_ON_ONCE(cpu_online(this_cpu) && irqs_disabled()
                     && !oops_in_progress);

        err = generic_exec_single(cpu, NULL, func, info, wait);

        put_cpu();

        return err;
}
EXPORT_SYMBOL(smp_call_function_single);

요청한 cpu에서 함수를 수행시킨다. 인수 wait이 true인 경우 실행이 완료될 때까지 기다린다.

 

generic_exec_single()

kernel/smp.c

/*
 * Insert a previously allocated call_single_data element
 * for execution on the given CPU. data must already have
 * ->func, ->info, and ->flags set.
 */
static int generic_exec_single(int cpu, struct call_single_data *csd,
                               smp_call_func_t func, void *info, int wait)
{
        struct call_single_data csd_stack = { .flags = 0 };
        unsigned long flags;


        if (cpu == smp_processor_id()) {
                local_irq_save(flags);
                func(info);
                local_irq_restore(flags);
                return 0;
        }


        if ((unsigned)cpu >= nr_cpu_ids || !cpu_online(cpu))
                return -ENXIO;


        if (!csd) {
                csd = &csd_stack;
                if (!wait)
                        csd = this_cpu_ptr(&csd_data);
        }

        csd_lock(csd);

        csd->func = func;
        csd->info = info;

        if (wait)
                csd->flags |= CSD_FLAG_WAIT;

        /*
         * The list addition should be visible before sending the IPI
         * handler locks the list to pull the entry off it because of
         * normal cache coherency rules implied by spinlocks.
         *
         * If IPIs can go out of order to the cache coherency protocol
         * in an architecture, sufficient synchronisation should be added
         * to arch code to make it appear to obey cache coherency WRT
         * locking and barrier primitives. Generic code isn't really
         * equipped to do the right thing...
         */
        if (llist_add(&csd->llist, &per_cpu(call_single_queue, cpu)))
                arch_send_call_function_single_ipi(cpu);

        if (wait)
                csd_lock_wait(csd);

        return 0;
}

지정된 cpu에서 함수가 수행되게 한다. 인수 wait이 true인 경우 수행이 완료될 때 까지 기다린다.

  • if (cpu == smp_processor_id()) { local_irq_save(flags); func(info); local_irq_restore(flags); return 0; }
    • 요청 받은 cpu가 현재 cpu인 경우그냥 함수를 호출하여 수행한다.
  • csd_lock(csd);
    • csd->flags에 lock 비트가 설정되어 있는 동안 sleep하고 설정되어 있지 않으면 lock 비트를 설정한다.
  • csd->func = func; csd->info = info;
    • csd에 호출할 함수와 인수 정보를 대입한다.
  • if (wait) csd->flags |= CSD_FLAG_WAIT;
    • wait이 true인 경우 csd->flags에 wait 비트를 설정한다. (대기중 표시)
  • if (llist_add(&csd->llist, &per_cpu(call_single_queue, cpu))) arch_send_call_function_single_ipi(cpu);
    • csd를 call_single_queue에 추가한 후 IPI cross call 소프트 인터럽트를 호출한다.
  • if (wait) csd_lock_wait(csd);
    • csd->flags에서 lock이 풀릴 때까지 대기한다.
      • 다른 cpu가 해당 함수를 수행하고 완료된 후 lock 비트를 clear 시켜 종료를 알린다.

 

arch_send_call_function_single_ipi()

arch/arm/kernel/smp.c

void arch_send_call_function_single_ipi(int cpu)
{
        smp_cross_call(cpumask_of(cpu), IPI_CALL_FUNC_SINGLE);
}

지정된 cpu에 대해 IPI cross call 소프트 인터럽트를 호출한다.

  • 호출된 cpu는 call_single_queue에 추가된 함수를 수행한다.

 

smp_cross_call()

arch/arm/kernel/smp.c

static void smp_cross_call(const struct cpumask *target, unsigned int ipinr)
{
        trace_ipi_raise(target, ipi_types[ipinr]);
        __smp_cross_call(target, ipinr);
}

전역 __smp_cross_call에 등록된 핸들러 함수를 호출한다.

  • 지정된 cpu에 대해 IPI cross call 소프트 인터럽트를 호출한다.
    • 호출된 cpu는 call_single_queue에 추가된 함수를 수행한다.

 

rpi2에서 __smp_cross_call에 호출함수를 등록하는 곳

bcm2709_smp_init_cpus()

void __init bcm2709_smp_init_cpus(void)
{
        void secondary_startup(void);
        unsigned int i, ncores;

        ncores = 4; // xxx scu_get_core_count(NULL);
        printk("[%s] enter (%x->%x)\n", __FUNCTION__, (unsigned)virt_to_phys((void *)secondary_startup), (unsigned)__io_address(ST_BASE + 0x10));
        printk("[%s] ncores=%d\n", __FUNCTION__, ncores);

        for (i = 0; i < ncores; i++) {
                set_cpu_possible(i, true);
                /* enable IRQ (not FIQ) */
                writel(0x1, __io_address(ARM_LOCAL_MAILBOX_INT_CONTROL0 + 0x4 * i));
                //writel(0xf, __io_address(ARM_LOCAL_TIMER_INT_CONTROL0   + 0x4 * i));
        }
        set_smp_cross_call(bcm2835_send_doorbell);
}

 

set_smp_cross_call()

arch/arm/kernel/smp.c

/*
 * Provide a function to raise an IPI cross call on CPUs in callmap.
 */ 
void __init set_smp_cross_call(void (*fn)(const struct cpumask *, unsigned int))
{
        if (!__smp_cross_call)
                __smp_cross_call = fn;
}

 

bcm2835_send_doorbell()

arch/arm/mach-bcm2709/bcm2709.c

static void bcm2835_send_doorbell(const struct cpumask *mask, unsigned int irq)
{
        int cpu;
        /*
         * Ensure that stores to Normal memory are visible to the
         * other CPUs before issuing the IPI.
         */
        dsb();

        /* Convert our logical CPU mask into a physical one. */
        for_each_cpu(cpu, mask)
        {
                /* submit softirq */
                writel(1<<irq, __io_address(ARM_LOCAL_MAILBOX0_SET0 + 0x10 * MPIDR_AFFINITY_LEVEL(cpu_logical_map(cpu), 0)));
        }
}

요청 받은 cpu들에 대해 소프트 인터럽트를 호출한다.

 

구조체

call_function_data 구조체

kernel/smp.c

struct call_function_data {
        struct call_single_data __percpu *csd;
        cpumask_var_t           cpumask;
};

 

call_single_data 구조체

include/linux/smp.h

struct call_single_data {
        struct llist_node llist;
        smp_call_func_t func;
        void *info;
        u16 flags;
};
  • llist
    • csd 리스트
  • func
    • 수행할 함수
  • *info
    • 함수에 인수로 전달할 정보
  • flags
    • 아래 비트를 저장한다.

kernel/smp.c

enum {
        CSD_FLAG_LOCK           = 0x01,
        CSD_FLAG_WAIT           = 0x02,
};
  • SMP 시스템에서 call single data를 위한 cpu의 처리 상태

 

참고