Alignment in C99 for Program-Defined Allocation

[Shao Miller]

In C99, is it possible to write a well-defined program which
implements its own memory allocation in an alignment-responsible way,
without using the C99 memory management functions?

For example, out of some pool with 'static' storage duration? I
cannot figure out how in any pool of 'unsigned char[XXX]', we could
determine the alignment for where a pointer might point to.

C1X looks like it might have '_Alignas' and 'alignof', but even
equipped with these, how might it be accomplished?

 

[chrisbazley]

In C99, is it possible to write a well-defined program which
implements its own memory allocation in an alignment-responsible way,
without using the C99 memory management functions?

For example, out of some pool with 'static' storage duration?  I
cannot figure out how in any pool of 'unsigned char[XXX]', we could
determine the alignment for where a pointer might point to.

enum
{
POOL_SIZE = 1024 /* Allow 1 KB to be allocated */
};

static char pool[POOL_SIZE];
static size_t pool_used = 0;

void *pool_alloc(size_t bytes, unsigned int align_log2)
{
char *block;
size_t alignment;

/* Get pointer to free space */
block = pool + pool_used;

/* Align pointer to nearest equal or higher multiple
of 2 to the power of align_log2. */
alignment = 1 << align_log2;
block = (block + (alignment - 1)) & ~(alignment - 1);

/* Is there enough free space for the allocation? */
if (POOL_SIZE - (block - pool) < bytes)
{
block = NULL; /* Not enough free space */
}
else
{
pool_used = (block - pool) + bytes;
}

return block;
}

A C compiler can't optimise multiplication and division by the
required alignment granularity (here, 2 to the power of 'align_log2')
unless it is a known constant. That is why my function uses bitwise
operators instead of integer multiplication and division. Because the
bitwise method only works for powers of two, I require the caller to
specify the alignment in that form.

Of course, if you need alignment to some multiple of a value that
isn't a power of two then it gets more computationally expensive.

If you're writing a macro rather than a function then you could
instead use ((((block) + ((alignment) - 1)) / (alignment)) *
(alignment)), which has the advantage of being more obvious and
working for all positive values of 'alignment'.

My function wastes less memory than the typical case of calling
malloc() and then aligning a pointer within the allocated block. In
that case, you have to include the maximum possible wastage in the
amount of memory requested. By the time you find out that you can
align to the required granularity and still have bytes free at the end
of the block, it is too late to do anything about it.

All untested and off the top of my head.

 

[Eric Sosman]

In C99, is it possible to write a well-defined program which
implements its own memory allocation in an alignment-responsible way,
without using the C99 memory management functions?

For example, out of some pool with 'static' storage duration? I
cannot figure out how in any pool of 'unsigned char[XXX]', we could
determine the alignment for where a pointer might point to.

For any object type T, the required alignment is a divisor
of sizeof(T). In particular, alignment on a sizeof(T) boundary
is always tight enough, perhaps tighter than needed.

Unfortunately, that doesn't seem to help! Since the family
of potential types in C is open-ended (in C99, even the family of
primitive types is open-ended), you can't just make a union of all
possible T and form your pool from an array of union instances.
Your malloc-equivalent could not be 100% sure that the memory
it returned was suitably aligned for all possible types; the caller
might be using a T you hadn't thought of. You could do it for any
one program, perhaps, by cataloging every type the code uses, but
the maintenance headaches would be simply awful.

The dodge of using a big char[] as the basis of the pool (a
theme you seem unhealthily attracted to) is flawed, the fundamental
problem being that there's no portable way to determine how the
array itself is aligned. I think you just need to accept the fact
that some internals of memory management aren't portable.

 

[chrisbazley]

enum
{
  POOL_SIZE = 1024 /* Allow 1 KB to be allocated */
};

static char pool[POOL_SIZE];
static size_t pool_used = 0;

void *pool_alloc(size_t bytes, unsigned int align_log2)
{
  char *block;
  size_t alignment;

  /* Get pointer to free space */
  block = pool + pool_used;

  /* Align pointer to nearest equal or higher multiple
     of 2 to the power of align_log2. */
  alignment = 1 << align_log2;
  block = (block + (alignment - 1)) & ~(alignment - 1);

  /* Is there enough free space for the allocation? */
  if (POOL_SIZE - (block - pool) < bytes)

This expression is wrong: If (block - pool) > POOL_SIZE then the
result of '(POOL_SIZE - (block - pool))' will be negative, and likely
compare greater than 'bytes'.

It should be:

void *pool_alloc(size_t bytes, unsigned int align_log2)
{
char *block;
size_t alignment, align_used;

/* Get pointer to free space */
block = pool + pool_used;

/* Align pointer to nearest equal or higher multiple
of 2 to the power of align_log2. */
alignment = 1 << align_log2;
block = (block + (alignment - 1)) & ~(alignment - 1);
align_used = block - pool;

/* Is there enough free space for the allocation? */
if (align_used > POOL_SIZE || POOL_SIZE - align_used < bytes)
{
block = NULL; /* Not enough free space */
}
else
{
pool_used = align_used + bytes;
}
return block;
}

(If you're wondering about the reason for these mental gymnastics, I'm
trying to cope with pathological input values of 'bytes' designed to
cause an overflow.)

 

[Shao Miller]

Oops! '(block + (alignment - 1))' is a pointer and thus a constraint
violation for '&', perhaps.

(If you're wondering about the reason for these mental gymnastics, I'm
trying to cope with pathological input values of 'bytes' designed to
cause an overflow.)

I do enjoy your kind offering of this nice code. If we treat
pointers as non-opaque, raw byte addresses, I think something like
this code works quite nicely. I expect this representation to be
fairly common.

Thanks so much, Christopher.

 

[Shao Miller]

In C99, is it possible to write a well-defined program which
implements its own memory allocation in an alignment-responsible way,
without using the C99 memory management functions?

For example, out of some pool with 'static' storage duration?  I
cannot figure out how in any pool of 'unsigned char[XXX]', we could
determine the alignment for where a pointer might point to.

     For any object type T, the required alignment is a divisor
of sizeof(T).  In particular, alignment on a sizeof(T) boundary
is always tight enough, perhaps tighter than needed.

Right. 'sizeof (T)' cannot be a fractional multiple of the alignment
requirement for 'T', otherwise an array has misaligned elements.

     Unfortunately, that doesn't seem to help!  Since the family
of potential types in C is open-ended (in C99, even the family of
primitive types is open-ended), you can't just make a union of all
possible T and form your pool from an array of union instances. Right.

Your malloc-equivalent could not be 100% sure that the memory
it returned was suitably aligned for all possible types; the caller
might be using a T you hadn't thought of.  You could do it for any
one program, perhaps, by cataloging every type the code uses, but
the maintenance headaches would be simply awful.
Right.

     The dodge of using a big char[] as the basis of the pool (a
theme you seem unhealthily attracted to)

It is attractive because: We can work with its elements without trap
representations. We can 'union' it to force alignment based on some
other types. If we have a non-portable notion of the representation
of some type of pointer as a raw byte address in a flat memory model
and address 0 being aligned for any type, that's all that's needed for
alignment, without any 'union'. See Christopher's post, for example.
We can copy objects as 'unsigned char[sizeof I]' ('I' is the
identifier designating an object.)

is flawed, the fundamental
problem being that there's no portable way to determine how the
array itself is aligned.

"Flawed" I'm not sure about. Determination of the array's alignment:
I don't know of a portable way, either.

 I think you just need to accept the fact
that some internals of memory management aren't portable.

It sure looks that way...

 

[Marcin Grzegorczyk]

In C99, is it possible to write a well-defined program which
implements its own memory allocation in an alignment-responsible way,
without using the C99 memory management functions?

For example, out of some pool with 'static' storage duration? I
cannot figure out how in any pool of 'unsigned char[XXX]', we could
determine the alignment for where a pointer might point to.

C1X looks like it might have '_Alignas' and 'alignof', but even
equipped with these, how might it be accomplished?

Assuming the current proposal for alignment specifiers makes it to the
C1X final document without major changes, you could declare the pool as

static _Alignas(max_align_t) unsigned char The_Pool[POOL_SIZE];

and use alignof(max_align_t) when you'd need to align offsets within the
pool.

 

[Shao Miller]

In C99, is it possible to write a well-defined program which
implements its own memory allocation in an alignment-responsible way,
without using the C99 memory management functions?

For example, out of some pool with 'static' storage duration? I
cannot figure out how in any pool of 'unsigned char[XXX]', we could
determine the alignment for where a pointer might point to.

C1X looks like it might have '_Alignas' and 'alignof', but even
equipped with these, how might it be accomplished?

Assuming the current proposal for alignment specifiers makes it to the
C1X final document without major changes, you could declare the pool as

static _Alignas(max_align_t) unsigned char The_Pool[POOL_SIZE];

and use alignof(max_align_t) when you'd need to align offsets within the
pool.

Most excellent and most appreciated, Marcin. I'll have to dig
through the current draft and see if '_Alignas' can be used for compound
literals, too.

 

[Richard Bos]

In C99, is it possible to write a well-defined program which
implements its own memory allocation in an alignment-responsible way,
without using the C99 memory management functions?

A program, yes, because in a single program you know all the types that
program uses.

A generic library, no, because some program somewhere on some
implementation is going to use intfast59_t which has 67-byte alignment
for some arcane reason.

A library specific to a single implementation, I _think_ it's possible,
but I don't guarantee that there are no subtle points somewhere deep
within the Standard which make it theoretically impossible.

Richard