Memory paging system and method including compressed page mapping hierarchy

In a memory paging system for a computer having an execution unit, a memory including a hierarchy of data stores for encoding a mapping from virtual memory addresses to physical memory addresses, and a translation lookaside buffer for caching recently-used virtual to physical address mappings, a compression/decompression subsystem comprising:

• a compression/decompression engine coupled between the execution unit and the memory for alternately compressing and expanding memory-resident pages;
• means residing in the hierarchy of data stores for identifying a compression state of memory-resident pages, the compression state identifying means triggering a compression fault upon a spill from the translation lookaside buffer, the compression state identifying means triggering a decompression fault upon an access to a memory page not represented in the translation lookaside buffer and identified as compressed by the compression state identifying means;
• a decompression fault handler responsive to the decompression fault, the decompression fault handler allocating memory for a decompressed memory page, triggering a decompression operation of the compression/decompression engine, and updating the hierarchy of data stores in accordance with the decompression operation;
• and
• a compression fault handler responsive to the compression fault, the compression fault handler scanning a free-list for a target memory block, triggering compression operation of the compression/decompression engine, and updating the hierarchy of data stores in accordance with the compression operation.

In a memory paging and compression system, a method for handling a decompression fault arising from a faulting memory access, the method comprising the steps of:

• allocating a new memory page;
• supplying a physical address of the new memory page to a compression/decompression engine;
• supplying a virtual address of the faulting memory access to the compression/decompression engine;
• triggering decompression by the compression/decompression engine, the decompression being from a compressed representation of the page corresponding to the faulting memory access to an uncompressed representation of same at the new memory page;
• and
• updating an address mapping hierarchy to indicate the physical address of the new memory page and uncompressed state of the corresponding page.

In a memory paging and compression system, a method for handling a compression fault, the method comprising the steps of:

• scanning a free-list for a new block in a compressed memory space;
• supplying a physical address of the new block to a compression/decompression engine;
• supplying a virtual address of a faulting memory access to the compression/decompression engine;
• triggering compression by the compression/decompression engine, the compression being from an uncompressed representation of the page corresponding to the faulting memory access to an compressed representation of same at the new block;
• updating an address mapping hierarchy to indicate a compressed state of the corresponding page;
• and
• updating a compressed page mapping hierarchy to indicate the physical address and size of the corresponding compressed representation.