TCMalloc: support userland ASLR on Linux

third_party/tcmalloc/chromium/src/system-alloc.cc

 // Copyright (c) 2005, Google Inc.
 // All rights reserved.
 // 
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 // 
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
@@ skipping 82 matching lines @@
 // Check that no bit is set at position ADDRESS_BITS or higher.
 template <int ADDRESS_BITS> bool CheckAddressBits(uintptr_t ptr) {
   return (ptr >> ADDRESS_BITS) == 0;
 }
 
 // Specialize for the bit width of a pointer to avoid undefined shift.
 template <> bool CheckAddressBits<8 * sizeof(void*)>(uintptr_t ptr) {
   return true;
 }
 
+// From libdieharder, public domain library by Bob Jenkins (rngav.c).
+// Described at http://burtleburtle.net/bob/rand/smallprng.html.
+// Not cryptographically secure, but good enough for what we need.
+typedef uint32_t u4;
+typedef struct ranctx { u4 a; u4 b; u4 c; u4 d; } ranctx;
+
+#define rot(x,k) ((x<<(k))|(x>>(32-(k))))

[Marius, 2013/01/29 06:45:21]

parens around x?

[jln (very slow on Chromium), 2013/01/29 07:02:16]

Done.

+
+static u4 ranval(ranctx* x) {
+  /* xxx: the generator being tested */
+  u4 e = x->a - rot(x->b, 27);
+  x->a = x->b ^ rot(x->c, 17);
+  x->b = x->c + x->d;
+  x->c = x->d + e;
+  x->d = e + x->a;
+  return x->d;
+}
+
+static u4 raninit(ranctx* x, u4 seed) {

[Marius, 2013/01/29 06:45:21]

static void?

[jln (very slow on Chromium), 2013/01/29 07:02:16]

Done.

+  u4 i, e;
+  x->a = x->b = x->c = 0xf1ea5eed;

[Marius, 2013/01/29 06:45:21]

Where does this sequence come from?
From the reference cited above it should be
a = 0xf1..ed, b = c = d = seed;

[jln (very slow on Chromium), 2013/01/29 07:02:16]

From the code in the repository. I changed it back to the reference.

+  x->d = seed - x->a;
+  for (i=0; i<20; ++i) {
+    e = ranval(x);
+  }
+  return e;
+}
+
+// End PRNG code.
+
+#define ASLR_IS_SUPPORTED \\
+    (defined(OS_LINUX) || defined(OS_CHROMEOS)) && defined(__x86_64__)
+
+// Give a random "hint" that is suitable for use with mmap(). This cannot make
+// mmap fail , as the kernel will simply not follow the hint if it can't.
+// However, this will create address space fragmentation.  Currently, we only
+// implement it on x86_64, where we have a 47 bits userland address space and
+// fragmentation is not an issue.
+void* GetRandomAddrHint() {
+#if defined(ASLR_IS_SUPPORTED)
+  // Note: we are protected by the general TCMalloc_SystemAlloc spinlock. Given
+  // the nature of what we're doing, it wouldn't be critical if we weren't.
+  // It's nice to share the state between threads, because scheduling will add
+  // some randomness to the succession of ranval() calls.
+  static ranctx ctx;
+  static bool initialized = false;
+  if (!initialized) {
+    volatile int c;
+    // Pre-initialize our seed, but /dev/urandom should always be available.
+    uint32_t seed = reinterpret_cast<unsigned long>(&c);
+    int urandom_fd = open("/dev/urandom", O_RDONLY);
+#if !defined(NDEBUG)
+    ASSERT(urandom_fd >= 0);
+#endif
+    if (urandom_fd >= 0) {
+      ssize_t len;
+      len = read(urandom_fd, &seed, sizeof(seed));
+#if !defined(NDEBUG)
+    ASSERT(len == sizeof(seed));
+#endif
+      close(seed);

[Marius, 2013/01/29 06:45:21]

close(urandom_fd) instead

[jln (very slow on Chromium), 2013/01/29 07:02:16]

Yeah, Chris caught it as well. Done.

+    }
+    raninit(&ctx, seed);
+    initialized = true;
+  }
+  uint64_t random_address = static_cast<uint64_t>(ranval(&ctx)) << 32 |

[Marius, 2013/01/29 06:45:21]

parens around << expression?
Is there no suitable macro to combine two u32 into u64 and avoid this verbose
construct?

[jln (very slow on Chromium), 2013/01/29 07:02:16]

Not that I know of. Done.

+                            ranval(&ctx);
+  // If the kernel cannot honor the hint in arch_get_unmapped_area_topdown, it
+  // will simply ignore it. So we give a hint that has a good chance of
+  // working.
+  // The mmap top-down allocator will normally allocate below TASK_SIZE - gap,
+  // with a gap that depends on the max stack size. See x86/mm/mmap.c. We
+  // should make allocations that are below this area, which would be
+  // 0x7ffbf8000000. We do a bit-wise "and" because it's simple and won't bias
+  // our random distribution.
+  random_address &= 0x6ffffffff000;

[Marius, 2013/01/29 06:45:21]

0x6ff..00 so you're sure it's sufficiently less so hint + alloc_size stays below
limit?
Either way, 34 bits of play.

[jln (very slow on Chromium), 2013/01/29 07:02:16]

Significantly reduced to keep half of address space untouched in a later
revision.

+  return reinterpret_cast<void*>(random_address);
+#else
+  return NULL;
+#endif  // ASLR_IS_SUPPORTED
+}
+
 }  // Anonymous namespace to avoid name conflicts on "CheckAddressBits".
 
 COMPILE_ASSERT(kAddressBits <= 8 * sizeof(void*),
                address_bits_larger_than_pointer_size);
 
 // Structure for discovering alignment
 union MemoryAligner {
   void*  p;
   double d;
   size_t s;
@@ skipping 19 matching lines @@
              EnvToInt("TCMALLOC_DEVMEM_LIMIT", 0),
              "Physical memory limit location in MB for /dev/mem allocation."
              "  Setting this to 0 means no limit.");
 DEFINE_bool(malloc_skip_sbrk,
             EnvToBool("TCMALLOC_SKIP_SBRK", false),
             "Whether sbrk can be used to obtain memory.");
 DEFINE_bool(malloc_skip_mmap,
             EnvToBool("TCMALLOC_SKIP_MMAP", false),
             "Whether mmap can be used to obtain memory.");
 
+DEFINE_bool(malloc_random_allocator,
+            EnvToBool("TCMALLOC_ASLR",
+#if defined(ASLR_IS_SUPPORTED)
+                      true),
+#else
+                      false),
+#endif
+            "Whether to randomize the address space via mmap().");
+
 // static allocators
 class SbrkSysAllocator : public SysAllocator {
 public:
   SbrkSysAllocator() : SysAllocator() {
   }
   void* Alloc(size_t size, size_t *actual_size, size_t alignment);
 };
 static char sbrk_space[sizeof(SbrkSysAllocator)];
 
 class MmapSysAllocator : public SysAllocator {
@@ skipping 145 matching lines @@
   // Ask for extra memory if alignment > pagesize
   size_t extra = 0;
   if (alignment > pagesize) {
     extra = alignment - pagesize;
   }
 
   // Note: size + extra does not overflow since:
   //            size + alignment < (1<<NBITS).
   // and        extra <= alignment
   // therefore  size + extra < (1<<NBITS)
-  void* result = mmap(NULL, size + extra,
+  void* address_hint = NULL;
+  if (FLAGS_malloc_random_allocator) {
+    address_hint = GetRandomAddrHint();
+  }
+  void* result = mmap(address_hint, size + extra,
                       PROT_READ|PROT_WRITE,
                       MAP_PRIVATE|MAP_ANONYMOUS,
                       -1, 0);
   if (result == reinterpret_cast<void*>(MAP_FAILED)) {
     return NULL;
   }
 
   // Adjust the return memory so it is aligned
   uintptr_t ptr = reinterpret_cast<uintptr_t>(result);
   size_t adjust = 0;
@@ skipping 120 matching lines @@
     failed_[i] = false;
   }
   return NULL;
 }
 
 static bool system_alloc_inited = false;
 void InitSystemAllocators(void) {
   MmapSysAllocator *mmap = new (mmap_space) MmapSysAllocator();
   SbrkSysAllocator *sbrk = new (sbrk_space) SbrkSysAllocator();
 
+  DefaultSysAllocator *sdef = new (default_space) DefaultSysAllocator();
+
+  // Unfortunately, this code runs before flags are initialized. So
+  // we can't use FLAGS_malloc_random_allocator.
+#if defined(ASLR_IS_SUPPORTED)
+  // Our only random allocator is mmap.
+  sdef->SetChildAllocator(mmap, 0, mmap_name);
+#else
   // In 64-bit debug mode, place the mmap allocator first since it
   // allocates pointers that do not fit in 32 bits and therefore gives
   // us better testing of code's 64-bit correctness.  It also leads to
   // less false negatives in heap-checking code.  (Numbers are less
   // likely to look like pointers and therefore the conservative gc in
   // the heap-checker is less likely to misinterpret a number as a
   // pointer).
-  DefaultSysAllocator *sdef = new (default_space) DefaultSysAllocator();
   if (kDebugMode && sizeof(void*) > 4) {
     sdef->SetChildAllocator(mmap, 0, mmap_name);
     sdef->SetChildAllocator(sbrk, 1, sbrk_name);
   } else {
     sdef->SetChildAllocator(sbrk, 0, sbrk_name);
     sdef->SetChildAllocator(mmap, 1, mmap_name);
   }
+#endif  // ASLR_IS_SUPPORTED
   sys_alloc = sdef;
 }
 
 void* TCMalloc_SystemAlloc(size_t size, size_t *actual_size,
                            size_t alignment) {
   // Discard requests that overflow
   if (size + alignment < size) return NULL;
 
   SpinLockHolder lock_holder(&spinlock);
 
@@ skipping 67 matching lines @@
     }
   }
 #endif
 }
 
 void TCMalloc_SystemCommit(void* start, size_t length) {
   // Nothing to do here.  TCMalloc_SystemRelease does not alter pages
   // such that they need to be re-committed before they can be used by the
   // application.
 }