Memory Allocator 동작 방식

ref

사전지식

하드웨어 관점에서 페이지 접근

CPU는 페이지테이블 레지스터(cr3, ttbr)를 통해 메모리에 접근해야하고, 초기 페이지 테이블이 물리메모리로 직접 매핑(identity mapping)되어있기 때문에 어셈블리 명령어로 접근하면 사용할 수 있다.
부트로더가 커널을 부팅하면서 현재 메모리 정보(예약, 사용중인, 사용가능한)를 커널에 넘겨준다.

CPU가 어떤 메모리를 접근할때 MMU를 통해서 가상메모리로 물리메모리에 접근하는데, TLB 라는 캐시에서 miss 된 경우 물리메모리에 있는 page table 을 여러번 접근하여 주소를 찾아온다.

  • 당연히 페이지 테이블을 접근하는 레지스터(cr3, ttbr)에는 물리주소가 저장되어 있다.

7f926d30-9ba9-4d26-93bf-6eab7dbe6e6f
7f926d30-9ba9-4d26-93bf-6eab7dbe6e6f

만약 페이지테이블에 주소가 매핑되어있지 않으면 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를 호출해서 물리페이지를 할당받게 된다.

9706ff4d-0e3d-4b07-890f-5cddf792d773
9706ff4d-0e3d-4b07-890f-5cddf792d773

  • 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를 차지하도록 만들기도 한다.

ccf87a93-6cb3-4a97-8e8b-9d26e17f8045
ccf87a93-6cb3-4a97-8e8b-9d26e17f8045

하나의 캐시에서는 슬랩이 전부 꽉찬 슬랩, 일부 객체만 할당된 슬랩, 완전히 빈 슬랩으로 나뉘어 연결리스트로 관리된다.
커널이 객체를 할당하려할 때 부분슬랩과 빈 슬랩이 없는 경우에만 Buddy System 을 통해 PAGE SIZE * N 단위로 물리적으로 연속된 페이지를 슬랩으로 할당받게 된다.

04272b69-2271-4067-8ff2-e6635103e29d
04272b69-2271-4067-8ff2-e6635103e29d

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는 다음 노드를 가리키도록 하면 돼서 쉽게 할당이 가능하다. (+ 할당 관련 메타데이터 업데이트)

fb510c3a-056f-476d-809e-a02fe9818b3f
fb510c3a-056f-476d-809e-a02fe9818b3f

활성화 슬랩을 다 채웠다면 kmem_cache_cpu.partial 에서 slab 을 하나를 꺼내 활성슬랩으로 가져온다.

kmem_cache_node

kmem_cache_cpu.slab과 kmem_cache_cpu.partial 에 남은 자리가 없다면 사용된다. 여러 코어가 하나의 노드를 공유하는 구조이기 때문에 접근 시 lock을 걸고 접근하게 된다.
numactl -H 로 노드 구조를 확인할 수 있으며 그림에서는 core 4개가 하나의 numa node를 같이 사용한다.

83f14e8b-f197-410e-9157-ecbae2feb9e7
83f14e8b-f197-410e-9157-ecbae2feb9e7

node.partial 은 새로운 할당을 위해 어떤 core도 관리하고 있지않은 slab이기 때문에 할당하려고하는 core가 락을 잡고 선점해서 가져간 후 앞으로 해당 슬랩을 사용하게된다.
어차피 물리메모리의 빠른 할당만을 위해 kmem_cache_cpu로 관리하는 것이기 때문에 어떤 cpu가 슬랩을 가져가도 상관없다.

f14c0a68-3f3c-4565-9e8b-5eaf1e070160
f14c0a68-3f3c-4565-9e8b-5eaf1e070160

결국 할당은 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

ESC
Type to search...