15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Copyright (c) 2006, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A low-level allocator that can be used by other low-level 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modules without introducing dependency cycles. 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This allocator is slow and wasteful of memory; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// it should not be used when performance is key. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/low_level_alloc.h" 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/dynamic_annotations.h" 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/spinlock.h" 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "malloc_hook-inl.h" 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <gperftools/malloc_hook.h> 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <errno.h> 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_UNISTD_H 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <unistd.h> 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_MMAP 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <sys/mman.h> 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <new> // for placement-new 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// On systems (like freebsd) that don't define MAP_ANONYMOUS, use the old 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// form of the name instead. 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef MAP_ANONYMOUS 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define MAP_ANONYMOUS MAP_ANON 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A first-fit allocator with amortized logarithmic free() time. 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --------------------------------------------------------------------------- 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const int kMaxLevel = 30; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We put this class-only struct in a namespace to avoid polluting the 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// global namespace with this struct name (thus risking an ODR violation). 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace low_level_alloc_internal { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This struct describes one allocated block, or one free block. 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct AllocList { 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Header { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) intptr_t size; // size of entire region, including this field. Must be 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // first. Valid in both allocated and unallocated blocks 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) intptr_t magic; // kMagicAllocated or kMagicUnallocated xor this 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LowLevelAlloc::Arena *arena; // pointer to parent arena 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *dummy_for_alignment; // aligns regions to 0 mod 2*sizeof(void*) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } header; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Next two fields: in unallocated blocks: freelist skiplist data 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // in allocated blocks: overlaps with client data 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int levels; // levels in skiplist used 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *next[kMaxLevel]; // actually has levels elements. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The AllocList node may not have room for 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // all kMaxLevel entries. See max_fit in 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // LLA_SkiplistLevels() 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using low_level_alloc_internal::AllocList; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --------------------------------------------------------------------------- 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A trivial skiplist implementation. This is used to keep the freelist 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in address order while taking only logarithmic time per insert and delete. 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An integer approximation of log2(size/base) 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Requires size >= base. 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int IntLog2(size_t size, size_t base) { 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int result = 0; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = size; i > base; i >>= 1) { // i == floor(size/2**result) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result++; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // floor(size / 2**result) <= base < floor(size / 2**(result-1)) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // => log2(size/(base+1)) <= result < 1+log2(size/base) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // => result ~= log2(size/base) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return a random integer n: p(n)=1/(2**n) if 1 <= n; p(n)=0 if n < 1. 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int Random() { 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int32 r = 1; // no locking---it's not critical 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ANNOTATE_BENIGN_RACE(&r, "benign race, not critical."); 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int result = 1; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while ((((r = r*1103515245 + 12345) >> 30) & 1) == 0) { 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result++; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return a number of skiplist levels for a node of size bytes, where 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// base is the minimum node size. Compute level=log2(size / base)+n 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// where n is 1 if random is false and otherwise a random number generated with 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the standard distribution for a skiplist: See Random() above. 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Bigger nodes tend to have more skiplist levels due to the log2(size / base) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// term, so first-fit searches touch fewer nodes. "level" is clipped so 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// level<kMaxLevel and next[level-1] will fit in the node. 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 0 < LLA_SkiplistLevels(x,y,false) <= LLA_SkiplistLevels(x,y,true) < kMaxLevel 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int LLA_SkiplistLevels(size_t size, size_t base, bool random) { 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // max_fit is the maximum number of levels that will fit in a node for the 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // given size. We can't return more than max_fit, no matter what the 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // random number generator says. 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int max_fit = (size-OFFSETOF_MEMBER(AllocList, next)) / sizeof (AllocList *); 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int level = IntLog2(size, base) + (random? Random() : 1); 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (level > max_fit) level = max_fit; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (level > kMaxLevel-1) level = kMaxLevel - 1; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(level >= 1, "block not big enough for even one level"); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return level; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return "atleast", the first element of AllocList *head s.t. *atleast >= *e. 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// For 0 <= i < head->levels, set prev[i] to "no_greater", where no_greater 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// points to the last element at level i in the AllocList less than *e, or is 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// head if no such element exists. 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static AllocList *LLA_SkiplistSearch(AllocList *head, 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *e, AllocList **prev) { 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *p = head; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int level = head->levels - 1; level >= 0; level--) { 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (AllocList *n; (n = p->next[level]) != 0 && n < e; p = n) { 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev[level] = p; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (head->levels == 0) ? 0 : prev[0]->next[0]; 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Insert element *e into AllocList *head. Set prev[] as LLA_SkiplistSearch. 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Requires that e->levels be previously set by the caller (using 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LLA_SkiplistLevels()) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void LLA_SkiplistInsert(AllocList *head, AllocList *e, 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList **prev) { 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LLA_SkiplistSearch(head, e, prev); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (; head->levels < e->levels; head->levels++) { // extend prev pointers 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev[head->levels] = head; // to all *e's levels 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i != e->levels; i++) { // add element to list 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) e->next[i] = prev[i]->next[i]; 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev[i]->next[i] = e; 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Remove element *e from AllocList *head. Set prev[] as LLA_SkiplistSearch(). 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Requires that e->levels be previous set by the caller (using 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LLA_SkiplistLevels()) 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void LLA_SkiplistDelete(AllocList *head, AllocList *e, 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList **prev) { 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *found = LLA_SkiplistSearch(head, e, prev); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(e == found, "element not in freelist"); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i != e->levels && prev[i]->next[i] == e; i++) { 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev[i]->next[i] = e->next[i]; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (head->levels > 0 && head->next[head->levels - 1] == 0) { 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) head->levels--; // reduce head->levels if level unused 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --------------------------------------------------------------------------- 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Arena implementation 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct LowLevelAlloc::Arena { 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Arena() : mu(SpinLock::LINKER_INITIALIZED) {} // does nothing; for static init 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit Arena(int) : pagesize(0) {} // set pagesize to zero explicitly 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for non-static init 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLock mu; // protects freelist, allocation_count, 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // pagesize, roundup, min_size 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList freelist; // head of free list; sorted by addr (under mu) 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 allocation_count; // count of allocated blocks (under mu) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 flags; // flags passed to NewArena (ro after init) 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t pagesize; // ==getpagesize() (init under mu, then ro) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t roundup; // lowest power of 2 >= max(16,sizeof (AllocList)) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (init under mu, then ro) 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t min_size; // smallest allocation block size 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (init under mu, then ro) 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The default arena, which is used when 0 is passed instead of an Arena 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// pointer. 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static struct LowLevelAlloc::Arena default_arena; 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Non-malloc-hooked arenas: used only to allocate metadata for arenas that 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// do not want malloc hook reporting, so that for them there's no malloc hook 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// reporting even during arena creation. 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static struct LowLevelAlloc::Arena unhooked_arena; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static struct LowLevelAlloc::Arena unhooked_async_sig_safe_arena; 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// magic numbers to identify allocated and unallocated blocks 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const intptr_t kMagicAllocated = 0x4c833e95; 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const intptr_t kMagicUnallocated = ~kMagicAllocated; 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class SCOPED_LOCKABLE ArenaLock { 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit ArenaLock(LowLevelAlloc::Arena *arena) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXCLUSIVE_LOCK_FUNCTION(arena->mu) 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : left_(false), mask_valid_(false), arena_(arena) { 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((arena->flags & LowLevelAlloc::kAsyncSignalSafe) != 0) { 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We've decided not to support async-signal-safe arena use until 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // there a demonstrated need. Here's how one could do it though 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (would need to be made more portable). 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if 0 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sigset_t all; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sigfillset(&all); 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->mask_valid_ = 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (pthread_sigmask(SIG_BLOCK, &all, &this->mask_) == 0); 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(false, "We do not yet support async-signal-safe arena."); 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->arena_->mu.Lock(); 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~ArenaLock() { RAW_CHECK(this->left_, "haven't left Arena region"); } 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Leave() /*UNLOCK_FUNCTION()*/ { 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->arena_->mu.Unlock(); 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if 0 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (this->mask_valid_) { 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pthread_sigmask(SIG_SETMASK, &this->mask_, 0); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->left_ = true; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool left_; // whether left region 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool mask_valid_; 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if 0 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sigset_t mask_; // old mask of blocked signals 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LowLevelAlloc::Arena *arena_; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_COPY_AND_ASSIGN(ArenaLock); 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // anonymous namespace 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// create an appropriate magic number for an object at "ptr" 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "magic" should be kMagicAllocated or kMagicUnallocated 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline static intptr_t Magic(intptr_t magic, AllocList::Header *ptr) { 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return magic ^ reinterpret_cast<intptr_t>(ptr); 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Initialize the fields of an Arena 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void ArenaInit(LowLevelAlloc::Arena *arena) { 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (arena->pagesize == 0) { 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->pagesize = getpagesize(); 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Round up block sizes to a power of two close to the header size. 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->roundup = 16; 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (arena->roundup < sizeof (arena->freelist.header)) { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->roundup += arena->roundup; 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Don't allocate blocks less than twice the roundup size to avoid tiny 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // free blocks. 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->min_size = 2 * arena->roundup; 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->freelist.header.size = 0; 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->freelist.header.magic = 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Magic(kMagicUnallocated, &arena->freelist.header); 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->freelist.header.arena = arena; 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->freelist.levels = 0; 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(arena->freelist.next, 0, sizeof (arena->freelist.next)); 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->allocation_count = 0; 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (arena == &default_arena) { 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Default arena should be hooked, e.g. for heap-checker to trace 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // pointer chains through objects in the default arena. 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->flags = LowLevelAlloc::kCallMallocHook; 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (arena == &unhooked_async_sig_safe_arena) { 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->flags = LowLevelAlloc::kAsyncSignalSafe; 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->flags = 0; // other arenas' flags may be overridden by client, 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // but unhooked_arena will have 0 in 'flags'. 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// L < meta_data_arena->mu 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)LowLevelAlloc::Arena *LowLevelAlloc::NewArena(int32 flags, 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Arena *meta_data_arena) { 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(meta_data_arena != 0, "must pass a valid arena"); 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (meta_data_arena == &default_arena) { 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((flags & LowLevelAlloc::kAsyncSignalSafe) != 0) { 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) meta_data_arena = &unhooked_async_sig_safe_arena; 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if ((flags & LowLevelAlloc::kCallMallocHook) == 0) { 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) meta_data_arena = &unhooked_arena; 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Arena(0) uses the constructor for non-static contexts 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Arena *result = 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new (AllocWithArena(sizeof (*result), meta_data_arena)) Arena(0); 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ArenaInit(result); 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->flags = flags; 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// L < arena->mu, L < arena->arena->mu 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool LowLevelAlloc::DeleteArena(Arena *arena) { 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(arena != 0 && arena != &default_arena && arena != &unhooked_arena, 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "may not delete default arena"); 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ArenaLock section(arena); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool empty = (arena->allocation_count == 0); 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) section.Leave(); 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (empty) { 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (arena->freelist.next[0] != 0) { 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *region = arena->freelist.next[0]; 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t size = region->header.size; 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->freelist.next[0] = region->next[0]; 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(region->header.magic == 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Magic(kMagicUnallocated, ®ion->header), 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "bad magic number in DeleteArena()"); 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(region->header.arena == arena, 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "bad arena pointer in DeleteArena()"); 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(size % arena->pagesize == 0, 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "empty arena has non-page-aligned block size"); 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(reinterpret_cast<intptr_t>(region) % arena->pagesize == 0, 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "empty arena has non-page-aligned block"); 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int munmap_result; 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((arena->flags & LowLevelAlloc::kAsyncSignalSafe) == 0) { 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) munmap_result = munmap(region, size); 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) munmap_result = MallocHook::UnhookedMUnmap(region, size); 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(munmap_result == 0, 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "LowLevelAlloc::DeleteArena: munmap failed address"); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Free(arena); 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return empty; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --------------------------------------------------------------------------- 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return value rounded up to next multiple of align. 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// align must be a power of two. 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static intptr_t RoundUp(intptr_t addr, intptr_t align) { 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (addr + align - 1) & ~(align - 1); 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Equivalent to "return prev->next[i]" but with sanity checking 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// that the freelist is in the correct order, that it 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// consists of regions marked "unallocated", and that no two regions 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// are adjacent in memory (they should have been coalesced). 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// L < arena->mu 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static AllocList *Next(int i, AllocList *prev, LowLevelAlloc::Arena *arena) { 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(i < prev->levels, "too few levels in Next()"); 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *next = prev->next[i]; 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next != 0) { 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(next->header.magic == Magic(kMagicUnallocated, &next->header), 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "bad magic number in Next()"); 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(next->header.arena == arena, 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "bad arena pointer in Next()"); 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (prev != &arena->freelist) { 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(prev < next, "unordered freelist"); 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(reinterpret_cast<char *>(prev) + prev->header.size < 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reinterpret_cast<char *>(next), "malformed freelist"); 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return next; 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Coalesce list item "a" with its successor if they are adjacent. 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void Coalesce(AllocList *a) { 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *n = a->next[0]; 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n != 0 && reinterpret_cast<char *>(a) + a->header.size == 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reinterpret_cast<char *>(n)) { 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LowLevelAlloc::Arena *arena = a->header.arena; 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) a->header.size += n->header.size; 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n->header.magic = 0; 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n->header.arena = 0; 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *prev[kMaxLevel]; 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LLA_SkiplistDelete(&arena->freelist, n, prev); 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LLA_SkiplistDelete(&arena->freelist, a, prev); 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) a->levels = LLA_SkiplistLevels(a->header.size, arena->min_size, true); 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LLA_SkiplistInsert(&arena->freelist, a, prev); 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Adds block at location "v" to the free list 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// L >= arena->mu 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void AddToFreelist(void *v, LowLevelAlloc::Arena *arena) { 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *f = reinterpret_cast<AllocList *>( 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reinterpret_cast<char *>(v) - sizeof (f->header)); 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(f->header.magic == Magic(kMagicAllocated, &f->header), 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "bad magic number in AddToFreelist()"); 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(f->header.arena == arena, 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "bad arena pointer in AddToFreelist()"); 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) f->levels = LLA_SkiplistLevels(f->header.size, arena->min_size, true); 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *prev[kMaxLevel]; 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LLA_SkiplistInsert(&arena->freelist, f, prev); 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) f->header.magic = Magic(kMagicUnallocated, &f->header); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Coalesce(f); // maybe coalesce with successor 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Coalesce(prev[0]); // maybe coalesce with predecessor 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Frees storage allocated by LowLevelAlloc::Alloc(). 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// L < arena->mu 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void LowLevelAlloc::Free(void *v) { 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (v != 0) { 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *f = reinterpret_cast<AllocList *>( 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reinterpret_cast<char *>(v) - sizeof (f->header)); 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(f->header.magic == Magic(kMagicAllocated, &f->header), 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "bad magic number in Free()"); 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LowLevelAlloc::Arena *arena = f->header.arena; 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((arena->flags & kCallMallocHook) != 0) { 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MallocHook::InvokeDeleteHook(v); 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ArenaLock section(arena); 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AddToFreelist(v, arena); 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(arena->allocation_count > 0, "nothing in arena to free"); 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->allocation_count--; 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) section.Leave(); 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// allocates and returns a block of size bytes, to be freed with Free() 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// L < arena->mu 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void *DoAllocWithArena(size_t request, LowLevelAlloc::Arena *arena) { 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *result = 0; 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (request != 0) { 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *s; // will point to region that satisfies request 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ArenaLock section(arena); 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ArenaInit(arena); 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // round up with header 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t req_rnd = RoundUp(request + sizeof (s->header), arena->roundup); 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (;;) { // loop until we find a suitable region 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // find the minimum levels that a block of this size must have 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i = LLA_SkiplistLevels(req_rnd, arena->min_size, false) - 1; 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i < arena->freelist.levels) { // potential blocks exist 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *before = &arena->freelist; // predecessor of s 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while ((s = Next(i, before, arena)) != 0 && s->header.size < req_rnd) { 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) before = s; 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (s != 0) { // we found a region 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we unlock before mmap() both because mmap() may call a callback hook, 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and because it may be slow. 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->mu.Unlock(); 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // mmap generous 64K chunks to decrease 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the chances/impact of fragmentation: 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t new_pages_size = RoundUp(req_rnd, arena->pagesize * 16); 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *new_pages; 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((arena->flags & LowLevelAlloc::kAsyncSignalSafe) != 0) { 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_pages = MallocHook::UnhookedMMap(0, new_pages_size, 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PROT_WRITE|PROT_READ, MAP_ANONYMOUS|MAP_PRIVATE, -1, 0); 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_pages = mmap(0, new_pages_size, 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PROT_WRITE|PROT_READ, MAP_ANONYMOUS|MAP_PRIVATE, -1, 0); 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(new_pages != MAP_FAILED, "mmap error"); 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->mu.Lock(); 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s = reinterpret_cast<AllocList *>(new_pages); 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->header.size = new_pages_size; 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pretend the block is allocated; call AddToFreelist() to free it. 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->header.magic = Magic(kMagicAllocated, &s->header); 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->header.arena = arena; 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AddToFreelist(&s->levels, arena); // insert new region into free list 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *prev[kMaxLevel]; 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LLA_SkiplistDelete(&arena->freelist, s, prev); // remove from free list 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // s points to the first free region that's big enough 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (req_rnd + arena->min_size <= s->header.size) { // big enough to split 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocList *n = reinterpret_cast<AllocList *> 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (req_rnd + reinterpret_cast<char *>(s)); 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n->header.size = s->header.size - req_rnd; 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n->header.magic = Magic(kMagicAllocated, &n->header); 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n->header.arena = arena; 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->header.size = req_rnd; 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AddToFreelist(&n->levels, arena); 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->header.magic = Magic(kMagicAllocated, &s->header); 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(s->header.arena == arena, ""); 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arena->allocation_count++; 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) section.Leave(); 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result = &s->levels; 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ANNOTATE_NEW_MEMORY(result, request); 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void *LowLevelAlloc::Alloc(size_t request) { 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *result = DoAllocWithArena(request, &default_arena); 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((default_arena.flags & kCallMallocHook) != 0) { 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this call must be directly in the user-called allocator function 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for MallocHook::GetCallerStackTrace to work properly 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MallocHook::InvokeNewHook(result, request); 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void *LowLevelAlloc::AllocWithArena(size_t request, Arena *arena) { 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RAW_CHECK(arena != 0, "must pass a valid arena"); 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *result = DoAllocWithArena(request, arena); 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((arena->flags & kCallMallocHook) != 0) { 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this call must be directly in the user-called allocator function 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for MallocHook::GetCallerStackTrace to work properly 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MallocHook::InvokeNewHook(result, request); 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)LowLevelAlloc::Arena *LowLevelAlloc::DefaultArena() { 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return &default_arena; 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 523