Donnerstag, 8. Januar 2015

Langsamer ist besser!

Die Programmiersprache C gilt als super schnell und optimal geeignet für Hardware-nahe Aufgaben. Im Internet gibt es reichlich Verweise darauf, wie viel schneller C ist und wie viel langsamer im Gegensatz dazu interpretierte Sprachen sind. Das Problem an solchen Vergleichen ist, dass sie Äpfel mit Birnen vergleichen. Das wird deutlich, wenn man sich das folgende Beispiel ansieht.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char **argv)
{
  int8_t a, b, c;

  a = atoi (argv[1]);
  b = atoi (argv[2]);

  c = a + b;

  printf ("%d\n", c);

  return 0;
}

Das Programm erwartet zwei Zahlen als Argument, addiert sie und gibt das Ergebnis aus. Es lässt sich ohne Fehler und Warnungen übersetzen.

cc -Wall -c -o c-speed.o c-speed.c
cc c-speed.o -o c-speed
Und auf den ersten Blick scheint es ganz gut zu funktionieren.

$ ./c-speed 1 2
3
Auf den zweiten Blick auch noch.

$ ./c-speed 10 20
30

Nur auf den dritten leider nicht mehr.

$ ./c-speed 100 200
44

Das Problem ist, dass für die Speicherung der Zahl 8 Bit verwendet wurden. Integer-Zahlen werden von heutzutage üblichen Architekturen als Zweierkomplement gespeichert. Das bedeutet, dass ein Bit für das Vorzeichen reserviert wird und die restlichen für die Zahl. Der Wertebereich ist somit -128 bis 127. Darin lässt sich eine 100 speichern aber keine 200 und erst recht keine 300.

Die binäre Darstellung der drei Zahlen sieht folgendermaßen aus.

100 ⇒ 0 1 1 0 0 1 0 0
200 ⇒ 0 1 1 0 0 1 0 0 0
300 ⇒ 0 1 0 0 1 0 1 1 0 0

Auf der rechten Seite ist das niedrigstwertige Bit und auf der linken das höchstwertige Bit. Die führende Null gibt an, dass es sich um eine positive Zahl handelt. Für die 200 reichen somit 8 Bit nicht mehr aus, es werden 9 benötigt. Und für die 300 werden schon 10 benötigt.

C ist dieser Sachverhalt völlig egal. Statt den Überlauf zu erkennen wird einfach mit dem weiter gerechnet, was übrig bleibt nachdem die übergelaufenen Bits weggeschmissen wurden. Dafür gibt es auch eine hochtrabende Bezeichnung: rechnen in Restklassenringen. Und das ist etwas völlig anderes als das, was Schülern in Unter- und Mittelstufe als "Rechnen" beigebracht wird.

In diesem konkreten Fall bedeutet es, dass das neunte Bit der 200 und das neunte und zehnte Bit der 300 über Bord gehen. Allerdings kommt es bei der 300 dazu gar nicht erst, weil durch den Wegfall des neunten Bits die 200 negativ wird, weil jetzt das höchste Bit nicht mehr eine Null sondern eine Eins ist.

200 ⇒ 0 1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 0 ⇒ -56

Somit entsteht bei der Addition gar kein Überlauf, da C aus der Addition eine Subtraktion macht: 100 + (-56) = 44. Somit wäre erklärt wie C bei der Addition von 100 und 200 auf 44 kommt. Und da C keine Addition sondern eine Restklassen-Addition durchgeführt hat, hat es auch alles richtig gemacht. Dass weder das Restklassen-Ergebnis noch die Erklärung, was genau es denn ist, einem normal sterblichen Anwender irgend etwas bringen, der auf seinem Kontoauszug eine 44 liest, obwohl er gerade 200€ eingezahlt hat und zuvor noch 100€ auf dem Konto waren, dürfte offensichtlich sein.

Ein typischer C-Programmierer wird nun darauf hinweisen, dass man ja auch mehr Bits für die Speicherung von Zahlen verwenden kann. Die Zeiten, dass man mit Prozessoren auskommen musste, die nur 8 Bit verarbeiten konnten sind lange vorbei und somit könnte man zur Speicherung der Zahl int16_t oder int32_t oder int64_t verwenden. Schon int16_t würde für die Speicherung von 100, 200 und 300 völlig ausreichen, da für die 300 nur 10 Bit nötig waren.

Auf den ersten Blick erscheint das einleuchtend aber das ist nicht wirklich eine Lösung für das Problem. Das Problem ist lediglich aufgeschoben und aufgeschoben ist bekannter Weise nicht aufgehoben. Die Aufschiebung besteht darin, dass der Überlauf bei der Verwendung von int16_t nicht mehr bei Zahlen größer als 127 auftritt sondern bei Zahlen größer als 32767. Das Spielchen kann man jetzt weiter treiben und immer größere Wortbreiten verwenden.

8 Bit:127
16 Bit:32767
32 Bit:2147483647
64 Bit:9223372036854775807
128 Bit:170141183460469231731687303715884105727
256 Bit:57896044618658097711785492504343953926634992332820282019728792003956564819967

Die 256 Bit erscheinen auf den ersten Blick recht groß und man könnte auf die Idee kommen, die Wahrscheinlichkeit, dass es in einem Programm, das mit 256 Bit Zahlen arbeitet, zu einem Überlauf kommt, könne man jetzt wirklich vernachlässigen.

Allerdings sollte man sich klar machen, dass es durchaus Anwendungen gibt, bei denen längere Zahlen benötigt werden. Eine RSA-Verschlüsselung mit 256 Bit Zahlen ist heutzutage als lächerlich zu betrachten, da zur Zeit mindestens 2048 Bits benötigt werden, um einigermaßen sicher zu sein. Und ebenso wichtig dürfte der Sachverhalt sein, dass man nicht davon ausgehen darf, dass ein Programm in dem vom Programmierer vorgesehenen Zahlenbereich arbeitet. Jemand, der eine Sicherheitslücke in einer Software aufspüren will, wird selbstverständlich ein Programm gerade mit solchen Eingaben füttern, die außerhalb dessen liegen, was der Programmierer der Software ursprünglich bei der Planung und Entwicklung als normal angesehen hatte.

Das bedeutet, dass das typische Verhalten eines C-Programmierers, Zahlenüberläufe zu ignorieren, ein sehr großes Sicherheitsrisiko darstellt. Die Geschwindigkeit, die man dadurch erreicht, dass man einfach ungenau arbeitet, wird durch Fehler und Sicherheitsprobleme erkauft. Und somit ist die Aussage "C sei schnell" mehr ein Fluch als ein Segen.

Wenn man also Zahlenüberläufe wirklich vermeiden will, dann ist die logische Konsequenz, dass man eine Zahl nicht mehr in etwas speichern kann, das durch den Restklassenring der gerade zur Verfügung stehenden CPU beschränkt ist. Denn genau das macht C. Statt dessen muss man eine Zahl als eine sog. Bignum oder Big-Integer speichern. Das wiederum geht auch in C unter Verwendung der GMP-Bibliothek. Aber dadurch verliert man die sagenumwobene Geschwindigkeit von C, weil eine Zahl nicht mehr mit nur einem CPU-Befehl addiert werden kann. Statt dessen sieht die Rechnung mit Bignums folgendermaßen aus.

  1. Dekodierung der Zahl von der in der Bignum-Bibliothek gewählten Kodierung in eine für die verwendete CPU verständliche Darstellung.
  2. Durchführung der gewünschten Rechnung unter zu Hilfenahme von diversen von der CPU bereitgestellten Operationen.
  3. Codierung der Zahl in die von der Bignum-Bibliothek benötigte Form.
Und dieser Aufwand muss für jede Addition, jede Multiplikation und jede sonstige Rechenoperation gemacht werden. Und damit ist auch sofort klar, dass das alles andere als schnell ist sonder richtig langsam. Und das ist auch gut so. Denn in diesem Fall bedeutet Langsamkeit Richtigkeit.

Wer also der Meinung ist, in C zu programmieren sei eine gute Idee, weil die Programme so schön schnell sind oder die Verwendung des Java-Typs int sei eine gute Idee, weil er so viel schneller als BigInteger ist, dem kann ich nur mein Beileid aussprechen. Die Schnelligkeit von C ist keine Eigenschaft der Sprache, sondern man bezahlt für sie in barer Münze. Heutzutage kann man Exploits wie geschnitten Brot kaufen. Wer also sicher programmieren will, sollte darauf Wert legen, dass seine Programmiersprache keine Werbung damit macht, wie schnell sie sei. Statt dessen gilt beim Programmieren wie in der 30-Zone vor dem Kindergarten:

Langsamer ist besser!

Mittwoch, 7. Januar 2015

Raspberry Pi ohne Bildschirm und Tastatur booten

Mit Hilfe eines seriellen Kabels kann man den Raspberry Pi ganz ohne Bildschirm und Tastatur booten. Und wenn man keine großen Stromverbraucher an den USB-Ports des Raspis hängen hat, reicht auch die normale USB-Stromversorgung über den GPIO-Port. Ein Test-Aufbau auf dem heimischen Schreibtisch vereinfacht sich dadurch erheblich.

Man benötigt für das Login über die serielle Schnittstelle ein speziell für den Raspberry Pi angebotenes serielles USB-Kabel. Ich habe meins für 8,80€ bei Reichelt bestellt. Es nennt sich dort "USB zu TTL für Raspberry Pi, 1,0 m" und die Artikelbezeichnung ist "RPI USB TTL". Man kann kein "gewöhnliches" RS232-USB-Kabel benutzen und die entsprechenden Adern verbinden, weil die Pegel der RS232-Schnittstelle für den GPIO-Port des Raspberry Pi den Tod bedeuten.

Wenn man den Raspi über das Kabel mit dem Computer verbindet, steckt man die rote Ader für die Stromversorgung praktischer weise erst mal nicht. Andernfalls würde er direkt booten und man könnte den Boot-Vorgang im Terminal nicht sehen, da Windows erst mal den Treiber für die serielle Schnittstelle installieren muss.

Wenn Windows den Treiber richtig installiert hat, taucht im Gerätemanager der entsprechende COM-Port mit der Nummer auf, die man für Putty benötigt.

In meinem Fall ist es COM15. Die serielle Schnittstelle des Raspi wird meist mit 115200 Baud betrieben und nicht wie früher üblich mit 9600 Baud. Wenn man in Putty den "Serial" "Connection type" auswählt, kann man COM-Port und Baud-Rate setzen.

Jetzt kann man dem Raspi mit dem roten Kabel seine Versorgungsspannung geben. Die vier Adern des seriellen Kabels müssen folgendermaßen angeschlossen werden

Rot: auf den äußeren beiden Beinen sind die 5 Volt Versorgungsspannung
Schwarz: das dritte Bein ist Ground
Weiß: das vierte Bein ist TX (GPIO 14)
Grün: und das fünfte Bein ist RX (GPIO 15)

Wenn man die Adern richtig gesteckt hat, fängt der Raspi direkt an zu booten.

In Putty kann man parallel verfolgen, wie die Boot-Meldungen durch rauschen. Dank der hohen Baud-Rate geht das angenehm schnell.

Und schließlich kann man sich über die serielle Schnittstelle auch anmelden, ohne dafür eine Tastatur oder einen Monitor bemühen zu müssen.

Hintergrund

Warum funktioniert das so wie oben beschrieben? Grundsätzlich funktioniert eine serielle Konsole an jedem System, das eine serielle Schnittstelle hat. Allerdings muss man jeder Komponente, die eine Ausgabe erzeugt oder Eingaben erwartet, separat mitteilen, dass sie die serielle Schnittstelle nutzen soll. Bei klassischen PC-Systemen sind das die folgenden gemäß der Reihenfolge, wie sie beim Boot aktiv sind:
  1. BIOS: zum Beispiel Phoenix, AMI, OpenBIOS etc.
  2. Boot-Loader: zum Beispiel Grub, Syslinux etc.
  3. Kernel: zum Beispiel Linux.
  4. Konsole: zum Beispiel agetty aus der "util-linux"-Programm-Sammlung.
Viele kommerzielle BIOSe sind nicht in der Lage, für die Ein- und Ausgabe eine serielle Schnittstelle zu verwenden. Man findet die Funktion meist nur bei Server-BIOSen oder bei BIOSen für zum Beispiel Network-Appliances wie dem ALIX-Board. Deswegen ist es heutzutage bei der Verwendung von PC-Hardware meist unüblich geworden, die Konsole auf die serielle Schnittstelle zu legen, was ich aber eher als Mangel betrachte.

Beim Raspi mit Raspbian ist die Situation erfreulicher Weise anders und auch etwas einfacher, weil er weder ein interaktives BIOS noch einen interaktiven Boot-Loader hat. Somit muss man nur noch dem Kernel und der Konsole sagen, dass sie die serielle Schnittstelle verwenden sollen.

Der Kernel wird beim Raspi-Boot-Loader über die Datei "cmdline.txt" auf der SD-Karte parametrisiert. Nachdem das System gebootet ist, ist die SD-Karte unter dem Verzeichnis /boot gemountet:

pi@raspberrypi:~$ cat /boot/cmdline.txt
dwc_otg.lpm_enable=0 console=ttyAMA0,115200 console=tty1 root=/dev/mmcblk0p2 rootfstype=ext4 elevator=deadline rootwait
Der relevante Paramter ist console=ttyAMA0,115200. Die Syntax für den Parameter ist in der Linux-Kernel-Dokumentation zu finden. Das erste Argument ist das serielle Gerät und das zweite die Baud-Rate.

Die Linux-Konsole wird durch den ersten aller Prozesse also Init gestartet. Init wiederum wird durch die Datei /etc/inittab konfiguriert. In der Inittab stehen Programm-Aufrufe pro Runlevel. Der normale Runlevel ist bei Raspbian 2:

pi@raspberrypi:~$ runlevel
N 2
Dem entsprechend muss in der Inittab für Runlevel 2 ein Aufruf von getty konfiguriert sein:
pi@raspberrypi:~$ awk -F: '/^[^#]/ && $2~2' /etc/inittab
id:2:initdefault:
l2:2:wait:/etc/init.d/rc 2
ca:12345:ctrlaltdel:/sbin/shutdown -t1 -a -r now
1:2345:respawn:/sbin/getty --noclear 38400 tty1
2:23:respawn:/sbin/getty 38400 tty2
3:23:respawn:/sbin/getty 38400 tty3
4:23:respawn:/sbin/getty 38400 tty4
5:23:respawn:/sbin/getty 38400 tty5
6:23:respawn:/sbin/getty 38400 tty6
T0:23:respawn:/sbin/getty -L ttyAMA0 115200 vt100
Und dort ist der Aufruf auch in der letzten Zeile zu finden. Wichtig ist, dass überall die gleiche Baud-Rate verwendet wird, da man zum Zeitpunkt der Übergabe der serielle Schnittstelle vom Kernel an Getty in Putty schlecht die Baud-Rate ändern kann.

Wenn man den GPIO-Port 14 für was anderes wie zum Beispiel eine Strom-Trennung verwenden möchte, könnte man den Raspi auch über zwei klassische USB-Seriell-Adapter mit dem PC verbinden: einer käme in den PC und der andere in einen USB-Port des Raspis und verbunden würden die beiden über ein Null-Modem-Kabel. Damit das funktioniert muss im Kernel der passende Treiber für den USB-Seriell-Adapter sein und man müsste anstatt ttyAMA0 das entsprechende Gerät für den USB-Seriell-Adapter verwenden. Typischerweise wäre das ttyUSB0. Allerdings würde dies eine Anpassung am Standard-Raspbian-Image erfordern, was bedeutet, dass man unter Windows die zweite Partition der SD-Karte mounten muss, um dort die Inittab zu ändern. Unter Windows gehört der Schreib-Zugriff auf EXT4-Partitionen nicht zu den Standard-Funktionen. Von Paragon wird ein Tool angeboten, mit dem das möglich sein soll. Wie gut das funktioniert bleibt zu testen.