js/src/jspropertycache.cpp

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set ts=8 sw=4 et tw=98:
   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 the GNU General Public License Version 2 or later (the "GPL"), or
  29  * 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 #include "jspropertycache.h"
  42 #include "jscntxt.h"
  43 #include "jsnum.h"
  44 #include "jsobjinlines.h"
  45 #include "jspropertycacheinlines.h"
  46
  47 using namespace js;
  48
  49 JS_STATIC_ASSERT(sizeof(PCVal) == sizeof(jsuword));
  50
  51 JS_REQUIRES_STACK PropertyCacheEntry *
  52 PropertyCache::fill(JSContext *cx, JSObject *obj, uintN scopeIndex, uintN protoIndex,
  53                     JSObject *pobj, const Shape *shape, JSBool adding)
  54 {
  55     jsbytecode *pc;
  56     jsuword kshape, vshape;
  57     JSOp op;
  58     const JSCodeSpec *cs;
  59     PCVal vword;
  60     PropertyCacheEntry *entry;
  61
  62     JS_ASSERT(this == &JS_PROPERTY_CACHE(cx));
  63     JS_ASSERT(!cx->runtime->gcRunning);
  64
  65     if (js_IsPropertyCacheDisabled(cx)) {
  66         PCMETER(disfills++);
  67         return JS_NO_PROP_CACHE_FILL;
  68     }
  69
  70     /*
  71      * Check for fill from js_SetPropertyHelper where the setter removed shape
  72      * from pobj (via unwatch or delete, e.g.).
  73      */
  74     if (!pobj->nativeContains(*shape)) {
  75         PCMETER(oddfills++);
  76         return JS_NO_PROP_CACHE_FILL;
  77     }
  78
  79     /*
  80      * Dictionary-mode objects have unique shapes, so there is no way to cache
  81      * a prediction of the next shape when adding.
  82      */
  83     if (adding && obj->inDictionaryMode()) {
  84         PCMETER(add2dictfills++);
  85         return JS_NO_PROP_CACHE_FILL;
  86     }
  87
  88     /*
  89      * Check for overdeep scope and prototype chain. Because resolve, getter,
  90      * and setter hooks can change the prototype chain using JS_SetPrototype
  91      * after js_LookupPropertyWithFlags has returned the nominal protoIndex,
  92      * we have to validate protoIndex if it is non-zero. If it is zero, then
  93      * we know thanks to the pobj->nativeContains test above, combined with the
  94      * fact that obj == pobj, that protoIndex is invariant.
  95      *
  96      * The scopeIndex can't be wrong. We require JS_SetParent calls to happen
  97      * before any running script might consult a parent-linked scope chain. If
  98      * this requirement is not satisfied, the fill in progress will never hit,
  99      * but vcap vs. scope shape tests ensure nothing malfunctions.
 100      */
 101     JS_ASSERT_IF(scopeIndex == 0 && protoIndex == 0, obj == pobj);
 102
 103     if (protoIndex != 0) {
 104         JSObject *tmp = obj;
 105
 106         for (uintN i = 0; i != scopeIndex; i++)
 107             tmp = tmp->getParent();
 108         JS_ASSERT(tmp != pobj);
 109
 110         protoIndex = 1;
 111         for (;;) {
 112             tmp = tmp->getProto();
 113
 114             /*
 115              * We cannot cache properties coming from native objects behind
 116              * non-native ones on the prototype chain. The non-natives can
 117              * mutate in arbitrary way without changing any shapes.
 118              */
 119             if (!tmp || !tmp->isNative()) {
 120                 PCMETER(noprotos++);
 121                 return JS_NO_PROP_CACHE_FILL;
 122             }
 123             if (tmp == pobj)
 124                 break;
 125             ++protoIndex;
 126         }
 127     }
 128
 129     if (scopeIndex > PCVCAP_SCOPEMASK || protoIndex > PCVCAP_PROTOMASK) {
 130         PCMETER(longchains++);
 131         return JS_NO_PROP_CACHE_FILL;
 132     }
 133
 134     /*
 135      * Optimize the cached vword based on our parameters and the current pc's
 136      * opcode format flags.
 137      */
 138     pc = cx->regs->pc;
 139     op = js_GetOpcode(cx, cx->fp()->script(), pc);
 140     cs = &js_CodeSpec[op];
 141     kshape = 0;
 142
 143     do {
 144         /*
 145          * Check for a prototype "plain old method" callee computation. What
 146          * is a plain old method? It's a function-valued property with stub
 147          * getter, so get of a function is idempotent.
 148          */
 149         if (cs->format & JOF_CALLOP) {
 150             if (shape->isMethod()) {
 151                 /*
 152                  * A compiler-created function object, AKA a method, already
 153                  * memoized in the property tree.
 154                  */
 155                 JS_ASSERT(pobj->hasMethodBarrier());
 156                 JSObject &funobj = shape->methodObject();
 157                 JS_ASSERT(&funobj == &pobj->nativeGetSlot(shape->slot).toObject());
 158                 vword.setFunObj(funobj);
 159                 break;
 160             }
 161
 162             if (!pobj->generic() && shape->hasDefaultGetter() && pobj->containsSlot(shape->slot)) {
 163                 const Value &v = pobj->nativeGetSlot(shape->slot);
 164                 JSObject *funobj;
 165
 166                 if (IsFunctionObject(v, &funobj)) {
 167                     /*
 168                      * Great, we have a function-valued prototype property
 169                      * where the getter is JS_PropertyStub. The type id in
 170                      * pobj does not evolve with changes to property values,
 171                      * however.
 172                      *
 173                      * So here, on first cache fill for this method, we brand
 174                      * obj with a new shape and set the JSObject::BRANDED flag.
 175                      * Once this flag is set, any property assignment that
 176                      * changes the value from or to a different function object
 177                      * will result in shape being regenerated.
 178                      */
 179                     if (!pobj->branded()) {
 180                         PCMETER(brandfills++);
 181 #ifdef DEBUG_notme
 182                         JSFunction *fun = GET_FUNCTION_PRIVATE(cx, JSVAL_TO_OBJECT(v));
 183                         JSAutoByteString funNameBytes;
 184                         if (const char *funName = GetFunctionNameBytes(cx, fun, &funNameBytes)) {
 185                             fprintf(stderr,
 186                                     "branding %p (%s) for funobj %p (%s), shape %lu\n",
 187                                     pobj, pobj->getClass()->name, JSVAL_TO_OBJECT(v), funName,
 188                                     obj->shape());
 189                         }
 190 #endif
 191                         if (!pobj->brand(cx))
 192                             return JS_NO_PROP_CACHE_FILL;
 193                     }
 194                     vword.setFunObj(*funobj);
 195                     break;
 196                 }
 197             }
 198         }
 199
 200         /*
 201          * If getting a value via a stub getter, or doing an INCDEC op
 202          * with stub getters and setters, we can cache the slot.
 203          */
 204         if (!(cs->format & (JOF_SET | JOF_FOR)) &&
 205             (!(cs->format & JOF_INCDEC) || (shape->hasDefaultSetter() && shape->writable())) &&
 206             shape->hasDefaultGetter() &&
 207             pobj->containsSlot(shape->slot)) {
 208             /* Great, let's cache shape's slot and use it on cache hit. */
 209             vword.setSlot(shape->slot);
 210         } else {
 211             /* Best we can do is to cache shape (still a nice speedup). */
 212             vword.setShape(shape);
 213             if (adding &&
 214                 pobj->shape() == shape->shape) {
 215                 /*
 216                  * Our caller added a new property. We also know that a setter
 217                  * that js_NativeSet might have run has not mutated pobj, so
 218                  * the added property is still the last one added, and pobj is
 219                  * not branded.
 220                  *
 221                  * We want to cache under pobj's shape before the property
 222                  * addition to bias for the case when the mutator opcode
 223                  * always adds the same property. This allows us to optimize
 224                  * periodic execution of object initializers or other explicit
 225                  * initialization sequences such as
 226                  *
 227                  *   obj = {}; obj.x = 1; obj.y = 2;
 228                  *
 229                  * We assume that on average the win from this optimization is
 230                  * greater than the cost of an extra mismatch per loop owing to
 231                  * the bias for the following case:
 232                  *
 233                  *   obj = {}; ... for (...) { ... obj.x = ... }
 234                  *
 235                  * On the first iteration of such a for loop, JSOP_SETPROP
 236                  * fills the cache with the shape of the newly created object
 237                  * obj, not the shape of obj after obj.x has been assigned.
 238                  * That mismatches obj's shape on the second iteration. Note
 239                  * that on the third and subsequent iterations the cache will
 240                  * be hit because the shape is no longer updated.
 241                  */
 242                 JS_ASSERT(shape == pobj->lastProperty());
 243                 JS_ASSERT(!pobj->nativeEmpty());
 244
 245                 kshape = shape->previous()->shape;
 246
 247                 /*
 248                  * When adding we predict no prototype object will later gain a
 249                  * readonly property or setter.
 250                  */
 251                 vshape = cx->runtime->protoHazardShape;
 252             }
 253         }
 254     } while (0);
 255
 256     if (kshape == 0) {
 257         kshape = obj->shape();
 258         vshape = pobj->shape();
 259     }
 260     JS_ASSERT(kshape < SHAPE_OVERFLOW_BIT);
 261
 262     if (obj == pobj) {
 263         JS_ASSERT(scopeIndex == 0 && protoIndex == 0);
 264     } else {
 265 #ifdef DEBUG
 266         if (scopeIndex == 0) {
 267             JS_ASSERT(protoIndex != 0);
 268             JS_ASSERT((protoIndex == 1) == (obj->getProto() == pobj));
 269         }
 270 #endif
 271
 272         if (scopeIndex != 0 || protoIndex != 1) {
 273             /*
 274              * Make sure that a later shadowing assignment will enter
 275              * PurgeProtoChain and invalidate this entry, bug 479198.
 276              *
 277              * This is not thread-safe but we are about to make all objects
 278              * except multi-threaded wrappers (bug 566951) single-threaded.
 279              * And multi-threaded wrappers are non-native Proxy instances, so
 280              * they won't use the property cache.
 281              */
 282             obj->setDelegate();
 283         }
 284     }
 285     JS_ASSERT(vshape < SHAPE_OVERFLOW_BIT);
 286
 287     entry = &table[hash(pc, kshape)];
 288     PCMETER(entry->vword.isNull() || recycles++);
 289     entry->assign(pc, kshape, vshape, scopeIndex, protoIndex, vword);
 290
 291     empty = false;
 292     PCMETER(fills++);
 293
 294     /*
 295      * The modfills counter is not exact. It increases if a getter or setter
 296      * recurse into the interpreter.
 297      */
 298     PCMETER(entry == pctestentry || modfills++);
 299     PCMETER(pctestentry = NULL);
 300     return entry;
 301 }
 302
 303 static inline JSAtom *
 304 GetAtomFromBytecode(JSContext *cx, jsbytecode *pc, JSOp op, const JSCodeSpec &cs)
 305 {
 306     if (op == JSOP_LENGTH)
 307         return cx->runtime->atomState.lengthAtom;
 308
 309     // The method JIT's implementation of instanceof contains an internal lookup
 310     // of the prototype property.
 311     if (op == JSOP_INSTANCEOF)
 312         return cx->runtime->atomState.classPrototypeAtom;
 313
 314     ptrdiff_t pcoff = (JOF_TYPE(cs.format) == JOF_SLOTATOM) ? SLOTNO_LEN : 0;
 315     JSAtom *atom;
 316     GET_ATOM_FROM_BYTECODE(cx->fp()->script(), pc, pcoff, atom);
 317     return atom;
 318 }
 319
 320 JS_REQUIRES_STACK JSAtom *
 321 PropertyCache::fullTest(JSContext *cx, jsbytecode *pc, JSObject **objp, JSObject **pobjp,
 322                         PropertyCacheEntry *entry)
 323 {
 324     JSObject *obj, *pobj, *tmp;
 325     uint32 vcap;
 326
 327     JSStackFrame *fp = cx->fp();
 328
 329     JS_ASSERT(this == &JS_PROPERTY_CACHE(cx));
 330     JS_ASSERT(uintN((fp->hasImacropc() ? fp->imacropc() : pc) - fp->script()->code)
 331               < fp->script()->length);
 332
 333     JSOp op = js_GetOpcode(cx, fp->script(), pc);
 334     const JSCodeSpec &cs = js_CodeSpec[op];
 335
 336     obj = *objp;
 337     vcap = entry->vcap;
 338
 339     if (entry->kpc != pc) {
 340         PCMETER(kpcmisses++);
 341
 342         JSAtom *atom = GetAtomFromBytecode(cx, pc, op, cs);
 343 #ifdef DEBUG_notme
 344         JSScript *script = cx->fp()->getScript();
 345         JSAutoByteString printable;
 346         fprintf(stderr,
 347                 "id miss for %s from %s:%u"
 348                 " (pc %u, kpc %u, kshape %u, shape %u)\n",
 349                 js_AtomToPrintableString(cx, atom, &printable),
 350                 script->filename,
 351                 js_PCToLineNumber(cx, script, pc),
 352                 pc - script->code,
 353                 entry->kpc - script->code,
 354                 entry->kshape,
 355                 obj->shape());
 356                 js_Disassemble1(cx, script, pc,
 357                                 pc - script->code,
 358                                 JS_FALSE, stderr);
 359 #endif
 360
 361         return atom;
 362     }
 363
 364     if (entry->kshape != obj->shape()) {
 365         PCMETER(kshapemisses++);
 366         return GetAtomFromBytecode(cx, pc, op, cs);
 367     }
 368
 369     /*
 370      * PropertyCache::test handles only the direct and immediate-prototype hit
 371      * cases. All others go here. We could embed the target object in the cache
 372      * entry but then entry size would be 5 words. Instead we traverse chains.
 373      */
 374     pobj = obj;
 375
 376     if (JOF_MODE(cs.format) == JOF_NAME) {
 377         while (vcap & (PCVCAP_SCOPEMASK << PCVCAP_PROTOBITS)) {
 378             tmp = pobj->getParent();
 379             if (!tmp || !tmp->isNative())
 380                 break;
 381             pobj = tmp;
 382             vcap -= PCVCAP_PROTOSIZE;
 383         }
 384
 385         *objp = pobj;
 386     }
 387
 388     while (vcap & PCVCAP_PROTOMASK) {
 389         tmp = pobj->getProto();
 390         if (!tmp || !tmp->isNative())
 391             break;
 392         pobj = tmp;
 393         --vcap;
 394     }
 395
 396     if (matchShape(cx, pobj, vcap >> PCVCAP_TAGBITS)) {
 397 #ifdef DEBUG
 398         JSAtom *atom = GetAtomFromBytecode(cx, pc, op, cs);
 399         jsid id = ATOM_TO_JSID(atom);
 400
 401         id = js_CheckForStringIndex(id);
 402         JS_ASSERT(pobj->nativeContains(id));
 403 #endif
 404         *pobjp = pobj;
 405         return NULL;
 406     }
 407
 408     PCMETER(vcapmisses++);
 409     return GetAtomFromBytecode(cx, pc, op, cs);
 410 }
 411
 412 #ifdef DEBUG
 413 void
 414 PropertyCache::assertEmpty()
 415 {
 416     JS_ASSERT(empty);
 417     for (uintN i = 0; i < SIZE; i++) {
 418         JS_ASSERT(!table[i].kpc);
 419         JS_ASSERT(!table[i].kshape);
 420         JS_ASSERT(!table[i].vcap);
 421         JS_ASSERT(table[i].vword.isNull());
 422     }
 423 }
 424 #endif
 425
 426 void
 427 PropertyCache::purge(JSContext *cx)
 428 {
 429     if (empty) {
 430         assertEmpty();
 431         return;
 432     }
 433
 434     PodArrayZero(table);
 435     JS_ASSERT(table[0].vword.isNull());
 436     empty = true;
 437
 438 #ifdef JS_PROPERTY_CACHE_METERING
 439   { static FILE *fp;
 440     if (!fp)
 441         fp = fopen("/tmp/propcache.stats", "w");
 442     if (fp) {
 443         fputs("Property cache stats for ", fp);
 444 #ifdef JS_THREADSAFE
 445         fprintf(fp, "thread %lu, ", (unsigned long) cx->thread->id);
 446 #endif
 447         fprintf(fp, "GC %u\n", cx->runtime->gcNumber);
 448
 449 # define P(mem) fprintf(fp, "%11s %10lu\n", #mem, (unsigned long)mem)
 450         P(fills);
 451         P(nofills);
 452         P(rofills);
 453         P(disfills);
 454         P(oddfills);
 455         P(add2dictfills);
 456         P(modfills);
 457         P(brandfills);
 458         P(noprotos);
 459         P(longchains);
 460         P(recycles);
 461         P(tests);
 462         P(pchits);
 463         P(protopchits);
 464         P(initests);
 465         P(inipchits);
 466         P(inipcmisses);
 467         P(settests);
 468         P(addpchits);
 469         P(setpchits);
 470         P(setpcmisses);
 471         P(setmisses);
 472         P(kpcmisses);
 473         P(kshapemisses);
 474         P(vcapmisses);
 475         P(misses);
 476         P(flushes);
 477         P(pcpurges);
 478 # undef P
 479
 480         fprintf(fp, "hit rates: pc %g%% (proto %g%%), set %g%%, ini %g%%, full %g%%\n",
 481                 (100. * pchits) / tests,
 482                 (100. * protopchits) / tests,
 483                 (100. * (addpchits + setpchits))
 484                 / settests,
 485                 (100. * inipchits) / initests,
 486                 (100. * (tests - misses)) / tests);
 487         fflush(fp);
 488     }
 489   }
 490 #endif
 491
 492     PCMETER(flushes++);
 493 }
 494
 495 void
 496 PropertyCache::purgeForScript(JSContext *cx, JSScript *script)
 497 {
 498     JS_ASSERT(!cx->runtime->gcRunning);
 499
 500     for (PropertyCacheEntry *entry = table; entry < table + SIZE; entry++) {
 501         if (JS_UPTRDIFF(entry->kpc, script->code) < script->length) {
 502             entry->kpc = NULL;
 503 #ifdef DEBUG
 504             entry->kshape = entry->vcap = 0;
 505             entry->vword.setNull();
 506 #endif
 507         }
 508     }
 509 }