Linux: grow a unique random mapping in ASLR

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 119 matching lines @@
 
 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);
   }
 }
 
+// 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.

[jar (doing other things), 2013/02/04 18:34:08]

Question: In a 64 address space, why do they only use the lower 2^48 bits worth
of virtual space (or at least, why are allocations all below the 2^47 mark per
that constant?)

[jln (very slow on Chromium), 2013/02/04 19:23:04]

It's an architectural limitation. It saves transistors in the processor. 64 bits
addresses on x86_64 have to be "canonical", i.e. roughly a 64 bits sign-extended
version of a 48 bits value.

The high order bit set is reserved for the kernel (that's a Linux decision, but
a very common one on this architecture).

+// 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.
+const uint64_t kRandomAddressMask = 0x3ffffffff000ULL;
+
 #endif  // defined(ASLR_IS_SUPPORTED)
 
 // 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)
   return NULL;
@@ skipping 20 matching lines @@
       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);
   }
   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;
+  random_address &= kRandomAddressMask;
   return reinterpret_cast<void*>(random_address);
 #endif  // ASLR_IS_SUPPORTED
 }
 
+// Allocate |length| bytes of memory using mmap(). The memory will be
+// readable and writeable, but not executable.
+// Like mmap(), we will return MAP_FAILED on failure.
+// |is_aslr_enabled| controls address space layout randomization. When true, we
+// will put the first mapping at a random address and will then try to grow it.
+// If it's not possible to grow an existing mapping, a new one will be created.
+void* AllocWithMmap(size_t length, bool is_aslr_enabled) {
+  // Note: we are protected by the general TCMalloc_SystemAlloc spinlock.
+  static void* address_hint = NULL;
+  if (is_aslr_enabled &&
+      (!address_hint ||
+       reinterpret_cast<uint64_t>(address_hint) & ~kRandomAddressMask)) {

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

Another way to look at this (which may help convince you) is:

"do we already have a good hint ?" yes, do nothing : no, get a new hint.

Should I create an intermediate bool to make that clear?

+    address_hint = GetRandomAddrHint();
+  }
+
+  // address_hint is likely to make us grow an existing mapping.
+  void* result = mmap(address_hint, length, PROT_READ|PROT_WRITE,
+                      MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
+  if (result == address_hint) {
+    // If mmap() succeeded at a address_hint, our next mmap() will try to grow
+    // the current mapping as long as it's compatible with our ASLR mask.
+    // This has been done for performance reasons, see crbug.com/173371.
+    // It should be possible to strike a better balance between performance
+    // and security but will be done at a later date.
+    // If this overflows, it could only set address_hint to NULL, which is
+    // what we want (and can't happen on the currently supported architecture).
+    address_hint = static_cast<char*>(result) + length;
+  } else {
+    // mmap failed or a collision prevented the kernel from honoring the hint,
+    // reset the hint.
+    address_hint = NULL;
+  }
+  return result;
+}
+
 }  // 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 192 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* 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);
+  void* result = AllocWithMmap(size + extra, FLAGS_malloc_random_allocator);
   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;
   if ((ptr & (alignment - 1)) != 0) {
     adjust = alignment - (ptr & (alignment - 1));
   }
@@ skipping 226 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.
 }