/[jscoverage]/trunk/js/jsscope.cpp
ViewVC logotype

Annotation of /trunk/js/jsscope.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 399 - (hide annotations)
Tue Dec 9 03:37:47 2008 UTC (11 years, 9 months ago) by siliconforks
File size: 68054 byte(s)
Use SpiderMonkey from Firefox 3.1b2.

1 siliconforks 332 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2     * vim: set ts=8 sw=4 et tw=78:
3     *
4     * ***** BEGIN LICENSE BLOCK *****
5     * Version: MPL 1.1/GPL 2.0/LGPL 2.1
6     *
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/
11     *
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
15     * License.
16     *
17     * The Original Code is Mozilla Communicator client code, released
18     * March 31, 1998.
19     *
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.
24     *
25     * Contributor(s):
26     *
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.
38     *
39     * ***** END LICENSE BLOCK ***** */
40    
41     /*
42     * JS symbol tables.
43     */
44     #include "jsstddef.h"
45     #include <stdlib.h>
46     #include <string.h>
47     #include "jstypes.h"
48     #include "jsarena.h"
49     #include "jsbit.h"
50     #include "jsclist.h"
51     #include "jsdhash.h"
52     #include "jsutil.h" /* Added by JSIFY */
53     #include "jsapi.h"
54     #include "jsatom.h"
55     #include "jscntxt.h"
56     #include "jsdbgapi.h"
57     #include "jslock.h"
58     #include "jsnum.h"
59     #include "jsscope.h"
60     #include "jsstr.h"
61    
62     JSScope *
63     js_GetMutableScope(JSContext *cx, JSObject *obj)
64     {
65     JSScope *scope, *newscope;
66     JSClass *clasp;
67     uint32 freeslot;
68    
69     scope = OBJ_SCOPE(obj);
70     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
71     if (scope->object == obj)
72     return scope;
73     newscope = js_NewScope(cx, 0, scope->map.ops, LOCKED_OBJ_GET_CLASS(obj),
74     obj);
75     if (!newscope)
76     return NULL;
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;
87     }
88     scope = (JSScope *) js_DropObjectMap(cx, &scope->map, obj);
89     JS_TRANSFER_SCOPE_LOCK(cx, scope, newscope);
90     return newscope;
91     }
92    
93     /*
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.
97     */
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 *))
102    
103     static void
104     InitMinimalScope(JSScope *scope)
105     {
106     scope->shape = 0;
107     scope->hashShift = JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2;
108     scope->entryCount = scope->removedCount = 0;
109     scope->table = NULL;
110     scope->lastProp = NULL;
111     }
112    
113     static JSBool
114     CreateScopeTable(JSContext *cx, JSScope *scope, JSBool report)
115     {
116     int sizeLog2;
117     JSScopeProperty *sprop, **spp;
118    
119     JS_ASSERT(!scope->table);
120     JS_ASSERT(scope->lastProp);
121    
122     if (scope->entryCount > SCOPE_HASH_THRESHOLD) {
123     /*
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.
129     */
130     sizeLog2 = JS_CeilingLog2(2 * scope->entryCount);
131     scope->hashShift = JS_DHASH_BITS - sizeLog2;
132     } else {
133     JS_ASSERT(scope->hashShift == JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2);
134     sizeLog2 = MIN_SCOPE_SIZE_LOG2;
135     }
136    
137     scope->table = (JSScopeProperty **)
138     calloc(JS_BIT(sizeLog2), sizeof(JSScopeProperty *));
139     if (!scope->table) {
140     if (report)
141     JS_ReportOutOfMemory(cx);
142     return JS_FALSE;
143     }
144     js_UpdateMallocCounter(cx, JS_BIT(sizeLog2) * sizeof(JSScopeProperty *));
145    
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);
150     }
151     return JS_TRUE;
152     }
153    
154     JSScope *
155     js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
156     JSObject *obj)
157     {
158     JSScope *scope;
159    
160     scope = (JSScope *) JS_malloc(cx, sizeof(JSScope));
161     if (!scope)
162     return NULL;
163    
164     js_InitObjectMap(&scope->map, nrefs, ops, clasp);
165     scope->object = obj;
166     scope->flags = 0;
167     InitMinimalScope(scope);
168    
169     #ifdef JS_THREADSAFE
170     js_InitTitle(cx, &scope->title);
171     #endif
172     JS_RUNTIME_METER(cx->runtime, liveScopes);
173     JS_RUNTIME_METER(cx->runtime, totalScopes);
174     return scope;
175     }
176    
177     #ifdef DEBUG_SCOPE_COUNT
178     extern void
179     js_unlog_scope(JSScope *scope);
180     #endif
181    
182     #if defined DEBUG || defined JS_DUMP_PROPTREE_STATS
183     # include "jsprf.h"
184     # define LIVE_SCOPE_METER(cx,expr) JS_LOCK_RUNTIME_VOID(cx->runtime,expr)
185     #else
186     # define LIVE_SCOPE_METER(cx,expr) /* nothing */
187     #endif
188    
189     void
190     js_DestroyScope(JSContext *cx, JSScope *scope)
191     {
192     #ifdef DEBUG_SCOPE_COUNT
193     js_unlog_scope(scope);
194     #endif
195    
196     #ifdef JS_THREADSAFE
197     js_FinishTitle(cx, &scope->title);
198     #endif
199     if (scope->table)
200     JS_free(cx, scope->table);
201    
202     LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= scope->entryCount);
203     JS_RUNTIME_UNMETER(cx->runtime, liveScopes);
204     JS_free(cx, scope);
205     }
206    
207     #ifdef JS_DUMP_PROPTREE_STATS
208     typedef struct JSScopeStats {
209     jsrefcount searches;
210     jsrefcount hits;
211     jsrefcount misses;
212     jsrefcount hashes;
213     jsrefcount steps;
214     jsrefcount stepHits;
215     jsrefcount stepMisses;
216     jsrefcount adds;
217     jsrefcount redundantAdds;
218     jsrefcount addFailures;
219     jsrefcount changeFailures;
220     jsrefcount compresses;
221     jsrefcount grows;
222     jsrefcount removes;
223     jsrefcount removeFrees;
224     jsrefcount uselessRemoves;
225     jsrefcount shrinks;
226     } JSScopeStats;
227    
228     JS_FRIEND_DATA(JSScopeStats) js_scope_stats = {0};
229    
230     # define METER(x) JS_ATOMIC_INCREMENT(&js_scope_stats.x)
231     #else
232     # define METER(x) /* nothing */
233     #endif
234    
235     JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4);
236     JS_STATIC_ASSERT(sizeof(jsid) == JS_BYTES_PER_WORD);
237    
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))
242     #else
243     # error "Unsupported configuration"
244     #endif
245    
246     /*
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
250     * itself.
251     */
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)
255    
256     JS_FRIEND_API(JSScopeProperty **)
257     js_SearchScope(JSScope *scope, jsid id, JSBool adding)
258     {
259     JSHashNumber hash0, hash1, hash2;
260     int hashShift, sizeLog2;
261     JSScopeProperty *stored, *sprop, **spp, **firstRemoved;
262     uint32 sizeMask;
263    
264     METER(searches);
265     if (!scope->table) {
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) {
270     METER(hits);
271     return spp;
272     }
273     }
274     METER(misses);
275     return spp;
276     }
277    
278     /* Compute the primary hash address. */
279     METER(hashes);
280     hash0 = SCOPE_HASH0(id);
281     hashShift = scope->hashShift;
282     hash1 = SCOPE_HASH1(hash0, hashShift);
283     spp = scope->table + hash1;
284    
285     /* Miss: return space for a new entry. */
286     stored = *spp;
287     if (SPROP_IS_FREE(stored)) {
288     METER(misses);
289     return spp;
290     }
291    
292     /* Hit: return entry. */
293     sprop = SPROP_CLEAR_COLLISION(stored);
294     if (sprop && sprop->id == id) {
295     METER(hits);
296     return spp;
297     }
298    
299     /* Collision: double hash. */
300     sizeLog2 = JS_DHASH_BITS - hashShift;
301     hash2 = SCOPE_HASH2(hash0, sizeLog2, hashShift);
302     sizeMask = JS_BITMASK(sizeLog2);
303    
304     /* Save the first removed entry pointer so we can recycle it if adding. */
305     if (SPROP_IS_REMOVED(stored)) {
306     firstRemoved = spp;
307     } else {
308     firstRemoved = NULL;
309     if (adding && !SPROP_HAD_COLLISION(stored))
310     SPROP_FLAG_COLLISION(spp, sprop);
311     }
312    
313     for (;;) {
314     METER(steps);
315     hash1 -= hash2;
316     hash1 &= sizeMask;
317     spp = scope->table + hash1;
318    
319     stored = *spp;
320     if (SPROP_IS_FREE(stored)) {
321     METER(stepMisses);
322     return (adding && firstRemoved) ? firstRemoved : spp;
323     }
324    
325     sprop = SPROP_CLEAR_COLLISION(stored);
326     if (sprop && sprop->id == id) {
327     METER(stepHits);
328     return spp;
329     }
330    
331     if (SPROP_IS_REMOVED(stored)) {
332     if (!firstRemoved)
333     firstRemoved = spp;
334     } else {
335     if (adding && !SPROP_HAD_COLLISION(stored))
336     SPROP_FLAG_COLLISION(spp, sprop);
337     }
338     }
339    
340     /* NOTREACHED */
341     return NULL;
342     }
343    
344     static JSBool
345     ChangeScope(JSContext *cx, JSScope *scope, int change)
346     {
347     int oldlog2, newlog2;
348     uint32 oldsize, newsize, nbytes;
349     JSScopeProperty **table, **oldtable, **spp, **oldspp, *sprop;
350    
351     if (!scope->table)
352     return CreateScopeTable(cx, scope, JS_TRUE);
353    
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);
361     if (!table) {
362     JS_ReportOutOfMemory(cx);
363     return JS_FALSE;
364     }
365    
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;
371    
372     /* Treat the above calloc as a JS_malloc, to match CreateScopeTable. */
373     cx->runtime->gcMallocBytes += nbytes;
374    
375     /* Copy only live entries, leaving removed and free ones behind. */
376     for (oldspp = oldtable; oldsize != 0; oldspp++) {
377     sprop = SPROP_FETCH(oldspp);
378     if (sprop) {
379     spp = js_SearchScope(scope, sprop->id, JS_TRUE);
380     JS_ASSERT(SPROP_IS_FREE(*spp));
381     *spp = sprop;
382     }
383     oldsize--;
384     }
385    
386     /* Finally, free the old table storage. */
387     JS_free(cx, oldtable);
388     return JS_TRUE;
389     }
390    
391     /*
392     * Take care to exclude the mark bits in case we're called from the GC.
393     */
394     #define SPROP_FLAGS_NOT_MATCHED (SPROP_MARK | SPROP_FLAG_SHAPE_REGEN)
395    
396     static JSDHashNumber
397     js_HashScopeProperty(JSDHashTable *table, const void *key)
398     {
399     const JSScopeProperty *sprop = (const JSScopeProperty *)key;
400     JSDHashNumber hash;
401     JSPropertyOp gsop;
402    
403     /* Accumulate from least to most random so the low bits are most random. */
404     hash = 0;
405     gsop = sprop->getter;
406     if (gsop)
407     hash = JS_ROTATE_LEFT32(hash, 4) ^ (jsword)gsop;
408     gsop = sprop->setter;
409     if (gsop)
410     hash = JS_ROTATE_LEFT32(hash, 4) ^ (jsword)gsop;
411    
412     hash = JS_ROTATE_LEFT32(hash, 4)
413     ^ (sprop->flags & ~SPROP_FLAGS_NOT_MATCHED);
414    
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;
419     return hash;
420     }
421    
422     #define SPROP_MATCH(sprop, child) \
423     SPROP_MATCH_PARAMS(sprop, (child)->id, (child)->getter, (child)->setter, \
424     (child)->slot, (child)->attrs, (child)->flags, \
425     (child)->shortid)
426    
427     #define SPROP_MATCH_PARAMS(sprop, aid, agetter, asetter, aslot, aattrs, \
428     aflags, ashortid) \
429     ((sprop)->id == (aid) && \
430     SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
431     aflags, ashortid))
432    
433     #define SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
434     aflags, ashortid) \
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))
441    
442     static JSBool
443     js_MatchScopeProperty(JSDHashTable *table,
444     const JSDHashEntryHdr *hdr,
445     const void *key)
446     {
447     const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr;
448     const JSScopeProperty *sprop = entry->child;
449     const JSScopeProperty *kprop = (const JSScopeProperty *)key;
450    
451     return SPROP_MATCH(sprop, kprop);
452     }
453    
454     static const JSDHashTableOps PropertyTreeHashOps = {
455     JS_DHashAllocTable,
456     JS_DHashFreeTable,
457     js_HashScopeProperty,
458     js_MatchScopeProperty,
459     JS_DHashMoveEntryStub,
460     JS_DHashClearEntryStub,
461     JS_DHashFinalizeStub,
462     NULL
463     };
464    
465     /*
466     * A property tree node on rt->propertyFreeList overlays the following prefix
467     * struct on JSScopeProperty.
468     */
469     typedef struct FreeNode {
470     jsid id;
471     JSScopeProperty *next;
472     JSScopeProperty **prevp;
473     } FreeNode;
474    
475     #define FREENODE(sprop) ((FreeNode *) (sprop))
476    
477     #define FREENODE_INSERT(list, sprop) \
478     JS_BEGIN_MACRO \
479     FREENODE(sprop)->next = (list); \
480     FREENODE(sprop)->prevp = &(list); \
481     if (list) \
482     FREENODE(list)->prevp = &FREENODE(sprop)->next; \
483     (list) = (sprop); \
484     JS_END_MACRO
485    
486     #define FREENODE_REMOVE(sprop) \
487     JS_BEGIN_MACRO \
488     *FREENODE(sprop)->prevp = FREENODE(sprop)->next; \
489     if (FREENODE(sprop)->next) \
490     FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp; \
491     JS_END_MACRO
492    
493     /* NB: Called with rt->gcLock held. */
494     static JSScopeProperty *
495     NewScopeProperty(JSRuntime *rt)
496     {
497     JSScopeProperty *sprop;
498    
499     sprop = rt->propertyFreeList;
500     if (sprop) {
501     FREENODE_REMOVE(sprop);
502     } else {
503     JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *,
504     &rt->propertyArenaPool,
505     sizeof(JSScopeProperty));
506     if (!sprop)
507     return NULL;
508     }
509    
510     JS_RUNTIME_METER(rt, livePropTreeNodes);
511     JS_RUNTIME_METER(rt, totalPropTreeNodes);
512     return sprop;
513     }
514    
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
523    
524     typedef struct PropTreeKidsChunk PropTreeKidsChunk;
525    
526     struct PropTreeKidsChunk {
527     JSScopeProperty *kids[MAX_KIDS_PER_CHUNK];
528     JSDHashTable *table;
529     PropTreeKidsChunk *next;
530     };
531    
532     static PropTreeKidsChunk *
533     NewPropTreeKidsChunk(JSRuntime *rt)
534     {
535     PropTreeKidsChunk *chunk;
536    
537     chunk = (PropTreeKidsChunk *) calloc(1, sizeof *chunk);
538     if (!chunk)
539     return NULL;
540     JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0);
541     JS_RUNTIME_METER(rt, propTreeKidsChunks);
542     return chunk;
543     }
544    
545     static void
546     DestroyPropTreeKidsChunk(JSRuntime *rt, PropTreeKidsChunk *chunk)
547     {
548     JS_RUNTIME_UNMETER(rt, propTreeKidsChunks);
549     if (chunk->table)
550     JS_DHashTableDestroy(chunk->table);
551     free(chunk);
552     }
553    
554     /* NB: Called with rt->gcLock held. */
555     static JSBool
556     InsertPropertyTreeChild(JSRuntime *rt, JSScopeProperty *parent,
557     JSScopeProperty *child, PropTreeKidsChunk *sweptChunk)
558     {
559     JSDHashTable *table;
560     JSPropertyTreeEntry *entry;
561     JSScopeProperty **childp, *kids, *sprop;
562     PropTreeKidsChunk *chunk, **chunkp;
563     uintN i;
564    
565     JS_ASSERT(!parent || child->parent != parent);
566    
567     if (!parent) {
568     table = &rt->propertyTreeHash;
569     entry = (JSPropertyTreeEntry *)
570     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
571     if (!entry)
572     return JS_FALSE;
573     childp = &entry->child;
574     sprop = *childp;
575     if (!sprop) {
576     *childp = child;
577     } else {
578     /*
579     * A "Duplicate child" case.
580     *
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).
587     *
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
592     * can't dangle.
593     */
594     JS_ASSERT(sprop != child && SPROP_MATCH(sprop, child));
595     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
596     }
597     } else {
598     childp = &parent->kids;
599     kids = *childp;
600     if (kids) {
601     if (KIDS_IS_CHUNKY(kids)) {
602     chunk = KIDS_TO_CHUNK(kids);
603    
604     table = chunk->table;
605     if (table) {
606     entry = (JSPropertyTreeEntry *)
607     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
608     if (!entry)
609     return JS_FALSE;
610     if (!entry->child) {
611     entry->child = child;
612     while (chunk->next)
613     chunk = chunk->next;
614     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
615     childp = &chunk->kids[i];
616     sprop = *childp;
617     if (!sprop)
618     goto insert;
619     }
620     chunkp = &chunk->next;
621     goto new_chunk;
622     }
623     }
624    
625     do {
626     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
627     childp = &chunk->kids[i];
628     sprop = *childp;
629     if (!sprop)
630     goto insert;
631    
632     JS_ASSERT(sprop != child);
633     if (SPROP_MATCH(sprop, child)) {
634     /*
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.
639     */
640     JS_ASSERT(sprop != child);
641     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
642     }
643     }
644     chunkp = &chunk->next;
645     } while ((chunk = *chunkp) != NULL);
646    
647     new_chunk:
648     if (sweptChunk) {
649     chunk = sweptChunk;
650     } else {
651     chunk = NewPropTreeKidsChunk(rt);
652     if (!chunk)
653     return JS_FALSE;
654     }
655     *chunkp = chunk;
656     childp = &chunk->kids[0];
657     } else {
658     sprop = kids;
659     JS_ASSERT(sprop != child);
660     if (SPROP_MATCH(sprop, child)) {
661     /*
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.
666     */
667     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
668     }
669     if (sweptChunk) {
670     chunk = sweptChunk;
671     } else {
672     chunk = NewPropTreeKidsChunk(rt);
673     if (!chunk)
674     return JS_FALSE;
675     }
676     parent->kids = CHUNK_TO_KIDS(chunk);
677     chunk->kids[0] = sprop;
678     childp = &chunk->kids[1];
679     }
680     }
681     insert:
682     *childp = child;
683     }
684    
685     child->parent = parent;
686     return JS_TRUE;
687     }
688    
689     /* NB: Called with rt->gcLock held. */
690     static PropTreeKidsChunk *
691     RemovePropertyTreeChild(JSRuntime *rt, JSScopeProperty *child)
692     {
693     PropTreeKidsChunk *freeChunk;
694     JSScopeProperty *parent, *kids, *kid;
695     JSDHashTable *table;
696     PropTreeKidsChunk *list, *chunk, **chunkp, *lastChunk;
697     uintN i, j;
698     JSPropertyTreeEntry *entry;
699    
700     freeChunk = NULL;
701     parent = child->parent;
702     if (!parent) {
703     /*
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.
707     */
708     table = &rt->propertyTreeHash;
709     } else {
710     kids = parent->kids;
711     if (KIDS_IS_CHUNKY(kids)) {
712     list = chunk = KIDS_TO_CHUNK(kids);
713     chunkp = &list;
714     table = chunk->table;
715    
716     do {
717     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
718     if (chunk->kids[i] == child) {
719     lastChunk = chunk;
720     if (!lastChunk->next) {
721     j = i + 1;
722     } else {
723     j = 0;
724     do {
725     chunkp = &lastChunk->next;
726     lastChunk = *chunkp;
727     } while (lastChunk->next);
728     }
729     for (; j < MAX_KIDS_PER_CHUNK; j++) {
730     if (!lastChunk->kids[j])
731     break;
732     }
733     --j;
734     if (chunk != lastChunk || j > i)
735     chunk->kids[i] = lastChunk->kids[j];
736     lastChunk->kids[j] = NULL;
737     if (j == 0) {
738     *chunkp = NULL;
739     if (!list)
740     parent->kids = NULL;
741     freeChunk = lastChunk;
742     }
743     goto out;
744     }
745     }
746    
747     chunkp = &chunk->next;
748     } while ((chunk = *chunkp) != NULL);
749     } else {
750     table = NULL;
751     kid = kids;
752     if (kid == child)
753     parent->kids = NULL;
754     }
755     }
756    
757     out:
758     if (table) {
759     entry = (JSPropertyTreeEntry *)
760     JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
761    
762     if (entry->child == child)
763     JS_DHashTableRawRemove(table, &entry->hdr);
764     }
765     return freeChunk;
766     }
767    
768     static JSDHashTable *
769     HashChunks(PropTreeKidsChunk *chunk, uintN n)
770     {
771     JSDHashTable *table;
772     uintN i;
773     JSScopeProperty *sprop;
774     JSPropertyTreeEntry *entry;
775    
776     table = JS_NewDHashTable(&PropertyTreeHashOps, NULL,
777     sizeof(JSPropertyTreeEntry),
778     JS_DHASH_DEFAULT_CAPACITY(n + 1));
779     if (!table)
780     return NULL;
781     do {
782     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
783     sprop = chunk->kids[i];
784     if (!sprop)
785     break;
786     entry = (JSPropertyTreeEntry *)
787     JS_DHashTableOperate(table, sprop, JS_DHASH_ADD);
788     entry->child = sprop;
789     }
790     } while ((chunk = chunk->next) != NULL);
791     return table;
792     }
793    
794     /*
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!
798     *
799     * We use rt->gcLock, not rt->rtLock, to allow the GC potentially to nest here
800     * under js_GenerateShape.
801     */
802     static JSScopeProperty *
803     GetPropertyTreeChild(JSContext *cx, JSScopeProperty *parent,
804     JSScopeProperty *child)
805     {
806     JSRuntime *rt;
807     JSDHashTable *table;
808     JSPropertyTreeEntry *entry;
809     JSScopeProperty *sprop;
810     PropTreeKidsChunk *chunk;
811     uintN i, n;
812 siliconforks 399 uint32 shape;
813 siliconforks 332
814     rt = cx->runtime;
815     if (!parent) {
816     JS_LOCK_GC(rt);
817    
818     table = &rt->propertyTreeHash;
819     entry = (JSPropertyTreeEntry *)
820     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
821     if (!entry)
822     goto out_of_memory;
823    
824     sprop = entry->child;
825     if (sprop)
826     goto out;
827     } else {
828     /*
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.
835     *
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.
840     */
841     entry = NULL;
842     sprop = parent->kids;
843     if (sprop) {
844     if (KIDS_IS_CHUNKY(sprop)) {
845     chunk = KIDS_TO_CHUNK(sprop);
846    
847     table = chunk->table;
848     if (table) {
849     JS_LOCK_GC(rt);
850     entry = (JSPropertyTreeEntry *)
851     JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
852     sprop = entry->child;
853     if (sprop) {
854     JS_UNLOCK_GC(rt);
855     return sprop;
856     }
857     goto locked_not_found;
858     }
859    
860     n = 0;
861     do {
862     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
863     sprop = chunk->kids[i];
864     if (!sprop) {
865     n += i;
866     if (n >= CHUNK_HASH_THRESHOLD) {
867     chunk = KIDS_TO_CHUNK(parent->kids);
868     if (!chunk->table) {
869     table = HashChunks(chunk, n);
870     JS_LOCK_GC(rt);
871     if (!table)
872     goto out_of_memory;
873     if (chunk->table)
874     JS_DHashTableDestroy(table);
875     else
876     chunk->table = table;
877     goto locked_not_found;
878     }
879     }
880     goto not_found;
881     }
882    
883     if (SPROP_MATCH(sprop, child))
884     return sprop;
885     }
886     n += MAX_KIDS_PER_CHUNK;
887     } while ((chunk = chunk->next) != NULL);
888     } else {
889     if (SPROP_MATCH(sprop, child))
890     return sprop;
891     }
892     }
893    
894     not_found:
895     JS_LOCK_GC(rt);
896     }
897    
898     locked_not_found:
899 siliconforks 399 /*
900     * Call js_GenerateShape before the allocation to prevent collecting the
901     * new property when the shape generation triggers the GC.
902     */
903     shape = js_GenerateShape(cx, JS_TRUE, NULL);
904    
905 siliconforks 332 sprop = NewScopeProperty(rt);
906     if (!sprop)
907     goto out_of_memory;
908    
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 siliconforks 399 sprop->shape = shape;
918 siliconforks 332
919     if (!parent) {
920     entry->child = sprop;
921     } else {
922     if (!InsertPropertyTreeChild(rt, parent, sprop, NULL))
923     goto out_of_memory;
924     }
925    
926     out:
927     JS_UNLOCK_GC(rt);
928     return sprop;
929    
930     out_of_memory:
931     JS_UNLOCK_GC(rt);
932     JS_ReportOutOfMemory(cx);
933     return NULL;
934     }
935    
936     #ifdef DEBUG_notbrendan
937     #define CHECK_ANCESTOR_LINE(scope, sparse) \
938     JS_BEGIN_MACRO \
939     if ((scope)->table) CheckAncestorLine(scope, sparse); \
940     JS_END_MACRO
941    
942     static void
943     CheckAncestorLine(JSScope *scope, JSBool sparse)
944     {
945     uint32 size;
946     JSScopeProperty **spp, **start, **end, *ancestorLine, *sprop, *aprop;
947     uint32 entryCount, ancestorCount;
948    
949     ancestorLine = SCOPE_LAST_PROP(scope);
950     if (ancestorLine)
951     JS_ASSERT(SCOPE_HAS_PROPERTY(scope, ancestorLine));
952    
953     entryCount = 0;
954     size = SCOPE_CAPACITY(scope);
955     start = scope->table;
956     for (spp = start, end = start + size; spp < end; spp++) {
957     sprop = SPROP_FETCH(spp);
958     if (sprop) {
959     entryCount++;
960     for (aprop = ancestorLine; aprop; aprop = aprop->parent) {
961     if (aprop == sprop)
962     break;
963     }
964     JS_ASSERT(aprop);
965     }
966     }
967     JS_ASSERT(entryCount == scope->entryCount);
968    
969     ancestorCount = 0;
970     for (sprop = ancestorLine; sprop; sprop = sprop->parent) {
971     if (SCOPE_HAD_MIDDLE_DELETE(scope) &&
972     !SCOPE_HAS_PROPERTY(scope, sprop)) {
973     JS_ASSERT(sparse);
974     continue;
975     }
976     ancestorCount++;
977     }
978     JS_ASSERT(ancestorCount == scope->entryCount);
979     }
980     #else
981     #define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
982     #endif
983    
984     static void
985     ReportReadOnlyScope(JSContext *cx, JSScope *scope)
986     {
987     JSString *str;
988     const char *bytes;
989    
990     str = js_ValueToString(cx, OBJECT_TO_JSVAL(scope->object));
991     if (!str)
992     return;
993     bytes = js_GetStringBytes(cx, str);
994     if (!bytes)
995     return;
996     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_READ_ONLY, bytes);
997     }
998    
999     JSScopeProperty *
1000     js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
1001     JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
1002     uintN attrs, uintN flags, intN shortid)
1003     {
1004     JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child;
1005     uint32 size, splen, i;
1006     int change;
1007     JSTempValueRooter tvr;
1008    
1009     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
1010     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1011    
1012     /*
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.
1017     */
1018     if (SCOPE_IS_SEALED(scope)) {
1019     ReportReadOnlyScope(cx, scope);
1020     return NULL;
1021     }
1022    
1023     /*
1024     * Normalize stub getter and setter values for faster is-stub testing in
1025     * the SPROP_CALL_[GS]ETTER macros.
1026     */
1027     if (getter == JS_PropertyStub)
1028     getter = NULL;
1029     if (setter == JS_PropertyStub)
1030     setter = NULL;
1031    
1032     /*
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.
1035     */
1036     spp = js_SearchScope(scope, id, JS_TRUE);
1037     sprop = overwriting = SPROP_FETCH(spp);
1038     if (!sprop) {
1039     JS_COUNT_OPERATION(cx, JSOW_NEW_PROPERTY);
1040    
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) {
1045     METER(compresses);
1046     change = 0;
1047     } else {
1048     METER(grows);
1049     change = 1;
1050     }
1051     if (!ChangeScope(cx, scope, change) &&
1052     scope->entryCount + scope->removedCount == size - 1) {
1053     METER(addFailures);
1054     return NULL;
1055     }
1056     spp = js_SearchScope(scope, id, JS_TRUE);
1057     JS_ASSERT(!SPROP_FETCH(spp));
1058     }
1059     } else {
1060     /* Property exists: js_SearchScope must have returned a valid entry. */
1061     JS_ASSERT(!SPROP_IS_REMOVED(*spp));
1062    
1063     /*
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.
1068     */
1069     if (!(attrs & JSPROP_SHARED) &&
1070     slot == SPROP_INVALID_SLOT &&
1071     SPROP_HAS_VALID_SLOT(sprop, scope)) {
1072     slot = sprop->slot;
1073     }
1074     if (SPROP_MATCH_PARAMS_AFTER_ID(sprop, getter, setter, slot, attrs,
1075     flags, shortid)) {
1076     METER(redundantAdds);
1077     return sprop;
1078     }
1079    
1080     /*
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.
1088     *
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
1093     * property.
1094     */
1095     if (sprop == SCOPE_LAST_PROP(scope)) {
1096     do {
1097     SCOPE_REMOVE_LAST_PROP(scope);
1098     if (!SCOPE_HAD_MIDDLE_DELETE(scope))
1099     break;
1100     sprop = SCOPE_LAST_PROP(scope);
1101     } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
1102     } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
1103     /*
1104     * If we have no hash table yet, we need one now. The middle
1105     * delete code is simple-minded that way!
1106     */
1107     if (!scope->table) {
1108     if (!CreateScopeTable(cx, scope, JS_TRUE))
1109     return NULL;
1110     spp = js_SearchScope(scope, id, JS_TRUE);
1111     sprop = overwriting = SPROP_FETCH(spp);
1112     }
1113     SCOPE_SET_MIDDLE_DELETE(scope);
1114     }
1115     SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1116    
1117     /*
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.
1123     */
1124     if (scope->table)
1125     SPROP_STORE_PRESERVING_COLLISION(spp, NULL);
1126     scope->entryCount--;
1127     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1128     sprop = NULL;
1129     }
1130    
1131     if (!sprop) {
1132     /*
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.
1138     */
1139     if (SCOPE_HAD_MIDDLE_DELETE(scope)) {
1140     JS_ASSERT(scope->table);
1141     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1142    
1143     splen = scope->entryCount;
1144     if (splen == 0) {
1145     JS_ASSERT(scope->lastProp == NULL);
1146     } else {
1147     /*
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.
1151     */
1152     spvec = (JSScopeProperty **)
1153     JS_malloc(cx, SCOPE_TABLE_NBYTES(splen));
1154     if (!spvec)
1155     goto fail_overwrite;
1156     i = splen;
1157     sprop = SCOPE_LAST_PROP(scope);
1158     JS_ASSERT(sprop);
1159     do {
1160     /*
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.
1166     */
1167     if (!SCOPE_GET_PROPERTY(scope, sprop->id))
1168     continue;
1169    
1170     JS_ASSERT(sprop != overwriting);
1171     if (i == 0) {
1172     /*
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
1177     * to realloc spvec.
1178     */
1179     JSScopeProperty *tmp = sprop;
1180     do {
1181     if (SCOPE_GET_PROPERTY(scope, tmp->id))
1182     i++;
1183     } while ((tmp = tmp->parent) != NULL);
1184     spp2 = (JSScopeProperty **)
1185     JS_realloc(cx, spvec, SCOPE_TABLE_NBYTES(splen+i));
1186     if (!spp2) {
1187     JS_free(cx, spvec);
1188     goto fail_overwrite;
1189     }
1190    
1191     spvec = spp2;
1192     memmove(spvec + i, spvec, SCOPE_TABLE_NBYTES(splen));
1193     splen += i;
1194     }
1195    
1196     spvec[--i] = sprop;
1197     } while ((sprop = sprop->parent) != NULL);
1198     JS_ASSERT(i == 0);
1199    
1200     /*
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.
1204     */
1205     do {
1206     if (spvec[i]->parent == sprop) {
1207     sprop = spvec[i];
1208     } else {
1209     sprop = GetPropertyTreeChild(cx, sprop, spvec[i]);
1210     if (!sprop) {
1211     JS_free(cx, spvec);
1212     goto fail_overwrite;
1213     }
1214    
1215     spp2 = js_SearchScope(scope, sprop->id, JS_FALSE);
1216     JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]);
1217     SPROP_STORE_PRESERVING_COLLISION(spp2, sprop);
1218     }
1219     } while (++i < splen);
1220     JS_free(cx, spvec);
1221    
1222     /*
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.
1227     */
1228     scope->lastProp = sprop;
1229     CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1230     JS_RUNTIME_METER(cx->runtime, middleDeleteFixups);
1231     }
1232    
1233     SCOPE_CLR_MIDDLE_DELETE(scope);
1234     }
1235    
1236     /*
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.
1241     */
1242     if (!(flags & SPROP_IS_ALIAS)) {
1243     if (attrs & JSPROP_SHARED) {
1244     slot = SPROP_INVALID_SLOT;
1245     } else {
1246     /*
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.
1251     */
1252     if (slot == SPROP_INVALID_SLOT &&
1253     !js_AllocSlot(cx, scope->object, &slot)) {
1254     goto fail_overwrite;
1255     }
1256     }
1257     }
1258    
1259     /*
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...
1263     */
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);
1269     if (!setter)
1270     goto fail_overwrite;
1271     }
1272    
1273     /* Find or create a property tree node labeled by our arguments. */
1274     child.id = id;
1275     child.getter = getter;
1276     child.setter = setter;
1277     child.slot = slot;
1278     child.attrs = attrs;
1279     child.flags = flags;
1280     child.shortid = shortid;
1281     sprop = GetPropertyTreeChild(cx, scope->lastProp, &child);
1282     if (!sprop)
1283     goto fail_overwrite;
1284    
1285     /*
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.
1289     */
1290     SCOPE_EXTEND_SHAPE(cx, scope, sprop);
1291    
1292     /* Store the tree node pointer in the table entry for id. */
1293     if (scope->table)
1294     SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
1295     scope->entryCount++;
1296     scope->lastProp = sprop;
1297     CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1298     #ifdef DEBUG
1299     if (!overwriting) {
1300     LIVE_SCOPE_METER(cx, ++cx->runtime->liveScopeProps);
1301     JS_RUNTIME_METER(cx->runtime, totalScopeProps);
1302     }
1303     #endif
1304    
1305     /*
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.
1312     */
1313     if (!scope->table && scope->entryCount >= SCOPE_HASH_THRESHOLD)
1314     (void) CreateScopeTable(cx, scope, JS_FALSE);
1315     }
1316    
1317     METER(adds);
1318     return sprop;
1319    
1320     fail_overwrite:
1321     if (overwriting) {
1322     /*
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
1329     */
1330     for (sprop = SCOPE_LAST_PROP(scope); ; sprop = sprop->parent) {
1331     if (!sprop) {
1332     sprop = SCOPE_LAST_PROP(scope);
1333     if (overwriting->parent == sprop) {
1334     scope->lastProp = overwriting;
1335     } else {
1336     sprop = GetPropertyTreeChild(cx, sprop, overwriting);
1337     if (sprop) {
1338     JS_ASSERT(sprop != overwriting);
1339     scope->lastProp = sprop;
1340     }
1341     overwriting = sprop;
1342     }
1343     break;
1344     }
1345     if (sprop == overwriting)
1346     break;
1347     }
1348     if (overwriting) {
1349     if (scope->table)
1350     SPROP_STORE_PRESERVING_COLLISION(spp, overwriting);
1351     scope->entryCount++;
1352     }
1353     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1354     }
1355     METER(addFailures);
1356     return NULL;
1357     }
1358    
1359     JSScopeProperty *
1360     js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
1361     JSScopeProperty *sprop, uintN attrs, uintN mask,
1362     JSPropertyOp getter, JSPropertyOp setter)
1363     {
1364     JSScopeProperty child, *newsprop, **spp;
1365    
1366     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1367    
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)
1373     getter = NULL;
1374     if (setter == JS_PropertyStub)
1375     setter = NULL;
1376     if (sprop->attrs == attrs &&
1377     sprop->getter == getter &&
1378     sprop->setter == setter) {
1379     return sprop;
1380     }
1381    
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;
1389    
1390     if (SCOPE_LAST_PROP(scope) == sprop) {
1391     /*
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.
1396     */
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))
1400     return NULL;
1401     }
1402    
1403     newsprop = GetPropertyTreeChild(cx, sprop->parent, &child);
1404     if (newsprop) {
1405     spp = js_SearchScope(scope, sprop->id, JS_FALSE);
1406     JS_ASSERT(SPROP_FETCH(spp) == sprop);
1407    
1408     if (scope->table)
1409     SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
1410     scope->lastProp = newsprop;
1411     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1412     }
1413     } else {
1414     /*
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.
1419     */
1420     newsprop = js_AddScopeProperty(cx, scope, child.id,
1421     child.getter, child.setter, child.slot,
1422     child.attrs, child.flags, child.shortid);
1423     }
1424    
1425     if (newsprop) {
1426     if (scope->shape == sprop->shape)
1427     scope->shape = newsprop->shape;
1428     else
1429     SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1430     }
1431     #ifdef JS_DUMP_PROPTREE_STATS
1432     else
1433     METER(changeFailures);
1434     #endif
1435     return newsprop;
1436     }
1437    
1438     JSBool
1439     js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id)
1440     {
1441     JSScopeProperty **spp, *stored, *sprop;
1442     uint32 size;
1443    
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);
1448     return JS_FALSE;
1449     }
1450     METER(removes);
1451    
1452     spp = js_SearchScope(scope, id, JS_FALSE);
1453     stored = *spp;
1454     sprop = SPROP_CLEAR_COLLISION(stored);
1455     if (!sprop) {
1456     METER(uselessRemoves);
1457     return JS_TRUE;
1458     }
1459    
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))
1463     return JS_FALSE;
1464     spp = js_SearchScope(scope, id, JS_FALSE);
1465     stored = *spp;
1466     sprop = SPROP_CLEAR_COLLISION(stored);
1467     }
1468    
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);
1473     }
1474    
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++;
1480     } else {
1481     METER(removeFrees);
1482     if (scope->table)
1483     *spp = NULL;
1484     }
1485     scope->entryCount--;
1486     LIVE_SCOPE_METER(cx, --cx->runtime->liveScopeProps);
1487    
1488     /* Update scope->lastProp directly, or set its deferred update flag. */
1489     if (sprop == SCOPE_LAST_PROP(scope)) {
1490     do {
1491     SCOPE_REMOVE_LAST_PROP(scope);
1492     if (!SCOPE_HAD_MIDDLE_DELETE(scope))
1493     break;
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);
1498     }
1499     SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1500     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1501    
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) {
1505     METER(shrinks);
1506     (void) ChangeScope(cx, scope, -1);
1507     }
1508    
1509     return JS_TRUE;
1510     }
1511    
1512     void
1513     js_ClearScope(JSContext *cx, JSScope *scope)
1514     {
1515     CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1516     LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= scope->entryCount);
1517    
1518     if (scope->table)
1519     free(scope->table);
1520     SCOPE_CLR_MIDDLE_DELETE(scope);
1521     InitMinimalScope(scope);
1522     JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1523     }
1524    
1525     void
1526     js_TraceId(JSTracer *trc, jsid id)
1527     {
1528     jsval v;
1529    
1530     v = ID_TO_VALUE(id);
1531     JS_CALL_VALUE_TRACER(trc, v, "id");
1532     }
1533    
1534     #ifdef DEBUG
1535     static void
1536     PrintPropertyGetterOrSetter(JSTracer *trc, char *buf, size_t bufsize)
1537     {
1538     JSScopeProperty *sprop;
1539     jsid id;
1540     size_t n;
1541     const char *name;
1542    
1543     JS_ASSERT(trc->debugPrinter == PrintPropertyGetterOrSetter);
1544     sprop = (JSScopeProperty *)trc->debugPrintArg;
1545     id = sprop->id;
1546     name = trc->debugPrintIndex ? js_setter_str : js_getter_str;
1547    
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);
1555     } else {
1556     JS_snprintf(buf, bufsize, "<object> %s", name);
1557     }
1558     }
1559     #endif
1560    
1561    
1562     void
1563     js_TraceScopeProperty(JSTracer *trc, JSScopeProperty *sprop)
1564     {
1565     if (IS_GC_MARKING_TRACER(trc))
1566     sprop->flags |= SPROP_MARK;
1567     TRACE_ID(trc, sprop->id);
1568    
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),
1575     JSTRACE_OBJECT);
1576     }
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),
1581     JSTRACE_OBJECT);
1582     }
1583     }
1584     #endif /* JS_HAS_GETTER_SETTER */
1585     }
1586    
1587     #ifdef JS_DUMP_PROPTREE_STATS
1588    
1589     #include <stdio.h>
1590    
1591     static void
1592     MeterKidCount(JSBasicStats *bs, uintN nkids)
1593     {
1594     JS_BASIC_STATS_ACCUM(bs, nkids);
1595     bs->hist[JS_MIN(nkids, 10)]++;
1596     }
1597    
1598     static void
1599     MeterPropertyTree(JSBasicStats *bs, JSScopeProperty *node)
1600     {
1601     uintN i, nkids;
1602     JSScopeProperty *kids, *kid;
1603     PropTreeKidsChunk *chunk;
1604    
1605     nkids = 0;
1606     kids = node->kids;
1607     if (kids) {
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];
1612     if (!kid)
1613     break;
1614     MeterPropertyTree(bs, kid);
1615     nkids++;
1616     }
1617     }
1618     } else {
1619     MeterPropertyTree(bs, kids);
1620     nkids = 1;
1621     }
1622     }
1623    
1624     MeterKidCount(bs, nkids);
1625     }
1626    
1627     static JSDHashOperator
1628     js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
1629     void *arg)
1630     {
1631     JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)hdr;
1632     JSBasicStats *bs = (JSBasicStats *)arg;
1633    
1634     MeterPropertyTree(bs, entry->child);
1635     return JS_DHASH_NEXT;
1636     }
1637    
1638     static void
1639     DumpSubtree(JSContext *cx, JSScopeProperty *sprop, int level, FILE *fp)
1640     {
1641     jsval v;
1642     JSString *str;
1643     JSScopeProperty *kids, *kid;
1644     PropTreeKidsChunk *chunk;
1645     uintN i;
1646    
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));
1651     } else {
1652     if (JSID_IS_ATOM(sprop->id)) {
1653     str = JSVAL_TO_STRING(v);
1654     } else {
1655     JS_ASSERT(JSID_IS_OBJECT(sprop->id));
1656     str = js_ValueToString(cx, v);
1657     fputs("object ", fp);
1658     }
1659     if (!str)
1660     fputs("<error>", fp);
1661     else
1662     js_FileEscapedString(fp, str, '"');
1663     }
1664    
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);
1668     kids = sprop->kids;
1669     if (kids) {
1670     ++level;
1671     if (KIDS_IS_CHUNKY(kids)) {
1672     chunk = KIDS_TO_CHUNK(kids);
1673     do {
1674     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1675     kid = chunk->kids[i];
1676     if (!kid)
1677     break;
1678     JS_ASSERT(kid->parent == sprop);
1679     DumpSubtree(cx, kid, level, fp);
1680     }
1681     } while ((chunk = chunk->next) != NULL);
1682     } else {
1683     kid = kids;
1684     DumpSubtree(cx, kid, level, fp);
1685     }
1686     }
1687     }
1688    
1689     #endif /* JS_DUMP_PROPTREE_STATS */
1690    
1691     void
1692     js_SweepScopeProperties(JSContext *cx)
1693     {
1694     JSRuntime *rt = cx->runtime;
1695     JSArena **ap, *a;
1696     JSScopeProperty *limit, *sprop, *parent, *kids, *kid;
1697     uintN liveCount;
1698     PropTreeKidsChunk *chunk, *nextChunk, *freeChunk;
1699     uintN i;
1700    
1701     #ifdef JS_DUMP_PROPTREE_STATS
1702     JSBasicStats bs;
1703     uint32 livePropCapacity = 0, totalLiveCount = 0;
1704     static FILE *logfp;
1705     if (!logfp)
1706     logfp = fopen("/tmp/proptree.stats", "w");
1707    
1708     JS_BASIC_STATS_INIT(&bs);
1709     MeterKidCount(&bs, rt->propertyTreeHash.entryCount);
1710     JS_DHashTableEnumerate(&rt->propertyTreeHash, js_MeterPropertyTree, &bs);
1711    
1712     {
1713     double props, nodes, mean, sigma;
1714    
1715     props = rt->liveScopePropsPreSweep;
1716     nodes = rt->livePropTreeNodes;
1717     JS_ASSERT(nodes == bs.sum);
1718     mean = JS_MeanAndStdDevBS(&bs, &sigma);
1719    
1720     fprintf(logfp,
1721     "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
1722     props, nodes, nodes / props, mean, sigma, bs.max);
1723     }
1724    
1725     JS_DumpHistogram(&bs, logfp);
1726     #endif
1727    
1728     ap = &rt->propertyArenaPool.first.next;
1729     while ((a = *ap) != NULL) {
1730     limit = (JSScopeProperty *) a->avail;
1731     liveCount = 0;
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)
1735     continue;
1736    
1737     /*
1738     * If the mark bit is set, sprop is alive, so clear the mark bit
1739     * and continue the while loop.
1740     *
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.
1744     */
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;
1749     } else {
1750     sprop->shape = ++cx->runtime->shapeGen;
1751     JS_ASSERT(sprop->shape != 0);
1752     }
1753     liveCount++;
1754     continue;
1755     }
1756    
1757     /* Ok, sprop is garbage to collect: unlink it from its parent. */
1758     freeChunk = RemovePropertyTreeChild(rt, sprop);
1759    
1760     /*
1761     * Take care to reparent all sprop's kids to their grandparent.
1762     * InsertPropertyTreeChild can potentially fail for two reasons:
1763     *
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.
1768     *
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.
1773     *
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.
1778     *
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
1785     * behaviour.
1786     */
1787     kids = sprop->kids;
1788     if (kids) {
1789     sprop->kids = NULL;
1790     parent = sprop->parent;
1791    
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);
1797     do {
1798     nextChunk = chunk->next;
1799     chunk->next = NULL;
1800     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1801     kid = chunk->kids[i];
1802     if (!kid)
1803     break;
1804     JS_ASSERT(kid->parent == sprop);
1805    
1806     /*
1807     * Clear a space in the kids array for possible
1808     * re-use by InsertPropertyTreeChild.
1809     */
1810     chunk->kids[i] = NULL;
1811     if (!InsertPropertyTreeChild(rt, parent, kid,
1812     chunk)) {
1813     /*
1814     * This can happen only if we failed to add an
1815     * entry to the root property hash table.
1816     */
1817     JS_ASSERT(!parent);
1818     kid->parent = NULL;
1819     }
1820     }
1821     if (!chunk->kids[0]) {
1822     /* The chunk wasn't reused, so we must free it. */
1823     DestroyPropTreeKidsChunk(rt, chunk);
1824     }
1825     } while ((chunk = nextChunk) != NULL);
1826     } else {
1827     kid = kids;
1828     if (!InsertPropertyTreeChild(rt, parent, kid, freeChunk)) {
1829     /*
1830     * This can happen only if we failed to add an entry
1831     * to the root property hash table.
1832     */
1833     JS_ASSERT(!parent);
1834     kid->parent = NULL;
1835     }
1836     }
1837     }
1838    
1839     if (freeChunk && !freeChunk->kids[0]) {
1840     /* The chunk wasn't reused, so we must free it. */
1841     DestroyPropTreeKidsChunk(rt, freeChunk);
1842     }
1843    
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);
1848     }
1849    
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);
1855     } else {
1856     #ifdef JS_DUMP_PROPTREE_STATS
1857     livePropCapacity += limit - (JSScopeProperty *) a->base;
1858     totalLiveCount += liveCount;
1859     #endif
1860     ap = &a->next;
1861     }
1862     }
1863    
1864     #ifdef JS_DUMP_PROPTREE_STATS
1865     fprintf(logfp, "arenautil %g%%\n",
1866     (totalLiveCount && livePropCapacity)
1867     ? (totalLiveCount * 100.0) / livePropCapacity
1868     : 0.0);
1869    
1870     #define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
1871    
1872     fprintf(logfp, "Scope search stats:\n"
1873     " searches: %6u\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"
1880     " adds: %6u\n"
1881     " redundantAdds: %6u\n"
1882     " addFailures: %6u\n"
1883     " changeFailures: %6u\n"
1884     " compresses: %6u\n"
1885     " grows: %6u\n"
1886     " removes: %6u\n"
1887     " removeFrees: %6u\n"
1888     " uselessRemoves: %6u\n"
1889     " shrinks: %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);
1909    
1910     #undef RATE
1911    
1912     fflush(logfp);
1913     #endif
1914    
1915     #ifdef DUMP_PROPERTY_TREE
1916     {
1917     FILE *dumpfp = fopen("/tmp/proptree.dump", "w");
1918     if (dumpfp) {
1919     JSPropertyTreeEntry *pte, *end;
1920    
1921     pte = (JSPropertyTreeEntry *) rt->propertyTreeHash.entryStore;
1922     end = pte + JS_DHASH_TABLE_SIZE(&rt->propertyTreeHash);
1923     while (pte < end) {
1924     if (pte->child)
1925     DumpSubtree(cx, pte->child, 0, dumpfp);
1926     pte++;
1927     }
1928     fclose(dumpfp);
1929     }
1930     }
1931     #endif
1932     }
1933    
1934     JSBool
1935     js_InitPropertyTree(JSRuntime *rt)
1936     {
1937     if (!JS_DHashTableInit(&rt->propertyTreeHash, &PropertyTreeHashOps, NULL,
1938     sizeof(JSPropertyTreeEntry), JS_DHASH_MIN_SIZE)) {
1939     rt->propertyTreeHash.ops = NULL;
1940     return JS_FALSE;
1941     }
1942     JS_INIT_ARENA_POOL(&rt->propertyArenaPool, "properties",
1943     256 * sizeof(JSScopeProperty), sizeof(void *), NULL);
1944     return JS_TRUE;
1945     }
1946    
1947     void
1948     js_FinishPropertyTree(JSRuntime *rt)
1949     {
1950     if (rt->propertyTreeHash.ops) {
1951     JS_DHashTableFinish(&rt->propertyTreeHash);
1952     rt->propertyTreeHash.ops = NULL;
1953     }
1954     JS_FinishArenaPool(&rt->propertyArenaPool);
1955     }

  ViewVC Help
Powered by ViewVC 1.1.24