Move WebCore into Source
[WebKit-https.git] / 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 }