Bug 693404 - Part 1: On MacOS, add public jemalloc function to purge MADV_FREE'd pages, making our RSS reflect reality. r=khuey
authorJustin Lebar <justin.lebar@gmail.com>
Mon, 24 Oct 2011 13:23:47 -0400
changeset 79148 3db099ca452a6d1d063b4c824cc5fc6a4607be77
parent 79147 564e841f1f57234109ff6e071367bf0dd398bb1d
child 79149 2f7668cd67bcfb16f108352530c28783e010308e
push id1
push userroot
push dateMon, 20 Oct 2014 17:29:22 +0000
reviewerskhuey
bugs693404
milestone10.0a1
Bug 693404 - Part 1: On MacOS, add public jemalloc function to purge MADV_FREE'd pages, making our RSS reflect reality. r=khuey
memory/jemalloc/jemalloc.c
memory/jemalloc/jemalloc.h
memory/jemalloc/linkedlist.h
--- a/memory/jemalloc/jemalloc.c
+++ b/memory/jemalloc/jemalloc.c
@@ -1,10 +1,10 @@
 /* -*- Mode: C; tab-width: 8; c-basic-offset: 8; indent-tabs-mode: t -*- */
-/* vim:set softtabstop=8 shiftwidth=8: */
+/* vim:set softtabstop=8 shiftwidth=8 noet: */
 /*-
  * Copyright (C) 2006-2008 Jason Evans <jasone@FreeBSD.org>.
  * 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
@@ -101,16 +101,39 @@
  */
 
 #ifdef MOZ_MEMORY_ANDROID
 #define NO_TLS
 #define _pthread_self() pthread_self()
 #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
+ * RSS will decrease by 1MB (almost) immediately.
+ *
+ * On Mac, we use madvise(MADV_FREE).  Unlike MADV_DONTNEED on Linux, MADV_FREE
+ * on Mac doesn't cause the OS to release the specified pages immediately; the
+ * OS keeps them in our process until the machine comes under memory pressure.
+ *
+ * It's therefore difficult to measure the process's RSS on Mac, since, in the
+ * absence of memory pressure, the contribution from the heap to RSS will not
+ * decrease due to our madvise calls.
+ *
+ * We therefore define MALLOC_DOUBLE_PURGE on Mac.  This causes jemalloc to
+ * track which pages have been MADV_FREE'd.  You can then call
+ * jemalloc_purge_freed_pages(), which will force the OS to release those
+ * MADV_FREE'd pages, making the process's RSS reflect its true memory usage.
+ *
+ */
+#ifdef MOZ_MEMORY_DARWIN
+#define MALLOC_DOUBLE_PURGE
+#endif
+
+/*
  * MALLOC_PRODUCTION disables assertions and statistics gathering.  It also
  * defaults the A and J runtime options to off.  These settings are appropriate
  * for production systems.
  */
 #ifndef MOZ_MEMORY_DEBUG
 #  define	MALLOC_PRODUCTION
 #endif
 
@@ -349,16 +372,17 @@ typedef long ssize_t;
 
 #ifndef MOZ_MEMORY
 #include "un-namespace.h"
 #endif
 
 #endif
 
 #include "jemalloc.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
@@ -600,16 +624,21 @@ static const bool __isthreaded = true;
     * Threshold value for the exponential moving contention average at which to
     * re-assign a thread.
     */
 #  define BALANCE_THRESHOLD_DEFAULT	(1U << (SPIN_LIMIT_2POW-4))
 #endif
 
 /******************************************************************************/
 
+/* MALLOC_DECOMMIT and MALLOC_DOUBLE_PURGE are mutually exclusive. */
+#if defined(MALLOC_DECOMMIT) && defined(MALLOC_DOUBLE_PURGE)
+#error MALLOC_DECOMMIT and MALLOC_DOUBLE_PURGE are mutually exclusive.
+#endif
+
 /*
  * Mutexes based on spinlocks.  We can't use normal pthread spinlocks in all
  * places, because they require malloc()ed memory, which causes bootstrapping
  * issues in some cases.
  */
 #if defined(MOZ_MEMORY_WINDOWS)
 #define malloc_mutex_t CRITICAL_SECTION
 #define malloc_spinlock_t CRITICAL_SECTION
@@ -802,23 +831,24 @@ struct arena_chunk_map_s {
 	 *    runs, rather than directly embedding linkage.
 	 */
 	rb_node(arena_chunk_map_t)	link;
 
 	/*
 	 * Run address (or size) and various flags are stored together.  The bit
 	 * layout looks like (assuming 32-bit system):
 	 *
-	 *   ???????? ???????? ????---- --ckdzla
+	 *   ???????? ???????? ????---- -mckdzla
 	 *
 	 * ? : Unallocated: Run address for first/last pages, unset for internal
 	 *                  pages.
 	 *     Small: Run address.
 	 *     Large: Run size for first page, unset for trailing pages.
 	 * - : Unused.
+	 * m : MADV_FREE/MADV_DONTNEED'ed?
 	 * c : decommitted?
 	 * k : key?
 	 * d : dirty?
 	 * z : zeroed?
 	 * l : large?
 	 * a : allocated?
 	 *
 	 * Following are example bit patterns for the three types of runs.
@@ -840,18 +870,37 @@ struct arena_chunk_map_s {
 	 *     rrrrrrrr rrrrrrrr rrrr---- -------a
 	 *
 	 *   Large:
 	 *     ssssssss ssssssss ssss---- ------la
 	 *     -------- -------- -------- ------la
 	 *     -------- -------- -------- ------la
 	 */
 	size_t				bits;
-#if defined(MALLOC_DECOMMIT) || defined(MALLOC_STATS)
+
+/* Note that CHUNK_MAP_DECOMMITTED's meaning varies depending on whether
+ * MALLOC_DECOMMIT and MALLOC_DOUBLE_PURGE are defined.
+ *
+ * If MALLOC_DECOMMIT is defined, a page which is CHUNK_MAP_DECOMMITTED must be
+ * re-committed with pages_commit() before it may be touched.  If
+ * MALLOC_DECOMMIT is defined, MALLOC_DOUBLE_PURGE may not be defined.
+ *
+ * If neither MALLOC_DECOMMIT nor MALLOC_DOUBLE_PURGE is defined, pages which
+ * are madvised (with either MADV_DONTNEED or MADV_FREE) are marked with
+ * CHUNK_MAP_MADVISED.
+ *
+ * Otherwise, if MALLOC_DECOMMIT is not defined and MALLOC_DOUBLE_PURGE is
+ * defined, then a page which is madvised is marked as CHUNK_MAP_MADVISED.
+ * When it's finally freed with jemalloc_purge_freed_pages, the page is marked
+ * as CHUNK_MAP_DECOMMITTED.
+ */
+#if defined(MALLOC_DECOMMIT) || defined(MALLOC_STATS) || defined(MALLOC_DOUBLE_PURGE)
+#define	CHUNK_MAP_MADVISED	((size_t)0x40U)
 #define	CHUNK_MAP_DECOMMITTED	((size_t)0x20U)
+#define	CHUNK_MAP_MADVISED_OR_DECOMMITTED (CHUNK_MAP_MADVISED | CHUNK_MAP_DECOMMITTED)
 #endif
 #define	CHUNK_MAP_KEY		((size_t)0x10U)
 #define	CHUNK_MAP_DIRTY		((size_t)0x08U)
 #define	CHUNK_MAP_ZEROED	((size_t)0x04U)
 #define	CHUNK_MAP_LARGE		((size_t)0x02U)
 #define	CHUNK_MAP_ALLOCATED	((size_t)0x01U)
 };
 typedef rb_tree(arena_chunk_map_t) arena_avail_tree_t;
@@ -861,16 +910,26 @@ typedef rb_tree(arena_chunk_map_t) arena
 typedef struct arena_chunk_s arena_chunk_t;
 struct arena_chunk_s {
 	/* Arena that owns the chunk. */
 	arena_t		*arena;
 
 	/* Linkage for the arena's chunks_dirty tree. */
 	rb_node(arena_chunk_t) link_dirty;
 
+#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;
+#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;
 
@@ -946,16 +1005,22 @@ struct arena_s {
 
 #ifdef MALLOC_STATS
 	arena_stats_t		stats;
 #endif
 
 	/* 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;
+#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.
 	 *
 	 * There is one spare chunk per arena, rather than one spare total, in
 	 * order to avoid interactions between multiple threads that could make
@@ -1803,17 +1868,16 @@ malloc_printf(const char *format, ...)
 	vsnprintf(buf, sizeof(buf), format, ap);
 	va_end(ap);
 	_malloc_message(buf, "", "", "");
 }
 #endif
 
 /******************************************************************************/
 
-#ifdef MALLOC_DECOMMIT
 static inline void
 pages_decommit(void *addr, size_t size)
 {
 
 #ifdef MOZ_MEMORY_WINDOWS
 	VirtualFree(addr, size, MEM_DECOMMIT);
 #else
 	if (mmap(addr, size, PROT_NONE, MAP_FIXED | MAP_PRIVATE | MAP_ANON, -1,
@@ -1829,17 +1893,16 @@ pages_commit(void *addr, size_t size)
 #  ifdef MOZ_MEMORY_WINDOWS
 	VirtualAlloc(addr, size, MEM_COMMIT, PAGE_READWRITE);
 #  else
 	if (mmap(addr, size, PROT_READ | PROT_WRITE, MAP_FIXED | MAP_PRIVATE |
 	    MAP_ANON, -1, 0) == MAP_FAILED)
 		abort();
 #  endif
 }
-#endif
 
 static bool
 base_pages_alloc_mmap(size_t minsize)
 {
 	bool ret;
 	size_t csize;
 #if defined(MALLOC_DECOMMIT) || defined(MALLOC_STATS)
 	size_t pminsize;
@@ -3064,35 +3127,39 @@ arena_run_split(arena_t *arena, arena_ru
 		chunk->map[run_ind+total_pages-1].bits = (rem_pages <<
 		    pagesize_2pow) | (chunk->map[run_ind+total_pages-1].bits &
 		    pagesize_mask);
 		arena_avail_tree_insert(&arena->runs_avail,
 		    &chunk->map[run_ind+need_pages]);
 	}
 
 	for (i = 0; i < need_pages; i++) {
-#if defined(MALLOC_DECOMMIT) || defined(MALLOC_STATS)
+#if defined(MALLOC_DECOMMIT) || defined(MALLOC_STATS) || defined(MALLOC_DOUBLE_PURGE)
 		/*
 		 * Commit decommitted pages if necessary.  If a decommitted
 		 * page is encountered, commit all needed adjacent decommitted
 		 * pages in one operation, in order to reduce system call
 		 * overhead.
 		 */
-		if (chunk->map[run_ind + i].bits & CHUNK_MAP_DECOMMITTED) {
+		if (chunk->map[run_ind + i].bits & CHUNK_MAP_MADVISED_OR_DECOMMITTED) {
 			size_t j;
 
 			/*
 			 * Advance i+j to just past the index of the last page
-			 * to commit.  Clear CHUNK_MAP_DECOMMITTED along the
-			 * way.
+			 * to commit.  Clear CHUNK_MAP_DECOMMITTED and
+			 * CHUNK_MAP_MADVISED along the way.
 			 */
 			for (j = 0; i + j < need_pages && (chunk->map[run_ind +
-			    i + j].bits & CHUNK_MAP_DECOMMITTED); j++) {
-				chunk->map[run_ind + i + j].bits ^=
-				    CHUNK_MAP_DECOMMITTED;
+			    i + j].bits & CHUNK_MAP_MADVISED_OR_DECOMMITTED); j++) {
+				/* DECOMMITTED and MADVISED are mutually exclusive. */
+				assert(!(chunk->map[run_ind + i + j].bits & CHUNK_MAP_DECOMMITTED &&
+					 chunk->map[run_ind + i + j].bits & CHUNK_MAP_MADVISED));
+
+				chunk->map[run_ind + i + j].bits &=
+				    ~CHUNK_MAP_MADVISED_OR_DECOMMITTED;
 			}
 
 #  ifdef MALLOC_DECOMMIT
 			pages_commit((void *)((uintptr_t)chunk + ((run_ind + i)
 			    << pagesize_2pow)), (j << pagesize_2pow));
 #    ifdef MALLOC_STATS
 			arena->stats.ncommit++;
 #    endif
@@ -3199,31 +3266,39 @@ arena_chunk_init(arena_t *arena, arena_c
 #endif
 #ifdef MALLOC_STATS
 	arena->stats.committed += arena_chunk_header_npages;
 #endif
 
 	/* Insert the run into the runs_avail tree. */
 	arena_avail_tree_insert(&arena->runs_avail,
 	    &chunk->map[arena_chunk_header_npages]);
+
+	LinkedList_Init(&chunk->chunks_madvised_elem);
 }
 
 static void
 arena_chunk_dealloc(arena_t *arena, arena_chunk_t *chunk)
 {
 
 	if (arena->spare != NULL) {
 		if (arena->spare->ndirty > 0) {
 			arena_chunk_tree_dirty_remove(
 			    &chunk->arena->chunks_dirty, arena->spare);
 			arena->ndirty -= arena->spare->ndirty;
 #ifdef MALLOC_STATS
 			arena->stats.committed -= arena->spare->ndirty;
 #endif
 		}
+
+#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);
+#endif
+
 		VALGRIND_FREELIKE_BLOCK(arena->spare, 0);
 		chunk_dealloc((void *)arena->spare, chunksize);
 #ifdef MALLOC_STATS
 		arena->stats.mapped -= chunksize;
 		arena->stats.committed -= arena_chunk_header_npages;
 #endif
 	}
 
@@ -3317,34 +3392,43 @@ arena_purge(arena_t *arena)
 
 	/*
 	 * Iterate downward through chunks until enough dirty memory has been
 	 * purged.  Terminate as soon as possible in order to minimize the
 	 * number of system calls, even if a chunk has only been partially
 	 * purged.
 	 */
 	while (arena->ndirty > (opt_dirty_max >> 1)) {
+#ifdef MALLOC_DOUBLE_PURGE
+		bool madvised = false;
+#endif
 		chunk = arena_chunk_tree_dirty_last(&arena->chunks_dirty);
 		assert(chunk != NULL);
 
 		for (i = chunk_npages - 1; chunk->ndirty > 0; i--) {
 			assert(i >= arena_chunk_header_npages);
 
 			if (chunk->map[i].bits & CHUNK_MAP_DIRTY) {
+#ifdef MALLOC_DECOMMIT
+				const size_t free_operation = CHUNK_MAP_DECOMMITTED;
+#else
+				const size_t free_operation = CHUNK_MAP_MADVISED;
+#endif
 				assert((chunk->map[i].bits &
-				    CHUNK_MAP_DECOMMITTED) == 0);
-				chunk->map[i].bits ^= CHUNK_MAP_DECOMMITTED | CHUNK_MAP_DIRTY;
+				        CHUNK_MAP_MADVISED_OR_DECOMMITTED) == 0);
+				chunk->map[i].bits ^= free_operation | CHUNK_MAP_DIRTY;
 				/* Find adjacent dirty run(s). */
-				for (npages = 1; i > arena_chunk_header_npages
-				    && (chunk->map[i - 1].bits &
-				    CHUNK_MAP_DIRTY); npages++) {
+				for (npages = 1;
+				     i > arena_chunk_header_npages &&
+				       (chunk->map[i - 1].bits & CHUNK_MAP_DIRTY);
+				     npages++) {
 					i--;
 					assert((chunk->map[i].bits &
-					    CHUNK_MAP_DECOMMITTED) == 0);
-					chunk->map[i].bits ^= CHUNK_MAP_DECOMMITTED | CHUNK_MAP_DIRTY;
+					        CHUNK_MAP_MADVISED_OR_DECOMMITTED) == 0);
+					chunk->map[i].bits ^= free_operation | CHUNK_MAP_DIRTY;
 				}
 				chunk->ndirty -= npages;
 				arena->ndirty -= npages;
 
 #ifdef MALLOC_DECOMMIT
 				pages_decommit((void *)((uintptr_t)
 				    chunk + (i << pagesize_2pow)),
 				    (npages << pagesize_2pow));
@@ -3356,30 +3440,41 @@ arena_purge(arena_t *arena)
 #ifdef MALLOC_STATS
 				arena->stats.committed -= npages;
 #endif
 
 #ifndef MALLOC_DECOMMIT
 				madvise((void *)((uintptr_t)chunk + (i <<
 				    pagesize_2pow)), (npages << pagesize_2pow),
 				    MADV_FREE);
+#  ifdef MALLOC_DOUBLE_PURGE
+				madvised = true;
+#  endif
 #endif
 #ifdef MALLOC_STATS
 				arena->stats.nmadvise++;
 				arena->stats.purged += npages;
 #endif
 				if (arena->ndirty <= (opt_dirty_max >> 1))
 					break;
 			}
 		}
 
 		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);
+		}
+#endif
 	}
 }
 
 static void
 arena_run_dalloc(arena_t *arena, arena_run_t *run, bool dirty)
 {
 	arena_chunk_t *chunk;
 	size_t size, run_ind, run_pages;
@@ -4557,16 +4652,19 @@ arena_new(arena_t *arena)
 		return (true);
 
 #ifdef MALLOC_STATS
 	memset(&arena->stats, 0, sizeof(arena_stats_t));
 #endif
 
 	/* Initialize chunks. */
 	arena_chunk_tree_dirty_new(&arena->chunks_dirty);
+#ifdef MALLOC_DOUBLE_PURGE
+	LinkedList_Init(&arena->chunks_madvised);
+#endif
 	arena->spare = NULL;
 
 	arena->ndirty = 0;
 
 	arena_avail_tree_new(&arena->runs_avail);
 
 #ifdef MALLOC_BALANCE
 	arena->contention = 0;
@@ -6376,16 +6474,88 @@ jemalloc_stats(jemalloc_stats_t *stats)
 			malloc_spin_unlock(&arena->lock);
 		}
 	}
 
 	assert(stats->mapped >= stats->committed);
 	assert(stats->committed >= stats->allocated);
 }
 
+#ifdef MALLOC_DOUBLE_PURGE
+
+/* Explicitly remove all of this chunk's MADV_FREE'd pages from memory. */
+static void
+hard_purge_chunk(arena_chunk_t *chunk)
+{
+	/* See similar logic in arena_purge(). */
+
+	size_t i;
+	for (i = arena_chunk_header_npages; i < chunk_npages; i++) {
+		/* Find all adjacent pages with CHUNK_MAP_MADVISED set. */
+		size_t npages;
+		for (npages = 0;
+		     chunk->map[i + npages].bits & CHUNK_MAP_MADVISED && i + npages < chunk_npages;
+		     npages++) {
+			/* Turn off the chunk's MADV_FREED bit and turn on its
+			 * DECOMMITTED bit. */
+			assert(!(chunk->map[i + npages].bits & CHUNK_MAP_DECOMMITTED));
+			chunk->map[i + npages].bits ^= CHUNK_MAP_MADVISED_OR_DECOMMITTED;
+		}
+
+		/* We could use mincore to find out which pages are actually
+		 * present, but it's not clear that's better. */
+		if (npages > 0) {
+			pages_decommit(((char*)chunk) + (i << pagesize_2pow), npages << pagesize_2pow);
+			pages_commit(((char*)chunk) + (i << pagesize_2pow), npages << pagesize_2pow);
+		}
+		i += npages;
+	}
+}
+
+/* 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)) {
+		LinkedList* next = arena->chunks_madvised.next;
+		arena_chunk_t *chunk =
+			LinkedList_Get(arena->chunks_madvised.next,
+				       arena_chunk_t, chunks_madvised_elem);
+		hard_purge_chunk(chunk);
+		LinkedList_Remove(&chunk->chunks_madvised_elem);
+	}
+
+	malloc_spin_unlock(&arena->lock);
+}
+
+void
+jemalloc_purge_freed_pages()
+{
+	size_t i;
+	for (i = 0; i < narenas; i++) {
+		arena_t *arena = arenas[i];
+		if (arena != NULL)
+			hard_purge_arena(arena);
+	}
+}
+
+#else /* !defined MALLOC_DOUBLE_PURGE */
+
+void
+jemalloc_purge_freed_pages()
+{
+	/* Do nothing. */
+}
+
+#endif /* defined MALLOC_DOUBLE_PURGE */
+
+
+
 #ifdef MOZ_MEMORY_WINDOWS
 void*
 _recalloc(void *ptr, size_t count, size_t size)
 {
 	size_t oldsize = (ptr != NULL) ? isalloc(ptr) : 0;
 	size_t newsize = count * size;
 
 	/*
--- a/memory/jemalloc/jemalloc.h
+++ b/memory/jemalloc/jemalloc.h
@@ -75,13 +75,40 @@ size_t	je_malloc_usable_size(const void 
 /* Linux has memalign and malloc_usable_size */
 #if !defined(MOZ_MEMORY_LINUX)
 void	*memalign(size_t alignment, size_t size);
 size_t	malloc_usable_size(const void *ptr);
 #endif /* MOZ_MEMORY_LINUX */
 
 void	jemalloc_stats(jemalloc_stats_t *stats);
 
+/*
+ * On some operating systems (Mac), we use madvise(MADV_FREE) to hand pages
+ * back to the operating system.  On Mac, the operating system doesn't take
+ * this memory back immediately; instead, the OS takes it back only when the
+ * machine is running out of physical memory.
+ *
+ * This is great from the standpoint of efficiency, but it makes measuring our
+ * actual RSS difficult, because pages which we've MADV_FREE'd shouldn't count
+ * against our RSS.
+ *
+ * This function explicitly purges any MADV_FREE'd pages from physical memory,
+ * causing our reported RSS match the amount of memory we're actually using.
+ *
+ * Note that this call is expensive in two ways.  First, it may be slow to
+ * execute, because it may make a number of slow syscalls to free memory.  This
+ * function holds the big jemalloc locks, so basically all threads are blocked
+ * while this function runs.
+ *
+ * This function is also expensive in that the next time we go to access a page
+ * which we've just explicitly decommitted, the operating system has to attach
+ * to it a physical page!  If we hadn't run this function, the OS would have
+ * less work to do.
+ *
+ * If MALLOC_DOUBLE_PURGE is not defined, this function does nothing.
+ */
+void    jemalloc_purge_freed_pages();
+
 #ifdef __cplusplus
 } /* extern "C" */
 #endif
 
 #endif /* _JEMALLOC_H_ */
new file mode 100644
--- /dev/null
+++ b/memory/jemalloc/linkedlist.h
@@ -0,0 +1,77 @@
+/* -*- 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>
+
+typedef struct LinkedList_s LinkedList;
+
+struct LinkedList_s {
+	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