Study of Formal Specifications of the Object Memory:

Introduction:
These are questions, answers and remarks that came to my mind while
studying chapter 30 from the BlueBook.  I had access to two machine
readable copies, that Mario Wolzcko (marioAtwolczkoDotcom) and Alain
Fisher (mailinglistDotfischerAtbluewinDotch) kindly provided.

Mario put his files on
	http://www.wolczko.com/st80/
Thank you!

(End of Introduction)

Question: To allocate n words from free chunks, only chunks with size
= n or size >= n+headerSize are used. Why?

Answer: Allocating a chunk with n < size < n+headerSize would leave a
free chunk with size < headerSize, which would break the list of free
chunk which is linked by the Class field in the header.
(End of Answer)

Question: Are the links of free chunks valid object pointers?

Answer: Yes. A link is either a 16 bit word index into the Object table
or a NonPointer. And a pointer to an object which is not a small integer is
a 16 bit word index into the Object table. A NonPointer would be a
valid object pointer to a small integer.
(End of Answer)

Question: Do the free chunks in the list headed at LastFreeChunkList
always have a size >= BigSize?

Answer: No. If only part of a bigger chunk in the LastFreeChunkList is
allocated, the remaining chunk might have a size less than BigSize.
This happens in the routine
	attemptToAllocateChunkInCurrentSegment:

(End of Answer)

Question: In the routine abandonFreeChunksInSegment the variable
lowWaterMark is computed as the minimum of all locations of free chunks
in a segment. It is initalized to HeapSpaceStop. Is this the minimum
of the empty set? How would you define the minimum of an empty set?

Answer: The sum of the empty set is the neutral element with respect
to "+", which is zero.

The product of the elements of the empty set is the neutral element
with respect to "*", which is one.

The pattern of the above examples yields:
The minimum of the empty set is the neutral element with respect to
"min", which is the positive infinite number.

But any value that is not exceeded by any possible element of the set
whose minimum is computed will suffice. In this case, HeapSpaceStop or
HeapSpaceStop-headerSize are valid candidates to initialize
lowWaterMark to. But to indicate to the sender, the
compactCurrentSegment routine, that there are no free chunks at all,
the answer must be HeapSpaceStop and not HeapSpaceStop-headerSize.
(End of Answer)

Remark: In the description of the compaction algorithm (pp. 671-674) I
had to exchange "bottom" with "top", "above" with "below" etc. before I
could understand it. (End of Remark)

Question: In a segment, are the locations increasing from top to bottom
or decreasing?

Answer: The bottom of the segment is supposed to contain permanently
allocated objects. And at locations below the lowWaterMark there are
no free chunks, that is at low locations there are permanently allocated
objects. So the bottom of the segment is the one with lowest location, the
top of the segment with the highest location, i. e. HeapSpaceStop.
In other words, the locations of a segment are decreasing from top to bottom.
This differs from the convention used in other parts of the Blue Book.
(End of Answer)

Remark: In the description of the compaction algorithm (pp. 671-674) I
had to exchange "bottom" with "top", "above" with "below" etc. before I
could understand it. (End of Remark)

Question: Which loop test is simplified by traversing the fields of a
chunk in reverse order as mentioned in the description for the routine
	forAllOtherObjectsAccessibleFrom:suchThat:do
on page 680?

Answer: The loop test is
	(offset <- offset - 1) > 0,
which is simpler and faster than
	(offset <- offset + 1) <= (self lastPointerOf: current).
(End of Answer)

Question: What do the fields of a compiled method contain?

Answer: The layout of a compiled methods is defined in the section
"Objects Used by the Interpreter/CompiledMethods", p 576/577.
(End of Answer)

Question:
How does Smalltalk guarantee that compiled methods are the only objects
with a mixture of 16-bit and 8-bit fields.

Answer: An object without indexed instance variables is created by the
primitive methods Behavior|new, and Behavior|basicNew, both of which
invoke the primitiveNew routine (70), whereas an object with indexed
instance variables is created by the primitive methods Behaviour|new:
and Behavior|basicNew:, both of which invoke the primitiveNewWithArg
routine(71). Both primitive routines won't allocate fields with mixed width.

So you cannot create an object with mixed width fields by sending new,
new:, basicNew, or basicNew: messages to a class. Not even by sending
one of those messages to CompiledMethod. Instead, you need to send the
message newMethod:numberOfBytes header:headerWord to CompiledMethod,
which invokes the primitiveNewMethod routine (79).
(End of Answer)

Error: The routine primitiveNewMethod does
not check the class of the receiver being the CompiledMethod class. So the
primitiveNewMethod routine, if received by another metaclass, will
invalidate the assumption of the routine lastPointerOf: on page 686,
which might destroy the memory.

This error is not fixed by Mario or Alain.
(End of Error)

Error: The implementation of the isIntegerValue: routine is wrong.

To rectify, one first has to decide if the parameter is signed, as
defined in the section "Object Memory Interface" on page 573 or
unsigned, as the parameter name valueWord seems to imply. (Words are 16
bit unsigned integers)

  isIntegerValue: valueWord
	^valueWord < 16r8000 "assuming valueWord is unsigned."

  isIntegerValue: value
	^-16r4000 <= value and: [value < 16r4000] "assuming value is signed."

Mario discovered and fixed this error, assuming valueWord being signed
and using the ideom "cock up", which is new to me and unknown to my
copy of Webster's New World Dictionary, 2nd edition, but nevertheless I
like it!

isIntegerValue: valueWord
	"ERROR: G&R really cock this up"
	^valueWord >= -16384 and: [valueWord <= 16383]
(End of Error)

Remark: If the base of the number literals in the BlueBook version of
the isIntegerValue: routine would have been chosen judiciously, it
probably would turn out less broken.  (End of Remark)

Question: Which of the routines in the section "Interface to the
Bytecode Interpreter" survive being passed an object pointer to a small
integer?

Answer: Only the routines in the categories reference counting, class
pointer access and, of course, integer access may be passed an object
pointer to a small integer.  (End Of Answer)

Error: According to the Implementation Index the routines
fetchPointer:ofObject:, storePointer:ofObject:withValue:,
fetchWord:ofObject, storeWord:ofObject:withValue, fetchByte:ofObject:,
and storeByte:ofObject:withValue:  are not used. They should be
removed!

But wait: They are used by the interpreter as defined in the
section "Array and Stream Primitives" on page 626. These primitives do
not defend themselves against being received by objects without indexed
instance variables or, even worse, by small integers. This might be
exploited as a security hole or break the object memory structures.

In this respect the VM does not quite reach the stadia rod put up by
Unix, with its kernel data structures protected from evil minded or
stupid users -- even if they have the awsome powers of root.  (End Of
Error)

Question: Are there any more errors discovered by Mario?

Answer: The shell command

	$ for f in *; do grep ERROR $f/*; done

executed from the directory VMsrc/ObjectMemory reveals nine errors.
(End of Answer)

Errors discovered by Mario:

fetchByteLengthOf: objectPointer
    "ERROR in selector of next line"
    ^(self fetchWordLengthOf: objectPointer)*2 - (self oddBitOf: objectPointer)

fetchClassOf: objectPointer
    (self isIntegerObject: objectPointer)
        ifTrue: [^IntegerClass] "ERROR IntegerClass not defined"
        ifFalse: [^self classBitsOf: objectPointer]

initialInstanceOf: classPointer
    0 to: ObjectTableSize-2 by: 2 do:
        [ :pointer |
            "ERROR in next line, second part of test omitted"
            ((self freeBitOf: pointer) = 0
				and: [(self countBitOf: pointer) ~= 0 ])
                    ifTrue: [(self fetchClassOf: pointer) = classPointer
							ifTrue: [^pointer]]].
    ^NilPointer

Remark: Typo, read countBitsOf: not countBitOf:. This improvement would
not work if the object memory is run without a reference counting
collector. The RealObjectMemory as described by the Blue Book generally
is supposed to work with the marking collector allone.  (End of remark)

instanceAfter: objectPointer
    | classPointer |
    "ERROR: next line omitted by G&R"
    classPointer <- self fetchClassOf: objectPointer.
    objectPointer to: ObjectTableSize-2 by: 2 do:
        [ :pointer |
            (self freeBitOf: pointer) = 0
                ifTrue: [(self fetchClassOf: pointer) = classPointer
                        ifTrue: [^pointer]]].
    ^NilPointer

Remark: This routine would not return the next but the current object
pointer, if it is not a free entry. And why no test anymore for being
referenced? This one should be even better than Mario's:

instanceAfter: objectPointer
    | classPointer |
    classPointer <- self fetchClassOf: objectPointer.
    objectPointer + 2 to: ObjectTableSize-2 by: 2 do:
        [ :pointer |
            ((self freeBitOf: pointer) = 0
			    and: [(self countBitsOf: pointer) ~= 0 ])
					ifTrue: [(self fetchClassOf: pointer) = classPointer
							ifTrue: [^pointer]]].
    ^NilPointer

(End of Remark)

swapPointersOf: firstPointer and: secondPointer
    "ERROR in next line, firstPointer redefined"
    | firstSegment firstLocation "firstPointer" firstOdd |

The markAccessibleObjects and rectifyCountsAndDeallocateGarbage
routines refer to the undefined variable rootObjectPointers.

Remark: On page 682, two root objects are mentioned, namely the system
dictionary Smalltalk and the current process. (End of Remark)

The routine lastPointer refers to the undefined variable MethodClass,
which is supposed to contain the object pointer to the instance of
CompiledMethod class.

The routine cantBeIntegerPointer refers to Sensor notify, which is
undefined.

Remark: The "formal definition" of this routine needs some interpretation
on the programmer's part: In Unix, if the check failed, print a last word 
on stderr like: 'Sanity check failed. Exiting ...' and then call exit(1).
(End of Remark)
(End of Errors discovered by Mario)

Question: How does the ObjectMemory know the object pointer to instances of
Integer class and the CompiledMethod class.

Answer: Those object pointers are constant. For Smalltalk V2, they are
defined in the memo/page07.jpg. (End of Answer)

Question: How does the ObjectMemory know the root objects needed for the
marking collector, that is the oops of Smalltalk and the current process.

Answer: The object pointer of the active context is maintained in a VM
register, the object pointer of Smalltalk is constant and defined in
memo/page07.jpg.(End of Answer)

(End of Study of Formal Specifications of the Object Memory)

Date: 23.05.2006
Author: Wolfgang Helbig (helbigAtLehreDotBA-StuttgartDotDE)

Changes:
16.06.2006 Add answers drawn from the memo and given by Klaus.