From e75e9be130910a7344f553e5e6c664047a0d0464 Mon Sep 17 00:00:00 2001 From: Jason Evans Date: Sun, 17 Apr 2016 12:55:10 -0700 Subject: Add rtree element witnesses. --- include/jemalloc/internal/mutex.h | 11 ++-- include/jemalloc/internal/private_symbols.txt | 4 ++ include/jemalloc/internal/rtree.h | 76 +++++++++++++++++++++++---- include/jemalloc/internal/tsd.h | 2 + include/jemalloc/internal/witness.h | 16 ++++-- 5 files changed, 90 insertions(+), 19 deletions(-) (limited to 'include/jemalloc') diff --git a/include/jemalloc/internal/mutex.h b/include/jemalloc/internal/mutex.h index 52217991..b4e01ff8 100644 --- a/include/jemalloc/internal/mutex.h +++ b/include/jemalloc/internal/mutex.h @@ -6,21 +6,24 @@ typedef struct malloc_mutex_s malloc_mutex_t; #ifdef _WIN32 # define MALLOC_MUTEX_INITIALIZER #elif (defined(JEMALLOC_OSSPIN)) -# define MALLOC_MUTEX_INITIALIZER {0, WITNESS_INITIALIZER(WITNESS_RANK_OMIT)} +# define MALLOC_MUTEX_INITIALIZER \ + {0, WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT)} #elif (defined(JEMALLOC_MUTEX_INIT_CB)) # define MALLOC_MUTEX_INITIALIZER \ - {PTHREAD_MUTEX_INITIALIZER, NULL, WITNESS_INITIALIZER(WITNESS_RANK_OMIT)} + {PTHREAD_MUTEX_INITIALIZER, NULL, \ + WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT)} #else # if (defined(JEMALLOC_HAVE_PTHREAD_MUTEX_ADAPTIVE_NP) && \ defined(PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP)) # define MALLOC_MUTEX_TYPE PTHREAD_MUTEX_ADAPTIVE_NP # define MALLOC_MUTEX_INITIALIZER \ {PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP, \ - WITNESS_INITIALIZER(WITNESS_RANK_OMIT)} + WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT)} # else # define MALLOC_MUTEX_TYPE PTHREAD_MUTEX_DEFAULT # define MALLOC_MUTEX_INITIALIZER \ - {PTHREAD_MUTEX_INITIALIZER, WITNESS_INITIALIZER(WITNESS_RANK_OMIT)} + {PTHREAD_MUTEX_INITIALIZER, \ + WITNESS_INITIALIZER("mutex", WITNESS_RANK_OMIT)} # endif #endif diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt index 42c730c6..102f01c0 100644 --- a/include/jemalloc/internal/private_symbols.txt +++ b/include/jemalloc/internal/private_symbols.txt @@ -468,6 +468,10 @@ rtree_elm_lookup rtree_elm_read rtree_elm_read_acquired rtree_elm_release +rtree_elm_witness_access +rtree_elm_witness_acquire +rtree_elm_witness_release +rtree_elm_witnesses_cleanup rtree_elm_write rtree_elm_write_acquired rtree_read diff --git a/include/jemalloc/internal/rtree.h b/include/jemalloc/internal/rtree.h index dbea434c..e62ab6b9 100644 --- a/include/jemalloc/internal/rtree.h +++ b/include/jemalloc/internal/rtree.h @@ -7,6 +7,8 @@ #ifdef JEMALLOC_H_TYPES typedef struct rtree_elm_s rtree_elm_t; +typedef struct rtree_elm_witness_s rtree_elm_witness_t; +typedef struct rtree_elm_witness_tsd_s rtree_elm_witness_tsd_t; typedef struct rtree_level_s rtree_level_t; typedef struct rtree_s rtree_t; @@ -23,6 +25,29 @@ typedef struct rtree_s rtree_t; /* Used for two-stage lock-free node initialization. */ #define RTREE_NODE_INITIALIZING ((rtree_elm_t *)0x1) +/* + * Maximum number of concurrently acquired elements per thread. This controls + * how many witness_t structures are embedded in tsd. Ideally rtree_elm_t would + * have a witness_t directly embedded, but that would dramatically bloat the + * tree. This must contain enough entries to e.g. coalesce two extents. + */ +#define RTREE_ELM_ACQUIRE_MAX 4 + +/* Initializers for rtree_elm_witness_tsd_t. */ +#define RTREE_ELM_WITNESS_INITIALIZER { \ + NULL, \ + WITNESS_INITIALIZER("rtree_elm", WITNESS_RANK_RTREE_ELM) \ +} + +#define RTREE_ELM_WITNESS_TSD_INITIALIZER { \ + { \ + RTREE_ELM_WITNESS_INITIALIZER, \ + RTREE_ELM_WITNESS_INITIALIZER, \ + RTREE_ELM_WITNESS_INITIALIZER, \ + RTREE_ELM_WITNESS_INITIALIZER \ + } \ +} + #endif /* JEMALLOC_H_TYPES */ /******************************************************************************/ #ifdef JEMALLOC_H_STRUCTS @@ -35,6 +60,15 @@ struct rtree_elm_s { }; }; +struct rtree_elm_witness_s { + const rtree_elm_t *elm; + witness_t witness; +}; + +struct rtree_elm_witness_tsd_s { + rtree_elm_witness_t witnesses[RTREE_ELM_ACQUIRE_MAX]; +}; + struct rtree_level_s { /* * A non-NULL subtree points to a subtree rooted along the hypothetical @@ -97,6 +131,13 @@ rtree_elm_t *rtree_subtree_read_hard(tsdn_t *tsdn, rtree_t *rtree, unsigned level); rtree_elm_t *rtree_child_read_hard(tsdn_t *tsdn, rtree_t *rtree, rtree_elm_t *elm, unsigned level); +void rtree_elm_witness_acquire(tsdn_t *tsdn, const rtree_t *rtree, + uintptr_t key, const rtree_elm_t *elm); +void rtree_elm_witness_access(tsdn_t *tsdn, const rtree_t *rtree, + const rtree_elm_t *elm); +void rtree_elm_witness_release(tsdn_t *tsdn, const rtree_t *rtree, + const rtree_elm_t *elm); +void rtree_elm_witnesses_cleanup(tsd_t *tsd); #endif /* JEMALLOC_H_EXTERNS */ /******************************************************************************/ @@ -125,9 +166,11 @@ extent_t *rtree_read(tsdn_t *tsdn, rtree_t *rtree, uintptr_t key, bool dependent); rtree_elm_t *rtree_elm_acquire(tsdn_t *tsdn, rtree_t *rtree, uintptr_t key, bool dependent, bool init_missing); -extent_t *rtree_elm_read_acquired(rtree_elm_t *elm); -void rtree_elm_write_acquired(rtree_elm_t *elm, const extent_t *extent); -void rtree_elm_release(rtree_elm_t *elm); +extent_t *rtree_elm_read_acquired(tsdn_t *tsdn, const rtree_t *rtree, + rtree_elm_t *elm); +void rtree_elm_write_acquired(tsdn_t *tsdn, const rtree_t *rtree, + rtree_elm_t *elm, const extent_t *extent); +void rtree_elm_release(tsdn_t *tsdn, const rtree_t *rtree, rtree_elm_t *elm); void rtree_clear(tsdn_t *tsdn, rtree_t *rtree, uintptr_t key); #endif @@ -393,11 +436,14 @@ rtree_elm_acquire(tsdn_t *tsdn, rtree_t *rtree, uintptr_t key, bool dependent, } while (atomic_cas_p(&elm->pun, (void *)extent, s)); } + if (config_debug) + rtree_elm_witness_acquire(tsdn, rtree, key, elm); + return (elm); } JEMALLOC_INLINE extent_t * -rtree_elm_read_acquired(rtree_elm_t *elm) +rtree_elm_read_acquired(tsdn_t *tsdn, const rtree_t *rtree, rtree_elm_t *elm) { extent_t *extent; @@ -405,24 +451,34 @@ rtree_elm_read_acquired(rtree_elm_t *elm) extent = (extent_t *)((uintptr_t)elm->pun & ~((uintptr_t)0x1)); assert(((uintptr_t)extent & (uintptr_t)0x1) == (uintptr_t)0x0); + if (config_debug) + rtree_elm_witness_access(tsdn, rtree, elm); + return (extent); } JEMALLOC_INLINE void -rtree_elm_write_acquired(rtree_elm_t *elm, const extent_t *extent) +rtree_elm_write_acquired(tsdn_t *tsdn, const rtree_t *rtree, rtree_elm_t *elm, + const extent_t *extent) { assert(((uintptr_t)extent & (uintptr_t)0x1) == (uintptr_t)0x0); assert(((uintptr_t)elm->pun & (uintptr_t)0x1) == (uintptr_t)0x1); + + if (config_debug) + rtree_elm_witness_access(tsdn, rtree, elm); + elm->pun = (void *)((uintptr_t)extent | (uintptr_t)0x1); - assert(rtree_elm_read_acquired(elm) == extent); + assert(rtree_elm_read_acquired(tsdn, rtree, elm) == extent); } JEMALLOC_INLINE void -rtree_elm_release(rtree_elm_t *elm) +rtree_elm_release(tsdn_t *tsdn, const rtree_t *rtree, rtree_elm_t *elm) { - rtree_elm_write(elm, rtree_elm_read_acquired(elm)); + rtree_elm_write(elm, rtree_elm_read_acquired(tsdn, rtree, elm)); + if (config_debug) + rtree_elm_witness_release(tsdn, rtree, elm); } JEMALLOC_INLINE void @@ -431,8 +487,8 @@ rtree_clear(tsdn_t *tsdn, rtree_t *rtree, uintptr_t key) rtree_elm_t *elm; elm = rtree_elm_acquire(tsdn, rtree, key, true, false); - rtree_elm_write_acquired(elm, NULL); - rtree_elm_release(elm); + rtree_elm_write_acquired(tsdn, rtree, elm, NULL); + rtree_elm_release(tsdn, rtree, elm); } #endif diff --git a/include/jemalloc/internal/tsd.h b/include/jemalloc/internal/tsd.h index f4ff8d76..ca8915ea 100644 --- a/include/jemalloc/internal/tsd.h +++ b/include/jemalloc/internal/tsd.h @@ -573,6 +573,7 @@ struct tsd_init_head_s { O(arenas_tdata_bypass, bool) \ O(tcache_enabled, tcache_enabled_t) \ O(witnesses, witness_list_t) \ + O(rtree_elm_witnesses, rtree_elm_witness_tsd_t) \ O(witness_fork, bool) \ #define TSD_INITIALIZER { \ @@ -588,6 +589,7 @@ struct tsd_init_head_s { false, \ tcache_enabled_default, \ ql_head_initializer(witnesses), \ + RTREE_ELM_WITNESS_TSD_INITIALIZER, \ false \ } diff --git a/include/jemalloc/internal/witness.h b/include/jemalloc/internal/witness.h index c68c9694..f15665bc 100644 --- a/include/jemalloc/internal/witness.h +++ b/include/jemalloc/internal/witness.h @@ -4,7 +4,8 @@ typedef struct witness_s witness_t; typedef unsigned witness_rank_t; typedef ql_head(witness_t) witness_list_t; -typedef int witness_comp_t (const witness_t *, const witness_t *); +typedef int witness_comp_t (const witness_t *, void *, const witness_t *, + void *); /* * Lock ranks. Witnesses with rank WITNESS_RANK_OMIT are completely ignored by @@ -26,7 +27,8 @@ typedef int witness_comp_t (const witness_t *, const witness_t *); #define WITNESS_RANK_ARENA_CHUNKS 9U #define WITNESS_RANK_ARENA_EXTENT_CACHE 10 -#define WITNESS_RANK_BASE 11U +#define WITNESS_RANK_RTREE_ELM 11U +#define WITNESS_RANK_BASE 12U #define WITNESS_RANK_LEAF 0xffffffffU #define WITNESS_RANK_ARENA_BIN WITNESS_RANK_LEAF @@ -38,7 +40,7 @@ typedef int witness_comp_t (const witness_t *, const witness_t *); #define WITNESS_RANK_PROF_NEXT_THR_UID WITNESS_RANK_LEAF #define WITNESS_RANK_PROF_THREAD_ACTIVE_INIT WITNESS_RANK_LEAF -#define WITNESS_INITIALIZER(rank) {"initializer", rank, NULL, {NULL, NULL}} +#define WITNESS_INITIALIZER(name, rank) {name, rank, NULL, NULL, {NULL, NULL}} #endif /* JEMALLOC_H_TYPES */ /******************************************************************************/ @@ -61,6 +63,9 @@ struct witness_s { */ witness_comp_t *comp; + /* Opaque data, passed to comp(). */ + void *opaque; + /* Linkage for thread's currently owned locks. */ ql_elm(witness_t) link; }; @@ -70,7 +75,7 @@ struct witness_s { #ifdef JEMALLOC_H_EXTERNS void witness_init(witness_t *witness, const char *name, witness_rank_t rank, - witness_comp_t *comp); + witness_comp_t *comp, void *opaque); #ifdef JEMALLOC_JET typedef void (witness_lock_error_t)(const witness_list_t *, const witness_t *); extern witness_lock_error_t *witness_lock_error; @@ -211,7 +216,8 @@ witness_lock(tsdn_t *tsdn, witness_t *witness) /* Not forking, rank order reversal. */ witness_lock_error(witnesses, witness); } else if (w->rank == witness->rank && (w->comp == NULL || w->comp != - witness->comp || w->comp(w, witness) > 0)) { + witness->comp || w->comp(w, w->opaque, witness, witness->opaque) > + 0)) { /* * Missing/incompatible comparison function, or comparison * function indicates rank order reversal. -- cgit v1.2.3