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