[tbb-dev] Memory Allocator #10281 write-up

[Tom Ritter]

Firefox has a feature where you can build a memory allocator library
and shim it into Firefox - this is called building a memory
replacement library. It requires an additional build-time
configuration option.

Our first investigation was with PartitionAlloc being built as a
memory replacement library. This mostly worked, except we could not
replicate the implementation of memalign, which required editing the
core internals of PartitionAlloc.  It's also important to note that
our use of PartitionAlloc did not actually partition the allocations
based on any intelligent design. This is an ongoing problem.

Currently, when Firefox performs an allocation, it will snake its way
through the layers of abstraction until it arrives at our replacement
library. The only information that has been passed into our
replacement library is the size of the allocation. We do not have any
context about what the allocation is for, and therefore which
partition we would like to place it in.  (We theorized about walking
the call stack in assembly and binning allocation based on that but
this was an untested idea.)

The work with PartitionAlloc paused.

After some time, Firefox began investigating partitioning allocations
using jemalloc3's partitioning capabilities. jemalloc3 is a new
version of the currently used allocator, jemalloc. Mozilla's migration
process is first to move to jemalloc3, and then to start partitioning
allocations. Currently, their move to jemalloc3 is paused because
<actually I'm not entirely sure why. I think "performance" and
"mobile".>

However the code for jemalloc3 is present, and making use of it is
only a configuration change away. jemalloc3 solves one of the problems
of PartitionAlloc - the allocator actually, completely works. Mostly.
There is at least one issue which I believe is <an outstanding bug in
jemalloc causing mismatched VirtualAlloc/Free calls - but this may be
fixed now>. We did some performance comparisons of jemalloc vs
jemalloc3 and it was reasonable: http://imgur.com/a/A6TV9

To actually partition allocations we can implement a replace library
that makes use of jemalloc3's partitioning capabilities. But we run
into the same problem as before - we don't have any context to know
what partition to put an allocation into.

One thought was that we could use memory tags, but after
investigation, that did not seem feasible.  We _can_ go through the
Firefox codebase and change the allocation call to include an arena
constant, but this patch will be difficult to maintain, we are likely
to miss some allocation situations, and eventually Mozilla will do
this themselves.

References:
https://lists.torproject.org/pipermail/tbb-dev/2015-May/000269.html
was my most-recent message on this topic.
It references a github issue that is now closed.  The patch referenced
below should not be needed if this patch solves Mozilla's issue.  Does
it? Was jemalloc's fix merged? Questions I don't know the answer to.

https://lists.torproject.org/pipermail/tbb-dev/2015-May/000272.html
Was my followup.


Future Directions and Open Questions:
- Do we have a clear picture on why mozilla isn't shipping jemalloc3?
- Is the jemalloc3 code in ESR38 considered bug-free, or did the known
github issue not get patched in it?
- Is there concern over switching TBB's allocator over to jemalloc3?
- Is there concern over enabling the replace-malloc switch in TBB?
- If both of those are done, any TBB distribution can, at start-time,
choose to use a randomizing allocator in the form of a replacement
library. The beginnings of one is attached. The library does not need
to be used by default, but can be included in every install.
-------------- next part --------------
This assumes jemalloc3 is enabled.

================================================
.mozconfig

ac_add_options --enable-replace-malloc

================================================
memory/replace/moz.build

+ DIRS += ['randchunks']

================================================
memory/replace/randchunks/moz.build

SharedLibrary('replace_randchunks')

SOURCES += [
    'malloc.cpp',
    ]

DEFINES['abort'] = 'moz_abort'

DISABLE_STL_WRAPPING = True

================================================
memory/replace/randchunks/malloc.cpp

#include "replace_malloc.h"
#include <unistd.h>
#include <execinfo.h>
#include <stdlib.h>
#include <stdio.h>

//Requires https://bug1052573.bugzilla.mozilla.org/attachment.cgi?id=8573433

#define NUM_RAND_ARENAS 10

static const malloc_table_t *funcs = NULL;
static unsigned int mallocs = 0, frees = 0, reallocs = 0, callocs = 0;
static unsigned int arenas[NUM_RAND_ARENAS];
static const uintptr_t randseed = 5;

extern "C" {

void replace_init(const malloc_table_t *table)
{
  funcs = table;
  for(int i=0; i<NUM_RAND_ARENAS; i++) {
    arenas[i] = funcs->malloc_create_partition();
  }
  printf("In init!\n");
}

void replace_jemalloc_stats(jemalloc_stats_t *stats)
{
  void* fps[4];
  backtrace(fps, 4);
  

  printf("%d mallocs, %d frees, %d reallocs, %d callocs\n4-point stacktrace:\n", mallocs, frees, reallocs, callocs);
  backtrace_symbols_fd(fps, 4, STDERR_FILENO);
}

void* replace_malloc(size_t size)
{
  int arena_indx;
  uintptr_t fps[4];
  //backtrace((void**)fps, 4);
  
  arena_indx = (randseed * fps[1] * fps[2] * fps[3]) % NUM_RAND_ARENAS;

  mallocs++;
  return funcs->malloc_from_partition(arenas[arena_indx], size);
}

void replace_free(void* ptr)
{
  frees++;
  funcs->free(ptr);
}

void* replace_realloc(void* ptr, size_t size)
{
  int arena_indx;
  uintptr_t fps[4];
  //backtrace((void**)fps, 4);
  
  arena_indx = (randseed * fps[1] * fps[2] * fps[3]) % NUM_RAND_ARENAS;

  reallocs++;
  return funcs->realloc_from_partition(arenas[arena_indx], ptr, size);
}

void* replace_calloc(size_t nmemb, size_t size)
{
  int arena_indx;
  uintptr_t fps[4];
  //backtrace((void**)fps, 4);
  
  arena_indx = (randseed * fps[1] * fps[2] * fps[3]) % NUM_RAND_ARENAS;

  callocs++;
  return funcs->calloc_from_partition(arenas[arena_indx], nmemb, size);
}

} //extern C