Zarovnání struktury dat - Data structure alignment

Zarovnání datové struktury je způsob uspořádání a přístupu k datům v paměti počítače . Skládá se ze tří samostatných, ale souvisejících otázek: zarovnání dat , datové struktury čalounění a balících .

CPU v moderní počítačový hardware provádí čte a zapisuje do paměti nejúčinněji, když jsou data přirozeně vyrovnány , což obecně znamená, že adresa paměti jsou data je násobkem velikosti dat. Například ve 32bitové architektuře mohou být data zarovnána, pokud jsou data uložena ve čtyřech po sobě jdoucích bajtech a první bajt leží na hranici 4 bajtů.

Zarovnání dat je zarovnání prvků podle jejich přirozeného zarovnání. Aby bylo zajištěno přirozené zarovnání, může být nutné vložit nějaké polstrování mezi prvky struktury nebo za poslední prvek struktury. Například na 32bitovém počítači by datová struktura obsahující 16bitovou hodnotu následovanou 32bitovou hodnotou mohla mít 16bitové odsazení mezi 16bitovou hodnotou a 32bitovou hodnotou pro zarovnání 32bitové hodnota na 32bitové hranici. Alternativně lze zabalit strukturu, vynechat odsazení, což může vést k pomalejšímu přístupu, ale využívá tři čtvrtiny paměti.

Přestože je zarovnání datové struktury zásadním problémem všech moderních počítačů, mnoho počítačových jazyků a implementace počítačových jazyků zarovnání dat zpracovává automaticky. Fortran , Ada , PL/I , Pascal , určité implementace C a C ++ , D , Rust , C# a montážní jazyk umožňují alespoň částečnou kontrolu polstrování datové struktury, což může být užitečné za určitých zvláštních okolností.

Definice

Adresa paměti a se říká, že je zarovnaná na n bytů, když a je násobkem n bytů (kde n je mocnina 2). V tomto kontextu je bajt nejmenší jednotkou přístupu do paměti, tj. Každá adresa paměti určuje jiný bajt. N -byte zarovnané adresa bude mít nejméně log 2 (N) nejméně významných nul, když jsou exprimovány v binárním formátu .

Alternativní znění zarovnané na bity určuje b/8 zarovnanou adresu (např. 64bitová zarovnání je zarovnaná na 8 bajtů).

Říká se, že přístup do paměti je zarovnán, když jsou data, ke kterým se přistupuje, dlouhá n  bytů a adresa počátku je zarovnaná na n bajtů. Je-li přístup do paměti nejsou vyrovnány, to je řekl, aby byl nevyrovnané . Všimněte si, že podle definice jsou přístupy k bajtové paměti vždy zarovnány.

Paměťový ukazatel, který odkazuje na primitivním dat, která je n  bajtů je řekl, aby byl vyrovnán , pokud je povoleno pouze obsahovat adresy, které jsou n -byte vyrovnané, jinak je prý nezarovnaný . Ukazatel paměti, který odkazuje na agregát dat (datovou strukturu nebo pole), je zarovnán, pokud (a pouze pokud) je zarovnán každý primitivní datum v agregátu.

Všimněte si toho, že výše uvedené definice předpokládají, že každý primitivní datum je mocnina o délce dvou bajtů. Pokud tomu tak není (jako u 80bitové s plovoucí desetinnou čárkou na x86 ) kontext ovlivňuje podmínky, kde je vztažný bod považován za zarovnaný nebo ne.

Datové struktury mohou být uloženy v paměti na zásobníku se statickou velikostí známou jako ohraničená nebo na haldě s dynamickou velikostí známou jako neomezená .

Problémy

CPU přistupuje k paměti jediným paměťovým slovem najednou. Dokud je velikost paměťového slova alespoň tak velká jako největší primitivní datový typ podporovaný počítačem, zarovnané přístupy budou vždy přistupovat k jednomu paměťovému slovu. To nemusí platit pro nesprávně zarovnané přístupy k datům.

Pokud nejvyšší a nejnižší bajty v nulovém bodu nejsou ve stejném paměťovém slově, musí počítač rozdělit přístup k nulovému bodu na více přístupů do paměti. K generování přístupů do paměti a jejich koordinaci je zapotřebí mnoho složitých obvodů. Aby procesor zvládl případ, kdy jsou paměťová slova na různých paměťových stránkách, musí před provedením instrukce buď ověřit, že jsou přítomny obě stránky, nebo musí být schopen zpracovat chybný TLB nebo chybu stránky při jakémkoli přístupu do paměti během provádění instrukce.

Některé návrhy procesorů se záměrně vyhýbají zavádění takové složitosti a místo toho poskytují alternativní chování v případě nesprávně zarovnaného přístupu k paměti. Například implementace architektury ARM před ARMv6 ISA vyžadují povinný přístup k zarovnané paměti pro všechny pokyny pro načítání a ukládání více bajtů. V závislosti na tom, která konkrétní instrukce byla vydána, může být výsledkem pokusu o nevyrovnaný přístup zaokrouhlení dolů nejméně významných bitů adresy, která se provinila, a její přeměna na zarovnaný přístup (někdy s dalšími výhradami) nebo vyvolání výjimky MMU (pokud je hardware MMU je přítomen), nebo tiše poskytne jiné potenciálně nepředvídatelné výsledky. Architektury ARMv6 a novější podporují nezarovnaný přístup za mnoha okolností, ale ne nutně všechny.

Když je přistupováno k jednomu paměťovému slovu, operace je atomická, tj. Celé paměťové slovo se čte nebo zapisuje najednou a ostatní zařízení musí počkat, až se operace čtení nebo zápisu dokončí, než k ní budou mít přístup. To nemusí platit pro nezarovnané přístupy k více paměťovým slovům, např. První slovo může být přečteno jedním zařízením, obě slova zapsána jiným zařízením a poté druhé slovo přečteno prvním zařízením, takže načtená hodnota není ani původní hodnotou ani aktualizovaná hodnota. Přestože jsou takové poruchy vzácné, lze je velmi obtížně identifikovat.

Polstrování datové struktury

Ačkoli kompilátor (nebo tlumočník ) obvykle přiděluje jednotlivé datové položky na zarovnané hranice, datové struktury mají často členy s různými požadavky na zarovnání. Aby bylo zachováno správné zarovnání, překladač normálně vkládá další nejmenované datové členy, aby byl každý člen správně zarovnán. Kromě toho může být datová struktura jako celek vyplněna konečným nejmenovaným členem. To umožňuje správné zarovnání každého člena pole struktur .

Polstrování je vloženo pouze tehdy, když za členem struktury následuje prut s větším požadavkem na zarovnání nebo na konci struktury. Změnou pořadí prvků ve struktuře je možné změnit množství výplně potřebné k udržení zarovnání. Pokud jsou například členové seřazeny podle sestupných požadavků na zarovnání, je vyžadováno minimální množství odsazení. Minimální požadované množství polstrování je vždy menší než největší zarovnání ve struktuře. Výpočet maximálního požadovaného množství výplně je složitější, ale je vždy menší než součet požadavků na zarovnání pro všechny prvky minus dvojnásobek součtu požadavků na zarovnání pro nejméně zarovnanou polovinu prvků struktury.

Ačkoli C a C ++ nedovolují kompilátoru změnit pořadí členů struktury, aby ušetřily místo, jiné jazyky mohou. Je také možné říci většině kompilátorů C a C ++, aby "sbalily" členy struktury na určitou úroveň zarovnání, např. "Pack (2)" znamená zarovnat datové členy větší než bajt na hranici dvou bajtů, takže všechny výplňové členy jsou maximálně jeden bajt dlouhé. Podobně v PL/I může být deklarována struktura, UNALIGNEDkterá eliminuje veškeré odsazení kromě kolem bitových řetězců.

Jedním z použití těchto „zabalených“ struktur je zachování paměti. Například struktura obsahující jeden bajt a čtyřbajtové celé číslo by vyžadovala tři další bajty odsazení. Velká řada takových struktur by v případě zabalení spotřebovala o 37,5% méně paměti, i když přístup ke každé struktuře může trvat déle. Tento kompromis lze považovat za formu časoprostorového kompromisu .

Ačkoli se k šetření paměťového prostoru nejčastěji používá použití „zabalených“ struktur , lze jej také použít k formátování datové struktury pro přenos pomocí standardního protokolu. Při tomto použití je ale také třeba dbát na to, aby hodnoty strukturních členů byly uloženy s endianitou požadovanou protokolem (často pořadí bajtů sítě ), která se může lišit od endianity používané nativně hostitelským počítačem.

Výpočetní výplň

Následující vzorce uvádějí počet výplňových bytů potřebných k zarovnání začátku datové struktury (kde mod je operátor modulo ):

padding = (align - (offset mod align)) mod align
aligned = offset + padding
        = offset + ((align - (offset mod align)) mod align)

Například výplň, která se má přidat k odsazení 0x59d pro 4bajtovou zarovnanou strukturu, je 3. Struktura pak začne na 0x5a0, což je násobek 4. Když je však zarovnání ofsetu již stejné jako zarovnání , druhé modulo in (align - (offset mod align)) mod align vrátí nulu, proto je původní hodnota ponechána beze změny.

Vzhledem k tomu, že zarovnání je podle definice mocninou dvou, lze operaci modulo omezit na bitově booleovskou operaci AND.

Následující vzorce produkují vyrovnané offset (pokud si je bitový A a ~ bitové NOT ):

padding = (align - (offset & (align - 1))) & (align - 1)
        = (-offset & (align - 1))
aligned = (offset + (align - 1)) & ~(align - 1)
        = (offset + (align - 1)) & -align

Typické zarovnání struktur C na x86

Členové datové struktury jsou uloženi postupně v paměti, takže v níže uvedené struktuře bude člen Data1 vždy předcházet Data2; a Data2 budou vždy předcházet Data3:

struct MyData
{
    short Data1;
    short Data2;
    short Data3;
};

Pokud je typ „short“ uložen ve dvou bajtech paměti, pak by každý člen výše zobrazené datové struktury byl zarovnán na 2 bajty. Data1 by byla na offsetu 0, Data2 na offsetu 2 a Data3 na offsetu 4. Velikost této struktury by byla 6 bytů.

Typ každého člena struktury má obvykle výchozí zarovnání, což znamená, že pokud není programátorem požadováno jinak, bude zarovnáno na předem určenou hranici. Následující typická zarovnání platí pro kompilátory společností Microsoft ( Visual C ++ ), Borland / CodeGear ( C ++ Builder ), Digital Mars (DMC) a GNU ( GCC ) při kompilaci pro 32bitové x86:

  • Char (jeden bajt) bude zarovnán 1 bajt.
  • Krátká (dva byty) budou zarovnány 2 byte.
  • Int (čtyři byty) budou vyrovnány 4-byte.
  • Dlouho (čtyři byty) budou vyrovnány 4-byte.
  • Float (čtyři byty) budou vyrovnány 4-byte.
  • A double (osm bajtů) bude 8-byte zarovnané na Windows a 4-bajt zarovnány na Linuxu (8-byte s -malign-double kompilace času opce).
  • Long (osm bajtů) budou vyrovnány 4-byte.
  • A dlouho dvojité (deset bajtů s C ++ Builder a DMC, osm bajtů s Visual C ++, dvanáct bajtů s GCC) bude 8 bajtů vyrovnán s C ++ Builder, 2-byte v jedné ose s DMC, 8-bajt zarovnány s vizuální C ++ a 4 bajty zarovnány s GCC.
  • Jakýkoli ukazatel (čtyři bajty) bude zarovnán na 4 bajty. (např .: char*, int*)

Jediné pozoruhodné rozdíly v zarovnání pro 64bitový systém LP64 ve srovnání s 32bitovým systémem jsou:

  • Dlouho (osm bajtů) bude zarovnán 8 bajtů.
  • A double (osm bajtů) bude zarovnán 8 bajtů.
  • Long (osm bajtů) bude zarovnán 8 bajtů.
  • A dlouho dvojité (osm bajtů s Visual C ++, šestnáct bajtů s GCC), bude 8 bajtů v souladu s Visual C ++ a 16 bajtů v jedné ose s GCC.
  • Jakýkoli ukazatel (osm bajtů) bude zarovnán na 8 bajtů.

Některé datové typy jsou závislé na implementaci.

Zde je struktura s členy různých typů, celkem 8 bajtů před kompilací:

struct MixedData
{
    char Data1;
    short Data2;
    int Data3;
    char Data4;
};

Po kompilaci bude datová struktura doplněna o výplňové bajty, aby bylo zajištěno správné zarovnání pro každý z jejích členů:

struct MixedData  /* After compilation in 32-bit x86 machine */
{
    char Data1; /* 1 byte */
    char Padding1[1]; /* 1 byte for the following 'short' to be aligned on a 2 byte boundary
assuming that the address where structure begins is an even number */
    short Data2; /* 2 bytes */
    int Data3;  /* 4 bytes - largest structure member */
    char Data4; /* 1 byte */
    char Padding2[3]; /* 3 bytes to make total size of the structure 12 bytes */
};

Kompilovaná velikost struktury je nyní 12 bajtů. Je důležité si uvědomit, že poslední člen je vyplněn požadovaným počtem bajtů, takže celková velikost struktury by měla být násobkem největšího zarovnání jakéhokoli prvku struktury (zarovnání (int) v tomto případě, které = 4 na linux-32bit/gcc).

V tomto případě se k poslednímu členu přidají 3 bajty, aby se struktura vyplnila na velikost 12 bajtů (zarovnání (int) × 3).

struct FinalPad {
  float x;
  char n[1];
};

V tomto případě celková velikost struktury sizeof (FinalPad) == 8 , ne 5 (takže velikost je násobkem 4 (zarovnání float)).

struct FinalPadShort {
  short s;
  char n[3];
};

V tomto případě celková velikost struktury sizeof (FinalPadShort) == 6 , not 5 (not 8 either) (so that the size is a multiple of 2 (alignment (short) = 2 on linux-32bit/gcc)).

Je možné změnit zarovnání struktur, aby se zmenšila paměť, kterou vyžadují (nebo aby odpovídala stávajícímu formátu) změnou pořadí členů struktury nebo změnou zarovnání kompilátoru (nebo „zabalení“) členů struktury.

struct MixedData  /* after reordering */
{
    char Data1;
    char Data4;   /* reordered */
    short Data2;
    int Data3;
};

Zkompilovaná velikost struktury nyní odpovídá předem zkompilované velikosti 8 bajtů . Všimněte si, že Padding1 [1] byl nahrazen (a tedy odstraněn) Data4 a Padding2 [3] již není nutný, protože struktura je již zarovnána na velikost dlouhého slova.

Alternativní způsob vynucování vyrovnání struktury MixedData, která má být zarovnána na hranici jednoho bajtu, způsobí, že předprocesor zahodí předem určené zarovnání členů struktury, a nebudou tedy vloženy žádné výplňové bajty.

I když neexistuje standardní způsob definování zarovnání členů struktury, některé kompilátory používají direktivy #pragma k určení balení uvnitř zdrojových souborů. Zde je příklad:

#pragma pack(push)  /* push current alignment to stack */
#pragma pack(1)     /* set alignment to 1 byte boundary */

struct MyPackedData
{
    char Data1;
    long Data2;
    char Data3;
};

#pragma pack(pop)   /* restore original alignment from stack */

Tato struktura by měla v 32bitovém systému zkompilovanou velikost 6 bajtů . Výše uvedené směrnice jsou k dispozici v překladačích společností Microsoft , Borland , GNU a mnoha dalších.

Další příklad:

struct MyPackedData
{
    char Data1;
    long Data2;
    char Data3;
} __attribute__((packed));

Výchozí balení a balíček #pragma

U některých kompilátorů Microsoft, zejména u procesorů RISC, existuje neočekávaný vztah mezi výchozím balením projektu (směrnice /Zp) a směrnicí #pragma pack . #Pragma pack směrnice bude moci být použit pouze ke snížení velikosti obalu o konstrukci z výchozí projekt balení. To vede k problémům s interoperabilitou s hlavičkami knihoven, které používají například #pragma pack (8) , pokud je balení projektu menší než toto. Z tohoto důvodu by nastavení zabalení projektu na jinou hodnotu, než je výchozí 8 bajtů, porušilo direktivy #pragma pack používané v záhlavích knihoven a vedlo k binární nekompatibilitě mezi strukturami. Toto omezení není k dispozici při kompilaci pro x86.

Přidělení paměti zarovnáno s řádky mezipaměti

Bylo by užitečné přidělit paměť zarovnanou na řádky mezipaměti . Pokud je pole rozděleno na více než jedno vlákno, na kterém má pracovat, může mít ohraničení podskupin, které není zarovnáno s řádky mezipaměti, vést ke snížení výkonu. Zde je příklad přidělení paměti (dvojité pole velikosti 10) zarovnáno do mezipaměti 64 bajtů.

#include <stdlib.h>
double *foo(void) {
   double *var;//create array of size 10
   int     ok;

   ok = posix_memalign((void**)&var, 64, 10*sizeof(double));

   if (ok != 0)
     return NULL;

   return var;
}

Hardwarový význam požadavků na zarovnání

Obavy o zarovnání mohou ovlivnit oblasti mnohem větší než struktura C, pokud je účelem efektivní mapování této oblasti pomocí mechanismu překladu adres hardwaru (přemapování PCI, provozování MMU ).

Například v 32bitovém operačním systému není stránka 4  KiB (4096 bajtů) jen libovolným 4 KiB kusem dat. Místo toho je to obvykle oblast paměti, která je zarovnána na hranici 4 KiB. Důvodem je, že zarovnání stránky na hranici velikosti stránky umožňuje hardwaru namapovat virtuální adresu na fyzickou adresu nahrazením vyšších bitů v adrese, nikoli složitou aritmetikou.

Příklad: Předpokládejme, že máme mapování TLB virtuální adresy 0x2CFC7000 na fyzickou adresu 0x12345000. (Všimněte si, že obě tyto adresy jsou zarovnány na hranici 4 KiB.) Přístup k datům umístěným na virtuální adrese va = 0x2CFC7ABC způsobí, že rozlišení TLB 0x2CFC7 až 0x12345 vydá fyzický přístup k pa = 0x12345ABC. Zde se 20/12bitové rozdělení naštěstí shoduje s hexadecimálním reprezentačním dělením s 5/3 číslicemi. Hardware může tento překlad implementovat jednoduše kombinací prvních 20 bitů fyzické adresy (0x12345) a posledních 12 bitů virtuální adresy (0xABC). Toto je také označováno jako fyzicky indexované (ABC) fyzicky označené (12345).

Blok dat o velikosti 2 (n+1) - 1 má vždy jeden dílčí blok o velikosti 2 n  zarovnaný na 2 n  bajtech.

Takto lze dynamický alokátor, který nemá žádné znalosti o zarovnání, poskytovat zarovnané vyrovnávací paměti za cenu faktoru dva při ztrátě prostoru.

// Example: get 4096 bytes aligned on a 4096 byte buffer with malloc()

// unaligned pointer to large area
void *up = malloc((1 << 13) - 1);
// well-aligned pointer to 4 KiB
void *ap = aligntonext(up, 12);

kde aligntonext ( p , r ) funguje tak, že přidá zarovnaný přírůstek a poté vymaže r nejméně významných bitů p . Možnou implementací je

// Assume `uint32_t p, bits;` for readability
#define alignto(p, bits)      (((p) >> bits) << bits)
#define aligntonext(p, bits)  alignto(((p) + (1 << bits) - 1), bits)

Poznámky

Reference

Další čtení

  • Bryant, Randal E .; David, O'Hallaron (2003). Počítačové systémy: perspektiva programátora (ed. 2003). Upper Saddle River, New Jersey, USA: Pearson Education . ISBN 0-13-034074-X.
  • „1. Úvod: Zarovnání segmentů“. 8086 Family Utilities - Uživatelská příručka pro vývojové systémy založené na 8080/8085 (PDF) . Revize E (A620/5821 6K DD ed.). Santa Clara, Kalifornie, USA: Intel Corporation . Květen 1982 [1980, 1978]. s. 1-6, 3-5. Objednací číslo: 9800639-04. Archivováno (PDF) z originálu na 2020-02-29 . Citováno 2020-02-29 . […] Segment může mít jeden (a v případě atributu inpage dva) z pěti atributů zarovnání: […] Byte, což znamená, že segment může být umístěn na jakékoli adrese. […] Word, což znamená, že segment lze umístit pouze na adresu, která je násobkem dvou, počínaje adresou 0H. […] Odstavec, což znamená, že segment lze umístit pouze na adresu, která je násobkem 16, počínaje adresou 0. […] Stránka, což znamená, že segment může být umístěn pouze na adrese, která je násobkem 256 , počínaje adresou 0. […] Stránka, což znamená, že segment může být umístěn na kterémkoli z předchozích atributů platí plus musí být umístěn tak, aby nepřekročil hranici stránky […] Kódy zarovnání jsou: […] B - byte […] W - slovo […] G - odstavec […] xR - stránka […] P - stránka […] A - absolutní […] x v kódu zarovnání stránky může být jakýkoli jiný kód zarovnání. […] Segment může mít atribut inpage, což znamená, že musí být umístěn na 256 bajtové stránce a může mít atribut word, což znamená, že musí být umístěn na sudém číslovaném bajtu. […]

externí odkazy