Fragen? Antworten! Siehe auch: Alternativlos
size_t scan_ushort(const char* src,unsigned short* dest) {Der Code nimmt eine Zeichenkette und versucht das als ASCII-Dezimalzahl zu parsen. Rückgabewert ist die Anzahl der Bytes, die gelesen wurden. Der Punkt an der Funktion ist, dass sie Integer Overflow erkennen und dann abbrechen soll. Bei scan_ushort ist auf meinem System der maximal abbildbare Wert 65535. Wenn man scan_ushort mit "65535" aufruft, soll er 5 zurückgeben und 65535 nach dest schreiben. Wenn man es mit "65536" aufruft, soll er 4 zurückgeben und 6553 nach dest schreiben.
if (sizeof(unsigned short) == sizeof(unsigned int)) {
/* a good optimizing compiler should remove the else clause when not
* needed */
return scan_uint(src,(unsigned int*)dest);
} else {
register const char *tmp=src;
register unsigned short int l=0;
register unsigned char c;
while ((c=*tmp-'0')<10) {
unsigned short int n;
/* division is very slow on most architectures */
n=l<<3; if ((n>>3)!=l) break;
if (n+(l<<1) < n) break;
n+=l<<1;
if (n+c < n) break;
l=n+c;
++tmp;
}
if (tmp-src) *dest=l;
return tmp-src;
}
}
Der Überlauf-Check sieht so aus, weil die anderen Optionen doof sind. Die offensichtliche Option wäre, dass ich einen Zwischenwert eines breiteren Integertypen nehme. Für scan_ushort würde das auch gehen, aber für scan_ulonglong nicht. Daher nehme ich die Option lieber nicht. Der zentrale Schritt ist:
l=l*10+(naechstes_zeichen-'0')Dabei kann sowohl die Multiplikation als auch die Addition überlaufen, und beides muss geprüft werden. Option 1:
temp=l*10;Leider sind Multiplikation und vor allem Division auf vielen verbreiteten Prozessoren sehr teuer. Option 2:
if (l!=temp/10) goto fail;
temp=l*8; // *8 ist ein Linksshift um drei Bits, kostet so gut wie nichtsSieht sehr kompliziert aus, ist aber eigentlich sehr einfach. Und dann gibt es noch den finalen Schritt, dass man zu temp (im Code oben als n bezeichnet) noch die aktuelle Ziffer dazuaddiert. Das kann auch überlaufen, daher:
if (temp/8!=l) goto fail; // /8 ist ein Rechtsshift um drei Bits, kostet auch so gut wie nichts
if (temp+(l*2) < temp) goto fail; // l*8+l*2==l*10, l*2 ist Linksshift um 1, ist billig
if (n+c < n) goto fail;Und hier war der Bug. Dieser Test schlug nie an. Der Hintergrund sind die Integer-Promotion-Regeln in C. Die sagen, dass in arithmetischen Ausdrücken beide Seiten zu int promoted werden, wenn sie kleiner sind. Das heißt, dass n+c nicht überläuft, sondern komfortabel in dem int Platz hat.
Natürlich frage ich mich heute, wie mir dieser offensichtliche Fehler 2006 passieren konnte. Die Antwort ist, dass ich das von scan_uint kopiert hatte, und dort funktioniert der Check. Hätte ich trotzdem sehen müssen. Oder zumindest ein Unit-Test hätte es finden müssen. Aber mein Unit-Test hat nur 655350 getestet, nicht 65536.
Ich rolle das hier aus, weil immer wieder Leute irgendwo behaupten, ich hielte mich selbst für unfehlbar. Das ist natürlich völliger Bullshit. Fehler machen alle. Sogar djb. :-)
Wichtig ist, dass man dazuzulernen bereit ist, und dass man alten Code alle paar Jahre nochmal anguckt, um sowas zu finden. Es sind ja auch nicht alle "Fehler" tatsächlich Fehler. Manchmal haben sich auch die Ansprüche geändert. So hatte ich dieses "bei Overflow abbrechen" nur bei ein paar Integer-Parsern implementiert damals, weil mir das bei Hex und Oktal schlicht nicht so wichtig war. Das lasse ich mir heute nicht mehr durchgehen.
Ich erinnere mich daran, dass ich vor Jahren mal eine Mail von Florian Weimer kriegte, damals beim RUS-CERT. Das war 2002. Der meinte, dass das calloc in dietlibc unsicher sei. Wenn man da zwei große Zahlen reintut, dann kann die Multiplikation überlaufen, und dann kann calloc Erfolg zurückliefern, obwohl die Werte zu groß waren. Ich fand damals, dass das nicht meine Schuld sei, wenn die Leute das falsch aufrufen. Ich habe das widerwillig trotzdem gefixt. Heute habe ich da meine Philosophie komplett geändert. Wenn du ein Stück Code schreibst, das man falsch aufrufen kann, dann musst du das soweit sinnvoll und möglich abfangen. Der Grund ist, dass das die TCB reduziert. Wenn zehn Leute deine Funktion aufrufen, dann muss ich beim Security-Audit nur noch gucken, ob der Check in deiner Funktion sauber ist, nicht ob nicht einer deiner zehn Aufrufer Mist macht.
Update: Hier kam die Frage auf, ob ich das heute noch so schreiben würde. Nein, würde ich nicht. Seit dem habe ich ein paar Sachen ausgemessen und würde lieber n*8 als n<<3 schreiben. Auch der Trick mit dem c=*tmp-'0' (c ist unsigned, daher mappt der Fall c<'0' auf einen großen Wert und der Test auf kleiner Zehn schlägt fehl) ist überflüssig, wie ich in der Zwischenzeit gelernt habe. Das register-Schlüsselwort bringt nichts, schadet aber auch nichts. Die Variablennamen könnten länger sein, aber das würde die Lesbarkeit nicht erhöhen. Ob da jetzt "temp" oder "n" steht, spielt auch keine Rolle. l und c würde ich auch heute so benennen. tmp würde ich heute cur oder so nennen. Die Integer Overflow Checks würde ich auch heute noch so machen. Wieso habe ich mir überhaupt so viel Gedanken um die Performance gemacht? Weil jeder Cycle, den dein Code langsamer als nötig läuft, ein Argument für deine User ist, lieber was anderes zu benutzen. Und das andere ist dann weniger sorgfältig und merkt nicht, wenn eine zu große Zahl reinkommt.
Für Library-Programmierer gibt es meiner Erfahrung nach mehrere goldene Richtlinien, an die man sich dringend halten sollte.
Sonst kann man es auch gleich bleiben lassen.