malloc/free question

[Snis Pilbor]

Howdy C warriors =)

I'd like to be able to malloc a block of memory, then later free just a
certain (trailing or leading) portion of it. For example, malloc 100
bytes, then later free the last 20 of them. If I just blindly do
something like free(myptr + 80), will this:

1. be guaranteed to do what I want and safely free the last 20 bytes,
2. be guaranteed to corrupt memory, or
3. have behavior dependent on implementation and not nailed down by C
specifications?

If 2 or 3, is there some other way to do what I want? For example some
way of telling it to malloc 80 bytes, then 20, but specify that the 20
must start where the 80 end?

BTW, the reason I want to do this is I am computing a linked list of
structures for later usage. During the computation stage, each element
will require some extra storage for computations, but once computation
is done and the list is prepared, this extra storage will no longer be
needed. Yes, I could maintain a separate and parallel linked list for
just the calculation storage, but this would be a big pain.

Thanks =)

 

[Morris Dovey]

Snis Pilbor (in (e-mail address removed))
said:

| I'd like to be able to malloc a block of memory, then later free
| just a certain (trailing or leading) portion of it. For example,
| malloc 100 bytes, then later free the last 20 of them. If I just
| blindly do something like free(myptr + 80), will this:
|
| 1. be guaranteed to do what I want and safely free the last 20
| bytes,
| 2. be guaranteed to corrupt memory, or
| 3. have behavior dependent on implementation and not nailed down
| by C specifications?

Read up on the realloc() function. It will allow you to "re-size" an
area previously obtained with malloc(). If you want to discard the
data in the beginning of an allocation, then you'll need to either
shift the data to overwrite what you don't want before realloc()ing -
or allocate a new (smaller) area, copy the still-wanted data to it,
and then free() the original area.

 

[Tom St Denis]

Howdy C warriors =)

I'd like to be able to malloc a block of memory, then later free just a
certain (trailing or leading) portion of it. For example, malloc 100
bytes, then later free the last 20 of them. If I just blindly do
something like free(myptr + 80), will this:

<snip>

look up realloc.

Tom

 

[Tom St Denis]

Howdy C warriors =)

I'd like to be able to malloc a block of memory, then later free just a
certain (trailing or leading) portion of it. For example, malloc 100
bytes, then later free the last 20 of them. If I just blindly do
something like free(myptr + 80), will this:

<snip>

look up realloc.

Tom

 

[Keith Thompson]

Howdy C warriors =)

I'd like to be able to malloc a block of memory, then later free just a
certain (trailing or leading) portion of it. For example, malloc 100
bytes, then later free the last 20 of them. If I just blindly do
something like free(myptr + 80), will this:

1. be guaranteed to do what I want and safely free the last 20 bytes,
2. be guaranteed to corrupt memory, or
3. have behavior dependent on implementation and not nailed down by C
specifications?

Calling free() with a pointer that isn't either the result of a
previous call to malloc(), calloc(), or realloc() or a null pointer
invokes undefined behavior. Your option 3 comes closest to describing
this, except that the implementation is under no obligation to define
or document the behavior, and it can depend on anything (including the
phase of the moon) and cause arbitrarily bad results (nasal demons).

As others have said, you want realloc().

 

[Andrey Tarasevich]

I'd like to be able to malloc a block of memory, then later free just a
certain (trailing or leading) portion of it. For example, malloc 100
bytes, then later free the last 20 of them.

Cannot be done by standard means.

If I just blindly do
something like free(myptr + 80), will this:

1. be guaranteed to do what I want and safely free the last 20 bytes,
2. be guaranteed to corrupt memory, or
3. have behavior dependent on implementation and not nailed down by C
specifications?

No. This will lead to undefined behavior. In practice, it will crash on
most platforms. If it doesn't crash immediately, it will damage the
integrity of the heap and crash later.

If 2 or 3, is there some other way to do what I want? For example some
way of telling it to malloc 80 bytes, then 20, but specify that the 20
must start where the 80 end?

For this you'll have to implement your own custom memory management
routines (custom allocator). Others suggested 'realloc', but in reality
'realloc' is not doing what you need because it is not guaranteed to
keep the block in its original location (even if requested to shrink the
block).

BTW, the reason I want to do this is I am computing a linked list of
structures for later usage. During the computation stage, each element
will require some extra storage for computations, but once computation
is done and the list is prepared, this extra storage will no longer be
needed. Yes, I could maintain a separate and parallel linked list for
just the calculation storage, but this would be a big pain.

Hmm... That's how it is usually done.

Or you can update you code to make it work with 'realloc', i.e. be ready
that the list element might suddenly jump to other place in memory after
being 'realloc'-ed.

 

[Al Balmer]

Howdy C warriors =)

I'd like to be able to malloc a block of memory, then later free just a
certain (trailing or leading) portion of it. For example, malloc 100
bytes, then later free the last 20 of them. If I just blindly do
something like free(myptr + 80), will this:

1. be guaranteed to do what I want and safely free the last 20 bytes,
2. be guaranteed to corrupt memory, or
3. have behavior dependent on implementation and not nailed down by C
specifications?

3, but tending toward 2.

Use realloc.

 

[Keith Thompson]

3, but tending toward 2.

Use realloc.

I recommended this myself, but be careful. As somebody pointed out,
realloc() may relocate the object, even if the requested size is
smaller than the original size. For that matter, it's not even
guaranteed that a realloc() requesting a smaller size will succeed;
there's probably no good reason for it to fail, but you should always
check the result anyway, and be prepared to deal with a failure.

 

[Al Balmer]

I recommended this myself, but be careful. As somebody pointed out,
realloc() may relocate the object, even if the requested size is
smaller than the original size.

True, but you rarely care, unless it has pointers into itself. Of
course, since this is a linked list, you'd need to fix up the links.

For that matter, it's not even
guaranteed that a realloc() requesting a smaller size will succeed;
there's probably no good reason for it to fail, but you should always
check the result anyway, and be prepared to deal with a failure.

SOP.

I do wonder if the OP really needs to keep the extra 20 bytes attached
until the list is complete, or whether he could use a fixed temporary
area for the processing of each element.

Even if the temp information has to be retained until the end, I'd
seriously consider using two lists. It's really no more trouble than
using one, and a lot less messy to free the unneeded one.

 

[Stephen Sprunk]

I recommended this myself, but be careful. As somebody pointed out,
realloc() may relocate the object, even if the requested size is
smaller than the original size. For that matter, it's not even
guaranteed that a realloc() requesting a smaller size will succeed;
there's probably no good reason for it to fail, but you should always
check the result anyway, and be prepared to deal with a failure.

Cite? I thought realloc() is not allowed to fail or move the block if the
requested size is the same or smaller than the existing block.
Realistically, is there any implementation out there (other than the DS9k)
where that assumption doesn't hold? Even if the block moves, that's a
standard problem with using realloc() which needs to be dealt with in most
cases, so it's good to get in the habit.

With only 20 bytes being returned and the size of the bookkeeping overhead
for malloc() et al to track those 20 bytes and try to reuse them (if
possible), it's almost not worth the effort to bother shrinking the block.
Keeping a second list with those extra 20 bytes may be worth the easier
disposal of the blocks, plus it may reduce heap fragmentation as a bonus.

S

 

[Richard Heathfield]

Stephen Sprunk said:

Cite? I thought realloc() is not allowed to fail or move the block if the
requested size is the same or smaller than the existing block.

No cite available, as far as I can see. Basically, the Standard does not
place those restrictions on realloc. If it did, we could cite!

<snip>

 

[Keith Thompson]

Cite? I thought realloc() is not allowed to fail or move the block if
the requested size is the same or smaller than the existing
block.

C99 7.20.3.4.

If memory for the new object cannot be allocated, the
old object is not deallocated and its value is unchanged.

The realloc function returns a pointer to the new object (which
may have the same value as a pointer to the old object), or a null
pointer if the new object could not be allocated.

The standard says nothing about *why* the new object could not be
allocated.

Realistically, is there any implementation out there (other
than the DS9k) where that assumption doesn't hold? Even if the block
moves, that's a standard problem with using realloc() which needs to
be dealt with in most cases, so it's good to get in the habit.

It's quite possible that a shrinking realloc() never actually fails in
any real-world implementation (but I wouldn't use that as an excuse to
forego checking the result). It seems entirely plausible that a
shrinking realloc() might move the object if might make for more
efficient future allocations.

[...]

 

[Snis Pilbor]

(snip)

With only 20 bytes being returned and the size of the bookkeeping overhead
for malloc() et al to track those 20 bytes and try to reuse them (if
possible), it's almost not worth the effort to bother shrinking the block.
Keeping a second list with those extra 20 bytes may be worth the easier
disposal of the blocks, plus it may reduce heap fragmentation as a bonus.

Hehe, obviously 20 bytes was an arbitrary example. In actuality the
actual amount in my code is dynamic and not even fixed at runtime.
Anyway in light of all the comments I think a parallel list is the best
solution, though it would certainly be nice if it WERE possible to free
bits and pieces of allocated blocks...

This may be wandering dangerously near the boundaries of topic, but I
always assumed when you malloc a block, of say size N, it would
actually select a block of size (say) N+100 (or replace 100 with
something else, it is just a guess), use the extra 100 to store
metadata, which would either precede or follow the N bytes (if it
preceded, then malloc would actually return a pointer 100 bytes in,
making the process invisible to the user). And that this metadata is
how "free" knows how to behave in the first place. This sacrifices
some memory but to do things any other way, would require a separate
pointer table/tree which mean it would cost at least O(log n) time just
to free a pointer (where n=number of blocks that have ever been
allocated minus number of blocks that have ever been freed)

If this assumption is true and the meta data followed the actual block,
then it would be trivial for the malloc developer to allow shrinking
like I wanted. But I guess this is a very naive view of things, I'm
sure there is a lot more going on in a malloc than meets the eye... =)

C sure is the most interesting computer language =)

 

[Gordon Burditt]

Hehe, obviously 20 bytes was an arbitrary example. In actuality the

Ok, let's suppose that was 20k or 20 meg.

actual amount in my code is dynamic and not even fixed at runtime.
Anyway in light of all the comments I think a parallel list is the best
solution, though it would certainly be nice if it WERE possible to free
bits and pieces of allocated blocks...

You can. Allocate a smaller piece, copy, and free the original
allocation. Or call realloc() if the piece you want to free is at
the *END* of the block.

This may be wandering dangerously near the boundaries of topic, but I
always assumed when you malloc a block, of say size N, it would
actually select a block of size (say) N+100 (or replace 100 with
something else, it is just a guess), use the extra 100 to store
metadata, which would either precede or follow the N bytes (if it
preceded, then malloc would actually return a pointer 100 bytes in,
making the process invisible to the user). And that this metadata is
how "free" knows how to behave in the first place.

Some implementations actually do this. It is common that the
metadata is closer to the size of one or two pointers or integers
(e.g. 4-16 bytes). Also, the metadata is likely *BEFORE* the user
data (if it was *AFTER*, how would you find it?).

This sacrifices
some memory but to do things any other way, would require a separate
pointer table/tree which mean it would cost at least O(log n) time just
to free a pointer (where n=number of blocks that have ever been
allocated minus number of blocks that have ever been freed)

If this assumption is true and the meta data followed the actual block,
then it would be trivial for the malloc developer to allow shrinking
like I wanted.

No, it wouldn't. If you pass in a pointer *SOMEWHERE IN THE BLOCK*,
how the heck to you find the metadata? Remember, the user's data
can contain absolutely anything, including looking sort of like
metadata, only it's wrong.

Some implementations of realloc() know enough to shrink a block in
place (the metadata is *BEFORE* the block) without any copying.
But you have to pass in the pointer from malloc() or realloc(), not
it plus something.

But I guess this is a very naive view of things, I'm
sure there is a lot more going on in a malloc than meets the eye... =)

C sure is the most interesting computer language =)

Gordon L. Burditt

 

[Don Porges]

Hehe, obviously 20 bytes was an arbitrary example. In actuality the
actual amount in my code is dynamic and not even fixed at runtime.
Anyway in light of all the comments I think a parallel list is the best
solution, though it would certainly be nice if it WERE possible to free
bits and pieces of allocated blocks...

Instead of a parallel list, what's wrong with each of your list elements containing a
pointer to its extended information, said memory being freed -- and its pointer
explicitly set to NULL -- when you're done with the extended information? This
costs one pointer's-worth of data in each list element but then you don't have to
keep two pointers, one into each list. Or do I misunderstand your goal? (Do you
really mean "not even fixed at runtime"?)

 

[Al Balmer]

This may be wandering dangerously near the boundaries of topic, but I
always assumed when you malloc a block, of say size N, it would
actually select a block of size (say) N+100 (or replace 100 with
something else, it is just a guess), use the extra 100 to store
metadata, which would either precede or follow the N bytes (if it
preceded, then malloc would actually return a pointer 100 bytes in,
making the process invisible to the user).

One of many ways of doing it.

A lot of research has gone into memory allocation algorithms, and many
papers have been written.

 

[Al Balmer]

Hehe, obviously 20 bytes was an arbitrary example. In actuality the
actual amount in my code is dynamic and not even fixed at runtime.
Anyway in light of all the comments I think a parallel list is the best
solution, though it would certainly be nice if it WERE possible to free
bits and pieces of allocated blocks...

If you can spare room in the main list for a pointer, each item can
point to an allocated block of temporary memory. When you don't need
it any more, just walk your list and free each block.