JavaScriptCore/kjs/collector.cpp

   1 // -*- mode: c++; c-basic-offset: 4 -*-
   2 /*
   3  *  This file is part of the KDE libraries
   4  *  Copyright (C) 2003, 2004, 2005, 2006 Apple Computer, Inc.
   5  *
   6  *  This library is free software; you can redistribute it and/or
   7  *  modify it under the terms of the GNU Lesser General Public
   8  *  License as published by the Free Software Foundation; either
   9  *  version 2 of the License, or (at your option) any later version.
  10  *
  11  *  This library is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  *  Lesser General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU Lesser General Public
  17  *  License along with this library; if not, write to the Free Software
  18  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #include "config.h"
  23 #include "collector.h"
  24
  25 #include <wtf/FastMalloc.h>
  26 #include <wtf/FastMallocInternal.h>
  27 #include <wtf/HashCountedSet.h>
  28 #include "internal.h"
  29 #include "list.h"
  30 #include "value.h"
  31
  32 #include <setjmp.h>
  33 #include <algorithm>
  34
  35 #if PLATFORM(DARWIN)
  36
  37 #include <pthread.h>
  38 #include <mach/mach_port.h>
  39 #include <mach/task.h>
  40 #include <mach/thread_act.h>
  41
  42 #elif PLATFORM(WIN_OS)
  43
  44 #include <windows.h>
  45
  46 #elif PLATFORM(UNIX)
  47
  48 #include <pthread.h>
  49
  50 #if HAVE(PTHREAD_NP_H)
  51 #include <pthread_np.h>
  52 #endif
  53
  54 #endif
  55
  56 #define DEBUG_COLLECTOR 0
  57
  58 using std::max;
  59
  60 namespace KJS {
  61
  62 // tunable parameters
  63 const size_t MINIMUM_CELL_SIZE = 56;
  64 const size_t BLOCK_SIZE = (8 * 4096);
  65 const size_t SPARE_EMPTY_BLOCKS = 2;
  66 const size_t MIN_ARRAY_SIZE = 14;
  67 const size_t GROWTH_FACTOR = 2;
  68 const size_t LOW_WATER_FACTOR = 4;
  69 const size_t ALLOCATIONS_PER_COLLECTION = 1000;
  70
  71 // derived constants
  72 const size_t CELL_ARRAY_LENGTH = (MINIMUM_CELL_SIZE / sizeof(double)) + (MINIMUM_CELL_SIZE % sizeof(double) != 0 ? sizeof(double) : 0);
  73 const size_t CELL_SIZE = CELL_ARRAY_LENGTH * sizeof(double);
  74 const size_t CELLS_PER_BLOCK = ((BLOCK_SIZE * 8 - sizeof(uint32_t) * 8 - sizeof(void *) * 8) / (CELL_SIZE * 8));
  75
  76
  77
  78 struct CollectorCell {
  79   union {
  80     double memory[CELL_ARRAY_LENGTH];
  81     struct {
  82       void *zeroIfFree;
  83       ptrdiff_t next;
  84     } freeCell;
  85   } u;
  86 };
  87
  88
  89 struct CollectorBlock {
  90   CollectorCell cells[CELLS_PER_BLOCK];
  91   uint32_t usedCells;
  92   CollectorCell *freeList;
  93 };
  94
  95 struct CollectorHeap {
  96   CollectorBlock **blocks;
  97   size_t numBlocks;
  98   size_t usedBlocks;
  99   size_t firstBlockWithPossibleSpace;
 100
 101   CollectorCell **oversizeCells;
 102   size_t numOversizeCells;
 103   size_t usedOversizeCells;
 104
 105   size_t numLiveObjects;
 106   size_t numLiveObjectsAtLastCollect;
 107 };
 108
 109 static CollectorHeap heap = {NULL, 0, 0, 0, NULL, 0, 0, 0, 0};
 110
 111 bool Collector::memoryFull = false;
 112
 113 void* Collector::allocate(size_t s)
 114 {
 115   assert(JSLock::lockCount() > 0);
 116
 117   // collect if needed
 118   size_t numLiveObjects = heap.numLiveObjects;
 119   if (numLiveObjects - heap.numLiveObjectsAtLastCollect >= ALLOCATIONS_PER_COLLECTION) {
 120     collect();
 121     numLiveObjects = heap.numLiveObjects;
 122   }
 123
 124   if (s > CELL_SIZE) {
 125     // oversize allocator
 126
 127     size_t usedOversizeCells = heap.usedOversizeCells;
 128     size_t numOversizeCells = heap.numOversizeCells;
 129
 130     if (usedOversizeCells == numOversizeCells) {
 131       numOversizeCells = max(MIN_ARRAY_SIZE, numOversizeCells * GROWTH_FACTOR);
 132       heap.numOversizeCells = numOversizeCells;
 133       heap.oversizeCells = static_cast<CollectorCell **>(fastRealloc(heap.oversizeCells, numOversizeCells * sizeof(CollectorCell *)));
 134     }
 135
 136     void *newCell = fastMalloc(s);
 137     heap.oversizeCells[usedOversizeCells] = static_cast<CollectorCell *>(newCell);
 138     heap.usedOversizeCells = usedOversizeCells + 1;
 139     heap.numLiveObjects = numLiveObjects + 1;
 140
 141     return newCell;
 142   }
 143
 144   // slab allocator
 145
 146   size_t usedBlocks = heap.usedBlocks;
 147
 148   size_t i = heap.firstBlockWithPossibleSpace;
 149   CollectorBlock *targetBlock;
 150   size_t targetBlockUsedCells;
 151   if (i != usedBlocks) {
 152     targetBlock = heap.blocks[i];
 153     targetBlockUsedCells = targetBlock->usedCells;
 154     assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
 155     while (targetBlockUsedCells == CELLS_PER_BLOCK) {
 156       if (++i == usedBlocks)
 157         goto allocateNewBlock;
 158       targetBlock = heap.blocks[i];
 159       targetBlockUsedCells = targetBlock->usedCells;
 160       assert(targetBlockUsedCells <= CELLS_PER_BLOCK);
 161     }
 162     heap.firstBlockWithPossibleSpace = i;
 163   } else {
 164 allocateNewBlock:
 165     // didn't find one, need to allocate a new block
 166     size_t numBlocks = heap.numBlocks;
 167     if (usedBlocks == numBlocks) {
 168       numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
 169       heap.numBlocks = numBlocks;
 170       heap.blocks = static_cast<CollectorBlock **>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock *)));
 171     }
 172
 173     targetBlock = static_cast<CollectorBlock *>(fastCalloc(1, sizeof(CollectorBlock)));
 174     targetBlock->freeList = targetBlock->cells;
 175     targetBlockUsedCells = 0;
 176     heap.blocks[usedBlocks] = targetBlock;
 177     heap.usedBlocks = usedBlocks + 1;
 178     heap.firstBlockWithPossibleSpace = usedBlocks;
 179   }
 180
 181   // find a free spot in the block and detach it from the free list
 182   CollectorCell *newCell = targetBlock->freeList;
 183
 184   // "next" field is a byte offset -- 0 means next cell, so a zeroed block is already initialized
 185   // could avoid the casts by using a cell offset, but this avoids a relatively-slow multiply
 186   targetBlock->freeList = reinterpret_cast<CollectorCell *>(reinterpret_cast<char *>(newCell + 1) + newCell->u.freeCell.next);
 187
 188   targetBlock->usedCells = targetBlockUsedCells + 1;
 189   heap.numLiveObjects = numLiveObjects + 1;
 190
 191   return newCell;
 192 }
 193
 194 #if USE(MULTIPLE_THREADS)
 195
 196 struct Collector::Thread {
 197   Thread(pthread_t pthread, mach_port_t mthread) : posixThread(pthread), machThread(mthread) {}
 198   Thread *next;
 199   pthread_t posixThread;
 200   mach_port_t machThread;
 201 };
 202
 203 pthread_key_t registeredThreadKey;
 204 pthread_once_t registeredThreadKeyOnce = PTHREAD_ONCE_INIT;
 205 Collector::Thread *registeredThreads;
 206
 207 static void destroyRegisteredThread(void *data)
 208 {
 209   Collector::Thread *thread = (Collector::Thread *)data;
 210
 211   if (registeredThreads == thread) {
 212     registeredThreads = registeredThreads->next;
 213   } else {
 214     Collector::Thread *last = registeredThreads;
 215     for (Collector::Thread *t = registeredThreads->next; t != NULL; t = t->next) {
 216       if (t == thread) {
 217         last->next = t->next;
 218           break;
 219       }
 220       last = t;
 221     }
 222   }
 223
 224   delete thread;
 225 }
 226
 227 static void initializeRegisteredThreadKey()
 228 {
 229   pthread_key_create(&registeredThreadKey, destroyRegisteredThread);
 230 }
 231
 232 void Collector::registerThread()
 233 {
 234   pthread_once(&registeredThreadKeyOnce, initializeRegisteredThreadKey);
 235
 236   if (!pthread_getspecific(registeredThreadKey)) {
 237     pthread_t pthread = pthread_self();
 238     WTF::fastMallocRegisterThread(pthread);
 239     Collector::Thread *thread = new Collector::Thread(pthread, pthread_mach_thread_np(pthread));
 240     thread->next = registeredThreads;
 241     registeredThreads = thread;
 242     pthread_setspecific(registeredThreadKey, thread);
 243   }
 244 }
 245
 246 #endif
 247
 248 #define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)
 249
 250 // cells are 8-byte aligned
 251 #define IS_CELL_ALIGNED(p) (((intptr_t)(p) & 7) == 0)
 252
 253 void Collector::markStackObjectsConservatively(void *start, void *end)
 254 {
 255   if (start > end) {
 256     void *tmp = start;
 257     start = end;
 258     end = tmp;
 259   }
 260
 261   assert(((char *)end - (char *)start) < 0x1000000);
 262   assert(IS_POINTER_ALIGNED(start));
 263   assert(IS_POINTER_ALIGNED(end));
 264
 265   char **p = (char **)start;
 266   char **e = (char **)end;
 267
 268   size_t usedBlocks = heap.usedBlocks;
 269   CollectorBlock **blocks = heap.blocks;
 270   size_t usedOversizeCells = heap.usedOversizeCells;
 271   CollectorCell **oversizeCells = heap.oversizeCells;
 272
 273   const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);
 274
 275   while (p != e) {
 276     char *x = *p++;
 277     if (IS_CELL_ALIGNED(x) && x) {
 278       for (size_t block = 0; block < usedBlocks; block++) {
 279         size_t offset = x - reinterpret_cast<char *>(blocks[block]);
 280         if (offset <= lastCellOffset && offset % sizeof(CollectorCell) == 0)
 281           goto gotGoodPointer;
 282       }
 283       for (size_t i = 0; i != usedOversizeCells; i++)
 284         if (x == reinterpret_cast<char *>(oversizeCells[i]))
 285           goto gotGoodPointer;
 286       continue;
 287
 288 gotGoodPointer:
 289       if (((CollectorCell *)x)->u.freeCell.zeroIfFree != 0) {
 290         JSCell *imp = reinterpret_cast<JSCell *>(x);
 291         if (!imp->marked())
 292           imp->mark();
 293       }
 294     }
 295   }
 296 }
 297
 298 void Collector::markCurrentThreadConservatively()
 299 {
 300     jmp_buf registers;
 301     setjmp(registers);
 302
 303 #if PLATFORM(DARWIN)
 304     pthread_t thread = pthread_self();
 305     void *stackBase = pthread_get_stackaddr_np(thread);
 306 #elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)
 307     NT_TIB *pTib;
 308     __asm {
 309         MOV EAX, FS:[18h]
 310         MOV pTib, EAX
 311     }
 312     void *stackBase = (void *)pTib->StackBase;
 313 #elif PLATFORM(UNIX)
 314     static void *stackBase = 0;
 315     static pthread_t stackThread;
 316     pthread_t thread = pthread_self();
 317     if (stackBase == 0 || thread != stackThread) {
 318         pthread_attr_t sattr;
 319 #if HAVE(PTHREAD_NP_H)
 320         // e.g. on FreeBSD 5.4, neundorf@kde.org
 321         pthread_attr_get_np(thread, &sattr);
 322 #else
 323         // FIXME: this function is non-portable; other POSIX systems may have different np alternatives
 324         pthread_getattr_np(thread, &sattr);
 325 #endif
 326         // Should work but fails on Linux (?)
 327         //  pthread_attr_getstack(&sattr, &stackBase, &stackSize);
 328         pthread_attr_getstackaddr(&sattr, &stackBase);
 329         assert(stackBase);
 330         stackThread = thread;
 331     }
 332 #else
 333 #error Need a way to get the stack base on this platform
 334 #endif
 335
 336     int dummy;
 337     void *stackPointer = &dummy;
 338
 339     markStackObjectsConservatively(stackPointer, stackBase);
 340 }
 341
 342 #if USE(MULTIPLE_THREADS)
 343
 344 typedef unsigned long usword_t; // word size, assumed to be either 32 or 64 bit
 345
 346 void Collector::markOtherThreadConservatively(Thread *thread)
 347 {
 348   thread_suspend(thread->machThread);
 349
 350 #if PLATFORM(X86)
 351   i386_thread_state_t regs;
 352   unsigned user_count = sizeof(regs)/sizeof(int);
 353   thread_state_flavor_t flavor = i386_THREAD_STATE;
 354 #elif PLATFORM(X86_64)
 355   x86_thread_state64_t  regs;
 356   unsigned user_count = x86_THREAD_STATE64_COUNT;
 357   thread_state_flavor_t flavor = x86_THREAD_STATE64;
 358 #elif PLATFORM(PPC)
 359   ppc_thread_state_t  regs;
 360   unsigned user_count = PPC_THREAD_STATE_COUNT;
 361   thread_state_flavor_t flavor = PPC_THREAD_STATE;
 362 #elif PLATFORM(PPC64)
 363   ppc_thread_state64_t  regs;
 364   unsigned user_count = PPC_THREAD_STATE64_COUNT;
 365   thread_state_flavor_t flavor = PPC_THREAD_STATE64;
 366 #else
 367 #error Unknown Architecture
 368 #endif
 369   // get the thread register state
 370   thread_get_state(thread->machThread, flavor, (thread_state_t)&regs, &user_count);
 371
 372   // scan the registers
 373   markStackObjectsConservatively((void *)&regs, (void *)((char *)&regs + (user_count * sizeof(usword_t))));
 374
 375   // scan the stack
 376 #if PLATFORM(X86) && __DARWIN_UNIX03
 377   markStackObjectsConservatively((void *)regs.__esp, pthread_get_stackaddr_np(thread->posixThread));
 378 #elif PLATFORM(X86)
 379   markStackObjectsConservatively((void *)regs.esp, pthread_get_stackaddr_np(thread->posixThread));
 380 #elif PLATFORM(X86_64) && __DARWIN_UNIX03
 381   markStackObjectsConservatively((void *)regs.__rsp, pthread_get_stackaddr_np(thread->posixThread));
 382 #elif PLATFORM(X86_64)
 383   markStackObjectsConservatively((void *)regs.rsp, pthread_get_stackaddr_np(thread->posixThread));
 384 #elif (PLATFORM(PPC) || PLATFORM(PPC64)) && __DARWIN_UNIX03
 385   markStackObjectsConservatively((void *)regs.__r1, pthread_get_stackaddr_np(thread->posixThread));
 386 #elif PLATFORM(PPC) || PLATFORM(PPC64)
 387   markStackObjectsConservatively((void *)regs.r1, pthread_get_stackaddr_np(thread->posixThread));
 388 #else
 389 #error Unknown Architecture
 390 #endif
 391
 392   thread_resume(thread->machThread);
 393 }
 394
 395 #endif
 396
 397 void Collector::markStackObjectsConservatively()
 398 {
 399   markCurrentThreadConservatively();
 400
 401 #if USE(MULTIPLE_THREADS)
 402   for (Thread *thread = registeredThreads; thread != NULL; thread = thread->next) {
 403     if (thread->posixThread != pthread_self()) {
 404       markOtherThreadConservatively(thread);
 405     }
 406   }
 407 #endif
 408 }
 409
 410 typedef HashCountedSet<JSCell *> ProtectCounts;
 411
 412 static ProtectCounts& protectedValues()
 413 {
 414     static ProtectCounts pv;
 415     return pv;
 416 }
 417
 418 void Collector::protect(JSValue *k)
 419 {
 420     assert(k);
 421     assert(JSLock::lockCount() > 0);
 422
 423     if (JSImmediate::isImmediate(k))
 424       return;
 425
 426     protectedValues().add(k->downcast());
 427 }
 428
 429 void Collector::unprotect(JSValue *k)
 430 {
 431     assert(k);
 432     assert(JSLock::lockCount() > 0);
 433
 434     if (JSImmediate::isImmediate(k))
 435       return;
 436
 437     protectedValues().remove(k->downcast());
 438 }
 439
 440 void Collector::markProtectedObjects()
 441 {
 442   ProtectCounts& pv = protectedValues();
 443   ProtectCounts::iterator end = pv.end();
 444   for (ProtectCounts::iterator it = pv.begin(); it != end; ++it) {
 445     JSCell *val = it->first;
 446     if (!val->marked())
 447       val->mark();
 448   }
 449 }
 450
 451 bool Collector::collect()
 452 {
 453   assert(JSLock::lockCount() > 0);
 454
 455 #if USE(MULTIPLE_THREADS)
 456     bool currentThreadIsMainThread = !pthread_is_threaded_np() || pthread_main_np();
 457 #else
 458     bool currentThreadIsMainThread = true;
 459 #endif
 460
 461   if (Interpreter::s_hook) {
 462     Interpreter* scr = Interpreter::s_hook;
 463     do {
 464       scr->mark(currentThreadIsMainThread);
 465       scr = scr->next;
 466     } while (scr != Interpreter::s_hook);
 467   }
 468
 469   // MARK: first mark all referenced objects recursively starting out from the set of root objects
 470
 471   markStackObjectsConservatively();
 472   markProtectedObjects();
 473   List::markProtectedLists();
 474
 475   // SWEEP: delete everything with a zero refcount (garbage) and unmark everything else
 476
 477   size_t emptyBlocks = 0;
 478   size_t numLiveObjects = heap.numLiveObjects;
 479
 480   for (size_t block = 0; block < heap.usedBlocks; block++) {
 481     CollectorBlock *curBlock = heap.blocks[block];
 482
 483     size_t usedCells = curBlock->usedCells;
 484     CollectorCell *freeList = curBlock->freeList;
 485
 486     if (usedCells == CELLS_PER_BLOCK) {
 487       // special case with a block where all cells are used -- testing indicates this happens often
 488       for (size_t i = 0; i < CELLS_PER_BLOCK; i++) {
 489         CollectorCell *cell = curBlock->cells + i;
 490         JSCell *imp = reinterpret_cast<JSCell *>(cell);
 491         if (imp->m_marked) {
 492           imp->m_marked = false;
 493         } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
 494           imp->~JSCell();
 495           --usedCells;
 496           --numLiveObjects;
 497
 498           // put cell on the free list
 499           cell->u.freeCell.zeroIfFree = 0;
 500           cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
 501           freeList = cell;
 502         }
 503       }
 504     } else {
 505       size_t minimumCellsToProcess = usedCells;
 506       for (size_t i = 0; i < minimumCellsToProcess; i++) {
 507         CollectorCell *cell = curBlock->cells + i;
 508         if (cell->u.freeCell.zeroIfFree == 0) {
 509           ++minimumCellsToProcess;
 510         } else {
 511           JSCell *imp = reinterpret_cast<JSCell *>(cell);
 512           if (imp->m_marked) {
 513             imp->m_marked = false;
 514           } else if (currentThreadIsMainThread || imp->m_destructorIsThreadSafe) {
 515             imp->~JSCell();
 516             --usedCells;
 517             --numLiveObjects;
 518
 519             // put cell on the free list
 520             cell->u.freeCell.zeroIfFree = 0;
 521             cell->u.freeCell.next = reinterpret_cast<char *>(freeList) - reinterpret_cast<char *>(cell + 1);
 522             freeList = cell;
 523           }
 524         }
 525       }
 526     }
 527
 528     curBlock->usedCells = usedCells;
 529     curBlock->freeList = freeList;
 530
 531     if (usedCells == 0) {
 532       emptyBlocks++;
 533       if (emptyBlocks > SPARE_EMPTY_BLOCKS) {
 534 #if !DEBUG_COLLECTOR
 535         fastFree(curBlock);
 536 #endif
 537         // swap with the last block so we compact as we go
 538         heap.blocks[block] = heap.blocks[heap.usedBlocks - 1];
 539         heap.usedBlocks--;
 540         block--; // Don't move forward a step in this case
 541
 542         if (heap.numBlocks > MIN_ARRAY_SIZE && heap.usedBlocks < heap.numBlocks / LOW_WATER_FACTOR) {
 543           heap.numBlocks = heap.numBlocks / GROWTH_FACTOR;
 544           heap.blocks = (CollectorBlock **)fastRealloc(heap.blocks, heap.numBlocks * sizeof(CollectorBlock *));
 545         }
 546       }
 547     }
 548   }
 549
 550   if (heap.numLiveObjects != numLiveObjects)
 551     heap.firstBlockWithPossibleSpace = 0;
 552
 553   size_t cell = 0;
 554   while (cell < heap.usedOversizeCells) {
 555     JSCell *imp = (JSCell *)heap.oversizeCells[cell];
 556
 557     if (!imp->m_marked && (currentThreadIsMainThread || imp->m_destructorIsThreadSafe)) {
 558       imp->~JSCell();
 559 #if DEBUG_COLLECTOR
 560       heap.oversizeCells[cell]->u.freeCell.zeroIfFree = 0;
 561 #else
 562       fastFree(imp);
 563 #endif
 564
 565       // swap with the last oversize cell so we compact as we go
 566       heap.oversizeCells[cell] = heap.oversizeCells[heap.usedOversizeCells - 1];
 567
 568       heap.usedOversizeCells--;
 569       numLiveObjects--;
 570
 571       if (heap.numOversizeCells > MIN_ARRAY_SIZE && heap.usedOversizeCells < heap.numOversizeCells / LOW_WATER_FACTOR) {
 572         heap.numOversizeCells = heap.numOversizeCells / GROWTH_FACTOR;
 573         heap.oversizeCells = (CollectorCell **)fastRealloc(heap.oversizeCells, heap.numOversizeCells * sizeof(CollectorCell *));
 574       }
 575     } else {
 576       imp->m_marked = false;
 577       cell++;
 578     }
 579   }
 580
 581   bool deleted = heap.numLiveObjects != numLiveObjects;
 582
 583   heap.numLiveObjects = numLiveObjects;
 584   heap.numLiveObjectsAtLastCollect = numLiveObjects;
 585
 586   memoryFull = (numLiveObjects >= KJS_MEM_LIMIT);
 587
 588   return deleted;
 589 }
 590
 591 size_t Collector::size()
 592 {
 593   return heap.numLiveObjects;
 594 }
 595
 596 #ifdef KJS_DEBUG_MEM
 597 void Collector::finalCheck()
 598 {
 599 }
 600 #endif
 601
 602 size_t Collector::numInterpreters()
 603 {
 604   size_t count = 0;
 605   if (Interpreter::s_hook) {
 606     Interpreter* scr = Interpreter::s_hook;
 607     do {
 608       ++count;
 609       scr = scr->next;
 610     } while (scr != Interpreter::s_hook);
 611   }
 612   return count;
 613 }
 614
 615 size_t Collector::numProtectedObjects()
 616 {
 617   return protectedValues().size();
 618 }
 619
 620 static const char *typeName(JSCell *val)
 621 {
 622   const char *name = "???";
 623   switch (val->type()) {
 624     case UnspecifiedType:
 625       break;
 626     case UndefinedType:
 627       name = "undefined";
 628       break;
 629     case NullType:
 630       name = "null";
 631       break;
 632     case BooleanType:
 633       name = "boolean";
 634       break;
 635     case StringType:
 636       name = "string";
 637       break;
 638     case NumberType:
 639       name = "number";
 640       break;
 641     case ObjectType: {
 642       const ClassInfo *info = static_cast<JSObject *>(val)->classInfo();
 643       name = info ? info->className : "Object";
 644       break;
 645     }
 646     case GetterSetterType:
 647       name = "gettersetter";
 648       break;
 649   }
 650   return name;
 651 }
 652
 653 HashCountedSet<const char*>* Collector::rootObjectTypeCounts()
 654 {
 655     HashCountedSet<const char*>* counts = new HashCountedSet<const char*>;
 656
 657     ProtectCounts& pv = protectedValues();
 658     ProtectCounts::iterator end = pv.end();
 659     for (ProtectCounts::iterator it = pv.begin(); it != end; ++it)
 660         counts->add(typeName(it->first));
 661
 662     return counts;
 663 }
 664
 665 } // namespace KJS