summaryrefslogtreecommitdiffstats
path: root/kjs/collector.cpp
diff options
context:
space:
mode:
authortoma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da>2009-11-25 17:56:58 +0000
committertoma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da>2009-11-25 17:56:58 +0000
commitce4a32fe52ef09d8f5ff1dd22c001110902b60a2 (patch)
tree5ac38a06f3dde268dc7927dc155896926aaf7012 /kjs/collector.cpp
downloadtdelibs-ce4a32fe52ef09d8f5ff1dd22c001110902b60a2.tar.gz
tdelibs-ce4a32fe52ef09d8f5ff1dd22c001110902b60a2.zip
Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features.
BUG:215923 git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdelibs@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da
Diffstat (limited to 'kjs/collector.cpp')
-rw-r--r--kjs/collector.cpp312
1 files changed, 312 insertions, 0 deletions
diff --git a/kjs/collector.cpp b/kjs/collector.cpp
new file mode 100644
index 000000000..62d594329
--- /dev/null
+++ b/kjs/collector.cpp
@@ -0,0 +1,312 @@
+// -*- c-basic-offset: 2 -*-
+/*
+ * This file is part of the KDE libraries
+ * Copyright (C) 2003 Apple Computer, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ */
+
+#include "collector.h"
+
+#include "value.h"
+#include "internal.h"
+
+#ifndef MAX
+#define MAX(a,b) ((a) > (b) ? (a) : (b))
+#endif
+
+namespace KJS {
+
+// tunable parameters
+const int MINIMUM_CELL_SIZE = 56;
+const int BLOCK_SIZE = (8 * 4096);
+const int SPARE_EMPTY_BLOCKS = 2;
+const int MIN_ARRAY_SIZE = 14;
+const int GROWTH_FACTOR = 2;
+const int LOW_WATER_FACTOR = 4;
+const int ALLOCATIONS_PER_COLLECTION = 1000;
+
+// derived constants
+const int CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
+const int CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
+const int CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(int) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
+
+
+
+struct CollectorCell {
+ double memory[CELL_ARRAY_LENGTH];
+};
+
+
+struct CollectorBlock {
+ CollectorCell cells[CELLS_PER_BLOCK];
+ int usedCells;
+ CollectorCell *freeList;
+};
+
+struct CollectorHeap {
+ CollectorBlock **blocks;
+ int numBlocks;
+ int usedBlocks;
+ int firstBlockWithPossibleSpace;
+
+ CollectorCell **oversizeCells;
+ int numOversizeCells;
+ int usedOversizeCells;
+
+ int numLiveObjects;
+ int numAllocationsSinceLastCollect;
+};
+
+static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
+
+bool Collector::memoryFull = false;
+
+void* Collector::allocate(size_t s)
+{
+ if (s == 0)
+ return 0L;
+
+ // collect if needed
+ if (++heap.numAllocationsSinceLastCollect >= ALLOCATIONS_PER_COLLECTION) {
+ collect();
+ }
+
+ if (s > (unsigned)CELL_SIZE) {
+ // oversize allocator
+ if (heap.usedOversizeCells == heap.numOversizeCells) {
+ heap.numOversizeCells = MAX(MIN_ARRAY_SIZE, heap.numOversizeCells * GROWTH_FACTOR);
+ heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
+ }
+
+ void *newCell = malloc(s);
+ heap.oversizeCells[heap.usedOversizeCells] = (CollectorCell *)newCell;
+ heap.usedOversizeCells++;
+ heap.numLiveObjects++;
+
+ ((ValueImp *)(newCell))->_flags = 0;
+ return newCell;
+ }
+
+ // slab allocator
+
+ CollectorBlock *targetBlock = NULL;
+
+ int i;
+ for (i = heap.firstBlockWithPossibleSpace; i < heap.usedBlocks; i++) {
+ if (heap.blocks[i]->usedCells < CELLS_PER_BLOCK) {
+ targetBlock = heap.blocks[i];
+ break;
+ }
+ }
+
+ heap.firstBlockWithPossibleSpace = i;
+
+ if (targetBlock == NULL) {
+ // didn't find one, need to allocate a new block
+
+ if (heap.usedBlocks == heap.numBlocks) {
+ heap.numBlocks = MAX(MIN_ARRAY_SIZE, heap.numBlocks * GROWTH_FACTOR);
+ heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
+ }
+
+ targetBlock = (CollectorBlock *)calloc(1, sizeof(CollectorBlock));
+ targetBlock->freeList = targetBlock->cells;
+ heap.blocks[heap.usedBlocks] = targetBlock;
+ heap.usedBlocks++;
+ }
+
+ // find a free spot in the block and detach it from the free list
+ CollectorCell *newCell = targetBlock->freeList;
+
+ ValueImp *imp = (ValueImp*)newCell;
+ if (imp->_vd != NULL) {
+ targetBlock->freeList = (CollectorCell*)(imp->_vd);
+ } else if (targetBlock->usedCells == (CELLS_PER_BLOCK - 1)) {
+ // last cell in this block
+ targetBlock->freeList = NULL;
+ } else {
+ // all next pointers are initially 0, meaning "next cell"
+ targetBlock->freeList = newCell + 1;
+ }
+
+ targetBlock->usedCells++;
+ heap.numLiveObjects++;
+
+ ((ValueImp *)(newCell))->_flags = 0;
+ return (void *)(newCell);
+}
+
+bool Collector::collect()
+{
+ bool deleted = false;
+
+ // MARK: first mark all referenced objects recursively
+ // starting out from the set of root objects
+ if (InterpreterImp::s_hook) {
+ InterpreterImp *scr = InterpreterImp::s_hook;
+ do {
+ //fprintf( stderr, "Collector marking interpreter %p\n",(void*)scr);
+ scr->mark();
+ scr = scr->next;
+ } while (scr != InterpreterImp::s_hook);
+ }
+
+ // mark any other objects that we wouldn't delete anyway
+ for (int block = 0; block < heap.usedBlocks; block++) {
+
+ int minimumCellsToProcess = heap.blocks[block]->usedCells;
+ CollectorBlock *curBlock = heap.blocks[block];
+
+ for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
+ if (minimumCellsToProcess < cell) {
+ goto skip_block_mark;
+ }
+
+ ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
+
+ if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
+
+ if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
+ ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
+ imp->mark();
+ }
+ } else {
+ minimumCellsToProcess++;
+ }
+ }
+ skip_block_mark: ;
+ }
+
+ for (int cell = 0; cell < heap.usedOversizeCells; cell++) {
+ ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
+ if ((imp->_flags & (ValueImp::VI_CREATED|ValueImp::VI_MARKED)) == ValueImp::VI_CREATED &&
+ ((imp->_flags & ValueImp::VI_GCALLOWED) == 0 || imp->refcount != 0)) {
+ imp->mark();
+ }
+ }
+
+ // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
+
+ int emptyBlocks = 0;
+
+ for (int block = 0; block < heap.usedBlocks; block++) {
+ CollectorBlock *curBlock = heap.blocks[block];
+
+ int minimumCellsToProcess = curBlock->usedCells;
+
+ for (int cell = 0; cell < CELLS_PER_BLOCK; cell++) {
+ if (minimumCellsToProcess < cell) {
+ goto skip_block_sweep;
+ }
+
+ ValueImp *imp = (ValueImp *)(curBlock->cells + cell);
+
+ if (!(imp->_flags & ValueImp::VI_DESTRUCTED)) {
+ if (!imp->refcount && imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
+ //fprintf( stderr, "Collector::deleting ValueImp %p (%s)\n", (void*)imp, typeid(*imp).name());
+ // emulate destructing part of 'operator delete()'
+ imp->~ValueImp();
+ curBlock->usedCells--;
+ heap.numLiveObjects--;
+ deleted = true;
+
+ // put it on the free list
+ imp->_vd = (ValueImpPrivate*)curBlock->freeList;
+ curBlock->freeList = (CollectorCell *)imp;
+
+ } else {
+ imp->_flags &= ~ValueImp::VI_MARKED;
+ }
+ } else {
+ minimumCellsToProcess++;
+ }
+ }
+
+ skip_block_sweep:
+
+ if (heap.blocks[block]->usedCells == 0) {
+ emptyBlocks++;
+ if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
+#ifndef DEBUG_COLLECTOR
+ free(heap.blocks[block]);
+#endif
+ // swap with the last block so we compact as we go
+ heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
+ heap.usedBlocks--;
+ block--; // Don't move forward a step in this case
+
+ if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
+ heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
+ heap.blocks = (CollectorBlock **)realloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
+ }
+ }
+ }
+ }
+
+ if (deleted) {
+ heap.firstBlockWithPossibleSpace = 0;
+ }
+
+ int cell = 0;
+ while (cell < heap.usedOversizeCells) {
+ ValueImp *imp = (ValueImp *)heap.oversizeCells[cell];
+
+ if (!imp->refcount &&
+ imp->_flags == (ValueImp::VI_GCALLOWED | ValueImp::VI_CREATED)) {
+
+ imp->~ValueImp();
+#ifndef DEBUG_COLLECTOR
+ free((void *)imp);
+#endif
+
+ // swap with the last oversize cell so we compact as we go
+ heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
+
+ heap.usedOversizeCells--;
+ deleted = true;
+ heap.numLiveObjects--;
+
+ if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
+ heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR;
+ heap.oversizeCells = (CollectorCell **)realloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
+ }
+
+ } else {
+ imp->_flags &= ~ValueImp::VI_MARKED;
+ cell++;
+ }
+ }
+
+ heap.numAllocationsSinceLastCollect = 0;
+
+ memoryFull = (heap.numLiveObjects >= KJS_MEM_LIMIT);
+
+ return deleted;
+}
+
+int Collector::size()
+{
+ return heap.numLiveObjects;
+}
+
+#ifdef KJS_DEBUG_MEM
+void Collector::finalCheck()
+{
+}
+#endif
+
+} // namespace KJS