Buddy Memory Allocator (해지)

관련 커널 옵션들

CONFIG_KMEMCHECK

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

 

CONFIG_MEMORY_ISOLATION

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

 

CONFIG_KASAN

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

 

페이지 해지(free)

 

__free_pages-1a

 

__free_one_page-1

 

__free_pages()

mm/page_alloc.c

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

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

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

 

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

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

free_pages-2a

 

put_page_testzero()

include/linux/mm.h

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

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

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

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

 

free_hot_cold_page()

mm/page_alloc.c

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

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

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

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

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

out:
        local_irq_restore(flags);
}

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

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

 

free_pcppages_bulk()

mm/page_alloc.c

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

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

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

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

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

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

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

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

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

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

 

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

free_pcppages_bulk-2b

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

 

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

free_pcppages_bulk-1a

 

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

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

 

get_freepage_migratetype()

include/linux/mm.h

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

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

 

has_isolate_pageblock()

include/linux/page-isolation.h

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

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

 

free_pages_prepare()

mm/page_alloc.c

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

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

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

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

        reset_page_owner(page, order);

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

        return true;
}

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

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

 

free_pages_check()

mm/page_alloc.c

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

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

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

 

bad_page()

mm/page_alloc.c

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

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

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

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

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

 

free_tail_pages_check()

mm/page_alloc.c

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

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

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

 

free_one_page()

mm/page_alloc.c

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

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

 

__free_one_page()

mm/page_alloc.c

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

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

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

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

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

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

 

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

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

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

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

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

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

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

 

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

 

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

__free_one_page-2b

 

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

__free_one_page-3

 

__find_buddy_index()

mm/internal.h

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

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

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

 

page_is_buddy()

mm/page_alloc.c

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

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

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

                return 1;
        }

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

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

                return 1;
        }
        return 0;
}

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

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

 

참고

답글 남기기

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