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