Memory Allocation: An example.
			David Malone
			11/11/1999

This example follows the allocation of memory in the following
program.  I've numbered the lines so you can follow the explanation.

	+-------------------------------------------------------+
L1	|struct matrix {					|
L2	|	int size;					|
L3	|	double *data;					|
L4	|};							|
L5	|							|
L6	|int main() {						|
L7	|	struct matrix *m;				|
L8	|							|
L9	|	m = alloc_matrix(10);				|
L10	|	fill_matrix(m,1.0);				|
L11	|	free_matrix(m);					|
L12	|	exit(0);					|
L13	|}							|
L14	|							|
L15	|struct matrix *alloc_matrix(int size) {		|
L16	|	struct matrix *r;				|
L17	|							|
L18	|	r = malloc(sizeof(struct matrix));		|
L19	|	r->size = size;					|
L20	|	r->data = malloc(sizeof(double)*size*size);	|
L21	|							|
L22	|	return r;					|
L23	|}							|
L24	|							|
L25	|void fill_matrix(struct matrix *m,double value) {	|
L26	|	int i,j;					|
L27	|							|
L28	|	for( i = 0; i < m->size; i++ )			|
L29	|		for( j = 0; j < m->size; j++ )		|
L30	|			m->data[i*m->size + j] = value;	|
L31	|}							|
L32	|							|
L33	|void free_matrix(struct matrix *m) {			|
L34	|	free(m->data);					|
L35	|	free(m);					|
L36	|}							|
	+-------------------------------------------------------+

OK - we'll begin with the memory map of our program just before
main starts to run. I've numbered the addresses in memory from
0x0000 to 0xffff. When we begin suppose that:

	1) the stack is at the top of the address space (at 0xffff),
	2) that our compiled C code starts with main() at 0x0008,
	3) that the C library is at 0x0200,
	4) that the heap then starts at 0x0400.

	+-----------------------+ <- Bottom of stack.
0xffff	|                       |
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
	|                       |
	|                       |
	|                       |
0x0400	|-----------------------| <- Top of heap.
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

When main begins (L7) space for a pointer called "m" is needed.
I'll write this as main::m - to show it is the m in main. Space
for variables inside functions is allocated on the stack, so the
bottom of the stack moves down and space for main::m is made.

I've supposed pointers are 4 bytes, so the 4 bytes allocated to
main::m are 0xfffc, 0xfffd, 0xfffe and 0xffff. No value is written
into this memory yet, and no memory is set aside for the struct
m will point at.

	+-----------------------+
0xfffc	|                       |<- main::m
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
	|                       |
	|                       |
0x0400	|-----------------------| <- Top of heap.
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

The next thing that happens in main is alloc_matrix(10) is called
(L9).  Before this can be done three things need to be stored.
First the registers must be saved before calling alloc_matrix, then
10 must be put on the stack so that alloc_matrix knows what number
is was given and finally the address to return to once alloc_matrix
is finished must be put on the stack.

I've supposed that the registers take up 32 bytes and that the
address to go back to in main is 0x0084.

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matrix::size
0xffd4	| 0x0084                |<- address to return to inside main
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
0x0400	|-----------------------| <- Top of heap.
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now we are ready to start running matrix_alloc. At line 16 we see that
matrix_alloc allocates space for a pointer called r. That moves the stack
down another 4 bytes.

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matrix::size
0xffd4	| 0x0084                |<- address to return to inside main
0xffd0	|                       |<- matrix_alloc::r
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
0x0400	|-----------------------| <- Top of heap.
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now on line 18 the first thing that happens is that we call
malloc(sizeof(struct matrix)). Since "struct matrix" contains an
int (size 4) and a pointer to a double (size 4), it would be
reasonable to expect struct matrix to have size 8. Again, because
we are about to make a function call we must push the registers
and the return address onto the stack.

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matrix::size
0xffd4	| 0x0084                |<- address to return to inside main
0xffd0	|                       |<- matrix_alloc::r
0xffb0	|                       |<- registers saved from matrix_alloc.
0xffac	| 8                     |<- argument to malloc.
0xffb8	| 0x00c4                |<- address to return to inside matrix_alloc.
	+-----------------------+<- new bottom of stack
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
0x0400	|-----------------------| <- Top of heap.
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now we are running the code for malloc, which will be somewhere inside the
C library. We have asked it to set aside 8 bytes on the heap. Since the
top of the heap it currently at 0x0400, it will move to 0x0408 and the
bytes 0x0400 to 0x0407 inclusive will be set aside.

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matirx::size
0xffd4	| 0x0084                |<- address to return to inside main
0xffd0	|                       |<- matrix_alloc::r
0xffb0	|                       |<- registers saved from matrix_alloc.
0xffac	| 8                     |<- argument to malloc.
0xffb8	| 0x00c4                |<- address to return to inside matrix_alloc.
	+-----------------------+<- new bottom of stack
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
0x0408	|-----------------------| <- Top of heap.
0x0400	|                       | <- 8 bytes set aside by malloc.
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now malloc passes the address (0x0400) of these bytes back to alloc_matrix,
so it pops the return address off the stack restores the registers and the
value 0x0400 is written into alloc_matrix::r. (We're now back to L18).

Note that while space on the stack has been freed up, the 8 bytes on the
heap remain allocated.

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matirx::size
0xffd4	| 0x0084                |<- address to return to inside main
0xffd0	| 0x0400                |<- matrix_alloc::r
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
0x0408	|-----------------------| <- Top of heap.
0x0400	|                       | <- 8 bytes set aside by malloc.
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

On L19 we want to write size (which was passed in as a parameter) into
r->size. I should explain what writing to r->size means:

	r has value 0x0400, which is the address of some memory we are
	about to use as a "struct matrix". Since r->size is an int at
	the start of this structure it means write 4 bytes representing
	an integer at address 0x0400.

	When we write to r->data, in a moment, this will mean write
	4 bytes, representing a pointer, to 0x0404 - the extra 4 is
	to skip over r->size.

So the end result of L19 is that the 10 on the stack is copied into
location 0x0400.

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matirx::size
0xffd4	| 0x0084                |<- address to return to inside main
0xffd0	| 0x0400                |<- matrix_alloc::r
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
	|                       |
0x0408	|-----------------------| <- Top of heap.
0x0400	|size=10                | <- 8 bytes set aside by malloc.
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now the first thing that happens on line 20 is that malloc is called
with a size of 8*10*10 = 800 (presuming a double has size 8). Again we
have to shove the registers, 800 and the return address onto the stack.
The return address will be a bit higher this time as we have now finished
L18 and L19.

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matirx::size
0xffd4	| 0x0084                |<- address to return to inside main
0xffd0	| 0x0400                |<- matrix_alloc::r
0xffb0	|                       |<- registers saved from matrix_alloc.
0xffac	| 800                   |<- argument to malloc.
0xffb8	| 0x00c4                |<- address to return to inside matrix_alloc.
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
	|                       |
0x0408	|-----------------------| <- Top of heap.
0x0400	|size=10                | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Again we are running malloc in the C library which sets aside 800
bytes starting at the top of the heap. 800 in hex is 0x320 and the
top of the heap is now at 0x0408, so the bytes at 0x0408 to 0x727
are set aside.

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matirx::size
0xffd4	| 0x0084                |<- address to return to inside main
0xffd0	| 0x0400                |<- matrix_alloc::r
0xffb0	|                       |<- registers saved from matrix_alloc.
0xffac	| 800                   |<- argument to malloc.
0xffb8	| 0x00c4                |<- address to return to inside matrix_alloc.
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|                       |
	|                       |
	|                       |
0x0408	|                       | <- 800 bytes set aside by malloc.
0x0400	|size=10                | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Malloc returns the start address of these 800 bytes to alloc_matrix,
after popping the registers off the stack and jumping to the return
address.

The start address is 0x0408 and this gets written into r->data at
address 0x0404 (as r has value 0x0400 and data has an offset of 4
in struct matrix).

	+-----------------------+
0xfffc	|                       |<- main::m
0xffdc	|                       |<- registers saved for main.
0xffd8	| 10                    |<- argument alloc_matirx::size
0xffd4	| 0x0084                |<- address to return to inside main
0xffd0	| 0x0400                |<- matrix_alloc::r
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|                       |
	|                       |
	|                       |
0x0408	|                       | <- 800 bytes set aside by malloc.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now we are at line 22 where alloc_matrix finishes and pops the
registers off the stack and jumps back to address 0x0084 in main
(half way through line 9) where the value in alloc_matrix::r is
returned and put into main::m.

We are now in a situation where m points at a section of 8 bytes
on the heap which as a struct matrix contains:

	m->size = 10
	m->data = 0x0408

The pointer m->data points at a section of 800 bytes on the heap
which we are about to use as 100 doubles, or a 10x10 matrix of
doubles.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|                       |
	|                       |
	|                       |
0x0408	|                       | <- 800 bytes set aside by malloc.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now we are on line 10 and about to call fill_matrix. This time we must
push the registers, return address and 2 arguments onto the stack. The
two arguments are a pointer with value 0x0400 (copied from main::m) and
the double value 1.0.

Again as we are futher through main the return address into main is a
little higher than last time.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
0xffdc	|			|<- registers saved for main.
0xffd8	| 0x0400                |<- first argument (fill_matirx::m)
0xffd0	| 1.0                   |<- second argument (fill_matrix::value)
0xffcc	| 0x00a2                |<- address to return to inside main
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|                       |
	|                       |
	|                       |
0x0408	|                       | <- 800 bytes set aside by malloc.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Line 26 is the first line of fill_matrix. It allocates space for two
integers i and j. These go on the stack again.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
0xffdc	|			|<- registers saved for main.
0xffd8	| 0x0400                |<- first argument (fill_matirx::m)
0xffd0	| 1.0                   |<- second argument (fill_matrix::value)
0xffcc	| 0x00a2                |<- address to return to inside main
0xffc8	|                       |<- fill_matrix::i
0xffc4	|                       |<- fill_matrix::j
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|                       |
	|                       |
	|                       |
0x0408	|                       | <- 800 bytes set aside by malloc.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now, the for loops on L28 and L29 make i and j take on values (0,0),
(0,1) (0,2).. (0,9) (1,0) (1,1) .. (1,9). It knows to stop at 10
because fill_matrix::m is 0x0400 and so fill_matrix::m->size also
looks at location 0x0400 'cos size has offset 0 inside struct matrix,
and location 0x0400 contains 10.

Likewise m->data points at the first of an array of 100 doubles. By
working out i*10+j you will find that we are stepping through these
doubles and writing value, which is 1.0, into each of them.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
0xffdc	|			|<- registers saved for main.
0xffd8	| 0x0400                |<- first argument (fill_matirx::m)
0xffd0	| 1.0                   |<- second argument (fill_matrix::value)
0xffcc	| 0x00a2                |<- address to return to inside main
0xffc8	| 9                     |<- fill_matrix::i
0xffc4	| 9                     |<- fill_matrix::j
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|              ... 1.0  |
	| ....                  |
	| 1.0 1.0 1.0 1.0 1.0   |
0x0408	| 1.0 1.0 1.0 1.0 1.0   | <- 800 bytes set aside by malloc.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now we have an array, starting at location 0x0408 with 100 doubles
in, all which have had 1.0 written into them.

Returning from fill_matrix only involves restoring the registers
and jumping to the return address. As fill_matix is a void, we do
not have to pass a value back to main.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|              ... 1.0  |
	| ....                  |
	| 1.0 1.0 1.0 1.0 1.0   |
0x0408	| 1.0 1.0 1.0 1.0 1.0   | <- 800 bytes set aside by malloc.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Back in main we are now on line 11, and about to call free_matrix.
We have to push the registers, return address and the value of m onto
the stack.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
0xffdc	|			|<- registers saved for main.
0xffd8	| 0x0400                |<- first argument (free_matrix::m)
0xffd4	| 0x00b6                |<- return address
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|              ... 1.0  |
	| ....                  |
	| 1.0 1.0 1.0 1.0 1.0   |
0x0408	| 1.0 1.0 1.0 1.0 1.0   | <- 800 bytes set aside by malloc.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now, there are no variables declared inside free_matrix, so we move
straight to line 34. free_matrix::m has value 0x0400 and m->data
has offset 4 so we want the contents of location 0x0404. Looking
we see this is 0x0408. So, the argument to free in line 34 is
0x0408. As usual we push the arguments, return address and registers
onto the stack.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
0xffdc	|			|<- registers saved for main.
0xffd8	| 0x0400                |<- argument (free_matrix::m)
0xffd4	| 0x00b6                |<- return address in main
0xffb4	|			|<- registers saved for free_matrix
0xffd8	| 0x0408                |<- argument to free
0xffb4	| 0x0164		|<- address to return to inside free_matrix.
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
0x0730	|-----------------------| <- Top of heap.
	|              ... 1.0  |
	| ....                  |
	| 1.0 1.0 1.0 1.0 1.0   |
0x0408	| 1.0 1.0 1.0 1.0 1.0   | <- 800 bytes set aside by malloc.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

Now free will be some code inside the C library. It will try to free the
chunk of data on the heap starting at 0x408. Malloc will have noted that
this region was 800 bytes long and so free will know to only free that
much. When free returns the top of the heap will have moved back down
to 0x0408.

[NB - If data had been allocated above 0x730 on the heap, the top of the
heap would not move down, so that data would remain valid. Malloc and free
look after all this stuff automatically for you.]

Free is a void function, so it just restores the registers and jumps back
to 0x0164 in free_matrix.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
0xffdc	|			|<- registers saved for main.
0xffd8	| 0x0400                |<- argument (free_matrix::m)
0xffd4	| 0x00b6                |<- return address
0xffd8	| 0x0408                |<- argument to free
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
	|                       |
0x0408	|-----------------------| <- Top of heap.
0x0400	|size=10 data=0x0408    | <- 8 bytes set aside by malloc. struct matrix
	|-----------------------|
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

We can now no longer use the array of doubles which is pointed by m->data -
that memory is no longer available to us. Finally on line 35 free is called
with 0x0400 as an argument, which after the usual pushing and popping
moves the top of the heap back to 0x0400. On line 36 we return to main,
address 0x00b6.

	+-----------------------+
0xfffc	| 0x0400                |<- main::m
	+-----------------------+<- new bottom of stack
	|                       |
	|                       |
	|                       |
	|     F R E E           |
	|       M E M O R Y     |
	|                       |
	|                       |
	|                       |
0x0400	|-----------------------| <- Top of heap.
0x0200	|Library functions      |
	|-----------------------|
0x0160	|free_matrix() { ... }  |
0x0120	|fill_matrix() { ... }  |
0x00c0	|matix_alloc() { ... }  |
0x0080	|main() { ... }         |
	+-----------------------+

To call exit(0) in main will involve pushing registers and 0 onto the stack
and a return address onto the stack. However exit never returns, and our
processes address space will be completly freed when it is finished.

Footnotes:

1) In the real world what is pushed onto the stack at each function
call is likely to be different to what I have shown. For example it
may not be necessary to save any registers, as space for most variables
will have been allocated on the stack.


2) In the real world a struct may well be "padded", where space is
added inside the structure to keep data nicely aligned. For example:

struct blah {
	char foo;
	double bar;
};

Might have foo with offset 0 and size 1 byte, then 7 bytes of
padding and then 8 bytes for bar to keep bar lined up correctly.
Structures which are not padded are said to be "packed".

Trouble can arise if you use two different compilers to compile
different bits of a program unless they have the same rules for
padding. An ABI should specify how to pack structures.

3) Malloc may also do similar rounding to powers of 2. If you ask
for 13 bytes, chances are that malloc will allocate atleast 16.
This makes management of what is allocated much easier.

4) Malloc has to remember how long each allocation it makes is, so
free knows how much to free later. This means that malloc will
probably have a small amount of memory allocated for this bookeeping.
Where to put this memory is an interesting question - you can't
malloc it! (See Poul-Henning Kamp's paper on malloc for more details).

5) I choose not to put main starting at address 0x0000 because that
is where the NULL pointer points on most Unix systems. Usually Unix
will map a bad page at address 0x0000 which causes a segmentation
fault so people can find bugs where they accidently use a NULL
pointer.

6) The other addresses I just made up, but should be consistant.
An address space running from 0x0000 to  0xffff is only 64kB -
which is a bit small for todays computer systems.  The address
space your processes actually run in are probably atleast 4GB in
size.