Reviewed by Darin.
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 23 Apr 2004 22:40:31 +0000 (22:40 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 23 Apr 2004 22:40:31 +0000 (22:40 +0000)
Implementation of conservative GC, based partly on code from
Darin. It's turned off for now, so it shouldn't have any effect on
the normal build.

        * JavaScriptCore.pbproj/project.pbxproj:
        * kjs/collector.cpp:
        (KJS::Collector::markStackObjectsConservatively):
        (KJS::Collector::markProtectedObjects):
        (KJS::Collector::collect):
        * kjs/collector.h:
        * kjs/protect.h:
        (KJS::gcProtect):
        (KJS::gcUnprotect):
        * kjs/protected_values.cpp: Added.
        (KJS::ProtectedValues::getProtectCount):
        (KJS::ProtectedValues::increaseProtectCount):
        (KJS::ProtectedValues::insert):
        (KJS::ProtectedValues::decreaseProtectCount):
        (KJS::ProtectedValues::expand):
        (KJS::ProtectedValues::shrink):
        (KJS::ProtectedValues::rehash):
        (KJS::ProtectedValues::computeHash):
        * kjs/protected_values.h: Added.
        * kjs/value.cpp:
        (ValueImp::useConservativeMark):
        (ValueImp::mark):
        (ValueImp::marked):
        * kjs/value.h:
        (KJS::ValueImp::):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@6472 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JavaScriptCore/ChangeLog
JavaScriptCore/JavaScriptCore.pbproj/project.pbxproj
JavaScriptCore/kjs/collector.cpp
JavaScriptCore/kjs/collector.h
JavaScriptCore/kjs/protect.h
JavaScriptCore/kjs/protected_values.cpp [new file with mode: 0644]
JavaScriptCore/kjs/protected_values.h [new file with mode: 0644]
JavaScriptCore/kjs/value.cpp
JavaScriptCore/kjs/value.h

index c98a50f..106187e 100644 (file)
@@ -1,3 +1,37 @@
+2004-04-23  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Darin.
+
+       Implementation of conservative GC, based partly on code from
+       Darin. It's turned off for now, so it shouldn't have any effect on
+       the normal build.
+       
+        * JavaScriptCore.pbproj/project.pbxproj:
+        * kjs/collector.cpp:
+        (KJS::Collector::markStackObjectsConservatively):
+        (KJS::Collector::markProtectedObjects):
+        (KJS::Collector::collect):
+        * kjs/collector.h:
+        * kjs/protect.h:
+        (KJS::gcProtect):
+        (KJS::gcUnprotect):
+        * kjs/protected_values.cpp: Added.
+        (KJS::ProtectedValues::getProtectCount):
+        (KJS::ProtectedValues::increaseProtectCount):
+        (KJS::ProtectedValues::insert):
+        (KJS::ProtectedValues::decreaseProtectCount):
+        (KJS::ProtectedValues::expand):
+        (KJS::ProtectedValues::shrink):
+        (KJS::ProtectedValues::rehash):
+        (KJS::ProtectedValues::computeHash):
+        * kjs/protected_values.h: Added.
+        * kjs/value.cpp:
+        (ValueImp::useConservativeMark):
+        (ValueImp::mark):
+        (ValueImp::marked):
+        * kjs/value.h:
+        (KJS::ValueImp::):
+
 === Safari-138 ===
 
 2004-04-22  Richard Williamson   <rjw@apple.com>
index 68dd112..fac82d5 100644 (file)
                                5199B266061BB1300070C006,
                                65AB004B06261CBA0076DE63,
                                65C02FBC0637462A003E7EE6,
+                               650B68DB0639033F009D42DE,
                        );
                        isa = PBXHeadersBuildPhase;
                        runOnlyForDeploymentPostprocessing = 0;
                                5182A53C06012C3000CBD2F2,
                                5199B1BF061B65BC0070C006,
                                65AB004A06261CBA0076DE63,
+                               650B68DA0639033F009D42DE,
                        );
                        isa = PBXSourcesBuildPhase;
                        runOnlyForDeploymentPostprocessing = 0;
                08FB77AEFE84172EC02AAC07 = {
                        children = (
                                938772E5038BFE19008635CE,
+                               650B68D80639033F009D42DE,
+                               650B68D90639033F009D42DE,
                                65AB004806261CBA0076DE63,
                                65AB004906261CBA0076DE63,
                                F692A84E0255597D01FF60F7,
 //652
 //653
 //654
+               650B68D80639033F009D42DE = {
+                       fileEncoding = 30;
+                       isa = PBXFileReference;
+                       lastKnownFileType = sourcecode.cpp.cpp;
+                       path = protected_values.cpp;
+                       refType = 4;
+                       sourceTree = "<group>";
+               };
+               650B68D90639033F009D42DE = {
+                       fileEncoding = 30;
+                       isa = PBXFileReference;
+                       lastKnownFileType = sourcecode.c.h;
+                       path = protected_values.h;
+                       refType = 4;
+                       sourceTree = "<group>";
+               };
+               650B68DA0639033F009D42DE = {
+                       fileRef = 650B68D80639033F009D42DE;
+                       isa = PBXBuildFile;
+                       settings = {
+                       };
+               };
+               650B68DB0639033F009D42DE = {
+                       fileRef = 650B68D90639033F009D42DE;
+                       isa = PBXBuildFile;
+                       settings = {
+                               ATTRIBUTES = (
+                                       Private,
+                               );
+                       };
+               };
                651F6412039D5B5F0078395C = {
                        fileEncoding = 30;
                        isa = PBXFileReference;
index ec6cfb6..09ef8ee 100644 (file)
@@ -162,12 +162,101 @@ void* Collector::allocate(size_t s)
   return (void *)(newCell);
 }
 
+#if TEST_CONSERVATIVE_GC
+#define IS_POINTER_ALIGNED(p) (((int)(p) & (sizeof(char *) - 1)) == 0)
+
+void Collector::markStackObjectsConservatively(void *start, void *end)
+{
+  assert(((char *)end - (char *)start) < 0x1000000);
+  assert(IS_POINTER_ALIGNED(start));
+  assert(IS_POINTER_ALIGNED(end));
+  
+  char **p = (char **)start;
+  char **e = (char **)end;
+  
+  while (p != e) {
+    char *x = *p++;
+    if (IS_POINTER_ALIGNED(x)) {
+      bool good = false;
+      for (int block = 0; block < heap.usedBlocks; block++) {
+       size_t offset = x - (char *)heap.blocks[block];
+       const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
+       if (offset <= lastCellOffset && offset % sizeof(CollectorCell) == 0) {
+         good = true;
+         break;
+       }
+      }
+      
+      if (!good) {
+       int n = heap.usedOversizeCells;
+       for (int i = 0; i != n; i++) {
+         if (x == (char *)heap.oversizeCells[i]) {
+           good = true;
+           break;
+         }
+       }
+      }
+      
+      if (good && ((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
+       ValueImp *imp = (ValueImp *)x;
+       if (!imp->marked())
+         imp->mark();
+      }
+    }
+  }
+}
+
+void Collector::markStackObjectsConservatively()
+{
+  jmp_buf registers;
+  setjmp(registers);
+
+  pthread_t thread = pthread_self();
+  void *stackBase = pthread_get_stackaddr_np(thread);
+  void *stackPointer;
+  asm("mr %0,r1" : "=r" (stackPointer));
+  markStackObjectsConservatively(stackPointer, stackBase);
+}
+
+void Collector::markProtectedObjects()
+{
+  for (int i = 0; i < ProtectedValues::_tableSize; i++) {
+    ValueImp *val = ProtectedValues::_table[i].key;
+    if (val && !val->marked()) {
+      val->mark();
+    }
+  }
+}
+
+#endif
+
 bool Collector::collect()
 {
   assert(Interpreter::lockCount() > 0);
 
   bool deleted = false;
 
+#if TEST_CONSERVATIVE_GC
+  // CONSERVATIVE MARK: mark the root set using conservative GC bit (will compare later)
+  ValueImp::useConservativeMark(true);
+
+  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);
+  }
+
+  markStackObjectsConservatively();
+  markProtectedObjects();
+
+
+  ValueImp::useConservativeMark(false);
+#endif
+
   // MARK: first mark all referenced objects recursively
   // starting out from the set of root objects
   if (InterpreterImp::s_hook) {
@@ -244,7 +333,11 @@ bool Collector::collect()
          curBlock->freeList = (CollectorCell *)imp;
 
        } else {
+#if TEST_CONSERVATIVE_GC
+         imp->_flags &= ~(ValueImp::VI_MARKED | ValueImp::VI_CONSERVATIVE_MARKED);
+#else
          imp->_flags &= ~ValueImp::VI_MARKED;
+#endif
        }
       } else {
        minimumCellsToProcess++;
index f68a0e1..be5bba3 100644 (file)
@@ -24,6 +24,8 @@
 #ifndef _KJSCOLLECTOR_H_
 #define _KJSCOLLECTOR_H_
 
+#include "value.h"
+
 #define KJS_MEM_LIMIT 500000
 
 namespace KJS {
@@ -68,6 +70,13 @@ namespace KJS {
     static const void *rootObjectClasses(); // actually returns CFSetRef
 #endif
   private:
+
+#if TEST_CONSERVATIVE_GC
+    static void markProtectedObjects();
+    static void markStackObjectsConservatively();
+    static void markStackObjectsConservatively(void *start, void *end);
+#endif
+
     static bool memoryFull;
   };
 
index 691d292..1bf2a61 100644 (file)
 #include "object.h"
 #include "reference.h"
 #include "value.h"
+#include "protected_values.h"
 
 namespace KJS {
 
-    inline void gcProtect(ValueImp *) {}
-    inline void gcUnprotect(ValueImp *) {}
+    inline void gcProtect(ValueImp *val) 
+      { 
+#if TEST_CONSERVATIVE_GC
+       ProtectedValues::increaseProtectCount(val);
+#endif
+      }
+    inline void gcUnprotect(ValueImp *val)
+      { 
+#if TEST_CONSERVATIVE_GC
+       ProtectedValues::decreaseProtectCount(val);
+#endif
+      }
     
     class ProtectedValue : public Value {
     public:
diff --git a/JavaScriptCore/kjs/protected_values.cpp b/JavaScriptCore/kjs/protected_values.cpp
new file mode 100644 (file)
index 0000000..fe6df1e
--- /dev/null
@@ -0,0 +1,217 @@
+// -*- c-basic-offset: 2 -*-
+/*
+ *  This file is part of the KDE libraries
+ *  Copyright (C) 2004 Apple Computer, Inc.
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Library 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
+ *  Library General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Library General Public License
+ *  along with this library; see the file COPYING.LIB.  If not, write to
+ *  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ *  Boston, MA 02111-1307, USA.
+ *
+ */
+
+#include "protected_values.h"
+
+namespace KJS {
+
+const int _minTableSize = 64;
+
+ProtectedValues::KeyValue *ProtectedValues::_table;
+int ProtectedValues::_tableSize;
+int ProtectedValues::_tableSizeMask;
+int ProtectedValues::_keyCount;
+
+int ProtectedValues::getProtectCount(ValueImp *k)
+{
+    if (!k)
+       return 0;
+
+    if (!_table)
+       return 0;
+
+    unsigned hash = computeHash(k);
+    
+    int i = hash & _tableSizeMask;
+#if DUMP_STATISTICS
+    ++numProbes;
+    numCollisions += _table[i].key && _table[i].key != k;
+#endif
+    while (ValueImp *key = _table[i].key) {
+        if (key == k) {
+           return _table[i].value;
+       }
+        i = (i + 1) & _tableSizeMask;
+    }
+
+    return 0;
+}
+
+
+void ProtectedValues::increaseProtectCount(ValueImp *k)
+{
+    if (!k)
+       return;
+
+    if (!_table)
+        expand();
+    
+    unsigned hash = computeHash(k);
+    
+    int i = hash & _tableSizeMask;
+#if DUMP_STATISTICS
+    ++numProbes;
+    numCollisions += _table[i].key && _table[i].key != k;
+#endif
+    while (ValueImp *key = _table[i].key) {
+        if (key == k) {
+           _table[i].value++;
+           return;
+       }
+        i = (i + 1) & _tableSizeMask;
+    }
+    
+    _table[i].key = k;
+    _table[i].value = 1;
+    ++_keyCount;
+    
+    if (_keyCount * 2 >= _tableSize)
+        expand();
+}
+
+inline void ProtectedValues::insert(ValueImp *k, int v)
+{
+    unsigned hash = computeHash(k);
+    
+    int i = hash & _tableSizeMask;
+#if DUMP_STATISTICS
+    ++numProbes;
+    numCollisions += _table[i] != 0;
+#endif
+    while (_table[i].key)
+        i = (i + 1) & _tableSizeMask;
+    
+    _table[i].key = k;
+    _table[i].value = v;
+}
+
+void ProtectedValues::decreaseProtectCount(ValueImp *k)
+{
+    if (!k)
+       return;
+
+    unsigned hash = computeHash(k);
+    
+    ValueImp *key;
+    
+    int i = hash & _tableSizeMask;
+#if DUMP_STATISTICS
+    ++numProbes;
+    numCollisions += _table[i].key && _table[i].key == k;
+#endif
+    while ((key = _table[i].key)) {
+        if (key == k)
+            break;
+        i = (i + 1) & _tableSizeMask;
+    }
+    if (!key)
+        return;
+    
+    _table[i].value--;
+
+    if (_table[i].value != 0)
+       return;
+
+    _table[i].key = 0;
+    --_keyCount;
+    
+    if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
+        shrink();
+        return;
+    }
+    
+    // Reinsert all the items to the right in the same cluster.
+    while (1) {
+        i = (i + 1) & _tableSizeMask;
+        key = _table[i].key;
+       int value = _table[i].value;
+        if (!key)
+            break;
+        _table[i].key = 0;
+        _table[i].value = 0;
+        insert(key, value);
+    }
+}
+
+void ProtectedValues::expand()
+{
+    rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
+}
+
+void ProtectedValues::shrink()
+{
+    rehash(_tableSize / 2);
+}
+
+void ProtectedValues::rehash(int newTableSize)
+{
+    int oldTableSize = _tableSize;
+    KeyValue *oldTable = _table;
+
+    _tableSize = newTableSize;
+    _tableSizeMask = newTableSize - 1;
+    _table = (KeyValue *)calloc(newTableSize, sizeof(KeyValue));
+
+    for (int i = 0; i != oldTableSize; ++i)
+        if (oldTable[i].key)
+            insert(oldTable[i].key, oldTable[i].value);
+
+    free(oldTable);
+}
+
+// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
+// or anything like that.
+const unsigned PHI = 0x9e3779b9U;
+
+// This hash algorithm comes from:
+// http://burtleburtle.net/bob/hash/hashfaq.html
+// http://burtleburtle.net/bob/hash/doobs.html
+unsigned ProtectedValues::computeHash(ValueImp *pointer)
+{
+    int length = sizeof(ValueImp *);
+    char s[sizeof(ValueImp *)];
+               
+    memcpy((void *)s, (void *)&pointer, sizeof(ValueImp *));
+
+    unsigned h = PHI;
+    h += length;
+    h += (h << 10); 
+    h ^= (h << 6); 
+
+    for (int i = 0; i < length; i++) {
+        h += (unsigned char)s[i];
+       h += (h << 10); 
+       h ^= (h << 6); 
+    }
+
+    h += (h << 3);
+    h ^= (h >> 11);
+    h += (h << 15);
+
+    if (h == 0)
+        h = 0x80000000;
+
+    return h;
+}
+
+
+} // namespace
diff --git a/JavaScriptCore/kjs/protected_values.h b/JavaScriptCore/kjs/protected_values.h
new file mode 100644 (file)
index 0000000..40bb152
--- /dev/null
@@ -0,0 +1,60 @@
+// -*- c-basic-offset: 2 -*-
+/*
+ *  This file is part of the KDE libraries
+ *  Copyright (C) 2004 Apple Computer, Inc.
+ *
+ *  This library is free software; you can redistribute it and/or
+ *  modify it under the terms of the GNU Library 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
+ *  Library General Public License for more details.
+ *
+ *  You should have received a copy of the GNU Library General Public License
+ *  along with this library; see the file COPYING.LIB.  If not, write to
+ *  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ *  Boston, MA 02111-1307, USA.
+ *
+ */
+
+
+#ifndef _KJS_PROTECTED_VALUES_H_
+#define _KJS_PROTECTED_VALUES_H_
+
+namespace KJS {
+    class ValueImp;
+
+    class ProtectedValues {
+       struct KeyValue {
+           ValueImp *key;
+           int value;
+       };
+
+    public:
+       static void increaseProtectCount(ValueImp *key);
+       static void decreaseProtectCount(ValueImp *key);
+
+       static int getProtectCount(ValueImp *key);
+
+    private:
+       static void insert(ValueImp *key, int value);
+       static void expand();
+       static void shrink();
+       static void rehash(int newTableSize);
+       static unsigned computeHash(ValueImp *pointer);
+
+       // let the collector scan the table directly for protected
+       // values
+       friend class Collector;
+
+       static KeyValue * ProtectedValues::_table;
+       static int ProtectedValues::_tableSize;
+       static int ProtectedValues::_tableSizeMask;
+       static int ProtectedValues::_keyCount;
+    };
+}
+
+#endif
index a2fb5cf..88913da 100644 (file)
@@ -56,16 +56,44 @@ ValueImp::~ValueImp()
   //fprintf(stderr,"ValueImp::~ValueImp %p\n",(void*)this);
 }
 
+#if TEST_CONSERVATIVE_GC
+static bool conservativeMark = false;
+
+void ValueImp::useConservativeMark(bool use)
+{
+  conservativeMark = use;
+}
+#endif
+
 void ValueImp::mark()
 {
   //fprintf(stderr,"ValueImp::mark %p\n",(void*)this);
+#if TEST_CONSERVATIVE_GC
+  if (conservativeMark) {
+    _flags |= VI_CONSERVATIVE_MARKED;
+  } else {
+    if (!(_flags | VI_CONSERVATIVE_MARKED)) {
+      printf("Conservative collector missed ValueImp 0x%x.\n", (int)this);
+    }
+    _flags |= VI_MARKED;
+  }
+#else
   _flags |= VI_MARKED;
+#endif
 }
 
 bool ValueImp::marked() const
 {
   // Simple numbers are always considered marked.
+#if TEST_CONSERVATIVE_GC
+  if (conservativeMark) {
+    return SimpleNumber::is(this) || (_flags & VI_CONSERVATIVE_MARKED);
+  } else {
+    return SimpleNumber::is(this) || (_flags & VI_MARKED);
+  }
+#else
   return SimpleNumber::is(this) || (_flags & VI_MARKED);
+#endif
 }
 
 void ValueImp::setGcAllowed()
index 9fde98f..c225352 100644 (file)
@@ -25,6 +25,8 @@
 #ifndef _KJS_VALUE_H_
 #define _KJS_VALUE_H_
 
+#define TEST_CONSERVATIVE_GC 0
+
 #ifndef NDEBUG // protection against problems if committing with KJS_VERBOSE on
 
 // Uncomment this to enable very verbose output from KJS
@@ -148,11 +150,18 @@ namespace KJS {
       VI_MARKED = 1,
       VI_GCALLOWED = 2,
       VI_CREATED = 4
+#if TEST_CONSERVATIVE_GC
+      , VI_CONSERVATIVE_MARKED = 8
+#endif
     }; // VI means VALUEIMPL
 
     // Give a compile time error if we try to copy one of these.
     ValueImp(const ValueImp&);
     ValueImp& operator=(const ValueImp&);
+
+#if TEST_CONSERVATIVE_GC
+    static void useConservativeMark(bool);
+#endif
   };
 
   /**