a no-kernel system

[Francois-Rene Rideau]

Dear Joyous Tunespeople,
  I was asked to explain how a no-kernel system could be done, so here do I.


### What I call a kernel ###

  Firstly, let me say again what a kernel is:
a kernel is some piece of code that *must* be called whenever different
system objects want to communicate (i.e. a syscall manager). It introduces
some useless and harmful overhead, and prevents fine-grained system objects
from being efficiently implemented, while not being able to bring any
useful functionality. It can also implement only stubborn or completely
inefficient security mechanisms (see Unices, or VSTa), when a no-kernel
scheme can cope with any kind of security complexity.
  Re-read my previous message. The mailing-list archive is on
frmap711.mathp7.jussieu.fr:pub/scratch/rideau/moose/TUNES/mailing-list-archive,
if you've lost it.

[As for Chris, when I talked about unix processes, I was criticizing a
kernel-based architecture, and explained all the harmful complications it
lead to; not about how we should do it, but about how we should avoid to do]

[As for JVS, no ! We'll not have multiple kernels, but freely-interacting
objects, none being a compulsory one, none being a kernel, which does not
mean other objects wouldn't be able to call it frequently]

[As for Mike,

2) yes, we'll provide standard objects to solve as much problems as we can,
but no, they won't constitute a kernel. They will be replaceable, and third
parties will be able and encouraged to provide compatible, incompatible, or
completely new objects to replace them. Any object provider including us
will have to *convince* and won't be able to *force* people to use one's
objects. If we ain't the best, we deserve our libraries not to be used; but
our system will still be the best anyway, because it allows free computing.
   Because there will be a world-wide net, new modules will spread quickly,
and selection of the fittest will be fast, so that there will be no problem
of "I don't have this module" or "I need tons of different but equivalent
modules". If programs are standard objects, automatic source-to-source
translation to adapt programs from one interface to the other will also
be common and help remove obsolete modules from the surface of earth.

]


### Security ###

   Raul raised the security problem. I say that the no-kernel concept allows
far more security than any kernel.
   Raul seems to believe that code should always be allowed to crash, and
thus a virtual-machine kernel would be needed for security. But why
should code always be allowed to crash ? For "performance" ? How performant
is a program that may crash ? Not at all, everyone will tell you (especially
in the industry). Are you happy with programs that crash ? No I'm sure.
So let's just not admit crashable programs. There exist well-known
techniques (type/bound/assertion checking, either static or dynamic) to
prevent any crash. And believe me, they cost much much much less than all
the paranoid stubborn VM mechanisms which require user-level security
mechanism anyway for error avoidance, management and recovery (for even
if the system can cope with process crash, other processes or threads may
not be able to).
   This means we won't be able to use unmodified standard C compilers
(like gcc), but if that was what we wanted, unix and clones would have been
enough to us. But we can very well have optional VM managers in our system
to securely execute unsafe binaries, for binary compatibility/emulation
modes. However, we won't make a compulsory kernel out of it,
because of the monstruous useless and harmful overhead it would introduce.

  As for programming bugs that may appear despise any decidable
crash-proofing mechanisms (see Turing's fundamental theorems), there are
also well-known techniques for proving program correctness, so why not use
them, and refuse any unproven program ? Of course, a "root" user could say
"admit it" as a program proof, and that's what we'd use in the meantime.

  As for Mike, no, I'm not too harsh with microkernels. Get subscribed to
the VSTa mailing-list if you don't believe me; see how they constantly
have to choose between putting highly complex mechanisms in the kernel
or outside it. In one case, they require a syscall everytime, and grow
the kernel above micro- size; in the other, they must rely on unsecure
users to use the same (complex) protocol. There is no end to their pain,
as long as the underlying compilers may produce unsecure code. And if
compilers weren't allowed to do, their kernel would become pure
overhead. Yes, I mean it. Please tell why my arguments don't stand, and
argue otherwise before you can say I'm too harsh.


### How dynamic linking works ###

  "Dynamic linking" is only some word from the ancient times to talk about
a coarse-grained lazy evaluation. Let's get the full power of lazy evaluation.
And when I say evaluation, it also includes what compiler people falsely call
"optimization" (not to say less than the neighbour).
   So, when an object really needs evaluate another, the call just gets inlined
then executed; but to allow migration, we need that source code be remembered,
and that at migrationable points, object state be uncompilable.

   Here is an example (I hope you'll be satisfied, Mike):
   Imagine that modifying an array A was inlined to a direct memory access.
Then, you can still migrate the array (if it is heavily needed somewhere
else), or even part of it (if the large array was properly segmented to allow
it, which can very well be compatible with inlining accesses). But then,
direct memory accesses will be invalidated, and any directly-accessing
routine that was not migrated together with the array are invalidated too
(or perhaps just the inlined access when possible), by replacing it with
some stub that'll call the recompiler. Recompiling is modular and may
happen from any language (but *we*'ll provide it from LLL only, at least
to begin with).
   Note that all this {,un,re}inlining stuff is costly enough so that
real-time threads should avoid them by locking all necessary resources.

   Of course, even when the resources need be locked, the sources need not,
so that they won't occupy physical memory if not needed. They may even never
be in physical memory, as another computer may have (in a nearer or farther
past) inlined it for you, and be ready to re-inline it. If we ever run on old
8 bit machines, I expect a 16 or 32 bit machine to act as a server there !
   As for RPC, we'll eventually provide a large span of RPC managers,
according to the security of the line and the remote host, and the network
topology (e.g. a host->hard disk line is considered very secure, and no
translation is needed for swapping). For lowly secure lines or hosts,
more consistency and identification checks will be done. Checks can also be
done assymetrically (e.g. the 8 bit Apple ][ client trusts blindly the 32 bit
PC server, while the server totally distrusts the client).

   Mike bothered about the security of the dynamic linker. Well, like any
other program, the linker will have to be proven correct to be accepted
(the ultimate argument to prove it being some super-user saying "admit it"
for too obscure parts). So there is no *particular* problem about the dynamic
linker. Let's use only secure software. All objects can run in a model without
protection, because all objects are inherantly secure. If you wanna run some
unsecure object, find some machine or VM inside which you are a super-user !
   Super-users are also encouraged to abandon their rights unless they really
need them. Easy to do: abandon them all, but for one emergency thread, and
allow that thread to send you objects; then use the emergency thread to send
any required object to less priviledged ones.


### The meta-protocol ###

   The meta-protocol itself is a protocol, and thus is purely conventional
and may be replaced or upgraded. Of course, as always, we'll provide the
best one, so nobody will have to get one from third-parties, but they may
if they like or need.
   It will typically include some type-checking, differenciating types to
be at least no weaker than the GC (that has to differentiate data from
pointers), but that may be stronger. Multiple type systems correspond to
multiple meta-protocols (or sub-protocols of it). Stronger meta-protocols
will also require some correctness proof. The proof may include
arguments like "object X (with argument Y) told it was true" to simplify, so
that if you don't trust, but trust X and Y, you may ask object X with argument
Y about what it thinks. Multiple proofs may be provided, so that if the
loader trusts object X1, but not object X2, you may prove using either X1 or
X2. The proof itself may require outer modules, that may have to be loaded,
etc; but the loader will ensure that no more resource will be allocated to
the object than the object is allowed.
   As for the standard type system, I'd recommend one much like the Coq
proof system uses.


### Garbage collection ###

   We'll need some distributed GC mechanism. A synchronized algorithm is
possible on a local net (or for multiple VM's in a same host); but for a
large (world-wide ?) net, some conservative GC mechanism is needed for
synchronization may be impossible (synchronization is needed to remove
cycles).
   Again, the GC is *not* a kernel. But if you want to share objects with
other machines, you'd better share a common GC protocol. This is a
standard-related problem. However, even given the protocol, you may use
any GC from any vendor, and dynamically replace it, and migrate every
single object from the address space managed by the older GC to the
address space managed by the newer one (of course, until all the objects
migrated, the older one is still needed). The same holds for the dynamic
loader: when all stubs using the older dynamic loader have been replaced,
the newer one has definitively taken over.

--    ,        	                                ,           _ v    ~  ^  --
-- Fare -- rideau@clipper.ens.fr -- Francois-Rene Rideau -- +)ang-Vu Ban --
--                                      '                   / .          --
MOOSE project member. OSL developer.                      |   |   /
Dreams about The Universal (Distributed) Database.       --- --- //
Snail mail: 6, rue Augustin Thierry 75019 PARIS FRANCE   /|\ /|\ //
Phone: 033 1 42026735                                    /|\ /|\ /