# US 2014/0195767 A1 · Lightweight Random Memory Allocation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195767 A1 - Document ID: US20140195767A1 - Status: Published application - Kind: A1 - Application number: 14/203,310 - Filed: 2014-03-10 - Published: 2014-07-10 - Earliest claimed: 2011-04-14 - Assignees: Microsoft Corporation - Applicants: Microsoft Corporation - Inventors: Gregory J. Colombo; Hari Pulapaka; Arun U. Kishan; Stephen L. Hufnagel; Garrett Trent Leischner; Evan Lincoln Tice; Matthew R. Miller - Web page: https://patentgrep.com/patent/US20140195767A1 ## CPC - G06F 3/0631: {by allocating resources to storage systems} - G06F 3/0671: {In-line storage system} - G06F 9/5016: {the resource being the memory} - G06F 12/0223: {User address space allocation, e.g. contiguous or non contiguous base addressing} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract In response to a memory allocation request received from an application thread, a random number is obtained (e.g., from a random number list previously populated with multiple random numbers). A starting location in at least a portion of a bitmap associated with a region including multiple blocks of the memory is determined based on the random number. A portion of the bitmap is scanned, beginning at the starting location, to identify a location in the bitmap corresponding to an available block of the multiple blocks, and an indication of this available block is returned to the application thread. ## Claims ### Claim 1 A method in a system, the method comprising: receiving, from an application thread, a request for memory to be allocated to the application thread, including an index value; obtaining a random number, the obtaining based on the received index value; determining, based on the random number, a starting location in at least a portion of a bitmap associated with a region including multiple blocks of the memory; scanning, beginning at the starting location, at least the portion of the bitmap to identify a location in the bitmap corresponding to an available block of the multiple blocks; and returning, to the application thread, an indication of the available block. ### Claim 2 (depends on 1) A method as recited in claim 1, the obtaining the random number comprising obtaining the random number from a list of previously generated random numbers. ### Claim 3 (depends on 2) A method as recited in claim 2, further comprising replacing, by a module of a memory allocator, one or more random numbers in the list with one or more new random numbers during performance of a high latency operation by the memory allocator that also performs the determining and the scanning. ### Claim 4 (depends on 2) A method as recited in claim 2, the obtaining the random number further comprising: obtaining the random number from a location in the list of previously generated random numbers identified by the index value; updating the index value; and wherein multiple additional application threads in the system requesting that memory be allocated have different associated index values. ### Claim 5 (depends on 1) A method as recited in claim 1, the portion of the bitmap including a number of bits equal to a native word size of a device implementing the system. ### Claim 6 (depends on 1) A method as recited in claim 1, the bitmap including multiple portions, the method further comprising selecting as the at least a portion of the bitmap one of the multiple portions having at least one location corresponding to an available block of the multiple blocks. ### Claim 7 (depends on 6) A method as recited in claim 6, the selecting further comprising: identifying a most recently freed block in the region; and selecting, as the at least a portion of the bitmap, the one of the multiple portions that includes a location corresponding to the most recently freed block. ### Claim 8 (depends on 1) A method as recited in claim 1, the determining the starting location comprising rotating the portion a number of times based on the random number to generate a rotated portion of the bitmap, and using a leftmost or rightmost location of the rotated portion as the starting location, the scanning comprising scanning the rotated portion. ### Claim 9 (depends on 8) A method as recited in claim 8, the rotating the portion a number of times based on the random number comprising rotating the portion a number of times equal to the random number. ### Claim 10 (depends on 8) A method as recited in claim 8, each location in the rotated portion having a first value indicating that the location corresponds to an unavailable block of the multiple blocks or a second value indicating that the location corresponds to an available block of the multiple blocks, the scanning comprising scanning the rotated portion, beginning at the starting location, for a next location in the rotated portion having the second value. ### Claim 11 (depends on 1) A method as recited in claim 1, the scanning comprising scanning, beginning at the starting location, for a next location in the bitmap having a value indicating that the location corresponds to an available block of the multiple blocks. ### Claim 12 (depends on 1) A method as recited in claim 1, the indication of the available block being a memory address of a beginning of the available block in the memory. ### Claim 13 One or more computer storage media having stored thereon multiple instructions that, when executed by one or more processors of a device, cause the one or more processors to: populate a random number list with multiple random numbers; receive, in response to a memory allocation request from an application thread, an index value associated with the application thread; obtain, based on the index value, a random number from the random number list; identify, by scanning a portion of a data structure associated with a region including multiple blocks of memory, an available block of the multiple blocks, the scanning beginning at a location determined based on the random number; and return, to the application thread, an indication of the identified available block. ### Claim 14 (depends on 13) One or more computer storage media as recited in claim 13, the multiple instructions implementing a memory allocator and further causing the one or more processors to replace one or more of the random numbers in the random number list with one or more new random numbers during performance of a high latency operation by the memory allocator. ### Claim 15 (depends on 13) One or more computer storage media as recited in claim 13, the instructions that cause the one or more processors to obtain the random number including instructions that cause the one or more processors to: obtain the random number from a location in the random number list identified by the index value; and update the index value. ### Claim 16 (depends on 13) One or more computer storage media as recited in claim 13, the data structure comprising a bitmap, and the instructions that cause the one or more processors to identify the available block comprising instructions that cause the one or more processors to: rotate a portion of the bitmap a number of times based on the random number to generate a rotated portion of the bitmap; and begin scanning the rotated portion at the leftmost or rightmost location of the rotated portion. ### Claim 17 (depends on 16) One or more computer storage media as recited in claim 16, the instructions that cause the one or more processors to rotate the portion of the bitmap a number of times comprising instructions that cause the one or more processors to rotate the portion a number of times equal to the random number. ### Claim 18 (depends on 17) One or more computer storage media as recited in claim 17, each location in the rotated portion having a first value indicating that the location corresponds to an unavailable block of the multiple blocks or a second value indicating that the location corresponds to an available block of the multiple blocks, the instructions that cause the one or more processors to begin scanning the rotated portion comprising instructions that cause the one or more processors to begin scanning the rotated portion at the leftmost or rightmost location of the rotated portion for a next location in the rotated portion having the second value. ### Claim 19 (depends on 13) One or more computer storage media as recited in claim 13, the index value being associated with a group of multiple application threads that include the application thread.