PARALLEL DYNAMIC MEMORY ALLOCATION USING A LOCK-FREE POP-ONLY FIFO

• US 20130198479A1
• 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,417,881 B2
• Time in Patent Office: Days
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

One embodiment of the present invention sets forth a technique for dynamically allocating memory using one or more lock-free pop-only 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 first memory allocation request specifying a first amount of memory;

receiving a second memory allocation request simultaneously with the first memory allocation request, wherein the second memory allocation request specifies the first amount of memory;

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

selecting a first FIFO and a second FIFO that are each populated with FIFO nodes of the FIFO node size;

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

popping a second FIFO head node from the second FIFO, simultaneously with the popping of the first FIFO head node, to satisfy the second memory allocation request.

2. The method of claim 1, further comprising receiving a first allocation free request to free a portion of memory represented by the first FIFO head node.

3. The method of claim 2, further comprising updating tracking information associated with the first FIFO to indicate that the first FIFO head node is freed.

4. The method of claim 3, wherein the tracking information is updated using an atomic operation.

5. The method of claim 2, further comprising:

receiving additional allocation free requests to free additional portions of memory represented by additional FIFO nodes popped from the first FIFO;

determining that all FIFO nodes popped from the first FIFO are freed;

retiring the first FIFO; and

releasing a quantity of memory corresponding to the FIFO nodes populating the first FIFO.

6. The method of claim 1, wherein the first FIFO is configured as a lock-free pop-only FIFO and the second FIFO is configured as a lock-free FIFO.

7. The method of claim 1, further comprising receiving a first allocation push request for a portion of memory represented by the second FIFO head node.

8. The method of claim 7, further comprising pushing the second FIFO head node onto the second FIFO as a new FIFO tail node.

9. The method of claim 8, further comprising:

changing a configuration of the second FIFO from a lock-free FIFO to a lock-free pop-only FIFO;

receiving an allocation free request to free a portion of memory represented by a FIFO node popped from the second FIFO; and

updating tracking information associated with the second FIFO to indicate that the FIFO node is freed.

10. The method of claim 1, further comprising:

creating the first FIFO;

populating the first FIFO with the 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

initializing tracking information associated with the first FIFO indicating a quantity of FIFO nodes that populate the first FIFO.

11. A computing system, comprising:

a memory heap;

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

a second FIFO that is populated with a second quantity of FIFO nodes that each represent the portion of memory from the memory heap; and

a memory allocation engine that is configured to;

receive a first memory allocation request specifying a first amount of memory;

receive a second memory allocation request simultaneously with the first memory allocation request, wherein the second memory allocation request specifies the first amount of memory;

identify a first-in first-out buffer (FIFO) node size based on the first amount of memory;

select the first FIFO and the second FIFO based on the FIFO node size;

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

pop a second FIFO head node from the second FIFO, simultaneously with the popping of the first FIFO head node, to satisfy the second 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 first memory allocation request specifying a first amount of memory;

receiving a second memory allocation request simultaneously with the first memory allocation request, wherein the second memory allocation request specifies the first amount of memory;

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

selecting a first FIFO and a second FIFO that are each populated with FIFO nodes of the FIFO node size;

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

popping a second FIFO head node from the second FIFO, simultaneously with the popping of the first FIFO head node, to satisfy the second memory allocation request.

13. The non-transitory computer-readable storage medium of claim 12, further comprising receiving a first allocation free request to free a portion of memory represented by the first FIFO head node.

14. The non-transitory computer-readable storage medium of claim 13, further comprising updating tracking information associated with the first FIFO to indicate that the first FIFO head node is freed.

15. The non-transitory computer-readable storage medium of claim 14, wherein the tracking information is updated using an atomic operation.

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

receiving additional allocation free requests to free additional portions of memory represented by additional FIFO nodes popped from the first FIFO;

determining that all FIFO nodes popped from the first FIFO are freed;

retiring the first FIFO; and

releasing a quantity of memory corresponding to the FIFO nodes populating the first FIFO.

17. The non-transitory computer-readable storage medium of claim 12, wherein the first FIFO is configured as a lock-free pop-only FIFO and the second FIFO is configured as a lock-free FIFO.

18. The non-transitory computer-readable storage medium of claim 12, further comprising receiving a first allocation push request for a portion of memory represented by the second FIFO head node.

19. The non-transitory computer-readable storage medium of claim 18, further comprising pushing the second FIFO head node onto the second FIFO as a new FIFO tail node.

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

changing a configuration of the second FIFO from a lock-free FIFO to a lock-free pop-only FIFO;

receiving an allocation free request to free a portion of memory represented by a FIFO node popped from the second FIFO; and

updating tracking information associated with the second FIFO to indicate that the FIFO node is freed.