How the free implemented

[OperaHelloMarch]

I have see a example implementation for free() in IBM developerworks
as below:

void free(void *firstbyte) {

struct mem_control_block *mcb;

/* Backup from the given pointer to find the
* mem_control_block
*/

mcb = firstbyte - sizeof(struct mem_control_block);

/* Mark the block as being available */

mcb->is_available = 1;

/* That's It! We're done. */

return;
}

Here, it doesn't check if the parameter firstbyte is a real firstbyte.
If I write code like below, I think the whole system may crash.

#include <stdlib.h>

int main(int argc, char *argv[])
{
int* ptr;
ptr=(int*)malloc(sizeof(int)*100);

/*OK, to change the position of the head*/
ptr[0]=1;
ptr++;

/*send the invalid pointer to free() */
free(ptr);
}

I have compiled this file under linux, and get an error message "***
glibc detected *** free(): invalid pointer: 0x09fa800c ***"

How can the free() know that my pointer is invalid? Is there any array
for valid pointer stored in memory?

Thanks in advance!

 

[Ian Collins]

Here, it doesn't check if the parameter firstbyte is a real firstbyte.
If I write code like below, I think the whole system may crash.

#include <stdlib.h>

int main(int argc, char *argv[])
{
int* ptr;
ptr=(int*)malloc(sizeof(int)*100);

*please* don't cast the return value of malloc!

/*OK, to change the position of the head*/
ptr[0]=1;
ptr++;

/*send the invalid pointer to free() */
free(ptr);

Undefined behaviour, look out for exploding toilets.

}

I have compiled this file under linux, and get an error message "***
glibc detected *** free(): invalid pointer: 0x09fa800c ***"

How can the free() know that my pointer is invalid? Is there any array
for valid pointer stored in memory?

It's an feature of the implementation. Possibly malloc sets a flag
behind the value returned and free checks it.

 

[santosh]

I have see a example implementation for free() in IBM developerworks
as below:

And because it's an implementation specific code, it can, and probably
has to, freely break the constraints of the standard.

void free(void *firstbyte) {

struct mem_control_block *mcb;

/* Backup from the given pointer to find the
* mem_control_block
*/

mcb = firstbyte - sizeof(struct mem_control_block);

Arithmetic on void pointer values is implementation dependant.

/* Mark the block as being available */

mcb->is_available = 1;

/* That's It! We're done. */

return;
}

Here, it doesn't check if the parameter firstbyte is a real firstbyte.
If I write code like below, I think the whole system may crash.

It doesn't need to check.

#include <stdlib.h>

int main(int argc, char *argv[])
{
int* ptr;
ptr=(int*)malloc(sizeof(int)*100);

Don't cast the return value of malloc in C.

/*OK, to change the position of the head*/
ptr[0]=1;
ptr++;

/*send the invalid pointer to free() */
free(ptr);
}

I have compiled this file under linux, and get an error message "***
glibc detected *** free(): invalid pointer: 0x09fa800c ***"

How can the free() know that my pointer is invalid? Is there any array
for valid pointer stored in memory?

As far as the standard is concerned, free must receive a value
previously obtained from malloc, calloc or realloc. Anything else is
undefined behaviour. However a particular implementation is allowed to
define undefined behaviour and do something that may be sane for that
implementation as long as it doesn't break the fundamental rules of C.

How glibc's free detected your spurious argument can be answered only
by glibc's source code.

 

[OperaHelloMarch]

It's an feature of the implementation. Possibly malloc sets a flag
behind the value returned and free checks it.

I don't think a special value is a good idea, Maybe I should go and
study the source code of glibc.

 

[OperaHelloMarch]

Thanks, I will go to read the source code.

I have see a example implementation for free() in IBM developerworks
as below:

And because it's an implementation specific code, it can, and probably
has to, freely break the constraints of the standard.

void free(void *firstbyte) {

struct mem_control_block *mcb;

/* Backup from the given pointer to find the
* mem_control_block
*/

mcb = firstbyte - sizeof(struct mem_control_block);

Arithmetic on void pointer values is implementation dependant.

/* Mark the block as being available */

mcb->is_available = 1;

/* That's It! We're done. */

Here, it doesn't check if the parameter firstbyte is a real firstbyte.
If I write code like below, I think the whole system may crash.

It doesn't need to check.

#include <stdlib.h>

int main(int argc, char *argv[])
{
int* ptr;
ptr=(int*)malloc(sizeof(int)*100);

Don't cast the return value of malloc in C.

/*OK, to change the position of the head*/
ptr[0]=1;
ptr++;

/*send the invalid pointer to free() */
free(ptr);
}

I have compiled this file under linux, and get an error message "***
glibc detected *** free(): invalid pointer: 0x09fa800c ***"

How can the free() know that my pointer is invalid? Is there any array
for valid pointer stored in memory?

As far as the standard is concerned, free must receive a value
previously obtained from malloc, calloc or realloc. Anything else is
undefined behaviour. However a particular implementation is allowed to
define undefined behaviour and do something that may be sane for that
implementation as long as it doesn't break the fundamental rules of C.

How glibc's free detected your spurious argument can be answered only
by glibc's source code.

 

[Ian Collins]

*Please trim signatures!*

I don't think a special value is a good idea, Maybe I should go and
study the source code of glibc.

Why not? That's how I do it in my test allocator.

 

[llothar]

int* ptr;

Don't cast the return value of malloc in C.

Why. I'm getting warnings/errors from my C compiler if i don't do it.

 

[santosh]

Why. I'm getting warnings/errors from my C compiler if i don't do it.

No, you're getting errors from a C++ compiler. In C++ a cast is
necessary for conversion to/from void to other pointer types, but in
C, it's not needed. You're invoking your combined C and C++ compiler
in C++ mode. Try using it in C only mode.

 

[CBFalconer]

.... snip ...

I have compiled this file under linux, and get an error message
"*** glibc detected *** free(): invalid pointer: 0x09fa800c ***"

How can the free() know that my pointer is invalid? Is there any
array for valid pointer stored in memory?

It requires a combination of voodoo and black magic. System
programmers also draw myriad pentacles and spin widdershins within
them.

Try reading some source code for malloc implementations. Beware
that they are intrinsically system dependant. You can find the
source for glibc, or you can try:

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

[1] c:\c\junk>cc junk.o nmalloc.o -o junk.exe

[1] c:\c\junk>junk
free: memory fouled
Exiting due to signal SIGABRT
Raised at eip=00004a0e
eax=0008e20c ebx=00000120 ecx=00000000 edx=0000000a esi=00000054
edi=0000e328
ebp=0008e2b8 esp=0008e208 program=C:\C\JUNK\JUNK.EXE
cs: sel=00a7 base=88c4f000 limit=0009ffff
ds: sel=00b7 base=88c4f000 limit=0009ffff
es: sel=00b7 base=88c4f000 limit=0009ffff
fs: sel=0087 base=0000a5d0 limit=0000ffff
gs: sel=00c7 base=00000000 limit=0010ffff
ss: sel=00b7 base=88c4f000 limit=0009ffff
App stack: [0008e328..0000e328] Exceptn stack:
[0000e288..0000c348]

Call frame traceback EIPs:
0x00004934 __djgpp_traceback_exit+48, file c:/c/malloc/nmalloc.c,
line 1024
0x00004a0e raise+90, file c:/c/malloc/nmalloc.c, line 1024
0x00001da0 free+80, file c:/c/malloc/nmalloc.c, line 840
0x00001657 main+39, file c:/c/junk/junk.c, line 11
0x00003ad8 __crt1_startup+176, file c:/c/malloc/nmalloc.c, line
1024

[1] c:\c\junk>symify junk.exe

 

[CBFalconer]

.... snip ...

I have compiled this file under linux, and get an error message
"*** glibc detected *** free(): invalid pointer: 0x09fa800c ***"

How can the free() know that my pointer is invalid? Is there any
array for valid pointer stored in memory?

It requires a combination of voodoo and black magic. System
programmers also draw myriad pentacles and spin widdershins within
them.

Try reading some source code for malloc implementations. Beware
that they are intrinsically system dependant. You can find the
source for glibc, or you can try:

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

[1] c:\c\junk>cc junk.o nmalloc.o -o junk.exe

[1] c:\c\junk>junk
free: memory fouled
Exiting due to signal SIGABRT
Raised at eip=00004a0e
eax=0008e20c ebx=00000120 ecx=00000000 edx=0000000a esi=00000054
edi=0000e328
ebp=0008e2b8 esp=0008e208 program=C:\C\JUNK\JUNK.EXE
cs: sel=00a7 base=88c4f000 limit=0009ffff
ds: sel=00b7 base=88c4f000 limit=0009ffff
es: sel=00b7 base=88c4f000 limit=0009ffff
fs: sel=0087 base=0000a5d0 limit=0000ffff
gs: sel=00c7 base=00000000 limit=0010ffff
ss: sel=00b7 base=88c4f000 limit=0009ffff
App stack: [0008e328..0000e328] Exceptn stack:
[0000e288..0000c348]

Call frame traceback EIPs:
0x00004934 __djgpp_traceback_exit+48, file c:/c/malloc/nmalloc.c,
line 1024
0x00004a0e raise+90, file c:/c/malloc/nmalloc.c, line 1024
0x00001da0 free+80, file c:/c/malloc/nmalloc.c, line 840
0x00001657 main+39, file c:/c/junk/junk.c, line 11
0x00003ad8 __crt1_startup+176, file c:/c/malloc/nmalloc.c, line
1024

[1] c:\c\junk>symify junk.exe

 

[CBFalconer]

Why. I'm getting warnings/errors from my C compiler if i don't do it.

Please don't remove attributions (joe wrote: lines) for material
you quote.

Those errors mean you are doing something wrong. Some
possibilities include:

failing to #include <stdlib.h>
failing to use a C compiler. A C++ compiler will do this.

See the cfaq, which you should already have done.

--
Some useful references about C:
<http://www.ungerhu.com/jxh/clc.welcome.txt>
<http://www.eskimo.com/~scs/C-faq/top.html> (cfaq)
<http://benpfaff.org/writings/clc/off-topic.html>
<http://anubis.dkuug.dk/jtc1/sc22/wg14/www/docs/n869/> (C99)
<http://www.dinkumware.com/refxc.html> (C-library}
<http://gcc.gnu.org/onlinedocs/> (GNU docs)
<http://clc-wiki.net> (C-info)

 

[Flash Gordon]

santosh wrote, On 04/03/07 13:21:

No, you're getting errors from a C++ compiler.

How do you know? He might be getting warnings because he has not
included stdlib.h.

> In C++ a cast is
necessary for conversion to/from void to other pointer types, but in
C, it's not needed. You're invoking your combined C and C++ compiler
in C++ mode. Try using it in C only mode.

This is good advice.

Another good rule is *NEVER* put in a cast to get rid of a warning. Only
ever put in casts when you have a full and complete understanding of why
in a specific instance a cast is required. In the case of malloc it is
NOT required in C and casting just hides the problem not curing it,
where the problem is either what Santosh suggested or what I suggested.

 

[Stephen Sprunk]

I don't think a special value is a good idea, Maybe I should go and
study the source code of glibc.

It's a common technique, whether you like it or not. The other obvious
technique is that malloc() would create a separate set of data structures to
keep track of allocations, and free() would traverse that checking to see if
the pointer you gave it was one malloc() had previously returned. This is
safer, but significantly slower. The fastest method of all, of course, is
to do no checking at all; the Standard doesn't require any.

S

 

[Keith Thompson]

santosh wrote, On 04/03/07 13:21:

How do you know? He might be getting warnings because he has not
included stdlib.h.


This is good advice.

Another good rule is *NEVER* put in a cast to get rid of a
warning. Only ever put in casts when you have a full and complete
understanding of why in a specific instance a cast is required. In the
case of malloc it is NOT required in C and casting just hides the
problem not curing it, where the problem is either what Santosh
suggested or what I suggested.

Agreed. Yet another good rule: never do *anything* just to get rid of
a warning, without understanding what you're doing.

 

[Flash Gordon]

Keith Thompson wrote, On 05/03/07 03:59:

Agreed. Yet another good rule: never do *anything* just to get rid of
a warning, without understanding what you're doing.

Yes, I agree completely.

 

[Richard Bos]

Why. I'm getting warnings/errors from my C compiler if i don't do it.

Then you've forgotten to #include <stdlib.h>.

If you do #include that header and you still get that diagnostic, you're
not using a C compiler but one for an inferior knock-off.

Richard

 

[santosh]

Then you've forgotten to #include <stdlib.h>.

If you do #include that header and you still get that diagnostic, you're
not using a C compiler but one for an inferior knock-off.

Or perhaps a pre-ANSI C compiler?

 

[Richard Tobin]

Agreed. Yet another good rule: never do *anything* just to get rid of
a warning, without understanding what you're doing.

You might even eliminate "just to get rid of a warning" from that
sentence...

-- Richard

 

[Daniel Rudy]

At about the time of 3/4/2007 1:11 AM, (e-mail address removed) stated
the following:

I have see a example implementation for free() in IBM developerworks
as below:

void free(void *firstbyte) {

struct mem_control_block *mcb;

/* Backup from the given pointer to find the
* mem_control_block
*/

mcb = firstbyte - sizeof(struct mem_control_block);

/* Mark the block as being available */

mcb->is_available = 1;

/* That's It! We're done. */

return;
}

There's got to be more to it than that. Make that alot more.

Here, it doesn't check if the parameter firstbyte is a real firstbyte.
If I write code like below, I think the whole system may crash.

#include <stdlib.h>

int main(int argc, char *argv[])
{
int* ptr;
ptr=(int*)malloc(sizeof(int)*100);

/*OK, to change the position of the head*/
ptr[0]=1;
ptr++;

/*send the invalid pointer to free() */
free(ptr);
}

I have compiled this file under linux, and get an error message "***
glibc detected *** free(): invalid pointer: 0x09fa800c ***"

How can the free() know that my pointer is invalid? Is there any array
for valid pointer stored in memory?

Thanks in advance!

On *MY* system (FreeBSD which is another version of Unix like Linux is),
free(3) calls pubrealloc with a few preset parameters. pubrealloc is
called by malloc(3), realloc(3), and free(3). Digging into the code, I
have determined that pubremalloc determines what to do based on the
parameters that it gets. Internally, there is imalloc, irealloc, and ifree.

It seems that the smallest amount of memory that can be allocated is a
chunk, which is set as a predetermined size which I believe is 128 bytes
(based on a u_int (32 bit unsigned int on my system). But looking that
the structure, it seems that it can vary from 128 bytes to pagesize.
ifree calls two different functions: free_bytes and free_pages.
free_bytes frees chunks of memory and moves their locations from the
allocated list to the free list, both of which are doubly linked lists.
There seems to be a third list that keeps track of pages as well.

From what I can gather, free_bytes scans the allocated list looking for
the pointer in question. If it doesn't find it, then it kicks it back,
otherwise it moves the entry to the free list. If the memory block is
larger than 128 bytes, it seems to move the entire block over to the
free list. After something has been freed, it updates the page list.

Now this is where things get interesting. If the page has nothing
allocated on it, and it's the last page, then free_pages calls madvise
with the MADV_FREE flag then uses brk(2) and sbrk(2) to return the page
or pages to the operating system. There is also an internal function
called map_pages that uses those same syscalls to map pages from the
system into the processes data segment. And I found another suprize...
it uses mmap(2) to allocate the first page in malloc_init and uses that
for the directory.

I guess this is *somewhat* on topic in comp.lang.c because we are
talking about a standard C library function, but since this is also
Unix, I've added comp.unix.programmer to the list.

--
Daniel Rudy

Email address has been base64 encoded to reduce spam
Decode email address using b64decode or uudecode -m

Why geeks like computers: look chat date touch grep make unzip
strip view finger mount fcsk more fcsk yes spray umount sleep

 

[Lew Pitcher]

I have see a example implementation for free() in IBM developerworks
as below:

[snip]

free() is a part of the whole malloc()/calloc()/free() memory
management facility of the C standard library, and any discussion of
it must be taken in that context.

The IBM Developerworks site gave you one implementation of free(), but
that free() presumes a corresponding, complimentary and compatable
implementation of malloc() and calloc(). Trying to use the IBM sample
code for free() without having used the corresponding code for
malloc() is just asking for problems.

IIRC, K&R discuss a rudimentary malloc()/free() in "The C Programming
Language", in which the free() looks something like the example IBM
code you presented. In that rudimentary allocator, memory was taken
from a pool of static storage on malloc(), and returned to the pool on
free(). Each block of memory taken from the pool was managed with a
simple structure which preceded the memory returned to the caller.
Your IBM code presumes similar.