Parallel Dynamic Memory Allocation Using A Lock-Free FIFO

• US 20130198480A1
• Filed: 01/30/2012
• Published: 08/01/2013
• Est. Priority Date: 01/30/2012
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: Stephen Jones
• Inventors: JONES, Stephen, Huang, Xiaohuang
• Granted Patent: US 9,542,227 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2205/064 Linked list, i.e. structure using pointers, e.g. allowing non-contiguous address segments in one logical buffer or dynamic buffer space allocation
• CPC Class Codes: G06F 2209/5011 Pool
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

One embodiment of the present invention sets forth a technique for dynamically allocating memory using one or more lock-free FIFOs. One or more lock-free FIFOs are populated with FIFO nodes, where each FIFO node represents a memory allocation of a predetermined size. Each particular lock-free FIFO includes memory allocations of a single size. Different lock-free FIFOs may include memory allocations for different sizes to service allocation requests for different size memory allocations. A lock-free mechanism is used to pop FIFO nodes from the FIFO. The use of the lock-free FIFO allows multiple consumers to simultaneously attempt to pop the head FIFO node without first obtaining a lock to ensure exclusive access of the FIFO.

Claims

1. A method of allocating memory, the method comprising:

receiving a memory allocation request specifying an amount of memory;

identifying first-in first-out sub-system (FIFO) node size based on the amount of memory;

selecting a first FIFO that is populated with FIFO nodes of the FIFO node size; and

popping a FIFO head node from the first FIFO to satisfy the memory allocation request.

2. The method of claim 1, further comprising:

creating the first FIFO including a head pointer value; and

populating the first FIFO with the FIFO nodes configured in a linked list, wherein each FIFO node includes a next value that indicates a next FIFO node in the linked list.

3. The method of claim 1, further comprising:

receiving a second memory allocation request;

determining that the second memory request is rejected by the first FIFO;

selecting a second FIFO; and

popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

4. The method of claim 3, further comprising indicating that the first FIFO is unavailable for allocations.

5. The method of claim 4, wherein the first FIFO is empty.

6. The method of claim 1, further comprising:

receiving a second memory allocation request;

determining that the second memory request is rejected by the first FIFO;

creating a second FIFO;

populating the second FIFO with FIFO nodes of the FIFO node size, wherein the FIFO nodes are configured in a linked list and each FIFO node includes a next value that indicates a next FIFO node in the linked list; and

popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

7. The method of claim 1, further comprising:

receiving a second memory allocation request specifying a second amount of memory;

determining that the FIFO node size is smaller than the second amount of memory;

creating a second FIFO;

populating the second FIFO with second FIFO nodes of a second FIFO node size that is greater than the FIFO node size; and

popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

8. The method of claim 1, wherein the FIFO nodes represent portions of sequential memory and the FIFO nodes are configured in a linked list in an order of the portions of sequential memory.

9. The method of claim 1, further comprising combining a first memory allocation request from a first thread with a second memory allocation request from a second thread to generate the memory allocation request.

10. The method of claim 1, further comprising:

determining that all the FIFO nodes that populate the first FIFO are freed;

retiring the first FIFO; and

releasing a quantity of memory corresponding to the FIFO nodes.

11. A computing system, comprising:

a memory heap;

a first first-in first-out sub-system (FIFO) that is populated with FIFO nodes that each represent a portion of memory from the memory heap; and

a memory allocation engine that is configured to;

receive a memory allocation request specifying an amount of memory;

identify a FIFO node size based on the amount of memory;

select the first FIFO that is populated with the FIFO nodes, wherein the FIFO nodes are of the FIFO node size; and

pop a FIFO head node from the first FIFO to satisfy the memory allocation request.

12. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to allocate memory, by performing the steps of:

receiving a memory allocation request specifying an amount of memory;

identifying first-in first-out sub-system (FIFO) node size based on the amount of memory;

selecting a first FIFO that is populated with FIFO nodes of the FIFO node size; and

popping a FIFO head node from the first FIFO to satisfy the memory allocation request.

13. The non-transitory computer-readable storage medium of claim 12, further comprising:

creating the first FIFO including a head pointer value; and

populating the first FIFO with the FIFO nodes configured in a linked list, wherein each FIFO node includes a next value that indicates a next FIFO node in the linked list.

14. The non-transitory computer-readable storage medium of claim 12, further comprising:

receiving a second memory allocation request;

determining that the second memory request is rejected by the first FIFO;

selecting a second FIFO; and

popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

15. The non-transitory computer-readable storage medium of claim 14, further comprising indicating that the first FIFO is unavailable for allocations.

16. The non-transitory computer-readable storage medium of claim 14, wherein the first FIFO is empty.

17. The non-transitory computer-readable storage medium of claim 12, further comprising:

receiving a second memory allocation request;

determining that the second memory request is rejected by the first FIFO;

creating a second FIFO;

populating the second FIFO with FIFO nodes of the FIFO node size, wherein the FIFO nodes are configured in a linked list and each FIFO node includes a next value that indicates a next FIFO node in the linked list; and

popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

18. The non-transitory computer-readable storage medium of claim 12, further comprising:

receiving a second memory allocation request specifying a second amount of memory;

determining that the FIFO node size is smaller than the second amount of memory;

creating a second FIFO;

populating the second FIFO with second FIFO nodes of a second FIFO node size that is greater than the FIFO node size; and

popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

19. The non-transitory computer-readable storage medium of claim 12, wherein the FIFO nodes represent portions of sequential memory and the FIFO nodes are configured in a linked list in an order of the portions of sequential memory.

20. The non-transitory computer-readable storage medium of claim 12, further comprising:

determining that all the FIFO nodes that populate the first FIFO are freed;

retiring the first FIFO; and

releasing a quantity of memory corresponding to the FIFO nodes.