release 0.0.0.20 and thoughts

Francois-Rene Rideau rideau@clipper.ens.fr
Thu, 10 Aug 95 10:51:26 MET DST


">" spc
">>" fare
">>>" spc
">>>>" fare

>>    What I think and prove is lame and evil is the no-information paradigm
>> from traditional system design, by which no information is statically or
>> dynamically assumed or enforced about running threads, leading to a paranoid
>> protection mechanism that is inefficient in time space and security alike.
>   Well, my own view is not to assume anything, or at the best, assume the
> worse unless proven otherwise.
   I do not say anything otherwise. What I say is the system must support
additional dynamic information, and be able to adapt to more cooperative
environments. Not just sit with always the same static paranoid code.

> And as to verifing code to make sure it'll
> do what it says it'll do I feel is an NP-complete problem, but that's just
> me.
   It's worse than that: it's not even decidable !
But why should that prevent us from supporting it ?
That a program may run at all is undecidable. Will you design
computers so that they won't support programs that run ????????
   Will you prevent compilers from removing *any* run-time check just because
the general problem of deciding whether this is possible is undecidable ???


>   There is a real concern over security, and if you have two people using a
> single machine, you've cut your effective security in half.
   I'd rather say you double insecurity in a logarithmic scale. But sure,
security *is* my main concern. And my point is low-level checks and paranoia
can bring only inefficiency and insecurity. Only high-level proofs can bring
you real security, and brings efficiency at the same time.

> Same goes with
> computers over a network (and I hope you realize that in these enlightened
> days, the network IS the computer).  And it's in a network based distributed
> system where micro-kernels (well, designed around certain paradigms) really
> shine.  They also work better on multi-processor (MIMD) systems.
   Apart for microkernels (that completely suck), I completely agree.

>   Unless you can show me a way that cooperative multitasking will work
> across a network, in a multiprocessor computer, or both.
   I fear I cannot demonstrate that unless you provide me the machine,
plus food and shelter for the time I develop such software ;) But if
you do, sure I will !


>>    Of course, at the time when computer memories were tiny, one couldn't
>> afford complicated systems, and would prefer make it tiny, and let people
>> hack their way with it. But this is no more tolerable on nowadays'
>> computers,
>> that can handle much more memory than what the user can input.
>> 
>   And it's that thinking, where memory is infinite, that lead to the current
> state of systems, like Windows or modern Unix systems.  You may find it hard
> to believe, but I have, sitting next to me right now, a Unix based box with
> only 512K physical RAM (probably a few meg total in virtual memory) with a
> 15M harddrive.  With a kernel size of 69.4K.
   You don't seem to get my point. I have never ever said that memory was
plenty and could be wasted, or that each node could be assumed to have as
much as possible.
   What I've been saying is that there is a qualitative leap in the amount
of available memory. Fifty years ago, memory was just enough for tiny
programs to exist. Meta-operations were hand-done by humans. Then, the
computer could automate recording and restoring so humans needed retype
programs. Then it could handle simple compilation so humans needn't
hand-assemble programs. Now, the amount of memory in a computer is more
than what the user in front of it can produce during his whole life.
The day you fill a 1GB byte harddisk with just *original* non-redundant,
meaningful hand-written personal software, call me, so I buy you a new one.
Whole encyclopaedias fit a CD-ROM.
   So yes, there is some qualitative change in the amount of memory available
that system software should take into account. This is not a call to waste
available memory, but on the contrary, to use it efficiently. The waste is
the current design based on files and ad-hoc abstractions.


>>    The problem is *not* only the registerwise information state,
>> but also and
>> mostly all the rest, semaphores, etc, things that make a shared GCed
>> address space impossible 
> 
>   Count me stupid, but I sure don't see how you have to save semaphores as
> part of "state" information of a task.  Sure, semaphores are owned by tasks,
> but I've yet to come across an implimentation were they had to be "saved"
> across context switches.
   You don't seem to get that the way context switches occur is a very
important point in the system structure, that considerably affects
synchronization et al. So tell me, how will you do inter-thread GC or
any synchronization without trusting threads at all ? How will you do that
without any cooperation ? How in a non-informative preemptive scheduler
will you be able to tell what is a pointer from what isn't, and what pointed
object starts where, as each thread may have been interrupted anywhere ?
   You were talking about not wasting memory. Now what do you call that
having to reserve separate stacks, heaps, etc, for each thread, just because
you didn't want threads to cooperate ?


>> In a cooperatively informative system,
>> synchronization is enforced at compile time when possible, or with the
>> help of compile-time calling conventions.
>   I fail to see how that helps.  I keep thinking of starving philosophers
> myself.
   So imagine the multithreaded GC again. Instead of letting your
non-informative task preempt anywhere, and/or refuse it preempt for
long periods, you can enforce at compile time that it will both preempt
only a valid point, and preempt often enough. Similarly, you can have
very efficient scheduling by letting subthreads subschedule directly,
by registering the schedule policy together with the readjust routine
(both are included in a CPS routine) so that you have synchronization
and efficiency at the same time.



>>    Why forbid assembly ? Sure forbid unchecked assembly to novices,
>> or at least not outside of a paranoid isolation/emulation box. 
>   But this goes against that TUNES stands for.  Freedom of programming and
> all that, unless I'm missing something again 8-)
   Freedom of programming is not freedom to run any binary. Writing dumb
assembly code is no more programming than renaming a .gif or .mod file
to .com; and running such code should not be allowed anymore than running
such files. Freedom has never been freedom to do anything.


>> But
>> that's not worse than what exists on current systems. The problem with
>> those systems is that you *cannot* use assembly at all or anything to
>> extend the system itself. 
>   I've yet to come across a system were I can't use assembly.  Even on Unix,
> the assembler (usually called 'as') is available for anyone to use (assuming
> the C compiler is available for anyone to use).
  You don't think to get my point again. In unix you don't extend the
system at all, be it in assembly or anything. You run code in paranoidly
isolated tasks. Well there are still e.g. linux' loadable modules,
but this cancels *any* security.


>   Not that I'm trying to sell QNX here.  Just pointing out there are systems
> out there that allow to extend the system itself.
  None allow extension to be both efficient and secure.


>> Just *everything* is done in those damn paranoid
>> inefficient coarse-grained "processes".
>   Well, if you're talking about Unix, then yes, the unit of execution is
> quite coarse-grained.  But most OSes written after 1980 have the concept of
> thread (or task), which has less context than a process.
  And then these threads have no security at all, and completely
horrible semantics. Are you advocating that we should use such completely
unsecure clumsy stuff ? Don't you see threads were invented to bypass the
OS because the OS just got in the way ?


>   I don't see how you can make yield() be a sti()cli() pair.
    Well, maybe we've got mixed up: what I mean was the routine to
possibly yield execution if the timeslice is over, which may be rather
called pause(). Does that solve your problem ?

> And what is an
> "interrupted-position-dependent routine"?  And if it's what I think it is,
> how does the system "know" a routine is "interrupted-position-dependend"?  I
> thought the whole idea of interrupts was that the interrupted routine is
> unaware of being interrupted.
    Let's imagine this code for the 68K, where address registers are to
be relocated, while data registers are not.
    subl %a1,%a0
    movl %a0,%d0
Well, then if an interrupt happens between the two instructions, then
surely a0 should not be relocated, so a code position dependent adjustement
routine will have to be run before processing could go on.


>> still I'm convinced that
>> cooperatively informative systems are the most reliable way to do things.
>   Reliable, maybe.  Fast.  No.
   Fast yes. Again, you fail to consider GC and persistency.


>   And when I pause a moment to gather my thoughts in replying, the e engine
> will get the CPU, and less overhead (in general) will be lost during the
> rescheduling (say I pause for a minute) than in the e engine having to
> yield() every so often.
   Then what ? This is perfectly possible with my cooperative thingy.
You do position-dependent adjustement, the adjustement being nothing in
the main loop that computes. Really trivial example.


>>    The interrupt takes place in both systems. The difference is not there.
>> The difference is address space, page table, stack, and process info
>> swapping;
>   Well, on the 386 (assuming you are using paging and not the segments at
> all) just reloading CR3 remaps the address space, ESP readjusts the stack.
> All that's really left is the rest of the general registers (a popd will
> work wonders here) and that's about it.  I've also checked the VAX
> architecture.  Pretty much the same thing (just reloading a few certain
> registers).
   You forget to talk about all the cache miss penalty that this swapping
incur. And believe me, task switch has a severe cache miss penalty. Plus
it consumes up a lot of memory per task, thus limiting the multitasking and
involving a lot of swapping and memory waste. Not to talk about the above
impossibility of reliable synchronization for GC and persistency.


>> the problem is synchronization for garbage collection and/or checkpointing.
>> This is several hundreds of cycles (to the least) at each context switch,
>> while a cooperative way would cost only tens of cycles, so we already gain
>> at least one order of magnitude in such overheads.
>   I still don't see this.
   If you don't synchronize, you can't share heaps and stacks, so you lose
far more time swapping stacks and heaps in and out of memory than you
saved by not synchronizing. You just can't do good GC, either, though you can
use "conservative" algorithms, but then you lose long term persistency.
And if you don't synchronize, you cannot do checkpointing, and have a
resilient persistent memory.
   Resilient long-term persistency are requirements for TUNES (even though
it is intended to support stripped down versions for specific applications).


>>>>    Because the function is not actually called !
>>>> Instead, code is modified at
>>>> some point by the interrupt-driven routine that decides of a schedule...
>>>   This is better than preemtive?  It sounds preemtive to me, and while it
>>> IS
>>> possible, it sounds like more work than just having the CPU save the state
>>> and move on to another task.
>>    You can call it preemptive. And it does save time as compared to stubborn
>> state save in that you can customze it to feet your needs.
>   I'm sorry, but unless I see actual code, I'm not buying this argument.
   Information *is* needed anyway as I showed earlier. My method shows how
you lose nothing in using it as compared to your usual preemptive code,
but you gain synchronization. And yes, even then, adjusting thread state before
to save it costs less than saving the whole machine state.


[About a reflective macro system]
>   Here's a hint:  Forth.
   Thanks you, I know it for years. It ain't no hint, because (available)
Forth ain't precisely the right system to produce asm code for various
machines (including C), as is needed for TUNES. Actually, there is one
FORTH system that could help: Macro4th. Well, if you can set it up for
me so that it be used as a preprocessor to C and various assembly
languages, I buy it. Moreover, a Forth-like core is precisely what is
intended for the Tunes LLL...


>   And yes, I've written a Turing Machine.  In BASIC, lo these many years
> ago.
   I'm asking if you've written programs *for* a Turing Machine, which
is quite different. E.g. Tetris, or even a poor little multiplier. If
you have, then I expect you to understand what high-level programming
brings over low-level programming, particularly if you want efficient
code and/or reasonable development time.


>> Global conventions=a one fixed convention for all routines. e.g. C argument
>> passing.
>   I would think using a single calling convention would speed things up, if
> only to avoid the gyrations needed to massage the parameters around (or glue
> code).
   Uh ? Look at assembly generated by C compilers, and see who's doing
a lot of gyrations and parameter massaging. Procedure-specific calling
conventions could be very easy to implement for the compiler, and would
reduce all that overhead.

--    ,        	                                ,           _ 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://www.eleves.ens.fr:8080/home/rideau/Tunes/"