Physical Memory Model (FLATMEM, SPARSEMEM)

struct page 메모

Introduction

완전히 flat한 형태 (왼쪽), 중간 중간에 구멍이 있는 형태

물리 메모리가 sparse하게 존재하는 경우 (왼쪽), 물리 메모리가 sparse하게 존재하며 서로 다른 NUMA 아키텍처인 경우

물리 메모리는 시스템 내에서 다양한 형태로 존재할 수 있다. 물리 주소 공간의 처음부터 끝까지 사용가능한 물리 메모리가 연속적으로 존재하거나, 중간에 구멍이 있을 수도 있다. 아니면 중간에 구멍이 있는 정도가 아니라 드문드문 물리 메모리가 존재할 수도 있으며, 서로 다른 NUMA 노드에 속할 수도 있다.

그림에서 보여주듯 물리 메모리의 레이아웃은 정말 다양한 형태로 존재할 수 있으며, 운영체제 입장에서는 이러한 다양한 물리 메모리의 형태를 커버할 수 있는 모델을 사용해야 한다. 또한 예전에 struct page에 관해 정리한 적이 있다. struct page는 PAGE_SIZE 크기의 메모리에 대한 디스크립터이다. 이 디스크립터의 레이아웃 또한 물리 메모리 모델에 따라서 형태가 바뀐다. 그리고 page frame number <-> struct page 포인터 변환 방법도 다르다.

현대적인 64비트 프로세서와 배포판을 사용한다면 주로 다음 세 가지 config들을 사용하게 되는데, 천천히 알아보자.

SPARSEMEM, SPARSEMEM_VMEMMAP, SPARSEMEM_EXTREME

Physical Memory Model

FLATMEM

완전히 flat한 형태 (왼쪽), 중간 중간에 구멍이 있는 형태

대체로 컴퓨터 시스템에서 물리 메모리는 왼쪽처럼 완전히 구멍이 없고 평평한 형태보다는 오른쪽처럼 중간에 구멍이 조금씩은 있을 것이다. (MMIO를 위한 부분이라던가) 이런 경우 리눅스는 왼쪽 사진처럼 물리 메모리가 (대체로) 연속적으로 존재할 것이라고 가정하는 FLATMEM 메모리 모델을 사용한다. FLATMEM은 non-NUMA 아키텍처이며 물리 메모리가 대부분 연속적으로 존재하는 경우에 적합하다.

struct page layout

FLATMEM의 경우, struct page들은 전역으로 존재하는 mem_map이라는 이름의 하나의 거대한 배열의 형태로 존재하며, physical page frame number가 배열의 인덱스로 사용된다. 중간에 물리 메모리에 구멍이 존재하는 경우에는 해당하는 디스크립터도 사용하지 않고 낭비된다. pfn이 배열의 인덱스로 사용되므로 pfn_to_page(), page_to_pfn() 매크로의 구현도 단순한다.

#define __pfn_to_page(pfn)	(mem_map + ((pfn) - ARCH_PFN_OFFSET))
#define __page_to_pfn(page)	((unsigned long)((page) - mem_map) + \
				 ARCH_PFN_OFFSET)

PFN validity

page frame number가 유효한지, 즉 pfn에 해당하는 struct page가 존재하는지 확인할 때는 pfn_valid() 매크로를 사용한다. FLATMEM에서는 mem_map의 모든 원소에 대하여 pfn_valid()가 참을 반환한다. 단, 아키텍처 구현에서 mem_map의 일부를 free할 수도 있는데, 그런 경우에는 free된 원소들에 대하여 pfn_valid()가 거짓을 반환해야 한다. [1]

SPARSEMEM

SPARSEMEM은 가장 가변적인 메모리 모델이며, 메모리 hot-plug와 hot-remove, non-volatile memory를 위한 별도의 memory map과, 거대한 시스템에서 memory map의 deferred initialization을 지원하는 고급 메모리 모델이다. [1] SPARSEMEM은 NUMA를 효과적으로 지원하며, 아래 그림처럼 메모리가 듬성듬성 존재하는 경우까지도 효율적으로 관리한다. 대체로 FLATMEM보다는 SPARSEMEM이 기본적으로 사용된다.

물리 메모리가 sparse하게 존재하는 경우 (왼쪽), 물리 메모리가 sparse하게 존재하며 서로 다른 NUMA 아키텍처인 경우

SPARSEMEM에서 물리 메모리는 섹션들의 집합이며, 하나의 섹션은 struct mem_section으로 표현된다. FLATMEM에서는 memory map이 mem_map이라는 전역변수로 존재했지만, SPARSEMEM에서는 struct mem_section별로 섹션에 해당하는 물리 메모리들에 대한 struct page 배열을 갖는다. (section_mem_map) 섹션의 크기와 개수는 SECTION_SIZE_BITS, MAX_PHYSMEM_BITS에 의해 결정된다.

https://www.kernel.org/doc/html/v6.1/mm/memory-model.html

x86_64에서 SECTION_SIZE_BITS는 27이므로 섹션 하나의 크기는 128MiB이며, 섹션의 개수는 물리 메모리의 최대 크기를 섹션의 크기로 나누어야 하므로 페이지 테이블이 몇 단계냐에 따라서 2^(MAX_PHYSMEM_BITS - 27)개의 섹션이 존재한다. 따라서 x86_64에서는 2^25 혹은 2^19개의 섹션이 존재한다. 각 섹션은 섹션 번호로 구분할 수 있는데, 섹션 번호는 물리 주소를 SECTION_SIZE_BITS (or PA_SECTION_SHIFT)만큼 오른쪽 시프트를 하면 얻을 수 있다.

하나의 섹션은 다시 여러 개의 subsection으로 나눌 수 있다. subsection의 크기는 SUBSECTION_SHIFT에 의해 결정되며, 섹션마다 1 << (SECTION_SIZE_BITS - SUBSECTION_SHIFT)개의 서브 섹션이 존재한다.

struct mem_section은 하나의 섹션을 나타내며, 전체 물리 메모리는 mem_section의 2차원 배열로 나타낼 수 있다. 이 배열의 정의는 다음과 같다. (그렇다. 구조체의 이름도 mem_section이고 배열의 이름도 mem_section이다. 헷갈린다.)

/*
 * Permanent SPARSEMEM data:
 *
 * 1) mem_section	- memory sections, mem_map's for valid memory
 */
#ifdef CONFIG_SPARSEMEM_EXTREME
struct mem_section **mem_section;
#else
struct mem_section mem_section[NR_SECTION_ROOTS][SECTIONS_PER_ROOT]
	____cacheline_internodealigned_in_smp;
#endif
EXPORT_SYMBOL(mem_section);

mem_section 배열의 정의는 SPARSEMEM_EXTREME을 사용하냐 아니냐에 따라 달라진다. 정의는 다르지만 둘다 사실상 struct mem_section의 2차원 배열이다. 

mem_section에서는 섹션들을 SECTIONS_PER_ROOT개씩 묶어서 root라고 부른다. 섹션 번호의 하위 비트들은 root 내에서의 섹션 번호이며, 상위 비트들은 root의번호로 사용된다.

그런데 편하게 섹션 번호를 인덱스로 하는 1차원 배열을 정의하면 될텐데 왜 2차원 배열일까? 그건 뒤에서 SPARSEMEM_EXTREME을 살펴보면서 알아보자.

SPARSEMEM_STATIC, SPARSEMEM_EXTREME

SPARSEMEM을 사용할 때, mem_section 배열을 어떻게 구성하냐에 따라서 SPARSEMEM_STATIC 혹은 SPARSEMEM_EXTREME config을 추가적으로 활성화하게 된다.

SPARSEMEM_STATIC에서는 struct mem_section의 2차원 배열이 정적 배열로 선언된다. 64비트 커널에서는 많은 수의 섹션이 존재하기 때문에 SPARSEMEM_STATIC을 사용할 경우 bss 섹션이 커질 수 있으며 사용되지 않는 섹션에 대한 원소들도 다수 할당된다.

struct mem_section mem_section[NR_SECTION_ROOTS][SECTIONS_PER_ROOT]
	____cacheline_internodealigned_in_smp;

mem_section 배열의 정의를 보면 왼쪽 사진처럼 root마다 여러 개의 섹션이 있을 것 같지만, SPARSEMEM_STATIC에서는 SECTIONS_PER_ROOT가 1이기 때문에 오른쪽 사진처럼 사실상 1차원 배열이다. 이렇게 굳이 2차원 배열로 정의해놓고 1차원 배열처럼 쓰는 이유는, 애초에 mem_section 배열을 2차원 배열로 사용하는 이유가 SPARSEMEM_EXTREME에서 mem_section 배열을 root라는 단위로 동적으로 할당해서 쓰기 위한 것이기 때문이다.

SPARSEMEM_EXTREME은 SPARSEMEM_STATIC처럼 전체 2차원 배열을 한꺼번에 할당하지 않고, 아래 그림처럼 실제 물리 메모리가 존재하는 부분만 동적으로 할당된다.

SPARSEMEM_EXTREME을 사용하면 사용되지 않는 root는 할당하지 않으므로 메모리 오버헤드를 줄이는 대신, 실행 오버헤드가 증가하게 된다. 64비트 커널에서는 섹션의 수가 아주 많기 때문에 SPARSEMEM_STATIC을 사용하면 mem_section 배열의 크기만 수MiB~수백MiB가 되므로 대부분 SPARSEMEM_EXTREME을 사용한다.

struct page layout

struct page layout on SPARSEMEM

PAGE_EXTENSION을 사용하지 않을 때 struct mem_section, mem_section_usage의 정의는 다음과 같다.

struct mem_section {
	/*
	 * This is, logically, a pointer to an array of struct
	 * pages.  However, it is stored with some other magic.
	 * (see sparse.c::sparse_init_one_section())
	 *
	 * Additionally during early boot we encode node id of
	 * the location of the section here to guide allocation.
	 * (see sparse.c::memory_present())
	 *
	 * Making it a UL at least makes someone do a cast
	 * before using it wrong.
	 */
	unsigned long section_mem_map;
	struct mem_section_usage *usage;
};

section_mem_map은 논리적으로 struct page의 배열에 대한 포인터이며 section_mem_map 필드의 비트들은 섹션에 대한 정보를 기록하는 데 사용된다.

struct mem_section_usage {
#ifdef CONFIG_SPARSEMEM_VMEMMAP
	DECLARE_BITMAP(subsection_map, SUBSECTIONS_PER_SECTION);
#endif
	/* See declaration of similar field in struct zone */
	unsigned long pageblock_flags[0];
};

usage는 (SPARSEMEM_VMEMMAP을 사용하는 경우) 섹션 내 각 subsection들의 validity를 비트맵으로 저장하며, section_mem_map 상의 page block들의 flag (migrate type)을 나타낸다.

Section number to mem_section conversion

섹션 번호를 mem_section 배열의 원소로 변환하는 것은 섹션 번호를 root 번호와 root 내에서의 섹션 번호로 나누어서 각각 인덱스로 사용하면 구할 수 있다.

static inline struct mem_section *__nr_to_section(unsigned long nr)
{
	unsigned long root = SECTION_NR_TO_ROOT(nr);

	if (unlikely(root >= NR_SECTION_ROOTS))
		return NULL;

#ifdef CONFIG_SPARSEMEM_EXTREME
	if (!mem_section || !mem_section[root])
		return NULL;
#endif
	return &mem_section[root][nr & SECTION_ROOT_MASK];
}

pfn_to_page(), page_to_pfn()

SPARSEMEM에서는 struct page의 flags필드에 섹션 번호가 저장되어있다. include/linux/page-flags-layout.h를 보자.

/*
 * page->flags layout:
 *
 * There are five possibilities for how page->flags get laid out.  The first
 * pair is for the normal case without sparsemem. The second pair is for
 * sparsemem when there is plenty of space for node and section information.
 * The last is when there is insufficient space in page->flags and a separate
 * lookup is necessary.
 *
 * No sparsemem or sparsemem vmemmap: |       NODE     | ZONE |             ... | FLAGS |
 *      " plus space for last_cpupid: |       NODE     | ZONE | LAST_CPUPID ... | FLAGS |
 * classic sparse with space for node:| SECTION | NODE | ZONE |             ... | FLAGS |
 *      " plus space for last_cpupid: | SECTION | NODE | ZONE | LAST_CPUPID ... | FLAGS |
 * classic sparse no space for node:  | SECTION |     ZONE    | ... | FLAGS |
 */

주석에 잘 설명되어있듯 SPARSEMEM을 사용하며 SPARSEMEM_VMEMMAP을 사용하지 않는 경우 섹션 번호가 flags 필드에 저장된다.

page_to_pfn()은 struct page에서 section number를 가져온 후 pfn으로 변환하며, pfn_to_page()는 pfn을 section number로 변환한 후 struct page의 위치를 계산한다.

/*
 * Note: section's mem_map is encoded to reflect its start_pfn.
 * section[i].section_mem_map == mem_map's address - start_pfn;
 */
#define __page_to_pfn(pg)					\
({	const struct page *__pg = (pg);				\
	int __sec = page_to_section(__pg);			\
	(unsigned long)(__pg - __section_mem_map_addr(__nr_to_section(__sec)));	\
})

#define __pfn_to_page(pfn)				\
({	unsigned long __pfn = (pfn);			\
	struct mem_section *__sec = __pfn_to_section(__pfn);	\
	__section_mem_map_addr(__sec) + __pfn;		\
})

static inline struct page *__section_mem_map_addr(struct mem_section *section)
{
	unsigned long map = section->section_mem_map;
	map &= SECTION_MAP_MASK;
	return (struct page *)map;
}

그런데, 위 코드를 보고 이쯤에서 이상함을 느낄 수 있다. pfn은 section_mem_map에 대한 인덱스가 아닌 절대적인 값인데 어떻게 section_mem_map + pfn로 struct page의 위치를 계산할 수 있지? 그 답은 sparse_encode_mem_map()에 있다.

/*
 * Subtle, we encode the real pfn into the mem_map such that
 * the identity pfn - section_mem_map will return the actual
 * physical page frame number.
 */
static unsigned long sparse_encode_mem_map(struct page *mem_map, unsigned long pnum)
{
	unsigned long coded_mem_map =
		(unsigned long)(mem_map - (section_nr_to_pfn(pnum)));
	BUILD_BUG_ON(SECTION_MAP_LAST_BIT > PFN_SECTION_SHIFT);
	BUG_ON(coded_mem_map & ~SECTION_MAP_MASK);
	return coded_mem_map;
}

section_mem_map에 저장되는 값은 struct page 배열의 주소가 아니라, 거기서 섹션의 pfn을 뺀 값이 저장된다. 이렇게 저장하면 pfn이라는 절대적인 값을 struct page 배열 내에서의 인덱스인 것처럼 사용할 수 있다.

PFN validity

아키텍처에 따라서 pfn validity를 확인하는 방법은 다양할 수 있지만, 일반적인 구현은 include/linux/mmzone.h에 있다.

SPARSEMEM (without SPARSEMEM_VMEMMAP)에서는 pfn_section_valid()가 서브섹션 단위의 validity를 확인하지 않기 때문에 섹션 단위로 (i.e. 128MiB in x86_64) valid하거나 invalid하다.

#ifndef CONFIG_HAVE_ARCH_PFN_VALID
/**
 * pfn_valid - check if there is a valid memory map entry for a PFN
 * @pfn: the page frame number to check
 *
 * Check if there is a valid memory map entry aka struct page for the @pfn.
 * Note, that availability of the memory map entry does not imply that
 * there is actual usable memory at that @pfn. The struct page may
 * represent a hole or an unusable page frame.
 *
 * Return: 1 for PFNs that have memory map entries and 0 otherwise
 */
static inline int pfn_valid(unsigned long pfn)
{
	struct mem_section *ms;

	/*
	 * Ensure the upper PAGE_SHIFT bits are clear in the
	 * pfn. Else it might lead to false positives when
	 * some of the upper bits are set, but the lower bits
	 * match a valid pfn.
	 */
	if (PHYS_PFN(PFN_PHYS(pfn)) != pfn)
		return 0;

	if (pfn_to_section_nr(pfn) >= NR_MEM_SECTIONS)
		return 0;
	ms = __pfn_to_section(pfn);
	if (!valid_section(ms))
		return 0;
	/*
	 * Traditionally early sections always returned pfn_valid() for
	 * the entire section-sized span.
	 */
	return early_section(ms) || pfn_section_valid(ms, pfn);
}
#endif

SPARSEMEM_VMEMMAP

SPARSEMEM은 FLATMEM이 커버하지 못하는 다양한 형태의 물리 메모리 레이아웃을 효과적으로 커버하지만, 대신 page <-> pfn 변환이 FLATMEM보다 복잡하다. SPARSEMEM_VMEMMAP은 더 간단하고 효율적으로 page <-> pfn 변환을 하기 위해 도입되었다.

대부분의 64비트 아키텍처에서 SPARSEMEM_VMEMMAP이 사용되지만, 가상 주소 공간을 많이 차지하기 때문에 안그래도 주소 공간이 작은 32비트 커널에서는 사용되지 않는다.

struct page layout

!SPARSEMEM_VMEMMAP에서 struct page의 layout은 앞서 설명한대로 struct mem_section 별로 struct page의 배열이 존재하는 형태이다. 이와 달리 SPARSEMEM_VMEMMAP에서는 커널 주소 공간에 가상의 memory map을 위한 영역이 존재한다 (vmemmap).

섹션을 초기화할 때 !SPARSEMEM_VMEMMAP에서는 그냥 memblock_alloc()을 통해서 할당받지만, SPARSEMEM_VMEMMAP에서는 페이지를 할당한 후 먼저 vmemmap 주소 공간에 populate한 다음 그걸 section_mem_map에 인코딩한다. 따라서 비록 각 섹션의 struct page의 배열들이 물리적으로는 흩어져있더라도 vmemmap 주소 공간 상에서 연속적이게 된다. vmemmap 매크로(x86_64, arm64)는 virtual memory map의 시작을 가리키며, 하나의 거대한 struct page의 배열인 것처럼 사용된다.

pfn_to_page(), page_to_pfn()

SPARSEMEM_VMEMMAP에서의 pfn <-> page 변환은, 비록 FLATMEM처럼 물리적으로 연속적이지는 않지만 가상 주소 상으로 연속적인 가상의 memory map이 존재하므로, FLATMEM처럼 아주 간단하게 변환할 수 있다.

/* memmap is virtually contiguous.  */
#define __pfn_to_page(pfn)	(vmemmap + (pfn))
#define __page_to_pfn(page)	(unsigned long)((page) - vmemmap)

참고로 vmemmap에서는 page -> section 변환이 필요하지 않기 때문에 struct page의 flags 필드에 섹션 번호가 저장되지 않는다.

vmemmap population

vmemmap population은 부팅 후 sparse_init() -> sparse_init_nid()에서 섹션을 초기화하면서 __populate_section_memmap()을 호출하면서 수행된다.

PFN validity

SPARSEMEM_VMEMMAP에서는 struct mem_section_usage에 섹션 내의 각 subsection이 유효한지를 bitmap으로 관리하기 때문에,  pfn_section_valid()에서 subsection 단위 (2MiB in x86_64)의 validity를 체크할 수 있다.

References

[1] Physical Memory Model, Linux Kernel Documentation