US 6,182,089 B2 · Method, system and computer program product for dynamically allocating large memory pages of different sizes

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.

Claims21

Dependent claims

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.

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 more elements

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.

10 more elements

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.

4 more elements

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.

11 more elements

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.

10 more elements

Dependencies are inferred from the claim text.

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

Life of this patent

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

Life of this patent

Abstract

Claims21