<div dir="ltr"><div dir="ltr">On Wed, 26 Feb 2020 at 18:48, Ömer Sinan Ağacan <<a href="mailto:omeragacan@gmail.com">omeragacan@gmail.com</a>> wrote:<br></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">So the key points from this thread are:<br>
<br>
- PAP payloads are scavenged using the function's bitmap. Because a PAPs payload<br>
will have less number of closures than the function's arity the bitmap will<br>
always have enough bits.<br>
<br>
- A bit in a function bitmap is NOT for liveness (e.g. does not indicate whether<br>
an argument used or not), but for pointers vs. non-pointers. Function bitmaps<br>
are called "liveness bits" in the code generator which is misleading.<br></blockquote><div><br></div><div>I think of all bitmaps as representing "liveness" (or equivalently "pointerhood") for the purposes of GC. There's no difference from the GC's perspective between a non-pointer and a pointer that it doesn't need to follow.<br></div><div><br></div><div>In fact there's nothing to prevent us using the function bitmap to indicate dead arguments too - it would require zero changes in the RTS, the compiler would only need to mark unused pointer arguments as non-pointers in the bitmap. Probably wouldn't be worth very much overall, but I do recall one space leak that would have been cured by this.<br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
- In a function bitmap (small or large), 0 means pointer, 1 means non-pointer.<br></blockquote><div><br></div><div>This is true of bitmaps generally I think, not just function bitmaps. <br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
This is really what confused me in my last email above. For some reason I<br>
intuitively expected 1 to mean pointer, not 0. Simon M also got this wrong<br></blockquote><div><br></div><div>Oops :)</div><div><br></div><div>I think there may originally have been a good reason to have it this way around: before eval/apply, we used bitmaps to describe stack frames, but we didn't need to encode a size in the bitmap because the default was for the stack contents to be pointers unless there was something to tell us otherwise. So a zero suffix of a bitmap just meant "the rest is just normal stack". This changed with eval/apply, but we kept the convention that zero meant pointer in a bitmap.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
("So a 0 in the bitmap always means non-pointer.") so maybe this is confusing<br>
to others too.<br>
<br>
- For functions with known argument patterns we don't use the function's bitmap.<br>
These function's type are greater than ARG_BCO (2), and for those we use the<br>
stg_arg_bitmaps array to get the bitmap.<br>
<br>
For example, the bitmap for ARG_PPP (function with 3 pointer arguments) is at<br>
index 23 in this array, which is 0b11. For ARG_PNN it's 0b110000011. The least<br>
significant 6 bits are for the size (3), the remaining 0b110 means the first<br>
argument is a pointer, rest of the two are non-pointers.<br></blockquote><div><br></div><div>Actually I think documentation on this is missing in the wiki, I guess I never got around to updating it when we implemented eval/apply. This page should really describe function info tables: <a href="https://gitlab.haskell.org/ghc/ghc/wikis/commentary/rts/storage/heap-objects#info-tables">https://gitlab.haskell.org/ghc/ghc/wikis/commentary/rts/storage/heap-objects#info-tables</a></div><div><br></div><div>If you want to add documentation that would be a good place.<br></div><div><br></div><div>Cheers</div><div>Simon<br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
I still don't understand why this assertion<br>
<br>
ASSERT(BITMAP_SIZE(bitmap) >= size);<br>
<br>
I added to scavenge_small_bitmap in !2727 is failing though.<br>
<br>
Ömer<br>
<br>
Simon Peyton Jones <<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>>, 24 Şub 2020 Pzt, 13:45<br>
tarihinde şunu yazdı:<br>
><br>
> I’m not following this in detail, but do please make sure that the results of this discussion end up in a suitable Note. Obviously it’s not transparently clear as-is, and I can see clarity emerging<br>
><br>
><br>
><br>
> Thanks!<br>
><br>
><br>
> Simon<br>
><br>
><br>
><br>
> From: ghc-devs <<a href="mailto:ghc-devs-bounces@haskell.org" target="_blank">ghc-devs-bounces@haskell.org</a>> On Behalf Of Simon Marlow<br>
> Sent: 24 February 2020 08:22<br>
> To: Ömer Sinan Ağacan <<a href="mailto:omeragacan@gmail.com" target="_blank">omeragacan@gmail.com</a>><br>
> Cc: ghc-devs <<a href="mailto:ghc-devs@haskell.org" target="_blank">ghc-devs@haskell.org</a>><br>
> Subject: Re: Confused about PAP object layout<br>
><br>
><br>
><br>
> On Thu, 20 Feb 2020 at 09:21, Ömer Sinan Ağacan <<a href="mailto:omeragacan@gmail.com" target="_blank">omeragacan@gmail.com</a>> wrote:<br>
><br>
> > I'm not sure what you mean by "garbage". The bitmap merely determines whether<br>
> > a field is a pointer,<br>
><br>
> I think the bitmap is for liveness, not for whether a field is pointer or not.<br>
> Relevant code for building an info table for a function:<br>
><br>
> mk_pieces (Fun arity (ArgGen arg_bits)) srt_label<br>
> = do { (liveness_lit, liveness_data) <- mkLivenessBits dflags arg_bits<br>
> ; let fun_type | null liveness_data = aRG_GEN<br>
> | otherwise = aRG_GEN_BIG<br>
> extra_bits = [ packIntsCLit dflags fun_type arity ]<br>
> ++ (if inlineSRT dflags then [] else [ srt_lit ])<br>
> ++ [ liveness_lit, slow_entry ]<br>
> ; return (Nothing, Nothing, extra_bits, liveness_data) }<br>
><br>
> This uses the word "liveness" rather than "pointers".<br>
><br>
> However I just realized that the word "garbage" is still not the best way to<br>
> describe what I'm trying to say. In the example<br>
><br>
> [pap_info, x, y, z]<br>
><br>
> If the function's bitmap is [1, 0, 1], then `y` may be a dead (an unused<br>
> argument, or "garbage" as I describe in my previous email) OR it may be a<br>
> non-pointer, but used (i.e. not a garbage).<br>
><br>
><br>
><br>
> I don't think we ever put a zero in the bitmap for a pointer-but-not-used argument. We don't do liveness analysis for function arguments, as far as I'm aware. So a 0 in the bitmap always means "non-pointer".<br>
><br>
><br>
><br>
> The only reaosn the code uses the terminology "liveness" here is that it's sharing code with the code that handles bitmaps for stack frames, which do deal with liveness.<br>
><br>
><br>
><br>
> So maybe "liveness" is also not the best way to describe this bitmap, as 0 does<br>
> not mean dead but rather "don't follow in GC".<br>
><br>
><br>
> On my quest to understand and document this code better I have one more<br>
> question. When generating info tables for functions with know argument patterns<br>
> (ArgSpec) we initialize the bitmap as 0. Relevant code:<br>
><br>
> mk_pieces (Fun arity (ArgSpec fun_type)) srt_label<br>
> = do { let extra_bits = packIntsCLit dflags fun_type arity : srt_label<br>
> ; return (Nothing, Nothing, extra_bits, []) }<br>
><br>
> Here the last return value is for the liveness data. I don't understand how can<br>
> this be correct, because when we use this function in a PAP this will cause NOT<br>
> scavenging the PAP payload. Relevant code (simplified):<br>
><br>
> STATIC_INLINE GNUC_ATTR_HOT StgPtr<br>
> scavenge_PAP_payload (StgClosure *fun, StgClosure **payload, StgWord size)<br>
> {<br>
> const StgFunInfoTable *fun_info =<br>
> get_fun_itbl(UNTAG_CONST_CLOSURE(fun));<br>
><br>
> StgPtr p = (StgPtr)payload;<br>
><br>
> StgWord bitmap;<br>
> switch (fun_info->f.fun_type) {<br>
> ...<br>
><br>
> default:<br>
> bitmap = BITMAP_BITS(stg_arg_bitmaps[fun_info->f.fun_type]);<br>
> small_bitmap:<br>
> p = scavenge_small_bitmap(p, size, bitmap);<br>
> break;<br>
> }<br>
> return p;<br>
> }<br>
><br>
><br>
> Here if I have a function with three pointer args (ARG_PPP) the shown branch<br>
> that will be taken, but because the bitmap is 0 (as shown in the mk_pieces code<br>
> above) nothing in the PAPs payload will be scavenged.<br>
><br>
><br>
><br>
> It gets the bitmap from stg_arg_bitmaps[fun_info->f.fun_type], not from the info table. Hope this helps.<br>
><br>
><br>
><br>
> Cheers<br>
><br>
> Simon<br>
><br>
><br>
><br>
><br>
><br>
><br>
> Here's an example from a debugging session:<br>
><br>
> >>> print pap<br>
> $10 = (StgPAP *) 0x42001fe030<br>
><br>
> >>> print *pap<br>
> $11 = {<br>
> header = {<br>
> info = 0x7fbdd1f06640 <stg_PAP_info><br>
> },<br>
> arity = 2,<br>
> n_args = 1,<br>
> fun = 0x7fbdd2d23ffb,<br>
> payload = 0x42001fe048<br>
> }<br>
><br>
> So this PAP is applied one argument, which is a boxed object (a FUN_2_0):<br>
><br>
> >>> print *get_itbl(UNTAG_CLOSURE(pap->payload[0]))<br>
> $20 = {<br>
> layout = {<br>
> payload = {<br>
> ptrs = 2,<br>
> nptrs = 0<br>
> },<br>
> bitmap = 2,<br>
> large_bitmap_offset = 2,<br>
> __pad_large_bitmap_offset = 2,<br>
> selector_offset = 2<br>
> },<br>
> type = 11,<br>
> srt = 1914488,<br>
> code = 0x7fbdd2b509c0 "H\215E\370L9\370r[I\203\304 M;\245X\003"<br>
> }<br>
><br>
> However if I look at the function of this PAP:<br>
><br>
> >>> print *get_fun_itbl(UNTAG_CLOSURE(pap->fun))<br>
> $21 = {<br>
> f = {<br>
> slow_apply_offset = 16,<br>
> __pad_slow_apply_offset = 3135120895,<br>
> b = {<br>
> bitmap = 74900193017889,<br>
> bitmap_offset = 258342945,<br>
> __pad_bitmap_offset = 258342945<br>
> },<br>
> fun_type = 23,<br>
> arity = 3<br>
> },<br>
> i = {<br>
> layout = {<br>
> payload = {<br>
> ptrs = 0,<br>
> nptrs = 0<br>
> },<br>
> bitmap = 0,<br>
> large_bitmap_offset = 0,<br>
> __pad_large_bitmap_offset = 0,<br>
> selector_offset = 0<br>
> },<br>
> type = 14,<br>
> srt = 1916288,<br>
> code = 0x7fbdd2b50260 <base_GHCziRead_list3_info><br>
> "I\203\304(M;\245X\003"<br>
> }<br>
> }<br>
><br>
> It has arity 3. Since the first argument is a boxed object and this function has<br>
> arity 3, if the argument is actually live in the function (i.e. not an unused<br>
> argument), then the bitmap should have a 1 for this. But because the argument<br>
> pattern is known (ARG_PPP) we initialized the bitmap as 0! Not sure how this<br>
> can work.<br>
><br>
> What am I missing?<br>
><br>
> Thanks,<br>
><br>
> Ömer<br>
><br>
> Ben Gamari <<a href="mailto:ben@smart-cactus.org" target="_blank">ben@smart-cactus.org</a>>, 14 Şub 2020 Cum, 20:25 tarihinde şunu yazdı:<br>
> ><br>
> > Ömer Sinan Ağacan <<a href="mailto:omeragacan@gmail.com" target="_blank">omeragacan@gmail.com</a>> writes:<br>
> ><br>
> > > I think that makes sense, with the invariant that n_args <= bitmap_size. We<br>
> > > evacuate the arguments used by the function but not others. Thanks.<br>
> > ><br>
> > > It's somewhat weird to see an object with useful stuff, then garbage, then<br>
> > > useful stuff again in the heap, but that's not an issue by itself. For example<br>
> > > if I have something like<br>
> > ><br>
> > > [pap_info, x, y, z]<br>
> > ><br>
> > > and according to the function `y` is dead, then after evacuating I get<br>
> > ><br>
> > > [pap_info, x, <garbage>, z]<br>
> > ><br>
> > > This "garbage" is evacuated again and again every time we evacuate this PAP.<br>
> > ><br>
> > I'm not sure what you mean by "garbage". The bitmap merely determines<br>
> > whether a field is a pointer, not whether it is copied during<br>
> > evacuation. A field's bitmap bit not being set merely means that we won't<br>
> > evacuate the value of that field during scavenging.<br>
> ><br>
> > Nevertheless, this all deserves a comment in scavenge_PAP.<br>
> ><br>
> > Cheers,<br>
> ><br>
> > - Ben<br>
> ><br>
</blockquote></div></div>