Index: user/glebius/course/05.memory/lection.tex
===================================================================
--- user/glebius/course/05.memory/lection.tex	(revision 256996)
+++ user/glebius/course/05.memory/lection.tex	(revision 256997)
@@ -1,853 +1,853 @@
 \documentclass{beamer}
 
 \usepackage[utf8]{inputenc}
 \usepackage[russian]{babel}
 \usepackage{tikz}
 \usepackage{url}
 \usepackage{xcolor}
 \usepackage{listings}
 \usepackage{verbatim}
 \usepackage{ifthen}
 \usepackage{bytefield}
 \usepackage{wasysym}
 
 \usetikzlibrary{positioning}
 \usetikzlibrary{shapes}
 \usetikzlibrary{arrows}
 \usetikzlibrary{decorations.text}
 \usetikzlibrary{patterns}
 \usetikzlibrary{chains}
 \usetikzlibrary{scopes}
 \usetikzlibrary{calc}
 
 \input{../course.tex}
 
 \title{Memory management in FreeBSD}
 
 \tikzset {
 	entry/.style={draw, thick, on chain, text width=.25\paperwidth,
 		      align=center},
 	large/.style={entry, minimum height=.15\paperheight},
 	noentry/.style={entry, fill=gray, shading=axis, shading angle=45},
 	nolarge/.style={large, fill=gray, shading=axis, shading angle=45},
 	page/.style={draw, thick, node distance=3mm},
 	vmmap/.style={draw, thick, rounded corners},
 	vmentry/.style={draw, thick, rounded corners},
 	vmobject/.style={draw, thick, rounded corners, text width=7ex },
 	pointer/.style={->, thick, rounded corners},
 }
 
 \begin{document}
 
 \begin{frame}
 \titlepage
 \end{frame}
 
 
 \begin{frame}
 \frametitle{Process (static) address space}
 \begin{figure}
 \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \node [name=kernel, nolarge] { kernel };
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, large] { stack };
     \node [name=unmap, nolarge] { not mapped memory };
     \node [name=heap, large] { heap };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
 
     \draw [<-] (kernel.north west) --
 	node [below] {\scriptsize{0xff \ldots ff}} +(-1.5cm, 0);
     \draw [<-] (null.south west) --
 	node [above] {\scriptsize{0x00}} +(-1.5cm, 0);
 \end{tikzpicture}
 \end{figure}
 \end{frame}
 
 \FootReferences{procstat(1)}{}
 \begin{frame}
 \frametitle{Process (static) address space}
 Try this out:
 \shellcmd{%
 \# /rescue/cat \&\\
 \lbrack1\rbrack 48141\\
 \# procstat -v \$!\\
 \begin{tabular}{rrrrrrrrrrr}
   PID &            START &              END & PRT  & RES & PRES & REF & SHD &   FL & TP & PATH \\
 48141 &         0x400000 &         0x96d000 & r-x  & 677 &    0 &   4 &   2 & CN-- & vn & /rescue/chio \\
 48141 &         0xb6d000 &         0xb94000 & rw-  &  38 &    0 &   1 &   0 & C--- & vn & /rescue/chio \\
 48141 &         0xb94000 &         0xdc8000 & rw-  &  21 &    0 &   1 &   0 & ---- & df & \\
 48141 &      0x800c00000 &      0x801400000 & rw-  &  81 &    0 &   1 &   0 & ---- & df & \\
 48141 &   0x7fffffbfe000 &   0x7fffffbff000 & ---  &   0 &    0 &   0 &   0 & ---- & -- & \\
 48141 &   0x7ffffffdf000 &   0x7ffffffff000 & rw-  &   4 &    0 &   1 &   0 & ---D & df & \\
 48141 &   0x7ffffffff000 &   0x800000000000 & r-x  &   0 &    0 &  67 &   0 & ---- & ph & \\
 \end{tabular}
 }
 \end{frame}
 
 
 \FootReferences{}{}
 \begin{frame}
 \frametitle{Stack grows implicitly}
 \begin{columns}
 \begin{column}{.4\paperwidth}
   \begin{figure}
   \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, large] { stack };
     \node [name=unmap, nolarge] { not mapped memory };
     \node [name=heap, large] { heap };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
 
     \draw (stack.south west) ++(0cm, -2mm) [<-] --
 	node [above] {\scriptsize{deref!}} +(-1.5cm, 0);
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \begin{column}{.2\paperwidth}
   \begin{tikzpicture}
     \draw [->, thick] (0,0) -- node [above] {\small{page fault}}
 	+(.2\paperwidth,0);
   \end{tikzpicture}
 \end{column}
 \begin{column}{.4\paperwidth}
   \begin{figure}
   \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, large, minimum height=.20\paperheight] { stack };
     \node [name=unmap, nolarge, minimum height=.10\paperheight]
 	{ not mapped memory };
     \node [name=heap, large] { heap };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
 
     \draw [thick] (stack.center) ++(-1cm,0) node (mark1) {}
 	[->] -- (mark1 |- stack.south);
     \draw [thick] (stack.center) ++(1cm,0) node (mark2) {}
 	[->] -- (mark2 |- stack.south);
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \end{columns}
 \end{frame}
 
 
 \FootReferences{sbrk(2)}{}
 \begin{frame}
 \frametitle{Heap grows explicitly (used to grow \smiley )}
 \begin{columns}
 \begin{column}{.4\paperwidth}
   \begin{figure}
   \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, large] { stack };
     \node [name=unmap, nolarge] { not mapped memory };
     \node [name=heap, large] { heap };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \begin{column}{.2\paperwidth}
   \begin{tikzpicture}
     \draw [->, thick] (0,0) -- node [above] {\small{sbrk(2)}}
 	+(.2\paperwidth,0);
   \end{tikzpicture}
 \end{column}
 \begin{column}{.4\paperwidth}
   \begin{figure}
   \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, large] { stack };
     \node [name=unmap, nolarge, minimum height=.10\paperheight]
 	{ not mapped memory };
     \node [name=heap, large, minimum height=.20\paperheight] { heap };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
 
     \draw [thick] (heap.center) ++(-1cm,0) node (mark1) {}
 	[->] -- (mark1 |- heap.north);
     \draw [thick] (heap.center) ++(1cm,0) node (mark2) {}
 	[->] -- (mark2 |- heap.north);
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \end{columns}
 \end{frame}
 
 
 \FootReferences{mmap(2)}{}
 \begin{frame}
 \frametitle{Mapping more on heap}
 \begin{columns}
 \begin{column}{.4\paperwidth}
   \begin{figure}
   \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, large] { stack };
     \node [name=unmap, nolarge] { not mapped memory };
     \node [name=heap, large] { heap };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \begin{column}{.2\paperwidth}
   \begin{tikzpicture}
     \draw [->, thick] (0,0) -- node [above] {\small{mmap(2)}}
 	+(.2\paperwidth,0);
   \end{tikzpicture}
 \end{column}
 \begin{column}{.4\paperwidth}
   \begin{figure}
   \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, large] { stack };
     \node [name=unmap1, nolarge, minimum height=.05\paperheight]
 	{ not mapped };
     \node [name=mmap, large, minimum height=.05\paperheight]
 	{ more heap };
     \node [name=unmap2, nolarge, minimum height=.05\paperheight]
 	{ not mapped };
     \node [name=heap, large] { heap };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \end{columns}
 \end{frame}
 
 
 \FootReferences{mmap(2), malloc(3), rtld(1)}{}
 \begin{frame}
 \frametitle{Modern process memory map}
 \begin{columns}
 \begin{column}{.5\paperwidth}
   \begin{figure}
   \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \tikzset {
 	large/.style={entry, minimum height=.1\paperheight},
     }
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, entry] { stack };
     \node [name=unmap1, nolarge] { not mapped };
     \node [name=mmap, entry] { malloc arena };
     \node [name=unmap2, nolarge] { not mapped };
     \node [name=lib, entry] { library };
     \node [name=unmap3, nolarge] { not mapped };
     \node [name=heap, entry] { ld-elf };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \begin{column}{.5\paperwidth}
 \begin{itemize}
   \item{program itself via mmap(2)}
   \item{dynamic libraries via mmap(2)}
   \item{malloc(3) arenas via mmap(2)}
 \end{itemize}
 \onslide<2-> {
     Try this out:
     \shellcmd{%
     \# /bin/cat \&\\
     \# procstat -v \$!\\
     }
     Or this:
     \shellcmd{%
     \# procstat -v \$\$\\
     }
 }
 \end{column}
 \end{columns}
 \end{frame}
 
 
 \FootReferences{}{}
 \begin{frame}
 \frametitle{VM space}
 \begin{figure}
 \begin{tikzpicture}[start chain=going below, node distance=0mm]
     \tikzset {
 	large/.style={entry, minimum height=.1\paperheight},
     }
     \node [name=argv, entry] { argv, envp };
     \node [name=stack, entry] { stack };
     \node [name=unmap1, nolarge] { not mapped };
     \node [name=mmap, entry] { malloc arena };
     \node [name=unmap2, nolarge] { not mapped };
     \node [name=lib, entry] { library };
     \node [name=unmap3, nolarge] { not mapped };
     \node [name=heap, entry] { ld-elf };
     \node [name=data, entry] { initialized data };
     \node [name=text, entry] { program text };
     \node [name=null, noentry] { };
 
     \node [name=vmspace, draw, thick, color=red, ellipse,
 	  minimum width=.35\paperwidth,
 	  minimum height=.8\paperheight] at (lib.north) {};
     \node [ellipse callout, draw, color=red,
 	   callout absolute pointer={(node cs:name=vmspace, angle=40)},
 	   node distance=5mm, right=of stack] { vm\_map };
 
     \node [name=vmentry, draw, thick, color=red, ellipse,
 	  minimum width=.30\paperwidth,
 	  minimum height=2em] at (lib.center) {};
     \node [ellipse callout, draw, color=red,
 	   callout absolute pointer={(node cs:name=vmentry, angle=2)},
 	   node distance=7mm, right=of unmap2] { vm\_map\_entry };
 \end{tikzpicture}
 \end{figure}
 \end{frame}
 
 
 \FootReferences{}{sys/vm/vm\_map.h}
 \begin{frame}
 \frametitle{Kernel representation of VM space}
 \begin{figure}
 \small\begin{tikzpicture}
   \node [name=vmspace, struct, rectangle split parts=3] {
 	\textbf{struct vmspace}
 	\nodepart{two} struct vm\_map
 	\nodepart{three} struct vm\_pmap
   };
   \node [name=vmmap, struct, right=of vmspace, rectangle split parts=4] {
 	\textbf{struct vm\_map}
 	\nodepart{two} struct vm\_map\_entry header
 	\nodepart{three} struct vm\_map\_entry \*tree
 	\nodepart{four} \ldots
   };
   \node [name=entry1, struct, below=of vmspace, rectangle split parts=5] {
 	\textbf{struct vm\_map\_entry}
 	\nodepart{two} struct vm\_map\_entry *next
 	\nodepart{three} vm\_offset\_t start
 	\nodepart{four} vm\_offset\_t end
 	\nodepart{five} \ldots
   };
   \node [name=entry2, struct, right=of entry1, rectangle split parts=5] {
 	\textbf{struct vm\_map\_entry}
 	\nodepart{two} struct vm\_map\_entry *next
 	\nodepart{three} vm\_offset\_t start
 	\nodepart{four} vm\_offset\_t end
 	\nodepart{five} \ldots
   };
 
   \node [name=mark, node distance=5mm, above left=of entry1] {};
   \draw [pointer] (vmmap.two east) -- ++(5mm,0)
 	|- (mark.center) |- (entry1.one west);
 
   \draw [->, thick] (entry1.two east) to [out=0, in=180] (entry2.one west);
   \draw [pointer] (entry2.two east) --
 	++(5mm,0) -- ++(0,-1cm);
 \end{tikzpicture}
 \end{figure}
 \end{frame}
 
 
 \FootReferences{}{sys/vm/vm\_map.h, sys/vm/vm\_object.h}
 \begin{frame}
 \frametitle{A VM map entry is backed by an object}
 \begin{figure}
 \begin{tikzpicture}
   \node [name=entry, struct, rectangle split parts=4] {
 	\textbf{struct vm\_map\_entry}
 	\nodepart{two} \ldots
 	\nodepart{three} struct vm\_object *object
 	\nodepart{four} \ldots
   };
   \node [name=object, struct, right=of entry, rectangle split parts=5] {
 	\textbf{struct vm\_object}
 	\nodepart{two} \ldots
 	\nodepart{four} union *pager
 	\nodepart{three} struct vm\_radix rtree
 	\nodepart{five} \ldots
   };
 
   \draw [->, thick] (entry.three east) to [out=0, in=180] (object.one west);
 
   \node [name=page1, page, below=of object] { vm\_page };
   \draw [->, thick, rounded corners] (object.three east) -- ++(1cm,0)
 	|- (page1.east);
 
   \node [name=page2, page, below right=of page1] { vm\_page };
   \node [name=page3, page, below left=of page1] { vm\_page };
   \draw [->,thick] (page1.south) to [out=290, in=180] (page2.west);
   \draw [->,thick] (page1.south) to [out=250, in=0] (page3.east);
 
   \node [name=page4, page, below right=of page3] { vm\_page };
   \node [name=page5, page, below left=of page3] { vm\_page };
   \draw [->,thick] (page3.south) to [out=290, in=180] (page4.west);
   \draw [->,thick] (page3.south) to [out=250, in=0] (page5.east);
 
   \node [name=page6, page, below right=of page5] { vm\_page };
   \node [name=page7, page, below left=of page5] { vm\_page };
   \draw [->,thick] (page5.south) to [out=290, in=180] (page6.west);
   \draw [->,thick] (page5.south) to [out=250, in=0] (page7.east);
 
   \node [name=page8, page, below right=of page4] { vm\_page };
   \draw [->,thick] (page4.south) to [out=290, in=180] (page8.west);
 
 \end{tikzpicture}
 \end{figure}
 \end{frame}
 
 
 \FootReferences{}{sys/vm/vm\_page.h, sys/vm/vm\_page.c}
 \begin{frame}
 \frametitle{VM page}
   \begin{itemize}
     \item{Small structure describing one resident physical page}
     \item{All vm\_page structs are allocated at boot time}
     \item{A page belongs to one object}
   \end{itemize}
 \end{frame}
 
 
 \FootReferences{}{sys/vm/vm\_pager.h, sys/vm/vm\_pager.c}
 \begin{frame}
 \frametitle{VM objects' pager}
 \begin{columns}
 \begin{column}{.5\paperwidth}
   \begin{itemize}
     \item{Object serves as cache of memory page}
     \item{Pager implements particular cache in/cache out semantics}
   \end{itemize}
 \end{column}
 \begin{column}{.5\paperwidth}
   \begin{figure}
   \begin{tikzpicture}
      \node [struct, rectangle split parts=7] {
 	\textbf{struct pagerops}
 	\nodepart{two} pgo\_init\_t      *pgo\_init
 	\nodepart{three} pgo\_alloc\_t     *pgo\_alloc
 	\nodepart{four} pgo\_dealloc\_t   *pgo\_dealloc
 	\nodepart{five} pgo\_getpages\_t  *pgo\_getpages
 	\nodepart{six} pgo\_putpages\_t  *pgo\_putpages
 	\nodepart{seven} pgo\_haspage\_t   *pgo\_haspage
      };
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \end{columns}
 \end{frame}
 
 
 \FootReferences{}{sys/vm/vm\_object.h, sys/vm/vm\_object.c,
 		  sys/vm/default\_pager.c, sys/vm/swap\_pager.c}
 \begin{frame}
 \frametitle{Anonymous object}
 \begin{columns}
 \begin{column}{.5\paperwidth}
   \begin{figure}
   \begin{tikzpicture}
       \node [name=object, struct, rectangle split parts=5] {
 	\textbf{struct vm\_object}
 	\only<1> { \nodepart{two} \textit{uses default pager} }
 	\only<2,3> { \nodepart{two} \textit{{\color{red}uses swap pager}}}
 	\nodepart{three} \ldots
 	\nodepart{four} struct vm\_radix rtree
 	\nodepart{five} \ldots
       };
       \node [name=page1, page, below right=of object] {vm\_page};
       \draw [pointer] (object.five east) -| (page1.north);
       \only<1,2> {
         \node [name=page2, page, node distance=0, below=of page1] {vm\_page};
         \node [name=page3, page, node distance=0, below=of page2] {vm\_page};
       }
       \only<2> {
 	\node [name=swap, draw, rounded corners, fill=gray, shading=axis,
 	  left=of page3, xshift=-2em]
 	  {swap partition};
 	\node [name=ell, draw, thick, color=red, ellipse,
 	  minimum width=12ex, minimum height=4em] at (page2.south) {};
 	\draw [->, thick, color=red]
 	  (node cs:name=ell, angle=235) to [out=235, in=315]
 	  node [above] { swap out } (swap.south);
       }
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \begin{column}{.4\paperwidth}
   \begin{itemize}
     \item{Anonymous object usually backs vm\_map\_entry made by sbrk(),
 	  or mmap(MAP\_ANON), or stack}
     \item{Default pager is a nop}
     \onslide<2-> {
       \item{In case of memory pressure default pages is changed to swap pager}
     }
     \onslide<3-> {
       \item{Object remains with swap pager forever}
     }
   \end{itemize}
 \end{column}
 \end{columns}
 \end{frame}
 
 
 \FootReferences{}{sys/vm/vm\_object.h, sys/vm/vm\_object.c,
 		  sys/vm/vnode\_pager.c}
 \begin{frame}
 \frametitle{Vnode backed object}
 \begin{columns}
 \begin{column}{.5\paperwidth}
   \begin{figure}
   \begin{tikzpicture}
       \node [name=object, struct, rectangle split parts=6] {
 	\textbf{struct vm\_object}
 	\nodepart{two} uses vnode pager
 	\nodepart{three} \ldots
 	\nodepart{four} void *handle
 	\nodepart{five} struct vm\_radix rtree
 	\nodepart{six} \ldots
       };
       \node [name=vnode, struct, below=of object.south west, anchor=west,
 	     rectangle split parts=1] {
 	\textbf{struct vnode}
       };
       \draw [->, thick] (object.four west) to [out=180, in=180]
 	(vnode.one west);
       \node [name=file, draw, rounded corners, fill=gray, shading=axis,
 	     below=of vnode] {a file};
       \draw [->, thick] (vnode) -- (file);
       \node [name=page1, page, below right=of object] {vm\_page};
       \node [name=page2, page, node distance=0, below=of page1] {vm\_page};
       \node [name=page3, page, node distance=0, below=of page2] {vm\_page};
       \draw [pointer] (object.five east) -| (page1.north);
       \only<2> {
         \node [name=page4, page, color=red, node distance=0, below=of page3]
 	   {vm\_page};
 	\draw [->, thick, color=red] (file.east) to [out=0, in=270]
 	  node [pos=.3, above, sloped] { page in } (page4.south);
       }
       \only<3> {
 	\node [name=ell, draw, thick, color=red, ellipse,
 	  minimum width=12ex, minimum height=2em] at (page2) {};
 	\draw [->, thick, color=red] (ell.west) to [out=180, in=0]
 	  node [below, sloped] { page out } (file.east);
       }
   \end{tikzpicture}
   \end{figure}
 \end{column}
 \begin{column}{.4\paperwidth}
   \begin{itemize}
     \item{Vnode object backs vm\_map\_entry made for program text, initialized
 	  data, dynamic library text/data or result of mmap() on a file}
     \onslide<2-> {
       \item{Page fault brings a page from the file into memory}
     }
     \onslide<3-> {
       \item{If mapping is {\color{red}writable and shared},
 	    dirty pages are written back to the file}
     }
   \end{itemize}
 \end{column}
 \end{columns}
 \end{frame}
 
 
 \FootReferences{}{sys/vm/vm\_object.h, sys/vm/vm\_object.c}
 \begin{frame}
 \frametitle<1>{Private mappings}
 \frametitle<2>{Private mappings: a process fork(2)s}
 \frametitle<3>{Private mappings: child modifies a page}
 \frametitle<4-5>{Private mappings: shadow chains can grow hairy}
 \frametitle<6-7>{Private mappings: shadow chain split}
 \frametitle<8-9>{Private mappings: shadow chain collapse}
 \begin{figure}
 \begin{tikzpicture}[node distance=2mm]
   \node [name=procA, vmmap] { process A };
   \node [name=entA, vmentry, below right=of procA] { vm\_map\_entry };
   \draw [pointer] (procA.south) |- (entA.west);
 
   \node [name=obj, vmobject, below right=2mm and .4\paperwidth of entA]
 	{ vnode object };
   \draw [pointer] (entA.east) -| (obj.north);
   \node [name=page1, page, below=of obj] {page 1};
   \draw [pointer] (obj) -- (page1);
   \node [name=page2, page, node distance=0, below=of page1] {page 2};
   \node [name=page3, page, node distance=0, below=of page2] {page 3};
 
   \onslide<2-7> {
     \node [name=procB, vmmap, below=.2\paperheight of procA] { process B };
     \node [name=entB, vmentry, below right=of procB] { vm\_map\_entry };
     \draw [pointer] (procB.south) |- (entB.west);
   }
 
   \only<2> {
     \draw [pointer] (entB.north) |- (node cs:name=obj, angle=200);
   }
 
   \onslide<3-> {
     \node [name=shadow, vmobject, above right=2mm and 10mm of entB]
 	{ shadow object };
     \draw [pointer] (shadow.east) to [out=0, in=180] (obj.west);
     \node [name=pageB1, page, below=of shadow] {page 1};
     \draw [pointer] (shadow) -- (pageB1);
   }
   \onslide<3-7> {
     \draw [pointer] (entB.north) |- (shadow.west);
   }
 
   \onslide<4-> {
     \node [name=procC, vmmap, below=.2\paperheight of procB] { process C };
     \node [name=entC, vmentry, below right=of procC] { vm\_map\_entry };
     \draw [pointer] (procC.south) |- (entC.west);
   }
 
   \only<4> {
     \node [name=mark, above right=of entC] {} ;
     \draw [pointer] (entC.north)
 	.. controls +(0,10mm) and (mark) .. (shadow.south west);
   }
 
   \onslide<5-8> {
     \node [name=shadowC, vmobject, below=.2\paperheight of shadow]
 	{ shadow object };
     \draw [pointer] (entC.north) |- (shadowC.west);
   }
   \onslide<5,8> {
     \node [name=pageC2, page, below=of shadowC] {page 2};
     \draw [pointer] (shadowC) -- (pageC2);
   }
   \onslide<5,6,8> {
     \draw [pointer] (shadowC.north west)
 	to [out=135, in=225] (shadow.south west);
   }
 
   \onslide<6-7> {
     \node [name=pageC1, page, below=of shadowC] {{\color{red}page 1}};
     \draw [pointer] (shadowC) -- (pageC1);
   }
 
   \onslide<7> {
     \draw [pointer, color=red] (shadowC.east)
 	to [out=0, in=225] (obj.south west);
   }
 
   \onslide<8> {
     \node [name=procB, vmmap, below=.2\paperheight of procA, dotted]
 	{ process B };
     \node [name=entB, vmentry, below right=of procB, dotted]
 	{ vm\_map\_entry };
     \draw [pointer, dotted] (procB.south) |- (entB.west);
     \draw [pointer, dotted] (entB.north) |- (shadow.west);
   }
 
   \onslide<9> {
     \draw [pointer, color=red] (entC.north) to [out=90, in=180] (shadow.west);
     \node [name=pageB2, page, node distance=0, below=of pageB1]
 	{{\color{red}page 2}};
   }
 \end{tikzpicture}
 \end{figure}
 \end{frame}
 
 
 \FootReferences{malloc(9),memguard(9),redzone(9)}{sys/kern/kern\_malloc.c}
 \begin{frame}
 \frametitle{kernel malloc(9)}
 \begin{figure}
 \begin{tikzpicture}[start chain=main going below,
                     node distance=3mm,
                     every join/.style={->, draw},
                     font=\scriptsize]
   \tikzset {
     base/.style={draw, thick, on chain, align=center, minimum height=4ex},
     proc/.style={base, rectangle},
     test/.style={base, diamond, aspect=3},
     term/.style={proc, rounded corners},
   }
 
   \node [name=entry, proc] {malloc(size)};
   \node [name=memguard, test, join] {memguard?};
   { [start branch=memguard going below]
     \node [name=guardalloc, proc, join] {v = memguard\_alloc()};
   }
   \node [name=pagesize, continue chain=going right, test, join]
 	{size <= page size};
   { [start branch=large going right]
     \node [name=largealloc, proc, join] {v = uma\_large\_malloc()};
   }
   \node [name=zone, continue chain=going below, proc, join]
 	{zone = min(power2(size))};
   \node [name=zalloc, proc, join] {v = uma\_zalloc(zone)};
   \node [name=mtp, proc, join] {malloc type accounting};
   \node [name=redzone, test, join] {redzone?};
   { [start branch=redzone going right]
     \node [name=redsetup, proc, join] {redzone\_setup(v)};
   }
   \node [name=return, term, join] {return v};
 
   \path (memguard.east) to node [yshift=1ex, red] {$no$} (pagesize);
   \path (memguard.south) to node [xshift=1em, green] {$yes$} (guardalloc);
   \draw [->,rounded corners] (guardalloc.south) |- (return.west);
   \path (pagesize.south) to node [xshift=1em, green] {$yes$} (zone);
   \path (pagesize.east) to node [yshift=1ex, red] {$no$} (largealloc);
   \draw [->,rounded corners] (largealloc.south) |- (mtp.east);
   \path (redzone.south) to node [xshift=1em, red] {$no$} (return);
   \path (redzone.east) to node [yshift=1ex, green] {$yes$} (redsetup);
   \draw [->,rounded corners] (redsetup.south) |- (return.east);
 \end{tikzpicture}
 \end{figure}
 \end{frame}
 
 
 \FootReferences{uma(9),vmstat(8)}{sys/vm/uma\_int.h,sys/vm/uma\_core.c}
 \begin{frame}
 \frametitle{uma(9): the zone allocator}
 Let's look at malloc(9) zones in UMA:
 \shellcmd{%
 \# vmstat -z \textbar~head -1 \&\& vmstat -z \textbar~egrep '\^~\lbrack0-9\rbrack+:'\\
 \begin{tabular}{rrrrrrrr}
 ITEM  &   SIZE  &  LIMIT  &  USED  &  FREE  &    REQ &FAIL &SLEEP \\
 16:   &     16, &      0, &  8055, &   479, &  30823,&   0,&   0 \\
 32:   &     32, &      0, &   706, &  1044, & 197057,&   0,&   0 \\
 64:   &     64, &      0, &  1905, &  8759, &3215548,&   0,&   0 \\
 128:  &    128, &      0, &  1463, &  5202, & 387198,&   0,&   0 \\
 256:  &    256, &      0, &   616, &  4304, & 757799,&   0,&   0 \\
 512:  &    512, &      0, &   426, &  3846, &  50371,&   0,&   0 \\
 1024: &   1024, &      0, &    80, &   116, &  70702,&   0,&   0 \\
 2048: &   2048, &      0, &    79, &    87, &  71207,&   0,&   0 \\
 4096: &   4096, &      0, &   193, &    49, &  78923,&   0,&   0 \\
 \end{tabular}
 }
 \end{frame}
 
 %
 % This ugly TikZ code is taken from my master thesis and needs to
 % be redesigned. Too much absolute node positioning here.
 %
 \newcommand{\structline}[2]{ #1 & #2 \\ }
 \FootReferences{uma(9)}{sys/vm/uma\_int.h, sys/vm/uma\_core.c}
 \begin{frame}
 \frametitle{uma(9) is a slab allocator}
 \begin{columns}
 \begin{column}{.03\paperwidth}
 \end{column}
 \begin{column}{.97\paperwidth}
 \begin{tikzpicture}[thick]
 \draw [rounded corners] (1.0cm, 0cm) -- (0cm, 0cm) -- (0cm, 3cm)
         -- (1.0cm, 3cm);
 \foreach \i in { 1, 2, 4, 5}
   \node (item\i) at (\i cm * 1.0, 0cm) [draw, anchor=south west,
    outer sep=0pt, minimum height=3cm, minimum width=1.0cm] {};
 \node (item3) at (3.0cm, 0cm) [anchor=south west,
    outer sep=0pt, minimum height=3cm, minimum width=1.0cm] { \ldots };
 % waste
 \draw [pattern=checkerboard light gray]
         (node cs:name=item5, anchor=north east) --
         (7cm, 3cm) -- (7cm, 0cm) --
         (node cs:name=item5, anchor=south east) -- cycle;
 % slab header
 \shadedraw [shading=axis,shading angle=45] (7cm, 0cm) -- (7cm, 3cm)
         { [rounded corners] -- (12cm, 3cm) -- (12cm, 0cm) } -- cycle;
 \draw (9.5cm, 1.5cm) node (slab) [rectangle split, rectangle split parts = 2,
 				   rounded corners, draw, fill=white] {
 	\textbf{struct uma\_slab}
 	\nodepart{two}
 	\begin{tabular}{ll}
 	\structline{uint8\_t}   {*us\_data}
 	\structline{slabbits}   {us\_free}
 	\ldots
 	\end{tabular}
 };
 % slab size
 \draw (12cm / 2, 3.25cm) node (sizelabel) {slab size (PAGE\_SIZE)};
 \draw [<-] (0cm, 3.25cm) -- (sizelabel.west);
 \draw [->] (sizelabel.east) -- (12cm, 3.25cm);
 % pointer
 \draw [fill] (node cs:name=slab,angle=5) circle (2pt);
 \draw [rounded corners, ->] (node cs:name=slab,angle=5) -| ++(0.25cm, -2cm) -|
         (0.55cm,0cm);
 \end{tikzpicture}
 \end{column}
 \end{columns}
 \end{frame}
 
 
 \begin{frame}
 \frametitle{uma(9) structures}
 \begin{columns}
 \begin{column}{.03\paperwidth}
 \end{column}
 \begin{column}{.97\paperwidth}
 \begin{tikzpicture}[node distance=5mm, font=\scriptsize]
   \node [name=keg, struct, rectangle split parts=4] {
     \textbf{struct uma\_keg}
-    \nodepart{two} LIST\_HEAD(,uma\_slab)    uk\_part\_slab
-    \nodepart{three} LIST\_HEAD(,uma\_slab)    uk\_free\_slab
+    \nodepart{two} LIST\_HEAD(,uma\_slab)    uk\_free\_slab
+    \nodepart{three} LIST\_HEAD(,uma\_slab)    uk\_part\_slab
     \nodepart{four} LIST\_HEAD(,uma\_slab)    uk\_full\_slab
   };
 
 \tikzset {
   slab/.style = {draw, thick, rounded corners,
 		  rectangle split, rectangle split draw splits=false,
 		  rectangle split horizontal, 
 		  minimum width=10ex, minimum height=3ex},
   fslab/.style = {slab,
 		  rectangle split part fill={struct!50, struct!50, struct!50,
 		  struct!50}},
   pslab1/.style = {slab,
 		  rectangle split part fill={struct!50, struct!50, white!50,
 		  white!50}},
   pslab2/.style = {slab,
 		  rectangle split part fill={struct!50, white!50, white!50,
 		  white!50}},
   eslab/.style = {slab,
 		  rectangle split part fill={white!50, white!50, white!50,
 		  white!50}},
 }
 	
   \node [name=fslab1, fslab,
 	 below=10mm of keg.south west, anchor=north west, xshift=-8mm] {};
   \node [name=fslab2, fslab, node distance=1mm, below=of fslab1] {};
   \node [name=fslab3, fslab, node distance=1mm, below=of fslab2] {};
   \node [name=fslab4, fslab, node distance=1mm, below=of fslab3] {};
   \node [name=pslab1, pslab1, right=of fslab1] {};
   \node [name=pslab2, pslab2, node distance=1mm, below=of pslab1] {};
   \node [name=eslab, eslab, right=of pslab1] {};
 
   \draw [pointer] (keg.four east) -- ++(1mm,0) -- +(0,-5mm) -| (fslab1.north);
   \draw [pointer] (keg.three east) -- ++(2mm,0) -- +(0,-14mm) -| (pslab1.north);
   \draw [pointer] (keg.two east) -- ++(3mm,0) -- +(0,-22mm) -| (eslab.north);
 
 \onslide<2-> {
   \node [name=zone, left=of keg, struct, rectangle split parts=4] {
     \textbf{struct uma\_zone}
     \nodepart{two} struct uma\_cache uz\_cpu\lbrack$ncpus$\rbrack
     \nodepart{three} LIST\_HEAD(,uma\_bucket)  uz\_buckets
     \nodepart{four} struct uma\_keg *uz\_keg
   };
   \node [name=cache, below=of zone.south west, anchor=north west,
          struct, rectangle split parts=3] {
     \textbf{struct uma\_cache}
     \nodepart{two} uma\_bucket\_t    uc\_freebucket
     \nodepart{three} uma\_bucket\_t    uc\_allocbucket
   };
   \node [name=bucket, below=of cache.south west, anchor=north west,
 	 struct, rectangle split parts=4] {
     \textbf{struct uma\_bucket}
     \nodepart{two} int16\_t ub\_cnt
     \nodepart{three} int16\_t ub\_entries
     \nodepart{four} void *ub\_bucket\lbrack\rbrack
   };
   \draw [pointer] (zone.two west) -- +(-3mm,0) |- (cache.one west);
   \draw [pointer] (cache.two west) -- +(-3mm,0) |- (bucket.one west);
   \draw [pointer] (zone.four east) to [out=0, in=180] (keg.one west);
 }
 \end{tikzpicture}
 \end{column}
 \end{columns}
 \end{frame}
 
 \end{document}