For great juiciness!

Ever since Andrés J. Díaz provided the Redis plugin for collectd, I played with the idea of using Redis to store the data, too. Since the communications library is straight forward and easy to use, I easily wrote the Write Redis plugin which does precisely that. But coding the plugin is not the hard part. As with all database storage backends the schema is the tricky part. Unfortunately, I’m having some performance issues.

I ended up using sorted sets to store the values. Each identifier is used as a key and the value is added to the sorted set as a string. The string contains the timestamp, too, in order to get unique members (there are no duplicates in a set). The timestamp of each value is also used as the score, the sorting parameter. So in a typical setup you’d have a more or less fixed number of keys each updated regularly. Front-ends would use the ZRANGEBYSCORE command to retrieve the performance data within a certain time frame. I decided against using lists because, being linked lists, looking up data for a random time frame is very costly.

Since data is only inserted and never deleted, the amount of data stored will exceed the amount of available RAM eventually – irregardless of the amount of RAM available. The challenge is that there are many small updates distributed over a large set of keys and that this information needs to be written to disk. As I explain in great detail in Inside the RRDtool plugin, the main goal is to avoid disk seeks which are the limiting factor in this task. Redis has full control over where to place each value on disk, in contrast to RRDtool and RRDCacheD. Also, it doesn’t consolidate values into a less detailed resolution. So I, as a user, have sacrificed quite some functionality in order to allow for more performance. But is Redis up for the task or am I using the wrong tool for the job?
(more…)

Comments(115)

I recently stumbled upon an if-condition where I suspected an error. I traced the problem back and went on a journey of incorrect conditions, missing corner cases and plain laziness. I write this down not to expose the authors, but in the hope this is a lesson to someone who uses complicated if-conditions himself.

The task was to check for “simple integers”. Given a character array, the function should return an error if the buffer did not contain a simple and possibly negative integer. Or, a bit more precise: A valid buffer only contains the characters “0” through “9”, a terminating null-byte and optionally a leading minus (actually a hyphen). Easy, isn’t it?

The first version was this:
for (i = 0; buffer[i] != 0; i++)
  if (buffer[i] < '0' || buffer[i] > '9' || (i = 0 && buffer[i] == '-'))
    return error();
This has one obvious flaw: The zero is assigned to i rather than compared with it.

This was caught right away (two days later) and corrected to the second version:
for (i = 0; buffer[i] != 0; i++)
  if (buffer[i] < '0' || buffer[i] > '9' || (i == 0 && buffer[i] == '-'))
    return error();
This was in September 2003. Do you see the problem yet?

Four years later, in March 2007, someone noticed that actually negative numbers don’t work at all. If the first character is a hyphen, the error is triggered. So the code got changed to this:
for (i = 0; buffer[i] != 0; i++)
  if ((buffer[i] < '0' || buffer[i] > '9') && (i != 0 && buffer[i] != '-'))
    return error();
So is this better? A hyphen is accepted as the first character and nowhere else. All done, right? Well, not quite, because the first position is now the only position ever to be checked.

In the following two and a half years the code was re-indented twice, then once re-factored and then re-indented a third time. Was it not for the great Git tools I would never have found the true origin of what is next.

In November 2009 it was discovered that there was still something not quite right. So the code got reworked again.
if ((buffer[0] < '0' || buffer[0] > '9')
    && buffer[0] != '-'
    && buffer[0] == 0))
  return error();
for (i = 1; buffer[i] != 0; i++)
  if (buffer[i] < '0' || buffer[i] > '9')
    return error();
This is close, but still no cookie: All characters except the first one can only be the characters “0” through “9”. The first character, however, is not checked at all. The only condition in which the first error is triggered is if the first character is a null-byte.

While they teach this in the first semester of any computer science class, Boolean algebra and De Morgan’s laws are not easy. Especially if you want to negate an expression with a couple of conditions you really should take a piece of paper to do this. Here is the correct solution in case you were wondering:
for (i = 0; buffer[i] != 0; i++)
  if ((buffer[i] < '0' || buffer[i] > '9') && (i != 0 || buffer[i] != '-'))
    return error();

The morale of this should be to avoid complex, negated conditions if possible. If you do, formulate them positively, but parenthesis around the whole thing and negate it altogether. That’s much easier to comprehend for us mere human beings (and the compiler doesn’t care at all). In my opinion, the best solution for this problem is the following:
for (i = 0; buffer[i] != 0; i++) {
  if ((i == 0) && (buffer[0] == '-'))
    continue;
  if (buffer[i] < '0' || buffer[i] > '9')
    return error();
}
The special condition for the first character is easy to understand because it’s formulated in a positive manner and the common condition for all characters is easy enough to read. This implementation shares one bug with most the other implementations, though: The empty string and the string “-” are not reported as errors. This should be done outside the loop though.

A second option would be to use regular expressions. They were invented so you wouldn’t have to write error prone parsers yourself, you know? An appropriate regular expression would look like this:

^-?[0-9][0-9]*$

This one even takes care of the empty word problem.

Comments Off

Letzten Dienstag hat ein Rentner drei Menschen erschossen und eine vierte Person gefährlich verletzt. Als wolle man meinen letzten Blog-Eintrag untermauern schreibt wdr.de:

„Ein als psychisch auffällig und aggressiv bekannter Rentner hat das Blutbad von Schwalmtal gestanden.”
(Hervorhebung von mir)

Keine Killerspiele, kein Paintball, kein Schützenverein, kein Ausländer – kein Wunder dass die entsprechenden Berichte auf tagesschau.de nur noch im Innenpolitik-Ressort unter „ferner liefen” zu finden sind.

Auch taz schlägt die in die gleiche Kerbe wie ich vor ein paar Tagen – sehr erfreulich.

Ich bin mal gespannt wann der Herr Herrmann vorschlägt alle CSU-Stammtische zu verbieten.

Comments Off

Die „Nürnberger Nachrichten” berichten in ihrer Ausgabe vom letzten Mittwoch über die 16-Jährige, die einen Amoklauf verüben wollte und durch Zufall gestoppt wurde. Ihr wird jetzt der Prozess gemacht.

Große Medienaufmerksamkeit hat die Sache nicht bekommen. Vermutlich weil sie unterm Strich niemanden umgebracht hat – für einen Amoklauf ein erbärmliches Ergebnis und die Öffentlichkeit interessiert sich nicht für Versager (wenn es keine Nacktbilder von ihnen gibt). Außerdem passt das Mädel nicht in das etablierte Täterbild, denn, so schreiben die „Nürnberger Nachrichten”:

„Anders als Täter in anderen Amok-Fällen war die Einser-Schülerin nicht besessen von Gewaltspielen am Computer.”

Stattdessen gelten „persönliche Schwierigkeiten” als Hauptmotiv, denn:

„Sie habe offensichtlich massive Probleme mit Mitschülern, Lehrern und ihren Eltern gehabt.”

So, die anderen Amokläufer waren also alle „besessen von Gewaltspielen”. Was ist denn mit dem 41-Jährigen Amerikaner vietnamesischer Abstammung, der im April 2009 13 Menschen erschossen hat und dann Selbstmord beging? Der hat kurz vor seinem Amoklauf noch schnell einen Abschiedsbrief an einen Fernsehsender geschickt. Ich bin kein Psychologe, aber meines Erachtens war der Typ hochgradig paranoid. Von Undercover-Agenten, die während er schläft in seine Wohnung eindringen und ihn anfassen, ist da die Rede, und dass man versucht hat ihn in Verkehrsunfälle zu verwickeln. Besessen: ja. Computerspiele: nicht so wirklich.

„Ja, aber …”, wäre jetzt eine erwartete Reaktion, „… du suchst dir jetzt halt Beispiele zusammen die deine Aussage unterstützen!”. Nun, bisher habe ich noch keine Aussage gemacht, sondern die Aussagen anderer Leute überspitzt ironisch zitiert. Von den letzten vier Amokläufen, von denen ich in der Zeitung gelesen habe, waren das zwei. Die anderen beiden sind die aus Erfurt und Winnenden. Beide Täter waren jugendlich (17 und 19 Jahre alt), männlich und haben Counter Strike gespielt. Der Eine hatte außerdem massive schulische Probleme (er wurde ohne Abschluss rausgeschmissen), litt an maßloser Selbstüberschätzung, hatte eine eindeutige Waffenaffinität und schrieb ein Drehbuch zu einem Gewaltfilm („so drastisch wie möglich” stand da drin, zum Beispiel). Der Andere hatte schulische Probleme (er wurde gemobbt), war in psychiatrischer Behandlung schoss mit den Waffen seines Vaters im Keller und im Wald rum.

Die Auswahl ist im übrigen echt willkürlich: Jedes Jahr geschehen (weltweit) mehrere Amokläufe, so 2–3 durchschnittlich. Da Fälle von 2006 anzusprechen wirkt absurd. Aber die nicht-deutschen Fälle werden so gut wie nie mit Computerspielen in Verbindung gebracht. Ob und, falls ja, wie viel die Täter gespielt haben ist schlicht und ergreifend nicht bekannt.

Und nun zu einer Multiple-Choice-Aufgabe, Statistik, 1. Semester:

Aus den oben gemachten Beobachtungen geht mit großer Wahrscheinlichkeit hervor (zwei zutreffend):

1. Amokläufer haben psychische Probleme und/oder ihr Leben nicht im Griff.
2. Gewalt in Computerspielen führt zu Amokläufen.
3. Computerspiele werden hauptsächlich von männlichen Jugendlichen gespielt.
4. Paintball spielen führt zu Amokläufen.

Meiner Meinung nach kommt es zu Amokläufen, wenn sich psychisch nicht ganz sattelfeste Personen in Gewaltfantasien flüchten. Wenn sie zu Hause das Bombelnbasteln anfangen oder mit Knarren im Wald rumballern – das ist so der Zeitpunkt um professionelle Hilfe zu holen. Wenn diese Menschen dann noch Computerspiele spielen, hilft ihnen das vermutlich nicht im Geringsten ihre Aggressionen abzubauen. Aber diese Spiele sind ein Symptom, nicht der Auslöser. Wenn man sich die Biographie aller mir bekannter Amokläufer anschaut (die mit Computerspielen in Verbindung gebracht wurden), dann habe ich bisher noch nie folgenden Ablauf gesehen: „Kontakt mit Computerspiel mit xy Jahren. Dadurch geht Leben vor die Hunde. Amoklauf.” Was man hingegen immer wieder liest, ist: „Leben geht vor die Hunde. Fühlt sich ungerecht behandelt und machtlos. Gewaltphantasien. Computerspiele. Amoklauf.”

Was mich stört ist die Darstellung von Computerspielen in der Öffentlichkeit. Dass Politiker in ihrem verblödeten Aktionismus ein einfaches und wählerstimmen-neutrales Opfer suchen ist ärgerlich, überrascht aber auch nicht. Aber dass sich die Medien so zur Hure der Politik machen und dieses Bild, das den Aktionismus erst rechtfertigt, prägen, bringt mich auf die Palme.

Comments Off

I recently found an article in a German magazine which – for some unknown reason – felt it necessary to praise recursion. If you read enough introductory textbooks, you soon get the impression that there is only one problem ever solved using recursion: the Fibonacci sequence. And that article was no exception. Of course, the sequence really is nice to show how recursion works. It can be formulated as:
unsigned int fib (unsigned int n)
{
  if (n < 2)
    return (n);
  else
    return (fib (n−1) + fib (n−2));
}
This is of course very short and elegant, but I think it’s a bad example for recursion in general, because this recursion is very inefficient. Code length and efficiency have nothing in common!
(more…)

Comments Off

Auf dem Verlorene-Generation-Blog bemerkt der Autor ketzerisch ganz richtig, dass es sich bei dem Stopp-Schild (Zeichen 206), das zum Symbol der staatlichen Zensur in Deutschland geworden ist, eigentlich um das falsche Verkehrszeichen handelt. Das dort vorgeschlagene „Einfahrt Verboten!”-Zeichen trifft den Sachverhalt schon deutlich besser.

Um den völlig inadäquaten Sperrmechanismen Rechnung zu tragen, bietet sich ein weiteres Zeichen an:

Zeichen 325: Beginn eines verkehrsberuhigten Bereichs

Zynische Grüße,
–octo

Comments Off

Vielleicht bin ich ja auch einfach nur latent paranoid, aber irgendwie find’ ich das beim Wählen schon immer wieder beunruhigend: Um meine Stimme abzugeben genügt (m)eine Wahlbenachrichtigungskarte – (m)einen Lichtbild-/Personalausweis wollte niemand von mir sehen. Von der Sicherheit her vergleichbar mit einem Passwort, das per E-Mail zugeschickt wird. Und auf der andren Seite sollen Betreiber von Internet-Cafés Ausweise kontrollieren. Wenn das so weitergeht kann ich bei der Bank bald ohne Identifikation Geld abheben, brauch für das Benutzen des ÖPNV aber ein polizeiliches Führungszeugnis…

Comments Off

This post is in German, since it talks about a local wireless LAN network project.

Vor ein paar Wochen haben Sebastian und ich zu einer Gruppe Kontakt aufgenommen, die ein Freifunk-Netzwerk in Nürnberg, Fürth und Erlangen aufbauen wollen. Der Name des Projekts ist Freifunk Franken (FFF).

Bei Freifunk handelt es sich eine Initiative zur Schaffung von Mesh-Networks (die holprige deutsche Übersetzung, „vermaschte Netzwerke”, mag ich nicht) mittels Wireless-LAN, also Funk-Netzwerke ohne direkte zentrale Verwaltung. Realisiert wird das mit OpenWrt und olsrd, das ein Link-state routing protocol implementiert.

Graph eines Mesh-Netzwerks mit vier Knoten

Meines Erachtens gibt es exzellente Gründe sich daran zu beteiligen:

1. Persönlicher Spieltrieb

Wem derartige Gründe, obwohl großartig, nicht ausreichen, der darf sich auch warum und mollig fühlen bei dem Gedanken „sein Internetz” zu teilen oder kann darauf spekulieren, demnächst das Freifunk-Netz auch von wo anders aus nutzen zu können.

Für wen die Geschichte interessant klingt, den möchte ich herzlich einladen das Projekt und insbesondere die Leute mal kennen zu lernen. Wir treffen uns jeden Dienstag ab 19 Uhr im K4 in Nürnberg (gleich beim Bahnhof). Das Bier ist aus Weißenohe! Eine Webgeschreibung gibt’s natürlich auch.

Comments(0)

The authors of libtool have decided to make some backwards incompatible changes. Therefore, the version number has changed from 1.5 to 2.0 – exactly how it should be. I hate libtool for a variety of reasons, but this in this respect the authors made everything right, in my opinion.

But as soon as one group is doing something right, another has to fuck up. Instead of creating a libtool2 package, the maintainer of the Debian package decided to just upgrade the existing libtool package. (The Debian people have this weird philosophy that having many packages is bad for mirror admins and therefore rather create a big mess than add a couple more packages…) This means that you can install either version 1.5 or version 2.0 – but not both at the same time.

So if you’re involved in a couple of projects, some require libtool 1.5 and some require libtool 2.0 (supporting both is hard; kudos to Sebastian for figuring out how to do it and implement this for collectd), you will have to chose what projects you want to continue working on or set up a second box with the other libtool version.

As an “amusing” side note: libltdl3-dev does not depend on libtool < 2 nor doeslibltdl-dev depend on libtool >= 2. Removing the version number from the development package is, as far as I know, according to the Debian guidelines, so that you can have this awesome situation (having to chose which version to install) more often! Because people, who want to support multiple versions of a library, are probably a statistical anomaly or something…

*sigh*

Comments(58)

The idea has been around for a while – as a matter of fact verification and encryption of data has been mentioned in the design goals for collectd 4 – but so far nobody has had enough pain to do anything against the unsecured transmission of data. My favorite solution, asymmetric cryptography using Datagram Transport Layer Security (DTLS), is still not possible because GnuTLS doesn’t implement it and OpenSSL has a GPL-incompatible license.

Recently Thorsten von Eicken of RightScale approached me and offered to sponsor development in this direction. So last night I finally set to work and implement some means of security for the network protocol. It’s a symmetric schema based on libgcrypt (which has a nice, straight forward interface, btw.) using a shared secret.

There are three security levels which have slightly different (but related) behavior on clients and servers:

• Encrypt
  Client: Encrypt outgoing data using AES-256 and a shared secret. Integrity of encrypted data is ensured by a SHA-1 hash.
  Server: Only accept encrypted messages.
• Sign
  Client: Sign outgoing messages using HMAC-SHA-256 and a shared secret.
  Server: Accept signed and encrypted packets.
• None
  Client: Send data without any secutiry measures. (Plain-text doesn’t quite fit since it’s a binary protocol ;)
  Server: Accept (almost) everything. If a shared secret is configured, encrypted packets are decrypted and signed packets are rejected if the HMAC is incorrect.

The security level and the (possibly) required shared secret can be set per socket so that proxies can pass data between different (logical) domains.

The entire code is still pretty much a moving target, but if you want to give it a try check out the master branch from our Git repository and make sure libgcrypt is installed.

Comments(61)