Central processing unit cache friendly multithreaded allocation

Abstract

A cluster allocation bitmap determines which clusters in a band of storage remain unallocated. However, concurrent access to a cluster allocation bitmap can cause CPU stalls as copies of the cluster allocation bitmap in a CPU's level 1 (L1) cache are invalidated by another CPU allocating from the same bitmap. In one embodiment, cluster allocation bitmaps are divided into L1 cache line sized and aligned chunks. Each core of a multicore CPU is directed at random to allocate space out of a chunk. Because the chunks are L1 cache line aligned, the odds of the same portion of the cluster allocation bitmap being loaded into multiple L1 caches by multiple CPU cores is reduced, reducing the odds of an L1 cache invalidation. The number of CPU cores performing allocations on a given cluster allocation bitmap is limited based on the number of chunks with unallocated space that remain.

The invention claimed is: 
     
       1. A method for storage allocation on a computing device comprising a multi-core central processing unit (CPU), each CPU core having a non-shared cache, the method comprising:
 receiving, at a filesystem allocator, a plurality of storage allocation requests, each executing on a different core of the multi-core CPU, wherein the storage allocation requests are for a file system volume that is divided into bands composed of a plurality of storage clusters, and wherein, for each band, storage clusters are marked as allocated or unallocated by a corresponding cluster allocation bitmap; 
 dividing a cluster allocation bitmap into a plurality of chunks, wherein each chunk is the size of a cache line of the non-shared cache, wherein each chunk is aligned in system memory with the non-shared cache lines of the non-shared cache, and wherein a chunk status bitmap indicates which of the plurality of chunks has at least one unallocated cluster; 
 determining a maximum number of storage allocation requests allowed to concurrently search for available space in the cluster allocation bitmap based on a number of chunks containing at least one unallocated cluster; 
 allowing each of the plurality of storage allocation requests, up to the maximum number, to search for unallocated space within the cluster allocation bitmap; and 
 when a requested amount of unallocated space is found, allocating the unallocated space by modifying the cluster allocation bitmap with an interlocked operation. 
 
     
     
       2. The method of  claim 1 , wherein up to the maximum number of storage allocation requests are allowed to execute concurrently. 
     
     
       3. The method of  claim 1 , wherein the storage allocation requests are for an amount of space contained in less than 32 clusters of storage space. 
     
     
       4. The method of  claim 1 , wherein the chunk status bitmap indicates, by default, that a chunk has at least one unallocated cluster, and wherein the chunk status bitmap is changed to indicate a chunk no longer has at least one unallocated cluster in response to a search of that chunk failing to allocate the requested space. 
     
     
       5. The method of  claim 1 , wherein, when a storage allocation request is for more space than can be allocated using interlocked operations, granting that storage allocation request exclusive access to a band. 
     
     
       6. The method of  claim 1 , wherein searching for unallocated space within the cluster allocation bitmap includes beginning the search at a start of a randomly chosen chunk, and wherein, upon not finding the requested storage, modifying the chunk status bitmap to indicate the randomly chosen chunk does not have an available cluster. 
     
     
       7. A computing device for storage allocation on a computing device comprising a multi-core central processing unit (CPU), each CPU core having a non-shared cache, the computing device comprising:
 one or more processors; 
 a memory in communication with the one or more processors, the memory having computer-readable instructions stored thereupon which, when executed by the one or more processors, cause the computing device to:
 receive, at a filesystem allocator, a plurality of storage allocation requests, each executing on a different core of the multi-core CPU, wherein the storage allocation requests are for a file system volume that is divided into bands composed of a plurality of storage clusters, and wherein, for each band, storage clusters are marked as allocated or unallocated by a corresponding cluster allocation bitmap; 
 divide a cluster allocation bitmap into a plurality of chunks, wherein each chunk is the size of a cache line of the non-shared cache, wherein each chunk is aligned in system memory with the non-shared cache lines of the non-shared cache, and wherein a chunk status bitmap indicates which of the plurality of chunks has at least one unallocated cluster; 
 determine a maximum number of storage allocation requests allowed to concurrently search for available space in the cluster allocation bitmap based on a number of chunks containing at least one unallocated cluster; 
 for each of the storage allocation requests, up to the maximum number, selecting one of the plurality of chunks at random and begin searching for unallocated space at the address of that chunk; and 
 when a requested amount of unallocated space is found, allocating the unallocated space by modifying the cluster allocation bitmap with an interlocked operation. 
 
 
     
     
       8. The computing device of  claim 7 , wherein the maximum number of the plurality of storage allocation requests allowed to concurrently search for available space in the cluster allocation bitmap is half the number of chunks containing unallocated space. 
     
     
       9. The computing device of  claim 8 , wherein the maximum number of the plurality of storage allocation requests allowed to concurrently search for available space in the cluster allocation bitmap is increased for every core in the multi-core CPU above 4 and decreased for every core in the multi-core CPU below 4. 
     
     
       10. The computing device of  claim 7 , the memory having computer-readable instructions stored thereupon which, when executed by the one or more processors, further cause the computing device to, for each storage allocation request:
 determine a random number n from 0 to the number of chunks containing unallocated space; and 
 assign the storage allocation request to nth chunk containing unallocated space. 
 
     
     
       11. The computing device of  claim 7 , wherein searching a chunk for unallocated space includes loading the chunk into the non-shared cache of the core performing the search, and wherein assigning different storage allocation requests to search different chunks causes each bit of cluster allocation bitmap to be loaded into at most one non-shared cache, such that modifying the cluster allocation bitmap does not invalidate a portion of the cluster allocation bitmap loaded into a different non-shared cache. 
     
     
       12. The computing device of  claim 7 , wherein a band comprises 64 megabytes (MB) of storage, wherein a storage cluster comprises 4 kilobytes (kB), wherein a cluster allocation bitmap comprises 16,384 bits, wherein a non-shared cache line comprises 64 bytes, and wherein each cluster allocation bitmap is divided into 32 64 byte chunks. 
     
     
       13. The computing device of  claim 7 , wherein the maximum number of the plurality of storage allocation requests allowed to concurrently search for available space in the cluster allocation bitmap is calculated dynamically, including increasing the maximum number when a detected percentage of storage allocation request failures due to contention falls below a defined threshold and reducing the maximum number when the detected percentage of storage allocation request failures due to contention rises above a second defined threshold. 
     
     
       14. The computing device of  claim 7 , wherein contention caused by two storage allocation requests attempting to allocate storage in the same chunk is detected when one of the two storage allocation requests fails, and wherein in response to a storage allocation request failure, directing the storage allocation request to retry using another band. 
     
     
       15. A method for storage allocation on a computing device comprising a multi-core central processing unit (CPU), each CPU core having a non-shared cache, the method comprising:
 receiving, at a filesystem allocator, a request to allocate an amount of storage on a file system volume that is divided into bands, wherein each band is composed of a plurality of storage clusters, and wherein, for each band, storage clusters are marked as allocated or unallocated by a corresponding cluster allocation bitmap; 
 dividing a cluster allocation bitmap into a plurality of chunks, wherein each chunk is the size of a cache line of the non-shared cache, and wherein each chunk is aligned in system memory with the non-shared cache lines of the non-shared cache; 
 determining an address within the cluster allocation bitmap based on an address of a selected chunk of the plurality of chunks; 
 searching, beginning at the determined address, the cluster allocation bitmap for unallocated space; and 
 allocating the unallocated space when the amount of unallocated space is identified. 
 
     
     
       16. The method of  claim 15 , wherein searching at the determined address includes searching the selected chunk of the plurality of chunks. 
     
     
       17. The method of  claim 15 , wherein the chunk is selected randomly from a subset of the plurality of chunks that have not been marked as full. 
     
     
       18. The method of  claim 15 , wherein searching for unallocated space beginning at an address of a first chunk causes the CPU to load the chunk into a line of the non-shared cache, such that, another CPU core searching the same cluster allocation bitmap, but beginning at an address of a second chunk, does not also load a portion of the first chunk into a non-shared cache of the other CPU. 
     
     
       19. The method of  claim 15 , wherein the request to allocate an amount of storage on the file system volume is one of a plurality of concurrently executing requests to allocate storage on the file system volume, wherein each of the concurrently executing requests to allocate storage are executing on different cores of the multi-core CPU, and wherein each of the plurality of requests begins searching the cluster allocation bitmap at an address of a different chunk of the plurality of chunks. 
     
     
       20. The method of  claim 15 , wherein allocating the unallocated space includes setting bits in the cluster allocation bitmap from 0 to 1 for each allocated cluster.