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
60namespace 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.
65static 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    if (ret == MAP_FAILED)
77        ret = 0;
78#endif
79    return ret;
80}
81
82static 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
107struct 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
118uint32_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
130uint32_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
149static 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.
155static 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#elif CPU(ARM64)
174    // ARM64 on Linux has 39-bit user space.
175    random &= 0x3fffffffffUL;
176    random += 0x1000000000UL;
177#else // !CPU(X86_64) && !CPU(ARM64)
178    // This is a good range on Windows, Linux and Mac.
179    // Allocates in the 0.5-1.5GB region.
180    random &= 0x3fffffff;
181    random += 0x20000000;
182#endif // CPU(X86_64)
183    random &= kPageAllocationGranularityBaseMask;
184    return reinterpret_cast<void*>(random);
185}
186
187void* allocPages(void* addr, size_t len, size_t align)
188{
189    ASSERT(len >= kPageAllocationGranularity);
190    ASSERT(!(len & kPageAllocationGranularityOffsetMask));
191    ASSERT(align >= kPageAllocationGranularity);
192    ASSERT(!(align & kPageAllocationGranularityOffsetMask));
193    ASSERT(!(reinterpret_cast<uintptr_t>(addr) & kPageAllocationGranularityOffsetMask));
194    size_t alignOffsetMask = align - 1;
195    size_t alignBaseMask = ~alignOffsetMask;
196    ASSERT(!(reinterpret_cast<uintptr_t>(addr) & alignOffsetMask));
197    // If the client passed null as the address, choose a good one.
198    if (!addr) {
199        addr = getRandomPageBase();
200        addr = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(addr) & alignBaseMask);
201    }
202
203    // The common case, which is also the least work we can do, is that the
204    // address and length are suitable. Just try it.
205    void* ret = systemAllocPages(addr, len);
206    // If the alignment is to our liking, we're done.
207    if (!ret || !(reinterpret_cast<uintptr_t>(ret) & alignOffsetMask))
208        return ret;
209
210    // Annoying. Unmap and map a larger range to be sure to succeed on the
211    // second, slower attempt.
212    freePages(ret, len);
213
214    size_t tryLen = len + (align - kPageAllocationGranularity);
215    RELEASE_ASSERT(tryLen > len);
216
217    // We loop to cater for the unlikely case where another thread maps on top
218    // of the aligned location we choose.
219    int count = 0;
220    while (count++ < 100) {
221        ret = systemAllocPages(addr, tryLen);
222        if (!ret)
223            return 0;
224        // We can now try and trim out a subset of the mapping.
225        addr = reinterpret_cast<void*>((reinterpret_cast<uintptr_t>(ret) + alignOffsetMask) & alignBaseMask);
226
227        // On POSIX systems, we can trim the oversized mapping to fit exactly.
228        // This will always work on POSIX systems.
229        if (trimMapping(ret, tryLen, addr, len))
230            return addr;
231
232        // On Windows, you can't trim an existing mapping so we unmap and remap
233        // a subset. We used to do for all platforms, but OSX 10.8 has a
234        // broken mmap() that ignores address hints for valid, unused addresses.
235        freePages(ret, tryLen);
236        ret = systemAllocPages(addr, len);
237        if (ret == addr || !ret)
238            return ret;
239
240        // Unlikely race / collision. Do the simple thing and just start again.
241        freePages(ret, len);
242        addr = getRandomPageBase();
243        addr = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(addr) & alignBaseMask);
244    }
245    IMMEDIATE_CRASH();
246    return 0;
247}
248
249void freePages(void* addr, size_t len)
250{
251    ASSERT(!(reinterpret_cast<uintptr_t>(addr) & kPageAllocationGranularityOffsetMask));
252    ASSERT(!(len & kPageAllocationGranularityOffsetMask));
253#if OS(POSIX)
254    int ret = munmap(addr, len);
255    RELEASE_ASSERT(!ret);
256#else
257    BOOL ret = VirtualFree(addr, 0, MEM_RELEASE);
258    RELEASE_ASSERT(ret);
259#endif
260}
261
262void setSystemPagesInaccessible(void* addr, size_t len)
263{
264    ASSERT(!(len & kSystemPageOffsetMask));
265#if OS(POSIX)
266    int ret = mprotect(addr, len, PROT_NONE);
267    RELEASE_ASSERT(!ret);
268#else
269    BOOL ret = VirtualFree(addr, len, MEM_DECOMMIT);
270    RELEASE_ASSERT(ret);
271#endif
272}
273
274void setSystemPagesAccessible(void* addr, size_t len)
275{
276    ASSERT(!(len & kSystemPageOffsetMask));
277#if OS(POSIX)
278    int ret = mprotect(addr, len, PROT_READ | PROT_WRITE);
279    RELEASE_ASSERT(!ret);
280#else
281    void* ret = VirtualAlloc(addr, len, MEM_COMMIT, PAGE_READWRITE);
282    RELEASE_ASSERT(ret);
283#endif
284}
285
286void decommitSystemPages(void* addr, size_t len)
287{
288    ASSERT(!(len & kSystemPageOffsetMask));
289#if OS(POSIX)
290    int ret = madvise(addr, len, MADV_FREE);
291    RELEASE_ASSERT(!ret);
292#else
293    setSystemPagesInaccessible(addr, len);
294#endif
295}
296
297void recommitSystemPages(void* addr, size_t len)
298{
299    ASSERT(!(len & kSystemPageOffsetMask));
300#if OS(POSIX)
301    (void) addr;
302#else
303    setSystemPagesAccessible(addr, len);
304#endif
305}
306
307} // namespace WTF
308
309