Re: [boost] low-level sub-allocation/alignment challenge

From: Valentin Bonnard (Bonnard.V_at_[hidden])
Date: 2000-08-24 21:39:53

On Thu, Aug 24, 2000 at 12:09:30AM -0400, David Abrahams wrote:

> The goal is to portably sub-allocate a POD struct from larger blocks
> obtained from malloc() without wasting space or invoking undefined behavior.

IMO alignement is very badly described in the standard, and no 
supported at all (there are no standard tools to determine the 
alignement of a type, round up a pointer to align it with some 
value, or stack-allocate aligned char arrays), so no, I don't 
think there are strictly standard solutions.

> The POD struct ends with a variable-length array. Here is an example of what
> the struct looks like:
> 
> struct Rule
> {
>     unsigned long cost;
>     const void* action;
>     const char* symbols[1]; // actually a variable-length array
> };

symbols has 1 element, so when you write symbols[1] 
you get undefined behaviour. That's why C99 introduced 
arrays of undefined size: otherwise you have to way 
to _name_ a variable lenth array at the end of a structure, 
because either you under-estimate the size, and then you 
cannot access members of the array, either you over-estimate 
the size, and you cannot access the struct at all (because 
the size of the struct is greater than the size you allocate). 

> I think I know how to calculate the amount of room needed to accomodate any
> number of symbols in a Rule:
>    offsetof(Rule, symbols) + n * sizeof(const char*)
> ought to do the trick. The greater challenge is to figure out how many bytes
> of padding (if any) are needed between the first Rule allocated and the next
> one. The problem is that the byte following the last symbol in one Rule may
> not be aligned properly for the next Rule. I realize that on most machines,
> sizeof(unsigned long) == sizeof(void*) == sizeof(char*), so there will be no
> problem, but remember I want a *portable* solution.

There is a class in the vault to find out the alignement of 
a given type (I think).

> If you can solve that problem, it would be great to know (for curiosity's
> sake, mostly) how to perfom the same trick when Rule is not strictly a
> POD...

Are the any real cases where offsetof doesn't work on non PODs (except 
with virtual bases of course) ?

-- 
Valentin Bonnard