Memory Garbage Collection without Remapping Virtual Addresses
Original Publication Date: 2009-Oct-08
Included in the Prior Art Database: 2009-Oct-08
AbstractDisclosed is a method for consolidating data from multiple physical pages while leaving the virtual addressing of the data the same.
Ȉˇˇ ˄˄ ˄
Ȉˇˇ ˄˄ ˄ Ȉˇˇ ˄˄ ˄
In an embedded environment without a large backing store, efficient use of physical memory is always a concern. Mapping virtual pages on top of physical pages is one way of increasing efficiency as it allows larger virtual contiguous address spaces to be created from smaller fragmented physical address spaces. Mapping virtual pages on top of physical pages does not solve the entire problem though. Small allocations/de-allocations, those less than a page, can cause fragmentation or inefficient use of physical memory. If one allocation still exists within a physical page, then that physical page can not be freed to be used for other page sized allocations. This can greatly reduce the usage efficiency of the physical memory.
There are four components to the described process of consolidating physical pages: when consolidation should be attempted, how to manage the consolidation between pages, data movement to the consolidated pages, and reservation in virtual pages which have been consolidated. Determining when consolidation should be attempted can occur on a periodic basis, or aging of the allocations; i.e., only consolidate after an allocation has persisted for some period of time.
To manage the consolidations between pages, it must be determined which areas within a page are allocated. A simple way to keep track of this is to use a bit mask for fixed size regions of a page. The fixed size region may represent the smallest possible allocation, or something larger, but must be less than or equal to half the size of a page. If there is one or more allocation within that region, then the bit is set. When all the allocations for a region have been de-allocated, then the bit is cleared. Several pages can be easily compared to determine if they can be consolidated by a logical ANDing of the bit masks for those pages. If the result is non-zero, the pages can not be consolidated together. In addition, a reference count of how many virtual pages are mapped to a physical page must be managed. When all allocations in a virtual page are freed and no longer reference the physical page, then decrement the reference count. Once the reference count goes to zero, the physical page can be freed.
Once it is determined which pages can be consolidated together, all data must be moved to one physical page and the mapping for all affected virtual pages updated. This is accomplished by copying the data to the exact same offset within the physical page targeted for consolidation. The page table is then updated to map each of the affected virtual pages to the targeted physical page.
When virtual pages share a consolidated physical page, there needs to be an awareness of the allocations within the other virtual pages. Meaning two virtual pages may not...