Smalltalk › Squeak › Squeak VM

A question from VM-beginners list

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

2 messages Options

Mateusz Grotek

A question from VM-beginners list

I asked the following in the VM-beginners list, but got no responses. So
I'm trying here. Thanks!

Dear VM specialists,

I have the following question concerning the proposed (is it already
implemented?) become implementation:
http://www.mirandabanda.org/cogblog/2013/09/13/lazy-become-and-a-partial-read-barrier/

How does this implementation prevent forming long chains of redirections?

Let's say I have a variable V1 pointing to an object O1. (V1 -> O1).
I have another variable V2 pointing to an object O2. (V2 -> O2).
After that I do: V1 becomeForward: V2.
Now O1 points to O2, so I have V1 -> O1 -> O2
Now I assign to V2 an object O3: (V2 -> O3)
And again do:
V1 becomeForward: V2.

So I have: V1 -> O1 -> O2 -> O3

I do it a couple of times. Now I have a long chain of redirections:
V1 -> O1 -> O2 -> O3 -> O4 -> O5 -> .... -> ON

If I save my image it gets saved inside it. So the longer I use my image
the longer the chain is. In the end it's longer than my memory and the
image crashes.

What am I missing?

Yours sincerely,
Mateusz Grotek

Eliot Miranda-2

Re: A question from VM-beginners list

Hi Mateusz,

On Wed, Mar 26, 2014 at 11:19 AM, Mateusz Grotek <[hidden email]> wrote:

I asked the following in the VM-beginners list, but got no responses. So
I'm trying here. Thanks!

Dear VM specialists,

I have the following question concerning the proposed (is it already
implemented?) become implementation:
http://www.mirandabanda.org/cogblog/2013/09/13/lazy-become-and-a-partial-read-barrier/

How does this implementation prevent forming long chains of redirections?

Let's say I have a variable V1 pointing to an object O1. (V1 -> O1).
I have another variable V2 pointing to an object O2. (V2 -> O2).
After that I do: V1 becomeForward: V2.
Now O1 points to O2, so I have V1 -> O1 -> O2
Now I assign to V2 an object O3: (V2 -> O3)
And again do:
V1 becomeForward: V2.

So I have: V1 -> O1 -> O2 -> O3

I do it a couple of times. Now I have a long chain of redirections:
V1 -> O1 -> O2 -> O3 -> O4 -> O5 -> .... -> ON

If I save my image it gets saved inside it. So the longer I use my image
the longer the chain is. In the end it's longer than my memory and the
image crashes.

What am I missing?

That's a great question! There are several points at which forwarders get followed and the references to the forwarders are replaced by the target of the chain of forwarders.

Forwarders get followed during garbage collection. That means after an object has been scanned by either the scavenger or the mark-sweep garbage collector, if it referred to forwarders before the scan it no longer does after the scan. Further, when the VM does a snapshot it also does a full scan-mark GC, so there are no forwarders in a snapshot.

Forwarders get followed on message send and primitive evaluation. If the receiver of a send is a forwarder then the VM follows forwarders in the arguments and temporaries of the current activation. If a primitive fails and the primitive has a non-negative "primitive accessor depth" then the VM traverses the transitive closure of the objects comprising the primitive's receiver and arguments to that depth, following and eliminating forwarders. If it finds a forwarder it retries the primitive. See primitives-and-the-partial-read-barrier.

Since in Smalltalk inst var access is direct, not by message send, the VM also scans the receivers of the frames in the stack zone after any become that forwards a pointer object, since that object could have an inst var fetched from it. This avoids a read barrier on inst var fetch. Alas there /is/ a read barrier on global variable access, since a global variable (an Association, ClassBinding, etc) could be becommed, and eliminating the read barrier would involve scanning all methods in the stack zone, which would be expensive. But the read barrier is cheap because the contents of the global variable are being accessed anyway (either reading or writing the value of the association). So the additional check on the class index of the global is cheap; it won't create any additional cache misses, and on current machines the test itself is very fast; it's the reads that cost.

Further, forwarders only get created during become, or pinning, and become and pinning are relatively rare operations.

So in practice deep chains of forwarders don't get created, and get eliminated during normal processing.

Yours sincerely,
Mateusz Grotek

Thanks, Mateusz. Would you be willing to ask your question again on my blog and allow me to post the above reply to the blog? That's a great question and it would be better on the blog than in some mail archive.
--
best,

Eliot