Finish realisierung

7 files changed, 167 insertions, 35 deletions

diff --git a/doc/class-assignment/realisierung/fbwarn.tex b/doc/class-assignment/realisierung/fbwarn.tex
index e69de29..097145d 100644
--- a/doc/class-assignment/realisierung/fbwarn.tex
+++ b/doc/class-assignment/realisierung/fbwarn.tex
@@ -0,0 +1,128 @@
+\subsection{fbwarn}
+Falls die Festplattenverifizierung Fehlschlägt, muss der Nutzer gewarnt werden (es ist auch möglich das Gerät einfach auszuschalten, jedoch sollte dies aus UX gründen nicht gemacht werden).
+
+\subsubsection{Grafischer Output}
+Die Warnung ist am besten grafisch zu tun, jedoch gibt es keinen display server wie Wayland oder X11, deshalb muss direkt auf den Framebuffer /dev/fb* geschrieben werden, um graphischen Output zu zeigen.\\
+Da jeder verfügbare framebuffer als /dev/fbX verfügbar ist, kann man ganz einfach die Datei öffnen und mit mmap manipulieren:
+
+\begin{minted}[fontsize=\footnotesize]{c}
+ // imports: stdlib, linux/fb.h, stdio
+ int main()
+ {
+     int fbfd = 0;
+     struct fb_var_screeninfo vinfo;
+     struct fb_fix_screeninfo finfo;
+     
+     // Open the framebuffer file for reading and writing
+     fbfd = open("/dev/fb0", O_RDWR);
+          
+     // Get fixed screen information
+     ioctl(fbfd, FBIOGET_FSCREENINFO, &finfo);
+     // Get variable screen information
+     ioctl(fbfd, FBIOGET_VSCREENINFO, &vinfo);
+  
+     // Map the device to memory
+     fbp = (char *)mmap(0, screensize, PROT_READ | PROT_WRITE, MAP_SHARED, fbfd, 0);
+ 
+     location = (300+vinfo.xoffset) * (vinfo.bits_per_pixel/8) + \
+                (100+vinfo.yoffset) * finfo.line_length;
+     *(fbp + location) = 100;        // Some blue
+     *(fbp + location + 1) = 50;     // A little green
+     *(fbp + location + 2) = 200;    // A lot of red
+     *(fbp + location + 3) = 0;      // No transparency
+
+     munmap(fbp, screensize);
+     close(fbfd);
+     return 0;
+ }
+\end{minted}
+Dies genügt, wenn man einfache Formen in den Framebuffer zeichnen möchte, wie im Bild zu sehen ist
+\begin{figure}[h]
+  \centering
+  \includegraphics[scale=0.7]{realisierung/images/framebuffer-rectangle.png}
+  \caption{C Programm welches einen Quadrat mit Gradient direkt in den Framebuffer schreibt}
+\end{figure}
+
+Jedoch wird es komplizierter, wenn man auch Text anzeigen möchte, da man jeden Pixel manuell schreiben muss welches bei Sätzen wie ``System Verification Failed'' bereits sehr umständlich ist.\\
+Deshalb ist eine bessere lösung nötig, eine Bibliothek die in den Framebuffer schreiben kann und alle Rendering funktionen abstrahiert. Die Bibliothek die ich benutzt habe ist Raylib, eine C bibliothek welche hauptsächlich für die Entwicklung von Spielen gedacht ist, jedoch, nicht wie andere Engines, keine besonderen Features hat, sondern jediglich verschiedene Aspekte wie Grafik, Physik und Audio abstrahiert. Glücklicherweise kann mit der Compilerflag \texttt{-DEGL\_NO\_X11} raylib so kompiliert werden, dass es direkt in den Framebuffer schreibt, anstatt versucht ein Fenster zu öffnen.
+\bigbreak \noindent
+\begin{figure}[h]
+  \centering
+  \includegraphics[scale=0.5]{realisierung/images/raylib-framebuffer.png}
+  \caption{Raylib Beispielprogramm \texttt{shapes\_basic\_shapes} in einer VM mit output direkt zum Framebuffer}
+\end{figure}
+
+Hiermit wird es um einiges Einfacher eigene Bilder zu erstellen, die angezeigt werden wenn nötig.
+
+\subsubsection{Grafikformat}
+Da es recht umständlich wär, das Bild immer manuell in C zu programmieren, ist es am besten ein Grafikformat zu benutzen welches extern geladen werden kann. Der erste gedanke wäre, einfach jpg-xl oder png bilder zu benutzen, jedoch sind Rasterbasierte Grafikformate hier nicht sehr nützlich, da die Warnung auf viele verschiedene Bildschirmgrößen angezeigt werden muss, also sind Vektorbasierten Grafikformate nötig. Die bekannteste wäre SVG, eine XML basiertes Format mit dem Bilder geschrieben werden können, die unendlich groß skaliert werden können. SVG ist jedoch sehr komplex und hat features die hier nicht nötig sind.\\
+Da ich kein Vektorbasiertes Grafikformat gefunden habe, welches auch sehr Simpel gehalten ist, habe ich mich entschlossen ein eigenes Format zu entwickeln.\\
+\\
+Das Format hat eine Funktionsbasierte Syntax, das heißt, dass im gegensatz zu SVG man einfach Funktionen aufruft um Formen zu zeichen oder Text zu schreiben:
+\begin{verbatim}
+rectangle (x=100,y=100,height=100,width=100,color="#FFFFFFFF",fill=true)
+\end{verbatim}
+Da diese art von Syntax sehr simpel zu Parsen ist, kann es alles direkt in POSIX-C implementiert werden, ohne externe Bibliotheken verwenden zu müssen.\\
+Der nächste Schritt ist festzulegen, welche Funktionen benötigt werden. Mit betracht auf die Unterstützten Funktionen in raylib, habe ich die folgenden Funktionen implementiert:
+\begin{itemize}
+\item IMG\\
+  Funktion um ein Bild zu Initialisieren, muss immer die erste Funktion in einem Bild sein.
+\item rectangle\\
+  Funktion um ein Rechteck zu zeichnen, unterstützt ausegfüllte und nicht ausgefüllte Rechtecke.
+\item roundedrectangle\\
+  Ein Rechteck aber mit abgerundeten Ecken.
+\item circle\\
+  Ein Kreis.
+\item circlesegment\\
+  Ein Kreissegment.
+\item ring\\
+  Ein Ring, kann genutzt werden um nicht ausegfüllte Kreise zu zeichnen.
+\item ellipse\\
+  Eine Ellipse.
+\item triangle\\
+  Ein Dreieck.
+\item text\\
+  Text.
+\end{itemize}
+Mit diesen Funktionen kann eine Bild ungefähr so aussehen:\\
+
+\begin{verbatim}
+// The IMG function is always required
+// it initializes the image with its size
+IMG (height=100, width=100)
+
+// A rectangle 
+rectangle (x=0, y=0, height=100, width=100, color="#5BCEFA", fill=true, thickness=0)
+
+/*
+ Rectangle but multiline
+*/
+rectangle (x=20, y=0,
+height=60, width=100,
+color="#F5A9B8",
+fill=true, thickness=0)
+
+circle (x=100,y=100,radius=10,color="#CfCfCf")
+\end{verbatim}
+Trotz des sehr simplen Aufbaus und kleinen Arsenal an Funktionen, ist es möglich viele verschiedene Dinge zu zeichnen, Perfekt um Grafiken für die Warnung von Nutzern zu erstellen.
+
+\hypersetup{pageanchor=false}
+\begin{figure}[h]
+  \centering
+  \begin{minipage}[c]{0.4\linewidth}
+    \includegraphics[width=\linewidth]{realisierung/images/bvg-haskell.png}
+    \caption{Haskell Logo in bvg}
+  \end{minipage}
+  \hfill
+  \begin{minipage}[c]{0.4\linewidth}
+    \includegraphics[width=\linewidth]{realisierung/images/bvg-rectangle.png}
+    \caption{Rechtecke und Text}
+  \end{minipage}
+\end{figure}
+\hypersetup{pageanchor=true}
+
+
+%%% Local Variables:
+%%% mode: LaTeX
+%%% TeX-master: "../fsverify"
+%%% End:
diff --git a/doc/class-assignment/realisierung/fsverify.tex b/doc/class-assignment/realisierung/fsverify.tex
index 6277f32..6c61313 100644
--- a/doc/class-assignment/realisierung/fsverify.tex
+++ b/doc/class-assignment/realisierung/fsverify.tex
@@ -3,10 +3,7 @@ Da das Konzept der Festplattenverifizierung nichts neues ist, habe ich mir erstm
 Hierbei war google's dm-verity, welches in Android und ChromeOS geräten genutzt wird, die beste Hilfe, da es am besten dokumentiert und ausgetestet ist.
 
 \subsubsection{Partitionslayout}
-Inspiriert an dm-verity, entschied ich mich dafür, die Datenbank auf eine eigene Partition zu speichern, also war das erste Ziel ein gutes Partitionslayout zu Entwickeln, in der die Datenbank und Metadata so gut wie möglich gespiechert werden kann.
-\\
-%\pagebreak
-\\
+Inspiriert an dm-verity, entschied ich mich dafür, die Datenbank auf eine eigene Partition zu speichern, also war das erste Ziel ein gutes Partitionslayout zu Entwickeln, in der die Datenbank und Metadata so gut wie möglich gespiechert werden kann.\\
 Die erste Version des Layouts war recht simpel, es hatte alles was wirklich wichtig war, eine magic number, die signatur, größe des Dateisystems und größe der Datenbank:
 \begin{verbatim}
 <magic number> <signature> <filesystem size> <table size>
@@ -27,10 +24,8 @@ Die erste Version des Layouts war recht simpel, es hatte alles was wirklich wich
     \hline
   \end{tabular}
 \end{center}
-In der implementierung dieses Layouts viel dann auf, dass es keinen Sinn macht, die Datenbankgröße in MB festzulegen
-\\
-\\
-Die zweite Version fügt ein weiteres Feld hinzu um die Einheit der Datenbankgröße festzulegen:
+In der implementierung dieses Layouts fiel dann auf, dass es keinen Sinn macht, die Datenbankgröße in MB festzulegen
+Die zweite Version fügt aus diesem Grund ein weiteres Feld hinzu um die Einheit der Datenbankgröße festzulegen:
 \begin{verbatim}
 <magic number> <signature> <filesystem size> <table size> <table unit>
 \end{verbatim}
@@ -53,7 +48,6 @@ Die zweite Version fügt ein weiteres Feld hinzu um die Einheit der DatenbankgrÃ
   \end{tabular}
 \end{center}
 \hfill \break
-\\
 Die nächste version teilte die Signatur in zwei teile auf. Da minisign signaturen aus einem kommentar, einer vertrauten signatur, einem weiteren kommentar und einer nicht vertrauten signatur
 \begin{verbatim}
 <magic number> <untrusted signature hash> <trusted signature hash>
@@ -82,7 +76,8 @@ Die nächste version teilte die Signatur in zwei teile auf. Da minisign signatur
 
 \subsubsection{Datenbanklayout}
 Nachdem der Header der Partition festgelegt wurde, muss festgelegt werden, wie die Datenbank festgelegt ist.
-bbolt, die Datenbankbibliothek die fsverify nutzt, hat ein key/value system, das heißt, dass jeder Wert mit einem Schlüssel verbunden ist. Zudem benutzt bbolt das konzept von ``Buckets'', einem Eimer in dem Datenpaare sortiert werden können.\\
+bbolt, die Datenbankbibliothek die fsverify nutzt, hat ein key/value system, das heißt, dass jeder Wert mit einem Schlüssel verbunden ist. Zudem benutzt bbolt das konzept von ``Buckets'', einem Eimer in dem Datenpaare sortiert werden können.
+\bigbreak \noindent
 Das erste Layout war für eine implementation von fsverify die nur auf einem Thread läuft, besteht aus einem Bucket ``Nodes'', in dem jede Node gespeichert wird.
 Eine Node sieht wie folgt aus:
 
@@ -111,10 +106,9 @@ type Node struct {
     \hline
   \end{tabular}
 \end{center}
-
-\\
-Jeder Block, welcher 2kb groß ist, bekommt eine Node zugewiesen, diese Nodes werden in der Datenbank aneinandergereiht, mit dem wert von PrevBlockSum als den key.
+Jeder Block bekommt eine Node zugewiesen, diese Nodes werden in der Datenbank aneinandergereiht, mit dem wert von PrevBlockSum als den key.
 Der Wert PrevBlockSum erlaubt es, während der Verifizierung Fehler in der Datenbank zu finden. Wird eine Node verändert, stimmt der PrevBlockSum der nächsten Node nicht mehr, dass heißt, dass es nicht mehr möglich ist, den Key zu der nächsten Node zu berechnen, wodurch die Verifizierung fehlschlägt.
+\pagebreak
 \begin{verbatim}
 +-----+     +------+     +------+        +------+
 |0x000|     |0xFA0 |     |0x1F40|        |0x3E80|
@@ -123,7 +117,6 @@ Der Wert PrevBlockSum erlaubt es, während der Verifizierung Fehler in der Daten
 |     |     |adBfa |     |1Ab3d |        |bAd31 |
 +-----+     +------+     +------+        +------+
 \end{verbatim}
-\pagebreak
 Wird hier eine Node verändert, stimmt die restliche Kette nicht mehr
 \begin{verbatim}
                          Hash passt nicht mehr
@@ -137,20 +130,17 @@ Wird hier eine Node verändert, stimmt die restliche Kette nicht mehr
                        |
                  Veränderter Wert
 \end{verbatim}
-\\
 Da die erste Node keinen vorränger hat, von dem es PrevNodeSum berechnen kann, wird ihr der wert ``Entrypoint'' gegeben.
-\\
+\bigbreak \noindent
 Diese Datenbankstruktur hat ohne Probleme funktioniert, jedoch war fsverify viel zu langsam wenn es auf einem Thread läuft. Das Problem bei dem Multithreading jedoch ist, dass man Nodes nicht wahrlos aufgreifen kann, sondern eine vorherige Node oder die entrypoint Node braucht. Die Lösung ist recht einfach, die anzahl der Threads wird in verifysetup bereits angegeben und somit in fsverify fest einprogrammiert. Somit gibt es in der Datenbank mehrere entrypoint Nodes, die sich durch eine hinzugefügte Nummer unterscheiden. Dadurch ist es weiterhin möglich die Datenbank zu verifizieren, während es multithreaded läuft.
 
 \subsubsection{Datenbanksignatur}
 Um sicherzustellen, dass die Datenbank nicht modifiziert wurde, wird eine Signatur generiert die mit der gelesenen Datenbank verglichen wird.\\
 Wie bereits erwähnt, wird für die Signatur das Programm minisign benutzt. Minisign beruht auf ein public/private key system, wodurch eine Signatur von dem privaten Schlüssel generiert wird und durch den öffentlichen Schluss verifiziert werden kann.\\
 Die Signatur wurde bereits im Partitionsheader gespeichert, was übrig bleibt ist der öffentliche Schlüssel.\\
-\\
 Da der öffentliche Schlüssel und die Signatur gebraucht werden, um eine Datenbank zu verifizieren, muss sichergestellt werden, dass beide seperat gespeichert werden und zumindest der öffentliche Schlüssel nicht bearbeitet werden kann.\\
 Die erste Idee um dies zu lösen wäre, dass man einfach den Schlüssel in eine Datei schreibt, und die Datei schreibgeschutzt Speichert. Jedoch ist bei diesem weg der speicherort der Datei das problem, wie soll man sicher sein, dass nicht das ganze Dateisystem verändert wurde um einen neuen Schlüssel zu beinhalten?
-\\
-\\
+\bigbreak \noindent
 Das heißt, dass man ein Schreibgeschütztes, möglichst seperates und immer vertraubares Speichermedium braucht, auf der man den Schlüssel speichert.\\
 Die lösung: Microcontoller. Sie können über usb-serial (also /dev/ttyACM* in Linux) Daten übertragen, können durch das Modifizieren bestimmter Sektoren permanent schreibgeschützt werden, und sind sehr klein, also können sie von dem Nutzer mitgetragen werden oder in dem Gerät direkt verbaut sein.
 \\
@@ -166,7 +156,7 @@ void setup() {
 void loop() {}
 \end{verbatim}
 
-Es wird eine Serielle Konsole auf einer Baudrate von 9600 geöffnet, auf der einmalig der öffentliche Schlüssel ausgegeben wird. Es ist wichtig zu beachten, dass der Schlüssel mit Tabstops (\backlash t) ausgegeben wird, diese benutzt fsverify um zu wissen, ob der volle Schlüssel aufgenommen wird, fehlt der Tabstop am anfang oder am Ende, ist es sehr wahrscheinlich, dass der Schlüssel auch nicht vollständig aufgenommen wurde.
+Es wird eine Serielle Konsole auf einer Baudrate von 9600 geöffnet, auf der einmalig der öffentliche Schlüssel ausgegeben wird. Es ist wichtig zu beachten, dass der Schlüssel mit Tabstops (\symbol{92} t) ausgegeben wird, diese benutzt fsverify um zu wissen, ob der volle Schlüssel aufgenommen wird, fehlt der Tabstop am anfang oder am Ende, ist es sehr wahrscheinlich, dass der Schlüssel auch nicht vollständig aufgenommen wurde.
 
 \subsubsection{Optimierung}
 Wie bereits gesagt, lief die erste version von fsverify auf einem Thread, dies führte zu einer laufzeit von über einer Stunde bei einer Partitionsgröße von 1gb. Da fsverify beim booten des systems ausgeführt werden soll, ist eine laufzeit von einer Stunde nicht akzeptabel.
@@ -176,20 +166,27 @@ Mit diesen Optimierungen hat sich die Laufzeit etwas verbessert, von 60 Minuten
 \\
 Der nächste schritt war es, fsverify mit multithreading zu implementieren, die dafür notwendigen änderungen in der Datenbank wurden bereits erklärt. In fsverify selber hat sich die art geändert, wie die Daten von der Partition gelesen werden. Anstatt alles auf einmal zu lesen und durchzugehen, wird die größe der Partition genommen, durch die anzahl der Threads geteilt, und somit für jeden Thread genau die anzahl an bytes gelesen, die für die Node-kette nötig ist. Dies stellt sicher, dass keine Kette sich überlappt und korruptionen von Nodes in ketten auffallen, da sie durch Korruptionen versuchen könnten, bytes zu lesen die sie garnicht lesen sollten.\\
 Durch das multithreading hat sich die Laufzeit von den singlethreaded 50 Minuten zu nur 6 Sekunden verringert.
-\\
-\\
+\bigbreak \noindent
 Fsverify hatte eine Laufzeitoptimierung von 60000\% in einer Woche:
 \begin{verbatim}
-10.02.2024: fsverify takes 60minutes to complete for 1gb
+10.02.2024:
+fsverify takes 60minutes to complete for 1gb
 optimizations: none
-
-12.02.2024: fsverify takes 52minutes to complete for 1gb
+\end{verbatim}
+\pagebreak
+\begin{verbatim}
+12.02.2024:
+fsverify takes 52minutes to complete for 1gb
 optimizations: block size 2k, sha1 instead of sha256
-
-17.02.2024: fsverify takes ~6 seconds to complete for 1gb with 12 threads (p7530)
-optimizations: block size 2k, sha1 instead of sha256, multithreaded, db batch operations
+\end{verbatim}
+\begin{verbatim}
+17.02.2024:
+fsverify takes ~6 seconds to complete for 1gb with 12 threads (p7530)
+optimizations: block size 2k, sha1 instead of sha256,
+               multithreaded, db batch operations
 unoptimizations: manual connecting of arduino, ~1 second penalty
 \end{verbatim}
+
 %%% Local Variables:
 %%% mode: LaTeX
 %%% TeX-master: "../fsverify"
diff --git a/doc/class-assignment/realisierung/images/bvg-haskell.png b/doc/class-assignment/realisierung/images/bvg-haskell.png
new file mode 100644
index 0000000..eca956c
--- /dev/null
+++ b/doc/class-assignment/realisierung/images/bvg-haskell.png
diff --git a/doc/class-assignment/realisierung/images/bvg-rectangle.png b/doc/class-assignment/realisierung/images/bvg-rectangle.png
new file mode 100644
index 0000000..4460041
--- /dev/null
+++ b/doc/class-assignment/realisierung/images/bvg-rectangle.png
diff --git a/doc/class-assignment/realisierung/images/framebuffer-rectangle.png b/doc/class-assignment/realisierung/images/framebuffer-rectangle.png
new file mode 100644
index 0000000..5b100aa
--- /dev/null
+++ b/doc/class-assignment/realisierung/images/framebuffer-rectangle.png
diff --git a/doc/class-assignment/realisierung/images/raylib-framebuffer.png b/doc/class-assignment/realisierung/images/raylib-framebuffer.png
new file mode 100644
index 0000000..5876c42
--- /dev/null
+++ b/doc/class-assignment/realisierung/images/raylib-framebuffer.png
diff --git a/doc/class-assignment/realisierung/verifysetup.tex b/doc/class-assignment/realisierung/verifysetup.tex
index 9a28b3a..2b79012 100644
--- a/doc/class-assignment/realisierung/verifysetup.tex
+++ b/doc/class-assignment/realisierung/verifysetup.tex
@@ -9,17 +9,24 @@ Mit dem wechsel zu multithreading ging dies dann runter zu 19 Sekunden mit 12 Th
 \\
 Die Laufzeit von verifysetup verbesserte sich um 33846\% in einer Woche.
 \begin{verbatim}
-10.02.2024: fsverify setup takes 110minutes to complete for 1gb
+10.02.2024:
+fsverify setup takes 110minutes to complete for 1gb
 optimizations: none
-
-12.02.2024: fsverify setup takes 71minutes to complete for 1gb
+\end{verbatim}
+\begin{verbatim}
+12.02.2024:
+fsverify setup takes 71minutes to complete for 1gb
 optimizations: block size 2k, sha1 instead of sha256
-
-12.02.2024: fsverify setup takes ~9.54 seconds to complete for 1gb with 12 threads
+\end{verbatim}
+\begin{verbatim}
+12.02.2024:
+fsverify setup takes ~9.54 seconds to complete for 1gb with 12 threads
 optimizations: block size 2k, sha1 instead of sha256,
                multithreaded, db batch operations
-
-17.02.2024: fsverify setup takes ~19.50 seconds to complete for 1gb with 12 threads
+\end{verbatim}
+\begin{verbatim}
+17.02.2024:
+fsverify setup takes ~19.50 seconds to complete for 1gb with 12 threads
 optimizations: block size 2k, sha1 instead of sha256,
                multithreaded, db batch operations
 unoptimizations: enable database signing, header generation,