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 |
1233207 |
{ |
64 |
1233207 |
JSScope *scope, *newscope; |
65 |
|
|
66 |
1233207 |
scope = OBJ_SCOPE(obj); |
67 |
1233207 |
JS_ASSERT(JS_IS_SCOPE_LOCKED(cx, scope)); |
68 |
1233207 |
if (scope->object == obj) |
69 |
1132002 |
return scope; |
70 |
101205 |
newscope = js_NewScope(cx, 0, scope->map.ops, LOCKED_OBJ_GET_CLASS(obj), |
71 |
|
obj); |
72 |
101205 |
if (!newscope) |
73 |
0 |
return NULL; |
74 |
101205 |
JS_LOCK_SCOPE(cx, newscope); |
75 |
101205 |
obj->map = js_HoldObjectMap(cx, &newscope->map); |
76 |
101205 |
scope = (JSScope *) js_DropObjectMap(cx, &scope->map, obj); |
77 |
101205 |
JS_TRANSFER_SCOPE_LOCK(cx, scope, newscope); |
78 |
101205 |
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 |
144713 |
{ |
94 |
144713 |
scope->hashShift = JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2; |
95 |
144713 |
scope->entryCount = scope->removedCount = 0; |
96 |
144713 |
scope->table = NULL; |
97 |
144713 |
scope->lastProp = NULL; |
98 |
|
} |
99 |
|
|
100 |
|
static JSBool |
101 |
|
CreateScopeTable(JSContext *cx, JSScope *scope, JSBool report) |
102 |
65339 |
{ |
103 |
65339 |
int sizeLog2; |
104 |
65339 |
JSScopeProperty *sprop, **spp; |
105 |
|
|
106 |
65339 |
JS_ASSERT(!scope->table); |
107 |
65339 |
JS_ASSERT(scope->lastProp); |
108 |
|
|
109 |
65339 |
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 |
65339 |
JS_ASSERT(scope->hashShift == JS_DHASH_BITS - MIN_SCOPE_SIZE_LOG2); |
118 |
65339 |
sizeLog2 = MIN_SCOPE_SIZE_LOG2; |
119 |
|
} |
120 |
|
|
121 |
65339 |
scope->table = (JSScopeProperty **) |
122 |
|
calloc(JS_BIT(sizeLog2), sizeof(JSScopeProperty *)); |
123 |
65339 |
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 |
65339 |
cx->runtime->gcMallocBytes += JS_BIT(sizeLog2) * sizeof(JSScopeProperty *); |
131 |
|
|
132 |
65339 |
scope->hashShift = JS_DHASH_BITS - sizeLog2; |
133 |
457405 |
for (sprop = scope->lastProp; sprop; sprop = sprop->parent) { |
134 |
392066 |
spp = js_SearchScope(scope, sprop->id, JS_TRUE); |
135 |
392066 |
SPROP_STORE_PRESERVING_COLLISION(spp, sprop); |
136 |
|
} |
137 |
65339 |
return JS_TRUE; |
138 |
|
} |
139 |
|
|
140 |
|
JSScope * |
141 |
|
js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp, |
142 |
|
JSObject *obj) |
143 |
144713 |
{ |
144 |
144713 |
JSScope *scope; |
145 |
|
|
146 |
144713 |
scope = (JSScope *) JS_malloc(cx, sizeof(JSScope)); |
147 |
144713 |
if (!scope) |
148 |
0 |
return NULL; |
149 |
|
|
150 |
144713 |
js_InitObjectMap(&scope->map, nrefs, ops, clasp); |
151 |
144713 |
scope->object = obj; |
152 |
144713 |
scope->flags = 0; |
153 |
144713 |
scope->dswIndex = 0; |
154 |
144713 |
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 |
144713 |
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 |
144713 |
{ |
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 |
144713 |
if (scope->table) |
196 |
65339 |
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 |
144713 |
JS_free(cx, scope); |
204 |
|
} |
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 |
4329402 |
{ |
248 |
4329402 |
JSHashNumber hash0, hash1, hash2; |
249 |
4329402 |
int hashShift, sizeLog2; |
250 |
4329402 |
JSScopeProperty *stored, *sprop, **spp, **firstRemoved; |
251 |
4329402 |
uint32 sizeMask; |
252 |
|
|
253 |
|
METER(searches); |
254 |
4329402 |
if (!scope->table) { |
255 |
|
/* Not enough properties to justify hashing: search from lastProp. */ |
256 |
1089816 |
JS_ASSERT(!SCOPE_HAD_MIDDLE_DELETE(scope)); |
257 |
3010688 |
for (spp = &scope->lastProp; (sprop = *spp); spp = &sprop->parent) { |
258 |
2316464 |
if (sprop->id == id) { |
259 |
|
METER(hits); |
260 |
395592 |
return spp; |
261 |
|
} |
262 |
|
} |
263 |
|
METER(misses); |
264 |
694224 |
return spp; |
265 |
|
} |
266 |
|
|
267 |
|
/* Compute the primary hash address. */ |
268 |
3239586 |
hash0 = SCOPE_HASH0(id); |
269 |
3239586 |
hashShift = scope->hashShift; |
270 |
3239586 |
hash1 = SCOPE_HASH1(hash0, hashShift); |
271 |
3239586 |
spp = scope->table + hash1; |
272 |
|
|
273 |
|
/* Miss: return space for a new entry. */ |
274 |
3239586 |
stored = *spp; |
275 |
3239586 |
if (SPROP_IS_FREE(stored)) { |
276 |
|
METER(misses); |
277 |
1906955 |
return spp; |
278 |
|
} |
279 |
|
|
280 |
|
/* Hit: return entry. */ |
281 |
1332631 |
sprop = SPROP_CLEAR_COLLISION(stored); |
282 |
1332631 |
if (sprop && sprop->id == id) { |
283 |
|
METER(hits); |
284 |
709091 |
return spp; |
285 |
|
} |
286 |
|
|
287 |
|
/* Collision: double hash. */ |
288 |
623540 |
sizeLog2 = JS_DHASH_BITS - hashShift; |
289 |
623540 |
hash2 = SCOPE_HASH2(hash0, sizeLog2, hashShift); |
290 |
623540 |
sizeMask = JS_BITMASK(sizeLog2); |
291 |
|
|
292 |
|
/* Save the first removed entry pointer so we can recycle it if adding. */ |
293 |
623540 |
if (SPROP_IS_REMOVED(stored)) { |
294 |
0 |
firstRemoved = spp; |
295 |
|
} else { |
296 |
623540 |
firstRemoved = NULL; |
297 |
623540 |
if (adding && !SPROP_HAD_COLLISION(stored)) |
298 |
142942 |
SPROP_FLAG_COLLISION(spp, sprop); |
299 |
|
} |
300 |
|
|
301 |
1372945 |
for (;;) { |
302 |
|
METER(steps); |
303 |
1281007 |
hash1 -= hash2; |
304 |
1281007 |
hash1 &= sizeMask; |
305 |
1281007 |
spp = scope->table + hash1; |
306 |
|
|
307 |
1281007 |
stored = *spp; |
308 |
1281007 |
if (SPROP_IS_FREE(stored)) { |
309 |
|
METER(stepMisses); |
310 |
513845 |
return (adding && firstRemoved) ? firstRemoved : spp; |
311 |
|
} |
312 |
|
|
313 |
767162 |
sprop = SPROP_CLEAR_COLLISION(stored); |
314 |
767162 |
if (sprop && sprop->id == id) { |
315 |
|
METER(stepHits); |
316 |
109695 |
return spp; |
317 |
|
} |
318 |
|
|
319 |
657467 |
if (SPROP_IS_REMOVED(stored)) { |
320 |
0 |
if (!firstRemoved) |
321 |
0 |
firstRemoved = spp; |
322 |
|
} else { |
323 |
657467 |
if (adding && !SPROP_HAD_COLLISION(stored)) |
324 |
91938 |
SPROP_FLAG_COLLISION(spp, sprop); |
325 |
|
} |
326 |
|
} |
327 |
|
|
328 |
|
/* NOTREACHED */ |
329 |
4329402 |
return NULL; |
330 |
|
} |
331 |
|
|
332 |
|
static JSBool |
333 |
|
ChangeScope(JSContext *cx, JSScope *scope, int change) |
334 |
48594 |
{ |
335 |
48594 |
int oldlog2, newlog2; |
336 |
48594 |
uint32 oldsize, newsize, nbytes; |
337 |
48594 |
JSScopeProperty **table, **oldtable, **spp, **oldspp, *sprop; |
338 |
|
|
339 |
|
/* Grow, shrink, or compress by changing scope->table. */ |
340 |
48594 |
oldlog2 = JS_DHASH_BITS - scope->hashShift; |
341 |
48594 |
newlog2 = oldlog2 + change; |
342 |
48594 |
oldsize = JS_BIT(oldlog2); |
343 |
48594 |
newsize = JS_BIT(newlog2); |
344 |
48594 |
nbytes = SCOPE_TABLE_NBYTES(newsize); |
345 |
48594 |
table = (JSScopeProperty **) calloc(nbytes, 1); |
346 |
48594 |
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 |
48594 |
scope->hashShift = JS_DHASH_BITS - newlog2; |
353 |
48594 |
scope->removedCount = 0; |
354 |
48594 |
oldtable = scope->table; |
355 |
48594 |
scope->table = table; |
356 |
|
|
357 |
|
/* Treat the above calloc as a JS_malloc, to match CreateScopeTable. */ |
358 |
48594 |
cx->runtime->gcMallocBytes += nbytes; |
359 |
|
|
360 |
|
/* Copy only live entries, leaving removed and free ones behind. */ |
361 |
845426 |
for (oldspp = oldtable; oldsize != 0; oldspp++) { |
362 |
796832 |
sprop = SPROP_FETCH(oldspp); |
363 |
796832 |
if (sprop) { |
364 |
597624 |
spp = js_SearchScope(scope, sprop->id, JS_TRUE); |
365 |
597624 |
JS_ASSERT(SPROP_IS_FREE(*spp)); |
366 |
597624 |
*spp = sprop; |
367 |
|
} |
368 |
796832 |
oldsize--; |
369 |
|
} |
370 |
|
|
371 |
|
/* Finally, free the old table storage. */ |
372 |
48594 |
JS_free(cx, oldtable); |
373 |
48594 |
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 |
190894 |
{ |
386 |
190894 |
const JSScopeProperty *sprop = (const JSScopeProperty *)key; |
387 |
190894 |
JSDHashNumber hash; |
388 |
190894 |
JSPropertyOp gsop; |
389 |
|
|
390 |
|
/* Accumulate from least to most random so the low bits are most random. */ |
391 |
190894 |
hash = 0; |
392 |
190894 |
gsop = sprop->getter; |
393 |
190894 |
if (gsop) |
394 |
157166 |
hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ (jsword)gsop; |
395 |
190894 |
gsop = sprop->setter; |
396 |
190894 |
if (gsop) |
397 |
56660 |
hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ (jsword)gsop; |
398 |
|
|
399 |
190894 |
hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) |
400 |
|
^ (sprop->flags & ~SPROP_FLAGS_NOT_MATCHED); |
401 |
|
|
402 |
190894 |
hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->attrs; |
403 |
190894 |
hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->shortid; |
404 |
190894 |
hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->slot; |
405 |
190894 |
hash = (hash >> (JS_DHASH_BITS - 4)) ^ (hash << 4) ^ sprop->id; |
406 |
190894 |
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 |
166226 |
{ |
434 |
166226 |
const JSPropertyTreeEntry *entry = (const JSPropertyTreeEntry *)hdr; |
435 |
166226 |
const JSScopeProperty *sprop = entry->child; |
436 |
166226 |
const JSScopeProperty *kprop = (const JSScopeProperty *)key; |
437 |
|
|
438 |
166226 |
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 |
26695 |
{ |
485 |
26695 |
JSScopeProperty *sprop; |
486 |
|
|
487 |
26695 |
sprop = rt->propertyFreeList; |
488 |
26695 |
if (sprop) { |
489 |
0 |
FREENODE_REMOVE(sprop); |
490 |
|
} else { |
491 |
26695 |
JS_ARENA_ALLOCATE_CAST(sprop, JSScopeProperty *, |
492 |
|
&rt->propertyArenaPool, |
493 |
|
sizeof(JSScopeProperty)); |
494 |
26695 |
if (!sprop) |
495 |
0 |
return NULL; |
496 |
|
} |
497 |
|
|
498 |
|
JS_RUNTIME_METER(rt, livePropTreeNodes); |
499 |
|
JS_RUNTIME_METER(rt, totalPropTreeNodes); |
500 |
26695 |
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 |
786 |
{ |
521 |
786 |
PropTreeKidsChunk *chunk; |
522 |
|
|
523 |
786 |
chunk = calloc(1, sizeof *chunk); |
524 |
786 |
if (!chunk) |
525 |
0 |
return NULL; |
526 |
786 |
JS_ASSERT(((jsuword)chunk & CHUNKY_KIDS_TAG) == 0); |
527 |
|
JS_RUNTIME_METER(rt, propTreeKidsChunks); |
528 |
786 |
return chunk; |
529 |
|
} |
530 |
|
|
531 |
|
static void |
532 |
|
DestroyPropTreeKidsChunk(JSRuntime *rt, PropTreeKidsChunk *chunk) |
533 |
786 |
{ |
534 |
|
JS_RUNTIME_UNMETER(rt, propTreeKidsChunks); |
535 |
786 |
free(chunk); |
536 |
|
} |
537 |
|
|
538 |
|
/* NB: Called with the runtime lock held. */ |
539 |
|
static JSBool |
540 |
|
InsertPropertyTreeChild(JSRuntime *rt, JSScopeProperty *parent, |
541 |
|
JSScopeProperty *child, PropTreeKidsChunk *sweptChunk) |
542 |
50771 |
{ |
543 |
50771 |
JSPropertyTreeEntry *entry; |
544 |
50771 |
JSScopeProperty **childp, *kids, *sprop; |
545 |
50771 |
PropTreeKidsChunk *chunk, **chunkp; |
546 |
50771 |
uintN i; |
547 |
|
|
548 |
50771 |
JS_ASSERT(!parent || child->parent != parent); |
549 |
|
|
550 |
50771 |
if (!parent) { |
551 |
23585 |
entry = (JSPropertyTreeEntry *) |
552 |
|
JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_ADD); |
553 |
23585 |
if (!entry) |
554 |
0 |
return JS_FALSE; |
555 |
23585 |
childp = &entry->child; |
556 |
23585 |
sprop = *childp; |
557 |
23585 |
if (!sprop) { |
558 |
23505 |
*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 |
27186 |
JS_ASSERT(sprop != child && SPROP_MATCH(sprop, child)); |
577 |
|
JS_RUNTIME_METER(rt, duplicatePropTreeNodes); |
578 |
|
} |
579 |
|
} else { |
580 |
27186 |
childp = &parent->kids; |
581 |
27186 |
kids = *childp; |
582 |
27186 |
if (kids) { |
583 |
2742 |
if (KIDS_IS_CHUNKY(kids)) { |
584 |
2315 |
chunk = KIDS_TO_CHUNK(kids); |
585 |
4179 |
do { |
586 |
34886 |
for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) { |
587 |
32646 |
childp = &chunk->kids[i]; |
588 |
32646 |
sprop = *childp; |
589 |
32646 |
if (!sprop) |
590 |
1939 |
goto insert; |
591 |
|
|
592 |
30707 |
JS_ASSERT(sprop != child); |
593 |
30707 |
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 |
30707 |
JS_ASSERT(sprop != child); |
601 |
|
JS_RUNTIME_METER(rt, duplicatePropTreeNodes); |
602 |
|
} |
603 |
|
} |
604 |
2240 |
chunkp = &chunk->next; |
605 |
2240 |
} while ((chunk = *chunkp) != NULL); |
606 |
|
|
607 |
376 |
if (sweptChunk) { |
608 |
17 |
chunk = sweptChunk; |
609 |
|
} else { |
610 |
359 |
chunk = NewPropTreeKidsChunk(rt); |
611 |
359 |
if (!chunk) |
612 |
0 |
return JS_FALSE; |
613 |
|
} |
614 |
376 |
*chunkp = chunk; |
615 |
376 |
childp = &chunk->kids[0]; |
616 |
|
} else { |
617 |
427 |
sprop = kids; |
618 |
427 |
JS_ASSERT(sprop != child); |
619 |
427 |
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 |
427 |
chunk = NewPropTreeKidsChunk(rt); |
630 |
427 |
if (!chunk) |
631 |
0 |
return JS_FALSE; |
632 |
427 |
parent->kids = CHUNK_TO_KIDS(chunk); |
633 |
427 |
chunk->kids[0] = sprop; |
634 |
427 |
childp = &chunk->kids[1]; |
635 |
|
} |
636 |
|
} |
637 |
|
insert: |
638 |
27186 |
*childp = child; |
639 |
|
} |
640 |
|
|
641 |
50771 |
child->parent = parent; |
642 |
50771 |
return JS_TRUE; |
643 |
|
} |
644 |
|
|
645 |
|
/* NB: Called with the runtime lock held. */ |
646 |
|
static void |
647 |
|
RemovePropertyTreeChild(JSRuntime *rt, JSScopeProperty *child) |
648 |
26695 |
{ |
649 |
26695 |
JSPropertyTreeEntry *entry; |
650 |
26695 |
JSScopeProperty *parent, *kids, *kid; |
651 |
26695 |
PropTreeKidsChunk *list, *chunk, **chunkp, *lastChunk; |
652 |
26695 |
uintN i, j; |
653 |
|
|
654 |
26695 |
parent = child->parent; |
655 |
26695 |
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 |
24765 |
entry = (JSPropertyTreeEntry *) |
662 |
|
JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_LOOKUP); |
663 |
|
|
664 |
24765 |
if (entry->child == child) |
665 |
24685 |
JS_DHashTableRawRemove(&rt->propertyTreeHash, &entry->hdr); |
666 |
|
} else { |
667 |
1930 |
kids = parent->kids; |
668 |
1930 |
if (KIDS_IS_CHUNKY(kids)) { |
669 |
1802 |
list = chunk = KIDS_TO_CHUNK(kids); |
670 |
1802 |
chunkp = &list; |
671 |
|
|
672 |
3685 |
do { |
673 |
28811 |
for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) { |
674 |
26928 |
if (chunk->kids[i] == child) { |
675 |
1802 |
lastChunk = chunk; |
676 |
1802 |
if (!lastChunk->next) { |
677 |
1584 |
j = i + 1; |
678 |
|
} else { |
679 |
218 |
j = 0; |
680 |
333 |
do { |
681 |
333 |
chunkp = &lastChunk->next; |
682 |
333 |
lastChunk = *chunkp; |
683 |
333 |
} while (lastChunk->next); |
684 |
|
} |
685 |
4540 |
for (; j < MAX_KIDS_PER_CHUNK; j++) { |
686 |
2948 |
if (!lastChunk->kids[j]) |
687 |
1579 |
break; |
688 |
|
} |
689 |
1802 |
--j; |
690 |
1802 |
if (chunk != lastChunk || j > i) |
691 |
367 |
chunk->kids[i] = lastChunk->kids[j]; |
692 |
1802 |
lastChunk->kids[j] = NULL; |
693 |
1802 |
if (j == 0) { |
694 |
358 |
*chunkp = NULL; |
695 |
358 |
if (!list) |
696 |
2 |
parent->kids = NULL; |
697 |
358 |
DestroyPropTreeKidsChunk(rt, lastChunk); |
698 |
|
} |
699 |
358 |
return; |
700 |
|
} |
701 |
|
} |
702 |
|
|
703 |
1883 |
chunkp = &chunk->next; |
704 |
1883 |
} while ((chunk = *chunkp) != NULL); |
705 |
|
} else { |
706 |
128 |
kid = kids; |
707 |
128 |
if (kid == child) |
708 |
128 |
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 |
1223311 |
{ |
722 |
1223311 |
JSRuntime *rt; |
723 |
1223311 |
JSPropertyTreeEntry *entry; |
724 |
1223311 |
JSScopeProperty *sprop; |
725 |
1223311 |
PropTreeKidsChunk *chunk; |
726 |
1223311 |
uintN i; |
727 |
|
|
728 |
1223311 |
rt = cx->runtime; |
729 |
1223311 |
if (!parent) { |
730 |
142544 |
JS_LOCK_RUNTIME(rt); |
731 |
|
|
732 |
142544 |
entry = (JSPropertyTreeEntry *) |
733 |
|
JS_DHashTableOperate(&rt->propertyTreeHash, child, JS_DHASH_ADD); |
734 |
142544 |
if (!entry) |
735 |
0 |
goto out_of_memory; |
736 |
|
|
737 |
142544 |
sprop = entry->child; |
738 |
142544 |
if (sprop) |
739 |
141364 |
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 |
1080767 |
entry = NULL; |
754 |
1080767 |
sprop = parent->kids; |
755 |
1080767 |
if (sprop) { |
756 |
1056423 |
if (KIDS_IS_CHUNKY(sprop)) { |
757 |
38238 |
chunk = KIDS_TO_CHUNK(sprop); |
758 |
44400 |
do { |
759 |
210080 |
for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) { |
760 |
203874 |
sprop = chunk->kids[i]; |
761 |
203874 |
if (!sprop) |
762 |
701 |
goto not_found; |
763 |
|
|
764 |
203173 |
if (SPROP_MATCH(sprop, child)) |
765 |
37493 |
return sprop; |
766 |
|
} |
767 |
6206 |
} while ((chunk = chunk->next) != NULL); |
768 |
|
} else { |
769 |
1018185 |
if (SPROP_MATCH(sprop, child)) |
770 |
1017759 |
return sprop; |
771 |
|
} |
772 |
|
} |
773 |
|
|
774 |
|
not_found: |
775 |
26695 |
JS_LOCK_RUNTIME(rt); |
776 |
|
} |
777 |
|
|
778 |
26695 |
sprop = NewScopeProperty(rt); |
779 |
26695 |
if (!sprop) |
780 |
0 |
goto out_of_memory; |
781 |
|
|
782 |
26695 |
sprop->id = child->id; |
783 |
26695 |
sprop->getter = child->getter; |
784 |
26695 |
sprop->setter = child->setter; |
785 |
26695 |
sprop->slot = child->slot; |
786 |
26695 |
sprop->attrs = child->attrs; |
787 |
26695 |
sprop->flags = child->flags; |
788 |
26695 |
sprop->shortid = child->shortid; |
789 |
26695 |
sprop->parent = sprop->kids = NULL; |
790 |
26695 |
if (!parent) { |
791 |
1180 |
entry->child = sprop; |
792 |
|
} else { |
793 |
25515 |
if (!InsertPropertyTreeChild(rt, parent, sprop, NULL)) |
794 |
0 |
goto out_of_memory; |
795 |
|
} |
796 |
|
|
797 |
|
out: |
798 |
168059 |
JS_UNLOCK_RUNTIME(rt); |
799 |
168059 |
return sprop; |
800 |
|
|
801 |
|
out_of_memory: |
802 |
0 |
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 |
0 |
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 |
|
} |
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 |
1232023 |
{ |
872 |
1232023 |
JSScopeProperty **spp, *sprop, *overwriting, **spvec, **spp2, child; |
873 |
1232023 |
uint32 size, splen, i; |
874 |
1232023 |
int change; |
875 |
|
|
876 |
1232023 |
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 |
1232023 |
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 |
1232023 |
if (getter == JS_PropertyStub) |
895 |
145712 |
getter = NULL; |
896 |
1232023 |
if (setter == JS_PropertyStub) |
897 |
1163587 |
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 |
1232023 |
spp = js_SearchScope(scope, id, JS_TRUE); |
904 |
1232023 |
sprop = overwriting = SPROP_FETCH(spp); |
905 |
1232023 |
if (!sprop) { |
906 |
|
/* Check whether we need to grow, if the load factor is >= .75. */ |
907 |
1223279 |
size = SCOPE_CAPACITY(scope); |
908 |
1223279 |
if (scope->entryCount + scope->removedCount >= size - (size >> 2)) { |
909 |
48594 |
if (scope->removedCount >= size >> 2) { |
910 |
|
METER(compresses); |
911 |
0 |
change = 0; |
912 |
|
} else { |
913 |
|
METER(grows); |
914 |
48594 |
change = 1; |
915 |
|
} |
916 |
48594 |
if (!ChangeScope(cx, scope, change) && |
917 |
|
scope->entryCount + scope->removedCount == size - 1) { |
918 |
|
METER(addFailures); |
919 |
0 |
return NULL; |
920 |
|
} |
921 |
48594 |
spp = js_SearchScope(scope, id, JS_TRUE); |
922 |
48594 |
JS_ASSERT(!SPROP_FETCH(spp)); |
923 |
|
} |
924 |
|
} else { |
925 |
|
/* Property exists: js_SearchScope must have returned a valid entry. */ |
926 |
8744 |
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 |
8744 |
if (!(attrs & JSPROP_SHARED) && |
935 |
|
slot == SPROP_INVALID_SLOT && |
936 |
|
SPROP_HAS_VALID_SLOT(sprop, scope)) { |
937 |
8712 |
slot = sprop->slot; |
938 |
|
} |
939 |
8744 |
if (SPROP_MATCH_PARAMS_AFTER_ID(sprop, getter, setter, slot, attrs, |
940 |
|
flags, shortid)) { |
941 |
|
METER(redundantAdds); |
942 |
8712 |
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 |
32 |
if (flags & SPROP_IS_DUPLICATE) { |
954 |
32 |
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 |
0 |
if (sprop == SCOPE_LAST_PROP(scope)) { |
972 |
0 |
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 |
0 |
} 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 |
0 |
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 |
0 |
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 |
32 |
if (scope->table) |
1001 |
0 |
SPROP_STORE_PRESERVING_COLLISION(spp, NULL); |
1002 |
32 |
scope->entryCount--; |
1003 |
|
CHECK_ANCESTOR_LINE(scope, JS_TRUE); |
1004 |
32 |
sprop = NULL; |
1005 |
|
} |
1006 |
|
|
1007 |
1223311 |
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 |
1223311 |
if (SCOPE_HAD_MIDDLE_DELETE(scope)) { |
1017 |
0 |
JS_ASSERT(scope->table); |
1018 |
|
CHECK_ANCESTOR_LINE(scope, JS_TRUE); |
1019 |
|
|
1020 |
0 |
splen = scope->entryCount; |
1021 |
0 |
if (splen == 0) { |
1022 |
0 |
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 |
0 |
spvec = (JSScopeProperty **) |
1030 |
|
JS_malloc(cx, SCOPE_TABLE_NBYTES(splen)); |
1031 |
0 |
if (!spvec) |
1032 |
0 |
goto fail_overwrite; |
1033 |
0 |
i = splen; |
1034 |
0 |
sprop = SCOPE_LAST_PROP(scope); |
1035 |
0 |
JS_ASSERT(sprop); |
1036 |
0 |
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 |
0 |
if (!SCOPE_GET_PROPERTY(scope, sprop->id)) |
1045 |
0 |
continue; |
1046 |
|
|
1047 |
0 |
JS_ASSERT(sprop != overwriting); |
1048 |
0 |
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 |
0 |
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 |
0 |
spvec[--i] = sprop; |
1074 |
0 |
} while ((sprop = sprop->parent) != NULL); |
1075 |
0 |
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 |
0 |
do { |
1083 |
0 |
if (spvec[i]->parent == sprop) { |
1084 |
0 |
sprop = spvec[i]; |
1085 |
|
} else { |
1086 |
0 |
sprop = GetPropertyTreeChild(cx, sprop, spvec[i]); |
1087 |
0 |
if (!sprop) { |
1088 |
0 |
JS_free(cx, spvec); |
1089 |
0 |
goto fail_overwrite; |
1090 |
|
} |
1091 |
|
|
1092 |
0 |
spp2 = js_SearchScope(scope, sprop->id, JS_FALSE); |
1093 |
0 |
JS_ASSERT(SPROP_FETCH(spp2) == spvec[i]); |
1094 |
0 |
SPROP_STORE_PRESERVING_COLLISION(spp2, sprop); |
1095 |
|
} |
1096 |
0 |
} while (++i < splen); |
1097 |
0 |
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 |
0 |
scope->lastProp = sprop; |
1106 |
|
CHECK_ANCESTOR_LINE(scope, JS_FALSE); |
1107 |
|
JS_RUNTIME_METER(cx->runtime, middleDeleteFixups); |
1108 |
|
} |
1109 |
|
|
1110 |
0 |
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 |
1223311 |
if (!(flags & SPROP_IS_ALIAS)) { |
1120 |
1223199 |
if (attrs & JSPROP_SHARED) { |
1121 |
22176 |
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 |
1201023 |
if (slot != SPROP_INVALID_SLOT) |
1131 |
0 |
JS_ASSERT(overwriting); |
1132 |
1201023 |
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 |
1223311 |
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 |
1223311 |
child.id = id; |
1151 |
1223311 |
child.getter = getter; |
1152 |
1223311 |
child.setter = setter; |
1153 |
1223311 |
child.slot = slot; |
1154 |
1223311 |
child.attrs = attrs; |
1155 |
1223311 |
child.flags = flags; |
1156 |
1223311 |
child.shortid = shortid; |
1157 |
1223311 |
sprop = GetPropertyTreeChild(cx, scope->lastProp, &child); |
1158 |
1223311 |
if (!sprop) |
1159 |
0 |
goto fail_overwrite; |
1160 |
|
|
1161 |
|
/* Store the tree node pointer in the table entry for id. */ |
1162 |
1223311 |
if (scope->table) |
1163 |
712333 |
SPROP_STORE_PRESERVING_COLLISION(spp, sprop); |
1164 |
1223311 |
scope->entryCount++; |
1165 |
1223311 |
scope->lastProp = sprop; |
1166 |
|
CHECK_ANCESTOR_LINE(scope, JS_FALSE); |
1167 |
1223311 |
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 |
1223311 |
if (!scope->table && scope->entryCount >= SCOPE_HASH_THRESHOLD) |
1181 |
65339 |
(void) CreateScopeTable(cx, scope, JS_FALSE); |
1182 |
|
} |
1183 |
|
|
1184 |
|
METER(adds); |
1185 |
1223311 |
return sprop; |
1186 |
|
|
1187 |
|
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 |
0 |
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 |
|
} |
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 |
1184 |
{ |
1231 |
1184 |
JSScopeProperty child, *newsprop, **spp; |
1232 |
|
|
1233 |
|
CHECK_ANCESTOR_LINE(scope, JS_TRUE); |
1234 |
|
|
1235 |
|
/* Allow only shared (slot-less) => unshared (slot-full) transition. */ |
1236 |
1184 |
attrs |= sprop->attrs & mask; |
1237 |
1184 |
JS_ASSERT(!((attrs ^ sprop->attrs) & JSPROP_SHARED) || |
1238 |
|
!(attrs & JSPROP_SHARED)); |
1239 |
1184 |
if (getter == JS_PropertyStub) |
1240 |
0 |
getter = NULL; |
1241 |
1184 |
if (setter == JS_PropertyStub) |
1242 |
0 |
setter = NULL; |
1243 |
1184 |
if (sprop->attrs == attrs && |
1244 |
|
sprop->getter == getter && |
1245 |
|
sprop->setter == setter) { |
1246 |
1184 |
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 |
0 |
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 |
0 |
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 |
0 |
JSScopeProperty **spp, *stored, *sprop; |
1303 |
0 |
uint32 size; |
1304 |
|
|
1305 |
0 |
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 |
0 |
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 |
0 |
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 |
|
} |
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 |
32 |
{ |
1493 |
32 |
JSArena **ap, *a; |
1494 |
32 |
JSScopeProperty *limit, *sprop, *parent, *kids, *kid; |
1495 |
32 |
uintN liveCount; |
1496 |
32 |
PropTreeKidsChunk *chunk, *nextChunk; |
1497 |
32 |
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 |
32 |
ap = &rt->propertyArenaPool.first.next; |
1543 |
254 |
while ((a = *ap) != NULL) { |
1544 |
222 |
limit = (JSScopeProperty *) a->avail; |
1545 |
222 |
liveCount = 0; |
1546 |
53612 |
for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) { |
1547 |
|
/* If the id is null, sprop is already on the freelist. */ |
1548 |
53390 |
if (sprop->id == JSVAL_NULL) |
1549 |
2084 |
continue; |
1550 |
|
|
1551 |
|
/* If the mark bit is set, sprop is alive, so we skip it. */ |
1552 |
51306 |
if (sprop->flags & SPROP_MARK) { |
1553 |
24611 |
sprop->flags &= ~SPROP_MARK; |
1554 |
24611 |
liveCount++; |
1555 |
24611 |
continue; |
1556 |
|
} |
1557 |
|
|
1558 |
|
/* Ok, sprop is garbage to collect: unlink it from its parent. */ |
1559 |
26695 |
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 |
26695 |
kids = sprop->kids; |
1584 |
26695 |
if (kids) { |
1585 |
24314 |
sprop->kids = NULL; |
1586 |
24314 |
parent = sprop->parent; |
1587 |
|
/* Validate that grandparent has no kids or chunky kids. */ |
1588 |
24314 |
JS_ASSERT(!parent || !parent->kids || |
1589 |
|
KIDS_IS_CHUNKY(parent->kids)); |
1590 |
24314 |
if (KIDS_IS_CHUNKY(kids)) { |
1591 |
425 |
chunk = KIDS_TO_CHUNK(kids); |
1592 |
445 |
do { |
1593 |
445 |
nextChunk = chunk->next; |
1594 |
445 |
chunk->next = NULL; |
1595 |
1812 |
for (i = 0; i < MAX_KIDS_PER_CHUNK; i++) { |
1596 |
1790 |
kid = chunk->kids[i]; |
1597 |
1790 |
if (!kid) |
1598 |
423 |
break; |
1599 |
1367 |
JS_ASSERT(kid->parent == sprop); |
1600 |
|
|
1601 |
|
/* |
1602 |
|
* Clear a space in the kids array for possible |
1603 |
|
* re-use by InsertPropertyTreeChild. |
1604 |
|
*/ |
1605 |
1367 |
chunk->kids[i] = NULL; |
1606 |
1367 |
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 |
0 |
JS_ASSERT(!parent); |
1613 |
0 |
kid->parent = NULL; |
1614 |
|
} |
1615 |
|
} |
1616 |
445 |
if (!chunk->kids[0]) { |
1617 |
|
/* The chunk wasn't reused so we can free it */ |
1618 |
428 |
DestroyPropTreeKidsChunk(rt, chunk); |
1619 |
|
} |
1620 |
445 |
} while ((chunk = nextChunk) != NULL); |
1621 |
|
} else { |
1622 |
23889 |
kid = kids; |
1623 |
23889 |
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 |
0 |
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 |
26695 |
sprop->id = JSVAL_NULL; |
1638 |
26695 |
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 |
222 |
if (liveCount == 0) { |
1644 |
26806 |
for (sprop = (JSScopeProperty *) a->base; sprop < limit; sprop++) |
1645 |
26695 |
FREENODE_REMOVE(sprop); |
1646 |
111 |
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 |
111 |
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 |
|
} |
1680 |
|
|
1681 |
|
JSBool |
1682 |
|
js_InitPropertyTree(JSRuntime *rt) |
1683 |
16 |
{ |
1684 |
16 |
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 |
16 |
JS_InitArenaPool(&rt->propertyArenaPool, "properties", |
1690 |
|
256 * sizeof(JSScopeProperty), sizeof(void *)); |
1691 |
16 |
return JS_TRUE; |
1692 |
|
} |
1693 |
|
|
1694 |
|
void |
1695 |
|
js_FinishPropertyTree(JSRuntime *rt) |
1696 |
16 |
{ |
1697 |
16 |
if (rt->propertyTreeHash.ops) { |
1698 |
16 |
JS_DHashTableFinish(&rt->propertyTreeHash); |
1699 |
16 |
rt->propertyTreeHash.ops = NULL; |
1700 |
|
} |
1701 |
16 |
JS_FinishArenaPool(&rt->propertyArenaPool); |