closos/Documentation/chap-intro.tex

\chapter{Introduction}
\pagenumbering{arabic}

\section{What a Lisp operating system is}

A Lisp Operating System (LispOS for short) is not just another
operating system that happens to be written in Lisp (although that
would be a good thing in itself).  For the purpose of this document, a
LispOS is also an operating system that uses the Lisp interactive
environment as an inspiration for the interface between the user and
the system, and between applications and the system.

In this document, we give some ideas on what a LispOS might contain,
how it would be different from existing operating systems, and how
such a system might be created.

\section{Problems with existing systems}

\subsection{The concept of a \emph{process}}

Most popular existing operating systems are derived from \unix{} which
was written in the 1970s.  The computers for which \unix{} was intended
had a very small address space; too small for most usable end-user
applications.  To solve this problem, the creators of \unix{} used the
concept of a \emph{process}.  A large application was written so
that it consisted of several smaller programs, each of which ran in
its own address space.  These smaller programs would communicate by
having one application write text to its output stream for another
application to read.  This method of communication was called
a \emph{pipe} and a sequence of small applications was called
a \emph{pipeline}.  As a typical example of a chain of applications,
consider the pipeline for producing a typeset document (one of the
main applications for which \unix{} was designed).  This chain had a
program for creating tables (called \texttt{tbl}), a program for
generating pictures (called \texttt{pic}), a program for generating
equations (called \texttt{eqn}), and of course the typesetting program
itself (called \texttt{troff}).

The computers that \unix{} was intended to run on did not have any
memory-management unit (MMU).  The absence of memory management meant
that the code could not move around in physical memory depending on
whether other programs were present in memory as well.  To solve this
problem, a mechanism called \emph{swapping} was used.  Each program
was written so that it had the entire physical address space at its
disposal, and to make that work, one process at a time was present in
physical memory.  To give the illusion of multi-programming, at
regular intervals the current process was interrupted, moved from main
memory to secondary memory, and another runnable process was loaded
into main memory instead.  Programs written in low-level languages
such as \clanguage{} and \cplusplus{} are still written as if they
were meant to be executed on such early computers.

Using \unix{}-style pipes to communicate between different components of
an application has several disadvantages:

\begin{itemize}
\item To communicate complex data structures (such as trees or
graphs), they must be converted to a stream of bytes by the
creating component, and it must be analyzed and parsed into an
equivalent data structure by the using component.  Not only is
this unparsing/parsing inefficient in terms of computing
resources, but it is also problematic from a
software-engineering point of view, because the external format
must be specified and maintained as a separate aspect of each
component.
\item An artificial \emph{order} between the different components is
imposed, so that components can not work as libraries that other
components can use in any order.  Sometimes (as in the example
of the \texttt{troff} chain) the end result of a computation
depends in subtle ways on the order between the components of
the chain.  Introducing a new component may require other
components to be modified.  
\end{itemize}

Pipes also have some advantages though.  In particular, they provide a
\emph{synchronization} mechanism between programs, making it very easy
to implement producer/consumer control structures.

It is an interesting observation that in most text books on
operating systems, the concept of a process is presented as playing
a central role in operating-system design, whereas it ought to be
presented as an unfortunate necessity due to the limited address
space of existing computers in the 1970s.  It is also presented
as \emph{the} method for obtaining some kind of \emph{security},
preventing one application from intentionally or accidentally
modifying the data of some other application.  In reality, there are
several ways of obtaining such security, and separate address spaces
should be considered to be a method with too many disadvantages. 

Nowadays, computers have addresses%
\footnote{The virtual address is 64 bits wide.  That does not mean
  that all 64 bits are used on all implementations of the
  architectures.  However, on the current (as of this writing) Intel
  and AMD x86-64 processors, at least 48 bits are used, and this
  number is likely to increase in the future.}
that are 64 bit wide, making it possible to address almost 20 exabytes
of data.  To get an idea of the order of magnitude of such a number,
consider that a fairly large disc that can hold a terabyte of data.
Then each byte of 20 million such discs can be directly addressed by
the processor.  We can thus consider the problem of too small an
address space to be solved.  The design of \sysname{} takes advantage
of this large address space to find better solutions to the problems
that processes were intended to solve.

\subsection{Hierarchical file systems}

Existing operating system come with a \emph{hierarchical file
system}.  There are two significant problems,
namely \emph{hierarchical} and \emph{file}.

The \emph{ hierarchy} is also a concept that dates back to the
1970s, and it was considered a vast improvement on flat file
systems.  However, as some authors%
\footnote{See
  \texttt{http://www.shirky.com/writings/ontology\_overrated.html}}
explain, most things are not naturally hierarchical.  A hierarchical
organization imposes an artificial order between names.  Whether a
document is called \texttt{Lisp/Programs/2013/stuff},
\texttt{Programs/Lisp/2013/stuff}, or something else like
\texttt{2013/Programs/Lisp/stuff}, is usually not important.

The problem with a \emph{file} is that it is only a sequence of
bytes with no structure.  This lack of structure fits the \unix{} pipe
model very well, because intermediate steps between individual
software components can be saved to a file without changing the
result.  But it also means that in order for complex data structures
to be stored in the file system, they have to be transformed into a
sequence of bytes.  And whenever such a structure needs to be
modified by some application, it must again be parsed and
transformed into an in-memory structure.

\subsection{Distinction between primary and secondary memory}

Current systems (at least for desktop computers) make a very clear
distinction between primary and secondary memory.  Not only are the
two not the same, but they also have totally different semantics:
\begin{itemize}
\item Primary memory is \emph{volatile}.  When power is turned off,
    whatever was in primary memory is lost.
    \item Secondary memory is \emph{permanent}.  Stored data will not
    disappear when power is turned off.
\end{itemize}

This distinction coupled with the semantics of the two memories
creates a permanent conundrum for the user of most applications, in
that if current application data is \emph{not} saved, then it will
be lost in case of power loss, and if it \emph{is} saved, then
previously saved data is forever lost. 

Techniques were developed as early in the 1960s for presenting
primary and secondary memory as a single abstraction to the user.
For example, the \multics{} system had a single hierarchy of fixed-size
byte arrays (called segments) that served as permanent storage, but
that could also be treated as any in-memory array by applications.
As operating systems derived from \unix{} became widespread, these
techniques were largely forgotten. 

\subsection{Full address-space access}

With operating systems such as \unix{}, programs written in low-level
languages such as \clanguage{} are written so that they have access to
the full (virtual) address space%
\footnote{Or sometimes half of it, the operating system kernel
  occupying the other half.}
except that such a program naturally can not access the contents of a
virtual address that does not have any physical memory associated with
it.

Programs are written like that for historical reasons.  Early
computers had no memory-management unit, so there was no way to
prevent a program from accessing the contents of any address.
Essentially, we still write programs today as if we were using
computers with no memory-management unit.

Full address-space access is a notorious source of security problems,
in particular in combination with a programming language like
\clanguage{}.  The \clanguage{} language specification leaves many situations
unspecified, and most compilers take advantage of this freedom to
optimize for speed, to the detriment of other aspects such as
security.  As a result, it is possible for \clanguage{} programs to construct
arbitrary data and arbitrary addresses and alter large parts of its
addressable memory in uncontrolled ways.

Thus if a program does not take great care to prevent a temporary buffer
from overflowing, reading an external document such as a web page may
overwrite part of the stack%
\footnote{Problems with buffer overflow are not limited to the stack,
  of course.  Overflowing a buffer located on the heap is a security
  problem as well.}
(which is located in the address space of
the process).  Such a buffer overflow can alter the return address of
the currently executing function, so that instead of returning
normally, it returns to some code that can have an effect that the
program was absolutely not meant to have.  It can do that because the
\clanguage{} library is linked into the same address space as the rest
of the code, so anything that a program can do with the \clanguage{}
library, such as deleting files or transfer sensitive information to
an external computer, can be done as a result of reading an external
document.

There have been attempts to mitigate these basic problems with a
fully accessible address space.  Recently, for instance, a technique
called \emph{address space layout randomization}%
\footnote{https://en.wikipedia.org/wiki/Address\_space\_layout\_randomization}
has started being used to prevent the problems caused by full
address-space access.  The technique consists of giving the code of
the main program and of the libraries that it uses different virtual
addresses each time the programs is executed.  That way, a malicious
document can not rely on the address to return to being at a
particular location, and defective programs that do not check for
buffer overflow can continue to exist without so much danger in terms
of security.

But address space layout randomization has its own problems.  For one
thing, a program can no longer be written to have predefined data
structures with absolute virtual address at start-up.  Either relative
addressing must be used (which complicates the code and thus makes it
less maintainable), or such data structures must use symbolic
addresses to be resolved by the dynamic linker at program start-up
(which also complicates the code, but in addition slows down program
start-up because of additional work that the linker must do).

In summary, then, a system in which a user program executes in a
process with an address space to which the code has full access will
always have problems in terms of security, performance,
maintainability, or a combination of those.

\subsection{The concept of a kernel}

The kernel of an operating system is a fairly large, monolithic
program that is started when the computer is powered on. The kernel is
not an ordinary program of the computer. It executes in a privileged
state so that it has full access to devices and to data structures
that must be protected from direct use by user-level programs.

The very existence of a kernel is problematic because the computer
needs to be restarted whenever the kernel is updated, and then all
existing state is lost, including open files and data structures that
reside in volatile memory. Some programs, such as web browsers,
compensate somewhat for this problem by remembering the open windows
and the addresses that were associated with each window.

The fact that the kernel is monolithic poses a problem; because, when
code needs to be added to the kernel in the form of a kernel module,
such code has full access to the entire computer system. This
universal access represents a security risk, of course, but more
commonly, the module can be defective and then it will fail often by
crashing the entire computer.

The problem with traditional kernels compared to the planned LispOS
described in this document is similar to the difference between an
executable file resulting from a program written in \clanguage{} and a
\commonlisp{} system.%
\footnote{Thanks to Daniel Kochmański for suggesting this comparison,
  and for letting me use it here.}  In a traditional executable
program created by the linker from a collection of modules, it is hard
to replace an individual function.  The linker has turned the entire
program into a monolithic executable in which addresses have been
resolved once and for all.  Compare that situation to a typical
\commonlisp{} system in which it is normal practice to replace a
single function, redefine a class, or add a method to a generic
function, without restarting the \commonlisp{} system.  The planned
LispOS will be able to have parts of it updated, just as an ordinary
\commonlisp{} system is able to do, without rebooting.

We have had solutions to this problem for many decades. The Multics
system, for example, did not have a kernel at all. An interrupt or a
system call was executed by the user-level process that issued the
system call or that happened to be executing when the interrupt
arrived. The code that executed then was not part of a monolithic
kernel, but existed as independent programs that could be added or
replaced without restarting the system. The system could still crash,
of course, if some essential system-wide data structure was corrupted,
but most of the time, only the user-level process that issued the
request would crash, simply because the problem was limited to the
address space of a single process.  Multics did not have a kernel, but
it still had the problem of full access to its own address space, so
that the stack could be overwritten by a defective end-user program.

\subsection{Mediocre input/output performance}

Recent research \cite{Barroso:2017:AKM:3069398.3015146}
\cite{Waddington:2018:SCC:3289258.3186331} indicates that the
performance of input and output in traditional kernel-based systems is
not good enough for some of the modern devices now becoming available.
Recall that, in order to perform some input or output, an application
program must make a system call so that the kernel can perform the
operation on behalf of the application.  Things are organized this way
in order to prevent application programs from directly accessing
devices so as to protect those devices from getting incorrect
controls.  Thus, input and output requires a \emph{context switch}
which consists of the \emph{system call} itself, a change of the
\emph{page table} for address translation, and \emph{flushing the
  cache} since virtual addresses are no longer valid.  Such a context
switch typically takes around $1 \mu s$.

For typical devices such as disks, performance is not a problem
because these devices are very slow compared to the time it takes for
the context switch.  However, for some modern storage devices the slow
context switch is a problem.

\section{Objectives for a Lisp operating system}

The three main objectives of a Lisp operating system correspond to
solutions to the two main problems with existing systems as indicated
in the previous section.

\subsection{Single address space}

Instead of each application having its own address space, we propose
that all applications share a single large address space.  This way,
applications can share data simply by passing pointers around,
because a pointer is globally valid, unlike pointers in current
operating systems. 

Clearly, if there is a single address space shared by all
applications, there needs to be a different mechanism to ensure
\emph{protection} between them so that one application can not
intentionally or accidentally destroy the data of another application.
Many high-level programming languages (in particular \lisp{}, but
others as well) propose a solution to this problem by simply not
allowing users to execute arbitrary machine code.  Instead, they allow
only code that has been produced from the high-level notation of the
language and which excludes arbitrary pointer arithmetic so that the
application can only address its own data.  We shall call this kind of
system a \emph{controlled access system}%
\footnote{In the literature, this technique is sometimes called
  "trusted compiler", be we want to avoid that terminology in this
  document, because it suggests that the compiler must somehow be
  formally verified correct in order for this technique to be useful.
  Technically, the typical modern operating system would then have to
  be formally verified correct in order for the separation of address
  spaces to be a trusted mechanism.  Clearly, we use such modern
  operating systems on a daily basis without any such formal
  verification, and we are reasonably sure that it respects that
  separation.} and we shall call the typical modern operating system
where a process has full access to its address space, an
\emph{arbitrary access system}.

In order for access to be completely controlled, some optimizations
that current \commonlisp{} compilers allow, must be ruled out.
Examples of such optimizations are avoiding array-bounds checking
(typically when the \texttt{safety} quality is set to $0$) or trusting
the programmer with \texttt{dynamic-extent} declarations.  Such
optimizations could still be allowed in system code, but installing
such code would require additional privileges, equivalent to those of
system administrators on current operating systems.

It might sometimes be desirable to write an application in a
low-level language like \clanguage{} or even assembler, or it might be
necessary to run applications that have been written for other
systems.  Such applications could co-exist with the normal ones, but
they would have to work in their own address space as with current
operating systems, and with the same difficulties of communicating
with other applications.  

\subsection{Object store based on attributes}

Instead of a hierarchical file system, we propose an \emph{object
  store} which can contain any objects.  If a file (i.e. a
sequence of bytes) is desired, it would be stored as an array of
bytes.

Instead of organizing the objects into a hierarchy, objects in the
store can optionally be associated with an arbitrary number
of \emph{attributes}.  These attributes are \emph{key/value} pairs, such as for
example the date of creation of the archive entry, the creator (a
user) of the archive entry, and the \emph{access permissions} for
the entry.  Notice that attributes are not properties of the objects
themselves, but only of the archive entry that allows an object to
be accessed.  Some attributes might be derived from the contents of the
object being stored such as the \emph{sender} or the \emph{date} of
an email message.  It should be possible to accomplish most searches
of the store without accessing the objects themselves, but only the
attributes.  Occasionally, contents must be accessed such as when a raw
search of the contents of a text is wanted. 

For a more detailed description of the object store, see
\refChap{chap-object-store}. 

It is sometimes desirable to group related objects together as
with \emph{directories} of current operating systems.  Should a user
want such a group, it would simply be another object (say instances
of the class \texttt{directory}) in the store.  Users who can not
adapt to a non-hierarchical organization can even store such
directories as one of the objects inside another directory.

When (a pointer to) an object is returned to a user as a result of a
search of the object store, it is actually similar to what is called
a "capability" in the operating-system literature.  Such a
capability is essentially only a pointer with a few bits indicating
what \emph{access rights} the user has to the objects.  Each creator
may interpret the contents of those bits as he or she likes, but
typically they would be used to restrict access, so that for
instance executing a \emph{reader} method is allowed, but executing
a \emph{writer} method is not.

\subsection{Single memory abstraction}

Current computers have two kinds of memory, a \emph{primary} memory
which is fast, volatile, and expensive, and \emph{secondary} memory
which is slow, permanent, and cheap.  In contrast, the Lisp operating
system would present a single abstraction of the memory, which looks
like any interactive Lisp system, except that data is permanent.

In an implementation of a Lisp operating system on a current computer
with two kinds of memory, the primary memory simply acts as a
\emph{cache} for the secondary memory, so that the address of an
object uniquely determines where in the secondary memory it is stored.
The cache is managed as an ordinary \emph{virtual memory} with
existing algorithms.

There are some indications that future computers may feature new
memory technology with is fast, permanent, and cheap.  An
implementation of a Lisp operating system on such a computer will have
the same abstraction of the memory, but its structure will be greatly
simplified.

Since data is permanent, application writers are encouraged to
provide a sophisticated \emph{undo} facility.  

\subsection{Other features}

\subsubsection{Crash proof (maybe)}

There is extensive work on crash-proof systems, be it operating
systems or database systems.  In our opinion, this work is
confusing in that the objective is not clearly stated.

Sometimes the objective is stated as the desire that no data be lost
when power is lost.  But the solution to that problem already exists
in every laptop computer; it simply provides a \emph{battery} that
allows the system to continue to work, or to be \emph{shut down} in a
controlled way. 

Other times, the objective is stated as a protection against
defective software, so that data is stored at regular intervals
(checkpointing), perhaps combined with a \emph{transaction log} so
that the state of the system immediately before a crash can always
be recovered.  But it is very hard to protect oneself against
defective software.  There can be defects in the checkpointing code
or in the code for logging transactions, and there can be defects in
the underlying file system.  We believe that it is a better use of
developer time to find and eliminate defects than to aim for a
recovery as a result of existing defects.

\subsubsection{Multiple simultaneous environments}

To allow for a user to add methods to standard generic functions (such
as \texttt{print-object}) without interfering with other users, we
suggest that each user gets a different \emph{global environment}.
The environment maps \emph{names} to \emph{objects} such as functions,
classes, types, packages, and more.  Immutable objects (such as the
\texttt{common-lisp} package)%
\footnote{The \texttt{common-lisp} package is probably a bad example
  of an immutable object, because it could very well be necessary to
  make modifications to it on a per-user basis as a result of the
  installation of different software systems.}
can exist in several different
environments simultaneously, but other objects (such as the generic
function \texttt{print-object}) would be different in different
environments.

Multiple environments would also provide more safety for users in
that if a user inadvertently removes some system feature, then it
can be recovered from a default environment, and in the worst case a
fresh default environment could be installed for a user who
inadvertently destroyed large parts of his or her environment. 

Finally, multiple environments would simplify experimentation with
new features without running the risk of destroying the entire
system.  Different versions of a single package could exist in
different environments.

For more details on multiple environments, see
\refChap{chap-environments}.

\subsubsection{Safe concurrency}

Any modern operating system must be written to handle
\emph{concurrency}, both in terms of \emph{context switches} at
arbitrary times, but especially in terms of \emph{multiple
  simultaneous threads} of execution resulting from the execution of
the system on a computer with multiple cores.

In particular, we will guarantee the integrity of the system in the
presence of concurrency, so that there are no race conditions that may
cause the system to be in an undefined state.  We accomplish this
guarantee by well known techniques such as locks, lock-free data
structures, transactional memory, etc.

Furthermore, the global system garbage collector
\seesec{chap-garbage-collection}, will itself be parallel and
concurrent in order to take advantage of the existence of multiple
cores, and in order to minimize pauses during garbage collection.

\section{How to accomplish it}

The most important aspect of a Lisp operating system is not that all
the code be written in Lisp, but rather to present a Lisp-like
interface between users and the system and between applications and
the system.  It is therefore legitimate to take advantage of some
existing system (probably \linux{} or some \bsd{} version) in order to
provide services such as device drivers, network communication, thread
scheduling, etc.

\subsection{Create a Lisp system to be used as basis}

The first step is to create a \commonlisp{} system that can be used as a basis
for the Lisp operating system.  It should already allow for multiple
environments, and it should be available on 64-bit platforms.
Preferably, this system should use as little \clanguage{} code as
possible and interact directly with the system calls of the underlying
kernel.

\subsection{Create a single-user system as a \unix{} process}

In parallel with creating a new \commonlisp{} system, it is possible to
implement and test many of the features of the interface between the
system and the users, such as the object store (probably without
access control) using an existing \commonlisp{} system running as a process in
an ordinary operating system.  

The result of this activity would be sufficient to write or adapt
several applications such as text editors, inspectors, debuggers, GUI
interface libraries, etc. for the system.

\subsection{Create a multi-user system as a \unix{} process}

With the new \commonlisp{} system complete and the object store implemented,
it will be possible to create a full multi-user system (including
protection) as a \unix{} process, where the \unix{} system would play
the role of a virtual machine, supplying essential services such as
input/output, networking, etc. 

\subsection{Create a bootable system}

The final step is to replace the temporary \unix{} kernel with native
device drivers, and to write the code for required system services
such as the \emph{thread scheduler}, \emph{synchronization
  primitives}, etc.  Such a system could initially run in an emulator
such as QEMU in order to facilitate debugging.  Integration with an
existing operating system could be accomplished by communication with
the host operating system through its X11 server, which would avoid
the necessity of a native display server for the Lisp operating
system.