A storage device includes a non-volatile semiconductor storage device including a plurality of physical blocks, and a controller. The controller is configured to maintain a mapping of logical addresses to locations within the physical blocks, send, to a host, a first list that contains logical addresses corresponding to one or more target physical block that are targeted for garbage collection, and then receive, from the host, a second list that contains one or more logical addresses in the first list, and invalidate data stored in the logical addresses in the second list prior to the garbage collection.