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 }