473,717 Members | 2,051 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Question regarding implementation details of malloc in K&R2

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
Dec 2 '07 #1
7 2166
somenath wrote:
On Dec 2, 5:53 pm, James Kuyper <jameskuy...@ve rizon.netwrote:
>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.
Dec 2 '07 #2
somenath wrote:
On Dec 2, 5:53 pm, James Kuyper <jameskuy...@ve rizon.netwrote:
>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.

Dec 2 '07 #3
On Dec 2, 6:30 pm, santosh <santosh....@gm ail.comwrote:
somenath wrote:
On Dec 2, 5:53 pm, James Kuyper <jameskuy...@ve rizon.netwrote:
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 ?

Dec 2 '07 #4
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.
Dec 2 '07 #5
somenath wrote:
On Dec 2, 6:30 pm, santosh <santosh....@gm ail.comwrote:
>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().

Dec 2 '07 #6
Barry Schwarz wrote:
<so*********@gm ail.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

Dec 5 '07 #7
On Sun, 2 Dec 2007 05:18:27 -0800 (PST), somenath
<so*********@gm ail.comwrote:
>On Dec 2, 5:53 pm, James Kuyper <jameskuy...@ve rizon.netwrote:
>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
Dec 6 '07 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

5
7978
by: David | last post by:
this phrase has been mentioned many times in this NG and it seems like everyone know what it's. is it a book? a standard? or a guide of some sort? where can i read more about K&R2? thanks!
16
1679
by: TTroy | last post by:
I FOUND MAJOR ERRORS in K&R2 (making it almost useless for the herein mentioned topics). K&R2 Section 5.9 Pointers vs. Multidimension Arrays starts of like this... "Newcomers to C are somtimes confused about the difference between a two-dimensional array and an array of pointers..." then continues to explain int *b; to be...
16
2274
by: Josh Zenker | last post by:
This is my attempt at exercise 1-10 in K&R2. The code looks sloppy to me. Is there a more elegant way to do this? #include <stdio.h> /* copies input to output, printing */ /* series of blanks as a single one */ int main() { int c;
5
1470
by: Clausfor | last post by:
Hello everybody, I cannot find where in the K&R2 it is stated that variables must be defined at the beginning of a block and not within other lines. In Section 1.2 I read: In C, all variables must be declared before they are used, usually at the beginning of the function before any executable statements. USUALLY does not mean ABSOLUTELY, correct? I know that in C99 it is possible, but I'm interested in C89.
2
2292
by: arnuld | last post by:
there is a solution on "clc-wiki" for exercise 1.17 of K&R2: http://clc-wiki.net/wiki/K%26R2_solutions:Chapter_1:Exercise_17 i see this uses pointers whereas K&R2 have not discussed pointers yet. i have created a solution myself by modifying the example programme of section 1.19. i tried to find the source-code of K&R2 using Google. i found the home
8
4759
by: arnuld | last post by:
i have created a solutions myself. it compiles without any trouble and runs but it prints some strange characters. i am not able to find where is the trouble. --------------------------------- PROGRAMME -------------------------------- /* K&R2 section 1.9 exercise 1.19
19
2400
by: arnuld | last post by:
this programme runs without any error but it does not do what i want it to do: ------------- PROGRAMME -------------- /* K&R2, section 1.6 Arrays; Exercise 1-13. STATEMENT: Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical
24
1800
by: Anthony Irwin | last post by:
Hi all, I have been going through the k&r2 book and all the examples are done with main() instead of int main(void) and k&r2 in the start of chapter 1 does not return 0 so I haven't yet either. I did two compiles shown below. $ gcc -std=c89 -Wall exercise_1-9.c -o exercise_1-9 exercise_1-9.c:5: warning: return type defaults to `int'
15
1814
by: arnuld | last post by:
STATEMENT: Write the function strindex(s, t), which returns the position of the rightmost occurence of t in s, or -1 if there is none. PURPOSE: this program prints the index of the rightmost match on the line. The match we have to find is a char array named pattern. We also print out the number of matches we have found. We will take the input from command-line. PROBLEM: Segmentation Fault
0
8823
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9348
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9202
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9109
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
7981
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6648
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4478
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
3177
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2545
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.