% $Id: justintime.tex,v 1.7 2009-03-02 15:22:20 potyra Exp $
%
% Copyright (C) 2003-2009 FAUmachine Team <info@faumachine.org>.
% This program is free software. You can redistribute it and/or modify it
% under the terms of the GNU General Public License, either version 2 of
% the License, or (at your option) any later version. See COPYING.

\documentclass[a4paper,10pt]{article}
\usepackage{german,epsfig}
% \parindent0pt

\title{FAUmachine Just-In-Time Compiler}
\author{Volkmar Sieh \\{\tt Volkmar.Sieh@informatik.uni-erlangen.de}}

\begin{document}
\maketitle
\tableofcontents

%---------------------
\section{Introduction}
%---------------------

...

%-----------------
\section{Overview}
%-----------------

The simulator needs some registers and some memory for simulation.
Which registers and which part of memory is used is decribed in
section XXXXX.

Most of the code can be executed without any change. Nevertheless some
code must be changed just-in-time to allow execution in user-mode.
Section XXXXX describes how this transformation should be done.

This code transformation has to be done every time new code has
to be executed. This leads to questions when to compile new
instructions, how many instructions should be compiled at once,
what code to remove and so on. Section XXXXX deals with these questions.

Data structures used by the just-in-time compiler are described in
section XXXXX.

%------------------------------
\section{Register/Memory Usage}
%------------------------------

Segment registers \%fs and \%gs are use by simulator itself. All
other (user writeable) registers (\%eax, \%ebx, \%ecx, \%edx, \%edi,
\%esi, \%ebp, \%esp, \%cs, \%ds, \%es, \%ss) are used in the standard
way.

\%fs will be used by the simulator if \%fs or \%gs is used by user code.
\%gs allways contains the segment selector of a data segment 0-4 GByte.

%----------------------------
\section{Code Transformation}
%----------------------------

Most of the code can be executed without any change. Some instructions
can be modified easily such that an in-place-replacement seems
reasonable. Nevertheless all code must be copied from the original
location to some kind of cache to allow code modifications (see
subsection XXXXX).

Some instructions (see subsection XXXXX) will get a prefix which is a
jump into the simulator itself as they are too complicated to be
transformed into a small number of different instructions.

Instructions affecting the control-flow must be changed to reflect new
target addresses and to correctly push/pop return addresses on stack.
See subsection XXXXX for more information.

At the end of all compiled code the {\tt compile} subroutine of the
simulator must be called. See subsection XXXXX for information on
these subroutine calls.

Subsection XXXXX shows some examples of modified code.

\subsection{Simple Code Modification}
%------------------------------------

Code using the \%fs or \%gs prefix must be replaced because the
registers are already used by the simulator.

It might be modified very simply:
\begin{verbatim}
    xyz %fs:ea
\end{verbatim}
should be replaced by
\begin{verbatim}
    movw %gs:fs, %fs
    xyz  %fs:ea
\end{verbatim}

Similar:
\begin{verbatim}
    xyz %gs:ea
\end{verbatim}
should be replaced by
\begin{verbatim}
    movw %gs:gs, %fs
    xyz  %fs:ea
\end{verbatim}

% \begin{verbatim}
% If running in real-mode:
% Doesn't work - FIXME VOSSI
%     xyz	%cs:ea			movw	%cs, %fs
% 				xyz	%fs:ea
% \end{verbatim}

\subsection{Simulator Calls}
%---------------------------

All instructions which
\begin{itemize}
\item save or load segment selectors
	(e.g. {\tt pushw \%ds; movw \%ax, \%es; lss \%esp, stack})
\item have different semantics in user-mode and supervisor mode
	(e.g. {\tt pushf, popf})
\item are priviledged instructions
	(e.g. {\tt movl \%eax, \%cr3; cli})
\end{itemize}
must be modified. These more complicated instructions have to be
simulated. They will be compiled by replacing them with

\begin{verbatim}
x:  movl $x, %gs:eip
    jmp  simulator
\end{verbatim}

Example:

\begin{verbatim}
    pushf
\end{verbatim}

will be replaced by

\begin{verbatim}
x:  movl $x, %gs:eip
    jmp  simulator
\end{verbatim}

Using the address saved in \%gs:eip the simulator can determine
the instruction, simulate it and can return to the next instruction
following the simulated one.

The following is a list of instructions which must be simulated:

\begin{itemize}
\item movw \%?s, ea
\item movw ea, \%?s
\item pushw \%?s
\item popw \%?s
\item lcall *
\item lret
\item ljmp *
\item l?s \%reg, ea
\item sti
\item cli
\item pushf
\item popf
\item iret
\item in?
\item ins?
\item out?
\item outs?
\item *	\%cs:* /* if running in real-mode */
\item int *
\item rdtsc
\item lmsr
\item smsr
\item rdmsr
\item wrmsr
\item rdpmc
\item cpuid
\item lfence
\item mfence
\item rep nop
\item hlt
\item lgdt
\item sgdt
\item lldt
\item sldt
\item lidt
\item sidt
\item str
\item ltr
\item invlpg
\item wbinvd
\item clts
\item mov *,\%cr?
\item mov \%cr?,*
\item mov *,\%db?
\item mov \%db?,*
\end{itemize}

\subsection{Control-flow Instructions}
%-------------------------------------

All instructions modifying the control flow must be checked and
compiled correctly.

There are two strategies:

\begin{itemize}
\item Replace target addresses.
\item Stop before the call, ret, or jump instruction and simulate it.
\end{itemize}

If jump addresses are known at compile-time we should replace the
addresses by the new addresses. This is fairly simple and will give
no performance penalty.

The more complicated case is when the addresses are not known at
compile-time (e.g. during {\tt call}, {\tt ret}, {\tt jmp *xx}).
We must not execute a standard {\tt call} instruction because it will
push a modified return address onto the stack. This bad address
might be seen by the subroutine called.

Therefore we should simulate all such instructions. Because
these instructions will be called very often any optimization is
welcome. This optimization might be done by using a different
simulator call:

\begin{verbatim}
x:  movl $x, %gs:eip
    jmp  control_flow
    ...
\end{verbatim}

Example:
\begin{verbatim}
    call func
\end{verbatim}
should be replaced by
\begin{verbatim}
x:  movl $x, %gs:eip
    jmp  control_flow
    call func
\end{verbatim}

\subsection{End of Compiled Code}
%------------------------------------------

There might be a chance that there is a huge basic block in user code
not containing any simulator call. The block might be that big that the
compiled code doesn't fit into one cache line. This might happen if
the original code has a programming error leading to execution of bad
code (e.g. data).

In this case a jump instruction can jump to the next cache line
containing the following of the compiled code.

\subsection{Examples}
%--------------------

Original code:
\begin{verbatim}
    x
    ...
    y
    z
\end{verbatim}

Cache line 1:
\begin{verbatim}
    x
    ...
    y
    jmp next
\end{verbatim}

Cache line 2:
\begin{verbatim}
next:
    z
\end{verbatim}

%-----------------------
\section{Compiling Code}
%-----------------------

There are several questions:
\begin{itemize}
\item When do we have to load and compile code?
\item How many and which instructions should we load and compile?
\item When do we have to throw away compiled code?
\item What code should be thrown away?
\end{itemize}

\subsection{When do we have to load and compile code?}
%-----------------------------------------------------

We have to load and compile code (at least one instruction) if we
want to continue simulation. If we return from the simulation of one
instruction we return to compiled code. There must be at least one
executable instruction in the buffer.

\subsection{How many instructions should be loaded and compiled?}
%----------------------------------------------------------------

There might be several different strategies:

Load and compile
\begin{itemize}
\item exactly one instruction
\item a stream of instructions up to the next control flow instruction
	with special address ({\tt call}, {\tt ret}, {\tt iret}, or
	{\tt jmp *} instruction) or up to the next special (prefixed)
	instruction
\item one basic block (up to the next jump, call or conditional branch
	instruction)
\item one procedure (up to the next {\tt ret} or {\tt iret} instruction)
\item as many instruction as we have space in buffer
\end{itemize}

Different strategies will lead to different overhead:

If we only load an compile one instruction we don't load any
instruction which is not really needed. On the other hand we have to
call the simulator very often to load next instructions.

Filling the buffer with instructions may lead to loading of many
instructions not executed.

\subsection{When do we have to throw away code?}
%-----------------------------------------------

We have to throw away compiled code if the real code is modified
somehow. This has to be detected. It might be detected by changing
access rights of the pages containing the real code. Pages may be
set to be read-only in case we read any byte of an instruction out
of the page. Any write access to that page later on will lead to a
page-fault. In the page-fault handler we can throw away the
pre-compiled code of that page and set the read-write flag again.

This detection is not needed in case we only load and compile exactly
one instruction and throw it away after execution.

The other case in which we must flush pre-compiled code is when the
buffer gets full. Then we have to free code compiled previously.

\subsection{What code should be thrown away?}
%--------------------------------------------

We can throw away {\em any} code as we can reload it later if it is
used again. But of cause we should throw away that code, that is not
used any longer. This seems to be difficult to decide.

So in the first step it should be ok to implement any strategie. A
simple but nevertheless good strategie seems to be the strategie
removing the oldest code in cache.

%------------------------
\section{Data Structures}
%------------------------

The data used by the just-in-time module can be divided into two parts.
First there's a cache with {\tt CACHE\_LINES} cache lines where code
is compiled into. The other part is an array of {\tt CACHE\_LINES}
records containing informations about all these cache lines.
\begin{verbatim}
struct {
    unsigned char cache[N][CACHE_LINE_SIZE];
    struct cache_info cache_info[N];
};
\end{verbatim}

All cache lines have the same size ({\tt CACHE\_LINE\_SIZE}). It should
be a power of 2 to speed up calculation of real-eip / cache-eip.

Cache line info is stored in records of the following type:
\begin{verbatim}
struct cache_info {
    unsigned long eip;
    unsigned long len;

    struct cache_info *hash_next;
    struct cache_info *lru_next;
    struct cache_info *ref1_first;
    struct cache_info *ref2_first;
    struct cache_info *ref1_next;
    struct cache_info *ref2_next;
};
\end{verbatim}

{\tt eip} is the original address of the first instruction in cache.
It is used for calculation the hash of the record (see below).

The length of the cache line is given by the {\tt len} variable with
the following semantics:

Non-modified instructions of length {\tt N} will be counted with {\tt N}.
Only one modified instruction will be in one cache line as last
instruction. This instruction (original length {\tt M} bytes) will
only count with 1 byte. Jumps to another cache line at the end of a
cache line will {\em not} be counted. Same with fetch instructions at
the end of a cache line.

{\tt hash\_next} is used to find cache lines containing code for a given
eip quickly. The hash function is
\begin{verbatim}
unsigned long hash(unsigned long eip)
{
    return (eip / CACHE_LINE_SIZE) % HASHSIZE;
}
\end{verbatim}

{\tt lru\_next} is a pointer to the next cache line to be re-used in case
of running out of cache lines for new compiled code.

Every cache line can reference at most two following cache lines. This is
when one cache line ends with a {\tt jcc} instruction which directs
control flow to at most two different locations.
Referencing cache lines are stored using two single linked lists
({\tt ref1\_first}, {\tt ref1\_next} and {\tt ref2\_first},
{\tt ref2\_next}). If a cache line references itself this is not stored
in these lists.

%------------------
\section{Simulator}
%------------------

Simulator entry:

\begin{verbatim}
simulator:
    /*
     * Switch stack.
     */
    /* Save program stack. */
    /* movw %ss, %gs:ss */	/* No need to save. Cannot be changed... */
    movl %esp, %gs:esp

    /* Setup simulator stack. */
    movw %gs:ss_sim, %ss
    movl %gs:esp_sim, %esp

    /*
     * Switch data segments.
     */
    /* Save program data segments. */
    /* movw %ds, %gs:ds */ /* No need to save. Cannot be changed... */
    /* movw %es, %gs:es */
    /* movw %fs, %gs:fs */ /* No need to save. Will be reloaded... */
    /* movw %gs, %gs:gs */

    /* Load simulator data segments. */
    movw %gs:ds_sim, %ds
    movw %gs:es_sim, %es
    /* movw %gs:fs_sim, %fs */ /* Not used. */
    /* movw %gs:gs_sim, %gs */

    /*
     * Save registers.
     */
    pushfl
    popl eflags
    movl %eax, eax
    movl %ebx, ebx
    movl %ecx, ecx
    movl %edx, edx
    movl %edi, edi
    movl %esi, esi
    movl %ebp, ebp

    /*
     * Do simulation...
     */
    movl %esp, %eax
    pushl %eax
    call sim
    addl $4, %esp

    /*
     * Restore registers.
     */
    movl ebp, %ebp
    movl esi, %esi
    movl edi, %edi
    movl edx, %edx
    movl ecx, %ecx
    movl ebx, %ebx
    movl eax, %eax
    pushl eflags
    popfl

    /*
     * Switch data segments.
     */
    movw %gs:es, %es
    movw %gs:ds, %ds
    /* movw %gs:fs, %fs */ /* Will be reloaded before use. */
    /* movw %gs:gs, %gs */

    /*
     * Switch stack.
     */
    movl %gs:esp, %esp
    movw %gs:ss, %ss

    /* Return. */
    ljmp *%gs:cs_sim:%gs:eip_sim
\end{verbatim}

\end{document}