In many cases, a message must store a non-linear data structure (i.e.
"payload") using pointers. Examples of these are binary trees, hash
tables etc. Thus, the message itself contains only a pointer to the
actual data. When the message is sent to the same processor, these
pointers point to the original locations, which are within the address
space of the same processor. However, when such a message is sent to
other processors, these pointers will point to invalid locations.
I need a way to ``serialize'' (or pack) my message structures into a
contiguous raw memory block (and then be able to de-serialize or
"unpack" them at the other end.
This is not a trivial problem, but it's not a particularly difficult
one, either.
In some cases the original data structure, or a suitable facsimile,
can be reconstructed from the data alone. This is often the case
with hash tables, sorted lists, binary trees, and so forth. The
sending side simply sends the nodes and the receiving side inserts
them into the appropriate data structure.
In the general case, however, you need a mechanism for preserving
associations between pieces of data. Pointers are such a mechanism,
but they (almost always[1]) represent a system-specific, and usually
process-specific, mapping, and in any case the information that a
portable C program can extract from them is limited.
So the obvious solution is to have your serialization process replace
the pointers with some portable representation of the associations
between items. One very simple approach is to serialize all of the
items into a single block of malloc'd memory (using a pointer to
unsigned char), and replace the pointers with offsets into that
block. The deserializer extracts items, remembering the locations it
has extracted them to, and converts from offsets back into pointers.
A better scheme is probably to label each item with a unique
identifier and replace each pointer with the identifier of the object
it points to. This is essentially the same as the "offset" scheme
except that it makes the mapping explicit (offsets are really just
unique IDs). That increases the information available to the
deserializer, which makes it more robust - it's easier for it to
detect malformed input. Transporting data and converting it among
representations are fragile, vulnerable operations, and you want to
make them as robust as possible.
I just need a simple example, using a simple structure that contains
pointers (say a ptr to another struct, or a char*) so that I can build
on from that.
It's difficult to provide a robust, portable, short example, because
this is not a problem that lends itself to short, portable code.
Portable data representations require marshalling and unmarshalling
from and to the local system's representation. Furthermore, to
really handle the general case, you have to keep a map from object
addresses to IDs while serializing (so that each pointer can be
converted to its ID), and a reverse map while deserializing.
Here's an outline for the serializer:
- Walk the data, creating a unique ID for each item and mapping
it to the item's address. You'll have to choose what data structure
to use for the map; a hash table (keyed by address) is an obvious
choice, but might not be worth the overhead and complexity.
- As each item is serialized, prefix it with its ID (and, presumably,
type information and any other metadata your system needs to provide).
- In the serialized representation, replace each pointer field with
the ID of the pointed-to object.
This two-pass approach is simpler than a single pass, which would
have to remember the locations in the serialized data of pointer/ID
fields that referred to objects that hadn't yet been assigned an ID,
so you could fill those in later.
The deserializer would use a similar two-pass process, first
allocating areas for each item and building a map between area and ID
in the process, then deserializing each item into its area and
setting pointer fields using the map.
1. There are esoteric architectures which use "fat" pointers that
contain more information than simply an offset into address space,
but that's an implementation detail that's not useful in portable C
programming.
--
Michael Wojcik (e-mail address removed)
Against all odds, over a noisy telephone line, tapped by the tax authorities
and the secret police, Alice will happily attempt, with someone she doesn't
trust, whom she can't hear clearly, and who is probably someone else, to
fiddle her tax return and to organise a coup d'etat, while at the same time
minimising the cost of the phone call. -- John Gordon
