US6457112B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Memory block allocation system and method
Assignee: SCSK Corp
•
Filing: 2001-08-20
•
Granted: 2002-09-24
•
Expires: 2021-08-20
Abstract
Abstract A system and method for allocating memory blocks and indexing the pointer to the memory blocks in a set of tables. The tables translate the pointers to the memory blocks enabling the efficient lookup of pointers during translation and garbage collection. The memory blocks further include structures for facilitating the indexing into tables and referencing pointers into allocated memory.
Inventors
- 👤 Mathew J. Hostetter
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:50
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
388 words
A method of allocating memory from a pool of free memory comprising the steps of: a) allocating a memory block from the pool of free memory, the memory block having a size at least as large as a predefined page size and composed of at least one memory block pages, the memory block storing representations of memory block characteristics, a next memory block address, and data; b) for each of the at least one memory block pages in the memory block, each of the at least one memory block pages having a page address, executing the steps of i) checking an entry in a first page table found by indexing into the first page table with a first portion of the page address, ii) if the entry in the first page table is null, executing the steps of creating a second page table having a set of entries for storing representations of addresses to memory blocks, entering a representation of the address of the second page table in the first page table entry selected by the first portion of the page address, and entering in the second page table a representation of the page address to the memory block at the entry selected by a second portion of the page address; iii) if the entry in the first page table is not null, executing the steps of selecting the second page table via the representation of the address to the second page table found in the entry of the first page table, checking a second page table entry found by indexing into the second page table with the second portion of the page address, if the entry in the second page table is null, entering the representation of the memory block address in that entry, otherwise if the page address represents a first of the at least one memory block pages, entering the representation of the memory block address in the entry of the second page table and storing the former contents of that entry in the next memory block address of the memory block, or if the page address does not represent the first of the at least one memory block pages, entering the memory block address in the next memory block address of a memory block pointed to by the entry in the second page table.
Claim 2
Independent Claim
388 words
A method of allocating memory from a pool of free memory comprising the steps of: a) allocating a memory block from the pool of free memory, the memory block having a size at least as large as a predefined page size and composed of at least one memory block pages, the memory block storing representations of memory block characteristics, a next memory block address, and data; b) for each of the at least one memory block pages in the memory block, each of the at least one memory block pages having a page address, executing the steps of i) checking an entry in a first page table found by indexing into the first page table with a first portion of the page address, ii) if the entry in the first page table is null, executing the steps of creating a second page table having a set of entries for storing representations of addresses to memory blocks, entering a representation of the address of the second page table in the first page table entry selected by the first portion of the page address, and entering in the second page table a representation of the page address to the memory block at the entry selected by a second portion of the page address; iii) if the entry in the first page table is not null, executing the steps of selecting the second page table via the representation of the address to the second page table found in the entry of the first page table, checking a second page table entry found by indexing into the second page table with the second portion of the page address, if the entry in the second page table is null, entering the representation of the memory block address in that entry, otherwise if the page address represents a first of the at least one memory block pages, entering the representation of the memory block address in the entry of the second page table and storing the former contents of that entry in the next memory block address of the memory block, or if the page address does not represent the first of the at least one memory block pages, entering the memory block address in the next memory block address of a memory block pointed to by the entry in the second page table.
Claim 3
Dependent Claim
21 words
The method of claim 1 wherein the predefined page size is determined by a page size portion of the page address.
Claim 4
Dependent Claim
29 words
The method of claim 2 wherein the page size portion of the page address is not used for indexing into the first page table or the second page table.
Claim 5
Dependent Claim
402 words
Computer-excutable codes stored on a compute-readable medium, the computer-executable codes are executed to allocate memory from a pool of free memory, the computer-executable codes comprising: a) code to allocate a memory block from the pool of free memory, the memory block having a size at least as large as a predefined page size and composed of at least one memory block pages, the memory block storing representations of memory block characteristics, a next memory block address, and data b) for each of the at least one memory block pages in the memory block, each of the at least one memory block pages having a page address, code to execute the steps of i) checking an entry in a first page table found by indexing into the first page table with a first portion of the page address, ii) if the entry in the first page table is null, executing the steps of creating a second page table having a set of entries for storing representations of addresses to memory blocks, entering a representation of the address of the second page table in the first page table entry selected by the first portion of the page address, and entering in the second page table a representation of the page address to the memory block at the entry selected by a second portion of the page address; iii) if the entry in the first page table is not null, executing the steps of selecting the second page table via the representation of the address to the second page table found in the entry of the first page table, checking a second page table entry found by indexing into the second page table with the second portion of the page address, if the entry in the second page table is null, entering the representation of the memory block address in that entry, otherwise if the page address represents a first of the at least one memory block pages, entering the representation of the memory block address in the entry of the second page table and storing the former contents of that entry in the next memory block address of the memory block, or if the page address does not represent the first of the at least one memory block pages, entering the memory block address in the next memory block address of a memory block pointed to by the entry in the second page table.
Claim 6
Dependent Claim
402 words
Computer-excutable codes stored on a compute-readable medium, the computer-executable codes are executed to allocate memory from a pool of free memory, the computer-executable codes comprising: a) code to allocate a memory block from the pool of free memory, the memory block having a size at least as large as a predefined page size and composed of at least one memory block pages, the memory block storing representations of memory block characteristics, a next memory block address, and data b) for each of the at least one memory block pages in the memory block, each of the at least one memory block pages having a page address, code to execute the steps of i) checking an entry in a first page table found by indexing into the first page table with a first portion of the page address, ii) if the entry in the first page table is null, executing the steps of creating a second page table having a set of entries for storing representations of addresses to memory blocks, entering a representation of the address of the second page table in the first page table entry selected by the first portion of the page address, and entering in the second page table a representation of the page address to the memory block at the entry selected by a second portion of the page address; iii) if the entry in the first page table is not null, executing the steps of selecting the second page table via the representation of the address to the second page table found in the entry of the first page table, checking a second page table entry found by indexing into the second page table with the second portion of the page address, if the entry in the second page table is null, entering the representation of the memory block address in that entry, otherwise if the page address represents a first of the at least one memory block pages, entering the representation of the memory block address in the entry of the second page table and storing the former contents of that entry in the next memory block address of the memory block, or if the page address does not represent the first of the at least one memory block pages, entering the memory block address in the next memory block address of a memory block pointed to by the entry in the second page table.
Claim 7
Dependent Claim
27 words
The computer-executable codes stored on a computer-readable medium of claim 4 wherein the predefined page size is determined by a page size portion of the page address.
Claim 8
Dependent Claim
35 words
The computer-executable codes stored on a computer-readable medium of claim 5 wherein the page size portion of the page address is not used for indexing into the first page table or the second page table.
Claim 9
Independent Claim
426 words
An apparatus for allocating memory from a pool of free memory, the apparatus comprising: a memory which stores computer-executable codes and the pool of free memory; and a processor which executes the codes so as to a) allocate a memory block from the pool of free memory, the memory block having a size at least as large as a predefined page size and composed of at least one memory block pages, the memory block consisting of slots for storing representations of a starting address, an ending address, a next memory block address, and data, b) for each of the at least one memory block pages in the memory block, each of the at least one memory block pages having a page address, execute the steps so as to i) check an entry in a first page table found by indexing into the first page table with a first portion of the page address, ii) determine if the entry in the first page table is null, then execute the steps so as to create a second page table having a set of entries for storing representations of addresses to memory blocks, enter a representation of the address of the second page table in the first page table entry selected by the first portion of the page address, and enter in the second page table a representation of the page address to the memory block at the entry selected by a second portion of the page address, iii) determine if the entry in the first page table is not null, then execute the steps so as to select the second page table via the representation of the address to the second page table found in the entry of the first page table, check a second page table entry found by indexing into the second page table with the second portion of the page address, if the entry in the second page table is null, enter the representation of the memory block address in that entry, otherwise if the page address represents a first of the at least one memory block pages, enter the representation of the memory block address in the entry of the second page table and storing the former contents of that entry in the next memory block address of the memory block, or if the page address does not represent the first of the at least one memory block pages, enter the memory block address in the next memory block address of a memory block pointed to by the entry in the second page table.
Claim 10
Independent Claim
426 words
An apparatus for allocating memory from a pool of free memory, the apparatus comprising: a memory which stores computer-executable codes and the pool of free memory; and a processor which executes the codes so as to a) allocate a memory block from the pool of free memory, the memory block having a size at least as large as a predefined page size and composed of at least one memory block pages, the memory block consisting of slots for storing representations of a starting address, an ending address, a next memory block address, and data, b) for each of the at least one memory block pages in the memory block, each of the at least one memory block pages having a page address, execute the steps so as to i) check an entry in a first page table found by indexing into the first page table with a first portion of the page address, ii) determine if the entry in the first page table is null, then execute the steps so as to create a second page table having a set of entries for storing representations of addresses to memory blocks, enter a representation of the address of the second page table in the first page table entry selected by the first portion of the page address, and enter in the second page table a representation of the page address to the memory block at the entry selected by a second portion of the page address, iii) determine if the entry in the first page table is not null, then execute the steps so as to select the second page table via the representation of the address to the second page table found in the entry of the first page table, check a second page table entry found by indexing into the second page table with the second portion of the page address, if the entry in the second page table is null, enter the representation of the memory block address in that entry, otherwise if the page address represents a first of the at least one memory block pages, enter the representation of the memory block address in the entry of the second page table and storing the former contents of that entry in the next memory block address of the memory block, or if the page address does not represent the first of the at least one memory block pages, enter the memory block address in the next memory block address of a memory block pointed to by the entry in the second page table.
Claim 11
Dependent Claim
21 words
The apparatus of claim 7 wherein the predefined page size is determined by a page size portion of the page address.
Claim 12
Dependent Claim
30 words
The apparatus of claim 8 where in the page size portion of the page address is not used to indexed into the first page table or the second page table.
References Cited (Backward Citations)
US6088780A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-09-23 | 2006-03-25 | 2006-09-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-09-23 | 2010-03-25 | 2010-09-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-09-23 | 2014-03-25 | 2014-09-24 | $7700.00 | Window Closed / Lapsed |