Označený ukazatel - Tagged pointer

Ve vědě o počítačích , je značená ukazatel je ukazatel (konkrétně adresa paměti ) s dalšími údaji s ním spojených, jako je například kousku indirection nebo počet odkazů . Tato dodatečná data se často „skládají“ do ukazatele, což znamená, že jsou uložena v datech představujících adresu a využívají výhod určitých vlastností adresování paměti. Název pochází ze systémů „ tagged architecture “, které si vyhrazují bity na hardwarové úrovni, aby označily význam každého slova; dodatečná data se nazývají „tag“ nebo „tagy“, i když přesně řečeno „tag“ označuje data specifikující typ, nikoli jiná data; použití „označeného ukazatele“ je však všudypřítomné.

Skládání značek do ukazatele

Existují různé techniky skládání značek do ukazatele.

Většina architektur je adresovatelná bajtem (nejmenší adresovatelnou jednotkou je bajt), ale určité typy dat budou často přizpůsobeny velikosti dat, často slovu nebo jeho násobku. Tato nesrovnalost ponechává několik nejméně významných bitů ukazatele nepoužitých, které lze použít pro značky - nejčastěji jako bitové pole (každý bit jako samostatná značka) - pokud kód, který používá ukazatel , tyto bity před přístupem maskuje Paměť. Např. Na 32bitové architektuře (pro adresy i velikost slova) má slovo 32 bitů = 4 bajty, takže adresy se slovem jsou vždy násobkem 4, proto končí v 00, takže poslední 2 bity jsou k dispozici; zatímco na 64bitové architektuře je slovo 64 bitů = 8 bajtů, takže adresy se slovem končí na 000, přičemž poslední 3 bity jsou k dispozici. V případech, kdy jsou data zarovnána na násobek velikosti slova, jsou k dispozici další bity. V případě architektur, které lze adresovat slovům, data zarovnaná podle slov nezanechávají žádné bity k dispozici, protože mezi zarovnáním a adresováním není žádný rozpor, ale data zarovnaná na násobek velikosti slova ano.

Naopak v některých operačních systémech jsou virtuální adresy užší než celková šířka architektury, což ponechává nejvýznamnější bity dostupné pro značky; to lze v případě zarovnaných adres kombinovat s předchozí technikou. To platí zejména pro 64bitové architektury, protože 64 bitů adresního prostoru je daleko nad datovými požadavky všech kromě největších aplikací, a proto má mnoho praktických 64bitových procesorů užší adresy. Všimněte si, že šířka virtuální adresy může být užší než šířka fyzické adresy , což může být zase užší než šířka architektury; pro označování ukazatelů v uživatelském prostoru je virtuální adresový prostor poskytovaný operačním systémem (zase poskytovaný jednotkou správy paměti ) relevantní šířka. Některé procesory ve skutečnosti výslovně zakazují použití takových označených ukazatelů na úrovni procesoru, zejména x86-64 , což vyžaduje použití kanonických formulářových adres operačním systémem, přičemž nejvýznamnější bity jsou všechny 0 nebo všechny 1 s.

A konečně, systém virtuální paměti ve většině moderních operačních systémů vyhrazuje blok logické paměti kolem adresy 0 jako nepoužitelný. To znamená, že například ukazatel na 0 nikdy není platným ukazatelem a lze jej použít jako speciální hodnotu ukazatele null . Na rozdíl od dříve zmíněných technik to umožňuje pouze jednu speciální hodnotu ukazatele, nikoli další data pro ukazatele obecně.

Příklady

Jedním z prvních příkladů hardwarové podpory pro tagované ukazatele na komerční platformě byl IBM System / 38 . Společnost IBM později přidala podporu označeného ukazatele do architektury PowerPC na podporu operačního systému IBM i , což je vývoj platformy System / 38.

Významným příkladem použití označených ukazatelů je modul runtime Objective-C v systému iOS 7 na ARM64 , který se používá zejména na iPhone 5S . V iOS 7 jsou virtuální adresy 33 bitů (zarovnané podle bajtů), takže adresy zarovnané podle slova používají pouze 30 bitů, přičemž u značek zůstávají 3 bity. Ukazatele třídy Objective-C jsou zarovnány na slovo a pole značek se používají k mnoha účelům, například k uložení počtu odkazů a k tomu, zda má objekt destruktor .

Starší verze systému MacOS používaly k ukládání odkazů na datové objekty označené adresy zvané Handles. Vysoké bity adresy označovaly, zda byl datový objekt uzamčen, očištěn a / nebo pochází ze souboru prostředků. To způsobilo problémy s kompatibilitou, když MacOS adresování pokročilo z 24 bitů na 32 bitů v systému 7.

Ukazatel nuly proti zarovnanému

Použití nuly k reprezentaci nulového ukazatele je extrémně běžné, přičemž mnoho programovacích jazyků (například Ada ) se na toto chování výslovně spoléhá. Teoreticky lze k označení podmínek jiných než nulový ukazatel použít jiné hodnoty v bloku logické paměti vyhrazené operačnímu systému, ale tato použití se zdají být vzácná, snad proto, že jsou přinejlepším nepřenosná . V softwarovém designu je obecně přijímanou praxí, že pokud je potřeba speciální hodnota ukazatele odlišná od null (například sentinel v určitých datových strukturách ), měl by to programátor výslovně zajistit.

Využití zarovnání ukazatelů poskytuje větší flexibilitu než nulové ukazatele / sentinely, protože umožňuje označování ukazatelů informacemi o typu namířených dat, podmínkách, za kterých k nim lze přistupovat, nebo jinými podobnými informacemi o použití ukazatele. Tyto informace lze poskytnout spolu s každým platným ukazatelem. Naproti tomu nulové ukazatele / sentinely poskytují pouze konečný počet označených hodnot odlišných od platných ukazatelů.

V tagované architektuře je počet bitů v každém slově paměti vyhrazen, aby fungoval jako tag. Značkové architektury, jako jsou stroje Lisp , často mají hardwarovou podporu pro interpretaci a zpracování označených ukazatelů.

GNU libc malloc() poskytuje 8bajtové adresy paměti pro 32bitové platformy a 16bajtové zarovnání pro 64bitové platformy. Větší hodnoty zarovnání lze získat pomocí posix_memalign() .

Příklady

Příklad 1

V následujícím C kódu se hodnota nula používá k označení nulového ukazatele:

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 */
}

Příklad 2

Zde programátor poskytl globální proměnnou, jejíž adresa se poté použije jako indikátor:

#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 */
}

Příklad 3

Předpokládejme, že máme datovou strukturu, table_entry která je vždy zarovnána na hranici 16 bajtů. Jinými slovy, nejméně významné 4 bity adresy položky tabulky jsou vždy 0 ( 2 ⁴ = 16 ). Tyto 4 bity bychom mohli použít k označení záznamu v tabulce dalšími informacemi. Například bit 0 může znamenat pouze pro čtení, bit 1 může znamenat špinavý (záznam v tabulce je třeba aktualizovat) atd.

Pokud jsou ukazatele 16bitové hodnoty, pak:

• 0x3421 je ukazatel jen pro čtení table_entry na adresu at 0x3420
• 0xf472 je ukazatel na špinavou table_entry adresu 0xf470

Výhody

Hlavní výhodou označených ukazatelů je, že zabírají méně místa než ukazatel spolu se samostatným polem značky. To může být obzvláště důležité, když je ukazatel návratová hodnota z funkce . Může to být také důležité ve velkých tabulkách ukazatelů.

Drobnější výhodou je, že uložením značky na stejné místo jako ukazatel je často možné zaručit atomicitu operace, která aktualizuje ukazatel i jeho značku bez mechanismů externí synchronizace . To může být extrémně velký nárůst výkonu, zejména v operačních systémech.

Nevýhody

Označené ukazatele mají stejné problémy jako seznamy propojené xor , i když v menší míře. Například ne všichni debuggery budou moci správně sledovat tagované ukazatele; to však není problém pro debugger, který je navržen s ohledem na tagované ukazatele.

Použití nuly k reprezentaci nulového ukazatele netrpí těmito nevýhodami: je všudypřítomné, většina programovacích jazyků považuje nulu za speciální nulovou hodnotu a důkladně prokázala svou robustnost. Výjimkou je způsob, jakým se nula účastní rozlišení přetížení v C ++, kde nula je považována spíše za celé číslo než za ukazatel; z tohoto důvodu je upřednostňována speciální hodnota nullptr před celým číslem nula. U označených ukazatelů se však nuly obvykle nepoužívají k reprezentaci nulových ukazatelů.

Reference