1. A method, performed by a processor, for managing data in a data storage having data deduplication, comprising: in response to a portion of the data storage determined to be inaccessible, querying an identifier of a user data segment by examining a corresponding back reference data structure; wherein: if the outcome of the query is negative, the user data segment is determined not associated with the particular storage block, and if the outcome of the query is positive, the user data segment is warranted be examined further to determine if the user data segment is associated with the particular storage block.