1/* 2 * Copyright (C) 1998-2000 Netscape Communications Corporation. 3 * Copyright (C) 2003-6 Apple Computer 4 * 5 * Other contributors: 6 * Nick Blievers <nickb@adacel.com.au> 7 * Jeff Hostetler <jeff@nerdone.com> 8 * Tom Rini <trini@kernel.crashing.org> 9 * Raffaele Sena <raff@netwinder.org> 10 * 11 * This library is free software; you can redistribute it and/or 12 * modify it under the terms of the GNU Lesser General Public 13 * License as published by the Free Software Foundation; either 14 * version 2.1 of the License, or (at your option) any later version. 15 * 16 * This library is distributed in the hope that it will be useful, 17 * but WITHOUT ANY WARRANTY; without even the implied warranty of 18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 19 * Lesser General Public License for more details. 20 * 21 * You should have received a copy of the GNU Lesser General Public 22 * License along with this library; if not, write to the Free Software 23 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 24 * 25 * Alternatively, the contents of this file may be used under the terms 26 * of either the Mozilla Public License Version 1.1, found at 27 * http://www.mozilla.org/MPL/ (the "MPL") or the GNU General Public 28 * License Version 2.0, found at http://www.fsf.org/copyleft/gpl.html 29 * (the "GPL"), in which case the provisions of the MPL or the GPL are 30 * applicable instead of those above. If you wish to allow use of your 31 * version of this file only under the terms of one of those two 32 * licenses (the MPL or the GPL) and not to allow others to use your 33 * version of this file under the LGPL, indicate your decision by 34 * deletingthe provisions above and replace them with the notice and 35 * other provisions required by the MPL or the GPL, as the case may be. 36 * If you do not delete the provisions above, a recipient may use your 37 * version of this file under any of the LGPL, the MPL or the GPL. 38 */ 39 40/* 41 * Lifetime-based fast allocation, inspired by much prior art, including 42 * "Fast Allocation and Deallocation of Memory Based on Object Lifetimes" 43 * David R. Hanson, Software -- Practice and Experience, Vol. 20(1). 44 */ 45 46#include "config.h" 47#include "Arena.h" 48 49#include <algorithm> 50#include <stdlib.h> 51#include <string.h> 52#include <wtf/Assertions.h> 53#include <wtf/FastMalloc.h> 54 55using namespace std; 56 57namespace WebCore { 58 59#ifdef DEBUG_ARENA_MALLOC 60static int i = 0; 61#endif 62 63#define ARENA_DEFAULT_ALIGN sizeof(double) 64#define BIT(n) ((unsigned int)1 << (n)) 65#define BITMASK(n) (BIT(n) - 1) 66#define CEILING_LOG2(_log2, _n) \ 67 unsigned int j_ = (unsigned int)(_n); \ 68 (_log2) = 0; \ 69 if ((j_) & ((j_)-1)) \ 70 (_log2) += 1; \ 71 if ((j_) >> 16) \ 72 (_log2) += 16, (j_) >>= 16; \ 73 if ((j_) >> 8) \ 74 (_log2) += 8, (j_) >>= 8; \ 75 if ((j_) >> 4) \ 76 (_log2) += 4, (j_) >>= 4; \ 77 if ((j_) >> 2) \ 78 (_log2) += 2, (j_) >>= 2; \ 79 if ((j_) >> 1) \ 80 (_log2) += 1; 81#define FREE_PATTERN 0xDA 82 83static int CeilingLog2(unsigned int i) { 84 int log2; 85 CEILING_LOG2(log2, i); 86 return log2; 87} 88 89void InitArenaPool(ArenaPool* pool, const char*, unsigned size, unsigned align) 90{ 91 if (align == 0) 92 align = ARENA_DEFAULT_ALIGN; 93 pool->mask = BITMASK(CeilingLog2(align)); 94 pool->first.next = NULL; 95 pool->first.base = pool->first.avail = pool->first.limit = (uword)ARENA_ALIGN(&pool->first + 1); 96 pool->current = &pool->first; 97 pool->arenasize = size; 98} 99 100void* ArenaAllocate(ArenaPool* pool, unsigned int numBytes, unsigned int& bytesAllocated) 101{ 102 Arena* arena; 103 char* returnPointer; 104 105 ASSERT((numBytes & pool->mask) == 0); 106 107 numBytes = (uword)ARENA_ALIGN(numBytes); 108 109 // attempt to allocate from arenas at pool->current 110 { 111 arena = pool->current; 112 do { 113 if (arena->avail + numBytes <= arena->limit) { 114 pool->current = arena; 115 returnPointer = (char *)arena->avail; 116 arena->avail += numBytes; 117 return returnPointer; 118 } 119 } while (NULL != (arena = arena->next)); 120 } 121 122 // attempt to allocate from the heap 123 { 124 unsigned int size = max(pool->arenasize, numBytes); 125 size += sizeof *arena + pool->mask; /* header and alignment slop */ 126#ifdef DEBUG_ARENA_MALLOC 127 i++; 128 printf("Malloc: %d\n", i); 129#endif 130 bytesAllocated = size; 131 arena = (Arena*)fastMalloc(size); 132 // fastMalloc will abort() if it fails, so we are guaranteed that a is not 0. 133 arena->limit = (uword)arena + size; 134 arena->base = arena->avail = (uword)ARENA_ALIGN(arena + 1); 135 returnPointer = (char *)arena->avail; 136 arena->avail += numBytes; 137 // the newly allocated arena is linked after pool->current and becomes pool->current. 138 arena->next = pool->current->next; 139 pool->current->next = arena; 140 pool->current = arena; 141 if (!pool->first.next) 142 pool->first.next = arena; 143 return(returnPointer); 144 } 145} 146 147// Free tail arenas linked after head, which may not be the true list head. 148// Reset pool->current to point to head in case it pointed at a tail arena. 149static void FreeArenaList(ArenaPool* pool, Arena* head) 150{ 151 Arena** arenaPointer = &head->next; 152 Arena* arena = *arenaPointer; 153 if (!arena) 154 return; 155 156#ifdef DEBUG 157 do { 158 ASSERT(arena->base <= arena->avail && arena->avail <= arena->limit); 159 arena->avail = arena->base; 160 memset((void*)(arena)->avail, FREE_PATTERN, (arena)->limit - (arena)->avail) 161 } while ((arena = arena->next) != 0); 162 arena = *arenaPointer; 163#endif 164 165 do { 166 *arenaPointer = arena->next; 167 168#ifdef DEBUG 169 memset((void*)(arena), FREE_PATTERN, (arena)->limit - (uword)(arena)); 170#endif 171 172#ifdef DEBUG_ARENA_MALLOC 173 i--; 174 printf("Free: %d\n", i); 175#endif 176 177 fastFree(arena); 178 arena = 0; 179 } while ((arena = *arenaPointer) != 0); 180 pool->current = head; 181} 182 183void FinishArenaPool(ArenaPool* pool) 184{ 185 FreeArenaList(pool, &pool->first); 186} 187 188} 189