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]

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.

 

[somenath]

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 ?

 

[James Kuyper]

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]

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]

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

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]

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

 

[Barry Schwarz]

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

 

[CBFalconer]

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.

 

[Barry Schwarz]

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