Move arena_slab_data_t's nfree into extent_t's e_bits.

Compact extent_t to 128 bytes on 64-bit systems by moving
arena_slab_data_t's nfree into extent_t's e_bits.

Cacheline-align extent_t structures so that they always cross the
minimum number of cacheline boundaries.

Re-order extent_t fields such that all fields except the slab bitmap
(and overlaid heap profiling context pointer) are in the first
cacheline.

This resolves #461.

6 files changed, 86 insertions, 43 deletions

diff --git a/include/jemalloc/internal/arena_structs_a.h b/include/jemalloc/internal/arena_structs_a.h
index ed265b2..07013a0 100644
--- a/include/jemalloc/internal/arena_structs_a.h
+++ b/include/jemalloc/internal/arena_structs_a.h
@@ -2,9 +2,6 @@
 #define JEMALLOC_INTERNAL_ARENA_STRUCTS_A_H
 
 struct arena_slab_data_s {
-	/* Number of free regions in slab. */
-	unsigned	nfree;
-
 	/* Per region allocated/deallocated bitmap. */
 	bitmap_t	bitmap[BITMAP_GROUPS_MAX];
 };
diff --git a/include/jemalloc/internal/extent_inlines.h b/include/jemalloc/internal/extent_inlines.h
index 22229b5..99fa67c 100644
--- a/include/jemalloc/internal/extent_inlines.h
+++ b/include/jemalloc/internal/extent_inlines.h
@@ -11,6 +11,7 @@ extent_state_t extent_state_get(const extent_t *extent);
 bool extent_zeroed_get(const extent_t *extent);
 bool extent_committed_get(const extent_t *extent);
 bool extent_slab_get(const extent_t *extent);
+unsigned extent_nfree_get(const extent_t *extent);
 void *extent_base_get(const extent_t *extent);
 void *extent_addr_get(const extent_t *extent);
 size_t extent_size_get(const extent_t *extent);
@@ -25,6 +26,9 @@ void extent_addr_set(extent_t *extent, void *addr);
 void extent_addr_randomize(tsdn_t *tsdn, extent_t *extent, size_t alignment);
 void extent_size_set(extent_t *extent, size_t size);
 void extent_szind_set(extent_t *extent, szind_t szind);
+void extent_nfree_set(extent_t *extent, unsigned nfree);
+void extent_nfree_inc(extent_t *extent);
+void extent_nfree_dec(extent_t *extent);
 void extent_sn_set(extent_t *extent, size_t sn);
 void extent_state_set(extent_t *extent, extent_state_t state);
 void extent_zeroed_set(extent_t *extent, bool zeroed);
@@ -112,6 +116,13 @@ extent_slab_get(const extent_t *extent) {
 	    EXTENT_BITS_SLAB_SHIFT);
 }
 
+JEMALLOC_INLINE unsigned
+extent_nfree_get(const extent_t *extent) {
+	assert(extent_slab_get(extent));
+	return (unsigned)((extent->e_bits & EXTENT_BITS_NFREE_MASK) >>
+	    EXTENT_BITS_NFREE_SHIFT);
+}
+
 JEMALLOC_INLINE void *
 extent_base_get(const extent_t *extent) {
 	assert(extent->e_addr == PAGE_ADDR2BASE(extent->e_addr) ||
@@ -211,6 +222,25 @@ extent_szind_set(extent_t *extent, szind_t szind) {
 }
 
 JEMALLOC_INLINE void
+extent_nfree_set(extent_t *extent, unsigned nfree) {
+	assert(extent_slab_get(extent));
+	extent->e_bits = (extent->e_bits & ~EXTENT_BITS_NFREE_MASK) |
+	    ((uint64_t)nfree << EXTENT_BITS_NFREE_SHIFT);
+}
+
+JEMALLOC_INLINE void
+extent_nfree_inc(extent_t *extent) {
+	assert(extent_slab_get(extent));
+	extent->e_bits += ((uint64_t)1U << EXTENT_BITS_NFREE_SHIFT);
+}
+
+JEMALLOC_INLINE void
+extent_nfree_dec(extent_t *extent) {
+	assert(extent_slab_get(extent));
+	extent->e_bits -= ((uint64_t)1U << EXTENT_BITS_NFREE_SHIFT);
+}
+
+JEMALLOC_INLINE void
 extent_sn_set(extent_t *extent, size_t sn) {
 	extent->e_bits = (extent->e_bits & ~EXTENT_BITS_SN_MASK) |
 	    ((uint64_t)sn << EXTENT_BITS_SN_SHIFT);
@@ -260,10 +290,10 @@ extent_init(extent_t *extent, arena_t *arena, void *addr, size_t size,
 	extent_state_set(extent, state);
 	extent_zeroed_set(extent, zeroed);
 	extent_committed_set(extent, committed);
+	ql_elm_new(extent, ql_link);
 	if (config_prof) {
 		extent_prof_tctx_set(extent, NULL);
 	}
-	ql_elm_new(extent, ql_link);
 }
 
 JEMALLOC_INLINE void
diff --git a/include/jemalloc/internal/extent_structs.h b/include/jemalloc/internal/extent_structs.h
index ddc0408..1527acb 100644
--- a/include/jemalloc/internal/extent_structs.h
+++ b/include/jemalloc/internal/extent_structs.h
@@ -20,8 +20,9 @@ struct extent_s {
 	 * t: state
 	 * i: szind
 	 * n: sn
+	 * f: nfree
 	 *
-	 * nnnnnnnn ... nnnnnnni iiiiiiit tzcbaaaa aaaaaaaa
+	 * nnnnnnnn ... nnnnnfff fffffffi iiiiiiit tzcbaaaa aaaaaaaa
 	 *
 	 * arena_ind: Arena from which this extent came, or all 1 bits if
 	 *            unassociated.
@@ -47,6 +48,8 @@ struct extent_s {
 	 *        even for non-slabs, either due to large_pad or promotion of
 	 *        sampled small regions.
 	 *
+	 * nfree: Number of free regions in slab.
+	 *
 	 * sn: Serial number (potentially non-unique).
 	 *
 	 *     Serial numbers may wrap around if JEMALLOC_MUNMAP is defined, but
@@ -61,26 +64,35 @@ struct extent_s {
 	uint64_t		e_bits;
 #define EXTENT_BITS_ARENA_SHIFT		0
 #define EXTENT_BITS_ARENA_MASK \
-    (((1U << MALLOCX_ARENA_BITS) - 1) << EXTENT_BITS_ARENA_SHIFT)
+    (((uint64_t)(1U << MALLOCX_ARENA_BITS) - 1) << EXTENT_BITS_ARENA_SHIFT)
 
 #define EXTENT_BITS_SLAB_SHIFT		MALLOCX_ARENA_BITS
-#define EXTENT_BITS_SLAB_MASK		(0x1U << EXTENT_BITS_SLAB_SHIFT)
+#define EXTENT_BITS_SLAB_MASK \
+    ((uint64_t)0x1U << EXTENT_BITS_SLAB_SHIFT)
 
 #define EXTENT_BITS_COMMITTED_SHIFT	(MALLOCX_ARENA_BITS + 1)
-#define EXTENT_BITS_COMMITTED_MASK	(0x1U << EXTENT_BITS_COMMITTED_SHIFT)
+#define EXTENT_BITS_COMMITTED_MASK \
+    ((uint64_t)0x1U << EXTENT_BITS_COMMITTED_SHIFT)
 
 #define EXTENT_BITS_ZEROED_SHIFT	(MALLOCX_ARENA_BITS + 2)
-#define EXTENT_BITS_ZEROED_MASK		(0x1U << EXTENT_BITS_ZEROED_SHIFT)
+#define EXTENT_BITS_ZEROED_MASK \
+    ((uint64_t)0x1U << EXTENT_BITS_ZEROED_SHIFT)
 
 #define EXTENT_BITS_STATE_SHIFT		(MALLOCX_ARENA_BITS + 3)
-#define EXTENT_BITS_STATE_MASK		(0x3U << EXTENT_BITS_STATE_SHIFT)
+#define EXTENT_BITS_STATE_MASK \
+    ((uint64_t)0x3U << EXTENT_BITS_STATE_SHIFT)
 
 #define EXTENT_BITS_SZIND_SHIFT		(MALLOCX_ARENA_BITS + 5)
 #define EXTENT_BITS_SZIND_MASK \
-    (((1U << LG_CEIL_NSIZES) - 1) << EXTENT_BITS_SZIND_SHIFT)
+    (((uint64_t)(1U << LG_CEIL_NSIZES) - 1) << EXTENT_BITS_SZIND_SHIFT)
 
-#define EXTENT_BITS_SN_SHIFT \
+#define EXTENT_BITS_NFREE_SHIFT \
     (MALLOCX_ARENA_BITS + 5 + LG_CEIL_NSIZES)
+#define EXTENT_BITS_NFREE_MASK \
+    ((uint64_t)((1U << (LG_SLAB_MAXREGS + 1)) - 1) << EXTENT_BITS_NFREE_SHIFT)
+
+#define EXTENT_BITS_SN_SHIFT \
+    (MALLOCX_ARENA_BITS + 5 + LG_CEIL_NSIZES + (LG_SLAB_MAXREGS + 1))
 #define EXTENT_BITS_SN_MASK		(UINT64_MAX << EXTENT_BITS_SN_SHIFT)
 
 	/* Pointer to the extent that this structure is responsible for. */
@@ -89,17 +101,6 @@ struct extent_s {
 	/* Extent size. */
 	size_t			e_size;
 
-	union {
-		/* Small region slab metadata. */
-		arena_slab_data_t	e_slab_data;
-
-		/* Profile counters, used for large objects. */
-		union {
-			void		*e_prof_tctx_pun;
-			prof_tctx_t	*e_prof_tctx;
-		};
-	};
-
 	/*
 	 * List linkage, used by a variety of lists:
 	 * - arena_bin_t's slabs_full
@@ -112,6 +113,17 @@ struct extent_s {
 
 	/* Linkage for per size class sn/address-ordered heaps. */
 	phn(extent_t)		ph_link;
+
+	union {
+		/* Small region slab metadata. */
+		arena_slab_data_t	e_slab_data;
+
+		/* Profile counters, used for large objects. */
+		union {
+			void		*e_prof_tctx_pun;
+			prof_tctx_t	*e_prof_tctx;
+		};
+	};
 };
 typedef ql_head(extent_t) extent_list_t;
 typedef ph(extent_t) extent_heap_t;
diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt
index 64151c1..5d03f5d 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -175,6 +175,10 @@ extent_list_last
 extent_list_remove
 extent_list_replace
 extent_merge_wrapper
+extent_nfree_dec
+extent_nfree_get
+extent_nfree_inc
+extent_nfree_set
 extent_past_get
 extent_prof_tctx_get
 extent_prof_tctx_set
diff --git a/src/arena.c b/src/arena.c
index b0913c3..b8ef473 100644
--- a/src/arena.c
+++ b/src/arena.c
@@ -361,13 +361,13 @@ arena_slab_reg_alloc(tsdn_t *tsdn, extent_t *slab,
 	arena_slab_data_t *slab_data = extent_slab_data_get(slab);
 	size_t regind;
 
-	assert(slab_data->nfree > 0);
+	assert(extent_nfree_get(slab) > 0);
 	assert(!bitmap_full(slab_data->bitmap, &bin_info->bitmap_info));
 
 	regind = bitmap_sfu(slab_data->bitmap, &bin_info->bitmap_info);
 	ret = (void *)((uintptr_t)extent_addr_get(slab) +
 	    (uintptr_t)(bin_info->reg_size * regind));
-	slab_data->nfree--;
+	extent_nfree_dec(slab);
 	return ret;
 }
 
@@ -416,12 +416,12 @@ arena_slab_reg_dalloc(tsdn_t *tsdn, extent_t *slab,
 	const arena_bin_info_t *bin_info = &arena_bin_info[binind];
 	size_t regind = arena_slab_regind(slab, binind, ptr);
 
-	assert(slab_data->nfree < bin_info->nregs);
+	assert(extent_nfree_get(slab) < bin_info->nregs);
 	/* Freeing an unallocated pointer can cause assertion failure. */
 	assert(bitmap_get(slab_data->bitmap, &bin_info->bitmap_info, regind));
 
 	bitmap_unset(slab_data->bitmap, &bin_info->bitmap_info, regind);
-	slab_data->nfree++;
+	extent_nfree_inc(slab);
 }
 
 static void
@@ -999,7 +999,7 @@ arena_slab_dalloc(tsdn_t *tsdn, arena_t *arena, extent_t *slab) {
 
 static void
 arena_bin_slabs_nonfull_insert(arena_bin_t *bin, extent_t *slab) {
-	assert(extent_slab_data_get(slab)->nfree > 0);
+	assert(extent_nfree_get(slab) > 0);
 	extent_heap_insert(&bin->slabs_nonfull, slab);
 }
 
@@ -1022,7 +1022,7 @@ arena_bin_slabs_nonfull_tryget(arena_bin_t *bin) {
 
 static void
 arena_bin_slabs_full_insert(arena_bin_t *bin, extent_t *slab) {
-	assert(extent_slab_data_get(slab)->nfree == 0);
+	assert(extent_nfree_get(slab) == 0);
 	extent_list_append(&bin->slabs_full, slab);
 }
 
@@ -1209,7 +1209,7 @@ arena_slab_alloc(tsdn_t *tsdn, arena_t *arena, szind_t binind,
 
 	/* Initialize slab internals. */
 	arena_slab_data_t *slab_data = extent_slab_data_get(slab);
-	slab_data->nfree = bin_info->nregs;
+	extent_nfree_set(slab, bin_info->nregs);
 	bitmap_init(slab_data->bitmap, &bin_info->bitmap_info, false);
 
 	arena_nactive_add(arena, extent_size_get(slab) >> LG_PAGE);
@@ -1277,7 +1277,7 @@ arena_bin_malloc_hard(tsdn_t *tsdn, arena_t *arena, arena_bin_t *bin,
 		 * Another thread updated slabcur while this one ran without the
 		 * bin lock in arena_bin_nonfull_slab_get().
 		 */
-		if (extent_slab_data_get(bin->slabcur)->nfree > 0) {
+		if (extent_nfree_get(bin->slabcur) > 0) {
 			void *ret = arena_slab_reg_alloc(tsdn, bin->slabcur,
 			    bin_info);
 			if (slab != NULL) {
@@ -1290,8 +1290,7 @@ arena_bin_malloc_hard(tsdn_t *tsdn, arena_t *arena, arena_bin_t *bin,
 				 * arena_bin_lower_slab() must be called, as if
 				 * a region were just deallocated from the slab.
 				 */
-				if (extent_slab_data_get(slab)->nfree ==
-				    bin_info->nregs) {
+				if (extent_nfree_get(slab) == bin_info->nregs) {
 					arena_dalloc_bin_slab(tsdn, arena, slab,
 					    bin);
 				} else {
@@ -1311,7 +1310,7 @@ arena_bin_malloc_hard(tsdn_t *tsdn, arena_t *arena, arena_bin_t *bin,
 	}
 	bin->slabcur = slab;
 
-	assert(extent_slab_data_get(bin->slabcur)->nfree > 0);
+	assert(extent_nfree_get(bin->slabcur) > 0);
 
 	return arena_slab_reg_alloc(tsdn, slab, bin_info);
 }
@@ -1333,8 +1332,8 @@ arena_tcache_fill_small(tsdn_t *tsdn, arena_t *arena, tcache_bin_t *tbin,
 	    tbin->lg_fill_div); i < nfill; i++) {
 		extent_t *slab;
 		void *ptr;
-		if ((slab = bin->slabcur) != NULL &&
-		    extent_slab_data_get(slab)->nfree > 0) {
+		if ((slab = bin->slabcur) != NULL && extent_nfree_get(slab) >
+		    0) {
 			ptr = arena_slab_reg_alloc(tsdn, slab,
 			    &arena_bin_info[binind]);
 		} else {
@@ -1405,8 +1404,7 @@ arena_malloc_small(tsdn_t *tsdn, arena_t *arena, szind_t binind, bool zero) {
 	usize = index2size(binind);
 
 	malloc_mutex_lock(tsdn, &bin->lock);
-	if ((slab = bin->slabcur) != NULL && extent_slab_data_get(slab)->nfree >
-	    0) {
+	if ((slab = bin->slabcur) != NULL && extent_nfree_get(slab) > 0) {
 		ret = arena_slab_reg_alloc(tsdn, slab, &arena_bin_info[binind]);
 	} else {
 		ret = arena_bin_malloc_hard(tsdn, arena, bin, binind);
@@ -1582,7 +1580,7 @@ arena_dalloc_bin_slab(tsdn_t *tsdn, arena_t *arena, extent_t *slab,
 static void
 arena_bin_lower_slab(tsdn_t *tsdn, arena_t *arena, extent_t *slab,
     arena_bin_t *bin) {
-	assert(extent_slab_data_get(slab)->nfree > 0);
+	assert(extent_nfree_get(slab) > 0);
 
 	/*
 	 * Make sure that if bin->slabcur is non-NULL, it refers to the
@@ -1592,7 +1590,7 @@ arena_bin_lower_slab(tsdn_t *tsdn, arena_t *arena, extent_t *slab,
 	 */
 	if (bin->slabcur != NULL && extent_snad_comp(bin->slabcur, slab) > 0) {
 		/* Switch slabcur. */
-		if (extent_slab_data_get(bin->slabcur)->nfree > 0) {
+		if (extent_nfree_get(bin->slabcur) > 0) {
 			arena_bin_slabs_nonfull_insert(bin, bin->slabcur);
 		} else {
 			arena_bin_slabs_full_insert(bin, bin->slabcur);
@@ -1619,10 +1617,11 @@ arena_dalloc_bin_locked_impl(tsdn_t *tsdn, arena_t *arena, extent_t *slab,
 	}
 
 	arena_slab_reg_dalloc(tsdn, slab, slab_data, ptr);
-	if (slab_data->nfree == bin_info->nregs) {
+	unsigned nfree = extent_nfree_get(slab);
+	if (nfree == bin_info->nregs) {
 		arena_dissociate_bin_slab(slab, bin);
 		arena_dalloc_bin_slab(tsdn, arena, slab, bin);
-	} else if (slab_data->nfree == 1 && slab != bin->slabcur) {
+	} else if (nfree == 1 && slab != bin->slabcur) {
 		arena_bin_slabs_full_remove(bin, slab);
 		arena_bin_lower_slab(tsdn, arena, slab, bin);
 	}
diff --git a/src/extent.c b/src/extent.c
index 3f4f5f1..8bd8eb7 100644
--- a/src/extent.c
+++ b/src/extent.c
@@ -94,7 +94,8 @@ extent_alloc(tsdn_t *tsdn, arena_t *arena) {
 	extent = extent_list_last(&arena->extent_freelist);
 	if (extent == NULL) {
 		malloc_mutex_unlock(tsdn, &arena->extent_freelist_mtx);
-		return base_alloc(tsdn, arena->base, sizeof(extent_t), QUANTUM);
+		return base_alloc(tsdn, arena->base, sizeof(extent_t),
+		    CACHELINE);
 	}
 	extent_list_remove(&arena->extent_freelist, extent);
 	malloc_mutex_unlock(tsdn, &arena->extent_freelist_mtx);