{"id":149,"date":"2013-09-13T11:51:53","date_gmt":"2013-09-13T19:51:53","guid":{"rendered":"http:\/\/www.mirandabanda.org\/cogblog\/?p=149"},"modified":"2013-09-13T12:29:59","modified_gmt":"2013-09-13T20:29:59","slug":"lazy-become-and-a-partial-read-barrier","status":"publish","type":"post","link":"http:\/\/www.mirandabanda.org\/cogblog\/2013\/09\/13\/lazy-become-and-a-partial-read-barrier\/","title":{"rendered":"Lazy Become and a Partial Read Barrier for Spur"},"content":{"rendered":"

Lazy Become and a Partial Read Barrier for Spur<\/a><\/h2>\n

One of the stated design goals for Spur is to support pinned objects via lazy become. \u00c2\u00a0This is one of the less well-thought-out<\/a> parts of the design. \u00c2\u00a0If I can make lazy become work it’ll be (as I hope to convince you in this article) a significant improvement over the current Squeak VM’s become implementation. \u00c2\u00a0But it must work, and to that end I thought I’d write a post describing my current design of the scheme, and allow y’all to criticise it, either shooting it down in flames, saving me the effort of tilting at windmills<\/a>, \u00c2\u00a0or helping fill in the blanks and offer \u00c2\u00a0improvements to help the scheme’s success. So let’s have a tilt at describing become:.<\/p>\n

How becoming<\/h3>\n

Become is Smalltalk-speak for an operation that changes all references to one object into references to another. \u00c2\u00a0There are two becomes. two-way, where two objects exchange identities, and one-way where references to a first object are replaced by references to a second object, and the first object becomes inaccessible, to be swept away by the garbage collector. \u00c2\u00a0This operation has traditionally been used to grow collections in Smalltalk, and to update live instances when a class definition changes, adding or removing variables. \u00c2\u00a0It can also be used to replace a movable copy of an object with a non-movable copy in some more suitable space, for example effectively morphing a movable object in new space with an immobile one in old space. \u00c2\u00a0Being able to pin objects down is invaluable in a Foreign Function Interface<\/a> (FFI) where one wants to pass storage to other components.<\/p>\n

The traditional implementation of become in the earliest Smalltalk-80 implementations<\/a> was based around a two-part object representation. \u00c2\u00a0The system had a table of object headers, all of the same size, and each header contained some information used by the garbage collector (contents contain pointers or not, etc)\u00c2\u00a0and<\/em> a pointer to the body of the object, the body containing the object’s class, its size, and its fields. \u00c2\u00a0The two-way become operation is simple with this representation; simply swap the pointers to the object bodies, plus whatever other header bits are relevant. \u00c2\u00a0Here there is effectively a read barrier on every class and instance variable access, through the pointer, so-called “object table indirection”. \u00c2\u00a0The VisualWorks<\/a> memory manager still uses this scheme, updated to work with a generational collector.<\/p>\n

Subsequently, Digitalk’s Smalltalk\/V used a flat object representation without object table indirection, and hence provided a one-way become which scanned through memory, replacing any reference to the first object with a reference to the second.<\/p>\n

The existing Squeak\/Cog garbage collector has a flat object representation, and supports both two-way and one-way bulk becomes. \u00c2\u00a0The input to the become primitive is two arrays of objects, and the become is pair-wise, performing either a two-way or a one-way become on each pair of objects in the two arrays. \u00c2\u00a0This is implemented above the VM’s compaction system which stops the world, allocates some forwarding blocks, replaces the headers of objects to move or become, with pointers to their forwarding blocks, which contain their final position after become or compaction, scans memory following object references through forwarding blocks updating pointers, and then, if compacting, moving objects, finally discarding the forwarding blocks.<\/p>\n

All approaches support grow, and instance migration (although IIRC Smalltalk\/V didn’t migrate instances on class redefinition), but while the cost of the object indirection version is O(1), with hidden costs in object table indirection, the flat implementation is O(n) in the size of the heap, and in the age of 64-bit machines that’s a problem.<\/p>\n

An alternative implementation, oft-used in Lisp systems, is to add a read barrier to all object access, and mark objects as forwarders. \u00c2\u00a0This can be used to implement lazy copying garbage collection<\/a> where objects are copied from one semi-space to another in parallel to the main program (the “mutator”). \u00c2\u00a0To become, or move an object one replaces the object’s header or first field with a forwarding\u00c2\u00a0<\/em>pointer to the desired target or copy in a new location, marking the “corpse” as forwarded. \u00c2\u00a0The program checks the forwarded flag on each access. \u00c2\u00a0If there is hardware support, as in a Lisp machine, this can work well. \u00c2\u00a0But without hardware support, and like the object table representation, it has costs, slowing down program execution due to the scattering of forwarding checks and forwarding pointer follows throughout program execution.<\/p>\n

The Spur Conjecture<\/h3>\n

Smalltalk provides strict object encapsulation; the only way to access the state of an object is to send it a message. \u00c2\u00a0OK, bald-faced lies<\/a> are very popular these days, but with Smalltalk there’s more than a grain of truth here. \u00c2\u00a0The only violations of this principle are though certain primitives. \u00c2\u00a0The add primitives, for example, be it on SmallIntegers (fixnums) or Large integers (bignums) access the state of both the receiver and the argument in computing the result. \u00c2\u00a0One might think that instVarAt: and instVarAt:put:, which can access the instance variables of any object from the outside, violate encapsulation, but one still has to send the message to the object one is accessing. \u00c2\u00a0Mirror primitives<\/a>, however, do violate encapsulation, allowing one to reach inside an object without sending a message to it, passing the object to be accessed as an argument to the mirror primitive. \u00c2\u00a0The up side is that mirrors provide security, they are capabilities that only certain parts of a system are trusted with; instVarAt: and instVarAt:put: declare open season on internals and are thankfully used with discretion in Smalltalk systems.<\/p>\n

Given strict encapsulation it seems to me that we can rely on message sending to follow forwarding pointers. \u00c2\u00a0(almost) Every message send in Smalltalk involves some form of check of the class of the receiver. \u00c2\u00a0In the abstract, a message is activated by fetching a receiver object’s class, and searching the method dictionaries in the class’s hierarchy until a matching method is found. \u00c2\u00a0In practice, the process is optimized using method lookup caches<\/a>. \u00c2\u00a0Every send involves fetching either the object’s class, or a unique class identifier (e.g. an index into a class table) from the object and comparing it against a possibly matching tag in a cache. \u00c2\u00a0If they match, the right method is in the cache. \u00c2\u00a0If they don’t match a full lookup is needed. \u00c2\u00a0By arranging that forwarding objects have their class tags changed, the message send cache probe becomes a forwarding object trap. \u00c2\u00a0Whenever a message is sent to a forwarding object the cache probe will fail and the failure path can follow the forwarding pointer.<\/p>\n

The scheme then implements pinning and become using forwarding pointers. \u00c2\u00a0The old space collector will not move pinned objects, and to avoid pinned objects filling up new space, an unpinned young object is pinned by allocating a pinned copy in old space and marking the young object as a forwarding object pointing to the copy. \u00c2\u00a0Two-way become is implemented by either swapping contents if the two objects have the same size, or allocating two copies, and forwarding the originals to the exchanged copies. \u00c2\u00a0One-way become is implemented by marking the first object as forwarded, pointing to the second object. \u00c2\u00a0This seems great in principle, but there are a number of pitfalls, not just the primitive argument one mentioned above.<\/p>\n

My Spur conjecture is that using a message send trap is an effective approach because the pitfalls are limited and manageable. \u00c2\u00a0So what are the pitfalls?<\/p>\n

 <\/p>\n

Falling With Style<\/h3>\n

 <\/p>\n

The first pitfall is that Smalltalk accesses two other objects far more than the receiver, which are the current method and the active context. \u00c2\u00a0Smalltalk-80’s execution model executes bytecodes and references literals stored in the current CompiledMethod object. \u00c2\u00a0In most good Smalltalk implementations, methods are compiled on-the-fly to machine code and the machine code is executed. \u00c2\u00a0In fact, Cog is a hybrid interpreter+JIT, interpreting essentially only at start-up. \u00c2\u00a0So the becoming of methods is really only an issue in \u00c2\u00a0the interpreter. \u00c2\u00a0Smalltalk-80’s execution model also\u00c2\u00a0provides access to the underlying activation record, a context, and in a fast Smalltalk implementation (and Cog’s not too shabby) contexts are essentially virtual, created on-demand only when the program asks to see them; the VM’s actual activation records are more-or-less conventional stack frames, and contexts are proxy objects for them. \u00c2\u00a0And while message sending is heavily optimized, when a method cache probe does fail the class hierarchy of the receiver is searched, and any object there-in could have been becomed.<\/p>\n

The more-or-less conventional stack frames are housed not on the machine stack but in a\u00c2\u00a0stack zone<\/em><\/a> of quite limited size, organized as a set of pages. \u00c2\u00a0The stack zone acts much like a young generation for contexts, storing the most recently active N stack frames. \u00c2\u00a0While the number of pages in the stack zone is a settable parameter, the zone’s size is typically less than 100 kb. \u00c2\u00a0So it is practicable and quick to scan the stack zone and follow forwarding pointers after a become operation. \u00c2\u00a0We can know that the receiver in a stack frame is never a forwarding pointer and hence not need a read barrier when reading its instance variables. \u00c2\u00a0We can know that the method in an interpreted frame\u00c2\u00a0is never a forwarding pointer and hence not need a read barrier when interpreting bytecodes or accessing literals. \u00c2\u00a0However, a literal itself may be a forwarded object, and so, for example, we may have to follow the message selector on a message probe miss. \u00c2\u00a0We must scan the first-level method lookup cache and remove forwarded entries there-in; again the\u00c2\u00a0first-level method lookup cache \u00c2\u00a0is quite small, perhaps 4k entries.<\/p>\n

To avoid checking class fetch (where the class table is indexed by an instance’s class index to locate its class object for method lookup) we can scan the class table after a become operation. \u00c2\u00a0There can be up to 4M classes in Spur, but this is still a tiny fraction of a large heap – ignoring page density, faulting in 4M pages could be expensive ;-). \u00c2\u00a0But in the common case the class table contains a few thousand classes, most of them in the first few pages of the table, and that’s a tiny amount of memory to scan. \u00c2\u00a0There is a wrinkle; the class table contains only classes that have been entered into the table, either by being instantiated, or by being entered into a hash table (this because a class’s index into the table is its identityHash<\/a>). \u00c2\u00a0But method lookup traverses a class’s superclass chain, and e.g. abstract superclasses on the chain may not have been entered into the table. \u00c2\u00a0So the scan for forwarding pointers needs to follow the superclass chain of each class in the table until a class with an index is found; classes with indices are in the table so will be seen in scanning the table.<\/p>\n

In Squeak super sends are implemented using a method’s method class association<\/em>; this is its last literal and is an association from class name to class object of the class that owns the method, the method’s method class (quite different from the method’s class). \u00c2\u00a0A superclass send fetches the value of the method class association and then the superclass \u00c2\u00a0of the method class, and starts the lookup in this superclass. \u00c2\u00a0To avoid a read barrier on accessing the superclass, the stack zone scan needs to follow the method class association to the class.<\/p>\n

Since the stack zone<\/a>\u00c2\u00a0houses \u00c2\u00a0only some activation records, return from the base stack frame in a stack page may attempt to return out of the stack zone into a context. \u00c2\u00a0At this point the VM “faults in” the context into a new stack page (which I term marrying it with its stack frame). \u00c2\u00a0This process must now check for forwarding pointers throughout the context and the method’s method class association. \u00c2\u00a0Since marrying a context is an expensive operation this adds hopefully negligible overhead.<\/p>\n

Access to literals other than the method class association are of three kinds, message selectors, global variable associations, and ordinary literals. \u00c2\u00a0Let’s consider these in turn.<\/p>\n