[CS] tagged pointer

tagged pointer는 memory alignment를 이용해 포인터의 일부 비트에 추가 정보를 저장하는 메모리 최적화 기법이다.

예를 들어 32bit 환경에서 어떤 객체가 4바이트 단위로 정렬된다면, 그 객체의 주소 하위 2비트는 항상 00이 된다.
이처럼 aligment 등으로 인해 항상 일정한 값을 가지는 비트를 tag(플래그, 타입 정보 등) 용도로 활용하는 기법을 tagged pointer라고 한다.

Example

리눅스 커널에서 동적으로 할당된 포인터는 최소 4바이트로 정렬되므로, 하위 2비트는 항상 0이다. 리눅스의 XArray는 이 점을 활용해 포인터 값 자체에 작은 태그를 함께 인코딩한다. 사용 가능한 태그 값은 0, 1, 3이며, 2는 내부 엔트리(internal entry)용으로 예약되어 있다.

• xa_tag_pointer(): 포인터의 하위 비트에 태그를 OR 연산으로 삽입한다.
• xa_untag_pointer(): 하위 2비트를 마스킹해 원래 포인터를 복원한다.
• xa_pointer_tag(): 하위 2비트만 추출해 저장된 태그 값을 반환한다.

static inline void *xa_tag_pointer(void *p, unsigned long tag)
{
	return (void *)((unsigned long)p | tag);
}

static inline void *xa_untag_pointer(void *entry)
{
	return (void *)((unsigned long)entry & ~3UL);
}

static inline unsigned int xa_pointer_tag(void *entry)
{
	return (unsigned long)entry & 3UL;
}