1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sw=4 et tw=78:
4 * ***** BEGIN LICENSE BLOCK *****
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
7 * The contents of this file are subject to the Mozilla Public License Version
8 * 1.1 (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 * http://www.mozilla.org/MPL/
12 * Software distributed under the License is distributed on an "AS IS" basis,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14 * for the specific language governing rights and limitations under the
17 * The Original Code is Mozilla Communicator client code, released
20 * The Initial Developer of the Original Code is
21 * Netscape Communications Corporation.
22 * Portions created by the Initial Developer are Copyright (C) 1998
23 * the Initial Developer. All Rights Reserved.
27 * Alternatively, the contents of this file may be used under the terms of
28 * either of the GNU General Public License Version 2 or later (the "GPL"),
29 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30 * in which case the provisions of the GPL or the LGPL are applicable instead
31 * of those above. If you wish to allow use of your version of this file only
32 * under the terms of either the GPL or the LGPL, and not to allow others to
33 * use your version of this file under the terms of the MPL, indicate your
34 * decision by deleting the provisions above and replace them with the notice
35 * and other provisions required by the GPL or the LGPL. If you do not delete
36 * the provisions above, a recipient may use your version of this file under
37 * the terms of any one of the MPL, the GPL or the LGPL.
39 * ***** END LICENSE BLOCK ***** */
52 #include "jsutil.h" /* Added by JSIFY */
64 js_GenerateShape(JSContext
*cx
, bool gcLocked
)
70 shape
= JS_ATOMIC_INCREMENT(&rt
->shapeGen
);
71 JS_ASSERT(shape
!= 0);
72 if (shape
>= SHAPE_OVERFLOW_BIT
) {
74 * FIXME bug 440834: The shape id space has overflowed. Currently we
75 * cope badly with this and schedule the GC on the every call. But
76 * first we make sure that increments from other threads would not
77 * have a chance to wrap around shapeGen to zero.
79 rt
->shapeGen
= SHAPE_OVERFLOW_BIT
;
80 js_TriggerGC(cx
, gcLocked
);
86 js_GetMutableScope(JSContext
*cx
, JSObject
*obj
)
88 JSScope
*scope
, *newscope
;
92 scope
= OBJ_SCOPE(obj
);
93 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx
, scope
));
94 if (scope
->object
== obj
)
98 * Compile-time block objects each have their own scope, created at
99 * birth, and runtime clone of a block objects are never mutated.
101 JS_ASSERT(STOBJ_GET_CLASS(obj
) != &js_BlockClass
);
102 newscope
= JSScope::create(cx
, scope
->map
.ops
, LOCKED_OBJ_GET_CLASS(obj
), obj
);
105 JS_LOCK_SCOPE(cx
, newscope
);
106 obj
->map
= &newscope
->map
;
108 JS_ASSERT(newscope
->freeslot
== JSSLOT_FREE(STOBJ_GET_CLASS(obj
)));
109 clasp
= STOBJ_GET_CLASS(obj
);
110 if (clasp
->reserveSlots
) {
111 freeslot
= JSSLOT_FREE(clasp
) + clasp
->reserveSlots(cx
, obj
);
112 if (freeslot
> STOBJ_NSLOTS(obj
))
113 freeslot
= STOBJ_NSLOTS(obj
);
114 if (newscope
->freeslot
< freeslot
)
115 newscope
->freeslot
= freeslot
;
117 JS_TRANSFER_SCOPE_LOCK(cx
, scope
, newscope
);
118 JS_ATOMIC_DECREMENT(&scope
->nrefs
);
119 if (scope
->nrefs
== 0)
120 JSScope::destroy(cx
, scope
);
125 * JSScope uses multiplicative hashing, _a la_ jsdhash.[ch], but specialized
126 * to minimize footprint. But if a scope has fewer than SCOPE_HASH_THRESHOLD
127 * entries, we use linear search and avoid allocating scope->table.
129 #define SCOPE_HASH_THRESHOLD 6
130 #define MIN_SCOPE_SIZE_LOG2 4
131 #define MIN_SCOPE_SIZE JS_BIT(MIN_SCOPE_SIZE_LOG2)
132 #define SCOPE_TABLE_NBYTES(n) ((n) * sizeof(JSScopeProperty *))
135 JSScope::initMinimal(JSContext
*cx
)
137 js_LeaveTraceIfGlobalObject(cx
, object
);
139 hashShift
= JS_DHASH_BITS
- MIN_SCOPE_SIZE_LOG2
;
140 entryCount
= removedCount
= 0;
146 JSScope::createTable(JSContext
*cx
, bool report
)
149 JSScopeProperty
*sprop
, **spp
;
154 if (entryCount
> SCOPE_HASH_THRESHOLD
) {
156 * Either we're creating a table for a large scope that was populated
157 * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or
158 * JSOP_SETPROP; or else calloc failed at least once already. In any
159 * event, let's try to grow, overallocating to hold at least twice the
160 * current population.
162 sizeLog2
= JS_CeilingLog2(2 * entryCount
);
163 hashShift
= JS_DHASH_BITS
- sizeLog2
;
165 JS_ASSERT(hashShift
== JS_DHASH_BITS
- MIN_SCOPE_SIZE_LOG2
);
166 sizeLog2
= MIN_SCOPE_SIZE_LOG2
;
169 table
= (JSScopeProperty
**) calloc(JS_BIT(sizeLog2
), sizeof(JSScopeProperty
*));
172 JS_ReportOutOfMemory(cx
);
175 js_UpdateMallocCounter(cx
, JS_BIT(sizeLog2
) * sizeof(JSScopeProperty
*));
177 hashShift
= JS_DHASH_BITS
- sizeLog2
;
178 for (sprop
= lastProp
; sprop
; sprop
= sprop
->parent
) {
179 spp
= search(sprop
->id
, true);
180 SPROP_STORE_PRESERVING_COLLISION(spp
, sprop
);
186 JSScope::create(JSContext
*cx
, JSObjectOps
*ops
, JSClass
*clasp
, JSObject
*obj
)
188 JS_ASSERT(OPS_IS_NATIVE(ops
));
191 JSScope
*scope
= (JSScope
*) JS_malloc(cx
, sizeof(JSScope
));
195 scope
->map
.ops
= ops
;
198 scope
->freeslot
= JSSLOT_FREE(clasp
);
200 scope
->initMinimal(cx
);
203 js_InitTitle(cx
, &scope
->title
);
205 JS_RUNTIME_METER(cx
->runtime
, liveScopes
);
206 JS_RUNTIME_METER(cx
->runtime
, totalScopes
);
210 #if defined DEBUG || defined JS_DUMP_PROPTREE_STATS
212 # define LIVE_SCOPE_METER(cx,expr) JS_LOCK_RUNTIME_VOID(cx->runtime,expr)
214 # define LIVE_SCOPE_METER(cx,expr) /* nothing */
218 JSScope::destroy(JSContext
*cx
, JSScope
*scope
)
221 js_FinishTitle(cx
, &scope
->title
);
224 JS_free(cx
, scope
->table
);
226 LIVE_SCOPE_METER(cx
, cx
->runtime
->liveScopeProps
-= scope
->entryCount
);
227 JS_RUNTIME_UNMETER(cx
->runtime
, liveScopes
);
234 JS_ASSERT(nrefs
>= 0);
235 JS_ATOMIC_INCREMENT(&nrefs
);
239 JSScope::drop(JSContext
*cx
, JSObject
*obj
)
242 /* We are called from only js_ShareWaitingTitles and js_FinalizeObject. */
243 JS_ASSERT(!obj
|| CX_THREAD_IS_RUNNING_GC(cx
));
245 JS_ASSERT(nrefs
> 0);
257 #ifdef JS_DUMP_PROPTREE_STATS
258 typedef struct JSScopeStats
{
265 jsrefcount stepMisses
;
267 jsrefcount redundantAdds
;
268 jsrefcount addFailures
;
269 jsrefcount changeFailures
;
270 jsrefcount compresses
;
273 jsrefcount removeFrees
;
274 jsrefcount uselessRemoves
;
278 JS_FRIEND_DATA(JSScopeStats
) js_scope_stats
= {0};
280 # define METER(x) JS_ATOMIC_INCREMENT(&js_scope_stats.x)
282 # define METER(x) /* nothing */
285 JS_STATIC_ASSERT(sizeof(JSHashNumber
) == 4);
286 JS_STATIC_ASSERT(sizeof(jsid
) == JS_BYTES_PER_WORD
);
288 #if JS_BYTES_PER_WORD == 4
289 # define HASH_ID(id) ((JSHashNumber)(id))
290 #elif JS_BYTES_PER_WORD == 8
291 # define HASH_ID(id) ((JSHashNumber)(id) ^ (JSHashNumber)((id) >> 32))
293 # error "Unsupported configuration"
297 * Double hashing needs the second hash code to be relatively prime to table
298 * size, so we simply make hash2 odd. The inputs to multiplicative hash are
299 * the golden ratio, expressed as a fixed-point 32 bit fraction, and the id
302 #define SCOPE_HASH0(id) (HASH_ID(id) * JS_GOLDEN_RATIO)
303 #define SCOPE_HASH1(hash0,shift) ((hash0) >> (shift))
304 #define SCOPE_HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
307 JSScope::search(jsid id
, bool adding
)
309 JSHashNumber hash0
, hash1
, hash2
;
311 JSScopeProperty
*stored
, *sprop
, **spp
, **firstRemoved
;
316 /* Not enough properties to justify hashing: search from lastProp. */
317 JS_ASSERT(!hadMiddleDelete());
318 for (spp
= &lastProp
; (sprop
= *spp
); spp
= &sprop
->parent
) {
319 if (sprop
->id
== id
) {
328 /* Compute the primary hash address. */
330 hash0
= SCOPE_HASH0(id
);
331 hash1
= SCOPE_HASH1(hash0
, hashShift
);
334 /* Miss: return space for a new entry. */
336 if (SPROP_IS_FREE(stored
)) {
341 /* Hit: return entry. */
342 sprop
= SPROP_CLEAR_COLLISION(stored
);
343 if (sprop
&& sprop
->id
== id
) {
348 /* Collision: double hash. */
349 sizeLog2
= JS_DHASH_BITS
- hashShift
;
350 hash2
= SCOPE_HASH2(hash0
, sizeLog2
, hashShift
);
351 sizeMask
= JS_BITMASK(sizeLog2
);
353 /* Save the first removed entry pointer so we can recycle it if adding. */
354 if (SPROP_IS_REMOVED(stored
)) {
358 if (adding
&& !SPROP_HAD_COLLISION(stored
))
359 SPROP_FLAG_COLLISION(spp
, sprop
);
369 if (SPROP_IS_FREE(stored
)) {
371 return (adding
&& firstRemoved
) ? firstRemoved
: spp
;
374 sprop
= SPROP_CLEAR_COLLISION(stored
);
375 if (sprop
&& sprop
->id
== id
) {
380 if (SPROP_IS_REMOVED(stored
)) {
384 if (adding
&& !SPROP_HAD_COLLISION(stored
))
385 SPROP_FLAG_COLLISION(spp
, sprop
);
394 JSScope::changeTable(JSContext
*cx
, int change
)
396 int oldlog2
, newlog2
;
397 uint32 oldsize
, newsize
, nbytes
;
398 JSScopeProperty
**newtable
, **oldtable
, **spp
, **oldspp
, *sprop
;
401 return createTable(cx
, true);
403 /* Grow, shrink, or compress by changing this->table. */
404 oldlog2
= JS_DHASH_BITS
- hashShift
;
405 newlog2
= oldlog2
+ change
;
406 oldsize
= JS_BIT(oldlog2
);
407 newsize
= JS_BIT(newlog2
);
408 nbytes
= SCOPE_TABLE_NBYTES(newsize
);
409 newtable
= (JSScopeProperty
**) calloc(nbytes
, 1);
411 JS_ReportOutOfMemory(cx
);
415 /* Now that we have newtable allocated, update members. */
416 hashShift
= JS_DHASH_BITS
- newlog2
;
421 /* Treat the above calloc as a JS_malloc, to match CreateScopeTable. */
422 cx
->runtime
->gcMallocBytes
+= nbytes
;
424 /* Copy only live entries, leaving removed and free ones behind. */
425 for (oldspp
= oldtable
; oldsize
!= 0; oldspp
++) {
426 sprop
= SPROP_FETCH(oldspp
);
428 spp
= search(sprop
->id
, true);
429 JS_ASSERT(SPROP_IS_FREE(*spp
));
435 /* Finally, free the old table storage. */
436 JS_free(cx
, oldtable
);
441 * Take care to exclude the mark bits in case we're called from the GC.
443 #define SPROP_FLAGS_NOT_MATCHED (SPROP_MARK | SPROP_FLAG_SHAPE_REGEN)
446 js_HashScopeProperty(JSDHashTable
*table
, const void *key
)
448 const JSScopeProperty
*sprop
= (const JSScopeProperty
*)key
;
452 /* Accumulate from least to most random so the low bits are most random. */
454 gsop
= sprop
->getter
;
456 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ (jsword
)gsop
;
457 gsop
= sprop
->setter
;
459 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ (jsword
)gsop
;
461 hash
= JS_ROTATE_LEFT32(hash
, 4)
462 ^ (sprop
->flags
& ~SPROP_FLAGS_NOT_MATCHED
);
464 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ sprop
->attrs
;
465 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ sprop
->shortid
;
466 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ sprop
->slot
;
467 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ sprop
->id
;
471 #define SPROP_MATCH(sprop, child) \
472 SPROP_MATCH_PARAMS(sprop, (child)->id, (child)->getter, (child)->setter, \
473 (child)->slot, (child)->attrs, (child)->flags, \
476 #define SPROP_MATCH_PARAMS(sprop, aid, agetter, asetter, aslot, aattrs, \
478 ((sprop)->id == (aid) && \
479 SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
482 #define SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
484 ((sprop)->getter == (agetter) && \
485 (sprop)->setter == (asetter) && \
486 (sprop)->slot == (aslot) && \
487 (sprop)->attrs == (aattrs) && \
488 (((sprop)->flags ^ (aflags)) & ~SPROP_FLAGS_NOT_MATCHED) == 0 && \
489 (sprop)->shortid == (ashortid))
492 js_MatchScopeProperty(JSDHashTable
*table
,
493 const JSDHashEntryHdr
*hdr
,
496 const JSPropertyTreeEntry
*entry
= (const JSPropertyTreeEntry
*)hdr
;
497 const JSScopeProperty
*sprop
= entry
->child
;
498 const JSScopeProperty
*kprop
= (const JSScopeProperty
*)key
;
500 return SPROP_MATCH(sprop
, kprop
);
503 static const JSDHashTableOps PropertyTreeHashOps
= {
506 js_HashScopeProperty
,
507 js_MatchScopeProperty
,
508 JS_DHashMoveEntryStub
,
509 JS_DHashClearEntryStub
,
510 JS_DHashFinalizeStub
,
515 * A property tree node on rt->propertyFreeList overlays the following prefix
516 * struct on JSScopeProperty.
518 typedef struct FreeNode
{
520 JSScopeProperty
*next
;
521 JSScopeProperty
**prevp
;
524 #define FREENODE(sprop) ((FreeNode *) (sprop))
526 #define FREENODE_INSERT(list, sprop) \
528 FREENODE(sprop)->next = (list); \
529 FREENODE(sprop)->prevp = &(list); \
531 FREENODE(list)->prevp = &FREENODE(sprop)->next; \
535 #define FREENODE_REMOVE(sprop) \
537 *FREENODE(sprop)->prevp = FREENODE(sprop)->next; \
538 if (FREENODE(sprop)->next) \
539 FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp; \
542 /* NB: Called with rt->gcLock held. */
543 static JSScopeProperty
*
544 NewScopeProperty(JSRuntime
*rt
)
546 JSScopeProperty
*sprop
;
548 sprop
= rt
->propertyFreeList
;
550 FREENODE_REMOVE(sprop
);
552 JS_ARENA_ALLOCATE_CAST(sprop
, JSScopeProperty
*,
553 &rt
->propertyArenaPool
,
554 sizeof(JSScopeProperty
));
559 JS_RUNTIME_METER(rt
, livePropTreeNodes
);
560 JS_RUNTIME_METER(rt
, totalPropTreeNodes
);
564 #define CHUNKY_KIDS_TAG ((jsuword)1)
565 #define KIDS_IS_CHUNKY(kids) ((jsuword)(kids) & CHUNKY_KIDS_TAG)
566 #define KIDS_TO_CHUNK(kids) ((PropTreeKidsChunk *) \
567 ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
568 #define CHUNK_TO_KIDS(chunk) ((JSScopeProperty *) \
569 ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
570 #define MAX_KIDS_PER_CHUNK 10
571 #define CHUNK_HASH_THRESHOLD 30
573 typedef struct PropTreeKidsChunk PropTreeKidsChunk
;
575 struct PropTreeKidsChunk
{
576 JSScopeProperty
*kids
[MAX_KIDS_PER_CHUNK
];
578 PropTreeKidsChunk
*next
;
581 static PropTreeKidsChunk
*
582 NewPropTreeKidsChunk(JSRuntime
*rt
)
584 PropTreeKidsChunk
*chunk
;
586 chunk
= (PropTreeKidsChunk
*) calloc(1, sizeof *chunk
);
589 JS_ASSERT(((jsuword
)chunk
& CHUNKY_KIDS_TAG
) == 0);
590 JS_RUNTIME_METER(rt
, propTreeKidsChunks
);
595 DestroyPropTreeKidsChunk(JSRuntime
*rt
, PropTreeKidsChunk
*chunk
)
597 JS_RUNTIME_UNMETER(rt
, propTreeKidsChunks
);
599 JS_DHashTableDestroy(chunk
->table
);
603 /* NB: Called with rt->gcLock held. */
605 InsertPropertyTreeChild(JSRuntime
*rt
, JSScopeProperty
*parent
,
606 JSScopeProperty
*child
, PropTreeKidsChunk
*sweptChunk
)
609 JSPropertyTreeEntry
*entry
;
610 JSScopeProperty
**childp
, *kids
, *sprop
;
611 PropTreeKidsChunk
*chunk
, **chunkp
;
614 JS_ASSERT(!parent
|| child
->parent
!= parent
);
617 table
= &rt
->propertyTreeHash
;
618 entry
= (JSPropertyTreeEntry
*)
619 JS_DHashTableOperate(table
, child
, JS_DHASH_ADD
);
622 childp
= &entry
->child
;
628 * A "Duplicate child" case.
630 * We can't do away with child, as at least one live scope entry
631 * still points at it. What's more, that scope's lastProp chains
632 * through an ancestor line to reach child, and js_Enumerate and
633 * others count on this linkage. We must leave child out of the
634 * hash table, and not require it to be there when we eventually
635 * GC it (see RemovePropertyTreeChild, below).
637 * It is necessary to leave the duplicate child out of the hash
638 * table to preserve entry uniqueness. It is safe to leave the
639 * child out of the hash table (unlike the duplicate child cases
640 * below), because the child's parent link will be null, which
643 JS_ASSERT(sprop
!= child
&& SPROP_MATCH(sprop
, child
));
644 JS_RUNTIME_METER(rt
, duplicatePropTreeNodes
);
647 childp
= &parent
->kids
;
650 if (KIDS_IS_CHUNKY(kids
)) {
651 chunk
= KIDS_TO_CHUNK(kids
);
653 table
= chunk
->table
;
655 entry
= (JSPropertyTreeEntry
*)
656 JS_DHashTableOperate(table
, child
, JS_DHASH_ADD
);
660 entry
->child
= child
;
663 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
664 childp
= &chunk
->kids
[i
];
669 chunkp
= &chunk
->next
;
675 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
676 childp
= &chunk
->kids
[i
];
681 JS_ASSERT(sprop
!= child
);
682 if (SPROP_MATCH(sprop
, child
)) {
684 * Duplicate child, see comment above. In this
685 * case, we must let the duplicate be inserted at
686 * this level in the tree, so we keep iterating,
687 * looking for an empty slot in which to insert.
689 JS_ASSERT(sprop
!= child
);
690 JS_RUNTIME_METER(rt
, duplicatePropTreeNodes
);
693 chunkp
= &chunk
->next
;
694 } while ((chunk
= *chunkp
) != NULL
);
700 chunk
= NewPropTreeKidsChunk(rt
);
705 childp
= &chunk
->kids
[0];
708 JS_ASSERT(sprop
!= child
);
709 if (SPROP_MATCH(sprop
, child
)) {
711 * Duplicate child, see comment above. Once again, we
712 * must let duplicates created by deletion pile up in a
713 * kids-chunk-list, in order to find them when sweeping
714 * and thereby avoid dangling parent pointers.
716 JS_RUNTIME_METER(rt
, duplicatePropTreeNodes
);
721 chunk
= NewPropTreeKidsChunk(rt
);
725 parent
->kids
= CHUNK_TO_KIDS(chunk
);
726 chunk
->kids
[0] = sprop
;
727 childp
= &chunk
->kids
[1];
734 child
->parent
= parent
;
738 /* NB: Called with rt->gcLock held. */
739 static PropTreeKidsChunk
*
740 RemovePropertyTreeChild(JSRuntime
*rt
, JSScopeProperty
*child
)
742 PropTreeKidsChunk
*freeChunk
;
743 JSScopeProperty
*parent
, *kids
, *kid
;
745 PropTreeKidsChunk
*list
, *chunk
, **chunkp
, *lastChunk
;
747 JSPropertyTreeEntry
*entry
;
750 parent
= child
->parent
;
753 * Don't remove child if it is not in rt->propertyTreeHash, but only
754 * matches a root child in the table that has compatible members. See
755 * the "Duplicate child" comments in InsertPropertyTreeChild, above.
757 table
= &rt
->propertyTreeHash
;
760 if (KIDS_IS_CHUNKY(kids
)) {
761 list
= chunk
= KIDS_TO_CHUNK(kids
);
763 table
= chunk
->table
;
766 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
767 if (chunk
->kids
[i
] == child
) {
769 if (!lastChunk
->next
) {
774 chunkp
= &lastChunk
->next
;
776 } while (lastChunk
->next
);
778 for (; j
< MAX_KIDS_PER_CHUNK
; j
++) {
779 if (!lastChunk
->kids
[j
])
783 if (chunk
!= lastChunk
|| j
> i
)
784 chunk
->kids
[i
] = lastChunk
->kids
[j
];
785 lastChunk
->kids
[j
] = NULL
;
790 freeChunk
= lastChunk
;
796 chunkp
= &chunk
->next
;
797 } while ((chunk
= *chunkp
) != NULL
);
808 entry
= (JSPropertyTreeEntry
*)
809 JS_DHashTableOperate(table
, child
, JS_DHASH_LOOKUP
);
811 if (entry
->child
== child
)
812 JS_DHashTableRawRemove(table
, &entry
->hdr
);
817 static JSDHashTable
*
818 HashChunks(PropTreeKidsChunk
*chunk
, uintN n
)
822 JSScopeProperty
*sprop
;
823 JSPropertyTreeEntry
*entry
;
825 table
= JS_NewDHashTable(&PropertyTreeHashOps
, NULL
,
826 sizeof(JSPropertyTreeEntry
),
827 JS_DHASH_DEFAULT_CAPACITY(n
+ 1));
831 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
832 sprop
= chunk
->kids
[i
];
835 entry
= (JSPropertyTreeEntry
*)
836 JS_DHashTableOperate(table
, sprop
, JS_DHASH_ADD
);
837 entry
->child
= sprop
;
839 } while ((chunk
= chunk
->next
) != NULL
);
844 * Called without cx->runtime->gcLock held. This function acquires that lock
845 * only when inserting a new child. Thus there may be races to find or add a
846 * node that result in duplicates. We expect such races to be rare!
848 * We use rt->gcLock, not rt->rtLock, to avoid nesting the former inside the
849 * latter in js_GenerateShape below.
851 static JSScopeProperty
*
852 GetPropertyTreeChild(JSContext
*cx
, JSScopeProperty
*parent
,
853 JSScopeProperty
*child
)
857 JSPropertyTreeEntry
*entry
;
858 JSScopeProperty
*sprop
;
859 PropTreeKidsChunk
*chunk
;
866 table
= &rt
->propertyTreeHash
;
867 entry
= (JSPropertyTreeEntry
*)
868 JS_DHashTableOperate(table
, child
, JS_DHASH_ADD
);
872 sprop
= entry
->child
;
877 * Because chunks are appended at the end and never deleted except by
878 * the GC, we can search without taking the runtime's GC lock. We may
879 * miss a matching sprop added by another thread, and make a duplicate
880 * one, but that is an unlikely, therefore small, cost. The property
881 * tree has extremely low fan-out below its root in popular embeddings
882 * with real-world workloads.
884 * Patterns such as defining closures that capture a constructor's
885 * environment as getters or setters on the new object that is passed
886 * in as |this| can significantly increase fan-out below the property
887 * tree root -- see bug 335700 for details.
890 sprop
= parent
->kids
;
892 if (KIDS_IS_CHUNKY(sprop
)) {
893 chunk
= KIDS_TO_CHUNK(sprop
);
895 table
= chunk
->table
;
898 entry
= (JSPropertyTreeEntry
*)
899 JS_DHashTableOperate(table
, child
, JS_DHASH_LOOKUP
);
900 sprop
= entry
->child
;
905 goto locked_not_found
;
910 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
911 sprop
= chunk
->kids
[i
];
914 if (n
>= CHUNK_HASH_THRESHOLD
) {
915 chunk
= KIDS_TO_CHUNK(parent
->kids
);
917 table
= HashChunks(chunk
, n
);
922 JS_DHashTableDestroy(table
);
924 chunk
->table
= table
;
925 goto locked_not_found
;
931 if (SPROP_MATCH(sprop
, child
))
934 n
+= MAX_KIDS_PER_CHUNK
;
935 } while ((chunk
= chunk
->next
) != NULL
);
937 if (SPROP_MATCH(sprop
, child
))
947 sprop
= NewScopeProperty(rt
);
951 sprop
->id
= child
->id
;
952 sprop
->getter
= child
->getter
;
953 sprop
->setter
= child
->setter
;
954 sprop
->slot
= child
->slot
;
955 sprop
->attrs
= child
->attrs
;
956 sprop
->flags
= child
->flags
;
957 sprop
->shortid
= child
->shortid
;
958 sprop
->parent
= sprop
->kids
= NULL
;
959 sprop
->shape
= js_GenerateShape(cx
, true);
962 entry
->child
= sprop
;
964 if (!InsertPropertyTreeChild(rt
, parent
, sprop
, NULL
))
974 JS_ReportOutOfMemory(cx
);
978 #ifdef DEBUG_notbrendan
979 #define CHECK_ANCESTOR_LINE(scope, sparse) \
981 if ((scope)->table) CheckAncestorLine(scope, sparse); \
985 CheckAncestorLine(JSScope
*scope
, bool sparse
)
988 JSScopeProperty
**spp
, **start
, **end
, *ancestorLine
, *sprop
, *aprop
;
989 uint32 entryCount
, ancestorCount
;
991 ancestorLine
= SCOPE_LAST_PROP(scope
);
993 JS_ASSERT(scope
->has(ancestorLine
));
996 size
= SCOPE_CAPACITY(scope
);
997 start
= scope
->table
;
998 for (spp
= start
, end
= start
+ size
; spp
< end
; spp
++) {
999 sprop
= SPROP_FETCH(spp
);
1002 for (aprop
= ancestorLine
; aprop
; aprop
= aprop
->parent
) {
1009 JS_ASSERT(entryCount
== scope
->entryCount
);
1012 for (sprop
= ancestorLine
; sprop
; sprop
= sprop
->parent
) {
1013 if (scope
->hadMiddleDelete() && !scope
->has(sprop
)) {
1019 JS_ASSERT(ancestorCount
== scope
->entryCount
);
1022 #define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
1026 JSScope::reportReadOnlyScope(JSContext
*cx
)
1031 str
= js_ValueToString(cx
, OBJECT_TO_JSVAL(object
));
1034 bytes
= js_GetStringBytes(cx
, str
);
1037 JS_ReportErrorNumber(cx
, js_GetErrorMessage
, NULL
, JSMSG_READ_ONLY
, bytes
);
1041 js_MakeScopeShapeUnique(JSContext
*cx
, JSScope
*scope
)
1043 js_LeaveTraceIfGlobalObject(cx
, scope
->object
);
1044 scope
->shape
= js_GenerateShape(cx
, JS_FALSE
);
1048 JSScope::add(JSContext
*cx
, jsid id
,
1049 JSPropertyOp getter
, JSPropertyOp setter
,
1050 uint32 slot
, uintN attrs
,
1051 uintN flags
, intN shortid
)
1053 JSScopeProperty
**spp
, *sprop
, *overwriting
, **spvec
, **spp2
, child
;
1054 uint32 size
, splen
, i
;
1056 JSTempValueRooter tvr
;
1058 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx
, this));
1059 CHECK_ANCESTOR_LINE(this, true);
1062 * You can't add properties to a sealed scope. But note well that you can
1063 * change property attributes in a sealed scope, even though that replaces
1064 * a JSScopeProperty * in the scope's hash table -- but no id is added, so
1065 * the scope remains sealed.
1068 reportReadOnlyScope(cx
);
1073 * Normalize stub getter and setter values for faster is-stub testing in
1074 * the SPROP_CALL_[GS]ETTER macros.
1076 if (getter
== JS_PropertyStub
)
1078 if (setter
== JS_PropertyStub
)
1082 * Search for id in order to claim its entry, allocating a property tree
1083 * node if one doesn't already exist for our parameters.
1085 spp
= search(id
, true);
1086 sprop
= overwriting
= SPROP_FETCH(spp
);
1088 /* Check whether we need to grow, if the load factor is >= .75. */
1089 size
= SCOPE_CAPACITY(this);
1090 if (entryCount
+ removedCount
>= size
- (size
>> 2)) {
1091 if (removedCount
>= size
>> 2) {
1098 if (!changeTable(cx
, change
) &&
1099 entryCount
+ removedCount
== size
- 1) {
1103 spp
= search(id
, true);
1104 JS_ASSERT(!SPROP_FETCH(spp
));
1107 /* Property exists: JSScope::search must have returned a valid *spp. */
1108 JS_ASSERT(!SPROP_IS_REMOVED(*spp
));
1111 * If all property members match, this is a redundant add and we can
1112 * return early. If the caller wants to allocate a slot, but doesn't
1113 * care which slot, copy sprop->slot into slot so we can match sprop,
1114 * if all other members match.
1116 if (!(attrs
& JSPROP_SHARED
) &&
1117 slot
== SPROP_INVALID_SLOT
&&
1118 SPROP_HAS_VALID_SLOT(sprop
, this)) {
1121 if (SPROP_MATCH_PARAMS_AFTER_ID(sprop
, getter
, setter
, slot
, attrs
,
1123 METER(redundantAdds
);
1128 * If we are clearing sprop to force the existing property that it
1129 * describes to be overwritten, then we have to unlink sprop from the
1130 * ancestor line at this->lastProp, lazily if sprop is not lastProp.
1131 * And we must remove the entry at *spp, precisely so the lazy "middle
1132 * delete" fixup code further below won't find sprop in this->table,
1133 * in spite of sprop being on the ancestor line.
1135 * When we finally succeed in finding or creating a new sprop
1136 * and storing its pointer at *spp, we'll use the |overwriting|
1137 * local saved when we first looked up id to decide whether we're
1138 * indeed creating a new entry, or merely overwriting an existing
1141 if (sprop
== SCOPE_LAST_PROP(this)) {
1143 SCOPE_REMOVE_LAST_PROP(this);
1144 if (!hadMiddleDelete())
1146 sprop
= SCOPE_LAST_PROP(this);
1147 } while (sprop
&& !has(sprop
));
1148 } else if (!hadMiddleDelete()) {
1150 * If we have no hash table yet, we need one now. The middle
1151 * delete code is simple-minded that way!
1154 if (!createTable(cx
, true))
1156 spp
= search(id
, true);
1157 sprop
= overwriting
= SPROP_FETCH(spp
);
1161 js_MakeScopeShapeUnique(cx
, this);
1164 * If we fail later on trying to find or create a new sprop, we will
1165 * goto fail_overwrite and restore *spp from |overwriting|. Note that
1166 * we don't bother to keep this->removedCount in sync, because we'll
1167 * fix up *spp and this->entryCount shortly, no matter how control
1168 * flow returns from this function.
1171 SPROP_STORE_PRESERVING_COLLISION(spp
, NULL
);
1173 CHECK_ANCESTOR_LINE(this, true);
1179 * If properties were deleted from the middle of the list starting at
1180 * this->lastProp, we may need to fork the property tree and squeeze
1181 * all deleted properties out of this scope's ancestor line. Otherwise
1182 * we risk adding a node with the same id as a "middle" node, violating
1183 * the rule that properties along an ancestor line have distinct ids.
1185 if (hadMiddleDelete()) {
1187 CHECK_ANCESTOR_LINE(this, true);
1190 * Our forking heuristic tries to balance the desire to avoid
1191 * over-compacting (over-forking) against the desire to
1192 * *periodically* fork anyways, in order to prevent paying scan
1193 * penalties on each insert indefinitely, on a lineage with only
1194 * a few old middle-deletions. So we fork if either:
1196 * - A quick scan finds a true conflict.
1197 * - We are passing through a doubling-threshold in size and
1198 * have accumulated a nonzero count of uncompacted deletions.
1201 bool conflicts
= false;
1203 uint32 threshold
= JS_BIT(JS_CeilingLog2(entryCount
));
1204 for (sprop
= SCOPE_LAST_PROP(this); sprop
; sprop
= sprop
->parent
) {
1206 if (sprop
->id
== id
) {
1212 if (conflicts
|| count
> threshold
) {
1214 * Enumerate live entries in this->table using a temporary
1215 * vector, by walking the (possibly sparse, due to deletions)
1216 * ancestor line from this->lastProp.
1219 JS_ASSERT(splen
!= 0);
1220 spvec
= (JSScopeProperty
**)
1221 JS_malloc(cx
, SCOPE_TABLE_NBYTES(splen
));
1223 goto fail_overwrite
;
1225 sprop
= SCOPE_LAST_PROP(this);
1229 * NB: use JSScope::lookup, not JSScope::has, as the latter
1230 * macro insists that sprop->id maps to sprop, while the
1231 * former simply tests whether sprop->id is bound in this
1234 if (!lookup(sprop
->id
))
1237 JS_ASSERT(sprop
!= overwriting
);
1240 } while ((sprop
= sprop
->parent
) != NULL
);
1244 * Now loop forward through spvec, forking the property tree
1245 * whenever we see a "parent gap" due to deletions from this
1246 * scope. NB: sprop is null on first entry to the loop body.
1249 if (spvec
[i
]->parent
== sprop
) {
1252 sprop
= GetPropertyTreeChild(cx
, sprop
, spvec
[i
]);
1255 goto fail_overwrite
;
1258 spp2
= search(sprop
->id
, false);
1259 JS_ASSERT(SPROP_FETCH(spp2
) == spvec
[i
]);
1260 SPROP_STORE_PRESERVING_COLLISION(spp2
, sprop
);
1262 } while (++i
< splen
);
1266 * Now sprop points to the last property in this scope, where
1267 * the ancestor line from sprop to the root is dense w.r.t.
1268 * this scope: it contains no nodes not mapped by this->table.
1271 CHECK_ANCESTOR_LINE(this, false);
1272 JS_RUNTIME_METER(cx
->runtime
, middleDeleteFixups
);
1273 clearMiddleDelete();
1278 * Aliases share another property's slot, passed in the |slot| param.
1279 * Shared properties have no slot. Unshared properties that do not
1280 * alias another property's slot get one here, but may lose it due to
1281 * a JS_ClearScope call.
1283 if (!(flags
& SPROP_IS_ALIAS
)) {
1284 if (attrs
& JSPROP_SHARED
) {
1285 slot
= SPROP_INVALID_SLOT
;
1288 * We may have set slot from a nearly-matching sprop, above.
1289 * If so, we're overwriting that nearly-matching sprop, so we
1290 * can reuse its slot -- we don't need to allocate a new one.
1291 * Similarly, we use a specific slot if provided by the caller.
1293 if (slot
== SPROP_INVALID_SLOT
&&
1294 !js_AllocSlot(cx
, object
, &slot
)) {
1295 goto fail_overwrite
;
1301 * Check for a watchpoint on a deleted property; if one exists, change
1302 * setter to js_watch_set.
1303 * XXXbe this could get expensive with lots of watchpoints...
1305 if (!JS_CLIST_IS_EMPTY(&cx
->runtime
->watchPointList
) &&
1306 js_FindWatchPoint(cx
->runtime
, this, id
)) {
1308 JS_PUSH_TEMP_ROOT_SPROP(cx
, overwriting
, &tvr
);
1309 setter
= js_WrapWatchedSetter(cx
, id
, attrs
, setter
);
1311 JS_POP_TEMP_ROOT(cx
, &tvr
);
1313 goto fail_overwrite
;
1316 /* Find or create a property tree node labeled by our arguments. */
1318 child
.getter
= getter
;
1319 child
.setter
= setter
;
1321 child
.attrs
= attrs
;
1322 child
.flags
= flags
;
1323 child
.shortid
= shortid
;
1324 sprop
= GetPropertyTreeChild(cx
, lastProp
, &child
);
1326 goto fail_overwrite
;
1329 * This scope's shape defaults to its last property's shape, but may be
1330 * regenerated later as this scope diverges (from the property cache
1331 * point of view) from the structural type associated with sprop.
1335 /* Store the tree node pointer in the table entry for id. */
1337 SPROP_STORE_PRESERVING_COLLISION(spp
, sprop
);
1338 CHECK_ANCESTOR_LINE(this, false);
1341 LIVE_SCOPE_METER(cx
, ++cx
->runtime
->liveScopeProps
);
1342 JS_RUNTIME_METER(cx
->runtime
, totalScopeProps
);
1347 * If we reach the hashing threshold, try to allocate this->table.
1348 * If we can't (a rare event, preceded by swapping to death on most
1349 * modern OSes), stick with linear search rather than whining about
1350 * this little set-back. Therefore we must test !this->table and
1351 * this->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
1352 * entry count just reached the threshold.
1354 if (!table
&& entryCount
>= SCOPE_HASH_THRESHOLD
)
1355 (void) createTable(cx
, false);
1359 if (js_IdIsIndex(sprop
->id
, &index
))
1360 setIndexedProperties();
1368 * We may or may not have forked overwriting out of this scope's
1369 * ancestor line, so we must check (the alternative is to set a flag
1370 * above, but that hurts the common, non-error case). If we did fork
1371 * overwriting out, we'll add it back at scope->lastProp. This means
1372 * enumeration order can change due to a failure to overwrite an id.
1373 * XXXbe minor(?) incompatibility
1375 for (sprop
= SCOPE_LAST_PROP(this); ; sprop
= sprop
->parent
) {
1377 sprop
= SCOPE_LAST_PROP(this);
1378 if (overwriting
->parent
== sprop
) {
1379 lastProp
= overwriting
;
1381 sprop
= GetPropertyTreeChild(cx
, sprop
, overwriting
);
1383 JS_ASSERT(sprop
!= overwriting
);
1386 overwriting
= sprop
;
1390 if (sprop
== overwriting
)
1395 SPROP_STORE_PRESERVING_COLLISION(spp
, overwriting
);
1398 CHECK_ANCESTOR_LINE(this, true);
1405 JSScope::change(JSContext
*cx
, JSScopeProperty
*sprop
,
1406 uintN attrs
, uintN mask
,
1407 JSPropertyOp getter
, JSPropertyOp setter
)
1409 JSScopeProperty child
, *newsprop
, **spp
;
1411 CHECK_ANCESTOR_LINE(this, true);
1413 /* Allow only shared (slot-less) => unshared (slot-full) transition. */
1414 attrs
|= sprop
->attrs
& mask
;
1415 JS_ASSERT(!((attrs
^ sprop
->attrs
) & JSPROP_SHARED
) ||
1416 !(attrs
& JSPROP_SHARED
));
1417 if (getter
== JS_PropertyStub
)
1419 if (setter
== JS_PropertyStub
)
1421 if (sprop
->attrs
== attrs
&&
1422 sprop
->getter
== getter
&&
1423 sprop
->setter
== setter
) {
1427 child
.id
= sprop
->id
;
1428 child
.getter
= getter
;
1429 child
.setter
= setter
;
1430 child
.slot
= sprop
->slot
;
1431 child
.attrs
= attrs
;
1432 child
.flags
= sprop
->flags
;
1433 child
.shortid
= sprop
->shortid
;
1435 if (SCOPE_LAST_PROP(this) == sprop
) {
1437 * Optimize the case where the last property added to this scope is
1438 * changed to have a different attrs, getter, or setter. In the last
1439 * property case, we need not fork the property tree. But since we do
1440 * not call JSScope::addProperty, we may need to allocate a new slot
1443 if ((sprop
->attrs
& JSPROP_SHARED
) && !(attrs
& JSPROP_SHARED
)) {
1444 JS_ASSERT(child
.slot
== SPROP_INVALID_SLOT
);
1445 if (!js_AllocSlot(cx
, object
, &child
.slot
))
1449 newsprop
= GetPropertyTreeChild(cx
, sprop
->parent
, &child
);
1451 spp
= search(sprop
->id
, false);
1452 JS_ASSERT(SPROP_FETCH(spp
) == sprop
);
1455 SPROP_STORE_PRESERVING_COLLISION(spp
, newsprop
);
1456 lastProp
= newsprop
;
1457 CHECK_ANCESTOR_LINE(this, true);
1461 * Let JSScope::addProperty handle this |overwriting| case, including
1462 * the conservation of sprop->slot (if it's valid). We must not call
1463 * JSScope::remove here, because it will free a valid sprop->slot and
1464 * JSScope::add won't re-allocate it.
1466 newsprop
= add(cx
, child
.id
, child
.getter
, child
.setter
, child
.slot
,
1467 child
.attrs
, child
.flags
, child
.shortid
);
1471 js_LeaveTraceIfGlobalObject(cx
, object
);
1472 replacingShapeChange(cx
, sprop
, newsprop
);
1474 #ifdef JS_DUMP_PROPTREE_STATS
1476 METER(changeFailures
);
1482 JSScope::remove(JSContext
*cx
, jsid id
)
1484 JSScopeProperty
**spp
, *stored
, *sprop
;
1487 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx
, this));
1488 CHECK_ANCESTOR_LINE(this, true);
1490 reportReadOnlyScope(cx
);
1495 spp
= search(id
, false);
1497 sprop
= SPROP_CLEAR_COLLISION(stored
);
1499 METER(uselessRemoves
);
1503 /* Convert from a list to a hash so we can handle "middle deletes". */
1504 if (!table
&& sprop
!= lastProp
) {
1505 if (!createTable(cx
, true))
1507 spp
= search(id
, false);
1509 sprop
= SPROP_CLEAR_COLLISION(stored
);
1512 /* First, if sprop is unshared and not cleared, free its slot number. */
1513 if (SPROP_HAS_VALID_SLOT(sprop
, this)) {
1514 js_FreeSlot(cx
, object
, sprop
->slot
);
1515 JS_ATOMIC_INCREMENT(&cx
->runtime
->propertyRemovals
);
1518 /* Next, remove id by setting its entry to a removed or free sentinel. */
1519 if (SPROP_HAD_COLLISION(stored
)) {
1521 *spp
= SPROP_REMOVED
;
1529 LIVE_SCOPE_METER(cx
, --cx
->runtime
->liveScopeProps
);
1531 /* Update this->lastProp directly, or set its deferred update flag. */
1532 if (sprop
== SCOPE_LAST_PROP(this)) {
1534 SCOPE_REMOVE_LAST_PROP(this);
1535 if (!hadMiddleDelete())
1537 sprop
= SCOPE_LAST_PROP(this);
1538 } while (sprop
&& !has(sprop
));
1539 if (!SCOPE_LAST_PROP(this))
1540 clearMiddleDelete();
1541 } else if (!hadMiddleDelete()) {
1544 js_MakeScopeShapeUnique(cx
, this);
1545 CHECK_ANCESTOR_LINE(this, true);
1547 /* Last, consider shrinking this->table if its load factor is <= .25. */
1548 size
= SCOPE_CAPACITY(this);
1549 if (size
> MIN_SCOPE_SIZE
&& entryCount
<= size
>> 2) {
1551 (void) changeTable(cx
, -1);
1558 JSScope::clear(JSContext
*cx
)
1560 CHECK_ANCESTOR_LINE(this, true);
1561 LIVE_SCOPE_METER(cx
, cx
->runtime
->liveScopeProps
-= entryCount
);
1565 clearMiddleDelete();
1567 JS_ATOMIC_INCREMENT(&cx
->runtime
->propertyRemovals
);
1571 JSScope::brandingShapeChange(JSContext
*cx
, uint32 slot
, jsval v
)
1573 js_MakeScopeShapeUnique(cx
, this);
1577 JSScope::deletingShapeChange(JSContext
*cx
, JSScopeProperty
*sprop
)
1579 js_MakeScopeShapeUnique(cx
, this);
1583 JSScope::methodShapeChange(JSContext
*cx
, uint32 slot
, jsval toval
)
1585 js_MakeScopeShapeUnique(cx
, this);
1589 JSScope::protoShapeChange(JSContext
*cx
)
1591 js_MakeScopeShapeUnique(cx
, this);
1595 JSScope::replacingShapeChange(JSContext
*cx
, JSScopeProperty
*sprop
, JSScopeProperty
*newsprop
)
1597 if (shape
== sprop
->shape
)
1598 shape
= newsprop
->shape
;
1600 js_MakeScopeShapeUnique(cx
, this);
1604 JSScope::sealingShapeChange(JSContext
*cx
)
1606 js_MakeScopeShapeUnique(cx
, this);
1610 JSScope::shadowingShapeChange(JSContext
*cx
, JSScopeProperty
*sprop
)
1612 js_MakeScopeShapeUnique(cx
, this);
1616 js_TraceId(JSTracer
*trc
, jsid id
)
1620 v
= ID_TO_VALUE(id
);
1621 JS_CALL_VALUE_TRACER(trc
, v
, "id");
1626 PrintPropertyGetterOrSetter(JSTracer
*trc
, char *buf
, size_t bufsize
)
1628 JSScopeProperty
*sprop
;
1633 JS_ASSERT(trc
->debugPrinter
== PrintPropertyGetterOrSetter
);
1634 sprop
= (JSScopeProperty
*)trc
->debugPrintArg
;
1636 name
= trc
->debugPrintIndex
? js_setter_str
: js_getter_str
;
1638 if (JSID_IS_ATOM(id
)) {
1639 n
= js_PutEscapedString(buf
, bufsize
- 1,
1640 ATOM_TO_STRING(JSID_TO_ATOM(id
)), 0);
1641 if (n
< bufsize
- 1)
1642 JS_snprintf(buf
+ n
, bufsize
- n
, " %s", name
);
1643 } else if (JSID_IS_INT(sprop
->id
)) {
1644 JS_snprintf(buf
, bufsize
, "%d %s", JSID_TO_INT(id
), name
);
1646 JS_snprintf(buf
, bufsize
, "<object> %s", name
);
1652 JSScopeProperty::trace(JSTracer
*trc
)
1654 if (IS_GC_MARKING_TRACER(trc
))
1655 flags
|= SPROP_MARK
;
1658 #if JS_HAS_GETTER_SETTER
1659 if (attrs
& (JSPROP_GETTER
| JSPROP_SETTER
)) {
1660 if (attrs
& JSPROP_GETTER
) {
1661 JS_SET_TRACING_DETAILS(trc
, PrintPropertyGetterOrSetter
, this, 0);
1662 JS_CallTracer(trc
, js_CastAsObject(getter
), JSTRACE_OBJECT
);
1664 if (attrs
& JSPROP_SETTER
) {
1665 JS_SET_TRACING_DETAILS(trc
, PrintPropertyGetterOrSetter
, this, 1);
1666 JS_CallTracer(trc
, js_CastAsObject(setter
), JSTRACE_OBJECT
);
1669 #endif /* JS_HAS_GETTER_SETTER */
1672 #ifdef JS_DUMP_PROPTREE_STATS
1677 MeterKidCount(JSBasicStats
*bs
, uintN nkids
)
1679 JS_BASIC_STATS_ACCUM(bs
, nkids
);
1680 bs
->hist
[JS_MIN(nkids
, 10)]++;
1684 MeterPropertyTree(JSBasicStats
*bs
, JSScopeProperty
*node
)
1687 JSScopeProperty
*kids
, *kid
;
1688 PropTreeKidsChunk
*chunk
;
1693 if (KIDS_IS_CHUNKY(kids
)) {
1694 for (chunk
= KIDS_TO_CHUNK(kids
); chunk
; chunk
= chunk
->next
) {
1695 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
1696 kid
= chunk
->kids
[i
];
1699 MeterPropertyTree(bs
, kid
);
1704 MeterPropertyTree(bs
, kids
);
1709 MeterKidCount(bs
, nkids
);
1712 static JSDHashOperator
1713 js_MeterPropertyTree(JSDHashTable
*table
, JSDHashEntryHdr
*hdr
, uint32 number
,
1716 JSPropertyTreeEntry
*entry
= (JSPropertyTreeEntry
*)hdr
;
1717 JSBasicStats
*bs
= (JSBasicStats
*)arg
;
1719 MeterPropertyTree(bs
, entry
->child
);
1720 return JS_DHASH_NEXT
;
1724 DumpSubtree(JSContext
*cx
, JSScopeProperty
*sprop
, int level
, FILE *fp
)
1728 JSScopeProperty
*kids
, *kid
;
1729 PropTreeKidsChunk
*chunk
;
1732 fprintf(fp
, "%*sid ", level
, "");
1733 v
= ID_TO_VALUE(sprop
->id
);
1734 if (JSID_IS_INT(sprop
->id
)) {
1735 fprintf(fp
, "%d", JSVAL_TO_INT(v
));
1737 if (JSID_IS_ATOM(sprop
->id
)) {
1738 str
= JSVAL_TO_STRING(v
);
1740 JS_ASSERT(JSID_IS_OBJECT(sprop
->id
));
1741 str
= js_ValueToString(cx
, v
);
1742 fputs("object ", fp
);
1745 fputs("<error>", fp
);
1747 js_FileEscapedString(fp
, str
, '"');
1750 fprintf(fp
, " g/s %p/%p slot %u attrs %x flags %x shortid %d\n",
1751 (void *) sprop
->getter
, (void *) sprop
->setter
, sprop
->slot
,
1752 sprop
->attrs
, sprop
->flags
, sprop
->shortid
);
1756 if (KIDS_IS_CHUNKY(kids
)) {
1757 chunk
= KIDS_TO_CHUNK(kids
);
1759 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
1760 kid
= chunk
->kids
[i
];
1763 JS_ASSERT(kid
->parent
== sprop
);
1764 DumpSubtree(cx
, kid
, level
, fp
);
1766 } while ((chunk
= chunk
->next
) != NULL
);
1769 DumpSubtree(cx
, kid
, level
, fp
);
1774 #endif /* JS_DUMP_PROPTREE_STATS */
1777 js_SweepScopeProperties(JSContext
*cx
)
1779 JSRuntime
*rt
= cx
->runtime
;
1781 JSScopeProperty
*limit
, *sprop
, *parent
, *kids
, *kid
;
1783 PropTreeKidsChunk
*chunk
, *nextChunk
, *freeChunk
;
1786 #ifdef JS_DUMP_PROPTREE_STATS
1788 uint32 livePropCapacity
= 0, totalLiveCount
= 0;
1791 logfp
= fopen("/tmp/proptree.stats", "w");
1793 JS_BASIC_STATS_INIT(&bs
);
1794 MeterKidCount(&bs
, rt
->propertyTreeHash
.entryCount
);
1795 JS_DHashTableEnumerate(&rt
->propertyTreeHash
, js_MeterPropertyTree
, &bs
);
1798 double props
, nodes
, mean
, sigma
;
1800 props
= rt
->liveScopePropsPreSweep
;
1801 nodes
= rt
->livePropTreeNodes
;
1802 JS_ASSERT(nodes
== bs
.sum
);
1803 mean
= JS_MeanAndStdDevBS(&bs
, &sigma
);
1806 "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
1807 props
, nodes
, nodes
/ props
, mean
, sigma
, bs
.max
);
1810 JS_DumpHistogram(&bs
, logfp
);
1813 ap
= &rt
->propertyArenaPool
.first
.next
;
1814 while ((a
= *ap
) != NULL
) {
1815 limit
= (JSScopeProperty
*) a
->avail
;
1817 for (sprop
= (JSScopeProperty
*) a
->base
; sprop
< limit
; sprop
++) {
1818 /* If the id is null, sprop is already on the freelist. */
1819 if (sprop
->id
== JSVAL_NULL
)
1823 * If the mark bit is set, sprop is alive, so clear the mark bit
1824 * and continue the while loop.
1826 * Regenerate sprop->shape if it hasn't already been refreshed
1827 * during the mark phase, when live scopes' lastProp members are
1828 * followed to update both scope->shape and lastProp->shape.
1830 if (sprop
->flags
& SPROP_MARK
) {
1831 sprop
->flags
&= ~SPROP_MARK
;
1832 if (sprop
->flags
& SPROP_FLAG_SHAPE_REGEN
)
1833 sprop
->flags
&= ~SPROP_FLAG_SHAPE_REGEN
;
1835 sprop
->shape
= js_RegenerateShapeForGC(cx
);
1840 /* Ok, sprop is garbage to collect: unlink it from its parent. */
1841 freeChunk
= RemovePropertyTreeChild(rt
, sprop
);
1844 * Take care to reparent all sprop's kids to their grandparent.
1845 * InsertPropertyTreeChild can potentially fail for two reasons:
1847 * 1. If parent is null, insertion into the root property hash
1848 * table may fail. We are forced to leave the kid out of the
1849 * table (as can already happen with duplicates) but ensure
1850 * that the kid's parent pointer is set to null.
1852 * 2. If parent is non-null, allocation of a new KidsChunk can
1853 * fail. To prevent this from happening, we allow sprops's own
1854 * chunks to be reused by the grandparent, which removes the
1855 * need for InsertPropertyTreeChild to malloc a new KidsChunk.
1857 * If sprop does not have chunky kids, then we rely on the
1858 * RemovePropertyTreeChild call above (which removed sprop from
1859 * its parent) either leaving one free entry, or else returning
1860 * the now-unused chunk to us so we can reuse it.
1862 * We also require the grandparent to have either no kids or else
1863 * chunky kids. A single non-chunky kid would force a new chunk to
1864 * be malloced in some cases (if sprop had a single non-chunky
1865 * kid, or a multiple of MAX_KIDS_PER_CHUNK kids). Note that
1866 * RemovePropertyTreeChild never converts a single-entry chunky
1867 * kid back to a non-chunky kid, so we are assured of correct
1873 parent
= sprop
->parent
;
1875 /* Assert that grandparent has no kids or chunky kids. */
1876 JS_ASSERT(!parent
|| !parent
->kids
||
1877 KIDS_IS_CHUNKY(parent
->kids
));
1878 if (KIDS_IS_CHUNKY(kids
)) {
1879 chunk
= KIDS_TO_CHUNK(kids
);
1881 nextChunk
= chunk
->next
;
1883 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
1884 kid
= chunk
->kids
[i
];
1887 JS_ASSERT(kid
->parent
== sprop
);
1890 * Clear a space in the kids array for possible
1891 * re-use by InsertPropertyTreeChild.
1893 chunk
->kids
[i
] = NULL
;
1894 if (!InsertPropertyTreeChild(rt
, parent
, kid
,
1897 * This can happen only if we failed to add an
1898 * entry to the root property hash table.
1904 if (!chunk
->kids
[0]) {
1905 /* The chunk wasn't reused, so we must free it. */
1906 DestroyPropTreeKidsChunk(rt
, chunk
);
1908 } while ((chunk
= nextChunk
) != NULL
);
1911 if (!InsertPropertyTreeChild(rt
, parent
, kid
, freeChunk
)) {
1913 * This can happen only if we failed to add an entry
1914 * to the root property hash table.
1922 if (freeChunk
&& !freeChunk
->kids
[0]) {
1923 /* The chunk wasn't reused, so we must free it. */
1924 DestroyPropTreeKidsChunk(rt
, freeChunk
);
1927 /* Clear id so we know (above) that sprop is on the freelist. */
1928 sprop
->id
= JSVAL_NULL
;
1929 FREENODE_INSERT(rt
->propertyFreeList
, sprop
);
1930 JS_RUNTIME_UNMETER(rt
, livePropTreeNodes
);
1933 /* If a contains no live properties, return it to the malloc heap. */
1934 if (liveCount
== 0) {
1935 for (sprop
= (JSScopeProperty
*) a
->base
; sprop
< limit
; sprop
++)
1936 FREENODE_REMOVE(sprop
);
1937 JS_ARENA_DESTROY(&rt
->propertyArenaPool
, a
, ap
);
1939 #ifdef JS_DUMP_PROPTREE_STATS
1940 livePropCapacity
+= limit
- (JSScopeProperty
*) a
->base
;
1941 totalLiveCount
+= liveCount
;
1947 #ifdef JS_DUMP_PROPTREE_STATS
1948 fprintf(logfp
, "arenautil %g%%\n",
1949 (totalLiveCount
&& livePropCapacity
)
1950 ? (totalLiveCount
* 100.0) / livePropCapacity
1953 #define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
1955 fprintf(logfp
, "Scope search stats:\n"
1957 " hits: %6u %5.2f%% of searches\n"
1958 " misses: %6u %5.2f%%\n"
1959 " hashes: %6u %5.2f%%\n"
1960 " steps: %6u %5.2f%% %5.2f%% of hashes\n"
1961 " stepHits: %6u %5.2f%% %5.2f%%\n"
1962 " stepMisses: %6u %5.2f%% %5.2f%%\n"
1964 " redundantAdds: %6u\n"
1965 " addFailures: %6u\n"
1966 " changeFailures: %6u\n"
1967 " compresses: %6u\n"
1970 " removeFrees: %6u\n"
1971 " uselessRemoves: %6u\n"
1973 js_scope_stats
.searches
,
1974 js_scope_stats
.hits
, RATE(hits
, searches
),
1975 js_scope_stats
.misses
, RATE(misses
, searches
),
1976 js_scope_stats
.hashes
, RATE(hashes
, searches
),
1977 js_scope_stats
.steps
, RATE(steps
, searches
), RATE(steps
, hashes
),
1978 js_scope_stats
.stepHits
,
1979 RATE(stepHits
, searches
), RATE(stepHits
, hashes
),
1980 js_scope_stats
.stepMisses
,
1981 RATE(stepMisses
, searches
), RATE(stepMisses
, hashes
),
1982 js_scope_stats
.adds
,
1983 js_scope_stats
.redundantAdds
,
1984 js_scope_stats
.addFailures
,
1985 js_scope_stats
.changeFailures
,
1986 js_scope_stats
.compresses
,
1987 js_scope_stats
.grows
,
1988 js_scope_stats
.removes
,
1989 js_scope_stats
.removeFrees
,
1990 js_scope_stats
.uselessRemoves
,
1991 js_scope_stats
.shrinks
);
1998 #ifdef DUMP_PROPERTY_TREE
2000 FILE *dumpfp
= fopen("/tmp/proptree.dump", "w");
2002 JSPropertyTreeEntry
*pte
, *end
;
2004 pte
= (JSPropertyTreeEntry
*) rt
->propertyTreeHash
.entryStore
;
2005 end
= pte
+ JS_DHASH_TABLE_SIZE(&rt
->propertyTreeHash
);
2008 DumpSubtree(cx
, pte
->child
, 0, dumpfp
);
2018 js_InitPropertyTree(JSRuntime
*rt
)
2020 if (!JS_DHashTableInit(&rt
->propertyTreeHash
, &PropertyTreeHashOps
, NULL
,
2021 sizeof(JSPropertyTreeEntry
), JS_DHASH_MIN_SIZE
)) {
2022 rt
->propertyTreeHash
.ops
= NULL
;
2025 JS_INIT_ARENA_POOL(&rt
->propertyArenaPool
, "properties",
2026 256 * sizeof(JSScopeProperty
), sizeof(void *), NULL
);
2031 js_FinishPropertyTree(JSRuntime
*rt
)
2033 if (rt
->propertyTreeHash
.ops
) {
2034 JS_DHashTableFinish(&rt
->propertyTreeHash
);
2035 rt
->propertyTreeHash
.ops
= NULL
;
2037 JS_FinishArenaPool(&rt
->propertyArenaPool
);