Linux @ Home

ggT / gcd, wer kann’s am Kürzesten? Diese Frage, tauchte auf, nachdem ich versuchte, den grössten gemeinsamen Teiler aus Lust und Laune in ein paar Programmiersprachen zu implementieren (und einige male kläglich scheiterte). Von der Auswahl ausgenommen sind esoterische oder „unleserliche“ Sprachen (APL) und natürlich solche, die eine gcd-Funktion bereits in den Bibliotheken haben. Unter diesen Gesichtspunkten gewinnt hier relativ klar Forth! Irgendwie überraschend (aber beim zweiten Nachdenken doch nicht mehr so überraschend), dass eine Programmiersprache aus den Sechzigerjahren des vorigen Jahrhunderts so unglaublich effizient im Ausdruck ist:

: gcd ( a b -- n )
  begin dup while tuck mod repeat drop ;

Zugegeben, ohne genau zu wissen, was tuck macht, ist es etwas schwierig zu verstehen, aber das Prinzip der wiederholenden Modulo ist schon klar zu erkennen.
Aufrufe dieser Funktion macht man dann in etwa so:

142864 24 gcd . 8

oder pro Linie ein Argument (da merkt man deutlich, dass Forth nur auf einem Stack arbeitet):

14361672
649981417530
gcd
. 1446

Wer dies unbedingt austesten will, sollte sich gforth (GNU) installieren. Für Fans der UPN: In Forth rechnet man aufgrund des Stacks natürlich mit der umgekehrten polnischen Notation:

5 3 + 7 2 + * .

(mit dem Punkt holt man sich das letzte Resultat vom Stack, quasi ein pop). Natürlich gibt es auch andere Kandidaten, die zumindest ähnlich kurz sind, aber meines Erachtens ist Forth noch die bekannteste (ich habe jedenfalls noch nie was von K oder Joy gehört). Interessanterweise bietet auch gnuplot eine Lösung dafür an. Ich weiss nicht, ob man Gnuplot zu den Turing-vollständigen Sprachen zählt, deshalb ausser Konkurrenz:

gcd (a, b) = b == 0 ? a : gcd (b, a % b)

Ach ja, der Preis für die längste Implementierung von gcd geht an SED (ein Streaming-Editor von Unix, der eigentlich nie als Programmiersprache gedacht war), den Sourcecode kann man sich bei rosettacode.org angucken

Zugegeben, ich verstand den Boyer-Moore Algorithmus nicht ganz, was alleine schon ein Grund war, eine einfachere Variante zu implementieren. Der Boyer-Moore-Horspool ist so eine Variante. Glücklicherweise zeigt sich, dass die Horspool-Vereinfachung die Textsuche im durchschnittlichen Fall nicht oder nicht viel langsamer werden lässt (rein subjektive Einschätzung!). Neugierige sollten den Code 1:1 kopieren und verwenden können mit einem beliebigen Java-Compiler. Und bitte einfach den Programmierstil ausblenden, es ging mir nur darum, den Algorithmus zu testen und wenigstens halbwegs zu verstehen. Heute braucht man sich kaum mehr selber um Implementierungen von Suchalgorithmen zu bemühen, die meisten Programmierumgebungen bringen entsprechende Bibliotheksfunktionen seit vielen Jahren mit.

public class BoyerMooreHorspoolSearch {
	private char[] text;
	private int text_len;
	private static final int ALPHABET_SIZE = 256;
 
	public BoyerMooreHorspoolSearch() {
		String str = "overeovere The oxen-brown Fox jumped over the Fox-lake. It (fox) didn't" +
				" know why, but it was kinda fun overemphasized! xxxxxxxxxxx aaaaaaa";
		this.text = str.toCharArray();
		text_len = text.length;
		System.out.println("DEBUG: text_len: " + text_len);
	}
 
	public BoyerMooreHorspoolSearch(String text) {
		this.text = text.toCharArray();
		text_len = this.text.length;
	}
 
	private void search(final String pattern) {
		char[] pat = pattern.toCharArray();
		int pat_len = pat.length;
		int[] occurrenceTable = initOccurrence(pat);
		int pos = 0; // our text index position
		int countloops = 0;
 
		while (pos <= text_len-pat_len) {
			int j = pat_len-1; // our pattern index position
			// As long as the pattern chars are hits (we start at the
			// end of the pattern) => go one backwards (to the left).
			while (j >= 0 && pat[j] == text[pos+j]) j--; // hits
			if (j < 0) report(pattern, pos);
 
			// We get here, when: a) a full hit was found
			// and b) nothing was found or partially pattern was found
			// in either case, we have to check, how far to the right we
			// can jump now.
			//
			// Now we do this in one step: take the jump-length from
			// the occurrenceTable indicating pat_len, if the character
			// of the current pos in text is _not_ in the pattern and
			// giving the difference from the right to the rightmost character
			// in the pattern, if the character at pos in text _is_ in our
			// pattern
			pos += occurrenceTable[text[pos+pat_len - 1]];
			countloops++;
		}
		System.out.println("DEBUG: Loops: " + countloops);
	}
 
	private int[] initOccurrence(final char[] pat) {
		int[] occurrenceTable = new int[ALPHABET_SIZE];
		char a;
		int pat_len = pat.length;
 
		for (a = 0; a < ALPHABET_SIZE; a++)
			occurrenceTable[a] = pat_len;
 
		// We fill the table at the position of the ASCII char
		// (for example occurrenceTable[97] for 'a') with the
		// index value of it's last occurrence in the pattern.
		for (int j = 0; j < pat_len-1; j++)
			occurrenceTable[pat[j]]=pat_len - j - 1;
 
		return occurrenceTable;
	}
 
	private void report(final String pat, final int pos) {
		System.out.println("Found \"" + pat + "\" at position "
				+ (pos+1) + " (index " + pos + ") in the text!");
	}
 
	// Driver
	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		BoyerMooreHorspoolSearch bmh = new BoyerMooreHorspoolSearch("Is there a fox?");
		BoyerMooreHorspoolSearch bmh = new BoyerMooreHorspoolSearch();
 
		bmh.search("Fox");
		bmh.search("fox");
		bmh.search(" fox"); // this should _not_ be found
		bmh.search("ox");
		bmh.search("xxx");
		bmh.search("overe");
	}

Puppet ist seit Jahren im Aufwind und entwickelt sich zum Nonplusultra im professionellen Konfigurationsmanagement. Es ist schon längst nicht mehr nur die “Alternative zu cfengine” die es anfangs noch war. Die Liste der Firmen, die seit längerem und im grossen bis sehr grossen Umfang (bis zehntausende von Servern oder Instanzen) auf Puppet setzen ist beeindruckend, darunter finden sich unter anderem Google, Twitter, Red Hat, Sun, Citrix, match.com, Rackspace etc. Wegen der ausgezeichneten Reputation von Puppet und der möglichen Vollautomatisierung (ein heiliger Gral von Systemadministratoren, leider wird dies manchmal eher als Bedrohung ihres Jobs wahrgenommen) entschieden wir uns für eine Evaluation dieser Software. Der Preis für die Flexibilität und die überragende Mächtigkeit dieses Instruments ist allerdings am Anfang ziemlich hoch: Nicht wegen dem Kaufpreis, es handelt sich ja um Opensource, aber die Lernkurve ist am Anfang wirklich sehr steil. So steil, dass ich mich die erste Woche mehr als einmal gefragt habe: Sollen wir wirklich? Lohnt sich das überhaupt für unsere 20 Linux-Server? Vielleicht ist es gar nicht so schlecht, dass die Einstiegshürde so hoch ist, damit wird sichergestellt, dass sich nur eingehend damit beschäftigt, wer genau weiss, was er tut (das ist auch bei Linux-Administratoren nicht automatisch der Fall und was genau mit dem Werkzeug erreicht werden soll.

Nach zwei Wochen intensiven Lernens (Meistens “Learning by doing”, denn praktisch alle  Puppet-Bücher sind nicht wirklich brauchbar) ist die Antwort Ja. Ja, und es würde sich sogar nur mit 10 Servern bereits lohnen. Denn nach dem hohen Lernaufwand am Anfang wird das Erstellen von neuen Modulen und Konfigurationen immer einfacher und schneller. Es macht Spass, ein derartig mächtiges Werkzeug immer besser zu beherrschen. Zudem gibt es eine Unmenge von vorgefertigten Modulen auf den entsprechenden Internetseiten zu finden. Und nicht zuletzt lernt man sehr viel über deklarative Sprachen und wenn man will, kann man zugleich noch etwas Ruby Programmieren lernen, je nachdem wie tief man in die Materie eintauchen möchte.

Einen anständigen Workflow vorausgesetzt kommt man unter Umständen auch intensiv mit Git in Kontakt, was einem den zukünftigen Umgang mit diesem ebenfalls sehr mächtigen Versionierungswerkzeug in anderen Projekten sehr einfach macht (Projektleiter, ob kommerziell oder Opensource sind froh, wenn sie nicht erst einen Kurs in “Git basics” geben müssen). Als kleiner Bonus wird durch den Workflow auch ein Produktionsrelease-Zyklus eingaführt mit Test und Live-Szenarien, ohne die sonst üblichen Probleme eines Paradigmen- oder Prozesswechsels (Akzeptanz u.ä.), denn die ersten Früchte der Arbeit werden sehr schnell auch individuell spürbar. Für vorsichtigere Naturen lohnt sich bestimmt ein Blick auf die Enterprise-Version, mit der die Installation vollautomatisch auf Klick funktioniert und für die man auch offiziellen Support bekommt.

Warum scheuen dennoch viele Administratoren den Weg in die Vollautomatisierung? Bei einigen herrscht wohl noch die altbekannte Angst vor dem Überflüssigwerden des Administrators vor. Dies lässt sich in der Welt der proprietären Betriebssysteme und Software (aber nicht nur dort) sehr häufig beobachten, wo selbst einfachste, repetierbare Aufgaben teilweise Stunden benötigen. Mein Argument gegen diese Angst ist, dass wir unseren Job nicht machen, um langweilige, wiederholende und im Prinzip immergleiche Arbeiten zu machen. Dazu kann man auch Roboter (sprich: Puppet) nehmen! Als Systemadministrator / Entwickler etc. hat man genug zu tun, kreative und nachhaltige Lösungen für nicht-alltägliche Probleme zu finden. Diese Arbeit ist essentiell das, was uns  implizit motiviert! Typische Situation: Die ersten 10 Apache-Installationen macht man noch gerne, weil man lernt und das Ergebnis sehen kann. Danach merkt man schnell, dass es immer dasselbe ist. Warum also nicht automatisieren? Jeder Systemadministrator den ich kenne, hat eine Liste mit 100+ interessanteren Problemen und Ideen, welche ihrer Firma einen echten Mehrwert bieten würden, wenn man denn neben den alltäglichen Aufgaben Zeit für sie fände. Deshalb ist Automatisierung keine Bedrohung sondern eine Befreiung! Sobald man mit vielen Servern zu tun hat, muss man sich ohnehin überlegen, wie man diese effizient und nachvollziehbar gleich aufsetzen und administrieren will, daher ist in grösseren Firmen diese Form der Automatisierung schon eher ein Sachzwang, will man motivierte und kreative anstatt genervte Administatoren.

Im Gegensatz zu cfengine besteht derzeit leider noch keine offizielle Windows-Unterstützung. Es sind jedoch Entwicklungen im Gange, dass bald die wichtigsten Ressourcen durch einen Windows-Agent realisiert werden können.

In diesem Sinne gelte das alte Administratoren-Credo: Wenn eine Arbeit automatisch erledigt werden kann, soll man keinen Menschen damit belästigen. Denn Menschen haben Interessanteres zu tun.

Shellskripte müssen nicht zwangsläufig an die Shell in der Konsole gebunden sein. Sie können auch ansprechend verpackt werden für Otto Normaluser. Dazu gibt es verschiedenste Ansätze. Einer der modernsten und flexibelsten ist kdialog unter KDE4. Das Besondere an kdialog ist seine Fähigkeit zur Interprozess-Kommunikation (IPC) via DBus. DBus wurde von freedesktop.org entwickelt und ist mittlerweile bei fast allen Distributionen standardmäßig vorhanden. In KDE 3 kam dafür das KDE-eigene DCOP zum Einsatz. Noch früher in KDE 1 wurde eine Corba-Implementiereung verwendet. Beide Lösungen waren jedoch zu gross und umständlich.

Mein Beispielskript hier zeigt, wie man einen Fortschrittsbalken implementiert, welcher via DBus vom laufenden Shellskript gesteuert werden kann. Natürlich kann man via DBus noch viele weitere mehr oder weniger nützliche oder witzige Dinge machen mit dem jeweiligen Dialog, wie z.B. den Titel und Inhalt laufend verändern etc.

Solche Skripte müssen übrigens nicht auf KDE beschränkt sein. Es sollte schon mittels installierten kdelibs und natürlich kdialog möglich sein, dieselben unter Gnome, XFCE etc.laufen zu lassen, obwohl dort der Einsatz von zenity (GTK-basiert) eher angebracht wäre. Zenity ist praktisch in jeder Distribution installiert. Nur Leider fehlt dort der Progress-Callback resp. die Interprozess-Kommunikation. Zenity’s Progressbar ist dadurch eher eine simple Aktivitätsanzeige. Allen Alternativen zu kdialog ist gemein, dass sie die erwähnte Progressbar lediglich indirekt implementieren, z.B. indem sie die Prozentwerte des Balkens entgegennehmen oder die Aktivität während einer Operation anzeigen, Beispiel:

find /usr/bin | zenity --progress --pulsate

Durch die Verwendung von DBus können wir vielleicht bald auf eine wirklich Desktopunabhängige Lösung hoffen, indem z.B. auch zenity die Dialoge über DBus ansteuerbar macht…

Natürlich halten damit auch wieder die sleep-Anweisungen Einzug, damit nicht alle Text vorbeihuschen. Sie verlangsamen den Ablauf zwar insgesamt, aber bei einem Prozedur wie “USB-Stick entschlüsseln und einhängen” ist dies meines erachtens vernachläßigbar zu gunsten der Lesbarkeit der Infotexte.

#!/usr/bin/env bash
 
# TODO: Dieses Skript sollte durch das udev-System aufgerufen werden
# siehe dazu /etc/udev/rules.d/90-crypto-usb-stick.rules
 
USER=myuser
DEVICE=/dev/usbstick
MAPPERDIR=/dev/mapper/crypto_usbstick
MOUNTDIR=/media/crypto_usbstick
 
dbusRef=$(kdialog --title "Crypto-USB-Stick aktivieren und einhängen" --progressbar "Starte..." 2)
sleep 1
 
if ! kdialog --password "Bitte Passwort für Crypto-USB-Stick eingeben:" | cryptsetup luksOpen $DEVICE ${MAPNAME}; then
    kdialog --error "Konnte das Cryptodevice nicht erstellen! Vermutlich falsches Passwort eingeben?"
    qdbus $dbusRef org.kde.kdialog.ProgressDialog.close
    exit 1
fi
sleep 1
 
qdbus $dbusRef org.kde.kdialog.ProgressDialog.setLabelText "Verzeichnis $MOUNTDIR wird gesucht"
if [ ! -e $MOUNTDIR ]; then
    qdbus $dbusRef org.kde.kdialog.ProgressDialog.setLabelText "Verzeichnis $MOUNTDIR wird erstellt"
    mkdir $MOUNTDIR
fi
qdbus $dbusRef Set org.kde.kdialog.ProgressDialog value 1
sleep 1
 
qdbus $dbusRef org.kde.kdialog.ProgressDialog.setLabelText "Cryptodevice wird nach $MOUNTDIR eingehängt"
if ! mount $MAPPERDIR $MOUNTDIR -orw,user,exec,uid=$USER,gid=$USER; then
    kdialog --error "Konnte den Crypto-USB-Stick nicht in $MOUNTDIR einhängen!"
    qdbus $dbusRef org.kde.kdialog.ProgressDialog.close
    exit 1
fi
sleep 1
 
qdbus $dbusRef Set org.kde.kdialog.ProgressDialog value 2
qdbus $dbusRef org.kde.kdialog.ProgressDialog.setLabelText "Vorgang erfolgreich beendet!"
sleep 2
 
qdbus $dbusRef org.kde.kdialog.ProgressDialog.close

Perl 5.10 ist nun bereits eine Weile draussen und hat Einzug auf die gängigen Linux-Distributionen gehalten. Aus diesem Grunde möchte ich an dieser Stelle einen kleinen Reminder bringen, welche Features für den Programmieraltag wirklich der Rede Wert sind. Viele der Neuerungen sind Backports aus der Designarbeit an Perl 6.

Da dies keine Einführung in Perl darstellt, sondern eine Info an Cracks, Admins und solche die es werden wollen, gehe ich nicht auf die Details ein. Ich schlage vor die Code-Beispiele jeweils in die Kommandozeile zu kopieren und zu damit herum zu spielen.

Wenn man die neuen Features benutzen will muss man dies im Skript deklarieren.

use feature ':5.10';

Continue reading…