태그된 포인터

Tagged pointer

컴퓨터 과학에서 태그된 포인터는 포인터(구체적으로 메모리 주소)이며, 이와 관련된 추가 데이터가 있는 포인터(예: 방향 비트 또는 기준 카운트)이다.이 추가 데이터는 종종 포인터로 "접혀져"지는데, 이는 메모리 주소 지정의 특정 속성을 이용하여 주소를 나타내는 데이터에 인라인으로 저장된다는 것을 의미한다.이름은 "태그된 아키텍처" 시스템에서 유래되었는데, 하드웨어 레벨에서 비트를 예약하여 각 단어의 중요성을 표시하였다. 추가 데이터를 "태그" 또는 "태그"라고 부르지만, 엄밀히 말하면 "태그된 포인터"는 다른 데이터가 아닌 유형을 지정하는 데이터를 가리킨다. 그러나 "태그된 포인터"라는 용어는 어디에나 있다.

태그를 포인터로 접기

태그를 포인터로 접는 기술에는 여러 가지가 있다.[1][unreliable source?]

대부분의 아키텍처는 바이트 주소 지정 가능(가장 작은 주소 지정 가능 단위는 바이트)이지만, 특정 유형의 데이터는 데이터 크기(흔히 단어 또는 여러 개)에 맞춰 정렬되는 경우가 많다.이러한 불일치로 인해 포인터 중 몇 개의 중요도가 가장 낮은 비트가 사용되지 않으며, 이는 메모리에 액세스하기 전에 포인터를 사용하는 코드가 이러한 비트를 마스킹하는 한 태그(각 비트 별개 태그)에 가장 많이 사용될 수 있다.예: 32비트 아키텍처(주소와 단어 크기 모두)에서 워드는 32비트 = 4바이트이므로 워드 정렬 주소는 항상 4의 배수로, 따라서 00에서 종료되어 마지막 2비트를 사용할 수 있는 반면, 64비트 아키텍처에서는 워드 = 8바이트가 64비트인 반면 워드 정렬 주소는 000로 끝나 마지막 3비트를 사용할 수 있게 된다.데이터가 워드 크기의 배수로 정렬된 경우 추가 비트를 사용할 수 있다.워드 어드레싱 가능 아키텍처의 경우, 워드 정렬 데이터는 정렬과 어드레싱 사이에 불일치가 없기 때문에 사용 가능한 비트를 남겨두지 않지만, 워드 사이즈의 배수로 정렬된 데이터는 그렇게 한다.

반대로, 일부 운영 체제에서는 가상 주소가 전체 아키텍처 너비보다 좁아서 태그에 가장 중요한 비트를 사용할 수 있다. 이는 정렬된 주소의 경우 이전 기법과 결합될 수 있다.특히 64비트 아키텍처의 경우 64비트의 어드레스 공간이 가장 큰 애플리케이션을 제외한 모든 애플리케이션의 데이터 요건을 훨씬 상회하고, 따라서 많은 실용적인 64비트 프로세서가 어드레스를 좁게 하고 있기 때문이다.가상 주소 너비가 물리적 주소 너비보다 좁을 수 있으며, 이는 아키텍처 너비보다 좁을 수 있다는 점에 유의하십시오. 사용자 공간의 포인터 태그 지정의 경우 운영체제가 제공하는 가상 주소 공간(메모리 관리 장치가 차례로 제공함)이 관련 너비입니다.실제로 일부 프로세서는 특히 프로세서 수준에서 이러한 태그가 지정된 포인터의 사용을 금지하고 있으며, 특히 x86-64는 운영체제에 의한 표준 양식 주소를 사용해야 하며 대부분의 중요한 비트는 0초 또는 1초이다.

마지막으로, 대부분의 최신 운영 체제에서 가상 메모리 시스템은 주소 0 주변의 논리적 메모리 블록을 사용할 수 없는 것으로 보존한다.이것은 예를 들어, 0에 대한 포인터는 결코 유효한 포인터가 아니며 특별한 null 포인터 값으로 사용될 수 있다는 것을 의미한다.앞서 언급한 기법과는 달리, 이것은 일반적으로 포인터의 추가 데이터가 아닌 하나의 특별한 포인터 값만 허용한다.

예

상용 플랫폼에서 태그가 지정된 포인터에 대한 하드웨어 지원의 초기 사례 중 하나는 IBM System/38이었다.[2]IBM은 나중에 IBM i 운영 체제를 지원하기 위해 PowerPC 아키텍처에 태그가 붙은 포인터 지원을 추가했는데, 이는 System/38 플랫폼의 발전이다.[3]

태그가 지정된 포인터의 사용의 중요한 예는 아이폰 5S에서 특히 사용되는 ARM64의 iOS 7에서 Objective-C 런타임이다.iOS 7에서 가상 주소는 주소 정보의 33비트만 포함하고 64비트 길이로 태그의 31비트를 남긴다.목표-C 클래스 포인터는 8바이트 정렬로 3비트의 주소 공간을 추가로 확보하며, 태그 필드는 참조 카운트 저장 및 객체에 소멸자가 있는지 여부 등 다양한 용도로 사용된다.[4][5]

초기 버전의 MacOS는 데이터 개체에 대한 참조를 저장하기 위해 핸들이라는 태그 지정된 주소를 사용했다.주소의 높은 비트는 데이터 개체가 각각 잠금, 삭제 가능 및/또는 리소스 파일에서 생성되었는지 여부를 가리켰다.이는 시스템 7에서 MacOS 어드레싱이 24비트에서 32비트로 진전되었을 때 호환성 문제를 야기했다.[6]

Null 대 정렬 포인터

null 포인터를 나타내기 위해 0을 사용하는 것은 매우 일반적이며, 많은 프로그래밍 언어(예: Ada)가 명시적으로 이 동작에 의존한다.이론적으로, 운영체제가 보존된 논리 메모리의 블록에 있는 다른 값들은 null 포인터가 아닌 다른 조건에 태그를 붙이는 데 사용될 수 있지만, 기껏해야 휴대성이 없기 때문에 이러한 사용은 드문 것으로 보인다.소프트웨어 설계에서는 일반적으로 null(특정 데이터 구조의 sentinel 등)과 구별되는 특별한 포인터 값이 필요한 경우 프로그래머가 명시적으로 제공해야 한다.

포인터의 정렬을 활용하면 포인터가 가리키는 데이터 유형, 포인터가 접속될 수 있는 조건 또는 포인터의 사용에 관한 기타 유사한 정보로 태그가 지정될 수 있기 때문에 포인터/센티넬보다 유연성이 높다.이 정보는 모든 유효한 포인터와 함께 제공될 수 있다.대조적으로, null 포인터/센티넬은 유효한 포인터와 구별되는 한정된 수의 태그된 값만 제공한다.

태그가 붙은 아키텍처에서, 메모리의 모든 단어에 있는 많은 비트는 태그의 역할을 하기 위해 예약된다.Lisp 시스템과 같이 태그가 지정된 아키텍처는 태그가 지정된 포인터를 해석하고 처리할 수 있도록 하드웨어를 지원하는 경우가 많다.

GNU libc malloc()32비트 플랫폼을 위한 8바이트 정렬 메모리 주소와 64비트 플랫폼을 위한 16바이트 정렬을 제공한다.[7]더 큰 선형 값은 다음과 같이 얻을 수 있다.posix_memalign().[8]

예

예 1

다음 C 코드에서 0 값은 null 포인터를 나타내기 위해 사용된다.

공허하게 하다 선택적으로_return_a_value (인트로* option_return_value_properties) {   /* ... */   인트로 value_to_return = 1;    /* 비 NULL인가? (NULL, 논리적 False, 0은 C에서 동등하게 비교됨) */   만일 (option_return_value_properties)     /* 있는 경우 */를 사용하여 호출 함수에 값을 전달하십시오.     *option_return_value_properties = value_to_return;    /* 그렇지 않으면 포인터가 참조 해제되지 않음 */ }

예 2

여기서 프로그래머는 글로벌 변수를 제공했고, 그 주소는 다음 보초로서 사용된다.

#SENTINEL &sentinel_s 정의  node_t sentinel_s.;  공허하게 하다 do_something_to_a_node (node_t * p) {   만일 (NULL == p)     /* 뭔가를 해 */   다른 만일 (센티넬 == p)     /* 다른 일을 하라 */   다른     /* p를 노드 */에 대한 유효한 포인터로 간주 }

예 3

데이터 구조를 가지고 있다고 가정해 보십시오.table_entry그것은 항상 16바이트의 경계선에 맞춰져 있다.즉, 테이블 항목 주소의 최하위 4비트는 항상 0(24 = 16)이다.우리는 이 4비트를 사용하여 추가 정보로 테이블 엔트리를 표시할 수 있다.예를 들어, 비트 0은 읽기 전용, 비트 1은 더러움(테이블 항목을 업데이트해야 함) 등을 의미할 수 있다.

포인터가 16비트 값인 경우:

  • 0x3421에 대한 읽기 전용 포인터table_entry주소서0x3420
  • 0xf472더러운 것에 대한 포인터다.table_entry주소서0xf470

이점

태그가 지정된 포인터의 주요 장점은 별도 태그 필드와 함께 포인터보다 공간을 적게 차지한다는 것이다.이것은 포인터가 함수의 반환 값일 때 특히 중요할 수 있다.그것은 또한 큰 포인터 테이블에서 중요할 수 있다.

보다 미묘한 이점은 태그를 포인터와 동일한 위치에 저장함으로써 외부 동기화 메커니즘 없이 포인터와 해당 태그를 모두 업데이트하는 작업의 원자성을 보장할 수 있는 경우가 많다는 점이다.이는 특히 운영 체제에서 매우 큰 성능 이득이 될 수 있다.

단점들

태그가 지정된 포인터는 비록 작지만 xor 링크된 목록과 동일한 어려움을 가지고 있다.예를 들어, 모든 디버거가 태그가 지정된 포인터를 제대로 따를 수 있는 것은 아니지만, 태그가 지정된 포인터를 염두에 두고 설계된 디버거의 문제는 아니다.

null 포인터를 나타내기 위해 0을 사용하는 것은 이러한 단점을 겪지 않는다: 그것은 널리 퍼지고 대부분의 프로그래밍 언어는 0을 특별한 null 값으로 취급하며, 그 견고성을 철저히 증명했다.예외는 C++에서 0이 과부하 분해능에 참여하는 방식이며, 여기서 0은 포인터가 아닌 정수로 취급된다. 이러한 이유로 정수 0보다 특수 값 nullptr을 선호한다.그러나 태그가 지정된 포인터가 있는 경우 일반적으로 0은 null 포인터를 나타내기 위해 사용되지 않는다.

참조

  1. ^ 금요일 Q&A 2012-07-27: 마이크 애쉬의 Tagged 포인터 제작
  2. ^ Levy, Henry M. (1984). "The IBM System/38" (PDF). Capability-Based Computer Systems. Digital Press. ISBN 0-932376-22-3.
  3. ^ Frank G. Soltis (1997). Inside the AS/400, Second Edition. Duke Press. ISBN 978-1882419661.
  4. ^ 금요일 Q&A 2013-09-27: ARM64 and You, by Mike Ash
  5. ^ [objc 설명]:논점자이사
  6. ^ Bricknell, K. J. Macintosh C: A Hobbyist's Guide To Programming the Mac OS in C.
  7. ^ "Malloc Examples". The GNU C Library. Retrieved 5 September 2018.
  8. ^ posix_memalign(3) – Linux Programmer's Manual – Library Functions