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		/*
41		* JS Mark-and-Sweep Garbage Collector.
42		*
43		* This GC allocates only fixed-sized things big enough to contain two words
44		* (pointers) on any host architecture.  It allocates from an arena pool (see
45		* jsarena.h).  It uses an ideally parallel array of flag bytes to hold the
46		* mark bit, finalizer type index, etc.
47		*
48		* XXX swizzle page to freelist for better locality of reference
49		*/
50		#include "jsstddef.h"
51		#include <stdlib.h>     /* for free, called by JS_ARENA_DESTROY */
52		#include <string.h>     /* for memset, called by jsarena.h macros if DEBUG */
53		#include "jstypes.h"
54		#include "jsarena.h" /* Added by JSIFY */
55		#include "jsutil.h" /* Added by JSIFY */
56		#include "jshash.h" /* Added by JSIFY */
57		#include "jsapi.h"
58		#include "jsatom.h"
59		#include "jscntxt.h"
60		#include "jsconfig.h"
61		#include "jsdbgapi.h"
62		#include "jsfun.h"
63		#include "jsgc.h"
64		#include "jsinterp.h"
65		#include "jslock.h"
66		#include "jsnum.h"
67		#include "jsobj.h"
68		#include "jsscope.h"
69		#include "jsscript.h"
70		#include "jsstr.h"
71
72		#if JS_HAS_XML_SUPPORT
73		#include "jsxml.h"
74		#endif
75
76		/*
77		* GC arena sizing depends on amortizing arena overhead using a large number
78		* of things per arena, and on the thing/flags ratio of 8:1 on most platforms.
79		*
80		* On 64-bit platforms, we would have half as many things per arena because
81		* pointers are twice as big, so we double the bytes for things per arena.
82		* This preserves the 1024 byte flags sub-arena size, which relates to the
83		* GC_PAGE_SIZE (see below for why).
84		*/
85		#if JS_BYTES_PER_WORD == 8
86		# define GC_THINGS_SHIFT 14     /* 16KB for things on Alpha, etc. */
87		#else
88		# define GC_THINGS_SHIFT 13     /* 8KB for things on most platforms */
89		#endif
90		#define GC_THINGS_SIZE  JS_BIT(GC_THINGS_SHIFT)
91		#define GC_FLAGS_SIZE   (GC_THINGS_SIZE / sizeof(JSGCThing))
92		#define GC_ARENA_SIZE   (GC_THINGS_SIZE + GC_FLAGS_SIZE)
93
94		/*
95		* A GC arena contains one flag byte for each thing in its heap, and supports
96		* O(1) lookup of a flag given its thing's address.
97		*
98		* To implement this, we take advantage of the thing/flags numerology: given
99		* the 8K bytes worth of GC-things, there are 1K flag bytes.  We mask a thing's
100		* address with ~1023 to find a JSGCPageInfo record at the front of a mythical
101		* "GC page" within the larger 8K thing arena.  That JSGCPageInfo contains a
102		* pointer to the 128 flag bytes corresponding to the things in the page, so we
103		* index into this flags array using the thing's index within its page.
104		*
105		* To align thing pages on 1024-byte boundaries, we must allocate the 9KB of
106		* flags+things arena payload, then find the first 0 mod 1024 boundary after
107		* the first payload address.  That's where things start, with a JSGCPageInfo
108		* taking up the first thing-slot, as usual for 0 mod 1024 byte boundaries.
109		* The effect of this alignment trick is to split the flags into at most 2
110		* discontiguous spans, one before the things and one after (if we're really
111		* lucky, and the arena payload starts on a 0 mod 1024 byte boundary, no need
112		* to split).
113		*
114		* The overhead of this scheme for most platforms is (16+8*(8+1))/(16+9K) or
115		* .95% (assuming 16 byte JSArena header size, and 8 byte JSGCThing size).
116		*
117		* Here's some ASCII art showing an arena:
118		*
119		*   split
120		*     |
121		*     V
122		*  +--+-------+-------+-------+-------+-------+-------+-------+-------+-----+
123		*  |fB|  tp0  |  tp1  |  tp2  |  tp3  |  tp4  |  tp5  |  tp6  |  tp7  | fA  |
124		*  +--+-------+-------+-------+-------+-------+-------+-------+-------+-----+
125		*              ^                                 ^
126		*  tI ---------+                                 |
127		*  tJ -------------------------------------------+
128		*
129		*  - fB are the "before split" flags, fA are the "after split" flags
130		*  - tp0-tp7 are the 8 thing pages
131		*  - thing tI points into tp1, whose flags are below the split, in fB
132		*  - thing tJ points into tp5, clearly above the split
133		*
134		* In general, one of the thing pages will have some of its things' flags on
135		* the low side of the split, and the rest of its things' flags on the high
136		* side.  All the other pages have flags only below or only above.  Therefore
137		* we'll have to test something to decide whether the split divides flags in
138		* a given thing's page.  So we store the split pointer (the pointer to tp0)
139		* in each JSGCPageInfo, along with the flags pointer for the 128 flag bytes
140		* ideally starting, for tp0 things, at the beginning of the arena's payload
141		* (at the start of fB).
142		*
143		* That is, each JSGCPageInfo's flags pointer is 128 bytes from the previous,
144		* or at the start of the arena if there is no previous page in this arena.
145		* Thus these ideal 128-byte flag pages run contiguously from the start of the
146		* arena (right over the split!), and the JSGCPageInfo flags pointers contain
147		* no discontinuities over the split created by the thing pages.  So if, for a
148		* given JSGCPageInfo *pi, we find that
149		*
150		*  pi->flags + ((jsuword)thing % 1024) / sizeof(JSGCThing) >= pi->split
151		*
152		* then we must add GC_THINGS_SIZE to the nominal flags pointer to jump over
153		* all the thing pages that split the flags into two discontiguous spans.
154		*
155		* (If we need to implement card-marking for an incremental GC write barrier,
156		* we can use the low byte of the pi->split pointer as the card-mark, for an
157		* extremely efficient write barrier: when mutating an object obj, just store
158		* a 1 byte at (uint8 *) ((jsuword)obj & ~1023) for little-endian platforms.
159		* When finding flags, we'll of course have to mask split with ~255, but it is
160		* guaranteed to be 1024-byte aligned, so no information is lost by overlaying
161		* the card-mark byte on split's low byte.)
162		*/
163		#define GC_PAGE_SHIFT   10
164		#define GC_PAGE_MASK    ((jsuword) JS_BITMASK(GC_PAGE_SHIFT))
165		#define GC_PAGE_SIZE    JS_BIT(GC_PAGE_SHIFT)
166
167		typedef struct JSGCPageInfo {
168		uint8       *split;
169		uint8       *flags;
170		} JSGCPageInfo;
171
172		#define FIRST_THING_PAGE(a)     (((a)->base + GC_FLAGS_SIZE) & ~GC_PAGE_MASK)
173
174		/*
175		* Given a jsuword page pointer p and a thing size n, return the address of
176		* the first thing in p.  We know that any n not a power of two packs from
177		* the end of the page leaving at least enough room for one JSGCPageInfo, but
178		* not for another thing, at the front of the page (JS_ASSERTs below insist
179		* on this).
180		*
181		* This works because all allocations are a multiple of sizeof(JSGCThing) ==
182		* sizeof(JSGCPageInfo) in size.
183		*/
184		#define FIRST_THING(p,n)        (((n) & ((n) - 1))                            \
185		? (p) + (uint32)(GC_PAGE_SIZE % (n))         \
186		: (p) + (n))
187
188		static JSGCThing *
189		gc_new_arena(JSArenaPool *pool, size_t nbytes)
190	2494	{
191	2494	uint8 *flagp, *split, *pagep, *limit;
192	2494	JSArena *a;
193	2494	jsuword p;
194	2494	JSGCThing *thing;
195	2494	JSGCPageInfo *pi;
196
197		/* Use JS_ArenaAllocate to grab another 9K-net-size hunk of space. */
198	2494	flagp = (uint8 *) JS_ArenaAllocate(pool, GC_ARENA_SIZE);
199	2494	if (!flagp)
200	0	return NULL;
201	2494	a = pool->current;
202
203		/* Reset a->avail to start at the flags split, aka the first thing page. */
204	2494	p = FIRST_THING_PAGE(a);
205	2494	split = pagep = (uint8 *) p;
206	2494	a->avail = FIRST_THING(p, nbytes);
207	2494	JS_ASSERT(a->avail >= p + sizeof(JSGCPageInfo));
208	2494	thing = (JSGCThing *) a->avail;
209		JS_ArenaCountAllocation(pool, a->avail - p);
210	2494	a->avail += nbytes;
211
212		/* Initialize the JSGCPageInfo records at the start of every thing page. */
213	2494	limit = pagep + GC_THINGS_SIZE;
214	19952	do {
215	19952	pi = (JSGCPageInfo *) pagep;
216	19952	pi->split = split;
217	19952	pi->flags = flagp;
218	19952	flagp += GC_PAGE_SIZE >> (GC_THINGS_SHIFT -  GC_PAGE_SHIFT);
219	19952	pagep += GC_PAGE_SIZE;
220	19952	} while (pagep < limit);
221	2494	return thing;
222		}
223
224		uint8 *
225		js_GetGCThingFlags(void *thing)
226	1049446	{
227	1049446	JSGCPageInfo *pi;
228	1049446	uint8 *flagp;
229
230	1049446	pi = (JSGCPageInfo *) ((jsuword)thing & ~GC_PAGE_MASK);
231	1049446	flagp = pi->flags + ((jsuword)thing & GC_PAGE_MASK) / sizeof(JSGCThing);
232	1049446	if (flagp >= pi->split)
233	561095	flagp += GC_THINGS_SIZE;
234	1049446	return flagp;
235		}
236
237		JSBool
238		js_IsAboutToBeFinalized(JSContext *cx, void *thing)
239	0	{
240	0	uint8 flags = *js_GetGCThingFlags(thing);
241
242	0	return !(flags & (GCF_MARK | GCF_LOCK | GCF_FINAL));
243		}
244
245		typedef void (*GCFinalizeOp)(JSContext *cx, JSGCThing *thing);
246
247		#ifndef DEBUG
248		# define js_FinalizeDouble       NULL
249		#endif
250
251		#if !JS_HAS_XML_SUPPORT
252		# define js_FinalizeXMLNamespace NULL
253		# define js_FinalizeXMLQName     NULL
254		# define js_FinalizeXML          NULL
255		#endif
256
257		static GCFinalizeOp gc_finalizers[GCX_NTYPES] = {
258		(GCFinalizeOp) js_FinalizeObject,           /* GCX_OBJECT */
259		(GCFinalizeOp) js_FinalizeString,           /* GCX_STRING */
260		(GCFinalizeOp) js_FinalizeDouble,           /* GCX_DOUBLE */
261		(GCFinalizeOp) js_FinalizeString,           /* GCX_MUTABLE_STRING */
262		NULL,                                       /* GCX_PRIVATE */
263		(GCFinalizeOp) js_FinalizeXMLNamespace,     /* GCX_NAMESPACE */
264		(GCFinalizeOp) js_FinalizeXMLQName,         /* GCX_QNAME */
265		(GCFinalizeOp) js_FinalizeXML,              /* GCX_XML */
266		NULL,                                       /* GCX_EXTERNAL_STRING */
267		NULL,
268		NULL,
269		NULL,
270		NULL,
271		NULL,
272		NULL,
273		NULL
274		};
275
276		#ifdef GC_MARK_DEBUG
277		static const char newborn_external_string[] = "newborn external string";
278
279		static const char *gc_typenames[GCX_NTYPES] = {
280		"newborn object",
281		"newborn string",
282		"newborn double",
283		"newborn mutable string",
284		"newborn private",
285		"newborn Namespace",
286		"newborn QName",
287		"newborn XML",
288		newborn_external_string,
289		newborn_external_string,
290		newborn_external_string,
291		newborn_external_string,
292		newborn_external_string,
293		newborn_external_string,
294		newborn_external_string,
295		newborn_external_string
296		};
297		#endif
298
299		intN
300		js_ChangeExternalStringFinalizer(JSStringFinalizeOp oldop,
301		JSStringFinalizeOp newop)
302	0	{
303	0	uintN i;
304
305	0	for (i = GCX_EXTERNAL_STRING; i < GCX_NTYPES; i++) {
306	0	if (gc_finalizers[i] == (GCFinalizeOp) oldop) {
307	0	gc_finalizers[i] = (GCFinalizeOp) newop;
308	0	return (intN) i;
309		}
310		}
311	0	return -1;
312		}
313
314		#ifdef JS_GCMETER
315		#define METER(x) x
316		#else
317		#define METER(x) /* nothing */
318		#endif
319
320		/* Initial size of the gcRootsHash table (SWAG, small enough to amortize). */
321		#define GC_ROOTS_SIZE   256
322		#define GC_FINALIZE_LEN 1024
323
324		JSBool
325		js_InitGC(JSRuntime *rt, uint32 maxbytes)
326	16	{
327	16	uintN i;
328
329	16	JS_ASSERT(sizeof(JSGCThing) == sizeof(JSGCPageInfo));
330	16	JS_ASSERT(sizeof(JSGCThing) >= sizeof(JSObject));
331	16	JS_ASSERT(sizeof(JSGCThing) >= sizeof(JSString));
332	16	JS_ASSERT(sizeof(JSGCThing) >= sizeof(jsdouble));
333	16	JS_ASSERT(GC_FLAGS_SIZE >= GC_PAGE_SIZE);
334	16	JS_ASSERT(sizeof(JSStackHeader) >= 2 * sizeof(jsval));
335
336	176	for (i = 0; i < GC_NUM_FREELISTS; i++)
337	160	JS_InitArenaPool(&rt->gcArenaPool[i], "gc-arena", GC_ARENA_SIZE, 1);
338	16	if (!JS_DHashTableInit(&rt->gcRootsHash, JS_DHashGetStubOps(), NULL,
339		sizeof(JSGCRootHashEntry), GC_ROOTS_SIZE)) {
340	0	rt->gcRootsHash.ops = NULL;
341	0	return JS_FALSE;
342		}
343	16	rt->gcLocksHash = NULL;     /* create lazily */
344
345		/*
346		* Separate gcMaxMallocBytes from gcMaxBytes but initialize to maxbytes
347		* for default backward API compatibility.
348		*/
349	16	rt->gcMaxBytes = rt->gcMaxMallocBytes = maxbytes;
350	16	return JS_TRUE;
351		}
352
353		#ifdef JS_GCMETER
354		JS_FRIEND_API(void)
355		js_DumpGCStats(JSRuntime *rt, FILE *fp)
356		{
357		uintN i;
358
359		fprintf(fp, "\nGC allocation statistics:\n");
360
361		#define UL(x)       ((unsigned long)(x))
362		#define ULSTAT(x)   UL(rt->gcStats.x)
363		fprintf(fp, "     public bytes allocated: %lu\n", UL(rt->gcBytes));
364		fprintf(fp, "    private bytes allocated: %lu\n", UL(rt->gcPrivateBytes));
365		fprintf(fp, "             alloc attempts: %lu\n", ULSTAT(alloc));
366		for (i = 0; i < GC_NUM_FREELISTS; i++) {
367		fprintf(fp, "       GC freelist %u length: %lu\n",
368		i, ULSTAT(freelen[i]));
369		fprintf(fp, " recycles via GC freelist %u: %lu\n",
370		i, ULSTAT(recycle[i]));
371		}
372		fprintf(fp, "allocation retries after GC: %lu\n", ULSTAT(retry));
373		fprintf(fp, "        allocation failures: %lu\n", ULSTAT(fail));
374		fprintf(fp, "         things born locked: %lu\n", ULSTAT(lockborn));
375		fprintf(fp, "           valid lock calls: %lu\n", ULSTAT(lock));
376		fprintf(fp, "         valid unlock calls: %lu\n", ULSTAT(unlock));
377		fprintf(fp, "       mark recursion depth: %lu\n", ULSTAT(depth));
378		fprintf(fp, "     maximum mark recursion: %lu\n", ULSTAT(maxdepth));
379		fprintf(fp, "     mark C recursion depth: %lu\n", ULSTAT(cdepth));
380		fprintf(fp, "   maximum mark C recursion: %lu\n", ULSTAT(maxcdepth));
381		fprintf(fp, "     mark C stack overflows: %lu\n", ULSTAT(dswmark));
382		fprintf(fp, "   mark DSW recursion depth: %lu\n", ULSTAT(dswdepth));
383		fprintf(fp, " maximum mark DSW recursion: %lu\n", ULSTAT(maxdswdepth));
384		fprintf(fp, "  mark DSW up-tree movement: %lu\n", ULSTAT(dswup));
385		fprintf(fp, "DSW up-tree obj->slot steps: %lu\n", ULSTAT(dswupstep));
386		fprintf(fp, "   maximum GC nesting level: %lu\n", ULSTAT(maxlevel));
387		fprintf(fp, "potentially useful GC calls: %lu\n", ULSTAT(poke));
388		fprintf(fp, "           useless GC calls: %lu\n", ULSTAT(nopoke));
389		fprintf(fp, "  thing arenas freed so far: %lu\n", ULSTAT(afree));
390		fprintf(fp, "     stack segments scanned: %lu\n", ULSTAT(stackseg));
391		fprintf(fp, "stack segment slots scanned: %lu\n", ULSTAT(segslots));
392		#undef UL
393		#undef US
394
395		#ifdef JS_ARENAMETER
396		JS_DumpArenaStats(fp);
397		#endif
398		}
399		#endif
400
401		#ifdef DEBUG
402		JS_STATIC_DLL_CALLBACK(JSDHashOperator)
403		js_root_printer(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 i, void *arg)
404		{
405		uint32 *leakedroots = (uint32 *)arg;
406		JSGCRootHashEntry *rhe = (JSGCRootHashEntry *)hdr;
407
408		(*leakedroots)++;
409		fprintf(stderr,
410		"JS engine warning: leaking GC root \'%s\' at %p\n",
411		rhe->name ? (char *)rhe->name : "", rhe->root);
412
413		return JS_DHASH_NEXT;
414		}
415		#endif
416
417		void
418		js_FinishGC(JSRuntime *rt)
419	16	{
420	16	uintN i;
421
422		#ifdef JS_ARENAMETER
423		JS_DumpArenaStats(stdout);
424		#endif
425		#ifdef JS_GCMETER
426		js_DumpGCStats(rt, stdout);
427		#endif
428	176	for (i = 0; i < GC_NUM_FREELISTS; i++) {
429	160	JS_FinishArenaPool(&rt->gcArenaPool[i]);
430	160	rt->gcFreeList[i] = NULL;
431		}
432	16	JS_ArenaFinish();
433
434	16	if (rt->gcRootsHash.ops) {
435		#ifdef DEBUG
436		uint32 leakedroots = 0;
437
438		/* Warn (but don't assert) debug builds of any remaining roots. */
439		JS_DHashTableEnumerate(&rt->gcRootsHash, js_root_printer,
440		&leakedroots);
441		if (leakedroots > 0) {
442		if (leakedroots == 1) {
443		fprintf(stderr,
444		"JS engine warning: 1 GC root remains after destroying the JSRuntime.\n"
445		"                   This root may point to freed memory. Objects reachable\n"
446		"                   through it have not been finalized.\n");
447		} else {
448		fprintf(stderr,
449		"JS engine warning: %lu GC roots remain after destroying the JSRuntime.\n"
450		"                   These roots may point to freed memory. Objects reachable\n"
451		"                   through them have not been finalized.\n",
452		(unsigned long) leakedroots);
453		}
454		}
455		#endif
456
457	16	JS_DHashTableFinish(&rt->gcRootsHash);
458	16	rt->gcRootsHash.ops = NULL;
459		}
460	16	if (rt->gcLocksHash) {
461	0	JS_DHashTableDestroy(rt->gcLocksHash);
462	0	rt->gcLocksHash = NULL;
463		}
464		}
465
466		JSBool
467		js_AddRoot(JSContext *cx, void *rp, const char *name)
468	22011	{
469	22011	JSBool ok = js_AddRootRT(cx->runtime, rp, name);
470	22011	if (!ok)
471	0	JS_ReportOutOfMemory(cx);
472	22011	return ok;
473		}
474
475		JSBool
476		js_AddRootRT(JSRuntime *rt, void *rp, const char *name)
477	22011	{
478	22011	JSBool ok;
479	22011	JSGCRootHashEntry *rhe;
480
481		/*
482		* Due to the long-standing, but now removed, use of rt->gcLock across the
483		* bulk of js_GC, API users have come to depend on JS_AddRoot etc. locking
484		* properly with a racing GC, without calling JS_AddRoot from a request.
485		* We have to preserve API compatibility here, now that we avoid holding
486		* rt->gcLock across the mark phase (including the root hashtable mark).
487		*
488		* If the GC is running and we're called on another thread, wait for this
489		* GC activation to finish.  We can safely wait here (in the case where we
490		* are called within a request on another thread's context) without fear
491		* of deadlock because the GC doesn't set rt->gcRunning until after it has
492		* waited for all active requests to end.
493		*/
494	22011	JS_LOCK_GC(rt);
495		#ifdef JS_THREADSAFE
496		JS_ASSERT(!rt->gcRunning || rt->gcLevel > 0);
497		if (rt->gcRunning && rt->gcThread != js_CurrentThreadId()) {
498		do {
499		JS_AWAIT_GC_DONE(rt);
500		} while (rt->gcLevel > 0);
501		}
502		#endif
503	22011	rhe = (JSGCRootHashEntry *) JS_DHashTableOperate(&rt->gcRootsHash, rp,
504		JS_DHASH_ADD);
505	22011	if (rhe) {
506	22011	rhe->root = rp;
507	22011	rhe->name = name;
508	22011	ok = JS_TRUE;
509		} else {
510	0	ok = JS_FALSE;
511		}
512	22011	JS_UNLOCK_GC(rt);
513	22011	return ok;
514		}
515
516		JSBool
517		js_RemoveRoot(JSRuntime *rt, void *rp)
518	22011	{
519		/*
520		* Due to the JS_RemoveRootRT API, we may be called outside of a request.
521		* Same synchronization drill as above in js_AddRoot.
522		*/
523	22011	JS_LOCK_GC(rt);
524		#ifdef JS_THREADSAFE
525		JS_ASSERT(!rt->gcRunning || rt->gcLevel > 0);
526		if (rt->gcRunning && rt->gcThread != js_CurrentThreadId()) {
527		do {
528		JS_AWAIT_GC_DONE(rt);
529		} while (rt->gcLevel > 0);
530		}
531		#endif
532	22011	(void) JS_DHashTableOperate(&rt->gcRootsHash, rp, JS_DHASH_REMOVE);
533	22011	rt->gcPoke = JS_TRUE;
534	22011	JS_UNLOCK_GC(rt);
535	22011	return JS_TRUE;
536		}
537
538		#ifdef DEBUG_brendan
539		#define NGCHIST 64
540
541		static struct GCHist {
542		JSBool      lastDitch;
543		JSGCThing   *freeList;
544		} gchist[NGCHIST];
545
546		unsigned gchpos;
547		#endif
548
549		void *
550		js_NewGCThing(JSContext *cx, uintN flags, size_t nbytes)
551	782858	{
552	782858	JSBool tried_gc;
553	782858	JSRuntime *rt;
554	782858	size_t nflags;
555	782858	uintN i;
556	782858	JSGCThing *thing, **flp;
557	782858	uint8 *flagp;
558	782858	JSLocalRootStack *lrs;
559	782858	uint32 *bytesptr;
560
561	782858	rt = cx->runtime;
562	782858	JS_LOCK_GC(rt);
563	782858	JS_ASSERT(!rt->gcRunning);
564	782858	if (rt->gcRunning) {
565		METER(rt->gcStats.finalfail++);
566	0	JS_UNLOCK_GC(rt);
567	0	return NULL;
568		}
569
570		#ifdef TOO_MUCH_GC
571		#ifdef WAY_TOO_MUCH_GC
572		rt->gcPoke = JS_TRUE;
573		#endif
574		js_GC(cx, GC_KEEP_ATOMS | GC_ALREADY_LOCKED);
575		tried_gc = JS_TRUE;
576		#else
577	782858	tried_gc = JS_FALSE;
578		#endif
579
580		METER(rt->gcStats.alloc++);
581	782858	nbytes = JS_ROUNDUP(nbytes, sizeof(JSGCThing));
582	782858	nflags = nbytes / sizeof(JSGCThing);
583	782858	i = GC_FREELIST_INDEX(nbytes);
584	782858	flp = &rt->gcFreeList[i];
585
586		retry:
587	782858	thing = *flp;
588	782858	if (thing) {
589	0	*flp = thing->next;
590	0	flagp = thing->flagp;
591		METER(rt->gcStats.freelen[i]--);
592		METER(rt->gcStats.recycle[i]++);
593		} else {
594	782858	if (rt->gcBytes < rt->gcMaxBytes &&
595		(tried_gc || rt->gcMallocBytes < rt->gcMaxMallocBytes))
596		{
597		/*
598		* Inline form of JS_ARENA_ALLOCATE adapted to truncate the current
599		* arena's limit to a GC_PAGE_SIZE boundary, and to skip over every
600		* GC_PAGE_SIZE-byte-aligned thing (which is actually not a thing,
601		* it's a JSGCPageInfo record).
602		*/
603	782858	JSArenaPool *pool = &rt->gcArenaPool[i];
604	782858	JSArena *a = pool->current;
605	782858	jsuword p = a->avail;
606	782858	jsuword q = p + nbytes;
607
608	782858	if (q > (a->limit & ~GC_PAGE_MASK)) {
609	2494	thing = gc_new_arena(pool, nbytes);
610		} else {
611	780364	if ((p & GC_PAGE_MASK) == 0) {
612		/* Beware, p points to a JSGCPageInfo record! */
613	16848	p = FIRST_THING(p, nbytes);
614	16848	q = p + nbytes;
615		JS_ArenaCountAllocation(pool, p & GC_PAGE_MASK);
616		}
617	780364	a->avail = q;
618	780364	thing = (JSGCThing *)p;
619		}
620		JS_ArenaCountAllocation(pool, nbytes);
621		}
622
623		/*
624		* Consider doing a "last ditch" GC if thing couldn't be allocated.
625		*
626		* Keep rt->gcLock across the call into js_GC so we don't starve and
627		* lose to racing threads who deplete the heap just after js_GC has
628		* replenished it (or has synchronized with a racing GC that collected
629		* a bunch of garbage).  This unfair scheduling can happen on certain
630		* operating systems.  For the gory details, see Mozilla bug 162779
631		* (http://bugzilla.mozilla.org/show_bug.cgi?id=162779).
632		*/
633	782858	if (!thing) {
634	0	if (!tried_gc) {
635	0	rt->gcPoke = JS_TRUE;
636	0	js_GC(cx, GC_KEEP_ATOMS | GC_ALREADY_LOCKED);
637	0	tried_gc = JS_TRUE;
638		METER(rt->gcStats.retry++);
639	0	goto retry;
640		}
641	782858	goto fail;
642		}
643
644		/* Find the flags pointer given thing's address. */
645	782858	flagp = js_GetGCThingFlags(thing);
646		}
647
648	782858	lrs = cx->localRootStack;
649	782858	if (lrs) {
650		/*
651		* If we're in a local root scope, don't set cx->newborn[type] at all,
652		* to avoid entraining garbage from it for an unbounded amount of time
653		* on this context.  A caller will leave the local root scope and pop
654		* this reference, allowing thing to be GC'd if it has no other refs.
655		* See JS_EnterLocalRootScope and related APIs.
656		*/
657	1136	if (js_PushLocalRoot(cx, lrs, (jsval) thing) < 0) {
658		/*
659		* When we fail for a thing allocated through the tail of
660		* the last arena, thing's flag byte is not initialized. So
661		* to prevent GC accessing the uninitialized flags during
662		* the finalization, we always mark the thing as final. See
663		* bug 337407.
664		*/
665	0	*flagp = GCF_FINAL;
666	0	goto fail;
667		}
668		} else {
669		/*
670		* No local root scope, so we're stuck with the old, fragile model of
671		* depending on a pigeon-hole newborn per type per context.
672		*/
673	781722	cx->newborn[flags & GCF_TYPEMASK] = thing;
674		}
675
676		/* We can't fail now, so update flags and rt->gc{,Private}Bytes. */
677	782858	*flagp = (uint8)flags;
678	782858	bytesptr = ((flags & GCF_TYPEMASK) == GCX_PRIVATE)
679		? &rt->gcPrivateBytes
680		: &rt->gcBytes;
681	782858	*bytesptr += nbytes + nflags;
682
683		/*
684		* Clear thing before unlocking in case a GC run is about to scan it,
685		* finding it via cx->newborn[].
686		*/
687	782858	thing->next = NULL;
688	782858	thing->flagp = NULL;
689		#ifdef DEBUG_brendan
690		gchist[gchpos].lastDitch = tried_gc;
691		gchist[gchpos].freeList = *flp;
692		if (++gchpos == NGCHIST)
693		gchpos = 0;
694		#endif
695		METER(if (flags & GCF_LOCK) rt->gcStats.lockborn++);
696	782858	JS_UNLOCK_GC(rt);
697	782858	return thing;
698
699		fail:
700		METER(rt->gcStats.fail++);
701	0	JS_UNLOCK_GC(rt);
702	0	JS_ReportOutOfMemory(cx);
703	0	return NULL;
704		}
705
706		JSBool
707		js_LockGCThing(JSContext *cx, void *thing)
708	0	{
709	0	JSBool ok = js_LockGCThingRT(cx->runtime, thing);
710	0	if (!ok)
711	0	JS_ReportOutOfMemory(cx);
712	0	return ok;
713		}
714
715		/*
716		* Deep GC-things can't be locked just by setting the GCF_LOCK bit, because
717		* their descendants must be marked by the GC.  To find them during the mark
718		* phase, they are added to rt->gcLocksHash, which is created lazily.
719		*
720		* NB: we depend on the order of GC-thing type indexes here!
721		*/
722		#define GC_TYPE_IS_STRING(t)    ((t) == GCX_STRING ||                         \
723		(t) >= GCX_EXTERNAL_STRING)
724		#define GC_TYPE_IS_XML(t)       ((unsigned)((t) - GCX_NAMESPACE) <=           \
725		(unsigned)(GCX_XML - GCX_NAMESPACE))
726		#define GC_TYPE_IS_DEEP(t)      ((t) == GCX_OBJECT || GC_TYPE_IS_XML(t))
727
728		#define IS_DEEP_STRING(t,o)     (GC_TYPE_IS_STRING(t) &&                      \
729		JSSTRING_IS_DEPENDENT((JSString *)(o)))
730
731		#define GC_THING_IS_DEEP(t,o)   (GC_TYPE_IS_DEEP(t) || IS_DEEP_STRING(t, o))
732
733		JSBool
734		js_LockGCThingRT(JSRuntime *rt, void *thing)
735	0	{
736	0	JSBool ok, deep;
737	0	uint8 *flagp, flags, lock, type;
738	0	JSGCLockHashEntry *lhe;
739
740	0	ok = JS_TRUE;
741	0	if (!thing)
742	0	return ok;
743
744	0	flagp = js_GetGCThingFlags(thing);
745
746	0	JS_LOCK_GC(rt);
747	0	flags = *flagp;
748	0	lock = (flags & GCF_LOCK);
749	0	type = (flags & GCF_TYPEMASK);
750	0	deep = GC_THING_IS_DEEP(type, thing);
751
752		/*
753		* Avoid adding a rt->gcLocksHash entry for shallow things until someone
754		* nests a lock -- then start such an entry with a count of 2, not 1.
755		*/
756	0	if (lock || deep) {
757	0	if (!rt->gcLocksHash) {
758	0	rt->gcLocksHash =
759		JS_NewDHashTable(JS_DHashGetStubOps(), NULL,
760		sizeof(JSGCLockHashEntry),
761		GC_ROOTS_SIZE);
762	0	if (!rt->gcLocksHash) {
763	0	ok = JS_FALSE;
764	0	goto done;
765		}
766	0	} else if (lock == 0) {
767		#ifdef DEBUG
768		JSDHashEntryHdr *hdr =
769		JS_DHashTableOperate(rt->gcLocksHash, thing,
770		JS_DHASH_LOOKUP);
771		JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(hdr));
772		#endif
773		}
774
775	0	lhe = (JSGCLockHashEntry *)
776		JS_DHashTableOperate(rt->gcLocksHash, thing, JS_DHASH_ADD);
777	0	if (!lhe) {
778	0	ok = JS_FALSE;
779	0	goto done;
780		}
781	0	if (!lhe->thing) {
782	0	lhe->thing = thing;
783	0	lhe->count = deep ? 1 : 2;
784		} else {
785	0	JS_ASSERT(lhe->count >= 1);
786	0	lhe->count++;
787		}
788		}
789
790	0	*flagp = (uint8)(flags | GCF_LOCK);
791		METER(rt->gcStats.lock++);
792	0	ok = JS_TRUE;
793		done:
794	0	JS_UNLOCK_GC(rt);
795	0	return ok;
796		}
797
798		JSBool
799		js_UnlockGCThingRT(JSRuntime *rt, void *thing)
800	64	{
801	64	uint8 *flagp, flags;
802	64	JSGCLockHashEntry *lhe;
803
804	64	if (!thing)
805	0	return JS_TRUE;
806
807	64	flagp = js_GetGCThingFlags(thing);
808	64	JS_LOCK_GC(rt);
809	64	flags = *flagp;
810
811	64	if (flags & GCF_LOCK) {
812	64	if (!rt->gcLocksHash ||
813		(lhe = (JSGCLockHashEntry *)
814		JS_DHashTableOperate(rt->gcLocksHash, thing,
815		JS_DHASH_LOOKUP),
816		JS_DHASH_ENTRY_IS_FREE(&lhe->hdr))) {
817		/* Shallow GC-thing with an implicit lock count of 1. */
818	0	JS_ASSERT(!GC_THING_IS_DEEP(flags & GCF_TYPEMASK, thing));
819		} else {
820		/* Basis or nested unlock of a deep thing, or nested of shallow. */
821	0	if (--lhe->count != 0)
822	0	goto out;
823	0	JS_DHashTableOperate(rt->gcLocksHash, thing, JS_DHASH_REMOVE);
824		}
825	64	*flagp = (uint8)(flags & ~GCF_LOCK);
826		}
827
828	64	rt->gcPoke = JS_TRUE;
829		out:
830		METER(rt->gcStats.unlock++);
831	64	JS_UNLOCK_GC(rt);
832	64	return JS_TRUE;
833		}
834
835		#ifdef GC_MARK_DEBUG
836
837		#include <stdio.h>
838		#include "jsprf.h"
839
840		JS_FRIEND_DATA(FILE *) js_DumpGCHeap;
841		JS_EXPORT_DATA(void *) js_LiveThingToFind;
842
843		#ifdef HAVE_XPCONNECT
844		#include "dump_xpc.h"
845		#endif
846
847		static const char *
848		gc_object_class_name(void* thing)
849		{
850		uint8 *flagp = js_GetGCThingFlags(thing);
851		const char *className = "";
852		static char depbuf[32];
853
854		switch (*flagp & GCF_TYPEMASK) {
855		case GCX_OBJECT: {
856		JSObject  *obj = (JSObject *)thing;
857		JSClass   *clasp = JSVAL_TO_PRIVATE(obj->slots[JSSLOT_CLASS]);
858		className = clasp->name;
859		#ifdef HAVE_XPCONNECT
860		if (clasp->flags & JSCLASS_PRIVATE_IS_NSISUPPORTS) {
861		jsval privateValue = obj->slots[JSSLOT_PRIVATE];
862
863		JS_ASSERT(clasp->flags & JSCLASS_HAS_PRIVATE);
864		if (!JSVAL_IS_VOID(privateValue)) {
865		void  *privateThing = JSVAL_TO_PRIVATE(privateValue);
866		const char *xpcClassName = GetXPCObjectClassName(privateThing);
867
868		if (xpcClassName)
869		className = xpcClassName;
870		}
871		}
872		#endif
873		break;
874		}
875
876		case GCX_STRING:
877		case GCX_MUTABLE_STRING: {
878		JSString *str = (JSString *)thing;
879		if (JSSTRING_IS_DEPENDENT(str)) {
880		JS_snprintf(depbuf, sizeof depbuf, "start:%u, length:%u",
881		JSSTRDEP_START(str), JSSTRDEP_LENGTH(str));
882		className = depbuf;
883		} else {
884		className = "string";
885		}
886		break;
887		}
888
889		case GCX_DOUBLE:
890		className = "double";
891		break;
892		}
893
894		return className;
895		}
896
897		static void
898		gc_dump_thing(JSGCThing *thing, uint8 flags, GCMarkNode *prev, FILE *fp)
899		{
900		GCMarkNode *next = NULL;
901		char *path = NULL;
902
903		while (prev) {
904		next = prev;
905		prev = prev->prev;
906		}
907		while (next) {
908		uint8 nextFlags = *js_GetGCThingFlags(next->thing);
909		if ((nextFlags & GCF_TYPEMASK) == GCX_OBJECT) {
910		path = JS_sprintf_append(path, "%s(%s @ 0x%08p).",
911		next->name,
912		gc_object_class_name(next->thing),
913		(JSObject*)next->thing);
914		} else {
915		path = JS_sprintf_append(path, "%s(%s).",
916		next->name,
917		gc_object_class_name(next->thing));
918		}
919		next = next->next;
920		}
921		if (!path)
922		return;
923
924		fprintf(fp, "%08lx ", (long)thing);
925		switch (flags & GCF_TYPEMASK) {
926		case GCX_OBJECT:
927		{
928		JSObject  *obj = (JSObject *)thing;
929		jsval     privateValue = obj->slots[JSSLOT_PRIVATE];
930		void      *privateThing = JSVAL_IS_VOID(privateValue)
931		? NULL
932		: JSVAL_TO_PRIVATE(privateValue);
933		const char *className = gc_object_class_name(thing);
934		fprintf(fp, "object %8p %s", privateThing, className);
935		break;
936		}
937		#if JS_HAS_XML_SUPPORT
938		case GCX_NAMESPACE:
939		{
940		JSXMLNamespace *ns = (JSXMLNamespace *)thing;
941		fprintf(fp, "namespace %s:%s",
942		JS_GetStringBytes(ns->prefix), JS_GetStringBytes(ns->uri));
943		break;
944		}
945		case GCX_QNAME:
946		{
947		JSXMLQName *qn = (JSXMLQName *)thing;
948		fprintf(fp, "qname %s(%s):%s",
949		JS_GetStringBytes(qn->prefix), JS_GetStringBytes(qn->uri),
950		JS_GetStringBytes(qn->localName));
951		break;
952		}
953		case GCX_XML:
954		{
955		extern const char *js_xml_class_str[];
956		JSXML *xml = (JSXML *)thing;
957		fprintf(fp, "xml %8p %s", xml, js_xml_class_str[xml->xml_class]);
958		break;
959		}
960		#endif
961		case GCX_DOUBLE:
962		fprintf(fp, "double %g", *(jsdouble *)thing);
963		break;
964		case GCX_PRIVATE:
965		fprintf(fp, "private %8p", (void *)thing);
966		break;
967		default:
968		fprintf(fp, "string %s", JS_GetStringBytes((JSString *)thing));
969		break;
970		}
971		fprintf(fp, " via %s\n", path);
972		free(path);
973		}
974
975		#endif /* !GC_MARK_DEBUG */
976
977		static void
978		gc_mark_atom_key_thing(void *thing, void *arg)
979	15664	{
980	15664	JSContext *cx = (JSContext *) arg;
981
982	15664	GC_MARK(cx, thing, "atom", NULL);
983		}
984
985		void
986		js_MarkAtom(JSContext *cx, JSAtom *atom, void *arg)
987	24085	{
988	24085	jsval key;
989
990	24085	if (atom->flags & ATOM_MARK)
991	332	return;
992	23753	atom->flags |= ATOM_MARK;
993	23753	key = ATOM_KEY(atom);
994	23753	if (JSVAL_IS_GCTHING(key)) {
995		#ifdef GC_MARK_DEBUG
996		char name[32];
997
998		if (JSVAL_IS_STRING(key)) {
999		JS_snprintf(name, sizeof name, "'%s'",
1000		JS_GetStringBytes(JSVAL_TO_STRING(key)));
1001		} else {
1002		JS_snprintf(name, sizeof name, "<%x>", key);
1003		}
1004		#endif
1005	23737	GC_MARK(cx, JSVAL_TO_GCTHING(key), name, arg);
1006		}
1007	23753	if (atom->flags & ATOM_HIDDEN)
1008	1344	js_MarkAtom(cx, atom->entry.value, arg);
1009		}
1010
1011		/*
1012		* These macros help avoid passing the GC_MARK_DEBUG-only |arg| parameter
1013		* during recursive calls when GC_MARK_DEBUG is not defined.
1014		*/
1015		#ifdef GC_MARK_DEBUG
1016		# define UNMARKED_GC_THING_FLAGS(thing, arg)                                  \
1017		UnmarkedGCThingFlags(thing, arg)
1018		# define NEXT_UNMARKED_GC_THING(vp, end, thingp, flagpp, arg)                 \
1019		NextUnmarkedGCThing(vp, end, thingp, flagpp, arg)
1020		# define MARK_GC_THING(cx, thing, flagp, arg)                                 \
1021		MarkGCThing(cx, thing, flagp, arg)
1022		# define CALL_GC_THING_MARKER(marker, cx, thing, arg)                         \
1023		marker(cx, thing, arg)
1024		#else
1025		# define UNMARKED_GC_THING_FLAGS(thing, arg)                                  \
1026		UnmarkedGCThingFlags(thing)
1027		# define NEXT_UNMARKED_GC_THING(vp, end, thingp, flagpp, arg)                 \
1028		NextUnmarkedGCThing(vp, end, thingp, flagpp)
1029		# define MARK_GC_THING(cx, thing, flagp, arg)                                 \
1030		MarkGCThing(cx, thing, flagp)
1031		# define CALL_GC_THING_MARKER(marker, cx, thing, arg)                         \
1032		marker(cx, thing, NULL)
1033		#endif
1034
1035		static uint8 *
1036		UNMARKED_GC_THING_FLAGS(void *thing, void *arg)
1037	151669	{
1038	151669	uint8 flags, *flagp;
1039
1040	151669	if (!thing)
1041	143	return NULL;
1042
1043	151526	flagp = js_GetGCThingFlags(thing);
1044	151526	flags = *flagp;
1045	151526	JS_ASSERT(flags != GCF_FINAL);
1046		#ifdef GC_MARK_DEBUG
1047		if (js_LiveThingToFind == thing)
1048		gc_dump_thing(thing, flags, arg, stderr);
1049		#endif
1050
1051	151526	if (flags & GCF_MARK)
1052	81495	return NULL;
1053
1054	70031	return flagp;
1055		}
1056
1057		static jsval *
1058		NEXT_UNMARKED_GC_THING(jsval *vp, jsval *end, void **thingp, uint8 **flagpp,
1059		void *arg)
1060	39335	{
1061	39335	jsval v;
1062	39335	void *thing;
1063	39335	uint8 *flagp;
1064
1065	237781	while (vp < end) {
1066	220366	v = *vp;
1067	220366	if (JSVAL_IS_GCTHING(v)) {
1068	71971	thing = JSVAL_TO_GCTHING(v);
1069	71971	flagp = UNMARKED_GC_THING_FLAGS(thing, arg);
1070	71971	if (flagp) {
1071	21920	*thingp = thing;
1072	21920	*flagpp = flagp;
1073	21920	return vp;
1074		}
1075		}
1076	198446	vp++;
1077		}
1078	17415	return NULL;
1079		}
1080
1081		static void
1082		DeutschSchorrWaite(JSContext *cx, void *thing, uint8 *flagp);
1083
1084		static JSBool
1085		MARK_GC_THING(JSContext *cx, void *thing, uint8 *flagp, void *arg)
1086	61896	{
1087	61896	JSRuntime *rt;
1088	61896	JSObject *obj;
1089	61896	jsval v, *vp, *end;
1090	61896	JSString *str;
1091	61896	void *next_thing;
1092	61896	uint8 *next_flagp;
1093		#ifdef JS_GCMETER
1094		uint32 tailCallNesting;
1095		#endif
1096		#ifdef GC_MARK_DEBUG
1097		JSScope *scope;
1098		JSScopeProperty *sprop;
1099		char name[32];
1100		#endif
1101	61896	int stackDummy;
1102
1103	61896	rt = cx->runtime;
1104		METER(tailCallNesting = 0);
1105		METER(if (++rt->gcStats.cdepth > rt->gcStats.maxcdepth)
1106		rt->gcStats.maxcdepth = rt->gcStats.cdepth);
1107
1108		#ifndef GC_MARK_DEBUG
1109		start:
1110		#endif
1111	70013	JS_ASSERT(flagp);
1112		METER(if (++rt->gcStats.depth > rt->gcStats.maxdepth)
1113		rt->gcStats.maxdepth = rt->gcStats.depth);
1114	70013	if (*flagp & GCF_MARK) {
1115		/*
1116		* This should happen only if recursive MARK_GC_THING marks flags
1117		* already stored in the caller's *next_flagp.
1118		*/
1119	142	goto out;
1120		}
1121
1122	69871	*flagp |= GCF_MARK;
1123
1124		#ifdef GC_MARK_DEBUG
1125		if (js_DumpGCHeap)
1126		gc_dump_thing(thing, *flagp, arg, js_DumpGCHeap);
1127		#endif
1128
1129	69871	switch (*flagp & GCF_TYPEMASK) {
1130		case GCX_OBJECT:
1131		/* If obj->slots is null, obj must be a newborn. */
1132	17415	obj = (JSObject *) thing;
1133	17415	vp = obj->slots;
1134	17415	if (!vp)
1135	0	goto out;
1136
1137		/* Switch to Deutsch-Schorr-Waite if we exhaust our stack quota. */
1138	17415	if (!JS_CHECK_STACK_SIZE(cx, stackDummy)) {
1139		METER(rt->gcStats.dswmark++);
1140	0	DeutschSchorrWaite(cx, thing, flagp);
1141	0	goto out;
1142		}
1143
1144		/* Mark slots if they are small enough to be GC-allocated. */
1145	17415	if ((vp[-1] + 1) * sizeof(jsval) <= GC_NBYTES_MAX)
1146	11401	GC_MARK(cx, vp - 1, "slots", arg);
1147
1148		/* Set up local variables to loop over unmarked things. */
1149	17415	end = vp + ((obj->map->ops->mark)
1150		? CALL_GC_THING_MARKER(obj->map->ops->mark, cx, obj, arg)
1151		: JS_MIN(obj->map->freeslot, obj->map->nslots));
1152
1153	17415	vp = NEXT_UNMARKED_GC_THING(vp, end, &thing, &flagp, arg);
1154	17415	if (!vp)
1155	9301	goto out;
1156	8114	v = *vp;
1157
1158		/*
1159		* Here, thing is the first value in obj->slots referring to an
1160		* unmarked GC-thing.
1161		*/
1162		#ifdef GC_MARK_DEBUG
1163		scope = OBJ_IS_NATIVE(obj) ? OBJ_SCOPE(obj) : NULL;
1164		#endif
1165	35708	for (;;) {
1166		/* Check loop invariants. */
1167	21920	JS_ASSERT(v == *vp && JSVAL_IS_GCTHING(v));
1168	21920	JS_ASSERT(thing == JSVAL_TO_GCTHING(v));
1169	21920	JS_ASSERT(flagp == js_GetGCThingFlags(thing));
1170
1171		#ifdef GC_MARK_DEBUG
1172		if (scope) {
1173		uint32 slot;
1174		jsval nval;
1175
1176		slot = vp - obj->slots;
1177		for (sprop = SCOPE_LAST_PROP(scope); ; sprop = sprop->parent) {
1178		if (!sprop) {
1179		switch (slot) {
1180		case JSSLOT_PROTO:
1181		strcpy(name, js_proto_str);
1182		break;
1183		case JSSLOT_PARENT:
1184		strcpy(name, js_parent_str);
1185		break;
1186		default:
1187		JS_snprintf(name, sizeof name,
1188		"**UNKNOWN SLOT %ld**",
1189		(long)slot);
1190		break;
1191		}
1192		break;
1193		}
1194		if (sprop->slot == slot) {
1195		nval = ID_TO_VALUE(sprop->id);
1196		if (JSVAL_IS_INT(nval)) {
1197		JS_snprintf(name, sizeof name, "%ld",
1198		(long)JSVAL_TO_INT(nval));
1199		} else if (JSVAL_IS_STRING(nval)) {
1200		JS_snprintf(name, sizeof name, "%s",
1201		JS_GetStringBytes(JSVAL_TO_STRING(nval)));
1202		} else {
1203		strcpy(name, "**FINALIZED ATOM KEY**");
1204		}
1205		break;
1206		}
1207		}
1208		} else {
1209		strcpy(name, "**UNKNOWN OBJECT MAP ENTRY**");
1210		}
1211		#endif
1212
1213	21920	do {
1214	21920	vp = NEXT_UNMARKED_GC_THING(vp+1, end, &next_thing, &next_flagp,
1215		arg);
1216	21920	if (!vp) {
1217		/*
1218		* Here thing came from the last unmarked GC-thing slot.
1219		* We can eliminate tail recursion unless GC_MARK_DEBUG
1220		* is defined.
1221		*/
1222		#ifdef GC_MARK_DEBUG
1223		GC_MARK(cx, thing, name, arg);
1224		goto out;
1225		#else
1226		METER(++tailCallNesting);
1227	8114	goto start;
1228		#endif
1229		}
1230	13806	} while (next_thing == thing);
1231	13788	v = *vp;
1232
1233		#ifdef GC_MARK_DEBUG
1234		GC_MARK(cx, thing, name, arg);
1235		#else
1236	13788	MARK_GC_THING(cx, thing, flagp, arg);
1237		#endif
1238	13788	thing = next_thing;
1239	13788	flagp = next_flagp;
1240		}
1241	449	break;
1242
1243		#ifdef DEBUG
1244		case GCX_STRING:
1245		str = (JSString *)thing;
1246		JS_ASSERT(!JSSTRING_IS_DEPENDENT(str));
1247		break;
1248		#endif
1249
1250		case GCX_MUTABLE_STRING:
1251	449	str = (JSString *)thing;
1252	449	if (JSSTRING_IS_DEPENDENT(str)) {
1253	37	thing = JSSTRDEP_BASE(str);
1254	37	flagp = UNMARKED_GC_THING_FLAGS(thing, arg);
1255	37	if (flagp) {
1256		#ifdef GC_MARK_DEBUG
1257		GC_MARK(cx, thing, "base", arg);
1258		goto out;
1259		#else
1260		METER(++tailCallNesting);
1261	3	goto start;
1262		#endif
1263		}
1264		}
1265	16	break;
1266
1267		#if JS_HAS_XML_SUPPORT
1268		case GCX_NAMESPACE:
1269	16	CALL_GC_THING_MARKER(js_MarkXMLNamespace, cx, (JSXMLNamespace *)thing,
1270		arg);
1271	16	break;
1272
1273		case GCX_QNAME:
1274	32	CALL_GC_THING_MARKER(js_MarkXMLQName, cx, (JSXMLQName *)thing, arg);
1275	32	break;
1276
1277		case GCX_XML:
1278	16	CALL_GC_THING_MARKER(js_MarkXML, cx, (JSXML *)thing, arg);
1279		break;
1280		#endif
1281		}
1282
1283		out:
1284		METER(rt->gcStats.depth -= 1 + tailCallNesting);
1285		METER(rt->gcStats.cdepth--);
1286	61896	return JS_TRUE;
1287		}
1288
1289		/*
1290		* An invalid object reference that's distinct from JSVAL_TRUE and JSVAL_FALSE
1291		* when tagged as a boolean.  Used to indicate empty DSW mark stack.
1292		*
1293		* Reversed pointers that link the DSW mark stack through obj->slots entries
1294		* are also tagged as booleans so we can find each pointer and unreverse it.
1295		* Because no object pointer is <= 16, these values can be distinguished from
1296		* JSVAL_EMPTY, JSVAL_TRUE, and JSVAL_FALSE.
1297		*/
1298		#define JSVAL_EMPTY (2 << JSVAL_TAGBITS)
1299
1300		/*
1301		* To optimize native objects to avoid O(n^2) explosion in pathological cases,
1302		* we use a dswIndex member of JSScope to tell where in obj->slots to find the
1303		* reversed pointer.  Scrounging space in JSScope by packing existing members
1304		* tighter yielded 16 bits of index, which we use directly if obj->slots has
1305		* 64K or fewer slots.  Otherwise we make scope->dswIndex a fixed-point 16-bit
1306		* fraction of the number of slots.
1307		*/
1308		static JS_INLINE uint16
1309		EncodeDSWIndex(jsval *vp, jsval *slots)
1310	0	{
1311	0	uint32 nslots, limit, index;
1312	0	jsdouble d;
1313
1314	0	nslots = slots[-1];
1315	0	limit = JS_BIT(16);
1316	0	index = PTRDIFF(vp, slots, jsval);
1317	0	JS_ASSERT(index < nslots);
1318	0	if (nslots > limit) {
1319	0	d = ((jsdouble)index / nslots) * limit;
1320	0	JS_ASSERT(0 <= d && d < limit);
1321	0	return (uint16) d;
1322		}
1323	0	return (uint16) index;
1324		}
1325
1326		static JS_INLINE uint32
1327		DecodeDSWIndex(uint16 dswIndex, jsval *slots)
1328	0	{
1329	0	uint32 nslots, limit;
1330	0	jsdouble d;
1331
1332	0	nslots = slots[-1];
1333	0	limit = JS_BIT(16);
1334	0	JS_ASSERT(dswIndex < nslots);
1335	0	if (nslots > limit) {
1336	0	d = ((jsdouble)dswIndex * nslots) / limit;
1337	0	JS_ASSERT(0 <= d && d < nslots);
1338	0	return (uint32) d;
1339		}
1340	0	return dswIndex;
1341		}
1342
1343		static void
1344		DeutschSchorrWaite(JSContext *cx, void *thing, uint8 *flagp)
1345	0	{
1346	0	jsval top, parent, v, *vp, *end;
1347	0	JSObject *obj;
1348	0	JSScope *scope;
1349		#ifdef JS_GCMETER
1350		JSRuntime *rt = cx->runtime;
1351		#endif
1352
1353	0	top = JSVAL_EMPTY;
1354
1355		down:
1356		METER(if (++rt->gcStats.dswdepth > rt->gcStats.maxdswdepth)
1357		rt->gcStats.maxdswdepth = rt->gcStats.dswdepth);
1358	0	obj = (JSObject *) thing;
1359	0	parent = OBJECT_TO_JSVAL(obj);
1360
1361		/* Precompute for quick testing to set and get scope->dswIndex. */
1362	0	scope = (OBJ_IS_NATIVE(obj) && OBJ_SCOPE(obj)->object == obj)
1363		? OBJ_SCOPE(obj)
1364		: NULL;
1365
1366		/* Mark slots if they are small enough to be GC-allocated. */
1367	0	vp = obj->slots;
1368	0	if ((vp[-1] + 1) * sizeof(jsval) <= GC_NBYTES_MAX)
1369	0	GC_MARK(cx, vp - 1, "slots", NULL);
1370
1371	0	end = vp + ((obj->map->ops->mark)
1372		? obj->map->ops->mark(cx, obj, NULL)
1373		: JS_MIN(obj->map->freeslot, obj->map->nslots));
1374
1375	0	*flagp |= GCF_MARK;
1376
1377	0	for (;;) {
1378	0	while ((vp = NEXT_UNMARKED_GC_THING(vp, end, &thing, &flagp, NULL))
1379		!= NULL) {
1380	0	v = *vp;
1381	0	JS_ASSERT(JSVAL_TO_GCTHING(v) == thing);
1382
1383	0	if (JSVAL_IS_OBJECT(v)) {
1384	0	*vp = JSVAL_SETTAG(top, JSVAL_BOOLEAN);
1385	0	top = parent;
1386	0	if (scope)
1387	0	scope->dswIndex = EncodeDSWIndex(vp, obj->slots);
1388	0	goto down;
1389		}
1390
1391		/* Handle string and double GC-things. */
1392	0	MARK_GC_THING(cx, thing, flagp, NULL);
1393		}
1394
1395		/* If we are back at the root (or we never left it), we're done. */
1396		METER(rt->gcStats.dswdepth--);
1397	0	if (scope)
1398	0	scope->dswIndex = 0;
1399	0	if (top == JSVAL_EMPTY)
1400	0	return;
1401
1402		/* Time to go back up the spanning tree. */
1403		METER(rt->gcStats.dswup++);
1404	0	obj = JSVAL_TO_OBJECT(top);
1405	0	vp = obj->slots;
1406	0	end = vp + vp[-1];
1407
1408		/*
1409		* If obj is native and owns its own scope, we can minimize the cost
1410		* of searching for the reversed pointer.
1411		*/
1412	0	scope = (OBJ_IS_NATIVE(obj) && OBJ_SCOPE(obj)->object == obj)
1413		? OBJ_SCOPE(obj)
1414		: NULL;
1415	0	if (scope)
1416	0	vp += DecodeDSWIndex(scope->dswIndex, vp);
1417
1418		/*
1419		* Alas, we must search for the reversed pointer.  If we used the
1420		* scope->dswIndex hint, we'll step over a few slots for objects with
1421		* a few times 64K slots, etc.  For more typical (that is, far fewer
1422		* than 64K slots) native objects that own their own scopes, this loop
1423		* won't iterate at all.  The order of complexity for host objects and
1424		* unmutated native objects is O(n^2), but n (4 or 5 in most cases) is
1425		* low enough that we don't care.
1426		*
1427		* We cannot use a reversed pointer into obj->slots, because there
1428		* is no way to find an object from an address within its slots.
1429		*/
1430	0	v = *vp;
1431	0	while (v <= JSVAL_TRUE || !JSVAL_IS_BOOLEAN(v)) {
1432		METER(rt->gcStats.dswupstep++);
1433	0	JS_ASSERT(vp + 1 < end);
1434	0	v = *++vp;
1435		}
1436
1437	0	*vp++ = parent;
1438	0	parent = top;
1439	0	top = JSVAL_CLRTAG(v);
1440		}
1441		}
1442
1443		void
1444		js_MarkGCThing(JSContext *cx, void *thing, void *arg)
1445	79661	{
1446	79661	uint8 *flagp;
1447
1448	79661	flagp = UNMARKED_GC_THING_FLAGS(thing, arg);
1449	79661	if (!flagp)
1450	31553	return;
1451	48108	MARK_GC_THING(cx, thing, flagp, arg);
1452		}
1453
1454		JS_STATIC_DLL_CALLBACK(JSDHashOperator)
1455		gc_root_marker(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 num, void *arg)
1456	21995	{
1457	21995	JSGCRootHashEntry *rhe = (JSGCRootHashEntry *)hdr;
1458	21995	jsval *rp = (jsval *)rhe->root;
1459	21995	jsval v = *rp;
1460
1461		/* Ignore null object and scalar values. */
1462	21995	if (!JSVAL_IS_NULL(v) && JSVAL_IS_GCTHING(v)) {
1463	21995	JSContext *cx = (JSContext *)arg;
1464		#ifdef DEBUG
1465		uintN i;
1466		JSArena *a;
1467		jsuword firstpage;
1468		JSBool root_points_to_gcArenaPool = JS_FALSE;
1469		void *thing = JSVAL_TO_GCTHING(v);
1470
1471		for (i = 0; i < GC_NUM_FREELISTS; i++) {
1472		for (a = cx->runtime->gcArenaPool[i].first.next; a; a = a->next) {
1473		firstpage = FIRST_THING_PAGE(a);
1474		if (JS_UPTRDIFF(thing, firstpage) < a->avail - firstpage) {
1475		root_points_to_gcArenaPool = JS_TRUE;
1476		break;
1477		}
1478		}
1479		}
1480		if (!root_points_to_gcArenaPool && rhe->name) {
1481		fprintf(stderr,
1482		"JS API usage error: the address passed to JS_AddNamedRoot currently holds an\n"
1483		"invalid jsval.  This is usually caused by a missing call to JS_RemoveRoot.\n"
1484		"The root's name is \"%s\".\n",
1485		rhe->name);
1486		}
1487		JS_ASSERT(root_points_to_gcArenaPool);
1488		#endif
1489
1490	21995	GC_MARK(cx, JSVAL_TO_GCTHING(v), rhe->name ? rhe->name : "root", NULL);
1491		}
1492	21995	return JS_DHASH_NEXT;
1493		}
1494
1495		JS_STATIC_DLL_CALLBACK(JSDHashOperator)
1496		gc_lock_marker(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 num, void *arg)
1497	0	{
1498	0	JSGCLockHashEntry *lhe = (JSGCLockHashEntry *)hdr;
1499	0	void *thing = (void *)lhe->thing;
1500	0	JSContext *cx = (JSContext *)arg;
1501
1502	0	GC_MARK(cx, thing, "locked object", NULL);
1503	0	return JS_DHASH_NEXT;
1504		}
1505
1506		void
1507		js_ForceGC(JSContext *cx, uintN gcflags)
1508	16	{
1509	16	uintN i;
1510
1511	272	for (i = 0; i < GCX_NTYPES; i++)
1512	256	cx->newborn[i] = NULL;
1513	16	cx->lastAtom = NULL;
1514	16	cx->runtime->gcPoke = JS_TRUE;
1515	16	js_GC(cx, gcflags);
1516	16	JS_ArenaFinish();
1517		}
1518
1519		#define GC_MARK_JSVALS(cx, len, vec, name)                                    \
1520		JS_BEGIN_MACRO                                                            \
1521		jsval _v, *_vp, *_end;                                                \
1522		\
1523		for (_vp = vec, _end = _vp + len; _vp < _end; _vp++) {                \
1524		_v = *_vp;                                                        \
1525		if (JSVAL_IS_GCTHING(_v))                                         \
1526		GC_MARK(cx, JSVAL_TO_GCTHING(_v), name, NULL);                \
1527		}                                                                     \
1528		JS_END_MACRO
1529
1530		void
1531		js_GC(JSContext *cx, uintN gcflags)
1532	16	{
1533	16	JSRuntime *rt;
1534	16	JSContext *iter, *acx;
1535	16	JSStackFrame *fp, *chain;
1536	16	uintN i, depth, nslots, type;
1537	16	JSStackHeader *sh;
1538	16	JSTempValueRooter *tvr;
1539	16	size_t nbytes, nflags;
1540	16	JSArena *a, **ap;
1541	16	uint8 flags, *flagp, *split;
1542	16	JSGCThing *thing, *limit, **flp, **oflp;
1543	16	GCFinalizeOp finalizer;
1544	16	uint32 *bytesptr;
1545	16	JSBool all_clear;
1546		#ifdef JS_THREADSAFE
1547		jsword currentThread;
1548		uint32 requestDebit;
1549		#endif
1550
1551	16	rt = cx->runtime;
1552		#ifdef JS_THREADSAFE
1553		/* Avoid deadlock. */
1554		JS_ASSERT(!JS_IS_RUNTIME_LOCKED(rt));
1555		#endif
1556
1557		/*
1558		* Don't collect garbage if the runtime isn't up, and cx is not the last
1559		* context in the runtime.  The last context must force a GC, and nothing
1560		* should suppress that final collection or there may be shutdown leaks,
1561		* or runtime bloat until the next context is created.
1562		*/
1563	16	if (rt->state != JSRTS_UP && !(gcflags & GC_LAST_CONTEXT))
1564	0	return;
1565
1566		/*
1567		* Let the API user decide to defer a GC if it wants to (unless this
1568		* is the last context).  Invoke the callback regardless.
1569		*/
1570	16	if (rt->gcCallback) {
1571	0	if (!rt->gcCallback(cx, JSGC_BEGIN) && !(gcflags & GC_LAST_CONTEXT))
1572	0	return;
1573		}
1574
1575		/* Lock out other GC allocator and collector invocations. */
1576	16	if (!(gcflags & GC_ALREADY_LOCKED))
1577	16	JS_LOCK_GC(rt);
1578
1579		/* Do nothing if no mutator has executed since the last GC. */
1580	16	if (!rt->gcPoke) {
1581		METER(rt->gcStats.nopoke++);
1582	0	if (!(gcflags & GC_ALREADY_LOCKED))
1583	0	JS_UNLOCK_GC(rt);
1584	0	return;
1585		}
1586		METER(rt->gcStats.poke++);
1587	16	rt->gcPoke = JS_FALSE;
1588
1589		#ifdef JS_THREADSAFE
1590		/* Bump gcLevel and return rather than nest on this thread. */
1591		currentThread = js_CurrentThreadId();
1592		if (rt->gcThread == currentThread) {
1593		JS_ASSERT(rt->gcLevel > 0);
1594		rt->gcLevel++;
1595		METER(if (rt->gcLevel > rt->gcStats.maxlevel)
1596		rt->gcStats.maxlevel = rt->gcLevel);
1597		if (!(gcflags & GC_ALREADY_LOCKED))
1598		JS_UNLOCK_GC(rt);
1599		return;
1600		}
1601
1602		/*
1603		* If we're in one or more requests (possibly on more than one context)
1604		* running on the current thread, indicate, temporarily, that all these
1605		* requests are inactive.  NB: if cx->thread is 0, then cx is not using
1606		* the request model, and does not contribute to rt->requestCount.
1607		*/
1608		requestDebit = 0;
1609		if (cx->thread) {
1610		/*
1611		* Check all contexts for any with the same thread-id.  XXX should we
1612		* keep a sub-list of contexts having the same id?
1613		*/
1614		iter = NULL;
1615		while ((acx = js_ContextIterator(rt, JS_FALSE, &iter)) != NULL) {
1616		if (acx->thread == cx->thread && acx->requestDepth)
1617		requestDebit++;
1618		}
1619		} else {
1620		/*
1621		* We assert, but check anyway, in case someone is misusing the API.
1622		* Avoiding the loop over all of rt's contexts is a win in the event
1623		* that the GC runs only on request-less contexts with 0 thread-ids,
1624		* in a special thread such as might be used by the UI/DOM/Layout
1625		* "mozilla" or "main" thread in Mozilla-the-browser.
1626		*/
1627		JS_ASSERT(cx->requestDepth == 0);
1628		if (cx->requestDepth)
1629		requestDebit = 1;
1630		}
1631		if (requestDebit) {
1632		JS_ASSERT(requestDebit <= rt->requestCount);
1633		rt->requestCount -= requestDebit;
1634		if (rt->requestCount == 0)
1635		JS_NOTIFY_REQUEST_DONE(rt);
1636		}
1637
1638		/* If another thread is already in GC, don't attempt GC; wait instead. */
1639		if (rt->gcLevel > 0) {
1640		/* Bump gcLevel to restart the current GC, so it finds new garbage. */
1641		rt->gcLevel++;
1642		METER(if (rt->gcLevel > rt->gcStats.maxlevel)
1643		rt->gcStats.maxlevel = rt->gcLevel);
1644
1645		/* Wait for the other thread to finish, then resume our request. */
1646		while (rt->gcLevel > 0)
1647		JS_AWAIT_GC_DONE(rt);
1648		if (requestDebit)
1649		rt->requestCount += requestDebit;
1650		if (!(gcflags & GC_ALREADY_LOCKED))
1651		JS_UNLOCK_GC(rt);
1652		return;
1653		}
1654
1655		/* No other thread is in GC, so indicate that we're now in GC. */
1656		rt->gcLevel = 1;
1657		rt->gcThread = currentThread;
1658
1659		/* Wait for all other requests to finish. */
1660		while (rt->requestCount > 0)
1661		JS_AWAIT_REQUEST_DONE(rt);
1662
1663		#else  /* !JS_THREADSAFE */
1664
1665		/* Bump gcLevel and return rather than nest; the outer gc will restart. */
1666	16	rt->gcLevel++;
1667		METER(if (rt->gcLevel > rt->gcStats.maxlevel)
1668		rt->gcStats.maxlevel = rt->gcLevel);
1669	16	if (rt->gcLevel > 1)
1670	0	return;
1671
1672		#endif /* !JS_THREADSAFE */
1673
1674		/*
1675		* Set rt->gcRunning here within the GC lock, and after waiting for any
1676		* active requests to end, so that new requests that try to JS_AddRoot,
1677		* JS_RemoveRoot, or JS_RemoveRootRT block in JS_BeginRequest waiting for
1678		* rt->gcLevel to drop to zero, while request-less calls to the *Root*
1679		* APIs block in js_AddRoot or js_RemoveRoot (see above in this file),
1680		* waiting for GC to finish.
1681		*/
1682	16	rt->gcRunning = JS_TRUE;
1683	16	JS_UNLOCK_GC(rt);
1684
1685		/* If a suspended compile is running on another context, keep atoms. */
1686	16	if (rt->gcKeepAtoms)
1687	0	gcflags |= GC_KEEP_ATOMS;
1688
1689		/* Reset malloc counter. */
1690	16	rt->gcMallocBytes = 0;
1691
1692		/* Drop atoms held by the property cache, and clear property weak links. */
1693	16	js_DisablePropertyCache(cx);
1694	16	js_FlushPropertyCache(cx);
1695		#ifdef DEBUG_notme
1696		{ extern void js_DumpScopeMeters(JSRuntime *rt);
1697		js_DumpScopeMeters(rt);
1698		}
1699		#endif
1700
1701		restart:
1702	32	rt->gcNumber++;
1703
1704		/*
1705		* Mark phase.
1706		*/
1707	32	JS_DHashTableEnumerate(&rt->gcRootsHash, gc_root_marker, cx);
1708	32	if (rt->gcLocksHash)
1709	0	JS_DHashTableEnumerate(rt->gcLocksHash, gc_lock_marker, cx);
1710	32	js_MarkAtomState(&rt->atomState, gcflags, gc_mark_atom_key_thing, cx);
1711	32	js_MarkWatchPoints(cx);
1712	32	js_MarkScriptFilenames(rt, gcflags);
1713	32	js_MarkNativeIteratorStates(cx);
1714
1715	32	iter = NULL;
1716	32	while ((acx = js_ContextIterator(rt, JS_TRUE, &iter)) != NULL) {
1717		/*
1718		* Iterate frame chain and dormant chains. Temporarily tack current
1719		* frame onto the head of the dormant list to ease iteration.
1720		*
1721		* (NB: see comment on this whole "dormant" thing in js_Execute.)
1722		*/
1723	0	chain = acx->fp;
1724	0	if (chain) {
1725	0	JS_ASSERT(!chain->dormantNext);
1726	0	chain->dormantNext = acx->dormantFrameChain;
1727		} else {
1728	0	chain = acx->dormantFrameChain;
1729		}
1730
1731	0	for (fp = chain; fp; fp = chain = chain->dormantNext) {
1732	0	do {
1733	0	if (fp->callobj)
1734	0	GC_MARK(cx, fp->callobj, "call object", NULL);
1735	0	if (fp->argsobj)
1736	0	GC_MARK(cx, fp->argsobj, "arguments object", NULL);
1737	0	if (fp->varobj)
1738	0	GC_MARK(cx, fp->varobj, "variables object", NULL);
1739	0	if (fp->script) {
1740	0	js_MarkScript(cx, fp->script, NULL);
1741	0	if (fp->spbase) {
1742		/*
1743		* Don't mark what has not been pushed yet, or what
1744		* has been popped already.
1745		*/
1746	0	depth = fp->script->depth;
1747	0	nslots = (JS_UPTRDIFF(fp->sp, fp->spbase)
1748		< depth * sizeof(jsval))
1749		? (uintN)(fp->sp - fp->spbase)
1750		: depth;
1751	0	GC_MARK_JSVALS(cx, nslots, fp->spbase, "operand");
1752		}
1753		}
1754	0	GC_MARK(cx, fp->thisp, "this", NULL);
1755	0	if (fp->argv) {
1756	0	nslots = fp->argc;
1757	0	if (fp->fun) {
1758	0	if (fp->fun->nargs > nslots)
1759	0	nslots = fp->fun->nargs;
1760	0	nslots += fp->fun->extra;
1761		}
1762	0	GC_MARK_JSVALS(cx, nslots, fp->argv, "arg");
1763		}
1764	0	if (JSVAL_IS_GCTHING(fp->rval))
1765	0	GC_MARK(cx, JSVAL_TO_GCTHING(fp->rval), "rval", NULL);
1766	0	if (fp->vars)
1767	0	GC_MARK_JSVALS(cx, fp->nvars, fp->vars, "var");
1768	0	GC_MARK(cx, fp->scopeChain, "scope chain", NULL);
1769	0	if (fp->sharpArray)
1770	0	GC_MARK(cx, fp->sharpArray, "sharp array", NULL);
1771
1772	0	if (fp->xmlNamespace)
1773	0	GC_MARK(cx, fp->xmlNamespace, "xmlNamespace", NULL);
1774	0	} while ((fp = fp->down) != NULL);
1775		}
1776
1777		/* Cleanup temporary "dormant" linkage. */
1778	0	if (acx->fp)
1779	0	acx->fp->dormantNext = NULL;
1780
1781		/* Mark other roots-by-definition in acx. */
1782	0	GC_MARK(cx, acx->globalObject, "global object", NULL);
1783	0	for (i = 0; i < GCX_NTYPES; i++)
1784	0	GC_MARK(cx, acx->newborn[i], gc_typenames[i], NULL);
1785	0	if (acx->lastAtom)
1786	0	GC_MARK_ATOM(cx, acx->lastAtom, NULL);
1787	0	if (JSVAL_IS_GCTHING(acx->lastInternalResult)) {
1788	0	thing = JSVAL_TO_GCTHING(acx->lastInternalResult);
1789	0	if (thing)
1790	0	GC_MARK(cx, thing, "lastInternalResult", NULL);
1791		}
1792		#if JS_HAS_EXCEPTIONS
1793	0	if (acx->throwing && JSVAL_IS_GCTHING(acx->exception))
1794	0	GC_MARK(cx, JSVAL_TO_GCTHING(acx->exception), "exception", NULL);
1795		#endif
1796		#if JS_HAS_LVALUE_RETURN
1797	0	if (acx->rval2set && JSVAL_IS_GCTHING(acx->rval2))
1798	0	GC_MARK(cx, JSVAL_TO_GCTHING(acx->rval2), "rval2", NULL);
1799		#endif
1800
1801	0	for (sh = acx->stackHeaders; sh; sh = sh->down) {
1802		METER(rt->gcStats.stackseg++);
1803		METER(rt->gcStats.segslots += sh->nslots);
1804	0	GC_MARK_JSVALS(cx, sh->nslots, JS_STACK_SEGMENT(sh), "stack");
1805		}
1806
1807	0	if (acx->localRootStack)
1808	0	js_MarkLocalRoots(cx, acx->localRootStack);
1809	0	for (tvr = acx->tempValueRooters; tvr; tvr = tvr->down) {
1810	0	if (tvr->count == -1) {
1811	0	if (JSVAL_IS_GCTHING(tvr->u.value)) {
1812	0	GC_MARK(cx, JSVAL_TO_GCTHING(tvr->u.value),
1813		"tvr->u.value", NULL);
1814		}
1815	0	} else if (tvr->count == -2) {
1816	0	tvr->u.marker(cx, tvr);
1817		} else {
1818	0	JS_ASSERT(tvr->count >= 0);
1819	0	GC_MARK_JSVALS(cx, tvr->count, tvr->u.array, "tvr->u.array");
1820		}
1821		}
1822
1823	0	if (acx->sharpObjectMap.depth > 0)
1824	0	js_GCMarkSharpMap(cx, &acx->sharpObjectMap);
1825		}
1826		#ifdef DUMP_CALL_TABLE
1827		js_DumpCallTable(cx);
1828		#endif
1829
1830	32	if (rt->gcCallback)
1831	0	(void) rt->gcCallback(cx, JSGC_MARK_END);
1832
1833		/*
1834		* Sweep phase.
1835		*
1836		* Finalize as we sweep, outside of rt->gcLock, but with rt->gcRunning set
1837		* so that any attempt to allocate a GC-thing from a finalizer will fail,
1838		* rather than nest badly and leave the unmarked newborn to be swept.
1839		*
1840		* Finalize smaller objects before larger, to guarantee finalization of
1841		* GC-allocated obj->slots after obj.  See FreeSlots in jsobj.c.
1842		*/
1843	32	js_SweepAtomState(&rt->atomState);
1844	32	js_SweepScopeProperties(rt);
1845	352	for (i = 0; i < GC_NUM_FREELISTS; i++) {
1846	320	nbytes = GC_FREELIST_NBYTES(i);
1847	320	nflags = nbytes / sizeof(JSGCThing);
1848
1849	3910	for (a = rt->gcArenaPool[i].first.next; a; a = a->next) {
1850	3590	flagp = (uint8 *) a->base;
1851	3590	split = (uint8 *) FIRST_THING_PAGE(a);
1852	3590	limit = (JSGCThing *) a->avail;
1853	1283727	for (thing = (JSGCThing *) split; thing < limit; thing += nflags) {
1854	1280137	if (((jsuword)thing & GC_PAGE_MASK) == 0) {
1855	27621	thing = (JSGCThing *) FIRST_THING((jsuword)thing, nbytes);
1856	27621	flagp = js_GetGCThingFlags(thing);
1857		}
1858	1280137	flags = *flagp;
1859	1280137	if (flags & GCF_MARK) {
1860	69871	*flagp &= ~GCF_MARK;
1861	1210266	} else if (!(flags & (GCF_LOCK | GCF_FINAL))) {
1862		/* Call the finalizer with GCF_FINAL ORed into flags. */
1863	775026	type = flags & GCF_TYPEMASK;
1864	775026	finalizer = gc_finalizers[type];
1865	775026	if (finalizer) {
1866	343323	*flagp = (uint8)(flags | GCF_FINAL);
1867	343323	if (type >= GCX_EXTERNAL_STRING)
1868	0	js_PurgeDeflatedStringCache((JSString *)thing);
1869	343323	finalizer(cx, thing);
1870		}
1871
1872		/* Set flags to GCF_FINAL, signifying that thing is free. */
1873	775026	*flagp = GCF_FINAL;
1874
1875	775026	bytesptr = (type == GCX_PRIVATE)
1876		? &rt->gcPrivateBytes
1877		: &rt->gcBytes;
1878	775026	JS_ASSERT(*bytesptr >= nbytes + nflags);
1879	775026	*bytesptr -= nbytes + nflags;
1880		}
1881	1280137	flagp += nflags;
1882	1280137	if (JS_UPTRDIFF(flagp, split) < nflags)
1883	3397	flagp += GC_THINGS_SIZE;
1884		}
1885		}
1886		}
1887
1888		/*
1889		* Sweep script filenames after sweeping functions in the generic loop
1890		* above. In this way when scripted function's finalizer destroys script
1891		* triggering a call to rt->destroyScriptHook, the hook can still access
1892		* script's filename. See bug 323267.
1893		*/
1894	32	js_SweepScriptFilenames(rt);
1895
1896		/*
1897		* Free phase.
1898		* Free any unused arenas and rebuild the JSGCThing freelist.
1899		*/
1900	352	for (i = 0; i < GC_NUM_FREELISTS; i++) {
1901	320	ap = &rt->gcArenaPool[i].first.next;
1902	320	a = *ap;
1903	320	if (!a)
1904	68	continue;
1905
1906	252	all_clear = JS_TRUE;
1907	252	flp = oflp = &rt->gcFreeList[i];
1908	252	*flp = NULL;
1909		METER(rt->gcStats.freelen[i] = 0);
1910
1911	252	nbytes = GC_FREELIST_NBYTES(i);
1912	252	nflags = nbytes / sizeof(JSGCThing);
1913	3590	do {
1914	3590	flagp = (uint8 *) a->base;
1915	3590	split = (uint8 *) FIRST_THING_PAGE(a);
1916	3590	limit = (JSGCThing *) a->avail;
1917	1283727	for (thing = (JSGCThing *) split; thing < limit; thing += nflags) {
1918	1280137	if (((jsuword)thing & GC_PAGE_MASK) == 0) {
1919	27621	thing = (JSGCThing *) FIRST_THING((jsuword)thing, nbytes);
1920	27621	flagp = js_GetGCThingFlags(thing);
1921		}
1922	1280137	if (*flagp != GCF_FINAL) {
1923	69871	all_clear = JS_FALSE;
1924		} else {
1925	1210266	thing->flagp = flagp;
1926	1210266	*flp = thing;
1927	1210266	flp = &thing->next;
1928		METER(rt->gcStats.freelen[i]++);
1929		}
1930	1280137	flagp += nflags;
1931	1280137	if (JS_UPTRDIFF(flagp, split) < nflags)
1932	3397	flagp += GC_THINGS_SIZE;
1933		}
1934
1935	3590	if (all_clear) {
1936	2264	JS_ARENA_DESTROY(&rt->gcArenaPool[i], a, ap);
1937	2264	flp = oflp;
1938		METER(rt->gcStats.afree++);
1939		} else {
1940	1326	ap = &a->next;
1941	1326	all_clear = JS_TRUE;
1942	1326	oflp = flp;
1943		}
1944	3590	} while ((a = *ap) != NULL);
1945
1946		/* Terminate the new freelist. */
1947	252	*flp = NULL;
1948		}
1949
1950	32	if (rt->gcCallback)
1951	0	(void) rt->gcCallback(cx, JSGC_FINALIZE_END);
1952		#ifdef DEBUG_notme
1953		{ extern void DumpSrcNoteSizeHist();
1954		DumpSrcNoteSizeHist();
1955		printf("GC HEAP SIZE %lu (%lu)\n",
1956		(unsigned long)rt->gcBytes, (unsigned long)rt->gcPrivateBytes);
1957		}
1958		#endif
1959
1960	32	JS_LOCK_GC(rt);
1961	32	if (rt->gcLevel > 1 || rt->gcPoke) {
1962	16	rt->gcLevel = 1;
1963	16	rt->gcPoke = JS_FALSE;
1964	16	JS_UNLOCK_GC(rt);
1965	16	goto restart;
1966		}
1967	16	js_EnablePropertyCache(cx);
1968	16	rt->gcLevel = 0;
1969	16	rt->gcLastBytes = rt->gcBytes;
1970	16	rt->gcRunning = JS_FALSE;
1971
1972		#ifdef JS_THREADSAFE
1973		/* If we were invoked during a request, pay back the temporary debit. */
1974		if (requestDebit)
1975		rt->requestCount += requestDebit;
1976		rt->gcThread = 0;
1977		JS_NOTIFY_GC_DONE(rt);
1978		if (!(gcflags & GC_ALREADY_LOCKED))
1979		JS_UNLOCK_GC(rt);
1980		#endif
1981
1982	16	if (rt->gcCallback) {
1983	0	if (gcflags & GC_ALREADY_LOCKED)
1984	0	JS_UNLOCK_GC(rt);
1985	0	(void) rt->gcCallback(cx, JSGC_END);
1986	0	if (gcflags & GC_ALREADY_LOCKED)
1987	16	JS_LOCK_GC(rt);
1988		}