2....a)Hardware:①Basic
Memory Information Maintenance Based on Buddy Tree:
Proposed by Chang et al.[1] and adopted by Xue et al.[2], OR-gate bit-vectors (BVs) and AND-gate BVs are used to maintain the memory usage of the heap and one BV accounts for the information of a particular depth of the buddy tree. Supposed that the allocator is designed to manage MAUs. Accordingly, the buddy tree will have a depth of
, as the tree shown in the figure above, which has a depth
of 3 and can manage 8 MAUs, each of which is a 1kb block node. Each node located in the layer at the depth of
represents a memory block with size of
MAUs and a
-bit vector
of the layer can be used to record the status of these nodes, in which the
-th node is mapped to the bit
. A bit in the OR-gate BV of the layer,
, indicates the
-th memory block in this layer is empty when it is 0, otherwise, the value of the bit will be 1. As for a bit in the AND-gate BV of the layer,
, it will be 1 only if the corresponding memory block is full. Based on this, the allocator will handle the (de-)allocation requests via two stages, (de-)allocation stage and maintenance stage.
In the following content, we will illustrate how buddy tree works through a series of operations based on it.
OR-gate bit-vectors (BVs)
For conventional buddy tree, each layer will be first described with a bit-vector, based on OR-gate from leaves to root. The leaves of buddy tree represent the availability of MAUs and an entire OR-gate tree can be built from the leaves to the root according to follow equation:
For example shown below, after a 1kb block node is allocated, the node 7 in the figure below is marked with a value of 0 because both its son have the value of 0, while node 4 is marked as 1 due to an unavailable son.
The OR-gate tree can indicate the availability of memory blocks in the -th layer with
, where the first zero bit represents an available block for the request with size ranging from
to
.
AND-gate bit-vectors (BVs)
In order to find the first zero bit, the specified OR-gate BV will be fed into an AND-gate tree as leaves. For example, in order to locate an 2kb block node, the second layer of OR-gate tree will be the input of AND-gate tree, when searching a 2-MAUs block for allocation. Only when both children nodes are allocated, the node can be marked as full. Therefore, AND-gate buddy tree can be constructed according to following equation:
For example shown in the figure below, after one more 4kb block node is allocated, the node 2 is marked with a value of 0 because one of its son is still available, while node 3 is marked as 1 due to no allocable son.
The AND-gate tree can propagate availability information upward toward the root in such a way that the location of the first zero in can be found by a non-backtracking search from the root to the target leaf by tracking the child node with a value of 0, with a time complexity of
.
Allocation Stage:
Suppose the size of the incoming request ranges from to
. The allocation stage begins with the search based on AND-gate tree. Then, if the first zero bit is found at the
-th lowest position of the bit-vector
, the resultant memory address will be
.
For example, if searching for a 2-MAUs block in the figure above, the allocator will go through nodes 1, 2 and 5 of AND-gate tree. Then, because node 5 is the 2-th node at the depth of 2, the allocated address should be 2. After allocation, the allocated bits in the corresponding BVs will be flipped. This procedure is presented in the figure below.
Deallocation Stage:
Since the information of previous allocation has already been recorded during allocation stage, the action of freeing a memory block flips the corresponding bit in the OR-gate BV and takes much less time than allocating one.
Maintenance Stage:
Marking downwards and marking upwards in this stage maintain the allocation information for latter requests. The procedure of marking downwards starts from the layer of OR-gate buddy tree, which is located in allocation stage according to the request size, to the bottom layer. During marking downward after allocation, for each layer, the bits covered by the allocated block will be set to 1. In contrast, those bits will be set to be 0 after freeing.
For instance, in the example of allocation, if the node 5 of OR-gate tree in the figure is allocated, nodes 10 and 11, will be marked with 1. Similarly, in the example below, if node 3 is freed, nodes 6, 7, 12, 13, 14 and 15, will be marked with 0.
To mark upwards, all the upper layers need to be updated, by setting their BVs according to the definition of OR-gate tree and AND-gate tree. In the example of allocation, if the node 5 of OR-gate tree in the figure is allocated, nodes 2 and 1, will be marked with 1, though they have been marked.
[1] Chang, J. Morris, and Edward F. Gehringer. "A high-performance memory allocator for object-oriented systems." IEEE Transactions on Computers 3 (1996): 357-366.
[2] Xue, Zeping, and David B. Thomas. "SysAlloc: A hardware manager for dynamic memory allocation in heterogeneous systems." Field Programmable Logic and Applications (FPL), 2015 25th International Conference on. IEEE, 2015.