Che cos'è un buon allocatore di memoria C per sistemi embedded? [chiuso]

Question

Ho una singola applicazione threaded integrata che alloca e dealloca un sacco di piccoli blocchi (32-64b). Lo scenario perfetto per un allocatore basato su cache. E anche se potrei PROVARE a scriverne uno, sarà probabilmente una perdita di tempo, e non ben testato e messo a punto come una soluzione che è già stata in prima linea.

Quindi quale sarebbe il miglior allocatore che potrei usare per questo scenario?

Nota: sto usando una macchina virtuale Lua nel sistema (che è il colpevole dell'80 +% delle allocazioni), quindi non posso banalmente rifattorizzare il mio codice per utilizzare allocazioni di stack per aumentare le prestazioni di allocazione.

Answer 1

Di recente ho fatto alcune ricerche su questo argomento, poiché abbiamo riscontrato un problema con la frammentazione della memoria. Alla fine abbiamo deciso di rimanere con l'implementazione di GNU libc e aggiungere alcuni pool di memoria a livello di applicazione dove necessario. C'erano altri allocatori che avevano un migliore comportamento di frammentazione, ma non eravamo abbastanza a nostro agio nel sostituire il malloc a livello globale. GNU ha il vantaggio di una lunga storia alle spalle.

Nel tuo caso sembra giustificato; supponendo che non sia possibile correggere la VM, queste allocazioni minime sono molto dispendiose. Non so quale sia il tuo intero ambiente, ma potresti prendere in considerazione l'idea di raggruppare le chiamate in malloc / realloc / free solo sulla VM in modo da poterlo passare a un gestore progettato per piccoli pool.

Answer 2

In un precedente progetto in C su cui ho lavorato, abbiamo intrapreso la strada dell'implementazione delle nostre routine di gestione della memoria per una libreria eseguita su una vasta gamma di piattaforme, inclusi i sistemi embedded. La libreria ha inoltre allocato e liberato un gran numero di piccoli buffer. Ha funzionato relativamente bene e non ha impiegato una grande quantità di codice per implementare. Posso darti un po 'di informazioni su tale implementazione nel caso tu voglia sviluppare qualcosa da te.

L'implementazione di base includeva una serie di routine che gestivano buffer di dimensioni stabilite. Le routine sono state usate come wrapper attorno a malloc () e free (). Abbiamo usato queste routine per gestire l'allocazione delle strutture che usavamo di frequente e anche per gestire buffer generici di dimensioni di set. È stata utilizzata una struttura per descrivere ogni tipo di buffer gestito. Quando veniva allocato un buffer di un tipo specifico, avremmo malloc () la memoria in blocchi (se un elenco di buffer liberi era vuoto). Ad esempio, se gestissimo buffer a 10 byte, potremmo creare un singolo malloc () che conteneva spazio per 100 di questi buffer per ridurre la frammentazione e il numero di malloc sottostanti necessari.

Nella parte anteriore di ciascun buffer si trova un puntatore che verrebbe utilizzato per concatenare i buffer in un elenco libero. Quando venivano allocati i 100 buffer, ciascun buffer veniva concatenato nella lista libera. Quando il buffer era in uso, il puntatore veniva impostato su null. Abbiamo anche mantenuto un elenco dei "blocchi" di buffer, in modo da poter effettuare una semplice pulizia chiamando free () su ciascuno dei buffer effettivi malloc.

Per la gestione delle dimensioni del buffer dinamico, abbiamo anche aggiunto una variabile size_t all'inizio di ogni buffer che indica la dimensione del buffer. Questo è stato quindi utilizzato per identificare in quale blocco buffer reinserire il buffer quando è stato liberato. Avevamo routine di sostituzione per malloc () e free () che eseguivano l'aritmetica del puntatore per ottenere la dimensione del buffer e quindi per inserire il buffer nell'elenco libero. Avevamo anche un limite alla quantità di buffer gestiti. I buffer di dimensioni superiori a questo limite sono stati semplicemente mallocati e passati all'utente. Per le strutture che abbiamo gestito, abbiamo creato routine wrapper per l'allocazione e la liberazione delle strutture specifiche.

Alla fine abbiamo anche evoluto il sistema per includere la garbage collection su richiesta dell'utente per ripulire la memoria inutilizzata. Dato che avevamo il controllo su tutto il sistema, ci sono state varie ottimizzazioni che siamo riusciti a fare nel tempo per aumentare le prestazioni del sistema. Come ho già detto, ha funzionato abbastanza bene.

Answer 3

Sono un po 'in ritardo alla festa, ma voglio solo condividere un allocatore di memoria molto efficiente per i sistemi embedded che ho recentemente trovato e testato: https://github.com/dimonomid/umm_malloc

Questa è una libreria di gestione della memoria appositamente progettata per funzionare con ARM7, personalmente la uso su dispositivi PIC32, ma dovrebbe funzionare su qualsiasi dispositivo a 16 e 8 bit (ho in programma di testare su PIC24 a 16 bit , ma non l'ho ancora testato)

Sono stato gravemente sconfitto dalla frammentazione con allocatore predefinito: il mio progetto spesso alloca blocchi di varie dimensioni, da diversi byte a diverse centinaia di byte, e talvolta ho riscontrato un errore di "memoria insufficiente". Il mio dispositivo PIC32 ha un totale di 32 KB di RAM e 8192 byte sono usati per l'heap. Nel momento specifico sono disponibili più di 5 KB di memoria libera, ma l'allocatore predefinito ha un blocco di memoria massimo non frammentato di soli 700 byte, a causa della frammentazione. È un peccato, quindi ho deciso di cercare una soluzione più efficiente.

Ero già a conoscenza di alcuni allocatori, ma tutti hanno dei limiti (come la dimensione del blocco dovrebbe essere una potenza o 2, e a partire non da 2 ma da, diciamo, 128 byte), o era solo buggy. Ogni volta, dovevo tornare all'allocatore predefinito.

Ma questa volta, sono fortunato: ho trovato questo: http: // hempeldesigngroup .com / embedded / stories / memorymanager /

Quando ho provato questo allocatore di memoria, esattamente nella stessa situazione con 5 KB di memoria libera, ha più di 3800 byte di blocco! È stato così incredibile per me (rispetto a 700 byte) e ho eseguito un duro test: il dispositivo ha funzionato pesantemente per più di 30 ore. Nessuna perdita di memoria, tutto funziona come dovrebbe funzionare. Ho anche trovato questo allocatore nel repository FreeRTOS: http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg= 1041 # , e questo fatto è un'ulteriore prova della stabilità di umm_malloc. Quindi sono passato completamente a umm_malloc e ne sono abbastanza soddisfatto.

Ho dovuto solo cambiarlo un po ': la configurazione era un po' buggy quando la macro UMM_TEST_MAIN non è definita, quindi ho creato il repository github (il link è in cima a questo post). Ora, la configurazione dipendente dall'utente è memorizzata in un file separato umm_malloc_cfg.h

Non ho ancora approfondito gli algoritmi applicati in questo allocatore, ma ha una spiegazione molto dettagliata degli algoritmi, quindi chiunque sia interessato può guardare all'inizio del file umm_malloc.c. Almeno, " binning " l'approccio dovrebbe offrire enormi vantaggi in termini di frammentazione: http://g.oswego.edu/dl /html/malloc.html

Credo che chiunque abbia bisogno di un efficiente allocatore di memoria per microcontrollori, dovrebbe almeno provarlo.

Answer 4

Anche se è passato un po 'di tempo da quando l'ho chiesto, la mia soluzione finale è stata quella di utilizzare SmallObjectAllocator di LoKi che funzionava benissimo. Sbarazzato di tutte le chiamate del sistema operativo e migliorato le prestazioni del mio motore Lua per i dispositivi integrati. Molto bello e semplice, e vale circa 5 minuti di lavoro!

Answer 5

Dalla versione 5.1 , Lua ha consentito una personalizzata allocatore da impostare quando creando nuovi stati .

Answer 6

Vorrei solo aggiungere a questo anche se è un vecchio thread. In un'applicazione incorporata se è possibile analizzare l'utilizzo della memoria per l'applicazione e trovare un numero massimo di allocazione di memoria di dimensioni variabili, in genere il tipo più veloce di allocatore è quello che utilizza pool di memoria. Nelle nostre app integrate possiamo determinare tutte le dimensioni di allocazione che saranno mai necessarie durante il runtime. Se riesci a farlo, puoi eliminare completamente la frammentazione dell'heap e disporre di allocazioni molto veloci. La maggior parte di queste implementazioni ha un pool di overflow che farà un regolare malloc per i casi speciali che si spera siano molto lontani se avessi fatto bene la tua analisi.

Answer 7

Ho usato il sistema 'binary buddy' con buoni risultati in vxworks. Fondamentalmente, dividi il tuo mucchio tagliando i blocchi a metà per ottenere la più piccola potenza di un blocco di due dimensioni per contenere la tua richiesta e quando i blocchi vengono liberati, puoi fare un passaggio sull'albero per unire nuovamente i blocchi per mitigare la frammentazione. Una ricerca su Google dovrebbe mostrare tutte le informazioni necessarie.

Answer 8

Sto scrivendo un allocatore di memoria C chiamato tinymem che intende deframmentare l'heap e riutilizzare la memoria. Dai un'occhiata:

https://github.com/vitiral/tinymem

Nota: questo progetto è stato interrotto per funzionare sull'implementazione della ruggine:

https://github.com/vitiral/defrag-rs

Inoltre, non avevo mai sentito parlare di umm_malloc prima. Sfortunatamente, non sembra essere in grado di gestire la frammentazione, ma sembra sicuramente utile. Dovrò verificarlo.