Multidimensional contiguous memory allocation
The present disclosure is related to multidimensional contiguous memory allocation. Multidimensional contiguous memory allocation can include receiving an allocation request for an amount of memory that is contiguous in a multiple dimensions of the memory and determining whether the memory includes a region corresponding to the requested amount that is a candidate as being unallocated based on information indicating a maximum number of contiguous unallocated allocable portions of the memory. In response to determining that the memory includes the candidate region, the method can include determining whether the candidate region is unallocated based on a subset of information indicating whether each allocable portion of the memory is allocated. The subset of information corresponds to the candidate region only.
1. A method, comprising:
receiving an allocation request for an amount of memory that is contiguous in a plurality of dimensions of the memory;
determining whether the memory includes a region corresponding to the requested amount that is a candidate as being unallocated based on information indicating a maximum number of contiguous unallocated allocable portions of the memory in a first dimension of the plurality of dimensions that correspond to a particular element of a second dimension of the plurality of dimensions;
in response to determining that the memory includes the candidate region, determining whether the candidate region is unallocated based on a scan of a subset of the information indicating whether each allocable portion of the memory is allocated, wherein the subset of the information corresponds to the candidate region only; and
receiving data corresponding to the allocation request; and
storing the data in the candidate region.
2. The method of claim 1 , wherein the information further comprises information indicating the maximum number of contiguous unallocated allocable portions of the memory in the second dimension that correspond to a particular element of the first dimension.
3. The method of claim 2 , wherein the information further comprises information indicating the maximum number of contiguous unallocated allocable portions of the memory in a third dimension.
4. The method of claim 1 , wherein receiving the allocation request for the amount of memory comprises receiving the allocation request for an amount of virtual memory, and wherein the memory comprises physical memory that is contiguous in the plurality of dimensions of the physical memory.
5. The method of claim 4 , wherein the method includes allocating the candidate region in response to determining that the candidate region is unallocated.
6. The method of claim 1 , wherein the method is performed by at least one of a controller and an operating system of a computing system, and wherein the memory comprises random access memory.
7. The method of claim 6 , wherein the random access memory comprises volatile memory or non-volatile memory.
8. A method, comprising:
storing a multidimensional matrix including a respective plurality of units per dimension,
wherein each unit indicates whether a respective allocable portion of memory is allocated, and
wherein each dimension of the multidimensional matrix corresponds to a respective dimension of the memory;
storing a plurality of vectors, wherein each vector corresponds to a respective one of the plurality of dimensions,
wherein each vector includes a respective plurality of entries, and
wherein each entry represents a maximum number of contiguous unallocated allocable portions of the memory in the corresponding dimension that correspond to a particular element of a different dimension;
receiving data corresponding to an allocation request; and
storing the data in at least two of the number of contiguous unallocated allocable portions.
9. The method of claim 8 , wherein the method includes receiving the allocation request for an amount of memory that is contiguous in a plurality of dimensions of the memory; and
searching the plurality of vectors and scanning only a portion of the multidimensional matrix in response to the request.
10. The method of claim 9 , wherein scanning only the portion of the multidimensional matrix comprises scanning only the portion of the multidimensional matrix based on a result of searching the plurality of vectors.
11. The method of claim 10 , wherein the portion of the multidimensional matrix includes a number of units equal to a number of allocable portions of the memory needed to fulfill the request.
12. The method of claim 8 , wherein the method includes updating the multidimensional matrix and the plurality of vectors after an allocable portion of memory is allocated.
13. The method of claim 8 , wherein the method is performed by at least one of a controller and an operating system of a computing system, and wherein the memory comprises random access memory.
14. The method of claim 13 , wherein the random access memory comprises volatile memory or non-volatile memory.
15. An apparatus, comprising:
a host; and
a multidimensional random access memory coupled to the host, wherein the host is configured to:
receive an allocation request for an amount of memory that is contiguous in a plurality of dimensions of the memory;
search a plurality of vectors to determine whether the memory includes a region corresponding to the requested amount that is a candidate as being unallocated based on information stored in the plurality of vectors;
wherein each of the plurality of vectors corresponds to one of the plurality of dimensions of the memory and includes a plurality of entries, and
wherein each entry represents a maximum number of contiguous unallocated allocable portions of the memory in the corresponding dimension that correspond to a particular element of a different dimension;
in response to a determination that the memory includes the candidate region, determining whether the candidate region is unallocated;
receive data corresponding to the allocation request; and
store the data in the candidate region.
16. The apparatus of claim 15 , wherein the host is configured to search the plurality of vectors to determine whether the maximum number of contiguous unallocated allocable portions of the memory per corresponding dimension are sufficient in the plurality of dimensions to fulfill the request.
17. The apparatus of claim 15 , wherein the host is configured to determine whether the region is unallocated based on information stored in a portion of a matrix, wherein the portion corresponds to the region.
18. The apparatus of claim 17 , wherein the host is configured to scan only the portion of the matrix,
wherein the matrix comprises an n-dimensional matrix corresponding to n-dimensions of the memory, and
wherein the matrix, at each intersection of the n-dimensions, includes a respective indication of whether a corresponding allocable portion of the memory is allocated.
19. The apparatus of claim 15 , wherein the host is configured to allocate the candidate region in response to determining that the candidate region is unallocated.
20. The apparatus of claim 15 , wherein the host comprises a memory management unit.
21. The apparatus of claim 15 , wherein the multidimensional random access memory comprises volatile memory or non-volatile memory.
22. A non-transitory computer readable medium storing instructions executable by a processing resource to:
receive an allocation request for an amount of virtual memory, wherein the request specifies:
memory that is contiguous in a first dimension of a plurality of dimensions of the memory; and
memory that is contiguous in a second dimension of the plurality of dimensions of the memory; and
determine whether the first dimension of a physical memory includes a first number of contiguous unallocated allocable portions sufficient to fulfill the request by searching a vector corresponding to the first dimension for information indicating a maximum number of contiguous unallocated allocable portions of the physical memory in the first dimension;
determine whether the second dimension of the physical memory includes a second number of contiguous unallocated allocable portions of the memory sufficient to fulfill the request;
determine whether the first number of contiguous unallocated allocable portions and the second number of contiguous unallocated allocable portions are aligned in the first and the second dimensions to form a region of physical memory that is contiguous in the first and the second dimensions;
receive data corresponding to the allocation request; and
store the data in the region of physical memory.
23. The medium of claim 22 , including instructions to allocate the region of physical memory in response to a determination that the first and the second numbers of contiguous unallocated allocable portions are aligned in the first and the second dimensions.
24. The medium of claim 22 , wherein the instructions to determine whether the second dimension includes a second number of contiguous unallocated allocable portions comprise instructions to:
search a vector corresponding to the second dimension for information indicating a maximum number of contiguous unallocated allocable portions of the physical memory in the second dimension.
25. The medium of claim 22 , wherein the instructions to determine whether the first number of contiguous unallocated allocable portions and the second number of contiguous unallocated allocable portions are aligned in the first and the second dimensions comprise instructions to:
scan only a portion of a matrix for information indicating whether each of the allocable portions of the region are unallocated, wherein the portion of the matrix corresponds to the region.
26. A non-transitory computer readable medium storing instructions executable by a processing resource to:
determine whether a memory includes a region that is contiguous in a plurality of dimensions of the memory corresponding to a requested amount that is a candidate as being unallocated based on information indicating a maximum number of contiguous unallocated allocable portions of the memory in each dimension;
scan a subset of the information indicating whether each allocable portion of the memory is unallocated in response a determination that the memory includes the candidate region, wherein the subset of the information corresponds to the candidate region only;
receive data corresponding to the requested amount; and
store the data in the candidate region.
27. The medium of claim 26 , including instructions to determine whether the memory includes a second region that is contiguous in the plurality of dimensions of the memory corresponding to the requested amount that is a second candidate in response to the subset of the information indicating that the candidate region is not unallocated.
28. The medium of claim 27 , wherein the subset of the information indicates that the candidate region is not unallocated if the region is partially allocated.
29. The medium of claim 27 , including instructions to scan a second subset of the information indicating whether each allocable portion of the memory is unallocated in response a determination that the memory includes the second candidate region, wherein the second subset of the information corresponds to the second candidate region only.
30. The medium of claim 26 , including instructions to return a null point in response to not converging on a region that is contiguous in the plurality of dimensions of the memory and is unallocated.