파일을 한 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()의 전체 정의입니다. RCU 구간은 tree 검색을 위한 것이며 반환 뒤에도 그 page들이 cache에 남도록 참조를 하나씩 확보한 것은 아닙니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* Complete definition from Linux v6.0 mm/readahead.c.
* Source: https://github.com/torvalds/linux/blob/v6.0/mm/readahead.c
* Copyright (C) 2002, Linus Torvalds
* 09Apr2002 Andrew Morton -- Initial version.
* Kernel excerpt; not a standalone user-space program.
* This tag is not asserted to be the book's exact source revision.
*/
static pgoff_t count_history_pages(struct address_space *mapping,
pgoff_t index, unsigned long max)
{
pgoff_t head;
rcu_read_lock();
head = page_cache_prev_miss(mapping, index - 1, max);
rcu_read_unlock();
return index - 1 - head;
}
try_context_readahead()는 history가 현재 요청량 이하이면 0을 반환합니다. 이 경우 기존 state를 바꾸지 않아 독립적인 작은 random read가 sequential stream의 예상을 오염시키지 않게 합니다. history가 파일 처음까지 이어진 조건에서는 두 배의 가중치를 주고, 요청량까지 더한 수를 상한으로 제한합니다. 성공하면 시작을 현재 index로 바꾸고 tail을 1 page로 둔 뒤 1을 반환합니다. 이 1은 read I/O가 끝났다는 반환값이 아닙니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* Complete definition from Linux v6.0 mm/readahead.c.
* Source: https://github.com/torvalds/linux/blob/v6.0/mm/readahead.c
* Copyright (C) 2002, Linus Torvalds
* 09Apr2002 Andrew Morton -- Initial version.
* Kernel excerpt; not a standalone user-space program.
* This tag is not asserted to be the book's exact source revision.
*/
static int try_context_readahead(struct address_space *mapping,
struct file_ra_state *ra,
pgoff_t index,
unsigned long req_size,
unsigned long max)
{
pgoff_t size;
size = count_history_pages(mapping, index, max);
/*
* not enough history pages:
* it could be a random read
*/
if (size <= req_size)
return 0;
/*
* starts from beginning of file:
* it is a strong indication of long-run stream (or whole-file-read)
*/
if (size >= index)
size *= 2;
ra->start = index;
ra->size = min(size + req_size, max);
ra->async_size = 1;
return 1;
}
다른 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()의 전체 정의입니다. 앞의 두 helper와 함께 branch의 우선순위, 조기 반환, state를 유지하는 경로와 수정하는 경로를 직접 확인할 수 있습니다. 각 파일은 GPL-2.0-only 식별자와 source attribution을 보존한 kernel 발췌이며 standalone program은 아닙니다.
// SPDX-License-Identifier: GPL-2.0-only
/*
* Complete definition from Linux v6.0 mm/readahead.c.
* Source: https://github.com/torvalds/linux/blob/v6.0/mm/readahead.c
* Copyright (C) 2002, Linus Torvalds
* 09Apr2002 Andrew Morton -- Initial version.
* Kernel excerpt; not a standalone user-space program.
* This tag is not asserted to be the book's exact source revision.
*/
static void ondemand_readahead(struct readahead_control *ractl,
struct folio *folio, unsigned long req_size)
{
struct backing_dev_info *bdi = inode_to_bdi(ractl->mapping->host);
struct file_ra_state *ra = ractl->ra;
unsigned long max_pages = ra->ra_pages;
unsigned long add_pages;
pgoff_t index = readahead_index(ractl);
pgoff_t expected, prev_index;
unsigned int order = folio ? folio_order(folio) : 0;
/*
* If the request exceeds the readahead window, allow the read to
* be up to the optimal hardware IO size
*/
if (req_size > max_pages && bdi->io_pages > max_pages)
max_pages = min(req_size, bdi->io_pages);
/*
* start of file
*/
if (!index)
goto initial_readahead;
/*
* It's the expected callback index, assume sequential access.
* Ramp up sizes, and push forward the readahead window.
*/
expected = round_up(ra->start + ra->size - ra->async_size,
1UL << order);
if (index == expected || index == (ra->start + ra->size)) {
ra->start += ra->size;
ra->size = get_next_ra_size(ra, max_pages);
ra->async_size = ra->size;
goto readit;
}
/*
* Hit a marked folio without valid readahead state.
* E.g. interleaved reads.
* Query the pagecache for async_size, which normally equals to
* readahead size. Ramp it up and use it as the new readahead size.
*/
if (folio) {
pgoff_t start;
rcu_read_lock();
start = page_cache_next_miss(ractl->mapping, index + 1,
max_pages);
rcu_read_unlock();
if (!start || start - index > max_pages)
return;
ra->start = start;
ra->size = start - index; /* old async_size */
ra->size += req_size;
ra->size = get_next_ra_size(ra, max_pages);
ra->async_size = ra->size;
goto readit;
}
/*
* oversize read
*/
if (req_size > max_pages)
goto initial_readahead;
/*
* sequential cache miss
* trivial case: (index - prev_index) == 1
* unaligned reads: (index - prev_index) == 0
*/
prev_index = (unsigned long long)ra->prev_pos >> PAGE_SHIFT;
if (index - prev_index <= 1UL)
goto initial_readahead;
/*
* Query the page cache and look for the traces(cached history pages)
* that a sequential stream would leave behind.
*/
if (try_context_readahead(ractl->mapping, ra, index, req_size,
max_pages))
goto readit;
/*
* standalone, small random read
* Read as is, and do not pollute the readahead state.
*/
do_page_cache_ra(ractl, req_size, 0);
return;
initial_readahead:
ra->start = index;
ra->size = get_init_ra_size(req_size, max_pages);
ra->async_size = ra->size > req_size ? ra->size - req_size : ra->size;
readit:
/*
* Will this read hit the readahead marker made by itself?
* If so, trigger the readahead marker hit now, and merge
* the resulted next readahead window into the current one.
* Take care of maximum IO pages as above.
*/
if (index == ra->start && ra->size == ra->async_size) {
add_pages = get_next_ra_size(ra, max_pages);
if (ra->size + add_pages <= max_pages) {
ra->async_size = add_pages;
ra->size += add_pages;
} else {
ra->size = max_pages;
ra->async_size = max_pages >> 1;
}
}
ractl->_index = ra->start;
page_cache_ra_order(ractl, ra, order);
}
이 함수의 반환 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의 전체 정의와 설명은 이 차이를 별도로 다룹니다. 실제 locked folio allocation과 filesystem callback 소비, 실패 뒤 cleanup은 folio 전달과 참조의 계약에 이어집니다. 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.
- Linux v6.18: synchronous/asynchronous readahead policy.
- Linux kernel licensing rules.