Home | History | Annotate | Download | only in platform
      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