Method, apparatus, and computer-readable medium for providing physical memory management functions

• US 7,809,918 B1
• Filed: 07/22/2005
• Issued: 10/05/2010
• Est. Priority Date: 07/22/2005
• Status: Active Grant

• Current Assignee: American Megatrends International, LLC
• Original Assignee: American Megatrends Incorporated
• Inventors: Samuel, Balasingh
• Primary Examiner(s): Tsai; Sheng-Jen
• Assistant Examiner(s): Chrzanowski; Matthew R
• Application Number:
  US11/187,425
• Time in Patent Office: 1,901 Days
• Field of Search: 711/171
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

A method, apparatus, and computer-readable medium for providing memory management functions are provided. According to one method, a memory allocation process is exposed that receives a requested memory size with a memory allocation request and returns a pointer to an area of allocated memory of the requested memory size if available. A memory deallocation process is also exposed that receives requests to deallocate previously allocated memory regions in the form of a pointer to the memory region to be deallocated. The allocation and deallocation processes maintain a list of linked lists, each of the linked lists describing an unallocated portion of the memory. Only a single linked list must be updated by the allocation process. The deallocation process adds a new linked list and rebuilds the list of linked lists to merge any linked lists corresponding to adjacent portions of memory.

Claims

1. A computer-implemented method for providing physical memory management functions to programs executing in a pre-boot environment, the method comprising:

receiving an allocation request from a program executing in the pre-boot environment for allocating a portion of a physical computer memory, wherein the allocation request identifies a requested memory size, wherein the memory management functions are configured to maintain a single list of data structures describing the physical computer memory, the list of data structures comprising a first data structure describing a first area of the physical computer memory that is available for allocation, the first area comprising a first memory portion and a second memory portion contiguous to the first memory portion, the first data structure comprising a first pointer node, a first size node, and a first next node, the first pointer node referencing a beginning of the first memory portion of the physical computer memory, the first size node describing a combined memory size of the first memory portion and the second memory portion, the first next node referencing a null value, and wherein each and every data structure in the list of data structures describes an unallocated portion of the physical computer memory;

in response to receiving the allocation request, determining whether the requested memory size is available for allocation;

in response to determining that the requested memory size is available for allocation through the first memory portion, (i) allocating the first memory portion, (ii) updating the first pointer node from referencing the beginning of the first memory portion to referencing a beginning of the second memory portion, (iii) updating the first size node from describing the combined memory size of the first memory portion and the second memory portion to describing a memory size of the second memory portion, and (iv) returning a pointer to the first memory portion in response to the allocation request;

receiving a request to deallocate a second area of the physical computer memory that has been allocated, the request comprising a pointer to the second area of the physical computer memory to be deallocated; and

in response to receiving the deallocation request, determining the size of the second area, determining whether the second area was allocated by the memory management functions, and in response to determining that the second area was allocated by the memory management functions, (i) deallocating the second area, (ii) creating a second data structure describing the second area, and (iii) updating the first next node from referencing the null value to referencing the second data structure, the second data structure comprising a second pointer node, a second size node, and a second next node, the second pointer node referencing a beginning of the second area, the second size node describing a memory size of the second area, and the second next node referencing the null value.

2. The method of claim 1, wherein each data structure in the list of data structures comprises

a first pointer stored in a corresponding pointer node, the first pointer configured to point to the start of an unallocated portion of the physical computer memory,

data stored in a corresponding size node identifying the size of the unallocated portion of the physical computer memory, and

a second pointer stored in a corresponding next node that points to a next data structure in the list of data structures.

3. The method of claim 2, wherein determining whether the requested memory size is available for allocation comprises scanning the list of data structures to identify a data structure corresponding to an unallocated portion of the physical computer memory equal to or larger than the requested memory size;

and in response to determining that the requested memory size is not available, returning an error.

4. The method of claim 3, wherein updating the data structure describing the unallocated portion of the physical computer memory to describe the unallocated portion of memory after the allocation of the requested memory comprises updating the first pointer stored in the identified data structure to reflect a new start of the unallocated portion of the physical computer memory and updating the data identifying the size of the unallocated portion in the identified data structure by reducing the size of the unallocated portion by the requested memory size.

5. The method of claim 1, further comprising in response to determining that the requested memory size is available for allocation:

writing data identifying the size of the allocated memory to a location adjacent to the allocated memory; and

writing a unique digital signature comprising a verifiable unique string of characters to a location adjacent to the allocated memory.

6. The method of claim 5, wherein determining the size of the portion of the memory to be deallocated comprises reading the data identifying the size of the allocated memory from the portion of the memory identified by the pointer received with the deallocation request.

7. The method of claim 5, wherein determining whether the portion of the memory to be deallocated corresponds to a portion of the memory allocated by the memory management functions comprises reading and verifying the unique digital signature from the portion of the memory identified by the pointer received with the deallocation request.

8. A computer storage medium having computer-readable instructions stored thereon which, when executed by a computer in a pre-boot environment, cause the computer to:

receive an allocation request from a program executing in the pre-boot environment for allocating a portion of a physical computer memory, wherein the allocation request identifies a requested memory size, wherein the memory management functions are configured to maintain a single list of data structures describing the physical computer memory, the list of data structures comprising a first data structure describing a first area of the physical computer memory that is available for allocation, the first area comprising a first memory portion and a second memory portion contiguous to the first memory portion, the first data structure comprising a first pointer node, a first size node, and a first next node, the first pointer node referencing a beginning of the first memory portion of the physical computer memory, the first size node describing a combined memory size of the first memory portion and the second memory portion, the first next node referencing a null value, and wherein each and every data structure in the list of data structures describes an unallocated portion of the physical computer memory;

in response to receiving the allocation request, determining whether the requested memory size is available for allocation;

in response to determining that the requested memory size is available for allocation through the first memory portion, (i) allocating the first memory portion, (ii) updating the first pointer node from referencing the beginning of the first memory portion to referencing a beginning of the second memory portion, (iii) updating the first size node from describing the combined memory size of the first memory portion and the second memory portion to describing a memory size of the second memory portion, and (iv) returning a pointer to first memory portion in response to the allocation request;

receive a request to deallocate a second area of the physical computer memory that has been allocated, the request comprising a pointer to the second area of the physical computer memory to be deallocated; and

in response to receiving the deallocation request, determine the size of the second area, determining whether second area was allocated by the memory management functions, and

in response to determining that the second area was allocated by the memory management functions, (i) deallocate the second area, (ii) create a second data structure describing the second area, and (iii) update the first next node from referencing the null value to referencing the second data structure, the second data structure comprising a second pointer node, a second size node, and a second next node, the second pointer node referencing a beginning of the second area, the second size node describing a memory size of the second area, and the second next node referencing the null value.

9. The computer storage medium of claim 8, wherein the computer-readable instructions are part of a Basic Input/Output System (“

BIOS”

) of the computer.

10. An apparatus capable of managing the allocation of memory in a pre-boot environment of a computer, comprising:

a processor;

a memory area operatively connected to the processor;

a firmware operatively connected to the processor; and

one or more Basic Input/Output System (“

BIOS”

) routines contained in the firmware and configured to

receive an allocation request from a program executing in the pre-boot environment for allocating a portion of a physical computer memory, wherein the allocation request identifies a requested memory size, wherein the memory management functions are configured to maintain a single list of data structures describing the physical computer memory, the list of data structures comprising a first data structure describing a first area of the physical computer memory that is available for allocation, the first area comprising a first memory portion and a second memory portion contiguous to the first memory portion, the first data structure comprising a first pointer node, a first size node, and a first next node, the first pointer node referencing a beginning of the first memory portion of the physical computer memory, the first size node describing a combined memory size of the first memory portion and the second memory portion, the first next node referencing a null value, and wherein each and every data structure in the list of data structures describes an unallocated portion of the physical computer memory;

in response to receiving the allocation request, determining whether the requested memory size is available for allocation;

in response to determining that the requested memory size is available for allocation through the first memory portion, (i) allocating the first memory portion, (ii) updating the first pointer node from referencing the beginning of the first memory portion to referencing a beginning of the second memory portion, (iii) updating the first size node from describing the combined memory size of the first memory portion and the second memory portion to describing a memory size of the second memory portion, and (iv) returning a pointer to first memory portion in response to the allocation request;

receive a request to deallocate a second area of the physical computer memory that has been allocated, the request comprising a pointer to the second area of the physical computer memory to be deallocated; and

in response to receiving the deallocation request, determine the size of the second area, determining whether second area was allocated by the memory management functions, and

in response to determining that the second area was allocated by the memory management functions, (i) deallocate the second area, (ii) create a second data structure describing the second area, and (iii) update the first next node from referencing the null value to referencing the second data structure, the second data structure comprising a second pointer node, a second size node, and a second next node, the second pointer node referencing a beginning of the second area, the second size node describing a memory size of the second area, and the second next node referencing the null value.

11. The apparatus of claim 10, wherein determining whether the portion of the memory area to be deallocated corresponds to a portion of the memory allocated by the BIOS routines comprises reading and verifying a unique digital signature comprising a unique string of characters from the portion of the memory area identified by the pointer received with the request.