Optimize PageTableManager and associated VMM.

    - Changed overall page table behavior to no longer use C bits
      in page table entries.  Instead, individual blocks mark
      pages as dirty based on stores during page faults.  Initially
      all writable pages are marked read-only until the first store
      to it.  At that time the block gets an exception and changes
      the permission on the page table entry to writable and marks
      its own SPTE to dirty.

    - Greatly reduced the number of tlbie's and page table accesses.
      Accomplished this by:
          * Skipping many of the page table manipulations, such as
	    LRU updates, when the PTE is invalid.
	  * Converting most of the previously general-case of
	    "Modifying a PTE" to specific cases such as "Resetting
	    the Reference Bit" and "Modifying the SW field".

    - Fixed the LRU-flush algorithm so that it is O(n) instead of
      O(n^2), where n = size of page table.

Change-Id: I2520fa88970fd7f656e6348bf6b34d5db82fd3db
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/892
Tested-by: Jenkins Server
Reviewed-by: Douglas R. Gilbert <dgilbert@us.ibm.com>
Reviewed-by: Daniel M. Crowell <dcrowell@us.ibm.com>
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

8 files changed, 46 insertions, 23 deletions

diff --git a/src/include/kernel/basesegment.H b/src/include/kernel/basesegment.H
index 51e99b0bf..293b24f1c 100644
--- a/src/include/kernel/basesegment.H
+++ b/src/include/kernel/basesegment.H
@@ -64,7 +64,8 @@ class BaseSegment : public Segment
          *
          * Calls block chain to deal with page fault.
          */
-        virtual bool handlePageFault(task_t* i_task, uint64_t i_addr);
+        virtual bool handlePageFault(task_t* i_task, uint64_t i_addr,
+                                     bool i_store);
 
         /**
          * @brief Implementation of the pure-virtual function from Segment.
@@ -108,8 +109,8 @@ class BaseSegment : public Segment
 
         /**
          * @brief Sets the page permissions for a given virtual address and size.
-         * @param i_va[in] - virtual address of the page(s) to set permissions  
-         * @param i_size[in] - range of memory that needs permissions updated... 
+         * @param i_va[in] - virtual address of the page(s) to set permissions
+         * @param i_size[in] - range of memory that needs permissions updated...
          *           if i_size equals 0 then we only need to update an
          *           individual page.
          * @param i_access_type[in] - type of permission to set
@@ -148,7 +149,7 @@ class BaseSegment : public Segment
         /**
          * @brief Sets the page permissions for a given virtual address and size.
          * @param i_va[in] - virtual address of the page(s) to set permissions
-         * @param i_size[in] - range of memory that needs permissions updated... 
+         * @param i_size[in] - range of memory that needs permissions updated...
          *          if i_size equals 0 then we only need to update an individual
          *          page.
          * @param i_access_type[in] - type of permission to set
diff --git a/src/include/kernel/block.H b/src/include/kernel/block.H
index 48e27b803..5d80ea7c6 100644
--- a/src/include/kernel/block.H
+++ b/src/include/kernel/block.H
@@ -104,6 +104,7 @@ class Block
          *
          * @param[in] i_task - Task causing the page fault.
          * @param[in] i_addr - Effective address accessed to cause fault.
+         * @param[in] i_store - The fault was due to a store.
          *
          * @return true - Page fault was successfully handled.
          *
@@ -114,14 +115,14 @@ class Block
          * If the address is not within this block, the block will attempt to
          * make calls down the block-chain if it exists.
          */
-        bool handlePageFault(task_t* i_task, uint64_t i_addr);
+        bool handlePageFault(task_t* i_task, uint64_t i_addr, bool i_store);
 
         /**
          * @brief Locate the physical address of the given virtual address
          *
          * @param[in] i_vaddr virtual address
          *
-         * @return the physical address bound to the virtual address, 
+         * @return the physical address bound to the virtual address,
          *         -EFAULT if not found @see errno.h
          */
         uint64_t findPhysicalAddress(uint64_t i_vaddr) const;
@@ -202,7 +203,7 @@ class Block
          *          and a size of memory needing updated permissions
          * @param i_va[in] - virtual address of the beginning of the
          *           pages that need updating.
-         * @param i_size[in] - range of memory that needs updating 
+         * @param i_size[in] - range of memory that needs updating
          *          if i_size equals 0 then we only need to update an
          *          individual page.
          * @param i_access_type[in] - type of permission to set using
diff --git a/src/include/kernel/devicesegment.H b/src/include/kernel/devicesegment.H
index dcaf78af8..c300eedde 100644
--- a/src/include/kernel/devicesegment.H
+++ b/src/include/kernel/devicesegment.H
@@ -56,12 +56,13 @@ class DeviceSegment : public Segment
 
         /**
          * @brief Handle a page fault for a device address access
-         * @param i_task[in] - Task pointer to the task requiring the page
-         * @param i_addr[in] - 64-bit address needed to be paged
+         * @param[in] i_task - Task pointer to the task requiring the page
+         * @param[in] i_addr - 64-bit address needed to be paged
+         * @param[in] i_store - Fault was due to a store.
          * @return bool - true: Page added to page table
          *               false: Not a valid address to be paged
          */
-        bool handlePageFault(task_t* i_task, uint64_t i_addr);
+        bool handlePageFault(task_t* i_task, uint64_t i_addr, bool i_store);
 
 
         /**
diff --git a/src/include/kernel/ptmgr.H b/src/include/kernel/ptmgr.H
index 918e4211f..b570e0d14 100644
--- a/src/include/kernel/ptmgr.H
+++ b/src/include/kernel/ptmgr.H
@@ -59,12 +59,12 @@ class PageTableManager
     {
         PT_SIZE = (1 << 18), /**< Size of Page Table in bytes */
         PTE_SIZE = /**< Size of 1 Page Table Entry in bytes */
-            2*sizeof(uint64_t), 
+            2*sizeof(uint64_t),
         PTEG_SIZE = 8, /**< Number of PTEs in a single PTE Group */
         PTEG_COUNT =  /**< Number of PTEGs in the Page Table */
             (PT_SIZE / PTE_SIZE) / PTEG_SIZE,
         INVALID_PN = /**< Error value for a Page Number return */
-            0xFFFFFFFFFFFFFFFF, 
+            0xFFFFFFFFFFFFFFFF,
     };
 
     /**
@@ -72,7 +72,7 @@ class PageTableManager
      */
     struct UsageStats_t {
 	union {
-	    struct { 
+	    struct {
 		uint64_t C:1;    /**< Page has been modified  */
 		uint64_t R:1;    /**< Page has been referenced  */
 		uint64_t LRU:2;  /**< Current value of LRU  */
@@ -299,6 +299,11 @@ class PageTableManager
     /**
      * @brief  Write a PTE to memory and update caches appropriately
      *
+     * @note This function should only be used to change a PTE from valid to
+     *       invalid or from invalid to valid, unless modifying the permissions
+     *       on an existing PTE (without changing addresses).  Use in two
+     *       stages otherwise.
+     *
      * @param[in] i_pte  Local pointer to PTE data
      * @param[in] i_dest  Real Address inside page table to write i_pte data into
      * @param[in] i_valid  true=set Valid bit, false=clear Valid bit
@@ -371,11 +376,21 @@ class PageTableManager
     uint64_t getStatus( PageTableEntry* i_pte );
 
     /**
-     * @brief Update the LRU statistics for other PTEs in the same PTEG as the target
+     * @brief Update the LRU statistics for other PTEs in the same PTEG as the
+     *        target
+     *
+     * @param[in] i_newPTE  Real address of PTE that is being added to the
+     *                      Page Table
+     */
+    void updateLRUGroup( const PageTableEntry* i_newPTE );
+
+    /**
+     * @brief Update the LRU statistics for a specific PTE.
      *
-     * @param[in] i_newPTE  Real address of PTE that is being added to the Page Table
+     * @param[in] i_newPTE  Real address of PTE to update.
      */
-    void updateLRU( const PageTableEntry* i_newPTE );
+    void updateLRUEntry( PageTableEntry* i_newPTE );
+
 
     /**
      * @brief Invalidate TLB for a PTE
@@ -449,7 +464,7 @@ class PageTableManager
      *
      * @param[out] o_pte  PTE to modify
      */
-    static void setupDefaultPTE( PageTableEntry* o_pte );
+    static void setupDefaultPTE( PageTableEntry* o_pte ) ALWAYS_INLINE;
 
     /**
      * @brief  Push C/R/LRU bits to the VMM
diff --git a/src/include/kernel/segment.H b/src/include/kernel/segment.H
index 798539309..63aa13480 100644
--- a/src/include/kernel/segment.H
+++ b/src/include/kernel/segment.H
@@ -53,6 +53,7 @@ class Segment
          *
          * @param[in] i_task - Task causing the page fault.
          * @param[in] i_addr - Effective address accessed to cause fault.
+         * @param[in] i_store - The fault was due to a store.
          *
          * @return true - Page fault was successfully handled.
          *
@@ -60,7 +61,8 @@ class Segment
          * that the VMM will perform appropriate action, such as killing the
          * task.
          */
-        virtual bool handlePageFault(task_t* i_task, uint64_t i_addr) = 0;
+        virtual bool handlePageFault(task_t* i_task, uint64_t i_addr,
+                                     bool i_store) = 0;
 
         /**
          * @brief Get the base address of this segment.
diff --git a/src/include/kernel/segmentmgr.H b/src/include/kernel/segmentmgr.H
index 85ecf3269..ecefbc0dd 100644
--- a/src/include/kernel/segmentmgr.H
+++ b/src/include/kernel/segmentmgr.H
@@ -84,6 +84,7 @@ class SegmentManager
          *
          * @param[in] i_task - Task causing the page fault.
          * @param[in] i_addr - Effective address accessed to cause fault.
+         * @param[in] i_store - The page fault was due to a store.
          *
          * @return true - Page fault was successfully handled.
          *
@@ -91,7 +92,8 @@ class SegmentManager
          * that the VMM will perform appropriate action, such as killing the
          * task.
          */
-        static bool handlePageFault(task_t* i_task, uint64_t i_addr);
+        static bool handlePageFault(task_t* i_task, uint64_t i_addr,
+                                    bool i_store);
 
         /**
          * @brief Adds a segment to the container.
@@ -150,7 +152,7 @@ class SegmentManager
 
     private:
         /** See handlePageFault. */
-        bool _handlePageFault(task_t* i_task, uint64_t i_addr);
+        bool _handlePageFault(task_t* i_task, uint64_t i_addr, bool i_store);
         /** See addSegment. */
         void _addSegment(Segment* i_segment, size_t i_segId);
         /** See getSegment. */
diff --git a/src/include/kernel/stacksegment.H b/src/include/kernel/stacksegment.H
index 460a61b49..0c80d9fae 100644
--- a/src/include/kernel/stacksegment.H
+++ b/src/include/kernel/stacksegment.H
@@ -85,7 +85,7 @@ class StackSegment : public Segment
          *
          * Calls block chain to deal with page fault.
          */
-        bool handlePageFault(task_t* i_task, uint64_t i_addr);
+        bool handlePageFault(task_t* i_task, uint64_t i_addr, bool i_store);
 
         /**
          * @brief Locate the physical address of the given virtual address
diff --git a/src/include/kernel/vmmmgr.H b/src/include/kernel/vmmmgr.H
index 46f283e18..7a1fd6f7b 100644
--- a/src/include/kernel/vmmmgr.H
+++ b/src/include/kernel/vmmmgr.H
@@ -77,13 +77,14 @@ class VmmManager
          *
          * @param[in] t - Task causing the page fault.
          * @param[in] effAddr - Effective address accessed to cause fault.
+         * @param[in] store - The PTE miss was due to a store.
          *
          * @return true - PTE miss was successfully handled.
          *
          * If the PTE miss is not successfully handled, the exception
          * handler should collect debug information and kill the task.
          */
-        static bool pteMiss(task_t* t, uint64_t effAddr);
+        static bool pteMiss(task_t* t, uint64_t effAddr, bool store);
 
         /**
          * @brief Map a device into the device segment
@@ -177,7 +178,7 @@ class VmmManager
         void initPTEs();
         void initSDR1();
 
-        bool _pteMiss(task_t*, uint64_t);
+        bool _pteMiss(task_t*, uint64_t, bool);
 
         /** See findPhysicalAddress */
         uint64_t _findPhysicalAddress(uint64_t i_vaddr);