1439470 - Crash in RedBlackTree<T>::Remove at rb.h:520, rb.h:462

Status: RESOLVED FIXED

(Core :: Memory Allocator, enhancement)

Description

[Mike Hommey [:glandium]]

There are other classes of crashes in RedBlackTree<T>::Remove, which I'm sure existed before bug 1412722 (most of them are double-free of huge allocations), but there are at least two kinds that I could find that are related to something I spotted while translating the current rb.h code to rust:
https://crash-stats.mozilla.com/report/index/26ceeaa3-db9f-4641-a46b-dc68d0180220
https://crash-stats.mozilla.com/report/index/c59942ce-cede-4d8b-8e1a-b25b50180219

Those are null derefs caused by the absence of the sentinel.

Comment 1

[Mike Hommey [:glandium]]

Attachment: Bug 1439470 - Turn TreeNode into a smart pointer-like type.

This will allow the upcoming changes to add some safety back to the code
after bug 1412722.

Review commit: https://reviewboard.mozilla.org/r/221518/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/221518/

Comment 2

[Mike Hommey [:glandium]]

Attachment: Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

The code before bug 1412722 benefitted from the sentinel being an actual
node object, and some code paths ended up checking its color (always
black) or getting its right and left node, that always returned to the
sentinel.

When TreeNode currently contains a nullptr, all those lead to a null
deref if the calling code is not doing the right checks, which happens
to be the case in at least some places. Instead of relying on the
callers doing the right thing, make the TreeNode do the right thing when
it contains a nullptr, effectively acting as the sentinel in that case.

We additionally ensure that nothing in the calling code will be trying
to change the color or left/right pointers on the sentinel, which is an
extra safe net compared to the code before bug 1412722.

Review commit: https://reviewboard.mozilla.org/r/221520/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/221520/

Comment 3

[Mike Hommey [:glandium]]

Attachment: Bug 1439470 - Remove some now unnecessary checks.

Since TreeNode::{Left,Right,Color} is always a valid call to make, we
don't need to check if for nullity before calling those functions.

This effectively kind of reverts some parts of bug 1412722.

Review commit: https://reviewboard.mozilla.org/r/221522/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/221522/

Comment 4

[Mike Hommey [:glandium]]

(In reply to Mike Hommey [:glandium] from comment #0)
> There are other classes of crashes in RedBlackTree<T>::Remove, which I'm
> sure existed before bug 1412722 (most of them are double-free of huge
> allocations)

I failed to mention: those are bug 1405062.

> We additionally ensure that nothing in the calling code will be trying
> to change the color or left/right pointers on the sentinel, which is an
> extra safe net compared to the code before bug 1412722.

Another advantage of this change is that it should separate those crash signatures from those related to double-free, although I'm also going to file another bug to make those separate too.

Comment 5

[Code Review Bot [:reviewbot]]

Comment on attachment 8952276 [details]
Bug 1439470 - Turn TreeNode into a smart pointer-like type.

https://reviewboard.mozilla.org/r/221518/#review227314


Code analysis found 1 defect in this patch:
 - 1 defect found by clang-tidy

You can run this analysis locally with:
 - `./mach static-analysis check path/to/file.cpp` (C/C++)


If you see a problem in this automated review, please report it here: http://bit.ly/2y9N9Vx


::: memory/build/rb.h:194
(Diff revision 1)
> -      Trait::GetTreeNode(this).SetColor(aColor);
> +      Trait::GetTreeNode(mNode).SetColor(aColor);
>      }
> +
> +    T* Get() { return mNode; }
> +
> +    operator bool() { return mNode; }

Error: Bad implicit conversion operator for 'treenode' [clang-tidy: mozilla-explicit-operator-bool]

Comment 6

[Mike Hommey [:glandium]]

Comment on attachment 8952276 [details]
Bug 1439470 - Turn TreeNode into a smart pointer-like type.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221518/diff/1-2/

Comment 7

[Mike Hommey [:glandium]]

Comment on attachment 8952277 [details]
Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221520/diff/1-2/

Comment 8

[Mike Hommey [:glandium]]

Comment on attachment 8952278 [details]
Bug 1439470 - Remove some now unnecessary checks.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221522/diff/1-2/

Comment 9

[Nicholas Nethercote [inactive]]

Comment on attachment 8952276 [details]
Bug 1439470 - Turn TreeNode into a smart pointer-like type.

https://reviewboard.mozilla.org/r/221518/#review227326

::: memory/build/rb.h:194
(Diff revision 2)
> -      Trait::GetTreeNode(this).SetColor(aColor);
> +      Trait::GetTreeNode(mNode).SetColor(aColor);
>      }
> +
> +    T* Get() { return mNode; }
> +
> +    MOZ_IMPLICIT operator bool() { return mNode; }

`return !!mNode` is clearer?

Comment 10

[Nicholas Nethercote [inactive]]

Comment on attachment 8952277 [details]
Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

https://reviewboard.mozilla.org/r/221520/#review227328

::: memory/build/rb.h:192
(Diff revision 2)
>      }
>  
> -    NodeColor Color() { return Trait::GetTreeNode(mNode).Color(); }
> +    NodeColor Color()
> +    {
> +      return mNode ? Trait::GetTreeNode(mNode).Color() : NodeColor::Black;
> +    }

I don't see any comments in rb.h about sentinels. It feels like there should be some...

Comment 11

[Nicholas Nethercote [inactive]]

Comment on attachment 8952277 [details]
Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

https://reviewboard.mozilla.org/r/221520/#review227332

::: memory/build/rb.h:167
(Diff revision 2)
>      {
>        mNode = aOther.mNode;
>        return *this;
>      }
>  
> -    TreeNode Left() { return TreeNode(Trait::GetTreeNode(mNode).Left()); }
> +    TreeNode Left()

Comments about how Left() and Right() work would probably also be useful.

Comment 12

[Nicholas Nethercote [inactive]]

Comment on attachment 8952278 [details]
Bug 1439470 - Remove some now unnecessary checks.

https://reviewboard.mozilla.org/r/221522/#review227330

::: commit-message-17af0:1
(Diff revision 2)
> +Bug 1439470 - Remove some not unnecessary checks. r?njn

Remove the "not"?

Comment 13

[Mike Hommey [:glandium]]

(In reply to Nicholas Nethercote [:njn] from comment #12)
> Comment on attachment 8952278 [details]
> Bug 1439470 - Remove some not unnecessary checks.
> 
> https://reviewboard.mozilla.org/r/221522/#review227330
> 
> ::: commit-message-17af0:1
> (Diff revision 2)
> > +Bug 1439470 - Remove some not unnecessary checks. r?njn
> 
> Remove the "not"?

Hah, it was meant to be spelled "now".

Comment 14

[Mike Hommey [:glandium]]

Comment on attachment 8952276 [details]
Bug 1439470 - Turn TreeNode into a smart pointer-like type.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221518/diff/2-3/

Comment 15

[Mike Hommey [:glandium]]

Comment on attachment 8952277 [details]
Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221520/diff/2-3/

Comment 16

[Mike Hommey [:glandium]]

Comment on attachment 8952278 [details]
Bug 1439470 - Remove some now unnecessary checks.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221522/diff/2-3/

Comment 17

[Mike Hommey [:glandium]]

Comment on attachment 8952277 [details]
Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

Does this satisfy your comments?

Comment 18

[Nicholas Nethercote [inactive]]

Comment on attachment 8952277 [details]
Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

https://reviewboard.mozilla.org/r/221520/#review227342

Looks good, thank you.

Comment 19

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/f95559ae3134
Turn TreeNode into a smart pointer-like type. r=njn
https://hg.mozilla.org/integration/autoland/rev/cf9d00862149
Turn TreeNode(nullptr) into a "virtual" sentinel. r=njn
https://hg.mozilla.org/integration/autoland/rev/c43ee00c3e6b
Remove some now unnecessary checks. r=njn

Comment 20

[Andreea Pavel [:apavel]]

Backed out for failing automation.py 

Push that caused the failures: https://treeherder.mozilla.org/#/jobs?repo=autoland&revision=c43ee00c3e6b611b21f6a51db79f5f86df110e91

Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=163133604&repo=autoland&lineNumber=6924

Backout: https://hg.mozilla.org/integration/autoland/rev/be033090d62ad73cb15da9993f855c91c8bdc78c

Comment 21

[Mike Hommey [:glandium]]

Thank you GCC for creating stupid code for constexpr constructors:

0000000000406170 <_GLOBAL__sub_I_Unified_cpp_memory_build0.cpp>:
  406170:       55                      push   %rbp
  406171:       48 c7 05 fc e4 22 00    movq   $0x0,0x22e4fc(%rip)        # 634678 <_ZL7gArenas+0x38>
  406178:       00 00 00 00 
  40617c:       48 c7 05 f9 e4 22 00    movq   $0x0,0x22e4f9(%rip)        # 634680 <_ZL7gArenas+0x40>
  406183:       00 00 00 00 
  406187:       48 89 e5                mov    %rsp,%rbp
  40618a:       5d                      pop    %rbp
  40618b:       c3                      retq   
  40618c:       0f 1f 40 00             nopl   0x0(%rax)

Best part? _ZL7gArenas is in .bss:
0000000000634640 l     O .bss	0000000000000048              _ZL7gArenas

The funny part? The static initializer above runs *after* malloc_init_hard, so those movq's overwrite gArenas.mArenas.mRoot, which, at that time, contains mDefaultArena.

So when iterating the arenas in the atfork handler after a fork(), the default arena is not forcefully unlocked, and if the default arena lock happens to be held before the fork, the child process ends up dead-locked when something else tries to get the default arena lock.

I thought adding a constexpr (non-default) constructor on RedBlackTree might help, but it doesn't. Removing the constexpr constructor on TreeNode doesn't work either because of the other constructor that takes a T* that needs to exist, so I'm afraid the only workaround to GCC's stupidity here is to turn mRoot into a T*.

Comment 22

[Mike Hommey [:glandium]]

Adding a constexpr constructor to RedBlackTree *and* ArenaCollection makes the static initializer go away.

Comment 23

[Mike Hommey [:glandium]]

Well, MSVC can also do funny things with constexpr:
https://bugs.chromium.org/p/chromium/issues/detail?id=660967

Comment 24

[Mike Hommey [:glandium]]

Comment on attachment 8952276 [details]
Bug 1439470 - Turn TreeNode into a smart pointer-like type.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221518/diff/3-4/

Comment 25

[Mike Hommey [:glandium]]

Comment on attachment 8952277 [details]
Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221520/diff/3-4/

Comment 26

[Mike Hommey [:glandium]]

Comment on attachment 8952278 [details]
Bug 1439470 - Remove some now unnecessary checks.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221522/diff/3-4/

Comment 27

[Nicholas Nethercote [inactive]]

Comment on attachment 8952276 [details]
Bug 1439470 - Turn TreeNode into a smart pointer-like type.

https://reviewboard.mozilla.org/r/221518/#review228104

::: memory/build/rb.h:204
(Diff revisions 2 - 4)
>      T* mNode;
>    };
>  
>  private:
> -  TreeNode mRoot;
> +  // Ideally we'd use a TreeNode for mRoot, but we need RedBlackTree to stay
> +  // a POD to avoid a static initializer for gArenas.

"a POD type"?

Comment 28

[Mike Hommey [:glandium]]

Comment on attachment 8952276 [details]
Bug 1439470 - Turn TreeNode into a smart pointer-like type.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221518/diff/4-5/

Comment 29

[Mike Hommey [:glandium]]

Comment on attachment 8952277 [details]
Bug 1439470 - Turn TreeNode(nullptr) into a "virtual" sentinel.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221520/diff/4-5/

Comment 30

[Mike Hommey [:glandium]]

Comment on attachment 8952278 [details]
Bug 1439470 - Remove some now unnecessary checks.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/221522/diff/4-5/

Comment 31

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/f56735818e28
Turn TreeNode into a smart pointer-like type. r=njn
https://hg.mozilla.org/integration/autoland/rev/31f9d7d3f703
Turn TreeNode(nullptr) into a "virtual" sentinel. r=njn
https://hg.mozilla.org/integration/autoland/rev/9665d7248cc5
Remove some now unnecessary checks. r=njn

Comment 32

[Dorel Luca [:dluca]]

https://hg.mozilla.org/mozilla-central/rev/f56735818e28
https://hg.mozilla.org/mozilla-central/rev/31f9d7d3f703
https://hg.mozilla.org/mozilla-central/rev/9665d7248cc5