Defragmentation of persistent main memory

• US 10,168,911 B1
• Filed: 06/13/2017
• Issued: 01/01/2019
• Est. Priority Date: 06/13/2017
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Oukid, Ismail, Schreter, Ivan, Booss, Daniel
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US15/621,736
• Publication Number:
  US 20180356991A1
• Time in Patent Office: 567 Days
• Field of Search: None
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 2206/1004 Defragmentation
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/064 Management of blocks

Abstract

Disclosed herein are system, method, and computer program product embodiments for defragmentation of persistent main memory (e.g., storage class memory). An embodiment operates by determining that a request to allocate a block of persistent main memory cannot be fulfilled, identifying the largest block of a plurality of free blocks associated with a persistent allocator, and punching a hole at the location of the block within a segment of the persistent main memory. The embodiment further operates by determining that at least one neighboring block of the largest block is also a hole, and coalescing the at least one neighboring block and the largest block.

Claims

1. A computer-implemented method, comprising:

creating initial block information that indicates that an initial block, comprising a largest block of a plurality of free blocks, is a first hole in an original segment of memory;

creating an updated segment based on modifying the original segment to represent that contents of the original segment corresponding to the initial block do not contain any data;

modifying free block information to represent that the initial block is not one of the plurality of free blocks;

determining that an adjacent block adjacent to the initial block is a second hole in the updated segment based on adjacent block information corresponding to the adjacent block;

creating first combination block information based on modifying the initial block information to represent a first combination of the initial block and the adjacent block; and

deleting the adjacent block information corresponding to the adjacent block.

2. The method of claim 1, further comprising:

determining that a size of the first combination of the initial block, the adjacent block is equal to a size of the updated segment;

deleting the first combination block information; and

deleting an association between the updated segment and an allocator identifier.

3. The method of claim 1, further comprising:

determining that the adjacent block is at an end of the updated segment; and

disassociating the initial block from a portion of a virtual address space.

4. The method of claim 1, wherein the adjacent block is a first adjacent block, the adjacent block information is first adjacent block information, and further comprising:

determining that a second adjacent block is a third hole in the updated segment based on second adjacent block information corresponding to the second adjacent block, the second adjacent block adjacent to the initial block;

creating second combination block information based on updating the first combination block information to represent a second combination of the initial block, the first adjacent block, and the second adjacent block; and

deleting the second adjacent block information corresponding to the second adjacent block.

5. The method of claim 1, wherein the initial block and the adjacent block are included in one or more leaves of a b-tree.

6. The method of claim 1, further comprising:

receiving a request to allocate a requested block of a first size;

determining that a second size of the first combination of the initial block and the adjacent block is equal to the first size based on the first combination block information; and

fulfilling the request based at least in part on the first combination of the initial block and the adjacent block.

7. The method of claim 1, wherein the creating an updated segment based on modifying the original segment to represent that contents of the original segment corresponding to the initial block do not contain any data, further comprises calling a system call to punch a hole in the initial block.

8. A non-transitory computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:

creating initial block information that indicates that an initial block, comprising a largest block of a plurality of free blocks, is a first hole in an original segment;

modifying free block information to represent that the initial block is not one of the plurality of free blocks;

creating an updated segment based on modifying the original segment to represent that contents of the original segment corresponding to the initial block do not contain any data;

determining that a left block is a second hole in the updated segment based on left block information corresponding to the left block, the left block adjacent to the initial block;

creating combination block information based on updating the initial block information to represent a combination of the initial block and the left block; and

deleting the left block information corresponding to the left block.

9. The non-transitory computer-readable device of claim 8, wherein the combination block information is a first combination block information, the combination is a first combination, and the operations further comprising:

determining that a right block is a third hole in the updated segment based on right block information corresponding to the right block, the right block adjacent to the initial block;

creating second combination block information based on updating the first combination block information to represent a second combination of the initial block, the left block, and the right block; and

deleting the right block information corresponding to the right block.

10. The non-transitory computer-readable device of claim 9, the operations further comprising:

determining that the right block is at an end of the updated segment; and

disassociating the initial block from a portion of a virtual address space.

11. The non-transitory computer-readable device of claim 9, the operations further comprising:

determining that a size attribute of the second combination of the initial block, the left block, and the right block is equal to a size attribute of the updated segment;

deleting the second combination block information;

deleting an association between the updated segment and an allocator identifier; and

deleting the updated segment from a file system.

12. The non-transitory computer-readable device of claim 9, wherein the creating the combination block information, further comprises:

updating a size attribute of the initial block information to include a size of the initial block and a size of the left block.

13. The non-transitory computer-readable device of claim 8, the operations further comprising:

receiving a request to allocate a requested block of a first size;

determining that a second size of the combination of the initial block and the left block is equal to the first size based on the combination block information; and

fulfilling the request based at least in part on the combination of the initial block and the left block.

14. A system, comprising:

storage class memory including;

an original segment that includes a plurality of blocks;

free block information;

block attribute information for the plurality of blocks, the block attribute information including a hole status of individual blocks of the plurality of blocks;

dynamic random-access memory including;

a persistent allocator that includes a block allocator;

a mapping between the block allocator and the original segment; and

one or more processors, wherein the one or more processors are configured to;

modify the block attribute information to indicate that an initial block is a first hole in the original segment;

modify the free block information to indicate that the initial block of the plurality of blocks is not a free block;

create an updated segment based on modifying the original segment to represent that contents of the original segment corresponding to the initial block do not contain any data;

determine that a neighboring block of the plurality of blocks is a second hole based on the block attribute information, the neighboring block adjacent to the initial block; and

modify the block attribute information to represent a combination of the initial block and the neighboring block.

15. The system of claim 14, wherein the one or more processors are further configured to:

receive, at the persistent allocator, a request to allocate a requested block of a first size;

determine that a second size of the combination of the initial block and the neighboring block is equal to the first size based on the block attribute information; and

fulfill the request based at least in part on the combination of the initial block and the neighboring block.

16. The system of claim 14, wherein the one or more processors are further configured to:

receive, at the persistent allocator, a request to allocate a requested block of a particular size; and

determine that a plurality of allocators are unable to accommodate the request based on the particular size, the plurality of allocators including the block allocator.

17. The system of claim 14, wherein the modify the block attribute information to represent a combination of the initial block and the neighboring block, further comprises:

increasing a size of the initial block in the block attribute information by a size of the neighboring block; and

deleting a portion of the block attribute information pertaining the neighboring block.

18. The system of claim 14, wherein the neighboring block is a first neighboring block, the combination is a first combination, and the one or more processors are further configured to:

determine a second neighboring block is a third hole in the updated segment based on the block attribute information, the neighboring block adjacent to the initial block; and

modify the block attribute information to represent a second combination of the initial block, the first neighboring block, and the second neighboring block.

19. The system of claim 18, wherein the block allocator is a tree-based allocator, and the initial block, the first neighboring block, and the second neighboring block are included in one or more leaves of a tree.

20. The system of claim 19, wherein the tree is a SCM-DRAM b-tree.