Hardware-base accelerator for managing copy-on-write of multi-level caches utilizing block copy-on-write differential update table

Patent metadata

Field	Value
Publication number	US-9304946-B2
Application number	US-201213813591-A
Country	US
Kind code	B2
Filing date	Jun 25, 2012
Priority date	Jun 25, 2012
Publication date	Apr 5, 2016
Grant date	Apr 5, 2016

Abstract

Technologies are described herein for providing a hardware-based accelerator adapted to manage copy-on-write. Some example technologies may identify a read request adapted to read a block at an original memory address. The technologies may utilize the hardware-based accelerator to determine whether the block is located at the original memory address. When a determination is made that the block is located in at the original memory address, the technologies may utilize the hardware-based accelerator to pass the original memory address so that the read request can be performed utilizing the original memory address. When a determination is made that the block is not located in the memory at the original memory address, the technologies may utilize the hardware-based accelerator to generate a new memory address and to pass the new memory address so that the read request can be performed utilizing the new memory address.

First claim

What is claimed is:

1. A method to provide a hardware-based accelerator adapted to manage copy-on-write in a memory of a computer, the method comprising:
identifying a read request adapted to read a block in the memory at an original memory address, wherein the original memory address comprises a page index, a page offset, and a block offset, wherein the page index comprises an index portion and a tag portion;
utilizing the hardware-based accelerator to determine whether the block is located in the memory at the original memory address based on a record in a lazy copy table, the record corresponding to a source page located at a source page index and a destination page located at a destination page index, wherein the record comprises a tag, a new page index, a copy-on-write status comprising a plurality of status identifiers, and a level identifier for the copy-on-write status ranging from a highest level of the copy-on-write status that corresponds to two or more blocks in the source page to a first level of the copy-on-write status that corresponds to a corresponding block in the source page, wherein each of the plurality of status identifiers comprises a status bit;
storing the tag in a first entry of the lazy copy table, the source page index in a second entry of the lazy copy table, at least one of the plurality of status identifiers in a third entry of the lazy copy table, and the level identifier in a fourth entry of the lazy copy table;
determining whether the copy-on-write status indicates that a block in the destination page has been modified from the corresponding block in the source page by recursively evaluating multiple instances of the copy-on-write status based on the level identifier in response to a determination that a quantity of the plurality of status identifiers in the copy-on-write status is less than a quantity of blocks in a page size of the memory, wherein recursively evaluating multiple instances of the copy-on-write status further comprises:
converting the page offset from a binary representation to a bitmap;
determining whether a result of a bitwise AND operation between the bitmap and the cop-on-write status equals zero;
responsive to determining that the result of the bitwise AND operation between the bitmap and the copy-on-write status does not equal zero, determining that the copy-on-write status indicates that the block in the destination page has been modified from the source page; and
responsive to determining that the result of the bitwise AND operation between the bitmap and the copy-on-write status equals zero, determining that the copy-on-write status indicates that the block in the destination page has not been modified from the source page;
in response to determination by the hardware-based accelerator that the block is located in the memory at the original memory address and the copy-on-write status indicates that the block in the destination page has been modified from the corresponding block in the source page, utilizing the hardware-based accelerator to pass the original memory address to a controller of the computer, wherein the controller is adapted to perform the read request utilizing the original memory address; and
in response to determination by the hardware-based accelerator that the block is not located in the memory at the original memory address and the copy-on-write status indicates that the block in the destination page has not been modified from the corresponding block in the source page, utilizing the hardware-based accelerator to generate a new memory address and to pass the new memory address to the controller of the computer, wherein the controller is adapted to perform the read request utilizing the new memory address.

2. The method of claim 1 ,
wherein utilizing the hardware-based accelerator to determine whether the block is located in the memory at the original memory address comprises:
identifying the record in the lazy copy tables; and
determining whether the tag of the record matches the tag portion of the page index of the original memory address.

3. The method of claim wherein utilizing the hardware-based accelerator to pass the original memory address to the controller of the computer comprises:
responsive to determining that the tag does not match the tag portion, passing the original memory address to the controller of the computer, wherein the controller is adapted to perform the read request utilizing the original memory address.

4. The method of claim 2 , wherein utilizing the hardware-based accelerator to generate the new memory address and to pass the new memory address to the controller of the computer comprises:
generating the new memory address comprising the new page index, the page offset, and the block offset, wherein the new memory address corresponds to the source page.

5. The method of claim 1 , wherein the level identifier is greater than zero, and wherein recursively evaluating multiple instances of the copy-on-write status based on the level identifier comprises:
(a) determining that a current instance of the copy-on-write status indicates that a current region containing the block in the destination page has been modified from a corresponding current region in the source page, wherein the current region is larger than the block, and wherein the current instance of the copy-on-write status and the current region correspond to a current value of the level identifier;
(b) decrementing the level identifier;
(c) repeating (a) and (b) until either the copy-on-write status indicates that the region in the destination page has not been modified from the corresponding region in the source page, or the level identifier equals zero; and
(d) when the level identifier equals zero, determining that a final instance of the copy-on-write status corresponding to the zero value of the level identifier indicates that the block in the destination page has been modified from the corresponding block in the source page.

6. The method of claim 2 , wherein the block comprises a first block, the page index comprises a first page index, the page offset comprises a first page offset, the block offset comprises a first block offset, the index portion comprises a first index portion, the tag portion comprises a first tag portion, the record comprises a first record, the tag comprises a first tag, the new page index comprises a first new page index, the copy-on-write status comprises a first copy-on-write status, the new memory address comprises a first new memory address, the method further comprising:
intercepting a write request adapted to write to a second block in the memory at a second memory address, wherein the second memory address corresponds to the destination page, wherein the second memory address comprises a second page index, a second page offset, and a second block offset, and wherein the second page index comprises a second index portion and a second tag portion;
in response to intercepting the write request, identifying a second record in the lazy copy table, wherein the second record is indexed in the lazy copy table at the second index portion, and wherein the second record comprises a second tag, a second new page index, and a second copy-on-write status;
generating a second new memory address comprising the second new page index, the second page offset, and the second block offset;
copying the second block from the source page at the second new memory address to the destination page at the second memory address;
setting the second copy-on-write status to indicate that the second block in the destination page has been modified; and
proceeding with the write using the second memory address.

7. The method of claim 2 , wherein the block comprises a first block, the page index

Assignees

• Solihin Yan
• Empire Technology Dev Llc

Inventors

• Solihin Yan

Classifications

• G06F12/10 Primary

  Address translation · CPC title

• G06F11/1446

  Point-in-time backing up or restoration of persistent data · CPC title

• G06F12/0882

  Page mode · CPC title

• G06F9/3881

  Arrangements for communication of instructions and data · CPC title

• G06F12/16 Primary

  Protection against loss of memory contents {(contains no material, see G06F11/00)} · CPC title