1 /* -*- Mode: c++; c-basic-offset: 4; tab-width: 40; indent-tabs-mode: nil -*- */
2 /* vim: set ts=40 sw=4 et tw=99: */
3 /* ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
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/
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
16 * The Original Code is the Mozilla SpiderMonkey property tree implementation
18 * The Initial Developer of the Original Code is
20 * Portions created by the Initial Developer are Copyright (C) 2002-2010
21 * the Initial Developer. All Rights Reserved.
24 * Brendan Eich <brendan@mozilla.org>
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.
38 * ***** END LICENSE BLOCK ***** */
47 #include "jspropertytree.h"
50 #include "jsscopeinlines.h"
54 struct PropertyRootKey
56 const JSScopeProperty
*firstProp
;
59 PropertyRootKey(const JSScopeProperty
*child
, uint32 shape
)
60 : firstProp(child
), emptyShape(shape
) {}
62 static JSDHashNumber
hash(JSDHashTable
*table
, const void *key
) {
63 const PropertyRootKey
*rkey
= (const PropertyRootKey
*)key
;
65 return rkey
->firstProp
->hash() ^ rkey
->emptyShape
;
69 struct PropertyRootEntry
: public JSDHashEntryHdr
71 JSScopeProperty
*firstProp
;
75 static JSBool
match(JSDHashTable
*table
, const JSDHashEntryHdr
*hdr
, const void *key
) {
76 const PropertyRootEntry
*rent
= (const PropertyRootEntry
*)hdr
;
77 const PropertyRootKey
*rkey
= (const PropertyRootKey
*)key
;
79 return rent
->firstProp
->matches(rkey
->firstProp
) &&
80 rent
->emptyShape
== rkey
->emptyShape
;
84 static const JSDHashTableOps PropertyRootHashOps
= {
87 PropertyRootKey::hash
,
88 PropertyRootEntry::match
,
89 JS_DHashMoveEntryStub
,
90 JS_DHashClearEntryStub
,
96 HashScopeProperty(JSDHashTable
*table
, const void *key
)
98 const JSScopeProperty
*sprop
= (const JSScopeProperty
*)key
;
103 MatchScopeProperty(JSDHashTable
*table
,
104 const JSDHashEntryHdr
*hdr
,
107 const JSPropertyTreeEntry
*entry
= (const JSPropertyTreeEntry
*)hdr
;
108 const JSScopeProperty
*sprop
= entry
->child
;
109 const JSScopeProperty
*kprop
= (const JSScopeProperty
*)key
;
111 return sprop
->matches(kprop
);
114 static const JSDHashTableOps PropertyTreeHashOps
= {
119 JS_DHashMoveEntryStub
,
120 JS_DHashClearEntryStub
,
121 JS_DHashFinalizeStub
,
128 if (!JS_DHashTableInit(&hash
, &PropertyRootHashOps
, NULL
,
129 sizeof(PropertyRootEntry
), JS_DHASH_MIN_SIZE
)) {
133 JS_InitArenaPool(&arenaPool
, "properties",
134 256 * sizeof(JSScopeProperty
), sizeof(void *), NULL
);
135 emptyShapeChanges
= 0;
140 PropertyTree::finish()
143 JS_DHashTableFinish(&hash
);
146 JS_FinishArenaPool(&arenaPool
);
150 * NB: Called with cx->runtime->gcLock held if gcLocked is true.
151 * On failure, return null after unlocking the GC and reporting out of memory.
154 PropertyTree::newScopeProperty(JSContext
*cx
, bool gcLocked
)
156 JSScopeProperty
*sprop
;
159 JS_LOCK_GC(cx
->runtime
);
164 JS_ARENA_ALLOCATE_CAST(sprop
, JSScopeProperty
*, &arenaPool
,
165 sizeof(JSScopeProperty
));
167 JS_UNLOCK_GC(cx
->runtime
);
168 JS_ReportOutOfMemory(cx
);
173 JS_UNLOCK_GC(cx
->runtime
);
175 JS_RUNTIME_METER(cx
->runtime
, livePropTreeNodes
);
176 JS_RUNTIME_METER(cx
->runtime
, totalPropTreeNodes
);
180 #define CHUNKY_KIDS_TAG ((jsuword)1)
181 #define KIDS_IS_CHUNKY(kids) ((jsuword)(kids) & CHUNKY_KIDS_TAG)
182 #define KIDS_TO_CHUNK(kids) ((PropTreeKidsChunk *) \
183 ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
184 #define CHUNK_TO_KIDS(chunk) ((JSScopeProperty *) \
185 ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
186 #define MAX_KIDS_PER_CHUNK 10
187 #define CHUNK_HASH_THRESHOLD 30
189 struct PropTreeKidsChunk
{
190 JSScopeProperty
*kids
[MAX_KIDS_PER_CHUNK
];
192 PropTreeKidsChunk
*next
;
196 * NB: Called with cx->runtime->gcLock held, always.
197 * On failure, return null after unlocking the GC and reporting out of memory.
199 static PropTreeKidsChunk
*
200 NewPropTreeKidsChunk(JSContext
*cx
)
202 PropTreeKidsChunk
*chunk
;
204 chunk
= (PropTreeKidsChunk
*) js_calloc(sizeof *chunk
);
206 JS_UNLOCK_GC(cx
->runtime
);
207 JS_ReportOutOfMemory(cx
);
210 JS_ASSERT(((jsuword
)chunk
& CHUNKY_KIDS_TAG
) == 0);
211 JS_RUNTIME_METER(cx
->runtime
, propTreeKidsChunks
);
215 static PropTreeKidsChunk
*
216 DestroyPropTreeKidsChunk(JSContext
*cx
, PropTreeKidsChunk
*chunk
)
218 JS_RUNTIME_UNMETER(cx
->runtime
, propTreeKidsChunks
);
220 JS_DHashTableDestroy(chunk
->table
);
222 PropTreeKidsChunk
*nextChunk
= chunk
->next
;
228 * NB: Called with cx->runtime->gcLock held, always.
229 * On failure, return null after unlocking the GC and reporting out of memory.
232 PropertyTree::insertChild(JSContext
*cx
, JSScopeProperty
*parent
,
233 JSScopeProperty
*child
)
236 JS_ASSERT(!child
->parent
);
237 JS_ASSERT(!JSVAL_IS_NULL(parent
->id
));
238 JS_ASSERT(!JSVAL_IS_NULL(child
->id
));
240 JSScopeProperty
**childp
= &parent
->kids
;
241 if (JSScopeProperty
*kids
= *childp
) {
242 JSScopeProperty
*sprop
;
243 PropTreeKidsChunk
*chunk
;
245 if (!KIDS_IS_CHUNKY(kids
)) {
247 JS_ASSERT(sprop
!= child
);
248 if (sprop
->matches(child
)) {
250 * Duplicate child created while racing to getChild on the same
251 * node label. See PropertyTree::getChild, further below.
253 JS_RUNTIME_METER(cx
->runtime
, duplicatePropTreeNodes
);
255 chunk
= NewPropTreeKidsChunk(cx
);
258 parent
->kids
= CHUNK_TO_KIDS(chunk
);
259 chunk
->kids
[0] = sprop
;
260 childp
= &chunk
->kids
[1];
262 PropTreeKidsChunk
**chunkp
;
264 chunk
= KIDS_TO_CHUNK(kids
);
265 if (JSDHashTable
*table
= chunk
->table
) {
266 JSPropertyTreeEntry
*entry
= (JSPropertyTreeEntry
*)
267 JS_DHashTableOperate(table
, child
, JS_DHASH_ADD
);
269 JS_UNLOCK_GC(cx
->runtime
);
270 JS_ReportOutOfMemory(cx
);
274 entry
->child
= child
;
277 for (uintN i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
278 childp
= &chunk
->kids
[i
];
283 chunkp
= &chunk
->next
;
289 for (uintN i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
290 childp
= &chunk
->kids
[i
];
295 JS_ASSERT(sprop
!= child
);
296 if (sprop
->matches(child
)) {
298 * Duplicate child, see comment above. In this
299 * case, we must let the duplicate be inserted at
300 * this level in the tree, so we keep iterating,
301 * looking for an empty slot in which to insert.
303 JS_ASSERT(sprop
!= child
);
304 JS_RUNTIME_METER(cx
->runtime
, duplicatePropTreeNodes
);
307 chunkp
= &chunk
->next
;
308 } while ((chunk
= *chunkp
) != NULL
);
311 chunk
= NewPropTreeKidsChunk(cx
);
315 childp
= &chunk
->kids
[0];
321 child
->parent
= parent
;
325 /* NB: Called with cx->runtime->gcLock held. */
327 PropertyTree::removeChild(JSContext
*cx
, JSScopeProperty
*child
)
330 JSPropertyTreeEntry
*entry
;
332 JSScopeProperty
*parent
= child
->parent
;
334 JS_ASSERT(!JSVAL_IS_NULL(parent
->id
));
336 JSScopeProperty
*kids
= parent
->kids
;
337 if (!KIDS_IS_CHUNKY(kids
)) {
338 JSScopeProperty
*kid
= kids
;
344 PropTreeKidsChunk
*list
= KIDS_TO_CHUNK(kids
);
345 PropTreeKidsChunk
*chunk
= list
;
346 PropTreeKidsChunk
**chunkp
= &list
;
348 JSDHashTable
*table
= chunk
->table
;
349 PropTreeKidsChunk
*freeChunk
= NULL
;
352 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
353 if (chunk
->kids
[i
] == child
) {
354 PropTreeKidsChunk
*lastChunk
= chunk
;
355 if (!lastChunk
->next
) {
360 chunkp
= &lastChunk
->next
;
362 } while (lastChunk
->next
);
364 for (; j
< MAX_KIDS_PER_CHUNK
; j
++) {
365 if (!lastChunk
->kids
[j
])
369 if (chunk
!= lastChunk
|| j
> i
)
370 chunk
->kids
[i
] = lastChunk
->kids
[j
];
371 lastChunk
->kids
[j
] = NULL
;
376 freeChunk
= lastChunk
;
382 chunkp
= &chunk
->next
;
383 } while ((chunk
= *chunkp
) != NULL
);
387 entry
= (JSPropertyTreeEntry
*)
388 JS_DHashTableOperate(table
, child
, JS_DHASH_LOOKUP
);
390 if (entry
->child
== child
)
391 JS_DHashTableRawRemove(table
, &entry
->hdr
);
394 DestroyPropTreeKidsChunk(cx
, freeChunk
);
398 PropertyTree::emptyShapeChange(uint32 oldEmptyShape
, uint32 newEmptyShape
)
400 if (oldEmptyShape
== newEmptyShape
)
403 PropertyRootEntry
*rent
= (PropertyRootEntry
*) hash
.entryStore
;
404 PropertyRootEntry
*rend
= rent
+ JS_DHASH_TABLE_SIZE(&hash
);
406 while (rent
< rend
) {
407 if (rent
->emptyShape
== oldEmptyShape
)
408 rent
->newEmptyShape
= newEmptyShape
;
415 static JSDHashTable
*
416 HashChunks(PropTreeKidsChunk
*chunk
, uintN n
)
420 JSScopeProperty
*sprop
;
421 JSPropertyTreeEntry
*entry
;
423 table
= JS_NewDHashTable(&PropertyTreeHashOps
, NULL
,
424 sizeof(JSPropertyTreeEntry
),
425 JS_DHASH_DEFAULT_CAPACITY(n
+ 1));
429 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
430 sprop
= chunk
->kids
[i
];
433 entry
= (JSPropertyTreeEntry
*)
434 JS_DHashTableOperate(table
, sprop
, JS_DHASH_ADD
);
435 entry
->child
= sprop
;
437 } while ((chunk
= chunk
->next
) != NULL
);
442 * Called without cx->runtime->gcLock held. This function acquires that lock
443 * only when inserting a new child. Thus there may be races to find or add a
444 * node that result in duplicates. We expect such races to be rare!
446 * We use cx->runtime->gcLock, not ...->rtLock, to avoid nesting the former
447 * inside the latter in js_GenerateShape below.
450 PropertyTree::getChild(JSContext
*cx
, JSScopeProperty
*parent
, uint32 shape
,
451 const JSScopeProperty
&child
)
453 PropertyRootEntry
*rent
;
454 JSScopeProperty
*sprop
;
457 PropertyRootKey
rkey(&child
, shape
);
459 JS_LOCK_GC(cx
->runtime
);
460 rent
= (PropertyRootEntry
*) JS_DHashTableOperate(&hash
, &rkey
, JS_DHASH_ADD
);
462 JS_UNLOCK_GC(cx
->runtime
);
463 JS_ReportOutOfMemory(cx
);
467 sprop
= rent
->firstProp
;
471 JS_ASSERT(!JSVAL_IS_NULL(parent
->id
));
474 * Because chunks are appended at the end and never deleted except by
475 * the GC, we can search without taking the runtime's GC lock. We may
476 * miss a matching sprop added by another thread, and make a duplicate
477 * one, but that is an unlikely, therefore small, cost. The property
478 * tree has extremely low fan-out below its root in popular embeddings
479 * with real-world workloads.
481 * Patterns such as defining closures that capture a constructor's
482 * environment as getters or setters on the new object that is passed
483 * in as |this| can significantly increase fan-out below the property
484 * tree root -- see bug 335700 for details.
487 sprop
= parent
->kids
;
489 if (!KIDS_IS_CHUNKY(sprop
)) {
490 if (sprop
->matches(&child
))
493 PropTreeKidsChunk
*chunk
= KIDS_TO_CHUNK(sprop
);
495 if (JSDHashTable
*table
= chunk
->table
) {
496 JS_LOCK_GC(cx
->runtime
);
497 JSPropertyTreeEntry
*entry
= (JSPropertyTreeEntry
*)
498 JS_DHashTableOperate(table
, &child
, JS_DHASH_LOOKUP
);
499 sprop
= entry
->child
;
502 goto locked_not_found
;
507 for (uintN i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
508 sprop
= chunk
->kids
[i
];
511 if (n
>= CHUNK_HASH_THRESHOLD
) {
512 chunk
= KIDS_TO_CHUNK(parent
->kids
);
514 JSDHashTable
*table
= HashChunks(chunk
, n
);
516 JS_ReportOutOfMemory(cx
);
520 JS_LOCK_GC(cx
->runtime
);
522 JS_DHashTableDestroy(table
);
524 chunk
->table
= table
;
525 goto locked_not_found
;
531 if (sprop
->matches(&child
))
534 n
+= MAX_KIDS_PER_CHUNK
;
535 } while ((chunk
= chunk
->next
) != NULL
);
540 JS_LOCK_GC(cx
->runtime
);
544 sprop
= newScopeProperty(cx
, true);
548 new (sprop
) JSScopeProperty(child
.id
, child
.rawGetter
, child
.rawSetter
, child
.slot
,
549 child
.attrs
, child
.flags
, child
.shortid
);
550 sprop
->parent
= sprop
->kids
= NULL
;
551 sprop
->shape
= js_GenerateShape(cx
, true);
554 rent
->firstProp
= sprop
;
555 rent
->emptyShape
= shape
;
556 rent
->newEmptyShape
= 0;
558 if (!PropertyTree::insertChild(cx
, parent
, sprop
))
563 JS_UNLOCK_GC(cx
->runtime
);
570 MeterKidCount(JSBasicStats
*bs
, uintN nkids
)
572 JS_BASIC_STATS_ACCUM(bs
, nkids
);
573 bs
->hist
[JS_MIN(nkids
, 10)]++;
577 MeterPropertyTree(JSBasicStats
*bs
, JSScopeProperty
*node
)
580 JSScopeProperty
*kids
, *kid
;
581 PropTreeKidsChunk
*chunk
;
586 if (KIDS_IS_CHUNKY(kids
)) {
587 for (chunk
= KIDS_TO_CHUNK(kids
); chunk
; chunk
= chunk
->next
) {
588 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
589 kid
= chunk
->kids
[i
];
592 MeterPropertyTree(bs
, kid
);
597 MeterPropertyTree(bs
, kids
);
602 MeterKidCount(bs
, nkids
);
605 static JSDHashOperator
606 js_MeterPropertyTree(JSDHashTable
*table
, JSDHashEntryHdr
*hdr
, uint32 number
,
609 PropertyRootEntry
*rent
= (PropertyRootEntry
*)hdr
;
610 JSBasicStats
*bs
= (JSBasicStats
*)arg
;
612 MeterPropertyTree(bs
, rent
->firstProp
);
613 return JS_DHASH_NEXT
;
617 JSScopeProperty::dump(JSContext
*cx
, FILE *fp
)
619 JS_ASSERT(!JSVAL_IS_NULL(id
));
621 jsval idval
= ID_TO_VALUE(id
);
622 if (JSVAL_IS_INT(idval
)) {
623 fprintf(fp
, "[%ld]", (long) JSVAL_TO_INT(idval
));
626 if (JSVAL_IS_STRING(idval
)) {
627 str
= JSVAL_TO_STRING(idval
);
629 JS_ASSERT(JSVAL_IS_OBJECT(idval
));
630 str
= js_ValueToString(cx
, idval
);
631 fputs("object ", fp
);
634 fputs("<error>", fp
);
636 js_FileEscapedString(fp
, str
, '"');
639 fprintf(fp
, " g/s %p/%p slot %u attrs %x ",
640 JS_FUNC_TO_DATA_PTR(void *, rawGetter
),
641 JS_FUNC_TO_DATA_PTR(void *, rawSetter
),
646 #define DUMP_ATTR(name, display) if (attrs & JSPROP_##name) fputs(" " #display + first, fp), first = 0
647 DUMP_ATTR(ENUMERATE
, enumerate
);
648 DUMP_ATTR(READONLY
, readonly
);
649 DUMP_ATTR(PERMANENT
, permanent
);
650 DUMP_ATTR(GETTER
, getter
);
651 DUMP_ATTR(SETTER
, setter
);
652 DUMP_ATTR(SHARED
, shared
);
657 fprintf(fp
, "flags %x ", flags
);
661 #define DUMP_FLAG(name, display) if (flags & name) fputs(" " #display + first, fp), first = 0
662 DUMP_FLAG(ALIAS
, alias
);
663 DUMP_FLAG(HAS_SHORTID
, has_shortid
);
664 DUMP_FLAG(METHOD
, method
);
665 DUMP_FLAG(MARK
, mark
);
666 DUMP_FLAG(SHAPE_REGEN
, shape_regen
);
667 DUMP_FLAG(IN_DICTIONARY
, in_dictionary
);
672 fprintf(fp
, "shortid %d\n", shortid
);
676 JSScopeProperty::dumpSubtree(JSContext
*cx
, int level
, FILE *fp
)
678 fprintf(fp
, "%*sid ", level
, "");
683 if (KIDS_IS_CHUNKY(kids
)) {
684 PropTreeKidsChunk
*chunk
= KIDS_TO_CHUNK(kids
);
686 for (uintN i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
687 JSScopeProperty
*kid
= chunk
->kids
[i
];
690 JS_ASSERT(kid
->parent
== this);
691 kid
->dumpSubtree(cx
, level
, fp
);
693 } while ((chunk
= chunk
->next
) != NULL
);
695 JSScopeProperty
*kid
= kids
;
696 JS_ASSERT(kid
->parent
== this);
697 kid
->dumpSubtree(cx
, level
, fp
);
705 OrphanNodeKids(JSContext
*cx
, JSScopeProperty
*sprop
)
707 JSScopeProperty
*kids
= sprop
->kids
;
713 * The grandparent must have either no kids or (still, after the
714 * removeChild call above) chunky kids.
716 JS_ASSERT(!sprop
->parent
|| !sprop
->parent
->kids
||
717 KIDS_IS_CHUNKY(sprop
->parent
->kids
));
719 if (KIDS_IS_CHUNKY(kids
)) {
720 PropTreeKidsChunk
*chunk
= KIDS_TO_CHUNK(kids
);
723 for (uintN i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
724 JSScopeProperty
*kid
= chunk
->kids
[i
];
728 if (!JSVAL_IS_NULL(kid
->id
)) {
729 JS_ASSERT(kid
->parent
== sprop
);
733 } while ((chunk
= DestroyPropTreeKidsChunk(cx
, chunk
)) != NULL
);
735 JSScopeProperty
*kid
= kids
;
737 if (!JSVAL_IS_NULL(kid
->id
)) {
738 JS_ASSERT(kid
->parent
== sprop
);
745 js::RemoveNodeIfDead(JSDHashTable
*table
, JSDHashEntryHdr
*hdr
, uint32 number
, void *arg
)
747 PropertyRootEntry
*rent
= (PropertyRootEntry
*)hdr
;
748 JSScopeProperty
*sprop
= rent
->firstProp
;
750 JS_ASSERT(!sprop
->parent
);
751 if (!sprop
->marked()) {
753 OrphanNodeKids((JSContext
*)arg
, sprop
);
754 return JS_DHASH_REMOVE
;
756 return JS_DHASH_NEXT
;
760 js::SweepScopeProperties(JSContext
*cx
)
764 uint32 livePropCapacity
= 0, totalLiveCount
= 0;
767 if (const char *filename
= getenv("JS_PROPTREE_STATFILE"))
768 logfp
= fopen(filename
, "w");
772 JS_BASIC_STATS_INIT(&bs
);
773 MeterKidCount(&bs
, JS_PROPERTY_TREE(cx
).hash
.entryCount
);
774 JS_DHashTableEnumerate(&JS_PROPERTY_TREE(cx
).hash
, js_MeterPropertyTree
, &bs
);
776 double props
, nodes
, mean
, sigma
;
778 props
= cx
->runtime
->liveScopePropsPreSweep
;
779 nodes
= cx
->runtime
->livePropTreeNodes
;
780 JS_ASSERT(nodes
== bs
.sum
);
781 mean
= JS_MeanAndStdDevBS(&bs
, &sigma
);
784 "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
785 props
, nodes
, nodes
/ props
, mean
, sigma
, bs
.max
);
787 JS_DumpHistogram(&bs
, logfp
);
792 * First, remove unmarked nodes from JS_PROPERTY_TREE(cx).hash. This table
793 * requires special handling up front, rather than removal during regular
794 * heap sweeping, because we cannot find an entry in it from the firstProp
795 * node pointer alone -- we would need the emptyShape too.
797 * Rather than encode emptyShape in firstProp somehow (a tagged overlay on
798 * parent, perhaps, but that would slow down JSScope::search and other hot
799 * paths), we simply orphan kids of garbage nodes in the property tree's
800 * root-ply before sweeping the node heap.
802 JS_DHashTableEnumerate(&JS_PROPERTY_TREE(cx
).hash
, RemoveNodeIfDead
, cx
);
805 * Second, if any empty scopes have been reshaped, rehash the root ply of
806 * this tree using the new empty shape numbers as key-halves. If we run out
807 * of memory trying to allocate the new hash, disable the property cache by
808 * setting SHAPE_OVERFLOW_BIT in rt->shapeGen. The next GC will therefore
809 * renumber shapes as well as (we hope, eventually) free sufficient memory
810 * for a successful re-run through this code.
812 if (JS_PROPERTY_TREE(cx
).emptyShapeChanges
) {
813 JSDHashTable
&oldHash
= JS_PROPERTY_TREE(cx
).hash
;
814 uint32 tableSize
= JS_DHASH_TABLE_SIZE(&oldHash
);
815 JSDHashTable newHash
;
817 if (!JS_DHashTableInit(&newHash
, &PropertyRootHashOps
, NULL
,
818 sizeof(PropertyRootEntry
), tableSize
)) {
819 cx
->runtime
->shapeGen
|= SHAPE_OVERFLOW_BIT
;
821 PropertyRootEntry
*rent
= (PropertyRootEntry
*) oldHash
.entryStore
;
822 PropertyRootEntry
*rend
= rent
+ tableSize
;
824 while (rent
< rend
) {
825 if (rent
->firstProp
) {
826 uint32 emptyShape
= rent
->newEmptyShape
;
828 emptyShape
= rent
->emptyShape
;
830 PropertyRootKey
rkey(rent
->firstProp
, emptyShape
);
831 PropertyRootEntry
*newRent
=
832 (PropertyRootEntry
*) JS_DHashTableOperate(&newHash
, &rkey
, JS_DHASH_ADD
);
834 newRent
->firstProp
= rent
->firstProp
;
835 newRent
->emptyShape
= emptyShape
;
836 newRent
->newEmptyShape
= 0;
841 JS_ASSERT(newHash
.generation
== 0);
842 JS_DHashTableFinish(&oldHash
);
843 JS_PROPERTY_TREE(cx
).hash
= newHash
;
844 JS_PROPERTY_TREE(cx
).emptyShapeChanges
= 0;
849 * Third, sweep the heap clean of all unmarked nodes. Here we will find
850 * nodes already GC'ed from the root ply, but we will avoid re-orphaning
851 * their kids, because the kids member will already be null.
853 JSArena
**ap
= &JS_PROPERTY_TREE(cx
).arenaPool
.first
.next
;
854 while (JSArena
*a
= *ap
) {
855 JSScopeProperty
*limit
= (JSScopeProperty
*) a
->avail
;
858 for (JSScopeProperty
*sprop
= (JSScopeProperty
*) a
->base
; sprop
< limit
; sprop
++) {
859 /* If the id is null, sprop is already on the freelist. */
860 if (JSVAL_IS_NULL(sprop
->id
))
864 * If the mark bit is set, sprop is alive, so clear the mark bit
865 * and continue the while loop.
867 * Regenerate sprop->shape if it hasn't already been refreshed
868 * during the mark phase, when live scopes' lastProp members are
869 * followed to update both scope->shape and lastProp->shape.
871 if (sprop
->marked()) {
873 if (cx
->runtime
->gcRegenShapes
) {
874 if (sprop
->hasRegenFlag())
875 sprop
->clearRegenFlag();
877 sprop
->shape
= js_RegenerateShapeForGC(cx
);
883 if (!sprop
->inDictionary()) {
885 * Here, sprop is garbage to collect, but its parent might not
886 * be, so we may have to remove it from its parent's kids chunk
887 * list or kid singleton pointer set.
889 * Without a separate mark-clearing pass, we can't tell whether
890 * sprop->parent is live at this point, so we must remove sprop
891 * if its parent member is non-null. A saving grace: if sprop's
892 * parent is dead and swept by this point, sprop->parent will
893 * be null -- in the next paragraph, we null all of a property
894 * tree node's kids' parent links when sweeping that node.
897 JS_PROPERTY_TREE(cx
).removeChild(cx
, sprop
);
900 OrphanNodeKids(cx
, sprop
);
904 * Note that JSScopeProperty::insertFree nulls sprop->id so we know
905 * that sprop is on the freelist.
907 sprop
->insertFree(JS_PROPERTY_TREE(cx
).freeList
);
908 JS_RUNTIME_UNMETER(cx
->runtime
, livePropTreeNodes
);
911 /* If a contains no live properties, return it to the malloc heap. */
912 if (liveCount
== 0) {
913 for (JSScopeProperty
*sprop
= (JSScopeProperty
*) a
->base
; sprop
< limit
; sprop
++)
915 JS_ARENA_DESTROY(&JS_PROPERTY_TREE(cx
).arenaPool
, a
, ap
);
918 livePropCapacity
+= limit
- (JSScopeProperty
*) a
->base
;
919 totalLiveCount
+= liveCount
;
928 "\nProperty tree stats for gcNumber %lu\n",
929 (unsigned long) cx
->runtime
->gcNumber
);
931 fprintf(logfp
, "arenautil %g%%\n",
932 (totalLiveCount
&& livePropCapacity
)
933 ? (totalLiveCount
* 100.0) / livePropCapacity
936 #define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
939 "Scope search stats:\n"
941 " hits: %6u %5.2f%% of searches\n"
942 " misses: %6u %5.2f%%\n"
943 " hashes: %6u %5.2f%%\n"
944 " steps: %6u %5.2f%% %5.2f%% of hashes\n"
945 " stepHits: %6u %5.2f%% %5.2f%%\n"
946 " stepMisses: %6u %5.2f%% %5.2f%%\n"
947 " tableAllocFails %6u\n"
949 " wrapWatchFails %6u\n"
953 " redundantPuts: %6u\n"
956 " changeFails: %6u\n"
960 " removeFrees: %6u\n"
961 " uselessRemoves: %6u\n"
963 js_scope_stats
.searches
,
964 js_scope_stats
.hits
, RATE(hits
, searches
),
965 js_scope_stats
.misses
, RATE(misses
, searches
),
966 js_scope_stats
.hashes
, RATE(hashes
, searches
),
967 js_scope_stats
.steps
, RATE(steps
, searches
), RATE(steps
, hashes
),
968 js_scope_stats
.stepHits
,
969 RATE(stepHits
, searches
), RATE(stepHits
, hashes
),
970 js_scope_stats
.stepMisses
,
971 RATE(stepMisses
, searches
), RATE(stepMisses
, hashes
),
972 js_scope_stats
.tableAllocFails
,
973 js_scope_stats
.toDictFails
,
974 js_scope_stats
.wrapWatchFails
,
976 js_scope_stats
.addFails
,
978 js_scope_stats
.redundantPuts
,
979 js_scope_stats
.putFails
,
980 js_scope_stats
.changes
,
981 js_scope_stats
.changeFails
,
982 js_scope_stats
.compresses
,
983 js_scope_stats
.grows
,
984 js_scope_stats
.removes
,
985 js_scope_stats
.removeFrees
,
986 js_scope_stats
.uselessRemoves
,
987 js_scope_stats
.shrinks
);
994 if (const char *filename
= getenv("JS_PROPTREE_DUMPFILE")) {
996 JS_snprintf(pathname
, sizeof pathname
, "%s.%lu",
997 filename
, (unsigned long)cx
->runtime
->gcNumber
);
998 FILE *dumpfp
= fopen(pathname
, "w");
1000 PropertyRootEntry
*rent
= (PropertyRootEntry
*) JS_PROPERTY_TREE(cx
).hash
.entryStore
;
1001 PropertyRootEntry
*rend
= rent
+ JS_DHASH_TABLE_SIZE(&JS_PROPERTY_TREE(cx
).hash
);
1003 while (rent
< rend
) {
1004 if (rent
->firstProp
) {
1005 fprintf(dumpfp
, "emptyShape %u ", rent
->emptyShape
);
1006 rent
->firstProp
->dumpSubtree(cx
, 0, dumpfp
);