Allocation and Deallocation of Space in Keykos
There is no garbage collection in Keykos technology and in particular none in the foundations.
I want to say why we chose not to incorporate such function in the foundations.
In broad outline we wanted an allocation scheme that was both subject to capability discipline and that placed incentives to manage storage in the hands of those in a position to do so—to avoid externalities, as the economist would say.
Durability is proposed to guard against flawed decisions to explicitly deallocate.
First I observe that the choice has not been much of a problem but this observation is of limited value considering that only a few decades of programming effort has been invested in the resulting environment.
No truly large programming efforts have tested the need for garbage collection.
Garbage collection in a persistent system has a different flavor from that of most programming languages where the space to be recycled is not likely to persist beyond a few days.
(Smalltalk keeps garbage collected spaces indefinitely.
I don’t know how leaks are found in Smalltalk.)
GC in Keykos would presumably bear on the month-to-month and year-to-year space allocation issues.
This bears on the GC decision, but it is not clear in which direction.
There are three allocation schemes to reclaim unneeded storage that we were aware of:
- Explicit allocation and matched freeing
- Garbage collection as in early Lisp systems
- Allocation within areas, as in PL/I’s AREA construct.
PL/I had a data structure called an AREA in which storage could be allocated.
You could allocate an AREA of a size of your choosing, and then allocate other space within such an AREA.
AREAs were composed of contiguous virtual addresses.
An AREA could be deallocated at once and all contained objects would thereby be gone.
The AREA mirrored an underlying OS construct called the sub-pool.
Often, perhaps usually, the OS would set storage protection so as to trap references to deallocated sub-pools.
In Keykos we had already determined that pointers to deallocated objects would be safe in the sense that use of such a pointer (== capability == key) would have well determined semantics consistent with protection.
It was not thereby necessary to avoid capabilities to departed objects for safety of the whole system.
The space bank is an object that is invoked to acquire “new” units of storage, which are pages and nodes.
As Keykos is predicated on a single level store, the bank serves to allocate both RAM and disk.
Storage is freed by either invoking the bank passing a capability to the storage unit, or by invoking the bank with an order to free all of the storage that it ever created.
There is an order on a bank to create a sub-bank.
If S is a sub-bank of X then storage units from S are counted as also from X.
Invoking X to free its yields also frees those of S as well as S itself.
This provides hierarchical authority to allocate space.
When a “user”, typically a programmer or application owner, is introduced to the system he is allocated his own space bank.
He can allow his friends in as well by granting them banks subservient to his own.
Applications with persistent state are likely to keep that state under their own bank and the authority to delete that state is conveyed by the capability to its bank.
The space bank is thus an extension of the sub-pool idea.
The primary reason that we chose the sub-pool idea was accountability.
We charged for space and several principles seemed to be required that only the sub-pool pattern provided:
- He who pays for the storage has ultimate control over its persistence.
- It shall be possible, at least with preplanning, to learn who is consuming the storage.
- Capability discipline must be respected, indeed that the allocation mechanisms be implemented within that discipline.
I do not know how to allocate storage in light of the above principles except thru something like the space bank.
In particular space leakage products that I have seen for Java do not respect integrity of object boundaries.
They require infinite privilege.
The schemes I have described here do not assume that someone can violate encapsulation to track storage, any more than a power company has the right to enter your house to see which appliances are consuming the power.
Usage patterns for the space bank
Virtually all invocations whose purpose is to create something new require a space bank capability as a parameter.
During the creation of a complex object, creation code will pass the bank it is using to the creators of sub-objects for their use.
If the outer object is accused of using excessive storage then it may be modified to create a few sub-banks to perform sub-allocations in order to find out where the space is going.
This pattern uses storage accountability to track down inefficient storage use.
Durability
None of this is much comfort to those who worry that data will disappear while it is still needed.
What keeps the over powered, yet under informed administrator from deleting material critical to an application?
Pointing out the problems of relying only an GC does not answer their needs.
The durability scheme was invented relatively late in Keykos development to address a problem that had hardly arisen.
In that sense it is an entirely theoretical solution but I think that something much like it will work.
The signals entering the protected fort described in that note include any signals capable of deleting the object.
This is a framework where conflicting goals can be properly traded off.
As an application is installed that depends on significantly expensive storage, that fact will come to light and considered before the application is made durable itself.
The storage cannot be deleted without invoking the authority to delete the object.
Incentives and Externalities
The AltaVista search “+externalit* economic* incentive*” turns up a large variety of ideas for mechanisms to adjust incentives of those who make choices that affect others.
The adjusted incentives are supposed to provide a mutual benefit.
In a capability system with conventional GC, my inattention to storage matters may cause your application to fail.
Conventional GC discipline may fail to provide me incentive to conserve storage and even fail to support “central authority” in determining that it is my fault.
Commercially available schemes to analyze the use of storage in Java applications do not respect the encapsulation rules of the language.
These schemes cannot be adapted to capability systems while conforming to capability discipline.
Keykos was designed in a world where programs with divergent interests ran in the same system, while allowing mutually acceptable interactions.
Charging for storage is one way to align incentives.
All of the ways that I know to align incentives require accountability of storage use.
Durability mechanisms are perhaps cumbersome but they do address the availability of applications that, perhaps contrary to contract, refuse to operate after some date or event.
Such mechanisms are more complete if less convenient.
Most Keykos code fell into one of these easy patterns for allocation and deallocation:
For complex static structures, a block of generation code would be accompanied by a block of deallocation code which executes is reverse order of allocation,
including loops that ran backwards.
Upon failure to acquire space, there would always be a natural place to goto to reverse what had been built.
Often dynamic storage allocation could be fit into this plan as well.
Many structures, such as trees of nodes can be easily deallocated recursively.
Many ‘throwaway’ programs would merely create a bank and when done invoke the bank to recall all of its yield.