letting free() know how much to free...?

[Jim H]

In one of my functions I create a char string s, of dynamic allocated
length.

I want to free the memory before my function returns. Everywhere I find
says free(s) is the way to do this, but I'm not so sure. How can the
language
know how much space to free? It looks to me as if this would just free the
first
char in the string, since an array is a pointer to it's first element.

What am I missing?

 

[Richard Bos]

I want to free the memory

"The" memory? What memory? You can't just call free() on any pointer,
you know. It must be a pointer you previously got from *alloc(), and
which hasn't been freed in the mean time.

before my function returns. Everywhere I find
says free(s) is the way to do this, but I'm not so sure.

Well, what other way would you use?

How can the language know how much space to free?

It knows. By magic, if that's how it wants to do it. Suffice it to know
that the Standard require that if *alloc() allocate memory and return a
pointer to it, free() knows how to free that memory when given that, and
no other, pointer.

It looks to me as if this would just free the first char in the string,
since an array is a pointer to it's first element.

I cannot fathom that logic.

Richard

 

[Dan Pop]

In one of my functions I create a char string s, of dynamic allocated
length.

I want to free the memory before my function returns. Everywhere I find
says free(s) is the way to do this, but I'm not so sure.

If everyone says this is the proper way, there must be a reason...

How can the language know how much space to free?

The language neither knows nor cares. It is the implementation of the
dynamical memory allocation function that does. And its obvious how:
because you specified the size when you allocated the memory block.
malloc gave you the address of the block, but memorised its size
somewhere. This somewhere can be in a block header that precedes the
block, so, when you give the block address to free(), it can easily
compute the address of the block header and retrieve its size from there.
That's why strange things can happen if you write beyond the limits of the
dynamically allocated memory blocks.

It looks to me as if this would just free the first
char in the string, since an array is a pointer to it's first element.

If you have a pointer to the first byte, you can also figure out the
size of the array, if you memorised it at the array allocation time,
which is what malloc and friends typically do. I have already showed
you a simple way of doing it, but it's not the only possible method (e.g.
a table associating a length to each allocated block starting address
could be maintained by malloc and friends and searched by free).

What am I missing?

Many things, apparently.

Dan

 

[Christopher Benson-Manica]

since an array is a pointer to it's first element.

This sounds like a job for the FAQ:

http://www.eskimo.com/~scs/C-faq/q6.3.html
http://www.eskimo.com/~scs/C-faq/q6.8.html

 

[Leor Zolman]

In one of my functions I create a char string s, of dynamic allocated
length.

I want to free the memory before my function returns. Everywhere I find
says free(s) is the way to do this, but I'm not so sure. How can the
language
know how much space to free? It looks to me as if this would just free the
first
char in the string, since an array is a pointer to it's first element.

What am I missing?

In K&R, there is, I believe, an implementation of alloc() and free() that
you may want to take a look at (for demystification purposes). The
executive summary: the pointer you get from malloc() et. al. refers to
your requested amount of memory (except when it is NULL, of course), but
"parasitically clinging" to that memory, typically just before it (I'm not
sure whether other implementations are possible), is a data structure that
gives free() the ability to re-assimilate that memory into the free
store...and that data structure includes the size of the allocated block,
among other things.
-leor

Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html

 

[Jim H]

since an array is a pointer to it's first element.

This sounds like a job for the FAQ:

http://www.eskimo.com/~scs/C-faq/q6.3.html
http://www.eskimo.com/~scs/C-faq/q6.8.html

You rightly saw it was the the equivalence between arrays and pointers
that I was
getting mixed up in.
I had been told that an array and a pointer to the start of the array were
exactly the
same in every way, so given an array:

char * str[];

sizeof( str ) would be the same as sizeof( &(str[0]) );

I can now see that the equivalence only goes so far. Thanks for the help.

 

[Malcolm]

and that data structure includes the size of the allocated block,
among other things.

Actually if you implement malloc() and free() in the obvious way, then all
you need is the size of the block. You can tell where the block is by
pointer arithmetic, and that's all you need to know to consolidate freed
blocks and keep track of them.

 

[Ben Pfaff]

Actually if you implement malloc() and free() in the obvious way, then all
you need is the size of the block. You can tell where the block is by
pointer arithmetic, and that's all you need to know to consolidate freed
blocks and keep track of them.

How are you going to efficiently find the beginning of the
previous block if you only store the size of the current block?
If you can't find the beginning of the previous block, how can
you do consolidation?

 

[Leor Zolman]

Actually if you implement malloc() and free() in the obvious way, then all
you need is the size of the block. You can tell where the block is by
pointer arithmetic, and that's all you need to know to consolidate freed
blocks and keep track of them.

To be precise, I should have said "...includes the size of the allocated
block (or a reasonable way for it to be deduced), among other things."

As soon as I read another post in the thread discussing how the size can be
derived, I just knew someone was going to bring this up. If this is the
worst misspeak I commit over the next week...it probably means I'm about to
stop posting for a week ;-)
-leor


Leor Zolman
BD Software
(e-mail address removed)
www.bdsoft.com -- On-Site Training in C/C++, Java, Perl & Unix
C++ users: Download BD Software's free STL Error Message
Decryptor at www.bdsoft.com/tools/stlfilt.html

 

[Malcolm]

How are you going to efficiently find the beginning of the
previous block if you only store the size of the current block?
If you can't find the beginning of the previous block, how can
you do consolidation?

As we allocate and free memory the arena fragments. We store the fragments
as a linked list which is always kept in ascending order.
When a block is freed you can find its place in the list by walking it until
two pointers straddle the block to be freed.
To consolidate, we need to know the size and the intial position of the
previous block, the size and intial position of the block to be freed, and
the size and intial position of the following block. Since the intial
position of the block to free is given by the pointer, it follows that all
we need to store is the size, in a block that is allocated. Blocks in the
free list, however, need both size information and pointers to the next
block.
If you attempt to store the location of the previous block you run into
problems when it is broken up or consolidated by further allocations.
Walking a linked list is fast, but it is still an O(N) operation. In
practise the easiest way of getting rid of this inefficiency is to treat
small blocks specially. You then have only a few big allocations to run from
the general-purpose allocator. If you are sufficiently determined you can
store all the free blocks in a balanced binary tree and find the position of
the free block that way.