malloc/free question 
Author Message
 malloc/free question

In a recent C programming class, an intresting question was posed to the
"teacher".  How does the free function "know" how much memory to de-allocate
after malloc has reserved it ?

EXAMPLE :

int *p;
p = mal
loc(10);   /* reserve 10 bytes of storage */
.......
.......
free(p);          /* "de-allocate" those 10 bytes */

The "teacher" does not know hoe free "remembers" how much to de-allocate.

I suggested that malloc probably returns a pointer to a structure that has
a pointer to the "allocated" memory and also the number of bytes that were
allocated, so, when the free function is called using the pointer to the
structure, free uses the bytes allocate member of that structure to
"de-allocate" the memory.  

This notion of mine totally blew the
teachers mind
(its a community college advanced C programming course !!).  He said the
only way to find out would be to get the source for the malloc and free
functions.  I dont THINK I would require the source if some of you out there
already know (but it would be nice to see the source, just for the buzz...)
how these two functions operate.

I considered this intresting enough to use as my first posting to the net,
so I apoligize if the answer is in some other group.

Thanks in advance to anyone who answers this posting !!



Wed, 14 Oct 1992 01:36:27 GMT  
 malloc/free question

Quote:

>In a recent C programming class, an intresting question was posed to the
>"teacher".  How does the free function "know" how much memory to de-allocate
>after malloc has reserved it ?

Well, in M'soft languages, malloc allocates a buffer at least two bytes bigger
than what you ask for.  The size of the buffer is stored in the first two
bytes, and the pointer malloc() returns points to the third byte of the buffer.

free() then takes the pointer, subtracts two from it to find where the size is
stored, and takes it from there.

Not to much different from what you thought.


Kaleb Keithley

spelling and grammar flames > /dev/null



Wed, 14 Oct 1992 07:44:02 GMT  
 malloc/free question
<
<In a recent C programming class, an intresting question was posed to the
<"teacher".  How does the free function "know" how much memory to de-allocate
<after malloc has reserved it ?
<
< [ example deleted ]
<
<
<The "teacher" does not know hoe free "remembers" how much to de-allocate.
<
<I suggested that malloc probably returns a pointer to a structure that has
<a pointer to the "allocated" memory and also the number of bytes that were
<allocated, so, when the free function is called using the pointer to the
<structure, free uses the bytes allocate member of that structure to
<"de-allocate" the memory.  
<
This is, as they say, 'implementation dependant'.  Typically, though, it is
done much as you suspected.  A hunk of memory is allocated from the heap,
somewhat larger than the requested size.  At the start of this hunk, such
information as size (and other bookkeeping info) is stored.

<This notion of mine totally blew the
<teachers mind
<(its a community college advanced C programming course !!).  He said the
<only way to find out would be to get the source for the malloc and free
<functions.  I dont THINK I would require the source if some of you out there
<already know (but it would be nice to see the source, just for the buzz...)
<how these two functions operate.
<
Well, if you really want to, there are quite a few PD C compilers out there,
some even with source for the libraries if you really want to see how a
semi-real world malloc works.  However, be warned that this is a non-trivial
problem.  Not to mention the fact that looking at other people's C code can
make you wish you stayed in bed.  If your interest is more academic, you
can look at any decent data structures text, and it will probably describe
several dynamic memory handling schemes.

The text I have is _Data_Structures_in_Pascal_ bye Horowitz & Sahni, ISBN
0-88175-165-0.  This is an OK text, but the code tends to be pretty awful
(they use goto's like they get a commission for each one...).

<I considered this intresting enough to use as my first posting to the net,
<so I apoligize if the answer is in some other group.

No need to apologize.  This is a reasonable question, and as appropriate to
this group as any other.

<Thanks in advance to anyone who answers this posting !!

No problem.

Dave Schaumann          | "Strange women lying in ponds distributing swords

FidoNet: 1/300/4        |               -M. python



Wed, 14 Oct 1992 08:44:18 GMT  
 malloc/free question
Quote:

>In a recent C programming class, an intresting question was posed to the
>"teacher".  How does the free function "know" how much memory to de-allocate
>after malloc has reserved it ?
> [...]
>I suggested that malloc probably returns a pointer to a structure that has
>a pointer to the "allocated" memory and also the number of bytes that were
>allocated, so, when the free function is called using the pointer to the
>structure, free uses the bytes allocate member of that structure to
>"de-allocate" the memory.  

Well I have never seen the source for a malloc and I don't know how it is
normally done but a moment's thought will suggest that the above can't work.
Consider the following:
    char *ptr = malloc(64);
    strcpy(ptr, "Stomp on the malloc structure");
    free(ptr);

So what happens to the data in the structure?  More likely it uses an
internal lookup table such as:
    static struct {
        void *ptr;
        size_t len;
    } malloc_structure[MAX_MALLOC_STRUCTURES];

I am sure that there are other possibilities and in fact different compilers
may use different techniques but any implementation must return a pointer to
the actual memory allocated.

Quote:
>This notion of mine totally blew the teachers mind

Mine too :-)

--

D'Arcy Cain Consulting             |   Organized crime with an attitude
West Hill, Ontario, Canada         |
(416) 281-6094                     |



Wed, 14 Oct 1992 10:07:11 GMT  
 malloc/free question
Quote:

>Well, in M'soft languages, malloc allocates a buffer at least two bytes bigger

          ^^^^^^
        is this MS-C compiler?

Quote:
>than what you ask for.  The size of the buffer is stored in the first two
>bytes, and the pointer malloc() returns points to the third byte of the buffer.

>free() then takes the pointer, subtracts two from it to find where the size is
>stored, and takes it from there.

        If it is, does 'malloc()' in MSC guarantee continuous mem. block?
        If not, how does this 2-bytes info. handle non-contiguous block?

--
        Daeshik Kim     H: (301) 445-0475/2147 O: (703) 689-5878




Wed, 14 Oct 1992 11:04:38 GMT  
 malloc/free question

Quote:

>    If it is, does 'malloc()' in MSC guarantee continuous mem. block?
>    If not, how does this 2-bytes info. handle non-contiguous block?

The memory has to be allocated contiguously.  Otherwise you couldn't do
something like:

ptr = malloc(10 * sizeof(struct x));

for(i=0; i<10; i++)
 {
  ptr[i] = some_value;
  ptr ++;
 }

I know this could be done with fewer statements, but this is a tad bit more
readable.

---

Intergraph Corp.        uunet!ingr!b23b!naomi!lester



Thu, 15 Oct 1992 00:56:13 GMT  
 malloc/free question

Quote:

> ptr = malloc(10 * sizeof(struct x));

> for(i=0; i<10; i++)
>  {
>   ptr[i] = some_value;
>   ptr ++;
>  }

Oops, it should be:
for(i=0; i<10; i++)
 {
  ptr[i] = some_value; or ptr++ = some_value;
 }
---

Intergraph Corp.        uunet!ingr!b23b!naomi!lester

--
---

Intergraph Corp.        uunet!ingr!b23b!naomi!lester



Thu, 15 Oct 1992 02:22:34 GMT  
 malloc/free question

Quote:

>In a recent C programming class, an intresting question was posed to the
>"teacher".  How does the free function "know" how much memory to de-allocate
>after malloc has reserved it ?

The answer is "it has to know somehow".  The method is implementation-
specific.  The *usual* technique is to essentially allocate a struct
like this:

        struct {
                size_t nbytes;
                char space[size_the_user_asked_for];
        }

and then record the size in "nbytes" and return a pointer to "space".
When free() is handed the pointer to "space", it uses its knowledge
of the structure to map that back to a pointer to the whole thing, and
then picks up the size from "nbytes".

There are other methods.  In particular, an intelligent malloc that sees
a lot of requests for the same size (quite common in programs using linked
lists) may set aside an area of memory for blocks of that size, in which
case free() first tests its argument to see if it points into that area.
(Note, the details of this test are machine-specific.)  That avoids the
overhead of having an "nbytes" value for each of many small blocks.  There
are a number of other similar techniques.
--
If OSI is the answer, what is |     Henry Spencer at U of Toronto Zoology



Thu, 15 Oct 1992 07:17:33 GMT  
 malloc/free question

Quote:

>    If it is, does 'malloc()' in MSC guarantee continuous mem. block?

The malloc() function, by definition, must return a single contiguous block
of memory.
--
If OSI is the answer, what is |     Henry Spencer at U of Toronto Zoology



Thu, 15 Oct 1992 07:18:20 GMT  
 malloc/free question
"Use the source, Luke"

In K&R 1, on page 173, you find the following subheading:

        8.7  Example - A Storage Allocator

The remainder of this page, and the following four pages, include what appears
to be the version of malloc for the Ritchie compiler. It's certainly a
plausible implementation.

I can't recommend K&R enough. Not only is it the original source for the C
language, but it's an excellent book in its own right. Too many language
designers seem incapable of producing both a good tutorial and usable reference
manual for their brainchild... this book is a notable exception to the rule.
--


\_.--._/
      v        Disclaimer: People have opinions, organisations have policy.



Thu, 15 Oct 1992 21:37:52 GMT  
 malloc/free question

Quote:


>>        If it is, does 'malloc()' in MSC guarantee continuous mem. block?

>The malloc() function, by definition, must return a single contiguous block
>of memory.

And also, the free() function will coalesce returned memory blocks so that memory
does become too fragmented. By the way, the original K&R, section 8.7 has the source
code for a basic memory allocator, including alloc() and free(). Check it out!
-----
Barry Friedman  | "Why stop now, just when I'm hating it?" Marvin the paranoid android


Fri, 16 Oct 1992 06:14:41 GMT  
 malloc/free question

Quote:


>>Well, in M'soft languages, malloc allocates a buffer at least two bytes bigger
>      ^^^^^^
>    is this MS-C compiler?

Yes, this includes M'soft C 5.1, QC 2.01, Pascal 3.31, and probably Pascal 4.0
but I don't have Pascal 4.0 to check.

Quote:
>    If it is, does 'malloc()' in MSC guarantee continuous mem. block?

Yes, if it can't honor the request, then it returns NULL.  What good would
a non-continous block of memory be? :-)

Quote:
>    If not, how does this 2-bytes info. handle non-contiguous block?

I'm not sure what you mean by this.  I personally don't know of any OS or
run-time library that has support for non-contiguous blocks.  Hardware
like the 386 can map non-contiguous memory segments such that that appear
to be contiguous to the application program, but then, if they appear
contiguous, then support for non-contiguous becomes superfluous.  
Anyway, 386 memory management is way beyond the scope of the original thread.

I looked at the man pages for malloc on my Sun, and a realloc() "...returns
a pointer to the (possibly moved) block." Which would imply that even a
realloc'd block is contiguous.  

malloc() "...returns a pointer to a block of at least size bytes."  Again,
implying that a contiguous block has been allocated.


Kaleb Keithley

spelling and grammar flames > /dev/null



Sat, 17 Oct 1992 00:00:37 GMT  
 malloc/free question
Anyone who tries to teach C without being familiar with K&R is an
incompetent.

The last chapter (of the first edition, at least; my 2nd edition is
at home) has a sample malloc/free implementation.
        /r$
--

Use a domain-based address or give alternate paths, or you may lose out.



Sat, 17 Oct 1992 01:35:08 GMT  
 malloc/free question
<In a recent C programming class, an intresting question was posed to the
<"teacher".  How does the free function "know" how much memory to de-allocate
<after malloc has reserved it ?

In the original K&R, there was presented an example of to write malloc/free.



Sat, 17 Oct 1992 02:50:27 GMT  
 malloc/free question
<
<In a recent C programming class, an intresting question was posed to the
<"teacher".  How does the free function "know" how much memory to de-allocate
<after malloc has reserved it ?
<
< [ example deleted ]
<
<
<The "teacher" does not know hoe free "remembers" how much to de-allocate.

This means that your teacher hasn't read K&R (1 or 2), at least not
up to the end of the last chapter, because there he would have found
the answer (more or less what you described in your article).

Of course, there may have been many other ways to do this.
Basically, you must associate an adress with a number, and just
to give one other approach, `malloc' could internally maintain some
array which contains adresses and the number of bytes allocated
there. If this implementation doesn't want to pose any arbitrary
limitation or extreme overhead, this array too must be maintained
in dynamically allocated memory.

So a program should never depend on some useful information to be
found at an adress just *below* a pointer returned from malloc (to
query the size *could* be useful sometimes and it's a pitty that a
portable program must duplicated this information, if it is ever
needed.)
--



Fri, 16 Oct 1992 21:54:53 GMT  
 
 [ 25 post ]  Go to page: [1] [2]

 Relevant Pages 

1. malloc/free questions

2. malloc - free question

3. malloc/free question

4. basic malloc/free question

5. dumb malloc free question

6. malloc/free question with Purify

7. Bonehead malloc/free question

8. Intersting malloc() / free() question

9. malloc, realloc, free questions

10. Dumb question concerning malloc/free

11. a question about malloc and free

12. simple question about malloc & free

 

 
Powered by phpBB® Forum Software