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