🏷️ dfde  🏷️ tech  🏷️ programming  🏷️ linux 
📆 01.08.2024

Bibliothek für Quellcodeverleih

Entwicklung und Verwendung einer Shared Library für Primfaktorzerlegung in C

In einem früheren Artikel habe ich gezeigt, wie man Zahlen auf dem DAMPF-Stack in ihre Primfaktoren zerlegt. Die Performance war in der PHP-Implementierung weder mit mod_php noch mit PHP-FPM als Laufzeitumgebung berauschend.

Besinnen wir uns also auf das gute, alte C und verzichten wir für einmal auf das Web! Doch wie können wir die Programmlogik dennoch wiederverwendbar machen, zumal wir auf das Web als Deployment-Mechanismus verzichten müssen? Hierzu soll eine sogenannte Shared Library verwendet werden!

factorizer: Ein Programm zum Faktorisieren von Primzahlen

Zunächst einmal soll ein C-Programm zur Faktorisierung von Primzahlen geschrieben werden. Zur Faktorisierung müssen als erstes Primzahlen bis zu einer bestimmten Obergrenze gefunden werden können:

int *primes_up_to(int x)
{
    int i = 0, j = 0;
    int *primes = NULL;

    if (x < 2) {
        primes = (int *)malloc(sizeof(int));
        primes[0] = 0;
        return primes;
    }

    primes = (int *)malloc(sizeof(int) * x);
    memset(primes, 0, x);

    for (i = 2, j = 0; i <= x; i++) {
        if (is_prime(i)) {
            primes[j++] = i;
        }
    }

    return primes;
}

bool is_prime(int x)
{
    if (x < 2) {
        return false;
    }
    for (int i = 2; i <= x / 2; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

Dies bewerkstelligt die Funktion primes_up_to zusammen mit der Hilfsfunktion is_prime. Der grösste Unterschied zur PHP-Implementierung ist das Memory-Management: Da ein Array von Primzahlen zurückgegeben werden soll, muss hierfür mit malloc Platz reserviert werden. Da es schwer abzuschätzen ist, wie viele Primzahlen bis zur Obergrenze auftauchen werden, wird einfach Platz für x Primzahlen reserviert. Das Array ist 0-terminiert, wodurch ein Element am Ende benötigt wird ‒ Platz ist ja genug da. Die Elemente werden einfach alle mit 0 initialisiert. Wird eine unsinnige Obergrenze (x < 2) verlangt, wird einfach ein Array bestehend aus dem 0-Element zurückgeliefert. Der Aufrufer kann dann über die Ergebnisse iterieren, bis der Wert 0, der ja bekanntlich keine Primzahl ist, erreicht worden ist.

Auch die Faktorisierung einer einzelnen Zahl wurde sehr ähnlich wie in PHP gelöst:

int *factorize(int x)
{
    int i = 0, j = 0, n = 0;
    int *primes = NULL, *factors = NULL;

    if (x < 1) {
        factors = (int *)malloc(sizeof(int));
        factors[0] = 0;
        return factors;
    }

    n = log2(x) + 1; // heuristic: log2(16) = 4, fits "worst" case  [2, 2, 2, 2]
    primes = primes_up_to(sqrt(x));
    factors = (int *)malloc(sizeof(int) * (n + 1));
    memset(factors, 0, n + 1);

    for (i = 0, j = 0; primes[i] != 0 && x > 1;) {
        if (x % primes[i] == 0) {
            factors[j++] = primes[i];
            x /= primes[i];
        } else {
            i++;
        }
    }
    if (x > 1) {
        factors[j] = x;
    }
    free(primes);

    return factors;
}

Auch hier spielt das Memory-Management wieder eine Rolle. Da man a priori nicht weiss, in wie viele Primfaktoren eine Zahl zerlegt werden kann, muss eine Heuristik beigezogen werden. Im “schlimmsten” Fall, d.h. bei Zweierpotenzen wie 32 oder 1024, wird ein Array von 2en ‒ der kleinsten Primzahl ‒ zurückgegeben. Die Anzahl der 2en kann mit dem 2er-Logarithmus berechnet werden. So erhalten wir von einer Zahl x maximal log2(x) Primfaktoren. Ein weiteres Element für die 0-Terminierung wird ebenfalls angefügt.

Weiter müssen die gefundenen Primzahlen nach der Faktorisierung mit free wieder entsorgt werden. (Da wir eine Library schreiben, wissen wir nicht, wie unser Code verwendet werden wird. Soll er in einem langlaufenden Serverprozess zum Einsatz kommen, darf auf keinen Fall Memory geleaked werden.)

Das Programm zur Faktorisierung sieht dann folgendermassen aus:

#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool is_prime(int);
int *primes_up_to(int);
int *factorize(int);

int main(int argc, char *argv[])
{
    int lower = 0, upper = 0, i = 0, j = 0;

    if (argc < 3) {
        fprintf(stderr, "usage: %s [lower] [upper]\n", argv[0]);
        return 1;
    }

    lower = atoi(argv[1]);
    upper = atoi(argv[2]);
    if (lower > upper) {
        fprintf(stderr, "[lower] must be <= [upper], was %d > %d\n", lower, upper);
        return 1;
    }

    for (i = lower; i <= upper; i++) {
        printf("%d: ", i);
        int *factors = factorize(i);
        for (j = 0; factors[j] != 0; j++) {
            printf("%d ", factors[j]);
        }
        free(factors);
        putchar('\n');
    }

    return 0;
}

Der Benutzer muss das Programm mit einer Unter- und Obergrenze aufrufen ‒ und wird über einen falschen Gebrauch über stderr informiert. Das Programm wird mithilfe von einem Makefile gebaut (hierzu sollte das Debian-Paket build-essential installiert sein):

factorize: factorize.c
	gcc -Wall -std=c99 $^ -lm -o $@

Das Programm factorize wird anhand des Quellcodes in factorize.c gebaut. Mit -Wall werden alle Warnungen angezeigt. Es wird der Standard C99 mit -std verwendet. Die Variable $^ beinhaltet eine Liste aller Abhängigkeiten; hier ist das bloss factorize.c. Mithilfe von -lm wird die Mathematik-Library (math.h) dynamisch zugelinkt. Die Ausgabe findet mit dem Parameter -o und der automatischen Variable $@ in die Datei factorize statt.

Das Programm kann folgendermassen gebaut und ausgeführt werden:

$ make
gcc -Wall -std=c99 factorize.c -lm -o factorize

$ ./factorize 10 20
10: 2 5
11: 11
12: 2 2 3
13: 13
14: 2 7
15: 3 5
16: 2 2 2 2
17: 17
18: 2 3 3
19: 19
20: 2 2 5

Die erste Spalte zeigt die Zahlen des gewünschten Bereichs an; in der zweiten Spalte werden dann die Primfaktoren dargestellt.

libfactorizer.so: Eine Programmbibliothek zur Faktorisierung von Primzahlen

Zwar läuft das Programm korrekt, doch lassen sich die eigentlichen Berechnungsfunktionen nicht in einem anderen Kontext wiederverwenden, etwa in einem CGI-Programm, welches andere Anforderungen an Eingabe/Ausgabe stellt als ein Kommandozeilenprogramm.

Die wiederverwendbaren Funktionen sollen darum in eine Shared Library ausgelagert werden, gegen die dann ein Anwendungsprogramm gelinkt werden kann. Dies würde u.a. auch die Aktualisierung oder Ersetzung der Library erlauben, ohne dass das Anwendungsprogramm neu kompiliert werden müsste.

Zuerst sollen die Funktionsdeklarationen in eine Header-Datei factorize.h ausgelagert werden:

#ifndef factorize_h
#define factorize_h

extern int *factorize(int);
extern int *primes_up_to(int);
extern bool is_prime(int);

#endif

Hier gibt es zwei Unterschiede zur bisherigen Deklaration:

  1. Alle Definitionen sind in das Präprozessor-Paar #ifndef/#endif eingeschlossen. Die ganzen Deklarationen sollen nur ausgeführt werden, wenn das Symbol factorize_h noch nicht definiert ist, welches dann sogleich mit den Deklarationen zusammen definiert wird. (Das verhindert Mehrfachdeklarationen, wenn ein grösseres Programm die gleiche Header-Datei mehrmals einfügt.)
  2. Die Funktionen sind mit dem Schlüsselwort extern deklariert. Dies weist den Compiler darauf hin, dass die Funktion in einer externen Library zu finden ist, die später dazugeklinkt wird.

Die Funktionen sind dann in einer etwas reduzierten Datei factorize.c abgelegt (hier gekürzt wiedergegeben):

#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

#include "factorize.h"

int *factorize(int x)
{
    // ...
}

int *primes_up_to(int x)
{
    // ...
}

bool is_prime(int x)
{
    // ...
}

Die Deklarationen werden aus der Header-Datei factorize.h herangezogen. Die Funktion main fehlt hingegen. Diese wurde in eine separate Datei main.c ausgelagert, die nicht zur Library gehört, sondern diese bloss verwendet (hier auch gekürzt wiedergegeben):

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

#include "factorize.h"

int main(int argc, char *argv[])
{
    // ...
}

Bauen der Programmbibliothek

Aus der Datei factorize.c soll nun eine Bibliotheksdatei namens libfactorize.so erstellt werden. (Das Präfix lib ist eine Konvention, auf die sich der Linker zum Auflösen der Abhängigkeiten verlässt.) Die Kompilierung erfolgt in zwei Schritten, welche im Makefile definiert werden:

libfactorize.so: factorize.o
        gcc -shared $^ -o $@

factorize.o: factorize.c
        gcc -c -Wall -fpic $^ -o $@

Das untere Target factorize.o ist eine Objektdatei, welche einen Zwischenschritt zur Library darstellt. Der Compiler wird mit dem Flag -c aufgerufen, welches ihn anweist, das Programm nur zu kompilieren und nicht zu linken. Das Flag -fpic sorgt dafür, dass position-independent code (PIC) generiert wird: Code, der nicht davon abhängig ist, an welchen genauen Adressen die Instruktionen zu liegen kommen. (Es werden relative statt absolute Offsets für Adressen verwendet.) Diese Option ist für eine externe Programmbibliothek sehr wichtig. (Für ausführbare Programme existiert die -fpie-Option analog dazu.)

Das obere Target libfactorize.so ist die fertig gelinkte Library, welche auf Basis des Targets factorize.o erstellt wird. Hier ist das Flag -shared wichtig, das dafür sorgt, dass das Ergebnis von anderen Programmen verlinkt werden kann.

Die Library wird folgendermassen kompiliert:

$ make libfactorize.so
gcc -c -Wall -fpic factorize.c -o factorize.o
gcc -shared factorize.o -o libfactorize.so

Nun soll das Programm factorize auf Basis von main.c und der Library libfactorize.so gebaut werden, wozu ein weiteres Target im Makefile definiert wird:

factorize: main.c libfactorize.so
        gcc -L./ -Wall $^ -lfactorize -lm -o $@

Da sich die Library im gleichen Verzeichnis befindet, wird der Suchpfad hierfür mit dem Flag -L als ./ angegeben. Wichtig ist auch das Flag -lfactorize, welches die Library libfactorize.so (l wird zu lib erweitert) hinzulinkt, wie es auch mit der libm (für math.h) passiert.

Das Ergebnis ist ein Anwendungsprogramm, das leider noch nicht funktioniert:

$ make factorize
gcc -L./ -Wall main.c libfactorize.so -lfactorize -lm -o factorize

$ ./factorize 10 12
./factorize: error while loading shared libraries: libfactorize.so: cannot open shared object file: No such file or directory

Library zur Ausführung finden

Die Library libfactorize.so kann offenbar nicht gefunden werden, obwohl sie im gleichen Verzeichnis liegt. Mithilfe von ldd(1) kann dies veranschaulicht werden:

$ ldd factorize
        linux-vdso.so.1 (0x00007ffea84ff000)
        libfactorize.so => not found
        libm.so.6 => /usr/lib/libm.so.6 (0x00007fc36079f000)
        libc.so.6 => /usr/lib/libc.so.6 (0x00007fc3605bd000)
        /lib64/ld-linux-x86-64.so.2 => /usr/lib64/ld-linux-x86-64.so.2 (0x00007fc3608b9000)

Die Library libfactorize.so kann ‒ im Gegensatz etwa zur libm.so.6 und zur libc.so.6 ‒ nicht gefunden werden.

Zur Laufzeit kann der Suchpfad für Libraries mithilfe der Umgebungsvariable LD_LIBRARY_PATH um weitere Verzeichnisse ergänzt werden:

$ LD_LIBRARY_PATH="./:$LD_LIBRARY_PATH" ./factorize 10 12
10: 2 5
11: 11
12: 2 2 3

Zwar könnte diese Umgebungsvariable per export-Anweisung für die ganze Shell-Session gesetzt werden, es gibt aber eine bessere Variante: Die Library soll systemweit auffindbar gemacht werden.

Library systemweit konfigurieren

Zunächst soll die Library an einen passenden Ort für die systemweite Verwendung verschoben werden und Lese-/Ausführungsberechtigungen für alle Benutzer erhalten:

$ sudo mv libfactorize.so /usr/local/lib/
$ sudo chmod 755 /usr/local/lib/libfactorize.so

Leider wird diese noch nicht von ldconfig(8) gefunden:

$ sudo ldconfig -p | grep factor

Der Suchpfad für Shared Libraries kann jedoch ergänzt werden. Entweder geschieht das in der Datei /etc/ld.so.conf, welche alle *.conf-Dateien eines Unterverzeichnisses einfügt:

include /etc/ld.so.conf.d/*.conf

So ist es sinnvoller, eine separate Datei in /etc/ld.so.conf.d/ anzulegen, etwa namens factorize.conf mit folgendem Inhalt:

/usr/local/lib/

Der Library-Cache muss neu aufgebaut werden, damit die Änderung greift:

$ sudo ldconfig
$ sudo ldconfig -p | grep factor
        libfactorize.so (libc6,x86-64) => /usr/local/lib/libfactorize.so

Nun klappt’s auch mit der Auflösung der Library und der Ausführung des Programms:

$ ldd factorize | grep factor
        libfactorize.so => /usr/local/lib/libfactorize.so (0x00007f5c911e3000)

$ ./factorize 10 12
10: 2 5
11: 11
12: 2 2 3

Fazit

Ein in C geschriebenes Kommandozeilenprogramm zur Faktorisierung von Primzahlen wurde in eine Library und in eine Anwendung, welche diese Library verwendet, aufgeteilt. Die Organisation des Quellcodes und das Bauen der Artefakte wurden dadurch wesentlich komplizierter. Auch muss die Library auffindbar gemacht werden: Entweder bei der jeweiligen Ausführung, oder aber systemweit für alle künftigen Ausführungen. Der Vorteil, der darin besteht, dass nun verschiedene Programme auf die Funktionalität zurückgreifen können, wurde teuer erkauft. Doch kann sich dieser je nach Funktionsumfang der Library durchaus lohnen.

Übungen

Wer sich selber etwas mit C, Shared Libraries und dem ganzen Kompilier- sowie Konfigurationsvorgang einer Shared Library befassen möchte, kann sich an folgenden Übungen versuchen:

  1. Erstelle eine weitere Library namens libprime.so, welche die beiden Funktionen primes_up_to und is_prime beinhaltet. Die neue Library soll systemweit zur Verfügung stehen.
  2. Passe die bestehende Library libfactorize.so so an, dass sie nur noch die Funktion factorize enthält und anbietet. Diese soll entsprechend auf die neue Library libprime.so zurückgreifen.
  3. Baue das Anwendungsprogramm factorize auf Basis der neuen Libraries und stelle sicher, dass die Abhängigkeiten zur Laufzeit aufgelöst werden können.