Why runtime alignment could be useful

[Clint Olsen]

I did a Google about this, and I've seen this covered quite a few times -
some leading to useful tricks with offsetof() to discern alignment and
others using a big-union of intrinsic types to discern what the compiler
would do with this kind of data and act accordingly. Others claimed it
couldn't be done or it wasn't worth it.

Rather than dive into the how, I wanted to discuss more of the _why_ since
that was asked a few times and nobody replied to that question.

The best examples I can give are keeping related data together and avoiding
fragmentation by multiple (perhaps unecessary) malloc calls. When writing
ADT libraries, it would be nice to keep node/link info together with the
associated data. The alternative is to force the user to include a
node/link struct in their data structure and force the library writer to
expose his API unecessarily. Another situation is to be able to write a
debugging memory allocator where you have extra space at the beginning of
the allocation section to store information such as file/line info of where
it occurred. Richard's MemTrack library had an example of this in 'C
Unleashed'. Then the info is just a known offset away from the user
pointer. Otherwise you would need a rather complex translation scheme to
tie the addresses to the alloc info since pointer values themselves cannot
be portably used.

I'm just curious as to what others think of this technique and if it's
really worth the effort.

-Clint

[Richard Heathfield]

Clint Olsen wrote:

<snip>

Another situation is to be able to write a
debugging memory allocator where you have extra space at the beginning of
the allocation section to store information such as file/line info of
where
it occurred. Richard's MemTrack library had an example of this in 'C
Unleashed'. Then the info is just a known offset away from the user
pointer. Otherwise you would need a rather complex translation scheme to
tie the addresses to the alloc info since pointer values themselves cannot
be portably used.

In fact, the known-offset technique has its own portability problems.
Because of this, I have used a very different technique in the "CLINT"
(cough!) library, where I simply dump the memory info to a log file, where
a separate utility can read it and analyse it after the run is completed.
This turns out to be an amply flexible way to detect and fix leaks and
"kaels", as well as leaving the application code /and/ library code
unsullied by portability concerns.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Eric Sosman]

Clint Olsen wrote:

I did a Google about this, and I've seen this covered quite a few times -
some leading to useful tricks with offsetof() to discern alignment and
others using a big-union of intrinsic types to discern what the compiler
would do with this kind of data and act accordingly. Others claimed it
couldn't be done or it wasn't worth it.

Rather than dive into the how, I wanted to discuss more of the _why_ since
that was asked a few times and nobody replied to that question.

The best examples I can give are keeping related data together and avoiding
fragmentation by multiple (perhaps unecessary) malloc calls. When writing
ADT libraries, it would be nice to keep node/link info together with the
associated data. The alternative is to force the user to include a
node/link struct in their data structure and force the library writer to
expose his API unecessarily. Another situation is to be able to write a
debugging memory allocator where you have extra space at the beginning of
the allocation section to store information such as file/line info of where
it occurred. Richard's MemTrack library had an example of this in 'C
Unleashed'. Then the info is just a known offset away from the user
pointer. Otherwise you would need a rather complex translation scheme to
tie the addresses to the alloc info since pointer values themselves cannot
be portably used.

I'm just curious as to what others think of this technique and if it's
really worth the effort.

You don't say so explicitly, but I guess you're looking
for a portable way to answer the question "What is the most
restrictive alignment required by this implementation, for
any data type whatsoever?" (The techniques you mention are
already capable of answering the question for any particular
type T, but they're no good for the more general question
because the set of types is extensible.)

IMHO, the question is not all that interesting except to
the implementors of the compiler and library. They obviously
need the answer, but since they need not obtain it portably
they are free to resort to other means -- foreknowledge is
perhaps the most typical. For the other two uses you mention:

- For ADTs you'd like (I guess) to start each node with
your own header of structural data, and then make a copy
of the "payload" data just after it. To ensure proper
alignment of the payload you want to pad your header to
a multiple of the maximal alignment.

That's one approach, but it's certainly not the only
way. If the payload is of fixed length you can easily
plant your structural data *after* the payload data.
Or you could go for greater flexibility and avoid
copying the data altogether: segregate the structural
data from the payload entirely, and use a `void*' to
point to the payload. This latter approach has the
advantage that a single payload can exist simultaneously
in a three hash tables, two skip lists, and a partridge
in a B-tree.

In short, I don't see a compelling reason for ADT APIs
to require the alignment information. Convenient for
some kinds of implementation, perhaps, but not vital.

- For a debugging memory manager, my advice is *not* to
keep your structural information close to the payload.
Of all memory locations, those adjacent to the allocated
areas are surely the most vulnerable to being trashed
by fencepost errors, runaway strcpy(), and the like.

In my own debugging malloc() -- I guess pretty much
everybody eventually gets around to writing one -- I
keep the structural data separate from the allocated
areas as much as possible. I don't do arithmetic on
the argument to free() to discover the size of the
block; instead, I look up the address in a skip list.
A lookup failure means a bad argument value -- double-
freeing, or freeing a garbage pointer -- and I can
detect this without running off the rails.

On the other hand, there *is* one place where it would
help if I could determine the maximal alignment: I plant
pre-initialized "guard zones" before and after each
allocated area, and check their content at free() (and
at some other times) to determine whether the program has
stomped outside its supposed allocation. The sizes of
the guard zones must, obviously, depend on the alignment
required for the payload; I've just hard-wired this with
a #define, but it would be nicer if there were a clean
way to get the result.

Summary: The answer to the alignment question would be useful
in some specialized circumstances, but might not be useful enough
to justify all the work a Standards committee might have to expend
on it. Note in particular that making use of the answer involves
doing arithmetic on integer representations of pointer values,
which means the committee would have to come up with definitions
for how to convert back and forth; the current definitions are
not strong enough to support the uses we're considering.

--
Er*********@sun.com

[Clint Olsen]

On 2004-02-05, Eric Sosman <Er*********@sun.com> wrote:

You don't say so explicitly, but I guess you're looking for a portable
way to answer the question "What is the most restrictive alignment
required by this implementation, for any data type whatsoever?" (The
techniques you mention are already capable of answering the question for
any particular type T, but they're no good for the more general question
because the set of types is extensible.)
Yes, the set of types is extensible, but eventually a struct has to boil
down to an intrinsic type in C. Have you ever seen or heard of a case
where the alignment of an aggregate was greater than the alignment of it's
members? I know that there's nothing stopping an implementation from doing
this, however.
That's one approach, but it's certainly not the only
way. If the payload is of fixed length you can easily
plant your structural data *after* the payload data.
Or you could go for greater flexibility and avoid
copying the data altogether: segregate the structural
data from the payload entirely, and use a `void*' to
point to the payload. This latter approach has the
advantage that a single payload can exist simultaneously
in a three hash tables, two skip lists, and a partridge
in a B-tree.
Yes, I can see the benefit of using void pointers to share data between
structures, but my way doesn't preclude that from happening. If you want
to store pointers, by all means do. I just remove the 'fixed' constraint
from the equation. However, doing so means that a separate alocation would
be required since there's no way to copy the variable length data and
guarantee it's suitably aligned.
In my own debugging malloc() -- I guess pretty much
everybody eventually gets around to writing one -- I
keep the structural data separate from the allocated
areas as much as possible. I don't do arithmetic on
the argument to free() to discover the size of the
block; instead, I look up the address in a skip list.
A lookup failure means a bad argument value -- double-
freeing, or freeing a garbage pointer -- and I can
detect this without running off the rails.
How do you look up the address in a skip list when the address (the pointer
value) is not portable?
On the other hand, there *is* one place where it would
help if I could determine the maximal alignment: I plant
pre-initialized "guard zones" before and after each
allocated area, and check their content at free() (and
at some other times) to determine whether the program has
stomped outside its supposed allocation. The sizes of
the guard zones must, obviously, depend on the alignment
required for the payload; I've just hard-wired this with
a #define, but it would be nicer if there were a clean
way to get the result.

Yes, I agree that this would be very cool.

Thanks for your detailed response.

-Clint

[Gordon Burditt]

>Yes, the set of types is extensible, but eventually a struct has to boil

down to an intrinsic type in C. Have you ever seen or heard of a case
where the alignment of an aggregate was greater than the alignment of it's
members? I know that there's nothing stopping an implementation from doing
this, however.

Yes. Some compilers align a struct or union to the strictest
alignment of all the members it *MIGHT* have. This means that for
a struct consisting entirely of chars and char arrays, on a machine
with some alignment restrictions for types other than char, the
alignment is stricter than that for its members. It also means the
compiler doesn't have to bother with checking what's in the struct
to figure out it's alignment. It's a struct, therefore the alignment
is known.
Gordon L. Burditt

[Eric Sosman]

Clint Olsen wrote:

On 2004-02-05, Eric Sosman <Er*********@sun.com> wrote:

You don't say so explicitly, but I guess you're looking for a portable
way to answer the question "What is the most restrictive alignment
required by this implementation, for any data type whatsoever?" (The
techniques you mention are already capable of answering the question for
any particular type T, but they're no good for the more general question
because the set of types is extensible.)

Yes, the set of types is extensible, but eventually a struct has to boil
down to an intrinsic type in C. Have you ever seen or heard of a case
where the alignment of an aggregate was greater than the alignment of it's
members? I know that there's nothing stopping an implementation from doing
this, however.

I seem to recall a compiler that aligned all struct types
rather strictly, even if the individual elements' alignment
requirements were more lenient. Alas, my own memory's gathering
bit-rot seems to have obscured the details, but the upshot was
that `struct {char a;}' would always be padded to something like
four or eight bytes.

In my own debugging malloc() -- I guess pretty much
everybody eventually gets around to writing one -- I
keep the structural data separate from the allocated
areas as much as possible. I don't do arithmetic on
the argument to free() to discover the size of the
block; instead, I look up the address in a skip list.
A lookup failure means a bad argument value -- double-
freeing, or freeing a garbage pointer -- and I can
detect this without running off the rails.

How do you look up the address in a skip list when the address (the pointer
value) is not portable?

The skip list's nodes use the address as the key, just as
they might use a telephone number or keyword string or whatever.
True, the lookup itself relies on two non-portable assumptions:

- The `<' and `>' relations do something sensible when given
pointers not based on the same array. That is, I can drive
the search with an ordering relation not guaranteed by the
Standard.

- If someone hands a garbage pointer to free() or realloc(),
it's safe to compare that garbage pointer to valid pointers
*and* the garbage will never compare equal to anything
valid. That's what lets me detect bad arguments.

As I mentioned earlier, I also hard-wire an assumption about the
maximal alignment and do some bit-fiddling on pointers-as-integers --
so there are at least four non-portable things going on in the package,
and a clean way to discover the maximal alignment would only fix one
of them. Not a huge benefit, methinks.

--
Er*********@sun.com