Scalable page migration after memory de-duplication

A system for memory de-duplication, the system comprising:

• a memory;
• one or more processors, in communication with the memory;
• a first data structure, in communication with the one or more processors;
• a second data structure, in communication with the one or more processors;
• and
• a third data structure, in communication with the one or more processors;
• wherein the one or more processors are configured to:
• receive a first single memory page;
• scan a plurality of candidate memory pages of the first data structure, wherein the first data structure includes a plurality of nodes including at least a first node and a second node, wherein each of the first node and the second node point to a first candidate memory page and a second candidate memory page respectively;
• identify a first matched memory page as a match to the first single memory page, wherein the first matched memory page is one of the plurality of candidate memory pages that matches the first single memory page;
• determine that a quantity of memory page mappings to the first matched memory page is less than a threshold;
• responsive to determining that the quantity of memory page mappings to the first matched memory page is less than the threshold, add a first mapping to the first matched memory page, the first mapping identifying the first single memory page;
• receive a second single memory page;
• scan the plurality of candidate memory pages of the first data structure;
• identify the first matched memory page as a match to the second single memory page;
• determine that the quantity of memory page mappings to the first matched memory page meets the threshold;
• and
• responsive to determining that the quantity of memory page mappings to the first matched memory page meets the threshold:
• scan the second data structure for the match to the second single memory page;
• determine that the second data structure lacks the match to the second single memory page;
• and
• responsive to determining that the second data structure lacks the match to the second single memory page, store the second single memory page in the second data structure.

A computer readable non-transitory storage medium comprising executable instructions that, when executed, are configured to cause the a processor to:

• receive a first single memory page;
• scan a plurality of candidate memory pages of the first data structure, wherein the first data structure includes a plurality of nodes including at least a first node and a second node, wherein each of the first node and the second node point to a first candidate memory page and a second candidate memory page respectively;
• identify a first matched memory page as a match to the first single memory page, wherein the first matched memory page is one of the plurality of candidate memory pages that matches the first single memory page;
• determine that a quantity of memory page mappings to the first matched memory page is less than a threshold;
• responsive to determining that the quantity of memory page mappings to the first matched memory page is less than the threshold, add a first mapping to the first matched memory page, the first mapping identifying the first single memory page;
• receive a second single memory page;
• scan the plurality of candidate memory pages of the first data structure;
• identify the first matched memory page as a match to the second single memory page;
• determine that the quantity of memory page mappings to the first matched memory page meets the threshold;
• and
• responsive to determining that the quantity of memory page mappings to the first matched memory page meets the threshold:
• scan the second data structure for the match to the second single memory page;
• determine that the second data structure lacks the match to the second single memory page;
• responsive to determining that the second data structure lacks the match to the second single memory page, store the second single memory page in the second data structure;
• receive a third single memory page;
• scan the plurality of candidate memory pages of the first data structure;
• identify the first matched memory page as a match to the third single memory page;
• determine that the quantity of memory page mappings to the first matched memory page meets the threshold;
• and
• responsive to determining that the quantity of memory page mappings to the first matched memory page meets the threshold:
• scan the second data structure for the match to the third single memory page;
• identify the second single memory page as the match to the third single memory page;
• and
• responsive to identifying the second single memory page as the match to the third single memory page, create the third data structure, wherein the third data structure replaces the first matched memory page, and wherein creating the third data structure includes:
• creating an identifier node in the first data structure, the identifier node identifying content of each matched memory page in the third data structure;
• attaching the first matched memory page to the identifier node;
• and
• attaching a second matched memory page to the first matched memory page, including:
• adding a second mapping to the second matched memory page, the second mapping identifying the second single memory page, and
• adding a third mapping to the second matched memory page, the third mapping identifying the third single memory page.