Allocating shared memory among multiple tasks in a multiprocessor environment

The present disclosure generally relates to a method and system for efficiently sharing limited memory among multiple processors. Each processor has a local linked list. The local linked list identifies the pages allocated to the specific processor as well as the number of free codewords for each allocated page. Additionally, the local linked list includes the location of the next free codeword(s) for each allocated page. When all codewords are available, the page is considered free and may be sent back to the page pool used by all of the processors. If there are a sufficient number of contiguous free codewords on an allocated page, then new codeword data may be stored in the page. If there is not a sufficient number of contiguous free codewords on any allocated page, then a new page is allocated from the page pool. Thus, efficient allocate of memory resources is achieved.

BACKGROUND OF THE DISCLOSURE

Field of the Disclosure

Embodiments of the present disclosure generally relate to a method and system for efficiently sharing limited memory among multiple processors.

Description of the Related Art

In a multiprocessor hard disk drive (HDD) or SSD environment with a shared memory, each processor needs to allocate memory for use with the restrictions that (1) memory that is already in use by another processor may not be allocated to an additional processor; and (2) too much memory may not be allocated to any individual processor. If too much memory is allocated to any one processor, the other processors may “starve” for lack of memory. Typically, memory is divided up into fixed sized chunks called pages. Each processor allocates pages as pages are needed. As a page that has been allocated to a processor is no longer needed, the page is returned to the global pool of pages so that the page may be (re)used by any of the processors in the system.

A page is the memory granularity required for write operations in a memory device such as an SSD device. A codeword is the memory granularity for read operations in a memory device such as an SSD device. A single read operation utilizes one or more codewords. In many memory devices, the page size is a multiple of the codeword size.

Depending upon the workload, each processor may only need a small fraction of a page for the task that the processor is handling. The simple solution is to ignore the large fraction of the page that is not needed and, when the processor is done with the memory that is needed, return the entire page back to the pool. For systems with a large amount of disposable memory, using only small portions of a page is not an issue. However, for smaller, embedded systems, such as systems running on HDDs or SSDs, there is typically not enough high-performance memory to allow for wasting large portions of allocated pages. Specifically, allocating memory is a low overhead operation (i.e., low processor cycles), and efficiency is currently lacking. Additionally, the total utilization of memory is very high, which can lead to inefficiencies. The total utilization of memory and the allocation of memory often conflict.

Therefore, there is a need in the art for a method and system to efficiently utilize and allocate memory among multiple processors.

SUMMARY OF THE DISCLOSURE

The present disclosure generally relates to a method and system for efficiently sharing limited memory among multiple processors. Each processor has a local linked list. The local linked list identifies the pages allocated to the specific processor as well as the number of free codewords for each allocated page. Additionally, the local linked list includes the location of the next free codeword(s) for each allocated page. When all codewords are available, the page is considered free and may be sent back to the page pool used by all of the processors. If there are a sufficient number of contiguous free codewords on an allocated page, then new codeword data may be stored in the page. If there is not a sufficient number of contiguous free codewords on any allocated page, then a new page is allocated to the processor from the page pool. Efficient allocation of memory resources is achieved because pages are not swapped back to the free pool unless no codewords remain allocated in the page, which reduces overhead for allocation and free pages; codewords within a page can be reused before the entire page is released, thus maintaining a higher overall utilization of buffer; and as codewords are freed, the pages are added to the codeword contiguous free count thus allowing for larger allocations to be made to increase overall buffer utilization.

Reference is made within the disclosure to a “storage device”. It is to be understood that the “storage device” is not to be limited to any specific storage device such as an SSD, HDD or other memory device. Rather, it is to be understood that unless specifically stated, a “storage device” is to encompass the possibility of any generic storage device.

In one embodiment, a system comprises a host device; and a storage device coupled to the host device. The storage device comprises a plurality of processors. Each processor includes: means to create a local linked list; means to allocate a free page from a page pool; means to return a free page to the page pool; means to allocate and free codewords from the page; means to check the local linked list; means to change identification of a first free codeword in the local linked list; and means to change an identification number of a number of codewords free in the local linked list. The storage device also includes a memory device coupled to each processor of the plurality of processors.

In another embodiment, a method comprises: checking a local linked list on a first processor of a plurality of processors; determining that an allocated page on the local linked list has a number of contiguous codewords that is greater than or equal to a number of codewords to be allocated; allocating codewords from the allocated page; incrementing a number of a first codeword free for the allocated page in the local linked list; and decreasing a number of codewords free for the allocated page in the local linked list.

In another embodiment, a method comprises: freeing one or more codewords in an allocated page, wherein the allocated page is allocated to a first processor of a plurality of processors; incrementing a number of codewords free in the allocated page in a local linked list for the first processor; determining whether the allocated page has any codewords allocated; and returning the allocated page to a page pool, wherein the page pool is shared by the plurality of processors.

DETAILED DESCRIPTION

The present disclosure generally relates to a method and system for efficiently sharing limited memory among multiple processors. Each processor has a local linked list. The local linked list identifies the pages allocated to the specific processor as well as the number of free codewords for each allocated page. Additionally, the local linked list includes the location of the next free codeword(s) for each allocated page. When all codewords are available, the page is considered free and may be sent back to the page pool used by all of the processors. If there are a sufficient number of contiguous free codewords on an allocated page, then new codeword data may be stored in the page. If there is not a sufficient number of contiguous free codewords on any allocated page, then a new page is allocated to the processor from the page pool. Efficient allocation of memory resources is achieved because pages are not swapped back to the free pool unless no codewords remain allocated in the page, which reduces overhead for allocation and free pages; codewords within a page can be reused before the entire page is released, thus maintaining a higher overall utilization of buffer; and as codewords are freed, the pages are added to the codeword contiguous free count thus allowing for larger allocations to be made to increase overall buffer utilization.

FIG. 1is a schematic illustration of a system100according to one embodiment. The system includes a host device102that interacts with a storage device104. A controller106is coupled to both the host device102and the storage device104. The storage device104stores data that may be needed by the host device102at various times. When the data is needed, the host device102contacts the storage device104to obtain the data. The controller106controls the communication between the storage device104and the host device102.

The storage device104includes a controller108and multiple CPUs or processors110A-110N. The storage device104also includes a memory device112. The memory device112is coupled to all of the CPUs110A-110N as well as the controller108.

FIG. 2Ais a schematic illustration of a generic CPU or processor110of the system100ofFIG. 1. InFIG. 2A, the CPU110is shown to have a controller202that interacts with both a cache storage204and the memory device112. As will be discussed below, the memory device112includes a plurality of pages that can be allocated to the plurality of processors110A-110N. Each processor110A-110N has a local linked list that includes identification of one or more allocated pages, a listing of the first codeword free for each allocated page in the local linked list, and a listing of the total number of codewords free for each allocated page in the local linked list.

The controllers106,202are digital circuits that manage the flow of data going to and from the storage device104(in the case of controller106) and to and from an individual CPU110A-110N (in the case of controller202). The controllers106,202can be separate chips or integrated into other chips, such as being placed on the same die or as an integral part of a CPU (as in the case of controller202). Controllers106,202may be referred to as integrated memory controllers (IMC), a memory chip controller (MCC) or a memory controller unit (MCU). The controllers202function to create a local linked list; to allocate codewords among allocated pages; to check the local linked list; to change identification of a first free codeword in the local linked list; and to change an identification number of a number of codewords free in the local linked list.

FIG. 2Bis a schematic illustration of a memory device112having multiple pages210A-210I. It is to be understood that while nine separate pages have been shown, the memory device112may have more or less pages. Nine pages210A-210I are used for exemplification purposes only and is not to be limiting.

FIG. 3is schematic illustration of multiple processors110A-110C accessing a common memory device112according to one embodiment. As shown inFIG. 3, each processor110A-110C has access to all of the multiple pages210A-210I in the entire memory device112. However, while each processor110A-110C has access to all of the pages210A-210I, certain pages210A-210I have been allocated to certain processors110A-110C while certain pages210A-210I are not currently needed by any processor110A-110C and thus are still in the page pool of unallocated or available pages210A-210I. In particular, processor110A currently has pages210A,210E allocated thereto as shown by lines302,304; processor110B has pages210D,210G allocated thereto as shown by lines306,308; and processor110C has page210H allocated thereto as shown by line310.

As noted above, there is a need in the art for a method and system to efficiently allocate memory among multiple processors. To solve the need, some parameters need to be implemented. Codeword allocations for a specific read request should all be contiguous. A single page should be used for as many codeword allocations as possible. A new page should not be allocated from the memory or page pool until no pages already allocated have enough contiguous codewords available therein to meet the new codeword allocation request. Codewords for a specific read request cannot span multiple memory pages since pages allocated by a processor are not guaranteed to be contiguous and so those pages can be freed up as quickly as possible for other uses once the pages are unused.

In order to ensure efficient allocation of memory among the multiple processors, a local linked list is created on each processor. Each element in the list contains the page unique ID (PageUID); unique ID of the first codeword free in the page (FirstCwFree); and the number of contiguous codewords free from the first (NumCwFree), where numCwFree is less than or equal to the number of codewords in a page (NumCwPerPage).

When a processor needs to allocate codewords (NumCwToAllocate), the processor first checks the local, associated linked list on the processor to look for a node where NumCwFree is greater than or equal to NumCwToAllocate. If a node is found, the processor increments FirstCwFree and decrements NumCwFree by NumCwToAllocate. The processor then completes the assigned task.

If a node is not found, then the processor allocates a new page from the global page pool. The processor then adds a new node to the processor's local linked list where FirstCwFree is set to NumCwToAllocate and NumCwFree is set to NumCwPerPage-NumCwToAllocate. The processor then completes the assigned task.

When a processor is done with the codewords, the processor first checks the processor's local linked list to look for a node with the same PageUID as that of the codewords to be freed and a range of free code words immediately preceding or following the range to be freed. If a matching node is not found, the processor adds a new node to the processor's local linked list for the codeword range to be freed.

If a matching node is found, then the processor increments NumCwFree by NumCwToAllocate and, if the new range to free precedes the existing free range, also decrements FirstCwFree by NumCwToAllocate. If NumCwFree equals NumCwPerPage, the node is removed from the local linked list of the processor and the entire page is returned to the global pool.

FIGS. 4A-4Eare schematic illustrations of a linked list400for a processor according to one embodiment.FIG. 4Arepresents some point in time where two pages have been allocated to a processor. As shown inFIG. 4A, the processor has two pages allocated thereto, PageUID2and PageUID5. For PageUID2, the FirstCwFree is at5with the NumCwFree equal to 45. PageUID5, on the other hand, has the FirstCwFree at 0 with NumCwFree equal to 5. Additionally, PageUID5has additionally codewords not yet allocated starting at 10 with NumCwFree equal to 5. Thus, on PageUID2, the codewords 0-4 are allocated and codewords 5-49 are available. For PageUID5, codewords 0-4 and 10-14 are available while codewords 5-9 and all codewords from 15 to the last codeword are allocated.

Moving now toFIG. 4B, the five used codewords from PageUID2(i.e., codewords 0-4) have been freed. Therefore, for PageUID2, all codewords have been freed and the entire PageUID2is not in use. Thus, PageUID2can be returned to the page pool for another processor to allocate. Therefore, inFIG. 4B, PageUID2is no longer shown as PageUID2has been returned to the pool.

Moving now toFIG. 4C, 10 codewords now need allocated for the processor. PageUID5still has FirstCwFree at 0 with NumCwFree equal to 5, and PageUID5has additional codewords free with the next codeword free at 10 and NumCwFree equal to 5. Therefore, PageUID5does not have 10 or more sequential or continuous codewords free and thus, PageUID5is not sufficient for allocating the 10 codewords. Therefore, a new page, PageUID1, needs to be allocated from the pool to the processor. PageUID1has 50 codewords upon being allocated to the processor, none of which are in use. Thus, there are 10 continuous codewords available in PageUID1, and PageUID1is used for the 10 codewords. Once the 10 codewords are allocated from PageUID1, PageUID1has a FirstCwFree at 10 with NumCwFree equal to 40.

Moving now toFIG. 4D, five codewords are freed from codewords 5-9 on PageUID5. Thus, PageUID5now has the FirstCwFree at 0 as before, but the NumCwFree is 15. Therefore, codewords 0-14 are now free and, assuming that there are more than 15 codewords in PageUID5, the remaining codewords are allocated. If no codewords in PageUID5are allocated, then PageUID5may be returned to the pool.

Moving now toFIG. 4E, 8 codewords need to be allocated. PageUID5has 15 codewords free starting at codeword 0. PageUID1has 40 codewords free starting at codeword 10. Thus, both PageUID1and PageUID5have at least 8 continuous codewords free. If PageUID5is utilized for the 8 codewords, as shown inFIG. 4E, then after the 8 codewords are allocated to PageUID5, the FirstCwFree is 8 for PageUID5and the NumCwFree is 7 for PageUID5. The 7 remaining codewords in PageUID5and the 40 remaining codewords in PageUID1may be used at a later time.

FIG. 5is a flow chart500illustrating an embodiment of the disclosure. The process starts with a processor having a plurality of codewords to allocate. The processor searches the pages allocated thereto in block502. A determination is made in block504as to whether there are a sufficient number of continuous codewords available in the allocated pages for allocating the codewords from the page. If there is not a sufficient number of continuous codewords available, then a new page is allocated from the pool of pages in block506and the codewords are then allocated from the new page in block508. If there is a sufficient number of continuous codewords in block504, then the codewords are allocated from a page that has the sufficient number of continuous codewords in block508.

FIG. 6is a flow chart600illustrating another embodiment of the disclosure. The process starts with a processor freeing up one or more codewords in a page that has been allocated to the processor in block602. The processor then increments the NumCwFree in the local list by an amount equal to the number of codewords freed in block604. Depending upon the first contiguous codeword that has been freed, the processor may need to change the FirstCwFree to reflect the location of the first free codeword in block606. If the FirstCwFree is now 0 in block608and the NumCwFree is equal to the total number of codewords on the page in block610, then the page is returned to the pool in block614. If the FirstCwFree is not 0 in block606or the NumCwFree is less than the total number of codewords on the page, then the page remains allocated to the processor in block612.

In operation, the method involves checking a local linked list on a first processor of a plurality of processors; determining that an allocated page on the local linked list has a number of contiguous codewords that is greater than or equal to a number of codewords to be allocated; allocating codewords from the allocated page; incrementing a number of a first codeword free for the allocated page in the local linked list; and decreasing a number of codewords free for the allocated page in the local linked list. The method may additionally include: checking the local linked list on the first processor; determining that allocated pages do not have sufficient contiguous codewords available; and obtaining a new page from a page pool shared by the plurality of processors. The method may further include allocating codewords from the new page and updating the local linked list. The method may further comprise freeing a plurality of codewords from a second page allocated to the first processor; determining that all of the codewords for the second page are free; and returning the second page to a page pool. The method may further comprise checking a local linked list on a second processor of a plurality of processors; determining that an allocated page on the local linked list of the second processor has a number of contiguous codewords that is greater than or equal to a number of codewords to be allocated; allocating codewords from the allocated page; incrementing a number of a first codeword free for the allocated page in the local linked list; and decreasing a number of codewords free for the allocated page in the local linked list. Additionally, the method may include freeing a plurality of codewords from a second page allocated to the second processor; determining that all of the codewords for the second page are free; and returning the second page to a page pool. Finally, the method may include checking the local linked list on the second processor; determining that allocated pages do not have sufficient contiguous codewords available; and obtaining a new page from a page pool shared by the plurality of processors.

Also, in operation, the method may comprise checking a local linked list on a first processor of a plurality of processors, wherein checking comprises: looking for an allocated page of the first processor with a same PageUID as one or more codewords to be freed; and looking for a range of free codewords immediately preceding or following the one or more codewords to be freed; determining if there is a page to be freed; and returning the page to the page pool if the page is determined to have no codewords allocated therefrom.

By allocating codewords in a continuous manner in allocated pages, multiple processors can efficiently share limited memory. The memory allocation is contiguous with no SGLs and a single page is used for as many memory allocations as possible to maximize the usage of an allocated page. No single memory allocation spans multiple pages. Furthermore, as codewords are freed, a determination is made as to whether the allocated page still has any codewords allocated. If no codewords are allocated in an allocated page, then the page is returned to the page pool and is available for allocation to any other processor. By doing the above, memory allocate is fast and efficient.