[자료구조][Linux][WIP] XArray

XArray는 매우 큰 포인터 배열처럼 동작하는 추상 데이터 타입(abstract data type) 입니다. 해시와 크기 변경 가능한 배열을 모두 만족 시킵니다. 해시와 다른 점이라면, 캐시 친화적인 방식으로 위치 이동(이전, 다음)을 효율적으로 할 수 있습니다. 크기 변경 가능한 배열과 다른 점이라면, 배열의 크기를 증가 시키기 위해서 데이터를 복사 하거나 MMU 매핑을 변경할 필요가 없습니다. 양방향 연결 리스트(doubly-linked list) 보다 메모리 효율성이 좋고 병렬화 가능하며 캐시 친화적입니다. 또한 RCU의 장점을 활용하여 락킹없이 조회 작업을 수행합니다.

 

위와 같이 XArray는 많은 장점을 가지고 있는 자료구조 입니다. 하지만 XArray에는 몇가지 특징(장단점)들이 있습니다.

 

XArray를 구현할때 인덱스가 밀집되어 있으면 효율적입니다. 해시는 분산되는 특성을 가지고 있으므로 인덱스로 해시를 사용하거나 객체를 해싱하면 성능이 떨어집니다. XArray는 작은 인덱스에 최적화되어 있지만 대량의 인덱스에서도 성능이 좋습니다. 하지만 인덱스가 ULONG_MAX보다 크게 되면 XArray를 사용할 수 없습니다. 즉, XArray에서 인데스 최대 크기는 ULONG_MAX로 제한되어 있습니다. XArray는 페이지 캐시에서 가장 잘 활용될 수 있습니다.

 

배열에서 NULL이 아닌 각각의 요소(entry)는 3개 비트를 가지고 있으며 이것을 marks라고 합니다. 각각의 mark는 다른것들과 별도로 set 혹은 clear 됩니다. 이렇게 marked된 요소들에 대해서 반복 작업할 수 있습니다.

 

일반 포인터들은 XArray에 바로 저장 될 수 있으며 4바이트로 정렬되어 있습니다. kmalloc() 및 alloc_page()에서 리턴되는 포인터는 여기에 해당됩니다. 그러나 사용자 공간(user-space)에서 사용하는 포인터나 함수 포인터는 여기에 해당하지 않습니다. 정적으로 할당된 객체 주소가 4바이트로 정렬되어 있다면 XArray에 저장할 수 있습니다.

 

XArray에 0부터 LONG_MAX 사이의 정수를 저장할 수도 있습니다. 이들을 XArray에 저장하기 위해서는 정수값을 xa_mk_value() API 함수를 사용하여 XArray 요소(entry)로 변환해야 합니댜. 또한 XArray에서 요소(entry)를 검색 할때는 xa_is_value() API 함수를 사용하고 요소(entry)를 다시 정수로 변환 할때는 xa_to_value() 함수를 사용합니다.

 

위와 같이 XArray에 접근 하기 위해서는 XArray 전용 API 함수들을 사용합니다.

XArray는 unsigned long으로 색인화된(2^BITS_PER_LONG 개) 포인터 배열이며 radix tree를 많이 보완 했습니다. 기존에 리눅스 커널 소스에 있었던 radix tree는 점차적으로 XArray로 교체될듯 합니다. 아래를 보시면 왼쪽은 radix tree API 함수들이고 오는쪽은 이 함수를 대체하는 XArray API 함수들입니다.

 

출처

https://www.kernel.bz/boardPost/118679/19