<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div apple-content-edited="true"><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div>I believe there is just one check when the parameter is first passed.</div><div><br></div></span></span></span></span></span></span></span></span></div></span></div><div><div>On 22 Apr 2009, at 10:54, Jay wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; ">Yes this helps, thank you. Maybe checkin under doc? One thing you didn't understand my wording about and you seemed to contradict is "VAR to VAR".<br> <br> <br>PROCEDURE F1() =<br>VAR i;<br>BEGIN<br> F2(i);<br>END F1;<br> <br><br>PROCEDURE F2(VAR a:INTEGER)=<br>BEGIN<br> F3(i);<br>END F2;<br> <br><br>PROCEDURE F3(VAR a:INTEGER)=<br>BEGIN<br> a := 1;<br>END F3;<br> <br><br>Where are the calls to CheckLoad/StoreTracedRef?<br> (Duh, I can try it out..)<br>It seems redundant to put them "everywhere".<br>Esp. it seems that F2 shouldn't have do anything.<br><br> <br>But throw in that F3 might extern and that is unclear.<br>So I just made up a suggestion that VAR is not good to pass to C code.<br>That checks are inserted when 1) a pointer is dereferenced -- loaded<br>or stored in Modula-3 or 2) a<br>pointer becomes untraced (var becomes untraced ref, among others).<br> <br> <br> > Right. I think I did see you compute and pass an offset to C code<br> <br> <br>I had something like that very recently but think I didn't set it or commit it.<br>I had something like:<br> <br> <br>size_t offset;<br> <br> <br>Init(Mutex* root, int* interior)<br>{<br> offset = (size_t)interior - (size_t)root;<br>}<br> <br> <br>DoSomething(Mutex* anotherRoot)<br>{<br> int* interior = (int*)(offset + (size_t)anotherRoot);<br> printf("%d\n", *interior);<br>}<br> <br> <br>but I came up with a way to avoid that I think, and then rolled it all back or something anyway.<br> <br> <br> <br> - Jay<br> <br><hr id="stopSpelling">CC:<span class="Apple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>From:<span class="Apple-converted-space"> </span><a href="mailto:hosking@cs.purdue.edu">hosking@cs.purdue.edu</a><br>To:<span class="Apple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br>Subject: Re: [M3devel] explanation of CheckLoadTracedRef?<br>Date: Wed, 22 Apr 2009 10:02:52 +1000<br><br><div><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div style="word-wrap: break-word; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div>On 21 Apr 2009, at 19:37, Jay wrote:</div></span></span></span></span></span></span></span></span></div></span></div><div><br class="EC_Apple-interchange-newline"><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">> > How bad/unportable was it the previous way, the VM-synchronized way?<br>><span class="EC_Apple-converted-space"> </span><br>> Not compatible with system threading.<br><br> <br>Really? NT386 wasn't VM-synchronized back in 3.6, 4.1, etc.?</div></span></blockquote><div><br></div><div>It was, but every system call had to be wrapped with a call to acquire the global heap lock!</div><div><br></div><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">Or only with great cost?</div></span></blockquote><div><br></div><div>Yes, taking the lock was expensive and prevented scaling on multi-cores.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">I have to admit, those old import .libs, kernel32.lib, etc. I didn't realize what was in them when I deleted them. I thought they were just regular import .libs.</div></span></blockquote><div><br></div><div>There was also the work to wrap all dll symbols to acquire the lock.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">I think I got luckly in that the overlap between me deleting them and you removing VM-synchronized GC was small or zero.</div></span></blockquote><div><br></div><div>You should have seen the mess it was before... ;-)</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">> You should *never* access a field in the heap in C code! All<span class="EC_Apple-converted-space"> </span><br>> accesses to traced fields in the heap must take place in Modula-3.<span class="EC_Apple-converted-space"> </span><br>> Otherwise things will break! C wrappers should not do anything other<span class="EC_Apple-converted-space"> </span><br>> than forward calls to C library calls. They should not perform heap<span class="EC_Apple-converted-space"> </span><br>> accesses.<br><br> <br>Ok, that makes sense.<br>Important "out" is the accessing stack is always ok.</div></span></blockquote><div><br></div><div>Yes, so long as a references to an object is held on the stack then it is safe to pass an address within it to external calls. Thus, many C functions can take VAR arguments that may end being references to the fields of objects. The compiler injects the necessary CheckLoad/CheckStore operations when passing VAR parameters, etc., and the GC maintains the invariant that all stack-referenced objects don't move, stay black (for incremental GC), and remain dirty (for generational GC).</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">But this is a requirement I didn't keep in mind.<br>Now, luckily, the C wrappers are all relatively thin and not difficult<br>to re-review in their entirety.</div></span></blockquote><div><br></div><div>Right. I think I did see you compute and pass an offset to C code, but that may have only been in code you e-mailed me for perusal rather than code that got checked in. Might be worth reviewing...</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">But, take for example "open".<br>The first parameter to it is bound to be in the heap.</div></span></blockquote><div><br></div><div>The ambiguous roots garbage collector we use maintains the invariant that pointers to the interior of heap objects from the stack *pin* that object in the heap: it will not move while the pointer from the stack exists, and invariants will be maintained so that its contenst can be manipulated safely even in the face of incremental and generational GC.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">But probably it is untraced or somehow ok, since it does<br>come from a module used primarily for C interop.</div></span></blockquote><div><br></div><div>Certainly, C code should never be manipulating the *traced* fields of traced heap objects. It is fine for it to manipulate the untraced fields of traced heap objects.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">And, the line between C wrappers and the "C library" that they forward to<br>does not exist.<br>If I, say, pass a VAR to a VAR..no check is made?</div></span></blockquote><div><br></div><div>Not sure what you mean by this. Any call that passes traced VAR params will generate a check as necessary before the call.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">Important to declare extern/C functions as taking UNTRACED REF and not VAR?</div></span></blockquote><div><br></div><div>No, VAR is fine. So long as the VAR value being passed is not traced.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">> I think you are confusing incremental and incremental GC.<br>You assume I understand more than I do (I assume you have a typo. :))</div></span></blockquote><div><br></div><div>;-)</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">"generational" -- the concept that most objects die young.<br> (aka most objects could have been allocated on the stack...)</div></span></blockquote><div><br></div><div>Not quite. The idea is that the likelihood of an object dying is a function of its age. There is a *weak* generational hypothesis that "most objects die young", and a *strong* generational hypothesis that "the older an object is the less likely it is to die". Many (but not all) programs support these hypotheses, which permits generational GC to focus effort where it is likely to be profitable (i.e., to free up a lot of space).</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">But does that imply detailed implementation choices, or is just like a "guiding principle"?<br>I guess it implies the heap is split into at least two generations, old and young.<br>Though I guess in reality there is a range of young, less young, lesser young, least young, etc.</div></span></blockquote><div><br></div><div>Right, many different collectors have exploited age in this way. For the M3 collector we have just two generations: old and young.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">And that has objects age, they should be moved from young to old heaps, and references to them either updated right away, or "caught" upon use and updated then...something like that.</div></span></blockquote><div><br></div><div>Old-space objects are "clean" if they contain no references to young-space objects. The Modula-3 compiler injects checks to make sure that whenever we store a reference into a clean old-space object it is marked "dirty". When a young-space collection occurs we must process the references in dirty old-space objects as roots into the young-space.</div><br><blockquote><span class="EC_Apple-style-span" style="word-spacing: 0px; font: normal normal normal 12px/normal Helvetica; text-transform: none; color: rgb(0, 0, 0); text-indent: 0px; white-space: normal; letter-spacing: normal; border-collapse: separate; "><div class="EC_hmmessage" style="font-size: 10pt; font-family: Verdana; ">"incremental" -- don't pause the world..</div></span></blockquote><div><br></div><div>Not quite. The opposite of stop-the-world (stopping all the mutator threads to process their stacks) is on-the-fly. Incremental refers to the ability to interleave GC work with mutator work. If the GC work can be interleaved with mutator threads without stopping the mutator threads at each increment then the collector is said to be concurrent (GC work proceeds concurrently with mutator work).</div><div>The current M3 collector has a stop-the-world non-moving phase, followed by an concurrent copying phase. I have some incomplete work that will also make the M3 collector on-the-fly (no STW phase) and parallel (multiple GC threads can operate concurrently).</div><div><br></div><div>Hope all this helps!</div></div><br></div></span><br class="Apple-interchange-newline"></blockquote></div><br></body></html>