Memory allocator for a multiprocessor computer system

• US 20040205304A1
• Filed: 04/30/2004
• Published: 10/14/2004
• Est. Priority Date: 08/29/1997
• Status: Active Grant

• Current Assignee: Brent A. Kingsbury, Paul E. McKenney, Phillip E. Krueger, Stuart A. Friedberg
• Original Assignee: Brent A. Kingsbury, Paul E. McKenney, Phillip E. Krueger, Stuart A. Friedberg
• Inventors: McKenney, Paul E., Kingsbury, Brent A., Friedberg, Stuart A., Krueger, Phillip E.
• Granted Patent: US 7,472,233 B2
• Time in Patent Office: Days
• US Class Current: 711/148
• 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 an operating system and having shared 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 allocate memory on a specified node;

in response to the request, allocating memory on the specified node; and

indicating an address for the allocated memory.

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 the 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 operating system function 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 operating system function 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 a request to allocate memory from a specified memory pool; and

allocating the memory includes allocating memory from the specified pool.

20. The method of claim 19 wherein receiving the request includes a request to delay allocating the memory until memory from the specified pool is available.

21. The method of claim 19 wherein receiving the request includes a request that allocating the memory indicate failure if memory from the specified pool is not available.

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

providing a pool of available memory blocks per processor;

if a first processor makes a memory allocation request for memory from the first processor'"'"'s pool, allocating the memory for the first processor without acquiring a lock on the pool; and

if a second processor makes a memory allocation request for memory from the first processor'"'"'s pool, allocating the memory for the second processor from the first processor'"'"'s pool after acquiring a lock on the pool.

23. The method of claim 22 wherein the shared memory is distributed shared memory.

24. In a multiprocessor system with shared memory, a data structure in memory for dynamically allocating memory among the multiple processors, comprising:

a first field for identifying memory blocks in a first processor'"'"'s memory pool available for allocation; and

a second field for identifying a lock for accessing the memory block identified in the first field;

the available memory blocks being accessible by the first processor without acquiring a lock in the second field and being accessible by a second processor only after acquiring a lock in the second field.

25. The method of claim 24 wherein the shared memory is distributed shared memory.

26-35. -35.