Oznaczony wskaźnik

W informatyce oznaczony wskaźnikiem jest wskaźnikiem ( konkretnie adresem pamięci ) z dodatkowymi danymi z nim związanymi, takimi jak bit pośredni lub liczba odwołań . Te dodatkowe dane są często „zwijane” we wskaźnik, co oznacza, że są przechowywane w linii danych reprezentujących adres, wykorzystując pewne właściwości adresowania pamięci. Nazwa pochodzi od „ tagowanej architektury „ systemy, które rezerwowały bity na poziomie sprzętowym, aby wskazać znaczenie każdego słowa; dodatkowe dane nazywane są „znacznikiem” lub „znacznikami”, chociaż ściśle mówiąc „znacznik” odnosi się do danych określających typ, a nie inne dane ; jednak , użycie „oznaczonego wskaźnika” jest wszechobecne.

Składanie znaczników do wskaźnika

Istnieją różne techniki składania znaczników we wskaźnik. ^{[ niewiarygodne źródło? ]}

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

I odwrotnie, w niektórych systemach operacyjnych adresy wirtualne są węższe niż ogólna 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 zwłaszcza w przypadku architektur 64-bitowych, ponieważ 64-bitowa przestrzeń adresowa znacznie przekracza wymagania dotyczące danych wszystkich aplikacji z wyjątkiem 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ż adres fizyczny szerokość, która z kolei może być węższa niż szerokość architektury; dla znakowania wskaźników w przestrzeni użytkownika , odpowiednia szerokość to wirtualna przestrzeń adresowa zapewniana przez system operacyjny (z kolei zapewniana przez jednostkę zarządzania pamięcią ). 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 większością znaczących bitów zerami lub tylko zerami.

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żyty jako specjalna pustego wskaźnika . W przeciwieństwie do wcześniej wspomnianych technik, pozwala to tylko na pojedynczą specjalną wartość wskaźnika, a nie dodatkowe dane dla wskaźników ogólnie.

Przykłady

Jednym z najwcześniejszych przykładów sprzętowej obsługi wskaźników ze znacznikami na platformie komercyjnej był IBM System/38 . IBM dodał później obsługę znaczników ze znacznikami do PowerPC , aby obsługiwać system operacyjny IBM i , który jest ewolucją platformy System / 38.

Znaczącym przykładem użycia oznaczonych wskaźników jest środowisko uruchomieniowe Objective-C w systemie iOS 7 na ARM64 , zwłaszcza używane w telefonie iPhone 5S . W systemie iOS 7 adresy wirtualne zawierają tylko 33 bity informacji adresowych, ale mają długość 64 bitów, pozostawiając 31 bitów na znaczniki. Wskaźniki klasy Objective-C są wyrównane do 8 bajtów, zwalniając dodatkowe 3 bity przestrzeni adresowej, a pola znaczników są używane do wielu celów, takich jak przechowywanie liczby odwołań i sprawdzanie, czy obiekt ma destruktor .

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

Wskaźnik zerowy a wyrównany

Użycie zera do reprezentowania wskaźnika zerowego jest niezwykle powszechne, a wiele języków programowania (takich jak Ada ) wyraźnie polega na tym zachowaniu. Teoretycznie inne wartości w bloku pamięci logicznej zarezerwowanej dla systemu operacyjnego mogłyby być użyte do oznaczania warunków innych niż wskaźnik zerowy, ale takie zastosowania wydają się rzadkie, być może dlatego, że w najlepszym razie nie są przenośne . Ogólnie przyjętą praktyką w projektowaniu oprogramowania jest to, że jeśli potrzebna jest specjalna wartość wskaźnika różna od null (taka jak wartość wskaźnika w niektórych strukturach danych ), programista powinien wyraźnie to zapewnić.

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 jakich można uzyskać do nich dostęp, lub innymi podobnymi informacjami o użyciu wskaźnika. Informacje te można podać wraz z każdym prawidłowym wskaźnikiem. W przeciwieństwie do tego, zerowe wskaźniki/strażnicy 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. Architektury ze znacznikami, takie jak maszyny Lisp , często mają sprzętowe wsparcie dla interpretacji i przetwarzania oznakowanych wskaźników.

GNU libc malloc() zapewnia adresy pamięci wyrównane do 8 bajtów dla platform 32-bitowych i wyrównanie do 16 bajtów 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 wskaźnika zerowego:

    
  
     

  
   
    
      

  
 void  opcjonalnie_return_a_value  (  int  *  opcjonalnie_return_value_pointer  )  {  /* ... */  int  value_to_return  =  1  ;  /* czy jest różny od NULL? (zwróć uwagę, że NULL, logiczny fałsz i zero są porównywane jednakowo w C) */   if  (  opcjonalny_wskaźnik_wartości_zwrotu  )  /* jeśli tak, użyj go do przekazania wartości do funkcji wywołującej */  *  opcjonalny_wskaźnik_wartości_zwrotu  =  wartość_do_zwrotu  ;  /* w przeciwnym razie wskaźnik nigdy nie jest wyłuskiwany */  }

Przykład 2

Tutaj programista udostępnił 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  )  /* zrób coś */  else  if  (  SENTINEL  ==  p  )  /* zrób coś innego */  else  /* traktuj p jako poprawny wskaźnik do węzła */  }

Przykład 3

Załóżmy, że mamy strukturę danych table_entry , która jest zawsze wyrównana do granicy 16 bajtów. Innymi słowy, najmniej znaczące 4 bity adresu wpisu w tablicy to zawsze 0 ( $24 = 16$ ). Moglibyśmy użyć tych 4 bitów do oznaczenia wpisu w tabeli dodatkowymi informacjami. Na przykład bit 0 może oznaczać tylko do odczytu, bit 1 może oznaczać zabrudzenie (wpis w tabeli wymaga aktualizacji) i tak dalej.

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

0x3421 jest wskaźnikiem tylko do odczytu do pozycji table_entry pod adresem 0x3420
0xf472 jest wskaźnikiem do brudnego wpisu tabeli pod adresem 0xf470

Zalety

Główną zaletą oznakowanych 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 dużych tabelach wskaźników.

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

Niedogodności

Wskaźniki ze znacznikami mają te same trudności, co listy połączone xor , chociaż w mniejszym stopniu. Na przykład nie wszystkie debugery będą mogły prawidłowo śledzić oznakowane wskaźniki; nie jest to jednak problemem dla debugera zaprojektowanego z myślą o oznakowanych 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ą solidność. Wyjątkiem jest sposób, w jaki zero uczestniczy w rozpoznawaniu przeciążenia w C++, gdzie zero jest traktowane jako liczba całkowita, a nie wskaźnik; z tego powodu wartość specjalna nullptr jest preferowana zamiast liczby całkowitej zero. Jednak w przypadku oznaczonych wskaźników zera zwykle nie są używane do reprezentowania wskaźników zerowych.