Method, system and computer program product for dynamically allocating large memory pages of different sizes

• US 6,182,089 B1
• Filed: 09/23/1997
• Issued: 01/30/2001
• Est. Priority Date: 09/23/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Schimmel, Curt F., Stevens, Luis F., Ganapathy, Narayanan
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/935,820
• Time in Patent Office: 1,225 Days
• Field of Search: 707/206
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 2212/652 Page size control
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method, system and computer program product for dynamically allocating large memory pages of different sizes. Each process can select multiple page sizes. An algorithm referred to as a “Coalescing Daemon” is used to allocate large pages. “High water marks” are specified to the operating system. A high water mark is the maximum percentage of total system memory that the Coalescing Daemon coalesces for a given page size. The high water marks are used to allocate a number of free memory pages for each specified page size. Separate freelists are created and maintained for each page size. Each freelist comprises a linked list of data structures that represent free physical memory pages. A bitmap is set-up by the operating system to represent all memory available to processes. The bitmap is used for determining which memory pages are free during coalescing. The Coalescing Daemon allocates memory pages using a weak, mild and strong coalescing policy. The weak policy is performed first, followed by the mild and the strong policies. The mild and strong policies are performed only if the preceding policy or policies fail. The weak policy searches the bitmap for free contiguous areas of memory and inserts an entry into the associated freelist if found. If the weak policy is unsuccessful, the mild policy attempts to find a suitable chunk of memory which is used to create a contiguous chunk of free memory by migrating busy base pages to other areas. The mild coalescing policy searches the bitmap for a chunk of memory in which the set bits (i.e. the free base pages) are above a tunable predetermined threshold value. Thus, a limited amout of migration is performed according to predetermined threshold. If the mild coalescing policy fails the strong coalescing policy is performed. In the strong coalescing policy, base pages are migrated to create a free chunk, regardless of a threshold amount.

Claims

1. A method for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, said method comprising the steps of:

specifying a plurality of high water marks, wherein each of the high water marks defines a threshold amount for large pages of a given page size; and

coalescing the portion of memory for a large memory page of a large page size when the number of memory pages of the large page size is less than the threshold amount for the large page size.

2. A system for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, said system comprising:

a specifier that specifies a plurality of high water marks, wherein each of the high water marks defines a threshold amount for large pages of a given page size; and

a coalescer that coalesces the portion of memory for a large memory page of a large page size when the number of memory pages of the large page size is less than the threshold amount for the large page size.

3. A method for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, said method comprising the steps of:

creating an empty set of freelists for representing free memory pages, each freelist corresponding to a particular predetermined page size, and each freelist corresponding to a progressively larger page size beginning with the base page size and ending with the largest page size;

searching the portion of memory for free memory pages of the base page size;

inserting a freelist entry into the freelist corresponding to the base page size for each free memory page found in said searching step;

specifying a plurality of high water marks, wherein each of the high water marks defines a threshold amount for large pages of a given page size;

coalescing the portion of memory for a large memory page of a large page size when the number of memory pages of the large page size is less than the threshold amount for the large page size; and

updating said set of freelists by adding an entry to the freelist corresponding to the large memory page and deleting associated multiple entries from the freelist corresponding to the base page size, if a free large memory page is coalesced in said coalescing step.

4. The method of claim 3, further comprising the steps of:

creating a bitmap comprising at least one bit for each base page size segment in the portion of memory; and

dynamically maintaining bits in the bitmap to represent base pages that are free and base pages that are busy.

5. The method of claim 4, wherein said searching step is performed by searching said bitmap for free base sized pages.

6. The method of claim 4, wherein said coalescing step includes searching said bitmap for a chunk of memory beginning at a boundary aligned with the large memory page, wherein the chunk comprises a plurality of free contiguous base pages that in aggregate, are equal in size to said large memory page.

7. The method of claim 4, wherein said coalescing step includes searching said bitmap for a chunk of memory beginning at a boundary aligned with said large memory page, said chunk equal in size to said large memory page and comprises a number of free base pages above a predetermined threshold value and further comprises busy base pages that are all migratable;

and

migrating the busy base pages to an area in the portion of memory outside of said chunk.

8. The method of claim 4, wherein said coalescing step includes searching said bitmap for a chunk of memory beginning at a boundary aligned with said large memory page, said chunk equal in size to said large memory page and comprises busy base pages that are all migratable;

migrating the busy base pages to an area within the portion of memory outside of the chunk.

9. The method of claim 4, wherein said coalescing step includes the steps of:

searching the bitmap for a free chunk of memory beginning at a boundary aligned with the large memory page, wherein the free chunk comprises a plurality of free contiguous base pages that in aggregate, are equal in size to the large memory page;

if the free chunk is not found, searching the bitmap for a mildly busy chunk of memory beginning at a boundary aligned with the large memory page; and

if the free chunk and the mildly busy chunk are not found, searching the bitmap for any chunk of memory, beginning at a boundary aligned with the large memory page and having a size equal to the large memory page and comprising busy base pages that are all migratable; and

migrating the busy pages to an area in the portion of memory outside of a found chunk if either the mildly busy chunk or the any chunk is found;

wherein the mildly busy chunk is equal in size to the large memory page, and comprises a number of free base pages above a predetermined threshold value, and further comprises busy base pages that are all migratable.

10. The method of claim 4, wherein the computer system is a multi-node computer system comprising a plurality of nodes;

wherein each freelist further corresponds to a particular page size at one the plurality of nodes; and

wherein the bitmap further comprises a separate bitmap for each of the plurality of nodes.

11. The method of claim 3 further comprising the step of:

responding to a page free request by searching an area in the portion of memory associated with the page free request for chunks of memory suitable as an undiscovered free large memory page, and by automatically coalescing the undiscovered free large memory page in response to the page free request;

whereby said responding step saves the necessity of separately performing said coalescing step for the undiscovered free large memory page.

12. A method for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, said method comprising the steps of:

maintaining a set of freelists, each freelist associated with a particular page size and comprising zero or more entries therein, each entry representing a free physical memory page of the particular page size;

receiving a memory allocation request for a memory page of a large page size from a process;

determining if a current entry exists in the freelist associated with the large page size;

allocating, to the process, the free physical memory page associated with the current entry, if the current entry exists;

searching for a larger entry in the freelist associated with a next larger page size, if the current entry does not exist;

splitting the larger entry, if the larger entry is found in said searching step, said splitting step comprising the steps of

(a) removing the larger entry from the freelist searched in said searching step as a selected entry,

(b) inserting an appropriate amount of entries in a freelist corresponding to a next lower page size of the selected entry,

(c) determining whether the next lower page size is the large page size,

(d) if said determining step determines the next lower pape size is not the large page size, then choosing one of the appropriate amount of entries as the selected entry and removing the selected entry from the freelist corresponding to a next lower page size, and

(e) repeating said steps (b), (c), and (d) until a freelist associated with the large page size is referenced in said inserting step; and

repeating said searching and splitting steps until a freelist of the largest page size is searched or the larger entry is found in said searching step.

13. The method of claim 12, wherein the computer system is a multi-node computer system comprising a plurality of nodes, and wherein each freelist further corresponds to a particular page size at one the plurality of nodes.

14. A system for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, said system comprising:

a freelist creator that creates an empty set of freelists for representing free memory pages, each freelist corresponding to a particular predetermined page size, and each freelist corresponding to a progressively larger page size beginning with the base page size and ending with the largest page size;

a searcher that searches the portion of memory for free memory pages of the base page size;

an inserter that inserts a freelist entry into the freelist corresponding to the base page size for each free memory page found by said searcher;

a specifier that specifies a plurality of high water marks, wherein each of the high water marks defines a threshold amount for large pages of a given page size;

a coalescer that coalesces the portion of memory for a large memory page of a large page size when the number of memory pages of the large page size is less than the threshold amount for the large page size; and

an updater that updates the set of freelists by adding an entry to a freelist corresponding to the large memory page and deleting associated multiple entries from a freelist corresponding to the base page size, if a free large memory page is coalesced by said coalescer.

15. The system of claim 14, further comprising:

a bitmap creator that creates a bitmap comprising at least one bit for each base page size segment in the portion of memory; and

a maintainer that dynamically maintains bits in the bitmap to represent base pages that are free and base pages that are busy.

16. A system for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, said system comprising:

a maintainer that maintains a set of freelists, each freelist associated with a particular page size and comprising zero or more entries therein, each entry representing a free physical memory page of the particular page size;

a receiver that receives a memory allocation request for a memory page of a large page size from a process;

a determiner that determines if a current entry exists in the freelist associated with the large page size;

an allocator that allocates, to the process, the free physical memory page associated with the current entry, if the current entry exists;

a searcher that searches for a larger entry in the freelist associated with a next larger page size, if the current entry does not exist;

a splitter that splits the larger entry, if the larger entry is found by said searcher, said splitter comprising

(a) a remover that removes the larger entry from the freelist searched by said searcher as a selected entry,

(a) an inserter that inserts an appropriate amount of entries in a freelist corresponding to a next lower page size of the selected entry,

(c) a determiner that determines whether the next lower page size is the large page size,

(d) a remover that, if said determiner determines the next lower page size is not the large page size, chooses one of the appropriate amount of entries as the selected entry and removes the selected entry from the freelist corresponding to a next lower pape size, and

(e) a first repeater that invokes said elements (b), (c), and (d) until a freelist associated with the large page size is referenced by said inserter; and

a second repeater that invokes said searcher and said splitter until a freelist of the largest page size is searched or the larger entry is found by said searcher.

17. A computer program product comprising a computer useable medium having computer program logic stored therein, said computer program logic for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, wherein said computer program logic comprises:

a freelist creator that enables the computer to create an empty set of freelists for representing free memory pages, each freelist corresponding to a particular predetermined page size, and each freelist corresponding to a progressively larger page size beginning with the base page size and ending with the largest page size;

a searcher that enables the computer to search the portion of memory for free memory pages of the base page size;

an inserter that enables the computer to insert a freelist entry into the freelist corresponding to the base page size for each free memory page found by said searcher;

a specifier that enables the computer to specify a plurality of high water marks, wherein each of the high water marks defines a threshold amount for large pages of a given page size;

a coalescer that enables the computer to coalesce the portion of memory for a large memory page of a large page size when the number of memory papes of the large page size is less than the threshold amount for the large page size; and

an updater that enables the computer to update said set of freelists by adding an entry to a freelist corresponding to the large memory page and deleting associated multiple entries from a freelist corresponding to the base page size, if a free large memory page is coalesced by said coalescer.

18. The computer program product of claim 17, further comprising:

a bitmap creator that enables the computer to create a bitmap comprising at least one bit for each base page size segment in the portion of memory; and

a maintainer that enables the computer to dynamically maintain bits in the bitmap to represent base pages that are free and base pages that are busy.

19. A computer program product comprising a computer useable medium having computer program logic stored therein, said computer program logic for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, wherein said computer program logic comprises:

a maintainer that enables the computer to maintain a set of freelists, each freelist associated with a particular page size and comprising zero or more entries therein, each entry representing a free physical memory page of the particular page size;

a receiver that enables the computer to receive a memory allocation request for a memory page of a large page size from a process;

a determiner that enables the computer to determine if a current entry exists in the freelist associated with the large page size;

an allocator that enables the computer to allocate, to the process, the free physical memory page associated with the current entry, if the current entry exists;

a searcher that enables the computer to search for a larger entry in the freelist associated with a next larger page size, if the current entry does not exist; and

a splitter that enables the computer to split the larger entry, if the larger entry is found by said searcher, said splitter comprising

(a) a remover that removes the larger entry from the freelist searched by said searcher as a selected entry,

(b) an inserter that inserts an appropriate amount of entries in a freelist corresponding to a next lower page size of the selected entry,

(c) a determiner that determines whether the next lower page size is the large page size,

(d) a remover that, if said determiner determines the next lower page size is not the large page size, chooses one of the anpropriate amount of entries as the selected entry and removes the selected entry from the freelist corresponding to a next lower page size, and

(e) a first repeater that invokes said elements (b), (c), and (d) until a freelist associated with the large page size is referenced by said inserter; and

a second repeater that enables the computer to invoke said searcher and said splitter until a freelist of the largest page size is searched or said larger entry is found by said searcher.

20. A system for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, said system comprising:

means for creating an empty set of freelists for representing free memory pages, each freelist corresponding to a particular predetermined page size, and each freelist corresponding to a progressively larger page size beginning with the base page size and ending with the largest page size;

means for searching the portion of memory for free memory pages of the base page size;

means for inserting a freelist entry into the freelist corresponding to the base page size for each free memory page found by said searching means;

means for specifying a plurality of high water marks, wherein each of the high water marks defines a threshold amount for large pages of a given page size;

means for coalescing the portion of memory for a large memory page of a large page size when the number of memory pages of the large page size is less than the threshold amount for the large page size; and

means for updating the set of freelists by adding an entry to a freelist corresponding to the large memory page and deleting associated multiple entries from a freelist corresponding to the base page size, if a free large memory page is coalesced by said coalescing means.

21. A system for dynamically allocating memory pages in a portion of memory within a computer system, said memory pages being of various page sizes from a base page size to a largest page size, said system comprising:

means for maintaining a set of freelists, each freelist associated with a particular page size and comprising zero or more entries therein, each entry representing a free physical memory page of the particular page size;

means for receiving a memory allocation request for a memory page of a large page size from a process;

means for determining if a current entry exists in the freelist associated with the large page size;

means for allocating, to the process, the free physical memory page associated with the current entry, if the current entry exists;

means for searching for a larger entry in the freelist associated with a next larger page size, if the current entry does not exist;

means for splitting the larger entry, if the larger entry is found by said searching means, said splitting means comprising

(a) means for removing the larger entry from the freelist searched by said searching means as a selected entry,

(b) means for inserting an appropriate amount of entries in a freelist corresponding to a next lower page size of the selected entry,

(c) means for determining whether the next lower page size is the large page size,

(d) if said determining means determines the next lower page size is not the large page size, means for choosing one of the appropriate amount of entries as the selected entry and means for removing the selected entry from the freelist corresponding to a next lower page size, and

(e) a first repeating means that invokes said elements (b), (c), and (d) until a freelist associated with the large page size is referenced by said inserting means; and

a second repeating means that invokes said searching and said splitting until a freelist of the largest page size is searched or the larger entry is found by said searching means.