Shared fabric attached memory allocator

• US 10,705,951 B2
• Filed: 01/31/2018
• Issued: 07/07/2020
• Est. Priority Date: 01/31/2018
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Patel, Yuvraj, Zhang, Yupu, Gmach, Daniel
• Primary Examiner(s): Grullon, Francisco A
• Application Number:
  US15/885,044
• Publication Number:
  US 20190236001A1
• Time in Patent Office: 888 Days
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0284 Multiple user address space allocation, e.g. using different base addresses interprocessor communication G06F15/163
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

An example system comprises one or more processing nodes to execute one or more processes; a switching fabric coupled to the one or more processing nodes; a fabric-attached memory (FAM) coupled with the switching fabric; and a memory allocator to allocate and release memory in the FAM in response to memory allocation requests and memory release requests from the one or more processes. The memory allocator is to partition the FAM into a memory shelf comprising a plurality of memory books of equal size. The memory allocator is to map a shelf into a virtual memory zone, the zone aligned with the boundaries of one or more books. The memory allocator is to maintain an indexed free-memory list where each index level is an entry point to a list of free memory blocks of a particular size in the zone, and the memory allocator to maintain a bitmap of the zone to identify if a memory block of a particular size is allocated.

Claims

1. A system, comprising:

a plurality of processing nodes configured to execute one or more processes, each processing node comprising a processor, a local memory, and a fabric bridge;

a switching fabric comprising a plurality of fabric switch instances, each fabric switch instance coupled to at least one of the plurality of processing nodes via the fabric bridge of the at least one of the plurality of processing nodes;

a fabric-attached memory (FAM) comprising a plurality of memory instances, each memory instance of the FAM being directly coupled to a fabric switch instance of the switching fabric and each fabric switch instance being coupled with at least one other fabric switch instance of the switching fabric;

wherein each memory instance of the FAM is shared by each of the processing nodes such that each memory block within every memory instance, independent of whether the memory block has been previously accessed, allocated or released by a different processing node of the plurality of processing nodes, may be accessed, allocated, and released by each processing node of the plurality of processing nodes;

a memory allocator to allocate and release one or more memory blocks in the FAM in response to memory allocation requests and memory release requests from the one or more processes executed by one or more of the processing nodes,

the memory allocator to partition the FAM into a memory shelf comprising a plurality of memory books of equal size,

the memory allocator to map a shelf into a virtual memory zone, the zone aligned with boundaries of one or more books,

the memory allocator to maintain an indexed free-memory list having a plurality of index levels, where each index level is an entry point to a list of free memory blocks of a particular size in the zone, and

the memory allocator to maintain a bitmap of the zone to identify if a memory block of a particular size is allocated.

2. The system of claim 1, where in response to a request from a process to allocate memory for a memory block that is less than or equal to one-half of any free memory block in the zone, the memory allocator is operative to:

identify a smallest free memory block from the free memory list;

iteratively divide the free memory block into smaller memory blocks until a size of a smaller memory block is larger than the requested memory block size and the requested memory block size is larger than the next memory block size would be after another division;

allocate the smaller memory block by removing the block from the free memory list and setting the corresponding bit in the bitmap; and

return a handle to the process identifying the address and index level of the smaller memory block.

3. The system of claim 1, where in response to a request from a process to allocate memory for a particular size memory block that is larger than the size of any free memory block in the zone, the memory allocator is operative to:

identify a largest pair of contiguous free memory blocks from the free memory list;

merge the contiguous free memory blocks until the size of a merged memory block is larger than the requested memory block size;

remove the merged block from the free memory list and set a corresponding bit in the bitmap; and

return a handle to the requesting process identifying an address and an index level of the merged memory block.

4. The system of claim 1, where in response to a request from a process to release a designated memory block, the memory allocator is operative to:

receive a handle of the designated memory block from the process, the handle identifying the address and the index level of the designated memory block;

based on the address and the index level of the designated memory block, determine a bit in the bitmap corresponding to the designated memory block;

clear the bit; and

add the designated memory block to the free-memory list at the identified index level.

5. The system of claim 1, wherein to consolidate free memory in the zone, the allocator is operative to:

sort all entries in the free memory list at each index level by memory address;

walk through the sorted entries to identify contiguous memory blocks of the same size; and

to

iteratively;

merge the contiguous memory blocks at each level into memory blocks of the next largest size, beginning at the index level corresponding to a smallest free memory block size and proceeding to an index level corresponding to a largest free memory block size; and

move the merged memory blocks from their current index level to an index level corresponding to a next largest memory block size.

6. The system of claim 1, where when a memory allocation request exceeds available free memory in the zone, the memory allocator is further operative to grow the zone to include additional books in the shelf up to a number limited by a capacity of the shelf.

7. The system of claim 6, where when a memory allocation request exceeds available free memory in the shelf, the memory allocator is further operative to grow the shelf by adding additional books up to a maximum addressable memory space of the system.

8. A method, comprising:

partitioning a shared fabric attached memory (FAM) into a memory shelf comprising a plurality of memory books of equal size,

wherein the shared FAM comprises a plurality of memory instances shared between a plurality of processing nodes such that each memory block within every memory instance, independent of whether the memory block has been previously accessed, allocated or released by a different processing node of the plurality of processing nodes, may be accessed, allocated, and released by each processing node of the plurality of processing nodes;

wherein each processing node comprises a processor, a local memory, and a fabric bridge, wherein the processing node is coupled to a switching fabric;

wherein the switching fabric comprises a plurality of fabric switch instances, each fabric switch instance coupled to at least one of the plurality of processing nodes via the fabric bridge of the at least one of the plurality of processing nodes; and

wherein each of memory instance of the FAM is directly coupled to a fabric switch instance of the switching fabric and each fabric switch instance is coupled with at least one other fabric switch instance of the switching fabric;

mapping a shelf into a virtual memory zone, the zone aligned with boundaries of one or more books;

maintaining an indexed free-memory list having a plurality of index levels where each index level is an entry point to a list of free memory blocks of a particular size in the zone; and

maintaining a bitmap of the zone to identify if a memory block of a particular size is free or allocated.

9. The method of claim 8, further comprising:

receiving a request to allocate memory for a memory block that is less than or equal to one-half of any free memory block in the zone;

identifying a smallest free memory block from the free memory list;

dividing the free memory block into smaller memory blocks until a size of a current memory block is larger than the requested memory block size and the requested memory block size is larger than the next memory block size would be after another division;

removing the current memory block from the free memory list and setting a corresponding bit in the bitmap; and

returning a handle identifying an address and an index level of the current memory block.

10. The method of claim 8, further comprising:

receiving a request to allocate memory for a memory block that is larger than any free memory block in the zone;

identifying a largest pair of contiguous free memory blocks from the free memory list;

merging the contiguous free memory blocks until the size of a merged memory block is larger than the requested memory block size;

removing the merged memory block and setting a corresponding bit in the bitmap; and

returning a handle identifying an address and an index level of the merged memory block.

11. The method of claim 8, further comprising:

receiving a handle of a designated memory block identifying an address and an index level of the designated memory block;

based on the address and the index level of the designated memory block, determining a bit in the bitmap corresponding to the designated memory block;

clearing the bit; and

adding the designated memory block to the free-memory list at the identified index level.

12. A non-transitory computer-readable storage medium encoded with instructions executable by a processor of a computing system, the computer-readable storage medium comprising instructions to:

partition a shared fabric attached memory (FAM) coupled to the processor into a memory shelf comprising a plurality of memory books of equal size,

wherein the shared FAM comprises a plurality of memory instances shared between a plurality of processing nodes such that each memory block within every memory instance, independent of whether the memory block has been previously accessed, allocated or released by a different processing node of the plurality of processing nodes, may be accessed, allocated, and released by each processing node of the plurality of processing nodes;

wherein each processing node comprises a processor, a local memory, and a fabric bridge, wherein the processing node is coupled to a switching fabric;

wherein the switching fabric comprises a plurality of fabric switch instances, each fabric switch instance coupled to at least one of the plurality of processing nodes via the fabric bridge of the at least one of the plurality of processing nodes; and

wherein each of memory instance of the FAM is directly coupled to a fabric switch instance of the switching fabric and each fabric switch instance is coupled with at least one other fabric switch instance of the switching fabric;

map a shelf into a virtual memory zone,

maintain an indexed free-memory list having a plurality of index levels where each index level is an entry point to a list of free memory blocks of a particular size in the zone; and

maintain a bitmap of the zone to identify if a memory block of a particular size is free or allocated.

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

receive a request to allocate memory for a memory block that is less than or equal to one-half of any free memory block in the zone;

identify a smallest free memory block from the free memory list;

divide the free memory block into smaller memory blocks until a size of a current memory block is larger than the requested memory block size and the requested memory block size is larger than the next memory block size would be after another division;

remove the current memory block from the free memory list and setting a corresponding bit in the bitmap; and

return a handle identifying the address and index level of the current memory block.

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

receive a request to allocate memory for a memory block that is larger than any free memory block in the zone;

identify a largest pair of contiguous free memory blocks from the free memory list;

merge the contiguous free memory blocks until the size of a merged memory block is larger than the requested memory block size;

remove the merged memory block and set a corresponding bit in the bitmap; and

return a handle identifying an address and an index level of the merged memory block.

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

receive a request to release a designated memory block;

receive a handle of the designated memory block identifying an address and an index level of the designated memory block;

based on the address and the index level of the designated memory block, determine a bit in the bitmap corresponding to the designated memory block;

clear the bit; and

add the designated memory block to the free-memory list at the identified index level.