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.

[jar (doing other things), 2013/01/30 02:29:13]

Why are we using this, rather than more standard crypto functions??  What is
this adding to the mix?

We already called with a result from devrand.  IF that fails, this just produces
a predictable constant, based on the &c (I think).  If devrand works, this
mixing doesn't appear to add much IMO.

What am I missing?

[jln (very slow on Chromium), 2013/01/30 02:52:13]

What would be a more standard crypto function ? We could add a better crypto
PRNG here, but we don't need it, this is good enough.

/dev/urandom is only used once, to feed the seed of the PRNG. When it's not
available (for instance PPAPI plugins), we use &c. &C has some randomness due to
STACK ASLR and a few other factors.

+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))))
+
+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;
+}
+
+void raninit(ranctx* x, u4 seed) {
+  u4 i;
+  x->a = 0xf1ea5eed, x->b = x->c = x->d = seed;
+  for (i=0; i<20; ++i) {
+    (void)ranval(x);
+  }
+}
+
+// End PRNG code.
+
+#define ASLR_IS_SUPPORTED \\

[jar (doing other things), 2013/01/30 02:29:13]

I doubt you meant to postpend a double backslash...  Didn't you just want to
continue the #define?  

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Done.

+    (defined(OS_LINUX) || defined(OS_CHROMEOS)) && defined(__x86_64__)

[jar (doing other things), 2013/01/30 02:29:13]

"defined" is only meaningful in the context of a "#if" line.  You can't play
games and #define something to be a conditional, hoping it will be expanded and
evaluated inside a #if.  I'm pretty sure you need to 
#if defined...
#defined ASLR_IS_SUPPORTED
#endif


[I could be mistaken about this... but when I wrote a C preprocessor, back in
the old "ANSI C" days, this form was not supported as I *think* you intended. 
If you can reference newer doc, that is fine.]

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Done.

+
+// 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.

[jar (doing other things), 2013/01/30 02:29:13]

nit: Remove extra space: "fail  , as" ---> "fail, as"

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Done.

+// 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)

[jar (doing other things), 2013/01/30 02:29:13]

I'm pretty sure this will always evaluate to true, since you *did* define this
macro.  Note that whether you had said:
#define foo 1
or
#define foo 0
you would still get a true from:
#if defined(foo)

As a result, it appears that your "conditional code" is really not conditional
at all :-(.

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Done.

+  // 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 char c;

[jar (doing other things), 2013/01/30 02:29:13]

Why did you use the keyword volatile here?  What did you think you were getting
that was different??

[jln (very slow on Chromium), 2013/01/30 02:52:13]

I'm trying to tame a potential processor optimization. As you know, I got burned
recently :)

I really want the address of c, as I expect to get from randomness from it. I
don't want the compiler to think that the C standard allows it to virtually put
it at address 0 or something since I don't use the address for real. Or
something along these lines.

In practice it doesn't matter, given that we call read() with something that
depends on this.. But I thought it would be nicer to assert with volatile.

+    // Pre-initialize our seed with a "random" address in case /dev/urandom is
+    // not available.
+    uint32_t seed = (reinterpret_cast<uint64_t>(&c) >> 32) ^
+                    reinterpret_cast<uint64_t>(&c);
+    int urandom_fd = open("/dev/urandom", O_RDONLY);
+    if (urandom_fd >= 0) {
+      ssize_t len;
+      len = read(urandom_fd, &seed, sizeof(seed));
+      ASSERT(len == sizeof(seed));
+      int ret = close(urandom_fd);
+      ASSERT(ret == 0);
+    }
+    raninit(&ctx, seed);
+    initialized = true;

[jar (doing other things), 2013/01/30 02:29:13]

FWIW: the compiler can optimize this line to perform it around line 148. Why not
list it there?  

Your protection via a lock is probably critical to make this code reviewable
(without concerns for the race to init the static), so I'd suggest changing the
comment on line 142 to better appreciate the lock.

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Yes, that comment was for the ranctx, but you're right about initialized.

+  }
+  uint64_t random_address = (static_cast<uint64_t>(ranval(&ctx)) << 32) |
+                            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 use 0x3ffffffff000 as the mask so that we only "pollute" half of the
+  // address space. In the unlikely case where fragmentation would become an
+  // issue, the kernel will still have another half to use.
+  // A a bit-wise "and" won't bias our random distribution.
+  random_address &= 0x3ffffffff000ULL;
+  return reinterpret_cast<void*>(random_address);
+#else
+  return NULL;

[jar (doing other things), 2013/01/30 02:29:13]

nit: With if's (and certainly #if), it is much easier to read if the short
branch (in this case, return NULL) appears first).

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Done.

+#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)

[jar (doing other things), 2013/01/30 02:29:13]

As noted, this is always true here :-(.

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Done.

+                      true),

[jar (doing other things), 2013/01/30 02:29:13]

nit: breaking coded fragments (single short lines) across ifdefs makes things
much less readable.  Please just write teh two lines out separately.

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Done.

+#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);

[jar (doing other things), 2013/01/30 02:29:13]

Instead of moving line at 455 up to line 542 above, why not put this block (with
the ifdef) down in front of line 557?

Merges are always a pain, and the less code motion you create, the easier things
will be.

[jln (very slow on Chromium), 2013/01/30 02:52:13]

Done.

+#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);

[jar (doing other things), 2013/01/30 02:29:13]

Why is this line not included in the new ASLR code?

[jln (very slow on Chromium), 2013/01/30 02:52:13]

At first, I thought we didn't want a fallback to the brk() heap.

But in the x86_64 case (our case), it's really unlikely that an attacker would
be able to put pressure on the address space to get a brk() heap fallback.

There are also more fringe reasons: with a randomized mmap() allocator, in
theory, if we got really unlucky, we could collide with the brk() heap. However,
if we're concerned about that, I could just tune the ASLR zone to make sure it
can never happen.

WDYT ?

   } 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.
 }