Practical packing for structs of bytes

[Michael Henry]

All,

(Note: This is a repost from comp.lang.c.moderated, in the hopes
that a wider audience might provide more information. That
thread may be found here:
http://groups.google.com/group/comp.lang.c.moderated/browse_frm/thread/4b422712201764c6
)

I've got a design for protocol processing that uses structs
containing only uint8_t and arrays of uint8_t, along with nested
structs that are similarly constructed. These structs are
overlaid onto a buffer containing a protocol header, providing
convenient access to the protocol fields using struct syntax.
Endian conversions are handled via macro accessors for
multi-byte fields. The technique applies to unions as well as
structs.

For example:

/* Represents a 16-bit Big-Endian field. */
typedef struct BigU16
{
uint8_t raw_BigU16[2];
} BigU16;

/* Overlaid onto a buffer containing a protocol header. */
typedef struct ProtocolHeader
{
uint8_t payloadType;
BigU16 payloadSize;
} ProtocolHeader;

uint8_t *buf = ...buffer of raw protocol bytes...;

ProtocolHeader *p = (ProtocolHeader *) buf;

uint8_t type = p->payloadType;
uint16_t size = GetBigU16(p->payloadSize);

Byte-sized fields may be manipulated directly (e.g., the
payloadType field above). Macros such as GetBigU16() take care
of accessing misaligned multi-byte fields and performing Endian
conversions. Because multi-byte fields are stored as structs of
arrays, it's difficult to accidentally bypass the necessary
accessor macros and touch the raw data directly. It's also
impossible to extract a field using the wrong size or
Endianness.

For this idea to work, the compiler must not introduce padding
in the struct or place additional alignment constraints on the
structs. I recognize that standard C sadly does not provide a
uniform way to request "packed" structs for this situation;
however, in many practical cases, the above design can be made
to work with real-world compilers. For example:

- A #pragma may be available to pack individual structs
(e.g., Microsoft's Visual C++ compiler family).

- A declaration modifier may be available to pack individual
structs (e.g., gcc's __attribute__((packed)) feature).

- The compiler may avoid excess alignment and padding based on
"natural" field alignment requirements without the need for
any special directives, because the structs are built only of
bytes.

Though a bit ugly, I can declare the structs as follows:

#include "pack_1.h"

typedef PACKED_STRUCT(ProtocolHeader)
{
uint8_t payloadType;
BigU16 payloadSize;
} ProtocolHeader:

#include "pack_def.h"

where the PACKED_STRUCT() macro provides a compiler-dependent
decoration such as __attribute__((packed)), and the pack_xxx.h
headers supply compiler-dependent #pragmas if needed, switching
between one-byte packing and the system default.

Ultimately, I'd like to know whether the above hacks are
sufficient to avoid problems with practical compilers I'm likely
to encounter, now and in the foreseeable future. We have a
large degree of control over the choice of compilers in my
immediate office, but I'd like our code to be usable by sister
organizations that have less control over their tools. While
it's difficult to say exactly which compilers we'll encounter, I
expect them all to be "practical" compilers meant to serve
real-world needs of customers, not the intentionally perverse
theoretical compilers meant to test the bounds of the standard
(since I know that a purely standards-conforming compiler
rejects outright the basis of my design).

My questions are:

- What existing compilers and associated environments that would
not work with the above scheme?

- Are there trends either toward or away from the current level
of support for controlling struct packing (such as future ISO
standard support for it, or a likelihood that compilers would
*stop* providing such support, or stop providing "natural"
alignment)?

- Is there another way to provide the elegance of the struct
technique while remaining truly portable?

From reading the gcc source code, I understand that Linux
internally relies on the "natural" alignment properties of
structs, so compilers for Linux probably have to support that
feature, which might be a reason to think that compilers would
continue to provide the padding-related support my design
requires.

Thanks,
Michael Henry

The above question generated the following reply from lacos in the
comp.lang.c.moderated thread:

- A #pragma may be available to pack individual structs (e.g.,
Microsoft's Visual C++ compiler family).

Oracle Solaris Studio has "#pragma pack(n)" and "-xmemalign=ab":

http://docs.sun.com/app/docs/doc/821-1384/bjacr?l=en&a=view

As a matter of interest, I checked the installed documentation of an
"HP C
V7.1-015 on OpenVMS Alpha V8.3" instance, and sure enough, it says

CC

Language_topics

Preprocessor

#pragma

#pragma [no]member_alignment[_m|_nm]

Tells the compiler to align structure members on the
next
boundary appropriate to the type of the member rather
than
the next byte. For example, a long variable is aligned
on
the next longword boundary; a short variable on the next
word boundary.

Syntax:

#pragma nomember_alignment [base_alignment]
#pragma member_alignment [save | restore]

The optional base_alignment parameter can be used with
#pragma nomember_alignment to specify the base alignment
of the structure. Use one of the following keywords to
specify the base_alignment:

o BYTE (1 byte)

o WORD (2 bytes)

o LONGWORD (4 bytes)

o QUADWORD (8 bytes)

o OCTAWORD (16 bytes)

The optional save and restore keywords can be used to
save
the current state of the member_alignment and to restore
the previous state, respectively. This feature is
necessary for writing header files that require
member_alignment or nomember_alignment, or that require
inclusion in a member_alignment that is already set.

lacos

 

[Ersek, Laszlo]

uint8_t *buf = ...buffer of raw protocol bytes...;

ProtocolHeader *p = (ProtocolHeader *) buf;

I wanted to add before: dependent on the placeholder code that provides
the initializer to "buf", this may still invoke undefined behavior,
in-effect implementation-dependent "structure packing" notwithstanding.

Additionally, you'll probably cast "buf" again to another pointer type,
based on payloadType (the "record discriminator"). One of two ways is
required for that:

1)

struct payload
{
struct protocol_header hdr;
union
{
struct { ... } t1;
struct { ... } t2;
...
} u;
};


2)

union u
{
struct
{
struct protocol_header hdr;
...
} t1;

struct
{
struct protocol_header hdr;
...
} t2;

...
};

(Too lazy to look up references now, sorry!)

I was also thinking about how you could usefully employ flexible array
members. They wouldn't work with option #1, because a struct ending with a
flexible array member can't be placed in another struct. They would work
with option #2 though.

In the end I couldn't concoct a good, succinct use case for flexible array
members in various packet types, and gave up on this part of my post. So
this is just a raw brain dump now.

I believe without introspection capabilities, people tend to describe
"network structures" with small dedicated languages, and generate
structure declarations and (de)serialization code from that. I'm reminded
of:

http://en.wikipedia.org/wiki/Protocol_Buffers
http://en.wikipedia.org/wiki/Interface_description_language

The output of such generators can be portable C source.

lacos

 

[Jorgen Grahn]

.

I've got a design for protocol processing that uses structs
containing only uint8_t and arrays of uint8_t, along with nested
structs that are similarly constructed. These structs are
overlaid onto a buffer containing a protocol header, providing
convenient access to the protocol fields using struct syntax.
Endian conversions are handled via macro accessors for
multi-byte fields. The technique applies to unions as well as
structs. ....
Byte-sized fields may be manipulated directly (e.g., the
payloadType field above). Macros such as GetBigU16()

Why not inline functions? Safer, just as efficient, standardized back
in the 1990s.

(GetBigU16() should be called GetU16() by the way -- the thing it gets
is a native uint16_t, from the caller's point of view.)

take care
of accessing misaligned multi-byte fields and performing Endian
conversions. Because multi-byte fields are stored as structs of
arrays, it's difficult to accidentally bypass the necessary
accessor macros and touch the raw data directly. It's also
impossible to extract a field using the wrong size or
Endianness.

That is indeed a Good Thing.

....

- Is there another way to provide the elegance of the struct
technique while remaining truly portable?

I agree it's more elegant than trying to map general structs only
octet buffers from/to the network, but I /really/ think you're better
off treating these as just arrays of unsigned char. Which means
writing parsers on a case-by-case basis.

I've done this many times, for different protocols, and it's not hard
or even ugly -- if you isolate it and make good use of helper
functions similar to your GetU16() (that scheme can by the way be
extended to user-defined types for even more elegance).

The parts that *are* hard have to do with the semantics of the message,
and that's something your design doesn't help with -- you have to deal
with that when you're using your nested struct of uint8_t.

/Jorgen

 

[Michael Henry]

On Fri, 2010-09-17, Michael Henry wrote:

...


Why not inline functions? Safer, just as efficient, standardized back
in the 1990s.

In-house coding standards require C89 compatibility for wide
portability, so we can't assume the presence of inline
functions; however, I do see the irony that we'd worry about
inline not being standard, yet contemplate using packed structs

(GetBigU16() should be called GetU16() by the way -- the thing it gets
is a native uint16_t, from the caller's point of view.)

I'd have preferred GetU16, but I initially didn't see how I
could differentiate Big-Endian and Little-Endian fields from a
single macro. In fact, I'd have preferred a single function or
macro that would perform the correct Endian conversion and
return an integer of the right size. Returning a different type
still seems problematic, but your comment caused me to think a
little more about the Big- vs. Little-Endian aspect. I believe
I could make a compile-time determination about the Endian of a
field by "encoding" this information in the size of an array:

typedef union BigU16
{
uint8_t raw_U16[2];
char endian[2]; /* "2" means Big-Endian. */
} BigU16;

typedef union LittleU16
{
uint8_t raw_U16[2];
char endian[1]; /* "1" means Big-Endian. */
} LittleU16;

This would allow something like this:

#define GetU16(field) (sizeof((field).endian) == 1 ? \
GetLittleU16(field) : GetBigU16(field))

I don't know how to accomplish this kind of type-based
"overloading" using just functions.

I agree it's more elegant than trying to map general structs only
octet buffers from/to the network, but I /really/ think you're better
off treating these as just arrays of unsigned char. Which means
writing parsers on a case-by-case basis.

Though I really like the struct technique, I think you're right.
For our most portable code, we should avoid overlaying structs
onto byte arrays.

Thanks,
Michael Henry

 

[Michael Henry]

I wanted to add before: dependent on the placeholder code that provides
the initializer to "buf", this may still invoke undefined behavior,
in-effect implementation-dependent "structure packing" notwithstanding.

Is the undefined behavior due to alignment restrictions on the
struct, or was there something else? I'd been intending to
initialize buf to point to an arbitrary offset into the array of
bytes from the wire:

uint8_t bytesFromWire[MAX_PACKET_SIZE];
 uint8_t *buf = &bytesFromWire; /* "i" is any in-range value. */

Additionally, you'll probably cast "buf" again to another pointer type,
based on payloadType (the "record discriminator"). One of two ways is
required for that:

1)

struct payload
{
   struct protocol_header hdr;
   union
   {
     struct { ... } t1;
     struct { ... } t2;
     ...
   } u;

};

2)

union u
{
   struct
   {
     struct protocol_header hdr;
     ...
   } t1;

   struct
   {
     struct protocol_header hdr;
     ...
   } t2;

   ...

};

I believe without introspection capabilities, people tend to describe
"network structures" with small dedicated languages, and generate
structure declarations and (de)serialization code from that. I'm reminded
of:

http://en.wikipedia.org/wiki/Protocol_Buffers
http://en.wikipedia.org/wiki/Interface_description_language

Thanks for the links. We've been considering the use of Google
Protocol Buffers for other portions of our code. They may well
be a good fit for things like RPC handlers, where the entire
inbound set of parameters is demarshaled en masse, processing
occurs on the inputs and new outputs are generated, then the
entire outbound set of paramters is marshaled en masse to the
network. But the struct overlay technique is particularly
appealing in cases where a fully marshaled packet must be
examined in a random field or two, with perhaps another field or
two being modified before the packet is passed along (e.g., the
code to route a packet based on its destination address). It's
very convenient to have direct access to arbitrary fields as
needed without demarshaling the entire protocol header.
Nevertheless, I think the struct overlay technique is just out
of reach for "portable" code.

Thanks,
Michael Henry

 

[Ian Collins]

I wanted to add before: dependent on the placeholder code that provides
the initializer to "buf", this may still invoke undefined behavior,
in-effect implementation-dependent "structure packing" notwithstanding.

Is the undefined behavior due to alignment restrictions on the
struct, or was there something else? I'd been intending to
initialize buf to point to an arbitrary offset into the array of
bytes from the wire:

uint8_t bytesFromWire[MAX_PACKET_SIZE];
uint8_t *buf =&bytesFromWire; /* "i" is any in-range value. */

The arbitrary offset may not be correctly aligned for types with a size > 1.

It looks like you are leaning towards the sensible option of not
attempting to overlay structures on arrays of bytes!

I once had to port some code from an embedded system which supported
packed structs to a hosted environment that did not. The result wasn't
pretty. You are definitely better of with explicit demarshalling code.

 

[Ersek, Laszlo]

Is the undefined behavior due to alignment restrictions on the struct,

Yes, that's what I had in mind.

Cheers,
lacos

 

[Michael Henry]

The arbitrary offset may not be correctly aligned for types with a size > 1.

The novelty (novel to me, at least) of my proposed approach is
to use only unsigned char and arrays of unsigned char inside
these structs, as well as embedded structs similarly
constructed. The intent was to avoid primitive data types with
size greater than one, so that there wouldn't be any alignment
worries as long as the compiler didn't spuriously add needless
alignment or padding restrictions. This is of course not a
portable construct, but I was hoping that a quality compiler
implementation would avoid padding and alignment restrictions
because I'm using only unsigned chars. Of course, this is
predicated on having structs that track the alignment
requirements of their contained fields. I'd hoped to avoid the
need for compiler-dependent pragmas or attributes on the struct
declarations on the theory that no compiler would do other than
the "sensible" thing described above. Naturally, I was bitten
almost immediately by gcc 3.4.6 for eCos on the ARM
architecture. In this build of gcc, structs are always 32-bit
aligned regardless of their contained fields. Reading the gcc
source code, I saw that this is required by the ARM reference
manual. I'd done my testing with gcc for Linux on the ARM,
where my assumptions about "quality" compilers held. Comments
in the gcc source code also mentioned broken code within NetBSD
that made my above assumptions about naturally aligned structs
requiring only naturally required padding and alignment. So gcc
grudgingly sets the minimum required struct padding to 8 bits
for NetBSD and Linux, since in those environments too much code
relies on this behavior. This convinced me that I'd at least
need to invoke pragmas or attributes on certain compilers, since
my hope of naturally aligned chars was clearly dashed. I'd
still hoped that someone with more insight into trends would be
able to make a slam-dunk case one way or the other. A post
claiming that Very-Popular-Environment has no packing capability
whatsoever and fails with the proposed technique, or
alternatively that the standards committee were planning to add
standardized packing support, would perhaps have made it easier
to decide.

It looks like you are leaning towards the sensible option of not
attempting to overlay structures on arrays of bytes!

Yes. We'd stopped using general overlaid structs years ago due
to portability concerns. I'd revived consideration of the idea
when I'd thought of the possibility of using only unsigned
chars, hoping that this limited choice of fields would make
things enough more portable. But the standard gives too much
freedom to compiler implementers, such that I don't feel
comfortable making the assumptions necessary to use this
technique in our most portable code.

Thanks to all for their helpful advice and suggestions,
Michael Henry

 

[Jorgen Grahn]

In-house coding standards require C89 compatibility for wide
portability, so we can't assume the presence of inline
functions; however, I do see the irony that we'd worry about
inline not being standard, yet contemplate using packed structs

But seriously, maybe it's time to review those standards. Inline
is so nice -- especially for readability: it no longer costs
performance to break out duplicated code.

I'd have preferred GetU16, but I initially didn't see how I
could differentiate Big-Endian and Little-Endian fields from a
single macro.

I assumed you only had two kinds: the big-endian world, and your
native endianness:

inside outside
------------------
native <-- big-endian (get)
native --> big-endian (put)

You probably rarely want other combinations than that (the socket API
struct in_addr and a few more are exceptions -- they are supposed to
be stored, in C, as big-endian uint32_t etc.)

....

Though I really like the struct technique, I think you're right.
For our most portable code, we should avoid overlaying structs
onto byte arrays.

Ah, good.

/Jorgen

 

[Michael Henry]

But seriously, maybe it's time to review those standards. Inline
is so nice -- especially for readability: it no longer costs
performance to break out duplicated code.

I've been looking for a smooth way to have inline on platforms
where it's supported, and degenerate into regular functions on
other systems to keep the C89 compatibility. Something like
using a macro that's defined to "inline" on supported systems,
and empty on others. I've not yet spent enough time to find a
sufficiently elegant solution. Changing the shared in-house
coding standards to allow C99 impacts several offices outside
our own, making it a more complex undertaking. It's also
another hard-to-forecast question: Will we need to run on a
pre-C99 compiler without inline? Like asking how many compilers
can't do packed structs, it's hard to find out how many
compilers can't do inline. Since inline is just a performance
booster, we can consider it optional and use it only when
available on a given platform.

I assumed you only had two kinds: the big-endian world, and your
native endianness:

For the most part, that's true, since most of the protocols we
process use the standard network-Endian convention. But we also
process some protocols with Little-Endian fields on the wire, so
we need to handle both kinds. At least we don't have to deal
with Vax-Endian or any other crazy variations

Mike

 

[Keith Thompson]

For the most part, that's true, since most of the protocols we
process use the standard network-Endian convention. But we also
process some protocols with Little-Endian fields on the wire, so
we need to handle both kinds. At least we don't have to deal
with Vax-Endian or any other crazy variations

I don't think the VAX is particularly odd as far as endianness is
concerned; you're probably thinking of the PDP-11.

 

[Michael Henry]

I don't think the VAX is particularly odd as far as endianness is
concerned; you're probably thinking of the PDP-11.

Yes, indeed; thanks for the correction.

Michael Henry

 

[lawrence.jones]

I don't think the VAX is particularly odd as far as endianness is
concerned; you're probably thinking of the PDP-11.

VAX Floating-point is "middle endian", just like the PDP-11.
All the integer types are little endian.