<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div>On Sep 4, 2007, at 04:15, Talin wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Gordon Henriksen wrote:</div></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> <blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">But to elaborate upon the described class of collectors: The emitted GC tables do not describe the dynamic call stack; rather, they are static data compiled into the executable. Only when cross-referenced with the dynamic call stack do they identify the roots. The garbage collectors for .NET and Java work in this manner.</span></div></blockquote><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Here's an example of the sort of data these tables might contain. (I<span class="Apple-converted-space"> <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">generated this using the -print-gc feature which I have added to llc locally; the llc in Subversion cannot print this data because it does not collect it.) This test case has a simple function with 2 roots and 1 call.</span></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">GC roots for fun:</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><span class="Apple-converted-space"> </span>0 <span class="Apple-converted-space"> </span>8[sp]</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><span class="Apple-converted-space"> </span>1 <span class="Apple-converted-space"> </span>4[sp]</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">GC safe points for fun:</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><span class="Apple-converted-space"> </span>label 1: post-call, live = { 0, 1 }</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Provided this information, the collector can easily identify the live<span class="Apple-converted-space"> <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">roots within fun's stack frame at runtime—so long as fun is paused at the safe point, which it must be if it is not the topmost stack frame.</span></span></div></blockquote></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><blockquote type="cite"> </blockquote><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">How do you get the info for the non-topmost stack frames in this case?</div></blockquote><div><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">The runtime needs to walk the machine stack. The return address of the inner frame will have the address of <font class="Apple-style-span" face="Courier">label 1</font> while <font class="Apple-style-span" face="Courier">fun</font> is paused in the call that precedes it. An actual codegen example of the same module is here:</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070903/053242.html">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20070903/053242.html</a></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">Llabel1 is the safe point.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><span class="Apple-converted-space"><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">Am I going to need to implement my own version of llvm_cg_walk_gcroots() ?</span></span></div></blockquote><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">If you choose not use the LowerGC transformation and the attendant shadow stack.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">My current mad scheme (which I'm not sure will work) for safe points in<span class="Apple-converted-space"> <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">a multi-threaded environment uses a global POSIX reader/writer lock. Each running thread keeps a read lock on the global lock when it's running. The old-generation collector attempts to acquire a write-lock when it needs to do a collection. At some semi-regular interval, the application threads will need to momentarily release the lock, telling the global collector its OK to run. (This is only for the old generation - young generation collections are handled per-thread, hopefully. Although cross-thread references make that complex...) The advantage of this scheme is that it doesn't require preemptive thread freezing, icky pagefault-based write barriers or other platform-specific hacks, the disadvantage is that all threads have to wait if some thread doesn't want to release the read lock in a timely manner.</span></span></div></blockquote><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">Could work.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br class="webkit-block-placeholder"></div><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">The hard part will be analyzing loops in the generated IR to decide<span class="Apple-converted-space"> <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">whether a call to pulse the lock needs to be inserted in the loop body or not. Obviously, dropping and reacquiring a lock is expensive, so if the loop is provably short, I don't want to do that.</span></span></div></blockquote><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; ">Sure. And if there already exists an unconditional safe point within the loop body, then you also do not need to insert one in the loop. This is a very common need, and is one of the target-independent features I want to provide in the collector infrastructure. However, although I have made provisions for it, I have no immediate need for it. Patches are welcome.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">So it sounds like I should be passing the pointer to the stack root list<span class="Apple-converted-space"> <span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">at the same time I release the lock? I supposed I could store it in the TLD which I guess wouldn't be too expensive.</span></span></div></blockquote><br></div><div><span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Trebuchet MS; 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: Trebuchet MS; 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: Trebuchet MS; 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: Trebuchet MS; 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: Trebuchet MS; 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: Trebuchet MS; 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; ">— Gordon<br class="Apple-interchange-newline"></span></span></span></span></span></span> </div><br></body></html>