Writing an OS for PC

Francois-Rene Rideau rideau@clipper.ens.fr
Tue, 30 May 95 21:34:25 MET DST

>   You have some interesting concepts,
> some of which I'd like to ask a few more
> questions about.
Please do...

> The first thing that comes to mind after reading your letter
> is that it seem you are attempting to create a very strictly controlled
> environment.  Hmmm.  I don't know about that.
> I've always found difficulty in
> very controlled environments.  As a programmer, I always, but always, find
> something that I need to do where there is no way (or support).
   The only kind of control in traditional systems is paranoid forbiddance.
Sure it's stupid and uneffective, and everybody hates it. Now, that's
not what TUNES will do. The kind of control we have is higher-order
correction proof, that is, all that a human can logically say to prove
that a program is safe.
   Strong typing is a particular case of that (see the ML category of
languages). TUNES will eventually allow people to prove that assembly
routines are correct, so that people need not be root to use assembly.
Also, higher-order program manipulation allows to optimize code through
safe programmable code transformations.

>>    Preemption is made necessary by the complete unsecurity that has
>> deep roots in traditional OS design. But when possible (most of the
>> time), cooperation yields *far* better performance. In TUNES, we will
>> provide the required security for cooperation
>   What is "required security"?
   All binary code is required to abide by cooperation rules.
Compilers are required to produce such code.
By default, the system checks some PGP signature to ensure that
code was emitted from a valid source. Paranoid people can have an
empty list of valid sources, and will thus refuse to run any code
that was externally generated.

> Without preemption, you have no way of keeping
> a task from locking up the entire system.
   Yes there is: be sure beforehand that the task will not lcok up the system.
Do not run unsafe tasks. That's like removing runtime-checks when you know
the checked integer won't overflow. You can, if you're careful.

> You also have no way of executing
> work with any type of priority scheme, as far as I can tell, unless you have
> some OS implementation ideas I haven't grasped.
See the multithreading entry in the TUNES LLL page:
You can very well mix cooperation and timing.

> I do agree that cooperation
> can improve performance.
> However, after dealing with Windows for so long, I am
> really tired of "cooperation", where one task decides he's the only one that
> gets to make the CP wait for god knows how long.
   Because Windows sucks, and windows development tools suck, because they
are C based. Sure, there is no way to achieve fair cooperation using existing
tools. This is why TUNES will get rid of these.

>> Of course, this security is just impossible to achieve using C [well,
>> not completely impossible; but then, C would be only a very heavy
>> burden, and would lose *all* its advantages: existing libraries and
>> compilers]. Which is why TUNES refuses C as a standard system
>> language.
>   I'm not an advocate or an opposite of C.  I use any and all programming
> languages.  However, I don't really understand how anything is
> impossible in C,
> nor how C code could be a heavy burden on anything,
> esp. with a good optimizer.
   Yes, and with a good optimizer for Turing machine, it is possible to
compile efficient code for it, too...
   Seriously, nothing is completely impossible in any Turing-equivalent
language. But some languages make program development, maintenance,
modification, such a mess, that people should really use another language.

> (Could be kinda bias, though, I prefer assembler to all languages).  So what
> language DO you plan on using?  I can't think of anything better than C than
> assembler.
Do you know FORTH ? Lisp ? ML ? Haskell ? BETA ? SELF ? Perl ? Icon ?
Have a try !

>>    Well, sure the implementation on 32-bit computers like intel PCs
>> should be 32-bit. But TUNES intends to allow dynamic distribution on
>> heterogeneous platforms with different word size (e.g. 8, 16, 20, 32,
>> 64 or 128 bits). Thus 32 bit should not be hardwired anywhere in the
>> system, be purely implementation dependent, and should not interfere
>> with dynamic code migration.
>   Obviously, you do plan on using a high-level language
> that supports porting.
> Again, one of the things that I don't understand is how you are going to
> prevent dependencies on your word size.  From the user perspective,
> it's much
> easier.  From the OS point of view, not depending on the hardware would be
> virtually impossible, wouldn't it?
   No, it wouldn't. Why should humans be able to do it, and not machines ?
Determining the right size for a word is just a matter of knowing the
range of values some variable will represent. If people statically
know it, a machine can know it statically too. If people don't know it
statically, the machine can dynamically adjust the size much more reliably
than any human could do.

>>    TUNES will provide fine grain at all levels: you can determine
>> exactly what modules you have. A stripped specialized system should
>> fit the small ROM of some embedded micro-controller, while a full
>> featured one could take advantage of thousands gigs of distributed
>> shared memory.
>   You are aware that recapturing efficiencies in other areas are going to be
> spent on this arena?
Uh ? I'm not sure I grasp what you mean...

> One of the reasons that I am choosing to avoid
> a message
> based system is due to the fact that zillions of messages,
> function calls upon
> function calls, strict interfaces to millions of little functions
> consumes vast
> amounts of resources.  "Fine grain" sounds like it will take a significant
> amount of resource to get from the 1st user call, all the way down and back
> again, depending on what was requested of it.  I guess "fine grain" is
> relative, though, and perhaps I don't understand your breaking points.
   Message passing is just a model among others, that is isomorphic to
function call. TUNES will not priviledge any model, and let people use
whichever model suits their purpose the best. Now, as of the number of
messages being passed or functions being called, have you ever heard about
inlining function calls ? I'm sure you have, and often do it manually.
The system can very well do it dynamically, which is commonly called
"partial evaluation", and yields great results while simplifying system
design a lot: compiling, interpreting, evaluating, lazy evaluation and
futures are just special cases of partial evaluation.
   No more function calls than needed will actually happen in TUNES,
which is not the case with "kernel" or worse "microkernel" design where
lots of time is wasted in stupid lame useless runtime dispatchers.

>> Now, with existing software tools, writing usable error recovery code
>> is *very* difficult.
>   With the MVS operating system, error recovery code is quite easy
> to write and
> implement.  The OS calls the current error recovery procedure, and keeps
> cascading through previously catalogued error recovery procedures until one
> handles it to the point it wants the OS to "retry" the user's process.  The
> funnest part is actually figuring out what to do in various error conditions.
   Yeah. That's called throwing exceptions in modern programming languages.
Now, the problem is when you add a new kind of exception, lots of the new
code becomes obsolete, because you can't do automatic higher-order
transformations to make old code aware of the new exception. Thus you have
to manually update old code, and maintenance is a mess.

>> Higher-order programming should allow programmable debug code
>> generation from annotated sources.
>   Programmable debug code generation?  What's that?  Is this the same stuff
> that's written into Borlands C and ASM programs when you request debug
> support?
> This is great for user programs, but often impossible for system-oriented
> programs/tasks.
   No, it's much more than that. It's dynamic code annotation. You should be
able to dynamically annotate the debuggable code, to add arbitrary
features to it. Existing systems only allow to do very restricted things
at debugging points, with no way to automatize things.
   For example, in TUNES, profiling is a triffle: just annotate all functions
(automatically, not manually) with some automatically generated accounting
code. You can personalize this annotation in any way you want, have special
cases for special functions, etc.
   Have you ever tried to debug threaded code with an existing asm level
debugger ? Or debug a program being interpreted from a source-debugger
for the interpreter ? If you ever tried, you may have an idea about what I

>> Debugging is needed at source level. A language that requires debugging
>> is lame. A language that doesn't allow debugging is lamer even.
>   I don't disagree with the need for source-level debugging.  It is valuable
> beyond ...

> Other things are required as well, though.  No matter how well
> anything is written, things end up in endless loops, memory does get trashed,
> etc.
Endless loops yes, memory being wasted, yes, (well, in many case, one
can *prove* it won't be, but if generic enough human interaction is allowed,
yes there are problems). Memory being trashed, no: strong typing prevents it.

> Source level debugging *only* is simply not enough for all problems.
Depends on what "debugging" is. See above.

> The
> statement about a language that requires debugging is interesting.
> How in the
> world are you ever going to prevent logic errors?
By allowing not to run any program that doesn't come with a proof,
and limiting the compulsory set of admitted axioms to a very
limited amount of programs whose sources are freely available.

> Errors like moving a count
> to a pointer, a pointer to a count, and be-bopping through an array?
   Strong typing already solves such things.
Safely optimizing a strongly typed program can yield programs as
good as manually doing it will, and much safer.

> Such a
> high-level language where the statement "DO IT." generates and runs an entire
> program (exaggeration, of course, but not sarcasm)?
   The system can very well (and will) track down the meaning  of such
statements. Program manipulation is not done at ascii level, but at the
level of some internal representation...

>>    Firstly, let's make it clear that all PC specificities should not
>> modify in any way the user-visible specifications of the system. Only
>> the system and compiler back-end implementors should /need/ know
>> them. TUNES will be as portable as can be. Once portable code is
>> running, everyone is free to use the niftiest trick to make one's
>> modules faster and smaller on one's computer.
> [...]
> The point, I guess, is that I
> always want the capability to use environment-dependent code if I choose.
I never denied it: see about being free to use the niftiest tricks.

>>    Of course, as few selectors as possible should be static, but more
>> than two may be useful, be it just to allow use of code in multiple
>> priviledge rings, return to real or v86 mode, etc.
>   Depending on the efficiency requirements, I suppose.  My method is to have
> two static selectors.  The first selector is a data pointer to itself
> (both GDT 
> and all LDTs).
> The second is the OS virtual memory pool, where everything else
> in the world is anchored to, somehow, someway.
Hey ! You already need selectors for executable code ! Why have them
more or less static than the above ??

>>    Sure, we shall take the most out of the hardware capabilities. Now,
>> I can't see why the programmer would want to interfere with such
>> low-level unportable things. We shall first limit all that as much as
>> possible. Later modules can implement their own abstractions and
>> management of these.
>   Basically to report.
Only the system implementers need such reports, while debugging.
Hopefully, clean design will reduce the need for debugging...

> Report on tasks, users, memory, device characteristics
> or status, etc.  In these cases, if the memory aquired by the OS to maintain
> this information is DPL 0, it requires a task to go DPL 0 to get it.  This is
> just one more task that can kill the OS.  If you make as much as possible DPL
> 3, write-protected, you have the ability to minimize OS stability.  You even
> have the capability of running much of the OS itself DPL 3 to prevent it from
> munching itself.  It only goes DPL 0 when it must perform something requiring
> the privilege.
In my vision, security is maintained at a much higher level than the priviledge
mode. Low priviledge would be used only to enable paging write trapping, and
run emulators. Protection is a software concept: have programs that don't
crash and trash. Hardware can't help. All these hardware protections are the
stupidest things ever conceived. Should the effort put in there have been
used to produce simpler hardware and more advanced software, computers would
have been way faster and more reliable.

>>    Tasks are some coarse-grained abstraction, that only introduce
>> overhead with no gain. Only emulation boxes and unsafe code need run
>> in isolated address space.
>   Please don't take offense, but I think this statement is ridiculous.  The
> first thing that I'd say is: unsafe code = EVERYTHING.
No. Have you ever seen true strongly typing languages ?
Have you ever seen reliable compilers ?
Do you know about formal programming methods ?
All these can produce programs that you can be sure won't crash,
even if they don't do what you think they will.

> Emulation boxes, of course.
> But the first thing that comes to mind is that every task has the
> capability to use a 4GB address space.  If you don't task, then ALL tasks can
> only share 1 4GB.  Back to the days when people didn't know what virtual
> address spaces were, almost.
Yes. Who needs hardware virtual memory ? Virtual memory can be done much
better in software. The money spent in doing hardware virtual memory is
pure waste. Having fast on-chip RAM instead of lame TLBs, with fast
read/write instructions would allow truely faster computers (see the MuP21)
at much lower cost. TUNES will take advantage of hardware capabilities when
there are, but won't require any to exist.

> Also, I believe there is lots of gain.  It
> utilizes the hardwares capability to execute other tasks when the current
> task
> cannot execute, instead of having the OS software have to try to perform a
> state switch.  This is what DOS has done for years with TSR's.
   Why should hardware switch be better than software switch ?
The software knows much better what it needs to switch. Hardware designers
should provide tools to software designers, and not impose constraints on

>> In TUNES, there is no such thing as "system call".
>   This is what I think I'm getting, but still wondering about.
> It sound like
> you are trying to create a product where user tasks and system tasks
> alike hold
> hands, and dance nicely together around in a circle.
Exactly !

> Non-preemption, linking,
> load-modules for functions, no system calls, no tasks, etc.

> I still don't
> understand how you are going to prevent a programmer from bringing
> your system to it's knees by:
> a) Not following standards,
   If you mean not using a safe compiler,
the administrator can and will forbid the system to run such programs.
To run some unsafe program, you need to use some emulation box (TUNES
can emulate itself trivially) or the consent of a superuser.

> b) Forgetting a piece of logic,
Uh ? Sure a bad programmer can always crash *his* program, and all the
parts of the system he was granted random write access to.
But this will always be the case whatever you do. Nobody can ever
prevent you for doing "/bin/rm -rf /".

> c) Intent, etc.
Intent ? what's that ?

> If there's nothing I like more about MVS (One of IBM's OS's),
> is that it is virtually impossible to kill, no matter WHAT you do.
> That single
> item is probably priority #1 by FAR in my design.
I don't know MVS, and thus don't get what you mean by "kill".
Whose killing are you talking about ?

> Do you see it as an OS where
> anyone can run anything, anytime that it's required?
> Background/foreground
> jobs, online users, file servers,
> communications/network programs, programmer
> development, management reporting, etc. etc. etc.?
   Yes, anyone is free to do anything he likes with his account.
No one is bound to trust what someone else is doing, though.
If you don't trust Mr X's fileserver, don't use it. Nobody will
force you do it. But if you trust it (or trust some abstraction
over it), you can use it seamlessly like any other fileserver.
Also, you can close access to your objects, so that others can't
write it, can't annotate it, or can`t read it (Actually, just can't
*see* it).

>>    And do have a look at the TUNES page (see URL below).
>   I'll have to do that.  One reason is to find out what "annotated" means to
> you guys.  I'm having trouble relating that word to programs.
   Yeah. Unhappily, this particular point ain't always very clear
in the TUNES pages yet.
   Basically, annotating is a way of extending the meaning of an object
to a broader context. In TUNES, it is the one way to define properties of
objects, and it can be done dynamically.

--    ,        	                                ,           _ v    ~  ^  --
-- Fare -- rideau@clipper.ens.fr -- Francois-Rene Rideau -- +)ang-Vu Ban --
--                                      '                   / .          --
Join the TUNES project for a computing system based on computing freedom !
		   TUNES is a Useful, Not Expedient System
WWW page at URL: "http://acacia.ens.fr:8080/home/rideau/Tunes/"