"free space" with declared type

[Mark Piffer]

On 20 Dec 2004 09:33:11 -0800, Mark Piffer

Google has problems, period!

Very annoying, indeed! The following is hand-quoted so please excuse
any errors.

You've missed one word and one phrase -- 'portably' and "general
purpose".

Well, by posting this to c.l.c I subject my questions automatically to
those terms (you think I don't remember those poor OT-poster skeletons
rotting in their cages alongside the entrance to c.l.c? )

Similarly, you can write an allocator which is fully portable for a
specific type or set of types. Trivially, you can make one which is
portable for char, by using a union you can make one which is portable
for all integral types, etc., but you can't make one which gives
alignment suitable for any purpose without knowing machine details.

How would a set of types be implemented? I can think of a union
containing this set, but an allocator for it would be next to useless,
because you are forced to always use up storage for the largest
member. The alignment issues are clear to me and I don't mind them, if
I want general purpose alignment, it's up to the implementation, ok.

Embedded programs are not portable in the same way,
they are implicitly (and sometimes explicitly) tied to a specific
architecture or set of architectures and hardware, so it is no problem
to have a specific allocator, preferably grouped in a library with other
machine specific functionality. All you then need to do, if the rest of
your program has been implemented portably, is to change the specific
parts which depend on the architecture (keeping the interface the

same).
Please do not underestimate or deny the striving for portability in
embedded software. Most parts of the embedded software I have seen and
written do (or would) benefit substantially by being made conformant.
The ability to run code cross-platform is a tremendous help in
implementing embedded software and in simulating the application in a
much friendlier environment.

The point is that if you (or whoever is implementing the allocator)
knows what they are doing there is no problem. For instance, if you
know that the worst case alignment your program needs is a long then you
can do your own alignment to sizeof(long). If you know that your
machine has linear addresses which correspond to values in an unsigned
long then you can do appropriate arithmetic on them. It just isn't
portable to any architecture you might ever find -- but it may well work
for all machines you will ever find in practice which want to use your

Chris C

I am currently implementing a file-system-like part for an embedded
software. The only thing that is architecture dependent is the
low-level access to memory, 5 out of ca. 3000 lines of C. Right now I
have a setup that allows me, without touching the module itself,
compile and run it on an 16-bit big endian embedded as well as on my
32-bit little endian desktop machine. Now I have come to the point
that I want (for the sake of extendibility) rewrite the statemachines
which drive the high level operations on the memory. The statemachines
are hierarchical and could be beautifully controlled with a
polymorphic stack which holds the locals for each statemachine. As one
can't foresee the order in which the statemachines are called and
because storage on the embedded platform isn't large, an array of
unions is not feasible (oh well, maybe with a complete permutation of
all locals in all call orders, but then I'll bust implementation
limits). I can hide this, as you propose, behind some allocator magic,
but then the language has imposed on me an additional problem that I
didn't have before and worse, I lose another part of the ability to
simulate a 1:1 image of my code on the desktop. Maybe I'm suffering
from a narrowed mental horizon but IMHO the standardized UB was a bad
bargain for losing the "storage is storage is storage" property.

Mark

 

[Chris Croughton]

Well, by posting this to c.l.c I subject my questions automatically to
those terms (you think I don't remember those poor OT-poster skeletons
rotting in their cages alongside the entrance to c.l.c? )

Indeed, but in practice most real-world programs don't need that extreme
level of conformance (anything using network or other libraries, for a
start).

How would a set of types be implemented? I can think of a union
containing this set, but an allocator for it would be next to useless,
because you are forced to always use up storage for the largest
member.

Yes, that's what malloc does (in fact it often wastes more than that
because it might have to align for a type you don't need).

The alignment issues are clear to me and I don't mind them, if
I want general purpose alignment, it's up to the implementation, ok.

Well, you could have a separate allocator for each type. But in
practice if you align to the largest type (not allocate in units of that
type, just align to it) that must work. So you can have:

union BiggestType
{
short s;
int i;
long l;
};

then align the start of the allocated area to sizeof(union BiggestType).

Please do not underestimate or deny the striving for portability in
embedded software. Most parts of the embedded software I have seen and
written do (or would) benefit substantially by being made conformant.
The ability to run code cross-platform is a tremendous help in
implementing embedded software and in simulating the application in a
much friendlier environment.

Yes, but some parts will have to change. If the program is accessing
hardware, those parts will need to be changed or emulated -- but /only/
those parts if it is written correctly. Similarly with memory
allocation, inter-process (thread) communication, etc. There are other
standards which deal with some of them.

I am currently implementing a file-system-like part for an embedded
software. The only thing that is architecture dependent is the
low-level access to memory, 5 out of ca. 3000 lines of C. Right now I
have a setup that allows me, without touching the module itself,
compile and run it on an 16-bit big endian embedded as well as on my
32-bit little endian desktop machine.

I work on mobile phone software, we do the same (except that reading and
writing flash ROM and other hardware access also has to be ported, and
running on several OSs with different task models means that those
interfaces need a common layer as well).

Now I have come to the point
that I want (for the sake of extendibility) rewrite the statemachines
which drive the high level operations on the memory. The statemachines
are hierarchical and could be beautifully controlled with a
polymorphic stack which holds the locals for each statemachine. As one
can't foresee the order in which the statemachines are called and
because storage on the embedded platform isn't large, an array of
unions is not feasible (oh well, maybe with a complete permutation of
all locals in all call orders, but then I'll bust implementation
limits). I can hide this, as you propose, behind some allocator magic,
but then the language has imposed on me an additional problem that I
didn't have before and worse, I lose another part of the ability to
simulate a 1:1 image of my code on the desktop.

How about endian and alignment issues in your structures? It is not
possible to ever run things totally 1:1 in different environments, and
that's nothing to do with the language used it's because the environment
is part of the problem.

Maybe I'm suffering
from a narrowed mental horizon but IMHO the standardized UB was a bad
bargain for losing the "storage is storage is storage" property.

If you want Java you know where it is. And it's slow and unwieldy
because it hides all of those 'messy' things and pretends to be running
on the same machine everywhere (except that it fails at that as well!).
There is no such thing as a totally portable embedded program, because
by its nature it deals with things outside the C standard. You can
however come arbitrarily close to it for the majority of the program,
leaving the messy bits to port.

Chris C

 

[Keith Thompson]

Well, you could have a separate allocator for each type. But in
practice if you align to the largest type (not allocate in units of that
type, just align to it) that must work. So you can have:

union BiggestType
{
short s;
int i;
long l;
};

then align the start of the allocated area to sizeof(union BiggestType).

Right, but that's not a portable definition of union BiggestType. You
need a long long member for C99 (or for C90 implementations that
support it as an extension). You should also have at least a long
double member, a long double complex member (for C99), a void* member,
a function pointer member, a struct pointer member, and maybe a few
other pointer types as well.

 

[Charlie Gordon]

Right, but that's not a portable definition of union BiggestType. You
need a long long member for C99 (or for C90 implementations that
support it as an extension). You should also have at least a long
double member, a long double complex member (for C99), a void* member,
a function pointer member, a struct pointer member, and maybe a few
other pointer types as well.

How relevant is this to alignment constraints in general ?
Let me quote C99 7.20.3 verse 1 :

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

It doesn't put any extra constraint on alignment beyond this. Whether a pointer
can be dereferenced to access a particular object type for a given alignment
value is hardware dependent and possibly software selectable. Efficiency is
also a concern, and library designers may make decisions to improve cache
effectiveness by aligning malloc'ed blocks on certain boundaries not
specifically required for just dereferencing constraints.

Requiring excessive alignment such as multiples of sizeof(long double complex)
may be correct but is not necessary.

To assess actual alignment constraints, a structure might be used to figure how
much padding the compiler inserted between various types :

struct {
char a;
short x;
} s_short;
struct {
char a;
long double complex x;
} s_long_double_complex;

// probably the same as sizeof(short)
int align_short = (char*)&s_short.x - (char*)&s_short;
// probably different from sizeof(long double complex)
int align_long_double_complex = (char*)&s_long_double_complex.x -
(char*)s_long_double_complex;
....

But there is no guarantee that structure fields are layed out in the order of
definition.
Maybe this would fix it:
int align_long_double_complex = sizeof(s_long_double_complex) - sizeof(long
double complex);

As a matter of fact, malloc() alignment constraints can be different for
different allocation sizes : why should malloc(1) be aligned on anything but a
byte boundary ?

Some bold programmers like to store tag bits in the low order bits of malloced()
pointers, and then mask those off upon dereferencing the actual object. This is
non portable of course, and relies on false assumptions even for known
architectures: hand crafted allocation routines are needed to enforce this ugly
stuff.

 

[Chris Croughton]

Right, but that's not a portable definition of union BiggestType. You
need a long long member for C99 (or for C90 implementations that
support it as an extension). You should also have at least a long
double member, a long double complex member (for C99), a void* member,
a function pointer member, a struct pointer member, and maybe a few
other pointer types as well.

No, that's my point, you /don't/ need one of everything if you know that
your program won't be using it. As far as I can remember I have never
allocated anything in C with a pointer to function member (pointer to
data, yes), and I won't be using any sort of complex number until C99
becomes universal (at the moment, as mentioned recently, there is no
completely conforming C99 implementation and the nearest one costs $$$,
I write for portability so that the code can be used on existing
compilers).

My union is portable, it isn't totally general. A totally general union
wouldn't be portable (since features like long long may be present but
their presence may not be detectable) and may not even be possible since
some types provided by the implementation may be known only to the
implementors (they may provide a _uint128 which is used by the file
functions, for instance, their malloc() would know about it but your
allocator wouldn't).

Chris C

 

[Michael Mair]

How relevant is this to alignment constraints in general ?
Let me quote C99 7.20.3 verse 1 :

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

It doesn't put any extra constraint on alignment beyond this. Whether a pointer
can be dereferenced to access a particular object type for a given alignment
value is hardware dependent and possibly software selectable. Efficiency is
also a concern, and library designers may make decisions to improve cache
effectiveness by aligning malloc'ed blocks on certain boundaries not
specifically required for just dereferencing constraints.

Requiring excessive alignment such as multiples of sizeof(long double complex)
may be correct but is not necessary.

To assess actual alignment constraints, a structure might be used to figure how
much padding the compiler inserted between various types :

struct {
char a;
short x;
} s_short;
struct {
char a;
long double complex x;
} s_long_double_complex;

// probably the same as sizeof(short)
int align_short = (char*)&s_short.x - (char*)&s_short;
// probably different from sizeof(long double complex)
int align_long_double_complex = (char*)&s_long_double_complex.x -
(char*)s_long_double_complex;
...

You are looking for the offsetof macro:
struct get_align_ldc {
char a;
long double complex x;
};

align_long_double_complex = offsetof(struct get_align_ldc, x);

But there is no guarantee that structure fields are layed out in the order of
definition.

Huh? Where does this come from?
How could we make use of the same initial sequence when using unions if
structure members were laid out arbitrarily/differently?
I am too lazy to look it up now, but I think _you_ should support this
claim by using either standard or the respective last public draft.

Maybe this would fix it:
int align_long_double_complex = sizeof(s_long_double_complex) - sizeof(long
double complex);

How so?
If, for example, we consider long doubles with, say, 80 bits but
64 bit alignment (nothing in the standard prohibits that) then
we would effectively need 3*64 bits for a corresponding
struct get_align_ld... which gives us 128 bits instead of 64.

As a matter of fact, malloc() alignment constraints can be different for
different allocation sizes : why should malloc(1) be aligned on anything but a
byte boundary ?

Good point.

Some bold programmers like to store tag bits in the low order bits of malloced()
pointers, and then mask those off upon dereferencing the actual object. This is
non portable of course, and relies on false assumptions even for known
architectures: hand crafted allocation routines are needed to enforce this ugly
stuff.

Sounds quite like unnecessary "optimisation". Where would one
need something like that?


Cheers
Michael

 

[Keith Thompson]

How relevant is this to alignment constraints in general ?
Let me quote C99 7.20.3 verse 1 :

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

It doesn't put any extra constraint on alignment beyond this.
Whether a pointer can be dereferenced to access a particular object
type for a given alignment value is hardware dependent and possibly
software selectable. Efficiency is also a concern, and library
designers may make decisions to improve cache effectiveness by
aligning malloc'ed blocks on certain boundaries not specifically
required for just dereferencing constraints.

Requiring excessive alignment such as multiples of sizeof(long
double complex) may be correct but is not necessary.

The intent is to support alignment at least as strict as that of
long double complex, not multiples of its size.

[...]

But there is no guarantee that structure fields are layed out in the
order of definition.

Yes, there is. C99 6.7.2.1p5 says:

... a structure is a type consisting of a sequence of members,
whose storage is allocated in an ordered sequence ...

 

[CBFalconer]

.... snip ...

No, that's my point, you /don't/ need one of everything if you
know that your program won't be using it. As far as I can
remember I have never allocated anything in C with a pointer to
function member (pointer to data, yes), and I won't be using any

.... snip ...

How do you know that? For example, I replaced the malloc system I
use here. I found it was called during program initialization for
such things as creating file blocks for stdin etc. Some items were
even freed. At any rate, it made using such things as printf for
debugging purposes impossible.

 

[Charlie Gordon]

Charlie Gordon wrote:

I meant aligning on multiples of sizeof(long double complex), which incidentally
is not what the union achieves, as its size may be even larger than that
(smallest common multiple of alignment constraints of all members).

You are looking for the offsetof macro:
struct get_align_ldc {
char a;
long double complex x;
};

align_long_double_complex = offsetof(struct get_align_ldc, x);

Yes, I wasn't sure if offsetof() was part of C99. Note that it may not be
available on pre-C99 platforms, and these are quite numerous ;-)

Huh? Where does this come from?
How could we make use of the same initial sequence when using unions if
structure members were laid out arbitrarily/differently?
I am too lazy to look it up now, but I think _you_ should support this
claim by using either standard or the respective last public draft.

Well you are right, I hadn't checked either, and this baseless claim may be more
appropriate for C++ structs.
I quote C99 6.7.2.1 verse 13:

"
Within a structure object, the non-bit-field members and the units in which
bit-fields
reside have addresses that increase in the order in which they are declared. A
pointer to a
structure object, suitably converted, points to its initial member (or if that
member is a
bit-field, then to the unit in which it resides), and vice versa. There may be
unnamed
padding within a structure object, but not at its beginning.
"

Note however that the order of allocation of bitfields in storage units is
implementation defined, the storage unit size and alignment as well, very little
control is at the hands of the programmer in this regard (6.7.2.1 verses 10 and
11):

"
10 An implementation may allocate any addressable storage unit large enough to
hold a bit-
field. If enough space remains, a bit-field that immediately follows another
bit-field in a
structure shall be packed into adjacent bits of the same unit. If insufficient
space remains,
whether a bit-field that does not fit is put into the next unit or overlaps
adjacent units is
implementation-defined. The order of allocation of bit-fields within a unit
(high-order to
low-order or low-order to high-order) is implementation-defined. The alignment
of the
addressable storage unit is unspecified.
11 A bit-field declaration with no declarator, but only a colon and a width,
indicates an
unnamed bit-field.105) As a special case, a bit-field structure member with a
width of 0
indicates that no further bit-field is to be packed into the unit in which the
previous bit-
field, if any, was placed.
"

How so?
If, for example, we consider long doubles with, say, 80 bits but
64 bit alignment (nothing in the standard prohibits that) then
we would effectively need 3*64 bits for a corresponding
struct get_align_ld... which gives us 128 bits instead of 64.

jinx! you are right!

Good point.

I would like more comments from the C99 guys on this point.

Sounds quite like unnecessary "optimisation". Where would one
need something like that?

I have seen that kind of bit twiddling used in toy and real-life Lisp
interpreters implemented in C.

 

[Keith Thompson]

No, that's my point, you /don't/ need one of everything if you know that
your program won't be using it.

[...]

Good point. (There's some risk of breaking things if you eventually
try to allocate something bizarre, but software maintenance in general
is risky.)

 

[Michael Mair]

I meant aligning on multiples of sizeof(long double complex), which incidentally
is not what the union achieves, as its size may be even larger than that
(smallest common multiple of alignment constraints of all members).


Yes, I wasn't sure if offsetof() was part of C99. Note that it may not be
available on pre-C99 platforms, and these are quite numerous ;-)

From the ansi.c (C89) file of Dan Pop:

"
4.1.5 Common definitions <stddef.h>

The following types and macros are defined in the standard header
<stddef.h> . Some are also defined in other headers, as noted in
their respective sections.
"
[...]
"
The macros are

NULL

which expands to an implementation-defined null pointer constant; and

offsetof( type, member-designator)

which expands to an integral constant expression that has type size_t,
the value of which is the offset in bytes, to the structure member
(designated by member-designator ), from the beginning of its
structure (designated by type ). The member-designator shall be such
that given

static type t;

then the expression &(t. member-designator ) evaluates to an address
constant. (If the specified member is a bit-field, the behavior is
undefined.)
"

Maybe someone else knows better when offsetof made it into
the library headers.

Well you are right, I hadn't checked either, and this baseless claim may be more
appropriate for C++ structs.
I quote C99 6.7.2.1 verse 13:

"
Within a structure object, the non-bit-field members and the units in which
bit-fields
reside have addresses that increase in the order in which they are declared. A
pointer to a
structure object, suitably converted, points to its initial member (or if that
member is a
bit-field, then to the unit in which it resides), and vice versa. There may be
unnamed
padding within a structure object, but not at its beginning.
"

Note however that the order of allocation of bitfields in storage units is
implementation defined, the storage unit size and alignment as well, very little
control is at the hands of the programmer in this regard (6.7.2.1 verses 10 and
11):

"
10 An implementation may allocate any addressable storage unit large enough to
hold a bit-
field. If enough space remains, a bit-field that immediately follows another
bit-field in a
structure shall be packed into adjacent bits of the same unit. If insufficient
space remains,
whether a bit-field that does not fit is put into the next unit or overlaps
adjacent units is
implementation-defined. The order of allocation of bit-fields within a unit
(high-order to
low-order or low-order to high-order) is implementation-defined. The alignment
of the
addressable storage unit is unspecified.
11 A bit-field declaration with no declarator, but only a colon and a width,
indicates an
unnamed bit-field.105) As a special case, a bit-field structure member with a
width of 0
indicates that no further bit-field is to be packed into the unit in which the
previous bit-
field, if any, was placed.
"

Yep, but bit-fields are not really important for alignment issues as
they are declared to be of integer type.


[snip]

I would like more comments from the C99 guys on this point.

AFAIK, nothing speaks against that but I am not reading in csc
where there may be arguments against this.


Cheers
Michael

 

[Chris Croughton]

... snip ...

How do you know that?

Because I call it when I want to use it, it isn't called by anything I
haven't written. Obviously, it isn't called malloc (which would make
the program non-conformant anyway), it's called something like memAlloc.
In some of its incarnations it uses a static array, in some it uses a
known address in memory, in some it gets memory with malloc and manages
it itself (doing garbage collection, for instance).

For example, I replaced the malloc system I
use here. I found it was called during program initialization for
such things as creating file blocks for stdin etc. Some items were
even freed. At any rate, it made using such things as printf for
debugging purposes impossible.

You were trying to replace a system function with something of your own,
obviously without knowledge of how it was used in your system.

See what I wrote. You can write an allocator which is portable but not
general, or one which is general but not portable, but not one which is
both general and portable since the system constraints are outside the
C standard. One of those constraints, into which you evidently fell,
can be that the system and implementation libraries may call the
standard named functions outside your code and expect them to behave in
ways and at times you don't expect.

Chris C

 

[CBFalconer]

.... snip ...


You were trying to replace a system function with something of your
own, obviously without knowledge of how it was used in your system.

No, I was deliberately replacing a system component, with knowledge
of its usage. The point is that the investigation goes beyond the
immediate application.

You can see the end result on my pages as nmalloc.zip

 

[Chris Croughton]

No, that's my point, you /don't/ need one of everything if you know that
your program won't be using it.

[...]

Good point. (There's some risk of breaking things if you eventually
try to allocate something bizarre, but software maintenance in general
is risky.)

Indeed. In my case I know that certain programs I write will never need
to use floating point at all, and that at least for the forseeable
future I won't be using the complex types (since there are far too many
compilers and libraries which don't support them as per the standard and
the point of code being portable is that anything should be able to
compile it, not just one proprietary compiler). For the vast majority
of programs I write (and all of the ones I've written in the last couple
of decades which need special memory allocators) I only need to bother
about integer types (up to long long) and pointer to data.

Chris C

 

[Chris Croughton]

No, I was deliberately replacing a system component, with knowledge
of its usage.

Evidently with insufficient knowledge of its use, since it failed.

I suspect that it would do worse on some systems, because some of the
libraries will be using your code and others using the 'malloc' in the
OS...

The point is that the investigation goes beyond the
immediate application.

And the code becomes non-portable.

You can see the end result on my pages as nmalloc.zip

Hmm, it seems to be doing non-portable things like casting a pointer to
an integer type ('ulong', which is in fact an unsigned int) and masking
off bits for alignment. Yes, this works on the ix86 processors and on
many others, but it isn't standard C.

Chris C