an idea about Protected Control Transferring

[lemonyii]

Recently I have been thinking about an idea from an article, “provide only a Protected Control Transferring, and leave everything even RPC to upper level.” I thought this to be powerful, but I still got some problems theoretically.

Firstly, let’s see how I wish to implement this.
1. Server register an PCT TARGET.
2. Client execute SYSENTER or SYSCALL with PTC TARGET INDEX and RETURN ADDRESS in registers.
3. The PCT CODE loads TARGET CR3 and use SYSEXIT to execute the TARGET CODE.
4. The TARGET CODE use SYSENTER to tell PCT CODE, which will use SYSEXIT to switch to the RETURN ADDRESS given by the Client.

So generally we got 2 PCTs to complete a call someone, one for calling and another for returning. The prime cost of one PCT is as following:
1. SYSENTER/SYSEXIT
2. CR3 LOAD, well I thought this would be the main problem but I don’t know how much.
3. A few PCT CODE executing, which will access the TARGET PCT TABLE ITEM and use a few bytes of PCT STACK. This depending on the following problems.

So my problems are,
1. SYSENTER/SYSEXIT switches between ring 0 and ring 3, I have to distinguish rings of the client or server. This is not too big.
2. Security is the biggest problem, which will happen at PCT RETURN on STEP4 mentioned above. Anyone can use this way to destroy another process by returning to an unexpected address in victim’s space, or the trusted server may also have bugs modifying its stored returning address. My current best way is to use a PCT STACK for each thread to trace it, but in this way a #PF may occur within PCT code, I don’t want this to happen. Another way is the client telling a magic number to the trusted server and only those who have this number can returning to the client, but this cannot prevent the server’s bugs from destroying the client.

well my target is: less time, more protection. and if you have any good idea or critics about anything I mentioned above, figure it out.
Thx!

[FallenAvatar]

Recently I have been thinking about an idea from an article, “provide only a Protected Control Transferring, and leave everything even RPC to upper level.”

Link?

- Monk

[lemonyii]

Recently I have been thinking about an idea from an article, “provide only a Protected Control Transferring, and leave everything even RPC to upper level.”

Link?

well i cannot find it any more, and that's something in my native language, which simply mentioned about it in one or two sentence(s) when referring to exokernel, no details.

[Brendan]

Hi,

So my problems are,
1. SYSENTER/SYSEXIT switches between ring 0 and ring 3, I have to distinguish rings of the client or server. This is not too big.
2. Security is the biggest problem, which will happen at PCT RETURN on STEP4 mentioned above. Anyone can use this way to destroy another process by returning to an unexpected address in victim’s space, or the trusted server may also have bugs modifying its stored returning address. My current best way is to use a PCT STACK for each thread to trace it, but in this way a #PF may occur within PCT code, I don’t want this to happen. Another way is the client telling a magic number to the trusted server and only those who have this number can returning to the client, but this cannot prevent the server’s bugs from destroying the client.

First; it'd be more like this:
1. Server registers an PCT TARGET.
2. Client executes SYSENTER or SYSCALL with PTC TARGET INDEX and RETURN ADDRESS in registers
3. PCT CODE stores RETURN ADDRESS and RETURN CR3 somewhere
4. PCT CODE loads TARGET CR3 and uses SYSEXIT to execute the TARGET CODE
5. TARGET CODE does whatever, then uses SYSENTER to return to PCT CODE
6. PCT CODE loads RETURN CR3 and uses SYSEXIT to return to RETURN ADDRESS

In this case there's no problem with security.

The first problem is that it's extremely slow. For example, if a process needs to send 1234 bytes of data to another process, then the data won't fit in the registers and you can't use a pointer, so the data is probably going to have to be broken up into 96 byte pieces (12 registers full of data at a time, where the other registers are used for things like return address, PCT target index, function number, etc); and so that 1234 bytes of data is going to be 13 PCT calls, which involves reloading CR3 (and destroying TLBs, etc) a total of 26 times.

The second problem is that there's no synchronisation. To ensure that the target is able to handle a call (and isn't in the middle of something else), you'll have to forget about SMP and avoid pre-emption (use a co-operative scheduler). This means that it's going to be very bad for modern multi-core systems. It also means that your scheduler must be bad. For example, if the CPUs are busy doing unimportant work like finding prime numbers and the user presses a key, then the keyboard driver (or GUI or an application) won't be able to preempt the unimportant work. The end user is going to have to sit there waiting for about 99 years while the CPUs find every prime number before the system can handle their key press.

The only way to avoid the second problem (e.g. support SMP and/or have a scheduler that isn't bad) is to create a new thread in the target process. In this case there's still no synchronisation; so the target process is going to have provide its own (locks/mutexes/semaphores). This can be very painful for people writing code (locks are hard, which is why a lot of software is still single-threaded even though almost all computers have been multi-core for 10 years now). It will also be less efficient - the additional overhead of creating and destroying a thread for every PCT, plus the additional task switches caused by lock contention.

If you do the right thing and provide usable synchronisation as part of the PCT; then you'll end up with some sort of traditional IPC (e.g. messaging).


Cheers,

Brendan

[dschatz]

Nice reply Brendan, a few comments:

2. Client executes SYSENTER or SYSCALL with PTC TARGET INDEX and RETURN ADDRESS in registers

I think it is a mistake to directly use a global identifier here. Make it more like a file descriptor works, a process local identifier which maps to a (hidden) global identifier.

The first problem is that it's extremely slow. For example, if a process needs to send 1234 bytes of data to another process, then the data won't fit in the registers and you can't use a pointer, so the data is probably going to have to be broken up into 96 byte pieces (12 registers full of data at a time, where the other registers are used for things like return address, PCT target index, function number, etc); and so that 1234 bytes of data is going to be 13 PCT calls, which involves reloading CR3 (and destroying TLBs, etc) a total of 26 times.

This can be alleviated if there is some way for client/server to share pages.

The second problem is that there's no synchronisation. To ensure that the target is able to handle a call (and isn't in the middle of something else), you'll have to forget about SMP and avoid pre-emption (use a co-operative scheduler). This means that it's going to be very bad for modern multi-core systems. It also means that your scheduler must be bad. For example, if the CPUs are busy doing unimportant work like finding prime numbers and the user presses a key, then the keyboard driver (or GUI or an application) won't be able to preempt the unimportant work. The end user is going to have to sit there waiting for about 99 years while the CPUs find every prime number before the system can handle their key press.

The only way to avoid the second problem (e.g. support SMP and/or have a scheduler that isn't bad) is to create a new thread in the target process. In this case there's still no synchronisation; so the target process is going to have provide its own (locks/mutexes/semaphores). This can be very painful for people writing code (locks are hard, which is why a lot of software is still single-threaded even though almost all computers have been multi-core for 10 years now). It will also be less efficient - the additional overhead of creating and destroying a thread for every PCT, plus the additional task switches caused by lock contention.

I don't understand this. The entry into the server can choose how to manage the concurrency (create a thread, enqueue the request, etc.) - This is similar to how Barrelfish IPC works. Threads are a user-space construct and so can be very cheap to create/destroy (especially with some caching). RE pre-emption: The server entry (think of it as a user-space scheduler) is the only part that should not be pre-empted, there are a number of solutions for this.

The advantage of this approach is that the request concurrency is not inhibited by the IPC model, a server can create as many (or as few) threads as necessary to handle the requests. There are some problems - off the top of my head: how can a client ensure that they will get control back from the server? (do they have to trust that the server will do that?)

[Combuster]

In practice, no request to a server will guarantee a response, and especially not a prompt response. The server might have bugs and deadlock trying to handle it. The system might help a bit by sending a default answer whenever a process gets terminated, but regardless of the mechanic, there's no guarantee.

If you block your main thread in a synchronous call to another server, you're thoroughly doing it wrong, because you're breaking the responsiveness of your calling program entirely, preventing any exits entirely. Running it over asynchronous IPC or synchronously in a secondary thread saves you from killing your UI, and having a properly functioning cancel button means you can get out of otherwise broken situations.

And from experience, some system calls in Linux can be equally bad for your health for exactly the same reason, and then it's "trusted" code you're talking to - as if it matters.


Bottom line, no IPC is inherently safe. Proper design structures are much more important, and making a habit out of not doing any waits on IO on the app's critical path saves you from most of this.

[dschatz]

Remember, in this context threads really don't exist as a system primitive. A synchronous transfer of control must have some mechanism to regain control. What happens if you get pre-empted? Does the server get your timeslice or do you get it back? There is no concept of "blocking your main thread" because a thread is a user-level construct which is scheduled by each process.

[Combuster]

Then what about the called process, will you allow it to suffer it to have code being executed there randomly stopped at an unpredictable point? Suddenly everything has to use lock-free concurrency and transaction support.

[dschatz]

Good question. I'll discuss this just with respect to scheduling, most of it also applies to IPC in general.

The way scheduler activations handled pre-emption was to save the processor state. On a future entry to the user scheduler, it can reload the processor state or store it aside and run a different user-level thread. The user-level scheduler must be re-entrant in this scheme because its possible for the scheduler itself to be preempted. Note that this requires a stack of processor states for each preemption, where the user-level scheduler can pop off these "frames". One drawback is the need to manage this stack as some dynamic resource between the kernel and process.

An alternative approach that I believe is taken by Barrelfish and Nemesis is to have only two frames - normal preemption saves to the first "thread" frame and preemption in the user-level scheduler saves to the second "scheduler" frame. When reactivated, if there is anything saved in the scheduler frame it is always reloaded by the kernel implicitly. This way, the scheduler doesn't need to be re-entrant - it is the scheduler's responsibility to clear the "thread" frame for future preemption.

[Brendan]

Hi,

Good question. I'll discuss this just with respect to scheduling, most of it also applies to IPC in general.

The way scheduler activations handled pre-emption was to save the processor state. On a future entry to the user scheduler, it can reload the processor state or store it aside and run a different user-level thread. The user-level scheduler must be re-entrant in this scheme because its possible for the scheduler itself to be preempted. Note that this requires a stack of processor states for each preemption, where the user-level scheduler can pop off these "frames". One drawback is the need to manage this stack as some dynamic resource between the kernel and process.

An alternative approach that I believe is taken by Barrelfish and Nemesis is to have only two frames - normal preemption saves to the first "thread" frame and preemption in the user-level scheduler saves to the second "scheduler" frame. When reactivated, if there is anything saved in the scheduler frame it is always reloaded by the kernel implicitly. This way, the scheduler doesn't need to be re-entrant - it is the scheduler's responsibility to clear the "thread" frame for future preemption.

And now with all the fixes, it's no longer a simple "protected control transfer" and has grown into full fledged IPC (with buffers/shared pages, scheduling mixed up in it, etc).

Note that user-level schedulers are a worthless joke - there's no way for one process to know that its threads are less important than threads in other processes, so it fails the "do the important work first" golden rule. Of course you could have something keeping track of the state and priority of all threads (in all processes) and have a bunch of communication between the user-level schedulers and the "global thread state tracker"; but in that case it'd be much more efficient to do scheduling in the "global thread state tracker" and avoid the need for user-level schedulers and the additional communication and all the race conditions.


Cheers,

Brendan

[Combuster]

Note that user-level schedulers are a worthless joke - there's no way for one process to know that its threads are less important than threads in other processes

I always remembered them as being responsible for deciding which threads are to be ran in the current process - where you actually do know which threads are important.

[Brendan]

Hi,

Note that user-level schedulers are a worthless joke - there's no way for one process to know that its threads are less important than threads in other processes

I always remembered them as being responsible for deciding which threads are to be ran in the current process - where you actually do know which threads are important.

Where you only know how important threads within that one process are; and don't know how important threads in all processes are (unless there's an additional "something", that makes user level scheduling less efficient and even more pointless).

For example; imagine a process has a high priority thread and a low priority thread. The high priority thread blocks. Does its user-level thread scheduler run the low priority thread (the only other thread in the processes), or not?


Cheers,

Brendan

[mallard]

For example; imagine a process has a high priority thread and a low priority thread. The high priority thread blocks. Does its user-level thread scheduler run the low priority thread (the only other thread in the processes), or not?

In a user-level threading system, all threads are subject to the process' priority. Thus, the "high priority" thread is only "high priority" compared to other threads in the same process. The process' priority sets the relationship to threads from other processes. The same goes with "low priority". It's only "low priority" compared to other threads in the same process. Thus if there are no runnable higher priority threads in the same process, it runs.

Since such a system has no concept of "global" thread priorities, there is no such issue to worry about.

[Brendan]

Hi,

For example; imagine a process has a high priority thread and a low priority thread. The high priority thread blocks. Does its user-level thread scheduler run the low priority thread (the only other thread in the processes), or not?

In a user-level threading system, all threads are subject to the process' priority. Thus, the "high priority" thread is only "high priority" compared to other threads in the same process. The process' priority sets the relationship to threads from other processes. The same goes with "low priority". It's only "low priority" compared to other threads in the same process. Thus if there are no runnable higher priority threads in the same process, it runs.

Since such a system has no concept of "global" thread priorities, there is no such issue to worry about.

Except now you've got an additional "process scheduler", and processes continually diddling with their process priority and telling the process scheduler when the process' priority changes.

Why not improve efficiency and reduce the need for extra bloat in every process by making the process scheduler schedule threads instead?

It's a nice example of "additional "something", that makes user level scheduling less efficient and even more pointless".


Cheers,

Brendan

[mallard]

Except now you've got an additional "process scheduler", and processes continually diddling with their process priority and telling the process scheduler when the process' priority changes.

There's rarely a need to change a process' priority in any system. User-level scheduling doesn't have much of an effect on that. In fact, there's rarely a need to change a thread's priority either. It's usually clear what it should be when the thread is started.

In my (conventionally-threaded) system, I have, in theory, 4294967295 possible thread priorities. So far, I'm using 4 of them (a value for high-priority kernel threads servicing hardware devices, a value for normal kernel threads, a value for userspace threads and a value for the idle thread).

Why not improve efficiency and reduce the need for extra bloat in every process by making the process scheduler schedule threads instead?

As with just about everything in programming, there's a trade-off. You gain simplicity in the kernel since you have one "kernel thread" per process and probably improve the speed of (kernel) context switches (since there are less threads to consider). You also gain flexibility since userspace processes are free to decide their own scheduling algorithms without affecting anything else. It can also be faster, as no system call is needed to switch between threads in the same process.

You lose simplicity in userspace code and some efficiency. It might also make userspace processes harder to debug if the debugger doesn't understand the scheduler that the particular process is using. Especially if the debugger is external to the OS.

Note that you can have user-level threading even if the OS supports traditional multi-threading. Various programming languages/environments/libraries do so.

It's a nice example of "additional "something", that makes user level scheduling less efficient and even more pointless".

I know you have (IMHO overly) strong opinions on just about everything related to OS development, but really, most aspects of design are simply a matter of subjective opinion and personal preference. Nobody's forcing you to adopt a particular design. As long as the design is workable, why not just live and let live?