18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 1998-2000 Netscape Communications Corporation. 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2003-6 Apple Computer 46c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen * Copyright (C) Research In Motion Limited 2010. All rights reserved. 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Other contributors: 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Nick Blievers <nickb@adacel.com.au> 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Jeff Hostetler <jeff@nerdone.com> 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Tom Rini <trini@kernel.crashing.org> 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Raffaele Sena <raff@netwinder.org> 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * This library is free software; you can redistribute it and/or 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modify it under the terms of the GNU Lesser General Public 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * License as published by the Free Software Foundation; either 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * version 2.1 of the License, or (at your option) any later version. 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * This library is distributed in the hope that it will be useful, 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * but WITHOUT ANY WARRANTY; without even the implied warranty of 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Lesser General Public License for more details. 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * You should have received a copy of the GNU Lesser General Public 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * License along with this library; if not, write to the Free Software 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Alternatively, the contents of this file may be used under the terms 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * of either the Mozilla Public License Version 1.1, found at 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * http://www.mozilla.org/MPL/ (the "MPL") or the GNU General Public 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * License Version 2.0, found at http://www.fsf.org/copyleft/gpl.html 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (the "GPL"), in which case the provisions of the MPL or the GPL are 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * applicable instead of those above. If you wish to allow use of your 328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * version of this file only under the terms of one of those two 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * licenses (the MPL or the GPL) and not to allow others to use your 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * version of this file under the LGPL, indicate your decision by 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * deletingthe provisions above and replace them with the notice and 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * other provisions required by the MPL or the GPL, as the case may be. 378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * If you do not delete the provisions above, a recipient may use your 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * version of this file under any of the LGPL, the MPL or the GPL. 398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef Arena_h 428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define Arena_h 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 446c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen#include <wtf/FastMalloc.h> 456c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen 466c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen// FIXME: We'd always like to use AllocAlignmentInteger for Arena alignment 476c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen// but there is concern over the memory growth this may cause. 486c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen#ifdef WTF_USE_ARENA_ALLOC_ALIGNMENT_INTEGER 496c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen#define ARENA_ALIGN_MASK (sizeof(WTF::AllocAlignmentInteger) - 1) 506c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen#else 518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define ARENA_ALIGN_MASK 3 526c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen#endif 538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectnamespace WebCore { 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5621939df44de1705786c545cd1bf519d47250322dBen Murdochtypedef uintptr_t uword; 578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectstruct Arena { 598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Arena* next; // next arena 608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project uword base; // aligned base address 618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project uword limit; // end of arena (1+last byte) 628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project uword avail; // points to next available byte in arena 638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project}; 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectstruct ArenaPool { 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Arena first; // first arena in pool list. 678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Arena* current; // current arena. 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned int arenasize; 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project uword mask; // Mask (power-of-2 - 1) 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project}; 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectvoid InitArenaPool(ArenaPool *pool, const char *name, 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned int size, unsigned int align); 748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectvoid FinishArenaPool(ArenaPool *pool); 758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectvoid FreeArenaPool(ArenaPool *pool); 768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectvoid* ArenaAllocate(ArenaPool *pool, unsigned int nb); 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 786c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen#define ARENA_ALIGN(n) (((uword)(n) + ARENA_ALIGN_MASK) & ~ARENA_ALIGN_MASK) 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define INIT_ARENA_POOL(pool, name, size) \ 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project InitArenaPool(pool, name, size, ARENA_ALIGN_MASK + 1) 818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define ARENA_ALLOCATE(p, pool, nb) \ 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Arena *_a = (pool)->current; \ 846c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen unsigned int _nb = ARENA_ALIGN(nb); \ 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project uword _p = _a->avail; \ 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project uword _q = _p + _nb; \ 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (_q > _a->limit) \ 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project _p = (uword)ArenaAllocate(pool, _nb); \ 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else \ 908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project _a->avail = _q; \ 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p = (void *)_p; 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define ARENA_GROW(p, pool, size, incr) \ 948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Arena *_a = (pool)->current; \ 956c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen unsigned int _incr = ARENA_ALIGN(incr); \ 968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project uword _p = _a->avail; \ 978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project uword _q = _p + _incr; \ 986c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen if (_p == (uword)(p) + ARENA_ALIGN(size) && \ 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project _q <= _a->limit) { \ 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project _a->avail = _q; \ 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { \ 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p = ArenaGrow(pool, p, size, incr); \ 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define ARENA_MARK(pool) ((void *) (pool)->current->avail) 1068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define UPTRDIFF(p,q) ((uword)(p) - (uword)(q)) 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef DEBUG 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define FREE_PATTERN 0xDA 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CLEAR_UNUSED(a) ASSERT((a)->avail <= (a)->limit); \ 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project memset((void*)(a)->avail, FREE_PATTERN, \ 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project (a)->limit - (a)->avail) 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CLEAR_ARENA(a) memset((void*)(a), FREE_PATTERN, \ 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project (a)->limit - (uword)(a)) 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CLEAR_UNUSED(a) 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define CLEAR_ARENA(a) 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define ARENA_RELEASE(pool, mark) \ 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project char *_m = (char *)(mark); \ 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Arena *_a = (pool)->current; \ 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (UPTRDIFF(_m, _a->base) <= UPTRDIFF(_a->avail, _a->base)) { \ 1246c2af9490927c3c5959b5cb07461b646f8b32f6cKristian Monsen _a->avail = (uword)ARENA_ALIGN(_m); \ 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project CLEAR_UNUSED(_a); \ 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { \ 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ArenaRelease(pool, _m); \ 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define ARENA_DESTROY(pool, a, pnext) \ 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if ((pool)->current == (a)) (pool)->current = &(pool)->first; \ 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project *(pnext) = (a)->next; \ 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project CLEAR_ARENA(a); \ 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project fastFree(a); \ 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project (a) = 0; 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 140