Contents
Why Yet Another Dynamic Memory Manager?
Application transparent memory defragmentation
Automatic garbage collector (GC)
Memory allocation is type-safe
No additional libraries required
Why Yet Another Dynamic Memory Manager?
I have designed it as part of my magister thesis to play with memory allocaition techniques. It works, and I think it's good idea to share such code.
Techlonogy implemented in the library is not completely new. Something like this is used in run time environments (virtual machines) of interpreted languages like Java, Python or Perl. In particular it can be appropriate choise in following cases
- For building an implementation of a language similary to those mentioned above. You have option not to start once again writing everything from scratch.
- In implementation of software for portable device where efficient memory utilization is important and many applications are written from scratch.
Pointer abstraction implemented in Flood allow to effectively manage memory allocations. And it is stand-alone library which allows you not to duplicate pool management code again and again.
More about features
Application transparent memory defragmentation
Flood can reorganize blocks in memory in order to merge all free snippets into large free blocks available for allocation. Affected pointers are updated by Flood when particular object moves. It implies that application can even do not mention these changes. Nonetheelse such application should obey some restrictions (see below for more details).
Automatic garbage collector (GC)
In simple cases for GC is used simple reference counting algorithm. In a nutshell, each block holds number of existing references to himself. If number of existing references goes down to 0, then desrtuctor for that block is executed. This approach is very efficient and easy to implement but can not correctly handle all cases. When there is a cycle of pointers this algorithm can not help. For latter case in Flood's GC is implemented a pointer tracing (mark&sweep or root tracing) algorithm. This algorithm belongs to class of non conservative garbage collectors.
I hope that combination of these two approaches has little overhead for memory maintenace during most time and provides ability to handle complicated cases when it is necessary.
Implemented in C++
I hope that this choise is not significantly hits Flood's performance. At the same time it allow easily implement features like following.
Memory allocation is type-safe
Each block allocated by Flood is typed. That is if you allocate an array of type A, you will not able to assign pointer to it to pointer to different type B without type cast.
"Smart pointer" used in Flood is declared as template class
template <class T>
class dynamic
{ ... }
Allocation blocks are implemented as class instances. It is possible to derive new classes which can extend memory management functionality at relatively low level.
Each allocated can be interpreted as an array. If only one object of given type is required then array length should be set to 1.
No additional libraries required
This statement is not completely true: Flood uses STL (console I/O for testing facility and <algorithm> header in core implementation), and glib (thru GCC) for initialization process (malloc is used once). Despite this initialization process can be easily modified to use Unix brk() call only.
Thanks to this property porting of Flood should be extremely straitforward.
Flood is not thread safe
There is a number of critical sections which need to be protected if the code is used in multi-threaded environment. Garbage collection algorithm is rather fast but consist of big critical sections. Thus it need to be modified in order to obtain good responrse time from system as whole. But note that GC algorithm is invoked only in extreme cases when there is not enough memory and exist orphaned pointer cycles, or explicitly by user. In most cases reference counting works well.
Fixed pool size
Current implementation allows only fixed-size pools. Pool size is determined at Flood's initialization. This limitation is planned to be taken away (see also TODO file in sources).
Memory defragmentation
Memory fragmentation is a situation when total amount of not allocated memory is enough to continue work, but there is no appropriate continuous free memory range. There are different approaches to handle it. These include
- Just use memory layering (swap space) thus extending accessible address range. If there not enough memory, rarely used fragments of it are swapped out into external big capacity and slow device. In portable devices and diskless systems this is inappropriate choice.
- Approach similary to previous one: use big cache and store inactive fragments in complessed state in RAM as well as active fragments. It is desirable to perform compression - decompression using special hardware.
- Pre - fragment data structures. E.g. instead of allocating big continuous array allocate it as a set of little fragments, and access them using binary tree, for instance. This approach leads to additional overhead in memory and CPU usage.
- Reorder memory blocks and merge free ones into large free fragments. This procedure in most cases is very fast and in fact has complexity somwhere equivalent to copying blocks to their new places. Efficiency of this method depends on frequency of defragmentations. The approach is implemented in Flood.
At first sight latter approach is very attractive. So what's the catch? The point is nessecity to update all pointers affected by object relocations. It contradicts with usual pointer handling. Conventional agreement is to suppose that once object is allocated it can not change it's location. This we can safely obtain pointer to address inside object body, can use pointer arithmetic and can freely assign pointers each to other. If by contrary object is free to move run time environment should watch for all pointers. But it is possible not in all cases. Thus in order to implement automatic defragmentation we need to restrict pointer semantic. Concluding all this, automatic pointer update makes Flood incompatible with most existing code because much of code assumes that location of object is constant and uses this assumption. Thus Flood is primarily useful in areas highlighted above.
Possible workarounds for aquiring comatibility are
- Disable defragmentation. Int this case Flood statys useful as GC-enabled memory manager altough not so effectife.
- Mark particular blocks (variables) as fixed and not relocatable.
Difficulties in using the library arise from the fact that automatic pointer update requires registration of all application's pointers which are located in or point to heap. The better way to do it is to have hardware and compiler support (tagged memory and modified pointer semantics). Unfortunately we do not have it in conventional computer systems and Flood emulates this functionality using bitmask registry. Automatic update makes these pointers incompatible with those used in conventional libraries. And if Flood is sole dynamic memory manager in the system it is a problem.
Notwithstanding that many compatibility issues can be solved, I think that primary application area of Flood is built-in systems and portable devices. (Such applications often written from scratch and require effecient memory allocation procedures).
How it works
User application uses typed smart pointers which interact with memory pool to perform necessary memory allocation opearions.
Memory pool implementation consists of two core classes
- DynamicMemoryPool - holds information about pool as whole (pool size, it's position, block chain entries, location of auxiliary structures etc.). DynamicMemoryPool is in fact singleton i.e. there is only one instance object of this class.
- Block - basic allocation unit, it is parent of more specialized blocks. Class block has reference to the instance of DynamicMemoryPool in order to invoke callback functions. Perhaps it is not an elegant solution because it limits Flood to have only one memory pool.
Blocks are in two-way linked list.
Memory pool is divided into three parts
- Block allocation area (blocks chain is situated here).
- Reserved area. This area is reserved for defragmentation and GC algorithms. These require some area to keep auxiliray structures and reservation helps to simplify and speedup them. Size of this part changes depenging on currently allocated data.
- Pointer bitmask. This bitmask allows to determine whether particular word in pool is a pointer or not. Other containers for this purpose can be used but bitmask has several advantages: it has already known fixed size (about 3% of whole pool size for 32bit platforms), constant (and little) time for addition/deletion.
Restrictions on pointer values are as follows. These restrictions are automatically maintained by smart pointers.
- Pointer should refer to the beginning address of allocated unit. This restriction is required by necessity to reverse pointer graph (to find all pointers refferring to a particular block). This restriction makes this operation very fast.
- Pointer should be registered within memory manager and application should not make anyassumptions about it's value because it may be changed within defragmentation. This restriction implies that pointer arithmetic can not be used, and only allowing comparison between pointers is "==" or "!=". Despite this arithmetic can be emulated using special pointer class which uses pointer[offset] access method. (Comapre it to Java, where you can use arrays for this purpose).
Parts of Flood source may look tricky, but most of them are solving particular problems perhaps not in the best way :)
How to use
This library was born as a part of research work, and thus it may leak of some practically required functions. But it is not a big problem - it's open sourced :) If you have problems with flood you can ask author (see home page).
For soure code example you may look at flood-src-root/debug/dm_test.cc file.