Commits

Stéphane GALLAND committed f879cb1

First version of the chapter 5.

Comments (0)

Files changed (20)

.autolatex_project.cfg

 ; Config::Simple 4.59
-; Thu Jan  2 17:57:25 2014
+; Wed Jan  8 23:18:06 2014
 
 [generation]
 main file=LO46.tex
 generate images=true
-image directory=imgs/all:imgs/chapter0:imgs/chapter1:imgs/chapter2:imgs/chapter3:imgs/chapter4:imgs/appendix
+image directory=imgs/all:imgs/chapter0:imgs/chapter1:imgs/chapter2:imgs/chapter3:imgs/chapter4:imgs/chapter5:imgs/appendix
 
 
 \usepackage{listings}
 \usepackage{algorithm2e}
 
-\graphicspath{{./imgs/all/},{./imgs/chapter0/},{./imgs/chapter1/},{./imgs/chapter2/},{./imgs/chapter3/},{./imgs/chapter4/},{./imgs/appendix/}}
+\graphicspath{{./imgs/all/},{./imgs/chapter0/},{./imgs/chapter1/},{./imgs/chapter2/},{./imgs/chapter3/},{./imgs/chapter4/},{./imgs/chapter5/},{./imgs/appendix/}}
 
 \title{Compilation and Language Theory}
 \subtitle{2$^\text{nd}$ edition}
 
 %\input{chapters/chapter3}
 
-\input{chapters/chapter4}
+%\input{chapters/chapter4}
 
-%\input{chapters/chapter5}
+\input{chapters/chapter5}
 
-\input{chapters/appendix}
+%\input{chapters/appendix}
 
 \end{document}

chapters/chapter5.tex

-\part[author={Stéphane GALLAND}]{Runtime Environments}
-\label{chap:runtime_environments}
+\part[author={Stéphane GALLAND}]{run-time Environments}
+\label{chap:run-time_environments}
 
 \tableofcontentslide
 
 \section{Introduction}
 
+\begin{frame}{Introduction}
+	\begin{itemize}
+	\item A compiler must implement the abstractions embodied in the source-language definition.
+	\vfill
+	\item \emph{The compiler must cooperate with the operating system and other systems software to support these abstracts on the target machine.}
+	\vfill
+	\item To do so, the compiler creates and manages a \Emph{run-time environment} in which it assumes its target programs are being executed.
+	\vfill
+	\item \alert{This chapter presents the key points of the run-time environment:}
+		\begin{enumerate}
+		\item Management of the Heap,
+		\item Management of the Stack,
+		\item Dynamic Memory Deallocation.
+		\end{enumerate}
+	\end{itemize}
+\end{frame}
+
+\section{Data Storage}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/show/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\begin{frame}{Storage Organization}
+	\begin{itemize}
+	\item The target program runs in its own \emph{logical address space} in which each value has a location.
+	\item The organization and management of this logical address space is shared between: \begin{itemize}
+		\item the compiler,
+		\item the operating system,
+		\item the target machine.
+		\end{itemize}
+	\vfill
+	\item The operating system maps the logical addresses into physical addresses.
+	\item When defined, a \emph{virtual machine} is a program that is representing the operating system and the target machine into an abstract and platform-independent machine.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}[t]{Structure of the Logicial Address Space}
+	\begin{itemize}
+	\item In the run-time environment, the logical address space has a structure; typically:
+	\end{itemize}
+	\vfill
+	\begin{columns}
+		\begin{column}{.3\linewidth}
+			\raisebox{-.5\height}{\includeanimatedfigure[width=\linewidth]{address_space_structure}}
+		\end{column}
+		\begin{column}{.7\linewidth}\begin{small}
+			\only<2>{\begin{itemize}
+				\item The compiler can place the executable target code in a statically determined area, named Code.
+				\item This area contains the binary representations of the instructions to execute.
+				\item The format of the code depends on the target machine: Intel binary assembler, byte code\dots
+				\end{itemize}}
+			\only<3>{\begin{itemize}
+				\item Similarly, the size of some program data may be known at compile time.
+				\item The area where these data are stored in named Static area, usually put just after the Code area.
+				\item \inlineexamples{string literals, global constants and variables, information related to garbage collection\dots}
+				\item The addresses of the static data are directly put in the code.
+				\end{itemize}}
+			\only<4>{\begin{itemize}
+				\item The stack is used to store data structures called activation records.
+				\item Activation records are generated during the procedure/function calls (explained later).
+				\item Basically, each record contains the status of the machine: ordinal counter, machine registers, and data whose lifetimes are the same as the activation time (usually local variables).
+				\end{itemize}}
+			\only<5>{\begin{itemize}
+				\item Many languages allow the programmer to allocate and deallocate data under program control (malloc, new\dots)
+				\item The heap is used to manage this kind of long-lived data.
+				\end{itemize}}
+			\only<6>{\begin{itemize}
+				\item The heap and the stack are growing up and consume the free memory space between them.
+				\item When the stack cannot grow up, the classical ``stack overflow'' error is fired.
+				\item When the heap cannot grow up, the classical ``out of memory'' error is fired.
+				\end{itemize}}
+			\end{small}
+		\end{column}
+	\end{columns}
+\end{frame}
+
+\begin{frame}{Static vs. Dynamic Storage Allocation}
+	The layout and allocation of data to memory locations in the run-time environment are key issues in storage management.
+	\vfill
+	\begin{block}{Static Storage Allocation}
+		It is made \emph{by the compiler} looking only at the text of the program, not at what the program does when it executes.
+	\end{block}
+	\vfill
+	\begin{block}{Dynamic Storage Allocation}
+		\begin{itemize}
+		\item It is made only \emph{while the program is running}.
+		\item Many compilers use a combination of the strategies explained in the following slide for dynamic storage allocation.
+		\end{itemize}
+	\end{block}
+\end{frame}
+
+\begin{frame}{Strategies for Dynamic Storage Allocation}
+	\begin{block}{Stack Storage}
+		\begin{itemize}
+		\item Names local to a procedure are allocated space \emph{on a stack}.
+		\item The stack supports the normal call/return policy for procedures.
+		\end{itemize}
+	\end{block}
+	\vfill
+	\begin{block}{Heap Storage}
+		\begin{description}
+		\item Data that may outlive the call to the procedure that created it is usually allocated \emph{on a ``heap''} of reusable storage.
+		\item The heap is an area of virtual memory that allows data to obtain and release storage.
+		\item[Garbage collection] the run-time environment detects useless data in heap and releases them.
+		\end{description}
+	\end{block}
+\end{frame}
+
+\section{Stack management}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/show/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\subsection{Stack allocation}
+
+
+\subsubsection{Introduction}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/show/hide/hide}]
+
+\begin{frame}{Stack Allocation}
+	\begin{description}
+	\item Compilers that use procedures, functions, or methods as units manage a part of their run-time memory as a stack.
+	\item[Note] procedure will be used as a generic term for procedure, function and method.
+	\vfill
+	\item Each time a procedure is called:
+		\begin{itemize}
+		\item space for its local variables is pushed into a stack.
+		\end{itemize}
+	\item When the procedure terminates:
+		\begin{itemize}
+		\item space is popped off the stack.
+		\end{itemize}
+	\vfill
+	\item The activation of procedure $\equiv$ the call to the procedure.
+	\end{description}
+\end{frame}
+
+\begin{frame}[fragile]{Nested Activation in Time}
+	\begin{small}
+	\alertbox{Stack allocation would not be feasible if procedure calls did not nest in time.}
+	\begin{columns}
+		\begin{column}{.5\linewidth}
+			\begin{itemize}
+			\item If an activation of procedure \code{p} calls procedure \code{q}, then that activation of \code{q} must end before the activation of \code{p} can end.
+			\end{itemize}
+			\includegraphics[width=\linewidth]{nested_activation}
+		\end{column}
+		\begin{column}{.5\linewidth}
+			\begin{lstlisting}[language=C,basicstyle=\Tiny]
+			int a[11];
+			void readArray() {
+			    int i; // read and fill a
+			}
+			int partition(int m, int n) {
+			    // let v, a[m..p-1] < v, a[p]=v, a[p+1..n] >= v
+			    // return p
+			}
+			void quicksort(int m, int n) {
+			    int i;
+			    if (n>m) {
+			        i = partition(m,n);
+			        quicksort(m,i-1);
+			        quicksort(i+1,n);
+			    }
+			}
+			main() {
+			    readArray();
+			    a[0] = -9999;
+			    a[11] = 9999;
+			    quicksort(1,9);
+			}
+			\end{lstlisting}
+		\end{column}
+	\end{columns}
+	\end{small}
+\end{frame}
+
+\begin{frame}[allowframebreaks]{Termination of Nested Activation}
+	Three common cases when \code{p} calls \code{q}:
+	\vspace{1em}
+	\begin{enumerate}
+	\item[Normal] The activation of \code{q} terminates normally. Then in essentially any language, control resumes just after the point of \code{p} at which the call to \code{q} was made.
+	\vspace{1em}
+	\item[Abort] The activation of \code{q}, or some procedure called by \code{q}, either directly or indirectly, aborts.
+\code{p} ends simultaneously with \code{q}.
+	\item[Exception] The activation of \code{q} terminates because of an exception that \code{q} cannot handle. \\
+		Procedure \code{p} may handle the exception: the activation of \code{q} has terminated but \code{p} continues (not necessary where \code{q} was called). \\
+		If \code{p} cannot handle the exception, then this activation of \code{p} terminates at the same time as the activation of \code{q}, and presumably, the exception will be handled by some other open activation of a procedure.
+	\end{enumerate}
+\end{frame}
+
+\subsubsection{Activation tree}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}{Activation Tree}
+	The activations of procedures during the running of an entire program is represented by a tree, named \emph{activation tree}.
+	\vfill
+	\begin{description}
+	\item[Node] an activation;
+	\vfill
+	\item[Root Node] the root is the activation of the ``main'' procedure that initiates the execution of the program.
+	\vfill
+	\item[Child Node] activations of the procedures called by the activation represented by the parent node. The order of the children (from left to right) is the order of the activations.
+	\end{description}
+\end{frame}
+
+\figureslide{Example of Activation Tree}{activation_tree_example}
+
+\subsubsection{Control Stack and Activation record}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}{Control Stack and Activation Record}
+	\begin{itemize}
+	\item Procedure calls and returns are usually managed by a run-time stack called the \emph{control stack}.
+	\vfill
+	\item Each live activation has an \emph{activation record} (or frame) on the control stack.
+	\vfill
+	\item The entire sequence of activation records on the stack corresponding to the path in the activation tree to the activation where control currently resides.
+	\vfill
+	\item \emph{The latter activation has its record at the top of the stack.}
+	\end{itemize}
+\end{frame}
+
+\figureslide{Example of Control Stack}{control_stack_example}
+
+\begin{frame}[t]{Structure of the Activation Record}
+	\begin{itemize}
+	\item The contents of activation records vary with the language being implemented; typically:
+	\end{itemize}
+	\vfill
+	\begin{columns}
+		\begin{column}{.3\linewidth}
+			\raisebox{-.5\height}{\includeanimatedfigure[width=\linewidth]{activation_record_structure}}
+		\end{column}
+		\begin{column}{.7\linewidth}\begin{small}
+			\only<2>{\begin{itemize}
+				\item Temporary values, such as those arising from the evaluation of expressions, in cases where the temporaries cannot be held in registers.
+				\end{itemize}}
+			\only<3>{\begin{itemize}
+				\item Local data belonging to the procedure whose activation record this is.
+				\end{itemize}}
+			\only<4>{\begin{itemize}
+				\item Information about the state of the machine just before the call to the procedure.
+				\item It typically includes:
+					\begin{description}
+					\item[return address] the value of the ordinal counter to which the called procedure must return.
+					\item[Registers] The contents of registers that were used by the calling procedure and that must be restored when the return occurs.
+					\end{description}
+				\end{itemize}}
+			\only<5>{\begin{itemize}
+				\item An ``access link'' may be needed to locate data needed by the called procedure but found elsewhere (in another activation record\dots)
+				\end{itemize}}
+			\only<6>{\begin{itemize}
+				\item A ``control link'' is pointing to the activation record of the caller.
+				\end{itemize}}
+			\only<7>{\begin{itemize}
+				\item Space for the return value of the called function, if any.
+				\item Not all called procedures return a value.
+				\item We may prefer to place that value in a register for efficiency.
+				\end{itemize}}
+			\only<8>{\begin{itemize}
+				\item The actual parameters are given by the caller and used by the callee procedure.
+				\item Commonly, these values are not placed in the activation record but rather in registers, when possible.
+				\end{itemize}}
+			\end{small}
+		\end{column}
+	\end{columns}
+\end{frame}
+
+\subsubsection{Calling sequence}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}{Calling and Return Sequence}
+	\begin{definition}[Calling Sequence]
+		A calling sequence is a \code{code} that allocates an activation record on the stack and enters information into its fields.
+	\end{definition}
+	\begin{definition}[Return Sequence]
+		A return sequence is a \code{code} that deallocates an activation record from the stack and restores the state of the machine.
+	\end{definition}
+	\vfill
+	\alertbox{Calling sequences and the layout of activation records may differ greatly, even among implementations of the same language.}
+	\vfill
+	\begin{itemize}
+	\item The calling sequence is composed of: \begin{itemize}
+		\item Calling procedure (the ``caller''),
+		\item Called procedure (the ``callee'').
+		\end{itemize}
+	\end{itemize}
+\end{frame}
+
+\begin{frame}[t]{Principles of the Calling Sequences}
+	\putat(180,-200){\includeanimatedfigure[width=.4\paperwidth]{calling_sequence_principles}}
+	When designing calling sequences and the layout of the activation records, the following principles are used:
+	\only<1>{\begin{enumerate}
+		\item \emph{Values communicated between caller and callee are generally placed at the beginning of the callee activation record.}
+		\end{enumerate}}
+	\only<2>{\begin{enumerate}
+		\setcounter{enumi}{1}
+		\item \emph{Fixed-length items are placed in the middle of the record.}
+		\end{enumerate}}
+	\only<3>{\begin{enumerate}
+		\setcounter{enumi}{2}
+		\item \emph{Items whose size may not be known early enough are placed at the end of the activation record.}
+		\end{enumerate}}
+	\only<4>{\begin{enumerate}
+		\setcounter{enumi}{3}
+		\item \emph{We must locate the ``top-of-stack'' pointer judiciously.}
+		\end{enumerate}}
+	\vspace{1em}
+	\hspace{2em}\begin{minipage}{.5\linewidth}
+		\only<1>{	\small
+				\nohyphens{The caller can compute the actual parameters and put them at the top of the stack, without the necessity to create the entire record of the callee, and knowing how the callee's record layout is.}
+				\par
+				\nohyphens{The caller knows where to put the return value, relative to its own record.}
+		}
+		\only<2>{	\small
+				\nohyphens{If machine status are standardized, then programs such as debuggers will have an easier time deciphering the stack contents if an error occurs.}
+		}
+		\only<3>{	\small
+				\nohyphens{Most of the variables have a size that can be determined by the compiler. But some cannot (dynamic arrays\dots)}
+				\par
+				\nohyphens{The amount of space needed for temporaries is not known during the first phase of the intermediate code generation.}
+		}
+		\only<4>{	\small
+				\nohyphens{Commonly, it points to the end of the fixed-length fields in the activation record.}
+				\par
+				\nohyphens{The control link points to the ``top-of-stack'' of the previous record.}
+				\par
+				\nohyphens{Fixed-length data can then be accessed by fixed negative offset, and variable-length with a run-time positive offset.}
+		}
+	\end{minipage}
+\end{frame}
+
+\begin{frame}{Typical Calling Sequence}
+	\begin{enumerate}
+	\item The caller evaluates and stores the actual parameters
+	\item The caller stores a return address. \\
+		It stores the old value of the \code{top\_sp} into the callee's activation record. \\
+		It increments \code{top\_sp} to point to the callee activation record.
+	\item The callee saves the register values and other status information.
+	\item The callee initializes its local data and begins execution.
+	\end{enumerate}
+	\putat(-20,-175){\includegraphics[width=2em]{caller_callee}}
+\end{frame}
+
+\begin{frame}{Typical Return Sequence}
+	\begin{enumerate}
+	\item The callee places the return value next to the parameters.
+	\item Using information in the machine-status fields, the callee restores \code{top\_sp} and other registers. \\
+		It branches to the return address that the caller placed in the status field.
+	\item Although \code{top\_sp} has been decremented, the caller knows where the return value is, relative to the current value of \code{top\_sp}. \\
+		The caller may use that value.
+	\end{enumerate}
+	\putat(-20,-172){\includegraphics[width=2em]{callee_caller}}
+\end{frame}
+
+\subsubsection{Variable-length data on the stack}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}{Variable-length Data}
+	\begin{itemize}
+	\item Programs contain a lot of data whose \Emph{sizes are known at run-time}; but which are local to a procedure.
+	\item Because \Emph{they are local to the procedure}, they may be allocated on the stack.
+	\vfill
+	\item In most of the modern languages, these objects are allocated in the \emph{heap}.
+	\item However, it is also possible to allocate objects, arrays, or other data structures of unknown size on the \emph{stack}.
+	\end{itemize}
+	\vfill
+	\begin{block}{Why on the stack?}
+		Avoiding the expense of garbage collecting the space allocated for the variable-length data.
+	\end{block}
+\end{frame}
+
+\pgfdeclareimage[width=.3\paperwidth]{stack_allocation_strategy}{imgs/chapter5/stack_allocation_strategy}
+
+\begin{frame}[fragile]{Allocation Strategy}
+	\putat(180,-140){\pgfuseimage{stack_allocation_strategy}}
+	\begin{itemize}
+	\item Below, the example of programs in C99 and C\# in which a local array is declared. Its size depends on the value of the procedure parameter.
+	\end{itemize}
+	\begin{minipage}{.5\linewidth}
+	\begin{itemize}
+	\item The common strategy is to:
+		\begin{enumerate}
+		\item Allocate the arrays at the end of the record.
+		\item Put pointers to the allocated regions in the local data.
+		\end{enumerate}
+	\end{itemize}
+	\end{minipage} \\
+	\vspace{2em}
+	\begin{columns}
+		\begin{column}{.5\linewidth}
+			\begin{lstlisting}[language=c]
+			/* C99 */
+			void myFunction(int n) {
+			   float localArray[n];
+			   /* Do something with array */
+			}
+			\end{lstlisting}
+		\end{column}
+		\begin{column}{.5\linewidth}
+			\begin{lstlisting}[language=c]
+			/* C# */
+			unsafe void myFunction(int n) {
+			   int* localArray = stackalloc int[size];
+			   /* Do something with array */
+			}
+			\end{lstlisting}
+		\end{column}
+	\end{columns}
+\end{frame}
+
+\begin{frame}{Pointers \code{top} and \code{top\_sp}}
+	\begin{itemize}
+	\item Two pointers are used:
+		\begin{description}
+		\item[top] marks the actual top of the stack. It points to the position at which the next activation record will begin.
+		\item[top\_sp] is used to find local, fixed-length fields of the top activation record.
+		\end{description}
+	\vfill
+	\item When returning from a call: \\
+		\code{top $\leftarrow$ top\_sp - length(fixed\_record\_part)}
+	\end{itemize}
+	\vfill
+	\begin{center}
+		\pgfuseimage{stack_allocation_strategy}
+	\end{center}
+\end{frame}
+
+\subsection{Access to nonlocal data on the stack}
+
+\subsubsection{Introduction}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/show/hide/hide}]
+
+\begin{frame}{Access to Nonlocal Data on the Stack}
+	\begin{itemize}
+	\item This section is devoted to the mechanisms of the procedures to access to their data.
+	\item Focusing on the mechanisms for finding data used within a procedure p but that does not belong to p.
+	\vfill
+	\item First, we study the cases of programs without nested functions.
+	\item Second, we introduces an algorithmic languages that permits to declare nested functions.
+	\end{itemize}
+\end{frame}
+
+\subsubsection{Data access without nested procedure}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}{Data Access Without Nested Procedures}
+	\begin{itemize}
+	\item In languages similar to C, variables are declared:
+		\begin{itemize}
+		\item inside a single function, or
+		\item outside any function (``globally'')
+		\end{itemize}
+	\vfill
+	\item It is impossible to declare a procedure inside the scope of another procedures.
+	\vfill
+	\item In such languages, allocation of storage for, and access to variables is simple:
+		\begin{itemize}
+		\item \emph{Global variables are allocated in the static storage.} The locations remain fixed and are known at compile time.
+		\item \emph{Any other name must be local to the activation at the top of the stack.} The locations are relative to the \code{top\_sp} pointer of the stack.
+		\end{itemize}
+	\end{itemize}
+\end{frame}
+
+\subsubsection{Issues with nested procedures}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}[fragile]{Language with Nested Procedure Declarations}
+	\begin{itemize}
+	\item Many languages enable to declare procedures inside the scope of another procedure (Algol60, Pascal, ML, LISP).
+	\item LISP is a functional language: variables, after initialized cannot change.
+	\end{itemize}
+	\vfill
+	\begin{columns}
+		\begin{column}{.4\linewidth}
+			Factorial Function, non-tail-recursion algorithm. \\
+			\vspace{3em}
+			Factorial Function, tail-recursion algorithm.
+		\end{column}
+		\begin{column}{.6\linewidth}
+			\begin{lstlisting}[language=lisp,basicstyle=\footnotesize]
+			(deffun factorial (n)
+				(if (<= n 1)
+				    1
+				    (* n factorial (- n 1))))
+
+			(deffun factorial (n)
+				(let ((deffun fact (n,acc)
+					      (if (<= n 1) acc
+					          (fact (- n 1) (* n acc))))
+				     (fact n 1)))
+			\end{lstlisting}
+		\end{column}
+	\end{columns}
+\end{frame}
+
+\begin{frame}{Issue with Nested Procedures}
+	\begin{footnotesize}
+	\alertbox{With nested procedure declaration, it is far more complicated to determine the addresses of the names used in the procedure.}
+	\vfill
+	\begin{example}
+		\begin{columns}
+			\begin{column}[t]{.6\linewidth}
+				\begin{itemize}
+				\item Let the procedure \code{g} declared inside the scope of the procedure \code{p}.
+				\item \code{g} is accessing to the variable \code{a}, locally declared in \code{p}.
+				\item It is difficult to determine at compile time where is the variable \code{a} in the stack, because of the recursive calls.
+				\item The address of \code{a} in the stack can be determined only at run-time.
+				\end{itemize}
+			\end{column}
+			\begin{column}[t]{.4\linewidth}
+				\begin{scriptsize}
+				\begin{myprocedure}{p}{n}
+				\Begin{
+					\KwSty{Declare} a \affect n/2\;
+					\KwSty{Procedure} {g()} \\
+					\Begin{
+						\lIf{$n>1$}{p(n-1)\;}
+						\lElseIf{$n=1$}{p(a/2)\;}
+					}
+					g() \;
+				}
+				\end{myprocedure}
+				\end{scriptsize}
+			\end{column}
+		\end{columns}
+	\end{example}
+	\end{footnotesize}
+\end{frame}
+
+\figureslide{Example of the Issue}{nested_procedure_issue}
+
+\subsubsection{Nesting depth}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}{Informal Definition of Nesting Depth}
+	\begin{itemize}
+	\item Let nesting depth $1$ the declaration of a procedure outside another procedure.
+	\item Let nesting depth $2$ the declaration of a procedure inside one other procedure of nesting depth $1$.
+	\item Let nesting depth $n$ the declaration of a procedure inside one other procedure of nesting depth $n-1$.
+	\end{itemize}
+	\begin{columns}
+		\begin{column}{.3\linewidth}
+			\begin{scriptsize}
+			\begin{myprocedure}{p}{n}
+			\Begin{
+				\KwSty{Declare} a \affect n/2\;
+				\KwSty{Procedure} {g()} \\
+				\Begin{
+					\lIf{$n>1$}{p(n-1)\;}
+					\lElseIf{$n=1$}{p(a/2)\;}
+				}
+				g() \;
+			}
+			\end{myprocedure}
+			\end{scriptsize}
+		\end{column}
+		\begin{column}{.35\linewidth}
+			\begin{small}
+			\code{p} has nesting depth $1$. \\
+			\vspace{2em}
+			\code{g} has nesting depth $2$.
+			\end{small}
+		\end{column}
+	\end{columns}
+\end{frame}
+
+\subsubsection{Access links}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}{Access Link}
+	\begin{small}
+	\begin{definition}
+		Access links provide a mean for the implementation of the static scope rule for nested functions.
+	\end{definition}
+	\begin{description}
+	\item If procedure \code{g} is immediately nested in procedure \code{p}; then the access link in any activation of \code{g} points to the most recent activation of \code{p}.
+	\item[Note] nesting depth of \code{p} must be exactly one less than the nesting depth of \code{g}.
+	\end{description}
+	\end{small}
+	\begin{columns}
+		\begin{column}{.5\linewidth}
+			\includegraphics[width=\linewidth]{access_link}
+		\end{column}
+		\begin{column}{.3\linewidth}
+			\begin{tiny}
+			\begin{myprocedure}{p}{n}
+			\Begin{
+				\KwSty{Declare} a \affect n/2\;
+				\KwSty{Procedure} {g()} \\
+				\Begin{
+					\lIf{$n>1$}{p(n-1)\;}
+					\lElseIf{$n=1$}{p(a/2)\;}
+				}
+				g() \;
+			}
+			\end{myprocedure}
+			\end{tiny}
+		\end{column}
+	\end{columns}
+\end{frame}
+
+\begin{frame}{Chain of Access Links}
+	\begin{itemize}
+	\item Access links form a chain from the activation record at the top of the stack to a sequence of activations at progressively lower nesting depths.
+	\vfill
+	\item Along this chain are all the activations whose data and procedures are accessible to the currently executing procedure.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Example of Access Links}
+	\putat(160,-75){\parbox{.5\linewidth}{\normalcolor\mdseries
+		\begin{tiny}
+		\begin{myprocedure}{sqrt}{q}
+		\Begin{
+			\KwSty{Procedure} {babylonian\_algo(a,n)} \\
+			\Begin{
+				\KwSty{Declare} {a}\;
+				b \affect (a + q/a) / 2\;
+				\uIf{n {\textgreater} 0}{
+					\Return {b}\;
+				}
+				\Else{
+					\Return {babylonian\_algo(a,n-1)}\;
+				}
+			}
+			\Return{babylonian\_algo(q/2, 10)}\;
+		}
+		sqrt(5)\;
+		\end{myprocedure}
+		\end{tiny}
+	}}
+	\putat(160,-170){\only<4>{\parbox{.5\linewidth}{\normalcolor\mdseries
+		\small\nohyphens{To access to the value of \code{q}, we know at compile time, that it is reachable after one dereferencing in the access link pointer chain.}
+	}}}
+	\putat(-20,-190){\includeanimatedfigure[width=.5\paperwidth]{access_link_example}}
+\end{frame}
+
+\begin{frame}[t]{Determining the Access Link Target}
+	\begin{small}
+	\begin{itemize}
+	\item Let the procedure \code{q} calling \code{p}.
+	\item Let $N_\alpha$ the nesting depth of $\alpha$.
+	\item Let $D_\beta$ the set of the nesting procedures in which $\beta$ is defined.
+	\end{itemize}
+	\end{small}
+	\begin{block}{First Case}
+		\[ \left( N_p > N_q \right) \Rightarrow \left( q \in D_p \wedge N_p = N_q + 1 \right) \]
+		Then the access link from \code{p} leads to \code{q}.
+	\end{block}
+\end{frame}
+
+\begin{frame}[t]{Determining the Access Link Target}
+	\begin{small}
+	\begin{itemize}
+	\item Let the procedure \code{q} calling \code{p}.
+	\item Let $N_\alpha$ the nesting depth of $\alpha$.
+	\item Let $D_\beta$ the set of the nesting procedures in which $\beta$ is defined.
+	\end{itemize}
+	\end{small}
+	\begin{block}{Second Case}
+		\[ \left( N_p \le N_q \right) \Rightarrow \left( \exists r \; \bigg| \; \begin{pmatrix}
+			r \in D_p \wedge N_p = N_r + 1 \wedge \\
+			r \in D_q \wedge N_r > N_q
+			\end{pmatrix} \right) \]
+		Then \begin{itemize}
+			\item The access link from \code{p} leads to \code{r}.
+			\item There is $N_q - N_p + 1$ access links from \code{q} to \code{r}.
+			\item Include recursive calls, where \code{p} = \code{q}.
+			\end{itemize}
+	\end{block}
+\end{frame}
+
+\begin{frame}[t]{Passing a Procedure as Parameter}
+	\begin{itemize}
+	\item A procedure \code{p} is passed to another procedure \code{q} as a parameter; \code{q} calls its parameter.
+	\end{itemize}
+	\begin{alertblock}{Problem}
+		\begin{itemize}
+		\item If \code{q} does not know the context in which \code{p} appears in the program;
+		\item it is impossible for \code{q} to know how to set the access link for \code{p}.
+		\end{itemize}
+	\end{alertblock}
+	\begin{block}{Solution}
+		\begin{itemize}
+		\item The caller of a procedure with a procedure as parameter must also pass the proper access link to the parameter
+		\item ie. the caller must pass the name and the access link as parameters.
+		\end{itemize}
+	\end{block}
+\end{frame}
+
+\begin{frame}[fragile]{Example of a Procedure Passing as Parameter}
+	\putat(172,-74){\parbox{.5\linewidth}{\normalcolor\mdseries
+		\begin{tiny}
+			{{\def\dash{\raise2.1pt\hbox{\rule{1pt}{0.3pt}}\hspace{1pt}}\begin{tabbing}
+			({\textbf{defun}}\ a(x)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{({\textbf{let}}\ (}({\textbf{defun}}\ b(f)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{}(\dots\ f\ \dots)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{})\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}({\textbf{defun}}\ c(y)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{({\textbf{let}}\ (}({\textbf{defun}}\ d(z)\ (\dots))\ )\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{}\ \ \ \ \ \ (\dots\ (b\ d)\ \dots)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{})\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{})\\
+			\makebox[16pt][l]{}\ \ \ \ \ )\\
+			\makebox[16pt][l]{}\ \ \ \ \ (\dots\ (c\ 1)\ \dots)\\
+			\makebox[16pt][l]{})\\
+			)
+			\end{tabbing}}}
+		\end{tiny}
+	}}
+	\only<1>{\putat(160,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{Function \code{a} is called.}}}}
+	\only<2>{\putat(160,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{Function \code{c} is called.\\According to the first case, access link leads to \code{a}.}}}}
+	\only<3>{\putat(160,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{Function \code{b} is called with the procedure \code{d} as parameter.\\According to the second case, access link leads to \code{a}.\\The context of \code{d} is also passed as parameter.}}}}
+	\only<4>{\putat(160,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{Function \code{d} is called through the parameter \code{f}. The access link is directly taken from the context \textcircledP.}}}}
+	\putat(-20,-190){\includeanimatedfigure[width=.5\paperwidth]{procedure_as_parameter_example}}
+\end{frame}
+
+\subsubsection{Displays}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={show/shaded/hide/hide}]
+
+\begin{frame}{Problem with Access Links}
+	\alertbox{If the nesting depth gets large, we may have to follow long chains of links to reach the data we need.}
+\end{frame}
+
+\begin{frame}{The Display: a Solution to the Access Link Problem}
+	\alertbox*{Use of an auxiliary array \code{d}, called the \emph{display}.}
+	\vfill
+	\begin{itemize}
+	\item A display is a collection (an array) of pointers, one for each nesting depth.
+	\vfill
+	\item At all times, \code{d[i]} is a pointer to the highest activation record on the stack for any procedure at nesting depth \code{i}.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Why Displays?}
+	\begin{itemize}
+	\item If procedure \code{p} is executing, and it needs to access element \code{x} belonging to some procedure \code{q}, we need to look only in \code{d[i]}, where \code{i} is the nesting depth of \code{q}.
+	\vfill
+	\item The compiler knows what \code{i} is, so it can generate code to access \code{x} using \code{d[i]} and the offset of \code{x} from the top of the activation record for \code{q}.
+	\vfill
+	\item The code never needs to follow a long chain of access links.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Maintaining the Displays when Creating Records}
+	\begin{itemize}
+	\item Each time a record is added in the stack, we need to save previous values of display entries.
+	\vfill
+	\item \Emph{If} procedure \code{p} at depth $N_p$ is called, \Emph{and}
+	\item the activation record of \code{p} is not the first on the stack for a procedure at depth $N_p$, \Emph{then}
+	\vfill
+	\item Put the value of \code{d[$N_p$]} in the activation record of \code{p}.
+	\item Set \code{d[$N_p$]} to the activation record of \code{p}.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Maintaining the Displays when Returning from Records}
+	\begin{itemize}
+	\item Each time a record returns, we need to restore previous values of display entries.
+	\vfill
+	\item Set \code{d[$N_p$]} to the value previously stored in the activation record of \code{p}.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}[fragile]{Example of Displays}
+	\putat(172,-74){\parbox{.5\linewidth}{\normalcolor\mdseries
+		\begin{tiny}
+			{{\def\dash{\raise2.1pt\hbox{\rule{1pt}{0.3pt}}\hspace{1pt}}\begin{tabbing}
+			({\textbf{defun}}\ a(x)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{({\textbf{let}}\ (}({\textbf{defun}}\ b(f)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{}(\dots\ f\ \dots)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{})\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}({\textbf{defun}}\ c(y)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{({\textbf{let}}\ (}({\textbf{defun}}\ d(z)\ (\dots))\ )\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{}\ \ \ \ \ \ (\dots\ (b\ d)\ \dots)\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{}\makebox[16pt][l]{})\\
+			\makebox[16pt][l]{}\makebox[16pt][l]{})\\
+			\makebox[16pt][l]{}\ \ \ \ \ )\\
+			\makebox[16pt][l]{}\ \ \ \ \ (\dots\ (c\ 1)\ \dots)\\
+			\makebox[16pt][l]{})\\
+			)
+			\end{tabbing}}}
+		\end{tiny}
+	}}
+	
+	\only<1>{\putat(170,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{
+				The displays are pointing somewhere in the stack. \\
+				Function \code{a} is called. \\
+				Create the record. \\
+				Save \code{d[1]}, which is pointing on a lower activation record.}}}}
+	\only<2>{\putat(170,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{
+				Because \code{d[1]} is not pointing to the record of \code{a}, change \code{d[1]}.}}}}
+	\only<3>{\putat(170,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{
+				The function \code{c} is called. \\
+				Its record is created. \\
+				The previous value of \code{d[2]} is saved.}}}}
+	\only<4>{\putat(170,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{
+				Because the record of \code{c} is not the one pointed by \code{d[2]}, set \code{d[2]} to leads to \code{c}.}}}}
+	\only<5>{\putat(170,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{
+				The function \code{b} is called. \\
+				Save the \code{d[2]}, and set its value to leads to \code{b}.}}}}
+	\only<6>{\putat(170,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{
+				The function \code{d} is called through the parameter \code{f}. \\
+				The displays are updated.}}}}
+	\only<7>{\putat(170,-170){\parbox{.5\linewidth}{\normalcolor\mdseries\small\nohyphens{
+					To obtain the value of \code{x}:
+					\begin{itemize}\normalcolor\mdseries\small
+					\item Because \code{x} is at nesting depth 1, follows \code{d[1]} to reach the right record.
+					\item Read the value of \code{x} in the record.
+					\end{itemize}}}}}
+	\putat(-20,-190){\includeanimatedfigure[width=.5\paperwidth]{display_example}}
+\end{frame}
+
+\section{Heap management}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/show/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\subsection{Introduction}
+
+\begin{frame}{What is the Heap?}
+	\begin{itemize}
+	\item The heap is the portion of the store that is used for data that lives indefinitely, or until the program explicitly deletes it.
+	\vfill
+	\item Modern languages provides dedicated operators for the allocation and deallocation in the heap. For example, \kw{new} and \kw{delete} in C++.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Heap Management}
+	\begin{itemize}
+	\item This section describes the \emph{memory manager}, the subsystem that allocates and deallocates space within the heap.
+	\vfill
+	\item The memory manager is the interface between the application program and the operating system.
+	\vfill
+	\item \emph{Garbage collection} is the process of finding spaces within the heap that are no longer used by the program and can be reallocated. The \emph{garbage collector} is an important subcomponent of the memory manager.
+	\end{itemize}
+\end{frame}
+
+\subsection{Memory manager}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\begin{frame}{Memory Manager}
+	\begin{itemize}
+	\item The memory manager keeps track of all the free space in heap storage at all times.
+	\vfill
+	\item Its two basic functions are:
+		\begin{enumerate}
+		\item allocation,
+		\item deallocation.
+		\end{enumerate}
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Allocation by the Memory Manager}
+	\begin{itemize}
+	\item Produces a chunk of contiguous memory for each variable or object associated to the allocation request.
+	\vfill
+	\item If not enough contiguous space is available for a chunk, it seeks to increase the heap storage space by requesting memory to the operating system.
+	\vfill
+	\item The defragmentation of the heap is generally not implemented.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Deallocation by the Memory Manager}
+	\begin{itemize}
+	\item Returns deallocated space to the pool of free space.
+	\vfill
+	\item The deallocation space may be reused for future allocations.
+	\vfill
+	\item Typically, the memory manager does not return memory to the operating system, even if the program's heap usage drops.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Space Efficiency of the Memory Manager}
+	\begin{block}{Property: Space Efficiency}
+		\begin{itemize}
+		\item A memory manager should minimize the total heap space need by a program.
+		\item Space efficiency is achieved by minimizing the ``fragmentation'' (discussed later).
+		\end{itemize}
+	\end{block}
+\end{frame}
+
+\begin{frame}{Program Efficiency of the Memory Manager}
+	\begin{block}{Property: Program Efficiency}
+		\begin{itemize}
+		\item A memory manager should make good use of the memory subsystem to allow programs to run faster.
+		\item The time taken to execute an instruction can vary widely depending on where objects are placed in memory.
+		\item Programs tends to exhibit ``locality'' (discussed later), which refers to the nonrandom clustered way in which typical programs access memory.
+		\item By attention to the placement of objects in memory, the memory manager can make better use of space, and make the program run faster.
+		\end{itemize}
+	\end{block}
+\end{frame}
+
+\begin{frame}{Low Overhead of the Memory Manager}
+	\begin{block}{Property: Low Overhead}
+		\begin{itemize}
+		\item Because memory allocations and deallocations are frequent operations in many programs (such as ones written in Java), it is important that these operations be as efficient as possible.
+		\item We wish to minimize the overhead, the fraction of execution time spent performing allocation and deallocation.
+		\end{itemize}
+	\end{block}
+	\vspace{1em}
+	\begin{description}
+	\item[Note] the overhead of allocation is dominated by a large amount of small requests; the overhead of managing large objects is less important.
+	\end{description}
+\end{frame}
+
+\begin{frame}{Efficiency of a Program}
+	\begin{itemize}
+	\item The efficiency of a program is determined by:
+		\begin{enumerate}
+		\item the number of instructions executed, and
+		\item the time taken to execute each of these instructions.
+		\end{enumerate}
+	\vfill
+	\item Data-intensive programs can therefore benefit significantly from optimizations that make good use of the memory subsystem.
+	\vfill
+	\item \emph{The run-time environment should prefer to use the memory storages close to the processor.}
+	\vfill
+	\item The concept of ``locality'' will help us to improve the use of the memory subsystem.
+	\end{itemize}
+\end{frame}
+
+\subsection{Locality in programs}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\begin{frame}{Concept of Locality}
+	\begin{small}
+	\begin{block}{\small Hypothesis}
+		The conventional wisdom is that programs spend 90\% of their time executing 10\% of the code.
+	\end{block}
+	In other words: they spend most of their time executing a relatively small fraction of the code and touching only a small fraction of the data.
+	\begin{definition}[Temporal Locality]
+		The memory locations, which are accessed by the program, are likely to be accessed again within a short period of time.
+	\end{definition}
+	\begin{definition}[Spatial Locality]
+		The memory locations close to the accessed location are likely also to be accessed within a short period of time.
+	\end{definition}
+	\end{small}
+\end{frame}
+
+\begin{frame}{Consequences of the Locality}
+	\begin{enumerate}
+	\item Programs often contains many instructions that are never executed.
+	\vfill
+	\item After evolution, legacy systems contain many instructions that are no longer used.
+	\vfill
+	\item Only a small fraction of the code that could be invoked is actually executed in a typical run of the program.
+	\vfill
+	\item The typical program spends most of its time executing innermost loops and tight recursive cycles in a program.
+	\end{enumerate}
+\end{frame}
+
+\begin{frame}{Memory Hierarchy}
+	\begin{itemize}
+	\item Memory manager (and compiler optimizer) must be aware of how the operating system is managing its memory.
+	\item In modern systems, the memory is composed of several layers:
+	\end{itemize}
+	\vspace{1em}
+	\begin{center}
+	\includegraphics[width=.8\linewidth]{memory_hierarchy}
+	\end{center}
+\end{frame}
+
+\begin{frame}{Locality and Memory Hierarchy}
+	\begin{itemize}
+	\item Locality permits to take advantage of the memory hierarchy.
+	\vfill
+	\item By placing the most common instructions and data in the fast-but-small storage, 
+	\vfill
+	\item While leaving the rest in the slow-but-large storage, we can lower the average memory-access time.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Optimization Policy}
+	\begin{small}
+	\begin{itemize}
+	\item Put the most-recent-used instruction in the fastest memory (example of spatial locality).
+	\item Put together in the same memory page/block the instructions that may be always executed together (example of spatial locality).
+	\item Temporal and spatial locality of data be improved by changing:
+		\begin{itemize}
+		\item the data layout, or
+		\item the order of the computations.
+		\end{itemize}
+	\end{itemize}
+	\begin{example}
+		\begin{itemize}
+		\item For example, visiting a large amount of data and performing small operations on is not a good approach.
+		\item Preferably, we should push down smaller data set into a faster memory level, and perform the computations on them.
+		\end{itemize}
+	\end{example}
+	\end{small}
+\end{frame}
+
+\subsection{Reduction of the fragmentation}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\begin{frame}{Holes in the Heap}
+	\begin{itemize}
+	\item At the beginning of the program, the heap is one contiguous unit of free space.
+	\vfill
+	\item As the program allocates and deallocates memory, this space is broken up into free and used chunks.
+	\vfill
+	\item The free chunks need not reside in a contiguous area of the heap.
+	\vfill
+	\item \emph{The free chunks are named holes.}
+	\vfill
+	\item Alternating chunks and holes is named the \emph{fragmentation} of the heap.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Object Placement for Minimizing the Defragmentation}
+	\begin{itemize}
+	\item We reduce fragmentation by controlling how the memory manager places new objects in the heap.
+	\vfill
+	\item Several approaches/strategies may be used:
+		\vfill
+		\begin{enumerate}
+		\item[Best-Fit Object Placement] Allocate the requested memory in the smallest available hole that is large enough. Not good for spatial locality.
+		\vfill
+		\item[First-Fit Object Placement] Allocate the requested memory in the first hole, which is able to contains the requested chunk. Less efficient than the previous one.
+		\vfill
+		\item[Next-Fit Object Placement] When no hole of the exact size was found, allocate the in the lastly split hole. Good for spatial locality and efficient.
+		\end{enumerate}
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Bins in the Best-Fit Implementation}
+	\begin{itemize}
+	\item To improve the implementation of the best-fit approach, we introduces the \emph{bins}.
+	\item \emph{Free space chunks are grouped into bins}, according to their sizes.
+	\item Many bins for the smaller sizes, because there are usually many more small objects.
+	\end{itemize}
+	\begin{block}{\small Lea Memory Manager (GNU C compiler)}\small 
+		\begin{itemize}
+		\item Bins of every multiple of 8 bytes until 512 bytes.
+		\item Larger-sized bins are logarithmically spaced.
+		\item Within the bins the chunks are ordered by their sizes.
+		\item Wilderness chunk: the largest bin because its size may be extended after requesting more memory to OS.
+		\end{itemize}
+	\end{block}
+\end{frame}
+
+\begin{frame}{Allocation of a Chunk}
+	Let a requested chunk \code{c} to be allocated.
+	\begin{enumerate}
+	\item If there is a bin for chunks of the size of \code{c}, we take any free space chunk from that bin.
+	\vfill
+	\item\label{allocation_chunk_b} If there is no bin for chunks of the size of \code{c}, we take the smallest bin that may include the requested size. \\
+		Within that bin, we can use either a first-fit or a best-fit strategy. \\
+		The remainder space of the selected chunk will generally be placed in a bin with smaller size.
+	\vfill
+	\item If there is no more free chunk in a bin, we repeat the point \ref{allocation_chunk_b} on a bin for a larger size; or we reach the wilderness chunk, which surely provide enough space.
+	\end{enumerate}
+\end{frame}
+
+\begin{frame}{Managing and Coalescing Free Space}
+	\begin{itemize}
+	\item When an object is deallocated, the memory manager make its chunk free.
+	\item In some circumstances, it may also be possible to combine (coalesce) that freed chunk with adjacent chunks.
+	\vfill
+	\item Two majors data structures are basically used for supporting coalescing of adjacent free blocks:
+		\begin{enumerate}
+		\item Boundary Tags
+		\item Doubly Linked, Embedded Free List
+		\end{enumerate}
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Managing and Coalescing Free Space}
+	\begin{itemize}
+	\item When an object is deallocated, the memory manager make its chunk free.
+	\item In some circumstances, it may also be possible to combine (coalesce) that freed chunk with adjacent chunks.
+	\vfill
+	\item Two majors data structures are basically used for supporting coalescing of adjacent free blocks:
+		\begin{enumerate}
+		\item \emph{Boundary Tags},
+		\item \emph{Doubly Linked Free List}, Embedded Free List.
+		\end{enumerate}
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Boundary Tags}
+	\sidenote{The order of the boundary tags depends on the run-time environment}
+	\begin{itemize}
+	\item At both the low and high ends of a chunk, whether free or allocated, we keep vital information.
+	\vfill
+	\item \Emph{At both ends}, we put:
+		\begin{enumerate}
+		\item a bit that indicates if the chunk is free or allocated.
+		\item a count of the total number of bytes in the chunk.
+		\end{enumerate}
+	\end{itemize}
+	\vfill
+	\begin{center}
+		\includegraphics[width=.8\linewidth]{boundary_tags}
+	\end{center}
+\end{frame}
+
+\begin{frame}{Doubly Linked Free List}
+	\sidenote{The order of the boundary tags depends on the run-time environment}
+	\begin{itemize}
+	\item The free chunks (but not the allocated ones) are linked in a doubly linked list.
+	\vfill
+	\item In addition to the boundary tags, a pointer to the next and to the following free space chunks are added at the both ends of the chunk.
+	\vfill
+	\item Does not need to allocate more space for these pointers: the pointers takes the unused bytes of the free chunks.
+	\item For the smaller chunks, they are expanded to allow to contain the pointers.
+	\end{itemize}
+	\vfill
+	\begin{center}
+		\includegraphics[width=.8\linewidth]{doubly_linked_list}
+	\end{center}
+\end{frame}
+
+\subsection{Manual Deallocation}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/shaded/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\begin{frame}{Manual Deallocation}
+	\begin{itemize}
+	\item This subsection is devoted to the manual deallocation requests, such as in C and C++ languages.
+	\vfill
+	\item Ideally, any storage that will no longer be accessed should be deleted.
+	\vfill
+	\item Conversely, any storage that may be referenced must not be deleted.
+	\vfill
+	\item It is hard to enforce these properties.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}{Main Problems with Manual Deallocations}
+	Two common errors may occurs in manual memory management:
+	\begin{enumerate}
+	\vfill
+	\item[Memory Leak] failing ever to delete data that cannot be referenced.
+	\vfill
+	\item[Dangling-pointer reference] referencing deleted data.
+	\end{enumerate}
+\end{frame}
+
+\begin{frame}{Problem of Memory Leak}
+	\begin{small}
+	\begin{block}{\small Observation}
+		\begin{itemize}
+		\item It is hard for a developer to tell if a program will never refer to some storage in the future.
+		\item The common mistake is not deleting storage that will never be referenced.
+		\end{itemize}
+	\end{block}
+	\begin{alertblock}{\small Problem}
+		May slow down the execution of the program due to increased memory usage.
+	\end{alertblock}
+	\begin{block}{\small Remarks}
+		\begin{itemize}
+		\item Correctness of the program is not changed.
+		\item Many programs may tolerate leaks but not the long-time and the critical ones (operating systems, server code\dots)
+		\end{itemize}
+	\end{block}
+	\end{small}
+\end{frame}
+
+\begin{frame}{Solving the Memory Leak Problem}
+	\begin{enumerate}
+	\item \emph{Automatic garbage collection gets rid of memory leaks by deallocating all the garbage.}\\
+		Even with a garbage collector, programs may still use more memory than necessary.
+	\vfill
+	\item \emph{A programmer may know that an object will never be referenced.} \\
+		He must deliberately remove the references to objects that will never be referenced, so the objects can be deallocated automatically.
+	\end{enumerate}
+\end{frame}
+
+\begin{frame}{Problem of Dangling-Pointer Reference}
+	\begin{small}
+	\begin{block}{\small Observation}
+		\begin{itemize}
+		\item Deletion of a storage, and then referencing the deleted storage.
+		\item These pointers are named ``dangling pointers.''
+		\end{itemize}
+	\end{block}
+	\begin{alertblock}{\small Problem}
+		\begin{itemize}
+		\item When the storage has been reallocated, it produces random effects on the program.
+		\item Writing through a dangling pointer changes an other variable than the one expecting by the dangling pointer.
+		\end{itemize}
+	\end{alertblock}
+	\begin{block}{\small Remarks}
+		Read, write or deallocate a pointer is named ``dereferencing the pointer.''
+	\end{block}
+	\end{small}
+\end{frame}
+
+\begin{frame}{Solving the Dangling-Pointer-Reference Problem}
+	\alertbox{Unfortunately, there is no turnkey solution.}
+	\begin{enumerate}
+	\item \emph{The programmer must be aware and may pay attention to his uses of the pointers.}
+	\vfill
+	\item \emph{The dangling-pointer-dereference error does not occurs in run-time environments that has an \Emph{automatic garbage collector}.}
+	\end{enumerate}
+\end{frame}
+
+\begin{frame}{Illegal Address Error}
+	\begin{definition}
+		This error occurs when the address to dereference is null or outside the bounds of any allocated memory (including the bounds of the memory space of the process).
+	\end{definition}
+	\vfill
+	\begin{itemize}
+	\item The illegal address error is related to the dangling-pointer-dereference error.
+	\item This error is at the origin of many security violations from hackers.
+	\item One solution is that the compiler inserts checks with every access, to make sure it is within the bounds.
+	\item The compiler optimizer may remove several of these checks when they are detected as not necessary.
+	\end{itemize}
+\end{frame}
+
+\begin{frame}[allowframebreaks]{Programming Conventions and Tools}
+	\begin{block}{Object Ownership}
+	\begin{itemize}
+	\item Associate an owner with each object at all times.
+	\item The owner is usually a function.
+	\item The owner is responsible for either deleting the object or for passing the object to another owner.
+	\item Non-owning points may reference the object, but the object must never be deallocated through them.
+	\item This convention eliminates memory leaks, and the deletion of the same object twice.
+	\item This convention does not solve the dangling-point-reference problem.
+	\end{itemize}
+	\end{block}
+	%
+	\framebreak
+	%
+	\begin{block}{Reference Counting}
+	\begin{itemize}
+	\item Associate a count with each dynamically allocated object.
+	\item Whenever the reference to the object is created, the counter is incremented.
+	\item Whenever the reference to the object is deleted, the counter is decremented.
+	\item The storage for the object is released when the counter is zero.
+	\item Expensive operation.
+	\item Do not work with inaccessible circular data structures.
+	\end{itemize}
+	\end{block}
+	%
+	\framebreak
+	%
+	\begin{block}{Region-Based Allocation}
+	\begin{itemize}
+	\item When objects are created to be used only within some step of a computation, we can allocate all such objects in the same region.
+	\item We then delete the entire region once that computation step completes.
+	\item Limited applicability.
+	\item Very efficient.
+	\end{itemize}
+	\end{block}
+\end{frame}
+
+\section{Garbage collection}
+
+\tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={show/show/hide},subsubsectionstyle={hide/hide/hide/hide}]
+
+\subsection{Introduction}
+
+\subsection{Properties of a garbage collector}
+
+\subsection{Reachability of data}
+
+\subsection{Reference-counting garbage collector}
+
+\subsubsection{Introduction}
+
+\subsubsection{Basic mark-and-sweep collector}
+
+\subsubsection{Basic abstraction}
+
+\subsubsection{Optimizing mark-and-sweep}
+
+\subsubsection{Mark-and-compact garbage collector}
+
+\subsubsection{Copying collector}
+
+\subsubsection{Brief Comparison}
+
+\subsection{Trace-based garbage collector}
+
+\subsubsection{Introduction}
+
+\subsubsection{Incremental garbage collector}
+
+\subsubsection{Incremental reachability analysis}
+
+\subsubsection{Basics of a partial collector}
+
+\subsubsection{Generational garbage collector}
+
+\subsubsection{Train algorithm}
+
+\subsection{Short-pause garbage collector}
+
 \section{Conclusion}
 
 \tableofcontentslide[sectionstyle={show/shaded},subsectionstyle={hide/hide/hide},subsubsectionstyle={hide/hide/hide/hide}]

imgs/chapter5/access_link.svg

Added
New image
+<?xml version="1.0" encoding="UTF-8" standalone="no"?>
+<!-- Created with Inkscape (http://www.inkscape.org/) -->
+
+<svg
+   xmlns:dc="http://purl.org/dc/elements/1.1/"
+   xmlns:cc="http://creativecommons.org/ns#"
+   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
+   xmlns:svg="http://www.w3.org/2000/svg"
+   xmlns="http://www.w3.org/2000/svg"
+   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
+   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
+   width="208.96512"
+   height="97.713028"
+   id="svg3089"
+   version="1.1"
+   inkscape:version="0.48.3.1 r9886"
+   sodipodi:docname="access_link.svg">
+  <defs
+     id="defs3091">
+    <marker
+       style="overflow:visible"
+       id="TriangleOutL-Blue"
+       refX="0"
+       refY="0"
+       orient="auto"
+       inkscape:stockid="TriangleOutL-Blue">
+      <path
+         inkscape:connector-curvature="0"
+         transform="scale(0.8,0.8)"
+         style="fill:#2b5879;fill-rule:evenodd;stroke:#2b5879;stroke-width:1pt"
+         d="m 5.77,0 -8.65,5 0,-10 8.65,5 z"
+         id="path6655" />
+    </marker>
+  </defs>
+  <sodipodi:namedview
+     id="base"
+     pagecolor="#ffffff"
+     bordercolor="#666666"
+     borderopacity="1.0"
+     inkscape:pageopacity="0.0"
+     inkscape:pageshadow="2"
+     inkscape:zoom="2.8"
+     inkscape:cx="102.96021"
+     inkscape:cy="53.550351"
+     inkscape:document-units="px"
+     inkscape:current-layer="layer2"
+     showgrid="false"
+     fit-margin-top="2"
+     fit-margin-left="2"
+     fit-margin-right="2"
+     fit-margin-bottom="2"
+     inkscape:window-width="1440"
+     inkscape:window-height="876"
+     inkscape:window-x="0"
+     inkscape:window-y="24"
+     inkscape:window-maximized="1"
+     showguides="true"
+     inkscape:guide-bbox="true" />
+  <metadata
+     id="metadata3094">
+    <rdf:RDF>
+      <cc:Work
+         rdf:about="">
+        <dc:format>image/svg+xml</dc:format>
+        <dc:type
+           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
+        <dc:title />
+      </cc:Work>
+    </rdf:RDF>
+  </metadata>
+  <g
+     inkscape:groupmode="layer"
+     id="layer2"
+     inkscape:label="Base &lt;1-&gt;"
+     style="display:inline"
+     transform="translate(127.65808,-33.239692)">
+    <path
+       style="opacity:1;color:#000000;fill:#dfeff7;fill-opacity:1;fill-rule:nonzero;stroke:none;stroke-width:0.50000000000000000;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate"
+       d="m -87.506523,42.958275 c 45.412841,-23.818263 81.0200614,16.651532 126.071419,0 l 0,82.487285 c -43.7976011,-13.59909 -88.891479,12.52953 -126.071419,0 z"
+       id="rect11075"
+       inkscape:connector-curvature="0"
+       sodipodi:nodetypes="ccccc" />
+    <text
+       xml:space="preserve"
+       style="font-size:10px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial"
+       x="231.42857"
+       y="146.64285"
+       id="text15223"
+       sodipodi:linespacing="125%"
+       transform="translate(-107.72169,-11.291725)"><tspan
+         sodipodi:role="line"
+         id="tspan15225"
+         x="231.42857"
+         y="146.64285" /></text>
+    <path
+       style="fill:none;stroke:#2b5879;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"
+       d="m -87.863664,112.77829 126.785707,0"
+       id="path6453-0-0"
+       inkscape:connector-curvature="0" />
+    <path
+       style="opacity:0.9;color:#000000;fill:none;stroke:#2b5879;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate"
+       d="m 38.564896,42.958275 0,82.130135 z"
+       id="rect11075-4"
+       inkscape:connector-curvature="0"
+       sodipodi:nodetypes="ccc" />
+    <path
+       inkscape:connector-curvature="0"
+       style="opacity:0.9;color:#000000;fill:none;stroke:#2b5879;stroke-width:1;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;marker:none;visibility:visible;display:inline;overflow:visible;enable-background:accumulate"
+       d="m -87.506523,42.958275 0,83.415855 z"
+       id="rect11075-4-6"
+       sodipodi:nodetypes="ccc" />
+    <text
+       sodipodi:linespacing="125%"
+       id="text15223-0"
+       y="181.071"
+       x="303.66641"
+       style="font-size:10px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial"
+       xml:space="preserve"><tspan
+         y="181.071"
+         x="303.66641"
+         id="tspan15225-2"
+         sodipodi:role="line" /></text>
+    <path
+       sodipodi:nodetypes="cc"
+       inkscape:connector-curvature="0"
+       id="path3853"
+       d="m -83.729787,58.727074 c -19.385643,1.329203 -23.008523,22.088219 -8.214286,30.31946"
+       style="fill:none;stroke:#2b5879;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#TriangleOutL-Blue)" />
+    <g
+       id="layer1"
+       inkscape:label="Code &lt;2&gt;"
+       style="display:inline"
+       transform="translate(72.23785,34.428145)" />
+    <g
+       id="layer3"
+       inkscape:label="Static &lt;3&gt;"
+       style="display:inline"
+       transform="translate(72.23785,34.428145)" />
+    <g
+       inkscape:label="Stack &lt;4&gt;"
+       id="g3085"
+       style="display:inline"
+       transform="translate(72.23785,34.428145)" />
+    <g
+       style="display:inline"
+       id="g3096"
+       inkscape:label="Heap &lt;5&gt;"
+       transform="translate(72.23785,34.428145)" />
+    <g
+       id="layer4"
+       inkscape:label="Free Memory &lt;6&gt;"
+       transform="translate(72.23785,34.428145)" />
+    <path
+       style="fill:none;stroke:#2b5879;stroke-width:0.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"
+       d="m -87.863664,100.77829 126.78571,0"
+       id="path6453-0-0-7"
+       inkscape:connector-curvature="0" />
+    <text
+       xml:space="preserve"
+       style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Arial;-inkscape-font-specification:Arial"
+       x="-24.480574"
+       y="109.6621"
+       id="text6459-5-4"
+       sodipodi:linespacing="125%"><tspan
+         sodipodi:role="line"
+         x="-24.480574"
+         y="109.6621"
+         id="tspan3874-5">4</tspan></text>
+    <path
+       style="fill:none;stroke:#2b5879;stroke-width:0.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"
+       d="m -87.863664,88.77829 126.78571,0"
+       id="path6453-0-0-5"
+       inkscape:connector-curvature="0" />
+    <text
+       xml:space="preserve"
+       style="font-size:9px;font-style:italic;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Arial;-inkscape-font-specification:Arial Italic"
+       x="-24.480574"
+       y="97.662102"
+       id="text6459-5-8"
+       sodipodi:linespacing="125%"><tspan
+         sodipodi:role="line"
+         x="-24.480574"
+         y="97.662102"
+         id="tspan3874-2"
+         style="font-size:8px;font-style:normal;-inkscape-font-specification:Arial">Activation Record Data</tspan></text>
+    <path
+       style="fill:none;stroke:#2b5879;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"
+       d="m -87.863664,76.77829 126.78571,0"
+       id="path6453-0-0-7-0"
+       inkscape:connector-curvature="0" />
+    <text
+       xml:space="preserve"
+       style="font-size:9px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Arial;-inkscape-font-specification:Arial"
+       x="-24.480574"
+       y="85.662102"
+       id="text6459-5-4-2"
+       sodipodi:linespacing="125%"><tspan
+         sodipodi:role="line"
+         x="-24.480574"
+         y="85.662102"
+         id="tspan3874-5-5">8</tspan></text>
+    <path
+       style="fill:none;stroke:#2b5879;stroke-width:0.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"
+       d="m -87.863664,64.77829 126.78571,0"
+       id="path6453-0-0-8"
+       inkscape:connector-curvature="0" />
+    <text
+       xml:space="preserve"
+       style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Arial;-inkscape-font-specification:Arial"
+       x="-24.480574"
+       y="73.662102"
+       id="text6459-5-0"
+       sodipodi:linespacing="125%"><tspan
+         sodipodi:role="line"
+         x="-24.480574"
+         y="73.662102"
+         id="tspan3874-6">Access Link</tspan></text>
+    <path
+       style="fill:none;stroke:#2b5879;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-opacity:1;stroke-dasharray:none;display:inline"
+       d="m -87.863664,52.77829 126.78571,0"
+       id="path6453-0-0-7-7"
+       inkscape:connector-curvature="0" />
+    <g
+       id="layer1-5"
+       inkscape:label="Code &lt;2&gt;"
+       style="display:inline"
+       transform="matrix(-1,0,0,1,106.69916,81.34361)">
+      <path
+         style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
+         d="m 216.57142,-4.9101356 c 0,0 1.67642,2.4867274 2,3.7946428 0.32358,1.30791541 0,12.8476258 0,12.8476258 l 4,1.589286 -4,1.589285 c 0,0 0.32358,11.602845 0,12.91076 -0.32358,1.307916 -2,3.794643 -2,3.794643"
+         id="path3035"
+         inkscape:connector-curvature="0"
+         sodipodi:nodetypes="czccczc" />
+    </g>
+    <path
+       style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;display:inline"
+       d="m -109.87226,52.731968 c 0,0 -1.67642,2.486727 -2,3.794643 -0.32358,1.307915 0,6.579769 0,6.579769 l -4,1.589286 4,1.589285 c 0,0 -0.32358,5.334988 0,6.642903 0.32358,1.307916 2,3.794643 2,3.794643"
+       id="path3035-7"
+       inkscape:connector-curvature="0"
+       sodipodi:nodetypes="czccczc" />
+    <text
+       xml:space="preserve"
+       style="font-size:10px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial"
+       x="-123.49988"
+       y="96.945564"
+       id="text4309"
+       sodipodi:linespacing="125%"><tspan
+         sodipodi:role="line"
+         id="tspan4311"
+         x="-123.49988"
+         y="96.945564">p</tspan></text>
+    <text
+       xml:space="preserve"
+       style="font-size:10px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;font-family:Arial;-inkscape-font-specification:Arial"
+       x="-123.19714"
+       y="66.481293"
+       id="text4343"
+       sodipodi:linespacing="125%"><tspan
+         sodipodi:role="line"
+         id="tspan4345"
+         x="-123.19714"
+         y="66.481293">g</tspan></text>
+    <text
+       xml:space="preserve"
+       style="font-size:8px;font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Arial;-inkscape-font-specification:Arial"
+       x="-24.269642"
+       y="62.047688"
+       id="text6459-5-0-5"
+       sodipodi:linespacing="125%"><tspan
+         sodipodi:role="line"
+         x="-24.269642"
+         y="62.047688"
+         id="tspan3874-6-2">Control Link</tspan></text>
+    <text
+       xml:space="preserve"
+       style="font-size:8px;font-style:italic;font-variant:normal;font-weight:normal;font-stretch:normal;text-align:center;line-height:125%;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;display:inline;font-family:Arial;-inkscape-font-specification:Arial Italic"
+       x="62.185944"
+       y="58.833401"
+       id="text6459-5-0-9"
+       sodipodi:linespacing="125%"><tspan
+         sodipodi:role="line"
+         x="62.185944"
+         y="58.833401"
+         id="tspan3874-6-8">Activation</tspan><tspan
+         sodipodi:role="line"
+         x="62.185944"
+         y="68.833405"
+         id="tspan3976">Record</tspan><tspan
+         sodipodi:role="line"
+         x="62.185944"
+         y="78.833405"
+         id="tspan3978">Data</tspan></text>
+    <path
+       sodipodi:nodetypes="cc"
+       inkscape:connector-curvature="0"
+       id="path3853-8"
+       d="m 34.605857,69.989765 c 19.385638,1.329203 15.93745,13.603447 8.214278,19.056769"
+       style="fill:none;stroke:#2b5879;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#TriangleOutL-Blue);display:inline" />
+  </g>
+  <g
+     inkscape:groupmode="layer"
+     id="layer5"
+     inkscape:label="Control &lt;2-&gt;"
+     style="display:inline"
+     transform="translate(-0.12166733,-8)" />
+  <g
+     inkscape:groupmode="layer"
+     id="layer6"
+     inkscape:label="Local Data &lt;3-&gt;"
+     style="display:inline"
+     transform="translate(-0.12166733,-8)" />
+  <g
+     inkscape:groupmode="layer"
+     id="layer7"
+     inkscape:label="sp &lt;4&gt;"
+     style="display:inline"
+     transform="translate(-0.12166733,-8)" />
+</svg>