[[완료]] linux rb_node에 대한 질문입니다.
음 cfs를 공부할려고 rb tree 에 대해서는 공부하였는데
리눅스 코드를 보다 막히는 부분이 있네요.
첫번째 궁금증은
struct rb_node
{
unsigned long rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
__attribute__((aligned(sizeof(long))));
이것인데 8byte단위로 aligned하겠다는 것같은데 무엇을 8byte단위로 정렬하는것인가요?
rb_node안의 멤버들의 크기가 8byte(64bit machine)이니까 멤버들을 정렬하는 건 아닌것 같은데요.
테스트 코드를 만들어 주소를 출력해봐도 특별한 점을 못찾겠네요.
그 다음 궁금점은
rb_node의 rb_parent_color가 부모 노드의 색깔을 저장하는 변수로 문서에서 읽었습니다.
1. 먼저 부모 노드의 주소를 자식의 color변수에 저장
node->rb_parent_color = (unsigned long )parent;
2. (제 생각) 자식 노드를 이용하여 부모 노드를 찾는데 사용되는 매크로 같은데 여기서 부모 주소에 & ~3을 하는게 먼지 도저히 모르겠네요.
위의 구조체 선언과 관련이 있을 것 같은데, 모르겠습니다.
#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
이 부분만 해결이 되면 나머지 부분이 clear하게 정리가 될꺼 같은데 답변 부탁드릴께요.
제가 잘못 이해한 부분이 있다면 꼬집어 주세요. 감사합니다.
제가 알기론..
1. 구조체의 시작 주소를 정렬하는 것입니다.
보통은 멤버 변수들의 정렬 제한을 고려해서 결정되기 때문에 필요없지만 CRIS 아키텍처에서는 필요하다고 하는군요..
(아래는 rb_node 구조체에 있는 주석입니다)
/* The alignment might seem pointless, but allegedly CRIS needs it */
2. 부모 노드의 색깔이 아니라 부모 노드의 포인터 + 자신의 색깔입니다.
공간 절약을 위해 color 필드를 따로 두지 않고 포인터의 최하위 비트를 이용한 것으로 기억합니다.
네~ 답변 감사합니다.
제가 잘못봤네요. 부모노드의 포인터 + 자신의 색깔이네요.
최하위 비트를 이용하여 자신의 색깔을 지정하네요.
아직 풀리지 않는 부분이 이 부분입니다.
#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
~3 왜 ~1이 아니라 추가적으로 한비트를 더 0로 만들까요?
rb_set_parent라는 함수에서도,
rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
이렇게 3으로 & 시키는데, 어떻게 된것인지??
분명한건 rb_parent에서 최하위 2비트를 mask시켜도 해당 부모의 주소를 받아온다는것인데,
음.. 최하위비트의 바로옆 비트는 어떤 의미가 되는것인지 궁금하네요.
감사합니다.
그냥 안쓰는 것 같은데요..
unused (reserved) bit라고 보시면 될 듯..
그런가요?
음.. 하나 더 궁금한건 어떻게 마지막 주소값이 1,3은 나올수없지만 2로 끝나는 주소가 안나오는걸 보장하는지 궁금하네요
즉 ~3을 시키면 주소의 마지막이 2인경우도 mask가 되버리는데 그럼 parent의 주소를 리턴할때 잘못된 값이 갈꺼 같은데요.
궁금점은 마지막 두비트가 부모의 주소를 가리키는데 사용되지 않는다는걸 어떻게 보장하는지 알고싶네요.
그래서
그래서 __attribute__((aligned(sizeof(long))))이 있는거죠. 16bit 아키텍쳐는 지원 안하니까 sizeof(long) >= 2^2.
음~ ㅡㅡ;
음.. 잘 이해가 안되는데 보충 설명 좀 해주시면 안될까요? ^^;
aligned(sizeof(long)) 속성
parent는 항상 rb_node를 가리키고
rb_node의 시작 주소는 최소 4바이트 단위로 정렬되어 있기 때문이죠..
음.. 만약 64bit 머신이라면 8byte단위로 정렬된다는것인데...
8byte로 정렬된다는 것이 8로 나눠진다는것인가요?
제가 test code를 만들어봤습니다.
#include <stdio.h> struct rb_node { unsigned long rb_parent_color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; }__attribute__((aligned(sizeof(long)))); int main() { struct rb_node a; struct rb_node b; printf("%u\n", sizeof(long)); printf("%u\n", sizeof(struct rb_node)); printf("%u\n", &a); printf("%u\n", &a.rb_parent_color); printf("%u\n", &a.rb_right); printf("%u\n", &a.rb_left); printf("%u\n", &b); printf("%u\n", &b.rb_parent_color); printf("%u\n", &b.rb_right); printf("%u\n", &b.rb_left); return 0; }그런데 출력이
8
24
3217608672
3217608672
3217608680
3217608688
3217608640
3217608640
3217608648
3217608656
3217608672 이게 노드의 주소인데 ~3으로 mask를 해버리면 2가 사라지지 않나요?
뭔가 놓치고 있는것 같은데, 친절한 답변 감사드립니다. ^^;
s/%u/%x/
10진수 말고 16진수로 출력해 보세요.. ^^
헛.. 답변 감사드립니다.
음 출력을 해보니 마지막 비트가 항상 0이네요.
잦은 질문에도 친절한 답변 감사드립니다. 복 받으실껍니다.
아직 약간 정리가 안되는게 있는게 좀만 생각해보면 될것 같습니다.
감사드립니다.^^
마지막 2비트는...
rbtree의 color를 저장하는 용도로 사용됩니다. 실제로는 1비트만 사용되죠.
즐거운 것이 답이 아닐까?
댓글 달기