where do the extra bytes go while using Malloc ?

Hi,
In the case of heap , to keep track of a single chunk of memory it
requires 8 bytes of information.
That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
pointer to the next block of memory.  So, For every additional chunk,
even if it is only one byte long, these 8 bytes are required again, in
addition to the 1 byte actually needed to store the chunk itself.

So, there should be wastage of memory for managing the linked list
(heap).
But, How does malloc/calloc then allocate the exact size of data as
there must be some wastage of memory that has to be taken into account
while allocating in heap memory (Memory consumed for managing the
information in terms of linked list) ?

That is, Malloc should consume more space to allocate the desired
amount of data . where do the extra bytes go ?

Thx in advans,
Karthik Balaguru

karthikbalaguru wrote:
> Hi,
> In the case of heap , to keep track of a single chunk of memory it
> requires 8 bytes of information.
> That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
> pointer to the next block of memory.  So, For every additional chunk,
> even if it is only one byte long, these 8 bytes are required again, in
> addition to the 1 byte actually needed to store the chunk itself.
> 
That might be one implementation, the working of malloc are not covered
by the standard.  Don't forget the value returned by malloc is correctly
aligned for any type.

> So, there should be wastage of memory for managing the linked list
> (heap).
> But, How does malloc/calloc then allocate the exact size of data as
> there must be some wastage of memory that has to be taken into account
> while allocating in heap memory (Memory consumed for managing the
> information in terms of linked list) ?
> 
You can't get something (functionality) for nothing.

> That is, Malloc should consume more space to allocate the desired
> amount of data . where do the extra bytes go ?
> 
That's up to the implementation.

-- 
Ian Collins.

[This reply written in comp.lang.c, and followups set to that group.]

karthikbalaguru said:

> Hi,
> In the case of heap , to keep track of a single chunk of memory it
> requires 8 bytes of information.

Not necessarily. It might need only 1, or it may need a dozen or a 
thousand.

> That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
> pointer to the next block of memory.

C doesn't require that 4 bytes are used for pointers. On some systems, 2 
suffice. On others, 8 are needed. Indeed, 1-byte pointers are feasible 
(think 32-bits-per-byte DSPs, for example).

> So, For every additional chunk,
> even if it is only one byte long, these 8 bytes are required again, in
> addition to the 1 byte actually needed to store the chunk itself.

Well, to be more general, yes, it is likely that the memory management 
subsystem will incur a per-call overhead (although C does not mandate 
this).

> So, there should be wastage of memory for managing the linked list
> (heap).

There can be, yes.

> But, How does malloc/calloc then allocate the exact size of data

The C Standard requires that malloc etc return NULL if they fail, or a 
pointer to the requested amount of memory if they succeed. Thus, those 
functions must allocate *at least* the amount of memory requested (or 
return NULL). But the Standard doesn't forbid them from allocating more, 
and indeed they might do so. Or they might not, of course.

> as
> there must be some wastage of memory that has to be taken into account
> while allocating in heap memory (Memory consumed for managing the
> information in terms of linked list) ?
> 
> That is, Malloc should consume more space to allocate the desired
> amount of data . where do the extra bytes go ?

You mean, where is the management info stored? Well, it depends on the 
implementation. Several possible solutions exist. If you really need to 
know, C can't tell you - but your implementation's documentation might be 
able to.

-- 
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

karthikbalaguru wrote:

> How does malloc/calloc then allocate the exact size of data as
> there must be some wastage of memory that has to be taken into account
> while allocating in heap memory (Memory consumed for managing the
> information in terms of linked list) ?


While this in principle is an implementation issue it is to my knowledge 
fairly common to place (some of) this management data for each malloc 
block just in front of the block. Or it was, at least, on the systems I 
was using 10-20 years ago.

For example, if you look at the code for malloc in one of the latest 
glibc releases it says:

"Minimum overhead per allocated chunk: 4 or 8 bytes. Each malloced chunk 
has a hidden word of overhead holding size and status information."

The more detailed description in the code [1] seem to indicate that the 
management bytes are placed both in front and at the end of the 
application data block.

[1] 
http://www.google.com/codesearch?q=file%3Aglibc-2.5%2Fmalloc%2Fmalloc.c+%22malloc_chunk+details%3A%22



Regards,
-- 
Filip Larsen

karthikbalaguru wrote:

> Hi,
> In the case of heap , to keep track of a single chunk of memory it
> requires 8 bytes of information.
> That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
> pointer to the next block of memory.

This is just one possible scenario under one possible implementation.
Pointer sizes can vary, as can the accounting data used by malloc.

> So, For every additional chunk, 
> even if it is only one byte long, these 8 bytes are required again, in
> addition to the 1 byte actually needed to store the chunk itself.

In your scenario eight bytes are needed just to record the minimal
necessary book-keeping information. In most "real world" malloc
implementations rather more space would be set aside.

> So, there should be wastage of memory for managing the linked list
> (heap). 

Not necessarily. If the malloc implementation can embed all necessary
information into the pointer itself. The point is, numerous schemes are
possible and there are many factors responsible for the choice made.

> But, How does malloc/calloc then allocate the exact size of data as
> there must be some wastage of memory that has to be taken into account
> while allocating in heap memory (Memory consumed for managing the
> information in terms of linked list) ?

Why should the book-keeping overhead prevent malloc from allocating the
exact amount of data requested? Indeed, though it might allocate more
than what was asked, if it could not allocate at least as much as was
requested, then the implementation is broken.

> That is, Malloc should consume more space to allocate the desired
> amount of data . where do the extra bytes go ?

This _really_ depends on the implementation. It could be anywhere from
being embedded in the pointer itself, behind the allocated block, after
the allocated block, elsewhere in memory, on a file on disk, on a
remote server on a network... you get the idea?

karthikbalaguru wrote:
> Hi,
> In the case of heap , to keep track of a single chunk of memory it
> requires 8 bytes of information.
> That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
> pointer to the next block of memory.  So, For every additional chunk,
> even if it is only one byte long, these 8 bytes are required again, in
> addition to the 1 byte actually needed to store the chunk itself.

As many people have pointed out, the amount of space that is needed can 
differ from one implementation to another, and the way in which that 
information is stored can also be implementation-dependent. You 
shouldn't write code that depends upon such details.

However, I've often found that it's useful when thinking about a 
function, to have a particular implementation in mind. Without a 
specific implementation in mind, it's easy for a newbie to get lost. 
Just keep in mind that any particular implementation might be quite 
different from the one you're thinking of. Here's a couple of models 
that you can use for that purpose:

One approach: when malloc(n) is called, memory for at least n+x bytes is 
actually allocated, for some value of 'x'. The first x bytes of the 
allocated space is used to store the control information you're talking 
about; the value returned by malloc() actually points at the first byte 
after the control information.

Second approach: all allocations are rounded up to the next power of 
two. malloc() maintains blocks of memory for each power of two currently 
in use, from which it allocates one piece at a time. When free() is 
called, it can figure out the rounded-up allocation size (it doesn't 
have any need to know the original requested allocation size), just by 
determining which of those blocks of memory is pointed at by the pointer 
being free()d.

On Oct 23, 12:41 am, karthikbalaguru <karthikbalagur...@gmail.com>
wrote:
> Hi,
> In the case of heap , to keep track of a single chunk of memory it
> requires 8 bytes of information.

Not on a 16 bit machine or 64 bit machine.

> That is, it requires 4 bytes to hold the size, and 4 bytes to hold the
> pointer to the next block of memory.  

Unless it is 8 bytes + 8 bytes or 2 bytes + 2 bytes or something else.

> So, For every additional chunk,
> even if it is only one byte long, these 8 bytes are required again, in
> addition to the 1 byte actually needed to store the chunk itself.
>
> So, there should be wastage of memory for managing the linked list
> (heap).
> But, How does malloc/calloc then allocate the exact size of data as
> there must be some wastage of memory that has to be taken into account
> while allocating in heap memory (Memory consumed for managing the
> information in terms of linked list) ?

You are considering some particular implementation.  Your actual
allocator may or may not work like that.

> That is, Malloc should consume more space to allocate the desired
> amount of data . where do the extra bytes go ?

When there is wasted space, it does not go anywhere.  It just gets
wasted.  If you are worried about it because of tight space
requirements, write your own sub-allocator.

Look:
https://www.archmemory.com/index.asp?PageAction=VIEWCATS&Category=44417
  1GB DDR2-800 ECC Module $94.99

Now calculate how much time you would spend trying to save a GB of RAM
by finagling little bits here and there.
That should tell you something important.

Filip Larsen wrote:
> karthikbalaguru wrote:
> 
>> How does malloc/calloc then allocate the exact size of data as
>> there must be some wastage of memory that has to be taken into
>> account while allocating in heap memory (Memory consumed for
>> managing the information in terms of linked list) ?
> 
> While this in principle is an implementation issue it is to my
> knowledge fairly common to place (some of) this management data
> for each malloc block just in front of the block. Or it was, at
> least, on the systems I was using 10-20 years ago.

You can examine the C code for a fairly portable malloc in
nmalloc.zip, written for DJGPP.  A malloc package cannot be
portable, since it depends on system knowledge.  However nmalloc is
pretty close to standard C, requires the system provide an sbrk()
function to supply memory, and compiles under gcc.  The gcc
requirement is due to a set of development macros, none of which
are in operation for the final package.  You can find nmalloc.zip
at:

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

-- 
 Chuck F (cbfalconer at maineline dot net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>



-- 
Posted via a free Usenet account from http://www.teranews.com

"karthikbalaguru" <karthikbalaguru79@gmail.com> wrote in message
> That is, Malloc should consume more space to allocate the desired
> amount of data . where do the extra bytes go ?
>
The trick is to store the control block just before the pointer you return. 
Then free() subtracts the block from the pointer passed to it, and has all 
the information it needs to make the memory avaialble for further 
allocations.

That's not the only way of doing it, and in fact most modern systems use a 
rather different method for small allocations, but it is how a simple 
malloc() works. If you check my website you will find a memory allocation 
package. It is one of the free sample chapters of Basic Algorithms.


-- 
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm
 

On Oct 24, 3:50 am, "Malcolm McLean" <regniz...@btinternet.com> wrote:
> "karthikbalaguru" <karthikbalagur...@gmail.com> wrote in message
> > That is, Malloc should consume more space to allocate the desired
> > amount of data . where do the extra bytes go ?
>
> The trick is to store the control block just before the pointer you return.
> Then free() subtracts the block from the pointer passed to it, and has all
> the information it needs to make the memory avaialble for further
> allocations.
>
> That's not the only way of doing it, and in fact most modern systems use a
> rather different method for small allocations, but it is how a simple
> malloc() works. If you check my website you will find a memory allocation
> package. It is one of the free sample chapters of Basic Algorithms.
>
> --
> Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm

Thx to all of you for the info :):)

Karthik Balaguru