Garbage Collection Technique for Non-volatile Memory by Using Tree Data Structure

Dokeun Lee, Youjip Won

http://doi.org/

Most traditional garbage collectors commonly use the language level metadata, which is designed for pointer type searching. However, because it is difficult to use this metadata in non-volatile memory allocation platforms, a new garbage collection technique is essential for nonvolatile memory utilization. In this paper, we design new metadata for managing information regarding non-volatile memory allocation called "Allocation Tree". This metadata is comprised of tree data structure for fast information lookup and a node that holds an allocation address and an object ID pair in key-value form. The Garbage Collector starts collecting when there are insufficient non-volatile memory spaces, and it compares user data and the allocation tree for garbage detection. We develop this algorithm in a persistent heap based non-volatile memory allocation platform called "HEAPO" for demonstration.