Fix PartitionAlloc randomization on 32-bit systems

third_party/WebKit/Source/wtf/PageAllocator.cpp

 /*
  * Copyright (C) 2013 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 40 matching lines @@
 #elif OS(WIN)
 
 #include <windows.h>
 
 #else
 #error Unknown OS
 #endif // OS(POSIX)
 
 namespace WTF {
 
-// This simple internal function wraps the OS-specific page allocation call so
-// that it behaves consistently: the address is a hint and if it cannot be used,
+// This internal function wraps the OS-specific page allocation call so that
+// it behaves consistently: the address is a hint and if it cannot be used,
 // the allocation will be placed elsewhere.
-static void* systemAllocPages(void* addr, size_t len, PageAccessibilityConfiguration pageAccessibility)
+static void* systemAllocPages(void* addr, size_t len, bool commit, PageAccessibilityConfiguration pageAccessibility)
 {
     ASSERT(!(len & kPageAllocationGranularityOffsetMask));
     ASSERT(!(reinterpret_cast<uintptr_t>(addr) & kPageAllocationGranularityOffsetMask));
     void* ret;
 #if OS(WIN)
-    int accessFlag = pageAccessibility == PageAccessible ? PAGE_READWRITE : PAGE_NOACCESS;
-    ret = VirtualAlloc(addr, len, MEM_RESERVE | MEM_COMMIT, accessFlag);
-    if (!ret)
-        ret = VirtualAlloc(0, len, MEM_RESERVE | MEM_COMMIT, accessFlag);
+    DWORD allocType = MEM_RESERVE | (commit ? MEM_COMMIT : 0);
+    DWORD accessFlag = pageAccessibility == PageAccessible ? PAGE_READWRITE : PAGE_NOACCESS;
+    ret = VirtualAlloc(addr, len, allocType, accessFlag);
+    if (!ret && addr)
+        ret = VirtualAlloc(0, len, allocType, accessFlag);
 #else
     int accessFlag = pageAccessibility == PageAccessible ? (PROT_READ | PROT_WRITE) : PROT_NONE;
     ret = mmap(addr, len, accessFlag, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
     if (ret == MAP_FAILED)
         ret = 0;
 #endif
     return ret;
 }
 
-static bool trimMapping(void* baseAddr, size_t baseLen, void* trimAddr, size_t trimLen)
-{
-#if OS(WIN)
-    return false;
-#else
-    char* basePtr = static_cast<char*>(baseAddr);
-    char* trimPtr = static_cast<char*>(trimAddr);
-    ASSERT(trimPtr >= basePtr);
-    ASSERT(trimPtr + trimLen <= basePtr + baseLen);
-    size_t preLen = trimPtr - basePtr;
-    if (preLen) {
-        int ret = munmap(basePtr, preLen);
-        RELEASE_ASSERT(!ret);
-    }
-    size_t postLen = (basePtr + baseLen) - (trimPtr + trimLen);
-    if (postLen) {
-        int ret = munmap(trimPtr + trimLen, postLen);
-        RELEASE_ASSERT(!ret);
-    }
-    return true;
-#endif
-}
-
 void* allocPages(void* addr, size_t len, size_t align, PageAccessibilityConfiguration pageAccessibility)
 {
     ASSERT(len >= kPageAllocationGranularity);
     ASSERT(!(len & kPageAllocationGranularityOffsetMask));
     ASSERT(align >= kPageAllocationGranularity);
     ASSERT(!(align & kPageAllocationGranularityOffsetMask));
     ASSERT(!(reinterpret_cast<uintptr_t>(addr) & kPageAllocationGranularityOffsetMask));
     size_t alignOffsetMask = align - 1;
     size_t alignBaseMask = ~alignOffsetMask;
     ASSERT(!(reinterpret_cast<uintptr_t>(addr) & alignOffsetMask));
     // If the client passed null as the address, choose a good one.
     if (!addr) {
         addr = getRandomPageBase();
         addr = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(addr) & alignBaseMask);
     }
 
-    // The common case, which is also the least work we can do, is that the
-    // address and length are suitable. Just try it.
-    void* ret = systemAllocPages(addr, len, pageAccessibility);
-    // If the alignment is to our liking, we're done.
-    if (!ret || !(reinterpret_cast<uintptr_t>(ret) & alignOffsetMask))
-        return ret;
+    // First try to force an exact-size, aligned allocation from our random base.
+    for (int count = 0; count < 3; ++count) {
+        void* ret = systemAllocPages(addr, len, false, pageAccessibility);
+        // If the alignment is to our liking, we're done.
+        if (!(reinterpret_cast<uintptr_t>(ret) & alignOffsetMask)) {

[Tom Sepez, 2015/10/05 19:13:31]

nit: maybe reads cleaner if you test !ret and early return above rather than
testing inside this block.

[jschuh, 2015/10/05 20:02:29]

Removed the nested block entirely.

+            if (ret)
+                recommitSystemPages(ret, len);
+            return ret;
+        }
+        // We failed, so we retry another range depending on the size of our address space.
+        freePages(ret, len);
+#if CPU(X86_64) || CPU(ARM64)
+        // Keep trying random addresses on 64-bit systems, because they have the space.
+        addr = getRandomPageBase();
+        addr = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(addr)& alignBaseMask);
+#else
+        // Use a linear probe on 32-bit systems, where the address space tends to be cramped.

[Tom Sepez, 2015/10/05 19:07:30]

Thought you were going to try 3 random allocations before falling back to
probing.

[jschuh, 2015/10/05 20:02:29]

Explained in previous message.

+        // This may wrap, but we'll just fall back to the guaranteed method in that case.
+        addr = reinterpret_cast<void*>((reinterpret_cast<uintptr_t>(ret) + align) & alignBaseMask);
+#endif
+    }
 
-    // Annoying. Unmap and map a larger range to be sure to succeed on the
-    // second, slower attempt.
-    freePages(ret, len);
+    // Map a larger allocation so we can force alignment, but continuing randomizing only on
+    // 64-bit POSIX.
+    const size_t tryLen = len + (align - kPageAllocationGranularity);

[Tom Sepez, 2015/10/05 19:13:31]

nit: the const doesn't buy you a lot here and isn't really needed.

[jschuh, 2015/10/05 20:02:29]

Done.

+    RELEASE_ASSERT(tryLen > len);
+    while (true) {
+        addr = nullptr;
+#if OS(POSIX) && (CPU(X86_64) && CPU(ARM64))
+        addr = getRandomPageBase();
+#endif
+        void* ret = systemAllocPages(addr, tryLen, false, pageAccessibility);
+        if (!ret)
+            return ret;
+        size_t preSlack = reinterpret_cast<uintptr_t>(ret) & (align - 1);
+        preSlack = preSlack ? align - preSlack : 0;
+        size_t postSlack = tryLen - preSlack - len;
+        ASSERT(preSlack || postSlack);
+        ASSERT(preSlack < tryLen);
+        ASSERT(postSlack < tryLen);
+#if OS(POSIX) // On POSIX we can resize the allocation run.
+        if (preSlack) {
+            int res = munmap(ret, preSlack);
+            RELEASE_ASSERT(!res);
+            ret = addr = reinterpret_cast<char*>(ret) + preSlack;
+        }
+        if (postSlack) {
+            int res = munmap(reinterpret_cast<char*>(ret) + len, postSlack);
+            RELEASE_ASSERT(!res);
+        }
+#else // On Windows we can't resize the allocation run.
+        if (preSlack || postSlack) {
+            addr = reinterpret_cast<char*>(ret) + preSlack;
+            freePages(ret, len);
+            ret = systemAllocPages(addr, len, true, pageAccessibility);
+            if (!ret)
+                return ret;
+        }
+#endif
+        if (ret == addr)
+            return ret;
+        freePages(ret, len);
+    }
 
-    size_t tryLen = len + (align - kPageAllocationGranularity);
-    RELEASE_ASSERT(tryLen > len);
-
-    // We loop to cater for the unlikely case where another thread maps on top
-    // of the aligned location we choose.
-    int count = 0;
-    while (count++ < 100) {
-        ret = systemAllocPages(addr, tryLen, pageAccessibility);
-        if (!ret)
-            return 0;
-        // We can now try and trim out a subset of the mapping.
-        addr = reinterpret_cast<void*>((reinterpret_cast<uintptr_t>(ret) + alignOffsetMask) & alignBaseMask);
-
-        // On POSIX systems, we can trim the oversized mapping to fit exactly.
-        // This will always work on POSIX systems.
-        if (trimMapping(ret, tryLen, addr, len))
-            return addr;
-
-        // On Windows, you can't trim an existing mapping so we unmap and remap
-        // a subset. We used to do for all platforms, but OSX 10.8 has a
-        // broken mmap() that ignores address hints for valid, unused addresses.
-        freePages(ret, tryLen);
-        ret = systemAllocPages(addr, len, pageAccessibility);
-        if (ret == addr || !ret)
-            return ret;
-
-        // Unlikely race / collision. Do the simple thing and just start again.
-        freePages(ret, len);
-        addr = getRandomPageBase();
-        addr = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(addr) & alignBaseMask);
-    }
-    IMMEDIATE_CRASH();
     return 0;
 }
 
 void freePages(void* addr, size_t len)
 {
     ASSERT(!(reinterpret_cast<uintptr_t>(addr) & kPageAllocationGranularityOffsetMask));
     ASSERT(!(len & kPageAllocationGranularityOffsetMask));
 #if OS(POSIX)
     int ret = munmap(addr, len);
     RELEASE_ASSERT(!ret);
@@ skipping 58 matching lines @@
 #else
     (void) addr;
     (void) len;
     // TODO(cevans): implement this using MEM_RESET for Windows, once we've
     // decided that the semantics are a match.
 #endif
 }
 
 } // namespace WTF