diff options
Diffstat (limited to 'src/third_party/js-1.7/jsgc.c')
| -rw-r--r-- | src/third_party/js-1.7/jsgc.c | 3201 |
1 files changed, 3201 insertions, 0 deletions
diff --git a/src/third_party/js-1.7/jsgc.c b/src/third_party/js-1.7/jsgc.c new file mode 100644 index 00000000000..7fae096e0e8 --- /dev/null +++ b/src/third_party/js-1.7/jsgc.c @@ -0,0 +1,3201 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- + * vim: set ts=8 sw=4 et tw=78: + * + * ***** BEGIN LICENSE BLOCK ***** + * Version: MPL 1.1/GPL 2.0/LGPL 2.1 + * + * The contents of this file are subject to the Mozilla Public License Version + * 1.1 (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * Software distributed under the License is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License + * for the specific language governing rights and limitations under the + * License. + * + * The Original Code is Mozilla Communicator client code, released + * March 31, 1998. + * + * The Initial Developer of the Original Code is + * Netscape Communications Corporation. + * Portions created by the Initial Developer are Copyright (C) 1998 + * the Initial Developer. All Rights Reserved. + * + * Contributor(s): + * + * Alternatively, the contents of this file may be used under the terms of + * either of the GNU General Public License Version 2 or later (the "GPL"), + * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), + * in which case the provisions of the GPL or the LGPL are applicable instead + * of those above. If you wish to allow use of your version of this file only + * under the terms of either the GPL or the LGPL, and not to allow others to + * use your version of this file under the terms of the MPL, indicate your + * decision by deleting the provisions above and replace them with the notice + * and other provisions required by the GPL or the LGPL. If you do not delete + * the provisions above, a recipient may use your version of this file under + * the terms of any one of the MPL, the GPL or the LGPL. + * + * ***** END LICENSE BLOCK ***** */ + +/* + * JS Mark-and-Sweep Garbage Collector. + * + * This GC allocates fixed-sized things with sizes up to GC_NBYTES_MAX (see + * jsgc.h). It allocates from a special GC arena pool with each arena allocated + * using malloc. It uses an ideally parallel array of flag bytes to hold the + * mark bit, finalizer type index, etc. + * + * XXX swizzle page to freelist for better locality of reference + */ +#include "jsstddef.h" +#include <stdlib.h> /* for free */ +#include <string.h> /* for memset used when DEBUG */ +#include "jstypes.h" +#include "jsutil.h" /* Added by JSIFY */ +#include "jshash.h" /* Added by JSIFY */ +#include "jsapi.h" +#include "jsatom.h" +#include "jsbit.h" +#include "jsclist.h" +#include "jscntxt.h" +#include "jsconfig.h" +#include "jsdbgapi.h" +#include "jsexn.h" +#include "jsfun.h" +#include "jsgc.h" +#include "jsinterp.h" +#include "jsiter.h" +#include "jslock.h" +#include "jsnum.h" +#include "jsobj.h" +#include "jsscope.h" +#include "jsscript.h" +#include "jsstr.h" + +#if JS_HAS_XML_SUPPORT +#include "jsxml.h" +#endif + +/* + * GC arena sizing depends on amortizing arena overhead using a large number + * of things per arena, and on the thing/flags ratio of 8:1 on most platforms. + * + * On 64-bit platforms, we would have half as many things per arena because + * pointers are twice as big, so we double the bytes for things per arena. + * This preserves the 1024 byte flags sub-arena size, which relates to the + * GC_PAGE_SIZE (see below for why). + */ +#if JS_BYTES_PER_WORD == 8 +# define GC_THINGS_SHIFT 14 /* 16KB for things on Alpha, etc. */ +#else +# define GC_THINGS_SHIFT 13 /* 8KB for things on most platforms */ +#endif +#define GC_THINGS_SIZE JS_BIT(GC_THINGS_SHIFT) +#define GC_FLAGS_SIZE (GC_THINGS_SIZE / sizeof(JSGCThing)) + +/* + * A GC arena contains one flag byte for each thing in its heap, and supports + * O(1) lookup of a flag given its thing's address. + * + * To implement this, we take advantage of the thing/flags numerology: given + * the 8K bytes worth of GC-things, there are 1K flag bytes. Within each 9K + * allocation for things+flags there are always 8 consecutive 1K-pages each + * aligned on 1K boundary. We use these pages to allocate things and the + * remaining 1K of space before and after the aligned pages to store flags. + * If we are really lucky and things+flags starts on a 1K boundary, then + * flags would consist of a single 1K chunk that comes after 8K of things. + * Otherwise there are 2 chunks of flags, one before and one after things. + * + * To be able to find the flag byte for a particular thing, we put a + * JSGCPageInfo record at the beginning of each 1K-aligned page to hold that + * page's offset from the beginning of things+flags allocation and we allocate + * things after this record. Thus for each thing |thing_address & ~1023| + * gives the address of a JSGCPageInfo record from which we read page_offset. + * Due to page alignment + * (page_offset & ~1023) + (thing_address & 1023) + * gives thing_offset from the beginning of 8K paged things. We then divide + * thing_offset by sizeof(JSGCThing) to get thing_index. + * + * Now |page_address - page_offset| is things+flags arena_address and + * (page_offset & 1023) is the offset of the first page from the start of + * things+flags area. Thus if + * thing_index < (page_offset & 1023) + * then + * allocation_start_address + thing_index < address_of_the_first_page + * and we use + * allocation_start_address + thing_index + * as the address to store thing's flags. If + * thing_index >= (page_offset & 1023), + * then we use the chunk of flags that comes after the pages with things + * and calculate the address for the flag byte as + * address_of_the_first_page + 8K + (thing_index - (page_offset & 1023)) + * which is just + * allocation_start_address + thing_index + 8K. + * + * When we allocate things with size equal to sizeof(JSGCThing), the overhead + * of this scheme for 32 bit platforms is (8+8*(8+1))/(8+9K) or 0.87% + * (assuming 4 bytes for each JSGCArena header, and 8 bytes for each + * JSGCThing and JSGCPageInfo). When thing_size > 8, the scheme wastes the + * flag byte for each extra 8 bytes beyond sizeof(JSGCThing) in thing_size + * and the overhead is close to 1/8 or 12.5%. + * FIXME: How can we avoid this overhead? + * + * Here's some ASCII art showing an arena: + * + * split or the first 1-K aligned address. + * | + * V + * +--+-------+-------+-------+-------+-------+-------+-------+-------+-----+ + * |fB| tp0 | tp1 | tp2 | tp3 | tp4 | tp5 | tp6 | tp7 | fA | + * +--+-------+-------+-------+-------+-------+-------+-------+-------+-----+ + * ^ ^ + * tI ---------+ | + * tJ -------------------------------------------+ + * + * - fB are the "before split" flags, fA are the "after split" flags + * - tp0-tp7 are the 8 thing pages + * - thing tI points into tp1, whose flags are below the split, in fB + * - thing tJ points into tp5, clearly above the split + * + * In general, one of the thing pages will have some of its things' flags on + * the low side of the split, and the rest of its things' flags on the high + * side. All the other pages have flags only below or only above. + * + * (If we need to implement card-marking for an incremental GC write barrier, + * we can replace word-sized offsetInArena in JSGCPageInfo by pair of + * uint8 card_mark and uint16 offsetInArena fields as the offset can not exceed + * GC_THINGS_SIZE. This would gives an extremely efficient write barrier: + * when mutating an object obj, just store a 1 byte at + * (uint8 *) ((jsuword)obj & ~1023) on 32-bit platforms.) + */ +#define GC_PAGE_SHIFT 10 +#define GC_PAGE_MASK ((jsuword) JS_BITMASK(GC_PAGE_SHIFT)) +#define GC_PAGE_SIZE JS_BIT(GC_PAGE_SHIFT) +#define GC_PAGE_COUNT (1 << (GC_THINGS_SHIFT - GC_PAGE_SHIFT)) + +typedef struct JSGCPageInfo { + jsuword offsetInArena; /* offset from the arena start */ + jsuword unscannedBitmap; /* bitset for fast search of marked + but not yet scanned GC things */ +} JSGCPageInfo; + +struct JSGCArena { + JSGCArenaList *list; /* allocation list for the arena */ + JSGCArena *prev; /* link field for allocation list */ + JSGCArena *prevUnscanned; /* link field for the list of arenas + with marked but not yet scanned + things */ + jsuword unscannedPages; /* bitset for fast search of pages + with marked but not yet scanned + things */ + uint8 base[1]; /* things+flags allocation area */ +}; + +#define GC_ARENA_SIZE \ + (offsetof(JSGCArena, base) + GC_THINGS_SIZE + GC_FLAGS_SIZE) + +#define FIRST_THING_PAGE(a) \ + (((jsuword)(a)->base + GC_FLAGS_SIZE - 1) & ~GC_PAGE_MASK) + +#define PAGE_TO_ARENA(pi) \ + ((JSGCArena *)((jsuword)(pi) - (pi)->offsetInArena \ + - offsetof(JSGCArena, base))) + +#define PAGE_INDEX(pi) \ + ((size_t)((pi)->offsetInArena >> GC_PAGE_SHIFT)) + +#define THING_TO_PAGE(thing) \ + ((JSGCPageInfo *)((jsuword)(thing) & ~GC_PAGE_MASK)) + +/* + * Given a thing size n, return the size of the gap from the page start before + * the first thing. We know that any n not a power of two packs from + * the end of the page leaving at least enough room for one JSGCPageInfo, but + * not for another thing, at the front of the page (JS_ASSERTs below insist + * on this). + * + * This works because all allocations are a multiple of sizeof(JSGCThing) == + * sizeof(JSGCPageInfo) in size. + */ +#define PAGE_THING_GAP(n) (((n) & ((n) - 1)) ? (GC_PAGE_SIZE % (n)) : (n)) + +#ifdef JS_THREADSAFE +/* + * The maximum number of things to put to the local free list by taking + * several things from the global free list or from the tail of the last + * allocated arena to amortize the cost of rt->gcLock. + * + * We use number 8 based on benchmarks from bug 312238. + */ +#define MAX_THREAD_LOCAL_THINGS 8 + +#endif + +JS_STATIC_ASSERT(sizeof(JSGCThing) == sizeof(JSGCPageInfo)); +JS_STATIC_ASSERT(sizeof(JSGCThing) >= sizeof(JSObject)); +JS_STATIC_ASSERT(sizeof(JSGCThing) >= sizeof(JSString)); +JS_STATIC_ASSERT(sizeof(JSGCThing) >= sizeof(jsdouble)); +JS_STATIC_ASSERT(GC_FLAGS_SIZE >= GC_PAGE_SIZE); +JS_STATIC_ASSERT(sizeof(JSStackHeader) >= 2 * sizeof(jsval)); + +/* + * JSPtrTable capacity growth descriptor. The table grows by powers of two + * starting from capacity JSPtrTableInfo.minCapacity, but switching to linear + * growth when capacity reaches JSPtrTableInfo.linearGrowthThreshold. + */ +typedef struct JSPtrTableInfo { + uint16 minCapacity; + uint16 linearGrowthThreshold; +} JSPtrTableInfo; + +#define GC_ITERATOR_TABLE_MIN 4 +#define GC_ITERATOR_TABLE_LINEAR 1024 + +static const JSPtrTableInfo iteratorTableInfo = { + GC_ITERATOR_TABLE_MIN, + GC_ITERATOR_TABLE_LINEAR +}; + +/* Calculate table capacity based on the current value of JSPtrTable.count. */ +static size_t +PtrTableCapacity(size_t count, const JSPtrTableInfo *info) +{ + size_t linear, log, capacity; + + linear = info->linearGrowthThreshold; + JS_ASSERT(info->minCapacity <= linear); + + if (count == 0) { + capacity = 0; + } else if (count < linear) { + log = JS_CEILING_LOG2W(count); + JS_ASSERT(log != JS_BITS_PER_WORD); + capacity = (size_t)1 << log; + if (capacity < info->minCapacity) + capacity = info->minCapacity; + } else { + capacity = JS_ROUNDUP(count, linear); + } + + JS_ASSERT(capacity >= count); + return capacity; +} + +static void +FreePtrTable(JSPtrTable *table, const JSPtrTableInfo *info) +{ + if (table->array) { + JS_ASSERT(table->count > 0); + free(table->array); + table->array = NULL; + table->count = 0; + } + JS_ASSERT(table->count == 0); +} + +static JSBool +AddToPtrTable(JSContext *cx, JSPtrTable *table, const JSPtrTableInfo *info, + void *ptr) +{ + size_t count, capacity; + void **array; + + count = table->count; + capacity = PtrTableCapacity(count, info); + + if (count == capacity) { + if (capacity < info->minCapacity) { + JS_ASSERT(capacity == 0); + JS_ASSERT(!table->array); + capacity = info->minCapacity; + } else { + /* + * Simplify the overflow detection assuming pointer is bigger + * than byte. + */ + JS_STATIC_ASSERT(2 <= sizeof table->array[0]); + capacity = (capacity < info->linearGrowthThreshold) + ? 2 * capacity + : capacity + info->linearGrowthThreshold; + if (capacity > (size_t)-1 / sizeof table->array[0]) + goto bad; + } + array = (void **) realloc(table->array, + capacity * sizeof table->array[0]); + if (!array) + goto bad; +#ifdef DEBUG + memset(array + count, JS_FREE_PATTERN, + (capacity - count) * sizeof table->array[0]); +#endif + table->array = array; + } + + table->array[count] = ptr; + table->count = count + 1; + + return JS_TRUE; + + bad: + JS_ReportOutOfMemory(cx); + return JS_FALSE; +} + +static void +ShrinkPtrTable(JSPtrTable *table, const JSPtrTableInfo *info, + size_t newCount) +{ + size_t oldCapacity, capacity; + void **array; + + JS_ASSERT(newCount <= table->count); + if (newCount == table->count) + return; + + oldCapacity = PtrTableCapacity(table->count, info); + table->count = newCount; + capacity = PtrTableCapacity(newCount, info); + + if (oldCapacity != capacity) { + array = table->array; + JS_ASSERT(array); + if (capacity == 0) { + free(array); + table->array = NULL; + return; + } + array = (void **) realloc(array, capacity * sizeof array[0]); + if (array) + table->array = array; + } +#ifdef DEBUG + memset(table->array + newCount, JS_FREE_PATTERN, + (capacity - newCount) * sizeof table->array[0]); +#endif +} + +#ifdef JS_GCMETER +# define METER(x) x +#else +# define METER(x) ((void) 0) +#endif + +static JSBool +NewGCArena(JSRuntime *rt, JSGCArenaList *arenaList) +{ + JSGCArena *a; + jsuword offset; + JSGCPageInfo *pi; + uint32 *bytesptr; + + /* Check if we are allowed and can allocate a new arena. */ + if (rt->gcBytes >= rt->gcMaxBytes) + return JS_FALSE; + a = (JSGCArena *)malloc(GC_ARENA_SIZE); + if (!a) + return JS_FALSE; + + /* Initialize the JSGCPageInfo records at the start of every thing page. */ + offset = (GC_PAGE_SIZE - ((jsuword)a->base & GC_PAGE_MASK)) & GC_PAGE_MASK; + JS_ASSERT((jsuword)a->base + offset == FIRST_THING_PAGE(a)); + do { + pi = (JSGCPageInfo *) (a->base + offset); + pi->offsetInArena = offset; + pi->unscannedBitmap = 0; + offset += GC_PAGE_SIZE; + } while (offset < GC_THINGS_SIZE); + + METER(++arenaList->stats.narenas); + METER(arenaList->stats.maxarenas + = JS_MAX(arenaList->stats.maxarenas, arenaList->stats.narenas)); + + a->list = arenaList; + a->prev = arenaList->last; + a->prevUnscanned = NULL; + a->unscannedPages = 0; + arenaList->last = a; + arenaList->lastLimit = 0; + + bytesptr = (arenaList == &rt->gcArenaList[0]) + ? &rt->gcBytes + : &rt->gcPrivateBytes; + *bytesptr += GC_ARENA_SIZE; + + return JS_TRUE; +} + +static void +DestroyGCArena(JSRuntime *rt, JSGCArenaList *arenaList, JSGCArena **ap) +{ + JSGCArena *a; + uint32 *bytesptr; + + a = *ap; + JS_ASSERT(a); + bytesptr = (arenaList == &rt->gcArenaList[0]) + ? &rt->gcBytes + : &rt->gcPrivateBytes; + JS_ASSERT(*bytesptr >= GC_ARENA_SIZE); + *bytesptr -= GC_ARENA_SIZE; + METER(rt->gcStats.afree++); + METER(--arenaList->stats.narenas); + if (a == arenaList->last) + arenaList->lastLimit = (uint16)(a->prev ? GC_THINGS_SIZE : 0); + *ap = a->prev; + +#ifdef DEBUG + memset(a, JS_FREE_PATTERN, GC_ARENA_SIZE); +#endif + free(a); +} + +static void +InitGCArenaLists(JSRuntime *rt) +{ + uintN i, thingSize; + JSGCArenaList *arenaList; + + for (i = 0; i < GC_NUM_FREELISTS; i++) { + arenaList = &rt->gcArenaList[i]; + thingSize = GC_FREELIST_NBYTES(i); + JS_ASSERT((size_t)(uint16)thingSize == thingSize); + arenaList->last = NULL; + arenaList->lastLimit = 0; + arenaList->thingSize = (uint16)thingSize; + arenaList->freeList = NULL; + METER(memset(&arenaList->stats, 0, sizeof arenaList->stats)); + } +} + +static void +FinishGCArenaLists(JSRuntime *rt) +{ + uintN i; + JSGCArenaList *arenaList; + + for (i = 0; i < GC_NUM_FREELISTS; i++) { + arenaList = &rt->gcArenaList[i]; + while (arenaList->last) + DestroyGCArena(rt, arenaList, &arenaList->last); + arenaList->freeList = NULL; + } +} + +uint8 * +js_GetGCThingFlags(void *thing) +{ + JSGCPageInfo *pi; + jsuword offsetInArena, thingIndex; + + pi = THING_TO_PAGE(thing); + offsetInArena = pi->offsetInArena; + JS_ASSERT(offsetInArena < GC_THINGS_SIZE); + thingIndex = ((offsetInArena & ~GC_PAGE_MASK) | + ((jsuword)thing & GC_PAGE_MASK)) / sizeof(JSGCThing); + JS_ASSERT(thingIndex < GC_PAGE_SIZE); + if (thingIndex >= (offsetInArena & GC_PAGE_MASK)) + thingIndex += GC_THINGS_SIZE; + return (uint8 *)pi - offsetInArena + thingIndex; +} + +JSRuntime* +js_GetGCStringRuntime(JSString *str) +{ + JSGCPageInfo *pi; + JSGCArenaList *list; + + pi = THING_TO_PAGE(str); + list = PAGE_TO_ARENA(pi)->list; + + JS_ASSERT(list->thingSize == sizeof(JSGCThing)); + JS_ASSERT(GC_FREELIST_INDEX(sizeof(JSGCThing)) == 0); + + return (JSRuntime *)((uint8 *)list - offsetof(JSRuntime, gcArenaList)); +} + +JSBool +js_IsAboutToBeFinalized(JSContext *cx, void *thing) +{ + uint8 flags = *js_GetGCThingFlags(thing); + + return !(flags & (GCF_MARK | GCF_LOCK | GCF_FINAL)); +} + +typedef void (*GCFinalizeOp)(JSContext *cx, JSGCThing *thing); + +#ifndef DEBUG +# define js_FinalizeDouble NULL +#endif + +#if !JS_HAS_XML_SUPPORT +# define js_FinalizeXMLNamespace NULL +# define js_FinalizeXMLQName NULL +# define js_FinalizeXML NULL +#endif + +static GCFinalizeOp gc_finalizers[GCX_NTYPES] = { + (GCFinalizeOp) js_FinalizeObject, /* GCX_OBJECT */ + (GCFinalizeOp) js_FinalizeString, /* GCX_STRING */ + (GCFinalizeOp) js_FinalizeDouble, /* GCX_DOUBLE */ + (GCFinalizeOp) js_FinalizeString, /* GCX_MUTABLE_STRING */ + NULL, /* GCX_PRIVATE */ + (GCFinalizeOp) js_FinalizeXMLNamespace, /* GCX_NAMESPACE */ + (GCFinalizeOp) js_FinalizeXMLQName, /* GCX_QNAME */ + (GCFinalizeOp) js_FinalizeXML, /* GCX_XML */ + NULL, /* GCX_EXTERNAL_STRING */ + NULL, + NULL, + NULL, + NULL, + NULL, + NULL, + NULL +}; + +#ifdef GC_MARK_DEBUG +static const char newborn_external_string[] = "newborn external string"; + +static const char *gc_typenames[GCX_NTYPES] = { + "newborn object", + "newborn string", + "newborn double", + "newborn mutable string", + "newborn private", + "newborn Namespace", + "newborn QName", + "newborn XML", + newborn_external_string, + newborn_external_string, + newborn_external_string, + newborn_external_string, + newborn_external_string, + newborn_external_string, + newborn_external_string, + newborn_external_string +}; +#endif + +intN +js_ChangeExternalStringFinalizer(JSStringFinalizeOp oldop, + JSStringFinalizeOp newop) +{ + uintN i; + + for (i = GCX_EXTERNAL_STRING; i < GCX_NTYPES; i++) { + if (gc_finalizers[i] == (GCFinalizeOp) oldop) { + gc_finalizers[i] = (GCFinalizeOp) newop; + return (intN) i; + } + } + return -1; +} + +/* This is compatible with JSDHashEntryStub. */ +typedef struct JSGCRootHashEntry { + JSDHashEntryHdr hdr; + void *root; + const char *name; +} JSGCRootHashEntry; + +/* Initial size of the gcRootsHash table (SWAG, small enough to amortize). */ +#define GC_ROOTS_SIZE 256 +#define GC_FINALIZE_LEN 1024 + +JSBool +js_InitGC(JSRuntime *rt, uint32 maxbytes) +{ + InitGCArenaLists(rt); + if (!JS_DHashTableInit(&rt->gcRootsHash, JS_DHashGetStubOps(), NULL, + sizeof(JSGCRootHashEntry), GC_ROOTS_SIZE)) { + rt->gcRootsHash.ops = NULL; + return JS_FALSE; + } + rt->gcLocksHash = NULL; /* create lazily */ + + /* + * Separate gcMaxMallocBytes from gcMaxBytes but initialize to maxbytes + * for default backward API compatibility. + */ + rt->gcMaxBytes = rt->gcMaxMallocBytes = maxbytes; + + return JS_TRUE; +} + +#ifdef JS_GCMETER +JS_FRIEND_API(void) +js_DumpGCStats(JSRuntime *rt, FILE *fp) +{ + uintN i; + size_t totalThings, totalMaxThings, totalBytes; + + fprintf(fp, "\nGC allocation statistics:\n"); + +#define UL(x) ((unsigned long)(x)) +#define ULSTAT(x) UL(rt->gcStats.x) + totalThings = 0; + totalMaxThings = 0; + totalBytes = 0; + for (i = 0; i < GC_NUM_FREELISTS; i++) { + JSGCArenaList *list = &rt->gcArenaList[i]; + JSGCArenaStats *stats = &list->stats; + if (stats->maxarenas == 0) { + fprintf(fp, "ARENA LIST %u (thing size %lu): NEVER USED\n", + i, UL(GC_FREELIST_NBYTES(i))); + continue; + } + fprintf(fp, "ARENA LIST %u (thing size %lu):\n", + i, UL(GC_FREELIST_NBYTES(i))); + fprintf(fp, " arenas: %lu\n", UL(stats->narenas)); + fprintf(fp, " max arenas: %lu\n", UL(stats->maxarenas)); + fprintf(fp, " things: %lu\n", UL(stats->nthings)); + fprintf(fp, " max things: %lu\n", UL(stats->maxthings)); + fprintf(fp, " free list: %lu\n", UL(stats->freelen)); + fprintf(fp, " free list density: %.1f%%\n", + stats->narenas == 0 + ? 0.0 + : (100.0 * list->thingSize * (jsdouble)stats->freelen / + (GC_THINGS_SIZE * (jsdouble)stats->narenas))); + fprintf(fp, " average free list density: %.1f%%\n", + stats->totalarenas == 0 + ? 0.0 + : (100.0 * list->thingSize * (jsdouble)stats->totalfreelen / + (GC_THINGS_SIZE * (jsdouble)stats->totalarenas))); + fprintf(fp, " recycles: %lu\n", UL(stats->recycle)); + fprintf(fp, " recycle/alloc ratio: %.2f\n", + (jsdouble)stats->recycle / + (jsdouble)(stats->totalnew - stats->recycle)); + totalThings += stats->nthings; + totalMaxThings += stats->maxthings; + totalBytes += GC_FREELIST_NBYTES(i) * stats->nthings; + } + fprintf(fp, "TOTAL STATS:\n"); + fprintf(fp, " public bytes allocated: %lu\n", UL(rt->gcBytes)); + fprintf(fp, " private bytes allocated: %lu\n", UL(rt->gcPrivateBytes)); + fprintf(fp, " alloc attempts: %lu\n", ULSTAT(alloc)); +#ifdef JS_THREADSAFE + fprintf(fp, " alloc without locks: %1u\n", ULSTAT(localalloc)); +#endif + fprintf(fp, " total GC things: %lu\n", UL(totalThings)); + fprintf(fp, " max total GC things: %lu\n", UL(totalMaxThings)); + fprintf(fp, " GC things size: %lu\n", UL(totalBytes)); + fprintf(fp, "allocation retries after GC: %lu\n", ULSTAT(retry)); + fprintf(fp, " allocation failures: %lu\n", ULSTAT(fail)); + fprintf(fp, " things born locked: %lu\n", ULSTAT(lockborn)); + fprintf(fp, " valid lock calls: %lu\n", ULSTAT(lock)); + fprintf(fp, " valid unlock calls: %lu\n", ULSTAT(unlock)); + fprintf(fp, " mark recursion depth: %lu\n", ULSTAT(depth)); + fprintf(fp, " maximum mark recursion: %lu\n", ULSTAT(maxdepth)); + fprintf(fp, " mark C recursion depth: %lu\n", ULSTAT(cdepth)); + fprintf(fp, " maximum mark C recursion: %lu\n", ULSTAT(maxcdepth)); + fprintf(fp, " delayed scan bag adds: %lu\n", ULSTAT(unscanned)); +#ifdef DEBUG + fprintf(fp, " max delayed scan bag size: %lu\n", ULSTAT(maxunscanned)); +#endif + fprintf(fp, " maximum GC nesting level: %lu\n", ULSTAT(maxlevel)); + fprintf(fp, "potentially useful GC calls: %lu\n", ULSTAT(poke)); + fprintf(fp, " useless GC calls: %lu\n", ULSTAT(nopoke)); + fprintf(fp, " thing arenas freed so far: %lu\n", ULSTAT(afree)); + fprintf(fp, " stack segments scanned: %lu\n", ULSTAT(stackseg)); + fprintf(fp, "stack segment slots scanned: %lu\n", ULSTAT(segslots)); + fprintf(fp, "reachable closeable objects: %lu\n", ULSTAT(nclose)); + fprintf(fp, " max reachable closeable: %lu\n", ULSTAT(maxnclose)); + fprintf(fp, " scheduled close hooks: %lu\n", ULSTAT(closelater)); + fprintf(fp, " max scheduled close hooks: %lu\n", ULSTAT(maxcloselater)); +#undef UL +#undef US + +#ifdef JS_ARENAMETER + JS_DumpArenaStats(fp); +#endif +} +#endif + +#ifdef DEBUG +static void +CheckLeakedRoots(JSRuntime *rt); +#endif + +void +js_FinishGC(JSRuntime *rt) +{ +#ifdef JS_ARENAMETER + JS_DumpArenaStats(stdout); +#endif +#ifdef JS_GCMETER + js_DumpGCStats(rt, stdout); +#endif + + FreePtrTable(&rt->gcIteratorTable, &iteratorTableInfo); +#if JS_HAS_GENERATORS + rt->gcCloseState.reachableList = NULL; + METER(rt->gcStats.nclose = 0); + rt->gcCloseState.todoQueue = NULL; +#endif + FinishGCArenaLists(rt); + + if (rt->gcRootsHash.ops) { +#ifdef DEBUG + CheckLeakedRoots(rt); +#endif + JS_DHashTableFinish(&rt->gcRootsHash); + rt->gcRootsHash.ops = NULL; + } + if (rt->gcLocksHash) { + JS_DHashTableDestroy(rt->gcLocksHash); + rt->gcLocksHash = NULL; + } +} + +JSBool +js_AddRoot(JSContext *cx, void *rp, const char *name) +{ + JSBool ok = js_AddRootRT(cx->runtime, rp, name); + if (!ok) + JS_ReportOutOfMemory(cx); + return ok; +} + +JSBool +js_AddRootRT(JSRuntime *rt, void *rp, const char *name) +{ + JSBool ok; + JSGCRootHashEntry *rhe; + + /* + * Due to the long-standing, but now removed, use of rt->gcLock across the + * bulk of js_GC, API users have come to depend on JS_AddRoot etc. locking + * properly with a racing GC, without calling JS_AddRoot from a request. + * We have to preserve API compatibility here, now that we avoid holding + * rt->gcLock across the mark phase (including the root hashtable mark). + * + * If the GC is running and we're called on another thread, wait for this + * GC activation to finish. We can safely wait here (in the case where we + * are called within a request on another thread's context) without fear + * of deadlock because the GC doesn't set rt->gcRunning until after it has + * waited for all active requests to end. + */ + JS_LOCK_GC(rt); +#ifdef JS_THREADSAFE + JS_ASSERT(!rt->gcRunning || rt->gcLevel > 0); + if (rt->gcRunning && rt->gcThread->id != js_CurrentThreadId()) { + do { + JS_AWAIT_GC_DONE(rt); + } while (rt->gcLevel > 0); + } +#endif + rhe = (JSGCRootHashEntry *) JS_DHashTableOperate(&rt->gcRootsHash, rp, + JS_DHASH_ADD); + if (rhe) { + rhe->root = rp; + rhe->name = name; + ok = JS_TRUE; + } else { + ok = JS_FALSE; + } + JS_UNLOCK_GC(rt); + return ok; +} + +JSBool +js_RemoveRoot(JSRuntime *rt, void *rp) +{ + /* + * Due to the JS_RemoveRootRT API, we may be called outside of a request. + * Same synchronization drill as above in js_AddRoot. + */ + JS_LOCK_GC(rt); +#ifdef JS_THREADSAFE + JS_ASSERT(!rt->gcRunning || rt->gcLevel > 0); + if (rt->gcRunning && rt->gcThread->id != js_CurrentThreadId()) { + do { + JS_AWAIT_GC_DONE(rt); + } while (rt->gcLevel > 0); + } +#endif + (void) JS_DHashTableOperate(&rt->gcRootsHash, rp, JS_DHASH_REMOVE); + rt->gcPoke = JS_TRUE; + JS_UNLOCK_GC(rt); + return JS_TRUE; +} + +#ifdef DEBUG + +JS_STATIC_DLL_CALLBACK(JSDHashOperator) +js_root_printer(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 i, void *arg) +{ + uint32 *leakedroots = (uint32 *)arg; + JSGCRootHashEntry *rhe = (JSGCRootHashEntry *)hdr; + + (*leakedroots)++; + fprintf(stderr, + "JS engine warning: leaking GC root \'%s\' at %p\n", + rhe->name ? (char *)rhe->name : "", rhe->root); + + return JS_DHASH_NEXT; +} + +static void +CheckLeakedRoots(JSRuntime *rt) +{ + uint32 leakedroots = 0; + + /* Warn (but don't assert) debug builds of any remaining roots. */ + JS_DHashTableEnumerate(&rt->gcRootsHash, js_root_printer, + &leakedroots); + if (leakedroots > 0) { + if (leakedroots == 1) { + fprintf(stderr, +"JS engine warning: 1 GC root remains after destroying the JSRuntime.\n" +" This root may point to freed memory. Objects reachable\n" +" through it have not been finalized.\n"); + } else { + fprintf(stderr, +"JS engine warning: %lu GC roots remain after destroying the JSRuntime.\n" +" These roots may point to freed memory. Objects reachable\n" +" through them have not been finalized.\n", + (unsigned long) leakedroots); + } + } +} + +typedef struct NamedRootDumpArgs { + void (*dump)(const char *name, void *rp, void *data); + void *data; +} NamedRootDumpArgs; + +JS_STATIC_DLL_CALLBACK(JSDHashOperator) +js_named_root_dumper(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number, + void *arg) +{ + NamedRootDumpArgs *args = (NamedRootDumpArgs *) arg; + JSGCRootHashEntry *rhe = (JSGCRootHashEntry *)hdr; + + if (rhe->name) + args->dump(rhe->name, rhe->root, args->data); + return JS_DHASH_NEXT; +} + +void +js_DumpNamedRoots(JSRuntime *rt, + void (*dump)(const char *name, void *rp, void *data), + void *data) +{ + NamedRootDumpArgs args; + + args.dump = dump; + args.data = data; + JS_DHashTableEnumerate(&rt->gcRootsHash, js_named_root_dumper, &args); +} + +#endif /* DEBUG */ + +typedef struct GCRootMapArgs { + JSGCRootMapFun map; + void *data; +} GCRootMapArgs; + +JS_STATIC_DLL_CALLBACK(JSDHashOperator) +js_gcroot_mapper(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number, + void *arg) +{ + GCRootMapArgs *args = (GCRootMapArgs *) arg; + JSGCRootHashEntry *rhe = (JSGCRootHashEntry *)hdr; + intN mapflags; + JSDHashOperator op; + + mapflags = args->map(rhe->root, rhe->name, args->data); + +#if JS_MAP_GCROOT_NEXT == JS_DHASH_NEXT && \ + JS_MAP_GCROOT_STOP == JS_DHASH_STOP && \ + JS_MAP_GCROOT_REMOVE == JS_DHASH_REMOVE + op = (JSDHashOperator)mapflags; +#else + op = JS_DHASH_NEXT; + if (mapflags & JS_MAP_GCROOT_STOP) + op |= JS_DHASH_STOP; + if (mapflags & JS_MAP_GCROOT_REMOVE) + op |= JS_DHASH_REMOVE; +#endif + + return op; +} + +uint32 +js_MapGCRoots(JSRuntime *rt, JSGCRootMapFun map, void *data) +{ + GCRootMapArgs args; + uint32 rv; + + args.map = map; + args.data = data; + JS_LOCK_GC(rt); + rv = JS_DHashTableEnumerate(&rt->gcRootsHash, js_gcroot_mapper, &args); + JS_UNLOCK_GC(rt); + return rv; +} + +JSBool +js_RegisterCloseableIterator(JSContext *cx, JSObject *obj) +{ + JSRuntime *rt; + JSBool ok; + + rt = cx->runtime; + JS_ASSERT(!rt->gcRunning); + + JS_LOCK_GC(rt); + ok = AddToPtrTable(cx, &rt->gcIteratorTable, &iteratorTableInfo, obj); + JS_UNLOCK_GC(rt); + return ok; +} + +static void +CloseIteratorStates(JSContext *cx) +{ + JSRuntime *rt; + size_t count, newCount, i; + void **array; + JSObject *obj; + + rt = cx->runtime; + count = rt->gcIteratorTable.count; + array = rt->gcIteratorTable.array; + + newCount = 0; + for (i = 0; i != count; ++i) { + obj = (JSObject *)array[i]; + if (js_IsAboutToBeFinalized(cx, obj)) + js_CloseIteratorState(cx, obj); + else + array[newCount++] = obj; + } + ShrinkPtrTable(&rt->gcIteratorTable, &iteratorTableInfo, newCount); +} + +#if JS_HAS_GENERATORS + +void +js_RegisterGenerator(JSContext *cx, JSGenerator *gen) +{ + JSRuntime *rt; + + rt = cx->runtime; + JS_ASSERT(!rt->gcRunning); + JS_ASSERT(rt->state != JSRTS_LANDING); + JS_ASSERT(gen->state == JSGEN_NEWBORN); + + JS_LOCK_GC(rt); + gen->next = rt->gcCloseState.reachableList; + rt->gcCloseState.reachableList = gen; + METER(rt->gcStats.nclose++); + METER(rt->gcStats.maxnclose = JS_MAX(rt->gcStats.maxnclose, + rt->gcStats.nclose)); + JS_UNLOCK_GC(rt); +} + +/* + * We do not run close hooks when the parent scope of the generator instance + * becomes unreachable to prevent denial-of-service and resource leakage from + * misbehaved generators. + * + * Called from the GC. + */ +static JSBool +CanScheduleCloseHook(JSGenerator *gen) +{ + JSObject *parent; + JSBool canSchedule; + + /* Avoid OBJ_GET_PARENT overhead as we are in GC. */ + parent = JSVAL_TO_OBJECT(gen->obj->slots[JSSLOT_PARENT]); + canSchedule = *js_GetGCThingFlags(parent) & GCF_MARK; +#ifdef DEBUG_igor + if (!canSchedule) { + fprintf(stderr, "GEN: Kill without schedule, gen=%p parent=%p\n", + (void *)gen, (void *)parent); + } +#endif + return canSchedule; +} + +/* + * Check if we should delay execution of the close hook. + * + * Called outside GC or any locks. + * + * XXX The current implementation is a hack that embeds the knowledge of the + * browser embedding pending the resolution of bug 352788. In the browser we + * must not close any generators that came from a page that is currently in + * the browser history. We detect that using the fact in the browser the scope + * is history if scope->outerObject->innerObject != scope. + */ +static JSBool +ShouldDeferCloseHook(JSContext *cx, JSGenerator *gen, JSBool *defer) +{ + JSObject *parent, *obj; + JSClass *clasp; + JSExtendedClass *xclasp; + + /* + * This is called outside any locks, so use thread-safe macros to access + * parent and classes. + */ + *defer = JS_FALSE; + parent = OBJ_GET_PARENT(cx, gen->obj); + clasp = OBJ_GET_CLASS(cx, parent); + if (clasp->flags & JSCLASS_IS_EXTENDED) { + xclasp = (JSExtendedClass *)clasp; + if (xclasp->outerObject) { + obj = xclasp->outerObject(cx, parent); + if (!obj) + return JS_FALSE; + OBJ_TO_INNER_OBJECT(cx, obj); + if (!obj) + return JS_FALSE; + *defer = obj != parent; + } + } +#ifdef DEBUG_igor + if (*defer) { + fprintf(stderr, "GEN: deferring, gen=%p parent=%p\n", + (void *)gen, (void *)parent); + } +#endif + return JS_TRUE; +} + +/* + * Find all unreachable generators and move them to the todo queue from + * rt->gcCloseState.reachableList to execute thier close hooks after the GC + * cycle completes. To ensure liveness during the sweep phase we mark all + * generators we are going to close later. + */ +static void +FindAndMarkObjectsToClose(JSContext *cx, JSGCInvocationKind gckind, + JSGenerator **todoQueueTail) +{ + JSRuntime *rt; + JSGenerator *todo, **genp, *gen; + + rt = cx->runtime; + todo = NULL; + genp = &rt->gcCloseState.reachableList; + while ((gen = *genp) != NULL) { + if (*js_GetGCThingFlags(gen->obj) & GCF_MARK) { + genp = &gen->next; + } else { + /* Generator must not be executing when it becomes unreachable. */ + JS_ASSERT(gen->state == JSGEN_NEWBORN || + gen->state == JSGEN_OPEN || + gen->state == JSGEN_CLOSED); + + *genp = gen->next; + if (gen->state == JSGEN_OPEN && + js_FindFinallyHandler(gen->frame.script, gen->frame.pc) && + CanScheduleCloseHook(gen)) { + /* + * Generator yielded inside a try with a finally block. + * Schedule it for closing. + * + * We keep generators that yielded outside try-with-finally + * with gen->state == JSGEN_OPEN. The finalizer must deal with + * open generators as we may skip the close hooks, see below. + */ + gen->next = NULL; + *todoQueueTail = gen; + todoQueueTail = &gen->next; + if (!todo) + todo = gen; + METER(JS_ASSERT(rt->gcStats.nclose)); + METER(rt->gcStats.nclose--); + METER(rt->gcStats.closelater++); + METER(rt->gcStats.maxcloselater + = JS_MAX(rt->gcStats.maxcloselater, + rt->gcStats.closelater)); + } + } + } + + if (gckind == GC_LAST_CONTEXT) { + /* + * Remove scheduled hooks on shutdown as it is too late to run them: + * we do not allow execution of arbitrary scripts at this point. + */ + rt->gcCloseState.todoQueue = NULL; + } else { + /* + * Mark just-found unreachable generators *after* we scan the global + * list to prevent a generator that refers to other unreachable + * generators from keeping them on gcCloseState.reachableList. + */ + for (gen = todo; gen; gen = gen->next) + GC_MARK(cx, gen->obj, "newly scheduled generator"); + } +} + +/* + * Mark unreachable generators already scheduled to close and return the tail + * pointer to JSGCCloseState.todoQueue. + */ +static JSGenerator ** +MarkScheduledGenerators(JSContext *cx) +{ + JSRuntime *rt; + JSGenerator **genp, *gen; + + rt = cx->runtime; + genp = &rt->gcCloseState.todoQueue; + while ((gen = *genp) != NULL) { + if (CanScheduleCloseHook(gen)) { + GC_MARK(cx, gen->obj, "scheduled generator"); + genp = &gen->next; + } else { + /* Discard the generator from the list if its schedule is over. */ + *genp = gen->next; + METER(JS_ASSERT(rt->gcStats.closelater > 0)); + METER(rt->gcStats.closelater--); + } + } + return genp; +} + +#ifdef JS_THREADSAFE +# define GC_RUNNING_CLOSE_HOOKS_PTR(cx) \ + (&(cx)->thread->gcRunningCloseHooks) +#else +# define GC_RUNNING_CLOSE_HOOKS_PTR(cx) \ + (&(cx)->runtime->gcCloseState.runningCloseHook) +#endif + +typedef struct JSTempCloseList { + JSTempValueRooter tvr; + JSGenerator *head; +} JSTempCloseList; + +JS_STATIC_DLL_CALLBACK(void) +mark_temp_close_list(JSContext *cx, JSTempValueRooter *tvr) +{ + JSTempCloseList *list = (JSTempCloseList *)tvr; + JSGenerator *gen; + + for (gen = list->head; gen; gen = gen->next) + GC_MARK(cx, gen->obj, "temp list generator"); +} + +#define JS_PUSH_TEMP_CLOSE_LIST(cx, tempList) \ + JS_PUSH_TEMP_ROOT_MARKER(cx, mark_temp_close_list, &(tempList)->tvr) + +#define JS_POP_TEMP_CLOSE_LIST(cx, tempList) \ + JS_BEGIN_MACRO \ + JS_ASSERT((tempList)->tvr.u.marker == mark_temp_close_list); \ + JS_POP_TEMP_ROOT(cx, &(tempList)->tvr); \ + JS_END_MACRO + +JSBool +js_RunCloseHooks(JSContext *cx) +{ + JSRuntime *rt; + JSTempCloseList tempList; + JSStackFrame *fp; + JSGenerator **genp, *gen; + JSBool ok, defer; +#if JS_GCMETER + uint32 deferCount; +#endif + + rt = cx->runtime; + + /* + * It is OK to access todoQueue outside the lock here. When many threads + * update the todo list, accessing some older value of todoQueue in the + * worst case just delays the excution of close hooks. + */ + if (!rt->gcCloseState.todoQueue) + return JS_TRUE; + + /* + * To prevent an infinite loop when a close hook creats more objects with + * close hooks and then triggers GC we ignore recursive invocations of + * js_RunCloseHooks and limit number of hooks to execute to the initial + * size of the list. + */ + if (*GC_RUNNING_CLOSE_HOOKS_PTR(cx)) + return JS_TRUE; + + *GC_RUNNING_CLOSE_HOOKS_PTR(cx) = JS_TRUE; + + JS_LOCK_GC(rt); + tempList.head = rt->gcCloseState.todoQueue; + JS_PUSH_TEMP_CLOSE_LIST(cx, &tempList); + rt->gcCloseState.todoQueue = NULL; + METER(rt->gcStats.closelater = 0); + rt->gcPoke = JS_TRUE; + JS_UNLOCK_GC(rt); + + /* + * Set aside cx->fp since we do not want a close hook using caller or + * other means to backtrace into whatever stack might be active when + * running the hook. We store the current frame on the dormant list to + * protect against GC that the hook can trigger. + */ + fp = cx->fp; + if (fp) { + JS_ASSERT(!fp->dormantNext); + fp->dormantNext = cx->dormantFrameChain; + cx->dormantFrameChain = fp; + } + cx->fp = NULL; + + genp = &tempList.head; + ok = JS_TRUE; + while ((gen = *genp) != NULL) { + ok = ShouldDeferCloseHook(cx, gen, &defer); + if (!ok) { + /* Quit ASAP discarding the hook. */ + *genp = gen->next; + break; + } + if (defer) { + genp = &gen->next; + METER(deferCount++); + continue; + } + ok = js_CloseGeneratorObject(cx, gen); + + /* + * Unlink the generator after closing it to make sure it always stays + * rooted through tempList. + */ + *genp = gen->next; + + if (cx->throwing) { + /* + * Report the exception thrown by the close hook and continue to + * execute the rest of the hooks. + */ + if (!js_ReportUncaughtException(cx)) + JS_ClearPendingException(cx); + ok = JS_TRUE; + } else if (!ok) { + /* + * Assume this is a stop signal from the branch callback or + * other quit ASAP condition. Break execution until the next + * invocation of js_RunCloseHooks. + */ + break; + } + } + + cx->fp = fp; + if (fp) { + JS_ASSERT(cx->dormantFrameChain == fp); + cx->dormantFrameChain = fp->dormantNext; + fp->dormantNext = NULL; + } + + if (tempList.head) { + /* + * Some close hooks were not yet executed, put them back into the + * scheduled list. + */ + while ((gen = *genp) != NULL) { + genp = &gen->next; + METER(deferCount++); + } + + /* Now genp is a pointer to the tail of tempList. */ + JS_LOCK_GC(rt); + *genp = rt->gcCloseState.todoQueue; + rt->gcCloseState.todoQueue = tempList.head; + METER(rt->gcStats.closelater += deferCount); + METER(rt->gcStats.maxcloselater + = JS_MAX(rt->gcStats.maxcloselater, rt->gcStats.closelater)); + JS_UNLOCK_GC(rt); + } + + JS_POP_TEMP_CLOSE_LIST(cx, &tempList); + *GC_RUNNING_CLOSE_HOOKS_PTR(cx) = JS_FALSE; + + return ok; +} + +#endif /* JS_HAS_GENERATORS */ + +#if defined(DEBUG_brendan) || defined(DEBUG_timeless) +#define DEBUG_gchist +#endif + +#ifdef DEBUG_gchist +#define NGCHIST 64 + +static struct GCHist { + JSBool lastDitch; + JSGCThing *freeList; +} gchist[NGCHIST]; + +unsigned gchpos; +#endif + +void * +js_NewGCThing(JSContext *cx, uintN flags, size_t nbytes) +{ + JSRuntime *rt; + uintN flindex; + JSBool doGC; + JSGCThing *thing; + uint8 *flagp, *firstPage; + JSGCArenaList *arenaList; + jsuword offset; + JSGCArena *a; + JSLocalRootStack *lrs; +#ifdef JS_THREADSAFE + JSBool gcLocked; + uintN localMallocBytes; + JSGCThing **flbase, **lastptr; + JSGCThing *tmpthing; + uint8 *tmpflagp; + uintN maxFreeThings; /* max to take from the global free list */ + METER(size_t nfree); +#endif + + rt = cx->runtime; + METER(rt->gcStats.alloc++); /* this is not thread-safe */ + nbytes = JS_ROUNDUP(nbytes, sizeof(JSGCThing)); + flindex = GC_FREELIST_INDEX(nbytes); + +#ifdef JS_THREADSAFE + gcLocked = JS_FALSE; + JS_ASSERT(cx->thread); + flbase = cx->thread->gcFreeLists; + JS_ASSERT(flbase); + thing = flbase[flindex]; + localMallocBytes = cx->thread->gcMallocBytes; + if (thing && rt->gcMaxMallocBytes - rt->gcMallocBytes > localMallocBytes) { + flagp = thing->flagp; + flbase[flindex] = thing->next; + METER(rt->gcStats.localalloc++); /* this is not thread-safe */ + goto success; + } + + JS_LOCK_GC(rt); + gcLocked = JS_TRUE; + + /* Transfer thread-local counter to global one. */ + if (localMallocBytes != 0) { + cx->thread->gcMallocBytes = 0; + if (rt->gcMaxMallocBytes - rt->gcMallocBytes < localMallocBytes) + rt->gcMallocBytes = rt->gcMaxMallocBytes; + else + rt->gcMallocBytes += localMallocBytes; + } +#endif + JS_ASSERT(!rt->gcRunning); + if (rt->gcRunning) { + METER(rt->gcStats.finalfail++); + JS_UNLOCK_GC(rt); + return NULL; + } + +#ifdef TOO_MUCH_GC +#ifdef WAY_TOO_MUCH_GC + rt->gcPoke = JS_TRUE; +#endif + doGC = JS_TRUE; +#else + doGC = (rt->gcMallocBytes >= rt->gcMaxMallocBytes); +#endif + + arenaList = &rt->gcArenaList[flindex]; + for (;;) { + if (doGC) { + /* + * Keep rt->gcLock across the call into js_GC so we don't starve + * and lose to racing threads who deplete the heap just after + * js_GC has replenished it (or has synchronized with a racing + * GC that collected a bunch of garbage). This unfair scheduling + * can happen on certain operating systems. For the gory details, + * see bug 162779 at https://bugzilla.mozilla.org/. + */ + js_GC(cx, GC_LAST_DITCH); + METER(rt->gcStats.retry++); + } + + /* Try to get thing from the free list. */ + thing = arenaList->freeList; + if (thing) { + arenaList->freeList = thing->next; + flagp = thing->flagp; + JS_ASSERT(*flagp & GCF_FINAL); + METER(arenaList->stats.freelen--); + METER(arenaList->stats.recycle++); + +#ifdef JS_THREADSAFE + /* + * Refill the local free list by taking several things from the + * global free list unless we are still at rt->gcMaxMallocBytes + * barrier or the free list is already populated. The former + * happens when GC is canceled due to !gcCallback(cx, JSGC_BEGIN) + * or no gcPoke. The latter is caused via allocating new things + * in gcCallback(cx, JSGC_END). + */ + if (rt->gcMallocBytes >= rt->gcMaxMallocBytes || flbase[flindex]) + break; + tmpthing = arenaList->freeList; + if (tmpthing) { + maxFreeThings = MAX_THREAD_LOCAL_THINGS; + do { + if (!tmpthing->next) + break; + tmpthing = tmpthing->next; + } while (--maxFreeThings != 0); + + flbase[flindex] = arenaList->freeList; + arenaList->freeList = tmpthing->next; + tmpthing->next = NULL; + } +#endif + break; + } + + /* Allocate from the tail of last arena or from new arena if we can. */ + if ((arenaList->last && arenaList->lastLimit != GC_THINGS_SIZE) || + NewGCArena(rt, arenaList)) { + + offset = arenaList->lastLimit; + if ((offset & GC_PAGE_MASK) == 0) { + /* + * Skip JSGCPageInfo record located at GC_PAGE_SIZE boundary. + */ + offset += PAGE_THING_GAP(nbytes); + } + JS_ASSERT(offset + nbytes <= GC_THINGS_SIZE); + arenaList->lastLimit = (uint16)(offset + nbytes); + a = arenaList->last; + firstPage = (uint8 *)FIRST_THING_PAGE(a); + thing = (JSGCThing *)(firstPage + offset); + flagp = a->base + offset / sizeof(JSGCThing); + if (flagp >= firstPage) + flagp += GC_THINGS_SIZE; + METER(++arenaList->stats.nthings); + METER(arenaList->stats.maxthings = + JS_MAX(arenaList->stats.nthings, + arenaList->stats.maxthings)); + +#ifdef JS_THREADSAFE + /* + * Refill the local free list by taking free things from the last + * arena. Prefer to order free things by ascending address in the + * (unscientific) hope of better cache locality. + */ + if (rt->gcMallocBytes >= rt->gcMaxMallocBytes || flbase[flindex]) + break; + METER(nfree = 0); + lastptr = &flbase[flindex]; + maxFreeThings = MAX_THREAD_LOCAL_THINGS; + for (offset = arenaList->lastLimit; + offset != GC_THINGS_SIZE && maxFreeThings-- != 0; + offset += nbytes) { + if ((offset & GC_PAGE_MASK) == 0) + offset += PAGE_THING_GAP(nbytes); + JS_ASSERT(offset + nbytes <= GC_THINGS_SIZE); + tmpflagp = a->base + offset / sizeof(JSGCThing); + if (tmpflagp >= firstPage) + tmpflagp += GC_THINGS_SIZE; + + tmpthing = (JSGCThing *)(firstPage + offset); + tmpthing->flagp = tmpflagp; + *tmpflagp = GCF_FINAL; /* signifying that thing is free */ + + *lastptr = tmpthing; + lastptr = &tmpthing->next; + METER(++nfree); + } + arenaList->lastLimit = offset; + *lastptr = NULL; + METER(arenaList->stats.freelen += nfree); +#endif + break; + } + + /* Consider doing a "last ditch" GC unless already tried. */ + if (doGC) + goto fail; + rt->gcPoke = JS_TRUE; + doGC = JS_TRUE; + } + + /* We successfully allocated the thing. */ +#ifdef JS_THREADSAFE + success: +#endif + lrs = cx->localRootStack; + if (lrs) { + /* + * If we're in a local root scope, don't set newborn[type] at all, to + * avoid entraining garbage from it for an unbounded amount of time + * on this context. A caller will leave the local root scope and pop + * this reference, allowing thing to be GC'd if it has no other refs. + * See JS_EnterLocalRootScope and related APIs. + */ + if (js_PushLocalRoot(cx, lrs, (jsval) thing) < 0) { + /* + * When we fail for a thing allocated through the tail of the last + * arena, thing's flag byte is not initialized. So to prevent GC + * accessing the uninitialized flags during the finalization, we + * always mark the thing as final. See bug 337407. + */ + *flagp = GCF_FINAL; + goto fail; + } + } else { + /* + * No local root scope, so we're stuck with the old, fragile model of + * depending on a pigeon-hole newborn per type per context. + */ + cx->weakRoots.newborn[flags & GCF_TYPEMASK] = thing; + } + + /* We can't fail now, so update flags and rt->gc{,Private}Bytes. */ + *flagp = (uint8)flags; + + /* + * Clear thing before unlocking in case a GC run is about to scan it, + * finding it via newborn[]. + */ + thing->next = NULL; + thing->flagp = NULL; +#ifdef DEBUG_gchist + gchist[gchpos].lastDitch = doGC; + gchist[gchpos].freeList = rt->gcArenaList[flindex].freeList; + if (++gchpos == NGCHIST) + gchpos = 0; +#endif + METER(if (flags & GCF_LOCK) rt->gcStats.lockborn++); + METER(++rt->gcArenaList[flindex].stats.totalnew); +#ifdef JS_THREADSAFE + if (gcLocked) + JS_UNLOCK_GC(rt); +#endif + return thing; + +fail: +#ifdef JS_THREADSAFE + if (gcLocked) + JS_UNLOCK_GC(rt); +#endif + METER(rt->gcStats.fail++); + JS_ReportOutOfMemory(cx); + return NULL; +} + +JSBool +js_LockGCThing(JSContext *cx, void *thing) +{ + JSBool ok = js_LockGCThingRT(cx->runtime, thing); + if (!ok) + JS_ReportOutOfMemory(cx); + return ok; +} + +/* + * Deep GC-things can't be locked just by setting the GCF_LOCK bit, because + * their descendants must be marked by the GC. To find them during the mark + * phase, they are added to rt->gcLocksHash, which is created lazily. + * + * NB: we depend on the order of GC-thing type indexes here! + */ +#define GC_TYPE_IS_STRING(t) ((t) == GCX_STRING || \ + (t) >= GCX_EXTERNAL_STRING) +#define GC_TYPE_IS_XML(t) ((unsigned)((t) - GCX_NAMESPACE) <= \ + (unsigned)(GCX_XML - GCX_NAMESPACE)) +#define GC_TYPE_IS_DEEP(t) ((t) == GCX_OBJECT || GC_TYPE_IS_XML(t)) + +#define IS_DEEP_STRING(t,o) (GC_TYPE_IS_STRING(t) && \ + JSSTRING_IS_DEPENDENT((JSString *)(o))) + +#define GC_THING_IS_DEEP(t,o) (GC_TYPE_IS_DEEP(t) || IS_DEEP_STRING(t, o)) + +/* This is compatible with JSDHashEntryStub. */ +typedef struct JSGCLockHashEntry { + JSDHashEntryHdr hdr; + const JSGCThing *thing; + uint32 count; +} JSGCLockHashEntry; + +JSBool +js_LockGCThingRT(JSRuntime *rt, void *thing) +{ + JSBool ok, deep; + uint8 *flagp; + uintN flags, lock, type; + JSGCLockHashEntry *lhe; + + ok = JS_TRUE; + if (!thing) + return ok; + + flagp = js_GetGCThingFlags(thing); + + JS_LOCK_GC(rt); + flags = *flagp; + lock = (flags & GCF_LOCK); + type = (flags & GCF_TYPEMASK); + deep = GC_THING_IS_DEEP(type, thing); + + /* + * Avoid adding a rt->gcLocksHash entry for shallow things until someone + * nests a lock -- then start such an entry with a count of 2, not 1. + */ + if (lock || deep) { + if (!rt->gcLocksHash) { + rt->gcLocksHash = + JS_NewDHashTable(JS_DHashGetStubOps(), NULL, + sizeof(JSGCLockHashEntry), + GC_ROOTS_SIZE); + if (!rt->gcLocksHash) { + ok = JS_FALSE; + goto done; + } + } else if (lock == 0) { +#ifdef DEBUG + JSDHashEntryHdr *hdr = + JS_DHashTableOperate(rt->gcLocksHash, thing, + JS_DHASH_LOOKUP); + JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(hdr)); +#endif + } + + lhe = (JSGCLockHashEntry *) + JS_DHashTableOperate(rt->gcLocksHash, thing, JS_DHASH_ADD); + if (!lhe) { + ok = JS_FALSE; + goto done; + } + if (!lhe->thing) { + lhe->thing = thing; + lhe->count = deep ? 1 : 2; + } else { + JS_ASSERT(lhe->count >= 1); + lhe->count++; + } + } + + *flagp = (uint8)(flags | GCF_LOCK); + METER(rt->gcStats.lock++); + ok = JS_TRUE; +done: + JS_UNLOCK_GC(rt); + return ok; +} + +JSBool +js_UnlockGCThingRT(JSRuntime *rt, void *thing) +{ + uint8 *flagp, flags; + JSGCLockHashEntry *lhe; + + if (!thing) + return JS_TRUE; + + flagp = js_GetGCThingFlags(thing); + JS_LOCK_GC(rt); + flags = *flagp; + + if (flags & GCF_LOCK) { + if (!rt->gcLocksHash || + (lhe = (JSGCLockHashEntry *) + JS_DHashTableOperate(rt->gcLocksHash, thing, + JS_DHASH_LOOKUP), + JS_DHASH_ENTRY_IS_FREE(&lhe->hdr))) { + /* Shallow GC-thing with an implicit lock count of 1. */ + JS_ASSERT(!GC_THING_IS_DEEP(flags & GCF_TYPEMASK, thing)); + } else { + /* Basis or nested unlock of a deep thing, or nested of shallow. */ + if (--lhe->count != 0) + goto out; + JS_DHashTableOperate(rt->gcLocksHash, thing, JS_DHASH_REMOVE); + } + *flagp = (uint8)(flags & ~GCF_LOCK); + } + + rt->gcPoke = JS_TRUE; +out: + METER(rt->gcStats.unlock++); + JS_UNLOCK_GC(rt); + return JS_TRUE; +} + +#ifdef GC_MARK_DEBUG + +#include <stdio.h> +#include "jsprf.h" + +typedef struct GCMarkNode GCMarkNode; + +struct GCMarkNode { + void *thing; + const char *name; + GCMarkNode *next; + GCMarkNode *prev; +}; + +JS_FRIEND_DATA(FILE *) js_DumpGCHeap; +JS_EXPORT_DATA(void *) js_LiveThingToFind; + +#ifdef HAVE_XPCONNECT +#include "dump_xpc.h" +#endif + +static void +GetObjSlotName(JSScope *scope, JSObject *obj, uint32 slot, char *buf, + size_t bufsize) +{ + jsval nval; + JSScopeProperty *sprop; + JSClass *clasp; + uint32 key; + const char *slotname; + + if (!scope) { + JS_snprintf(buf, bufsize, "**UNKNOWN OBJECT MAP ENTRY**"); + return; + } + + sprop = SCOPE_LAST_PROP(scope); + while (sprop && sprop->slot != slot) + sprop = sprop->parent; + + if (!sprop) { + switch (slot) { + case JSSLOT_PROTO: + JS_snprintf(buf, bufsize, "__proto__"); + break; + case JSSLOT_PARENT: + JS_snprintf(buf, bufsize, "__parent__"); + break; + default: + slotname = NULL; + clasp = LOCKED_OBJ_GET_CLASS(obj); + if (clasp->flags & JSCLASS_IS_GLOBAL) { + key = slot - JSSLOT_START(clasp); +#define JS_PROTO(name,code,init) \ + if ((code) == key) { slotname = js_##name##_str; goto found; } +#include "jsproto.tbl" +#undef JS_PROTO + } + found: + if (slotname) + JS_snprintf(buf, bufsize, "CLASS_OBJECT(%s)", slotname); + else + JS_snprintf(buf, bufsize, "**UNKNOWN SLOT %ld**", (long)slot); + break; + } + } else { + nval = ID_TO_VALUE(sprop->id); + if (JSVAL_IS_INT(nval)) { + JS_snprintf(buf, bufsize, "%ld", (long)JSVAL_TO_INT(nval)); + } else if (JSVAL_IS_STRING(nval)) { + JS_snprintf(buf, bufsize, "%s", + JS_GetStringBytes(JSVAL_TO_STRING(nval))); + } else { + JS_snprintf(buf, bufsize, "**FINALIZED ATOM KEY**"); + } + } +} + +static const char * +gc_object_class_name(void* thing) +{ + uint8 *flagp = js_GetGCThingFlags(thing); + const char *className = ""; + static char depbuf[32]; + + switch (*flagp & GCF_TYPEMASK) { + case GCX_OBJECT: { + JSObject *obj = (JSObject *)thing; + JSClass *clasp = JSVAL_TO_PRIVATE(obj->slots[JSSLOT_CLASS]); + className = clasp->name; +#ifdef HAVE_XPCONNECT + if (clasp->flags & JSCLASS_PRIVATE_IS_NSISUPPORTS) { + jsval privateValue = obj->slots[JSSLOT_PRIVATE]; + + JS_ASSERT(clasp->flags & JSCLASS_HAS_PRIVATE); + if (!JSVAL_IS_VOID(privateValue)) { + void *privateThing = JSVAL_TO_PRIVATE(privateValue); + const char *xpcClassName = GetXPCObjectClassName(privateThing); + + if (xpcClassName) + className = xpcClassName; + } + } +#endif + break; + } + + case GCX_STRING: + case GCX_MUTABLE_STRING: { + JSString *str = (JSString *)thing; + if (JSSTRING_IS_DEPENDENT(str)) { + JS_snprintf(depbuf, sizeof depbuf, "start:%u, length:%u", + JSSTRDEP_START(str), JSSTRDEP_LENGTH(str)); + className = depbuf; + } else { + className = "string"; + } + break; + } + + case GCX_DOUBLE: + className = "double"; + break; + } + + return className; +} + +static void +gc_dump_thing(JSContext *cx, JSGCThing *thing, FILE *fp) +{ + GCMarkNode *prev = (GCMarkNode *)cx->gcCurrentMarkNode; + GCMarkNode *next = NULL; + char *path = NULL; + + while (prev) { + next = prev; + prev = prev->prev; + } + while (next) { + uint8 nextFlags = *js_GetGCThingFlags(next->thing); + if ((nextFlags & GCF_TYPEMASK) == GCX_OBJECT) { + path = JS_sprintf_append(path, "%s(%s @ 0x%08p).", + next->name, + gc_object_class_name(next->thing), + (JSObject*)next->thing); + } else { + path = JS_sprintf_append(path, "%s(%s).", + next->name, + gc_object_class_name(next->thing)); + } + next = next->next; + } + if (!path) + return; + + fprintf(fp, "%08lx ", (long)thing); + switch (*js_GetGCThingFlags(thing) & GCF_TYPEMASK) { + case GCX_OBJECT: + { + JSObject *obj = (JSObject *)thing; + jsval privateValue = obj->slots[JSSLOT_PRIVATE]; + void *privateThing = JSVAL_IS_VOID(privateValue) + ? NULL + : JSVAL_TO_PRIVATE(privateValue); + const char *className = gc_object_class_name(thing); + fprintf(fp, "object %8p %s", privateThing, className); + break; + } +#if JS_HAS_XML_SUPPORT + case GCX_NAMESPACE: + { + JSXMLNamespace *ns = (JSXMLNamespace *)thing; + fprintf(fp, "namespace %s:%s", + JS_GetStringBytes(ns->prefix), JS_GetStringBytes(ns->uri)); + break; + } + case GCX_QNAME: + { + JSXMLQName *qn = (JSXMLQName *)thing; + fprintf(fp, "qname %s(%s):%s", + JS_GetStringBytes(qn->prefix), JS_GetStringBytes(qn->uri), + JS_GetStringBytes(qn->localName)); + break; + } + case GCX_XML: + { + extern const char *js_xml_class_str[]; + JSXML *xml = (JSXML *)thing; + fprintf(fp, "xml %8p %s", xml, js_xml_class_str[xml->xml_class]); + break; + } +#endif + case GCX_DOUBLE: + fprintf(fp, "double %g", *(jsdouble *)thing); + break; + case GCX_PRIVATE: + fprintf(fp, "private %8p", (void *)thing); + break; + default: + fprintf(fp, "string %s", JS_GetStringBytes((JSString *)thing)); + break; + } + fprintf(fp, " via %s\n", path); + free(path); +} + +void +js_MarkNamedGCThing(JSContext *cx, void *thing, const char *name) +{ + GCMarkNode markNode; + + if (!thing) + return; + + markNode.thing = thing; + markNode.name = name; + markNode.next = NULL; + markNode.prev = (GCMarkNode *)cx->gcCurrentMarkNode; + if (markNode.prev) + markNode.prev->next = &markNode; + cx->gcCurrentMarkNode = &markNode; + + if (thing == js_LiveThingToFind) { + /* + * Dump js_LiveThingToFind each time we reach it during the marking + * phase of GC to print all live references to the thing. + */ + gc_dump_thing(cx, thing, stderr); + } + + js_MarkGCThing(cx, thing); + + if (markNode.prev) + markNode.prev->next = NULL; + cx->gcCurrentMarkNode = markNode.prev; +} + +#endif /* !GC_MARK_DEBUG */ + +static void +gc_mark_atom_key_thing(void *thing, void *arg) +{ + JSContext *cx = (JSContext *) arg; + + GC_MARK(cx, thing, "atom"); +} + +void +js_MarkAtom(JSContext *cx, JSAtom *atom) +{ + jsval key; + + if (atom->flags & ATOM_MARK) + return; + atom->flags |= ATOM_MARK; + key = ATOM_KEY(atom); + if (JSVAL_IS_GCTHING(key)) { +#ifdef GC_MARK_DEBUG + char name[32]; + + if (JSVAL_IS_STRING(key)) { + JS_snprintf(name, sizeof name, "'%s'", + JS_GetStringBytes(JSVAL_TO_STRING(key))); + } else { + JS_snprintf(name, sizeof name, "<%x>", key); + } +#endif + GC_MARK(cx, JSVAL_TO_GCTHING(key), name); + } + if (atom->flags & ATOM_HIDDEN) + js_MarkAtom(cx, atom->entry.value); +} + +static void +AddThingToUnscannedBag(JSRuntime *rt, void *thing, uint8 *flagp); + +static void +MarkGCThingChildren(JSContext *cx, void *thing, uint8 *flagp, + JSBool shouldCheckRecursion) +{ + JSRuntime *rt; + JSObject *obj; + jsval v, *vp, *end; + void *next_thing; + uint8 *next_flagp; + JSString *str; +#ifdef JS_GCMETER + uint32 tailCallNesting; +#endif +#ifdef GC_MARK_DEBUG + JSScope *scope; + char name[32]; +#endif + + /* + * With JS_GC_ASSUME_LOW_C_STACK defined the mark phase of GC always + * uses the non-recursive code that otherwise would be called only on + * a low C stack condition. + */ +#ifdef JS_GC_ASSUME_LOW_C_STACK +# define RECURSION_TOO_DEEP() shouldCheckRecursion +#else + int stackDummy; +# define RECURSION_TOO_DEEP() (shouldCheckRecursion && \ + !JS_CHECK_STACK_SIZE(cx, stackDummy)) +#endif + + rt = cx->runtime; + METER(tailCallNesting = 0); + METER(if (++rt->gcStats.cdepth > rt->gcStats.maxcdepth) + rt->gcStats.maxcdepth = rt->gcStats.cdepth); + +#ifndef GC_MARK_DEBUG + start: +#endif + JS_ASSERT(flagp); + JS_ASSERT(*flagp & GCF_MARK); /* the caller must already mark the thing */ + METER(if (++rt->gcStats.depth > rt->gcStats.maxdepth) + rt->gcStats.maxdepth = rt->gcStats.depth); +#ifdef GC_MARK_DEBUG + if (js_DumpGCHeap) + gc_dump_thing(cx, thing, js_DumpGCHeap); +#endif + + switch (*flagp & GCF_TYPEMASK) { + case GCX_OBJECT: + if (RECURSION_TOO_DEEP()) + goto add_to_unscanned_bag; + /* If obj->slots is null, obj must be a newborn. */ + obj = (JSObject *) thing; + vp = obj->slots; + if (!vp) + break; + + /* Mark slots if they are small enough to be GC-allocated. */ + if ((vp[-1] + 1) * sizeof(jsval) <= GC_NBYTES_MAX) + GC_MARK(cx, vp - 1, "slots"); + + /* Set up local variables to loop over unmarked things. */ + end = vp + ((obj->map->ops->mark) + ? obj->map->ops->mark(cx, obj, NULL) + : JS_MIN(obj->map->freeslot, obj->map->nslots)); + thing = NULL; + flagp = NULL; +#ifdef GC_MARK_DEBUG + scope = OBJ_IS_NATIVE(obj) ? OBJ_SCOPE(obj) : NULL; +#endif + for (; vp != end; ++vp) { + v = *vp; + if (!JSVAL_IS_GCTHING(v) || v == JSVAL_NULL) + continue; + next_thing = JSVAL_TO_GCTHING(v); + if (next_thing == thing) + continue; + next_flagp = js_GetGCThingFlags(next_thing); + if (*next_flagp & GCF_MARK) + continue; + JS_ASSERT(*next_flagp != GCF_FINAL); + if (thing) { +#ifdef GC_MARK_DEBUG + GC_MARK(cx, thing, name); +#else + *flagp |= GCF_MARK; + MarkGCThingChildren(cx, thing, flagp, JS_TRUE); +#endif + if (*next_flagp & GCF_MARK) { + /* + * This happens when recursive MarkGCThingChildren marks + * the thing with flags referred by *next_flagp. + */ + thing = NULL; + continue; + } + } +#ifdef GC_MARK_DEBUG + GetObjSlotName(scope, obj, vp - obj->slots, name, sizeof name); +#endif + thing = next_thing; + flagp = next_flagp; + } + if (thing) { + /* + * thing came from the last unmarked GC-thing slot and we + * can optimize tail recursion. + * + * Since we already know that there is enough C stack space, + * we clear shouldCheckRecursion to avoid extra checking in + * RECURSION_TOO_DEEP. + */ + shouldCheckRecursion = JS_FALSE; + goto on_tail_recursion; + } + break; + +#ifdef DEBUG + case GCX_STRING: + str = (JSString *)thing; + JS_ASSERT(!JSSTRING_IS_DEPENDENT(str)); + break; +#endif + + case GCX_MUTABLE_STRING: + str = (JSString *)thing; + if (!JSSTRING_IS_DEPENDENT(str)) + break; + thing = JSSTRDEP_BASE(str); + flagp = js_GetGCThingFlags(thing); + if (*flagp & GCF_MARK) + break; +#ifdef GC_MARK_DEBUG + strcpy(name, "base"); +#endif + /* Fallthrough to code to deal with the tail recursion. */ + + on_tail_recursion: +#ifdef GC_MARK_DEBUG + /* + * Do not eliminate C recursion when debugging to allow + * js_MarkNamedGCThing to build a full dump of live GC + * things. + */ + GC_MARK(cx, thing, name); + break; +#else + /* Eliminate tail recursion for the last unmarked child. */ + JS_ASSERT(*flagp != GCF_FINAL); + METER(++tailCallNesting); + *flagp |= GCF_MARK; + goto start; +#endif + +#if JS_HAS_XML_SUPPORT + case GCX_NAMESPACE: + if (RECURSION_TOO_DEEP()) + goto add_to_unscanned_bag; + js_MarkXMLNamespace(cx, (JSXMLNamespace *)thing); + break; + + case GCX_QNAME: + if (RECURSION_TOO_DEEP()) + goto add_to_unscanned_bag; + js_MarkXMLQName(cx, (JSXMLQName *)thing); + break; + + case GCX_XML: + if (RECURSION_TOO_DEEP()) + goto add_to_unscanned_bag; + js_MarkXML(cx, (JSXML *)thing); + break; +#endif + add_to_unscanned_bag: + AddThingToUnscannedBag(cx->runtime, thing, flagp); + break; + } + +#undef RECURSION_TOO_DEEP + + METER(rt->gcStats.depth -= 1 + tailCallNesting); + METER(rt->gcStats.cdepth--); +} + +/* + * Avoid using PAGE_THING_GAP inside this macro to optimize the + * thingsPerUnscannedChunk calculation when thingSize is a power of two. + */ +#define GET_GAP_AND_CHUNK_SPAN(thingSize, thingsPerUnscannedChunk, pageGap) \ + JS_BEGIN_MACRO \ + if (0 == ((thingSize) & ((thingSize) - 1))) { \ + pageGap = (thingSize); \ + thingsPerUnscannedChunk = ((GC_PAGE_SIZE / (thingSize)) \ + + JS_BITS_PER_WORD - 1) \ + >> JS_BITS_PER_WORD_LOG2; \ + } else { \ + pageGap = GC_PAGE_SIZE % (thingSize); \ + thingsPerUnscannedChunk = JS_HOWMANY(GC_PAGE_SIZE / (thingSize), \ + JS_BITS_PER_WORD); \ + } \ + JS_END_MACRO + +static void +AddThingToUnscannedBag(JSRuntime *rt, void *thing, uint8 *flagp) +{ + JSGCPageInfo *pi; + JSGCArena *arena; + size_t thingSize; + size_t thingsPerUnscannedChunk; + size_t pageGap; + size_t chunkIndex; + jsuword bit; + + /* Things from delayed scanning bag are marked as GCF_MARK | GCF_FINAL. */ + JS_ASSERT((*flagp & (GCF_MARK | GCF_FINAL)) == GCF_MARK); + *flagp |= GCF_FINAL; + + METER(rt->gcStats.unscanned++); +#ifdef DEBUG + ++rt->gcUnscannedBagSize; + METER(if (rt->gcUnscannedBagSize > rt->gcStats.maxunscanned) + rt->gcStats.maxunscanned = rt->gcUnscannedBagSize); +#endif + + pi = THING_TO_PAGE(thing); + arena = PAGE_TO_ARENA(pi); + thingSize = arena->list->thingSize; + GET_GAP_AND_CHUNK_SPAN(thingSize, thingsPerUnscannedChunk, pageGap); + chunkIndex = (((jsuword)thing & GC_PAGE_MASK) - pageGap) / + (thingSize * thingsPerUnscannedChunk); + JS_ASSERT(chunkIndex < JS_BITS_PER_WORD); + bit = (jsuword)1 << chunkIndex; + if (pi->unscannedBitmap != 0) { + JS_ASSERT(rt->gcUnscannedArenaStackTop); + if (thingsPerUnscannedChunk != 1) { + if (pi->unscannedBitmap & bit) { + /* Chunk already contains things to scan later. */ + return; + } + } else { + /* + * The chunk must not contain things to scan later if there is + * only one thing per chunk. + */ + JS_ASSERT(!(pi->unscannedBitmap & bit)); + } + pi->unscannedBitmap |= bit; + JS_ASSERT(arena->unscannedPages & ((size_t)1 << PAGE_INDEX(pi))); + } else { + /* + * The thing is the first unscanned thing in the page, set the bit + * corresponding to this page arena->unscannedPages. + */ + pi->unscannedBitmap = bit; + JS_ASSERT(PAGE_INDEX(pi) < JS_BITS_PER_WORD); + bit = (jsuword)1 << PAGE_INDEX(pi); + JS_ASSERT(!(arena->unscannedPages & bit)); + if (arena->unscannedPages != 0) { + arena->unscannedPages |= bit; + JS_ASSERT(arena->prevUnscanned); + JS_ASSERT(rt->gcUnscannedArenaStackTop); + } else { + /* + * The thing is the first unscanned thing in the whole arena, push + * the arena on the stack of unscanned arenas unless the arena + * has already been pushed. We detect that through prevUnscanned + * field which is NULL only for not yet pushed arenas. To ensure + * that prevUnscanned != NULL even when the stack contains one + * element, we make prevUnscanned for the arena at the bottom + * to point to itself. + * + * See comments in ScanDelayedChildren. + */ + arena->unscannedPages = bit; + if (!arena->prevUnscanned) { + if (!rt->gcUnscannedArenaStackTop) { + /* Stack was empty, mark the arena as bottom element. */ + arena->prevUnscanned = arena; + } else { + JS_ASSERT(rt->gcUnscannedArenaStackTop->prevUnscanned); + arena->prevUnscanned = rt->gcUnscannedArenaStackTop; + } + rt->gcUnscannedArenaStackTop = arena; + } + } + } + JS_ASSERT(rt->gcUnscannedArenaStackTop); +} + +static void +ScanDelayedChildren(JSContext *cx) +{ + JSRuntime *rt; + JSGCArena *arena; + size_t thingSize; + size_t thingsPerUnscannedChunk; + size_t pageGap; + size_t pageIndex; + JSGCPageInfo *pi; + size_t chunkIndex; + size_t thingOffset, thingLimit; + JSGCThing *thing; + uint8 *flagp; + JSGCArena *prevArena; + + rt = cx->runtime; + arena = rt->gcUnscannedArenaStackTop; + if (!arena) { + JS_ASSERT(rt->gcUnscannedBagSize == 0); + return; + } + + init_size: + thingSize = arena->list->thingSize; + GET_GAP_AND_CHUNK_SPAN(thingSize, thingsPerUnscannedChunk, pageGap); + for (;;) { + /* + * The following assert verifies that the current arena belongs to + * the unscan stack since AddThingToUnscannedBag ensures that even + * for stack's bottom prevUnscanned != NULL but rather points to self. + */ + JS_ASSERT(arena->prevUnscanned); + JS_ASSERT(rt->gcUnscannedArenaStackTop->prevUnscanned); + while (arena->unscannedPages != 0) { + pageIndex = JS_FLOOR_LOG2W(arena->unscannedPages); + JS_ASSERT(pageIndex < GC_PAGE_COUNT); + pi = (JSGCPageInfo *)(FIRST_THING_PAGE(arena) + + pageIndex * GC_PAGE_SIZE); + JS_ASSERT(pi->unscannedBitmap); + chunkIndex = JS_FLOOR_LOG2W(pi->unscannedBitmap); + pi->unscannedBitmap &= ~((jsuword)1 << chunkIndex); + if (pi->unscannedBitmap == 0) + arena->unscannedPages &= ~((jsuword)1 << pageIndex); + thingOffset = (pageGap + + chunkIndex * thingsPerUnscannedChunk * thingSize); + JS_ASSERT(thingOffset >= sizeof(JSGCPageInfo)); + thingLimit = thingOffset + thingsPerUnscannedChunk * thingSize; + if (thingsPerUnscannedChunk != 1) { + /* + * thingLimit can go beyond the last allocated thing for the + * last chunk as the real limit can be inside the chunk. + */ + if (arena->list->last == arena && + arena->list->lastLimit < (pageIndex * GC_PAGE_SIZE + + thingLimit)) { + thingLimit = (arena->list->lastLimit - + pageIndex * GC_PAGE_SIZE); + } else if (thingLimit > GC_PAGE_SIZE) { + thingLimit = GC_PAGE_SIZE; + } + JS_ASSERT(thingLimit > thingOffset); + } + JS_ASSERT(arena->list->last != arena || + arena->list->lastLimit >= (pageIndex * GC_PAGE_SIZE + + thingLimit)); + JS_ASSERT(thingLimit <= GC_PAGE_SIZE); + + for (; thingOffset != thingLimit; thingOffset += thingSize) { + /* + * XXX: inline js_GetGCThingFlags() to use already available + * pi. + */ + thing = (void *)((jsuword)pi + thingOffset); + flagp = js_GetGCThingFlags(thing); + if (thingsPerUnscannedChunk != 1) { + /* + * Skip free or already scanned things that share the chunk + * with unscanned ones. + */ + if ((*flagp & (GCF_MARK|GCF_FINAL)) != (GCF_MARK|GCF_FINAL)) + continue; + } + JS_ASSERT((*flagp & (GCF_MARK|GCF_FINAL)) + == (GCF_MARK|GCF_FINAL)); + *flagp &= ~GCF_FINAL; +#ifdef DEBUG + JS_ASSERT(rt->gcUnscannedBagSize != 0); + --rt->gcUnscannedBagSize; + + /* + * Check that GC thing type is consistent with the type of + * things that can be put to the unscanned bag. + */ + switch (*flagp & GCF_TYPEMASK) { + case GCX_OBJECT: +# if JS_HAS_XML_SUPPORT + case GCX_NAMESPACE: + case GCX_QNAME: + case GCX_XML: +# endif + break; + default: + JS_ASSERT(0); + } +#endif + MarkGCThingChildren(cx, thing, flagp, JS_FALSE); + } + } + /* + * We finished scanning of the arena but we can only pop it from + * the stack if the arena is the stack's top. + * + * When MarkGCThingChildren from the above calls + * AddThingToUnscannedBag and the latter pushes new arenas to the + * stack, we have to skip popping of this arena until it becomes + * the top of the stack again. + */ + if (arena == rt->gcUnscannedArenaStackTop) { + prevArena = arena->prevUnscanned; + arena->prevUnscanned = NULL; + if (arena == prevArena) { + /* + * prevUnscanned points to itself and we reached the bottom + * of the stack. + */ + break; + } + rt->gcUnscannedArenaStackTop = arena = prevArena; + } else { + arena = rt->gcUnscannedArenaStackTop; + } + if (arena->list->thingSize != thingSize) + goto init_size; + } + JS_ASSERT(rt->gcUnscannedArenaStackTop); + JS_ASSERT(!rt->gcUnscannedArenaStackTop->prevUnscanned); + rt->gcUnscannedArenaStackTop = NULL; + JS_ASSERT(rt->gcUnscannedBagSize == 0); +} + +void +js_MarkGCThing(JSContext *cx, void *thing) +{ + uint8 *flagp; + + if (!thing) + return; + + flagp = js_GetGCThingFlags(thing); + JS_ASSERT(*flagp != GCF_FINAL); + if (*flagp & GCF_MARK) + return; + *flagp |= GCF_MARK; + + if (!cx->insideGCMarkCallback) { + MarkGCThingChildren(cx, thing, flagp, JS_TRUE); + } else { + /* + * For API compatibility we allow for the callback to assume that + * after it calls js_MarkGCThing for the last time, the callback + * can start to finalize its own objects that are only referenced + * by unmarked GC things. + * + * Since we do not know which call from inside the callback is the + * last, we ensure that the unscanned bag is always empty when we + * return to the callback and all marked things are scanned. + * + * As an optimization we do not check for the stack size here and + * pass JS_FALSE as the last argument to MarkGCThingChildren. + * Otherwise with low C stack the thing would be pushed to the bag + * just to be feed to MarkGCThingChildren from inside + * ScanDelayedChildren. + */ + cx->insideGCMarkCallback = JS_FALSE; + MarkGCThingChildren(cx, thing, flagp, JS_FALSE); + ScanDelayedChildren(cx); + cx->insideGCMarkCallback = JS_TRUE; + } +} + +JS_STATIC_DLL_CALLBACK(JSDHashOperator) +gc_root_marker(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 num, void *arg) +{ + JSGCRootHashEntry *rhe = (JSGCRootHashEntry *)hdr; + jsval *rp = (jsval *)rhe->root; + jsval v = *rp; + + /* Ignore null object and scalar values. */ + if (!JSVAL_IS_NULL(v) && JSVAL_IS_GCTHING(v)) { + JSContext *cx = (JSContext *)arg; +#ifdef DEBUG + JSBool root_points_to_gcArenaList = JS_FALSE; + jsuword thing = (jsuword) JSVAL_TO_GCTHING(v); + uintN i; + JSGCArenaList *arenaList; + JSGCArena *a; + size_t limit; + + for (i = 0; i < GC_NUM_FREELISTS; i++) { + arenaList = &cx->runtime->gcArenaList[i]; + limit = arenaList->lastLimit; + for (a = arenaList->last; a; a = a->prev) { + if (thing - FIRST_THING_PAGE(a) < limit) { + root_points_to_gcArenaList = JS_TRUE; + break; + } + limit = GC_THINGS_SIZE; + } + } + if (!root_points_to_gcArenaList && rhe->name) { + fprintf(stderr, +"JS API usage error: the address passed to JS_AddNamedRoot currently holds an\n" +"invalid jsval. This is usually caused by a missing call to JS_RemoveRoot.\n" +"The root's name is \"%s\".\n", + rhe->name); + } + JS_ASSERT(root_points_to_gcArenaList); +#endif + + GC_MARK(cx, JSVAL_TO_GCTHING(v), rhe->name ? rhe->name : "root"); + } + return JS_DHASH_NEXT; +} + +JS_STATIC_DLL_CALLBACK(JSDHashOperator) +gc_lock_marker(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 num, void *arg) +{ + JSGCLockHashEntry *lhe = (JSGCLockHashEntry *)hdr; + void *thing = (void *)lhe->thing; + JSContext *cx = (JSContext *)arg; + + GC_MARK(cx, thing, "locked object"); + return JS_DHASH_NEXT; +} + +#define GC_MARK_JSVALS(cx, len, vec, name) \ + JS_BEGIN_MACRO \ + jsval _v, *_vp, *_end; \ + \ + for (_vp = vec, _end = _vp + len; _vp < _end; _vp++) { \ + _v = *_vp; \ + if (JSVAL_IS_GCTHING(_v)) \ + GC_MARK(cx, JSVAL_TO_GCTHING(_v), name); \ + } \ + JS_END_MACRO + +void +js_MarkStackFrame(JSContext *cx, JSStackFrame *fp) +{ + uintN depth, nslots; + + if (fp->callobj) + GC_MARK(cx, fp->callobj, "call object"); + if (fp->argsobj) + GC_MARK(cx, fp->argsobj, "arguments object"); + if (fp->varobj) + GC_MARK(cx, fp->varobj, "variables object"); + if (fp->script) { + js_MarkScript(cx, fp->script); + if (fp->spbase) { + /* + * Don't mark what has not been pushed yet, or what has been + * popped already. + */ + depth = fp->script->depth; + nslots = (JS_UPTRDIFF(fp->sp, fp->spbase) + < depth * sizeof(jsval)) + ? (uintN)(fp->sp - fp->spbase) + : depth; + GC_MARK_JSVALS(cx, nslots, fp->spbase, "operand"); + } + } + + /* Allow for primitive this parameter due to JSFUN_THISP_* flags. */ + JS_ASSERT(JSVAL_IS_OBJECT((jsval)fp->thisp) || + (fp->fun && JSFUN_THISP_FLAGS(fp->fun->flags))); + if (JSVAL_IS_GCTHING((jsval)fp->thisp)) + GC_MARK(cx, JSVAL_TO_GCTHING((jsval)fp->thisp), "this"); + + /* + * Mark fp->argv, even though in the common case it will be marked via our + * caller's frame, or via a JSStackHeader if fp was pushed by an external + * invocation. + * + * The hard case is when there is not enough contiguous space in the stack + * arena for actual, missing formal, and local root (JSFunctionSpec.extra) + * slots. In this case, fp->argv points to new space in a new arena, and + * marking the caller's operand stack, or an external caller's allocated + * stack tracked by a JSStackHeader, will not mark all the values stored + * and addressable via fp->argv. + * + * So in summary, solely for the hard case of moving argv due to missing + * formals and extra roots, we must mark actuals, missing formals, and any + * local roots arrayed at fp->argv here. + * + * It would be good to avoid redundant marking of the same reference, in + * the case where fp->argv does point into caller-allocated space tracked + * by fp->down->spbase or cx->stackHeaders. This would allow callbacks + * such as the forthcoming rt->gcThingCallback (bug 333078) to compute JS + * reference counts. So this comment deserves a FIXME bug to cite. + */ + if (fp->argv) { + nslots = fp->argc; + if (fp->fun) { + if (fp->fun->nargs > nslots) + nslots = fp->fun->nargs; + if (!FUN_INTERPRETED(fp->fun)) + nslots += fp->fun->u.n.extra; + } + GC_MARK_JSVALS(cx, nslots + 2, fp->argv - 2, "arg"); + } + if (JSVAL_IS_GCTHING(fp->rval)) + GC_MARK(cx, JSVAL_TO_GCTHING(fp->rval), "rval"); + if (fp->vars) + GC_MARK_JSVALS(cx, fp->nvars, fp->vars, "var"); + GC_MARK(cx, fp->scopeChain, "scope chain"); + if (fp->sharpArray) + GC_MARK(cx, fp->sharpArray, "sharp array"); + + if (fp->xmlNamespace) + GC_MARK(cx, fp->xmlNamespace, "xmlNamespace"); +} + +static void +MarkWeakRoots(JSContext *cx, JSWeakRoots *wr) +{ + uintN i; + void *thing; + + for (i = 0; i < GCX_NTYPES; i++) + GC_MARK(cx, wr->newborn[i], gc_typenames[i]); + if (wr->lastAtom) + GC_MARK_ATOM(cx, wr->lastAtom); + if (JSVAL_IS_GCTHING(wr->lastInternalResult)) { + thing = JSVAL_TO_GCTHING(wr->lastInternalResult); + if (thing) + GC_MARK(cx, thing, "lastInternalResult"); + } +} + +/* + * When gckind is GC_LAST_DITCH, it indicates a call from js_NewGCThing with + * rt->gcLock already held and when the lock should be kept on return. + */ +void +js_GC(JSContext *cx, JSGCInvocationKind gckind) +{ + JSRuntime *rt; + JSBool keepAtoms; + uintN i, type; + JSContext *iter, *acx; +#if JS_HAS_GENERATORS + JSGenerator **genTodoTail; +#endif + JSStackFrame *fp, *chain; + JSStackHeader *sh; + JSTempValueRooter *tvr; + size_t nbytes, limit, offset; + JSGCArena *a, **ap; + uint8 flags, *flagp, *firstPage; + JSGCThing *thing, *freeList; + JSGCArenaList *arenaList; + GCFinalizeOp finalizer; + JSBool allClear; +#ifdef JS_THREADSAFE + uint32 requestDebit; +#endif + + rt = cx->runtime; +#ifdef JS_THREADSAFE + /* Avoid deadlock. */ + JS_ASSERT(!JS_IS_RUNTIME_LOCKED(rt)); +#endif + + if (gckind == GC_LAST_DITCH) { + /* The last ditch GC preserves all atoms and weak roots. */ + keepAtoms = JS_TRUE; + } else { + JS_CLEAR_WEAK_ROOTS(&cx->weakRoots); + rt->gcPoke = JS_TRUE; + + /* Keep atoms when a suspended compile is running on another context. */ + keepAtoms = (rt->gcKeepAtoms != 0); + } + + /* + * Don't collect garbage if the runtime isn't up, and cx is not the last + * context in the runtime. The last context must force a GC, and nothing + * should suppress that final collection or there may be shutdown leaks, + * or runtime bloat until the next context is created. + */ + if (rt->state != JSRTS_UP && gckind != GC_LAST_CONTEXT) + return; + + restart_after_callback: + /* + * Let the API user decide to defer a GC if it wants to (unless this + * is the last context). Invoke the callback regardless. + */ + if (rt->gcCallback && + !rt->gcCallback(cx, JSGC_BEGIN) && + gckind != GC_LAST_CONTEXT) { + return; + } + + /* Lock out other GC allocator and collector invocations. */ + if (gckind != GC_LAST_DITCH) + JS_LOCK_GC(rt); + + /* Do nothing if no mutator has executed since the last GC. */ + if (!rt->gcPoke) { + METER(rt->gcStats.nopoke++); + if (gckind != GC_LAST_DITCH) + JS_UNLOCK_GC(rt); + return; + } + METER(rt->gcStats.poke++); + rt->gcPoke = JS_FALSE; + +#ifdef JS_THREADSAFE + JS_ASSERT(cx->thread->id == js_CurrentThreadId()); + + /* Bump gcLevel and return rather than nest on this thread. */ + if (rt->gcThread == cx->thread) { + JS_ASSERT(rt->gcLevel > 0); + rt->gcLevel++; + METER(if (rt->gcLevel > rt->gcStats.maxlevel) + rt->gcStats.maxlevel = rt->gcLevel); + if (gckind != GC_LAST_DITCH) + JS_UNLOCK_GC(rt); + return; + } + + /* + * If we're in one or more requests (possibly on more than one context) + * running on the current thread, indicate, temporarily, that all these + * requests are inactive. If cx->thread is NULL, then cx is not using + * the request model, and does not contribute to rt->requestCount. + */ + requestDebit = 0; + if (cx->thread) { + JSCList *head, *link; + + /* + * Check all contexts on cx->thread->contextList for active requests, + * counting each such context against requestDebit. + */ + head = &cx->thread->contextList; + for (link = head->next; link != head; link = link->next) { + acx = CX_FROM_THREAD_LINKS(link); + JS_ASSERT(acx->thread == cx->thread); + if (acx->requestDepth) + requestDebit++; + } + } else { + /* + * We assert, but check anyway, in case someone is misusing the API. + * Avoiding the loop over all of rt's contexts is a win in the event + * that the GC runs only on request-less contexts with null threads, + * in a special thread such as might be used by the UI/DOM/Layout + * "mozilla" or "main" thread in Mozilla-the-browser. + */ + JS_ASSERT(cx->requestDepth == 0); + if (cx->requestDepth) + requestDebit = 1; + } + if (requestDebit) { + JS_ASSERT(requestDebit <= rt->requestCount); + rt->requestCount -= requestDebit; + if (rt->requestCount == 0) + JS_NOTIFY_REQUEST_DONE(rt); + } + + /* If another thread is already in GC, don't attempt GC; wait instead. */ + if (rt->gcLevel > 0) { + /* Bump gcLevel to restart the current GC, so it finds new garbage. */ + rt->gcLevel++; + METER(if (rt->gcLevel > rt->gcStats.maxlevel) + rt->gcStats.maxlevel = rt->gcLevel); + + /* Wait for the other thread to finish, then resume our request. */ + while (rt->gcLevel > 0) + JS_AWAIT_GC_DONE(rt); + if (requestDebit) + rt->requestCount += requestDebit; + if (gckind != GC_LAST_DITCH) + JS_UNLOCK_GC(rt); + return; + } + + /* No other thread is in GC, so indicate that we're now in GC. */ + rt->gcLevel = 1; + rt->gcThread = cx->thread; + + /* Wait for all other requests to finish. */ + while (rt->requestCount > 0) + JS_AWAIT_REQUEST_DONE(rt); + +#else /* !JS_THREADSAFE */ + + /* Bump gcLevel and return rather than nest; the outer gc will restart. */ + rt->gcLevel++; + METER(if (rt->gcLevel > rt->gcStats.maxlevel) + rt->gcStats.maxlevel = rt->gcLevel); + if (rt->gcLevel > 1) + return; + +#endif /* !JS_THREADSAFE */ + + /* + * Set rt->gcRunning here within the GC lock, and after waiting for any + * active requests to end, so that new requests that try to JS_AddRoot, + * JS_RemoveRoot, or JS_RemoveRootRT block in JS_BeginRequest waiting for + * rt->gcLevel to drop to zero, while request-less calls to the *Root* + * APIs block in js_AddRoot or js_RemoveRoot (see above in this file), + * waiting for GC to finish. + */ + rt->gcRunning = JS_TRUE; + JS_UNLOCK_GC(rt); + + /* Reset malloc counter. */ + rt->gcMallocBytes = 0; + + /* Drop atoms held by the property cache, and clear property weak links. */ + js_DisablePropertyCache(cx); + js_FlushPropertyCache(cx); +#ifdef DEBUG_scopemeters + { extern void js_DumpScopeMeters(JSRuntime *rt); + js_DumpScopeMeters(rt); + } +#endif + +#ifdef JS_THREADSAFE + /* + * Set all thread local freelists to NULL. We may visit a thread's + * freelist more than once. To avoid redundant clearing we unroll the + * current thread's step. + * + * Also, in case a JSScript wrapped within an object was finalized, we + * null acx->thread->gsnCache.script and finish the cache's hashtable. + * Note that js_DestroyScript, called from script_finalize, will have + * already cleared cx->thread->gsnCache above during finalization, so we + * don't have to here. + */ + memset(cx->thread->gcFreeLists, 0, sizeof cx->thread->gcFreeLists); + iter = NULL; + while ((acx = js_ContextIterator(rt, JS_FALSE, &iter)) != NULL) { + if (!acx->thread || acx->thread == cx->thread) + continue; + memset(acx->thread->gcFreeLists, 0, sizeof acx->thread->gcFreeLists); + GSN_CACHE_CLEAR(&acx->thread->gsnCache); + } +#else + /* The thread-unsafe case just has to clear the runtime's GSN cache. */ + GSN_CACHE_CLEAR(&rt->gsnCache); +#endif + +restart: + rt->gcNumber++; + JS_ASSERT(!rt->gcUnscannedArenaStackTop); + JS_ASSERT(rt->gcUnscannedBagSize == 0); + + /* + * Mark phase. + */ + JS_DHashTableEnumerate(&rt->gcRootsHash, gc_root_marker, cx); + if (rt->gcLocksHash) + JS_DHashTableEnumerate(rt->gcLocksHash, gc_lock_marker, cx); + js_MarkAtomState(&rt->atomState, keepAtoms, gc_mark_atom_key_thing, cx); + js_MarkWatchPoints(cx); + js_MarkScriptFilenames(rt, keepAtoms); + js_MarkNativeIteratorStates(cx); + +#if JS_HAS_GENERATORS + genTodoTail = MarkScheduledGenerators(cx); + JS_ASSERT(!*genTodoTail); +#endif + + iter = NULL; + while ((acx = js_ContextIterator(rt, JS_TRUE, &iter)) != NULL) { + /* + * Iterate frame chain and dormant chains. Temporarily tack current + * frame onto the head of the dormant list to ease iteration. + * + * (NB: see comment on this whole "dormant" thing in js_Execute.) + */ + chain = acx->fp; + if (chain) { + JS_ASSERT(!chain->dormantNext); + chain->dormantNext = acx->dormantFrameChain; + } else { + chain = acx->dormantFrameChain; + } + + for (fp = chain; fp; fp = chain = chain->dormantNext) { + do { + js_MarkStackFrame(cx, fp); + } while ((fp = fp->down) != NULL); + } + + /* Cleanup temporary "dormant" linkage. */ + if (acx->fp) + acx->fp->dormantNext = NULL; + + /* Mark other roots-by-definition in acx. */ + GC_MARK(cx, acx->globalObject, "global object"); + MarkWeakRoots(cx, &acx->weakRoots); + if (acx->throwing) { + if (JSVAL_IS_GCTHING(acx->exception)) + GC_MARK(cx, JSVAL_TO_GCTHING(acx->exception), "exception"); + } else { + /* Avoid keeping GC-ed junk stored in JSContext.exception. */ + acx->exception = JSVAL_NULL; + } +#if JS_HAS_LVALUE_RETURN + if (acx->rval2set && JSVAL_IS_GCTHING(acx->rval2)) + GC_MARK(cx, JSVAL_TO_GCTHING(acx->rval2), "rval2"); +#endif + + for (sh = acx->stackHeaders; sh; sh = sh->down) { + METER(rt->gcStats.stackseg++); + METER(rt->gcStats.segslots += sh->nslots); + GC_MARK_JSVALS(cx, sh->nslots, JS_STACK_SEGMENT(sh), "stack"); + } + + if (acx->localRootStack) + js_MarkLocalRoots(cx, acx->localRootStack); + + for (tvr = acx->tempValueRooters; tvr; tvr = tvr->down) { + switch (tvr->count) { + case JSTVU_SINGLE: + if (JSVAL_IS_GCTHING(tvr->u.value)) { + GC_MARK(cx, JSVAL_TO_GCTHING(tvr->u.value), + "tvr->u.value"); + } + break; + case JSTVU_MARKER: + tvr->u.marker(cx, tvr); + break; + case JSTVU_SPROP: + MARK_SCOPE_PROPERTY(cx, tvr->u.sprop); + break; + case JSTVU_WEAK_ROOTS: + MarkWeakRoots(cx, tvr->u.weakRoots); + break; + default: + JS_ASSERT(tvr->count >= 0); + GC_MARK_JSVALS(cx, tvr->count, tvr->u.array, "tvr->u.array"); + } + } + + if (acx->sharpObjectMap.depth > 0) + js_GCMarkSharpMap(cx, &acx->sharpObjectMap); + } + +#ifdef DUMP_CALL_TABLE + js_DumpCallTable(cx); +#endif + + /* + * Mark children of things that caused too deep recursion during above + * marking phase. + */ + ScanDelayedChildren(cx); + +#if JS_HAS_GENERATORS + /* + * Close phase: search and mark part. See comments in + * FindAndMarkObjectsToClose for details. + */ + FindAndMarkObjectsToClose(cx, gckind, genTodoTail); + + /* + * Mark children of things that caused too deep recursion during the + * just-completed marking part of the close phase. + */ + ScanDelayedChildren(cx); +#endif + + JS_ASSERT(!cx->insideGCMarkCallback); + if (rt->gcCallback) { + cx->insideGCMarkCallback = JS_TRUE; + (void) rt->gcCallback(cx, JSGC_MARK_END); + JS_ASSERT(cx->insideGCMarkCallback); + cx->insideGCMarkCallback = JS_FALSE; + } + JS_ASSERT(rt->gcUnscannedBagSize == 0); + + /* Finalize iterator states before the objects they iterate over. */ + CloseIteratorStates(cx); + + /* + * Sweep phase. + * + * Finalize as we sweep, outside of rt->gcLock but with rt->gcRunning set + * so that any attempt to allocate a GC-thing from a finalizer will fail, + * rather than nest badly and leave the unmarked newborn to be swept. + * + * Finalize smaller objects before larger, to guarantee finalization of + * GC-allocated obj->slots after obj. See FreeSlots in jsobj.c. + */ + for (i = 0; i < GC_NUM_FREELISTS; i++) { + arenaList = &rt->gcArenaList[i]; + nbytes = GC_FREELIST_NBYTES(i); + limit = arenaList->lastLimit; + for (a = arenaList->last; a; a = a->prev) { + JS_ASSERT(!a->prevUnscanned); + JS_ASSERT(a->unscannedPages == 0); + firstPage = (uint8 *) FIRST_THING_PAGE(a); + for (offset = 0; offset != limit; offset += nbytes) { + if ((offset & GC_PAGE_MASK) == 0) { + JS_ASSERT(((JSGCPageInfo *)(firstPage + offset))-> + unscannedBitmap == 0); + offset += PAGE_THING_GAP(nbytes); + } + JS_ASSERT(offset < limit); + flagp = a->base + offset / sizeof(JSGCThing); + if (flagp >= firstPage) + flagp += GC_THINGS_SIZE; + flags = *flagp; + if (flags & GCF_MARK) { + *flagp &= ~GCF_MARK; + } else if (!(flags & (GCF_LOCK | GCF_FINAL))) { + /* Call the finalizer with GCF_FINAL ORed into flags. */ + type = flags & GCF_TYPEMASK; + finalizer = gc_finalizers[type]; + if (finalizer) { + thing = (JSGCThing *)(firstPage + offset); + *flagp = (uint8)(flags | GCF_FINAL); + if (type >= GCX_EXTERNAL_STRING) + js_PurgeDeflatedStringCache(rt, (JSString *)thing); + finalizer(cx, thing); + } + + /* Set flags to GCF_FINAL, signifying that thing is free. */ + *flagp = GCF_FINAL; + } + } + limit = GC_THINGS_SIZE; + } + } + + /* + * Sweep the runtime's property tree after finalizing objects, in case any + * had watchpoints referencing tree nodes. Then sweep atoms, which may be + * referenced from dead property ids. + */ + js_SweepScopeProperties(rt); + js_SweepAtomState(&rt->atomState); + + /* + * Sweep script filenames after sweeping functions in the generic loop + * above. In this way when a scripted function's finalizer destroys the + * script and calls rt->destroyScriptHook, the hook can still access the + * script's filename. See bug 323267. + */ + js_SweepScriptFilenames(rt); + + /* + * Free phase. + * Free any unused arenas and rebuild the JSGCThing freelist. + */ + for (i = 0; i < GC_NUM_FREELISTS; i++) { + arenaList = &rt->gcArenaList[i]; + ap = &arenaList->last; + a = *ap; + if (!a) + continue; + + allClear = JS_TRUE; + arenaList->freeList = NULL; + freeList = NULL; + METER(arenaList->stats.nthings = 0); + METER(arenaList->stats.freelen = 0); + + nbytes = GC_FREELIST_NBYTES(i); + limit = arenaList->lastLimit; + do { + METER(size_t nfree = 0); + firstPage = (uint8 *) FIRST_THING_PAGE(a); + for (offset = 0; offset != limit; offset += nbytes) { + if ((offset & GC_PAGE_MASK) == 0) + offset += PAGE_THING_GAP(nbytes); + JS_ASSERT(offset < limit); + flagp = a->base + offset / sizeof(JSGCThing); + if (flagp >= firstPage) + flagp += GC_THINGS_SIZE; + + if (*flagp != GCF_FINAL) { + allClear = JS_FALSE; + METER(++arenaList->stats.nthings); + } else { + thing = (JSGCThing *)(firstPage + offset); + thing->flagp = flagp; + thing->next = freeList; + freeList = thing; + METER(++nfree); + } + } + if (allClear) { + /* + * Forget just assembled free list head for the arena + * and destroy the arena itself. + */ + freeList = arenaList->freeList; + DestroyGCArena(rt, arenaList, ap); + } else { + allClear = JS_TRUE; + arenaList->freeList = freeList; + ap = &a->prev; + METER(arenaList->stats.freelen += nfree); + METER(arenaList->stats.totalfreelen += nfree); + METER(++arenaList->stats.totalarenas); + } + limit = GC_THINGS_SIZE; + } while ((a = *ap) != NULL); + } + + if (rt->gcCallback) + (void) rt->gcCallback(cx, JSGC_FINALIZE_END); +#ifdef DEBUG_srcnotesize + { extern void DumpSrcNoteSizeHist(); + DumpSrcNoteSizeHist(); + printf("GC HEAP SIZE %lu (%lu)\n", + (unsigned long)rt->gcBytes, (unsigned long)rt->gcPrivateBytes); + } +#endif + + JS_LOCK_GC(rt); + + /* + * We want to restart GC if js_GC was called recursively or if any of the + * finalizers called js_RemoveRoot or js_UnlockGCThingRT. + */ + if (rt->gcLevel > 1 || rt->gcPoke) { + rt->gcLevel = 1; + rt->gcPoke = JS_FALSE; + JS_UNLOCK_GC(rt); + goto restart; + } + js_EnablePropertyCache(cx); + rt->gcLevel = 0; + rt->gcLastBytes = rt->gcBytes; + rt->gcRunning = JS_FALSE; + +#ifdef JS_THREADSAFE + /* If we were invoked during a request, pay back the temporary debit. */ + if (requestDebit) + rt->requestCount += requestDebit; + rt->gcThread = NULL; + JS_NOTIFY_GC_DONE(rt); + + /* + * Unlock unless we have GC_LAST_DITCH which requires locked GC on return. + */ + if (gckind != GC_LAST_DITCH) + JS_UNLOCK_GC(rt); +#endif + + /* Execute JSGC_END callback outside the lock. */ + if (rt->gcCallback) { + JSWeakRoots savedWeakRoots; + JSTempValueRooter tvr; + + if (gckind == GC_LAST_DITCH) { + /* + * We allow JSGC_END implementation to force a full GC or allocate + * new GC things. Thus we must protect the weak roots from GC or + * overwrites. + */ + savedWeakRoots = cx->weakRoots; + JS_PUSH_TEMP_ROOT_WEAK_COPY(cx, &savedWeakRoots, &tvr); + JS_KEEP_ATOMS(rt); + JS_UNLOCK_GC(rt); + } + + (void) rt->gcCallback(cx, JSGC_END); + + if (gckind == GC_LAST_DITCH) { + JS_LOCK_GC(rt); + JS_UNKEEP_ATOMS(rt); + JS_POP_TEMP_ROOT(cx, &tvr); + } else if (gckind == GC_LAST_CONTEXT && rt->gcPoke) { + /* + * On shutdown iterate until JSGC_END callback stops creating + * garbage. + */ + goto restart_after_callback; + } + } +} + +void +js_UpdateMallocCounter(JSContext *cx, size_t nbytes) +{ + uint32 *pbytes, bytes; + +#ifdef JS_THREADSAFE + pbytes = &cx->thread->gcMallocBytes; +#else + pbytes = &cx->runtime->gcMallocBytes; +#endif + bytes = *pbytes; + *pbytes = ((uint32)-1 - bytes <= nbytes) ? (uint32)-1 : bytes + nbytes; +} |