l4-hackers December 2003

l4-hackers@os.inf.tu-dresden.de

17 participants
20 discussions

RE: Naive question about grant/map
by Volkmar Uhlig 11 Dec '03

11 Dec '03

> -----Original Message----- > From: Kevin Elphinstone > Sent: Wednesday, December 10, 2003 8:57 PM > To: 'Jonathan S. Shapiro' > Cc: 'L4 Hackers List' > Subject: RE: Naive question about grant/map > > Just a small, but important point relating to the statement below. > > The L4 mapping database is NOT strictly a cache, but it can be used to > implement cache-like behaviour which is usually what is done in most > systems. Kernel mappings are a dynamic subset of things defined at > user-level. However, in kernel mapping can be used to > indirectly define an address space or region of an address space > (if, for example, you what to avoid faults). I.e. it can equal > or be a superset of what is defined at user-level. However, doing > so requires carefully crafted and coordinated pager behaviour/protocol. > > You can term it a (large) cache with mechanisms to control > its population, but it is not exactly a "cache" in the terms usual > sense of the word. This also depends on your point of view. Your statement that the kernel mapping can be a superset of user-level pagers is wrong. The user-level pagers have full knowledge about the replacement policy (since it is implemented in user land via map and unmap) and therefore can rely on the fact that the kernel won't replace entries in the cache. If it would be a superset then the kernel would have to enter values itself. - Volkmar

2 1

Naive question about grant/map
by Jonathan S. Shapiro 11 Dec '03

11 Dec '03

I have a note about mappings and address spaces pending, but before I send it I want to ask a naive question about the map operations: Consider a sequence of operations in which A maps to B B maps same stuff to C. Is there some variant of the 'map' operation in which B does NOT retain the ability to revoke C's mapping? That is, in which the resulting mapping dependency hierarchy is A / \ B C instead of A | B | C That is, is there a way for a sender to give a receiver rights on data that are co-equal in all respects with those of the sender? If not, is it important? If such a "coequal map" operation existed, how often would it be used in contrast to the current map operation? shap -- Jonathan S. Shapiro <shap(a)eros-os.org>

8 13

systemclock
by Sebastian Bogan 10 Dec '03

10 Dec '03

Hey, I am using the latest L4Ka::Hazelnut. I was wondering how a usertask can access the systemclock. In X.2 they talk about a systemcall `systemclock' but it seems, that this call was not yet implemented.? Thanks for advise. Ciao Sebastian Bogan

2 1

The code size of Fiasco µ-kernel
by jwy002 08 Dec '03

08 Dec '03

Hi, Can anyone give me a rough figure about how much memory space is needed by L4 u-kernel? Thanks. Joseph

3 3

Memory mapping
by Jonathan S. Shapiro 08 Dec '03

08 Dec '03

One of the essential differences between EROS and L4 is their handling of mapping state. In light of Hermann's note: http://os.inf.tu-dresden.de/pipermail/l4-hackers/2003/001559.html I am beginning to believe that the difference in mapping architectures may be the only really basic difference. It affects how we think about caching of mapping state, how we think about memory management algorithms, and so forth. Before I start, I want to say "thank you" to Volkmar. In trying to understand the L4 model, I have gone through a progression of confusions. It is possible that I am still confused. The key clarification was Volkmar's comment that the current L4 map operation proceeds entirely on the native page tables in the x86 implementations. I currently believe that *neither* the L4 mapping system nor the EROS mapping system is adequate today. I have been thinking lately about how to find a happy middle ground, and I provisionally believe that I may have one. That will be the subject of my next note. So: The key differences between the L4 mapping state and the EROS-NG (next generation) mapping state may be described as follows: + In L4, the only important state is the state recorded in the mapping database. This state is a cache, and applications are required to be able to reconstruct their own mapping state on demand. Mappings are not named by any sort of name (local or global) that can be directly referenced by any application. Because they cannot be named, mappings are not first class objects -- there is no contract with any application about the kernel's logical mapping structure. Page fault handling is done at the granularity of a 'task'. + In EROS-NG, address spaces are expressed as guarded page tables (GPTs), and every GPT is named by a capability. GPTs are therefore first-class objects exported by the kernel. The kernel can "page" these objects in the same way that it can "page" data pages, but it is not free to discard them. Page fault handlers can be injected at any arbitrary GPT. There seem to be advantages and disadvantages to each design. 1. Cost of mapping: I believe the the correct way to measure the cost of a map operation is to include all of the costs necessary to actually get a valid PTE into the recipient address space. * L4 Map The dominant cost in the L4 map operation is the cost to build the necessary mapping DB entries in the kernel. PTEs are copied aggressively, so there are usually no further hardware page faults needed to load them when the recipient starts running. In addition to the kernel-level map operation, the recipient task must record the incoming mapping in some per-task database. This database essentially duplicates the state in the kernel, though my guess is that it can be accomplished via a region-based recording scheme in the usual cases (that is: I record that X bytes from File Y got mapped starting at address A, and that faults in this region should be recovered by making a request to thread-id T). It is not clear to me what the practical overhead of this additional tracking is. Unless something has changed in a way that I have failed to understand, L4 does not provide a means to share page tables across more than one task. * EROS-NG map (capability transfer) The dominant cost in the EROS-NG design is the cost of the page faults. PTEs are NOT transferred eagerly, and the recipient takes a fast path per-page fault to validate each mapping when it is first encountered. These mapping validation faults can be "batched" for performance, but the current EROS implementation does not do so, and there does not appear to be any compelling performance-motivated reason to *want* to do so. The kernel uses a variety of tricks to make these traversals more efficient on architectures that implement hierarchical page tables. In the current EROS system, there are several steps required on the part of both sender and receiver to extract the relevant capability for transmission and to insert it into the desired location in the recipient space. In EROS-NG these steps are accomplished in the kernel, though they may result in what I might call "GPT faults" -- I'll try to explain this in my next mail. For some architectures, it is an important point that the EROS strategy guarantees page table sharing whenever doing so is (a) possible and (b) correct -- even across threads that do not share an address space. In our experience, page table sharing is very important to overall system performance. This sort of sharing is especially important to provide efficient support for shared libraries. 2. Cost of Unmap: The costs of unmap in the two systems seem comparable if the implementation is done with care. Because EROS-NG provides explicit names for the GPTs, and because it is possible to build "alias" GPTs, the EROS unmap operation can be used more selectively than the L4 unmap operation. This may not be a critical issue. 3. Encapsulation If I understand matters correctly, an L4 page fault is always reported first to the client's per-task page fault handler. In EROS, page fault handlers can be associated with arbitrary regions of the address space, and faults delivered to these handlers are usually invisible to the client (except for latency). Mach, just for comparison, does per-region page fault handlers. They are not structured like those of EROS, but like EROS they allow specification of address fault handlers on a region by region basis. When I first encountered KeyKOS, I didn't see why this distinction mattered. Here is an example that may help clarify whether or not this distinction is important: Imagine that client C maps a file F into the address space of C. Portions of the file data may not be in memory, and may need to be demand paged. Note that C cannot have enough information to accomplish this demand paging action. At *best*, C has enough information to ask the file server to provide the missing mapping. Because C is not in a position to actually solve the problem, I would argue that the kernel has misdirected the fault. The L4 design appears to require more IPC steps than the corresponding EROS design, because it requires an extra IPC operation. >From an abstraction perspective, there is a second objection: the demand paging of this object is really none of C's business, but C is given full knowledge of all of the faults. This is an encapsulation failure. In fact, the design places a burden of mapping work on C that appears to me to be unnecessary. The one argument I see that might make this design desirable is the argument that the L4 kernel is simplified as a result. While I certainly believe that this is true, I think that the absence of first-class memory objects is a potential weakness. 4. Space The EROS-NG design is more space intensive in the kernel, because the kernel must maintain two representations of the mapping structure and a correlation structure: 1. The GPTs 2. The page tables 3. The depend table (for dependency tracking) The hardware page tables and the depend tables can be discarded at any time, and the GPTs are pageable. I do not believe that requiring more kernel space is inherently bad -- the issue is the amount of total pageable space at user and kernel levels combined. We have no evidence from the EROS work that total kernel virtual addressable space is at risk from this particular increase. The EROS kernel translation strategy is more complex than the corresponding L4 strategy. I do not believe that this is necessarily bad. More precisely, I believe that *all* of the complexities of mapping need to be examined together; not just the complexities that are incurred in the kernel. It is reasonable and desirable to push function out of the kernel when the cost of doing so is not excessive. Random Comments: It appears to me that there are peculiar boundary conditions implicit in the L4 design: if the very last page of a process is paged out, I am not sure how its pager thread runs, because I do not understand what memory that pager thread references in order to initiate instructions or store temporary data. I suspect that the solution is that the pager thread in turn specifies a pager thread (which I will call the meta-pager), and the meta-pager arranges to page enough state back in that the pager thread can make progress. Probably this all seems perfectly obvious to people who are familiar with L4. I find it confusing that every process must have two threads or must delegate mapping management to a third-party task. shap

2 1

Question about map operation
by Jonathan S. Shapiro 06 Dec '03

06 Dec '03

Believe it or not, I'm converging, but I'm trying to do it respectfully, which means asking an unreasonable number of stupid questions at high speed. :-) Now that I understand the shape of GPTs, I would like to understand the *mechanism* of the map operation. In particular, I would like to understand how the book-keeping mechanism works. It may be that this has been written up, and that I just haven't found it -- appearances notwithstanding, you guys collectively write faster than I do alone :-) Bootstrap conditions: 1. When a new, virgin, never-before-used task is created, can it have a completely empty address space, or is an initial flexpage required as an argument to the task-create operation? I'm trying to learn whether a null address space pointer is ever a conceptually valid thing for a task to have. Map operation: 2. Suppose a sender maps a single page to a recipient task, and the corresponding recipient address was previously undefined. What data structures get constructed in the recipient's GPT? I am *guessing* that the answer is: the recipient GPT tree is expanded by inserting GPT nodes until a slot can be contrived into which *something* can be placed that reflects the existence of the new mapping. I would like to know what the *something* is. In particular, is it a GPT whose type is 'alias'? 3. In order to support the unmap operation, some book-keeping data structure is needed in which all of the derived mappings can be discovered. Can someone describe for the x86 what book-keeping structures are created at the time of the "map", and how they are used at the time of the "unmap"? I think this may be the MapDB that someone mentioned earlier. I've had a hard time getting a clear understanding of that. I ask about x86 only because it is the machine that is most current in my mind. Also, please note that I am *not* trying to ask how the hardware addressing structure gets built -- I can think of several ways to handle that. Thank you! shap

2 2

Question about L4 address spaces
by Jonathan S. Shapiro 05 Dec '03

05 Dec '03

Before sending out anything on the subject of address spaces, I've been going through everything I could find on how L4 handles them. I now (finally) understand guarded page tables, and it is *staggering* how similar these are to EROS nodes -- something that I had assumed must not be true because of the user-layer map/grant/unmap API. Regrettably, I was in a very bad state when I first read this work years ago, and I simply didn't understand it at the time. For those unfamiliar with EROS, the way to think about EROS nodes is that they are guarded page tables whose size is fixed at 32 entries, and whose guard value is defined as: 0000...000xxxxxxxx where the number of x's is determined by the size of the subtree described. If the maximum number of bytes in the described subtree is 2^k, then there will be log2(2^k) == k don't care bits in the guard value. EROS chose to keep all nodes (GPTs) the same size, though Norm Hardy and recently discussed changing this. The main reason for keeping them the same size has to do with paging them -- it is convenient for all pageable objects to be of uniform size. What Norm and I recently noticed was that this was a restriction on representation size, not on the logical data structure size -- this last point will make more sense in a moment. Note that the EROS guard values are significantly less flexible than those of L4 -- a problem that I had been looking for a way to fix. The fact that the guard value is restricted to be all zero's means that the EROS address space tree favors compression of leftmost legs in the mapping tree. This is useful for code and data regions, but useless for stack regions and not as helpful as it could be for other sparsely allocated regions. I am not convinced that the EROS mapping structures have any good place to insert a generalized guard value; I need to think about this carefully. The EROS wrapper node serves double duty, taking on both the role of the "alias" GPT type and also something very similar to the "call-on-reference" GPT type. EROS wrappers provide "call-on-exception" rather than "call-on-reference". The call-on-exception node translates no bits, but contains a pointer to a contained GPT that *may* translate bits. This allows a partially populated space to behave as a normal space in those regions where it is defined, but fall back to a process where the underlying space is NOT defined. A similar effect can be achieved in L4 by expanding a call-on-reference node recursively as subregions are populated, but this is not exactly the same -- there is a hierarchy of exception types (invalid -> read-only -> read-write), and one would like to be able to invoke the exception handler for each. My provisional belief is that the call-on-exception design is strictly more general, but that the conceptual difference is quite minor. So with all of the above being said, the *interesting* difference between L4 address spaces and EROS address spaces may be reduced to naming and implementation details. Which brings me to yet another question (forthcoming). shap

1 0

Re: Naive question about grant/map
by Jonathan S. Shapiro 05 Dec '03

05 Dec '03

On Fri, 2003-12-05 at 09:52, Marcus Völp wrote: > Jonathan wrote: > >Note that "B can ask A to map to C" may not be possible -- B may not > >have any permission to perform an IPC to A. For example, A may be a > >fault handler that can be accessed by B only for page faults, but not > >directly via arbitrary IPCs -- the reason for such a restriction would > >be to prevent B from sending hostile messages to the fault handler. > > > > > > Faults are just messages, so to get the page from A as a result of a > page-fault, the fault has to be send to A, either directly by B or by > some intermediates such as a region mapper. So this line could as well > be used to demand the mapping to be established to C. The only way when > this does not work is when B awaits a mapping from anyone and A by > chance sends this mapping. This however is a very strange situation, > isn't it? > > By the way, we are now discussing offline the mailing list. Jean also > told me that your discussion with him went of the list at some point... My apologies -- the EROS lists munge reply-to, and I'm having to get used to saying "reply to all" again. I may have unintentionally tripped over an architecture difference between EROS and L4. In case it is revealing, let me explain it. In EROS, a memory region has a designated fault handler. This is not exactly the same as L4 tasks. Rather, imagine that each entry in the L4 GPT could optionally specify a fault handler (a thread) to handle that subspace. Because EROS has this arrangement, it is possible that an address space will hold a fault handler capability that the client application does NOT hold. In this case, the only fault messages that will arrive at the fault handler are those initiated by the kernel in response to load and store instructions. I do not understand adequately how memory fault handling is structured in L4, but if thread descriptors are ever virtualized I suspect that L4 will have the same possibility. shap

1 0

Second naive question about map operation
by Jonathan S. Shapiro 05 Dec '03

05 Dec '03

A second naive question. Imagine that thread A performs separate map operations to each of B and C (maps of the same thing). This results in a dependency relationship of the form: A / \ B C Given that these operations have happened, is there a way for A to revoke the mapping held by B without also revoking the mapping held by C? Does it matter? -- Jonathan S. Shapiro <shap(a)eros-os.org>

3 3

Unifying EROS and L4
by Jonathan S. Shapiro 04 Dec '03

04 Dec '03

In preparation for the upcoming gathering in Dresden, I want to start some discussion about opportunities for unifying the L4 and EROS kernels. We have made some recent decisions in the EROS project that create a MUCH higher likelihood of success in this discussion. Similarly, the L4 team has been making progress on things that are drawing the two systems closer. Since this is a public mailing list, and since many of the participants have strong and well-motivated architectural sensibilities, I feel compelled to say: I am *not* interested in establishing which system is "better." I think that both systems have some very strong qualities, and I think that they are closer in spirit than matters at first appear. I also think that each system has weaknesses, and I am interested to figure out whether there may exist a hybrid architecture that combines the advantages of both, and might allow us to bring the two communities together so that we can make more effective progress. Let me also say at the start that I have *not* been lurking on the l4-hackers list, and that some of the issues I raise may already be "solved", either in the current implementation or in the sense that there is a commonly understood forthcoming design. To facilitate properly threaded discussions, I'll be dividing my comments into different architectural categories and sending them out under distinct subject lines. Regards, shap -- Jonathan S. Shapiro <shap(a)eros-os.org>

1 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

l4-hackers December 2003