Memory allocator for a multiprocessor computer system

• US 7,472,233 B2
• Filed: 04/30/2004
• Issued: 12/30/2008
• Est. Priority Date: 08/29/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E., Kingsbury, Brent A., Friedberg, Stuart A., Krueger, Phillip E.
• Primary Examiner(s): Tsai; Sheng-Jen
• Application Number:
  US10/835,768
• Publication Number:
  US 20040205304A1
• Time in Patent Office: 1,705 Days
• Field of Search: 711/148, 711/170, 711/147, 711/153, 711/171
• US Class Current: 711/147
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

Methods for dynamically allocating memory in a multiprocessor computer system such as a non-uniform memory access (NUMA) machine having distributed shared memory. The methods include allocating memory by specified node, memory class, or memory pool in response to requests by the system (kernel memory allocation) or a user (application memory allocation). Through these methods memory is allocated more efficiently in a NUMA machine. For example, allocating memory on a specified node in a NUMA machine, such as the same node on which a process requiring the memory is running, reduces memory access time. Allocating memory from a specified memory class allows device drivers with restricted DMA ranges to operate with dynamically allocated memory. Other benefits of these methods include minimizing expensive remote-memory accesses using a distributed reference count mechanism and lock-free cache access.

Claims

1. In a multiprocessor system having shared physical memory distributed among a plurality of nodes, a method of dynamically allocating memory on a specified node of the system, the method comprising:

receiving a request to dynamically allocate an amount of physical memory on a specified node, the request received from a process;

in response to the request, dynamically allocating the amount of physical memory on the specified node; and

indicating an address for the dynamically allocated amount of physical memory, wherein;

receiving the request includes a request to allocate the amount of physical memory from a specified memory pool;

allocating the amount of physical memory includes allocating the amount of physical memory from the specified pool, and dynamically allocating the amount of physical memory on the specified node comprises;

assigning a first variable to represent a count of memory structures in the physical memory, the count of memory structures in the physical memory represented by the first variable corresponding to a global count of memory structures in the physical memory for the multiprocessor system as a whole;

assigning multiple second variables, each second variables to represent a count of memory structures in the memory, the count of memory structures in the physical memory represented by each multiple second variable corresponding to a local count of memory structures in the physical memory for one of the plurality of nodes;

determining dynamically changeable desired levels of value of the multiple second variables as based on a distance between a total value of the multiple second variables and a predetermined limit of the multiple second variables;

maintaining a third variable, the third variable having a first part that stores the dynamically changeable desired levels of value of the multiple second variables, the third variable having a second part that stores the predetermined limit of the multiple second variables, and the third variable having a third part storing a leftover value of the multiple second variables, the leftover value being no less than one;

determining whether a selected second variable of the multiple second variables can be changed by the requested amount and stay within the dynamically changeable desired levels of value of the multiple second variables based on the total value of the multiple second variables and based on the predetermined limit of the multiple second variables as stored in the second part of the third variable;

if so, changing the selected second variable by the requested amount; and

if not, changing the first variable by the requested amount.

2. The method of claim 1 wherein the memory being allocated is within the address space of the operating system.

3. The method of claim 1 wherein:

receiving the request comprises receiving a call from a processor, the call including arguments specifying the size of memory and node specified;

allocating the memory comprises executing a function called by the call; and

indicating the address comprises returning a value to the source of the call.

4. The method of claim 1 wherein receiving the request comprises receiving a call from a processor, the call including arguments specifying the size of memory and node specified, and allocating the memory comprises:

selecting a data structure for the node specified, the data structure providing access to memory blocks on the specified node of the memory size specified; and

taking an available memory block from the blocks accessible through the data structure.

5. The method of claim 4 wherein selecting the data structure comprises:

determining if the node specified is the same node on which the processor that made the call is located;

if not, selecting a first data structure that provides access to memory blocks made available by the specified node to the node on which the processor is located;

if so, selecting a second data structure that provides access to memory blocks available to the processor.

6. The method of claim 4 wherein selecting the data structure comprises:

determining which of a number of memory block sizes corresponds to the memory size request; and

selecting a data structure that provides access to memory blocks of a size corresponding to the memory size request.

7. The method of claim 1 wherein the node request is encoded into a multi-bit flags argument of a memory allocation function call for interpretation by a function, the function call and flags argument being of a same format as the format of a pre-existing memory allocation function call but using one or more previously-unused bits of the flags argument to indicate the specified node, whereby the memory allocation function call is compatible with the pre-existing function call.

8. The method of claim 7 wherein, if the bits for making the node request are set to a default value in the multi-bit flags argument, the request defaults to the node on which a processor making the request is located and, if memory is not available on this node, then to another node where memory is available.

9. The method of claim 1 wherein:

receiving the request includes receiving a request that memory be allocated on any other system node if memory is not immediately available on the specified node; and

allocating the memory includes allocating memory on another system node if memory is not immediately available on the specified node.

10. The method of claim 1 wherein receiving the request includes a request to delay allocating the memory until memory is available on the specified node.

11. The method of claim 1 wherein receiving the request includes a request that allocating the memory indicate failure if memory is not available on the specified node.

12. The method of claim 1 wherein:

receiving the request includes a request to allocate memory from a specified memory class; and

allocating the memory includes allocating memory from the specified class.

13. The method of claim 12 wherein the memory class request is encoded into a multi-bit flags argument of a memory allocation function call for interpretation by a function, the function call and flags argument being of a same format as the format of a pre-existing memory allocation function call but using one or more previously unused bits of the flags argument to indicate the specified memory class, whereby the memory allocation function call is compatible with the pre-existing function call.

14. The method of claim 13 wherein, if the bits for making the memory class request are set to a default value in the multi-bit flags argument, the request defaults to a particular class of memory and, if memory is not available in this class, then to another class for which memory is available.

15. The method of claim 12 wherein the specified memory class is memory accessible by way of direct memory access (DMA) by a particular device.

16. The method of claim 12 wherein:

receiving the request includes a request that memory be allocated from another memory class if memory from the specified memory class is not available; and

allocating the memory includes allocating memory from another memory class if memory from the specified memory class is not available.

17. The method of claim 12 wherein receiving the request includes a request to delay allocating the memory until memory from the specified class is available.

18. The method of claim 12 wherein receiving the request includes a request that allocating the memory indicate failure if memory from the specified class is not available.

19. The method of claim 1 wherein receiving the request includes one or more of:

a request to delay allocating the memory until memory from the specified pool is available, and a request that allocating the memory indicate failure if memory from the specified pool is not available.

20. In a multiprocessor system with shared physical memory, the a method of dynamically allocating physical memory among the multiple processors, the method comprising:

providing a pool of available physical memory blocks per processor;

in response to a first processor makes a physical memory allocation request for an amount of physical memory from the first processor'"'"'s pool, dynamically allocating the amount of physical memory for the first processor without acquiring a lock on the pool; and

in response to a second processor makes a physical memory allocation request for an amount of physical memory from the first processor'"'"'s pool, dynamically allocating the amount of physical memory for the second processor from the first processor'"'"'s pool after acquiring a lock on the pool;

wherein dynamically allocating the amount of physical memory comprises;

assigning a first variable to represent a count of memory structures in the physical memory, the count of memory structures in the physical memory represented by the first variable corresponding to a global count of memory structures in the physical memory for the multiprocessor system as a whole;

assigning multiple second variables, each second variables to represent a count of memory structures in the memory, the count of memory structures in the physical memory represented by each multiple second variable corresponding to a local count of memory structures in the physical memory for one of the plurality of nodes;

determining dynamically changeable desired levels of value of the multiple second variables as based on a distance between a total value of the multiple second variables and a predetermined limit of the multiple second variables;

maintaining a third variable, the third variable having a first part that stores the dynamically changeable desired levels of value of the multiple second variables, the third variable having a second part that stores the predetermined limit of the multiple second variables, and the third variable having a third part storing a leftover value of the multiple second variables, the leftover value being no less than one;

determining whether a selected second variable of the multiple second variables can be changed by the requested amount and stay within the dynamically changeable desired levels of value of the multiple second variables based on the total value of the multiple second variables and based on the predetermined limit of the multiple second variables as stored in the second part of the third variable;

if so, changing the selected second variable by the requested amount; and

if not, changing the first variable by the requested amount.

21. The method of claim 20 wherein the shared memory is distributed shared memory.