Data invalidation acceleration through approximation of valid data counts

1. A non-volatile data storage device in communication with a host device, comprising:

a memory device having physical storage locations;

a cache memory configured to store a count value for each of the physical storage locations of the memory device and a map table having a plurality of entries associated with an address range A 1 to A x where a value of x is greater than 1; and

a controller configured to be responsive to a data invalidation request received from the host device which invalidates the address range A 1 to A x by invalidating a subset of the plurality of entries associated with the address range A 1 to A x , and decrementing a count value for the subset of the plurality of entries, wherein the subset of the plurality of entries comprises a number of entries less than the value of x.

2. The non-volatile data storage device of claim 1 , wherein the controller is further configured to determine an integer value N based on information in the data invalidation request, wherein N is greater than 1.

3. The non-volatile data storage device of claim 2 , wherein the controller is further configured to read every Nth entry of the plurality of entries.

4. The non-volatile data storage device of claim 2 , wherein the controller is further configured to decrement the count value for the subset of the plurality of entries by decrementing the count value of every Nth entry of the plurality of entries.

5. The non-volatile data storage device of claim 2 , wherein the controller is further configured to decrement the count value for the subset of the plurality of entries by decrementing, by the integer value N, the count value of every Nth entry of the plurality of entries.

6. The non-volatile data storage device of claim 2 , wherein the information includes a parameter specifying the value of x and wherein the controller is further configured to determine the integer value N based on the parameter.

7. The non-volatile data storage device of claim 6 , wherein the controller is further configured to assign a first value to the integer value N if the value of x falls within a first band of values.

8. The non-volatile data storage device of claim 7 , wherein the controller is further configured to assign the integer value N a second value if the value of x falls within a second band of values.

9. The non-volatile data storage device of claim 2 , wherein the information includes an execution parameter specifying the integer value N.

10. The non-volatile data storage device of claim 2 , further comprising:

wherein the controller is further configured to determine the integer value N based on a current usage of a processor of the non-volatile data storage device.

11. The non-volatile data storage device of claim 10 , further comprising:

wherein the controller is further configured to assign a first value to the integer value N if the current usage of the processor falls within a first band of usage values that is defined by a first and second threshold value.

12. The non-volatile data storage device of claim 2 , wherein the information includes a parameter specifying a maximum completion time for the execution of the data invalidation request.

13. The non-volatile data storage device of claim 12 , wherein the controller is further configured to calculate the number of entries in the subset of the plurality of entries based on the maximum completion time.

14. A method for executing a data invalidation command by a storage device, comprising:

receiving a data invalidation request;

responsive to the data invalidation request which invalidates an address range A 1 to A x , invalidating a subset of a plurality of entries in a map table based on the address range A 1 to A x where a value of x is greater than 1; and

decrementing a count value for the subset of the plurality of entries, wherein the subset of the plurality of entries comprises a number of entries less than the value of x.

15. The method of claim 14 , further comprising

calculating an integer value N based on information in the data invalidation request, the integer value N being less than the value of x and greater than 1.

16. The method of claim 15 , further comprising reading every Nth entry of the plurality of entries.

17. The method of claim 15 , wherein decrementing the count value for the subset of the plurality of entries comprises decrementing the count value of every Nth entry of the plurality of entries.

18. The method of claim 15 , wherein decrementing the count value for the subset of the plurality of entries comprises decrementing the count value of every Nth entry of the plurality of entries by the integer value N.

19. The method of claim 15 , wherein the information includes a parameter specifying the value of x and further comprising calculating the integer value N based on the parameter.

20. The method of claim 19 , further comprising assigning a first value to the integer value N if the value of x falls within a first band of values.

21. The method of claim 20 , further comprising assigning a second value to the integer value N if the value of x falls within a second band of usage values.

22. The method of claim 15 , wherein the information includes an execution parameter specifying the value of N.

23. The method of claim 15 , further comprising determining the integer value N based on a current usage of a processor of the storage device.

24. The method of claim 23 , further comprising assigning a first value to the integer value N if the current usage of the processor falls within a first band of usage values.

25. The method of claim 15 , wherein the information includes a parameter specifying a maximum completion time for execution of the data invalidation request.

26. The method of claim 25 , further comprising calculating the number of entries in the subset of the plurality of entries based on the maximum completion time.