This article appeared in the December 2009 issue of the
accu Overload magazine.
Shadow Data Types
Suppose we have a type called wibble defined as a concrete data type
(that is, a type whose representation is fully visible)
as follows:
// wibble.h
#include "grommet.h"
#include "flange.h"
typedef struct
{
grommet g;
flange f;
} wibble;
void wopen(wibble * w, int i);
...
void wclose(wibble * w);
The definition of wibble exposes the types involved in its
representation (grommet and flange in this made up example), and hence
requires a #include for those types in its header file. This exposure
has a price. One cost is that any change to the grommet or flange
header files, or any header files they in turn #include, at any depth,
will require a recompilation of any source file that #includes wibble.h
(either directly or transitively). Another cost is that client code can
easily become reliant on the exposed representation rather than relying
solely on the functional api. Note that in C++ you can avoid this
problem by declaring your data members private.
Abstract Data Types
These costs are sufficiently high that software developers have
invented techniques to hide a type's representation; to turn a type
into an Abstract Data Type. An Abstract Data Type is simply a type that
does not reveal its representation; a type that abstracts away its
representation. In this article I'll look at two abstract data type
implementation techniques: Opaque Data Types, and Shadow Data Types.
Opaque Data Types
The term Opaque Data Type is a well established term for the technique of
exposing only the name of the type in its header file. This is done with a forward type declaration.
This certainly has the affect of not exposing any representation!
// wibble.h
typedef struct wibble wibble;
wibble * wopen(int);
...
void wclose(wibble *);
Storage class restrictions
A definite downside with this approach is that clients cannot create objects.
#include "wibble.h"
void eg(void)
{
wibble * ptr; // ok
wibble value; // constraint violation
ptr = malloc(sizeof *ptr); // constraint violation
}
The wibble type's representation is defined in its source file and
so only code
in the source file can create wibble objects. Furthermore, these wibble
objects have to be returned to users as pointers. These two constraints
mean the created objects cannot have auto storage class. This is a
great loss since auto storage class alone of the three storage class
options allows the clients to decide where the objects live which can
greatly improve locality of reference.
// wibble.c
...
wibble * wopen(int value)
{
wibble opened;
...
return &opened; // very very bad
}
...
A second possibility is to create the objects with static storage class:
// wibble.c
...
static wibble wstorage[42];
static size_t windex = 0;
...
wibble * wopen(int value)
{
wibble * opened = &wstorage[windex];
windex++;
...
return opened;
}
...
The final possibility is to create the objects with allocated storage class. That is,
to create the objects dynamically on the heap:
// wibble.c
...
wibble * wopen(int value)
{
wibble * opened = malloc(sizeof *opened);
...
return opened;
}
...
The static and the allocated approaches have opposing advantages and disadvantages.
Static storage is very fast and doesn't fragment the memory but the type has to decide
the maximum number of objects the application will need. That might be a dependency going in the wrong direction.
Allocated storage is much slower and can create memory fragmentation issues, but
the application decides how many objects it needs.
In short, the classic ADT technique creates an abstraction that is
very opaque and pays a hefty price for this "over-abstraction".
Abstracting away the representation also abstracts away the size
details of a type and it is the loss of the size information that
creates the storage class restrictions.
The Shadow Data Type implementation technique attempts to rebalance
these forces of abstraction by separating size abstraction from representation abstraction.
Shadow Data Types
The term Shadow Data Type, in contrast to Opaque Data Type, is not a
well established term.
The technique I'm calling Shadow Data Type has probably been around for
a long time, it's just that it doesn't seem to have ever been
documented anywhere and so a term for it has never become established.
I've chosen the term Shadow Data Type to try and convey the idea that
when you shine a light
on an object it casts a shadow which reveals something of the size
of the object but nothing of the details of the object.
In other words, a Shadow Data Type has a "full" type declaration
(rather than a forward type declaration) but one revealing only the
size of type.
// wibble.h
typedef struct
{
unsigned char size_shadow[16];
} wibble;
void wopen(wibble *, int);
...
void wclose(wibble *);
The "true" definition of the type (together with its accompanying #includes) moves into the source file:
// wibble.c
#include "wibble.h"
#include "grommet.h"
#include "flange.h"
#include <string.h>
typedef struct
{
grommet g;
flange f;
} wibble_rep;
// sizeof(wibble) >= sizeof(wibble_rep)
void wopen(wibble * w, int value)
{
wibble_rep rep;
...
...
memcpy(w, &rep, sizeof rep);
}
...
However, there are two problems needing attention.
Synchronized Alignment?
Firstly, there is no guarantee the two types (wibble and wibble_rep)
are alignment compatible. We can solve this problem. The trick is to
create a union containing all the basic types. We don't know which
basic types have the strictest alignments but if the union contains
them all the union must also have the strictest alignment.
// alignment.h
typedef union
{
// one of each of all the basic types go here
// including data pointers and function pointers
} alignment;
We redefine wibble to be a union with two members; one member to take care of the
memory footprint and one member to take care of the alignment:
// wibble.h
#include "alignment.h"
typedef union
{
unsigned char size_shadow[16];
alignment universal;
} wibble;
...
The main problem with wibble being a union is that unions are rare.
Suppose you want to forward declare the wibble type in a header. You're
quite likely to forget it's a union.
typedef struct wibble wibble; // Oooops
We can fix this by simply putting the union inside a struct!
// wibble.h
#include "alignment.h"
typedef struct
{
union
{
unsigned char size[16];
alignment universal;
} shadow;
} wibble;
...
This is now sufficiently tricky to warrant an abstraction of its own:
// shadow_type.h
#ifndef SHADOW_TYPE_INCLUDED
#define SHADOW_TYPE_INCLUDED
#include "alignment.h"
#define SHADOW_TYPE(name, size) \
typedef struct \
{ \
union \
{ \
unsigned char bytes[size]; \
alignment universal; \
} shadow; \
} name
#endif
// wibble.h
#include "shadow_type.h"
SHADOW_TYPE(wibble, 16);
Synchronized Size?
The second problem is hinted at by the comment in wibble.c
// sizeof(wibble) >= sizeof(wibble_rep)
This comment, like all comments, has no teeth. Ideally we'd like an
assurance that if the types' sizes lose synchronization we're told about
it. This can be done by asserting the relationship inside a unit test
of course. The problem with this the possibility that the runtime check
inside a unit-test won't get run. Or, more likely, that the unit-test simply won't
get written at all. Fortunately in this case we can check the
relationship using a compile time assertion.
We start with the fact that you cannot declare an array of negative size:
extern char wont_compile[-1];
extern char will_compile[+1];
Now we have to select a size of either +1 or -1 if the asserted expression is true or false respectively.
// may or may not compile
extern char compile_time_assert[sizeof(wibble) >= sizeof(wibble_rep) ? +1 : -1];
Hiding this mechanism behind a macro inside a dedicated header helps to make the code more Intention Revealing.
// compile_time_assert.h
#define COMPILE_TIME_ASSERT(description, expression) \
extern char description[ (expression) ? 1 : -1 ]
// wibble.c
...
#include "compile_time_assert.h"
...
COMPILE_TIME_ASSERT(sizeof_wibble_is_not_less_than_sizeof_wibble_rep,
sizeof(wibble) >= sizeof(wibble_rep));
...
It's worth spending a few moments to think about alignment carefully. The wibble type contains a union to give us the strictest alignment. This means a single wibble_rep and a single wibble can overlay each other in either direction.
If we create an array of wibbles the compiler will ensure the address of each wibble is suitably aligned. To do this it may add trailing padding to the wibble type but this padding will be reflected by sizeof(wibble). Similarly, any padding for the wibble_rep type will also be reflected by sizeof(wibble_rep).
Importantly, since sizeof(wibble_rep) may be strictly less than sizeof(wibble) we cannot overlay an array of either type directly onto an array of the other type.
However, we are only concerned with creating an array of wibbles since that is the type the client uses. There should never be any need to create an array of wibble_reps. Nevertheless, the .c file implementation must always do any array pointer arithmetic in terms of wibbles and never in terms of wibble_reps.
Note also that using >= rather than == also allows binary compatibility with any alternative smaller representation.
Casting the shadow
Inside the source file we can create a helper function to overlay the true representation
onto the clients memory (the fragment below uses the dot designator syntax introduced in c99):
// wibble.c
static inline void shadow(wibble * dst, wibble_rep * src)
{
memcpy(dst, src, sizeof *src);
}
bool wopen(wibble * w, const char * name)
{
wibble_rep rep =
{
.g = ...,
.f = ...,
};
shadow(w, &rep);
...
}
Careful use of memcpy can help to make the wibble functions behave atomically from the users perspective. That is to say, the function can do the work off to the side in a local wibble_rep, and copy
back into the shadow only if everything is successful.
An alternative to memcpy is to cast the pointer on each access:
// wibble.c
static inline wibble_rep * light(wibble * w)
{
return (wibble_rep *)w;
}
void wclose(wibble * w)
{
wibble_rep * rep = light(w);
rep->g = ...;
rep->f = ...;
...
}
Constness?
It makes no sense to declare a wibble object with a const modifier unless the object can be initialized.
void pointless(void)
{
const wibble w; // :-(
// ... ?
}
However, this is not an issue since the wibble type is opaque anyway.
Nevertheless, a slight redesign can accommodate const wibble
objects if desired, at the cost of copying struct objects:
...
wibble wopen(int value)
{
wibble_rep rep = { ...value... };
wibble w;
memcpy(&w, &rep, sizeof rep);
return w;
}
void ok(void)
{
const wibble w = wopen(42);
...
}
Summary
In C it is impossible to expose a type's size without also exposing its representation. It is possible to define a type concretely and to explicitly specify its representation as being "unpublished". However, since C does not offer the C++ private keyword using the representation is always possible and remains a constant temptation. Once one piece of client code succumbs more are sure to follow and like a dam bursting the client and implementation quickly become tightly coupled and any separation is washed away.
Completely hiding a type's representation behind an opaque pointer/handle removes the temptation and creates a powerful abstraction but at the price of hiding the size of the type and the consequent restriction on the storage class of client memory.
A shadow data type offers a half-way house where a type is effectively split into two, with one part exposing the size and the other part holding the representation. The alignment and sizes of the two parts must correspond. Client code is then able to use all three storage class options. The implementation code takes the full load of the extra complexity mapping/overlaying between the split parts. One interesting observation is that the client code would be uneffected (other than needing recompilation) if the representation was moved back into the client side type (to try and improve performance perhaps).
No mechanism is universally applicable and the shadow data type is no exception! Experience and time alone will tell if and how useful it is. Caveat emptor.
is the title of another excellent book by Dan Pink.
As usual I'm going to quote from a few pages:
