Block I/O Operation

Original Source: http://studyfoss.egloos.com/5575220, http://studyfoss.egloos.com/5576850, http://studyfoss.egloos.com/5583458, http://studyfoss.egloos.com/5585801

Block I/O Operation

블록 장치는 개별 바이트 단위가 아닌 일정 크기(block) 단위로 접근하는 장치를 말하는 것으로 간단히 말하면 하드 디스크와 같은 대용량 저장 장치를 말한다. 전통적으로 이러한 블록 장치는 다른 (문자) 장치처럼 직접 다루는 대신 파일 시스템이라고 하는 추상화 계층을 통해 간접적으로 접근하게 되며 따라서 프로그래머는 해당 저장 장치가 어떠한 종류의 장치인지와는 무관하게 (또한 VFS에 의해 어떠한 파일 시스템인지와도 무관하게) 일관된 방식으로 (즉, 파일 및 디렉터리의 형태로) 이용하게 된다.

리눅스의 VFS 계층은 디스크 접근을 최소화하기 위해 페이지 캐시를 이용하여 한 번 접근한 디스크의 내용을 저장해 둔다. 하지만 여기서는 이러한 페이지 캐시의 작용은 건너뛰고 실제로 블록 장치와 I/O 연산을 수행하는 경우에 대해서 살펴보게 될 것이다.

블록 I/O의 시작 지점은 submit_bio() 함수이다. (일반적인 파일 시스템의 경우 buffer_head (bh)라는 구조체를 통해 디스크 버퍼를 관리하는데 이 경우 submit_bh() 함수가 사용되지만 이는 bh의 정보를 통해 bio 구조체를 할당하여 적절히 초기화한 후 다시 submit_bio() 함수를 호출하게 된다.)

이 함수는 I/O 연산의 종류 (간단하게는 READ 혹은 WRITE) 및 해당 연산에 대한 모든 정보를 포함하는 bio 구조체를 인자로 받는다. bio 구조체는 기본적으로 I/O를 수행할 디스크 영역의 정보와
I/O를 수행할 데이터를 저장하기 위한 메모리 영역의 정보를 포함한다. 여기서 몇가지 용어가 함께 사용되는데 혼동의 여지가 있으므로 간략히 정리하고 넘어가기로 한다.

먼저 섹터(sector)라는 것은 장치에 접근할 수 있는 최소의 단위이며 (H/W적인 특성이다) 대부분의 장치에서 512 바이트에 해당하므로, 리눅스 커널에서는 섹터는 항상 512 바이트로 가정하며 sector_t 타입은 (512 바이트의) 섹터 단위 크기를 나타낸다. (만약 해당 장치가 더 큰 크기의 섹터를 사용한다면 이는 장치 드라이버에서 적절히 변환해 주어야 한다)

블록(block)은 장치를 S/W적으로 관리하는 (즉, 접근하는) 크기로 섹터의 배수이다. 일반적으로 파일 시스템 생성 (mkfs) 시 해당 파일 시스템이 사용할 블록 크기를 결정하게 되며 현재 관리의 용이성을 위해 블록 크기는 페이지 크기 보다 크게 설정될 수 없다. 즉, 일반적인 환경에서 블록의 크기는 512B(?), 1KB, 2KB, 4KB 중의 하나가 될 것이다. 하나의 블록은 디스크 상에서 연속된 섹터로 이루어진다.

세그먼트(segment)는 장치와의 I/O 연산을 위한 데이터를 저장하는 "메모리" 영역을 나타내는 것으로 일반적으로는 페이지 캐시 내의 일부 영역에 해당 할 것이다. 하나의 블록은 메모리 상에서 동일한 페이지 내에 저장되지만 하나의 I/O 연산은 여러 블록으로 구성될 수도 있으므로 하나의 세그먼트는 (개념적으로) 여러 페이지에 걸칠 수도 있다.

블록 I/O 연산은 기본적으로 디스크에 저장된 데이터를 메모리로 옮기는 것 (READ) 혹은 메모리에 저장된 데이터를 디스크로 옮기는 것 (WRITE)이다. (장치의 특성에 따라 FLUSH, FUA, DISCARD 등의 추가적인 연산이 발생될 수도 있다.) I/O 연산이 여러 블록을 포함하는 경우 약간 복잡한 문제가 생길 수 있는데 이러한 블록 데이터가 디스크 혹은 메모리 상에서 연속되지 않은 위치에 존재할 수 있기 때문이다.

예를 들어 파일 시스템을 통해 어떠한 파일을 읽어들이는 경우를 생각해보자. 파일을 연속적으로 읽어들인다고 해도 이는 VFS 상에서 연속된 것으로 보이는 것일 뿐 실제 데이터는 디스크 곳곳에 흩어져있을 수도 있다. (많은 파일 시스템은 성능 향상을 위해 되도록 연속된 파일 데이터를 디스크 상에서도 연속된 위치에 저장하려고 시도하지만 시간이 지날 수록 단편화가 발생하므로 결국에는 어쩔 수 없이 이러한 현상이 발생하게 될 것이다.)

또한 디스크에서 읽어들인 데이터는 페이지 캐시 상에 저장되는데 페이지 캐시로 할당되는 메모리는 항상 개별 페이지 단위로 할당이 이루어지므로 메모리 상에서도 연속된 위치에 저장된다고 보장할 수 없다.

따라서 bio 구조체는 이러한 상황을 모두 고려하여 I/O 연산에 필요한 정보를 구성한다. 우선 하나의 bio은 디스크 상에서 연속된 영역 만을 나타낼 수 있다. 즉, 접근하려는 연속된 파일 데이터가 디스크 상에서 3부분으로 나뉘어져 있다면 세 개의 bio가 각각 할당되어 submit_bio() 함수를 통해 각각 전달될 것이다.

블록 I/O 연산 시 실제 데이터 복사는 대부분 DMA를 통해 이루어지게 되는데 이 때 (DMA를 수행하는) 장치는 물리 주소를 통해 메모리에 접근하게 되므로 설사 파일 매핑을 통해 파일 데이터를 저장한 페이지들이 (해당 프로세스의) 가상 메모리 상에서 연속된 위치에 존재한다고 하더라도 떨어진 페이지 프레임에 존재한다면 별도의 세그먼트로 인식할 것이다.

구식 장치의 경우 DMA를 수행할 때 디스크는 물론 메모리 상에서도 연속된 하나의 세그먼트 만을 지원했었다. 따라서 디스크 상에서 연속된 위치에 저장된 데이터라고 하더라도 메모리 상에서 연속되지 않았다면 하나의 I/O 연산을 통해 처리할 수 없는 상황이 발생하므로 여러 연산으로 분리해야 했었다. 하지만 장치가 scatter-gather DMA를 지원하거나 IO-MMU를 포함한 머신이라면 얘기가 달라진다. 현재 bio는 세그먼트를 bio_vec 구조체를 통해 저장하는데 세그먼트는 기본적으로 페이지의 형태로 저장되므로 이에 대한 모든 정보가 포함되며 장치가 한 I/O 당 여러 세그먼트를 지원할 수 있으므로 이를 배열(vector) 형태로 저장한다. 혹은 우연히도 디스크 상에 연속된 데이터가 메모리 상에서도 연속된 페이지에 저장되었을 수도 있다. 이 경우 별도의 페이지로 구성되었어도 물리적으로는 하나의 세그먼트로 처리한다. 또는 IO-MMU를 통해 떨어져있는 페이지들을 하나의 세그먼트 (연속된 주소)로 매핑할 수도 있다.

위 그림은 지금껏 설명한 bio의 구성을 보여준다. (설명을 간단히하기 위해 블록 크기와 페이지 크기가 동일한 환경을 고려하며 장치는 scatter-gather DMA 등을 통해 여러 세그먼트를 동시에 처리할 수 있다고 가정한다) 연속된 파일 주소 공간에 대한 I/O 요청은 디스크 상의 위치를 기준으로 3개의 bio로 나뉘어졌으며 각 bio는 해당 영역의 데이터를 담는 세그먼트를 여러 개 포함할 수 있다.

이번에는 submit_bio() 함수를 통해 bio가 전달되는 과정을 들여다보기로 하자.

submit_bio() 함수는 주어진 I/O 연산의 종류를 bio 구조체에 저장한 뒤 generic_make_request() 함수를 호출한다. I/O 연산의 종류 및 그에 따른 특성을 나타내기 위해 bio와 request 구조체는 REQ_* 형태의 플래그를 공유하며 이는 rq_flag_bits 열거형을 통해 정의되어 있고 위에서 설명한 I/O 연산 매크로들은 이 플래그들을 조합하여 만들어진다.

generic_make_request() 함수는 주어진 bio에 대해 장치 드라이버에 제공하는 방식(make_request_fn 콜백)을 통해 request를 만들어내는 작업을 수행한다.

여기서 bio는 앞서 살펴보았듯이 상위 계층 (VFS)에서 요청한 블록 I/O 연산에 대한 정보를 담고 있는 것이며 request는 실제로 장치 드라이버에서 장치와 실제 I/O 작업을 수행하는 것에 필요한 정보를 담고 있는 구조체이다.

이전 글에서 언급했듯이 블록 장치는 상대적으로 연산 속도가 매우 느리기 때문에 상위 계층에서 요청한 작업을 즉시 수행하지 않고 (I/O 스케줄러를 통해) 순서를 조정하게 되며 이 과정에서 여러 번에 걸쳐 요청된 bio들이 하나의 request로 합쳐지게 되는 경우도 있다.

이러한 작업들을 모두 처리하는 함수가 generic_make_request() 함수로써 장치 드라이버에서 I/O 연산에 필요한 여러 준비 작업들을 수행하게 되는데 몇몇 특별한 장치의 경우 이 과정이 재귀적으로 일어날 수 있기 때문에 이에 대한 대비를 위해 실제 처리는 __generic_make_request() 함수로 분리하였다.

S/W RAID (리눅스 커널에서는 MD (Multple Disks)라고 부른다) 또는 DM (Device Mapper)과 같은 장치는 커널에서 제공하는 특수 장치로 여러 물리적인 디스크 장치를 묶어서 마치 하나의 장치인 것 처럼 관리하는데, 이러한 장치에 대한 I/O 연산은 하위에 존재하는 여러 개의 실제 장치에 대한 I/O 연산으로 변경(clone)되어 수행되기도 하므로 이에 대한 재귀적인 처리 과정에서 커널 스택이 소진되는 문제가 발생할 수 있다. (direct-reclaim 시의 writeback과 같은 경우 이미 많은 양의 커널 스택이 사용된 상황일 것이다)

참고로 블록 계층에서의 메모리 할당은 매우 조심스럽게(?) 이루어지는데 앞서 말했다시피 이미 시스템의 메모리가 부족해진 상황에서 캐시로 사용되던 페이지들을 다른 용도로 재사용하기 위해 기존의 내용을 디스크에 기록해야 하는 경우가 많은데 이 때 디스크 I/O가 처리되기 때문이다. 즉, 메모리가 부족한 상황에서 메모리를 회수해야 하는 태스크가 (I/O 처리 과정에 필요한) 새로운 메모리를 요청하게 되는데 이미 메모리가 부족하므로 할당이 성공할 수 없고 따라서 해당 태스크가 대기 상태로 빠져 deadlock이 발생할 수 있는 문제를 안게 된다.

그래서 블록 I/O 처리 경로에서의 메모리 할당은 일반적으로 사용하는 GFP_KERNEL 매크로가 아닌,(I/O를 발생시키지 않는) GFP_NOIO 매크로를 통해 이루어지며 많은 경우 memory pool과 같은 기법을 이용하여 최악의 상황에서도 사용할 수 있도록 필요한 객체들을 사전에 미리 할당해 두는 방식을 사용한다.

generic_make_request() 함수는 현재 실행되는 태스크가 해당 함수를 재귀적으로 호출했는지 검사하기 위해 먼저 task_struct의 bio_list 필드를 검사한다.이 값이 NULL이 아니라면 재귀적으로 호출된 경우이므로 리스트에 현재 bio를 추가하고 종료한다. 그렇지 않다면 최초 호출이므로 스택에 할당된 bio_list 구조체로 bio_list 필드를 설정하고 실제로 요청을 처리하기 위해 __generic_make_request() 함수를 호출하며 호출이 완료된 후에는 그 사이에 재귀적으로 추가된 bio가 있는지 검사하여 있다면 이를 다시 수행한다. 리스트 내에 더 이상 bio가 존재하지 않는다면 bio_list 필드를 NULL로 설정하고 종료한다.

__generic_make_request() 함수도 또한 하나의 loop로 구현되어 있는데 마찬가지로 MD 혹은 DM과 같은 장치에서 해당 장치에 대한 I/O 요청을 그 하위의 실제 장치에 대한 I/O 요청으로 변경(remap)하는 경우가 있기 때문이다. 장치 드라이버는 주어진 bio를 실제 장치가 처리하기 위한 request로 만들기 위해 make_request_fn 콜백을 제공하는데 정상적인 경우 이 콜백 함수는 0을 리턴하여 loop 내부를 1번 만 수행하고 바로 종료한다. 하지만 위에서 말한 특수한 장치의 경우 0이 아닌 값을 리턴하여 bio가 다른 장치로 remap 되었음을 알려주면 다시 loop 내부를 수행하여 새로운 장치에 대해 필요한 검사를 수행한다.

loop 내부에서는 bio가 요청한 장치가 현재 사용 가능한 상태인지, 요청한 블록이 장치의 범위를 넘어서는지, FLUSH, FUA, DISCARD와 같은 특수 기능을 장치가 제공하는지 등을 검사하며 I/O를 요청한 장치가 디스크 파티션이라면 이를 전체 디스크에 대한 위치로 재조정한다. 또한 fault injection에 의한 I/O 요청 실패 상황을 검사하거나 block throttling 정책에 따라 현재 요청된 I/O를 잠시 대기 시킬 것인지 여부를 결정하게 된다.

이러한 모든 단계가 정상적으로 완료되면 드라이버에서 제공하는 make_request_fn 콜백을 호출한다.
일반적인 디스크 장치는 기본 구현인 __make_request() 함수를 콜백으로 등록하게 되며 이 과정에서 현재 bio를 장치에 전달하기 위해 필요한 request를 찾거나 새로 생성한다.

하지만 위에서 말한 MD 및 DM과 같은 복잡한 장치들은 물론 일반 파일을 디스크처럼 다루는 loop 장치와 메모리를 다루는 RAM 디스크 장치 (brd 모듈) 등은 request를 생성하지 않고 bio 구조체를 직접 이용하여 I/O 연산을 수행한다.

예를 들어 MD 장치의 구성 중에 여러 디스크를 마치 하나의 디스크인 것처럼 연결하는 linear 모드
(MD의 용어로는 personality라고 한다)가 있다. 이 경우 MD 장치로 들어온 요청은 make_request_fn 콜백으로 등록된 md_make_request() 함수에서 처리되는데 이는 다시 해당 장치의 personality에서 제공하는 make_request 콜백을 호출하여 결국 linear_make_request() 함수가 호출되게 된다.

linear_make_request() 함수는 MD 장치의 블록 번호에 해당하는 실제 장치를 찾은 후에 bio의 장치 및 섹터 정보를 적절히 변경하고 1을 리턴한다. 그러면 __generic_make_request() 함수 내의 loop가 새로운 장치에 대해 다시 수행되어 실제 디스크 장치로 I/O 요청이 전달되는 것이다. 만일 MD 장치에 대한 요청이 linear 모드로 연결된 실제 장치의 경계에 걸친 경우 이는 내부적으로 두 개의 bio로 분할되고 (bio_split() 함수 참고), 각각의 장치에 대해 다시 generic_make_request() 함수를 호출하므로 task_struct의 bio_list에 연결된 후 차례로 처리될 것이다.

bio를 통해 전달된 I/O 연산 요청은 각 블록 장치 드라이버에서 제공하는 make_request_fn 콜백을 통해 처리되는데 일반적인 디스크 장치의 경우 __make_request() 함수가 request를 할당하고 buffer bouncing, plugging, merging 등의 공통적인 작업을 처리한 후 이를 (elevator라고도 부르는) I/O 스케줄러에게 넘겨주게 된다. 여기서는 이 __make_request() 함수에 대해서 알아보기로 할 것이다.

가장 먼저 blk_queue_bounce() 함수를 통해 디스크 장치의 특성에 따라 페이지를 더 할당하는데
오래된 ISA 방식의 디스크인 경우 디스크 장치가 DMA를 통해 접근할 수 있는 주소의 범위가
16MB (24bit) 밖에 되지 않기 때문이다. (동일한 문제는 64bit 시스템의 PCI 장치에서도
4GB 이상의 메모리가 존재하는 경우에 발생할 수 있다.)

이 경우 전달된 bio의 세그먼트에 해당하는 페이지를 장치가 접근할 수 없으므로 접근할 수 있는 영역의 페이지 (ZONE_DMA/DMA32)를 새로 할당한 후 (이를 bounce buffer라고 한다) 이를 이용하여 실제 I/O를 대신 처리하는 방법을 사용해야 한다.

이 과정이 완료되면 I/O 요청을 드라이버에게 전달하기 위해 request 구조체를 할당하게 되는데 그 전에 기존의 request에 현재 bio가 merge 될 수 있는지를 먼저 검사하게 된다. 일단 request 구조체에 대해서 먼저 간략히 살펴볼 필요가 있다.

request 구조체는 기본적으로는 (bio와 동일하게) 디스크 상에서 연속된 영역에 해당하는 I/O 연산 요청에 대한 정보를 포함하는데 추가적으로 드라이버에서 사용할 여러 low-level 자료 구조를 포함/참조하고 있다. 특히나 세그먼트 정보는 이미 bio 구조체에 저장되어 있으므로 이를 그대로 이용하며
만약 연속된 디스크 영역에 여러 bio가 전달된 경우 이를 하나의 리스트로 연결하여 관리한다.

아래는 전체 request 구조체 중에서 현재 관심있는 부분 만을 표시한 것이다.

include/linux/blkdev.h:

struct request {
    struct list_head queuelist;

    ...

    struct request_queue *q;

    unsigned int cmd_flags;
    enum rq_cmd_type_bits cmd_type;

    ...

    ⁄* the following two fields are internal, NEVER access directly *⁄
    unsigned int __data_len;    ⁄* total data len *⁄
    sector_t __sector;          ⁄* sector cursor *⁄

    struct bio *bio;
    struct bio *biotail;

    struct hlist_node hash;      ⁄* merge hash *⁄

    ⁄*
     * The rb_node is only used inside the io scheduler, requests
     * are pruned when moved to the dispatch queue. So let the
     * completion_data share space with the rb_node.
     *⁄
    union {
        struct rb_node rb_node;    ⁄* sort/lookup *⁄
        void *completion_data;
    };

    ...

    ⁄* Number of scatter-gather DMA addr+len pairs after
     * physical address coalescing is performed.
     *⁄
    unsigned short nr_phys_segments;

    ...
};

request는 궁극적으로 해당 장치에서 제공하는 request_queue로 전달되어 처리되는데 (실제로 전달되는 순서는 I/O 스케줄러에서 조정한다) q 필드는 이 request가 전달될 큐를 가리키며 queuelist 필드는 request_queue 내의 리스트를 관리하기 위해 필요한 포인터이다. cmd_flags는 앞서 bio에서 살펴보았듯이 해당 I/O 연산의 특성을 알려주는 REQ_* 형태의 플래그이며 cmd_type은 일반적인 경우 REQ_TYPE_FS 값으로 설정된다. (filesystem 연산)

__sector는 해당 request가 접근하는 디스크 상의 위치를 섹터 단위로 저장한 것이며 __data_len은 해당 request가 처리하는 데이터의 길이를 바이트 단위로 저장한 것이다. (이 필드들은 드라이버에서 요청을 처리하는 도중에 갱신될 수 있으므로 외부에서 접근하면 안된다)

bio와 biotail은 해당 request에 포함된 bio의 목록으로 merge 시에 확장될 수 있으며 hash는 merge할 request를 빨리 찾을 수 있도록 해시 테이블을 구성하기 위해 필요하다. (merge 과정에 대해서는 잠시 후에 살펴볼 것이다.)

rb_node 필드는 I/O 스케줄러가 request를 디스크 상의 위치를 통해 정렬하기 위해 사용되며 nr_phys_segments는 해당 request가 포함하는 총 메모리 세그먼트의 수를 저장한다.

이제 merge 과정에 대해서 알아보기로 하자. submit_bio() 함수를 통해 요청된 (최초) bio는 request 형태로 변경될 것이다. 그런데 바로 후에 (아마도 filesystem 계층에서) 디스크 상에서 연속된 영역에 대해 다시 submit_bio()를 호출하여 bio를 요청하는 경우가 있을 수 있다.

이 경우 최초에 생성된 request에 두 번째로 요청된 bio가 포함되게 되며 __sector 및 __data_len 필드는 필요에 따라 적절히 변경될 것이고 bio와 biotail 필드는 각각 첫번째 bio와 두번째 bio를 가리키게 될 것이다. (각각의 bio는 내부의 bi_next 필드를 통해 연결된다)

그럼 문제는 주어진 bio를 merge할 request를 어떻게 찾아내느냐 인데 (위에서 설명한 아주 단순한 경우는 바로 이전에 생성된 request를 찾은 경우였지만 디스크 접근 패턴이 복잡한 경우는 여러 request들을 검색해 보아야 할 것이다.) 이를 위해 기본적으로 각 디스크의 I/O 스케줄러는 (위에서 언급한) 해시 테이블을 유지한다.

해시 테이블은 request가 접근하는 가장 마지막 섹터의 경계를 기준으로 구성하는데 이는 디스크 접근이 보통 섹터 번호가 증가하는 순으로 이루어지는 경우가 많기 때문일 것이다. 이 경우 원래의 request가 접근하는 제일 뒤쪽에 새로운 bio가 연결되므로 이를 back merge라고 부른다. 반대로 원래의 request보다 앞쪽에 위치하는 bio가 요청된 경우를 front merge라고 한다. back merge의 경우는 항상 가능하지만 front merge의 경우는 I/O 스케줄러에 따라 허용하지 않을 수도 있다. 물론 이 외에도 merge가 되려면 해당 request와 bio는 호환가능한 속성을 가져야 한다.

또한 sysfs를 통해 I/O 스케줄러의 merge 시도 여부를 제어할 수가 있는데예를 들어 sda라는 디스크의 경우 /sys/block/sda/queue/nomerges 파일의 값에

• 0을 쓰면 항상 (해시 테이블을 검색하여) 가능한 경우 merge를 허용하고,
• 1을 쓰면 바로 이전에 생성 또는 merge된 request와의 merge 만을 허용하며
• 2를 쓰면 merge를 허용하지 않게 된다.

하지만 이러한 I/O 스케줄러의 해시 테이블은 각 디스크 별로 유지되기 때문에 해당 디스크에 접근하려는 여러 태스크는 동기화를 위해 lock을 필요로하게 된다. 이는 많은 디스크 I/O가 발생하는 시스템에서 성능 상 좋지 않은 효과를 줄 수 있는데 이를 위해 이러한 공유 해시 테이블에 접근하기 전에 먼저 각 태스크 별로 유지하는 plugged list를 검사하여 merge가 가능한 request가 존재하는지 확인하게 된다.

plugged list는 이른바 'block device plugging'이라는 기능을 구현한 것인데 이는 디스크의 동작 효율을 높이기 위한 기법으로, 디스크가 idle 상태였다면 request가 요청된 즉시 처리하지 않고 조금 더 기다림으로써 여러 request를 모아서 한꺼번에 처리하거나 merge될 시간을 벌어주는 효과를 얻게 된다.

즉, 디스크에 대한 접근이 발생하면 plugged 상태로 되어 I/O 스케줄러가 잠시 request를 보관하며
이후 특정 조건이 만족된 경우 (일정 시간이 경과하거나, 충분히 많은 I/O 요청이 발생한 경우) 장치가 (자동으로) unplug되어 주어진 request들을 실제로 처리하기 시작하는 형태였다.

하지만 2.6.39 버전부터 plugging 방식이 태스크가 직접 unplug 하는 식으로 변경되면서 태스크 별로 I/O 스케줄러에 request를 넘기기 전에 자신이 생성한 request를 리스트 형태로 유지하게 되었다. 따라서 이는 공유되지 않으므로 불필요한 lock contention을 줄일 수 있다.

단 이 per-task plugging 방식은 선택적인 것이므로 __make_request() 실행 당시 해당 태스크는 이 기능을 이용하지 않을 수도 있다.

이렇게 plugged list와 I/O 스케줄러 (혹은 엘리베이터)의 request를 검색한 후에도 merge할 마땅한 request를 찾지 못했다면 해당 bio를 위한 request를 새로 생성한다. 마찬가지로 request 구조체를 할당할 때도 GFP_NOIO 플래그를 사용하며 mempool 인터페이스를 사용하여 비상 시를 위한 여분의 구조체를 미리 준비해 둔다.

또한 각 디스크 (request_queue)에는 처리할 수 있는 request의 최대값이 정해져 있어서 그 이상 request를 생성하지 못하도록 제어하는데 기본값으로는 BLKDEV_MAX_RQ (128)이 사용되며 이에 따라 해당 디스크의 congestion 상태를 판단하기 위한 threshold 값이 결정된다. 이 경우 113개 이상의 request가 대기 중이면 디스크가 병목 현상을 겪고 있다고 판단하며 대기 중인 request의 수가 다시 103개 이하로 떨어지면 정상 상태로 회복되었음을 인식한다.

따라서 request 할당 시 이 threshold 값을 보고 적절히 디스크 상태를 설정하여 상위 계층에서 I/O 요청을 생성하는 속도를 조절할 수 있도록 하고 있다.

만약 병목 현상이 일어나고 있는 상황에서도 계속 I/O 요청이 발생하여 결국 할당된 request의 수가 최대값에 다다르면 디스크 (request_queue)가 가득찼음을 나타내는 플래그를 설정하여 더 이상 request를 생성하지 못하도록 하되, 단 현재 태스크는 batcher task로 설정하여 얼마간의 (함께 요청된) request를 더 생성할 수 있도록 배려하고 있다. 또한 request 할당 시 메모리 부족으로 인해 잠시 sleep되었던 경우에도 해당 태스크를 batcher task로 설정한다.

이렇게 request를 할당받고 난 후에는 per-task plugging을 이용하는 경우라면 해당 request를 plugged list에 연결하고 그렇지 않은 경우라면 I/O 스케줄러에 전달한 뒤 바로 디스크 드라이버에게 I/O를 요청한다.

지금까지 상위 (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된 후 한 번에 처리되는 것을 볼 수 있었다.

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