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#ifdef DEBUG_ARENA_MALLOC
60static int i = 0;
61#endif
62
63#define ARENA_DEFAULT_ALIGN sizeof(double)
64#define BIT(n) ((unsigned int)1 << (n))
65#define BITMASK(n) (BIT(n) - 1)
66#define CEILING_LOG2(_log2, _n)   \
67    unsigned int j_ = (unsigned int)(_n);   \
68    (_log2) = 0;                    \
69    if ((j_) & ((j_)-1))            \
70        (_log2) += 1;               \
71    if ((j_) >> 16)                 \
72        (_log2) += 16, (j_) >>= 16; \
73    if ((j_) >> 8)                  \
74        (_log2) += 8, (j_) >>= 8;   \
75    if ((j_) >> 4)                  \
76        (_log2) += 4, (j_) >>= 4;   \
77    if ((j_) >> 2)                  \
78        (_log2) += 2, (j_) >>= 2;   \
79    if ((j_) >> 1)                  \
80        (_log2) += 1;
81#define FREE_PATTERN 0xDA
82
83static int CeilingLog2(unsigned int i) {
84    int log2;
85    CEILING_LOG2(log2, i);
86    return log2;
87}
88
89void InitArenaPool(ArenaPool* pool, const char*, unsigned size, unsigned align)
90{
91     if (align == 0)
92         align = ARENA_DEFAULT_ALIGN;
93     pool->mask = BITMASK(CeilingLog2(align));
94     pool->first.next = NULL;
95     pool->first.base = pool->first.avail = pool->first.limit = (uword)ARENA_ALIGN(&pool->first + 1);
96     pool->current = &pool->first;
97     pool->arenasize = size;
98}
99
100void* ArenaAllocate(ArenaPool* pool, unsigned int numBytes, unsigned int& bytesAllocated)
101{
102    Arena* arena;
103    char* returnPointer;
104
105    ASSERT((numBytes & pool->mask) == 0);
106
107    numBytes = (uword)ARENA_ALIGN(numBytes);
108
109    // attempt to allocate from arenas at pool->current
110    {
111        arena = pool->current;
112        do {
113            if (arena->avail + numBytes <= arena->limit)  {
114                pool->current = arena;
115                returnPointer = (char *)arena->avail;
116                arena->avail += numBytes;
117                return returnPointer;
118            }
119        } while (NULL != (arena = arena->next));
120    }
121
122    // attempt to allocate from the heap
123    {
124        unsigned int size = max(pool->arenasize, numBytes);
125        size += sizeof *arena + pool->mask;  /* header and alignment slop */
126#ifdef DEBUG_ARENA_MALLOC
127        i++;
128        printf("Malloc: %d\n", i);
129#endif
130        bytesAllocated = size;
131        arena = (Arena*)fastMalloc(size);
132        // fastMalloc will abort() if it fails, so we are guaranteed that a is not 0.
133        arena->limit = (uword)arena + size;
134        arena->base = arena->avail = (uword)ARENA_ALIGN(arena + 1);
135        returnPointer = (char *)arena->avail;
136        arena->avail += numBytes;
137        // the newly allocated arena is linked after pool->current and becomes pool->current.
138        arena->next = pool->current->next;
139        pool->current->next = arena;
140        pool->current = arena;
141        if (!pool->first.next)
142            pool->first.next = arena;
143        return(returnPointer);
144    }
145}
146
147// Free tail arenas linked after head, which may not be the true list head.
148// Reset pool->current to point to head in case it pointed at a tail arena.
149static void FreeArenaList(ArenaPool* pool, Arena* head)
150{
151    Arena** arenaPointer = &head->next;
152    Arena* arena = *arenaPointer;
153    if (!arena)
154        return;
155
156#ifdef DEBUG
157    do {
158        ASSERT(arena->base <= arena->avail && arena->avail <= arena->limit);
159        arena->avail = arena->base;
160        memset((void*)(arena)->avail, FREE_PATTERN, (arena)->limit - (arena)->avail)
161    } while ((arena = arena->next) != 0);
162    arena = *arenaPointer;
163#endif
164
165    do {
166        *arenaPointer = arena->next;
167
168#ifdef DEBUG
169        memset((void*)(arena), FREE_PATTERN, (arena)->limit - (uword)(arena));
170#endif
171
172#ifdef DEBUG_ARENA_MALLOC
173        i--;
174        printf("Free: %d\n", i);
175#endif
176
177        fastFree(arena);
178        arena = 0;
179    } while ((arena = *arenaPointer) != 0);
180    pool->current = head;
181}
182
183void FinishArenaPool(ArenaPool* pool)
184{
185    FreeArenaList(pool, &pool->first);
186}
187
188}
189