Everything is a $ABSTRACTION and Microkernel Hell

[Colonel Kernel]

Code provability, when done strictly at compile time will deny several key optimization strategies

Like what?

and mess up your ability to obfuscate code in unpredictable ways; this alone should give Microsoft the shivers as that's all commercial vendors can do now to slow down reversers for a few day Unless you plan on strictly banning reversing software like IDA Pro and Ollydebug.

Are you talking about the fact that Java .class files and .NET assemblies contain metadata that makes it really easy to disassemble them back into source code?

Code provability in a dynamic environment means checking things at run time, and then you're back with the rest of us if you correctly take advantage of the hardware mechanisms to do this.

I think now you're abusing the term "code provability". MMUs don't prove that code is safe -- they stop unsafe code from touching certain areas of memory. It is also an isolation mechanism, but it has nothing to do with proving anything.

I thought to leverage some strategy to soften the advantage you were trying to obtain by carefully managing PD's and invlpg instructions accross context switches on threads to avoid TLB misses rather than haphazardly performing a mov cr3. I'm not sure, but it isn't efficient enough yet in my head.

Now you've just stopped making sense altogether.

[Avarok]

>Code provability, when done strictly at compile time will deny several key >optimization strategies

Like what?

Like anything that involves SMC, or pointer arithmetic, or any device you haven't preconceived to accept as valid code? Or does your validation mechanism include a complete VM to test it with? Is the VM undetectable? Does it follow all possible branches? Even for jump gates, switches, and the likes?

Are you talking about the fact that Java .class files and .NET assemblies contain metadata that makes it really easy to disassemble them back into source code?

No. I'm talking about the fact that you're providing a system that iterates over all the code that gets compiled on a system and checks the validity of it. I assume you must make these decisions on safeness based on some meta data? All Eve needs to do is retool your installer by setting bytes and it's suddenly her way to reverse any program on Singularity.

I wonder how quickly Eve's patch would spread.

MMU's prove that code cannot damage any other part. Hence, safe. I can talk more later. Wife...

[Crazed123]

Now you've just stopped making sense altogether.

He does that. Don't mind it.

Oh, and this discussion seems to have drifted into another rehash of the "safe code in one address space or unsafe code isolated?" debate, so I'm pulling you lot back on topic.

Does anyone have any idea for OS-level abstractions that users can use to represent pretty much what they like?

I think Unix and Plan 9 show that files represent at least one fairly good one. Files (at least under 9P) represent files and certain devices extremely well, and they can feasibly represent just about any object. Passing kernel objects to other protection domains becomes a matter of binding your files into the target namespace (which you presumably have access to as part of your namespace), and directories allow you to bind entire separate namespaces into yours.

However, files don't serve very well for representing functional concepts. You can't execute a generic file. And how do you implement the connection between a client namespace and a file-server without invoking some lower-level IPC (as Plan 9 actually does, according to their papers)?

On the other hand, I like the idea of text-based portals. Basically, a user calls the portal by naming it to the kernel, passing a string as the "message" to go through the portal. The kernel might look up some kind of "closure" string that gets prepended or appended to the message-string, and the kernel then passes the completely processed string to an entry point in the target protection domain of the portal. It runs some arbitrary code and then returns another string, which the kernel passes back to the original caller of the portal.

The advantage of such an abstraction is that it can represent both pure-functional concepts (such as libraries), as well as object-orientation (using closure-strings).

However, I don't know exactly what kind of naming should be used for portals, in this case. Should they exist as an address space, a tagged database, a hierarchical namespace like a filesystem, or something else entirely? How can protection domains pass kernel objects like portals or memory pages to each other?

I've actually thought that the best idea might be to implement the server end of a protocol like 9P as portals: entry points into a protection domain that receive a 9P message and return the reply 9P message.

[Colonel Kernel]

Ok, sorry for the hijack. I get a little involved when big-picture issues are discussed.

Back to the original question:

Now my question is: how can we best fill in "Everything is a $ABSTRACTION" to achieve not merely a uniform interface, but true extensiblity.

You won't like my answer, but I don't think "everything is a ..." is a good design philosophy for anything. It tends to end up shoe-horning at least a few concepts into a form that is unnatural for them. This is the same reason I don't believe in the superiority of "pure functional languages" like Haskell or "pure OO" languages like Smalltalk. We are trying to model life, and life is not that simple.

However, I think you can break "everything" into just a few categories of things, and aim for "everything in the ... category is a ...". The important thing is to remember why you need the abstraction in the first place. What problem are you trying to solve? You may find that the problems are different in different parts of your system.

I'll tell you what abstractions I think make sense in different parts of an OS... YMMV. First, I would distinguish between passive and active parts of the OS: Passive being resources like files, devices, and memory; active being running processes or maybe even bus-mastering devices. For passive resources, I think that "everything is a file" is a fine choice -- it has worked well for decades, and to a certain extent it makes sense to the user too (to see how it has been used to very good effect, look at how Mac OS X users install most software... Drag what is (apparently) a single file to the Applications folder).

For active agents in the system, I think "everything is a process" and "all communication is by messages" are good design philosophies.

I have to admit I'm quite stymied by all this "portals" stuff you keep talking about. Maybe you could provide a link to a good summary of the concept?

In the ideal case, we can even implement every kernel operation but one in terms of that $ABSTRACTION (portals have this property, but see above for their other problems) without breaking the uniform interface.

Correct me if I'm wrong, but from this and the questions you've asked in other threads, it sounds like you're trying to design an exokernel -- is that right? If so, you should give up on having any sort of uniform, clean, highly-abstracted interface to your kernel. Exokernels deal in low-level grotty details, and tend to manage each type of resource (network packets, disk blocks, memory pages, CPU time slices) in a completely different way. It's really out of necessity, because an exokernel is just a hardware multiplexer, and has to avoid too many privilege & address space transitions... because they aren't single-address-space systems! Ok, I'll stop now.

From there, manipulating $ABSTRACTION would allow customization and whole or partial remodeling of the OS, as well as bringing any benefits that come with $ABSTRACTION itself (like distributed 9P2000 for file I/O).

Once upon a time we had a huge 12-page thread about having such flexibility as a design goal. To summarize my position, I think it's just about unachievable, and not worth the effort, at least in the general case. But some things (like distribution ala Plan 9 or QNX) are certainly nice to have. Others, like being able to plug in different schedulers without re-compiling the kernel, I am less convinced of the need for.

My view on a lot of software design, not just OSes, used to be based on a kind of quest for something that looked "nice" and "clean" and "regular", and then I realized that we always design software to solve a problem in some context, and both the problem and context come from life which is "not nice", "very dirty", and "irregular". Since I accepted this reality, I've actually been a lot happier and more successful at design.

Before anyone complains about this post being too "abstract", remember that $ABSTRACTION is in the title of the thread.

[Crazed123]

You won't like my answer, but I don't think "everything is a ..." is a good design philosophy for anything. It tends to end up shoe-horning at least a few concepts into a form that is unnatural for them. This is the same reason I don't believe in the superiority of "pure functional languages" like Haskell or "pure OO" languages like Smalltalk. We are trying to model life, and life is not that simple.

I think you're pretty much right, but having at most 3 central concepts that you shoehorn nearly everything else into just makes things so much easier to comprehend for users and application developers. It lets them concentrate on making their software run well rather than talking to your operating system.

However, I think you can break "everything" into just a few categories of things, and aim for "everything in the ... category is a ...". The important thing is to remember why you need the abstraction in the first place. What problem are you trying to solve? You may find that the problems are different in different parts of your system.

I'll tell you what abstractions I think make sense in different parts of an OS... YMMV. First, I would distinguish between passive and active parts of the OS: Passive being resources like files, devices, and memory; active being running processes or maybe even bus-mastering devices. For passive resources, I think that "everything is a file" is a fine choice -- it has worked well for decades, and to a certain extent it makes sense to the user too (to see how it has been used to very good effect, look at how Mac OS X users install most software... Drag what is (apparently) a single file to the Applications folder).

For active agents in the system, I think "everything is a process" and "all communication is by messages" are good design philosophies.

That sounds like a good idea on the surface, but I've honestly never seen a truly simple message-passing system. Ever. I've never seen a message-passing system as simple and beautiful as writing to files is.

I have to admit I'm quite stymied by all this "portals" stuff you keep talking about. Maybe you could provide a link to a good summary of the concept?

I don't think anyone has drawn up the Wikipedia page on portals yet. Here're some links to research OSs that use them.

http://www.hpl.hp.com/personal/Alistair ... iccds96.ps -- Kea
http://www1.bell-labs.com/project/pebble/ -- Pebble
ftp://ftp.cs.ucsb.edu/pub/papers/space/iwoos91.ps.gz -- SPACE

Basically, portals are generalizations of traps or function calls to create kernel-mediated entry points by which a running thread can leave one protection domain (usually an address space) to enter another at a set point, usually carrying some data and kernel objects with it.

In the ideal case, we can even implement every kernel operation but one in terms of that $ABSTRACTION (portals have this property, but see above for their other problems) without breaking the uniform interface.

Correct me if I'm wrong, but from this and the questions you've asked in other threads, it sounds like you're trying to design an exokernel -- is that right? If so, you should give up on having any sort of uniform, clean, highly-abstracted interface to your kernel. Exokernels deal in low-level grotty details, and tend to manage each type of resource (network packets, disk blocks, memory pages, CPU time slices) in a completely different way. It's really out of necessity, because an exokernel is just a hardware multiplexer, and has to avoid too many privilege & address space transitions... because they aren't single-address-space systems! Ok, I'll stop now.

I'm no longer attempting to design a really, bleeping tiny kernel. I ran into exactly the problems you described.

Once upon a time we had a huge 12-page thread about having such flexibility as a design goal. To summarize my position, I think it's just about unachievable, and not worth the effort, at least in the general case. But some things (like distribution ala Plan 9 or QNX) are certainly nice to have. Others, like being able to plug in different schedulers without re-compiling the kernel, I am less convinced of the need for.

I think *if* I could neatly fit those continuations I made up into a broader conceptual model I would base a system on them. But otherwise probably just write a kernel that could put different schedulers in at compile-time.

My view on a lot of software design, not just OSes, used to be based on a kind of quest for something that looked "nice" and "clean" and "regular", and then I realized that we always design software to solve a problem in some context, and both the problem and context come from life which is "not nice", "very dirty", and "irregular". Since I accepted this reality, I've actually been a lot happier and more successful at design.

Before anyone complains about this post being too "abstract", remember that $ABSTRACTION is in the title of the thread.

New Jerseyian!

[Avarok]

That sounds like a good idea on the surface, but I've honestly never seen a truly simple message-passing system. Ever. I've never seen a message-passing system as simple and beautiful as writing to files is.

I tend to agree. What I think Plan9 needs:

Plan 9 "everything is a file" is a wonderful abstraction. There is however a fatal flaw in their design because their implementation of a file cannot do certain key things efficiently. These are:

• How does a file store anything structured?
  How do we put meta data in a file?
  How do we handle multiple "streams" in one file (like executables).
  How can you secure a disk image when files delimit themselves?
  How can we optimize lookups?

My proposal is rather simple really. Instead of using file start and end delimiters, they should be using "slices" as coined in the language D for digital mars. Basically, just a pointer and length. Nothing changes except; you can now have file data contained inside another file's data subsets only.

This allows you to store metadata inside of it, pluralize streams, and kill the delimiters. You can now pass only the binary data part of a bitmap, and not have to process the headers or palette. You can do the same for music. You can have multiple entry points into your program as separate files (like a library), and keep the code and data separate. While it's still not as efficient as a struct, you can load structured, named data in via the file system.

The other major possibility is to allow pre-compiled file name lookups. This opens up a can of worms unless you can handle filesystem events and reflect that to compiled file names somehow, but can make using files a great deal more efficient. At that point, it's really not that bad to suggest storing structures on your file system if you want to provide structured things publicly.

Suddenly it starts making sense to expose many more things on the file system (along the lines of proc and dev).

Thoughts

ps: Secretly, I always wanted to use "." to enter directories instead of "/". This makes a path look like an OO name lookup. "dev.fb.0"

[Crazed123]

I tend to agree. What I think Plan9 needs:

Plan 9 "everything is a file" is a wonderful abstraction. There is however a fatal flaw in their design because their implementation of a file cannot do certain key things efficiently. These are:

• How does a file store anything structured?
  How do we put meta data in a file?
  How do we handle multiple "streams" in one file (like executables).
  How can you secure a disk image when files delimit themselves?
  How can we optimize lookups?

I've always thought we could fix the metadata issue by adding one of Reiser4's main features to 9P: a file can also be a directory and a directory can also be a file. If you talk about it as a directory, you access it as a directory. Talk about it as a file, and access it as a file.

My proposal is rather simple really. Instead of using file start and end delimiters, they should be using "slices" as coined in the language D for digital mars. Basically, just a pointer and length. Nothing changes except; you can now have file data contained inside another file's data subsets only.

This allows you to store metadata inside of it, pluralize streams, and kill the delimiters. You can now pass only the binary data part of a bitmap, and not have to process the headers or palette. You can do the same for music. You can have multiple entry points into your program as separate files (like a library), and keep the code and data separate. While it's still not as efficient as a struct, you can load structured, named data in via the file system.

These are implementation details that can be built on top of unstructured files in the way that structured FTP, 9P or HTTP can be built on top of unstructured TCP that rides on really, really unstructured IP.

The other major possibility is to allow pre-compiled file name lookups. This opens up a can of worms unless you can handle filesystem events and reflect that to compiled file names somehow, but can make using files a great deal more efficient. At that point, it's really not that bad to suggest storing structures on your file system if you want to provide structured things publicly.

Suddenly it starts making sense to expose many more things on the file system (along the lines of proc and dev).

As happens all too often, I have no idea what you're talking about.

ps: Secretly, I always wanted to use "." to enter directories instead of "/". This makes a path look like an OO name lookup. "dev.fb.0"

This doesn't work because files can't have methods, ie: they are a purely passive abstraction. On the other hand, if you built a portal-dispatcher service as a file-server and mounted it via 9P...

[Avarok]

A file can have methods.

A method is simply a stream that can successfully be run as code. All you need to do is correctly provide the right address to start at; and establish some (any) mechanism to handle security.

For example, a library simply could provide:

main,0x023a_7a6e
onkeydown,0x72b0_0721
onexit,0x17cd_af00

This is interesting because we've provided a means for an executable to handle events. The key here being that we allow any caller to provide most of the registers and stack, while the called program provides the code. This is an "entry point" as described in all the documentation already when people describe "main" or "_start", I'm simply recommending it be applied more than once.

[Crazed123]

You've just described dynamic linking. Mazal tov.

Now, without loading the file as position independent code (to dynamically link against it) or loading it as a process and using some kind of portals, a file cannot have methods.

But like I said, writing to a file can be made equivalent to calling a portal. Perhaps I shall develop along those lines.

[Avarok]

I still don't understand what a portal is. I asked for a link, if you care to inform me. I still get an image of Stargate when I see the word.

To refute...

Code is data. Files are buffers of data which are named on the file system and which may (or may not) be stored to disk. While we typically use Unix semantics of read/write/create/delete, files can be used for any purpose. If we mark the page's X bit, including calling their methods.

If writing a file can be equivalent to calling a portal, then perhaps there's more to the x86 platform than I thought. I understood calling something involved using an instruction that set the EIP/RIP register.

[Crazed123]

You can't call files because you can't jump to code stored on disc.

Calling a file would have to involve reading it into memory somewhere (position independent code required if you don't want to load it as an independent process), linking it to some other program, and then letting that program call the "file". That's dynamic linking in a nutshell.

Now, I posted several links to research papers on portal systems and I defined portals earlier. Go bang your head against those, because an exact formal definition of a portal does not exist.

All I can say is, a portal is a defined place where program control can flow out of one process or protection domain and into another.

In Plan 9, operating on a file generates a 9P message that the kernel sends to a server. 9P is essentially a special case of an RPC protocol. The 9P server uses some IPC code to receive and reply to the message.

Now, since portals serve as an alternative IPC method that passes control with a small data payload rather than a large data payload without control flow (message passing), one could implement a 9P server as a portal that receives a 9P message as its small data payload.

And since 9P servers can actually implement their "filesystems" any way they want, such a server could unmarshall the 9P message and treat it as two pieces of data: a function to call (represented as the filename) and the parameters to pass it (data to write). It could then pass the unmarshalled parameters to an actual function that the filename served to name.

In this way, an easy-to-implement special case of general portals can serve to help create a more general portal system represented as files.

Now go and study!

[Avarok]

You can't call files because you can't jump to code stored on disc.

This is just a definition disagreement. I view files as being an abstraction on a data buffer which may have two states, on disk or in memory; and may be accessed by passing the file system a name.

Assuming that definition, yes, files can be called. The file system pulls them up off disk into memory. From there, most operating systems then copy/map it out to "segments" to build a "process", but you could just call an address offset from the pointer the file system gives you.

I haven't implemented IPC, but I find your guy's mechanisms to be excessively complex at a cursory glance. I personally see no reason why one couldn't just share a buffer (passing a pointer and length) and have it page mapped across. The algorithm seems simpler to me than one to copy structs around and check their fields.

PS: The above shared memory strategy has dual purpose when one allows the stack to be dynamically allocated and manipulated; you can now pass your stack as shared memory to a library function - so in essence, you literally just share the memory, push push call.

[Crazed123]

I haven't implemented IPC, but I find your guy's mechanisms to be excessively complex at a cursory glance. I personally see no reason why one couldn't just share a buffer (passing a pointer and length) and have it page mapped across. The algorithm seems simpler to me than one to copy structs around and check their fields.

So how does the buffer get mapped between processes? And why is the buffer page-aligned? What happens if the address of the buffer is currently taken in the target address space?

Have you actually understood the software engineering problems inherent in shared-memory IPC at all?

[Avarok]

1) It gets mapped by the memory driver; because only ring 0 has the privilege level to maintain page tables.

2) In a 64-bit implementation with 16 exabytes of addressable space, if you can't align array allocations you're doing something wrong.

3) You map it somewhere else. You're passing a { void* ptr; ulong length; } anyways. I said so already.

I was hoping you'd ask the more challenging questions, like how do you handle calls that don't return, or how to you account cpu time across these boundaries.

[Schol-R-LEA]

After reading this, I'm now picturing something halfway between a Xanadu ent and a persistent memory system such as EROS. I know I worked out why such a combination doesn't work well before, but I can't recall why. I need to get to sleep....