Browse Prior Art Database

Hashed Page Table for Virtual Address Translation

IP.com Disclosure Number: IPCOM000115906D
Original Publication Date: 1995-Jul-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 106K

Publishing Venue

IBM

Related People

Chang, AS: AUTHOR [+2]

Abstract

Disclosed is a page table, used translate a virtual address to a real address. The table occupies an amount of storage proportional to the amount of installed memory and supports the use of aliases (multiple virtual addresses that translate to the same real address). This particular implementation of a hashed page table is used in conjunction with a virtual address that is fifty-two bits long. The virtual address is generated from a thirty-two bit Effective Address (EA) by appending the low order twenty-eight bits of the effective address to a segment identifier selected by the high order four bits of the effective address.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Hashed Page Table for Virtual Address Translation

      Disclosed is a page table, used translate a virtual address to
a real address.  The table occupies an amount of storage proportional
to the amount of installed memory and supports the use of aliases
(multiple virtual addresses that translate to the same real address).
This particular implementation of a hashed page table is used in
conjunction with a virtual address that is fifty-two bits long.  The
virtual address is generated from a thirty-two bit Effective Address
(EA) by appending the low order twenty-eight bits of the effective
address to a segment identifier selected by the high order four bits
of the effective address.

      The Hashed Page Table is a data structure used by hardware or
software to translate a virtual address to a real address.  The Hash
Table (HTAB) contains a maximum number of page table entry groups
(HTEGs) that is proportional to the amount of installed memory.  Each
HTEG contains space for eight Page Table Entries (PTEs).  Fewer HTEGs
may be allocated if software sets the HTABMASK appropriately.  For a
system with N pages of real memory installed, the proposed number of
HTEGs that should be allocated is N/2.

      HTEG contains eight PTEs.  HTEGs are the addressable element in
the HTAB.  The two hash algorithms and table search algorithm are
described later.  Each page table entry contains fields to specify
the virtual address, the real address, page protection, reference
bit, and change bit (Fig. 2).

      The Storage Description Register (SDR) contains the origin
pointer (HTABORG) to the HTAB and an eight bit hash mask (HTABMASK).
HTABORG is used in the computation of the pointer to the target HTEG.
That computation is described below.  The HTABMASK is provided to
allow the allocation of an HTAB smaller than required to support 4
gigabytes of real storage when there is less than the maximum storage
installed.

      Hash Table Search - When a translation of a virtual address
must be performed, the virtual address is used in combination with
the HATBORG and HTABMASK to compute the address of the HTEG that
would contain the translation of the virtual address if the
translation is contained in the table.  The search algorithm is
described below.

Hash Computation - The address of the primary HTEG is computed from
the virtual address, the SID, and the HTABORG described by the
following equations:
  op1 := HTABORG || 17*b'0'
  o...