Taggad pekare

Inom datavetenskap är en taggad pekare en pekare (konkret en minnesadress ) med ytterligare data associerade med den, såsom en inriktningsbit eller referensräkning . Dessa ytterligare data "viks" ofta in i pekaren, vilket betyder lagrad inline i data som representerar adressen, och drar fördel av vissa egenskaper hos minnesadressering. Namnet kommer från " taggad arkitektur "-system, som reserverade bitar på hårdvarunivå för att indikera betydelsen av varje ord; tilläggsdata kallas "tag" eller "taggar", även om "tagg" strikt sett hänvisar till data som anger en typ, inte andra data; dock är användningen "taggad pekare" allestädes närvarande.

Vik taggar i pekaren

Det finns olika tekniker för att vika taggar till en pekare. ^{[ opålitlig källa? ]}

De flesta arkitekturer är byteadresserbara (den minsta adresserbara enheten är en byte), men vissa typer av data kommer ofta att anpassas till storleken på datan, ofta ett ord eller multipel därav. Denna avvikelse lämnar några av de minst signifikanta bitarna av pekaren oanvända, som kan användas för taggar – oftast som ett bitfält (varje bit en separat tagg) – så länge som kod som använder pekaren maskerar dessa bitar innan de kommer åt minne. Till exempel, på en 32-bitars arkitektur (för både adresser och ordstorlek), är ett ord 32 bitar = 4 byte, så ordjusterade adresser är alltid en multipel av 4, och slutar därför på 00, vilket lämnar de sista 2 bitarna tillgängliga; medan på en 64-bitars arkitektur är ett ord 64 bitar = 8 byte, så ordjusterade adresser slutar på 000, vilket lämnar de sista 3 bitarna tillgängliga. I fall där data är inriktade med en multipel av ordstorlek, finns ytterligare bitar tillgängliga. I fallet med ordadresserbara arkitekturer lämnar ordjusterade data inga bitar tillgängliga, eftersom det inte finns någon diskrepans mellan justering och adressering, men data som justerats med en multipel av ordstorlek gör det.

Omvänt, i vissa operativsystem är virtuella adresser smalare än den övergripande arkitekturens bredd, vilket lämnar de mest signifikanta bitarna tillgängliga för taggar; detta kan kombineras med den tidigare tekniken vid justerade adresser. Detta är särskilt fallet på 64-bitars arkitekturer, eftersom 64-bitars adressutrymme ligger långt över datakraven för alla utom de största applikationerna, och därför har många praktiska 64-bitars processorer smalare adresser. Observera att den virtuella adressbredden kan vara smalare än den fysiska adressbredden, som i sin tur kan vara smalare än arkitekturens bredd; för taggning av pekare i användarutrymme är det virtuella adressutrymmet som tillhandahålls av operativsystemet (i sin tur tillhandahållet av minneshanteringsenheten) den relevanta bredden. Faktum är att vissa processorer specifikt förbjuder användning av sådana taggade pekare på processornivå, särskilt x86-64 , vilket kräver användning av kanoniska formatadresser av operativsystemet, med de flesta signifikanta bitarna alla 0:or eller alla 1:or.

Slutligen reserverar det virtuella minnessystemet i de flesta moderna operativsystem ett logiskt minnesblock runt adress 0 som oanvändbart. Det betyder att till exempel en pekare till 0 aldrig är en giltig pekare och kan användas som ett speciellt nollpekarvärde . Till skillnad från de tidigare nämnda teknikerna tillåter detta bara ett enda speciellt pekarvärde, inte extra data för pekare i allmänhet.

Exempel

Ett av de tidigaste exemplen på hårdvarustöd för taggade pekare i en kommersiell plattform var IBM System/38 . IBM lade senare till taggat pekarstöd till PowerPC- arkitekturen för att stödja operativsystemet IBM i , som är en vidareutveckling av System/38-plattformen.

Ett betydelsefullt exempel på användningen av taggade pekare är Objective-C runtime på iOS 7 på ARM64 , särskilt använd på iPhone 5S . I iOS 7 innehåller virtuella adresser bara 33 bitar adressinformation men är 64 bitar långa och lämnar 31 bitar för taggar. Objective-C klasspekare är 8-byte justerade och frigör ytterligare 3 bitar av adressutrymme, och taggfälten används för många ändamål, som att lagra ett referensantal och om objektet har en destruktor .

Tidiga versioner av MacOS använde taggade adresser som kallas Handles för att lagra referenser till dataobjekt. De höga bitarna i adressen indikerade om dataobjektet var låst, rensningsbart och/eller härrörde från en resursfil. Detta orsakade kompatibilitetsproblem när MacOS-adressering avancerade från 24 bitar till 32 bitar i System 7.

Null kontra justerad pekare

Användning av noll för att representera en nollpekare är extremt vanligt, med många programmeringsspråk (som Ada ) som uttryckligen förlitar sig på detta beteende. I teorin kan andra värden i ett operativsystem reserverat block av logiskt minne användas för att tagga andra villkor än en nollpekare, men dessa användningar verkar vara sällsynta, kanske för att de i bästa fall är icke- portabla . Det är allmänt accepterad praxis inom mjukvarudesign att om ett speciellt pekarvärde som är skilt från null (som en vaktpost i vissa datastrukturer ) behövs, bör programmeraren uttryckligen tillhandahålla det.

Att dra fördel av inriktningen av pekare ger mer flexibilitet än nollpekare/vaktposter eftersom det gör att pekare kan taggas med information om vilken typ av data som pekas på, förhållanden under vilka den kan nås eller annan liknande information om pekarens användning. Denna information kan tillhandahållas tillsammans med varje giltig pekare. Däremot tillhandahåller nollpekare/vaktposter endast ett ändligt antal taggade värden skilda från giltiga pekare.

I en taggad arkitektur är ett antal bitar i varje minnesord reserverade för att fungera som en tagg. Taggade arkitekturer, som Lisp-maskinerna , har ofta hårdvarustöd för att tolka och bearbeta taggade pekare.

GNU libc malloc() tillhandahåller 8-byte justerade minnesadresser för 32-bitars plattformar och 16-byte anpassning för 64-bitars plattformar. Större inriktningsvärden kan erhållas med posix_memalign() .

Exempel

Exempel 1

I följande C-kod används värdet noll för att indikera en nollpekare:

    
  
     

  
   
    
      

  
 void  optionally_return_a_value  (  int  *  optional_return_value_pointer  )  {  /* ... */  int  value_to_return  =  1  ;  /* är det icke-NULL? (observera att NULL, logiskt falskt och noll jämförs lika i C) */   if  (  optional_return_value_pointer  )  /* om så är fallet, använd det för att skicka ett värde till den anropande funktionen */  *  optional_return_value_pointer  =  value_to_return  ;  /* annars avviks pekaren aldrig */  }

Exempel 2

Här har programmeraren tillhandahållit en global variabel, vars adress sedan används som en vaktpost:



 

     
     
    
      
    
  
    
 #define SENTINEL &sentinel_s  node_t  sentinel_s  ;  void  do_something_to_a_node  (  node_t  *  p  )  {  if  (  NULL  ==  p  )  /* gör något */  else  if  (  SENTINEL  ==  p  )  /* gör något annat */  else  /* behandla p som en giltig pekare till en nod */  }

Exempel 3

Antag att vi har en datastruktur table_entry som alltid är justerad till en 16 byte-gräns. Med andra ord är de minst signifikanta 4 bitarna av en tabellposts adress alltid 0 ( 2 $4 = 16$ ). Vi skulle kunna använda dessa 4 bitar för att markera tabellposten med extra information. Till exempel kan bit 0 betyda skrivskyddad, bit 1 kan betyda smutsig (tabellposten måste uppdateras) och så vidare.

Om pekare är 16-bitars värden, då:

0x3421 är en skrivskyddad pekare till table_entry på adressen 0x3420
0xf472 är en pekare till en smutsig table_entry på adressen 0xf470

Fördelar

Den stora fördelen med taggade pekare är att de tar mindre plats än en pekare tillsammans med ett separat taggfält. Detta kan vara särskilt viktigt när en pekare är ett returvärde från en funktion . Det kan också vara viktigt i stora tabeller med pekare.

En mer subtil fördel är att genom att lagra en tagg på samma plats som pekaren är det ofta möjligt att garantera atomiciteten hos en operation som uppdaterar både pekaren och dess tagg utan externa synkroniseringsmekanismer . Detta kan vara en extremt stor prestandavinst, särskilt i operativsystem.

Nackdelar

Taggade pekare har några av samma svårigheter som xor länkade listor , men i mindre utsträckning. Till exempel kommer inte alla debuggers att kunna följa taggade pekare korrekt; detta är dock inte ett problem för en debugger som är designad med taggade pekare i åtanke.

Användningen av noll för att representera en nollpekare lider inte av dessa nackdelar: den är genomgripande, de flesta programmeringsspråk behandlar noll som ett speciellt nollvärde, och det har grundligt bevisat sin robusthet. Ett undantag är sättet att noll deltar i överbelastningsupplösning i C++, där noll behandlas som ett heltal snarare än en pekare; av denna anledning är specialvärdet nullptr att föredra framför heltal noll. Men med taggade pekare används vanligtvis inte nollor för att representera nollpekare.