Linked lists in flash memory

• US 10,261,704 B1
• Filed: 06/29/2016
• Issued: 04/16/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:
  US15/196,261
• Time in Patent Office: 1,021 Days
• 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/0619 in relation to data integrity, e.g. data losses, bit errors
• 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]

Abstract

Systems and methods for managing content in a flash memory. A data structure such as a linked is implemented in flash memory. Nodes can be added to the linked list by overwriting portions of the node when only sets are required to update the node. The nodes may include multiple pointer portions such that existing pointers can be invalided and open pointer portions used for the update to the node.

Claims

1. A method for implementing a linked list in a flash memory, the method comprising:

storing nodes of a linked list in the flash memory;

inserting a node into the linked list between a first node and a second node such that the first node links to the node and the node links to the second node, each of the node, the first node and the second node including a data portion and a pointer portion, the pointer portion including a first next pointer portion and a second next pointer portion, wherein the first next pointer portion and the second next pointer portion are not used at the same time to point to a next node; and

updating a first next pointer of the first node in the linked list by overwriting the first next pointer of the first node with a new next pointer to the inserted node when updating the first next pointer only requires setting bits in the pointer portion,

wherein the first next pointer of the first node is updated by storing the new next pointer in a table in a memory separate from the flash memory when the first next pointer and the second next pointer of the previous node cannot be updated by only setting bits in the pointer portion.

2. The method of claim 1, wherein the pointer portion of the first node includes an invalid bit.

3. The method of claim 2, further comprising setting the invalid bit to a 1 and writing the new next pointer to the inserted node to the table stored in the memory.

4. The method of claim 1, further comprising setting the first next pointer of the first node to a value that indicates that the first next pointer is invalid and writing the new next pointer to the inserted node to the second next pointer of the first node.

5. The method of claim 1, further comprising setting bits in the first next pointer to an invalid value and overwriting the second next pointer with the new next pointer to the inserted node.

6. The method of claim 1, wherein the linked list is associated with the table in the memory, further comprising updating the next pointer of the first node by writing the new next pointer to the inserted node to an entry in the table and overwriting the pointer portion to a value that indicates that the pointer portion is invalid when the pointer portion does not include an invalid bit or setting the invalid bit when the pointer portion includes the invalid bit.

7. The method of claim 1, further comprising traversing the previous node by locating the new next pointer to the inserted node when the pointer portion of the first node indicated that the next pointer stored therein is invalid, wherein the new next pointer is stored in the table in the memory or in the second pointer portion.

8. The method of claim 1, further comprising deleting a node from the linked list by marking the data portion of the node to be deleted as invalid, wherein the data portion is marked as invalid by overwriting the data portion to all 1s or setting at least some of the bits in the data portion to indicate an invalid status, or setting an invalid data bit if there is an invalid bit in the data portion.

9. The method of claim 8, further comprising traversing the linked list by skipping any nodes whose data portions are marked invalid, and continuing to the next node in the linked list via the next pointer of the node whose data portion is marked as invalid.

10. The method of claim 1, further comprising deleting a node from the linked list by overwriting a next pointer of a previous node or setting a new next pointer in the previous node either in the second next pointer of the previous node or in an in-memory table.

11. A flash memory configured to implement a linked list in the flash memory, the flash memory comprising:

a linked list stored in the flash memory, the linked list including a plurality of nodes, wherein each node includes a data portion, a first pointer portion, and a second pointer portion, wherein the first pointer portion and the second pointer portion are not used at the same time to point to a linked node;

a controller configured to insert nodes into a linked list stored in the flash memory, the linked list including a plurality of nodes wherein each node includes a data portion, a first pointer portion, and a second pointer portion, wherein the first pointer portion and the second pointer portion are not used at the same time, wherein the controller inserts nodes into the linked list or removes nodes from the linked list by overwriting the first pointer portion of nodes affected by the insertion or removal of a node, wherein the first pointer portions of nodes are only overwritten when new values for the first pointer portions of the nodes require bits in the first pointer portions of the nodes to be set,

wherein the new values for the portions of the nodes are stored in a table in a memory that is separate from the flash memory when the first pointer portions of the nodes and the second pointer portions of the nodes cannot be overwritten by only setting bits.

12. The flash memory of claim 11, where the controller inserts a node between a first node of the linked list and a second node of the linked list by overwriting a first pointer portion of the first node with a new next pointer.

13. The flash memory of claim 12, wherein the controller overwrites the first pointer portion of the first node by:

setting an invalid bit in the first pointer portion of the first node to mark the next pointer of the first node as invalid and overwriting the second pointer portion of the first node with the next pointer to the inserted node.

14. The flash memory of claim 12, wherein the controller overwrites the first pointer portion of the first node by:

setting at least some of the bits in the first pointer portion of the first node to mark the first next pointer of the first node as invalid and overwriting the second pointer portion of the first node with a next pointer to the inserted node.

15. The flash memory of claim 12, further comprising a memory, wherein the controller overwrites the first pointer portion of the first node by:

setting at least some of the bits in the first pointer portion of the first node or an invalid bit to mark the next pointer of the first node as invalid and adding the next pointer to the inserted node to the table in the memory.

16. The flash memory of claim 15, wherein the controller rewrites nodes of the linked list as new linked list nodes at a new location in the flash memory using entries in the table in the memory.

17. The flash memory of claim 12, wherein the controller overwrites the portions of the nodes using a logical OR operation or a compare and swap operation.

18. The flash memory of claim 16, further comprising erasing the linked list nodes that are not valid.

19. The flash memory of claim 12, further comprising inserting a node after an end node of the linked list by overwriting a first pointer portion of the end node with a next pointer to the inserted node at the end of the linked list, wherein the first pointer portion of the end node is initially set to all 0s when the end node is the last node in the linked list.

20. A method for implementing a linked list in a flash memory, the method comprising:

writing nodes of a linked list to the flash memory, wherein each node includes a data portion for storing data, a first pointer portion, and a second pointer portion, wherein the first next pointer portion and the second next pointer portion are not used at the same time to point to a node; and

associating the linked list with a table in a memory that is separate from the flash memory, wherein entries in the table are configured for storing pointers associated with the linked list; and

inserting a new node into the linked list between a first node of the linked list and a second node of the linked list in the flash memory by;

overwriting a first pointer portion of the first node to mark the first pointer portion of the first node as invalid; and

adding a new next pointer that points to the inserted node from the first node by;

overwriting the second pointer portion of the first node with the new next pointer only when overwriting the second pointer portion can be performed by setting bits in the second pointer portion, wherein the second pointer portion is not overwritten with the new next pointer when bits in the second pointer portion need to be unset;

or

writing the new next pointer to an entry in the table in the memory.

21. The method of claim 20, wherein the first pointer portion and the second pointer portion are overwritten using a logical OR operation or a compare and swap operation.

22. The method of claim 20, further comprising rewriting the linked list as a new linked list to a new location in the flash memory, wherein the new linked list incorporates the entries in the table into the pointer portions of the nodes and wherein the original linked list is marked for erasure.

23. The method of claim 20, further comprising overwriting the first pointer portion by setting the bits to a value indicating that the first pointer portion is invalid or by setting an invalid bit in the first pointer portion.