% LaTeX2e
% `Das Filesystem ext2, Modul Betriebssysteme 2009'
% 17. April 2009, Peter Schmid
% RCS-Id: $Id: ldap.tex,v 1.1 2008/10/31 08:22:35 pschmid Exp $

%\documentclass{beamer}
\documentclass[handout]{beamer}

\mode<presentation>
{
  \usetheme{Warsaw}

  \setbeamercovered{transparent}
}

\usepackage[german]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{alltt}

%\setbeameroption{show notes}

%---------------------------------------------------------------------

\title{Das Filesystem ext2}

\author{Peter Schmid}

\institute[HSZ-T] 
{
  Hochschule f\"u{}r Technik Z\"u{}rich\\
  Studiengang Informatik
}

\date[modbs08]{17.4.2009}

\pgfdeclareimage[height=0.5cm]{university-logo}{fig/hsz-logo}
\logo{\pgfuseimage{university-logo}}

%---------------------------------------------------------------------

\begin{document}

\begin{frame}

  \titlepage

\end{frame}

% ---------------------------------------------------------------------

\begin{frame}{Outline}

  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

% ---------------------------------------------------------------------


\section{Leistungsmerkmale}

\begin{frame}
  
  \frametitle{Leistungsmerkmale}
 
  \begin{itemize}
  \item<1-> Max file size: 2-64 TiB
  \item<2-> Max number of files: $10^{18}$
  \item<3-> Max filename length: 255 characters
  \item<3-> Max volume size: 16-32 TiB
  \item<4-> Allowed characters in filenames: Any byte except NUL and '/'
  \item<5-> Dates recorded
    \begin{itemize}
    \item<5-> modification (mtime)
    \item<5-> attribute modification (ctime)
    \item<5-> access (atime)
    \end{itemize}
  \item<6-> Date range: 14.12.1901 - 18.1.2038
  \item<7-> Free space: Bitmap
  \item<8-> Allocation: Index (Table)
  \end{itemize}

\end{frame}

% ---------------------------------------------------------------------

\section{Aufbau}


\subsection{Die "au"sere Struktur des ext2}

\begin{frame}
  
  \frametitle{Die "au"sere Struktur des ext2}

  Eine Gruppe ist max. 128 MB. Die ganze Disk (Partition) ist in
  gleich grosse Bl"ocke aufgeteilt, z.B. 1, 2, 4 oder 8 KB.

  \begin{itemize}
  \item Bootsektor (512 + 512 Bytes)
  \item Gruppe 0
  \item Gruppe 1
  \item ...
  \item Gruppe n
  \end{itemize}
  
  Anzeigen mit \texttt{dumpe2fs}

\end{frame}

% ---------------------------------------------------------------------


\subsection{Gruppen}

\begin{frame}
  
  \frametitle{Gruppen aka Blockgruppen}
  
  Aehnlich dem UNIX File System werden Zylindergruppen als Gruppen
  zusammengefasst, so dass die Seek-time minimiert wird. Daten sind
  nahe dem Inode.
  
  Jede Gruppe hat eine Kopie des Superblocks und der Deskriptoren. Struktur
  der Gruppe:
  
  \begin{itemize}
  \item Superblock 
  \item Gruppen-Deskriptoren
  \item Block Bitmap
  \item Inode Bitmap
  \item Inodes 
  \item Datenbl"ocke
  \end{itemize}
  
\end{frame}

\begin{frame}
  
  \frametitle{Aufbau Superblock (nicht komplett)}
  
ext2 Filesysteme starten mit dem Superblock (Offset 1024 Bytes). Superblock
ist 1024 Bytes gross.

\begin{tabular}{|l|l|l|}
\hline
\textbf{Offset} & \textbf{Length} & \textbf{Description} \\
\hline
0x00 & 4 & Total number of inodes \\
0x04 & 4 & Total number of blocks  \\
0x08 & 4 & Blocks reserved the super user \\
0x0C & 4 & Total number of free blocks \\
0x10 & 4 & Total number of free inodes \\
0x14 & 4 & First data block \\
0x18 & 4 & Block size \\
0x20 & 4 & Number of blocks per group \\
0x28 & 4 & Number of inodes per group \\
0x2C & 4 & Last time the file system was mounted \\
0x30 & 4 & Last write access to the file system \\
\hline
\end{tabular}

\end{frame}


\begin{frame}
  
  \frametitle{Gruppen-Deskriptoren}

Ist eine Tabelle von 32 Bytes grossen Deskriptoren. Jeder Deskriptor
beschreibt eine Blockgruppe. Block IDs sind absolut.

\begin{tabular}{|l|l|l|}
\hline
\textbf{Offset} & \textbf{Length} & \textbf{Description} \\
\hline
0x00 & 4 & Block id of the first block of the \emph{block bitmap} \\
0x04 & 4 & Block id of the first block of the \emph{inode bitmap} \\
0x08 & 4 & Block id of the first block of the \emph{inode table} \\
0x0C & 2 & Total number of free blocks \\
0x0E & 2 & Total number of free inodes \\
0x10 & 2 & Number of inodes allocated to directories \\
0x12 & 2 & Padding the structure on a 32bit boundary \\
0x14 & 12 & Reserved space for future revisions \\
\hline
\end{tabular}

\end{frame}


\begin{frame}
  
  \frametitle{Bitmaps}

  \begin{itemize}
  \item Ist das bit \textbf{0} so ist der Block/Inode frei
  \item ist das bit \textbf{1} so ist derBlock/Inode benutzt
  \item Das erste bit (LSB) des ersten Bytes ist für den ersten Block/Inode.
  \item Das zweite bit  des ersten Bytes ist für den zweiten Block/Inode.
  \item Das erste bit des zweiten Bytes ist für den neunten Block/Inode.

  \end{itemize}
\end{frame}


% ---------------------------------------------------------------------

\subsection{Inode (Indexknoten)}

\begin{frame}
  
  \frametitle{Inode (Indexknoten)}
  
  
  \begin{itemize}
  \item Jedes Objekt im Dateisystem wird durch einen Inode repr"asentiert
  \item Inode enth"alt Zeiger auf die Bl"ocke, in denen die Daten des Objekts sind
  \item Metadaten "uber ein Objekt mit Ausnahme seines Namens
  \item Inode Zeiger auf die ersten 12 Bl"ocke
  \item Inode Zeiger auf indirekten Block
  \item auf einen doppelt indirekten Block 
  \item auf einen dreifach indirekten Block 
  \item Inode ist 128 Bytes gross
  \item die ersten 11 Inodes in der Tabelle sind reserviert (Bad Blocks etc.)
  \end{itemize}

\end{frame}

\begin{frame}
  
  \frametitle{Aufbau Inode (nicht komplett)}
\begin{tabular}{|l|l|l|}
\hline
\textbf{Offset} & \textbf{Length} & \textbf{Description} \\
\hline
0x00 & 2 & Format and access rights of the file \\
0x02 & 2 & User id associated with the file  \\
0x04 & 4 & Size of the file in bytes \\
0x08 & 4 & Last time this inode was accessed \\
0x0C & 4 & Time when inode was created \\
0x10 & 4 & Last time this inode was modified \\
0x14 & 4 & Time when the inode was deleted \\
0x18 & 2 & Group id associated with the file \\
0x1A & 2 & Links count \\
0x1C & 4 & Number of blocks \\
0x28 & 48 & Direct pointers to the blocks (12) \\
0x58 & 4 & Indirect pointer to the blocks  \\
0x5C & 4 & Double indirect pointer to the blocks  \\
0x60 & 4 & Tripple indirect pointer to the blocks  \\
\hline
\end{tabular}

\end{frame}

\begin{frame}
  
  \frametitle{Inode lokalisieren}

Inodenummer $I$\\
Blockgruppe $B$\\
Lokaler Inode $I_L$\\
Anzahl Inodes pro Block $N$\\
Offset Inode $O_I$

$ B = \frac{I - 1} N $

$ I_L = (I - 1) \mod N $

Um den Offset zu bestimmen muss man noch $I_L$ mit 128 multiplizieren und den
Offset der Inodetabelle addieren.
 
\end{frame} 


% ---------------------------------------------------------------------

\subsection{Verzeichnisse}

\begin{frame}
  
  \frametitle{Verzeichnisse}

  \begin{itemize}
  \item ein Verzeichnis ist ein Dateisystemobjekt und hat wie eine
    normale Datei einen Inode
  \item eine spezielle Datei, die jeden Dateinamen im Verzeichnis mit
    einer Inode-Nummer verkn"upft
  \item man nennt das auch harter Link
  \item im Inode der Datei wird "uber die Anzahl der Verkn"upfungen Buch gef"uhrt
  \item erst wenn letzte Verkn"upfung gel"oscht, kann Dateiinhalt frei
    gegeben werden.
  \item zwei spezielle Verkn"upfungen werden immer erstellt: "."{} und ".."
  \end{itemize}
\end{frame} 


\begin{frame}
  
  \frametitle{Aufbau Verzeichnisse}
  Verkettete Liste von Einträgen. Ausgerichtet an 32 bit. Die Einträge sind
  wie folgt aufgebaut:

\begin{tabular}{|l|l|l|}
\hline
\textbf{Offset} & \textbf{Length} & \textbf{Description} \\
\hline
0x00 & 4 &  Inode number\\
0x04 & 2 &  Record length \\
0x06 & 1 &  Name length \\
0x07 & 1 &  File type \\
0x08 & 0 .. 255 &  File name\\

\hline
\end{tabular}

\end{frame} 

% ---------------------------------------------------------------------


\end{document}
