You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 121 lines 8.8 KiB Raw Permalink Normal View History

 TeXified paper 1 year ago​​​​​​​​​Added appropriate fonts for C names 1 year ago​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​TeXified paper 1 year ago​​​​Added appropriate fonts for C names 1 year ago​​​​​​​​​​​​​​​​​​​​​TeXified paper 1 year ago​​Added appropriate fonts for C names 1 year ago​​​​​​​​​​Added a conclusion to the paper 1 year agoTeXified paper 1 year ago​​​​​​​​​​​​​​​​​​​Added a conclusion to the paper 1 year ago​TeXified paper 1 year ago \documentclass{article} \begin{document}\title{A Memory Allocator}\author{Cameron Weinfurt, Thomas Johnson} \maketitle \section{Introduction} When implementing the functionality of abstract data structures, it becomes necessary to have an arraywhose size is not known at compile time. This is problematic in languages like C and C++ where thesize of an array must be known when compiling in order to calculate how bih the stack frame must be.The solution is to forgo having the array existing on the stack and not even dedicate space at compiletime for the array. Instead, the array is created during runtime once the size of the array can bedetermined. This is known as dynamic memory allocation. A special region in a process's memory isdedicated for these kinds of allocations, called the heap, while a memory allocator keeps track ofthis space's usage. How the allocator handles memory that is no longer in use and situations in whicha region must be resized depends on how it is implemented. In addition, the memory allocator has tobalance how much memory that it uses for record keeping while also minimizing the amount of CPU cyclesrequired to manage the memory region it has been given. In ANSI C, the standard library provides a memory allocator for general purpose use in programs.Dynamic memory allocation is performed through the {\tt malloc()} library call in which the callerpasses the desired size of the allocation and it returns a pointer to the allocated memory region. Itmust be noted that malloc does not initalize the returned memory region with any value, so the callermust initalize the array itself. However, the standard library also provides the {\tt calloc()}library call in which the allocated memory is initalized with zero in every byte. Resizing of anallocation is performed using the {\tt realloc()} and {\tt reallocarray()} library calls, which willeither grow the allocation in place or move the allocation to a space in which the new size can fit.The program must signify to the allocator that an memory region is to be marked free through the {\tt free()} libary call. Should it fail to notify the allocator that an allocation is no longer in use before all of its references go out of scope, it will become impossible to access the underlying data or use the space it took up; amemory leak. Other languages' standard libraries can provide memory allocators or additional data structures fordynamic allocation using other techniques. Rather returning a pointer as a reference to theallocation, languages like C++ and Rust provide smart references that determines when the underlyingmemory allocation can be freed by detecting when all of its references have gone out of scope. Runtimelanguages like those running on the Java Virtual Machine or Microsoft's Common Language Interface alsoprovide smart pointers, but wait to free the unused memory regions until a scheduled batch processoccurs known as a garbage collection. Higher order languages like Python and Lua completely abstractaway that dynamic allocation is occuring by only allowing abstract data structures to be created bythe programmer, allowing for their implementation to handle the underlying allocations neededtransparently. In practice, abstract data structures do not allocate in the same way. It is possible to categorizethem into two groups based on how they allocate. For data structures like vectors and smart strings, asingle allocation is made at its creation and then resized as data is either added or removed. This isthe first group. The second group consists of data structures like linked lists and trees, where manyallocations and frees are requested, but each allocation is fixed in size. Rather than handlingdynamic allocation request using one method, abstract data structures could instead give hints to theallocator as to what kind of allocations it should be making. Such an allocator could then beconstructed to take advantage of these hints and optimize accordingly. This is what this paper aims todemonstrate. \section{Implementation} \subsection{The Tree Allocator} Internally, the allocator is made of two self-balancing binary search trees in which one keeps recordsof free space available to the allocator while the other keeps records of allocated memory. Both treesare sorted using the size of their respective regions, though they can be search based on location inmemory as well. Each node can be one of three types depending on their purpose. The type is used todetermine which struct to represent the node with; the similar footprint permitting pointerpolymorphism. A red-black tree was chosen to perform the self-balancing due to the minimal cost ofadding a color field to each node. To perform an allocation, the allocator first searches for within the free space tree for a memoryblock of suitable size. If it cannot find one, it requests the operating system for additional memoryto mapped into the process before pushing the new space onto the tree and searching again. Once a noderepresenting a memory region of sufficent size is found, it is removed from the free-space tree. Theunderlying space is then split to fit the new allocation and leave the excess space unallocated. Theallocated space as a new node is pushed onto the allocations tree while the excess space also in newnodes are pushed back ono the free-space tree. In particular, the allocator attempts to place the newallocation in the center of the free space in order to minimize the chances of resizing causing amove. Deallocations are handled in a similar manner. When an address is requested to be freed, theallocator searches for the corresponding node in the allocations tree. This node is then popped offthe allocations tree and pushed onto the free-space tree. In addition, if it is found that this nodeis surrounded by unallocated memory after being pushed onto the free-space tree, it will merge thenodes together. This keeps fragmentation at a minimum and speeds up subsequent allocations anddeallocation. \subsection{The Watermark Allocator} On its own, the watermark allocator present many problems that make is unfeasible to use as anallocator. This model of allocator is simply a stack that cannot have elements popped off of it whilealso holding a reference counter. The obvious problem with this is that frees ultimately are leaksunder a watermark allocator. Unrestricted, a watermark allocator will eventually run out of memoryeven though free space may exist behind its stack pointer. This simplistic model does not come withoutits benefits; however, being that an allocation requires very little overhead and metadata to handle.The solution that was derived to take advantage of this property was to use the tree allocator tomanage a series of finite sized watermark allocators. The implementation does not create an instanceof a watermark allocator until a request for a fixed sized allocation is made. It is limited to aspace of 4096 bytes, enforcing that the allocator be used for small, fixed size allocations. Largerallocations will either fail or be allocated using the tree allocator instead. Should an allocator runout of space, a new one is created and the allocation is performed on that new allocator. In addition, it is stored as a node within the tree allocator, meaning the last reference to the memory region will be the global allocator itself, which will free the space through the tree allocator automatically when the reference count on the space goes to zero. \section{Results} % TODO: Add figures the LaTeX way To evaluate the effectiveness of the allocator, glibc's malloc was used as a benchmark. Tree alloc vs. Watermark alloc vs. Glibc Malloc with repeated allocs of size 20: Tree alloc vs. Glibc Malloc with repeated allocs of size 8000: %## Tree alloc vs. Watermark alloc vs Glibc Malloc with repeated frees of size 20: %## Tree alloc vs. Glibc Malloc with repeated frees of size 8000: %## Tree alloc vs. Glibc Realloc with repeatedly resizing allocations. A set of 3 allocations were made of size 20. They were doubled in size repeatedly in sequence of their allocation. \section{Conclusion} Due to time constraints, we were unable to finalize the allocator as a whole. The tree allocator is in a mostly working state, but appears to behave different depending on build parameters and which tools the test environment is run under. In most cases, the allocator will leak due to bugs in the red-black tree implementation. The watermark allocator, being dependent on the tree allocator, was not tested even though an implementation was written. The choice to use a red-black tree may have been suboptimal. Even though it is a self-balancing binary search tree that gives logarithmic time search, insert and deletion, other types of self-balancing trees could have been used. A B-tree may have been the more appropriate \end{document}