B Tree First Fit malloc() Algorithm

B Tree First-Fit Memory Allocator

by Young H. Song

BTFF Features

O(log n) time with First-Fit behavior, as n is the number of allocated & free blocks.
No boundary tag.
Separation between payload and bookkeeping meta data.
- It does not use any free payload area.
- As of v1.0, payloads are located in data segment area which is acquired by brk(), and bookkeeping meta data are located in separated area which is acquired by mmap().
Small bookkeeping meta data overhead.
Applicable to any kind of resource allocation.
- Memory, Disk, File, ...

BTFF Algorithms

B Tree Structure
- All allocated or free block data are sorted by the primary key which is address.
- free() and realloc() uses address as a key to locate a block.
- malloc() uses available size to search First Fit free block.
- Available sizes are the biggest available size of corresponding sub tree.
- If a block in a node is free, its available size is bigger than 0.
- Available sizes are maintained in case of any update, split or merge.
- Coalescing or splitting is based on standard B Tree operation.
Leaf
- B Tree allows a leaf to have different structure from non-leaf nodes, because there is no rotation in B Tree.
- Leaf & node size of 64 byte is chosen based on cache memory behavior of 16 word, and linear search is used within leaf or node.
- Each block’s address can be calculated from the starting address of the leaf and sizes of blocks.
- A block’s size is variable format which can be from 1 byte to 5 bytes, meaning that smaller payload has smaller bookkeeping meta data overhead. However, the bigger payload is, the smaller the ratio of bookkeeping meta data to payload is.
More details of algorithms.
- Coming soon.

Releases

License of the software

Redistribution and use in source and binary forms, with or without

modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright

notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright

notice, this list of conditions and the following disclaimer in the

documentation and/or other materials provided with the distribution.

3. All advertising materials mentioning features or use of this software

must display the following acknowledgement:

This product includes software developed by the Young H. Song.

4. Neither the name of the Young H. Song nor the

names of its contributors may be used to endorse or promote products

derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY Young H. Song ''AS IS'' AND ANY

EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

DISCLAIMED. IN NO EVENT SHALL Young H. Song BE LIABLE FOR ANY

DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND

ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

How to try BTFF

Future Work

memalign() in the middle of data segment.
mallopt(), malloc_trim(), malloc_usable_size(), malloc_stats(), malloc_get_state(), malloc_set_state()
alignment setting.
Option of mmap() for payload and brk() for bookeeping meta data.
etc...

Contact

Please contact me via song@youngho.net, if you

References

Bayer, Rudolf; McCreight, E. (July 1970), Organization and Maintenance of Large Ordered Indices, Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories.
Donald E. Knuth (April 1997), 2.5. DYNAMIC STORAGE ALLOCATION, The Art of Computer Programming Volume 1 Fundamental Algorithms Third Edition, Addison Wesley