What am I missing from this K&R sample?

Question

The following is an excerpt from a code sample in K&R's The C Programming Language (section 8.7):

typedef long Align;

union header {
    struct {
        union header *ptr;
        unsigned size;
    } s;
    Align x;
};

typedef union header Header;

And here is the explanatory excerpt:

To simplify alignment, all blocks are multiples of the header size, and the header is aligned properly. This is achieved by a union that contains the desired header structure and an instance of the most restrictive type, which we have arbitrarily made a long.

So, as I understand it, the idea is to ensure that a header instance takes up a number of bytes that is a multiple of sizeof(Align). The goal makes perfect sense to me.

But consider the case where long is 64 bits, int is 32 bits, and a pointer is 64 bits. In that case, header.s will be 64+32 = 96 bits. Thus, sizeof(header) will be 96 bits, which is not a multiple of 64 as intended.

In such a case, I suppose it would be necessary to define Align as something else (perhaps double). But I'm not quite sure whether I'm fully understanding what would dictate that choice for a particular architecture. Is it just the "biggest" type? And what if long is the biggest type - couldn't it fail to work in the way I described above?

Thanks

score 3 · Accepted Answer · edited Mar 22 '11 at 21:42

3

The compiler will adjust the size of header so that ptr, size, and x can all be retrieved efficiently from elements in a header[] array. On most architectures, the presence of x means that sizeof(header) will be increased to a multiple of sizeof(long).

edited Mar 22 '11 at 21:42

Matteo Italia

123,740
17
206
299

answered Mar 22 '11 at 21:08

kevin cline

2,608
2
25
38

score 3 · Answer 2 · answered Mar 22 '11 at 21:52

The size of a union is at least as large as the size of its largest member. So, even if sizeof(s) is 12 and sizeof(long) is 8, as in your example, you will still have sizeof(header) >= 12. Likewise, the alignment of a union is largest alignment of any of its members, so the presence of the long member ensures that the alignment of header is at least the alignment of long, which would be 8 in this case.

If you compile this code, you will almost certainly find that sizeof(header) is 16, not 12. The reason is that if you have an array of header objects, the compiler needs to ensure that the alignment of any of the members is proper, and arrays are stored contiguously in memory. In order to achieve that, the size needs to be a multiple of the alignment. The compiler does that by adding an extra 4 bytes of padding to the end of a header object.

score 1 · Answer 3 · answered Mar 22 '11 at 21:14

It has been a long time since I worked with structs. But, I did use them a fair bit. The main principle was to arrange members in descending alignment size order.

At the time this was written, long would align on the largest addressing boundary. I believe this is still the case, but I haven't followed hardware issues for a long time. Some hardware was designed so that longs were not efficiently addressed unless their address aligned with the size of long.

I believe the intent is that header will align on the next efficient addressing boundary for a long. This is hardware dependent. If longs are efficiently addressable on 32 bit boundaries, then the struct will align appropriately. If longs are only efficiently addressable on 64 bit boundaries, then the struct will consume 128 bits to align appropriately.

Members are never rearranged or reordered -- that is forbidden by the C standard. Instead, the compiler can (and often does) insert padding bytes between members and after the last member to make alignment more favorable. — Adam Rosenfield, Mar 22 '11 at 21:45
@Adam Rosefield: Hence when a programmer creates a struct they arrange fields in decreasing alignment size. I didn't intent to imply that the compiler would do so. byte, long, byte, long would be space inefficient. long, long, byte, byte would be more space efficient. Space efficiency is less of an issue these days. — BillThor, Mar 22 '11 at 21:56

score 0 · Answer 4 · answered Mar 22 '11 at 20:21

0

It's been a long time (way too long) since I read the K&R book, but I believe you are right. You would need to typedef Align to something at least the size of pointer on the platform in question + sizeof unsigned.

My guess is that when this was written (and last updated), 32-bit OS's reigned supreme and your scenario escaped the writers and editors. Of course, they are much smarter/wiser and I and I could be off the mark.

answered Mar 22 '11 at 20:21

DevSolo

667
4
9

Worse than that: when K&R was last updated, `(int)` was still 16 bits. (Hm, pre-ANSI K&R, that is. I wonder if this was ever revisited.) – geekosaur Mar 22 '11 at 20:57

score 0 · Answer 5 · answered Mar 23 '11 at 02:02

To be correct, sizeof(Align) must be greater or equal to sizeof(s). But today's compiler really don't care, and do the job for you.

#include <limits.h>
#include <stdio.h>

typedef long Align;

typedef union header {
    struct {
        union header *ptr;  /* 64 bits */
        unsigned size;    /* 32 bits */
    } s;                    /* subtotal 96 */
    Align x;                /* 64 bits -> should be greater than 96 */
} Header;                  /* total 128 bits */

typedef struct hair {
    union header *ptr;  /* 64 bits */
    unsigned size;      /* 32 bits */
} Hair;              /* subtotal 96 */

int main(void)
{
    Header u;
    Hair h;

    printf("char %ld bits, %ld bytes\n", sizeof(char)*CHAR_BIT,(sizeof(char)*CHAR_BIT)/8);
    printf("unsigned %ld bits, %ld bytes\n", sizeof(unsigned)*CHAR_BIT,(sizeof(unsigned)*CHAR_BIT)/8);
    printf("int %ld bits, %ld bytes\n", sizeof(int) * CHAR_BIT, (sizeof(int) * CHAR_BIT)/8);
    printf("long int %ld bits, %ld bytes\n", sizeof(long) * CHAR_BIT, (sizeof(long) * CHAR_BIT)/8);
    printf("long long int %ld bits, %ld bytes\n", sizeof(long long) * CHAR_BIT, (sizeof(long long) * CHAR_BIT)/8);
    printf("float %ld bits, %ld bytes\n", sizeof(float) * CHAR_BIT, (sizeof(float) * CHAR_BIT)/8);
    printf("double %ld bits, %ld bytes\n", sizeof(double) * CHAR_BIT, (sizeof(double) * CHAR_BIT)/8);
    printf("long double %ld bits, %ld bytes\n\n", sizeof(long double) * CHAR_BIT, (sizeof(long double) * CHAR_BIT)/8);
    printf("Header u %ld bits, %ld bytes\n", sizeof(u) * CHAR_BIT, (sizeof(u) * CHAR_BIT)/8);
    printf("Header *ptr %ld bits, %ld bytes\n", sizeof(u.s.ptr) * CHAR_BIT, (sizeof(u.s.ptr) * CHAR_BIT)/8);
    printf("Header size %ld bits, %ld bytes\n", sizeof(u.s.size) * CHAR_BIT, (sizeof(u.s.size) * CHAR_BIT)/8);
    printf("Header x %ld bits, %ld bytes\n\n", sizeof(u.x) * CHAR_BIT, (sizeof(u.x) * CHAR_BIT)/8);
    printf("Hair h %ld bits, %ld bytes\n", sizeof(h) * CHAR_BIT, (sizeof(h) * CHAR_BIT)/8);
    printf("Hair *ptr %ld bits, %ld bytes\n", sizeof(h.ptr) * CHAR_BIT, (sizeof(h.ptr) * CHAR_BIT)/8);
    printf("Hair size %ld bits, %ld bytes\n", sizeof(h.size) * CHAR_BIT, (sizeof(h.size) * CHAR_BIT)/8);
    return 0;
}

The output is:

$ ./union-limits 
char 8 bits, 1 bytes
unsigned 32 bits, 4 bytes
int 32 bits, 4 bytes
long int 64 bits, 8 bytes
long long int 64 bits, 8 bytes
float 32 bits, 4 bytes
double 64 bits, 8 bytes
long double 128 bits, 16 bytes

Header u 128 bits, 16 bytes
Header *ptr 64 bits, 8 bytes
Header size 32 bits, 4 bytes
Header x 64 bits, 8 bytes

Hair h 128 bits, 16 bytes
Hair *ptr 64 bits, 8 bytes
Hair size 32 bits, 4 bytes

As you can see, Hair is the same size of Header. But for compilers that don't do the job, the correct is to use long double as Align.

Take care, Beco.

What am I missing from this K&R sample?

5 Answers5

Linked