Implement BITMAP_INFO_INITIALIZER(nbits).

This allows static initialization of bitmap_info_t structures.

1 files changed, 67 insertions, 19 deletions

diff --git a/include/jemalloc/internal/bitmap.h b/include/jemalloc/internal/bitmap.h
index 36f38b59..0d456e2d 100644
--- a/include/jemalloc/internal/bitmap.h
+++ b/include/jemalloc/internal/bitmap.h
@@ -12,7 +12,7 @@ typedef unsigned long bitmap_t;
 
 /* Number of bits per group. */
 #define	LG_BITMAP_GROUP_NBITS		(LG_SIZEOF_BITMAP + 3)
-#define	BITMAP_GROUP_NBITS		(ZU(1) << LG_BITMAP_GROUP_NBITS)
+#define	BITMAP_GROUP_NBITS		(1U << LG_BITMAP_GROUP_NBITS)
 #define	BITMAP_GROUP_NBITS_MASK		(BITMAP_GROUP_NBITS-1)
 
 /*
@@ -21,12 +21,12 @@ typedef unsigned long bitmap_t;
  * use a tree instead.
  */
 #if LG_BITMAP_MAXBITS - LG_BITMAP_GROUP_NBITS > 3
-#  define USE_TREE
+#  define BITMAP_USE_TREE
 #endif
 
 /* Number of groups required to store a given number of bits. */
 #define	BITMAP_BITS2GROUPS(nbits)					\
-    ((nbits + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS)
+    (((nbits) + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS)
 
 /*
  * Number of groups required at a particular level for a given number of bits.
@@ -40,6 +40,9 @@ typedef unsigned long bitmap_t;
 #define	BITMAP_GROUPS_L3(nbits)						\
     BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(		\
 	BITMAP_BITS2GROUPS((nbits)))))
+#define	BITMAP_GROUPS_L4(nbits)						\
+    BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS(		\
+	BITMAP_BITS2GROUPS(BITMAP_BITS2GROUPS((nbits))))))
 
 /*
  * Assuming the number of levels, number of groups required for a given number
@@ -53,11 +56,13 @@ typedef unsigned long bitmap_t;
     (BITMAP_GROUPS_2_LEVEL(nbits) + BITMAP_GROUPS_L2(nbits))
 #define	BITMAP_GROUPS_4_LEVEL(nbits)					\
     (BITMAP_GROUPS_3_LEVEL(nbits) + BITMAP_GROUPS_L3(nbits))
+#define	BITMAP_GROUPS_5_LEVEL(nbits)					\
+    (BITMAP_GROUPS_4_LEVEL(nbits) + BITMAP_GROUPS_L4(nbits))
 
 /*
  * Maximum number of groups required to support LG_BITMAP_MAXBITS.
  */
-#ifdef USE_TREE
+#ifdef BITMAP_USE_TREE
 
 #if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS
 #  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS)
@@ -67,20 +72,63 @@ typedef unsigned long bitmap_t;
 #  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_3_LEVEL(BITMAP_MAXBITS)
 #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 4
 #  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_4_LEVEL(BITMAP_MAXBITS)
+#elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 5
+#  define BITMAP_GROUPS_MAX	BITMAP_GROUPS_5_LEVEL(BITMAP_MAXBITS)
 #else
 #  error "Unsupported bitmap size"
 #endif
 
-/* Maximum number of levels possible. */
-#define	BITMAP_MAX_LEVELS						\
-    (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP)				\
-    + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
+/*
+ * Maximum number of levels possible.  This could be statically computed based
+ * on LG_BITMAP_MAXBITS:
+ *
+ * #define BITMAP_MAX_LEVELS \
+ *     (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \
+ *     + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP)
+ *
+ * However, that would not allow the generic BITMAP_INFO_INITIALIZER() macro, so
+ * instead hardcode BITMAP_MAX_LEVELS to the largest number supported by the
+ * various cascading macros.  The only additional cost this incurs is some
+ * unused trailing entries in bitmap_info_t structures; the bitmaps themselves
+ * are not impacted.
+ */
+#define	BITMAP_MAX_LEVELS	5
+
+#define	BITMAP_INFO_INITIALIZER(nbits) {				\
+	/* nbits. */							\
+	nbits,								\
+	/* nlevels. */							\
+	(BITMAP_GROUPS_L0(nbits) > BITMAP_GROUPS_L1(nbits)) +		\
+	    (BITMAP_GROUPS_L1(nbits) > BITMAP_GROUPS_L2(nbits)) +	\
+	    (BITMAP_GROUPS_L2(nbits) > BITMAP_GROUPS_L3(nbits)) +	\
+	    (BITMAP_GROUPS_L3(nbits) > BITMAP_GROUPS_L4(nbits)) + 1,	\
+	/* levels. */							\
+	{								\
+		{0},							\
+		{BITMAP_GROUPS_L0(nbits)},				\
+		{BITMAP_GROUPS_L1(nbits) + BITMAP_GROUPS_L0(nbits)},	\
+		{BITMAP_GROUPS_L2(nbits) + BITMAP_GROUPS_L1(nbits) +	\
+		    BITMAP_GROUPS_L0(nbits)},				\
+		{BITMAP_GROUPS_L3(nbits) + BITMAP_GROUPS_L2(nbits) +	\
+		    BITMAP_GROUPS_L1(nbits) + BITMAP_GROUPS_L0(nbits)},	\
+		{BITMAP_GROUPS_L4(nbits) + BITMAP_GROUPS_L3(nbits) +	\
+		     BITMAP_GROUPS_L2(nbits) + BITMAP_GROUPS_L1(nbits)	\
+		     + BITMAP_GROUPS_L0(nbits)}				\
+	}								\
+}
+
+#else /* BITMAP_USE_TREE */
 
-#else /* USE_TREE */
+#define	BITMAP_GROUPS_MAX	BITMAP_BITS2GROUPS(BITMAP_MAXBITS)
 
-#define	BITMAP_GROUPS_MAX BITMAP_BITS2GROUPS(BITMAP_MAXBITS)
+#define	BITMAP_INFO_INITIALIZER(nbits) {				\
+	/* nbits. */							\
+	nbits,								\
+	/* ngroups. */							\
+	BITMAP_BITS2GROUPS(nbits)					\
+}
 
-#endif /* USE_TREE */
+#endif /* BITMAP_USE_TREE */
 
 #endif /* JEMALLOC_H_TYPES */
 /******************************************************************************/
@@ -95,7 +143,7 @@ struct bitmap_info_s {
 	/* Logical number of bits in bitmap (stored at bottom level). */
 	size_t nbits;
 
-#ifdef USE_TREE
+#ifdef BITMAP_USE_TREE
 	/* Number of levels necessary for nbits. */
 	unsigned nlevels;
 
@@ -104,10 +152,10 @@ struct bitmap_info_s {
 	 * bottom to top (e.g. the bottom level is stored in levels[0]).
 	 */
 	bitmap_level_t levels[BITMAP_MAX_LEVELS+1];
-#else /* USE_TREE */
+#else /* BITMAP_USE_TREE */
 	/* Number of groups necessary for nbits. */
 	size_t ngroups;
-#endif /* USE_TREE */
+#endif /* BITMAP_USE_TREE */
 };
 
 #endif /* JEMALLOC_H_STRUCTS */
@@ -134,7 +182,7 @@ void	bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit);
 JEMALLOC_INLINE bool
 bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo)
 {
-#ifdef USE_TREE
+#ifdef BITMAP_USE_TREE
 	size_t rgoff = binfo->levels[binfo->nlevels].group_offset - 1;
 	bitmap_t rg = bitmap[rgoff];
 	/* The bitmap is full iff the root group is 0. */
@@ -178,7 +226,7 @@ bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 	g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
 	*gp = g;
 	assert(bitmap_get(bitmap, binfo, bit));
-#ifdef USE_TREE
+#ifdef BITMAP_USE_TREE
 	/* Propagate group state transitions up the tree. */
 	if (g == 0) {
 		unsigned i;
@@ -207,7 +255,7 @@ bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo)
 
 	assert(!bitmap_full(bitmap, binfo));
 
-#ifdef USE_TREE
+#ifdef BITMAP_USE_TREE
 	i = binfo->nlevels - 1;
 	g = bitmap[binfo->levels[i].group_offset];
 	bit = ffs_lu(g) - 1;
@@ -247,7 +295,7 @@ bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 	g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK);
 	*gp = g;
 	assert(!bitmap_get(bitmap, binfo, bit));
-#ifdef USE_TREE
+#ifdef BITMAP_USE_TREE
 	/* Propagate group state transitions up the tree. */
 	if (propagate) {
 		unsigned i;
@@ -265,7 +313,7 @@ bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit)
 				break;
 		}
 	}
-#endif /* USE_TREE */
+#endif /* BITMAP_USE_TREE */
 }
 
 #endif