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//#define DEBUG_ARENA_MALLOC
60#ifdef DEBUG_ARENA_MALLOC
61static int i = 0;
62#endif
63
64#define FREELIST_MAX 30
65static Arena *arena_freelist;
66static 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
87static int CeilingLog2(unsigned int i) {
88    int log2;
89    CEILING_LOG2(log2,i);
90    return log2;
91}
92
93void 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 */
125void* 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 */
202static 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
248void FreeArenaPool(ArenaPool *pool)
249{
250    FreeArenaList(pool, &pool->first, false);
251}
252
253void FinishArenaPool(ArenaPool *pool)
254{
255    FreeArenaList(pool, &pool->first, true);
256}
257
258}
259