Ashish Panwar (Indian Institute of Science), Aravinda Parasad†

• Abstract

  Virtual to physical translation overhead는 성능에 큰 영향을 끼치는데, Huge Page를 통해 완화할 수 있음.

  그러나 Memory Fragmentation이 문제였는데 unmovable page는 fragmentation과 overhead를 발생시킴

  Illuminator는 unmovable page 추적하면서 효과적으로 처리할 것

• Introduction

  TLB Scaling 한계로 Memory Capacity 못따라간다. Huge Page는 TLB에 대한 요구조건과 miss율을 낮출 수 있다.

  그러나 CPU Latency가 증가하는 문제로 인해 현실적이지 않았음. (Page Fault, Compaction 등)

  기존에 Memory fragmentation의 영향은 없다는 학계의 믿음과는 대조적으로 이게 큰 영향을 끼치고 unmovable page가 주요 원인임

  최소한 long-running system의 context에서는 그럼

  • fragmentation via pollution
  • LIU(Latency-Inducing unsuccessful) Migration → 실패 latency

• Motivation

  Address Translation overhead 줄이고 효율적으로 쓰려면 Huge page 활용하면 좋음

  OS 전략은 첫째로 contiguous memory pool을 booting때부터 reserve 해 놓는 건데, flexible 하지 못해서 실용성 적음

  혹은 Transparent Huge Pages(THP)인데, OS가 알아서 huge page locate하고 관리하는 것 같은데

  System run-time 길어질 수록 fragmentation 증가하면서 효율 떨어짐. real world에서도 THP로 인한 overhead가 많이 언급됨.

  Illuminator는 THP를 효과적으로 쓸 수 있도록 할 것 임

• Memory Management Background

  • Unmovable pages

    페이지 mobility는 reference management structure에 의존하는데, user virtual address 공간은 page table과 object로 구성됨

    반면 kernel address 공간은 physical memory에 directly mapping되어있는데 reference 추적이 안되고 unmovable함

  • Memory allocation

    application의 요청이 있을 때 page fault가 발생하면, 후속 메모리 할당은 buddy allocator가 하는데, 큰 page 공간을 우선으로 공간 확보하려 함

    그러나 그게 안되면 더 큰 page size여도 baseline page(4KB) 단위로 할당해버려서 2MB size의 memory block 단위로 처리할 때 pollution이 생김

  • Read-Copy-Update (RCU)

    많은 서브시스템은 RCU 동기화 방식의 slab allocator를 쓰는데, 원본은 그대로 둔 채 복사본을 만들고 처리함. 그러다 grace period가 지나서

    원본이 참조되지 않을 때까지 기다렸다가 원본을 제거하는데, unmovable 상태가 발생함

  • Fragment migration 기술

    unmoble하면 allocation에 실패할 수도 있으니 많은 서브 시스템은 compaction같은 avoid & recover scheme 사용함

    얘네는 주로 movable, unmovable 두 개 region으로 나누어서 비슷한 방식으로 관리하는데 page-block 단위로 짤림

    근데 특정 영역에 메모리가 모자르면 fallback이 생기는데 이것 때문에 pollution이 발생하게 됨

    memory compaction 알고리즘은 migrate scanner(movable check)와 freepage scanner(free check) 두 개 포인터가 양 끝에서 돌면서 list를 구성함

  • fragmentation에 대한 자세한 분석

    virtual memory상에서 huge page 활용하려고 노력 많이 했는데, physical memory 어쩌지 못해서 한계 많았음

    • hybrid pageblock: movable/unmovable 이분적으로 구분되는게 아니라 page단위에서 혼합된 중간 상태
    • hybrid pageblock의 invisibility: 일반적인 subsystem은 hybrid pageblock에 대한 구분을 하지 않아서 최적화 안됨
    • fragmentation via pollution: 한 page만 unmovable해져도 전체 pageblock에 영향을 끼침, fallback 당시엔 list 끝에 있어도 head로 shift됨

  • LIU migration

    LIU migration은 전체 성공에 대한 사전 점검 없이 수행되기 때문에 unmovable 만나면 overhead가 큼: 하나만 있어도 해당 page block 크기의 latency

    현재 커널 design은 LIU migration이 효과적이라고 여기는데, pageblock보다 작을 때 얘기고, THB에서는 문제가 될 수 있음

  • Measuring fragmentation

    unmovable page의 분포가 중요함. unmovable page수가 fix되어있을 때 sparse하면 더 많은 pageblock에 영향을 끼칠 수 있음

    prior work에서는 fragmentation 수준을 측정하기 위해 FMFI를 썼는데, unmovable이 고려되진 않아서 unmovability index를 제안함

    2GB 시스템 예시로, 950개 pageblock이 있는데, hybrid pageblock이 664개였고, 대부분 50개 미만의 부분적인 unmovable만 있었음

  • Delayed reclamation

    slab allocator는 grace period 지나도 즉시 deferred object를 회수하지는 않음. (RCU queue 순위, side-job로써 throttling, kernel thread preemption)

    그래서 slab consumption 증가하고 fragmentation 악화됨. 리눅스 기본 slab alloc_pages 보다는 Prudence쓰면 좀 더 완화됨

  • Large memory large problems

    예상과 달리 LIU migration에서 같은 unmovable index상에서 memory size 커질 때 execution time 늘어지는 현상 발견

    SPEC2006 milc 사용해서 측정했는데, 할당을 엄청 적극적으로 하는 workload라서 fragmentation 가속화하기 위한 목적임

    같은 index(비율)이라도 절대적 hybrid-pageblock 개수는 증가하는데, kernel control이 특정 값으로 관리하는 비동기 compaction에서는 큰 차이가 없으나

    (fragmented든 non-fragmented든 memory size에 관계 없이 constant함. fragmented가 높긴 하지만)

    동기식 compaction의 경우에는 memory size에 따라 증가함. page fault 발생 시 stall 시간이 늘어지는 경우가 많아서 그런 듯

• Illuminator design and implementation

  huge page 잘쓰려면 OS는 fragmentation via pollution 줄이고 LIU migration 없애야 함 → slab memory 최소화 필요해서 prudence memory allocator 사용

  • Illuminator는 enhanced buddy allocator를 쓸거고

    일반적으로 movable에서 처리되는 user 공간에서의 할당과 unmovable 영역에서 처리되는 kernel 공간에서의 할당 사이에 Hybrid block을 독립적으로 두고 관리할 것

    Prudence는 deferred object를 적절히 reclaim하는 방식으로 동작하는데 kernel이 alloc_pages 호출을 최소화 하도록 하는 역할

  • page block은 movable, unmovable, hybrid로 세 가지를 색으로 구분

    unmovable pageblock에 빈 공간 없을 때 unmovable 요청 있으면, movable에서 갖다 쓰는게 아니라, movable에서 일부를 hybrid로 전환하고 거기서 쓰는 거임

    관리된 steal 방식이라 볼 수 있고 결과적으로 better clustering이 목표

  • migrate scanner는 page migration 관련 점검할 때 hybrid pageblock은 건너 뜀 → hybrid는 room을 남겨놔서 fallback 발생을 방지하고자

  • Reclaim: slab 할당 끝나거나 hybrid pageblock이 free가 될 수 있는데, 이후엔 movable로 관리해야함. 근데 바로바로 reclaim은 monitor overhead 있음

  • huge page 할당의 susceptibility

    migrate scanner랑 freepage scanner 두 개 포인터로 compaction하는 기준 linux에서는 hybrid 위치 따라서 결과 달라짐

    migrate scanner가 hybrid 만나면 충분한 공간 탐색을 못해서 그런건데, illuminator는 hybrid는 skip하고 탐색하기 때문에 괜찮음

  • timely reclaim: prudence는 각 slab cache에 대한 latent cache가 있고, grace period 정보를 갖고 slab allocator에 제공하는 RCU와 결합해서 grace period 기반 회수 가능

• Evaluation: illuminator 자세한 성능 얘기

  • default huge page promotion rate 사용: 1.6MB/s (khugepaged)
  • compaction cost 측정: Gorman의 cost-theoretic model ; Cost_mc
  • 정량적 fragmentation 완화 기술 성능 측정하기 위해: stress-highalloc, standard benchmark, 근데 3GB 까지만 지원
  • illuminator는 not fragmented에선 Linux 기본이랑 비슷한데, fragmented에선 3.4x huge page 할당했고, Cost_mc는 80까지 줄임
  • 벤치마크가 3GB까지만 쓸만해서, synthetic benchmark를 써서 3단계 fragmentation 만들어서 평가함.
  • unmovability index: moderate(0.25), high(0.5), critical(0.75); hybrid pageblock 비율
  • VM에선 guest에 적용할 때 효과 더 좋음. (물론 guest와 host 둘 다에 적용할 때 제일 좋음)
  • 왜냐면 guest는 address translation overhead가 더 크고(mcf 빼고), asynchronous compaction은 큰 영향 없는데, host는 async만 영향 받고, guest는 둘 다 받는다고
  • Discussion: Unmvable page는 GP OS에 다 있고 page table이나 DMA page 같은게 주로 unmovable함. large memory workload에서 page table 크기가 몇 GB 되기도 함