Oznaczony wskaźnik - Tagged pointer

W informatyce , A znakowany wskaźnik to wskaźnik (konkretnie adres pamięci ) z dodatkowymi danymi z nim związanych, takich jak na kawałku zadnie lub liczby odniesienia . Te dodatkowe dane są często „składane” we wskaźnik, co oznacza, że ​​są przechowywane w danych reprezentujących adres, wykorzystując pewne właściwości adresowania pamięci. Nazwa pochodzi od systemów „ architektury ze znacznikami ”, które zarezerwowały bity na poziomie sprzętowym, aby wskazać znaczenie każdego słowa; dodatkowe dane nazywane są „znacznikami” lub „znacznikami”, chociaż ściśle mówiąc „znacznik” odnosi się do danych określających typ, a nie innych danych; jednak użycie „oznaczonego wskaźnika” jest wszechobecne.

Składanie tagów we wskaźnik

Istnieją różne techniki składania znaczników we wskaźnik.

Większość architektur jest adresowalna bajtowo (najmniejszą adresowalną jednostką jest bajt), ale niektóre typy danych często są dopasowywane do rozmiaru danych, często jest to słowo lub jego wielokrotność. Ta rozbieżność pozostawia kilka najmniej znaczących bitów wskaźnika nieużywanych, które mogą być używane dla tagów - najczęściej jako pole bitowe (każdy bit jest oddzielnym znacznikiem) - o ile kod, który używa wskaźnika, maskuje te bity przed uzyskaniem dostępu pamięć. Np. W architekturze 32-bitowej (zarówno dla adresów, jak i dla rozmiaru słowa), słowo ma 32 bity = 4 bajty, więc adresy wyrównane do słów są zawsze wielokrotnością 4, stąd kończą się na 00, pozostawiając ostatnie 2 bity dostępne; podczas gdy w architekturze 64-bitowej słowo ma 64 bity = 8 bajtów, więc adresy wyrównane do słów kończą się na 000, pozostawiając 3 ostatnie dostępne bity. W przypadkach, gdy dane są wyrównane przy wielokrotności rozmiaru słowa, dostępne są dalsze bity. W przypadku architektur adresowalnych według słów, dane wyrównane do słów nie pozostawiają żadnych dostępnych bitów, ponieważ nie ma rozbieżności między wyrównaniem a adresowaniem, ale dane wyrównane przy wielokrotności rozmiaru słowa już tak.

I odwrotnie, w niektórych systemach operacyjnych adresy wirtualne są węższe niż całkowita szerokość architektury, co pozostawia najbardziej znaczące bity dostępne dla znaczników; można to połączyć z poprzednią techniką w przypadku wyrównanych adresów. Dzieje się tak szczególnie w przypadku architektur 64-bitowych, ponieważ 64 bity przestrzeni adresowej znacznie przekraczają wymagania dotyczące danych we wszystkich aplikacjach oprócz największych, a zatem wiele praktycznych procesorów 64-bitowych ma węższe adresy. Należy zauważyć, że szerokość adresu wirtualnego może być węższa niż szerokość adresu fizycznego , która z kolei może być węższa niż szerokość architektury; do oznaczania wskaźników w przestrzeni użytkownika , wirtualna przestrzeń adresowa zapewniana przez system operacyjny (z kolei zapewniana przez jednostkę zarządzającą pamięcią ) ma odpowiednią szerokość. W rzeczywistości niektóre procesory wyraźnie zabraniają używania takich oznaczonych wskaźników na poziomie procesora, zwłaszcza x86-64 , co wymaga użycia adresów w postaci kanonicznej przez system operacyjny, z najbardziej znaczącymi bitami zerowymi lub jednymi.

Wreszcie system pamięci wirtualnej w większości nowoczesnych systemów operacyjnych rezerwuje blok pamięci logicznej wokół adresu 0 jako bezużyteczny. Oznacza to, że na przykład wskaźnik do 0 nigdy nie jest prawidłowym wskaźnikiem i może być używany jako specjalna wartość wskaźnika zerowego . W przeciwieństwie do wcześniej wspomnianych technik, pozwala to tylko na jedną specjalną wartość wskaźnika, a nie na dodatkowe dane dla wskaźników ogólnie.

Przykłady

Jednym z najwcześniejszych przykładów wsparcia sprzętowego oznaczonych wskaźników na platformie komercyjnej był IBM System / 38 . Później IBM dodał obsługę znaczonych wskaźników do architektury PowerPC, aby obsługiwać system operacyjny IBM i , który jest ewolucją platformy System / 38.

Istotnym przykładem użycia oznaczonych wskaźników jest środowisko uruchomieniowe Objective-C na iOS 7 na ARM64 , szczególnie używane na iPhonie 5S . W systemie iOS 7 adresy wirtualne mają 33 bity (wyrównane do bajtów), więc adresy wyrównane do słów używają tylko 30 bitów, pozostawiając 3 bity na znaczniki. Wskaźniki klasy Objective-C są wyrównane do słów, a pola znaczników są używane do wielu celów, takich jak przechowywanie liczby odwołań i określanie, czy obiekt ma destruktor .

Wczesne wersje systemu MacOS wykorzystywały oznaczone adresy zwane uchwytami do przechowywania odniesień do obiektów danych. Wysokie bity adresu wskazywały, czy obiekt danych był odpowiednio zablokowany, możliwy do usunięcia i / lub pochodził z pliku zasobów. Spowodowało to problemy ze zgodnością, gdy adresowanie MacOS wzrosło z 24 do 32 bitów w Systemie 7.

Wskaźnik zerowy i wyrównany

Używanie zera do reprezentowania pustego wskaźnika jest niezwykle powszechne, ponieważ wiele języków programowania (takich jak Ada ) wyraźnie polega na tym zachowaniu. Teoretycznie inne wartości w bloku pamięci logicznej zarezerwowanym przez system operacyjny mogą być używane do oznaczania warunków innych niż wskaźnik zerowy, ale te zastosowania wydają się być rzadkie, być może dlatego, że w najlepszym przypadku są nieprzenośne . Powszechnie przyjętą praktyką w projektowaniu oprogramowania jest to, że jeśli potrzebna jest specjalna wartość wskaźnika różna od null (taka jak wartownik w pewnych strukturach danych ), programista powinien wyraźnie to przewidzieć.

Wykorzystanie wyrównania wskaźników zapewnia większą elastyczność niż zerowe wskaźniki / wartowniki, ponieważ umożliwia oznaczanie wskaźników informacjami o typie wskazywanych danych, warunkach, w których można uzyskać do nich dostęp, lub innymi podobnymi informacjami o użyciu wskaźnika. Ta informacja może być dostarczona wraz z każdym prawidłowym wskaźnikiem. Natomiast zerowe wskaźniki / wartowniki zapewniają tylko skończoną liczbę oznaczonych wartości, różniących się od prawidłowych wskaźników.

W architekturze ze znacznikami pewna liczba bitów w każdym słowie pamięci jest zarezerwowana do działania jako znacznik. Otagowane architektury, takie jak maszyny Lisp , często mają sprzętową obsługę do interpretacji i przetwarzania oznaczonych wskaźników.

GNU libc malloc() zapewnia wyrównane adresy pamięci 8-bajtowe dla platform 32-bitowych i wyrównanie 16-bajtowe dla platform 64-bitowych. Większe wartości wyrównania można uzyskać za pomocą posix_memalign() .

Przykłady

Przykład 1

W poniższym kodzie C wartość zero jest używana do wskazania pustego wskaźnika: 

void optionally_return_a_value (int* optional_return_value_pointer) {
  /* ... */
  int value_to_return = 1;

  /* is it non-NULL? (note that NULL, logical false, and zero compare equally in C) */
  if (optional_return_value_pointer)
    /* if so, use it to pass a value to the calling function */
    *optional_return_value_pointer = value_to_return;

  /* otherwise, the pointer is never dereferenced */
}

Przykład 2

Tutaj programista dostarczył zmienną globalną, której adres jest następnie używany jako wartownik: 

#define SENTINEL &sentinel_s

node_t sentinel_s;

void do_something_to_a_node (node_t * p) {
  if (NULL == p)
    /* do something */
  else if (SENTINEL == p)
    /* do something else */
  else
    /* treat p as a valid pointer to a node */
}

Przykład 3

Załóżmy, że mamy strukturę danych, table_entry która jest zawsze wyrównana do 16-bajtowej granicy. Innymi słowy, najmniej znaczące 4 bity adresu wpisu tablicy mają zawsze wartość 0 ( 2 4 = 16 ). Moglibyśmy użyć tych 4 bitów do oznaczenia wpisu tablicy dodatkowymi informacjami. Na przykład bit 0 może oznaczać tylko do odczytu, bit 1 może oznaczać brudny (wpis w tablicy musi zostać zaktualizowany) i tak dalej.

Jeśli wskaźniki są wartościami 16-bitowymi, to:

  • 0x3421 jest wskaźnikiem tylko do odczytu do table_entry adresu at 0x3420
  • 0xf472 jest wskaźnikiem do brudnego table_entry adresu 0xf470

Zalety

Główną zaletą oznaczonych wskaźników jest to, że zajmują mniej miejsca niż wskaźnik wraz z oddzielnym polem znacznika. Może to być szczególnie ważne, gdy wskaźnik jest wartością zwracaną przez funkcję . Może to być również ważne w przypadku dużych tabel wskaźników.

Bardziej subtelną zaletą jest to, że przechowując tag w tym samym miejscu co wskaźnik, często można zagwarantować atomowość operacji, która aktualizuje zarówno wskaźnik, jak i jego tag bez zewnętrznych mechanizmów synchronizacji . Może to być bardzo duży wzrost wydajności, szczególnie w systemach operacyjnych.

Niedogodności

Oznaczone wskaźniki mają te same trudności, co listy połączone xor , chociaż w mniejszym stopniu. Na przykład, nie wszystkie debuggery będą w stanie poprawnie śledzić oznakowane wskaźniki; nie jest to jednak problem w przypadku debugera zaprojektowanego z myślą o oznaczonych wskaźnikach.

Użycie zera do reprezentowania wskaźnika zerowego nie ma tych wad: jest wszechobecne, większość języków programowania traktuje zero jako specjalną wartość zerową i dokładnie udowodniło swoją niezawodność. Wyjątkiem jest sposób, w jaki zero uczestniczy w rozwiązywaniu przeciążeń w C ++, gdzie zero jest traktowane jako liczba całkowita, a nie wskaźnik; z tego powodu specjalna wartość nullptr jest preferowana w stosunku do liczby całkowitej zero. Jednak w przypadku wskaźników oznaczonych zera zwykle nie są używane do reprezentowania wskaźników zerowych.

Bibliografia