Bug 1403444 - Use a fixed size for the stack space used during rb_foreach. r?njn draft
authorMike Hommey <mh+mozilla@glandium.org>
Mon, 25 Sep 2017 06:57:09 +0900
changeset 670912 3122c5f1cdec1d17d4d180a18bfffc57256ee025
parent 670911 89607ef8c9afe50e87b07b1e877cc9f545491cc1
child 670913 f7643086efb2a18859dddc80079a6df5dd25cf0e
push id81767
push userbmo:mh+mozilla@glandium.org
push dateWed, 27 Sep 2017 06:43:40 +0000
reviewersnjn
bugs1403444
milestone58.0a1
Bug 1403444 - Use a fixed size for the stack space used during rb_foreach. r?njn That stack space would matter if recursion was involved, but there isn't any, and a max of 1440 bytes temporarily allocated on the stack is not really a problem.
memory/build/mozjemalloc.cpp
memory/build/rb.h
--- a/memory/build/mozjemalloc.cpp
+++ b/memory/build/mozjemalloc.cpp
@@ -296,20 +296,16 @@ void *_mmap(void *addr, size_t length, i
 #endif
 #endif
 }
 #define mmap _mmap
 #define munmap(a, l) syscall(SYS_munmap, a, l)
 #endif
 #endif
 
-#ifdef XP_WIN
-   /* MSVC++ does not support C99 variable-length arrays. */
-#  define RB_NO_C99_VARARRAYS
-#endif
 #include "rb.h"
 
 #ifdef MOZ_DEBUG
    /* Disable inlining to make debugging easier. */
 #ifdef inline
 #undef inline
 #endif
 
--- a/memory/build/rb.h
+++ b/memory/build/rb.h
@@ -35,20 +35,18 @@
  * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  *
  ******************************************************************************
  *
  * cpp macro implementation of left-leaning red-black trees.
  *
  * Usage:
  *
- *   (Optional.)
  *   #define SIZEOF_PTR ...
  *   #define SIZEOF_PTR_2POW ...
- *   #define RB_NO_C99_VARARRAYS
  *
  *   #include <rb.h>
  *   ...
  *
  * All operations are done non-recursively.  Parent pointers are not used, and
  * color bits are stored in the least significant bit of right-child pointers,
  * thus making node linkage as compact as is possible for red-black trees.
  *
@@ -164,27 +162,16 @@ struct RedBlackTree
 /* Tree initializer. */
 #define	rb_new(a_type, a_field, a_tree) do {				\
     (a_tree)->rbt_root = &(a_tree)->rbt_nil;				\
     rbp_node_new(a_type, a_field, a_tree, &(a_tree)->rbt_nil);		\
     rbp_black_set(a_type, a_field, &(a_tree)->rbt_nil);			\
 } while (0)
 
 /* Tree operations. */
-#define	rbp_black_height(a_type, a_field, a_tree, r_height) do {	\
-    a_type *rbp_bh_t;							\
-    for (rbp_bh_t = (a_tree)->rbt_root, (r_height) = 0;			\
-      rbp_bh_t != &(a_tree)->rbt_nil;					\
-      rbp_bh_t = rbp_left_get(a_type, a_field, rbp_bh_t)) {		\
-	if (rbp_red_get(a_type, a_field, rbp_bh_t) == false) {		\
-	    (r_height)++;						\
-	}								\
-    }									\
-} while (0)
-
 #define	rbp_first(a_type, a_field, a_tree, a_root, r_node) do {		\
     for ((r_node) = (a_root);						\
       rbp_left_get(a_type, a_field, (r_node)) != &(a_tree)->rbt_nil;	\
       (r_node) = rbp_left_get(a_type, a_field, (r_node))) {		\
     }									\
 } while (0)
 
 #define	rbp_last(a_type, a_field, a_tree, a_root, r_node) do {		\
@@ -774,45 +761,35 @@ a_prefix##remove(a_tree_type *tree, a_ty
  *   }
  *
  * Note that this idiom is not advised if every iteration modifies the tree,
  * since in that case there is no algorithmic complexity improvement over a
  * series of rb_{next,prev}() calls, thus making the setup overhead wasted
  * effort.
  */
 
-#ifdef RB_NO_C99_VARARRAYS
-   /*
-    * 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
-    * tree consumes all of memory.  Since each node must contain a minimum of
-    * two pointers, there can never be more nodes than:
-    *
-    *   1 << ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1))
-    *
-    * Since the depth of a tree is limited to 3*lg(#nodes), the maximum depth
-    * is:
-    *
-    *   (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
-    *
-    * This works out to a maximum depth of 87 and 180 for 32- and 64-bit
-    * systems, respectively (approximatly 348 and 1440 bytes, respectively).
-    */
-#  define rbp_compute_f_height(a_type, a_field, a_tree)
-#  define rbp_f_height	(3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
-#else
-#  define rbp_compute_f_height(a_type, a_field, a_tree)			\
-    /* Compute the maximum possible tree depth (3X the black height). */\
-    unsigned rbp_f_height;						\
-    rbp_black_height(a_type, a_field, a_tree, rbp_f_height);		\
-    rbp_f_height *= 3;
-#endif
+/*
+ * 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
+ * tree consumes all of memory.  Since each node must contain a minimum of
+ * two pointers, there can never be more nodes than:
+ *
+ *   1 << ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1))
+ *
+ * Since the depth of a tree is limited to 3*lg(#nodes), the maximum depth
+ * is:
+ *
+ *   (3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
+ *
+ * This works out to a maximum depth of 87 and 180 for 32- and 64-bit
+ * systems, respectively (approximatly 348 and 1440 bytes, respectively).
+ */
+#define rbp_f_height	(3 * ((SIZEOF_PTR<<3) - (SIZEOF_PTR_2POW+1)))
 
 #define	rb_foreach_begin(a_type, a_field, a_tree, a_var) {		\
-    rbp_compute_f_height(a_type, a_field, a_tree)			\
     {									\
 	/* Initialize the path to contain the left spine.             */\
 	a_type *rbp_f_path[rbp_f_height];				\
 	a_type *rbp_f_node;						\
 	bool rbp_f_synced = false;					\
 	unsigned rbp_f_depth = 0;					\
 	if ((a_tree)->rbt_root != &(a_tree)->rbt_nil) {			\
 	    rbp_f_path[rbp_f_depth] = (a_tree)->rbt_root;		\