How does free() knows?

[Suyog_Linux]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

 

[Joona I Palaste]

Suyog_Linux <[email protected]> scribbled the following

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

It depends entirely on the implementation. An internal variable is one
way, but there might be others. The standard does not mandate any
specific way.

 

[John Burton]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().

Most likely yes, although there is no portable way for users' programs to
get at this value.

I guess it's also possible that it might not keep the length explicity but
might instead keep a pointer to the next block, or maybe just keeps lists of
blocks of various sizes and get malloc to hand out a block from the list
with the next larger block... Or other schemes.

Given that the system almost certainly knows how big the block is I'm always
a little suprised that there is not getallocsize(void*) or some such
function to get the amount of allocated space in a block as it would be
fairly useful for some applications.

 

[SM Ryan]

(e-mail address removed) (Suyog_Linux) wrote:
# I wish to know how the free()function knows how much memory to be
# freed as we only give pointer to allocated memory as an argument to
# free(). Does system use an internal variable to store allocated memory
# when we use malloc().

The implementation is permitted any magic that correctly implements the interface.

With terabytes of VM and 64 bit addresses becoming available, an acceptable malloc
implementation for many programs is that malloc always allocates new memory
and free doesn't do anything but immediately return. Such an implementation doesn't
need to store block sizes anywhere.

 

[William L. Bahn]

Suyog_Linux <[email protected]> scribbled the following


It depends entirely on the implementation. An internal variable is one
way, but there might be others. The standard does not mandate any
specific way.

Out of curiosity (and I know that the standard does not mandate
any specific way) but are the mechancis of this something that is
usually handled by the program code (the stuff thrown in by the
compiler) or are the mechanics generally done by the operating
system? Which side of the house, more often than not, keeps track
of this? Would it be reasonable (not necessarily right and
certainly not guaranteed to be right) to suspect that with
smaller code sizes (memory models) that the program's "heap"
space is a block of memory that the OS gave it as start up and
the program manages the assignment requests within that block but
if you are working with a program that can request, at least
cumulatively, hundreds of megabytes of dynamic memory that the
program requests additional memory from the OS (perhaps in fewer,
but larger chunks) and the OS keeps track of the butcher's bill
for that?

 

[Karthik Kumar]

(e-mail address removed) (Suyog_Linux) wrote:
# I wish to know how the free()function knows how much memory to be
# freed as we only give pointer to allocated memory as an argument to
# free(). Does system use an internal variable to store allocated memory
# when we use malloc().

The implementation is permitted any magic that correctly implements the interface.

With terabytes of VM and 64 bit addresses becoming available, an acceptable malloc
implementation for many programs is that malloc always allocates new memory
and free doesn't do anything but immediately return. Such an implementation doesn't
need to store block sizes anywhere.

That would be a memory leak. At least free needs to flag something,
so that memory manager may act in the b.g. to get the job done.

 

[Michael Steve]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

One sneaky method is to hide that sort of information before the pointer
address returned by malloc(). So free() takes the address, then goes a few
addresses back, and knows the information on the size of the memory that was
allocated.

As stated in other offshoots of this post, there is no standard method to do
this prescribed by the standard.

Michael Steve

 

[John Smith]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

See Knuth's works for descriptions on memory allocation techniques. Of
course there might be an infinite number of different ways of implementing
memory allocation, but at least he describes some of them.

 

[Peter Koch Larsen]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

There is no standard way. Also bear in mind that "how much memory to be
freed" might not be the same as "how much memory was allocated".

/Peter

 

[Richard Tobin]

I guess it's also possible that it might not keep the length explicity

One way is to allocate blocks of different sizes from different areas
of memory, so that the size is implicit in the high-order address
bits. This technique is also used for object typing in
implementations of some languages, where it's known as "bibop".

-- Richard

 

[Thomas Matthews]

to be


argument to


allocated memory


is one



Out of curiosity (and I know that the standard does not mandate
any specific way) but are the mechancis of this something that is
usually handled by the program code (the stuff thrown in by the
compiler) or are the mechanics generally done by the operating
system?

The mechanics are up to the compiler implementor. Some compilers
have their own memory allocation schemes. Others use the operating
systems memory management routines. Still other compilers allow
users to provide their own.

There is nothing stopping program code from implementing
its own memory management.

Which side of the house, more often than not, keeps track
of this?

Probably the dark side; could be the section between the
ceiling and the bottom of the upper floor (where the pipes
may live).

Most programs leave memory management up to the compiler
implementation. Some non-portable programs may use the
operating system features. And yet other programs implement
their own memory management scheme. The simplest method
is to use the language memory allocation features and don't
worry _how_ it is implemented. There are more important
topics to worry about, such as program correctness, than
what operates under the hood of a language.

Would it be reasonable (not necessarily right and
certainly not guaranteed to be right) to suspect that with
smaller code sizes (memory models) that the program's "heap"
space is a block of memory that the OS gave it as start up and
the program manages the assignment requests within that block but
if you are working with a program that can request, at least
cumulatively, hundreds of megabytes of dynamic memory that the
program requests additional memory from the OS (perhaps in fewer,
but larger chunks) and the OS keeps track of the butcher's bill
for that?

Could be reasonable, could not be. Depends.
Many multi-user systems have different memory sizes set aside
for different users. Some operating systems implement a paging
system, where the program is given a "page" of memory and any
allocation beyond that page cause another one to be loaded in.
Some systems have a fixed memory size regardless of the executable
code size.

Executable code size has no relationship to the amount of memory
required by the executable program. A small program can be written
that uses a lot of memory while a large program can be written
that uses very little memory.

Focus on completing the program and getting all the bugs out
(correctness) before even thinking about how much memory it
needs, how fast it is or the size of the code. The latter
topics can all be optimized after profiling the program.


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Thomas Matthews]

I wish to know how the free()function knows how much memory to be
freed as we only give pointer to allocated memory as an argument to
free(). Does system use an internal variable to store allocated memory
when we use malloc().
Plz help......

Another method is to supply the size of the target in
the pointer structure:
<address, block size>
{Hey, I said it was another idea, maybe not the best.}


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[Peter Ho]

www.cours.polymtl.ca/inf6100/notes/chap9/chap9.html
The above link shows you how this works. Unfortunatly, it is written in French.

Peter
www.1sttechnews.com

 

[CBFalconer]

.... snip ...

Executable code size has no relationship to the amount of memory
required by the executable program. A small program can be written
that uses a lot of memory while a large program can be written
that uses very little memory.

This has (and has had) nothing to do with c.l.c++. F'ups set.

The following baby program will show how much memory you can
allocate in your system to a single object. If the returned
pointers change for each iteration the malloc package probably
does not go to any effort to avoid unnecessary copying, and maybe
needlessly slow.

/* mgobble.c - gobble as much memory as possible */

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
char *temp, *gobbler = NULL;
size_t sz = 1;

while ((temp = realloc(gobbler, sz))) {
printf("%10lu %p\n", (unsigned long)sz, (void *)temp);
gobbler = temp;
sz += sz;
}
free(gobbler);
return 0;
} /* main mgobble.c */

 

[Keith Thompson]

William L. Bahn wrote: [...]

Out of curiosity (and I know that the standard does not mandate
any specific way) but are the mechancis of this something that is
usually handled by the program code (the stuff thrown in by the
compiler) or are the mechanics generally done by the operating
system?

The mechanics are up to the compiler implementor. Some compilers
have their own memory allocation schemes. Others use the operating
systems memory management routines. Still other compilers allow
users to provide their own.

To be precise, it's up to the runtime library implementor. We often
use the term "compiler" to refer to the entire C implementation, but
it's more correct to refer to the compiler and the standard library as
separate things. They typically aren't even implemented by the same
people.

For example, on a Solaris system, I might gcc, but if my program
contains a call to malloc() or free(), the compiler just generates a
function call. The actual implementation is part of the runtime
library provided by Sun.

There is nothing stopping program code from implementing
its own memory management.

True, but you're likely to run into problems if you try to use the
names "malloc" and "free" for your memory management. (Some systems
may have ways of overriding the system memory management functions;
the details are off-topic here.) If you want to write your own
my_malloc() and my_free() functions, of course you can do so -- but
then system routines that your program calls are likely to use the
predefined malloc() and free(), so your memory manager had better be
able to coexist with the one provided by the system.

 

[Keith Thompson]

One way is to allocate blocks of different sizes from different areas
of memory, so that the size is implicit in the high-order address
bits. This technique is also used for object typing in
implementations of some languages, where it's known as "bibop".

Really? That sounds like it could be terribly inefficient -- a
program that allocates only chunks of a certain size could run out of
memory when there's still plenty left in another region. Though I
suppose the implementation could do something fancy in mapping real to
virtual addresses, so the unused areas don't actually exist.

I found a web reference to something called "Big Bag of Pages",
abbreviated "bipop". But I'm a bit skeptical that this would make
sense for a C-style malloc/free system.

Nevertheless, it's a good example of the kind of thing the standard
allows -- which means programmers who make unwarranted assumptions
about the inner workings of the memory management system are likely to
get into trouble.

 

[Keith Thompson]

Another method is to supply the size of the target in
the pointer structure:
<address, block size>
{Hey, I said it was another idea, maybe not the best.}

You'd need an offset along with the base address and size. For
example, the following is valid:

char *p = malloc(100);
char *q = p + 10;
free(q - 10);

If the information needed by free() is going to be stored in the
pointer, then q has to retain enough information to get back to the
base address of the allocated object. Either the "address" field of q
points to the base of the allocated object, with an offset of 10, or
the "address" field points directly to p[10] and the offset is -10;
the latter scheme might make for more efficient code.

This also gives you the possibility of run-time bounds checking.

 

[E. Robert Tisdale]

I wish to know how the free()function knows
how much memory to be freed
as we only give pointer to allocated memory as an argument to free().
Does system use an internal variable to store allocated memory
when we use malloc().

It depends upon the implementation.
Try this:

cat main.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
if (1 < argc) {
const
size_t n = atoi(argv[1]);
int* p = (int*)malloc(n*sizeof(int));
fprintf(stdout, "%d = p[-1]\n", p[-1]);
}
return 0;
}

gcc -Wall -std=c99 -pedantic -o main main.c
./main 1 17 = p[-1]
./main 2 17 = p[-1]
./main 3 17 = p[-1]
./main 4 25 = p[-1]
./main 5 25 = p[-1]
./main 6 33 = p[-1]
./main 7 33 = p[-1]
./main 8 41 = p[-1]
./main 9 41 = p[-1]
gcc --version

gcc (GCC) 3.3.3 20040412 (Red Hat Linux 3.3.3-7)

 

[Keith Thompson]

(e-mail address removed) (Suyog_Linux) wrote:
# I wish to know how the free()function knows how much memory to be
# freed as we only give pointer to allocated memory as an argument to
# free(). Does system use an internal variable to store allocated memory
# when we use malloc().

The implementation is permitted any magic that correctly implements
the interface.

With terabytes of VM and 64 bit addresses becoming available, an
acceptable malloc implementation for many programs is that malloc
always allocates new memory and free doesn't do anything but
immediately return. Such an implementation doesn't need to store
block sizes anywhere.

Please use the conventional "> " prefix for quoted text.
Please keep your lines down to about 72 columns.
Please use the standard "-- " signature delimiter.

I don't believe that an implementation of free() that does nothing
would be acceptable. The "terabytes of VM" you're talking about are
typically stored on disk; if you allocate more than the amount of
physical memory, your program is going to slow down as it swaps data
between disk and memory. For that matter, you're likely to slow down
the entire system, and you'll still run out eventually.

I work on some pretty big systems; they typically have no more than a
few gigabytes of virtual memory.

Even assuming terabytes of fast, cheap virtual memory and a full
64-bit address space, consider a program that does something like
this:

while (1) {
/* allocate a few megabytes of memory */
/* do some work */
/* free the allocated memory */
}

(Think of a server or a system daemon that runs continuously for
months at a time.) If free() does nothing, this is a serious memory
leak which will crash the program and/or bog down the system.

Fortunately, I don't believe that anyone has actually implemented such
a system.

 

[Richard Tobin]

Really? That sounds like it could be terribly inefficient -- a
program that allocates only chunks of a certain size could run out of
memory when there's still plenty left in another region. Though I
suppose the implementation could do something fancy in mapping real to
virtual addresses, so the unused areas don't actually exist.

Yes, you would probably map the regions as required on a modern machine.

Even without that, the pages for a given size don't all have to be
contiguous. You can have a map from high-order bits to sizes, and a
list of regions for going the other way.

I found a web reference to something called "Big Bag of Pages",
abbreviated "bipop".

That's it.

-- Richard