Question regarding implementation details of malloc in K&R2

[somenath]

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

[James Kuyper]

somenath wrote:

On Dec 2, 5:53 pm, James Kuyper <[e-mail]:

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

[santosh]

somenath wrote:

On Dec 2, 5:53 pm, James Kuyper <[e-mail]:

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

[somenath]

On Dec 2, 6:30 pm, santosh <[e-mail]:

somenath wrote:

On Dec 2, 5:53 pm, James Kuyper <[e-mail]:

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 ?

[Mark McIntyre]

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.

[santosh]

somenath wrote:

On Dec 2, 6:30 pm, santosh <[e-mail]:

>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().

[CBFalconer]

Barry Schwarz wrote:

<so*********@gmail.comwrote:

>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

[Barry Schwarz]

On Sun, 2 Dec 2007 05:18:27 -0800 (PST), somenath
<so*********@gmail.comwrote:

>On Dec 2, 5:53 pm, James Kuyper <[e-mail]:

>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