Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Question regarding implementation details of malloc in K&R2

Reply
Thread Tools

Question regarding implementation details of malloc in K&R2

 
 
somenath
Guest
Posts: n/a
 
      12-02-2007
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
 
Reply With Quote
 
 
 
 
James Kuyper
Guest
Posts: n/a
 
      12-02-2007
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.
 
Reply With Quote
 
 
 
 
somenath
Guest
Posts: n/a
 
      12-02-2007
On Dec 2, 5:53 pm, James Kuyper <(E-Mail Removed)> 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.-

 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      12-02-2007
somenath wrote:
> On Dec 2, 5:53 pm, James Kuyper <(E-Mail Removed)> 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.
 
Reply With Quote
 
santosh
Guest
Posts: n/a
 
      12-02-2007
somenath wrote:

> On Dec 2, 5:53 pm, James Kuyper <(E-Mail Removed)> 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.

 
Reply With Quote
 
somenath
Guest
Posts: n/a
 
      12-02-2007
On Dec 2, 6:30 pm, santosh <(E-Mail Removed)> wrote:
> somenath wrote:
> > On Dec 2, 5:53 pm, James Kuyper <(E-Mail Removed)> 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 ?

 
Reply With Quote
 
Mark McIntyre
Guest
Posts: n/a
 
      12-02-2007
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.
 
Reply With Quote
 
santosh
Guest
Posts: n/a
 
      12-02-2007
somenath wrote:

> On Dec 2, 6:30 pm, santosh <(E-Mail Removed)> 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().

 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      12-05-2007
On Sat, 1 Dec 2007 20:37:12 -0800 (PST), somenath
<(E-Mail Removed)> 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
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      12-05-2007
Barry Schwarz wrote:
> <(E-Mail Removed)> 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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
(FAQ details:) malloc(), void * and casts =?utf-8?b?QXNiasO4cm4gU8OmYsO4?= C Programming 37 11-20-2007 11:00 PM
Show Details/Hide Details link button =?Utf-8?B?Sm9l?= ASP .Net 1 03-13-2006 04:51 PM
free'ing malloc'd structure with malloc'd members John C Programming 13 08-02-2004 11:45 AM
Re: free'ing malloc'd structure with malloc'd members ravi C Programming 0 07-30-2004 12:42 PM
Warning "Re: Your details" & "Re: My details" Joe Lee Computer Support 3 05-17-2004 05:08 PM



Advertisments