B Tree First-Fit Memory Allocator
by Young H. Song
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, ...
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.
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.
32 bit only.
tested only on Ubuntu 12.04.4 LTS.
memalign() always uses the end of data segment.
mallopt(), malloc_trim(), malloc_usable_size(), malloc_stats(), malloc_get_state(), malloc_set_state() are not implemented.
8 byte aligned, because of glib-2.0 compatibility.
License of the software
Copyright (c) 2014, Young H. Song email@example.com
All rights reserved.
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
memalign() in the middle of data segment.
mallopt(), malloc_trim(), malloc_usable_size(), malloc_stats(), malloc_get_state(), malloc_set_state()
Option of mmap() for payload and brk() for bookeeping meta data.
Please contact me via firstname.lastname@example.org, if you
need to report any bug.
need any other form of license.
need to port BTFF to other platform.
Such as 64 bit, customized OS, etc...
need consulting service related to BTFF.
need to apply BTFF algorithm to other resource management.
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
Copyright © 2014, Young H. Song email@example.com
All rights reserved.