Linux Tutorial #21 XArray

문연수·2021년 6월 18일

Linux Tutorial

목록 보기

22/25

XArray 는 매우 큰 포인터 배열처럼 동작하는 추상 데이터 타입이다. 이는 해쉬와 전통적인 가변 크기 배열들의 요구 사항을 만족한다. 해쉬와 달리, 이는 현명하게 캐쉬 효율성을 지키며 앞과 뒤의 요소로 이동하는 것을 허용한다. 가변 크기 배열과 달리, 배열을 키우기 위해 데이터를 복사하거나 MMU 매핑을 변경할 필요가 없다. 이는 양뱡향 연결 리스트(doubly-linked list) 보다 더 좋은 메모리 효율성, 병렬성 그리고 캐시 친화성을 가진다. 이는 락없이 조회를 수행할 때 RCU 를 활용한다.

1. 기본 API

위에서 설명한 XArray 를 사용하기 위해선 커널에서 제공하는 별도의 전용 API 함수들을 사용해야 한다.

1. XArray 정의

struct xarray {
	spinlock_t	xa_lock;
/* private: The rest of the data structure is not to be used directly. */
	gfp_t		xa_flags;
	void __rcu *	xa_head;
};

// XArray 정의 with flags
#define XARRAY_INIT(name, flags) {				\
	.xa_lock = __SPIN_LOCK_UNLOCKED(name.xa_lock),		\
	.xa_flags = flags,					\
	.xa_head = NULL,					\
}

#define DEFINE_XARRAY_FLAGS(name, flags)				\
	struct xarray name = XARRAY_INIT(name, flags)

// XArray 정의: xa_init() 과 동일하나, 매크로는 컴파일 타임에 초기화가 진행됨
#define DEFINE_XARRAY(name) DEFINE_XARRAY_FLAGS(name, 0)

// XArray 초기화 with flags
static inline void xa_init_flags(struct xarray *xa, gfp_t flags)
{
	spin_lock_init(&xa->xa_lock);
	xa->xa_flags = flags;
	xa->xa_head = NULL;
}

// xa_init() - 비어있는 XArray 를 초기화
// 비어있는 XArray => 모든 원소가 전부 NULL 로 초기화된 상태
static inline void xa_init(struct xarray *xa)
{
	xa_init_flags(xa, 0);
}

DEFINE_XARRAY() 와 xa_init() 등의 함수로 xarray 를 정의할 수 있다. 두 함수의 차이점은, 전자(DEFINE_XARRAY)의 경우 컴파일 타임에 미리 대입이 끝나는 반면, 후자의 함수(xa_init()) 는 런타임에 초기화가 이뤄진다는 정도이다.

2. XArray 저장, 불러오기

/**
 * xa_store() - 해당 엔트리를 XArray 안에 저장
 * @xa: XArray.
 * @index: 배열의 인덱스.
 * @entry: 새로운 엔트리.
 * @gfp: 메모리 동적할당 플래그.
 */
void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp)
{
	void *curr;

	xa_lock(xa);
	curr = __xa_store(xa, index, entry, gfp);
	xa_unlock(xa);

	return curr;
}

xa_store() 함수를 통해 배열에 특정 인덱스에 엔트리를 저장할 수 있다.

/**
 * xa_load() - XArray 로부터 엔트리를 가져온다.
 * @xa: XArray.
 * @index: index into array.
 */
void *xa_load(struct xarray *xa, unsigned long index)
{
	XA_STATE(xas, xa, index);
	void *entry;

	rcu_read_lock();
	do {
		entry = xas_load(&xas);
		if (xa_is_zero(entry))
			entry = NULL;
	} while (xas_retry(&xas, entry));
	rcu_read_unlock();

	return entry;
}

반대로 xa_load() 함수를 통해 특정 인덱스의 엔트리를 가져올 수 있다.

또한 xa_erase() 함수를 호출하여 원소를 지울 수 있으나 대신 xa_store() 함수를 호출해서 NULL 엔트리를 저장하는 방법도 있다. 보통 후자의 방법이 선호되어진다.

3. XArray 탐색

/**
 * xa_find() - XArray 에서 엔트리를 탐색
 * @xa: XArray.
 * @indexp: 인덱스에 해당하는 포인터
 * @max: 탐색을 수행할 인덱스의 최대 크기
 * @filter: 선택 기준
 */
void *xa_find(struct xarray *xa, unsigned long *indexp,
			unsigned long max, xa_mark_t filter)
{
	XA_STATE(xas, xa, *indexp);
	void *entry;

	rcu_read_lock();
	do {
		if ((__force unsigned int)filter < XA_MAX_MARKS)
			entry = xas_find_marked(&xas, max, filter);
		else
			entry = xas_find(&xas, max);
	} while (xas_retry(&xas, entry));
	rcu_read_unlock();

	if (entry)
		*indexp = xas.xa_index;
	return entry;
}

xa_find() 함수는 XArray 내에 있는 엔트리를 탐색한다.

4. XArray 제거

/**
 * xa_destroy() - 모든 내부 자료구조를 해제한다.
 * @xa: XArray.
 */
void xa_destroy(struct xarray *xa)
{
	XA_STATE(xas, xa, 0);
	unsigned long flags;
	void *entry;

	xas.xa_node = NULL;
	xas_lock_irqsave(&xas, flags);
	entry = xa_head_locked(xa);
	RCU_INIT_POINTER(xa->xa_head, NULL);
	xas_init_marks(&xas);
	if (xa_zero_busy(xa))
		xa_mark_clear(xa, XA_FREE_MARK);
	/* lockdep checks we're still holding the lock in xas_free_nodes() */
	if (xa_is_node(entry))
		xas_free_nodes(&xas, xa_to_node(entry));
	xas_unlock_irqrestore(&xas, flags);
}

xa_destroy() 함수는 XArray 의 내부적인 자료 구조를 제거한다.

2. XArray 테스트

위에서 설명했던 API 를 테스트하는 예제 코드를 작성해보았다. 복잡한 내용이 아니므로 쉽게 이해할 수 있을 것이다.

소스코드

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/slab.h>

static DEFINE_XARRAY(array);

static void xa_user_dump(const struct xarray *xa)
{
	pr_info("xarray: %px head %px flags %x marks %d %d %d\n", 
			xa, xa->xa_head, xa->xa_flags, 
			xa_marked(xa, XA_MARK_0),
			xa_marked(xa, XA_MARK_1), 
			xa_marked(xa, XA_MARK_2));
}

static int xarray_user_test(void)
{
	unsigned long i;
	void *ret;

	struct item {
		unsigned long index;
		unsigned int order;
	};

	struct item *item;
	pr_info("xarray_user_test() starting...\n");

	item = kmalloc(sizeof(*item), GFP_KERNEL);

	item->index = 0;
	item->order = 100;

	pr_info("[0] item = %p\n", item);
	xa_store(&array, 0, (void *) item, GFP_KERNEL);

	for (i = 1; i <= 10; i++) {
		item = kmalloc(sizeof(*item), GFP_KERNEL);
		
		pr_info("[%d] item = %p, ", i, item);
		item->index = i;
		item->order = i + 100;

		xa_store(&array, i, (void *) item, GFP_KERNEL);

		xa_user_dump(&array);
	}

	ret = xa_load(&array, 0);
	pr_info("load ret = %p, %d, %d\n", ret,
			((struct item *) ret)->index, ((struct item *)ret)->order);

	ret = xa_load(&array, 8);
	pr_info("load ret = %p, %d, %d\n", ret,
			((struct item *) ret)->index, ((struct item *)ret)->order);

	ret = xa_erase(&array, 4);
	pr_info("erase ret = %p, %d, %d\n", ret,
			((struct item *) ret)->index, ((struct item *) ret)->order);

	ret = xa_erase(&array, 7);
	pr_info("erase ret = %p, %d, %d\n", ret,
			((struct item *) ret)->index, ((struct item *) ret)->order);

	i = 9;
	ret = xa_find(&array, &i, ULONG_MAX, XA_PRESENT);

	pr_info("find ret = %p, %d, %d\n", ret,
			((struct item *) ret)->index, ((struct item *)ret)->order);

	xa_for_each(&array, i, ret) {
		pr_info("each ret = %p, %d, %d\n", ret,
				((struct item *) ret)->index, ((struct item *)ret)->order);
	}

	xa_destroy(&array);

	pr_info("xarray_user_test() end.\n");

	return 0;
}

static void xarray_exit(void)
{
	pr_info("xarray_exit() end.\n");
}

module_init(xarray_user_test);
module_exit(xarray_exit);
MODULE_AUTHOR("Yeounsu Moon <yyyynoom@gmail.com>");
MODULE_LICENSE("GPL");

위에서 소개하지 않았던 xa_for_each 구문이 등장했는데 이는 다음에 나오는 단일 구문(single statement) 혹은 복합 구문(compound statement) 을 반복적으로 실행하며 배열의 각 엔트리를 방문하여 해당 엔트리를 ret 에 저장한다.