» Visualisierung von Metriken in Voronoi-Diagrammen

May 22, 2016 | cpp development german math | Adrian Kummerländer

In der Analysis 2 Vorlesung meines Mathematik Studiums beschäftigen wir uns derzeit mit Normen und Metriken in endlich dimensionalen Vektorräumen, welche wiederum die Grundlage für die Übertragung der, aus Analysis 1 bekannten, Konvergenz und Stetigkeitsbegriffe in höhere Dimensionen schaffen. Während der Bearbeitung der entsprechenden Übungsblätter habe ich dabei nach Visualisierungsmöglichkeiten recherchiert, um eine bessere Intuition für diese Begriffe zu erlangen. Voronoi-Diagramme sind eine solche Möglichkeit, deren Grundlagen und Generierung ich in diesem Artikel zwischen Theorie und Praxis näher erläutern möchte.

Normen und Metriken in endlichdimensionalen Vektorräumen

In der herkömmlichen Schulmathematik sowie alltäglichen Rechnungen definieren wir Begriffe wie die Größe einer Zahl und den Abstand zwischen zwei Zahlen implizit über deren Betrag beziehungsweise die Differenz |ab| mit a,bR 1. Diese implizite, ja intuitive Definition der genannten Begriffe reicht für vieles aus, gelangt aber schnell an ihre Grenzen, wenn wir das Ganze, im Rahmen der mathematischen Arbeit des Beweisens, auf formale Grundlagen stellen und als Fundament für Aussagen in anderen Mengen als den herkömmlichen Zahlen nutzen wollen.

Mit nicht herkömmlichen Zahlen meine ich dabei Elemente aus Vektorräumen2 wie R2. Zumindest für diesen, mittels eines Kartesischen Koordinatensystems als zweidimensionale Ebene darstellbaren, Vektorraum, haben wir in der Schule eine Vorstellung bekommen. Dies trifft sich gut, da sich auch die Visualisierung von Metriken mittels Voronoi-Diagrammen in diesem Raum abspielen wird.

Betrachten wir zunächst den Begriff der Größe oder auch des Betrags einer Zahl. Dieser wird für Elemente eines Vektorraums, also Vektoren, über Normen beschrieben. Eine Norm ist dabei formal eine Abbildung :VR0, also eine Funktion, die Elementen aus einem K-Vektorraum V3 einen reellen Wert größer oder gleich Null zuordnet.
Diese Funktion darf dabei nicht vollkommen beliebig definiert sein, sondern muss für x,yV sowie αK die folgenden Bedingungen erfüllen:

Definitheit |x|=0x=0
Homogenität |αx|=α|x|
Dreiecksungleichung |x+y||x|+|y|

Diese Anforderungen bedeuten, dass eine Funktion genau dann als Norm gesehen werden kann, wenn sie nur den Nullvektor auf die reelle Null abbildet, Skalare analog zu linearen Ausrücken herausgezogen werden können und ein Umweg zwischen zwei Punkten nie kürzer ist, als der direkte Verbindungsweg.

Betrachten wir an dieser Stelle die Defintion der häufig verwendeten Klasse der p-Normen:

xp:=(ni=1|xi|p)1pmitxRn,pR1

Beachtenswerter Weise geht aus dieser Norm für p=1 die Betragsnorm, also die Aufsummierung aller Komponentenbeträge des gegebenen Vektors, sowie für p=2 die sogenannte Euklidische Norm hervor. Durch Verschieben von p im Intervall [1,] lässt sich dabei die charakteristische Rautenform der Einheitskugel4 der Betragsnorm über die tatsächlich kugelförmige Einheitskugel der Euklidischen Norm in die quadratische Form der Maximumsnorm überführen (p).

Veränderung der abgeschlossenen Einheitskugel unter der p-Norm für p zwischen 1 und 3

Kommen wir nun zum Begriff des Abstands zwischen zwei Zahlen, welcher in Form von Metriken auf algebraische Strukturen wie Vektorräume übertragen wird. Wie in der Einführung dieses Abschnits beschrieben, haben wir den Abstand zwischen Zahlen schon in der Schule über den Betrag der Differenz beschrieben. Wir kennen an dieser Stelle in Form des Satz des Pythagoras auch schon eine sinnvolle Definition für den Abstand zwischen Punkten in R2:

d(x,y):=|x1x2|2|y1y2|2mitx,yR2

Diese Metrik über dem zweidimensionalen reellen Vektorraum lässt sich, auf folgende naheliegende Art und Weise, in eine Metrik für alle endlich dimensionalen R-Vektorräume erweitern:

d(x,y):= ni=1|xiyi|2mitx,yRn

Diese Metrik auf Grundlage des Satz des Pythagoras wird als Euklidische Metrik bezeichnet. Sie ist eine der Metriken, welche wir im weiteren Verlauf dieses Artikels in Voronoi-Diagrammen visualisieren werden.

Die Definition solcher Metriken als Abbildungen der Form d(x,y):V×VR0 beinhaltet eine Menge von Axiomen, welche von der Metrik-Abbildung erfüllt sein müssen.

Positive Definitheit d(x,y)0d(x,y)=0x=y
Symmetrie d(x,y)=d(y,x)
Dreiecksungleichung d(x,z)d(x,y)+d(y,z)

Wir fordern also, dass der Abstand zwischen beliebigen Punkten immer größer gleich Null sein muss, ein Nullabstand äquivalent zur Gleichheit der Punkte ist, die Reihenfolge der Punkte für den Abstand irrelevant ist und das der direkte Abstand zwischen zwei Punkten kleiner gleich einem Umweg über weitere Punkte ist.

Bei der Betrachtung der Definitionen von p-Norm und Euklidischer Metrik fällt auf, dass diese sich zu ähneln scheinen. Dies ist kein Zufall, denn Metriken können aus Normen induziert werden. So folgt die Euklidische Metrik mit d(x,y):=xy2 direkt aus der 2-Norm.

Es liegt also Nahe, dass auch aus die Betragsnorm mit p=1 eine Metrik induziert - die sogenannte Mannheimer-Metrik:

d(x,y):=ni=1|xiyi|mitx,yRn

Die Bezeichnung dieser Metrik als Mannheimer-, Manhattan oder auch Taxi-Metrik wird nachvollziehbar, wenn wir uns bewusst machen, dass sie die Betragsdifferenzen der Punkte aufsummiert und somit den Weg beschreibt, den ein Taxi in einem Straßenraster nachvollziehen müsste, wie es in Mannheim und zahlreichen nordamerikanischen Städten üblich ist, um von A nach B zu gelangen.

Wir haben also nun zwei Metriken kennengelernt, die beide für verschiedene p aus der gleichen p-Norm hervorgehen. Die Mathematik charakterisierende Suche nach gemeinsamen Mustern in abstrakten Strukturen legt nahe, dass so, wie die Betragsnorm und die Euklidische Norm Varianten der allgemeineren Klasse der p-Normen sind, auch die Mannheimer und Euklidische Metrik Varianten einer allgemeineren Klasse von Metriken sind. Diese allgemeinere Klasse beschreiben wir in Form der Minkowski-Metrik:

d(x,y):=(ni=1|xiyi|p)1pmitx,yRn,pR+

Die Beschreibung der Euklidischen und Mannheimer-Metrik als Varianten der Minkowski-Metrik ist damit gerechtfertigt, dass diese für p=1 beziehungsweise p=2 aus ihr hervorgehen.

Besonders interessant ist im Kontext der Visualisierung von Metriken, dass die Minkowski-Metrik für p[1,2] einen stetigen Übergang von der Mannheimer in die Euklidische Metrik ermöglicht. Dies ergibt schöne, flüssige Voronoi-Diagramme, wie wir im Abschnitt zu bewegten Bildern sehen werden.

Voronoi-Diagramme

Nachdem wir uns im vorangehenden Abschnitt einen groben Überblick über Normen und Metriken in endlich dimensionalen reellen Vektorräumen gemacht haben, können wir uns nun dem eigentlichen Thema dieses Artikels zuwenden: der Visualisierung von Metriken in Voronoi-Diagrammen.

Unter Voronoi-Diagrammen verstehen wir die Aufteilung der Euklidischen Ebene in disjunkte Teilflächen abhängig der Distanz zu einer gegebenen Menge von Punkten und gekennzeichnet durch entsprechende Einfärbung entsprechend des jeweils nächsten Punktes.

Im Falle der Euklidischen Metrik, d.h. der Minkowski-Metrik mit p=2, ergeben sich somit Grafiken wie die folgende:

Voronoi-Diagramm der Minkowski-Metrik mit p=2

Während wir die Definitionen der Metriken bisher im Speziellen für R2 betrachtet haben, gerät der zugrundeliegende Körper R mit der konkreten Generierung von Voronoi-Diagrammen als Pixelgrafiken in Konflikt, da wir offensichtlich nicht alle Punkte der Teilflächen bzw. Mengen darstellen können. Die naheliegendste Lösung für dieses Problem ist, die Metriken nur auf Z2 zu betrachten. Dies ist einfach möglich, da Z2 eine echte Teilmenge von R2 ist und eine triviale Bijektion zwischen Punkten in Z2 und Pixeln auf einem Bildschirm existiert.

Voronoi-Diagramm der Minkowski-Metrik mit p=1

Die konkrete Generierung von Voronoi-Diagrammen ist dann einfach möglich - es müssen nur die Punkte der, dem gewünschten Sichtbereich entsprechenden, Teilmenge von Z2 durchlaufen und abhängig ihrer Distanz zu den Referenzpunkten unter der gewünschten Metrik eingefärbt werden.

double minkowski_metric(
	const double         p,
	const imgen::vector& a,
	const imgen::vector& b
) {
	return std::pow(
		  std::pow(std::abs(std::get<0>(a) - std::get<0>(b)), p)
		+ std::pow(std::abs(std::get<1>(a) - std::get<1>(b)), p),
		1.0 / p
	);
}

Zur Approximation der Bildmenge R0 der Metrik-Funktionen verwenden wir double Werte, während die Ursprungsmenge R2×R2 über zwei Tupel des Typs std::tuple<std::ptrdiff_t, std::ptrdiff_t> in unserer Implementierung abgebildet wird.

Die obige Implementierung der Minkowski Metrik in C++ genügt zusammen mit folgendem, auf einer kleinen PPM Grafikbibliothek basierendem, Listing zur Generierung von Voronoi-Diagrammen über einer fixen reference_vectors Punktmenge für beliebige p.

std::pair<double, imgen::colored_vector> get_distance_to_nearest(
	const std::function<double(imgen::vector, imgen::vector)>& metric,
	const imgen::vector a
) {
	constexpr std::array<imgen::colored_vector, 9> reference_vectors{
		imgen::colored_vector{   0,    0, imgen::red()                },
		imgen::colored_vector{ 240,  200, imgen::color{220, 220, 220} },
		imgen::colored_vector{-100,  230, imgen::color{ 94, 113, 106} },
		imgen::colored_vector{ 120, -100, imgen::color{140, 146, 172} },
		imgen::colored_vector{ -42, -200, imgen::color{128, 128, 128} },
		imgen::colored_vector{ 120,   40, imgen::color{ 16,  20,  22} },
		imgen::colored_vector{-150,   50, imgen::color{192, 192, 192} },
		imgen::colored_vector{  60, -128, imgen::color{178, 190, 181} },
		imgen::colored_vector{-240,  -20, imgen::color{ 54,  69,  79} }
	};

	// [...] Bestimmung des nächsten Referenzvektors unter der gegebenen Metrik

	return std::make_pair(*minimal_distance, nearest);
}

void generate_minkowski_voronoi(const double p) {
	const auto metric{[p](const imgen::vector a, const imgen::vector b) -> double {
		return minkowski_metric(p, a, b);
	}};

	imgen::write_ppm(
		"voronoi_" + std::to_string(p) + ".ppm",
		512,
		512,
		[&metric](std::ptrdiff_t x, std::ptrdiff_t y) -> imgen::color {
			const auto& nearest = get_distance_to_nearest(
				metric,
				imgen::vector{x, y}
			);

			if ( nearest.first <= 5.0 ) {
				return imgen::black();
			} else {
				return std::get<2>(nearest.second);
			}
		}
	);
}

Die Punktmenge ist dabei die, welche in obigen Beispiel Diagrammen zu betrachten ist. Alles, was wir an dieser Stelle über die zentrale Funktion imgen::write_ppm wissen müssen, ist, dass diese formell ein Bild über der Menge M:={(x,y)Z2|x[w2,w2]y[h2,h2]} mit Höhe h und Breite w aufspannt und für (x,y)M die gegebene Funktion Z×Z[0,255]×[0,255]×[0,255] aufruft, wobei die Tupel ihrer Bildmenge als Farben interpretiert werden.

Zur Kennzeichnung der Referenzvektoren wird jeweils eine abgeschlossene Kugel unter der verwendeten Metrik mit Radius 5 gezogen. Dies hat den schönen Nebeneffekt, dass wir anhand der Form der Punktmarkierungen schon Rückschlüsse auf die zur Generierung verwendete Metrik ziehen können, da die Markierungen nur skalierte Versionen der Einheitskugel sind, welche wir im vorangehenden Abschnitt besprochen haben.

Der komplette Quellcode der aufgeführten Beispiele ist auf Github und cgit unter der MIT Lizenz frei verfügbar und kann so zur Generierung eigener Voronoi Diagramme herangezogen werden.

Minimalistische Generierung von Pixelgrafiken in C++

Wie bereits angedeutet, basiert der hier gewählte Weg zur Generierung von Voronoi-Diagrammen auf einer minimalistischen C++ Grafikbibliothek, welche im Rahmen meiner Experimente zu diesem Thema entstanden ist. Die Ursache dafür war, dass ich von vornherein nur einfache Pixelgrafiken generieren wollte und keinerlei Bedarf für die Vielfalt an Funktionalität hatte, wie sie von Grafikbibliotheken wie Cairo dargeboten wird. In solchen Situationen empfielt es sich, dass entstehende Program nicht mit Abhängigkeiten zu großen Frameworks zu überfrachten, sondern das Problem auf das Essenzielle zu reduzieren. In unserem Fall also die Iteration über eine gegebene Bildmenge und die Zuweisung von Farben zu Punkten. Andere Probleme wie Kompression und Animation in GIF Grafiken sind dann besser spezialisierten Werkzeugen wie Imagemagick überlassen.

Eines der wohl einfachsten Dateiformate für Pixelgrafiken ist das Portable PixMap Format, dass nur aus der magischen Zahl P6 gefolgt von Zeilenumbruch-separierter Breite und Höhe sowie einem Stream der Bildpunkte bestehend aus je drei Bytes für Rot, Grün und Blau in dieser Reihenfolge besteht. Dieses primitive Format führt dazu, dass die im Beispiel verwendete imgen::write_ppm Funktion sehr einfach zu implementieren ist:

void write_ppm(
	const std::string&                                   path,
	const std::size_t                                    width,
	const std::size_t                                    height,
	std::function<color(std::ptrdiff_t, std::ptrdiff_t)> generator
) {
	ppm_pixel_stream file(path, width, height);

	const std::ptrdiff_t min_y = height / 2 * -1;
	const std::ptrdiff_t max_y = height / 2;
	const std::ptrdiff_t min_x = width  / 2 * -1;
	const std::ptrdiff_t max_x = width  / 2;

	for ( std::ptrdiff_t posY = max_y; posY > min_y; --posY ) {
		for ( std::ptrdiff_t posX = min_x; posX < max_x; ++posX ) {
			file << generator(posX, posY);
		}
	}
}

Den inhärenten Mehraufwand der Verwendung von std::function zur Übergabe der Callbacks für Generierung und Metriken und der Ausgabestreams des Standards in imgen sowie der eigentlichen Diagram-Generierung akteptiere ich an dieser Stelle der Klarheit und des Vertrauens in den Compiler wegen. Weiterhin lässt sich die Performance von vielen repetiven Generierungen - die ohnehin nicht an der Ein-Ausgabe-Performance sondern an den konkreten Berechnungen hängt - über Multithreading in verkraftbare Schranken weisen.

Bewegte Bilder

Das in meinen Augen schönste Resultat dieses Artikels ist die Visualisierung der Transformation von der Mannheimer in die Euklidische Metrik in Form der folgenden GIF Animation:

Übergang von der Mannheimer in die Euklidische Metrik und zurück

Diese Grafik kann dabei vollautomatisch über das, auf Imagemagick basierende, Script voronoi.sh rekonstruiert werden. Da die Generierung der für die Animation notwendigen zahlreichen Einzelbilder von Voronoi-Diagrammen mit langsam ansteigendem p etwas Zeit kosten kann, lohnt sich die Optimierung durch Aufteilen des Arbeitsaufwands auf mehrere Verarbeitungsstränge. Dies ist einfach möglich, da wir keinerlei veränderliche Daten zwischen einzelnen Voronoi-Diagrammen teilen müssen. Da der Standard mittlerweile schon seit einigen Jahren Unterstützung für Multithreading bietet, gestaltet sich auch die konkrete Umsetzung dieser Optimierung erfreulich kompakt.

void generate_parallel_minkowski_voronoi(
	const unsigned int thread_count,
	const double       lower,
	const double       upper,
	const double       epsilon
) {
	std::vector<std::thread> threads;

	const double step = ( upper - lower ) / thread_count;
	double offset     = lower;

	while ( threads.size() < thread_count ) {
		threads.emplace_back([offset, step, epsilon]{
			generate_minkowski_voronoi(
				offset,
				offset + step,
				epsilon
			);
		});

		offset += step;
	}

	generate_minkowski_voronoi(upper);

	for ( auto& thread : threads ) {
		thread.join();
	}
}

Rückblick

Hiermit sind wir am Ende meines ersten textuellen Ausflugs an die Schnittstelle zwischen Mathematik und Software angelangt. Ich hoffe an dieser Stelle, dass die Ausführungen und Beispiele verständlich waren und ich mich, am Anfang meines Studiums der Mathematik stehend, nicht in formelle Fehler verstrickt habe.

Grundsätzlich finde ich Voronoi-Diagramme hilfreich, um eine visuelle Intuition für die Auswirkungen verschiedener Metriken zu gewinnen - gleichwohl diese in höheren Dimensionen schnell in ihrem Nutzen schwindet. Aber auch abgesehen vom praktischen Aspekten sind diese Diagramme eine schöne Möglichkeit in etwas anschaulicherem Kontext mit Mathematik zu spielen und schöne Bilder zu erzeugen.

Ansätze zum Ausbau der im Rahmen dieses Artikels entstandenen Programme - an dieser Stelle noch einmal der Hinweis auf die Quellen bei Github und cgit - sind verschiedene Metriken in einem Diagramm zu mischen oder zu gewichten sowie sich praktische Einsatzszenarien für Voronoi-Diagramme anzuschauen. Wenn die Grafiken beispielweise bei dem ein oder anderen meiner Leser die Erinnerung an Strukturen in der Natur wie Bienenwaben oder aufeinandertreffende Seifenblasen geweckt haben, dann liegt das daran, dass sich Prozesse dieser Art tatsächlich über Voronoi-Diagramme betrachten lassen. Der entsprechende Wikipedia-Artikel liefert hier als Abschluss eine Auflistung zahlreicher Anwendungsbeispiele.

  1. R könnte an dieser Stelle auch die Menge N der natürlichen Zahlen, die Menge C der komplexen Zahlen oder ein beliebiger anderer Körper sein, für den der Betrag definiert ist.

  2. Ein Vektorraum ist eine Menge von Vektoren gleicher Dimension, für welche die Operationen der Vektoraddition und Skalarmultiplikation sinnvoll definiert sind. Eine sinnvolle Definition dieser Operationen schließt neben einigen Rechenregeln mit ein, dass ein unter der Addition neutrales Element, der Nullvektor, sowie ein unter der Skalarmultiplikation neutraler Skalar, das Einselement, existieren. Zusätzlich muss zu jedem Vektor ein bezüglich der Addition inverses Element existieren, d.h. ein vV mit v+v=0. Zusammenfassend führen diese Anforderungen dazu, dass innerhalb eines Vektorraums in weitgehend gewohnter Art und Weise gerechnet werden kann.

  3. Der Begriff K-Vektorraum sagt aus, dass alle Komponenten der enthaltenen Vektoren Elemente aus dem Körper K sind. Im Falle eines R-Vektorraums sind also beispielsweise alle Komponenten aller Vektoren reelle Zahlen. Der Körper ist dabei auch die Menge, aus der die Skalare für die Skalarmultiplikation gegriffen werden.

  4. Die abgeschlossene Einheitskugel ist die Menge ¯¯¯¯B(1,0):={xV|x1} - also die Menge aller Vektoren mit Länge kleiner gleich Eins. Die Visualisierung dieser Kugel kann zur Charakterisierung von Normen herangezogen werden.

» Notes on function interposition in C++

February 21, 2016 | cpp development english | Adrian Kummerländer

To counterbalance the fastly increased amount of time I am spending on purely theoretical topics since I started studying mathematics, my most recent leisure time project was to familiarize myself with function interposition in C++ on Linux. This article will document some of the ins and outs of using this technique in an actual project in addition to describing how the acquisition of the interposed function’s pointer may be reasonably abstracted by a function template.

Basics

Most if not all of the applications and services one commonly uses are not monolithic executables that one could execute on the bare metal but depend on a number of separate libraries that provide useful abstractions the actual application is built upon. As most application share a common set of library dependencies it would be quite wasteful to package each application with its own separate copy of a given library. This is why most libraries are commonly linked dynamically which means that e.g. a call to random library function f is not resolved during compilation by replacing it with the library provided source code or a fixed reference to the implementation of f but resolved respectively linked at runtime. For Linux applications this dynamic resolution is commonly performed by the dynamic linker ld.so.

Instance specific configuration of this library is possible via a set of environment variables. One of these variables is LD_PRELOAD which enables us to provide “[…] a list of additional, user-specified, ELF shared objects to be loaded before all others [that] can be used to selectively override functions in other shared objects.” (ld.so manpage, section on LD_PRELOAD).

This feature is what is commonly referred to as function interposition and is what will be discussed in the following sections. Other options for intercepting function calls such as ptrace are not covered by this particular article.

Use case

Function interposition is useful in various practical scenarios such as providing custom memory allocators as drop in replacements for the appropriate standard library functions as well as monitoring the function calls of a application as an additional debugging avenue. Furthermore LD_PRELOAD’s nature of replacing library functions with custom logic in a not necessarily obvious manner makes it a security risk which is why it is disabled for e.g. setuid applications. But even with this restriction it may be used as a foundation for userland rootkits - for instance one could hijack the library functions used to interface with the file system and change what certain applications see. Such shenanigans could then in turn be used to manipulate the source code of an application during compilation while continuing to display the unchanged source code to the user via her chosen text editor and file hashing tool. More information on this kind of attack can be obtained e.g. in the 31c3 talk on reproducible builds which is where I was first confronted with this risk.

However the use case that led me to dive into this topic was to develop a tool to be dropped in front of any LD_PRELOAD supported program that would then monitor all relevant file system interactions and generate a nice summary of what was changed to be used for documentation purposes. The result of this undertaking is available on Github and cgit.

Requirements for successful interposition

To interpose a given function the library provided to the dynamic linker via LD_PRELOAD simply needs to contain a function symbol of the same name and signature.While this is not a problem in C it can be problematic in C++ as the compiler per default performs name mangling to convert a given function signature to a plain string1. Luckily this can be prevented by enclosing the functions to be interposed in an external "C" block.

Note that this only applies if we want to specifically interpose C functions from C++. There is nothing stopping us from interposing any function in a shared library as long as we can get the compiler to generate the correct symbol name. Accordingly this also works for C++ class member functions or functions of libraries written in other languages such as D.

To check if the symbols are exported correctly we can use nm which ĺists the symbols in ELF object files.

> nm libChangeLog.so | grep "open\|write"
000000000009e866 T open
000000000009e99b T write
000000000009ea5d T writev
000000000009f61a W _Z11track_writei
000000000009f6ec W 
_Z11track_writeRKNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE
[...]

As we can see interposing this library would lead to the application calling the library’s open, write and writev functions instead of the standard C library’s. Note that the C++ source additionally needs to be compiled as position-independent code to be usable as a shared library at all. If one uses clang or g++ this is easily achieved by adding the -fPIC option.

Acquiring a pointer to the actual function

Although we can now replace functions in a target application with our own logic the goal remains to merely interpose a function which means that we have to call the actual function at some point. The dynamic linker library offers a function to acquire the address of the next symbol with a given name in the resolution stack in the form of dlsym. This function is defined in the dlfcn.h header and requires the interposed library to be linked to ld.so.

void* dlsym(void* handle, const char* symbol);

While handle can be used to restrict the resolution to a specific shared library we pass a special pseudo-handle RTLD_NEXT which instructs the function to return the address of the next symbol whose name equals the null-terminated symbol parameter.

Note that RTLD_NEXT is only defined by dlfcn.h if _GNU_SOURCE is defined during preprocessing - i.e. before the header is included. This may happen implicitly if features.h is included. If this should not be the case a plain #define _GNU_SOURCE satisfies the requirement.

If we were working in C we could directly assign the returned pointer of type void* to a function pointer of the function’s signature. However this sort of cast is not allowed in C++ which is why we need to manually copy the address of the symbol into a function pointer. This may be achieved using std::memcpy.

const void* symbol_address{ dlsym(RTLD_NEXT, "write") };
ssize_t (actual_function*)(int, const void*, size_t){};

std::memcpy(&actual_function, &symbol_address, sizeof(symbol_address));

To prevent dlsym from being unneccessarily called more than once for a given symbol name one probably wants to persist the function pointer to e.g. a static variable local to the function body.

static ssize_t (actual_function*)(int, const void*, size_t){};

if ( !actual_function ) {
	const void* symbol_address{ dlsym(RTLD_NEXT, "write") };

	std::memcpy(&actual_function, &symbol_address, sizeof(symbol_address));
}

This logic should be placed in the function body and not for instance in a global initialization function as it is not guaranteed that such a function will be executed prior to any calls to interposed functions. The next section will describe an approach to reduce unneccessary code duplication in this context.

Abstracting function pointer handling

The most straight forward approach to abstracting the usage of dlsym is to wrap it in a more C++-like function template. To prevent unneccessary duplication of the functions return and parameter types as well as to hide the strange syntax of function pointer declaration we first define a template alias as follows:

template <class Result, typename... Arguments>
using ptr = Result(*)(Arguments...);

This allows us to define function pointers in a fashion simmilar to std::function and can be used as the template parameter of our actual dlsym abstraction.

template <typename FunctionPtr>
FunctionPtr get_ptr(const std::string& symbol_name) {
	const void* symbol_address{ dlsym(RTLD_NEXT, symbol_name.c_str()) };

	FunctionPtr actual_function{};
	std::memcpy(&actual_function, &symbol_address, sizeof(symbol_address));

	return actual_function;
}

This extraction of all dlsym calls into a single function template will come in handy during the section on problems in practice. Furthermore it allows us to write the exemplary interposition of the write library function in the following way which I for one find to be more maintainable and overall nicer looking than its c-style equivalent.

ssize_t write(int fd, const void* buffer, size_t count) {
	static actual::ptr<ssize_t, int, const void*, size_t> actual_write{};

	if ( !actual_write ) {
		actual_write = actual::get_ptr<decltype(actual_write)>("write");
	}

	// <-- custom logic to be interposed in all `write` calls

	return actual_write(fd, buffer, count);
}

Problems in practice

The approach detailed in the sections above was enough to develop my transparent file system change tracking tool to a point where it could monitor the actions of the core utilities as well as generate diffs of files edited in vim. But while checking out the current state of the neovim project I discovered that interposing libChangeLog.so led to a deadlock during startup.

This deadlock was caused by the custom memory allocation library jemalloc used by neovim because it calls mmap during its initialization phase. The problem with this is that it already leads to executing libChangeLog’s mmap version whose static actual_mmap function pointer is not initialized at this point in time. This is detected by our current logic and leads to a call to dlsym to remedy this situation. Sadly dlsym in turn requires memory allocation via calloc which leads us back to initializing jemalloc and as such to a deadlock.

I first saw this as a bug in jemalloc which seemed to be confirmed by a short search in my search engine of choice. This prompted me to create an appropriate bug report which was dismissed as a problem in the way mmap was interposed and not as a problem in the library. Thus it seems to be accepted practice that it is not the responsibility of a preloaded library to cater to the needs of other libraries relying on function interposition. This is of course a valid position as the whole issue is a kind of chicken and egg problem where both sides can be argued.

Issues of this kind are common when implementing interpositions of low level c-library functions as they are not only used everywhere but are also non-monolithic and may easily depend on each other if they are augmented by custom logic. If we want to interpose more than a single function or add logic depending on other library calls it is quite certain that we will run into issues simmilar to the one detailed in this section. While those issues can be fixed this can easily require the interposition of further functions which can possibly quickly spin out of control.

Implementing a static memory allocator

To return to our issue at hand I was left with the only option of working around the deadlock by adapting libChangeLog to call dlsym without relying on the wrapped application’s memory allocator of choice. The most straight forward way to do this is to provide another custom memory allocator alongside the payload function interpositions of mmap and friends.

Such a static memory allocator is implemented by libChangeLog in commit af756d and basically consists of a statically sized array allocated in the object file itself alongside a stacked allocation “algorithm” without any support for releasing and reusing memory of the static buffer once allocated.

This custom allocation logic is then selectively called by interpositions of free, malloc and calloc. The choice between using the real allocator and the static allocator depends on a dlsym recursion counter maintained by a init::dlsymContext scope guard helper class. As we already abstracted all usage of dlsym to a single function template the introduction of a static allocator for dlsym required only small changes to the existing function interpositions.

Summary

As a conclusion one could say that function interposition is useful for both debugging applications and building programs that monitor other processes on such a low level that one doesn’t need to care about the language they are written in nor needs to customize the monitoring logic for specific applications as long as everything works as expected. Furthermore it is a nice approach to familiarizing oneself with the lower level workings of Linux userland applications.

Although this approach depends on interfacing with C code it can be reasonably abstracted using C++ and as such can also make use of the higher level functionality offered by this language.

One should however expect to dive deeper into C library internals and debug lower level issues while actually wanting to implement higher level functionality. Furthermore we probably will not get away with just implementing an interposition of the function we are interested in but also other functions that depend on it in some fashion in some wrapped applications. Definitely exepect quite a few coredumps and deadlocks during development.

For a real world example of how function interposition using LD_PRELOAD and C++ may be used to build a small but hopefully useful application feel free to check out change on Github or cgit.

  1. This is required to e.g. support function overloading which is not available in C. Of course this also means that our interposed functions can not be overloaded. Function names may be demangled via the --demangle option of nm.