Is alignment union necessary for memory allocation header?

Question

In K&R2 they implement memory allocator in chapter 8. For each block there is header defined something like this (from memory, code may be non-exact):

union header_t
{
  struct 
  {
     unsigned size;
     unsigned* next; 
  };

  long align;
};

They do this to "make sure that the header is properly aligned on the boundaries of long". But doesn't the union align by the largest member? The struct is larger than the single align member, so the header will be aligned on the struct's multiples anyway, no?

What about when the struct is even larger (say it has many members). Is this alignment union trick always required in when write a memory allocator?

Answer 1

The size of these datatypes is platform dependent. I guess that the two unsigned members of the struct are 16 bits and the long align is 32 bits or two 32 bit members in the struct and 64 bits for the long.

Alignment boundaries would be either 32 or 64 bits

Answer 2

"The struct is larger than the single align member".

First, says who? What if, on your implementation, unsigned and unsigned* are each 32 bits, and long is 128 bits (or more realistically, 16 bits and 64 bits)?

Second, so what? Even if the struct is at least as big as long, it doesn't mean that it must have at least as big an alignment as long. If unsigned and unsigned* have no alignment requirements, then the struct has no alignment requirements. But perhaps long does.

Answer 3

The data type in K&R is:

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

  Align x;
};

Let's say we had this instead:

union header_t
{
  struct 
  {
     union header_t *next; 
     unsigned size;
  } s;
};

(By the way, you need a name for the struct variable and also change the pointer inside the struct to type union header_t *, because the data structure is a linked list.)

K&R's malloc() implementation reserves a chunk of space, and then uses this to maintain free store. When this malloc is called, it finds on the free list a place that has enough space, and returns a pointer to that tail end of it.

In particular, the relevant part of the code is:

typedef union header Header;
static Header base;
Header *p = &base;
...
p += p->s.size;
return (void *)(p+1);

Note that we are returning p+1 (cast to void *), so we have to make sure that this pointer is aligned for any data type. Since p itself is pointing to a Header *, we have to make sure that when we add sizeof(Header) to an aligned pointer, we get another aligned pointer back (remember, p+1 points to sizeof(Header) bytes from p). This requirement means that Header has to be aligned for all types of data.

The struct inside Header might not be aligned for the widest type possible. To make sure that our Header type is so aligned, we add a member to the union that we know to be maximally aligned, i.e., is the widest type on a given machine. K&R assume that this type is long. Also, note that it does not matter if the size of Header is greater than the size of Align type. The assumption here is that Align type here is a type with the strictest alignment requirements, not that it be huge.

Interestingly, we need to assume a 'maximally aligned' type because the C standard requires alignment for any type from pointers returned by malloc, but does not specify a portable way to find out what that alignment is going to be. If the standard did specify such a type, one could have used that type instead of long for Align.