#LyX 1.6.4 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass beamer
\begin_preamble
\usetheme{Copenhagen}
\usepackage{hyperref}
% or ...

%\setbeamercovered{transparent}
% or whatever (possibly just delete it)
%\usepackage{listings}
%\usetheme{Madrid}
%\usepackage{ae,aecompl}
\end_preamble
\use_default_options true
\language english
\inputencoding cp1255
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author "" 
\author "" 
\end_header

\begin_body

\begin_layout Title
Valgrind
\end_layout

\begin_layout Subtitle
From Magic to Science
\end_layout

\begin_layout Author
Shachar Raindel 
\end_layout

\begin_layout Institute
The Technion
\end_layout

\begin_layout Date
Haifux, 2010
\end_layout

\begin_layout BeginFrame
Outline
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

	
\backslash
tableofcontents[% 
\end_layout

\begin_layout Plain Layout

% 		currentsection, % causes all sections but the current to be shown in
 a semi-transparent way.
 
\end_layout

\begin_layout Plain Layout

% 		currentsubsection, % causes all subsections but the current subsection
 in the current section to ...
 
\end_layout

\begin_layout Plain Layout

% 		hideallsubsections, % causes all subsections to be hidden.
\end_layout

\begin_layout Plain Layout

% 		hideothersubsections, % causes the subsections of sections other than
 the current one to be hidden.
 
\end_layout

\begin_layout Plain Layout

% 		part=, % part number causes the table of contents of part part number
 to be shown 		
\end_layout

\begin_layout Plain Layout

       pausesections, % causes a 
\backslash
pause command to be issued before each section.
 This is useful if you 
\end_layout

\begin_layout Plain Layout

% 		pausesubsections, %  causes a 
\backslash
pause command to be issued before each subsection.
 
\end_layout

\begin_layout Plain Layout

% 		sections={ overlay specification }, 
\end_layout

\begin_layout Plain Layout

	] 
\end_layout

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout Section
Magic - Valgrind at Work
\end_layout

\begin_layout Subsection
Background
\end_layout

\begin_layout BeginFrame
Valgrind
\end_layout

\begin_layout Quote
\begin_inset Quotes eld
\end_inset

Valgrind is an award-winning instrumentation framework for building dynamic
 analysis tools
\begin_inset Quotes erd
\end_inset

 - Valgrind's front page
\end_layout

\begin_layout Itemize
Mostly known for Memcheck, which pinpoint many common problems in C/C++
 code
\end_layout

\begin_layout Itemize
Extremely useful tool for the novice C/C++ programmer
\end_layout

\begin_layout Itemize
Also useful for experienced ones
\end_layout

\begin_layout Itemize
Similar to Purify, Bounds-Checker, CodeGuard and Insure++
\end_layout

\begin_layout Itemize
Supports X86/Linux, AMD64/Linux, PPC32/Linux, PPC64/Linux and X86/Darwin
 (Mac OS X)
\end_layout

\begin_layout Itemize
ARM/Linux and MIPS/Linux ports are in progress, some versions for *BSD
\end_layout

\begin_layout Itemize
Supports wine - test your windows code with Valgrind!
\end_layout

\begin_layout Itemize
Available for X86/Linux since ~2003, actively developed
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{frame}[fragile]
\end_layout

\begin_layout Plain Layout


\backslash
frametitle{Sample (Bad) Code}
\end_layout

\end_inset


\end_layout

\begin_layout Itemize
We will use the following code for demonstration purposes:
\begin_inset CommandInset label
LatexCommand label
name "frame:codeSample"

\end_inset


\end_layout

\begin_deeper
\begin_layout Standard
\begin_inset listings
lstparams "language=C,numbers=left"
inline false
status open

\begin_layout Plain Layout

#include <stdio.h>
\end_layout

\begin_layout Plain Layout

#include <stdlib.h>
\end_layout

\begin_layout Plain Layout

#define SIZE 100
\end_layout

\begin_layout Plain Layout

int main() {
\end_layout

\begin_layout Plain Layout

    int i, sum = 0;
\end_layout

\begin_layout Plain Layout

    int *a = malloc(SIZE);
\end_layout

\begin_layout Plain Layout

    for( i=0; i < SIZE; ++i ) sum += a[i];
\end_layout

\begin_layout Plain Layout

    a[26] = 1;
\end_layout

\begin_layout Plain Layout

    a = NULL;
\end_layout

\begin_layout Plain Layout

    if(sum > 0) printf("Hi!
\backslash
n");
\end_layout

\begin_layout Plain Layout

    return 0;
\end_layout

\begin_layout Plain Layout

}
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Contains many bugs.
 Compiles without warnings or errors.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{frame}
\end_layout

\end_inset


\end_layout

\begin_layout Subsection
Live Demo
\end_layout

\begin_layout BeginFrame
Live Demo
\end_layout

\begin_layout Itemize
We are going to:
\end_layout

\begin_deeper
\begin_layout Itemize
compile the code
\end_layout

\begin_deeper
\begin_layout Quotation
gcc -Wall -ansi -pedantic -g -o sample sample.c
\end_layout

\end_deeper
\begin_layout Itemize
run the bare code
\end_layout

\begin_deeper
\begin_layout Quotation
./sample
\end_layout

\end_deeper
\begin_layout Itemize
run the program with valgrind
\end_layout

\begin_deeper
\begin_layout Quotation
valgrind 
\begin_inset Formula $--$
\end_inset

leak-check=full ./sample
\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
Results analysis will follow shortly after
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Invalid Reads
\end_layout

\begin_layout Example
==8990== Invalid read of size 4
\end_layout

\begin_layout Example
==8990== at 0x804844A: main (
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
hyperlink{frame:codeSample}{sample.c:7}
\end_layout

\end_inset

)
\end_layout

\begin_layout Example
==8990== Address 0x417e08c is 0 bytes after a block of size 100 alloc'd
 
\end_layout

\begin_layout Example
==8990== at 0x4024C1C: malloc (vg_replace_malloc.c:195) 
\end_layout

\begin_layout Example
==8990== by 0x8048430: main (sample.c:6) 
\end_layout

\begin_layout Itemize
We read past the end of the allocated array
\end_layout

\begin_layout Itemize
Trying to read from area which we are not allowed to access
\end_layout

\begin_layout Itemize
Could result in a SEGFAULT and surely doesn't do what we want
\end_layout

\begin_layout Itemize
Valgrind provides enough details to find the problem.
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Invalid Writes
\end_layout

\begin_layout Example
==8990== Invalid write of size 4 
\end_layout

\begin_layout Example
==8990== at 0x8048463: main (
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
hyperlink{frame:codeSample}{sample.c:8}
\end_layout

\end_inset

) 
\end_layout

\begin_layout Example
==8990== Address 0x417e090 is 4 bytes after a block of size 100 alloc'd
 
\end_layout

\begin_layout Example
==8990== at 0x4024C1C: malloc (vg_replace_malloc.c:195) 
\end_layout

\begin_layout Example
==8990== by 0x8048430: main (sample.c:6) 
\end_layout

\begin_layout Itemize
Similar to invalid read
\end_layout

\begin_layout Itemize
Details provided by valgrind:
\end_layout

\begin_deeper
\begin_layout Itemize
Location of fault (addresses, line number if debug-information present)
\end_layout

\begin_layout Itemize
Stack-trace to fault (you can get more using 
\emph on

\begin_inset Formula $--$
\end_inset

num
\begin_inset Formula $-$
\end_inset

callers=30
\emph default
 )
\end_layout

\begin_layout Itemize
Relevant blocks details and allocation/de-allocation stack-trace
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Memory Leaks
\end_layout

\begin_layout Itemize
At the end of the run, Valgrind does 
\begin_inset Quotes eld
\end_inset

Garbage Collection
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
Unreferenced memory in C/C++ 
\begin_inset Formula $\Rightarrow$
\end_inset

 memory leak
\end_layout

\begin_layout Example
==8990== 100 bytes in 1 blocks are definitely lost in loss record 1 of 1
 
\end_layout

\begin_layout Example
==8990== at 0x4024C1C: malloc (vg_replace_malloc.c:195) 
\end_layout

\begin_layout Example
==8990== by 0x8048430: main (
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
hyperlink{frame:codeSample}{sample.c:6}
\end_layout

\end_inset

) 
\end_layout

\begin_layout Itemize
Valgrind provides stack-trace for the allocation point
\end_layout

\begin_layout Itemize
3 kinds:
\end_layout

\begin_deeper
\begin_layout Itemize
Definitely lost (no pointers to allocation)
\end_layout

\begin_layout Itemize
Probably lost (pointers only to the middle of the allocation)
\end_layout

\begin_layout Itemize
Still reachable (block hasn't been free'd before exit, but pointers to it
 still exists)
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Use of Uninitialized Value
\end_layout

\begin_layout Example
==8990== Conditional jump or move depends on uninitialised value(s) 
\end_layout

\begin_layout Example
==8990== at 0x8048476: main (
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
hyperlink{frame:codeSample}{sample.c:10}
\end_layout

\end_inset

) 
\end_layout

\begin_layout Itemize
Valgrind checks and make sure the program flow is deterministic
\end_layout

\begin_layout Itemize
Usage of values which haven't been initialized in conditions is reported
\end_layout

\begin_layout Itemize
Also if they are passed as parameters for syscalls
\end_layout

\begin_layout Itemize
Valgrind will detail location in which the uninitialized data was used
\end_layout

\begin_layout Itemize
To get trace to the source of it, add 
\begin_inset Quotes eld
\end_inset


\emph on

\begin_inset Formula $--$
\end_inset

track
\begin_inset Formula $-$
\end_inset

origins=yes
\emph default

\begin_inset Quotes erd
\end_inset

 to the command-line
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout Subsection
Potential Pitfalls
\end_layout

\begin_layout BeginFrame
Outline
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

	
\backslash
tableofcontents[% 
\end_layout

\begin_layout Plain Layout

 		currentsection, % causes all sections but the current to be shown in
 a semi-transparent way.
 
\end_layout

\begin_layout Plain Layout

 		currentsubsection, % causes all subsections but the current subsection
 in the current section to ...
 
\end_layout

\begin_layout Plain Layout

% 		hideallsubsections, % causes all subsections to be hidden.
\end_layout

\begin_layout Plain Layout

% 		hideothersubsections, % causes the subsections of sections other than
 the current one to be hidden.
 
\end_layout

\begin_layout Plain Layout

% 		part=, % part number causes the table of contents of part part number
 to be shown 		
\end_layout

\begin_layout Plain Layout

%         pausesections, % causes a 
\backslash
pause command to be issued before each section.
 This is useful if you 
\end_layout

\begin_layout Plain Layout

% 		pausesubsections, %  causes a 
\backslash
pause command to be issued before each subsection.
 
\end_layout

\begin_layout Plain Layout

% 		sections={ overlay specification }, 
\end_layout

\begin_layout Plain Layout

	] 
\end_layout

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Danger, Will Robinson
\end_layout

\begin_layout Itemize
\begin_inset Flex URL
status open

\begin_layout Plain Layout

http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-0166
\end_layout

\end_inset


\end_layout

\begin_layout Itemize
Most of the time Valgrind's errors describe latent flaws in the program
\end_layout

\begin_layout Itemize
However, sometimes Valgrind is wrong
\end_layout

\begin_layout Itemize
Cryptography related code requires special attention
\end_layout

\begin_layout Itemize
A debian developer commented out code that valgrind didn't like
\end_layout

\begin_layout Itemize
Resulting in a latent bug
\end_layout

\begin_layout Itemize
With massive security implications
\end_layout

\begin_layout Itemize
All because valgrind claimed a value is used uninitialized
\end_layout

\begin_layout Itemize
Was intentionally used so, to collect more entropy
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{frame}[fragile]
\end_layout

\begin_layout Plain Layout


\backslash
label{frame:memcheckLimits}
\end_layout

\begin_layout Plain Layout


\backslash
frametitle{Problems that Valgrind doesn't Detect}
\end_layout

\end_inset


\end_layout

\begin_layout Itemize
Buffer overflows which ends up accessing valid memory:
\end_layout

\begin_layout Example

\end_layout

\begin_deeper
\begin_layout Standard
\begin_inset listings
inline false
status open

\begin_layout Plain Layout

char *p = malloc(1024); /* block 1 */
\end_layout

\begin_layout Plain Layout

char *q = malloc(1024); /* block 2 */
\end_layout

\begin_layout Plain Layout

p += 1200; /* "p" now points into block 2 */
\end_layout

\begin_layout Plain Layout

*p = 'a';  /* invalid write - undetected */ 
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout Itemize
Accesses to stack variables and global variables are not checked
\end_layout

\begin_layout Itemize
Business logic/algorithmic problems are not detected
\end_layout

\begin_layout Itemize
Checks only code that was executed
\end_layout

\begin_layout Itemize
Doesn't work well with statically-linked code
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{frame}
\end_layout

\end_inset


\end_layout

\begin_layout Section
More Magic - Advanced Valgrind Usage
\end_layout

\begin_layout Subsection
Other Tools in Valgrind
\end_layout

\begin_layout BeginFrame
Outline
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

	
\backslash
tableofcontents[% 
\end_layout

\begin_layout Plain Layout

 		currentsection, % causes all sections but the current to be shown in
 a semi-transparent way.
 
\end_layout

\begin_layout Plain Layout

 		currentsubsection, % causes all subsections but the current subsection
 in the current section to ...
 
\end_layout

\begin_layout Plain Layout

% 		hideallsubsections, % causes all subsections to be hidden.
\end_layout

\begin_layout Plain Layout

% 		hideothersubsections, % causes the subsections of sections other than
 the current one to be hidden.
 
\end_layout

\begin_layout Plain Layout

% 		part=, % part number causes the table of contents of part part number
 to be shown 		
\end_layout

\begin_layout Plain Layout

%         pausesections, % causes a 
\backslash
pause command to be issued before each section.
 This is useful if you 
\end_layout

\begin_layout Plain Layout

% 		pausesubsections, %  causes a 
\backslash
pause command to be issued before each subsection.
 
\end_layout

\begin_layout Plain Layout

% 		sections={ overlay specification }, 
\end_layout

\begin_layout Plain Layout

	] 
\end_layout

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Other Tools in Valgrind
\end_layout

\begin_layout Itemize
We talked about Memcheck -- the default tool in Valgrind
\end_layout

\begin_layout Itemize
But Valgrind can do much more than that
\end_layout

\begin_layout Itemize
Contains many tools, some stable, some experimental
\end_layout

\begin_layout Itemize
You can even write your own tools in few days of work
\end_layout

\begin_layout Itemize
Valgrind ships with the following tools:
\end_layout

\begin_layout Columns

\end_layout

\begin_deeper
\begin_layout Column
140pt
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
setbeamercolor{block title}{bg=orange}
\end_layout

\begin_layout Plain Layout


\backslash
setbeamercolor{block body}{bg=orange!40}
\end_layout

\end_inset


\end_layout

\begin_layout Block
\begin_inset ERT
status open

\begin_layout Plain Layout

{Memory Error Checkers}
\end_layout

\end_inset


\end_layout

\begin_deeper
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="1" columns="2">
<features>
<column alignment="left" valignment="top" width="0">
<column alignment="left" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- Ptrcheck 
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- Memcheck
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\end_deeper
\begin_layout Block
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{block}
\end_layout

\begin_layout Plain Layout


\backslash
setbeamercolor{block title}{bg=brown}
\end_layout

\begin_layout Plain Layout


\backslash
setbeamercolor{block body}{bg=orange!40}
\end_layout

\begin_layout Plain Layout


\backslash
begin{block}{Profilers}
\end_layout

\end_inset


\end_layout

\begin_deeper
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="2" columns="2">
<features>
<column alignment="left" valignment="top" width="0">
<column alignment="left" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- Cachegrind
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- Callgrind
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- Massif
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\end_deeper
\begin_layout Column
140pt
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
setbeamercolor{block title}{bg=red}
\end_layout

\begin_layout Plain Layout


\backslash
setbeamercolor{block body}{bg=orange!40}
\end_layout

\end_inset


\end_layout

\begin_layout Block
\begin_inset ERT
status open

\begin_layout Plain Layout

{Thread Error Detectors}
\end_layout

\end_inset


\end_layout

\begin_deeper
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="1" columns="2">
<features>
<column alignment="left" valignment="top" width="0">
<column alignment="left" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- Helgrind
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- DRD
\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\end_deeper
\begin_layout Block
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{block}
\end_layout

\begin_layout Plain Layout


\backslash
setbeamercolor{block title}{bg=yellow}
\end_layout

\begin_layout Plain Layout


\backslash
setbeamercolor{block body}{bg=orange!30}
\end_layout

\begin_layout Plain Layout


\backslash
begin{block}{Sample Tools and others}
\end_layout

\end_inset


\end_layout

\begin_deeper
\begin_layout Standard
\begin_inset Tabular
<lyxtabular version="3" rows="2" columns="2">
<features>
<column alignment="left" valignment="top" width="0">
<column alignment="left" valignment="top" width="0">
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- Lackey
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- None
\end_layout

\end_inset
</cell>
</row>
<row>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout
-- BBV
\end_layout

\end_inset
</cell>
<cell alignment="center" valignment="top" usebox="none">
\begin_inset Text

\begin_layout Plain Layout

\end_layout

\end_inset
</cell>
</row>
</lyxtabular>

\end_inset


\end_layout

\end_deeper
\begin_layout Block
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
setbeamercolor{block title}{bg=blue}
\end_layout

\begin_layout Plain Layout


\backslash
setbeamercolor{block body}{bg=blue!30}
\end_layout

\end_inset


\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Ptrcheck
\end_layout

\begin_layout Itemize
Activate by adding 
\begin_inset Formula $--$
\end_inset


\emph on
tool=exp-ptrcheck
\end_layout

\begin_layout Itemize
Similar in goals to Memcheck
\end_layout

\begin_layout Itemize
Still experimental
\end_layout

\begin_layout Itemize
Uses very different approach than Memcheck
\end_layout

\begin_layout Itemize
Can detect failures Memcheck doesn't detect (like the code we 
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
hyperlink{frame:memcheckLimits}{
\backslash
beamergotobutton{saw}}
\end_layout

\end_inset

 )
\end_layout

\begin_layout Itemize
Has got false positives (different than the ones Memcheck gets)
\end_layout

\begin_layout Itemize
Slower than Memcheck
\end_layout

\begin_layout Itemize
Doesn't check for memory leakage and validity of accesses
\end_layout

\begin_layout Itemize
Use alongside Memcheck for better coverage
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Profiling Tools
\end_layout

\begin_layout Itemize
Cachegrind
\end_layout

\begin_deeper
\begin_layout Itemize
Traces the code memory accesses and jump patterns
\end_layout

\begin_layout Itemize
Simulates a 2-level cache and branch predictor
\end_layout

\begin_layout Itemize
Provide details about cache misses and their source
\end_layout

\begin_layout Itemize
Can help optimizing performance critical code
\end_layout

\end_deeper
\begin_layout Itemize
Callgrind
\end_layout

\begin_deeper
\begin_layout Itemize
Extends Cachegrind
\end_layout

\begin_layout Itemize
Propagates the costs along the call-tree
\end_layout

\begin_layout Itemize
Has a KDE front-end -- KCacheGrind
\end_layout

\end_deeper
\begin_layout Itemize
Massif
\end_layout

\begin_deeper
\begin_layout Itemize
Memory allocations profiler
\end_layout

\begin_layout Itemize
Keeps stack-trace of every memory allocation/deallocation
\end_layout

\begin_layout Itemize
Print memory usage status in peak times and upon specific intervals
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Thread Error Detectors
\end_layout

\begin_layout Itemize
Functionality similar to Intel's ThreadChecker
\end_layout

\begin_layout Itemize
Detects a variety of threading related problems:
\end_layout

\begin_deeper
\begin_layout Itemize
Threading API misuse
\end_layout

\begin_layout Itemize
Lock order problems (potential dead-locks)
\end_layout

\begin_layout Itemize
Data-Races
\end_layout

\end_deeper
\begin_layout Itemize
Two similar implementations in Valgrind
\end_layout

\begin_deeper
\begin_layout Itemize
Helgrind
\end_layout

\begin_deeper
\begin_layout Itemize
The Internet claims it produces many false positives
\end_layout

\begin_layout Itemize
Supposedly catches more errors too
\end_layout

\end_deeper
\begin_layout Itemize
DRD
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout Subsection
Fine Tuning and Client Requests
\end_layout

\begin_layout BeginFrame
Outline
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

	
\backslash
tableofcontents[% 
\end_layout

\begin_layout Plain Layout

 		currentsection, % causes all sections but the current to be shown in
 a semi-transparent way.
 
\end_layout

\begin_layout Plain Layout

 		currentsubsection, % causes all subsections but the current subsection
 in the current section to ...
 
\end_layout

\begin_layout Plain Layout

% 		hideallsubsections, % causes all subsections to be hidden.
\end_layout

\begin_layout Plain Layout

% 		hideothersubsections, % causes the subsections of sections other than
 the current one to be hidden.
 
\end_layout

\begin_layout Plain Layout

% 		part=, % part number causes the table of contents of part part number
 to be shown 		
\end_layout

\begin_layout Plain Layout

%         pausesections, % causes a 
\backslash
pause command to be issued before each section.
 This is useful if you 
\end_layout

\begin_layout Plain Layout

% 		pausesubsections, %  causes a 
\backslash
pause command to be issued before each subsection.
 
\end_layout

\begin_layout Plain Layout

% 		sections={ overlay specification }, 
\end_layout

\begin_layout Plain Layout

	] 
\end_layout

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Client Requests
\end_layout

\begin_layout Itemize
Valgrind provides communication channel for tested programs
\end_layout

\begin_layout Itemize
Good for unit-test harnesses
\end_layout

\begin_layout Itemize
Also good if you are doing weird stuff in your code
\end_layout

\begin_deeper
\begin_layout Itemize
A special memory allocator, such as object-pool
\end_layout

\begin_deeper
\begin_layout Itemize
Use VALGRIND_CREATE_MEMPOOL to mark a memory area as an object-pool
\end_layout

\begin_layout Itemize
Use VALGRIND_MEMPOOL_ALLOC to mark an object as allocated
\end_layout

\begin_layout Itemize
Use VALGRIND_MEMPOOL_FREE to mark an object as free
\end_layout

\end_deeper
\begin_layout Itemize
Self-Modifying code, i.e.
 JIT compiler
\end_layout

\begin_deeper
\begin_layout Itemize
Use VALGRIND_DISCARD_TRANSLATIONS to report about areas in which code has
 been changed
\end_layout

\end_deeper
\end_deeper
\begin_layout Itemize
Useful also for hunting bugs
\end_layout

\begin_deeper
\begin_layout Itemize
For example, check for memory leaks, using 
\noun on
VALGRIND_DO_LEAK_CHECK
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Suppression Files
\end_layout

\begin_layout Itemize
Valgrind tends to be very noisy
\end_layout

\begin_layout Itemize
Most of the times it is indicating bugs that should be fixed
\end_layout

\begin_deeper
\begin_layout Itemize
But not always the one we want to fix right now
\end_layout

\end_deeper
\begin_layout Itemize
Sometimes it is correct code, which Valgrind failed to understand
\end_layout

\begin_deeper
\begin_layout Itemize
Mostly in sophisticated/extremely optimized library code
\end_layout

\begin_layout Itemize
Also possible when having unusual interactions with the kernel 
\end_layout

\end_deeper
\begin_layout Itemize
Valgrind includes a mechanism to silent a specific error
\end_layout

\begin_deeper
\begin_layout Itemize
Works with all tools that report errors
\end_layout

\begin_layout Itemize
Simple file format, see documentation for details
\end_layout

\begin_layout Itemize
Valgrind includes suppression for many common libs
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout Section
Science - How does Valgrind do that?
\end_layout

\begin_layout Subsection
The Core - Stuff all Valgrind Tools Share
\end_layout

\begin_layout BeginFrame
Outline
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

	
\backslash
tableofcontents[% 
\end_layout

\begin_layout Plain Layout

 		currentsection, % causes all sections but the current to be shown in
 a semi-transparent way.
 
\end_layout

\begin_layout Plain Layout

 		currentsubsection, % causes all subsections but the current subsection
 in the current section to ...
 
\end_layout

\begin_layout Plain Layout

% 		hideallsubsections, % causes all subsections to be hidden.
\end_layout

\begin_layout Plain Layout

% 		hideothersubsections, % causes the subsections of sections other than
 the current one to be hidden.
 
\end_layout

\begin_layout Plain Layout

% 		part=, % part number causes the table of contents of part part number
 to be shown 		
\end_layout

\begin_layout Plain Layout

%         pausesections, % causes a 
\backslash
pause command to be issued before each section.
 This is useful if you 
\end_layout

\begin_layout Plain Layout

% 		pausesubsections, %  causes a 
\backslash
pause command to be issued before each subsection.
 
\end_layout

\begin_layout Plain Layout

% 		sections={ overlay specification }, 
\end_layout

\begin_layout Plain Layout

	] 
\end_layout

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
VEX - Binary Translation
\end_layout

\begin_layout Itemize
We want to inspect all memory accesses in the code
\end_layout

\begin_layout Itemize
Straight forward solution - CPU emulation
\end_layout

\begin_layout Itemize
But this is really slow
\end_layout

\begin_layout Itemize
Treat the program binary as 
\begin_inset Quotes eld
\end_inset

source-code
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
Allow the tools to modify the code being compiled
\end_layout

\begin_layout Itemize
VEX's front-end translates X86 opcodes into Intermediate Representation
 code
\end_layout

\begin_layout Itemize
VEX's back-end translates IR code back to X86 code
\end_layout

\begin_layout Itemize
Tools can manipulate the IR code in the middle
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
IR code
\end_layout

\begin_layout Itemize
VEX translates each guest opcode into a block of IR code
\end_layout

\begin_layout Itemize
IR code is similar to assembly for a RISC-style machine
\end_layout

\begin_layout Itemize
IR code assumes machine with infinite number of variables
\end_layout

\begin_layout Itemize
The 
\begin_inset Quotes eld
\end_inset

guest state
\begin_inset Quotes erd
\end_inset

 is stored in a special memory area
\end_layout

\begin_layout ExampleBlock
\begin_inset ERT
status open

\begin_layout Plain Layout

{ IR translation of ``addl 
\backslash
%eax, 
\backslash
%ebx'' }
\end_layout

\end_inset


\end_layout

\begin_deeper
\begin_layout Standard
------ IMark(0x24F275, 7) ------
\end_layout

\begin_layout Standard
t3 = GET:I32(0) # get %eax, a 32-bit integer 
\end_layout

\begin_layout Standard
t2 = GET:I32(12) # get %ebx, a 32-bit integer 
\end_layout

\begin_layout Standard
t1 = Add32(t3,t2) # addl 
\end_layout

\begin_layout Standard
PUT(0) = t1 # put %eax 
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
IR code - Properties
\end_layout

\begin_layout Itemize
IR code is fully typed:
\end_layout

\begin_deeper
\begin_layout Itemize
All variables and results of calculations have type
\end_layout

\begin_layout Itemize
No implicit type conversion
\end_layout

\begin_layout Itemize
VEX performs sanity checks on these types all of the time
\end_layout

\end_deeper
\begin_layout Itemize
IR code is in a Single Static Assignment form
\end_layout

\begin_deeper
\begin_layout Itemize
Each variable is assigned only once
\end_layout

\begin_layout Itemize
Simplifies the instrumentation of the code
\end_layout

\begin_layout Itemize
Also simplifies the optimization of the code when running it
\end_layout

\end_deeper
\begin_layout Itemize
IR code is presented to the tools in semi-parsed form
\end_layout

\begin_deeper
\begin_layout Itemize
Easy to manipulate lists of instructions
\end_layout

\begin_layout Itemize
Instructions are presented in a convinient data-structure
\end_layout

\begin_layout Itemize
Useful functions for manipulating IR code (add/remove instructions, etc.)
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
JIT, VEX and IR
\end_layout

\begin_layout Itemize
The 
\begin_inset Formula $X86\rightarrow IR\rightarrow X86$
\end_inset

 translation is done in a Just In Time manner
\end_layout

\begin_layout Itemize
Every basic-block is translated upon its first execution
\end_layout

\begin_deeper
\begin_layout Definition
\begin_inset Flex CharStyle:Alert
status collapsed

\begin_layout Plain Layout
Basic-Block
\end_layout

\end_inset

 - a linear sequence of code, with one entry point, one exit point and no
 jump instructions contained within it.
\end_layout

\end_deeper
\begin_layout Itemize
The translation is done so that Valgrind's dispatcher regains control after
 each basic-block
\end_layout

\begin_layout Itemize
Caching of translated code blocks improves execution speed
\end_layout

\begin_layout BeginFrame
Bootstrap Code
\end_layout

\begin_layout Itemize
Small, shared launcher - launches the relevant tool 
\end_layout

\begin_layout Itemize
Each tool's binary contains a complete copy of the core code
\end_layout

\begin_layout Itemize
The interesting stuff in bootstrap:
\end_layout

\begin_deeper
\begin_layout Itemize
Reading the debug information for the target program
\end_layout

\begin_layout Itemize
Initialize VEX - Valgrind's binary-translation mechanism 
\end_layout

\begin_layout Itemize
Call tool-specific init code
\end_layout

\begin_layout Itemize
Load the target program
\end_layout

\begin_layout Itemize
Setup the environment for the target program run
\end_layout

\begin_layout Itemize
Initialize Valgrind's thread-scheduler
\end_layout

\begin_deeper
\begin_layout Itemize
The scheduler makes sure that only one thread runs at a time
\end_layout

\begin_layout Itemize
Still replicates the entire thread structure to the OS
\end_layout

\begin_layout Itemize
Also handles signals
\end_layout

\end_deeper
\begin_layout Itemize
Kick-start the 
\begin_inset Quotes eld
\end_inset

guest
\begin_inset Quotes erd
\end_inset

 application main thread, using VEX and Valgrind's dispatcher
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Function Call Redirection
\end_layout

\begin_layout Itemize
Valgrind implements a redirection mechanism
\end_layout

\begin_layout Itemize
This mechanism can 
\begin_inset Quotes eld
\end_inset

hijack
\begin_inset Quotes erd
\end_inset

 various function calls
\end_layout

\begin_layout Itemize
Done in the binary translation level
\end_layout

\begin_layout Itemize
Some examples where this ability is useful:
\end_layout

\begin_deeper
\begin_layout Itemize
Memory allocation functions
\end_layout

\begin_layout Itemize
Various sys-calls (write/read files, etc.)
\end_layout

\begin_layout Itemize
Loading dynamic-link library
\end_layout

\begin_layout Itemize
Replace some optimized functions with debug versions
\end_layout

\end_deeper
\begin_layout Itemize
The guest code can request that as well
\end_layout

\begin_deeper
\begin_layout Itemize
Redirect requests are indicated by a specially mangled function name
\end_layout

\begin_layout Itemize
Special 
\begin_inset Quotes eld
\end_inset

magic-sequance
\begin_inset Quotes erd
\end_inset

 to call the original function
\end_layout

\begin_layout Itemize
Nice C macros make it developer friendly
\end_layout

\begin_layout Itemize
See documentation for details
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Client Requests - Behind the Scenes
\end_layout

\begin_layout Itemize
The VEX compiler recognizes few magic-sequances
\end_layout

\begin_layout Itemize
The magic-sequances are a no-op when run on normal CPU
\end_layout

\begin_layout Itemize
In X86, the magic-sequance is 
\begin_inset Quotes eld
\end_inset

roll 3, %edi ; roll 13, %edi; roll 29, %edi ; roll 19, %edi;
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
Followed by 
\begin_inset Quotes eld
\end_inset

xchgl %reg, %reg
\begin_inset Quotes erd
\end_inset

, where reg indicates the kind of the magic-sequance
\end_layout

\begin_layout Itemize
Similar style request for the other platforms
\end_layout

\begin_layout Itemize
Used to trigger Valgrind's Client Request mechanism
\end_layout

\begin_layout Itemize
On X86, client request param is passed on EAX, result is returned on EDX
\end_layout

\begin_layout Itemize
Also used for calling functions without the redirects
\end_layout

\begin_layout Itemize
And for getting the original address of a redirected call
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout Subsection
Memcheck - Behind the Scenes
\end_layout

\begin_layout BeginFrame
Outline
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

	
\backslash
tableofcontents[% 
\end_layout

\begin_layout Plain Layout

 		currentsection, % causes all sections but the current to be shown in
 a semi-transparent way.
 
\end_layout

\begin_layout Plain Layout

 		currentsubsection, % causes all subsections but the current subsection
 in the current section to ...
 
\end_layout

\begin_layout Plain Layout

% 		hideallsubsections, % causes all subsections to be hidden.
\end_layout

\begin_layout Plain Layout

% 		hideothersubsections, % causes the subsections of sections other than
 the current one to be hidden.
 
\end_layout

\begin_layout Plain Layout

% 		part=, % part number causes the table of contents of part part number
 to be shown 		
\end_layout

\begin_layout Plain Layout

%         pausesections, % causes a 
\backslash
pause command to be issued before each section.
 This is useful if you 
\end_layout

\begin_layout Plain Layout

% 		pausesubsections, %  causes a 
\backslash
pause command to be issued before each subsection.
 
\end_layout

\begin_layout Plain Layout

% 		sections={ overlay specification }, 
\end_layout

\begin_layout Plain Layout

	] 
\end_layout

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Memcheck Basics, A-bits
\end_layout

\begin_layout Itemize
Memcheck tracks what memory the guest application may access
\end_layout

\begin_layout Itemize
Two levels of allowed access:
\end_layout

\begin_deeper
\begin_layout Itemize
Write to / read from the memory 
\end_layout

\begin_layout Itemize
Use the value in memory for anything serious
\end_layout

\end_deeper
\begin_layout Itemize
The first one is tracked with 
\begin_inset Quotes eld
\end_inset

A
\begin_inset Quotes erd
\end_inset

 bits (Access)
\end_layout

\begin_deeper
\begin_layout Itemize
One bit per byte of memory
\end_layout

\begin_layout Itemize
Set to 0 if guest is not allowed to access (i.e.
 free'd block)
\end_layout

\begin_layout Itemize
Set to 1 upon memory allocation
\end_layout

\begin_layout Itemize
Report an error if guest code touched memory with A == 0
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
V-bits
\end_layout

\begin_layout Itemize
The second access level is tracked with 
\begin_inset Quotes eld
\end_inset

V
\begin_inset Quotes erd
\end_inset

 bits (Valid)
\end_layout

\begin_deeper
\begin_layout Itemize
One bit per bit of memory
\end_layout

\begin_layout Itemize
Set to 1 if the original memory bit haven't been defined yet
\end_layout

\begin_layout Itemize
Set to zero once the memory bit is set
\end_layout

\begin_layout Itemize
State is transitive
\end_layout

\begin_deeper
\begin_layout Example
If 
\begin_inset Formula $c$
\end_inset

 is not defined, evaluating 
\begin_inset Formula $a=b+c$
\end_inset

 will get 
\begin_inset Formula $a$
\end_inset

 to be undefined too 
\end_layout

\end_deeper
\begin_layout Itemize
Reports an error when conditional jumps and syscalls are given undefined
 values
\end_layout

\end_deeper
\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Leak Check
\end_layout

\begin_layout Itemize
Memcheck does leak check in the end of a run of a program
\end_layout

\begin_layout Itemize
It is possible to trigger it through a client request as well
\end_layout

\begin_layout Itemize
Very similar in concept to garbage--collection
\end_layout

\begin_layout Itemize
Chases pointers from globals and stack variables
\end_layout

\begin_layout Itemize
Only considers pointers which are defined (V-bit = 0)
\end_layout

\begin_layout Itemize
If there are no pointers to a block, it is 
\begin_inset Quotes eld
\end_inset

definitely lost
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
If there are still valid pointers to a block, it is 
\begin_inset Quotes eld
\end_inset

still reachable
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
If there is a pointer to somewhere in the middle of a block, it is 
\begin_inset Quotes eld
\end_inset

possibly lost
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
If the only pointers to a block are from definitely lost blocks, it is 
\begin_inset Quotes eld
\end_inset

indirectly lost
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout Itemize
Valgrind keeps the stack-trace of the allocation point for each block
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout Subsection
Stuff I use Valgrind for
\end_layout

\begin_layout BeginFrame
Outline
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout

	
\backslash
tableofcontents[% 
\end_layout

\begin_layout Plain Layout

 		currentsection, % causes all sections but the current to be shown in
 a semi-transparent way.
 
\end_layout

\begin_layout Plain Layout

 		currentsubsection, % causes all subsections but the current subsection
 in the current section to ...
 
\end_layout

\begin_layout Plain Layout

% 		hideallsubsections, % causes all subsections to be hidden.
\end_layout

\begin_layout Plain Layout

% 		hideothersubsections, % causes the subsections of sections other than
 the current one to be hidden.
 
\end_layout

\begin_layout Plain Layout

% 		part=, % part number causes the table of contents of part part number
 to be shown 		
\end_layout

\begin_layout Plain Layout

%         pausesections, % causes a 
\backslash
pause command to be issued before each section.
 This is useful if you 
\end_layout

\begin_layout Plain Layout

% 		pausesubsections, %  causes a 
\backslash
pause command to be issued before each subsection.
 
\end_layout

\begin_layout Plain Layout

% 		sections={ overlay specification }, 
\end_layout

\begin_layout Plain Layout

	] 
\end_layout

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
My Research (So Far)
\end_layout

\begin_layout Itemize
In my research, I'm looking into memory allocation schemes
\end_layout

\begin_layout Itemize
My claim is that with proper hinting from the application these can be improved
 significantly
\end_layout

\begin_layout Itemize
I use valgrind to measure the current situation
\end_layout

\begin_layout Itemize
Attempting to quantify possible improvement
\end_layout

\begin_layout Itemize
A new tool, which I call mtrace
\end_layout

\begin_layout Itemize
Practically merges parts of lackey and of massif
\end_layout

\begin_layout Itemize
Traces all allocations and memory accesses
\end_layout

\begin_layout Itemize
Post-processing scripts for gathering statistics and data
\end_layout

\begin_layout Itemize
Nice plots of memory access patterns in Matlab (next slides)
\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Memory Access Patern of Xvnc
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename myResearch-bigpic.eps
	scale 45

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Memory Access Patern of Xvnc (Detail)
\end_layout

\begin_layout Standard
\begin_inset Graphics
	filename myResearch-detail.eps
	scale 45

\end_inset


\end_layout

\begin_layout EndFrame

\end_layout

\begin_layout BeginFrame
Questions?
\end_layout

\begin_layout Standard
\align center

\size giant
?
\end_layout

\begin_layout EndFrame

\end_layout

\end_body
\end_document
