\documentclass[aspectratio=169]{beamer}

\usepackage{minted}
\usetheme{Madrid}
%Information to be included in the title page:
\title[Ernovos] %optional
{Overview of Ernovos}

\subtitle{An operating system in Erlang}

\author[Reitsma, Erik] {Erik Reitsma}

\def\code#1{\texttt{#1}}

\begin{document}

\frame{\titlepage}

\begin{frame}
    \frametitle{Objectives}
    \begin{itemize}
        \item As little C code as possible
        \item As much in Erlang as possible
        \item No use of C code of others
        \item Support 32-bit x86 (i586)
        \item Support ARM (Zynq) 
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Personal objectives}
    \begin{itemize}
        \item Learn about operating systems
        \item Learn about Erlang/BEAM
        \item Learn about C programming
        \item Have fun!
    \end{itemize}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Some Erlang: modules and recursion}
    \begin{minted}{erlang}
-module(myfun).

-export([fac/1]).

fac(0) -> 1;
fac(N) -> N * fac(N - 1).
    \end{minted}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Some Erlang: modules and recursion}
    \begin{minted}{erlang}
-module(myfun).

-export([fac/1]).

fac(N) when N < 1 -> 1;
fac(N) -> N * fac(N - 1).
    \end{minted}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Some Erlang: spawning processes and sending messages}
    \begin{minted}{erlang}
F = fun() -> 
        receive
            {print, Message} ->
                io:format("Got message: ~p~n", [Message]);
            stop ->
                ok
        end
    end,
P = spawn(F),
P ! {print, "Hello World!"}.
    \end{minted}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Some Erlang: pattern matching with bitstrings}
    \begin{minted}{erlang}
        Eshell V12.3.2.1  (abort with ^G)
        1> A = <<100000:32/big>>.
        <<0,1,134,160>>
        2> <<B1:16, B2:4, B3:4, B4:8>> = A.
        <<0,1,134,160>>
        3> [B1, B2, B3, B4].
        [1,8,6,160]        
    \end{minted}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Decoding an Ethernet packet}
    \begin{minted}{erlang}
decode_frame(<<Destination:6/binary,
    Source:6/binary,
    EtherType:16/big,
    Payload/binary>>) ->
    #ethernet_frame{destination = Destination,
         source = Source,
         type = EtherType,
         payload = Payload}.
    \end{minted}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Decoding an IP packet}
    \begin{minted}{erlang}
decode(<<Version:4, Header_length:4,
         Differentiated_Services:8, Total_length:16,
         Identification:16, Flags:3,
         Fragment_offset:13, Time_to_live:8,
         Protocol:8, Header_Checksum:16,
         Source_Address:4/binary, Destination_Address:4/binary,
         OptionsAndData/binary>>) ->
    OptionsSize = 4 * (Header_length - 5),
    <<Options:OptionsSize/binary, DataAndMore/binary>> = OptionsAndData,
    %% sometimes we may get too much data to be safe,
    %% try to cut it off, if we can
    DataLength = Total_length - (Header_length * 4),
    ...
    \end{minted}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Some Erlang: lists and tuples}
    \begin{minted}{erlang}
        1> A = "Hello World".
        "Hello World"
        2> is_list(A).
        true
        3> hd(A).
        72
        4> B = [5000 | A].
        [5000,72,101,108,108,111,32,87,111,114,108,100]
        5> T = {A, B}.
        {"Hello World",
         [5000,72,101,108,108,111,32,87,111,114,108,100]}
        6> {X, Y} = T.
        {"Hello World",
         [5000,72,101,108,108,111,32,87,111,114,108,100]}
        7> tl(Y).
        "Hello World"        
    \end{minted}
\end{frame}

\begin{frame}
    \frametitle{Architecture}
    Separate layers
    \begin{itemize}
        \item Hardware dependent (i586, zynq)
        \item Low level OS (LLOS)
        \item Erlang virtual machine (ErlVM)
        \item Erlang code (ErlOS)
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{i586}
    Functions specific for i586
    \begin{itemize}
        \item Bootloader (primary and secondary)
        \item Utilities for disk image creation
        \item Inventory of memory
        \item UART (for debugging native code)
        \item Installing of fault handlers
        \item Installing of interrupt handers
        \item Installing of timer (PIT)
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Zynq}
    Functions specific for Zynq
    \begin{itemize}
        \item Registration of configured free memory
        \item Installing of interrupt handlers
        \item Setup of TTC timer
        \item Cache configuration
    \end{itemize}
\end{frame}
\begin{frame}
    \frametitle{Low level OS (LLOS)}
    Generic functions for use by the Erlang Virtual machine
    \begin{itemize}
        \item Management of memory pages
        \item \code{malloc()}
        \item \code{memset()}, \code{memmove()} etc.
        \item \code{printf()} to UART and VGA (if enabled)
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Malloc}
    \begin{itemize}
        \item Large allocations get pages
        \item Small allocations taken from bins
        \item Bins have linked lists of blocks
        \item Block may span several pages
        \item Block contains items of equal size
        \item Block has header with info on item size
        \item Bininfo specifies item size, number of items per block, number of pages, header size
        \item Header has bitmap of used items in block
        \item Four bytes before allocated memory contain information about type and size
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Erlang Virtual Machine}
    Basic features of the virtual machine
    \begin{itemize}
        \item Adapted BEAM modules
        \item Data types
        \item Processes (many, no shared data)
        \item Messages
        \item Garbage collection per process
        \item Erlang functions implemented in C
        \item Limited CPU stack, but use \code{term\_stack} in pages
        \item 32-bit aligned
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Erlang Virtual Machine}
    Additions for hardware handling
    \begin{itemize}
        \item Read and write memory addresses
        \item Allocation of memory buffers
        \item Interrupt handling
        \item Timer handling (for \code{receive after})
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Instructions}
    Instructions from \code{.beam} files are implemented directly
    \begin{itemize}
        \item Each instruction in a separate file
        \item Instructions up to and including OTP 21
        \item Instruction loop is in a single function
        \item Current state is in local variables
        \item Use \code{goto} to jump to next instruction
        \item Instruction addresses are put in \code{.beam} file during loading
    \end{itemize}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Opcode: move}
    \begin{minted}{c}
Operation(move)
{
  erl_term value;

  kdebug_instruction("move", 2);

  ArgGet(Argument(1), value);
  argSet(current_process, Argument(2), value);

  NextInstruction(2);
  CheckAndContinue;
}
    \end{minted}
\end{frame}

\begin{frame}
    \frametitle{Code loading}
    \begin{itemize}
        \item Original \code{.beam}-file converted for easier processing
        \item Initial code loaded from tar in VM binary
        \item Copied to allocated memory
        \item Opcodes replaced by location of instruction implementation
        \item Atoms added to atom table
        \item Labels replaced by location of referenced code
        \item Module versions prepared
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Data types}
    Term fits in 32 bits
    \begin{itemize}
        \item Pointer to heap type (prefix 0b00)
        \item Small int (prefix 0b01)
        \item Cons cell (prefix 0b10)
        \item Atom (index) (prefix 0b00011)
        \item Proces (prefix 0b00111)
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Heap types}
    Term has prefix 0b00 and points to process heap
    \begin{itemize}
        \item Tuple
        \item Shared binary
        \item Large int
        \item Function
        \item Local binary
        \item Float
        \item Binary context (used while matching binaries)
        \item Reference
        \item Map
        \item Membuf (added for drivers)
        \item External function
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Large integers}
    \begin{itemize}
        \item Stored in array of 32 bits unsigned int
        \item Stored on process heap
        \item Header contains size and sign
        \item Arithmetic: add, subtract, multiply, divide, remainder, negate, compare
        \item Bitwise logical: and, or, not, xor
        \item Combinations large/small integers
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Binaries}
    \begin{itemize}
        \item Local binaries on process heap
        \item Shared binaries in \code{malloc}ed blob
        \item Header specifies size and bit offset
        \item Local binaries are copied
        \item Shared binaries are reference counted by process
        \item Reference counts are updated on process exit
        \item Process remembers seen shared binaries
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Lambda functions}
    \begin{itemize}
        \item Function is generated by compiler in defining module
        \item Module name and function index in struct on heap
        \item Relevant bound variables in struct on heap
        \item Just another value on heap
        \item Bound variables will be copied when sent as message
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Membufs}
    Memory buffers for drivers
    \begin{itemize}
        \item Allocate memory
        \item Optional number of alignment bits
        \item Get address of membuf
        \item Write binary to membuf
        \item Read binary from membuf
        \item Owned by creating process
        \item Only owner process can use the membuf
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Process state}
    Process state in struct \code{erl\_process} (53 members)
    \begin{itemize}
        \item Current opcode
        \item Registers
        \item Message queue
        \item Heap
        \item Call stack
        \item Catch stack
        \item Shared binaries
        \item Membufs
        \item Process dictionary
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Concurrency}
    \begin{itemize}
        \item Instruction limit per process
        \item Process is also descheduled on \code{wait} instruction
        \item Local variables stored in \code{erl\_process}
        \item Next runnable process selected
        \item Process is runnable if it was scheduled out or has a waiting message
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Error handling}
    \begin{itemize}
        \item Error cause set in local variable
        \item Error cause checked after each instruction
        \item Catch stack in process state unwound
        \item Linked and monitoring processes informed on process termination
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Built-in functions (BIFs)}
    \begin{itemize}
        \item Implemented inline
        \item Opcodes for different arities
        \item Implemented in VM in \code{switch} statements
        \item Registers and local state directly accessible
        \item Should be fast
        \item Continue with next instruction
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Native implemented functions (NIFs)}
    \begin{itemize}
        \item Stubs in Erlang modules
        \item Overwrite location of function with function pointer native implementation
        \item Access to memory and special instructions, interrupt tables
        \item \code{<module\_name>\_module\_create.c} registers functions
        \item \code{<module\_name>\_module\_impl.c} implements function
        \item Continue with \code{Return}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Example of native implemented function}
    \begin{minted}{C}
BifImplementation(x86_outWord_2) {
    if (is_small_int(current_process->regX[0])) {
        if (is_small_int(current_process->regX[1]))         {
            outWord((uint16_t)term_to_small_int(current_process->regX[0]),
                    (uint16_t)term_to_small_int(current_process->regX[1]));
            setX(current_process, 0, ATOM_ok);
        } else {
            fault = ATOM_badarg;
        }
    } else {
        fault = ATOM_badarg;
    }   
    Return;
}    
    \end{minted}
\end{frame}

\begin{frame}
    \frametitle{Garbage collection}
    Garbage collection per process
    \begin{itemize}
        \item Copy all live data to new allocated memory
        \item Live data is in process registers, stack, process dictionary, messages
        \item Pointer locations will change
        \item Register local term variables with collector to be updated
        \item After copy, old heap range is freed
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Interrupt handling}
    \begin{itemize}
        \item Process can register for interrupt
        \item Process can register service
        \item Service is script with defined instructions
        \item Load, move, store, and, or, xor, not, add, sub
        \item Input, output (Intel)
        \item Send message to process
    \end{itemize}
\end{frame}

\begin{frame}[fragile]
    \frametitle{Interrupt handling example: keyboard}
    \begin{minted}{erlang}
interrupt_server:add_driver(1, self(), 
    [{move_immediate, 16#60, 0},
     {in, byte, 0, 1},
     {send, 1}])
    \end{minted}
    \begin{itemize}
        \item Register this process for IRQ 1
        \item Write 0x60 to register 0
        \item Read from input port register 0 into register 1
        \item Send value of register 1 to process 
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Boot loaders x86}
    \begin{itemize}
        \item Assembly code
        \item Primary loader from sector 0 loads secondary loader
        \item Secondary enables A20
        \item Reads memory map to provide to C memory page handler
        \item Reads boot device from BIOS
        \item Loads ELF header from hard coded location using BIOS
        \item Loads ELF binary using BIOS
        \item Prepares and enters protected mode
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Kernel start}
    \begin{itemize}
        \item Initialize UART
        \item Process boot information from bootloader
        \item Initialize terminal
        \item Install interrupt and fault handlers
        \item Initialize timer
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Virtual machine start}
    \begin{itemize}
        \item Initialize atom table
        \item Initialize shared heap
        \item Initialize opcode table
        \item Load modules from tar
        \item Initialize BIF modules
        \item Create runtime
        \item Create first process
        \item Initialize and enable interrupts
        \item Jump into runtime loop
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Start of Erlang code (x86)}
    \begin{columns}
        \column{0.4\textwidth}
    \begin{itemize}
        \item Start Erlang term storage (ets)
        \item Start timer service
        \item Start init process
        \item Start logger
        \item Start interrupt server
        \item Start device manager
        \item Start file server
    \end{itemize}
    \column{0.6\textwidth}
    \begin{itemize}
        \item Start mount manager
        \item Start rtc driver
        \item Start VGA text driver
        \item Start network manager
        \item Start PCI handler
        \item Mount first ATA device as root of file system
        \item Start keyboard driver
    \end{itemize}
\end{columns}
\end{frame}

\begin{frame}
    \frametitle{Start of Erlang code (Zynq)}
    \begin{itemize}
        \item Start Erlang term storage (ets)
        \item Start init process
        \item Start Zynq MMU
        \item Start interrupt server
        \item Start Zynq GPIO handler
        \item Enable some GPIO pins for output (LEDs)
        \item Start network manager
        \item Start Zynq Ethernet driver
        \item Start Zynq UART server
        \item Start TTY on UART
        \item Blink some LEDs
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Features implemented in Erlang}
    \begin{itemize}
        \item Hardware drivers
        \item File systems
        \item Networking
        \item Shell on terminal
        \item Crypto
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Hardware drivers in Erlang}
    \begin{itemize}
        \item VGA
        \item PCI enumeration
        \item PCI generic ATA
        \item Intel EtherExpress PRO/100 Ethernet (QEmu)
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{File systems}
    \begin{itemize}
        \item Generic block API
        \item Generic ATA implements block API
        \item FAT uses block API
        \item FAT read-only
        \item FAT implements low-level file API in OTP
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Networking}
    \begin{itemize}
        \item Ethernet driver
        \item \texttt{ethernet\_handler}
        \item ARP 
        \item IPv4, some IPv6
        \item TCP, UDP, ICMP
        \item DHCP client
        \item Implementation of OTP \texttt{gen\_tcp} and \texttt{gen\_udp}
        \item Minimal HTTP server
        \item SSH server from OTP
    \end{itemize}
\end{frame}

\begin{frame}
    \frametitle{Crypto}
    \begin{itemize}
        \item Implementation of functions from OTP module \code{crypto} in Erlang
        \item AES128, AES192, AES256
        \item Modes CBC, CFB (block), CTR (stream)
        \item Elliptic curves
        \item Prime and polynomial based fields
        \item SHA224, SHA256, SHA384, SHA512
        \item ECDSA, ECDH
        \item Sufficient for SSH server
    \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Future}
  \begin{itemize}
  \item Page tables
  \item 64 bit (instructions, data structures)
  \item New BEAM instructions
  \item RISC-V
  \item USB
  \item Tests
  \end{itemize}
\end{frame}
\end{document}