Optimized boot operations within a flash storage array

• US 10,296,354 B1
• Filed: 01/21/2015
• Issued: 05/21/2019
• Est. Priority Date: 01/21/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Sanvido, Marco, Hankins, Richard, McAuliffe, Mark, Cheng, HuiHui, Doshi, Nidhi, Neelakantam, Naveen, Vachharajani, Neil
• Primary Examiner(s): Rehman, Mohammed H
• Application Number:
  US14/602,052
• Time in Patent Office: 1,581 Days
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1024 Latency reduction
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 9/4401 Bootstrapping security arrangements therefor G06F21/57
• CPC Class Codes: G06F 9/4408 Boot device selection

Abstract

A system and method for efficiently starting up a plurality of solid-state storage devices. A computing system includes one or more storage devices storing data in multiple allocation units (AUs). In a boot region, a data storage controller maintains an AU management set that identifies a state of various AUs in the system. In various embodiments, the management set includes an identification of a subset of free AUs, transitional AU, unincorporated AUs, and speculative AUs. At various times, information corresponding to the AU management set is stored to non-volatile storage. During a boot sequence, the AU management set information is accessed and the identified AUs are searched to identify allocated AUs rather than performing a search of all of the AUs in the system.

Claims

1. An apparatus for identifying and accessing available memory blocks in a flash storage system, the apparatus configured to:

build a management set that identifies a subset of the memory blocks of the free block list, one or more transitional memory blocks, one or more unincorporated memory blocks, and one or more speculative memory blocks;

before shutdown of the flash storage system, generate a free block list of the memory blocks that are available on the flash storage system; and

during bootup of the flash storage system;

for each memory block on the free block list, determine if the memory block has been correctly listed as available or has been allocated; and

identify all currently available memory blocks in dependence upon determining if the memory block has been correctly listed as available or has been allocated.

2. The apparatus as recited in claim 1, wherein the apparatus is further configured to:

identify a given memory block identified as most recently allocated, wherein the given memory block identified as most recently allocated corresponds to a last memory block whose identification was stored to persistent storage before a bootup sequence; and

identify all memory blocks allocated after the given memory block based on a search of the memory blocks of the free block list.

3. The apparatus as recited in claim 2, wherein the apparatus is configured to use an indication of allocated memory blocks stored in persistent storage with said one or more memory blocks allocated after the given memory block to identify all allocated memory blocks in the flash storage system and all available memory blocks in the flash storage system without a search of memory blocks other than the memory blocks of the free block list.

4. The apparatus as recited in claim 1, wherein the apparatus is further configured to store an indication of allocated memory blocks in the flash storage system responsive to detecting a condition.

5. The apparatus as recited in claim 1, wherein the apparatus is further configured to allocate only memory blocks from the memory blocks of the free block list.

6. The apparatus recited in claim 1, wherein the apparatus is further configured to store an identification of the memory blocks of the free block list to persistent memory responsive to detecting a condition.

7. A method for identifying and accessing available memory blocks in a flash storage system, the method comprising:

building a management set that identifies a subset of the memory blocks of the free block list, one or more transitional memory blocks, one or more unincorporated memory blocks, and one or more speculative memory blocks;

before shutdown of the flash storage system, generating a free block list of the memory blocks that are available on the flash storage system; and

during bootup of the flash storage system;

for each memory block on the free block list, determining if the memory block has been correctly listed as available or has been allocated; and

identifying all currently available memory blocks in dependence upon determining if the memory block has been correctly listed as available or has been allocated.

8. The method as recited in claim 7, further comprising:

identifying a given memory block identified as most recently allocated, wherein the given memory block identified as most recently allocated corresponds to a last memory block whose identification was stored to persistent storage before a bootup sequence; and

identifying all memory blocks allocated after the given memory block based on a search of the memory blocks of the free block list.

9. The method as recited in claim 8, further comprising using an indication of allocated memory blocks stored in persistent storage with said one or more memory blocks allocated after the given memory block to identify all allocated memory blocks in the flash storage system and all available memory blocks in the flash storage system without a search of memory blocks other than the memory blocks of the free block list.

10. The method as recited in claim 7, further comprising storing an indication of allocated memory blocks in the flash storage system responsive to detecting a condition.

11. The method as recited in claim 7, further comprising allocating only memory blocks from the memory blocks of the free block list.

12. The method as recited in claim 7, further comprising storing an identification of the one or more free memory blocks to persistent memory responsive to detecting a condition.

13. A non-transitory computer readable storage medium for identifying and accessing available memory blocks in a flash storage system, the storage medium storing program instructions executable by a processor to:

build a management set that identifies a subset of the memory blocks of the free block list, one or more transitional memory blocks, one or more unincorporated memory blocks, and one or more speculative memory blocks;

before shutdown of the flash storage system, generate a free block list of the memory blocks that are available on the flash storage system; and

during bootup of the flash storage system;

for each memory block on the free block list, determine if the memory block has been correctly listed as available or has been allocated; and

identify all currently available memory blocks in dependence upon determining if the memory block has been correctly listed as available or has been allocated.

14. The non-transitory computer readable storage medium as recited in claim 13, further comprising program instructions executable by the processor to:

identify a given memory block identified as most recently allocated, wherein the given memory block identified as most recently allocated corresponds to a last memory block whose identification was stored to persistent storage before a bootup sequence; and

identify all memory blocks allocated after the given memory block based on a search of the memory blocks of the free block list.

15. The non-transitory computer readable storage medium as recited in claim 13, wherein the program instructions are further executable to store an indication of allocated memory blocks in the flash storage system responsive to detecting a condition.

16. The non-transitory computer readable storage medium as recited in claim 15, wherein the program instructions are further executable to use an indication of allocated memory blocks stored in persistent storage with said one or more memory blocks allocated after the given memory block to identify all allocated memory blocks in the flash storage system and all available memory blocks in the flash storage system without a search of memory blocks other than the memory blocks of the free block list.

17. The non-transitory computer readable storage medium as recited in claim 13, wherein the instructions are further executable to allocate only memory blocks from the memory blocks of the free block list.

18. The non-transitory computer readable storage medium as recited in claim 13, wherein the instructions are further executable to store an identification of the memory blocks of the free block list to persistent memory responsive to detecting a condition.