Heap memory management

• US 20040186976A1
• Filed: 03/12/2004
• Published: 09/23/2004
• Est. Priority Date: 03/19/2003
• Status: Active Grant

• Current Assignee: Autodesk, Inc.
• Original Assignee: Autodesk, Inc.
• Inventors: Bayt, Jack M.
• Granted Patent: US 7,272,698 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method, apparatus, and article of manufacture provide the ability to efficiently and effectively manage memory. A file is broken into multiple memory blocks that are managed as nodes in a heap tree. A request to access memory at a linear file address is received. The linear file address is then translated to the appropriate heap block reference to complete the memory access. Additionally, a tri-linked list/tree of deallocated memory units available for use by the heap may be used. A first link points to units smaller than a current block size, a second link points to units equal to the current block size, and a third link points to units larger than the current block size. When a request for memory is received, the tree is traversed to find a unit that satisfies the request and the appropriate unit in the free list is allocated.

Claims

1. A method for managing memory, comprising:

breaking up a file into two or more memory blocks;

managing the two or more memory blocks as nodes in a heap tree wherein each node has a heap block reference;

receiving a request to access memory at a linear file address; and

translating the linear file address to an appropriate heap block reference to access the memory block.

2. The method of claim 1, wherein the translating utilizes a file address mapping tree comprising a mapping from linear file addresses to heap block references.

3. The method of claim 2, further comprising updating the file address mapping tree when a block is inserted into the heap tree.

4. The method of claim 2, further comprising updating the file address mapping tree when address space is deleted by:

deleting an associated block from the heap tree;

reducing a size of partial blocks as needed; and

adjusting the file address mapping tree accordingly.

5. The method of claim 1, wherein:

(a) the request to access memory comprises a request to insert data into the file at an insertion point; and

(b) the method further comprises;

(i) breaking one of the memory blocks at the insertion point; and

(ii) inserting the new data as a node in the heap tree.

6. A method for allocating memory comprising:

maintaining, in a tree, a tri-linked list of deallocated memory units available for use by a heap, wherein a first link points to available deallocated memory units smaller than a current block size, a second link points to available deallocated memory units equal to the current block size, and a third link points to available deallocated memory units larger than the current block size;

receiving a request for memory;

traversing the tree to find a deallocated memory unit that satisfies the request for memory; and

allocating the deallocated memory unit that satisfies the request.

7. The method of claim 6, wherein the traversing does not search the second link.

8. The method of claim 6, wherein memory units of equal size are linked together in the tree.

9. A system for managing memory comprising:

(a) a file broken up into two or more blocks of memory;

(b) a heap tree configured to manage the two or more blocks of memory as nodes in the heap tree, wherein;

(i) each node has a heap block reference;

(ii) the heap tree is configured to receive a request to access memory at a linear file address; and

(iii) the heap tree is configured to translate the linear file address to an appropriate heap block reference to access the memory block.

10. The system of claim 9, further comprising a file address mapping tree utilized by the heap tree, wherein the file address mapping tree comprises a mapping from linear file addresses to heap block references.

11. The system of claim 10, wherein the file address mapping tree is updated when a block is inserted into the heap tree.

12. The system of claim 10, wherein the file address mapping tree is updated when address space is deleted by:

deleting an associated block from the heap tree;

reducing a size of partial blocks as needed; and

adjusting the file address mapping tree accordingly.

13. The system of claim 9, wherein:

(a) the request to access memory comprises a request to insert data into the file at an insertion point; and

(b) the heap tree is configured to insert the data by;

(i) breaking one of the memory blocks at the insertion point; and

(ii) inserting the new data as a node in the heap tree.

14. A system for allocating memory comprising:

(a) a heap tree comprising a tri-linked list of deallocated memory units available for use by a heap;

(b) a first link of the tri-linked list pointing to available deallocated memory units smaller than a current block size;

(c) a second link of the tri-linked list pointing to available deallocated memory units equal to the current block size;

(d) a third link of the tri-linked list pointing to available deallocated memory units larger than the current block size;

(e) the heap configured to;

(i) receive a request for memory;

(ii) traverse the heap tree to find a deallocated memory unit that satisfies the request for memory; and

(iii) allocate the deallocated memory unit that satisfies the request.

15. The system of claim 14, wherein memory units of equal size are linked together in the heap tree.

16. An article of manufacture comprising a program storage medium readable by a computer and embodying one or more instructions executable by the computer to perform a method for managing memory, the method comprising:

breaking up a file into two or more memory blocks;

managing the two or more memory blocks as nodes in a heap tree wherein each node has a heap block reference;

receiving a request to access memory at a linear file address; and

translating the linear file address to an appropriate heap block reference to access the memory block.

17. The article of manufacture of claim 16, wherein the translating utilizes a file address mapping tree comprising a mapping from linear file addresses to heap block references.

20. The article of manufacture of claim 16, wherein:

(a) the request to access memory comprises a request to insert data into the file at an insertion point; and

(b) the method further comprises;

(i) breaking one of the memory blocks at the insertion point; and

(ii) inserting the new data as a node in the heap tree.

18. The article of manufacture of claim 18, wherein the method further comprises updating the file address mapping tree when a block is inserted into the heap tree.

19. The article of manufacture of claim 18, wherein the file address mapping tree is updated when address space is deleted by:

deleting an associated block from the heap tree;

reducing a size of partial blocks as needed; and

adjusting the file address mapping tree accordingly.

21. An article of manufacture comprising a program storage medium readable by a computer and embodying one or more instructions executable by the computer to perform a method for allocating memory, the method comprising:

maintaining, in a tree, a tri-linked list of deallocated memory units available for use by a heap, wherein a first link points to available deallocated memory units smaller than a current block size, a second link points to available deallocated memory units equal to the current block size, and a third link points to available deallocated memory units larger than the current block size;

receiving a request for memory;

traversing the tree to find a deallocated memory unit that satisfies the request for memory; and

allocating the deallocated memory unit that satisfies the request.

22. The article of manufacture of claim 21, wherein the traversing does not search the second link.

23. The article of manufacture of claim 21, wherein memory units of equal size are linked together in the tree.