This paper opens ambitiously:
If [ALGOL:Utradition] languages are to be used for real:Utime applications, the implementation of their run:Utime system has to guarantee total security, without any loss of efficiency.
The main goal of this paper is to discuss this general security:Uwith:Uefficiency problem and, in particular, to present a new, secure approach to storage management with interesting efficiency properties in terms of computing cost.
After a few more paragraphs about the history of dynamic storage allocation methods in high level programming languages, the authors plunge into a description of their algorithm.
Suppose that you wanted to add dynamic storage allocation to an ALGOL:Utradition programming language. Suppose further that your storage allocation mechanism was to use explicit deallocation (i.e., no reference counting or garbage collection) and that you were extremely concerned about the dangling reference problem. Specifically, let’s assume that you wanted 100 percent reliable detection of an attempt to dereference a dangling pointer. Cioni and Kreczmar propose the following algorithm. Assume that for each dynamically allocated object there is a distinguished cell, which holds the address of the object and a :Iguard:Ucounter. (A guard:Ucounter is essentially an optimized time:Ustamp of the object’s creation time, as we will see.) All the distinguished cells reside in an area of storage that holds nothing else. In the programming language implementation, a pointer value is represented as a pair consisting of the address of one of these distinguished cells and a guard:Ucounter value. The implementation of NEW allocates a block of storage and returns the address of the block’s distinguished cell and a copy of the guard:Ucounter value. The implementation of FREE returns the object to the free storage pool and increments the guard:Ucounter values are compared on every attempted dereference of the pointer, a dangling pointer will be detected precisely when the values differ.
At this point, you undoubtedly have the same burning questions that I did after reading the first four sections of the paper. Happily, the next two sections, entitled Time and Space Cost and Parallelism, seemed to promise the answers. Unhappily, that promise was largely unfulfilled. Although the algorithm given in Section 2:U4 of the paper seems to be logically correct, there are flaws in the authors’ analysis of time and space costs and in their extension to the basic algorithm to tolerate a parallel programming environment. The former fails to face up to the magnitude of the real overheads, and the latter is simply incorrect. Let’s examine these in turn.
The space cost of the distinguished cell is probably acceptable, since many storage allocators introduce comparable overheads in the representation of heap objects. Having to carry around a guard:Ucounter value with each pointer seems more questionable, but the authors propose an encoding trick (suitable on some computers, like an IBM 360, but not others, like a PDP:U11) that packs the guard:Ucounter into a single word with the address of the distinguished cell. The same trick also helps to reduce the time cost of pointer validation to two or three machine instructions. But can an application really tolerate two or three additional instructions on every pointer dereference? This cost is at least as great as the cost of checking array subscripts, an overhead that many real:Utime applications find intolerable. Furthermore, if the application really cares about sotrage integrity, both pointer validation and array subscript checking are necessary. If we are to believe the authors’ assertion, quoted above, about the needs of real:Utime applications, I don’t see how we can can accept their algorithm as a solution that guarantees “total security without any loss of efficiency.” On the other hand, their approach seems perfectly acceptable for an application that is prepared to tolerate these costs in exchange for a strong guarantee of storage integrity.
A more serious failing lies in the authors’ plan for coping with parallelism. They extend the sequential algorithm by introducing semaphores and reader:Uwriter synchronization. Their solution correctly synchronizes the pointer validation function with NEW and FREE. Unfortunately, the actual use of the validated pointer is unsynchronized] In a parallel environment, FREE could be invoked just after pointer validation had succeeded but before the pointer was dereferenced. (Of course, a parallel program that actually did such a thing must have a serious synchronization error, but that’s exactly the sort of error that must be detected by a 100 percent reliable dangling pointer check.)
The authors have also neglected to provide an execution cost analysis of the version of the algorithm. No longer can the pointer validation be claimed to incur two or three instructions of overhead; I would estimate a minimum of 20 in the normal case. (I should add that this estimate is fairly optimistic, since it assumes that the normal cases of semaphore operations are 2:U3 instructions each.)
In summary, I cannot recommend the application of this approach for the sweeping purpose outlined in the paper’s introduction. However, for some purely sequential applications, the algorithm may be useful. For example, in a system that is used for rapid prototyping, the reliable detection of dangling pointers might well be worth the time and space overheads.
I feel compelled to add a comment on the lack of editorial quality in the publication of this paper. There are many errors in grammar and technical usage, several of which are significant enough to confuse the English:Uspeaking reader. In a couple of places, the prose actually says the opposite of what the authors evidently intended to communicate. There are also numerous typesetting errors in both the prose and the program fragments. Finally, a particularly central piece of code (the implementation of NEW) was split across an odd/even page pair, making it extremely inconvenient to read. Readers deserve better technical editing and proofreading.
