Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Alignment in C99 for Program-Defined Allocation

Reply
Thread Tools

Alignment in C99 for Program-Defined Allocation

 
 
Shao Miller
Guest
Posts: n/a
 
      08-07-2010
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?
 
Reply With Quote
 
 
 
 
chrisbazley@bigfoot.com
Guest
Posts: n/a
 
      08-07-2010
On Aug 7, 12:57*pm, Shao Miller <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      08-07-2010
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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid
 
Reply With Quote
 
chrisbazley@bigfoot.com
Guest
Posts: n/a
 
      08-07-2010
On Aug 7, 1:41*pm, (E-Mail Removed) 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
 
Reply With Quote
 
Shao Miller
Guest
Posts: n/a
 
      08-07-2010
On Aug 7, 8:54*am, (E-Mail Removed) wrote:
> On Aug 7, 1:41*pm, (E-Mail Removed) 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.
 
Reply With Quote
 
Shao Miller
Guest
Posts: n/a
 
      08-07-2010
On Aug 7, 8:53*am, Eric Sosman <(E-Mail Removed)> 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...
 
Reply With Quote
 
Marcin Grzegorczyk
Guest
Posts: n/a
 
      08-08-2010
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
 
Reply With Quote
 
Shao Miller
Guest
Posts: n/a
 
      08-08-2010
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.
 
Reply With Quote
 
Richard Bos
Guest
Posts: n/a
 
      08-14-2010
Shao Miller <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Dynamic memory allocation for array(ex: int a[size]) with C99 and older Shivanand Kadwadkar C Programming 4 12-28-2010 02:03 AM
How to find the alignment requirements of a give type in the C99 standard? xmllmx C Programming 4 08-28-2007 12:59 AM
Difference between "library parts" of C99 and "language parts" of C99 albert.neu@gmail.com C Programming 3 03-31-2007 08:14 PM
C99 struct initialization (C99/gcc) jilerner@yahoo.com C Programming 3 02-20-2006 04:41 AM
Allocation schema w.r.t. padding and alignment... SenderX C++ 2 05-13-2004 08:51 PM



Advertisments