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

From: Branko Èibej (branko.cibej_at_[hidden])
Date: 2000-08-24 00:54:45

David Abrahams wrote:
> 
> Hi,
> 
> I'm trying to solve a seemingly simple problem that's turning out to be
> harder than it looks. I'm hoping someone out there has the expertise to
> help.
> 
> The goal is to portably sub-allocate a POD struct from larger blocks
> obtained from malloc() without wasting space or invoking undefined behavior.
> 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
> };
> 
> 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*)

The space is usually calculated like this:

    sizeof(Rule) + (n - 1) * sizeof(const char*)

Although the size you get might be a bit larger than with your
expression (due to possible padding at the end of Rule), that
should rarely happen in practice.

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

The only portable solution I know of is to align to sizeof(Rule), as if you
had an array of Rules.

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

Yikes. If it isn't a POD, AFAIK the compiler can lay out the class
members any way it likes; e.g., it can put "symbols" at the beginning
of the memory layout, or put a vtable pointer after "symbols" ...

However, assuming that the layout is reasonably sane (data members in
the order of declaration and nothing but padding after the last data
member), the method outlined above should work.

    Brane

-- 
Branko Èibej                 <branko.cibej_at_[hidden]>
HERMES SoftLab, Litijska 51, 1000 Ljubljana, Slovenia
voice: ([phone]     fax: [phone]