Mesh: Compacting Memory Management

for C/C++ Applications

Bobby Powers David Tench
College of Information and Computer Sciences College of Information and Computer Sciences
University of Massachusetts Amherst University of Massachusetts Amherst
Amherst, MA, USA Amherst, MA, USA
bpowers@[Link] dtench@[Link]

Emery D. Berger Andrew McGregor

College of Information and Computer Sciences College of Information and Computer Sciences
arXiv:1902.04738v2 [[Link]] 16 Feb 2019

University of Massachusetts Amherst University of Massachusetts Amherst

Amherst, MA, USA Amherst, MA, USA
emery@[Link] mcgregor@[Link]

Abstract integers, store flags in the low bits of aligned addresses, per-
Programs written in C/C++ can suffer from serious memory form arithmetic on addresses and later reference them, or
fragmentation, leading to low utilization of memory, de- even store addresses to disk and later reload them. This
graded performance, and application failure due to memory hostile environment makes it impossible to safely relocate
exhaustion. This paper introduces Mesh, a plug-in replace- objects: if an object is relocated, all pointers to its original
ment for malloc that, for the first time, eliminates fragmen- location must be updated. However, there is no way to safely
tation in unmodified C/C++ applications. Mesh combines update every reference when they are ambiguous, much less
novel randomized algorithms with widely-supported virtual when they are absent.
memory operations to provably reduce fragmentation, break- Existing memory allocators for C/C++ employ a variety of
ing the classical Robson bounds with high probability. Mesh best-effort heuristics aimed at reducing average fragmenta-
generally matches the runtime performance of state-of-the- tion [17]. However, these approaches are inherently limited.
art memory allocators while reducing memory consumption; In a classic result, Robson showed that all such allocators can
in particular, it reduces the memory of consumption of Fire- suffer from catastrophic memory fragmentation [26]. This
fox by 16% and Redis by 39%. increase in memory consumption can be as high as the log
of the ratio between the largest and smallest object sizes allo-
CCS Concepts • Software and its engineering → Allo- cated. For example, for an application that allocates 16-byte
cation / deallocation strategies; and 128KB objects, it is possible for it to consume 13× more
Keywords Memory management, runtime systems, un- memory than required.
managed languages Despite nearly fifty years of conventional wisdom indicat-
ing that compaction is impossible in unmanaged languages,
1 Introduction this paper shows that it is not only possible but also practical.
It introduces Mesh, a memory allocator that effectively and
Memory consumption is a serious concern across the spec- efficiently performs compacting memory management to
trum of modern computing platforms, from mobile to desk- reduce memory usage in unmodified C/C++ applications.
top to datacenters. For example, on low-end Android devices, Crucially and counterintuitively, Mesh performs com-
Google reports that more than 99 percent of Chrome crashes paction without relocation; that is, without changing the
are due to running out of memory when attempting to dis- addresses of objects. This property is vital for compatibility
play a web page [15]. On desktops, the Firefox web browser with arbitrary C/C++ applications. To achieve this, Mesh
has been the subject of a five-year effort to reduce its memory builds on a mechanism which we call meshing, first intro-
footprint [28]. In datacenters, developers implement a range duced by Novark et al.’s Hound memory leak detector [23].
of techniques from custom allocators to other ad hoc ap- Hound employed meshing in an effort to avoid catastrophic
proaches in an effort to increase memory utilization [25, 27]. memory consumption induced by its memory-inefficient allo-
A key challenge is that, unlike in garbage-collected en- cation scheme, which can only reclaim memory when every
vironments, automatically reducing a C/C++ application’s object on a page is freed. Hound first searches for pages
memory footprint via compaction is not possible. Because whose live objects do not overlap. It then copies the contents
the addresses of allocated objects are directly exposed to of one page onto the other, remaps one of the virtual pages
programmers, C/C++ applications can freely modify or hide to point to the single physical page now holding the contents
addresses. For example, a program may stash addresses in
 Bobby Powers, David Tench, Emery D. Berger, and Andrew McGregor

free free

allocated allocated

virtual memory virtual memory

physical memory physical memory

munmap

(a) Before: these pages are candidates for “meshing” (b) After: both virtual pages now point to the first physical page;
because their allocated objects do not overlap. the second page is now freed.

Figure 1. Mesh in action. Mesh employs novel randomized algorithms that let it efficiently find and then “mesh” candidate
pages within spans (contiguous 4K pages) whose contents do not overlap. In this example, it increases memory utilization
across these pages from 37.5% to 75%, and returns one physical page to the OS (via munmap), reducing the overall memory
footprint. Mesh’s randomized allocation algorithm ensures meshing’s effectiveness with high probability.
of both pages, and finally relinquishes the other physical export LD_PRELOAD=[Link]). Our empirical evalua-
page to the OS. Figure 1 illustrates meshing in action. tion demonstrates that our implementation of Mesh is both
Mesh overcomes two key technical challenges of mesh- fast and efficient in practice. It generally matches the per-
ing that previously made it both inefficient and potentially formance of state-of-the-art allocators while guaranteeing
entirely ineffective. First, Hound’s search for pages to mesh the absence of catastrophic fragmentation with high prob-
involves a linear scan of pages on calls to free. While this ability. In addition, it occasionally yields substantial space
search is more efficient than a naive O(n 2 ) search of all possi- savings: replacing the standard allocator with Mesh auto-
ble pairs of pages, it remains prohibitively expensive for use matically reduces memory consumption by 16% (Firefox) to
in the context of a general-purpose allocator. Second, Hound 39% (Redis).
offers no guarantees that any pages would ever be meshable.
Consider an application that happens to allocate even one 1.1 Contributions
object in the same offset in every page. That layout would This paper makes the following contributions:
preclude meshing altogether, eliminating the possibility of
saving any space. • It introduces Mesh, a novel memory allocator that acts
Mesh makes meshing both efficient and provably effec- as a plug-in replacement for malloc. Mesh combines
tive (with high probability) by combining it with two novel remapping of virtual to physical pages (meshing) with
randomized algorithms. First, Mesh uses a space-efficient randomized allocation and search algorithms to enable
randomized allocation strategy that effectively scatters ob- safe and effective compaction without relocation for
jects within each virtual page, making the above scenario C/C++ (§2, §3, §4).
provably exceedingly unlikely. Second, Mesh incorporates • It presents theoretical results that guarantee Mesh’s
an efficient randomized algorithm that is guaranteed with efficiency and effectiveness with high probability (§5).
high probability to quickly find candidate pages that are • It evaluates Mesh’s performance empirically, demon-
likely to mesh. These two algorithms work in concert to en- strating Mesh’s ability to reduce space consumption
able formal guarantees on Mesh’s effectiveness. Our analysis while generally imposing low runtime overhead (§6).
shows that Mesh breaks the above-mentioned Robson worst
case bounds for fragmentation with high probability [26]. 2 Overview
We implement Mesh as a library for C/C++ applications This section provides a high-level overview of how Mesh
running on Linux of Mac OS X. Mesh interposes on memory works and gives some intuition as to how its algorithms
management operations, making it possible to use it without and implementation ensure its efficiency and effectiveness,
code changes or even recompilation by setting the appro- before diving into detailed description of Mesh’s algorithms
priate environment variable to load the Mesh library (e.g., (§3), implementation (§4), and its theoretical analysis (§5).
Mesh

2.1 Remapping Virtual Pages 2.3 Finding Spans to Mesh

Mesh enables compaction without relocating object ad- Given a set of spans, our goal is to mesh them in a way that
dresses; it depends only on hardware-level virtual memory frees as many physical pages as possible. We can think of
support, which is standard on most computing platforms this task as that of partitioning the spans into subsets such
like x86 and ARM64. Mesh works by finding pairs of pages that the spans in each subset mesh. An optimal partition
and merging them together physically but not virtually: this would minimize the number of such subsets.
merging lets it relinquish physical pages to the OS. Unfortunately, as we show, optimal meshing is not feasible
Meshing is only possible when no objects on the pages (§5). Instead, the algorithms in Section 3 present practical
occupy the same offsets. A key observation is that as frag- methods for finding high-quality meshes under real-world
mentation increases (that is, as there are more free objects), time constraints. We show that solving a simplified version
the likelihood of successfully finding pairs of pages that mesh of the problem (§3) is sufficient to achieve reasonable meshes
also increases. with high probability (§5).
Figure 1 schematically illustrates the meshing process.
Mesh manages memory at the granularity of spans, which 3 Algorithms
are runs of contiguous 4K pages (for purposes of illustration, Mesh comprises three main algorithmic components: allo-
the figure shows single-page spans). Each span only contains cation (§3.1), deallocation (§3.2), and finding spans to mesh
same-sized objects. The figure shows two spans of memory (§3.3). Unless otherwise noted and without loss of generality,
with low utilization (each is under 40% occupied) and whose all algorithms described here are per size class (within spans,
allocations are at non-overlapping offsets. all objects are same size).
Meshing consolidates allocations from each span onto one
physical span. Each object in the resulting meshed span re- 3.1 Allocation
sides at the same offset as it did in its original span; that is,
Allocation in Mesh consists of two steps: (1) finding a span
its virtual addresses are preserved, making meshing invisible
to allocate from, and (2) randomly allocating an object from
to the application. Meshing then updates the virtual-to-
that span. Mesh always allocates from a thread-local shuffle
physical mapping (the page tables) for the process so that
vector – a randomized version of a freelist (described in detail
both virtual spans point to the same physical span. The
in §4.2). The shuffle vector contains offsets corresponding
second physical span is returned to the OS. When average
to the slots of a single span. We call that span the attached
occupancy is low, meshing can consolidate many pages, of-
span for a given thread.
fering the potential for considerable space savings.
If the shuffle vector is empty, Mesh relinquishes the cur-
rent thread’s attached span (if one exists) to the global heap
2.2 Random Allocation (which holds all unattached spans), and asks it to select a
new span. If there are no partially full spans, the global heap
A key threat to meshing is that pages could contain objects at returns a new, empty span. Otherwise, it selects a partially
the same offset, preventing them from being meshed. In the full span for reuse. To maximize utilization, the global heap
worst case, all spans would have only one allocated object, groups spans into bins organized by decreasing occupancy
each at the same offset, making them non-meshable. Mesh (e.g., 75-99% full in one bin, 50-74% in the next). The global
employs randomized allocation to make this worst-case be- heap scans for the first non-empty bin (by decreasing occu-
havior exceedingly unlikely. It allocates objects uniformly pancy), and randomly selects a span from that bin.
at random across all available offsets in a span. As a result, Once a span has been selected, the allocator adds the
the probability that all objects will occupy the same offset is offsets corresponding to the free slots in that span to the
(1/b)n−1 , where b is the number of objects in a span, and n thread-local shuffle vector (in a random order). Mesh pops
is the number of spans. the first entry off the shuffle vector and returns it.
In practice, the resulting probability of being unable to
mesh many pages is vanishingly small. For example, when 3.2 Deallocation
meshing 64 spans with one 16-byte object allocated on each
Deallocation behaves differently depending on whether the
(so that the number of objects b in a 4K span is 256), the
free is local (the address belongs to the current thread’s
likelihood of being unable to mesh any of these spans is
attached span), remote (the object belongs to another thread’s
10−152 . To put this into perspective, there are estimated to
attached span), or if it belongs to the global heap.
be roughly 1082 particles in the universe.
For local frees, Mesh adds the object’s offset onto the
We use randomness to guide the design of Mesh’s algo-
span’s shuffle vector in a random position and returns. For
rithms (§3) and implementation (§4); this randomization lets
remote frees, Mesh atomically resets the bit in the corre-
us prove robust guarantees of its performance (§5), showing
sponding index in a bitmap associated with each span. Fi-
that Mesh breaks the Robson bounds with high probability.
nally, for an object belonging to the global heap, Mesh marks
 Bobby Powers, David Tench, Emery D. Berger, and Andrew McGregor

SplitMesher(S, t) Mesh uses the same size classes correspond to those used by
1 n = length(S) jemalloc for objects 1024 bytes and smaller [11], and power-
2 Sl , Sr = S[1 : n/2], S[n/2 + 1 : n] of-two size classes for objects between 1024 and 16K. Alloca-
3 for (i = 0, i < t, i + +) tions are fulfilled from the smallest size class they fit in (e.g.,
4 len = |Sl | objects of size 33–48 bytes are served from the 48-byte size
5 for (j = 0, j < len, j + +) class); objects larger than 16K are individually fulfilled from
6 if Meshable (Sl (j), Sr (j + i % len)) the global arena. Small objects are allocated out of spans (§2),
7 Sl ← Sl \ Sl (j) which are multiples of the page size and contain between 8
8 Sr ← Sr \ Sr (j + i % len) and 256 objects of a fixed size. Having at least eight objects
9 mesh(Sl (j), Sr (j + i % len)) per span helps amortize the cost of reserving memory from
the global manager for the current thread’s allocator.
Figure 2. Meshing random pairs of spans. SplitMesher Objects of 4KB and larger are always page-aligned and
splits the randomly ordered span list S into halves, then span at least one entire page. Mesh does not consider these
probes pairs between halves for meshes. Each span is probed objects for meshing; instead, the pages are directly freed to
up to t times. the OS.
Mesh’s heap organization consists of four main compo-
the object as free, updates the span’s occupancy bin; this nents. MiniHeaps track occupancy and other metadata for
action may additionally trigger meshing. spans (§4.1). Shuffle vectors enable efficient, random allo-
cation out of a MiniHeap (§4.2). Thread local heaps satisfy
3.3 Meshing
small-object allocation requests without the need for locks
When meshing, Mesh randomly chooses pairs of spans and or atomic operations in the common case (§4.3). Finally,
attempts to mesh each pair. The meshing algorithm, which the global heap (§4.4) manages runtime state shared by all
we call SplitMesher (Figure 2), is designed both for practical threads, large object allocation, and coordinates meshing
effectiveness and for its theoretical guarantees. The parame- operations (§4.5).
ter t, which determines the maximum number of times each
span is probed (line 3), enables space-time trade-offs. The 4.1 MiniHeaps
parameter t can be increased to improve mesh quality and
therefore reduce space, or decreased to improve runtime, at MiniHeaps manage allocated physical spans of memory and
the cost of sacrificed meshing opportunities. We empirically are either attached or detached. An attached MiniHeap is
found that t = 64 balances runtime and meshing effective- owned by a specific thread-local heap, while a detached Mini-
ness, and use this value in our implementation. Heap is only referenced through the global heap. New small
SplitMesher proceeds by iterating through Sl and check- objects are only allocated out of attached MiniHeaps.
ing whether it can mesh each span with another span chosen Each MiniHeap contains metadata that comprises span
from Sr (line 6). If so, it removes these spans from their length, object size, allocation bitmap, and the start addresses
respective lists and meshes them (lines 7–9). SplitMesher of any virtual spans meshed to a unique physical span. The
repeats until it has checked t ∗ |Sl | pairs of spans; §4.5 de- number of objects that can be allocated from a MiniHeap
scribes the implementation of SplitMesher in detail. bitmap is objectCount = spanSize / objSize. The allocation
bitmap is initialized to objectCount zero bits.
4 Implementation When a MiniHeap is attached to a thread-local shuffle vec-
tor (§4.2), each offset that is unset in the MiniHeap’s bitmap
We implement Mesh as a drop-in replacement memory allo-
is added to the shuffle vector, with that bit now atomically
cator that implements meshing for single or multi-threaded
set to one in the bitmap. This approach is designed to allow
applications written in C/C++. Its current implementation
multiple threads to free objects which keeping most memory
work for 64-bit Linux and Mac OS X binaries. Mesh can be ex-
allocation operations local in the common case.
plicitly linked against by passing -lmesh to the linker at com-
When an object is freed and the free is non-local (§3.2),
pile time, or loaded dynamically by setting the LD_PRELOAD
the bit is reset. When a new MiniHeap is allocated, there
(Linux) or DYLD_INSERT_LIBRARIES (Mac OS X) environ-
is only one virtual span that points to the physical memory
ment variables to point to the Mesh library. When loaded,
it manages. After meshing, there may be multiple virtual
Mesh interposes on standard libc functions to replace all
spans pointing to the MiniHeap’s physical memory.
memory allocation functions.
Mesh combines traditional allocation strategies with
4.2 Shuffle Vectors
meshing to minimize heap usage. Like most modern memory
allocators [2, 3, 11, 13, 22], Mesh is a segregated-fit allocator. Shuffle vectors are a novel data structure that lets Mesh
Mesh employs fine-grained size classes to reduce internal perform randomized allocation out of a MiniHeap efficiently
fragmentation due to rounding up to the nearest size class. and with low space overhead.
Mesh

selecting the next available number in the vector, “bump-

3 0 2 7 6 1 5 4 ing” the allocation index and returning the corresponding
address. Deallocation works by placing the freed object at
the front of the vector and performing one iteration of the
shuffle algorithm; this operation preserves randomization
(a) A shuffle vector for a span of size 8, where no objects of the vector. Figure 3 illustrates this process, while Fig-
have yet been allocated. ure 4 has pseudocode listings for initialization, allocation,
and deallocation.
0 2 7 6 1 5 4 Shuffle vectors impose far less space overhead than ran-
dom probing. First, with a maximum of 256 objects in a span,
each offset in the vector can be represented as an unsigned
character (a single byte). Second, because Mesh needs only
(b) The shuffle vector after the first object has been allo- one shuffle vector per attached MiniHeap, the amount of
cated. memory required for vectors is 256c, where c is the number
of size classes (24 in the current implementation): roughly
3 0 2 7 6 1 5 4 2.8K per thread. Finally, shuffle vectors are only ever ac-
cessed from a single thread, and so do not require locks or
atomic operations. While bitmaps must be operated on atom-
ically (frees may originate at any time from other threads),
(c) On free, the object’s offset is pushed onto the front of shuffle vectors are only accessed from a single thread and
the vector, the allocation index is updated, and the offset do not require synchronization or cache-line flushes.
is swapped with a randomly chosen offset.
4.3 Thread Local Heaps
1 0 2 7 6 3 5 4 All malloc and free requests from an application start at the
thread’s local heap. Thread local heaps have shuffle vectors
for each size class, a reference to the global heap, and their
own thread-local random number generator.
(d) Finally, after the swap, new allocations proceed in a
Allocation requests are handled differently depending on
bump-pointer like fashion.
the size of the allocation. If an allocation request is larger
Figure 3. Shuffle vectors compactly enable fast random than 16K, it is forwarded to the global heap for fulfillment
allocation. Indices (one byte each) are maintained in random (§4.4). Allocation requests 16K and smaller are small object
order; allocation is popping, and deallocation is pushing plus allocations and are handled directly by the shuffle vector
a random swap (§4.2). for the size class corresponding to the allocation request, as
in Figure 4a. If the shuffle vector is empty, it is refilled by
Previous memory allocators that have employed random- requesting an appropriately sized MiniHeap from the global
ization (for security or reliability) perform randomized al- heap. This MiniHeap is a partially-full MiniHeap if one exists,
location by random probing into bitmaps [3, 22]. In these or represents a freshly-allocated span if no partially full ones
allocators, a memory allocation request chooses a random are available for reuse. Frees, as in Figure 4d, first check if
number in the range [0, objectCount − 1]. If the associated the object is from an attached MiniHeap. If so, it is handled
bit is zero in the bitmap, the allocator sets it to one and re- by the appropriate shuffle vector, otherwise it is passed to
turns the address of the corresponding offset. If the offset is the global heap to handle.
already one, meaning that the object is in use, a new random
number is chosen and the process repeated. Random probing 4.4 Global Heap
allocates objects in O(1) expected time but requires overprovi- The global heap allocates MiniHeaps for thread-local heaps,
sioning memory by a constant factor (e.g., 2× more memory handles all large object allocations, performs non-local frees
must be allocated than needed). This overprovisioning is at for both small and large objects, and coordinates meshing.
odds with our goal of reducing space overhead.
Shuffle vectors solve this problem, combining low space 4.4.1 The Meshable Arena
overhead with worst-case O(1) running time for malloc and The global heap allocates meshable spans and large objects
free. Each comprises a fixed-size array consisting of all the from a single, global meshable arena. This arena contains
offsets from a span that are not already allocated, and an two sets of bins for same-length spans — one set is for de-
allocation index representing the head. Each vector is ini- mand zero-ed spans (freshly mmapped), and the other for used
tially randomized with the Knuth-Fischer-Yates shuffle [18], spans — and a mapping of page offsets from the start of the
and its allocation index is set to 0. Allocation proceeds by arena to their owning MiniHeap pointers. Used pages are
 Bobby Powers, David Tench, Emery D. Berger, and Andrew McGregor

not immediately returned to the OS as they are likely to void *MeshLocal::malloc(size_t sz) {
be needed again soon, and reclamation is relatively expen- int szClass;
sive. Only after 64MB of used pages have accumulated, or // forward to global heap if large
whenever meshing is invoked, Mesh returns pages to OS by if (!getSizeClass(sz, &szClass))
calling fallocate on the heap’s file descriptor (§4.5.1) with return _global->malloc(sz);
the FALLOC_FL_PUNCH_HOLE flag. auto shufVec = _shufVecs[szClass];
if ([Link]()) {
4.4.2 MiniHeap allocation [Link]();
[Link](
Allocating a MiniHeap of size k pages begins with requesting
_global->allocMiniheap(szClass));}
k pages from the meshable arena. The global allocator then
return [Link]();
allocates and initializes a new MiniHeap instance from an }
internal allocator that Mesh uses for its own needs. This
MiniHeap is kept live so long as the number of allocated void ShuffleVector::attach(MiniHeap *mh){
objects remains non-zero, and singleton MiniHeaps are used _mh = mh;
to account for large object allocations. Finally, the global al- _off = maxCount();
locator updates the mapping of offsets to MiniHeaps for each for (auto i = 0; i < maxCount(); i++){
of the k pages to point at the address of the new MiniHeap. // true if atomically set (0 -> 1)
if ([Link](i)) {
4.4.3 Large objects _list[_off--] = i;
} }
All large allocation requests (greater than 16K) are directly
shuffle(_list[_off],
handled by the global heap. Large allocation requests are
_list[maxCount()]);
rounded up to the nearest multiple of the hardware page size }
(4K on x86_64), and a MiniHeap for 1 object of that size is
requested, as detailed above. The start of the span tracked void *ShuffleVector::malloc() {
by that MiniHeap is returned to the program as the result of const auto off = _list[_off++];
the malloc call. return _spanStart + off * _objSize;
}
4.4.4 Non-local frees
If free is called on a pointer that is not contained in an void MeshLocal::free(void *ptr) {
attached MiniHeap for that thread, the free is handled by // check if in attached MiniHeap
for (auto i=0; i<SizeClassCount; i++){
the global heap. Non-local frees occur when the thread that
const auto curr = _shufVecs[i];
frees the object is different from the thread that allocated
if (curr->contains(ptr)) {
it, or if there have been sufficient allocations on the current curr->free(ptr);
thread that the original MiniHeap was exhaused and a new return; } }
MiniHeap for that size class was attached. _global->free(ptr); // general case
Looking up the owning MiniHeap for a pointer is a con- }
stant time operation. The pointer is checked to ensure it falls
within the arena, the arena start address is subtracted from void ShuffleVector::free(void *ptr) {
it, and the result is divided by the page size. The resulting const auto freedOff = getOff(ptr);
offset is then used to index into a table of MiniHeap pointers. _list[--_off] = freedOff;
If the result is zero, the pointer is invalid (memory manage- // place newly freed address
// randomly in the shuffle vector
ment errors like double-frees are thus easily discovered and
auto swapOff =
discarded); otherwise, it points to a live MiniHeap.
_rng.inRange(_off, maxCount() - 1);
Once the owning MiniHeap has been found, that Mini- swap(_list[_off], _list[swapOff]);
Heap’s bitmap is updated atomically in a compare-and-set }
loop. If a free occurs for an object where the owning Mini-
Heap is attached to a different thread, the free atomically
updates that MiniHeap’s bitmap, but does not update the Figure 4. Pseudocode for Mesh’s core allocation and deallo-
other thread’s corresponding shuffle vector. cation routines.
4.5 Meshing Meshing is rate limited by a configurable parameter, set-
Mesh’s implementation of meshing is guided by theoretical table at program startup and during runtime by the applica-
results (described in detail in Section 5) that enable it to tion through the semi-standard mallctl API. The default
efficiently find a number of spans that can be meshed. rate meshes at most once every tenth of a second. If the last
Mesh

meshing freed less than one MB of heap space, the timer is

not restarted until a subsequent allocation is freed through
0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0
the global heap. This approach ensures that Mesh does not
waste time searching for meshes when the application and
heap are in a steady state.
We implement the SplitMesher algorithm from Section 3
in C++ to find meshes. Meshing proceeds one size class at a
time. Pairs of mesh candidates found by SplitMesher are
recorded in a list, and after SplitMesher returns candidate
pairs are meshed together en masse. 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0
Meshing spans together is a two step process. First, Mesh
consolidates objects onto a single physical span. This con- Figure 5. An example meshing graph. Nodes correspond
solidation is straightforward: Mesh copies objects from one to the spans represented by the strings 01101000, 01010000,
span into the free space of the other span, and updates Mini- 00100110, and 00010000. Edges connect meshable strings
Heap metadata (like the allocation bitmap). Importantly, as (corresponding to non-overlapping spans).
Mesh copies data at the physical span layer, even though
objects are moving in memory, no pointers or data internal the handler checks if the address that triggered the segfault
to moved objects or external references need to be updated. was involved in a meshing operation; if so, the handler exits
Finally, Mesh updates the process’s virtual-to-physical map- and the instruction causing the write is re-executed by the
pings to point all meshed virtual spans at the consolidated CPU as normal against the fully relocated object.
physical span.

4.5.1 Page Table Updates 4.5.3 Concurrent Allocation

Mesh updates the process’s page tables via calls to mmap. All thread-local allocation (on threads other than the one
We exploit the fact that mmap lets the same offset in a file running SplitMesher) can proceed concurrently and inde-
(corresponding to a physical span) be mapped to multiple pendently with meshing, until and unless a thread needs a
addresses. Mesh’s arena, rather than being an anonymous fresh span to allocate from. Allocation only is performed
mapping, as in traditional malloc implementations, is in- from spans owned by a thread, and only spans owned by the
stead a mapping backed by a temporary file. This temporary global manager are considered for meshing; spans have a
file is obtained via the memfd_create system call and only single owner. The thread running SplitMesher holds the
exists in memory or on swap. global heap’s lock while meshing. This lock also synchro-
nizes transferring ownership of a span from the global heap
4.5.2 Concurrent Meshing to a thread-local heap (or vice-versa). If another thread re-
Meshing takes place concurrently with the normal execu- quires a new span to fulfill an allocation request, the thread
tion of other program threads with no stop-the-world phase waits until the global manager finishes meshing and releases
required. This is similar to how concurrent relocation is im- the lock.
plemented in low-latency garbage collector algorithms like
Pauseless and C4 [4, 29], as described below. Mesh main- 5 Analysis
tains two invariants throughout the meshing process: reads
of objects being relocated are always correct and available to This section shows that the SplitMesher procedure de-
concurrently executing threads, and objects are never writ- scribed in §3.3 comes with strong formal guarantees on
ten to while being relocated between physical spans. The the quality of the meshing found along with bounds on
first invariant is maintained through the atomic semantics its runtime. In situations where significant meshing oppor-
of mmap, the second through a write barrier. tunities exist (that is, when compaction is most desirable),
Mesh’s write barrier is implemented with page protections SplitMesher finds with high probability an approximation
and a segfault trap handler. Before relocating objects, Mesh arbitrarily close to 1/2 of the best possible meshing in O (n/q)
calls mprotect to mark the virtual page where objects are time, where n is the number of spans and q is the global prob-
being copied from as read-only. Concurrent reads succeed ability of two spans meshing.
as normal. If a concurrent thread tries to write to an object To formally establish these bounds on quality and runtime,
being relocated, a Mesh-controlled segfault signal handler we show that meshing can be interpreted as a graph problem,
is invoked by a combination of the hardware and operating analyze its complexity (§5.1), show that we can do nearly as
system. This handler waits on a lock for the current meshing well by solving an easier graph problem instead (§5.2), and
operation to complete, the last step of which is remapping prove that SplitMesher approximates this problem with
the source virtual span as read/write. Once meshing is done high probability (§5.3).
 Bobby Powers, David Tench, Emery D. Berger, and Andrew McGregor

5.1 Formal Problem Definitions Rather than reason about MinCliqeCover on a meshing
Since Mesh segregates objects based on size, we can limit our graph G, we consider the equivalent problem of coloring
analysis to compaction within a single size class without loss the complement graph Ḡ in which there is an edge between
of generality. For our analysis, we represent spans as binary every pair of two nodes whose strings do not mesh. The
strings of length b, the maximum number of objects that the nodes of Ḡ can be partitioned into at most 2b − 1 subsets
span can store. Each bit represents the allocation state of a N 1 . . . N 2b −1 such that all nodes in each Ni represent the
single object. We represent each span π with string s such same string si . The induced subgraph of Ni in Ḡ is a clique
that s (i) = 1 if π has an object at offset i, and 0 otherwise. since all its nodes have a 1 in the same position and so cannot
be pairwise meshed. Further, all nodes in Ni have the same
Definition 5.1. We say two strings s 1 , s 2 mesh iff i s 1 (i) ·
Í
set of neighbors.
s 2 (i) = 0. More generally, a set of binary strings are said to Since Ni is a clique, at most one node in Ni may be col-
mesh if every pair of strings in this set mesh. ored with any color. Fix some coloring on Ḡ. Swapping the
When we mesh k spans together, the objects scattered colors of two nodes in Ni does not change the validity of the
across those k spans are moved to a single span while retain- coloring since these nodes have the same neighbor set. We
ing their offset from the start of the span. The remaining can therefore unambiguously represent a valid coloring of Ḡ
k − 1 spans are no longer needed and are released to the merely by indicating in which cliques each color appears.
operating system. We say that we “release” k − 1 strings With 2b cliques and a maximum of n colors, there are at
when we mesh k strings together. Since our goal is to empty most (n + 1)c such colorings on the graph where c = 22 .
b

as many physical spans as possible, we can characterize our This follows because each color used can be associated with
theoretical problem as follows: a subset of {1, . . . , 2b } corresponding to which of the cliques
Problem 1. Given a multi-set of n binary strings of length b, have node with this color; we call this subset a signature
find a meshing that releases the maximum number of strings. and note there are c possible signatures. A coloring can be
therefore be associated with a multi-set of possible signatures
Note that the total number of strings released is equal to where each signature has multiplicity between 0 and n; there
n − ρ − ϕ, where ρ is the number of total meshes performed, are (n + 1)c such multi-sets. This is polynomial in n since b
and ϕ is the number of strings that remain unmeshed. is constant and hence c is also constant. So we can simply
A Formulation via Graphs: We observe that an instance check each coloring for validity (a coloring is valid iff no
of the meshing problem, a string multi-set S, can naturally color appears in two cliques whose string representations
be expressed via a graph G(S) where there is a node for every mesh). The algorithm returns a valid coloring with the lowest
string in S and an edge between two nodes iff the relevant number of colors from all valid colorings discovered. □
strings can be meshed. Figure 5 illustrates this representation
Unfortunately, while technically polynomial, the running
via an example.
time of the above algorithm would obviously be prohibitive
If a set of strings are meshable, then there is an edge be-
in practice. Fortunately, as we show, we can exploit the
tween every pair of the corresponding nodes: the set of
randomness in the strings to design a much faster algorithm.
corresponding nodes is a clique. We can therefore decom-
pose the graph into k disjoint cliques iff we can free n − k 5.2 Simplifying the Problem: From
strings in the meshing problem. Unfortunately, the prob- MinCliqeCover to Matching
lem of decomposing a graph into the minimum number of
disjoint cliques (MinCliqeCover) is in general NP-hard. We leverage Mesh’s random allocation to simplify meshing;
Worse, it cannot even be approximated up to a factor m1−ϵ this random allocation implies a distribution over the graphs
unless P = N P [30]. that exhibits useful structural properties. We first make the
While the meshing problem is reducible to MinCliqe- following important observation:
Cover, we have not shown that the meshing problem is NP- Observation 1. Conditioned on the occupancies of the strings,
Hard. The meshing problem is indeed NP-hard for strings of edges in the meshing graph are not three-wise independent.
arbitrary length, but in practice string length is proportional
to span size, which is constant. To see that edges are not three-wise independent consider
three random strings s 1 , s 2 , s 3 of length 16, each with exactly 6
Theorem 5.2. The meshing problem for S, a multi-set of ones. It is impossible for these strings to all mesh mutually, so
strings of constant length, is in P. their mesh graph cannot be a triangle. Hence, if we know that
Proof. We assume without loss of generality that S does not s 1 and s 2 mesh, and that s 2 and s 3 mesh, we know for certain
contain the all-zero string s 0 ; if it does, since s 0 can be meshed that s 1 and s 3 cannot mesh. More generally, conditioning
with any other string and so can always be released, we can on s 1 and s 2 meshing and s 1 and s 3 meshing decreases the
solve the meshing problem for S \ s 0 and then mesh each probability that s 1 and s 3 mesh. Below, we quantify this effect
instance of s 0 arbitrarily. to argue that we can mesh near-optimally by solving the
Mesh

much easier Matching problem on the meshing graph (i.e., Lemma 5.3. If t = k/q for some user defined parameter k > 1,
restricting our attention to finding cliques of size 2) instead SplitMesher finds a matching of size at least n(1−e −2k )/4 be-
of MinCliqeCover. Another consequence of the above tween the left and right span sets with probability approaching
observation is that we will not be able to appeal to theoretical 1 as n ≥ 2k/q grows.
results on the standard model of random graphs, Erdős-Renyi
graphs, in which each possible edge is present with some Proof. Let Sl = {v 1 , v 2 , . . . vn/2 } and Sr = {u 1 , u 2 , . . . un/2 }.
fixed probability and the edges are fully independent. Instead Let t = k/q where k > 1 is some arbitrary constant. For
we will need new algorithms and proofs that only require ui ∈ Sl and i ≤ j ≤ j + t, we say (ui , v j ) is a good match if all
independence of acyclic collections of edges. the following properties hold: (1) there is an edge between ui
and v j , (2) there are no edges between ui and v j ′ for i ≤ j ′ < j,
Triangles and Larger Cliques are Uncommon. Because and (3) there are no edges between ui ′ and v j for i < i ′ ≤ j.
of the dependencies across the edges present in a meshing We observe that SplitMesher finds any good match, al-
graph, we can argue that triangles (and hence also larger though it may also find additional matches. It therefore
cliques) are relatively infrequent in the graph and certainly suffices to consider only the number of good matches. The
less frequent than one would expect were all edges indepen- probability (ui , v j ) is a good match is q(1 − q)2(j−i) by appeal-
dent. For example, consider three strings s 1 , s 2 , s 3 ∈ {0, 1}b ing to the fact that the collection of edges under consideration
with occupancies r 1 , r 2 , and r 3 , respectively. The probability is acyclic. Hence, Pr(ui has a good match) is
they mesh is kÕ
/q−1
1 − (1 − q)2k /q 1 − e −2k
r := q (1 − q)2i = q > .
1 − (1 − q) 2 2
b − r1  b b − r1 − r2  b i=0
       
× .
r2 r2 r3 r3 To analyze the number of good Í matches, define X i = 1
iff ui has a good match. Then, i X i is the number of good
This value is significantly less than would have been the matches. By linearity of expectation, the expected number
of good matches is rn/2. We decompose i X i into
Í
case if the events corresponding to pairs of strings being
meshable were independent. For instance, if b = 32, r 1 = Õ
r 2 = r 3 = 10, this probability is so low that even if there were Z 0 + Z 1 + . . . + Z t −1 where Z j = Xi .
1000 strings, the expected number of triangles would be less i≡j mod t
than 2. In contrast, had all meshes been independent, with
the same parameters, there would have been 167 triangles. Since each Z j is a sum of n/(2t) independent variables, by the

Chernoff bound, P Z j < (1 − ϵ) E[Z j ] ≤ exp −ϵ 2rn/(4t) .


The above analysis suggests that we can focus on finding
only cliques of size 2, thereby solving Matching instead of By the union bound,
MinCliqeCover. The evaluation in Section 6 vindicates
P (X < (1 − ϵ) rn/2) ≤ t exp −ϵ 2rn/(4t)


this approach, and we show a strong accuracy guarantee for
Matching below. and this becomes arbitrarily small as n grows. □

5.3 Theoretical Guarantees In the worst case, the algorithm checks nk/2q pairs. For
Since we need to perform meshing at runtime, it is essential our implementation of Mesh, we use a static value of t = 64;
that our algorithm for finding strings to mesh be as effi- this value enables the guarantees of Lemma 5.1 in cases
cient as possible. It would be far too costly in both time and where significant meshing is possible. As Section 6 shows,
memory overhead to actually construct the meshing graph this value for t results in effective memory compaction with
and run an existing matching algorithm on it. Instead, the modest performance overhead.
SplitMesher algorithm (shown in Figure 2) performs mesh-
ing without the need for explicitly constructing the meshing 5.4 Summary of Analytical Results
graph. We show the problem of meshing is reducible to a graph
For further efficiency, we need to constrain the value of the problem, MinCliqeCover. While solving this problem is
parameter t, which controls Mesh’s space-time tradeoff. If t infeasible, we show that probabilistically, we can do nearly
were set as large as n, then SplitMesher could, in the worst as well by finding the maximum Matching, a much eas-
case, exhaustively search all pairs of spans between the left ier graph problem. We analyze our meshing algorithm as
and right sets: a total of n 2 /4 probes. In practice, we want to an approximation to the maximum matching on a random
choose a significantly smaller value for t so that Mesh can meshing graph, and argue that it succeeds with high probabil-
always complete the meshing process quickly without the ity. As a corollary of these results, Mesh breaks the Robson
need to search all possible pairs of strings. bounds with high probability.
 Bobby Powers, David Tench, Emery D. Berger, and Andrew McGregor

6 Evaluation 800

RSS (MiB)
600
Our evaluation answers the following questions: Does Mesh
400
reduce overall memory usage with reasonable performance
200
overhead? (§6.2) Does randomization provide empirical ben-
0
efits beyond its analytical guarantees? (§6.3) 0 50 100
Time Since Program Start (seconds)
6.1 Experimental Setup default jemalloc Mesh
We perform all experiments on a MacBook Pro with 16 GiB of Figure 6. Firefox: Mesh decreases mean heap size by 16%
RAM and an Intel i7-5600U, running Linux 4.18 and Ubuntu over the course of the Speedometer 2.0 benchmark compared
Bionic. We use glibc 2.26 and jemalloc 3.6.0 for SPEC2006, with the version of jemalloc bundled with Firefox, with less
Redis 4.0.2, and Ruby 2.5.1. Two builds of Firefox 57.0.4 were than a 1% change in the reported Speedometer score (§6.2.1).
compiled as release builds, one with its internal allocator dis-
abled to allow the use of alternate allocators via LD_PRELOAD.
SPEC was compiled with clang version 4.0 at the -O2 opti- run and calculate average memory usage recorded by mstat.
mization level, and Mesh was compiled with gcc 8 at the -O3 We tested both a standard release build of Firefox, along
optimization level and with link-time optimization (-flto). with a release build that did not bundle Mozilla’s fork of
Measuring memory usage: To accurately measure the jemalloc (hereafter referred to as mozjemalloc) and instead
memory usage of an application over time, we developed directly called malloc-related functions, with Mesh included
a Linux-based utility, mstat, that runs a program in a new via LD_PRELOAD. We report the average resident set size
memory control group [21]. mstat polls the resident-set size over the course of the benchmark and a 15 second cooldown
(RSS) and kernel memory usage statistics for all processes in period afterward, collecting three runs per allocator.
the control group at a constant frequency. This enables us to Mesh reduces the memory consumption of Firefox by 16%
account for the memory required for larger page tables (due compared to Firefox’s bundled jemalloc allocator. Mesh re-
to meshing) in our evaluation. We have verified that mstat quires 530 MB (σ = 22.4 MB) to complete the benchmark,
does not perturb performance results. while the Mozilla allocator needs 632 MB (σ = 25.3 MB).
This result shows that Mesh can effectively reduce mem-
6.2 Memory Savings and Performance Overhead ory overhead even in widely used and heavily optimized
We evaluate Mesh’s impact on memory consumption and applications. Mesh achieves this savings with less than a 1%
runtime across the Firefox web browser, the Redis data struc- reduction in performance (measured as the score reported
ture store, and the SPECint2006 benchmark suite. by Speedometer).
Figure 6 shows memory usage over the course of a
6.2.1 Firefox Speedometer benchmark run under Mesh and the default
Firefox is an especially challenging application for memory jemalloc allocator. While memory usage under both peaks
reduction since it has been the subject of a five year effort to similar levels, Mesh is able to keep heap size consistently
to reduce its memory footprint [28]. To evaluate Mesh’s lower.
impact on Firefox’s memory consumption under realistic
conditions, we measure Firefox’s RSS while running the 6.2.2 Redis
Speedometer 2.0 benchmark. Speedometer was constructed Redis is a widely-used in-memory data structure server.
by engineers working on the Google Chrome and Apple Sa- Redis 4.0 introduced a feature called “active defragmenta-
fari web browsers to simulate the patterns in use on websites tion” [25, 27]. Redis calculates a fragmentation ratio (RSS
today, stressing a number of browser subsystems like DOM over sum of active allocations) once a second. If this ratio
APIs, layout, CSS resolution and the JavaScript engine. In is too high, it triggers a round of active defragmentation.
Firefox, most of these subsystems are multi-threaded, even This involves making a fresh copy of Redis’s internal data
for a single page [10]. The benchmark comprises a number of structures and freeing the old ones. Active defragmentation
small “todo” apps written in a number of different languages relies on allocator-specific APIs in jemalloc both for gather-
and styles, with a final score computed as the geometric ing statistics and for its ability to perform allocations that
mean of the time taken by the executed tests. bypass thread-local caches, increasing the likelihood they
We test Firefox in single-process mode (disabling content will be contiguous in memory.
sandboxing, which spawns multiple processes) under the We adapt a benchmark from the official Redis test suite
mstat tool to record memory usage over time. Our test to measure how Mesh’s automatic compaction compares
opens a tab, loads the Speedometer page from a local server, with Redis’s active defragmentation, as well as against the
waits 2 seconds, and then automatically executes the test. standard glibc allocator. This benchmark runs for a total of
We record the reported score at the end of the benchmark 7.5 seconds, regardless of allocator. It configures Redis to act
Mesh

300 300
RSS (MiB)

RSS (MiB)
200 200

100 100

0 0
0 1 2 3 4 5 6 0 1 2 3
Time Since Program Start (seconds) Time Since Program Start (seconds)

jemalloc + activedefrag Mesh Mesh (no meshing) jemalloc Mesh Mesh (no meshing) Mesh (no rand)

Figure 7. Redis: Mesh automatically achieves significant Figure 8. Ruby benchmark: Mesh is able to decrease mean
memory savings (39%), obviating the need for its custom, heap size by 18% compared to Mesh with randomization
application-specific “defragmentation” routine (§6.2.2). disabled and non-compacting allocators (§6.3).

as an LRU cache with a maximum of 100 MB of objects (keys benchmark is [Link], a Perl benchmark that per-
and values). The test then allocates 700,000 random keys forms a number of e-mail related tasks including spam de-
and values, where the values have a length of 240 bytes. Fi- tection (SpamAssassin). With glibc, its peak RSS is 664MB.
nally, the test inserts 170,000 new keys with values of length Mesh reduces its peak RSS to 564MB (a 15% reduction) while
492. Our only change from the original Redis test is to in- increasing its runtime overhead by only 3.9%.
crease the value sizes in order to place all allocators on a
level playing field with respect to internal fragmentation; 6.3 Empirical Value of Randomization
the chosen values of 240 and 492 bytes ensure that tested Randomization is key to Mesh’s analytic guarantees; we
allocators use similar size classes for their allocations. We evaluate whether it also can have an observable empirical
test Mesh with Redis in two configurations: with meshing al- impact on its ability to reclaim space. To do this, we test three
ways on and with meshing disabled, both without any input configurations of Mesh: (1) meshing disabled, (2) meshing
or coordination from the redis-server application. enabled but randomization disabled, and (3) Mesh with both
Figure 7 shows memory usage over time for Redis under meshing and randomization enabled (the default).
Mesh, as well as under jemalloc with Redis’s “activedefrag” We tested these configurations with Firefox and Redis,
enabled, as measured by mstat (§6.1). The “activedefrag” and found no significant differences when randomization
configuration enables active defragmentation after all objects was disabled; we believe that this is due to the highly ir-
have been added to the cache. regular (effectively random) allocation patterns that these
Using Mesh automatically and portably achieves the same applications exhibit. We hypothesized that a more regu-
heap size reduction (39%) as Redis’s active defragmentation. lar allocation pattern would be more challenging for a non-
During most of the 7.5s of this test Redis is idle; Redis only randomized baseline. To test this hypothesis, we wrote a
triggers active defragmentation during idle periods. With synthetic microbenchmark with a regular allocation pattern
Mesh, insertion takes 1.76s, while with Redis’s default of in Ruby. Ruby is an interpreted programming language popu-
jemalloc, insertion takes 1.72s. Mesh’s compaction is addi- lar for implementing web services, including GitHub, AirBnB,
tionally significantly faster than Redis’s active defragmenta- and the original version of Twitter. Ruby makes heavy use
tion. During execution with Mesh, a total of 0.23s are spent of object-oriented and functional programming paradigms,
meshing (the longest pause is 22 ms), while active defrag- making it allocation-intensive. Ruby is garbage collected,
mentation accounts for 1.49s (5.5× slower). This high latency and while the standard MRI Ruby implementation (written
may explain why Redis disables “activedefrag” by default. in C) has a custom GC arena for small objects, large objects
(like strings) are allocated directly with malloc.
Our Ruby microbenchmark repeatedly performs a se-
6.2.3 SPEC Benchmarks
quence of string allocations and deallocations, simulating
Most of the SPEC benchmarks are not particularly com- the effect of accumulating results from an API and periodi-
pelling targets for Mesh because they have small overall cally filtering some out. It allocates a number of strings of a
footprints and do not exercise the memory allocator. Across fixed size, then retaining references 25% of the strings while
the entire SPECint 2006 benchmark suite, Mesh modestly dropping references to the rest. Each iteration the length of
decreases average memory consumption (geomean: −2.4%) the strings is doubled. The test requires only a fixed 128 MB
vs. glibc, while imposing minimal execution time overhead to hold the string contents.
(geomean: 0.7%). Figure 8 presents the results of running this application
However, for allocation-intensive applications with large with the three variants of Mesh and jemalloc; for this bench-
footprints, Mesh is able to substantially reduce peak memory mark, jemalloc and glibc are essentially indistinguishable.
consumption. In particular, the most allocation-intensive With meshing disabled, Mesh exhibits similar runtime and
 Bobby Powers, David Tench, Emery D. Berger, and Andrew McGregor

heap size to jemalloc. With meshing enabled but random- not require programmer or compiler support; its compaction
ization disabled, Mesh imposes a 4% runtime overhead and approach is orthogonal to GC.
yields only a modest 3% reduction in heap size. CouchDB and Redis implement ad hoc best-effort com-
Enabling randomization in Mesh increases the time over- paction, which they call “defragmentation”. These work by
head to 10.7% compared to jemalloc, but the use of random- iterating through program data structures like hash tables,
ization lets it significantly reduce the mean heap size over copying each object’s contents into freshly-allocated blocks
the execution time of the microbenchmark (a 19% reduction). (in the hope they will be contiguous), updating pointers,
The additional runtime overhead is due to the additional and then freeing the old objects [25, 27]. This application-
system calls and memory copies induced by the meshing specific approach is not only inefficient (because it may copy
process. This result demonstrates that randomization is not objects that are already densely packed) and brittle (because
just useful for providing analytical guarantees but can also it relies on internal allocator behavior that may change in
be essential for meshing to be effective in practice. new releases), but it may also be ineffective, since the alloca-
tor cannot ensure that these objects are actually contiguous
6.4 Summary of Empirical Results in memory. Unlike these approaches, Mesh performs com-
For a number of memory-intensive applications, including paction efficiently and its effectiveness is guaranteed.
aggressively space-optimized applications like Firefox, Mesh
Compacting garbage collection in managed languages:
can substantially reduce memory consumption (by 16% to
Compacting garbage collection has long been a feature of
39%) while imposing a modest impact on runtime perfor-
languages like LISP and Java [12, 14]. Contemporary run-
mance (e.g., around 1% for Firefox and SPECint 2006). We
times like the Hotspot JVM [20], the .NET VM [19], and the
find that Mesh’s randomization can enable substantial space
SpiderMonkey JavaScript VM [7] all implement compaction
reduction in the face of a regular allocation pattern.
as part of their garbage collection algorithms. Mesh brings
the benefits of compaction to C/C++; in principle, it could
7 Related Work
also be used to automatically enable compaction for language
Hound: Hound is a memory leak detector for C/C++ applica- implementations that rely on non-compacting collectors.
tions that introduced meshing (a.k.a. “virtual compaction”),
a mechanism that Mesh leverages [23]. Hound combines an Bounds on Partial Compaction: Cohen and Petrank prove
age-segregated heap with data sampling to precisely iden- upper and lower bounds on defragmentation via partial com-
tify leaks. Because Hound cannot reclaim memory until paction [5, 6]. In their setting, corresponding to managed en-
every object on a page is freed, it relies on a heuristic version vironments, every object may be relocated to any free mem-
of meshing to prevent catastrophic memory consumption. ory location; they ask what space savings can be achieved if
Hound is unsuitable as a replacement general-purpose allo- the memory manager is only allowed to relocate a bounded
cator; it lacks both Mesh’s theoretical guarantees and space number of objects. By contrast, Mesh is designed for unman-
and runtime efficiency (Hound’s repository is missing files aged languages where objects cannot be arbitrarily relocated.
and it does not build, precluding a direct empirical com-
PCM fault mitigation: Ipek et al. use a technique similar
parison here). The Hound paper reports a geometric mean
to meshing to address the degradation of phase-change mem-
slowdown of ≈ 30% for SPECint2006 (compared to Mesh’s
ory (PCM) over the lifetime of a device [16]. The authors
0.7%), slowing one benchmark (xalancbmk) by almost 10×.
introduce dynamically replicated memory (DRM), which
Hound also generally increases memory consumption, while
uses pairs of PCM pages with non-overlapping bit failures
Mesh often substantially decreases it.
to act as a single page of (non-faulty) storage. When the
Compaction for C/C++: Previous work has described a va- memory controller reports a page with new bit failures, the
riety of manual and compiler-based approaches to support OS attempts to pair it with a complementary page. A random
compaction for C++. Detlefs shows that if developers use graph analysis is used to justify this greedy algorithm.
annotations in the form of smart pointers, C++ code can also DRM operates in a qualitatively different domain than
be managed with a relocating garbage collector [8]. Edelson Mesh. In DRM, the OS occasionally attempts to pair newly
introduced GC support through a combination of automati- faulty pages against a list of pages with static bit failures.
cally generated smart pointer classes and compiler transfor- This process is incremental and local. In Mesh, the occu-
mations that support relocating GC [9]. Google’s Chrome pancy of spans in the heap is more dynamic and much less
uses an application-specific compacting GC for C++ objects local. Mesh solves a full, non-incremental version of the
called Oilpan that depends on the presence of a single event meshing problem each cycle. Additionally, in DRM, the ran-
loop [1]. Developers must use a variety of smart pointer dom graph describes an error model rather than a design
classes instead of raw pointers to enable GC and relocation. decision; additionally, the paper’s analysis is flawed. The
This effort took years. Unlike these approaches, Mesh is fully paper erroneously claims that the resulting graph is a sim-
general, works for unmodified C and C++ binaries, and does ple random graph; in fact, its edges are not independent (as
Mesh

we show in §5.2). This invalidates the claimed performance Association, 37–56.

guarantees, which depend on properties of simple random [9] Daniel R. Edelson. 1992. Precompiling C++ for Garbage Collection.
graphs. In contrast, we prove the efficacy of our original In Proceedings of the International Workshop on Memory Management
(IWMM ’92). Springer-Verlag, London, UK, UK, 299–314. [Link]
SplitMesher algorithm for Mesh using a careful random [Link]/[Link]?id=645648.664820
graph analysis. [10] Wikipedia: The Free Encyclopedia. 2018. Quantum (Mozilla). https:
//[Link]/wiki/Quantum_(Mozilla).
8 Conclusion [11] Jason Evans. 2006. A scalable concurrent malloc (3) implementation
for FreeBSD. In Proc. of the bsdcan conference, ottawa, canada.
This paper introduces Mesh, a memory allocator that effi- [12] Robert R. Fenichel and Jerome C. Yochelson. 1969. A LISP Garbage-
ciently performs compaction without relocation to save mem- collector for Virtual-memory Computer Systems. Commun. ACM 12,
ory for unmanaged languages. We show analytically that 11 (Nov. 1969), 611–612. [Link]
Mesh provably avoids catastrophic memory fragmentation [13] Sanjay Ghemawat and Paul Menage. 2007. TCMalloc: Thread-caching
malloc. [Link]
with high probability, and empirically show that Mesh can [14] Wilfred J. Hansen. 1969. Compact List Representation: Definition,
substantially reduce memory fragmentation for memory- Garbage Collection, and System Implementation. Commun. ACM 12,
intensive applications written in C/C++ with low runtime 9 (Sept. 1969), 499–507. [Link]
overhead. We have released Mesh as an open source project; [15] Kentaro Hara. 2017. State of Blink’s
it can be used with arbitrary C and C++ Linux and Mac OS X Speed. [Link]
1Az-F3CamBq6hZ5QqQt-ynQEMWEhHY1VTvlRwL7b_6TU.
binaries [24]. In future work, we plan to explore integrating [16] Engin Ipek, Jeremy Condit, Edmund B. Nightingale, Doug Burger, and
Mesh into language runtimes that do not currently support Thomas Moscibroda. 2010. Dynamically Replicated Memory: Building
compaction, such as Go and Rust. Reliable Systems from Nanoscale Resistive Memories. SIGPLAN Not.
45, 3 (March 2010), 3–14. [Link]
[17] Mark S. Johnstone and Paul R. Wilson. 1998. The Memory Frag-
Acknowledgments mentation Problem: Solved?. In Proceedings of the 1st International
This material is based upon work supported by the National Symposium on Memory Management (ISMM ’98). ACM, New York, NY,
Science Foundation under Grant No. 1637536. Any opinions, USA, 26–36. [Link]
findings, and conclusions or recommendations expressed in [18] Donald E Knuth. 1981. The Art of Programming, vol. 2, Semi-
Numerical Algorithms.
this material are those of the author and do not necessarily [19] Rico Mariani. 2003. Garbage Collector Basics and Performance Hints.
reflect the views of the National Science Foundation. [Link]
[20] Sun Microystems. 2006. Memory Management in the Java HotSpot™
References Virtual Machine.
[21] Milan Navrátil, Marie Doleželová, Peter Ondrejka, Eva Ma-
[1] Mads Adger. 2013. [Blink-dev] Oilpan - experimenting with a garbage
joršinová, Martin Prpič, Rüdiger Landmann, and Douglas Silas.
collected heap for the DOM. [Link]
2017. Introduction To Control Groups, Resource Management
[2] Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R.
Guide. [Link]
Wilson. 2000. Hoard: a scalable memory allocator for multithreaded
enterprise_linux/6/html/resource_management_guide/ch01.
applications. In ASPLOS-IX: Proceedings of the ninth international
[22] Gene Novark and Emery D. Berger. 2010. DieHarder: securing
conference on Architectural support for programming languages and
the heap. In Proceedings of the 17th ACM conference on Computer and
operating systems. ACM Press, New York, NY, USA, 117–128. https:
communications security (CCS ’10). ACM, New York, NY, USA, 573–584.
//[Link]/10.1145/378993.379232
[Link]
[3] Emery D. Berger and Benjamin G. Zorn. 2006. DieHard: Proba-
[23] Gene Novark, Emery D. Berger, and Benjamin G. Zorn. 2009. Effi-
bilistic Memory Safety for Unsafe Languages. In Proceedings of the
ciently and precisely locating memory leaks and bloat. In Proceedings
2006 ACM SIGPLAN Conference on Programming Language Design and
of the 2009 ACM SIGPLAN conference on Programming language design
Implementation (PLDI 2006). ACM Press, New York, NY, USA, 158–168.
and implementation (PLDI 2009). ACM, New York, NY, USA, 397–407.
[Link]
[Link]
[4] Cliff Click, Gil Tene, and Michael Wolf. 2005. The Pauseless GC Algo-
[24] Bobby Powers and Emery D. Berger. 2018. Mesh repository. https:
rithm. In Proceedings of the 1st ACM/USENIX International Conference
//[Link]/plasma-umass/mesh.
on Virtual Execution Environments (VEE ’05). ACM, New York, NY,
[25] Dave Rigby. 2017. [jemalloc] expose hints that will allow applications to
USA, 46–56. [Link]
perform runtime active defragmentation Bug 566. [Link]
[5] Nachshon Cohen and Erez Petrank. 2013. Limitations of Partial
jemalloc/jemalloc/issues/566.
Compaction: Towards Practical Bounds. In Proceedings of the 34th
[26] J. M. Robson. 1977. Worst case fragmentation of first fit and best
ACM SIGPLAN Conference on Programming Language Design and
fit storage allocation strategies. Comput. J. 20, 3 (1977), 242. https:
Implementation (PLDI ’13). ACM, New York, NY, USA, 309–320.
//[Link]/10.1093/comjnl/20.3.242
[Link]
[27] Salvatore Sanfilippo. 2017. Redis 4.0 GA is out! [Link]
[6] Nachshon Cohen and Erez Petrank. 2017. Limitations of Partial
com/forum/#!msg/redis-db/5Kh3viziYGQ/58TKLwX0AAAJ.
Compaction: Towards Practical Bounds. ACM Trans. Program. Lang.
[28] John Schoenick. 2017. ARE WE SLIM YET? [Link]
Syst. 39, 1, Article 2 (March 2017), 44 pages. [Link]
com/[Link].
2994597
[29] Gil Tene, Balaji Iyengar, and Michael Wolf. 2011. C4: The Continuously
[7] Jon Coppeard. 2015. Compacting Garbage Collection in SpiderMonkey.
Concurrent Compacting Collector. In Proceedings of the International
[Link]
Symposium on Memory Management (ISMM ’11). ACM, New York, NY,
[8] David Detlefs. 1992. Garbage Collection and Run-time Typing as a C++
USA, 79–88. [Link]
Library. In Proceedings of the 1992 USENIX C++ Conference. USENIX
 Bobby Powers, David Tench, Emery D. Berger, and Andrew McGregor

[30] David Zuckerman. 2007. Linear Degree Extractors and the Inapprox-
imability of Max Clique and Chromatic Number. Theory of Computing
3, 6 (2007), 103–128.