Speichermanagement für Arduino
15.04.2013 yahe arduino code hardware legacy security
Derzeit laufe ich mich ein wenig warm für die Entwicklung meines eigentlich angestrebten Arduino-Projekts. Eine Sache, die ich dort brauchen werde, sind Strings bzw. Zeichenketten. Dafür verwendet man normalerweise einfach "unsigned char"-Arrays und speichert sich die Länge irgendwo noch mit ab. Ich wollte das ganze allerdings ein bisschen handlicher haben, also schrieb ich mir eine kleine API, die mir gut nutzbare Strings bastelt. Die Verwendung war relativ einfach: Es wurde ein Array allokiert, dessen Index mit 1 beginnt, während im Index 0 die Größe des Arrays gespeichert wurde. Das ganze bezeichnet man als "length-prefixed String". Wenn man fertig war, deallokierte man den Speicher einfach wieder.
Soweit so gut, allerdings machte @servicecase18 mich darauf aufmerksam, dass ich mir mehr Gedanken über die Speicherverwaltung machen sollte. Hintergrund: Es gibt zwei verschiedene Arten von Speicher. Auf der einen Seite ist da der Heap, in dem per "malloc()" und "calloc()" dynamisch Speicher angefragt wird. Und auf der anderen Seite gibt es den Stack, in dem lokale Variablen von Funktionsaufrufen vorgehalten werden. Diese beiden Speicherbereiche wachsen sich entgegen. Im schlimmsten Fall treffen sich beide Speicherbereiche, was dazu führt, dass die Schreibzugriffe in dem einen Speicherbereich unerwartete Änderungen in dem anderen Speicherbereich verursacht. Wenn man keine Kontrolle über den Heap hat und diesen nach und nach zumüllt, läuft man eher Gefahr, auf solche Probleme zu stoßen. Also machte ich mich ans Werk und begann damit, mir eine einfache Speicherverwaltung zu bauen, die Teil der Bibliothek Cryptuino geworden ist.
MEM_SIZE init_mem(MEM_SIZE size);
bool deinit_mem();
bool is_init_mem();
MEM_SIZE max_mem();
MEM_SIZE min_mem();
MEM_SIZE sizeof_mem();
MEM_TYPE get_mem(MEM position);
bool set_mem(MEM position, MEM_TYPE value);
bool copy_mem(MEM source, MEM destination, MEM_SIZE count);
bool copy_mem_rev(MEM source, MEM destination, MEM_SIZE count);Deren Funktionsweise entspricht im ersten Schritt grob dem vorherigen Ansatz. Man allokiert einen Speicherblock, kann mit diesem arbeiten und deallokiert ihn später (bzw. niemals). Wichtig sind die beiden Funktionen "copy_mem()" und "copy_mem_rev()", denn diese werden später der Hauptbestandteil der Speicherverwaltung sein. Das Hauptproblem, das solch eine Speicherverwaltung lösen muss, ist die sogenannte Fragmentierung.
Stellen wir uns den Speicher im Computer mal als eine Reihe von Boxen vor, in die wir Inhalte packen können.
[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]Von diesem Speicher kann man sich nun durch Allokieren einzelne Teile reservieren, z.B. um darin Texte oder Zahlen zu speichern. Wir allokieren uns mal 2 Speicherblöcke, einen mit der Größe 3, in den wir "xxx" schreiben und einen mit der Größe 4, in den wir "yyyy" schreiben.
[x][x][x][y][y][y][y][ ][ ][ ][ ][ ][ ][ ][ ][ ]Die einzelnen Bytes sind einfach aneinander gereiht. Wenn wir nun den ersten Speicherblock mit dem Inhalt "xxx" nicht mehr benötigen, können wir ihn deallokieren, damit er für andere Speicheranfragen verfügbar ist.
[ ][ ][ ][y][y][y][y][ ][ ][ ][ ][ ][ ][ ][ ][ ]Wenn wir nun einen neuen Speicherblock mit der Größe 5 für den Wert "zzzzz" benötigen, müssen wir diesen hinter den Block mit dem Inhalt "yyyy" schreiben, da davor ja nicht genug Platz ist.
[ ][ ][ ][y][y][y][y][z][z][z][z][z][ ][ ][ ][ ]Soweit funktioniert alles normal. Wenn wir nun noch einen Speicherblock mit der Größe 6 für den Wert "aaaaaa" haben wollen, bekommen wir jedoch ein Problem. Wir haben zwar theoretisch noch 7 Bytes an Speicher zur Verfügung, diese sind jedoch in Teile von je 3 Bytes und 4 Bytes zertrennt (sprich: fragmentiert). Somit können wir keinen Speicherblock mit der gewünschten Größe mehr allokieren.
Glücklicherweise hat solch ein Arduino nicht sonderlich viel Speicher und glücklicherweise ist es nicht wichtig, dass die Speicherverwaltung bei meinem Projekt sonderlich schnell ist. Es ist viel wichtiger, dass sie zuverlässig arbeitet. Aus diesem Grund geht sie wie folgt vor: Jedes Mal, wenn ein Speicherblock deallokiert wird, wird sämtlicher nachfolgender Speicherinhalt nach vorne geschoben, sodass keine Lücken im Speicher entstehen. Dadurch hat man am Ende immer den gesamten freien Speicher hinter den belegten Speicherblöcken und muss sich nicht um etwaige Fragmentierung sorgen.
Gehen wir noch einmal zu dem Beispiel zurück, bei dem ein Speicherblock mit 3 Bytes und ein Speicherblock mit 4 Bytes belegt war.
[x][x][x][y][y][y][y][ ][ ][ ][ ][ ][ ][ ][ ][ ]An der Stelle, wo der Block "xxx" deallokiert wird, geben wir nicht mehr nur den Speicher für eine anderweitige Verwendung frei, sondern wir schieben den Block "yyyy" zusätzlich nach vorn.
[y][y][y][y][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]Nun allokieren wir wieder unseren 5 Bytes großen Speicherblock fÜr den Inhalt "zzzzz".
[y][y][y][y][z][z][z][z][z][ ][ ][ ][ ][ ][ ][ ]Und dank der durchgeführten Defragmentierung haben wir nun am Ende genug Platz, um unseren 6 Bytes großen Speicherblock "aaaaaa" zu allokieren. Das war vor der Einführung unserer kleinen Speicherverwaltung noch nicht möglich.
[y][y][y][y][z][z][z][z][z][a][a][a][a][a][a][ ]Das ganze hat jedoch einen kleinen Haken: Damit wir den Speicher wild umherschieben können, müssen wir die Bezeichnung der Speicherblöcke von ihrer tatsächlichen Position entkoppeln. Stattdessen brauchen eine Referenzliste zwischen "Nummer des Blocks" und "Position des Blocks im Speicher". Normalerweise bezeichnet man Speicherblöcke in der Form "Speicherblock, der an Position X beginnt". Da sich hier die Position X jedoch ändern kann, sobald Speicher deallokiert wird, müssen wir die Speicherblöcke stattdessen mit "Speicherblock mit der Nummer N" ansprechen und dann intern gucken, wo dieser Speicherblock tatsächlich liegt.
Wenn man die Anzahl der Zuordnungen von "Speicherblock mit der Nummer N" zu "Position X" dynamisch machen wollte, könnte man zum Beispiel eine verlinkte Liste nehmen. Diese würde jedoch wieder die Fragmentierungsgefahr für den restlichen Speicher erhöhen. Aus diesem Grund habe ich mich dafür entschieden, dass man beim Initialisieren der Speicherverwaltung angeben muss, wieviele Speicherblöcke maximal allokiert werden können.
CHUNK init_chunk(MEM_SIZE memSize, CHUNK_SIZE chunkCount);
bool deinit_chunk();
bool is_init_chunk();
CHUNK alloc_chunk(CHUNK_SIZE size);
bool dealloc_chunk(CHUNK number);
bool is_alloc_chunk(CHUNK number);
bool resize_chunk(CHUNK number, CHUNK_SIZE size);
CHUNK_SIZE countof_chunk();
CHUNK_SIZE max_chunk();
CHUNK_SIZE min_chunk();
CHUNK_SIZE free_chunk();
CHUNK_SIZE used_chunk();
MEM_SIZE freeMem_chunk();
MEM_SIZE usedMem_chunk();
CHUNK_SIZE sizeof_chunk(CHUNK number);
CHUNK_TYPE get_chunk(CHUNK number, CHUNK_SIZE position);
bool set_chunk(CHUNK number, CHUNK_SIZE position, CHUNK_TYPE value);
bool copy_chunk(CHUNK source, CHUNK destination);
bool copyOffset_chunk(CHUNK source, CHUNK destination, CHUNK_SIZE sourceOffset, CHUNK_SIZE destinationOffset);
bool copyOffsetLength_chunk(CHUNK source, CHUNK destination, CHUNK_SIZE sourceOffset, CHUNK_SIZE destinationOffset, CHUNK_SIZE length);
CHUNK duplicate_chunk(CHUNK number);
bool equal_chunk(CHUNK source, CHUNK destination);
bool equalOffset_chunk(CHUNK source, CHUNK destination, CHUNK_SIZE sourceOffset, CHUNK_SIZE destinationOffset);
bool equalOffsetLength_chunk(CHUNK source, CHUNK destination, CHUNK_SIZE sourceOffset, CHUNK_SIZE destinationOffset, CHUNK_SIZE length);
CHUNK make_chunk(CHUNK_TYPE* chunk, CHUNK_SIZE size);
bool print_chunk(CHUNK number);
bool printHex_chunk(CHUNK number);
bool zero_chunk(CHUNK number);
bool zeroOffset_chunk(CHUNK number, CHUNK_SIZE offset);
bool zeroOffsetLength_chunk(CHUNK number, CHUNK_SIZE offset, CHUNK_SIZE length);
MEM_SIZE zeroFreeMem_chunk();Bei der Initialisierung der Speicherverwaltung wird zum einen angegeben, wieviele Bytes an Speicher er verwalten soll und zum anderen, wieviele Speicherblöcke maximal möglich sein sollen. Bei jeder Allokierung eines "Chunks" geht ein freier Speicherblock verloren und bei jedem Deallokieren eines Chunks erhält man einen freien Speicherblock zurück. Die API meines kleinen Speichermanagers gibt mir noch ein paar andere nützliche Funktionen, wie zum Beispiel das Herausfinden des verbrauchten und noch freien Speichers, das Ändern der Größe eines Chunks, das Kopieren des Inhalts eines Chunks in einen anderen, das Duplizieren von Chunks und das Ausnullen von Chunks (um sicher zu gehen, dass dort keine Zufallswerte enthalten sind).
P.S.: Hier sieht man ein Beispiel, wie man die Speicherverwaltung einsetzen kann.
// Speicher mit 1024 Bytes und maximal 32 Chunks reservieren
init_chunk(1024, 32);
// Chunk A mit 100 Bytes erzeugen
CHUNK chunkA = alloc_chunk(100);
CHUNK_SIZE index;
// in Chunk A die Werte von 1..100 schreiben
for (index = 0; index < sizeof_chunk(chunkA); index++) {
set_chunk(chunkA, index, index+1);
}
// die Werte von 100..1 ausgeben
for (index = sizeof_chunk(chunkA); index > 0; index--) {
printf("%d ", get_chunk(chunkA, index-1));
}
printf("\n");
// Chunk B aus Array erzeugen
CHUNK chunkB = make_chunk("Das ist ein Test.", 17);
// Größe von Chunk A ändern
resize_chunk(chunkA, sizeof_chunk(chunkB));
// Inhalt von Chunk B nach Chunk A kopieren
copy_chunk(chunkB, chunkA);
// Inhalt von Chunk A ausgeben
print_chunk(chunkA);
// Speicher von Chunk A und Chunk B freigeben
dealloc_chunk(chunkA);
dealloc_chunk(chunkB);
// leeren Speicher mit Nullen überschreiben
zeroFreeMem_chunk();
// Speichermanager freigeben
deinit_chunk();
