c campionamento - Qual è la regola rigorosa di aliasing?




6 Answers

Una tipica situazione in cui si verificano problemi di aliasing è quando si sovrappone una struct (come un device / network msg) su un buffer della dimensione della parola del proprio sistema (come un puntatore a uint32_t o uint16_t s). Quando sovrapponi una struttura su un tale buffer, o un buffer su una tale struttura attraverso il cast del puntatore, puoi facilmente violare le rigide regole di aliasing.

Quindi, in questo tipo di configurazione, se voglio inviare un messaggio a qualcosa, dovrei avere due puntatori incompatibili che puntano allo stesso blocco di memoria. Potrei quindi codificare in modo ingenuo qualcosa del genere:

typedef struct Msg
{
    unsigned int a;
    unsigned int b;
} Msg;

void SendWord(uint32_t);

int main(void)
{
    // Get a 32-bit buffer from the system
    uint32_t* buff = malloc(sizeof(Msg));

    // Alias that buffer through message
    Msg* msg = (Msg*)(buff);

    // Send a bunch of messages    
    for (int i =0; i < 10; ++i)
    {
        msg->a = i;
        msg->b = i+1;
        SendWord(buff[0]);
        SendWord(buff[1]);   
    }
}

La rigorosa regola di aliasing rende questa impostazione illegale: il dereferenziamento di un puntatore che alias un oggetto che non è di un tipo compatibile o uno degli altri tipi consentiti da C 2011 6.5 paragrafo 7 1 è un comportamento indefinito. Sfortunatamente, puoi ancora scrivere codice in questo modo, magari ricevere degli avvertimenti, farlo compilare bene, solo per avere strani comportamenti inaspettati quando esegui il codice.

(GCC appare piuttosto incoerente nella sua capacità di dare avvertimenti di aliasing, a volte dandoci un avvertimento amichevole e qualche volta no.)

Per capire perché questo comportamento è indefinito, dobbiamo pensare a cosa la rigida regola di aliasing compra il compilatore. Fondamentalmente, con questa regola, non deve pensare di inserire istruzioni per aggiornare il contenuto del buff ogni volta che si esegue il ciclo. Invece, quando si ottimizzano, con alcune assunzioni fastidiosamente non forzate sull'aliasing, possono omettere quelle istruzioni, caricare il buff[0] e buff[1 ] nei registri della CPU una volta prima dell'esecuzione del ciclo e accelerare il corpo del ciclo. Prima che fosse introdotto il rigoroso aliasing, il compilatore doveva vivere in uno stato di paranoia che il contenuto del buff poteva cambiare in qualsiasi momento da qualunque luogo. Quindi, per ottenere un vantaggio in termini di prestazioni extra e presumendo che la maggior parte delle persone non utilizzi puntatori di punteggiatura tipografica, è stata introdotta la rigorosa regola di aliasing.

Tenete a mente, se pensate che l'esempio sia inventato, questo potrebbe accadere anche se state passando un buffer ad un'altra funzione facendo l'invio per voi, se invece lo avete.

void SendMessage(uint32_t* buff, size_t size32)
{
    for (int i = 0; i < size32; ++i) 
    {
        SendWord(buff[i]);
    }
}

E abbiamo riscritto il nostro ciclo precedente per sfruttare questa comoda funzione

for (int i = 0; i < 10; ++i)
{
    msg->a = i;
    msg->b = i+1;
    SendMessage(buff, 2);
}

Il compilatore potrebbe o potrebbe non essere abbastanza o abbastanza intelligente da provare a inviare SendMessage e potrebbe decidere di caricare o meno il buff di nuovo. Se SendMessage fa parte di un'altra API compilata separatamente, probabilmente contiene istruzioni per caricare i contenuti del buff. Poi di nuovo, forse sei in C ++ e questa è solo una versione di intestazione basata su modelli che il compilatore pensa possa essere in linea. O forse è solo qualcosa che hai scritto nel tuo file .c per tua comodità. In ogni caso, un comportamento indefinito potrebbe comunque verificarsi. Anche quando conosciamo qualcosa di ciò che sta accadendo sotto il cofano, è ancora una violazione della regola, quindi non è garantito un comportamento ben definito. Quindi, semplicemente avvolgendo una funzione che prende il nostro buffer delimitato dalla parola, non è necessariamente d'aiuto.

Quindi come faccio ad aggirare questo?

  • Usa un sindacato. La maggior parte dei compilatori supporta questo senza lamentarsi del rigoroso aliasing. Questo è permesso in C99 e permesso esplicitamente in C11.

    union {
        Msg msg;
        unsigned int asBuffer[sizeof(Msg)/sizeof(unsigned int)];
    };
    
  • Puoi disabilitare il rigoroso aliasing nel tuo compilatore ( f[no-]strict-aliasing in gcc))

  • Puoi usare char* per l'aliasing invece della parola del tuo sistema. Le regole consentono un'eccezione per char* (incluso signed char e unsigned char ). Si presume sempre che char* alias altri tipi. Tuttavia, questo non funzionerà nell'altro modo: non ci sono supposizioni che la tua strucse alias un buffer di caratteri.

Attenzione per principianti

Questo è solo un potenziale campo minato quando si sovrappongono due tipi l'uno sull'altro. Dovresti anche imparare l' endianness , l' allineamento delle parole e come affrontare i problemi di allineamento attraverso il packing delle strutture correttamente.

Nota

1 I tipi che C 2011 6.5 7 consente a un lvalue di accedere sono:

  • un tipo compatibile con il tipo effettivo dell'oggetto,
  • una versione qualificata di un tipo compatibile con il tipo effettivo dell'oggetto,
  • un tipo che è il tipo firmato o non firmato corrispondente al tipo effettivo dell'oggetto,
  • un tipo che è il tipo firmato o senza segno corrispondente a una versione qualificata del tipo effettivo dell'oggetto,
  • un tipo aggregato o sindacale che include uno dei tipi sopra menzionati tra i suoi membri (incluso, in modo ricorsivo, un membro di un'unione subaggregata o contenuta), o
  • un tipo di personaggio.
frequenza numero

Quando si fa una domanda sul comportamento non definito comune in C , le anime sono più illuminate di quanto facesse riferimento alla rigida regola di aliasing.
Di cosa stanno parlando?




Questa è la regola di aliasing rigida, trovata nella sezione 3.10 dello standard C ++ 03 (altre risposte forniscono una buona spiegazione, ma nessuna ha fornito la regola stessa):

Se un programma tenta di accedere al valore memorizzato di un oggetto tramite un lvalue diverso da uno dei seguenti tipi, il comportamento non è definito:

  • il tipo dinamico dell'oggetto,
  • una versione cv-qualificata del tipo dinamico dell'oggetto,
  • un tipo che è il tipo firmato o senza segno corrispondente al tipo dinamico dell'oggetto,
  • un tipo che è il tipo firmato o senza segno corrispondente a una versione qualificata CV del tipo dinamico dell'oggetto,
  • un tipo aggregato o sindacale che include uno dei tipi sopra menzionati tra i suoi membri (incluso, in modo ricorsivo, un membro di un sindacato subaggregato o contenuto),
  • un tipo che è un tipo di classe base (possibilmente qualificato cv) del tipo dinamico dell'oggetto,
  • un tipo di char o unsigned char .

Formulazione C ++ 11 e C ++ 14 (modifiche enfatizzate):

Se un programma tenta di accedere al valore memorizzato di un oggetto tramite un glValue diverso da uno dei seguenti tipi, il comportamento non è definito:

  • il tipo dinamico dell'oggetto,
  • una versione cv-qualificata del tipo dinamico dell'oggetto,
  • un tipo simile (come definito in 4.4) al tipo dinamico dell'oggetto,
  • un tipo che è il tipo firmato o senza segno corrispondente al tipo dinamico dell'oggetto,
  • un tipo che è il tipo firmato o senza segno corrispondente a una versione qualificata CV del tipo dinamico dell'oggetto,
  • un tipo aggregato o di unione che include uno dei tipi sopra menzionati tra i suoi elementi o membri di dati non statici (incluso, in modo ricorsivo, un elemento o un membro di dati non statici di una unione parziale o contenuta),
  • un tipo che è un tipo di classe base (possibilmente qualificato cv) del tipo dinamico dell'oggetto,
  • un tipo di char o unsigned char .

Due modifiche erano piccole: glvalue invece di lvalue e chiarimenti del caso aggregato / unione.

Il terzo cambiamento rende più forte la garanzia (rilassa la forte regola dell'aliasing): il nuovo concetto di tipi simili che ora sono alias sicuri.

Anche la dicitura C (C99; ISO / IEC 9899: 1999 6.5 / 7; la stessa identica formulazione è utilizzata in ISO / IEC 9899: 2011 §6.5 ¶7):

Un oggetto deve avere il suo valore memorizzato accessibile solo da un'espressione lvalue che ha uno dei seguenti tipi 73) o 88) :

  • un tipo compatibile con il tipo effettivo dell'oggetto,
  • una versione quali fi cata di un tipo compatibile con il tipo effettivo dell'oggetto,
  • un tipo che è il tipo firmato o non firmato corrispondente al tipo effettivo dell'oggetto,
  • un tipo che è il tipo firmato o senza segno corrispondente a una versione quali fi cata del tipo effettivo dell'oggetto,
  • un tipo aggregato o sindacale che include uno dei tipi sopra menzionati tra i suoi membri (incluso, in modo ricorsivo, un membro di un'unione subaggregata o contenuta), o
  • un tipo di personaggio.

73) o 88) L'intento di questa lista è di specificare quelle circostanze in cui un oggetto può o non può essere aliasato.




Come addendum a ciò che Doug T. ha già scritto, ecco un semplice caso di test che probabilmente lo innesca con gcc:

check.c

#include <stdio.h>

void check(short *h,long *k)
{
    *h=5;
    *k=6;
    if (*h == 5)
        printf("strict aliasing problem\n");
}

int main(void)
{
    long      k[1];
    check((short *)k,k);
    return 0;
}

Compilare con gcc -O2 -o check check.c . Solitamente (con la maggior parte delle versioni di gcc che ho provato) questo produce "un rigoroso problema di aliasing", perché il compilatore presuppone che "h" non possa essere lo stesso indirizzo di "k" nella funzione "check". Per questo motivo il compilatore ottimizza il if (*h == 5) distanza e chiama sempre il printf.

Per chi fosse interessato ecco il codice assemblatore x64, prodotto da gcc 4.6.3, eseguito su ubuntu 12.04.2 per x64:

movw    $5, (%rdi)
movq    $6, (%rsi)
movl    $.LC0, %edi
jmp puts

Quindi la condizione if è completamente scomparsa dal codice assembler.




Digitare punire tramite cast di puntatore (al contrario di usare un'unione) è un importante esempio di rottura dell'aliasing rigoroso.




Dopo aver letto molte delle risposte, sento il bisogno di aggiungere qualcosa:

Aliasing rigoroso (che descriverò tra poco) è importante perché :

  1. L'accesso alla memoria può essere costoso (in termini di prestazioni), motivo per cui i dati vengono manipolati nei registri della CPU prima di essere riscritti nella memoria fisica.

  2. Se i dati in due diversi registri della CPU verranno scritti nello stesso spazio di memoria, non possiamo prevedere quali dati "sopravviveranno" quando codificheremo in C.

    In assembly, dove codifichiamo manualmente il caricamento e lo scaricamento dei registri della CPU, sapremo quali dati rimangono intatti. Ma C (per fortuna) riassume questo dettaglio.

Poiché due puntatori possono puntare alla stessa posizione nella memoria, ciò potrebbe comportare un codice complesso che gestisce possibili collisioni .

Questo codice extra è lento e fa male le prestazioni poiché esegue operazioni extra di lettura / scrittura della memoria che sono sia più lente che (eventualmente) non necessarie.

La regola di aliasing rigoroso ci consente di evitare il codice macchina ridondante nei casi in cui si dovrebbe essere sicuri che due puntatori non puntino allo stesso blocco di memoria (vedere anche la restrictparola chiave).

L'Aliasing Stretto afferma che è sicuro assumere che i puntatori a diversi tipi puntano a posizioni diverse nella memoria.

Se un compilatore rileva che due puntatori puntano a tipi diversi (ad esempio, a int *e a float *), assumerà che l'indirizzo di memoria è diverso e non proteggerà contro le collisioni dell'indirizzo di memoria, determinando un codice macchina più veloce.

Ad esempio :

Assumiamo la seguente funzione:

void merge_two_ints(int *a, int *b) {
  *b += *a;
  *a += *b;
}

Per gestire il caso in cui a == b(entrambi i puntatori puntano alla stessa memoria), dobbiamo ordinare e testare il modo in cui cariciamo i dati dalla memoria ai registri della CPU, quindi il codice potrebbe finire in questo modo:

  1. carico ae bdalla memoria.

  2. aggiungi aa b.

  3. salva b e ricarica a .

    (salvare dal registro della CPU alla memoria e caricare dalla memoria al registro della CPU).

  4. aggiungi ba a.

  5. salva a(dal registro CPU) nella memoria.

Il passaggio 3 è molto lento perché ha bisogno di accedere alla memoria fisica. Tuttavia, è necessario proteggere dalle istanze dove ae bpuntare allo stesso indirizzo di memoria.

Aliasing severo ci consentirebbe di evitare ciò dicendo al compilatore che questi indirizzi di memoria sono nettamente diversi (il che, in questo caso, consentirà un'ulteriore ottimizzazione che non può essere eseguita se i puntatori condividono un indirizzo di memoria).

  1. Questo può essere detto al compilatore in due modi, usando diversi tipi a cui puntare. vale a dire:

    void merge_two_numbers(int *a, long *b) {...}
    
  2. Usando la restrictparola chiave. vale a dire:

    void merge_two_ints(int * restrict a, int * restrict b) {...}
    

Ora, soddisfacendo la regola di aliasing severo, il passaggio 3 può essere evitato e il codice verrà eseguito molto più velocemente.

Infatti, aggiungendo la restrictparola chiave, l'intera funzione potrebbe essere ottimizzata per:

  1. carico ae bdalla memoria.

  2. aggiungi aa b.

  3. salva il risultato sia a ache a b.

Questa ottimizzazione non avrebbe potuto essere fatta prima, a causa della possibile collisione (dove ae bsarebbe triplicata anziché raddoppiata).




Tecnicamente in C ++, la rigorosa regola di aliasing non è probabilmente mai applicabile.

Nota la definizione di riferimento indiretto ( * operatore ):

L'operatore unario * esegue l'indirezione: l'espressione a cui viene applicato deve essere un puntatore a un tipo di oggetto o un puntatore a un tipo di funzione e il risultato è un lvalue che fa riferimento all'oggetto o alla funzione a cui punta l'espressione .

Anche dalla definizione di glvalue

Un glivalue è un'espressione la cui valutazione determina l'identità di un oggetto, (... snip)

Pertanto, in qualsiasi traccia di programma ben definita, un gl valore si riferisce a un oggetto. Quindi la cosiddetta regola di aliasing rigorosa non si applica mai. Questo potrebbe non essere ciò che i designer volevano.




Related

c undefined-behavior strict-aliasing type-punning