percpu는 "percpu: implement new dynamic percpu allocator"의 패치로 리뉴얼 되었습니다. 또한 뒤따르는 후속 패치들로 2800줄에 이르는 코드가 되었습니다. 다양한 내용이 반영된 최신의 percpu.c 파일을 분석하기보다는 몇 줄 안되는 초창기 버전의 percpu.c를 분석하며, percpu의 컨셉과 구현되었는지 알아보도록 하겠습니다.
주의! 해당 글은 percpu가 처음 도입된 Linux kernel v2.6.29을 다룹니다.
Prehistoric implementation
우선 percpu가 재구현되기 전에 모습을 살펴보고, 어떤 점 때문에 대대적으로 수정되었는지 알아보도록 하겠습니다. 재구현 이전에는 percpu가 static, dynamic에 따라 서로 다른 구조로 구현되었습니다.
Static percpu variable
우선 static percpu 변수에 대해 살펴보도록 하겠습니다. Static percpu 변수는 아래와 같은 DEFINE_PER_CPU 매크로를 사용하여 선언합니다.
이 매크로는,
이 변수의 타입은 인자로 받은 type이다.
이 변수의 이름은 "per_cpu__" 와 인자로 받은 name을 ## 연산자를 이용하여 만든다.
이 변수는 .data.percpu 섹션에 위치한다.
단순히 매크로를 통해 선언하는 것으로는 static percpu 변수를 바로 사용할 수 없습니다. 사용하기 위해서는 setup_per_cpu_areas() 함수를 통해 static percpu가 초기화해야 합니다. 아래의 첨부된 코드를 살펴보면서 어떻게 구현되었는지 확인해보도록 하겠습니다.
해당 함수는 static percpu를 영역을 CPU마다 가지도록 합니다. 그렇게 하기 위해서 필요한 용량의 크기를 구한 후 bootmem 할당자를 통해 메모리를 할당합니다. 그런 다음 각 CPU마다 .data.percpu의 값들을 복사하고 그 위치를 저장합니다.
Dynamic percpu variable
옛 Dynamic percpu 변수의 경우, 아래와 같이 간단하게 구성되었습니다.
해당 구조로 인해,
데이터에 접근하기 위해 메모리 참조가 2번 필요합니다.
할당할 때, 실제 데이터의 크기(CPU 개수 * 자료형 크기)보다 더 많은 메모리가 요구됩니다.
앞서 살펴본 대로 static percpu와 dynamic percpu의 구조는 서로 다릅니다. 따라서 이들을 하나의 percpu로 통합하는 패치를 앞으로 살펴보도록 하겠습니다.
Reimplementation
새로운 percpu는 dynamic percpu를 static percpu의 구조에서 할당받을 수 있도록 변경되었습니다. 이전의 static percpu을 초기화하는 setup_percpu_area 함수처럼, 연속된 메모리를 할당받고, CPU마다 공평하게 분배합니다. 여기서 연속된 하나의 커다란 메모리를 chunk라 하고, CPU마다 분배받은 영역을 unit이라 합니다.
static percpu의 경우 chunk를 할당하고 각각의 unit에 .data.percpu 섹션을 복사하고 난 뒤 추가로 해야할 일이 없지만, dynamic percpu는 동적으로 새로운 영역을 할당 또는 해제할 수 있어야 합니다. 즉, chunk 내의 dynamic percpu를 할당할 공간이 부족하면 새로운 영역을 할당 받아야 합니다. 이때, percpu는 새로운 chunk를 만듭니다. 따라서 chunk는 계속 늘어날 수 있도록 하고, 특정 chunk를 검색할 수 있도록 자료 구조를 가져야 합니다. 이러한 요구 사항들을 어떻게 구현했는지 chunk 구조체를 살펴보도록 하겠습니다.
앞서 말한대로 chunk 내부의 멤버들은 크게 2가지로 분류됩니다. 첫 번째는 검색을 위한 멤버, 두 번째는 메모리 관리를 위한 멤버입니다. 우선 이 두 가지 종류의 멤버 중 메모리 관리를 위한 멤버에 대해 알아보겠습니다.
Chunk's internal memory management
위에서 chunk는 하나의 연속된 메모리라 하였습니다. 실제로는 연속된 가상 주소 영역을 할당 받는 것입니다. 물리 페이지와의 매핑은 실제로 percpu 할당 요청이 들어올 때까지 미루어 집니다. get_vm_area를 통해 할당된 가상 주소 영역은 멤버 변수 vm에 저장됩니다. 실제로 할당된 물리 페이지는 chunk 내부의 페이지 디스크립터 배열(struct page* page[])을 사용하여 관리합니다.
관련된 여러 함수들은 아래와 같습니다. 단순하므로 설명은 생략하겠습니다.
유닛 내의 할당된 공간/사용 가능한 공간을 관리를 위해서는 chunk의 멤버 변수 map을 사용합니다.
최신 버전에서 chunk 내 메모리 관리 방식은 이와 다른 방식을 사용합니다. 이전 방식에 관심이 없다면 아래의 설명은 넘어가면 됩니다.
map은 unit 내의 할당 정보를 저장하고 있는 벡터입니다. 할당된/할당되지 않은 연속된 범위에 대해 하나의 엔트리를 가집니다. 할당된 영역은 음수로, 할당되지 않은 영역은 양수로 저장됩니다.
아래는 단순한 map의 사용 예입니다. unit에서 사용 가능한 영역으로는 0x8과, 0x18이 있습니다. 0x20과 0x10 영역은 현재 사용 중인 영역이므로 음수로 표현됩니다.
이러한 map의 특성으로 chunk에서 새로운 percpu 영역을 할당 또는 해제할 때마다 map를 갱신해야 합니다.
Chunk searching
dynamic percpu를 할당할 때, 요청한 크기를 할당 가능한 chunk를 찾아야 합니다. 단순하게 모든 chunk를 순회하면서 찾을 수 있지만, 효율적인 검색을 위해 slot을 사용합니다. 이 방법은 최신 버전까지 사용되고 있습니다.
chunk의 free size에 따라 chunk가 위치하는 슬롯이 다르도록 만듭니다. 만약 alloc/free에 의해 freesize가 변경되면 chunk를 올바른 슬롯에 배치하는 pcpu_chunk_relocate를 호출합니다.
alloc을 요청할 때의 size를 보고 어떤 슬롯에 해당하는지 알기 위해 아래의 pcpu_size_to_slot 함수가 사용됩니다.
Dynamic percpu allocation
이제, dynamic percpu allocation 과정을 살펴보도록 하겠습니다. 할당 과정은 3가지로 이루어져 있습니다.
요청받은 사이즈를 수용할 수 있는 chunk 찾는다.
해당 chunk에 새로운 percpu 영역 할당한다. 즉, chunk 내부 자료구조들을 갱신한다.
할당한 percpu에 대해 매핑이 되지 않은 가상 주소가 있다면 매핑한다.
구체적인 구현은 아래의 코드를 보면서 확인하겠습니다.
Line 12~14: 앞서 본 pcpu_size_to_slot 함수를 통해 size에 해당하는 슬롯을 구합니다. 할당에 성공할 때까지 구한 슬롯에서 더 큰 free size를 가지는 슬롯까지 순회합니다.
Line 16~18: 해당 chunk에 연속된 메모리가 존재한다면 pcpu_alloc_area를 호출합니다.
Line 34: 할당한 offset에 실제 물리 메모리가 매핑 되도록 populate를 진행합니다.
Line 39~42: chunk의 시작 가상 주소와 offset을 더해 percpu 주소를 만들어 리턴합니다. 이 때 __addr_to_pcpu_ptr 매크로를 이용해 가상 주소를 percpu 주소로 변경합니다. 이 매크로에 대한 자세한 내용은 뒤에서 확인해보겠습니다.
chunk 내의 사용 가능한 영역을 할당하는 함수는 pcpu_alloc_area 입니다. map을 순회하며 빈 공간에 할당이 가능한 지 확인하며, 할당 가능하다면 영역을 할당한 후 map을 갱신합니다. map이 어떻게 갱신되는지 궁금하신 분만 아래의 구현을 살펴보시면 될 것 같습니다.
이제 할당 받은 가상 주소 영역에 물리 페이지를 populate하는 pcpu_populate_chunk 함수를 살펴보도록 하겠습니다.
해당 함수는 [offset, offset+size-1]의 주소 영역의 매핑되지 않은 물리 페이지들을 매핑/초기화합니다.
Line 4~5: offset, offset+size에 대응하는 페이지 인덱스를 구합니다.
Line 15: 시작 페이지 인덱스부터 마지막 페이지 인덱스까지 순회합니다.
Line 16~24: 매핑되지 않은 map_start와 map_end의 페이지들을 가상 주소와 매핑합니다. pcpu_map 함수 내부에서 map_kernel을 통해 페이지 디스크립터와 가상 주소를 연결합니다.
Line 26~27: map_start와 map_end를 설정합니다. 할당되지 않은 페이지 인덱스의 시작과 끝을 저장합니다.
Line 30~37: 현재 페이지 인덱스에 각 유닛 별로 페이지를 할당합니다.
Line 40: 루프 안에서 매핑 하지 못한 페이지를 매핑합니다.
Line 43~45: 할당한 페이지들을 0으로 초기화합니다.
Dynamic allocation free
이제, dynamic percpu free 과정을 살펴보도록 하겠습니다. 해제 과정에서 해야 할 주요 과정으로는 아래와 같이 2가지가 있습니다.
인자로 받은 포인터가 속한 chunk를 구합니다.
해당 chunk의 map 자료 구조를 갱신합니다.
실제 구현에서는 사용하지 않는 chunk에 대한 reclaim도 같이 구현되어 있습니다. 자세한 내용은 아래의 코드를 살펴보면서 설명하겠습니다.
Line 3: 인자로 받은 percpu 주소를 가상 주소로 변환합니다. (아래에서 이 매크로에 대해 설명하겠습니다
Line 11~14: 가상 주소가 속한 chunk를 검색합니다. chunk를 구하였다면, chunk의 시작 주소로부터 얼마나 떨어졌는지 의미하는 offset을 구합니다.
Line 16: chunk와 offset을 통해 해당 영역을 사용 가능한 영역이라 변경합니다. 그렇게 하기 위해 chunk 내부의 map에 관련된 자료 구조들을 갱신합니다.
Line 19~27: 해당 영역을 반환하고, 아무도 이 chunk를 사용하지 않는다면 reclaim을 진행합니다. relaim은 work queue로 실행되며, reclaim을 진행하기 위해선 1개 이상의 사용되지 않는 다른 chunk가 있어야 합니다.
앞서 보았듯이 chunk에 어떤 영역을 반환하기 위해서 pcpu_free_area가 사용됩니다. 앞서 언급한 대로 map을 통한 관리는 최신 버전에서는 사용하지 않는 방법이기에 궁금하신 분만 아래의 코드를 참고하시면 될 것 같습니다.
지금까지 사용자가 percpu 변수를 할당하고 해제하는 주요 함수들(__alloc_perpcu, free_percpu)를 살펴보았습니다. 이제는 chunk에 대한 api를 살펴보도록 하겠습니다.
chunk allocation
만약 percpu 요청을 응답할 chunk가 없다면 새로운 chunk를 생성할 필요가 있습니다. 정규 할당자를 사용할 수 있는 경우에는 alloc_pcpu_chunk을 통해 동적으로 새로운 chunk를 생성할 수 있습니다.
alloc_pcpu_chunk는 정규 할당자를 이용하여, chunk 구조체를 할당하고 초기화 한다.
Line 5에서 chunk를 위한 공간을 할당을 받습니다.
Line 9~12: map을 할당을 하고, 초기화를 합니다. 모든 영역이 사용 가능하므로 pcpu_unit_size를 저장하는 엔트리 하나만 소유합니다.
Line 14: pcpu_chunk_size의 크기의 가상 주소 영역을 할당합니다.
Line 20~24: list, free_size, contig_hint를 초기화한 뒤 chunk를 반환합니다.
이렇게 만들어진 chunk는 slot에 등록어서, alloc_perpcu 함수를 통한 percpu 할당 요청에 응답할 수 있게 됩니다.
하지만 alloc_pcpu_chunk는 정규 할당자를 사용할 수 있을 때, 사용 가능합니다. 따라서 static percpu를 위한 chunk 할당할 때는 별도의 함수가 사용됩니다. pcpu_setup_first_chunk는 percpu에 관련된 여러 전역 변수들을 세팅하고 첫 chunk를 생성합니다.
Line 12~14: 위 함수는 인자로 unit_size를 직접 설정할 수도 있습니다. 그렇지 않다면 static percpu 크기 또는 최소 크기에 맞춥니다.
Line 18~22: percpu 시스템에 사용되는 unit의 크기와, chunk의 크기와 같은 전역 변수들을 설정합니다.
Line 28~31: slot을 위한 공간을 할당하고, 초기화를 진행합니다.
Line 38~41: free_size가 인자로 들어오면 그 값을 chunk의 free_size로 설정합니다. 아니라면 static한 영역을 할당하고 남은 공간으로 free_size를 설정합니다.
Line 46~60: 해당 chunk의 가상 주소 영역을 설정합니다. 인자로 base_addr가 설정되어 있다면, 해당 주소를 시작 주소로 사용합니다. base_addr이 설정되어 있지 않으면 vm_area_register_early 함수를 통해 가상 주소 영역을 할당 받습니다.
Line 64~79: cpu 별로 인자로 받은 get_page_fn를 통해 페이지를 할당합니다. 할당받은 페이지는 chunk의 page 배열에 저장됩니다.
Line 82~92: populate_pte_fn 함수 인자가 있다면, chunk에 할당된 가상 주소 영역의 매핑을 위해 페이지 테이블을 구성합니다. 그런 다음 페이지 테이블 엔트리에 값을 쓰면서 가상 주소와 할당 받은 물리 페이지를 매핑합니다.
Line 95: 구성된 chunk를 올바른 슬롯에 배치합니다.
Line 99~100: 생성한 chunk의 시작 가상 주소를 pcpu_base_addr에 저장하고, pcpu_unit_size를 반환합니다.
여기서 한 가지 주목해야할 점은, static percpu 영역이라도 그 가상 주소는 임의의 주소에 배치될 수 있다는 것 입니다. 하지만 코드에서 사용되는 static perpcu의 symbol들은 link time에 결정되어 버립니다. 따라서 link time에 결정된 static percpu 심볼들의 주소를 first chunk에 할당한 가상 주소와 변환할 수 있어야 합니다.
이것이 바로 앞에서는 넘어갔던 매크로 __addr_to_pcpu_ptr, __pcpu_ptr_to_addr입니다. 이 매크로에서 사용되는 용어 pcpu_ptr은 link time에 결정된 percpu 심볼들의 주소이고, 용어 addr은 chunk가 사용하는 가상 주소입니다.
이러한 변환 관계를 만들기 위해 pcpu_setup_first_chunk 함수는 static percpu를 수용하는 chunk의 시작 가상 주소를 pcpu_base_addr에 저장합니다.
chunk reclaim/free
앞서 free_percpu에서 본 것 같이, 사용되지 않은 chunk가 있을 때, chunk를 reclaim을 합니다. 이 때 pcpu_reclaim이 work queue로 동작합니다.
해당 함수는 사용되지 않는 chunk가 위치한 slot을 순회하면서, chunk를 작업 리스트로 list_move 합니다. 작업 리스트에 옮겨진 chunk들은 pcpu_depopulate_chunk를 통해 할당 받은 물리 페이지들을 버디 시스템에 반환하고, 가상 주소와 물리 페이지의 매핑을 해제합니다. 또한 free_pcpu_chunk를 통해 동적 할당 받은 메모리들을 반환합니다.
Access a percpu
사용자가 할당받은 percpu 변수를 사용하기 위해서는 먼저 offset table을 만들어야 합니다. offset 테이블은 percpu 주소를 unit 별 가상 주소로 변환해주는 offset을 저장합니다.
Line 15에서는 내부적으로 pcpu_psetup_first_chunk 함수를 호출합니다.
Line 20~22에서 unit 별 오프셋을 계산하여 테이블에 저장합니다.
이렇게 per_cpu_offset이 완성되었다면, percpu 변수에 접근하는 매크로들을 사용할 수 있습니다. static하게 할당된
percpu냐 dynamic하게 할당된 percpu냐에 따라 사용하는 매크로가 다릅니다.
static하게 선언된 percpu는 아래의 매크로에 나온 것 처럼 per_cpu을 사용합니다. 해당 매크로는 static한 percpu 변수의 심볼과 아까 초기화하는 과정을 살펴본 offset 테이블을 통해 chunk 내의 unit의 가상 주소를 넘겨줍니다.
dynamic하게 선언된 percpu 변수는 alloc 마지막 부분에서 __addr_to_pcpu_ptr을 통해 percpu 주소 저장했었습니다. 이 값을 가지고 percpu 변수에 접근하려면 아래의 매크로를 사용합니다.
percpu 주소는 offset 테이블에 저장된 값을 이용하면 쉽게 원하는 unit의 가상 주소를 얻을 수 있습니다.
이렇게 하여 새롭게 리뉴얼된 percpu에 대해 알아보았습니다. 해당 서브시스템은 허태준님이 개발을 하셨고, 제 첫 패치가 올라간 서브시스템이라 제에게는 여러 의미를 가지고 있습니다. 이 글을 읽은 후, 최신 버전의 percpu를 살펴보시는 데에 도움이 되었으면 합니다.