.. comment: -*- mode:rst;coding:utf-8 -*-
Lisp OS Prototype
===============================================================================
PJB axioms
-------------------------------------------------------------------------------
- single memory space abstraction.
- each lisp object reference = (object x typetag)
- environment = package namespace (1) ; a genealogy of environments
that can be copied ("forked") and modified.
- strong trusted compiler (VM abstraction); drivers would be converted
and compiled in the native environment.
Concept
-------------------------------------------------------------------------------
Capabilities as implemented in systems like EROS are optimized for the
system needs: protection of the system and access rights to the system
resources. The number of capabilities is rather limited. Usually
capabilities represent macroscopic objects (an address space, a file,
etc). Also the number of operations on a given capability is limited.
On the other hand, in a lisp system, the unit of access would be the
lisp object, and the number of operations on a lisp object is
unbounded, in any case, greater compared to OS capabilities.
Therefore we won't try to add any capability features onto lisp object
beyond what they already are, given a strongly controlled managed
memory environment: a lisp object IS a capabilty: once you have a
reference to a lisp object, you can use it with any operator (of which
you have a reference). A program can only access the lisp objects and
the operators it has access to, by tautological definition. The
protection is entirely ensured by the compiler that prevents any
unsafe or uncontrolled operation. ``(declaim (optimize (safety 999)))``.
How a lisp program can gain access to an object or operator
-------------------------------------------------------------------------------
A lisp program can gain access to a lisp object or a lisp operator
initially only thru symbols and literal object representations:
- an initial set of accessible symbols, and literal objects, are
provided to a program by the lisp reader used to read that program
source. Using ``cl:*readtable*``,
+ the lisp reader builds new literal objects:
* number
* character
* array
* pathname
* lists (cons cells)
* structure (if access to the symbol naming the structure type)
+ the lisp reader gives access to the following features:
* ``cl:quote`` (')
* ``cl:function`` (#')
* backquote/unquote underlying operator names, eg. such as list,
list*, cons, quote, etc.
* ``cl:eval`` (#.)
+ the lisp reader gives access to the symbols accessible in the
packages that are accessible, thru INTERN: ::
* symbols (``intern``, uninterned), using ``cl:*package*``
- from the objects and operators accessible thru the initial set of
accessible objects, the program can further access other objects,
with accessors and introspection operators, if they're provided by
or accessible from the initial set. For example: ::
cl:list-all-packages
cl:intern
cl:do-symbols
cl:find-symbol
cl:funcall
cl:macroexpand
cl:eval
cl:*readtable* ; gives access to the reader macro operators.
…
In a way, ``CL:LIST-ALL-PACKAGES`` is the root of all that is
accessible in Common Lisp: all the packages, all the symbols,
cl:*readtable*, etc.
With the addition of ``environments`` consisting merely in a set of
packages, the use of a current environment determines which set of
packages (particularly, CL and KEYWORD), and which set of reader
macros are used to read the program. As long as this set doesn't
include operators allowing indiscriminate access to those environment,
protection is ensured, and access is limited and controled.
Problems
-------------------------------------------------------------------------------
An implementation problem:
duplication of the CL package:
CL₁:NULL fbound to CL:NULL
CL₂:NULL fbound to CL:NULL
CL₁:NIL eq to CL:NIL
CL₂:NIL eq to CL:NIL
--------------------------------------------
side channel (cl:symbol-plist 'cl:nil)
==> cl₁:symbol-plist and cl₂:symbol-plist must be fbound to a
different function than cl:symbol-plist
CL₁:NULL fbound to CL:NULL
CL₂:NULL fbound to CL:NULL
CL₁:NIL bound to CL:NIL
CL₂:NIL bound to CL:NIL
--------------------------------------------
side channel (cl:symbol-plist cl₁:nil)
'cl₁:nil is true.
'cl₂:nil is true.
==> cl₁:symbol-plist and cl₂:symbol-plist must be fbound to a
different function than cl:symbol-plist
CL:NIL = 'CL:NIL
CL:T = 'CL:T
KEYWORD:K = 'KEYWORD:K
special variables
loop-finish, call-next-method
standard-object, etc.
Secureos
===============================================================================
http://mumble.net/jar/pubs/secureos/
http://mumble.net/~jar/pubs/secureos/secureos.html
- eros uses capabilities for its (small number of) types and purposes,
- lisp object = capability means there are a much bigger number of
types, and a much bigger number of purposes (access rights)
depending on the type of objects. rwx is to restrictive.
Notes
===============================================================================
There's another feature of unix processes: they isolate the user code
from the system code, notably in terms of user/supervisor modes, and
memory protection. (Even if as an optimization a unix process can run in
user mode, from kernel code mapped in the user address space, it's code
that is mapped read-only and entirely under control of the kernel).
There's one feature of pipes we don't find in normal chains of function
calls: they synchronize parallel processes.
So a PIPE operation can still be useful in a lisp REPL, that would run
producers/consumers in parallel, and synchronize them according to the
speed they produce/consume lisp objects.
Concerning the hierarchical file system, the proposed alternative to use
keywords to classify automatically the items goes too far in the other
direction: you have to remember the keywords!
They don't often show the list of keywords that have been used so far,
and neither do they propose easy ways to navigate them.
On the other hand, what works well with humans, is the spatial memory.
It is even used as a mnemotechnic trick to remember large quantities of
data. That's where a hierarchical file system is good, when you use it
to build a spatial structure from as high a level you want down to as
low a level you want (eg. planet, country, city, street, house, room,
cabinet, drawer, file (the real one ;-)). cf. also Apple's idea of the
desktop metaphor, where document icons are placed in _physical_
locations (the coordinates are recorded in the files metadata and are
never lost). This gives a tangible way to find documents, geographically
based, in each folder window. However, this fails when the number of items
become too big. (Personnaly I can find more easily files left unused
for a long time by walking back to their path than by searching them
graphically, or by keywords, but clearly we can't generalize).
While google sees and shows the web as a bunch of links, indexed by
keywords, the resources are still organized hierarchically:
protocol: http
tld: com
domain metamodular
(no sub*domain)
hierarchical path: /Common-Lisp
file: lispos
type: html
For some reason, it made more sense to use this hierarchical pathname,
rather than to let google index it and giving me three keywords to find
this document thru it.
In conclusion, I would not reject the hierarchical file system, but
rather provide various paradigms of file classification.
In EROS, a capability based system, there's no predefined file
system. There's a root object, and domain objects that can let the user
connect to them and objects that will manage the keys for the user, and
some keys may let the user access an object that manage files, letting
the user retrieve them according to their own schemes and rules. So:
1- file systems organization are entirely "virtual", managed by
application level objects,
2- there can be several different kind of file system managing objects,
3- the user only has access to the file system objects or other data
objects to which he has access. Systematic "chroot".
Indeed, it's more like a persistent object database than a file system
properly.
With 64-bit addressing spaces, the address can also identify network
objects, with the disk playing the role of a cache for the accessible
network objects. cf. eg. DropBox, or web caches, etc.
Against the loss of data, journaled disk I/O works well enough.
cf. journaled file systems like ext3; in the case of EROS, the system
keeps a journal, and has an optimized background task to update the
disk, which archived better I/O throughput than unix file systems.
Of course, the presence of batteries in a lot of modern computer system
helps a lot.
http://coyotos.org/docs/index.html
http://eros-os.org/eros.html
I agree that eventually a LispOS will have an archicture closer to
capability based OSes than to unix.
One important question is the role of the language or language run-time
in the architecture of the system, notably the status of the code
generated by the compiler.
1- Do we allow other code generators? Such as compilers of other languages
generating native code? If we do, it means that the level at which we
have to enforce controls is that of the processor, with user
mode/supervisor mode and MMUs, etc. And we are considering spreading
elements of the Common Lisp system across those two parts.
2- Or do we enforce that all code that runs on the system goes thru the
system compiler? After all, Common Lisp provides a low level language
(the 25 special operators), and we could reject execution of data
generated outside of the system compiler. Or like Java, we could have
a validator of code generated, before switching it to the executable
status.
In the case of EROS, while there's a single addressing space,
accessibility of address ranges depends on the capabilities the domain
has. There's memory protection enforced with the usual hardware
features (supervisor mode vs. user mode, MMU, etc). So it's more like
option 1-.
One objective for me would be to have a system that is introspectable at
the source level and which could be modified while running (like a
Smalltalk system or Lisp Machine systems). This should not be too
difficult to attain with the option 2- and the management of the
environments. Assuming the system and CL package are protected, we
could provide an operator to make a writable copy of the parts of the system or CL
environment the user wants to modify and there on, the user would be
working with a forked "virtual" machine. Actually, all domains (EROS
terminology = set of capabilities ≅process) are already like virtual
machines, since each has its own environment.
Considering this notion of lisp environment, with the need for
protection, I would say that the unit in such a system would be the CL
COMPILATION-UNIT. Which can be as small as a single function, or as big
as a whole (asdf) system compiled and optimized in a single
with-compilation-unit.
Let's say that we give names to environments or subenvironments,
hierarchically at the superior level to the package names, like:
BEACH:::CL:CAR or PJB:::CL:DEFUN.
(mount beach::: pjb:::com.informatimago.common-lisp.cesarum
:access '(:read :execute))
would make the package COM.INFORMATIMAGO.COMMON-LISP.CESARUM from the
environment PJB readable and executable in the environment BEACH.
That gives access to all the units linked to symbols in that package.
(mount pjb:::cl (copy-package system:::cl) :access '(:read :write :execute))
would replace in the PJB environment CL package by a copy of the CL package
that is modifiable.
We'll need to list all the elements to put in these environment.
- packages (mapping of package names to packages),
- global bindings of symbol in the packages:
- macro-function,
- fdefinition,
- symbol value (therefore *readtable*, therefore reader macros),
- symbol macro.
- sub-environments (so a user may create his own specific use environments),
(non exhaustive list)
We would have to add a token binding for special operators, to allow a
(any) CL package to be used to read sources to be compiled by the system
compiler. It could be a set of special macros bound to macro-function.
(setf (macro-function 'si) (macro-function 'system:::cl:if))
would copy the special operator status of IF to the symbol SI, so that:
(compile '(lambda (a b) (si (zerop a) b (1- b))))
would compile just like:
(compile '(lambda (a b) (if (zerop a) b (1- b))))
but also pjb:::cl:if,
when (not (eql (system:::system:find-package "CL" :environment "PJB")
(system:::system:find-package "CL" :environment "SYSTEM")))
About generic functions, I'm wondering if we couldn't rely on the
symbols naming the specialisers?
If beach:::example:toy and pjb:::example:toy are two different symbols
naming a class, then (defmethod print-object ((self toy) stream) …) read
and evaluated in the beach::: environment where beach:::cl:*package* is
bound to the package beach:::example, or the pjb::: environment where
pjb:::cl:*package* is bound to the package pjb:::example would define
two different methods on two different classes, even if print-object is
system:::cl:print-object in both cases. (CL already forbids definition
of standard methods on standard classes (named with symbols in CL,
ie. in system:::cl).
And I'm wondering because there could be specialization/generalization
relationships between classes across environments, so a call to
(print-object my-toy *standard-output*) could involve methods in
different environments in the (call-next-method) chain.
Now, the thing is that each time the control goes from a unit in one
environment to a unit in another environment, capabilities and
environments must be checked managed. (cf. capability OSes).
I'm not sure capability management can be reduced to some bits in
addresses. IIRC, in EROS, there's some more sophisticated processing done, to
ensure correct security rules.
One thing: if the system:::cl package is compiled as a single
compilation unit, then it's a single environment unit, which means that
when the function system:::cl:load calls system:::cl:read, it jumps to
the code in the same unit. If I take a writable copy of that package,
and redefine pjb:::cl:read, system:::cl:load will not call my new unit.
On the other hand, if we provide system:::cl with independent
compilation units for each function and macro, when the function
system:::cl:load calls system:::cl:read it goes thru the symbol cl:read
in the current environment, so when I redefine pjb:::cl:read, and call
system:::cl:load in the pjb::: environment, will call system:::cl:load
my pjb:::cl:read unit. Both options may be useful.
So we'd have a system buit upon:
- units of code (one or more functions with an ABI defined by the system
compiler).
- environments (a set of bindings: package, symbol functions, symbol
values, etc).
- persistent objects.
- capabilities to manage access to the objects and units of code.
Are the special operators (and the few other notions like bindings,
closures, etc) sufficient an API to the system compiler?
Do we need new special operators (eg. to manage capabilities)?
Do we need a lower level API (eg. LLVM)?
In a system with persistent objects, there's a system garbage collector
(even at 4TB hard disks fill quickly). Is this garbage collector able
to manage the memory for user programs too, or do we need or want to
have application level garbage collectors? (I'd guess that
generationnal garbage collectors would work at all those levels). Also,
we may want a parallel and/or real-time garbage collector (just for the
competition ;-)).
Similarly, in eg. EROS, IIRC each object brings along set of
capabilities. That would make some overhead on cons cells and other
small lisp objects. Perhaps we need to keep a notion of lisp image,
with an internal garbage collector, and those lisp images would be the
persistent data unit with its list of capabilities. But that sounds
like quite a complication: the objects inside the lisp image wouldn't be
system objects accessible from the other environments.
Let's imagine a list of objects (eg. windows) managed by the system.
(system:::display:all-windows) -> (#<window "emacs"> #<window "repl"> …)
assume the system collects those windows object from all the
environements, and builds a list of which it gives our environment read
access: we can read the car and the cdr of each cons cell. However,
some windows may be in some environment which don't give us access to
their window objects.
Calls such as (system:::display:window-position #<window "login">) or
(system:::display:send-key-event #<window "login"> #\x) would not be
able to read the login window position or write its event queue.
But other windows in the list (ours) would be accessible.
That said, when implementing a different compiler, or a virtual machine,
or a specific application, it may also be an implementation choice to
put all the data of a program in such a big "image" object, and produce
a single unit of code to manipulate these image objects.
So for example, a device driver written in C could be compiled into a
single unit of code (with lisp entry points and using system lisp
objects externally), addressing its C buffers and data structure
internally in a single "C" image object.
Perhaps we should use the word "domain" instead of "environment", since
"environment" already means something in CL, and "domain" is used in
some capability OSes to denote something similar? (But there are also
some differences, we'll see).
Too bad Jonathan Shapiro has been hired during a few years by Microsoft
so he didn't work much on coyotos, and he's somewhat sidetracked
designing BitC, his system programming language. He hasn't made much
progress on coyotos.
In any case:
1- it looks like it could work,
2- the crucial part is the design of the environments and the bindings we
put in it, along with the system compiler support for them,
3- this could be added to a CL implementation to explore without needing
the rest of the system (persistance, capability access control,
etc). Actually with techniques like IBCL (shadowing packages) and
some reader macro hackery, a prototype could be done without even
having to hack the entrails of a CL compiler.
4- apart from those OS level developments, CL applications would still
have their familiar CL environment, so there would be minimal work to
"port" them; we can provide them a posixy virtual file system and the
needed features to make them happy.
I would have to re-read the EROS and coyotos papers, (and perhaps some
other capability OS stuff), to make a summary of the relationships
between code units, data objects, environments and capabilities. And
we could hack a CL implementation to add those environments and see what
comes out of it.
Unfortunately, since I'm currently salaried, I'm left with only at most
a couple of hours a week to consacre to this project.
Basically, the idea of my LEP project was just to gather existing
lisp applications and lisp servers in a system, and see what a purely
CL environment would be able to archieve nowadays; not much I expect, but
there is some code already in a lot of application domains, so gathered
in a single place, that could be a critical mass to attract some
interest? But I'm also worried that starting with an architecture too
similar to unix systems, the user experience wouldn't be that different,
just a little more inconvenient.
From: Robert Strandh <robert.strandh@gmail.com>
Subject: Re: Initial version of a LispOS web page.
To: "Pascal J. Bourguignon" <pjb@informatimago.com>
Date: Sun, 27 Oct 2013 06:28:04 +0100 (5 days, 7 hours, 52 minutes ago)
Message-ID: <CADUeJY5RD7a9_hBqqVdvZHra1NHmUoV-A0E0zxEA8sXE57TotA@mail.gmail.com>
Hello again,
> Concerning the hierarchical file system, the proposed alternative to use
> keywords to classify automatically the items goes too far in the other
> direction: you have to remember the keywords!
>
> They don't often show the list of keywords that have been used so far,
> and neither do they propose easy ways to navigate them.
I did not mean to say that the classification was going to be made
automatically in all cases. SOME things can be automatic, like date,
subject, etc. But most keywords will be carefully chosen by the user,
just as the user carefully chooses directory names and file names
in a traditional operating system.
I imagine that at any point in time, a user has a set of keywords that
can be used to classify items. The set can be modified of course, but
it is important that keywords are chosen from this set so that an object
won't be eternally lost in case the user makes a simple typo.
Now, I haven't decided the exact nature of these keywords. Sometimes
I think they are just Lisp keywords. Sometimes I think they can be
arbitrary objects. Sometimes I think they could be optionally related by
some inheritance-like mechanism.
Let me give this some more thought so that I can come up with plausible
examples. I think such examples would clarify things a bit.
Take care,
--
Robert Strandh
From: Robert Strandh <robert.strandh@gmail.com>
Subject: Re: Initial version of a LispOS web page.
To: "Pascal J. Bourguignon" <pjb@informatimago.com>
Date: Mon, 28 Oct 2013 10:54:30 +0100 (4 days, 3 hours, 26 minutes ago)
Message-ID: <CADUeJY5rM_s3CGWhxKT44mQff8W7pZvzeYim5w7BeJpABGEzww@mail.gmail.com>
Hello,
I made a LaTeX version of the specification, and I created an GitHub
repository for it. The address is github.com/robert-strandh/LispOS.
> There's another feature of unix processes: they isolate the user code
> from the system code, notably in terms of user/supervisor modes, and
> memory protection. (Even if as an optimization a unix process can run in
> user mode, from kernel code mapped in the user address space, it's code
> that is mapped read-only and entirely under control of the kernel).
In the chapter called "Protection" in the new spec, I address this
problem.
> There's one feature of pipes we don't find in normal chains of function
> calls: they synchronize parallel processes.
>
> So a PIPE operation can still be useful in a lisp REPL, that would run
> producers/consumers in parallel, and synchronize them according to the
> speed they produce/consume lisp objects.
I agree, but I think the pipes need to be able to transmit objects
other than bytes.
> Concerning the hierarchical file system, the proposed alternative to use
> keywords to classify automatically the items goes too far in the other
> direction: you have to remember the keywords!
I wrote a new chapter called "Object store" that explains in more
detail what it is that I want to accomplish. It would be great if you
could read it and see whether you are still opposed to my suggestion.
I am very convinced that hierarchies should not be IMPOSED, because,
well, the world is not organized that way (as the document "ontology
is overrated" clearly shows), so in my suggested system there is no
hierarchy imposed. However, as I also write, nothing prevents a user
from organizing his or her objects in a hierarchy of directories if
desired.
> With 64-bit addressing spaces, the address can also identify network
> objects, with the disk playing the role of a cache for the accessible
> network objects. cf. eg. DropBox, or web caches, etc.
Maybe. Though I don't think 64 bits is enough to identify network
objects UNIQUELY. They would have to be assigned dynamically,
just like opening a file assigns a file descriptor, or like a segment
in Multics gets assigned a segment number.
> One important question is the role of the language or language run-time
> in the architecture of the system, notably the status of the code
> generated by the compiler.
>
> 1- Do we allow other code generators? Such as compilers of other languages
> generating native code? If we do, it means that the level at which we
> have to enforce controls is that of the processor, with user
> mode/supervisor mode and MMUs, etc. And we are considering spreading
> elements of the Common Lisp system across those two parts.
>
> 2- Or do we enforce that all code that runs on the system goes thru the
> system compiler? After all, Common Lisp provides a low level language
> (the 25 special operators), and we could reject execution of data
> generated outside of the system compiler. Or like Java, we could have
> a validator of code generated, before switching it to the executable
> status.
I wrote my thoughts about this in one of the new chapters.
More later....
Take care,
--
Robert Strandh
From: Robert Strandh <robert.strandh@gmail.com>
Subject: Re: Initial version of a LispOS web page.
To: "Pascal J. Bourguignon" <pjb@informatimago.com>
Date: Mon, 28 Oct 2013 12:06:29 +0100 (4 days, 2 hours, 14 minutes ago)
Message-ID: <CADUeJY45mWrZPTb9=Ck1qaiB218HLNaLVs3hqfjAptyYsG9ZXg@mail.gmail.com>
Hello again,
> One objective for me would be to have a system that is introspectable at
> the source level and which could be modified while running (like a
> Smalltalk system or Lisp Machine systems). This should not be too
> difficult to attain with the option 2- and the management of the
> environments.
I agree completely.
> Assuming the system and CL package are protected, we
> could provide an operator to make a writable copy of the parts of the system or CL
> environment the user wants to modify and there on, the user would be
> working with a forked "virtual" machine. Actually, all domains (EROS
> terminology = set of capabilities ≅process) are already like virtual
> machines, since each has its own environment.
I address this issue in one of the chapters of the latest version of
the spec on GitHub. Notice that the CL PACKAGE is always protected,
in that no symbols can be added to it or removed from it. The user
should not have such rights either. What the user might want to
modify though, is the ENVIRONMENT that maps names objects. Again,
when it comes to system FUNCTIONS, this mapping can not be modified.
But the mapping can be modified for certain system VARIABLES, such as
*PRINT-BASE*. When systems such as SBCL refer to "package locks" they
also mean that one cannot modify the part of the environment that the
HyperSpec says one is not allowed to. The user might also want to
modify certain system OBJECTS such as generic functions (by adding
methods).
In what I wrote, I suggest a two-level user environment where level 0
in inherited from the system. I don't know whether more than one two
levels would be useful. Also, I don't have an opinion as to whether
modifiable stuff is cloned when the user environment is CREATED or if
it is done lazily when the user wants to modify an object or a binding
that is permitted to modify.
> Considering this notion of lisp environment, with the need for
> protection, I would say that the unit in such a system would be the CL
> COMPILATION-UNIT. Which can be as small as a single function, or as big
> as a whole (asdf) system compiled and optimized in a single
> with-compilation-unit.
Yes, that is what I suggest as well, but in my proposal, the environment
of a compilation unit is resolved at load time.
> Let's say that we give names to environments or subenvironments,
> hierarchically at the superior level to the package names, like:
> BEACH:::CL:CAR or PJB:::CL:DEFUN.
>
> (mount beach::: pjb:::com.informatimago.common-lisp.cesarum
> :access '(:read :execute))
>
> would make the package COM.INFORMATIMAGO.COMMON-LISP.CESARUM from the
> environment PJB readable and executable in the environment BEACH.
> That gives access to all the units linked to symbols in that package.
>
> (mount pjb:::cl (copy-package system:::cl) :access '(:read :write :execute))
>
> would replace in the PJB environment CL package by a copy of the CL package
> that is modifiable.
Perhaps this is overkill. As I suggest in the document I wrote, a user can
just make any object available to any other user through the object store,
(or by sending a pointer by email).
In terms of introspection, clearly we need some way of accessing the
environments of each individual user. However by just making those environments
first-class objects as usual, this should be easy without any additional
functionality like mounting.
> We'll need to list all the elements to put in these environment.
>
> - packages (mapping of package names to packages),
> - global bindings of symbol in the packages:
> - macro-function,
> - fdefinition,
> - symbol value (therefore *readtable*, therefore reader macros),
> - symbol macro.
> - sub-environments (so a user may create his own specific use environments),
> (non exhaustive list)
Right, and types, classes, compiler macros.
I need more time to read this, because I don't know what the problem is
that your suggested functionality will solve.
Take care,
--
Robert Strandh
Crash proof & consistency of data structures
--------------------------------------------------------------------------------
From: pjb@informatimago.com (Pascal J. Bourguignon)
Subject: lispos: Crash proof (maybe)
To: Robert Strandh <robert.strandh@gmail.com>
Date: Sun, 27 Oct 2013 18:44:50 +0100 (4 days, 19 hours, 33 minutes ago)
Organization: Informatimago
Message-Id: <87mwlur4kt.fsf@informatimago.com>
Reply-to: pjb@informatimago.com
One aspect is that of the consistency of the data structures.
One thing that fsck does, is garbage collection: it checks the link
count of each node, and re-attach in /lost+found those that have a
positive link count with no directory entry, and otherwise, it removes
the nodes that have a link count of 0.
Otherwise, fsck checks and corrects the structure of two kinds of unix
"objects": the hierarchical directory, and the file blocks.
One thing that is not done by fsck, is to check the data structures
_inside_ the files.
If we want a crash proof system, with unification of primary and
secondary memory, we must be able to ensure consistency of all data in
memory.
The lisp garbage collector performs part of it: if we lose a reference
to a lisp object, then it's collected, and that's it. Perhaps it would
be a good idea to keep several references to the objects close to the
root; if the root pointer was mangled (nullified) in a crash, the
garbage collector could free everything when we restart. Otherwise
there could be an option to scan memory and recover unreferenced
objects, but this sounds very dangerous.
But the delicate part is what fsck doesn't do: checking the
consistency of data. If the crash occurs when partial bit patterns
have been commited to memory, then we may read back inconsistent or
invalid data. I guess invalid data would be caught by the run time as
type errors. Inconsistent could be more problematic, and would even
be a security risk, eg. if a reference to a string is replaced by
hasard of the bit patterns by a reference to an object belonging to a
different environment.
In the absolute, we can't count on the data written to persistent
secondary memory to be 100% consistent, after a crash.
And as you wrote, there can always be defects in software, including
system software.
We could have tools that would do consistency checks beyond what the
garbage collector would do, for example, checking for type patterns
over data structures. And depending on the security level (the
environment in/capability with which we run the tool), we could
either allow modification of the bad data structures, or cutting them
out (resetting the reference to the bad data structure so it gets
garbage collected). This would rely on an effective type system (with
satisfies functions to perform deep checks, validate the capabilities,
etc).
--
__Pascal Bourguignon__
http://www.informatimago.com/
From: Robert Strandh <robert.strandh@gmail.com>
Subject: Re: lispos: Crash proof (maybe)
To: Pascal Bourguignon <pjb@informatimago.com>
Date: Mon, 28 Oct 2013 10:35:06 +0100 (4 days, 3 hours, 44 minutes ago)
Message-ID: <CADUeJY5mj_J+Sxp0ZtW0PN6nij2fB_4ThNgJ4Qk7zNBPgVT+sw@mail.gmail.com>
Hi,
You are definitely right about everything that is required for a
crash-proof system. However, I have no idea how to accomplish it.
At some point in time, I though that Eros would be a good basis for a
crash-proof system, but then I talked to Jonathan Shapiro at a
conference, and he said that he had abandoned it partly because the
method he proposed does not scale.
Coupled with the fact that the goals of crash-proof-ness are confused
so that it seems difficult to find anything reliable in the
literature, I have given up trying to accomplish anything. When I
discussed this issue with Jim Goodman (the inventor of the
cash-coherence protocol and the speculative lock elision mechanism of
modern processors) it became clear to me that the only reasonable
crash-proof goal that one could hope to accomplish was resistance to
power failure. Furthermore, if one were to implement such a system in
software, in order for it to be effective, it would have to run with
disk cashes turned off, probably with disastrous performance as a
result. That's when I came to the conclusion that it is better then
to require enough UPS to flush all the cashes so that the system can
safely be shut down.
Of course, if you think it is interesting to do some further thinking
in this area, I am certainly not going to stop you. I make take it up
myself one day as well, but right now I have too many other fish to
fry (or cats to flog, as we say in France).
Take care,
--
Robert Strandh
bindings in environments / capabilities
--------------------------------------------------------------------------------
http://www.eros-os.org/essays/capintro.html
http://en.wikipedia.org/wiki/Capability-based_security
http://www.cap-lore.com/CapTheory/Language/
(one specific kind of capabilities)
- controlling access
- preventing access
- limiting access
- granting access
- revoking access
Operations on a cons cell: ::
(car (cons a d))
(cdr (cons a d))
(rplaca (cons a d) na)
(rplacd (cons a d) na)
(type-of (cons a d))
krw = (capability (cons a d) '(car cdr rplaca rplacd type-of))
kro = (capability (cons a d) '(car cdr type-of))
(car krw) -> a
(rplaca krw na) --> (na . d)
(car kro) -> a
(rplaca kro na) : capability-error
(operation-allowed-p 'car kro) -> t
(operation-allowed-p 'cdr kro) -> nil
DreamOS
================================================================================
From: dmytrish@gmail.com
Subject: Re: DreamOS: Operating system written in Scheme
Newsgroups: comp.lang.scheme
Date: Tue, 29 Oct 2013 10:00:52 -0700 (PDT) (2 hours, 33 minutes ago)
Message-ID: <d3e8a910-19c0-42cc-ab84-d4dc5b31022b@googlegroups.com>
On Tuesday, April 14, 2009 5:10:03 PM UTC+3, Eduardo Cavazos wrote:
> Hello,
>
> Dream is an R4RS Scheme interpreter written in assembly language by
> David Joseph Stith:
>
> http://www.stripedgazelle.org/joey/dream.html
>
> He wrote a small operating system based on Dream:
>
> http://www.stripedgazelle.org/joey/dreamos.html
>
> I was able to boot it using 'bochs'. Once booted I "mounted" the
> floppy and was able to list the files on there. It comes with a vi-
> like text editor. Here's a screenshot of DreamOS running in bochs.
> I've got the editor open on the svga driver:
>
> http://proteus.freeshell.org/dreamos-2009-04-14.png
>
> Recompiling the OS is as simple as:
>
> dream make_image.scm
>
> There's also an SVGA mode available.
>
> Both Dream and DreamOS look to be under active development; sources of
> both were updated just a few days ago.
>
> Very cool project...
>
> Ed
Is it still alive? I think it's a truly amazing project and it's very
sad the link is not valid anymore (I have a copy of the source on my
hard drive though). Also, I've been trying to find more mentions about
it on the internet and have not found anything.
Scratch
================================================================================
You've proposed to use a small number of bits in the pointers to
encode capabilities. I'm using here sets of symbols. It would be
easy to reserve one combination of access tag bits to defer to a list
of capability symbols stored in the green bytes of the object.
In EROS there's also a small number of bits, but they define coarser
objects (using at least one memory page), a small set of object types:
number, page, capability-page, node, address-space and process, and 32
capabilities per node (since the EROS system manages the capabilities
for the objects itself, storing them in separate memory pages called
nodes)).
access right capabilities: should it be "automatic"? or must each
function check for the capabilities as it wishes?
set of axioms:
PJB:
- single memory space abstraction
- each lisp object reference = capability = (object x typetag x capabilities)
- environment = package namespace (1) ; a genealogy of environments
that can be copied ("forked") and modified.
- strong trusted compiler (VM abstraction); drivers would be converted and compiled in the native environment.
- virtualization could be provided too (separate address space, untrusted environment, syscalls).
BEACH:
- single memory space abstraction
- each lisp object reference = capability = (object x typetag x capabilities)
- environment = package namespace x bindings (2) ; environments can be
_used_ with access restrictions (used read-only), by other environments.
- objet-store
- trusted compiler
- separate address space for untrusted code (virtualization). drivers would be compiled by standard compilers running in untrusted spaces.
(1) method dispatch is done on different classes (if different symbols are used to name them)
for different generic functions (if different symbols are used to define them).
/|\ (setf (symbol-function 'oops) (symbol-function 'print-object))
(defmethod oops ((self my-class) stream) 'oops)
(print-object (make-instance 'my-class) *standard-output*) -> oops
but (defmethod print-object ((self pjb:::example::my-class) stream) 'pjb)
(defmethod print-object ((self beach:::example::my-class) stream) 'beach)
can distinguish the two classes with the standard dispatch algorithm.
The only point is to ensure that the expected bigger number of
classes doesn't become a problem.
(2) method dispatch is done according to the bindings in the
environment for the generic function methods.
::
(function system:::cl:print)
(lambda () (system:::cl:write object stream system:::keyword:base system:::cl:*print-base*))
*print-base*