MemoryAdvCh.tex

\chapter{All About Memory}

% 
% 
% Copyright 2002 Jonathan Bartlett
% 
% Permission is granted to copy, distribute and/or modify this
% document under the terms of the GNU Free Documentation License,
% Version 1.1 or any later version published by the Free Software
% Foundation; with no Invariant Sections, with no Front-Cover Texts,
% and with no Back-Cover Texts.  A copy of the license is included in fdl.xml
% 

Okay, so the last chapter was quite a doozy.  This may seem overwhelming
at first, but if you can stick it out you will have the background you need
to being a successful programmer.

\section{How a Computer Views Memory}

A computer looks at memory as a long sequence of numbered storage
locations.  A sequence of \emph{millions} of numbered
storage locations.  Everything is stored in these locations.  Your
programs are store there, your data is stored there, everything.  
Each storage location looks like every other one.  The locations 
holding your program are just like the ones holding your data.  In
fact, the computer has no idea which are which.  So, we've seen
how numbers are stored - each value takes up four storage locations.
How are the instructions stored?  Each instruction is a different
length.  Most instructions take up one or two storage locations for
the instruction itself, and then storage locations for the instruction's
arguments.  For example,

\begin{simpletyping}
\begin{lstlisting}
	movl data\_items(,{\ediBare},4), {\ebxBare}
\end{lstlisting}
\end{simpletyping}

takes up 7% FIXME - is this right? 
 storage locations.  The first two hold the instruction,
the third one tells which registers to use, and the next four hold
the storage location of \icode{data\_items}.  In memory,
these look just like all the other numbers, and the instructions themselves
can be moved into and out of registers just like numbers, because that's
what they are.  Now, let's define a few terms:

\begin{description}
\item[Address] An address is the number of a storage location.  For example, the first
storage location on a computer has an address of 0, the second has
an address of 1, and so on.\footnote{You actually never use
addresses this low, but it works for discussion.}
Every piece of data on the computer not in a register has an address.
Normally, we don't ever type the exact address of something, but we
use symbols instead (like using \icode{data\_items} in our
second program).
\item[Pointer] A pointer is a register or memory storage location whose value is an 
address.  In our second example, \icode{{\ebpBare}} was a pointer
to the current stack position.  Programming uses a lot of pointers,
which we will see eventually.
\item[Byte] This is the size of a storage location.  On Intel computers, a byte
can hold numbers between 0 and 255
\item[Word] This is the size of a normal register.  On Intel computers, a word
is four storage locations(bytes) long.
\end{description}

We have been using terms like \emph{storage location} instead
of their proper terms, like \emph{byte}.  This was so you
could have a better grasp on what was being done.  From here on, we
will be using the above terms instead, so be sure you know what they mean.

\section{The Instruction Pointer}

Previously we have concentrated on general registers and how they work.
The only special register we've dealt with is the status register, and
we really didn't say much about it.  The next special register we will
deal with is the instruction pointer, or \icode{{\eipBare}}.
We mentioned earlier that the computer sees every byte on the computer
in the same way.  If we have a number that is an entire word, the computer
doesn't know what address that word starts or ends at.  The computer doesn't know
the difference between instructions and data, either.  Any value in memory could be 
instructions, data, or the middle of an instruction or piece of data.  So how does the computer
know what to execute?  The answer is the instruction pointer.  The
instruction pointer always has the value of the next instruction.  When
the computer is ready to execute an instruction, it looks at the
instruction pointer to see where to go next.  It then increments the
instruction pointer to point to the next instruction.  After it finishes
executing the current instruction, it looks a the instruction pointer
again.  That's all well and good, but what about jumps (the 
\icode{jmp} family of instructions)?  At the end of those
instructions, the computer does \_not\_ look at the next instruction,
it goes to an instruction in a totally different place.  How does this
work?  Because 

\begin{simpletyping}
\begin{lstlisting}
	jmp somewhere
\end{lstlisting}
\end{simpletyping}

is exactly the same as

\begin{simpletyping}
\begin{lstlisting}
	movl \$somewhere, {\eipBare}
\end{lstlisting}
\end{simpletyping}

Where \icode{somewhere} is a symbol referring to a program
section.  Now, you can't actually do this, because you are not
allowed to refer directly to \icode{{\eipBare}}, but if you
could this would be how.  Also note that we put a dollar sign
in front of \icode{somewhere}.  How do we know when to
put a dollar sign and when not to?  The dollar sign says to treat
\icode{somewhere} as a value.  If the dollar sign weren't
there, it would move the value in the \icode{somewhere}'s
address into \icode{{\eipBare}}, which is not what we want.
In our previous programs, we often will load registers like this:

\begin{simpletyping}
\begin{lstlisting}
	movl  \$0, {\ebxBare}
\end{lstlisting}
\end{simpletyping}

If we accidentally left out the dollar sign, instead of putting the
number zero in \icode{{\ebxBare}}, we would be putting whatever
was at address zero on our computer into \icode{{\ebxBare}}.

\section{The Memory Layout of a Linux Program}

Okay, this whole section is completely stolen.  Call the police, I'm
plagiarizing.  This whole section was
basically copied from Konstantin Boldyshev's document, \documentname{Startup
state of a Linux/i386 ELF binary}, available at 
\url{http://linuxassembly.org/startup.html}.
Blame him for any mistakes (just kidding).  This information only applies
to Linux running on IA-32 architectures (Intel machines).   Other
operating systems and other system architectures probably work
differently.

When you program is loaded into memory, each \icode{.section}
is loaded into its own spot.  The actual code (the \icode{.text}
section) is loaded at the address 0x08048000.  The \icode{.data}
section is loaded immediately after that, followed by a section we
haven't talked about, called the \icode{.bss} 
section.  The \icode{.bss} section has all of the memory
locations that we reserve that we don't put values in until run-time.
In the \icode{.data} section, we put actual values into
the storage spaces we reserved (with the \icode{.long} 
directive).  This information is embedded in the program file, and
loaded when the program starts.  The \icode{.bss} section
is not initialized until after the program is run.  Therefore, the
data doesn't have to be stored in the program file itself, it just
notes that it needs a certain number of storage spaces.  Anyway,
we'll talk more about that later.

The last storage location that can be addressed is location
0xbfffffff.  The \icode{.text}, \icode{.data},
and \icode{.bss} sections all start at 0x08048000 and
grow larger.  The next sections start at the end and grow back
downward.\footnote{You may be thinking, "what if they grow
toward each other and overlap?"  Although this is possible, it
is extremely unlikely, because the amount of space in-between is
huge.}  First, at the very end of memory,
there are  two words that
just contain zeroes.  After that comes the name of the program.
Each letter takes up one byte, and it is ended by
the NULL character (the \icode{\\0} we talked about
earlier).\footnote{The NULL character is actually the 
number 0, not to be confused with the \emph{character}
\icode{0}, whose numeric value is not zero.  Every
possible letter, symbol, or number you can type with your keyboard
has a number associated with it.  These numbers are called
"ASCII codes".  We'll deal more with these later.}
After the program name comes the program environment values.  These
are not important to us now.  Then come the program arguments.
These are the values that the user typed in on the command line
to run this program.  In the case of the "maximum" program, there
would only be one value, \icode{./maximum}.  Other
programs take more arguments.  When we run \icodecmd{as},
for example, we give it several arguments - \icode{as},
\icode{maximum.s}, \icode{-o}, and 
\icode{maximum.o}.  After these, we have the stack.
This is where all of our data goes when we do pushes, pops and
calls.  Since the stack is at the top of the memory, it grows
down.  \icode{{\espBare}} always holds the current address
of where the next value will be put on the stack.  It then gets
decreased whenever there is a push, and increased whenever there
is a pop.  So,

\begin{simpletyping}
\begin{lstlisting}
	pushl {\eaxBare}
\end{lstlisting}
\end{simpletyping}

is equivalent to

\begin{simpletyping}
\begin{lstlisting}
	movl {\eaxBare}, ({\espBare})
	subl \$4, {\espBare}
\end{lstlisting}
\end{simpletyping}

\icode{subl} does subtraction.  Since \icode{{\eaxBare}}
is four bytes big, we have to subtract 4 from \icode{{\espBare}}.
In the same way

\begin{simpletyping}
\begin{lstlisting}
	popl {\eaxBare}
\end{lstlisting}
\end{simpletyping}

is the same as

\begin{simpletyping}
\begin{lstlisting}
	movl ({\espBare}), {\eaxBare}
	addl \$4, {\espBare}
\end{lstlisting}
\end{simpletyping}

Now, notice on the \icode{movl}, we had \icode{{\espBare}}
in parenthesis.  That's because we wanted the value that \icode{{\espBare}}
pointed to, not the actual address.  If we just did

\begin{simpletyping}
\begin{lstlisting}
	movl {\espBare}, {\eaxBare}
\end{lstlisting}
\end{simpletyping}

\icode{{\eaxBare}} would just have the pointer to the end of the stack.

So, the stack grows downward, while the \icode{.bss} section grows 
upward.  This middle part is called the break, and you are not allowed to 
access it until you tell the kernel that you want to.  If you try, you
will get an error (segmentation fault).  The same will happen if you try to
access data before the beginning of your program, 0x08048000.  In general,
it's best not to access any location unless you have reserved storage
for it in the stack, data, or bss sections.

\section{Every Memory Address is a Lie}

So, why does the computer not allow you to access memory in the 
break area?  To answer this question, we will have to delve into
the depths of how your computer really handles memory.  Be warned,
reading this section is like taking the blue pill\footnote{as
in the movie, \documentname{The Matrix}}.

You may have wondered, since every program gets loaded into the same
place in memory, don't they step on each other, or overwrite each other?
It would seem so.  However, as a program writer, you only access
\emph{virtual memory}.  \emph{Physical memory}
refers to the actual RAM chips inside your computer and what they contain.   It's usually
between 16 and 512 Megabytes.  If we talk about a \emph{physical
memory address}, we are talking about where exactly on these
chips a piece of memory is located.  So, what's virtual memory?  Virtual
memory is the way your program thinks about memory.  Before loading
your program, Linux finds empty physical memory, and then tells
the processor to pretend that this memory is actually at the address
0x0804800.  Confused yet?  Let me explain further.

Each program gets its own sandbox to play in.  Every program running
on your computer thinks that it was loaded at memory address 0x0804800,
and that its stack starts at 0xbffffff.  When Linux loads a program,
it finds a section of memory, and then tells the processor to use
that section of memory as the address 0x0804800 for this program.  The
address that a program believes it uses is called the virtual address,
while the actual address on the chips that it refers to is called
the physical address.  The process of assigning virtual addresses to
physical addresses is called \emph{mapping}.  Earlier we 
talked about the break in memory between the bss and the stack, but
we didn't talk about why it was there.  The reason is that this
segment of virtual memory addresses hasn't been mapped onto 
physical memory addresses.  The mapping process takes up considerable
time and space, so if every possible virtual address of every possible
program were mapped, you probably couldn't even run one program.  So,
the break is the area that contains unmapped memory.

Virtual memory can be mapped to more than just physical memory; it
can be mapped to disk as well.  Swap
files, swap partitions, and paging files all refer to the same 
basic idea - extending memory mapping to disk.  For example, let's
say you only have 16 Megabytes of physical memory.  Let's also say that
8 Megabytes are being used by Linux and some basic applications, and you
want to run a program that requires 20 Megabytes of memory.  Can you?  The
answer is yes, if you have set up a swap file or partition.  What
happens is that after all of your remaining 8 Megabytes of physical memory
have been mapped into virtual memory, Linux starts mapping parts of
your disk into memory.  So, if you access a "memory" location in your
program, that location may not actually be in memory at all, but on
disk.  When you access the memory, Linux notices that the memory
is on disk, and moves that portion of the disk back into physical 
memory, and moves another part of physical memory back onto the disk.
So, not only can Linux have a virtual address map to a different
physical address, it can also move those mappings around as needed.

Memory is separated out into groups called \emph{pages}.  When
running Linux on Intel systems, a page is four thousand ninety six bytes of memory.
All of the memory mappings are done a page at a time.  What this means to you
is that whenever you are programming, try to keep most memory accesses within
the same basic range of memory, so you will only need a page or two of memory.
Otherwise, Linux will have to keep moving pages on and off of disk to keep up
with you.  Disk access is slow, so this can really slow down your program.  Also,
if you have a lot of programs that are all moving around too fast into memory, your
machine can get so bogged down moving pages on and off of disk that the system
becomes unusable.  Programmers call this \emph{swap death}.  It is
usually recoverable if you start terminating your programs, but it's a pain.

\section{Getting More Memory}

We know that Linux maps all of our virtual memory into real memory or
swap.  If you try to access a piece of virtual memory that hasn't been mapped yet,
it triggers an error known as a segmentation fault, which will terminate your 
program.  The program break point, if you remember, is the last valid address you
can use.  Now, this is all great if you know beforehand how much storage you will
need.  You can just add all the memory you need to your data section, and it will
all be there.  But let's say you don't know how much memory you will need.  For example,
with a text editor, you don't know how long the person's file will be.  You could try
to find a maximum file size, and just tell the user that they can't go beyond that, but
that's a waste if the file is small.  So, Linux has a facility to move the break point.
If you need more memory, you can just tell Linux where you want the new break point
to be, and Linux will map all the memory you need, and then move the break point.  The
way we tell Linux to move the break point is the same way we told Linux to exit our program.
We load \icode{{\eaxBare}} with the system call number, 45 in this case, and load
\icode{{\ebxBare}} with the new breakpoint.  Then you call \icode{int \$0x80}
to signal Linux to do its work.  Linux will do its thing, and then return either 0 if there is no 
memory left or the
new break point in \icode{{\eaxBare}}.  The new break point might actually be larger
than what you asked for, because Linux rounds up to the nearest page.

 

The problem with this method is keeping track of the memory.  Let's say I need to
move the break to have room to load a file, and then need to move a break again to
load another file.  Later, let's say you get rid of the first file.  You now have
a giant gap in memory that's mapped, but you aren't using.  If you continue to 
move the break for each file you load, you can easily run out of memory.  So, what
you need is a \emph{memory manager}.  A memory manager consists of
two basic functions - \icode{allocate} and \icode{deallocate}.  A
memory manager usually also has an initialization function.  Not that the function names
might not be \icode{allocate} and \icode{deallocate}, but that
the functionality will be the same.
Whenever you need a certain amount of memory, you can simply tell \icode{allocate}
how much you need, and it will give you back an address to the memory.  When you're done with it, you tell \icode{deallocate}
that you are through with it.  Then \icode{allocate} will be able to reuse the
memory.  This minimizes the number of "holes" in your memory, making sure that you
are making the best use of it you can.

% FIXME - what about talking about handles? 

\section{A Simple Memory Manager}

Here I will show you a simple memory manager.  It is extremely slow at allocating memory,
especially after having been called several times\footnote{I use the word "slow", but 
it will not be noticeably slow for any example used in this book.}.  However, it shows the principles quite
well, and as we learn more sophisticated programming techniques, we will improve upon it.
As usual, I will give you the program first for you to look through.  Afterwards will follow
an in-depth explanation.

\begin{simpletyping}
\lstinputlisting{alloc.s}
\end{simpletyping}

The first thing to notice is that there is no \icode{\_start} symbol.  The reason
is that this is just a section of a program.  A memory manager by itself is not a full 
program - it doesn't do anything.  It has to be linked with another program to work.  Will
will see that happen later.  So, you can assemble it, but you can't link it.  So, type in
the program as \icodefilename{alloc.s}, and then assemble it with

\begin{simpletyping}
\begin{lstlisting}
as alloc.s -o alloc.o
\end{lstlisting}
\end{simpletyping}

Okay, now let's look at the code.

\section{Variables and Constants}

At the beginning of the program, we have two locations set up -

\begin{simpletyping}
\begin{lstlisting}
heap\_begin:
	.long 0

current\_break:
	.long 0
\end{lstlisting}
\end{simpletyping}

The section of memory being managed is commonly referred to as the \emph{heap}.  Now,
when we assemble the program, we have no idea where the beginning of the heap is, nor where the
current break point is.  Therefore, we reserve space for them, but just fill them with a 0 for the
time being.  You'll notice that the comments call them \emph{global variables}.  
A set of terms commonly used are \emph{global} and \emph{local} variables.
A local variable is a variable that is allocated on the stack when a procedure is run.  A global
variable is declared as above, and is allocated when the program begins.  So, global variables last
for the length of the program, while local variables only last for the run of the procedure.  It is
good programming practice to use as few global variables as possible, but there are some cases
where it is unavoidable.  We will look more at local variables later.

Next we have a section called \emph{constants}.  A constant is a symbol that we
use to represent a number.  For example, here we have

\begin{simpletyping}
\begin{lstlisting}
	.equ UNAVAILABLE, 0
	.equ AVAILABLE, 1
\end{lstlisting}
\end{simpletyping}

This means that anywhere we use the symbol UNAVAILABLE, to make it just like we're using the
number 0, and any time we use the symbol AVAILABLE, to make it just like we're using the number 1.
This makes the program much more readable.  We also have several others that make the program more
readable, like

\begin{simpletyping}
\begin{lstlisting}
	.equ BRK, 45
	.equ LINUX\_SYSCALL, 0x80
\end{lstlisting}
\end{simpletyping}

It is much easier to read \icode{int \$LINUX\_SYSCALL} than \icode{int \$0x80},
even though their meanings are the same.  In general, you should replace any hardcoded
value in your code that has a meaning with \icode{.equ} statements.

Next we have structure definitions.  The memory that we will be handing out has a definite
structure - it has four bytes for the allocated flag, four bytes for the size, and the rest
for the actual memory.  The eight bytes at the beginning are known as the header.  They
contain descriptive information about the data, but aren't actually a part of the data.  Anyway,
we have the following definitions:

\begin{simpletyping}
\begin{lstlisting}
	.equ HEADER\_SIZE, 8
	.equ HDR\_AVAIL\_OFFSET, 0
	.equ HDR\_SIZE\_OFFSET, 4
\end{lstlisting}
\end{simpletyping}

So, this says that the header is 8 bytes, the available flag is offset 0 positions from the 
beginning (it's the first thing), and the size field is offset 4 positions from the 
beginning (right after the available flag).  Since all of our structures are defined here,
if we needed to rearrange for some reason, all we have to do is change the numbers here.  If
we needed to add another field, we would just define it here, and change the 
\icode{HEADER\_SIZE}.  So, putting definitions like this at the top of the program
is useful, especially for long-term maintenance.  Just remember that these are only valid
for the current file.

\section{The \icode{allocate\_init} function}

Okay, this is a simple function.  All it does is set up the \icode{heap\_begin} and
\icode{current\_break} variables we discussed earlier.  So, if you remember the
discussion earlier, the current break can be found using the break system call.  So, the function
looks like this:

\begin{simpletyping}
\begin{lstlisting}
	pushl {\ebpBare}
	movl  {\espBare}, {\ebpBare}

	movl  \$BRK, {\eaxBare}
	movl  \$0,  {\ebxBare}
	int   \$LINUX\_SYSCALL

	incl  {\eaxBare}
\end{lstlisting}
\end{simpletyping}

Anyway, after \icode{int \$LINUX\_SYSCALL}, \icode{{\eaxBare}} holds the last valid address.  
We actually want the first invalid address, so we just increment \icode{{\eaxBare}}.  Then
we move that value to the \icode{heap\_begin} and \icode{current\_break}
locations.  Then we leave the function.  Like this:

\begin{simpletyping}
\begin{lstlisting}
	movl  {\eaxBare}, current\_break
	movl  {\eaxBare}, heap\_begin
	movl  {\ebpBare}, {\espBare}
	popl  {\ebpBare}
\end{lstlisting}
\end{simpletyping}

So, why do we want to put an invalid address as the beginning of our heap?  Because we don't control
any memory yet.  Our \icode{allocate} function will notice this, and reset the break
so that we actually have memory.

\section{The \icode{allocate} function}

This is the doozy function.  Let's start by looking at an outline of the function:

\begin{enumerate}
\item Start at the beginning of the heap 
\item Check to see if we're at the end of the heap 
\item If we are at the end of the heap, grab the memory we need from the kernel, mark it
as "unavailable" and return it.  If the kernel won't give us any more, return a 0. 
\item If the current memory segment is marked "unavailable", go to the next one, and go
back to \#2 
\item If the current memory segment is large enough to hold the requested amount of space,
mark it as "unavailable" and return it. 
\item Go back to \#2 
\end{enumerate}

Now, look through the code with this in mind.  Be sure to read the comments so you'll know 
which register holds which value.  

Now that you've looked through the code, let's examine it one line at a time.  We start
off like this:

\begin{simpletyping}
\begin{lstlisting}
	pushl {\ebpBare}
	movl  {\espBare}, {\ebpBare}
	movl  ST\_MEM\_SIZE({\ebpBare}), {\ecxBare}
	movl  heap\_begin, {\eaxBare}
	movl  current\_break, {\ebxBare}
\end{lstlisting}
\end{simpletyping}

This section initializes all of our registers.  The first two lines are standard function
stuff.  The next move pulls the size of the memory to allocate off of the stack.  This is
our function parameter.  Notice that we used \icode{ST\_MEM\_SIZE} instead of the
number 8.  This is to make our code more readable.  I used the prefix \icode{ST}
because it is a stack offset.  You don't have to do this, I do this just so I know which
symbols refer to stack offsets.  After that, I move the beginning heap address and the 
end of the heap (current break) into registers.  I am now ready to do processing.

The next section is marked \icode{alloca\_loop\_begin}.  A \emph{loop}
is a section of code repeated many times in a row until certain conditions occur.  In this
case we are going to loop until we either find an open memory segment or determine that
we need more memory.  Our first statements check for needing more memory.

\begin{simpletyping}
\begin{lstlisting}
	cmpl {\ebxBare}, {\eaxBare}
	je   move\_break
\end{lstlisting}
\end{simpletyping}

\icode{{\eaxBare}} holds the current memory segment being examined, and \icode{{\ebxBare}}
holds the location past the current break.  Therefore, if this condition occurs, we need more 
memory to allocate this space.  Notice, too, that this is the case for the first call after
\icode{allocate\_init}.  So, let's skip down to \icode{move\_break} and
see what happens there.

\begin{simpletyping}
\begin{lstlisting}
move\_break:
	addl  \$HEADER\_SIZE, {\ebxBare}
	addl  {\ecxBare}, {\ebxBare}
	pushl {\eaxBare}
	pushl {\ecxBare}
	pushl {\ebxBare}
	movl  \$BRK, {\eaxBare}
	int   \$LINUX\_SYSCALL
\end{lstlisting}
\end{simpletyping}

So, when we reach this point in the code, \icode{{\ebxBare}} holds where we want the next
segment of memory to be.  The size should be the size requested plus the size of our headers.  So,
we add those numbers to \icode{{\ebxBare}}, and that's where we want the program break to be.
We then push all the registers we want to save on the stack, and call the break system call. After 
that we check for errors

\begin{simpletyping}
\begin{lstlisting}
	cmpl  \$0, {\eaxBare}
	je    error
\end{lstlisting}
\end{simpletyping}

Afterwards we pop the registers back off the stack, mark the memory as unavailable, record
the size of the memory, and make sure \icode{{\eaxBare}} points to the start of usable
memory (after the headers).

\begin{simpletyping}
\begin{lstlisting}
	popl  {\ebxBare}
	popl  {\ecxBare}
	popl  {\eaxBare}
	movl  \$UNAVAILABLE, HDR\_AVAIL\_OFFSET({\eaxBare})
	movl  {\ecxBare}, HDR\_SIZE\_OFFSET({\eaxBare})
	addl  \$HEADER\_SIZE, {\eaxBare}
\end{lstlisting}
\end{simpletyping}

Then we store the new program break and return

\begin{simpletyping}
\begin{lstlisting}
	movl  {\ebxBare}, current\_break
	movl  {\ebpBare}, {\espBare}
	popl  {\ebpBare}
	ret
\end{lstlisting}
\end{simpletyping}

The \icode{error} code just returns 0 in \icode{{\eaxBare}}, so we won't 
discuss it.

So let's look at the rest of the loop.  What happens if the current memory being looked at isn't
past the end?  Well, let's look.

\begin{simpletyping}
\begin{lstlisting}
	movl HDR\_SIZE\_OFFSET({\eaxBare}), {\edxBare}
	cmpl \$UNAVAILABLE, HDR\_AVAIL\_OFFSET({\eaxBare})
	je   next\_location
\end{lstlisting}
\end{simpletyping}

First, we grab the size of the memory segment and put it in \icode{{\edxBare}}.
Then, we look at the available flag to see if it is set to \icode{UNAVAILABLE}.
If so, that means that memory is in use, so we'll have to skip over it.  So, if
the available flag is set to \icode{UNAVAILABLE}, you go to the code
labeled \icode{next\_location}.  If the available flag is set to
\icode{AVAILABLE}, then we keep on going.  This is known as 
\emph{falling through}, because we didn't test for this condition and
jump to another location - this is the default.  We didn't have to jump here, it is
just the next instruction.  

So, let's say that the space was available, and so we fall through.  Then we check to
see if this space is big enough to hold the requested amount of memory.  The size of
this segment is being held in \icode{{\edxBare}}, so we do

\begin{simpletyping}
\begin{lstlisting}
	cmpl  {\edxBare}, {\ecxBare}
	jle   allocate\_here
\end{lstlisting}
\end{simpletyping}

So, if the requested size is less than or equal to the current segment size, we
can use this block.  It doesn't matter if the current segment is larger than requested,
because the extra space will just be unused.  So, let's jump down to 
\icode{allocate\_here} and see what happens there -

\begin{simpletyping}
\begin{lstlisting}
	movl  \$UNAVAILABLE, HDR\_AVAIL\_OFFSET({\eaxBare})
	addl  \$HEADER\_SIZE, {\eaxBare}
	movl  {\ebpBare}, {\espBare}
	popl  {\ebpBare}
	ret
\end{lstlisting}
\end{simpletyping}

So, we mark the memory as being unavailable, move \icode{{\eaxBare}} past the header,
and use it as the return value for the function.

Okay, so let's say the segment wasn't big enough.  What then?  Well, we fall through
again, to the code labeled \icode{next\_location}.  This section of code
is used both for falling through and for jumping to any time that we figure out that
the current memory segment won't work for allocating memory.  All it does is
advance \icode{{\eaxBare}} to the next possible memory segment, and go back
to the beginning of the loop.   Remember that \icode{{\edxBare}} is holding
the size of the memory segment, and \icode{HEADER\_SIZE} is the symbol
for the size of the memory segment's header.  So we have

\begin{simpletyping}
\begin{lstlisting}
	addl  \$HEADER\_SIZE, {\eaxBare}
	addl  {\edxBare}, {\eaxBare}
	jmp   alloc\_loop\_begin
\end{lstlisting}
\end{simpletyping}

And the function runs another loop.  Now, whenever you have a loop, you must make sure that
it will \emph{always} end.  In our case, we have the following possibilities:

\begin{itemize}
\item We will reach the end of the heap 
\item We will find a memory segment that's available and large enough 
\item We will go to the next location 
\end{itemize}

The first two items are conditions that will cause the loop to end.  The third one
will keep it going.  This loop will always end.  Even if we never find an open segment, 
we will eventually reach the end of the heap.  Whenever you write a loop, you must
always make sure it ends, or else the computer will waste all of its time there, and
you'll have to terminate your program.   This is called an \emph{infinite loop},
because it could go on forever without stopping.

\section{The \icode{deallocate} function}

The \icode{deallocate} function is much easier than the allocate one.
That's because it doesn't have to do any searching at all.  It can just mark
the current memory segment as \icode{AVAILABLE}, and \icode{allocate}
will find it next time it is run.   So we have

\begin{simpletyping}
\begin{lstlisting}
	movl  ST\_MEMORY\_SEG({\espBare}), {\eaxBare}
	subl  \$HEADER\_SIZE, {\eaxBare}
	movl  \$AVAILABLE, HDR\_AVAIL\_OFFSET({\eaxBare})
	ret
\end{lstlisting}
\end{simpletyping}

In this function, we don't have to save \icode{{\ebpBare}} or \icode{{\espBare}}
since we're not changing them, nor do we have to restore them at the end.  All we're
doing is reading the address of the memory segment from the stack, backing up to the
beginning of the header, and marking the segment as available.  This function has no
return value, so we don't care what we leave in \icode{{\eaxBare}}.

\section{Performance Issues and Other Problems}

Okay, so we have our nice little memory manager.  It's a very simplistic one.  Most memory
managers are much more complex.  Ours was simple so you could see the basics of what
a memory manager has to deal with.  Now, our memory manager does work, it just doesn't
do so optimally.  Before you read the next paragraph, try to think about what the
problems with it might be.

Okay, the biggest problem here is speed.  Now, if there are only a few allocations made,
then speed won't be a big issue.  But think about what happens if you make a thousand
allocations.  On allocation number 1000, you have to search through 999 memory segments
to find that you have to request more memory.  As you can see, that's getting pretty
slow.  In addition, remember that Linux can keep pages of memory on disk instead of in
memory.  So, since you have to go through every piece of memory, that means that Linux
has to load every part of memory from disk to check to see if its available.  You can
see how this could get really, really slow.\footnote{This is why adding more
memory to your computer makes it run faster.  The more memory your computer has, the
less it puts on disk, so it doesn't have to always be interrupting your programs to
retreive pages off the disk.}  This method is said to run in 
\emph{linear} time, which means that every element you have to
manage makes your program take longer.   A program that runs in \emph{constant}
time takes the same amount of time no matter how many elements you are managing.
Take the \icode{deallocate} function, for instance.  It only runs 4 instructions,
no matter how many elements we are managing, or where they are in memory.  In fact, although
our \icode{allocate} function is one of the slowest of all memory managers,
the \icode{deallocate} function is one of the fastest.  Later, we will see
how to improve \icode{allocate} considerably, without slowing down
\icode{deallocate} too much.

Another performance problem is the number of times we're calling the break system call.
System calls take a long time.  They aren't like functions, because the processor has
to switch modes.  Your program isn't allowed to map itself memory, but the Linux kernel is.  
So, the processor has to switch into \emph{kernel mode}, then it maps the
memory, and then switches back to \emph{user mode}.  This is also called
a \emph{context switch}.  This takes a long time because although your
program looks at its virtual memory, Linux looks at the physical memory.  Therefore,
the processor has to forget all of its page mappings.  All of this takes a lot of time.
So, you should avoid calling the kernel unless you really need to.  The problem that we
have is that we aren't recording where Linux actually sets the break.  In our previous
discussion, we mentioned that Linux might actually set the break past where we requested
it.  If we wanted to save time, we should record that location in \icode{move\_break},
and the next time we ask for memory, look to see if the break is already where we need it.
Along the same lines, it might be wise to always ask for a lot more memory than we really
need, in order to reduce the number of times we have to call the break system call.  We
just have to remember that Linux has to map everything, even if we don't use it, so we
don't want to waste too many resources.  You will find that most things in programming
are about balances.  Do we want it to go faster or use less memory?  Do we want an exact
answer in a few hours, or an approximate one in a few minutes?  Do we need 
\icode{allocate} or \icode{deallocate} to be faster?  For example,
let's say that our program has three times as many allocations as deallocations, and 
then at the end it deallocates everything it hasn't used.  In that case, we need 
\icode{allocate} to be as fast as possible, because it's used three times
as often.  Decisions like this characterize programming.

Another problem we have is that if we are looking for a 5-byte segment of memory, and
the first open one we come to is 1000 bytes, we will simply mark the whole thing
as allocated and return it.  This leaves 995 bytes of unused, but allocated, memory.
It would be nice in such situations to break it apart so the other 995 bytes can be
used later.  It would also be nice to combine consecutive free spaces when looking
for large allocations.

A potentially bigger problem that we have is that we assume that we are the only
program that can set the break.  In many programs, there is more than one memory
manager.  Also, there are other reasons to map memory that we will see in a later
chapter.% XREF
  Both of these things will break using this memory manager, because it
assumes that it has all of free memory.  Trace through the program and see what kind
of problems you might run into if another function moved the break between 
\icode{allocate}s and used the memory?  \icode{allocate} would
have no idea, and just write over it.  That would suck.

 

Finally, we have a problem that we have unrestricted access to global variables, namely
\icode{heap\_begin} and \icode{current\_break}.  Now, 
\icode{heap\_begin} isn't a problem because it is set once and then only read.
However, \icode{current\_break} changes quite often.  Later, we will see
cases where you might be in \icode{allocate} when you need to call
\icode{allocate} again because of an external event.  If the two 
\icode{allocate}s are both trying to modify \icode{current\_break}, 
it could be disasterous.  If you are totally confused by this, that's okay.  I'm just
warning you about later chapters.  Just be aware that you should avoid using global
variables as much as possible.  In this book, we will use them a decent amount because
the generally give shorter, simpler programs - which is good for a book, but not so good
for real life.