• Messages sorted by: [ date ][ thread ][ subject ][ author ] [ Next ]
• [ Previous ] In reply to: Charles Landau

This is a multi-part message in MIME format.

--------------F046D0A0C09905268EB1C8FF
Content-Type: text/plain; charset=us-ascii; x-mac-type="54455854"; x-mac-creator="4D4F5353"
Content-Transfer-Encoding: 7bit

Resending (apologies if you receive this twice):

The segment/address space serves multiple purposes. It provides a flat address space of data bytes that is much larger than a page, in fact as large as the native address space or more. Its specs are designed to permit extremely efficient access to the data by means of caching of the structure of the space in the native address mapping architecture (and, of course, caching of the contents of the space in the native data cache). It does this while providing sufficient generality to support subsetting and composition of spaces.

There is a need for a fundamental (i.e. kernel-implemented) object that provides a large flat space of keys in a similar way. Such an object would permit efficient and bounded walking of node trees by the kernel, which would be significantly faster than doing the same outside the kernel (as the supernode does). As with data spaces, caching of the structure is theoretically possible. On some architectures it may even be possible to use the address mapping structures (e.g. page tables) as part of such a cache. (It is an implementation issue whether doing so is desirable.)

A nice feature of data address spaces is that once one is built, it can be used by anyone with essentially no knowledge of either the page size or the node size. It simply appears as a range of consecutively-numbered bytes. To make key spaces equally simple, we would design it like the supernode
(http://www.cis.upenn.edu/~KeyKOS/agorics/KeyKos/Gnosis/75.html), as a
tree of nodes whose lowest-level keys are addressed by consecutive numbers. (I use the word "address" in the general sense of specifying, not in the sense of data addresses produced by the hardware.) If the node size is 32, then the low 5 bits of address are an index into the lowest-level node, etc. This makes the partitioning of the address different for keys than for bytes, for in EROS the page size is not a power of the node size. As a result, with this design there is probably little in common between data spaces and key spaces.

It has been proposed to support, subject to permission, fetching and storing of keys at any specified level in the tree, not just the lowest level. I'm disinclined to support this; it complicates the interface, exposes the internal structure of the flat space more widely than necessary, and obscures the analogy with data spaces.

Let's explore whether it makes sense to have more commonality between the two kinds of spaces, so that one space could contain both data and keys. This would have the advantage of parsimony of concepts as well as implementation. Consider an architecture in which the node size is 32 and the page size is 4096 (such as EROS/i486). In a 32-bit address, the high 20 bits address a page or a node; the next 10 bits could address two more levels of nodes. Consecutive keys would thus be numbered by addresses differing by 4, which I view as unnatural. This design does not expose the physical size of a key, but it does expose to every client a combination of the capacities of the page and the node.

(The EROS CapPage is another design to serve the same goal of mixing
data and key spaces, but it has some disadvantages compared to the above scheme. As has been previously pointed out, it exposes the physical size of a key (in combination with the page size), which is considered undesirable. And it requires a new type of object that is allocated on the disk. Its larger size eliminates nearly one level of tree walk, but when the walk is performed by the kernel, the additional level should not be that significant.)

I'm undecided on the merits of combining data and key spaces. Can anyone show a compelling reason to merge them, or not?

--------------F046D0A0C09905268EB1C8FF
Content-Type: message/rfc822
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Return-Path: <owner-eros-arch@eros-os.org> Received: from nmail.netgate.net (nmail.netgate.net [204.145.147.77])

	by pop.netgate.net (8.8.5/8.8.8-KB.072299) with ESMTP id JAA22227
	for <clandau@pop.netgate.net>; Mon, 7 Feb 2000 09:36:35 -0800 (PST)
Received: from vp3.netgate.net (vp3.netgate.net [204.145.147.63])
	by nmail.netgate.net (8.9.3/8.9.3) with ESMTP id HAA07510
	for <clandau@netgate.net>; Mon, 7 Feb 2000 07:17:55 -0800 (PST)
Received: from mail.eros-os.org (EROS.CIS.UPENN.EDU [158.130.6.119])
	by vp3.netgate.net (8.8.5/8.8.8-KB.072299) with ESMTP id HAA13243
	for <clandau@macslab.com>; Mon, 7 Feb 2000 07:13:57 -0800 (PST)
Received: (from majordomo@localhost)
	by mail.eros-os.org (8.8.5/8.8.5) id LAA03205
	for eros-arch-list; Mon, 7 Feb 2000 11:00:53 -0500

	by mail.eros-os.org (8.8.5/8.8.5) with ESMTP id LAA03202
	for <eros-arch@eros.cis.upenn.edu>; Mon, 7 Feb 2000 11:00:49 -0500

The segment/address space serves multiple purposes. It provides a flat address space of data bytes that is much larger than a page, in fact as large as the native address space or more. Its specs are designed to permit extremely efficient access to the data by means of caching of the structure of the space in the native address mapping architecture (and, of course, caching of the contents of the space in the native data cache). It does this while providing sufficient generality to support subsetting and composition of spaces.

There is a need for a fundamental (i.e. kernel-implemented) object that provides a large flat space of keys in a similar way. Such an object would permit efficient and bounded walking of node trees by the kernel, which would be significantly faster than doing the same outside the kernel (as the supernode does). As with data spaces, caching of the structure is theoretically possible. On some architectures it may even be possible to use the address mapping structures (e.g. page tables) as part of such a cache. (It is an implementation issue whether doing so is desirable.)

A nice feature of data address spaces is that once one is built, it can be used by anyone with essentially no knowledge of either the page size or the node size. It simply appears as a range of consecutively-numbered bytes. To make key spaces equally simple, we would design it like the supernode
(http://www.cis.upenn.edu/~KeyKOS/agorics/KeyKos/Gnosis/75.html), as a
tree of nodes whose lowest-level keys are addressed by consecutive numbers. (I use the word "address" in the general sense of specifying, not in the sense of data addresses produced by the hardware.) If the node size is 32, then the low 5 bits of address are an index into the lowest-level node, etc. This makes the partitioning of the address different for keys than for bytes, for in EROS the page size is not a power of the node size. As a result, with this design there is probably little in common between data spaces and key spaces.

It has been proposed to support, subject to permission, fetching and storing of keys at any specified level in the tree, not just the lowest level. I'm disinclined to support this; it complicates the interface, exposes the internal structure of the flat space more widely than necessary, and obscures the analogy with data spaces.

Let's explore whether it makes sense to have more commonality between the two kinds of spaces, so that one space could contain both data and keys. This would have the advantage of parsimony of concepts as well as implementation. Consider an architecture in which the node size is 32 and the page size is 4096 (such as EROS/i486). In a 32-bit address, the high 20 bits address a page or a node; the next 10 bits could address two more levels of nodes. Consecutive keys would thus be numbered by addresses differing by 4, which I view as unnatural. This design does not expose the physical size of a key, but it does expose to every client a combination of the capacities of the page and the node.

(The EROS CapPage is another design to serve the same goal of mixing
data and key spaces, but it has some disadvantages compared to the above scheme. As has been previously pointed out, it exposes the physical size of a key (in combination with the page size), which is considered undesirable. And it requires a new type of object that is allocated on the disk. Its larger size eliminates nearly one level of tree walk, but when the walk is performed by the kernel, the additional level should not be that significant.)

I'm undecided on the merits of combining data and key spaces. Can anyone show a compelling reason to merge them, or not?

--------------F046D0A0C09905268EB1C8FF--

[ Next ]
• [ Previous ] In reply to: Charles Landau