Patent US2154460A successfully refreshed from Google Patents.
Patent US5440710A successfully refreshed from Google Patents.
US5440710A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Emulation of segment bounds checking using paging with sub-page validity
Assignee: Samsung Electronics Co Ltd
•
Filing: 1994-03-08
•
Granted: 1995-08-08
•
Expires: 2014-03-08
Abstract
Abstract Segmentation is added to a reduced instruction set computer (RISC) processor which supports paging. The arithmetic-logic-unit (ALU) is extended to allow for a 3-port addition so that the segment base can be added when the virtual address is being generated. Segment bounds checking is achieved by extending the paging system to allow for valid regions that are less than the full page size. Sub-page validity can mimic segmentation because a segment can be broken up into a number of full pages and one or more partially-valid pages at the segment boundaries. A page that is not wholly valid has an "event" on the page, and a memory reference to this page will either cause a software routine to be invoked to check the segment bound, or an extension to the TLB, called a sub-page validity buffer, is used to check if the reference was to a valid portion of the page. Events may also be defined for program watchpoints and defective memory locations. Segment bounds thus do not have to be compared for each access, and the bounds do not even have to be stored on the CPU die.
Inventors
- 👤 David E. Richter
- 👤 Earl T. Cohen
- 👤 James S. Blomgren
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 23:40
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/36; G06F11/362; G06F11/3648; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0877; G06F12/0882; G06F12/10; G06F12/1027; G06F12/1036; G06F12/1045
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
301 words
A paging system adapted for emulating segment bounds checking wherein pages completely contained within segment boundaries are not checked for segment bounds violations, whereas pages containing segment boundaries are tested for segment bounds violations by a sub-page validity buffer for checking validity of a virtual address, said virtual address comprising a virtual page number and a page offset, said sub-page validity buffer comprising: a plurality of buffer entries, each of said plurality of buffer entries comprising: a virtual page number field; and a sub-page validity field for indicating a valid subset of page offsets within a page; first compare means for receiving said virtual page number and comparing said virtual page number field with said virtual page number, said first compare means indicating a selected buffer entry of said plurality of buffer entries if said virtual page number field matches said virtual page number, said selected buffer entry including a selected sub-page validity field; and second compare means for receiving said selected sub-page validity field and comparing said page offset to said valid subset of page offsets, said second compare means indicating that said page offset is invalid if said page offset is not within said valid subset of page offsets, said second compare means signaling that said page offset is valid if no buffer entry in said plurality of buffer entries is a matching buffet entry, said matching buffer entry containing said virtual page number field matching said virtual page number, wherein the absence of said matching buffer entry in said sub-page validity buffer indicates that segment bound do not need to be checked for said virtual address, wherein pages completely contained within segment boundaries are not checked for segment bounds violations, whereby validity of said page offset is checked for pages having only a subset of page offsets valid.
Claim 2
Dependent Claim
301 words
A paging system adapted for emulating segment bounds checking wherein pages completely contained within segment boundaries are not checked for segment bounds violations, whereas pages containing segment boundaries are tested for segment bounds violations by a sub-page validity buffer for checking validity of a virtual address, said virtual address comprising a virtual page number and a page offset, said sub-page validity buffer comprising: a plurality of buffer entries, each of said plurality of buffer entries comprising: a virtual page number field; and a sub-page validity field for indicating a valid subset of page offsets within a page; first compare means for receiving said virtual page number and comparing said virtual page number field with said virtual page number, said first compare means indicating a selected buffer entry of said plurality of buffer entries if said virtual page number field matches said virtual page number, said selected buffer entry including a selected sub-page validity field; and second compare means for receiving said selected sub-page validity field and comparing said page offset to said valid subset of page offsets, said second compare means indicating that said page offset is invalid if said page offset is not within said valid subset of page offsets, said second compare means signaling that said page offset is valid if no buffer entry in said plurality of buffer entries is a matching buffet entry, said matching buffer entry containing said virtual page number field matching said virtual page number, wherein the absence of said matching buffer entry in said sub-page validity buffer indicates that segment bound do not need to be checked for said virtual address, wherein pages completely contained within segment boundaries are not checked for segment bounds violations, whereby validity of said page offset is checked for pages having only a subset of page offsets valid.
Claim 3
Dependent Claim
57 words
The buffer of claim 1 wherein said sub-page validity field comprises: a first field for specifying a size of said valid subset of page offsets, said size being equal to or less than said size of a page; and a second field for specifying a page offset indicating a location of said valid subset of page offsets.
Claim 4
Dependent Claim
56 words
The buffer of claim 1 wherein said sub-page validity field comprises: a first field for specifying a first page offset indicating a location of said valid subset of page offsets; control bits for encoding control information about said first field; and said second compare means including means for interpreting said first field with said control information.
Claim 5
Dependent Claim
41 words
The buffer of claim 3 wherein said control bits indicate if page offsets within said valid subset of page offsets must be greater than or equal to, or less than or equal to said first page offset in said first field.
Claim 6
Dependent Claim
83 words
The buffer of claim 4 wherein said sub-page validity field further comprises: a second field for specifying a second page offset further indicating said location of said valid subset of page offsets; wherein said control bits further indicate if said valid subset of page offsets is between said first page offset and said second page offset, said control bits further indicating if said valid subset of page offsets is outside of a region between said first page offset and said second page offset.
Claim 7
Dependent Claim
45 words
The buffer of claim 1 wherein said sub-page validity field comprises: a valid mask field, said valid mask field comprising: a plurality of bit masks, said bit masks comprising a plurality of valid bits for indicating if a fixed-size portion of a page is valid.
Claim 8
Dependent Claim
45 words
The buffer of claim 6 said plurality of bit masks corresponds to a different size for said fixed-size portion, bit masks corresponding to a larger fixed-size portion indicating which fixed-size portion is referred to by said bit mask corresponding to a next smaller fixed-size portion.
Claim 9
Dependent Claim
237 words
A paging system for translating a virtual address to a physical address, said virtual address comprising a virtual page number and a page offset, said paging system adapted for emulating segment bounds checking, said paging system comprising: a translation-lookaside buffer (TLB), said TLB comprising a plurality of page entries, each of said plurality of page entries comprising: a virtual page number field for comparing with said virtual page number, a match indicating that the page entry with the matching virtual page number field be selected; a physical page address field, for combining with said page offsets, for outputting to a main memory; sub-page validity means for indicating a specified subset of page offsets for pages containing a segment bound, said specified subset defined by said segment bound, the absence of a sub-page validity means for a particular page entry in said plurality of page entries indicating that segment bounds do not need to be checked for said particular entry; and sub-page compare means for comparing said page offset with said specified subset of page offsets, said sub-page compare means providing a segment out-of-bounds indication if said page offset is not within said specified subset of page offsets, wherein pages completely contained within segment boundaries are not checked for segment bounds violations, whereby segment bounds checking is emulated by said paging system for a page that has only a subset of said page offsets accessible for a segment.
Claim 10
Dependent Claim
237 words
A paging system for translating a virtual address to a physical address, said virtual address comprising a virtual page number and a page offset, said paging system adapted for emulating segment bounds checking, said paging system comprising: a translation-lookaside buffer (TLB), said TLB comprising a plurality of page entries, each of said plurality of page entries comprising: a virtual page number field for comparing with said virtual page number, a match indicating that the page entry with the matching virtual page number field be selected; a physical page address field, for combining with said page offsets, for outputting to a main memory; sub-page validity means for indicating a specified subset of page offsets for pages containing a segment bound, said specified subset defined by said segment bound, the absence of a sub-page validity means for a particular page entry in said plurality of page entries indicating that segment bounds do not need to be checked for said particular entry; and sub-page compare means for comparing said page offset with said specified subset of page offsets, said sub-page compare means providing a segment out-of-bounds indication if said page offset is not within said specified subset of page offsets, wherein pages completely contained within segment boundaries are not checked for segment bounds violations, whereby segment bounds checking is emulated by said paging system for a page that has only a subset of said page offsets accessible for a segment.
Claim 11
Dependent Claim
132 words
The paging system of claim 8 wherein said sub-page compare means comprises a software compare routine that compares said page offset to said segment bound; said paging system further comprising a translation handler, for loading page entries from main memory into said TLB, said translation handler being activated when no page entry in said TLB has a virtual page number field that matches said virtual page number, said translation handler not loading a page entry into said TLB for a partially-valid page having said segment bound within said page, said translation handler activating said software compare routine when a partially valid page is accessed, whereby said TLB will be loaded only with fully valid pages, whereas partially-valid pages at said segment bound always cause a page fault, activating said software compare routine.
Claim 12
Dependent Claim
65 words
The system of claim 9 further comprising a one-time TLB entry, loaded by said translation handler if said page offset is within a valid portion of said partially-valid page, said software compare routine providing a valid indication to said translation handler if said page offset is within said specified subset of page offsets, said one-time TLB entry being valid for a single memory reference only.
Claim 13
Dependent Claim
84 words
The paging system of claim 8 wherein said sub-page validity means comprises a sub-page validity field for indicating said specified subset of page offsets, said specified subset of page offsets defined by said segment bound, said sub-page validity field having a corresponding page entry in said TLB; the sub-page compare means receiving said sub-page validity field corresponding to said selected page entry, said sub-page compare means providing said segment out-of-bounds indication if said page offset is not within said specified subset of page offsets.
Claim 14
Dependent Claim
55 words
The system of claim 11 wherein said sub-page validity field comprises: a first field for specifying a size of said specified subset of page offsets, said size being equal to or less than said page size; and a second field for specifying a page offset indicating a location of said specified subset within said page.
Claim 15
Dependent Claim
53 words
The system of claim 11 wherein said sub-page validity field comprises: a first bounds field for specifying a first page offset indicating a location of said specified subset within said page; and control bits for encoding a manner in which said sub-page compare means compares said page offset to said first bounds field.
Claim 16
Dependent Claim
32 words
The system of claim 13 wherein said control bits indicate if said specified subset of page offsets is greater than or less than said first page offset in said first bounds field.
Claim 17
Dependent Claim
80 words
The system of claim 14 wherein said sub-page validity field further comprises: a second bounds field for specifying a second page offset further indicating said location of said specified subset within said page; wherein said control bits further indicate if said specified subset of page offsets is between said first page offset and said second page offset or if said specified subset of page offsets is outside of a region between said first page offset and said second page offset.
Claim 18
Dependent Claim
52 words
The system of claim 11 wherein said sub-page validity field comprises: a valid mask field, said valid mask field comprising: a plurality of bit masks, said bit masks comprising a plurality of valid bits, each of said plurality of valid bits for indicating if a fixed-size portion of a page is valid.
Claim 19
Dependent Claim
48 words
The system of claim 16 wherein each bit mask in said plurality of bit masks corresponds to a different size for said fixed-size portions, said bit masks corresponding to a larger fixed-size portion indicating said location of said fixed-size portions that said next smaller bit mask refers to.
Claim 20
Dependent Claim
25 words
The system of claim 11 wherein said sub-page validity field is joined to a corresponding page entry in said TLB and stored in said TLB.
Claim 21
Dependent Claim
46 words
The system of claim 11 wherein said sub-page validity field is stored in a sub-page validity buffer comprising a plurality of sub-page entries, said plurality of page entries in said TLB further comprising a pointer field for selecting a sub-page entry in said sub-page validity buffer.
Claim 22
Dependent Claim
60 words
The system of claim 11 wherein said sub-page validity field is stored in a sub-page validity buffer comprising a plurality of sub-page entries, each entry in said plurality of sub-page entries comprising said sub-page validity field, and a second virtual page number field, a sub-page entry being selected if said second virtual page number field matches said virtual page number.
Claim 23
Dependent Claim
59 words
The system of claim 20 wherein said virtual address further comprises a segment number, each entry in said plurality of sub-page entries further comprising a segment number field, said sub-page entry being selected if said segment number of said virtual address matches said segment number field and if said second virtual page number field matches said virtual page number.
Claim 24
Independent Claim
259 words
A method for emulating segment bounds checking in a paging system, said method comprising: loading a translation-lookaside buffer (TLB) with entries corresponding to pages containing a fixed number of page offsets, each entry present in said TLB corresponding to a page wherein every page offset is valid for reference; translating a virtual address to a physical address using said entries in said TLB when said virtual address has a corresponding entry in said TLB, said corresponding entry having a virtual page number field matching a portion of said virtual address; generating a page fault if said virtual address has no corresponding entry in said TLB; loading a new entry into said TLB if said virtual address corresponds to a page wherein every page offset within said page is valid for reference and not checked for segment bounds violations; and executing a software handler routine if said virtual address does not correspond to a page wherein every page offset within said page is valid for reference, said software handler routine comparing an offset portion of said virtual address to a bound for a segment, said software handler routine continuing execution of a user program if said offset portion of said virtual address is within said bound for said segment, said handler routine sending a segment bounds fault to said user program if said offset portion of said virtual address is not within said bound for said segment, whereby segment bounds checking is performed by said software handler routine for pages wherein not every page offset address is valid for reference.
Claim 25
Independent Claim
259 words
A method for emulating segment bounds checking in a paging system, said method comprising: loading a translation-lookaside buffer (TLB) with entries corresponding to pages containing a fixed number of page offsets, each entry present in said TLB corresponding to a page wherein every page offset is valid for reference; translating a virtual address to a physical address using said entries in said TLB when said virtual address has a corresponding entry in said TLB, said corresponding entry having a virtual page number field matching a portion of said virtual address; generating a page fault if said virtual address has no corresponding entry in said TLB; loading a new entry into said TLB if said virtual address corresponds to a page wherein every page offset within said page is valid for reference and not checked for segment bounds violations; and executing a software handler routine if said virtual address does not correspond to a page wherein every page offset within said page is valid for reference, said software handler routine comparing an offset portion of said virtual address to a bound for a segment, said software handler routine continuing execution of a user program if said offset portion of said virtual address is within said bound for said segment, said handler routine sending a segment bounds fault to said user program if said offset portion of said virtual address is not within said bound for said segment, whereby segment bounds checking is performed by said software handler routine for pages wherein not every page offset address is valid for reference.
Claim 26
Dependent Claim
67 words
The method of claim 22 wherein said software handler routine emulates a memory access referenced by said virtual address if said offset portion of said virtual address is within said bound for said segment, said software handler routine transferring data between a main memory and a central processing unit generating said virtual address, said software handler routine continuing execution of said user program after transferring said data.
Claim 27
Dependent Claim
76 words
The method of claim 22 wherein said software handler routine loads a translation entry into a one-time TLB if said offset portion of said virtual address is within said bound for said segment, said one-time TLB being valid only for said virtual address that is being translated, said software handler routine continuing execution of said user program after loading said translation entry, said user program using said translation entry in said one-time TLB to continue execution.
Claim 28
Dependent Claim
27 words
The method of claim 22 wherein said virtual address is a linear address generated by adding a segment base to an address generated by said user program.
References Cited (Backward Citations)
US3942155A
Cited
US4376297A
Cited
US4550368A
Cited
US4972338A
Cited
US4885680A
Cited
US4961135A
Cited
US5058003A
Cited
US5261049A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-07 | 1999-02-06 | 1999-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-07 | 2003-02-06 | 2003-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-07 | 2007-02-06 | 2007-08-08 | $7700.00 | Window Closed / Lapsed |