Translation table and method for compressed data

摘要

A translation table has entries that each include a share bit and a delta bit, with pointers that point to a memory block that includes reuse bits. When two translation table entries reference identical fragments in a memory block, one of the translation table entries is changed to refer to the same memory block referenced in the other translation table entry, which frees up a memory block. The share bit is set to indicate a translation table entry is sharing its memory block with another translation table entry. In addition, a translation table entry may include a private delta in the form of a pointer that references a memory fragment in the memory block that is not shared with other translation table entries. When a translation table has a private delta, its delta bit is set.

主权项

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.