Add rtree element witnesses.
diff --git a/include/jemalloc/internal/mutex.h b/include/jemalloc/internal/mutex.h
index 5221799..b4e01ff 100644
--- a/include/jemalloc/internal/mutex.h
+++ b/include/jemalloc/internal/mutex.h
@@ -6,21 +6,24 @@
#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 42c730c..102f01c 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -468,6 +468,10 @@
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 dbea434..e62ab6b 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 @@
/* 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_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 @@
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 @@
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 @@
} 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 @@
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_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 f4ff8d7..ca8915e 100644
--- a/include/jemalloc/internal/tsd.h
+++ b/include/jemalloc/internal/tsd.h
@@ -573,6 +573,7 @@
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 @@
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 c68c969..f15665b 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 @@
#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 @@
#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 @@
*/
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 @@
#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 @@
/* 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.
diff --git a/src/mutex.c b/src/mutex.c
index a1fac34..119b8e3 100644
--- a/src/mutex.c
+++ b/src/mutex.c
@@ -104,7 +104,7 @@
pthread_mutexattr_destroy(&attr);
#endif
if (config_debug)
- witness_init(&mutex->witness, name, rank, NULL);
+ witness_init(&mutex->witness, name, rank, NULL, NULL);
return (false);
}
diff --git a/src/rtree.c b/src/rtree.c
index c6b64cf..504f9f2 100644
--- a/src/rtree.c
+++ b/src/rtree.c
@@ -169,3 +169,126 @@
return (rtree_node_init(tsdn, rtree, level, &elm->child));
}
+
+static int
+rtree_elm_witness_comp(const witness_t *a, void *oa, const witness_t *b,
+ void *ob)
+{
+ uintptr_t ka = (uintptr_t)oa;
+ uintptr_t kb = (uintptr_t)ob;
+
+ assert(ka != 0);
+ assert(kb != 0);
+
+ return ((ka > kb) - (ka < kb));
+}
+
+static witness_t *
+rtree_elm_witness_alloc(tsd_t *tsd, uintptr_t key, const rtree_elm_t *elm)
+{
+ witness_t *witness;
+ size_t i;
+ rtree_elm_witness_tsd_t *witnesses = tsd_rtree_elm_witnessesp_get(tsd);
+
+ /* Iterate over entire array to detect double allocation attempts. */
+ witness = NULL;
+ for (i = 0; i < sizeof(rtree_elm_witness_tsd_t) / sizeof(witness_t);
+ i++) {
+ rtree_elm_witness_t *rew = &witnesses->witnesses[i];
+
+ assert(rew->elm != elm);
+ if (rew->elm == NULL && witness == NULL) {
+ rew->elm = elm;
+ witness = &rew->witness;
+ witness_init(witness, "rtree_elm",
+ WITNESS_RANK_RTREE_ELM, rtree_elm_witness_comp,
+ (void *)key);
+ }
+ }
+ assert(witness != NULL);
+ return (witness);
+}
+
+static witness_t *
+rtree_elm_witness_find(tsd_t *tsd, const rtree_elm_t *elm)
+{
+ size_t i;
+ rtree_elm_witness_tsd_t *witnesses = tsd_rtree_elm_witnessesp_get(tsd);
+
+ for (i = 0; i < sizeof(rtree_elm_witness_tsd_t) / sizeof(witness_t);
+ i++) {
+ rtree_elm_witness_t *rew = &witnesses->witnesses[i];
+
+ if (rew->elm == elm)
+ return (&rew->witness);
+ }
+ not_reached();
+}
+
+static void
+rtree_elm_witness_dalloc(tsd_t *tsd, witness_t *witness, const rtree_elm_t *elm)
+{
+ size_t i;
+ rtree_elm_witness_tsd_t *witnesses = tsd_rtree_elm_witnessesp_get(tsd);
+
+ for (i = 0; i < sizeof(rtree_elm_witness_tsd_t) / sizeof(witness_t);
+ i++) {
+ rtree_elm_witness_t *rew = &witnesses->witnesses[i];
+
+ if (rew->elm == elm) {
+ rew->elm = NULL;
+ witness_init(&rew->witness, "rtree_elm",
+ WITNESS_RANK_RTREE_ELM, rtree_elm_witness_comp,
+ NULL);
+ return;
+ }
+ }
+ not_reached();
+}
+
+void
+rtree_elm_witness_acquire(tsdn_t *tsdn, const rtree_t *rtree, uintptr_t key,
+ const rtree_elm_t *elm)
+{
+ witness_t *witness;
+
+ if (tsdn_null(tsdn))
+ return;
+
+ witness = rtree_elm_witness_alloc(tsdn_tsd(tsdn), key, elm);
+ witness_lock(tsdn, witness);
+}
+
+void
+rtree_elm_witness_access(tsdn_t *tsdn, const rtree_t *rtree,
+ const rtree_elm_t *elm)
+{
+ witness_t *witness;
+
+ if (tsdn_null(tsdn))
+ return;
+
+ witness = rtree_elm_witness_find(tsdn_tsd(tsdn), elm);
+ witness_assert_owner(tsdn, witness);
+}
+
+void
+rtree_elm_witness_release(tsdn_t *tsdn, const rtree_t *rtree,
+ const rtree_elm_t *elm)
+{
+ witness_t *witness;
+
+ if (tsdn_null(tsdn))
+ return;
+
+ witness = rtree_elm_witness_find(tsdn_tsd(tsdn), elm);
+ witness_unlock(tsdn, witness);
+ rtree_elm_witness_dalloc(tsdn_tsd(tsdn), witness, elm);
+}
+
+void
+rtree_elm_witnesses_cleanup(tsd_t *tsd)
+{
+
+ /* Do nothing. */
+}
diff --git a/src/witness.c b/src/witness.c
index 23753f2..8efff56 100644
--- a/src/witness.c
+++ b/src/witness.c
@@ -3,12 +3,13 @@
void
witness_init(witness_t *witness, const char *name, witness_rank_t rank,
- witness_comp_t *comp)
+ witness_comp_t *comp, void *opaque)
{
witness->name = name;
witness->rank = rank;
witness->comp = comp;
+ witness->opaque = opaque;
}
#ifdef JEMALLOC_JET
diff --git a/test/unit/rtree.c b/test/unit/rtree.c
index 9c992e1..786cc35 100644
--- a/test/unit/rtree.c
+++ b/test/unit/rtree.c
@@ -85,15 +85,15 @@
true);
assert_ptr_not_null(elm,
"Unexpected rtree_elm_acquire() failure");
- rtree_elm_write_acquired(elm, extent);
- rtree_elm_release(elm);
+ rtree_elm_write_acquired(tsdn, &arg->rtree, elm, extent);
+ rtree_elm_release(tsdn, &arg->rtree, elm);
elm = rtree_elm_acquire(tsdn, &arg->rtree, key, true,
false);
assert_ptr_not_null(elm,
"Unexpected rtree_elm_acquire() failure");
- rtree_elm_read_acquired(elm);
- rtree_elm_release(elm);
+ rtree_elm_read_acquired(tsdn, &arg->rtree, elm);
+ rtree_elm_release(tsdn, &arg->rtree, elm);
} else
rtree_read(tsdn, &arg->rtree, key, false);
}
@@ -234,8 +234,8 @@
true);
assert_ptr_not_null(elm,
"Unexpected rtree_elm_acquire() failure");
- rtree_elm_write_acquired(elm, &extent);
- rtree_elm_release(elm);
+ rtree_elm_write_acquired(tsdn, &rtree, elm, &extent);
+ rtree_elm_release(tsdn, &rtree, elm);
assert_ptr_eq(rtree_read(tsdn, &rtree, keys[j], true),
&extent,
"rtree_read() should return previously set value");
diff --git a/test/unit/witness.c b/test/unit/witness.c
index ed17275..2b01203 100644
--- a/test/unit/witness.c
+++ b/test/unit/witness.c
@@ -40,20 +40,26 @@
}
static int
-witness_comp(const witness_t *a, const witness_t *b)
+witness_comp(const witness_t *a, void *oa, const witness_t *b, void *ob)
{
assert_u_eq(a->rank, b->rank, "Witnesses should have equal rank");
+ assert(oa == (void *)a);
+ assert(ob == (void *)b);
+
return (strcmp(a->name, b->name));
}
static int
-witness_comp_reverse(const witness_t *a, const witness_t *b)
+witness_comp_reverse(const witness_t *a, void *oa, const witness_t *b, void *ob)
{
assert_u_eq(a->rank, b->rank, "Witnesses should have equal rank");
+ assert(oa == (void *)a);
+ assert(ob == (void *)b);
+
return (-strcmp(a->name, b->name));
}
@@ -68,12 +74,12 @@
witness_assert_lockless(tsdn);
- witness_init(&a, "a", 1, NULL);
+ witness_init(&a, "a", 1, NULL, NULL);
witness_assert_not_owner(tsdn, &a);
witness_lock(tsdn, &a);
witness_assert_owner(tsdn, &a);
- witness_init(&b, "b", 2, NULL);
+ witness_init(&b, "b", 2, NULL, NULL);
witness_assert_not_owner(tsdn, &b);
witness_lock(tsdn, &b);
witness_assert_owner(tsdn, &b);
@@ -96,12 +102,12 @@
witness_assert_lockless(tsdn);
- witness_init(&a, "a", 1, witness_comp);
+ witness_init(&a, "a", 1, witness_comp, &a);
witness_assert_not_owner(tsdn, &a);
witness_lock(tsdn, &a);
witness_assert_owner(tsdn, &a);
- witness_init(&b, "b", 1, witness_comp);
+ witness_init(&b, "b", 1, witness_comp, &b);
witness_assert_not_owner(tsdn, &b);
witness_lock(tsdn, &b);
witness_assert_owner(tsdn, &b);
@@ -111,7 +117,7 @@
witness_lock_error = witness_lock_error_intercept;
saw_lock_error = false;
- witness_init(&c, "c", 1, witness_comp_reverse);
+ witness_init(&c, "c", 1, witness_comp_reverse, &c);
witness_assert_not_owner(tsdn, &c);
assert_false(saw_lock_error, "Unexpected witness lock error");
witness_lock(tsdn, &c);
@@ -120,7 +126,7 @@
saw_lock_error = false;
- witness_init(&d, "d", 1, NULL);
+ witness_init(&d, "d", 1, NULL, NULL);
witness_assert_not_owner(tsdn, &d);
assert_false(saw_lock_error, "Unexpected witness lock error");
witness_lock(tsdn, &d);
@@ -150,8 +156,8 @@
witness_assert_lockless(tsdn);
- witness_init(&a, "a", 1, NULL);
- witness_init(&b, "b", 2, NULL);
+ witness_init(&a, "a", 1, NULL, NULL);
+ witness_init(&b, "b", 2, NULL, NULL);
witness_lock(tsdn, &b);
assert_false(saw_lock_error, "Unexpected witness lock error");
@@ -186,7 +192,7 @@
witness_assert_lockless(tsdn);
- witness_init(&a, "a", 1, NULL);
+ witness_init(&a, "a", 1, NULL, NULL);
witness_lock(tsdn, &a);
assert_false(saw_lock_error, "Unexpected witness lock error");
@@ -220,7 +226,7 @@
witness_assert_lockless(tsdn);
- witness_init(&a, "a", 1, NULL);
+ witness_init(&a, "a", 1, NULL, NULL);
assert_false(saw_owner_error, "Unexpected owner error");
witness_unlock(tsdn, &a);
@@ -247,7 +253,7 @@
witness_assert_lockless(tsdn);
- witness_init(&a, "a", 1, NULL);
+ witness_init(&a, "a", 1, NULL, NULL);
assert_false(saw_lockless_error, "Unexpected lockless error");
witness_assert_lockless(tsdn);