PATENT CLAIM ANALYSIS

Application Number: 15898407
Application Type: Utility
Filing Date: 2018-02
Publication Date: 2019-08
Patent Classification: ["711", "117000"]

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.

Claim (Index 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:\n 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:\n 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; \n 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; \n 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; \n 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 \n when a requested amount of unallocated space is found, allocating the unallocated space by modifying the cluster allocation bitmap with an interlocked operation.

Metadata:
- Claim Count in Document: 5.0
- Percentile: 88.0
- Lexical Diversity: 1.89412
- Patent Class: 711.0
- Transitional Phrase Type: open
- Component Type: 1
- Foreign Priority: False
- Related Applications: ['15898414', '15626101', '15607003', '11267938', '14943896']

Analysis Scores:
- 35 USC 101 Eligibility (BERT): 0.526966047377539
- 35 USC 102 Novelty (BERT): 0.5608157368993927
- Combined Prediction Score: 0.5303510163297245
- Mean Citation Score: 260.687412
- Max Citation Score: 461.45895
- Similarity Product: 364.2783270817101

Labels:
- Claim Label 101: 1
- Claim Label 102: 1
- Claim Label 103: 1
- Claim Label 112: 1
- Combined Label: 1
- Label 101 Adjusted: 1

Dataset: test