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 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.