where do the extra bytes go while using Malloc ? - Embedded

This is a discussion on where do the extra bytes go while using Malloc ? - Embedded ; 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 ...

+ Reply to Thread
Results 1 to 10 of 10

Thread: where do the extra bytes go while using Malloc ?

  1. 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


  2. Re: where do the extra bytes go while using Malloc ?

    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.

  3. Re: where do the extra bytes go while using Malloc ?

    [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
    Email: -http://www. +rjh@
    Google users:
    "Usenet is a strange place" - dmr 29 July 1999

  4. Re: where do the extra bytes go while using Malloc ?

    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=f...+details%3A%22



    Regards,
    --
    Filip Larsen

  5. Re: where do the extra bytes go while using Malloc ?

    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?



  6. Re: where do the extra bytes go while using Malloc ?

    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.

  7. Re: where do the extra bytes go while using Malloc ?

    On Oct 23, 12:41 am, karthikbalaguru
    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...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.



  8. Re: where do the extra bytes go while using Malloc ?

    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:



    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.




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


  9. Re: where do the extra bytes go while using Malloc ?


    "karthikbalaguru" 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



  10. Re: where do the extra bytes go while using Malloc ?

    On Oct 24, 3:50 am, "Malcolm McLean" wrote:
    > "karthikbalaguru" 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


+ Reply to Thread