High performance memory allocator
Aspects of the disclosure are directed to a memory allocator for assigning contiguous memory space for data packets in on-chip memory of a network interface card. The memory allocator includes a plurality of sub-allocators that correspond to a structure of entries, where each entry represents a quanta of memory allocation. The sub-allocators are organized in decreasing size in the memory allocator based on the amount of memory quanta they can allocate.
1 . A method for assigning contiguous memory space for data packets, comprising:
receiving, with one or more processors, an allocation request to assign a number of continuous pointers to a sub-allocator memory of a plurality of sub-allocator memories that represent different quantas of memory allocation;
searching, with the one or more processors, for an available entry in a summary vector that corresponds to an available row in a sub-allocator memory;
selecting, with the one or more processors, a row in a sub-allocator memory based on a first available entry in the summary vector;
selecting, with the one or more processors, a first available entry in the selected row to provide addresses for the number of continuous pointers; and
marking, with the one or more processors, the selected entry as unavailable in the summary vector.
2 . The method of claim 1 , further comprising:
determining, with the one or more processors, corresponding entries to the selected entry in other sub-allocator memories; and
marking, with the one or more processors, the corresponding entries as unavailable.
3 . The method of claim 2 , further comprising resetting, with the one or more processors, entries in the summary vector based on the selected entry marked as unavailable and the corresponding entries marked as unavailable.
4 . The method of claim 1 , wherein the summary vector being searched matches the number of continuous pointers.
5 . The method of claim 1 , wherein the number of continuous pointers corresponds to a number of cells in a data packet.
6 . The method of claim 1 , further comprising determining, with the one or more processors, the number of continuous pointers to assign based on an incoming allocation request size and a cell size.
7 . The method of claim 1 , further comprising:
receiving, with the one or more processors, a deallocation request to remove a pointer from an entry in a sub-allocator memory; and
marking, with the one or more processors, the entry from which the pointer is being removed as available.
8 . The method of claim 7 , further comprising:
determining, with the one or more processors, corresponding entries to the entry from which the pointer is being removed in other sub-allocator memories; and
marking, with the one or more processors, the corresponding entries to the entry from which the pointer is being removed as available.
9 . The method of claim 7 , wherein allocation requests and deallocation requests are received in a round-robin fashion.
10 . The method of claim 1 , wherein the plurality of sub-allocator memories are arranged in decreasing size based on a number of continuous cells each sub-allocator memory can support.
11 . A system comprising:
one or more processors; and
one or more storage devices coupled to the one or more processors and storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations for assigning contiguous memory space for data packets, the operations comprising:
receiving an allocation request to assign a number of continuous pointers to a sub-allocator memory of a plurality of sub-allocator memories that represent different quantas of memory allocation;
searching for an available entry in a summary vector that corresponds to an available row in a sub-allocator memory;
selecting a row in a sub-allocator memory based on a first available entry in the summary vector;
selecting a first available entry in the selected row to provide addresses for the number of continuous pointers; and
marking the selected entry as unavailable in the summary vector.
12 . The system of claim 11 , wherein the operations further comprise:
determining corresponding entries to the selected entry in other sub-allocator memories;
marking the corresponding entries as unavailable; and
resetting entries in the summary vector based on the selected entry marked as unavailable and the corresponding entries marked as unavailable.
13 . The system of claim 11 , wherein the summary vector being searched matches the number of continuous pointers.
14 . The system of claim 11 , wherein the number of continuous pointers corresponds to a number of cells in a data packet.
15 . The system of claim 11 , wherein the operations further comprise determining the number of continuous pointers to assign based on an incoming allocation request size and a cell size.
16 . The system of claim 11 , wherein the operations further comprise:
receiving a deallocation request to remove a pointer from an entry in a sub-allocator memory;
marking the entry from which the pointer is being removed as available;
determining corresponding entries to the entry from which the pointer is being removed in other sub-allocator memories; and
marking the corresponding entries to the entry from which the pointer is being removed as available.
17 . The system of claim 16 , wherein allocation requests and deallocation requests are received in a round-robin fashion.
18 . The system of claim 11 , wherein the plurality of sub-allocator memories are arranged in decreasing size based on a number of continuous cells each sub-allocator memory can support.
19 . A non-transitory computer readable medium for storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations for assigning contiguous memory space for data packets, the operations comprising:
receiving an allocation request to assign a number of continuous pointers to a sub-allocator memory of a plurality of sub-allocator memories that each represent different quantas of memory allocation;
searching for an available entry in a summary vector that corresponds to an available row in a sub-allocator memory;
selecting a row in a sub-allocator memory based on a first available entry in the summary vector;
selecting a first available entry in the selected row to provide addresses for the number of continuous pointers; and
marking the selected entry as unavailable in the summary vector.
20 . The non-transitory computer readable medium of claim 19 , wherein the operations further comprise:
determining corresponding entries to the selected entry in other sub-allocator memories;
marking the corresponding entries as unavailable; and
resetting entries in the summary vector based on the selected entry marked as unavailable and the corresponding entries marked as unavailable.