realloc() implicit free() ?

[CBFalconer]

7.20.3p1 sentence 2:

"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 usedto access such an object or an array
of such objects in the space allocated (until the space is
explicitly deallocated)."


I'm not sure why, the Rationale doesn't give any hints here. It
doesn't particularly make sense that the allocated space must be
aligned to store an object that could not fit into the space,
perhaps there is another reason we are overlooking or maybe I'm
misinterpreting the above quote.

The malloc subsystem doesn't know, and can't know, what type the
pointer will be used for. It returns a void*, and the only
information it gets is the size required. That size may be for one
item, or for many items.

Similarly the application has no information as to the alignment
requirements for a type. The compiler system does. That is one of
the fundamental reasons that malloc is a system function, and
simply cannot be written in purely portable code.

--
Some informative links:
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

 

[CBFalconer]

I'm writing a malloc thing and compiling it in gcc on a pc.
How do you know what the alignment should be?

No, and neither can you. Only the system implementor can know.
You can make some educated guesses in some cases, but you can never
find out in a portable manner.

--
Some informative links:
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

 

[Michael Mair]

Thanks, Rob

The malloc subsystem doesn't know, and can't know, what type the
pointer will be used for. It returns a void*, and the only
information it gets is the size required. That size may be for one
item, or for many items.

Similarly the application has no information as to the alignment
requirements for a type. The compiler system does. That is one of
the fundamental reasons that malloc is a system function, and
simply cannot be written in purely portable code.

Hmmm, I can accept this as an additional explanation but still do
not see the _necessity_ for the standard giving the cited
restriction.
Thank you.

Cheers
Michael

 

[Michael Mair]

Indeed, it does seem unnecessary. It also seems to be what the
Standard requires. I suspect, however, that an implementor might
be able to get away with the "as-if" rule and align to just 2 bytes
in this case, provided the following code fragment still works:

void *vp;
char *cp;
double *dp;
/* add other types if desired */

cp = malloc(3);
if (cp == NULL) ... handle error ...
vp = cp;
dp = vp;
assert(vp == cp);
assert(dp == vp);
cp = (char *)dp;
assert(cp == vp);
puts("all OK");

In other words, if we have a system on which we can detect "failure
to align for any object whatsoever" by just using ordinary pointer
assignments, *then* that system will have to do 16-byte (or whatever)
alignment for a 3-byte malloc; but if the system handles "misaligned"
pointers without trouble, as long as they are not used to access
their misaligned objects, then -- because there will be no way for
the user to tell -- the as-if rule will allow us to implement
malloc(3) with just two-byte alignment.

Thank you -- as usual, I can learn something from your response

Cheers
Michael

 

[Eric Sosman]

7.20.3p1 sentence 2:

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

Taken in isolation, this sentence says that

struct s { char c[30000]; } x = { 0 };
struct s *p = malloc(1); /* assume success */
*p = x;

should work: The allocation has succeeded, the returned value
is therefore suitably aligned for any type (`struct s' in
particular), the value can be assigned to any type of pointer
(including `struct s*'), and can then be used to access an
object of that type. All the preconditions of the sentence
are met -- and yet, the access is obviously not permitted.

What this means is that snipping a sentence from the rest
of the Standard can distort its meaning. Elsewhere in the
Standard we can learn that `*p = x' produces undefined behavior,
so no conforming program can access a `struct s' through the
value returned by this particular malloc(). It follows that no
conforming program can actually encounter any alignment
problem by trying to access a `struct s' through this pointer;
the access itself is forbidden. Under the "as if" rule, if
nothing else, I believe malloc(1) can perfectly well return a
value that is not `struct s'-aligned because no conforming
program can ever detect the non-alignment.

However, the quoted sentence still places some restrictions
on what malloc(1) could return. For example,

void *p1 = malloc(1); /* assume success */
double *dp = p1;
void *p2 = dp;
assert (p2 == p1);

That is, converting the pointer to `double*' and back again
must not change its value. On machines where pointers to
different types have different representations, malloc(1) is
constrained to return values that can be converted to and from
any data pointer type without damage -- but as long as the
conversion is guaranteed to succeed, I don't think the value
need actually suffice for any data type that won't fit in the
allocated space.

 

[Chris Torek]

I'm writing a malloc thing and compiling it in gcc on a pc.
How do you know what the alignment should be?

Alas, ANSI/ISO C does not have any way to find out.

In the absence of the ability to write "comp.lang.c-conformant" code,
if you still need to get the job done, write non-conformant code.

For the various 4.xBSD systems, we defined a pair of macros (in
one of the <machine/*.h> headers), ALIGN(p) and ALIGNBYTES, that
do the trick.

The "machine" headers are different on each implementation, but
attempt to abstract out as much as possible. Thus, for instance,
<machine/frame.h> gives the stack frame for whatever implementation
you are using, always as a "struct frame" (and additional special
frames for user => kernel boundary crossings, in some cases). This
works fine as long as there is one consistent call-stack frame,
and you can write a simplified stack-trace-dump function that works
on (say) five completely different architectures (with some assistant
functions or macros), as long as they all use just the one "struct
frame". This eases code porting, but is not perfect: as soon as
you try to support (say) both 32- and 64-bit SPARC routines, you
start to need to distinguish between a 32-bit stack frame and a
64-bit stack frame ("struct frame32" and "struct frame64"), and
you must write a SPARC-specific "simplified stack-trace-dump"
module. Still, you get to share the original (single frame) dump
routine across those five machines, so that instead of six source
files to maintain (for six architectures), you have just two.

The idea is simple enough: make common code to solve common problems.
The trick is knowing what is common, what is not, and how to abstract
away irrelevant details without losing the important details.

 

[Robert Gamble]

7.20.3p1 sentence 2:

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

Taken in isolation, this sentence says that

struct s { char c[30000]; } x = { 0 };
struct s *p = malloc(1); /* assume success */
*p = x;

should work:

No, it doesn't.

The allocation has succeeded, the returned value is
therefore suitably aligned for any type (`struct s' in particular), the
value can be assigned to any type of pointer (including `struct s*'),
and can then be used to access an object of that type. All the
preconditions of the sentence are met -- and yet, the access is
obviously not permitted.

The only thing being discussed here is alignmentment requirements. The
above quote states that your object created with malloc will be properly
*aligned* to hold any type, not that any type can actually be stored in it
if the space doesn't exist.

Rob Gamble

 

[S.Tobias]

Taken in isolation, this sentence says that

struct s { char c[30000]; } x = { 0 };
struct s *p = malloc(1); /* assume success */
*p = x;

should work: The allocation has succeeded, the returned value
is therefore suitably aligned for any type (`struct s' in
particular), the value can be assigned to any type of pointer
(including `struct s*'), and can then be used to access an
object of that type. All the preconditions of the sentence
are met -- and yet, the access is obviously not permitted.

What this means is that snipping a sentence from the rest
of the Standard can distort its meaning. (3)
Elsewhere in the
Standard we can learn that `*p = x' produces undefined behavior,
so no conforming program can access a `struct s' through the
value returned by this particular malloc().

[ snipped implications which follow from (1) and (3),
but somehow (2) was lost, because it didn't fit into the theory;
rejected only 30% of facts - congratulations of a success! ]

So, under your interpretation, the Standard in one place *requires*
something that it forbids at another, and yet you're happy about it?
What do you people drink to keep you out of depression?


How about this: I say the Standard requires `malloc(1)' to return
at least enough space to accommodate `struct s'.
Stretched? Yes, but fits your assumptions better.

In another post I offered a different interpretation of the Standard,
which IMHO is more rational (I mean the implications are more rational,
not the interpretation itself), but I won't argue for its credibility,
because I'm not completely convinced myself.

Yet another resolution could be to acknowledge the Standard has
simply an error there and no conclusions can be drawn.

 

[Stephen Sprunk]

Hmmm, I can accept this as an additional explanation but still do
not see the _necessity_ for the standard giving the cited
restriction.

If malloc() were allowed to inspect the size of the request and
determine that it was allowed to return a pointer to something of a
different alignment than normal, there would be nothing wrong with that
per se.

However, it is reasonable to assume that no existing implementation did
that at the time C89 was written, nor that any new implementation after
that time would take advantage of that "feature" since it'd be extra
work for virtually no gain, so why make a point of allowing it? Letting
malloc() deal with a single alignment for all requests, regardless of
size, is the simpler option.

S

 

[Walter Roberson]

# The question is not over-specified if one is concerned about
# whether one is leaking memory. When your datasets are ~1 Gb each
# and you are handling them in a loop, you can't afford to allow memory
# to leak.

All you can do to prevent leaks is to match frees to allocs; you don't need to
know how the library is implemented to do that much. It's still leaking
you're stuck unless you can get the library source code.

That's not ALL you can do: you can also ask questions about paragraphs
that one might have overlooked or which might have been clarified
in addendums that one hasn't seen, which proscribe the behaviour
of library routines so as to remove the ambiguity.

If no-one happens to know the answer, or if the answer is
indeterminate, then one can sometimes write one's own routine that
avoids the indeterminate behaviour. In the case of realloc(),
since it is never -required- that the address be left unchanged,
one can write a replacement for realloc() in terms of malloc(),
a memory copy, and a free(), provided that one knows the current
size of the object at hand.

 

[SM Ryan]

(e-mail address removed)-cnrc.gc.ca (Walter Roberson) wrote:

# That's not ALL you can do: you can also ask questions about paragraphs
# that one might have overlooked or which might have been clarified
# in addendums that one hasn't seen, which proscribe the behaviour
# of library routines so as to remove the ambiguity.

Do you have sample code of how to do that?

 

[Russell Shaw]

That's not ALL you can do: you can also ask questions about paragraphs
that one might have overlooked or which might have been clarified
in addendums that one hasn't seen, which proscribe the behaviour
of library routines so as to remove the ambiguity.

If no-one happens to know the answer, or if the answer is
indeterminate, then one can sometimes write one's own routine that
avoids the indeterminate behaviour. In the case of realloc(),
since it is never -required- that the address be left unchanged,
one can write a replacement for realloc() in terms of malloc(),
a memory copy, and a free(), provided that one knows the current
size of the object at hand.

For the address to not change, the new realloc'd size must fit in
the same place. If there was occupied memory following your data
and you wanted to increase the size of your data, the realloc will
have to copy it all to a different location where it will fit.
In this case, the address *will* change.

 

[Walter Roberson]

(e-mail address removed)-cnrc.gc.ca (Walter Roberson) wrote:

# That's not ALL you can do: you can also ask questions about paragraphs
# that one might have overlooked or which might have been clarified
# in addendums that one hasn't seen, which proscribe the behaviour
# of library routines so as to remove the ambiguity.

Do you have sample code of how to do that?

Sure, but are you finding a deficiency in your existing facility to ask
intelligent questions about matters whose resolutions are not immediately
clear?

 

[S.Tobias]

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

Taken in isolation, this sentence says that
struct s { char c[30000]; } x = { 0 };
struct s *p = malloc(1); /* assume success */

Just a thought:

There might actually be a reason to require `p' to have max alignment
(assignment-wise) for `malloc(0)'. It is even documented in
the Rationale:
OBJ *p = calloc(0, sizeof(OBJ));
The Standard obviously wants to support zero-length array paradigm,
although zero-size objects are not supported.

`malloc(1)' may be considered as "a zero-length array (of any type)
plus 1 byte ``padding'' ".
When you need a zero-length array, but at the same time you need
a unique pointer (and it is not known if malloc(0) returns NULL
or not), then malloc(1) (or generally: malloc(n*size+1), n==0,1,2,...)
will always provide such pointer.

Therefore we actually want `malloc(n)' to return for every `n' a value
that is aligned suitably for any type.

However I still can't see any reason to require max alignment
access-wise (more than the requested size), but maybe this is just
not to make things too complicated. The Standard could simply
say that the returned pointer value has maximum alignment, but
for strange reason it chose to say in a circuitous way that the
alignment is maximal both assignment-wise and access-wise (which
is exactly the same thing), forgetting that access itself is
not always possible.


[Sorry for being a little ironic last time.]

 

[Walter Roberson]

Walter Roberson wrote:

For the address to not change, the new realloc'd size must fit in
the same place. If there was occupied memory following your data
and you wanted to increase the size of your data, the realloc will
have to copy it all to a different location where it will fit.
In this case, the address *will* change.

Yes? I must be missing your point? Or did you perchance overlook
my double negative? "never required [...] left unchanged" means
"the routine may change the address under any circumstances it
feels fit."

If one writes a replacement version of realloc() in terms of
malloc/copy/free (and an additional parameter that indicates
the object's -current- size), then what one loses is the
-possibility- that the data won't have to move (and thus
be copied) if extra space just happens to be available
immediately after to the current object. But that's an
efficiency optimization; and especially if one is working with
large data sets, the extra efficiency might be pretty meaningless
compared to the possibility that one is leaking large chunks
of memory if indeed realloc() does not free the original
memory chunk when it happens to move data.


My user was satisfied with the posted analysis that in C99 the
as-if free() is explicit, and that in C89 the as-if free() is the
most reasonable interpretation. My commentatary in this sub-thread
is only around the point of whether I should have been telling my user
"You shouldn't even be -thinking- about whether there might be a memory
leak or not: it is Not Allowed to ask questions even to yourself about
anything not explicitly made clear in the one paragraph of the standard
most directly dedicated to defining the routine."

 

[Russell Shaw]

Walter Roberson wrote:


For the address to not change, the new realloc'd size must fit in
the same place. If there was occupied memory following your data
and you wanted to increase the size of your data, the realloc will
have to copy it all to a different location where it will fit.
In this case, the address *will* change.

Yes? I must be missing your point? Or did you perchance overlook
my double negative? "never required [...] left unchanged" means
"the routine may change the address under any circumstances it
feels fit."

I saw the context of:

...one can write a replacement for realloc() in terms of malloc(),
memory copy, and a free(), provided that one knows the current
size of the object at hand.

combined with the context of the preceding part as meaning that
you could make it so that the returned address was never changed.

If one writes a replacement version of realloc() in terms of
malloc/copy/free (and an additional parameter that indicates
the object's -current- size), then what one loses is the
-possibility- that the data won't have to move

In other words, it *will* move. But not so. If the new size passed in
is smaller than the current size, you could just return the same address.

> (and thus
be copied) if extra space just happens to be available
immediately after to the current object. But that's an
efficiency optimization; and especially if one is working with
large data sets, the extra efficiency might be pretty meaningless
compared to the possibility that one is leaking large chunks
of memory if indeed realloc() does not free the original
memory chunk when it happens to move data.

I know what you mean, but your double negatives are a bit confusing

My user was satisfied with the posted analysis that in C99 the
as-if free() is explicit, and that in C89 the as-if free() is the
most reasonable interpretation. My commentatary in this sub-thread
is only around the point of whether I should have been telling my user
"You shouldn't even be -thinking- about whether there might be a memory
leak or not: it is Not Allowed to ask questions even to yourself about
anything not explicitly made clear in the one paragraph of the standard
most directly dedicated to defining the routine."

ok

 

[SM Ryan]

(e-mail address removed)-cnrc.gc.ca (Walter Roberson) wrote:
# In article <[email protected]>,
# >[email protected] (Walter Roberson) wrote:
#
# ># That's not ALL you can do: you can also ask questions about paragraphs
# ># that one might have overlooked or which might have been clarified
# ># in addendums that one hasn't seen, which proscribe the behaviour
# ># of library routines so as to remove the ambiguity.
#
# >Do you have sample code of how to do that?
#
# Sure, but are you finding a deficiency in your existing facility to ask
# intelligent questions about matters whose resolutions are not immediately
# clear?

Simple 'no' would've sufficed.

Someday you'll learn about modular programming.

 

[CBFalconer]

Robert Gamble wrote:
.... snip ...

7.20.3p1 sentence 2:

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

Taken in isolation, this sentence says that

struct s { char c[30000]; } x = { 0 };
struct s *p = malloc(1); /* assume success */
*p = x;

should work: The allocation has succeeded, the returned value
is therefore suitably aligned for any type (`struct s' in
particular), the value can be assigned to any type of pointer
(including `struct s*'), and can then be used to access an
object of that type. All the preconditions of the sentence
are met -- and yet, the access is obviously not permitted.

However, if you follow that with:

if (tmp = realloc(p, sizeof *p) {
p = tmp;
*p = x;
}

access is perfectly legitimate, and p may not necessarily have
changed. The alignment is now needed.

--
Some informative links:
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

 

[CBFalconer]

.... snip ...

How about this: I say the Standard requires `malloc(1)' to return
at least enough space to accommodate `struct s'.
Stretched? Yes, but fits your assumptions better.

No. malloc has no way of knowing what such a requirement is.

--
Some informative links:
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html

 

[Walter Roberson]

Someday you'll learn about modular programming.

My Magic 8-Ball seems to be out of order this evening; I don't
see how modular programming has to do with the question of whether
or not "all" one can do is interpret documentation narrowly and
at face value.

It seems to me that, in the absence of knowledge of whether
the as-if free() was or was not done, use of realloc() would
be contrary to Dijkstra's principles of structured programming
that routines should be -provably- correct. Code that leaks memory
(except at program exit) would seldom be "probably correct".

Someday you'll learn about modular programming.

A long time ago, in a galaxy far far away...