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

Kommentare


Name
Webseite (optional)
Captcha: 3x=12   x=?
Kommentar