js/src/jsgc.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is Mozilla Communicator client code, released
  17  * March 31, 1998.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * Netscape Communications Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 1998
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #ifndef jsgc_h___
  41 #define jsgc_h___
  42
  43 /* Gross special case for Gecko, which defines malloc/calloc/free. */
  44 #ifdef mozilla_mozalloc_macro_wrappers_h
  45 #  define JS_GC_UNDEFD_MOZALLOC_WRAPPERS
  46 /* The "anti-header" */
  47 #  include "mozilla/mozalloc_undef_macro_wrappers.h"
  48 #endif
  49
  50 /*
  51  * JS Garbage Collector.
  52  */
  53 #include <setjmp.h>
  54
  55 #include "jstypes.h"
  56 #include "jsprvtd.h"
  57 #include "jspubtd.h"
  58 #include "jsdhash.h"
  59 #include "jsbit.h"
  60 #include "jsgcchunk.h"
  61 #include "jsutil.h"
  62 #include "jsvector.h"
  63 #include "jsversion.h"
  64 #include "jsobj.h"
  65 #include "jsfun.h"
  66 #include "jsgcstats.h"
  67 #include "jscell.h"
  68
  69 struct JSCompartment;
  70
  71 extern "C" void
  72 js_TraceXML(JSTracer *trc, JSXML* thing);
  73
  74 #if JS_STACK_GROWTH_DIRECTION > 0
  75 # define JS_CHECK_STACK_SIZE(limit, lval)  ((jsuword)(lval) < limit)
  76 #else
  77 # define JS_CHECK_STACK_SIZE(limit, lval)  ((jsuword)(lval) > limit)
  78 #endif
  79
  80 namespace js {
  81
  82 struct Shape;
  83
  84 namespace gc {
  85
  86 /*
  87  * The kind of GC thing with a finalizer. The external strings follow the
  88  * ordinary string to simplify js_GetExternalStringGCType.
  89  */
  90 enum FinalizeKind {
  91     FINALIZE_OBJECT0,
  92     FINALIZE_OBJECT2,
  93     FINALIZE_OBJECT4,
  94     FINALIZE_OBJECT8,
  95     FINALIZE_OBJECT12,
  96     FINALIZE_OBJECT16,
  97     FINALIZE_OBJECT_LAST = FINALIZE_OBJECT16,
  98     FINALIZE_FUNCTION,
  99 #if JS_HAS_XML_SUPPORT
 100     FINALIZE_XML,
 101 #endif
 102     FINALIZE_SHORT_STRING,
 103     FINALIZE_STRING,
 104     FINALIZE_EXTERNAL_STRING,
 105     FINALIZE_LIMIT
 106 };
 107
 108 const uintN JS_FINALIZE_OBJECT_LIMIT = 6;
 109
 110 /* Every arena has a header. */
 111 struct ArenaHeader {
 112     JSCompartment   *compartment;
 113     Arena<FreeCell> *next;
 114     FreeCell        *freeList;
 115     unsigned        thingKind;
 116     bool            isUsed;
 117     size_t          thingSize;
 118 #ifdef DEBUG
 119     bool            hasFreeThings;
 120 #endif
 121 };
 122
 123 template <typename T>
 124 union ThingOrCell {
 125     T               t;
 126     FreeCell        cell;
 127 };
 128
 129 template <typename T, size_t N, size_t R>
 130 struct Things {
 131     ThingOrCell<T>  things[N];
 132     char            filler[R];
 133 };
 134
 135 template <typename T, size_t N>
 136 struct Things<T, N, 0> {
 137     ThingOrCell<T>  things[N];
 138 };
 139
 140 template <typename T>
 141 struct Arena {
 142     static const size_t ArenaSize = 4096;
 143
 144     struct AlignedArenaHeader {
 145         T align[(sizeof(ArenaHeader) + sizeof(T) - 1) / sizeof(T)];
 146     };
 147
 148     /* We want things in the arena to be aligned, so align the header. */
 149     union {
 150         ArenaHeader aheader;
 151         AlignedArenaHeader align;
 152     };
 153
 154     static const size_t ThingsPerArena = (ArenaSize - sizeof(AlignedArenaHeader)) / sizeof(T);
 155     static const size_t FillerSize = ArenaSize - sizeof(AlignedArenaHeader) - sizeof(T) * ThingsPerArena;
 156     Things<T, ThingsPerArena, FillerSize> t;
 157
 158     inline Chunk *chunk() const;
 159     inline size_t arenaIndex() const;
 160
 161     inline ArenaHeader *header() { return &aheader; };
 162
 163     inline MarkingDelay *getMarkingDelay() const;
 164     inline ArenaBitmap *bitmap() const;
 165
 166     inline ConservativeGCTest mark(T *thing, JSTracer *trc);
 167     void markDelayedChildren(JSTracer *trc);
 168     inline bool inFreeList(void *thing) const;
 169     inline T *getAlignedThing(void *thing);
 170 #ifdef DEBUG
 171     inline bool assureThingIsAligned(void *thing);
 172 #endif
 173
 174     void init(JSCompartment *compartment, unsigned thingKind);
 175 };
 176 JS_STATIC_ASSERT(sizeof(Arena<FreeCell>) == 4096);
 177
 178 /*
 179  * Live objects are marked black. How many other additional colors are available
 180  * depends on the size of the GCThing.
 181  */
 182 static const uint32 BLACK = 0;
 183
 184 /* An arena bitmap contains enough mark bits for all the cells in an arena. */
 185 struct ArenaBitmap {
 186     static const size_t BitCount = Arena<FreeCell>::ArenaSize / Cell::CellSize;
 187     static const size_t BitWords = BitCount / JS_BITS_PER_WORD;
 188
 189     uintptr_t bitmap[BitWords];
 190
 191     JS_ALWAYS_INLINE bool isMarked(size_t bit, uint32 color) {
 192         bit += color;
 193         JS_ASSERT(bit < BitCount);
 194         uintptr_t *word = &bitmap[bit / JS_BITS_PER_WORD];
 195         return *word & (uintptr_t(1) << (bit % JS_BITS_PER_WORD));
 196     }
 197
 198     JS_ALWAYS_INLINE bool markIfUnmarked(size_t bit, uint32 color) {
 199         JS_ASSERT(bit + color < BitCount);
 200         uintptr_t *word = &bitmap[bit / JS_BITS_PER_WORD];
 201         uintptr_t mask = (uintptr_t(1) << (bit % JS_BITS_PER_WORD));
 202         if (*word & mask)
 203             return false;
 204         *word |= mask;
 205         if (color != BLACK) {
 206             bit += color;
 207             word = &bitmap[bit / JS_BITS_PER_WORD];
 208             mask = (uintptr_t(1) << (bit % JS_BITS_PER_WORD));
 209             if (*word & mask)
 210                 return false;
 211             *word |= mask;
 212         }
 213         return true;
 214     }
 215
 216     JS_ALWAYS_INLINE void unmark(size_t bit, uint32 color) {
 217         bit += color;
 218         JS_ASSERT(bit < BitCount);
 219         uintptr_t *word = &bitmap[bit / JS_BITS_PER_WORD];
 220         *word &= ~(uintptr_t(1) << (bit % JS_BITS_PER_WORD));
 221     }
 222
 223 #ifdef DEBUG
 224     bool noBitsSet() {
 225         for (unsigned i = 0; i < BitWords; i++) {
 226             if (bitmap[i] != uintptr_t(0))
 227                 return false;
 228         }
 229         return true;
 230     }
 231 #endif
 232 };
 233
 234 /* Ensure that bitmap covers the whole arena. */
 235 JS_STATIC_ASSERT(Arena<FreeCell>::ArenaSize % Cell::CellSize == 0);
 236 JS_STATIC_ASSERT(ArenaBitmap::BitCount % JS_BITS_PER_WORD == 0);
 237
 238 /* Marking delay is used to resume marking later when recursive marking uses too much stack. */
 239 struct MarkingDelay {
 240     Arena<Cell> *link;
 241     uintptr_t   unmarkedChildren;
 242     jsuword     start;
 243
 244     void init()
 245     {
 246         link = NULL;
 247         unmarkedChildren = 0;
 248     }
 249 };
 250
 251 struct EmptyArenaLists {
 252     /* Arenas with no internal freelist prepared. */
 253     Arena<FreeCell> *cellFreeList;
 254
 255     /* Arenas with internal freelists prepared for a given finalize kind. */
 256     Arena<FreeCell> *freeLists[FINALIZE_LIMIT];
 257
 258     void init() {
 259         PodZero(this);
 260     }
 261
 262     Arena<FreeCell> *getOtherArena() {
 263         Arena<FreeCell> *arena = cellFreeList;
 264         if (arena) {
 265             cellFreeList = arena->header()->next;
 266             return arena;
 267         }
 268         for (int i = 0; i < FINALIZE_LIMIT; i++) {
 269             if ((arena = (Arena<FreeCell> *) freeLists[i])) {
 270                 freeLists[i] = freeLists[i]->header()->next;
 271                 return arena;
 272             }
 273         }
 274         JS_NOT_REACHED("No arena");
 275         return NULL;
 276     }
 277
 278     template <typename T>
 279     inline Arena<T> *getTypedFreeList(unsigned thingKind);
 280
 281     template <typename T>
 282     inline Arena<T> *getNext(JSCompartment *comp, unsigned thingKind);
 283
 284     template <typename T>
 285     inline void insert(Arena<T> *arena);
 286 };
 287
 288 template <typename T>
 289 inline Arena<T> *
 290 EmptyArenaLists::getTypedFreeList(unsigned thingKind) {
 291     JS_ASSERT(thingKind < FINALIZE_LIMIT);
 292     Arena<T> *arena = (Arena<T>*) freeLists[thingKind];
 293     if (arena) {
 294         freeLists[thingKind] = freeLists[thingKind]->header()->next;
 295         return arena;
 296     }
 297     return NULL;
 298 }
 299
 300 template<typename T>
 301 inline Arena<T> *
 302 EmptyArenaLists::getNext(JSCompartment *comp, unsigned thingKind) {
 303     Arena<T> *arena = getTypedFreeList<T>(thingKind);
 304     if (arena) {
 305         JS_ASSERT(arena->header()->isUsed == false);
 306         JS_ASSERT(arena->header()->thingSize == sizeof(T));
 307         arena->header()->isUsed = true;
 308         arena->header()->thingKind = thingKind;
 309         arena->header()->compartment = comp;
 310         return arena;
 311     }
 312     arena = (Arena<T> *)getOtherArena();
 313     JS_ASSERT(arena->header()->isUsed == false);
 314     arena->init(comp, thingKind);
 315     return arena;
 316 }
 317
 318 template <typename T>
 319 inline void
 320 EmptyArenaLists::insert(Arena<T> *arena) {
 321     unsigned thingKind = arena->header()->thingKind;
 322     JS_ASSERT(thingKind < FINALIZE_LIMIT);
 323     arena->header()->next = freeLists[thingKind];
 324     freeLists[thingKind] = (Arena<FreeCell> *) arena;
 325 }
 326
 327 /* The chunk header (located at the end of the chunk to preserve arena alignment). */
 328 struct ChunkInfo {
 329     Chunk           *link;
 330     JSRuntime       *runtime;
 331     EmptyArenaLists emptyArenaLists;
 332     size_t          age;
 333     size_t          numFree;
 334 };
 335
 336 /* Chunks contain arenas and associated data structures (mark bitmap, delayed marking state). */
 337 struct Chunk {
 338     static const size_t BytesPerArena = sizeof(Arena<FreeCell>) +
 339                                         sizeof(ArenaBitmap) +
 340                                         sizeof(MarkingDelay);
 341
 342     static const size_t ArenasPerChunk = (GC_CHUNK_SIZE - sizeof(ChunkInfo)) / BytesPerArena;
 343     static const size_t MaxAge = 3;
 344
 345     Arena<FreeCell> arenas[ArenasPerChunk];
 346     ArenaBitmap     bitmaps[ArenasPerChunk];
 347     MarkingDelay    markingDelay[ArenasPerChunk];
 348
 349     ChunkInfo       info;
 350
 351     void clearMarkBitmap();
 352     void init(JSRuntime *rt);
 353
 354     bool unused();
 355     bool hasAvailableArenas();
 356     bool withinArenasRange(Cell *cell);
 357
 358     template <typename T>
 359     Arena<T> *allocateArena(JSCompartment *comp, unsigned thingKind);
 360
 361     template <typename T>
 362     void releaseArena(Arena<T> *a);
 363
 364     JSRuntime *getRuntime();
 365     bool expire();
 366 };
 367 JS_STATIC_ASSERT(sizeof(Chunk) <= GC_CHUNK_SIZE);
 368 JS_STATIC_ASSERT(sizeof(Chunk) + Chunk::BytesPerArena > GC_CHUNK_SIZE);
 369
 370 Arena<Cell> *
 371 Cell::arena() const
 372 {
 373     uintptr_t addr = uintptr_t(this);
 374     JS_ASSERT(addr % sizeof(FreeCell) == 0);
 375     addr &= ~(Arena<FreeCell>::ArenaSize - 1);
 376     return reinterpret_cast<Arena<Cell> *>(addr);
 377 }
 378
 379 Chunk *
 380 Cell::chunk() const
 381 {
 382     uintptr_t addr = uintptr_t(this);
 383     JS_ASSERT(addr % sizeof(FreeCell) == 0);
 384     addr &= ~(GC_CHUNK_SIZE - 1);
 385     return reinterpret_cast<Chunk *>(addr);
 386 }
 387
 388 ArenaBitmap *
 389 Cell::bitmap() const
 390 {
 391     return &chunk()->bitmaps[arena()->arenaIndex()];
 392 }
 393
 394 STATIC_POSTCONDITION_ASSUME(return < ArenaBitmap::BitCount)
 395 size_t
 396 Cell::cellIndex() const
 397 {
 398     return reinterpret_cast<const FreeCell *>(this) - reinterpret_cast<FreeCell *>(&arena()->t);
 399 }
 400
 401 template <typename T>
 402 Chunk *
 403 Arena<T>::chunk() const
 404 {
 405     uintptr_t addr = uintptr_t(this);
 406     JS_ASSERT(addr % sizeof(FreeCell) == 0);
 407     addr &= ~(GC_CHUNK_SIZE - 1);
 408     return reinterpret_cast<Chunk *>(addr);
 409 }
 410
 411 template <typename T>
 412 size_t
 413 Arena<T>::arenaIndex() const
 414 {
 415     return reinterpret_cast<const Arena<FreeCell> *>(this) - chunk()->arenas;
 416 }
 417
 418 template <typename T>
 419 MarkingDelay *
 420 Arena<T>::getMarkingDelay() const
 421 {
 422     return &chunk()->markingDelay[arenaIndex()];
 423 }
 424
 425 template <typename T>
 426 ArenaBitmap *
 427 Arena<T>::bitmap() const
 428 {
 429     return &chunk()->bitmaps[arenaIndex()];
 430 }
 431
 432 template <typename T>
 433 inline T *
 434 Arena<T>::getAlignedThing(void *thing)
 435 {
 436     jsuword start = reinterpret_cast<jsuword>(&t.things[0]);
 437     jsuword offset = reinterpret_cast<jsuword>(thing) - start;
 438     offset -= offset % aheader.thingSize;
 439     return reinterpret_cast<T *>(start + offset);
 440 }
 441
 442 #ifdef DEBUG
 443 template <typename T>
 444 inline bool
 445 Arena<T>::assureThingIsAligned(void *thing)
 446 {
 447     return (getAlignedThing(thing) == thing);
 448 }
 449 #endif
 450
 451 static void
 452 AssertValidColor(const void *thing, uint32 color)
 453 {
 454     JS_ASSERT_IF(color, color < reinterpret_cast<const js::gc::FreeCell *>(thing)->arena()->header()->thingSize / sizeof(FreeCell));
 455 }
 456
 457 inline bool
 458 Cell::isMarked(uint32 color = BLACK) const
 459 {
 460     AssertValidColor(this, color);
 461     return bitmap()->isMarked(cellIndex(), color);
 462 }
 463
 464 bool
 465 Cell::markIfUnmarked(uint32 color = BLACK) const
 466 {
 467     AssertValidColor(this, color);
 468     return bitmap()->markIfUnmarked(cellIndex(), color);
 469 }
 470
 471 void
 472 Cell::unmark(uint32 color) const
 473 {
 474     JS_ASSERT(color != BLACK);
 475     AssertValidColor(this, color);
 476     bitmap()->unmark(cellIndex(), color);
 477 }
 478
 479 JSCompartment *
 480 Cell::compartment() const
 481 {
 482     return arena()->header()->compartment;
 483 }
 484
 485 template <typename T>
 486 static inline
 487 Arena<T> *
 488 GetArena(Cell *cell)
 489 {
 490     return reinterpret_cast<Arena<T> *>(cell->arena());
 491 }
 492
 493 #define JSTRACE_XML         2
 494
 495 /*
 496  * One past the maximum trace kind.
 497  */
 498 #define JSTRACE_LIMIT       3
 499
 500 /*
 501  * Lower limit after which we limit the heap growth
 502  */
 503 const size_t GC_ARENA_ALLOCATION_TRIGGER = 30 * js::GC_CHUNK_SIZE;
 504
 505 /*
 506  * A GC is triggered once the number of newly allocated arenas
 507  * is GC_HEAP_GROWTH_FACTOR times the number of live arenas after
 508  * the last GC starting after the lower limit of
 509  * GC_ARENA_ALLOCATION_TRIGGER.
 510  */
 511 const float GC_HEAP_GROWTH_FACTOR = 3.0f;
 512
 513 static inline size_t
 514 GetFinalizableTraceKind(size_t thingKind)
 515 {
 516     JS_STATIC_ASSERT(JSExternalString::TYPE_LIMIT == 8);
 517
 518     static const uint8 map[FINALIZE_LIMIT] = {
 519         JSTRACE_OBJECT,     /* FINALIZE_OBJECT0 */
 520         JSTRACE_OBJECT,     /* FINALIZE_OBJECT2 */
 521         JSTRACE_OBJECT,     /* FINALIZE_OBJECT4 */
 522         JSTRACE_OBJECT,     /* FINALIZE_OBJECT8 */
 523         JSTRACE_OBJECT,     /* FINALIZE_OBJECT12 */
 524         JSTRACE_OBJECT,     /* FINALIZE_OBJECT16 */
 525         JSTRACE_OBJECT,     /* FINALIZE_FUNCTION */
 526 #if JS_HAS_XML_SUPPORT      /* FINALIZE_XML */
 527         JSTRACE_XML,
 528 #endif
 529         JSTRACE_STRING,     /* FINALIZE_SHORT_STRING */
 530         JSTRACE_STRING,     /* FINALIZE_STRING */
 531         JSTRACE_STRING,     /* FINALIZE_EXTERNAL_STRING */
 532     };
 533
 534     JS_ASSERT(thingKind < FINALIZE_LIMIT);
 535     return map[thingKind];
 536 }
 537
 538 static inline bool
 539 IsFinalizableStringKind(unsigned thingKind)
 540 {
 541     return unsigned(FINALIZE_SHORT_STRING) <= thingKind &&
 542            thingKind <= unsigned(FINALIZE_EXTERNAL_STRING);
 543 }
 544
 545 /*
 546  * Get the type of the external string or -1 if the string was not created
 547  * with JS_NewExternalString.
 548  */
 549 static inline intN
 550 GetExternalStringGCType(JSExternalString *str)
 551 {
 552     JS_STATIC_ASSERT(FINALIZE_STRING + 1 == FINALIZE_EXTERNAL_STRING);
 553     JS_ASSERT(!JSString::isStatic(str));
 554
 555     unsigned thingKind = str->externalStringType;
 556     JS_ASSERT(IsFinalizableStringKind(thingKind));
 557     return intN(thingKind);
 558 }
 559
 560 static inline uint32
 561 GetGCThingTraceKind(void *thing)
 562 {
 563     JS_ASSERT(thing);
 564     if (JSString::isStatic(thing))
 565         return JSTRACE_STRING;
 566     Cell *cell = reinterpret_cast<Cell *>(thing);
 567     return GetFinalizableTraceKind(cell->arena()->header()->thingKind);
 568 }
 569
 570 static inline JSRuntime *
 571 GetGCThingRuntime(void *thing)
 572 {
 573     return reinterpret_cast<FreeCell *>(thing)->chunk()->info.runtime;
 574 }
 575
 576 #ifdef DEBUG
 577 extern bool
 578 checkArenaListsForThing(JSCompartment *comp, jsuword thing);
 579 #endif
 580
 581 /* The arenas in a list have uniform kind. */
 582 struct ArenaList {
 583     Arena<FreeCell>       *head;          /* list start */
 584     Arena<FreeCell>       *cursor;        /* arena with free things */
 585
 586     inline void init() {
 587         head = NULL;
 588         cursor = NULL;
 589     }
 590
 591     inline Arena<FreeCell> *getNextWithFreeList() {
 592         Arena<FreeCell> *a;
 593         while (cursor != NULL) {
 594             ArenaHeader *aheader = cursor->header();
 595             a = cursor;
 596             cursor = aheader->next;
 597             if (aheader->freeList)
 598                 return a;
 599         }
 600         return NULL;
 601     }
 602
 603 #ifdef DEBUG
 604     template <typename T>
 605     bool arenasContainThing(void *thing) {
 606         for (Arena<T> *a = (Arena<T> *) head; a; a = (Arena<T> *) a->header()->next) {
 607             JS_ASSERT(a->header()->isUsed);
 608             if (thing >= &a->t.things[0] && thing < &a->t.things[a->ThingsPerArena])
 609                 return true;
 610         }
 611         return false;
 612     }
 613
 614     bool markedThingsInArenaList() {
 615         for (Arena<FreeCell> *a = (Arena<FreeCell> *) head; a; a = (Arena<FreeCell> *) a->header()->next) {
 616             if (!a->bitmap()->noBitsSet())
 617                 return true;
 618         }
 619         return false;
 620     }
 621 #endif
 622
 623     inline void insert(Arena<FreeCell> *a) {
 624         a->header()->next = head;
 625         head = a;
 626     }
 627
 628     void releaseAll() {
 629         while (head) {
 630             Arena<FreeCell> *next = head->header()->next;
 631             head->chunk()->releaseArena(head);
 632             head = next;
 633         }
 634         head = NULL;
 635         cursor = NULL;
 636     }
 637
 638     inline bool isEmpty() const {
 639         return (head == NULL);
 640     }
 641 };
 642
 643 struct FreeLists {
 644     FreeCell       **finalizables[FINALIZE_LIMIT];
 645
 646     void purge();
 647
 648     inline FreeCell *getNext(uint32 kind) {
 649         FreeCell *top = NULL;
 650         if (finalizables[kind]) {
 651             top = *finalizables[kind];
 652             if (top) {
 653                 *finalizables[kind] = top->link;
 654             } else {
 655                 finalizables[kind] = NULL;
 656             }
 657 #ifdef DEBUG
 658             if (top && !top->link)
 659                 top->arena()->header()->hasFreeThings = false;
 660 #endif
 661         }
 662         return top;
 663     }
 664
 665     template <typename T>
 666     inline void populate(Arena<T> *a, uint32 thingKind) {
 667         finalizables[thingKind] = &a->header()->freeList;
 668     }
 669
 670 #ifdef DEBUG
 671     bool isEmpty() const {
 672         for (size_t i = 0; i != JS_ARRAY_LENGTH(finalizables); ++i) {
 673             if (finalizables[i])
 674                 return false;
 675         }
 676         return true;
 677     }
 678 #endif
 679 };
 680 }
 681
 682 typedef Vector<gc::Chunk *, 32, SystemAllocPolicy> GCChunks;
 683
 684 struct GCPtrHasher
 685 {
 686     typedef void *Lookup;
 687
 688     static HashNumber hash(void *key) {
 689         return HashNumber(uintptr_t(key) >> JS_GCTHING_ZEROBITS);
 690     }
 691
 692     static bool match(void *l, void *k) { return l == k; }
 693 };
 694
 695 typedef HashMap<void *, uint32, GCPtrHasher, SystemAllocPolicy> GCLocks;
 696
 697 struct RootInfo {
 698     RootInfo() {}
 699     RootInfo(const char *name, JSGCRootType type) : name(name), type(type) {}
 700     const char *name;
 701     JSGCRootType type;
 702 };
 703
 704 typedef js::HashMap<void *,
 705                     RootInfo,
 706                     js::DefaultHasher<void *>,
 707                     js::SystemAllocPolicy> RootedValueMap;
 708
 709 /* If HashNumber grows, need to change WrapperHasher. */
 710 JS_STATIC_ASSERT(sizeof(HashNumber) == 4);
 711
 712 struct WrapperHasher
 713 {
 714     typedef Value Lookup;
 715
 716     static HashNumber hash(Value key) {
 717         uint64 bits = JSVAL_BITS(Jsvalify(key));
 718         return (uint32)bits ^ (uint32)(bits >> 32);
 719     }
 720
 721     static bool match(const Value &l, const Value &k) { return l == k; }
 722 };
 723
 724 typedef HashMap<Value, Value, WrapperHasher, SystemAllocPolicy> WrapperMap;
 725
 726 class AutoValueVector;
 727 class AutoIdVector;
 728 }
 729
 730 static inline void
 731 CheckGCFreeListLink(js::gc::FreeCell *cell)
 732 {
 733     /*
 734      * The GC things on the free lists come from one arena and the things on
 735      * the free list are linked in ascending address order.
 736      */
 737     JS_ASSERT_IF(cell->link,
 738                  cell->arena() ==
 739                  cell->link->arena());
 740     JS_ASSERT_IF(cell->link, cell < cell->link);
 741 }
 742
 743 extern bool
 744 RefillFinalizableFreeList(JSContext *cx, unsigned thingKind);
 745
 746 #ifdef DEBUG
 747 extern bool
 748 CheckAllocation(JSContext *cx);
 749 #endif
 750
 751 /*
 752  * Get the type of the external string or -1 if the string was not created
 753  * with JS_NewExternalString.
 754  */
 755 extern intN
 756 js_GetExternalStringGCType(JSString *str);
 757
 758 extern JS_FRIEND_API(uint32)
 759 js_GetGCThingTraceKind(void *thing);
 760
 761 #if 1
 762 /*
 763  * Since we're forcing a GC from JS_GC anyway, don't bother wasting cycles
 764  * loading oldval.  XXX remove implied force, fix jsinterp.c's "second arg
 765  * ignored", etc.
 766  */
 767 #define GC_POKE(cx, oldval) ((cx)->runtime->gcPoke = JS_TRUE)
 768 #else
 769 #define GC_POKE(cx, oldval) ((cx)->runtime->gcPoke = JSVAL_IS_GCTHING(oldval))
 770 #endif
 771
 772 extern JSBool
 773 js_InitGC(JSRuntime *rt, uint32 maxbytes);
 774
 775 extern void
 776 js_FinishGC(JSRuntime *rt);
 777
 778 extern JSBool
 779 js_AddRoot(JSContext *cx, js::Value *vp, const char *name);
 780
 781 extern JSBool
 782 js_AddGCThingRoot(JSContext *cx, void **rp, const char *name);
 783
 784 #ifdef DEBUG
 785 extern void
 786 js_DumpNamedRoots(JSRuntime *rt,
 787                   void (*dump)(const char *name, void *rp, JSGCRootType type, void *data),
 788                   void *data);
 789 #endif
 790
 791 extern uint32
 792 js_MapGCRoots(JSRuntime *rt, JSGCRootMapFun map, void *data);
 793
 794 /* Table of pointers with count valid members. */
 795 typedef struct JSPtrTable {
 796     size_t      count;
 797     void        **array;
 798 } JSPtrTable;
 799
 800 extern JSBool
 801 js_RegisterCloseableIterator(JSContext *cx, JSObject *obj);
 802
 803 #ifdef JS_TRACER
 804 extern JSBool
 805 js_ReserveObjects(JSContext *cx, size_t nobjects);
 806 #endif
 807
 808 extern JSBool
 809 js_LockGCThingRT(JSRuntime *rt, void *thing);
 810
 811 extern void
 812 js_UnlockGCThingRT(JSRuntime *rt, void *thing);
 813
 814 extern JS_FRIEND_API(bool)
 815 IsAboutToBeFinalized(JSContext *cx, void *thing);
 816
 817 extern JS_FRIEND_API(bool)
 818 js_GCThingIsMarked(void *thing, uintN color);
 819
 820 extern void
 821 js_TraceStackFrame(JSTracer *trc, JSStackFrame *fp);
 822
 823 namespace js {
 824
 825 extern JS_REQUIRES_STACK void
 826 MarkRuntime(JSTracer *trc);
 827
 828 extern void
 829 TraceRuntime(JSTracer *trc);
 830
 831 extern JS_REQUIRES_STACK JS_FRIEND_API(void)
 832 MarkContext(JSTracer *trc, JSContext *acx);
 833
 834 /* Must be called with GC lock taken. */
 835 extern void
 836 TriggerGC(JSRuntime *rt);
 837
 838 /* Must be called with GC lock taken. */
 839 extern void
 840 TriggerCompartmentGC(JSCompartment *comp);
 841
 842 extern void
 843 MaybeGC(JSContext *cx);
 844
 845 } /* namespace js */
 846
 847 /*
 848  * Kinds of js_GC invocation.
 849  */
 850 typedef enum JSGCInvocationKind {
 851     /* Normal invocation. */
 852     GC_NORMAL           = 0,
 853
 854     /*
 855      * Called from js_DestroyContext for last JSContext in a JSRuntime, when
 856      * it is imperative that rt->gcPoke gets cleared early in js_GC.
 857      */
 858     GC_LAST_CONTEXT     = 1
 859 } JSGCInvocationKind;
 860
 861 /* Pass NULL for |comp| to get a full GC. */
 862 extern void
 863 js_GC(JSContext *cx, JSCompartment *comp, JSGCInvocationKind gckind);
 864
 865 #ifdef JS_THREADSAFE
 866 /*
 867  * This is a helper for code at can potentially run outside JS request to
 868  * ensure that the GC is not running when the function returns.
 869  *
 870  * This function must be called with the GC lock held.
 871  */
 872 extern void
 873 js_WaitForGC(JSRuntime *rt);
 874
 875 #else /* !JS_THREADSAFE */
 876
 877 # define js_WaitForGC(rt)    ((void) 0)
 878
 879 #endif
 880
 881 extern void
 882 js_DestroyScriptsToGC(JSContext *cx, JSCompartment *comp);
 883
 884 namespace js {
 885
 886 #ifdef JS_THREADSAFE
 887
 888 /*
 889  * During the finalization we do not free immediately. Rather we add the
 890  * corresponding pointers to a buffer which we later release on a separated
 891  * thread.
 892  *
 893  * The buffer is implemented as a vector of 64K arrays of pointers, not as a
 894  * simple vector, to avoid realloc calls during the vector growth and to not
 895  * bloat the binary size of the inlined freeLater method. Any OOM during
 896  * buffer growth results in the pointer being freed immediately.
 897  */
 898 class GCHelperThread {
 899     static const size_t FREE_ARRAY_SIZE = size_t(1) << 16;
 900     static const size_t FREE_ARRAY_LENGTH = FREE_ARRAY_SIZE / sizeof(void *);
 901
 902     PRThread*         thread;
 903     PRCondVar*        wakeup;
 904     PRCondVar*        sweepingDone;
 905     bool              shutdown;
 906     bool              sweeping;
 907
 908     Vector<void **, 16, js::SystemAllocPolicy> freeVector;
 909     void            **freeCursor;
 910     void            **freeCursorEnd;
 911
 912     JS_FRIEND_API(void)
 913     replenishAndFreeLater(void *ptr);
 914
 915     static void freeElementsAndArray(void **array, void **end) {
 916         JS_ASSERT(array <= end);
 917         for (void **p = array; p != end; ++p)
 918             js_free(*p);
 919         js_free(array);
 920     }
 921
 922     static void threadMain(void* arg);
 923
 924     void threadLoop(JSRuntime *rt);
 925     void doSweep();
 926
 927   public:
 928     GCHelperThread()
 929       : thread(NULL),
 930         wakeup(NULL),
 931         sweepingDone(NULL),
 932         shutdown(false),
 933         sweeping(false),
 934         freeCursor(NULL),
 935         freeCursorEnd(NULL) { }
 936
 937     bool init(JSRuntime *rt);
 938     void finish(JSRuntime *rt);
 939
 940     /* Must be called with GC lock taken. */
 941     void startBackgroundSweep(JSRuntime *rt);
 942
 943     /* Must be called outside the GC lock. */
 944     void waitBackgroundSweepEnd(JSRuntime *rt);
 945
 946     void freeLater(void *ptr) {
 947         JS_ASSERT(!sweeping);
 948         if (freeCursor != freeCursorEnd)
 949             *freeCursor++ = ptr;
 950         else
 951             replenishAndFreeLater(ptr);
 952     }
 953 };
 954
 955 #endif /* JS_THREADSAFE */
 956
 957 struct GCChunkHasher {
 958     typedef gc::Chunk *Lookup;
 959
 960     /*
 961      * Strip zeros for better distribution after multiplying by the golden
 962      * ratio.
 963      */
 964     static HashNumber hash(gc::Chunk *chunk) {
 965         JS_ASSERT(!(jsuword(chunk) & GC_CHUNK_MASK));
 966         return HashNumber(jsuword(chunk) >> GC_CHUNK_SHIFT);
 967     }
 968
 969     static bool match(gc::Chunk *k, gc::Chunk *l) {
 970         JS_ASSERT(!(jsuword(k) & GC_CHUNK_MASK));
 971         JS_ASSERT(!(jsuword(l) & GC_CHUNK_MASK));
 972         return k == l;
 973     }
 974 };
 975
 976 typedef HashSet<js::gc::Chunk *, GCChunkHasher, SystemAllocPolicy> GCChunkSet;
 977
 978 struct ConservativeGCThreadData {
 979
 980     /*
 981      * The GC scans conservatively between JSThreadData::nativeStackBase and
 982      * nativeStackTop unless the latter is NULL.
 983      */
 984     jsuword             *nativeStackTop;
 985
 986     union {
 987         jmp_buf         jmpbuf;
 988         jsuword         words[JS_HOWMANY(sizeof(jmp_buf), sizeof(jsuword))];
 989     } registerSnapshot;
 990
 991     /*
 992      * Cycle collector uses this to communicate that the native stack of the
 993      * GC thread should be scanned only if the thread have more than the given
 994      * threshold of requests.
 995      */
 996     unsigned requestThreshold;
 997
 998     JS_NEVER_INLINE void recordStackTop();
 999
1000 #ifdef JS_THREADSAFE
1001     void updateForRequestEnd(unsigned suspendCount) {
1002         if (suspendCount)
1003             recordStackTop();
1004         else
1005             nativeStackTop = NULL;
1006     }
1007 #endif
1008
1009     bool hasStackToScan() const {
1010         return !!nativeStackTop;
1011     }
1012 };
1013
1014 struct GCMarker : public JSTracer {
1015   private:
1016     /* The color is only applied to objects, functions and xml. */
1017     uint32 color;
1018   public:
1019     jsuword stackLimit;
1020     /* See comments before delayMarkingChildren is jsgc.cpp. */
1021     js::gc::Arena<js::gc::Cell> *unmarkedArenaStackTop;
1022 #ifdef DEBUG
1023     size_t              markLaterCount;
1024 #endif
1025
1026 #if defined(JS_DUMP_CONSERVATIVE_GC_ROOTS) || defined(JS_GCMETER)
1027     js::gc::ConservativeGCStats conservativeStats;
1028 #endif
1029
1030 #ifdef JS_DUMP_CONSERVATIVE_GC_ROOTS
1031     struct ConservativeRoot { void *thing; uint32 thingKind; };
1032     Vector<ConservativeRoot, 0, SystemAllocPolicy> conservativeRoots;
1033     const char *conservativeDumpFileName;
1034
1035     void dumpConservativeRoots();
1036 #endif
1037
1038   public:
1039     explicit GCMarker(JSContext *cx);
1040     ~GCMarker();
1041
1042     uint32 getMarkColor() const {
1043         return color;
1044     }
1045
1046     void setMarkColor(uint32 newColor) {
1047         /*
1048          * We must process any delayed marking here, otherwise we confuse
1049          * colors.
1050          */
1051         markDelayedChildren();
1052         color = newColor;
1053     }
1054
1055     void delayMarkingChildren(void *thing);
1056
1057     JS_FRIEND_API(void) markDelayedChildren();
1058 };
1059
1060 void
1061 MarkStackRangeConservatively(JSTracer *trc, Value *begin, Value *end);
1062
1063 } /* namespace js */
1064
1065 extern void
1066 js_FinalizeStringRT(JSRuntime *rt, JSString *str);
1067
1068 /*
1069  * This function is defined in jsdbgapi.cpp but is declared here to avoid
1070  * polluting jsdbgapi.h, a public API header, with internal functions.
1071  */
1072 extern void
1073 js_MarkTraps(JSTracer *trc);
1074
1075 namespace js {
1076 namespace gc {
1077
1078 /*
1079  * Macro to test if a traversal is the marking phase of GC to avoid exposing
1080  * ScriptFilenameEntry to traversal implementations.
1081  */
1082 #define IS_GC_MARKING_TRACER(trc) ((trc)->callback == NULL)
1083
1084 #if JS_HAS_XML_SUPPORT
1085 # define JS_IS_VALID_TRACE_KIND(kind) ((uint32)(kind) < JSTRACE_LIMIT)
1086 #else
1087 # define JS_IS_VALID_TRACE_KIND(kind) ((uint32)(kind) <= JSTRACE_STRING)
1088 #endif
1089
1090 /*
1091  * Set object's prototype while checking that doing so would not create
1092  * a cycle in the proto chain. The cycle check and proto change are done
1093  * only when all other requests are finished or suspended to ensure exclusive
1094  * access to the chain. If there is a cycle, return false without reporting
1095  * an error. Otherwise, set the proto and return true.
1096  */
1097 extern bool
1098 SetProtoCheckingForCycles(JSContext *cx, JSObject *obj, JSObject *proto);
1099
1100 JSCompartment *
1101 NewCompartment(JSContext *cx, JSPrincipals *principals);
1102
1103 } /* namespace js */
1104 } /* namespace gc */
1105
1106 inline JSCompartment *
1107 JSObject::getCompartment() const
1108 {
1109     return compartment();
1110 }
1111
1112 #ifdef JS_GC_UNDEFD_MOZALLOC_WRAPPERS
1113 #  include "mozilla/mozalloc_macro_wrappers.h"
1114 #endif
1115
1116 #endif /* jsgc_h___ */