Back to index

lightning-sunbird  0.9+nobinonly
jsscope.h
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  * vim: set ts=8 sw=4 et tw=78:
00003  *
00004  * ***** BEGIN LICENSE BLOCK *****
00005  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00006  *
00007  * The contents of this file are subject to the Mozilla Public License Version
00008  * 1.1 (the "License"); you may not use this file except in compliance with
00009  * the License. You may obtain a copy of the License at
00010  * http://www.mozilla.org/MPL/
00011  *
00012  * Software distributed under the License is distributed on an "AS IS" basis,
00013  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00014  * for the specific language governing rights and limitations under the
00015  * License.
00016  *
00017  * The Original Code is Mozilla Communicator client code, released
00018  * March 31, 1998.
00019  *
00020  * The Initial Developer of the Original Code is
00021  * Netscape Communications Corporation.
00022  * Portions created by the Initial Developer are Copyright (C) 1998
00023  * the Initial Developer. All Rights Reserved.
00024  *
00025  * Contributor(s):
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either of the GNU General Public License Version 2 or later (the "GPL"),
00029  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK ***** */
00040 
00041 #ifndef jsscope_h___
00042 #define jsscope_h___
00043 /*
00044  * JS symbol tables.
00045  */
00046 #include "jstypes.h"
00047 #include "jsobj.h"
00048 #include "jsprvtd.h"
00049 #include "jspubtd.h"
00050 
00051 #ifdef JS_THREADSAFE
00052 # include "jslock.h"
00053 #endif
00054 
00055 /*
00056  * Given P independent, non-unique properties each of size S words mapped by
00057  * all scopes in a runtime, construct a property tree of N nodes each of size
00058  * S+L words (L for tree linkage).  A nominal L value is 2 for leftmost-child
00059  * and right-sibling links.  We hope that the N < P by enough that the space
00060  * overhead of L, and the overhead of scope entries pointing at property tree
00061  * nodes, is worth it.
00062  *
00063  * The tree construction goes as follows.  If any empty scope in the runtime
00064  * has a property X added to it, find or create a node under the tree root
00065  * labeled X, and set scope->lastProp to point at that node.  If any non-empty
00066  * scope whose most recently added property is labeled Y has another property
00067  * labeled Z added, find or create a node for Z under the node that was added
00068  * for Y, and set scope->lastProp to point at that node.
00069  *
00070  * A property is labeled by its members' values: id, getter, setter, slot,
00071  * attributes, tiny or short id, and a field telling for..in order.  Note that
00072  * labels are not unique in the tree, but they are unique among a node's kids
00073  * (barring rare and benign multi-threaded race condition outcomes, see below)
00074  * and along any ancestor line from the tree root to a given leaf node (except
00075  * for the hard case of duplicate formal parameters to a function).
00076  *
00077  * Thus the root of the tree represents all empty scopes, and the first ply
00078  * of the tree represents all scopes containing one property, etc.  Each node
00079  * in the tree can stand for any number of scopes having the same ordered set
00080  * of properties, where that node was the last added to the scope.  (We need
00081  * not store the root of the tree as a node, and do not -- all we need are
00082  * links to its kids.)
00083  *
00084  * Sidebar on for..in loop order: ECMA requires no particular order, but this
00085  * implementation has promised and delivered property definition order, and
00086  * compatibility is king.  We could use an order number per property, which
00087  * would require a sort in js_Enumerate, and an entry order generation number
00088  * per scope.  An order number beats a list, which should be doubly-linked for
00089  * O(1) delete.  An even better scheme is to use a parent link in the property
00090  * tree, so that the ancestor line can be iterated from scope->lastProp when
00091  * filling in a JSIdArray from back to front.  This parent link also helps the
00092  * GC to sweep properties iteratively.
00093  *
00094  * What if a property Y is deleted from a scope?  If Y is the last property in
00095  * the scope, we simply adjust the scope's lastProp member after we remove the
00096  * scope's hash-table entry pointing at that property node.  The parent link
00097  * mentioned in the for..in sidebar above makes this adjustment O(1).  But if
00098  * Y comes between X and Z in the scope, then we might have to "fork" the tree
00099  * at X, leaving X->Y->Z in case other scopes have those properties added in
00100  * that order; and to finish the fork, we'd add a node labeled Z with the path
00101  * X->Z, if it doesn't exist.  This could lead to lots of extra nodes, and to
00102  * O(n^2) growth when deleting lots of properties.
00103  *
00104  * Rather, for O(1) growth all around, we should share the path X->Y->Z among
00105  * scopes having those three properties added in that order, and among scopes
00106  * having only X->Z where Y was deleted.  All such scopes have a lastProp that
00107  * points to the Z child of Y.  But a scope in which Y was deleted does not
00108  * have a table entry for Y, and when iterating that scope by traversing the
00109  * ancestor line from Z, we will have to test for a table entry for each node,
00110  * skipping nodes that lack entries.
00111  *
00112  * What if we add Y again?  X->Y->Z->Y is wrong and we'll enumerate Y twice.
00113  * Therefore we must fork in such a case, if not earlier.  Because delete is
00114  * "bursty", we should not fork eagerly.  Delaying a fork till we are at risk
00115  * of adding Y after it was deleted already requires a flag in the JSScope, to
00116  * wit, SCOPE_MIDDLE_DELETE.
00117  *
00118  * What about thread safety?  If the property tree operations done by requests
00119  * are find-node and insert-node, then the only hazard is duplicate insertion.
00120  * This is harmless except for minor bloat.  When all requests have ended or
00121  * been suspended, the GC is free to sweep the tree after marking all nodes
00122  * reachable from scopes, performing remove-node operations as needed.  Note
00123  * also that the stable storage of the property nodes during active requests
00124  * permits the property cache (see jsinterp.h) to dereference JSScopeProperty
00125  * weak references safely.
00126  *
00127  * Is the property tree worth it compared to property storage in each table's
00128  * entries?  To decide, we must find the relation <> between the words used
00129  * with a property tree and the words required without a tree.
00130  *
00131  * Model all scopes as one super-scope of capacity T entries (T a power of 2).
00132  * Let alpha be the load factor of this double hash-table.  With the property
00133  * tree, each entry in the table is a word-sized pointer to a node that can be
00134  * shared by many scopes.  But all such pointers are overhead compared to the
00135  * situation without the property tree, where the table stores property nodes
00136  * directly, as entries each of size S words.  With the property tree, we need
00137  * L=2 extra words per node for siblings and kids pointers.  Without the tree,
00138  * (1-alpha)*S*T words are wasted on free or removed sentinel-entries required
00139  * by double hashing.
00140  *
00141  * Therefore,
00142  *
00143  *      (property tree)                 <> (no property tree)
00144  *      N*(S+L) + T                     <> S*T
00145  *      N*(S+L) + T                     <> P*S + (1-alpha)*S*T
00146  *      N*(S+L) + alpha*T + (1-alpha)*T <> P*S + (1-alpha)*S*T
00147  *
00148  * Note that P is alpha*T by definition, so
00149  *
00150  *      N*(S+L) + P + (1-alpha)*T <> P*S + (1-alpha)*S*T
00151  *      N*(S+L)                   <> P*S - P + (1-alpha)*S*T - (1-alpha)*T
00152  *      N*(S+L)                   <> (P + (1-alpha)*T) * (S-1)
00153  *      N*(S+L)                   <> (P + (1-alpha)*P/alpha) * (S-1)
00154  *      N*(S+L)                   <> P * (1/alpha) * (S-1)
00155  *
00156  * Let N = P*beta for a compression ratio beta, beta <= 1:
00157  *
00158  *      P*beta*(S+L) <> P * (1/alpha) * (S-1)
00159  *      beta*(S+L)   <> (S-1)/alpha
00160  *      beta         <> (S-1)/((S+L)*alpha)
00161  *
00162  * For S = 6 (32-bit architectures) and L = 2, the property tree wins iff
00163  *
00164  *      beta < 5/(8*alpha)
00165  *
00166  * We ensure that alpha <= .75, so the property tree wins if beta < .83_.  An
00167  * average beta from recent Mozilla browser startups was around .6.
00168  *
00169  * Can we reduce L?  Observe that the property tree degenerates into a list of
00170  * lists if at most one property Y follows X in all scopes.  In or near such a
00171  * case, we waste a word on the right-sibling link outside of the root ply of
00172  * the tree.  Note also that the root ply tends to be large, so O(n^2) growth
00173  * searching it is likely, indicating the need for hashing (but with increased
00174  * thread safety costs).
00175  *
00176  * If only K out of N nodes in the property tree have more than one child, we
00177  * could eliminate the sibling link and overlay a children list or hash-table
00178  * pointer on the leftmost-child link (which would then be either null or an
00179  * only-child link; the overlay could be tagged in the low bit of the pointer,
00180  * or flagged elsewhere in the property tree node, although such a flag must
00181  * not be considered when comparing node labels during tree search).
00182  *
00183  * For such a system, L = 1 + (K * averageChildrenTableSize) / N instead of 2.
00184  * If K << N, L approaches 1 and the property tree wins if beta < .95.
00185  *
00186  * We observe that fan-out below the root ply of the property tree appears to
00187  * have extremely low degree (see the MeterPropertyTree code that histograms
00188  * child-counts in jsscope.c), so instead of a hash-table we use a linked list
00189  * of child node pointer arrays ("kid chunks").  The details are isolated in
00190  * jsscope.c; others must treat JSScopeProperty.kids as opaque.  We leave it
00191  * strongly typed for debug-ability of the common (null or one-kid) cases.
00192  *
00193  * One final twist (can you stand it?): the mean number of entries per scope
00194  * in Mozilla is < 5, with a large standard deviation (~8).  Instead of always
00195  * allocating scope->table, we leave it null while initializing all the other
00196  * scope members as if it were non-null and minimal-length.  Until a property
00197  * is added that crosses the threshold of 6 or more entries for hashing, or
00198  * until a "middle delete" occurs, we use linear search from scope->lastProp
00199  * to find a given id, and save on the space overhead of a hash table.
00200  */
00201 
00202 struct JSScope {
00203     JSObjectMap     map;                /* base class state */
00204     JSObject        *object;            /* object that owns this scope */
00205     uint8           flags;              /* flags, see below */
00206     int8            hashShift;          /* multiplicative hash shift */
00207     uint16          spare;              /* reserved */
00208     uint32          entryCount;         /* number of entries in table */
00209     uint32          removedCount;       /* removed entry sentinels in table */
00210     JSScopeProperty **table;            /* table of ptrs to shared tree nodes */
00211     JSScopeProperty *lastProp;          /* pointer to last property added */
00212 #ifdef JS_THREADSAFE
00213     JSContext       *ownercx;           /* creating context, NULL if shared */
00214     JSThinLock      lock;               /* binary semaphore protecting scope */
00215     union {                             /* union lockful and lock-free state: */
00216         jsrefcount  count;              /* lock entry count for reentrancy */
00217         JSScope     *link;              /* next link in rt->scopeSharingTodo */
00218     } u;
00219 #ifdef DEBUG
00220     const char      *file[4];           /* file where lock was (re-)taken */
00221     unsigned int    line[4];            /* line where lock was (re-)taken */
00222 #endif
00223 #endif
00224 };
00225 
00226 #define OBJ_SCOPE(obj)                  ((JSScope *)(obj)->map)
00227 
00228 /* By definition, hashShift = JS_DHASH_BITS - log2(capacity). */
00229 #define SCOPE_CAPACITY(scope)           JS_BIT(JS_DHASH_BITS-(scope)->hashShift)
00230 
00231 /* Scope flags and some macros to hide them from other files than jsscope.c. */
00232 #define SCOPE_MIDDLE_DELETE             0x0001
00233 #define SCOPE_SEALED                    0x0002
00234 
00235 #define SCOPE_HAD_MIDDLE_DELETE(scope)  ((scope)->flags & SCOPE_MIDDLE_DELETE)
00236 #define SCOPE_SET_MIDDLE_DELETE(scope)  ((scope)->flags |= SCOPE_MIDDLE_DELETE)
00237 #define SCOPE_CLR_MIDDLE_DELETE(scope)  ((scope)->flags &= ~SCOPE_MIDDLE_DELETE)
00238 
00239 #define SCOPE_IS_SEALED(scope)          ((scope)->flags & SCOPE_SEALED)
00240 #define SCOPE_SET_SEALED(scope)         ((scope)->flags |= SCOPE_SEALED)
00241 #if 0
00242 /*
00243  * Don't define this, it can't be done safely because JS_LOCK_OBJ will avoid
00244  * taking the lock if the object owns its scope and the scope is sealed.
00245  */
00246 #define SCOPE_CLR_SEALED(scope)         ((scope)->flags &= ~SCOPE_SEALED)
00247 #endif
00248 
00249 /*
00250  * A little information hiding for scope->lastProp, in case it ever becomes
00251  * a tagged pointer again.
00252  */
00253 #define SCOPE_LAST_PROP(scope)          ((scope)->lastProp)
00254 #define SCOPE_REMOVE_LAST_PROP(scope)   ((scope)->lastProp =                  \
00255                                          (scope)->lastProp->parent)
00256 
00257 struct JSScopeProperty {
00258     jsid            id;                 /* int-tagged jsval/untagged JSAtom* */
00259     JSPropertyOp    getter;             /* getter and setter hooks or objects */
00260     JSPropertyOp    setter;
00261     uint32          slot;               /* index in obj->slots vector */
00262     uint8           attrs;              /* attributes, see jsapi.h JSPROP_* */
00263     uint8           flags;              /* flags, see below for defines */
00264     int16           shortid;            /* tinyid, or local arg/var index */
00265     JSScopeProperty *parent;            /* parent node, reverse for..in order */
00266     JSScopeProperty *kids;              /* null, single child, or a tagged ptr
00267                                            to many-kids data structure */
00268 };
00269 
00270 /* JSScopeProperty pointer tag bit indicating a collision. */
00271 #define SPROP_COLLISION                 ((jsuword)1)
00272 #define SPROP_REMOVED                   ((JSScopeProperty *) SPROP_COLLISION)
00273 
00274 /* Macros to get and set sprop pointer values and collision flags. */
00275 #define SPROP_IS_FREE(sprop)            ((sprop) == NULL)
00276 #define SPROP_IS_REMOVED(sprop)         ((sprop) == SPROP_REMOVED)
00277 #define SPROP_IS_LIVE(sprop)            ((sprop) > SPROP_REMOVED)
00278 #define SPROP_FLAG_COLLISION(spp,sprop) (*(spp) = (JSScopeProperty *)         \
00279                                          ((jsuword)(sprop) | SPROP_COLLISION))
00280 #define SPROP_HAD_COLLISION(sprop)      ((jsuword)(sprop) & SPROP_COLLISION)
00281 #define SPROP_FETCH(spp)                SPROP_CLEAR_COLLISION(*(spp))
00282 
00283 #define SPROP_CLEAR_COLLISION(sprop)                                          \
00284     ((JSScopeProperty *) ((jsuword)(sprop) & ~SPROP_COLLISION))
00285 
00286 #define SPROP_STORE_PRESERVING_COLLISION(spp, sprop)                          \
00287     (*(spp) = (JSScopeProperty *) ((jsuword)(sprop)                           \
00288                                    | SPROP_HAD_COLLISION(*(spp))))
00289 
00290 /* Bits stored in sprop->flags. */
00291 #define SPROP_MARK                      0x01
00292 #define SPROP_IS_DUPLICATE              0x02
00293 #define SPROP_IS_ALIAS                  0x04
00294 #define SPROP_HAS_SHORTID               0x08
00295 #define SPROP_IS_HIDDEN                 0x10    /* a normally-hidden property,
00296                                                    e.g., function arg or var */
00297 
00298 /*
00299  * If SPROP_HAS_SHORTID is set in sprop->flags, we use sprop->shortid rather
00300  * than id when calling sprop's getter or setter.
00301  */
00302 #define SPROP_USERID(sprop)                                                   \
00303     (((sprop)->flags & SPROP_HAS_SHORTID) ? INT_TO_JSVAL((sprop)->shortid)    \
00304                                           : ID_TO_VALUE((sprop)->id))
00305 
00306 #define SPROP_INVALID_SLOT              0xffffffff
00307 
00308 #define SLOT_IN_SCOPE(slot,scope)         ((slot) < (scope)->map.freeslot)
00309 #define SPROP_HAS_VALID_SLOT(sprop,scope) SLOT_IN_SCOPE((sprop)->slot, scope)
00310 
00311 #define SPROP_HAS_STUB_GETTER(sprop)    (!(sprop)->getter)
00312 #define SPROP_HAS_STUB_SETTER(sprop)    (!(sprop)->setter)
00313 
00314 /*
00315  * NB: SPROP_GET must not be called if SPROP_HAS_STUB_GETTER(sprop).
00316  */
00317 #define SPROP_GET(cx,sprop,obj,obj2,vp)                                       \
00318     (((sprop)->attrs & JSPROP_GETTER)                                         \
00319      ? js_InternalGetOrSet(cx, obj, (sprop)->id,                              \
00320                            OBJECT_TO_JSVAL((sprop)->getter), JSACC_READ,      \
00321                            0, 0, vp)                                          \
00322      : (sprop)->getter(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp))
00323 
00324 /*
00325  * NB: SPROP_SET must not be called if (SPROP_HAS_STUB_SETTER(sprop) &&
00326  * !(sprop->attrs & JSPROP_GETTER)).
00327  */
00328 #define SPROP_SET(cx,sprop,obj,obj2,vp)                                       \
00329     (((sprop)->attrs & JSPROP_SETTER)                                         \
00330      ? js_InternalGetOrSet(cx, obj, (sprop)->id,                              \
00331                            OBJECT_TO_JSVAL((sprop)->setter), JSACC_WRITE,     \
00332                            1, vp, vp)                                         \
00333      : ((sprop)->attrs & JSPROP_GETTER)                                       \
00334      ? (JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,                    \
00335                              JSMSG_GETTER_ONLY, NULL), JS_FALSE)              \
00336      : (sprop)->setter(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp))
00337 
00338 /* Macro for common expression to test for shared permanent attributes. */
00339 #define SPROP_IS_SHARED_PERMANENT(sprop)                                      \
00340     ((~(sprop)->attrs & (JSPROP_SHARED | JSPROP_PERMANENT)) == 0)
00341 
00342 extern JSScope *
00343 js_GetMutableScope(JSContext *cx, JSObject *obj);
00344 
00345 extern JSScope *
00346 js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
00347             JSObject *obj);
00348 
00349 extern void
00350 js_DestroyScope(JSContext *cx, JSScope *scope);
00351 
00352 #define ID_TO_VALUE(id) (JSID_IS_ATOM(id) ? ATOM_JSID_TO_JSVAL(id) :          \
00353                          JSID_IS_OBJECT(id) ? OBJECT_JSID_TO_JSVAL(id) :      \
00354                          (jsval)(id))
00355 #define HASH_ID(id)     (JSID_IS_ATOM(id) ? JSID_TO_ATOM(id)->number :        \
00356                          JSID_IS_OBJECT(id) ? (jsatomid) JSID_CLRTAG(id) :    \
00357                          (jsatomid) JSID_TO_INT(id))
00358 
00359 extern JS_FRIEND_API(JSScopeProperty **)
00360 js_SearchScope(JSScope *scope, jsid id, JSBool adding);
00361 
00362 #define SCOPE_GET_PROPERTY(scope, id)                                         \
00363     SPROP_FETCH(js_SearchScope(scope, id, JS_FALSE))
00364 
00365 #define SCOPE_HAS_PROPERTY(scope, sprop)                                      \
00366     (SCOPE_GET_PROPERTY(scope, (sprop)->id) == (sprop))
00367 
00368 extern JSScopeProperty *
00369 js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
00370                     JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
00371                     uintN attrs, uintN flags, intN shortid);
00372 
00373 extern JSScopeProperty *
00374 js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
00375                             JSScopeProperty *sprop, uintN attrs, uintN mask,
00376                             JSPropertyOp getter, JSPropertyOp setter);
00377 
00378 extern JSBool
00379 js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id);
00380 
00381 extern void
00382 js_ClearScope(JSContext *cx, JSScope *scope);
00383 
00384 /*
00385  * These macros used to inline short code sequences, but they grew over time.
00386  * We retain them for internal backward compatibility, and in case one or both
00387  * ever shrink to inline-able size.
00388  */
00389 #define MARK_ID(cx,id)                js_MarkId(cx, id)
00390 #define MARK_SCOPE_PROPERTY(cx,sprop) js_MarkScopeProperty(cx, sprop)
00391 
00392 extern void
00393 js_MarkId(JSContext *cx, jsid id);
00394 
00395 extern void
00396 js_MarkScopeProperty(JSContext *cx, JSScopeProperty *sprop);
00397 
00398 extern void
00399 js_SweepScopeProperties(JSRuntime *rt);
00400 
00401 extern JSBool
00402 js_InitPropertyTree(JSRuntime *rt);
00403 
00404 extern void
00405 js_FinishPropertyTree(JSRuntime *rt);
00406 
00407 #endif /* jsscope_h___ */