src/arch/x86/pagetable_walker.cc - public/gem5 - Git at Google

 /*
  * Copyright (c) 2012 ARM Limited
  * All rights reserved.
  *
  * The license below extends only to copyright in the software and shall
  * not be construed as granting a license to any other intellectual
  * property including but not limited to intellectual property relating
  * to a hardware implementation of the functionality of the software
  * licensed hereunder.  You may use the software subject to the license
  * terms below provided that you ensure that this notice is replicated
  * unmodified and in its entirety in all distributions of the software,
  * modified or unmodified, in source code or in binary form.
  *
  * Copyright (c) 2007 The Hewlett-Packard Development Company
  * All rights reserved.
  *
  * The license below extends only to copyright in the software and shall
  * not be construed as granting a license to any other intellectual
  * property including but not limited to intellectual property relating
  * to a hardware implementation of the functionality of the software
  * licensed hereunder.  You may use the software subject to the license
  * terms below provided that you ensure that this notice is replicated
  * unmodified and in its entirety in all distributions of the software,
  * modified or unmodified, in source code or in binary form.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met: redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer;
  * redistributions in binary form must reproduce the above copyright
  * notice, this list of conditions and the following disclaimer in the
  * documentation and/or other materials provided with the distribution;
  * neither the name of the copyright holders nor the names of its
  * contributors may be used to endorse or promote products derived from
  * this software without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  *
  * Authors: Gabe Black
  */

 #include "arch/x86/pagetable_walker.hh"

 #include <memory>

 #include "arch/x86/faults.hh"
 #include "arch/x86/pagetable.hh"
 #include "arch/x86/tlb.hh"
 #include "arch/x86/vtophys.hh"
 #include "base/bitfield.hh"
 #include "base/trie.hh"
 #include "cpu/base.hh"
 #include "cpu/thread_context.hh"
 #include "debug/PageTableWalker.hh"
 #include "mem/packet_access.hh"
 #include "mem/request.hh"

 namespace X86ISA {

 Fault
 Walker::start(ThreadContext * _tc, BaseTLB::Translation *_translation,
               const RequestPtr &_req, BaseTLB::Mode _mode)
 {
     // TODO: in timing mode, instead of blocking when there are other
     // outstanding requests, see if this request can be coalesced with
     // another one (i.e. either coalesce or start walk)
     WalkerState * newState = new WalkerState(this, _translation, _req);
     newState->initState(_tc, _mode, sys->isTimingMode());
     if (currStates.size()) {
         assert(newState->isTiming());
         DPRINTF(PageTableWalker, "Walks in progress: %d\n", currStates.size());
         currStates.push_back(newState);
         return NoFault;
     } else {
         currStates.push_back(newState);
         Fault fault = newState->startWalk();
         if (!newState->isTiming()) {
             currStates.pop_front();
             delete newState;
         }
         return fault;
     }
 }

 Fault
 Walker::startFunctional(ThreadContext * _tc, Addr &addr, unsigned &logBytes,
               BaseTLB::Mode _mode)
 {
     funcState.initState(_tc, _mode);
     return funcState.startFunctional(addr, logBytes);
 }

 bool
 Walker::WalkerPort::recvTimingResp(PacketPtr pkt)
 {
     return walker->recvTimingResp(pkt);
 }

 bool
 Walker::recvTimingResp(PacketPtr pkt)
 {
     WalkerSenderState * senderState =
         dynamic_cast<WalkerSenderState *>(pkt->popSenderState());
     WalkerState * senderWalk = senderState->senderWalk;
     bool walkComplete = senderWalk->recvPacket(pkt);
     delete senderState;
     if (walkComplete) {
         std::list<WalkerState *>::iterator iter;
         for (iter = currStates.begin(); iter != currStates.end(); iter++) {
             WalkerState * walkerState = *(iter);
             if (walkerState == senderWalk) {
                 iter = currStates.erase(iter);
                 break;
             }
         }
         delete senderWalk;
         // Since we block requests when another is outstanding, we
         // need to check if there is a waiting request to be serviced
         if (currStates.size() && !startWalkWrapperEvent.scheduled())
             // delay sending any new requests until we are finished
             // with the responses
             schedule(startWalkWrapperEvent, clockEdge());
     }
     return true;
 }

 void
 Walker::WalkerPort::recvReqRetry()
 {
     walker->recvReqRetry();
 }

 void
 Walker::recvReqRetry()
 {
     std::list<WalkerState *>::iterator iter;
     for (iter = currStates.begin(); iter != currStates.end(); iter++) {
         WalkerState * walkerState = *(iter);
         if (walkerState->isRetrying()) {
             walkerState->retry();
         }
     }
 }

 bool Walker::sendTiming(WalkerState* sendingState, PacketPtr pkt)
 {
     WalkerSenderState* walker_state = new WalkerSenderState(sendingState);
     pkt->pushSenderState(walker_state);
     if (port.sendTimingReq(pkt)) {
         return true;
     } else {
         // undo the adding of the sender state and delete it, as we
         // will do it again the next time we attempt to send it
         pkt->popSenderState();
         delete walker_state;
         return false;
     }

 }

 Port &
 Walker::getPort(const std::string &if_name, PortID idx)
 {
     if (if_name == "port")
         return port;
     else
         return ClockedObject::getPort(if_name, idx);
 }

 void
 Walker::WalkerState::initState(ThreadContext * _tc,
         BaseTLB::Mode _mode, bool _isTiming)
 {
     assert(state == Ready);
     started = false;
     tc = _tc;
     mode = _mode;
     timing = _isTiming;
 }

 void
 Walker::startWalkWrapper()
 {
     unsigned num_squashed = 0;
     WalkerState *currState = currStates.front();
     while ((num_squashed < numSquashable) && currState &&
         currState->translation->squashed()) {
         currStates.pop_front();
         num_squashed++;

         DPRINTF(PageTableWalker, "Squashing table walk for address %#x\n",
             currState->req->getVaddr());

         // finish the translation which will delete the translation object
         currState->translation->finish(
             std::make_shared<UnimpFault>("Squashed Inst"),
             currState->req, currState->tc, currState->mode);

         // delete the current request if there are no inflight packets.
         // if there is something in flight, delete when the packets are
         // received and inflight is zero.
         if (currState->numInflight() == 0) {
             delete currState;
         } else {
             currState->squash();
         }

         // check the next translation request, if it exists
         if (currStates.size())
             currState = currStates.front();
         else
             currState = NULL;
     }
     if (currState && !currState->wasStarted())
         currState->startWalk();
 }

 Fault
 Walker::WalkerState::startWalk()
 {
     Fault fault = NoFault;
     assert(!started);
     started = true;
     setupWalk(req->getVaddr());
     if (timing) {
         nextState = state;
         state = Waiting;
         timingFault = NoFault;
         sendPackets();
     } else {
         do {
             walker->port.sendAtomic(read);
             PacketPtr write = NULL;
             fault = stepWalk(write);
             assert(fault == NoFault || read == NULL);
             state = nextState;
             nextState = Ready;
             if (write)
                 walker->port.sendAtomic(write);
         } while (read);
         state = Ready;
         nextState = Waiting;
     }
     return fault;
 }

 Fault
 Walker::WalkerState::startFunctional(Addr &addr, unsigned &logBytes)
 {
     Fault fault = NoFault;
     assert(!started);
     started = true;
     setupWalk(addr);

     do {
         walker->port.sendFunctional(read);
         // On a functional access (page table lookup), writes should
         // not happen so this pointer is ignored after stepWalk
         PacketPtr write = NULL;
         fault = stepWalk(write);
         assert(fault == NoFault || read == NULL);
         state = nextState;
         nextState = Ready;
     } while (read);
     logBytes = entry.logBytes;
     addr = entry.paddr;

     return fault;
 }

 Fault
 Walker::WalkerState::stepWalk(PacketPtr &write)
 {
     assert(state != Ready && state != Waiting);
     Fault fault = NoFault;
     write = NULL;
     PageTableEntry pte;
     if (dataSize == 8)
         pte = read->getLE<uint64_t>();
     else
         pte = read->getLE<uint32_t>();
     VAddr vaddr = entry.vaddr;
     bool uncacheable = pte.pcd;
     Addr nextRead = 0;
     bool doWrite = false;
     bool doTLBInsert = false;
     bool doEndWalk = false;
     bool badNX = pte.nx && mode == BaseTLB::Execute && enableNX;
     switch(state) {
       case LongPML4:
         DPRINTF(PageTableWalker,
                 "Got long mode PML4 entry %#016x.\n", (uint64_t)pte);
         nextRead = ((uint64_t)pte & (mask(40) << 12)) + vaddr.longl3 * dataSize;
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = pte.w;
         entry.user = pte.u;
         if (badNX || !pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         entry.noExec = pte.nx;
         nextState = LongPDP;
         break;
       case LongPDP:
         DPRINTF(PageTableWalker,
                 "Got long mode PDP entry %#016x.\n", (uint64_t)pte);
         nextRead = ((uint64_t)pte & (mask(40) << 12)) + vaddr.longl2 * dataSize;
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = entry.writable && pte.w;
         entry.user = entry.user && pte.u;
         if (badNX || !pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         nextState = LongPD;
         break;
       case LongPD:
         DPRINTF(PageTableWalker,
                 "Got long mode PD entry %#016x.\n", (uint64_t)pte);
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = entry.writable && pte.w;
         entry.user = entry.user && pte.u;
         if (badNX || !pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         if (!pte.ps) {
             // 4 KB page
             entry.logBytes = 12;
             nextRead =
                 ((uint64_t)pte & (mask(40) << 12)) + vaddr.longl1 * dataSize;
             nextState = LongPTE;
             break;
         } else {
             // 2 MB page
             entry.logBytes = 21;
             entry.paddr = (uint64_t)pte & (mask(31) << 21);
             entry.uncacheable = uncacheable;
             entry.global = pte.g;
             entry.patBit = bits(pte, 12);
             entry.vaddr = entry.vaddr & ~((2 * (1 << 20)) - 1);
             doTLBInsert = true;
             doEndWalk = true;
             break;
         }
       case LongPTE:
         DPRINTF(PageTableWalker,
                 "Got long mode PTE entry %#016x.\n", (uint64_t)pte);
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = entry.writable && pte.w;
         entry.user = entry.user && pte.u;
         if (badNX || !pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         entry.paddr = (uint64_t)pte & (mask(40) << 12);
         entry.uncacheable = uncacheable;
         entry.global = pte.g;
         entry.patBit = bits(pte, 12);
         entry.vaddr = entry.vaddr & ~((4 * (1 << 10)) - 1);
         doTLBInsert = true;
         doEndWalk = true;
         break;
       case PAEPDP:
         DPRINTF(PageTableWalker,
                 "Got legacy mode PAE PDP entry %#08x.\n", (uint32_t)pte);
         nextRead = ((uint64_t)pte & (mask(40) << 12)) + vaddr.pael2 * dataSize;
         if (!pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         nextState = PAEPD;
         break;
       case PAEPD:
         DPRINTF(PageTableWalker,
                 "Got legacy mode PAE PD entry %#08x.\n", (uint32_t)pte);
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = pte.w;
         entry.user = pte.u;
         if (badNX || !pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         if (!pte.ps) {
             // 4 KB page
             entry.logBytes = 12;
             nextRead = ((uint64_t)pte & (mask(40) << 12)) + vaddr.pael1 * dataSize;
             nextState = PAEPTE;
             break;
         } else {
             // 2 MB page
             entry.logBytes = 21;
             entry.paddr = (uint64_t)pte & (mask(31) << 21);
             entry.uncacheable = uncacheable;
             entry.global = pte.g;
             entry.patBit = bits(pte, 12);
             entry.vaddr = entry.vaddr & ~((2 * (1 << 20)) - 1);
             doTLBInsert = true;
             doEndWalk = true;
             break;
         }
       case PAEPTE:
         DPRINTF(PageTableWalker,
                 "Got legacy mode PAE PTE entry %#08x.\n", (uint32_t)pte);
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = entry.writable && pte.w;
         entry.user = entry.user && pte.u;
         if (badNX || !pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         entry.paddr = (uint64_t)pte & (mask(40) << 12);
         entry.uncacheable = uncacheable;
         entry.global = pte.g;
         entry.patBit = bits(pte, 7);
         entry.vaddr = entry.vaddr & ~((4 * (1 << 10)) - 1);
         doTLBInsert = true;
         doEndWalk = true;
         break;
       case PSEPD:
         DPRINTF(PageTableWalker,
                 "Got legacy mode PSE PD entry %#08x.\n", (uint32_t)pte);
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = pte.w;
         entry.user = pte.u;
         if (!pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         if (!pte.ps) {
             // 4 KB page
             entry.logBytes = 12;
             nextRead =
                 ((uint64_t)pte & (mask(20) << 12)) + vaddr.norml2 * dataSize;
             nextState = PTE;
             break;
         } else {
             // 4 MB page
             entry.logBytes = 21;
             entry.paddr = bits(pte, 20, 13) << 32 | bits(pte, 31, 22) << 22;
             entry.uncacheable = uncacheable;
             entry.global = pte.g;
             entry.patBit = bits(pte, 12);
             entry.vaddr = entry.vaddr & ~((4 * (1 << 20)) - 1);
             doTLBInsert = true;
             doEndWalk = true;
             break;
         }
       case PD:
         DPRINTF(PageTableWalker,
                 "Got legacy mode PD entry %#08x.\n", (uint32_t)pte);
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = pte.w;
         entry.user = pte.u;
         if (!pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         // 4 KB page
         entry.logBytes = 12;
         nextRead = ((uint64_t)pte & (mask(20) << 12)) + vaddr.norml2 * dataSize;
         nextState = PTE;
         break;
       case PTE:
         DPRINTF(PageTableWalker,
                 "Got legacy mode PTE entry %#08x.\n", (uint32_t)pte);
         doWrite = !pte.a;
         pte.a = 1;
         entry.writable = pte.w;
         entry.user = pte.u;
         if (!pte.p) {
             doEndWalk = true;
             fault = pageFault(pte.p);
             break;
         }
         entry.paddr = (uint64_t)pte & (mask(20) << 12);
         entry.uncacheable = uncacheable;
         entry.global = pte.g;
         entry.patBit = bits(pte, 7);
         entry.vaddr = entry.vaddr & ~((4 * (1 << 10)) - 1);
         doTLBInsert = true;
         doEndWalk = true;
         break;
       default:
         panic("Unknown page table walker state %d!\n");
     }
     if (doEndWalk) {
         if (doTLBInsert)
             if (!functional)
                 walker->tlb->insert(entry.vaddr, entry);
         endWalk();
     } else {
         PacketPtr oldRead = read;
         //If we didn't return, we're setting up another read.
         Request::Flags flags = oldRead->req->getFlags();
         flags.set(Request::UNCACHEABLE, uncacheable);
         RequestPtr request = std::make_shared<Request>(
             nextRead, oldRead->getSize(), flags, walker->masterId);
         read = new Packet(request, MemCmd::ReadReq);
         read->allocate();
         // If we need to write, adjust the read packet to write the modified
         // value back to memory.
         if (doWrite) {
             write = oldRead;
             write->setLE<uint64_t>(pte);
             write->cmd = MemCmd::WriteReq;
         } else {
             write = NULL;
             delete oldRead;
         }
     }
     return fault;
 }

 void
 Walker::WalkerState::endWalk()
 {
     nextState = Ready;
     delete read;
     read = NULL;
 }

 void
 Walker::WalkerState::setupWalk(Addr vaddr)
 {
     VAddr addr = vaddr;
     CR3 cr3 = tc->readMiscRegNoEffect(MISCREG_CR3);
     // Check if we're in long mode or not
     Efer efer = tc->readMiscRegNoEffect(MISCREG_EFER);
     dataSize = 8;
     Addr topAddr;
     if (efer.lma) {
         // Do long mode.
         state = LongPML4;
         topAddr = (cr3.longPdtb << 12) + addr.longl4 * dataSize;
         enableNX = efer.nxe;
     } else {
         // We're in some flavor of legacy mode.
         CR4 cr4 = tc->readMiscRegNoEffect(MISCREG_CR4);
         if (cr4.pae) {
             // Do legacy PAE.
             state = PAEPDP;
             topAddr = (cr3.paePdtb << 5) + addr.pael3 * dataSize;
             enableNX = efer.nxe;
         } else {
             dataSize = 4;
             topAddr = (cr3.pdtb << 12) + addr.norml2 * dataSize;
             if (cr4.pse) {
                 // Do legacy PSE.
                 state = PSEPD;
             } else {
                 // Do legacy non PSE.
                 state = PD;
             }
             enableNX = false;
         }
     }

     nextState = Ready;
     entry.vaddr = vaddr;

     Request::Flags flags = Request::PHYSICAL;
     if (cr3.pcd)
         flags.set(Request::UNCACHEABLE);

     RequestPtr request = std::make_shared<Request>(
         topAddr, dataSize, flags, walker->masterId);

     read = new Packet(request, MemCmd::ReadReq);
     read->allocate();
 }

 bool
 Walker::WalkerState::recvPacket(PacketPtr pkt)
 {
     assert(pkt->isResponse());
     assert(inflight);
     assert(state == Waiting);
     inflight--;
     if (squashed) {
         // if were were squashed, return true once inflight is zero and
         // this WalkerState will be freed there.
         return (inflight == 0);
     }
     if (pkt->isRead()) {
         // should not have a pending read it we also had one outstanding
         assert(!read);

         // @todo someone should pay for this
         pkt->headerDelay = pkt->payloadDelay = 0;

         state = nextState;
         nextState = Ready;
         PacketPtr write = NULL;
         read = pkt;
         timingFault = stepWalk(write);
         state = Waiting;
         assert(timingFault == NoFault || read == NULL);
         if (write) {
             writes.push_back(write);
         }
         sendPackets();
     } else {
         sendPackets();
     }
     if (inflight == 0 && read == NULL && writes.size() == 0) {
         state = Ready;
         nextState = Waiting;
         if (timingFault == NoFault) {
             /*
              * Finish the translation. Now that we know the right entry is
              * in the TLB, this should work with no memory accesses.
              * There could be new faults unrelated to the table walk like
              * permissions violations, so we'll need the return value as
              * well.
              */
             bool delayedResponse;
             Fault fault = walker->tlb->translate(req, tc, NULL, mode,
                                                  delayedResponse, true);
             assert(!delayedResponse);
             // Let the CPU continue.
             translation->finish(fault, req, tc, mode);
         } else {
             // There was a fault during the walk. Let the CPU know.
             translation->finish(timingFault, req, tc, mode);
         }
         return true;
     }

     return false;
 }

 void
 Walker::WalkerState::sendPackets()
 {
     //If we're already waiting for the port to become available, just return.
     if (retrying)
         return;

     //Reads always have priority
     if (read) {
         PacketPtr pkt = read;
         read = NULL;
         inflight++;
         if (!walker->sendTiming(this, pkt)) {
             retrying = true;
             read = pkt;
             inflight--;
             return;
         }
     }
     //Send off as many of the writes as we can.
     while (writes.size()) {
         PacketPtr write = writes.back();
         writes.pop_back();
         inflight++;
         if (!walker->sendTiming(this, write)) {
             retrying = true;
             writes.push_back(write);
             inflight--;
             return;
         }
     }
 }

 unsigned
 Walker::WalkerState::numInflight() const
 {
     return inflight;
 }

 bool
 Walker::WalkerState::isRetrying()
 {
     return retrying;
 }

 bool
 Walker::WalkerState::isTiming()
 {
     return timing;
 }

 bool
 Walker::WalkerState::wasStarted()
 {
     return started;
 }

 void
 Walker::WalkerState::squash()
 {
     squashed = true;
 }

 void
 Walker::WalkerState::retry()
 {
     retrying = false;
     sendPackets();
 }

 Fault
 Walker::WalkerState::pageFault(bool present)
 {
     DPRINTF(PageTableWalker, "Raising page fault.\n");
     HandyM5Reg m5reg = tc->readMiscRegNoEffect(MISCREG_M5_REG);
     if (mode == BaseTLB::Execute && !enableNX)
         mode = BaseTLB::Read;
     return std::make_shared<PageFault>(entry.vaddr, present, mode,
                                        m5reg.cpl == 3, false);
 }

 /* end namespace X86ISA */ }

 X86ISA::Walker *
 X86PagetableWalkerParams::create()
 {
     return new X86ISA::Walker(this);
 }
	/*
	* Copyright (c) 2012 ARM Limited
	* All rights reserved.
	*
	* The license below extends only to copyright in the software and shall
	* not be construed as granting a license to any other intellectual
	* property including but not limited to intellectual property relating
	* to a hardware implementation of the functionality of the software
	* licensed hereunder. You may use the software subject to the license
	* terms below provided that you ensure that this notice is replicated
	* unmodified and in its entirety in all distributions of the software,
	* modified or unmodified, in source code or in binary form.
	*
	* Copyright (c) 2007 The Hewlett-Packard Development Company
	* All rights reserved.
	*
	* The license below extends only to copyright in the software and shall
	* not be construed as granting a license to any other intellectual
	* property including but not limited to intellectual property relating
	* to a hardware implementation of the functionality of the software
	* licensed hereunder. You may use the software subject to the license
	* terms below provided that you ensure that this notice is replicated
	* unmodified and in its entirety in all distributions of the software,
	* modified or unmodified, in source code or in binary form.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions are
	* met: redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer;
	* redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution;
	* neither the name of the copyright holders nor the names of its
	* contributors may be used to endorse or promote products derived from
	* this software without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*
	* Authors: Gabe Black
	*/

	#include "arch/x86/pagetable_walker.hh"

	#include <memory>

	#include "arch/x86/faults.hh"
	#include "arch/x86/pagetable.hh"
	#include "arch/x86/tlb.hh"
	#include "arch/x86/vtophys.hh"
	#include "base/bitfield.hh"
	#include "base/trie.hh"
	#include "cpu/base.hh"
	#include "cpu/thread_context.hh"
	#include "debug/PageTableWalker.hh"
	#include "mem/packet_access.hh"
	#include "mem/request.hh"

	namespace X86ISA {

	Fault
	Walker::start(ThreadContext * _tc, BaseTLB::Translation *_translation,
	const RequestPtr &_req, BaseTLB::Mode _mode)
	{
	// TODO: in timing mode, instead of blocking when there are other
	// outstanding requests, see if this request can be coalesced with
	// another one (i.e. either coalesce or start walk)
	WalkerState * newState = new WalkerState(this, _translation, _req);
	newState->initState(_tc, _mode, sys->isTimingMode());
	if (currStates.size()) {
	assert(newState->isTiming());
	DPRINTF(PageTableWalker, "Walks in progress: %d\n", currStates.size());
	currStates.push_back(newState);
	return NoFault;
	} else {
	currStates.push_back(newState);
	Fault fault = newState->startWalk();
	if (!newState->isTiming()) {
	currStates.pop_front();
	delete newState;
	}
	return fault;
	}
	}

	Fault
	Walker::startFunctional(ThreadContext * _tc, Addr &addr, unsigned &logBytes,
	BaseTLB::Mode _mode)
	{
	funcState.initState(_tc, _mode);
	return funcState.startFunctional(addr, logBytes);
	}

	bool
	Walker::WalkerPort::recvTimingResp(PacketPtr pkt)
	{
	return walker->recvTimingResp(pkt);
	}

	bool
	Walker::recvTimingResp(PacketPtr pkt)
	{
	WalkerSenderState * senderState =
	dynamic_cast<WalkerSenderState *>(pkt->popSenderState());
	WalkerState * senderWalk = senderState->senderWalk;
	bool walkComplete = senderWalk->recvPacket(pkt);
	delete senderState;
	if (walkComplete) {
	std::list<WalkerState *>::iterator iter;
	for (iter = currStates.begin(); iter != currStates.end(); iter++) {
	WalkerState * walkerState = *(iter);
	if (walkerState == senderWalk) {
	iter = currStates.erase(iter);
	break;
	}
	}
	delete senderWalk;
	// Since we block requests when another is outstanding, we
	// need to check if there is a waiting request to be serviced
	if (currStates.size() && !startWalkWrapperEvent.scheduled())
	// delay sending any new requests until we are finished
	// with the responses
	schedule(startWalkWrapperEvent, clockEdge());
	}
	return true;
	}

	void
	Walker::WalkerPort::recvReqRetry()
	{
	walker->recvReqRetry();
	}

	void
	Walker::recvReqRetry()
	{
	std::list<WalkerState *>::iterator iter;
	for (iter = currStates.begin(); iter != currStates.end(); iter++) {
	WalkerState * walkerState = *(iter);
	if (walkerState->isRetrying()) {
	walkerState->retry();
	}
	}
	}

	bool Walker::sendTiming(WalkerState* sendingState, PacketPtr pkt)
	{
	WalkerSenderState* walker_state = new WalkerSenderState(sendingState);
	pkt->pushSenderState(walker_state);
	if (port.sendTimingReq(pkt)) {
	return true;
	} else {
	// undo the adding of the sender state and delete it, as we
	// will do it again the next time we attempt to send it
	pkt->popSenderState();
	delete walker_state;
	return false;
	}

	}

	Port &
	Walker::getPort(const std::string &if_name, PortID idx)
	{
	if (if_name == "port")
	return port;
	else
	return ClockedObject::getPort(if_name, idx);
	}

	void
	Walker::WalkerState::initState(ThreadContext * _tc,
	BaseTLB::Mode _mode, bool _isTiming)
	{
	assert(state == Ready);
	started = false;
	tc = _tc;
	mode = _mode;
	timing = _isTiming;
	}

	void
	Walker::startWalkWrapper()
	{
	unsigned num_squashed = 0;
	WalkerState *currState = currStates.front();
	while ((num_squashed < numSquashable) && currState &&
	currState->translation->squashed()) {
	currStates.pop_front();
	num_squashed++;

	DPRINTF(PageTableWalker, "Squashing table walk for address %#x\n",
	currState->req->getVaddr());

	// finish the translation which will delete the translation object
	currState->translation->finish(
	std::make_shared<UnimpFault>("Squashed Inst"),
	currState->req, currState->tc, currState->mode);

	// delete the current request if there are no inflight packets.
	// if there is something in flight, delete when the packets are
	// received and inflight is zero.
	if (currState->numInflight() == 0) {
	delete currState;
	} else {
	currState->squash();
	}

	// check the next translation request, if it exists
	if (currStates.size())
	currState = currStates.front();
	else
	currState = NULL;
	}
	if (currState && !currState->wasStarted())
	currState->startWalk();
	}

	Fault
	Walker::WalkerState::startWalk()
	{
	Fault fault = NoFault;
	assert(!started);
	started = true;
	setupWalk(req->getVaddr());
	if (timing) {
	nextState = state;
	state = Waiting;
	timingFault = NoFault;
	sendPackets();
	} else {
	do {
	walker->port.sendAtomic(read);
	PacketPtr write = NULL;
	fault = stepWalk(write);
	assert(fault == NoFault \|\| read == NULL);
	state = nextState;
	nextState = Ready;
	if (write)
	walker->port.sendAtomic(write);
	} while (read);
	state = Ready;
	nextState = Waiting;
	}
	return fault;
	}

	Fault
	Walker::WalkerState::startFunctional(Addr &addr, unsigned &logBytes)
	{
	Fault fault = NoFault;
	assert(!started);
	started = true;
	setupWalk(addr);

	do {
	walker->port.sendFunctional(read);
	// On a functional access (page table lookup), writes should
	// not happen so this pointer is ignored after stepWalk
	PacketPtr write = NULL;
	fault = stepWalk(write);
	assert(fault == NoFault \|\| read == NULL);
	state = nextState;
	nextState = Ready;
	} while (read);
	logBytes = entry.logBytes;
	addr = entry.paddr;

	return fault;
	}

	Fault
	Walker::WalkerState::stepWalk(PacketPtr &write)
	{
	assert(state != Ready && state != Waiting);
	Fault fault = NoFault;
	write = NULL;
	PageTableEntry pte;
	if (dataSize == 8)
	pte = read->getLE<uint64_t>();
	else
	pte = read->getLE<uint32_t>();
	VAddr vaddr = entry.vaddr;
	bool uncacheable = pte.pcd;
	Addr nextRead = 0;
	bool doWrite = false;
	bool doTLBInsert = false;
	bool doEndWalk = false;
	bool badNX = pte.nx && mode == BaseTLB::Execute && enableNX;
	switch(state) {
	case LongPML4:
	DPRINTF(PageTableWalker,
	"Got long mode PML4 entry %#016x.\n", (uint64_t)pte);
	nextRead = ((uint64_t)pte & (mask(40) << 12)) + vaddr.longl3 * dataSize;
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = pte.w;
	entry.user = pte.u;
	if (badNX \|\| !pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	entry.noExec = pte.nx;
	nextState = LongPDP;
	break;
	case LongPDP:
	DPRINTF(PageTableWalker,
	"Got long mode PDP entry %#016x.\n", (uint64_t)pte);
	nextRead = ((uint64_t)pte & (mask(40) << 12)) + vaddr.longl2 * dataSize;
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = entry.writable && pte.w;
	entry.user = entry.user && pte.u;
	if (badNX \|\| !pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	nextState = LongPD;
	break;
	case LongPD:
	DPRINTF(PageTableWalker,
	"Got long mode PD entry %#016x.\n", (uint64_t)pte);
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = entry.writable && pte.w;
	entry.user = entry.user && pte.u;
	if (badNX \|\| !pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	if (!pte.ps) {
	// 4 KB page
	entry.logBytes = 12;
	nextRead =
	((uint64_t)pte & (mask(40) << 12)) + vaddr.longl1 * dataSize;
	nextState = LongPTE;
	break;
	} else {
	// 2 MB page
	entry.logBytes = 21;
	entry.paddr = (uint64_t)pte & (mask(31) << 21);
	entry.uncacheable = uncacheable;
	entry.global = pte.g;
	entry.patBit = bits(pte, 12);
	entry.vaddr = entry.vaddr & ~((2 * (1 << 20)) - 1);
	doTLBInsert = true;
	doEndWalk = true;
	break;
	}
	case LongPTE:
	DPRINTF(PageTableWalker,
	"Got long mode PTE entry %#016x.\n", (uint64_t)pte);
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = entry.writable && pte.w;
	entry.user = entry.user && pte.u;
	if (badNX \|\| !pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	entry.paddr = (uint64_t)pte & (mask(40) << 12);
	entry.uncacheable = uncacheable;
	entry.global = pte.g;
	entry.patBit = bits(pte, 12);
	entry.vaddr = entry.vaddr & ~((4 * (1 << 10)) - 1);
	doTLBInsert = true;
	doEndWalk = true;
	break;
	case PAEPDP:
	DPRINTF(PageTableWalker,
	"Got legacy mode PAE PDP entry %#08x.\n", (uint32_t)pte);
	nextRead = ((uint64_t)pte & (mask(40) << 12)) + vaddr.pael2 * dataSize;
	if (!pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	nextState = PAEPD;
	break;
	case PAEPD:
	DPRINTF(PageTableWalker,
	"Got legacy mode PAE PD entry %#08x.\n", (uint32_t)pte);
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = pte.w;
	entry.user = pte.u;
	if (badNX \|\| !pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	if (!pte.ps) {
	// 4 KB page
	entry.logBytes = 12;
	nextRead = ((uint64_t)pte & (mask(40) << 12)) + vaddr.pael1 * dataSize;
	nextState = PAEPTE;
	break;
	} else {
	// 2 MB page
	entry.logBytes = 21;
	entry.paddr = (uint64_t)pte & (mask(31) << 21);
	entry.uncacheable = uncacheable;
	entry.global = pte.g;
	entry.patBit = bits(pte, 12);
	entry.vaddr = entry.vaddr & ~((2 * (1 << 20)) - 1);
	doTLBInsert = true;
	doEndWalk = true;
	break;
	}
	case PAEPTE:
	DPRINTF(PageTableWalker,
	"Got legacy mode PAE PTE entry %#08x.\n", (uint32_t)pte);
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = entry.writable && pte.w;
	entry.user = entry.user && pte.u;
	if (badNX \|\| !pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	entry.paddr = (uint64_t)pte & (mask(40) << 12);
	entry.uncacheable = uncacheable;
	entry.global = pte.g;
	entry.patBit = bits(pte, 7);
	entry.vaddr = entry.vaddr & ~((4 * (1 << 10)) - 1);
	doTLBInsert = true;
	doEndWalk = true;
	break;
	case PSEPD:
	DPRINTF(PageTableWalker,
	"Got legacy mode PSE PD entry %#08x.\n", (uint32_t)pte);
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = pte.w;
	entry.user = pte.u;
	if (!pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	if (!pte.ps) {
	// 4 KB page
	entry.logBytes = 12;
	nextRead =
	((uint64_t)pte & (mask(20) << 12)) + vaddr.norml2 * dataSize;
	nextState = PTE;
	break;
	} else {
	// 4 MB page
	entry.logBytes = 21;
	entry.paddr = bits(pte, 20, 13) << 32 \| bits(pte, 31, 22) << 22;
	entry.uncacheable = uncacheable;
	entry.global = pte.g;
	entry.patBit = bits(pte, 12);
	entry.vaddr = entry.vaddr & ~((4 * (1 << 20)) - 1);
	doTLBInsert = true;
	doEndWalk = true;
	break;
	}
	case PD:
	DPRINTF(PageTableWalker,
	"Got legacy mode PD entry %#08x.\n", (uint32_t)pte);
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = pte.w;
	entry.user = pte.u;
	if (!pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	// 4 KB page
	entry.logBytes = 12;
	nextRead = ((uint64_t)pte & (mask(20) << 12)) + vaddr.norml2 * dataSize;
	nextState = PTE;
	break;
	case PTE:
	DPRINTF(PageTableWalker,
	"Got legacy mode PTE entry %#08x.\n", (uint32_t)pte);
	doWrite = !pte.a;
	pte.a = 1;
	entry.writable = pte.w;
	entry.user = pte.u;
	if (!pte.p) {
	doEndWalk = true;
	fault = pageFault(pte.p);
	break;
	}
	entry.paddr = (uint64_t)pte & (mask(20) << 12);
	entry.uncacheable = uncacheable;
	entry.global = pte.g;
	entry.patBit = bits(pte, 7);
	entry.vaddr = entry.vaddr & ~((4 * (1 << 10)) - 1);
	doTLBInsert = true;
	doEndWalk = true;
	break;
	default:
	panic("Unknown page table walker state %d!\n");
	}
	if (doEndWalk) {
	if (doTLBInsert)
	if (!functional)
	walker->tlb->insert(entry.vaddr, entry);
	endWalk();
	} else {
	PacketPtr oldRead = read;
	//If we didn't return, we're setting up another read.
	Request::Flags flags = oldRead->req->getFlags();
	flags.set(Request::UNCACHEABLE, uncacheable);
	RequestPtr request = std::make_shared<Request>(
	nextRead, oldRead->getSize(), flags, walker->masterId);
	read = new Packet(request, MemCmd::ReadReq);
	read->allocate();
	// If we need to write, adjust the read packet to write the modified
	// value back to memory.
	if (doWrite) {
	write = oldRead;
	write->setLE<uint64_t>(pte);
	write->cmd = MemCmd::WriteReq;
	} else {
	write = NULL;
	delete oldRead;
	}
	}
	return fault;
	}

	void
	Walker::WalkerState::endWalk()
	{
	nextState = Ready;
	delete read;
	read = NULL;
	}

	void
	Walker::WalkerState::setupWalk(Addr vaddr)
	{
	VAddr addr = vaddr;
	CR3 cr3 = tc->readMiscRegNoEffect(MISCREG_CR3);
	// Check if we're in long mode or not
	Efer efer = tc->readMiscRegNoEffect(MISCREG_EFER);
	dataSize = 8;
	Addr topAddr;
	if (efer.lma) {
	// Do long mode.
	state = LongPML4;
	topAddr = (cr3.longPdtb << 12) + addr.longl4 * dataSize;
	enableNX = efer.nxe;
	} else {
	// We're in some flavor of legacy mode.
	CR4 cr4 = tc->readMiscRegNoEffect(MISCREG_CR4);
	if (cr4.pae) {
	// Do legacy PAE.
	state = PAEPDP;
	topAddr = (cr3.paePdtb << 5) + addr.pael3 * dataSize;
	enableNX = efer.nxe;
	} else {
	dataSize = 4;
	topAddr = (cr3.pdtb << 12) + addr.norml2 * dataSize;
	if (cr4.pse) {
	// Do legacy PSE.
	state = PSEPD;
	} else {
	// Do legacy non PSE.
	state = PD;
	}
	enableNX = false;
	}
	}

	nextState = Ready;
	entry.vaddr = vaddr;

	Request::Flags flags = Request::PHYSICAL;
	if (cr3.pcd)
	flags.set(Request::UNCACHEABLE);

	RequestPtr request = std::make_shared<Request>(
	topAddr, dataSize, flags, walker->masterId);

	read = new Packet(request, MemCmd::ReadReq);
	read->allocate();
	}

	bool
	Walker::WalkerState::recvPacket(PacketPtr pkt)
	{
	assert(pkt->isResponse());
	assert(inflight);
	assert(state == Waiting);
	inflight--;
	if (squashed) {
	// if were were squashed, return true once inflight is zero and
	// this WalkerState will be freed there.
	return (inflight == 0);
	}
	if (pkt->isRead()) {
	// should not have a pending read it we also had one outstanding
	assert(!read);

	// @todo someone should pay for this
	pkt->headerDelay = pkt->payloadDelay = 0;

	state = nextState;
	nextState = Ready;
	PacketPtr write = NULL;
	read = pkt;
	timingFault = stepWalk(write);
	state = Waiting;
	assert(timingFault == NoFault \|\| read == NULL);
	if (write) {
	writes.push_back(write);
	}
	sendPackets();
	} else {
	sendPackets();
	}
	if (inflight == 0 && read == NULL && writes.size() == 0) {
	state = Ready;
	nextState = Waiting;
	if (timingFault == NoFault) {
	/*
	* Finish the translation. Now that we know the right entry is
	* in the TLB, this should work with no memory accesses.
	* There could be new faults unrelated to the table walk like
	* permissions violations, so we'll need the return value as
	* well.
	*/
	bool delayedResponse;
	Fault fault = walker->tlb->translate(req, tc, NULL, mode,
	delayedResponse, true);
	assert(!delayedResponse);
	// Let the CPU continue.
	translation->finish(fault, req, tc, mode);
	} else {
	// There was a fault during the walk. Let the CPU know.
	translation->finish(timingFault, req, tc, mode);
	}
	return true;
	}

	return false;
	}

	void
	Walker::WalkerState::sendPackets()
	{
	//If we're already waiting for the port to become available, just return.
	if (retrying)
	return;

	//Reads always have priority
	if (read) {
	PacketPtr pkt = read;
	read = NULL;
	inflight++;
	if (!walker->sendTiming(this, pkt)) {
	retrying = true;
	read = pkt;
	inflight--;
	return;
	}
	}
	//Send off as many of the writes as we can.
	while (writes.size()) {
	PacketPtr write = writes.back();
	writes.pop_back();
	inflight++;
	if (!walker->sendTiming(this, write)) {
	retrying = true;
	writes.push_back(write);
	inflight--;
	return;
	}
	}
	}

	unsigned
	Walker::WalkerState::numInflight() const
	{
	return inflight;
	}

	bool
	Walker::WalkerState::isRetrying()
	{
	return retrying;
	}

	bool
	Walker::WalkerState::isTiming()
	{
	return timing;
	}

	bool
	Walker::WalkerState::wasStarted()
	{
	return started;
	}

	void
	Walker::WalkerState::squash()
	{
	squashed = true;
	}

	void
	Walker::WalkerState::retry()
	{
	retrying = false;
	sendPackets();
	}

	Fault
	Walker::WalkerState::pageFault(bool present)
	{
	DPRINTF(PageTableWalker, "Raising page fault.\n");
	HandyM5Reg m5reg = tc->readMiscRegNoEffect(MISCREG_M5_REG);
	if (mode == BaseTLB::Execute && !enableNX)
	mode = BaseTLB::Read;
	return std::make_shared<PageFault>(entry.vaddr, present, mode,
	m5reg.cpl == 3, false);
	}

	/* end namespace X86ISA */ }

	X86ISA::Walker *
	X86PagetableWalkerParams::create()
	{
	return new X86ISA::Walker(this);
	}