Adding a basic interface and implementation to the Segment/Block

path to update the LRU statistics when the PageTableManager code
clears the reference bit.  This is not meant to be a complete
implementation (different Task is open for that).

This is Task 3400.

Change-Id: If67efd16ead6f68a74f5f5a698013c1b852864d9
Reviewed-on: http://gfw160.austin.ibm.com:8080/gerrit/231
Tested-by: Jenkins Server
Reviewed-by: Daniel M. Crowell <dcrowell@us.ibm.com>

6 files changed, 131 insertions, 17 deletions

diff --git a/src/include/kernel/basesegment.H b/src/include/kernel/basesegment.H
index a661ae5ce..72869d535 100644
--- a/src/include/kernel/basesegment.H
+++ b/src/include/kernel/basesegment.H
@@ -63,7 +63,17 @@ class BaseSegment : public Segment
          *
          * Calls block chain to deal with page fault.
          */
-        bool handlePageFault(task_t* i_task, uint64_t i_addr);
+        virtual bool handlePageFault(task_t* i_task, uint64_t i_addr);
+
+        /**
+         * @brief Implementation of the pure-virtual function from Segment.
+         *        Update LRU statistics on the block that owns the address         *
+         *
+         * @param[in] i_vaddr - Virtual Address of page
+         * @param[in] i_stats - Usage statistics
+         */
+        virtual void updateRefCount( uint64_t i_vaddr,
+				     PageTableManager::UsageStats_t i_stats );
 
         /**
          * @brief Allocates a block of virtual memory of the given size
diff --git a/src/include/kernel/block.H b/src/include/kernel/block.H
index 94daf0b3a..2421f97f9 100644
--- a/src/include/kernel/block.H
+++ b/src/include/kernel/block.H
@@ -30,6 +30,8 @@
 #include <kernel/task.H>
 #include <kernel/vmmmgr.H>
 #include <kernel/blockmsghdlr.H>
+#include <kernel/msghandler.H>
+#include <kernel/ptmgr.H>
 
 class ShadowPTE;
 class Segment;
@@ -140,6 +142,20 @@ class Block
          */
         uint64_t findPhysicalAddress(uint64_t i_vaddr) const;
 
+        /**
+         * @brief Responsible for updating usage counts within the block [chain].
+         *
+         * @param[in] i_vaddr - Abbreviated Virtual Address of page
+         *                      (bottom 23 bits are zero)
+         * @param[in] i_stats - Usage statistics
+         *
+         * If the address is not within this block or a matching page cannot be
+         *  found, the block will attempt to make calls down the block-chain
+         *  if it exists.
+         */
+        void updateRefCount( uint64_t i_vaddr,
+			     PageTableManager::UsageStats_t i_stats );
+
         friend class Segment;
         friend class BaseSegment;
         friend class StackSegment;
diff --git a/src/include/kernel/ptmgr.H b/src/include/kernel/ptmgr.H
index bab4ba3b4..c7505bc1f 100644
--- a/src/include/kernel/ptmgr.H
+++ b/src/include/kernel/ptmgr.H
@@ -41,14 +41,14 @@ class PageTableManager
      */
     enum
     {
-        PTE_UNKNOWN          = 0x0000000000000000,  /**< Entry wasn't found */
-        PTE_PRESENT          = 0x0000000000000001,  /**< Entry is present in table */
-        PTE_VALID            = 0x0000000000000002,  /**< Entry is valid */
-        PTE_READ_ONLY        = 0x0000000000000004,  /**< Read-Only */
-        PTE_EXECUTE          = 0x0000000000000008,  /**< Execute permission */
-        PTE_CACHE_INHIBITED  = 0x0000000000000010,  /**< Cache-Inhibited Access */
-        PTE_MODIFIED         = 0x0000000000000020,  /**< Page has been modified */
-        PTE_ACCESSED         = 0x0000000000000040,  /**< Page has been accessed */
+        PTE_UNKNOWN         = 0x0000000000000000, /**< Entry wasn't found */
+        PTE_PRESENT         = 0x0000000000000001, /**< Entry is present in table */
+        PTE_VALID           = 0x0000000000000002, /**< Entry is valid */
+        PTE_READ_ONLY       = 0x0000000000000004, /**< Read-Only */
+        PTE_EXECUTE         = 0x0000000000000008, /**< Execute permission */
+        PTE_CACHE_INHIBITED = 0x0000000000000010, /**< Cache-Inhibited Access */
+        PTE_MODIFIED        = 0x0000000000000020, /**< Page has been modified */
+        PTE_ACCESSED        = 0x0000000000000040, /**< Page has been accessed */
     };
 
     /**
@@ -56,11 +56,30 @@ class PageTableManager
      */
     enum
     {
-        PT_SIZE = (1 << 18),  /**< Size of Page Table in bytes */
-        PTE_SIZE = 2*sizeof(uint64_t),   /**< Size of a single Page Table Entry in bytes */
-        PTEG_SIZE = 8,  /**< Number of PTEs in a single PTE Group */
-        PTEG_COUNT = (PT_SIZE / PTE_SIZE) / PTEG_SIZE,  /**< Number of PTEGs in the Page Table */
-        INVALID_PN = 0xFFFFFFFFFFFFFFFF,  /**< Invalid value for a Page Number return */
+        PT_SIZE = (1 << 18), /**< Size of Page Table in bytes */
+        PTE_SIZE = /**< Size of 1 Page Table Entry in bytes */
+            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, 
+    };
+
+    /**
+     * LRU Statistics
+     */
+    struct UsageStats_t {
+	union {
+	    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  */
+		uint64_t rsv:60; /**< Reserved space  */
+	    };
+	    uint64_t fullword;  /**< Full Dword0 */
+	};
+	UsageStats_t():fullword(0){};
     };
 
     /**
@@ -175,7 +194,8 @@ class PageTableManager
             struct {  /**< Dword0 Attributes */
                 uint64_t B:2;    /**< 0:1   Segment Size  */
                 uint64_t AVA:55; /**< 2:56  Abbreviated Virtual Address = VA w/o bottom 23 bits  */
-                uint64_t SW:2;   /**< 57:58 =SW[0:1] - Reserved  */
+                uint64_t SW:1;   /**< 57 =SW[] - Reserved  */
+                uint64_t R2:1;   /**< 58 =SW[1] - Shadow R bit  */
                 uint64_t LRU:2;  /**< 59:60 =SW[2:3] - Used for LRU algorithm  */
                 uint64_t L:1;    /**< 61    Virtual page size  */
                 uint64_t H:1;    /**< 62    Hash function identifier  */
@@ -413,13 +433,27 @@ class PageTableManager
     VmmManager::ACCESS_TYPES getAccessType( const PageTableEntry* i_pte );
 
     /**
+     * @brief  Calculate the original Virtual Address from a PTE
+     *
+     * @param[in] i_pte  PTE to examine, must be pointer to real entry in table
+     *
+     * @return uint64_t  page-aligned virtual address
+     */
+    uint64_t getVirtAddrFromPTE( const PageTableEntry* i_pte );
+
+    /**
      * @brief  Fill in default values for the PTE
      *
      * @param[out] o_pte  PTE to modify
      */
     static void setupDefaultPTE( PageTableEntry* o_pte );
 
-
+    /**
+     * @brief  Push C/R/LRU bits to the VMM
+     *
+     * @param[in] i_pte  PTE to examine, must be pointer to real entry in table
+     */
+    void pushUsageStats( PageTableEntry* i_pte );
 
     // Allow testcase to see inside
     friend class ptmgrtest;
diff --git a/src/include/kernel/segment.H b/src/include/kernel/segment.H
index 05c5c0fdc..d7a4a7547 100644
--- a/src/include/kernel/segment.H
+++ b/src/include/kernel/segment.H
@@ -28,6 +28,7 @@
 
 #include <kernel/task.H>
 #include <errno.h>
+#include <kernel/ptmgr.H>
 
 /** @class Segment
  *  @brief Virtual segment class to handle virtual memory management within
@@ -75,6 +76,19 @@ class Segment
          */
          virtual uint64_t findPhysicalAddress(uint64_t i_vaddr) const { return -EFAULT; };
 
+        /**
+         * @brief Update LRU statistics on the block that owns the address
+         *
+         * @param[in] i_vaddr - Virtual Address of page
+         * @param[in] i_stats - Usage statistics
+         */
+        virtual void updateRefCount( uint64_t i_vaddr,
+				     PageTableManager::UsageStats_t i_stats )
+	{
+	    //default to a NOOP
+	    return;
+	};
+
     protected:
             /** The base address of the segment. */
         const uint64_t iv_baseAddress;
diff --git a/src/include/kernel/segmentmgr.H b/src/include/kernel/segmentmgr.H
index 0d8caec33..563497047 100644
--- a/src/include/kernel/segmentmgr.H
+++ b/src/include/kernel/segmentmgr.H
@@ -29,6 +29,7 @@
 
 #include <kernel/task.H>
 #include <builtins.h>
+#include <kernel/ptmgr.H>
 
 // Forward declaration.
 class Segment;
@@ -107,6 +108,15 @@ class SegmentManager
          */
         static uint64_t findPhysicalAddress(uint64_t i_vaddr);
 
+        /**
+         * @brief Update LRU statistics on the block that owns the page
+         *
+         * @param[in] i_vaddr - Virtual Address of page
+         * @param[in] i_stats - Usage statistics
+         */
+        static void updateRefCount( uint64_t i_vaddr,
+				    PageTableManager::UsageStats_t i_stats );
+
 
     private:
         /** See handlePageFault. */
@@ -115,6 +125,9 @@ class SegmentManager
         void _addSegment(Segment* i_segment, size_t i_segId);
         /** See initSLB. */
         void _initSLB();
+            /** See updateRefCount. */
+	void _updateRefCount( uint64_t i_vaddr,
+			      PageTableManager::UsageStats_t i_stats );
 
         /** See findPhysicalAddress */
         uint64_t _findPhysicalAddress(uint64_t i_vaddr) const;
diff --git a/src/include/kernel/spte.H b/src/include/kernel/spte.H
index 1a284d6e7..abd81dff3 100644
--- a/src/include/kernel/spte.H
+++ b/src/include/kernel/spte.H
@@ -66,8 +66,11 @@ class ShadowPTE
                     /** Allocate from a zero'd page. */
                 uint32_t allocate_from_zero:1;
 
+                    /** LRU value - lower means it was accessed more recently. */
+                uint32_t last_access:3;
+
                     /** Reserved for future use. */
-                uint32_t reserved:6;
+                uint32_t reserved:3;
             } PACKED;
         };
 
@@ -106,10 +109,34 @@ class ShadowPTE
         bool isDirty() const { return dirty; };
             /** Set dirty bit. */
         void setDirty(bool i_dirty) { dirty = i_dirty; };
+
             /** Get allocate-from-zero bit. */
         bool isAllocateFromZero() const { return allocate_from_zero; };
             /** Set allocate-from-zero bit. */
         void setAllocateFromZero(bool i_zero) { allocate_from_zero = i_zero; };
+
+            /** Get last_acces bits. */
+        uint8_t getLRU() const { return last_access; };
+            /** Increment the LRU bits. */
+        void incLRU() {
+	    if( last_access < 0b111 )
+	    {
+		last_access++;
+	    }
+	};
+            /** Decrement the LRU bits. */
+        void decLRU() {
+	    if( last_access > 0 )
+	    {
+		last_access--;
+	    }
+	};
+            /** Zero out the LRU bits. */
+        void zeroLRU() {
+	    last_access = 0;
+	};
+
+
 };
 
 #endif