Track extent structure serial number (esn) in extent_t.

This enables stable sorting of extent_t structures.

4 files changed, 75 insertions, 16 deletions

diff --git a/include/jemalloc/internal/base_externs.h b/include/jemalloc/internal/base_externs.h
index 2c555cf..0a1114f 100644
--- a/include/jemalloc/internal/base_externs.h
+++ b/include/jemalloc/internal/base_externs.h
@@ -1,18 +1,19 @@
 #ifndef JEMALLOC_INTERNAL_BASE_EXTERNS_H
 #define JEMALLOC_INTERNAL_BASE_EXTERNS_H
 
-base_t	*b0get(void);
-base_t	*base_new(tsdn_t *tsdn, unsigned ind, extent_hooks_t *extent_hooks);
-void	base_delete(base_t *base);
-extent_hooks_t	*base_extent_hooks_get(base_t *base);
-extent_hooks_t	*base_extent_hooks_set(base_t *base,
+base_t *b0get(void);
+base_t *base_new(tsdn_t *tsdn, unsigned ind, extent_hooks_t *extent_hooks);
+void base_delete(base_t *base);
+extent_hooks_t *base_extent_hooks_get(base_t *base);
+extent_hooks_t *base_extent_hooks_set(base_t *base,
     extent_hooks_t *extent_hooks);
-void	*base_alloc(tsdn_t *tsdn, base_t *base, size_t size, size_t alignment);
-void	base_stats_get(tsdn_t *tsdn, base_t *base, size_t *allocated,
+void *base_alloc(tsdn_t *tsdn, base_t *base, size_t size, size_t alignment);
+extent_t *base_alloc_extent(tsdn_t *tsdn, base_t *base);
+void base_stats_get(tsdn_t *tsdn, base_t *base, size_t *allocated,
     size_t *resident, size_t *mapped);
-void	base_prefork(tsdn_t *tsdn, base_t *base);
-void	base_postfork_parent(tsdn_t *tsdn, base_t *base);
-void	base_postfork_child(tsdn_t *tsdn, base_t *base);
-bool	base_boot(tsdn_t *tsdn);
+void base_prefork(tsdn_t *tsdn, base_t *base);
+void base_postfork_parent(tsdn_t *tsdn, base_t *base);
+void base_postfork_child(tsdn_t *tsdn, base_t *base);
+bool base_boot(tsdn_t *tsdn);
 
 #endif /* JEMALLOC_INTERNAL_BASE_EXTERNS_H */
diff --git a/include/jemalloc/internal/extent_inlines.h b/include/jemalloc/internal/extent_inlines.h
index 6fc0101..e1c5cea 100644
--- a/include/jemalloc/internal/extent_inlines.h
+++ b/include/jemalloc/internal/extent_inlines.h
@@ -17,6 +17,8 @@ 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);
+size_t extent_esn_get(const extent_t *extent);
+size_t extent_bsize_get(const extent_t *extent);
 void *extent_before_get(const extent_t *extent);
 void *extent_last_get(const extent_t *extent);
 void *extent_past_get(const extent_t *extent);
@@ -27,6 +29,8 @@ void extent_arena_set(extent_t *extent, arena_t *arena);
 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_esn_set(extent_t *extent, size_t esn);
+void extent_bsize_set(extent_t *extent, size_t bsize);
 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);
@@ -40,6 +44,7 @@ void extent_prof_tctx_set(extent_t *extent, prof_tctx_t *tctx);
 void extent_init(extent_t *extent, arena_t *arena, void *addr, size_t size,
     bool slab, szind_t szind, size_t sn, extent_state_t state, bool zeroed,
     bool committed);
+void extent_binit(extent_t *extent, void *addr, size_t size, size_t sn);
 void extent_list_init(extent_list_t *list);
 extent_t *extent_list_first(const extent_list_t *list);
 extent_t *extent_list_last(const extent_list_t *list);
@@ -141,7 +146,17 @@ extent_addr_get(const extent_t *extent) {
 
 JEMALLOC_INLINE size_t
 extent_size_get(const extent_t *extent) {
-	return extent->e_size;
+	return (extent->e_size_esn & EXTENT_SIZE_MASK);
+}
+
+JEMALLOC_INLINE size_t
+extent_esn_get(const extent_t *extent) {
+	return (extent->e_size_esn & EXTENT_ESN_MASK);
+}
+
+JEMALLOC_INLINE size_t
+extent_bsize_get(const extent_t *extent) {
+	return extent->e_bsize;
 }
 
 JEMALLOC_INLINE void *
@@ -213,7 +228,19 @@ extent_addr_randomize(tsdn_t *tsdn, extent_t *extent, size_t alignment) {
 
 JEMALLOC_INLINE void
 extent_size_set(extent_t *extent, size_t size) {
-	extent->e_size = size;
+	assert((size & ~EXTENT_SIZE_MASK) == 0);
+	extent->e_size_esn = size | (extent->e_size_esn & ~EXTENT_SIZE_MASK);
+}
+
+JEMALLOC_INLINE void
+extent_esn_set(extent_t *extent, size_t esn) {
+	extent->e_size_esn = (extent->e_size_esn & ~EXTENT_ESN_MASK) | (esn &
+	    EXTENT_ESN_MASK);
+}
+
+JEMALLOC_INLINE void
+extent_bsize_set(extent_t *extent, size_t bsize) {
+	extent->e_bsize = bsize;
 }
 
 JEMALLOC_INLINE void
@@ -299,6 +326,19 @@ extent_init(extent_t *extent, arena_t *arena, void *addr, size_t size,
 }
 
 JEMALLOC_INLINE void
+extent_binit(extent_t *extent, void *addr, size_t bsize, size_t sn) {
+	extent_arena_set(extent, NULL);
+	extent_addr_set(extent, addr);
+	extent_bsize_set(extent, bsize);
+	extent_slab_set(extent, false);
+	extent_szind_set(extent, NSIZES);
+	extent_sn_set(extent, sn);
+	extent_state_set(extent, extent_state_active);
+	extent_zeroed_set(extent, true);
+	extent_committed_set(extent, true);
+}
+
+JEMALLOC_INLINE void
 extent_list_init(extent_list_t *list) {
 	ql_new(list);
 }
diff --git a/include/jemalloc/internal/extent_structs.h b/include/jemalloc/internal/extent_structs.h
index 3d3d418..38c3c8a 100644
--- a/include/jemalloc/internal/extent_structs.h
+++ b/include/jemalloc/internal/extent_structs.h
@@ -23,8 +23,8 @@ struct extent_s {
 	 * z: zeroed
 	 * t: state
 	 * i: szind
-	 * n: sn
 	 * f: nfree
+	 * n: sn
 	 *
 	 * nnnnnnnn ... nnnnnfff fffffffi iiiiiiit tzcbaaaa aaaaaaaa
 	 *
@@ -102,8 +102,20 @@ struct extent_s {
 	/* Pointer to the extent that this structure is responsible for. */
 	void			*e_addr;
 
-	/* Extent size. */
-	size_t			e_size;
+	union {
+		/*
+		 * Extent size and serial number associated with the extent
+		 * structure (different than the serial number for the extent at
+		 * e_addr).
+		 *
+		 * ssssssss [...] ssssssss ssssnnnn nnnnnnnn
+		 */
+		size_t			e_size_esn;
+	#define EXTENT_SIZE_MASK	((size_t)~(PAGE-1))
+	#define EXTENT_ESN_MASK		((size_t)PAGE-1)
+		/* Base extent size, which may not be a multiple of PAGE. */
+		size_t			e_bsize;
+	};
 
 	/*
 	 * List linkage, used by a variety of lists:
diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt
index c1573aa..dd35d50 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -86,6 +86,7 @@ b0get
 base_alloc
 base_boot
 base_delete
+base_extent_alloc
 base_extent_hooks_get
 base_extent_hooks_set
 base_ind_get
@@ -143,6 +144,9 @@ extent_arena_set
 extent_base_get
 extent_before_get
 extent_boot
+extent_binit
+extent_bsize_get
+extent_bsize_set
 extent_commit_wrapper
 extent_committed_get
 extent_committed_set
@@ -156,6 +160,8 @@ extent_dss_boot
 extent_dss_mergeable
 extent_dss_prec_get
 extent_dss_prec_set
+extent_esn_get
+extent_esn_set
 extent_heap_empty
 extent_heap_first
 extent_heap_insert