링크 ux 커 널 해시 링크 분석

해시 표 소개 hlist
Liux 커 널 에는 유명한 list 양 방향 순환 링크 를 제외 하고 중요 한 데이터 구조 가 있 는데 바로 해시 링크 입 니 다.해시 링크 도 많은 중요 한 부분 에서 사용 된다. 예 를 들 어 Liux 커 널 의 dentry, 프로 세 스 조회, 파일 시스템 등 은 hlist 가 Liux 커 널 을 이해 하 는 데 중요 한 의 미 를 가진다 고 할 수 있다.
데이터 구조의 소개

struct hlist_head 
{
	struct hlist_node *first;
};
struct hlist_node 
{
 struct hlist_node *next, **pprev;
};

Liux 커 널 의 해시 링크 는 두 개의 데이터 구조 로 구성 되 어 있 으 며, 하 나 는 hlist 이다.헤드 는 해시 표 의 시계 머리 이 고, 하 나 는 hlistnode, 해시 표 의 후속 노드 입 니 다.사용 할 때, 일반적으로 struct hlist 를 정의 합 니 다.head xxx [100] 배열 (100 은 하나의 대표 적 인 숫자 일 뿐 구체 적 인 상황 에 따라 정 합 니 다) 은 해시 함수 로 키 값 과 배열 의 대응 하 는 주 소 를 연결 합 니 다. 충돌 이 발생 하면 hlist 에 있 습 니 다.헤드 뒤에 계속 추가 합 니 다.
hlist_head 의 멤버 first 포인 터 는 다음 의 첫 번 째 노드 를 가리 키 며, 해시 링크 가 비어 있 으 면 NULL 입 니 다.
왜 hlist헤드 는 양 방향 체인 시계 가 되 지 않 습 니 다. 공간 을 절약 하기 위해 지침 하나 가 있 으 면 해시 배열 의 공간 소 모 는 반 으로 줄 어 들 기 때 문 입 니 다.
hlist_node 의 멤버 next 는 다음 노드 의 주 소 를 가리 키 며, 비어 있 으 면 NULL 이 고, 다른 멤버 pprev 는 2 급 포인터 로 이전 노드 의 next 멤버 의 주 소 를 가리 키 며, 이전 멤버 가 hlist 라면head 의 경우, pprev 의 값 은 앞의 first 포인터 의 주소 입 니 다.
Linux 의 링크 와 산 목록 의 조작 함수 정 의 는 include / linux / list. h 파일 에 있 습 니 다. 다음은 이 파일 을 열 어 hlist 데이터 구조의 조작 함수 와 매크로 를 보 겠 습 니 다.

#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

해시 링크 를 초기 화 합 니 다. 이 세 가지 초기 화 홍 도 는 hlist 를 만 드 는 것 입 니 다.head 구조 체, first 멤버 를 NULL 로 설정 합 니 다.

static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
	h->next = NULL;
	h->pprev = NULL;
}

이 함 수 는 hlist 를 초기 화 합 니 다.node 데이터 구 조 는 두 구성원 변 수 를 NULL 로 간단하게 할당 하 는 것 일 뿐 입 니 다.

static inline int hlist_unhashed(const struct hlist_node *h)
{
	return !h->pprev;
}

이 함 수 는 해시 링크 의 노드 가 해시 링크 에 있 는 지, 아니면 이미 삭제 되 었 는 지 판단 하 는 것 입 니 다.판단 방법 은 pprev 멤버 가 비어 있 는 지 아 닌 지 를 판단 하 는 것 입 니 다. NULL 이 라면 이 node 노드 가 해시 링크 에서 삭제 되 었 음 을 설명 합 니 다. 그렇지 않 으 면 이 노드 가 여전히 해시 링크 에 있다 는 것 을 설명 합 니 다.

static inline int hlist_empty(const struct hlist_head *h)
{
	return !h->first;
}

이 함 수 는 해시 링크 가 비어 있 는 지 아 닌 지 를 판단 하 는 것 입 니 다. 입력 매개 변 수 는 해시 체인 헤더 이 고 판단 방법 은 hlist 를 판단 하 는 것 입 니 다.헤드 의 퍼스트 멤버 는 NULL 입 니까?

static inline void __hlist_del(struct hlist_node *n)
{
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;
	*pprev = next;
	if (next)
		next->pprev = pprev;
}

이 함 수 는 해시 링크 삭제 의 주요 논리 함수 입 니 다. 입력 매개 변 수 는 삭제 할 링크 노드 입 니 다. 먼저 hlist 를 얻 습 니 다.node 의 next 와 pprev 멤버, next 는 다음 hlist 를 가리 키 고 있 습 니 다.node 구조 체 의 주소, pprev 는 이전 구성원 의 next 포인터 의 주소 입 니 다. * pprev 는 이전 노드 의 next 포인터 (first 포인터 일 수도 있 습 니 다) 입 니 다. 이전 포인터 의 next 포인터 의 값 이 next 포인터 의 값 으로 바 뀌 면 이전 노드 의 next 포인터 가 노드 를 삭제 할 다음 노드 를 가리 키 고 있 습 니 다. next 가 비어 있 지 않 으 면,다음 포인터 의 pprev 구성원 은 삭제 할 노드 의 이전 노드 의 next 구성원 의 주 소 를 가 리 킵 니 다.
이 함 수 는 hlist 를 표시 합 니 다.node 는 pprev 멤버 를 2 급 포인터 로 설정 한 장점 은 이전 노드 가 hlist 라 고 할 필요 가 없다 는 것 입 니 다.head 아니면 hlistnode 노드 로 다른 조작 을 합 니 다.만약 pprev 가 2 급 지침 이 아니 라 hlistnode * prev 는 먼저 컴 파일 할 때 오류 가 발생 합 니 다. 또한 작업 을 삭제 할 때 이전 노드 가 hlist 이기 때 문 입 니 다.head 아니면 hlistnode 는 서로 다른 논 리 를 한다.

static inline void hlist_del(struct hlist_node *n)
{
	__hlist_del(n);
	n->next = LIST_POISON1;
	n->pprev = LIST_POISON2;
}

이 함 수 는 사실 이전 함수 의 마무리 함수 입 니 다. 삭제 한 후에 삭 제 된 노드 의 포인터 값 을 변경 하 는 것 입 니 다. 이 LIST 에 대해 서 는...POISON 1 과 LISTPOISON 2 가 어떤 신성 한 지, 이 매크로 의 정 의 를 봅 시다.

/********** include/linux/list.h **********/
/*
 * These are non-NULL pointers that will result in page faults
 * under normal circumstances, used to verify that nobody uses
 * non-initialized list entries.
 */
#define LIST_POISON1  ((void *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200200)

이 매크로 의 위 에 영어 주석 이 있 습 니 다. 우 리 는 영 어 를 보면 알 수 있 습 니 다. 이 두 가 지 는 누군가가 초기 화 되 지 않 은 해시 링크 를 사용 하 는 것 을 방지 하기 위해 서 입 니 다. 컴퓨터 영 어 를 잘 배우 지 못 해도 안 됩 니 다.

static inline void hlist_del_init(struct hlist_node *n)
{
	if (!hlist_unhashed(n)) {
		__hlist_del(n);
		INIT_HLIST_NODE(n);
	}
}

이 함 수 는 해시 링크 의 노드 를 먼저 삭제 하고 초기 화 하 는 것 입 니 다.

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
	n->next = first;
	if (first)
		first->pprev = &n->next;
	h->first = n;
	n->pprev = &h->first;
}

이 함수 의 역할 은 해시 링크 의 노드 를 해시 링크 의 머리 노드 뒤에 삽입 하여 hlist 로 전달 하 는 것 입 니 다.head 와 hlistnode 구조 체, 우선 hlisthead 의 first 구성원 은 바로 뒤의 노드 의 지침 입 니 다. 이 노드 는 NULL 일 수 있 습 니 다. 그 다음 에 새로 삽 입 된 노드 의 next 는 first 뒤의 노드 를 가리 키 고 first 가 비어 있 지 않 으 면 뒤쪽 에 노드 가 존재 합 니 다. head 의 뒤쪽 노드 의 pprev 구성원 은 새로 삽 입 된 노드 의 next 구성원 의 주 소 를 가리 키 고 head 의 first 는 새로 삽 입 된 노드 를 가리 킵 니 다.노드 를 새로 삽입 한 pprev 구성원 은 head 의 first 구성원 의 주 소 를 가리킨다.

static inline void hlist_add_before(struct hlist_node *n,
					struct hlist_node *next)
{
	n->pprev = next->pprev;
	n->next = next;
	next->pprev = &n->next;
	*(n->pprev) = n;
}

이 함수 의 역할 은 하나의 노드 를 해시 링크 의 노드 앞 에 삽입 하 는 것 입 니 다. 먼저 삽입 할 노드 의 pprev 구성원 변 수 를 next 의 앞쪽 노드 를 가리 키 고 삽입 할 노드 의 next 는 다음 노드 를 가리 키 며 next 노드 의 pprev 는 삽 입 된 노드 의 next 노드 의 주 소 를 가리 키 는 것 입 니 다.삽 입 된 노드 의 pprev 가 가리 키 는 이전 노드 의 값 은 삽 입 된 노드 의 주소 가 됩 니 다.

static inline void hlist_add_after(struct hlist_node *n,
					struct hlist_node *next)
{
	next->next = n->next;
	n->next = next;
	next->pprev = &n->next;


	if(next->next)
		next->next->pprev  = &next->next;
}

이 함 수 는 한 노드 를 한 노드 의 뒤에 삽입 하 는 것 으로 이전 함수 와 차이 가 크 지 않 습 니 다. 유일 하 게 주의해 야 할 것 은 뒤쪽 이 NULL 일 수 있 습 니 다.

#define hlist_for_each(pos, head) \
	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
	     pos = pos->next)

이 매크로 는 해시 링크 를 옮 겨 다 니 는 매크로 입 니 다. pos 는 hlist 를 대표 합 니 다.node 구조 체 지침, head 대표 hlisthead 구조 체, 바로 하 세 링크 의 머리 입 니 다.