Newsgroup: it.comp.lang.c
Titolo: Data alignment

Mi chiedo: i membri di una struttura vengono automaticamente allineati
dal compilatore C in modo che l'accesso sia possibile o semplicemente
più veloce?
In un programma di test faccio:
  unsigned char data[3] = { 0x01, 0x02, 0x03 };
  printf("%d %d\n", *(int *)&data[0], *(int *)&data[1]);
Il risultato è
  513 770
dove 513 = 0x0201 e 770 = 0x0302 (l'architettura è infatti a 16 bit
con memorizzazione in Little Endian).
Questo esempio mi fa capire che l'accesso ad interi *non* allineati
sia comunque possibile (770 è infatti un intero non allineato ai 2
byte). E' garantito che sia così in tutte le piattaforme e compilatori
C?
Se quindi l'accesso non allineato è comunque possibile, a che scopo
viene inserito il padding dal compilatore tra i campi di una struct/
union per garantire l'allineamento?

 union per garantire l'allineamento?
non è sempre possibile, e dove lo è non è detto che sia la soluzione
migliore.
Ciao!

 union per garantire l'allineamento?
Come detto l'accesso a dati non allineati è sempre possibile, ma su 
certi processori può essere costoso in termini di istruzioni.
L'esempio che porti causa una sola lettura di memoria per leggere 16 
bit all'indirizzo di data[0] (se è allineato ai 16 bit), mentre causa 
due letture per leggere 16 bit all'indirizzo data[1].  Dovendo 
acquisire 8 bit da ogni indirizzo è inoltre necessario una 
elaborazione delle due letture per mettere al posto giusto ciascun 
gruppo di bit.  Su alcuni tipi di processore ciò richiede più registri 
e varie operazioni di shift e merge dei risultati di lettura.  Su 
alcuni ciò avviene in modo più o meno automatico, su altri deve essre 
il compilatore che genera le istruzioni necessarie.
Ciao
Giovanni
-- 
   A computer is like an air conditioner,
   it stops working when you open Windows.
   < 
http://giovanni.homelinux.net/
 >

 il compilatore che genera le istruzioni necessarie.
Però non capisco una cosa. Un puntatore generico cambia a runtime.
Come può il compilatore sapere se è allineato o meno e aggiungere le
istruzioni relative (se è compito del compilatore piuttosto che del
processore)?
Forse aggiunge sempre le istruzioni sovrabbondanti supponendo un
puntatore disallineato?
Per esempio, la funzione seguente:
  int
  getint(void *ptr)  {
    return *(int *)ptr;
  }
come viene tradotta?

 puntatore disallineato?
in caso sia void* sì.
Lo standard, riguardo al void*, ti garantisce la sicurezza
d'allineamento solo se converti da un tipo a void e poi di nuovo al
tipo di partenza.
Ciao!

 tipo di partenza.
Capito, ma la cosa succede anche se si forza, con un cast, un
puntatore
allineato al byte (tipo char) ad un tipo allineato alla word (tipo
int)?
Cioè, se faccio (come nel mio primo esempio):
  unsigned char data[] = { 0x01, 0x02, 0x03 };
  int x = *(int *)&data[1];
sto forzando un puntatore a unsigned char (&data[1]), quindi allineato
al byte,
ad essere un puntatore a int, quindi allineato alla word. Il
compilatore, se è il caso
(considerando l'architettura del processore) inserisce automaticamente
le
istruzioni per la lettura disallineata?


Boh! :-) Essendo una feature non standard, dipende dal compilatore!
Ciao!




Come ho già risposto il compilatore genererà le istruzioni per leggere
correttamente il dato.  A livello del linguaggio non esiste alcuna 
differenza, ma ogni compilatore genera le istruzioni per il processore 
target.
Per esempio il seguente codice:
struct {
   char str[10];
   int  num;
} var;
int num0;
int num3;
int funct(void)
{
   num0 = *((int *)&var.str[0]);
   num3 = *((int *)&var.str[3]);
   return num0 + num3;
}
produce per i processori della famiglia x86 il seguente codice:
         .file   "tst.c"
         .comm   var,16,4
         .comm   num0,4,4
         .comm   num3,4,4
         .text
.globl funct
         .type   funct, @function
funct:
         pushl   %ebp
         movl    %esp, %ebp
         movl    $var, %eax   !! indirizzo di var.str
         movl    (%eax), %eax !! legge 4 byte all'indirizzo var.str
         movl    %eax, num0
         movl    $var, %eax   !! indirizzo di var.str
         addl    $3, %eax     !! indirizzo di var.str[3]
         movl    (%eax), %eax !! legge 4 byte all'indirizzo var.str[3]
         movl    %eax, num3
         movl    num0, %edx
         movl    num3, %eax
         leal    (%edx,%eax), %eax
         popl    %ebp
         ret
         .size   funct, .-funct
         .ident  "GCC: (GNU) 4.4.4"
Come si può vedere non vi è alcuna differenza nel codice generato (a 
parte il calcolo dell'indirizzo).  Tuttavia nei processori moderni 
l'accesso alla memoria è dettato dalla dimensione del bus e nel caso 
di accesso ad str[3] sono richieste 2 letture di memoria.  Queste sono 
coordinate all'interno del processore ed il compilatore non deve 
preoccuparsene.
Altri processori (quelli RISC per esempio) non hanno un set di 
istruzioni così complesso ed intelligente ed il compilatore deve 
prendersi carico di questi dettagli.  Non sono più in possesso della 
documentazione ma mi sembra di ricordare (son passati quasi 20 anni 
ahime!) che i processori che equipaggiavano le macchine VAX della 
Digital avessero 30 registri e che il compilatore doveva generare le 
istruzioni per fare ciò che fa il firmware all'interno dei processori 
della famiglia x86.



devo contraddire Giovanni. Secondo lo Standard C, in generale non è
garantito che sia possibile fare cio' che hai scritto.
In particolare, lo standard dice che se si converte un puntatore ad un
tipo (per es.char) a puntatore a un tipo diverso (per es. int) SE il
valore del puntatore non è allineato correttamente per il tipo di
dato, si ha un comportamento indefinito (dunque il codice potrebbe non
funzionare come previsto).
Nota che è sufficiente anche solo effettuare la conversione, senza
necessariamente usare il puntatore per accedere all'oggetto puntato.
Come dice FtM, un caso speciale è void*. Un puntatore a void* può
essere convertito a qualunque altro tipo puntatore. Dunque tramite
void* si possono ottenere puntatori non allineati. Tuttavia se si usa
un puntatore non allineato per accedere in memoria, si ha un
comportamento indefinito.
Nota però che il significato di "allineato correttamente" dipende
dall'implementazione. Su alcune cpu è perfettamente possibile accedere
(ad. es.) a parole di 16 bit allocate in indirizzi dispari, in altre
no, e se è possibile la velocità di accesso può essere inferiore a
quella necessaria per leggere da un indirizzo pari. Nel casodi x86, a
cui fate riferimento, sembra che non ci siano problemi di allineamento
(anche se le prestazioni possono essere diverse).

 comportamento indefinito.
sbagliato: come infatti diceva FtM, lo standard garantisce che
convertendo da un puntatore a T in puntatore a void e poi convertendo
il risultato di nuovo in punttaore a T, si ha un valore che risulta
uguale.
Ma non è vero che convertire un puntatore a void in puntatore a T è
sempre consentito, in quanto il vincolo che il risultato della
conversione sia correttamente allineato a T è sempre in vigore.
Non a caso, per le funzioni di allocazione di memoria, il cui
risultato è appunto un puntatore a void che viene convertito in
puntatore a T, lo standard garantisce esplicitamente che la memoria
allocata sia correttamente allineate per ciascun possibile tipo.
faccio ammenda!

 (anche se le prestazioni possono essere diverse).
Ciao



Forse faresti meglio a studiare meglio il linguaggio.


 semplicemente per rendere più efficiente l'accesso alla memoria.
C99 sez 3.2  (definizione del termine "alignment")
3.2
1 alignment
requirement that objects of a particular type be located on storage
boundaries with
addresses that are particular multiples of a byte address
dopo di che, sez. 6.5.3.2 p4 e la annessa footnote 87 copre il caso di
accesso con puntatore non allineato e 6.3.2.3 par.7 copre il caso
della conversione tra puntatori, che come detto può essere indefinita
se si viola l'allineamento

 certo. Però se&var.str[3] non soddisfa i requisiti di allineamento

Nessuno dei punti che citi impone dei requisiti di allineamento alla 
memoria *fisica* del processore.  Impone solo che in certe situazione 
gli elementi di un certo tipo abbiano un allineamento multiplo della 
loro dimensione e senza relazione alla posizione fisica in memoria.
Ciò significa che un puntatore si un certo tipo deve indirizzare la 
base dell'oggetto e che l'incremento di un puntatore ad intero deve 
avvenire a step multipli della dimensione dell'intero, in modo tale 
che in un array gli elementi dello stesso tipo siano consecutivi.
Il paragrafo 6.5.3.2 al punto 4 dice che se applichi l'operatore '*' 
ad un puntatore invalido (non correttamente allineato al tipo di 
oggetto puntato) il risultato è indefinito non che il tipo deve avere 
un allineamento alla memoria fisica:
---------
4 The unary * operator denotes indirection. If the operand points to a 
function, the result is a function designator; if it points to an 
object, the result is an lvalue designating the object. If the operand 
has type ‘‘pointer to type’’, the result has type ‘‘type’’. If an 
invalid value has been assigned to the pointer, the behavior of the 
unary * operator is undefined (83).
--
83) Thus, &*E is equivalent to E (even if E is a null pointer), and 
&(E1[E2]) to ((E1)+(E2)). It is always true that if E is a function 
designator or an lvalue that is a valid operand of the unary & 
operator, *&E is a function designator or an lvalue equal to E.
If *P is an lvalue and T is the name of an object pointer type, *(T)P 
is an lvalue that has a type compatible with that to which T points. 
Among the invalid values for dereferencing a pointer by the unary * 
operator are a null pointer, an address inappropriately aligned for 
the type of object pointed to, and the address of an object after the 
end of its lifetime.
---------
Quanto alla conversione dei puntatori proprio il paragrafo 6.3.2.3 al
punto 7 conferma ciò che ho scritto:
----------
7 A pointer to an object or incomplete type may be converted to a
pointer to a different object or incomplete type. If the resulting
pointer is not correctly aligned (57) for the pointed-to type, the
behavior is undefined. Otherwise, when converted back again, the
result shall compare equal to the original pointer. When a pointer to
an object is converted to a pointer to a character type, the result
points to the lowest addressed byte of the object. Successive
increments of the result, up to the size of the object, yield pointers
to the remaining bytes of the object.
--
(57) In general, the concept ‘‘correctly aligned’’ is transitive: if a
pointer to type A is correctly aligned for a pointer to type B, which
in turn is correctly aligned for a pointer to type C, then a pointer
to type A is correctly aligned for a pointer to type C.
----------
IMO quest'ultimo paragrafo chiarisce il concetto di 'aligned', mentre 
il precedente dice che è *(T)P ritorna un valore del tipo a cui T 
punta.  Per cui *(int *)&str[3] ritorna un valore di tipo int ed è 
perfettamente valido indipendentemente dall'indirizzo fisico.
Dà un risultato indefinito solo se &str[3] non punta alla base di un 
oggetto di tipo int, non se l'oggetto non è allineato 'fisicamente' 
alla memoria.
Temo proprio che devi rivedere cosa si intende per 'alignement'.


 Temo proprio che devi rivedere cosa si intende per 'alignement'.
l'ho rivisto, è esattamente come ricordavo
Ti porto anche un evidenza sperimentale. Considera il seguente
programma:
/* Prova alignment */
#include <stdio.h>
int main(void) {
 unsigned char data[] = { 0x01, 0x02, 0x03 };
 short int i,j;
 i = * (short int *) &data[0];
 j = * (short int *) &data[1];
 i = i*j;
 printf("%d\n", i);
}
compilato con il SaS C su Amiga 2000. Risultato: Guru Meditation!
questo perchè il 68000 ha parole di 16 o 32 bit, ma effettuare un
accesso a 16 o 32 bit allocati ad un indirizzo dispari genera una
trap.
Rimuovendo l'accesso a data[1] tramite puntatore a short, il Guru
Meditation non c'è più.

   j = * (short int *)&data[1];
Quindi l'accesso, tramite cast, ad una qualsiasi locazione di memoria ha 
un risultato indefinito per lo standard C (magari con alcune coppie di 
compilatori/processori sì, ma non è detto) se il tipo del cast deve 
essere allineato.
Mi chiedo, allora, qual è il miglior modo per gestire i dati di un 
protocollo di comunicazione (TCP o altro) in cui, molto probabilmente, 
non sono allineati in memoria. Dovrei sempre lavorare di byte?
Immaginiamo di avere un pacchetto dati ricevuto:
   unsigned char data[PACKET_LENGTH];
e supponiamo che ci sia un intero senza segno a 32 bit Big Endian a 
partire dalla posizione 1. Devo per forza fare:
   uint32_t intero;
   intero = (data[1] << 24) + (data[2] << 16) + (data[3] << 8) + data[4];
invece che:
   intero = *(uint32_t *)data[1];
Naturalmente qui sto chiedendo qual è il codice che mi *garantisce* il 
risultato corretto indipendentemente dal compilatore e dal processore.
Mi sono perso quando parlate di passare a puntatore void. Per esempio, 
funzione
   uint32_t dummy(void *data) {
     return *(uint32_t *)data;
   }
ritorna sempre un risultato corretto? Oppure dipende dal puntatore che 
viene passato? Per esempio:
   unsigned char data[PACKET_LENGTH];
   uint32_t intero = dummy(&data[1]);
sicuramente funziona (ritornandomi l'intero a partire dalla posizione 1 
dell'array data[], ovviamente nell'endianess del processore, oppure no?

 dell'array data[], ovviamente nell'endianess del processore, oppure no?
no, è lo stesso discorso di prima. Sono io che, qualche post fa, ho
sbagliato asserendo che l'accesso tramite void* non risentiva di
problemi di allineamento. E' falso, assolutamente. Chiedo scusa
nuovamente.

 indirizzi che sono specifici multipli dell'indirizzo di un byte
Su una cosa sola concordo.  Che lo standard è scritto apposta per per 
avere interpretazioni contrapposte.
Del resto è stato scritto per accomodare esigenze diverse ed in modo 
tale che ognuno possa concludere come meglio gli aggrada.
Però l'esempio che riporti sull'Amiga è IMO una limitazione del 
compilatore usato che non espande correttamente le direttive.
Ho lavorato pochissimo con il 68000, ma guarda caso si trattva proprio 
di un ambiente dove si trattava di protocolli e non ricordo vi fossero 
i problemi che riporti.  O forse il vecchio standard non era così 
restrittivo.


 Io altre soluzioni universalmente portabili non ne conosco.
Quindi per ottenere quell'intero nel modo piïŋ― portabile possibile 
(indipendentemente dal processore e dal compilatore) dovrei fare per 
forza cosïŋ―:
---
   unsigned char data[PACKET_LENGTH];
   uint32_t intero;
   intero = (data[1] << 24) | (data[2] << 16) | (data[3] << 8) | data[4];
   intero = ntohl(intero);
---
dove (ispirandomi alle glibc):
---
#define __bswap_32(x) \
      ((((x) & 0xff000000u) >> 24) | (((x) & 0x00ff0000u) >>  8) | \
       (((x) & 0x0000ff00u) <<  8) | (((x) & 0x000000ffu) << 24))
uint32_t htonl (uint32_t x) {
#if BYTE_ORDER == BIG_ENDIAN
   return x;
#elif BYTE_ORDER == LITTLE_ENDIAN
   return __bswap_32 (x);
#endif
}
---
L'unica pecca di questa implementazione ïŋ― che, nel caso di dato 
allineato (o di processore che permette l'accesso non allineato in modo 
ugualmente performante), andrei a perdere tempo con lo shifting e la 
copia dei byte, quando sarebbe bastato un semplice cast. Per esempio, 
supponendo che l'intero sia in posizione 0, sarebbe bastato:
---
   unsigned char data[PACKET_LENGTH];
   uint32_t intero;
   intero = *(uint32_t *)&data[0];
   intero = ntohl(intero);
---
La ntohl(), se il processore fosse Big Endian, non farebbe nulla e, 
molto probabilmente, l'ottimizzatore non farebbe nessuna CALL.
Esiste una implementazione universalmente portabile che riesce a 
sfruttare, se ci sono, le potenzialitïŋ― del processore/compilatore per 
l'accesso non allineato, oppure si riduce al banale accesso a byte se 
proprio necessario?

 proprio necessario?
Il fatto di sfruttare o meno le potenzialità della cpu dipende sempre
dalla qualità del compilatore.

 restrittivo.
forse era una cpu 68020 o superiore, in cui non c'è la limitazione che
le parole siano allocate a indirizzi dispari.
Il compilatore SAS-C è un compilatore conforme al C89.

 ---
Ovviamente � sbagliato! Prima dell'ultima istruzione (con la chiamata 
alla ntohl), intero contiene gi� il numero corretto. Mediante gli shift 
e gli OR abbiamo gi� ordinato correttamente i byte da Big Endian 
all'endianess del processore.

Ora si che sono d'accordo.
Avevo già posto delle domande a tal riguardo senza aver risposte 
convincenti. Anch'io sono convinto che si possa parlare di padding solo 
in relazione a struct e union e che, conoscendo adeguatamente i 
puntatori, si possa accedere a qualsiasi locazione di memoria con 
qualsiasi puntatore a dati semplici, in sicurezza. Altrimenti i 'memory 
mapping' risulterebbero irrealizzabili. Grazie Giovanni. Mi hai reso la 
sicurezza ed un po' di fiducia in questi 'nuovi' compilatori ;-) di cui 
discutete.
Saluti.


Se non devi rendere codice portabile basta avere fiducia nelle
estensioni del proprio compilatore (e non cambiarlo/aggiornarlo mai).
Scelta secondo me opinabile, anche se (come diceva Ritchie, se non
sbaglio, riferendosi però in particolare alle ottimizzazioni) fare le
cose a mano invece che farle fare ad un compilatore elimina alla base
la necessità di utilizzarne uno. Come al solito dipende dai casi..
Ciao!