\documentclass[aspectratio=169,obeyspaces,spaces,hyphens]{beamer}
\usepackage{minted}
\usepackage{newunicodechar}
\usepackage{hyperref}

\mode<presentation>
\usetheme{Bootlin}

\title{Embedded Linux in less than 4 MB of RAM}
\authors{Michael Opdenacker}
\email{michael.opdenacker@bootlin.com}
\slidesurl{http://bootlin.com/pub/conferences/2017/jdll/}
\conference{JDLL Lyon 2017}

\begin{document}

\begin{frame}{\insertconference}
  \begin{columns}
    \column{0.6\textwidth}
    \fontsize{19}{19}\selectfont
    Linux in less than 4 MB of RAM\\
    \vspace{1cm}
    \fontsize{15}{15}\selectfont
    Michael Opdenacker \\
    Bootlin\\
    \normalsize
    {\em \insertemail}
    \column{0.4\textwidth}
       \includegraphics[width=1.0\textwidth]{logoJDLL.png}
  \end{columns}
\end{frame}

\begin{frame}{Michael Opdenacker}
  \begin{columns}
    \column{0.6\textwidth}
    \begin{itemize}
    \item Michael Opdenacker
    \item Founder and Embedded Linux engineer at Bootlin
      \begin{itemize}
      \item Embedded Linux {\bf expertise}
      \item {\bf Development}, consulting and training
      \end{itemize}
      \item Long time interest in embedded Linux boot time,
        and one of its prerequisites: small system size.
      \item From {\bf Orange}, France. Grew up in Lyon!
    \end{itemize}
    \column{0.4\textwidth}
    \begin{center}
       \includegraphics[width=1.0\textwidth]{tuxy.pdf}\\
       {\tiny Penguin from Justin Ternet
       (\url{https://openclipart.org/detail/182875/pinguin})}
    \end{center}
  \end{columns}
\end{frame}

\begin{frame}{Why reduce size?}
  There are multiple reasons for having a small kernel and system
  \begin{itemize}
    \item Run on very small systems (IoT)
    \item Run on old machines
    \item Run Linux as a bootloader
    \item Boot faster (for example on FPGAs)
    \item Reduce power consumption\\
          Even conceivable to run the whole system in CPU internal RAM
          or cache (DRAM is power hungry and needs refreshing) 
    \item Security: reduce the attack surface
    \item Cloud workloads: optimize instances for size and boot time.
    \item Spare as much RAM as possible for applications and
	  maximizing performance.
  \end{itemize}
  See \url{https://tiny.wiki.kernel.org/use_cases}
\end{frame}

\begin{frame}{How small can a normal Linux system be?}
  \begin{itemize}
  \item RAM
    \begin{itemize}
	\item You need 2-6 MB of RAM for an embedded kernel
        \item Need at least 8-16 MB to leave enough space for
	      user-space (if user-space is not too complex)
        \item More RAM helps with performance!
    \end{itemize}
  \item Storage
    \begin{itemize}
        \item You need 2-4 MB of space for an embedded kernel
	\item User space can fit in a few hundreds of KB.
        \item With a not-too-complex user-space, 8-16 MB of storage
	      can be sufficient.
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Let's work on the compiler}
  \begin{center}
    \includegraphics[width=0.9\textwidth]{global-architecture-compiler.pdf}
  \end{center}
\end{frame}

\begin{frame}{Compiler optimizations}
  \begin{itemize}
     \item {\em gcc} offers an easy-to-use \code{-Os} option for minimizing
           binary size.
     \item It is essentially the optimizations found in \code{-O2}
	   without the ones that increase size
  \end{itemize}
  See \url{https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html} for all available optimizations
\end{frame}

\begin{frame}{Using a recent compiler}
  Compiling for ARM versatile, Linux 4.10
  \begin{itemize}
  \item With gcc 4.7: 407512 bytes (zImage)
  \item With gcc 6.2: 405968 bytes (zImage, -0.4\%)
  \end{itemize}
  A minor gain!
\end{frame}

\begin{frame}{Using gcc LTO optimizations}
   LTO: Link Time Optimizations
   \begin{itemize}
      \item Allows gcc to keep extra source information to make further optimizations
            at link time, linking multiple object files together.
            In particular, this allows to remove unused code.
      \item Even works with programs built from a single source file!
            Example: \code{oggenc} from
            \url{http://people.csail.mit.edu/smcc/projects/single-file-programs/oggenc.c}
            (1.7 MB!)
      \item How to compile with LTO:\\
            \code{gcc -Os -flto oggenc.c -lm}
   \end{itemize}
   See again \url{https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html} for details.
\end{frame}

\begin{frame}{gcc LTO optimizations results} 
   Compiling \code{oggenc.c}
   \begin{itemize}
      \item With gcc 6.2 for x86\_64:
      \begin{itemize}
	  \item {\bf Without LTO}: 2122624 bytes (unstripped), 1964432 bytes
                (stripped) 
	  \item {\bf With LTO}: 2064480 bytes (unstripped, -2.7\%), 1915016 bytes
                (stripped, {\bf -2.6\%})
      \end{itemize}
      \item With gcc 6.2 for armelhf:
      \begin{itemize}
	  \item {\bf Without LTO}: 1157588 bytes (unstripped), 1018972 bytes
                (stripped) 
	  \item {\bf With LTO}: 1118480 bytes (unstripped, -3.4\%), 990248 bytes
                (stripped, {\bf -2.8\%})
      \end{itemize}
   \end{itemize}
   Note: the x86\_64 size is not meant to be compared with arm code. 64
   bit code is bigger than 32 bit code, that's expected.
\end{frame}

\begin{frame}{gcc vs clang}
  Let's try to compile \code{oggenc.c} again:
  \begin{itemize}
    \item Compiled with {\bf gcc} 6.2.0 on x86\_64:\\
	  \code{gcc oggenc.c -lm -Os; strip a.out}\\
	  Size: 1964432 bytes
    \item Compiled with {\bf clang} 3.8.1 on x86\_64:\\
	  \code{clang oggenc.c -lm -Os; strip a.out}\\
	  Size: 1865592 bytes (-5.0\%)
    \item Clang has a new \code{-Oz} option going a little further:\\
	  \code{clang oggenc.c -lm -Oz; strip a.out}\\
	  Size: 1853304 bytes {\bf (-5.7\%)}
    \item gcc can catch up a little with the LTO option:\\
	  \code{gcc oggenc.c -lm -flto -Os; strip a.out}\\
	  Size: 1915016 bytes (-2.7\%)
  \end{itemize}
  Note that gcc can win for very small programs (-1.2 \% vs
  clang on \code{hello.c}).
\end{frame}

\begin{frame}[fragile]
  \frametitle{ARM: arm vs thumb instruction sets}
  \begin{itemize}
     \item In addition to the {\em arm 32 bit instruction set}, the ARM 32 bit
           architecture also offers the {\em Thumb instruction set},
           which is supposed to be more compact.
     \item You can use \code{arm-linux-objdump -S} to distinguish
           between arm and thumb code.
  \end{itemize}
  \includegraphics[height=0.3\textheight]{armcode.pdf}
  \includegraphics[height=0.3\textheight]{thumbcode.pdf}
\end{frame}

\begin{frame}[fragile]
  \frametitle{ARM: arm vs thumb instruction sets (2)}
  \begin{itemize}
     \item To compile in arm mode:\\
           \code{arm-linux-gnueabihf-gcc -marm  oggenc.c -lm}\\
	   Result: 1323860 bytes
     \item To compile in thumb mode (default mode for my compiler!):\\
           \code{arm-linux-gnueabihf-gcc -mthumb  oggenc.c -lm}\\
	   Result: 1233716 bytes ({\bf -6.8\%})
     \item Notes:
     \begin{itemize}
        \item Thumb instructions are more compact but more are needed,
              which explains the limited size reduction.
        \item Thumb mode can be the default for your compiler!
        \item In my tests with \code{-marm}, the binary was a mix of Arm
	      and Thumb code. 
     \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Let's work on the kernel}
  \begin{center}
    \includegraphics[width=0.9\textwidth]{global-architecture-kernel.pdf}
  \end{center}
\end{frame}

\begin{frame}[fragile]
  \frametitle{How to get a small kernel?}
  \begin{itemize}
     \item Run \code{make tinyconfig} (since version 3.18)
     \item \code{make tinyconfig} is \code{make allnoconfig} plus
           configuration settings to reduce kernel size
     \item You will also need to add configuration settings to support
           your hardware and the system features you need.
  \end{itemize}
\begin{minted}[fontsize=\small]{make}
tinyconfig:
        $(Q)$(MAKE) -f $(srctree)/Makefile allnoconfig tiny.config
\end{minted} 
\end{frame}

\begin{frame}[fragile]
   \frametitle{kernel/configs/tiny.config}
\begin{minted}[fontsize=\small]{make}
# CONFIG_CC_OPTIMIZE_FOR_PERFORMANCE is not set
CONFIG_CC_OPTIMIZE_FOR_SIZE=y
# CONFIG_KERNEL_GZIP is not set
# CONFIG_KERNEL_BZIP2 is not set
# CONFIG_KERNEL_LZMA is not set
CONFIG_KERNEL_XZ=y
# CONFIG_KERNEL_LZO is not set
# CONFIG_KERNEL_LZ4 is not set
CONFIG_OPTIMIZE_INLINING=y
# CONFIG_SLAB is not set
# CONFIG_SLUB is not set
CONFIG_SLOB=y
\end{minted} 
\end{frame}

\begin{frame}[fragile]
   \frametitle{arch/x86/configs/tiny.config}
\begin{minted}[fontsize=\small]{make}
CONFIG_NOHIGHMEM=y
# CONFIG_HIGHMEM4G is not set
# CONFIG_HIGHMEM64G is not set
\end{minted} 
\end{frame}

\begin{frame}{tinyconfig Linux kernel size (arm)}
   \includegraphics[width=1.0\textwidth]{tinyconfig-arm-size.pdf}
   Not worse than 10 years back!
\end{frame}

\begin{frame}{tinyconfig Linux kernel size (x86)}
   \includegraphics[width=1.0\textwidth]{tinyconfig-x86-size.pdf}
\end{frame}

\begin{frame}{Linux kernel size notes}
   \begin{itemize}
      \item We reported the \code{vmlinux} file size, to
	    reflect the size that the kernel would use in RAM.
      \item However, the \code{vmlinux} file was not
            stripped in our experiments. You could get
	    smaller results.
      \item On the other hand, the kernel will make allocations
	    at runtime too. Counting on the stripped kernel size
	    would be too optimistic.
   \end{itemize}
\end{frame}

\begin{frame}{Demo}
   Mainline Linux 4.10 booting on QEMU\\
   ARM VersatilePB, with 3090 KB of RAM
   \begin{columns}
   \column{0.6\textwidth}
     \begin{itemize}
        \item \code{zImage}: 405464 bytes
        \item text: 972660 (program code)
        \item data: 117292 (initialized data)
        \item bss: 22312 (initialized data)
        \item total: 1112264
     \end{itemize}
   \column{0.4\textwidth}
      \includegraphics[width=1.0\textwidth]{qemu-versatile.png}
   \end{columns}
   Test it by yourself (all in a single line):\\
   \code{qemu-system-arm -M versatilepb -nographic -kernel zImage} \\
   \code{-initrd initarmfs.cpio.gz -dtb versatile-pb.dtb -m 3090k} \\
   Files: \url{http://bootlin.com/pub/conferences/2017/jdll/}
\end{frame}

\begin{frame}{State of the kernel tinification project}
   \begin{itemize}
      \item Stalled since Josh Triplett's patches were removed
	    from the {\em linux-next} tree
      \item See \url{https://lwn.net/Articles/679455}
      \item Patches still available on
            \url{https://git.kernel.org/cgit/linux/kernel/git/josh/linux.git/}
      \item Removing functionality through configuration settings may no
            longer be the way to go, as the complexity of kernel
            configuration parameter is already difficult to manage.
      \item The future may be in automatic removal of unused features
            (system calls, command line options, \code{/proc} contents,
            kernel command line parameters...)
      \item Lack of volunteers with time to drive the mainlining effort
            anyway.
   \end{itemize}
   Follow the kernel developers discussion about this topic:
   \url{https://lwn.net/Articles/608945/}. That was in 2014!
\end{frame}

\begin{frame}{gcc LTO and the Linux kernel}
   Patches proposed by Andi Kleen in 2012
   \begin{itemize}
      \item Such optimizations would allow performance improvements
            as well as some size reduction by eliminating unused code
            (-6\% on ARM, reported by Tim Bird).
      \item The last time the LTO patches were proposed, using LTO
            could create new issues or make problems harder to
            investigate. Linus didn't trust the toolchains at that time.
      \item See \url{https://lwn.net/Articles/512548/}
   \end{itemize}
\end{frame}

\begin{frame}{Kernel XIP}
   XIP: eXecution In Place
   \begin{itemize}
       \item Allows to keep the kernel text in flash (NOR flash
             required). 
       \item Only workable solution for systems with very little RAM 
       \item ARM is apparently the only platform supporting it 
   \end{itemize}
\end{frame}

\begin{frame}[fragile]
   \frametitle{How to help with kernel tinification (1)}
   \begin{itemize}
      \item Look for \code{obj-y} in kernel Makefiles:
\begin{minted}[fontsize=\small]{make}
obj-y     = fork.o exec_domain.o panic.o \
            cpu.o exit.o softirq.o resource.o \
            sysctl.o sysctl_binary.o capability.o ptrace.o user.o \
            signal.o sys.o kmod.o workqueue.o pid.o task_work.o \
            extable.o params.o \
            kthread.o sys_ni.o nsproxy.o \
            notifier.o ksysfs.o cred.o reboot.o \
            async.o range.o smpboot.o ucount.o
\end{minted}
      \item What about allowing to compile Linux without ptrace
            support (~14K on arm) or without reboot (9K)? 
      \item Another way is to look at the compile logs and check
            whether/why everything is needed.
   \end{itemize}
\end{frame}

\begin{frame}[fragile]
   \frametitle{How to help with kernel tinification (2)}
   \begin{itemize}
       \item Look for tinification opportunities, looking for the
             biggest symbols:\\
             \code{nm --size-sort vmlinux}
       \item Look for size regressions with the {\em Bloat-O-Meter}:
\begin{minted}[fontsize=\small]{console}
> ./scripts/bloat-o-meter vmlinux-4.9 vmlinux-4.10
add/remove: 101/135 grow/shrink: 155/109 up/down: 19517/-19324 (193)
function                                     old     new   delta
page_wait_table                                -    2048   +2048
sys_call_table                                 -    1600   +1600
cpuhp_bp_states                              980    1800    +820
...
\end{minted}
   \end{itemize}
\end{frame}

\begin{frame}{LLVM Linux project}
   \url{http://llvm.linuxfoundation.org/}
   \begin{columns}
   \column{0.75\textwidth}
      \begin{itemize}
         \item Using Clang to compile the Linux kernel also
               opens the door to performance and size optimizations,
	       possibibly even better than what you can get with gcc LTO.
         \item Unfortunately, the project looks stalled since 2015.
         \item News: Bernhard Rosenkränzer from Linaro has updated
               the patchset and should start pushing upstream soon.
	       Reference: \url{https://android-git.linaro.org/kernel/hikey-clang.git},
               branch \code{android-hikey-linaro-4.9-clang}
      \end{itemize}
    \column{0.25\textwidth}
       \includegraphics[width=1.0\textwidth]{tux-with-dragon-wings-135.png}
   \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Let's work on the user-space}
  \begin{center}
    \includegraphics[width=0.9\textwidth]{global-architecture-userspace.pdf}
  \end{center}
\end{frame}

\begin{frame}{Userspace - BusyBox vs Toybox}
  \begin{columns}
    \column{0.5\textwidth}
       \includegraphics[width=1.0\textwidth]{busybox-16files.png}
    \column{0.5\textwidth}
       \includegraphics[width=1.0\textwidth]{toybox-16files.png}
  \end{columns}
  \vfill
  Compiled on ARM with gcc 5.4 (dynamically linked with glibc)
\end{frame}

\begin{frame}{BusyBox vs Toybox - shell only}
  \begin{columns}
    \column{0.5\textwidth}
       \includegraphics[width=1.0\textwidth]{busybox-sh-only.png}
    \column{0.5\textwidth}
       \includegraphics[width=1.0\textwidth]{toybox-sh-only.png}
  \end{columns}
  \vfill
  Compiled on ARM with gcc 5.4 (dynamically linked with glibc)
\end{frame}

\begin{frame}{BusyBox vs Toybox - Conclusions}
  \begin{itemize}
    \item Toybox wins if your goal is to reduce size and have a tiny rootfs
    \item BusyBox wins in terms of configurability, and in terms of
          functionality for more elaborate needs.
    \item Comments from Rob Landley: the Toybox shell is too
          experimental to be used at the moment, and is meant to become
          a bash replacement. If you're looking for a small shell,
          you may look at {\em mksh} (\url{https://www.mirbsd.org/mksh.htm})
  \end{itemize}
\end{frame}

\begin{frame}{glibc vs uclibc vs musl (static)}
  Let's compile and strip BusyBox 1.26.2 {\bf statically} and compare the size
  \begin{itemize}
    \item With gcc 6.3, armel, musl 1.1.16:\\
          {\bf 183348} bytes
    \item With gcc 6.3, armel, uclibc-ng 1.0.22 :\\
          {\bf 210620} bytes.\\
    \item With gcc 6.2, armel, glibc:\\
          {\bf 755088} bytes
  \end{itemize}
  Note: BusyBox is automatically compiled with \code{-Os} and stripped.
\end{frame}

\begin{frame}{glibc vs uclibc vs musl (dynamic)}
  Let's compile and strip BusyBox 1.26.2 {\bf dynamically} and compare the size
  \begin{itemize}
    \item With gcc 6.3, armel, musl 1.1.16:\\
          {\bf 92948} bytes
    \item With gcc 6.3, armel, uclibc-ng 1.0.22 :\\
          {\bf 92116} bytes.\\
    \item With gcc 6.2, armel, glibc:\\
          {\bf 100336} bytes
  \end{itemize}
\end{frame}

\begin{frame}{glibc vs uclibc vs musl - small static executables}
  Let's compile and strip a \code{hello.c} program {\bf statically} and compare the size
  \begin{itemize}
    \item With gcc 6.3, armel, musl 1.1.16:\\
          {\bf 7300} bytes
    \item With gcc 6.3, armel, uclibc-ng 1.0.22 :\\
          {\bf 67204} bytes.
    \item With gcc 6.2, armel, glibc:\\
          {\bf 492792} bytes
  \end{itemize}
\end{frame}

\begin{frame}{Using super strip}
  \code{sstrip}
  (\url{http://www.muppetlabs.com/~breadbox/software/elfkickers.html})
  removes ELF contents that are not needed for program execution.
  \begin{itemize}
    \item Expect to save only a few hundreds or thousands of bytes
    \item \code{sstrip} is architecture independent (unlike
       \code{strip}) and is trivial to compile
  \end{itemize}
  Example with the small static program we've just compiled:
  \begin{itemize}
    \item With gcc 6.3, armel, musl 1.1.16: 7300 to 6520 bytes (-780)
    \item With gcc 6.3, armel, uclibc-ng 1.0.22: 67204 bytes to 66144 bytes (-1060)
    \item With gcc 6.2, armel, glibc: 492792 to 491208 bytes (-1584)
  \end{itemize}
  With BusyBox statically compiled with the musl library:
  \begin{itemize}
     \item From 183012 to 182289 (-723)
  \end{itemize}
\end{frame}

\begin{frame}{Achieving small filesystem size}
   \begin{itemize}
      \item For very small systems, booting on an initramfs is the best
            solution. It allows to boot earlier and faster too
            (no need for filesystem and storage drivers).
      \item A single static executable helps too (no libraries)
      \item For bigger sizes, compressing filesystems are useful:
      \begin{itemize}
         \item SquashFS for block storage
         \item JFFS2 for flash (UBI has too much overhead for small
               partitions)
         \item ZRAM (compressed block device in RAM)
      \end{itemize}
   \end{itemize}
\end{frame}

\begin{frame}{Distributions}
   If you need a distro, have a look at Alpine Linux:
  \begin{columns}
    \column{0.6\textwidth}
      \begin{itemize}
         \item \url{https://www.alpinelinux.org/}
         \item Based on {\em Musl} and {\em BusyBox}
         \item Also security oriented
         \item Fits in about 130 MB of storage
         \item Supports x86 and arm, both 32 and 64 bit.
      \end{itemize}
    \column{0.4\textwidth}
       \includegraphics[width=1.0\textwidth]{alpinelinux-logo.pdf}
    \end{columns}
\end{frame}

\begin{frame}{My next steps}
  \begin{columns}
    \column{0.8\textwidth}
      \begin{itemize}
         \item Try to push Josh Triplett's remaining patches upstream,\\
	       plus my own ones
         \item Try to support a board with no SDRAM:
	 \begin{itemize}
	    \item 512K of on-chip RAM
	    \item 2M of flash
            \item ARM Cortex M7 CPU
	    \item Cost: 23 EUR
         \end{itemize}
         Hoping to have a system with a very good battery life!
      \end{itemize}
    \column{0.2\textwidth}
       \includegraphics[width=1.0\textwidth]{stm32-nucleo-f767zi.jpg}\\
       STM32 Nucleo F767ZI
    \end{columns}
\end{frame}

\begin{frame}{Conclusions}
   \begin{itemize}
      \item Though there apparently hasn't been recent mainlining
            efforts, the kernel size can remain very small (405K
            compressed on ARM, running on a system with less than 4M of RAM).
      \item Compilers: use {\em clang} or {\em gcc LTO}
            (not for the kernel yet)
      \item New C library worth using: {\em musl}
      \item Worth giving Toybox a try too, when simple command
	    line utilities are sufficient.
      \item Still significant room for improvement. Difficult
            to make things removable without increasing the kernel
            parameter and testing complexity, though.
   \end{itemize}
\end{frame}

\begin{frame}{Useful resources}
   \begin{itemize}
      \item Home of the Linux tinification project
        \url{https://tiny.wiki.kernel.org/}\\
      \item Ideas ideas and projects which would be worth reviving
        \url{http://elinux.org/Kernel_Size_Reduction_Work}\\
      \item Tim Bird - Advanced size optimization of the Linux kernel (2013)
        \url{http://events.linuxfoundation.org/sites/events/files/lcjp13_bird.pdf}
      \item Pieter Smith -  Linux in a Lightbulb: How Far Are We on Tinification (2015)
        \url{http://www.elinux.org/images/6/67/Linux_In_a_Lightbulb-Where_are_we_on_tinification-ELCE2015.pdf}
      \item Vitaly Wool - Linux for Microcontrollers: From Marginal to Mainstream (2015)
        \url{http://www.elinux.org/images/9/90/Linux_for_Microcontrollers-_From_Marginal_to_Mainstream.pdf}
   \end{itemize}
\end{frame}


\questionslide

\end{document}
