Bug 1396723 - Use DoublyLinkedList in mozjemalloc. r=froydnj
authorMike Hommey <mh+mozilla@glandium.org>
Sat, 02 Sep 2017 08:55:42 +0900
changeset 429644 c3565469003215c97d043d4ef0f88dc4d7e5fa6a
parent 429643 45c68c943e97eb924e07ed701759faae4d57f569
child 429645 57f1221bf914f08e963f4bce8f529cd524ddfa55
push id7761
push userjlund@mozilla.com
push dateFri, 15 Sep 2017 00:19:52 +0000
treeherdermozilla-beta@c38455951db4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1396723
milestone57.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1396723 - Use DoublyLinkedList in mozjemalloc. r=froydnj Mozjemalloc uses its own doubly linked list, which, being inherited from C code, doesn't do much type checking, and, in practice, is rather similar to DoublyLinkedList, so use the latter instead.
memory/mozjemalloc/linkedlist.h
memory/mozjemalloc/mozjemalloc.cpp
mfbt/DoublyLinkedList.h
deleted file mode 100644
--- a/memory/mozjemalloc/linkedlist.h
+++ /dev/null
@@ -1,75 +0,0 @@
-/* -*- Mode: C; tab-width: 8; c-basic-offset: 8; indent-tabs-mode: t -*- */
-/* vim:set softtabstop=8 shiftwidth=8 noet: */
-/*-
- * Copyright (C) the Mozilla Foundation.
- * All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice(s), this list of conditions and the following disclaimer as
- *    the first lines of this file unmodified other than the possible
- *    addition of one or more copyright notices.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice(s), this list of conditions and the following disclaimer in
- *    the documentation and/or other materials provided with the
- *    distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE
- * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
- * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
- * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
- * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
- * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- *******************************************************************************/
-
-#ifndef linkedlist_h__
-#define linkedlist_h__
-
-#include <stddef.h>
-
-struct LinkedList {
-	LinkedList *next;
-	LinkedList *prev;
-};
-
-/* Convert from LinkedList* to foo*. */
-#define LinkedList_Get(e, type, prop) \
-  (type*)((char*)(e) - offsetof(type, prop))
-
-/* Insert |e| at the beginning of |l|.  */
-void LinkedList_InsertHead(LinkedList *l, LinkedList *e)
-{
-	e->next = l;
-	e->prev = l->prev;
-	e->next->prev = e;
-	e->prev->next = e;
-}
-
-void LinkedList_Remove(LinkedList *e)
-{
-	e->prev->next = e->next;
-	e->next->prev = e->prev;
-	e->next = e;
-	e->prev = e;
-}
-
-bool LinkedList_IsEmpty(LinkedList *e)
-{
-	return e->next == e;
-}
-
-void LinkedList_Init(LinkedList *e)
-{
-	e->next = e;
-	e->prev = e;
-}
-
-#endif
--- a/memory/mozjemalloc/mozjemalloc.cpp
+++ b/memory/mozjemalloc/mozjemalloc.cpp
@@ -107,16 +107,17 @@
  *******************************************************************************
  */
 
 #include "mozmemory_wrap.h"
 #include "mozjemalloc.h"
 #include "mozilla/Sprintf.h"
 #include "mozilla/Likely.h"
 #include "mozilla/MacroArgs.h"
+#include "mozilla/DoublyLinkedList.h"
 
 #ifdef ANDROID
 #define NO_TLS
 #endif
 
 /*
  * On Linux, we use madvise(MADV_DONTNEED) to release memory back to the
  * operating system.  If we release 1MB of live pages with MADV_DONTNEED, our
@@ -247,17 +248,16 @@ typedef long ssize_t;
 #include <mach/mach_init.h>
 #include <mach/vm_map.h>
 #include <malloc/malloc.h>
 #endif
 
 #endif
 
 #include "mozjemalloc_types.h"
-#include "linkedlist.h"
 
 /* Some tools, such as /dev/dsp wrappers, LD_PRELOAD libraries that
  * happen to override mmap() and call dlsym() from their overridden
  * mmap(). The problem is that dlsym() calls malloc(), and this ends
  * up in a dead lock in jemalloc.
  * On these systems, we prefer to directly use the system call.
  * We do that for Linux systems and kfreebsd with GNU userland.
  * Note sanity checks are not done (alignment of offset, ...) because
@@ -622,27 +622,42 @@ struct arena_chunk_t {
 
 #ifdef MALLOC_DOUBLE_PURGE
 	/* If we're double-purging, we maintain a linked list of chunks which
 	 * have pages which have been madvise(MADV_FREE)'d but not explicitly
 	 * purged.
 	 *
 	 * We're currently lazy and don't remove a chunk from this list when
 	 * all its madvised pages are recommitted. */
-	LinkedList	chunks_madvised_elem;
+	mozilla::DoublyLinkedListElement<arena_chunk_t> chunks_madvised_elem;
 #endif
 
 	/* Number of dirty pages. */
 	size_t		ndirty;
 
 	/* Map of pages within chunk that keeps track of free/large/small. */
 	arena_chunk_map_t map[1]; /* Dynamically sized. */
 };
 typedef rb_tree(arena_chunk_t) arena_chunk_tree_t;
 
+#ifdef MALLOC_DOUBLE_PURGE
+namespace mozilla {
+
+template<>
+struct GetDoublyLinkedListElement<arena_chunk_t>
+{
+  static DoublyLinkedListElement<arena_chunk_t>& Get(arena_chunk_t* aThis)
+  {
+    return aThis->chunks_madvised_elem;
+  }
+};
+
+}
+#endif
+
 struct arena_run_t {
 #if defined(MOZ_DEBUG) || defined(MOZ_DIAGNOSTIC_ASSERT_ENABLED)
 	uint32_t	magic;
 #  define ARENA_RUN_MAGIC 0x384adf93
 #endif
 
 	/* Bin this run is associated with. */
 	arena_bin_t	*bin;
@@ -704,17 +719,17 @@ struct arena_t {
 	arena_stats_t		stats;
 
 	/* Tree of dirty-page-containing chunks this arena manages. */
 	arena_chunk_tree_t	chunks_dirty;
 
 #ifdef MALLOC_DOUBLE_PURGE
 	/* Head of a linked list of MADV_FREE'd-page-containing chunks this
 	 * arena manages. */
-	LinkedList		chunks_madvised;
+	mozilla::DoublyLinkedList<arena_chunk_t> chunks_madvised;
 #endif
 
 	/*
 	 * In order to avoid rapid chunk allocation/deallocation when an arena
 	 * oscillates right on the cusp of needing a new chunk, cache the most
 	 * recently freed chunk.  The spare is left in the arena's chunk trees
 	 * until it is deleted.
 	 *
@@ -2694,35 +2709,36 @@ arena_chunk_init(arena_t *arena, arena_c
 #endif
 	arena->stats.committed += arena_chunk_header_npages;
 
 	/* Insert the run into the runs_avail tree. */
 	arena_avail_tree_insert(&arena->runs_avail,
 	    &chunk->map[arena_chunk_header_npages]);
 
 #ifdef MALLOC_DOUBLE_PURGE
-	LinkedList_Init(&chunk->chunks_madvised_elem);
+	new (&chunk->chunks_madvised_elem) mozilla::DoublyLinkedListElement<arena_chunk_t>();
 #endif
 }
 
 static void
 arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
 {
 
 	if (arena->spare) {
 		if (arena->spare->ndirty > 0) {
 			arena_chunk_tree_dirty_remove(
 			    &chunk->arena->chunks_dirty, arena->spare);
 			arena->ndirty -= arena->spare->ndirty;
 			arena->stats.committed -= arena->spare->ndirty;
 		}
 
 #ifdef MALLOC_DOUBLE_PURGE
-		/* This is safe to do even if arena->spare is not in the list. */
-		LinkedList_Remove(&arena->spare->chunks_madvised_elem);
+		if (arena->chunks_madvised.ElementProbablyInList(arena->spare)) {
+			arena->chunks_madvised.remove(arena->spare);
+		}
 #endif
 
 		chunk_dealloc((void *)arena->spare, chunksize, ARENA_CHUNK);
 		arena->stats.mapped -= chunksize;
 		arena->stats.committed -= arena_chunk_header_npages;
 	}
 
 	/*
@@ -2873,18 +2889,20 @@ arena_purge(arena_t *arena, bool all)
 		if (chunk->ndirty == 0) {
 			arena_chunk_tree_dirty_remove(&arena->chunks_dirty,
 			    chunk);
 		}
 #ifdef MALLOC_DOUBLE_PURGE
 		if (madvised) {
 			/* The chunk might already be in the list, but this
 			 * makes sure it's at the front. */
-			LinkedList_Remove(&chunk->chunks_madvised_elem);
-			LinkedList_InsertHead(&arena->chunks_madvised, &chunk->chunks_madvised_elem);
+			if (arena->chunks_madvised.ElementProbablyInList(chunk)) {
+				arena->chunks_madvised.remove(chunk);
+			}
+			arena->chunks_madvised.pushFront(chunk);
 		}
 #endif
 	}
 }
 
 static void
 arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
 {
@@ -4018,17 +4036,17 @@ arena_new(arena_t *arena)
 	if (malloc_spin_init(&arena->lock))
 		return (true);
 
 	memset(&arena->stats, 0, sizeof(arena_stats_t));
 
 	/* Initialize chunks. */
 	arena_chunk_tree_dirty_new(&arena->chunks_dirty);
 #ifdef MALLOC_DOUBLE_PURGE
-	LinkedList_Init(&arena->chunks_madvised);
+	new (&arena->chunks_madvised) mozilla::DoublyLinkedList<arena_chunk_t>();
 #endif
 	arena->spare = nullptr;
 
 	arena->ndirty = 0;
 
 	arena_avail_tree_new(&arena->runs_avail);
 
 	/* Initialize bins. */
@@ -5073,22 +5091,19 @@ hard_purge_chunk(arena_chunk_t *chunk)
 }
 
 /* Explicitly remove all of this arena's MADV_FREE'd pages from memory. */
 static void
 hard_purge_arena(arena_t *arena)
 {
 	malloc_spin_lock(&arena->lock);
 
-	while (!LinkedList_IsEmpty(&arena->chunks_madvised)) {
-		arena_chunk_t *chunk =
-			LinkedList_Get(arena->chunks_madvised.next,
-				       arena_chunk_t, chunks_madvised_elem);
+	while (!arena->chunks_madvised.isEmpty()) {
+		arena_chunk_t *chunk = arena->chunks_madvised.popFront();
 		hard_purge_chunk(chunk);
-		LinkedList_Remove(&chunk->chunks_madvised_elem);
 	}
 
 	malloc_spin_unlock(&arena->lock);
 }
 
 template<> inline void
 MozJemalloc::jemalloc_purge_freed_pages()
 {
--- a/mfbt/DoublyLinkedList.h
+++ b/mfbt/DoublyLinkedList.h
@@ -360,13 +360,26 @@ public:
 
   /**
    * Returns whether the given element is in the list. Note that this uses
    * T::operator==, not pointer comparison.
    */
   bool contains(const T& aElm) {
     return find(aElm) != Iterator();
   }
+
+  /**
+   * Returns whether the given element might be in the list. Note that this
+   * assumes the element is either in the list or not in the list, and ignores
+   * the case where the element might be in another list in order to make the
+   * check fast.
+   */
+  bool ElementProbablyInList(T* aElm) {
+    if (isEmpty()) {
+      return false;
+    }
+    return !ElementNotInList(aElm);
+  }
 };
 
 } // namespace mozilla
 
 #endif // mozilla_DoublyLinkedList_h