code.vuplus.com Git - vuplus_webkit/blob - Source/WebCore/platform/Arena.cpp

   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
  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->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(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(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 }