On Mon, 2003-12-08 at 09:30, Espen Skoglund wrote:

[Jonathan S Shapiro]

...

A maps some region to B B completes the receive operation, and therefore now has a copy of the mapping B is immediately preempted, before it can do any user-level book keeping about the mapping ... other stuff runs ... kernel runs out of mapping cache space, chooses to evict the mapping just received by B ... other stuff runs ... B attempts to reference the region that it believes should be mapped, and page faults.

...

Can someone explain the process by which B is able to get the mapping reconstructed?

A really quick answer:

B's pager, Pb, receives the page fault Pb requests the mapping from A

Note that Pb and A could here be the same thread...

This makes sense to me, but it also seems to me that if A is a process implementing the file server, and B has memory mapped a file from A, then the current design requires Pb to act as an intermediary -- primarily for the purpose of normalizing file offsets and doing a little bit of protocol translation. Further, it seems to me that there is an interesting problem of deceiting here, since the file server may not know that Pb and B are equivalent for access control purposes. Am I missing something that simplifies this scenario?

A longer answer would require a better understanding of our concept of "data spaces", "data space managers", and "region maps" [1]. Here's a rather shortish explanation of this scheme:

Data space: An unstructured data container, e.g., a file, anonymous memory, pinned memory, etc.

Data space manager: A server that manages accesses to a particular data space. The data space manager will typically have parts (or the whole) of the data space mapped into its own address space. It will map these parts off to clients.

Region map: A region map is a part of the client's address space that contains parts (or the whole) of a data space. Note that the region map need not be fully populated. If the client accesses a part of the region which is not mapped, a page fault will be generated.

Region mapper: The region mapper serves as the page fault handler for the threads within the client. The region mapper keeps track of all region maps attached to the address space. When the region mapper catches page faults it translated these page faults into requests that are forwarded to the respective data space manager.

Okay. This is roughly the model that I was reconstructing from first principles. I will try to use these terms from here on to avoid confusion. Based on your description, I am now reasonably convinced that the L4 operations are individually faster, but that the collective end to end protocol needed to resolve page faults when data spaces are involved may be significantly more complicated in L4 than it is in EROS. I suspect that the aggregate end to end costs in L4 are likely to be *slower* than EROS, but at best they are going to be very similar.

For B to access parts of the data space, the following steps would typically be taken (Rm = region mapper, Dm = data space manager):

1. Rm: Create region (R) 2. Rm: Request data space manager (Dm) to attach a data space (D) to R. 3. B: Touch some memory in R. Nothing is mapped yet and a page fault is therefore raised. 4. Rm: Receive page fault and use virtual address to identify region. 5. Rm: Request Dm to map parts of the data space to R. 6. Dm: Map parts of D to R.

An obvious optimization here is for Rm to request parts of the region map to be pre-populated before step 3.

A better optimization might be to provide sufficient information to the kernel so that it can more directly localize the correct fault handler. Or perhaps the L4 design embeds a philosophical argument that resolving these things at user level is (a) feasible and (b) likely as efficient than any kernel implementation, and therefore should not be done in the kernel? If so, I understand the philosophical point, and I am not sure that I agree. In my mind, the answer depends on what gets the job done best on an end to end basis. Please note that I'm not advocating placing policy in the kernel here. I'm wondering if there might be a better *mechanism* by which to express the user-desired policy.

[Hmm... my "short" answer turned out to be a bit longer than expected.]

Perhaps so, but it was VERY helpful! shap

On Mon, 2003-12-08 at 11:39, Hermann Härtig wrote:

Jonathan S. Shapiro wrote: That is a result of using thread ids for identification of senders which I consider a bad idea. If we need indeed (which I tend to believe) sender identification, the id space should be designed such that ids can be managed in user space and enforced by the kernel, i.e. Pb and the file server should be enabled to act under the same sender id.

We need to talk further about whether sender ID's are useful, but let me answer on the assumption that they are necessary. If sender ID's are used, then any change to a sender ID must be a privileged operation. It can be managed in user mode, but the software that does the management must be universally trusted. shap

[Jonathan S Shapiro]

Based on your description, I am now reasonably convinced that the L4 operations are individually faster, but that the collective end to end protocol needed to resolve page faults when data spaces are involved may be significantly more complicated in L4 than it is in EROS. I suspect that the aggregate end to end costs in L4 are likely to be *slower* than EROS, but at best they are going to be very similar.

Let's try to summarize what needs to be done for resolving a page fault using the data space model. 1. Page fault is raised, execution traps into the kernel. 2. Kernel translates the page fault into a page fault IPC. 3. The kernel switches to the pager---the region mapper. The region mapper resides in the same address space, so no address space switch needed. 4. The region mapper translates the page fault into a region map access. 5. The region mapper sends a request to the corresponding data space manager. Note that the request is sent "deceiving" or "propegating", meaning that the address space manager can reply direcly to the faulting thread. 6. The data space manager checks if the request is valid and translates the request to a map operation (this translation can be implemented very efficiently). 7. The data space manager replies with a mapping to the faulting thread. 8. The faulting thread resumes execution. As you point out below, it would be possible to associate a separate pager with different regions of virtual memory, but for reasons I argue below, this reduces flexibility. Anyhow, by associating a pager with separate memory regions we can only avoid one (intra address space) IPC operation (step 3). I'm not convinced that this matters much in practice since page faults are generally treated by the hardware as exceptions and incurs a substantial overhead in the first place (pipeline flushing, various synchronization when updating page tables, change of cache working sets, etc.). The performance numbers of the "data spaces" paper I cited in the last mail substantiate these claims.

Or perhaps the L4 design embeds a philosophical argument that resolving these things at user level is (a) feasible and (b) likely as efficient than any kernel implementation, and therefore should not be done in the kernel? If so, I understand the philosophical point, and I am not sure that I agree. In my mind, the answer depends on what gets the job done best on an end to end basis.

Yes, this philosophical argument does apply to the design decisions of L4.

Please note that I'm not advocating placing policy in the kernel here. I'm wondering if there might be a better *mechanism* by which to express the user-desired policy.

We've found that the only mechanism that allows us to express the user-desired policy is to perform all these policy decisions on user-level. For instance, the region mapper might suddenly choose to delay all write accesses to a particular region map, e.g., to capture a consistent snapshot of the region. It can do this by revoking all write accesses to the region, and if anyone tries to perform a write operation it can delay the write operation until the snapshot has been taken. On a more general level the argument seems to stem down to whether the kernel transparently handles exceptions or whether exceptions are exposed to the application and handled in an application specific way. Clearly, the L4 desgin favours the second approach. I realize that this approach may be unsatisfactory in certain situations, e.g., if one for some reason needs to make the application unaware of external communication. This is one of the gripes I have with the current versions of L4. One solution to make exceptions transparent to applicaitons, while still allowing policies to be defined on user-level could be to disallow an application to change its pager/exception handler, thereby making sure that the exception IPCs can not be seen by the application. Such a scheme would not really work with the current L4 specification because an application is always allowed to change its pager/exception handler. Even if we could make this restriction about non-changeable pagers/exception handlers, the application could still be able to intercept the exception IPCs by timely probing the state of other threads in the address space and aborting ongoing exception IPC operations. eSk

Stefan Götz wrote:

5. RM sends non-propagating request and waits for reply 6. DSM checks validity and translates request 7. DSM replies to RM

In general the DSM should not be able to alter regions it is not managing, i.e. at least the receive window must be shrinked to the region, the fault occured in. On x86-Pistachio the hack of modifying BR0 in the UTCB of the faulting thread might work. On architectures that place BR0 in Registers this is not possible, so the steps 6 and 7 are required anyway.

8. RM replies to faulting thread 9. fautling thread resumes execution

With this protocol, the client does not have to trust the DSM. If the DSM does not reply (properly), the RM can fix up the faulting thread to e.g. execute something like a signal handler.

Marcus