Build OS features in Software, not Hardware (was Re: Ne

[Alaric B. Williams]

On  4 Dec 96 at 22:50, Eric W. Biederman wrote:

> Alaric> I mean a compiler that does all the checking for illegal memory accesses and 
> Alaric> other crashmongers!
> 
> Compilers can not guarantee a program won't crash. 

They can't prove they won't go into infinite loops, but unless I've 
missed out some special case, I think they can prove they will be 
deterministic, and never access memory they shouldn't. Crashes occur 
when pointers (code or data) go wild, or the compiler produces code 
with an assumption in that is violated, such as that a case statement 
will catch all possible cases, and it doesn't so the code runs off 
the end (rare).

> I suspect the
> proper place for `proofs' is in the macros themselves.  In truth the
> only language that I have seen that do all don't allow illegal memory
> accesses are languages that can't _express_ them! 

Why should anyone have to express an illegal memory access? They 
arise either from typecasts or back doors such as external functions 
that perform typecasts. The ability to specify a constant address is 
only useful in hardware programming, and can be safely provided by a 
primitive that creates an array or other data structure at a specific 
address (eg, array of bytes at video RAM), which is welcome to refuse 
to create such arrays in the RAM used as heap etc.

> And even that isn't
> sufficient.

What special case have I missed? [worried]

> Alaric> Ok, perhaps AAM is a bad example, but my general argument is that 
> Alaric> specialised instructions in few bytes can provide amazing 
> Alaric> speed/compactness wins in the cases they come in useful. Smarter 
> Alaric> compilers can detect semantics equivelant to what this instruction 
> Alaric> does more reliably. The choice of truely useful special instructions 
> Alaric> is important, of course! We currently don't need an instruction that 
> Alaric> resolves a series of CAT scan cross sections into a 3D image, 
> Alaric> although such a CPU would be popular with medical visualisation 
> Alaric> systems!
> 
> I doubt it.  It is quite unlikely it would be quite expensive (since
> it has a small market), and slower than a high end processor with an
> optimized compiled program (probably a less well optimized i/o system
> or some other thing). 

How so? The general purpose CPU has to perform the same operations, 
plus the glue logic of seeing what it has to be doing - and a custom 
medvis chip could probably do a lot in parallel without the overhead 
of parallel CPUs!

> With hardware the motto is make the common case
> fast. 

And if the common case is deemed to be CAT scans...

> Code size is not really an issue.  It is at most a difference in a
> factor of 2 between risc and cisc. 

That's twice the price! Half the amount of code I can cram in my 8 
megs!

> The kind of instruction that could prove important are simple
> instructions that make the basic set of operations more powerful.
> Though with current technology things that make branches less frequent
> are very important.  What I suspect would be usefull is if there was
> found a basic set of operations from which both basic integer
> operations, `Multimedia operations', and floating point operations
> could all be synthesized at no more than the current cost.  Thus
> simplfy the processor and making more space for optimization.  

Ok. As I see it, specialised CPUs like the kind I keep talking 
about are very fast at a limited range of things, and consequently 
slower at things they're not suited for. RISC chips are faster than 
specialised chips doing what they don't like doing, but slower than 
truely specialised systems doing what they do best.

Something I've heard of recently is hardware compilation, where the 
'software' is compiled to a circuit which is fed into a FPGA 
(runtime-reconfigurable chip full of adders, logic gates, etc). This 
makes immense use of parallelism in the input language - only 
languages like OCCAM are considered suitable for it, apparently. And 
it can go tres fast without instruction decoding, fetching opcodes 
from RAM, etc. Future CPUs would consist of a normal CPU optimised 
for compilation (hash table lookup instruction? :-), with a huge FPGA 
network... the normal CPU compiles to the FPGA, which runs the 
software.

> Exactly.  But when it is a critical inner loop that _must_ be
> optimized, (especially starting with the compilers optimized code).
> There are some significant performance improvements you can make.
> Both applying known optimizations that your compiler doesn't make, and
> after finding the bottle necks rearanging your data structures so you
> can run the inner loop faster.

You can rearrange the data structures from your HLL. But I doubt the 
improvement of it peepholing over you peepholing is much at all. 
Large scale optimisations, I agree, will be human-controlled for some 
time...

> The fact that defining complex macros are much simpler in trivial
> grammers to the point of looking like simple code replacement (when (the scheme
> people say ) you are doing something much deeper than simple source
> code replacement).  Is a major win in comprehensibility.  

Right, Ok. Lisp et al are good at that since everything is ready 
tree-structured... one grammar I was considering looked a little like 
Lisp, except that instead of defining functions and macros like:

(name arg arg arg)

we had a list of args with arbitary namish stuff inbetween, like so:

[print [1+2i]]

There is defined [print 'arg'], and ['arg'+'arg'i]. The former is a 
procedure, the latter is a constructor for complex number objects... 
we could do away with the brackets, but that introduces the 
possibility of ambiguous syntax and increased complexity in the 
parser.

Once those semantic entities were isolated, then multimethod binding 
is used based upon operand types. Like in Ada, modules define 
classes, and specify a public interface; both public windows into the 
type structure, to access variables (which is not strictly needed), 
and public syntax elements.
 
> How a syntactic safe macro would look in a complex syntactic language
> like C++ is an interesting question. Templates and inline functions
> cover two of the common cases, but don't touch half the power.

Indeed!
 
> Eric

ABW 
--
Governments are merely protection rackets with good images.

Alaric B. Williams Internet : alaric@abwillms.demon.co.uk
<A HREF="http://www.abwillms.demon.co.uk/">http://www.abwillms.demon.co.uk/</A>