Question regarding implementation details of malloc in K&R2

Discussion in 'C Programming' started by somenath, Dec 2, 2007.

  1. somenath

    somenath Guest

    Hi All ,

    As a process of my C language learning I was trying to learn how
    malloc can be implemented from K&R2 .But I am not able to
    understand few points . It would be very much helpful if some body
    give some inputs in the bellow mentioned points.

    Point 1) I page 186 it is said that "In malloc, the requested size in
    characters is rounded up to the proper number of header-sized
    units; the block that will be allocated contains one more unit, for
    the header itself, and this is the value recorded in the size field of
    the header."
    My understanding is it is achieved by the following code segment

    nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;

    but I am not getting how it is done ? Suppose user has requested for 4
    bypes so "nbytes" will be = 5
    now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/
    = 16/12 + 1
    = 1+ 1 = 2
    So my doubt is how 2 will help to get 5 bytes ?

    Point 2 ) Why "return (void *)(p+1);" is used why p is not returned ?
    My understanding is p contains the starting address of the
    requested size so we should return (void *) p .

    Point 3 ) In "morecore" function "free((void *)(up+1));" is used to
    add up in the free list . My question is why we are not adding "up"
    instead of "up+1" ?

    Point 4)in the "free" function "bp = (Header *)ap - 1; /* point to
    block header */
    Is used to point to the header . Why ap is not used ?

    I am really confused . Please some body help me to understand the
    logic behind this implementation .

    Regards,
    Somenath
     
    somenath, Dec 2, 2007
    #1
    1. Advertising

  2. somenath

    James Kuyper Guest

    somenath wrote:
    > Hi All ,
    >
    > As a process of my C language learning I was trying to learn how
    > malloc can be implemented from K&R2 .But I am not able to
    > understand few points . It would be very much helpful if some body
    > give some inputs in the bellow mentioned points.
    >
    > Point 1) I page 186 it is said that "In malloc, the requested size in
    > characters is rounded up to the proper number of header-sized
    > units; the block that will be allocated contains one more unit, for
    > the header itself, and this is the value recorded in the size field of
    > the header."
    > My understanding is it is achieved by the following code segment
    >
    > nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
    >
    > but I am not getting how it is done ? Suppose user has requested for 4
    > bypes so "nbytes" will be = 5
    > now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/
    > = 16/12 + 1
    > = 1+ 1 = 2
    > So my doubt is how 2 will help to get 5 bytes ?


    Because numnits is the number of 12-byte header units allocated. That's
    enough for one 12-byte header and one 5-byte allocation, with 7 bytes
    left over.

    > Point 2 ) Why "return (void *)(p+1);" is used why p is not returned ?
    > My understanding is p contains the starting address of the
    > requested size so we should return (void *) p .


    The pointer p points at memory which contains two parts. The first 12
    bytes are a header which is used to keep track of this allocation, and
    is used only by the malloc() family of functions; it should never be
    changed by the user. The part starting at the 13th byte is the memory
    that has actually been set aside for the user.

    > Point 3 ) In "morecore" function "free((void *)(up+1));" is used to
    > add up in the free list . My question is why we are not adding "up"
    > instead of "up+1" ?


    Because free() requires a pointer to the memory that was set aside for
    the user. That memory starts at up+1. free() itself will subtract 1
    again, in order to get a pointer to the header associated with that memory.

    > Point 4)in the "free" function "bp = (Header *)ap - 1; /* point to
    > block header */
    > Is used to point to the header . Why ap is not used ?


    Because ap points at the memory allocated for the user. bp points at the
    header.
     
    James Kuyper, Dec 2, 2007
    #2
    1. Advertising

  3. somenath

    somenath Guest

    Re: Question regarding implementation details of malloc in K&R2

    On Dec 2, 5:53 pm, James Kuyper <> wrote:
    > somenath wrote:
    > > Hi All ,

    >
    > > As a process of my C language learning I was trying to learn how
    > > malloc can be implemented from K&R2 .But I am not able to
    > > understand few points . It would be very much helpful if some body
    > > give some inputs in the bellow mentioned points.

    >
    > > Point 1) I page 186 it is said that "In malloc, the requested size in
    > > characters is rounded up to the proper number of header-sized
    > > units; the block that will be allocated contains one more unit, for
    > > the header itself, and this is the value recorded in the size field of
    > > the header."
    > > My understanding is it is achieved by the following code segment

    >
    > > nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;

    >
    > > but I am not getting how it is done ? Suppose user has requested for 4
    > > bypes so "nbytes" will be = 5
    > > now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/
    > > = 16/12 + 1
    > > = 1+ 1 = 2
    > > So my doubt is how 2 will help to get 5 bytes ?

    >
    > Because numnits is the number of 12-byte header units allocated. That's
    > enough for one 12-byte header and one 5-byte allocation, with 7 bytes
    > left over.


    Thanks for your answer. I would like to verify my understanding.
    According to the above explanation suppose user wants to allocate 5
    bytes ,malloc basically allocating more than 5 bytes . Here it is 7
    bytes which is for the user to be used . Is the behavior expected ?


    > > Point 2 ) Why "return (void *)(p+1);" is used why p is not returned ?
    > > My understanding is p contains the starting address of the
    > > requested size so we should return (void *) p .

    >
    > The pointer p points at memory which contains two parts. The first 12
    > bytes are a header which is used to keep track of this allocation, and
    > is used only by the malloc() family of functions; it should never be
    > changed by the user. The part starting at the 13th byte is the memory
    > that has actually been set aside for the user.
    >
    > > Point 3 ) In "morecore" function "free((void *)(up+1));" is used to
    > > add up in the free list . My question is why we are not adding "up"
    > > instead of "up+1" ?

    >
    > Because free() requires a pointer to the memory that was set aside for
    > the user. That memory starts at up+1. free() itself will subtract 1
    > again, in order to get a pointer to the header associated with that memory.
    >
    > > Point 4)in the "free" function "bp = (Header *)ap - 1; /* point to
    > > block header */
    > > Is used to point to the header . Why ap is not used ?

    >
    > Because ap points at the memory allocated for the user. bp points at the
    > header.-
     
    somenath, Dec 2, 2007
    #3
  4. somenath

    James Kuyper Guest

    Re: Question regarding implementation details of malloc in K&R2

    somenath wrote:
    > On Dec 2, 5:53 pm, James Kuyper <> wrote:
    >> somenath wrote:
    >>> Hi All ,
    >>> As a process of my C language learning I was trying to learn how
    >>> malloc can be implemented from K&R2 .But I am not able to
    >>> understand few points . It would be very much helpful if some body
    >>> give some inputs in the bellow mentioned points.
    >>> Point 1) I page 186 it is said that "In malloc, the requested size in
    >>> characters is rounded up to the proper number of header-sized
    >>> units; the block that will be allocated contains one more unit, for
    >>> the header itself, and this is the value recorded in the size field of
    >>> the header."
    >>> My understanding is it is achieved by the following code segment
    >>> nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
    >>> but I am not getting how it is done ? Suppose user has requested for 4
    >>> bypes so "nbytes" will be = 5
    >>> now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/
    >>> = 16/12 + 1
    >>> = 1+ 1 = 2
    >>> So my doubt is how 2 will help to get 5 bytes ?

    >> Because numnits is the number of 12-byte header units allocated. That's
    >> enough for one 12-byte header and one 5-byte allocation, with 7 bytes
    >> left over.

    >
    > Thanks for your answer. I would like to verify my understanding.
    > According to the above explanation suppose user wants to allocate 5
    > bytes ,malloc basically allocating more than 5 bytes . Here it is 7
    > bytes which is for the user to be used . Is the behavior expected ?


    Yes. The example code allocates memory in blocks of 12 bytes. On some
    systems, a minimum block size is needed to ensure that the memory
    returned by malloc() has proper alignment. On other systems, it's merely
    a convenience. However, it is a significant convenience even on those
    machines, as you'll find out if you try re-designing the K&R example
    code to return exact-sized allocations.
     
    James Kuyper, Dec 2, 2007
    #4
  5. somenath

    santosh Guest

    Re: Question regarding implementation details of malloc in K&R2

    somenath wrote:

    > On Dec 2, 5:53 pm, James Kuyper <> wrote:
    >> somenath wrote:
    >> > Hi All ,

    >>
    >> > As a process of my C language learning I was trying to learn how
    >> > malloc can be implemented from K&R2 .But I am not able to
    >> > understand few points . It would be very much helpful if some body
    >> > give some inputs in the bellow mentioned points.

    >>
    >> > Point 1) I page 186 it is said that "In malloc, the requested size
    >> > in characters is rounded up to the proper number of header-sized
    >> > units; the block that will be allocated contains one more unit, for
    >> > the header itself, and this is the value recorded in the size field
    >> > of the header."
    >> > My understanding is it is achieved by the following code segment

    >>
    >> > nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;

    >>
    >> > but I am not getting how it is done ? Suppose user has requested
    >> > for 4 bypes so "nbytes" will be = 5
    >> > now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/
    >> > = 16/12 + 1
    >> > = 1+ 1 = 2
    >> > So my doubt is how 2 will help to get 5 bytes ?

    >>
    >> Because numnits is the number of 12-byte header units allocated.
    >> That's enough for one 12-byte header and one 5-byte allocation, with
    >> 7 bytes left over.

    >
    > Thanks for your answer. I would like to verify my understanding.
    > According to the above explanation suppose user wants to allocate 5
    > bytes ,malloc basically allocating more than 5 bytes . Here it is 7
    > bytes which is for the user to be used . Is the behavior expected ?


    <snip>

    The behaviour is expected but the caller is still allowed to actually
    use only the amount of bytes he requested the system for.
     
    santosh, Dec 2, 2007
    #5
  6. somenath

    somenath Guest

    Re: Question regarding implementation details of malloc in K&R2

    On Dec 2, 6:30 pm, santosh <> wrote:
    > somenath wrote:
    > > On Dec 2, 5:53 pm, James Kuyper <> wrote:
    > >> somenath wrote:
    > >> > Hi All ,

    >
    > >> > As a process of my C language learning I was trying to learn how
    > >> > malloc can be implemented from K&R2 .But I am not able to
    > >> > understand few points . It would be very much helpful if some body
    > >> > give some inputs in the bellow mentioned points.

    >
    > >> > Point 1) I page 186 it is said that "In malloc, the requested size
    > >> > in characters is rounded up to the proper number of header-sized
    > >> > units; the block that will be allocated contains one more unit, for
    > >> > the header itself, and this is the value recorded in the size field
    > >> > of the header."
    > >> > My understanding is it is achieved by the following code segment

    >
    > >> > nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;

    >
    > >> > but I am not getting how it is done ? Suppose user has requested
    > >> > for 4 bypes so "nbytes" will be = 5
    > >> > now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/
    > >> > = 16/12 + 1
    > >> > = 1+ 1 = 2
    > >> > So my doubt is how 2 will help to get 5 bytes ?

    >
    > >> Because numnits is the number of 12-byte header units allocated.
    > >> That's enough for one 12-byte header and one 5-byte allocation, with
    > >> 7 bytes left over.

    >
    > > Thanks for your answer. I would like to verify my understanding.
    > > According to the above explanation suppose user wants to allocate 5
    > > bytes ,malloc basically allocating more than 5 bytes . Here it is 7
    > > bytes which is for the user to be used . Is the behavior expected ?

    >
    > <snip>
    >
    > The behaviour is expected but the caller is still allowed to actually
    > use only the amount of bytes he requested the system for.- Hide quoted text -
    >


    Is this because user does not aware of how many bytes malloc has
    reserved extra ?
     
    somenath, Dec 2, 2007
    #6
  7. somenath wrote:
    > Hi All ,
    >
    > Point 1) I page 186 it is said that "In malloc, the requested size in
    > characters is rounded up to the proper number of header-sized
    > units; the block that will be allocated contains one more unit, for
    > the header itself, and this is the value recorded in the size field of
    > the header."
    > My understanding is it is achieved by the following code segment
    >
    > nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
    >
    > but I am not getting how it is done ? Suppose user has requested for 4
    > bypes so "nbytes" will be = 5
    > now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/
    > = 16/12 + 1
    > = 1+ 1 = 2
    > So my doubt is how 2 will help to get 5 bytes ?


    thats two units. How large is a unit?

    > Point 2 ) Why "return (void *)(p+1);" is used why p is not returned ?
    > My understanding is p contains the starting address of the
    > requested size so we should return (void *) p .


    I don't have the full code in front of me, but I suspect you're
    misreading it. p will be pointing to the start of the header, not the
    start of the data block.

    > Point 3 ) In "morecore" function "free((void *)(up+1));" is used to
    > add up in the free list . My question is why we are not adding "up"
    > instead of "up+1" ?


    Same answer as above.

    > Point 4)in the "free" function "bp = (Header *)ap - 1; /* point to
    > block header */
    > Is used to point to the header . Why ap is not used ?


    and again.
     
    Mark McIntyre, Dec 2, 2007
    #7
  8. somenath

    santosh Guest

    Re: Question regarding implementation details of malloc in K&R2

    somenath wrote:

    > On Dec 2, 6:30 pm, santosh <> wrote:
    >> somenath wrote:


    <snip>

    >> > Thanks for your answer. I would like to verify my understanding.
    >> > According to the above explanation suppose user wants to allocate 5
    >> > bytes ,malloc basically allocating more than 5 bytes . Here it is
    >> > 7 bytes which is for the user to be used . Is the behavior expected
    >> > ?

    >>
    >> <snip>
    >>
    >> The behaviour is expected but the caller is still allowed to actually
    >> use only the amount of bytes he requested the system for.- Hide
    >> quoted text -
    >>

    > Is this because user does not aware of how many bytes malloc has
    > reserved extra ?


    That's one possibility. But even if the user is aware of the extra
    storage, depending on it makes the code unportable to other
    implementations of malloc().
     
    santosh, Dec 2, 2007
    #8
  9. On Sat, 1 Dec 2007 20:37:12 -0800 (PST), somenath
    <> wrote:

    >Hi All ,
    >
    >As a process of my C language learning I was trying to learn how
    >malloc can be implemented from K&R2 .But I am not able to
    >understand few points . It would be very much helpful if some body
    >give some inputs in the bellow mentioned points.


    Remember that everything describe in that section of the book (and in
    this message) relates to their sample malloc, not to the library
    function of the same name.

    >
    >Point 1) I page 186 it is said that "In malloc, the requested size in
    >characters is rounded up to the proper number of header-sized
    >units; the block that will be allocated contains one more unit, for
    >the header itself, and this is the value recorded in the size field of
    >the header."
    >My understanding is it is achieved by the following code segment
    >
    >nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;
    >
    >but I am not getting how it is done ? Suppose user has requested for 4
    >bypes so "nbytes" will be = 5


    nbytes is 4. The phrase "contains one more unit" refers to the final
    size in header-sized units, not to the requested size in bytes. It
    doesn't change the following arithmetic.

    >now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/


    sizeof(Header) is 12 bytes. Memory will be allocated in units of 12.
    How many units does it take to provide the requested four bytes?
    Obviously one. Add one more unit for control and the request consumes
    two units.

    Once we overlook the missing parentheses, you correctly calculate this

    > = 16/12 + 1
    > = 1+ 1 = 2
    >So my doubt is how 2 will help to get 5 bytes ?


    Two header-sized units is 24 bytes. The first unit is used by the
    malloc for control. The second unit of 12 bytes provides the FOUR
    bytes requested (and eight left over).

    >
    >Point 2 ) Why "return (void *)(p+1);" is used why p is not returned ?
    > My understanding is p contains the starting address of the
    >requested size so we should return (void *) p .


    p points to the first header-sized unit. That is not available to the
    calling function. It is used by malloc for control. The first byte
    available to the user is at p+1.

    >
    >Point 3 ) In "morecore" function "free((void *)(up+1));" is used to
    >add up in the free list . My question is why we are not adding "up"
    >instead of "up+1" ?


    Because they are talking about their sample free function on page 188.
    In that function, the subtract 1 from the argument to get back to the
    control Header.

    >
    >Point 4)in the "free" function "bp = (Header *)ap - 1; /* point to
    >block header */
    >Is used to point to the header . Why ap is not used ?


    The user only sees the address returned by malloc which is actually
    sizeof(Header) bytes beyond the start of the area. The user has no
    idea how big Header is (abstract data type?). The user cannot
    subtract the correct quantity to get to the true starting address.
    Therefore, the user passes in the address he knows about and free
    backtracks to get to the start of the control Header.

    >
    >I am really confused . Please some body help me to understand the
    >logic behind this implementation .


    Take a piece of paper, mark off addresses, and "play computer" with a
    pencil.


    Remove del for email
     
    Barry Schwarz, Dec 5, 2007
    #9
  10. somenath

    CBFalconer Guest

    Barry Schwarz wrote:
    > <> wrote:
    >
    >> As a process of my C language learning I was trying to learn how
    >> malloc can be implemented from K&R2 .But I am not able to
    >> understand few points . It would be very much helpful if some body
    >> give some inputs in the bellow mentioned points.

    >
    > Remember that everything describe in that section of the book (and
    > in this message) relates to their sample malloc, not to the library
    > function of the same name.
    >

    .... snip useful discussion of K&R sample malloc ...
    >
    > Take a piece of paper, mark off addresses, and "play computer" with
    > a pencil.


    Another system you can look at is nmalloc for DJGPP. This is a
    real malloc package, with very few non-standard demands on the
    system, and includes testing mechanisms (using a supplied chunk of
    memory from main) and debug and tracing systems. It requires gcc
    for compilation, because of the variadic debug macros. It is
    available at:

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

    In particular, the testing mechanism eliminates the system source
    of memory, i.e. the sbrk system function. Also, the whole system
    is built around the definition of "struct memblock".

    What nmalloc supplies is well structured code, and all operations
    are O(1). Thus it will never cause long delays in operation.

    --
    Chuck F (cbfalconer at maineline dot net)
    <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Dec 5, 2007
    #10
  11. Re: Question regarding implementation details of malloc in K&R2

    On Sun, 2 Dec 2007 05:18:27 -0800 (PST), somenath
    <> wrote:

    >On Dec 2, 5:53 pm, James Kuyper <> wrote:
    >> somenath wrote:
    >> > Hi All ,

    >>
    >> > As a process of my C language learning I was trying to learn how
    >> > malloc can be implemented from K&R2 .But I am not able to
    >> > understand few points . It would be very much helpful if some body
    >> > give some inputs in the bellow mentioned points.

    >>
    >> > Point 1) I page 186 it is said that "In malloc, the requested size in
    >> > characters is rounded up to the proper number of header-sized
    >> > units; the block that will be allocated contains one more unit, for
    >> > the header itself, and this is the value recorded in the size field of
    >> > the header."
    >> > My understanding is it is achieved by the following code segment

    >>
    >> > nunits = (nbytes+sizeof(Header)-1)/sizeof(header) + 1;

    >>
    >> > but I am not getting how it is done ? Suppose user has requested for 4
    >> > bypes so "nbytes" will be = 5
    >> > now nunits = 5 + 12 -1 /12 + 1 /*Assume that sizeof(Header) = 12*/
    >> > = 16/12 + 1
    >> > = 1+ 1 = 2
    >> > So my doubt is how 2 will help to get 5 bytes ?

    >>
    >> Because numnits is the number of 12-byte header units allocated. That's
    >> enough for one 12-byte header and one 5-byte allocation, with 7 bytes
    >> left over.

    >
    >Thanks for your answer. I would like to verify my understanding.
    >According to the above explanation suppose user wants to allocate 5
    >bytes ,malloc basically allocating more than 5 bytes . Here it is 7
    >bytes which is for the user to be used . Is the behavior expected ?


    The use is only requesting four bytes. This sample version of malloc
    is allocating two contiguous Header units, 24 bytes. The first 12
    bytes are for the malloc and free functions to use and the user is not
    told about them. The second 12 bytes is the four the user requested
    plus 8 more (since this malloc actually allocates Header units) which
    the user is also not told about. This is the expected behavior for
    this sample malloc only. No one is claiming that the "real" malloc in
    any standard library actually works this way.



    Remove del for email
     
    Barry Schwarz, Dec 6, 2007
    #11
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?Sm9l?=

    Show Details/Hide Details link button

    =?Utf-8?B?Sm9l?=, Mar 13, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    911
    dkode
    Mar 13, 2006
  2. =?utf-8?b?QXNiasO4cm4gU8OmYsO4?=

    (FAQ details:) malloc(), void * and casts

    =?utf-8?b?QXNiasO4cm4gU8OmYsO4?=, Nov 13, 2007, in forum: C Programming
    Replies:
    37
    Views:
    1,035
    Lorenzo Villari
    Nov 20, 2007
  3. somenath

    Question regarding malloc casing

    somenath, Dec 2, 2007, in forum: C Programming
    Replies:
    10
    Views:
    508
    Joe Wright
    Dec 3, 2007
  4. Stephan Beal

    Question regarding safety of a malloc()

    Stephan Beal, Dec 24, 2008, in forum: C Programming
    Replies:
    17
    Views:
    530
  5. Andrew Shepson

    Question regarding safety of a malloc()

    Andrew Shepson, Jun 2, 2010, in forum: C Programming
    Replies:
    6
    Views:
    281
    Nick Keighley
    Jun 3, 2010
Loading...

Share This Page