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		/*
73		* GC arena sizing depends on amortizing arena overhead using a large number
74		* of things per arena, and on the thing/flags ratio of 8:1 on most platforms.
75		*
76		* On 64-bit platforms, we would have half as many things per arena because
77		* pointers are twice as big, so we double the bytes for things per arena.
78		* This preserves the 1024 byte flags sub-arena size, which relates to the
79		* GC_PAGE_SIZE (see below for why).
80		*/
81		#if JS_BYTES_PER_WORD == 8
82		# define GC_THINGS_SHIFT 14     /* 16KB for things on Alpha, etc. */
83		#else
84		# define GC_THINGS_SHIFT 13     /* 8KB for things on most platforms */
85		#endif
86		#define GC_THINGS_SIZE  JS_BIT(GC_THINGS_SHIFT)
87		#define GC_FLAGS_SIZE   (GC_THINGS_SIZE / sizeof(JSGCThing))
88		#define GC_ARENA_SIZE   (GC_THINGS_SIZE + GC_FLAGS_SIZE)
89
90		/*
91		* The private JSGCThing struct, which describes a gcFreeList element.
92		*/
93		struct JSGCThing {
94		JSGCThing   *next;
95		uint8       *flagp;
96		};
97
98		/*
99		* A GC arena contains one flag byte for each thing in its heap, and supports
100		* O(1) lookup of a flag given its thing's address.
101		*
102		* To implement this, we take advantage of the thing/flags numerology: given
103		* the 8K bytes worth of GC-things, there are 1K flag bytes.  We mask a thing's
104		* address with ~1023 to find a JSGCPageInfo record at the front of a mythical
105		* "GC page" within the larger 8K thing arena.  That JSGCPageInfo contains a
106		* pointer to the 128 flag bytes corresponding to the things in the page, so we
107		* index into this flags array using the thing's index within its page.
108		*
109		* To align thing pages on 1024-byte boundaries, we must allocate the 9KB of
110		* flags+things arena payload, then find the first 0 mod 1024 boundary after
111		* the first payload address.  That's where things start, with a JSGCPageInfo
112		* taking up the first thing-slot, as usual for 0 mod 1024 byte boundaries.
113		* The effect of this alignment trick is to split the flags into at most 2
114		* discontiguous spans, one before the things and one after (if we're really
115		* lucky, and the arena payload starts on a 0 mod 1024 byte boundary, no need
116		* to split).
117		*
118		* The overhead of this scheme for most platforms is (16+8*(8+1))/(16+9K) or
119		* .95% (assuming 16 byte JSArena header size, and 8 byte JSGCThing size).
120		*
121		* Here's some ASCII art showing an arena:
122		*
123		*   split
124		*     |
125		*     V
126		*  +--+-------+-------+-------+-------+-------+-------+-------+-------+-----+
127		*  |fB|  tp0  |  tp1  |  tp2  |  tp3  |  tp4  |  tp5  |  tp6  |  tp7  | fA  |
128		*  +--+-------+-------+-------+-------+-------+-------+-------+-------+-----+
129		*              ^                                 ^
130		*  tI ---------+                                 |
131		*  tJ -------------------------------------------+
132		*
133		*  - fB are the "before split" flags, fA are the "after split" flags
134		*  - tp0-tp7 are the 8 thing pages
135		*  - thing tI points into tp1, whose flags are below the split, in fB
136		*  - thing tJ points into tp5, clearly above the split
137		*
138		* In general, one of the thing pages will have some of its things' flags on
139		* the low side of the split, and the rest of its things' flags on the high
140		* side.  All the other pages have flags only below or only above.  Therefore
141		* we'll have to test something to decide whether the split divides flags in
142		* a given thing's page.  So we store the split pointer (the pointer to tp0)
143		* in each JSGCPageInfo, along with the flags pointer for the 128 flag bytes
144		* ideally starting, for tp0 things, at the beginning of the arena's payload
145		* (at the start of fB).
146		*
147		* That is, each JSGCPageInfo's flags pointer is 128 bytes from the previous,
148		* or at the start of the arena if there is no previous page in this arena.
149		* Thus these ideal 128-byte flag pages run contiguously from the start of the
150		* arena (right over the split!), and the JSGCPageInfo flags pointers contain
151		* no discontinuities over the split created by the thing pages.  So if, for a
152		* given JSGCPageInfo *pi, we find that
153		*
154		*  pi->flags + ((jsuword)thing % 1024) / sizeof(JSGCThing) >= pi->split
155		*
156		* then we must add GC_THINGS_SIZE to the nominal flags pointer to jump over
157		* all the thing pages that split the flags into two discontiguous spans.
158		*
159		* (If we need to implement card-marking for an incremental GC write barrier,
160		* we can use the low byte of the pi->split pointer as the card-mark, for an
161		* extremely efficient write barrier: when mutating an object obj, just store
162		* a 1 byte at (uint8 *) ((jsuword)obj & ~1023) for little-endian platforms.
163		* When finding flags, we'll of course have to mask split with ~255, but it is
164		* guaranteed to be 1024-byte aligned, so no information is lost by overlaying
165		* the card-mark byte on split's low byte.)
166		*/
167		#define GC_PAGE_SHIFT   10
168		#define GC_PAGE_MASK    ((jsuword) JS_BITMASK(GC_PAGE_SHIFT))
169		#define GC_PAGE_SIZE    JS_BIT(GC_PAGE_SHIFT)
170
171		typedef struct JSGCPageInfo {
172		uint8       *split;
173		uint8       *flags;
174		} JSGCPageInfo;
175
176		#define FIRST_THING_PAGE(a)     (((a)->base + GC_FLAGS_SIZE) & ~GC_PAGE_MASK)
177
178		static JSGCThing *
179		gc_new_arena(JSArenaPool *pool)
180	0	{
181	0	uint8 *flagp, *split, *pagep, *limit;
182	0	JSArena *a;
183	0	JSGCThing *thing;
184	0	JSGCPageInfo *pi;
185
186		/* Use JS_ArenaAllocate to grab another 9K-net-size hunk of space. */
187	0	flagp = (uint8 *) JS_ArenaAllocate(pool, GC_ARENA_SIZE);
188	0	if (!flagp)
189	0	return NULL;
190	0	a = pool->current;
191
192		/* Reset a->avail to start at the flags split, aka the first thing page. */
193	0	a->avail = FIRST_THING_PAGE(a);
194	0	split = pagep = (uint8 *) a->avail;
195	0	a->avail += sizeof(JSGCPageInfo);
196	0	thing = (JSGCThing *) a->avail;
197	0	a->avail += sizeof(JSGCThing);
198
199		/* Initialize the JSGCPageInfo records at the start of every thing page. */
200	0	limit = pagep + GC_THINGS_SIZE;
201	0	do {
202	0	pi = (JSGCPageInfo *) pagep;
203	0	pi->split = split;
204	0	pi->flags = flagp;
205	0	flagp += GC_PAGE_SIZE >> (GC_THINGS_SHIFT -  GC_PAGE_SHIFT);
206	0	pagep += GC_PAGE_SIZE;
207	0	} while (pagep < limit);
208	0	return thing;
209		}
210
211		uint8 *
212		js_GetGCThingFlags(void *thing)
213	0	{
214	0	JSGCPageInfo *pi;
215	0	uint8 *flagp;
216
217	0	pi = (JSGCPageInfo *) ((jsuword)thing & ~GC_PAGE_MASK);
218	0	flagp = pi->flags + ((jsuword)thing & GC_PAGE_MASK) / sizeof(JSGCThing);
219	0	if (flagp >= pi->split)
220	0	flagp += GC_THINGS_SIZE;
221	0	return flagp;
222		}
223
224		JSBool
225		js_IsAboutToBeFinalized(JSContext *cx, void *thing)
226	0	{
227	0	uint8 flags = *js_GetGCThingFlags(thing);
228
229	0	return !(flags & (GCF_MARK | GCF_LOCKMASK | GCF_FINAL));
230		}
231
232		typedef void (*GCFinalizeOp)(JSContext *cx, JSGCThing *thing);
233
234		static GCFinalizeOp gc_finalizers[GCX_NTYPES];
235
236		intN
237		js_ChangeExternalStringFinalizer(JSStringFinalizeOp oldop,
238		JSStringFinalizeOp newop)
239	0	{
240	0	uintN i;
241
242	0	for (i = GCX_EXTERNAL_STRING; i < GCX_NTYPES; i++) {
243	0	if (gc_finalizers[i] == (GCFinalizeOp) oldop) {
244	0	gc_finalizers[i] = (GCFinalizeOp) newop;
245	0	return (intN) i;
246		}
247		}
248	0	return -1;
249		}
250
251		#ifdef JS_GCMETER
252		#define METER(x) x
253		#else
254		#define METER(x) /* nothing */
255		#endif
256
257		/* Initial size of the gcRootsHash table (SWAG, small enough to amortize). */
258		#define GC_ROOTS_SIZE   256
259		#define GC_FINALIZE_LEN 1024
260
261		JSBool
262		js_InitGC(JSRuntime *rt, uint32 maxbytes)
263	0	{
264	0	JS_ASSERT(sizeof(JSGCThing) == sizeof(JSGCPageInfo));
265	0	JS_ASSERT(sizeof(JSGCThing) >= sizeof(JSObject));
266	0	JS_ASSERT(sizeof(JSGCThing) >= sizeof(JSString));
267	0	JS_ASSERT(sizeof(JSGCThing) >= sizeof(jsdouble));
268	0	JS_ASSERT(GC_FLAGS_SIZE >= GC_PAGE_SIZE);
269	0	JS_ASSERT(sizeof(JSStackHeader) >= 2 * sizeof(jsval));
270
271	0	if (!gc_finalizers[GCX_OBJECT]) {
272	0	gc_finalizers[GCX_OBJECT] = (GCFinalizeOp)js_FinalizeObject;
273	0	gc_finalizers[GCX_STRING] = (GCFinalizeOp)js_FinalizeString;
274		#ifdef DEBUG
275		gc_finalizers[GCX_DOUBLE] = (GCFinalizeOp)js_FinalizeDouble;
276		#endif
277	0	gc_finalizers[GCX_MUTABLE_STRING] = (GCFinalizeOp)js_FinalizeString;
278		}
279
280	0	JS_InitArenaPool(&rt->gcArenaPool, "gc-arena", GC_ARENA_SIZE,
281		sizeof(JSGCThing));
282	0	if (!JS_DHashTableInit(&rt->gcRootsHash, JS_DHashGetStubOps(), NULL,
283		sizeof(JSGCRootHashEntry), GC_ROOTS_SIZE)) {
284	0	rt->gcRootsHash.ops = NULL;
285	0	return JS_FALSE;
286		}
287	0	rt->gcLocksHash = NULL;     /* create lazily */
288	0	rt->gcMaxBytes = maxbytes;
289	0	return JS_TRUE;
290		}
291
292		#ifdef JS_GCMETER
293		void
294		js_DumpGCStats(JSRuntime *rt, FILE *fp)
295		{
296		fprintf(fp, "\nGC allocation statistics:\n");
297		fprintf(fp, "     bytes currently allocated: %lu\n", rt->gcBytes);
298		fprintf(fp, "                alloc attempts: %lu\n", rt->gcStats.alloc);
299		fprintf(fp, "            GC freelist length: %lu\n", rt->gcStats.freelen);
300		fprintf(fp, "  recycles through GC freelist: %lu\n", rt->gcStats.recycle);
301		fprintf(fp, "alloc retries after running GC: %lu\n", rt->gcStats.retry);
302		fprintf(fp, "           allocation failures: %lu\n", rt->gcStats.fail);
303		fprintf(fp, "              valid lock calls: %lu\n", rt->gcStats.lock);
304		fprintf(fp, "            valid unlock calls: %lu\n", rt->gcStats.unlock);
305		fprintf(fp, "   locks that hit stuck counts: %lu\n", rt->gcStats.stuck);
306		fprintf(fp, " unlocks that saw stuck counts: %lu\n", rt->gcStats.unstuck);
307		fprintf(fp, "          mark recursion depth: %lu\n", rt->gcStats.depth);
308		fprintf(fp, "  maximum mark recursion depth: %lu\n", rt->gcStats.maxdepth);
309		fprintf(fp, "      maximum GC nesting level: %lu\n", rt->gcStats.maxlevel);
310		fprintf(fp, "   potentially useful GC calls: %lu\n", rt->gcStats.poke);
311		fprintf(fp, "              useless GC calls: %lu\n", rt->gcStats.nopoke);
312		fprintf(fp, "     thing arenas freed so far: %lu\n", rt->gcStats.afree);
313		fprintf(fp, "  extra stack segments scanned: %lu\n", rt->gcStats.stackseg);
314		fprintf(fp, "   stack segment slots scanned: %lu\n", rt->gcStats.segslots);
315		#ifdef JS_ARENAMETER
316		JS_DumpArenaStats(fp);
317		#endif
318		}
319		#endif
320
321		#ifdef DEBUG
322		JS_STATIC_DLL_CALLBACK(JSDHashOperator)
323		js_root_printer(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 i, void *arg)
324		{
325		uint32 *leakedroots = (uint32 *)arg;
326		JSGCRootHashEntry *rhe = (JSGCRootHashEntry *)hdr;
327
328		(*leakedroots)++;
329		fprintf(stderr,
330		"JS engine warning: leaking GC root \'%s\' at %p\n",
331		rhe->name ? (char *)rhe->name : "", rhe->root);
332
333		return JS_DHASH_NEXT;
334		}
335		#endif
336
337		void
338		js_FinishGC(JSRuntime *rt)
339	0	{
340		#ifdef JS_ARENAMETER
341		JS_DumpArenaStats(stdout);
342		#endif
343		#ifdef JS_GCMETER
344		js_DumpGCStats(rt, stdout);
345		#endif
346	0	JS_FinishArenaPool(&rt->gcArenaPool);
347	0	JS_ArenaFinish();
348
349	0	if (rt->gcRootsHash.ops) {
350		#ifdef DEBUG
351		uint32 leakedroots = 0;
352
353		/* Warn (but don't assert) debug builds of any remaining roots. */
354		JS_DHashTableEnumerate(&rt->gcRootsHash, js_root_printer,
355		&leakedroots);
356		if (leakedroots > 0) {
357		if (leakedroots == 1) {
358		fprintf(stderr,
359		"JS engine warning: 1 GC root remains after destroying the JSRuntime.\n"
360		"                   This root may point to freed memory. Objects reachable\n"
361		"                   through it have not been finalized.\n");
362		} else {
363		fprintf(stderr,
364		"JS engine warning: %lu GC roots remain after destroying the JSRuntime.\n"
365		"                   These roots may point to freed memory. Objects reachable\n"
366		"                   through them have not been finalized.\n",
367		(unsigned long) leakedroots);
368		}
369		}
370		#endif
371
372	0	JS_DHashTableFinish(&rt->gcRootsHash);
373	0	rt->gcRootsHash.ops = NULL;
374		}
375	0	if (rt->gcLocksHash) {
376	0	JS_DHashTableDestroy(rt->gcLocksHash);
377	0	rt->gcLocksHash = NULL;
378		}
379	0	rt->gcFreeList = NULL;
380		}
381
382		JSBool
383		js_AddRoot(JSContext *cx, void *rp, const char *name)
384	0	{
385	0	JSBool ok = js_AddRootRT(cx->runtime, rp, name);
386	0	if (!ok)
387	0	JS_ReportOutOfMemory(cx);
388	0	return ok;
389		}
390
391		JSBool
392		js_AddRootRT(JSRuntime *rt, void *rp, const char *name)
393	0	{
394	0	JSBool ok;
395	0	JSGCRootHashEntry *rhe;
396
397		/*
398		* Due to the long-standing, but now removed, use of rt->gcLock across the
399		* bulk of js_GC, API users have come to depend on JS_AddRoot etc. locking
400		* properly with a racing GC, without calling JS_AddRoot from a request.
401		* We have to preserve API compatibility here, now that we avoid holding
402		* rt->gcLock across the mark phase (including the root hashtable mark).
403		*
404		* If the GC is running and we're called on another thread, wait for this
405		* GC activation to finish.  We can safely wait here (in the case where we
406		* are called within a request on another thread's context) without fear
407		* of deadlock because the GC doesn't set rt->gcRunning until after it has
408		* waited for all active requests to end.
409		*/
410	0	JS_LOCK_GC(rt);
411		#ifdef JS_THREADSAFE
412		JS_ASSERT(!rt->gcRunning || rt->gcLevel > 0);
413		if (rt->gcRunning && rt->gcThread != js_CurrentThreadId()) {
414		do {
415		JS_AWAIT_GC_DONE(rt);
416		} while (rt->gcLevel > 0);
417		}
418		#endif
419	0	rhe = (JSGCRootHashEntry *) JS_DHashTableOperate(&rt->gcRootsHash, rp,
420		JS_DHASH_ADD);
421	0	if (rhe) {
422	0	rhe->root = rp;
423	0	rhe->name = name;
424	0	ok = JS_TRUE;
425		} else {
426	0	ok = JS_FALSE;
427		}
428	0	JS_UNLOCK_GC(rt);
429	0	return ok;
430		}
431
432		JSBool
433		js_RemoveRoot(JSRuntime *rt, void *rp)
434	0	{
435		/*
436		* Due to the JS_RemoveRootRT API, we may be called outside of a request.
437		* Same synchronization drill as above in js_AddRoot.
438		*/
439	0	JS_LOCK_GC(rt);
440		#ifdef JS_THREADSAFE
441		JS_ASSERT(!rt->gcRunning || rt->gcLevel > 0);
442		if (rt->gcRunning && rt->gcThread != js_CurrentThreadId()) {
443		do {
444		JS_AWAIT_GC_DONE(rt);
445		} while (rt->gcLevel > 0);
446		}
447		#endif
448	0	(void) JS_DHashTableOperate(&rt->gcRootsHash, rp, JS_DHASH_REMOVE);
449	0	rt->gcPoke = JS_TRUE;
450	0	JS_UNLOCK_GC(rt);
451	0	return JS_TRUE;
452		}
453
454		void *
455		js_AllocGCThing(JSContext *cx, uintN flags)
456	0	{
457	0	JSBool tried_gc;
458	0	JSRuntime *rt;
459	0	JSGCThing *thing;
460	0	uint8 *flagp;
461
462		#ifdef TOO_MUCH_GC
463		js_GC(cx, GC_KEEP_ATOMS);
464		tried_gc = JS_TRUE;
465		#else
466	0	tried_gc = JS_FALSE;
467		#endif
468
469	0	rt = cx->runtime;
470	0	JS_LOCK_GC(rt);
471	0	JS_ASSERT(!rt->gcRunning);
472	0	if (rt->gcRunning) {
473		METER(rt->gcStats.finalfail++);
474	0	JS_UNLOCK_GC(rt);
475	0	return NULL;
476		}
477		METER(rt->gcStats.alloc++);
478		retry:
479	0	thing = rt->gcFreeList;
480	0	if (thing) {
481	0	rt->gcFreeList = thing->next;
482	0	flagp = thing->flagp;
483		METER(rt->gcStats.freelen--);
484		METER(rt->gcStats.recycle++);
485		} else {
486	0	if (rt->gcBytes < rt->gcMaxBytes &&
487		(tried_gc || rt->gcMallocBytes < rt->gcMaxBytes))
488		{
489		/*
490		* Inline form of JS_ARENA_ALLOCATE adapted to truncate the current
491		* arena's limit to a GC_PAGE_SIZE boundary, and to skip over every
492		* GC_PAGE_SIZE-byte-aligned thing (which is actually not a thing,
493		* it's a JSGCPageInfo record).
494		*/
495	0	JSArenaPool *pool = &rt->gcArenaPool;
496	0	JSArena *a = pool->current;
497	0	size_t nb = sizeof(JSGCThing);
498	0	jsuword p = a->avail;
499	0	jsuword q = p + nb;
500
501	0	if (q > (a->limit & ~GC_PAGE_MASK)) {
502	0	thing = gc_new_arena(pool);
503		} else {
504	0	if ((p & GC_PAGE_MASK) == 0) {
505		/* Beware, p points to a JSGCPageInfo record! */
506	0	p = q;
507	0	q += nb;
508		JS_ArenaCountAllocation(pool, nb);
509		}
510	0	a->avail = q;
511	0	thing = (JSGCThing *)p;
512		}
513		JS_ArenaCountAllocation(pool, nb);
514		}
515
516		/*
517		* Consider doing a "last ditch" GC if thing couldn't be allocated.
518		*
519		* Keep rt->gcLock across the call into js_GC so we don't starve and
520		* lose to racing threads who deplete the heap just after js_GC has
521		* replenished it (or has synchronized with a racing GC that collected
522		* a bunch of garbage).  This unfair scheduling can happen on certain
523		* operating systems.  For the gory details, see Mozilla bug 162779
524		* (http://bugzilla.mozilla.org/show_bug.cgi?id=162779).
525		*/
526	0	if (!thing) {
527	0	if (!tried_gc) {
528	0	rt->gcPoke = JS_TRUE;
529	0	js_GC(cx, GC_KEEP_ATOMS | GC_ALREADY_LOCKED);
530	0	tried_gc = JS_TRUE;
531		METER(rt->gcStats.retry++);
532	0	goto retry;
533		}
534		METER(rt->gcStats.fail++);
535	0	JS_UNLOCK_GC(rt);
536	0	JS_ReportOutOfMemory(cx);
537	0	return NULL;
538		}
539
540		/* Find the flags pointer given thing's address. */
541	0	flagp = js_GetGCThingFlags(thing);
542		}
543	0	*flagp = (uint8)flags;
544	0	rt->gcBytes += sizeof(JSGCThing) + sizeof(uint8);
545	0	cx->newborn[flags & GCF_TYPEMASK] = thing;
546
547		/*
548		* Clear thing before unlocking in case a GC run is about to scan it,
549		* finding it via cx->newborn[].
550		*/
551	0	thing->next = NULL;
552	0	thing->flagp = NULL;
553	0	JS_UNLOCK_GC(rt);
554	0	return thing;
555		}
556
557		JSBool
558		js_LockGCThing(JSContext *cx, void *thing)
559	0	{
560	0	JSBool ok = js_LockGCThingRT(cx->runtime, thing);
561	0	if (!ok)
562	0	JS_ReportOutOfMemory(cx);
563	0	return ok;
564		}
565
566		JSBool
567		js_LockGCThingRT(JSRuntime *rt, void *thing)
568	0	{
569	0	uint8 *flagp, flags, lockbits;
570	0	JSBool ok;
571	0	JSGCLockHashEntry *lhe;
572
573	0	if (!thing)
574	0	return JS_TRUE;
575	0	flagp = js_GetGCThingFlags(thing);
576	0	flags = *flagp;
577
578	0	ok = JS_FALSE;
579	0	JS_LOCK_GC(rt);
580	0	lockbits = (flags & GCF_LOCKMASK);
581
582	0	if (lockbits != GCF_LOCKMASK) {
583	0	if ((flags & GCF_TYPEMASK) == GCX_OBJECT) {
584		/* Objects may require "deep locking", i.e., rooting by value. */
585	0	if (lockbits == 0) {
586	0	if (!rt->gcLocksHash) {
587	0	rt->gcLocksHash =
588		JS_NewDHashTable(JS_DHashGetStubOps(), NULL,
589		sizeof(JSGCLockHashEntry),
590		GC_ROOTS_SIZE);
591	0	if (!rt->gcLocksHash)
592	0	goto error;
593		} else {
594		#ifdef DEBUG
595		JSDHashEntryHdr *hdr =
596		JS_DHashTableOperate(rt->gcLocksHash, thing,
597		JS_DHASH_LOOKUP);
598		JS_ASSERT(JS_DHASH_ENTRY_IS_FREE(hdr));
599		#endif
600		}
601	0	lhe = (JSGCLockHashEntry *)
602		JS_DHashTableOperate(rt->gcLocksHash, thing, JS_DHASH_ADD);
603	0	if (!lhe)
604	0	goto error;
605	0	lhe->thing = thing;
606	0	lhe->count = 1;
607	0	*flagp = (uint8)(flags + GCF_LOCK);
608		} else {
609	0	JS_ASSERT(lockbits == GCF_LOCK);
610	0	lhe = (JSGCLockHashEntry *)
611		JS_DHashTableOperate(rt->gcLocksHash, thing,
612		JS_DHASH_LOOKUP);
613	0	JS_ASSERT(JS_DHASH_ENTRY_IS_BUSY(&lhe->hdr));
614	0	if (JS_DHASH_ENTRY_IS_BUSY(&lhe->hdr)) {
615	0	JS_ASSERT(lhe->count >= 1);
616	0	lhe->count++;
617		}
618		}
619		} else {
620	0	*flagp = (uint8)(flags + GCF_LOCK);
621		}
622		} else {
623		METER(rt->gcStats.stuck++);
624		}
625
626		METER(rt->gcStats.lock++);
627	0	ok = JS_TRUE;
628		error:
629	0	JS_UNLOCK_GC(rt);
630	0	return ok;
631		}
632
633		JSBool
634		js_UnlockGCThingRT(JSRuntime *rt, void *thing)
635	0	{
636	0	uint8 *flagp, flags, lockbits;
637	0	JSGCLockHashEntry *lhe;
638
639	0	if (!thing)
640	0	return JS_TRUE;
641	0	flagp = js_GetGCThingFlags(thing);
642	0	flags = *flagp;
643
644	0	JS_LOCK_GC(rt);
645	0	lockbits = (flags & GCF_LOCKMASK);
646
647	0	if (lockbits != GCF_LOCKMASK) {
648	0	if ((flags & GCF_TYPEMASK) == GCX_OBJECT) {
649		/* Defend against a call on an unlocked object. */
650	0	if (lockbits != 0) {
651	0	JS_ASSERT(lockbits == GCF_LOCK);
652	0	lhe = (JSGCLockHashEntry *)
653		JS_DHashTableOperate(rt->gcLocksHash, thing,
654		JS_DHASH_LOOKUP);
655	0	JS_ASSERT(JS_DHASH_ENTRY_IS_BUSY(&lhe->hdr));
656	0	if (JS_DHASH_ENTRY_IS_BUSY(&lhe->hdr) &&
657		--lhe->count == 0) {
658	0	(void) JS_DHashTableOperate(rt->gcLocksHash, thing,
659		JS_DHASH_REMOVE);
660	0	*flagp = (uint8)(flags & ~GCF_LOCKMASK);
661		}
662		}
663		} else {
664	0	*flagp = (uint8)(flags - GCF_LOCK);
665		}
666		} else {
667		METER(rt->gcStats.unstuck++);
668		}
669
670	0	rt->gcPoke = JS_TRUE;
671		METER(rt->gcStats.unlock++);
672	0	JS_UNLOCK_GC(rt);
673	0	return JS_TRUE;
674		}
675
676		#ifdef GC_MARK_DEBUG
677
678		#include <stdio.h>
679		#include <stdlib.h>
680		#include "jsprf.h"
681
682		JS_FRIEND_DATA(FILE *) js_DumpGCHeap;
683		JS_EXPORT_DATA(void *) js_LiveThingToFind;
684
685		#ifdef HAVE_XPCONNECT
686		#include "dump_xpc.h"
687		#endif
688
689		static const char *
690		gc_object_class_name(void* thing)
691		{
692		uint8 *flagp = js_GetGCThingFlags(thing);
693		const char *className = "";
694		static char depbuf[32];
695
696		switch (*flagp & GCF_TYPEMASK) {
697		case GCX_OBJECT: {
698		JSObject  *obj = (JSObject *)thing;
699		JSClass   *clasp = JSVAL_TO_PRIVATE(obj->slots[JSSLOT_CLASS]);
700		className = clasp->name;
701		#ifdef HAVE_XPCONNECT
702		if (clasp->flags & JSCLASS_PRIVATE_IS_NSISUPPORTS) {
703		jsval privateValue = obj->slots[JSSLOT_PRIVATE];
704
705		JS_ASSERT(clasp->flags & JSCLASS_HAS_PRIVATE);
706		if (!JSVAL_IS_VOID(privateValue)) {
707		void  *privateThing = JSVAL_TO_PRIVATE(privateValue);
708		const char *xpcClassName = GetXPCObjectClassName(privateThing);
709
710		if (xpcClassName)
711		className = xpcClassName;
712		}
713		}
714		#endif
715		break;
716		}
717
718		case GCX_STRING:
719		case GCX_MUTABLE_STRING: {
720		JSString *str = (JSString *)thing;
721		if (JSSTRING_IS_DEPENDENT(str)) {
722		JS_snprintf(depbuf, sizeof depbuf, "start:%u, length:%u",
723		JSSTRDEP_START(str), JSSTRDEP_LENGTH(str));
724		className = depbuf;
725		} else {
726		className = "string";
727		}
728		break;
729		}
730
731		case GCX_DOUBLE:
732		className = "double";
733		break;
734		}
735
736		return className;
737		}
738
739		static void
740		gc_dump_thing(JSGCThing *thing, uint8 flags, GCMarkNode *prev, FILE *fp)
741		{
742		GCMarkNode *next = NULL;
743		char *path = NULL;
744
745		while (prev) {
746		next = prev;
747		prev = prev->prev;
748		}
749		while (next) {
750		path = JS_sprintf_append(path, "%s(%s).",
751		next->name,
752		gc_object_class_name(next->thing));
753		next = next->next;
754		}
755		if (!path)
756		return;
757
758		fprintf(fp, "%08lx ", (long)thing);
759		switch (flags & GCF_TYPEMASK) {
760		case GCX_OBJECT:
761		{
762		JSObject  *obj = (JSObject *)thing;
763		jsval     privateValue = obj->slots[JSSLOT_PRIVATE];
764		void      *privateThing = JSVAL_IS_VOID(privateValue)
765		? NULL
766		: JSVAL_TO_PRIVATE(privateValue);
767		const char *className = gc_object_class_name(thing);
768		fprintf(fp, "object %8p %s", privateThing, className);
769		break;
770		}
771		case GCX_DOUBLE:
772		fprintf(fp, "double %g", *(jsdouble *)thing);
773		break;
774		default:
775		fprintf(fp, "string %s", JS_GetStringBytes((JSString *)thing));
776		break;
777		}
778		fprintf(fp, " via %s\n", path);
779		free(path);
780		}
781
782		#endif /* !GC_MARK_DEBUG */
783
784		static void
785		gc_mark_atom_key_thing(void *thing, void *arg)
786	0	{
787	0	JSContext *cx = (JSContext *) arg;
788
789	0	GC_MARK(cx, thing, "atom", NULL);
790		}
791
792		void
793		js_MarkAtom(JSContext *cx, JSAtom *atom, void *arg)
794	0	{
795	0	jsval key;
796
797	0	if (atom->flags & ATOM_MARK)
798	0	return;
799	0	atom->flags |= ATOM_MARK;
800	0	key = ATOM_KEY(atom);
801	0	if (JSVAL_IS_GCTHING(key)) {
802		#ifdef GC_MARK_DEBUG
803		char name[32];
804
805		if (JSVAL_IS_STRING(key)) {
806		JS_snprintf(name, sizeof name, "'%s'",
807		JS_GetStringBytes(JSVAL_TO_STRING(key)));
808		} else {
809		JS_snprintf(name, sizeof name, "<%x>", key);
810		}
811		#endif
812	0	GC_MARK(cx, JSVAL_TO_GCTHING(key), name, arg);
813		}
814		}
815
816		void
817		js_MarkGCThing(JSContext *cx, void *thing, void *arg)
818	0	{
819	0	uint8 flags, *flagp;
820	0	JSRuntime *rt;
821	0	JSObject *obj;
822	0	uint32 nslots;
823	0	jsval v, *vp, *end;
824	0	JSString *str;
825		#ifdef GC_MARK_DEBUG
826		JSScope *scope;
827		JSScopeProperty *sprop;
828		#endif
829
830	0	if (!thing)
831	0	return;
832
833	0	flagp = js_GetGCThingFlags(thing);
834	0	flags = *flagp;
835	0	JS_ASSERT(flags != GCF_FINAL);
836		#ifdef GC_MARK_DEBUG
837		if (js_LiveThingToFind == thing)
838		gc_dump_thing(thing, flags, arg, stderr);
839		#endif
840
841	0	if (flags & GCF_MARK)
842	0	return;
843
844	0	*flagp |= GCF_MARK;
845	0	rt = cx->runtime;
846		METER(if (++rt->gcStats.depth > rt->gcStats.maxdepth)
847		rt->gcStats.maxdepth = rt->gcStats.depth);
848
849		#ifdef GC_MARK_DEBUG
850		if (js_DumpGCHeap)
851		gc_dump_thing(thing, flags, arg, js_DumpGCHeap);
852		#endif
853
854	0	switch (flags & GCF_TYPEMASK) {
855		case GCX_OBJECT:
856	0	obj = (JSObject *) thing;
857	0	vp = obj->slots;
858	0	if (!vp) {
859		/* If obj->slots is null, obj must be a newborn. */
860	0	JS_ASSERT(!obj->map);
861	0	goto out;
862		}
863	0	nslots = (obj->map->ops->mark)
864		? obj->map->ops->mark(cx, obj, arg)
865		: JS_MIN(obj->map->freeslot, obj->map->nslots);
866		#ifdef GC_MARK_DEBUG
867		scope = OBJ_IS_NATIVE(obj) ? OBJ_SCOPE(obj) : NULL;
868		#endif
869	0	for (end = vp + nslots; vp < end; vp++) {
870	0	v = *vp;
871	0	if (JSVAL_IS_GCTHING(v)) {
872		#ifdef GC_MARK_DEBUG
873		char name[32];
874
875		if (scope) {
876		uint32 slot;
877		jsval nval;
878
879		slot = vp - obj->slots;
880		for (sprop = SCOPE_LAST_PROP(scope); ;
881		sprop = sprop->parent) {
882		if (!sprop) {
883		switch (slot) {
884		case JSSLOT_PROTO:
885		strcpy(name, "__proto__");
886		break;
887		case JSSLOT_PARENT:
888		strcpy(name, "__parent__");
889		break;
890		case JSSLOT_PRIVATE:
891		strcpy(name, "__private__");
892		break;
893		default:
894		JS_snprintf(name, sizeof name,
895		"**UNKNOWN SLOT %ld**",
896		(long)slot);
897		break;
898		}
899		break;
900		}
901		if (sprop->slot == slot) {
902		nval = ID_TO_VALUE(sprop->id);
903		if (JSVAL_IS_INT(nval)) {
904		JS_snprintf(name, sizeof name, "%ld",
905		(long)JSVAL_TO_INT(nval));
906		} else if (JSVAL_IS_STRING(nval)) {
907		JS_snprintf(name, sizeof name, "%s",
908		JS_GetStringBytes(JSVAL_TO_STRING(nval)));
909		} else {
910		strcpy(name, "**FINALIZED ATOM KEY**");
911		}
912		break;
913		}
914		}
915		} else {
916		strcpy(name, "**UNKNOWN OBJECT MAP ENTRY**");
917		}
918		#endif
919	0	GC_MARK(cx, JSVAL_TO_GCTHING(v), name, arg);
920		}
921		}
922	0	break;
923
924		#ifdef DEBUG
925		case GCX_STRING:
926		str = (JSString *)thing;
927		JS_ASSERT(!JSSTRING_IS_DEPENDENT(str));
928		break;
929		#endif
930
931		case GCX_MUTABLE_STRING:
932	0	str = (JSString *)thing;
933	0	if (JSSTRING_IS_DEPENDENT(str))
934	0	GC_MARK(cx, JSSTRDEP_BASE(str), "base", arg);
935		break;
936		}
937
938		out:
939		METER(rt->gcStats.depth--);
940		}
941
942		JS_STATIC_DLL_CALLBACK(JSDHashOperator)
943		gc_root_marker(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 num, void *arg)
944	0	{
945	0	JSGCRootHashEntry *rhe = (JSGCRootHashEntry *)hdr;
946	0	jsval *rp = (jsval *)rhe->root;
947	0	jsval v = *rp;
948
949		/* Ignore null object and scalar values. */
950	0	if (!JSVAL_IS_NULL(v) && JSVAL_IS_GCTHING(v)) {
951	0	JSContext *cx = (JSContext *)arg;
952		#ifdef DEBUG
953		JSArena *a;
954		jsuword firstpage;
955		JSBool root_points_to_gcArenaPool = JS_FALSE;
956		void *thing = JSVAL_TO_GCTHING(v);
957
958		for (a = cx->runtime->gcArenaPool.first.next; a; a = a->next) {
959		firstpage = FIRST_THING_PAGE(a);
960		if (JS_UPTRDIFF(thing, firstpage) < a->avail - firstpage) {
961		root_points_to_gcArenaPool = JS_TRUE;
962		break;
963		}
964		}
965		if (!root_points_to_gcArenaPool && rhe->name) {
966		fprintf(stderr,
967		"JS API usage error: the address passed to JS_AddNamedRoot currently holds an\n"
968		"invalid jsval.  This is usually caused by a missing call to JS_RemoveRoot.\n"
969		"The root's name is \"%s\".\n",
970		rhe->name);
971		}
972		JS_ASSERT(root_points_to_gcArenaPool);
973		#endif
974
975	0	GC_MARK(cx, JSVAL_TO_GCTHING(v), rhe->name ? rhe->name : "root", NULL);
976		}
977	0	return JS_DHASH_NEXT;
978		}
979
980		JS_STATIC_DLL_CALLBACK(JSDHashOperator)
981		gc_lock_marker(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 num, void *arg)
982	0	{
983	0	JSGCLockHashEntry *lhe = (JSGCLockHashEntry *)hdr;
984	0	void *thing = (void *)lhe->thing;
985	0	JSContext *cx = (JSContext *)arg;
986
987	0	GC_MARK(cx, thing, "locked object", NULL);
988	0	return JS_DHASH_NEXT;
989		}
990
991		void
992		js_ForceGC(JSContext *cx, uintN gcflags)
993	0	{
994	0	uintN i;
995
996	0	for (i = 0; i < GCX_NTYPES; i++)
997	0	cx->newborn[i] = NULL;
998	0	cx->lastAtom = NULL;
999	0	cx->runtime->gcPoke = JS_TRUE;
1000	0	js_GC(cx, gcflags);
1001	0	JS_ArenaFinish();
1002		}
1003
1004		#define GC_MARK_JSVALS(cx, len, vec, name)                                    \
1005		JS_BEGIN_MACRO                                                            \
1006		jsval _v, *_vp, *_end;                                                \
1007		\
1008		for (_vp = vec, _end = _vp + len; _vp < _end; _vp++) {                \
1009		_v = *_vp;                                                        \
1010		if (JSVAL_IS_GCTHING(_v))                                         \
1011		GC_MARK(cx, JSVAL_TO_GCTHING(_v), name, NULL);                \
1012		}                                                                     \
1013		JS_END_MACRO
1014
1015		void
1016		js_GC(JSContext *cx, uintN gcflags)
1017	0	{
1018	0	JSRuntime *rt;
1019	0	JSContext *iter, *acx;
1020	0	JSStackFrame *fp, *chain;
1021	0	uintN i, depth, nslots, type;
1022	0	JSStackHeader *sh;
1023	0	JSArena *a, **ap;
1024	0	uint8 flags, *flagp, *split;
1025	0	JSGCThing *thing, *limit, **flp, **oflp;
1026	0	GCFinalizeOp finalizer;
1027	0	JSBool all_clear;
1028		#ifdef JS_THREADSAFE
1029		jsword currentThread;
1030		uint32 requestDebit;
1031		#endif
1032
1033	0	rt = cx->runtime;
1034		#ifdef JS_THREADSAFE
1035		/* Avoid deadlock. */
1036		JS_ASSERT(!JS_IS_RUNTIME_LOCKED(rt));
1037		#endif
1038
1039		/*
1040		* Don't collect garbage if the runtime isn't up, and cx is not the last
1041		* context in the runtime.  The last context must force a GC, and nothing
1042		* should suppress that final collection or there may be shutdown leaks,
1043		* or runtime bloat until the next context is created.
1044		*/
1045	0	if (rt->state != JSRTS_UP && !(gcflags & GC_LAST_CONTEXT))
1046	0	return;
1047
1048		/*
1049		* Let the API user decide to defer a GC if it wants to (unless this
1050		* is the last context).  Invoke the callback regardless.
1051		*/
1052	0	if (rt->gcCallback) {
1053	0	if (!rt->gcCallback(cx, JSGC_BEGIN) && !(gcflags & GC_LAST_CONTEXT))
1054	0	return;
1055		}
1056
1057		/* Lock out other GC allocator and collector invocations. */
1058	0	if (!(gcflags & GC_ALREADY_LOCKED))
1059	0	JS_LOCK_GC(rt);
1060
1061		/* Do nothing if no assignment has executed since the last GC. */
1062	0	if (!rt->gcPoke) {
1063		METER(rt->gcStats.nopoke++);
1064	0	if (!(gcflags & GC_ALREADY_LOCKED))
1065	0	JS_UNLOCK_GC(rt);
1066	0	return;
1067		}
1068		METER(rt->gcStats.poke++);
1069
1070		#ifdef JS_THREADSAFE
1071		/* Bump gcLevel and return rather than nest on this thread. */
1072		currentThread = js_CurrentThreadId();
1073		if (rt->gcThread == currentThread) {
1074		JS_ASSERT(rt->gcLevel > 0);
1075		rt->gcLevel++;
1076		METER(if (rt->gcLevel > rt->gcStats.maxlevel)
1077		rt->gcStats.maxlevel = rt->gcLevel);
1078		if (!(gcflags & GC_ALREADY_LOCKED))
1079		JS_UNLOCK_GC(rt);
1080		return;
1081		}
1082
1083		/*
1084		* If we're in one or more requests (possibly on more than one context)
1085		* running on the current thread, indicate, temporarily, that all these
1086		* requests are inactive.  NB: if cx->thread is 0, then cx is not using
1087		* the request model, and does not contribute to rt->requestCount.
1088		*/
1089		requestDebit = 0;
1090		if (cx->thread) {
1091		/*
1092		* Check all contexts for any with the same thread-id.  XXX should we
1093		* keep a sub-list of contexts having the same id?
1094		*/
1095		iter = NULL;
1096		while ((acx = js_ContextIterator(rt, JS_FALSE, &iter)) != NULL) {
1097		if (acx->thread == cx->thread && acx->requestDepth)
1098		requestDebit++;
1099		}
1100		} else {
1101		/*
1102		* We assert, but check anyway, in case someone is misusing the API.
1103		* Avoiding the loop over all of rt's contexts is a win in the event
1104		* that the GC runs only on request-less contexts with 0 thread-ids,
1105		* in a special thread such as might be used by the UI/DOM/Layout
1106		* "mozilla" or "main" thread in Mozilla-the-browser.
1107		*/
1108		JS_ASSERT(cx->requestDepth == 0);
1109		if (cx->requestDepth)
1110		requestDebit = 1;
1111		}
1112		if (requestDebit) {
1113		JS_ASSERT(requestDebit <= rt->requestCount);
1114		rt->requestCount -= requestDebit;
1115		if (rt->requestCount == 0)
1116		JS_NOTIFY_REQUEST_DONE(rt);
1117		}
1118
1119		/* If another thread is already in GC, don't attempt GC; wait instead. */
1120		if (rt->gcLevel > 0) {
1121		/* Bump gcLevel to restart the current GC, so it finds new garbage. */
1122		rt->gcLevel++;
1123		METER(if (rt->gcLevel > rt->gcStats.maxlevel)
1124		rt->gcStats.maxlevel = rt->gcLevel);
1125
1126		/* Wait for the other thread to finish, then resume our request. */
1127		while (rt->gcLevel > 0)
1128		JS_AWAIT_GC_DONE(rt);
1129		if (requestDebit)
1130		rt->requestCount += requestDebit;
1131		if (!(gcflags & GC_ALREADY_LOCKED))
1132		JS_UNLOCK_GC(rt);
1133		return;
1134		}
1135
1136		/* No other thread is in GC, so indicate that we're now in GC. */
1137		rt->gcLevel = 1;
1138		rt->gcThread = currentThread;
1139
1140		/* Wait for all other requests to finish. */
1141		while (rt->requestCount > 0)
1142		JS_AWAIT_REQUEST_DONE(rt);
1143
1144		#else  /* !JS_THREADSAFE */
1145
1146		/* Bump gcLevel and return rather than nest; the outer gc will restart. */
1147	0	rt->gcLevel++;
1148		METER(if (rt->gcLevel > rt->gcStats.maxlevel)
1149		rt->gcStats.maxlevel = rt->gcLevel);
1150	0	if (rt->gcLevel > 1)
1151	0	return;
1152
1153		#endif /* !JS_THREADSAFE */
1154
1155		/*
1156		* Set rt->gcRunning here within the GC lock, and after waiting for any
1157		* active requests to end, so that new requests that try to JS_AddRoot,
1158		* JS_RemoveRoot, or JS_RemoveRootRT block in JS_BeginRequest waiting for
1159		* rt->gcLevel to drop to zero, while request-less calls to the *Root*
1160		* APIs block in js_AddRoot or js_RemoveRoot (see above in this file),
1161		* waiting for GC to finish.
1162		*/
1163	0	rt->gcRunning = JS_TRUE;
1164	0	JS_UNLOCK_GC(rt);
1165
1166		/* If a suspended compile is running on another context, keep atoms. */
1167	0	if (rt->gcKeepAtoms)
1168	0	gcflags |= GC_KEEP_ATOMS;
1169
1170		/* Reset malloc counter. */
1171	0	rt->gcMallocBytes = 0;
1172
1173		/* Drop atoms held by the property cache, and clear property weak links. */
1174	0	js_DisablePropertyCache(cx);
1175	0	js_FlushPropertyCache(cx);
1176		#ifdef DEBUG_brendan
1177		{ extern void js_DumpScopeMeters(JSRuntime *rt);
1178		js_DumpScopeMeters(rt);
1179		}
1180		#endif
1181
1182		restart:
1183	0	rt->gcNumber++;
1184
1185		/*
1186		* Mark phase.
1187		*/
1188	0	JS_DHashTableEnumerate(&rt->gcRootsHash, gc_root_marker, cx);
1189	0	if (rt->gcLocksHash)
1190	0	JS_DHashTableEnumerate(rt->gcLocksHash, gc_lock_marker, cx);
1191	0	js_MarkAtomState(&rt->atomState, gcflags, gc_mark_atom_key_thing, cx);
1192	0	js_MarkWatchPoints(rt);
1193	0	iter = NULL;
1194	0	while ((acx = js_ContextIterator(rt, JS_TRUE, &iter)) != NULL) {
1195		/*
1196		* Iterate frame chain and dormant chains. Temporarily tack current
1197		* frame onto the head of the dormant list to ease iteration.
1198		*
1199		* (NB: see comment on this whole "dormant" thing in js_Execute.)
1200		*/
1201	0	chain = acx->fp;
1202	0	if (chain) {
1203	0	JS_ASSERT(!chain->dormantNext);
1204	0	chain->dormantNext = acx->dormantFrameChain;
1205		} else {
1206	0	chain = acx->dormantFrameChain;
1207		}
1208
1209	0	for (fp = chain; fp; fp = chain = chain->dormantNext) {
1210	0	do {
1211	0	if (fp->callobj)
1212	0	GC_MARK(cx, fp->callobj, "call object", NULL);
1213	0	if (fp->argsobj)
1214	0	GC_MARK(cx, fp->argsobj, "arguments object", NULL);
1215	0	if (fp->varobj)
1216	0	GC_MARK(cx, fp->varobj, "variables object", NULL);
1217	0	if (fp->script) {
1218	0	js_MarkScript(cx, fp->script, NULL);
1219	0	if (fp->spbase) {
1220		/*
1221		* Don't mark what has not been pushed yet, or what
1222		* has been popped already.
1223		*/
1224	0	depth = fp->script->depth;
1225	0	nslots = (JS_UPTRDIFF(fp->sp, fp->spbase)
1226		< depth * sizeof(jsval))
1227		? (uintN)(fp->sp - fp->spbase)
1228		: depth;
1229	0	GC_MARK_JSVALS(cx, nslots, fp->spbase, "operand");
1230		}
1231		}
1232	0	GC_MARK(cx, fp->thisp, "this", NULL);
1233	0	if (fp->argv) {
1234	0	nslots = fp->argc;
1235	0	if (fp->fun && fp->fun->nargs > nslots)
1236	0	nslots = fp->fun->nargs;
1237	0	GC_MARK_JSVALS(cx, nslots, fp->argv, "arg");
1238		}
1239	0	if (JSVAL_IS_GCTHING(fp->rval))
1240	0	GC_MARK(cx, JSVAL_TO_GCTHING(fp->rval), "rval", NULL);
1241	0	if (fp->vars)
1242	0	GC_MARK_JSVALS(cx, fp->nvars, fp->vars, "var");
1243	0	GC_MARK(cx, fp->scopeChain, "scope chain", NULL);
1244	0	if (fp->sharpArray)
1245	0	GC_MARK(cx, fp->sharpArray, "sharp array", NULL);
1246
1247	0	if (fp->objAtomMap) {
1248	0	JSAtom **vector, *atom;
1249
1250	0	nslots = fp->objAtomMap->length;
1251	0	vector = fp->objAtomMap->vector;
1252	0	for (i = 0; i < nslots; i++) {
1253	0	atom = vector[i];
1254	0	if (atom)
1255	0	GC_MARK_ATOM(cx, atom, NULL);
1256		}
1257		}
1258	0	} while ((fp = fp->down) != NULL);
1259		}
1260
1261		/* Cleanup temporary "dormant" linkage. */
1262	0	if (acx->fp)
1263	0	acx->fp->dormantNext = NULL;
1264
1265		/* Mark other roots-by-definition in acx. */
1266	0	GC_MARK(cx, acx->globalObject, "global object", NULL);
1267	0	GC_MARK(cx, acx->newborn[GCX_OBJECT], "newborn object", NULL);
1268	0	GC_MARK(cx, acx->newborn[GCX_STRING], "newborn string", NULL);
1269	0	GC_MARK(cx, acx->newborn[GCX_DOUBLE], "newborn double", NULL);
1270	0	GC_MARK(cx, acx->newborn[GCX_MUTABLE_STRING], "newborn mutable string",
1271		NULL);
1272	0	for (i = GCX_EXTERNAL_STRING; i < GCX_NTYPES; i++)
1273	0	GC_MARK(cx, acx->newborn[i], "newborn external string", NULL);
1274	0	if (acx->lastAtom)
1275	0	GC_MARK_ATOM(cx, acx->lastAtom, NULL);
1276		#if JS_HAS_EXCEPTIONS
1277	0	if (acx->throwing && JSVAL_IS_GCTHING(acx->exception))
1278	0	GC_MARK(cx, JSVAL_TO_GCTHING(acx->exception), "exception", NULL);
1279		#endif
1280		#if JS_HAS_LVALUE_RETURN
1281	0	if (acx->rval2set && JSVAL_IS_GCTHING(acx->rval2))
1282	0	GC_MARK(cx, JSVAL_TO_GCTHING(acx->rval2), "rval2", NULL);
1283		#endif
1284
1285	0	for (sh = acx->stackHeaders; sh; sh = sh->down) {
1286		METER(rt->gcStats.stackseg++);
1287		METER(rt->gcStats.segslots += sh->nslots);
1288	0	GC_MARK_JSVALS(cx, sh->nslots, JS_STACK_SEGMENT(sh), "stack");
1289		}
1290		}
1291
1292	0	if (rt->gcCallback)
1293	0	(void) rt->gcCallback(cx, JSGC_MARK_END);
1294
1295		/*
1296		* Sweep phase.
1297		* Finalize as we sweep, outside of rt->gcLock, but with rt->gcRunning set
1298		* so that any attempt to allocate a GC-thing from a finalizer will fail,
1299		* rather than nest badly and leave the unmarked newborn to be swept.
1300		*/
1301	0	js_SweepAtomState(&rt->atomState);
1302	0	js_SweepScopeProperties(rt);
1303	0	js_SweepScriptFilenames(rt);
1304	0	for (a = rt->gcArenaPool.first.next; a; a = a->next) {
1305	0	flagp = (uint8 *) a->base;
1306	0	split = (uint8 *) FIRST_THING_PAGE(a);
1307	0	limit = (JSGCThing *) a->avail;
1308	0	for (thing = (JSGCThing *) split; thing < limit; thing++) {
1309	0	if (((jsuword)thing & GC_PAGE_MASK) == 0) {
1310	0	flagp++;
1311	0	thing++;
1312		}
1313	0	flags = *flagp;
1314	0	if (flags & GCF_MARK) {
1315	0	*flagp &= ~GCF_MARK;
1316	0	} else if (!(flags & (GCF_LOCKMASK | GCF_FINAL))) {
1317		/* Call the finalizer with GCF_FINAL ORed into flags. */
1318	0	type = flags & GCF_TYPEMASK;
1319	0	finalizer = gc_finalizers[type];
1320	0	if (finalizer) {
1321	0	*flagp = (uint8)(flags | GCF_FINAL);
1322	0	if (type >= GCX_EXTERNAL_STRING)
1323	0	js_PurgeDeflatedStringCache((JSString *)thing);
1324	0	finalizer(cx, thing);
1325		}
1326
1327		/* Set flags to GCF_FINAL, signifying that thing is free. */
1328	0	*flagp = GCF_FINAL;
1329
1330	0	JS_ASSERT(rt->gcBytes >= sizeof(JSGCThing) + sizeof(uint8));
1331	0	rt->gcBytes -= sizeof(JSGCThing) + sizeof(uint8);
1332		}
1333	0	if (++flagp == split)
1334	0	flagp += GC_THINGS_SIZE;
1335		}
1336		}
1337
1338		/*
1339		* Free phase.
1340		* Free any unused arenas and rebuild the JSGCThing freelist.
1341		*/
1342	0	ap = &rt->gcArenaPool.first.next;
1343	0	a = *ap;
1344	0	if (!a)
1345	0	goto out;
1346	0	all_clear = JS_TRUE;
1347	0	flp = oflp = &rt->gcFreeList;
1348	0	*flp = NULL;
1349		METER(rt->gcStats.freelen = 0);
1350
1351	0	do {
1352	0	flagp = (uint8 *) a->base;
1353	0	split = (uint8 *) FIRST_THING_PAGE(a);
1354	0	limit = (JSGCThing *) a->avail;
1355	0	for (thing = (JSGCThing *) split; thing < limit; thing++) {
1356	0	if (((jsuword)thing & GC_PAGE_MASK) == 0) {
1357	0	flagp++;
1358	0	thing++;
1359		}
1360	0	if (*flagp != GCF_FINAL) {
1361	0	all_clear = JS_FALSE;
1362		} else {
1363	0	thing->flagp = flagp;
1364	0	*flp = thing;
1365	0	flp = &thing->next;
1366		METER(rt->gcStats.freelen++);
1367		}
1368	0	if (++flagp == split)
1369	0	flagp += GC_THINGS_SIZE;
1370		}
1371
1372	0	if (all_clear) {
1373	0	JS_ARENA_DESTROY(&rt->gcArenaPool, a, ap);
1374	0	flp = oflp;
1375		METER(rt->gcStats.afree++);
1376		} else {
1377	0	ap = &a->next;
1378	0	all_clear = JS_TRUE;
1379	0	oflp = flp;
1380		}
1381	0	} while ((a = *ap) != NULL);
1382
1383		/* Terminate the new freelist. */
1384	0	*flp = NULL;
1385
1386	0	if (rt->gcCallback)
1387	0	(void) rt->gcCallback(cx, JSGC_FINALIZE_END);
1388		#ifdef DEBUG_brendan
1389		{ extern void DumpSrcNoteSizeHist();
1390		DumpSrcNoteSizeHist();
1391		}
1392		#endif
1393
1394		out:
1395	0	JS_LOCK_GC(rt);
1396	0	if (rt->gcLevel > 1) {
1397	0	rt->gcLevel = 1;
1398	0	JS_UNLOCK_GC(rt);
1399	0	goto restart;
1400		}
1401	0	js_EnablePropertyCache(cx);
1402	0	rt->gcLevel = 0;
1403	0	rt->gcLastBytes = rt->gcBytes;
1404	0	rt->gcPoke = rt->gcRunning = JS_FALSE;
1405
1406		#ifdef JS_THREADSAFE
1407		/* If we were invoked during a request, pay back the temporary debit. */
1408		if (requestDebit)
1409		rt->requestCount += requestDebit;
1410		rt->gcThread = 0;
1411		JS_NOTIFY_GC_DONE(rt);
1412		if (!(gcflags & GC_ALREADY_LOCKED))
1413		JS_UNLOCK_GC(rt);
1414		#endif
1415
1416	0	if (rt->gcCallback) {
1417	0	if (gcflags & GC_ALREADY_LOCKED)
1418	0	JS_UNLOCK_GC(rt);
1419	0	(void) rt->gcCallback(cx, JSGC_END);
1420	0	if (gcflags & GC_ALREADY_LOCKED)
1421	0	JS_LOCK_GC(rt);
1422		}