Additive library for data structures in a flash memory

• US 10,521,123 B2
• Filed: 12/04/2018
• Issued: 12/31/2019
• Est. Priority Date: 06/29/2016
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Shilane, Philip N., Wallace, Grant R.
• Primary Examiner(s): Chappell, Daniel C.
• Application Number:
  US16/209,054
• Publication Number:
  US 20190107946A1
• Time in Patent Office: 392 Days
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 16/10 Programming or data input circuits
• CPC Class Codes: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators

Abstract

Systems and methods for managing data structures in a flash memory. A library is provided that supports read requests and write requests. The library allows reads and writes to be implemented without requiring the client to understand how the data structure is implemented in the flash memory.

Claims

1. A method for writing data to a data structure implemented in a flash memory, the method comprising:

receiving a write request from a client at the flash memory, wherein the flash memory includes a controller and a library that includes a plurality of calls that are performed by the controller, wherein the controller is configured to perform the write request, and wherein the write request is to write an update to a data structure stored in the flash memory in accordance with a particular call;

determining, by the controller, how to implement the write request in the flash memory, wherein the controller overwrites a location in the flash memory when an overwrite operation can be performed, wherein the update is written to an in-memory table or to a new location in the flash memory when the overwrite operation cannot be performed.

2. The method of claim 1, wherein the particular call is specified by the client in the write request.

3. The method of claim 1, wherein the particular call is determined by the controller.

4. The method of claim 1, wherein the write request includes the update and a location in the flash memory.

5. The method of claim 1, wherein the overwrite operation is performed when the write request only requires setting bits.

6. The method of claim 1, further comprising flushing contents of the in-memory table to the flash memory, wherein the contents are written to new locations in the flash memory when flushing the contents.

7. The method of claim 1, wherein the particular call is a logical OR operation or a compare and swap operation.

8. The method of claim 1, wherein the data structure includes a data portion and a pointer portion, wherein the data portion and the pointer portion can by overwritten independently.

9. A non-transitory computer readable medium comprising computer executable instructions that, when executed by a processor, perform a method for writing data to a data structure implemented in a flash memory, the method comprising:

receiving a write request from a client at the flash memory, wherein the flash memory includes a controller and a library that includes a plurality of calls that are performed by the controller, wherein the controller is configured to perform the write request wherein the write request is to write an update to a data structure stored in the flash memory in accordance with a particular call;

determining, by the controller, how to implement the write request in the flash memory, wherein the controller overwrites a location in the flash memory when an overwrite operation can be performed, wherein the update is written to an in-memory table or to a new location in the flash memory when the overwrite operation cannot be performed.

10. The non-transitory computer readable medium of claim 9, wherein the particular call is specified by the client in the write request.

11. The non-transitory computer readable medium of claim 9, wherein the particular call is determined by the controller.

12. The non-transitory computer readable medium of claim 9, wherein the write request includes the update and a location in the flash memory.

13. The non-transitory computer readable medium of claim 9, wherein the overwrite operation is performed when the write request only requires setting bits.

14. The non-transitory computer readable medium of claim 9, further comprising flushing contents of the in-memory table to the flash memory, wherein the contents are written to new locations in the flash memory when flushing the contents.

15. The non-transitory computer readable medium of claim 9, wherein the particular call is a logical OR operation or a compare and swap operation.

16. The non-transitory computer readable medium of claim 9, wherein the data structure includes a data portion and a pointer portion, wherein the data portion and the pointer portion can by overwritten independently.

17. A method for reading data from a data structure implemented in a flash memory, the method comprising:

receiving a read request from a client at the flash memory for data stored in a data structure, wherein the read request includes a location in the data structure, wherein the flash memory is associated with a library and a controller that are configured to support write requests and read requests, wherein the library includes a plurality of calls configured to perform the read requests and the write requests in the flash memory;

reading the data from the data structure at the location in the data structure stored in the flash memory;

applying updates to the data that are stored in an in-memory table, wherein the updates stored in the in-memory table correspond to writes to the requested data that were stored in the in-memory table instead of being written to the flash memory; and

returning the updated data to the client in response to the read request.

18. The method of claim 17, wherein the controller determines a particular call for the read request.

19. The method of claim 17, wherein the client specifies a particular call for the read request.

20. The method of claim 17, further comprising flushing the updates to the flash memory.