Hi,
Will someone please tell me, How malloc allocating memory from heap & what
data structure it is using to do so.
regards
Ardhendu
13  2556 
"Ardhendu Nandan" <ar************ *@rediffmail.co m> wrote in message
news:41******** *************** ***@posting.goo gle.com... Hi,
Will someone please tell me, How malloc allocating memory from heap &
what data structure it is using to do so.
Check out Knuth: The art of computer programming, Vol II (IIRC).
In short, there is no *single* answer, it depends on the implementation.
There are many ways of doing this, each having a specific set of pro's and
con's.
Ardhendu Nandan wrote: Will someone please tell me,
"How does malloc allocate memory from heap
& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
E. Robert Tisdale wrote: Ardhendu Nandan wrote:
Will someone please tell me,
"How does malloc allocate memory from heap
& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me). As for the remaining points:
- Some implementations may use a "free list" to
manage dynamic memory. Some use several such
lists. Some use trees, bit-maps, or other
data structures not well described by the term
"list."
- Some malloc() implementations search for free
storage. Others simply have it ready to dole
out, without any search required.
- Some free() implementations merge the released
storage with adjacent free areas. Others do
not, or do so only in some circumstances.
The Standard specifies what the memory management
functions must do, but not how they are to do it -- this
gives the implementor wide latitude in choosing data
structures and algorithms that suit the platform well.
The choices vary, and more widely than Mr. Tisdale's
reply suggests.
-- Er*********@sun .com
Eric Sosman wrote: E. Robert Tisdale wrote:
Ardhendu Nandan wrote:
Will someone please tell me,
"How does malloc allocate memory from heap
& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me). As for the remaining points:
- Some implementations may use a "free list" to
manage dynamic memory. Some use several such
lists. Some use trees, bit-maps, or other
data structures not well described by the term
"list."
- Some malloc() implementations search for free
storage. Others simply have it ready to dole
out, without any search required.
- Some free() implementations merge the released
storage with adjacent free areas. Others do
not, or do so only in some circumstances.
The Standard specifies what the memory management
functions must do, but not how they are to do it -- this
gives the implementor wide latitude in choosing data
structures and algorithms that suit the platform well.
The choices vary, and more widely than Mr. Tisdale's
reply suggests.
Examples?
E. Robert Tisdale wrote: Eric Sosman wrote:
E. Robert Tisdale wrote:
Ardhendu Nandan wrote:
Will someone please tell me,
"How does malloc allocate memory from heap
& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me). As for the remaining points:
- Some implementations may use a "free list" to
manage dynamic memory. Some use several such
lists. Some use trees, bit-maps, or other
data structures not well described by the term
"list."
- Some malloc() implementations search for free
storage. Others simply have it ready to dole
out, without any search required.
- Some free() implementations merge the released
storage with adjacent free areas. Others do
not, or do so only in some circumstances.
The Standard specifies what the memory management
functions must do, but not how they are to do it -- this
gives the implementor wide latitude in choosing data
structures and algorithms that suit the platform well.
The choices vary, and more widely than Mr. Tisdale's
reply suggests.
Examples?
"Buddy system" allocators use a tree, not a list,
and coalesce adjacent freed areas only if they are
buddies (and require no search to find the adjacent
buddy, either).
"Thread-hot" allocators usually have separate data
structures for each thread or group of threads, plus
some kind of cross-thread coordination.
"Pure mmap()" allocators just grab a new memory
block from the O/S at each malloc() and return it at
each free(), without trying to keep track of allocated
and available regions at all. (Admittedly this example
is a little shaky because "the O/S" is part of "the
implementation" and is presumably doing some record-
keeping of its own. Still, it's far from certain that
the O/S keeps track of your memory with a "free list"
or anything much like it.)
-- Er*********@sun .com
Eric Sosman wrote: E. Robert Tisdale wrote:
Eric Sosman wrote:
E. Robert Tisdale wrote:
Ardhendu Nandan wrote:
>Will someone please tell me,
>"How does malloc allocate memory from heap
>& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me). As for the remaining points:
- Some implementations may use a "free list" to
manage dynamic memory. Some use several such
lists. Some use trees, bit-maps, or other
data structures not well described by the term
"list."
- Some malloc() implementations search for free
storage. Others simply have it ready to dole
out, without any search required.
- Some free() implementations merge the released
storage with adjacent free areas. Others do
not, or do so only in some circumstances.
The Standard specifies what the memory management
functions must do, but not how they are to do it -- this
gives the implementor wide latitude in choosing data
structures and algorithms that suit the platform well.
The choices vary, and more widely than Mr. Tisdale's
reply suggests.
Examples?
"Buddy system" allocators use a tree, not a list,
and coalesce adjacent freed areas only if they are
buddies (and require no search to find the adjacent
buddy, either).
"Thread-hot" allocators usually have separate data
structures for each thread or group of threads, plus
some kind of cross-thread coordination.
"Pure mmap()" allocators just grab a new memory
block from the O/S at each malloc() and return it at
each free(), without trying to keep track of allocated
and available regions at all. (Admittedly this example
is a little shaky because "the O/S" is part of "the
implementation" and is presumably doing some record-
keeping of its own. Still, it's far from certain that
the O/S keeps track of your memory with a "free list"
or anything much like it.)
Actually, I was hoping that
you could name popular implementations
which did *not* use a free list.
You seem to be trying to convince someone
that a free list is not a typical, common or popular
implementation of free storage management.
Do your examples represent widely used implementations ?
Or are they obscure exceptions
that are of importance to almost no one?
In article <cn**********@n ntp1.jpl.nasa.g ov>,
E. Robert Tisdale <E.************ **@jpl.nasa.gov > wrote: malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
Free lists do not necessarily have to be searched. Implementations
that always allocate, say, power-of-two sized blocks are likely to use
a list for each size, so that no searching is needed. I believe that
the implementations on the machines I am using to post this message
have that property.
-- Richard
Eric Sosman <er*********@su n.com> wrote: E. Robert Tisdale wrote:
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me).
Or too blunt. A heap is very like a stack, only less neatly structured.
Richard
E. Robert Tisdale wrote:
Actually, I was hoping that
you could name popular implementations
which did *not* use a free list.
You seem to be trying to convince someone
that a free list is not a typical, common or popular
implementation of free storage management.
Do your examples represent widely used implementations ?
Or are they obscure exceptions
that are of importance to almost no one?
What I seem to be doing is only partly under my
control; the eye of the beholder has much to do with
it. My intent was to refute your implication that
all malloc()/etc. implementations (1) used free lists,
(2) conducted searches through them, and (3) combined
adjacent free areas.
The "obscure exceptions" include Solaris (which
provides about half a dozen different implementations
with different data structures and different trade-
offs), the Hoard thread-optimized memory allocator,
and (I'm led to believe) at least some of the Linux
library implementations . Whether these are "of
importance" is another eye-of-the-beholder matter.
Let me turn the question around: Can you come up
with a non-"obscure" C implementation that *does* use
a mere list to manage its memory? Whether you call it
"bloat" or "scale," implementations today are called
upon to manage far more memory than those of even five
years ago, never mind those of earlier times. O(N)
methods that were tolerable on 16-bit machines began
to show strain (and began to be replaced) in 32-bit
environments, and are simply not tenable in the 64-bit
world. All the major implementors have faced this
problem over the last couple decades, and I would be
frankly astonished if any of them failed to respond by
adopting fancier data structures than the list. So, go
to it: Hunt up the malloc() implementations for Solaris,
Linux, HP-UX, Windows, AIX, OpenVMS, Tru64, ... and let
us know who's still in the Stone Age.
-- Er*********@sun .com This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Chris S. |
last post by:
Is it possible to determine how much memory is allocated by an arbitrary
Python object? There doesn't seem to be anything in the docs about this,
but considering that Python manages memory allocation, why would such a
module be more difficult to design than say, the GC?
|
by: Roman Hartmann |
last post by:
hello,
I do have a question regarding structs. I have a struct (profil) which
has a pointer to another struct (point). The struct profil stores the
coordinates of points.
The problem is that I don't know how many points
there will be in every struct in the end, so I have to allocate memory
dynamically for
them and can't use an array of fixed size, unfortunately.
I would like to know if there is a better way to access struct members...
|
by: berthelot samuel |
last post by:
Hi,
I'm trying to develop an application for modeling 3D objects from
Bezier patches, but I have a memory allocation problem. Here are my
structures:
typedef struct _vector3 {
union
{
struct
{
|
by: Joerg Schwerdtfeger |
last post by:
Hi folks,
how can I determine the total main-memory size and the size of free
memory available in bytes?
I tried to use mallinfo() from malloc.h - resulting some strange values
in Windows (cygwin, gcc 3.3.1) and always 0 in Linux (2.4.22, gcc
3.3.2).
Thanks in advance,
|
by: RoSsIaCrIiLoIA |
last post by:
why not to build
a malloc_m() and a free_m() that *check* (if memory_debug=1) if
1) there are some errors in bounds of *all* allocated arrays
from them (and trace-print the path of code that make
the error and exit) just when malloc_m and free_m start.
(I use a 1100 static array for write the path (like a queue)
of called function, operator, etc and write using '+' where is
find the memory error)
2) if the pointer to free is alredy...
| | |
by: Dan Nilsen |
last post by:
Hi!
I'm writing a small piece of software that basically runs on an
embedded system with a Power-PC cpu. This runs on a stripped down
version of Linux - Busybox.
As I'm writing a piece of code that basically acts as a server and
that will be running for weeks or months and probably even longer,
memory management is a topic that is quite crucial.
|
by: Johan Tibell |
last post by:
I've written a piece of code that uses sockets a lot (I know that
sockets aren't portable C, this is not a question about sockets per
se). Much of my code ended up looking like this:
if (function(socket, args) == -1) {
perror("function");
exit(EXIT_FAILURE);
}
I feel that the ifs destroy the readability of my code. Would it be
|
by: Ken |
last post by:
In C programming, I want to know in what situations we should use
static memory allocation instead of dynamic memory allocation. My
understanding is that static memory allocation like using array is
faster than malloc, but dynamic memory allocation is more flexible.
Please comment... thanks.
|
by: Peterwkc |
last post by:
Hello all expert, i have two program which make me desperate bu after i have noticed the forum, my future is become brightness back.
By the way, my problem is like this i the first program was compiled and run without any erros but the second program has a run time error when the function return from allocate and the ptr become NULL. How to fixed this?
Second Program:
/* Best Method to allocate memory for 2D Array because it's
...
|
by: jeungster |
last post by:
Hello,
I'm trying to track down a memory issue with a C++ application that
I'm working on:
In a nutshell, the resident memory usage of my program continues to
grow as the program runs. It starts off at a nice 4% of memory, then
slowly grows up to 50% and beyond. This translates to around 2 gigs
of physical memory, and that's really way more memory than this
program should be taking up.
|
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...
| | |
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,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
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...
|
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...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
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...
| | |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |
