Bug 1396723 - Use DoublyLinkedList in mozjemalloc. r=froydnj
☠☠ backed out by bc13c43f6771 ☠ ☠
authorMike Hommey <mh+mozilla@glandium.org>
Sat, 02 Sep 2017 08:55:42 +0900
changeset 660388 1c0f9d069aded626bdd92b80996470ea778c8d9d
parent 660387 6ca94a450b810dce5cbb82b2fa13f3a34630a27b
child 660389 ad5c7dbaa4d6c2f31c3b5a89c159f781a2f92902
push id78390
push userbmo:emilio@crisal.io
push dateWed, 06 Sep 2017 23:04:15 +0000
reviewersfroydnj
bugs1396723
milestone57.0a1
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,38 @@ 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
+template<>
+struct mozilla::GetDoublyLinkedListElement<arena_chunk_t>
+{
+  static mozilla::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 +715,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 +2705,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 +2885,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 +4032,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 +5087,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
@@ -353,13 +353,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