Egloos | Log-in
F/OSS study
F/OSS study
[Linux] priority search tree (4)
Linux: 2.6.32

이전 글 보기:

이제 마지막으로 PST가 실제로 reverse mapping에서 어떻게 사용되는지를 살펴보기로 하자.
reverse mapping을 위해 각 address_space 객체는 PST의 root인 i_mmap 필드를 포함한다.
PST에는 해당 페이지 프레임을 포함하는 메모리 구역(vma)이 노드로 사용된다.
각 메모리 구역은 시작 주소와 끝 주소에 대응하는 페이지 프레임 인덱스를 가지므로
이를 이용하여 일반적인 PST의 노드로 표현할 수 있겠지만
실제로는 파일 내의 동일한 구간이 여러 메모리 구역에 매핑되기 때문에 (ex. glibc의 코드 영역)
reverse mapping을 위한 PST는 동일한 노드 여러 개를 처리하도록 변경되어야 한다.

먼저 vm_area_struct 구조체를 살펴보면 중간에 다음과 같은 필드를 포함하고 있음을 볼 수 있다.

    union {
        struct {
            struct list_head list;
            void *parent;    /* aligns with prio_tree_node parent */
            struct vm_area_struct *head;
        } vm_set;

        struct raw_prio_tree_node prio_tree_node;
    } shared;

shared 필드는 union 타입이며 vm_set이나 prio_tree_node 중의 하나로 사용된다.
prio_tree_node는 일반 prio_tree_node 구조체가 아닌 raw_prio_tree_node 구조체인데
이는 원래의 구조체에서 start와 last 필드를 제외한 것으로
트리 구조 자체에서 사용되는 left, right, parent 필드 만으로 구성된다.
vm_set 익명 구조체는 동일한 구간을 매핑하는 여러 vma들을 연결하기 위한 list와
현재 vma가 tree에 포함된 노드인지를 구분하는 목적으로 사용되는 parent 필드 및
PST와 list 사이를 연결해주는 head 필드로 구성된다.

여기서 parent 필드의 위치(offset)는 prio_tree_node나 vm_set이나 모두 동일하다는 것이 중요한데
일반적인 PST 연산에서는 (vm_set 부분을 무시하고 생각해보면) tree 내에 포함된 모든 노드는
parent 필드가 적절히 설정된다. 그러면 자동으로 vm_set.parent 필드도 설정되는 효과를 얻을 수 있으므로
이후에는 vm_set 구조체의 필드 만 보고도 해당 노드가 속한 위치를 판단할 수 있다.

이제 동일한 구간을 매핑하는 다른 vma가 PST에 삽입되는 경우를 생각해 보자.
처음 글에서 insert() 함수를 살펴보았을 때 반환값을 신경써서 본 사람이 있다면 알 수 있듯이
삽입할 노드와 완전히 동일한 구간을 매핑하는 노드가 PST에 이미 있는 경우에는
기존의 노드를 반환하며, 그렇지 않으면 삽입된 노드 자체를 반환하도록 구현되어 있다.
즉, 해당 구간이 이미 포함되어 있는지 검사하려면 insert()의 반환값이 인자로 주어진 노드와
동일한지를 검사하면 된다. 반환된 노드는 parent 필드가 적절히 설정되어 있으므로
해당 구간을 나타내는 두 개의 vma 중에서 어느 것이 PST에 속한 것인지를 금방 알 수 있다.
이제 PST에 포함된 노드의 shared.vm_set.head 필드에 새로 삽입한 노드의 포인터를 연결한다.
또한 새로 삽입한 노드의 shared.vm_set.head 필드에는 PST에 포함된 노드의 포인터를 연결한다.

이후에 다시 동일한 구간을 매핑하는 vma가 PST에 삽입되면
위에서 2번째로 삽입된, 즉 parent 필드가 NULL이고 head 필드는 NULL이 아닌 노드의 list에 계속 연결된다.
이렇게 3번째 이후로 삽입되는 노드들은 parent와 head가 모두 NULL로 설정된다.

정리하면 다음과 같다.
  • parent가 NULL이 아님: PST에 속한 노드 (1번째로 삽입된 노드)
  • parent는 NULL이고 head가 NULL이 아님: 리스트 내의 첫 노드 (2번째로 삽입된 노드)
  • parent도 NULL이고 head도 NULL임: 리스트 내의 나머지 노드 (3번째 이후로 삽입된 노드)

이러한 작업을 수행하는 vma_prio_tree_insert() 함수는
raw_prio_tree_insert() 함수를 호출하여 반환값과 원래 노드의 포인터를 비교하고
다른 경우 해당 노드를 list에 추가하도록 아래와 같은 vma_prio_tree_add() 함수를 호출한다.

void vma_prio_tree_add(struct vm_area_struct *vma, struct vm_area_struct *old)
{
    /* Leave these BUG_ONs till prio_tree patch stabilizes */
    BUG_ON(RADIX_INDEX(vma) != RADIX_INDEX(old));
    BUG_ON(HEAP_INDEX(vma) != HEAP_INDEX(old));

    vma->shared.vm_set.head = NULL;
    vma->shared.vm_set.parent = NULL;

    if (!old->shared.vm_set.parent)
        list_add(&vma->shared.vm_set.list,
                &old->shared.vm_set.list);
    else if (old->shared.vm_set.head)
        list_add_tail(&vma->shared.vm_set.list,
                &old->shared.vm_set.head->shared.vm_set.list);
    else {
        INIT_LIST_HEAD(&vma->shared.vm_set.list);
        vma->shared.vm_set.head = old;
        old->shared.vm_set.head = vma;
    }
}

여기서 old는 기존의 (PST 내에 포함된) 노드에 해당하며, vma는 새로 삽입할 노드에 해당한다.
첫 번째 if는 old가 parent를 가지지 않는 경우에 대한 검사인데
아마 정상적인 호출인 경우라면 old의 parent는 항상 NULL이 아닐 것이므로 실행되지 않을 것이다.
그렇다면 shared.vm_set.head 필드를 보고 NULL이 아니면 기존의 리스트가 존재하므로 해당 리스트에 추가하고,
head가 NULL이라면 새로 리스트를 생성하고 head를 설정한다.

마찬가지로 주어진 페이지를 포함하는 모든 vma를 찾는 연산을 수행할 때도 (실제로 reverse mapping이 필요한 경우이다)
먼저 PST 내의 노드를 순차적으로 찾아본 뒤 해당 노드의 shared.vm_set.head 필드가 설정되어 있다면
그에 대한 리스트를 탐색하는 방법으로 모든 vma를 순회할 수 있게 된다.
by namhyung | 2009/12/21 20:06 | Kernel | 트랙백 | 덧글(2)
트랙백 주소 : http://studyfoss.egloos.com/tb/5202795
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented by song0319 at 2012/02/28 14:00
안녕하세요 분석하신 자료구조 잘보고 갑니다. 문제는 이 트리의 장단점이 적혀있지 않은것 같아요
공부하다 감이 잡히지 않아 질문드립니다.
자료구조라는건 특정 행동에 대해 검색이나 삽입의 이득이 있어야 사용에 이유가 있는데 리눅스 커널은 그 장단점에 대해 자세히 설명하고 있지 않더군요
개인적으로 결론내린 이 자료형에 장점은 특정 구간의 검색에 있어서 힙과 같은 순차 접근으로 구간검색이 가능하지만 트리의 형태를 취함으로써 빠른 삽입이 가능한 구조라고 이해를 했는데 어떻게 생각하시나요?
언더스텐딩 리눅스 커널의 방식으로 자료형을 트리 순회 탐색하면 결국 힙 순서로 정렬된 리스트 힙 값이 같은 경우 라딕스 인덱스로 정렬된 리스트와 똑같은 노드 검색 시간이 걸릴 것 같은데..

그리고 일반적으로 구글에 검색되는 PST 트리 2차원 좌표계의 포함 영역검색 처럼 리눅스에 소계된 PST 는 삽입 빼고 별다른 장점이 없어 보입니다.
혼자 고민하다가 덧글이라도 남겨봅니다.

좋은자료 항상 감사하고 좋은하루 되세요
Commented by namhyung at 2012/03/03 17:41
안녕하세요.. 오랜만에 생각해 볼만한 어려운 주제를 던져주시네요.. ^^;

구간 검색이 가능한 알고리즘에 대해서 저도 깊게 생각해보진 않았지만
말씀하신대로 PST와 2차원 리스트에서 검색 시간은 동일한 성능(O(N)?)을 보일 것 같습니다.
또한 삽입/제거의 경우 트리 형태를 유지하는 한 O(logN) 정도가 되겠지만
overflow subtree 와 vm_set 등의 문제로 인해서 결국 O(N)에 가까워지지 않을까 합니다.
하지만 실제로 많지 않은 수의 노드가 사용된다면 성능 이득을 얻을 수 있을 것 같네요..

알고리즘에 대해서 깊이있는 고민을 하시는 모습을 보니 부럽기도 하고 부끄럽기도 하네요.. ;;
고민하시며 새로이 깨닫게 되신 내용이나 제가 잘 못 알고있는 내용이 있다면 언제라도 알려주시면 감사하겠습니다.
답글 남겨주셔서 감사드리고 좋은 하루 보내시길 바랍니다.

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
CAaQA3 documentation bash compiler algorithm git kernel SMP C patch x86 script synchronization glibc sed scm memory awk computer-architecture linux binutils perf CARM gcc blktrace block-layer vcs elf build emacs
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X