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

Annotation of /trunk/js/jsscope.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 507 - (hide annotations)
Sun Jan 10 07:23:34 2010 UTC (10 years, 8 months ago) by siliconforks
File size: 68667 byte(s)
Update SpiderMonkey from Firefox 3.6rc1.

1 siliconforks 507 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 siliconforks 332 * 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 siliconforks 507 #include <new>
45 siliconforks 332 #include <stdlib.h>
46     #include <string.h>
47     #include "jstypes.h"
48 siliconforks 507 #include "jsstdint.h"
49 siliconforks 332 #include "jsarena.h"
50     #include "jsbit.h"
51     #include "jsclist.h"
52     #include "jsdhash.h"
53     #include "jsutil.h" /* Added by JSIFY */
54     #include "jsapi.h"
55     #include "jsatom.h"
56     #include "jscntxt.h"
57     #include "jsdbgapi.h"
58     #include "jslock.h"
59     #include "jsnum.h"
60     #include "jsscope.h"
61     #include "jsstr.h"
62 siliconforks 507 #include "jstracer.h"
63 siliconforks 332
64 siliconforks 507 uint32
65     js_GenerateShape(JSContext *cx, bool gcLocked)
66     {
67     JSRuntime *rt;
68     uint32 shape;
69    
70     rt = cx->runtime;
71     shape = JS_ATOMIC_INCREMENT(&rt->shapeGen);
72     JS_ASSERT(shape != 0);
73     if (shape >= SHAPE_OVERFLOW_BIT) {
74     /*
75     * FIXME bug 440834: The shape id space has overflowed. Currently we
76     * cope badly with this and schedule the GC on the every call. But
77     * first we make sure that increments from other threads would not
78     * have a chance to wrap around shapeGen to zero.
79     */
80     rt->shapeGen = SHAPE_OVERFLOW_BIT;
81     shape = SHAPE_OVERFLOW_BIT;
82     js_TriggerGC(cx, gcLocked);
83     }
84     return shape;
85     }
86    
87 siliconforks 332 JSScope *
88     js_GetMutableScope(JSContext *cx, JSObject *obj)
89     {
90     JSScope *scope, *newscope;
91     JSClass *clasp;
92     uint32 freeslot;
93    
94     scope = OBJ_SCOPE(obj);
95     JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
96 siliconforks 507 if (scope->owned())
97 siliconforks 332 return scope;
98 siliconforks 460
99     /*
100     * Compile-time block objects each have their own scope, created at
101     * birth, and runtime clone of a block objects are never mutated.
102     */
103     JS_ASSERT(STOBJ_GET_CLASS(obj) != &js_BlockClass);
104 siliconforks 507 newscope = JSScope::create(cx, scope->ops, obj->getClass(), obj, scope->shape);
105 siliconforks 332 if (!newscope)
106     return NULL;
107     JS_LOCK_SCOPE(cx, newscope);
108 siliconforks 507 obj->map = newscope;
109 siliconforks 460
110     JS_ASSERT(newscope->freeslot == JSSLOT_FREE(STOBJ_GET_CLASS(obj)));
111 siliconforks 332 clasp = STOBJ_GET_CLASS(obj);
112     if (clasp->reserveSlots) {
113     freeslot = JSSLOT_FREE(clasp) + clasp->reserveSlots(cx, obj);
114     if (freeslot > STOBJ_NSLOTS(obj))
115     freeslot = STOBJ_NSLOTS(obj);
116 siliconforks 460 if (newscope->freeslot < freeslot)
117     newscope->freeslot = freeslot;
118 siliconforks 332 }
119     JS_TRANSFER_SCOPE_LOCK(cx, scope, newscope);
120 siliconforks 507 JS_ATOMIC_DECREMENT(&scope->nrefs);
121     if (scope->nrefs == 0)
122     JSScope::destroy(cx, scope);
123 siliconforks 332 return newscope;
124     }
125    
126     /*
127     * JSScope uses multiplicative hashing, _a la_ jsdhash.[ch], but specialized
128     * to minimize footprint. But if a scope has fewer than SCOPE_HASH_THRESHOLD
129     * entries, we use linear search and avoid allocating scope->table.
130     */
131     #define SCOPE_HASH_THRESHOLD 6
132     #define MIN_SCOPE_SIZE_LOG2 4
133     #define MIN_SCOPE_SIZE JS_BIT(MIN_SCOPE_SIZE_LOG2)
134     #define SCOPE_TABLE_NBYTES(n) ((n) * sizeof(JSScopeProperty *))
135    
136 siliconforks 507 void
137     JSScope::initMinimal(JSContext *cx, uint32 newShape)
138 siliconforks 332 {
139 siliconforks 507 shape = newShape;
140     emptyScope = NULL;
141     hashShift = JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2;
142     entryCount = removedCount = 0;
143     table = NULL;
144     lastProp = NULL;
145 siliconforks 332 }
146    
147 siliconforks 507 bool
148     JSScope::createTable(JSContext *cx, bool report)
149 siliconforks 332 {
150     int sizeLog2;
151     JSScopeProperty *sprop, **spp;
152    
153 siliconforks 507 JS_ASSERT(!table);
154     JS_ASSERT(lastProp);
155 siliconforks 332
156 siliconforks 507 if (entryCount > SCOPE_HASH_THRESHOLD) {
157 siliconforks 332 /*
158     * Either we're creating a table for a large scope that was populated
159     * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or
160     * JSOP_SETPROP; or else calloc failed at least once already. In any
161     * event, let's try to grow, overallocating to hold at least twice the
162     * current population.
163     */
164 siliconforks 507 sizeLog2 = JS_CeilingLog2(2 * entryCount);
165     hashShift = JS_DHASH_BITS - sizeLog2;
166 siliconforks 332 } else {
167 siliconforks 507 JS_ASSERT(hashShift == JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2);
168 siliconforks 332 sizeLog2 = MIN_SCOPE_SIZE_LOG2;
169     }
170    
171 siliconforks 507 table = (JSScopeProperty **) js_calloc(JS_BIT(sizeLog2) * sizeof(JSScopeProperty *));
172     if (!table) {
173 siliconforks 332 if (report)
174     JS_ReportOutOfMemory(cx);
175 siliconforks 507 return false;
176 siliconforks 332 }
177 siliconforks 507 cx->updateMallocCounter(JS_BIT(sizeLog2) * sizeof(JSScopeProperty *));
178 siliconforks 332
179 siliconforks 507 hashShift = JS_DHASH_BITS - sizeLog2;
180     for (sprop = lastProp; sprop; sprop = sprop->parent) {
181     spp = search(sprop->id, true);
182 siliconforks 332 SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
183     }
184 siliconforks 507 return true;
185 siliconforks 332 }
186    
187     JSScope *
188 siliconforks 507 JSScope::create(JSContext *cx, const JSObjectOps *ops, JSClass *clasp,
189     JSObject *obj, uint32 shape)
190 siliconforks 332 {
191 siliconforks 460 JS_ASSERT(OPS_IS_NATIVE(ops));
192     JS_ASSERT(obj);
193 siliconforks 332
194 siliconforks 507 JSScope *scope = cx->create<JSScope>(ops, obj);
195 siliconforks 332 if (!scope)
196     return NULL;
197    
198 siliconforks 460 scope->nrefs = 1;
199     scope->freeslot = JSSLOT_FREE(clasp);
200 siliconforks 507 scope->flags = cx->runtime->gcRegenShapesScopeFlag;
201     js_LeaveTraceIfGlobalObject(cx, obj);
202     scope->initMinimal(cx, shape);
203 siliconforks 332
204     #ifdef JS_THREADSAFE
205     js_InitTitle(cx, &scope->title);
206     #endif
207     JS_RUNTIME_METER(cx->runtime, liveScopes);
208     JS_RUNTIME_METER(cx->runtime, totalScopes);
209     return scope;
210     }
211    
212 siliconforks 507 JSEmptyScope *
213     JSScope::createEmptyScope(JSContext *cx, JSClass *clasp)
214     {
215     JS_ASSERT(!emptyScope);
216    
217     JSEmptyScope *scope = cx->create<JSEmptyScope>(ops, clasp);
218     if (!scope)
219     return NULL;
220    
221     /*
222     * This scope holds a reference to the new empty scope. Our only caller,
223     * getEmptyScope, also promises to incref on behalf of its caller.
224     */
225     scope->nrefs = 2;
226     scope->freeslot = JSSLOT_FREE(clasp);
227     scope->flags = OWN_SHAPE | cx->runtime->gcRegenShapesScopeFlag;
228     scope->initMinimal(cx, js_GenerateShape(cx, false));
229    
230     #ifdef JS_THREADSAFE
231     js_InitTitle(cx, &scope->title);
232     #endif
233     JS_RUNTIME_METER(cx->runtime, liveScopes);
234     JS_RUNTIME_METER(cx->runtime, totalScopes);
235     emptyScope = scope;
236     return scope;
237     }
238    
239 siliconforks 332 #if defined DEBUG || defined JS_DUMP_PROPTREE_STATS
240     # include "jsprf.h"
241     # define LIVE_SCOPE_METER(cx,expr) JS_LOCK_RUNTIME_VOID(cx->runtime,expr)
242     #else
243     # define LIVE_SCOPE_METER(cx,expr) /* nothing */
244     #endif
245    
246     void
247 siliconforks 507 JSScope::destroy(JSContext *cx, JSScope *scope)
248 siliconforks 332 {
249     #ifdef JS_THREADSAFE
250     js_FinishTitle(cx, &scope->title);
251     #endif
252     if (scope->table)
253 siliconforks 507 cx->free(scope->table);
254     if (scope->emptyScope)
255     scope->emptyScope->drop(cx, NULL);
256 siliconforks 332
257     LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= scope->entryCount);
258     JS_RUNTIME_UNMETER(cx->runtime, liveScopes);
259 siliconforks 507 cx->free(scope);
260 siliconforks 332 }
261    
262     #ifdef JS_DUMP_PROPTREE_STATS
263     typedef struct JSScopeStats {
264     jsrefcount searches;
265     jsrefcount hits;
266     jsrefcount misses;
267     jsrefcount hashes;
268     jsrefcount steps;
269     jsrefcount stepHits;
270     jsrefcount stepMisses;
271     jsrefcount adds;
272     jsrefcount redundantAdds;
273     jsrefcount addFailures;
274     jsrefcount changeFailures;
275     jsrefcount compresses;
276     jsrefcount grows;
277     jsrefcount removes;
278     jsrefcount removeFrees;
279     jsrefcount uselessRemoves;
280     jsrefcount shrinks;
281     } JSScopeStats;
282    
283     JS_FRIEND_DATA(JSScopeStats) js_scope_stats = {0};
284    
285     # define METER(x) JS_ATOMIC_INCREMENT(&js_scope_stats.x)
286     #else
287     # define METER(x) /* nothing */
288     #endif
289    
290     JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4);
291     JS_STATIC_ASSERT(sizeof(jsid) == JS_BYTES_PER_WORD);
292    
293     #if JS_BYTES_PER_WORD == 4
294     # define HASH_ID(id) ((JSHashNumber)(id))
295     #elif JS_BYTES_PER_WORD == 8
296     # define HASH_ID(id) ((JSHashNumber)(id) ^ (JSHashNumber)((id) >> 32))
297     #else
298     # error "Unsupported configuration"
299     #endif
300    
301     /*
302     * Double hashing needs the second hash code to be relatively prime to table
303     * size, so we simply make hash2 odd. The inputs to multiplicative hash are
304     * the golden ratio, expressed as a fixed-point 32 bit fraction, and the id
305     * itself.
306     */
307     #define SCOPE_HASH0(id) (HASH_ID(id) * JS_GOLDEN_RATIO)
308     #define SCOPE_HASH1(hash0,shift) ((hash0) >> (shift))
309     #define SCOPE_HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
310    
311 siliconforks 507 JSScopeProperty **
312     JSScope::searchTable(jsid id, bool adding)
313 siliconforks 332 {
314     JSHashNumber hash0, hash1, hash2;
315 siliconforks 507 int sizeLog2;
316 siliconforks 332 JSScopeProperty *stored, *sprop, **spp, **firstRemoved;
317     uint32 sizeMask;
318    
319 siliconforks 507 JS_ASSERT(table);
320 siliconforks 332
321     /* Compute the primary hash address. */
322     METER(hashes);
323     hash0 = SCOPE_HASH0(id);
324     hash1 = SCOPE_HASH1(hash0, hashShift);
325 siliconforks 507 spp = table + hash1;
326 siliconforks 332
327     /* Miss: return space for a new entry. */
328     stored = *spp;
329     if (SPROP_IS_FREE(stored)) {
330     METER(misses);
331     return spp;
332     }
333    
334     /* Hit: return entry. */
335     sprop = SPROP_CLEAR_COLLISION(stored);
336     if (sprop && sprop->id == id) {
337     METER(hits);
338     return spp;
339     }
340    
341     /* Collision: double hash. */
342     sizeLog2 = JS_DHASH_BITS - hashShift;
343     hash2 = SCOPE_HASH2(hash0, sizeLog2, hashShift);
344     sizeMask = JS_BITMASK(sizeLog2);
345    
346     /* Save the first removed entry pointer so we can recycle it if adding. */
347     if (SPROP_IS_REMOVED(stored)) {
348     firstRemoved = spp;
349     } else {
350     firstRemoved = NULL;
351     if (adding && !SPROP_HAD_COLLISION(stored))
352     SPROP_FLAG_COLLISION(spp, sprop);
353     }
354    
355     for (;;) {
356     METER(steps);
357     hash1 -= hash2;
358     hash1 &= sizeMask;
359 siliconforks 507 spp = table + hash1;
360 siliconforks 332
361     stored = *spp;
362     if (SPROP_IS_FREE(stored)) {
363     METER(stepMisses);
364     return (adding && firstRemoved) ? firstRemoved : spp;
365     }
366    
367     sprop = SPROP_CLEAR_COLLISION(stored);
368     if (sprop && sprop->id == id) {
369     METER(stepHits);
370     return spp;
371     }
372    
373     if (SPROP_IS_REMOVED(stored)) {
374     if (!firstRemoved)
375     firstRemoved = spp;
376     } else {
377     if (adding && !SPROP_HAD_COLLISION(stored))
378     SPROP_FLAG_COLLISION(spp, sprop);
379     }
380     }
381    
382     /* NOTREACHED */
383     return NULL;
384     }
385    
386 siliconforks 507 bool
387     JSScope::changeTable(JSContext *cx, int change)
388 siliconforks 332 {
389     int oldlog2, newlog2;
390     uint32 oldsize, newsize, nbytes;
391 siliconforks 507 JSScopeProperty **newtable, **oldtable, **spp, **oldspp, *sprop;
392 siliconforks 332
393 siliconforks 507 if (!table)
394     return createTable(cx, true);
395 siliconforks 332
396 siliconforks 507 /* Grow, shrink, or compress by changing this->table. */
397     oldlog2 = JS_DHASH_BITS - hashShift;
398 siliconforks 332 newlog2 = oldlog2 + change;
399     oldsize = JS_BIT(oldlog2);
400     newsize = JS_BIT(newlog2);
401     nbytes = SCOPE_TABLE_NBYTES(newsize);
402 siliconforks 507 newtable = (JSScopeProperty **) cx->calloc(nbytes);
403     if (!newtable)
404     return false;
405 siliconforks 332
406 siliconforks 507 /* Now that we have newtable allocated, update members. */
407     hashShift = JS_DHASH_BITS - newlog2;
408     removedCount = 0;
409     oldtable = table;
410     table = newtable;
411 siliconforks 332
412     /* Treat the above calloc as a JS_malloc, to match CreateScopeTable. */
413     cx->runtime->gcMallocBytes += nbytes;
414    
415     /* Copy only live entries, leaving removed and free ones behind. */
416     for (oldspp = oldtable; oldsize != 0; oldspp++) {
417     sprop = SPROP_FETCH(oldspp);
418     if (sprop) {
419 siliconforks 507 spp = search(sprop->id, true);
420 siliconforks 332 JS_ASSERT(SPROP_IS_FREE(*spp));
421     *spp = sprop;
422     }
423     oldsize--;
424     }
425    
426     /* Finally, free the old table storage. */
427 siliconforks 507 cx->free(oldtable);
428     return true;
429 siliconforks 332 }
430    
431     /*
432     * Take care to exclude the mark bits in case we're called from the GC.
433     */
434     #define SPROP_FLAGS_NOT_MATCHED (SPROP_MARK | SPROP_FLAG_SHAPE_REGEN)
435    
436     static JSDHashNumber
437     js_HashScopeProperty(JSDHashTable *table, const void *key)
438     {
439     const JSScopeProperty *sprop = (const JSScopeProperty *)key;
440     JSDHashNumber hash;
441     JSPropertyOp gsop;
442    
443     /* Accumulate from least to most random so the low bits are most random. */
444     hash = 0;
445     gsop = sprop->getter;
446     if (gsop)
447     hash = JS_ROTATE_LEFT32(hash, 4) ^ (jsword)gsop;
448     gsop = sprop->setter;
449     if (gsop)
450     hash = JS_ROTATE_LEFT32(hash, 4) ^ (jsword)gsop;
451    
452     hash = JS_ROTATE_LEFT32(hash, 4)
453     ^ (sprop->flags & ~SPROP_FLAGS_NOT_MATCHED);
454    
455     hash = JS_ROTATE_LEFT32(hash, 4) ^ sprop->attrs;
456     hash = JS_ROTATE_LEFT32(hash, 4) ^ sprop->shortid;
457     hash = JS_ROTATE_LEFT32(hash, 4) ^ sprop->slot;
458     hash = JS_ROTATE_LEFT32(hash, 4) ^ sprop->id;
459     return hash;
460     }
461    
462     #define SPROP_MATCH(sprop, child) \
463     SPROP_MATCH_PARAMS(sprop, (child)->id, (child)->getter, (child)->setter, \
464     (child)->slot, (child)->attrs, (child)->flags, \
465     (child)->shortid)
466    
467     #define SPROP_MATCH_PARAMS(sprop, aid, agetter, asetter, aslot, aattrs, \
468     aflags, ashortid) \
469     ((sprop)->id == (aid) && \
470     SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
471     aflags, ashortid))
472    
473     #define SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
474     aflags, ashortid) \
475     ((sprop)->getter == (agetter) && \
476     (sprop)->setter == (asetter) && \
477     (sprop)->slot == (aslot) && \
478     (sprop)->attrs == (aattrs) && \
479     (((sprop)->flags ^ (aflags)) & ~SPROP_FLAGS_NOT_MATCHED) == 0 && \
480     (sprop)->shortid == (ashortid))
481    
482     static JSBool
483     js_MatchScopeProperty(JSDHashTable *table,
484     const JSDHashEntryHdr *hdr,
485     const void *key)
486     {
487     const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr;
488     const JSScopeProperty *sprop = entry->child;
489     const JSScopeProperty *kprop = (const JSScopeProperty *)key;
490    
491     return SPROP_MATCH(sprop, kprop);
492     }
493    
494     static const JSDHashTableOps PropertyTreeHashOps = {
495     JS_DHashAllocTable,
496     JS_DHashFreeTable,
497     js_HashScopeProperty,
498     js_MatchScopeProperty,
499     JS_DHashMoveEntryStub,
500     JS_DHashClearEntryStub,
501     JS_DHashFinalizeStub,
502     NULL
503     };
504    
505     /*
506     * A property tree node on rt->propertyFreeList overlays the following prefix
507     * struct on JSScopeProperty.
508     */
509     typedef struct FreeNode {
510     jsid id;
511     JSScopeProperty *next;
512     JSScopeProperty **prevp;
513     } FreeNode;
514    
515     #define FREENODE(sprop) ((FreeNode *) (sprop))
516    
517     #define FREENODE_INSERT(list, sprop) \
518     JS_BEGIN_MACRO \
519     FREENODE(sprop)->next = (list); \
520     FREENODE(sprop)->prevp = &(list); \
521     if (list) \
522     FREENODE(list)->prevp = &FREENODE(sprop)->next; \
523     (list) = (sprop); \
524     JS_END_MACRO
525    
526     #define FREENODE_REMOVE(sprop) \
527     JS_BEGIN_MACRO \
528     *FREENODE(sprop)->prevp = FREENODE(sprop)->next; \
529     if (FREENODE(sprop)->next) \
530     FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp; \
531     JS_END_MACRO
532    
533     /* NB: Called with rt->gcLock held. */
534     static JSScopeProperty *
535     NewScopeProperty(JSRuntime *rt)
536     {
537     JSScopeProperty *sprop;
538    
539     sprop = rt->propertyFreeList;
540     if (sprop) {
541     FREENODE_REMOVE(sprop);
542     } else {
543     JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *,
544     &rt->propertyArenaPool,
545     sizeof(JSScopeProperty));
546     if (!sprop)
547     return NULL;
548     }
549    
550     JS_RUNTIME_METER(rt, livePropTreeNodes);
551     JS_RUNTIME_METER(rt, totalPropTreeNodes);
552     return sprop;
553     }
554    
555     #define CHUNKY_KIDS_TAG ((jsuword)1)
556     #define KIDS_IS_CHUNKY(kids) ((jsuword)(kids) & CHUNKY_KIDS_TAG)
557     #define KIDS_TO_CHUNK(kids) ((PropTreeKidsChunk *) \
558     ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
559     #define CHUNK_TO_KIDS(chunk) ((JSScopeProperty *) \
560     ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
561     #define MAX_KIDS_PER_CHUNK 10
562     #define CHUNK_HASH_THRESHOLD 30
563    
564     typedef struct PropTreeKidsChunk PropTreeKidsChunk;
565    
566     struct PropTreeKidsChunk {
567     JSScopeProperty *kids[MAX_KIDS_PER_CHUNK];
568     JSDHashTable *table;
569     PropTreeKidsChunk *next;
570     };
571    
572     static PropTreeKidsChunk *
573     NewPropTreeKidsChunk(JSRuntime *rt)
574     {
575     PropTreeKidsChunk *chunk;
576    
577 siliconforks 507 chunk = (PropTreeKidsChunk *) js_calloc(sizeof *chunk);
578 siliconforks 332 if (!chunk)
579     return NULL;
580     JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0);
581     JS_RUNTIME_METER(rt, propTreeKidsChunks);
582     return chunk;
583     }
584    
585     static void
586     DestroyPropTreeKidsChunk(JSRuntime *rt, PropTreeKidsChunk *chunk)
587     {
588     JS_RUNTIME_UNMETER(rt, propTreeKidsChunks);
589     if (chunk->table)
590     JS_DHashTableDestroy(chunk->table);
591 siliconforks 507 js_free(chunk);
592 siliconforks 332 }
593    
594     /* NB: Called with rt->gcLock held. */
595 siliconforks 507 static bool
596 siliconforks 332 InsertPropertyTreeChild(JSRuntime *rt, JSScopeProperty *parent,
597     JSScopeProperty *child, PropTreeKidsChunk *sweptChunk)
598     {
599     JSDHashTable *table;
600     JSPropertyTreeEntry *entry;
601     JSScopeProperty **childp, *kids, *sprop;
602     PropTreeKidsChunk *chunk, **chunkp;
603     uintN i;
604    
605     JS_ASSERT(!parent || child->parent != parent);
606    
607     if (!parent) {
608     table = &rt->propertyTreeHash;
609     entry = (JSPropertyTreeEntry *)
610     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
611     if (!entry)
612 siliconforks 507 return false;
613 siliconforks 332 childp = &entry->child;
614     sprop = *childp;
615     if (!sprop) {
616     *childp = child;
617     } else {
618     /*
619     * A "Duplicate child" case.
620     *
621     * We can't do away with child, as at least one live scope entry
622     * still points at it. What's more, that scope's lastProp chains
623     * through an ancestor line to reach child, and js_Enumerate and
624     * others count on this linkage. We must leave child out of the
625     * hash table, and not require it to be there when we eventually
626     * GC it (see RemovePropertyTreeChild, below).
627     *
628     * It is necessary to leave the duplicate child out of the hash
629     * table to preserve entry uniqueness. It is safe to leave the
630     * child out of the hash table (unlike the duplicate child cases
631     * below), because the child's parent link will be null, which
632     * can't dangle.
633     */
634     JS_ASSERT(sprop != child && SPROP_MATCH(sprop, child));
635     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
636     }
637     } else {
638     childp = &parent->kids;
639     kids = *childp;
640     if (kids) {
641     if (KIDS_IS_CHUNKY(kids)) {
642     chunk = KIDS_TO_CHUNK(kids);
643    
644     table = chunk->table;
645     if (table) {
646     entry = (JSPropertyTreeEntry *)
647     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
648     if (!entry)
649 siliconforks 507 return false;
650 siliconforks 332 if (!entry->child) {
651     entry->child = child;
652     while (chunk->next)
653     chunk = chunk->next;
654     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
655     childp = &chunk->kids[i];
656     sprop = *childp;
657     if (!sprop)
658     goto insert;
659     }
660     chunkp = &chunk->next;
661     goto new_chunk;
662     }
663     }
664    
665     do {
666     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
667     childp = &chunk->kids[i];
668     sprop = *childp;
669     if (!sprop)
670     goto insert;
671    
672     JS_ASSERT(sprop != child);
673     if (SPROP_MATCH(sprop, child)) {
674     /*
675     * Duplicate child, see comment above. In this
676     * case, we must let the duplicate be inserted at
677     * this level in the tree, so we keep iterating,
678     * looking for an empty slot in which to insert.
679     */
680     JS_ASSERT(sprop != child);
681     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
682     }
683     }
684     chunkp = &chunk->next;
685     } while ((chunk = *chunkp) != NULL);
686    
687     new_chunk:
688     if (sweptChunk) {
689     chunk = sweptChunk;
690     } else {
691     chunk = NewPropTreeKidsChunk(rt);
692     if (!chunk)
693 siliconforks 507 return false;
694 siliconforks 332 }
695     *chunkp = chunk;
696     childp = &chunk->kids[0];
697     } else {
698     sprop = kids;
699     JS_ASSERT(sprop != child);
700     if (SPROP_MATCH(sprop, child)) {
701     /*
702     * Duplicate child, see comment above. Once again, we
703     * must let duplicates created by deletion pile up in a
704     * kids-chunk-list, in order to find them when sweeping
705     * and thereby avoid dangling parent pointers.
706     */
707     JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
708     }
709     if (sweptChunk) {
710     chunk = sweptChunk;
711     } else {
712     chunk = NewPropTreeKidsChunk(rt);
713     if (!chunk)
714 siliconforks 507 return false;
715 siliconforks 332 }
716     parent->kids = CHUNK_TO_KIDS(chunk);
717     chunk->kids[0] = sprop;
718     childp = &chunk->kids[1];
719     }
720     }
721     insert:
722     *childp = child;
723     }
724    
725     child->parent = parent;
726 siliconforks 507 return true;
727 siliconforks 332 }
728    
729     /* NB: Called with rt->gcLock held. */
730     static PropTreeKidsChunk *
731     RemovePropertyTreeChild(JSRuntime *rt, JSScopeProperty *child)
732     {
733     PropTreeKidsChunk *freeChunk;
734     JSScopeProperty *parent, *kids, *kid;
735     JSDHashTable *table;
736     PropTreeKidsChunk *list, *chunk, **chunkp, *lastChunk;
737     uintN i, j;
738     JSPropertyTreeEntry *entry;
739    
740     freeChunk = NULL;
741     parent = child->parent;
742     if (!parent) {
743     /*
744     * Don't remove child if it is not in rt->propertyTreeHash, but only
745     * matches a root child in the table that has compatible members. See
746     * the "Duplicate child" comments in InsertPropertyTreeChild, above.
747     */
748     table = &rt->propertyTreeHash;
749     } else {
750     kids = parent->kids;
751     if (KIDS_IS_CHUNKY(kids)) {
752     list = chunk = KIDS_TO_CHUNK(kids);
753     chunkp = &list;
754     table = chunk->table;
755    
756     do {
757     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
758     if (chunk->kids[i] == child) {
759     lastChunk = chunk;
760     if (!lastChunk->next) {
761     j = i + 1;
762     } else {
763     j = 0;
764     do {
765     chunkp = &lastChunk->next;
766     lastChunk = *chunkp;
767     } while (lastChunk->next);
768     }
769     for (; j < MAX_KIDS_PER_CHUNK; j++) {
770     if (!lastChunk->kids[j])
771     break;
772     }
773     --j;
774     if (chunk != lastChunk || j > i)
775     chunk->kids[i] = lastChunk->kids[j];
776     lastChunk->kids[j] = NULL;
777     if (j == 0) {
778     *chunkp = NULL;
779     if (!list)
780     parent->kids = NULL;
781     freeChunk = lastChunk;
782     }
783     goto out;
784     }
785     }
786    
787     chunkp = &chunk->next;
788     } while ((chunk = *chunkp) != NULL);
789     } else {
790     table = NULL;
791     kid = kids;
792     if (kid == child)
793     parent->kids = NULL;
794     }
795     }
796    
797     out:
798     if (table) {
799     entry = (JSPropertyTreeEntry *)
800     JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
801    
802     if (entry->child == child)
803     JS_DHashTableRawRemove(table, &entry->hdr);
804     }
805     return freeChunk;
806     }
807    
808     static JSDHashTable *
809     HashChunks(PropTreeKidsChunk *chunk, uintN n)
810     {
811     JSDHashTable *table;
812     uintN i;
813     JSScopeProperty *sprop;
814     JSPropertyTreeEntry *entry;
815    
816     table = JS_NewDHashTable(&PropertyTreeHashOps, NULL,
817     sizeof(JSPropertyTreeEntry),
818     JS_DHASH_DEFAULT_CAPACITY(n + 1));
819     if (!table)
820     return NULL;
821     do {
822     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
823     sprop = chunk->kids[i];
824     if (!sprop)
825     break;
826     entry = (JSPropertyTreeEntry *)
827     JS_DHashTableOperate(table, sprop, JS_DHASH_ADD);
828     entry->child = sprop;
829     }
830     } while ((chunk = chunk->next) != NULL);
831     return table;
832     }
833    
834     /*
835     * Called without cx->runtime->gcLock held. This function acquires that lock
836     * only when inserting a new child. Thus there may be races to find or add a
837     * node that result in duplicates. We expect such races to be rare!
838     *
839 siliconforks 460 * We use rt->gcLock, not rt->rtLock, to avoid nesting the former inside the
840     * latter in js_GenerateShape below.
841 siliconforks 332 */
842     static JSScopeProperty *
843     GetPropertyTreeChild(JSContext *cx, JSScopeProperty *parent,
844     JSScopeProperty *child)
845     {
846     JSRuntime *rt;
847     JSDHashTable *table;
848     JSPropertyTreeEntry *entry;
849     JSScopeProperty *sprop;
850     PropTreeKidsChunk *chunk;
851     uintN i, n;
852    
853     rt = cx->runtime;
854     if (!parent) {
855     JS_LOCK_GC(rt);
856    
857     table = &rt->propertyTreeHash;
858     entry = (JSPropertyTreeEntry *)
859     JS_DHashTableOperate(table, child, JS_DHASH_ADD);
860     if (!entry)
861     goto out_of_memory;
862    
863     sprop = entry->child;
864     if (sprop)
865     goto out;
866     } else {
867     /*
868     * Because chunks are appended at the end and never deleted except by
869     * the GC, we can search without taking the runtime's GC lock. We may
870     * miss a matching sprop added by another thread, and make a duplicate
871     * one, but that is an unlikely, therefore small, cost. The property
872     * tree has extremely low fan-out below its root in popular embeddings
873     * with real-world workloads.
874     *
875     * Patterns such as defining closures that capture a constructor's
876     * environment as getters or setters on the new object that is passed
877     * in as |this| can significantly increase fan-out below the property
878     * tree root -- see bug 335700 for details.
879     */
880     entry = NULL;
881     sprop = parent->kids;
882     if (sprop) {
883     if (KIDS_IS_CHUNKY(sprop)) {
884     chunk = KIDS_TO_CHUNK(sprop);
885    
886     table = chunk->table;
887     if (table) {
888     JS_LOCK_GC(rt);
889     entry = (JSPropertyTreeEntry *)
890     JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
891     sprop = entry->child;
892     if (sprop) {
893     JS_UNLOCK_GC(rt);
894     return sprop;
895     }
896     goto locked_not_found;
897     }
898    
899     n = 0;
900     do {
901     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
902     sprop = chunk->kids[i];
903     if (!sprop) {
904     n += i;
905     if (n >= CHUNK_HASH_THRESHOLD) {
906     chunk = KIDS_TO_CHUNK(parent->kids);
907     if (!chunk->table) {
908     table = HashChunks(chunk, n);
909     JS_LOCK_GC(rt);
910     if (!table)
911     goto out_of_memory;
912     if (chunk->table)
913     JS_DHashTableDestroy(table);
914     else
915     chunk->table = table;
916     goto locked_not_found;
917     }
918     }
919     goto not_found;
920     }
921    
922     if (SPROP_MATCH(sprop, child))
923     return sprop;
924     }
925     n += MAX_KIDS_PER_CHUNK;
926     } while ((chunk = chunk->next) != NULL);
927     } else {
928     if (SPROP_MATCH(sprop, child))
929     return sprop;
930     }
931     }
932    
933     not_found:
934     JS_LOCK_GC(rt);
935     }
936    
937     locked_not_found:
938     sprop = NewScopeProperty(rt);
939     if (!sprop)
940     goto out_of_memory;
941    
942     sprop->id = child->id;
943     sprop->getter = child->getter;
944     sprop->setter = child->setter;
945     sprop->slot = child->slot;
946     sprop->attrs = child->attrs;
947     sprop->flags = child->flags;
948     sprop->shortid = child->shortid;
949     sprop->parent = sprop->kids = NULL;
950 siliconforks 507 sprop->shape = js_GenerateShape(cx, true);
951 siliconforks 332
952     if (!parent) {
953     entry->child = sprop;
954     } else {
955     if (!InsertPropertyTreeChild(rt, parent, sprop, NULL))
956     goto out_of_memory;
957     }
958    
959     out:
960     JS_UNLOCK_GC(rt);
961     return sprop;
962    
963     out_of_memory:
964     JS_UNLOCK_GC(rt);
965     JS_ReportOutOfMemory(cx);
966     return NULL;
967     }
968    
969     #ifdef DEBUG_notbrendan
970     #define CHECK_ANCESTOR_LINE(scope, sparse) \
971     JS_BEGIN_MACRO \
972     if ((scope)->table) CheckAncestorLine(scope, sparse); \
973     JS_END_MACRO
974    
975     static void
976 siliconforks 507 CheckAncestorLine(JSScope *scope, bool sparse)
977 siliconforks 332 {
978     uint32 size;
979     JSScopeProperty **spp, **start, **end, *ancestorLine, *sprop, *aprop;
980     uint32 entryCount, ancestorCount;
981    
982     ancestorLine = SCOPE_LAST_PROP(scope);
983     if (ancestorLine)
984 siliconforks 507 JS_ASSERT(scope->has(ancestorLine));
985 siliconforks 332
986     entryCount = 0;
987     size = SCOPE_CAPACITY(scope);
988     start = scope->table;
989     for (spp = start, end = start + size; spp < end; spp++) {
990     sprop = SPROP_FETCH(spp);
991     if (sprop) {
992     entryCount++;
993     for (aprop = ancestorLine; aprop; aprop = aprop->parent) {
994     if (aprop == sprop)
995     break;
996     }
997     JS_ASSERT(aprop);
998     }
999     }
1000     JS_ASSERT(entryCount == scope->entryCount);
1001    
1002     ancestorCount = 0;
1003     for (sprop = ancestorLine; sprop; sprop = sprop->parent) {
1004 siliconforks 507 if (scope->hadMiddleDelete() && !scope->has(sprop)) {
1005 siliconforks 332 JS_ASSERT(sparse);
1006     continue;
1007     }
1008     ancestorCount++;
1009     }
1010     JS_ASSERT(ancestorCount == scope->entryCount);
1011     }
1012     #else
1013     #define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
1014     #endif
1015    
1016 siliconforks 507 void
1017     JSScope::reportReadOnlyScope(JSContext *cx)
1018 siliconforks 332 {
1019     JSString *str;
1020     const char *bytes;
1021    
1022 siliconforks 507 str = js_ValueToString(cx, OBJECT_TO_JSVAL(object));
1023 siliconforks 332 if (!str)
1024     return;
1025     bytes = js_GetStringBytes(cx, str);
1026     if (!bytes)
1027     return;
1028     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_READ_ONLY, bytes);
1029     }
1030    
1031 siliconforks 507 void
1032     JSScope::generateOwnShape(JSContext *cx)
1033     {
1034     if (object)
1035     js_LeaveTraceIfGlobalObject(cx, object);
1036    
1037     shape = js_GenerateShape(cx, false);
1038     setOwnShape();
1039     }
1040    
1041 siliconforks 332 JSScopeProperty *
1042 siliconforks 507 JSScope::add(JSContext *cx, jsid id,
1043     JSPropertyOp getter, JSPropertyOp setter,
1044     uint32 slot, uintN attrs,
1045     uintN flags, intN shortid)
1046 siliconforks 332 {
1047     JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child;
1048     uint32 size, splen, i;
1049     int change;
1050     JSTempValueRooter tvr;
1051    
1052 siliconforks 507 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, this));
1053     CHECK_ANCESTOR_LINE(this, true);
1054 siliconforks 332
1055 siliconforks 507 JS_ASSERT(!JSVAL_IS_NULL(id));
1056     JS_ASSERT_IF(!cx->runtime->gcRegenShapes,
1057     hasRegenFlag(cx->runtime->gcRegenShapesScopeFlag));
1058    
1059 siliconforks 332 /*
1060     * You can't add properties to a sealed scope. But note well that you can
1061     * change property attributes in a sealed scope, even though that replaces
1062     * a JSScopeProperty * in the scope's hash table -- but no id is added, so
1063     * the scope remains sealed.
1064     */
1065 siliconforks 507 if (sealed()) {
1066     reportReadOnlyScope(cx);
1067 siliconforks 332 return NULL;
1068     }
1069    
1070     /*
1071     * Normalize stub getter and setter values for faster is-stub testing in
1072     * the SPROP_CALL_[GS]ETTER macros.
1073     */
1074     if (getter == JS_PropertyStub)
1075     getter = NULL;
1076     if (setter == JS_PropertyStub)
1077     setter = NULL;
1078    
1079     /*
1080     * Search for id in order to claim its entry, allocating a property tree
1081     * node if one doesn't already exist for our parameters.
1082     */
1083 siliconforks 507 spp = search(id, true);
1084 siliconforks 332 sprop = overwriting = SPROP_FETCH(spp);
1085     if (!sprop) {
1086     /* Check whether we need to grow, if the load factor is >= .75. */
1087 siliconforks 507 size = SCOPE_CAPACITY(this);
1088     if (entryCount + removedCount >= size - (size >> 2)) {
1089     if (removedCount >= size >> 2) {
1090 siliconforks 332 METER(compresses);
1091     change = 0;
1092     } else {
1093     METER(grows);
1094     change = 1;
1095     }
1096 siliconforks 507 if (!changeTable(cx, change) &&
1097     entryCount + removedCount == size - 1) {
1098 siliconforks 332 METER(addFailures);
1099     return NULL;
1100     }
1101 siliconforks 507 spp = search(id, true);
1102 siliconforks 332 JS_ASSERT(!SPROP_FETCH(spp));
1103     }
1104     } else {
1105 siliconforks 507 /* Property exists: JSScope::search must have returned a valid *spp. */
1106 siliconforks 332 JS_ASSERT(!SPROP_IS_REMOVED(*spp));
1107    
1108     /*
1109     * If all property members match, this is a redundant add and we can
1110     * return early. If the caller wants to allocate a slot, but doesn't
1111     * care which slot, copy sprop->slot into slot so we can match sprop,
1112     * if all other members match.
1113     */
1114     if (!(attrs & JSPROP_SHARED) &&
1115     slot == SPROP_INVALID_SLOT &&
1116 siliconforks 507 SPROP_HAS_VALID_SLOT(sprop, this)) {
1117 siliconforks 332 slot = sprop->slot;
1118     }
1119     if (SPROP_MATCH_PARAMS_AFTER_ID(sprop, getter, setter, slot, attrs,
1120     flags, shortid)) {
1121     METER(redundantAdds);
1122     return sprop;
1123     }
1124    
1125     /*
1126 siliconforks 460 * If we are clearing sprop to force the existing property that it
1127     * describes to be overwritten, then we have to unlink sprop from the
1128 siliconforks 507 * ancestor line at this->lastProp, lazily if sprop is not lastProp.
1129 siliconforks 460 * And we must remove the entry at *spp, precisely so the lazy "middle
1130 siliconforks 507 * delete" fixup code further below won't find sprop in this->table,
1131 siliconforks 460 * in spite of sprop being on the ancestor line.
1132 siliconforks 332 *
1133     * When we finally succeed in finding or creating a new sprop
1134     * and storing its pointer at *spp, we'll use the |overwriting|
1135     * local saved when we first looked up id to decide whether we're
1136     * indeed creating a new entry, or merely overwriting an existing
1137     * property.
1138     */
1139 siliconforks 507 if (sprop == SCOPE_LAST_PROP(this)) {
1140 siliconforks 332 do {
1141 siliconforks 507 SCOPE_REMOVE_LAST_PROP(this);
1142     if (!hadMiddleDelete())
1143 siliconforks 332 break;
1144 siliconforks 507 sprop = SCOPE_LAST_PROP(this);
1145     } while (sprop && !has(sprop));
1146     } else if (!hadMiddleDelete()) {
1147 siliconforks 332 /*
1148     * If we have no hash table yet, we need one now. The middle
1149     * delete code is simple-minded that way!
1150     */
1151 siliconforks 507 if (!table) {
1152     if (!createTable(cx, true))
1153 siliconforks 332 return NULL;
1154 siliconforks 507 spp = search(id, true);
1155 siliconforks 332 sprop = overwriting = SPROP_FETCH(spp);
1156     }
1157 siliconforks 507 setMiddleDelete();
1158 siliconforks 332 }
1159    
1160     /*
1161     * If we fail later on trying to find or create a new sprop, we will
1162     * goto fail_overwrite and restore *spp from |overwriting|. Note that
1163 siliconforks 507 * we don't bother to keep this->removedCount in sync, because we'll
1164     * fix up *spp and this->entryCount shortly, no matter how control
1165 siliconforks 332 * flow returns from this function.
1166     */
1167 siliconforks 507 if (table)
1168 siliconforks 332 SPROP_STORE_PRESERVING_COLLISION(spp, NULL);
1169 siliconforks 507 entryCount--;
1170     CHECK_ANCESTOR_LINE(this, true);
1171 siliconforks 332 sprop = NULL;
1172     }
1173    
1174     if (!sprop) {
1175     /*
1176     * If properties were deleted from the middle of the list starting at
1177 siliconforks 507 * this->lastProp, we may need to fork the property tree and squeeze
1178     * all deleted properties out of this scope's ancestor line. Otherwise
1179     * we risk adding a node with the same id as a "middle" node, violating
1180 siliconforks 332 * the rule that properties along an ancestor line have distinct ids.
1181     */
1182 siliconforks 507 if (hadMiddleDelete()) {
1183     JS_ASSERT(table);
1184     CHECK_ANCESTOR_LINE(this, true);
1185 siliconforks 332
1186 siliconforks 460 /*
1187     * Our forking heuristic tries to balance the desire to avoid
1188     * over-compacting (over-forking) against the desire to
1189     * *periodically* fork anyways, in order to prevent paying scan
1190     * penalties on each insert indefinitely, on a lineage with only
1191     * a few old middle-deletions. So we fork if either:
1192     *
1193     * - A quick scan finds a true conflict.
1194     * - We are passing through a doubling-threshold in size and
1195     * have accumulated a nonzero count of uncompacted deletions.
1196     */
1197    
1198     bool conflicts = false;
1199     uint32 count = 0;
1200 siliconforks 507 uint32 threshold = JS_BIT(JS_CeilingLog2(entryCount));
1201     for (sprop = SCOPE_LAST_PROP(this); sprop; sprop = sprop->parent) {
1202 siliconforks 460 ++count;
1203     if (sprop->id == id) {
1204     conflicts = true;
1205     break;
1206     }
1207     }
1208    
1209     if (conflicts || count > threshold) {
1210 siliconforks 332 /*
1211 siliconforks 507 * Enumerate live entries in this->table using a temporary
1212 siliconforks 332 * vector, by walking the (possibly sparse, due to deletions)
1213 siliconforks 507 * ancestor line from this->lastProp.
1214 siliconforks 332 */
1215 siliconforks 507 splen = entryCount;
1216 siliconforks 460 JS_ASSERT(splen != 0);
1217 siliconforks 332 spvec = (JSScopeProperty **)
1218 siliconforks 507 cx->malloc(SCOPE_TABLE_NBYTES(splen));
1219 siliconforks 332 if (!spvec)
1220     goto fail_overwrite;
1221     i = splen;
1222 siliconforks 507 sprop = SCOPE_LAST_PROP(this);
1223 siliconforks 332 JS_ASSERT(sprop);
1224     do {
1225     /*
1226 siliconforks 507 * NB: use JSScope::lookup, not JSScope::has, as the latter
1227     * macro insists that sprop->id maps to sprop, while the
1228     * former simply tests whether sprop->id is bound in this
1229     * scope.
1230 siliconforks 332 */
1231 siliconforks 507 if (!lookup(sprop->id))
1232 siliconforks 332 continue;
1233    
1234     JS_ASSERT(sprop != overwriting);
1235 siliconforks 460 JS_ASSERT(i != 0);
1236 siliconforks 332 spvec[--i] = sprop;
1237     } while ((sprop = sprop->parent) != NULL);
1238     JS_ASSERT(i == 0);
1239    
1240     /*
1241     * Now loop forward through spvec, forking the property tree
1242 siliconforks 507 * whenever we see a "parent gap" due to deletions from this
1243     * scope. NB: sprop is null on first entry to the loop body.
1244 siliconforks 332 */
1245     do {
1246     if (spvec[i]->parent == sprop) {
1247     sprop = spvec[i];
1248     } else {
1249     sprop = GetPropertyTreeChild(cx, sprop, spvec[i]);
1250     if (!sprop) {
1251 siliconforks 507 cx->free(spvec);
1252 siliconforks 332 goto fail_overwrite;
1253     }
1254    
1255 siliconforks 507 spp2 = search(sprop->id, false);
1256 siliconforks 332 JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]);
1257     SPROP_STORE_PRESERVING_COLLISION(spp2, sprop);
1258     }
1259     } while (++i < splen);
1260 siliconforks 507 cx->free(spvec);
1261 siliconforks 332
1262     /*
1263 siliconforks 507 * Now sprop points to the last property in this scope, where
1264     * the ancestor line from sprop to the root is dense w.r.t.
1265     * this scope: it contains no nodes not mapped by this->table.
1266 siliconforks 332 */
1267 siliconforks 507 lastProp = sprop;
1268     CHECK_ANCESTOR_LINE(this, false);
1269 siliconforks 332 JS_RUNTIME_METER(cx->runtime, middleDeleteFixups);
1270 siliconforks 507 clearMiddleDelete();
1271 siliconforks 332 }
1272     }
1273    
1274     /*
1275     * Aliases share another property's slot, passed in the |slot| param.
1276     * Shared properties have no slot. Unshared properties that do not
1277     * alias another property's slot get one here, but may lose it due to
1278     * a JS_ClearScope call.
1279     */
1280     if (!(flags & SPROP_IS_ALIAS)) {
1281     if (attrs & JSPROP_SHARED) {
1282     slot = SPROP_INVALID_SLOT;
1283     } else {
1284     /*
1285     * We may have set slot from a nearly-matching sprop, above.
1286     * If so, we're overwriting that nearly-matching sprop, so we
1287     * can reuse its slot -- we don't need to allocate a new one.
1288     * Similarly, we use a specific slot if provided by the caller.
1289     */
1290     if (slot == SPROP_INVALID_SLOT &&
1291 siliconforks 507 !js_AllocSlot(cx, object, &slot)) {
1292 siliconforks 332 goto fail_overwrite;
1293     }
1294     }
1295     }
1296    
1297     /*
1298     * Check for a watchpoint on a deleted property; if one exists, change
1299     * setter to js_watch_set.
1300     * XXXbe this could get expensive with lots of watchpoints...
1301     */
1302     if (!JS_CLIST_IS_EMPTY(&cx->runtime->watchPointList) &&
1303 siliconforks 507 js_FindWatchPoint(cx->runtime, this, id)) {
1304 siliconforks 460 if (overwriting)
1305     JS_PUSH_TEMP_ROOT_SPROP(cx, overwriting, &tvr);
1306 siliconforks 332 setter = js_WrapWatchedSetter(cx, id, attrs, setter);
1307 siliconforks 460 if (overwriting)
1308     JS_POP_TEMP_ROOT(cx, &tvr);
1309 siliconforks 332 if (!setter)
1310     goto fail_overwrite;
1311     }
1312    
1313     /* Find or create a property tree node labeled by our arguments. */
1314     child.id = id;
1315     child.getter = getter;
1316     child.setter = setter;
1317     child.slot = slot;
1318     child.attrs = attrs;
1319     child.flags = flags;
1320     child.shortid = shortid;
1321 siliconforks 507 sprop = GetPropertyTreeChild(cx, lastProp, &child);
1322 siliconforks 332 if (!sprop)
1323     goto fail_overwrite;
1324    
1325     /*
1326 siliconforks 507 * This scope's shape defaults to its last property's shape, but may be
1327     * regenerated later as this scope diverges (from the property cache
1328 siliconforks 332 * point of view) from the structural type associated with sprop.
1329     */
1330 siliconforks 507 extend(cx, sprop);
1331 siliconforks 332
1332     /* Store the tree node pointer in the table entry for id. */
1333 siliconforks 507 if (table)
1334 siliconforks 332 SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
1335 siliconforks 507 CHECK_ANCESTOR_LINE(this, false);
1336 siliconforks 332 #ifdef DEBUG
1337     if (!overwriting) {
1338     LIVE_SCOPE_METER(cx, ++cx->runtime->liveScopeProps);
1339     JS_RUNTIME_METER(cx->runtime, totalScopeProps);
1340     }
1341     #endif
1342    
1343     /*
1344 siliconforks 507 * If we reach the hashing threshold, try to allocate this->table.
1345 siliconforks 332 * If we can't (a rare event, preceded by swapping to death on most
1346     * modern OSes), stick with linear search rather than whining about
1347 siliconforks 507 * this little set-back. Therefore we must test !this->table and
1348     * this->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
1349 siliconforks 332 * entry count just reached the threshold.
1350     */
1351 siliconforks 507 if (!table && entryCount >= SCOPE_HASH_THRESHOLD)
1352     (void) createTable(cx, false);
1353 siliconforks 332 }
1354    
1355 siliconforks 460 jsuint index;
1356     if (js_IdIsIndex(sprop->id, &index))
1357 siliconforks 507 setIndexedProperties();
1358 siliconforks 460
1359 siliconforks 332 METER(adds);
1360     return sprop;
1361    
1362     fail_overwrite:
1363     if (overwriting) {
1364     /*
1365 siliconforks 507 * We may or may not have forked overwriting out of this scope's
1366     * ancestor line, so we must check (the alternative is to set a flag
1367     * above, but that hurts the common, non-error case). If we did fork
1368     * overwriting out, we'll add it back at scope->lastProp. This means
1369     * enumeration order can change due to a failure to overwrite an id.
1370     * XXXbe minor(?) incompatibility
1371 siliconforks 332 */
1372 siliconforks 507 for (sprop = SCOPE_LAST_PROP(this); ; sprop = sprop->parent) {
1373 siliconforks 332 if (!sprop) {
1374 siliconforks 507 sprop = SCOPE_LAST_PROP(this);
1375 siliconforks 332 if (overwriting->parent == sprop) {
1376 siliconforks 507 lastProp = overwriting;
1377 siliconforks 332 } else {
1378     sprop = GetPropertyTreeChild(cx, sprop, overwriting);
1379     if (sprop) {
1380     JS_ASSERT(sprop != overwriting);
1381 siliconforks 507 lastProp = sprop;
1382 siliconforks 332 }
1383     overwriting = sprop;
1384     }
1385     break;
1386     }
1387     if (sprop == overwriting)
1388     break;
1389     }
1390     if (overwriting) {
1391 siliconforks 507 if (table)
1392 siliconforks 332 SPROP_STORE_PRESERVING_COLLISION(spp, overwriting);
1393 siliconforks 507 entryCount++;
1394 siliconforks 332 }
1395 siliconforks 507 CHECK_ANCESTOR_LINE(this, true);
1396 siliconforks 332 }
1397     METER(addFailures);
1398     return NULL;
1399     }
1400    
1401     JSScopeProperty *
1402 siliconforks 507 JSScope::change(JSContext *cx, JSScopeProperty *sprop,
1403     uintN attrs, uintN mask,
1404     JSPropertyOp getter, JSPropertyOp setter)
1405 siliconforks 332 {
1406     JSScopeProperty child, *newsprop, **spp;
1407    
1408 siliconforks 507 CHECK_ANCESTOR_LINE(this, true);
1409 siliconforks 332
1410     /* Allow only shared (slot-less) => unshared (slot-full) transition. */
1411     attrs |= sprop->attrs & mask;
1412     JS_ASSERT(!((attrs ^ sprop->attrs) & JSPROP_SHARED) ||
1413     !(attrs & JSPROP_SHARED));
1414     if (getter == JS_PropertyStub)
1415     getter = NULL;
1416     if (setter == JS_PropertyStub)
1417     setter = NULL;
1418     if (sprop->attrs == attrs &&
1419     sprop->getter == getter &&
1420     sprop->setter == setter) {
1421     return sprop;
1422     }
1423    
1424     child.id = sprop->id;
1425     child.getter = getter;
1426     child.setter = setter;
1427     child.slot = sprop->slot;
1428     child.attrs = attrs;
1429     child.flags = sprop->flags;
1430     child.shortid = sprop->shortid;
1431    
1432 siliconforks 507 if (SCOPE_LAST_PROP(this) == sprop) {
1433 siliconforks 332 /*
1434 siliconforks 507 * Optimize the case where the last property added to this scope is
1435     * changed to have a different attrs, getter, or setter. In the last
1436     * property case, we need not fork the property tree. But since we do
1437     * not call JSScope::addProperty, we may need to allocate a new slot
1438     * directly.
1439 siliconforks 332 */
1440     if ((sprop->attrs & JSPROP_SHARED) && !(attrs & JSPROP_SHARED)) {
1441     JS_ASSERT(child.slot == SPROP_INVALID_SLOT);
1442 siliconforks 507 if (!js_AllocSlot(cx, object, &child.slot))
1443 siliconforks 332 return NULL;
1444     }
1445    
1446     newsprop = GetPropertyTreeChild(cx, sprop->parent, &child);
1447     if (newsprop) {
1448 siliconforks 507 spp = search(sprop->id, false);
1449 siliconforks 332 JS_ASSERT(SPROP_FETCH(spp) == sprop);
1450    
1451 siliconforks 507 if (table)
1452 siliconforks 332 SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
1453 siliconforks 507 lastProp = newsprop;
1454     CHECK_ANCESTOR_LINE(this, true);
1455 siliconforks 332 }
1456     } else {
1457     /*
1458 siliconforks 507 * Let JSScope::addProperty handle this |overwriting| case, including
1459     * the conservation of sprop->slot (if it's valid). We must not call
1460     * JSScope::remove here, because it will free a valid sprop->slot and
1461     * JSScope::add won't re-allocate it.
1462 siliconforks 332 */
1463 siliconforks 507 newsprop = add(cx, child.id, child.getter, child.setter, child.slot,
1464     child.attrs, child.flags, child.shortid);
1465 siliconforks 332 }
1466    
1467     if (newsprop) {
1468 siliconforks 507 js_LeaveTraceIfGlobalObject(cx, object);
1469     replacingShapeChange(cx, sprop, newsprop);
1470 siliconforks 332 }
1471     #ifdef JS_DUMP_PROPTREE_STATS
1472     else
1473     METER(changeFailures);
1474     #endif
1475     return newsprop;
1476     }
1477    
1478 siliconforks 507 bool
1479     JSScope::remove(JSContext *cx, jsid id)
1480 siliconforks 332 {
1481     JSScopeProperty **spp, *stored, *sprop;
1482     uint32 size;
1483    
1484 siliconforks 507 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, this));
1485     CHECK_ANCESTOR_LINE(this, true);
1486     if (sealed()) {
1487     reportReadOnlyScope(cx);
1488     return false;
1489 siliconforks 332 }
1490     METER(removes);
1491    
1492 siliconforks 507 spp = search(id, false);
1493 siliconforks 332 stored = *spp;
1494     sprop = SPROP_CLEAR_COLLISION(stored);
1495     if (!sprop) {
1496     METER(uselessRemoves);
1497 siliconforks 507 return true;
1498 siliconforks 332 }
1499    
1500     /* Convert from a list to a hash so we can handle "middle deletes". */
1501 siliconforks 507 if (!table && sprop != lastProp) {
1502     if (!createTable(cx, true))
1503     return false;
1504     spp = search(id, false);
1505 siliconforks 332 stored = *spp;
1506     sprop = SPROP_CLEAR_COLLISION(stored);
1507     }
1508    
1509     /* First, if sprop is unshared and not cleared, free its slot number. */
1510 siliconforks 507 if (SPROP_HAS_VALID_SLOT(sprop, this)) {
1511     js_FreeSlot(cx, object, sprop->slot);
1512 siliconforks 332 JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1513     }
1514    
1515     /* Next, remove id by setting its entry to a removed or free sentinel. */
1516     if (SPROP_HAD_COLLISION(stored)) {
1517 siliconforks 507 JS_ASSERT(table);
1518 siliconforks 332 *spp = SPROP_REMOVED;
1519 siliconforks 507 removedCount++;
1520 siliconforks 332 } else {
1521     METER(removeFrees);
1522 siliconforks 507 if (table)
1523 siliconforks 332 *spp = NULL;
1524     }
1525 siliconforks 507 entryCount--;
1526 siliconforks 332 LIVE_SCOPE_METER(cx, --cx->runtime->liveScopeProps);
1527    
1528 siliconforks 507 /* Update this->lastProp directly, or set its deferred update flag. */
1529     if (sprop == SCOPE_LAST_PROP(this)) {
1530 siliconforks 332 do {
1531 siliconforks 507 SCOPE_REMOVE_LAST_PROP(this);
1532     if (!hadMiddleDelete())
1533 siliconforks 332 break;
1534 siliconforks 507 sprop = SCOPE_LAST_PROP(this);
1535     } while (sprop && !has(sprop));
1536     if (!SCOPE_LAST_PROP(this))
1537     clearMiddleDelete();
1538     } else if (!hadMiddleDelete()) {
1539     setMiddleDelete();
1540 siliconforks 332 }
1541 siliconforks 507 generateOwnShape(cx);
1542     CHECK_ANCESTOR_LINE(this, true);
1543 siliconforks 332
1544 siliconforks 507 /* Last, consider shrinking this->table if its load factor is <= .25. */
1545     size = SCOPE_CAPACITY(this);
1546     if (size > MIN_SCOPE_SIZE && entryCount <= size >> 2) {
1547 siliconforks 332 METER(shrinks);
1548 siliconforks 507 (void) changeTable(cx, -1);
1549 siliconforks 332 }
1550    
1551 siliconforks 507 return true;
1552 siliconforks 332 }
1553    
1554     void
1555 siliconforks 507 JSScope::clear(JSContext *cx)
1556 siliconforks 332 {
1557 siliconforks 507 CHECK_ANCESTOR_LINE(this, true);
1558     LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= entryCount);
1559 siliconforks 332
1560 siliconforks 507 if (table)
1561     js_free(table);
1562     clearMiddleDelete();
1563     js_LeaveTraceIfGlobalObject(cx, object);
1564    
1565     JSClass *clasp = object->getClass();
1566     JSObject *proto = object->getProto();
1567     JSEmptyScope *emptyScope;
1568     uint32 newShape;
1569     if (proto &&
1570     OBJ_IS_NATIVE(proto) &&
1571     (emptyScope = OBJ_SCOPE(proto)->emptyScope) &&
1572     emptyScope->clasp == clasp) {
1573     newShape = emptyScope->shape;
1574     } else {
1575     newShape = js_GenerateShape(cx, false);
1576     }
1577     initMinimal(cx, newShape);
1578    
1579 siliconforks 332 JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1580     }
1581    
1582     void
1583 siliconforks 507 JSScope::brandingShapeChange(JSContext *cx, uint32 slot, jsval v)
1584     {
1585     generateOwnShape(cx);
1586     }
1587    
1588     void
1589     JSScope::deletingShapeChange(JSContext *cx, JSScopeProperty *sprop)
1590     {
1591     generateOwnShape(cx);
1592     }
1593    
1594     void
1595     JSScope::methodShapeChange(JSContext *cx, uint32 slot, jsval toval)
1596     {
1597     generateOwnShape(cx);
1598     }
1599    
1600     void
1601     JSScope::protoShapeChange(JSContext *cx)
1602     {
1603     generateOwnShape(cx);
1604     }
1605    
1606     void
1607     JSScope::replacingShapeChange(JSContext *cx, JSScopeProperty *sprop, JSScopeProperty *newsprop)
1608     {
1609     if (shape == sprop->shape)
1610     shape = newsprop->shape;
1611     else
1612     generateOwnShape(cx);
1613     }
1614    
1615     void
1616     JSScope::sealingShapeChange(JSContext *cx)
1617     {
1618     generateOwnShape(cx);
1619     }
1620    
1621     void
1622     JSScope::shadowingShapeChange(JSContext *cx, JSScopeProperty *sprop)
1623     {
1624     generateOwnShape(cx);
1625     }
1626    
1627     void
1628 siliconforks 332 js_TraceId(JSTracer *trc, jsid id)
1629     {
1630     jsval v;
1631    
1632     v = ID_TO_VALUE(id);
1633     JS_CALL_VALUE_TRACER(trc, v, "id");
1634     }
1635    
1636     #ifdef DEBUG
1637     static void
1638     PrintPropertyGetterOrSetter(JSTracer *trc, char *buf, size_t bufsize)
1639     {
1640     JSScopeProperty *sprop;
1641     jsid id;
1642     size_t n;
1643     const char *name;
1644    
1645     JS_ASSERT(trc->debugPrinter == PrintPropertyGetterOrSetter);
1646     sprop = (JSScopeProperty *)trc->debugPrintArg;
1647     id = sprop->id;
1648     name = trc->debugPrintIndex ? js_setter_str : js_getter_str;
1649    
1650     if (JSID_IS_ATOM(id)) {
1651     n = js_PutEscapedString(buf, bufsize - 1,
1652     ATOM_TO_STRING(JSID_TO_ATOM(id)), 0);
1653     if (n < bufsize - 1)
1654     JS_snprintf(buf + n, bufsize - n, " %s", name);
1655     } else if (JSID_IS_INT(sprop->id)) {
1656     JS_snprintf(buf, bufsize, "%d %s", JSID_TO_INT(id), name);
1657     } else {
1658     JS_snprintf(buf, bufsize, "<object> %s", name);
1659     }
1660     }
1661     #endif
1662    
1663     void
1664 siliconforks 507 JSScopeProperty::trace(JSTracer *trc)
1665 siliconforks 332 {
1666     if (IS_GC_MARKING_TRACER(trc))
1667 siliconforks 507 flags |= SPROP_MARK;
1668     js_TraceId(trc, id);
1669 siliconforks 332
1670     #if JS_HAS_GETTER_SETTER
1671 siliconforks 507 if (attrs & (JSPROP_GETTER | JSPROP_SETTER)) {
1672     if (attrs & JSPROP_GETTER) {
1673     JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, this, 0);
1674     JS_CallTracer(trc, js_CastAsObject(getter), JSTRACE_OBJECT);
1675 siliconforks 332 }
1676 siliconforks 507 if (attrs & JSPROP_SETTER) {
1677     JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, this, 1);
1678     JS_CallTracer(trc, js_CastAsObject(setter), JSTRACE_OBJECT);
1679 siliconforks 332 }
1680     }
1681     #endif /* JS_HAS_GETTER_SETTER */
1682     }
1683    
1684     #ifdef JS_DUMP_PROPTREE_STATS
1685    
1686     #include <stdio.h>
1687    
1688     static void
1689     MeterKidCount(JSBasicStats *bs, uintN nkids)
1690     {
1691     JS_BASIC_STATS_ACCUM(bs, nkids);
1692     bs->hist[JS_MIN(nkids, 10)]++;
1693     }
1694    
1695     static void
1696     MeterPropertyTree(JSBasicStats *bs, JSScopeProperty *node)
1697     {
1698     uintN i, nkids;
1699     JSScopeProperty *kids, *kid;
1700     PropTreeKidsChunk *chunk;
1701    
1702     nkids = 0;
1703     kids = node->kids;
1704     if (kids) {
1705     if (KIDS_IS_CHUNKY(kids)) {
1706     for (chunk = KIDS_TO_CHUNK(kids); chunk; chunk = chunk->next) {
1707     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1708     kid = chunk->kids[i];
1709     if (!kid)
1710     break;
1711     MeterPropertyTree(bs, kid);
1712     nkids++;
1713     }
1714     }
1715     } else {
1716     MeterPropertyTree(bs, kids);
1717     nkids = 1;
1718     }
1719     }
1720    
1721     MeterKidCount(bs, nkids);
1722     }
1723    
1724     static JSDHashOperator
1725     js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
1726     void *arg)
1727     {
1728     JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)hdr;
1729     JSBasicStats *bs = (JSBasicStats *)arg;
1730    
1731     MeterPropertyTree(bs, entry->child);
1732     return JS_DHASH_NEXT;
1733     }
1734    
1735     static void
1736     DumpSubtree(JSContext *cx, JSScopeProperty *sprop, int level, FILE *fp)
1737     {
1738     jsval v;
1739     JSString *str;
1740     JSScopeProperty *kids, *kid;
1741     PropTreeKidsChunk *chunk;
1742     uintN i;
1743    
1744     fprintf(fp, "%*sid ", level, "");
1745     v = ID_TO_VALUE(sprop->id);
1746     if (JSID_IS_INT(sprop->id)) {
1747     fprintf(fp, "%d", JSVAL_TO_INT(v));
1748     } else {
1749     if (JSID_IS_ATOM(sprop->id)) {
1750     str = JSVAL_TO_STRING(v);
1751     } else {
1752     JS_ASSERT(JSID_IS_OBJECT(sprop->id));
1753     str = js_ValueToString(cx, v);
1754     fputs("object ", fp);
1755     }
1756     if (!str)
1757     fputs("<error>", fp);
1758     else
1759     js_FileEscapedString(fp, str, '"');
1760     }
1761    
1762     fprintf(fp, " g/s %p/%p slot %u attrs %x flags %x shortid %d\n",
1763     (void *) sprop->getter, (void *) sprop->setter, sprop->slot,
1764     sprop->attrs, sprop->flags, sprop->shortid);
1765     kids = sprop->kids;
1766     if (kids) {
1767     ++level;
1768     if (KIDS_IS_CHUNKY(kids)) {
1769     chunk = KIDS_TO_CHUNK(kids);
1770     do {
1771     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1772     kid = chunk->kids[i];
1773     if (!kid)
1774     break;
1775     JS_ASSERT(kid->parent == sprop);
1776     DumpSubtree(cx, kid, level, fp);
1777     }
1778     } while ((chunk = chunk->next) != NULL);
1779     } else {
1780     kid = kids;
1781     DumpSubtree(cx, kid, level, fp);
1782     }
1783     }
1784     }
1785    
1786     #endif /* JS_DUMP_PROPTREE_STATS */
1787    
1788     void
1789     js_SweepScopeProperties(JSContext *cx)
1790     {
1791     JSRuntime *rt = cx->runtime;
1792     JSArena **ap, *a;
1793     JSScopeProperty *limit, *sprop, *parent, *kids, *kid;
1794     uintN liveCount;
1795     PropTreeKidsChunk *chunk, *nextChunk, *freeChunk;
1796     uintN i;
1797    
1798     #ifdef JS_DUMP_PROPTREE_STATS
1799     JSBasicStats bs;
1800     uint32 livePropCapacity = 0, totalLiveCount = 0;
1801     static FILE *logfp;
1802     if (!logfp)
1803     logfp = fopen("/tmp/proptree.stats", "w");
1804    
1805     JS_BASIC_STATS_INIT(&bs);
1806     MeterKidCount(&bs, rt->propertyTreeHash.entryCount);
1807     JS_DHashTableEnumerate(&rt->propertyTreeHash, js_MeterPropertyTree, &bs);
1808    
1809     {
1810     double props, nodes, mean, sigma;
1811    
1812     props = rt->liveScopePropsPreSweep;
1813     nodes = rt->livePropTreeNodes;
1814     JS_ASSERT(nodes == bs.sum);
1815     mean = JS_MeanAndStdDevBS(&bs, &sigma);
1816    
1817     fprintf(logfp,
1818     "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
1819     props, nodes, nodes / props, mean, sigma, bs.max);
1820     }
1821    
1822     JS_DumpHistogram(&bs, logfp);
1823     #endif
1824    
1825     ap = &rt->propertyArenaPool.first.next;
1826     while ((a = *ap) != NULL) {
1827     limit = (JSScopeProperty *) a->avail;
1828     liveCount = 0;
1829     for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) {
1830     /* If the id is null, sprop is already on the freelist. */
1831     if (sprop->id == JSVAL_NULL)
1832     continue;
1833    
1834     /*
1835     * If the mark bit is set, sprop is alive, so clear the mark bit
1836     * and continue the while loop.
1837     *
1838     * Regenerate sprop->shape if it hasn't already been refreshed
1839     * during the mark phase, when live scopes' lastProp members are
1840     * followed to update both scope->shape and lastProp->shape.
1841     */
1842     if (sprop->flags & SPROP_MARK) {
1843     sprop->flags &= ~SPROP_MARK;
1844 siliconforks 507 if (rt->gcRegenShapes) {
1845     if (sprop->flags & SPROP_FLAG_SHAPE_REGEN)
1846     sprop->flags &= ~SPROP_FLAG_SHAPE_REGEN;
1847     else
1848     sprop->shape = js_RegenerateShapeForGC(cx);
1849     }
1850 siliconforks 332 liveCount++;
1851     continue;
1852     }
1853    
1854     /* Ok, sprop is garbage to collect: unlink it from its parent. */
1855     freeChunk = RemovePropertyTreeChild(rt, sprop);
1856    
1857     /*
1858     * Take care to reparent all sprop's kids to their grandparent.
1859     * InsertPropertyTreeChild can potentially fail for two reasons:
1860     *
1861     * 1. If parent is null, insertion into the root property hash
1862     * table may fail. We are forced to leave the kid out of the
1863     * table (as can already happen with duplicates) but ensure
1864     * that the kid's parent pointer is set to null.
1865     *
1866     * 2. If parent is non-null, allocation of a new KidsChunk can
1867     * fail. To prevent this from happening, we allow sprops's own
1868     * chunks to be reused by the grandparent, which removes the
1869     * need for InsertPropertyTreeChild to malloc a new KidsChunk.
1870     *
1871     * If sprop does not have chunky kids, then we rely on the
1872     * RemovePropertyTreeChild call above (which removed sprop from
1873     * its parent) either leaving one free entry, or else returning
1874     * the now-unused chunk to us so we can reuse it.
1875     *
1876     * We also require the grandparent to have either no kids or else
1877     * chunky kids. A single non-chunky kid would force a new chunk to
1878     * be malloced in some cases (if sprop had a single non-chunky
1879     * kid, or a multiple of MAX_KIDS_PER_CHUNK kids). Note that
1880     * RemovePropertyTreeChild never converts a single-entry chunky
1881     * kid back to a non-chunky kid, so we are assured of correct
1882     * behaviour.
1883     */
1884     kids = sprop->kids;
1885     if (kids) {
1886     sprop->kids = NULL;
1887     parent = sprop->parent;
1888    
1889 siliconforks 507 /* The grandparent must have either no kids or chunky kids. */
1890 siliconforks 332 JS_ASSERT(!parent || !parent->kids ||
1891     KIDS_IS_CHUNKY(parent->kids));
1892     if (KIDS_IS_CHUNKY(kids)) {
1893     chunk = KIDS_TO_CHUNK(kids);
1894     do {
1895     nextChunk = chunk->next;
1896     chunk->next = NULL;
1897     for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1898     kid = chunk->kids[i];
1899     if (!kid)
1900     break;
1901     JS_ASSERT(kid->parent == sprop);
1902    
1903     /*
1904     * Clear a space in the kids array for possible
1905     * re-use by InsertPropertyTreeChild.
1906     */
1907     chunk->kids[i] = NULL;
1908 siliconforks 507 if (!InsertPropertyTreeChild(rt, parent, kid, chunk)) {
1909 siliconforks 332 /*
1910     * This can happen only if we failed to add an
1911     * entry to the root property hash table.
1912     */
1913     JS_ASSERT(!parent);
1914     kid->parent = NULL;
1915     }
1916     }
1917     if (!chunk->kids[0]) {
1918     /* The chunk wasn't reused, so we must free it. */
1919     DestroyPropTreeKidsChunk(rt, chunk);
1920     }
1921     } while ((chunk = nextChunk) != NULL);
1922     } else {
1923     kid = kids;
1924     if (!InsertPropertyTreeChild(rt, parent, kid, freeChunk)) {
1925     /*
1926     * This can happen only if we failed to add an entry
1927     * to the root property hash table.
1928     */
1929     JS_ASSERT(!parent);
1930     kid->parent = NULL;
1931     }
1932     }
1933     }
1934    
1935     if (freeChunk && !freeChunk->kids[0]) {
1936     /* The chunk wasn't reused, so we must free it. */
1937     DestroyPropTreeKidsChunk(rt, freeChunk);
1938     }
1939    
1940     /* Clear id so we know (above) that sprop is on the freelist. */
1941     sprop->id = JSVAL_NULL;
1942     FREENODE_INSERT(rt->propertyFreeList, sprop);
1943     JS_RUNTIME_UNMETER(rt, livePropTreeNodes);
1944     }
1945    
1946     /* If a contains no live properties, return it to the malloc heap. */
1947     if (liveCount == 0) {
1948     for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++)
1949     FREENODE_REMOVE(sprop);
1950     JS_ARENA_DESTROY(&rt->propertyArenaPool, a, ap);
1951     } else {
1952     #ifdef JS_DUMP_PROPTREE_STATS
1953     livePropCapacity += limit - (JSScopeProperty *) a->base;
1954     totalLiveCount += liveCount;
1955     #endif
1956     ap = &a->next;
1957     }
1958     }
1959    
1960     #ifdef JS_DUMP_PROPTREE_STATS
1961     fprintf(logfp, "arenautil %g%%\n",
1962     (totalLiveCount && livePropCapacity)
1963     ? (totalLiveCount * 100.0) / livePropCapacity
1964     : 0.0);
1965    
1966     #define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
1967    
1968     fprintf(logfp, "Scope search stats:\n"
1969     " searches: %6u\n"
1970     " hits: %6u %5.2f%% of searches\n"
1971     " misses: %6u %5.2f%%\n"
1972     " hashes: %6u %5.2f%%\n"
1973     " steps: %6u %5.2f%% %5.2f%% of hashes\n"
1974     " stepHits: %6u %5.2f%% %5.2f%%\n"
1975     " stepMisses: %6u %5.2f%% %5.2f%%\n"
1976     " adds: %6u\n"
1977     " redundantAdds: %6u\n"
1978     " addFailures: %6u\n"
1979     " changeFailures: %6u\n"
1980     " compresses: %6u\n"
1981     " grows: %6u\n"
1982     " removes: %6u\n"
1983     " removeFrees: %6u\n"
1984     " uselessRemoves: %6u\n"
1985     " shrinks: %6u\n",
1986     js_scope_stats.searches,
1987     js_scope_stats.hits, RATE(hits, searches),
1988     js_scope_stats.misses, RATE(misses, searches),
1989     js_scope_stats.hashes, RATE(hashes, searches),
1990     js_scope_stats.steps, RATE(steps, searches), RATE(steps, hashes),
1991     js_scope_stats.stepHits,
1992     RATE(stepHits, searches), RATE(stepHits, hashes),
1993     js_scope_stats.stepMisses,
1994     RATE(stepMisses, searches), RATE(stepMisses, hashes),
1995     js_scope_stats.adds,
1996     js_scope_stats.redundantAdds,
1997     js_scope_stats.addFailures,
1998     js_scope_stats.changeFailures,
1999     js_scope_stats.compresses,
2000     js_scope_stats.grows,
2001     js_scope_stats.removes,
2002     js_scope_stats.removeFrees,
2003     js_scope_stats.uselessRemoves,
2004     js_scope_stats.shrinks);
2005    
2006     #undef RATE
2007    
2008     fflush(logfp);
2009     #endif
2010    
2011     #ifdef DUMP_PROPERTY_TREE
2012     {
2013     FILE *dumpfp = fopen("/tmp/proptree.dump", "w");
2014     if (dumpfp) {
2015     JSPropertyTreeEntry *pte, *end;
2016    
2017     pte = (JSPropertyTreeEntry *) rt->propertyTreeHash.entryStore;
2018     end = pte + JS_DHASH_TABLE_SIZE(&rt->propertyTreeHash);
2019     while (pte < end) {
2020     if (pte->child)
2021     DumpSubtree(cx, pte->child, 0, dumpfp);
2022     pte++;
2023     }
2024     fclose(dumpfp);
2025     }
2026     }
2027     #endif
2028     }
2029    
2030 siliconforks 507 bool
2031 siliconforks 332 js_InitPropertyTree(JSRuntime *rt)
2032     {
2033     if (!JS_DHashTableInit(&rt->propertyTreeHash, &PropertyTreeHashOps, NULL,
2034     sizeof(JSPropertyTreeEntry), JS_DHASH_MIN_SIZE)) {
2035     rt->propertyTreeHash.ops = NULL;
2036 siliconforks 507 return false;
2037 siliconforks 332 }
2038     JS_INIT_ARENA_POOL(&rt->propertyArenaPool, "properties",
2039     256 * sizeof(JSScopeProperty), sizeof(void *), NULL);
2040 siliconforks 507 return true;
2041 siliconforks 332 }
2042    
2043     void
2044     js_FinishPropertyTree(JSRuntime *rt)
2045     {
2046     if (rt->propertyTreeHash.ops) {
2047     JS_DHashTableFinish(&rt->propertyTreeHash);
2048     rt->propertyTreeHash.ops = NULL;
2049     }
2050     JS_FinishArenaPool(&rt->propertyArenaPool);
2051     }

  ViewVC Help
Powered by ViewVC 1.1.24