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 */
63 js_GetMutableScope(JSContext
*cx
, JSObject
*obj
)
65 JSScope
*scope
, *newscope
;
69 scope
= OBJ_SCOPE(obj
);
70 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx
, scope
));
71 if (scope
->object
== obj
)
73 newscope
= js_NewScope(cx
, 0, scope
->map
.ops
, LOCKED_OBJ_GET_CLASS(obj
),
77 JS_LOCK_SCOPE(cx
, newscope
);
78 obj
->map
= js_HoldObjectMap(cx
, &newscope
->map
);
79 JS_ASSERT(newscope
->map
.freeslot
== JSSLOT_FREE(STOBJ_GET_CLASS(obj
)));
80 clasp
= STOBJ_GET_CLASS(obj
);
81 if (clasp
->reserveSlots
) {
82 freeslot
= JSSLOT_FREE(clasp
) + clasp
->reserveSlots(cx
, obj
);
83 if (freeslot
> STOBJ_NSLOTS(obj
))
84 freeslot
= STOBJ_NSLOTS(obj
);
85 if (newscope
->map
.freeslot
< freeslot
)
86 newscope
->map
.freeslot
= freeslot
;
88 scope
= (JSScope
*) js_DropObjectMap(cx
, &scope
->map
, obj
);
89 JS_TRANSFER_SCOPE_LOCK(cx
, scope
, newscope
);
94 * JSScope uses multiplicative hashing, _a la_ jsdhash.[ch], but specialized
95 * to minimize footprint. But if a scope has fewer than SCOPE_HASH_THRESHOLD
96 * entries, we use linear search and avoid allocating scope->table.
98 #define SCOPE_HASH_THRESHOLD 6
99 #define MIN_SCOPE_SIZE_LOG2 4
100 #define MIN_SCOPE_SIZE JS_BIT(MIN_SCOPE_SIZE_LOG2)
101 #define SCOPE_TABLE_NBYTES(n) ((n) * sizeof(JSScopeProperty *))
104 InitMinimalScope(JSScope
*scope
)
107 scope
->hashShift
= JS_DHASH_BITS
- MIN_SCOPE_SIZE_LOG2
;
108 scope
->entryCount
= scope
->removedCount
= 0;
110 scope
->lastProp
= NULL
;
114 CreateScopeTable(JSContext
*cx
, JSScope
*scope
, JSBool report
)
117 JSScopeProperty
*sprop
, **spp
;
119 JS_ASSERT(!scope
->table
);
120 JS_ASSERT(scope
->lastProp
);
122 if (scope
->entryCount
> SCOPE_HASH_THRESHOLD
) {
124 * Either we're creating a table for a large scope that was populated
125 * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or
126 * JSOP_SETPROP; or else calloc failed at least once already. In any
127 * event, let's try to grow, overallocating to hold at least twice the
128 * current population.
130 sizeLog2
= JS_CeilingLog2(2 * scope
->entryCount
);
131 scope
->hashShift
= JS_DHASH_BITS
- sizeLog2
;
133 JS_ASSERT(scope
->hashShift
== JS_DHASH_BITS
- MIN_SCOPE_SIZE_LOG2
);
134 sizeLog2
= MIN_SCOPE_SIZE_LOG2
;
137 scope
->table
= (JSScopeProperty
**)
138 calloc(JS_BIT(sizeLog2
), sizeof(JSScopeProperty
*));
141 JS_ReportOutOfMemory(cx
);
144 js_UpdateMallocCounter(cx
, JS_BIT(sizeLog2
) * sizeof(JSScopeProperty
*));
146 scope
->hashShift
= JS_DHASH_BITS
- sizeLog2
;
147 for (sprop
= scope
->lastProp
; sprop
; sprop
= sprop
->parent
) {
148 spp
= js_SearchScope(scope
, sprop
->id
, JS_TRUE
);
149 SPROP_STORE_PRESERVING_COLLISION(spp
, sprop
);
155 js_NewScope(JSContext
*cx
, jsrefcount nrefs
, JSObjectOps
*ops
, JSClass
*clasp
,
160 scope
= (JSScope
*) JS_malloc(cx
, sizeof(JSScope
));
164 js_InitObjectMap(&scope
->map
, nrefs
, ops
, clasp
);
167 InitMinimalScope(scope
);
170 js_InitTitle(cx
, &scope
->title
);
172 JS_RUNTIME_METER(cx
->runtime
, liveScopes
);
173 JS_RUNTIME_METER(cx
->runtime
, totalScopes
);
177 #ifdef DEBUG_SCOPE_COUNT
179 js_unlog_scope(JSScope
*scope
);
182 #if defined DEBUG || defined JS_DUMP_PROPTREE_STATS
184 # define LIVE_SCOPE_METER(cx,expr) JS_LOCK_RUNTIME_VOID(cx->runtime,expr)
186 # define LIVE_SCOPE_METER(cx,expr) /* nothing */
190 js_DestroyScope(JSContext
*cx
, JSScope
*scope
)
192 #ifdef DEBUG_SCOPE_COUNT
193 js_unlog_scope(scope
);
197 js_FinishTitle(cx
, &scope
->title
);
200 JS_free(cx
, scope
->table
);
202 LIVE_SCOPE_METER(cx
, cx
->runtime
->liveScopeProps
-= scope
->entryCount
);
203 JS_RUNTIME_UNMETER(cx
->runtime
, liveScopes
);
207 #ifdef JS_DUMP_PROPTREE_STATS
208 typedef struct JSScopeStats
{
215 jsrefcount stepMisses
;
217 jsrefcount redundantAdds
;
218 jsrefcount addFailures
;
219 jsrefcount changeFailures
;
220 jsrefcount compresses
;
223 jsrefcount removeFrees
;
224 jsrefcount uselessRemoves
;
228 JS_FRIEND_DATA(JSScopeStats
) js_scope_stats
= {0};
230 # define METER(x) JS_ATOMIC_INCREMENT(&js_scope_stats.x)
232 # define METER(x) /* nothing */
235 JS_STATIC_ASSERT(sizeof(JSHashNumber
) == 4);
236 JS_STATIC_ASSERT(sizeof(jsid
) == JS_BYTES_PER_WORD
);
238 #if JS_BYTES_PER_WORD == 4
239 # define HASH_ID(id) ((JSHashNumber)(id))
240 #elif JS_BYTES_PER_WORD == 8
241 # define HASH_ID(id) ((JSHashNumber)(id) ^ (JSHashNumber)((id) >> 32))
243 # error "Unsupported configuration"
247 * Double hashing needs the second hash code to be relatively prime to table
248 * size, so we simply make hash2 odd. The inputs to multiplicative hash are
249 * the golden ratio, expressed as a fixed-point 32 bit fraction, and the id
252 #define SCOPE_HASH0(id) (HASH_ID(id) * JS_GOLDEN_RATIO)
253 #define SCOPE_HASH1(hash0,shift) ((hash0) >> (shift))
254 #define SCOPE_HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
256 JS_FRIEND_API(JSScopeProperty
**)
257 js_SearchScope(JSScope
*scope
, jsid id
, JSBool adding
)
259 JSHashNumber hash0
, hash1
, hash2
;
260 int hashShift
, sizeLog2
;
261 JSScopeProperty
*stored
, *sprop
, **spp
, **firstRemoved
;
266 /* Not enough properties to justify hashing: search from lastProp. */
267 JS_ASSERT(!SCOPE_HAD_MIDDLE_DELETE(scope
));
268 for (spp
= &scope
->lastProp
; (sprop
= *spp
); spp
= &sprop
->parent
) {
269 if (sprop
->id
== id
) {
278 /* Compute the primary hash address. */
280 hash0
= SCOPE_HASH0(id
);
281 hashShift
= scope
->hashShift
;
282 hash1
= SCOPE_HASH1(hash0
, hashShift
);
283 spp
= scope
->table
+ hash1
;
285 /* Miss: return space for a new entry. */
287 if (SPROP_IS_FREE(stored
)) {
292 /* Hit: return entry. */
293 sprop
= SPROP_CLEAR_COLLISION(stored
);
294 if (sprop
&& sprop
->id
== id
) {
299 /* Collision: double hash. */
300 sizeLog2
= JS_DHASH_BITS
- hashShift
;
301 hash2
= SCOPE_HASH2(hash0
, sizeLog2
, hashShift
);
302 sizeMask
= JS_BITMASK(sizeLog2
);
304 /* Save the first removed entry pointer so we can recycle it if adding. */
305 if (SPROP_IS_REMOVED(stored
)) {
309 if (adding
&& !SPROP_HAD_COLLISION(stored
))
310 SPROP_FLAG_COLLISION(spp
, sprop
);
317 spp
= scope
->table
+ hash1
;
320 if (SPROP_IS_FREE(stored
)) {
322 return (adding
&& firstRemoved
) ? firstRemoved
: spp
;
325 sprop
= SPROP_CLEAR_COLLISION(stored
);
326 if (sprop
&& sprop
->id
== id
) {
331 if (SPROP_IS_REMOVED(stored
)) {
335 if (adding
&& !SPROP_HAD_COLLISION(stored
))
336 SPROP_FLAG_COLLISION(spp
, sprop
);
345 ChangeScope(JSContext
*cx
, JSScope
*scope
, int change
)
347 int oldlog2
, newlog2
;
348 uint32 oldsize
, newsize
, nbytes
;
349 JSScopeProperty
**table
, **oldtable
, **spp
, **oldspp
, *sprop
;
352 return CreateScopeTable(cx
, scope
, JS_TRUE
);
354 /* Grow, shrink, or compress by changing scope->table. */
355 oldlog2
= JS_DHASH_BITS
- scope
->hashShift
;
356 newlog2
= oldlog2
+ change
;
357 oldsize
= JS_BIT(oldlog2
);
358 newsize
= JS_BIT(newlog2
);
359 nbytes
= SCOPE_TABLE_NBYTES(newsize
);
360 table
= (JSScopeProperty
**) calloc(nbytes
, 1);
362 JS_ReportOutOfMemory(cx
);
366 /* Now that we have a new table allocated, update scope members. */
367 scope
->hashShift
= JS_DHASH_BITS
- newlog2
;
368 scope
->removedCount
= 0;
369 oldtable
= scope
->table
;
370 scope
->table
= table
;
372 /* Treat the above calloc as a JS_malloc, to match CreateScopeTable. */
373 cx
->runtime
->gcMallocBytes
+= nbytes
;
375 /* Copy only live entries, leaving removed and free ones behind. */
376 for (oldspp
= oldtable
; oldsize
!= 0; oldspp
++) {
377 sprop
= SPROP_FETCH(oldspp
);
379 spp
= js_SearchScope(scope
, sprop
->id
, JS_TRUE
);
380 JS_ASSERT(SPROP_IS_FREE(*spp
));
386 /* Finally, free the old table storage. */
387 JS_free(cx
, oldtable
);
392 * Take care to exclude the mark bits in case we're called from the GC.
394 #define SPROP_FLAGS_NOT_MATCHED (SPROP_MARK | SPROP_FLAG_SHAPE_REGEN)
397 js_HashScopeProperty(JSDHashTable
*table
, const void *key
)
399 const JSScopeProperty
*sprop
= (const JSScopeProperty
*)key
;
403 /* Accumulate from least to most random so the low bits are most random. */
405 gsop
= sprop
->getter
;
407 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ (jsword
)gsop
;
408 gsop
= sprop
->setter
;
410 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ (jsword
)gsop
;
412 hash
= JS_ROTATE_LEFT32(hash
, 4)
413 ^ (sprop
->flags
& ~SPROP_FLAGS_NOT_MATCHED
);
415 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ sprop
->attrs
;
416 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ sprop
->shortid
;
417 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ sprop
->slot
;
418 hash
= JS_ROTATE_LEFT32(hash
, 4) ^ sprop
->id
;
422 #define SPROP_MATCH(sprop, child) \
423 SPROP_MATCH_PARAMS(sprop, (child)->id, (child)->getter, (child)->setter, \
424 (child)->slot, (child)->attrs, (child)->flags, \
427 #define SPROP_MATCH_PARAMS(sprop, aid, agetter, asetter, aslot, aattrs, \
429 ((sprop)->id == (aid) && \
430 SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
433 #define SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
435 ((sprop)->getter == (agetter) && \
436 (sprop)->setter == (asetter) && \
437 (sprop)->slot == (aslot) && \
438 (sprop)->attrs == (aattrs) && \
439 (((sprop)->flags ^ (aflags)) & ~SPROP_FLAGS_NOT_MATCHED) == 0 && \
440 (sprop)->shortid == (ashortid))
443 js_MatchScopeProperty(JSDHashTable
*table
,
444 const JSDHashEntryHdr
*hdr
,
447 const JSPropertyTreeEntry
*entry
= (const JSPropertyTreeEntry
*)hdr
;
448 const JSScopeProperty
*sprop
= entry
->child
;
449 const JSScopeProperty
*kprop
= (const JSScopeProperty
*)key
;
451 return SPROP_MATCH(sprop
, kprop
);
454 static const JSDHashTableOps PropertyTreeHashOps
= {
457 js_HashScopeProperty
,
458 js_MatchScopeProperty
,
459 JS_DHashMoveEntryStub
,
460 JS_DHashClearEntryStub
,
461 JS_DHashFinalizeStub
,
466 * A property tree node on rt->propertyFreeList overlays the following prefix
467 * struct on JSScopeProperty.
469 typedef struct FreeNode
{
471 JSScopeProperty
*next
;
472 JSScopeProperty
**prevp
;
475 #define FREENODE(sprop) ((FreeNode *) (sprop))
477 #define FREENODE_INSERT(list, sprop) \
479 FREENODE(sprop)->next = (list); \
480 FREENODE(sprop)->prevp = &(list); \
482 FREENODE(list)->prevp = &FREENODE(sprop)->next; \
486 #define FREENODE_REMOVE(sprop) \
488 *FREENODE(sprop)->prevp = FREENODE(sprop)->next; \
489 if (FREENODE(sprop)->next) \
490 FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp; \
493 /* NB: Called with rt->gcLock held. */
494 static JSScopeProperty
*
495 NewScopeProperty(JSRuntime
*rt
)
497 JSScopeProperty
*sprop
;
499 sprop
= rt
->propertyFreeList
;
501 FREENODE_REMOVE(sprop
);
503 JS_ARENA_ALLOCATE_CAST(sprop
, JSScopeProperty
*,
504 &rt
->propertyArenaPool
,
505 sizeof(JSScopeProperty
));
510 JS_RUNTIME_METER(rt
, livePropTreeNodes
);
511 JS_RUNTIME_METER(rt
, totalPropTreeNodes
);
515 #define CHUNKY_KIDS_TAG ((jsuword)1)
516 #define KIDS_IS_CHUNKY(kids) ((jsuword)(kids) & CHUNKY_KIDS_TAG)
517 #define KIDS_TO_CHUNK(kids) ((PropTreeKidsChunk *) \
518 ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
519 #define CHUNK_TO_KIDS(chunk) ((JSScopeProperty *) \
520 ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
521 #define MAX_KIDS_PER_CHUNK 10
522 #define CHUNK_HASH_THRESHOLD 30
524 typedef struct PropTreeKidsChunk PropTreeKidsChunk
;
526 struct PropTreeKidsChunk
{
527 JSScopeProperty
*kids
[MAX_KIDS_PER_CHUNK
];
529 PropTreeKidsChunk
*next
;
532 static PropTreeKidsChunk
*
533 NewPropTreeKidsChunk(JSRuntime
*rt
)
535 PropTreeKidsChunk
*chunk
;
537 chunk
= (PropTreeKidsChunk
*) calloc(1, sizeof *chunk
);
540 JS_ASSERT(((jsuword
)chunk
& CHUNKY_KIDS_TAG
) == 0);
541 JS_RUNTIME_METER(rt
, propTreeKidsChunks
);
546 DestroyPropTreeKidsChunk(JSRuntime
*rt
, PropTreeKidsChunk
*chunk
)
548 JS_RUNTIME_UNMETER(rt
, propTreeKidsChunks
);
550 JS_DHashTableDestroy(chunk
->table
);
554 /* NB: Called with rt->gcLock held. */
556 InsertPropertyTreeChild(JSRuntime
*rt
, JSScopeProperty
*parent
,
557 JSScopeProperty
*child
, PropTreeKidsChunk
*sweptChunk
)
560 JSPropertyTreeEntry
*entry
;
561 JSScopeProperty
**childp
, *kids
, *sprop
;
562 PropTreeKidsChunk
*chunk
, **chunkp
;
565 JS_ASSERT(!parent
|| child
->parent
!= parent
);
568 table
= &rt
->propertyTreeHash
;
569 entry
= (JSPropertyTreeEntry
*)
570 JS_DHashTableOperate(table
, child
, JS_DHASH_ADD
);
573 childp
= &entry
->child
;
579 * A "Duplicate child" case.
581 * We can't do away with child, as at least one live scope entry
582 * still points at it. What's more, that scope's lastProp chains
583 * through an ancestor line to reach child, and js_Enumerate and
584 * others count on this linkage. We must leave child out of the
585 * hash table, and not require it to be there when we eventually
586 * GC it (see RemovePropertyTreeChild, below).
588 * It is necessary to leave the duplicate child out of the hash
589 * table to preserve entry uniqueness. It is safe to leave the
590 * child out of the hash table (unlike the duplicate child cases
591 * below), because the child's parent link will be null, which
594 JS_ASSERT(sprop
!= child
&& SPROP_MATCH(sprop
, child
));
595 JS_RUNTIME_METER(rt
, duplicatePropTreeNodes
);
598 childp
= &parent
->kids
;
601 if (KIDS_IS_CHUNKY(kids
)) {
602 chunk
= KIDS_TO_CHUNK(kids
);
604 table
= chunk
->table
;
606 entry
= (JSPropertyTreeEntry
*)
607 JS_DHashTableOperate(table
, child
, JS_DHASH_ADD
);
611 entry
->child
= child
;
614 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
615 childp
= &chunk
->kids
[i
];
620 chunkp
= &chunk
->next
;
626 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
627 childp
= &chunk
->kids
[i
];
632 JS_ASSERT(sprop
!= child
);
633 if (SPROP_MATCH(sprop
, child
)) {
635 * Duplicate child, see comment above. In this
636 * case, we must let the duplicate be inserted at
637 * this level in the tree, so we keep iterating,
638 * looking for an empty slot in which to insert.
640 JS_ASSERT(sprop
!= child
);
641 JS_RUNTIME_METER(rt
, duplicatePropTreeNodes
);
644 chunkp
= &chunk
->next
;
645 } while ((chunk
= *chunkp
) != NULL
);
651 chunk
= NewPropTreeKidsChunk(rt
);
656 childp
= &chunk
->kids
[0];
659 JS_ASSERT(sprop
!= child
);
660 if (SPROP_MATCH(sprop
, child
)) {
662 * Duplicate child, see comment above. Once again, we
663 * must let duplicates created by deletion pile up in a
664 * kids-chunk-list, in order to find them when sweeping
665 * and thereby avoid dangling parent pointers.
667 JS_RUNTIME_METER(rt
, duplicatePropTreeNodes
);
672 chunk
= NewPropTreeKidsChunk(rt
);
676 parent
->kids
= CHUNK_TO_KIDS(chunk
);
677 chunk
->kids
[0] = sprop
;
678 childp
= &chunk
->kids
[1];
685 child
->parent
= parent
;
689 /* NB: Called with rt->gcLock held. */
690 static PropTreeKidsChunk
*
691 RemovePropertyTreeChild(JSRuntime
*rt
, JSScopeProperty
*child
)
693 PropTreeKidsChunk
*freeChunk
;
694 JSScopeProperty
*parent
, *kids
, *kid
;
696 PropTreeKidsChunk
*list
, *chunk
, **chunkp
, *lastChunk
;
698 JSPropertyTreeEntry
*entry
;
701 parent
= child
->parent
;
704 * Don't remove child if it is not in rt->propertyTreeHash, but only
705 * matches a root child in the table that has compatible members. See
706 * the "Duplicate child" comments in InsertPropertyTreeChild, above.
708 table
= &rt
->propertyTreeHash
;
711 if (KIDS_IS_CHUNKY(kids
)) {
712 list
= chunk
= KIDS_TO_CHUNK(kids
);
714 table
= chunk
->table
;
717 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
718 if (chunk
->kids
[i
] == child
) {
720 if (!lastChunk
->next
) {
725 chunkp
= &lastChunk
->next
;
727 } while (lastChunk
->next
);
729 for (; j
< MAX_KIDS_PER_CHUNK
; j
++) {
730 if (!lastChunk
->kids
[j
])
734 if (chunk
!= lastChunk
|| j
> i
)
735 chunk
->kids
[i
] = lastChunk
->kids
[j
];
736 lastChunk
->kids
[j
] = NULL
;
741 freeChunk
= lastChunk
;
747 chunkp
= &chunk
->next
;
748 } while ((chunk
= *chunkp
) != NULL
);
759 entry
= (JSPropertyTreeEntry
*)
760 JS_DHashTableOperate(table
, child
, JS_DHASH_LOOKUP
);
762 if (entry
->child
== child
)
763 JS_DHashTableRawRemove(table
, &entry
->hdr
);
768 static JSDHashTable
*
769 HashChunks(PropTreeKidsChunk
*chunk
, uintN n
)
773 JSScopeProperty
*sprop
;
774 JSPropertyTreeEntry
*entry
;
776 table
= JS_NewDHashTable(&PropertyTreeHashOps
, NULL
,
777 sizeof(JSPropertyTreeEntry
),
778 JS_DHASH_DEFAULT_CAPACITY(n
+ 1));
782 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
783 sprop
= chunk
->kids
[i
];
786 entry
= (JSPropertyTreeEntry
*)
787 JS_DHashTableOperate(table
, sprop
, JS_DHASH_ADD
);
788 entry
->child
= sprop
;
790 } while ((chunk
= chunk
->next
) != NULL
);
795 * Called without cx->runtime->gcLock held. This function acquires that lock
796 * only when inserting a new child. Thus there may be races to find or add a
797 * node that result in duplicates. We expect such races to be rare!
799 * We use rt->gcLock, not rt->rtLock, to allow the GC potentially to nest here
800 * under js_GenerateShape.
802 static JSScopeProperty
*
803 GetPropertyTreeChild(JSContext
*cx
, JSScopeProperty
*parent
,
804 JSScopeProperty
*child
)
808 JSPropertyTreeEntry
*entry
;
809 JSScopeProperty
*sprop
;
810 PropTreeKidsChunk
*chunk
;
818 table
= &rt
->propertyTreeHash
;
819 entry
= (JSPropertyTreeEntry
*)
820 JS_DHashTableOperate(table
, child
, JS_DHASH_ADD
);
824 sprop
= entry
->child
;
829 * Because chunks are appended at the end and never deleted except by
830 * the GC, we can search without taking the runtime's GC lock. We may
831 * miss a matching sprop added by another thread, and make a duplicate
832 * one, but that is an unlikely, therefore small, cost. The property
833 * tree has extremely low fan-out below its root in popular embeddings
834 * with real-world workloads.
836 * Patterns such as defining closures that capture a constructor's
837 * environment as getters or setters on the new object that is passed
838 * in as |this| can significantly increase fan-out below the property
839 * tree root -- see bug 335700 for details.
842 sprop
= parent
->kids
;
844 if (KIDS_IS_CHUNKY(sprop
)) {
845 chunk
= KIDS_TO_CHUNK(sprop
);
847 table
= chunk
->table
;
850 entry
= (JSPropertyTreeEntry
*)
851 JS_DHashTableOperate(table
, child
, JS_DHASH_LOOKUP
);
852 sprop
= entry
->child
;
857 goto locked_not_found
;
862 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
863 sprop
= chunk
->kids
[i
];
866 if (n
>= CHUNK_HASH_THRESHOLD
) {
867 chunk
= KIDS_TO_CHUNK(parent
->kids
);
869 table
= HashChunks(chunk
, n
);
874 JS_DHashTableDestroy(table
);
876 chunk
->table
= table
;
877 goto locked_not_found
;
883 if (SPROP_MATCH(sprop
, child
))
886 n
+= MAX_KIDS_PER_CHUNK
;
887 } while ((chunk
= chunk
->next
) != NULL
);
889 if (SPROP_MATCH(sprop
, child
))
900 * Call js_GenerateShape before the allocation to prevent collecting the
901 * new property when the shape generation triggers the GC.
903 shape
= js_GenerateShape(cx
, JS_TRUE
, NULL
);
905 sprop
= NewScopeProperty(rt
);
909 sprop
->id
= child
->id
;
910 sprop
->getter
= child
->getter
;
911 sprop
->setter
= child
->setter
;
912 sprop
->slot
= child
->slot
;
913 sprop
->attrs
= child
->attrs
;
914 sprop
->flags
= child
->flags
;
915 sprop
->shortid
= child
->shortid
;
916 sprop
->parent
= sprop
->kids
= NULL
;
917 sprop
->shape
= shape
;
920 entry
->child
= sprop
;
922 if (!InsertPropertyTreeChild(rt
, parent
, sprop
, NULL
))
932 JS_ReportOutOfMemory(cx
);
936 #ifdef DEBUG_notbrendan
937 #define CHECK_ANCESTOR_LINE(scope, sparse) \
939 if ((scope)->table) CheckAncestorLine(scope, sparse); \
943 CheckAncestorLine(JSScope
*scope
, JSBool sparse
)
946 JSScopeProperty
**spp
, **start
, **end
, *ancestorLine
, *sprop
, *aprop
;
947 uint32 entryCount
, ancestorCount
;
949 ancestorLine
= SCOPE_LAST_PROP(scope
);
951 JS_ASSERT(SCOPE_HAS_PROPERTY(scope
, ancestorLine
));
954 size
= SCOPE_CAPACITY(scope
);
955 start
= scope
->table
;
956 for (spp
= start
, end
= start
+ size
; spp
< end
; spp
++) {
957 sprop
= SPROP_FETCH(spp
);
960 for (aprop
= ancestorLine
; aprop
; aprop
= aprop
->parent
) {
967 JS_ASSERT(entryCount
== scope
->entryCount
);
970 for (sprop
= ancestorLine
; sprop
; sprop
= sprop
->parent
) {
971 if (SCOPE_HAD_MIDDLE_DELETE(scope
) &&
972 !SCOPE_HAS_PROPERTY(scope
, sprop
)) {
978 JS_ASSERT(ancestorCount
== scope
->entryCount
);
981 #define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
985 ReportReadOnlyScope(JSContext
*cx
, JSScope
*scope
)
990 str
= js_ValueToString(cx
, OBJECT_TO_JSVAL(scope
->object
));
993 bytes
= js_GetStringBytes(cx
, str
);
996 JS_ReportErrorNumber(cx
, js_GetErrorMessage
, NULL
, JSMSG_READ_ONLY
, bytes
);
1000 js_AddScopeProperty(JSContext
*cx
, JSScope
*scope
, jsid id
,
1001 JSPropertyOp getter
, JSPropertyOp setter
, uint32 slot
,
1002 uintN attrs
, uintN flags
, intN shortid
)
1004 JSScopeProperty
**spp
, *sprop
, *overwriting
, **spvec
, **spp2
, child
;
1005 uint32 size
, splen
, i
;
1007 JSTempValueRooter tvr
;
1009 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx
, scope
));
1010 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1013 * You can't add properties to a sealed scope. But note well that you can
1014 * change property attributes in a sealed scope, even though that replaces
1015 * a JSScopeProperty * in the scope's hash table -- but no id is added, so
1016 * the scope remains sealed.
1018 if (SCOPE_IS_SEALED(scope
)) {
1019 ReportReadOnlyScope(cx
, scope
);
1024 * Normalize stub getter and setter values for faster is-stub testing in
1025 * the SPROP_CALL_[GS]ETTER macros.
1027 if (getter
== JS_PropertyStub
)
1029 if (setter
== JS_PropertyStub
)
1033 * Search for id in order to claim its entry, allocating a property tree
1034 * node if one doesn't already exist for our parameters.
1036 spp
= js_SearchScope(scope
, id
, JS_TRUE
);
1037 sprop
= overwriting
= SPROP_FETCH(spp
);
1039 JS_COUNT_OPERATION(cx
, JSOW_NEW_PROPERTY
);
1041 /* Check whether we need to grow, if the load factor is >= .75. */
1042 size
= SCOPE_CAPACITY(scope
);
1043 if (scope
->entryCount
+ scope
->removedCount
>= size
- (size
>> 2)) {
1044 if (scope
->removedCount
>= size
>> 2) {
1051 if (!ChangeScope(cx
, scope
, change
) &&
1052 scope
->entryCount
+ scope
->removedCount
== size
- 1) {
1056 spp
= js_SearchScope(scope
, id
, JS_TRUE
);
1057 JS_ASSERT(!SPROP_FETCH(spp
));
1060 /* Property exists: js_SearchScope must have returned a valid entry. */
1061 JS_ASSERT(!SPROP_IS_REMOVED(*spp
));
1064 * If all property members match, this is a redundant add and we can
1065 * return early. If the caller wants to allocate a slot, but doesn't
1066 * care which slot, copy sprop->slot into slot so we can match sprop,
1067 * if all other members match.
1069 if (!(attrs
& JSPROP_SHARED
) &&
1070 slot
== SPROP_INVALID_SLOT
&&
1071 SPROP_HAS_VALID_SLOT(sprop
, scope
)) {
1074 if (SPROP_MATCH_PARAMS_AFTER_ID(sprop
, getter
, setter
, slot
, attrs
,
1076 METER(redundantAdds
);
1081 * If we are clearing sprop to force an existing property to be
1082 * overwritten (apart from a duplicate formal parameter), we must
1083 * unlink it from the ancestor line at scope->lastProp, lazily if
1084 * sprop is not lastProp. And we must remove the entry at *spp,
1085 * precisely so the lazy "middle delete" fixup code further below
1086 * won't find sprop in scope->table, in spite of sprop being on
1087 * the ancestor line.
1089 * When we finally succeed in finding or creating a new sprop
1090 * and storing its pointer at *spp, we'll use the |overwriting|
1091 * local saved when we first looked up id to decide whether we're
1092 * indeed creating a new entry, or merely overwriting an existing
1095 if (sprop
== SCOPE_LAST_PROP(scope
)) {
1097 SCOPE_REMOVE_LAST_PROP(scope
);
1098 if (!SCOPE_HAD_MIDDLE_DELETE(scope
))
1100 sprop
= SCOPE_LAST_PROP(scope
);
1101 } while (sprop
&& !SCOPE_HAS_PROPERTY(scope
, sprop
));
1102 } else if (!SCOPE_HAD_MIDDLE_DELETE(scope
)) {
1104 * If we have no hash table yet, we need one now. The middle
1105 * delete code is simple-minded that way!
1107 if (!scope
->table
) {
1108 if (!CreateScopeTable(cx
, scope
, JS_TRUE
))
1110 spp
= js_SearchScope(scope
, id
, JS_TRUE
);
1111 sprop
= overwriting
= SPROP_FETCH(spp
);
1113 SCOPE_SET_MIDDLE_DELETE(scope
);
1115 SCOPE_MAKE_UNIQUE_SHAPE(cx
, scope
);
1118 * If we fail later on trying to find or create a new sprop, we will
1119 * goto fail_overwrite and restore *spp from |overwriting|. Note that
1120 * we don't bother to keep scope->removedCount in sync, because we'll
1121 * fix up *spp and scope->entryCount shortly, no matter how control
1122 * flow returns from this function.
1125 SPROP_STORE_PRESERVING_COLLISION(spp
, NULL
);
1126 scope
->entryCount
--;
1127 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1133 * If properties were deleted from the middle of the list starting at
1134 * scope->lastProp, we may need to fork the property tree and squeeze
1135 * all deleted properties out of scope's ancestor line. Otherwise we
1136 * risk adding a node with the same id as a "middle" node, violating
1137 * the rule that properties along an ancestor line have distinct ids.
1139 if (SCOPE_HAD_MIDDLE_DELETE(scope
)) {
1140 JS_ASSERT(scope
->table
);
1141 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1143 splen
= scope
->entryCount
;
1145 JS_ASSERT(scope
->lastProp
== NULL
);
1148 * Enumerate live entries in scope->table using a temporary
1149 * vector, by walking the (possibly sparse, due to deletions)
1150 * ancestor line from scope->lastProp.
1152 spvec
= (JSScopeProperty
**)
1153 JS_malloc(cx
, SCOPE_TABLE_NBYTES(splen
));
1155 goto fail_overwrite
;
1157 sprop
= SCOPE_LAST_PROP(scope
);
1161 * NB: test SCOPE_GET_PROPERTY, not SCOPE_HAS_PROPERTY --
1162 * the latter insists that sprop->id maps to sprop, while
1163 * the former simply tests whether sprop->id is bound in
1164 * scope. We must allow for duplicate formal parameters
1165 * along the ancestor line, and fork them as needed.
1167 if (!SCOPE_GET_PROPERTY(scope
, sprop
->id
))
1170 JS_ASSERT(sprop
!= overwriting
);
1173 * If our original splen estimate, scope->entryCount,
1174 * is less than the ancestor line height, there must
1175 * be duplicate formal parameters in this (function
1176 * object) scope. Count remaining ancestors in order
1179 JSScopeProperty
*tmp
= sprop
;
1181 if (SCOPE_GET_PROPERTY(scope
, tmp
->id
))
1183 } while ((tmp
= tmp
->parent
) != NULL
);
1184 spp2
= (JSScopeProperty
**)
1185 JS_realloc(cx
, spvec
, SCOPE_TABLE_NBYTES(splen
+i
));
1188 goto fail_overwrite
;
1192 memmove(spvec
+ i
, spvec
, SCOPE_TABLE_NBYTES(splen
));
1197 } while ((sprop
= sprop
->parent
) != NULL
);
1201 * Now loop forward through spvec, forking the property tree
1202 * whenever we see a "parent gap" due to deletions from scope.
1203 * NB: sprop is null on first entry to the loop body.
1206 if (spvec
[i
]->parent
== sprop
) {
1209 sprop
= GetPropertyTreeChild(cx
, sprop
, spvec
[i
]);
1212 goto fail_overwrite
;
1215 spp2
= js_SearchScope(scope
, sprop
->id
, JS_FALSE
);
1216 JS_ASSERT(SPROP_FETCH(spp2
) == spvec
[i
]);
1217 SPROP_STORE_PRESERVING_COLLISION(spp2
, sprop
);
1219 } while (++i
< splen
);
1223 * Now sprop points to the last property in scope, where the
1224 * ancestor line from sprop to the root is dense w.r.t. scope:
1225 * it contains no nodes not mapped by scope->table, apart from
1226 * any stinking ECMA-mandated duplicate formal parameters.
1228 scope
->lastProp
= sprop
;
1229 CHECK_ANCESTOR_LINE(scope
, JS_FALSE
);
1230 JS_RUNTIME_METER(cx
->runtime
, middleDeleteFixups
);
1233 SCOPE_CLR_MIDDLE_DELETE(scope
);
1237 * Aliases share another property's slot, passed in the |slot| param.
1238 * Shared properties have no slot. Unshared properties that do not
1239 * alias another property's slot get one here, but may lose it due to
1240 * a JS_ClearScope call.
1242 if (!(flags
& SPROP_IS_ALIAS
)) {
1243 if (attrs
& JSPROP_SHARED
) {
1244 slot
= SPROP_INVALID_SLOT
;
1247 * We may have set slot from a nearly-matching sprop, above.
1248 * If so, we're overwriting that nearly-matching sprop, so we
1249 * can reuse its slot -- we don't need to allocate a new one.
1250 * Similarly, we use a specific slot if provided by the caller.
1252 if (slot
== SPROP_INVALID_SLOT
&&
1253 !js_AllocSlot(cx
, scope
->object
, &slot
)) {
1254 goto fail_overwrite
;
1260 * Check for a watchpoint on a deleted property; if one exists, change
1261 * setter to js_watch_set.
1262 * XXXbe this could get expensive with lots of watchpoints...
1264 if (!JS_CLIST_IS_EMPTY(&cx
->runtime
->watchPointList
) &&
1265 js_FindWatchPoint(cx
->runtime
, scope
, id
)) {
1266 JS_PUSH_TEMP_ROOT_SPROP(cx
, overwriting
, &tvr
);
1267 setter
= js_WrapWatchedSetter(cx
, id
, attrs
, setter
);
1268 JS_POP_TEMP_ROOT(cx
, &tvr
);
1270 goto fail_overwrite
;
1273 /* Find or create a property tree node labeled by our arguments. */
1275 child
.getter
= getter
;
1276 child
.setter
= setter
;
1278 child
.attrs
= attrs
;
1279 child
.flags
= flags
;
1280 child
.shortid
= shortid
;
1281 sprop
= GetPropertyTreeChild(cx
, scope
->lastProp
, &child
);
1283 goto fail_overwrite
;
1286 * The scope's shape defaults to its last property's shape, but may
1287 * be regenerated later as the scope diverges (from the property cache
1288 * point of view) from the structural type associated with sprop.
1290 SCOPE_EXTEND_SHAPE(cx
, scope
, sprop
);
1292 /* Store the tree node pointer in the table entry for id. */
1294 SPROP_STORE_PRESERVING_COLLISION(spp
, sprop
);
1295 scope
->entryCount
++;
1296 scope
->lastProp
= sprop
;
1297 CHECK_ANCESTOR_LINE(scope
, JS_FALSE
);
1300 LIVE_SCOPE_METER(cx
, ++cx
->runtime
->liveScopeProps
);
1301 JS_RUNTIME_METER(cx
->runtime
, totalScopeProps
);
1306 * If we reach the hashing threshold, try to allocate scope->table.
1307 * If we can't (a rare event, preceded by swapping to death on most
1308 * modern OSes), stick with linear search rather than whining about
1309 * this little set-back. Therefore we must test !scope->table and
1310 * scope->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
1311 * entry count just reached the threshold.
1313 if (!scope
->table
&& scope
->entryCount
>= SCOPE_HASH_THRESHOLD
)
1314 (void) CreateScopeTable(cx
, scope
, JS_FALSE
);
1323 * We may or may not have forked overwriting out of scope's ancestor
1324 * line, so we must check (the alternative is to set a flag above, but
1325 * that hurts the common, non-error case). If we did fork overwriting
1326 * out, we'll add it back at scope->lastProp. This means enumeration
1327 * order can change due to a failure to overwrite an id.
1328 * XXXbe very minor incompatibility
1330 for (sprop
= SCOPE_LAST_PROP(scope
); ; sprop
= sprop
->parent
) {
1332 sprop
= SCOPE_LAST_PROP(scope
);
1333 if (overwriting
->parent
== sprop
) {
1334 scope
->lastProp
= overwriting
;
1336 sprop
= GetPropertyTreeChild(cx
, sprop
, overwriting
);
1338 JS_ASSERT(sprop
!= overwriting
);
1339 scope
->lastProp
= sprop
;
1341 overwriting
= sprop
;
1345 if (sprop
== overwriting
)
1350 SPROP_STORE_PRESERVING_COLLISION(spp
, overwriting
);
1351 scope
->entryCount
++;
1353 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1360 js_ChangeScopePropertyAttrs(JSContext
*cx
, JSScope
*scope
,
1361 JSScopeProperty
*sprop
, uintN attrs
, uintN mask
,
1362 JSPropertyOp getter
, JSPropertyOp setter
)
1364 JSScopeProperty child
, *newsprop
, **spp
;
1366 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1368 /* Allow only shared (slot-less) => unshared (slot-full) transition. */
1369 attrs
|= sprop
->attrs
& mask
;
1370 JS_ASSERT(!((attrs
^ sprop
->attrs
) & JSPROP_SHARED
) ||
1371 !(attrs
& JSPROP_SHARED
));
1372 if (getter
== JS_PropertyStub
)
1374 if (setter
== JS_PropertyStub
)
1376 if (sprop
->attrs
== attrs
&&
1377 sprop
->getter
== getter
&&
1378 sprop
->setter
== setter
) {
1382 child
.id
= sprop
->id
;
1383 child
.getter
= getter
;
1384 child
.setter
= setter
;
1385 child
.slot
= sprop
->slot
;
1386 child
.attrs
= attrs
;
1387 child
.flags
= sprop
->flags
;
1388 child
.shortid
= sprop
->shortid
;
1390 if (SCOPE_LAST_PROP(scope
) == sprop
) {
1392 * Optimize the case where the last property added to scope is changed
1393 * to have a different attrs, getter, or setter. In the last property
1394 * case, we need not fork the property tree. But since we do not call
1395 * js_AddScopeProperty, we may need to allocate a new slot directly.
1397 if ((sprop
->attrs
& JSPROP_SHARED
) && !(attrs
& JSPROP_SHARED
)) {
1398 JS_ASSERT(child
.slot
== SPROP_INVALID_SLOT
);
1399 if (!js_AllocSlot(cx
, scope
->object
, &child
.slot
))
1403 newsprop
= GetPropertyTreeChild(cx
, sprop
->parent
, &child
);
1405 spp
= js_SearchScope(scope
, sprop
->id
, JS_FALSE
);
1406 JS_ASSERT(SPROP_FETCH(spp
) == sprop
);
1409 SPROP_STORE_PRESERVING_COLLISION(spp
, newsprop
);
1410 scope
->lastProp
= newsprop
;
1411 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1415 * Let js_AddScopeProperty handle this |overwriting| case, including
1416 * the conservation of sprop->slot (if it's valid). We must not call
1417 * js_RemoveScopeProperty here, it will free a valid sprop->slot and
1418 * js_AddScopeProperty won't re-allocate it.
1420 newsprop
= js_AddScopeProperty(cx
, scope
, child
.id
,
1421 child
.getter
, child
.setter
, child
.slot
,
1422 child
.attrs
, child
.flags
, child
.shortid
);
1426 if (scope
->shape
== sprop
->shape
)
1427 scope
->shape
= newsprop
->shape
;
1429 SCOPE_MAKE_UNIQUE_SHAPE(cx
, scope
);
1431 #ifdef JS_DUMP_PROPTREE_STATS
1433 METER(changeFailures
);
1439 js_RemoveScopeProperty(JSContext
*cx
, JSScope
*scope
, jsid id
)
1441 JSScopeProperty
**spp
, *stored
, *sprop
;
1444 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx
, scope
));
1445 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1446 if (SCOPE_IS_SEALED(scope
)) {
1447 ReportReadOnlyScope(cx
, scope
);
1452 spp
= js_SearchScope(scope
, id
, JS_FALSE
);
1454 sprop
= SPROP_CLEAR_COLLISION(stored
);
1456 METER(uselessRemoves
);
1460 /* Convert from a list to a hash so we can handle "middle deletes". */
1461 if (!scope
->table
&& sprop
!= scope
->lastProp
) {
1462 if (!CreateScopeTable(cx
, scope
, JS_TRUE
))
1464 spp
= js_SearchScope(scope
, id
, JS_FALSE
);
1466 sprop
= SPROP_CLEAR_COLLISION(stored
);
1469 /* First, if sprop is unshared and not cleared, free its slot number. */
1470 if (SPROP_HAS_VALID_SLOT(sprop
, scope
)) {
1471 js_FreeSlot(cx
, scope
->object
, sprop
->slot
);
1472 JS_ATOMIC_INCREMENT(&cx
->runtime
->propertyRemovals
);
1475 /* Next, remove id by setting its entry to a removed or free sentinel. */
1476 if (SPROP_HAD_COLLISION(stored
)) {
1477 JS_ASSERT(scope
->table
);
1478 *spp
= SPROP_REMOVED
;
1479 scope
->removedCount
++;
1485 scope
->entryCount
--;
1486 LIVE_SCOPE_METER(cx
, --cx
->runtime
->liveScopeProps
);
1488 /* Update scope->lastProp directly, or set its deferred update flag. */
1489 if (sprop
== SCOPE_LAST_PROP(scope
)) {
1491 SCOPE_REMOVE_LAST_PROP(scope
);
1492 if (!SCOPE_HAD_MIDDLE_DELETE(scope
))
1494 sprop
= SCOPE_LAST_PROP(scope
);
1495 } while (sprop
&& !SCOPE_HAS_PROPERTY(scope
, sprop
));
1496 } else if (!SCOPE_HAD_MIDDLE_DELETE(scope
)) {
1497 SCOPE_SET_MIDDLE_DELETE(scope
);
1499 SCOPE_MAKE_UNIQUE_SHAPE(cx
, scope
);
1500 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1502 /* Last, consider shrinking scope's table if its load factor is <= .25. */
1503 size
= SCOPE_CAPACITY(scope
);
1504 if (size
> MIN_SCOPE_SIZE
&& scope
->entryCount
<= size
>> 2) {
1506 (void) ChangeScope(cx
, scope
, -1);
1513 js_ClearScope(JSContext
*cx
, JSScope
*scope
)
1515 CHECK_ANCESTOR_LINE(scope
, JS_TRUE
);
1516 LIVE_SCOPE_METER(cx
, cx
->runtime
->liveScopeProps
-= scope
->entryCount
);
1520 SCOPE_CLR_MIDDLE_DELETE(scope
);
1521 InitMinimalScope(scope
);
1522 JS_ATOMIC_INCREMENT(&cx
->runtime
->propertyRemovals
);
1526 js_TraceId(JSTracer
*trc
, jsid id
)
1530 v
= ID_TO_VALUE(id
);
1531 JS_CALL_VALUE_TRACER(trc
, v
, "id");
1536 PrintPropertyGetterOrSetter(JSTracer
*trc
, char *buf
, size_t bufsize
)
1538 JSScopeProperty
*sprop
;
1543 JS_ASSERT(trc
->debugPrinter
== PrintPropertyGetterOrSetter
);
1544 sprop
= (JSScopeProperty
*)trc
->debugPrintArg
;
1546 name
= trc
->debugPrintIndex
? js_setter_str
: js_getter_str
;
1548 if (JSID_IS_ATOM(id
)) {
1549 n
= js_PutEscapedString(buf
, bufsize
- 1,
1550 ATOM_TO_STRING(JSID_TO_ATOM(id
)), 0);
1551 if (n
< bufsize
- 1)
1552 JS_snprintf(buf
+ n
, bufsize
- n
, " %s", name
);
1553 } else if (JSID_IS_INT(sprop
->id
)) {
1554 JS_snprintf(buf
, bufsize
, "%d %s", JSID_TO_INT(id
), name
);
1556 JS_snprintf(buf
, bufsize
, "<object> %s", name
);
1563 js_TraceScopeProperty(JSTracer
*trc
, JSScopeProperty
*sprop
)
1565 if (IS_GC_MARKING_TRACER(trc
))
1566 sprop
->flags
|= SPROP_MARK
;
1567 TRACE_ID(trc
, sprop
->id
);
1569 #if JS_HAS_GETTER_SETTER
1570 if (sprop
->attrs
& (JSPROP_GETTER
| JSPROP_SETTER
)) {
1571 if (sprop
->attrs
& JSPROP_GETTER
) {
1572 JS_ASSERT(JSVAL_IS_OBJECT((jsval
) sprop
->getter
));
1573 JS_SET_TRACING_DETAILS(trc
, PrintPropertyGetterOrSetter
, sprop
, 0);
1574 JS_CallTracer(trc
, JSVAL_TO_OBJECT((jsval
) sprop
->getter
),
1577 if (sprop
->attrs
& JSPROP_SETTER
) {
1578 JS_ASSERT(JSVAL_IS_OBJECT((jsval
) sprop
->setter
));
1579 JS_SET_TRACING_DETAILS(trc
, PrintPropertyGetterOrSetter
, sprop
, 1);
1580 JS_CallTracer(trc
, JSVAL_TO_OBJECT((jsval
) sprop
->setter
),
1584 #endif /* JS_HAS_GETTER_SETTER */
1587 #ifdef JS_DUMP_PROPTREE_STATS
1592 MeterKidCount(JSBasicStats
*bs
, uintN nkids
)
1594 JS_BASIC_STATS_ACCUM(bs
, nkids
);
1595 bs
->hist
[JS_MIN(nkids
, 10)]++;
1599 MeterPropertyTree(JSBasicStats
*bs
, JSScopeProperty
*node
)
1602 JSScopeProperty
*kids
, *kid
;
1603 PropTreeKidsChunk
*chunk
;
1608 if (KIDS_IS_CHUNKY(kids
)) {
1609 for (chunk
= KIDS_TO_CHUNK(kids
); chunk
; chunk
= chunk
->next
) {
1610 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
1611 kid
= chunk
->kids
[i
];
1614 MeterPropertyTree(bs
, kid
);
1619 MeterPropertyTree(bs
, kids
);
1624 MeterKidCount(bs
, nkids
);
1627 static JSDHashOperator
1628 js_MeterPropertyTree(JSDHashTable
*table
, JSDHashEntryHdr
*hdr
, uint32 number
,
1631 JSPropertyTreeEntry
*entry
= (JSPropertyTreeEntry
*)hdr
;
1632 JSBasicStats
*bs
= (JSBasicStats
*)arg
;
1634 MeterPropertyTree(bs
, entry
->child
);
1635 return JS_DHASH_NEXT
;
1639 DumpSubtree(JSContext
*cx
, JSScopeProperty
*sprop
, int level
, FILE *fp
)
1643 JSScopeProperty
*kids
, *kid
;
1644 PropTreeKidsChunk
*chunk
;
1647 fprintf(fp
, "%*sid ", level
, "");
1648 v
= ID_TO_VALUE(sprop
->id
);
1649 if (JSID_IS_INT(sprop
->id
)) {
1650 fprintf(fp
, "%d", JSVAL_TO_INT(v
));
1652 if (JSID_IS_ATOM(sprop
->id
)) {
1653 str
= JSVAL_TO_STRING(v
);
1655 JS_ASSERT(JSID_IS_OBJECT(sprop
->id
));
1656 str
= js_ValueToString(cx
, v
);
1657 fputs("object ", fp
);
1660 fputs("<error>", fp
);
1662 js_FileEscapedString(fp
, str
, '"');
1665 fprintf(fp
, " g/s %p/%p slot %u attrs %x flags %x shortid %d\n",
1666 (void *) sprop
->getter
, (void *) sprop
->setter
, sprop
->slot
,
1667 sprop
->attrs
, sprop
->flags
, sprop
->shortid
);
1671 if (KIDS_IS_CHUNKY(kids
)) {
1672 chunk
= KIDS_TO_CHUNK(kids
);
1674 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
1675 kid
= chunk
->kids
[i
];
1678 JS_ASSERT(kid
->parent
== sprop
);
1679 DumpSubtree(cx
, kid
, level
, fp
);
1681 } while ((chunk
= chunk
->next
) != NULL
);
1684 DumpSubtree(cx
, kid
, level
, fp
);
1689 #endif /* JS_DUMP_PROPTREE_STATS */
1692 js_SweepScopeProperties(JSContext
*cx
)
1694 JSRuntime
*rt
= cx
->runtime
;
1696 JSScopeProperty
*limit
, *sprop
, *parent
, *kids
, *kid
;
1698 PropTreeKidsChunk
*chunk
, *nextChunk
, *freeChunk
;
1701 #ifdef JS_DUMP_PROPTREE_STATS
1703 uint32 livePropCapacity
= 0, totalLiveCount
= 0;
1706 logfp
= fopen("/tmp/proptree.stats", "w");
1708 JS_BASIC_STATS_INIT(&bs
);
1709 MeterKidCount(&bs
, rt
->propertyTreeHash
.entryCount
);
1710 JS_DHashTableEnumerate(&rt
->propertyTreeHash
, js_MeterPropertyTree
, &bs
);
1713 double props
, nodes
, mean
, sigma
;
1715 props
= rt
->liveScopePropsPreSweep
;
1716 nodes
= rt
->livePropTreeNodes
;
1717 JS_ASSERT(nodes
== bs
.sum
);
1718 mean
= JS_MeanAndStdDevBS(&bs
, &sigma
);
1721 "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
1722 props
, nodes
, nodes
/ props
, mean
, sigma
, bs
.max
);
1725 JS_DumpHistogram(&bs
, logfp
);
1728 ap
= &rt
->propertyArenaPool
.first
.next
;
1729 while ((a
= *ap
) != NULL
) {
1730 limit
= (JSScopeProperty
*) a
->avail
;
1732 for (sprop
= (JSScopeProperty
*) a
->base
; sprop
< limit
; sprop
++) {
1733 /* If the id is null, sprop is already on the freelist. */
1734 if (sprop
->id
== JSVAL_NULL
)
1738 * If the mark bit is set, sprop is alive, so clear the mark bit
1739 * and continue the while loop.
1741 * Regenerate sprop->shape if it hasn't already been refreshed
1742 * during the mark phase, when live scopes' lastProp members are
1743 * followed to update both scope->shape and lastProp->shape.
1745 if (sprop
->flags
& SPROP_MARK
) {
1746 sprop
->flags
&= ~SPROP_MARK
;
1747 if (sprop
->flags
& SPROP_FLAG_SHAPE_REGEN
) {
1748 sprop
->flags
&= ~SPROP_FLAG_SHAPE_REGEN
;
1750 sprop
->shape
= ++cx
->runtime
->shapeGen
;
1751 JS_ASSERT(sprop
->shape
!= 0);
1757 /* Ok, sprop is garbage to collect: unlink it from its parent. */
1758 freeChunk
= RemovePropertyTreeChild(rt
, sprop
);
1761 * Take care to reparent all sprop's kids to their grandparent.
1762 * InsertPropertyTreeChild can potentially fail for two reasons:
1764 * 1. If parent is null, insertion into the root property hash
1765 * table may fail. We are forced to leave the kid out of the
1766 * table (as can already happen with duplicates) but ensure
1767 * that the kid's parent pointer is set to null.
1769 * 2. If parent is non-null, allocation of a new KidsChunk can
1770 * fail. To prevent this from happening, we allow sprops's own
1771 * chunks to be reused by the grandparent, which removes the
1772 * need for InsertPropertyTreeChild to malloc a new KidsChunk.
1774 * If sprop does not have chunky kids, then we rely on the
1775 * RemovePropertyTreeChild call above (which removed sprop from
1776 * its parent) either leaving one free entry, or else returning
1777 * the now-unused chunk to us so we can reuse it.
1779 * We also require the grandparent to have either no kids or else
1780 * chunky kids. A single non-chunky kid would force a new chunk to
1781 * be malloced in some cases (if sprop had a single non-chunky
1782 * kid, or a multiple of MAX_KIDS_PER_CHUNK kids). Note that
1783 * RemovePropertyTreeChild never converts a single-entry chunky
1784 * kid back to a non-chunky kid, so we are assured of correct
1790 parent
= sprop
->parent
;
1792 /* Assert that grandparent has no kids or chunky kids. */
1793 JS_ASSERT(!parent
|| !parent
->kids
||
1794 KIDS_IS_CHUNKY(parent
->kids
));
1795 if (KIDS_IS_CHUNKY(kids
)) {
1796 chunk
= KIDS_TO_CHUNK(kids
);
1798 nextChunk
= chunk
->next
;
1800 for (i
= 0; i
< MAX_KIDS_PER_CHUNK
; i
++) {
1801 kid
= chunk
->kids
[i
];
1804 JS_ASSERT(kid
->parent
== sprop
);
1807 * Clear a space in the kids array for possible
1808 * re-use by InsertPropertyTreeChild.
1810 chunk
->kids
[i
] = NULL
;
1811 if (!InsertPropertyTreeChild(rt
, parent
, kid
,
1814 * This can happen only if we failed to add an
1815 * entry to the root property hash table.
1821 if (!chunk
->kids
[0]) {
1822 /* The chunk wasn't reused, so we must free it. */
1823 DestroyPropTreeKidsChunk(rt
, chunk
);
1825 } while ((chunk
= nextChunk
) != NULL
);
1828 if (!InsertPropertyTreeChild(rt
, parent
, kid
, freeChunk
)) {
1830 * This can happen only if we failed to add an entry
1831 * to the root property hash table.
1839 if (freeChunk
&& !freeChunk
->kids
[0]) {
1840 /* The chunk wasn't reused, so we must free it. */
1841 DestroyPropTreeKidsChunk(rt
, freeChunk
);
1844 /* Clear id so we know (above) that sprop is on the freelist. */
1845 sprop
->id
= JSVAL_NULL
;
1846 FREENODE_INSERT(rt
->propertyFreeList
, sprop
);
1847 JS_RUNTIME_UNMETER(rt
, livePropTreeNodes
);
1850 /* If a contains no live properties, return it to the malloc heap. */
1851 if (liveCount
== 0) {
1852 for (sprop
= (JSScopeProperty
*) a
->base
; sprop
< limit
; sprop
++)
1853 FREENODE_REMOVE(sprop
);
1854 JS_ARENA_DESTROY(&rt
->propertyArenaPool
, a
, ap
);
1856 #ifdef JS_DUMP_PROPTREE_STATS
1857 livePropCapacity
+= limit
- (JSScopeProperty
*) a
->base
;
1858 totalLiveCount
+= liveCount
;
1864 #ifdef JS_DUMP_PROPTREE_STATS
1865 fprintf(logfp
, "arenautil %g%%\n",
1866 (totalLiveCount
&& livePropCapacity
)
1867 ? (totalLiveCount
* 100.0) / livePropCapacity
1870 #define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
1872 fprintf(logfp
, "Scope search stats:\n"
1874 " hits: %6u %5.2f%% of searches\n"
1875 " misses: %6u %5.2f%%\n"
1876 " hashes: %6u %5.2f%%\n"
1877 " steps: %6u %5.2f%% %5.2f%% of hashes\n"
1878 " stepHits: %6u %5.2f%% %5.2f%%\n"
1879 " stepMisses: %6u %5.2f%% %5.2f%%\n"
1881 " redundantAdds: %6u\n"
1882 " addFailures: %6u\n"
1883 " changeFailures: %6u\n"
1884 " compresses: %6u\n"
1887 " removeFrees: %6u\n"
1888 " uselessRemoves: %6u\n"
1890 js_scope_stats
.searches
,
1891 js_scope_stats
.hits
, RATE(hits
, searches
),
1892 js_scope_stats
.misses
, RATE(misses
, searches
),
1893 js_scope_stats
.hashes
, RATE(hashes
, searches
),
1894 js_scope_stats
.steps
, RATE(steps
, searches
), RATE(steps
, hashes
),
1895 js_scope_stats
.stepHits
,
1896 RATE(stepHits
, searches
), RATE(stepHits
, hashes
),
1897 js_scope_stats
.stepMisses
,
1898 RATE(stepMisses
, searches
), RATE(stepMisses
, hashes
),
1899 js_scope_stats
.adds
,
1900 js_scope_stats
.redundantAdds
,
1901 js_scope_stats
.addFailures
,
1902 js_scope_stats
.changeFailures
,
1903 js_scope_stats
.compresses
,
1904 js_scope_stats
.grows
,
1905 js_scope_stats
.removes
,
1906 js_scope_stats
.removeFrees
,
1907 js_scope_stats
.uselessRemoves
,
1908 js_scope_stats
.shrinks
);
1915 #ifdef DUMP_PROPERTY_TREE
1917 FILE *dumpfp
= fopen("/tmp/proptree.dump", "w");
1919 JSPropertyTreeEntry
*pte
, *end
;
1921 pte
= (JSPropertyTreeEntry
*) rt
->propertyTreeHash
.entryStore
;
1922 end
= pte
+ JS_DHASH_TABLE_SIZE(&rt
->propertyTreeHash
);
1925 DumpSubtree(cx
, pte
->child
, 0, dumpfp
);
1935 js_InitPropertyTree(JSRuntime
*rt
)
1937 if (!JS_DHashTableInit(&rt
->propertyTreeHash
, &PropertyTreeHashOps
, NULL
,
1938 sizeof(JSPropertyTreeEntry
), JS_DHASH_MIN_SIZE
)) {
1939 rt
->propertyTreeHash
.ops
= NULL
;
1942 JS_INIT_ARENA_POOL(&rt
->propertyArenaPool
, "properties",
1943 256 * sizeof(JSScopeProperty
), sizeof(void *), NULL
);
1948 js_FinishPropertyTree(JSRuntime
*rt
)
1950 if (rt
->propertyTreeHash
.ops
) {
1951 JS_DHashTableFinish(&rt
->propertyTreeHash
);
1952 rt
->propertyTreeHash
.ops
= NULL
;
1954 JS_FinishArenaPool(&rt
->propertyArenaPool
);