Macrokernels

[benignbala]

Hello all,

I read about macrokernls in a few websites.... I don understand it fully because i got confused by the examples.... A few sites claim linux as a macrokernel and a few other sites claim windows NT as a macro kernel... there are also a few sites that list both as macrokernel... I till now think linux to be a monolithic kernel... can someone help by explaining what a macrokernel is and also about the abo said confusion.....

[Combuster]

since Macrokernel does not appear on wikipedia nor the os faq, i think people have confused it with the Monolithic Kernel (i.e. the two being the same).

In any case, both linux and NT are monolithic (and thus a 'macrokernel')

[Colonel Kernel]

I think "macrokernel" is just a fancy way of saying "OS where nearly everything runs in kernel mode and is internally modular". In normal usage (i.e. -- describing software other than OSes), "monolithic" implies a big pile of spaghetti. IMO, it has taken on a double meaning in the OS realm -- it usually implies a big pile of spaghetti that all runs in kernel mode.

So whether NT or Linux are "monolithic" or "macrokernel" is somewhat subjective and open for debate.

[DeletedAccount]

I don't think NT kernel is properly documented anywhere --- If Microsoft
want's us to beleive them ...Give us the source !!!
Finally NT kernel seems to have a predominantly monolithic achitecture...

[Solar]

I think the term "monolithic kernel" is something only microkernel evangelists would call another kernel.

"Monolithic" has strong derogative undertones IMNSHO. Early versions of Linux were "monolithic", I agree, as everything was compiled into one big binary image. The invention of loadable kernel modules, however, dates back to 1995 (Linux v1.2) - ever since, Linux might still be a macrokernel, but it is not a monolith anymore.

Even Wikipedia does the microkernel / monolithic thing in the kernel artickes. Look up "monolith" in the same Wikipedia, and you will see why it is not correct to call a modular kernel "monolithic", in the semantic sense.

I agree that a microkernel looks "cleaner" on the whiteboard. But it does add complexity (IPC and context switches required where a macrokernel simply does a function call), and if you don't pay attention it isn't even easier to debug than a microkernel and suffers from reduced performance, both due to that messaging overhead

You can make a microkernel that is more stable, easier maintainable, and recovers from driver failures. But it takes lots of careful work, and it is not an "automatic given". The same amount of careful work put into the architecture of a macrokernel might well result in something better, at least from an end-user POV.

"Monolithic" implies "inherently less well-designed". I try to avoid the term.

And I think that there are very few truly "monolithic" kernels out there, outside of hobbyist OS development, and neither Linux nor Windows really qualify because those parts running in kernel space are highly modular, not a BLOB.

[DeletedAccount]

--- I said 'predominantly monolithic' not strictly 'monolithic'.....

[Solar]

Not reacting to you, just ranting in general.

[Brendan]

Hi,

I mostly agree with Solar, except for a few points...

"Monolithic" has strong derogative undertones IMNSHO.

IMHO it depends on the purpose of the OS. For an OS designed for an embedded system there's absolutely nothing wrong with a monolithic system (and no derogative undertones). I'd extended this to any platform where the hardware/devices are always the same (e.g. X-box, PDA's, etc), but not 8x86 (where there's a huge variety of hardware and no system is the same as the next).

I agree that a microkernel looks "cleaner" on the whiteboard. But it does add complexity (IPC and context switches required where a macrokernel simply does a function call), and if you don't pay attention it isn't even easier to debug than a microkernel and suffers from reduced performance, both due to that messaging overhead.

If you started with a macro-kernel and replaced the function calls with IPC, it wouldn't really be much more complex. The real difference here is that you need to explicitly define the interfaces (which is a good idea anyway). IPC also usually makes IRQ latency worse, as there's usually a mechanism where the (kernel's) IRQ handler sends IPC to the device driver (instead of the device driver being called directly via the IDT).

The other main difference is devices that do DMA or bus mastering. For a micro-kernel this often involves "bounce buffers", where the hardware transfers data to/from the device driver's address space (rather than data being transfered directly to/from other processes address spaces). This makes performance worse as there's extra copying/transfers between the device driver and other processes, but also makes implementing device drivers (and linear memory management) easier because it's easier to determine if the physical addresses being used for the transfer are valid (i.e. aren't a security/protection violation, and are within limits imposed by hardware).

The problem (especially for 80x86) is there's thousands of different devices, and therefore thousands of different device drivers - it's impossible to guarantee all of these device drivers (which are hopefully implemented by third parties) are entirely bug free. The main idea of a micro-kernel is to sacrifice performance for security/protection - to shield the rest of the system from potential bugs. Some people (e.g. Linus) would argue that a macro-kernel can optionally do anything that a micro-kernel can, but "optional" security/protection is as good as no security/protection IMHO (especially for "trojan" software).

Microsoft's recent actions (e.g. the UMDF, or User Mode Device Framework) lead me to assume that Microsoft fully understands the benefits of micro-kernels. However, Microsoft are taking a more conservative approach - shifting things that don't effect performance much to user mode mode now, and possibly planning to shift more to user mode in future (when performance differences will be less noticable).

Linux is more like a swarm of bees - each bee doing it's own thing while trying to stay with the group. Because there's no-one really leading the group it's very hard to get the entire group to change direction. Despite this there are people trying to shift some things into user-space (like FUSE). Also (AFAIK), it is possible to write full device drivers in user mode under Linux (for e.g. see this article). Unfortunately to do this you need to turn I/O protection off, so it's mostly pointless (you lose the performance advantages of a macro-kernel but don't get the security/protection advantages of a micro-kernel). The only benefit I can see here is that the device driver programmer doesn't need to mess about with the kernel's internals.


Cheers,

Brendan

[Colonel Kernel]

The main idea of a micro-kernel is to sacrifice performance for security/protection - to shield the rest of the system from potential bugs.

There is another trade-off available: Get performance and protection, but require the use of safe languages. I would argue that Singularity is a microkernel, even though by default the entire OS (kernel and processes) run in kernel mode in a single address space.

If you started with a macro-kernel and replaced the function calls with IPC, it wouldn't really be much more complex. The real difference here is that you need to explicitly define the interfaces (which is a good idea anyway).

This is exactly the modularity benefit of microkernels. In Singularity, these IPC-based interfaces are defined via "contracts" in the Sing# language. They are effectively descriptions of state machines that describe how two processes can interact with one another. Letting the compiler enforce these contracts leads to very interesting optimizations, such as bounding the queue size needed on an IPC channel and preventing one process from "spamming" another.

IMO, the microkernel idea is sound, but the 30 year legacy of CPU hardware (privilege levels, MMU-based protection, etc.) has led too many people to ignore the alternatives. Many annoying problems can be elegantly solved at the programming language level, and you don't even have to use a functional language that nobody understands.

Heh... I'm becoming like Solar with his AmigaOS posts.

[Brendan]

Hi,

There is another trade-off available: Get performance and protection, but require the use of safe languages. I would argue that Singularity is a microkernel, even though by default the entire OS (kernel and processes) run in kernel mode in a single address space.

For an OS that relies on type-safe languages, a small security hole that allows any arbitrary code to run leaves the entire system unprotected. IMHO this isn't such a good idea considering that the amount of code you need to trust includes a complex compiler...

Put it like this - what are the chances of a security hole in a monolithic kernel, and what are the chances of a security hole in Singularity, it's compiler and it's shared libraries? I'd guess it's fairly even.


Cheers,

Brendan

[Colonel Kernel]

For an OS that relies on type-safe languages, a small security hole that allows any arbitrary code to run leaves the entire system unprotected.

This is true if you choose to run everything in a single address space. However, Singularity allows for multiple hardware protection "domains" that it can run one or more software-isolated processes in separate address spaces. Obviously you lose the performance benefits of zero-copy message-passing in this case, but at least there is a choice that can be made. This paper explains this mechanism:

ftp://ftp.research.microsoft.com/pub/tr/TR-2006-43.pdf

IMHO this isn't such a good idea considering that the amount of code you need to trust includes a complex compiler...

This is only true for the short term. The plan is to eventually have the Bartok compiler emit "typed assembly" (basically native x86 code with type annotations) that can be verified by a small verifier. This would mean that the compiler itself would no longer need to be trusted.

Put it like this - what are the chances of a security hole in a monolithic kernel, and what are the chances of a security hole in Singularity, it's compiler and it's shared libraries? I'd guess it's fairly even.

Not even close. Windows is easily an order of magnitude larger than Singularity in terms of lines of code. Even if it weren't, each line of code in a monolithic kernel might be some kind of pointer-based memory access that could go awry. In a type-safe language, this is simply impossible. Remember, most of the Singularity kernel itself is implemented in the safe subset of C# (something like 17% of the source files have a little bit of unsafe code in them, and only 5% of the kernel is C++ and assembly).

The potential areas where problems could arise are limited to the low-level interrupt-handling and thread dispatching code, low-level memory management, the kernel and application garbage collectors, and the low-level I/O functionality. There is active research into the possibility of type-safe garbage collectors, although I really don't know how well it's going.

There is also the basic benefit of being a microkernel architecture, namely that drivers cannot crash the system. There is no need whatsoever to trust code from 3rd parties, which makes the problem of keeping the system stable much more tractable than in the monolithic case.

[Brendan]

Hi,

For an OS that relies on type-safe languages, a small security hole that allows any arbitrary code to run leaves the entire system unprotected.

This is true if you choose to run everything in a single address space. However, Singularity allows for multiple hardware protection "domains" that it can run one or more software-isolated processes in separate address spaces. Obviously you lose the performance benefits of zero-copy message-passing in this case, but at least there is a choice that can be made. This paper explains this mechanism:

I'm not sure, but I was thinking "hardware domains" were added so that the performance of single address space could be compared with the performance of multiple address spaces, and to allow "apples to apples" performance comparisons.

With every application in it's own hardware domain, you've got a micro-kernel again...

For overall performance difference, their macro-benchmarks are interesting. For the first test (compiling 165000 lines of code), full "micro-kernel" style hardware isolation performed better than software isolation with run-time tests. For the second test (reading 50000 files and doing nothing with the read data) they say software isolation had a far lower number of cycles, but the test itself would have been I/O bound and they don't say anything about total execution time (I'm guessing the total execution time of the second test depends on hard disk transfer times and little else).

The second test does show that the 80x86 TLB isn't very good, but people have been saying that for years - each TLB entry should be tagged with some form of address space identifier so that TLB entries don't need to be flushed during an address space switch. AFAIK other architectures do this, and strangely, AMD's hardware virtualisation also does this (but only for guest OSs).

IMHO this isn't such a good idea considering that the amount of code you need to trust includes a complex compiler...

This is only true for the short term. The plan is to eventually have the Bartok compiler emit "typed assembly" (basically native x86 code with type annotations) that can be verified by a small verifier. This would mean that the compiler itself would no longer need to be trusted.

I have difficulty getting my head around the idea of a type-safe assembler - IMHO it'd be impossible to do while still calling it an assembler.

Put it like this - what are the chances of a security hole in a monolithic kernel, and what are the chances of a security hole in Singularity, it's compiler and it's shared libraries? I'd guess it's fairly even.

Not even close. Windows is easily an order of magnitude larger than Singularity in terms of lines of code. Even if it weren't, each line of code in a monolithic kernel might be some kind of pointer-based memory access that could go awry. In a type-safe language, this is simply impossible. Remember, most of the Singularity kernel itself is implemented in the safe subset of C# (something like 17% of the source files have a little bit of unsafe code in them, and only 5% of the kernel is C++ and assembly).

Not sure if that's a fair comparison - you'd want to compare lines of code that need to be trusted. For Windows this would equate to lines of code running at CPL=0 in a normal computer (e.g. not including device drivers for devices that aren't present). For Singularity this would equate to very little run-time code, and the toolchain used to enforce the software isolation. I'd also suggest comparing Singularity to the Linux kernel would be fairer, as there's no legacy APIs in Linux or Singularity (and the GUI runs in user-space on Linux, where it belongs IMHO).

The potential areas where problems could arise are limited to the low-level interrupt-handling and thread dispatching code, low-level memory management, the kernel and application garbage collectors, and the low-level I/O functionality. There is active research into the possibility of type-safe garbage collectors, although I really don't know how well it's going.

No - if the toolchain allows any form of unsafe operation to pass through undetected you're screwed (at least without the hardware protection domains where software isolation isn't used). As a very rough estimate, GCC plus GAS plus LD adds up to a fairly large amount of code (I'm not sure how the Bartok toolchain compares)...


Cheers,

Brendan

[Colonel Kernel]

I'm not sure, but I was thinking "hardware domains" were added so that the performance of single address space could be compared with the performance of multiple address spaces, and to allow "apples to apples" performance comparisons.

It's possible that they did it for that reason... it is a research project after all. However, the idea does seem generally useful IMO, "just in case"...

With every application in it's own hardware domain, you've got a micro-kernel again...

My original point was that it never stopped being a microkernel just because the isolation mechanism changed. But yes, with one SIP per domain it becomes like a conventional microkernel that uses hardware protection.

For overall performance difference, their macro-benchmarks are interesting. For the first test (compiling 165000 lines of code), full "micro-kernel" style hardware isolation performed better than software isolation with run-time tests.

Not surprising given that the test was mostly CPU-bound to one process. The fact that bounds checking isn't free has been known for a long time, but that's the price of avoiding problems like buffer overruns.

For the second test (reading 50000 files and doing nothing with the read data) they say software isolation had a far lower number of cycles, but the test itself would have been I/O bound and they don't say anything about total execution time (I'm guessing the total execution time of the second test depends on hard disk transfer times and little else).

My guess is that they were just trying to measure the IPC overhead.

The second test does show that the 80x86 TLB isn't very good, but people have been saying that for years - each TLB entry should be tagged with some form of address space identifier so that TLB entries don't need to be flushed during an address space switch. AFAIK other architectures do this, and strangely, AMD's hardware virtualisation also does this (but only for guest OSs).

Yes, these benchmarks would be really interesting on an architecture with a tagged TLB.

I have difficulty getting my head around the idea of a type-safe assembler - IMHO it'd be impossible to do while still calling it an assembler.

I probably should have said "assembly" not "assembler"... I'm thinking maybe they really meant machine code, since I see no reason to go from a binary representation of MSIL back to a textual representation of x86 code. Nevertheless, the acronymn they use is TAL (typed assembly language).

I'm sure I'm grossly oversimplifying, but here's how I imagine verification of typed assembly works. Each type defined in the program has a particular memory layout. The type information produced alongside the machine code describes all of these layouts and maps memory operands in the machine code to particular types. The verifier can then make sure that all memory accesses to each instance of a particular type do not stray outside the acceptible interpretation of its fields. Somehow it must also be able to tell when dynamic memory has been properly allocated by the garbage collector. I'm assuming it would be pretty straightforward to ensure that the stack is manipulated correctly.

Not sure if that's a fair comparison - you'd want to compare lines of code that need to be trusted.

That's what I'm saying -- you have to trust everything in the kernel in Windows (Linux too, although it doesn't include the GUI in there). The Singularity kernel is much, much smaller in comparison. I'm not sure how big the trusted code outside the kernel is, but I'm betting that discounting Bartok it's not that big, and the TAL verifier they come up with will probably be not much bigger than something like NASM (I would guess).

No - if the toolchain allows any form of unsafe operation to pass through undetected you're screwed (at least without the hardware protection domains where software isolation isn't used). As a very rough estimate, GCC plus GAS plus LD adds up to a fairly large amount of code (I'm not sure how the Bartok toolchain compares)...

Bartok is not exactly a full-blown compiler. It is an MSIL-to-x86 translator that also verifies the MSIL for type safety and does optimization. The output of Bartok is actually the only thing that needs to be verified in order for the software isolation to be guaranteed, and like I said, a verifier need not be that big. I really wish I could work on research like this... then I could give a firmer answer.

[DeletedAccount]

Some people say that Microsoft has a hybrid kernel see this link ...
http://en.wikipedia.org/wiki/Hybrid_kernel