Zonned Allocator -3- (Buddy 페이지 할당)

<kernel v5.0>

Zonned Allocator -3- (Buddy 페이지 할당)

Buddy Memory Allocator는 물리 메모리를 페이지 단위로 나눠 할당 관리하는 시스템으로 연속된(contiguous) 물리 페이지의 할당/해지를 지원한다. 또한 최대한 커다란 연속된 페이지를 확보하도록 단편화 관련 알고리즘들이 사용되고 있다.

  • 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 페이지와 movable 페이지가 동시에 사용될 수 있다.
    • CMA 페이지들이 할당되면 CMA Memory Allocator에서도 별도로 이를 관리한다.
  • 버디 시스템의 관리 기법이 계속 버전 업하면서 복잡도는 증가하고 있지만 최대한 버디 시스템의 효율(단편화 방지)이 높아지고 있다

 

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

  • 커널 v4.4-rc1부터 바뀐 내용은 다음과 같다.
    • MIGRATE_RECLAIMABLE 위치와 MIGRATE_MOVABLE의 위치가 바뀌었다.
    • MIGRATE_RESERVE가 없어지고 MIGRATE_HIGHATOMIC로 바뀌었다.

 

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

  • _mapcount
    • 버디 시스템의 free page로 페이지=-128(PAGE_BUDDY_MAPCOUNT_VALUE)
    • 할당되어 버디 시스템에서 빠져나간 페이지=-1
  • private
    • 버디 시스템에서 관리될 때 사용되는 order 값
    • 페이지가 할당되어 버디 시스템에서 빠져나갈 때에는 0으로 리셋된다.
  • index
    • 버디 시스템에서 구분되는 migratetype
  • count
    • 사용자 없이 free 된 페이지=0
    • 할당되고 사용되는 경우 증가

 

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

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

buddy-2

버디 페이지 할당

 

다음 그림은 rmqueue() 함수 이후 호출 과정을 보여준다.

 

rmqueue()

mm/page_alloc.c

/*
 * Allocate a page from the given zone. Use pcplists for order-0 allocations.
 */
static inline
struct page *rmqueue(struct zone *preferred_zone,
                        struct zone *zone, unsigned int order,
                        gfp_t gfp_flags, unsigned int alloc_flags,
                        int migratetype)
{
        unsigned long flags;
        struct page *page;

        if (likely(order == 0)) {
                page = rmqueue_pcplist(preferred_zone, zone, order,
                                gfp_flags, migratetype, alloc_flags);
                goto out;
        }

        /*
         * We most definitely don't want callers attempting to
         * allocate greater than order-1 page units with __GFP_NOFAIL.
         */
        WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));
        spin_lock_irqsave(&zone->lock, flags);

        do {
                page = NULL;
                if (alloc_flags & ALLOC_HARDER) {
                        page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);
                        if (page)
                                trace_mm_page_alloc_zone_locked(page, order, migratetype);
                }
                if (!page)
                        page = __rmqueue(zone, order, migratetype, alloc_flags);
        } while (page && check_new_pages(page, order));
        spin_unlock(&zone->lock);
        if (!page)
                goto failed;
        __mod_zone_freepage_state(zone, -(1 << order),
                                  get_pcppage_migratetype(page));

        __count_zid_vm_events(PGALLOC, page_zonenum(page), 1 << order);
        zone_statistics(preferred_zone, zone);
        local_irq_restore(flags);

out:
        /* Separate test+clear to avoid unnecessary atomics */
        if (test_bit(ZONE_BOOSTED_WATERMARK, &zone->flags)) {
                clear_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);
                wakeup_kswapd(zone, 0, 0, zone_idx(zone));
        }

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

failed:
        local_irq_restore(flags);
        return NULL;
}

요청 zone의 버디 시스템을 통해 @migratype의 @order 페이지를 할당한다. 성공 시 할당한 페이지 디스크립터를 반환하고, 실패하는 경우 null을 반환한다.

  • 코드 라인 10~14에서 높은 확률로 0-order 페이지 할당 요청 시 0 order only 버디 캐시로 동작하는 pcp(Per CPU Page Frame Cache)에서 할당을 받는다.
  • 코드 라인 23~32에서 0-order가 아닌 페이지를 요청한 경우 버디 시스템에서 할당을 수행한다. 만일 ALLOC_HARDER 플래그가 사용된 경우 highatomic 타입 리스트에서 먼저 할당을 시도한다.
    • ALLOC_HARDER 플래그는 gfp_mask에서 GFP_ATOMIC  플래그를 사용 시 그 안에 사용되는 __GFP_HIGH 플래그에 의해 설정된다.
      • #define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
    • check_new_pages() 함수에서는 디버그 사용 시 할당한 페이지의 무결성을 체크한다. (hwpoison 등)
  • 코드 라인 36~40에서 할당한 페이지 수만큼 free 페이지 카운터를 감소시키고, PGALLOC 카운터는 증가시킨다. 그리고 처음 요청한 존에서 할당했는지 여부에 대한 hit 및 miss 카운터등을 증/감시킨다.
  • 코드 라인 43~51에서 페이지 할당이 성공 또는 실패되어 빠져나가는 out: 레이블이다. 나가기 전에 존에 boost 워터마크를 조사하여 켜진 경우 플래그를 클리어하고 kswapd를 깨운다.

 

다음 그림은 rmqueue() 함수를 통해 pcp를 포함한 버디시스템에서 페이지 할당이 처리되는 모습을 보여준다.

 

__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 __always_inline struct page *
__rmqueue(struct zone *zone, unsigned int order, int migratetype,
                                                unsigned int alloc_flags)
{
        struct page *page;

retry:
        page = __rmqueue_smallest(zone, order, migratetype);
        if (unlikely(!page)) {
                if (migratetype == MIGRATE_MOVABLE)
                        page = __rmqueue_cma_fallback(zone, order);

                if (!page && __rmqueue_fallback(zone, order, migratetype,
                                                                alloc_flags))
                        goto retry;
        }

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

요청 zone의 버디 시스템을 통해 @migratype의 @order 페이지를 할당한다. 성공 시 할당한 페이지 디스크립터를 반환하고, 실패하는 경우 null을 반환한다.

  • 코드 라인 8에서 먼저 요청한 order부터 최대 order까지 즉, 작은 order 부터 검색하여 할당해본다.
  • 코드 라인9~11에서 페이지 할당이 실패한 경우 만일 movable 타입 요청인 경우 먼저 cma 공간에서 검색한다.
  • 코드 라인 13~15에서 여전히 페이지 할당이 실패한 경우 fallback 타입들을 검색하여 원하는 migrate 타입으로 이주시킨다. 이주가 성공적이면 다시 할당을 재시도한다.

 

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

 

__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 __always_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]);
                page = list_first_entry_or_null(&area->free_list[migratetype],
                                                        struct page, lru);
                if (!page)
                        continue;
                list_del(&page->lru);
                rmv_page_order(page);
                area->nr_free--;
                expand(zone, page, order, current_order, area, migratetype);
                set_pcppage_migratetype(page, migratetype);
                return page;
        }

        return NULL;
}

요청한 @migratetype으로 요청한 @order 부터 최상위 order 까지, 즉 작은 order부터 free_list를 검색하여 찾은 free 페이지를 반환한다.

  • 코드 라인 10~15에서 요청 @order 부터 최상위 order 까지@migratetype의 free_list를 순회하며 free 페이지를 찾는다.
  • 코드 라인 16에서 free_list에서 찾은 선두(hot) 페이지를 제거한다.
  • 코드 라인 17에서 할당할 페이지의 order 정보를 0으로 리셋하고 buddy 식별 플래그도 없앤다.
  • 코드 랑니 18에서 해당 order 슬롯의 nr_free를 감소시킨다.
  • 코드 라인 19에서 요청 order에 free 페이지가 없는 경우 큰 order를 가져와 확장한다.
    • guard 페이지를 사용하지 않는 한  큰 order 아래로 요청한 order까지 절반씩 분해하여 추가되는 과정을 알 수 있다.
    • 예) order=3, current_order=6인 경우
      • order=6을 잘라서 order 5, order 4, order 3에 하나씩 추가하고, 남은 order 3 페이지를 반환한다.
  • 코드 라인 20에서 migrate 타입을 기록한다.

 

큰 order 페이지 확장(분해)

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 order 보다 큰 @high order에서 페이지를 할당 받은 경우 확장(분해)하여 high-1 부터 low까지의 free 페이지를 등록한다.

  • 코드 라인 5에서 @high order 페이지 수를 미리 산출해둔다.
  • 코드 라인 7~10에서 @high order가 @low order 보다 큰 경우 area 및 high를 감소시키고 size를 반으로 감소시킨다.
  • 코드 라인 13~24에서 디버그용 guard 페이지를 사용하는 경우 max order의 절반 이하(0~5 order)들에 대해서는 skip 한다.
  • 코드 라인 25에서 area->free_list[migratetype]에 page[size]를 추가한다.
  • 코드 라인 26에서 area의 free 엔트리 수를 증가시킨다.
  • 코드 라인 27에서 추가한 페이지에 해당 order 값을 저장한다.

 

다음 그림은 order 8 페이지를 확장하여 할당 요청한 order 5 페이지를 이외에, 남는 페이지들을 order 7 ~ 5에 해당하는 free_list에 추가한다.

 


migrate type 부족 시 fallback

CMA 영역 사용

__rmqueue_cma_fallback()

mm/page_alloc.c

static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone,
                                        unsigned int order)
{
        return __rmqueue_smallest(zone, order, MIGRATE_CMA);
}

movable 타입 요청 시 해당 migrate 타입에서 검색이 실패하는 경우 cma 영역에서도 시도한다.

 

fallback migrate 타입 사용

__rmqueue_fallback()

mm/page_alloc.c

/*
 * Try finding a free buddy page on the fallback list and put it on the free
 * list of requested migratetype, possibly along with other pages from the same
 * block, depending on fragmentation avoidance heuristics. Returns true if
 * fallback was found so that __rmqueue_smallest() can grab it.
 *
 * The use of signed ints for order and current_order is a deliberate
 * deviation from the rest of this file, to make the for loop
 * condition simpler.
 */
static __always_inline bool
__rmqueue_fallback(struct zone *zone, int order, int start_migratetype,
                                                unsigned int alloc_flags)
{
        struct free_area *area;
        int current_order;
        int min_order = order;
        struct page *page;
        int fallback_mt;
        bool can_steal;

        /*
         * Do not steal pages from freelists belonging to other pageblocks
         * i.e. orders < pageblock_order. If there are no local zones free,
         * the zonelists will be reiterated without ALLOC_NOFRAGMENT.
         */
        if (alloc_flags & ALLOC_NOFRAGMENT)
                min_order = pageblock_order;

        /*
         * Find the largest available free page in the other list. This roughly
         * approximates finding the pageblock with the most free pages, which
         * would be too costly to do exactly.
         */
        for (current_order = MAX_ORDER - 1; current_order >= min_order;
                                --current_order) {
                area = &(zone->free_area[current_order]);
                fallback_mt = find_suitable_fallback(area, current_order,
                                start_migratetype, false, &can_steal);
                if (fallback_mt == -1)
                        continue;

                /*
                 * We cannot steal all free pages from the pageblock and the
                 * requested migratetype is movable. In that case it's better to
                 * steal and split the smallest available page instead of the
                 * largest available page, because even if the next movable
                 * allocation falls back into a different pageblock than this
                 * one, it won't cause permanent fragmentation.
                 */
                if (!can_steal && start_migratetype == MIGRATE_MOVABLE
                                        && current_order > order)
                        goto find_smallest;

                goto do_steal;
        }

        return false;

find_smallest:
        for (current_order = order; current_order < MAX_ORDER;
                                                        current_order++) {
                area = &(zone->free_area[current_order]);
                fallback_mt = find_suitable_fallback(area, current_order,
                                start_migratetype, false, &can_steal);
                if (fallback_mt != -1)
                        break;
        }

        /*
         * This should not happen - we already found a suitable fallback
         * when looking for the largest page.
         */
        VM_BUG_ON(current_order == MAX_ORDER);

do_steal:
        page = list_first_entry(&area->free_list[fallback_mt],
                                                        struct page, lru);

        steal_suitable_fallback(zone, page, alloc_flags, start_migratetype,
                                                                can_steal);

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

        return true;

}

요청한 migrate 타입에서 페이지 할당이 실패할 때 호출되는데, migrate 타입 fallback 순서에 의해 다음 migrate 타입을 뺏어온다.(steal). 다른 migrate 타입을 뺏어올 때에는 가장 큰 order 위주로 뺏어온다. 이렇게 큰 페이지를 뺏어와야 다음에 동일한 migrate 타입 요청 시 즉각 대응할 수 있다.

  • 코드 라인 17~18에서 ALLOC_NOFRAGMENT 요청이 있는 경우 페이지 블럭내에서 migrate 타입이 섞이지 않도록 min_order 값에 페이지 블럭 order를 대입한다.
  • 코드 라인 25~31에서 가장 큰 order 부터 min_order까지 버디 리스트를 역방향으로 순회하며 fallback migrate 타입 순으로 free 페이지가 있는지 여부를 알아온다.
  • 코드 라인 41~45에서 요청한 타입이 movable이고, 출력 결과인 can_steal이 false이면 find_smallest 레이블로 이동한다. 그렇지 않은 경우 do_steal 레이블로 이동한다.
  • 코드 라인 48에서 루프를 완료할 때까지 fallback migrate 타입에서도 페이지를 찾지 못한 경우 false를 반환한다.
  • 코드 라인 50~58에서 find_smallest: 레이블이다. 요청한 migrate 타입이 movable인 경우이므로 페이지 블럭내에서 migrate 타입이 섞이더라도 요청한 order 부터 가장 큰 오더까지, 즉 작은 order 순서부터 시작하여 fallback migrate 타입에 free 페이지가 있으면 루프를 탈출한다.
  • 코드 라인 66~76에서 do_steal: 레이블이다. 찾은 fallback migrate 타입의 free 페이지를 요청한 migrate 타입의 free_list로 뺏어온다. 그런 후 true를 반환한다.

 

아래 그림은 unmovable 타입으로 5-order page를 할당 받으려는데 unmovable 타입의 free_list에서 free 페이지를 확보하지 못한 경우 fallback migrate 타입순으로 free_list의 free 페이지를 검색하여 steal 하는 모습을 보여준다.

  • unmovable에 대한 첫 번째 fallback migrate 타입인 reclaimable migrate 타입의 free_list를 검색하고, 그 다음 두 번째 movable migrate 타입의 free_list를 검색한다.

 

적합한 fallback migrate 타입 찾기

find_suitable_fallback()

mm/page_alloc.c

/*
 * Check whether there is a suitable fallback freepage with requested order.
 * If only_stealable is true, this function returns fallback_mt only if
 * we can steal other freepages all together. This would help to reduce
 * fragmentation due to mixed migratetype pages in one pageblock.
 */
int find_suitable_fallback(struct free_area *area, unsigned int order,
                        int migratetype, bool only_stealable, bool *can_steal)
{
        int i;
        int fallback_mt;

        if (area->nr_free == 0)
                return -1;

        *can_steal = false;
        for (i = 0;; i++) {
                fallback_mt = fallbacks[migratetype][i];
                if (fallback_mt == MIGRATE_TYPES)
                        break;

                if (list_empty(&area->free_list[fallback_mt]))
                        continue;

                if (can_steal_fallback(order, migratetype))
                        *can_steal = true;

                if (!only_stealable)
                        return fallback_mt;

                if (*can_steal)
                        return fallback_mt;
        }

        return -1;
}

order 페이지가 fallback migrate 타입을 사용하는 free_list에 존재하고 이를 steal할 수 있는지 여부를 알아온다. compaction 루틴에서는 @only_stealable에 true를 사용하고, 이 때에는 반드시 steal 적합한 fallback migrate 타입만을 허용한다. 출력 인자 @can_steal에는 steal 적합 여부를 담아온다.

  • 코드 라인 7~8에서 해당 order에 어떠한 free 엔트리가 없는 경우 -1을 반환한다.
  • 코드 라인 11~17에서 요청한 migrate 타입의 fallback migrate 타입 순서대로 순회한다.
  • 코드 라인 19~26에서 steal 가능한 경우 출력 인자 *can_steal에 true를 대입하고 순회 중인 해당 migrate 타입을 반환한다. 만일 only_stealable이 false인 경우 *can_stean 여부와 관계 없이 더 이상 순회하지 않고 해당 migrate 타입을 반환한다.
  • 코드 라인 29에서 순회가 완료되도록 steal 가능한 migrate 타입이 없는 경우 -1을 반환한다.

 

다음 그림은 fallback 하여 사용할 migrate 타입을 알아오는 과정을 보여준다.

 

can_steal_fallback()

mm/page_alloc.c

/*
 * When we are falling back to another migratetype during allocation, try to
 * steal extra free pages from the same pageblocks to satisfy further
 * allocations, instead of polluting multiple pageblocks.
 *
 * If we are stealing a relatively large buddy page, it is likely there will
 * be more free pages in the pageblock, so try to steal them all. For
 * reclaimable and unmovable allocations, we steal regardless of page size,
 * as fragmentation caused by those allocations polluting movable pageblocks
 * is worse than movable allocations stealing from unmovable and reclaimable
 * pageblocks.
 */
static bool can_steal_fallback(unsigned int order, int start_mt)
{
        /*
         * Leaving this order check is intended, although there is
         * relaxed order check in next check. The reason is that
         * we can actually steal whole pageblock if this condition met,
         * but, below check doesn't guarantee it and that is just heuristic
         * so could be changed anytime.
         */
        if (order >= pageblock_order)
                return true;

        if (order >= pageblock_order / 2 ||
                start_mt == MIGRATE_RECLAIMABLE ||
                start_mt == MIGRATE_UNMOVABLE ||
                page_group_by_mobility_disabled)
                return true;

        return false;
}

reclaimable과 unmovable 타입을 요청한 경우 어떠한 fallback 타입이 선정되든 항상 true를 반환한다. 그러나 movable 타입으로 할당해야 하는 경우 order가 pageblock_order / 2 이상 값을 사용하는 경우에만 treu를 반환한다.

 

fallback migrate 타입에서 steal 하기

steal_suitable_fallback()

mm/page_alloc.c

/*
 * This function implements actual steal behaviour. If order is large enough,
 * we can steal whole pageblock. If not, we first move freepages in this
 * pageblock to our migratetype and determine how many already-allocated pages
 * are there in the pageblock with a compatible migratetype. If at least half
 * of pages are free or compatible, we can change migratetype of the pageblock
 * itself, so pages freed in the future will be put on the correct free list.
 */
static void steal_suitable_fallback(struct zone *zone, struct page *page,
                unsigned int alloc_flags, int start_type, bool whole_block)
{
        unsigned int current_order = page_order(page);
        struct free_area *area;
        int free_pages, movable_pages, alike_pages;
        int old_block_type;

        old_block_type = get_pageblock_migratetype(page);

        /*
         * This can happen due to races and we want to prevent broken
         * highatomic accounting.
         */
        if (is_migrate_highatomic(old_block_type))
                goto single_page;

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

        /*
         * Boost watermarks to increase reclaim pressure to reduce the
         * likelihood of future fallbacks. Wake kswapd now as the node
         * may be balanced overall and kswapd will not wake naturally.
         */
        boost_watermark(zone);
        if (alloc_flags & ALLOC_KSWAPD)
                set_bit(ZONE_BOOSTED_WATERMARK, &zone->flags);

        /* We are not allowed to try stealing from the whole block */
        if (!whole_block)
                goto single_page;

        free_pages = move_freepages_block(zone, page, start_type,
                                                &movable_pages);
        /*
         * Determine how many pages are compatible with our allocation.
         * For movable allocation, it's the number of movable pages which
         * we just obtained. For other types it's a bit more tricky.
         */
        if (start_type == MIGRATE_MOVABLE) {
                alike_pages = movable_pages;
        } else {
                /*
                 * If we are falling back a RECLAIMABLE or UNMOVABLE allocation
                 * to MOVABLE pageblock, consider all non-movable pages as
                 * compatible. If it's UNMOVABLE falling back to RECLAIMABLE or
                 * vice versa, be conservative since we can't distinguish the
                 * exact migratetype of non-movable pages.
                 */
                if (old_block_type == MIGRATE_MOVABLE)
                        alike_pages = pageblock_nr_pages
                                                - (free_pages + movable_pages);
                else
                        alike_pages = 0;
        }

        /* moving whole block can fail due to zone boundary conditions */
        if (!free_pages)
                goto single_page;

        /*
         * If a sufficient number of pages in the block are either free or of
         * comparable migratability as our allocation, claim the whole block.
         */
        if (free_pages + alike_pages >= (1 << (pageblock_order-1)) ||
                        page_group_by_mobility_disabled)
                set_pageblock_migratetype(page, start_type);

        return;

single_page:
        area = &zone->free_area[current_order];
        list_move(&page->lru, &area->free_list[start_type]);
}
  • 코드 라인 9에서 현재 페이지가 속한 페이지 블럭의 변경 되기 전 migrate 타입을 알아온다.
  • 코드 라인 15~16에서 highatomic 타입인 경우 single_page 레이블로 이동한다.
  • 코드 라인 19~22에서 페이지 블럭보다 큰 order 요청인 경우 페이지 블럭들내에서 migrate 타입이 섞이지 않는다. 따라서 single_page 레이블로 이동한다.
  • 코드 라인 29~31에서 페이지 블럭보다 작은 fallback order가 동작하면 watermark_boost_factor 비율(디폴트=15000, 150%)이 적용된 워터마크 boost를 지정하고, ALLOC_KSWAPD 요청이 있는 경우 존의 boost 워터마크 플래그를 설정한다.
  • 코드 라인 34~35에서 @whole_block 요청이 없으면 해당 페이지만을 처리하기 위해 single_page 레이블로 이동한다.
  • 코드 라인 37~38에서 해당 페이지가 포함된 페이지 블럭의 모든 free 페이지들이 있는 버디 시스템의 migrate 타입을 @start_type으로 이동시킨다.
  • 코드 라인 44~59에서 요청 migrate 타입별로 호환되는 migrate 타입 페이지들을 다음과 같이 산출하여 alike_pages에 대입한다.
    • movable 타입 요청
      • 페이지 블럭내에 사용 중인 모든 movable 페이지들
    • unmovable 타입 또는 unmovable 타입 요청
      • 기존 페이지 블럭이 movable 타입이었던 경우에만 페이지 블럭 내에 사용 중인 모든 movable 타입이 아닌 페이지 들
      • 기존 페이지 블럭이 movable 타입이 아닌 경우는 적용되지 않는다.
  • 코드 라인 62~63에서 free 페이지가 없는 경우 single_page 레이블로 이동한다.
  • 코드 라인 69~71에서 호환되는 페이지를 포함한 free 페이지가 페이지 블럭의 절반 이상인 경우 해당 페이지 블럭의 migrate 타입을 변경한다.
  • 코드 라인 75~77에서 single_page: 레이블이다. 해당 페이지만 free_list의 @start_type 으로 옮긴다.

 

다음 그림은 steal_suitable_fallback() 함수에서 페이지 블럭을 steal 할지, 아니면 해당 페이지만 steal 할지 여부를 판단하여 동작하는 모습을 보여준다.

 

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을 설정한다.

  • 코드 라인 4에서 start_order내에 들어갈 수 있는 pageblock의 수를 산출한다.
  • 코드 라인 6~9에서 페이지 블럭 수 만큼 순회하며 페이지 블럭의 migrate 타입을 설정한다.

 

페이지 블럭내 모든 free 페이지의 migrate 타입 이동

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);
}

지정된 zone의 요청 page가 있는 pageblock내의 모든 free page들을 요청 migrate 타입으로 변경하고 버디 시스템에서 요청 migrate 타입으로 이동하고 이동된 페이지 수를 반환한다. 단 존 경계를 이유로 페이지블럭의 끝 부분이 partial된 경우 move 시킬 수 없다.

  • 요청 zone의 시작 페이지가 pageblock 단위로 정렬되지 않은 경우에도 zone의 시작 주소부터 move 적용가능 (partial)
  • 요청 zone의 끝 페이지가 pageblock 단위로 정렬되지 않은 경우 그 pageblock은 사용할 수 없음

 

아래 그림은 지정된 zone의 페이지블럭에 있는 free page들의 migrate type을 요청한 타입으로 변경하는 모습을 보여준다.

move_freepages_block-1

 

zone_spans_pfn()

include/linux/mmzone.h

static inline bool zone_spans_pfn(const struct zone *zone, unsigned long pfn)
{
        return zone->zone_start_pfn <= pfn && pfn < zone_end_pfn(zone);
}

pfn이 zone의 영역에 들어있는지 여부를 반환한다.

 

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()
 */
static int move_freepages(struct zone *zone,
                          struct page *start_page, struct page *end_page,
                          int migratetype, int *num_movable)
{
        struct page *page;
        unsigned int 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(pfn_valid(page_to_pfn(start_page)) &&
                  pfn_valid(page_to_pfn(end_page)) &&
                  page_zone(start_page) != page_zone(end_page));
#endif
        for (page = start_page; page <= end_page;) {
                if (!pfn_valid_within(page_to_pfn(page))) {
                        page++;
                        continue;
                }

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

                if (!PageBuddy(page)) {
                        /*
                         * We assume that pages that could be isolated for
                         * migration are movable. But we don't actually try
                         * isolating, as that would be expensive.
                         */
                        if (num_movable &&
                                        (PageLRU(page) || __PageMovable(page)))
                                (*num_movable)++;

                        page++;
                        continue;
                }

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

        return pages_moved;
}

요청 zone의 시작 페이지부터 끝 페이지까지 모든 free page들에 대해 migrate 타입을 이동시키고, 이동시킨 페이지 수를 반환한다.

  • 코드 라인 21~25에서 시작 페이지부터 끝 페이지까지 순회하며 페이지가 hole 영역인 경우 skip 한다.
  • 코드 라인 30~42에서 버디 시스템에서 free되어 관리되는 페이지가 아니면 skip 한다.
    • 사용 중인 페이지가 lru movable에 포함된 경우 출력 인자 *num_movable을 증가시킨다.
  • 코드 라인44~48에서 현재 order에 해당하는 free_list의 지정한 migratetype으로 이동 시킨다.
  • 코드 라인 51에서 이동 시킨 페이지 수를 반환한다.

 

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

 

참고

 

Zoned Allocator -4- (Buddy 페이지 해지)

<kernel v5.0>

관련 커널 옵션들

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() 함수 이후의 호출 과정을 보여준다.

 

free_pages()

mm/page_alloc.c

void free_pages(unsigned long addr, unsigned int order)
{
        if (addr != 0) {
                VM_BUG_ON(!virt_addr_valid((void *)addr));
                __free_pages(virt_to_page((void *)addr), order);
        }
}

EXPORT_SYMBOL(free_pages);

버디 시스템으로 @addr 주소부터 @order 페이지를 할당 해제한다.

 

__free_pages()

mm/page_alloc.c

void __free_pages(struct page *page, unsigned int order)
{
        if (put_page_testzero(page))
                free_the_page(page, order);
}
EXPORT_SYMBOL(__free_pages);

참조 카운터가 감소시키며, 0이 되면 버디 시스템으로 @order 페이지를 할당 해제한다.

 

free_the_page()

mm/page_alloc.c

static inline void free_the_page(struct page *page, unsigned int order)
{
        if (order == 0)         /* Via pcp? */
                free_unref_page(page);
        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 타입의 경우 페이지를 버디 시스템으로 회수시킨다. 그리고 cma 및 highatomic 타입은 movable 타입의 pcp로 회수시킨다.
    • pcp 이주 시 overflow인 경우 batch 수 만큼 버디 시스템으로 회수시킨다.
  • order가 0이 아닌 multi page를 free할 때
    • pcp를 사용하지 않고 버디 시스템으로 회수시킨다.

 

__free_pages_ok()

mm/page_alloc.c

static void __free_pages_ok(struct page *page, unsigned int order)
{
        unsigned long flags;
        int migratetype;
        unsigned long pfn = page_to_pfn(page);

        if (!free_pages_prepare(page, order, true))
                return;

        migratetype = get_pfnblock_migratetype(page, pfn);
        local_irq_save(flags);
        __count_vm_events(PGFREE, 1 << order);
        free_one_page(page_zone(page), page, pfn, order, migratetype);
        local_irq_restore(flags);
}

사용이 완료된 order 페이지를 버디 시스템으로 회수한다.

  • 코드 라인 7~8에서 할당 해제할 페이지를 체크한다.
  • 코드 라인 12에서 PGFREE 카운터를 페이지 수 만큼 증가시킨다.
  • 코드 라인 13에서 order 페이지를 버디 시스템으로 회수한다.

 

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)
{
        spin_lock(&zone->lock);
        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);
}

사용이 완료된 order 페이지를 버디 시스템으로 회수한다.

  • 코드 라인 7~10에서 낮은 확률로 zone에 isolate 타입이 존재하거나 인수로 isolate 타입이 지정된 경우 페이지가 속한 페이지블럭의 migratetype을 사용한다.
  • 코드 라인 11에서 order 페이지를 버디 시스템의 migrate 타입으로 회수한다.

 

__free_one_page()

mm/page_alloc.c -1/2-

/*
 * 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 PageBuddy.
 * 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 combined_pfn;
        unsigned long uninitialized_var(buddy_pfn);
        struct page *buddy;
        unsigned int max_order;

        max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);

        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 (likely(!is_migrate_isolate(migratetype)))
                __mod_zone_freepage_state(zone, 1 << order, migratetype);

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

continue_merging:
        while (order < max_order - 1) {
                buddy_pfn = __find_buddy_pfn(pfn, order);
                buddy = page + (buddy_pfn - pfn);

                if (!pfn_valid_within(buddy_pfn))
                        goto done_merging;
                if (!page_is_buddy(page, buddy, order))
                        goto done_merging;
                /*
                 * 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_pfn = buddy_pfn & pfn;
                page = page + (combined_pfn - pfn);
                pfn = combined_pfn;
                order++;
        }
        if (max_order < MAX_ORDER) {
                /* If we are here, it means order is >= pageblock_order.
                 * We want to prevent merge between freepages on isolate
                 * pageblock and normal pageblock. Without this, pageblock
                 * isolation could cause incorrect freepage or CMA accounting.
                 *
                 * We don't want to hit this code for the more frequent
                 * low-order merging.
                 */
                if (unlikely(has_isolate_pageblock(zone))) {
                        int buddy_mt;

                        buddy_pfn = __find_buddy_pfn(pfn, order);
                        buddy = page + (buddy_pfn - pfn);
                        buddy_mt = get_pageblock_migratetype(buddy);

                        if (migratetype != buddy_mt
                                        && (is_migrate_isolate(migratetype) ||
                                                is_migrate_isolate(buddy_mt)))
                                goto done_merging;
                }
                max_order++;
                goto continue_merging;
        }

사용이 완료된 order 페이지를 버디 시스템의 migrate 타입으로 회수한다.

  • 코드 라인 11에서 최대 combine할 order 값으로 페이지 블럭 order와 max 오더중 작은 값을 사용한다. 루프에사용하므로 1추가된 값이다.
  • 코드 라인 17~18에서 버디 시스템에서 free 페이지 수를 관리할 때 isolate 타입은 free 페이지 수에 추가하지 않는다. 따라서 isolate 타입을 제외한 경우에만 free 페이지 수를 회수될 order 페이지 수만큼 감소시킨다.
  • 코드 라인 23~47에서 continue_merging: 레이블이다. max order 직전까지의 order를 증가시키며 페이지를 combine하기위해 가드 페이지가 아닌 버디 페이지를 찾은 경우 해당 order의 엔트리를 제거한다. 더 이상 combine할 버디 페이지가 없는 경우 루프를 벗어나 done_merging 레이블로 이동한다.
  • 코드 라인 48~71에서 페이지 블럭까지는 다른 migrate 타입을 combine하여도 상관이 없었다. 그러나 isolate 타입은 free 페이지 카운터에 추가되지 않기 때문에 isolation이 진행 중인 존에서는 페이지 블럭 이상의 order에 대해 combine될 buddy 페이지 역시 같은 migrate 타입을 사용하지 않는 경우 combine을 하지 못하게 하였다.

 

mm/page_alloc.c -2/2-

done_merging:
        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(buddy_pfn)) {
                struct page *higher_page, *higher_buddy;
                combined_pfn = buddy_pfn & pfn;
                higher_page = page + (combined_pfn - pfn);
                buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);
                higher_buddy = higher_page + (buddy_pfn - combined_pfn);
                if (pfn_valid_within(buddy_pfn) &&
                    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++;
}
  • 코드 라인 1~2에서 done_merging: 레이블이다. 더 이상 combine할 버디 페이지가 없는 경우에서 진입하였다. free 페이지에 order를 기록한다.
  • 코드 라인 12~24에서 2단 combine될 가능성이 있을 때 cold 방향에 추가한다. 회수할 order 페이지의 1 단계 위 order 페이지의 버디 페이지가 존재하는지 체크한다. 회수된 order 페이지의 짝이되는 버디 페이지가 추후 free될 때, 상위 order에서도 한 번 더 combine될 가능성이 커진다. 따라서 곧바로 할당되어 나가지 못하도록 최대한 더 보존하기 위해 tail(cold) 방향에 페이지를 추가한다.
  • 코드 라인 26~28에서 head(hot) 방향에 페이지를 추가하고, 해당 order의 엔트리 수를 1 증가시킨다.

 

다음 그림은 order 3 페이지 하나가 회수되었을 때 해당 페이지의 짝이되는 버디 페이지가 발견되면 상위 order로 병합(combine)되는 과정을 보여준다. 두 번의 병합(combine)을 통해 order 5에 등록되었다.

 

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

 

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된 페이지가 존재하는지 여부를 리턴한다.

 


회수한 order 페이지 체크

free_pages_prepare()

mm/page_alloc.c

static __always_inline bool free_pages_prepare(struct page *page,
                                        unsigned int order, bool check_free)
{
        int bad = 0;

        VM_BUG_ON_PAGE(PageTail(page), page);

        trace_mm_page_free(page, order);

        /*
         * Check tail pages before head page information is cleared to
         * avoid checking PageCompound for order-0 pages.
         */
        if (unlikely(order)) {
                bool compound = PageCompound(page);
                int i;

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

                if (compound)
                        ClearPageDoubleMap(page);
                for (i = 1; i < (1 << order); i++) {
                        if (compound)
                                bad += free_tail_pages_check(page, page + i);
                        if (unlikely(free_pages_check(page + i))) {
                                bad++;
                                continue;
                        }
                        (page + i)->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
                }
        }
        if (PageMappingFlags(page))
                page->mapping = NULL;
        if (memcg_kmem_enabled() && PageKmemcg(page))
                memcg_kmem_uncharge(page, order);
        if (check_free)
                bad += free_pages_check(page);
        if (bad)
                return false;

        page_cpupid_reset_last(page);
        page->flags &= ~PAGE_FLAGS_CHECK_AT_PREP;
        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_poison_pages(page, 1 << order, 0);
        kernel_map_pages(page, 1 << order, 0);
        kasan_free_nondeferred_pages(page, order);

        return true;
}

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

  • 코드 라인 14~21에서 compound 페이지인 경우 두번째 페이지의 PG_double_map을 클리어한다.
  • 코드 라인 22~30에서 두번째 페이지부터 order 페이지의 마지막까지 순회하며 bad 페이지 여부를 확인한다. 그리고 PAGE_FLAGS_CHECK_AT_PREP 플래그를 제거한다.
  • 코드 라인 32~33에서 페이지 매핑을 null로 초기화한다.
  • 코드 라인 34~35에서 kmemcg 페이지인 경우 order 페이지 만큼 uncharge한다.
  • 코드 라인 36~37에서 @check_free가 설정된 경우
  • 코드 라인 38~39에서 bad 페이지가 결과인 경우 false를 반환한다.
  • 코드 라인 41~43에서 페이지에서 cpupid 정보를 리셋하고,  PAGE_FLAGS_CHECK_AT_PREP 플래그도 제거하고, 페이지 owner를 리셋한다.
  • 코드 라인 45~50에서 highmem 페이지인 경우 디버그용 체크를 수행한다.
  • 코드 라인 51에서 아키텍처에서 free 페이지에 대한 검사를 지원하는 경우 수행한다.
  • 코드 라인 52에서 poison 디버그 기능을 사용하는 경우 free 페이지에 대해 poison 처리한다.
  • 코드 라인 53에서 pagealloc 디버그 기능을 사용하는 경우 메모리의 valid 여부를 확인한다.
  • 코드 라인 54에서 kasan 디버그 기능을 사용하는 경우의 처리이다.
  • 코드 라인 56에서 페이지에 이상이 없으므로 true를 반환한다.

 


버디 페이지 확인

__find_buddy_pfn()

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_pfn(unsigned long page_pfn, unsigned int order)
{
        return page_pfn ^ (1 << order);
}

요청한 order의 pfn과 짝을 이루는 버디 페이지의 pfn을 반환한다.

  • 예) pfn=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 coalesce a page and its buddy if
 * (a) the buddy is not in a hole (check before calling!) &&
 * (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 PageBuddy.
 * Setting, clearing, and testing PageBuddy 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 (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;
}

같은 존에 포함된 @page와 @buddy 페이지가 짝이면 1을 반환하고 그렇지 않으면 0을 반환한다.

  • 코드 라인 4~11에서 @buddy 페이지가 가드 페이지로 사용되고 있고, order도 동일한 경우 1을 반환한다. 단 @page와 @buddy 페이지가 같은 존에 위치하지 않은 경우 0을 반환한다.
  • 코드 라인 13~25에서 @buddy 페이지가 PG_buddy 플래그가 설정되어 있고, order도 동일한 경우 1을 반환한다. 단 @page와 @buddy 페이지가 같은 존에 위치하지 않은 경우 0을 반환한다.
  • 코드 라인 26에서 @page와 @buddy 페이지가 짝이 아니므로 0을 반환한다.

 


order 값 삭제

rmv_page_order()

mm/page_alloc.c

static inline void rmv_page_order(struct page *page)
{
        __ClearPageBuddy(page);
        set_page_private(page, 0);
}

페이지의 PG_buddy 플래그 클리어하고 order bit를 나타내는 페이지의 private에 0을 대입한다.

 

include/linux/mm.h

#define set_page_private(page, v)       ((page)->private = (v))

 

참고

 

 

mem_init()

<kernel v5.0>

free 메모리를 버디 시스템으로 이관

lowmem 및 highmem에 대한 모든 free 메모리에 대해 memblock 영역에서 버디 메모리 할당자로 이관한다.

 

mem_init() – ARM64

arch/arm64/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)
{
        if (swiotlb_force == SWIOTLB_FORCE ||
            max_pfn > (arm64_dma_phys_limit >> PAGE_SHIFT))
                swiotlb_init(1);
        else
                swiotlb_force = SWIOTLB_NO_FORCE;

        set_max_mapnr(pfn_to_page(max_pfn) - mem_map);

#ifndef CONFIG_SPARSEMEM_VMEMMAP
        free_unused_memmap();
#endif
        /* this will put all unused low memory onto the freelists */
        memblock_free_all();

        kexec_reserve_crashkres_pages();

        mem_init_print_info(NULL);

        /*
         * Check boundaries twice: Some fundamental inconsistencies can be
         * detected at build time already.
         */
#ifdef CONFIG_COMPAT
        BUILD_BUG_ON(TASK_SIZE_32 > DEFAULT_MAP_WINDOW_64);
#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;
        }
}

기존 memblock에서 reserve한 공간을 제외한 빈 공간들을 모두 버디 시스템에 등록하여 버디 시스템을 사용할 준비를 수행한다.

  • 코드 라인 3~7에서 “swiotlb=force” 커널 파라미터가 지정되거나 max_pfn이 dma 영역을 초과한 경우 sw 방식의 iotlb를 사용을 위해 I/O TLB용 버퍼 메모리를 할당한다.
    • arm64 디폴트 커널은 CONFIG_SWIOTLB를 사용한다.
    • “swiotlb=<force|noforce>” early 파라미터로 설정된다.
    • 예) ” software IO TLB [mem 0xef400000-0xf3400000] (64MB) mapped at [ffffffc0ef400000-ffffffc0f33fffff]”
  • 코드 라인 9에서 싱글 노드를 사용하는 시스템인 경우에만 전역 max_mapnr에 mem_map[] 배열에 대한 인덱스 번호를 저장한다.
  • 코드 라인 11~13에서 vmemmap을 사용하지 않는 경우 sparse 메모리 모델 또는 discontiguous 메모리 모델에서 메모리 사이의 사용되지 않는 공간이 상당히 클 수 있다. 따라서 이에 대해 메모리 낭비가 발생하지 않도록 미사용 공간에 대한 mem_map[ ]을 페이지 단위로 reserved memblock에서 free시킨다. x86과 ARM64 등에서는 CONFIG_SPARSEMEM_VMEMMAP의 사용이 가능하다.
  • 코드 라인 15에서 free memblock 영역에 대해 모두 버디 메모리 할당자의 빈 페이지로 이관 등록한다. memblock을 더 이상 사용하지 않는 경우 reserved & memory memblock 관리 배열까지 버디로 free시킨다.
    • ARM32의 경우는 추가 코드로 highmem 메모리 영역에 대해 버디 시스템으로 이관하는 free_highpage( ) 함수를 호출하는 코드가 있지만, ARM64에서는 highmem이 없으므로 해당 코드를 호출하지 않는다.
  • 코드 라인 19에서 메모리 초기화 정보를 출력한다.
    • 예) ” Memory: 2611360K/3145728K available (16060K kernel code, 8910K rwdata, 10300K rodata, 1664K init, 9117K bss, 501600K reserved, 32768K cma-reserved)”
  • 코드 라인 29~36에서 페이지 사이즈가 16K 이상이면서 물리 페이지가 128개 이하인 경우에 한해 메모리 할당 시 오버 커밋을 허용하게 한다.

 

다음 그림은 vmemmap을 사용하는 ARM64 시스템에서 mem_init() 함수를 통해 free 메모리를  memblock 할당자에서 버디 메모리 할당자로 전환하는 모습을 보여준다.

 

mem_init() – ARM32

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

#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);

기존 memblock에서 reserve한 공간을 제외한 빈 공간들을 모두 버디 시스템에 등록하여 버디 시스템을 사용할 준비를 수행한다.

  • 코드 라인 9에서 싱글 노드 시스템에서만 전역 max_mapnr에 mem_map[] 배열에 대한 인덱스 번호를 저장한다.
  • 코드 라인 12에서 Sparse 메모리 모델 또는 Discontig 메모리 모델에서 메모리 사이의 사용되지 않는 공간이 상당히 클 수 있다. 따라서 이에 대해 메모리 낭비가 발생하지 않도록 미사용 공간에 대한 mem_map[]을 페이지 단위로 reserve memblock에서 free 시킨다.
  • 코드 라인 13에서 free memblock 영역에 대해 모두 Buddy memory allocator의 빈 페이지로 이관 등록한다.
    • memblock을 더 이상 사용하지 않는 경우 reserved & memory memblock 관리배열까지 Buddy로 free 시킨다.
  • 코드 라인 20에서 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(VECTORS_BASE, 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

        /*
         * 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
}

가상 메모리 레이아웃 정보를 출력한다.

  • 예) 다음과 같은 출력 정보를 보여준다.
Virtual kernel memory layout:
    modules : 0xffffff8000000000 - 0xffffff8008000000   (   128 MB)
    vmalloc : 0xffffff8008000000 - 0xffffffbdbfff0000   (   246 GB)
      .init : 0xffffff8009040000 - 0xffffff8009160000   (  1152 KB)
      .text : 0xffffff8008080000 - 0xffffff8008bf0000   ( 11712 KB)
    .rodata : 0xffffff8008bf0000 - 0xffffff8009040000   (  4416 KB)
      .data : 0xffffff8009160000 - 0xffffff80092f6008   (  1625 KB)
    vmemmap : 0xffffffbdc0000000 - 0xffffffbfc0000000   (     8 GB maximum)
              0xffffffbdc0008000 - 0xffffffbdc3e00000   (    61 MB actual)
    fixed   : 0xffffffbffe7fd000 - 0xffffffbffec00000   (  4108 KB)
    PCI I/O : 0xffffffbffee00000 - 0xffffffbfffe00000   (    16 MB)
    memory  : 0xffffffc000200000 - 0xffffffc0f8000000   (  3966 MB)

 

다음 그림은 early 메모리 할당자인 memblock 에서 버디 메모리 할당자로 free 메모리 관리가 전환되는 모습을 보여준다.

 


미사용 memmap 할당 해제

free_unused_memmap() – ARM32

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이 없어 해당 사항 없다.

 

  • 코드 라인 10~11에서 memory memblock 엔트리 수 만큼 순회하며 시작 pfn 값을 알아온다.
    • PFN_UP(reg->base);
      • 물리 시작 주소에 PAGE_SIZE 단위로 round up한 후 pfn으로 변환
  • 코드 라인 18~19에서 Sparse memory model을 사용하는 경우 물리 시작 주소가 이전 기억해둔 memblock의 끝 주소를 섹션당 페이지 수(PAGES_PER_SECTION) 단위로 round up한 수를 초과하지 않게 한다.
  • 코드 라인 26에서 Sparse memory model이 아닌 경우 물리 시작 주소를 MAX_ORDER_NR_PAGES 단위로 round down 한다.
    • MAX_ORDER_NR_PAGES(1024)
  • 코드 라인 32~33에서 hole이 있는 경우 hole 만큼의 page를 관리하는 mem_map[]을 free 시킨다.
  • 코드 라인 40~41에서 memblock의 끝 주소를 round down하여 pfn으로 변환한 수를 MAX_ORDER_NR_PAGES 단위로 round up한 pfn 값
  • 코드 라인 45~47에서 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 메모리를 버디 시스템으로 이관

memblock_free_all()

mm/memblock.c

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

        reset_all_zones_managed_pages();

        pages = free_low_memory_core_early();
        totalram_pages_add(pages);

        return pages;
}

memblock을 스캔하여 free 메모리 영역을 찾아 버디 시스템에 이관하는 과정을 알아본다. 이 함수에서는 모든 free lowmem 영역을 버디 시스템의 free_list에 이관 등록한다. 핫플러그 메모리를 사용하지 않는 대부분의 시스템은 버디 시스템이 활성화되면 memblock을 더 이상 사용하지 않게 되는데, 이때 reserved & memory memblock의 관리 배열을 더 이상 사용하지 않으므로 이에 대한 영역도 버디 시스템에 이관한다.

  • 코드 라인 5에서 모든 온라인 노드의 각 zone->managed_pages를 0으로 초기화한다. managed_pages 필드는 존에서 사용 가능한 free 페이지 수를 나타낸다.
  • 코드 라인 7에서 모든 free lowmem 영역들을 버디 시스템의 free_list에 이관 등록한다. memblock을 더 이상 사용하지 않는 경우 reserved & memory memblock 관리 배열도 버디 시스템의 free_list에 이관 등록한다.
  • 코드 라인 8에서 free된 페이지들을 전역 totalram_pages에 추가한다.

 

reset_all_zones_managed_pages()

mm/memblock.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/memblock.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++)
                atomic_long_set(&z->managed_pages, 0);
}

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

 

커널 초기화 과정 이후 필요 없는 메모리 해제하기

free_low_memory_core_early()

mm/memblock.c

static unsigned long __init free_low_memory_core_early(void)
{
        unsigned long count = 0;
        phys_addr_t start, end;
        u64 i;

        memblock_clear_hotplug(0, -1);

        for_each_reserved_mem_region(i, &start, &end)
                reserve_bootmem_region(start, end);

        /*
         * We need to use NUMA_NO_NODE instead of NODE_DATA(0)->node_id
         *  because in some case like Node0 doesn't have RAM installed
         *  low ram will be on Node1
         */
        for_each_free_mem_range(i, NUMA_NO_NODE, MEMBLOCK_NONE, &start, &end,
                                NULL)
                count += __free_memory_core(start, end);

        return count;
}

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

  • 코드 라인 7에서 전체 memory memblock 영역에 대해 MEMBLOCK_HOTPLUG 비트를 클리어(clear)한다.
  • 코드 라인 9~10에서 전체 reserved memblock 영역의 모든 page 구조체에서 PG_reserved 비트를 설정하여 메모리가 이미 reserve되어 사용 중임을 마크한다.
  • 코드 라인 17~19에서 모든 free lowmem 영역을 버디 시스템의 free_list에 이관 등록한다.

 

reserve_bootmem_region()

mm/page_alloc.c

/*
 * Initialised pages do not have PageReserved set. This function is
 * called for each range allocated by the bootmem allocator and
 * marks the pages PageReserved. The remaining valid pages are later
 * sent to the buddy page allocator.
 */
void __meminit reserve_bootmem_region(phys_addr_t start, phys_addr_t end)
{
        unsigned long start_pfn = PFN_DOWN(start);
        unsigned long end_pfn = PFN_UP(end);

        for (; start_pfn < end_pfn; start_pfn++) {
                if (pfn_valid(start_pfn)) {
                        struct page *page = pfn_to_page(start_pfn);

                        init_reserved_page(start_pfn);

                        /* Avoid false-positive PageTail() */
                        INIT_LIST_HEAD(&page->lru);

                        /*
                         * no need for atomic set_bit because the struct
                         * page is not visible yet so nobody should
                         * access it yet.
                         */
                        __SetPageReserved(page);
                }
        }
}

요청 범위의 pfn 모두에 대해 page 구조체에서 PG_reserved 플래그를 설정한다. 추후 PG_reserved 플래그가 설정되지 않는 범위의 유효 페이지들에 대해서는 모두 버디 시스템으로 이관된다.

 

__free_memory_core()

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

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

  • 코드 라인 4~6에서 시작 물리 주소와 끝 물리 주소로 pfn 값을 구한다.
  • 코드 라인 11에서 페이지를 해제하여 버디 시스템으로 보낸다.
  • 코드 라인 해제한 페이지 수를 리턴한다.

 

__free_pages_memory()

mm/memblock.c

static void __init __free_pages_memory(unsigned long start, unsigned long end)
{
        int order;

        while (start < end) {
                order = min(MAX_ORDER - 1UL, __ffs(start));

                while (start + (1UL << order) > end)
                        order--;

                memblock_free_pages(pfn_to_page(start), start, order);

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

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

  • 코드 라인 5~6에서 start~end pfn까지 순회하며 start pfn 값으로 처음 order를 결정한다.
    • 2^n 단위로 잘라낸다.
    • __ffs()는 lsb -> msb 순으로 1로 설정된 비트를 찾는다. 못 찾은 경우에는 -1을 리턴한다. 예를 들어, start가 0x10003인 경우 order는 0이 된다.
  • 코드 라인 8~9에서 start pfn에 2^order를 더한 페이지 번호가 end를 초과한다면 order를 1씩 감소시킨다.
  • 코드 라인 2^order 페이지 공간을 버디에 free시키고 start += 2^order를 한 후 다시 루프를 수행한다.

 

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

__free_pages_memory-1

 


오더 페이지 해제하기

memblock_free_pages()

mm/page_alloc.c

void __init memblock_free_pages(struct page *page, unsigned long pfn,
                                                        unsigned int order)
{
        if (early_page_uninitialised(pfn))
                return;
        return __free_pages_boot_core(page, order);
}

요청한 2^order 페이지들을 해제한다.

  • 코드 라인 4~5에서 pfn에 해당하는 page 구조체가 초기화되지 않았다면 함수를 종료한다. page 구조체는 보통 부팅 초반에 싱글 스레드에 의해 초기화된다. 하지만 대용량 메모리를 가진 시스템에서는 이로 인해 부팅 속도 지연이 발생하게 된다. 따라서 이런 문제를 막기 위해  CONFIG_DEFERRED_STRUCT_PAGE_INIT 커널 설정을 사용하면 꼭 필요한 page 구조체만 초기화하고 나머지 page 구조체의 초기화는 뒤로 미룰 수가 있다.
  • 코드 라인 6에서 요청한 2^order 페이지를 버디 시스템으로 회수한다.

 

__free_pages_boot_core()

mm/page_alloc.c

void __init __free_pages_boot_core(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);

        atomic_long_add(nr_pages, &page_zone(page)->managed_pages);
        set_page_refcounted(page);
        __free_pages(page, order);
}

free시킬 페이지에 대해 PG_reserved 비트를 클리어하고 페이지가 참조되지 않음으로 설정(_count = 0)한다. managed_pages에 free시킬 페이지만큼 추가하고 첫 페이지를 참조 설정(_count = 1)한 후 버디 시스템으로 반환한다.

  • 코드 라인 7에서 요청한 시작 page 구조체를 캐시에 미리 로드한다.
  • 코드 라인 8~9에서 처리할 페이지들에 대해 마지막 페이지를 제외하고 루프를 돌며 다음 page 구조체를 캐시에 미리 로드한다. page 구조체 p를 조작하기 전에 pregetchw(p + 1)을 호출하여 다음 page 구조체마저 캐시 라인에 미리 로드하면 그전 page의 구조체 전체에 대해 어토믹 연산 작업 수행 시 한 번에 성공할 확률이 높아지므로 성능 향상에 도움이 된다.
    • page 구조체 p에 해당하는 데이터를 캐시에 로드하고 조작할 p->_count는 p 주소와 12바이트가 떨어져 있어서 p를 캐시에 미리 로드해도 같은 캐시 라인에 p->_count 영역이 로드되어 있지 않을 확률이 있다. 어차피 높은 확률로 다음 페이지 구조체 데이터도 필요하므로 미리 로드를 해놓으면 p->_count에 접근 시 어토믹 연산이 한 번에 성공할 확률이 더 높아져 성능에 도움이 될 수 있다.
    • ARM64에서 L1 데이터 캐시는 최소 16바이트부터 존재한다. 참고로 커널 v4.7부터는 _count 필드가 _refcount로 이름이 변경되었다.
  • 코드 라인 10~11에서 page 구조체의 플래그에 Reserved 비트를 클리어하고 참조 카운터를 0으로 만든다.
  • 코드 라인 13~14에서 마지막 페이지를 제외하고 루프를 돌았으므로 마지막 페이지에 대해 Reserved 비트를 클리어하고 참조 카운터를 0으로 만든다.
  • 코드 라인 16~18에서 존의 managed_pages에 버디 시스템으로 회수한 페이지 수를 더하고, 대표 페이지의 참조 카운터를 1로 설정하고, 페이지 회수 API를 호출한다.
    • 페이지의 참조 카운터를 0으로 하지 않고 1로 설정한 이유는 _ _free_pages( ) 함수를 분석해보면 금방 알 수 있다. _ _free_pages( ) 함수는 커널에서 페이지 회수 시에 사용하며, 많이 사용되는 API로 이 함수를 호출할 때 참조 카운터를 1 감소시키는 코드가 내부에 있는데 이 값이 0이 되는 순간에 실제 요청한 페이지들을 버디 시스템으로 회수하게 한다.

 

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

 


highmem 페이지들을 버디 시스템으로 이관

free_highpages-1

 

free_highpages() – ARM32

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 영역을 버디 시스템에 이관한다.

  • 코드 라인 8~10에서 memory memblock 수 만큼 순회하며 memblock 영역의 시작과 끝 pfn을 구한다.
    • 물리 시작 주소에 PAGE_SIZE 단위로 round up한 후 pfn으로 변환
    • 물리 끝 주소에 round down된 값을 pfn으로 변환
  • 코드 라인 13~14에서 memblock 엔트리가 lowmem인 경우는 skip 한다.
  • 코드 라인 16~17에서 노매핑 설정된 블럭은 skip 한다.
  • 코드 라인 20~21에서 memblock 엔트리가 lowmem/highmem 경계에 걸친 경우 lowmem 영역을 skip 한다.
  • 코드 라인 24~47에서 reserved 영역을 제외한 free 공간을 버디 시스템으로 이관한다.

 

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

<kernel v5.0>

page extension

memmap extension 또는 extended memap 이라고도 불린다. page 구조체를 변경하지 않고 page_ext라는 별도의 구조체를 만들어 page 확장을 하여 디버깅에 도움을 줄 수 있게 하였다. 이 기능은 2014년 12월 kernel v3.19-rc1에 LG 전자의 김준수님이 추가하였다.

 

다음과 같은 기능들이 준비되어 있다.

  • page alloc 디버깅
  • page poisoning 디버그
  • page owner 트래킹
  • idle page 트래킹

 

다음 그림은 sparse 메모리 모델이 아닌 경우 수행되는 page_ext_init_flatmem() 함수가 동작하여 확장 memmap을 생성하는 과정을 보여준다.

 

Flat & Discontiguous 메모리 모델에서의 page_ext 초기화

  • 참고로 sparse 메모리 모델에서의 초기화 루틴은 page_ext_init() 함수에서 한다.

 

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);
        bool need = false;

        for (i = 0; i < entries; i++) {
                if (page_ext_ops[i]->need && page_ext_ops[i]->need()) {
                        page_ext_ops[i]->offset = sizeof(struct page_ext) +
                                                extra_mem;
                        extra_mem += page_ext_ops[i]->size;
                        need = true;
                }
        }

        return need;
}

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

  • 코드 라인 7~8에서 컴파일 타임에 결정된 page_ext_ops[] 배열 엔트리 수 만큼 순회하며 해당 오퍼레이션에 등록된 (*need) 후크 함수에서 초기화가 필요한 경우 true를 반환하여 조건을 만족시킨다.
  • 코드 라인 9~10에서 해당 오퍼레이션의 offset에는 page_ext 구조체 + 해당 오퍼레이션이 사용할 extra 메모리에 대한 offset 바이트 수를 대입한다.
    • CONFIG_PAGE_OWNER 커널 옵션을 사용하는 경우 extra 메모리로 page_owner 구조체 사이즈를 사용한다.
  • 코드 라인 11에서 오퍼레이션에서 사용한 extra 메모리 사이즈 만큼 전역 변수 extra_mem에 더한다.

 

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 = get_entry_size() * 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 구조체 + extra 메모리 만큼을 memblock에 할당한다.

  • 코드 라인 7~9에서 해당 노드가 관리하는 홀을 포함한 전체 페이지 수를 가져온다.
  • 코드 라인 16~18에서 해당 노드의 시작과 끝 페이지가 최대 버디 오더 페이지 단위로 정렬되지 않은 경우 extra 공간을 더 정렬 단위만큼 추가한다.
    • MAX_ORDER_NR_PAGES는 버디 시스템에서 최대 할당 가능한 오더 페이지 수 이다.
  • 코드 라인 20~26에서 page_ext 용도로 메모리를 할당한다.
    • memblock의 DMA 주소 ~ lowmem 범위에 가능하면 노드 공간에 page_ext 공간을 할당한다.
    • 노드 주소 범위가 DMA 주소 ~ lowmem 범위에 포함되지 않는 경우에는 지정된 노드가 아니더라도 할당을 시도한다.
  • 코드 라인 27에서 할당된 메모리는 노드 멤버 node_page_ext에 지정한다.
  • 코드 라인 28에서 전역 사용량(바이트)에 할당 사이즈 만큼 추가한다.

 

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 엔트리 수 만큼 루프를 돌며 초기화 핸들러 함수를 호출한다.

 

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 정보츨 찾아 반환한다.

 

구조체

page_ext_operations 구조체

include/linux/page_ext.h

struct page_ext_operations {
        size_t offset;
        size_t size;
        bool (*need)(void);       
        void (*init)(void);
};
  • offset
    • page_ext 뒤에 추가된 extra 메모리를 가리키는 offset 이다.
  • size
    • 해당 오퍼레이션에서 사용하는 extra 메모리 바이트 수
    • CONFIG_PAGE_OWNER 커널 옵션을 사용하는 경우 page_owner 구조체 크기가 사용된다.
  •  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.
 *
 * When need callback returns true, page_ext checks if there is a request for
 * extra memory through size in struct page_ext_operations. If it is non-zero,
 * extra space is allocated for each page_ext entry and offset is returned to
 * user through offset in struct page_ext_operations.
 *
 * 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[] = {
#ifdef CONFIG_DEBUG_PAGEALLOC
        &debug_guardpage_ops,
#endif
#ifdef CONFIG_PAGE_OWNER
        &page_owner_ops,
#endif
#if defined(CONFIG_IDLE_PAGE_TRACKING) && !defined(CONFIG_64BIT)
        &page_idle_ops,
#endif
};

커널 옵션에 따라 몇 가지 기능의 핸들러 객체들이 등록되어 있다.

 

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,
};
#endif

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

 

page_owner_ops 전역 객체

mm/page_owner.c

struct page_ext_operations page_owner_ops = {
        .size = sizeof(struct page_owner),
        .need = need_page_owner,
        .init = init_page_owner,
};

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

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

 

page_idle_ops 전역 객체

mm/page_idle.c

#ifndef CONFIG_64BIT
struct page_ext_operations page_idle_ops = {
        .need = need_page_idle,
};
#endif

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

  • 이 오퍼레이션은 32비트 시스템에서만 사용되며, 64비트 시스템에서는 page_ext를 사용하는 이러한 오퍼레이션 없이 page 구조체만을 사용하여 동작한다.

 

참고

 

Interrupts -6- (IPI cross-call)

<kernel v5.4>

IPI (Inter Processor Interrupts)

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

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

1) ARM64

  •  IPI_RESCHEDULE
    • 리스케줄링 IPI
  • IPI_CALL_FUNC
    • call function IPI
  • IPI_CPU_STOP
    • cpu stop IPI
  • IPI_CPU_CRASH_STOP
    • cpu crash stop IPI
  • IPI_TIMER
    • broadcast 타이머 호출 IPI
  • IPI_IRQ_WORK
    • IRQ work IPI
  • IPI_WAKEUP
    • 다른 cpu를 깨우는 IPI

 

2) ARM32

SGI0~7에 해당하는 IPI들은 다음과 같다. SGI8-15는 secure 펌웨어 의해 예약되어 있다.

 


IPI 발생

IPI 함수 초기 설정

각 인터럽트 컨트롤러 초기화 함수에서 IPI 발생시킬 때 사용할 함수를 지정한다.

  • gic v3 드라이버
    • gic_smp_init() 함수에서 gic_raise_softirq() 함수를 지정
  • rpi2 IC 드라이버
    • bcm2709_smp_init_cpus() 함수에서 bcm2835_send_doorbell() 함수를 지정

 

set_smp_cross_call() – ARM64

arch/arm64/kernel/smp.c

void __init set_smp_cross_call(void (*fn)(const struct cpumask *, unsigned int))
{
        __smp_cross_call = fn;
}

IPI 발생시킬 때 사용할 함수를 지정한다.

 

set_smp_cross_call() – ARM32

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;
}

IPI 발생시킬 때 사용할 함수를 지정한다.

 

IPI 발생 API

smp_cross_call()

arch/arm64/kernel/smp.c & 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에 등록된 핸들러 함수를 호출하여 @ipinr에 해당하는 IPI를 비트 마스크로 표현된 @target cpu들에 발생시킨다.

 

IPI 발생 – GIC v3용

아래 함수 명에 사용된 softirq는 커널의 softirq subsystem을 뜻하는 것이 아니다. 외부 디바이스가 발생시키는 인터럽트가 아닌 cpu 내부에서 소프트웨어 명령으로 인해 발생되는 인터럽트라는 의미의 아키텍처 용어이다. ARM GIC에서는 이를 SGI(Software Generate Interrupt)로 표현한다.

 

다음 그림은 GIC v3 사용 시 최대 16개의 타겟 cpu들에 IPI(SGI)를 발생시키는 과정을 보여준다.

  • SGI는 0~15번까지 지정하여 인터럽트를 발생시킬 수 있다.

 

gic_raise_softirq()

drivers/irqchip/irq-gic-v3.c

static void gic_raise_softirq(const struct cpumask *mask, unsigned int irq)
{
        int cpu;

        if (WARN_ON(irq >= 16))
                return;

        /*
         * Ensure that stores to Normal memory are visible to the
         * other CPUs before issuing the IPI.
         */
        wmb();

        for_each_cpu(cpu, mask) {
                u64 cluster_id = MPIDR_TO_SGI_CLUSTER_ID(cpu_logical_map(cpu));
                u16 tlist;

                tlist = gic_compute_target_list(&cpu, mask, cluster_id);
                gic_send_sgi(cluster_id, tlist, irq);
        }

        /* Force the above writes to ICC_SGI1R_EL1 to be executed */
        isb();
}

요청 받은 cpu 비트 @mask에 대해  @irq 번호의 IPI를 발생시킨다.

  • 코드 라인 5~6에서 @irq 번호가 16 이상인 경우 처리를 중단하고 함수를 빠져나간다.
    • GIC의 경우 SGI#0 ~ SGI#15까지 발생 가능하다.
  • 코드 라인 12에서 IPI 발생 전에 다른 cpu들에서 저장한 노멀 메모리들의 저장을 확실하게 하는 메모리 베리어를 수행한다.
  • 코드 라인 14~20에서 cpu에 해당하는 mpidr 값에서 클러스터 id만 가져온다.

 

gic_compute_target_list()

drivers/irqchip/irq-gic-v3.c

static u16 gic_compute_target_list(int *base_cpu, const struct cpumask *mask,
                                   unsigned long cluster_id)
{
        int next_cpu, cpu = *base_cpu;
        unsigned long mpidr = cpu_logical_map(cpu);
        u16 tlist = 0;

        while (cpu < nr_cpu_ids) {
                tlist |= 1 << (mpidr & 0xf);

                next_cpu = cpumask_next(cpu, mask);
                if (next_cpu >= nr_cpu_ids)
                        goto out;
                cpu = next_cpu;

                mpidr = cpu_logical_map(cpu);

                if (cluster_id != MPIDR_TO_SGI_CLUSTER_ID(mpidr)) {
                        cpu--;
                        goto out;
                }
        }
out:
        *base_cpu = cpu;
        return tlist;
}

@cluster_id 들에 소속한 @mask에 포함된 cpu들에 대해 @base_cpu 부터 16비트의 비트마스크 값으로 반환한다.

  • 코드 라인 8~9에서 해당 cpu의 mpidr 값의 4비트가 cpu 번호이며 이 값을 반환하기 위해 사용할 tlist의 해당 cpu 비트를 설정한다.
  • 코드 라인 11~14에서 @mask에 설정된 다음 cpu를 알아온다.
  • 코드 라인 16~21에서 알아온 cpu의 클러스터 id가 @cluster_id와 다른 경우 cpu 번호를 그 전 성공한 번호로 감소시킨 후 함수를 빠져나가기 위해 out 레이블로 이동한다.
  • 코드 라인 23~25에서 인자 @base_cpu에 최종 타겟 cpu를 담고, 클러스터 @cluster_id에 포함되는 16비트 cpu 비트마스크를 반환한다.
    • 16비트 값을 반환하는 이유는 SGI가 최대 16개 cpu까지 지원하기 때문이다.

 

예) cluseter_id#0에 0~3번 cpu, cluster_id#1에 4~7번 cpu들이 배치되었을 때

  • base_cpu=2, mask=0x00ff, cluseter_id=0인 경우
    • 출력 인자 base_cpu=3이고, 반환 값=0x000c이다. (cpu2~3에 해당)

 

gic_send_sgi()

drivers/irqchip/irq-gic-v3.c

static void gic_send_sgi(u64 cluster_id, u16 tlist, unsigned int irq)
{
        u64 val;

        val = (MPIDR_TO_SGI_AFFINITY(cluster_id, 3)     |
               MPIDR_TO_SGI_AFFINITY(cluster_id, 2)     |
               irq << ICC_SGI1R_SGI_ID_SHIFT            |
               MPIDR_TO_SGI_AFFINITY(cluster_id, 1)     |
               MPIDR_TO_SGI_RS(cluster_id)              |
               tlist << ICC_SGI1R_TARGET_LIST_SHIFT);

        pr_devel("CPU%d: ICC_SGI1R_EL1 %llx\n", smp_processor_id(), val);
        gic_write_sgi1r(val);
}

@irq 번호에 해당하는 SGI(Software Generated Interrupt)를 @cluster_id의 @tlist cpu들에 발생시킨다.

  • ICC_SGI1R_EL1 레지스터에 @cluster_id로 aff3, aff2, aff1을 지정하고, 타겟 cpu 비트마스크인 @tlist를 대입한다.

 

IPI 발생 – rpi2 IC용

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들에 대해 IPI를 발생시킨다.

 


Call Function IPI

IPI(Inter Process Interrupts)를 수신 받아 처리하는 핸들러 함수는 handle_IPI()이다. 이 함수에서 사용하는 여러 IPI 항목 중 다음 2개의 항목은 다른 cpu의 요청에 의해 전달받은 call function data를 통해 이에 등록된 함수를 호출한다. 이러한 기능을 지원하기 위해 call_function_init() 함수를 통해 초기화한다.

  • IPI_CALL_FUNC
    • 요청한 함수들을 동작시킨다.
  • IPI_CALL_FUNC_SINGLE
    • 요청한 함수 하나를 동작시킨다.

 

Call Function 초기화

call_function_init()

kernel/smp.c

void __init call_function_init(void)
{
        int i;

        for_each_possible_cpu(i)
                init_llist_head(&per_cpu(call_single_queue, i));

        smpcfd_prepare_cpu(smp_processor_id());
}

call function에 사용되는 IPI 기능을 초기화한다.

  • 코드 라인 5~6에서 call function이 담기는 call_single_queue를 cpu 수 만큼초기화한다.
  • 코드 라인 8에서 현재 부트 cpu에 대한 call function data를 준비한다.

 

smpcfd_prepare_cpu()

kernel/smp.c

int smpcfd_prepare_cpu(unsigned int cpu)
{
        struct call_function_data *cfd = &per_cpu(cfd_data, cpu);

        if (!zalloc_cpumask_var_node(&cfd->cpumask, GFP_KERNEL,
                                     cpu_to_node(cpu)))
                return -ENOMEM;
        if (!zalloc_cpumask_var_node(&cfd->cpumask_ipi, GFP_KERNEL,
                                     cpu_to_node(cpu))) {
                free_cpumask_var(cfd->cpumask);
                return -ENOMEM;
        }
        cfd->csd = alloc_percpu(call_single_data_t);
        if (!cfd->csd) {
                free_cpumask_var(cfd->cpumask);
                free_cpumask_var(cfd->cpumask_ipi);
                return -ENOMEM;
        }

        return 0;
}

@cpu에 대한 call function data를 할당하고 초기화한다.

  • 코드 라인 5~7에서 cfd->cpumask를 할당한다.
  • 코드 라인 8~12에서 cfd->cpumask_ipi를 할당한다.
  • 코드 라인 13~18에서 per-cpu 멤버인 cfd->csd를 할당한다.
  • 코드 라인 20에서 성공 값 0을 반환한다.

 

function call IPI 발생 – many cpu

smp_call_function_many()

kernel/smp.c

/**
 * 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);

        /*
         * When @wait we can deadlock when we interrupt between llist_add() and
         * arch_send_call_function_ipi*(); when !@wait we can deadlock due to
         * csd_lock() on because the interrupt context uses the same csd
         * storage.
         */
        WARN_ON_ONCE(!in_task());
        /* 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;

        cpumask_clear(cfd->cpumask_ipi);
        for_each_cpu(cpu, cfd->cpumask) {
                call_single_data_t *csd = per_cpu_ptr(cfd->csd, cpu);

                csd_lock(csd);
                if (wait)
                        csd->flags |= CSD_FLAG_SYNCHRONOUS;
                csd->func = func;
                csd->info = info;
                if (llist_add(&csd->llist, &per_cpu(call_single_queue, cpu)))
                        __cpumask_set_cpu(cpu, cfd->cpumask_ipi);
        }

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

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

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

현재 cpu를 제외한 @mask cpu들에서 @func 함수가 실행되게 한다. @wait 인수를 설정하는 경우 각 cpu에서 함수의 실행이 완료될 때 까지 기다린다.

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

  • 코드 라인 24~30에서 전송할 대상 cpu들 @mask & online cpu들 중 첫 번째 cpu를 알아온다. 단 현재 cpu는 제외한다.
  • 코드 라인 33~35에서 다음 전송할 두 번째 cpu를 알아온다. 단 현재 cpu는 제외한다.
  • 코드 라인 38~41에서 전송 대상이 하나의 cpu인 경우 해당 cpu로 function call IPI를 발생시킨다.

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

  • 코드 라인 43~50에서 cfd_data라는 이름의 전역 per-cpu 객체의 cpumask에 현재 cpu를 제외한 타겟 cpu를 비트마스크 형태로 대입한다. 보낼 타겟 cpu가 하나도 없는 경우 함수를 빠져나간다.
  • 코드 라인 52~63에서 타겟 cpu들을 순회하며 per-cpu 타입인 call_single_data_t 타입 csd에 전송할 정보들을 저장한다.
    • csd_lock() 함수에서는 csd->flags에 lock 비트가 설정되어 있는 동안 sleep하고 설정되어 있지 않으면 lock 비트를 설정한다.
    • 현재 cpu의 call_single_queue의 선두에 추가한다.
  • 코드 라인 66에서 타겟 cpu들에 대해 function call IPI를 발생시킨다.
  • 코드 라인 68~75에서 인자 @wait이 지정된 경우 다른 cpu에서 func이 모두 실행되어 complete될 때까지 기다린다.

 

cfd_data

kernel/smp.c

static DEFINE_PER_CPU_ALIGNED(struct call_function_data, cfd_data);

 

다음 그림은 로컬 cpu를 제외한 타겟 cpu들에 대해 fastpath와 slowpath로 나뉘어 처리되는 과정을 보여준다.

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

        /*
         * When @wait we can deadlock when we interrupt between llist_add() and
         * arch_send_call_function_ipi*(); when !@wait we can deadlock due to
         * csd_lock() on because the interrupt context uses the same csd
         * storage.
         */
        WARN_ON_ONCE(!in_task());

        csd = &csd_stack;
        if (!wait) {
                csd = this_cpu_ptr(&csd_data);
                csd_lock(csd);
        }
        err = generic_exec_single(cpu, NULL, func, info, wait);

        if (wait)
                csd_lock_wait(csd);
        put_cpu();

        return err;
}
EXPORT_SYMBOL(smp_call_function_single);

지정한 @cpu에서 @func 함수를 동작시키도록 function call IPI를 발생시킨다. 인자 @wait이 설정된 경우 실행이 완료될 때까지 기다린다.

 

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)
{
        if (cpu == smp_processor_id()) {
                unsigned long flags;

                /*
                 * We can unlock early even for the synchronous on-stack case,
                 * since we're doing this from the same CPU..
                 */
                csd_unlock(csd);
                local_irq_save(flags);
                func(info);
                local_irq_restore(flags);
                return 0;
        }

        if ((unsigned)cpu >= nr_cpu_ids || !cpu_online(cpu)) {
                csd_unlock(csd);
                return -ENXIO;
        }

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

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

        /*
         * 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);

        return 0;
}

지정한 @cpu에서 @func 함수를 동작시키도록 function call IPI를 발생시킨다.

  • 코드 라인 4~16에서 요청 받은 cpu가 현재 cpu인 경우 IPI 발생 없이 그냥 함수를 호출하여 수행한다.
  • 코드 라인 18~21에서 허용 online cpu가 아니면 -ENXIO 에러를 반환한다.
  • 코드 라인 23~27에서 csd가 지정되지 않은 경우 전역 &csd_data를 사용한다.
  • 코드 라인 29~30에서 csd에 호출할 함수와 인수 정보를 대입한다.
  • 코드 라인 43~44에서 csd를 call_single_queue에 추가한 후 IPI를 발생시킨다.
  • 코드 라인 46에서 성공 값 0을 반환한다.

 

csd_data

kernel/smp.c

static DEFINE_PER_CPU_SHARED_ALIGNED(call_single_data_t, csd_data);

 

arch_send_call_function_single_ipi()

arch/arm64/kernel/smp.c & arch/arm/kernel/smp.c

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

지정된 @cpu에 대해 call function IPI를 발생시킨다.

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

 


IPI 핸들러

아키텍처 및 사용하는 인터럽트 컨트롤러마다 IPI 핸들러를 호출하는 곳이 다르다.

  • arm
    • do_IPI() -> handle_IPI()
  • arm GIC v3
    • gic_handle_irq() -> handle_IPI()

 

handle_IPI() – ARM64

arch/arm64/kernel/smp.c

/*
 * Main handler for inter-processor interrupts
 */
void handle_IPI(int ipinr, struct pt_regs *regs)
{
        unsigned int cpu = smp_processor_id();
        struct pt_regs *old_regs = set_irq_regs(regs);

        if ((unsigned)ipinr < NR_IPI) {
                trace_ipi_entry_rcuidle(ipi_types[ipinr]);
                __inc_irq_stat(cpu, ipi_irqs[ipinr]);
        }

        switch (ipinr) {
        case IPI_RESCHEDULE:
                scheduler_ipi();
                break;

        case IPI_CALL_FUNC:
                irq_enter();
                generic_smp_call_function_interrupt();
                irq_exit();
                break;

        case IPI_CPU_STOP:
                irq_enter();
                local_cpu_stop();
                irq_exit();
                break;

        case IPI_CPU_CRASH_STOP:
                if (IS_ENABLED(CONFIG_KEXEC_CORE)) {
                        irq_enter();
                        ipi_cpu_crash_stop(cpu, regs);

                        unreachable();
                }
                break;

#ifdef CONFIG_GENERIC_CLOCKEVENTS_BROADCAST
        case IPI_TIMER:
                irq_enter();
                tick_receive_broadcast();
                irq_exit();
                break;
#endif

#ifdef CONFIG_IRQ_WORK
        case IPI_IRQ_WORK:
                irq_enter();
                irq_work_run();
                irq_exit();
                break;
#endif

#ifdef CONFIG_ARM64_ACPI_PARKING_PROTOCOL
        case IPI_WAKEUP:
                WARN_ONCE(!acpi_parking_protocol_valid(cpu),
                          "CPU%u: Wake-up IPI outside the ACPI parking protocol\n",
                          cpu);
                break;
#endif

        default:
                pr_crit("CPU%u: Unknown IPI message 0x%x\n", cpu, ipinr);
                break;
        }

        if ((unsigned)ipinr < NR_IPI)
                trace_ipi_exit_rcuidle(ipi_types[ipinr]);
        set_irq_regs(old_regs);
}

@ipinr 번호에 해당하는 IPI를 발생시킨다.

  • 코드 라인 4에서 per-cpu 전역 변수인 __irq_regs에 @regs를 기록하고, 그 전 값은  이 루틴이 끝날때까지 old_regs 임시 변수에 저장한다.
  • 코드 라인 6~9에서 @ipinr가 NR_IPI 범위내에 있는 경우 IPI 시작에 대한 trace 출력을 하고 해당 @ipinr에 해당하는 ipi 카운터를 증가시킨다.
  • 코드 라인 11~14에서 IPI_RESCHEDULE 요청을 받은 경우 현재 프로세서에 대해 리스케쥴한다.
  • 코드 라인 16~20에서 IPI_CALL_FUNC 요청을 받은 경우 미리 등록된 call function 함수들을 호출한다.
  • 코드 라인 22~26에서 IPI_CPU_STOP 요청을 받은 경우 현재  cpu가 부팅 중 또는 동작 중인 경우 “CPU%u: stopping” 메시지 출력 및 스택 덤프를 하고 해당 cpu의 irq, fiq를 모두 정지 시키고 offline 상태로 바꾼 후 정지(spin)한다.
  • 코드 라인 28~35에서 IPI_CPU_CRASH_STOP 요청을 받은 경우 CONFIG_KEXEC_CORE 커널 옵션이 있는 경우에 한해 crash 처리를 한 후 cpu를 offline 상태로 바꾸고 정지(spin)시킨다.
  • 코드 라인 38~42에서 IPI_TIMER 요청을 받은 경우 tick 디바이스에 등록된 브로드 캐스트 이벤트 디바이스의 핸들러 함수를 호출한다.
  • 코드 라인 46~50에서 IPI_IRQ_WORK 요청을 받은 경우 현재의 모든 irq 작업들을 즉시 수행하게 한다.
  • 코드 라인 54~58에서 IPI_WAKEUP 요청을 받은 경우 아무것도 처리하지 않는다.
    • 이미 깨어나서 돌고 있고 아울러 트래킹을 위해 이미 해당 통계 카운터도 증가시켰다.
    • 호출 방법 1: arch_send_wakeup_ipi_mask(cpumask) 함수를 사용하여 cpumask에 해당하는 각 cpu들에 대해 WFI에 의해 잠들어 있는 경우 프로세서를 깨울 수 있다.
    • 호출 방법 2: 빅/리틀 hot plug cpu 시스템에서 gic_raise_softirq() 함수를 사용하여 WFI에 의해 대기하고 있는 cpu들을 깨운다. 이 때 인수로 1대신 0을 사용하여 호출하면 불필요한 printk 메시지(“CPU%u: Unknown IPI message 0x00000001”)를 출력하지 않고 트래킹을 위해 해당 카운터 수도 추적할 수 있다.
      • PM으로 전력 기능까지 콘트롤하는 GIC(Generic Interrupt Controller) #0을 사용하는 방법으로 지정한 cpu를 wakeup 시킨다.
    • 참고: ARM: 7536/1: smp: Formalize an IPI for wakeup
  • 코드 라인 61~64 정의 되지 않은 @ipinr 번호의 IPI를 요청했을 때 경고 메시지를 출력한다.
  • 코드 라인 66~67에서 @ ipinr이 범위내에 있는 경우 IPI 종료에 대한 trace 출력을 한다.
  • 코드 라인 68에서 백업해 두었던 old_regs를 per-cpu 전역 변수인 __irq_regs에 복원한다.

 

handle_IPI() – ARM32

arch/arm/kernel/smp.c

void handle_IPI(int ipinr, struct pt_regs *regs)
{
        unsigned int cpu = smp_processor_id();
        struct pt_regs *old_regs = set_irq_regs(regs);

        if ((unsigned)ipinr < NR_IPI) {
                trace_ipi_entry(ipi_types[ipinr]);
                __inc_irq_stat(cpu, ipi_irqs[ipinr]);
        }

        switch (ipinr) {
        case IPI_WAKEUP:
                break;

#ifdef CONFIG_GENERIC_CLOCKEVENTS_BROADCAST
        case IPI_TIMER:
                irq_enter();
                tick_receive_broadcast();
                irq_exit();
                break;
#endif

        case IPI_RESCHEDULE:
                scheduler_ipi();
                break;

        case IPI_CALL_FUNC:
                irq_enter();
                generic_smp_call_function_interrupt();
                irq_exit();
                break;

        case IPI_CPU_STOP:
                irq_enter();
                ipi_cpu_stop(cpu);
                irq_exit();
                break;

#ifdef CONFIG_IRQ_WORK
        case IPI_IRQ_WORK:
                irq_enter();
                irq_work_run();
                irq_exit();
                break;
#endif

        case IPI_COMPLETION:
                irq_enter();
                ipi_complete(cpu);
                irq_exit();
                break;

        case IPI_CPU_BACKTRACE:
                printk_nmi_enter();
                irq_enter();
                nmi_cpu_backtrace(regs);
                irq_exit();
                printk_nmi_exit();
                break;
        default:
                pr_crit("CPU%u: Unknown IPI message 0x%x\n",
                        cpu, ipinr);
                break;
        }

        if ((unsigned)ipinr < NR_IPI)
                trace_ipi_exit(ipi_types[ipinr]);
        set_irq_regs(old_regs);
}

@ipinr 번호에 해당하는 IPI를 발생시킨다.

  • 코드 라인 4에서 per-cpu 전역 변수인 __irq_regs에 @regs를 기록하고, 그 전 값은  이 루틴이 끝날때까지 old_regs 임시 변수에 저장한다.
  • 코드 라인 6~9에서 @ipinr가 NR_IPI 범위내에 있는 경우 IPI 시작에 대한 trace 출력을 하고 해당 @ipinr에 해당하는 ipi 카운터를 증가시킨다.
  • 코드 라인 11~13에서 IPI_WAKEUP 요청을 받은 경우 아무것도 처리하지 않는다.
    • 이미 깨어나서 돌고 있고 아울러 트래킹을 위해 이미 해당 통계 카운터도 증가시켰다.
    • 호출 방법 1: arch_send_wakeup_ipi_mask(cpumask) 함수를 사용하여 cpumask에 해당하는 각 cpu들에 대해 WFI에 의해 잠들어 있는 경우 프로세서를 깨울 수 있다.
    • 호출 방법 2: 빅/리틀 hot plug cpu 시스템에서 gic_raise_softirq() 함수를 사용하여 WFI에 의해 대기하고 있는 cpu들을 깨운다. 이 때 인수로 1대신 0을 사용하여 호출하면 불필요한 printk 메시지(“CPU%u: Unknown IPI message 0x00000001”)를 출력하지 않고 트래킹을 위해 해당 카운터 수도 추적할 수 있다.
      • PM으로 전력 기능까지 콘트롤하는 GIC(Generic Interrupt Controller) #0을 사용하는 방법으로 지정한 cpu를 wakeup 시킨다.
    • 참고: ARM: 7536/1: smp: Formalize an IPI for wakeup
  • 코드 라인 16~20에서 IPI_TIMER 요청을 받은 경우 tick 디바이스에 등록된 브로드 캐스트 이벤트 디바이스의 핸들러 함수를 호출한다.
  • 코드 라인 23~25에서 IPI_RESCHEDULE 요청을 받은 경우 현재 프로세서에 대해 리스케쥴한다.
  • 코드 라인 27~31에서 IPI_CALL_FUNC 요청을 받은 경우 미리 등록된 call function 함수들을 호출한다.
  • 코드 라인 33~37에서 IPI_CPU_STOP 요청을 받은 경우 현재  cpu가 부팅 중 또는 동작 중인 경우 “CPU%u: stopping” 메시지 출력 및 스택 덤프를 하고 해당 cpu의 irq, fiq를 모두 정지 시키고 offline 상태로 바꾼 후 정지(spin)한다.
  • 코드 라인 40~44에서 IPI_IRQ_WORK 요청을 받은 경우 현재의 모든 irq 작업들을 즉시 수행하게 한다.
  • 코드 라인 47~51에서 IPI_COMPLETION 요청을 받은 경우 register_ipi_completion() 함수로 등록해 놓은 per-cpu cpu_completion 에서 wait_for_completion()등으로 대기하고 있는 스레드를 깨운다.
  • 코드 라인 53~59에서 IPI_CPU_BACKTRACE 요청을 받은 경우 nmi backtrace를 지원하는 cpu들의 backtrace를 출력 한다.
  • 코드 라인 60~64 정의 되지 않은 @ipinr 번호의 IPI를 요청했을 때 경고 메시지를 출력한다.
  • 코드 라인 66~67에서 @ ipinr이 범위내에 있는 경우 IPI 종료에 대한 trace 출력을 한다.
  • 코드 라인 68에서 백업해 두었던 old_regs를 per-cpu 전역 변수인 __irq_regs에 복원한다.

 


IPI_TIMER 처리

tick_receive_broadcast()

kernel/time/tick-broadcast.c

#ifdef CONFIG_GENERIC_CLOCKEVENTS_BROADCAST
int tick_receive_broadcast(void)
{
        struct tick_device *td = this_cpu_ptr(&tick_cpu_device);
        struct clock_event_device *evt = td->evtdev;

        if (!evt)
                return -ENODEV;

        if (!evt->event_handler)
                return -EINVAL;

        evt->event_handler(evt);
        return 0;
}
#endif

tick 디바이스에 등록된 이벤트 디바이스의 핸들러 함수를 호출한다.

  • CONFIG_GENERIC_CLOCKEVENTS_BROADCAST 커널 옵션을 사용하는 경우에만 동작한다.
  • 호출 방법: tick_do_broadcast() 함수를 사용하여 해당 cpu들에 tick을 전달한다.
  • 참고: clockevents: Add generic timer broadcast receiver

 

  • 코드 라인 4~8에서 tick 디바이스에 등록된 clock 이벤트 디바이스를 알아온다. 없으면 -ENODEV 에러를 반환한다.
  • 코드 라인 10~11에서 clock 이벤트 디바이스에 이벤트 핸들러 함수가 등록되어 있지 않으면 -EINVAL 에러를 반환한다.
  • 코드 라인 13에서 등록된 이벤트 핸들러 함수를 호출한다.
  • 코드 라인 14에서 성공 값 0을 반환한다.

 


IPI_RESCHEDULE 처리

scheduler_ipi()

kernel/sched/core.c

void scheduler_ipi(void)
{
        /*            
         * Fold TIF_NEED_RESCHED into the preempt_count; anybody setting
         * TIF_NEED_RESCHED remotely (for the first time) will also send
         * this IPI.
         */
        preempt_fold_need_resched();

        if (llist_empty(&this_rq()->wake_list) && !got_nohz_idle_kick())
                return;

        /*
         * Not all reschedule IPI handlers call irq_enter/irq_exit, since
         * traditionally all their work was done from the interrupt return
         * path. Now that we actually do some work, we need to make sure
         * we do call them.
         *
         * Some archs already do call them, luckily irq_enter/exit nest
         * properly.
         *
         * Arguably we should visit all archs and update all handlers,
         * however a fair share of IPIs are still resched only so this would
         * somewhat pessimize the simple resched case.
         */
        irq_enter();
        sched_ttwu_pending();

        /*
         * Check if someone kicked us for doing the nohz idle load balance.
         */
        if (unlikely(got_nohz_idle_kick())) {
                this_rq()->idle_balance = 1;
                raise_softirq_irqoff(SCHED_SOFTIRQ);
        }
        irq_exit();
}

현재 프로세서에 대해 리스케쥴한다.

  • 호출 방법: smp_send_reschedule() 명령을 사용하여 해당 cpu에서 리스케쥴링하도록 요청한다.

 

  • 코드 라인 8에서 현재 스레드에 리스케쥴 요청이 있는 경우 preempt count에 있는 리스쥴 요청중 비트를 제거한다.
  • 코드 라인 10~11애서 런큐의 wake_list가 비어 있으면서 현재 cpu의 런큐에 NOHZ_BALANCE_KICK 요청이 없거나, 현재 cpu가 idle 상태가 아니거나 리스케쥴 요청이 있는 경우 리스케쥴할 태스크가 없어서 함수를 빠져나간다.
  • 코드 라인 26에서 hard irq preecmption 카운터를 증가시켜 preemption을 막고 irq 소요 시간 및 latency를 측정할 수 있도록 한다.
  • 코드 라인 27에서 런큐의 wake_list에서 모두 꺼내서 다시 enqueue 하여 리스케쥴 한다.
  • 코드 라인 32~35에서 낮은 확률로 현재 cpu의 런큐에 NOHZ_BALANCE_KICK 요청이 있고 현재 cpu가 idle 상태이면서 리스케쥴 요청이 없는 경우 런큐의 idle_balance 를 1로 설정하고 SCHED_SOFTIRQ 를 정지시킨다.
  • 코드 라인 36에서  hard irq preecmption 카운터를 감소시켜 preemption을 다시 열어주고  irq 소요 시간 및 latency를 측정할 수 있도록 후처리 작업을 수행한다.

 


IPI_CALL_FUNC 처리

generic_smp_call_function_interrupt()

include/linux/smp.h

#define generic_smp_call_function_interrupt \
        generic_smp_call_function_single_interrupt

IPI에 의해 인터럽트 된 후 미리 등록된 함수를 호출한다.

  • 호출 방법: arch_send_call_function_ipi_mask() 명령을 사용하여 해당 cpu들에서 미리 등록된 함수들을 호출한다.

 

generic_smp_call_function_single_interrupt()

kernel/smp.c

/**
 * generic_smp_call_function_single_interrupt - Execute SMP IPI callbacks
 *
 * Invoked by arch to handle an IPI for call function single.
 * Must be called with interrupts disabled.
 */
void generic_smp_call_function_single_interrupt(void)
{
        flush_smp_call_function_queue(true);
}

IPI에 의해 인터럽트 된 후 미리 등록된 함수를 호출한다.

  • 호출 방법: arch_send_call_function_single_ipi() 명령을 사용하여 요청 cpu에서 미리 등록된 함수를 호출한다.

 

flush_smp_call_function_queue()

kernel/smp.c

/**
 * flush_smp_call_function_queue - Flush pending smp-call-function callbacks
 *
 * @warn_cpu_offline: If set to 'true', warn if callbacks were queued on an
 *                    offline CPU. Skip this check if set to 'false'.
 *
 * Flush any pending smp-call-function callbacks queued on this CPU. This is
 * invoked by the generic IPI handler, as well as by a CPU about to go offline,
 * to ensure that all pending IPI callbacks are run before it goes completely
 * offline.
 *
 * Loop through the call_single_queue and run all the queued callbacks.
 * Must be called with interrupts disabled.
 */
static void flush_smp_call_function_queue(bool warn_cpu_offline)
{
        struct llist_head *head;
        struct llist_node *entry;
        call_single_data_t *csd, *csd_next;
        static bool warned;

        lockdep_assert_irqs_disabled();

        head = this_cpu_ptr(&call_single_queue);
        entry = llist_del_all(head);
        entry = llist_reverse_order(entry);

        /* There shouldn't be any pending callbacks on an offline CPU. */
        if (unlikely(warn_cpu_offline && !cpu_online(smp_processor_id()) &&
                     !warned && !llist_empty(head))) {
                warned = true; 
                WARN(1, "IPI on offline CPU %d\n", smp_processor_id());

                /*
                 * We don't have to use the _safe() variant here
                 * because we are not invoking the IPI handlers yet.
                 */
                llist_for_each_entry(csd, entry, llist)
                        pr_warn("IPI callback %pS sent to offline CPU\n",
                                csd->func);
        }

        llist_for_each_entry_safe(csd, csd_next, entry, llist) {
                csd->func(csd->info);
                csd_unlock(csd);
        }

        /*
         * Handle irq works queued remotely by irq_work_queue_on().
         * Smp functions above are typically synchronous so they
         * better run first since some other CPUs may be busy waiting
         * for them.
         */
        irq_work_run();
}

call_single_queue에 있는 모든 call function들을 한꺼번에 처리하고 비운다. 또한 남은 irq work도 모두 처리하여 비운다.

  • 코드 라인 10~12에서 per-cpu call_single_queue에 등록된 엔트리들을 모두 제거하고 entry로 가져오는데 가장 처음에 추가한 call_single_data 엔트리가 앞으로 가도록 순서를 거꾸로 바꾼다.
  • 코드 라인 15~27에서 인수 warn_cpu_offline가 설정된 경우 현재 cpu가 offline된 cpu인 경우 한 번만 “IPI on offline CPU %d” 및 “IPI callback %pS sent to offline CPU”라는 경고 메시지를 출력하게 한다.
  • 코드 라인 29~32에서 등록되어 있는 함수들을 모두 호출하여 수행한다.
  • 코드 라인 40에서 현재의 모든 irq 작업들을 즉시 수행하게 한다.

 


IPI_CPU_STOP 처리

local_cpu_stop() – ARM64

arch/arm64/kernel/smp.c

static void local_cpu_stop(void)
{
        set_cpu_online(smp_processor_id(), false);

        local_daif_mask();
        sdei_mask_local_cpu();
        cpu_park_loop();
}

로컬 cpu를 파킹(stop)한다.

  • 코드 라인 3에서 로컬 cpu를 offline 상태로 변경한다.
  • 코드 라인 5에서 로컬 cpu에 Exception들이 진입하지 않도록 모두 마스크한다.
  • 코드 라인 6에서 SDEI(Software Delegated Exception Interface)를 통해 로컬 cpu로의 인터럽트를 mask한다.
  • 코드 라인 7에서 cpu를 파킹한다.

 

ipi_cpu_stop() – ARM32

arch/arm/kernel/smp.c

/*
 * ipi_cpu_stop - handle IPI from smp_send_stop()
 */
static void ipi_cpu_stop(unsigned int cpu)
{
        if (system_state == SYSTEM_BOOTING ||
            system_state == SYSTEM_RUNNING) {
                raw_spin_lock(&stop_lock);
                pr_crit("CPU%u: stopping\n", cpu);
                dump_stack();
                raw_spin_unlock(&stop_lock);
        }

        set_cpu_online(cpu, false);

        local_fiq_disable();
        local_irq_disable();

        while (1)
                cpu_relax();
}

현재  cpu가 부팅 중 또는 동작 중인 경우 “CPU%u: stopping” 메시지 출력 및 스택 덤프를 하고 해당 cpu의 irq, fiq를 모두 정지 시키고 offline 상태로 바꾼 후 정지(spin)한다.

  • 호출 방법: smp_send_stop() 함수를 사용하여 현재 cpu를 제외한 online cpu를 stop 시킨다.

 


IPI_IRQ_WORKIRQ 처리

irq_work_run()

kernel/irq_work.c

/*
 * hotplug calls this through:
 *  hotplug_cfd() -> flush_smp_call_function_queue()
 */
void irq_work_run(void)
{
        irq_work_run_list(this_cpu_ptr(&raised_list));
        irq_work_run_list(this_cpu_ptr(&lazy_list));
}       
EXPORT_SYMBOL_GPL(irq_work_run);

현재의 모든 irq 작업들을 즉시 수행하게 한다.

  • CONFIG_IRQ_WORK 커널 옵션을 사용하는 경우에만 동작한다.
  • 호출 방법: arch_irq_work_raise() 요청을 받은 경우 현재 자신의 cpu에서 모든 irq 작업들을 즉시 수행하게 한다.
  • 참고: ARM: 7872/1: Support arch_irq_work_raise() via self IPIs

 

  • 코드 라인 3에서 &raised_list에 있는 모든 irq 작업들을 수행하게 한다.
  • 코드 라인 4에서 &lazy_list에 있는 모든 irq 작업들을 수행하게 한다.

 


IPI_COMPLETION 처리- ARM32

ipi_complete() – ARM32

arch/arm/kernel/smp.c

static void ipi_complete(unsigned int cpu)
{
        complete(per_cpu(cpu_completion, cpu));
}

register_ipi_completion() 함수로 등록해 놓은 per-cpu cpu_completion 에서 wait_for_completion()등으로 대기하고 있는 스레드를 깨운다.

 


IPI_CPU_BACKTRACE 처리 – ARM32

nmi_cpu_backtrace()

lib/nmi_backtrace.c

bool nmi_cpu_backtrace(struct pt_regs *regs)
{
        int cpu = smp_processor_id();

        if (cpumask_test_cpu(cpu, to_cpumask(backtrace_mask))) {
                if (regs && cpu_in_idle(instruction_pointer(regs))) {
                        pr_warn("NMI backtrace for cpu %d skipped: idling at %pS\n",
                                cpu, (void *)instruction_pointer(regs));
                } else {
                        pr_warn("NMI backtrace for cpu %d\n", cpu);
                        if (regs)
                                show_regs(regs);
                        else
                                dump_stack();
                }
                cpumask_clear_cpu(cpu, to_cpumask(backtrace_mask));
                return true;
        }

        return false;
}
NOKPROBE_SYMBOL(nmi_cpu_backtrace);

현재 cpu에 대한 레지스터 및 backtrace 로그를 출력한다.

 


구조체

call_function_data 구조체

kernel/smp.c

struct call_function_data {
        call_single_data_t      __percpu *csd;
        cpumask_var_t           cpumask;
        cpumask_var_t           cpumask_ipi;
};

call function IPI 호출 시 사용할 cfd로 function이 포함된 csd와 타겟 cpu들을 지정한 cpumask들이 담겨있다.

 

call_single_data_t 타입

include/linux/smp.h

/* Use __aligned() to avoid to use 2 cache lines for 1 csd */
typedef struct __call_single_data call_single_data_t
        __aligned(sizeof(struct __call_single_data));

 

include/linux/smp.h

struct __call_single_data {
        struct llist_node llist;
        smp_call_func_t func;
        void *info;
        unsigned int flags;
};

call function IPI 호출 시 사용할 csd로 function 정보가 담겨있다.

  •  llist
    • csd 리스트
  • func
    • 수행할 함수
  • *info
    • 함수에 인수로 전달할 정보
  • flags
    • 아래 플래그 비트를 저장한다.

 

kernel/smp.c

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

 

참고