Pointers And Memory - Contents
A D V E R T I S E M E N T
"Heap" memory, also known as "dynamic" memory, is an alternative to local stack
memory. Local memory (Section 2) is quite automatic it is allocated automatically on
function call and it is deallocated automatically when a function exits. Heap memory is
different in every way. The programmer explicitly requests the allocation of a memory
"block" of a particular size, and the block continues to be allocated until the programmer
explicitly requests that it be deallocated. Nothing happens automatically. So the
programmer has much greater control of memory, but with greater responsibility since
the memory must now be actively managed. The advantages of heap memory are...
- Lifetime:
Because the programmer now controls exactly when memory is
allocated and deallocated, it is possible to build a data structure in
memory, and return that data structure to the caller. This was never
possible with local memory which was automatically deallocated when the
function exited.
- Size: The size of allocated memory can be controlled with more detail.
For example, a string buffer can be allocated at run-time which is exactly
the right size to hold a particular string. With local memory, the code is
more likely to declare a buffer size 1000 and hope for the best. (See the
StringCopy() example below.)
The disadvantages of heap memory are...
- More Work:
Heap allocation needs to arranged explicitly in the code
which is just more work.
- More Bugs:
Because it's now done explicitly in the code, realistically on
occasion the allocation will be done incorrectly leading to memory bugs.
Local memory is constrained, but at least it's never wrong.
Nonetheless, there are many problems that can only be solved with heap memory, so
that's that way it has to be. In languages with garbage collectors such as Perl, LISP, or
Java, the above disadvantages are mostly eliminated. The garbage collector takes over
most of the responsibility for heap management at the cost of a little extra time taken at
run-time.
What Does The Heap Look Like?
Before seeing the exact details, let's look at a rough example of allocation and
deallocation in the heap...
Allocation
The heap is a large area of memory available for use by the program. The program can
request areas, or "blocks", of memory for its use within the heap. In order to allocate a
block of some size, the program makes an explicit request by calling the heap allocation
function. The allocation function reserves a block of memory of the requested size in the
heap and returns a pointer to it. Suppose a program makes three allocation requests to
allocate memory to hold three separate GIF images in the heap each of which takes 1024
bytes of memory. After the three allocation requests, memory might look like...
Each allocation request reserves a contiguous area of the requested size in the heap and
returns a pointer to that new block to the program. Since each block is always referred to
by a pointer, the block always plays the role of a "pointee" (Section 1) and the program
always manipulates its heap blocks through pointers. The heap block pointers are
sometimes known as "base address" pointers since by convention they point to the base
(lowest address byte) of the block.
In this example, the three blocks have been allocated contiguously starting at the bottom
of the heap, and each block is 1024 bytes in size as requested. In reality, the heap
manager can allocate the blocks wherever it wants in the heap so long as the blocks do
not overlap and they are at least the requested size. At any particular moment, some areas
in the heap have been allocated to the program, and so are "in use". Other areas have yet
to be committed and so are "free" and are available to satisfy allocation requests. The
heap manager has its own, private data structures to record what areas of the heap are
committed to what purpose at any moment The heap manager satisfies each allocation
request from the pool of free memory and updates its private data structures to record
which areas of the heap are in use.
Deallocation
When the program is finished using a block of memory, it makes an explicit deallocation
request to indicate to the heap manager that the program is now finished with that block.
The heap manager updates its private data structures to show that the area of memory
occupied by the block is free again and so may be re-used to satisfy future allocation
requests. Here's what the heap would look like if the program deallocates the second of
the three blocks...
After the deallocation, the pointer continues to point to the now deallocated block. The
program must not access the deallocated pointee. This is why the pointer is drawn in gray
the pointer is there, but it must not be used. Sometimes the code will set the pointer to
NULL immediately after the deallocation to make explicit the fact that it is no longer
valid
Programming The Heap
Programming the heap looks pretty much the same in most languages. The basic features
are....
- The heap is an area of memory available to allocate areas ("blocks") of
memory for the program.
- There is some "heap manager" library code which manages the heap for
the program. The programmer makes requests to the heap manager, which
in turn manages the internals of the heap. In C, the heap is managed by the
ANSI library functions malloc(), free(), and realloc().
- The heap manager uses its own private data structures to keep track of
which blocks in the heap are "free" (available for use) and which blocks
are currently in use by the program and how large those blocks are.
Initially, all of the heap is free.
- The heap may be of a fixed size (the usual conceptualization), or it may
appear to be of a fixed but extremely large size backed by virtual memory.
In either case, it is possible for the heap to get "full" if all of its memory
has been allocated and so it cannot satisfy an allocation request. The
allocation function will communicate this run-time condition in some way
to the program usually by returning a NULL pointer or raising a
language specific run-time exception.
- The allocation function requests a block in the heap of a particular size.
The heap manager selects an area of memory to use to satisfy the request,
marks that area as "in use" in its private data structures, and returns a
pointer to the heap block. The caller is now free to use that memory by
dereferencing the pointer. The block is guaranteed to be reserved for the
sole use of the caller the heap will not hand out that same area of
memory to some other caller. The block does not move around inside the
heap its location and size are fixed once it is allocated. Generally, when
a block is allocated, its contents are random. The new owner is responsible
for setting the memory to something meaningful. Sometimes there is
variation on the memory allocation function which sets the block to all
zeros (calloc() in C).
- The deallocation function is the opposite of the allocation function. The
program makes a single deallocation call to return a block of memory to
the heap free area for later re-use. Each block should only be deallocated
once. The deallocation function takes as its argument a pointer to a heap
block previously furnished by the allocation function. The pointer must be
exactly the same pointer returned earlier by the allocation function, not
just any pointer into the block. After the deallocation, the program must
treat the pointer as bad and not access the deallocated pointee.
C Specifics
In the C language, the library functions which make heap requests are malloc() ("memory
allocate") and free(). The prototypes for these functions are in the header file .
Although the syntax varies between languages, the roles of malloc() and free() are nearly
identical in all languages...
- void* malloc(unsigned long size); The malloc() function
takes an unsigned integer which is the requested size of the block
measured in bytes. Malloc() returns a pointer to a new heap block if the
allocation is successful, and NULL if the request cannot be satisfied
because the heap is full. The C operator sizeof() is a convenient way to
compute the size in bytes of a type sizeof(int) for an int pointee,
sizeof(struct fraction) for a struct fraction pointee.
- void free(void* heapBlockPointer); The free() function
takes a pointer to a heap block and returns it to the free pool for later reuse.
The pointer passed to free() must be exactly the pointer returned
earlier by malloc(), not just a pointer to somewhere in the block. Calling
free() with the wrong sort of pointer is famous for the particularly ugly
sort of crashing which it causes. The call to free() does not need to give
the size of the heap block the heap manager will have noted the size in
its private data structures. The call to free() just needs to identify which
block to deallocate by its pointer. If a program correctly deallocates all of
the memory it allocates, then every call to malloc() will later be matched
by exactly one call to free() As a practical matter however, it is not always
necessary for a program to deallocate every block it allocates see
"Memory Leaks" below.
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
|
Add to Favorites
Make Home Page
