Linux kernel v4.4에서 간단한 블록 장치 드라이버 만들어보기

radix tree를 이용해서 페이지 저장하기

radix tree 자료구조 소개

참고: https://lwn.net/Articles/175432/

일반적인 radix tree 자료구조가 아니라 리눅스에서 구현된 radix tree를 기준으로 설명하겠습니다.

radix tree는 페이지를 저장하는 자료구조입니다. 드라이버에서 페이지를 할당하고, 이 페이지를 키 값을 지정해서 트리에 저장합니다. 그리고 나중에 키 값을 이용해서 다시 해당 페이지를 찾는 것이지요. 구현이나 좀더 다양한 활용법은 참고 링크를 확인하시고, 우리는 그냥 페이지를 저장했다가 찾는 간단한 기능만 사용하겠습니다.

struct radix_tree_root

트리의 루트를 표현하는 구조체입니다. INIT_RADIX_TREE 매크로로 초기화합니다.

radix_tree_preload()/_end()/radix_tree_insert()

radix-tree에 페이지를 넣는게 radix_tree_inset() 함수입니다. 사용법은 간단합니다. 루트 노트의 주소와 페이지의 키값, 페이지 포인터만 지정하면 됩니다. 키 값을 뭘로 정할지는 드라이버가 알아서하면 됩니다. 잠시후 보겠지만 우리는 섹터 번호를 키 값으로 사용합니다. 왜냐면 디스크에서 유니크한 값이 섹터 번호니까요.

그런데 radix_tree_preload()라는게 있습니다. 꼭 필요한건 아니지만 많이 사용되는 함수입니다. 참고 문서를 보시면 radix_tree_insert()가 실패하면 안되는 상황에서 사용한다고 설명하고 있습니다. 트리에 어떤 데이터를 넣으려면 트리 노드를 표현하는 객체를 만들어야됩니다. 따라서 메모리 할당을 해야합니다. radix_tree_preload()는 메모리 할당을 미리 해놓는 것입니다. 트리란건 사실 데이터와 키 값을 저장하는 자료구조중에 속도가 필요할 때 쓰는 것입니다. 그런데 트리에 데이터를 넣을때마다 메모리 할당을 한다면 속도도 느려지고, 트리에 대한 동기화 문제도 복잡해집니다. 메모리 할당은 메모리가 부족한 경우 프로세스를 잠들게 할 수 있습니다. 만약 락이 걸린 상태에서 잠든다면 데드락의 가능성도 생기고 문제가 많아집니다.

그래서 preload를 합니다. 만약 preload가 실패한다면 메모리가 부족한 상황이므로 트리에 접근을 안하고 그러면 동기화 문제가 없어집니다. preload가 성공한다면 메모리 부족으로 실패할 일은 없으니 크리티컬 섹션에서 프로세스가 잠들 일도 없습니다.

그래서 결론은 radix_tree_preload()를 호출한 후에 성공하면 radix_tree_insert()를 호출하도록 구현한다는 것입니다. radix_tree_insert() 다음에는 radix_tree_preload_end()를 반드시 호출해야합니다. 왜인지는 커널 소스를 보시면 아시게 됩니다.

참고로 커널에서 뭔가 이거다음에 반드시 이거를 호출해라라고 규정할 때가 자주 있습니다. 이런건 반드시 지켜야합니다. 대부분 동기화와 관련되있어서 문제가 발생할 경우 디버깅하기가 어렵습니다. 그리고 커널 문서에 그런 사항들이 모두 기록된게 아닙니다. 왜냐면 코드가 자주 바뀌는 부분은 문서 자체를 아예 안만드니까요. 주석으로 설명하는 것도 한계가 있습니다. 가장 좋은 방법은 다른 드라이버 코드를 참고하는 것입니다. 소스 태깅 툴로 radix_tree_preload()를 호출하는 다른 코드들을 확인해보세요. 어떤 커널 함수를 사용할 때는 그 함수를 이미 사용하는 다른 코드를 찾아보는게 가장 좋은 레퍼런스가 됩니다. 문서나 주석은 바뀐 코드를 반영하지 않을 수 있지만, 코드 자체는 항상 옳으니까요.

radix_tree_lookup()

트리에서 특정 키 값을 갖는 페이지를 찾는 함수입니다. 사용법도 간단합니다. 루트와 키 값만 전달하면 페이지 포인터를 반환합니다.

mybrd_lookup_page()

모든 IO는 섹터단위로 이루어집니다. 몇번 섹터에서 몇개의 섹터를 읽기/쓰기가 IO가 동작하는 방식입니다. 따라서 radix-tree의 키 값도 섹터가 되야합니다.

mybrd_lookup_page()는 트리에서 특정 섹터의 데이터를 가지고 있는 페이지를 찾는 함수입니다. 함수 인자로 섹터 번호를 지정하면 그 섹터를 포함하고 있는 페이지를 반환합니다.

함수 내부를 보겠습니다. 먼저 rcu_read_lock()이 보입니다. RCU lock에 대해서는 다음 문서로 설명을 대신하겠습니다.

https://lwn.net/Articles/262464/

rcu_read_lock()의 핵심은 트리를 읽는 쓰레드는 배타적으로 실행될 필요없이 동시에 실행될 수 있다는 것입니다. 트리에서 페이지를 찾는 동작은 트리를 읽기만하지 뭔가를 바꾸지 않습니다. 따라서 rcu_read_lock()를 사용할 수 있습니다.

그 다음은 섹터 번호를 가지고 키 값을 만드는 것입니다. 하나의 페이지에는 4096바이트이고 섹터는 512바이트이므로 총 8개의 섹터가 저장될 수 있는데 이중에 어떤 섹터 번호를 키 값으로 할거냐가 문제가 됩니다. 우리는 항상 페이지에 저장되는 최초의 섹터 번호를 키값을 정하겠습니다. 따라서 (섹터번호*512/4096)라는 공식이 생성됩니다.

예로 몇개의 (섹터 키) 값의 쌍을 한번 계산해보겠습니다.

0 0

7 0

8 1

9 1

16 2

이걸 비트 연산 코드로 만들면 sector >> (12 - 9) 가 됩니다. 그런데 페이지 크기는 플랫폼마다 다를 수 있습니다. 커널에서는 플랫폼마다 다른 페이지 크기를 매크로로 정의하고 있습니다. PAGE_SIZE, PAGE_SHIFT등의 매크로를 사용하면 플랫폼 상관없이 페이지 크기를 확인할 수 있습니다. 따라서 최종 코드는 sector >> (PAGE_SHIFT - 9)가 됩니다.

키 값을 계산했으면 radix_tree_lookup()을 호출해서 페이지를 찾습니다. 페이지가 없을 수 있습니다. 아직 해당 섹터에 데이터를 안쓴것입니다.

mybrd_insert_page()

트리에 페이지를 추가합니다. 가장 먼저 이미 해당 섹터가 트리에 있는지를 확인합니다. 트리에 찾고자하는 페이지가 없다면 먼저 페이지를 할당합니다. 

페이지 할당에서 중요한 사항이 바로 할당 플래그입니다. 우리는 디스크 IO를 처리하는 드라이버를 만들고있으므로 GFP_NOIO 플래그를 사용해야합니다. 그 이유는 김민찬님의 강좌에서 잘 설명하고 있습니다.

https://www.linux.co.kr/home2/board/subbs/board.php?bo_table=lecture&wr_id=1641

GFP_NOIO와 GFP_NOFS는 현 재 메모리가 모자라 회수를 해야 되는 상황인데 함수를 호출한 context가 block I/O code라던가 파일시스템 코드 일경우 사용되게 된다. 예를 들면, block I/O의 코드 중에 buffer_head를 할당하는 함수가 있다. 그 경우, 커널이 buffer_head를 할당하려다가 메모리가 모자라다는 것을 알아 차렸다면 페이지 회수 알고리즘이 동작하기 시작하게 된다. 이때 메모리를 회수하기 위해 page cache에 있는 페이지들중 dirty 페이지를 하드디스크에 sync시켜 버리고 물리메모리에서 제거하면 그 메모리는 free 메모리로 사용할 수 있게 된다. 페이지를 sync하기 위해서 즉 하드디스크에 write하기위해서는 I/O를 수행하여야 하며 그러기 위해선 또 다시buffer_head를 할당해야만 하는 웃지 못할 일이 발생한다. 이런 문제들을 방지하기 위하여 있는 플래그이다.

간단하게 설명하면 GFP_NOIO 플래그를 지정하지않으면 드라이버에서 메모리를 할당하려고했는데 돌고돌아서 다시 드라이버가 호출될 수 있다는 것입니다. 결국 또 메모리 할당 함수가 호출되고 무한 루프가 될 수 있습니다.

그리고 이전에 설명한대로 preload()를 실행하고 spin-lock을 잡습니다.

그 다음은 섹터 번호로 키 값을 만듭니다. 그리고 page 구조체의 index필드에 키값을 저장하고 radix_tree_insert()함수를 이용해서 트리에 페이지를 추가하면 됩니다.

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
gurugio
현재 버전
선택 버전
graphittie 자세히 보기