Dynamic memory allocation using a shared free list

Patent metadata

Field	Value
Publication number	US-12493547-B2
Application number	US-202318330007-A
Country	US
Kind code	B2
Filing date	Jun 6, 2023
Priority date	Jun 6, 2023
Publication date	Dec 9, 2025
Grant date	Dec 9, 2025

Abstract

Apparatuses, systems, and techniques for dynamic memory allocation using a shared free list. A user tag is received, and a hashed user tag is generated. A first reference to an entry in a second data structure is identified in a first data structure using the hashed user tag. The entry includes multiple user tags. Responsive to determining that the multiple user tags do not include the user tag, a memory address is identified in a third data structure. The memory address is removed from the third data structure. Memory is allocated for a user context associated with the user tag at the memory address. The user tag is added to the second data structure.

First claim

What is claimed is:

1 . A method comprising:
determining a user tag and a user context associated with the user tag based on a network transaction, wherein the user context comprises at least part of the network transaction; generating a hashed user tag; identifying, in a first data structure using the hashed user tag, a first reference to an entry in a second data structure, the entry including a plurality of user tags; responsive to determining the plurality of user tags does not include the user tag:
identifying, in a third data structure, a memory address;
removing the memory address from the third data structure;
allocating memory for the user context associated with the user tag at the memory address; and
adding the user tag to the second data structure, wherein the user tag has an associated user tag offset and an associated user context offset, wherein the associated user tag offset indicates a first offset within the second data structure and the associated user context offset indicates a second offset within the second data structure.

2 . The method of claim 1 , further comprising:
locking the memory address; and returning a second reference to the memory address, wherein the second reference comprises the user tag offset.

3 . The method of claim 2 , further comprising:
receiving a request to release the user tag; deallocating memory for the user context associated with the user tag at the memory address; adding the memory address to the third data structure; and releasing the memory address.

4 . The method of claim 3 , further comprising:
removing the user tag from the entry in the second data structure; and rearranging the second data structure.

5 . The method of claim 1 , wherein the second data structure is a linked list.

6 . The method of claim 1 , wherein the third data structure is a last-in, first-out queue.

7 . The method of claim 1 , wherein the entry in the second data structure further comprises a plurality of valid bits, wherein each of the plurality of user tags is associated with one or more of the plurality of valid bits.

8 . A system comprising:
a memory; and hardware controller logic coupled to the memory, to perform operations comprising:
determining a user tag and a user context associated with the user tag based on a network transaction, wherein the user context comprises at least part of the network transaction;
generating a hashed user tag;
identifying, in a first data structure using the hashed user tag, a first reference to an entry in a second data structure, the entry including a plurality of user tags;
responsive to determining the plurality of user tags does not include the user tag:
identifying, in a third data structure, a memory address;
removing the memory address from the third data structure;
allocating memory for the user context associated with the user tag at the memory address; and
adding the user tag to the second data structure, wherein the user tag has an associated user tag offset and an associated user context offset, wherein the associated user tag offset indicates a first offset within the second data structure and the associated user context offset indicates a second offset within the second data structure.

9 . The system of claim 8 , the operations further comprising:
locking the memory address; and returning a second reference to the memory address, wherein the second reference comprises the user tag offset.

10 . The system of claim 9 , the operations further comprising:
receiving a request to release the user tag; deallocating memory for the user context associated with the user tag at the memory address; adding the memory address to the third data structure; and releasing the memory address.

11 . The system of claim 10 , the operations further comprising:
removing the user tag from the entry in the second data structure; and rearranging the second data structure.

12 . The system of claim 8 , wherein the second data structure is a linked list.

13 . The system of claim 8 , wherein the third data structure is a last-in, first-out queue.

14 . The system of claim 8 , wherein the entry in the second data structure further comprises a plurality of valid bits, wherein each of the plurality of user tags is associated with one or more of the plurality of valid bits.

15 . A network interface controller coupled with a host, the network interface controller comprising processing circuitry to perform operations comprising:
determining a user tag and a user context associated with the user tag based on a network transaction, wherein the user context comprises at least part of the network transaction; generating a hashed user tag; identifying, in a first data structure using the hashed user tag, a first reference to an entry in a second data structure, the entry including a plurality of user tags; responsive to determining the plurality of user tags does not include the user tag:
identifying, in a third data structure, a memory address;
removing the memory address from the third data structure;
allocating memory for the user context associated with the user tag at the memory address; and
adding the user tag to the second data structure, wherein the user tag has an associated user tag offset and an associated user context offset, wherein the associated user tag offset indicates a first offset within the second data structure and the associated user context offset indicates a second offset within the second data structure.

16 . The network interface controller of claim 15 , the operations further comprising:
locking the memory address; and returning a second reference to the memory address, wherein the second reference comprises the user tag offset.

17 . The network interface controller of claim 16 , the operations further comprising:
receiving a request to release the user tag; deallocating memory for the user context associated with the user tag at the memory address; adding the memory address to the third data structure; and releasing the memory address.

18 . The network interface controller of claim 17 , the operations further comprising:
removing the user tag from the entry in the second data structure; and rearranging the second data structure.

19 . The network interface controller of claim 15 , wherein the second data structure is a linked list.

20 . The network interface controller of claim 15 , wherein the third data structure is a last-in, first-out queue.

Assignees

• Mellanox Technologies Ltd

Inventors

• Kremer Gil
• Moyal Roee
• Voks Igor
• Peled Liel
• Peretz Eliel
• Shahar Ariel

Classifications

• G06F2212/154

  Networked environment · CPC title

• G06F12/023 Primary

  Free address space management · CPC title