mpatrol.txt

debug source code under unix platform.

without that option in order for your program to run at a reasonable
speed.

5 Memory allocations
********************

   In the C and C++ programming languages there are generally three
different types of memory allocation that can be used to hold the
contents of variables.  Other programming languages such as Pascal,
BASIC and FORTRAN also support some of these types of allocation,
although their implementations may be slightly different.

5.1 Static memory allocations
=============================

   The first type of memory allocation is known as a _static memory
allocation_, which corresponds to file scope variables and local static
variables.  The addresses and sizes of these allocations are fixed at
the time of compilation(1) and so they can be placed in a fixed-sized
data area which then corresponds to a section within the final linked
executable file.  Such memory allocations are called static because
they do not vary in location or size during the lifetime of the program.

   There can be many types of data sections within an executable file;
the three most common are normal data, BSS data and read-only data.
BSS data contains variables and arrays which are to be initialised to
zero at run-time and so is treated as a special case, since the actual
contents of the section need not be stored in the executable file.
Read-only data consists of constant variables and arrays whose contents
are guaranteed not to change when a program is being run.  For example,
on a typical SVR4 UNIX system the following variable definitions would
result in them being placed in the following sections:

     int a;           /* BSS data */
     int b = 1;       /* normal data */
     const int c = 2; /* read-only data */

   In C the first example would be considered a _tentative_
declaration, and if there was no subsequent definition of that variable
in the current translation unit then it would become a _common_
variable in the resulting object file.  When the object file gets
linked with other object files, any common variables with the same name
become one variable, or take their definition from a non-tentative
definition of that variable.  In the former case, the variable is
placed in the BSS section.  Note that C++ has no support for tentative
declarations.

   As all static memory allocations have sizes and address offsets that
are known at compile-time and are explicitly initialised, there is very
little that can go wrong with them.  Data can be read or written past
the end of such variables, but that is a common problem with all memory
allocations and is generally easy to locate in that case.  On systems
that separate read-only data from normal data, writing to a read-only
variable can be quickly diagnosed at run-time.

   ---------- Footnotes ----------

   (1) Or more accurately, at link time.

5.2 Stack memory allocations
============================

   The second type of memory allocation is known as a _stack memory
allocation_, which corresponds to non-static local variables and
call-by-value parameter variables.  The sizes of these allocations are
fixed at the time of compilation but their addresses will vary
depending on when the function which defines them is called.  Their
contents are not immediately initialised, and must be explicitly
initialised by the programmer upon entry to the function or when they
become visible in scope.

   Such memory allocations are placed in a system memory area called the
_stack_, which is allocated per process(1) and generally grows down in
memory.  When a function is called, the state of the calling function
must be preserved so that when the called function returns, the calling
function can resume execution.  That state is stored on the stack,
including all local variables and parameters.  The compiler generates
code to increase the size of the stack upon entry to a function, and
decrease the size of the stack upon exit from a function, as well as
saving and restoring the values of registers.

   There are a few common problems using stack memory allocations, and
most generally involve uninitialised variables, which a good compiler
can usually diagnose at compile-time.  Some compilers also have options
to initialise all local variables with a bit pattern so that
uninitialised stack variables will cause program faults at run-time.
As with static memory allocations, there can be problems with reading
or writing past the end of stack variables, but as their sizes are
fixed these can usually easily be located.

   ---------- Footnotes ----------

   (1) Or per thread on some systems.

5.3 Dynamic memory allocations
==============================

   The last type of memory allocation is known as a _dynamic memory
allocation_, which corresponds to memory allocated via `malloc()' or
`operator new[]'.  The sizes, addresses and contents of such memory vary
at run-time and so can cause a lot of problems when trying to diagnose
a fault in a program.  These memory allocations are called dynamic
memory allocations because their location and size can vary throughout
the lifetime of a program.

   Such memory allocations are placed in a system memory area called the
_heap_, which is allocated per process on some systems, but on others
may be allocated directly from the system in scattered blocks.  Unlike
memory allocated on the stack, memory allocated on the heap is not
freed when a function or scope is exited and so must be explicitly
freed by the programmer.  The pattern of allocations and deallocations
is not guaranteed to be (and is not really expected to be) linear and
so the functions that allocate memory from the heap must be able to
efficiently reuse freed memory and resize existing allocated memory on
request.  In some programming languages there is support for a _garbage
collector_, which attempts to automatically free memory that has had
all references to it removed, but this has traditionally not been very
popular for programming languages such as C and C++, and has been more
widely used in functional languages like ML(1).

   Because dynamic memory allocations are performed at run-time rather
than compile-time, they are outwith the domain of the compiler and must
be implemented in a run-time package, usually as a set of functions
within a linker library.  Such a package manages the heap in such a way
as to abstract its underlying structure from the programmer, providing
a common interface to heap management on different systems.  However,
this _malloc library_ must decide whether to implement a fast memory
allocator, a space-conserving memory allocator, or a bit of both.  It
must also try to keep its own internal tables to a minimum so as to
conserve memory, but this means that it has very little capability to
diagnose errors if any occur.

   In some compiler implementations there is a builtin function called
`alloca()'.  This is a dynamic memory allocation function that allocates
memory from the stack rather than the heap, and so the memory is
automatically freed when the function that called it returns.  This is
a non-standard feature that is not guaranteed to be present in a
compiler, and indeed may not be possible to implement on some
systems(2).  However, the mpatrol library provides a debugging version
of this function (and a few other related functions) on all systems, so
that they make use of the heap instead of the stack.

   As can be seen from the above paragraphs, dynamic memory allocations
are the types of memory allocations that can cause the most problems in
a program since almost nothing about them can be used by the compiler
to give the programmer useful warnings about using uninitialised
variables, using freed memory, running off the end of a
dynamically-allocated array, etc.  It is these types of memory
allocation problems that the mpatrol library loves to get its teeth
into!

   ---------- Footnotes ----------

   (1) There is currently at least one garbage collection package
available for C and C++ (*note Related software::).

   (2) Some compilers now support variable length arrays which provide
roughly the same functionality.

6 Operating system support
**************************

   Beneath every malloc library's public interface there is the
underlying operating system's memory management interface.  This
provides features which can be as simple as giving processes the
ability to allocate a new block of memory for themselves, or it can
offer advanced features such as protecting areas of memory from being
read or written.  Some embedded systems have no operating systems and
hence no support for dynamic memory allocation, and so the malloc
library must instead allocate blocks of memory from a fixed-sized array.
The mpatrol library can be built to support all of the above types of
system, but the more features an operating system can provide it with,
the more it can do.

   On operating systems such as UNIX and Windows, all dynamic memory
allocation requests from a process are dealt with by using a feature
called _virtual memory_.  This means that a process cannot perform
illegal requests without them being denied, which protects the other
running processes and the operating system from being affected by such
errors.  However, on AmigaOS and Netware platforms there is no virtual
memory support and so all processes effectively share the same address
space as the operating system and any other running processes.  This
means that one process can accidentally write into the data structures
of another process, usually causing the other process to fail and bring
down the system.  In addition, a process which allocates a lot of memory
will result in there being less available memory for other running
processes, and in extreme cases the operating system itself.

6.1 Virtual memory
==================

   _Virtual memory_ is an operating system feature that was originally
used to provide large usable address spaces for every process on
machines that had very little physical memory.  It is used by an
operating system to fool(1) a running process into believing that it can
allocate a vast amount of memory for its own purposes, although whether
it is allowed to or not depends on the operating system and the
permissions of the individual user.

   Virtual memory works by translating a virtual address (which the
process uses) into a physical address (which the operating system
uses).  It is generally implemented via a piece of hardware called a
_memory management unit_, or MMU.  The MMU's primary job is to
translate any virtual addresses that are referred to by machine
instructions into physical addresses by looking up a table which is
built by the operating system.  This table contains mappings to and
from _pages_(2) rather than bytes since it would otherwise be very
inefficient to handle mappings between individual bytes.  As a result,
every virtual memory operation operates on pages, which are indivisible
and are always aligned to the system page size.

   Even though each process can now see a huge address space, what
happens when it attempts to allocate more pages than actually
physically exist, or allocate an additional page of memory when all of
the physical pages are in use by it and other processes?  This problem
is solved by the operating system temporarily saving one or more of the
least-used pages (which might not necessarily belong that that process)
to a special place in the file system called a _swap file_, and mapping
the new pages to the physical addresses where the old pages once
resided.  The old pages which have been _swapped out_ are no longer
currently accessible, but their location in the swap file is noted in
the translation table.

   However, if one of the pages that has been swapped out is accessed
again, a _page fault_ occurs at the instruction which referred to the
address and the operating system catches this and reloads the page from
the swap file, possibly having to swap out another page to make space
for the new one.  If this occurs too often then the operating system
can slow down, having to constantly swap in and swap out the same pages
over and over again.  Such a problem is called _thrashing_ and can only
really be overcome by using less virtual memory or buying more physical
memory.

   It is also possible to take advantage of the virtual memory system's
interaction between physical memory and the file system in program
code, since mapping an existing file to memory means that the usual
file I/O operations can be replaced with memory read and write
operations.  The operating system will work out the optimum way to read
and write any buffers and it means that only one copy of the file
exists in both physical memory and the file system.  Note that this is
how _shared libraries_(3) on UNIX platforms are generally implemented,
with each individual process that uses the shared library having it
mapped to somewhere in its address space.

   Another major feature of virtual memory is its ability to read
protect and write protect individual pages of process memory.  This
means that the operating system can control access to different parts
of the address space for each process, and also means that a process
can read and/or write protect an area of memory when it wants to ensure
that it won't ever read or write to it again.  If an illegal memory
access is detected then a _signal_ will be sent to the process, whi