[PATCH] malloc: document and fix linked list handling

[Joern Engel <joern at purestorage dot com>]

Costa wondered why we have a write barrier without a matching read
barrier.  On closer examination that pattern is actually correct,
although by no means obvious.  There were, however, two bugs.

commit 52c75b22e320:
    Also, change the numa_arena[node] pointers whenever we use them.
    Otherwise those arenas become hot spots.  If we move them around, the
    load gets spread roughly evenly.

While this sounds good in principle, it races with _int_new_arena.  We
have to take the list_lock to do so safely.  At this point I'd rather
remove the code than go fancy with trylocks.

The second bug seems to be ancient.  atomic_write_barrier() protects
against the compiler reordering writes, but not against the cpu.

JIRA: PURE-27597
---
 tpc/malloc2.13/arena.h          | 16 +++++++++++++---
 tpc/malloc2.13/malloc-machine.h |  6 +++---
 2 files changed, 16 insertions(+), 6 deletions(-)

diff --git a/tpc/malloc2.13/arena.h b/tpc/malloc2.13/arena.h
index 7f50dacb8297..20c3614e65bf 100644
--- a/tpc/malloc2.13/arena.h
+++ b/tpc/malloc2.13/arena.h
@@ -706,6 +706,17 @@ static struct malloc_state *_int_new_arena(size_t size, int numa_node)
 	/* Add the new arena to the global lists.  */
 	a->numa_node = numa_node;
 
+	/*
+	 * a->next must be a valid pointer before changing
+	 * main_arena.next, otherwise a reader following the list
+	 * pointers could end up dereferencing NULL or worse.  The
+	 * same reasoning applies to a->local_next.
+	 *
+	 * No atomic_read_barrier() is needed, because these are
+	 * dependent reads that are naturally ordered.  You really
+	 * cannot load a->next->next before loading a->next, after
+	 * all.
+	 */
 	a->next = main_arena.next;
 	atomic_write_barrier();
 	main_arena.next = a;
@@ -797,10 +808,9 @@ static struct malloc_state *arena_get(size_t size)
 	 * to use a numa-local arena, but are limited to best-effort.
 	 */
 	tsd_getspecific(arena_key, arena);
-	if (!arena || arena->numa_node != node) {
+	if (!arena || arena->numa_node != node)
 		arena = numa_arena[node];
-		numa_arena[node] = arena->local_next;
-	}
+
 	if (arena && !mutex_trylock(&arena->mutex)) {
 		THREAD_STAT(++(arena->stat_lock_direct));
 	} else
diff --git a/tpc/malloc2.13/malloc-machine.h b/tpc/malloc2.13/malloc-machine.h
index 5e01a27e4adc..07072f5d5e11 100644
--- a/tpc/malloc2.13/malloc-machine.h
+++ b/tpc/malloc2.13/malloc-machine.h
@@ -110,15 +110,15 @@ typedef pthread_key_t tsd_key_t;
 
 
 #ifndef atomic_full_barrier
-# define atomic_full_barrier() __asm ("" ::: "memory")
+# define atomic_full_barrier() __sync_synchronize()
 #endif
 
 #ifndef atomic_read_barrier
-# define atomic_read_barrier() atomic_full_barrier ()
+# define atomic_read_barrier() atomic_full_barrier()
 #endif
 
 #ifndef atomic_write_barrier
-# define atomic_write_barrier() atomic_full_barrier ()
+# define atomic_write_barrier() atomic_full_barrier()
 #endif
 
 #ifndef DEFAULT_TOP_PAD
-- 
2.7.0.rc3