1 /* 2 * Copyright (C) 2013 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31 #include "config.h" 32 #include "wtf/PageAllocator.h" 33 34 #include "wtf/Assertions.h" 35 #include "wtf/ProcessID.h" 36 #include "wtf/SpinLock.h" 37 38 #include <limits.h> 39 40 #if OS(POSIX) 41 42 #include <sys/mman.h> 43 44 #ifndef MADV_FREE 45 #define MADV_FREE MADV_DONTNEED 46 #endif 47 48 #ifndef MAP_ANONYMOUS 49 #define MAP_ANONYMOUS MAP_ANON 50 #endif 51 52 #elif OS(WIN) 53 54 #include <windows.h> 55 56 #else 57 #error Unknown OS 58 #endif // OS(POSIX) 59 60 namespace WTF { 61 62 // This simple internal function wraps the OS-specific page allocation call so 63 // that it behaves consistently: the address is a hint and if it cannot be used, 64 // the allocation will be placed elsewhere. 65 static void* systemAllocPages(void* addr, size_t len) 66 { 67 ASSERT(!(len & kPageAllocationGranularityOffsetMask)); 68 ASSERT(!(reinterpret_cast<uintptr_t>(addr) & kPageAllocationGranularityOffsetMask)); 69 void* ret; 70 #if OS(WIN) 71 ret = VirtualAlloc(addr, len, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE); 72 if (!ret) 73 ret = VirtualAlloc(0, len, MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE); 74 #else 75 ret = mmap(addr, len, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); 76 RELEASE_ASSERT(ret != MAP_FAILED); 77 #endif 78 RELEASE_ASSERT(ret); 79 return ret; 80 } 81 82 static bool trimMapping(void* baseAddr, size_t baseLen, void* trimAddr, size_t trimLen) 83 { 84 #if OS(WIN) 85 return false; 86 #else 87 char* basePtr = static_cast<char*>(baseAddr); 88 char* trimPtr = static_cast<char*>(trimAddr); 89 ASSERT(trimPtr >= basePtr); 90 ASSERT(trimPtr + trimLen <= basePtr + baseLen); 91 size_t preLen = trimPtr - basePtr; 92 if (preLen) { 93 int ret = munmap(basePtr, preLen); 94 RELEASE_ASSERT(!ret); 95 } 96 size_t postLen = (basePtr + baseLen) - (trimPtr + trimLen); 97 if (postLen) { 98 int ret = munmap(trimPtr + trimLen, postLen); 99 RELEASE_ASSERT(!ret); 100 } 101 return true; 102 #endif 103 } 104 105 // This is the same PRNG as used by tcmalloc for mapping address randomness; 106 // see http://burtleburtle.net/bob/rand/smallprng.html 107 struct ranctx { 108 int lock; 109 bool initialized; 110 uint32_t a; 111 uint32_t b; 112 uint32_t c; 113 uint32_t d; 114 }; 115 116 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) 117 118 uint32_t ranvalInternal(ranctx* x) 119 { 120 uint32_t e = x->a - rot(x->b, 27); 121 x->a = x->b ^ rot(x->c, 17); 122 x->b = x->c + x->d; 123 x->c = x->d + e; 124 x->d = e + x->a; 125 return x->d; 126 } 127 128 #undef rot 129 130 uint32_t ranval(ranctx* x) 131 { 132 spinLockLock(&x->lock); 133 if (UNLIKELY(!x->initialized)) { 134 x->initialized = true; 135 char c; 136 uint32_t seed = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(&c)); 137 seed ^= static_cast<uint32_t>(getCurrentProcessID()); 138 x->a = 0xf1ea5eed; 139 x->b = x->c = x->d = seed; 140 for (int i = 0; i < 20; ++i) { 141 (void) ranvalInternal(x); 142 } 143 } 144 uint32_t ret = ranvalInternal(x); 145 spinLockUnlock(&x->lock); 146 return ret; 147 } 148 149 static struct ranctx s_ranctx; 150 151 // This internal function calculates a random preferred mapping address. 152 // It is used when the client of allocPages() passes null as the address. 153 // In calculating an address, we balance good ASLR against not fragmenting the 154 // address space too badly. 155 static void* getRandomPageBase() 156 { 157 uintptr_t random; 158 random = static_cast<uintptr_t>(ranval(&s_ranctx)); 159 #if CPU(X86_64) 160 random <<= 32UL; 161 random |= static_cast<uintptr_t>(ranval(&s_ranctx)); 162 // This address mask gives a low liklihood of address space collisions. 163 // We handle the situation gracefully if there is a collision. 164 #if OS(WIN) 165 // 64-bit Windows has a bizarrely small 8TB user address space. 166 // Allocates in the 1-5TB region. 167 random &= 0x3ffffffffffUL; 168 random += 0x10000000000UL; 169 #else 170 // Linux and OS X support the full 47-bit user space of x64 processors. 171 random &= 0x3fffffffffffUL; 172 #endif 173 #else // !CPU(X86_64) 174 // This is a good range on Windows, Linux and Mac. 175 // Allocates in the 0.5-1.5GB region. 176 random &= 0x3fffffff; 177 random += 0x20000000; 178 #endif // CPU(X86_64) 179 random &= kPageAllocationGranularityBaseMask; 180 return reinterpret_cast<void*>(random); 181 } 182 183 void* allocPages(void* addr, size_t len, size_t align) 184 { 185 RELEASE_ASSERT(len < INT_MAX - align); 186 ASSERT(len >= kPageAllocationGranularity); 187 ASSERT(!(len & kPageAllocationGranularityOffsetMask)); 188 ASSERT(align >= kPageAllocationGranularity); 189 ASSERT(!(align & kPageAllocationGranularityOffsetMask)); 190 ASSERT(!(reinterpret_cast<uintptr_t>(addr) & kPageAllocationGranularityOffsetMask)); 191 size_t alignOffsetMask = align - 1; 192 size_t alignBaseMask = ~alignOffsetMask; 193 ASSERT(!(reinterpret_cast<uintptr_t>(addr) & alignOffsetMask)); 194 // If the client passed null as the address, choose a good one. 195 if (!addr) { 196 addr = getRandomPageBase(); 197 addr = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(addr) & alignBaseMask); 198 } 199 200 // The common case, which is also the least work we can do, is that the 201 // address and length are suitable. Just try it. 202 void* ret = systemAllocPages(addr, len); 203 // If the alignment is to our liking, we're done. 204 if (!(reinterpret_cast<uintptr_t>(ret) & alignOffsetMask)) 205 return ret; 206 207 // Annoying. Unmap and map a larger range to be sure to succeed on the 208 // second, slower attempt. 209 freePages(ret, len); 210 211 size_t tryLen = len + (align - kPageAllocationGranularity); 212 213 // We loop to cater for the unlikely case where another thread maps on top 214 // of the aligned location we choose. 215 int count = 0; 216 while (count++ < 100) { 217 ret = systemAllocPages(addr, tryLen); 218 // We can now try and trim out a subset of the mapping. 219 addr = reinterpret_cast<void*>((reinterpret_cast<uintptr_t>(ret) + alignOffsetMask) & alignBaseMask); 220 221 // On POSIX systems, we can trim the oversized mapping to fit exactly. 222 // This will always work on POSIX systems. 223 if (trimMapping(ret, tryLen, addr, len)) 224 return addr; 225 226 // On Windows, you can't trim an existing mapping so we unmap and remap 227 // a subset. We used to do for all platforms, but OSX 10.8 has a 228 // broken mmap() that ignores address hints for valid, unused addresses. 229 freePages(ret, tryLen); 230 ret = systemAllocPages(addr, len); 231 if (ret == addr) 232 return ret; 233 234 // Unlikely race / collision. Do the simple thing and just start again. 235 freePages(ret, len); 236 addr = getRandomPageBase(); 237 addr = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(addr) & alignBaseMask); 238 } 239 IMMEDIATE_CRASH(); 240 return 0; 241 } 242 243 void freePages(void* addr, size_t len) 244 { 245 ASSERT(!(reinterpret_cast<uintptr_t>(addr) & kPageAllocationGranularityOffsetMask)); 246 ASSERT(!(len & kPageAllocationGranularityOffsetMask)); 247 #if OS(POSIX) 248 int ret = munmap(addr, len); 249 RELEASE_ASSERT(!ret); 250 #else 251 BOOL ret = VirtualFree(addr, 0, MEM_RELEASE); 252 RELEASE_ASSERT(ret); 253 #endif 254 } 255 256 void setSystemPagesInaccessible(void* addr, size_t len) 257 { 258 ASSERT(!(len & kSystemPageOffsetMask)); 259 #if OS(POSIX) 260 int ret = mprotect(addr, len, PROT_NONE); 261 RELEASE_ASSERT(!ret); 262 #else 263 BOOL ret = VirtualFree(addr, len, MEM_DECOMMIT); 264 RELEASE_ASSERT(ret); 265 #endif 266 } 267 268 void decommitSystemPages(void* addr, size_t len) 269 { 270 ASSERT(!(len & kSystemPageOffsetMask)); 271 #if OS(POSIX) 272 int ret = madvise(addr, len, MADV_FREE); 273 RELEASE_ASSERT(!ret); 274 #else 275 void* ret = VirtualAlloc(addr, len, MEM_RESET, PAGE_READWRITE); 276 RELEASE_ASSERT(ret); 277 #endif 278 } 279 280 } // namespace WTF 281 282
