This got lengthy. My apologies. The issue of mapping capabilities is an important one, and I very much want to see us come to some concensus on whether they are a good idea.
>In addition, the usual case is large contiguous mappings of dense
>objects. Tree structures don't do this well.
You're assuming we do it exactly like KeyKOS did - as a page-table-like address translation tree where each level decodes 'n' bits of address space. That's not what we're planning to do....
I wasn't clear about my objection.
As long as object mappings are not permitted to overlap (later mapping wins will ensure this), using a tree structure to find the mapping is a fine approach. My point was that one would like to have a structure that doesn't waste much space for areas of the address space that are unallocated, and one would like to take advantage of the fact that mappings within a single memory object are linear.
>Can you be a little more specific about how you intend to use
>composable memory objects and why the existing model in Mach is
>inadequate for what you need (other than the implementation)?
One of our domains of research is large, single- or few-address-space systems, where many different processes share an address space but still maintain separate protection domains, each "seeing" only certain subsets of that address space.
I've thought about SAS a bit, and I've concluded that SAS is poorly
understood. Let me deal with that in a moment.
Most of your examples of address space composition seem to exist only
to work around the problems inherent in what you call "mapping
capabilities." I'm about to try to convince you that mapping
capabilities are a bad idea, and that it would be better to get rid of
them.
mapping capability sent as part of a message.
All of the SAS systems I know about have intertwingled the issues of mappings and access rights. In these systems, not all processes can see all objects, and therefore they do *not* share the same address space. A better way to think of matters with no loss of generality is that SAS is a way of restricting object mappings to require all mappings of a given object to appear at the same virtual address. We can then talk about the implementation of the address space object. In a SAS it's probably a permission set on a globally shared address space, and we probably alter the "map this object" call, but that's an implementation detail.
... it's easiest if an arbitrary set of mappings can be represented by a single capability in a structured way: for example, one capability representing the text, data, and bss mappings for a particular program...
I think that this can be done without special OR objects. Instead, pass the equivalent of a Node containing memory object keys and data keys with recommended mapping addresses in pairs.
Mapping composition can be used to implement all kinds of neat
abstractions outside of the VM manager, such as copy-on-write.
This is a good point, but I think you're assuming a particular
solution when two are possible. One way to think about COW is that
writable pages from the writable object are mapped "on top" of the
non-writable pages from the backing object. If you think this
approach is desirable, my proposal is to handle it by mapping the
individual pages into the address space, overriding the previous
mappings. This appears to be your assumed implementation.
I suppose my view is that COW is not an attribute of the mapping; it's
an optimization for copying a memory object. As such, it's a memory
object artifact, not a mapping artifact. In this model, one
implements layered memory objects. The front object is writable, but
sparse, and the objects behind it are read only. On an object fault,
you copy pages into the front object, thus implementing COW.
The copying can be done by either the kernel or by a user-level object fault handler. For performance, the read-through logic probably wants to be handled in the kernel.
This approach also has the advantage of unifying COW between memory mapped objects and file-like objects (see my parenthetical on item (3) above).
By seperating memory objects from address spaces, I was trying to build a clean seperation between "memory object page not present but should be" type faults and "invalid mapping" type faults. The notion of a "memory object page not present" fault is only clean if there is a single, unambiguous manager who is responsible for fixing things. If two managers in a composed object tree, one enclosing the other, are both trying to implement coherency protocols things get dicy very quickly. This is my principle reason for resisting composable memory objects.
My proposed COW implementation does essentially what I was trying to avoid, and retains the clarity of responsibility only because the implementation is so restricted. The proposed mechanism is useful for COW and demand zero, and a couple of other special cases that are probably performance critical. Conceptually, however, I take the view that the backing object *has been copied* and that all faults should be resolved by the frontmost object.
Actually, the COW illusion isn't perfect; the memory object manager for the backing object is free to change the data out from under the front object.
I suppose that my real objection to this lies in the implementation. I am trying to approach the design from the assumption that the system runs without paging, and to resist adding structures in the kernel that exist solely to support backing store. In my current conceptualization, a given page can belong to at most one memory object at a time. So long as paging is kept out of the picture, I therefore don't need a page validity map in my current conceptualization of things. Under these conditions I can also guarantee the COW illusion. If swap space is kernel managed, I still don't need a page validity map.
Once I give in to the need for such a map, I think that the arguments against composition largely evaporate, and I'll have to rethink the seperation between address spaces and memory objects.
Sorry that this got so long...
Jonathan