BinaryInstructionCache.h

#ifndef ROSE_BinaryAnalysis_InstructionCache_H
#define ROSE_BinaryAnalysis_InstructionCache_H
#include <featureTests.h>
#if defined(ROSE_ENABLE_BINARY_ANALYSIS) && __cplusplus >= 201103L
#include <memory>
#include <unordered_map>

namespace Rose {
namespace BinaryAnalysis {

class Disassembler; // from Disassembler.h, but we only need the forward here.
class InstructionCache;
class InstructionPtr;
class LockedInstruction;
class ManagedInstruction;

// ManagedInstruction

class ManagedInstruction {
private:
    // Every ManagedInstruction is owned by a cache. The user might create additional shared pointers to this object, but as long
    // as any ManagedInstruction object exists and can potentially be in the ABSENT state, we need to have a cache that can
    // reconstruct the AST.
    InstructionCache *cache; // not null, set by constructor and never changed

    // Protects all following data members
    mutable SAWYER_THREAD_TRAITS::Mutex mutex_;

    // As is typical of cache-like objects, most of the data members are mutable because the some of the member functions that
    // modify them are conceptually const. For example, the operator-> is simply a dereference from the caller's point of void
    // and is thus const, but under the covers it needs to be able to convert this object from the ABSENT state to the PRESENT
    // state.

    // "time" of last dereference. This informs the cache eviction algorithm.
    mutable size_t lastAccess;

    // C++11 doesn't have discriminated unions like C++17, so we do it the hard way.
    enum State {
        ABSENT,                          // the pointer is non-null but the AST is not present 
        PRESENT                          // the AST is present or is a null pointer
    };
    mutable State state;
    union U {
        SgAsmInstruction *ast;         // the AST or null when in the PRESENT state
        rose_addr_t va;                 // the instruction starting address when in the ABSENT state.
    };
    mutable U u;

private:
    friend class InstructionCache;

    ManagedInstruction() = delete;
    ManagedInstruction(const ManagedInstruction&) = delete;
    ManagedInstruction& operator=(const ManagedInstruction&) = delete;

    ManagedInstruction(InstructionCache *cache, rose_addr_t va)
        : cache{cache}, state{ABSENT}, u{.va = va} {
        ASSERT_not_null(cache);
    }

    explicit ManagedInstruction(InstructionCache *cache)
        : cache{cache}, state{PRESENT}, u{.ast = nullptr} {
        ASSERT_not_null(cache);
    }

    // There is no safe way to do this with implicit locking. Any reference we would return could be held indefinitely by the
    // caller and there's no way we can automatically lock it.
    SgAsmInstruction& operator*() const = delete;

public:
    LockedInstruction operator->() const;               // hot

private:
    friend class InstructionPtr;

    // True if the underlying instructon is a null pointer.
    bool isNull() const;                                // hot

    // Create a locking pointer around the AST, and mark the AST as having been accessed.
    LockedInstruction lock() const;                     // hot

    // Make sure the AST is present and return a special pointer that causes it to be locked in the cache. The function is const
    // because it's typically called from a const context (pointer dereference) and from the user's point of void is constant even
    // though under the covers it's creating a new AST and swapping it into this object.
    LockedInstruction makePresentNS() const;            // hot

    // Evicts the AST from memory, deleting it from this object and replacing it with only the instruction address. The
    // instruction address, together with the information stored in the cache, is enough to recreate the AST if we ever need it
    // again.
    void evict();
    
    // Update the last access time used by the cache eviction algorithm.  The function is const because it's typically called
    // in a const context (pointer dereferencing).
    void updateTimerNS() const;                         // hot

    // Take the AST and its ownership away from this object, returning the AST. Throws an exception if the AST is locked, since
    // its not possible for the returned raw pointer and the cache to share ownership.
    SgAsmInstruction* take();
};

// LockedInstruction

class LockedInstruction {
private:
    mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects all following data members
    SgAsmInstruction *insn;

public:
    LockedInstruction();

    explicit LockedInstruction(SgAsmInstruction *insn); // hot

    explicit LockedInstruction(const InstructionPtr &insn);

    LockedInstruction(const LockedInstruction &other);

    LockedInstruction& operator=(const LockedInstruction &other);

    ~LockedInstruction();                               // hot

    void reset();

    SgAsmInstruction& operator*() const;

    SgAsmInstruction* operator->() const;               // hot

    SgAsmInstruction* get() const;

    explicit operator bool() const;
};

// InstructionPtr

class InstructionPtr {
    mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects all following data members
    std::shared_ptr<ManagedInstruction> mi_;

public:
    InstructionPtr() {}

    InstructionPtr(const InstructionPtr &other)
        : mi_(other.mi_) {}


    InstructionPtr& operator=(const InstructionPtr &other); // hot

    void reset();

    // Dereferences are inherently unsafe because we have no opportunity to lock the instruction in a way that we can then unlock
    // it, and we have no control over the lifetime of the reference that we would return.
    SgAsmInstruction& operator*() const = delete;

    LockedInstruction operator->() const;               // hot

    explicit operator bool() const;                     // hot

    LockedInstruction lock() const;

    SgAsmInstruction* take();

    bool operator==(const InstructionPtr &other) const;
    bool operator!=(const InstructionPtr &other) const;
    bool operator<=(const InstructionPtr &other) const;
    bool operator>=(const InstructionPtr &other) const;
    bool operator<(const InstructionPtr &other) const;
    bool operator>(const InstructionPtr &other) const;
    bool operator==(std::nullptr_t) const;
    bool operator!=(std::nullptr_t) const;              // hot
private:
    friend class InstructionCache;

    // Construct pointer to a ManagedInstruction that exists in an instruction cache. */
    static InstructionPtr instance(InstructionCache *cache, rose_addr_t va);
    static InstructionPtr instance(InstructionCache *cache);
};

// InstructionCache

class InstructionCache: public Sawyer::SharedObject {
public:
    class Exception: public Rose::Exception {
    public:
        Exception(const std::string &mesg)
            : Rose::Exception(mesg) {}
        ~Exception() throw() {}
    };

private:
    MemoryMap::Ptr memory_; // not null, constant for life of object
    Disassembler *decoder_; // not null, constant for life of object

    mutable SAWYER_THREAD_TRAITS::Mutex mutex_; // protects all following data members
    std::unordered_map<rose_addr_t, InstructionPtr> insns_;

    InstructionCache(const InstructionCache&) = delete;
    InstructionCache& operator=(const InstructionCache&) = delete;

public:
    InstructionCache(const MemoryMap::Ptr &memory, Disassembler *decoder)
        : memory_(memory), decoder_(decoder) {
        ASSERT_not_null(memory);
        ASSERT_not_null(decoder);
    }

    MemoryMap::Ptr memoryMap() const {
        return memory_; // mo lock necessary since memory_ can never change
    }

    Disassembler* decoder() const {
        return decoder_; // no lock necessary since decoder_ can never change.
    }
    
    InstructionPtr get(rose_addr_t va);

    LockedInstruction lock(rose_addr_t va);

    void evict();

private:
    friend class ManagedInstruction;

    // Decode a single instruction at the specified address. This function is thread safe.
    SgAsmInstruction* decode(rose_addr_t);
};

// InstructionGuard

class InstructionGuard {
    // The InstructionGuard was originally slightly more complicated, but the intruction of the automatic temporary locking
    // made it a lot simpler! All we need to do is hold onto a locked instruction pointer. However, we keep this class around because
    // it's better documentation for the programmer's intent than simply holding a locked pointer.
    LockedInstruction lock;

public:
    explicit InstructionGuard(const InstructionPtr &insn)
        : lock(insn) {}
};

// Inline definitions for hot functions

inline InstructionPtr&
InstructionPtr::operator=(const InstructionPtr &other) {
    SAWYER_THREAD_TRAITS::LockGuard2 lock(mutex_, other.mutex_);
    mi_ = other.mi_;
    return *this;
}

inline LockedInstruction
InstructionPtr::operator->() const {
    SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
    ASSERT_not_null(mi_);
    ManagedInstruction &mi = *mi_.get();
    return mi.lock();
}

inline LockedInstruction
ManagedInstruction::operator->() const {
    return lock();
}

inline LockedInstruction
ManagedInstruction::lock() const {
    SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
    updateTimerNS();
    return makePresentNS();
}

inline void
ManagedInstruction::updateTimerNS() const {
    static size_t nextTimer = 0;
    lastAccess = ++nextTimer;
}

inline LockedInstruction
ManagedInstruction::makePresentNS() const {
    if (ABSENT == state) {                              // unlikely
        SgAsmInstruction *decoded = cache->decode(u.va);
        ASSERT_not_null(decoded); // at worst, the decoder will return an unknown instruction
        state = PRESENT; // no-throw
        u.ast = decoded; // no-throw
    }
    return LockedInstruction{u.ast};
}

inline
LockedInstruction::LockedInstruction(SgAsmInstruction *insn)
    : insn(insn) {
    if (insn)
        insn->adjustCacheLockCount(+1);                 // ROSETTA generated, thus cannot be inlined
}

inline
LockedInstruction::~LockedInstruction() {
  if (insn)
      insn->adjustCacheLockCount(-1);
}

inline SgAsmInstruction*
LockedInstruction::operator->() const {
    SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
    ASSERT_not_null(insn);
    return insn;
}

inline
InstructionPtr::operator bool() const {
    SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
    return mi_.get() ? !(*mi_).isNull() : false;
}

inline bool
ManagedInstruction::isNull() const {
    SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
    // A null pointer can be in the absent state only if it was never yet in the present state. This is because all we know
    // about an absent pointer is it's address, not whether we can create an instruction AST at that address. Therefore, we
    // have to try to create the AST.
    makePresentNS();
    return u.ast == nullptr;
}

inline bool
InstructionPtr::operator!=(const std::nullptr_t) const {
    SAWYER_THREAD_TRAITS::LockGuard lock(mutex_);
    return mi_ && !(*mi_).isNull()? true : false;
}




} // namespace
} // namespacd
#endif
#endif