US5930827A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for dynamic memory management by association of free memory blocks using a binary tree organized in an address and size dependent manner
Assignee: Intel Corp
•
Filing: 1996-12-02
•
Granted: 1999-07-27
•
Expires: 2016-12-02
Abstract
Abstract A method and apparatus for dynamically allocating system memory using a binary tree organized in an address and size dependent manner. Within the prior art, dynamic memory allocation methods were not portable to virtual memory addressing systems wherein local memory and system memory were joined in a continuous region of linear addresses. The allocation method of the present invention utilizes a binary tree of free memory block headers, corresponding to free memory blocks. Each free memory block header has an address field and a translation table field. The address field corresponds to a virtual address of the free memory block. The translation table field points to an entry within a translation table that is used to map the virtual address to a block in system memory.
Inventors
- 👤 Jay J. Sturges
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 15:32
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/08; G06F12/10; G06F12/0223; G06F12/023
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
103 words
A method of allocating system memory within a computer system, comprising the steps of: (A) building a binary tree of free memory block headers, wherein each free memory block header includes an address field corresponding to a virtual address of a free memory block, and a translation table field pointing to an entry within a translation table, wherein each entry within said translation table corresponds to a block of said system memory; and (B) upon receiving an allocation request, allocating at least a part of a first of said blocks of system memory by using said binary tree of free memory block headers.
Claim 2
Independent Claim
103 words
A method of allocating system memory within a computer system, comprising the steps of: (A) building a binary tree of free memory block headers, wherein each free memory block header includes an address field corresponding to a virtual address of a free memory block, and a translation table field pointing to an entry within a translation table, wherein each entry within said translation table corresponds to a block of said system memory; and (B) upon receiving an allocation request, allocating at least a part of a first of said blocks of system memory by using said binary tree of free memory block headers.
Claim 3
Dependent Claim
49 words
The method of claim 1, further comprising the steps of: (C) upon receiving a deallocation request, deallocating said allocated first block of system memory by inserting a free memory block header corresponding to said first block of system memory in to said binary tree of free memory block headers.
Claim 4
Dependent Claim
50 words
The method of claim 1, wherein each of said free memory block headers formed in step (A) further comprises an offset address, and wherein step (B) further comprises the step of allocating a portion of said first system memory block starting at said offset address within said system memory block.
Claim 5
Dependent Claim
37 words
The method of claim 1, wherein said address field of each of said free memory block headers corresponds to a virtual address within a continuous linear region of virtual addresses available to clients within said computer system.
Claim 6
Dependent Claim
42 words
The method of claim 4, wherein said continuous linear region of virtual addresses includes a first group of addresses corresponding to local graphics memory and a second group of addresses corresponding to entries mapped into said system memory by said translation table.
Claim 7
Dependent Claim
169 words
The method of claim 1, wherein each of said free memory block headers of said binary tree further includes a size field indicating a size of said corresponding system memory block, and wherein said free memory block headers are organized into said binary tree in accordance with said size field and said address field, said binary tree comprising a predecessor free memory block an d a descendant free memory block, wherein the size field of the predecessor free memory block header is greater than the size field of the descendant free memory block header, the address field of the predecessor free memory block header is greater than the address field of the descendant free memory block header if the descendant free memory block header is a left free memory block header, and the address field of the predecessor free memory block header is less than the address field of the descendant free memory block header if the descendant free memory block header is a right free memory block header.
Claim 8
Dependent Claim
203 words
The method of claim 6, wherein said predecessor free memory block header includes two descendant free memory block headers, one a left free memory block header and one a right free memory block header, and wherein allocating said block of system memory of step (B) further includes the steps of (B1) upon receiving said allocation request, also receiving a requested block size; (B2) searching the binary tree of free memory block headers starting from said predecessor free memory block header and descending to said left free memory block header if said size field of said left free memory block header is greater than or equal to said requested block size, (B3) if said size field of said left free memory block header is less than said requested block size, descending to said right free memory block header if said size field of said right free memory block header is greater than or equal to said requested block size; and (B4) allocating said system memory block corresponding to said predecessor free memory block header if said size field of said left free memory block header and said size field of said right free memory block header are both smaller than said requested block size.
Claim 9
Dependent Claim
18 words
The method of claim 1, wherein each of said entries of said translation table are 32 bits long.
Claim 10
Dependent Claim
17 words
The method of claim 1, wherein each of said blocks of system memory are 4 kilobytes long.
Claim 11
Dependent Claim
12 words
A special purpose computer system for performing the method of claim 1.
Claim 12
Independent Claim
261 words
A method of allocating a plurality of blocks of system memory within a computer system, comprising the steps of: (A) building a translation table including a plurality of entries, each entry pointing to a block of said system memory; (B) building a free memory block binary tree including free memory block headers, each of said free memory block headers including a size field, an address field, and a translation table field, wherein said free memory block headers are organized into a binary tree in accordance with said size field and address field, said binary tree comprising a predecessor free memory block and a descendant free memory block, wherein the size field of the predecessor free memory block header is greater than the size field of the descendant free memory block header, the address field of the predecessor free memory block header is greater than the address field of the descendant free memory block header if the descendant free memory block header is a left descendant free memory block, the address field of the predecessor free memory block header is less than the address field of the descendant free memory block header if the descendant free memory block header is a right descendant free memory block, and the translation table field of each free memory block header points to an entry in the translation table corresponding to a free system memory block; and (C) upon receiving an allocation request, allocating at least a part of a first of said plurality of system memory blocks by using said free memory block binary tree.
Claim 13
Independent Claim
261 words
A method of allocating a plurality of blocks of system memory within a computer system, comprising the steps of: (A) building a translation table including a plurality of entries, each entry pointing to a block of said system memory; (B) building a free memory block binary tree including free memory block headers, each of said free memory block headers including a size field, an address field, and a translation table field, wherein said free memory block headers are organized into a binary tree in accordance with said size field and address field, said binary tree comprising a predecessor free memory block and a descendant free memory block, wherein the size field of the predecessor free memory block header is greater than the size field of the descendant free memory block header, the address field of the predecessor free memory block header is greater than the address field of the descendant free memory block header if the descendant free memory block header is a left descendant free memory block, the address field of the predecessor free memory block header is less than the address field of the descendant free memory block header if the descendant free memory block header is a right descendant free memory block, and the translation table field of each free memory block header points to an entry in the translation table corresponding to a free system memory block; and (C) upon receiving an allocation request, allocating at least a part of a first of said plurality of system memory blocks by using said free memory block binary tree.
Claim 14
Dependent Claim
44 words
The method of claim 11, further comprising the step of: (D) upon receiving a deallocation request, deallocating said first allocated system memory block by inserting a free memory block header corresponding to said first memory block in to said free memory block binary tree.
Claim 15
Dependent Claim
50 words
The method of claim 11, wherein each of said free memory block headers formed in step (B) further comprises an offset address, and wherein step (C) further comprises the step of allocating a portion of said first system memory block starting at said offset address within said system memory block.
Claim 16
Dependent Claim
36 words
The method of claim 11, wherein said address field of each of said free memory blocks corresponds to a virtual address within a continuous linear region of virtual addresses available to clients within said computer system.
Claim 17
Dependent Claim
42 words
The method of claim 14, wherein said continuous linear region of virtual addresses includes a first group of addresses corresponding to local graphics memory and a second group of addresses corresponding to entries mapped into said system memory by said translation table.
Claim 18
Dependent Claim
203 words
The method of claim 11, wherein said predecessor free memory block header includes two descendant free memory block headers, one a left free memory block header and one a right free memory block header, and wherein allocating said block of system memory of step (C) further includes the steps of (C1) upon receiving said allocation request, also receiving a requested block size; (C2) searching the binary tree of free memory block headers starting from said predecessor free memory block header and descending to said left free memory block header if said size field of said left free memory block header is greater than or equal to said requested block size, (C3) if said size field of said left free memory block header is less than said requested block size, descending to said right free memory block header if said size field of said right free memory block header is greater than or equal to said requested block size; and (C4) allocating said system memory block corresponding to said predecessor free memory block header if said size field of said left free memory block header and said size field of said right free memory block header are both smaller than said requested block size.
Claim 19
Dependent Claim
18 words
The method of claim 11, wherein each of said entries of said translation table are 32 bits long.
Claim 20
Dependent Claim
17 words
The method of claim 11, wherein each of said blocks of system memory are 4 kilobytes long.
Claim 21
Dependent Claim
12 words
A special purpose computer system for performing the method of claim 11.
Claim 22
Independent Claim
183 words
An apparatus for allocating system memory within a computer system, said apparatus comprising: (A) a first storage area having a first plurality of addressable units each corresponding to a virtual address, and wherein each addressable unit is capable of storing a translation table entry, and wherein each translation table entry points to a physical address; (B) a second storage area having a second plurality of addressable units, wherein each addressable unit has a free memory block header stored within it, and wherein each free memory block header includes an address field capable of storing one of said virtual addresses of said translation table, and a translation table field capable of storing a pointer to one of said translation table entries, and wherein said free memory block headers are logically organized as a binary tree; and (C) a system memory having a plurality of free addressable units each corresponding to one of said physical addresses within said translation table, and wherein at least a portion of each of said free addressable units are allocated according to said binary tree of free memory block headers.
Claim 23
Independent Claim
183 words
An apparatus for allocating system memory within a computer system, said apparatus comprising: (A) a first storage area having a first plurality of addressable units each corresponding to a virtual address, and wherein each addressable unit is capable of storing a translation table entry, and wherein each translation table entry points to a physical address; (B) a second storage area having a second plurality of addressable units, wherein each addressable unit has a free memory block header stored within it, and wherein each free memory block header includes an address field capable of storing one of said virtual addresses of said translation table, and a translation table field capable of storing a pointer to one of said translation table entries, and wherein said free memory block headers are logically organized as a binary tree; and (C) a system memory having a plurality of free addressable units each corresponding to one of said physical addresses within said translation table, and wherein at least a portion of each of said free addressable units are allocated according to said binary tree of free memory block headers.
Claim 24
Dependent Claim
53 words
The apparatus of claim 20, further comprising: (C) means for receiving a deallocation request and correspondingly deallocating a first of said allocated addressable units of system memory by inserting a free memory block header corresponding to said first addressable unit of system memory in to said binary tree of free memory block headers.
Claim 25
Dependent Claim
58 words
The apparatus of claim 20, wherein each of said free memory block headers stored in said second storage area further comprises an offset field capable of storing an offset address, wherein said offset address indicates an offset from a beginning address of a corresponding addressable unit of said system memory at which allocation of said addressable unit begins.
Claim 26
Dependent Claim
18 words
The apparatus of claim 20, wherein each of said entries of said translation table are 32 bits long.
Claim 27
Dependent Claim
18 words
The apparatus of claim 20, wherein each of said addressable units of system memory are 4 kilobytes long.
Claim 28
Dependent Claim
149 words
A memory device comprising: (A) a first storage area comprising a first plurality of addressable units, wherein a translation table entry is stored within each of said first plurality of addressable units, and wherein each entry within said translation table corresponds to a block of system memory of a computer system; and (B) a second storage area comprising a second plurality of addressable units, wherein a free memory block header is stored within each of said second plurality of addressable units, and each free memory block header includes an address field corresponding to a virtual address of a free block of said system memory of said computer system, and a translation table field pointing to one of said translation table entries, and wherein said free memory block headers are organized in a binary tree and said free blocks of said system memory are allocated according to said binary tree.
Claim 29
Dependent Claim
149 words
A memory device comprising: (A) a first storage area comprising a first plurality of addressable units, wherein a translation table entry is stored within each of said first plurality of addressable units, and wherein each entry within said translation table corresponds to a block of system memory of a computer system; and (B) a second storage area comprising a second plurality of addressable units, wherein a free memory block header is stored within each of said second plurality of addressable units, and each free memory block header includes an address field corresponding to a virtual address of a free block of said system memory of said computer system, and a translation table field pointing to one of said translation table entries, and wherein said free memory block headers are organized in a binary tree and said free blocks of said system memory are allocated according to said binary tree.
Claim 30
Dependent Claim
17 words
The memory device of claim 25, wherein each entry within said translation table is 32 bits long.
Claim 31
Dependent Claim
19 words
The memory device of claim 25, wherein each of said free blocks of system memory is 4 kilobytes long.
Claim 32
Independent Claim
119 words
An apparatus comprising: an execution unit that executes programming instructions; and a storage medium having stored therein a plurality of programming instructions to be executed by said execution unit, said programming instructions implementing dynamic memory management program that builds a binary tree of free memory block headers, wherein each free memory block header includes an address field corresponding to a virtual address of a free memory block, and a translation table field pointing to an entry within a translation table, wherein each entry within said translation table corresponds to a block of system memory, and allocates at least a part of a first of said blocks of system memory by using said binary tree of free memory block headers.
Claim 33
Independent Claim
119 words
An apparatus comprising: an execution unit that executes programming instructions; and a storage medium having stored therein a plurality of programming instructions to be executed by said execution unit, said programming instructions implementing dynamic memory management program that builds a binary tree of free memory block headers, wherein each free memory block header includes an address field corresponding to a virtual address of a free memory block, and a translation table field pointing to an entry within a translation table, wherein each entry within said translation table corresponds to a block of system memory, and allocates at least a part of a first of said blocks of system memory by using said binary tree of free memory block headers.
Claim 34
Dependent Claim
187 words
The apparatus of claim 28, wherein said storage medium further includes programming instructions to build said binary tree such that each of said free memory block headers further includes a size field indicating a size of said corresponding block of system memory, and wherein said free memory block headers are organized into said binary tree in accordance with said size field and said address field, said binary tree comprising a predecessor free memory block and a descendant free memory block, and wherein said binary tree is built such that the size field of the predecessor free memory block header is greater than the size field of the descendant free memory block header, the address field of the predecessor free memory block header is greater than the address field of the descendant free memory block header if the descendant free memory block header is a left free memory block header, and the address field of the predecessor free memory block header is less than the address field of the descendant free memory block header if the descendant free memory block header is a right free memory block header.
Claim 35
Dependent Claim
48 words
The apparatus of claim 28, wherein said storage medium further includes programming instructions to build said binary tree such that each predecessor free memory block header includes two descendant free memory block headers, one a left free memory block header and one a right free memory block header.
Claim 36
Dependent Claim
170 words
The apparatus of claim 30, wherein said storage medium further includes programming instructions to allocate said block of system memory upon receiving said allocation request coupled with a requested block size by searching the binary tree of free memory block headers starting from said predecessor free memory block header and descending to said left free memory block header if said size field of said left free memory block header is greater than or equal to said requested block size, if said size field of said left free memory block header is less than said requested block size, descending to said right free memory block header if said size field of said right free memory block header is greater than or equal to said requested block size, and allocating said system memory block corresponding to said predecessor free memory block header if said size field of said left free memory block header and said size field of said right free memory block header are both smaller than said requested block size.
References Cited (Backward Citations)
US3544976A
Cited
US4491836A
Cited
US4492956A
Cited
US4496944A
Cited
US5189733A
Cited
US5193202A
Cited
US5339397A
Cited
US5446863A
Cited
US5561786A
Cited
US5440692A
Cited
US5644749A
Cited
US5446854A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-26 | 2003-01-25 | 2003-07-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-26 | 2007-01-25 | 2007-07-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-26 | 2011-01-25 | 2011-07-27 | $7700.00 | Window Closed / Lapsed |