1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 *
3 * ***** BEGIN LICENSE BLOCK *****
4 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
5 *
6 * The contents of this file are subject to the Mozilla Public License Version
7 * 1.1 (the "License"); you may not use this file except in compliance with
8 * the License. You may obtain a copy of the License at
9 * http://www.mozilla.org/MPL/
10 *
11 * Software distributed under the License is distributed on an "AS IS" basis,
12 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
13 * for the specific language governing rights and limitations under the
14 * License.
15 *
16 * The Original Code is Mozilla Communicator client code, released
17 * March 31, 1998.
18 *
19 * The Initial Developer of the Original Code is
20 * Netscape Communications Corporation.
21 * Portions created by the Initial Developer are Copyright (C) 1998
22 * the Initial Developer. All Rights Reserved.
23 *
24 * Contributor(s):
25 *
26 * Alternatively, the contents of this file may be used under the terms of
27 * either of the GNU General Public License Version 2 or later (the "GPL"),
28 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29 * in which case the provisions of the GPL or the LGPL are applicable instead
30 * of those above. If you wish to allow use of your version of this file only
31 * under the terms of either the GPL or the LGPL, and not to allow others to
32 * use your version of this file under the terms of the MPL, indicate your
33 * decision by deleting the provisions above and replace them with the notice
34 * and other provisions required by the GPL or the LGPL. If you do not delete
35 * the provisions above, a recipient may use your version of this file under
36 * the terms of any one of the MPL, the GPL or the LGPL.
37 *
38 * ***** END LICENSE BLOCK ***** */
39
40 /*
41 * JS symbol tables.
42 */
43 #include "jsstddef.h"
44 #include <stdlib.h>
45 #include <string.h>
46 #include "jstypes.h"
47 #include "jsarena.h"
48 #include "jsbit.h"
49 #include "jsclist.h"
50 #include "jsdhash.h"
51 #include "jsutil.h" /* Added by JSIFY */
52 #include "jsapi.h"
53 #include "jsatom.h"
54 #include "jscntxt.h"
55 #include "jsdbgapi.h"
56 #include "jslock.h"
57 #include "jsnum.h"
58 #include "jsscope.h"
59 #include "jsstr.h"
60
61 JSScope *
js_GetMutableScope(JSContext * cx,JSObject * obj)62 js_GetMutableScope(JSContext *cx, JSObject *obj)
63 {
64 JSScope *scope, *newscope;
65
66 scope = OBJ_SCOPE(obj);
67 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
68 if (scope->object == obj)
69 return scope;
70 newscope = js_NewScope(cx, 0, scope->map.ops, LOCKED_OBJ_GET_CLASS(obj),
71 obj);
72 if (!newscope)
73 return NULL;
74 JS_LOCK_SCOPE(cx, newscope);
75 obj->map = js_HoldObjectMap(cx, &newscope->map);
76 scope = (JSScope *) js_DropObjectMap(cx, &scope->map, obj);
77 JS_TRANSFER_SCOPE_LOCK(cx, scope, newscope);
78 return newscope;
79 }
80
81 /*
82 * JSScope uses multiplicative hashing, _a la_ jsdhash.[ch], but specialized
83 * to minimize footprint. But if a scope has fewer than SCOPE_HASH_THRESHOLD
84 * entries, we use linear search and avoid allocating scope->table.
85 */
86 #define SCOPE_HASH_THRESHOLD 6
87 #define MIN_SCOPE_SIZE_LOG2 4
88 #define MIN_SCOPE_SIZE JS_BIT(MIN_SCOPE_SIZE_LOG2)
89 #define SCOPE_TABLE_NBYTES(n) ((n) * sizeof(JSScopeProperty *))
90
91 static void
InitMinimalScope(JSScope * scope)92 InitMinimalScope(JSScope *scope)
93 {
94 scope->hashShift = JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2;
95 scope->entryCount = scope->removedCount = 0;
96 scope->table = NULL;
97 scope->lastProp = NULL;
98 }
99
100 static JSBool
CreateScopeTable(JSScope * scope)101 CreateScopeTable(JSScope *scope)
102 {
103 int sizeLog2;
104 JSScopeProperty *sprop, **spp;
105
106 JS_ASSERT(!scope->table);
107 JS_ASSERT(scope->lastProp);
108
109 if (scope->entryCount > SCOPE_HASH_THRESHOLD) {
110 /*
111 * Ouch: calloc failed at least once already -- let's try again,
112 * overallocating to hold at least twice the current population.
113 */
114 sizeLog2 = JS_CeilingLog2(2 * scope->entryCount);
115 scope->hashShift = JS_DHASH_BITS - sizeLog2;
116 } else {
117 JS_ASSERT(scope->hashShift == JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2);
118 sizeLog2 = MIN_SCOPE_SIZE_LOG2;
119 }
120
121 scope->table = (JSScopeProperty **)
122 calloc(JS_BIT(sizeLog2), sizeof(JSScopeProperty *));
123 if (!scope->table)
124 return JS_FALSE;
125
126 scope->hashShift = JS_DHASH_BITS - sizeLog2;
127 for (sprop = scope->lastProp; sprop; sprop = sprop->parent) {
128 spp = js_SearchScope(scope, sprop->id, JS_TRUE);
129 SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
130 }
131 return JS_TRUE;
132 }
133
134 JSScope *
js_NewScope(JSContext * cx,jsrefcount nrefs,JSObjectOps * ops,JSClass * clasp,JSObject * obj)135 js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
136 JSObject *obj)
137 {
138 JSScope *scope;
139
140 scope = (JSScope *) JS_malloc(cx, sizeof(JSScope));
141 if (!scope)
142 return NULL;
143
144 js_InitObjectMap(&scope->map, nrefs, ops, clasp);
145 scope->object = obj;
146 scope->flags = 0;
147 InitMinimalScope(scope);
148
149 #ifdef JS_THREADSAFE
150 scope->ownercx = cx;
151 memset(&scope->lock, 0, sizeof scope->lock);
152
153 /*
154 * Set u.link = NULL, not u.count = 0, in case the target architecture's
155 * null pointer has a non-zero integer representation.
156 */
157 scope->u.link = NULL;
158
159 #ifdef DEBUG
160 scope->file[0] = scope->file[1] = scope->file[2] = scope->file[3] = NULL;
161 scope->line[0] = scope->line[1] = scope->line[2] = scope->line[3] = 0;
162 #endif
163 #endif
164
165 JS_RUNTIME_METER(cx->runtime, liveScopes);
166 JS_RUNTIME_METER(cx->runtime, totalScopes);
167 return scope;
168 }
169
170 #ifdef DEBUG_SCOPE_COUNT
171 extern void
172 js_unlog_scope(JSScope *scope);
173 #endif
174
175 void
js_DestroyScope(JSContext * cx,JSScope * scope)176 js_DestroyScope(JSContext *cx, JSScope *scope)
177 {
178 #ifdef DEBUG_SCOPE_COUNT
179 js_unlog_scope(scope);
180 #endif
181
182 #ifdef JS_THREADSAFE
183 /* Scope must be single-threaded at this point, so set scope->ownercx. */
184 JS_ASSERT(scope->u.count == 0);
185 scope->ownercx = cx;
186 js_FinishLock(&scope->lock);
187 #endif
188 if (scope->table)
189 JS_free(cx, scope->table);
190
191 #ifdef DEBUG
192 JS_LOCK_RUNTIME_VOID(cx->runtime,
193 cx->runtime->liveScopeProps -= scope->entryCount);
194 #endif
195 JS_RUNTIME_UNMETER(cx->runtime, liveScopes);
196 JS_free(cx, scope);
197 }
198
199 #ifdef DUMP_SCOPE_STATS
200 typedef struct JSScopeStats {
201 jsrefcount searches;
202 jsrefcount steps;
203 jsrefcount hits;
204 jsrefcount misses;
205 jsrefcount stepHits;
206 jsrefcount stepMisses;
207 jsrefcount adds;
208 jsrefcount redundantAdds;
209 jsrefcount addFailures;
210 jsrefcount changeFailures;
211 jsrefcount compresses;
212 jsrefcount grows;
213 jsrefcount removes;
214 jsrefcount removeFrees;
215 jsrefcount uselessRemoves;
216 jsrefcount shrinks;
217 } JSScopeStats;
218
219 JS_FRIEND_DATA(JSScopeStats) js_scope_stats;
220
221 # define METER(x) JS_ATOMIC_INCREMENT(&js_scope_stats.x)
222 #else
223 # define METER(x) /* nothing */
224 #endif
225
226 /*
227 * Double hashing needs the second hash code to be relatively prime to table
228 * size, so we simply make hash2 odd. The inputs to multiplicative hash are
229 * the golden ratio, expressed as a fixed-point 32 bit fraction, and the int
230 * property index or named property's atom number (observe that most objects
231 * have either no indexed properties, or almost all indexed and a few names,
232 * so collisions between index and atom number are unlikely).
233 */
234 #define SCOPE_HASH0(id) (HASH_ID(id) * JS_GOLDEN_RATIO)
235 #define SCOPE_HASH1(hash0,shift) ((hash0) >> (shift))
236 #define SCOPE_HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
237
238 JS_FRIEND_API(JSScopeProperty **)
js_SearchScope(JSScope * scope,jsid id,JSBool adding)239 js_SearchScope(JSScope *scope, jsid id, JSBool adding)
240 {
241 JSHashNumber hash0, hash1, hash2;
242 int hashShift, sizeLog2;
243 JSScopeProperty *stored, *sprop, **spp, **firstRemoved;
244 uint32 sizeMask;
245
246 METER(searches);
247 if (!scope->table) {
248 /* Not enough properties to justify hashing: search from lastProp. */
249 JS_ASSERT(!SCOPE_HAD_MIDDLE_DELETE(scope));
250 for (spp = &scope->lastProp; (sprop = *spp); spp = &sprop->parent) {
251 if (sprop->id == id) {
252 METER(hits);
253 return spp;
254 }
255 }
256 METER(misses);
257 return spp;
258 }
259
260 /* Compute the primary hash address. */
261 hash0 = SCOPE_HASH0(id);
262 hashShift = scope->hashShift;
263 hash1 = SCOPE_HASH1(hash0, hashShift);
264 spp = scope->table + hash1;
265
266 /* Miss: return space for a new entry. */
267 stored = *spp;
268 if (SPROP_IS_FREE(stored)) {
269 METER(misses);
270 return spp;
271 }
272
273 /* Hit: return entry. */
274 sprop = SPROP_CLEAR_COLLISION(stored);
275 if (sprop && sprop->id == id) {
276 METER(hits);
277 return spp;
278 }
279
280 /* Collision: double hash. */
281 sizeLog2 = JS_DHASH_BITS - hashShift;
282 hash2 = SCOPE_HASH2(hash0, sizeLog2, hashShift);
283 sizeMask = JS_BITMASK(sizeLog2);
284
285 /* Save the first removed entry pointer so we can recycle it if adding. */
286 if (SPROP_IS_REMOVED(stored)) {
287 firstRemoved = spp;
288 } else {
289 firstRemoved = NULL;
290 if (adding && !SPROP_HAD_COLLISION(stored))
291 SPROP_FLAG_COLLISION(spp, sprop);
292 }
293
294 for (;;) {
295 METER(steps);
296 hash1 -= hash2;
297 hash1 &= sizeMask;
298 spp = scope->table + hash1;
299
300 stored = *spp;
301 if (SPROP_IS_FREE(stored)) {
302 METER(stepMisses);
303 return (adding && firstRemoved) ? firstRemoved : spp;
304 }
305
306 sprop = SPROP_CLEAR_COLLISION(stored);
307 if (sprop && sprop->id == id) {
308 METER(stepHits);
309 return spp;
310 }
311
312 if (SPROP_IS_REMOVED(stored)) {
313 if (!firstRemoved)
314 firstRemoved = spp;
315 } else {
316 if (adding && !SPROP_HAD_COLLISION(stored))
317 SPROP_FLAG_COLLISION(spp, sprop);
318 }
319 }
320
321 /* NOTREACHED */
322 return NULL;
323 }
324
325 static JSBool
ChangeScope(JSContext * cx,JSScope * scope,int change)326 ChangeScope(JSContext *cx, JSScope *scope, int change)
327 {
328 int oldlog2, newlog2;
329 uint32 oldsize, newsize, nbytes;
330 JSScopeProperty **table, **oldtable, **spp, **oldspp, *sprop;
331
332 /* Grow, shrink, or compress by changing scope->table. */
333 oldlog2 = JS_DHASH_BITS - scope->hashShift;
334 newlog2 = oldlog2 + change;
335 oldsize = JS_BIT(oldlog2);
336 newsize = JS_BIT(newlog2);
337 nbytes = SCOPE_TABLE_NBYTES(newsize);
338 table = (JSScopeProperty **) calloc(nbytes, 1);
339 if (!table) {
340 JS_ReportOutOfMemory(cx);
341 return JS_FALSE;
342 }
343
344 /* Now that we have a new table allocated, update scope members. */
345 scope->hashShift = JS_DHASH_BITS - newlog2;
346 scope->removedCount = 0;
347 oldtable = scope->table;
348 scope->table = table;
349
350 /* Copy only live entries, leaving removed and free ones behind. */
351 for (oldspp = oldtable; oldsize != 0; oldspp++) {
352 sprop = SPROP_FETCH(oldspp);
353 if (sprop) {
354 spp = js_SearchScope(scope, sprop->id, JS_TRUE);
355 JS_ASSERT(SPROP_IS_FREE(*spp));
356 *spp = sprop;
357 }
358 oldsize--;
359 }
360
361 /* Finally, free the old table storage. */
362 JS_free(cx, oldtable);
363 return JS_TRUE;
364 }
365
366 /*
367 * Take care to exclude the mark and duplicate bits, in case we're called from
368 * the GC, or we are searching for a property that has not yet been flagged as
369 * a duplicate when making a duplicate formal parameter.
370 */
371 #define SPROP_FLAGS_NOT_MATCHED (SPROP_MARK | SPROP_IS_DUPLICATE)
372
373 JS_STATIC_DLL_CALLBACK(JSDHashNumber)
js_HashScopeProperty(JSDHashTable * table,const void * key)374 js_HashScopeProperty(JSDHashTable *table, const void *key)
375 {
376 const JSScopeProperty *sprop = (const JSScopeProperty *)key;
377 JSDHashNumber hash;
378 JSPropertyOp gsop;
379
380 /* Accumulate from least to most random so the low bits are most random. */
381 hash = 0;
382 gsop = sprop->getter;
383 if (gsop)
384 hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ (jsword)gsop;
385 gsop = sprop->setter;
386 if (gsop)
387 hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ (jsword)gsop;
388
389 hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4)
390 ^ (sprop->flags & ~SPROP_FLAGS_NOT_MATCHED);
391
392 hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->attrs;
393 hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->shortid;
394 hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->slot;
395 hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->id;
396 return hash;
397 }
398
399 #define SPROP_MATCH(sprop, child) \
400 SPROP_MATCH_PARAMS(sprop, (child)->id, (child)->getter, (child)->setter, \
401 (child)->slot, (child)->attrs, (child)->flags, \
402 (child)->shortid)
403
404 #define SPROP_MATCH_PARAMS(sprop, aid, agetter, asetter, aslot, aattrs, \
405 aflags, ashortid) \
406 ((sprop)->id == (aid) && \
407 SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
408 aflags, ashortid))
409
410 #define SPROP_MATCH_PARAMS_AFTER_ID(sprop, agetter, asetter, aslot, aattrs, \
411 aflags, ashortid) \
412 ((sprop)->getter == (agetter) && \
413 (sprop)->setter == (asetter) && \
414 (sprop)->slot == (aslot) && \
415 (sprop)->attrs == (aattrs) && \
416 (((sprop)->flags ^ (aflags)) & ~SPROP_FLAGS_NOT_MATCHED) == 0 && \
417 (sprop)->shortid == (ashortid))
418
419 JS_STATIC_DLL_CALLBACK(JSBool)
js_MatchScopeProperty(JSDHashTable * table,const JSDHashEntryHdr * hdr,const void * key)420 js_MatchScopeProperty(JSDHashTable *table,
421 const JSDHashEntryHdr *hdr,
422 const void *key)
423 {
424 const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr;
425 const JSScopeProperty *sprop = entry->child;
426 const JSScopeProperty *kprop = (const JSScopeProperty *)key;
427
428 return SPROP_MATCH(sprop, kprop);
429 }
430
431 static const JSDHashTableOps PropertyTreeHashOps = {
432 JS_DHashAllocTable,
433 JS_DHashFreeTable,
434 JS_DHashGetKeyStub,
435 js_HashScopeProperty,
436 js_MatchScopeProperty,
437 JS_DHashMoveEntryStub,
438 JS_DHashClearEntryStub,
439 JS_DHashFinalizeStub,
440 NULL
441 };
442
443 /*
444 * A property tree node on rt->propertyFreeList overlays the following prefix
445 * struct on JSScopeProperty.
446 */
447 typedef struct FreeNode {
448 jsid id;
449 JSScopeProperty *next;
450 JSScopeProperty **prevp;
451 } FreeNode;
452
453 #define FREENODE(sprop) ((FreeNode *) (sprop))
454
455 #define FREENODE_INSERT(list, sprop) \
456 JS_BEGIN_MACRO \
457 FREENODE(sprop)->next = (list); \
458 FREENODE(sprop)->prevp = &(list); \
459 if (list) \
460 FREENODE(list)->prevp = &FREENODE(sprop)->next; \
461 (list) = (sprop); \
462 JS_END_MACRO
463
464 #define FREENODE_REMOVE(sprop) \
465 JS_BEGIN_MACRO \
466 *FREENODE(sprop)->prevp = FREENODE(sprop)->next; \
467 if (FREENODE(sprop)->next) \
468 FREENODE(FREENODE(sprop)->next)->prevp = FREENODE(sprop)->prevp; \
469 JS_END_MACRO
470
471 /* NB: Called with the runtime lock held. */
472 static JSScopeProperty *
NewScopeProperty(JSRuntime * rt)473 NewScopeProperty(JSRuntime *rt)
474 {
475 JSScopeProperty *sprop;
476
477 sprop = rt->propertyFreeList;
478 if (sprop) {
479 FREENODE_REMOVE(sprop);
480 } else {
481 JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *,
482 &rt->propertyArenaPool,
483 sizeof(JSScopeProperty));
484 if (!sprop)
485 return NULL;
486 }
487
488 JS_RUNTIME_METER(rt, livePropTreeNodes);
489 JS_RUNTIME_METER(rt, totalPropTreeNodes);
490 return sprop;
491 }
492
493 #define CHUNKY_KIDS_TAG ((jsuword)1)
494 #define KIDS_IS_CHUNKY(kids) ((jsuword)(kids) & CHUNKY_KIDS_TAG)
495 #define KIDS_TO_CHUNK(kids) ((PropTreeKidsChunk *) \
496 ((jsuword)(kids) & ~CHUNKY_KIDS_TAG))
497 #define CHUNK_TO_KIDS(chunk) ((JSScopeProperty *) \
498 ((jsuword)(chunk) | CHUNKY_KIDS_TAG))
499 #define MAX_KIDS_PER_CHUNK 10
500
501 typedef struct PropTreeKidsChunk PropTreeKidsChunk;
502
503 struct PropTreeKidsChunk {
504 JSScopeProperty *kids[MAX_KIDS_PER_CHUNK];
505 PropTreeKidsChunk *next;
506 };
507
508 static PropTreeKidsChunk *
NewPropTreeKidsChunk(JSRuntime * rt)509 NewPropTreeKidsChunk(JSRuntime *rt)
510 {
511 PropTreeKidsChunk *chunk;
512
513 chunk = calloc(1, sizeof *chunk);
514 if (!chunk)
515 return NULL;
516 JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0);
517 JS_RUNTIME_METER(rt, propTreeKidsChunks);
518 return chunk;
519 }
520
521 static void
DestroyPropTreeKidsChunk(JSRuntime * rt,PropTreeKidsChunk * chunk)522 DestroyPropTreeKidsChunk(JSRuntime *rt, PropTreeKidsChunk *chunk)
523 {
524 JS_RUNTIME_UNMETER(rt, propTreeKidsChunks);
525 free(chunk);
526 }
527
528 /* NB: Called with the runtime lock held. */
529 static JSBool
InsertPropertyTreeChild(JSRuntime * rt,JSScopeProperty * parent,JSScopeProperty * child)530 InsertPropertyTreeChild(JSRuntime *rt, JSScopeProperty *parent,
531 JSScopeProperty *child)
532 {
533 JSPropertyTreeEntry *entry;
534 JSScopeProperty **childp, *kids, *sprop;
535 PropTreeKidsChunk *chunk, **chunkp;
536 uintN i;
537
538 JS_ASSERT(!parent || child->parent != parent);
539
540 if (!parent) {
541 entry = (JSPropertyTreeEntry *)
542 JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_ADD);
543 if (!entry)
544 return JS_FALSE;
545 childp = &entry->child;
546 sprop = *childp;
547 if (!sprop) {
548 *childp = child;
549 } else {
550 /*
551 * A "Duplicate child" case.
552 *
553 * We can't do away with child, as at least one live scope entry
554 * still points at it. What's more, that scope's lastProp chains
555 * through an ancestor line to reach child, and js_Enumerate and
556 * others count on this linkage. We must leave child out of the
557 * hash table, and not require it to be there when we eventually
558 * GC it (see RemovePropertyTreeChild, below).
559 *
560 * It is necessary to leave the duplicate child out of the hash
561 * table to preserve entry uniqueness. It is safe to leave the
562 * child out of the hash table (unlike the duplicate child cases
563 * below), because the child's parent link will be null, which
564 * can't dangle.
565 */
566 JS_ASSERT(sprop != child && SPROP_MATCH(sprop, child));
567 JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
568 }
569 } else {
570 childp = &parent->kids;
571 kids = *childp;
572 if (kids) {
573 if (KIDS_IS_CHUNKY(kids)) {
574 chunk = KIDS_TO_CHUNK(kids);
575 do {
576 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
577 childp = &chunk->kids[i];
578 sprop = *childp;
579 if (!sprop)
580 goto insert;
581
582 JS_ASSERT(sprop != child);
583 if (SPROP_MATCH(sprop, child)) {
584 /*
585 * Duplicate child, see comment above. In this
586 * case, we must let the duplicate be inserted at
587 * this level in the tree, so we keep iterating,
588 * looking for an empty slot in which to insert.
589 */
590 JS_ASSERT(sprop != child);
591 JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
592 }
593 }
594 chunkp = &chunk->next;
595 } while ((chunk = *chunkp) != NULL);
596
597 chunk = NewPropTreeKidsChunk(rt);
598 if (!chunk)
599 return JS_FALSE;
600 *chunkp = chunk;
601 childp = &chunk->kids[0];
602 } else {
603 sprop = kids;
604 JS_ASSERT(sprop != child);
605 if (SPROP_MATCH(sprop, child)) {
606 /*
607 * Duplicate child, see comment above. Once again, we
608 * must let duplicates created by deletion pile up in a
609 * kids-chunk-list, in order to find them when sweeping
610 * and thereby avoid dangling parent pointers.
611 */
612 JS_RUNTIME_METER(rt, duplicatePropTreeNodes);
613 }
614
615 chunk = NewPropTreeKidsChunk(rt);
616 if (!chunk)
617 return JS_FALSE;
618 parent->kids = CHUNK_TO_KIDS(chunk);
619 chunk->kids[0] = sprop;
620 childp = &chunk->kids[1];
621 }
622 }
623 insert:
624 *childp = child;
625 }
626
627 child->parent = parent;
628 return JS_TRUE;
629 }
630
631 /* NB: Called with the runtime lock held. */
632 static void
RemovePropertyTreeChild(JSRuntime * rt,JSScopeProperty * child)633 RemovePropertyTreeChild(JSRuntime *rt, JSScopeProperty *child)
634 {
635 JSPropertyTreeEntry *entry;
636 JSScopeProperty *parent, *kids, *kid;
637 PropTreeKidsChunk *list, *chunk, **chunkp, *lastChunk;
638 uintN i, j;
639
640 parent = child->parent;
641 if (!parent) {
642 /*
643 * Don't remove child if it is not in rt->propertyTreeHash, but only
644 * matches a root child in the table that has compatible members. See
645 * the "Duplicate child" comments in InsertPropertyTreeChild, above.
646 */
647 entry = (JSPropertyTreeEntry *)
648 JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_LOOKUP);
649
650 if (entry->child == child)
651 JS_DHashTableRawRemove(&rt->propertyTreeHash, &entry->hdr);
652 } else {
653 kids = parent->kids;
654 if (KIDS_IS_CHUNKY(kids)) {
655 list = chunk = KIDS_TO_CHUNK(kids);
656 chunkp = &list;
657
658 do {
659 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
660 if (chunk->kids[i] == child) {
661 lastChunk = chunk;
662 if (!lastChunk->next) {
663 j = i + 1;
664 } else {
665 j = 0;
666 do {
667 chunkp = &lastChunk->next;
668 lastChunk = *chunkp;
669 } while (lastChunk->next);
670 }
671 for (; j < MAX_KIDS_PER_CHUNK; j++) {
672 if (!lastChunk->kids[j])
673 break;
674 }
675 --j;
676 if (chunk != lastChunk || j > i)
677 chunk->kids[i] = lastChunk->kids[j];
678 lastChunk->kids[j] = NULL;
679 if (j == 0) {
680 *chunkp = NULL;
681 if (!list)
682 parent->kids = NULL;
683 DestroyPropTreeKidsChunk(rt, lastChunk);
684 }
685 return;
686 }
687 }
688
689 chunkp = &chunk->next;
690 } while ((chunk = *chunkp) != NULL);
691 } else {
692 kid = kids;
693 if (kid == child)
694 parent->kids = NULL;
695 }
696 }
697 }
698
699 /*
700 * Called *without* the runtime lock held, this function acquires that lock
701 * only when inserting a new child. Thus there may be races to find or add
702 * a node that result in duplicates. We expect such races to be rare!
703 */
704 static JSScopeProperty *
GetPropertyTreeChild(JSContext * cx,JSScopeProperty * parent,JSScopeProperty * child)705 GetPropertyTreeChild(JSContext *cx, JSScopeProperty *parent,
706 JSScopeProperty *child)
707 {
708 JSRuntime *rt;
709 JSPropertyTreeEntry *entry;
710 JSScopeProperty *sprop;
711 PropTreeKidsChunk *chunk;
712 uintN i;
713
714 rt = cx->runtime;
715 if (!parent) {
716 JS_LOCK_RUNTIME(rt);
717
718 entry = (JSPropertyTreeEntry *)
719 JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_ADD);
720 if (!entry)
721 goto out_of_memory;
722
723 sprop = entry->child;
724 if (sprop)
725 goto out;
726 } else {
727 /*
728 * Because chunks are appended at the end and never deleted except by
729 * the GC, we can search without taking the runtime lock. We may miss
730 * a matching sprop added by another thread, and make a duplicate one,
731 * but that is an unlikely, therefore small, cost. The property tree
732 * has extremely low fan-out below its root in popular embeddings with
733 * real-world workloads.
734 *
735 * If workload changes so as to increase fan-out significantly below
736 * the property tree root, we'll want to add another tag bit stored in
737 * parent->kids that indicates a JSDHashTable pointer.
738 */
739 entry = NULL;
740 sprop = parent->kids;
741 if (sprop) {
742 if (KIDS_IS_CHUNKY(sprop)) {
743 chunk = KIDS_TO_CHUNK(sprop);
744 do {
745 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
746 sprop = chunk->kids[i];
747 if (!sprop)
748 goto not_found;
749
750 if (SPROP_MATCH(sprop, child))
751 return sprop;
752 }
753 } while ((chunk = chunk->next) != NULL);
754 } else {
755 if (SPROP_MATCH(sprop, child))
756 return sprop;
757 }
758 }
759
760 not_found:
761 JS_LOCK_RUNTIME(rt);
762 }
763
764 sprop = NewScopeProperty(rt);
765 if (!sprop)
766 goto out_of_memory;
767
768 sprop->id = child->id;
769 sprop->getter = child->getter;
770 sprop->setter = child->setter;
771 sprop->slot = child->slot;
772 sprop->attrs = child->attrs;
773 sprop->flags = child->flags;
774 sprop->shortid = child->shortid;
775 sprop->parent = sprop->kids = NULL;
776 if (!parent) {
777 entry->child = sprop;
778 } else {
779 if (!InsertPropertyTreeChild(rt, parent, sprop))
780 goto out_of_memory;
781 }
782
783 out:
784 JS_UNLOCK_RUNTIME(rt);
785 return sprop;
786
787 out_of_memory:
788 JS_UNLOCK_RUNTIME(rt);
789 JS_ReportOutOfMemory(cx);
790 return NULL;
791 }
792
793 #ifdef DEBUG_notbrendan
794 #define CHECK_ANCESTOR_LINE(scope, sparse) \
795 JS_BEGIN_MACRO \
796 if ((scope)->table) CheckAncestorLine(scope, sparse); \
797 JS_END_MACRO
798
799 static void
CheckAncestorLine(JSScope * scope,JSBool sparse)800 CheckAncestorLine(JSScope *scope, JSBool sparse)
801 {
802 uint32 size;
803 JSScopeProperty **spp, **start, **end, *ancestorLine, *sprop, *aprop;
804 uint32 entryCount, ancestorCount;
805
806 ancestorLine = SCOPE_LAST_PROP(scope);
807 if (ancestorLine)
808 JS_ASSERT(SCOPE_HAS_PROPERTY(scope, ancestorLine));
809
810 entryCount = 0;
811 size = SCOPE_CAPACITY(scope);
812 start = scope->table;
813 for (spp = start, end = start + size; spp < end; spp++) {
814 sprop = SPROP_FETCH(spp);
815 if (sprop) {
816 entryCount++;
817 for (aprop = ancestorLine; aprop; aprop = aprop->parent) {
818 if (aprop == sprop)
819 break;
820 }
821 JS_ASSERT(aprop);
822 }
823 }
824 JS_ASSERT(entryCount == scope->entryCount);
825
826 ancestorCount = 0;
827 for (sprop = ancestorLine; sprop; sprop = sprop->parent) {
828 if (SCOPE_HAD_MIDDLE_DELETE(scope) &&
829 !SCOPE_HAS_PROPERTY(scope, sprop)) {
830 JS_ASSERT(sparse || (sprop->flags & SPROP_IS_DUPLICATE));
831 continue;
832 }
833 ancestorCount++;
834 }
835 JS_ASSERT(ancestorCount == scope->entryCount);
836 }
837 #else
838 #define CHECK_ANCESTOR_LINE(scope, sparse) /* nothing */
839 #endif
840
841 static void
ReportReadOnlyScope(JSContext * cx,JSScope * scope)842 ReportReadOnlyScope(JSContext *cx, JSScope *scope)
843 {
844 JSString *str;
845
846 str = js_ValueToString(cx, OBJECT_TO_JSVAL(scope->object));
847 JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_READ_ONLY,
848 str
849 ? JS_GetStringBytes(str)
850 : LOCKED_OBJ_GET_CLASS(scope->object)->name);
851 }
852
853 JSScopeProperty *
js_AddScopeProperty(JSContext * cx,JSScope * scope,jsid id,JSPropertyOp getter,JSPropertyOp setter,uint32 slot,uintN attrs,uintN flags,intN shortid)854 js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
855 JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
856 uintN attrs, uintN flags, intN shortid)
857 {
858 JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child;
859 uint32 size, splen, i;
860 int change;
861
862 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
863 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
864
865 /*
866 * You can't add properties to a sealed scope. But note well that you can
867 * change property attributes in a sealed scope, even though that replaces
868 * a JSScopeProperty * in the scope's hash table -- but no id is added, so
869 * the scope remains sealed.
870 */
871 if (SCOPE_IS_SEALED(scope)) {
872 ReportReadOnlyScope(cx, scope);
873 return NULL;
874 }
875
876 /*
877 * Normalize stub getter and setter values for faster is-stub testing in
878 * the SPROP_CALL_[GS]ETTER macros.
879 */
880 if (getter == JS_PropertyStub)
881 getter = NULL;
882 if (setter == JS_PropertyStub)
883 setter = NULL;
884
885 /*
886 * Search for id in order to claim its entry, allocating a property tree
887 * node if one doesn't already exist for our parameters.
888 */
889 spp = js_SearchScope(scope, id, JS_TRUE);
890 sprop = overwriting = SPROP_FETCH(spp);
891 if (!sprop) {
892 /* Check whether we need to grow, if the load factor is >= .75. */
893 size = SCOPE_CAPACITY(scope);
894 if (scope->entryCount + scope->removedCount >= size - (size >> 2)) {
895 if (scope->removedCount >= size >> 2) {
896 METER(compresses);
897 change = 0;
898 } else {
899 METER(grows);
900 change = 1;
901 }
902 if (!ChangeScope(cx, scope, change) &&
903 scope->entryCount + scope->removedCount == size - 1) {
904 METER(addFailures);
905 return NULL;
906 }
907 spp = js_SearchScope(scope, id, JS_TRUE);
908 JS_ASSERT(!SPROP_FETCH(spp));
909 }
910 } else {
911 /* Property exists: js_SearchScope must have returned a valid entry. */
912 JS_ASSERT(!SPROP_IS_REMOVED(*spp));
913
914 /*
915 * If all property members match, this is a redundant add and we can
916 * return early. If the caller wants to allocate a slot, but doesn't
917 * care which slot, copy sprop->slot into slot so we can match sprop,
918 * if all other members match.
919 */
920 if (!(attrs & JSPROP_SHARED) &&
921 slot == SPROP_INVALID_SLOT &&
922 SPROP_HAS_VALID_SLOT(sprop, scope)) {
923 slot = sprop->slot;
924 }
925 if (SPROP_MATCH_PARAMS_AFTER_ID(sprop, getter, setter, slot, attrs,
926 flags, shortid)) {
927 METER(redundantAdds);
928 return sprop;
929 }
930
931 /*
932 * Duplicate formal parameters require us to leave the old property
933 * on the ancestor line, so the decompiler can find it, even though
934 * its entry in scope->table is overwritten to point at a new property
935 * descending from the old one. The SPROP_IS_DUPLICATE flag helps us
936 * cope with the consequent disparity between ancestor line height and
937 * scope->entryCount.
938 */
939 if (flags & SPROP_IS_DUPLICATE) {
940 sprop->flags |= SPROP_IS_DUPLICATE;
941 } else {
942 /*
943 * If we are clearing sprop to force an existing property to be
944 * overwritten (apart from a duplicate formal parameter), we must
945 * unlink it from the ancestor line at scope->lastProp, lazily if
946 * sprop is not lastProp. And we must remove the entry at *spp,
947 * precisely so the lazy "middle delete" fixup code further below
948 * won't find sprop in scope->table, in spite of sprop being on
949 * the ancestor line.
950 *
951 * When we finally succeed in finding or creating a new sprop
952 * and storing its pointer at *spp, we'll use the |overwriting|
953 * local saved when we first looked up id to decide whether we're
954 * indeed creating a new entry, or merely overwriting an existing
955 * property.
956 */
957 if (sprop == SCOPE_LAST_PROP(scope)) {
958 do {
959 SCOPE_REMOVE_LAST_PROP(scope);
960 if (!SCOPE_HAD_MIDDLE_DELETE(scope))
961 break;
962 sprop = SCOPE_LAST_PROP(scope);
963 } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
964 } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
965 /*
966 * If we have no hash table yet, we need one now. The middle
967 * delete code is simple-minded that way!
968 */
969 if (!scope->table) {
970 if (!CreateScopeTable(scope)) {
971 JS_ReportOutOfMemory(cx);
972 return NULL;
973 }
974 spp = js_SearchScope(scope, id, JS_TRUE);
975 sprop = overwriting = SPROP_FETCH(spp);
976 }
977 SCOPE_SET_MIDDLE_DELETE(scope);
978 }
979 }
980
981 /*
982 * If we fail later on trying to find or create a new sprop, we will
983 * goto fail_overwrite and restore *spp from |overwriting|. Note that
984 * we don't bother to keep scope->removedCount in sync, because we'll
985 * fix up *spp and scope->entryCount shortly, no matter how control
986 * flow returns from this function.
987 */
988 if (scope->table)
989 SPROP_STORE_PRESERVING_COLLISION(spp, NULL);
990 scope->entryCount--;
991 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
992 sprop = NULL;
993 }
994
995 if (!sprop) {
996 /*
997 * If properties were deleted from the middle of the list starting at
998 * scope->lastProp, we may need to fork the property tree and squeeze
999 * all deleted properties out of scope's ancestor line. Otherwise we
1000 * risk adding a node with the same id as a "middle" node, violating
1001 * the rule that properties along an ancestor line have distinct ids
1002 * (unless flagged SPROP_IS_DUPLICATE).
1003 */
1004 if (SCOPE_HAD_MIDDLE_DELETE(scope)) {
1005 JS_ASSERT(scope->table);
1006 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1007
1008 splen = scope->entryCount;
1009 if (splen == 0) {
1010 JS_ASSERT(scope->lastProp == NULL);
1011 } else {
1012 /*
1013 * Enumerate live entries in scope->table using a temporary
1014 * vector, by walking the (possibly sparse, due to deletions)
1015 * ancestor line from scope->lastProp.
1016 */
1017 spvec = (JSScopeProperty **)
1018 JS_malloc(cx, SCOPE_TABLE_NBYTES(splen));
1019 if (!spvec)
1020 goto fail_overwrite;
1021 i = splen;
1022 sprop = SCOPE_LAST_PROP(scope);
1023 JS_ASSERT(sprop);
1024 do {
1025 /*
1026 * NB: test SCOPE_GET_PROPERTY, not SCOPE_HAS_PROPERTY --
1027 * the latter insists that sprop->id maps to sprop, while
1028 * the former simply tests whether sprop->id is bound in
1029 * scope. We must allow for duplicate formal parameters
1030 * along the ancestor line, and fork them as needed.
1031 */
1032 if (!SCOPE_GET_PROPERTY(scope, sprop->id))
1033 continue;
1034
1035 JS_ASSERT(sprop != overwriting);
1036 if (i == 0) {
1037 /*
1038 * If our original splen estimate, scope->entryCount,
1039 * is less than the ancestor line height, there must
1040 * be duplicate formal parameters in this (function
1041 * object) scope. Count remaining ancestors in order
1042 * to realloc spvec.
1043 */
1044 JSScopeProperty *tmp = sprop;
1045 do {
1046 if (SCOPE_GET_PROPERTY(scope, tmp->id))
1047 i++;
1048 } while ((tmp = tmp->parent) != NULL);
1049 spp2 = (JSScopeProperty **)
1050 JS_realloc(cx, spvec, SCOPE_TABLE_NBYTES(splen+i));
1051 if (!spp2) {
1052 JS_free(cx, spvec);
1053 goto fail_overwrite;
1054 }
1055
1056 spvec = spp2;
1057 memmove(spvec + i, spvec, SCOPE_TABLE_NBYTES(splen));
1058 splen += i;
1059 }
1060
1061 spvec[--i] = sprop;
1062 } while ((sprop = sprop->parent) != NULL);
1063 JS_ASSERT(i == 0);
1064
1065 /*
1066 * Now loop forward through spvec, forking the property tree
1067 * whenever we see a "parent gap" due to deletions from scope.
1068 * NB: sprop is null on first entry to the loop body.
1069 */
1070 do {
1071 if (spvec[i]->parent == sprop) {
1072 sprop = spvec[i];
1073 } else {
1074 sprop = GetPropertyTreeChild(cx, sprop, spvec[i]);
1075 if (!sprop) {
1076 JS_free(cx, spvec);
1077 goto fail_overwrite;
1078 }
1079
1080 spp2 = js_SearchScope(scope, sprop->id, JS_FALSE);
1081 JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]);
1082 SPROP_STORE_PRESERVING_COLLISION(spp2, sprop);
1083 }
1084 } while (++i < splen);
1085 JS_free(cx, spvec);
1086
1087 /*
1088 * Now sprop points to the last property in scope, where the
1089 * ancestor line from sprop to the root is dense w.r.t. scope:
1090 * it contains no nodes not mapped by scope->table, apart from
1091 * any stinking ECMA-mandated duplicate formal parameters.
1092 */
1093 scope->lastProp = sprop;
1094 CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1095 JS_RUNTIME_METER(cx->runtime, middleDeleteFixups);
1096 }
1097
1098 SCOPE_CLR_MIDDLE_DELETE(scope);
1099 }
1100
1101 /*
1102 * Aliases share another property's slot, passed in the |slot| param.
1103 * Shared properties have no slot. Unshared properties that do not
1104 * alias another property's slot get one here, but may lose it due to
1105 * a JS_ClearScope call.
1106 */
1107 if (!(flags & SPROP_IS_ALIAS)) {
1108 if (attrs & JSPROP_SHARED) {
1109 slot = SPROP_INVALID_SLOT;
1110 } else {
1111 /*
1112 * We may have set slot from a nearly-matching sprop, above.
1113 * If so, we're overwriting that nearly-matching sprop, so we
1114 * can reuse its slot -- we don't need to allocate a new one.
1115 * Callers should therefore pass SPROP_INVALID_SLOT for all
1116 * non-alias, unshared property adds.
1117 */
1118 if (slot != SPROP_INVALID_SLOT)
1119 JS_ASSERT(overwriting);
1120 else if (!js_AllocSlot(cx, scope->object, &slot))
1121 goto fail_overwrite;
1122 }
1123 }
1124
1125 /*
1126 * Check for a watchpoint on a deleted property; if one exists, change
1127 * setter to js_watch_set.
1128 * XXXbe this could get expensive with lots of watchpoints...
1129 */
1130 if (!JS_CLIST_IS_EMPTY(&cx->runtime->watchPointList) &&
1131 js_FindWatchPoint(cx->runtime, scope, id)) {
1132 setter = js_WrapWatchedSetter(cx, id, attrs, setter);
1133 if (!setter)
1134 goto fail_overwrite;
1135 }
1136
1137 /* Find or create a property tree node labeled by our arguments. */
1138 child.id = id;
1139 child.getter = getter;
1140 child.setter = setter;
1141 child.slot = slot;
1142 child.attrs = attrs;
1143 child.flags = flags;
1144 child.shortid = shortid;
1145 sprop = GetPropertyTreeChild(cx, scope->lastProp, &child);
1146 if (!sprop)
1147 goto fail_overwrite;
1148
1149 /* Store the tree node pointer in the table entry for id. */
1150 if (scope->table)
1151 SPROP_STORE_PRESERVING_COLLISION(spp, sprop);
1152 scope->entryCount++;
1153 scope->lastProp = sprop;
1154 CHECK_ANCESTOR_LINE(scope, JS_FALSE);
1155 if (!overwriting) {
1156 JS_RUNTIME_METER(cx->runtime, liveScopeProps);
1157 JS_RUNTIME_METER(cx->runtime, totalScopeProps);
1158 }
1159
1160 /*
1161 * If we reach the hashing threshold, try to allocate scope->table.
1162 * If we can't (a rare event, preceded by swapping to death on most
1163 * modern OSes), stick with linear search rather than whining about
1164 * this little set-back. Therefore we must test !scope->table and
1165 * scope->entryCount >= SCOPE_HASH_THRESHOLD, not merely whether the
1166 * entry count just reached the threshold.
1167 */
1168 if (!scope->table && scope->entryCount >= SCOPE_HASH_THRESHOLD)
1169 (void) CreateScopeTable(scope);
1170 }
1171
1172 METER(adds);
1173 return sprop;
1174
1175 fail_overwrite:
1176 if (overwriting) {
1177 /*
1178 * We may or may not have forked overwriting out of scope's ancestor
1179 * line, so we must check (the alternative is to set a flag above, but
1180 * that hurts the common, non-error case). If we did fork overwriting
1181 * out, we'll add it back at scope->lastProp. This means enumeration
1182 * order can change due to a failure to overwrite an id.
1183 * XXXbe very minor incompatibility
1184 */
1185 for (sprop = SCOPE_LAST_PROP(scope); ; sprop = sprop->parent) {
1186 if (!sprop) {
1187 sprop = SCOPE_LAST_PROP(scope);
1188 if (overwriting->parent == sprop) {
1189 scope->lastProp = overwriting;
1190 } else {
1191 sprop = GetPropertyTreeChild(cx, sprop, overwriting);
1192 if (sprop) {
1193 JS_ASSERT(sprop != overwriting);
1194 scope->lastProp = sprop;
1195 }
1196 overwriting = sprop;
1197 }
1198 break;
1199 }
1200 if (sprop == overwriting)
1201 break;
1202 }
1203 if (overwriting) {
1204 if (scope->table)
1205 SPROP_STORE_PRESERVING_COLLISION(spp, overwriting);
1206 scope->entryCount++;
1207 }
1208 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1209 }
1210 METER(addFailures);
1211 return NULL;
1212 }
1213
1214 JSScopeProperty *
js_ChangeScopePropertyAttrs(JSContext * cx,JSScope * scope,JSScopeProperty * sprop,uintN attrs,uintN mask,JSPropertyOp getter,JSPropertyOp setter)1215 js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
1216 JSScopeProperty *sprop, uintN attrs, uintN mask,
1217 JSPropertyOp getter, JSPropertyOp setter)
1218 {
1219 JSScopeProperty child, *newsprop, **spp;
1220
1221 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1222
1223 /* Allow only shared (slot-less) => unshared (slot-full) transition. */
1224 attrs |= sprop->attrs & mask;
1225 JS_ASSERT(!((attrs ^ sprop->attrs) & JSPROP_SHARED) ||
1226 !(attrs & JSPROP_SHARED));
1227 if (getter == JS_PropertyStub)
1228 getter = NULL;
1229 if (setter == JS_PropertyStub)
1230 setter = NULL;
1231 if (sprop->attrs == attrs &&
1232 sprop->getter == getter &&
1233 sprop->setter == setter) {
1234 return sprop;
1235 }
1236
1237 child.id = sprop->id;
1238 child.getter = getter;
1239 child.setter = setter;
1240 child.slot = sprop->slot;
1241 child.attrs = attrs;
1242 child.flags = sprop->flags;
1243 child.shortid = sprop->shortid;
1244
1245 if (SCOPE_LAST_PROP(scope) == sprop) {
1246 /*
1247 * Optimize the case where the last property added to scope is changed
1248 * to have a different attrs, getter, or setter. In the last property
1249 * case, we need not fork the property tree. But since we do not call
1250 * js_AddScopeProperty, we may need to allocate a new slot directly.
1251 */
1252 if ((sprop->attrs & JSPROP_SHARED) && !(attrs & JSPROP_SHARED)) {
1253 JS_ASSERT(child.slot == SPROP_INVALID_SLOT);
1254 if (!js_AllocSlot(cx, scope->object, &child.slot))
1255 return NULL;
1256 }
1257
1258 newsprop = GetPropertyTreeChild(cx, sprop->parent, &child);
1259 if (newsprop) {
1260 spp = js_SearchScope(scope, sprop->id, JS_FALSE);
1261 JS_ASSERT(SPROP_FETCH(spp) == sprop);
1262
1263 if (scope->table)
1264 SPROP_STORE_PRESERVING_COLLISION(spp, newsprop);
1265 scope->lastProp = newsprop;
1266 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1267 }
1268 } else {
1269 /*
1270 * Let js_AddScopeProperty handle this |overwriting| case, including
1271 * the conservation of sprop->slot (if it's valid). We must not call
1272 * js_RemoveScopeProperty here, it will free a valid sprop->slot and
1273 * js_AddScopeProperty won't re-allocate it.
1274 */
1275 newsprop = js_AddScopeProperty(cx, scope, child.id,
1276 child.getter, child.setter, child.slot,
1277 child.attrs, child.flags, child.shortid);
1278 }
1279
1280 #ifdef DUMP_SCOPE_STATS
1281 if (!newsprop)
1282 METER(changeFailures);
1283 #endif
1284 return newsprop;
1285 }
1286
1287 JSBool
js_RemoveScopeProperty(JSContext * cx,JSScope * scope,jsid id)1288 js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id)
1289 {
1290 JSScopeProperty **spp, *stored, *sprop;
1291 uint32 size;
1292
1293 JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope));
1294 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1295 if (SCOPE_IS_SEALED(scope)) {
1296 ReportReadOnlyScope(cx, scope);
1297 return JS_FALSE;
1298 }
1299 METER(removes);
1300
1301 spp = js_SearchScope(scope, id, JS_FALSE);
1302 stored = *spp;
1303 sprop = SPROP_CLEAR_COLLISION(stored);
1304 if (!sprop) {
1305 METER(uselessRemoves);
1306 return JS_TRUE;
1307 }
1308
1309 /* Convert from a list to a hash so we can handle "middle deletes". */
1310 if (!scope->table && sprop != scope->lastProp) {
1311 if (!CreateScopeTable(scope)) {
1312 JS_ReportOutOfMemory(cx);
1313 return JS_FALSE;
1314 }
1315 spp = js_SearchScope(scope, id, JS_FALSE);
1316 stored = *spp;
1317 sprop = SPROP_CLEAR_COLLISION(stored);
1318 }
1319
1320 /* First, if sprop is unshared and not cleared, free its slot number. */
1321 if (SPROP_HAS_VALID_SLOT(sprop, scope))
1322 js_FreeSlot(cx, scope->object, sprop->slot);
1323
1324 /* Next, remove id by setting its entry to a removed or free sentinel. */
1325 if (SPROP_HAD_COLLISION(stored)) {
1326 JS_ASSERT(scope->table);
1327 *spp = SPROP_REMOVED;
1328 scope->removedCount++;
1329 } else {
1330 METER(removeFrees);
1331 if (scope->table)
1332 *spp = NULL;
1333 }
1334 scope->entryCount--;
1335 JS_RUNTIME_UNMETER(cx->runtime, liveScopeProps);
1336
1337 /* Update scope->lastProp directly, or set its deferred update flag. */
1338 if (sprop == SCOPE_LAST_PROP(scope)) {
1339 do {
1340 SCOPE_REMOVE_LAST_PROP(scope);
1341 if (!SCOPE_HAD_MIDDLE_DELETE(scope))
1342 break;
1343 sprop = SCOPE_LAST_PROP(scope);
1344 } while (sprop && !SCOPE_HAS_PROPERTY(scope, sprop));
1345 } else if (!SCOPE_HAD_MIDDLE_DELETE(scope)) {
1346 SCOPE_SET_MIDDLE_DELETE(scope);
1347 }
1348 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1349
1350 /* Last, consider shrinking scope's table if its load factor is <= .25. */
1351 size = SCOPE_CAPACITY(scope);
1352 if (size > MIN_SCOPE_SIZE && scope->entryCount <= size >> 2) {
1353 METER(shrinks);
1354 (void) ChangeScope(cx, scope, -1);
1355 }
1356
1357 return JS_TRUE;
1358 }
1359
1360 void
js_ClearScope(JSContext * cx,JSScope * scope)1361 js_ClearScope(JSContext *cx, JSScope *scope)
1362 {
1363 CHECK_ANCESTOR_LINE(scope, JS_TRUE);
1364 #ifdef DEBUG
1365 JS_LOCK_RUNTIME_VOID(cx->runtime,
1366 cx->runtime->liveScopeProps -= scope->entryCount);
1367 #endif
1368
1369 if (scope->table)
1370 free(scope->table);
1371 SCOPE_CLR_MIDDLE_DELETE(scope);
1372 InitMinimalScope(scope);
1373 }
1374
1375 #ifdef DUMP_SCOPE_STATS
1376
1377 #include <stdio.h>
1378 #include <math.h>
1379
1380 uint32 js_nkids_max;
1381 uint32 js_nkids_sum;
1382 double js_nkids_sqsum;
1383 uint32 js_nkids_hist[11];
1384
1385 static void
MeterKidCount(uintN nkids)1386 MeterKidCount(uintN nkids)
1387 {
1388 if (nkids) {
1389 js_nkids_sum += nkids;
1390 js_nkids_sqsum += (double)nkids * nkids;
1391 if (nkids > js_nkids_max)
1392 js_nkids_max = nkids;
1393 }
1394 js_nkids_hist[JS_MIN(nkids, 10)]++;
1395 }
1396
1397 static void
MeterPropertyTree(JSScopeProperty * node)1398 MeterPropertyTree(JSScopeProperty *node)
1399 {
1400 uintN i, nkids;
1401 JSScopeProperty *kids, *kid;
1402 PropTreeKidsChunk *chunk;
1403
1404 nkids = 0;
1405 kids = node->kids;
1406 if (kids) {
1407 if (KIDS_IS_CHUNKY(kids)) {
1408 for (chunk = KIDS_TO_CHUNK(kids); chunk; chunk = chunk->next) {
1409 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1410 kid = chunk->kids[i];
1411 if (!kid)
1412 break;
1413 MeterPropertyTree(kid);
1414 nkids++;
1415 }
1416 }
1417 } else {
1418 MeterPropertyTree(kids);
1419 nkids = 1;
1420 }
1421 }
1422
1423 MeterKidCount(nkids);
1424 }
1425
1426 JS_STATIC_DLL_CALLBACK(JSDHashOperator)
js_MeterPropertyTree(JSDHashTable * table,JSDHashEntryHdr * hdr,uint32 number,void * arg)1427 js_MeterPropertyTree(JSDHashTable *table, JSDHashEntryHdr *hdr, uint32 number,
1428 void *arg)
1429 {
1430 JSPropertyTreeEntry *entry = (JSPropertyTreeEntry *)hdr;
1431
1432 MeterPropertyTree(entry->child);
1433 return JS_DHASH_NEXT;
1434 }
1435
1436 #include "jsprf.h"
1437
1438 static void
DumpSubtree(JSScopeProperty * sprop,int level,FILE * fp)1439 DumpSubtree(JSScopeProperty *sprop, int level, FILE *fp)
1440 {
1441 char buf[10];
1442 JSScopeProperty *kids, *kid;
1443 PropTreeKidsChunk *chunk;
1444 uintN i;
1445
1446 fprintf(fp, "%*sid %s g/s %p/%p slot %lu attrs %x flags %x shortid %d\n",
1447 level, "",
1448 JSVAL_IS_INT(sprop->id)
1449 ? (JS_snprintf(buf, sizeof buf, "%ld", JSVAL_TO_INT(sprop->id)),
1450 buf)
1451 : JS_GetStringBytes(ATOM_TO_STRING((JSAtom *) sprop->id)),
1452 (void *) sprop->getter, (void *) sprop->setter,
1453 (unsigned long) sprop->slot, sprop->attrs, sprop->flags,
1454 sprop->shortid);
1455 kids = sprop->kids;
1456 if (kids) {
1457 ++level;
1458 if (KIDS_IS_CHUNKY(kids)) {
1459 chunk = KIDS_TO_CHUNK(kids);
1460 do {
1461 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1462 kid = chunk->kids[i];
1463 if (!kid)
1464 break;
1465 JS_ASSERT(kid->parent == sprop);
1466 DumpSubtree(kid, level, fp);
1467 }
1468 } while ((chunk = chunk->next) != NULL);
1469 } else {
1470 kid = kids;
1471 DumpSubtree(kid, level, fp);
1472 }
1473 }
1474 }
1475
1476 #endif /* DUMP_SCOPE_STATS */
1477
1478 void
js_SweepScopeProperties(JSRuntime * rt)1479 js_SweepScopeProperties(JSRuntime *rt)
1480 {
1481 JSArena **ap, *a;
1482 JSScopeProperty *limit, *sprop, *parent, *kids, *kid;
1483 uintN liveCount;
1484 PropTreeKidsChunk *chunk, *nextChunk;
1485 uintN i;
1486
1487 #ifdef DUMP_SCOPE_STATS
1488 uint32 livePropCapacity = 0, totalLiveCount = 0;
1489 static FILE *logfp;
1490 if (!logfp)
1491 logfp = fopen("/tmp/proptree.stats", "a");
1492
1493 MeterKidCount(rt->propertyTreeHash.entryCount);
1494 JS_DHashTableEnumerate(&rt->propertyTreeHash, js_MeterPropertyTree, NULL);
1495
1496 {
1497 double mean = 0.0, var = 0.0, sigma = 0.0;
1498 double nodesum = rt->livePropTreeNodes;
1499 double kidsum = js_nkids_sum;
1500 if (nodesum > 0 && kidsum >= 0) {
1501 mean = kidsum / nodesum;
1502 var = nodesum * js_nkids_sqsum - kidsum * kidsum;
1503 if (var < 0.0 || nodesum <= 1)
1504 var = 0.0;
1505 else
1506 var /= nodesum * (nodesum - 1);
1507
1508 /* Windows says sqrt(0.0) is "-1.#J" (?!) so we must test. */
1509 sigma = (var != 0.0) ? sqrt(var) : 0.0;
1510 }
1511
1512 fprintf(logfp,
1513 "props %u nodes %g beta %g meankids %g sigma %g max %u",
1514 rt->liveScopeProps, nodesum, nodesum / rt->liveScopeProps,
1515 mean, sigma, js_nkids_max);
1516 }
1517
1518 fprintf(logfp, " histogram %u %u %u %u %u %u %u %u %u %u %u",
1519 js_nkids_hist[0], js_nkids_hist[1],
1520 js_nkids_hist[2], js_nkids_hist[3],
1521 js_nkids_hist[4], js_nkids_hist[5],
1522 js_nkids_hist[6], js_nkids_hist[7],
1523 js_nkids_hist[8], js_nkids_hist[9],
1524 js_nkids_hist[10]);
1525 js_nkids_sum = js_nkids_max = 0;
1526 js_nkids_sqsum = 0;
1527 memset(js_nkids_hist, 0, sizeof js_nkids_hist);
1528 #endif
1529
1530 ap = &rt->propertyArenaPool.first.next;
1531 while ((a = *ap) != NULL) {
1532 limit = (JSScopeProperty *) a->avail;
1533 liveCount = 0;
1534 for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) {
1535 /* If the id is null, sprop is already on the freelist. */
1536 if (sprop->id == JSVAL_NULL)
1537 continue;
1538
1539 /* If the mark bit is set, sprop is alive, so we skip it. */
1540 if (sprop->flags & SPROP_MARK) {
1541 sprop->flags &= ~SPROP_MARK;
1542 liveCount++;
1543 continue;
1544 }
1545
1546 /* Ok, sprop is garbage to collect: unlink it from its parent. */
1547 RemovePropertyTreeChild(rt, sprop);
1548
1549 /* Take care to reparent all sprop's kids to their grandparent. */
1550 kids = sprop->kids;
1551 if (kids) {
1552 sprop->kids = NULL;
1553 parent = sprop->parent;
1554 if (KIDS_IS_CHUNKY(kids)) {
1555 chunk = KIDS_TO_CHUNK(kids);
1556 do {
1557 for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) {
1558 kid = chunk->kids[i];
1559 if (!kid)
1560 break;
1561 JS_ASSERT(kid->parent == sprop);
1562 InsertPropertyTreeChild(rt, parent, kid);
1563 }
1564 nextChunk = chunk->next;
1565 DestroyPropTreeKidsChunk(rt, chunk);
1566 } while ((chunk = nextChunk) != NULL);
1567 } else {
1568 kid = kids;
1569 InsertPropertyTreeChild(rt, parent, kid);
1570 }
1571 }
1572
1573 /* Clear id so we know (above) that sprop is on the freelist. */
1574 sprop->id = JSVAL_NULL;
1575 FREENODE_INSERT(rt->propertyFreeList, sprop);
1576 JS_RUNTIME_UNMETER(rt, livePropTreeNodes);
1577 }
1578
1579 /* If a contains no live properties, return it to the malloc heap. */
1580 if (liveCount == 0) {
1581 for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++)
1582 FREENODE_REMOVE(sprop);
1583 JS_ARENA_DESTROY(&rt->propertyArenaPool, a, ap);
1584 } else {
1585 #ifdef DUMP_SCOPE_STATS
1586 livePropCapacity += limit - (JSScopeProperty *) a->base;
1587 totalLiveCount += liveCount;
1588 #endif
1589 ap = &a->next;
1590 }
1591 }
1592
1593 #ifdef DUMP_SCOPE_STATS
1594 fprintf(logfp, " arenautil %g%%\n",
1595 (totalLiveCount * 100.0) / livePropCapacity);
1596 fflush(logfp);
1597 #endif
1598
1599 #ifdef DUMP_PROPERTY_TREE
1600 {
1601 FILE *dumpfp = fopen("/tmp/proptree.dump", "w");
1602 if (dumpfp) {
1603 JSPropertyTreeEntry *pte, *end;
1604
1605 pte = (JSPropertyTreeEntry *) rt->propertyTreeHash.entryStore;
1606 end = pte + JS_DHASH_TABLE_SIZE(&rt->propertyTreeHash);
1607 while (pte < end) {
1608 if (pte->child)
1609 DumpSubtree(pte->child, 0, dumpfp);
1610 pte++;
1611 }
1612 fclose(dumpfp);
1613 }
1614 }
1615 #endif
1616 }
1617
1618 JSBool
js_InitPropertyTree(JSRuntime * rt)1619 js_InitPropertyTree(JSRuntime *rt)
1620 {
1621 if (!JS_DHashTableInit(&rt->propertyTreeHash, &PropertyTreeHashOps, NULL,
1622 sizeof(JSPropertyTreeEntry), JS_DHASH_MIN_SIZE)) {
1623 rt->propertyTreeHash.ops = NULL;
1624 return JS_FALSE;
1625 }
1626 JS_InitArenaPool(&rt->propertyArenaPool, "properties",
1627 256 * sizeof(JSScopeProperty), sizeof(void *));
1628 return JS_TRUE;
1629 }
1630
1631 void
js_FinishPropertyTree(JSRuntime * rt)1632 js_FinishPropertyTree(JSRuntime *rt)
1633 {
1634 if (rt->propertyTreeHash.ops) {
1635 JS_DHashTableFinish(&rt->propertyTreeHash);
1636 rt->propertyTreeHash.ops = NULL;
1637 }
1638 JS_FinishArenaPool(&rt->propertyArenaPool);
1639 }
1640