Reverse mapping page frame data structures to page table entries

• US 6,112,286 A
• Filed: 09/19/1997
• Issued: 08/29/2000
• Est. Priority Date: 09/19/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Stevens, Luis, Subramanya, Bhanuprakash, Ganapathy, Narayanan, Schimmel, Curt F.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Verbrugge, Kevin
• Application Number:
  US08/933,998
• Time in Patent Office: 1,075 Days
• Field of Search: 711/147, 711/203, 711/206, 711/207, 711/208, 711/209, 364/254.3
• US Class Current: 711/208
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables

Abstract

A system, method and computer program product for reverse mapping a page of memory to one or more data structure references, such as page table entries, that reference the page of memory. A number m of fields of a page frame data structure are reserved for storing reverse mapping data for a page of memory. Each reserved field can store a reverse map entry for pointing to a data structure reference, such as a page table entry, that references the page of memory that is represented by the page frame data structure. Where a number n of references to the page of memory is greater than the number m of reserved fields, a reverse map table is generated for storing additional reverse map entries. When a reverse map table is generated, one of the reverse map entries in one of the reserved fields of the page frame data structure is moved to the reverse map table. A pointer to the reverse map table is placed in the now-vacant reserved field. Indexes in the page table entries are used to identify and remove the reverse map entries when a page table is deallocated. Reverse map tables can be generated as needed and can be dynamically sized to accommodate any number of reverse map entries.

Claims

1. A method for reverse mapping page frame data structures that represent pages of memory, comprising the steps of:

(1) reserving a number m of fields in a first page frame data structure for storing reverse mapping information, the first page frame data structure representing a first page of memory;

(2) generating a number n of reverse map entries for pointing to data structure references that reference the first page of memory, wherein n≧

2;

(3) if the number n is less than or equal to the number m, placing all of the reverse map entries in the reserved fields of the first page frame data structure,

(4) if the number n is greater than the number m,

(i) placing m-1 reverse map entries in m-1 corresponding reserved fields,

(ii) placing the remaining n-(m-1) reverse map entries in a reverse map table, and

(iii) placing a pointer to the reverse map table in an unused reserved field of the first page frame data structure; and

(5) storing an index in each of the data structure references, wherein the index identifies one of the n reverse map entries that is pointing to the data structure reference.

2. The method according to claim 1, further comprising the steps of:

(6) detecting that data that is stored in the first page of memory is being moved to a second page of memory,

(7) using the reverse maps to identify the data structure references that reference the first page of memory, and

(8) updating the data structure references so that they reference the second page of physical memory.

3. The method according to claim 1, wherein step (2) comprises the steps of:

(a) generating a first reverse map entry that points to a page table entry that references the first page of memory.

4. The method of claim 3, further comprising the steps of:

(6) using the first reverse map entry to identify the page table entry in a distributed, shared memory multi-processor system, wherein the first page of memory is located in a first processing node and data that is stored in the first page of memory is migrated to a second page of memory that is located in a second processing node;

(7) updating the page table entry so that it references the second page of memory instead of the first page of memory;

(8) placing a second reverse map entry in a second page frame data structure that represents the second page of memory, wherein the second reverse map entry points to the first page table entry; and

(9) removing the first reverse map entry from the first page frame data structure.

5. The method of claim 3, further comprising the steps of:

(6) when a portion of a file that is mapped to the first page of memory is truncated, using the first reverse map entry to identify the first page table entry;

(7) removing the page table entry that is associated with the first page table address; and

(8) removing the first reverse map entry from the first page frame data structure.

6. The method according to claim 3, further comprising the steps of:

(6) when a copy of the page table entry is placed in a translational look-aside buffer (TLB), placing data that identifies the TLB in a page frame data structure that represents a page frame that stores the page table; and

(7) using the data that identifies the TLB to flush the TLB when a page table entry in the page table is changed.

7. The method of claim 1, further comprising the steps of:

(6) when a page of data is mapped to more than one virtual address by page table entries in different page tables, identifying a page frame data structure that is referenced by the more than one virtual addresses;

(7) using reverse map entries in the page frame data structure to identify the page table entries that map the data to the more than one virtual addresses; and

(8) deallocating all but one of the page table entries that map the data to the more than one virtual addresses.

8. The method according to claim 1, further comprising the steps of:

(6) when a data structure reference is discarded, using the index stored in the data structure reference to identify the one of the n reverse map entries pointing at the data structure reference; and

(7) removing the identified one of the n reverse map entries.

9. The method of claim 1, further comprising the steps of:

(6) detecting activity that affects the first page of memory; and

(7) using the n reverse map entries to identify the data structure references.

10. The method according to claim 9, wherein step (6) comprises:

(a) detecting at least one of the following types of activities that affects the first page of memory;

(i) a move operation,

(ii) a delete operation,

(iii) a virtual cache coherency operation,

(iv) a fork operation,

(v) a page-migration operation,

(vi) a file truncation operation,

(vii) a page aging operation, and

(viii) a page out operation.

11. The method according to claim 9, wherein step (6) comprises:

(a) detecting a termination of an import operation that affects the first page of memory.

12. A method for reverse mapping page frame data structures that represent pages of memory, comprising the steps of:

(1) reserving a number m of fields of a page frame data structure that represents a page frame for storing reverse mapping information;

(2) generating a plurality of reverse map entries that point to corresponding data structures that reference the page frame;

(3) associating each of the plurality of reverse map entries with the page frame data structure, comprising the steps of;

(a) generating a dynamically sizeable reverse map table;

(b) placing at least one of the plurality of reverse map entries in the reverse map table; and

(c) placing a pointer to the reverse map table in one of the reserved fields of the page frame data structure; and

(4) storing an index that identifies one of the plurality of reverse map entries in the corresponding data structure.

13. The method according to claim 12, wherein step (3) comprises the steps of:

(a) placing the reverse map entry in one of the reserved fields of the page frame data structure.

14. A computer program product comprising a computer useable medium having computer program logic stored therein, said computer program logic for enabling a computer to reverse map a page frame to data structure references that reference the page frame, wherein said computer program logic comprises:

a procedure that enables the computer to employ a number m of fields of a first page frame data structure, that represents a first page of memory, for storing reverse mapping information;

a procedure that enables the computer to generate a number n of reverse map entries for pointing to data structure references that reference the first page of memory, wherein n≧

2;

a procedure that enables the computer to place the reverse map entries in the reserved fields of the first page frame data structure if the number n is less than or equal to the number m;

a procedure that enables the computer to place m-1 reverse map entries in m-1 of the reserved fields if the number n is greater than the number m;

a procedure that enables the computer to place n-(m-1) reverse map entries in a reverse map table if the number n is greater than the number m;

a procedure that enables the computer to place a pointer to the reverse map table in an unused one of the m fields of the first page frame data structure if the number n is greater than the number m;

a procedure that enables the computer to store an index in each of the data structure references, wherein the index identifies one of the n reverse map entries that is pointing to the data structure reference.

15. The computer program product of claim 14, wherein said computer program logic further comprises:

a procedure that enables the computer to use a first reverse map entry to identify a first page table entry that references the first page of memory;

a procedure that enables the computer to update the first page table entry with a reference to a second page of memory if data that is mapped to the first page of memory is moved to the second page of memory;

a procedure that enables the computer to generate a second reverse map entry in a second page frame data structure that represents a second page of memory, if data that is mapped to the first page of memory is moved to the second page of memory; and

a procedure that enables the computer to remove the first reverse map entry from the first page frame data structure.

16. The computer program product of claim 14, further comprising:

a procedure that enables the computer to place data that identifies a translational look-aside buffer (TLB) in a page frame data structure that represents a page frame that stores the page table, when a copy of a page table entry from the page table is placed in the (TLB); and

a procedure that enables the computer to use the data that identifies the TLB to flush the TLB when a page table entry in the page table is changed.

17. A system for reverse mapping a page frame to a data structure reference that references the page frame, comprising:

a procedure that employs a number m of fields of a first page frame data structure, that represents a first page frame, for storing reverse mapping information;

a procedure that generates a number n of reverse map entries for pointing to data structure references that reference the first page frame, wherein n≧

2;

a procedure that places the reverse map entries in the reserved fields of the first page frame data structure if the number n is less than or equal to the number m;

a procedure that places m-1 reverse map entries in m-1 in the reserved fields of the first page frame data structure if the number n is greater than the number m;

a procedure the places n-(m-1) reverse map entries in a reverse map table if the number n is greater than the number m;

a procedure that places a pointer to the reverse map table in a remaining field of the first page frame data structure if the number n is greater than the number m; and

a procedure that stores an index in each of the data structure references, wherein the index identifies one of the n reverse map entries that is pointing to the data structure reference.

18. The system according to claim 17, wherein said procedure that employs a number m of fields of a first page frame data structure, comprises a procedure that employs two fields of the first page frame data structure for storing reverse mapping information.

19. The system according to claim 17, further comprising:

a procedure that uses a first reverse map entry to identify a first page table entry that references the first page of memory;

a procedure that updates the first page table entry with a reference to a second page of memory if data that is mapped to the first page of memory is moved to the second page of memory; and

a procedure that generates a second reverse map entry in a second page frame data structure that represents a second page of memory, if data that is mapped to the first page of memory is moved to the second page of memory.

20. The system of claim 17, further comprising:

a procedure that reverse maps a page frame to a page table entry that references the page frame;

a procedure that places data that identifies a translational look-aside buffer (TLB) in a page frame data structure that represents a page frame that stores the page table, when a copy of a page table entry from the page table is placed in the (TLB); and

a procedure that uses the data that identifies the TLB to flush the TLB when a page table entry in the page table is changed.