where do the extra bytes go while using Malloc ?

Discussion in 'C Programming' started by karthikbalaguru, Oct 23, 2007.

  1. 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
    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, Oct 23, 2007
    1. Advertisements

  2. karthikbalaguru

    Ian Collins Guest

    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.
    You can't get something (functionality) for nothing.
    That's up to the implementation.
    Ian Collins, Oct 23, 2007
    1. Advertisements

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

    karthikbalaguru said:
    Not necessarily. It might need only 1, or it may need a dozen or a
    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).
    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
    There can be, yes.
    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.
    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, Oct 23, 2007
  4. karthikbalaguru

    Filip Larsen Guest

    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.


    Filip Larsen, Oct 23, 2007
  5. [/QUOTE]
    And why would you need to keep the allocated memory in a linked list
    at all? If you were using such a list, it would be of free memory, in
    which case the allocatable memory itself could be used for the link.
    So (granting the other assumptions) there would not be an 8 byte
    overhead but a 4-byte overhead with an 8-byte minimum.

    What's more, if you only allocate in certain sizes you can keep
    separate lists for each size, which makes finding a suitable size
    block easy, and removes the need for storing the size in free blocks.
    And there are ways to avoid storing the size at all, by allocating
    different size blocks from different areas of memory.

    -- Richard
    Richard Tobin, Oct 23, 2007
  6. karthikbalaguru

    Mark Bluemel Guest

    There doesn't have to be a heap. The overheads don't have to be as you
    Why? 1) If I have the size, I can (perhaps) find the next block of
    memory, 2) sizes (and pointers) may not necessarily be 4 bytes long.
    As Richard H has said, putting this more generally, there must be some
    overhead involved in managing malloc()ed memory.

    The nature and size of the overhead is dependent on the implementation.
    It doesn't have to be a linked list - other data structures are
    available and may be applicable.
    It doesn't allocate the exact size of data requested. It allocates "at
    least enough" to satisfy the request, taking into account its management
    overheads and the contract it has to provide memory aligned
    appropriately for any data type.

    Where the implementers put them. There is no guaranteed general answer
    to the question - you'd need to examine a specific malloc implementation.

    If you wish to discuss a specific implementation, I suggest doing it
    somewhere other than "comp.lang.c"
    If you mean "thanks in advance" why not write that?
    Mark Bluemel, Oct 23, 2007
  7. karthikbalaguru

    santosh Guest

    This is just one possible scenario under one possible implementation.
    Pointer sizes can vary, as can the accounting data used by malloc.
    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.
    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.
    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.
    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?
    santosh, Oct 23, 2007
  8. 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.
    James Kuyper Jr., Oct 23, 2007
  9. karthikbalaguru

    user923005 Guest

    Not on a 16 bit machine or 64 bit machine.
    Unless it is 8 bytes + 8 bytes or 2 bytes + 2 bytes or something else.
    You are considering some particular implementation. Your actual
    allocator may or may not work like that.
    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.

    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.
    user923005, Oct 23, 2007
  10. karthikbalaguru

    santosh Guest

    glen herrmannsfeldt wrote:

    Because it's trivially easy to do this in the program, if wanted?
    santosh, Oct 23, 2007
  11. The way malloc() works, keeping track of the length of the allocated
    block, requires at least that the length be stored somewhere.

    The allocator used by OS/360, called GETMAIN/FREEMAIN, works a little
    differently. There is no overhead in the allocated memory.
    The length and starting address are specified for FREEMAIN.
    One can free part of an allocated region, even as a hole in the
    middle of a previously allocated region. The result is that the
    free memory contains a linked list, but the allocated memory has
    no overhead. (I believe allocations must be in multiples of
    eight bytes, though, if no other reason than to guarantee alignment.)

    I do wonder, though, why C supplies no routine to determine the length
    of an allocated block.

    -- glen
    glen herrmannsfeldt, Oct 23, 2007
  12. karthikbalaguru

    CBFalconer Guest

    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

    CBFalconer, Oct 23, 2007
  13. 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

    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.
    Malcolm McLean, Oct 23, 2007
  14. Should you return the length allocated or the length asked for? If the
    second you need an extra field, if the first you need to educate programmers
    not to use the function as a lazy array length.
    Malcolm McLean, Oct 23, 2007
  15. karthikbalaguru

    Mark Bluemel Guest

    British readers of the newsgroup might identify with me on this thread.

    I can imagine Mark Benton in his bank manager persona explaining that
    the extra bytes are saved up for the Directors' christmas party... Quite
    what the Directors do with the bytes, I haven't worked out.
    Mark Bluemel, Oct 24, 2007
  16. Thx to all of you for the info :):)

    Karthik Balaguru
    karthikbalaguru, Oct 24, 2007
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.