Gestione della memoria C per VM multipiattaforma

StackOverflow https://stackoverflow.com/questions/1616147

Domanda

Ho fatto una domanda sulle dimensioni del tipo C alla quale ottengo una risposta abbastanza buona, ma mi sono reso conto che potrei non formulare la domanda molto bene per essere utile per il mio scopo.

Il mio background è stato dall'Ingegnere Informatico prima di passare all'Ingegnere del Software, quindi mi piacciono le architetture dei computer e penso sempre a fare VM. Ho appena terminato un progetto interessante che rende VM su Java di cui sono abbastanza orgoglioso. Ma ci sono alcuni problemi legali che non riesco ad open-source ora e al momento ho del tempo libero. Quindi voglio vedere se riesco a creare un'altra VM su C (con una velocità migliore) solo per divertimento ed educazione.

Il fatto è che non sono un programma C l'ultima volta che ho scritto un problema C non banale è stato più di 10 anni fa. Ero Pascal, Delphi e ora programmatore Java e PHP.

Esistono numerosi ostacoli che posso prevedere e sto cercando di affrontarne uno e che sta accedendo alla libreria esistente (in Java, la riflessione risolve questo problema).

Ho intenzione di risolverlo avendo un buffer di dati (simile allo stack). Il client della mia VM può programmare per inserire i dati in questi stack prima di darmi il puntatore alla funzione nativa. 

int main(void) {
    // Prepare stack
    int   aStackSize = 1024*4;
    char *aStackData = malloc(aStackSize);

    // Initialise stack
    VMStack aStack;
    VMStack_Initialize(&aStack, (char *)aStackData, aStackSize);

    // Push in the parameters
    char *Params = VMStack_CurrentPointer(&aStack);
    VMStack_Push_int   (&aStack, 10  ); // Push an int
    VMStack_Push_double(&aStack, 15.3); // Push a double

    // Prepare space for the expected return
    char *Result = VMStack_CurrentPointer(&aStack);
    VMStack_Push_double(&aStack, 0.0); // Push an empty double for result

    // Execute
    void (*NativeFunction)(char*, char*) = &Plus;
    NativeFunction(Params, Result); // Call the function

    // Show the result
    double ResultValue = VMStack_Pull_double(&aStack); // Get the result
    printf("Result:  %5.2f\n", ResultValue);               // Print the result

    // Remove the previous parameters
    VMStack_Pull_double(&aStack); // Pull to clear space of the parameter
    VMStack_Pull_int   (&aStack); // Pull to clear space of the parameter

    // Just to be sure, print out the pointer and see if it is `0`
    printf("Pointer: %d\n", aStack.Pointer);

    free(aStackData);
    return EXIT_SUCCESS;
}

Il push, pull e il richiamo della funzione nativa possono essere innescati da un codice byte (in questo modo la VM verrà successivamente creata).

Per completezza (in modo che tu possa provarlo sul tuo computer), ecco il codice per Stack: 

typedef struct {
    int  Pointer;
    int  Size;
    char *Data;
} VMStack;

inline void   VMStack_Initialize(VMStack *pStack, char *pData, int pSize) __attribute__((always_inline));
inline char   *VMStack_CurrentPointer(VMStack *pStack)                    __attribute__((always_inline));
inline void   VMStack_Push_int(VMStack *pStack, int pData)                __attribute__((always_inline));
inline void   VMStack_Push_double(VMStack *pStack, double pData)          __attribute__((always_inline));
inline int    VMStack_Pull_int(VMStack *pStack)                           __attribute__((always_inline));
inline double VMStack_Pull_double(VMStack *pStack)                        __attribute__((always_inline));

inline void VMStack_Initialize(VMStack *pStack, char *pData, int pSize) {
    pStack->Pointer = 0;
    pStack->Data    = pData;
    pStack->Size    = pSize;
}

inline char *VMStack_CurrentPointer(VMStack *pStack) {
    return (char *)(pStack->Pointer + pStack->Data);
}

inline void VMStack_Push_int(VMStack *pStack, int pData) {
    *(int *)(pStack->Data + pStack->Pointer) = pData;
    pStack->Pointer += sizeof pData; // Should check the overflow
}
inline void VMStack_Push_double(VMStack *pStack, double pData) {
    *(double *)(pStack->Data + pStack->Pointer) = pData;
    pStack->Pointer += sizeof pData; // Should check the overflow
}

inline int VMStack_Pull_int(VMStack *pStack) {
    pStack->Pointer -= sizeof(int);// Should check the underflow
    return *((int *)(pStack->Data + pStack->Pointer));
}
inline double VMStack_Pull_double(VMStack *pStack) {
    pStack->Pointer -= sizeof(double);// Should check the underflow
    return *((double *)(pStack->Data + pStack->Pointer));
}

Per quanto riguarda la funzione nativa, ho creato quanto segue a scopo di test: 

// These two structures are there so that Plus will not need to access its parameter using
//    arithmetic-pointer operation (to reduce mistake and hopefully for better speed).
typedef struct {
    int    A;
    double B;
} Data;
typedef struct {
    double D;
} DDouble;



// Here is a helper function for displaying
void PrintData(Data *pData, DDouble *pResult) {
    printf("%5.2f + %5.2f = %5.2f\n", pData->A*1.0, pData->B, pResult->D);
}



// Some native function
void Plus(char* pParams, char* pResult) {
    Data    *D  = (Data    *)pParams; // Access data without arithmetic-pointer operation
    DDouble *DD = (DDouble *)pResult; // Same for return
    DD->D = D->A + D->B;
    PrintData(D, DD);
}

Quando eseguito, il codice sopra riportato restituisce: 

10.00 + 15.30 = 25.30
Result:  25.30
Pointer: 0

Funziona bene sulla mia macchina (Linux x86 32 bit GCC-C99). Sarà molto bello se questo funziona anche su altri sistemi operativi / architettura. Ma ci sono almeno tre problemi relativi alla memoria di cui dobbiamo essere a conoscenza.

1). Dimensione dei dati: sembra che se compili sia VM che funzioni native usando lo stesso compilatore sulla stessa architettura, i tipi di dimensione dovrebbero essere gli stessi.

2). Endianness - Lo stesso vale per la dimensione dei dati.

3). Allineamento della memoria - Qual è il problema poiché i byte di riempimento possono essere aggiunti in struct ma è difficile sincronizzarlo quando si prepara lo stack di parametri come (non c'è modo di sapere come viene aggiunto il riempimento tranne per la codifica effettiva).

Le mie domande sono:

1). Se conosco la dimensione dei tipi, c'è un modo per modificare la funzione push and pull per sincronizzarsi esattamente con il padding strutt? (modifica per consentire al compilatore di occuparsene come problemi di Datasize e Endians).

2). Se impacco la struttura per uno (usando #pragma pack(1)); (2.1) La penalità di prestazione sarà accettabile? e (2.2) la stabilità del programma sarà a rischio?

3). Che ne dite di imbottitura di 2,4 o 8? Quale dovrebbe essere buono per il sistema generale a 32 o 64 bit?

4). Potete guidarmi a una documentazione per un algoritmo di padding esatto, diciamo per GCC su x86?

5). C'è un modo migliore?

NOTA: multipiattaforma non è il mio obiettivo finale ma non posso resistere. Inoltre, le prestazioni non sono il mio obiettivo non appena non sono così brutte. Tutti questi sono per divertimento e apprendimento.

Ci scusiamo per il mio inglese e il post molto lungo.

Grazie a tutti in anticipo.

È stato utile?

Soluzione

Commenti tangenziali

Questi primi elementi sono tangenziali alle domande che hai posto, ma ... 

// Execute
void (*NativeFunction)(char*, char*) = &Plus;
NativeFunction(Params, Result); // Call the function

Penso che dovresti probabilmente usare 'void *' invece di 'char *' qui. Vorrei anche un typedef per il tipo di puntatore a funzione: 

typedef void (*Operator)(void *params, void *result);

Quindi puoi scrivere: 

Operator NativeFunction = Plus;

Anche la funzione attuale verrebbe modificata, ma solo leggermente: 

void Plus(void *pParams, void *pResult)

Inoltre, hai un piccolo problema di denominazione: questa funzione è 'IntPlusDoubleGivesDouble ()', piuttosto che una funzione generale 'aggiungi due tipi'.

Risposte dirette alle domande

  

1). Se conosco la dimensione dei tipi, c'è un modo per modificare la funzione push and pull per sincronizzarsi esattamente con il padding strutt? (modifica per consentire al compilatore di occuparsene come problemi di Datasize e Endians).

Non esiste un modo semplice per farlo. Ad esempio, considera: 

struct Type1
{
     unsigned char byte;
     int           number;
};
struct Type2
{
     unsigned char byte;
     double        number;
};

Su alcune architetture (SPARC a 32 o 64 bit, ad esempio), la struttura Type1 avrà "numero" allineato a un limite di 4 byte, ma la struttura Type2 avrà "numero" allineato su un 8- limite di byte (e potrebbe avere un "long double" su un limite di 16 byte). La tua strategia di "push individual elements" imposterebbe il puntatore dello stack di 1 dopo aver spinto il valore "byte" - quindi ti consigliamo di spostare il puntatore dello stack di 3 o 7 prima di premere il "numero", se il puntatore dello stack non è già appropriatamente allineati. Parte della descrizione della tua VM saranno gli allineamenti richiesti per un dato tipo; il codice push corrispondente dovrà garantire il corretto allineamento prima di premere.

  

2). Se impacco la struttura per uno (usando #pragma pack (1)); (2.1) La penalità di prestazione sarà accettabile? e (2.2) la stabilità del programma sarà a rischio?

Su macchine x86 e x86_64, se comprimete i dati, incorrerete in una penalità prestazionale per l'accesso ai dati non allineato. Su macchine come SPARC o PowerPC (per mecki ), otterrai un errore del bus o qualcosa di simile invece: è necessario accedere ai dati al suo corretto allineamento. Potresti risparmiare un po 'di spazio di memoria, a un costo in termini di prestazioni. Faresti meglio a garantire le prestazioni (che qui includono "prestazioni corrette invece di crash") al costo marginale nello spazio.

  

3). Che ne dite di imbottitura di 2,4 o 8? Quale dovrebbe essere buono per il sistema generale a 32 o 64 bit?

Su SPARC, è necessario collegare un tipo base N-byte a un limite N-byte. Su x86, otterrai le migliori prestazioni se fai lo stesso.

  

4). Potete guidarmi a una documentazione per un algoritmo di padding esatto diciamo per GCC su x86?

Dovresti leggere il manuale .

  

5). C'è un modo migliore?

Nota che il trucco 'Tipo1' con un singolo carattere seguito da un tipo ti dà il requisito di allineamento - possibilmente usando la macro 'offsetof ()' da <stddef.h>: 

offsetof(struct Type1, number)

Beh, non impacchetterei i dati nello stack - Lavorerei con l'allineamento nativo perché è impostato per fornire le migliori prestazioni. Lo scrittore del compilatore non aggiunge pigramente un riempimento a una struttura; lo mettono lì perché funziona "meglio" per l'architettura. Se decidi di conoscerlo meglio, puoi aspettarti le consuete conseguenze: programmi più lenti che a volte falliscono e non sono così portatili.

Inoltre, non sono convinto che scriverei il codice nelle funzioni dell'operatore per supporre che lo stack contenesse una struttura. Vorrei estrarre i valori dallo stack tramite l'argomento Params, sapendo quali erano gli offset e i tipi corretti. Se avessi spinto un numero intero e un doppio, avrei tirato un numero intero e un doppio (o, forse, in ordine inverso - avrei tirato un doppio e un int). A meno che non si stia pianificando una macchina virtuale insolita, poche funzionis avrà molti argomenti.

Altri suggerimenti

Post interessante e dimostra che hai lavorato molto. Quasi il post SO ideale.

Non ho risposte pronte, quindi per favore abbi pazienza. Dovrò fare qualche altra domanda: P

  

1). Se conosco la dimensione dei tipi, c'è un modo per modificare la funzione push and pull per sincronizzarsi esattamente con il padding strutt? (modifica per consentire al compilatore di occuparsene come problemi di Datasize e Endians).

È solo dal punto di vista delle prestazioni? Stai pensando di introdurre puntatori insieme a tipi aritmetici nativi?

  

2). Se impacco la struttura per uno (usando #pragma pack (1)); (2.1) La penalità di prestazione sarà accettabile? e (2.2) la stabilità del programma sarà a rischio?

Questa è una cosa definita dall'implementazione. Non qualcosa su cui puoi contare su più piattaforme.

  

3). Che ne dite di imbottitura di 2,4 o 8? Quale dovrebbe essere buono per il sistema generale a 32 o 64 bit?

Il valore che corrisponde alla dimensione della parola nativa dovrebbe offrire prestazioni ottimali.

  

4). Potete guidarmi a una documentazione per un algoritmo di padding esatto, diciamo per GCC su x86?

Non conosco la parte superiore della mia testa. Ma ho visto il codice simile a questo in uso.

Nota che puoi specifica gli attributi delle variabili usando GCC (che ha anche qualcosa chiamato default_struct __attribute__((packed)) che disattiva il riempimento).

Ci sono alcune ottime domande qui, molte di esse si aggrovigliano in alcuni importanti problemi di progettazione, ma per la maggior parte di noi - possiamo vedere a cosa stai lavorando (diretto appena pubblicato mentre scrivo, così puoi vedere che stai generando interesse) possiamo capire il tuo inglese abbastanza bene che ciò su cui stai lavorando sono alcuni problemi del compilatore e alcuni problemi di progettazione della lingua - diventa difficile risolvere la domanda ma in quanto stai già lavorando in JNI c'è speranza ...

Per prima cosa, proverei ad allontanarmi da pragmi; Molte persone, moltissime non saranno d'accordo. Per una discussione canonica sul perché vedere la giustificazione della posizione in lingua D sulla questione. Per un altro, c'è un puntatore a 16 bit sepolto nel codice.

I problemi sono quasi infiniti, ben studiati e probabilmente ci faranno seppellire in opposizione e intransigenza intramurale. se posso suggerire di leggere la la Home Page di Kenneth Louden e il manuale di architettura Intel. Ce l'ho, ho provato a leggerlo. L'allineamento della struttura dei dati, insieme a molte altre questioni che si mettono in discussione, sono profondamente sepolti nella scienza del compilatore storico e rischiano di farti stupire da chissà cosa. (gergo o idiomatico per conseguenze imprevedibili di conseguenza)

Detto questo, ecco qui:

  1. Dimensioni tipo C Che tipo di dimensioni?
  2. Ingegnere informatico prima di passare a Software Engineer Hai mai studiato i microcontrollori? Dai un'occhiata ad alcune delle opere di Don Lancaster.
  3. Pascal, Delphi e ora Java e PHP programmatore. Questi vengono relativamente rimossi dall'architettura di base dei processori, anche se molte persone mostreranno o proveranno a mostrare come possono essere usati per scrivere routine potenti e fondamentali. Suggerisco di guardare il parser ricorsivo di discesa di David Eck per vedere esattamente come iniziare a studiare la questione. Inoltre, Kenneth Louden ha un'implementazione di & Quot; Tiny & Quot; che è un vero compilatore. Ho scoperto qualcosa non molto tempo fa che penso sia stato chiamato asm dot org ... lavoro molto avanzato e molto potente era disponibile per lo studio lì, ma è molto lungo iniziare a scrivere in assemblatore con l'intenzione di entrare nella scienza del compilatore. Inoltre, la maggior parte delle architetture presenta differenze non coerenti tra un processore e l'altro.
  4. accesso alla libreria esistente

Ci sono molte librerie in giro, Java ne ha alcune buone. Non so degli altri. Un approccio è quello di provare a scrivere una lib. Java ha una buona base e lascia spazio a persone a cui piace provare a trovare qualcosa di meglio. Inizia con il miglioramento di Knuth-Morris-Pratt o qualcosa del genere: non mancano solo i posti dove iniziare. Prova Directory degli algoritmi di programmazione per computer e, sicuramente, guarda Dizionario di algoritmi e strutture dati su NIST

  1. always_inline

Non necessariamente, vedi Dov Bulka - il lavoratore ha conseguito un dottorato in CS e anche un autore competente in aree in cui l'efficienza nel tempo / la robustezza dell'affidabilità e così via non sono soggette ad alcune delle quotazioni &; & modello quot; paradigma dal quale ricaviamo un po 'del " Oh! non importa " su questioni che contano davvero.

Come nota di chiusura, la strumentazione e il controllo rappresentano oltre il 60% del mercato effettivo delle capacità di programmazione raggiunte come descritto. Per qualche motivo, abbiamo sentito parlare principalmente del modello di business. Lasciami condividere con te e dentro tidbit che ho da una fonte affidabile. Dal 10% al 60% o più i rischi reali per la sicurezza e la proprietà derivano da questioni veicolari che derivano da furti, furti e similiing. Non sentirai mai appelli per & Quot; 90 giorni di minerali bustin presso il centro di estrazione mineraria della contea! & Quot; per i biglietti del traffico, infatti la maggior parte delle persone non si rende nemmeno conto che le citazioni sul traffico sono (N.A. - U.S.A.) reati di classe 4 e sono effettivamente classificabili come tali.

Mi sembra che tu abbia fatto un buon passo verso un buon lavoro, ...

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top