[Linux Kernel 5] Buddy System (fastpath & slowpath)

이번 포스트에서는 리눅스 커널의 메모리 할당 정책 중 버디 시스템에 대해 알아본다.

 

 

1. Basic Concept

 

이 전 NUMA와 Memory Zone 포스트에서 NUMA 노드마다 Zone들이 있고,

Zone에는 free_area 배열이 있는 것을 보았다.

Buddy System은 이 free_area를 이용하여 Zone 별로 구현한다.

Buddy System은 메모리를 페이지 단위의 2의 승수로 나눠서 메모리 할당과 반환을 수행한다.

free_area[0]은 전체 메모리를 4K(1 페이지)로 나눈 목록을 관리한다.

free_area[1]은 마찬가지로 8K(2 페이지)로 나눈 목록을 관리하며,

마지막 원소인 free_area[MAX_ORDER - 1]은 4K * 2^(MAX_ORDER - 1)의 사이즈(4M)의 목록을 관리한다.

(MAX_ORDER은 현재 11로 지정되어 있다.)

 

버디 시스템에서 메모리를 할당하는 경우 requested_size >> PAGE_SHIFT 이 후 비트 수를 계산하면 된다.

예를 들어 20000 바이트를 할당한다고 하면 20000 >> PAGE_SHIFT = 4이며,

4는 100₂로 비트 수가 3이다. 그러면 free_area[3]에서 메모리를 할당하면 된다.

4096 이하의 바이트의 경우 >> PAGE_SHIFT의 값이 0이기 때문에 free_area[0]에서 메모리를 할당하면 된다.

이 때, 할당하는 페이지 수는 order로 나타낸다. free_area[3]의 경우 order 3에 해당하는 페이지이다.

반대로 해제시에는 인접 영역이 사용하지 않는 공간인지 확인하여 병합을 시도한다.

병합의 결과 영역이 확장되면 그에 따라 free_area 목록을 갱신한다.

다음은 Buddy System 상에서 할당과 반환의 예시를 보여준다.

Buddy System Example

 

 

 

2. MIGRATE 속성

 

free_area의 정의는 다음과 같다.

struct free_area {
	struct list_head	free_list[MIGRATE_TYPES];
	unsigned long		nr_free;
};

즉, free_area는 각 원소마다 MIGRATE_TYPES에 따른 page 리스트를 가지고 있다.

MIGRATE_TYPES는 다음과 같다.

enum migratetype {
	MIGRATE_UNMOVABLE,
	MIGRATE_MOVABLE,
	MIGRATE_RECLAIMABLE,
	MIGRATE_PCPTYPES,	/* the number of types on the pcp lists */
	MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
	/*
	 * MIGRATE_CMA migration type is designed to mimic the way
	 * ZONE_MOVABLE works.  Only movable pages can be allocated
	 * from MIGRATE_CMA pageblocks and page allocator never
	 * implicitly change migration type of MIGRATE_CMA pageblock.
	 *
	 * The way to use it is to change migratetype of a range of
	 * pageblocks to MIGRATE_CMA which can be done by
	 * __free_pageblock_cma() function.  What is important though
	 * is that a range of pageblocks must be aligned to
	 * MAX_ORDER_NR_PAGES should biggest page be bigger then
	 * a single pageblock.
	 */
	MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	MIGRATE_ISOLATE,	/* can't allocate from here */
#endif
	MIGRATE_TYPES
};
 

즉, free_area[0].free_list[MIGRATE_UNMOVABLE]은 UNMOVABLE 타입의 페이지 하나짜리 리스트이며

free_area[1].free_list[MIGRATE_MOVABLE]은 MOVABLE 타입의 페이지 두개짜리 리스트이다.

이렇게 MIGRATE 타입별로 페이지를 관리하여 Memory Compation 작업의 효율을 높일 수 있다.

 

UNMOVABLE 타입은 이동과 반환이 불가능한 타입이다.

MOVABLE 타입은 이동 가능한 타입으로 단편화를 최소화하기 위해 사용한다.

RECLAIMABLE 타입은 이동은 불가능하지만 반환은 가능한 타입이다.

HIGHATOMIC(=PCPTYPES) 타입은 인터럽트 핸들러 등에서 GFP_ATOMIC 할당 시 사용한다.

CMA 타입은 contiguous area 메모리 할당 시 (DMA에서 cma_alloc) 사용한다.

ISOLATE 타입은 movable 페이지들을 migration 할 때 임시로 설정되는 타입이다. (해당 타입의 페이지는 절대 할당하지 않는다.)

 

 

 

 

3. 물리 페이지 할당

 

여태까지 봐온 내용을 토대로 물리 페이지 할당의 시퀀스를 간략화하면 다음과 같다.

우선 NUMA 메모리 정책을 통해 할당 대상이 되는 node를 정한다.

그리고 해당 node에서 알맞은 zone에 buddy system을 통해 할당을 수행한다.

사실 buddy system의 할당 과정은 memory cgroup의 통제 위에서 이루어지며,

캐시 시스템 또한 관여하게 되는데 이는 추후 포스트에서 알아보기로 한다.

 

저번 포스트에서 page 할당 시 페이지 할당 함수를 살펴봤다.

결국 마지막에는 __alloc_pages_nodemask 함수를 호출하였는데, 해당 함수의 정의는 다음과 같다.

/*
 * This is the 'heart' of the zoned buddy allocator.
 */
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, int preferred_nid,
							nodemask_t *nodemask)
{
	struct page *page;
	unsigned int alloc_flags = ALLOC_WMARK_LOW;
	gfp_t alloc_mask; /* The gfp_t that was actually used for allocation */
	struct alloc_context ac = { };
 
	/*
	 * There are several places where we assume that the order value is sane
	 * so bail out early if the request is out of bound.
	 */
	if (unlikely(order >= MAX_ORDER)) {
		WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));
		return NULL;
	}
 
	gfp_mask &= gfp_allowed_mask;
	alloc_mask = gfp_mask;
	if (!prepare_alloc_pages(gfp_mask, order, preferred_nid, nodemask, &ac, &alloc_mask, &alloc_flags))
		return NULL;
 
	finalise_ac(gfp_mask, &ac);
 
	/*
	 * Forbid the first pass from falling back to types that fragment
	 * memory until all local zones are considered.
	 */
	alloc_flags |= alloc_flags_nofragment(ac.preferred_zoneref->zone, gfp_mask);
 
	/* First allocation attempt */
	page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
	if (likely(page))
		goto out;
 
	/*
	 * Apply scoped allocation constraints. This is mainly about GFP_NOFS
	 * resp. GFP_NOIO which has to be inherited for all allocation requests
	 * from a particular context which has been marked by
	 * memalloc_no{fs,io}_{save,restore}.
	 */
	alloc_mask = current_gfp_context(gfp_mask);
	ac.spread_dirty_pages = false;
 
	/*
	 * Restore the original nodemask if it was potentially replaced with
	 * &cpuset_current_mems_allowed to optimize the fast-path attempt.
	 */
	if (unlikely(ac.nodemask != nodemask))
		ac.nodemask = nodemask;
 
	page = __alloc_pages_slowpath(alloc_mask, order, &ac);
 
out:
	if (memcg_kmem_enabled() && (gfp_mask & __GFP_ACCOUNT) && page &&
	    unlikely(__memcg_kmem_charge(page, gfp_mask, order) != 0)) {
		__free_pages(page, order);
		page = NULL;
	}
 
	trace_mm_page_alloc(page, order, alloc_mask, ac.migratetype);
 
	return page;
}

주석과 같이 해당 함수가 zoned buddy allocator의 핵심이다. 해당 함수를 대략 살펴보면 다음과 같다.

 

우선 인자로 전달받은 order이 MAX_ORDER 이상이면 NULL을 반환한다.

이는 buddy system에서 한번에 요청할 수 있는 연속된 메모리의 최대 크기가 4M라는 것이다.

즉, 그 이상 크기의 메모리 할당 시에는 저번 포스트의 vmalloc에서 본 것처럼 분리된 물리 메모리를 연속된 가상메모리로 매핑하여 사용한다.

 

prepare_alloc_pages는 alloc_context에 zone index, zonelist, nodemask, migratetype을 설정하고 cgroup 처리를 하는 등 페이지 할당을 준비한다.

finalise_ac는 prepare_alloc_pages에 이어서 alloc_context에 dirty pages(dirty zone 밸런싱에 사용)와 preferred_zoneref를 설정하며 할당 준비를 마무리한다.

 

get_page_from_freelist에서는 Fast-path 페이지 할당을 시도한다.

Fast-path 할당이 실패한 경우 dirty zone 밸런싱을 하지 않도록 설정하고 Slow-path 할당을 시도한다.

 

OUT 레이블에서는 memory cgroup의 limit을 벗어난 경우 페이지를 해제하고 할당에 실패하도록 한다.

 

 

 

4. Fast-path 페이지 할당

 

__alloc_pages_nodemask에서 fast-path 할당을 위해 호출한 함수 get_page_from_freelist의 정의는 다음과 같다.

/*
 * get_page_from_freelist goes through the zonelist trying to allocate
 * a page.
 */
static struct page *
get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags,
						const struct alloc_context *ac)
{
	struct zoneref *z;
	struct zone *zone;
	struct pglist_data *last_pgdat_dirty_limit = NULL;
	bool no_fallback;
 
retry:
	/*
	 * Scan zonelist, looking for a zone with enough free.
	 * See also __cpuset_node_allowed() comment in kernel/cpuset.c.
	 */
	no_fallback = alloc_flags & ALLOC_NOFRAGMENT;
	z = ac->preferred_zoneref;
	for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,
								ac->nodemask) {
		struct page *page;
		unsigned long mark;
 
		if (cpusets_enabled() &&
			(alloc_flags & ALLOC_CPUSET) &&
			!__cpuset_zone_allowed(zone, gfp_mask))
				continue;
		/*
		 * When allocating a page cache page for writing, we
		 * want to get it from a node that is within its dirty
		 * limit, such that no single node holds more than its
		 * proportional share of globally allowed dirty pages.
		 * The dirty limits take into account the node's
		 * lowmem reserves and high watermark so that kswapd
		 * should be able to balance it without having to
		 * write pages from its LRU list.
		 *
		 * XXX: For now, allow allocations to potentially
		 * exceed the per-node dirty limit in the slowpath
		 * (spread_dirty_pages unset) before going into reclaim,
		 * which is important when on a NUMA setup the allowed
		 * nodes are together not big enough to reach the
		 * global limit.  The proper fix for these situations
		 * will require awareness of nodes in the
		 * dirty-throttling and the flusher threads.
		 */
		if (ac->spread_dirty_pages) {
			if (last_pgdat_dirty_limit == zone->zone_pgdat)
				continue;
 
			if (!node_dirty_ok(zone->zone_pgdat)) {
				last_pgdat_dirty_limit = zone->zone_pgdat;
				continue;
			}
		}
 
		if (no_fallback && nr_online_nodes > 1 &&
		    zone != ac->preferred_zoneref->zone) {
			int local_nid;
 
			/*
			 * If moving to a remote node, retry but allow
			 * fragmenting fallbacks. Locality is more important
			 * than fragmentation avoidance.
			 */
			local_nid = zone_to_nid(ac->preferred_zoneref->zone);
			if (zone_to_nid(zone) != local_nid) {
				alloc_flags &= ~ALLOC_NOFRAGMENT;
				goto retry;
			}
		}
 
		mark = wmark_pages(zone, alloc_flags & ALLOC_WMARK_MASK);
		if (!zone_watermark_fast(zone, order, mark,
				       ac_classzone_idx(ac), alloc_flags)) {
			int ret;
 
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/*
			 * Watermark failed for this zone, but see if we can
			 * grow this zone if it contains deferred pages.
			 */
			if (static_branch_unlikely(&deferred_pages)) {
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
			/* Checked here to keep the fast path fast */
			BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);
			if (alloc_flags & ALLOC_NO_WATERMARKS)
				goto try_this_zone;
 
			if (node_reclaim_mode == 0 ||
			    !zone_allows_reclaim(ac->preferred_zoneref->zone, zone))
				continue;
 
			ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);
			switch (ret) {
			case NODE_RECLAIM_NOSCAN:
				/* did not scan */
				continue;
			case NODE_RECLAIM_FULL:
				/* scanned but unreclaimable */
				continue;
			default:
				/* did we reclaim enough */
				if (zone_watermark_ok(zone, order, mark,
						ac_classzone_idx(ac), alloc_flags))
					goto try_this_zone;
 
				continue;
			}
		}
 
try_this_zone:
		page = rmqueue(ac->preferred_zoneref->zone, zone, order,
				gfp_mask, alloc_flags, ac->migratetype);
		if (page) {
			prep_new_page(page, order, gfp_mask, alloc_flags);
 
			/*
			 * If this is a high-order atomic allocation then check
			 * if the pageblock should be reserved for the future
			 */
			if (unlikely(order && (alloc_flags & ALLOC_HARDER)))
				reserve_highatomic_pageblock(page, zone, order);
 
			return page;
		} else {
#ifdef CONFIG_DEFERRED_STRUCT_PAGE_INIT
			/* Try again if zone has deferred pages */
			if (static_branch_unlikely(&deferred_pages)) {
				if (_deferred_grow_zone(zone, order))
					goto try_this_zone;
			}
#endif
		}
	}
 
	/*
	 * It's possible on a UMA machine to get through all zones that are
	 * fragmented. If avoiding fragmentation, reset and try again.
	 */
	if (no_fallback) {
		alloc_flags &= ~ALLOC_NOFRAGMENT;
		goto retry;
	}
 
	return NULL;
}

함수가 꽤 방대한데 간략화하면 다음과 같다.

1) 요청한 node와 zonelist에서 선호 우선순위가 높은 zone에 대해 아래 루틴을 반복한다.

2) cgroup상의 지원과 dirty balancing limit을 체크한다.

3) no_fallback이 설정된 경우 로컬 노드가 아니라면 재시도한다.

4) zone_watermark_fast로 가용 메모리를 체크한다.

5) 메모리가 부족한 경우 node_reclaim으로 페이지를 회수하고, zone_watermark_ok로 다시 체크한다.

6) 메모리 할당이 가능하다면 rmqueue로 buddy system상에서 페이지를 할당한다.

7) 성공시 page 구조체를 초기화하여 반환한다.

8) 실패시 null을 반환한다.

 

실제로 페이지를 할당하는 핵심은 rmqueue 함수다.

 

 

 

5. Slow-path 할당

 

fast-path 할당이 실패한 경우 slow-path를 진행하는 함수 __alloc_pages_slowpath의 정의는 다음과 같다.

static inline struct page *
__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,
						struct alloc_context *ac)
{
	bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;
	const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;
	struct page *page = NULL;
	unsigned int alloc_flags;
	unsigned long did_some_progress;
	enum compact_priority compact_priority;
	enum compact_result compact_result;
	int compaction_retries;
	int no_progress_loops;
	unsigned int cpuset_mems_cookie;
	int reserve_flags;
 
	/*
	 * We also sanity check to catch abuse of atomic reserves being used by
	 * callers that are not in atomic context.
	 */
	if (WARN_ON_ONCE((gfp_mask & (__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)) ==
				(__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)))
		gfp_mask &= ~__GFP_ATOMIC;
 
retry_cpuset:
	compaction_retries = 0;
	no_progress_loops = 0;
	compact_priority = DEF_COMPACT_PRIORITY;
	cpuset_mems_cookie = read_mems_allowed_begin();
 
	/*
	 * The fast path uses conservative alloc_flags to succeed only until
	 * kswapd needs to be woken up, and to avoid the cost of setting up
	 * alloc_flags precisely. So we do that now.
	 */
	alloc_flags = gfp_to_alloc_flags(gfp_mask);
 
	/*
	 * We need to recalculate the starting point for the zonelist iterator
	 * because we might have used different nodemask in the fast path, or
	 * there was a cpuset modification and we are retrying - otherwise we
	 * could end up iterating over non-eligible zones endlessly.
	 */
	ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
					ac->high_zoneidx, ac->nodemask);
	if (!ac->preferred_zoneref->zone)
		goto nopage;
 
	if (alloc_flags & ALLOC_KSWAPD)
		wake_all_kswapds(order, gfp_mask, ac);
 
	/*
	 * The adjusted alloc_flags might result in immediate success, so try
	 * that first
	 */
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
	if (page)
		goto got_pg;
 
	/*
	 * For costly allocations, try direct compaction first, as it's likely
	 * that we have enough base pages and don't need to reclaim. For non-
	 * movable high-order allocations, do that as well, as compaction will
	 * try prevent permanent fragmentation by migrating from blocks of the
	 * same migratetype.
	 * Don't try this for allocations that are allowed to ignore
	 * watermarks, as the ALLOC_NO_WATERMARKS attempt didn't yet happen.
	 */
	if (can_direct_reclaim &&
			(costly_order ||
			   (order > 0 && ac->migratetype != MIGRATE_MOVABLE))
			&& !gfp_pfmemalloc_allowed(gfp_mask)) {
		page = __alloc_pages_direct_compact(gfp_mask, order,
						alloc_flags, ac,
						INIT_COMPACT_PRIORITY,
						&compact_result);
		if (page)
			goto got_pg;
 
		/*
		 * Checks for costly allocations with __GFP_NORETRY, which
		 * includes some THP page fault allocations
		 */
		if (costly_order && (gfp_mask & __GFP_NORETRY)) {
			/*
			 * If allocating entire pageblock(s) and compaction
			 * failed because all zones are below low watermarks
			 * or is prohibited because it recently failed at this
			 * order, fail immediately unless the allocator has
			 * requested compaction and reclaim retry.
			 *
			 * Reclaim is
			 *  - potentially very expensive because zones are far
			 *    below their low watermarks or this is part of very
			 *    bursty high order allocations,
			 *  - not guaranteed to help because isolate_freepages()
			 *    may not iterate over freed pages as part of its
			 *    linear scan, and
			 *  - unlikely to make entire pageblocks free on its
			 *    own.
			 */
			if (compact_result == COMPACT_SKIPPED ||
			    compact_result == COMPACT_DEFERRED)
				goto nopage;
 
			/*
			 * Looks like reclaim/compaction is worth trying, but
			 * sync compaction could be very expensive, so keep
			 * using async compaction.
			 */
			compact_priority = INIT_COMPACT_PRIORITY;
		}
	}
 
retry:
	/* Ensure kswapd doesn't accidentally go to sleep as long as we loop */
	if (alloc_flags & ALLOC_KSWAPD)
		wake_all_kswapds(order, gfp_mask, ac);
 
	reserve_flags = __gfp_pfmemalloc_flags(gfp_mask);
	if (reserve_flags)
		alloc_flags = reserve_flags;
 
	/*
	 * Reset the nodemask and zonelist iterators if memory policies can be
	 * ignored. These allocations are high priority and system rather than
	 * user oriented.
	 */
	if (!(alloc_flags & ALLOC_CPUSET) || reserve_flags) {
		ac->nodemask = NULL;
		ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,
					ac->high_zoneidx, ac->nodemask);
	}
 
	/* Attempt with potentially adjusted zonelist and alloc_flags */
	page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);
	if (page)
		goto got_pg;
 
	/* Caller is not willing to reclaim, we can't balance anything */
	if (!can_direct_reclaim)
		goto nopage;
 
	/* Avoid recursion of direct reclaim */
	if (current->flags & PF_MEMALLOC)
		goto nopage;
 
	/* Try direct reclaim and then allocating */
	page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,
							&did_some_progress);
	if (page)
		goto got_pg;
 
	/* Try direct compaction and then allocating */
	page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,
					compact_priority, &compact_result);
	if (page)
		goto got_pg;
 
	/* Do not loop if specifically requested */
	if (gfp_mask & __GFP_NORETRY)
		goto nopage;
 
	/*
	 * Do not retry costly high order allocations unless they are
	 * __GFP_RETRY_MAYFAIL
	 */
	if (costly_order && !(gfp_mask & __GFP_RETRY_MAYFAIL))
		goto nopage;
 
	if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,
				 did_some_progress > 0, &no_progress_loops))
		goto retry;
 
	/*
	 * It doesn't make any sense to retry for the compaction if the order-0
	 * reclaim is not able to make any progress because the current
	 * implementation of the compaction depends on the sufficient amount
	 * of free memory (see __compaction_suitable)
	 */
	if (did_some_progress > 0 &&
			should_compact_retry(ac, order, alloc_flags,
				compact_result, &compact_priority,
				&compaction_retries))
		goto retry;
 
 
	/* Deal with possible cpuset update races before we start OOM killing */
	if (check_retry_cpuset(cpuset_mems_cookie, ac))
		goto retry_cpuset;
 
	/* Reclaim has failed us, start killing things */
	page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);
	if (page)
		goto got_pg;
 
	/* Avoid allocations with no watermarks from looping endlessly */
	if (tsk_is_oom_victim(current) &&
	    (alloc_flags == ALLOC_OOM ||
	     (gfp_mask & __GFP_NOMEMALLOC)))
		goto nopage;
 
	/* Retry as long as the OOM killer is making progress */
	if (did_some_progress) {
		no_progress_loops = 0;
		goto retry;
	}
 
nopage:
	/* Deal with possible cpuset update races before we fail */
	if (check_retry_cpuset(cpuset_mems_cookie, ac))
		goto retry_cpuset;
 
	/*
	 * Make sure that __GFP_NOFAIL request doesn't leak out and make sure
	 * we always retry
	 */
	if (gfp_mask & __GFP_NOFAIL) {
		/*
		 * All existing users of the __GFP_NOFAIL are blockable, so warn
		 * of any new users that actually require GFP_NOWAIT
		 */
		if (WARN_ON_ONCE(!can_direct_reclaim))
			goto fail;
 
		/*
		 * PF_MEMALLOC request from this context is rather bizarre
		 * because we cannot reclaim anything and only can loop waiting
		 * for somebody to do a work for us
		 */
		WARN_ON_ONCE(current->flags & PF_MEMALLOC);
 
		/*
		 * non failing costly orders are a hard requirement which we
		 * are not prepared for much so let's warn about these users
		 * so that we can identify them and convert them to something
		 * else.
		 */
		WARN_ON_ONCE(order > PAGE_ALLOC_COSTLY_ORDER);
 
		/*
		 * Help non-failing allocations by giving them access to memory
		 * reserves but do not use ALLOC_NO_WATERMARKS because this
		 * could deplete whole memory reserves which would just make
		 * the situation worse
		 */
		page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_HARDER, ac);
		if (page)
			goto got_pg;
 
		cond_resched();
		goto retry;
	}
fail:
	warn_alloc(gfp_mask, ac->nodemask,
			"page allocation failure: order:%u", order);
got_pg:
	return page;
}

이번에도 함수가 굉장히 방대한데 간략화하면 다음과 같다.

1) gfp_mask를 alloc_flags로 변환한다.

2) zonelist에서 선호 zone을 선택한다.

3) alloc_flags에 kswapd reclaim이 설정되어 있는 경우 zone에 free 메모리가 기준치 미만이거나 단편화가 심한 경우 kswapd를 깨운다.

4) kswapd 수행 후 조정된 flag로 첫 번째 할당(get_page_from_freelist)을 시도한다.

5) movable이 아닌 order 1 이상의 할당 요청 시 direct_reclaim이 설정되어 있다면 direct_compact를 수행하여 페이지를 할당한다. (__alloc_pages_direct_compact)

6) reclaim cost가 너무 클(expensive) 경우 nopage로 넘어가고, 할만한 경우 async compact를 설정한다.

7) kswapd를 깨우거나 노드와 존을 바꿔서 할당을 시도해본다.

8) reclaim의 가능 여부를 보고 direct_reclaim 및 direct_compact 할당을 시도한다.

9) 재시도 여부를 판단하여 재시도 / 포기 / 다음 단계 진행을 한다.

10) OOM 킬링을 통해 할당을 시도한다.

11) nopage 레이블에서 fallback 할당을 시도한다.

12) 위의 할당 시도들에서 성공 시 바로 페이지를 반환하고 마지막까지 실패하면 할당을 포기한다.

 

결국 slow-path는 kswapd, direct-compaction, direct-reclaim, OOM-killing을 통해 메모리를 확보하여 할당을 시도한다.

 

 

 

6. rmqueue

 

위에서 결국 buddy system의 페이지 할당은 rmqueue 함수로 하는 것을 알 수 있다.

해당 함수의 정의는 다음과 같다.

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

1) order 0 할당 요청 시 rmqueue_pcplist를 호출하여 buddy cache로 동작하는 pcp(Per CPU Page Frame Cache)에서 할당 받는다.

2) alloc_flags에 ALLOC_HARDER이 설정된 경우 HIGHATOMIC 타입 리스트에서 할당을 시도한다.

3) 그 외엔 __rmqueue를 호출하여 실제 할당을 시도한다.

4) free/alloc 페이지 카운터를 조정한다.

5) zone flag에 BOOSTED_WATERMARK 설정시 kswapd를 깨운다.

 

실제 할당을 진행하는 __rmqueue는 다음과 같다.

/*
 * 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;
}
 
/*
 * 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 = get_page_from_free_area(area, migratetype);
		if (!page)
			continue;
		del_page_from_free_area(page, area);
		expand(zone, page, order, current_order, area, migratetype);
		set_pcppage_migratetype(page, migratetype);
		return page;
	}
 
	return NULL;
}
 
/*
 * 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]);

		/*
		 * 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
		 */
		if (set_page_guard(zone, &page[size], high, migratetype))
			continue;

		add_to_free_area(&page[size], area, migratetype);
		set_page_order(&page[size], high);
	}
}

__rmqueue에서는 __rmqueue_smallest를 호출하여 할당할 수 있는 가장 작은 페이지를 할당한다.

실패한 경우 fallback 타입을 검색하여 migratetype 이동 후 할당을 다시 시도한다.

__rmqueue_smallest에서는 인자로 전달받은 order부터 MAX_ORDER - 1까지 지정된 migratetype의 free_area를 순환하며 free page를 찾는다.

page를 할당받았으면 free_area에서 페이지를 제거하고, 할당을 인자로 전달받은 order보다 높은 곳에서 했다면 expand를 진행한다.

expand는 low order보다 큰 high order에서 페이지를 할당받은 경우 페이지를 high - 1부터 low 까지 분해한다.

예를 들어 __rmqueue_smallest의 인자 order은 2이고 할당에 성공한 current_order이 4라면

high order 4를 (order 3, order 2, order 2)로 분해하여 마지막 order 2를 반환한다.

 

 

 

7. 물리 페이지 반환

 

이 전 포스트에서 물리 페이지 반환 시 결국 __free_pages를 호출한다고 하였다.

이 함수 또한 free_the_page를 호출하고, order이 0이라면(pcp) free_unref_page를, 그 외엔 __free_pages_ok를 호출한다.

__free_pages_ok와 이 함수 내부에서 호출하는 free_one_page -> __free_one_page는 다음과 같다.

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);
}
 
/*
 * 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;
	struct capture_control *capc = task_capc(zone);
 
	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) {
		if (compaction_capture(capc, page, order, migratetype)) {
			__mod_zone_freepage_state(zone, -(1 << order),
								migratetype);
			return;
		}
		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
			del_page_from_free_area(buddy, &zone->free_area[order]);
		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;
	}
 
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)
			&& !is_shuffle_order(order)) {
		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)) {
			add_to_free_area_tail(page, &zone->free_area[order],
					      migratetype);
			return;
		}
	}
 
	if (is_shuffle_order(order))
		add_to_free_area_random(page, &zone->free_area[order],
				migratetype);
	else
		add_to_free_area(page, &zone->free_area[order], migratetype);
 
}

이번에도 코드가 조금 방대한데, 결국 반환하는 order의 페이지를 migrate 타입에 회수하고 병합하는 것이다.

예를들어 MOVABLE migrate에 order 2인 페이지였다면,

해당 free_area[2].free_list[MIGRATE_MOVABLE]에서 buddy page를 찾아서 상위 order로 병합하는 것을 반복한다.

 

 

이상 buddy system 상에서 메모리 할당과 반환(해제)를 알아보았다.

더욱 자세한 내용은 LWN이나 Kernel Documentation을 찾아보도록 한다.