Flexible Array Aug 25, 2009

8월에 글이 많이 부족했다.
회사일로도 많이 바뻤고, 집안일로도 많이 바뻤고, 도저히
블로깅을 할 시간은 내기 힘들었다.

8월이 가기전에 또 다른 시간을 내기 힘들 것 같아, 아들 밥 먹고
있는 틈을 타서 지난번 봐두었던 기사에 대해 정리하기로 한다.

http://lwn.net/Articles/345273/


커널 프로그래밍을 할때 흔히들 큰 메모리 버퍼를 할당해서 사용해야
핲 필요가 있는 경우가 있다. 이때 큰 버퍼를 할당하기 위해서는
메모리 공간을 어떤 API로 확보해야 할까?
이미 우리는 여러 서적이가 기타 article들을 바탕으로 커널에서 big
order page allocation은 실패할 확률이 높다는 것을 알고 있다.
그러므로 kmalloc은 선택할 수 있는 방법은 아니다.
그래도 어쩔 수 없지 않는가? 우리는 big memory chunk가 필요한데.

Big memory가 물리적으로 연속될 필요가 없다면 가장 쉽게 선택할 수
있는 방법은 단연 vmalloc이다. vmalloc은 여러 문제가 있지만,
이번 기사에서 지적하고 있는 문제는 일반적인 32 bit system에서의
linear address space의 부족함이다. 커널이 사용하는 메모리 1G 중
896M는 direct mapped 되어지고, 나머지 공간 중에서도 일부는
kmap, kmap_atomic, fixed_map등을 위해 띠어주고 나면 대략 120M
정도가 vmalloc을 위해 사용가능하다.

또 다른 이유는 SMP system에서의 overhead가 크다는 것이다.
(TLB flush 및 IPI로 인하여. 이 중 많은 부분이 Nick Piggin에 의해
lazy flush방식으로 optimization되었었지만, 아무리 그렇더라도
vmalloc을 사용하지 않는 경우에 비해 overhead가 큰 것은 사실이다.)

그럼 여지껏 개발자들은 어떻게 그런 요구를 만족시켰는가?
답은 여러가지가 있을 수 있지만 일부 취했던 방식은 kmalloc을 통해
할당된 4K page들을 manage하여 array based로 접근하였다. array 방식으로
사용했던 이유는 간단하다. 여러분이 big memory chunk가 필요하다고 하자.
단일 object을 위해 그 메모리 공간을 사용하려고 그 큰 공간이 필요한건가?
그렇다. 대부분은 object pooling을 위해서이다. 그 얘기는 결국 array based
접근하는 것이 효율적이라는 것을 의미한다. object size가 고정이라면 말이다.

이러한 공통적인 need들이 증가하는 것은 결국 새로운 feature가
필요하다는 것을 암시하며, 그래서 나온 것이 vmalloc을 사용하지 않으면서도
large array를 할당하기 위한 general한 framework으로써, Andrew Morton에
의한 idea로 IBM의 Dave Hansen에 의해 구현된 "flexible array"이다.

Flexible array는 임의의 수의 고정된 크기의 array를 할당할 수 있으며,
배열과 같이 index를 통해 접근된다. 내부적으로는 single page allocation을
통해 page들 연결시켜 사용하기 때문에 fragmentation 문제를 발생시키지 않으며,
kmalloc을 통해 할당된 4K page들이기 때문에 vmalloc과 같은 overhead도 존재하지
않는다. 하지만 단점은 array는 직접 addressing할 수 없으며, object의 크기는
시스템의 page size 이내여야 한며, array에 data를 저장하기 위해서는
copy operation이 필요하다는 것이다.

현재 Flexible Array는 mmtom에서 계속 패치되고 있으며, 아직까지 특정 사용자가
존재하지 않음으로 API는 계속해서 바뀔 수 있다. 그러므로 사용법을 굳이 언급하지는
않는다.