![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to jsscope.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Synchronet] / sbbs / include / mozilla / js|
Return to jsscope.h CVS log | Up to [Synchronet] / sbbs / include / mozilla / js |
1.1 ! root 1: /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- ! 2: * ! 3: * ***** BEGIN LICENSE BLOCK ***** ! 4: * Version: MPL 1.1/GPL 2.0/LGPL 2.1 ! 5: * ! 6: * The contents of this file are subject to the Mozilla Public License Version ! 7: * 1.1 (the "License"); you may not use this file except in compliance with ! 8: * the License. You may obtain a copy of the License at ! 9: * http://www.mozilla.org/MPL/ ! 10: * ! 11: * Software distributed under the License is distributed on an "AS IS" basis, ! 12: * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License ! 13: * for the specific language governing rights and limitations under the ! 14: * License. ! 15: * ! 16: * The Original Code is Mozilla Communicator client code, released ! 17: * March 31, 1998. ! 18: * ! 19: * The Initial Developer of the Original Code is ! 20: * Netscape Communications Corporation. ! 21: * Portions created by the Initial Developer are Copyright (C) 1998 ! 22: * the Initial Developer. All Rights Reserved. ! 23: * ! 24: * Contributor(s): ! 25: * ! 26: * Alternatively, the contents of this file may be used under the terms of ! 27: * either of the GNU General Public License Version 2 or later (the "GPL"), ! 28: * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), ! 29: * in which case the provisions of the GPL or the LGPL are applicable instead ! 30: * of those above. If you wish to allow use of your version of this file only ! 31: * under the terms of either the GPL or the LGPL, and not to allow others to ! 32: * use your version of this file under the terms of the MPL, indicate your ! 33: * decision by deleting the provisions above and replace them with the notice ! 34: * and other provisions required by the GPL or the LGPL. If you do not delete ! 35: * the provisions above, a recipient may use your version of this file under ! 36: * the terms of any one of the MPL, the GPL or the LGPL. ! 37: * ! 38: * ***** END LICENSE BLOCK ***** */ ! 39: ! 40: #ifndef jsscope_h___ ! 41: #define jsscope_h___ ! 42: /* ! 43: * JS symbol tables. ! 44: */ ! 45: #include "jstypes.h" ! 46: #include "jsobj.h" ! 47: #include "jsprvtd.h" ! 48: #include "jspubtd.h" ! 49: ! 50: #ifdef JS_THREADSAFE ! 51: # include "jslock.h" ! 52: #endif ! 53: ! 54: /* ! 55: * Given P independent, non-unique properties each of size S words mapped by ! 56: * all scopes in a runtime, construct a property tree of N nodes each of size ! 57: * S+L words (L for tree linkage). A nominal L value is 2 for leftmost-child ! 58: * and right-sibling links. We hope that the N < P by enough that the space ! 59: * overhead of L, and the overhead of scope entries pointing at property tree ! 60: * nodes, is worth it. ! 61: * ! 62: * The tree construction goes as follows. If any empty scope in the runtime ! 63: * has a property X added to it, find or create a node under the tree root ! 64: * labeled X, and set scope->lastProp to point at that node. If any non-empty ! 65: * scope whose most recently added property is labeled Y has another property ! 66: * labeled Z added, find or create a node for Z under the node that was added ! 67: * for Y, and set scope->lastProp to point at that node. ! 68: * ! 69: * A property is labeled by its members' values: id, getter, setter, slot, ! 70: * attributes, tiny or short id, and a field telling for..in order. Note that ! 71: * labels are not unique in the tree, but they are unique among a node's kids ! 72: * (barring rare and benign multi-threaded race condition outcomes, see below) ! 73: * and along any ancestor line from the tree root to a given leaf node (except ! 74: * for the hard case of duplicate formal parameters to a function). ! 75: * ! 76: * Thus the root of the tree represents all empty scopes, and the first ply ! 77: * of the tree represents all scopes containing one property, etc. Each node ! 78: * in the tree can stand for any number of scopes having the same ordered set ! 79: * of properties, where that node was the last added to the scope. (We need ! 80: * not store the root of the tree as a node, and do not -- all we need are ! 81: * links to its kids.) ! 82: * ! 83: * Sidebar on for..in loop order: ECMA requires no particular order, but this ! 84: * implementation has promised and delivered property definition order, and ! 85: * compatibility is king. We could use an order number per property, which ! 86: * would require a sort in js_Enumerate, and an entry order generation number ! 87: * per scope. An order number beats a list, which should be doubly-linked for ! 88: * O(1) delete. An even better scheme is to use a parent link in the property ! 89: * tree, so that the ancestor line can be iterated from scope->lastProp when ! 90: * filling in a JSIdArray from back to front. This parent link also helps the ! 91: * GC to sweep properties iteratively. ! 92: * ! 93: * What if a property Y is deleted from a scope? If Y is the last property in ! 94: * the scope, we simply adjust the scope's lastProp member after we remove the ! 95: * scope's hash-table entry pointing at that property node. The parent link ! 96: * mentioned in the for..in sidebar above makes this adjustment O(1). But if ! 97: * Y comes between X and Z in the scope, then we might have to "fork" the tree ! 98: * at X, leaving X->Y->Z in case other scopes have those properties added in ! 99: * that order; and to finish the fork, we'd add a node labeled Z with the path ! 100: * X->Z, if it doesn't exist. This could lead to lots of extra nodes, and to ! 101: * O(n^2) growth when deleting lots of properties. ! 102: * ! 103: * Rather, for O(1) growth all around, we should share the path X->Y->Z among ! 104: * scopes having those three properties added in that order, and among scopes ! 105: * having only X->Z where Y was deleted. All such scopes have a lastProp that ! 106: * points to the Z child of Y. But a scope in which Y was deleted does not ! 107: * have a table entry for Y, and when iterating that scope by traversing the ! 108: * ancestor line from Z, we will have to test for a table entry for each node, ! 109: * skipping nodes that lack entries. ! 110: * ! 111: * What if we add Y again? X->Y->Z->Y is wrong and we'll enumerate Y twice. ! 112: * Therefore we must fork in such a case, if not earlier. Because delete is ! 113: * "bursty", we should not fork eagerly. Delaying a fork till we are at risk ! 114: * of adding Y after it was deleted already requires a flag in the JSScope, to ! 115: * wit, SCOPE_MIDDLE_DELETE. ! 116: * ! 117: * What about thread safety? If the property tree operations done by requests ! 118: * are find-node and insert-node, then the only hazard is duplicate insertion. ! 119: * This is harmless except for minor bloat. When all requests have ended or ! 120: * been suspended, the GC is free to sweep the tree after marking all nodes ! 121: * reachable from scopes, performing remove-node operations as needed. Note ! 122: * also that the stable storage of the property nodes during active requests ! 123: * permits the property cache (see jsinterp.h) to dereference JSScopeProperty ! 124: * weak references safely. ! 125: * ! 126: * Is the property tree worth it compared to property storage in each table's ! 127: * entries? To decide, we must find the relation <> between the words used ! 128: * with a property tree and the words required without a tree. ! 129: * ! 130: * Model all scopes as one super-scope of capacity T entries (T a power of 2). ! 131: * Let alpha be the load factor of this double hash-table. With the property ! 132: * tree, each entry in the table is a word-sized pointer to a node that can be ! 133: * shared by many scopes. But all such pointers are overhead compared to the ! 134: * situation without the property tree, where the table stores property nodes ! 135: * directly, as entries each of size S words. With the property tree, we need ! 136: * L=2 extra words per node for siblings and kids pointers. Without the tree, ! 137: * (1-alpha)*S*T words are wasted on free or removed sentinel-entries required ! 138: * by double hashing. ! 139: * ! 140: * Therefore, ! 141: * ! 142: * (property tree) <> (no property tree) ! 143: * N*(S+L) + T <> S*T ! 144: * N*(S+L) + T <> P*S + (1-alpha)*S*T ! 145: * N*(S+L) + alpha*T + (1-alpha)*T <> P*S + (1-alpha)*S*T ! 146: * ! 147: * Note that P is alpha*T by definition, so ! 148: * ! 149: * N*(S+L) + P + (1-alpha)*T <> P*S + (1-alpha)*S*T ! 150: * N*(S+L) <> P*S - P + (1-alpha)*S*T - (1-alpha)*T ! 151: * N*(S+L) <> (P + (1-alpha)*T) * (S-1) ! 152: * N*(S+L) <> (P + (1-alpha)*P/alpha) * (S-1) ! 153: * N*(S+L) <> P * (1/alpha) * (S-1) ! 154: * ! 155: * Let N = P*beta for a compression ratio beta, beta <= 1: ! 156: * ! 157: * P*beta*(S+L) <> P * (1/alpha) * (S-1) ! 158: * beta*(S+L) <> (S-1)/alpha ! 159: * beta <> (S-1)/((S+L)*alpha) ! 160: * ! 161: * For S = 6 (32-bit architectures) and L = 2, the property tree wins iff ! 162: * ! 163: * beta < 5/(8*alpha) ! 164: * ! 165: * We ensure that alpha <= .75, so the property tree wins if beta < .83_. An ! 166: * average beta from recent Mozilla browser startups was around .6. ! 167: * ! 168: * Can we reduce L? Observe that the property tree degenerates into a list of ! 169: * lists if at most one property Y follows X in all scopes. In or near such a ! 170: * case, we waste a word on the right-sibling link outside of the root ply of ! 171: * the tree. Note also that the root ply tends to be large, so O(n^2) growth ! 172: * searching it is likely, indicating the need for hashing (but with increased ! 173: * thread safety costs). ! 174: * ! 175: * If only K out of N nodes in the property tree have more than one child, we ! 176: * could eliminate the sibling link and overlay a children list or hash-table ! 177: * pointer on the leftmost-child link (which would then be either null or an ! 178: * only-child link; the overlay could be tagged in the low bit of the pointer, ! 179: * or flagged elsewhere in the property tree node, although such a flag must ! 180: * not be considered when comparing node labels during tree search). ! 181: * ! 182: * For such a system, L = 1 + (K * averageChildrenTableSize) / N instead of 2. ! 183: * If K << N, L approaches 1 and the property tree wins if beta < .95. ! 184: * ! 185: * We observe that fan-out below the root ply of the property tree appears to ! 186: * have extremely low degree (see the MeterPropertyTree code that histograms ! 187: * child-counts in jsscope.c), so instead of a hash-table we use a linked list ! 188: * of child node pointer arrays ("kid chunks"). The details are isolated in ! 189: * jsscope.c; others must treat JSScopeProperty.kids as opaque. We leave it ! 190: * strongly typed for debug-ability of the common (null or one-kid) cases. ! 191: * ! 192: * One final twist (can you stand it?): the mean number of entries per scope ! 193: * in Mozilla is < 5, with a large standard deviation (~8). Instead of always ! 194: * allocating scope->table, we leave it null while initializing all the other ! 195: * scope members as if it were non-null and minimal-length. Until a property ! 196: * is added that crosses the threshold of 6 or more entries for hashing, or ! 197: * until a "middle delete" occurs, we use linear search from scope->lastProp ! 198: * to find a given id, and save on the space overhead of a hash table. ! 199: */ ! 200: ! 201: struct JSScope { ! 202: JSObjectMap map; /* base class state */ ! 203: JSObject *object; /* object that owns this scope */ ! 204: uint16 flags; /* flags, see below */ ! 205: int16 hashShift; /* multiplicative hash shift */ ! 206: uint32 entryCount; /* number of entries in table */ ! 207: uint32 removedCount; /* removed entry sentinels in table */ ! 208: JSScopeProperty **table; /* table of ptrs to shared tree nodes */ ! 209: JSScopeProperty *lastProp; /* pointer to last property added */ ! 210: #ifdef JS_THREADSAFE ! 211: JSContext *ownercx; /* creating context, NULL if shared */ ! 212: JSThinLock lock; /* binary semaphore protecting scope */ ! 213: union { /* union lockful and lock-free state: */ ! 214: jsrefcount count; /* lock entry count for reentrancy */ ! 215: JSScope *link; /* next link in rt->scopeSharingTodo */ ! 216: } u; ! 217: #ifdef DEBUG ! 218: const char *file[4]; /* file where lock was (re-)taken */ ! 219: unsigned int line[4]; /* line where lock was (re-)taken */ ! 220: #endif ! 221: #endif ! 222: }; ! 223: ! 224: #define OBJ_SCOPE(obj) ((JSScope *)(obj)->map) ! 225: ! 226: /* By definition, hashShift = JS_DHASH_BITS - log2(capacity). */ ! 227: #define SCOPE_CAPACITY(scope) JS_BIT(JS_DHASH_BITS-(scope)->hashShift) ! 228: ! 229: /* Scope flags and some macros to hide them from other files than jsscope.c. */ ! 230: #define SCOPE_MIDDLE_DELETE 0x0001 ! 231: #define SCOPE_SEALED 0x0002 ! 232: ! 233: #define SCOPE_HAD_MIDDLE_DELETE(scope) ((scope)->flags & SCOPE_MIDDLE_DELETE) ! 234: #define SCOPE_SET_MIDDLE_DELETE(scope) ((scope)->flags |= SCOPE_MIDDLE_DELETE) ! 235: #define SCOPE_CLR_MIDDLE_DELETE(scope) ((scope)->flags &= ~SCOPE_MIDDLE_DELETE) ! 236: ! 237: #define SCOPE_IS_SEALED(scope) ((scope)->flags & SCOPE_SEALED) ! 238: #define SCOPE_SET_SEALED(scope) ((scope)->flags |= SCOPE_SEALED) ! 239: #if 0 ! 240: /* ! 241: * Don't define this, it can't be done safely because JS_LOCK_OBJ will avoid ! 242: * taking the lock if the object owns its scope and the scope is sealed. ! 243: */ ! 244: #define SCOPE_CLR_SEALED(scope) ((scope)->flags &= ~SCOPE_SEALED) ! 245: #endif ! 246: ! 247: /* ! 248: * A little information hiding for scope->lastProp, in case it ever becomes ! 249: * a tagged pointer again. ! 250: */ ! 251: #define SCOPE_LAST_PROP(scope) ((scope)->lastProp) ! 252: #define SCOPE_REMOVE_LAST_PROP(scope) ((scope)->lastProp = \ ! 253: (scope)->lastProp->parent) ! 254: ! 255: struct JSScopeProperty { ! 256: jsid id; /* int-tagged jsval/untagged JSAtom* */ ! 257: JSPropertyOp getter; /* getter and setter hooks or objects */ ! 258: JSPropertyOp setter; ! 259: uint32 slot; /* index in obj->slots vector */ ! 260: uint8 attrs; /* attributes, see jsapi.h JSPROP_* */ ! 261: uint8 flags; /* flags, see below for defines */ ! 262: int16 shortid; /* tinyid, or local arg/var index */ ! 263: JSScopeProperty *parent; /* parent node, reverse for..in order */ ! 264: JSScopeProperty *kids; /* null, single child, or a tagged ptr ! 265: to many-kids data structure */ ! 266: }; ! 267: ! 268: /* JSScopeProperty pointer tag bit indicating a collision. */ ! 269: #define SPROP_COLLISION ((jsuword)1) ! 270: #define SPROP_REMOVED ((JSScopeProperty *) SPROP_COLLISION) ! 271: ! 272: /* Macros to get and set sprop pointer values and collision flags. */ ! 273: #define SPROP_IS_FREE(sprop) ((sprop) == NULL) ! 274: #define SPROP_IS_REMOVED(sprop) ((sprop) == SPROP_REMOVED) ! 275: #define SPROP_IS_LIVE(sprop) ((sprop) > SPROP_REMOVED) ! 276: #define SPROP_FLAG_COLLISION(spp,sprop) (*(spp) = (JSScopeProperty *) \ ! 277: ((jsuword)(sprop) | SPROP_COLLISION)) ! 278: #define SPROP_HAD_COLLISION(sprop) ((jsuword)(sprop) & SPROP_COLLISION) ! 279: #define SPROP_FETCH(spp) SPROP_CLEAR_COLLISION(*(spp)) ! 280: ! 281: #define SPROP_CLEAR_COLLISION(sprop) \ ! 282: ((JSScopeProperty *) ((jsuword)(sprop) & ~SPROP_COLLISION)) ! 283: ! 284: #define SPROP_STORE_PRESERVING_COLLISION(spp, sprop) \ ! 285: (*(spp) = (JSScopeProperty *) ((jsuword)(sprop) \ ! 286: | SPROP_HAD_COLLISION(*(spp)))) ! 287: ! 288: /* Bits stored in sprop->flags. */ ! 289: #define SPROP_MARK 0x01 ! 290: #define SPROP_IS_DUPLICATE 0x02 ! 291: #define SPROP_IS_ALIAS 0x04 ! 292: #define SPROP_HAS_SHORTID 0x08 ! 293: ! 294: /* ! 295: * If SPROP_HAS_SHORTID is set in sprop->flags, we use sprop->shortid rather ! 296: * than id when calling sprop's getter or setter. ! 297: */ ! 298: #define SPROP_USERID(sprop) \ ! 299: (((sprop)->flags & SPROP_HAS_SHORTID) ? INT_TO_JSVAL((sprop)->shortid) \ ! 300: : ID_TO_VALUE((sprop)->id)) ! 301: ! 302: #define SPROP_INVALID_SLOT 0xffffffff ! 303: ! 304: #define SPROP_HAS_VALID_SLOT(sprop, scope) \ ! 305: ((sprop)->slot < (scope)->map.freeslot) ! 306: ! 307: #define SPROP_HAS_STUB_GETTER(sprop) (!(sprop)->getter) ! 308: #define SPROP_HAS_STUB_SETTER(sprop) (!(sprop)->setter) ! 309: ! 310: #define SPROP_CALL_GETTER(cx,sprop,getter,obj,obj2,vp) \ ! 311: (!(getter) || \ ! 312: (getter)(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp)) ! 313: #define SPROP_CALL_SETTER(cx,sprop,setter,obj,obj2,vp) \ ! 314: (!(setter) || \ ! 315: (setter)(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp)) ! 316: ! 317: #define SPROP_GET(cx,sprop,obj,obj2,vp) \ ! 318: (((sprop)->attrs & JSPROP_GETTER) \ ! 319: ? js_InternalGetOrSet(cx, obj, (sprop)->id, \ ! 320: OBJECT_TO_JSVAL((sprop)->getter), JSACC_READ, \ ! 321: 0, 0, vp) \ ! 322: : SPROP_CALL_GETTER(cx, sprop, (sprop)->getter, obj, obj2, vp)) ! 323: ! 324: #define SPROP_SET(cx,sprop,obj,obj2,vp) \ ! 325: (((sprop)->attrs & JSPROP_SETTER) \ ! 326: ? js_InternalGetOrSet(cx, obj, (sprop)->id, \ ! 327: OBJECT_TO_JSVAL((sprop)->setter), JSACC_WRITE, \ ! 328: 1, vp, vp) \ ! 329: : ((sprop)->attrs & JSPROP_GETTER) \ ! 330: ? (JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, \ ! 331: JSMSG_GETTER_ONLY, NULL), JS_FALSE) \ ! 332: : SPROP_CALL_SETTER(cx, sprop, (sprop)->setter, obj, obj2, vp)) ! 333: ! 334: /* Macro for common expression to test for shared permanent attributes. */ ! 335: #define SPROP_IS_SHARED_PERMANENT(sprop) \ ! 336: ((~(sprop)->attrs & (JSPROP_SHARED | JSPROP_PERMANENT)) == 0) ! 337: ! 338: extern JSScope * ! 339: js_GetMutableScope(JSContext *cx, JSObject *obj); ! 340: ! 341: extern JSScope * ! 342: js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp, ! 343: JSObject *obj); ! 344: ! 345: extern void ! 346: js_DestroyScope(JSContext *cx, JSScope *scope); ! 347: ! 348: #define ID_TO_VALUE(id) (((id) & JSVAL_INT) ? id : ATOM_KEY((JSAtom *)(id))) ! 349: #define HASH_ID(id) (((id) & JSVAL_INT) \ ! 350: ? (jsatomid) JSVAL_TO_INT(id) \ ! 351: : ((JSAtom *)id)->number) ! 352: ! 353: extern JS_FRIEND_API(JSScopeProperty **) ! 354: js_SearchScope(JSScope *scope, jsid id, JSBool adding); ! 355: ! 356: #define SCOPE_GET_PROPERTY(scope, id) \ ! 357: SPROP_FETCH(js_SearchScope(scope, id, JS_FALSE)) ! 358: ! 359: #define SCOPE_HAS_PROPERTY(scope, sprop) \ ! 360: (SCOPE_GET_PROPERTY(scope, (sprop)->id) == (sprop)) ! 361: ! 362: extern JSScopeProperty * ! 363: js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id, ! 364: JSPropertyOp getter, JSPropertyOp setter, uint32 slot, ! 365: uintN attrs, uintN flags, intN shortid); ! 366: ! 367: extern JSScopeProperty * ! 368: js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope, ! 369: JSScopeProperty *sprop, uintN attrs, uintN mask, ! 370: JSPropertyOp getter, JSPropertyOp setter); ! 371: ! 372: extern JSBool ! 373: js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id); ! 374: ! 375: extern void ! 376: js_ClearScope(JSContext *cx, JSScope *scope); ! 377: ! 378: #define MARK_SCOPE_PROPERTY(sprop) ((sprop)->flags |= SPROP_MARK) ! 379: ! 380: extern void ! 381: js_SweepScopeProperties(JSRuntime *rt); ! 382: ! 383: extern JSBool ! 384: js_InitPropertyTree(JSRuntime *rt); ! 385: ! 386: extern void ! 387: js_FinishPropertyTree(JSRuntime *rt); ! 388: ! 389: #endif /* jsscope_h___ */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.