Memory management system and method for allocating and reusing memory

• US 6,701,420 B1
• Filed: 02/01/1999
• Issued: 03/02/2004
• Est. Priority Date: 02/01/1999
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Johnson, Brett Edward, Hamilton, Michael T
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/241,469
• Time in Patent Office: 1,856 Days
• Field of Search: 711/170, 711/171, 711/172, 711/156, 711/163, 711/165, 709/104, 707/205
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A memory management system and method that quickly allocates and reuses memory for storage of data, such as display lists in a graphics system. The memory manager allocates memory without information regarding the amount of memory that is to be required while minimizing system-level memory allocation calls and maximizing the contiguity of the allocated memory which is used. The memory manager acquires from system memory a memory block that is of a predetermined size that is significantly larger than the anticipated memory size required to store a display list. The memory manager allocates to the display list that portion of the acquired memory block necessary for storing the display list, maintaining control over the unused portion of the acquired memory in a memory pool of available memory for future allocation to another display list without performing subsequent system-level calls.

Claims

1. In a computer system having an operating system operatively coupled to a system memory and a graphics system, a method for allocating memory to store display lists for processing by the graphics system, the method comprising the steps of:

generating a system-level call to acquire a contiguous block of system memory logically comprising a data region defining a free memory node;

allocating the free memory node to a display list without generating a system-level call;

logically forming a portion of a memory block required to store the display list into a separately-managed used memory node, and any remaining portion of the memory block into a separately-managed free memory node that is not returned to system memory; and

repeating the allocating and logically forming steps to store all or part of a next display list in the separately-managed free memory node.

2. The method of claim 1, wherein the memory block is one of a plurality of individually-acquired memory blocks that are logically associated in a locally-controlled memory pool.

3. The method of claim 1, wherein the generating step occurs in response to a request to store a display list in memory, wherein the size of the acquired memory block is greater than that necessary to store the display list.

4. The method of claim 1, wherein the memory block comprises a plurality of free memory nodes, and wherein the repeating step comprises:

selecting a free memory node that includes sufficient memory space to store the next display list;

allocating the selected free memory node to the next display list without generating a system-level call; and

logically forming a portion of the selected memory node required to store the next display list into a separately-managed used memory node, and any remaining portion of the selected memory block into a separately-managed free memory node.

5. The method of claim 4, wherein the repeating step further comprises the steps of:

before the selecting step, determining whether the memory block comprises a memory node having sufficient space to store the next display list,

wherein the selecting, allocating and logically forming steps are performed when the selecting step is determined affirmatively; and

acquiring an additional memory block from system memory when step d) is determined negatively,

wherein the selecting, allocating and logically forming steps are performed so as to store the next display list in the additional memory block.

6. The method of claim 1, wherein the memory nodes comprise data and header regions in which display list and memory management data are respectively stored, and wherein the used and free status of each memory node is maintained in one or more lists stored in the memory node header regions.

7. The method of claim 1, wherein the memory block is one of a plurality of individually-acquired memory blocks that are logically associated in a locally-controlled memory pool, each memory block also comprising a header region in which memory management data is stored.

8. The method of claim 1, wherein when the memory block comprises one or more used and free memory nodes the method further comprises the steps of:

e) coalescing the adjacent free memory nodes into a single separately-managed free memory node having a contiguous data region having a size equal to at least a sum of the sizes of the data regions of the coalesced memory nodes.

9. The method of claim 8, further comprising the steps of:

f) deallocating each memory node in the memory block as it is no longer needed to store display lists, wherein the deallocated memory node is not returned to system memory and is retained as a free memory node in the memory pool.

10. In a computer system having an operating system operatively coupled to a system memory and a graphics system, a memory manager for managing the storage of display lists as they are generated by graphics application, the memory manager comprising:

a memory resizer that acquires from system memory a memory pool of one or more memory blocks each comprising one or more memory nodes in which all or part of a display list can be stored, wherein the memory resizer resizes partially used memory nodes by logically forming a portion of a memory node required to store the display list into a separately-managed used memory node, and any remaining portion of the memory node into a separately-managed free memory node that is not returned to system memory.

11. The memory manager of claim 10, wherein the memory manager further comprises:

a memory allocator configured to allocate to the display list without generating a system-level call, one or more free memory nodes in the memory pool when sufficient memory to store the display list is available in the memory pool, and to acquire a block of memory from system memory using a system-level call when sufficient memory to store the display list is not available in the memory pool.

12. The memory manager of claim 10, wherein the memory allocator allocates the one or more memory nodes in response to a request to store a display list in memory, wherein when the memory allocator acquires a memory block from system memory, the acquired memory block has a size that is greater than that necessary to store the display list.

13. The memory manager of claim 10, wherein the memory nodes comprise data and header regions in which display list and memory management data are respectively stored, and wherein used and free status of each memory node is maintained in one or more lists stored in the memory node header regions.

14. The memory manager of claim 10, wherein the memory block is one of a plurality of individually-acquired memory blocks that are logically associated in a memory pool controlled by the memory manager, each memory block also comprising a header region in which memory management data is stored.

15. The memory manager of claim 10, wherein when the memory block comprises one or more used and free memory nodes, wherein the memory manager further comprises:

a coalescer that combines adjacent free memory nodes into a single separately-managed free memory node having a contiguous data region the size of which is approximately equal to at least a sum of the sizes of the data regions of the coalesced memory nodes.

16. The memory manager of claim 15, further comprising:

a deallocator that deallocates each memory node in the memory block as the memory node is no longer needed to store display lists, wherein the deallocator returns memory node is not returned to system memory and is retained as a free memory node in the memory pool.

17. The memory manager of claim 10, wherein the memory manager is an operational component of a display list driver that managing the storage of display lists as they are generated by graphics application and also comprises:

a display list compiler configured to generate a request for memory to store a display list upon receipt of a graphics call sequence from the graphics application; and

a display list executor configured to retrieve a display list from the memory pool and to provide the display list to a graphics hardware driver of the computer system.

18. The memory manager of claim 17, wherein the display list compiler generates the request for memory prior to receiving information indicative of the size of the display list to be stored.

19. The memory manager of claim 18, wherein the memory request is a system-level call, and wherein the memory manager intercepts and processes the system-level call generated by the display list driver.

20. In a computer system having an operating system operatively coupled to a system memory and a graphics system, a memory manager for managing the storage of display lists as they are generated by graphics application, the memory manager comprising:

memory resizing means for acquiring from system memory a memory pool of one or more memory blocks each comprising one or more memory nodes in which all or part of a display list can be stored, and for resizing partially used memory nodes by logically forming a portion of a memory node required to store the display list into a separately-managed used memory node, and any remaining portion of the memory node into a separately-managed free memory node that is not returned to system memory.

21. The memory manager of claim 20, wherein the memory manager further comprises:

a memory allocator configured to allocate to the display list without generating a system-level call, one or more free memory nodes in the memory pool when sufficient memory to store the display list is available in the memory pool, and to acquire a block of memory from system memory using a system-level call when sufficient memory to store the display list is not available in the memory pool.

22. The memory manager of claim 20, wherein when the memory block comprises one or more used and free memory nodes, wherein the memory manager further comprises:

coalescing means for combining adjacent free memory nodes into a single separately-managed free memory node having a contiguous data region the size of which is approximately equal to at least a sum of the sizes of the data regions of the coalesced memory nodes.

23. The memory manager of claim 20, further comprising:

deallocating means for deallocating each memory node in the memory block as the memory node is no longer needed to store display lists, wherein the deallocating means returns memory node is not returned to system memory and is retained as a free memory node in the memory pool.

24. The memory manager of claim 20, wherein the memory manager is an operational component of a display list driver that managing the storage of display lists as they are generated by graphics application and also comprises:

a compiling means for generating a request for memory to store a display list upon receipt of a graphics call sequence from the graphics application; and

a display list executing means for retrieving a display list from the memory pool and for providing the display list to a graphics hardware driver of the computer system.