root/core/VTable.cpp

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. getRawDispID
  2. sortImtThunkEntries
  3. disp_id
  4. buildImtEntries
  5. dispatchImt
  6. resolveImt
  7. resolveImtSlotFromBase
  8. resolveImtSlotSelf
  9. resolveImtSlot
  10. linked
  11. resolveSignatures
  12. makeMethodEnv
  13. size
  14. newParameterizedVTable

/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is [Open Source Virtual Machine.].
 *
 * The Initial Developer of the Original Code is
 * Adobe System Incorporated.
 * Portions created by the Initial Developer are Copyright (C) 1993-2006
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *   Adobe AS3 Team
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */


#include "avmplus.h"
//#define DOPROF
//#include "vprof.h"

namespace avmplus
{

#if defined FEATURE_NANOJIT
        
        /*
                Research suggests that linear searches are best for up to 4 entries, binary
                search best for 4...10, and lookup-table best for larger sizes. Lookup tables
                are impractical here, since our iid values aren't consecutive but rather
                arbitrary integers, so we just use linear-and-binary. Furthermore, profiling
                suggested that separate linear search wasn't a measurable gain, so we
                always do a binary search, in the name of simplicity.
        
                http://www.sagecertification.org/events/javavm02/full_papers/zendra/zendra_html/index.html
        */
        
        // AvmCore::bindingToMethodId will assert inapproppriately
        static inline uint32_t getRawDispID(Binding b) { return  uint32_t(uintptr_t(b))>>3; }
        
        static void sortImtThunkEntries(ImtThunkEntry* map, uint32_t count)
        {
                // intervals suggested by http://www.research.att.com/~njas/sequences/A108870
                // we'll never get anywhere near the upper limits but it's probably cheaper than extending algorithmically
                static const uint32_t k_shellsort_intervals[] = { 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, 30301, 
                                                                                        68178, 153401, 345152, 776591, 1747331, 3931496, 8845866, 19903198, 
                                                                                        44782196, 100759940, 226709866, 510097200, 1147718700 };
                
                // simple ShellSort -- the list rarely gets larger than 100 or so, so this is efficient and compact
                if (count <= 1)
                        return;

                ImtThunkEntry* beg = map;
                ImtThunkEntry* end = map + count;       // one past end!

                int32_t interval_idx = 0;
                while (count > k_shellsort_intervals[interval_idx+1])
                        ++interval_idx;

                while (interval_idx >= 0)
                {
                        const int32_t interval = k_shellsort_intervals[interval_idx--];
                        for (ImtThunkEntry* i = beg + interval; i < end; i++) 
                        {
                                ImtThunkEntry temp = *i;
                                ImtThunkEntry* j = i;
                                ImtThunkEntry* nj = j - interval;
                                while ((nj >= beg) && nj->iid > temp.iid)
                                {
                                        AvmAssert(j >= beg && j < end);
                                        AvmAssert(nj >= beg && nj < end);
                                        *j = *nj;
                                        j = nj;
                                        nj = j - interval;
                                }
                                AvmAssert(j >= beg && j < end);
                                *j = temp;
                   }
                }
        }
        
        class ImtEntry: public MMgc::GCObject
        {
        public:
                inline ImtEntry(ImtEntry* n, MethodInfo* v, uint32_t d) : next(n), iid(v->iid()), disp_id(d) { }
                ImtEntry* const next;
                uintptr_t const iid;
                uintptr_t const disp_id;
        };

        static ImtEntry* buildImtEntries(VTable* vtable, uint32_t slot, uint32_t& count)
        {
                ImtEntry* map = NULL;
                count = 0;
                
                MMgc::GC* gc = vtable->traits->core->GetGC(); 
                Traitsp traits = vtable->traits;
                AvmAssert(!traits->isInterface());
                AvmAssert(traits->core->IsJITEnabled());
                
                // first check to see if we added any interfaces. if not, we can just inherit.
                // do this first, since it's pretty common and allows us to skip lots of hashtable lookups
                // and memory allocations.
                if (!traits->implementsNewInterfaces())
                        return NULL;
                
                TraitsBindingsp tb = traits->getTraitsBindings();
                for (InterfaceIterator ifc_iter(traits); ifc_iter.hasNext();)
                {
                        Traits* ifc = ifc_iter.next();
                        
                        TraitsBindingsp ifcd = ifc->getTraitsBindings();
                        StTraitsBindingsIterator iter(ifcd);
                        while (iter.next())
                        {
                                const Stringp name = iter.key();
                                if (name == NULL)
                                        continue;

                                const Namespacep ns = iter.ns();
                                const Binding iBinding = iter.value();

                                // taking some liberties here in the name of compact code...
                                // the opaque AvmCore accessors aren't flexible enough here,
                                // rely on knowledge of current Binding structure
                                const uint32_t iDispID = getRawDispID(iBinding);
                                const BindingKind ibk = AvmCore::bindingKind(iBinding);
                                Binding cBinding = BIND_NONE;
                                
                                MethodInfo* v0 = ((1<<ibk) & ((1<<BKIND_METHOD)|(1<<BKIND_GET)|(1<<BKIND_GETSET))) ? 
                                                                        ifcd->getMethod(iDispID) :
                                                                        NULL;

                                if (v0 && uint32_t(v0->iid() % VTable::IMT_SIZE) == slot)
                                {
                                        if (cBinding == BIND_NONE)
                                                cBinding = tb->findBinding(name, ns);
                                        AvmAssert(cBinding != BIND_NONE);
                                        map = new (gc) ImtEntry(map, v0, getRawDispID(cBinding));
                                        ++count;
                                }

                                MethodInfo* v1 = ((1<<ibk) & ((1<<BKIND_SET)|(1<<BKIND_GETSET))) ? 
                                                                        ifcd->getMethod(iDispID+1) :
                                                                        NULL;
                                if (v1 && uint32_t(v1->iid() % VTable::IMT_SIZE) == slot)
                                {
                                        if (cBinding == BIND_NONE)
                                                cBinding = tb->findBinding(name, ns);
                                        AvmAssert(cBinding != BIND_NONE);
                                        map = new (gc) ImtEntry(map, v1, getRawDispID(cBinding)+1);
                                        ++count;
                                }
                        } // for j
                }
                
                AvmAssert(map != NULL);
                return map;
        }

        /*static*/ GprImtThunkProcRetType VTable::dispatchImt(ImtThunkEnv* ite, int argc, uint32* ap, uintptr_t iid)
        {
                AvmAssert(ite->imtMapCount > 1);
                const ImtThunkEntry* const m = ite->entries();
                uint32_t lo = 0;
                uint32_t hi = ite->imtMapCount;
                while (lo < hi)
                {
                        uint32_t const mid = (lo + hi) >> 1;
                        if (m[mid].iid < iid)
                        {
                                lo = mid + 1;
                        }
                        else
                        {
                                hi = mid;
                        }
                }
                AvmAssert((lo < ite->imtMapCount) && (m[lo].iid == iid));
                ScriptObject* const receiver = *(ScriptObject**)ap;
                MethodEnv* const env = receiver->vtable->methods[m[lo].disp_id];
                return (*env->implGPR())(env, argc, ap);
        }

        /*static*/ GprImtThunkProcRetType VTable::resolveImt(ImtThunkEnv* ite, int argc, uint32* ap, uintptr_t iid)
        {
                const uint32_t slot = iid % IMT_SIZE;

                VTable* self = ite->vtable;
                
                self->resolveImtSlot(slot);

                ite = self->imt[slot]; // get the fresh, new one

                return (*ite->implImtGPR())(ite, argc, ap, iid);
        }

        // Copy the imt thunk from the base vtable - callers must make sure
        // that the stub can be copied from the base class - i.e. resolveImtSlotFromBase
        // or resolveImtSlotSelf must have already been called successfully on the base vtable.
        void VTable::resolveImtSlotFromBase(uint32_t slot)
        {
                AvmCore* core = traits->core;
                MMgc::GC* gc = core->GetGC();

                ImtThunkEnv* ite = base->imt[slot];
                // copy down imt stub from base class
                AvmAssert(ite != NULL);

                // if base->imt[i] is really an IMT thunk, use it.
                // BUT, it might be a plain MethodEnv* from a single-entry case, in which case
                // we want to use our own MethodEnv at the same disp-id. Alas, we don't have the disp-id 
                // handy at this point, since we didn't build the ImtEntry chain. Rather than build it in 
                // all cases, let's compare vs our parent's method list; linear search, but I'm guessing that's
                // still a net win vs. doing the ImtEntry chain building. (Our base's TB is most likely still
                // in the cache since we used it inside buildImtEntries.)
                TraitsBindingsp tb = base->traits->getTraitsBindings();
                for (uint32_t j = 0; j < tb->methodCount; ++j)
                {
                        if (ite == (ImtThunkEnv*)base->methods[j])
                        {
                                ite = (ImtThunkEnv*)this->methods[j];
                                break;
                        }
                }
                WB(gc, this, &imt[slot], ite);
        }

        // returns false if we need to copy the imt stub from base,
        // otherwise returns true
        bool VTable::resolveImtSlotSelf(uint32_t slot)
        {
                AvmAssert(this->linked);
                AvmAssert(this->base != NULL); // only Object has null base, and it has no Interfaces
                AvmAssert(!traits->isInterface());
                AvmAssert(traits->core->IsJITEnabled());
                
                ImtThunkEnv* ite;
                uint32_t imtMapCount = 0;

                ImtEntry* imtMap = buildImtEntries(this, slot, imtMapCount);
                if (!imtMap)
                {
                        return false;
                }
                else
                {
                        AvmCore* core = traits->core;
                        MMgc::GC* gc = core->GetGC();

                        AvmAssert(imtMapCount > 0);
                        if (imtMapCount == 1)
                        {
                                ite = (ImtThunkEnv*) this->methods[imtMap->disp_id];
                                gc->Free(imtMap);
                        }
                        else
                        {
                                ite = new (gc, imtMapCount * sizeof(ImtThunkEntry)) ImtThunkEnv(VTable::dispatchImt, imtMapCount);
                                //_nvprof("IMT ",MMgc::GC::Size(ite));
                                ImtThunkEntry* m = ite->entries();
                                ImtEntry* e = imtMap;
                                while (e)
                                {
                                        m->iid = e->iid;
                                        m->disp_id = e->disp_id;
                                        ++m;
                                        ImtEntry* t = e;
                                        e = e->next;
                                        gc->Free(t);
                                }
                                sortImtThunkEntries(ite->entries(), ite->imtMapCount);
                        }
                        WB(gc, this, &imt[slot], ite);
                }
                return true;
        }

        void VTable::resolveImtSlot(uint32_t slot)
        {
                AvmCore* core = traits->core;
                MMgc::GC* gc = core->GetGC();

                if( this->resolveImtSlotSelf(slot) )
                        return;

                List<VTable*> work_stack(gc);

                work_stack.add(this);

                // Walk up the base VTables until we find one where the slot
                // can be resolved without copying it from its base
                VTable* cur = this->base;
                while(cur->imt[slot]->implImtGPR() == VTable::resolveImt 
                        && !cur->resolveImtSlotSelf(slot) ) 
                {
                        work_stack.add(cur);
                        cur = cur->base;
                }

                // work backwards through the base types, copying
                // the imt stub down as we go
                uint32 size = work_stack.size();
                for(uint32 i = 0; i < size; ++i)
                {
                        cur = work_stack[size-i-1];
                        cur->resolveImtSlotFromBase(slot);
                }
        }
        
#endif // FEATURE_NANOJIT
        
        VTable::VTable(Traits* traits, VTable* _base, Toplevel* toplevel) :
                _toplevel(toplevel),
                init(NULL),
                base(_base),
                ivtable(NULL),
                traits(traits),
                linked(false)
        {
                AvmAssert(traits != NULL);
        }

        void VTable::resolveSignatures(ScopeChain* scope)
        {
                AvmAssert(scope != NULL);

                if( this->linked )
                        return;
                linked = true;
                if (!traits->isResolved())
                {
                        traits->resolveSignatures(toplevel());
                        traits->init_declaringScopes(scope->scopeTraits());
                }

#if defined(DEBUG) || defined(_DEBUG)
                // have to use local variables for CodeWarrior
                Traits* traitsBase = traits->base;
                Traits* baseTraits = base ? base->traits : 0;
                // make sure the traits of the base vtable matches the base traits
                AvmAssert((base == NULL && traits->base == NULL) || (base != NULL && traitsBase == baseTraits));
#endif // DEBUG

                AvmCore* core = traits->core;
                MMgc::GC* gc = core->GetGC();

                if (traits->init && !this->init)
                {
                        this->init = makeMethodEnv(traits->init, scope);
                }

                // populate method table

                const TraitsBindingsp td = traits->getTraitsBindings();
                const TraitsBindingsp btd = td->base;
                for (uint32_t i = 0, n = td->methodCount; i < n; i++)
                {
                        MethodInfo* method = td->getMethod(i);

                        if (btd && i < btd->methodCount && method == btd->getMethod(i))
                        {
                                        // inherited method
                                        //this->methods[i] = base->methods[i];
                                WB(gc, this, &methods[i], base->methods[i]);
                                continue;
                        }
                                        // new definition
                        if (method != NULL)
                        {
                                //this->methods[i] = new (gc) MethodEnv(method, this);
                                WB(gc, this, &methods[i], makeMethodEnv(method, scope));
                                continue;
                        }
                        #ifdef AVMPLUS_VERBOSE
                        if (traits->pool->isVerbose(VB_traits))
                        {
                                // why would the compiler assign sparse disp_id's?
                                traits->core->console << "WARNING: empty disp_id " << i << " on " << traits << "\n";
                        }
                        #endif
                }

                        // this is done here b/c this property of the traits isn't set until the
                        // Dictionary's ClassClosure is called
                if (base)
                        traits->isDictionary = base->traits->isDictionary;

#if defined FEATURE_NANOJIT
                if (traits->core->IsJITEnabled())
                {
                        ImtThunkEnv* ite = new (gc) ImtThunkEnv(VTable::resolveImt, this);
                        for (uint32_t i=0; i < IMT_SIZE; i++)
                        {
                                // they all share the same ImtThunkEnv for now 
                                // (lazily replaced in resolveImt by an inherited or new one)
                                WB(gc, this, &imt[i], ite);
                        }
                }
#endif
        }

        MethodEnv* VTable::makeMethodEnv(MethodInfo* func, ScopeChain* scope)
        {
                AvmCore* core = this->core();
                AbcEnv* abcEnv = scope->abcEnv();
                MethodEnv* methodEnv = new (core->GetGC()) MethodEnv(func, scope);
                // register this env in the callstatic method table
                int method_id = func->method_id();
                if (method_id != -1)
                {
                        AvmAssert(abcEnv->pool() == func->pool());
                        if (abcEnv->getMethod(method_id) == NULL)
                        {
                                abcEnv->setMethod(method_id, methodEnv);
                        }
                        #ifdef AVMPLUS_VERBOSE
                        else if (func->pool()->isVerbose(VB_traits))
                        {
                                core->console << "WARNING: tried to re-register global MethodEnv for " << func << "\n";
                        }
                        #endif
                }
                return methodEnv;
        }

#ifdef DEBUGGER
        uint32 VTable::size() const
        {
                uint32 size = sizeof(VTable);

                if(ivtable != NULL)
                        size += ivtable->size();

                const TraitsBindingsp td = traits->getTraitsBindings();
                const uint32_t n = td->methodCount;
                const uint32_t baseMethodCount = base ? td->base->methodCount : 0;
                size += td->methodCount*sizeof(MethodInfo*);

                for (uint32_t i=0; i < n; i++)
                {
                        MethodInfo* method = td->getMethod(i);
                        
                        if (i < baseMethodCount && td->base && method == td->base->getMethod(i))
                        {
                                continue;
                        }
                        else if(method != NULL)
                        {
                                size += method->size();
                        }
                }
                return size;
        }
#endif

        VTable* VTable::newParameterizedVTable(Traits* param_traits, Stringp fullname)
        {
                Toplevel* toplevel = this->toplevel();
                AvmCore* core = toplevel->core();
                Namespacep traitsNs = this->traits->ns();
                PoolObject* traitsPool = this->traits->pool;

                Stringp classname = core->internString(fullname->appendLatin1("$"));
                Traits* ctraits = traitsPool->getTraits(Multiname(traitsNs, classname), toplevel);
                Traits* itraits;
                if (!ctraits)
                {
                        ctraits = this->traits->newParameterizedCTraits(classname, traitsNs);
                        itraits = traitsPool->resolveParameterizedType(toplevel, this->ivtable->traits, param_traits);
                        ctraits->itraits = itraits;
                }
                else
                {
                        itraits = ctraits->itraits;
                }

                AvmAssert(itraits != NULL);
                itraits->resolveSignatures(toplevel);
                ctraits->resolveSignatures(toplevel);

                VTable* objVecVTable = toplevel->objectVectorClass->vtable;
                AbcEnv* objVecAbcEnv = toplevel->vectorobj_cscope->abcEnv();
                Toplevel* objVecToplevel = objVecVTable->toplevel();
                VTable* objVecIVTable = objVecVTable->ivtable;

                VTable* cvtab = core->newVTable(ctraits, objVecToplevel->class_ivtable, objVecToplevel); 
                ScopeChain* cvtab_cscope = toplevel->vectorobj_cscope->cloneWithNewVTable(core->GetGC(), cvtab, objVecAbcEnv);

                VTable* ivtab = core->newVTable(itraits, objVecIVTable, objVecToplevel);
                ScopeChain* ivtab_iscope = toplevel->vectorobj_iscope->cloneWithNewVTable(core->GetGC(), ivtab, objVecAbcEnv);
                cvtab->ivtable = ivtab;
                ivtab->init = objVecIVTable->init;

                cvtab->resolveSignatures(cvtab_cscope);
                ivtab->resolveSignatures(ivtab_iscope);
                
                return cvtab;
        }
}

/* [<][>][^][v][top][bottom][index][help] */