Memory allocation by malloc

[Ardhendu Nandan]

Hi,
Will someone please tell me, How malloc allocating memory from heap & what
data structure it is using to do so.
regards
Ardhendu

 

[dandelion]

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.

 

[E. Robert Tisdale]

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.

 

[Eric Sosman]

Ardhendu Nandan wrote:




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.

 

[E. Robert Tisdale]

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?

 

[Eric Sosman]

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

 

[E. Robert Tisdale]

"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?

 

[Richard Tobin]

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

 

[Richard Bos]

E. Robert Tisdale wrote:

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

 

[Eric Sosman]

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.

 

[Keith Thompson]

Or too blunt. A heap is very like a stack, only less neatly structured.

Seems to me it's not a pun at all, just a (not entirely literal) use
of the word. To be a pun, it would have to play on a similarity in
the pronunciation of two words or phrases. Not that it matters, of
course.

 

[Michael Wojcik]

Seems to me it's not a pun at all, just a (not entirely literal) use
of the word. To be a pun, it would have to play on a similarity in
the pronunciation of two words or phrases.

That's certainly one possible definition of "pun", but in rhetoric
and poetics technical definitions of "pun" rarely restrict the trope
to accidents of pronunciation. For example, Richard Lanham writes:

Puns come in so many different forms that one scholar (Walter
Redfern, _Puns_) confesses at the beginning of his book that he
gave up trying to identify the separate species.
(_A Handlist of Rhetorical Terms_, 2nd ed, 127)

Among the examples Lanham cites to illustrate the pun is JFK's
infamous "Ich bin ein Berliner", which is a grammatical pun, not one
of pronunciation (and an inadvertent one at that).

In Lanham's analysis the typical rhetorical pun is a "bistable
illusion" at the word level - he likens it to irony in diction. He
goes on to identify both adnominatio (playing on the sound of words)
and paronomasia (playing on the sense of words) as types of pun,
though he says antanaclasis (one word used in two contrasting senses,
or substitution of a word for its homonym, or repetition of a word
but in different senses) is "closest to the simple English pun" (127,
128, 12).

The use of "heap" derived from "stack" is arguably an example of
paronomasia. However, it strikes me as no more than an extended
metaphor. "Stack" is used because the data structure is
metaphorically a stack of items; thus the association with a heap of
items doesn't require any play on meanings of "stack". (Had "stack"
been coined in its computer usage for some other reason - say, as
some sort of acronym, or from a proper name - then we'd have a clear
case of punning.)

However, this is more a poetic than a rhetorical trope, and poetics
is a notoriously subjective field of inquiry.

 

[Richard Bos]

Among the examples Lanham cites to illustrate the pun is JFK's
infamous "Ich bin ein Berliner", which is a grammatical pun, not one
of pronunciation (and an inadvertent one at that).

Agh... no, it isn't. Ask any Berliner.

Richard

 

[Michael Wojcik]

Agh... no, it isn't. Ask any Berliner.

I don't care whether it is or not; I'm reporting Lanham's example,
not one of my own. (And yes, I've read far more discussion about
whether this was or wasn't an error, funny, etc, than I could
possibly want.)