This file discribes how do malloc and checker work.
 Written by Tristan Gingold (c) 1993.

You can (or must) add comments, precisions, you can complete, correct what I
(and other) write.
Excuse me for the English mistakes. If you spend time to see them, take time
to correct them.

  /\     I won't decribe line per line the file.
 /||\
/ .. \
------

   Intro: ( I think you know C language and what is malloc)

How is the memory organized?
The standard way is to divide the memory of a processus into three segments:
+--------------+---------------+--------------+--------------+---------------+
|   text seg   |   data seg    |  bss seg     |-->        <--|  stack seg    |
| (code)       | (initialized) | (fill to 0)  |-->        <--|               |
|  read only   | read & write  | read & write |-->        <--|               |
+--------------+---------------+--------------+--------------+---------------+
0            &etext          &edata          &end           esp      0xbfffffff
text and data segment are read from the executable. bss segment is allocated
when the executable time and initialized at 0. Besides the bss segment, the
processus can allocate memory by brk(2) or sbrk(3), but usually it calls
malloc(3). The memory allocated is named the heap. The heap grows upward. At
the end of the processus memory, the space is reserved for the stack.

Usually, the stack segment grows (downward) automatically.
This malloc use a table to save information on the heap.
So, each block of the heap has an entry in this table.
This table is named _heapinfo[]. There is an entry for BLOCKSIZE(4096)
bytes. At the begin, it has a fixed size HEAP. When this size is too small,
malloc grow this table. See malloc.c:morecore.

Blocks can be grouped with other (if they follow each-other), or can be
sub-divised in fragments. Fragment size is a power of 2. Minimum size of
fragment is sizeof(struct list), because free frags(ments) are linked and
structure list, which is inside the fragment contains the links.
So malloc alloc often more memory that necessary, but it is rather fast.

Note: malloc(0) return 0.


				malloc:
The first task of malloc is to initialised itself if it hasn't been done.
if __malloc_initialized is null, malloc call initialize. This flag is also
used in other piece of software that works with malloc.

malloc check that size is greater than sizeof(struct list) and change size
if necessary. So, too small fragment must not exist.

According to size, malloc will alloc blocks or a fragment.

 Blocks:
malloc loop until it reachs a large enough block or until the loop is
complete.
If no memory is found, malloc will get more memory (with morecore), but
perhaps the last block has memory, so malloc can join the two zone.The new
block is linked.
If memory is found, malloc remove the block from the free list.

Garbage detecting.
When calling chkr_garbage_detector() the data and stack are searched
for pointers to heap blocks. These blocks are then recursively
searched for pointers to other heap blocks.

Blocks not found in this search are signalled as garbage.

chkr_evol_detector() does the same search but does not report lost
blocks that are already reported in a previous chkr_garbage_detector()
or chkr_evol_detector().