UNIXwork

Idee für Struct-Serialisierung

2018-05-01 13:10:48.0

Eine kleine semi-sinnvolle Idee, wie man Serialisierung in C realisieren kann, die ich einfach mal teilen möchte. Wer hingegen nach einer ordentlichen Serialisierungsmethode sucht, der sollte besser Codegeneratoren verwenden, wie z.B. Google Protocol Buffers für C++ oder protobuf-c für C.

Meine Idee hingegen basiert darauf, dass man seine Daten gar nicht erst serialisieren muss, weil sie bereits seriell im Speicher liegen.

Der triviale Fall

Structs, die keine Pointer enthalten, kann man direkt so wie sie im Speicher liegen in eine Datei schreiben oder aus ihr lesen.

struct mydata {
    int a;
    int b;
    float c;
};

...

struct mydata data;
data.a = 12;
data.b = 14;
data.c = 13.37;

write(fd, &data, sizeof(struct mydata));

...

struct mydata d2;
read(fd2, &d2, sizeof(struct mydata);

Das Konzept

Doch was machen wir, wenn eine Struct Pointer auf Structs oder andere Daten (z.B. Strings) enthält? Wenn man nur die Adresse speichert, bringt einem das beim Deserialisieren nichts, denn es fehlen nicht nur die Daten, der Pointer ist vielleicht auch ungültig.

Die Idee, die ich nun hatte, ist, dass die ganze Objekt-Hierarchie sich nur in einem festgelegten großen Speicherblock befinden darf. Die Structs enthalten dann auch keine echten Pointer mehr, sondern nur noch eine relative Adresse zu diesem Speicherblock, also quasi ein Index.

Hier ein kleines Beispiel, wie ich mir das vorstelle. Angenommen man hat folgende Structs:

typedef struct {
    int x;
    int y;
    int z;
} ChildObj;

typedef intptr_t ChildObjPtr;

typedef struct {
    ChildObjPtr child1;
    ChildObjPtr child2;
} RootObj;

Zuerst alloziert man genug Speicher, der (hoffentlich) für alle Daten reicht.

char *block = malloc(EVERYTHING_YOU_NEED);
size_t i = 0;

Will man jetzt Speicher für eine Struct reservieren, nutzt man dann nicht mehr malloc, sondern man greift auf den vorher reservierten Speichier zurück:

RootObj *root = (RootObj*)(block+i);
i += sizeof(RootObj);

ChildObj *c1 = (ChildObj*)(block+i);
i += sizeof(ChildObj);

ChildObj *c2 = (ChildObj*)(block+i);
i += sizeof(ChildObj);

c1->x = 1;
c1->y = 2;
c1->z = 3;
c2->x = 10;
c2->y = 20;
c2->z = 30;

Im RootObj möchte man jetzt Verweise auf die beiden anderen Structs haben. Hierfür müssen wir nur aus den Pointern c1 und c2 die Adressen relativ zu dem Pointer block berechnen.

root->child1 = (ChildObjPtr) (char*)c1 - block;
root->child2 = (ChildObjPtr) (char*)c2 - block;

Im Speicher liegen jetzt hintereinander die Daten. Zuerst RootObj und dann zwei mal ChildObj. Das kann man so direkt in Dateien schreiben und auch wieder daraus lesen.

Ein Problem ist, dass ich nicht direkt auf die Felder child1 und child2 zugreifen kann. Also statt root->child1 müsste man wieder die Adresse umrechnen:

((ChildObj*)(block + root->child1))->x = 5;

Optische Verbesserungen

Das ganze ist natürlich ganz schön hässlich. Und unpraktisch. Man kann kein malloc mehr verwenden und -> geht auch nicht. Dafür hat man viel Schreibarbeit und Rumgerechne, was viel Potential für Fehler hat.

Man könnte sich aber einen eigenen malloc-ähnlichen Memory-Allocator schreiben, der ein ähnliches Interface für Speicherverwaltung zur Verfügung stellt, aber auf einem zusammenhängenden Speicherbereich operiert. Die UCX-Bibliothek enthält eine einfache Implementierung hierfür.

Und für das Arbeiten mit den relativen Pointern kann man sich ein paar Makros schreiben:

// stores an absolut pointer as a relative pointer
#define SPTR(root, ptr) (intptr_t)((char*)ptr - (char*)root)

// converts a relative pointer to an absolut pointer
#define CPTR(root, relptr) (void*)((char*)root + relptr)

Mit den Makros sieht der Code von oben dann etwas schöner aus:

root->child1 = SPTR(root, c1); // still not as nice as root->child1 = c1  :'(

ChildObj* child = CPTR(root, root->child1);

Natürlich nicht ganz perfekt, schöner geht das aber leider nicht.

Probleme

Das Konzept ist, dass einfach der ganze Speicherblock beim Serialisieren irgendwo hin geschrieben wird, oder zumindestens so viel davon, wie belegt ist. Um aber halbwegs komformabel zu arbeiten benötigt man ein malloc/free ähnliches Interface zur Verwaltung seines Speicherblocks. In der Praxis kommt es häufig vor, dass sich Daten auch ändern. Speicher wird freigegeben und neuer alloziert. Dabei würden dann im Speicher Lücken entstehen. Beim Transferieren des Speicherblocks würden somit viele unnötige Daten übertragen werden.

Ein weiteres Problem ist, dass man vorher wissen muss, wie viel Speicher man benötigt. Diesen müsste man auch von Anfang an komplett allozieren, selbst wenn man erstmal nur wenig benötigt. Und falls er nicht reicht kann man ganz aufgeben.

Das Konzept kann aber abgewandelt werden, um die Probleme zu lösen. Wir können auch einen eigenen Allocator schreiben, der beliebig den Speicher verwaltet und nicht nur einen großen Block. Und anstatt beim serialisieren einfach nur einen großen Block zu schreiben, brauchen wir einen richtigen Serialisierer für den Allocator, der also alle vom Allocator ausgestellten Speicherbereiche irgendwie serialisiert, so dass genau diese Speicherbereiche in der Form wiederhergestellt werden können. Freie Speicherbereiche können dabei dann natürlich weggelassen werden.

Die Idee mit den relativen Pointern funktioniert dann natürlich nicht mehr, aber statt Pointer auf Kind-Objekte könnte man immer noch Integer verwenden, die dann vom Allocator für einen Lookup des echten Pointers verwendet werden. Man könnte daher immer noch mit den beiden Makros arbeiten, nur dass diese dann komplexere Logik als eine einfache Addition enthalten würden.

Zusammenfassung

Anstatt also eine Struct bzw ein Objekt mit allen ihren Membern zu serialisieren, serialisiert man einen Allocator, der für die Speicherreservierung der Objekte verwendet wurde. Objekte enthalten keine direkten Pointer auf die Speicheradresse anderer Objekte, sondern nur einen Index (oder ein Integer mit anderer Bedeutung).

Ist dieses Konzept sinnvoll? Ich weiß es nicht. Jedenfalls hab ich nicht vor, es irgendwo produktiv anzuwenden. Deswegen habe ich mir auch ein komplettes Code-Beispiel gespart.

Autor: Olaf | 0 Kommentare | Tags: c

Überladung von Funktionen in C

2018-04-21 18:59:29.0

Wer sich C schon mal angeschaut hat, der weiß, dass es dort keine Überladung von Funktionen gibt. Unterschiedliche Deklarationen von Funktionen mit dem selben Namen sind nicht erlaubt.

void myfunction(int i);
void myfunction(char *s); /* geht nicht */
void myfunction(int a, int b); /* geht erst recht nicht */

Je nach dem, was man vorhat, gibt es allerdings ein paar Tricks, um doch noch ans Ziel zu kommen.

In meinem Fall wollte ich Funktionen in zwei Varianten, die eine dieser Structs als Argument erhält:

typedef struct {
    char *ptr;
    size_t length;
} sstr_t;

/* new struct for const strings */
typedef struct {
    const char *ptr;
    size_t length;
} scstr_t;

Wie man sieht, sind beide Structs sehr ähnlich. Mein Plan war, dass diverse alte Funktionen, die bisher sstr_t-Parameter erwartet haben, dann mit beiden Structs funktionieren. Da man Structs (ohne Pointer) nicht in andere casten kann, konnte ich nicht einfache Wrapper-Makros für die Funktionen schreiben, die einfach einen Cast enthalten.

Das ganze brauche ich, um die String-API von UCX zu verbessern. Es soll auch eine eine Struct für konstante Strings geben, die dann auch benutzt werden kann, ohne die Quellcodekompatiblität groß zu brechen. Dabei habe ich mehrere Lösungen gefunden:

C11 _Generic

Seit C11 gibt es das _Generic Keyword für generische Ausdrücke. Damit können zur Compile-Time je nach Typ eines Arguments unterschiedliche Ausdrücke ausgewählt werden. Zum Beispiel:

void print_int(int i);
void print_string(char *s);

#define print(x) _Generic(x, int: print_int, char *: print_string)(x)

Benutzt man das Makro print nun mit einem int, wird die Funktion print_int ausgeführt. Bei einem char * wird print_string verwendet.

Was übrigens nicht geht ist folgendes:

#define print(x) _Generic(x, int: print_int(x), char *: print_string(x))

gcc/clang builtins

Gcc hat ein paar nützliche Builtins, mit denen man das Gleiche erreichen kann wie mit dem C11 _Generic. Praktischerweise unterstützt clang diese Builtins auch. Trotzdem verlässt man damit natürlich den Pfad der C-Standardkonformität.

Die beiden Builtins, mit denen man _Generics nachbauen kann, sind:

type __builtin_choose_expr (const_exp, exp1, exp2)
int __builtin_types_compatible_p (type1, type2)

Mit __builtin_types_compatible_p prüfen wir, ob der Typ kompatibel ist, und nehmen dies als Bedingung um eine Expression mit __builtin_choose_expr auszuwählen.

#define print(x) __builtin_choose_expr(__builtin_types_compatible_p(x, int), print_int, print_string)(x)

Spracherweiterungen: Statement Expressions und typeof

Statement Expressions sind eine C Erweiterung, die von einigen Compilern, unter anderem gcc, clang, aber auch anderen, unterstützt werden. Damit kann ein Compound-Statement wie eine Expression funktionieren. Die Anweisungen müssen nur mit ({ }) eingeschlossen werden. Dies kann dann überall stehen, wo Expressions erlaubt sind, also z.B. auch als Funktionsparameter.

Allgemein sowas wie _Generic nachbauen geht mit Statement Expressions nicht. Mein ursprüngliches Problem mit den zwei ähnlichen Structs hingegen lässt sich lösen. Statt jeweils eine Funktion für jeden Typ zu implementieren, reicht eine einzelne Funktion, die über ein Makro aufgerufen wird. Das Makro enthält dann eine Statement Expression, die sstr_t oder scstr_t in den richtigen Typ umwandelt.

Zum Einsatz kommt dabei auch typeof, was wieder eine Erweiterung ist, die auch von mehreren Compilern unterstützt wird. Hiermit kann eine Variable mit dem selben Typ wie eine andere deklariert werden.

void print_s(scstr_t s);

#define print(x) print_s( ({ \
    typeof(x) tmp = x; \
    scstr_t arg = { tmp.ptr, tmp.length }; \
    arg; \
}) )

Leere Parameterliste

Deklariert man in C eine Funktion ohne Angabe irgendeines Parameters, dann heißt dies nicht, das keine Parameter übergeben werden können, sondern dass der Compiler beliebige Parameter erlaubt:

void func();

void voidfunc(void);

int main(void) {
    func(1);
    func(1, 2, 3);
    func("string");
    func();

    voidfunc(); // no arguments allowed

    return 0;
}

Ähnlich wie beim Beispiel mit den Statement Expressions kann ich damit ein Makro für meine Funktion bauen, welches mit Hilfe einer Funktion das sstr_t oder scstr_t Argument umwandelt. Die Umwandlungsfunktion wird mit leerer Argumentliste deklariert und implementiert wird sie folgendermaßen:

scstr_t convert2scstr(sstr_t s) {
    scstr_t ret;
    ret.ptr = s.ptr;
    ret.length = s.length;
    return ret;
}

Dies funktioniert logischerweise nur, weil die beiden Structs gleich groß sind und einen gleichen Aufbau haben. Der Unterschied zwischen char * und const char* ist in diesem Fall egal. Sieht etwas frickelig aus, ist aber standardkonform und kann als Fallback-Lösung für alte oder unbekannte Compiler benutzt werden.

Insgesammt also genug Lösungsansätze, um sowohl alte Compiler zu unterstützen, aber bei neueren Compilern das ganze etwas sauberer umzusetzen.

Autor: Olaf | 0 Kommentare | Tags: c, ucx

Virtuellen Desktop wechseln - aus VBox-Guest heraus

2017-12-22 14:59:29.0

Den virtuellen Desktop kann man gewöhnlich schön per Tastenkombination wechslen, was leider nicht funktioniert, wenn eine VirtualBox-VM den Fokus hat. Dabei wäre es so schön, wenn man auf einem virtuellen Desktop eine VM im Vollbildmodus hätte und man bequem zwischen Host und Gast wechseln könnte.

Da ich leider keine VBox-Einstellung oder irgendeinen einfachen Trick gefunden habe, um dieses Verhalten zu ändern, habe ich eine vielleicht etwas primitive aber einfache Lösung gefunden.

Ein kleines Tool, welches auf dem Host läuft und per Socket einfache Befehle wie “down” oder “up” entgegen nimmt und daraufhin den virtuellen Desktop wechselt. Im Gast-System muss man noch die dortigen Tastenkombinationen für das wechseln des virtuellen Desktops so ändern, dass stattdessen an den Host diese Befehle gesendet werden.

Hier gibt es das Programm, welches auf dem Host laufen muss. Dieses lauscht auf Port 9302 und nimmt die Befehle “up”, “down”, “left” und “right” an, wobei “left” und “right” aktuell das gleiche machen wie “up” und “down”. Außerdem gibt es noch keine Konfigurationsmöglichkeiten oder Sicherheitsmechanismen.

Im Gastsystem erstellt man dann passende Scripte wie dieses hier:

#!/bin/sh
echo "up" | nc host 9302

Diese Scripte müssen dann nur noch per Tastenkombination ausgeführt werden.

Das ganze ist noch etwas primitiv, aber Verbesserungen sind geplant. Fortsetzung folgt (irgendwann).

Autor: Olaf | 0 Kommentare | Tags: x11, virtualbox, c

Codedump 1

2017-12-21 20:26:13.0

Beispielcode ohne großartige Erklärung.

aes_commoncrypto.c

Ein kurzes Beispiel dafür, wie man mit der macOS-API CommonCrypto mit AES etwas verschlüsselt und wieder entschlüsselt.

Autor: Olaf | 0 Kommentare | Tags: c, macos, crypto

File Locking - flock vs fcntl

2017-12-19 17:57:24.0

Wer sich mit File-Locking beschäftigt, der wird vermutlich auf zwei Möglichkeiten stoßen: die Funktion flock und Locking mit fcntl. Es gibt zwei wichtige Unterschiede zwischen diesen beiden Funktionen.

Locks, die mit flock erstellt wurden, werden bei einem fork an den Kind-Prozess weitergegeben. Es wird jedoch nicht der Lock kopiert, wenn durch fork oder dup der Filedescriptor dupliziert wird, denn jeder Filedescriptor auf die gelockte Datei enthält nur eine Referenz auf den selben Lock. Der Lock bleibt bestehen bis entweder alle Filedeskriptoren geschlossen sind, oder explizit eine Unlock-Operation auf einen Filedescriptor mit diesem Lock, egal in welchem Prozess, ausgeführt wird.

Mit fcntl erstellte Locks werden bei einem fork hingegen gar nicht weitergegeben. Der Lock gilt immer nur für den Prozess, der ihn erstellt hat. Außerdem wird ein Lock entfernt, wenn auch nur ein Filedescriptor der gelockten Datei geschlossen wird.

Der andere große Unterschied ist, dass nur Locking mit fcntl Posix-spezifiziert ist. Die Funktion flock hingegen ist eine BSD-Erfindung, die jedoch auch von Linux übernommen wurde. Andere Unixe, wie z.B. Solaris, unterstützen flock gar nicht.

Außerdem unterscheidet sich auch das Interface der beiden Funktionen deutlich. Mit fcntl hat man ein bisschen mehr Schreibarbeit, dafür ist es auch möglich nur einen Bereich einer Datei zu locken, wärend flock etwas primitiver ist.

Locking mit fcntl:

int fd = open(path, O_RDWR);

struct flock lock;
memset(&lock, 0, sizeof(struct flock);
lock.l_type = F_WRLCK;
lock.l_whence = SEEK_SET;
lock.l_start = 0;
lock.l_len = 0;
fcntl(fd, F_GETLK, &lock);

Locking mit flock:

int fd = open(path, O_RDWR);

flock(fd, LOCK_EX);

Die Verlockung ist vielleicht groß, flock zu nutzen, wenn man nur schnell und einfach eine ganze Datei locken möchte. Ich würde aber empfehlen, immer fcntl zu nutzen, außer man möchte wirklich Locks mit mehreren Prozessen teilen.

Autor: Olaf | 0 Kommentare | Tags: unix, c
Weiter