| 1 |
// -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- |
| 2 |
/* Copyright (c) 2006, Google Inc. |
| 3 |
* All rights reserved. |
| 4 |
* |
| 5 |
* Redistribution and use in source and binary forms, with or without |
| 6 |
* modification, are permitted provided that the following conditions are |
| 7 |
* met: |
| 8 |
* |
| 9 |
* * Redistributions of source code must retain the above copyright |
| 10 |
* notice, this list of conditions and the following disclaimer. |
| 11 |
* * Redistributions in binary form must reproduce the above |
| 12 |
* copyright notice, this list of conditions and the following disclaimer |
| 13 |
* in the documentation and/or other materials provided with the |
| 14 |
* distribution. |
| 15 |
* * Neither the name of Google Inc. nor the names of its |
| 16 |
* contributors may be used to endorse or promote products derived from |
| 17 |
* this software without specific prior written permission. |
| 18 |
* |
| 19 |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 20 |
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 21 |
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 22 |
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 23 |
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 24 |
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 25 |
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 26 |
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 27 |
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 28 |
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 29 |
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 30 |
*/ |
| 31 |
|
| 32 |
// A low-level allocator that can be used by other low-level |
| 33 |
// modules without introducing dependency cycles. |
| 34 |
// This allocator is slow and wasteful of memory; |
| 35 |
// it should not be used when performance is key. |
| 36 |
|
| 37 |
#include "base/low_level_alloc.h" |
| 38 |
#include "base/dynamic_annotations.h" |
| 39 |
#include "base/spinlock.h" |
| 40 |
#include "base/logging.h" |
| 41 |
|
| 42 |
#include "malloc_hook-inl.h" |
| 43 |
#include <gperftools/malloc_hook.h> |
| 44 |
|
| 45 |
#include "mmap_hook.h" |
| 46 |
|
| 47 |
#ifdef HAVE_UNISTD_H |
| 48 |
#include <unistd.h> |
| 49 |
#endif |
| 50 |
#include <new> // for placement-new |
| 51 |
|
| 52 |
// A first-fit allocator with amortized logarithmic free() time. |
| 53 |
|
| 54 |
LowLevelAlloc::PagesAllocator::~PagesAllocator() { |
| 55 |
} |
| 56 |
|
| 57 |
// --------------------------------------------------------------------------- |
| 58 |
static const int kMaxLevel = 30; |
| 59 |
|
| 60 |
// We put this class-only struct in a namespace to avoid polluting the |
| 61 |
// global namespace with this struct name (thus risking an ODR violation). |
| 62 |
namespace low_level_alloc_internal { |
| 63 |
// This struct describes one allocated block, or one free block. |
| 64 |
struct AllocList { |
| 65 |
struct Header { |
| 66 |
intptr_t size; // size of entire region, including this field. Must be |
| 67 |
// first. Valid in both allocated and unallocated blocks |
| 68 |
intptr_t magic; // kMagicAllocated or kMagicUnallocated xor this |
| 69 |
LowLevelAlloc::Arena *arena; // pointer to parent arena |
| 70 |
void *dummy_for_alignment; // aligns regions to 0 mod 2*sizeof(void*) |
| 71 |
} header; |
| 72 |
|
| 73 |
// Next two fields: in unallocated blocks: freelist skiplist data |
| 74 |
// in allocated blocks: overlaps with client data |
| 75 |
int levels; // levels in skiplist used |
| 76 |
AllocList *next[kMaxLevel]; // actually has levels elements. |
| 77 |
// The AllocList node may not have room for |
| 78 |
// all kMaxLevel entries. See max_fit in |
| 79 |
// LLA_SkiplistLevels() |
| 80 |
}; |
| 81 |
} |
| 82 |
using low_level_alloc_internal::AllocList; |
| 83 |
|
| 84 |
|
| 85 |
// --------------------------------------------------------------------------- |
| 86 |
// A trivial skiplist implementation. This is used to keep the freelist |
| 87 |
// in address order while taking only logarithmic time per insert and delete. |
| 88 |
|
| 89 |
// An integer approximation of log2(size/base) |
| 90 |
// Requires size >= base. |
| 91 |
static int IntLog2(size_t size, size_t base) { |
| 92 |
int result = 0; |
| 93 |
for (size_t i = size; i > base; i >>= 1) { // i == floor(size/2**result) |
| 94 |
result++; |
| 95 |
} |
| 96 |
// floor(size / 2**result) <= base < floor(size / 2**(result-1)) |
| 97 |
// => log2(size/(base+1)) <= result < 1+log2(size/base) |
| 98 |
// => result ~= log2(size/base) |
| 99 |
return result; |
| 100 |
} |
| 101 |
|
| 102 |
// Return a random integer n: p(n)=1/(2**n) if 1 <= n; p(n)=0 if n < 1. |
| 103 |
static int Random() { |
| 104 |
static uint32 r = 1; // no locking---it's not critical |
| 105 |
int result = 1; |
| 106 |
while ((((r = r*1103515245 + 12345) >> 30) & 1) == 0) { |
| 107 |
result++; |
| 108 |
} |
| 109 |
return result; |
| 110 |
} |
| 111 |
|
| 112 |
// Return a number of skiplist levels for a node of size bytes, where |
| 113 |
// base is the minimum node size. Compute level=log2(size / base)+n |
| 114 |
// where n is 1 if random is false and otherwise a random number generated with |
| 115 |
// the standard distribution for a skiplist: See Random() above. |
| 116 |
// Bigger nodes tend to have more skiplist levels due to the log2(size / base) |
| 117 |
// term, so first-fit searches touch fewer nodes. "level" is clipped so |
| 118 |
// level<kMaxLevel and next[level-1] will fit in the node. |
| 119 |
// 0 < LLA_SkiplistLevels(x,y,false) <= LLA_SkiplistLevels(x,y,true) < kMaxLevel |
| 120 |
static int LLA_SkiplistLevels(size_t size, size_t base, bool random) { |
| 121 |
// max_fit is the maximum number of levels that will fit in a node for the |
| 122 |
// given size. We can't return more than max_fit, no matter what the |
| 123 |
// random number generator says. |
| 124 |
int max_fit = (size-OFFSETOF_MEMBER(AllocList, next)) / sizeof (AllocList *); |
| 125 |
int level = IntLog2(size, base) + (random? Random() : 1); |
| 126 |
if (level > max_fit) level = max_fit; |
| 127 |
if (level > kMaxLevel-1) level = kMaxLevel - 1; |
| 128 |
RAW_CHECK(level >= 1, "block not big enough for even one level"); |
| 129 |
return level; |
| 130 |
} |
| 131 |
|
| 132 |
// Return "atleast", the first element of AllocList *head s.t. *atleast >= *e. |
| 133 |
// For 0 <= i < head->levels, set prev[i] to "no_greater", where no_greater |
| 134 |
// points to the last element at level i in the AllocList less than *e, or is |
| 135 |
// head if no such element exists. |
| 136 |
static AllocList *LLA_SkiplistSearch(AllocList *head, |
| 137 |
AllocList *e, AllocList **prev) { |
| 138 |
AllocList *p = head; |
| 139 |
for (int level = head->levels - 1; level >= 0; level--) { |
| 140 |
for (AllocList *n; (n = p->next[level]) != 0 && n < e; p = n) { |
| 141 |
} |
| 142 |
prev[level] = p; |
| 143 |
} |
| 144 |
return (head->levels == 0) ? 0 : prev[0]->next[0]; |
| 145 |
} |
| 146 |
|
| 147 |
// Insert element *e into AllocList *head. Set prev[] as LLA_SkiplistSearch. |
| 148 |
// Requires that e->levels be previously set by the caller (using |
| 149 |
// LLA_SkiplistLevels()) |
| 150 |
static void LLA_SkiplistInsert(AllocList *head, AllocList *e, |
| 151 |
AllocList **prev) { |
| 152 |
LLA_SkiplistSearch(head, e, prev); |
| 153 |
for (; head->levels < e->levels; head->levels++) { // extend prev pointers |
| 154 |
prev[head->levels] = head; // to all *e's levels |
| 155 |
} |
| 156 |
for (int i = 0; i != e->levels; i++) { // add element to list |
| 157 |
e->next[i] = prev[i]->next[i]; |
| 158 |
prev[i]->next[i] = e; |
| 159 |
} |
| 160 |
} |
| 161 |
|
| 162 |
// Remove element *e from AllocList *head. Set prev[] as LLA_SkiplistSearch(). |
| 163 |
// Requires that e->levels be previous set by the caller (using |
| 164 |
// LLA_SkiplistLevels()) |
| 165 |
static void LLA_SkiplistDelete(AllocList *head, AllocList *e, |
| 166 |
AllocList **prev) { |
| 167 |
AllocList *found = LLA_SkiplistSearch(head, e, prev); |
| 168 |
RAW_CHECK(e == found, "element not in freelist"); |
| 169 |
for (int i = 0; i != e->levels && prev[i]->next[i] == e; i++) { |
| 170 |
prev[i]->next[i] = e->next[i]; |
| 171 |
} |
| 172 |
while (head->levels > 0 && head->next[head->levels - 1] == 0) { |
| 173 |
head->levels--; // reduce head->levels if level unused |
| 174 |
} |
| 175 |
} |
| 176 |
|
| 177 |
// --------------------------------------------------------------------------- |
| 178 |
// Arena implementation |
| 179 |
|
| 180 |
struct LowLevelAlloc::Arena { |
| 181 |
Arena() : mu(SpinLock::LINKER_INITIALIZED) {} // does nothing; for static init |
| 182 |
explicit Arena(int) : pagesize(0) {} // set pagesize to zero explicitly |
| 183 |
// for non-static init |
| 184 |
|
| 185 |
SpinLock mu; // protects freelist, allocation_count, |
| 186 |
// pagesize, roundup, min_size |
| 187 |
AllocList freelist; // head of free list; sorted by addr (under mu) |
| 188 |
int32 allocation_count; // count of allocated blocks (under mu) |
| 189 |
int32 flags; // flags passed to NewArena (ro after init) |
| 190 |
size_t pagesize; // ==getpagesize() (init under mu, then ro) |
| 191 |
size_t roundup; // lowest power of 2 >= max(16,sizeof (AllocList)) |
| 192 |
// (init under mu, then ro) |
| 193 |
size_t min_size; // smallest allocation block size |
| 194 |
// (init under mu, then ro) |
| 195 |
PagesAllocator *allocator; |
| 196 |
}; |
| 197 |
|
| 198 |
// The default arena, which is used when 0 is passed instead of an Arena |
| 199 |
// pointer. |
| 200 |
static struct LowLevelAlloc::Arena default_arena; |
| 201 |
|
| 202 |
// Non-malloc-hooked arenas: used only to allocate metadata for arenas that |
| 203 |
// do not want malloc hook reporting, so that for them there's no malloc hook |
| 204 |
// reporting even during arena creation. |
| 205 |
static struct LowLevelAlloc::Arena unhooked_arena; |
| 206 |
static struct LowLevelAlloc::Arena unhooked_async_sig_safe_arena; |
| 207 |
|
| 208 |
namespace { |
| 209 |
|
| 210 |
class DefaultPagesAllocator : public LowLevelAlloc::PagesAllocator { |
| 211 |
public: |
| 212 |
virtual ~DefaultPagesAllocator() {}; |
| 213 |
virtual void *MapPages(int32 flags, size_t size); |
| 214 |
virtual void UnMapPages(int32 flags, void *addr, size_t size); |
| 215 |
}; |
| 216 |
|
| 217 |
} |
| 218 |
|
| 219 |
// magic numbers to identify allocated and unallocated blocks |
| 220 |
static const intptr_t kMagicAllocated = 0x4c833e95; |
| 221 |
static const intptr_t kMagicUnallocated = ~kMagicAllocated; |
| 222 |
|
| 223 |
namespace { |
| 224 |
class SCOPED_LOCKABLE ArenaLock { |
| 225 |
public: |
| 226 |
explicit ArenaLock(LowLevelAlloc::Arena *arena) |
| 227 |
EXCLUSIVE_LOCK_FUNCTION(arena->mu) |
| 228 |
: left_(false), mask_valid_(false), arena_(arena) { |
| 229 |
if ((arena->flags & LowLevelAlloc::kAsyncSignalSafe) != 0) { |
| 230 |
// We've decided not to support async-signal-safe arena use until |
| 231 |
// there a demonstrated need. Here's how one could do it though |
| 232 |
// (would need to be made more portable). |
| 233 |
#if 0 |
| 234 |
sigset_t all; |
| 235 |
sigfillset(&all); |
| 236 |
this->mask_valid_ = |
| 237 |
(pthread_sigmask(SIG_BLOCK, &all, &this->mask_) == 0); |
| 238 |
#else |
| 239 |
RAW_CHECK(false, "We do not yet support async-signal-safe arena."); |
| 240 |
#endif |
| 241 |
} |
| 242 |
this->arena_->mu.Lock(); |
| 243 |
} |
| 244 |
~ArenaLock() { RAW_CHECK(this->left_, "haven't left Arena region"); } |
| 245 |
void Leave() UNLOCK_FUNCTION() { |
| 246 |
this->arena_->mu.Unlock(); |
| 247 |
#if 0 |
| 248 |
if (this->mask_valid_) { |
| 249 |
pthread_sigmask(SIG_SETMASK, &this->mask_, 0); |
| 250 |
} |
| 251 |
#endif |
| 252 |
this->left_ = true; |
| 253 |
} |
| 254 |
private: |
| 255 |
bool left_; // whether left region |
| 256 |
bool mask_valid_; |
| 257 |
#if 0 |
| 258 |
sigset_t mask_; // old mask of blocked signals |
| 259 |
#endif |
| 260 |
LowLevelAlloc::Arena *arena_; |
| 261 |
DISALLOW_COPY_AND_ASSIGN(ArenaLock); |
| 262 |
}; |
| 263 |
} // anonymous namespace |
| 264 |
|
| 265 |
// create an appropriate magic number for an object at "ptr" |
| 266 |
// "magic" should be kMagicAllocated or kMagicUnallocated |
| 267 |
inline static intptr_t Magic(intptr_t magic, AllocList::Header *ptr) { |
| 268 |
return magic ^ reinterpret_cast<intptr_t>(ptr); |
| 269 |
} |
| 270 |
|
| 271 |
// Initialize the fields of an Arena |
| 272 |
static void ArenaInit(LowLevelAlloc::Arena *arena) { |
| 273 |
if (arena->pagesize == 0) { |
| 274 |
arena->pagesize = getpagesize(); |
| 275 |
// Round up block sizes to a power of two close to the header size. |
| 276 |
arena->roundup = 16; |
| 277 |
while (arena->roundup < sizeof (arena->freelist.header)) { |
| 278 |
arena->roundup += arena->roundup; |
| 279 |
} |
| 280 |
// Don't allocate blocks less than twice the roundup size to avoid tiny |
| 281 |
// free blocks. |
| 282 |
arena->min_size = 2 * arena->roundup; |
| 283 |
arena->freelist.header.size = 0; |
| 284 |
arena->freelist.header.magic = |
| 285 |
Magic(kMagicUnallocated, &arena->freelist.header); |
| 286 |
arena->freelist.header.arena = arena; |
| 287 |
arena->freelist.levels = 0; |
| 288 |
memset(arena->freelist.next, 0, sizeof (arena->freelist.next)); |
| 289 |
arena->allocation_count = 0; |
| 290 |
if (arena == &default_arena) { |
| 291 |
// Default arena should be hooked, e.g. for heap-checker to trace |
| 292 |
// pointer chains through objects in the default arena. |
| 293 |
arena->flags = LowLevelAlloc::kCallMallocHook; |
| 294 |
} else if (arena == &unhooked_async_sig_safe_arena) { |
| 295 |
arena->flags = LowLevelAlloc::kAsyncSignalSafe; |
| 296 |
} else { |
| 297 |
arena->flags = 0; // other arenas' flags may be overridden by client, |
| 298 |
// but unhooked_arena will have 0 in 'flags'. |
| 299 |
} |
| 300 |
arena->allocator = LowLevelAlloc::GetDefaultPagesAllocator(); |
| 301 |
} |
| 302 |
} |
| 303 |
|
| 304 |
// L < meta_data_arena->mu |
| 305 |
LowLevelAlloc::Arena *LowLevelAlloc::NewArena(int32 flags, |
| 306 |
Arena *meta_data_arena) { |
| 307 |
return NewArenaWithCustomAlloc(flags, meta_data_arena, NULL); |
| 308 |
} |
| 309 |
|
| 310 |
// L < meta_data_arena->mu |
| 311 |
LowLevelAlloc::Arena *LowLevelAlloc::NewArenaWithCustomAlloc(int32 flags, |
| 312 |
Arena *meta_data_arena, |
| 313 |
PagesAllocator *allocator) { |
| 314 |
RAW_CHECK(meta_data_arena != 0, "must pass a valid arena"); |
| 315 |
if (meta_data_arena == &default_arena) { |
| 316 |
if ((flags & LowLevelAlloc::kAsyncSignalSafe) != 0) { |
| 317 |
meta_data_arena = &unhooked_async_sig_safe_arena; |
| 318 |
} else if ((flags & LowLevelAlloc::kCallMallocHook) == 0) { |
| 319 |
meta_data_arena = &unhooked_arena; |
| 320 |
} |
| 321 |
} |
| 322 |
// Arena(0) uses the constructor for non-static contexts |
| 323 |
Arena *result = |
| 324 |
new (AllocWithArena(sizeof (*result), meta_data_arena)) Arena(0); |
| 325 |
ArenaInit(result); |
| 326 |
result->flags = flags; |
| 327 |
if (allocator) { |
| 328 |
result->allocator = allocator; |
| 329 |
} |
| 330 |
return result; |
| 331 |
} |
| 332 |
|
| 333 |
// L < arena->mu, L < arena->arena->mu |
| 334 |
bool LowLevelAlloc::DeleteArena(Arena *arena) { |
| 335 |
RAW_CHECK(arena != 0 && arena != &default_arena && arena != &unhooked_arena, |
| 336 |
"may not delete default arena"); |
| 337 |
ArenaLock section(arena); |
| 338 |
bool empty = (arena->allocation_count == 0); |
| 339 |
section.Leave(); |
| 340 |
if (empty) { |
| 341 |
while (arena->freelist.next[0] != 0) { |
| 342 |
AllocList *region = arena->freelist.next[0]; |
| 343 |
size_t size = region->header.size; |
| 344 |
arena->freelist.next[0] = region->next[0]; |
| 345 |
RAW_CHECK(region->header.magic == |
| 346 |
Magic(kMagicUnallocated, ®ion->header), |
| 347 |
"bad magic number in DeleteArena()"); |
| 348 |
RAW_CHECK(region->header.arena == arena, |
| 349 |
"bad arena pointer in DeleteArena()"); |
| 350 |
RAW_CHECK(size % arena->pagesize == 0, |
| 351 |
"empty arena has non-page-aligned block size"); |
| 352 |
RAW_CHECK(reinterpret_cast<intptr_t>(region) % arena->pagesize == 0, |
| 353 |
"empty arena has non-page-aligned block"); |
| 354 |
int munmap_result = tcmalloc::DirectMUnMap((arena->flags & LowLevelAlloc::kAsyncSignalSafe) == 0, |
| 355 |
region, size); |
| 356 |
RAW_CHECK(munmap_result == 0, |
| 357 |
"LowLevelAlloc::DeleteArena: munmap failed address"); |
| 358 |
} |
| 359 |
Free(arena); |
| 360 |
} |
| 361 |
return empty; |
| 362 |
} |
| 363 |
|
| 364 |
// --------------------------------------------------------------------------- |
| 365 |
|
| 366 |
// Return value rounded up to next multiple of align. |
| 367 |
// align must be a power of two. |
| 368 |
static intptr_t RoundUp(intptr_t addr, intptr_t align) { |
| 369 |
return (addr + align - 1) & ~(align - 1); |
| 370 |
} |
| 371 |
|
| 372 |
// Equivalent to "return prev->next[i]" but with sanity checking |
| 373 |
// that the freelist is in the correct order, that it |
| 374 |
// consists of regions marked "unallocated", and that no two regions |
| 375 |
// are adjacent in memory (they should have been coalesced). |
| 376 |
// L < arena->mu |
| 377 |
static AllocList *Next(int i, AllocList *prev, LowLevelAlloc::Arena *arena) { |
| 378 |
RAW_CHECK(i < prev->levels, "too few levels in Next()"); |
| 379 |
AllocList *next = prev->next[i]; |
| 380 |
if (next != 0) { |
| 381 |
RAW_CHECK(next->header.magic == Magic(kMagicUnallocated, &next->header), |
| 382 |
"bad magic number in Next()"); |
| 383 |
RAW_CHECK(next->header.arena == arena, |
| 384 |
"bad arena pointer in Next()"); |
| 385 |
if (prev != &arena->freelist) { |
| 386 |
RAW_CHECK(prev < next, "unordered freelist"); |
| 387 |
RAW_CHECK(reinterpret_cast<char *>(prev) + prev->header.size < |
| 388 |
reinterpret_cast<char *>(next), "malformed freelist"); |
| 389 |
} |
| 390 |
} |
| 391 |
return next; |
| 392 |
} |
| 393 |
|
| 394 |
// Coalesce list item "a" with its successor if they are adjacent. |
| 395 |
static void Coalesce(AllocList *a) { |
| 396 |
AllocList *n = a->next[0]; |
| 397 |
if (n != 0 && reinterpret_cast<char *>(a) + a->header.size == |
| 398 |
reinterpret_cast<char *>(n)) { |
| 399 |
LowLevelAlloc::Arena *arena = a->header.arena; |
| 400 |
a->header.size += n->header.size; |
| 401 |
n->header.magic = 0; |
| 402 |
n->header.arena = 0; |
| 403 |
AllocList *prev[kMaxLevel]; |
| 404 |
LLA_SkiplistDelete(&arena->freelist, n, prev); |
| 405 |
LLA_SkiplistDelete(&arena->freelist, a, prev); |
| 406 |
a->levels = LLA_SkiplistLevels(a->header.size, arena->min_size, true); |
| 407 |
LLA_SkiplistInsert(&arena->freelist, a, prev); |
| 408 |
} |
| 409 |
} |
| 410 |
|
| 411 |
// Adds block at location "v" to the free list |
| 412 |
// L >= arena->mu |
| 413 |
static void AddToFreelist(void *v, LowLevelAlloc::Arena *arena) { |
| 414 |
AllocList *f = reinterpret_cast<AllocList *>( |
| 415 |
reinterpret_cast<char *>(v) - sizeof (f->header)); |
| 416 |
RAW_CHECK(f->header.magic == Magic(kMagicAllocated, &f->header), |
| 417 |
"bad magic number in AddToFreelist()"); |
| 418 |
RAW_CHECK(f->header.arena == arena, |
| 419 |
"bad arena pointer in AddToFreelist()"); |
| 420 |
f->levels = LLA_SkiplistLevels(f->header.size, arena->min_size, true); |
| 421 |
AllocList *prev[kMaxLevel]; |
| 422 |
LLA_SkiplistInsert(&arena->freelist, f, prev); |
| 423 |
f->header.magic = Magic(kMagicUnallocated, &f->header); |
| 424 |
Coalesce(f); // maybe coalesce with successor |
| 425 |
Coalesce(prev[0]); // maybe coalesce with predecessor |
| 426 |
} |
| 427 |
|
| 428 |
// Frees storage allocated by LowLevelAlloc::Alloc(). |
| 429 |
// L < arena->mu |
| 430 |
void LowLevelAlloc::Free(void *v) { |
| 431 |
if (v != 0) { |
| 432 |
AllocList *f = reinterpret_cast<AllocList *>( |
| 433 |
reinterpret_cast<char *>(v) - sizeof (f->header)); |
| 434 |
RAW_CHECK(f->header.magic == Magic(kMagicAllocated, &f->header), |
| 435 |
"bad magic number in Free()"); |
| 436 |
LowLevelAlloc::Arena *arena = f->header.arena; |
| 437 |
if ((arena->flags & kCallMallocHook) != 0) { |
| 438 |
MallocHook::InvokeDeleteHook(v); |
| 439 |
} |
| 440 |
ArenaLock section(arena); |
| 441 |
AddToFreelist(v, arena); |
| 442 |
RAW_CHECK(arena->allocation_count > 0, "nothing in arena to free"); |
| 443 |
arena->allocation_count--; |
| 444 |
section.Leave(); |
| 445 |
} |
| 446 |
} |
| 447 |
|
| 448 |
// allocates and returns a block of size bytes, to be freed with Free() |
| 449 |
// L < arena->mu |
| 450 |
static void *DoAllocWithArena(size_t request, LowLevelAlloc::Arena *arena) { |
| 451 |
void *result = 0; |
| 452 |
if (request != 0) { |
| 453 |
AllocList *s; // will point to region that satisfies request |
| 454 |
ArenaLock section(arena); |
| 455 |
ArenaInit(arena); |
| 456 |
// round up with header |
| 457 |
size_t req_rnd = RoundUp(request + sizeof (s->header), arena->roundup); |
| 458 |
for (;;) { // loop until we find a suitable region |
| 459 |
// find the minimum levels that a block of this size must have |
| 460 |
int i = LLA_SkiplistLevels(req_rnd, arena->min_size, false) - 1; |
| 461 |
if (i < arena->freelist.levels) { // potential blocks exist |
| 462 |
AllocList *before = &arena->freelist; // predecessor of s |
| 463 |
while ((s = Next(i, before, arena)) != 0 && s->header.size < req_rnd) { |
| 464 |
before = s; |
| 465 |
} |
| 466 |
if (s != 0) { // we found a region |
| 467 |
break; |
| 468 |
} |
| 469 |
} |
| 470 |
// we unlock before mmap() both because mmap() may call a callback hook, |
| 471 |
// and because it may be slow. |
| 472 |
arena->mu.Unlock(); |
| 473 |
// mmap generous 64K chunks to decrease |
| 474 |
// the chances/impact of fragmentation: |
| 475 |
size_t new_pages_size = RoundUp(req_rnd, arena->pagesize * 16); |
| 476 |
void *new_pages = arena->allocator->MapPages(arena->flags, new_pages_size); |
| 477 |
arena->mu.Lock(); |
| 478 |
s = reinterpret_cast<AllocList *>(new_pages); |
| 479 |
s->header.size = new_pages_size; |
| 480 |
// Pretend the block is allocated; call AddToFreelist() to free it. |
| 481 |
s->header.magic = Magic(kMagicAllocated, &s->header); |
| 482 |
s->header.arena = arena; |
| 483 |
AddToFreelist(&s->levels, arena); // insert new region into free list |
| 484 |
} |
| 485 |
AllocList *prev[kMaxLevel]; |
| 486 |
LLA_SkiplistDelete(&arena->freelist, s, prev); // remove from free list |
| 487 |
// s points to the first free region that's big enough |
| 488 |
if (req_rnd + arena->min_size <= s->header.size) { // big enough to split |
| 489 |
AllocList *n = reinterpret_cast<AllocList *> |
| 490 |
(req_rnd + reinterpret_cast<char *>(s)); |
| 491 |
n->header.size = s->header.size - req_rnd; |
| 492 |
n->header.magic = Magic(kMagicAllocated, &n->header); |
| 493 |
n->header.arena = arena; |
| 494 |
s->header.size = req_rnd; |
| 495 |
AddToFreelist(&n->levels, arena); |
| 496 |
} |
| 497 |
s->header.magic = Magic(kMagicAllocated, &s->header); |
| 498 |
RAW_CHECK(s->header.arena == arena, ""); |
| 499 |
arena->allocation_count++; |
| 500 |
section.Leave(); |
| 501 |
result = &s->levels; |
| 502 |
} |
| 503 |
return result; |
| 504 |
} |
| 505 |
|
| 506 |
void *LowLevelAlloc::Alloc(size_t request) { |
| 507 |
void *result = DoAllocWithArena(request, &default_arena); |
| 508 |
if ((default_arena.flags & kCallMallocHook) != 0) { |
| 509 |
// this call must be directly in the user-called allocator function |
| 510 |
// for MallocHook::GetCallerStackTrace to work properly |
| 511 |
MallocHook::InvokeNewHook(result, request); |
| 512 |
} |
| 513 |
return result; |
| 514 |
} |
| 515 |
|
| 516 |
void *LowLevelAlloc::AllocWithArena(size_t request, Arena *arena) { |
| 517 |
RAW_CHECK(arena != 0, "must pass a valid arena"); |
| 518 |
void *result = DoAllocWithArena(request, arena); |
| 519 |
if ((arena->flags & kCallMallocHook) != 0) { |
| 520 |
// this call must be directly in the user-called allocator function |
| 521 |
// for MallocHook::GetCallerStackTrace to work properly |
| 522 |
MallocHook::InvokeNewHook(result, request); |
| 523 |
} |
| 524 |
return result; |
| 525 |
} |
| 526 |
|
| 527 |
LowLevelAlloc::Arena *LowLevelAlloc::DefaultArena() { |
| 528 |
return &default_arena; |
| 529 |
} |
| 530 |
|
| 531 |
static DefaultPagesAllocator *default_pages_allocator; |
| 532 |
static union { |
| 533 |
char chars[sizeof(DefaultPagesAllocator)]; |
| 534 |
void *ptr; |
| 535 |
} debug_pages_allocator_space; |
| 536 |
|
| 537 |
LowLevelAlloc::PagesAllocator *LowLevelAlloc::GetDefaultPagesAllocator(void) { |
| 538 |
if (default_pages_allocator) { |
| 539 |
return default_pages_allocator; |
| 540 |
} |
| 541 |
default_pages_allocator = new (debug_pages_allocator_space.chars) DefaultPagesAllocator(); |
| 542 |
return default_pages_allocator; |
| 543 |
} |
| 544 |
|
| 545 |
void *DefaultPagesAllocator::MapPages(int32 flags, size_t size) { |
| 546 |
const bool invoke_hooks = ((flags & LowLevelAlloc::kAsyncSignalSafe) == 0); |
| 547 |
|
| 548 |
auto result = tcmalloc::DirectAnonMMap(invoke_hooks, size); |
| 549 |
|
| 550 |
RAW_CHECK(result.success, "mmap error"); |
| 551 |
|
| 552 |
return result.addr; |
| 553 |
} |
| 554 |
|
| 555 |
void DefaultPagesAllocator::UnMapPages(int32 flags, void *region, size_t size) { |
| 556 |
const bool invoke_hooks = ((flags & LowLevelAlloc::kAsyncSignalSafe) == 0); |
| 557 |
|
| 558 |
int munmap_result = tcmalloc::DirectMUnMap(invoke_hooks, region, size); |
| 559 |
RAW_CHECK(munmap_result == 0, |
| 560 |
"LowLevelAlloc::DeleteArena: munmap failed address"); |
| 561 |
} |