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

Contents of /trunk/js/jsscope.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 332 - (show annotations)
Thu Oct 23 19:03:33 2008 UTC (11 years, 11 months ago) by siliconforks
File size: 67855 byte(s)
Add SpiderMonkey from Firefox 3.1b1.

The following directories and files were removed:
correct/, correct.js
liveconnect/
nanojit/
t/
v8/
vprof/
xpconnect/
all JavaScript files (Y.js, call.js, if.js, math-partial-sums.js, md5.js, perfect.js, trace-test.js, trace.js)


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
813 rt = cx->runtime;
814 if (!parent) {
815 JS_LOCK_GC(rt);
816
817 table = &rt->propertyTreeHash;
818 entry = (JSPropertyTreeEntry *)
819 JS_DHashTableOperate(table, child, JS_DHASH_ADD);
820 if (!entry)
821 goto out_of_memory;
822
823 sprop = entry->child;
824 if (sprop)
825 goto out;
826 } else {
827 /*
828 * Because chunks are appended at the end and never deleted except by
829 * the GC, we can search without taking the runtime's GC lock. We may
830 * miss a matching sprop added by another thread, and make a duplicate
831 * one, but that is an unlikely, therefore small, cost. The property
832 * tree has extremely low fan-out below its root in popular embeddings
833 * with real-world workloads.
834 *
835 * Patterns such as defining closures that capture a constructor's
836 * environment as getters or setters on the new object that is passed
837 * in as |this| can significantly increase fan-out below the property
838 * tree root -- see bug 335700 for details.
839 */
840 entry = NULL;
841 sprop = parent->kids;
842 if (sprop) {
843 if (KIDS_IS_CHUNKY(sprop)) {
844 chunk = KIDS_TO_CHUNK(sprop);
845
846 table = chunk->table;
847 if (table) {
848 JS_LOCK_GC(rt);
849 entry = (JSPropertyTreeEntry *)
850 JS_DHashTableOperate(table, child, JS_DHASH_LOOKUP);
851 sprop = entry->child;
852 if (sprop) {
853 JS_UNLOCK_GC(rt);
854 return sprop;
855 }
856 goto locked_not_found;
857 }
858
859 n = 0;
860 do {
861 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
862 sprop = chunk->kids[i];
863 if (!sprop) {
864 n += i;
865 if (n >= CHUNK_HASH_THRESHOLD) {
866 chunk = KIDS_TO_CHUNK(parent->kids);
867 if (!chunk->table) {
868 table = HashChunks(chunk, n);
869 JS_LOCK_GC(rt);
870 if (!table)
871 goto out_of_memory;
872 if (chunk->table)
873 JS_DHashTableDestroy(table);
874 else
875 chunk->table = table;
876 goto locked_not_found;
877 }
878 }
879 goto not_found;
880 }
881
882 if (SPROP_MATCH(sprop, child))
883 return sprop;
884 }
885 n += MAX_KIDS_PER_CHUNK;
886 } while ((chunk = chunk->next) != NULL);
887 } else {
888 if (SPROP_MATCH(sprop, child))
889 return sprop;
890 }
891 }
892
893 not_found:
894 JS_LOCK_GC(rt);
895 }
896
897 locked_not_found:
898 sprop = NewScopeProperty(rt);
899 if (!sprop)
900 goto out_of_memory;
901
902 sprop->id = child->id;
903 sprop->getter = child->getter;
904 sprop->setter = child->setter;
905 sprop->slot = child->slot;
906 sprop->attrs = child->attrs;
907 sprop->flags = child->flags;
908 sprop->shortid = child->shortid;
909 sprop->parent = sprop->kids = NULL;
910 sprop->shape = js_GenerateShape(cx, JS_TRUE);
911
912 if (!parent) {
913 entry->child = sprop;
914 } else {
915 if (!InsertPropertyTreeChild(rt, parent, sprop, NULL))
916 goto out_of_memory;
917 }
918
919 out:
920 JS_UNLOCK_GC(rt);
921 return sprop;
922
923 out_of_memory:
924 JS_UNLOCK_GC(rt);
925 JS_ReportOutOfMemory(cx);
926 return NULL;
927 }
928
929 #ifdef DEBUG_notbrendan
930 #define CHECK_ANCESTOR_LINE(scope, sparse) \
931 JS_BEGIN_MACRO \
932 if ((scope)->table) CheckAncestorLine(scope, sparse); \
933 JS_END_MACRO
934
935 static void
936 CheckAncestorLine(JSScope *scope, JSBool sparse)
937 {
938 uint32 size;
939 JSScopeProperty **spp, **start, **end, *ancestorLine, *sprop, *aprop;
940 uint32 entryCount, ancestorCount;
941
942 ancestorLine = SCOPE_LAST_PROP(scope);
943 if (ancestorLine)
944 JS_ASSERT(SCOPE_HAS_PROPERTY(scope, ancestorLine));
945
946 entryCount = 0;
947 size = SCOPE_CAPACITY(scope);
948 start = scope->table;
949 for (spp = start, end = start + size; spp < end; spp++) {
950 sprop = SPROP_FETCH(spp);
951 if (sprop) {
952 entryCount++;
953 for (aprop = ancestorLine; aprop; aprop = aprop->parent) {
954 if (aprop == sprop)
955 break;
956 }
957 JS_ASSERT(aprop);
958 }
959 }
960 JS_ASSERT(entryCount == scope->entryCount);
961
962 ancestorCount = 0;
963 for (sprop = ancestorLine; sprop; sprop = sprop->parent) {
964 if (SCOPE_HAD_MIDDLE_DELETE(scope) &&
965 !SCOPE_HAS_PROPERTY(scope, sprop)) {
966 JS_ASSERT(sparse);
967 continue;
968 }
969 ancestorCount++;
970 }
971 JS_ASSERT(ancestorCount == scope->entryCount);
972 }
973 #else
974 #define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
975 #endif
976
977 static void
978 ReportReadOnlyScope(JSContext *cx, JSScope *scope)
979 {
980 JSString *str;
981 const char *bytes;
982
983 str = js_ValueToString(cx, OBJECT_TO_JSVAL(scope->object));
984 if (!str)
985 return;
986 bytes = js_GetStringBytes(cx, str);
987 if (!bytes)
988 return;
989 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_READ_ONLY, bytes);
990 }
991
992 JSScopeProperty *
993 js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
994 JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
995 uintN attrs, uintN flags, intN shortid)
996 {
997 JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child;
998 uint32 size, splen, i;
999 int change;
1000 JSTempValueRooter tvr;
1001
1002 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
1003 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1004
1005 /*
1006 * You can't add properties to a sealed scope. But note well that you can
1007 * change property attributes in a sealed scope, even though that replaces
1008 * a JSScopeProperty * in the scope's hash table -- but no id is added, so
1009 * the scope remains sealed.
1010 */
1011 if (SCOPE_IS_SEALED(scope)) {
1012 ReportReadOnlyScope(cx, scope);
1013 return NULL;
1014 }
1015
1016 /*
1017 * Normalize stub getter and setter values for faster is-stub testing in
1018 * the SPROP_CALL_[GS]ETTER macros.
1019 */
1020 if (getter == JS_PropertyStub)
1021 getter = NULL;
1022 if (setter == JS_PropertyStub)
1023 setter = NULL;
1024
1025 /*
1026 * Search for id in order to claim its entry, allocating a property tree
1027 * node if one doesn't already exist for our parameters.
1028 */
1029 spp = js_SearchScope(scope, id, JS_TRUE);
1030 sprop = overwriting = SPROP_FETCH(spp);
1031 if (!sprop) {
1032 JS_COUNT_OPERATION(cx, JSOW_NEW_PROPERTY);
1033
1034 /* Check whether we need to grow, if the load factor is >= .75. */
1035 size = SCOPE_CAPACITY(scope);
1036 if (scope->entryCount + scope->removedCount >= size - (size >> 2)) {
1037 if (scope->removedCount >= size >> 2) {
1038 METER(compresses);
1039 change = 0;
1040 } else {
1041 METER(grows);
1042 change = 1;
1043 }
1044 if (!ChangeScope(cx, scope, change) &&
1045 scope->entryCount + scope->removedCount == size - 1) {
1046 METER(addFailures);
1047 return NULL;
1048 }
1049 spp = js_SearchScope(scope, id, JS_TRUE);
1050 JS_ASSERT(!SPROP_FETCH(spp));
1051 }
1052 } else {
1053 /* Property exists: js_SearchScope must have returned a valid entry. */
1054 JS_ASSERT(!SPROP_IS_REMOVED(*spp));
1055
1056 /*
1057 * If all property members match, this is a redundant add and we can
1058 * return early. If the caller wants to allocate a slot, but doesn't
1059 * care which slot, copy sprop->slot into slot so we can match sprop,
1060 * if all other members match.
1061 */
1062 if (!(attrs & JSPROP_SHARED) &&
1063 slot == SPROP_INVALID_SLOT &&
1064 SPROP_HAS_VALID_SLOT(sprop, scope)) {
1065 slot = sprop->slot;
1066 }
1067 if (SPROP_MATCH_PARAMS_AFTER_ID(sprop, getter, setter, slot, attrs,
1068 flags, shortid)) {
1069 METER(redundantAdds);
1070 return sprop;
1071 }
1072
1073 /*
1074 * If we are clearing sprop to force an existing property to be
1075 * overwritten (apart from a duplicate formal parameter), we must
1076 * unlink it from the ancestor line at scope->lastProp, lazily if
1077 * sprop is not lastProp. And we must remove the entry at *spp,
1078 * precisely so the lazy "middle delete" fixup code further below
1079 * won't find sprop in scope->table, in spite of sprop being on
1080 * the ancestor line.
1081 *
1082 * When we finally succeed in finding or creating a new sprop
1083 * and storing its pointer at *spp, we'll use the |overwriting|
1084 * local saved when we first looked up id to decide whether we're
1085 * indeed creating a new entry, or merely overwriting an existing
1086 * property.
1087 */
1088 if (sprop == SCOPE_LAST_PROP(scope)) {
1089 do {
1090 SCOPE_REMOVE_LAST_PROP(scope);
1091 if (!SCOPE_HAD_MIDDLE_DELETE(scope))
1092 break;
1093 sprop = SCOPE_LAST_PROP(scope);
1094 } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
1095 } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
1096 /*
1097 * If we have no hash table yet, we need one now. The middle
1098 * delete code is simple-minded that way!
1099 */
1100 if (!scope->table) {
1101 if (!CreateScopeTable(cx, scope, JS_TRUE))
1102 return NULL;
1103 spp = js_SearchScope(scope, id, JS_TRUE);
1104 sprop = overwriting = SPROP_FETCH(spp);
1105 }
1106 SCOPE_SET_MIDDLE_DELETE(scope);
1107 }
1108 SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1109
1110 /*
1111 * If we fail later on trying to find or create a new sprop, we will
1112 * goto fail_overwrite and restore *spp from |overwriting|. Note that
1113 * we don't bother to keep scope->removedCount in sync, because we'll
1114 * fix up *spp and scope->entryCount shortly, no matter how control
1115 * flow returns from this function.
1116 */
1117 if (scope->table)
1118 SPROP_STORE_PRESERVING_COLLISION(spp, NULL);
1119 scope->entryCount--;
1120 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1121 sprop = NULL;
1122 }
1123
1124 if (!sprop) {
1125 /*
1126 * If properties were deleted from the middle of the list starting at
1127 * scope->lastProp, we may need to fork the property tree and squeeze
1128 * all deleted properties out of scope's ancestor line. Otherwise we
1129 * risk adding a node with the same id as a "middle" node, violating
1130 * the rule that properties along an ancestor line have distinct ids.
1131 */
1132 if (SCOPE_HAD_MIDDLE_DELETE(scope)) {
1133 JS_ASSERT(scope->table);
1134 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1135
1136 splen = scope->entryCount;
1137 if (splen == 0) {
1138 JS_ASSERT(scope->lastProp == NULL);
1139 } else {
1140 /*
1141 * Enumerate live entries in scope->table using a temporary
1142 * vector, by walking the (possibly sparse, due to deletions)
1143 * ancestor line from scope->lastProp.
1144 */
1145 spvec = (JSScopeProperty **)
1146 JS_malloc(cx, SCOPE_TABLE_NBYTES(splen));
1147 if (!spvec)
1148 goto fail_overwrite;
1149 i = splen;
1150 sprop = SCOPE_LAST_PROP(scope);
1151 JS_ASSERT(sprop);
1152 do {
1153 /*
1154 * NB: test SCOPE_GET_PROPERTY, not SCOPE_HAS_PROPERTY --
1155 * the latter insists that sprop->id maps to sprop, while
1156 * the former simply tests whether sprop->id is bound in
1157 * scope. We must allow for duplicate formal parameters
1158 * along the ancestor line, and fork them as needed.
1159 */
1160 if (!SCOPE_GET_PROPERTY(scope, sprop->id))
1161 continue;
1162
1163 JS_ASSERT(sprop != overwriting);
1164 if (i == 0) {
1165 /*
1166 * If our original splen estimate, scope->entryCount,
1167 * is less than the ancestor line height, there must
1168 * be duplicate formal parameters in this (function
1169 * object) scope. Count remaining ancestors in order
1170 * to realloc spvec.
1171 */
1172 JSScopeProperty *tmp = sprop;
1173 do {
1174 if (SCOPE_GET_PROPERTY(scope, tmp->id))
1175 i++;
1176 } while ((tmp = tmp->parent) != NULL);
1177 spp2 = (JSScopeProperty **)
1178 JS_realloc(cx, spvec, SCOPE_TABLE_NBYTES(splen+i));
1179 if (!spp2) {
1180 JS_free(cx, spvec);
1181 goto fail_overwrite;
1182 }
1183
1184 spvec = spp2;
1185 memmove(spvec + i, spvec, SCOPE_TABLE_NBYTES(splen));
1186 splen += i;
1187 }
1188
1189 spvec[--i] = sprop;
1190 } while ((sprop = sprop->parent) != NULL);
1191 JS_ASSERT(i == 0);
1192
1193 /*
1194 * Now loop forward through spvec, forking the property tree
1195 * whenever we see a "parent gap" due to deletions from scope.
1196 * NB: sprop is null on first entry to the loop body.
1197 */
1198 do {
1199 if (spvec[i]->parent == sprop) {
1200 sprop = spvec[i];
1201 } else {
1202 sprop = GetPropertyTreeChild(cx, sprop, spvec[i]);
1203 if (!sprop) {
1204 JS_free(cx, spvec);
1205 goto fail_overwrite;
1206 }
1207
1208 spp2 = js_SearchScope(scope, sprop->id, JS_FALSE);
1209 JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]);
1210 SPROP_STORE_PRESERVING_COLLISION(spp2, sprop);
1211 }
1212 } while (++i < splen);
1213 JS_free(cx, spvec);
1214
1215 /*
1216 * Now sprop points to the last property in scope, where the
1217 * ancestor line from sprop to the root is dense w.r.t. scope:
1218 * it contains no nodes not mapped by scope->table, apart from
1219 * any stinking ECMA-mandated duplicate formal parameters.
1220 */
1221 scope->lastProp = sprop;
1222 CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1223 JS_RUNTIME_METER(cx->runtime, middleDeleteFixups);
1224 }
1225
1226 SCOPE_CLR_MIDDLE_DELETE(scope);
1227 }
1228
1229 /*
1230 * Aliases share another property's slot, passed in the |slot| param.
1231 * Shared properties have no slot. Unshared properties that do not
1232 * alias another property's slot get one here, but may lose it due to
1233 * a JS_ClearScope call.
1234 */
1235 if (!(flags & SPROP_IS_ALIAS)) {
1236 if (attrs & JSPROP_SHARED) {
1237 slot = SPROP_INVALID_SLOT;
1238 } else {
1239 /*
1240 * We may have set slot from a nearly-matching sprop, above.
1241 * If so, we're overwriting that nearly-matching sprop, so we
1242 * can reuse its slot -- we don't need to allocate a new one.
1243 * Similarly, we use a specific slot if provided by the caller.
1244 */
1245 if (slot == SPROP_INVALID_SLOT &&
1246 !js_AllocSlot(cx, scope->object, &slot)) {
1247 goto fail_overwrite;
1248 }
1249 }
1250 }
1251
1252 /*
1253 * Check for a watchpoint on a deleted property; if one exists, change
1254 * setter to js_watch_set.
1255 * XXXbe this could get expensive with lots of watchpoints...
1256 */
1257 if (!JS_CLIST_IS_EMPTY(&cx->runtime->watchPointList) &&
1258 js_FindWatchPoint(cx->runtime, scope, id)) {
1259 JS_PUSH_TEMP_ROOT_SPROP(cx, overwriting, &tvr);
1260 setter = js_WrapWatchedSetter(cx, id, attrs, setter);
1261 JS_POP_TEMP_ROOT(cx, &tvr);
1262 if (!setter)
1263 goto fail_overwrite;
1264 }
1265
1266 /* Find or create a property tree node labeled by our arguments. */
1267 child.id = id;
1268 child.getter = getter;
1269 child.setter = setter;
1270 child.slot = slot;
1271 child.attrs = attrs;
1272 child.flags = flags;
1273 child.shortid = shortid;
1274 sprop = GetPropertyTreeChild(cx, scope->lastProp, &child);
1275 if (!sprop)
1276 goto fail_overwrite;
1277
1278 /*
1279 * The scope's shape defaults to its last property's shape, but may
1280 * be regenerated later as the scope diverges (from the property cache
1281 * point of view) from the structural type associated with sprop.
1282 */
1283 SCOPE_EXTEND_SHAPE(cx, scope, sprop);
1284
1285 /* Store the tree node pointer in the table entry for id. */
1286 if (scope->table)
1287 SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
1288 scope->entryCount++;
1289 scope->lastProp = sprop;
1290 CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1291 #ifdef DEBUG
1292 if (!overwriting) {
1293 LIVE_SCOPE_METER(cx, ++cx->runtime->liveScopeProps);
1294 JS_RUNTIME_METER(cx->runtime, totalScopeProps);
1295 }
1296 #endif
1297
1298 /*
1299 * If we reach the hashing threshold, try to allocate scope->table.
1300 * If we can't (a rare event, preceded by swapping to death on most
1301 * modern OSes), stick with linear search rather than whining about
1302 * this little set-back. Therefore we must test !scope->table and
1303 * scope->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
1304 * entry count just reached the threshold.
1305 */
1306 if (!scope->table && scope->entryCount >= SCOPE_HASH_THRESHOLD)
1307 (void) CreateScopeTable(cx, scope, JS_FALSE);
1308 }
1309
1310 METER(adds);
1311 return sprop;
1312
1313 fail_overwrite:
1314 if (overwriting) {
1315 /*
1316 * We may or may not have forked overwriting out of scope's ancestor
1317 * line, so we must check (the alternative is to set a flag above, but
1318 * that hurts the common, non-error case). If we did fork overwriting
1319 * out, we'll add it back at scope->lastProp. This means enumeration
1320 * order can change due to a failure to overwrite an id.
1321 * XXXbe very minor incompatibility
1322 */
1323 for (sprop = SCOPE_LAST_PROP(scope); ; sprop = sprop->parent) {
1324 if (!sprop) {
1325 sprop = SCOPE_LAST_PROP(scope);
1326 if (overwriting->parent == sprop) {
1327 scope->lastProp = overwriting;
1328 } else {
1329 sprop = GetPropertyTreeChild(cx, sprop, overwriting);
1330 if (sprop) {
1331 JS_ASSERT(sprop != overwriting);
1332 scope->lastProp = sprop;
1333 }
1334 overwriting = sprop;
1335 }
1336 break;
1337 }
1338 if (sprop == overwriting)
1339 break;
1340 }
1341 if (overwriting) {
1342 if (scope->table)
1343 SPROP_STORE_PRESERVING_COLLISION(spp, overwriting);
1344 scope->entryCount++;
1345 }
1346 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1347 }
1348 METER(addFailures);
1349 return NULL;
1350 }
1351
1352 JSScopeProperty *
1353 js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
1354 JSScopeProperty *sprop, uintN attrs, uintN mask,
1355 JSPropertyOp getter, JSPropertyOp setter)
1356 {
1357 JSScopeProperty child, *newsprop, **spp;
1358
1359 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1360
1361 /* Allow only shared (slot-less) => unshared (slot-full) transition. */
1362 attrs |= sprop->attrs & mask;
1363 JS_ASSERT(!((attrs ^ sprop->attrs) & JSPROP_SHARED) ||
1364 !(attrs & JSPROP_SHARED));
1365 if (getter == JS_PropertyStub)
1366 getter = NULL;
1367 if (setter == JS_PropertyStub)
1368 setter = NULL;
1369 if (sprop->attrs == attrs &&
1370 sprop->getter == getter &&
1371 sprop->setter == setter) {
1372 return sprop;
1373 }
1374
1375 child.id = sprop->id;
1376 child.getter = getter;
1377 child.setter = setter;
1378 child.slot = sprop->slot;
1379 child.attrs = attrs;
1380 child.flags = sprop->flags;
1381 child.shortid = sprop->shortid;
1382
1383 if (SCOPE_LAST_PROP(scope) == sprop) {
1384 /*
1385 * Optimize the case where the last property added to scope is changed
1386 * to have a different attrs, getter, or setter. In the last property
1387 * case, we need not fork the property tree. But since we do not call
1388 * js_AddScopeProperty, we may need to allocate a new slot directly.
1389 */
1390 if ((sprop->attrs & JSPROP_SHARED) && !(attrs & JSPROP_SHARED)) {
1391 JS_ASSERT(child.slot == SPROP_INVALID_SLOT);
1392 if (!js_AllocSlot(cx, scope->object, &child.slot))
1393 return NULL;
1394 }
1395
1396 newsprop = GetPropertyTreeChild(cx, sprop->parent, &child);
1397 if (newsprop) {
1398 spp = js_SearchScope(scope, sprop->id, JS_FALSE);
1399 JS_ASSERT(SPROP_FETCH(spp) == sprop);
1400
1401 if (scope->table)
1402 SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
1403 scope->lastProp = newsprop;
1404 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1405 }
1406 } else {
1407 /*
1408 * Let js_AddScopeProperty handle this |overwriting| case, including
1409 * the conservation of sprop->slot (if it's valid). We must not call
1410 * js_RemoveScopeProperty here, it will free a valid sprop->slot and
1411 * js_AddScopeProperty won't re-allocate it.
1412 */
1413 newsprop = js_AddScopeProperty(cx, scope, child.id,
1414 child.getter, child.setter, child.slot,
1415 child.attrs, child.flags, child.shortid);
1416 }
1417
1418 if (newsprop) {
1419 if (scope->shape == sprop->shape)
1420 scope->shape = newsprop->shape;
1421 else
1422 SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1423 }
1424 #ifdef JS_DUMP_PROPTREE_STATS
1425 else
1426 METER(changeFailures);
1427 #endif
1428 return newsprop;
1429 }
1430
1431 JSBool
1432 js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id)
1433 {
1434 JSScopeProperty **spp, *stored, *sprop;
1435 uint32 size;
1436
1437 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
1438 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1439 if (SCOPE_IS_SEALED(scope)) {
1440 ReportReadOnlyScope(cx, scope);
1441 return JS_FALSE;
1442 }
1443 METER(removes);
1444
1445 spp = js_SearchScope(scope, id, JS_FALSE);
1446 stored = *spp;
1447 sprop = SPROP_CLEAR_COLLISION(stored);
1448 if (!sprop) {
1449 METER(uselessRemoves);
1450 return JS_TRUE;
1451 }
1452
1453 /* Convert from a list to a hash so we can handle "middle deletes". */
1454 if (!scope->table && sprop != scope->lastProp) {
1455 if (!CreateScopeTable(cx, scope, JS_TRUE))
1456 return JS_FALSE;
1457 spp = js_SearchScope(scope, id, JS_FALSE);
1458 stored = *spp;
1459 sprop = SPROP_CLEAR_COLLISION(stored);
1460 }
1461
1462 /* First, if sprop is unshared and not cleared, free its slot number. */
1463 if (SPROP_HAS_VALID_SLOT(sprop, scope)) {
1464 js_FreeSlot(cx, scope->object, sprop->slot);
1465 JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1466 }
1467
1468 /* Next, remove id by setting its entry to a removed or free sentinel. */
1469 if (SPROP_HAD_COLLISION(stored)) {
1470 JS_ASSERT(scope->table);
1471 *spp = SPROP_REMOVED;
1472 scope->removedCount++;
1473 } else {
1474 METER(removeFrees);
1475 if (scope->table)
1476 *spp = NULL;
1477 }
1478 scope->entryCount--;
1479 LIVE_SCOPE_METER(cx, --cx->runtime->liveScopeProps);
1480
1481 /* Update scope->lastProp directly, or set its deferred update flag. */
1482 if (sprop == SCOPE_LAST_PROP(scope)) {
1483 do {
1484 SCOPE_REMOVE_LAST_PROP(scope);
1485 if (!SCOPE_HAD_MIDDLE_DELETE(scope))
1486 break;
1487 sprop = SCOPE_LAST_PROP(scope);
1488 } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
1489 } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
1490 SCOPE_SET_MIDDLE_DELETE(scope);
1491 }
1492 SCOPE_MAKE_UNIQUE_SHAPE(cx, scope);
1493 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1494
1495 /* Last, consider shrinking scope's table if its load factor is <= .25. */
1496 size = SCOPE_CAPACITY(scope);
1497 if (size > MIN_SCOPE_SIZE && scope->entryCount <= size >> 2) {
1498 METER(shrinks);
1499 (void) ChangeScope(cx, scope, -1);
1500 }
1501
1502 return JS_TRUE;
1503 }
1504
1505 void
1506 js_ClearScope(JSContext *cx, JSScope *scope)
1507 {
1508 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1509 LIVE_SCOPE_METER(cx, cx->runtime->liveScopeProps -= scope->entryCount);
1510
1511 if (scope->table)
1512 free(scope->table);
1513 SCOPE_CLR_MIDDLE_DELETE(scope);
1514 InitMinimalScope(scope);
1515 JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1516 }
1517
1518 void
1519 js_TraceId(JSTracer *trc, jsid id)
1520 {
1521 jsval v;
1522
1523 v = ID_TO_VALUE(id);
1524 JS_CALL_VALUE_TRACER(trc, v, "id");
1525 }
1526
1527 #ifdef DEBUG
1528 static void
1529 PrintPropertyGetterOrSetter(JSTracer *trc, char *buf, size_t bufsize)
1530 {
1531 JSScopeProperty *sprop;
1532 jsid id;
1533 size_t n;
1534 const char *name;
1535
1536 JS_ASSERT(trc->debugPrinter == PrintPropertyGetterOrSetter);
1537 sprop = (JSScopeProperty *)trc->debugPrintArg;
1538 id = sprop->id;
1539 name = trc->debugPrintIndex ? js_setter_str : js_getter_str;
1540
1541 if (JSID_IS_ATOM(id)) {
1542 n = js_PutEscapedString(buf, bufsize - 1,
1543 ATOM_TO_STRING(JSID_TO_ATOM(id)), 0);
1544 if (n < bufsize - 1)
1545 JS_snprintf(buf + n, bufsize - n, " %s", name);
1546 } else if (JSID_IS_INT(sprop->id)) {
1547 JS_snprintf(buf, bufsize, "%d %s", JSID_TO_INT(id), name);
1548 } else {
1549 JS_snprintf(buf, bufsize, "<object> %s", name);
1550 }
1551 }
1552 #endif
1553
1554
1555 void
1556 js_TraceScopeProperty(JSTracer *trc, JSScopeProperty *sprop)
1557 {
1558 if (IS_GC_MARKING_TRACER(trc))
1559 sprop->flags |= SPROP_MARK;
1560 TRACE_ID(trc, sprop->id);
1561
1562 #if JS_HAS_GETTER_SETTER
1563 if (sprop->attrs & (JSPROP_GETTER | JSPROP_SETTER)) {
1564 if (sprop->attrs & JSPROP_GETTER) {
1565 JS_ASSERT(JSVAL_IS_OBJECT((jsval) sprop->getter));
1566 JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, sprop, 0);
1567 JS_CallTracer(trc, JSVAL_TO_OBJECT((jsval) sprop->getter),
1568 JSTRACE_OBJECT);
1569 }
1570 if (sprop->attrs & JSPROP_SETTER) {
1571 JS_ASSERT(JSVAL_IS_OBJECT((jsval) sprop->setter));
1572 JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, sprop, 1);
1573 JS_CallTracer(trc, JSVAL_TO_OBJECT((jsval) sprop->setter),
1574 JSTRACE_OBJECT);
1575 }
1576 }
1577 #endif /* JS_HAS_GETTER_SETTER */
1578 }
1579
1580 #ifdef JS_DUMP_PROPTREE_STATS
1581
1582 #include <stdio.h>
1583
1584 static void
1585 MeterKidCount(JSBasicStats *bs, uintN nkids)
1586 {
1587 JS_BASIC_STATS_ACCUM(bs, nkids);
1588 bs->hist[JS_MIN(nkids, 10)]++;
1589 }
1590
1591 static void
1592 MeterPropertyTree(JSBasicStats *bs, JSScopeProperty *node)
1593 {
1594 uintN i, nkids;
1595 JSScopeProperty *kids, *kid;
1596 PropTreeKidsChunk *chunk;
1597
1598 nkids = 0;
1599 kids = node->kids;
1600 if (kids) {
1601 if (KIDS_IS_CHUNKY(kids)) {
1602 for (chunk = KIDS_TO_CHUNK(kids); chunk; chunk = chunk->next) {
1603 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1604 kid = chunk->kids[i];
1605 if (!kid)
1606 break;
1607 MeterPropertyTree(bs, kid);
1608 nkids++;
1609 }
1610 }
1611 } else {
1612 MeterPropertyTree(bs, kids);
1613 nkids = 1;
1614 }
1615 }
1616
1617 MeterKidCount(bs, nkids);
1618 }
1619
1620 static JSDHashOperator
1621 js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
1622 void *arg)
1623 {
1624 JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)hdr;
1625 JSBasicStats *bs = (JSBasicStats *)arg;
1626
1627 MeterPropertyTree(bs, entry->child);
1628 return JS_DHASH_NEXT;
1629 }
1630
1631 static void
1632 DumpSubtree(JSContext *cx, JSScopeProperty *sprop, int level, FILE *fp)
1633 {
1634 jsval v;
1635 JSString *str;
1636 JSScopeProperty *kids, *kid;
1637 PropTreeKidsChunk *chunk;
1638 uintN i;
1639
1640 fprintf(fp, "%*sid ", level, "");
1641 v = ID_TO_VALUE(sprop->id);
1642 if (JSID_IS_INT(sprop->id)) {
1643 fprintf(fp, "%d", JSVAL_TO_INT(v));
1644 } else {
1645 if (JSID_IS_ATOM(sprop->id)) {
1646 str = JSVAL_TO_STRING(v);
1647 } else {
1648 JS_ASSERT(JSID_IS_OBJECT(sprop->id));
1649 str = js_ValueToString(cx, v);
1650 fputs("object ", fp);
1651 }
1652 if (!str)
1653 fputs("<error>", fp);
1654 else
1655 js_FileEscapedString(fp, str, '"');
1656 }
1657
1658 fprintf(fp, " g/s %p/%p slot %u attrs %x flags %x shortid %d\n",
1659 (void *) sprop->getter, (void *) sprop->setter, sprop->slot,
1660 sprop->attrs, sprop->flags, sprop->shortid);
1661 kids = sprop->kids;
1662 if (kids) {
1663 ++level;
1664 if (KIDS_IS_CHUNKY(kids)) {
1665 chunk = KIDS_TO_CHUNK(kids);
1666 do {
1667 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1668 kid = chunk->kids[i];
1669 if (!kid)
1670 break;
1671 JS_ASSERT(kid->parent == sprop);
1672 DumpSubtree(cx, kid, level, fp);
1673 }
1674 } while ((chunk = chunk->next) != NULL);
1675 } else {
1676 kid = kids;
1677 DumpSubtree(cx, kid, level, fp);
1678 }
1679 }
1680 }
1681
1682 #endif /* JS_DUMP_PROPTREE_STATS */
1683
1684 void
1685 js_SweepScopeProperties(JSContext *cx)
1686 {
1687 JSRuntime *rt = cx->runtime;
1688 JSArena **ap, *a;
1689 JSScopeProperty *limit, *sprop, *parent, *kids, *kid;
1690 uintN liveCount;
1691 PropTreeKidsChunk *chunk, *nextChunk, *freeChunk;
1692 uintN i;
1693
1694 #ifdef JS_DUMP_PROPTREE_STATS
1695 JSBasicStats bs;
1696 uint32 livePropCapacity = 0, totalLiveCount = 0;
1697 static FILE *logfp;
1698 if (!logfp)
1699 logfp = fopen("/tmp/proptree.stats", "w");
1700
1701 JS_BASIC_STATS_INIT(&bs);
1702 MeterKidCount(&bs, rt->propertyTreeHash.entryCount);
1703 JS_DHashTableEnumerate(&rt->propertyTreeHash, js_MeterPropertyTree, &bs);
1704
1705 {
1706 double props, nodes, mean, sigma;
1707
1708 props = rt->liveScopePropsPreSweep;
1709 nodes = rt->livePropTreeNodes;
1710 JS_ASSERT(nodes == bs.sum);
1711 mean = JS_MeanAndStdDevBS(&bs, &sigma);
1712
1713 fprintf(logfp,
1714 "props %g nodes %g beta %g meankids %g sigma %g max %u\n",
1715 props, nodes, nodes / props, mean, sigma, bs.max);
1716 }
1717
1718 JS_DumpHistogram(&bs, logfp);
1719 #endif
1720
1721 ap = &rt->propertyArenaPool.first.next;
1722 while ((a = *ap) != NULL) {
1723 limit = (JSScopeProperty *) a->avail;
1724 liveCount = 0;
1725 for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) {
1726 /* If the id is null, sprop is already on the freelist. */
1727 if (sprop->id == JSVAL_NULL)
1728 continue;
1729
1730 /*
1731 * If the mark bit is set, sprop is alive, so clear the mark bit
1732 * and continue the while loop.
1733 *
1734 * Regenerate sprop->shape if it hasn't already been refreshed
1735 * during the mark phase, when live scopes' lastProp members are
1736 * followed to update both scope->shape and lastProp->shape.
1737 */
1738 if (sprop->flags & SPROP_MARK) {
1739 sprop->flags &= ~SPROP_MARK;
1740 if (sprop->flags & SPROP_FLAG_SHAPE_REGEN) {
1741 sprop->flags &= ~SPROP_FLAG_SHAPE_REGEN;
1742 } else {
1743 sprop->shape = ++cx->runtime->shapeGen;
1744 JS_ASSERT(sprop->shape != 0);
1745 }
1746 liveCount++;
1747 continue;
1748 }
1749
1750 /* Ok, sprop is garbage to collect: unlink it from its parent. */
1751 freeChunk = RemovePropertyTreeChild(rt, sprop);
1752
1753 /*
1754 * Take care to reparent all sprop's kids to their grandparent.
1755 * InsertPropertyTreeChild can potentially fail for two reasons:
1756 *
1757 * 1. If parent is null, insertion into the root property hash
1758 * table may fail. We are forced to leave the kid out of the
1759 * table (as can already happen with duplicates) but ensure
1760 * that the kid's parent pointer is set to null.
1761 *
1762 * 2. If parent is non-null, allocation of a new KidsChunk can
1763 * fail. To prevent this from happening, we allow sprops's own
1764 * chunks to be reused by the grandparent, which removes the
1765 * need for InsertPropertyTreeChild to malloc a new KidsChunk.
1766 *
1767 * If sprop does not have chunky kids, then we rely on the
1768 * RemovePropertyTreeChild call above (which removed sprop from
1769 * its parent) either leaving one free entry, or else returning
1770 * the now-unused chunk to us so we can reuse it.
1771 *
1772 * We also require the grandparent to have either no kids or else
1773 * chunky kids. A single non-chunky kid would force a new chunk to
1774 * be malloced in some cases (if sprop had a single non-chunky
1775 * kid, or a multiple of MAX_KIDS_PER_CHUNK kids). Note that
1776 * RemovePropertyTreeChild never converts a single-entry chunky
1777 * kid back to a non-chunky kid, so we are assured of correct
1778 * behaviour.
1779 */
1780 kids = sprop->kids;
1781 if (kids) {
1782 sprop->kids = NULL;
1783 parent = sprop->parent;
1784
1785 /* Assert that grandparent has no kids or chunky kids. */
1786 JS_ASSERT(!parent || !parent->kids ||
1787 KIDS_IS_CHUNKY(parent->kids));
1788 if (KIDS_IS_CHUNKY(kids)) {
1789 chunk = KIDS_TO_CHUNK(kids);
1790 do {
1791 nextChunk = chunk->next;
1792 chunk->next = NULL;
1793 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1794 kid = chunk->kids[i];
1795 if (!kid)
1796 break;
1797 JS_ASSERT(kid->parent == sprop);
1798
1799 /*
1800 * Clear a space in the kids array for possible
1801 * re-use by InsertPropertyTreeChild.
1802 */
1803 chunk->kids[i] = NULL;
1804 if (!InsertPropertyTreeChild(rt, parent, kid,
1805 chunk)) {
1806 /*
1807 * This can happen only if we failed to add an
1808 * entry to the root property hash table.
1809 */
1810 JS_ASSERT(!parent);
1811 kid->parent = NULL;
1812 }
1813 }
1814 if (!chunk->kids[0]) {
1815 /* The chunk wasn't reused, so we must free it. */
1816 DestroyPropTreeKidsChunk(rt, chunk);
1817 }
1818 } while ((chunk = nextChunk) != NULL);
1819 } else {
1820 kid = kids;
1821 if (!InsertPropertyTreeChild(rt, parent, kid, freeChunk)) {
1822 /*
1823 * This can happen only if we failed to add an entry
1824 * to the root property hash table.
1825 */
1826 JS_ASSERT(!parent);
1827 kid->parent = NULL;
1828 }
1829 }
1830 }
1831
1832 if (freeChunk && !freeChunk->kids[0]) {
1833 /* The chunk wasn't reused, so we must free it. */
1834 DestroyPropTreeKidsChunk(rt, freeChunk);
1835 }
1836
1837 /* Clear id so we know (above) that sprop is on the freelist. */
1838 sprop->id = JSVAL_NULL;
1839 FREENODE_INSERT(rt->propertyFreeList, sprop);
1840 JS_RUNTIME_UNMETER(rt, livePropTreeNodes);
1841 }
1842
1843 /* If a contains no live properties, return it to the malloc heap. */
1844 if (liveCount == 0) {
1845 for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++)
1846 FREENODE_REMOVE(sprop);
1847 JS_ARENA_DESTROY(&rt->propertyArenaPool, a, ap);
1848 } else {
1849 #ifdef JS_DUMP_PROPTREE_STATS
1850 livePropCapacity += limit - (JSScopeProperty *) a->base;
1851 totalLiveCount += liveCount;
1852 #endif
1853 ap = &a->next;
1854 }
1855 }
1856
1857 #ifdef JS_DUMP_PROPTREE_STATS
1858 fprintf(logfp, "arenautil %g%%\n",
1859 (totalLiveCount && livePropCapacity)
1860 ? (totalLiveCount * 100.0) / livePropCapacity
1861 : 0.0);
1862
1863 #define RATE(f1, f2) (((double)js_scope_stats.f1 / js_scope_stats.f2) * 100.0)
1864
1865 fprintf(logfp, "Scope search stats:\n"
1866 " searches: %6u\n"
1867 " hits: %6u %5.2f%% of searches\n"
1868 " misses: %6u %5.2f%%\n"
1869 " hashes: %6u %5.2f%%\n"
1870 " steps: %6u %5.2f%% %5.2f%% of hashes\n"
1871 " stepHits: %6u %5.2f%% %5.2f%%\n"
1872 " stepMisses: %6u %5.2f%% %5.2f%%\n"
1873 " adds: %6u\n"
1874 " redundantAdds: %6u\n"
1875 " addFailures: %6u\n"
1876 " changeFailures: %6u\n"
1877 " compresses: %6u\n"
1878 " grows: %6u\n"
1879 " removes: %6u\n"
1880 " removeFrees: %6u\n"
1881 " uselessRemoves: %6u\n"
1882 " shrinks: %6u\n",
1883 js_scope_stats.searches,
1884 js_scope_stats.hits, RATE(hits, searches),
1885 js_scope_stats.misses, RATE(misses, searches),
1886 js_scope_stats.hashes, RATE(hashes, searches),
1887 js_scope_stats.steps, RATE(steps, searches), RATE(steps, hashes),
1888 js_scope_stats.stepHits,
1889 RATE(stepHits, searches), RATE(stepHits, hashes),
1890 js_scope_stats.stepMisses,
1891 RATE(stepMisses, searches), RATE(stepMisses, hashes),
1892 js_scope_stats.adds,
1893 js_scope_stats.redundantAdds,
1894 js_scope_stats.addFailures,
1895 js_scope_stats.changeFailures,
1896 js_scope_stats.compresses,
1897 js_scope_stats.grows,
1898 js_scope_stats.removes,
1899 js_scope_stats.removeFrees,
1900 js_scope_stats.uselessRemoves,
1901 js_scope_stats.shrinks);
1902
1903 #undef RATE
1904
1905 fflush(logfp);
1906 #endif
1907
1908 #ifdef DUMP_PROPERTY_TREE
1909 {
1910 FILE *dumpfp = fopen("/tmp/proptree.dump", "w");
1911 if (dumpfp) {
1912 JSPropertyTreeEntry *pte, *end;
1913
1914 pte = (JSPropertyTreeEntry *) rt->propertyTreeHash.entryStore;
1915 end = pte + JS_DHASH_TABLE_SIZE(&rt->propertyTreeHash);
1916 while (pte < end) {
1917 if (pte->child)
1918 DumpSubtree(cx, pte->child, 0, dumpfp);
1919 pte++;
1920 }
1921 fclose(dumpfp);
1922 }
1923 }
1924 #endif
1925 }
1926
1927 JSBool
1928 js_InitPropertyTree(JSRuntime *rt)
1929 {
1930 if (!JS_DHashTableInit(&rt->propertyTreeHash, &PropertyTreeHashOps, NULL,
1931 sizeof(JSPropertyTreeEntry), JS_DHASH_MIN_SIZE)) {
1932 rt->propertyTreeHash.ops = NULL;
1933 return JS_FALSE;
1934 }
1935 JS_INIT_ARENA_POOL(&rt->propertyArenaPool, "properties",
1936 256 * sizeof(JSScopeProperty), sizeof(void *), NULL);
1937 return JS_TRUE;
1938 }
1939
1940 void
1941 js_FinishPropertyTree(JSRuntime *rt)
1942 {
1943 if (rt->propertyTreeHash.ops) {
1944 JS_DHashTableFinish(&rt->propertyTreeHash);
1945 rt->propertyTreeHash.ops = NULL;
1946 }
1947 JS_FinishArenaPool(&rt->propertyArenaPool);
1948 }

  ViewVC Help
Powered by ViewVC 1.1.24