[Linux] 블록 장치 I/O 동작 방식 (4) in Linux 3.1-rc4

*출처: http://studyfoss.egloos.com/5585801

지금까지 상위 (filesystem) 계층에서 요청된 I/O 연산이 bio를 거쳐 request로 만들어지는 과정을
살펴보았다. 이제 이렇게 생성된 request가 I/O 스케줄러 단에서 처리되는 방식을 알아볼 것이다.

앞서 살펴보았듯이 생성된 request는 대부분 (per-task) plugging 기능이 적용된 상태일 것이므로
(직접적인 read/write의 경우는 물론 read-ahead, writeback의 경우도 이에 해당한다)
I/O 스케줄러에게 전달되기에 앞서 plugged list에 잠시 보관된다.

plugging 기능을 사용하려면 해당 함수의 스택에 blk_plug 구조체를 할당하고
먼저 blk_start_plug() 함수를 호출한 후에 I/O 연산을 발생시키고
마지막으로 blk_finish_plug() 함수를 호출하면 된다.

blk_start_plug() 함수는 주어진 blk_plug 구조체를 적절히 초기화한 후에
현재 태스크의 plug 필드에 저장하는데, 만약 blk_start_plug() 함수가 중첩된 실행 경로 상에서
여러 번 호출되었다면 제일 첫 번째로 호출된 경우에만 plug 필드를 저장한다.
이는 plugging 로직이 가장 상위 수준에서 처리될 수 있도록 보장해 준다.

blk_finish_plug() 함수는 태스크의 plug 필드와 인자로 주어진 blk_plug 구조체가 일치하는 경우에만
동작하며, 대응하는 start 함수와 현재 finish 함수 사이에서 발생한 I/O 연산 (request)들을 모두
I/O 스케줄러에게 전달하고 (insert) 실제로 드라이버가 I/O를 실행하도록 한다.
request를 I/O 스케줄러에게 전달하는 방식은 request의 종류 및 상황에 따라 몇 가지 정책이 적용된다.

만약 plugged list에 request가 존재하는 상황에서 어떠한 이유로 인해 현재 태스크가 더 이상
실행되지 못하고 (자발적으로!) sleep 해야한다면 kblockd 스레드가 대신 plugged list를 넘겨받아
I/O 스케줄러에게 전달한 뒤에 I/O 연산을 실행한다.

plugged list 내의 request들이 I/O 스케줄러에게 전달되는 순간 다시 한번 merge가 가능한지
검사하게 되는데 이는 여러 태스크들이 동시에 디스크 상의 비슷한 위치에 접근하는 경우 각각의 태스크들은
자신의 plugged list에 포함되어 다른 태스크들은 접근하지 못하던 request들이 이제 공유되므로
새로이 merge될 가능성이 있기 때문이다. 이러한 정책은 ELEVATOR_INSERT_SORT_MERGE로 나타내며,
plugging 기법을 이용하지 않을 시에는 이러한 merge 시도를 할 필요가 없으므로
ELEVATOR_INSERT_SORT 정책이 사용된다.

I/O 스케줄러는 주어진 request들을 디스크 상의 위치에 따라 배열하여 seek time을 최소화하기 위해
노력하는데, 이 때 기본적으로 디스크의 헤드가 한 쪽 방향으로만 일정하게 움직이도록 하므로
이를 엘리베이터 (elevator)라고도 부른다. (물론 세부 동작은 각 I/O 스케줄러마다 다르다)

이를 위해서는 I/O 스케줄러 내부에 request들을 (잘 정렬하여) 보관할 자료구조가 필요한데
여기서는 rb tree (red-black tree)가 사용되며, 앞서 살펴보았듯이 (merge를 위해)
정렬된 rb tree 내의 특정 request를 빨리 찾아내기 위해 별도의 해시 테이블을 가지고 있다.
이렇게 rb tree 내에 보관된 request들은 REQ_SORTED라는 플래그를 추가하여 표시한다.

하지만 FLUSH/FUA request에 대해서는 약간 다른 ELEVATOR_INSERT_FLUSH 정책을 취하게 되는데
이러한 request들은 해당 디스크의 특성에 따라 다르게 처리될 수 있으며 또한 일반적인 merge를
지원하는 대신 중첩된 flush 요청을 한꺼번에 처리하는 기법을 사용하기 때문이다.

앞서 살펴보았듯이 FLUSH는 디스크 내부의 write-back 캐시의 내용을 실제 디스크에 저장하라는 의미이며
FUA는 write-back 캐시가 없는 것처럼 현재 데이터를 디스크에 직접 기록하라는 의미이다.
따라서 디스크가 내부 캐시를 가지지 않는 경우라면 FLUSH/FUA는 아무런 의미가 없다.
또한 캐시를 가진 디스크라고 하더라도 FUA 지원 여부는 선택적이므로 지원하지 않는 디스크의 경우
FUA request가 들어오면 이를 다시 FLUSH로 변경하여 처리하게 된다.

특히 FUA request의 경우 write할 데이터와 함께 요청되므로 최악(?)의 경우
하나의 (FLUSH & FUA) request는 다음과 같이 세 단계로 나누어 처리되어야 한다.

 (pre) FLUSH + WRITE + (post) FLUSH

따라서 FLUSH/FUA request는 REQ_FLUSH_SEQ 플래그를 추가하여 이러한 과정을 거치고 있음을 나타내며
이에 대한 추가적인 정보를 request 구조체 내의 flush (구조체) 필드에 저장하고 있다.

또한 이러한 request를 여러 태스크가 동시에 요청하는 경우 FLUSH 연산이 여러 차례 실행될 수 있으나
그 사이 데이터가 write 되지 않았다면 실질적으로 의미가 없으므로 (캐시 내의 모든 데이터가 이미 저장되었다)
이러한 중첩된 FLUSH 연산을 한 번만 수행해도 동일한 효과를 얻을 수 있게 될 것이다.

따라서 이러한 FLUSH/FUA request를 효율적으로 처리하기 위해 별도의 queue를 유지하며
총 2개의 리스트를 통해 하나의 FLUSH 요청이 실행되는 동안 발생된 FLUSH request들은 다른 리스트에
대기시키는 double buffering 방식을 이용하여 중첩된 request들을 한꺼번에 완료시키게 된다.

이렇게 I/O 스케줄러에게 전달된 request는 최종적으로 dispatch queue로 전달된다.
이렇게 전달된 request는 더 이상 merge될 수 없으므로 해시 테이블에서 제거되며 dispatch queue 내에서
디스크 섹터 번호를 기준으로 정렬된다 (단, 이미 처리 중이거나 REQ_SOFTBARRIER 플래그가 설정된
request들은 더 이상 정렬할 수 없으므로 그 이후의 request들만을 고려하게 된다).

dispatch queue 내의 request들은 순서대로 드라이버에 의해 처리되며
이렇게 request의 처리를 실제로 시작하는 것을 dispatch 혹은 issue라고 부른다.
dispatch된 request들은 REQ_STARTED 플래그를 추가로 설정하며 queue에서 제거되며
디스크 오류로 인해 request가 오랫동안 완료되지 못하는 경우를 방지하기 위해 타이머를 설정한다.

dispatch queue가 비게되면 드라이버는 I/O 스케줄러에게 새로운 request를 queue에 추가하도록 요청한다.
request가 더이상 존재하지 않거나 I/O 스케줄러가 dispatch queue로 전달하지 않으면 처리는 종료된다.

지금껏 블록 장치 I/O 연산이 전달되는 과정을 간략히 살펴보았는데
리눅스 커널의 블록 서브시스템 관리자이기도 한 Jens Axboe님이 만든 blktrace 도구를 이용하면
현재 시스템 내의 디스크 장치의 I/O 과정을 한 눈에 알아볼 수 있는 방법을 제공한다.

만일 기본적인 출력 내용을 터미널 상에서 확인하고 싶다면 단순히 btrace라는 스크립트를 이용할 수 있다.
그 외의 자세한 옵션은 blktrace 및 blkparse의 man 페이지를 참조하기 바란다.
아래는 내 시스템에서의 출력 내용 중 일부이다.

# btrace /dev/sda
  ...
  8,0    0       60    10.168088873   178  A  WS 353925552 + 8 <- (8,5) 46516656
  8,0    0       61    10.168089576   178  Q  WS 353925552 + 8 [jbd2/sda5-8]
  8,0    0       62    10.168097323   178  G  WS 353925552 + 8 [jbd2/sda5-8]
  8,0    0       63    10.168098432   178  P   N [jbd2/sda5-8]
  8,0    0       64    10.168100785   178  A  WS 353925560 + 8 <- (8,5) 46516664
  8,0    0       65    10.168101033   178  Q  WS 353925560 + 8 [jbd2/sda5-8]
  8,0    0       66    10.168102298   178  M  WS 353925560 + 8 [jbd2/sda5-8]
  8,0    0       67    10.168104627   178  A  WS 353925568 + 8 <- (8,5) 46516672
  8,0    0       68    10.168104843   178  Q  WS 353925568 + 8 [jbd2/sda5-8]
  8,0    0       69    10.168105513   178  M  WS 353925568 + 8 [jbd2/sda5-8]
  8,0    0       70    10.168106517   178  A  WS 353925576 + 8 <- (8,5) 46516680
  8,0    0       71    10.168106744   178  Q  WS 353925576 + 8 [jbd2/sda5-8]
  8,0    0       72    10.168107411   178  M  WS 353925576 + 8 [jbd2/sda5-8]
  8,0    0       73    10.168109205   178  A  WS 353925584 + 8 <- (8,5) 46516688
  8,0    0       74    10.168109435   178  Q  WS 353925584 + 8 [jbd2/sda5-8]
  8,0    0       75    10.168110081   178  M  WS 353925584 + 8 [jbd2/sda5-8]
  8,0    0       76    10.168111110   178  A  WS 353925592 + 8 <- (8,5) 46516696
  8,0    0       77    10.168111328   178  Q  WS 353925592 + 8 [jbd2/sda5-8]
  8,0    0       78    10.168111953   178  M  WS 353925592 + 8 [jbd2/sda5-8]
  8,0    0       79    10.168112970   178  A  WS 353925600 + 8 <- (8,5) 46516704
  8,0    0       80    10.168113266   178  Q  WS 353925600 + 8 [jbd2/sda5-8]
  8,0    0       81    10.168113923   178  M  WS 353925600 + 8 [jbd2/sda5-8]
  8,0    0       82    10.168115804   178  A  WS 353925608 + 8 <- (8,5) 46516712
  8,0    0       83    10.168116019   178  Q  WS 353925608 + 8 [jbd2/sda5-8]
  8,0    0       84    10.168116656   178  M  WS 353925608 + 8 [jbd2/sda5-8]
  8,0    0       85    10.168118495   178  A  WS 353925616 + 8 <- (8,5) 46516720
  8,0    0       86    10.168118722   178  Q  WS 353925616 + 8 [jbd2/sda5-8]
  8,0    0       87    10.168119371   178  M  WS 353925616 + 8 [jbd2/sda5-8]
  8,0    0       88    10.168121449   178  A  WS 353925624 + 8 <- (8,5) 46516728
  8,0    0       89    10.168121665   178  Q  WS 353925624 + 8 [jbd2/sda5-8]
  8,0    0       90    10.168122304   178  M  WS 353925624 + 8 [jbd2/sda5-8]
  8,0    0       91    10.168123327   178  A  WS 353925632 + 8 <- (8,5) 46516736
  8,0    0       92    10.168123554   178  Q  WS 353925632 + 8 [jbd2/sda5-8]
  8,0    0       93    10.168124212   178  M  WS 353925632 + 8 [jbd2/sda5-8]
  8,0    0       94    10.168125241   178  A  WS 353925640 + 8 <- (8,5) 46516744
  8,0    0       95    10.168125462   178  Q  WS 353925640 + 8 [jbd2/sda5-8]
  8,0    0       96    10.168126087   178  M  WS 353925640 + 8 [jbd2/sda5-8]
  8,0    0       97    10.168128954   178  I  WS 353925552 + 96 [jbd2/sda5-8]
  8,0    0        0    10.168131125     0  m   N cfq178 insert_request
  8,0    0        0    10.168131926     0  m   N cfq178 add_to_rr
  8,0    0       98    10.168133660   178  U   N [jbd2/sda5-8] 1
  8,0    0        0    10.168135051     0  m   N cfq workload slice:100
  8,0    0        0    10.168136148     0  m   N cfq178 set_active wl_prio:0 wl_type:1
  8,0    0        0    10.168136908     0  m   N cfq178 Not idling. st->count:1
  8,0    0        0    10.168138014     0  m   N cfq178 fifo=          (null)
  8,0    0        0    10.168138615     0  m   N cfq178 dispatch_insert
  8,0    0        0    10.168139739     0  m   N cfq178 dispatched a request
  8,0    0        0    10.168140355     0  m   N cfq178 activate rq, drv=1
  8,0    0       99    10.168140588   178  D  WS 353925552 + 96 [jbd2/sda5-8]
  8,0    0      100    10.168534375     0  C  WS 353925552 + 96 [0]
  8,0    0        0    10.168554570     0  m   N cfq178 complete rqnoidle 1
  8,0    0        0    10.168555455     0  m   N cfq178 set_slice=120
  8,0    0        0    10.168556271     0  m   N cfq178 Not idling. st->count:1
  8,0    0        0    10.168556774     0  m   N cfq schedule dispatch
  ...

여기서 주의깊게 봐야할 부분은 알파벳 약자로 이루어진 6번째와 7번째 열 부분이다.
6번째 열이 나타내는 것은 해당 request가 처리되는 과정을 나타내며 (아래에서 설명)
7번째 열이 나타내는 것은 request의 종류로 여기서 WS는 sync write, N은 none에 해당한다.

6번째 열을 자세히 살펴보면 약간의 규칙성을 발견할 수 있는데 (첫번째 request는 제외)
먼저 A는 remap의 약자로 (8,5) 즉 /dev/sda5 파티션에 대한 I/O가
/dev/sda 디스크 전체에 대한 위치로 변환된 것을 뜻한다.
다음은 Q인데 이것은 queue의 약자로 make_request_fn이 실행되어 bio의 처리가 시작되었음을 뜻한다.
다음은 G인데 이것은 get (request)의 약자로 request 구조체가 하나 할당되었음을 뜻한다.
다음은 P인데 이것은 plug의 약자로 request가 plugged list에 포함되었음을 뜻한다.

이후의 요청들은 모두 A -> Q -> M의 과정을 거치는데, A와 Q는 위와 동일하고
M은 merge의 약자로 요청된 bio가 (앞선) request와 통합되었음을 뜻하는 것이며
8번째 열은 해당 bio의 시작 섹터 번호 및 크기임을 고려하면 연속된 요청이란 것을 쉽게 알 수 있다.

그 아래쪽에 I가 보이는데 이것은 insert의 약자로 앞서 생성(되고 merge)된 request가
I/O 스케줄러에게 전달되었음을 뜻한다. 그 바로 아래는 실제 request가 아닌 message를 의미하는
m이 있으며 (이는 CFQ 스케줄러에서 출력한 메시지이다) 지금은 무시하고 넘어가도 좋다.
다음은 U인데 이것은 unplug의 약자로 plugged list 내의 request들을 I/O 스케줄러에게 모두 전달했음을 뜻한다.
다음은 D인데 이것은 dispatch의 약자로 드라이버에게 I/O 연산의 실행을 시작하라고 요청하였음을 뜻한다.
다음은 C인데 이것은 complete의 약자로 dispatch된 request의 처리가 완료되었음을 뜻하는 것이다.

위의 경우 8섹터 (= 4KB) 크기의 bio 12개가 순서대로 요청되어 96섹터 (= 48KB) 크기의 한 request로
merge된 후 한 번에 처리되는 것을 볼 수 있었다.

지금까지 살펴본 과정을 그림으로 나타내면 다음과 같다.