Newsgroup: it.comp.lang.c++
Titolo: allocatore

Saluti.
Siccome sul sistema in cui sto svilppando
non si puo' usare memoria dinamica sono
costretto a scrivermi un allocatore che
usa memoria allocata sullo stack.
Purtroppo non sono molto esperto di
questioni a basso livello (in particolare
circa l'alignment).
Attualmente ho una cosa del genere
(non proprio cosi' ma da l'idea):
template<class T> class Allocator
{
    private:
        T memory[20];
        int pos; // posizione nell'array
    public:
        T* create(const T& val)
        {
            return new(memory + pos) T(val);
        }
 
        destroy(T* p)
        {
            p->~T();
        }
}
Il problema e' che in questo modo e' necessario
che T abbia un costruttore di default.
Inoltre ci sono problemi nella distruzione 
(quando Allocator viene distrutto gli elementi 
di memory vengono di nuovo distrutti).
Per questo e' preferibile avere una cosa del genere:
template<class T> class Allocator
{
    private:
        char memory[20 * sizeof(T)];
        int pos; // posizione nell'array
    public:
        T* create(const T& val)
        {
            return (T*)new(memory + pos * sizeof(T)) T(val);
        }
 
        destroy(T* p)
        {
            p->~T();
        }
}
Il mio dubbio e' sulla questione dell'alignment.
E' corretto fare cosi'?
Grazie Manlio Perillo


Certo costruire un'allocatore ad hoc non e' la cosa piu' banale del mondo,
soprattutto se non si ha alla base un gestore di memoria piu' a basso
livello che gestisca questioni appunto come quelle dell' allineamento.
L'idea di un dislocatore che lavori sullo stack non e' male, pero' per
creare un meccanismo di allocazione efficiente sarebbe meglio confinare il
codice + di basso livello in una componente separata, un po come il
meccanismo degli slab utilizzato nell' allocatore di memoria dinamica nel
kernel di Linux, che a sua volta si basa su un allocatore + a basso livello.
Per quanto concerne la questione dell' allineamento, questo dovrebbe essere
appunto gestito da componenti specifiche  che possano in maniera efficiente
gestirne tutte le sfaccettature.
Se ti trovi su ambienti Unix, dovresti tenerti allineato alla dimensione del
page_frame onde evitare page_fault e rendere i processi che utilizzano
questo meccanismo di allocazione immuni da rescheduling indesiderati,  anche
se mi sembra di capire che sviluppi su sistemi embedded.
Per tornare al tuo esempio, supponendo una page size di 4096 byte, potresti
procedere cosi':
#define    CHUNK_SIZE    (4096)
#define    CHUNK_NUMBER    (100)
#define    PAGE_ALIGN    (0xffffffff << 12)
char mem[CHUNK_SIZE * CHUNK_NUMBER];
char *align_mem = (char*)(((int)mem & PAGE_ALIGNED) + CHUNK_SIZE);
.....
.....
Ivan

 E' corretto fare cosi'?
In generale, no. Non credo che esista un metodo portabile e
perfettamente sicuro per allocare sullo stack un'area di memoria non
inizializzata allineata correttamente per contenere un oggetto di un
dato tipo. La tecnica usata comunemente e' quella di costruire una
union con tutti i tipi di dati nativi, n modo da avere la ragionevole
certezza che l'allineamento sia corretto anche per un tipo definito
dall'utente (comunque la rigiri il primo membro dato non puo' che
essere di un tipo nativo, no?).
L'alternativa e' verificare come funziona l'allineamento sulla tua
piattaforma ed adeguarti a quella specifica.
Ciao,
Nicola

 gestirne tutte le sfaccettature.
Il problema e' che lavorando sullo stack il compilatore non gli
fornisce alcuna garanzia sull'allineamento di oggetti generici (array
di char, per intenderci).
Scendendo di livello come suggerisci tu si rinuncia all'unica fonte
portabile di informazione sull'allineamento richiesto, ovvero il tipo
dell'oggetto da allocare, e ci si infogna in codice che per forza di
cose e' totalmente dipendente dalla piattaforma. Se non sta scrivendo
un sistema operativo, a mio avviso Manlio fa meglio a cercare di
mantenere il livello che sta cercando di usare il piu' a lungo
possibile.
Ciao,
Nicola

 
Non e' molto semplice ma forse riesco a tirar fuori qualcosa.
Grazie  Manlio Perillo

 .....
Provo a vedere se posso fare una cosa del genere nel mio caso.
Grazie Manlio Perillo

 possibile.
un approccio simile, a cui ci si potrebbe rifare e' quello proposto da 
Herb Sutter in exceptional c++, tema 30, punto 3
in pratica usa dei fixed allocator, template sulla dimensione degli 
oggetti da allocare. gli allocator sono istanziati come singleton. 
destinando ogni istanza a gestire un determinato range di pagine della 
memoria, lavorando solo con una specifica dimensione, si potrebbe 
realizzare qualcosa di simile a quanto richiesto. il problema e' che 
istanziare i singleton richiede tempo, quindi se il sistema embedded e' 
time critical, occore una fase di inizializzazione in cui si creeranno 
tutti quelli necessari. inoltre, si occupano piu' pagine di memoria che 
con un approccio alla cieca

 Mi sembra una soluzione ragionavole.
Tra parentesi se non sbaglio la libreria type_traits di Boost
(
www.boost.org
) dovrebbe contenere il template type_with_alignment, o
quualcosa del genere.
Ciao,
Nicola


Ho visto del codice per quella piattaforma e fa come nel mio esempio
precedente.
L'unica differenza e' che quando avanza alla posizione successiva fa:
pos += sizeof(T);
pos = (pos + 1) & 0xFFFFFFFE;
perche' (commenta l'autore) in questo modo si parte
sempre da un indirizzoa pari.
Ha un qualche senso? Io non capisco.
Tornando al problema in generale, mi chiedevo se e' corretto
fare una cosa del genere
template<class T> class Allocator
{
    private:
        struct TBuf
        {
            char space[sizeof(T)];
        }
        TBuf memory[20];
    // ...
};
Infatti (ma non vorrei sbagliare) le strutture dovrebbero
avere il corretto allineamento e cio' dovrebbe garantire
che la memoria allocata sia allineata correttamente.
Comunque, dato che non mi e' molto chiaro il concetto di
alignment, mi sarebbe utile qualche reference che tratti
l'argomento.
Saluti e grazie  Manlio Perillo

 essere di un tipo nativo, no?).
pensando a tutt'altro, mi e' tornato in mente raw_storage_iterator... 
non so se si possa usare in questo caso, in quanto lo conosco solo per 
"sentito dire" e non ho mai spulciato a fondo le sue caratteristiche. 
Che ne pensa il vasto mondo?

 piattaforma ed adeguarti a quella specifica.
pensando a tutt'altro, mi e' tornato in mente raw_storage_iterator. 
Credete sia possibile usarlo per implementare cio' che si richiedeva?
Qualcosa del tipo
static const int mem_size = 4096;
#include <memory>
template<class T> class Allocator {
    private:
        typedef std::raw_storage_iterator<T*, T> iterator;
        T memory[mem_size];
        Iterator pos;
    public:
        Allocator () : pos(memory) {};
        T* create(const T& val) throw() {
            T* res = pos(val);
            ++pos;
            return res;
        }
 
        destroy(T* p) {
            p->~T();
        }
}
credo che in questo modo si evitino i problemi di allineamento, per la 
semantica dell'operatore ++. O sbaglio? Comunque mancano la gestione 
della dimensione della memoria e delle eccezioni

         }

"Nicola Musatti" <Nicola....@ObjectWay.it> ha scritto nel messaggio
news:a327cf48.02121...@posting.google.com...

Quello che dici e' quello che mi sto proponendo di fare.
Un sistema semplice e soprattutto portabile.
Infatti il programma, oltre a girare sul sistema
embedded, deve girare anche su Windows 2000
(su cui lavoro io) e su Linux (su cui faccio
dei test addizionali).
Grazie  Manlio Perillo

 oggetti da allocare.
Qualcosa di simile a quanto ho scritto nell'ultimo messaggio?
Grazie  Manlio Perillo

"Paolo Podda" <p.p...@tiscaliNOSPAM.it> ha scritto nel messaggio
news:1285164.k...@news.iol.it...

L'idea di allocare un array tipo
T memory[mem_size]
e' quella che uso attualmente.
I problemi sono essenzialmente due:
- per T e' richiesto il costruttore di default.
  Nel mio programma e' possibile ma mi obbliga a
  'forzare' delle cose.
- Quando Allocator viene distrutto, vengono invocati
  di nuovo i distruttori delle instanze in memory.
  Anche questo nel mio programma non e' un grosso
  problema (dato che in pratica non termina mai).


 Qualcosa di simile a quanto ho scritto nell'ultimo messaggio?
ummm, quale?

   problema (dato che in pratica non termina mai).
Nella mia impl, non credo, visto che semplicemente non ci si preoccupa 
dei puntatori, ma si fanno delle copie di valori in memoria non 
inizializzata, che poi viene distrutta come mem sullo stack
a meno che non mi sfugga qualcosa

 a meno che non mi sfugga qualcosa
una cosa che manca, e' ovviamente riportare indietro il puntatore ad una 
cancellazione, e nello spostamento in avanti, saltare nei vari buchi 
rimasti

a meno che non mi sfugga qualcosa
Tu dichiari una struttura che contiene un array di T
e altra roba (quell'iterator). Perche' l'array non
dovrebbe essere costruito (e di conseguenza richiedere
un costruttore di default per gli oggetti contenuti) ?
Perche' in uscita non dovrebbe essere distrutto ?
Quello che fai e' di costruire un oggetto su un altro
oggetto che risulta ancora "vivo" e di distruggere un
oggetto che poi verra' distrutto nuovamente.
L'iteratore di raw storage e' pensato per lavorare
appunto su aree di memoria, non su oggetti "vivi"
come invece lo usi tu.
Andrea

 Perche' in uscita non dovrebbe essere distrutto ?
uhm, vero. e' che ho preso pari pari il codice postato, e non ci avevo 
riflettuto
direi che allora si puo' risolvere con cast e puntatore a char
template<class T> class Allocator {
  private:
    typedef std::raw_storage_iterator<T*, T> Iterator;
    Iterator pos;
    char memory[mem_size];
    int size;
  public:
    Allocator () : pos(reinterpret_cast<T *>(memory)) {
    /* credo che serva per la gestione dell'array, che manca */ 
      size = mem_size / (sizeof(T) / sizeof(char)); 
    };
 
   T* create(const T& val) throw() {
   /* versione semplice, manca la gestione 
      di buchi nell'array e di array pieno*/
      T* res = pos;
      *pos++ = val;
      return res; 
   }
...
};        
dovrebbe sempre mantenere l'allineamento, giusto?

"Nicola Musatti" <Nicola....@ObjectWay.it> ha scritto nel messaggio
news:a327cf48.02121...@posting.google.com...

Per caso, leggendo uno dei tanti header di Windows ho visto che
per calcolare l'alignment di un tipo fa (ad esempio)
template<class T> int align_of()
{
    struct align_helper
    {
        char x;
        T test;
    };
    return (int)&((align_helper)0)->test);
}
Ha un minimo di portabilita'?
Comunque daro' una occhiata alla libreria type_traits.
Grazie  Manlio Perillo

 Ha un minimo di portabilita'?
In generale no, ma mi aspetto che funzioni su tutti i sistemi intel (ad es. Linux).
Ciao,
Nicola

 l'argomento.
Purtroppo non saprei cosa indicarti.
Ciao,
Nicola

 dovrebbe sempre mantenere l'allineamento, giusto?
No, perche' raw_storage_iterator non aggiusta la posizione alla quale
viene inizializzato. L'unica operazione "particolare" che compie e'
utilizzare construct() per inizializzare un oggetto nell'espressione
*iter = ...
Per il resto delega all'iteratore sottostante, presumibilmente un
puntatore.
Ciao,
Nicola


Temo di aver detto una scemenza.
Ancora non mi e' completamente chiaro il concetto
ma forse qualcosa la sto cominciando a capire.
Per prima cosa ecco un template per calcolare l'alignment
(segue la stessa implementazione usata in BOOST):
template<typename T> struct alignof
{
  struct helper
  {
    char padding;
    T object;
  };
  static const unsigned diff = sizeof(helper) - sizeof(T);
  static const unsigned value = (diff < sizeof(T)) ? diff : sizeof(T);
};
Spero solo che sia portabile.
Allora, supponendo che nel mio allocatore:
    template<typename T> class Allocator;
sia alignof<T>::value == 1, non ci sono problemi nel
fare
    char memory[sizeof(T) * n];
vero?
Inoltre, andando nel dettaglio della mia piattaforma,
e' corretto fare:
    struct TBuf
    {
        // per assicurare che l'indirizzo di partenza sia pari
        static const unsigned even_size = (sizeof(T) + 1) & 0xfffffffe;
        char space[even_size];
    };
    TBuf memory[n];
?


 puntatore.
scusami, forse parliamo di cose differenti: anche ricorrendo 
all'aritmetica dei puntatori, si dovrebbe mantenere l'allineamento, se 
opero su di un T*, visto che l'iteratore e' inizializzato sul tipo T

     TBuf memory[n];
Mi aspetto di si, ma non sono sicuro che sia garantito ovunque.
Ciao,
Nicola

...

Il costruttore di raw_storage_iterator prende come argomento un output
iterator per il quale l'espressione &*iter deve costituire un
puntatore valido a T.
La conversione che effettui nel tuo esempio applicando
reinterpret_cast<T *> all'indirizzo dell'array non e' affatto
garantita ritornare un puntatore valido.
Ciao,
Nicola


Che cosa potrebbe non funzionare?
Il fatto che sizeof(TBuf) !== even_size oppure che even_size non e' pari?
Grazie  Manlio Perillo

 garantita ritornare un puntatore valido.
l'unico guaio che prevedo e' se il reinterpret_cast fallisse, ma non ne 
vedo il motivo: e' fatto apposta per delle "porcherie" del genere :) 
infatti 
5.2.10.7
A pointer to an object can be explicitly converted to a pointer to an 
object of different type.*
[Footnote: The types may have different cv-qualifiers, subject to the 
overall restriction that a reinterpret_cast cannot cast away constness. 
--- end foonote] 
mi sembra che la cosa sia permessa esplicitamente, o sbaglio? Non mi 
pare di trovarci nel caso in cui un T[] sia differente da un T*
Certo testare il risultato del casta e' bene, a prescindere

Il fatto che sizeof(TBuf) !== even_size oppure che even_size non e' pari?
Il problema e' che TBuf potrebbe essere allocato ad un indirizzo
che non rispetta l'allinamento del tipo per cui lo vuoi usare.
Quello che viene garantito sempre e' che gli indirizzi tornati
da malloc sono validi per qualunque tipo... ma per gli oggetti
allocati su stack o su memoria statica questa garanzia manca.
HTH
Andrea

infatti 
Non e' che il cast fallisce... ma l'indirizzo che ottieni potrebbe
non essere utilizzabile per puntare ad un oggetto di tipo T.
Nella libreria standard queste cose vengono fatte solo con buffer
ottenuti da malloc, operator new o similia; queste funzioni hanno
scritto sul loro contratto che devono restituire indirizzi validi
per *qualunque* tipo di oggetto.
Questa comoda garanzia con aree allocate su stack o in memoria
statica non c'e'. Questo e' il nocciolo del problema.
HTH
Andrea

 --- end foonote]
quel che dice il resto non credo ci interessi, in quanto parla di 
riconversione del puntatore al tipo originale, a cui impone vincoli, 
anche di allineamento. invece, dopo l'allocazione, il nostro puntatore 
viene sempre visto e usato come un T*

 statica non c'e'. Questo e' il nocciolo del problema.
rileggendo meglio mi accorgo della specifica su tale conversione per cui 
il risultato non e' specificato.
forse con un'ulteriore porcheria si potrebbe venirne a capo, ma sarebbe 
veramente mooolto sporca: una cosa del tipo
template<class T> class Allocator {
  private:
    typedef std::raw_storage_iterator<T*, T> Iterator;
    Iterator pos;
    struct memory_{char x_[mem_size];} memory;
    int size;
  public:
    Allocator () : pos(reinterpret_cast<T *>(memory)) {
pero' diffido chiunque da usare codice del genere, e se vi chiedono se 
l'ho scritto io, dite di no

 Il fatto che sizeof(TBuf) !== even_size oppure che even_size non e' pari?
Il problema e' che non ho sufficiente dimestichezza con questi
argomenti da sentirmi sicuro delle mie affermazioni.
Ciao,
Nicola


Certo!



Nel mio caso l'oggetto che devo allocare e' sempre una struttura.
Per questa struttura ho inoltre alignof<T>::value == 1;


 Mi resta da vedere se il g++ ha una opzione appropriata.
lo fai sul codice stesso:
char memory[20] __attribute__ ((aligned (4));
allinea memory a 4 byte

Quello che cambia e' anche la sizeof della struttura.
In C e C++ viene garantito che il sizeof di un array
e' esattamente la dimensione dell'array moltiplicata
per il sizeof dell'elemento.
Questo e' il motivo per cui e' possibile che in una
struttura sia presente del padding anche alla fine
della stuttura oltre che fra un membro e l'altro.
In VC++ e' permesso modificare liberamente il packing
perche' i processori intel hanno solo problemi di
prestazioni quando si accede a dati non allineati.
Ci sono processori (caso tipico sono i RISC) in cui
invece non rispettare l'allineamento naturale per il
tipo non e' solo sconveniente... ma assolutamente
impossibile.
Nota anche che ci sono o almeno c'erano compilatori
per intel che non prevedono il parametro di packing
per le strutture (una volta anche g++ non aveva
questa possibilita'... ora non so).
Andrea

l'ho scritto io, dite di no
E perche' qualcosa di simile dovrebbe funzionare ?
La struttura memory e' fatta di char e non ha nulla
a che vedere con il tipo T. Perche' il compilatore
dovrebbe garantirti per quell'array l'allineamento
richiesto per il tipo T ?
Andrea

 richiesto per il tipo T ?
perche' una struct siffatta dovrebbe avere, almeno su tutte le 
architetture di mia conoscenza, regole di allineamento pari o superiori 
a qualunque altra struttura di dati. Ma proprio perche' nessuno te lo 
garantisce, ho aggiunto quelle due righe alla fine, e un forse


Almeno nella versione 3.2 (di cui ho appena scaricato
il manuale) e' presente.


"Paolo Podda" <p.p...@tiscaliNOSPAM.it> ha scritto nel messaggio
news:1540366.a...@news.iol.it...

Anche il Visual C++ ha una opzione simile.
Puo' essere una soluzione.
Mi devo documentare meglio.


 Spero che non si siano problemi.
Sparc. Purtroppo ho perso il riferimento, ma ho letto da poco un post
da qualche parte proprio a proposito di problemi di allineamento su
Sparc. Puoi provare a vedere se Boost contiene codice specifico.
Ciao,
Nicola

 Puoi provare a vedere se Boost contiene codice specifico.
Ho visto che in BOOST e' presente un template
    type_with_alignment
Sto cercando di capire come funziona.
Non mi sembra ci sia qualcosa di specifico per Sparc.
Comunque credo che essenzialmente usi una union come mi avevi
consigliato.
Ad esempio per allineare correttamente un array per qualsiasi tipo:
class alignment_dummy;
typedef void (*function_ptr)();
typedef int (alignment_dummy::*member_ptr);
typedef int (alignment_dummy::*member_function_ptr)();
union
{
    char c;
    short s;
    int i;
    long l;
    float f;
    double d;
    function_ptr fp;
    member_ptr mp;
    member_function_ptr mfp;
    char memory[20];
};
Comunque per la workstation Sun non dovrebbero esserci problemi dato
che il gcc ha una keyword per allineare correttamente un tipo
(cosi' come il VCC).
Purtroppo il compilatore embedded non prevede keyword specifiche, quindi
credo che usero' la union (anche se nel programma originale a cui sto
lavorando non faceva nulla del genere, semplicemente si assicurava che
l'indirizzo fosse pari).
Grazie e auguri di Buon Natale   Manlio Perillo

 l'indirizzo fosse pari).
forse conviene fare cosě anche a te... faccio l'avvocato del diavolo:
se ti assicuri che l'indirizzo sia pari o, ancora meglio, un multiplo
di 4, dovresti essere ragionevolmente sicuro che funzioni su un
mucchio di piattaforme, per il resto credo tu ti complichi la vita
eccessivamente! ;-)


Il problema e' questo! Perche' si assicurava solo che l'indirizzo fosse
pari e non multiplo di 4?
Perche' prevedeva la possibilita' che l'indirizzo non fosse pari?
Questo puo' accadere solo(?) se si alloca un char (ma non e' il mio
caso) o se le strutture solo 'impacchettate' (e' una cosa che
devo ancora verificare).
Purtroppo il codice non e' commentato bene e non si capisce la cosa.
Io per sicurezza preferisco fare come ho detto (basta definire delle
semplici macro).