(2022.05.27) Address Translation (2)

이번 포스팅에서는 주로 TLB와 TLB를 도입해서 파생하는 문제를 보완하는 내용을 다룰 것이다.

1. TLB란?

TLB는 translation lookaside buffer의 약자로 멀티 레벨 페이지 테이블에서 발생하는 translation cost를 mitigate하기 위해 도입되었다. CPU cache는 메모리의 내용을 cache하지만, TLB는 virtual 페이지에서 physical 프레임으로의 "번역 결과"를 cache한다. 만약 cache hit이 되면 해당 번역을 사용하고, cache miss가 되면 멀티 레벨 페이지 테이블을 순회하며 직접 번역한다. 

2. Translation Cost

TLB를 도입하게 되면 TLB를 우선적으로 살펴보고, 확률적으로 hit이 되기 때문에 miss일 때만 페이지 테이블을 살펴보면 된다. 따라서 전체 Translation Cost는 Cost of TLB Lookup + Prob(TLB miss) * Cost of PT Lookup이 된다. 

 

TLB까진 CPU에 포함이 되어 있으며, TLB나 페이지 테이블에서 나온 결과를 사용해 물리 메모리에 접근하는 것을 볼 수 있다.

 

TLB는 set-associative cache로 주로 구현되지만 fully-associative한 경우만 살펴보자. (그래서 이게 뭔데요?) TLB의 엔트리는 매칭되는 매핑을 찾기 위한 Virtual 페이지 넘버, 매핑의 결과인 Physical 프레임 넘버, 그리고 해당 페이지의 작업 권한 access로 구성된다. 매칭이 있을 경우, access 정보가 없다면 valid한 접근인지를 알 수 없으므로 반드시 가지고 있어야 한다. 매칭되는 엔트리를 찾는 방식은 1 by 1이 아닌 HW 구현에 의해 parallel하게 진행된다.  

 

TLB는 거저 혜택을 주는 것이 아니며, 관리가 필요하다. 일례로 OS가 특정 페이지에 대해 작업 권한(퍼미션)을 변경한 경우를 생각해보자. 페이지 테이블에서 access가 바뀐 것이 TLB에서도 저절로 바뀌지 않기 때문에 access bit가 변경된 직후에는 페이지 테이블과 TLB가 synchronize되지 않을 수 있다. 이를 활용한 공격도 있다. (Shadow TLB attack) 그렇기에 OS는 이 문제를 해결하기 위해 TLB 전체를 비워버리면서 오래되어 잘못된 번역을 없애버린다. 이를 TLB flush (TLB shootdown)이라고 한다. 예전에는 서로 다른 상황에서 쓴 용어였지만 지금은 서로 번갈아가면서 쓴다고 한다. TLB flush를 하는 것을 까먹었다고 해도 당장 crash가 나지 않기 때문에 문제 발견이 늦어질 수 있어 보안상 위험하다. 그렇다고 flush를 너무 자주한다면 performance가 낮아지므로 적절한 시점에만 하는 것이 중요하다.

 

또 다른 문제는 Context Switch가 일어날 경우 TLB 엔트리가 재사용이 안 된다는 점이다. 이는 Synonym과 Homonym 현상 때문이다. Synonym (동의어)는 다른 VA가 같은 PA로 연결되는 것을 의미하고, Homonym (동음이의어)은 동일한 VA가 다른 PA로 연결되는 것을 의미한다. 이는 Virtual Address가 per process이기 때문에 나타나는 현상으로, TLB에 cache된 번역은 cache가 되었을 때 실행되고 있었던 프로세스에 대해서만 유효하기 때문에 엔트리를 다른 프로세스에 대해 재사용할 수는 없다. 

3. Tagged TLB

다만 위의 얘기를 반대로 뒤집었을 때, 엔트리가 cache될 때 실행되었던 프로세스가 재실행된다면 엔트리를 사용할 수 있다는 점을 의미한다. 또한, TLB 엔트리 전체를 Context Switching 마다 버리는 것은 비용이 많이 들어가기 때문에 flush를 최소화하기 위해서라도 수정이 필요하다. 이를 위해 파생된 것이 Tagged TLB이다.

 

Tagged TLB에서는 각 엔트리에 해당 엔트리가 cache될 때 실행되던 프로세스 ID를 같이 저장하여 어느 프로세스에서 사용될 수 있는 번역인지를 같이 표기하고, TLB hit 조건을 pid가 일치하도록 하는 조건을 추가해 강화한다. tagged TLB에서는 context switch시 flush가 일어나지 않지만 permission change에서는 OS가 TLB의 엔트리를 변경할 수 없는 특징 때문에 flush가 일어나야한다. 인텔에서는 특정 엔트리만 flush가 될 수 있도록 조정이 가능하다고 한다. 

4. TLB의 장점과 한계

TLB는 DRAM 내에 존재해 번역이 느릴 수 밖에 없는 페이지 테이블(90 ms)과 달리 1~2 CPU cycle 내에 (0.3 ~ 0.6ms) 빠른 번역이 가능하다. 그럼에도 불구하고 번역 비용이 쉽게 줄어들지 않는 것을 확인할 수 있다. 429.mcf 같은 사례를 보면 전체 CPU cycle의 40% 정도를 페이지 walk에만 태우고 있다는 것을 볼 수 있다. 이는 최근 어플리케이션이 large memory footprint와 낮은 메모리 locality를 가진데에 비해 TLB의 메모리 coverage가 부족하기 때문이다. 메모리의 크기는 키우는데 한계가 없는데에 비해, TLB는 용량을 키우는데에 한계가 있다. parallel 탐색을 해야 하는 TLB의 특성상 용량을 키우면 TLB 탐색의 시간이 늘어나 실질적으로 무용지물이 되기 때문이다. TLB의 용량을 늘리지 않으면서도, TLB의 coverage를 증가시키기 위해서는 페이지의 크기를 늘리면 된다. 

5. Super pages

위의 아이디어에서 착안한 것이 superpage이다. superpage란 contiguous한 페이지의 집합으로, TLB 엔트리는 페이지 또는 superpage로 매핑이 될 수 있도록 한다. 일례로 x86의 TLB 엔트리는 평범하게 4kB 페이지를 매핑할 수도 있으나, 더 큰 superpage인 2MB, 1GB를 매핑하게 할 수도 있다. Superpage를 사용할 경우 더 큰 범위의 메모리 매핑을 TLB로 할 수 있다는 장점이 있다.

 

Superpage를 사용할 경우 아키텍쳐에서 가상 주소를 번역하는 방식이 달라지는 것을 볼 수 있다. 더 많은 수의 bit를 오프셋으로 사용하고 TLB의 엔트리 또한 매칭으로 SP 넘버를 사용해서 SF로 번역한다. 예시로 x86-64에서는 superpage를 사용할 때 21개의 하위 비트를 오프셋으로 사용하고, 3단계의 페이지 테이블을 사용한다 (2MB superpage). 만약 한 단계를 더 없앤다면 30개의 하위 비트를 사용하는 것이며, 한 superpage의 크기는 1GB가 된다. HW가 주어진 주소를 가지고 번역을 할 때 superpage인지의 여부를 판단하게 하는 bit가 존재해 superpage로 번역할지 일반 page로 번역할지를 구분할 수 있다. 

 

실제로 Superpage를 사용하면 4kB 페이지만을 사용할 때와 비교해서 속도가 향상된 것을 볼 수 있다. (평균적으로 30% 정도) 이러한 속도 향상은 TLB의 사용이 좀 더 효율적이게 되어, address translation cost가 줄어들었기 때문이다. 이러한 성능 향상에도 불구하고 사람들은 일반적으로 Superpage (Transparent Huge Page)를 사용하는 것을 꺼리며 많은 시스템이 해당 기능을 끌 것을 요구한다. 이는 internal fragmentation이 발생하기 때문이다. 더 자세한 내용은 교수님의 논문에 잘 소개되어 있으니 관심이 있으면 보도록 하자. 물론 기말에는 안 나오니 알아서 할 것! 응 안 봐...