Memory Management in HDF5

Is a Memory Manager Necessary?

Some form of memory management may be necessary in HDF5 when the various deletion operators are implemented so that the file memory is not permanently orphaned. However, since an HDF5 file was designed with persistent data in mind, the importance of a memory manager is questionable.

On the other hand, when certain meta data containers (file glue) grow, they may need to be relocated in order to keep the container contiguous.

Example: An object header consists of up to two chunks of contiguous memory. The first chunk is a fixed size at a fixed location when the header link count is greater than one. Thus, inserting additional items into an object header may require the second chunk to expand. When this occurs, the second chunk may need to move to another location in the file, freeing the file memory which that chunk originally occupied.

The relocation of meta data containers could potentially orphan a significant amount of file memory if the application has made poor estimates for preallocation sizes.

Levels of Memory Management

Memory management by the library can be independent of memory management support by the file format. The file format can support no memory management, some memory management, or full memory management. Similarly with the library.

Support in the Library

No Support: I

When memory is deallocated it simply becomes unreferenced (orphaned) in the file. Memory allocation requests are satisfied by extending the file.

A separate off-line utility can be used to detect the unreferenced bytes of a file and "bubble" them up to the end of the file and then truncate the file.

Some Support: II

The library could support partial memory management all the time, or full memory management some of the time. Orphaning free blocks instead of adding them to a free list should not affect the file integrity, nor should fulfilling new requests by extending the file instead of using the free list.

Full Support: III

The library supports space-efficient memory management by always fulfilling allocation requests from the free list when possible, and by coalescing adjacent free blocks into a single larger free block.

Support in the File Format

No Support: A

The file format does not support memory management; any unreferenced block in the file is assumed to be free. If the library supports full memory management then it will have to traverse the entire file to determine which blocks are unreferenced.

Some Support: B

Assuming that unreferenced blocks are free can be dangerous in a situation where the file is not consistent. For instance, if a directory tree becomes detached from the main directory hierarchy, then the detached directory and everything that is referenced only through the detached directory become unreferenced. File repair utilities will be unable to determine which unreferenced blocks need to be linked back into the file hierarchy.

Therefore, it might be useful to keep an unsorted, doubly-linked list of free blocks in the file. The library can add and remove blocks from the list in constant time, and can generate its own internal free-block data structure in time proportional to the number of free blocks instead of the size of the file. Additionally, a library can use a subset of the free blocks, an alternative which is not feasible if the file format doesn't support any form of memory management.

Full Support: C

The file format can mirror library data structures for space-efficient memory management. The free blocks are linked in unsorted, doubly-linked lists with one list per free block size. The heads of the lists are pointed to by a B-tree whose nodes are sorted by free block size. At the same time, all free blocks are the leaf nodes of another B-tree sorted by starting and ending address. When the trees are used in combination we can deallocate and allocate memory in O(log N) time where N is the number of free blocks.

Combinations of Library and File Format Support

We now evaluate each combination of library support with file support:

I-A

If neither the library nor the file support memory management, then each allocation request will come from the end of the file and each deallocation request is a no-op that simply leaves the free block unreferenced.

• Advantages
  • No file overhead for allocation or deallocation.
  • No library overhead for allocation or deallocation.
  • No file traversal required at time of open.
  • No data needs to be written back to the file when it's closed.
  • Trivial to implement (already implemented).
• Disadvantages
  • Inefficient use of file space.
  • A file repair utility must reclaim lost file space.
  • Difficulties for file repair utilities. (Is an unreferenced block a free block or orphaned data?)

II-A

In order for the library to support memory management, it will be required to build the internal free block representation by traversing the entire file looking for unreferenced blocks.

• Advantages
  • No file overhead for allocation or deallocation.
  • Variable amount of library overhead for allocation and deallocation depending on how much work the library wants to do.
  • No data needs to be written back to the file when it's closed.
  • Might use file space efficiently.
• Disadvantages
  • Might use file space inefficiently.
  • File traversal required at time of open.
  • A file repair utility must reclaim lost file space.
  • Difficulties for file repair utilities.
  • Sharing of the free list between processes falls outside the HDF5 file format documentation.

III-A

In order for the library to support full memory management, it will be required to build the internal free block representation by traversing the entire file looking for unreferenced blocks.

• Advantages
  • No file overhead for allocation or deallocation.
  • Efficient use of file space.
  • No data needs to be written back to the file when it's closed.
• Disadvantages
  • Moderate amount of library overhead for allocation and deallocation.
  • File traversal required at time of open.
  • A file repair utility must reclaim lost file space.
  • Difficulties for file repair utilities.
  • Sharing of the free list between processes falls outside the HDF5 file format documentation.

I-B

If the library doesn't support memory management but the file format supports some level of management, then a file repair utility will have to be run occasionally to reclaim unreferenced blocks.

• Advantages
  • No file overhead for allocation or deallocation.
  • No library overhead for allocation or deallocation.
  • No file traversal required at time of open.
  • No data needs to be written back to the file when it's closed.
• Disadvantages
  • A file repair utility must reclaim lost file space.
  • Difficulties for file repair utilities.

II-B

Both the library and the file format support some level of memory management.

• Advantages
  • Constant file overhead per allocation or deallocation.
  • Variable library overhead per allocation or deallocation depending on how much work the library wants to do.
  • Traversal at file open time is on the order of the free list size instead of the file size.
  • The library has the option of reading only part of the free list.
  • No data needs to be written at file close time if it has been amortized into the cost of allocation and deallocation.
  • File repair utilties don't have to be run to reclaim memory.
  • File repair utilities can detect whether an unreferenced block is a free block or orphaned data.
  • Sharing of the free list between processes might be easier.
  • Possible efficient use of file space.
• Disadvantages
  • Possible inefficient use of file space.

III-B

The library provides space-efficient memory management but the file format only supports an unsorted list of free blocks.

• Advantages
  • Constant time file overhead per allocation or deallocation.
  • No data needs to be written at file close time if it has been amortized into the cost of allocation and deallocation.
  • File repair utilities don't have to be run to reclaim memory.
  • File repair utilities can detect whether an unreferenced block is a free block or orphaned data.
  • Sharing of the free list between processes might be easier.
  • Efficient use of file space.
• Disadvantages
  • O(log N) library overhead per allocation or deallocation where N is the total number of free blocks.
  • O(N) time to open a file since the entire free list must be read to construct the in-core trees used by the library.
  • Library is more complicated.

I-C

This has the same advantages and disadvantages as I-C with the added disadvantage that the file format is much more complicated.

II-C

If the library only provides partial memory management but the file requires full memory management, then this method degenerates to the same as II-A with the added disadvantage that the file format is much more complicated.

III-C

The library and file format both provide complete data structures for space-efficient memory management.

• Advantages
  • Files can be opened in constant time since the free list is read on demand and amortised into the allocation and deallocation requests.
  • No data needs to be written back to the file when it's closed.
  • File repair utilities don't have to be run to reclaim memory.
  • File repair utilities can detect whether an unreferenced block is a free block or orphaned data.
  • Sharing the free list between processes is easy.
  • Efficient use of file space.
• Disadvantages
  • O(log N) file allocation and deallocation cost where N is the total number of free blocks.
  • O(log N) library allocation and deallocation cost.
  • Much more complicated file format.
  • More complicated library.

The Algorithm for II-B

The file contains an unsorted, doubly-linked list of free blocks. The address of the head of the list appears in the boot block. Each free block contains the following fields:

The library reads as much of the free list as convenient when convenient and pushes those entries onto stacks. This can occur when a file is opened or any time during the life of the file. There is one stack for each free block size and the stacks are sorted by size in a balanced tree in memory.

Deallocation involves finding the correct stack or creating a new one (an O(log K) operation where K is the number of stacks), pushing the free block info onto the stack (a constant-time operation), and inserting the free block into the file free block list (a constant-time operation which doesn't necessarily involve any I/O since the free blocks can be cached like other objects). No attempt is made to coalesce adjacent free blocks into larger blocks.

Allocation involves finding the correct stack (an O(log K) operation), removing the top item from the stack (a constant-time operation), and removing the block from the file free block list (a constant-time operation). If there is no free block of the requested size or larger, then the file is extended.

To provide sharability of the free list between processes, the last step of an allocation will check for the free block signature and if it doesn't find one will repeat the process. Alternatively, a process can temporarily remove free blocks from the file and hold them in it's own private pool.

To summarize...

File opening

O(N) amortized over the time the file is open, where N is the number of free blocks. The library can still function without reading any of the file free block list.

Deallocation

O(log K) where K is the number of unique sizes of free blocks. File access is constant.

Allocation

O(log K). File access is constant.

File closing

O(1) even if the library temporarily removes free blocks from the file to hold them in a private pool since the pool can still be a linked list on disk.

The Algorithm for III-C

The HDF5 file format supports a general B-tree mechanism for storing data with keys. If we use a B-tree to represent all parts of the file that are free and the B-tree is indexed so that a free file chunk can be found if we know the starting or ending address, then we can efficiently determine whether a free chunk begins or ends at the specified address. Call this the Address B-Tree.

If a second B-tree points to a set of stacks where the members of a particular stack are all free chunks of the same size, and the tree is indexed by chunk size, then we can efficiently find the best-fit chunk size for a memory request. Call this the Size B-Tree.

All free blocks of a particular size can be linked together with an unsorted, doubly-linked, circular list and the left and right sibling addresses can be stored within the free chunk, allowing us to remove or insert items from the list in constant time.

Deallocation of a block fo file memory consists of:

1. Add the new free block whose address is ADDR to the address B-tree.
   1. If the address B-tree contains an entry for a free block that ends at ADDR-1 then remove that block from the B-tree and from the linked list (if the block was the first on the list then the size B-tree must be updated). Adjust the size and address of the block being freed to include the block just removed from the free list. The time required to search for and possibly remove the left block is O(log N) where N is the number of free blocks.
   2. If the address B-tree contains an entry for the free block that begins at ADDR+LENGTH then remove that block from the B-tree and from the linked list (if the block was the first on the list then the size B-tree must be updated). Adjust the size of the block being freed to include the block just removed from the free list. The time required to search for and possibly remove the right block is O(log N).
   3. Add the new (adjusted) block to the address B-tree. The time for this operation is O(log N).
2. Add the new block to the size B-tree and linked list.
   1. If the size B-tree has an entry for this particular size, then add the chunk to the tail of the list. This is an O(log K) operation where K is the number of unique free block sizes.
   2. Otherwise make a new entry in the B-tree for chunks of this size. This is also O(log K).

Allocation is similar to deallocation.

To summarize...

File opening

O(1)

Deallocation

O(log N) where N is the total number of free blocks. File access time is O(log N).

Allocation

O(log N). File access time is O(log N).

File closing

O(1).