Translation table and method for compressed data

1. An apparatus comprising:

a memory having a plurality of memory blocks; and

a translation table having a plurality of translation table entries, each translation table entry having a share bit and a plurality of pointers that each point to a memory fragment in a memory block in the memory, wherein the share bit is set on a first translation table entry when the first translation table entry includes at least one pointer that points to a memory fragment in the memory block that is shared with a second translation table entry, wherein each translation table entry includes a delta bit, wherein first and second translation table entries each have the share bits set and delta bits cleared when the first and second translation table entries have all pointers that point to memory fragments that are all shared by the first and second translation table entries, and wherein the first and second translation table entries each have the share bit set and the first translation table entry has the delta bit set when the first translation table entry includes at least one pointer that points to a memory fragment in the memory block that is shared with the second translation table entry and when the first translation table entry includes at least one pointer that points to a different memory fragment in the memory block that is not shared, wherein the first and second translation table entries each have the share bit cleared and the delta bit cleared when the plurality of pointers in the first translation table entry point to different memory blocks than the plurality of pointers in the second translation table entry.

2. The apparatus of claim 1 wherein the share bit on the first translation table entry is cleared when the first translation table entry does not share any memory fragments with any other translation table entry.

3. The apparatus of claim 1 wherein the different memory fragment in the memory block that is not shared comprises a private delta.

4. The apparatus of claim 1 wherein the delta bit on the first translation table entry is cleared when the first translation table entry does not point to a private delta.

5. The apparatus of claim 1 further comprising a reuse mechanism that identifies first and second memory blocks with identical content, changes a translation table entry corresponding to the first memory block to point to at least one memory fragment in the second memory block, releases the first memory block, and sets the share bit of the translation table entries corresponding to the first and second memory blocks.

6. The apparatus of claim 5 further comprising a signature mechanism that generates a digital signature for each of a plurality of memory blocks that include the first and second memory blocks, wherein the reuse mechanism identifies the first and second memory blocks have identical content by comparing a digital signature for the first memory block with a digital signature for the second memory block.

7. The apparatus of claim 1 wherein each memory block comprises a plurality of reuse bits indicating a number of the plurality of translation table entries that share at least one memory fragment in the memory block.

8. The apparatus of claim 7 further comprising a reuse mechanism that identifies first and second memory blocks with identical content, changes a translation table entry corresponding to the first memory block to point to at least one memory fragment in the second memory block, releases the first memory block, sets the share bit of the translation table entries corresponding to the first and second memory blocks, and sets the reuse bits in the second memory block to indicate the number of the plurality of translation table entries that share the at least one memory fragment in the memory block.

9. The apparatus of claim 8 further comprising a signature mechanism that generates a digital signature for each of a plurality of memory blocks, wherein the reuse mechanism identifies the first and second memory blocks have identical content by comparing a digital signature for the first memory block with a digital signature for the second memory block.

10. An apparatus comprising:

a memory having a plurality of memory blocks, each memory block comprising a plurality of reuse bits indicating reuse of the memory block;

a translation table having a plurality of translation table entries, each translation table entry having a share bit, a delta bit, and a plurality of pointers that each point to a memory fragment in a memory block, wherein the share bit is set on a first translation table entry when the first translation table entry includes at least one pointer that points to a memory fragment in the memory block that is shared with a second translation table entry, wherein the share bit on the first translation table entry is cleared when the first translation table entry does not share any memory fragments with any other translation table entry, wherein the delta bit on the first translation table entry is set when the first translation table entry includes at least one pointer that points to the memory fragment in the memory block that is shared with the second translation table entry and when the first translation table entry includes at least one pointer that points to a different memory fragment in the memory block that is not shared with the second translation table entry, wherein the different memory fragment in the memory block that is not shared comprises a private delta, wherein the delta bit is cleared on the first translation table entry when the first translation table entry does not point to a private delta;

a reuse mechanism that identifies first and second memory blocks with identical content, the first and second memory blocks having corresponding first and second translation table entries, changes the first translation table entry to point to at least one memory fragment in the second memory block, releases the first memory block, sets the share bit of the first and second translation table entries, and sets the reuse bits in the second memory block to indicate a number of the plurality of translation table entries that share the second memory block;

a signature mechanism that generates a digital signature for each of the plurality of memory blocks, wherein the reuse mechanism identifies the first and second memory blocks have identical content by comparing a digital signature for the first memory block with a digital signature for the second memory block.

11. An apparatus comprising:

a memory having a plurality of memory blocks, each memory block comprising a plurality of reuse bits indicating reuse of the memory block;

a translation table having a plurality of translation table entries, each translation table entry having a share bit, a delta bit, and a plurality of pointers that each point to a memory fragment in a memory block in the memory, wherein the share bit is set on a first translation table entry when the first translation table entry includes at least one pointer that points to a memory fragment in the memory block that is shared with a second translation table entry, wherein the first and second translation table entries each have the share bits set and delta bits cleared when the first and second translation table entries have all pointers that point to memory fragments that are all shared by the first and second translation table entries, and wherein the first and second translation table entries each have the share bit set and the first translation table entry has the delta bit set when the first translation table entry includes at least one pointer that points to a memory fragment in the memory block that is shared with the second translation table entry and when the first translation table entry includes at least one pointer that points to a different memory fragment in the memory block that is not shared, wherein the first and second translation table entries each have the share bit cleared and the delta bit cleared when the plurality of pointers in the first translation table entry point to different memory blocks than the plurality of pointers in the second translation table entry;

generating a digital signature for each of the plurality of translation table entries, wherein the digital signature for a selected translation table entry comprises a hash value computed for a tile of bytes of the selected translation table entry, wherein the tile of bytes comprises a subset of contiguous bytes of the selected translation table entry;

identifying third and fourth memory blocks with identical content by comparing a digital signature for the third memory block with a digital signature for the fourth memory block, wherein the third and fourth memory blocks have corresponding third and fourth translation table entries;

changing the third translation table entry corresponding to the third memory block to point to at least one memory fragment in the fourth memory block;

releasing the third memory block;

setting the share bit of the third and fourth translation table entries;

clearing the share bit on the third translation table entry when the third translation table entry does not share any memory fragments with any other translation table entry;

clearing the share bit on the fourth translation table entry when the fourth translation table entry does not share any memory fragments with any other translation table entry;

setting the delta bit on the third translation table entry when the third translation table entry includes at least one pointer that points to the memory fragment in the memory block that is shared with the fourth translation table entry and when the third translation table entry includes at least one pointer that points to a different memory fragment in the memory block that is not shared, wherein the different memory fragment in the memory block that is not shared comprises a private delta;

clearing the delta bit on the third translation table entry when the third translation table entry does not point to a private delta; and

setting the reuse bits in a memory block shared by the third and fourth translation table entries to indicate a number of the plurality of translation table entries that share the at least one memory fragment in the memory block.