Make dss operations lockless.

Rather than protecting dss operations with a mutex, use atomic
operations.  This has negligible impact on synchronization overhead
during typical dss allocation, but is a substantial improvement for
extent_in_dss() and the newly added extent_dss_mergeable(), which can be
called multiple times during extent deallocations.

This change also has the advantage of avoiding tsd in deallocation paths
associated with purging, which resolves potential deadlocks during
thread exit due to attempted tsd resurrection.

This resolves #425.

1 files changed, 103 insertions, 77 deletions

diff --git a/src/extent_dss.c b/src/extent_dss.c
index e0e6635..31fe8fe 100644
--- a/src/extent_dss.c
+++ b/src/extent_dss.c
@@ -12,20 +12,19 @@ const char	*dss_prec_names[] = {
 	"N/A"
 };
 
-/* Current dss precedence default, used when creating new arenas. */
-static dss_prec_t	dss_prec_default = DSS_PREC_DEFAULT;
-
 /*
- * Protects sbrk() calls.  This avoids malloc races among threads, though it
- * does not protect against races with threads that call sbrk() directly.
+ * Current dss precedence default, used when creating new arenas.  NB: This is
+ * stored as unsigned rather than dss_prec_t because in principle there's no
+ * guarantee that sizeof(dss_prec_t) is the same as sizeof(unsigned), and we use
+ * atomic operations to synchronize the setting.
  */
-static malloc_mutex_t	dss_mtx;
+static unsigned		dss_prec_default = (unsigned)DSS_PREC_DEFAULT;
 
 /* Base address of the DSS. */
 static void		*dss_base;
-/* Current end of the DSS, or ((void *)-1) if the DSS is exhausted. */
-static void		*dss_prev;
-/* Current upper limit on DSS addresses. */
+/* Atomic boolean indicating whether the DSS is exhausted. */
+static unsigned		dss_exhausted;
+/* Atomic current upper limit on DSS addresses. */
 static void		*dss_max;
 
 /******************************************************************************/
@@ -43,35 +42,63 @@ extent_dss_sbrk(intptr_t increment)
 }
 
 dss_prec_t
-extent_dss_prec_get(tsdn_t *tsdn)
+extent_dss_prec_get(void)
 {
 	dss_prec_t ret;
 
 	if (!have_dss)
 		return (dss_prec_disabled);
-	malloc_mutex_lock(tsdn, &dss_mtx);
-	ret = dss_prec_default;
-	malloc_mutex_unlock(tsdn, &dss_mtx);
+	ret = (dss_prec_t)atomic_read_u(&dss_prec_default);
 	return (ret);
 }
 
 bool
-extent_dss_prec_set(tsdn_t *tsdn, dss_prec_t dss_prec)
+extent_dss_prec_set(dss_prec_t dss_prec)
 {
 
 	if (!have_dss)
 		return (dss_prec != dss_prec_disabled);
-	malloc_mutex_lock(tsdn, &dss_mtx);
-	dss_prec_default = dss_prec;
-	malloc_mutex_unlock(tsdn, &dss_mtx);
+	atomic_write_u(&dss_prec_default, (unsigned)dss_prec);
 	return (false);
 }
 
+static void *
+extent_dss_max_update(void *new_addr)
+{
+	void *max_cur;
+	spin_t spinner;
+
+	/*
+	 * Get the current end of the DSS as max_cur and assure that dss_max is
+	 * up to date.
+	 */
+	spin_init(&spinner);
+	while (true) {
+		void *max_prev = atomic_read_p(&dss_max);
+
+		max_cur = extent_dss_sbrk(0);
+		if ((uintptr_t)max_prev > (uintptr_t)max_cur) {
+			/*
+			 * Another thread optimistically updated dss_max.  Wait
+			 * for it to finish.
+			 */
+			spin_adaptive(&spinner);
+			continue;
+		}
+		if (!atomic_cas_p(&dss_max, max_prev, max_cur))
+			break;
+	}
+	/* Fixed new_addr can only be supported if it is at the edge of DSS. */
+	if (new_addr != NULL && max_cur != new_addr)
+		return (NULL);
+
+	return (max_cur);
+}
+
 void *
 extent_alloc_dss(tsdn_t *tsdn, arena_t *arena, void *new_addr, size_t size,
     size_t alignment, bool *zero, bool *commit)
 {
-	void *ret;
 	extent_t *gap;
 
 	cassert(have_dss);
@@ -89,35 +116,27 @@ extent_alloc_dss(tsdn_t *tsdn, arena_t *arena, void *new_addr, size_t size,
 	if (gap == NULL)
 		return (NULL);
 
-	malloc_mutex_lock(tsdn, &dss_mtx);
-	if (dss_prev != (void *)-1) {
+	if (!atomic_read_u(&dss_exhausted)) {
 		/*
 		 * The loop is necessary to recover from races with other
 		 * threads that are using the DSS for something other than
 		 * malloc.
 		 */
 		while (true) {
-			void *gap_addr, *dss_next;
+			void *ret, *max_cur, *gap_addr, *dss_next, *dss_prev;
 			size_t gap_size;
 			intptr_t incr;
 
-			/* Avoid an unnecessary system call. */
-			if (new_addr != NULL && dss_max != new_addr)
-				break;
-
-			/* Get the current end of the DSS. */
-			dss_max = extent_dss_sbrk(0);
-
-			/* Make sure the earlier condition still holds. */
-			if (new_addr != NULL && dss_max != new_addr)
-				break;
+			max_cur = extent_dss_max_update(new_addr);
+			if (max_cur == NULL)
+				goto label_oom;
 
 			/*
 			 * Compute how much gap space (if any) is necessary to
 			 * satisfy alignment.  This space can be recycled for
 			 * later use.
 			 */
-			gap_addr = (void *)(PAGE_CEILING((uintptr_t)dss_max));
+			gap_addr = (void *)(PAGE_CEILING((uintptr_t)max_cur));
 			ret = (void *)ALIGNMENT_CEILING((uintptr_t)gap_addr,
 			    PAGE_CEILING(alignment));
 			gap_size = (uintptr_t)ret - (uintptr_t)gap_addr;
@@ -126,17 +145,24 @@ extent_alloc_dss(tsdn_t *tsdn, arena_t *arena, void *new_addr, size_t size,
 				    gap_size, false, false, true, false);
 			}
 			dss_next = (void *)((uintptr_t)ret + size);
-			if ((uintptr_t)ret < (uintptr_t)dss_max ||
-			    (uintptr_t)dss_next < (uintptr_t)dss_max)
-				break; /* Wrap-around. */
+			if ((uintptr_t)ret < (uintptr_t)max_cur ||
+			    (uintptr_t)dss_next < (uintptr_t)max_cur)
+				goto label_oom; /* Wrap-around. */
 			incr = gap_size + size;
+
+			/*
+			 * Optimistically update dss_max, and roll back below if
+			 * sbrk() fails.  No other thread will try to extend the
+			 * DSS while dss_max is greater than the current DSS
+			 * max reported by sbrk(0).
+			 */
+			if (atomic_cas_p(&dss_max, max_cur, dss_next))
+				continue;
+
+			/* Try to allocate. */
 			dss_prev = extent_dss_sbrk(incr);
-			if (dss_prev == (void *)-1)
-				break;
-			if (dss_prev == dss_max) {
+			if (dss_prev == max_cur) {
 				/* Success. */
-				dss_max = dss_next;
-				malloc_mutex_unlock(tsdn, &dss_mtx);
 				if (gap_size != 0)
 					extent_dalloc_gap(tsdn, arena, gap);
 				else
@@ -147,69 +173,69 @@ extent_alloc_dss(tsdn_t *tsdn, arena_t *arena, void *new_addr, size_t size,
 					*commit = pages_decommit(ret, size);
 				return (ret);
 			}
+			/*
+			 * Failure, whether due to OOM or a race with a raw
+			 * sbrk() call from outside the allocator.  Try to roll
+			 * back optimistic dss_max update; if rollback fails,
+			 * it's due to another caller of this function having
+			 * succeeded since this invocation started, in which
+			 * case rollback is not necessary.
+			 */
+			atomic_cas_p(&dss_max, dss_next, max_cur);
+			if (dss_prev == (void *)-1) {
+				/* OOM. */
+				atomic_write_u(&dss_exhausted, (unsigned)true);
+				goto label_oom;
+			}
 		}
 	}
-	/* OOM. */
-	malloc_mutex_unlock(tsdn, &dss_mtx);
+label_oom:
 	extent_dalloc(tsdn, arena, gap);
 	return (NULL);
 }
 
-bool
-extent_in_dss(tsdn_t *tsdn, void *addr)
+static bool
+extent_in_dss_helper(void *addr, void *max)
 {
-	bool ret;
-
-	cassert(have_dss);
 
-	malloc_mutex_lock(tsdn, &dss_mtx);
-	if ((uintptr_t)addr >= (uintptr_t)dss_base
-	    && (uintptr_t)addr < (uintptr_t)dss_max)
-		ret = true;
-	else
-		ret = false;
-	malloc_mutex_unlock(tsdn, &dss_mtx);
-
-	return (ret);
+	return ((uintptr_t)addr >= (uintptr_t)dss_base && (uintptr_t)addr <
+	    (uintptr_t)max);
 }
 
 bool
-extent_dss_boot(void)
+extent_in_dss(void *addr)
 {
 
 	cassert(have_dss);
 
-	if (malloc_mutex_init(&dss_mtx, "dss", WITNESS_RANK_DSS))
-		return (true);
-	dss_base = extent_dss_sbrk(0);
-	dss_prev = dss_base;
-	dss_max = dss_base;
-
-	return (false);
+	return (extent_in_dss_helper(addr, atomic_read_p(&dss_max)));
 }
 
-void
-extent_dss_prefork(tsdn_t *tsdn)
+bool
+extent_dss_mergeable(void *addr_a, void *addr_b)
 {
+	void *max;
 
-	if (have_dss)
-		malloc_mutex_prefork(tsdn, &dss_mtx);
-}
+	cassert(have_dss);
 
-void
-extent_dss_postfork_parent(tsdn_t *tsdn)
-{
+	if ((uintptr_t)addr_a < (uintptr_t)dss_base && (uintptr_t)addr_b <
+	    (uintptr_t)dss_base)
+		return (true);
 
-	if (have_dss)
-		malloc_mutex_postfork_parent(tsdn, &dss_mtx);
+	max = atomic_read_p(&dss_max);
+	return (extent_in_dss_helper(addr_a, max) ==
+	    extent_in_dss_helper(addr_b, max));
 }
 
 void
-extent_dss_postfork_child(tsdn_t *tsdn)
+extent_dss_boot(void)
 {
 
-	if (have_dss)
-		malloc_mutex_postfork_child(tsdn, &dss_mtx);
+	cassert(have_dss);
+
+	dss_base = extent_dss_sbrk(0);
+	dss_exhausted = (unsigned)(dss_base == (void *)-1);
+	dss_max = dss_base;
 }
 
 /******************************************************************************/