SimpleMemoryMap.hpp

Go to the documentation of this file.

 
#pragma once
 
#include "sparta/memory/MemoryExceptions.hpp"
#include "sparta/memory/AddressTypes.hpp"
#include "sparta/memory/BlockingMemoryIF.hpp"
 
namespace sparta
{
    namespace memory
    {
        class SimpleMemoryMap
        {
        public:
 
            struct Mapping
            {
                Mapping(addr_t _start, addr_t _end, BlockingMemoryIF* _memif, addr_t _dest_off) :
                    start(_start),
                    end(_end),
                    dest_off(_dest_off),
                    memif(_memif)
                {
                    sparta_assert(memif != nullptr);
                }
 
                const addr_t start;
 
                const addr_t end;
 
                const addr_t dest_off;
 
                BlockingMemoryIF* const memif;
 
                addr_t mapAddress(addr_t input) const noexcept {
                    return (input - start) + dest_off;
                }
 
                bool contains(addr_t a) const noexcept {
                    return a >= start && a < end;
                }
 
                bool overlaps(addr_t a, addr_t b) const noexcept {
                    return (a >= start && a < end) || (b > start && b <= end) || (a < start && b > end);
                }
            };
 
 
            SimpleMemoryMap() = delete;
 
            SimpleMemoryMap(addr_t block_size) :
                block_size_(block_size),
                bintree_(nullptr),
                num_mappings_(0)
            {
                sparta_assert(block_size > 0, "block size must be greater than 0");
                block_idx_rshift_ = (addr_t)log2(block_size);
                block_offset_mask_ = (1 << block_idx_rshift_) - 1;
            }
 
            virtual ~SimpleMemoryMap() {
                delete bintree_;
            }
 
 
 
            void addMapping(addr_t start,
                            addr_t end,
                            BlockingMemoryIF* memif,
                            addr_t dest_start) {
                sparta_assert(memif);
                sparta_assert(memif->getBlockSize() == block_size_);
                sparta_assert(start < end);
                sparta_assert((start & block_offset_mask_) == 0);
                sparta_assert((end & block_offset_mask_) == 0);
                sparta_assert((dest_start & block_offset_mask_) == 0);
 
                const addr_t required_range = (end-start) + dest_start;
                if(memif->getRange() < required_range){
                    throw SpartaException("Total range of destination memory interface is ")
                        << "too small to contain all mappings from SimpleMemoryMap mapping "
                        << "[" << start << ", " << end << ") -> " << memif
                        << " with dest_start" << dest_start << ". Mapped input range size "
                        << "exceeds memory interface (with range " << memif->getRange()
                        << " by " << required_range - memif->getRange();
                }
 
                // Verify that the stand and end addresses do not contain do not
                // overlap any mappings. This information could be extracted
                // from the tree, but it is simple to explicitly test here to
                // ensure that no tree changes need to be rolled back. There is no
                // performance concern for insertion
                for(auto& m : mappings_) {
                    if(m->overlaps(start,end)){
                        throw SpartaException("Cannot add another mapping [")
                            << start << ", " << end
                            << ") which overlaps another. "
                            << " mapping occupying [" << m->start
                            << ", " << m->end << ")";
                    }
                }
 
                addr_t min = 0;
                addr_t max = ~(addr_t)0;
                BinTreeNode* n = bintree_;
 
                // Insert left endpoint
                if(!n){
                    // No root yet
                    min = start;
                    n = bintree_ = new BinTreeNode(nullptr, start);
                    RBTreeFixup_(n);
                    // No fixing should actually have taken place
                }else{
                    while(1){
                        if(n->dest != nullptr){
                            Mapping* m = n->dest.get();
                            // Children nodes on a side will always exist if start is outside this mapping on that side
                            if(start < m->start){
                                sparta_assert(n->l);
                                n = n->l;
                            }else if(start >= m->end){
                                sparta_assert(n->r);
                                n = n->r;
                            }else{
                                throw SpartaException("Cannot add another mapping [")
                                    << start << ", " << end
                                    << ") in a range previously occupied by another. "
                                    << "Destination found occupying [" << m->start
                                    << ", " << m->end << "). Found when placing left endpoint";
                            }
                        }else if(n->separator == start){
                            // Insert right endpoint immediately
                            min = start;
                            //std::cout << "\nAlready had START sepatator @ " << start << std::endl;
                            break;
                        }else if(n->separator < start){
                            min = n->separator;
                            if(n->r){
                                sparta_assert(n->separator >= min);
                                n = n->r;
                            }else{
                                n->r = new BinTreeNode(n, start);
                                n = n->r;
                                RBTreeFixup_(n);
                                // If n was relocated up in the tree, the right-endpoint
                                // insertion loop will find it.
                                break;
                            }
                        }else{
                            max = n->separator;
                            if(n->l){
                                sparta_assert(n->separator <= max);
                                n = n->l;
                            }else{
                                n->l = new BinTreeNode(n, start);
                                n = n->l;
                                RBTreeFixup_(n);
                                // If n was relocated up in the tree, the right-endpoint
                                // insertion loop will find it.
                                break;
                            }
                        }
                    } // while(1)
                } // if(!n) { } else {
 
                // Insert right endpoint
                while(1){
                    if(n->dest != nullptr){
                        Mapping* m = n->dest.get();
                        // Children nodes on a side will always exist if start is outside this mapping on that side
                        if(end <= m->start){
                            assert(n->l);
                            n = n->l;
                        }else if(end > m->end){
                            sparta_assert(n->r);
                            n = n->r;
                        }else{
                            throw SpartaException("Cannot add another mapping [")
                                << std::hex << start << ", " << end
                                << ") in a range previously occupied by another. "
                                << "Destination found occupying [" << m->start
                                << ", " << m->end << "). Found when placing right endpoint";
                        }
                    }else if(n->separator == end){
                        // Insert destination now
                        max = end;
                        //std::cout << "\nAlready had END sepatator @ " << end << std::endl;
                        break;
                    }else if(n->separator < start){
                        throw SpartaException("Node separator ")
                            << n->separator
                            << " encountered when placing right endpoint cannot be less than the start of the range";
                    }else if(n->separator == start){
                        min = n->separator;
                        if(n->r){
                            sparta_assert(n->separator <= max);
                            n = n->r;
                        }else{
                            // Is new endpoint required or is this node already constrained by ancestors
                            if(max != end){
                                n->r = new BinTreeNode(n, end);
                                n = n->r;
                                RBTreeFixup_(n);
                            }
                            break;
                        }
                    }else if(n->separator < end){
                        throw SpartaException("Cannot add another mapping [")
                            << std::hex << start << ", " << end
                            << ") in a range previously occupied by another. "
                            << "Separator at " << n->separator
                            << " found occupying [" << min << ", " << max << ")";
                    }else{
                        // n->sepatator > end
                        max = n->separator;
                        if(n->l){
                            sparta_assert(n->separator <= max);
                            n = n->l;
                        }else{
                            // Is new endpoint required or is this node already constrained by ancestors
                            if(max != end){
                                n->l = new BinTreeNode(n, end);
                                n = n->l;
                                RBTreeFixup_(n);
                            }
                            break;
                        }
                    }
                } // while(1)
 
                // Place final destination node
                // This will always be a child of a separator node. We cannot
                // have two destination nodes in a parent-child relationship
                // because separator nodes always define their edges.
                sparta_assert(n);
                sparta_assert(n->separator != ~0ULL);
                std::unique_ptr<Mapping> m(new Mapping(start, end, memif, dest_start));
                if(end <= n->separator){
                    if(n->l){
                        // Fixup moved n around and attached a left child where
                        // the destination node would be. Find the start separator node
                        n = findSeparatorNode_(bintree_, start);
                        sparta_assert(!n->r); // Ensure this has no children to the left that we might be about to replace
                        n->r = new BinTreeNode(n, std::move(m)); // Takes ownership
                        n = n->r;
                    }else{
                        n->l = new BinTreeNode(n, std::move(m)); // Takes ownership
                        n = n->l;
                    }
                }else if(start >= n->separator){
                    if(n->r){
                        // Fixup moved n around and attached a right child where
                        // the destination node would be. Find the end separator node
                        n = findSeparatorNode_(bintree_, end);
                        sparta_assert(!n->l); // Ensure this has no children to the right that we might be about to replace
                        n->l = new BinTreeNode(n, std::move(m)); // Takes ownership
                        n = n->l;
                    }else{
                        n->r = new BinTreeNode(n, std::move(m)); // Takes ownership
                        n = n->r;
                    }
                }else{
                    throw SpartaException("Error placing destination mapping node [")
                        << start << ", " << end << "). Range somehow spanned a separator at " << n->separator << ". This should not have occurred";
                }
                RBTreeFixup_(n);
 
                num_mappings_ += 1;
                mappings_.push_back(n->dest.get());
            }
 
            void dumpTree(std::ostream& o) const {
                if(bintree_){
                    bintree_->recursDump(o);
                }
            }
 
            void dumpMappings(std::ostream& o) const {
                uint32_t desc_len = 1;
                uint32_t start_len = 1;
                uint32_t end_len = 1;
                for(const Mapping* m : mappings_){
                    desc_len = std::max<uint32_t>(m->memif->getDescription().size(), desc_len);
                    std::stringstream tmp;
                    tmp << std::showbase << std::hex << m->start;
                    start_len = std::max<uint32_t>(tmp.str().size(), start_len);
                    tmp.str("");
                    tmp << std::showbase << std::hex << m->end;
                    end_len = std::max<uint32_t>(tmp.str().size(), end_len);
                }
 
                // Sort content
                std::vector<const Mapping*> sorted = mappings_;
 
                std::sort(sorted.begin(), sorted.end(),
                          [](const Mapping* m1, const Mapping* m2){return m1->start < m2->start;});
 
                auto f = o.flags();
                for(const Mapping* m : sorted){
                    o << "map: [" << std::hex << std::showbase << std::setw(start_len)
                      << m->start << ", " << std::setw(end_len) << m->end
                      << std::noshowbase << ") -> \"" << std::setw(desc_len)
                      << m->memif->getDescription() << "\" +0x" << m->dest_off<< '\n';
                }
                o.flags(f);
            }
 
            BlockingMemoryIF* findInterface(addr_t addr) {
                Mapping* m = findMapping(addr);
                if(!m){
                    return nullptr;
                }
                return m->memif;
            }
 
            Mapping* findMapping(addr_t addr) {
                // Navigate the bintree to find the addr (if contained)
                BinTreeNode* n = bintree_;
                Mapping* m = nullptr;
 
                // Search tree for first mapping
                while(n){
                    if(n->dest){
                        m = n->dest.get();
                        if(addr < m->start){
                            n = n->l;
                        }else if(addr >= m->end){
                            n = n->r;
                        }else{
                            return m;
                        }
                    }else if(addr >= n->separator){
                        n = n->r;
                    }else{
                        n = n->l;
                    }
                }
                if(!n){
                    return nullptr;
                }
 
                return m;
            }
 
            const Mapping* findMapping(addr_t addr) const {
                // Navigate the bintree to find the addr (if contained)
                const BinTreeNode* n = bintree_;
                const Mapping* m = nullptr;
 
                // Search tree for first mapping
                while(n){
                    if(n->dest){
                        m = n->dest.get();
                        if(addr < m->start){
                            n = n->l;
                        }else if(addr >= m->end){
                            n = n->r;
                        }else{
                            return m;
                        }
                    }else if(addr >= n->separator){
                        n = n->r;
                    }else{
                        n = n->l;
                    }
                }
                if(!n){
                    return nullptr;
                }
                return m;
            }
 
            void verifyHasMapping(addr_t addr, addr_t size) const {
                const addr_t end = addr+size;
 
                const BinTreeNode* n = bintree_;
                const Mapping* m = nullptr;
 
                while(n){
                    if(n->dest){
                        m = n->dest.get();
                        if(addr < m->start){
                            n = n->l;
                        }else if(addr >= m->end){
                            n = n->r;
                        }else if(end <= m->end){
                            return; // Ok. Reached a destination containing both addr and end
                        }else{
                            throw MemoryAccessError(addr, size, "any", "This access spans more than one mapping");
                        }
                    }else if(addr >= n->separator){
                        n = n->r;
                    }else{
                        n = n->l;
                    }
                }
                throw MemoryAccessError(addr, size, "any", "No single mapping found for this address/size");
            }
 
            std::pair<const BlockingMemoryIF*, addr_t> mapAddress(addr_t addr) const noexcept {
                const Mapping* m = findMapping(addr);
                if(!m){
                    return {nullptr, 0};
                }
                return {m->memif, m->mapAddress(addr)};
            }
 
            uint32_t getNumMappings() const {
                return num_mappings_;
            }
 
            const std::vector<const Mapping*>& getMappings() const {
                return mappings_;
            }
 
 
 
            addr_t getBlockSize() const { return block_size_; }
 
 
            std::string stringize(bool pretty=false) const {
                (void) pretty;
                std::stringstream ss;
                ss << "<SimpleMemoryMap " << num_mappings_ << " mappings>";
                return ss.str();
            }
 
        private:
 
            struct BinTreeNode
            {
                BinTreeNode() = delete;
 
                BinTreeNode(const BinTreeNode&) = delete;
 
                BinTreeNode& operator=(const BinTreeNode&) = delete;
 
                BinTreeNode(BinTreeNode* p, addr_t sep) :
                    separator(sep),
                    parent(p),
                    l(nullptr),//new BinTreeNode(this)), // Leaf
                    r(nullptr),//new BinTreeNode(this)), // Leaf
                    dest(nullptr),
                    red(true)
                { }
 
                BinTreeNode(BinTreeNode* p, Mapping* d) :
                    separator(~(addr_t)0),
                    parent(p),
                    l(nullptr),//new BinTreeNode(this)), // Leaf
                    r(nullptr),//new BinTreeNode(this)), // Leaf
                    dest(d),
                    red(true)
                { }
 
                BinTreeNode(BinTreeNode* p, std::unique_ptr<Mapping>&& d) :
                    separator(~(addr_t)0),
                    parent(p),
                    l(nullptr),//new BinTreeNode(this)), // Leaf
                    r(nullptr),//new BinTreeNode(this)), // Leaf
                    dest(std::move(d)),
                    red(true)
                { }
 
                ~BinTreeNode() {
                    delete l;
                    delete r;
                }
 
                BinTreeNode* grandparent() {
                    if(parent){
                        return parent->parent;
                    }
                    return nullptr;
                }
 
                BinTreeNode* uncle() {
                    BinTreeNode *g = grandparent();
                    if(!g){
                        return nullptr;
                    }
                    if(parent == g->l){
                        return g->r;
                    }
                    return g->l;
                }
 
                void recursDump(std::ostream& o, int depth=0) const {
                    auto f = o.flags();
                    if(red){
                        o << "(R) ";
                    }else{
                        o << "(B) ";
                    }
                    if(dest){
                        o << "map: [0x" << std::hex << dest->start << ", 0x" << dest->end
                          << ") -> memif:" << dest->memif << " \"" << dest->memif->getDescription() << "\" dest_offset=+0x" << dest->dest_off<< '\n';
                    }else{
                        o << "sep: " << std::hex << "0x" << separator << '\n';
                    }
 
                    o.flags(f);
 
                    for(int i=0; i<depth; ++i){
                        o << "  ";
                    }
                    o << "l: ";
                    if(l){
                        l->recursDump(o, depth+1);
                    }else{
                        o << "-\n";
                    }
 
                    for(int i=0; i<depth; ++i){
                        o << "  ";
                    }
                    o << "r: ";
                    if(r){
                        r->recursDump(o, depth+1);
                    }else{
                        o << "-\n";
                    }
                }
 
                const addr_t separator; 
                BinTreeNode* parent;    
                BinTreeNode* l;         
                BinTreeNode* r;         
                const std::unique_ptr<Mapping> dest; 
                bool red;               
            };
 
            void RBTreeFixup_(BinTreeNode* n){
                sparta_assert(n);
 
                n->red = true; // Inserted node colored red
                // Ascend tree and fix RB-Tree rule violations
                while((bintree_ != n) && (n->parent->red)){
                    if(n->parent == n->parent->parent->l){
                        BinTreeNode* u = n->parent->parent->r;
                        if(u && u->red){
                            // RB-Tree case 1 - Recolor
                            n->parent->red = false;
                            u->red = false;
                            n->parent->parent->red = true;
                            n = n->parent->parent;
                        }else{
                            // Uncle is black (RB-Tree null-leafs would be black)
                            if(n == n->parent->r){
                                // RB-Tree case 2 - move n up and rotate left
                                n = n->parent;
                                rotateLeft_(n);
                            }
                            // RB-Tree case 3 - Recolor
                            n->parent->red = false;
                            n->parent->parent->red = true;
                            rotateRight_(n->parent->parent);
                        }
                    }else{
                        // Identical to logic in previous if statement with l/r reversed
                        BinTreeNode* u = n->parent->parent->l;
                        if(u && u->red){
                            n->parent->red = false;
                            u->red = false;
                            n->parent->parent->red = true;
                            n = n->parent->parent;
                        }else{
                            if(n == n->parent->l){
                                n = n->parent;
                                rotateRight_(n);
                            }
                            n->parent->red = false;
                            n->parent->parent->red = true;
                            rotateLeft_(n->parent->parent);
                        }
                    }
                }
 
                bintree_->red = false; // RB-Tree root is always blackx
            }
 
            BinTreeNode* findSeparatorNode_(BinTreeNode* root, addr_t addr) {
                BinTreeNode* n = root;
                while(1){
                    if(n->dest){
                        const Mapping* m = n->dest.get();
                        if(addr < m->start){
                            n = n->l;
                        }else if(addr >= m->end){
                            n = n->r;
                        }else{
                            throw SpartaException("Looking for a separator node at addr=")
                                << addr << " ended up within a mapping node";
                        }
                    }else if(addr == n->separator){
                        return n;
                    }else if(addr > n->separator){
                        n = n->r;
                    }else{
                        n = n->l;
                    }
                }
                return n;
            }
 
            void rotateLeft_(BinTreeNode* n){
                sparta_assert(n);
                sparta_assert(n->r);
                BinTreeNode* pivot = n->r;
                n->r = pivot->l;
                if(n->r){
                    n->r->parent = n;
                }
                pivot->parent = n->parent;
 
                if(n->parent == nullptr){
                    bintree_ = pivot;
                }else{
                    if(n == n->parent->l){
                        n->parent->l = pivot;
                    }else{
                        n->parent->r = pivot;
                    }
                }
                pivot->l = n;
                n->parent = pivot;
            }
 
            void rotateRight_(BinTreeNode* n){
                sparta_assert(n);
                sparta_assert(n->l);
                BinTreeNode* pivot = n->l;
                n->l = pivot->r;
                if(n->l){
                    n->l->parent = n;
                }
                pivot->parent = n->parent;
 
                if(n->parent == nullptr){
                    bintree_ = pivot;
                }else{
                    if(n == n->parent->r){
                        n->parent->r = pivot;
                    }else{
                        n->parent->l = pivot;
                    }
                }
                pivot->r = n;
                n->parent = pivot;
            }
 
            addr_t block_size_;
 
            BinTreeNode* bintree_;
 
            uint32_t num_mappings_;
 
            std::vector<const Mapping*> mappings_;
 
            addr_t block_idx_rshift_;
 
            addr_t block_offset_mask_;
 
        }; // class SimpleMemoryMap
    } // namespace memory
} // namespace sparta
 
 
inline std::ostream& operator<<(std::ostream& out, const sparta::memory::SimpleMemoryMap& mi) {
    out << mi.stringize();
    return out;
}
 
inline std::ostream& operator<<(std::ostream& out, const sparta::memory::SimpleMemoryMap* mi) {
    if(nullptr == mi){
        out << "null";
    }else{
        out << mi->stringize();
    }
    return out;
}