Category: arduino

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();

Arduino: Mein Einstieg in die Microcontroller-Programmierung

10.04.2013 yahe arduino code hardware legacy

Elektrotechnik war noch nie mein Steckenpferd. Ich hatte zwar Rechnertechnikvorlesungen im Studium, in denen wir auch Dinge wie Ampelanlagen geplant oder kleinere Schaltungen gebastelt haben, trotzdem wurde ich nie das Gefühl los, dass ich dort eher rumprobiere, als wirklich zu wissen, was ich tue. Nach dem Studium habe ich deshalb nichts mehr mit Elektrotechnik zu tun gehabt. Doch das wird sich nun ändern, denn ich habe angefangen, mit der Arduino-Plattform zu spielen. Es handelt sich dabei um Open Hardware, was bedeutet, dass die Baupläne frei verfügbar sind, in Eigenproduktion hergestellt, modifiziert und verkauft werden dürfen. Neben den originalen Arduino-Boards gibt es auch Platinen von Drittanbietern, die "Arduino-kompatibel" sind. Sie lassen sich mit der Original-Software programmieren, können aber mitunter andere Hardwarekomponenten beinhalten.

Interessanterweise sind mir mit meiner Trigger Trap und meiner HexBright bereits mehrere Arduino-kompatible Geräte über den Weg gelaufen. Auch mein Freund Jonas hat bereits mit einem Arduino gebastelt. Mit Hilfe von Multiplexern hat er einen RGB-LED-Tisch gebaut.

Doch wie fängt man am besten an, wenn man keine Ahnung von alldem hat? Ein Crashkurs musste hat. Von denen gibt es einige im World-Wide-Web. Allerdings hatte ich keine Lust, mir selbst erst alles zusammen zu suchen. Deshalb habe ich mich stattdessen für das originale Arduino Starter Kit entschieden.

Arduino Starter Kit

Hauptbestandteile des Starterkits sind ein Arduino Uno, ein Buch mit Bauanleitungen und dazu weitere hilfreiche Bauteile - z.B. ein Breadboard, ein USB-Kabel zum Anschließen des Arduinos an den Computer, ein LCD-Display, viele Widerstände, LEDs, Steckverbinder und so weiter. Im Buch wird auch die Einrichtung der Software und das Aufspielen von Programmen auf die Arduino-Platine thematisiert. Darüber hinaus werden Dinge wie die Verbindung zwischen Stromspannung, Stromstärke und Widerstand, sowie die Markierungen auf Widerständen erklärt.

Starter Kit Hauptbestandteile Starter Kit Hauptbestandteile

Um ehrlich zu sein, habe ich nicht alle Beispielprojekte einzeln zusammengesteckt. Nach den ersten Experimenten habe mir die Beschreibungen und Codebeispiele angesehen, um die Projekte zu verstehen, nutze sie jedoch eher als Referenz, wenn ich ein neues Bauteil in einem eigenen Projekt verwenden möchte. Ein paar Projekte habe ich bereits zusammengebaut.

Lichttheremin

Da wäre zum Beispiel das Lichttheremin LightTheremine, das auch als Projekt im Buch enthalten ist. Hierbei wird anhand eines Photoresistors geprüft, wie hell es ist. Je heller es ist, desto höher ist der Ton, der über ein Piezoelement ausgegeben wird. Theoretisch könnte man damit Musik machen. Wirklich viel Programmieren muss man dafür gar nicht.

Rudimentärer Recorder

Neben dem Ausgeben von Tönen habe ich auch versucht, Töne durch den Bau eines Recorder aufzunehmen. Da ich nur ein Piezoelement zur Verfügung hatte, musste ich ein bisschen tricksen, um mit dem gleichen Bauteil sowohl Töne aufnehmen als auch abspielen zu können. Aus dem Grund gibt es einen Aufnahmeknopf und einen separaten Abspielknopf.

RBG-LED-Datenübertragung RBG-LED-Datenübertragung RBG-LED-Datenübertragung

Beim letzten Projekt RGBdata habe ich eine RGB-LED verwendet, sowie 3 Photoresistoren, die mit jeweils einer Farbe abgeklebt sind. Das hat den Effekt, dass jeder der drei Photoresistoren nur noch auf einen Farbteil der RGB-LED reagiert. Die RGB-LED wird aktiviert und die Photoresistoren lesen den Schaltzustand der RGB-LED wieder aus. Die Idee dahinter ist, mit einer RGB-LED zur selben Zeit drei Informationszustände (rot an/aus, grün an/aus, blau an/aus) darstellen und diese auch wieder auswerten zu können. Inspiriert wurde ich dabei vom blendfreien Fernlicht. Das ganze könnte man verwenden, um per Licht Daten zu übertragen.

Wenn ich genug experimentiert habe, werde ich damit beginnen, ein Projekt zu realisieren, das ich schon seit längerem im Kopf habe, vor dem ich mich aufgrund der Elektrotechnikanteile jedoch bisher immer gesträubt habe. Was es ist und wie es funktioniert, werde ich später mal an geeigneter Stelle präsentieren. Bis dahin werde ich noch ein bisschen Spaß mit meinen Bastelprojekten haben.


Search

Links

RSS feed

Categories

administration (40)
arduino (12)
calcpw (2)
code (33)
hardware (16)
java (2)
legacy (113)
linux (27)
publicity (6)
review (2)
security (58)
thoughts (21)
windows (17)
wordpress (19)