\chapter{Implementation} \label{chap:implementation} This chapter contains some of the details of the implementation of preload. Preload is implemented in C and is less than 3000 lines of code, and becomes a small 35kb binary when compiled. However, it uses the GLib library\footnote{Available from \url{http://www.gtk.org/}} for basic data structures and the application main loop. GLib is a convenience library for C programming that is widely used in the GNOME project\footnote{\url{http://www.gnome.org/}}. \section{Dependencies} Preload uses the \syscall{readahead} system call that is specific to the Linux kernel and supported by the GNU libc implementation. Most other Unix kernels provide system calls with similar functionality, so it is rather straightforward to port preload to other UNIX systems, like the BSDs or Solaris. Depending on the implementation, the \syscall{madvise} system call may be used as a substitute. See \autoref{sec:prefetching} for details. The GLib library that preload depends on is ported to various systems and can be compiled (and is usually available) on all modern and legacy desktop systems. \section{Configuration Parameters}\label{sec:conf-params} Preload reads configuration parameters from an INI-style text file that is normally located at \file{\$prefix/etc/preload.conf}. This can be changed at compile time, or using the \opt{conffile} command line argument when invoking preload. The recognized configuration parameters follow. \subsection{Model parameters} \label{subsec:model-params} The model parameters control various aspects of the model and algorithms as described in \autoref{sec:model} and \autoref{chap:algorithms}. The following model parameters are recognized: \begin{itemize} \item\confkeydoc{model.cycle}{integer}{seconds}{20} This is the quantum of time for preload. Preload performs data gathering and predictions every cycle. \emph{Note:} Setting this parameter too low may reduce system performance and stability. \item\confkeydoc{model.halflife}{integer}{hours}{168 (one week)} The time it takes for statistic information to lose importance to a level half of the current importance. This parameter controls how soon preload forgets about the past. Setting it to a higher value makes it take longer for preload to change its mind about its beliefs, while setting it lower makes preload more sensitive and responsive to the current happenings. This is used to compute the decay factor for all exponentially-fading mean computations. Setting this parameter too high will essentially prevent preload from learning new things. \item\confkeydoc{model.minsize}{integer}{bytes}{2\thinspace000\thinspace000} This is the minimum sum of the length of maps of the process for preload to consider tracking an application. \emph{Note:} Setting this parameter too high will make preload less effective, while setting it too low will make it consume quadratically more resources, as it tracks more processes. \end{itemize} \subsection{Memory Usage Parameters} The total memory preload uses for prefetching is computed using the following formula: \begin{eqnarray} \begin{array}{rcl} \max &(0, &\text{\confkey{memstat.total}} \times \text{\confkey{model.memtotal}}\\ &+ &\text{\confkey{memstat.free}} \times \text{\confkey{model.memfree}})\\ + &&\text{\confkey{memstat.cached}} \times \text{\confkey{model.memcached}} \end{array} \label{eqn:memory} \end{eqnarray} where \confkey{memstat} is the MemStat object filled with memory statistics of the system at runtime. The formula above is written such that it can use configuration parameters to express all (interesting) linear combinations of system memory variables. The more memory preload receives for prefetching, the more effective it is, at the cost of more memory used. The following parameters control how much memory preload is allowed to use for prefetching in a cycle. All values are percentages and are clamped to the range -100 to 100. \begin{itemize} \item\confkeydoc{model.memtotal}{integer}{percentage}{-10} Multiplier for total memory variable part of the memory usage formula. \item\confkeydoc{model.memfree}{integer}{percentage}{100} Multiplier for free memory variable part of the memory usage formula. Reducing this value makes preload less agressive during the boot time, where most of the memory is free. \item\confkeydoc{model.memcached}{integer}{percentage}{30} Multiplier for cached memory variable part of the memory usage formula. Increasing this value makes preload more agressive during steady state after the boot. That is, for the most of the operating time of the system. During this time the kernel typically does not let memory to stay free for long and uses it for page-cache. When preload prefetches files, it is essentially causing other pages to be evicted from the cache. \end{itemize} The default values for the memory usage formula result in: \begin{eqnarray} \begin{array}{rcl} \max &(0, &-10\% \times \text{\confkey{model.memtotal}}\\ &+ & 100\% \times \text{\confkey{model.memfree}})\\ + && 30\% \times \text{\confkey{model.memcached}} \end{array} \end{eqnarray} which essentially means: use all free memory except for ten percent of total memory, and thirty percent of memory already used for caches. When a system is in steady state, there is little free memory available since the kernel utilizes most of the free memory for caching. During boot time on the other hand, there is little cached memory and a lot of free memory. Given this, the \confkey{model.memfree} and \confkey{model.memcached} controls enable tuning preload's aggressiveness during boot process and steady state fairly separately. \subsection{System Parameters} \label{subsec:system-params} System parameters enable customizing aspects of the preload daemon that are specific to the implementation and unlike model parameters, do not directly affect the internal working of the scanning and prefetching subsystems. \begin{itemize} \item\confkeydoc{system.doscan}{boolean}{\relax}{true} Specifies whether preload should monitor running processes and update its model state. This is the monitoring subsystem of preload and should normally run, but you may want to temporarily turn it off for various reasons like testing predictions. Note that if scanning is off, predictions are made based on whatever processes have been running when preload started again and again, and the list of running processes is not updated at all. \item\confkeydoc{system.dopredict}{boolean}{\relax}{true} Specifies whether preload should make prediction and prefetch anything off the disk. Similar to \confkey{system.doscan}, you normally want this to be enabled: this is the other subsystem in preload. But you may want to temporarily turn it off, for example to only train the model without prefetching anything. These two parameters allow turning scan/predict subsystems on/off on the fly, by modifying the configuration file and signaling the daemon. \item\confkeydoc{system.autosave}{integer}{seconds}{3600} Preload will automatically save its state to disk periodically, and this parameter determines how often. This is only relevant if \confkey{system.doscan} is enabled. The state is saved when the daemon exits normally (using termination signals). So auto-saving is not strictly required. \item\confkeydoc{system.mapprefix}{string}{\relax}{\emph{empty}, accept all} A list of path prefixes that controls which mapped files should be scanned by preload. The list items are separated by semicolons. Matching stops as soon as an item matches. For each item, if it matches the beginning of the full file name, a match occurs, and the file is accepted. If on the other hand, the item starts with an exclamation mark as its first character, the rest of the item is considered for matching, and if a match happens, the file is rejected. As an example a value of \file{!/lib/modules;/} means that every file other than those in \file{/lib/modules} should be accepted. In this case, the trailing item can be removed, since if no match occurs, the file is accepted. It is advised to make sure that \file{/dev} is rejected, since preload does not differentiate device files internally. \item\confkeydoc{system.exeprefix}{string}{\relax}{\emph{empty}, accept all} A list of path prefixes that controls which binary executables should be scanned by preload. The syntax is exactly the same as \confkey{system.mapprefix}. \end{itemize} \section{Persistent State Storage} The persistent state of the model is stored in a simple text file that is normally located at \file{\$prefix/var/lib/preload/preload.state}. This can be changed at compile time, or using the \opt{statefile} command line argument when invoking preload. The file is read and used to populate the model when preload starts, or if it does not exist, an empty model is constructed. It will be saved periodically as set with the \confkey{autosave} configuration parameter, when preload is shutting down, or upon receiving the \sig{USR2} signal. \section{Prefetching} \label{sec:prefetching} Preload uses the \syscall{readahead} system call that is specific to the Linux kernel and supported by the GNU libc implementation. Most other Unix kernels provide system calls with similar functionality, so it is rather straightforward to port preload to other UNIX systems, like the BSDs or Solaris. There are an entire family of \emph{advise} system calls that can be used as a substitute, depending on the implementation: \syscall{madvise}, \syscall{fadvise}, \syscall{posix\_madvise}, and \syscall{posix\_fadvise}. If all fails, one can even use the \syscall{read} system call to fetch data into main memory, this is a bit wasteful however, as it makes the kernel copy the data into user-space unnecessarily. One way to improve prefetching performance is to make sure all files to be prefetched are queued instead of sequentially read, such that the kernel has more opportunities to avoid seeking around the hard disk. However, the \syscall{readahead} system call is implemented as a command and will block the caller until the request is fulfilled. The \syscall{posix\_madvise} implementation specification is more promising with regard to this. However, the current implementation in Linux is synchronous, like \syscall{readahead} \cite{kernelnewbies:riel}. The Fedora readahead package described in \autoref{subsec:fedora-readahead} uses a filesystem-specific API to determine the place of the first block of each file on the disk, and sorts files to be prefetched on the position of their first block and reads them in that order, supposedly reducing disk access time. Since preload tries to be fairly conservative and not affect system balance in a noticeable way, reading files one at a time is probably acceptable. Note that preload generates prefetching system calls for all the selected maps even if it prefetched some of them at the previous cycle. This means, if no applications are started or shut down, preload generates the exact same system calls as the previous cycle and if those maps are still in memory, the system call essentially becomes a no-operation. We also call \syscall{sched\_yield} after reading every few files to give away processor volunteerly instead of exhausting our time slice. This is useful to keep system responsive as being I/O bound during the prefetching phase, preload will get elevated priority over other processes. \section{Resource Consumption} Preload has a modest memory footprint. Its main memory consumption is the model that is kept in memory, and with an uncommonly large setting of 1000 maps and 100 applications, it operates in less than 3MB of memory, the main contender being the Markov objects that are quadratic in the number of applications, and take less than 200 bytes. The process is in the sleep state most of the time, waiting for the next cycle or blocking on I/O, so the load on the processor is minimal. At each cycle it involves scanning \proc\ to gather data and the mathematical computation to update the model and make predictions. When the system is in an stable state (not swapping or under tight memory conditions) and the set of running applications does not change, preload enters a steady state after a few cycles and stops making new I/O requests. This means that it does not interfere with power-saving activities on laptop systems, like turning the hard disk drive off. \section{Running Preload} When invoked, preload starts running as a background daemon on the system. It accepts the following command line arguments: \begin{itemize} \item\textbf{\opt{help}:} writes out information about invoking preload and exits. \item\textbf{\opt{version}:} writes out the version number of the preload binary and exits. \item\textbf{\opt{conffile \emph{file}}:} sets the file containing configuration parameters (defaults to \file{\$prefix/etc/preload.conf}). The configuration file is used for tuning model parameters as well as other behaviors of preload. Configuration parameters are enumerated in detail in \autoref{sec:conf-params}. \item\textbf{\opt{statefile \emph{file}}:} sets the file for storing persistent state data (defaults to \file{\$prefix/var/lib/preload/preload.state}). \item\textbf{\opt{logfile \emph{file}}:} sets the file used to write out informative messages to (defaults to \file{\$prefix/var/log/preload.log}). An empty \file{\emph{file}} argument redirects messages to the standard output. \item\textbf{\opt{foreground}:} instructs preload to run in the foreground, not as a daemon. \item\textbf{\opt{nice \emph{adjustment}}:} adjusts the nice level of the daemon (defaults to +15). \item\textbf{\opt{verbose \emph{level}}:} adjusts the verbosity level of the daemon. Levels 0 to 10 are recognized with 10 being the most verbose (defaults to 4). \item\textbf{\opt{debug}:} enable debugging mode. Equivalent to \opt{logfile '{}'} \opt{foreground} \opt{verbose 9}. \end{itemize} When running, preload responds to a variety of signals: \begin{itemize} \item\textbf{\sig{HUP}:} Reloads configuration file and reopens the log file. Reopening log file allows for rotating the log file (backing up current content and starting a new one) without restarting the daemon. \item\textbf{\sig{USR1}:} Dumps messages containing the current state and configuration parameters. Useful for debugging purposes. \item\textbf{\sig{USR2}:} Saves the current state to the state file. \item\textbf{\sig{INT}, \sig{QUIT}, \sig{TERM}:} Saves the state and quits. \end{itemize} \section{Source Code} The source code of preload is publicly available at \url{http://preload.sf.net/}. It is also distributed for Debian based systems in the Debian unstable package repository. The source code is fairly straightforward and closely maps to the algorithms presented in \autoref{chap:algorithms}. \section{Other Issues} Preload currently does not handle package updates or removals. However, doing that is as simple as removing objects that have a probability of less than a certain threshold, and removed files will be eventually removed from the model. \subsection{Floating-Point Precision} A minor issue when implementing the inference algorithms of \autoref{subsec:inference} is how to maintain the products in the probability equations within an acceptable precision. To solve this, we use \emph{log-probabilities}, ie.~compute the sum of the natural logarithm of the elements instead of computing their product, and convert back to a probability value when necessary. This drastically reduces the error in the floating point computations and is common practice in machine learning. \subsection{Prelink} \emph{Prelink} is a daemon available on various Linux systems, including Fedora, that runs on the system periodically (once every 24 hour or less frequently), analyzing all installed shared library and applications, and assigning a unique virtual address slot for each shared library, and \emph{relocating} them to that address. The idea is that when running applications, if the shared library can be loaded at its allocated address, no relocation is necessary anymore. This improves application startup-time \cite{jelinek04prelink}. Prelink's operation conflicts with preload, in that prelink modifies shared library files, creating a new one and renaming it to the original one. This causes running processes to see deleted files as their maps. However, this is not a major problem because: \begin{itemize} \item When preload prefetches, it will prefetch the current version of the file, and when a new application starts, it is linked against the current version. Except for the rare occasions that the current version between prefetching and application start-up changes, prefetch always loads the version that is going to be used by new applications started, \item While prelink changes shared objects, the only way it does that is by modifying some relocations structures in the file. The modifications are in-place and do not change the offsets of interesting regions of the file that preload uses in its data structures. So, prelinking does not nullify preload's work. \end{itemize} Preload handles the conflict by behaving as if no maps of currently running applications were deleted.