Translation of multiple virtual pages upon a TLB miss

Claim 2

In a digital computer, a method for use in translating an incoming memory address in a first address space into a corresponding memory address in a second address space comprising the steps of: translating, in response to a miss in a translation lookaside buffer (TLB), a plurality of successive contiguous page addresses in said first address space into a corresponding plurality of page addresses in said second address space, said plurality of successive contiguous page addresses in said first address space containing a page address of said incoming memory address; and storing, in the TLB, said plurality of page addresses in said second address space.

Claim 3

The method in claim 1 wherein said storing step comprises the steps of: creating a TLB entry containing a first one of said plurality of page addressees in said first address space and each of said plurality of page addresses in said second address space; and inserting said TLB entry into the TLB.

Claim 4

The method in claim 2 wherein said first address space is virtual address space containing a plurality of virtual page addresses and said second address space is real address space containing a plurality real page addresses.

Claim 5

The method of claim 3 further comprising the steps of: searching the TLB, in response to an incoming virtual page address contained in an incoming virtual memory address, for a specific TLB entry that contains a plurality of real page addresses for a block of corresponding contiguous virtual page addresses containing said incoming virtual page address; generating, in response to said searching step, a TLB miss in the event said specific TLB entry does not exist in the TLB; and determining, in response to said searching step and the existence of said specific TLB entry, whether one of said plurality of real page addresses stored therein and corresponding to said incoming virtual page address is valid; and, if valid, reading said one of said plurality of real page addresses from said TLB entry as a corresponding translated real page address, otherwise generating a TLB miss.

Claim 6

The method in claim 4 further comprising the step of forming a real memory address by concatenating said one of said plurality of real page addresses with a value of a byte index field from said incoming virtual memory address, wherein said real memory address contains said one of said plurality of real page address followed by a byte index field value.

Claim 7

The method in claim 3 wherein said creating step further comprises the step of incorporating within said TLB entry a separate bit for each of said plurality of real page addresses, wherein said separate bit indicates whether a corresponding one of said plurality of real page addresses is valid or not.

Claim 8

The method in claim 6 wherein said TLB entry further comprises a block index field for identifying a block address for the first one of said plurality of virtual page addresses within said page table.

Claim 9

The method in claim 7 wherein said TLB entry further comprises segment table origin and segment index fields for respectively identifying an origin of a segment table and a particular segment table entry therein.

Claim 10

The method in claim 8 wherein said inserting step comprises the step of hashing the TLB entry into the TLB through values of the segment and block index fields contained in the TLB entry.

Claim 11

The method in claim 6 wherein a first one of said plurality of virtual page addresses lies on a partition of a pre-defined block of virtual page addresses in a page table.

Claim 12

The method in claim 10 wherein said pre-defined block comprises four successive contiguous virtual page addresses.

Claim 13

The method in claim 10 wherein said translating step further comprises the steps of: first translating the first one of said plurality of virtual page addresses in said pre-defined block through appropriate entries in both a segment table and the page table to yield a first page table entry in said page table and, from said first page table entry, obtaining a corresponding one of said plurality of real page addresses; and second translating a second one and each successive remaining one of said plurality of virtual page addresses in said pre-defined block into corresponding ones of said plurality of real page addresses by accessing, from the page table, successive contiguous entries following said first page table entry and obtaining from each such successive entry a remaining corresponding one of said plurality of real page addresses.

Claim 14

The method in claim 12 wherein said first translating step comprises the steps of: first accessing the segment table, in response to a segment table origin address and a value of a segment index present in a virtual memory address, to provide therefrom a segment table entry; reading a page table origin address from said segment table entry; second accessing the page table, in response to said page table origin address and a value of a page index present in the virtual memory address, in order to provide therefrom said first page table entry; and reading a first real page address from said first page table entry.

Claim 15

In a digital computer, a method for use in translating an incoming virtual memory address into a corresponding real memory address comprising the steps of: accessing a translation lookaside buffer (TLB) comprising: searching the TLB, in response to an incoming virtual page address contained in said incoming virtual memory address, for a TLB entry that contains real page addresses for a block of corresponding contiguous virtual page addresses containing said incoming virtual page address; generating, in response to said searching step, a TLB miss in the event said TLB entry does not exist in the TLB; and determining, in response to said searching step and the existence of said TLB entry, whether one of said real page addresses stored therein and corresponding to said incoming virtual page address is valid; and if valid, reading said one real page address from said TLB entry as a corresponding translated real page address, otherwise generating a TLB miss; and updating the TLB, in response to said TLB miss, comprising: translating a plurality of successive contiguous virtual page addresses into a corresponding plurality of real page addresses, said plurality of successive contiguous virtual page addresses containing said incoming virtual page address and forming the block of said corresponding contiguous virtual page addresses; creating a new TLB entry for said block, said new TLB entry containing a first one of said plurality of successive contiguous virtual page addresses and each of said plurality of real page addresses; and inserting said new TLB entry into the TLB.

Claim 16

In a digital computer, a method for use in translating an incoming virtual memory address into a corresponding real memory address comprising the steps of: accessing a translation lookaside buffer (TLB) comprising: searching the TLB, in response to an incoming virtual page address contained in said incoming virtual memory address, for a TLB entry that contains real page addresses for a block of corresponding contiguous virtual page addresses containing said incoming virtual page address; generating, in response to said searching step, a TLB miss in the event said TLB entry does not exist in the TLB; and determining, in response to said searching step and the existence of said TLB entry, whether one of said real page addresses stored therein and corresponding to said incoming virtual page address is valid; and if valid, reading said one real page address from said TLB entry as a corresponding translated real page address, otherwise generating a TLB miss; and updating the TLB, in response to said TLB miss, comprising: translating a plurality of successive contiguous virtual page addresses into a corresponding plurality of real page addresses, said plurality of successive contiguous virtual page addresses containing said incoming virtual page address and forming the block of said corresponding contiguous virtual page addresses; creating a new TLB entry for said block, said new TLB entry containing a first one of said plurality of successive contiguous virtual page addresses and each of said plurality of real page addresses; and inserting said new TLB entry into the TLB.

Claim 17

The method in claim 14 further comprising the step of forming a real memory address by concatenating said one real page address with a value of a byte index field from said incoming virtual memory address, wherein said real memory address contains said one real page address followed by said byte index field value.

Claim 18

The method in claim 14 wherein said creating step further comprises the step of incorporating said TLB entry a separate bit for each of said plurality of real page addresses, wherein said separate bit indicates whether a corresponding one of said plurality of real page addresses is valid or not.

Claim 19

The method of claim 16 wherein a first one of said successive contiguous virtual page addresses lies on a partition of the block of virtual page addresses in a page table.

Claim 20

The method in claim 17 wherein said translating step further comprises the steps of: first translating the first one of said plurality of successive contiguous virtual page addresses in said block through appropriate entries in both a segment table and the page table to yield a first page table entry in said page table and, from said first page table entry, obtaining a corresponding one of said plurality of real page addresses; and second translating a second one and each successive remaining one of said plurality of virtual page addresses in said block into corresponding ones of said plurality of real page addresses by accessing, from the page table, successive contiguous entries following said first page table entry and obtaining from each such successive entry a remaining corresponding one of said plurality of real page addresses.

Claim 21

The method in claim 18 wherein said first translating step comprises the steps of: first accessing the segment table, in response to a segment table origin address and a value of a segment index present in the incoming virtual memory address, to provide therefrom a segment table entry; reading a page table origin address from said segment table entry; second accessing the page table, in response to said page table origin address and a value of a page index present in the incoming virtual memory address, in order to provide therefrom said first page table entry; and reading said first real page address from said first page table entry.

Claim 22

The method in claim 16 wherein said block comprises four successive contiguous virtual page addresses.

Claim 23

In a digital computer, apparatus for use in translating an incoming memory address in a first address space into a corresponding memory address in a second address space comprising: a translation lookaside buffer (TLB); means for translating, in response to a miss in the TLB, a plurality of successive contiguous page addresses in said first address space into a corresponding plurality of page addresses in said second address space, said plurality of page addresses in said first address space containing a page address of said incoming memory address; and means for storing, in the TLB, said plurality of page addresses in said second address space.

Claim 24

In a digital computer, apparatus for use in translating an incoming memory address in a first address space into a corresponding memory address in a second address space comprising: a translation lookaside buffer (TLB); means for translating, in response to a miss in the TLB, a plurality of successive contiguous page addresses in said first address space into a corresponding plurality of page addresses in said second address space, said plurality of page addresses in said first address space containing a page address of said incoming memory address; and means for storing, in the TLB, said plurality of page addresses in said second address space.

Claim 25

The apparatus in claim 21 wherein said TLB is formed of TLB entries, each of said entries comprising a first one of said plurality of page addresses in said first address space and each of said plurality of page addresses in said second address space.

Claim 26

The method in claim 22 wherein said first address space is virtual address space containing a plurality of virtual page addresses and said second address space is real address space containing a plurality of real page addresses.

Claim 27

The apparatus in claim 23 wherein each of said TLB entries further comprises a separate bit for each of said plurality of real page addresses, wherein said separate bit indicates whether a corresponding one of said plurality of real page addresses is valid or not.

Claim 28

The apparatus in claim 24 wherein the first one of said virtual page addresses lies on a partition of a pre-defined block of virtual page addresses in a page table.

Claim 29

The apparatus in claim 25 wherein said pre-defined block comprises four successive contiguous virtual page addresses.

Claim 30

The apparatus in claim 24 wherein said each of said TLB entries further comprises a block index field for identifying a block address for the first one of said plurality of virtual page addresses within said page table.

Claim 31

The apparatus in claim 27 wherein each of said TLB entries further comprises segment table origin and segment index fields for respectively identifying an origin of a segment table and a particular segment table entry therein.