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

Contents of /trunk/js/jsscope.cpp

Parent Directory Parent Directory | Revision Log Revision Log


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

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

  ViewVC Help
Powered by ViewVC 1.1.24