Minimalist Microkernel Memory Management

[gaf]

Almost everywhere I go there's a LAN with N computers, where a single application can only use the resources of one of those computers while the remaining N-1 computers spend most of their time idle. Another annoyance is that each computer is only used by one user at a time, despite the hardware being capable of handling multiple video cards, multiple keyboards, etc. A typical office with 10 computers could be reduced to 5 computers (2 users per computer) while increasing performance and providing additional features.

Cluster computing and multi-processor systems will definitly play an important role in the future and maybe it's really sufficient as a niche (this also depends on how microsoft and linux will react). I also like the idea of allowing a computer to be used by several users simultaniously, after all most office work (spead-sheet, serving, etc) doesn't really challenge todays systems anyways.

I meant actual code signatures (private/public key pairs), code signatures are difficult to forge, and any modification after the signing corrupts the signature (Same sort of thing used in SSL), so it is used to verify authenticity. To pre-empt malicious software, B is the only way to go but if anyone has a better idea then I'd like to hear it.

Ok, this should work pretty well. For some reason I just didn't think of using public-key encryption for the signatures to ensure that that the module/server has not been tampered with..

I think the main problem with approach A is not that developers have to give their code away, but that you'll have to check it for bugs, which can mean a lot of work if it's a big server. Maybe there's the possibility of a compromise between A and B:

- You provide a message board dedicated to 3rd party servers which users can use to exchange their experiences with a module
- A dev has to be member of the board and must have posted at least 20 messages (you should also chech their quality..)
- Once a dev has finished writing a server, he signes it with an own signature and sends it together with his board member ID and login to you
- You add his signature and some header information (serverID, release date, version, etc) of the server to the next kernel release
- A user that wants to install a module has now some information to estimate whether the dev can be trusted (number of posts by the dev, number of modules by the dev, feedback in the forum)
- If a server is bug prone or even malicious, the feedback in the forum will be very bad
- You should then exclude the server from the signature list in the next release and warn the dev that he'll be kicked if this happends too often

The advantage over approach A is that it's much harder for a stranger to release a malicous server because he usually won't have to reputation needed.

regards,
gaf

[Legend_]

There are various other situations in which it makes some more sense than in my example to use further user-level managers:
- partitions on hard-disks
- groups in general (students, profs, deans)
- quotas for users

I have a question to the example with partitions on the harddisk. How should this work without having every read/write operation go through some sort of driver. Technically, at best, I could give an application direct access to the ports, irq, memory, etc. of the harddisk controller, but on that level not directly securely to a single partition.
Or would it be mostly using a driver again?

[Legend_]

Sorry for a double post, but isn't a special pager for an app the exception and not the rule? And how would an app without a special pager perform with sigma0 being in kernel space vs. in user space?

[Brendan]

Hi,

Sorry for a double post, but isn't a special pager for an app the exception and not the rule? And how would an app without a special pager perform with sigma0 being in kernel space vs. in user space?

I'd say that'd depend on how it is implemented, how it could've been implemented (what you compare it to) and how much the application uses it.

One possible way of doing things is to implement everything as seperate modules, and then (after assessing performance bottlenecks) start building the most commonly used things into the kernel so that they use the same interface and normal software can't tell the difference between user-level services and kernel-level services. It's a fair bit more work, but it's the only way to get factual data on the performance difference (for your OS design and applications that use your OS)...

Otherwise, I'd start by measuring the cost of sending/receiving a single message (both worst case and best case).


Cheers,

Brendan

[gaf]

I have a question to the example with partitions on the harddisk. How should this work without having every read/write operation go through some sort of driver. Technically, at best, I could give an application direct access to the ports, irq, memory, etc. of the harddisk controller, but on that level not directly securely to a single partition.
Or would it be mostly using a driver again?

The driver's job is to multiplex its device and therefore all reads/writes have to go through it. What's new is that it only has to go through the driver without having to pass several user-space managers (or the kernel) first and that the driver is really low-level so that it allows things such as caching to be done by the app itself.

Sorry for a double post, but isn't a special pager for an app the exception and not the rule? And how would an app without a special pager perform with sigma0 being in kernel space vs. in user space?

1. Why shouldn't I build an OS with three pagers that are specialized on special kinds of applications to increase their performance and a fourth for all other apps that are hard to categorize or for which it doesn't matter anyways ? Today it's perfectly natural that there's only one pager, namely the kernel, but I'm sure that this will change once it's possible to have more than that. Apart from that even one user-space pager is better than none due to the increased modularity (I can still decide which one I'd like to use).

2. I doubt that you could measure any difference in performance. After all real apps also do some other things apart from allocation/delocation huge amounts of memory all the time and smaller allocations don't involve any communication with sigma0 anyways because they can be done directly from the pager's pool.

One possible way of doing things is to implement everything as seperate modules, and then (after assessing performance bottlenecks) start building the most commonly used things into the kernel so that they use the same interface and normal software can't tell the difference between user-level services and kernel-level services. It's a fair bit more work, but it's the only way to get factual data on the performance difference (for your OS design and applications that use your OS)...

If you were really to re-integrate modules that the formerly ran in user-space back into the kernel, you'd eventullay end up with the same hardwired and non-flexible design that you'd have gotten if you had started with a monolithic kernel straight away.
I'm not clinching to user-space modules, in fact a microkernel is defined by its design and not by the ring it's running on. My own kernel will (in a far, far future) allow the user to chose whether he wants to run a module (driver or manager) in user-space, which is good for devs and people that just prefere a stable system over a fast one (debugging, recovery, etc), or in kernel space which gains a slightly increased performance for hard-core gamers and overclocking freaks, but without ever even allowing modules to circumvent of the design. They will therefore have to be written in a secure script language (possibly the same that will be used for heterogenious clusters computing..) and are compiled by the kernel at installation time. The idea is to enforce the rules through the sematics of the language and not the x86 hardware (I/O map, paging, etc) so that it can be considered safe to run these modules in kernel space. This is however a pretty advanced feature, not only because it's very hard to find/design a scripting language that fullfills all requirements, but also because I - let's face it - won't run into any performance problems with my OS within the next 5 years

regards,
gaf

[Brendan]

Hi,

One possible way of doing things is to implement everything as seperate modules, and then (after assessing performance bottlenecks) start building the most commonly used things into the kernel so that they use the same interface and normal software can't tell the difference between user-level services and kernel-level services. It's a fair bit more work, but it's the only way to get factual data on the performance difference (for your OS design and applications that use your OS)...

If you were really to re-integrate modules that the formerly ran in user-space back into the kernel, you'd eventullay end up with the same hardwired and non-flexible design that you'd have gotten if you had started with a monolithic kernel straight away.

Possibly, but it'd also be possible to support any number of user-pagers and the a default/optimized pager built into the kernel - modularity where it's needed/used and performance where modularity isn't needed/used. Don't be surprised if everyone just uses the default/optimized pager though ::)...


Cheers,

Brendan

[Solar]

This thread turned into a bit of exokernel advertising, so I thought "what the heck"...

The driver's job is to multiplex its device and therefore all reads/writes have to go through it. What's new is that it only has to go through the driver without having to pass several user-space managers (or the kernel) first and that the driver is really low-level so that it allows things such as caching to be done by the app itself.

Great. So that app designers have to face the question whether the default cache is good enough (i.e., have to know how the default cache works) and whether a self-written one could improve perfomance (i.e., have to write up a prototype and benchmark it and explain results to a management that doesn't have an idea what they're talking about).

Plus a maintenance coder who suddenly finds himself checking not only the app logic, but some gritty cache implementation for bugs, too...

In my book, I don't trust app designers to cleanly distinguish between their app and their reimplementations of system. Either you write something that's "system", or you write something that is "app". But there has to be a clean break between the two, and you have to be able to always switch everything that is "system" back to defaults to check the "app" part for sanity.

Once you have to tell people they have to install cache A for their database and cache B for their browser and cache C for their mail client (I know I'm stretching the example here), having to deal with three different sets of troubles but not being able to toss it out for the default system cache...

...deep trouble.

And while I truly believe that exos can solve the various security and performance problems, I also truly believe that they are a pest when it comes to system maintainability.

I live in the reality where code is badly written and undocumented, where people write production code who should never be let close to a compiler. In this world, exo's are a recipee for a maintainers / administrators nightmare.

[gaf]

Don't be surprised if everyone just uses the default/optimized pager though ::)...

It's not my problem if the programmer isn't capable to decide which pager is best for him. I've done all I could by giving him the chance to do so, but poor programmers will always write poor programms no matter what the system is..

Great. So that app designers have to face the question whether the default cache is good enough (i.e., have to know how the default cache works) and whether a self-written one could improve perfomance (i.e., have to write up a prototype and benchmark it and explain results to a management that doesn't have an idea what they're talking about).

Plus a maintenance coder who suddenly finds himself checking not only the app logic, but some gritty cache implementation for bugs, too...

In my book, I don't trust app designers to cleanly distinguish between their app and their reimplementations of system. Either you write something that's "system", or you write something that is "app". But there has to be a clean break between the two, and you have to be able to always switch everything that is "system" back to defaults to check the "app" part for sanity.

This sounds as if the app programmer would be forced to rewrite half of the system for every new app, but that's simply not true. The average coder will simply use a library that provides him with a nice abstraction and is probably even easier to use than a kernel interface because it's more specific and doesn't have to deal with backwards compatibility et cetera.

There therefore is a clean cut between system programming (developing the library) and application programming (writing apps based on libraries). No sane programmer would try to do both at the same time by writing his application directly on top of the exokernel interface.

It's exactly the same situation in todays operating systems where programmers use libs to handle data-types in a more comfortable way (e.g STL in C++). In therory this could also be included into the kernel but it's not done to improve performance and "leave the policy to the apps". The result is that everybody (with the exception of some utter asm coders..) just uses the library and not that application writters have to develope their own linked list and tree classes..

regards,
gaf

[Legend_]

2. I doubt that you could measure any difference in performance. After all real apps also do some other things apart from allocation/delocation huge amounts of memory all the time and smaller allocations don't involve any communication with sigma0 anyways because they can be done directly from the pager's pool.

Why should I put a generic pager between the app and sigma0 anyway?
Isn't sigma0 supposed to be a generic pager?

[JoeKayzA]

Hi!

Why should I put a generic pager between the app and sigma0 anyway?
Isn't sigma0 supposed to be a generic pager?

On L4? AFAIK, no. The sigma0 server should just return a page (that corresponds to a physical page) when it is requested to do so. Nothing more. The generic pager does at least some swap-management with those pages. IIRC, on startup the pagers that get started in the system should request memory from sigma0 until it runs out of memory, so IIRC sigma0 itself is only used at startup anyway (from the docs). If a pager is substituted or added at runtime, one of the other pagers must grant the memory it needs.

cheers Joe

[Solar]

It's not my problem if the programmer isn't capable to decide which pager is best for him. I've done all I could by giving him the chance to do so, but poor programmers will always write poor programms no matter what the system is..

Ah, so the app programmer who goes for the default just as virtually every app programmer on any other system has just been degraded from "sensible" (trust the system) to "incapable" (you know, not only should you know how to write solid app code but you should also be a pro in paging algorithms...)?!?

This sounds as if the app programmer would be forced to rewrite half of the system for every new app...

Never said that.

The average coder will simply use a library that provides him with a nice abstraction and is probably even easier to use than a kernel interface because it's more specific and doesn't have to deal with backwards compatibility et cetera.

Just as on a non-exo system. Agreed so far.

There therefore is a clean cut between system programming (developing the library) and application programming (writing apps based on libraries).

Nope, there isn't. The whole concept of exo's is that you can replace the library piecemeal, adapt it to your liking, and thus create an app that uses lib X, one that uses lib Y, and one that uses parts of lib X with parts of lib Y with some proprietary pieces thrown in, all hidden somewhere in the depths of app code.

And trust me, every possible violation of sanity does exist in the sources of a company somewhere if it's large enough. None of which is documented. That is the reality of a maintenance coder, and it's bad enough without every app potientially fiddling with system policy.

No sane programmer would try to do both at the same time by writing his application directly on top of the exokernel interface.

You have no idea how many insane programmers are employed in the IT industry.

It's exactly the same situation in todays operating systems where programmers use libs to handle data-types in a more comfortable way (e.g STL in C++).

Ahhh... but now we're talking standard libraries!

In therory this could also be included into the kernel but it's not done to improve performance and "leave the policy to the apps".

I'll leave the STL aside (since there's some ABI trickery involved there) and take the C Standard Library as example. Well after all apps on a system have been compiled and installed, you could exchange the C link libs, and any new-starting app would use the new libs none the wiser. The C link libraries were replacable plug-ins, completely seperate from application code.

Linux uses the POSIX extensions to the C lib. Microsoft added MSFC. AmigaOS added dos.library and consorts. MacOS added... dunno, but every OS added its OS API to the standard, and at the bottom level that's what everyone uses, with complexity added on top, free construction happy-hour for everyone.

The thing with exo's is that the happy-hour starts at a much lower level, and I don't like the idea of the API divergence that would introduce once your system hits mainstream and a couple thousand geeks start hacking together their own "policy" libs because they think they can do better - and tens of thousands other coders using whichever libs because they can't tell the difference and fall for "nicest homepage" merits.

But as I said, that is very much philosophy and very little technology. Exos can add performance, and I see them gaining a niche in the embedded and dedicated-system sector. I just think their concepts are flawed in regards to the mainstream desktop / workstation department, where raw performance has long since been sacrificed for security, omnipresent API and rapid time-to-market anyway - think Java...

[gaf]

Nope, there isn't. The whole concept of exo's is that you can replace the library piecemeal, adapt it to your liking, and thus create an app that uses lib X, one that uses lib Y, and one that uses parts of lib X with parts of lib Y with some proprietary pieces thrown in, all hidden somewhere in the depths of app code.

(application programming)
An application programmer would never write code on the raw kernel interface, quite simply because he's (normally) not even capable of doing so. They therefore get a library that doesn't destroy their naive view of the OS and allows them to write their programms just as in any other OS.

(system programming)
The development of libraries that will be done by teams of highly skilled programmers that do know quite well what they are doing. The library will then be released along with a documentation of the methodes it supports and some info for what kind of of tasks it was made so that the app programmer doesn't have to know know how it works under the hood if he's just using it.

I'm not saying that it's not (technically) possible to mix these two, it just wouldn't be very wise. If somebody decides to do so anyway, his lousy application design isn't my fault just as you can't blame Microsoft if somebody uses undocumented systemcalls and side-effects of their API to "optimize" his programm and the whole hack gets totaly incomprehensible for everybody else and doesn't work any more once the latest service pack has been installed...

And trust me, every possible violation of sanity does exist in the sources of a company somewhere if it's large enough. None of which is documented. That is the reality of a maintenance coder, and it's bad enough without every app potientially fiddling with system policy.

Is it really my job protect the programmer from himself ?!?
Who am I to do this ? I think that most of them are quite capable to deal with it and those that aren't should maybe just stick to VisualBasic which protects them very well from the fierce coding reality..

I'll leave the STL aside (since there's some ABI trickery involved there) and take the C Standard Library as example. Well after all apps on a system have been compiled and installed, you could exchange the C link libs, and any new-starting app would use the new libs none the wiser. The C link libraries were replacable plug-ins, completely seperate from application code.

Hmm, this is not going in the direction I wanted it to..
The idea was to show that even in todays operation systems there are some fields in which apps have great liberties about "policies" (eg: data-structures, file-types) and that this neither lead to total chaos nor to the application programmer having to spend ages reinventing the wheel over and over again. An example would be a picture viewer that uses a lib to read jpeg files or an application using the STL rather than its own list-class.

The thing with exo's is that the happy-hour starts at a much lower level, and I don't like the idea of the API divergence that would introduce once your system hits mainstream and a couple thousand geeks start hacking together their own "policy" libs because they think they can do better - and tens of thousands other coders using whichever libs because they can't tell the difference and fall for "nicest homepage" merits.

I'm sure that after some time there will be a number of well accepted and elaborated libraries for all kinds of policies. This market won't be static - new ideas will appear and have to prove themselves agains the others and older projects may eventually get out-dated and disappear again.
Just have some trust in what Darwin said: "The fittest library will survive"
If you don't want to leave it all to the open market, you could also try to enforce some basic guidelines and quality by introducing minimum standards for your OS (modules will be benchmarked and categorized, detailed review released on an official site).

regards,
gaf

[Legend_]

Hi!

Why should I put a generic pager between the app and sigma0 anyway?
Isn't sigma0 supposed to be a generic pager?

On L4? AFAIK, no. The sigma0 server should just return a page (that corresponds to a physical page) when it is requested to do so. Nothing more. The generic pager does at least some swap-management with those pages. IIRC, on startup the pagers that get started in the system should request memory from sigma0 until it runs out of memory, so IIRC sigma0 itself is only used at startup anyway (from the docs). If a pager is substituted or added at runtime, one of the other pagers must grant the memory it needs.

cheers Joe

Then I have to admit that I don't see any real reason for sigma0 to exist if there is at least a common pager used for most apps ...

[gaf]

Then I have to admit that I don't see any real reason for sigma0 to exist if there is at least a common pager used for most apps ...

I'm really wondering why everybody seems to have a problem with sigma0. As JoeKayzA has already said, the current sigma0 in L4 initially holds all the whole physical memory and is meant to give it all away to the pagers at system start-up. It will never be called again and only exists because this policy could be changed in the future (eg support for pager loaded at run-time, page-frame rebalancing between the pagers) and because there is the need for some root manager from which the other pagers get their access-permission to memory (please have a look at how grant, map and unmap work).

Sigma0 is necessary from a logical point of view, increases flexibility for future implementations and it comes at the costs of a few (read: smaller than 20) kBs and no CPU time. Is this really such a bad idea ?

regards,
gaf

[Colonel Kernel]

Sigma0 is necessary from a logical point of view, increases flexibility for future implementations and it comes at the costs of a few (read: smaller than 20) kBs and no CPU time. Is this really such a bad idea ?

I think it's just a psychological barrier that people hit: (process == heavyweight). It just seems odd to have an entire process dedicated to such a simple (and apparently one-time) task. But in fact it only seems odd because we're all used to processes being fairly large resource-hungry things. My $0.02.