[PATCH] malloc: use atomic free list

[Joern Engel <joern at purestorage dot com>]

From: Joern Engel <joern@purestorage.org>

Malloc will almost never block on a mutex.  If it would, it will jump to
the next arena until it finds an uncontested mutex - creating a new
arena if this strategy fails.

Free is forced to block on the mutex, as it cannot free objects to a
different arena.  To avoid this we put freed chunks on an atomic list
and let the next taker of the lock handle chunks on this list.

JIRA: PURE-27597
---
 tpc/malloc2.13/malloc.c |  6 ++++++
 tpc/malloc2.13/tcache.h | 50 ++++++++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 51 insertions(+), 5 deletions(-)

diff --git a/tpc/malloc2.13/malloc.c b/tpc/malloc2.13/malloc.c
index 1ee563bb299e..90d0e7e552b9 100644
--- a/tpc/malloc2.13/malloc.c
+++ b/tpc/malloc2.13/malloc.c
@@ -2112,6 +2112,12 @@ struct malloc_state {
 	/* Memory allocated from the system in this arena.  */
 	INTERNAL_SIZE_T system_mem;
 	INTERNAL_SIZE_T max_system_mem;
+
+	/*
+	 * Chunks freed by tcache_gc, not sorted into any bins yet and
+	 * not protected by mutex - use atomic operations on this.
+	 */
+	mchunkptr atomic_free_list;
 };
 
 struct malloc_par {
diff --git a/tpc/malloc2.13/tcache.h b/tpc/malloc2.13/tcache.h
index 1829cd4ebb9a..0ddee48a30dc 100644
--- a/tpc/malloc2.13/tcache.h
+++ b/tpc/malloc2.13/tcache.h
@@ -104,10 +104,22 @@ static inline int is_accessed(struct thread_cache *cache, int bin)
 	return get_bit(cache->accessed_map, bin);
 }
 
+static void free_atomic_list(struct malloc_state *arena)
+{
+	struct malloc_chunk *victim, *next;
+
+	victim = __sync_lock_test_and_set(&arena->atomic_free_list, NULL);
+	while (victim) {
+		next = victim->fd;
+		_int_free(arena, victim);
+		victim = next;
+	}
+}
+
 static void tcache_gc(struct thread_cache *cache)
 {
 	struct malloc_chunk *victim, *next;
-	struct malloc_state *arena;
+	struct malloc_state *arena = NULL;
 	int i, did_repeat = 0;
 
 repeat:
@@ -122,10 +134,19 @@ repeat:
 			cache->tc_size -= chunksize(victim);
 			cache->tc_count--;
 			arena = arena_for_chunk(victim);
-			/* TODO: use atomic bins instead */
-			mutex_lock(&arena->mutex);
-			_int_free(arena, victim);
-			mutex_unlock(&arena->mutex);
+			/*
+			 * Free, unlike malloc, has no choice which arena to
+			 * use and therefore cannot avoid blocking on the
+			 * mutex by using trylock.
+			 *
+			 * Instead we move chunks to an atomic list that we
+			 * can access locklessly and defer actually freeing
+			 * of the chunks to the next allocator that holds
+			 * the mutex.
+			 */
+			do {
+				victim->fd = arena->atomic_free_list;
+			} while (!__sync_bool_compare_and_swap(&arena->atomic_free_list, victim->fd, victim));
 			victim = next;
 		}
 	}
@@ -149,6 +170,24 @@ repeat:
 		assert(cache->tc_size == 0);
 		assert(cache->tc_count == 0);
 	}
+	if (arena && !mutex_trylock(&arena->mutex)) {
+		/*
+		 * Chunks on the atomic free list can linger for a long time
+		 * if no allocations from that arena happen.  This occupies
+		 * system memory that otherwise might be returned to the kernel.
+		 *
+		 * If we can get the mutex, we might as well handle the atomic
+		 * list.  If not, the arena must be in active use and someone
+		 * else will handle this for us.
+		 *
+		 * Theoretically we should try every arena we processed chunks
+		 * for.  By doing it for just one arena essentially at random,
+		 * we will eventually do it for all and don't have to keep track
+		 * of all the arenas we used.
+		 */
+		free_atomic_list(arena);
+		arena_unlock(arena);
+	}
 }
 
 static void *tcache_malloc(size_t size)
@@ -213,6 +252,7 @@ static void *tcache_malloc(size_t size)
 	arena = arena_get(size);
 	if (!arena)
 		return NULL;
+	free_atomic_list(arena);
 	/* TODO: _int_malloc does checked_request2size() again, which is silly */
 	victim = _int_malloc(arena, size);
 	if (!victim) {
-- 
2.7.0.rc3