1 /* 2 * Copyright (C) 1998-2000 Netscape Communications Corporation. 3 * Copyright (C) 2003-6 Apple Computer 4 * 5 * Other contributors: 6 * Nick Blievers <nickb (at) adacel.com.au> 7 * Jeff Hostetler <jeff (at) nerdone.com> 8 * Tom Rini <trini (at) kernel.crashing.org> 9 * Raffaele Sena <raff (at) 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 55 using namespace std; 56 57 namespace WebCore { 58 59 //#define DEBUG_ARENA_MALLOC 60 #ifdef DEBUG_ARENA_MALLOC 61 static int i = 0; 62 #endif 63 64 #define FREELIST_MAX 30 65 static Arena *arena_freelist; 66 static int freelist_count = 0; 67 68 #define ARENA_DEFAULT_ALIGN sizeof(double) 69 #define BIT(n) ((unsigned int)1 << (n)) 70 #define BITMASK(n) (BIT(n) - 1) 71 #define CEILING_LOG2(_log2,_n) \ 72 unsigned int j_ = (unsigned int)(_n); \ 73 (_log2) = 0; \ 74 if ((j_) & ((j_)-1)) \ 75 (_log2) += 1; \ 76 if ((j_) >> 16) \ 77 (_log2) += 16, (j_) >>= 16; \ 78 if ((j_) >> 8) \ 79 (_log2) += 8, (j_) >>= 8; \ 80 if ((j_) >> 4) \ 81 (_log2) += 4, (j_) >>= 4; \ 82 if ((j_) >> 2) \ 83 (_log2) += 2, (j_) >>= 2; \ 84 if ((j_) >> 1) \ 85 (_log2) += 1; 86 87 static int CeilingLog2(unsigned int i) { 88 int log2; 89 CEILING_LOG2(log2,i); 90 return log2; 91 } 92 93 void InitArenaPool(ArenaPool* pool, const char*, unsigned size, unsigned align) 94 { 95 if (align == 0) 96 align = ARENA_DEFAULT_ALIGN; 97 pool->mask = BITMASK(CeilingLog2(align)); 98 pool->first.next = NULL; 99 pool->first.base = pool->first.avail = pool->first.limit = 100 (uword)ARENA_ALIGN(pool, &pool->first + 1); 101 pool->current = &pool->first; 102 pool->arenasize = size; 103 } 104 105 106 /* 107 ** ArenaAllocate() -- allocate space from an arena pool 108 ** 109 ** Description: ArenaAllocate() allocates space from an arena 110 ** pool. 111 ** 112 ** First try to satisfy the request from arenas starting at 113 ** pool->current. 114 ** 115 ** If there is not enough space in the arena pool->current, try 116 ** to claim an arena, on a first fit basis, from the global 117 ** freelist (arena_freelist). 118 ** 119 ** If no arena in arena_freelist is suitable, then try to 120 ** allocate a new arena from the heap. 121 ** 122 ** Returns: pointer to allocated space or NULL 123 ** 124 */ 125 void* ArenaAllocate(ArenaPool *pool, unsigned int nb) 126 { 127 Arena *a; 128 char *rp; /* returned pointer */ 129 130 ASSERT((nb & pool->mask) == 0); 131 132 nb = (uword)ARENA_ALIGN(pool, nb); /* force alignment */ 133 134 /* attempt to allocate from arenas at pool->current */ 135 { 136 a = pool->current; 137 do { 138 if ( a->avail +nb <= a->limit ) { 139 pool->current = a; 140 rp = (char *)a->avail; 141 a->avail += nb; 142 return rp; 143 } 144 } while( NULL != (a = a->next) ); 145 } 146 147 /* attempt to allocate from arena_freelist */ 148 { 149 Arena *p = NULL; /* previous pointer, for unlinking from freelist */ 150 151 for ( a = arena_freelist; a != NULL ; p = a, a = a->next ) { 152 if ( a->base +nb <= a->limit ) { 153 if ( p == NULL ) 154 arena_freelist = a->next; 155 else 156 p->next = a->next; 157 a->avail = a->base; 158 rp = (char *)a->avail; 159 a->avail += nb; 160 /* the newly allocated arena is linked after pool->current 161 * and becomes pool->current */ 162 a->next = pool->current->next; 163 pool->current->next = a; 164 pool->current = a; 165 if ( 0 == pool->first.next ) 166 pool->first.next = a; 167 freelist_count--; 168 return(rp); 169 } 170 } 171 } 172 173 /* attempt to allocate from the heap */ 174 { 175 unsigned int sz = max(pool->arenasize, nb); 176 sz += sizeof *a + pool->mask; /* header and alignment slop */ 177 #ifdef DEBUG_ARENA_MALLOC 178 i++; 179 printf("Malloc: %d\n", i); 180 #endif 181 a = (Arena*)fastMalloc(sz); 182 // fastMalloc will abort() if it fails, so we are guaranteed that a is not 0. 183 a->limit = (uword)a + sz; 184 a->base = a->avail = (uword)ARENA_ALIGN(pool, a + 1); 185 rp = (char *)a->avail; 186 a->avail += nb; 187 /* the newly allocated arena is linked after pool->current 188 * and becomes pool->current */ 189 a->next = pool->current->next; 190 pool->current->next = a; 191 pool->current = a; 192 if ( !pool->first.next ) 193 pool->first.next = a; 194 return(rp); 195 } 196 } /* --- end ArenaAllocate() --- */ 197 198 /* 199 * Free tail arenas linked after head, which may not be the true list head. 200 * Reset pool->current to point to head in case it pointed at a tail arena. 201 */ 202 static void FreeArenaList(ArenaPool *pool, Arena *head, bool reallyFree) 203 { 204 Arena **ap, *a; 205 206 ap = &head->next; 207 a = *ap; 208 if (!a) 209 return; 210 211 #ifdef DEBUG 212 do { 213 ASSERT(a->base <= a->avail && a->avail <= a->limit); 214 a->avail = a->base; 215 CLEAR_UNUSED(a); 216 } while ((a = a->next) != 0); 217 a = *ap; 218 #endif 219 220 if (freelist_count >= FREELIST_MAX) 221 reallyFree = true; 222 223 if (reallyFree) { 224 do { 225 *ap = a->next; 226 CLEAR_ARENA(a); 227 #ifdef DEBUG_ARENA_MALLOC 228 if (a) { 229 i--; 230 printf("Free: %d\n", i); 231 } 232 #endif 233 fastFree(a); a = 0; 234 } while ((a = *ap) != 0); 235 } else { 236 /* Insert the whole arena chain at the front of the freelist. */ 237 do { 238 ap = &(*ap)->next; 239 freelist_count++; 240 } while (*ap); 241 *ap = arena_freelist; 242 arena_freelist = a; 243 head->next = 0; 244 } 245 pool->current = head; 246 } 247 248 void FreeArenaPool(ArenaPool *pool) 249 { 250 FreeArenaList(pool, &pool->first, false); 251 } 252 253 void FinishArenaPool(ArenaPool *pool) 254 { 255 FreeArenaList(pool, &pool->first, true); 256 } 257 258 #ifdef ANDROID_INSTRUMENT 259 size_t ReportPoolSize(const ArenaPool* pool) 260 { 261 size_t total = 0; 262 for (const Arena *a = &pool->first; a; a = a->next) 263 total += (a->limit - a->base); 264 for (const Arena *fa = arena_freelist; fa; fa = fa->next ) 265 total += (fa->limit - fa->base); 266 return total; 267 } 268 #endif 269 270 } 271
