PIPT / VIVT / VIPT 캐시와 flush_dcache_folio()

오랜만에 글을 쓴다. 이번 글에서는 PIPT, VIPT, VIVT 캐시의 특성을 정리하고 페이지 캐시에서 언제 flush_dcache_folio()를 호출해야하는지 정리해본다.

캐시 복습

우선 캐시를 간단하게 복습해보자. (자세하게는 다루지 않는다!) 캐시는 너무 thrashing이 잦은 direct mapped 캐시나 현실적으로 너무 비싼 fully associative 캐시보다는 set associative 캐시가 주로 사용된다.

아주 엉성하게 그림을 그려봤는데... 위 그림은 같은 인덱스를 갖는 캐시 라인들을 set이라고 부르고, 4-way라서 하나의 set에 4개의 캐시 라인이 있다는 걸 표현하고자 했다. direct mapped 캐시와는 달리 N-way set associative 캐시는 인덱스가 같더라도 set 내에 N개의 캐시라인이 존재하기 때문에 thrashing이 비교적 덜 일어난다.

캐시는 접근하는 주소를 tag, index, offset으로 나눈다. offset은 캐시라인 내에서의 오프셋이며 어떤 캐시라인에 접근하는지는 tag와 index에 의해 결정된다. index는 set associative 캐시 내에서의 set을 선택하는 데에 사용되며, tag는 해당 set에 현재 접근하려는 주소에 대한 사본이 존재하는지 구분하는 용도로 사용된다. 예를 들어서 두 주소 0x1234567812345678과 0x5678567812345678은 index는 같지만 tag가 다르기 때문에, 같은 set 안에서 tag로 구분해야 한다.

위 그림에서는 크기가 1MB이고 캐시라인의 크기가 64바이트인 4-way set associative 캐시에서 tag, index, offset을 몇비트씩 사용하는지 그려봤다.

PIPT, VIVT, VIPT

재미있게도 캐시에서 tag와 index를 가상 주소에서 가져오냐 물리 주소에서 가져오냐에 따라서 다양한 특성과 문제가 발생한다.

PIPT: index와 tag 모두 물리 주소에서 가져온다.
VIVT: index와 tag 모두 가상 주소에서 가져온다.
VIPT: index는 가상 주소, tag는 물리 주소에서 가져온다.
PIVT: PIVT는 사용되지 않으므로 논의하지 않는다.

Physically Indexed, Physically Tagged

PIPT 캐시는 물리 주소에서 tag와 index를 가져오기 때문에 1) TLB를 통해서 먼저 주소 변환을 하고 2) 그렇게 얻은 물리 주소로 cache lookup을 해야한다. 따라서 이 때 지연시간은 TLB의 지연시간 + 캐시의 지연 시간이 되기 때문에 지연 시간이 조금 크다. 다르게 말하면 TLB lookup과 cache lookup을 serial하게 수행해야 하므로 느리다. PIPT는 느리지만 VIVT나 VIPT에서 생기는 synonym, homonym 문제가 발생하지 않는다.

homonym 문제

VIVT / VIPT 캐시를 살펴보기 전에 homonym, synonym 문제를 먼저 살펴보자. 먼저 homonym은 같은 가상 주소가 서로 다른 물리 주소를 가리킬 수 있음을 의미한다. 이 문제는 virtually tagged 방식의 캐시에서 발생한다. 멀티 태스킹 환경에서는 어떤 프로세스를 실행하냐에 따라서 같은 가상 주소라도 서로 다른 물리 주소를 가리킬 수 있다. virtually tagged 방식인 경우에는 문맥 전환 이후에 cache hit이 되었을 때, 캐시라인 안에 저장된 데이터가 현재 프로세스의 것인지 이전 프로세스의 것인지 구분할 수 없다.

해결 방법

1) 문맥 전환을 할 때마다 캐시를 writeback/invalidate하는 방법
2) tag에 특수한 식별자를 포함시켜서 서로 다른 프로세스의 캐시라인 간에는 cache hit이 발생하지 않도록 하는 방법. (ARM에 ASID-tagged VIVT cache라는게 있다. 근데 이건 사라지는 추세인 것 같다.)

synonym 문제

synonym은 서로 다른 가상 주소가 같은 물리 주소를 가리키지만, 캐시에서 인덱스가 달라 서로 다른 set에 저장될 때 발생하는 문제로 virtually indexed 방식의 캐시에서 발생한다. 이 글에서는 편의상 페이지의 크기가 4KB라고 가정한다.

위의 예시에서는 비트 [5:12]를 인덱스에 사용한다. 페이지가 4KB이므로 하위 12비트는 물리 주소와 가상 주소에서 모두 같지만, 비트 [12]는 물리 주소의 비트 [12]와 가상 주소 비트 [12]가 다를 수 있다. 예를 들어서 비트 [12]가 서로 다른 두 가상 주소가 같은 물리 주소를 가리킨다면 캐시 내에서 서로 다른 set에 저장되기 때문에, 하나의 캐시 라인이 갱신되었을 때 나머지 하나는 stale한 데이터를 갖게 된다.

해결 방법

1) 인덱스의 크기를 줄이는 방법. 예시에서는 인덱스가 비트 [5:11]까지를 사용하도록 하면 된다. 인텔 CPU에서 이런 방법을 사용한다고 한다.

2) 같은 주소 공간 내에서는 비트 [11]보다 상위에 있는 비트들이 같은 가상 주소만 사용하도록 하는 방법 (page coloring)

3) 이 글에서는 캐시 내에서 동일한 두 태그가 존재하는지 확인하는 방식으로 aliasing을 피할 수 있다고 한다. 아직 막 와닿지는 않는다.

Virtually Indexed, Virtually Tagged

VIVT는 tag와 index 모두 가상 주소에서 가져온다. VIVT 캐시는 가상 주소로 cache lookup을 할 수 있기 때문에 주소 변환을 하지 않아도 된다는 장점이 있지만, homonym 문제가 있어 문맥 교환을 할 때마다 캐시를 writeback/invalidate 해줘야 한다.

그리고 synonym 문제도 하드웨어 단에서 일어나지 않도록 보장해주든지, 운영체제에서 page coloring을 해주든지 해야한다.

Virtually Indexed, Physically Tagged

VIPT 캐시는 VIVT에서의 homonym 문제가 존재하지 않아 문맥 교환을 할 때 캐시를 비우지 않아도 된다. 그리고 TLB lookup과 cache lookup을 동시에 할 수 있어서 PIPT보다 빠르다.  (synonym 문제는 여전히 존재한다.)

다시 살펴보는 페이지 캐시에서의 D-cache aliasing 문제

사실 이 글은 필자가 페이지 캐시에서의 D-cache aliasing을 제대로 이해하지 못했던 것 같아서 정리하는 글이다. 얼마전에 페이지 캐시를 다뤘는데 이 부분에 대한 설명이 부족했던 것 같다.

64비트 환경에서 페이지 캐시상의 페이지가 사용자 프로세스에서 writable하고 shared하게 매핑된 경우(i_mmap_writable > 0)는 위와 같이 그려질 것이다. 그러면 커널이 페이지 캐시에 접근할 때 사용하는 direct mapping 영역상의 가상 주소와, 사용자 프로세스가 페이지 캐시에 접근하는 가상 주소가 다르기 때문에, 한 쪽이 데이터를 갱신하면 다른 한 쪽은 stale한 데이터를 볼 수 있다.

따라서 리눅스는 페이지 캐시에 접근할 때 다음과 같은 경우에 flush_dcache_folio()를 호출해서 d-cache를 flush한다.

1) i_mmap_writable > 0인 경우에는 페이지 캐시를 읽기 전에 d-cache를 flush해준 후 읽어야 한다. (커널이 stale한 데이터를 보지 않도록)

2) i_mmap_writable > 0인 경우에는 페이지 캐시에 쓰기 전에 d-cache를 flush해준 후에 덮어쓴다. (커널이 stale한 데이터를 덮어쓰지 않도록) 덮어 쓴 다음에는 i_mmap_writable의 값에 관계없이 사용자 프로세스가 stale한 데이터를 보지 않도록 d-cache를 flush해야한다.

글을 쓰다보니 생긴 질문

리눅스는 page coloring을 지원하는가? 만약 그렇지 않다면, 다수의 프로세스가 같은 파일에 대해서 writable하고 shared한 매핑을 만들면 synonym 문제를 어떻게 피할까? 아마 arch_get_unmmaped_area()에 힌트가 있을지도 모른다.

이 글에서 다루지 못한것

보통 VIPT는 주로 L1 캐시에서만 사용하고 더 하위 캐시는 PIPT 캐시를 사용한다고 한다. (이 부분은 좀더 알아봐야할 것 같다.)

참고 문서

Understanding Caching | Linux Journal

flush_dcache_page와 kmap_atomic

How does the VIPT to PIPT conversion work on L1->L2 eviction

Virtually indexed physically tagged cache Synonym

Virtually Indexed Physically Tagged (VIPT) Cache - GeeksforGeeks