Alignment in C99 for Program-Defined Allocation

Discussion in 'C Programming' started by Shao Miller, Aug 7, 2010.

  1. Shao Miller

    Shao Miller Guest

    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?
     
    Shao Miller, Aug 7, 2010
    #1
    1. Advertising

  2. Shao Miller

    Guest

    On Aug 7, 12:57 pm, Shao Miller <> wrote:
    > 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.

    --
    Christopher Bazley
     
    , Aug 7, 2010
    #2
    1. Advertising

  3. Shao Miller

    Eric Sosman Guest

    On 8/7/2010 7:57 AM, Shao Miller wrote:
    > 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.

    --
    Eric Sosman
    lid
     
    Eric Sosman, Aug 7, 2010
    #3
  4. Shao Miller

    Guest

    On Aug 7, 1:41 pm, wrote:
    > 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.)

    --
    Christopher Bazley
     
    , Aug 7, 2010
    #4
  5. Shao Miller

    Shao Miller Guest

    On Aug 7, 8:54 am, wrote:
    > On Aug 7, 1:41 pm, wrote:
    > > 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);

    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, Aug 7, 2010
    #5
  6. Shao Miller

    Shao Miller Guest

    On Aug 7, 8:53 am, Eric Sosman <> wrote:
    > On 8/7/2010 7:57 AM, Shao Miller wrote:
    >
    > > 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...
     
    Shao Miller, Aug 7, 2010
    #6
  7. Shao Miller wrote:
    > 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.
    --
    Marcin Grzegorczyk
     
    Marcin Grzegorczyk, Aug 8, 2010
    #7
  8. Shao Miller

    Shao Miller Guest

    Marcin Grzegorczyk wrote:
    > Shao Miller wrote:
    >> 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.
     
    Shao Miller, Aug 8, 2010
    #8
  9. Shao Miller

    Richard Bos Guest

    Shao Miller <> wrote:

    > 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
     
    Richard Bos, Aug 14, 2010
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Oodini
    Replies:
    1
    Views:
    1,779
    Keith Thompson
    Sep 27, 2005
  2. Replies:
    3
    Views:
    3,683
    Chris Torek
    Feb 20, 2006
  3. Replies:
    3
    Views:
    603
    Keith Thompson
    Mar 31, 2007
  4. xmllmx
    Replies:
    4
    Views:
    312
    Gordon Burditt
    Aug 28, 2007
  5. Shivanand Kadwadkar
    Replies:
    4
    Views:
    521
    J. J. Farrell
    Dec 28, 2010
Loading...

Share This Page