Memory Allocator 동작 방식
ref
사전지식
하드웨어 관점에서 페이지 접근
CPU는 페이지테이블 레지스터(cr3, ttbr)를 통해 메모리에 접근해야하고, 초기 페이지 테이블이 물리메모리로 직접 매핑(identity mapping)되어있기 때문에 어셈블리 명령어로 접근하면 사용할 수 있다.
부트로더가 커널을 부팅하면서 현재 메모리 정보(예약, 사용중인, 사용가능한)를 커널에 넘겨준다.
CPU가 어떤 메모리를 접근할때 MMU를 통해서 가상메모리로 물리메모리에 접근하는데, TLB 라는 캐시에서 miss 된 경우 물리메모리에 있는 page table 을 여러번 접근하여 주소를 찾아온다.
- 당연히 페이지 테이블을 접근하는 레지스터(cr3, ttbr)에는 물리주소가 저장되어 있다.
만약 페이지테이블에 주소가 매핑되어있지 않으면 Page Fault가 발생하고, 커널에서 연결해둔 핸들러가 호출되며 유효한 VA 주소인지 판단 후 demand paging (PTE에 buddy allocator를 통해 얻은 물리주소 매핑) 을 하는게 일반적이지만 잘못된 접근으로 판단되면 진짜 Page Fault (SIGSEGV) 가 발생한다.
당연하게도 초기엔 핸들러가 없어서 demand paging 없이 Page Fault 예외만 발생한다.
DMA
CPU가 관여하지 않고 하드웨어가 메모리에 직접 쓰게 만드는 방식인데, DMA는 페이지테이블 레지스터가 없어서 가상주소를 사용할 수 없기 때문에 CPU에서 처음 세팅할때부터 물리주소로 알려줘야한다.
CPU가 가상메모리에서 사용하는 MMU 처럼 DMA를 위한 IOMMU 라는 장치가 있기 때문에 메모리를 할당 후 장치가 사용할 수 있는 DMA를 위한 메모리주소로 변환하고 장치에게 넘겨주는 형태이다.
IOMMU가 없는경우엔 물리메모리와 같은 주소를 사용하게 된다.
void *buf;
dma_addr_t dma_addr;
buf = kmalloc(4096, GFP_KERNEL);
if (!buf) return -ENOMEM;
// 이땐 가상주소로 접근함.
memcpy(buf, data, 4096);
// device가 사용할 DMA 주소로 변환. (IOMMU)
dma_addr = dma_map_single(&pdev->dev, buf, 4096, DMA_TO_DEVICE);
if (dma_mapping_error(&pdev->dev, dma_addr)) {
kfree(buf);
return -EIO;
}
// device에 dma_addr 전달
program_dma_engine(dma_addr, 4096);
// DMA 완료를 기다림
wait_for_completion(...);
dma_unmap_single(&pdev->dev, dma_addr, 4096, DMA_TO_DEVICE);
kfree(buf);
User Space
프로세스 실행까지
일반적으로 프로그램을 실행할 때 fork()로 child task를 만들고, child가 execve()를 호출하게 된다.
execve는 현재 태스크의 user address space를 새로운 실행파일의 space로 교체하는 작업을 하는데 이 과정에서 리눅스 기준 load_elf_binary() 함수에서 생성하는 vm_area_struct 구조체에 가상주소 범위에 대한 정보가 담긴다. (용도, 권한 등)
struct vm_area_struct {
unsigned long vm_start;
unsigned long vm_end;
/* read/write/execute/shared 등의 속성 */
vm_flags_t vm_flags;
/* 이 VMA가 속한 프로세스 주소 공간 */
struct mm_struct *vm_mm;
/* file-backed mapping이면 연결된 파일 */
struct file *vm_file;
/* 파일에서 어느 offset에 해당하는지 */
unsigned long vm_pgoff;
...
};
페이지 테이블은 커널영역을 얕은복사로 만들고, 유저영역을 비워놓은 상태로 프로세스의 컨텍스트에 저장된다.
이후 fork() → execve() 가 호출되면서 이 테이블을 cpu의 페이지테이블 레지스터로 교체하게되며 프로세스가 실행된다.
task_struct
│
└── mm
│
mm_struct
│
├── VMA들
│ ├─ .text
│ ├─ .data
│ ├─ heap
│ ├─ stack
│ └─ mmap 영역
│
└── pgd
│
Top-level Page Table
테이블이 전부 비어있기 때문에 process code 실행 등 매핑이 안되어있는 메모리에 접근할 때 TLB miss → PageTable lookup → #PF 가 발생하게 되면서 커널의 핸들러로 들어와서 demand paging 이 진행된다.
이 demand paging 때 Buddy System에서 물리메모리를 할당받아 페이지테이블에 연결해줄 수 있게되는 것이다.
.bss 영역 같은 static 영역은 프로그램 이미지의 일부라서 로더가 Program Header를 파싱할 때 VMA에 기록하기 때문에 일반적으로 처음부터 크기가 정해지고 바로 사용할 수 있게된다.
동적 메모리 할당
malloc 과 같은 동적 메모리는 프로그램을 작성할 때 라이브러리 헤더를 include 하고, 함수 호출로 힙메모리를 할당받게 되는데 이 영역은 라이브러리에 구현된 allocator 를 통해 할당받게 된다.
하나의 시스템 안에는 다양한 라이브러리가 있고 같은 라이브러리도 버전이 달라질 수 있기 때문에 다양한 allocator가 존재한다고 볼 수 있다. 하나의 프로세스 안에서도 여러 라이브러리를 링크하면 여러 allocator가 동시에 존재할 수 있게된다.
당연하게도 allocator는 자기가 직접 관리하는 영역을 내준 것이며 관리하는 방식도 다르기 때문에 호출한 할당함수에 대응되는 해제함수를 사용해야한다.
| allocator | 핵심 관리 방식 | 가장 중요한 아이디어 | 한 줄 요약 |
|---|---|---|---|
| glibc malloc | chunk + tcache + bins + arena | 가변 크기 chunk를 여러 free list로 분류 | 빈 chunk를 크기별 bin에 넣어 재사용 |
| jemalloc | arena + extent + slab + bitmap + tcache | size class별 slab을 체계적으로 관리 | 큰 extent를 size-class slab으로 쪼개 관리 |
| TCMalloc | per-CPU cache + CentralFreeList + Span + PageHeap | CPU별 free object cache | CPU마다 객체를 쌓아두고 중앙에서 batch refill |
| mimalloc | heap + page + size class + 여러 free list | page마다 free list를 잘게 분산 | 작은 page-local freelist를 아주 많이 만들어 contention을 분산 |
이 함수들을 사용해서 힙 메모리를 할당하면 allocator들이 관리하게 되고, 관리하는 메모리를 전부 다 사용한 경우 mmap() 이나 brk() 함수 호출로 커널에 추가 가상메모리 할당을 요청하게 된다.
정확히 말하면 커널이 VMA를 수정해주는 것이고, 다른 VMA와 마찬가지로 PF가 발생할 때 물리메모리에 매핑된다.
brk(): .bss 영역 이후에 있는 heap 영역을 연속적으로 확장시키는 함수mmap(): 임의 위치에 독립적인 새 mapping을 만드는 방식. VMA에 이미 매핑되어있지 않은 공간이라면 가능
Kernel Space
커널에서도 가상메모리 할당을 위해 slab/slub allocator를 사용하는데, 유저영역과 기본 개념은 동일하게 allocator가 미리 물리주소를 점유하고 있다가 커널이 요청할 때 나눠서 할당해주는 역할을 한다.
커널에서는 allocator 가 필요 없을것이라 생각될 수 있지만, 기본적으로 Byddy System은 페이지 기반으로 할당해주기 때문에 크기가 너무 크고, 물리메모리에 여러 스레드가 접근하면 락이 필요해서 느려질 뿐더러 커널오브젝트는 할당 해제가 잦아서 allocator가 훨씬 효율적이게 된다.
커널 영역에서는 #PF와 demand paging을 통해 물리페이지를 할당받는 것이 아니라 직접 page allocator를 호출해서 물리페이지를 할당받게 된다.
- Page Allocator(Buddy): 페이지 할당을 요청하면 실제 물리 주소의 페이지를 할당해준다.
- Slab Allocator: 할당받은 페이지를 slab 이라는 객체 단위로 쪼개서 사용한다. 커널은 같은 모양의 객체를 반복해서 사용하기 때문에 효율적인 메모리 관리를 위해 사용한다.
- Slub Allocator: 슬랩할당자는 복잡한 큐 기반 캐싱 방법을 사용하는데, 최신 리눅스(2007년 10월 이후커널)는 단순화하고 성능을 개선한 슬럽할당자를 사용한다.
Slab Allocator
커널은 기본적으로 특정 크기의 객체를 아주 많이 사용한다.
그렇기 때문에 같은 크기의 오브젝트를 연속된 공간에 넣어 관리가 쉽도록 만들었고 그것이 슬랩이라는 공간으로 부른다.
슬랩은 kmem_cache라는 구조체로 관리하는데 관리하는 커널객체의 크기별로 범용적인 kmalloc-128 같은 캐시가 N개 있기도 하고 UAF 같은 공격을 막기위해 특정 구조체 전용으로 만들어져 있기도 하다. (같은크기의 kmem_cache 가 하나가 아니라는게 중요)
꼭 같은 크기의 obj만 들어가는게 아니라 그냥 100byte를 범용적으로 만들고나면 가장 비슷한 크기인 kmalloc-128 로 할당하고 128byte를 차지하도록 만들기도 한다.
하나의 캐시에서는 슬랩이 전부 꽉찬 슬랩, 일부 객체만 할당된 슬랩, 완전히 빈 슬랩으로 나뉘어 연결리스트로 관리된다.
커널이 객체를 할당하려할 때 부분슬랩과 빈 슬랩이 없는 경우에만 Buddy System 을 통해 PAGE SIZE * N 단위로 물리적으로 연속된 페이지를 슬랩으로 할당받게 된다.
Slab allocator 구조
slab.c (array_cache), slab_def.h (kmem_cache), slab.h (kmem_cache_node), struct slab
정확한 구조를 보면 코어마다 사용하는 cpu_cache가 존재한다.
object가 재할당 될 때 이미 해제된 주소가 CPU코어의 L1 캐시에 남아있을 수도 있기도 하고, 공유 cache에서 가져오려면 lock이 필요하기 때문에 cpu_cache 에서 재사용을 우선시 한다.
kmem_cache별로 크기가 일정하기 때문에 크기는 신경쓸 필요 없이 entry에서 꺼내서 할당해주면 된다.
cpu_cache에 저장된 메모리주소를 this_cpu_ptr 같은 매크로로 접근하면 CPU코어번호 기반 주소로 변경되어 접근할 수 있다.
- 할당 순서:
array_cache→slabs_partial→slabs_free→new page
[ kmem_cache (ex. kmalloc-64) ]
├─ cpu_cache ─────> [ array_cache (per cpu) ]
│ void *entry[] # 최근 해제된 free object ptr 스택 (CPU별로 관리)
│ uint limit # 캐시 최대 크기. 초과되면 batchcount 단위로 kmem_cache_node에 반납
│
└─ node[] ────────> [ kmem_cache_node (per node) ]
├─ slabs_partial ────┐
├─ slabs_full ───────┼──> [ struct slab ] # from kernel 5.17
└─ slabs_free ───────┘ slab_cache
slab_list : kmem_cache_node 에 연결하기 위한 구조체
┌─────────────── freelist : 해제된 object 확인하기 위한 인덱스배열
[2][0][3][1] active : 사용중인 object 수
│ s_mem : 첫 object 시작주소
freelist[active] │
부터 free obj v
[obj:use][obj:free][obj:use][obj:free]
Slub Allocator
Slab, Slub, Slob은 커널메모리를 다른 구조로 관리하게되며, 작은 임베디드는 Slob, 최신 리눅스는 Slub Allocator 를 사용했었지만 커널 6.3 부터 임베디드는 TINY_SLUB 사용하며 리눅스 allocator는 SLUB 하나만 남아있다.
Slub Allocator 구조
위에서 설명했던 array_cache 처럼 kmem_cache_cpu에서 먼저 할당 후 부족하면 kmem_cache_node 라는 전역 슬랩관리 구조체에서 가져오도록 구현되어 있다.
node는 CPU 소켓에 가까운 메모리를 의미하는데, 멀티 CPU 시스템(서버)에서는 의미가 있지만 일반 PC같은 싱글 cpu에서는 커널 전체에서 공유하는 노드가 된다.
kmem_cache에서는 할당을 위해 슬랩을 관리하기 때문에 slabs_full(꽉찬 슬랩)은 관리하지 않고 partial이 된 경우만 관리를 시작한다.
slabs_free(빈 슬랩)은 일반적으로 page allocator에 반환되고, min_partial 값보다 적어진 경우에만 성능을 위해 리스트로 관리한다. (CPU slab에서 내려올 때 deactivate_slab()에서 min_partial로 판단함)
kmem_cache_cpu, kmem_cache_node
[ kmem_cache (ex. kmalloc-64) ]
├─ min_partial :
├─ cpu_slab ─────> [ kmem_cache_cpu (per cpu) ]
│ freelist : 현재 CPU가 바로 사용할 다음 free object pointer
│ slab : 현재 CPU가 바로 할당에 사용할 active slab 1개
│ partial : CPU가 예비로 들고 있는 partial slab list (optional)
│
└─ node[] ───────> [ kmem_cache_node (per node) ]
nr_partial : kmem_cache_node 에서 관리하는 partial 수 (>= min_partial)
partial ───────> [ struct slab ] ────> [ struct slab ]
freelist : 첫 free object 주소
inuse : 사용 중인 object 수
objects : 전체 object 수
[ call slab_address(slab) ] : slab의 시작 (커널의 가상주소)
│ *freelist
[obj0:use][free][obj2:use][free]
└── next ptr ──┘└─ next ptr ─> NULL
kmem_cache_cpu
kmem_cache_cpu.slab (활성화 슬랩)에 자리가 있는 경우 freelist의 주소를 반환해주고 freelist는 다음 노드를 가리키도록 하면 돼서 쉽게 할당이 가능하다. (+ 할당 관련 메타데이터 업데이트)
활성화 슬랩을 다 채웠다면 kmem_cache_cpu.partial 에서 slab 을 하나를 꺼내 활성슬랩으로 가져온다.
kmem_cache_node
kmem_cache_cpu.slab과 kmem_cache_cpu.partial 에 남은 자리가 없다면 사용된다. 여러 코어가 하나의 노드를 공유하는 구조이기 때문에 접근 시 lock을 걸고 접근하게 된다.
numactl -H 로 노드 구조를 확인할 수 있으며 그림에서는 core 4개가 하나의 numa node를 같이 사용한다.
node.partial 은 새로운 할당을 위해 어떤 core도 관리하고 있지않은 slab이기 때문에 할당하려고하는 core가 락을 잡고 선점해서 가져간 후 앞으로 해당 슬랩을 사용하게된다.
어차피 물리메모리의 빠른 할당만을 위해 kmem_cache_cpu로 관리하는 것이기 때문에 어떤 cpu가 슬랩을 가져가도 상관없다.
결국 할당은 cpu.slab(활성슬랩) → cpu.partial → node.paritial 순서로 할당된다.
메모리 해제
디버그 모드를 켜지 않는경우 full slab은 관리되지 않는다.
메모리를 해제하면 해제된 객체 메모리 주소를 가지고 slab 주소를 찾고, cpu.partial 또는 node.partial 리스트에 추가한다. 여기에서 중요한건 바로 직전에 해제했다고 하더라도 cpu.slab (활성슬랩) 으로 들어가는것이 아니라는 것이다.
void kfree(const void *object)
{
folio = virt_to_folio(object); // 객체 주소 → 그 주소가 속한 페이지(folio)
...
slab = folio_slab(folio); // 페이지 → struct slab (page에 오버레이)
s = slab->slab_cache; // 슬랩 → 어느 캐시 소속인지
slab_free(s, slab, ...); // 이제 이 슬랩을 __slab_free로
}
슬랩 확인하기
/proc/slabinfo 를 읽어보면 시스템에서 각 슬랩의 사용량을 확인할 수 있다. CPU마다 보여주는 상세 내역은 아니기에 참고정도만 한다.
bluejay:/ $ cat /proc/slabinfo
slabinfo - version: 2.1
# name <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <limit> <batchcount> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
zspage 37074 38398 56 73 1 : tunables 0 0 0 : slabdata 526 526 0
zs_handle 253555 261120 8 512 1 : tunables 0 0 0 : slabdata 510 510 0
dm_bufio_buffer-4 83 225 160 25 1 : tunables 0 0 0 : slabdata 9 9 0
dm_bufio_buffer-4 48 150 160 25 1 : tunables 0 0 0 : slabdata 6 6 0
dm_bufio_buffer-4 300 300 160 25 1 : tunables 0 0 0 : slabdata 12 12 0
...
kmalloc-rcl-128 2287 2464 128 32 1 : tunables 0 0 0 : slabdata 77 77 0
kmalloc-rcl-64 5606 5760 64 64 1 : tunables 0 0 0 : slabdata 90 90 0
kmalloc-8k 926 940 8192 4 8 : tunables 0 0 0 : slabdata 235 235 0
kmalloc-4k 5281 5288 4096 8 8 : tunables 0 0 0 : slabdata 661 661 0
kmalloc-2k 3462 3488 2048 16 8 : tunables 0 0 0 : slabdata 218 218 0
kmalloc-1k 5031 5056 1024 32 8 : tunables 0 0 0 : slabdata 158 158 0
kmalloc-512 10707 10816 512 32 4 : tunables 0 0 0 : slabdata 338 338 0
kmalloc-256 6312 6336 256 32 2 : tunables 0 0 0 : slabdata 198 198 0
kmalloc-192 7233 7308 192 21 1 : tunables 0 0 0 : slabdata 348 348 0
kmalloc-128 28682 31712 128 32 1 : tunables 0 0 0 : slabdata 991 991 0
kmalloc-64 284009 284544 64 64 1 : tunables 0 0 0 : slabdata 4446 4446 0
kmem_cache_node 356 704 64 64 1 : tunables 0 0 0 : slabdata 11 11 0
kmem_cache 324 480 256 32 2 : tunables 0 0 0 : slabdata 15 15 0
Comments