423070 - Clang analyzer to verify Traverse and Unlink cycle collection methods

Status: NEW

(Developer Infrastructure :: Source Code Analysis, defect, P2)

Description

[David Mandelin [:dmandelin]]

For each class that participates in cycle collection (i.e., has a nsCycleCollectingRefCnt member), check the Traverse and Unlink methods. Verify that each method mentions each owned pointer (i.e., each pointer of type nsCOMPtr, nsRefPtr, etc.)

Comment 1

[Ben Turner (not reading bugmail, use the needinfo flag!)]

Perfectly valid implementations may not touch all their owned pointers, of course, but I'd prefer to have some false positives!

Comment 2

[Daniel Brooks [:db48x]]

Why not write a script that creates the correct Traverse and Unlink methods, rather than verifying manually written ones?

Comment 3

[David Mandelin [:dmandelin]]

Attachment: Analysis results

Here's the results. It found 94 error reports, plus some sites where the main class doesn't seem to be referred to at all inside Traverse or Unlink, but it looks like maybe that's just supposed to happen sometimes. As always, please check out the results and let me know if I've misunderstood the spec or you need any other changes.

Comment 4

[Ben Turner (not reading bugmail, use the needinfo flag!)]

(In reply to comment #3)

This is sweet, thanks David!

Comment 5

[Jesse Ruderman]

Is this script in hg?  If not, can you attach it to the bug so it doesn't get lost?

Comment 6

[David Mandelin [:dmandelin]]

Attachment: Scripts

Comment 7

[(no longer active)]

I want to see if I can fix this now.  Do we have any good heauristics these days to be able to tell automatically whether a member type should participate in cycle collection?  Obvious things such as nsCOMPtr and nsRefPtr definitely should, but what about things such as T*, T&, classes containing such members, etc?  Are there member types that sometimes should and sometimes should not participate in CC?  (I suspect T* would be in that category, depending on whether it's semantically a strong reference.)

Comment 8

[Andrew McCreight [:mccr8]]

I'll post some more tomorrow, but I did some more than this, I think based on dmandelin's Dehydra scripts, over in bug 423032.

Comment 9

[Olli Pettay [:smaug][[e-mail]]]

Only nsCOMPtr and nsRefPtr pointing to possibly cycle collectable objects should be added to CC.

Comment 10

[Andrew McCreight [:mccr8]]

(In reply to Olli Pettay [:smaug] from comment #9)
> Only nsCOMPtr and nsRefPtr pointing to possibly cycle collectable objects
> should be added to CC.

It is a little more complicated than that, in practice.  There are things like arrays and hashtables of refcounted pointers.  We also have a number of cases where there's a structure containing refcounted pointers that is uniquely owned by another, and we traverse/unlink through the owning outer structure.

Also, you don't want to actually report all refcounted fields to the CC, only things where there is some subclass that is cycle collected.  For ISupports classes, arguably you should just tell it about everything and then just deal with the extra QIs that go nowhere, but for non-ISupports classes you'll actually need to check if the class implements refcounting.  We don't support any inheritance in that situation, so at least you won't have to deal with subtyping.

I found that it was useful to check both directions of the should-be-traversed relation, by which I mean that you want to check that the set of fields traversed/unlinked is exactly the same as the set that you think should be traversed/unlinked.  When I was working on my static analysis, this exposed a number of things I was missing in my analysis.  That will report fields that are raw pointers but are just being manually AddRefed, but I think we want to fix those anyways.

Comment 11

[(no longer active)]

I have an intern who is going to work on this... Vicariously assigning to myself for now.

Comment 12

[Andrew McCreight [:mccr8]]

Bug 423032 is another place to look for more information, and has a link to my github repo, where I expanded dmandelin's scripts a fair amount.  Things have changed a good amount since then, and you aren't using Dehydra, but it might be useful to look at some of the logic there.

Comment 13

[poiru]

Not actively working on this at the moment so unassigning for now. I hope to pick this up after I finish some of my current projects.

Comment 14

[Nika Layzell [:nika] (ni? for response)]

Let's hope that I'm the last in the line of people who have been assigned this bug :)

Comment 15

[Nika Layzell [:nika] (ni? for response)]

Attachment: TestCycleCollection.cpp

This is the current test which I have running locally for my plugin. I hope it's well enough commented that you can understand what's going on from the comments, but if you have questions just ask them on irc. I'm usually around.

The main point of this review is that I want to see if people are OK with the usage of the pass so far.

Basically, this pass is intended to ensure that every field which should be traversed is traversed. It doesn't ensure that every field which is traversed should be traversed. It also doesn't make any effort to validate statements which it doesn't understand within traverse blocks.

Comment 16

[Nika Layzell [:nika] (ni? for response)]

I feel like I should have a quick list of things which this doesn't cover at all:
* Implementations which dispatch to other functions for part of the traversal/unlinking
* Inline or owned (UniquePtr) structs which contain traversable items
* Base classes which contain traversable items
* Ensuring that only fields which should be traversed are traversed

I feel like most of those should be handled in follow-ups. This feels like a big enough project as is without that extra complexity.

Things this does cover, which may not be immediately obvious
* nsTHashtable, nsTArray, etc. containing RefPtr or nsCOMPtr.
* non-XPCOM cycle collectable types.

(I may have forgotten things which aren't handled)

Comment 17

[Nika Layzell [:nika] (ni? for response)]

Attachment: List of XPCOM classes which would need to be annotated with MOZ_CC

Comment 18

[Olli Pettay [:smaug][[e-mail]]]

Comment on attachment 8677089 [details]
TestCycleCollection.cpp

Would be good to point out that MOZ_CC is in practice the only thing one may need to use, and that usually only in case of C++ interfaces (abstract classes).

Comment 19

[Andrew McCreight [:mccr8]]

Sorry for the delay in my feedback.

It would be good to include a list of things that we could check that we don't in there, as a breadcrumb for anybody in the future who might expand on it.

Why do you need the MOZ_CC_TRAVERSABLE_PTR annotation? Offhand, I would think that the ImplCycleCollectionTraverse would be visible in the same scope as when you would call it. It would also be good to be more concrete in your paragraph on TRAVERSABLE, along the lines of "An example of a class that is traversable but not cycle collectable would be a container class that can hold cycle collected objects, such as nsTArray." (MOZ_CC_TRAVERSE_IMPL is similar I guess, in that I'd hope that it would in general be defined by ImplCycleCollectionTraverse, though I'm sure there are many places where people did not bother.)

Is MOZ_CC_OWNS_TEMPLATE_ARG always needed, or can you infer it if say the template argument is used in an nsRefPtr<T> field? I guess you need this for the basic owning classes like nsRefPtr? This isn't a CC-specific concept, but I suppose if no other analysis is going to use that now the CC is okay.

Out of curiousity, how is UniquePtr<> covered but nsTArray<> isn't? (I think the former isn't a big deal because it isn't as heavily used in CCed classes, IIRC.)

Comment 20

[Nika Layzell [:nika] (ni? for response)]

(In reply to Andrew McCreight [:mccr8] from comment #19)
> Sorry for the delay in my feedback.
> 
> It would be good to include a list of things that we could check that we
> don't in there, as a breadcrumb for anybody in the future who might expand
> on it.
> 
> Why do you need the MOZ_CC_TRAVERSABLE_PTR annotation? Offhand, I would
> think that the ImplCycleCollectionTraverse would be visible in the same
> scope as when you would call it. It would also be good to be more concrete
> in your paragraph on TRAVERSABLE, along the lines of "An example of a class
> that is traversable but not cycle collectable would be a container class
> that can hold cycle collected objects, such as nsTArray."
> (MOZ_CC_TRAVERSE_IMPL is similar I guess, in that I'd hope that it would in
> general be defined by ImplCycleCollectionTraverse, though I'm sure there are
> many places where people did not bother.)

MOZ_CC_TRAVERSABLE_PTR isn't inferred from ImplCycleCollectionTraverse, because there are also ImplCycleCollectionTraverse functions for, for example, nsTArray, which have different constraints on their template arguments. Also, due to the way that templating works with late specialization, it's easier to get correctness through annotating the type, rather than inferring properties of the type due to the fact that it would be possible to specialize a function to be passed the type.

MOZ_CC_TRAVERSE_IMPL is actually used to annotate the Type::cycleCollect::Traverse method so that they can be identified more easily, such that I can analyze them. Introspecting on their name to discover if they are a method named Traverse on a class named cycleCollect would probably be slower, and these methods are almost always created by a macro anyways, so I thought that this was an OK compromise.

> Is MOZ_CC_OWNS_TEMPLATE_ARG always needed, or can you infer it if say the
> template argument is used in an nsRefPtr<T> field? I guess you need this for
> the basic owning classes like nsRefPtr? This isn't a CC-specific concept,
> but I suppose if no other analysis is going to use that now the CC is okay.

MOZ_CC_OWNS_TEMPLATE_ARG is horribly named - I will agree. It's not actually a nsRefPtr thing, rather it is a container thing. Basically what it means is that it needs to be traversed with ImplCycleCollectionTraverse, but only if it's type argument needs to be traversed. Maybe it should be called MOZ_CC_TRANSPARENT_TRAVERSE or something like that, because rather than traversing directly to a cycle collectable type, it traverses to a type which contains a cycle collectable type (if that makes sense).

> Out of curiousity, how is UniquePtr<> covered but nsTArray<> isn't? (I think
> the former isn't a big deal because it isn't as heavily used in CCed
> classes, IIRC.)

Other way around! nsTArray is covered, and UniquePtr isn't.

Comment 21

[Andrew McCreight [:mccr8]]

(In reply to Michael Layzell [:mystor] from comment #20)
> Other way around! nsTArray is covered, and UniquePtr isn't.

Right, that's what I meant. Why is UniquePtr<> not covered?

The rest makes sense. Thanks for the explanations.

Comment 22

[Nika Layzell [:nika] (ni? for response)]

(In reply to Andrew McCreight [:mccr8] from comment #21)
> (In reply to Michael Layzell [:mystor] from comment #20)
> > Other way around! nsTArray is covered, and UniquePtr isn't.
> 
> Right, that's what I meant. Why is UniquePtr<> not covered?
> 
> The rest makes sense. Thanks for the explanations.

I haven't looked into whether there are any problems, but the answer is probably because I just needed to add the MOZ_CC_OWNS_TEMPLATE_ARG attribute to it.

The hard one which isn't done yet is arbitrary inline structs, but I think that should happen in a follow-up.

Comment 23

[Andrew McCreight [:mccr8]]

(In reply to Michael Layzell [:mystor] from comment #22)
> I haven't looked into whether there are any problems, but the answer is
> probably because I just needed to add the MOZ_CC_OWNS_TEMPLATE_ARG attribute
> to it.

Ok, that makes sense. I was just curious if there was anything more to it.

> The hard one which isn't done yet is arbitrary inline structs, but I think
> that should happen in a follow-up.

Sounds good. That's a bit of a niche use case anyways. As long as you are covering the basic container classes like nsTArray that should be good for most things.

Comment 24

[Nika Layzell [:nika] (ni? for response)]

I didn't get any work done last week, but I've finally gotten a build with the analysis running which fully builds (locally at least). I'm putting it on try right now: https://treeherder.mozilla.org/#/jobs?repo=try&revision=870a8f5c9195 (watch it fail to compile somehow).

I'm certain that I broke something in the process of making the analysis happy, so I'll have to go back and fix that, then I'll have to rebase, and then I'll attach a patch.

Comment 25

[Nika Layzell [:nika] (ni? for response)]

Unfortunately because I dropped this patch for 9 months, almost all of the work I did to get it working on the codebase doesn't apply anymore >.<.

This being said, I'm increasing its priority, as I very recently made an error which would have been caught by this analysis (bug 1289900).

Comment 26

[Sylvestre Ledru [:Sylvestre]]

Michael, are you going to finish the work? Maybe Andi can help finishing the work if you want.

Comment 27

[Nika Layzell [:nika] (ni? for response)]

(In reply to Sylvestre Ledru [:sylvestre] from comment #26)
> Michael, are you going to finish the work? Maybe Andi can help finishing the
> work if you want.

It would be awesome if Andi could help out with finishing off this bug!

Andi, would you be up for taking this through to completion? I can help out if you have questions of course.

Comment 28

[Andi [:andi]]

Sure i can take it over, but right no i'm in PTO till 12th of august. I will give you a ping when i'll be back.

Comment 29

[Emilio Cobos Álvarez [:emilio]]

We talked a bit about this and I suggested something like adding an ASSERT_NO_CYCLECOLLECTABLE instead of trying to prove that the thing doesn't QI, and then requiring that all members are mentioned in the traverse impl... I could try to give something like that a shot...

Comment 30

[Nika Layzell [:nika] (ni? for response)]

Unassigning as I don't have time to work on this.