larus larus

Niner since 2005


  • Singularity III: Revenge of the SIP

    Chris Kelly wrote:

    Fantasitic program - I have loved all 3 now. I would like to get the research paper mentioned at the end of the program - where can I find it.

    Best wishes

    Chris Kelly


    All our papers, techincal reports, etc. are on line:

  • Singularity III: Revenge of the SIP

    Would it be posible, if you were on a mission to break Singularity, to write a compiler that did not implement all the compile time checks thus allowing you access to pointers and the like, or is all code fully verified at runtime as well?

    Yes. But, we're working to fix this hole.

    Right now, rightly or wrongly, we trust our compiler to ensure type and memory safety. It isn't a good idea, since our compiler is a complex, optimizing compiler that still has bugs (as do all compilers).

    And, practically, we can't use another compiler, since we would have no reason to trust it.

    However, we're working hard to apply an idea called Typed Assembly Language (TAL) to fix this hole. TAL requires that a compiler produce a proof of the type and memory safety of the code it compilers, along with the x86 instructions (it isn't a big deal for a compiler for a type safe language, as it just has to propagate this information through all its phases). A proof isn't large and it is easy to check against the x86 code. The checker is a couple thousand lines of code, which can be very carefully written and incorporated into Singularity. With TAL, any compiler that produces a proof is usable for Singularity and we do not need to trust any (including our) compiler.

    Here's a reference to TAL

    Morrisett, G., Walker, D., Crary, K. and Glew, N. From System F to Typed Assembly Language. ACM Transactions on Programming Languages and Systems, 21 (3), 1999, 527-568.
  • Singularity III: Revenge of the SIP

    Secondly, I have a question. I was going through the paper TR-2006-43.pdf where it is mentioned that unrelated processes could have hardware barriers between them, whereas processes that share data may not have hardware barriers.

    Isn't the situation similar, if not entirely, to the way things are today? unrelated processes do not share data or data are copied between them; on the other hand, application servers are a single process where all applications are within the same address space.

    So my question is: is it worthwhile to turn the whole concept into a separate O/S built from scratch? would it not make more sense to use the knowledge gained by the singularity project to built a programming language with the advanced safety features of singularity as well as an application server which would host such processes?

    There are lots of ways in which the ideas from Singularity can be applied. We deliberately took some extreme positions (message passing, no dynamic code loading, safe languages, etc.) and tried to see where this architecture would go. As with most research, some of the ideas will have more impact than others, but it is hard to know in advance what they will be.
  • Singularity III: Revenge of the SIP

    But, IIRC, they said when you pass a message over a channel between SIPs, one of the reasons it is fast is because it is a reference to the object and not a copy.  So the other SIP has a pointer to the data.  Is this not correct?

    Yes, in most cases, we pass a pointer rather than copy data. This does not result in shared memory, since we also make sure that the process sending the message does not retain a pointer to the data. This is the result of a programming language property called linearity that our compiler enforces on data sent acrosss channels.

    There are cases where we do copy data. They arise when a system uses hardware domains to put SIPS into separate address spaces. Then, a message needs to be copied from one address space into another, which makes communication more expensive and makes hardware isolation more expensive than SIPS.

    The nice thing about linearity is that a program can't tell the difference between the two cases, so we can optimize the implementation.

    Lots more details on this in our paper:

    Language Support for Fast and Reliable Message-based Communication in the Singularity OS, Manuel Fähndrich, Mark Aiken, Chris Hawblitzel, Orion Hodson, Galen Hunt, James Larus, and Steven Levi, EuroSys 2006 Conference, pp. 177–190.

  • Singularity III: Revenge of the SIP

    Do you guys envisage running into similar perf issues that they did with OSX, which is also based on a microkernel?

    We're pretty confident that we will not run into the same performance issues as Mach, OSX, or other microkernel OS. Those systems relied on hardware mechanisms to protect the kernel against user code and to keep one process from messing with another. They had no choice, since those systems were written in C, and so got absolutely no support on the programming language side.

    Our TR ("Deconstructing Process Isolation" -- on the Singularity web site) contains some measurements of the cost of using a processor's virtual memory hardware and protection rings to provide isolation. The cost can be high, both in performance and in system complexity. In addition, it becomes a lot harder to pass information between processes when they live in seperate address spaces, so you start taking short cuts like sharing parts of the address spaces.

    SIPs reduce the cost of process isolation and communication. In one sense, they shift the checking necessary to provide isolation from run time to compile time. This is a great tradeoff, when you can take advantage of it. It also demonstrates that software schemes, when properly architected, can be faster than hardware assisted approaches. (For another interesting example, find a copy of VMWare's forthcomming ASPLOS paper "A Comparison of Software and Hardware Techniques for x86 Virtualization" -- they found that sofware VMs could run faster than VMs that used the new virtualization features in x86 processors.)
  • Singularity III: Revenge of the SIP

    Have you ever thought of emulating the old OS inside Singularity?

    Since Singularity won't reach a mature state (mature = can be used by a lot people, without going back to the DOS UI and knowing much about OS internals) in the next couple of years, emulation could be an interesting alternative.

    No. Seriously. We decided at the beginning that we wouldn't worry about backward compatibility. After all, we're not writing a commercial OS or building the replacement for Windows.

    So far, we haven't regretted this decision. It has allowed us to look at more interesting ways of doing things and not spend a lot of time trying to figure out how to run "dusty decks".
  • Singularity III: Revenge of the SIP

    That is another question that came to my mind: is it possible to write a compiler for Singularity that creates code that could do everything? With everything I mean everything in it's own process (creating pointers, load code from address x): i know that you said that channels don't allow pointers being passed to another process. Or isn't it possible because that compiler would have been loaded and compiled by your own compiler and that one wouldn't allow it... I guess the second option is the right one, isn't it?

    Do you mean an interpreter for a language like Perl or Python? We've thought about this (but haven't done it yet). At one level, it is very easy. We can write a pure (CS101) interpreter that accepts a program as a text string and executes it. That would be slower than modern interpreters that compile a program to executable code, so the next stage is to include a code generator in the interpreter. As long as the code generator is part of the trusted computing base (ie Singularity), there is not fundamental problem with this approach. An interesting research challenge is to verify the code generator, so that it doesn't need to be trusted. This is a fun area to think about, with lots of good open problems.
  • Singularity III: Revenge of the SIP

    Is the future in Multicores?
    Yes (unfortunately). Parallel programming is hard, but no one has any other idea of how to keep making processors faster.
  • Singularity III: Revenge of the SIP

    Is there an MSR team researching how to upgrad and OS over many interations ...

    This is a problem we (Singularity) are very interested in. It is not an easy problem for any piece of software, particularity a platform on which other software is built, particularly a widely successful platform.

    There are a couple of things we've done already and a few more that we're thinking about.

    First, our interfaces are strongly versioned. You compile against version 1.1.1 of the kernel API or library interface. We can tell what version code was compiled against, which makes it a lot easier to produce shims and backward compatibility layers.

    Second, applications are described by a manifest, which specifies all of the components of the application and all of the dependencies among them. The system owns the application abstraction and controls the installation process. We've designed it so that the system can read the manifest and determine if installing the application would cause any conflicts -- before a single file is installed. If there are conflicts, the system can refuse to install a new component (ie device driver) or application.

    Third, channel provide a very well defined interface between parts of the system. They have an explicit communictaion protocol (which we check) and the communications patterns are well defined (and can be constrained by the system, another story). This helps keep the system structure organized and gives us a way of making and enforcing policies (i.e., device drivers only have two channels: one to establish a connection and one for control).

    We hope that these ideas will help keep the system well structured as it evolves, but only time will tell. Right now, Singularity is a small system (a few hundred thousand lines of code), and the real challenge would only arise if it grew and was maintained by a larger, less cohesive team.

  • Singularity III: Revenge of the SIP

    This is Jim Larus, one of the researchers in the Singularity project and the people in the video. We're thrilled with the number of people who have seen the Channel 9 Singularity videos. Before we quit our day jobs and head for Hollywood, I'd be happy to answer questions about Singularity.

    Is Singularity a lot slower then traditional operating systems once hardware protection is activated?

    Probably not -- it is a bit hard to answer the question phrased this way, since you are asking for an apples to oranges comparison.

    Let me explain.

    We have measured Singularity with varying levels of hardware protection enabled. (Details in Deconstructing Process Isolation, Mark Aiken, Manuel Fähndrich, Chris Hawblitzel, Galen Hunt, James Larus, Microsoft Research Technical Report MSR-TR-2006-43)

    The results depended a lot on what was running on Singularity. A computationally intensive application wasn't affected by adding hardware protection, since it ran in one process, didn't thrash the TLB, and did little communication.

    An IO intensive application ran a lot (~30%) slower with hardware isolation, since it required frequent context switches and a large amount of interprocess communication, both of which became a lot more expensive with hardware protection.

    It would be interesting to compare these numbers against another system, but there are so many differences that it would be difficult to isolate the cost of SIPs and hardware domains vs. conventional processes. Instead, we've modelled a conventional systems as a version of Singularity in which the kernel and device drivers run in one hardware domain and application and system processes each run in their own domain. There is a considerable cost for this arrangement for the IO intensive benchmark.

    The other interesting result from this paper was that turning off run-time checks for null pointers and array bounds only saved 4.5%. Language safety isn't necessarily expensive when you have a good compiler.

    How do you make sure that a pointer does not point to any address space of another process? Are there no classes in your C# dialect that allows that? Is there no IntPtr class and therefore no way to initialize a pointer with an int?

    We rely on two aspects of the system design.

    First, application and system code (aside from the kernel and run-time system) is written in safe C#. In this language, like Java, you can't create a pointer and you can't mangle a pointer. Period. This is a property that a compiler (and some run-time tests) can check, and we do.

    We're working on reducing the amount of code that is unsafe. It is an interesting set of open research problems (i.e., what would a safe, verified garbage collector look like?), but we don't have answers yet. Stay tuned.

    The other property is that a process cannot pass a pointer from its space to any other process (or the kernel). The channels do not allow code to pass addresses (we check in the compiler) and the kernel interfaces do not allow pointer passing either. This has a lot of benefits in a garbage collected system as well, since we don't have to look for root pointers in other processes.

    So, if a process can't create a pointer and it can't be passed a pointer, there is no way for the process to dereference another SIP's objects.
  • Singularity: A research OS written in C#

    These are good questions, and the answers probably aren't clear from the video.

    1. We don't have DLLs, in the sense of dynamically loaded libraries, but we do have libraries of code that can be reused in various applications.

    2. I'm not sure what you mean by "app/drive statically linked against the code"? Code in two processes is only related by the channels between them, which have contracts expression the data that is transfered and the legal message patterns. Beyond those, there is not linking and the code in each process is entirely independent.

    3. We don't have a JIT. We precompile everything before executing it. If you don't have dynamic code loading, you don't need a JIT.


  • Singularity: A research OS written in C#

    an unsound assumption that a program isn't violating language semantics with dirty tricks, such as converting an integer to a pointer.

    I never thought of using pointers as integers a dirty trick....
    in x86 they're the same width so it doesn't really matter in the compiled code nor asm which is which type. I guess the same is true on 64 with long.

    Do you have any plans for embedded systems, 8051/2, arm?
    what about just arm? I don't forsee this going to 8 or 16 bit in short retrospect.

    Sorry to offend old-time C programmers, but it is a dirty trick to treat pointers as integers. Moreover, in any version of C after K&R C, it is also unnecessary, except in a few obvious circumstances, such as referencing a literal memory address such as a device register:  *((int*)0xffffeeee)

    The fact that it works on a particular machine is just a coincidence that makes your code more difficult to read, more difficult to port, and aviolation of the C language semantics (that why they introduced void* a long time ago).

    But, in context, I was refering to the difficulty of analyzing code with static tools. Once you start confusing pointers and integers, the tools (including optimizing compilers) pretty much give up and assume the worst.

    Types serve a purpose, both to make code clearer and easier for humans to read, but also to tell compilers and other tools that the universe of items accessible through a variable are distinct from the items accessible from another variable and that only a limited set of operations can be applied to that variable.

    And, yes, the lowest level of our runtime system obviously manipulates raw memory pointers. But, we call them memory pointers (UInt_Ptr), not integers.

    We haven't looked at 8/16 bit systems, but that does not seem like a likely direction for our work. 64 bits, on the other hand, opens a lot of interesting possibilities.

View All