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

Contents of /trunk/js/jsscope.cpp

Parent Directory Parent Directory | Revision Log Revision Log


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

1 /* -*- 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 <new>
45 #include <stdlib.h>
46 #include <string.h>
47 #include "jstypes.h"
48 #include "jsstdint.h"
49 #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 #include "jstracer.h"
63
64 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 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 if (scope->owned())
97 return scope;
98
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 newscope = JSScope::create(cx, scope->ops, obj->getClass(), obj, scope->shape);
105 if (!newscope)
106 return NULL;
107 JS_LOCK_SCOPE(cx, newscope);
108 obj->map = newscope;
109
110 JS_ASSERT(newscope->freeslot == JSSLOT_FREE(STOBJ_GET_CLASS(obj)));
111 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 if (newscope->freeslot < freeslot)
117 newscope->freeslot = freeslot;
118 }
119 JS_TRANSFER_SCOPE_LOCK(cx, scope, newscope);
120 JS_ATOMIC_DECREMENT(&scope->nrefs);
121 if (scope->nrefs == 0)
122 JSScope::destroy(cx, scope);
123 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 void
137 JSScope::initMinimal(JSContext *cx, uint32 newShape)
138 {
139 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 }
146
147 bool
148 JSScope::createTable(JSContext *cx, bool report)
149 {
150 int sizeLog2;
151 JSScopeProperty *sprop, **spp;
152
153 JS_ASSERT(!table);
154 JS_ASSERT(lastProp);
155
156 if (entryCount > SCOPE_HASH_THRESHOLD) {
157 /*
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 sizeLog2 = JS_CeilingLog2(2 * entryCount);
165 hashShift = JS_DHASH_BITS - sizeLog2;
166 } else {
167 JS_ASSERT(hashShift == JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2);
168 sizeLog2 = MIN_SCOPE_SIZE_LOG2;
169 }
170
171 table = (JSScopeProperty **) js_calloc(JS_BIT(sizeLog2) * sizeof(JSScopeProperty *));
172 if (!table) {
173 if (report)
174 JS_ReportOutOfMemory(cx);
175 return false;
176 }
177 cx->updateMallocCounter(JS_BIT(sizeLog2) * sizeof(JSScopeProperty *));
178
179 hashShift = JS_DHASH_BITS - sizeLog2;
180 for (sprop = lastProp; sprop; sprop = sprop->parent) {
181 spp = search(sprop->id, true);
182 SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
183 }
184 return true;
185 }
186
187 JSScope *
188 JSScope::create(JSContext *cx, const JSObjectOps *ops, JSClass *clasp,
189 JSObject *obj, uint32 shape)
190 {
191 JS_ASSERT(OPS_IS_NATIVE(ops));
192 JS_ASSERT(obj);
193
194 JSScope *scope = cx->create<JSScope>(ops, obj);
195 if (!scope)
196 return NULL;
197
198 scope->nrefs = 1;
199 scope->freeslot = JSSLOT_FREE(clasp);
200 scope->flags = cx->runtime->gcRegenShapesScopeFlag;
201 js_LeaveTraceIfGlobalObject(cx, obj);
202 scope->initMinimal(cx, shape);
203
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 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 #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 JSScope::destroy(JSContext *cx, JSScope *scope)
248 {
249 #ifdef JS_THREADSAFE
250 js_FinishTitle(cx, &scope->title);
251 #endif
252 if (scope->table)
253 cx->free(scope->table);
254 if (scope->emptyScope)
255 scope->emptyScope->drop(cx, NULL);
256
257 LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= scope->entryCount);
258 JS_RUNTIME_UNMETER(cx->runtime, liveScopes);
259 cx->free(scope);
260 }
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 JSScopeProperty **
312 JSScope::searchTable(jsid id, bool adding)
313 {
314 JSHashNumber hash0, hash1, hash2;
315 int sizeLog2;
316 JSScopeProperty *stored, *sprop, **spp, **firstRemoved;
317 uint32 sizeMask;
318
319 JS_ASSERT(table);
320
321 /* Compute the primary hash address. */
322 METER(hashes);
323 hash0 = SCOPE_HASH0(id);
324 hash1 = SCOPE_HASH1(hash0, hashShift);
325 spp = table + hash1;
326
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 spp = table + hash1;
360
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 bool
387 JSScope::changeTable(JSContext *cx, int change)
388 {
389 int oldlog2, newlog2;
390 uint32 oldsize, newsize, nbytes;
391 JSScopeProperty **newtable, **oldtable, **spp, **oldspp, *sprop;
392
393 if (!table)
394 return createTable(cx, true);
395
396 /* Grow, shrink, or compress by changing this->table. */
397 oldlog2 = JS_DHASH_BITS - hashShift;
398 newlog2 = oldlog2 + change;
399 oldsize = JS_BIT(oldlog2);
400 newsize = JS_BIT(newlog2);
401 nbytes = SCOPE_TABLE_NBYTES(newsize);
402 newtable = (JSScopeProperty **) cx->calloc(nbytes);
403 if (!newtable)
404 return false;
405
406 /* Now that we have newtable allocated, update members. */
407 hashShift = JS_DHASH_BITS - newlog2;
408 removedCount = 0;
409 oldtable = table;
410 table = newtable;
411
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 spp = search(sprop->id, true);
420 JS_ASSERT(SPROP_IS_FREE(*spp));
421 *spp = sprop;
422 }
423 oldsize--;
424 }
425
426 /* Finally, free the old table storage. */
427 cx->free(oldtable);
428 return true;
429 }
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 chunk = (PropTreeKidsChunk *) js_calloc(sizeof *chunk);
578 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 js_free(chunk);
592 }
593
594 /* NB: Called with rt->gcLock held. */
595 static bool
596 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 return false;
613 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 return false;
650 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 return false;
694 }
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 return false;
715 }
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 return true;
727 }
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 * We use rt->gcLock, not rt->rtLock, to avoid nesting the former inside the
840 * latter in js_GenerateShape below.
841 */
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 sprop->shape = js_GenerateShape(cx, true);
951
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 CheckAncestorLine(JSScope *scope, bool sparse)
977 {
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 JS_ASSERT(scope->has(ancestorLine));
985
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 if (scope->hadMiddleDelete() && !scope->has(sprop)) {
1005 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 void
1017 JSScope::reportReadOnlyScope(JSContext *cx)
1018 {
1019 JSString *str;
1020 const char *bytes;
1021
1022 str = js_ValueToString(cx, OBJECT_TO_JSVAL(object));
1023 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 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 JSScopeProperty *
1042 JSScope::add(JSContext *cx, jsid id,
1043 JSPropertyOp getter, JSPropertyOp setter,
1044 uint32 slot, uintN attrs,
1045 uintN flags, intN shortid)
1046 {
1047 JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child;
1048 uint32 size, splen, i;
1049 int change;
1050 JSTempValueRooter tvr;
1051
1052 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, this));
1053 CHECK_ANCESTOR_LINE(this, true);
1054
1055 JS_ASSERT(!JSVAL_IS_NULL(id));
1056 JS_ASSERT_IF(!cx->runtime->gcRegenShapes,
1057 hasRegenFlag(cx->runtime->gcRegenShapesScopeFlag));
1058
1059 /*
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 if (sealed()) {
1066 reportReadOnlyScope(cx);
1067 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 spp = search(id, true);
1084 sprop = overwriting = SPROP_FETCH(spp);
1085 if (!sprop) {
1086 /* Check whether we need to grow, if the load factor is >= .75. */
1087 size = SCOPE_CAPACITY(this);
1088 if (entryCount + removedCount >= size - (size >> 2)) {
1089 if (removedCount >= size >> 2) {
1090 METER(compresses);
1091 change = 0;
1092 } else {
1093 METER(grows);
1094 change = 1;
1095 }
1096 if (!changeTable(cx, change) &&
1097 entryCount + removedCount == size - 1) {
1098 METER(addFailures);
1099 return NULL;
1100 }
1101 spp = search(id, true);
1102 JS_ASSERT(!SPROP_FETCH(spp));
1103 }
1104 } else {
1105 /* Property exists: JSScope::search must have returned a valid *spp. */
1106 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 SPROP_HAS_VALID_SLOT(sprop, this)) {
1117 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 * 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 * ancestor line at this->lastProp, lazily if sprop is not lastProp.
1129 * And we must remove the entry at *spp, precisely so the lazy "middle
1130 * delete" fixup code further below won't find sprop in this->table,
1131 * in spite of sprop being on the ancestor line.
1132 *
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 if (sprop == SCOPE_LAST_PROP(this)) {
1140 do {
1141 SCOPE_REMOVE_LAST_PROP(this);
1142 if (!hadMiddleDelete())
1143 break;
1144 sprop = SCOPE_LAST_PROP(this);
1145 } while (sprop && !has(sprop));
1146 } else if (!hadMiddleDelete()) {
1147 /*
1148 * If we have no hash table yet, we need one now. The middle
1149 * delete code is simple-minded that way!
1150 */
1151 if (!table) {
1152 if (!createTable(cx, true))
1153 return NULL;
1154 spp = search(id, true);
1155 sprop = overwriting = SPROP_FETCH(spp);
1156 }
1157 setMiddleDelete();
1158 }
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 * 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 * flow returns from this function.
1166 */
1167 if (table)
1168 SPROP_STORE_PRESERVING_COLLISION(spp, NULL);
1169 entryCount--;
1170 CHECK_ANCESTOR_LINE(this, true);
1171 sprop = NULL;
1172 }
1173
1174 if (!sprop) {
1175 /*
1176 * If properties were deleted from the middle of the list starting at
1177 * 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 * the rule that properties along an ancestor line have distinct ids.
1181 */
1182 if (hadMiddleDelete()) {
1183 JS_ASSERT(table);
1184 CHECK_ANCESTOR_LINE(this, true);
1185
1186 /*
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 uint32 threshold = JS_BIT(JS_CeilingLog2(entryCount));
1201 for (sprop = SCOPE_LAST_PROP(this); sprop; sprop = sprop->parent) {
1202 ++count;
1203 if (sprop->id == id) {
1204 conflicts = true;
1205 break;
1206 }
1207 }
1208
1209 if (conflicts || count > threshold) {
1210 /*
1211 * Enumerate live entries in this->table using a temporary
1212 * vector, by walking the (possibly sparse, due to deletions)
1213 * ancestor line from this->lastProp.
1214 */
1215 splen = entryCount;
1216 JS_ASSERT(splen != 0);
1217 spvec = (JSScopeProperty **)
1218 cx->malloc(SCOPE_TABLE_NBYTES(splen));
1219 if (!spvec)
1220 goto fail_overwrite;
1221 i = splen;
1222 sprop = SCOPE_LAST_PROP(this);
1223 JS_ASSERT(sprop);
1224 do {
1225 /*
1226 * 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 */
1231 if (!lookup(sprop->id))
1232 continue;
1233
1234 JS_ASSERT(sprop != overwriting);
1235 JS_ASSERT(i != 0);
1236 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 * 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 */
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 cx->free(spvec);
1252 goto fail_overwrite;
1253 }
1254
1255 spp2 = search(sprop->id, false);
1256 JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]);
1257 SPROP_STORE_PRESERVING_COLLISION(spp2, sprop);
1258 }
1259 } while (++i < splen);
1260 cx->free(spvec);
1261
1262 /*
1263 * 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 */
1267 lastProp = sprop;
1268 CHECK_ANCESTOR_LINE(this, false);
1269 JS_RUNTIME_METER(cx->runtime, middleDeleteFixups);
1270 clearMiddleDelete();
1271 }
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 !js_AllocSlot(cx, object, &slot)) {
1292 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 js_FindWatchPoint(cx->runtime, this, id)) {
1304 if (overwriting)
1305 JS_PUSH_TEMP_ROOT_SPROP(cx, overwriting, &tvr);
1306 setter = js_WrapWatchedSetter(cx, id, attrs, setter);
1307 if (overwriting)
1308 JS_POP_TEMP_ROOT(cx, &tvr);
1309 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 sprop = GetPropertyTreeChild(cx, lastProp, &child);
1322 if (!sprop)
1323 goto fail_overwrite;
1324
1325 /*
1326 * 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 * point of view) from the structural type associated with sprop.
1329 */
1330 extend(cx, sprop);
1331
1332 /* Store the tree node pointer in the table entry for id. */
1333 if (table)
1334 SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
1335 CHECK_ANCESTOR_LINE(this, false);
1336 #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 * If we reach the hashing threshold, try to allocate this->table.
1345 * 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 * this little set-back. Therefore we must test !this->table and
1348 * this->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
1349 * entry count just reached the threshold.
1350 */
1351 if (!table && entryCount >= SCOPE_HASH_THRESHOLD)
1352 (void) createTable(cx, false);
1353 }
1354
1355 jsuint index;
1356 if (js_IdIsIndex(sprop->id, &index))
1357 setIndexedProperties();
1358
1359 METER(adds);
1360 return sprop;
1361
1362 fail_overwrite:
1363 if (overwriting) {
1364 /*
1365 * 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 */
1372 for (sprop = SCOPE_LAST_PROP(this); ; sprop = sprop->parent) {
1373 if (!sprop) {
1374 sprop = SCOPE_LAST_PROP(this);
1375 if (overwriting->parent == sprop) {
1376 lastProp = overwriting;
1377 } else {
1378 sprop = GetPropertyTreeChild(cx, sprop, overwriting);
1379 if (sprop) {
1380 JS_ASSERT(sprop != overwriting);
1381 lastProp = sprop;
1382 }
1383 overwriting = sprop;
1384 }
1385 break;
1386 }
1387 if (sprop == overwriting)
1388 break;
1389 }
1390 if (overwriting) {
1391 if (table)
1392 SPROP_STORE_PRESERVING_COLLISION(spp, overwriting);
1393 entryCount++;
1394 }
1395 CHECK_ANCESTOR_LINE(this, true);
1396 }
1397 METER(addFailures);
1398 return NULL;
1399 }
1400
1401 JSScopeProperty *
1402 JSScope::change(JSContext *cx, JSScopeProperty *sprop,
1403 uintN attrs, uintN mask,
1404 JSPropertyOp getter, JSPropertyOp setter)
1405 {
1406 JSScopeProperty child, *newsprop, **spp;
1407
1408 CHECK_ANCESTOR_LINE(this, true);
1409
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 if (SCOPE_LAST_PROP(this) == sprop) {
1433 /*
1434 * 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 */
1440 if ((sprop->attrs & JSPROP_SHARED) && !(attrs & JSPROP_SHARED)) {
1441 JS_ASSERT(child.slot == SPROP_INVALID_SLOT);
1442 if (!js_AllocSlot(cx, object, &child.slot))
1443 return NULL;
1444 }
1445
1446 newsprop = GetPropertyTreeChild(cx, sprop->parent, &child);
1447 if (newsprop) {
1448 spp = search(sprop->id, false);
1449 JS_ASSERT(SPROP_FETCH(spp) == sprop);
1450
1451 if (table)
1452 SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
1453 lastProp = newsprop;
1454 CHECK_ANCESTOR_LINE(this, true);
1455 }
1456 } else {
1457 /*
1458 * 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 */
1463 newsprop = add(cx, child.id, child.getter, child.setter, child.slot,
1464 child.attrs, child.flags, child.shortid);
1465 }
1466
1467 if (newsprop) {
1468 js_LeaveTraceIfGlobalObject(cx, object);
1469 replacingShapeChange(cx, sprop, newsprop);
1470 }
1471 #ifdef JS_DUMP_PROPTREE_STATS
1472 else
1473 METER(changeFailures);
1474 #endif
1475 return newsprop;
1476 }
1477
1478 bool
1479 JSScope::remove(JSContext *cx, jsid id)
1480 {
1481 JSScopeProperty **spp, *stored, *sprop;
1482 uint32 size;
1483
1484 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, this));
1485 CHECK_ANCESTOR_LINE(this, true);
1486 if (sealed()) {
1487 reportReadOnlyScope(cx);
1488 return false;
1489 }
1490 METER(removes);
1491
1492 spp = search(id, false);
1493 stored = *spp;
1494 sprop = SPROP_CLEAR_COLLISION(stored);
1495 if (!sprop) {
1496 METER(uselessRemoves);
1497 return true;
1498 }
1499
1500 /* Convert from a list to a hash so we can handle "middle deletes". */
1501 if (!table && sprop != lastProp) {
1502 if (!createTable(cx, true))
1503 return false;
1504 spp = search(id, false);
1505 stored = *spp;
1506 sprop = SPROP_CLEAR_COLLISION(stored);
1507 }
1508
1509 /* First, if sprop is unshared and not cleared, free its slot number. */
1510 if (SPROP_HAS_VALID_SLOT(sprop, this)) {
1511 js_FreeSlot(cx, object, sprop->slot);
1512 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 JS_ASSERT(table);
1518 *spp = SPROP_REMOVED;
1519 removedCount++;
1520 } else {
1521 METER(removeFrees);
1522 if (table)
1523 *spp = NULL;
1524 }
1525 entryCount--;
1526 LIVE_SCOPE_METER(cx, --cx->runtime->liveScopeProps);
1527
1528 /* Update this->lastProp directly, or set its deferred update flag. */
1529 if (sprop == SCOPE_LAST_PROP(this)) {
1530 do {
1531 SCOPE_REMOVE_LAST_PROP(this);
1532 if (!hadMiddleDelete())
1533 break;
1534 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 }
1541 generateOwnShape(cx);
1542 CHECK_ANCESTOR_LINE(this, true);
1543
1544 /* 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 METER(shrinks);
1548 (void) changeTable(cx, -1);
1549 }
1550
1551 return true;
1552 }
1553
1554 void
1555 JSScope::clear(JSContext *cx)
1556 {
1557 CHECK_ANCESTOR_LINE(this, true);
1558 LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= entryCount);
1559
1560 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 JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1580 }
1581
1582 void
1583 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 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 JSScopeProperty::trace(JSTracer *trc)
1665 {
1666 if (IS_GC_MARKING_TRACER(trc))
1667 flags |= SPROP_MARK;
1668 js_TraceId(trc, id);
1669
1670 #if JS_HAS_GETTER_SETTER
1671 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 }
1676 if (attrs & JSPROP_SETTER) {
1677 JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, this, 1);
1678 JS_CallTracer(trc, js_CastAsObject(setter), JSTRACE_OBJECT);
1679 }
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 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 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 /* The grandparent must have either no kids or chunky kids. */
1890 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 if (!InsertPropertyTreeChild(rt, parent, kid, chunk)) {
1909 /*
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 bool
2031 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 return false;
2037 }
2038 JS_INIT_ARENA_POOL(&rt->propertyArenaPool, "properties",
2039 256 * sizeof(JSScopeProperty), sizeof(void *), NULL);
2040 return true;
2041 }
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