Added project presentationHEADmaster

8 files changed, 500 insertions, 0 deletions

diff --git a/presentation/images/file_fmt_subsystem_integration.tex b/presentation/images/file_fmt_subsystem_integration.tex
new file mode 100644
index 0000000..a18be3f
--- /dev/null
+++ b/presentation/images/file_fmt_subsystem_integration.tex
@@ -0,0 +1,32 @@
+%-------------------------------------------------------------------------------
+% file_fmt_subsystem_integration.tex - subsystem integration as image
+%-------------------------------------------------------------------------------
+% author   : Manuel Bentele
+% date     : Aug 29, 2019
+% copyright: (c) 2019 Manuel Bentele
+%-------------------------------------------------------------------------------
+
+\begin{tikzpicture}[
+        box/.style = {rectangle, draw, minimum height = 0.15\textheight},
+        bwidth/.style = {minimum width = 0.35\textwidth},
+        old/.style = {dashed, fill = gray!10},
+        arrow/.style = {-triangle 45},
+        desc/.style = {font = \small}
+    ]
+    \node[box, old, minimum height = 0.08\textheight, bwidth] (blk) {Block layer};
+    \node[box, old, below = 0.6 of blk, bwidth] (loop) {Loop device module};
+    \node[box, old, minimum height = 0.1\textheight,
+        xshift = -0.1\textheight, yshift = -0.01\textheight] (lodevs)
+            at (loop.south east) {Loop devices};
+    \node[box, fill = hdr, right = 2 of loop] (subsys) {File format subsystem};
+    \node[box, fill = dat, minimum height = 0.1\textheight,
+        xshift = -0.1\textheight, yshift = -0.01\textheight] (drvs)
+            at (subsys.south east) {File format drivers};
+    \node[box, right = 2 of subsys, old] (file) {Backing files};
+    
+    \draw[arrow] (blk) -- node[right, desc] {Requests} (loop);
+    \draw[arrow] (loop) -- node[above, desc] {Requests} (subsys);
+    \draw[arrow] (subsys) --
+        node[anchor = west, rotate = 90, align = left, desc]
+            {read\\write\\\ \ \vdots} (file);
+\end{tikzpicture}
\ No newline at end of file
diff --git a/presentation/images/linux_storage_stack.tex b/presentation/images/linux_storage_stack.tex
new file mode 100644
index 0000000..3fb9eb2
--- /dev/null
+++ b/presentation/images/linux_storage_stack.tex
@@ -0,0 +1,64 @@
+%-------------------------------------------------------------------------------
+% linux_storage_stack.tex - renders the storage stack of the Linux kernel
+%-------------------------------------------------------------------------------
+% author   : Manuel Bentele
+% date     : Aug 29, 2019
+% copyright: (c) 2019 Manuel Bentele
+%-------------------------------------------------------------------------------
+
+\begin{tikzpicture}[
+        box/.style = {rectangle, draw, minimum height = 0.75cm, align = center},
+        largeb/.style = {minimum width = 0.7\textwidth},
+        smallb/.style = {minimum width = 0.225\textwidth},
+        arrow/.style = {-triangle 45},
+        desc/.style = {font = \footnotesize},
+        node distance = 0.06\textwidth
+    ]
+    
+    \node[box, largeb, fill = hdr] (apps) {Applications};
+    \node[box, largeb, fill = ret, below = of apps] (vfs)
+        {Virtual file system (VFS)};
+    \node[box, smallb, fill = gray!15, left = of vfs] (dio) {Direct IO};
+    \node[box, smallb, fill = gray!15, right = of vfs] (pgc) {Page cache};
+    
+    \draw[arrow] ([xshift=-0.3\textwidth]apps.south) -- node[right,desc] {read}
+        ([xshift=-0.3\textwidth]vfs.north);
+    \draw[arrow] ([xshift=-0.1\textwidth]apps.south) -- node[right,desc] {write}
+        ([xshift=-0.1\textwidth]vfs.north);
+    \draw[arrow] ([xshift=0.1\textwidth]apps.south) -- node[right,desc] {open}
+        ([xshift=0.1\textwidth]vfs.north);
+    \draw[arrow] ([xshift=0.3\textwidth]apps.south) -- node[right,desc] {\dots}
+        ([xshift=0.3\textwidth]vfs.north);
+    
+    \draw[line width = 2pt] (vfs) -- (dio);
+    \draw[line width = 2pt] (vfs) -- (pgc);
+    \draw[arrow] (apps) -| node[above, align = center, desc]
+        {mmap\\malloc} (pgc);
+    
+    \node[box, largeb, below = of vfs, fill = dat] (dmp)
+        {Device mapper (optional)};
+    \node[box, largeb, below = of dmp, fill = l2t] (blk)
+        {Block layer\\\scriptsize (maps BIOs to requests)};
+    
+    \draw[arrow] (pgc) |- node[desc, below] {BIOs (block IOs)} (dmp);
+    \draw[arrow] (dio) |- node[desc, below] {BIOs (block IOs)} (dmp);
+    \draw[arrow] (dmp) -- node[desc, left] {BIOs} (blk);
+    \draw[arrow] ([xshift=-0.05\textwidth]dmp.north) -- 
+        node[desc, left, pos = 1.0] {stackable} ++(0, 0.03\textwidth) --
+            ++(0.1\textwidth, 0) -- ++(0, -0.03\textwidth);
+    
+    \node[box, largeb, fill = reb, below = of blk] (drvrq)
+        {Block drivers\\\scriptsize (request based)};
+    \node[box, smallb, fill = reb, right = of drvrq] (drvbio)
+        {Block drivers\\\scriptsize (BIO based)};
+    
+    \draw[arrow] (blk) -- node[desc, right] {Requests} (drvrq);
+    \draw[arrow] (dmp.south)++(0, -0.03\textwidth) -|
+        node[desc, right, pos=0.725] {BIOs} (drvbio);
+    
+    \node[box, fill = gray!15, below = of drvrq.south west, anchor = north west,
+        minimum width = 0.9865\textwidth] (hw) {Physical or virtual devices};
+    
+    \draw[arrow] (drvrq) -- (drvrq |- hw.north);
+    \draw[arrow] (drvbio) -- (drvbio |- hw.north);
+\end{tikzpicture}
\ No newline at end of file
diff --git a/presentation/images/qcow2_addressing.tex b/presentation/images/qcow2_addressing.tex
new file mode 100644
index 0000000..f052248
--- /dev/null
+++ b/presentation/images/qcow2_addressing.tex
@@ -0,0 +1,63 @@
+%-------------------------------------------------------------------------------
+% qcow2_addressing.tex - addressing of QCOW2 data clusters as image
+%-------------------------------------------------------------------------------
+% author   : Manuel Bentele
+% date     : Aug 29, 2019
+% copyright: (c) 2019 Manuel Bentele
+%-------------------------------------------------------------------------------
+
+\begin{tikzpicture}[
+        arrow/.style = {-triangle 45},
+        datacluster/.style = {rectangle, draw, fill = dat,
+            minimum width = 0.1\textwidth, minimum height = 0.1\textheight},
+        heading/.style = {font = \Large}
+    ]
+    \node[inner sep = 0, anchor = north] (l1table) at (0, 0) {
+        \begin{tabular}{|p{0.25\textwidth}|} \hline
+            \cellcolor{dat} \\ \hline
+                            \\ \hline
+            \cellcolor{dat} \\ \hline
+                            \\ \hline
+        \end{tabular}
+    };
+
+    \node[inner sep = 0, anchor = north] (l2table1) at (0.5\textwidth, 0) {
+        \begin{tabular}{|p{0.25\textwidth}|} \hline
+                            \\ \hline
+                            \\ \hline
+            \cellcolor{dat} \\ \hline
+                            \\ \hline
+            \cellcolor{dat} \\ \hline
+        \end{tabular}
+    };
+
+    \node[inner sep = 0, below = 0.75 of l2table1] (l2table2) {
+        \begin{tabular}{|p{0.25\textwidth}|} \hline
+                            \\ \hline
+            \cellcolor{dat} \\ \hline
+            \cellcolor{dat} \\ \hline
+                            \\ \hline
+            \cellcolor{dat} \\ \hline
+        \end{tabular}
+    };
+
+    \node[inner sep = 0, anchor = north, datacluster] (data1) at (0.9\textwidth, 0) {};
+    \node[inner sep = 0, below = 0.5 of data1, datacluster] (data2) {};
+    \node[inner sep = 0, below = 0.5 of data2, datacluster] (data3) {};
+    \node[inner sep = 0, below = 0.5 of data3, datacluster] (data4) {};
+    \node[inner sep = 0, below = 0.5 of data4, datacluster] (data5) {};
+
+    \node[above = 0.5 of l1table, heading]  {L1~table};
+    \node[above = 0.5 of l2table1, heading] {L2~tables};
+    \node[above = 0.5 of data1, heading]    {Data clusters};
+    
+
+    \draw[arrow] ($(l1table.north east)!0.125!(l1table.south east)$) -- ($(l2table1.north west)!0.1!(l2table1.south west)$);
+    \draw[arrow] ($(l1table.north east)!0.625!(l1table.south east)$) -- ($(l2table2.north west)!0.1!(l2table2.south west)$);
+    
+    \draw[arrow] ($(l2table1.north east)!0.5!(l2table1.south east)$) -- (data1.west);
+    \draw[arrow] ($(l2table1.north east)!0.9!(l2table1.south east)$) -- (data2.west);
+    \draw[arrow] ($(l2table2.north east)!0.3!(l2table2.south east)$) -- (data3.west);
+    \draw[arrow] ($(l2table2.north east)!0.5!(l2table2.south east)$) -- (data4.west);
+    \draw[arrow] ($(l2table2.north east)!0.9!(l2table2.south east)$) -- (data5.west);
+\end{tikzpicture}
\ No newline at end of file
diff --git a/presentation/images/qcow2_performance.tex b/presentation/images/qcow2_performance.tex
new file mode 100644
index 0000000..e5849e9
--- /dev/null
+++ b/presentation/images/qcow2_performance.tex
@@ -0,0 +1,36 @@
+%-------------------------------------------------------------------------------
+% qcow2_performance.tex - shows how QCOW2 performs compared to qemu-nbd
+%-------------------------------------------------------------------------------
+% author   : Manuel Bentele
+% date     : Aug 31, 2019
+% copyright: (c) 2019 Manuel Bentele
+%-------------------------------------------------------------------------------
+
+\begin{tikzpicture}
+    \pgfplotstableread[
+        col sep = semicolon

+    ]{../measurements/fio_results.csv}\resultdata
+    \begin{axis}[
+            height = 5cm,
+            width = 0.95\textwidth,
+            ybar,
+            ymin = 0.75,
+            ymax = 4.25,
+            ylabel = {Throughput gain factor},
+            legend cell align = {left},
+            ymajorgrids,
+            x tick label style = {rotate = 30, anchor = north east,
+                align = right},
+            xticklabels from table={\resultdata}{Type},
+            xtick = data,
+            axis lines = left,
+            enlarge x limits = 0.1,
+        ]
+    
+        \addplot table[y = {Factor_512}, x expr=\coordindex]{\resultdata};
+        \addlegendentry{512~byte operation};
+    
+        \addplot table[y = {Factor_4096}, x expr=\coordindex]{\resultdata};
+        \addlegendentry{4096~byte operation};
+    \end{axis}
+\end{tikzpicture}
\ No newline at end of file
diff --git a/presentation/images/qcow2_reading.tex b/presentation/images/qcow2_reading.tex
new file mode 100644
index 0000000..ed11d93
--- /dev/null
+++ b/presentation/images/qcow2_reading.tex
@@ -0,0 +1,55 @@
+%-------------------------------------------------------------------------------
+% qcow2_reading.tex - shows how QCOW2 clusters are mapped for reading
+%-------------------------------------------------------------------------------
+% author   : Manuel Bentele
+% date     : Aug 29, 2019
+% copyright: (c) 2019 Manuel Bentele
+%-------------------------------------------------------------------------------
+
+\begin{tikzpicture}[
+        arrow/.style = {-triangle 45}
+    ]
+    \node[inner sep = 0, anchor = north] (blkdev) at (0, 0) {
+        \renewcommand*{\arraystretch}{1.3}
+        \begin{tabular}{|c|} \hline
+                            \\ \hline
+                            \\ \hline
+                            \\ \hline
+                            \\ \hline
+            \cellcolor{dat} \\ \hline
+                            \\ \hline
+            \cellcolor{dat} \\ \hline
+            \cellcolor{dat} \\ \hline
+                            \\ \hline
+            \cellcolor{dat} \\ \hline
+        \end{tabular}
+    };
+
+    \node[inner sep = 0, anchor = north, right = of blkdev] (qcow2) {
+        \renewcommand*{\arraystretch}{1.3}
+        \hspace*{-0.25cm}
+        \begin{tabular}{|c|} \hline
+            \cellcolor{hdr}Header         \\ \hline
+            \cellcolor{ret}Refcount table \\ \hline
+            \cellcolor{reb}Refcount block \\ \hline
+            \cellcolor{l1t}L1~table       \\ \hline
+            \cellcolor{l2t}L2~table       \\ \hline
+            \cellcolor{dat}Data cluster   \\ \hline
+            \cellcolor{l2t}L2~table       \\ \hline
+            \cellcolor{dat}Data cluster   \\ \hline
+            \cellcolor{dat}Data cluster   \\ \hline
+            \cellcolor{dat}Data cluster   \\ \hline
+        \end{tabular}
+    };
+
+    \draw[triangle 45-triangle 45] ($(blkdev.north west)!0!(blkdev.south west)$) -- node[left] {$O$} ($(blkdev.north west)!0.6!(blkdev.south west)$);
+    \draw[triangle 45-triangle 45] ($(blkdev.north west)!0.6!(blkdev.south west)$) -- node[left] {$S$} ($(blkdev.north west)!0.8!(blkdev.south west)$);
+
+    \node[above = 0.5 of blkdev, align = center] {Block\\device};
+    \node[above = 0.5 of qcow2, align = center] {QCOW2\\file format};
+
+    \draw[arrow] ($(blkdev.north east)!0.45!(blkdev.south east)$) -- ($(qcow2.north west)!0.75!(qcow2.south west)$);
+    \draw[arrow] ($(blkdev.north east)!0.65!(blkdev.south east)$) -- ($(qcow2.north west)!0.55!(qcow2.south west)$);
+    \draw[arrow] ($(blkdev.north east)!0.75!(blkdev.south east)$) -- ($(qcow2.north west)!0.85!(qcow2.south west)$);
+    \draw[arrow] ($(blkdev.north east)!0.95!(blkdev.south east)$) -- ($(qcow2.north west)!0.95!(qcow2.south west)$);
+\end{tikzpicture}
\ No newline at end of file
diff --git a/presentation/images/qcow2_structure.tex b/presentation/images/qcow2_structure.tex
new file mode 100644
index 0000000..861527b
--- /dev/null
+++ b/presentation/images/qcow2_structure.tex
@@ -0,0 +1,21 @@
+%-------------------------------------------------------------------------------
+% qcow2_structure.tex - structure of the QCOW2 disk image file format as image
+%-------------------------------------------------------------------------------
+% author   : Manuel Bentele
+% date     : Aug 29, 2019
+% copyright: (c) 2019 Manuel Bentele
+%-------------------------------------------------------------------------------
+
+\renewcommand*{\arraystretch}{1.3}
+\begin{tabular}{|c|} \hline
+    \cellcolor{hdr}Header         \\ \hline
+    \cellcolor{ret}Refcount table \\ \hline
+    \cellcolor{reb}Refcount block \\ \hline
+    \cellcolor{l1t}L1~table       \\ \hline
+    \cellcolor{l2t}L2~table       \\ \hline
+    \cellcolor{dat}Data cluster   \\ \hline
+    \cellcolor{l2t}L2~table       \\ \hline
+    \cellcolor{dat}Data cluster   \\ \hline
+    \cellcolor{dat}Data cluster   \\ \hline
+    \vdots
+\end{tabular}
\ No newline at end of file
diff --git a/presentation/presentation.pdf b/presentation/presentation.pdf
new file mode 100644
index 0000000..64fd944
--- /dev/null
+++ b/presentation/presentation.pdf
diff --git a/presentation/presentation.tex b/presentation/presentation.tex
new file mode 100644
index 0000000..b86129c
--- /dev/null
+++ b/presentation/presentation.tex
@@ -0,0 +1,229 @@
+%-------------------------------------------------------------------------------
+% presentation.tex - presentation of the QCOW2 in-kernel project
+%-------------------------------------------------------------------------------
+% author   : Manuel Bentele
+% date     : Aug 26, 2019
+% copyright: (c) 2019 Manuel Bentele
+%-------------------------------------------------------------------------------
+
+\documentclass[english]{beamer}
+
+%-------------------------------------------------------------------------------
+% Presentation theme settings
+%-------------------------------------------------------------------------------
+\usetheme{Malmoe}
+\usecolortheme{beaver}
+\useinnertheme{rounded}
+
+%-------------------------------------------------------------------------------
+% Used packages
+%-------------------------------------------------------------------------------
+\usepackage{colortbl}
+\usepackage{xcolor}
+\usepackage{hyperref}
+\usepackage{tikz}
+\usetikzlibrary{positioning, calc, arrows}
+\usepackage{pgfplots}
+\usepackage{pgfplotstable}
+\pgfplotsset{compat = newest}
+\usepackage{pifont}
+
+%-------------------------------------------------------------------------------
+% Custom macros and definitions
+%-------------------------------------------------------------------------------
+\makeatletter\let\frametextheight\beamer@frametextheight\makeatother
+
+\newcommand{\cmark}{\ding{51}}
+\newcommand{\xmark}{\ding{55}}
+
+\colorlet{hdr}{green!15}
+\colorlet{ret}{yellow!15}
+\colorlet{reb}{orange!15}
+\colorlet{l1t}{red!15}
+\colorlet{l2t}{violet!15}
+\colorlet{dat}{cyan!15}
+
+%-------------------------------------------------------------------------------
+% General definitions
+%-------------------------------------------------------------------------------
+\title{QCOW2 in the Linux kernel}
+\author[M. Bentele]{Manuel Bentele}
+\institute{University of Freiburg}
+\date{September 2, 2019}
+
+\begin{document}
+
+\begin{frame}
+    \maketitle
+\end{frame}
+
+\section{Analysis}
+\subsection{Requirements}
+\begin{frame}{What has to be done?}
+    \begin{block}{Implement the QCOW (QEMU Copy On Write) disk file format version~2 in the Linux kernel such that \dots}
+        \vspace*{0.5cm}
+        \begin{itemize}
+            \item reading of the normal QCOW2 disk file format is possible
+            \item compressed \& sparse QCOW2 disk files are supported as well
+            \item the disk file format is exposed as block device
+            \item the implementation compiles \& runs under Linux kernel 5 later
+            \item the performance is better than using qemu-nbd
+        \end{itemize} 
+    \end{block}
+\end{frame}
+
+\subsection{Linux storage stack}
+\begin{frame}{How does the Linux storage stack looks like?}
+    \begin{center}
+        \resizebox{!}{0.775\textheight}{
+            \input{images/linux_storage_stack}
+        }
+    \end{center}
+\end{frame}
+
+\subsection{Implementation approaches}
+\begin{frame}{How can the implementation be achieved?}
+    \begin{block}{\xmark\ FUSE (Filesystem in Userspace) driver}
+        \begin{itemize}
+            \item implement reading of QCOW2 file format as user space driver
+        \end{itemize}
+    \end{block}
+    \begin{block}{\xmark\ Device mapper target}
+        \begin{itemize}
+            \item implement reading of QCOW2 file format as mapped target
+        \end{itemize}
+    \end{block}
+    \begin{block}{\xmark\ Custom block driver}
+        \begin{itemize}
+            \item create block driver \& configuration utility for reading QCOW2
+        \end{itemize}
+    \end{block}
+    \begin{block}{\cmark\ Loop device module extension}
+        \begin{itemize}
+            \item extend the loop device module \& configuration utility by a file format subsystem to implement QCOW2 as additional file format driver
+        \end{itemize}
+    \end{block}
+\end{frame}
+
+\section{Implementation}
+\subsection{Loop device module extension}
+\begin{frame}{How is the file format subsystem integrated?}
+    \resizebox{\textwidth}{!}{%
+        \input{images/file_fmt_subsystem_integration}
+    }
+    \vfill
+    \begin{itemize}
+        \item file format subsystem abstracts the direct access to backing files to implement various file formats
+        \item file formats are implemented as file format drivers
+        \item drivers are registered at the subsystem
+        \item subsystem supports (asynchronous) reads, (asynchronous) writes, flushes and virtual disk sizes
+    \end{itemize}
+\end{frame}
+
+\begin{frame}[fragile, shrink=35]{How does a file format driver look like?}
+\begin{verbatim}
+#include "loop_file_fmt.h"
+
+static int drv_file_fmt_read(struct loop_file_fmt *lo_fmt,
+                             struct request *rq) {
+    /* TODO: implement reading of file format */
+    return -EIO;
+}
+
+static struct loop_file_fmt_ops drv_file_fmt_ops = {
+    .read = drv_file_fmt_read
+};
+    
+static struct loop_file_fmt_driver drv_file_fmt = {
+    .name = "DRV",
+    .file_fmt_type = LO_FILE_FMT_RAW,
+    .ops = &drv_file_fmt_ops,
+    .owner = THIS_MODULE
+};
+
+// register driver with loop_file_fmt_register_driver(&drv_file_fmt)
+// unregister driver with loop_file_fmt_unregister_driver(&drv_file_fmt)
+\end{verbatim}
+\end{frame}
+
+\subsection{QCOW2 file format driver}
+\begin{frame}{How is the QCOW2 disk file format structured?}
+    \begin{columns}
+        \begin{column}[c]{0.25\textwidth}
+            \resizebox{\textwidth}{!}{%
+                \input{images/qcow2_structure}
+            }
+        \end{column}
+        \begin{column}[c]{0.75\textwidth}
+            \begin{itemize}
+                \item data is saved in data clusters of equal size (512\,B -- 2\,MB)
+                \item header provides offsets to 1st level tables
+                \item two-level lookup of data clusters (L1 \& L2~tables)
+                \item two-level reference count for copy on write (Refcount \& Refcount block tables)
+                \item numbers are stored in big-endian order
+                \item data clusters can be compressed or encrypted
+                \item support of embedded snapshots by use of internal copy on write
+            \end{itemize}
+        \end{column}
+    \end{columns}
+\end{frame}
+
+\begin{frame}{How does QCOW2 addresses data clusters?}
+    \begin{itemize}
+        \item QCOW2 header stores an offset in the file to the L1~table
+        \item L1~table stores offsets in the file to L2 tables
+        \item L2~tables stores offsets in the file to the data clusters
+    \end{itemize}
+    \begin{center}
+        \resizebox{!}{0.55\textheight}{%
+            \input{images/qcow2_addressing}
+        }
+    \end{center}
+\end{frame}
+
+\begin{frame}{How does the QCOW2 driver read data?}
+    \begin{columns}
+        \begin{column}[c]{0.4\textwidth}
+            \resizebox{\textwidth}{!}{%
+                \input{images/qcow2_reading}
+            }
+        \end{column}
+        \begin{column}[c]{0.6\textwidth}
+            Given a Linux IO read request with size $S$ and block device offset $O$:
+            \begin{enumerate}
+                \item calculate cluster $C$ and position $P$ for $O$ using cached L1 \& L2~tables
+                \item decompress the data of $C$ if $C$ is compressed
+                \item read data from $P$ into IO read request until $S$ bytes or the end of $C$ is reached
+                \item repeat steps 1 -- 3 until IO read request is filled with $S$ bytes
+            \end{enumerate}
+        \end{column}
+    \end{columns}
+\end{frame}
+
+\subsection{Performance of the driver}
+\begin{frame}{How does the implementation perform compared to qemu-nbd?}
+    \resizebox{\textwidth}{!}{
+        \input{images/qcow2_performance}
+    }
+\end{frame}
+
+\section{Outlook}
+\subsection{Further work}
+\begin{frame}{What can be done in the future?}
+    \begin{block}{File format subsystem}
+        \begin{itemize}
+            \item implement other file formats, e.g. VDI, VMDK, \dots
+            \item extend the API to support snapshots \& encryption
+        \end{itemize}
+    \end{block}
+    \begin{block}{QCOW2 file format driver}
+        \begin{itemize}
+            \item implement write operations
+            \item implement encryption \& snapshot support
+            \item improve performance by hardware aligned cache allocation
+            \item add a QCOW2 L2 cache clean interval
+        \end{itemize}
+    \end{block}
+\end{frame}
+
+\end{document}