Speichermanagement für Arduino

Derzeit laufe ich mich ein wenig warm für die Entwicklung meines eigentlich angestrebten Arduino-Projektes. Eine Sache, die ich dort brauchen werde, sind Strings bzw. generell 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.

1
2
3
4
5
6
7
CHARRAY alloc_charray(CHARRAY_TYPE size);
CHARRAY copy_charray(CHARRAY charray);
void dealloc_charray(CHARRAY charray);
CHARRAY make_charray(CHARRAY array, CHARRAY_TYPE size);
void print_charray(CHARRAY charray);
CHARRAY resize_charray(CHARRAY charray, CHARRAY_TYPE size);
CHARRAY_TYPE sizeof_charray(CHARRAY charray);

Die Verwendung dieser API (von der ihr hier die Headerdatei und die Sourcedatei findet), ist relativ einfach. Man allokiert ein Chararray, kann dann über die Indizes 1 bis size darauf zugreifen und in 0 ist die Größe des Chararrays gespeichert. Wenn man fertig ist, deallokiert man den Speicher wieder. Das ganze bezeichnet man übrigens als length-prefixed Strings.

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 - der, der per malloc(), calloc() angefragt wird und der, der in Form von Variablen direkt in Funktionen verwendet wird. Diese befinden sich in verschiedenen Speicherbereichen und wachsen sich entgegen (der eine von links zur Mitte, der andere von rechts zur Mitte). Im schlimmsten Fall treffen sich beide Speicherbereiche in der Mitte. Das hieße, dass der eine Speicher den anderen überschreibt. Im Falle vom Arduino würde man das nicht mitkriegen - eher unschön, da es so zu den unterschiedlichsten Problemen kommen kann. Wenn man keine Kontrolle über den Heapbereich hat und dieser 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 erstmal einen einfachen Speicherzugriff zu basteln. Auf dessen Basis würde ich dann den eigentlichen Speichermanager bauen.

1
2
3
4
5
6
7
8
9
10
11
12
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);

Die Funktionsweise entspricht grob den Chararrays. Man allokiert einen Speicherblock, kann mit diesem arbeiten und deallokiert ihn später. Wichtig sind die beiden Funktionen copy_mem() und copy_mem_rev(), diese werden später der Hauptbestandteil der Speicherverwaltung sein (hier gibt es die Headerdatei und die Sourcedatei).

Das Problem an so einer Speicherverwaltung 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. Hier schemenhaft mal 16 Byte Speicher:

1
[.][.][.][.][.][.][.][.][.][.][.][.][.][.][.][.]

Von diesem Speicher kann man sich nun durch Allokieren Teile reservieren - zum Beispiel, um darin Texte oder Zahlen zu speichern. Wir allokieren uns als Beispiel jetzt mal 2 Blöcke. Einen mit der Größe 3, in den wir "xxx" hineinschreiben und einen mit der Größe 4, in den wir "yyyy" rein schreiben. Das ganze sähe dann so aus:

1
[x][x][x][y][y][y][y][.][.][.][.][.][.][.][.][.]

Die einzelnen Bytes sind einfach aneinander gereiht. Wenn wir nun den ersten Block mit "xxx" nicht mehr benötigen, können wir ihn deallokieren, damit er für andere Speicheranfragen verfügbar ist:

1
[.][.][.][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:

1
[.][.][.][y][y][y][y][z][z][z][z][z][.][.][.][.]

Soweit in Ordnung. Aber was, wenn wir nun noch einen Block mit der Größe 6 für den Wert "aaaaaa" haben wollen? Jetzt stecken wir in der Sackgasse. Wir haben zwar theoretisch noch 7 Byte an Speicher zur Verfügung, diese sind jedoch in Teile von je 3 und 4 Bytes zertrennt (sprich: fragmentiert). Somit können wir keinen Speicherblock mit der gewünschten Größe allokieren.

Glücklicherweise hat solch ein Arduino nicht sonderlich viel Speicher und so wie der Zufall will, ist es nicht wichtig, dass die Speicherverwaltung bei meinem Projekt sonderlich schnell ist. Sie muss zuverlässig sein - das ist viel wichtiger. Aus diesem Grund geht sie wie folgt vor: Jedes Mal, wenn ein Speicherblock deallokiert wird, wird sämtlicher Speicher, der ihm folgt, nach vorne geschoben, sodass keine Lücken im Speicher entstehen. So hat man am Ende immer den gesamten freien Speicher hinter den belegten Blöcken und muss sich nicht um etwaige Fragmentierung sorgen. Und noch eine andere tolle Sache: Wir können die Größe von Speicherblöcken ändern, ohne sie umherkopieren zu müssen. 🙂

Wenn wir uns noch einmal das Beispiel nehmen:

1
[x][x][x][y][y][y][y][.][.][.][.][.][.][.][.][.]

An der Stelle, wo der Block "xxx" deallokiert wird, geben wir nicht nur den Speicher für eine neuerliche Verwendung frei, sondern wir schieben den Block "yyyy" nach vorne:

1
[y][y][y][y][.][.][.][.][.][.][.][.][.][.][.][.]

Wenn wir nun den Block "zzzzz" allokieren...

1
[y][y][y][y][z][z][z][z][z][.][.][.][.][.][.][.]

...haben wir am Ende genug Platz, um unseren großen Block "aaaaaa" zu allokieren. Das war vor der Einführung unseres kleinen Speichermanagers noch nicht möglich:

1
[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. Mit anderen Worten: wir 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 X sich hier jedoch ändern kann, wenn Speicher deallokiert wird, wäre das doof. Also müssen wir die Blöcke stattdessen mit "Speicherblock mit der Nummer X" ansprechen und dann intern gucken, wo dieser Speicherblock denn überhaupt liegt.

Wenn man das Speichern dieser Information 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 für eine statische Liste entschieden.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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);
CHUNK duplicate_chunk(CHUNK number);
CHUNK make_chunk(CHUNK_TYPE* chunk, CHUNK_SIZE size);
bool print_chunk(CHUNK number);
bool printHex_chunk(CHUNK number);
bool zero_chunk(CHUNK number);
MEM_SIZE zeroFreeMem_chunk();

Bei der Initialisierung des Speichermanagers wird zum einen angegeben, wieviel Speicher er verwalten soll und zum anderen, wieviele Speicherslots (also Speicherteile) maximal möglich sein sollen. Bei jeder Allokierung eines Chunks geht einer dieser Slots verloren und bei jedem Deallokieren eines Chunks erhält man den Slot zurück.
Die API meines kleinen Speichermanagers gibt mir noch ein paar andere nützliche Funktionen: 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 (hier gibt es die Headerdatei und die Sourcedatei).

Soderle, ich hoffe, euch hat der kleine Ausflug in die Welt der Speicherverwaltung gefallen. Alle Codebeispiel sind sowohl auf meinem Mac als auch auf dem Arduino lauffähig. Ich gehe also mal davon aus, dass sie halbwegs plattformunabhängig sind. 😀

Für Fragen, Anregungen und Verbesserungsvorschläge bin ich natürlich jederzeit zu haben. 🙂

Speicherintensive Grüße, Kenny

P.S.: Hier mal ein Beispiel, wie man das ganze nutzen kann.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 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();

7 Kommentare » Schreibe einen Kommentar

  1. Ich würde dir empfehlen, Codeschnipsel via gist.github.com einzubinden/anzubieten.

    Gerade für das Anschauen von verlinkten .c/.h-Dateien von Vorteil, da man sich so den Umweg über Herunterladen & ImEditorÖffnen spart und sich einfach den Sourcecode online anschauen kann.

    • Ich muss generell gucken, wie ich das am besten mache. Aber bisher sind es nur Zwischenarbeitsstände. Versionsnummern mit drei Zahlen zeigen Alpha-Releases an. Das hier sind alles "0.0.1"er Releases - also die erste Alpha vor einer Beta. Ab der ersten Betaversion wird's interessant. Bis dahin ist das Anbieten des Codes nur eine nette Dreingabe, nicht der Hauptgrund des Artikels. 🙂

      • Aber gerade dafür sind ja Gists auch gut, weil du dort selbst die kleinsten Schnipsel versionieren kannst. (Sind alles Minirepos.)

        • Ja, schon klar. Aber ich habe mich bereits lange genug davor gedrückt, eine ordentliche Downloadlösung zu bauen. Das soll sich ändern. Hier weiß ich allerdings nicht, ob ich mich auf einen externen Hoster wie github einlassen will. Das muss ich mir erst genau überlegen. 🙂

Schreibe einen Kommentar

Um Ihnen beim weiteren Kommentieren auf dieser Webseite die erneute Eingabe Ihrer Daten zu ersparen, wird beim Absenden Ihres Kommentars ein Cookie an Ihren Browser gesendet und von diesem gespeichert. Mit dem Absenden eines Kommentars auf dieser Webseite stimmen Sie der Speicherung und Übertragung dieses Cookies explizit zu.

Pflichtfelder sind mit * markiert.