I Think by the time you add a header you have added a lot of complexity for little gain. eg C Interop or mapping directly to structures such as IP headers become Impossible. You can add the header to the top but then you need to find the base object all the time and access it..certainly not elegant.
The C# method of storing no interior references has some merit . Value types are copied by value , they can be passed by reference ( register) but are never stored as a reference. Its a good idea , it doesnt work that great in C# because in 1) In v 1 there were no generics so every collection was boxed ( and people still havent unlearned that generic arrays of structs are not boxed and can be passed by ref) 2) You dont know when its boxed and there are so many cases where they get boxed that your better of dealling with reference types 99% of the time. The only trick is you cant store a reference to the interior array itself.. but you can store a slice. Slices are interior pointers and have the same issue, I was thinking they can be handled by a mask and some high bits ( on 32 bit or cases where you cant change the mark a fat pointer of ref + offset) , make the mark aware of slices ( via type look up or a slice lookup ( like ref lookup) in the type ) and then remove the bits making them just a reference to the base object. Then use slices as interior pointers. Note for an interior array slice would point to the object and when you take the slice for the 0 element , the offset would be &array[0] - &object. Unlike general interior references which could be common this would only be slices which would be much rarer. I still think at least for v1 embedded unboxed arrays should be ref types or value types restricted to having no references it makes things a lot more simpler and can be extended later . I even think their size should be limited to 128 or 256 elements ( and your large object problems go away) . You dont want to be in a position where a design feature people are using is stopping you doing something like remove the read barrier etc. Easier to introduce later. Like the read barrier removal i take it the read locks are only needed while the collector is running , the cost of this will be high on single core . Isn't checking for the read lock the same as a read barrier or is it a write barrier on mutate which sets the lock and only the collector checks it ? What about other mutattng threads / reading threads ? "*read* references to the same object in the same mutator's current call frame to become dead" sounds pretty bad , does this include a "this" pointer ? .. What is dead anyway are you reffering to a C++ dead object ref , will this give a null ref exception ? Thinking further i think its ok going from readable to read-write is pretty rare so will be done under pretty tight conditions.. The rest of the conditions seem ok . Ben On Wed, Oct 30, 2013 at 2:02 AM, Jonathan S. Shapiro <[email protected]>wrote: > So I've been thinking pretty hard about interior object references, > because it's harder than I thought at first. > > My initial thought about interior references was that we would need to use > two different referencer representations depending on whether the runtime > performed relocation or not. The problem is that in a relocating collector > we need a way to find the header of the outer object. That's actually > pretty ugly, because it makes object size and representation contingent on > the selection of GC technique. It's also a problem because "fat references" > are conservatively contagious. For example, it probably would mean that all > /this/ pointers would have to become fat references. > > So I spent some more time thinking about it, and maybe I have some ideas. > I'd like feedback, alternatives, and pointers to documentation of other > solutions. > > The balance of this email is *only* considering relocating collectors. > > *Assumptions* > > First, let me state my assumptions about on-heap objects from the GC point > of view: > > 1. The initial word contains the mark bits, GC colors, and object size > in words. This object is "owned" by the GC. It is not accessed by the > mutator except in barrier code that is (1) generated by or (2) compiled in > on behalf of the GC subsystem. I will refer to this as the GC header word. > 2. The GC assumes that the next word is a VTable pointer, *if and only > if* the object is relocatable *and* this is a relocating GC > implementation. A relocating GC can be implemented without this assumption, > but we can't exploit the constant object optimization without it. A > non-relocating GC does not require this assumption. > 3. Marking and forwarding are performed only on exterior objects. The > fact that an object has *been* forwarded needs to be recorded on both > interior and exterior object headers. > > Note that as much as I'd prefer to get rid of them, I think *interior* objects > also require object header words. In principle these could be eliminated, > but I don't really see a clean way to do it. > > *Problem Statement* > > There are several problems that need to be solved for interior pointers: > > 1. For various reasons, we need to be able to find the containing * > exterior* object from an interior object reference. > 2. We need a way to *identify* interior pointers during marking and > relocation. > 3. Marking an interior object needs to have the effect of marking the > exterior object. > 4. Interior object references may point into an exterior object that > has been forwarded. This needs to be handled by the barrier implementation. > > The last two issues are pretty easy to address once we solve the first > two, so I'll focus on the first two. > * > * > *Identifying Interior Object References* > > Identifying interior object references in large object space is easy, > because they won't point at the start of a page. For the same reason, it's > easy to locate both the containing object base pointer and the object > header for such an object. Note that we probably need to identify LOS > object references distinctively in any case, because the object headers for > those objects are likely to be represented differently from those in > conventional object spaces. > > Identifying interior object references in the stack is not really necessary > *. *First, *all* references into the stack are effectively interior > pointers (into the stack frame), but second, we do not forward or relocate > such objects [*], so we don't really need to be concerned about whether an > object reference into the stack names the beginning of an object. The hard > cases are interior references that point into the nursery or the general > heap. > > [*] There's a possibility that on-stack objects get forwarded if we > implement lazy continuation capture, but that's doable, and I'm going to > ignore it here. > > > So the real problem is to *identify* interior references into the nursery > or the general heap. > > I considered identifying interior pointers by setting a low-order bit in > the pointer value, but I think that's difficult: > > - It forces us to conservatively mask off that low bit on an awful lot > of references. Note that we can't really do this by duplicating code, nor > would we want to. > - Once the bit is masked off, we end up with a lot of un-identified > interior pointers in GC roots. We *can* limit them to appear *only* in > GC roots, and distinguish those with static typing, but it adds a bunch of > stuff to keep track of, and a bunch of main-line code to do the masking. > > I also considered an approach that would use two virtual mappings of the > heap - one for interior references and the other for exterior references. > That approach: > > - Eliminates the masking code > - Preserves the identifiability of interior references at all points, > so we don't need static typing magic to identify them. > - Cuts the available virtual space in half (not an issue on 64 bit > systems). > - Makes object EQ slightly more expensive. > > On 32-bit systems, at least, I think that's not a solution because of the > reduction in available virtual address space. > > So that leaves some sort of marker bit in the interior object header, > which could either be a distinguished bit 'I' or the uppermost bit of the > GC's object size field (see below). > > *Finding Exterior from Interior* > > Given an interior reference into the nursery or general heap, it's not * > that* hard to find the object base. We walk backwards through the line > markers to find the nearest preceding non-continued line, and then walk > forward using the object sizes until we find the object containing the > reference of interest. Alternatively - and probably better - note that the > GC runtime does not use the object size field in an interior GC header; we > can use this field to hold a (negative) offset to the containing object, > which allows us to walk outward to the exterior object directly. > > If we use the reverse-offset approach, then the high-order bit of the > object size does double duty as a bit that identifies interior objects. > > Personally, I don't think it matters whether we use two's complement > encoding or reserve an 'I' bit. We're going to lose a bit either way. I > think the choice probably gets made based on the barrier implementations. > There may turn out to be a reason to have the 'I' bit conveniently adjacent > to something else for some reason. > > *Other Thoughts* > * > * > *Incremental Logging* > > As I was writing through this, it occurred to me that interior header > words solve another problem: incremental logging. When an object is very > large, we *really* don't want to be logging the whole object. If unboxed > objects on the interior carry 'M' (modified and deferred) bits, then we > have a straightforward way to log (hierarchically structured) sub-portions > of objects. That's actually very nice, because it means that the *write* > barrier > is almost entirely unaffected by the presence of interior objects. > > *Deferred Read Barriers* > * > * > It also occurred to me that it *might* be possible to use the 'M' bits to > reduce forwarding overhead dynamically. The core idea is that we don't need > to do read barriers until somebody actually modifies the object. If we can > assume the presence of read locks, then I think we can do something like > the following: > > 1. An object cannot be forwarded with the M bit set. That is: we > require any deferred RC updates to be flushed. > 2. An object whose 'M' bit is *clear* can be forwarded eagerly. > Immediately after forwarding, *both* copies of the object are valid. > 3. The first time that an update is performed on *either* copy, we > know that: > 1. The 'M' bit is clear prior to this write barrier > 2. The mutator thread performing this store holds an exclusive lock > on this object > > If we can somehow make the following additional assumptions: > > - Upgrading an object from readable to read-write (by running a write > barrier) causes all *read* references to the same object in the same > mutator's current call frame to become dead. > - Upgrading a *forwarded* object from readable to read-write *also* causes > a stack return barrier to be introduced. > - If mutator A holds a write lock on an object, then no other mutator > holds a live *read* reference on the same object > > Then *we don't need a read barrier at all*, which means (pleasantly) that > we don't need dynamic translation. > > *Summary* > * > * > > 1. I think there is a workable way to use a thin representation for > interior pointers in a relocating collector > 2. It could be that we don't need a read barrier after all. > > > _______________________________________________ > bitc-dev mailing list > [email protected] > http://www.coyotos.org/mailman/listinfo/bitc-dev > >
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
