Making Huge Pages Actually Useful : Illuminator

Making Huge Pages Actually Useful : Illuminator

위 논문을 읽고 정리한 내용입니다.

Notion에서 보기 

---

Abstract

• huge page로 virtual-to-physical address translation overhead를 완화할 수 있다. 그러나 memory fragmentation 문제로 contiguous 한 mapping이 어려워 huge page를 실제로는 잘 사용하지 못했다.
  • huge page 사용시** spike : 갑작스러운 발생
  • 커널과 같은 unmovable page 처리 문제로 불필요한 memory management 작업이 수행되어 높은 CPU utilization이나 latency spike가 발생한다.
• 본 논문에서는 memory manager로 Illuminator를 제안한다.** page allocator : 모든 unmovable page를 tracking하는 기능을 제공한다.⇒ compaction cost를 99%까지 감소시키고, application performance를 2.3배까지 증가시키고, MySQL DB server에서 maximun latency를 30배까지 감소시켰다.
• ⇒ huge page allocation으로 인해 발생하는 cost를 줄여 효과적으로 huge page를 사용하게 한다.
• page allocator와 같은 다양한 서브시스템을 제공한다.

1. Introduction

• TLB 부족 → address translation overhead→ TLB miss를 감소시켜 page table lookup에 사용되는 CPU time을 최소화한다.
• ↔ memory fragmentation
• ⇒ huge page support 등장
• huge page 사용시 문제점ii) high kernel space CPU utilization⇒ 그래서 대부분의 DB server는 huge page를 사용하지 않고 있다.
• → 주요 원인 : OS의 unmovable page에 대한 poor handling
• iii) latency spike
• i) memory fragmentation
• huge page에 나타나는 performance anomalies의 주요 원인
  • fragmentation via pollution : unmovable page로 인해 memory contiguity가 불필요하게 polluted되는 현상
  • latency-inducing unsuccessful (LIU) migration : kernel이 huge page 할당을 시도하는 동안 polluted 영역에서 불필요하게 page를 migrate하는 현상
  • → fragmentation recovery cost 증가
• Illuminator (simple memory management framework)
  • Linux kernel에서 수정한다.
  • explicit하게 모든 unmovable page를 track한다.
  • → LIU migration을 제거한다.
  • LIU migration 없이 (불필요한 page migration 없이) memory compaction을 수행하여 cost-effective한 huge page 할당을 할 수 있게 한다.
  • page allocator가 효율적으로 unmovable page들을 클러스터링할 수 있게 하여 pollution으로 인한 fragmentation을 감소시킨다.
  • fragmentation을 완화하고 stressful한 조건에서도 application이 huge page의 이점을 사용할 수 있도록 한다.

2. Motivation

• 가상화 시스템에서의 address translation은 memory lookup을 6배 이상 수행해야 한다.→ huge page의 이점을 완전하게 활용하기 위해선 운영체제가 fragmentation을 효과적으로 완화시켜야 한다.
• → modern HW는 huge page utilization을 높여 native system과 virtualized system에서의 address translation 효율성을 비슷하게 만들었다.
• 운영체제가 huge page를 지원하는 HW를 leverage하는 방법Windows, OS X가 사용하는 매커니즘→ 이 방식은 flexibility가 떨어지고 application이 explicit하게 huge page를 요청해야 한다.Linux와 FreeBSD에서 사용하는 방식으로 huge page를 자동으로 할당한다.
• → 프로그램을 오래 실행시킬수록 THP로 인한 성능 이점이 떨어진다.
• ii) Transparent Huge Pages (THP)
• Linux는 libhugetlbfs 인터페이스를 제공하여 huge page 사용을 위해 시스템을 조정한다.
• i) 부팅시에 contiguous memory pool을 reserve한다.

Tales from the real world

• khugepaged 프로세스는 CPU cycle을 많이 소모하기 때문에 THP는 성능 저하의 원인이 된다. compaction이 자주 일어나서 kernel space CPU utilization을 증가시킨다.
• →그래서 실제로는 대부분 huge page를 disabled한다.
• 이러한 문제는 unmovalbe page에 대한 poor handling으로 인해 발생하는 것이다. 따라서 Illuminator는 THP가 실제로 long-running 시스템에서도 유용하게 사용될 수 있도록 한다.

3. Memory management background

3.1 Unmovable pages

• page의 mobility는 reference management structure에 의해 결정된다.→ 이러한 page들은 content를 copy하고 해당하는 참조를 업데이트 하여 migration을 수행할 수 있다. (movable)ii) kernel address space는 physical memory에 directly mapping된다. kernel virtual address에 상수를 더해 physical address로 변환한다.→ reference가 track되지 않아서 disk로 migrate되거나 swap될 수 없다.
• → 심각한 fragmentation을 유발한다.
• → inode와 같은 kernel object를 unmovable하게 만든다.
• **vm_mm : 프로세스의 memory descriptor를 가리키는 포인터 변수
• i) user virtual address space는 page table, vm_mm, vm_area_struct 등의 object로 관리된다.
• 즉, 커널 주소 공간이 사용하는 객체는 unmovable하다. (migration 불가능)

3.2 Memory allocation

• Linux의 basic memory allocation framework
•  
• kernel object는 slab allocator에 의해 할당된다.
  • buddy allocation
    • 가능한 적당하게 메모리 요청을 만족하도록 메모리를 여러 부분으로 나누는 메모리 할당 알고리즘으로 메모리의 크기를 절반씩 분할하면서 가장 잘 맞는 크기의 메모리를 찾는다.
    1. 요청한 메모리 크기보다 동일하거나 큰 2^ 블록을 찾는다.
    2. 적절한 크기의 메모리가 발견되면 프로그램에 할당한다.
    3. 적절한 크기의 메모리가 없다면 요청된 메모리 크기보다 큰 사이즈로 메모리 영역을 절반씩 자른다.
    4. 하한선에 도착하면 해당 메모리를 할당한다.
    5. 적당한 크기의 메모리 영역을 발견할 때까지 이 과정을 반복한다.
  slab cache에 의해 발생한 page들은 unmovable하다.
• slab cache는 buddy allocator의 alloc_pages를 통한 메모리 요청으로 채워진다.
• application 요청들은 buddy allocator에 의해 처리된다.이때 메모리가 fragmented된 상태라면 direct(synchronous) compaction을 수행한다.→ khugepaged 커널 스레드로 asynchronous compaction을 수행하여 background에서 baseline page들은 huge page로 promotion한다.
• → huge page 할당에 실패하면 kernel은 baseline page를 할당한다.
• → page fault 발생시 우선적으로 huge page를 할당한다.

3.3 RCU and deferred objects

• slab allocator를 사용하는 서브 시스템들은 Read-Copy-Update (RCU) synchronization 매커니즘을 사용한다.
  • Read-Copy-Update (RCU)
    • read 동작에서 블로킹 되지 않는 read/write 동기화 매커니즘
    • read 오버헤드가 거의 없다.
    • deadlock 이슈가 없다.
    • write 동작이 느리다.
• RCU에서 writer는 object를 update하기 전에 새로운 copy를 생성하고 old copy를 free하는 것을 지연시킨다.**grace period : 기존의 모든 reader에게 completion을 표시하는 것 / RCU작업을 수행하는 자료에 관련된 reader들의 처리가 완료됨을 보장할 수 있도록 대기하는 구간이다.
• → deferred object로 인해 unmovable memory footprint가 증가한다.
• → deferred object는 grace period 이후에 synchronization 매커니즘에 의해 재요청된다.

3.4 Fragementation mitigation technique

• unmovable page의 잘못된 배치는 영구적인 fragmentation을 초래하여 huge page 할당 실패의 원인이 된다.
• → current system은 fragmentation avoidance (anti-fragmentation) + recovery mechnism (memory compaction) 을 통해 fragmentation을 처리한다.

1. Anti-fragmentation
   • memory를 두 개의 disjoint 영역으로 분리하여 비슷한 할당으로 클러스터링한다.ii) movable (하위의 초록 네모)
   • i) unmovable (상위의 빨간 네모)
   • pageblock 단위로 파티셔닝 된다.
   • ** pageblock : huge page sized contiguous physical memory region
   • buddy allocator가 할당 요청 소스를 기반으로 region을 선택한다. (예를 들어 커널 요청은 unmovable region에서 서비스된다. )
   • region은 free memory 영역이 부족하면 다른 영역으로부터 pageblock을 가져올 수도 있다. (=fallback)
2.  
3. memory compaction (recovery from fragmentation)
   • migrate scanner는 한 쪽 끝에서 in-use movable baseline page 리스트를 가리킨다.
   • freepage scanner는 다른 쪽 끝에서 free baseline page 리스트를 가리킨다.
   • migrate scanner의 리스트에서 가져온 page는 memory contiguity를 회복하기 위해 freepage scanner의 리스트에 복사된다.

4. A detailed analysis of fragmentation

Hybrid pageblock

• movable pages + unmovable pages

 

• pageblock 4개 (P1~P4)
• (A) : P1과 P4에 free page가 남아있지 않은 상태에서 커널로부터 unmovable page에 대한 요청이 들어오면
• (B) : Linux 알고리즘은 movable 영역에 있던 P2를 unmovable 영역으로 가져온다. (fallback)
• → P2가 기존에 movable page를 가지고 있었다면 hybrid pageblock이 된다.

4.1 The invisibility of hybrid pageblocks

• anti-fragmentation 기반의 movable/unmovable 분류는 hybrid pageblock을 invisible하게 하여 movability를 stale하게 한다.
• subsystem은 movable pageblock과 unmovable pageblock만 있다는 가정을 두고 운영된다.→ 4.1.1~4.1.3과 같은 poor decision making을 초래한다.
• (커널은 hybrid pageblock 을 인식하지 못한다.)

4.1.1 Fragmentation via pollution

• fallback하는 동안 hybrid pageblock이 free list의 head에 위치함에도 불구하고 hybrid pageblock들은 allocaton / free cycle 주기동안 head에 없는 것처럼 여겨진다.
• → buddy allocator는 기존의 hybrid pageblock들을 인지하지 못하여 효율적으로 식별하거나 재사용할 수 없다.
• 위의 Figure 1에서 (C) → (D) 과정에서 P1의 polluted된다.(매 fallback마다 새로운 hybrid pageblock을 만드는 것이 최악)
• (E) → (F) 과정에서는 P4라는 새로운 hybrid pageblock을 만들어낸다.
• unmovable page로 인해 polluted(hybrid) pageblock은 huge page로 할당될 수 없다. 그래서 pollution으로 인한 fragmentation은 huge page 할당을 제한한다.
• ⇒ fragmentation via pollution (hybrid pageblock) → huge page allocation 방해

4.1.2 LIU migration (latency-inducing unsuccessful)

• page migration
  • 프로세스가 보는 virtual address를 바꾸지 않고 page의 물리적 위치를 바꾸는 것이다.
  • LIU migration : huge page를 할당하려고 할때 커널이 unmovable page로 인해 polluted된 영역에서 page를 불필요하게 migrate하는 것
  • 해당 메모리에 접근하려는 프로세스가 실행 중인 프로세서 근처에 있는 page를 이동시켜 메모리 접근 latency를 줄이기 위해 수행하는 작업니다.
  • sys_migrate_pages() : 프로세스의 page는 다른 프로세스로 relocate될 수 있다.
  In kernel use of migrate_pages()
  1. LRU에서 page를 제거한다.**LRU = 페이지 교체 알고리즘 / least recently used
  2. isolate_lru_page()를 호출하여 migrate하려는 page의 리스트를 만들고 page들을 리스트로 옮긴다. 그리고 page reference 를 증가시켜 migration 중에 page가 버려지는 일이 없도록 한다.
  3. new_page_t : old page를 올바른 새로운 페이지로 할당하는 방법을 설정한다.
  4. migrate_pages() : migration을 수행하기 위해 호출된다. 이동시키려는 각 페이지에 맞는 새로운 페이지를 할당하는 함수를 호출한다.
  How migrate_pages() works
  • migration 시점에 page에 대한 모든 참조가 제거되어 있으면 해당 페이지를 이동시킨다. 해당 페이지는 이미 isolate_lru_page()에 의해서 LRU에서 제거되고 refcount가 증가되어 있는 상태이다.
  • steps
    1. migrate할 페이지를 lock한다.
    2. 페이지의 수정 사항이 디스크로 write back이 완료되었는지 확인한다.
    3. 이동할 새로운 페이지를 lock한다.
    4. 해당 페이지를 참조하는 모든 page table을 migration entry로 바꾼다.
    5. → page의 mapcount를 감소시킨다. 그 결과 mapcount가 0이라면 해당 page를 migrate하지 않는다. 해당 page에 접근하려는 모든 유저 스페이스 프로세스들은 page lock이 풀릴 때까지 대기한다. i_pages lock으로 기다리는 모든 프로세스들의 spinlock을 차단한다.
    6. page의 refcount를 확인하고 page에 대한 참조가 남아있다면 migrate를 하지 않는다.
    7. radix tree를 확인하고 해당 페이지에 대한 포인터가 없다면 migrate를 하지 않는다.
    8. 준비된 새로운 page에 대한 포인터를 radix tree에 추가한다.
    9. old page에 대한 reference count는 감소하고, 새로운 page에 대한 reference count가 증가한다.
    10. i_pages lock을 없애 mapping을 위한 lookup이 다시 가능해진다. spinlock을 가지고 있던 프로세스들은 새로운 page lock을 sleep하며 기다린다.
    11. page content가 새로운 page에 복사된다.
    12. 남아 있는 page flag도 새로운 page에 복사된다.
    13. old page의 플래그를 clear시켜 해당 page가 더 이상 정보를 담고 있지 않다는 것을 표시한다.
    14. 새로운 page에 대하여 대기중인 writeback을 수행한다.
    15. page lock을 olde page에서 new page로 옮긴다. 그러면 해당 page lock에 대기하고 있던 프로세스들은 page fault를 다시 수행하고 new page에 도달한다.
    16. 새로운 page는 LRU로 이동되고 swapper에 의해 스캔될 수 있는 상태로 돌아간다.
• compaction을 하는 동안 kernel은 migrate scanner로 만나는 모든 movable pageblock의 page들을 migrate한다.ex) Figure1의 (F) 상태
• ⇒ LIU migration
• 이때, movable pageblock은 항상 비어있을 수 있다는 최적의 상황을 가정한다. 그러나 movable pageblock에 hybrid pageblock들이 많이 있을 수 있다.
• LIU migration은 불필요한 CPU cycle을 소모한다.kernel은 pageblock으로부터 511개의 page를 migrate 하면서 huge page 할당에 2.5 millisecond latency를 추가한다.
• (이러한 latency는 많은 연속적인 pageblock들이 hybrid인 경우 더 악화되고 huge page 할당이 실패할 수도 있다.)
• ex) baseline page migration은 5ms이고 unmovable page 1개를 포함하고 있는 hybrid pageblock의 경우,
• page 내용을 복사하고 compaction을 수행하는 것은 critical operation을 포함한다.hybrid pageblock이 시스템에 많이 존재하는 경우 커널은 huge page 할당의 유용성을 확인하지 않고 huge page 할당 요청에 응답하면서 page migration을 수행하기 때문에 LIU migration은 불필요한 오버헤드가 된다.
• → migrate된 page가 다른 CPU core의 TLB에 mapping될 때 TLB invalidation도 필요하다.
• 현재 커널 설계는 sub-pageblock sized allocation으로 long-ter fragmentation을 방지하기 때문에 LIU migration이 문제가 아니라고 가정한다.→ 이러한 migration이 fragmentation을 줄이는데 바람직하다고 생각하지만 THP 할당에서는 free pageblock을 만들어내지 않기 때문에 적용할 수 없는 원리이다.
• ex) 64KB 할당 요청은 hybrid pageblock으로부터 page migration을 하여 서비스 될 수 있다. 또한 이후의 할당에 사용될 수 있는 다른 작은 block들을 free한다.
• 따라서 THP에서는 LIU migration으로 인해 발생하는 huge page 단위의 long-term fragmentation을 방지할 수 없다.
• Measuring fragmentation : unmovability index
  • 전체적인 fragmenation 상태는 unmovable page의 분포에 따라 결정된다.
  • sparsely polluted pageblock은 고정된 unmovable memory로 인해 높은 fragmenation을 초래한다.
  • 또한 적은 unmovable page를 가진 pageblock은 LIU migration이 많이 발생하기 때문에 compaction 오버헤드가 크다.
  • FMFI는 unmovable page를 고려하지 않기 때문에 fragmenation recovery의 어려운 정도를 측정할 수 없다.
  • 본 논문에서는 unmovability index를 사용한다.ex) unmovability index = 0.5 : total pageblock의 절반이 적어도 하나의 unmovable page를 포함하고 있다는 것을 의미한다.
  • → unmovable page로 polluted된 총 pageblock의 비율을 나타낸다.

4.1.3 Experimental study of Linux fragmentation

• Linux에서 fragmenation via pollution과 LIU migration은 빈번하게 발생한다.664 hybrid pageblock 중 624개의 pageblock은 50개 이하의 unmovable page를 갖는다. 그 중 24개의 pageblock은 오직 하나의 unmovable page를 갖는다.
• ex) 약 950 pageblock을 가진 2GB 시스템에서 커널 소스 편집은 몇 개의 unmovable page를 포함하는 hybrid pageblock 664개를 만들어 낸다.
• sparsly polluted pageblock → memory compaction overhead를 증가시킨다.

4.2 Delayed reclamation of deferred objects

• reclamation
  • 사용하지 않는 메모리를 확인해서 필요로 하는 다른 곳에 재할당하는 것
  • 리눅스에서 특정 프로세스에 할당되어 있지 않은 메모리는 주로 커널이 캐시로 사용한다.
  • 그러나 계속해서 캐시로 사용하고 reclamation을 하지 않으면 가용 메모리가 줄어든다. 그래서 reclamation을 통해 page cache 등을 반환해야 한다.
  • cache 메모리를 회수하는 것이기 때문에 시스템 성능에 영향을 미치지 않는다.
  • 프로세스로부터 메모리 할당 요청이 들어오면 커널은 FreeList에서 사용 가능한 메모리 영역을 찾아서 반환하는데 이때 사용 가능한 메모리 영역이 없다면 사용하고 있는 메모리 중 반환할 수 있는 메모리가 있는지 찾아서 반환해준다.
• 기존의 slab-based allocator에서 deferred object는 grace period 완료 직후에 즉시 재요청되지 않았다.→ queue의 끝에 있는 object의 reclamation은 지연된다.ii) deferred object의 reclamation을 담당하는 커널 쓰레드가 preemption될 수 있다.
• ii) RCU는 slab allocator의 상태와 상관 없이 application의 간섭을 피하기 위해 deferred object의 reclamation 비율을 조절한다.
• i) RCU 큐에서 deferred object를 관리하고, 각 object의 등록된 callback function을 통해서 재요청한다.
• deferred object는 reclaim되기 전까지 slab allocator에 보이지 않기 때문에 재사용될 수 없다.→ slab page는 unmovable page이기 때문에 alloc_pages 호출은 fragmenation via pollution을 증가시킨다.
• **alloc_pages : 페이지 단위로 메모리를 할당하는 API / 2^order만큼 페이지를 할당한다.
• → deferred object의 reclamation이 지연되는 것은 slab 소비를 증가시킨다. deferred object가 많이 대기중임에도 불구하고 새로운 할당 요청을 받아들여 slab allocator에 많은 slab cache를 채우게 된다.
• Illuminator는 hybrid pageblock을 조금만 만들어서 fragmentation via pollution을 방지한다.
•  
• 리눅스에서 deferred object reclamation 지연은 alloc_pages 호출 횟수를 증가시키고 이것은 hybrid pageblock을 많이 발생시켜 결국에는 fragmenation via pollution을 증가시킨다.
• Prudence (dynamic memory allocator)은 grace period 완료 직후에 즉시 deferred object recalamation을 한다.⇒ 따라서 본 논문에서는 slab allocator를 Prudence로 대체한다.
• → hybrid pageblock 개수를 리눅스보다 35% 감소시킨다.

4.3 Large memory large problems

• 메모리 크기가 커질수록 LIU migration으로 인한 성능 저하가 심해진다.
• large memory일수록 더 많은 hybrid pageblock을 가지고, small memory system과 비슷한 unmovability index에 도달하는데 더 오랜 시간이 걸린다.
• (large memory일수록 fragmentation via pollution에서 회복하는 시간이 오래 걸린다.)
• asynchronous compaction을 하면 fragmented case의 경우에도 실행 시간을 일정하다.→ 커널은 asynchronous compaction 비율만 제어하기 때문에 memory가 크면 실행 시간과 실행 시간이 지연이 더 크게 발생한다.
• 반면에 sychronous compaction은 page fault 발생시 application을 잠시 멈추기 때문에 실행시간이 길어진다. (hybrid pageblock의 수를 증가시키는 synchrnous compaction의 비율은 제한을 받지 않는다.)
• 이러한 문제를 해결하기 위해서 synchronous compaction rate도 제어하는 policy-based decision을 해야 하지만 본 논문에서는 다루지 않는다. (synchronous/asynchronous 모두에서 compaction 매커니즘을 효율적으로 하는 방법을 제안한다)

4.4 Impact of fragmentation in virtualized systems

• 가상화 시스템에서 guest OS는 host OS와 비슷한 알고리즘으로 fragmentation을 처리한다.
• → memory fragmentation이 발생했을 때 guest와 host 모두에서 LIU migration이 발생하기 때문에 가상화 환경에서 fragmentation이 더 심각하다.
• guest에서 huge page의 이점이 host에서보다 높기 때문에 guest memroy fragmentation의 영향은 host memory fragmenation 보다 더 안 좋은 영향을 미친다.
• 그러나 host에서도 fragmentation이 상당한 영향을 미치기 떄문에 guest와 host 모두에서 fragmenation을 처리해야 한다.

5. Illuminator design and implementation

• huge page를 지원하기 위해서 운영체제는 fragmentation via pollution과 LIU migration을 제거해야 한다.
• Illuminator는 간단한 디자인으로 hybrid pageblock을 explicit하게 관리하여 huge page 지원에 필요한 요건을 충족할 수 있다.
• 또한 slab cache 소비를 최적화하기 위해 Prudence memory allocator를 사용한다.

5.1 Explicit management of hybrid pageblocks

• Three-way partitioning based anti-fragmentationii) movable - greenmemroy management subsystem에게 mobility를 보여준다.
• 각 partition은 지정된 type의 page만 가지고 있는다.
• iii) hybrid - yellow
• i) unmovable - red

5.1.1 Mitigating fragmentation via pollution

• Illuminator에서 buddy allocator는 Linux와 마찬가지로 해당하는 영역에 먼저 메모리를 할당하지만 다른 영역이 해당 영역으로부터 pageblock을 가져가도록 하기 전에 hybrid pageblock을 할당한다.
• fallback이 발생하면 pageblock 내부의 base page들이 모두 free된 경우에만 다른 영역으로 가져가질 수 있다.
• 즉, Illuminator는 yellow영역에 있는 hybrid pageblock이 불필요하게 pollute되는 것을 방지한다. (hybrid pageblock 발생을 최소화하기)
• Illuminator의 memory allocation→ hybrid pageblock이 된 것이 계속해서 fallback을 서비스할 수 있는 동안 새로운 pageblock은 hybrid로 만들지 않는다.
• ⇒ hybrid pageblock 생성 개수를 감소시킬 수 있다.
• unmovable 영역에 있는 pageblock들이 free page를 가지고 있지 않은 상태에서 unmovable page 요청이 들어오면 movable 영역에 있는 pageblock을 fallback하고 해당 pageblock을 yellow 로 만든다.

5.1.2 Eliminating LIU migration

• Illuminator는 huge page related compaction을 base page related compaction과 분리하여 THP related LIU migration을 제거한다.
• huge page 할당 중에는 hybrid pageblock을 피한다.freepage scanner도 위와 같은 방식으로 free page를 수집하는 동안 hybrid pageblock을 건어뛴다. hybrid 영역의 free space는 소진되기 않기 때문에 이후에 발생하는 unmovable 할당 → movable 할당을 방지할 수 있다.
• migrate scanner가 migrate하기 전에 각 pageblock의 색깔을 확인하고 만약 pageblock이 hybrid (yellow)라면 전체 page block range (512 contiguous baseline page / huge page)를 건너뛴다.

5.2 Reclaiming pageblocks from the hybrid region

• hybrid pageblock은 movable로 바뀔 수 있다.
• — memory가 free될 때, slab allocator가 buddy allocator로 모든 page를 반납할 때
• Illuminator는 효율성을 위해 hybrid region으로부터 page reclamation을 lazy하게 한다. (proactive reclaiming)
• → buddy allocator가 각 pageblock 내부에 unmovable page의 개수를 tracking해야 한다.
• Illuminator는 compaction하는 동안 hybrid region으로부터 pageblock reclaim을 한다.→ hybrid pageblock이 오직 movable / free page를 가지고 있다면 (unmovable page가 없다면) Illuminator는 pageblock의 색깔을 green으로 바꾸고, movable region으로 옮긴다.→ compaction이 너무 오래 지연되면 쓰레드는 백그라운드에서 정기적으로 hybrid region을 스캔하고 pageblock reclaim을 한다.
• → hybrid pageblock이 unmovable / free page만 가지고 있다면 red로 색깔을 바꾸고, unmovable region으로 옮긴다.
• → 각 hybrid pageblock의 movable page와 unmovable page의 개수를 조회한다.

5.3 Eliminating susceptibility to page locations

• 리눅스 커널에서 hybrid pageblock의 invisibility의 부작용:
• 성능이 unmovable page의 물리적 위치의 영향을 쉽게 받는다.
• example scenarioP1~P3 3개의 pageblock이 있다고 가정한다.(A) : P2가 unmovable page를 하나 가지고 있는 hybrid pageblock(B) : P1이 unmovable page를 하나 가지고 있는 hybrid pageblock
• → P1→P3 LIU migratiohn은 P3에 P2를 수용할만한 공간을 남겨두지 않기 때문에 P2가 huge page로 할당될 수 없게 한다.
• → 리눅스는 A 에서 P1의 page들을 P3에 migrate하여 huge page 할당을 할 수 있다.
• 각 pageblock에 512개의 baseline page 중 256개 / 절반이 할당되어 있다고 가정한다.
•  
• Linux의 compaction cost는 unmovable page의 공간적 분배에 따라 결정된다.
• → spatial location of unmovable page는 huge page 할당에 다양한 latency를 초래한다.
• Illuminator는 compaction 중에 hybrid pageblock을 대상에서 제외하기 때문에 unmovable page의 물리적 위치의 영향을 받지 않고 LIU migration을 피할 수 있다.

5.4 Timely reclamation of deferred objects

• deferred object를 적절한 때에 reclamation하기 위해 Prudence를 사용한다
• Prudence는 deferred object는 latent cache에 저장한다.
• ** latent cache : slab cache마다 정의된 cache
• Prudence는 RCU과 통합하여 slab allocator에 grace period information을 제공한다.
• → slab allocator는 grace period 이후에 즉시 deferred object를 reclamation할 수 있다.
• Prudence는 또한 synchronization 매커니즘을 사용하여 slab allocator가 in-use / free / about-to-be-freed될 object를 완벽하게 조회할 수 있게 한다.
• → about-to-be-freed object는 적은 slab 내에서 object를 클러스터링하여 unmovable memory의 footprint를 줄이는데 도움이 되는 free operation을 위한 결정적인 힌트를 제공한다.
• 이러한 optimiztion들은 alloc_pages 호출 횟수를 줄인다.
• 그러나 Prudence를 이용하여 slab allocator를 최적화하는 것으로는 부족하다. buddy allocator의 영향 아래에 있는 fragmentation via pollution을 제거하는 것이 huge page 지원을 위해 필요하다.

5.5 Implementation notes

• memory compaction 코드를 살짝 바꿔서 buddy allocator의 memory fallback path를 수정한다.
• Prudence를 사용해서 deferred free opertion에 영향을 미친다.
• 일반적인 할당 및 반납 operation은 그대로 둔다.
• LIU migration을 제거하기 위해 critical data structure의 locking overhead를 완화하고 cache pollution과 TLB invalidation을 최소화한다.

6. Evaluation

6.1 Experimental setup and workloads

• Intel Ivy-Bridge server with 8 cores running at 2.4GHz with 8MB of Last-LevelCache and a 500GB SSD drive
• L1 dTLB and iTLB - 64 entries each for 4KB pages & 8 entries each for huge pages
• shared L2TLB - 512 entries for 4KB pages / huge page X
• workload
•  
• 실험은 paging의 영향을 없애기 위해 swap의 disable하고 실행되었다.
• NPB_CG.D, PostgreSQL, MySQL -large memory 워크로드는 24GB 물리적 메모리에서, 나머지는 8GB에서 수행되었다.
• khugepaged와 똑같이 default huge page promotion rate - 1.6MB per second

6.2 The cost model for memory compaction

• compaction에 소요된 cost를 측정하기 위해 Gorman의 cost-theoretic model을 사용하였다.
• cost of memory Costmc : read/write한 byte의 수
•  
• Costmc → compaction code로 인한 memory traffic → cache effiency
• 커널은 page가 TLB 캐시 여부를 알지 못하기 때문에 Page migration은 TLB shootdown이 필요하다. TLB shootdown은 잘 확장되지 않고, multicore 시스템에서 주된 성능 오버헤드이다. 따라서 효율적인 솔루션은 Costmc를 최소화하는 것이다.

6.3 Huge page allocations with stress-highalloc

• stress-highalloc은 fragmentation완화 기법의 영향을 양적으로 측정하기 위해 사용하는 Linux kernel community developer의 표준 벤치마크이다.
• 전체 시스템 메모리의 90%를 huge page로 요청하기 전에 paralle하게 여러개의 kernel compilation job을 실행시켜 memory allocator에 stress를 준다.
• stree-highalloc 5번 실행 평균 huge page 할당의 실패 비율memory가 unmovable page로 인해 fragmented된 상태에서 Illuminator가 Linux보다 훨씬 좋은 성능을 낸다. (3.4배 더 많은 huge page를 할당할 수 있고, 80%이상 Costmc를 감소시킨다.)
• → Illuminator의 unmovable page management가 성공적이기 때문이다.
•  

6.4 Performance results on bare-metal

• Illuminator는 메모리가 fragment되었을 때 성능 이점이 있다.
• synthetic 벤치마크로 fragmentation을 만들고 fragmenation 3단계의 성능을 측정했다.ii) high / unmovability index = 0.5 → Linux-H
• iii) critical / unmovability index = 0.7 → Linux-C
• i) moderate / unmovability index = 0.25 → Linux-M
• Illuminator의 성능은 3 단계에서 균일했다.→ Illuminator는 hybrid pageblock을 compaction에 참여시키기 않는다.
• → hybrid pageblock의 개수를 리눅스의 10% 미만으로 제한하기 때문이다. (리눅스가 75%의 hybrid pageblock을 가지고 있을때, Illuminator는 전체 pageblock의 8%만이 hybrid pageblock이다.)

6.4.1 Overall performance improvement

• baseline page와 관련된 성능

 

• Linux에서 fragmentation이 증가할수록 application 성능은 떨어진다.
• Illuminator의 일부 성능 저하ii) fragmented system에서 커널이 huge page promotion을 수행하는데 시간이 걸린다.
• i) illuminator는 오직 LIU migration만 제거한다. 따라서 일반적인 migration이 성능에 영향을 미친다.
• 그럼에도 불구하고 Illuminator는 Linux보다 전체적인 측면에서 성능 향상을 보인다.

Huge page allocation

• Linux의 huge page 할당 능력은 unmovability index의 영향을 받는다.→ Illuminator는 Linux보다 huge page 할당이 많다.
• → movability index가 높을수록 huge page 할당이 적어진다.
• 백그라운드에서 huge page promotion을 하는 khugepaged는 fragmentation의 영향을 받는다.

compaction overhead

• Illuminator는 LIU migration을 제거하여 compaction cost를 많이 감소시킨다.
• → CPU utilization을 감소시키고 application에 의해 소모되는 시스템 time을 줄인다.

6.4.2 Latency and OS jitter

• read-only 워크로드가 8개의 쓰레드와 함께 실행되는 32million row를 가진 데이터베이스 MySQL DB 서버로 LIU migration으로 인한 latency의 영향을 평가했다. 각 실험을 10번 반복하고 각 iteration 중 최대 latency를 기록했다.
• huge page 할당에 걸리는 시간은 migrate scanner이 마주친 hybrid pageblock의 개수에 따라 결정되기 때문에 Linux에서 huge page allocation latency는 unmovable page의 위치에 영향을 받는다. 따라서 해당 워크로드에서 높은 latency를 보인다.
• Illuminator는 LIU migration을 제거하여 fragmentation via pollution을 처리하기 때문에 huge page 할당을 많이 할 수 있다. 따라서 최대 latency가 낮고 높은 throughput을 보인다.

6.4.3 Performance isolation

• memory compaction은 migrate scanner에 의해 마주친 모든 movable page를 migrate하는 global 프로세스이다. 실패할 떄까지 충분한 huge page를 할당 / promote 하거나 스케줄러에 의해 preemption 당한다.
• fragmented 시스템에서 LIU migration은 Linux가 compaction을 무한 반복하게 만든다.
• → 같은 machine상에서 실행되는 다른 워크로드에까지 부정적인 영향을 미친다.
• Illuminator는 모든 경우에 isolation에서도 좋은 성능을 보인다.

6.5 Performance in virtualized environments

• host OS - 24GB 메모리 + Ubuntu 16.04
• 하이퍼바이저 - KVM
• guest OS - 8GB + 8 cores + Ubuntu 12.04
• 가상화 시스템에서 application 성능은 guest와 host 계층의 memory fragmentation 상태에 따라 결정된다.
• 실험 결과ii) illuminator가 guest에만 적용된 경우⇒ illuminator가 guest에 적용된 경우의 성능 > host에 적용된 경우 / guest와 host 모두에 적용된 경우 최고 성능이 나온다.
• iii) illuminator가 host와 guest 둘 다 적용된 경우
• i) illuminator가 host에만 적용된 경우

7. Related work

OS support for huge pages

• 그동안의 운영체제 연구들은 huge page 지원을 구현하고 성능을 최적화하고, huge page가 존재하는 메모리의 효율성을 개선하는데 초점을 맞춰왔지만 fragmentation에는 크게 관심을 보이지 않았다.
• Illuminator는 long-running system에서 huge page 할당이 실현가능하고 cost-effective하게 만들 수 있도록 policy decision을 보완했다.
• → 이전의 연구의 기법들과 쉽게 통합될 수 있을 것이다.

Fragmentation mitigation in user space

• object의 예상 lifetime과 크기에 의해 결정되는 할당과 reclamation 결정은 user space에서 copying이나 generational garbage colleror의 기반을 형성한다.
• Illuminator는 커널 수준의 fragmentation을 완화하는데 적합하지 않다.

Fragmentation mitigation in the kernel

• proactive anti-fragmentation : 처음부터 각 프로세스에 연속적인 메모리를 할당한다.↔ short-lived 프로세스에만 적용가능하여 한정적이다.
• → 각 프로세스가 종료되면 contiguous memory가 회복된다.
• defragmentin memory with Lumpy reclaim: contiguous 영역으로부터 파일을 지원하는 page를 drop하여 memory contiguity를 회복한다.
• Lumpy relaim은 Linux에 merge되었으나 이후 I/O traffic으로 인해 다시 제거되었다.
• contiguity-aware page replacement
• compaction을 돕기 위한 anti-fragmentation scheme → merged to Linux→ memory 용량이 제한적이거나 워크로드 특징을 미리 예측할 수 없는 경우 구현이 불가능하다.
• ii) Grouping Pages Based on their Mobility type (GPBM) : 메모리 파티션 사이트를 동적으로 관리하여 동적인 워크로드에 적합하다. page-clustering 알고리즘의 영향을 크게 받는다.
• i) 부팅시 movable 영역과 unmovable 영역에 정적인 파티셔닝을 한다.

8. Discussion

• unmovable page는 운영체제에서 일반적으로 발견된다. (large memory 워크로드일수록 unmovable page가 더 많이 발생한다.)
• → unmovable page는 여러 제약을 초래하기 때문에 movable kernel page를 제공하는 운영체제도 있다.
• Illuminator를 FreeBSD 등 다양한 운영체제에 적용하는 연구를 할 수도 있다.
• Illuminator는 fragmentation의 영향을 받는 이전의 연구들에 영향을 줄 수도 있다.

9. Conclusion

• huge page로 인한 성능 문제를 다루고, unmovable page가 운영체제 커널에서 fragmentation 완화를 방해하는 주 원인이 되는 이유를 보여주었다.
• Illuminator를 제안하여 huge page 할당이 실현 가능하도록 하고, fragmented system에서 cost-effective하게 huge page를 사용할 수 있는 방안을 제시하였다.
• https://github.com/apanwariisc/Illuminator

10. 장점과 단점

1) 장점

• huge page allocation 중에 hybrid pageblock을 무시하기 때문에 unmovable page로 인한 방해를 받지 않고 불필요한 migration을 없앤다.
• movable, unmovable 뿐만 아니라 hybird region 도 따로 파티셔닝하여 관리하여 hybrid region이 덜 만들어지게 한다.
• fragmentation을 효과적으로 감소시켜 huge page 할당을 돕는다.

2) 단점

• hybrid pageblock을 별도로 관리하기 때문에 메모리 관리 오버헤드가 발생한다.