Compact-Fit http://tiptoe.cs.uni-salzburg.at/compact-fit
by Hannes Payer hpayer@cs.uni-salzburg.at
27 August 2007 

 University Salzburg, www.uni-salzburg.at
 Department of Computer Science, cs.uni-salzburg.at

 This project is funded by the Austrian Science Fund 
 project number P18913

 This program is free software; you can redistribute 
 it and/or modify it under the terms of the GNU General 
 Public License as published by the Free Software 
 Foundation; either version 2 of the License, or (at 
 your option) any later version.

 This program is distributed in the hope that it 
 will be useful, but WITHOUT ANY WARRANTY; without 
 even the implied warranty of MERCHANTABILITY or 
 FITNESS FOR A PARTICULAR PURPOSE.  

 See the GNU General Public License for more details.


Compact-Fit
~~~~~~~~~~~~~~~~
Compact-Fit (CF) is a compacting real-time memory management 
system for allocating, deallocating and accessing memory objects. 
The system keeps the memory always compact and provides constant 
response times for allocation and access, and linear response time 
(in the size of the object) for deallocation when compaction 
occurs. Moreover, the system provides fully predictable memory, in 
the sense of fragmentation. In short, it is a real real-time memory 
management system. We present two implementations of the 
Compact-fit system and compare them to the established memory 
management systems, which all fail to satisfy the memory 
predictability requirement. The experiments confirm our theoretical 
complexity bounds and demonstrate competitive performance. In 
addition, we can control the performance vs. fragmentation trade-off, 
via our concept of partial compaction. The system can be 
parameterized with the needed level of compaction, leading to 
constant response times for deallocation as well, while keeping 
memory fragmentation bounded and fully predictable.

Files included:
	* cf.h - CF header file
	* cf.c - CF implementation
	* arch_dep.h - cpu bitmap instructions
	* main.c - mutator example
	* Makefile 

Usage : ./cf-test (Just execute the mutator)

Compilation instructions
~~~~~~~~~~~~~~~~~~~~~~~~

1. Get a working compiler
An actual version of GCC is the compiler of your choice.

2. Conditional compilation
Set the NONMOVING define directive to 1 if you want to use the nonmoving version
of CF, otherwise set it to 0. 

3. Compile it
Run make to build the example mutator.
                                                             

CF Example
~~~~~~~~~~~~~~~~~~
1. First you have to init your memory pool. Use the sbrk system call
to allocate a sufficient large memory range:

void *memory;
memory = sbrk(10000000);
cf_init(10000000, memory);

2. Allocate memory in CF using the cf_malloc function, e.g.:
int **ptr = cf_malloc(44);

3. Deallocate memory in CF using the cf_free function, e.g.:
cf_free(ptr);

4. There exist several debugging functions which show the memory state:
- cf_print_memory_information() prints general memory information
- cf_print_pages_status() shows the status of the pages
- cf_print_free_pages() shows the free pages
- cf_print_abstract_address_space() shows the abstract address space
- cf_print_block_frames_free_list() shows the free block frames