# Readahead는 marker와 cache history로 읽기 흐름을 다시 찾습니다

파일을 한 page씩 읽던 프로그램이 중간 offset으로 건너뛰었다가 다시 순서대로 읽기 시작했다고 가정하겠습니다. kernel은 application의 다음 호출을 알지 못합니다. 직전 window의 상태와 공유 page cache에 남은 흔적만으로 다음 읽기가 sequential일 가능성을 판단합니다. 이때 window를 키우는 공식보다 중요한 것은 어느 증거를 먼저 믿고, 증거가 부족하면 무엇을 바꾸지 않는지입니다.

상태 전이를 한 함수 안에서 보기 위해 이 글은 공식 Linux `v6.0`의 `ondemand_readahead()`를 사용합니다. 현재 v6.18의 구현이라고 소개하는 code는 아닙니다. v6.18에서는 synchronous와 asynchronous policy로 나뉘었고 marker 정렬과 초기 tail도 달라졌습니다. 과거 알고리즘을 실제로 읽은 뒤 현재와 비교해야 서로 다른 시기의 조건으로 하나의 가상 함수를 만들지 않을 수 있습니다. 책에 실린 모든 code의 정확한 tag를 v6.0으로 특정하는 것도 아닙니다.

## 같은 cache를 읽어도 예상 상태는 다를 수 있습니다

`file_ra_state`의 `start`, `size`, `async_size`는 한 열린 file 쪽의 예상입니다. cache contents는 mapping 쪽에서 공유하므로, 이 file의 최근 상태와 cached folio의 marker가 항상 같은 stream에서 만들어졌다는 보장은 없습니다. 다른 reader가 window를 준비했거나 같은 open file description을 공유한 요청이 상태를 바꾸었을 수 있습니다.

`start`는 window의 첫 file index, `size`는 그 window의 base-page 수입니다. `async_size`는 window 끝에서 다음 trigger까지의 거리를 나타내는 tail 길이입니다. policy가 사용하는 page 수와 실제 folio 객체 수는 다를 수 있습니다. order-2 folio 하나가 네 base page를 대표하므로 marker의 정렬에도 folio order가 관여합니다.

이 함수는 marker를 통해 들어왔는지 판단할 `folio` 인자를 받습니다. NULL이면 그 folio에서 발생한 marker hit이라는 증거가 없는 요청이고, non-NULL이면 이미 발견한 folio가 입력된 문맥입니다. 다만 NULL이라는 이유만으로 모든 filesystem I/O가 즉시 blocking이 된다고 읽어서는 안 됩니다. 아래 함수는 window를 결정하고 준비 경로에 넘기며 I/O 완료 전체를 기다리는 함수가 아닙니다.

## 예상 위치를 만났다면 window를 전진시킵니다

처음에는 기본 상한인 `ra_pages`를 사용합니다. 요청이 이보다 크고 `bdi->io_pages`도 기본 상한보다 크면 두 값의 작은 쪽으로 상한을 높입니다. 큰 demand request가 기본 window보다 크다는 이유만으로 잘라야 하는 것은 아니지만, 요청량과 hardware I/O hint를 모두 무시하고 무제한으로 준비하는 것도 아닙니다.

file index가 0이면 초기 window를 만듭니다. 그렇지 않으면 이전 window에서 기대한 marker와 window 끝을 비교합니다. 이 버전의 expected marker는 `start + size - async_size`를 현재 folio의 page 수로 **올림 정렬**한 index입니다. 그 위치이거나 window의 끝이면 sequential 접근의 증거로 보고, `start`를 직전 window 뒤로 옮긴 뒤 다음 크기를 정합니다. 이때 새 tail은 새 window 전체입니다.

이 비교가 순차성을 증명하는 것은 아닙니다. 여러 요청이 우연히 같은 위치를 만날 수도 있습니다. policy는 이 오판 가능성을 받아들이면서 불필요한 정밀 추적을 줄입니다. 따라서 callback index가 기대와 달랐다는 사실도 곧바로 I/O 오류가 되지는 않습니다.

## 뜻밖의 marker에서는 다음 hole을 찾습니다

folio는 marker를 갖고 있는데 해당 file의 예상 상태가 맞지 않으면 공유 cache를 다시 읽어 단서를 찾습니다. 이 구현은 RCU read-side 구간에서 `page_cache_next_miss()`를 호출해 현재 index 다음부터의 hole을 찾습니다. 이후 reader가 cache를 바꿀 수 있으므로 이 관찰은 영구적인 snapshot이 아닙니다.

검색 결과가 0이거나 현재 index에서의 거리가 상한보다 크면 함수는 더 진행하지 않습니다. 적절한 window를 복구할 증거가 없다는 뜻이지 해당 파일을 읽을 수 없다는 오류 판정이 아닙니다. 유효한 hole을 찾았다면 그 위치를 새 시작으로 하고, 이전 tail로 추정한 거리와 현재 요청량을 더한 뒤 다음 크기를 계산합니다.

marker가 없는 cache miss에서는 큰 요청, 이전 read 위치와의 인접성, cached history 순으로 다른 증거를 사용합니다. `prev_pos`에서 구한 이전 page와의 차이가 0 또는 1인 경우는 unaligned read와 바로 다음 page 접근을 포함합니다. byte position과 file index를 섞어 비교하지 않아야 하는 이유입니다.

## history는 RCU 아래의 제한된 관찰입니다

`count_history_pages()`는 바로 앞 index부터 거꾸로 missing 위치를 찾습니다. 반환값은 `index - 1 - head`이며 `pgoff_t`의 unsigned 계산을 사용합니다. 파일 처음까지 이어지는 경우의 sentinel과 wrap을 부호 있는 음수 index처럼 임의로 바꾸면 안 됩니다. `max`는 검색량도 제한하므로 파일 앞부분 전체의 접근 이력을 보존하는 장치가 아닙니다.

다음은 [v6.0 `count_history_pages()`](https://github.com/torvalds/linux/blob/v6.0/mm/readahead.c)의 전체 정의입니다. RCU 구간은 tree 검색을 위한 것이며 반환 뒤에도 그 page들이 cache에 남도록 참조를 하나씩 확보한 것은 아닙니다.

<!-- include-code:code/count_history_pages_v6_0.c -->

`try_context_readahead()`는 history가 현재 요청량 이하이면 0을 반환합니다. 이 경우 기존 state를 바꾸지 않아 독립적인 작은 random read가 sequential stream의 예상을 오염시키지 않게 합니다. history가 파일 처음까지 이어진 조건에서는 두 배의 가중치를 주고, 요청량까지 더한 수를 상한으로 제한합니다. 성공하면 시작을 현재 index로 바꾸고 tail을 1 page로 둔 뒤 1을 반환합니다. 이 1은 read I/O가 끝났다는 반환값이 아닙니다.

<!-- include-code:code/try_context_readahead_v6_0.c -->

다른 reader가 남긴 cache나 reclaim 때문에 생긴 hole도 같은 검색에 나타날 수 있습니다. 그러므로 충분한 history는 추측의 근거이지 application의 실제 접근 순서를 복원한 로그가 아닙니다. 검색 실패에 errno를 붙여 application read 실패로 전달하지 않는 것도 이 역할과 맞습니다.

## random read와 self-marker 병합의 경계입니다

sequential 증거를 찾지 못한 작은 요청은 요청량만, lookahead 0으로 일반 준비 helper에 넘기고 돌아갑니다. window state는 바꾸지 않습니다. 반대로 초기 window를 만드는 경우에는 요청량을 power of two 기반 heuristic에 넣고, window가 요청량보다 크면 그 차이를 tail로 사용합니다. 그렇지 않으면 이 버전은 tail을 window 전체로 둡니다.

그 뒤 self-marker 병합이 적용될 수 있습니다. `index == start`와 `size == async_size`가 모두 참이면 이번 read가 자기가 만든 marker를 곧바로 소비할 조건으로 보고 다음 window를 미리 합칩니다. `get_next_ra_size()`로 구한 추가량과 현재 크기의 합이 상한 이하이면 추가량을 새 tail로 정하고 두 window를 더합니다. 합이 상한을 넘으면 전체 크기는 상한, tail은 그 절반입니다. 조건 하나만 보고 항상 두 window를 합치는 알고리즘은 아닙니다.

아래는 [v6.0 `ondemand_readahead()`](https://github.com/torvalds/linux/blob/v6.0/mm/readahead.c)의 **전체 정의**입니다. 앞의 두 helper와 함께 branch의 우선순위, 조기 반환, state를 유지하는 경로와 수정하는 경로를 직접 확인할 수 있습니다. 각 파일은 GPL-2.0-only 식별자와 source attribution을 보존한 kernel 발췌이며 standalone program은 아닙니다.

<!-- include-code:code/ondemand_readahead_v6_0.c -->

이 함수의 반환 type은 `void`입니다. window를 준비하는 하위 helper에서 allocation이나 삽입이 실패해도 이 함수가 user read의 최종 errno를 반환하지는 않습니다. demand read와 fault는 나중에 실제 folio의 존재·lock·uptodate를 확인하며 필요하면 직접 read를 수행합니다. policy 성공, allocation 성공과 내용 준비 성공은 다른 단계입니다.

## 현재 구현과 비교할 때 바꾸지 말아야 할 경계입니다

v6.18의 synchronous policy는 초기 tail이 window 전체가 되는 옛 분기를 그대로 쓰지 않습니다. window가 요청량보다 크면 차이, 그렇지 않으면 절반을 사용합니다. asynchronous policy의 expected marker도 현재 folio 크기에 맞춰 내림 정렬합니다. self-marker를 합치던 옛 branch까지 이 두 조건에 덧붙이면 어느 release에도 없는 동작을 설명하게 됩니다.

[현재 readahead policy의 전체 정의와 설명](07-readahead-policy.md)은 이 차이를 별도로 다룹니다. 실제 locked folio allocation과 filesystem callback 소비, 실패 뒤 cleanup은 [folio 전달과 참조의 계약](08-readahead-io-ownership.md)에 이어집니다. policy state를 바꾸는 짧은 분기와 memory·I/O의 긴 수명 규칙을 분리해야 추측이 틀린 경우에도 왜 정상 read가 가능한지 설명할 수 있습니다.

## 참고 자료

- Lorenzo Stoakes, *The Linux Memory Manager*, Early Access 2025, Chapter 9, §9.7.3.
- Linux v6.0: [ondemand_readahead, try_context_readahead, count_history_pages](https://github.com/torvalds/linux/blob/v6.0/mm/readahead.c).
- Linux v6.18: [synchronous/asynchronous readahead policy](https://github.com/torvalds/linux/blob/v6.18/mm/readahead.c).
- [Linux kernel licensing rules](https://docs.kernel.org/process/license-rules.html).