Garbage collection in a storage system

A method for use in a computing system, the method comprising:

• maintaining a first table comprising a plurality of entries, wherein each of the plurality of entries of the first table maps a virtual address to a location in a data storage medium;
• identifying one or more entries in a second table comprising a plurality of entries, wherein each of the one or more entries of the second table includes a reverse mapping of an address of a location in the data storage medium to one or more virtual addresses, and wherein said one or more entries are identified as corresponding to a given segment;
• in response to determining the second table includes a valid mapping for a virtual address included in an entry of the one of the one or more entries:
• copying data from a first location identified in the entry to a second location in the data storage medium;
• and
• reclaiming the first storage location;
• accessing the given segment and identifying further entries which comprise a mapping of a location in the segment to one or more virtual addresses;
• determining whether the first table includes a valid mapping for each of the further entries;
• copying data from a current storage location in the segment corresponding to a valid mapping in the further entries to a new storage location in the data storage medium;
• and
• reclaiming the current storage location.

A non-transitory computer readable storage medium comprising program instructions, wherein said program instructions are executable to:

• maintain a first table comprising a plurality of entries, wherein each of the plurality of entries of the first table maps a virtual address to a location in a data storage medium;
• identify one or more entries in a second table comprising a plurality of entries, wherein each of the one or more entries of the second table comprises a reverse mapping of an address of a location in the data storage medium to one or more virtual addresses, and wherein said one or more entries are identified as corresponding to a given segment;
• in response to determining the second table includes a valid mapping for a virtual address included in an entry of the one of the one or more entries:
• copy data from a first location identified in the entry to a second location in the data storage medium;
• and
• reclaim the first storage location;
• access the given segment and identify further entries which comprise a mapping of a location in the segment to one or more virtual addresses;
• determine whether the first table includes a valid mapping for each of the further entries;
• copy data from a current storage location in the segment corresponding to a valid mapping in the further entries to a new storage location in the data storage medium;
• and
• reclaim the current storage location.