Closed Bug 1403444 Opened 3 years ago Closed 3 years ago

Templatize rb.h

Categories

(Core :: Memory Allocator, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla58
Tracking Status
firefox58 --- fixed

People

(Reporter: glandium, Assigned: glandium)

References

(Blocks 1 open bug)

Details

Attachments

(33 files, 30 obsolete files)

2.08 KB, text/x-python
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
59 bytes, text/x-review-board-request
njn
: review+
Details
Attached file preprocess.py
A large part of the patches I'm going to attach are essentially expanding macros without touching at the expanded code. I'm attaching the script I used here. Use with `preprocess.py macro file`. The script doesn't care about formatting, so I ran clang-format after each iteration, which is why there's a patch in the queue that runs clang-format first.

At the end of the 29 (!) patches, there's still some cleanup left to do, but I'd rather do them in a followup. This queue at least gets rid of *all* the macros in rb.h.
Note that "simplify the expanded code" usually means removing things like (this)-> after expansion.
Comment on attachment 8912541 [details]
Bug 1403444 - Remove typedefs for RedBlackTrees.

https://reviewboard.mozilla.org/r/183842/#review189126
Attachment #8912541 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912542 [details]
Bug 1403444 - Add getters and setters on RedBlackTreeNode.

https://reviewboard.mozilla.org/r/183844/#review189132

::: memory/build/rb.h:88
(Diff revision 1)
>  /* Node structure. */
>  template <typename T>
> -struct RedBlackTreeNode
> +class RedBlackTreeNode
> +{
> +  uintptr_t mLeft;
> +  uintptr_t mRightAndColor;

I feel like these would be better remaining as `T*`, because that's a better match for a pointer and a tagged pointer than `uintptr_t`. The operations on mLeft would lose a cast, those on mRight would gain a cast, but I think overall it would be slightly clearer.

Also, please add a comment on mRightAndColor indicating that its lowest bit is the color bit.
Attachment #8912542 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912543 [details]
Bug 1403444 - Make the "static" part of what the rb_wrap macro expands to..

https://reviewboard.mozilla.org/r/183846/#review189134
Attachment #8912543 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912544 [details]
Bug 1403444 - Use a fixed size for the stack space used during rb_foreach.

https://reviewboard.mozilla.org/r/183848/#review189136

::: memory/build/rb.h:771
(Diff revision 1)
>   */
>  
> -#ifdef RB_NO_C99_VARARRAYS
> -   /*
> +/*
> -    * Avoid using variable-length arrays, at the cost of using more stack space.
> + * Avoid using variable-length arrays, at the cost of using more stack space.
> -    * Size the path arrays such that they are always large enough, even if a
> + * Size the path arrays such that they are always large enough, even if a

The comment about avoiding variable-length arrays doesn't really make sense now. Please reword appropriately.

::: memory/build/rb.h:783
(Diff revision 1)
> -    * is:
> + * is:
> -    *
> + *
> -    *   (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
> + *   (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
> -    *
> + *
> -    * This works out to a maximum depth of 87 and 180 for 32- and 64-bit
> + * This works out to a maximum depth of 87 and 180 for 32- and 64-bit
> -    * systems, respectively (approximatly 348 and 1440 bytes, respectively).
> + * systems, respectively (approximatly 348 and 1440 bytes, respectively).

While you're here, "approximately" is misspelled.
Attachment #8912544 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912545 [details]
Bug 1403444 - Apply clang-format to the rb.h macros.

https://reviewboard.mozilla.org/r/183850/#review189138

::: memory/build/rb.h:844
(Diff revision 1)
> -	}								\
> -    }									\
> +      }                                                                        \
> +    }                                                                          \
> +  }                                                                            \
> +  }                                                                            \
> +  }                                                                            \
> -}
> +  }

The alignment of these closing braces is weird, but I guess all these macros will be gone by the end of the patch sequence, so it doesn't matter?
Attachment #8912545 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912546 [details]
Bug 1403444 - Abstract red-black-tree link field reference with a new macro.

https://reviewboard.mozilla.org/r/183852/#review189142
Attachment #8912546 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912547 [details]
Bug 1403444 - Trivially expand rbp_left_get.

https://reviewboard.mozilla.org/r/183854/#review189144
Attachment #8912547 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912548 [details]
Bug 1403444 - Trivially expand rbp_right_get.

https://reviewboard.mozilla.org/r/183856/#review189146
Attachment #8912548 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912549 [details]
Bug 1403444 - Trivially expand rbp_red_get.

https://reviewboard.mozilla.org/r/183858/#review189148
Attachment #8912549 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912550 [details]
Bug 1403444 - Trivially expand rbp_left_set.

https://reviewboard.mozilla.org/r/183860/#review189150
Attachment #8912550 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912552 [details]
Bug 1403444 - Trivially expand rbp_{color,red,black}_set.

https://reviewboard.mozilla.org/r/183864/#review189154

::: memory/build/rb.h:320
(Diff revision 1)
>      bool rbp_ll_red;                                                           \
>      rbp_rotate_left(a_type, a_field, (a_node), (r_node));                      \
>      rbp_ll_red = rb_node_field((a_node), a_field).IsRed();                     \
> -    rbp_color_set(a_type, a_field, (r_node), rbp_ll_red);                      \
> -    rbp_red_set(a_type, a_field, (a_node));                                    \
> +    rb_node_field((r_node), a_field)                                           \
> +      .SetColor(rbp_ll_red ? NodeColor::Red : NodeColor::Black);               \
> +    rb_node_field((a_node), a_field).SetColor(NodeColor::Red);                 \

The ternary operator comes up so often I wonder if having `SetColor(bool)` would be worthwhile. Also `SetBlack()` and `SetRed()`.
Attachment #8912552 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912553 [details]
Bug 1403444 - Replace some uses of IsRed() with Color() or IsBlack().

https://reviewboard.mozilla.org/r/183866/#review189156

Ok, so this patch at least partially reduces the need for the functions I suggested on the previous patch.
Attachment #8912553 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912554 [details]
Bug 1403444 - Move miscellaneous size related constants and macros earlier in mozjemalloc.cpp.

https://reviewboard.mozilla.org/r/183868/#review189158
Attachment #8912554 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912551 [details]
Bug 1403444 - Trivially expand rbp_right_set.

https://reviewboard.mozilla.org/r/183862/#review189160
Attachment #8912551 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912542 [details]
Bug 1403444 - Add getters and setters on RedBlackTreeNode.

https://reviewboard.mozilla.org/r/183844/#review189132

> I feel like these would be better remaining as `T*`, because that's a better match for a pointer and a tagged pointer than `uintptr_t`. The operations on mLeft would lose a cast, those on mRight would gain a cast, but I think overall it would be slightly clearer.
> 
> Also, please add a comment on mRightAndColor indicating that its lowest bit is the color bit.

> The operations on mLeft would lose a cast, those on mRight would gain a cast, but I think overall it would be slightly clearer.

Note that one operation on mRight gains two casts, and I'm not particularly convinced overall it makes things clearer. This is what this looks like after this treatment:

template <typename T>
class RedBlackTreeNode
{
  T* mLeft;
  T* mRightAndColor;

public:
  T* Left()
  {
    return mLeft;
  }

  void SetLeft(T* aValue)
  {
    mLeft = aValue;
  }

  T* Right()
  {
    return reinterpret_cast<T*>(
      reinterpret_cast<uintptr_t>(mRightAndColor) & uintptr_t(~1));
  }

  void SetRight(T* aValue)
  {
    mRightAndColor = reinterpret_cast<T*>(
      (reinterpret_cast<uintptr_t>(aValue) & uintptr_t(~1)) | Color());
  }

  NodeColor Color()
  {
    return static_cast<NodeColor>(reinterpret_cast<uintptr_t>(mRightAndColor) & 1);
  }

  bool IsRed()
  {
    return Color() == NodeColor::Red;
  }

  void SetColor(NodeColor aColor)
  {
    mRightAndColor = reinterpret_cast<T*>(
      (reinterpret_cast<uintptr_t>(mRightAndColor) & uintptr_t(~1)) | aColor);
  }
};
Comment on attachment 8912542 [details]
Bug 1403444 - Add getters and setters on RedBlackTreeNode.

https://reviewboard.mozilla.org/r/183844/#review189132

> > The operations on mLeft would lose a cast, those on mRight would gain a cast, but I think overall it would be slightly clearer.
> 
> Note that one operation on mRight gains two casts, and I'm not particularly convinced overall it makes things clearer. This is what this looks like after this treatment:
> 
> template <typename T>
> class RedBlackTreeNode
> {
>   T* mLeft;
>   T* mRightAndColor;
> 
> public:
>   T* Left()
>   {
>     return mLeft;
>   }
> 
>   void SetLeft(T* aValue)
>   {
>     mLeft = aValue;
>   }
> 
>   T* Right()
>   {
>     return reinterpret_cast<T*>(
>       reinterpret_cast<uintptr_t>(mRightAndColor) & uintptr_t(~1));
>   }
> 
>   void SetRight(T* aValue)
>   {
>     mRightAndColor = reinterpret_cast<T*>(
>       (reinterpret_cast<uintptr_t>(aValue) & uintptr_t(~1)) | Color());
>   }
> 
>   NodeColor Color()
>   {
>     return static_cast<NodeColor>(reinterpret_cast<uintptr_t>(mRightAndColor) & 1);
>   }
> 
>   bool IsRed()
>   {
>     return Color() == NodeColor::Red;
>   }
> 
>   void SetColor(NodeColor aColor)
>   {
>     mRightAndColor = reinterpret_cast<T*>(
>       (reinterpret_cast<uintptr_t>(mRightAndColor) & uintptr_t(~1)) | aColor);
>   }
> };

Come to think of it, keeping integral types would even allow to use bit fields and remove half the manual bit fiddling.
Comment on attachment 8912545 [details]
Bug 1403444 - Apply clang-format to the rb.h macros.

https://reviewboard.mozilla.org/r/183850/#review189138

> The alignment of these closing braces is weird, but I guess all these macros will be gone by the end of the patch sequence, so it doesn't matter?

> but I guess all these macros will be gone by the end of the patch sequence, so it doesn't matter?

Indeed.
Comment on attachment 8912552 [details]
Bug 1403444 - Trivially expand rbp_{color,red,black}_set.

https://reviewboard.mozilla.org/r/183864/#review189154

> The ternary operator comes up so often I wonder if having `SetColor(bool)` would be worthwhile. Also `SetBlack()` and `SetRed()`.

> The ternary operator comes up so often I wonder if having SetColor(bool) would be worthwhile. Also SetBlack() and SetRed().

As you've noted, most ternary operator uses are removed later on. At the end of the series, the remaining ones are unrelated to colors.
Attachment #8912542 - Attachment is obsolete: true
Attachment #8912543 - Attachment is obsolete: true
Attachment #8912544 - Attachment is obsolete: true
Attachment #8912545 - Attachment is obsolete: true
Attachment #8912546 - Attachment is obsolete: true
Attachment #8912547 - Attachment is obsolete: true
Attachment #8912548 - Attachment is obsolete: true
Attachment #8912549 - Attachment is obsolete: true
Attachment #8912550 - Attachment is obsolete: true
Attachment #8912551 - Attachment is obsolete: true
Attachment #8912552 - Attachment is obsolete: true
Attachment #8912553 - Attachment is obsolete: true
Attachment #8912554 - Attachment is obsolete: true
Attachment #8912555 - Attachment is obsolete: true
Attachment #8912555 - Flags: review?(n.nethercote)
Attachment #8912556 - Attachment is obsolete: true
Attachment #8912556 - Flags: review?(n.nethercote)
Attachment #8912557 - Attachment is obsolete: true
Attachment #8912557 - Flags: review?(n.nethercote)
Attachment #8912558 - Attachment is obsolete: true
Attachment #8912558 - Flags: review?(n.nethercote)
Attachment #8912559 - Attachment is obsolete: true
Attachment #8912559 - Flags: review?(n.nethercote)
Attachment #8912560 - Attachment is obsolete: true
Attachment #8912560 - Flags: review?(n.nethercote)
Attachment #8912561 - Attachment is obsolete: true
Attachment #8912561 - Flags: review?(n.nethercote)
Attachment #8912562 - Attachment is obsolete: true
Attachment #8912562 - Flags: review?(n.nethercote)
Attachment #8912563 - Attachment is obsolete: true
Attachment #8912563 - Flags: review?(n.nethercote)
Attachment #8912564 - Attachment is obsolete: true
Attachment #8912564 - Flags: review?(n.nethercote)
Attachment #8912565 - Attachment is obsolete: true
Attachment #8912565 - Flags: review?(n.nethercote)
Attachment #8912566 - Attachment is obsolete: true
Attachment #8912566 - Flags: review?(n.nethercote)
Attachment #8912567 - Attachment is obsolete: true
Attachment #8912567 - Flags: review?(n.nethercote)
Attachment #8912568 - Attachment is obsolete: true
Attachment #8912568 - Flags: review?(n.nethercote)
Attachment #8912569 - Attachment is obsolete: true
Attachment #8912569 - Flags: review?(n.nethercote)
Attachment #8912576 - Attachment is obsolete: true
Attachment #8912576 - Flags: review?(n.nethercote)
Attachment #8912577 - Attachment is obsolete: true
Attachment #8912577 - Flags: review?(n.nethercote)
Comment on attachment 8912541 [details]
Bug 1403444 - Remove typedefs for RedBlackTrees.

Sorry, I messed up with mozreview when adding one more patch to the queue :( that reset the whole queue.
Attachment #8912541 - Flags: review+ → review?(n.nethercote)
(In reply to Mike Hommey [:glandium] from comment #49)
> Come to think of it, keeping integral types would even allow to use bit
> fields and remove half the manual bit fiddling.

FWIW, this is what this would look like:

template <typename T>
class RedBlackTreeNode
{
  uintptr_t mLeft;
  uintptr_t mRight : sizeof(uintptr_t) * 8 - 1;
  NodeColor mColor : 1;

public:
  T* Left()
  {
    return reinterpret_cast<T*>(mLeft);
  }

  void SetLeft(T* aValue)
  {
    mLeft = reinterpret_cast<uintptr_t>(aValue);
  }

  T* Right()
  {
    return reinterpret_cast<T*>(mRight << 1);
  }

  void SetRight(T* aValue)
  {
    mRight = reinterpret_cast<uintptr_t>(aValue) >> 1;
  }

  NodeColor Color()
  {
    return mColor;
  }

  bool IsBlack()
  {
    return Color() == NodeColor::Black;
  }

  bool IsRed()
  {
    return Color() == NodeColor::Red;
  }

  void SetColor(NodeColor aColor)
  {
    mColor = aColor;
  }
};

Note mColor would need to be between mLeft and mRight for the current bit order to be preserved. (but only on little endian)
I'm inclined to stick with the old bit-masking approach. Seems more standard for tagged pointers, possibly because of the endianness issues.
Comment on attachment 8912541 [details]
Bug 1403444 - Remove typedefs for RedBlackTrees.

https://reviewboard.mozilla.org/r/183842/#review189440
Attachment #8912541 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912943 [details]
Bug 1403444 - Use templates for rb_node and rb_tree, and rename them.

https://reviewboard.mozilla.org/r/184266/#review189442
Attachment #8912943 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912944 [details]
Bug 1403444 - Add getters and setters on RedBlackTreeNode.

https://reviewboard.mozilla.org/r/184268/#review189444

::: memory/build/rb.h:88
(Diff revision 1)
>  /* Node structure. */
>  template <typename T>
> -struct RedBlackTreeNode
> +class RedBlackTreeNode
> +{
> +  uintptr_t mLeft;
> +  uintptr_t mRightAndColor;

Still need comments here about these fields.
Attachment #8912944 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912945 [details]
Bug 1403444 - Make the "static" part of what the rb_wrap macro expands to..

https://reviewboard.mozilla.org/r/184270/#review189446
Attachment #8912945 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912946 [details]
Bug 1403444 - Use a fixed size for the stack space used during rb_foreach.

https://reviewboard.mozilla.org/r/184272/#review189448
Attachment #8912946 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912947 [details]
Bug 1403444 - Apply clang-format to the rb.h macros.

https://reviewboard.mozilla.org/r/184274/#review189450
Attachment #8912947 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912948 [details]
Bug 1403444 - Abstract red-black-tree link field reference with a new macro.

https://reviewboard.mozilla.org/r/184276/#review189452
Attachment #8912948 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912949 [details]
Bug 1403444 - Trivially expand rbp_left_get.

https://reviewboard.mozilla.org/r/184278/#review189454
Attachment #8912949 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912950 [details]
Bug 1403444 - Trivially expand rbp_right_get.

https://reviewboard.mozilla.org/r/184280/#review189456
Attachment #8912950 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912951 [details]
Bug 1403444 - Trivially expand rbp_red_get.

https://reviewboard.mozilla.org/r/184282/#review189458
Attachment #8912951 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912952 [details]
Bug 1403444 - Trivially expand rbp_left_set.

https://reviewboard.mozilla.org/r/184284/#review189460
Attachment #8912952 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912953 [details]
Bug 1403444 - Trivially expand rbp_right_set.

https://reviewboard.mozilla.org/r/184286/#review189462
Attachment #8912953 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912954 [details]
Bug 1403444 - Trivially expand rbp_{color,red,black}_set.

https://reviewboard.mozilla.org/r/184288/#review189464
Attachment #8912954 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912955 [details]
Bug 1403444 - Replace some uses of IsRed() with Color() or IsBlack().

https://reviewboard.mozilla.org/r/184290/#review189466
Attachment #8912955 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912956 [details]
Bug 1403444 - Move miscellaneous size related constants and macros earlier in mozjemalloc.cpp.

https://reviewboard.mozilla.org/r/184292/#review189468
Attachment #8912956 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912957 [details]
Bug 1403444 - Add methods to the RedBlackTree template class, replacing rb_wrap.

https://reviewboard.mozilla.org/r/184294/#review189522

BTW, I'm making various style suggestions. It's fine to save them for later if doing them now would mess up the patch sequence.

::: memory/build/mozjemalloc.cpp:601
(Diff revision 1)
>  };
> -typedef RedBlackTree<extent_node_t> extent_tree_t;
>  
> +template<typename T>
> +int
> +CompareAddr(T* a, T* b)

'a' and 'b' don't follow the usual 'aFoo' pattern. (There are multiple examples of this below, too.)

::: memory/build/mozjemalloc.cpp:771
(Diff revision 1)
> +  {
> +    return aThis->link;
> +  }
> +};
> +
> +struct ArenaRunTreeTrait : public ArenaChunkMapLink

It's a bit weird and inconsistent that this trait class and the one just below get their GetTreeNode() method from a superclass, while all the other trait classes define them themselves. Is the use of the superclass necessary?

::: memory/build/mozjemalloc.cpp:776
(Diff revision 1)
> +struct ArenaRunTreeTrait : public ArenaChunkMapLink
> +{
> +  static inline int Compare(arena_chunk_map_t* a, arena_chunk_map_t* b)
> +  {
> +    MOZ_ASSERT(a);
> +    MOZ_ASSERT(b);

Most other Compare() functions lack these assertions. Is there a reason for the inconsistency?

::: memory/build/mozjemalloc.cpp:785
(Diff revision 1)
> +
> +struct ArenaAvailTreeTrait : public ArenaChunkMapLink
> +{
> +  static inline int Compare(arena_chunk_map_t* a, arena_chunk_map_t* b)
> +  {
> +    int ret;

Combine the declaration of `ret` with the assignment below.

::: memory/build/mozjemalloc.cpp:2044
(Diff revision 1)
>  #endif
>  }
>  
>  static void *
> -chunk_recycle(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, size_t size,
> -    size_t alignment, bool base, bool *zeroed)
> +chunk_recycle(RedBlackTree<extent_node_t, ExtentTreeSzTrait> *chunks_szad,
> +              RedBlackTree<extent_node_t, ExtentTreeTrait> *chunks_ad,

You could change these args to aFoo form. Likewise in various other functions.

::: memory/build/mozjemalloc.cpp:2212
(Diff revision 1)
>  }
>  
>  static void
> -chunk_record(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, void *chunk,
> -    size_t size, ChunkType chunk_type)
> +chunk_record(RedBlackTree<extent_node_t, ExtentTreeSzTrait> *chunks_szad,
> +             RedBlackTree<extent_node_t, ExtentTreeTrait> *chunks_ad,
> +             void *chunk, size_t size, ChunkType chunk_type)

Move the '*' to the left.

::: memory/build/rb.h:668
(Diff revision 1)
> -/*
> - * The rb_wrap() macro provides a convenient way to wrap functions around the
> - * cpp macros.  The main benefits of wrapping are that 1) repeated macro
> - * expansion can cause code bloat, especially for rb_{insert,remove)(), and
> - * 2) type, linkage, comparison functions, etc. need not be specified at every
> - * call point.
> +/* Tree structure. */
> +template<typename T, typename Trait>
> +struct RedBlackTree
> +{
> +  T* rbt_root;
> +  T rbt_nil;

mRoot and mNil?
Attachment #8912957 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912958 [details]
Bug 1403444 - Expand rb_new, rb_first, rb_last, rb_next and rb_prev.

https://reviewboard.mozilla.org/r/184296/#review189530
Attachment #8912958 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912959 [details]
Bug 1403444 - Expand rbp_node_new.

https://reviewboard.mozilla.org/r/184298/#review189532

::: memory/build/rb.h:629
(Diff revision 1)
>    void Init()
>    {
>      rbt_root = &rbt_nil;
> -    rbp_node_new(T, Trait::GetTreeNode, this, &rbt_nil);
> +    rb_node_field(&rbt_nil, Trait::GetTreeNode).SetLeft(&rbt_nil);
> +    rb_node_field(&rbt_nil, Trait::GetTreeNode).SetRight(&rbt_nil);
>      rb_node_field(&rbt_nil, Trait::GetTreeNode).SetColor(NodeColor::Black);

So the old code set it to Red and then immediately changed it to Black? +1 for the new code.
Attachment #8912959 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912960 [details]
Bug 1403444 - Trivially expand rb_node_field.

https://reviewboard.mozilla.org/r/184300/#review189536

I admit I didn't check every line of that patch.
Attachment #8912960 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912961 [details]
Bug 1403444 - Expand rbp_next and rbp_prev.

https://reviewboard.mozilla.org/r/184302/#review189538

::: memory/build/rb.h:576
(Diff revision 1)
>    T* Next(T* aNode)
>    {
>      T* ret;
> -    rbp_next(T, Trait::GetTreeNode, Trait::Compare, this, (aNode), (ret));
> +    if (Trait::GetTreeNode(aNode).Right() != &rbt_nil) {
> +      rbp_first(
> +        T, Trait::GetTreeNode, this, Trait::GetTreeNode(aNode).Right(), (ret));

Unnecessary parens around `ret`.

::: memory/build/rb.h:602
(Diff revision 1)
>    T* Prev(T* aNode)
>    {
>      T* ret;
> -    rbp_prev(T, Trait::GetTreeNode, Trait::Compare, this, (aNode), (ret));
> +    if (Trait::GetTreeNode(aNode).Left() != &rbt_nil) {
> +      rbp_last(
> +        T, Trait::GetTreeNode, this, Trait::GetTreeNode(aNode).Left(), (ret));

ditto
Attachment #8912961 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912962 [details]
Bug 1403444 - Expand rb_search and rb_nsearch.

https://reviewboard.mozilla.org/r/184304/#review189540
Attachment #8912962 - Flags: review?(n.nethercote) → review+
> Come to think of it, keeping integral types would even allow to use bit fields and remove half the manual bit fiddling.

If you leave them as integral, please add a comment explaining that they are actually a pointer and a tagged pointer, but they're stored as integers to reduce casting in the methods.
Comment on attachment 8912963 [details]
Bug 1403444 - Allow First and Last to take a start node, and use that in Next and Prev.

https://reviewboard.mozilla.org/r/184306/#review189542

::: memory/build/rb.h:517
(Diff revision 1)
>    }
>  
> -  T* First()
> +  T* First(T* aStart = nullptr)
>    {
>      T* ret;
> -    rbp_first(T, Trait::GetTreeNode, this, rbt_root, (ret));
> +    rbp_first(T, Trait::GetTreeNode, this, (aStart ? aStart : rbt_root), (ret));

Unnecessary parens around `ret`. (Probably fixable in an earlier patch.)
Attachment #8912963 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912964 [details]
Bug 1403444 - Expand rbp_first and rbp_last.

https://reviewboard.mozilla.org/r/184308/#review189544
Attachment #8912964 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912965 [details]
Bug 1403444 - Expand rb_insert.

https://reviewboard.mozilla.org/r/184310/#review189548

Holy shit!
Attachment #8912965 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912966 [details]
Bug 1403444 - Expand rb_remove.

https://reviewboard.mozilla.org/r/184312/#review189550

Whoa, that was even worse than rb_insert().
Attachment #8912966 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912967 [details]
Bug 1403444 - Replace rbp_rotate_left and rbp_rotate_right with private methods.

https://reviewboard.mozilla.org/r/184314/#review189552
Attachment #8912967 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912968 [details]
Bug 1403444 - Replace rbp_lean_left and rbp_lean_right with private methods.

https://reviewboard.mozilla.org/r/184316/#review189554
Attachment #8912968 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912969 [details]
Bug 1403444 - Replace rbp_move_red_left and rbp_move_red_right with private methods.

https://reviewboard.mozilla.org/r/184318/#review189556

I sure hope that script of yours doesn't have subtle bugs.
Attachment #8912969 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912970 [details]
Bug 1403444 - Remove rbp_f_synced.

https://reviewboard.mozilla.org/r/184320/#review189558
Attachment #8912970 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912971 [details]
Bug 1403444 - Replace the rb_foreach_* macros with a range iterator.

https://reviewboard.mozilla.org/r/184322/#review189560

::: memory/build/rb.h:621
(Diff revision 1)
>      return node;
>    }
> -};
>  
> -/*
> +  /*
> - * The iterators simulate recursion via an array of pointers that store the
> +   * The iterator simulate recursion via an array of pointers that store the

simulates

::: memory/build/rb.h:645
(Diff revision 1)
> - * is:
> +   * is:
> - *
> +   *
> - *   (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
> +   *   (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
> - *
> +   *
> - * This works out to a maximum depth of 87 and 180 for 32- and 64-bit
> +   * This works out to a maximum depth of 87 and 180 for 32- and 64-bit
> - * systems, respectively (approximatly 348 and 1440 bytes, respectively).
> +   * systems, respectively (approximatly 348 and 1440 bytes, respectively).

"approximately" is still misspelled :)
Attachment #8912971 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912972 [details]
Bug 1403444 - Add a helper class to avoid the tree traversal code having to use Trait::GetTreeNode noisily.

https://reviewboard.mozilla.org/r/184324/#review189562

Nice.

::: memory/build/rb.h:241
(Diff revision 1)
> +
> +  TreeNode* First(TreeNode* aStart)
> +  {
> +    TreeNode* ret;
> +    for (ret = aStart ? aStart : rbt_root; ret->Left() != &rbt_nil;
> +         ret = ret->Left()) {

I usually put for-loop headers on 3 lines if they don't fit on 1, but not everybody does that.
Attachment #8912972 - Flags: review?(n.nethercote) → review+
Comment on attachment 8912973 [details]
Bug 1403444 - Rename the RedBlackTree member variables.

https://reviewboard.mozilla.org/r/184326/#review189564

Nice.
Attachment #8912973 - Flags: review?(n.nethercote) → review+
Thank you for doing this. I'm sure it was a tedious slog, but the codebase will be better for it.
(In reply to Nicholas Nethercote [:njn] from comment #106)
> > +        T, Trait::GetTreeNode, this, Trait::GetTreeNode(aNode).Right(), (ret));
> 
> Unnecessary parens around `ret`.
> 
> > +        T, Trait::GetTreeNode, this, Trait::GetTreeNode(aNode).Left(), (ret));
> 
> ditto

(In reply to Nicholas Nethercote [:njn] from comment #109)
> > +    rbp_first(T, Trait::GetTreeNode, this, (aStart ? aStart : rbt_root), (ret));
> 
> Unnecessary parens around `ret`. (Probably fixable in an earlier patch.)

Note those parens all go away in another patch, so... meh.

(In reply to Nicholas Nethercote [:njn] from comment #118)
> Comment on attachment 8912972 [details]
> Bug 1403444 - Add a helper class to avoid the tree traversal code having to
> use Trait::GetTreeNode noisily.
> 
> https://reviewboard.mozilla.org/r/184324/#review189562
> 
> Nice.
> 
> ::: memory/build/rb.h:241
> (Diff revision 1)
> > +
> > +  TreeNode* First(TreeNode* aStart)
> > +  {
> > +    TreeNode* ret;
> > +    for (ret = aStart ? aStart : rbt_root; ret->Left() != &rbt_nil;
> > +         ret = ret->Left()) {
> 
> I usually put for-loop headers on 3 lines if they don't fit on 1, but not
> everybody does that.

This is the output from clang-format, fwiw.
(In reply to Nicholas Nethercote [:njn] from comment #102)
> > +struct ArenaRunTreeTrait : public ArenaChunkMapLink
> 
> It's a bit weird and inconsistent that this trait class and the one just
> below get their GetTreeNode() method from a superclass, while all the other
> trait classes define them themselves. Is the use of the superclass necessary?

Not necessary, but I like to not repeat myself. The main reason there's a GetTreeNode method in the first place is that in extent_node_t there are two link fields, but all the others only have one, and while they have different name right now because of history, I'm thinking we could make them all use the same name and then that superclass would be shared across all traits except the one for extent_node_t.
 
> ::: memory/build/mozjemalloc.cpp:776
> (Diff revision 1)
> > +struct ArenaRunTreeTrait : public ArenaChunkMapLink
> > +{
> > +  static inline int Compare(arena_chunk_map_t* a, arena_chunk_map_t* b)
> > +  {
> > +    MOZ_ASSERT(a);
> > +    MOZ_ASSERT(b);
> 
> Most other Compare() functions lack these assertions. Is there a reason for
> the inconsistency?

There's no reason besides "this is what the current code does". I've avoided any behavioral change in this patch queue.

> ::: memory/build/mozjemalloc.cpp:2044
> (Diff revision 1)
> >  #endif
> >  }
> >  
> >  static void *
> > -chunk_recycle(extent_tree_t *chunks_szad, extent_tree_t *chunks_ad, size_t size,
> > -    size_t alignment, bool base, bool *zeroed)
> > +chunk_recycle(RedBlackTree<extent_node_t, ExtentTreeSzTrait> *chunks_szad,
> > +              RedBlackTree<extent_node_t, ExtentTreeTrait> *chunks_ad,
> 
> You could change these args to aFoo form. Likewise in various other
> functions.

I wanted to avoid adding more noise to this patch. Plus, I think those arguments can actually go away.

> ::: memory/build/rb.h:668
> (Diff revision 1)
> > -/*
> > - * The rb_wrap() macro provides a convenient way to wrap functions around the
> > - * cpp macros.  The main benefits of wrapping are that 1) repeated macro
> > - * expansion can cause code bloat, especially for rb_{insert,remove)(), and
> > - * 2) type, linkage, comparison functions, etc. need not be specified at every
> > - * call point.
> > +/* Tree structure. */
> > +template<typename T, typename Trait>
> > +struct RedBlackTree
> > +{
> > +  T* rbt_root;
> > +  T rbt_nil;
> 
> mRoot and mNil?

Done in the last patch :)
Pushed by mh@glandium.org:
https://hg.mozilla.org/integration/autoland/rev/7abab00981a4
Use templates for rb_node and rb_tree, and rename them. r=njn
https://hg.mozilla.org/integration/autoland/rev/cbe9f428b8f5
Add getters and setters on RedBlackTreeNode. r=njn
https://hg.mozilla.org/integration/autoland/rev/fbefb8ef77a0
Make the "static" part of what the rb_wrap macro expands to.. r=njn
https://hg.mozilla.org/integration/autoland/rev/47be00052ea5
Use a fixed size for the stack space used during rb_foreach. r=njn
https://hg.mozilla.org/integration/autoland/rev/580a17be2513
Apply clang-format to the rb.h macros. r=njn
https://hg.mozilla.org/integration/autoland/rev/cfb67812dddd
Abstract red-black-tree link field reference with a new macro. r=njn
https://hg.mozilla.org/integration/autoland/rev/565c56054707
Trivially expand rbp_left_get. r=njn
https://hg.mozilla.org/integration/autoland/rev/0d20144aa038
Trivially expand rbp_right_get. r=njn
https://hg.mozilla.org/integration/autoland/rev/6c1c1b8d66ab
Trivially expand rbp_red_get. r=njn
https://hg.mozilla.org/integration/autoland/rev/26968aab7b2d
Trivially expand rbp_left_set. r=njn
https://hg.mozilla.org/integration/autoland/rev/a43b8b37d7d9
Trivially expand rbp_right_set. r=njn
https://hg.mozilla.org/integration/autoland/rev/8ff410c98e54
Trivially expand rbp_{color,red,black}_set. r=njn
https://hg.mozilla.org/integration/autoland/rev/f6335a2c4a31
Replace some uses of IsRed() with Color() or IsBlack(). r=njn
https://hg.mozilla.org/integration/autoland/rev/4921fe77c9e1
Move miscellaneous size related constants and macros earlier in mozjemalloc.cpp. r=njn
https://hg.mozilla.org/integration/autoland/rev/be4970676624
Add methods to the RedBlackTree template class, replacing rb_wrap. r=njn
https://hg.mozilla.org/integration/autoland/rev/7f30afe9cb7c
Expand rb_new, rb_first, rb_last, rb_next and rb_prev. r=njn
https://hg.mozilla.org/integration/autoland/rev/2251b63c2f08
Expand rbp_node_new. r=njn
https://hg.mozilla.org/integration/autoland/rev/0f46392fa6f2
Trivially expand rb_node_field. r=njn
https://hg.mozilla.org/integration/autoland/rev/abe60e0e33c6
Expand rbp_next and rbp_prev. r=njn
https://hg.mozilla.org/integration/autoland/rev/13b60a25e0af
Expand rb_search and rb_nsearch. r=njn
https://hg.mozilla.org/integration/autoland/rev/12cdddcf6f48
Allow First and Last to take a start node, and use that in Next and Prev. r=njn
https://hg.mozilla.org/integration/autoland/rev/ed366676ea67
Expand rbp_first and rbp_last. r=njn
https://hg.mozilla.org/integration/autoland/rev/1429099bea5c
Expand rb_insert. r=njn
https://hg.mozilla.org/integration/autoland/rev/65d0d8bf7a52
Expand rb_remove. r=njn
https://hg.mozilla.org/integration/autoland/rev/6ec1867b2d38
Replace rbp_rotate_left and rbp_rotate_right with private methods. r=njn
https://hg.mozilla.org/integration/autoland/rev/ccae5ad584bc
Replace rbp_lean_left and rbp_lean_right with private methods. r=njn
https://hg.mozilla.org/integration/autoland/rev/9093162201a6
Replace rbp_move_red_left and rbp_move_red_right with private methods. r=njn
https://hg.mozilla.org/integration/autoland/rev/8c09ef23038e
Remove rbp_f_synced. r=njn
https://hg.mozilla.org/integration/autoland/rev/f0aef1a9d5ac
Replace the rb_foreach_* macros with a range iterator. r=njn
https://hg.mozilla.org/integration/autoland/rev/b498ca38f5bc
Add a helper class to avoid the tree traversal code having to use Trait::GetTreeNode noisily. r=njn
https://hg.mozilla.org/integration/autoland/rev/7c81f176ea70
Rename the RedBlackTree member variables. r=njn
https://hg.mozilla.org/integration/autoland/rev/99cbce113cba
Remove typedefs for RedBlackTrees. r=njn
Blocks: 1403824
Blocks: 1403660
Comment on attachment 8912945 [details]
Bug 1403444 - Make the "static" part of what the rb_wrap macro expands to..

https://reviewboard.mozilla.org/r/184270/#review189670

Static analysis found 6 code issues in this patch. Please fix them.

            You can run this analysis locally with ./mach static-analysis check path/to/file.cpp
            If you notice a problem in this automated review, please report it here.

::: memory/build/mozjemalloc.cpp:1521
(Diff revision 1)
>  
>  	return (ret);
>  }
>  
>  /* Wrap red-black tree macros in functions. */
> -rb_wrap(static, extent_tree_szad_, extent_tree_t, extent_node_t,
> +rb_wrap(extent_tree_szad_, extent_tree_t, extent_node_t,

Warning: Do not use 'else' after 'break' [clang-tidy: readability-else-after-return]

::: memory/build/mozjemalloc.cpp:1534
(Diff revision 1)
>  
>  	return ((a_addr > b_addr) - (a_addr < b_addr));
>  }
>  
>  /* Wrap red-black tree macros in functions. */
> -rb_wrap(static, extent_tree_ad_, extent_tree_t, extent_node_t, link_ad,
> +rb_wrap(extent_tree_ad_, extent_tree_t, extent_node_t, link_ad,

Warning: Do not use 'else' after 'break' [clang-tidy: readability-else-after-return]

::: memory/build/mozjemalloc.cpp:2381
(Diff revision 1)
>  
>    return (a->mId > b->mId) - (a->mId < b->mId);
>  }
>  
>  /* Wrap red-black tree macros in functions. */
> -rb_wrap(static, arena_tree_, arena_tree_t, arena_t, mLink, arena_comp)
> +rb_wrap(arena_tree_, arena_tree_t, arena_t, mLink, arena_comp)

Warning: Do not use 'else' after 'break' [clang-tidy: readability-else-after-return]

::: memory/build/mozjemalloc.cpp:2396
(Diff revision 1)
>  
>  	return ((a_chunk > b_chunk) - (a_chunk < b_chunk));
>  }
>  
>  /* Wrap red-black tree macros in functions. */
> -rb_wrap(static, arena_chunk_tree_dirty_, arena_chunk_tree_t,
> +rb_wrap(arena_chunk_tree_dirty_, arena_chunk_tree_t,

Warning: Do not use 'else' after 'break' [clang-tidy: readability-else-after-return]

::: memory/build/mozjemalloc.cpp:2412
(Diff revision 1)
>  
>  	return ((a_mapelm > b_mapelm) - (a_mapelm < b_mapelm));
>  }
>  
>  /* Wrap red-black tree macros in functions. */
> -rb_wrap(static, arena_run_tree_, arena_run_tree_t, arena_chunk_map_t, link,
> +rb_wrap(arena_run_tree_, arena_run_tree_t, arena_chunk_map_t, link,

Warning: Do not use 'else' after 'break' [clang-tidy: readability-else-after-return]

::: memory/build/mozjemalloc.cpp:2444
(Diff revision 1)
>  
>  	return (ret);
>  }
>  
>  /* Wrap red-black tree macros in functions. */
> -rb_wrap(static, arena_avail_tree_, arena_avail_tree_t, arena_chunk_map_t, link,
> +rb_wrap(arena_avail_tree_, arena_avail_tree_t, arena_chunk_map_t, link,

Warning: Do not use 'else' after 'break' [clang-tidy: readability-else-after-return]
Apologies for the accidental drive-by review, our bot wasn't supposed to be enabled yet.

The problem it's complaining about is the one I fixed in bug 1403660. Please disregard this last review, and once you land your commits, I'll rebase my fix on top of them and land it as well.
https://hg.mozilla.org/mozilla-central/rev/7abab00981a4
https://hg.mozilla.org/mozilla-central/rev/cbe9f428b8f5
https://hg.mozilla.org/mozilla-central/rev/fbefb8ef77a0
https://hg.mozilla.org/mozilla-central/rev/47be00052ea5
https://hg.mozilla.org/mozilla-central/rev/580a17be2513
https://hg.mozilla.org/mozilla-central/rev/cfb67812dddd
https://hg.mozilla.org/mozilla-central/rev/565c56054707
https://hg.mozilla.org/mozilla-central/rev/0d20144aa038
https://hg.mozilla.org/mozilla-central/rev/6c1c1b8d66ab
https://hg.mozilla.org/mozilla-central/rev/26968aab7b2d
https://hg.mozilla.org/mozilla-central/rev/a43b8b37d7d9
https://hg.mozilla.org/mozilla-central/rev/8ff410c98e54
https://hg.mozilla.org/mozilla-central/rev/f6335a2c4a31
https://hg.mozilla.org/mozilla-central/rev/4921fe77c9e1
https://hg.mozilla.org/mozilla-central/rev/be4970676624
https://hg.mozilla.org/mozilla-central/rev/7f30afe9cb7c
https://hg.mozilla.org/mozilla-central/rev/2251b63c2f08
https://hg.mozilla.org/mozilla-central/rev/0f46392fa6f2
https://hg.mozilla.org/mozilla-central/rev/abe60e0e33c6
https://hg.mozilla.org/mozilla-central/rev/13b60a25e0af
https://hg.mozilla.org/mozilla-central/rev/12cdddcf6f48
https://hg.mozilla.org/mozilla-central/rev/ed366676ea67
https://hg.mozilla.org/mozilla-central/rev/1429099bea5c
https://hg.mozilla.org/mozilla-central/rev/65d0d8bf7a52
https://hg.mozilla.org/mozilla-central/rev/6ec1867b2d38
https://hg.mozilla.org/mozilla-central/rev/ccae5ad584bc
https://hg.mozilla.org/mozilla-central/rev/9093162201a6
https://hg.mozilla.org/mozilla-central/rev/8c09ef23038e
https://hg.mozilla.org/mozilla-central/rev/f0aef1a9d5ac
https://hg.mozilla.org/mozilla-central/rev/b498ca38f5bc
https://hg.mozilla.org/mozilla-central/rev/7c81f176ea70
https://hg.mozilla.org/mozilla-central/rev/99cbce113cba
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla58
(In reply to Jan Keromnes [:janx] from comment #159)
> Apologies for the accidental drive-by review, our bot wasn't supposed to be
> enabled yet.
> 
> The problem it's complaining about is the one I fixed in bug 1403660. Please
> disregard this last review, and once you land your commits, I'll rebase my
> fix on top of them and land it as well.

Why was it reviewing the 4th commit of a 32 commit queue that has already landed?
(In reply to Mike Hommey [:glandium] from comment #161)
> Why was it reviewing the 4th commit of a 32 commit queue that has already
> landed?

(Please use needinfo for questions like this.)

We manually ran the bot on this particular diffset while hacking on it locally (to see how it reacts to the code defects in the 4th commit) and this accidentally published a review on MozReview because we forgot to disable that feature while testing the bot. Sorry about that!
Blocks: 1411158
You need to log in before you can comment on or make changes to this bug.