Conditional Iteration for a Non-Volatile Device

• US 20140325115A1
• Filed: 07/18/2013
• Published: 10/30/2014
• Est. Priority Date: 04/25/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Ramsundar, Bharath, Talagala, Nisha, Sundararaman, Swaminathan
• Granted Patent: US 9,519,575 B2
• Time in Patent Office: Days
• US Class Current: 711/102
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

Apparatuses, systems, methods, and computer program products are disclosed for conditional iteration. A method includes receiving a request comprising a condition. A method includes checking an address mapping structure for entries satisfying a condition for a request. A method includes providing a result for a request based on one or more entries satisfying a condition for a request.

Claims

1. A method comprising:

receiving a request associated with an iteration condition;

checking an address mapping structure for entries satisfying the iteration condition for the request; and

providing a result for the request based on one or more entries satisfying the iteration condition for the request.

2. The method of claim 1, wherein checking the address mapping structure is performed in kernel-space such that entries of the address mapping structure failing to satisfy the iteration condition are not copied to user-space.

3. The method of claim 2, wherein the request comprises a system call received in kernel-space from a client executing in user-space.

4. The method of claim 1, wherein the iteration condition is defined by a client from which the request is received.

5. The method of claim 4, further comprising validating the client defined iteration condition and adding the validated iteration condition to a condition library for selection by clients in requests.

6. The method of claim 1, further comprising limiting the result to entries which a requesting client has permission to access.

7. The method of claim 1, wherein the result comprises a result set including a member for each entry that satisfies the iteration condition for the request.

8. The method of claim 1, wherein the result comprises a result for a next entry satisfying the iteration condition for the request relative to an iterator position in the address mapping structure.

9. The method of claim 1, wherein the address mapping structure comprises a logical-to-physical address mapping structure comprising entries mapping logical addresses for data to physical locations of the data in a non-volatile recording media.

10. The method of claim 9, wherein the iteration condition applies to the logical addresses of the address mapping structure such that the entries of the address mapping structure are checked without accessing the data in the non-volatile recording medium.

11. The method of claim 9, wherein the iteration condition applies to metadata stored in the entries of the address mapping structure with the logical addresses such that the entries of the address mapping structure are checked without accessing the data in the non-volatile recording medium.

12. The method of claim 11, wherein the metadata comprises time sequence metadata associated with an order in which the data was written to the non-volatile recording medium.

13. The method of claim 11, wherein the logical addresses are members of a sparse logical address space and at least one entry in the address mapping structure is associated with a key-value pair, and a key of the key-value pair is encoded by a logical address of the at least one entry.

14. The method of claim 13, wherein the iteration condition applies to the key of the key-value pair.

15. The method of claim 13, wherein the logical address of the at least one entry includes a value address portion that does not encode the key for the key-value pair, the value address portion sized to address at least a maximum size for a value of the key-value pair.

16. The method of claim 15, wherein the value address portion encodes a pool identifier for the key-value pair and the iteration condition applies to the pool identifier.

17. An apparatus comprising:

a mapping module configured to maintain a logical-to-physical mapping structure, the logical-to-physical mapping structure mapping logical addresses for data to locations for the data in a sequential log structure of a non-volatile memory media;

a condition module configured to locate an entry in the logical-to-physical mapping structure, the entry satisfying a predicate of an iteration request; and

a result module configured to return a result based on the located entry.

18. The apparatus of claim 17, further comprising a position module configured to determine an iterator position in the logical-to-physical mapping structure, the entry located by the condition module comprising a next entry relative to the iterator position in the logical-to-physical mapping structure, wherein the next entry is next relative to the iterator position in one of a logical address order and a temporal order for the entries.

19. The apparatus of claim 17, further comprising a validation module configured to validate security of the predicate of the iteration request and a condition library module configured to add the validated predicate to a condition library for selection by clients in iteration requests.

20. An apparatus comprising:

means for traversing entries of a logical-to-physical mapping structure for a non-volatile storage device;

means for matching an entry in the logical-to-physical mapping structure to a filter definition without accessing a non-volatile storage medium of the non-volatile storage device; and

means for performing an action for the matching entry.