justification check

[Victor Nazarov]

Consider I want to write my own version of standard malloc, calloc,
realloc, free. How can I portably check if they work correctly? The most
remarkable will be the test for right justification of each C type
dynamicly allocated.

--
vir

[Jeremy Yallop]

Victor Nazarov wrote:

Consider I want to write my own version of standard malloc, calloc,
realloc, free. How can I portably check if they work correctly? The most
remarkable will be the test for right justification of each C type
dynamicly allocated.

You can't check alignment (which I assume you mean by "justification")
portably. This is one of the impediments to writing the *alloc family
in standard C. You may be able to use standard C constructs to test
alignment on a particular platform, perhaps by converting the retured
pointer to an integer type and testing divisibility (with the modulus
operator or a bitmask).

#include <stdio.h>

int aligned(void *p, int boundary) {
return !((long)p % boundary);
}
int main() {
double d;
char c;
int x;
void *pointers[] = {&d, &c, &x, 0}, **p = pointers;
int alignments[] = {32, 16, 8, 4, 2, 0}, *i;

for (; *p; p++)
for (i = alignments; *i; i++)
printf("%p is %saligned on a %d-byte boundary\n",
*p, (aligned(*p, *i) ? "" : "not "), *i);
return 0;
}

Of course, you only need to check that the pointer returned by your
implementation of malloc is correctly aligned for /any/ type, i.e. it
must satisfy most stringent alignment requirements on the target
platform.

Jeremy.

[Jeremy Yallop]

Victor Nazarov wrote:

Consider I want to write my own version of standard malloc, calloc,
realloc, free. How can I portably check if they work correctly? The most
remarkable will be the test for right justification of each C type
dynamicly allocated.

You can't check alignment (which I assume you mean by "justification")
portably. This is one of the impediments to writing the *alloc family
in standard C. You may be able to use standard C constructs to test
alignment on a particular platform, perhaps by converting the retured
pointer to an integer type and testing divisibility (with the modulus
operator or a bitmask).

#include <stdio.h>

int aligned(void *p, int boundary) {
return !((long)p % boundary);
}
int main() {
double d;
char c;
int x;
void *pointers[] = {&d, &c, &x, 0}, **p = pointers;
int alignments[] = {32, 16, 8, 4, 2, 0}, *i;

for (; *p; p++)
for (i = alignments; *i; i++)
printf("%p is %saligned on a %d-byte boundary\n",
*p, (aligned(*p, *i) ? "" : "not "), *i);
return 0;
}

Of course, you only need to check that the pointer returned by your
implementation of malloc is correctly aligned for /any/ type, i.e. it
must satisfy most stringent alignment requirements on the target
platform.

Jeremy.

[Malcolm]

"Victor Nazarov" <vv*****@mail.ru> wrote in message

Consider I want to write my own version of standard malloc,
calloc, realloc, free. How can I portably check if they work
correctly? The most remarkable will be the test for right justification
of each C type dynamically allocated.

Use a Block structure to do all your controls. In the block, add a union of
all the basic types, to force alignment.

union alltypes
{
void *x1;
long x2;

... (don't forget function pointers)
};

struct control
{
struct control *next;
struct control *prev;
size_t len;
};

union block
{
union alltypes aligner;
struct control controldata;
};

[Malcolm]

"Victor Nazarov" <vv*****@mail.ru> wrote in message

Consider I want to write my own version of standard malloc,
calloc, realloc, free. How can I portably check if they work
correctly? The most remarkable will be the test for right justification
of each C type dynamically allocated.

Use a Block structure to do all your controls. In the block, add a union of
all the basic types, to force alignment.

union alltypes
{
void *x1;
long x2;

... (don't forget function pointers)
};

struct control
{
struct control *next;
struct control *prev;
size_t len;
};

union block
{
union alltypes aligner;
struct control controldata;
};

[Arthur J. O'Dwyer]

On Mon, 5 Apr 2004, Malcolm wrote:

"Victor Nazarov" <vv*****@mail.ru> wrote in message

Consider I want to write my own version of standard malloc,
calloc, realloc, free. How can I portably check if they work
correctly? The most remarkable will be the test for right justification
of each C type dynamically allocated.

Use a Block structure to do all your controls. In the block, add a union of
all the basic types, to force alignment.

union alltypes
{
void *x1;
long x2;

... (don't forget function pointers)
};

The problem with this, from the c.l.c point of view, is that there's
no way you can possibly make a union of *all* the basic types. For
all you know, the DS9000 requires 1024-byte alignment for array[42] of
double, and 1-byte alignment for all other data types. And there are
an infinity of different pointer types to check.
This is a FAQ both here and c.std.c, as far as I'm concerned. It
would be nice if C0x provided a macro MAX_ALIGNMENT or something so
that you could do this yourself, but as of C99 you still have to make
some non-standard assumption in order to guarantee that 'union alltypes'
is useful.

HTH,
-Arthur

[Arthur J. O'Dwyer]

On Mon, 5 Apr 2004, Malcolm wrote:

"Victor Nazarov" <vv*****@mail.ru> wrote in message

Consider I want to write my own version of standard malloc,
calloc, realloc, free. How can I portably check if they work
correctly? The most remarkable will be the test for right justification
of each C type dynamically allocated.

Use a Block structure to do all your controls. In the block, add a union of
all the basic types, to force alignment.

union alltypes
{
void *x1;
long x2;

... (don't forget function pointers)
};

The problem with this, from the c.l.c point of view, is that there's
no way you can possibly make a union of *all* the basic types. For
all you know, the DS9000 requires 1024-byte alignment for array[42] of
double, and 1-byte alignment for all other data types. And there are
an infinity of different pointer types to check.
This is a FAQ both here and c.std.c, as far as I'm concerned. It
would be nice if C0x provided a macro MAX_ALIGNMENT or something so
that you could do this yourself, but as of C99 you still have to make
some non-standard assumption in order to guarantee that 'union alltypes'
is useful.

HTH,
-Arthur

[Keith Thompson]

Jeremy Yallop <je****@jdyallop.freeserve.co.uk> writes:

Victor Nazarov wrote:

Consider I want to write my own version of standard malloc, calloc,
realloc, free. How can I portably check if they work correctly? The most
remarkable will be the test for right justification of each C type
dynamicly allocated.

You can't check alignment (which I assume you mean by "justification")
portably. This is one of the impediments to writing the *alloc family
in standard C. You may be able to use standard C constructs to test
alignment on a particular platform, perhaps by converting the retured
pointer to an integer type and testing divisibility (with the modulus
operator or a bitmask).

[code snipped]

Let me emphasize Jeremy's point about portability. Though I'm sure
his code will work properly on most systems, I know of at least one
(Cray vector systems) on which it will fail, because pointers are not
represented in the "obvious" way. I wouldn't bet against the
existence of other architectures on which it might also fail.

Leaving aside the alignment issue, there's no good way to check that
the memory requested was actually allocated. Suppose your malloc()
has a bug that causes it to return a pointer to memory that's actually
part of some user variable. The best you can do portably is confirm
that you can read and write the allocated memory -- but the only way
to confirm that you *can't* is to invoke undefined behavior.

A large part of the reason malloc() and friends are in the standard
library is because they *can't* be implemented portably.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"

[Keith Thompson]

Jeremy Yallop <je****@jdyallop.freeserve.co.uk> writes:

Victor Nazarov wrote:

Consider I want to write my own version of standard malloc, calloc,
realloc, free. How can I portably check if they work correctly? The most
remarkable will be the test for right justification of each C type
dynamicly allocated.

You can't check alignment (which I assume you mean by "justification")
portably. This is one of the impediments to writing the *alloc family
in standard C. You may be able to use standard C constructs to test
alignment on a particular platform, perhaps by converting the retured
pointer to an integer type and testing divisibility (with the modulus
operator or a bitmask).

[code snipped]

Let me emphasize Jeremy's point about portability. Though I'm sure
his code will work properly on most systems, I know of at least one
(Cray vector systems) on which it will fail, because pointers are not
represented in the "obvious" way. I wouldn't bet against the
existence of other architectures on which it might also fail.

Leaving aside the alignment issue, there's no good way to check that
the memory requested was actually allocated. Suppose your malloc()
has a bug that causes it to return a pointer to memory that's actually
part of some user variable. The best you can do portably is confirm
that you can read and write the allocated memory -- but the only way
to confirm that you *can't* is to invoke undefined behavior.

A large part of the reason malloc() and friends are in the standard
library is because they *can't* be implemented portably.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
Schroedinger does Shakespeare: "To be *and* not to be"

[Victor Nazarov]

Malcolm wrote:

"Victor Nazarov" <vv*****@mail.ru> wrote in message

Consider I want to write my own version of standard malloc,
calloc, realloc, free. How can I portably check if they work
correctly? The most remarkable will be the test for right justification
of each C type dynamically allocated.

Use a Block structure to do all your controls. In the block, add a union of
all the basic types, to force alignment.

union alltypes
{
void *x1;
long x2;

... (don't forget function pointers)
};

struct control
{
struct control *next;
struct control *prev;
size_t len;
};

union block
{
union alltypes aligner;
struct control controldata;
};

This seems to be the best solution to implement memory management, but
I'd like to find out any ways to test third party memory managements
functions for right (defined in C standard) behavior.

vir

[Victor Nazarov]

Malcolm wrote:

"Victor Nazarov" <vv*****@mail.ru> wrote in message

Consider I want to write my own version of standard malloc,
calloc, realloc, free. How can I portably check if they work
correctly? The most remarkable will be the test for right justification
of each C type dynamically allocated.

Use a Block structure to do all your controls. In the block, add a union of
all the basic types, to force alignment.

union alltypes
{
void *x1;
long x2;

... (don't forget function pointers)
};

struct control
{
struct control *next;
struct control *prev;
size_t len;
};

union block
{
union alltypes aligner;
struct control controldata;
};

This seems to be the best solution to implement memory management, but
I'd like to find out any ways to test third party memory managements
functions for right (defined in C standard) behavior.

vir

[Victor Nazarov]

Keith Thompson wrote:

Jeremy Yallop <je****@jdyallop.freeserve.co.uk> writes:

Victor Nazarov wrote:

Consider I want to write my own version of standard malloc, calloc,
realloc, free. How can I portably check if they work correctly? The most
remarkable will be the test for right justification of each C type
dynamicly allocated.

Thank you for your answers. I suspected that things were just like you
had described. So I think the way out is to forget about portability and
implement everything for the particular architecture.

vir

[Victor Nazarov]

Keith Thompson wrote:

Jeremy Yallop <je****@jdyallop.freeserve.co.uk> writes:

Victor Nazarov wrote:

Consider I want to write my own version of standard malloc, calloc,
realloc, free. How can I portably check if they work correctly? The most
remarkable will be the test for right justification of each C type
dynamicly allocated.

Thank you for your answers. I suspected that things were just like you
had described. So I think the way out is to forget about portability and
implement everything for the particular architecture.

vir

[CBFalconer]

Victor Nazarov wrote:

Keith Thompson wrote:

Jeremy Yallop <je****@jdyallop.freeserve.co.uk> writes:

Victor Nazarov wrote:

Consider I want to write my own version of standard malloc,
calloc, realloc, free. How can I portably check if they work
correctly? The most remarkable will be the test for right
justification of each C type dynamicly allocated.

Thank you for your answers. I suspected that things were just
like you had described. So I think the way out is to forget
about portability and implement everything for the particular
architecture.

The two areas that will require special system dependant attention
are alignment, and where to get the memory to dispense. If you
isolate those operations almost everything else can be quite
standard and portable code. You can find an example at:

<http://cbfalconer.home.att.net/download/nmalloc.zip>

--
"I'm a war president. I make decisions here in the Oval Office
in foreign policy matters with war on my mind." - Bush

[CBFalconer]

Victor Nazarov wrote:

Keith Thompson wrote:

Jeremy Yallop <je****@jdyallop.freeserve.co.uk> writes:

Victor Nazarov wrote:

Consider I want to write my own version of standard malloc,
calloc, realloc, free. How can I portably check if they work
correctly? The most remarkable will be the test for right
justification of each C type dynamicly allocated.

Thank you for your answers. I suspected that things were just
like you had described. So I think the way out is to forget
about portability and implement everything for the particular
architecture.

The two areas that will require special system dependant attention
are alignment, and where to get the memory to dispense. If you
isolate those operations almost everything else can be quite
standard and portable code. You can find an example at:

<http://cbfalconer.home.att.net/download/nmalloc.zip>

--
"I'm a war president. I make decisions here in the Oval Office
in foreign policy matters with war on my mind." - Bush

[Malcolm]

"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote in message

The problem with this, from the c.l.c point of view, is that there's
no way you can possibly make a union of *all* the basic types.
For all you know, the DS9000 requires 1024-byte alignment for
array[42] of double, and 1-byte alignment for all other data types.
I don't think this is allowed, because you can create an array of 42 doubles
from an array of 43 or higher.
And there are an infinity of different pointer types to check.
But all, except function pointers, have got to be interconvertible with void
*.
but as of C99 you still have to make
some non-standard assumption in order to guarantee that 'union
alltypes' is useful.

It may just be possible to write a conforming compiler that does so on a
perverse reading of the standard.

[Malcolm]

"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote in message

The problem with this, from the c.l.c point of view, is that there's
no way you can possibly make a union of *all* the basic types.
For all you know, the DS9000 requires 1024-byte alignment for
array[42] of double, and 1-byte alignment for all other data types.
I don't think this is allowed, because you can create an array of 42 doubles
from an array of 43 or higher.
And there are an infinity of different pointer types to check.
But all, except function pointers, have got to be interconvertible with void
*.
but as of C99 you still have to make
some non-standard assumption in order to guarantee that 'union
alltypes' is useful.

It may just be possible to write a conforming compiler that does so on a
perverse reading of the standard.

[Arthur J. O'Dwyer]

On Tue, 6 Apr 2004, Malcolm wrote:

"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote in message

The problem with this, from the c.l.c point of view, is that there's
no way you can possibly make a union of *all* the basic types.
For all you know, the DS9000 requires 1024-byte alignment for
array[42] of double, and 1-byte alignment for all other data types.

I don't think this is allowed, because you can create an array of 42
doubles from an array of 43 or higher.

Probably true. Still, C&V, please.

And there are an infinity of different pointer types to check.

But all, except function pointers, have got to be interconvertible with
void *.

Interconvertible, yes. Same size as, no. AFAICT it's perfectly
reasonable to have each pointer hold not only a memory address, but
also a representation of its type, a unique identifier, a pointer to a
reference counter, and several kilobytes of padding bits. :) IOW,
while
foo *f = (void*)&f;
void *p = (foo*)&p;
is valid, it is certainly *NOT* the case that
sizeof f == sizeof p
on all platforms.

but as of C99 you still have to make
some non-standard assumption in order to guarantee that 'union
alltypes' is useful.

It may just be possible to write a conforming compiler that does so on a
perverse reading of the standard.

I don't understand that comment. I meant, "in C99 there is no portable
way to construct a 'universal alignment' structure." What did you mean?

-Arthur

[Arthur J. O'Dwyer]

On Tue, 6 Apr 2004, Malcolm wrote:

"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote in message

The problem with this, from the c.l.c point of view, is that there's
no way you can possibly make a union of *all* the basic types.
For all you know, the DS9000 requires 1024-byte alignment for
array[42] of double, and 1-byte alignment for all other data types.

I don't think this is allowed, because you can create an array of 42
doubles from an array of 43 or higher.

Probably true. Still, C&V, please.

And there are an infinity of different pointer types to check.

But all, except function pointers, have got to be interconvertible with
void *.

Interconvertible, yes. Same size as, no. AFAICT it's perfectly
reasonable to have each pointer hold not only a memory address, but
also a representation of its type, a unique identifier, a pointer to a
reference counter, and several kilobytes of padding bits. :) IOW,
while
foo *f = (void*)&f;
void *p = (foo*)&p;
is valid, it is certainly *NOT* the case that
sizeof f == sizeof p
on all platforms.

but as of C99 you still have to make
some non-standard assumption in order to guarantee that 'union
alltypes' is useful.

It may just be possible to write a conforming compiler that does so on a
perverse reading of the standard.

I don't understand that comment. I meant, "in C99 there is no portable
way to construct a 'universal alignment' structure." What did you mean?

-Arthur

[Malcolm]

"Arthur J. O'Dwyer" <aj*@nospam.andrew.cmu.edu> wrote in message

It may just be possible to write a conforming compiler that does > > so

on a perverse reading of the standard.
I don't understand that comment. I meant, "in C99 there is no
portable way to construct a 'universal alignment' structure." What
did you mean?

What I mean is that you might be able to frustrate the alltypes structure by
remaining within the letter of the standard, but doing something perverse,
like making all pointers that point to a structure whose name begins A-M
have a different alignment requirement than pointers to structures beginning
N-Z.

void * may have a less strict alignment requirement than say double *,
however, so this was a mistake.