Memory management system and method using dual indexing structures

• US 5,835,959 A
• Filed: 12/01/1995
• Issued: 11/10/1998
• Est. Priority Date: 12/01/1995
• Status: Expired due to Term

• Current Assignee: SAND Technology, Inc.
• Original Assignee: SAND Technology, Inc.
• Inventors: McCool, Michael W., Kurman, Scott J.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Ellis, Kevin L.
• Application Number:
  US08/565,862
• Time in Patent Office: 1,075 Days
• Field of Search: 395/497.01, 395/497.02, 395/497.03, 395/497.04, 395/621, 395/416, 395/417, 395/418
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems

Abstract

An embodiment of the present invention is a memory management system. A storage device is organized into at least one file comprising numbered data frames of stored data for swapping into a memory. Each frame contains storage blocks of space. A memory is connected to the storage device and comprises a cache comprising numbered pages for storing swapped frames and a page list heads list comprising at least one list head entry. Each numbered page contains data frames that contain memory blocks for data storage or header frames that contain frame meta data. Each such list head entry stores a page number identifying a first of the numbered pages that contains free memory blocks of a given block size. A processor is connected to the memory and comprises means for allocating the one memory block responsive to a memory request by looking up the numbered page identified by the page number stored in the one list head entry.

Claims

1. A memory management system for a memory, the memory manager system and memory comprising:

a storage device organized into at least one file comprising frames of stored data for swapping into the memory;

the memory comprising numbered pages for storing swapped frames of the stored data from the storage device,

a page list heads list comprising list head entries, each said list head entry identifying the numbered page containing free memory blocks of storage space, at least one of said list head entries storing a page number identifying one of the numbered pages that contains one of the free memory blocks, and

a blocks list for each frame comprising at least one blocksize entry, each such blocksize entry containing a count of frames in the storage device that contain available storage space of a given size; and

a processor comprising

means using the page number stored in the at least one list head entry for allocating the memory blocks responsive to a memory request, and

means using the blocks list for allocating available storage space responsive to the memory request.

2. A memory management system according to claim 1, wherein the memory further comprises a page list for each numbered page comprising at least one page entry, each such page entry storing a page number identifying another of the numbered pages that contains another of the free memory blocks, the processor further comprising means for replacing at least one list head entry with a page number from one said page list.

3. A method for allocating requested memory blocks in a system comprising a storage device organized into at least one file comprising data frames of stored data for swapping into a memory,

the memory comprising

numbered pages for storing swapped frames of the stored data from the storage device,

a page list heads list comprising at least one list head entry, each said entry identifying one of said numbered pages that has free memory blocks of a predetermined block size, each entry storing a page number corresponding to one of the numbered pages in the memory containing a data frame from the storage device having a free memory block of the predetermined block size,

and a blocks list for each data frame comprising at least one blocksize entry, each such blocksize entry containing a count of data frames in the storage device that contain available storage space of a given block size,

the method comprising the steps of:

allocating the requested memory blocks from the memory using the page number stored in the at least one list entry in response to a memory request; and

when said previous allocating step is not successful, allocating the requested memory blocks from the available storage space in the storage device using the blocks list in response to a memory request.

4. The method of claim 3 wherein the memory further comprises a page list for each numbered page comprising at least one page entry, each such page entry storing a page number identifying another of the numbered pages that identifies another of the free memory blocks, the method comprising replacing at least one list head entry with a page number from one said page list.

5. A method using a computer for managing a memory organized into a plurality of layers, comprising:

generating a memory request for a fixed amount of memory in a service layer responsive to an application program;

receiving, in a memory manager layer, the memory request, the memory manager layer comprising a cache containing a plurality of pages for storing frames of data;

scanning at least one page list for a page entry, the page list containing a plurality of page entries, each page entry identifying one of the plurality of pages having a free memory block;

scanning a disk block list for a non-zero frame count, the disk block list containing a count of frames not contained in the cache having a free memory block of a given size; and

allocating free space by locating a block of free space in a memory-resident data frame at least as large as the fixed amount of memory in constant time and returning an in-memory address for the located block to the service layer.

6. A method according to claim 5, further comprising scanning a list of frame headers for a frame having a free memory block at least as large as the fixed amount of memory, each such frame header comprising an availability bitmap indicating that the corresponding frame has at least one free memory block.

7. A method according to claim 6 further comprising performing a comparison operation on the availability bitmap to determine whether a memory block at least as large as the fixed size is free in the corresponding frame.

8. A method using a computer for allocating a memory block having a requested size in constant time, the computer comprising a cache comprising numbered pages for storing swapped frames of stored data and a page list heads list comprising at least one list head entry, each numbered page containing memory blocks for data storage, each such list head entry storing a page number identifying the first of the numbered pages that contains one of the free memory blocks, each frame comprising storage blocks of storage space, comprising the steps of:

scanning the page list heads list responsive to a memory request to obtain from the one list head entry that stores a page number matching the first numbered page that contains the one memory block having free storage space at least as large as the requested size;

determining a memory block offset for the one memory block relative to the beginning of the frame;

maintaining a disk block list for each frame comprising at least one count entry, each such count entry containing a count of frames that contain available storage blocks of a given block size;

performing at least one of the steps of allocating or deallocating the one memory block by updating the page list heads list;

examining the disk block list after the step of allocating when none of the frames in memory have free space; and

allocating one of the storage blocks responsive to the memory request.

9. A method according to claim 8, further comprising the steps of:

maintaining a page list for each numbered page comprising at least one page entry, each such page entry storing a page number identifying another of the numbered pages that contains another of the free memory blocks; and

updating the page list heads list after the step of allocating or deallocating by replacing the page number stored in the one list head entry with the page number stored in the one page entry.

10. A method according to claim 8, wherein each of the memory blocks has a proportionate size and the page list heads list is organized according to the proportionate sizes.

11. A method using a computer for managing a partitioned memory, the computer comprising a memory connected to a storage device, comprising the steps of:

organizing the storage device into at least one file comprising numbered data frames of stored data for swapping into the memory, each frame in the at least one file comprising storage blocks of storage space;

partitioning the memory into a cache comprising numbered pages for storing swapped frames, each numbered page containing data frames that contain memory blocks of storage space;

forming a page list heads list comprising at least one list head entry, each such list head entry storing a page number identifying a first of the numbered pages that contains one of the free memory blocks of a given block size;

maintaining a disk block list for each frame comprising at least one count entry, each such count entry containing a count of frames that contain available storage blocks of a given block size;

allocating the one memory block responsive to a memory request by looking up the numbered page identified by the page number stored in the one list head entry;

examining the disk block list after the step of allocating when none of the memory blocks have free space; and

allocating one of the storage blocks responsive to the memory request.

12. A method according to claim 11, further comprising the steps of:

maintaining a page list for each numbered page comprising at least one page entry, each such page entry storing a page number identifying another of the numbered pages that contains another data frame that contains free memory blocks; and

updating the page list heads list after the step of allocating by replacing the page number stored in the one list head entry with the page number stored in the one page entry.

13. A method according to claim 11, wherein each of the memory blocks has a proportionate size and the page list heads list is organized according to the proportionate sizes.

14. A method using a computer for managing a memory, the computer comprising a storage means for storing a file comprising a plurality of frames and a cache connected to the storage means for storing frames swapped into the memory in pages, comprising the steps of:

updating a page list in the memory comprising a plurality of page entries, each such page entry containing a number identifying one of the pages that is storing a frame from the plurality of frames having free space of a given block size when a memory request is processed; and

updating a disk block list in the memory comprising a plurality of count entries, each such count entry containing a count of frames in the storage means that is storing a frame from the plurality of frames having free space of the given block size when a memory request is processed.

15. A method according to claim 14, further comprising the steps of:

receiving a memory request for freeing a fixed size of allocated space; and

deallocating the allocated space by adjusting at least one of the page list and disk block list.

16. A method according to claim 14, further comprising the steps of:

receiving a memory request for allocating a fixed amount of memory;

locating free space in the memory at least as large as the fixed size by examining the page list and the disk block list; and

allocating the free space by returning an address for the free space and adjusting at least one of the page list and disk block list.

17. A method according to claim 16, wherein each frame comprising a plurality of memory blocks having a predetermined size and the free space is a memory block, further comprising the steps of:

organizing the page list according to each predetermined size; and

organizing the disk block list according to each predetermined size.

18. A method according to claim 17, wherein each predetermined size is a power of two.

19. A method according to claim 16, wherein the step of locating further comprises the steps of:

scanning the page list when the memory request is not as large as a page; and

allocating a new frame when the memory request is at least as large as a page.

20. A method according to claim 19, further comprising the steps of:

scanning the disk block list when no page entry is found; and

allocating a new frame when no block entry is found.