safe "struct hack"?

[Jonathan Lee]

Hello all,
I've have a variation of the struct hack that I think is legal. Wondering if anyone could spot a reason why not. (By struct hack I mean putting a variable length array at the end of a struct, or a struct at the beginning of an array).

Suppose I want to add an int array to the end of

struct header
{
int a;
int b;
double c;
// int arr[]; // I think C99 would do this
}

Then I can make the union

union wrap
{
header hdr;
int arr[1];
}

And use calloc to get some memory

void* p = calloc(20, sizeof(wrap));

The following casts should be legal:
union* u = static_cast<union*>(p);
header* h = static_cast<header*>(u);
int* i = static_cast<int*>(u);

But, then, this should also be legal

int* j = static_cast<int*>(u + 1);

which is an aligned int pointer just past the header
struct. Seeing as how this came from calloc-d, "void"
memory, I think j + 0, j + 1, j + 2, ... are legal
int addresses.

After all, I can legally use

int* q = static_cast<int*>(p);

as an int array. I don't see why j would be any
different.

Can anyone see why this wouldn't be the case?

Thanks in advance,
--Jonathan

 

[Victor Bazarov]

I've have a variation of the struct hack that I think is legal. Wondering if anyone could spot a reason why not. (By struct hack I mean putting a variable length array at the end of a struct, or a struct at the beginning of an array).

Suppose I want to add an int array to the end of

struct header
{
int a;
int b;
double c;
// int arr[]; // I think C99 would do this
}

Then I can make the union

union wrap
{
header hdr;
int arr[1];
}

And use calloc to get some memory

void* p = calloc(20, sizeof(wrap));

The following casts should be legal:
union* u = static_cast<union*>(p);
header* h = static_cast<header*>(u);
int* i = static_cast<int*>(u);

But, then, this should also be legal

int* j = static_cast<int*>(u + 1);

which is an aligned int pointer just past the header
struct. Seeing as how this came from calloc-d, "void"
memory, I think j + 0, j + 1, j + 2, ... are legal
int addresses.

After all, I can legally use

int* q = static_cast<int*>(p);

as an int array. I don't see why j would be any
different.

Can anyone see why this wouldn't be the case?

If sizeof(int) is 5 and sizeof(double) is 8, you're in for a surprise.
I don't know of any architecture, currently in use, in which sizeof(int)
isn't a power of 2. The language makes no specific demand of it, however.

V

 

[Marcel Müller]

struct header
{
int a;
int b;
double c;
// int arr[]; // I think C99 would do this

Does this no longer work?
I could bet I have used this from time to time.

} ;
Then I can make the union

union wrap
{
header hdr;
int arr[1];
}

;

Do you really want to have a union here? I.e. you either have a header
/or/ one integer?

And use calloc to get some memory

void* p = calloc(20, sizeof(wrap));

You are allocating 20 headers here. There is no (portable) implication
on the number of additional integers. I would have expected something like
calloc(1, sizeof(wrap) + 20 * sizeof(int))

The following casts should be legal:
union* u = static_cast<union*>(p);

union is no type. You mean wrap.

header* h = static_cast<header*>(u);

Wrong. You cannot use static_cast for unrelated types.
Do you mean header* h = &u->hdr; ?

int* i = static_cast<int*>(u);

Also wrong for the same reason.

But, then, this should also be legal

int* j = static_cast<int*>(u + 1);

Same here. Here you need reinterpret_cast.

which is an aligned int pointer just past the header
struct. Seeing as how this came from calloc-d, "void"
memory, I think j + 0, j + 1, j + 2, ... are legal
int addresses.

You can't exactly know how many of them are legal. Se above.

After all, I can legally use

int* q = static_cast<int*>(p);

This works syntactically, as p is void*.

as an int array. I don't see why j would be any
different.

It is entirely different. p points to the start of your storage, while j
points after the (first) header.

Use
printf("p=%p\nu=%p\nh=%p\ni=%p\nj=%p\nq=%p\n", p,u,h,i,j,q);
to see what's going on.


Whatever you are going to do here seems not to hit the nail on the head.

If you want to have an header and a dynamically sized integer array in
one allocation then write a class with a custom new operator that takes
an additional argument for the size of the array and provide functions
for more or less safe access to the array. At least in debug builds I
would recommend boundary checks.


Marcel

 

[Jonathan Lee]

If sizeof(int) is 5 and sizeof(double) is 8, you're in for a surprise.

I don't see why -- the double is just for the sake of example. I'm not
expecting the double and int to coincide. The "header" struct could
contain anything. Sorry if that wasn't clear.

 

[James Kanze]

I've have a variation of the struct hack that I think is
legal. Wondering if anyone could spot a reason why not. (By
struct hack I mean putting a variable length array at the
end of a struct, or a struct at the beginning of an array).

There's no problem making it legal; I posted a method years ago,
and it is used in the g++ implementation of std::basic_string.

The problem you run into (both in my solution and yours) is
alignment. In g++, std::basic_string<double> will crash on some
32 bit machines (which require an alignment of 8 for double).
The problem is fixable, but not easily. (g++ just lives with
it. Not being able to use basic_string<double> doesn't seem to
bother many users.)

 

[Jonathan Lee]

struct header

int a;

int b;

double c;

// int arr[]; // I think C99 would do this

Does this no longer work?

I could bet I have used this from time to time.

I believe in C++ the usual trick is illegal because
you end up accessing past the end of the array. Though
it is widely supported.

Do you really want to have a union here? I.e. you either have a header

/or/ one integer?

yes. The union is for alignment requirements (see
below).

You are allocating 20 headers here. There is no (portable) implication

on the number of additional integers. I would have expected something like

calloc(1, sizeof(wrap) + 20 * sizeof(int))

That's not my understanding of calloc. What (I believe) I've
done is allocated enough space for 20 headers, with the
appropriate alignment. The number 20 is just for the sake
of example. The actual value would depend on how many ints
I want room for.

I've used calloc specifically here, because unlike new, I don't
think that the allocated space is "intended" for 20 headers.
Just that it is *suitable* for 20 headers.

union is no type. You mean wrap.
Typo.


Wrong. You cannot use static_cast for unrelated types.

Do you mean header* h = &u->hdr; ?

Yeah, sorry. Mostly meant that the union members are
aligned with the union, and the address of p, u, h
will all be the same.

You can't exactly know how many of them are legal. Se above.

I think I can. Basically I have 19 * sizeof(wrap) bytes with
the proper alignment for an int array. Therefore I should have

(19 * sizeof(wrap)) / sizeof(int)

elements. My claim is that this is no different than

int* t = (int*)calloc(19 * sizeof(wrap)/sizeof(int), sizeof(int))

This works syntactically, as p is void*.

Given the way calloc was called, it should be more than a
syntactic guarantee. I know this is C++, but if this didn't
work, you wouldn't be able to allocate arrays in C...

If you want to have an header and a dynamically sized integer array in
one allocation then write a class with a custom new operator that takes
an additional argument for the size of the array and provide functions
for more or less safe access to the array. At least in debug builds I
would recommend boundary checks.

That's precisely what I'm going to end up with. What I'm proposing is
a safe way of doing that underneath. I can't simply extend the memory
allocated by operator new, because I need the alignment guarantee.

 

[Jonathan Lee]

There's no problem making it legal; I posted a method years ago,

and it is used in the g++ implementation of std::basic_string.

I haven't seen a method that didn't "read past the end of an array".
If you've got a link to your method, I'd like to take a look.

The problem you run into (both in my solution and yours) is
alignment. In g++, std::basic_string<double> will crash on some
32 bit machines (which require an alignment of 8 for double).
The problem is fixable, but not easily. (g++ just lives with
it. Not being able to use basic_string<double> doesn't seem to
bother many users.)

I thought my solution got the alignment correct. If calloc puts
the unions contiguously (as it should)

wrap0 wrap1 wrap2 .. wrap19

Then the int array in wrap1 should have the correct alignment
(as far as the language is concerned).

I'm not sure if the problem you refer to is because of the
language, or a practical problem with the compiler (?)

 

[Marcel Müller]

That's not my understanding of calloc. What (I believe) I've
done is allocated enough space for 20 headers, with the
appropriate alignment. The number 20 is just for the sake
of example. The actual value would depend on how many ints
I want room for.

OK, seems that I did not catch what you are going to achieve at all.

If you are talking about alignment, AFAIK malloc/calloc/realloc always
returns storage that is suitable aligned for any native data type. OK,
it might no always be aligned for the fastest array access on a
particular platform (especially if you work with cache line
prefetching), but at least it would work.

I think I can. Basically I have 19 * sizeof(wrap) bytes with
the proper alignment for an int array. Therefore I should have

(19 * sizeof(wrap)) / sizeof(int)

elements. My claim is that this is no different than

int* t = (int*)calloc(19 * sizeof(wrap)/sizeof(int), sizeof(int))

Be careful. The division might cause truncations.

Given the way calloc was called, it should be more than a
syntactic guarantee. I know this is C++, but if this didn't
work, you wouldn't be able to allocate arrays in C...

It depends on what you expect about the resulting pointer.

That's precisely what I'm going to end up with. What I'm proposing is
a safe way of doing that underneath. I can't simply extend the memory
allocated by operator new, because I need the alignment guarantee.

You can have this easier.

size_t header_size = offsetof(wrap,arr);

This will include additional padding for the following arr.

wrap* w = malloc(header_size + n * sizeof(int);

This will be suitable aligned to handle an array of int after the
header, regardless of the headers content.

But you still could use a custom allocator. I have done this in a Java
like, immutable string implementation with strongly thread-safe
reference counting. The header (ref count and length) is followed by the
string content in one allocation. The custom allocator takes the array
size as additional parameter.
I further did the hack in the allocator that the pointers to these
instances point to the start of the array rather than the start of the
header. The header content is then located at this[-1]. This makes
references to string instances binary compatible to const char*, making
commonly used adapter functions so trivial, that no code is generated at
all. (Otherwise always NULL checks have to be done before the offset is
applied.)


Marcel

 

[James Kanze]

I haven't seen a method that didn't "read past the end of an array".
If you've got a link to your method, I'd like to take a look.

It's basically something like:

template <typename charT>
struct StringRep
{
size_t length;
size_t capacity;
int useCount;
void* operator new( size_t n, size_t additional )
{
return :perator new( n + additional * sizeof(StringRep) );
}
charT* data()
{
return reinterpret_cast<charT*>( this + 1 );
}
};

(There was more wrapper code, with the data members being
private, const and non-const versions of buffer, etc., but this
is enough to give the general idea.)

The basic idea is that there is never any declaration of the
array which makes up the data memory. And that a member
operator new forced you to use placement new to allocate the
additional space for the buffer.

The issue here is alignment; if sizeof(int) == 4, then
sizeof(StringRep) will probably be 12, and if instead of char,
the data type requires a stricter alignment than 4, you might
have problems. (g++ usess almost exactly this in its CoW
implementation of std::basic_string, and at least on some
machines, std::basic_string<double> will crash with an alignment
fault.) Of course, the alignment issue could be solved by
putting the buffer type in a union with some or all of the fixed
data members. (But in the case of std::basic_string, why
bother. In practice, at least in the enviroments which
libstdc++ supports, wchar_t will never be more than 32 bits, and
size_t will never be less, so you'll be OK for all real uses of
std::basic_string.)

I thought my solution got the alignment correct.

The union should do the trick.

If calloc puts
the unions contiguously (as it should)

wrap0 wrap1 wrap2 .. wrap19

Then the int array in wrap1 should have the correct alignment
(as far as the language is concerned).

But why calloc? The operator new function or malloc will be
just as good, called with sizeof(wrap) + n * sizeof(int). And
IMHO, it seems a lot cleaner to wrap it in the class itself.

 

[Jonathan Lee]

But you still could use a custom allocator. I have done this in a Java
like, immutable string implementation with strongly thread-safe
reference counting. The header (ref count and length) is followed by the
string content in one allocation. The custom allocator takes the array
size as additional parameter.

This is very similar to what I'm doing, actually. I'll implement
the custom allocator like you suggest. I was mostly concerned (for
the moment) about getting the memory correctly.

I further did the hack in the allocator that the pointers to these
instances point to the start of the array rather than the start of the
header. The header content is then located at this[-1]. This makes
references to string instances binary compatible to const char*, making
commonly used adapter functions so trivial, that no code is generated at
all. (Otherwise always NULL checks have to be done before the offset is
applied.)

An interesting thought. Thanks for the help.

 

[Jonathan Lee]

The union should do the trick.

I did consider something like what you posted, but was worried about
the alignment in general (I've ended up templating on the header
type and array type). I think I'll stick with the union to be safe.

But why calloc? The operator new function or malloc will be
just as good, called with sizeof(wrap) + n * sizeof(int). And
IMHO, it seems a lot cleaner to wrap it in the class itself.

I thought calloc had the *weakest* guarantee for alignment, while
still being correct. Like, calloc(5, 4) would only need to align
for a 4 byte structure, whereas malloc(20) would align for a 20
byte structure.

Maybe I'm wrong in that. But as you say, if it works for calloc
it'll work for malloc. So I'll use the better option, like you
suggest. And yeah, I'll work it into a proper interface.

Thanks for your help

--Jonathan

 

[James Kanze]

I did consider something like what you posted, but was worried about
the alignment in general (I've ended up templating on the header
type and array type). I think I'll stick with the union to be safe.

I thought calloc had the *weakest* guarantee for alignment, while
still being correct.

All of the C allocation functions have the same requirements:

The pointer returned if the allocation succeeds is suitably
aligned so that it may be assigned to a pointer to any type of
object with a fundamental alignment requirement and then used to
access such an object or an array of such objects in the space
allocated (until the space is explicitly deallocated).

The same holds for ":perator new()", and even "new char[]".
(Which means that "new int[]" may be less aligned than "new
char[]".)